Page 177 - 《软件学报》2020年第12期

李博扬 等:新型时空众包平台中的在线三维稳定匹配问题 3843

配,可能影响后续的匹配效果.比如在例 4 中,p 1 组成了(w 2 ,u 2 ,p 1 ),p 2 组成了(w 3 ,u 3 ,p 2 ),这个分配方式直接导致 u 4
和 u 5 找不到稳定匹配结果.如果将 w 2 和 u 2 分配到 p 5 ,将 w 3 和 u 3 分配到 p 3 ,那么所有的任务都可以被匹配,匹配
率提高到了 100%.
由于以上的不足,本节提出了基于预测的匹配算法:首先,使用人工智能技术预测出工人和用户的到达时间
区间和大致位置;其次,根据预测结果计算最大化匹配个数的结果;最后,根据预测结果和用户、工人的实际到达
情况,计算真正的匹配结果.
4.1 离线预测
在预测方面,基于历史记录的预测方法已经被广泛研究 [30−32] .文献[13]通过实验结果证明,HP-MSI [32] 具有
较好的预测结果.基于以上的时间和空间划分,本文采用 HP-MSI 作为离线预测工具,根据历史记录信息预测出
工人和用户的出现情况.对于每一个区域,它的工人/用户数量可以表示为一个时间序列,序列的长度为时间槽
的个数,序列中的值代表数量.熵是表征可预测性程度的有效指标,包括随机熵、香农熵和真实熵.真实熵的公式
如下所示:
()i
S real =− ∑ ( P S n ()i )log [ (P S n ( )i )] .
2
()i ( )i
n S ⊂ D n
()i
()i
()i
其中, D 表示区域 i 在 n 时刻的历史数量序,长度为 n; S n ()i 是 D 的有序子序列, (PS n ()i ) 表示在 D 中找到子序
n
n
n
列 S n ()i 的概率.HP-MSI 使用真实熵和移动的相关性来衡量区域级别的需求不确定.为预测区域中的数量,HP-
()i
SMI 采用马尔可夫预测器.预测器的输入是 D 、时刻 n 和马尔可夫预测矩阵 T.输出是 n+1 时刻的预测数量.
n
马尔可夫预测器可以在较低耗时下取得较高的预测准确率.
我们将时间和空间划分为若干个范围,每个时间段称之为“时间槽”,用户和工人的出现时间属于一个时间
槽,等待时间为一个或多个时间槽.整个地图也被划分为多个区域,每个用户和工人都出现在一个区域内,处于
k
区域交界处的用户和工人属于其左下角的区域,坐标按照区域的中心点计算.每个工人被表示为 w ,每个用户
, ij
k
被表示为 u .其中,i 表示区域的编号,j 表示时间槽的编号,k 表示在该区域该时间槽内的编号,从 1 开始.
, ij
例 5:对于表 1 中的出现顺序,将整个时间段分为两个时间槽:[t 0 ,t 4 ]和[t 5 ,t 9 ],那么 u 1-3 和 w 1-3 属于时间槽 1,u 4-6
和 w 4-6 属于时间槽 2.整个地图按照 1×1 的方格划分为 90 个区域,从左下角开始编号,即 u 4 所处于的区域编号为
1
1,w 4 所处于的区域编号为 3.基于以上的划分,可以将预测的工人和用户进行划分,例如 u 4 可以被编号为 u ,1 是
1,2
1
区域编号,2 是时间槽编号,1 是该区域该时间槽内的编号.w 4 可以被编号为 w .
3,2
通过预测方法得出的结果,将工人和用户分别进行编号,然后求解全局的稳定匹配.根据证明,求解全局稳
定匹配是 NP-hard 问题,可以采用最大团的方法求得准确,但时间复杂度极高.本文采用 DSM 算法进行求解 [10] .
静态匹配采用合并和拆分的思想.首先采用贪心求解出一个初步的匹配结果.对于未被匹配的用户,如果拆掉当
前的某个匹配再将拆离的用户递归匹配,如果可以使得匹配总数增加,那么当前的匹配状态将会被调整.由于原
算法并不考虑时间属性,调用过程中需要检查工人出现的时间是否可以覆盖用户出现的时间槽,如果工人出现
过晚,则不能匹配.
4.2 在线匹配
在线匹配的主要思想是:根据离线匹配的结果,为当前到达的工人或用户进行匹配.如果当前到达用户是预
测结果之外的,那么让这个用户延迟到最长等待时间时,到达这个时间点时,根据当前的实际情况,采用延迟匹
配算法进行匹配.在线匹配算法分为两个部分,当用户(或工人)到达时,算法首先在离线匹配结果中查找是是否
存在相关的匹配,如果存在,则直接进行匹配或等待到查找到了离线匹配;如果离线结果中查找不到结果且用户
等待到达最长等待时间,但仍没有被匹配,这种情况是由于预测或离线匹配的误差所导致,对于类似情况的用
户,在不影响离线匹配结果的基础上,调用延迟匹配算法进行求解.
预测指导的匹配算法的伪代码如算法 2 所示.算法的输入是动态到达的用户集 U 和工人集 W、静态的工