空间众包中支持周期性任务的在线匹配算法

doi:10.11772/j.issn.1001-9081.2024060747

《计算机应用》唯一官方网站 ›› 2025, Vol. 45 ›› Issue (6): 1934-1944.DOI: 10.11772/j.issn.1001-9081.2024060747

• 先进计算 • 上一篇

空间众包中支持周期性任务的在线匹配算法

刘俊岭¹^,², 孙萌¹^,², 孙焕良¹^,²(), 许景科¹^,²^,³

^1.沈阳建筑大学计算机科学与工程学院，沈阳 110168
^2.辽宁省城市建设大数据管理与分析重点实验室（沈阳建筑大学），沈阳 110168
^3.国家特种计算机工程技术研究中心沈阳分中心（沈阳建筑大学），沈阳 110168

收稿日期:2024-06-11 修回日期:2024-08-22 接受日期:2024-08-26 发布日期:2024-09-06 出版日期:2025-06-10
通讯作者: 孙焕良
作者简介:刘俊岭（1972—），女，辽宁沈阳人，副教授，博士，CCF会员，主要研究方向：时空数据查询、数据挖掘
孙萌（2000—），女，山东莱阳人，硕士研究生，CCF会员，主要研究方向：时空众包、数据挖掘
孙焕良（1969—），男，黑龙江望奎人，教授，博士生导师，博士，CCF高级会员，主要研究方向：空间数据管理、数据挖掘 sunhl@sjzu.edu.cn
许景科（1976—），男，辽宁海城人，教授，博士，CCF会员，主要研究方向：时空数据库、数据挖掘。
基金资助:
国家重点研发计划项目(2021YFF0306303);辽宁省教育厅项目(LJKMZ20220916)

Online matching algorithm for supporting periodic tasks in spatial crowdsourcing

Junling LIU¹^,², Meng SUN¹^,², Huanliang SUN¹^,²(), Jingke XU¹^,²^,³

^1.School of Computer Science and Engineering，Shenyang Jianzhu University，Shenyang Liaoning 110168，China
^2.Liaoning Province Big Data Management and Analysis Laboratory of Urban Construction （Shenyang Jianzhu University），Shenyang Liaoning 110168，China
^3.Shenyang Branch of National Special Computer Engineering Technology Research Center （Shenyang Jianzhu University），Shenyang Liaoning 110168，China

Received:2024-06-11 Revised:2024-08-22 Accepted:2024-08-26 Online:2024-09-06 Published:2025-06-10
Contact: Huanliang SUN
About author:LIU Junling， born in 1972， Ph. D.， associate professor. Her research interests include spatio-temporal data query， data mining.
SUN Meng， born in 2000， M. S. candidate. Her research interests include spatial crowdsourcing， data mining.
SUN Huanliang， born in 1969， Ph. D.， professor. His research interests include spatial data management， data mining.
XU Jingke， born in 1976， Ph. D.， professor. His research interests include spatio-temporal database， data mining.
Supported by:
National Key Research and Development Program of China(2021YFF0306303);Project of Educational Department of Liaoning Province(LJKMZ20220916)

摘要/Abstract

摘要：

针对空间众包中的一类重复多次且有固定需求的周期性任务，现有的匹配算法忽略了周期性任务对熟悉度的需求，提出一种空间众包中支持周期性任务的在线匹配算法。首先，将在线匹配问题视为多人游戏，将任务视为游戏的独立参与者，根据任务倾向于匹配熟悉度高的工人，工人倾向于匹配报酬高、距离近的任务的需求，确定玩家的效用函数，并进行博弈论（GT）分析；其次，将模拟退火（SA）策略引入GT的更新策略中，设计基于SA策略的GT算法；最后，在达到纳什均衡时实现总效用更大的匹配。在真实数据集上的实验结果表明，相较于现有相关算法，所提GT算法的匹配具有最高的总效用。可见，所提GT算法实现了更符合周期性任务和工人各自需求的匹配结果，可以提升在线空间众包平台的用户满意度。

关键词: 空间众包, 周期性任务, 博弈论, 总效用, 熟悉度

Abstract:

For a type of repetitive periodic tasks with fixed demand in spatial crowdsourcing， the existing matching algorithms ignore the familiarity required for periodic tasks， so that an online matching algorithm for supporting periodic tasks in spatial crowdsourcing was proposed. Firstly， the online matching problem was regarded as a multiplayer game， with tasks considered as independent participants in the game， and utility functions of the players were determined based on the need of tasks’ preference for matching workers with high familiarity and workers’ preference for tasks with high rewards and short distances， which were then analyzed using Game Theory （GT）. Then， a Simulated Annealing （SA） strategy was introduced into the updating strategy of GT， resulting in the design of GT algorithm based on SA strategy. Finally， a matching with greater total utility was achieved with reaching a Nash equilibrium. Experimental results on real datasets demonstrate that the proposed GT algorithm achieves the highest total utility compared to existing related algorithm， the matching of the proposed GT algorithm has the highest total utility. It can be seen that the proposed GT algorithm achieves matching results that better meet the need of periodic tasks and workers， which can enhance user satisfaction on online spatial crowdsourcing platforms.

Key words: spatial crowdsourcing, periodic task, Game Theory (GT), total utility, familiarity

中图分类号:

TP311

刘俊岭, 孙萌, 孙焕良, 许景科. 空间众包中支持周期性任务的在线匹配算法[J]. 计算机应用, 2025, 45(6): 1934-1944.

Junling LIU, Meng SUN, Huanliang SUN, Jingke XU. Online matching algorithm for supporting periodic tasks in spatial crowdsourcing[J]. Journal of Computer Applications, 2025, 45(6): 1934-1944.

图/表 12

图1 周期性任务匹配示例

Fig. 1 Example of periodic task matching

表1 任务信息

Tab. 1 Task information

任务ID	奖励	任务发布者	截止时间	发布时间
s₁	6	u₁	10	5
s_2-3	7	u₂	10	5
s_3-2	6	u₃	10	5
s_4-1	8	u₄	10	5
s₅	5	u₅	11	6
s₆	6	u₆	11	6
s₇	8	u₁	11	6

表2 工人-任务熟悉度矩阵

Tab. 2 Worker-task familiarity matrix

工人	任务
工人	u₁	u₂	u₃	u₄	u₅	u₆
w₁	10	7	9	2	3	5
w₂	8	0	6	6	4	2
w₃	0	5	0	7	4	6
w₄	2	3	5	4	8	9
w₅	5	6	7	5	0	8
w₆	3	2	4	3	9	4

表3 主要符号

Tab. 3 Main symbols

符号	说明
s	空间任务
w	工人
AS	活跃任务集
AW	活跃工人集
AVS（w）	工人w的可用任务集
AVW（s）	任务s的可用工人集
w_f	周期性任务曾经熟悉（familiar）匹配的工人

表4 实验参数设置

Tab. 4 Experimental parameters setting

$S$	$W$	γ	ρ
1 000	1 000	0.2	0.05
2 000	2 000	0.4	0.06
3 000	3 000	0.5	0.07
4 000	4 000	0.6	0.08
5 000	5 000	0.8	0.09

表4 实验参数设置

Tab. 4 Experimental parameters setting

$S$	$W$	γ	ρ
1 000	1 000	0.2	0.05
2 000	2 000	0.4	0.06
3 000	3 000	0.5	0.07
4 000	4 000	0.6	0.08
5 000	5 000	0.8	0.09

图2 S对算法性能的影响

Fig. 2 Influence of S on algorithm performance

图3 W对算法性能的影响

Fig. 3 Influence of W on algorithm performance

图4 γ对算法性能的影响

Fig. 4 Influence of γ on algorithm performance

图5 不同ρ对算法性能的影响

Fig. 5 Influence of ρ on algorithm performance

图6 熟悉度收益分析

Fig. 6 Familiarity profit analysis

图7 GT算法收敛性分析

Fig. 7 Convergence analysis of GT algorithm

图8 常用优化目标分析

Fig. 8 Common optimization objective analysis

参考文献 46

1	ZHANG J L， JIANG T， GAO X， et al. An online fairness-aware task planning approach for spatial crowdsourcing［J］. IEEE Transactions on Mobile Computing， 2024， 23（1）： 150-163.
2	YAO J， YANG L， XU X. Online dependent task assignment in preference aware spatial crowdsourcing［J］. IEEE Transactions on Services Computing， 2023， 16（4）： 2827-2840.
3	高晓沨，张嘉乐，高宇岑，等. 众包群智与算法优化［J］. 中国计算机学会通讯， 2023， 19（3）：71-80.
	GAO X F， ZHANG J L， GAO Y C， et al. Crowdsourcing collective intelligence and algorithm optimization［J］. Communications of the China Computer Federation， 2023， 19（3）： 71-80.
4	FURUHATA M， DESSOUKY M， ORDÓÑEZ F， et al. Ridesharing： the state-of-the-art and future directions［J］. Transportation Research Part B： Methodological， 2013， 57： 28-46.
5	XU X， LIU A， LIU G， et al. Drive less but finish more： food delivery based on multi-level workers in spatial crowdsourcing［C］// Proceedings of the 31st ACM International Conference on Information and Knowledge Management. New York： ACM， 2022： 2331-2340.
6	XIAO L， DRIDI M， HASSANI A H EL， et al. Mathematical model for the home health care scheduling and routing problem with flexible lunch break requirements［J］. IFAC-PapersOnLine， 2018， 51（11）： 334-339.
7	ZHENG Y， LIU F， HSIEH H P. U-Air： when urban air quality inference meets big data［C］// Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2013： 1436-1444.
8	CORIC V， GRUTESER M. Crowdsensing maps of on-street parking spaces［C］// Proceedings of the 2013 IEEE International Conference on Distributed Computing in Sensor Systems. Piscataway： IEEE， 2013： 115-122.
9	MASLOW A H. A theory of human motivation［J］. Psychological Review， 1943， 50（4）： 370-396.
10	REIS H T， MANIACI M R， CAPRARIELLO P A， et al. Familiarity does indeed promote attraction in live interaction［J］. Journal of Personality and Social Psychology， 2011， 101（3）： 557-570.
11	范红霞，马逸群，高培霞. 人际熟悉度影响信任水平的情境效应［J］. 心理技术与应用， 2016， 4（3）：135-138.
	FAN H X， MA Y Q， GAO P X. Interpersonal familiarity affect the trust level： the effect of context［J］. Psychology： Techniques and Applications， 2016， 4（3）： 135-138.
12	LI B， CHENG Y， YUAN Y， et al. Competition and cooperation： global task assignment in spatial crowdsourcing［J］. IEEE Transactions on Knowledge and Data Engineering， 2023， 35（10）： 9998-10010.
13	ZHAO Y， ZHENG K， GUO J， et al. Fairness-aware task assignment in spatial crowdsourcing： game-theoretic approaches［C］// Proceedings of the IEEE 37th International Conference on Data Engineering. Piscataway： IEEE， 2021： 265-276.
14	ZHAO Y， GUO J， CHEN X， et al. Coalition-based task assignment in spatial crowdsourcing［C］// Proceedings of the IEEE 37th International Conference on Data Engineering. Piscataway： IEEE， 2021： 241-252.
15	GALE D， SHAPLEY L S. College admissions and the stability of marriage［J］. The American Mathematical Monthly， 1962， 69（1）： 9-15.
16	ZHOU X， LIANG S， LI K， et al. Bilateral preference-aware task assignment in spatial crowdsourcing ［C］// Proceedings of the IEEE 38th International Conference on Data Engineering. Piscataway： IEEE， 2022： 1687-1699.
17	LIN Y， JIANG Y， LI Y， et al. Privacy-preserving batch-based task assignment over spatial crowdsourcing platforms［J］. Computer Networks， 2024， 241： No.110196.
18	ZHAO Y， ZHENG K， LI Y， et al. Profit optimization in spatial crowdsourcing： effectiveness and efficiency［J］. IEEE Transactions on Knowledge and Data Engineering， 2023， 35（8）： 8386-8401.
19	XU Y， XIAO M， WU J， et al. Incentive mechanism for spatial crowdsourcing with unknown social-aware workers： a three-stage Stackelberg game approach［J］. IEEE Transactions on Mobile Computing， 2023， 22（8）： 4698-4713.
20	LIU Y， GUO B， WANG Y， et al. TaskMe： multi-task allocation in mobile crowd sensing［C］// Proceedings of the 2016 ACM International Joint Conference on Pervasive and Ubiquitous Computing. New York： ACM， 2016： 403-414.
21	XIONG H， ZHANG D， CHEN G， et al. iCrowd： near-optimal task allocation for piggyback crowdsensing ［J］. IEEE Transactions on Mobile Computing， 2016， 15（8）： 2010-2022.
22	GUO B， CHEN H， YU Z， et al. FlierMeet： a mobile crowdsensing system for cross-space public information reposting， tagging， and sharing［J］. IEEE Transactions on Mobile Computing， 2015， 14（10）： 2020-2033.
23	TO H， FAN L， TRAN L， et al. Real-time task assignment in hyperlocal spatial crowdsourcing under budget constraints［C］// Proceedings of the 2016 IEEE International Conference on Pervasive Computing and Communications. Piscataway： IEEE， 2016： 1-8.
24	ZHENG L， CHEN L. Multi-campaign oriented spatial crowdsourcing［J］. IEEE Transactions on Knowledge and Data Engineering， 2020， 32（4）： 700-713.
25	ZHAO Y， LIU J， LI Y， et al. Preference-aware group task assignment in spatial crowdsourcing： effectiveness and efficiency［J］. IEEE Transactions on Knowledge and Data Engineering， 2023， 35（10）： 10722-10734.
26	WU G， CHEN Z， LIU J， et al. Task assignment for social-oriented crowdsourcing ［J］. Frontiers of Computer Science， 2023， 15（2）： No.152316.
27	CHEN Z， CHENG P， ZENG Y， et al. Minimizing maximum delay of task assignment in spatial crowdsourcing［C］// Proceedings of the IEEE 35th International Conference on Data Engineering. Piscataway： IEEE， 2019： 1454-1465.
28	王府鑫，王宁，曾奇雄. 基于工人长短期时空偏好的众包任务分配［J］. 软件学报， 2024， 35（10）： 4710-4728.
	WANG F X， WANG N， ZENG Q X. Long- and short-term spatio-temporal preference-aware task assignment in spatial crowdsourcing［J］. Journal of Software， 2024， 35（10）： 4710-4728.
29	MA Y， GAO X， BHATTI S S， et al. Clustering based priority queue algorithm for spatial task assignment in crowdsourcing ［J］. IEEE Transactions on Services Computing， 2024， 17（2）： 452-465.
30	刘俊岭，高新宇，孙焕良，等. 空间众包中隔离敏感的任务匹配算法［J］. 计算机工程与应用， 2024， 60（17）： 252-262.
	LIU J L， GAO X Y， SUN H L， et al. Isolation-sensitive task assignment in spatial crowdsourcing［J］. Computer Engineering and Applications， 2024， 60（17）： 252-262.
31	徐天承，乔少杰，武俊，等. 一种基于时空位置预测的空间众包任务分配方法［J］. 计算机研究与发展， 2022， 59（2）：310-328.
	XU T C， QIAO S J， WU J， et al. A spatial crowdsourcing task assignment approach based on spatio-temporal location prediction［J］. Journal of Computer Research and Development， 2022， 59（2）： 310-328.
32	裴树军，宋冬梅，孔德凯. Map/Reduce下快速剪枝算法在复杂任务调度中的应用［J］. 计算机科学与探索， 2018， 12（1）：72-81.
	PEI S J， SONG D M， KONG D K. Application of fast pruning algorithm in Map/Reduce for complex tasks scheduling［J］. Journal of Frontiers of Computer Science and Technology， 2018， 12（1）： 72-81.
33	LIU Z， LI K， ZHOU X， et al. Multi-stage complex task assignment in spatial crowdsourcing［J］. Information Sciences， 2022， 586： 119-139.
34	TONG Y， ZHOU Z， ZENG Y， et al. Spatial crowdsourcing： a survey ［J］. The VLDB Journal， 2020， 29： 217-250.
35	GEFEN D. E-commerce： the role of familiarity and trust［J］. Omega， 2000， 28（6）： 725-737.
36	MONDERER D， SHAPLEY L S. Potential games［J］. Games and Economic Behavior， 1996， 14（1）： 124-143.
37	郑延斌，王林林，席棚雪，等. 基于蚁群算法及博弈论的多Agent路径规划算法［J］. 计算机应用， 2019， 39（3）：681-687.
	ZHENG Y B， WANG L L， XI P X， et al. Multi-Agent path planning algorithm based on ant colony algorithm and game theory［J］. Journal of Computer Applications， 2019， 39（3）： 681-687.
38	FUDENBERG D， TIROLE J. Game theory［M］. Cambridge： MIT Press， 1991： 11-18.
39	KAUFMAN D E， SMITH R L. Fastest paths in time-dependent networks for intelligent vehicle-highway systems application［J］. Journal of Intelligent Transportation Systems， 1993， 1（1）： 1-11.
40	KIRKPATRICK S， GELATT C D， Jr， VECCHI M P. Optimization by simulated annealing［J］. Science， 1983， 220（4598）： 671-680.
41	NISAN N， ROUGHGARDEN T， TARDOS E， et al. Algorithmic game theory ［M］. Cambridge： Cambridge University Press， 2007： 25-29.
42	LIU Y， DONG L， MARKS R J. Common control channel assignment in cognitive radio networks using potential game theory［C］// Proceedings of the 2013 IEEE Wireless Communications and Networking Conference. Piscataway： IEEE， 2013： 315-320.
43	FABRIKANT A， PAPADIMITRIOU C， TALWAR K. The complexity of pure Nash equilibria［C］// Proceedings of the 36th Annual ACM Symposium on Theory of Computing. New York： ACM， 2004： 604-612.
44	OSBORNE M J. An introduction to game theory［M］. Oxford： Oxford University Press， 2003： 133-138.
45	GIBBONS R. An introduction to applicable game theory［J］. Journal of Economic Perspectives， 1997， 11（1）： 127-149.
46	CHO E， MYERS S A， LESKOVEC J. Friendship and mobility： user movement in location-based social networks［C］// Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2011： 1082-1090.

[1]	王思蕊, 程世娟, 袁非梦. 基于改进证据融合的高可靠产品可靠性评估方法[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 2140-2146.
[2]	许蕴韬, 朱俊武, 孙彬文, 孙茂圣, 陈四海. 选举供应链：基于区块链的供应链自治框架[J]. 《计算机应用》唯一官方网站, 2022, 42(6): 1770-1775.
[3]	龚胜佳, 张琳琳, 赵楷, 刘军涛, 杨涵. 基于区块链技术的虚假新闻检测方法[J]. 《计算机应用》唯一官方网站, 2022, 42(11): 3458-3464.
[4]	彭鹏, 倪志伟, 朱旭辉. 基于用户满意效用的空间众包任务分配方法[J]. 《计算机应用》唯一官方网站, 2022, 42(10): 3235-3243.
[5]	王艺洁, 凡佳飞, 王陈宇. 云边环境下基于博弈论的两阶段任务迁移策略[J]. 计算机应用, 2021, 41(5): 1392-1398.
[6]	张舒瑶, 李勇华, 范家佳. 基于博弈论的散货港口堆场堆位分配算法[J]. 计算机应用, 2021, 41(3): 867-874.
[7]	毛莺池, 徐雪松, 刘鹏飞. 基于稳定匹配的多用户任务卸载策略[J]. 计算机应用, 2021, 41(3): 786-793.
[8]	冉家敏, 倪志伟, 彭鹏, 朱旭辉. 考虑空间众包工作者服务质量的任务分配策略及其萤火虫群优化算法求解[J]. 计算机应用, 2021, 41(3): 794-802.
[9]	雷鹰, 郑万波, 魏嵬, 夏云霓, 李晓波, 刘诚武, 谢洪. 基于概率性能感知演化博弈策略的“云+边”混合环境中任务卸载方法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3302-3308.
[10]	郑延斌, 樊文鑫, 韩梦云, 陶雪丽. 基于博弈论及Q学习的多Agent协作追捕算法[J]. 计算机应用, 2020, 40(6): 1613-1620.
[11]	余敦辉, 袁旭, 张万山, 王晨旭. 基于动态阈值的时空众包在线分配算法[J]. 计算机应用, 2020, 40(3): 658-664.
[12]	范家佳, 刘洪星, 李勇华, 杨丽金. 基于博弈论的内河港口作业车辆协同选路方法[J]. 计算机应用, 2020, 40(1): 50-55.
[13]	张兴盛, 余敦辉, 张万山, 王晨旭. 时空众包环境下时效均衡的在线任务分配算法[J]. 计算机应用, 2019, 39(5): 1357-1363.
[14]	王甜甜, 于双元, 徐保民. 基于策略梯度算法的工作量证明中挖矿困境研究[J]. 计算机应用, 2019, 39(5): 1336-1342.
[15]	郑延斌, 王林林, 席鹏雪, 樊文鑫, 韩梦云. 基于蚁群算法及博弈论的多Agent路径规划算法[J]. 计算机应用, 2019, 39(3): 681-687.

空间众包中支持周期性任务的在线匹配算法

Online matching algorithm for supporting periodic tasks in spatial crowdsourcing

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 46

相关文章 15

编辑推荐

Metrics