Online matching algorithm for supporting periodic tasks in spatial crowdsourcing

doi:10.11772/j.issn.1001-9081.2024060747

Journal of Computer Applications ›› 2025, Vol. 45 ›› Issue (6): 1934-1944.DOI: 10.11772/j.issn.1001-9081.2024060747

• Advanced computing • Previous Articles

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)

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

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

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

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

Abstract

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

摘要：

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

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

CLC Number:

TP311

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.

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

Figures/Tables 12

Fig. 1 Example of periodic task matching

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

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

Tab. 3 Main symbols

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

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

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

Fig. 2 Influence of S on algorithm performance

Fig. 3 Influence of W on algorithm performance

Fig. 4 Influence of γ on algorithm performance

Fig. 5 Influence of ρ on algorithm performance

Fig. 6 Familiarity profit analysis

Fig. 7 Convergence analysis of GT algorithm

Fig. 8 Common optimization objective analysis

References 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]	Peng PENG, Zhiwei NI, Xuhui ZHU. Task allocation method of spatial crowdsourcing based on user satisfaction utility [J]. Journal of Computer Applications, 2022, 42(10): 3235-3243.
[2]	RAN Jiamin, NI Zhiwei, PENG Peng, ZHU Xuhui. Task allocation strategy considering service quality of spatial crowdsourcing workers and its glowworm swarm optimization algorithm solution [J]. Journal of Computer Applications, 2021, 41(3): 794-802.
[3]	NIE Xichan, ZHANG Yang, YU Dunhui, ZHANG Xingsheng. Spatial crowdsourcing task allocation algorithm for global optimization [J]. Journal of Computer Applications, 2020, 40(7): 1950-1958.
[4]	YU Dunhui, YUAN Xu, ZHANG Wanshan, WANG Chenxu. Spatiotemporal crowdsourcing online task allocation algorithm based ondynamic threshold [J]. Journal of Computer Applications, 2020, 40(3): 658-664.
[5]	ZHANG Xingsheng, YU Dunhui, ZHANG Wanshan, WANG Chenxu. Time utility balanced online task assignment algorithm under spatial crowdsourcing environment [J]. Journal of Computer Applications, 2019, 39(5): 1357-1363.
[6]	XIA Jun, YUAN Shuai, YANG Yi. Scheduling algorithm for periodic tasks with low energy consumption based on heterogeneous mult-core platforms [J]. Journal of Computer Applications, 2019, 39(10): 2980-2984.
[7]	LIU Hui, LI Sheng'en. Adaptive threshold algorithm based on statistical prediction under spatial crowdsourcing environment [J]. Journal of Computer Applications, 2018, 38(2): 415-420.
[8]	MAO Yingchi, MU Chao, BAO Wei, LI Xiaofang. Multi-type task assignment and scheduling oriented to spatial crowdsourcing [J]. Journal of Computer Applications, 2018, 38(1): 6-12.
[9]	CAO Jie, ZENG Guosun. Dual fault-tolerant scheduling algorithm of periodic and aperiodic hybrid real-time tasks in cloud environment [J]. Journal of Computer Applications, 2015, 35(3): 648-653.
[10]	. Improved task scheduling algorithm for embedded real-time operating system and its application [J]. Journal of Computer Applications, 2009, 29(09): 2516-2519.
[11]	ZHU Xiang-bin,JIN Yong-xian. Analysis and research of a window-constrained real-time system with mutual frames [J]. Journal of Computer Applications, 2005, 25(08): 1780-1782.

Online matching algorithm for supporting periodic tasks in spatial crowdsourcing

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 12

References 46

Related Articles 11

Recommended Articles

Metrics