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

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

• 算法的运行时间如图 9(b)所示:POM 算法的运行时间呈先减少后上升的趋势.在区域过大或过小时,算
法大部分时间调用 DM 算法,导致运行时间升高,和 DM 算法的运行时间相近;
• 算法的内存占用如图 9(c)所示:由于区域划分的增大,离线匹配结果增大,离线匹配结果增加,导致 POM
算法存储空间增大.原因和时间槽增大的情况类似.
5.4 实验总结

在本节中,我们使用真实数据集和合成数据集分别对算法的效用和效率进行了测试.在合理的设置下,POM
算法的实验结果和运行速度都高于 DM 算法,但是算法占用内存高与 DM 算法.在不同参数的测试中,DM 和
POM 算法都受到数据规模和用户等待时间的影响.随着数据规模的增长,两种算法的匹配数量、运行时间和内
存消耗都进行增长.随着等待时间的延长,两种算法的匹配数量、运行时间和内存消耗也都进行增长,但是在时
间过长或过短时,都会影响 POM 算法的效果.POM 算法还受时间槽长度和划分区域大小所影响.时间槽长度和
用户等待时间的差距影响了 POM 算法的效果,当时间槽长度和用户等待时间相近时,POM 的效果较好.区域划
分的粒度通过影响预测结果和离线匹配,从而影响 POM 的效果.在本实验中,采用 0.5km×0.5km 的划分时 POM
获得较好的效果.

6 结论及展望

本文研究新型时空众包平台中在线稳定匹配问题.区别于传统的研究工作,本文考虑工人、用户和工作点
这 3 种角色,将二维匹配问题扩展到三维问题,同时研究如何求解在线场景下的稳定匹配问题.本文首先给出了
三维在线稳定匹配问题的定义,然后提出一种基础算法(延时匹配算法)和一种改进算法(预测指导的匹配算法)
对问题进行求解.延时匹配算法当用户到达最长等待时间时,根据当前到达的工人和闲置的工作点进行匹配.预
测指导的匹配算法采用 HP-MSI 方法对数据分布进行预测,并生成离线匹配结果,算法根据离线匹配结果对在
线匹配进行指导.最后,本文使用真实数据集和合成数据集对算法进行实验.实验结果验证了算法的效果和效
率,以及算法的可扩展性和不同参数对算法的影响.实验结果表明:在合理的参数配置下,预测指导的匹配算法
的匹配结果和运行时间皆优于延时匹配算法.
未来工作中,将考虑用户和工人的活动距离约束,即用户和工人可以选择可接受的服务点的距离范围,防止
出现远距离移动的情况.同时,为用户的任务设置服务时间,工作点在服务中处于占用状态,服务完成后将被释
放,供其他用户使用.

References:
[1] Tong YX, Yuan Y, Cheng YR, Chen L, Wang GR. Survey on spatiotemporal crowdsourced data management techniques. Ruan Jian
Xue Bao/Journal of Software, 2017,28(1):35−58 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/28/35.htm
[doi: 10.13328/j.cnki.jos.005140]
[2] Kazemi L, Shahabi C. GeoCrowd: Enabling query answering with spatial crowdsourcing. In: Proc. of the Int’l Conf. on Advances
in Geographic Information Systems. Los Angeles: ACM, 2012. 189−198.
[3] To H, Shahabi C, Kazemi L. A server-assigned spatial crowdsourcing framework. ACM Trans. on Spatial Algorithms and Systems,
2015,1(1):2:1−2:28.
[4] Zheng L, Chen L. Mutual benefit aware task assignment in a bipartite labor market. In: Proc. of the 32nd IEEE Int’l Conf. on Data
Engineering. Helsinki: IEEE, 2016. 73−84.
[5] Song TS, Tong YX, Wang LB, She JY, Yao B, Chen L, Xu K. Trichromatic online matching in real-time spatial crowdsourcing. In:
Proc. of the 33rd IEEE Int’l Conf. on Data Engineering. San Diego: IEEE, 2017. 1009−1020.
[6] Li BY, Cheng YR, Yuan Y, Wang GR, Chen L. Three-Dimensional stable matching problem for spatial crowdsourcing platforms.
In: Proc. of the 25th ACM SIGKDD Conf. on Knowledge Discovery and Data Mining. Anchorage: ACM, 2019. 1643−1653.
[7] Xing YP, Wang LM, Li ZY, Zhan YZ. Multi-Attribute crowdsourcing task assignment with stability and satisfactory. IEEE Access,
2019,7:133351−133361.