Aggregation-based dual heterogeneous task allocation in spatial crowdsourcing

Abstract

Spatial crowdsourcing (SC) is a popular data collection paradigm for numerous applications. With the increment of tasks and workers in SC, heterogeneity becomes an unavoidable difficulty in task allocation. Existing researches only focus on the single-heterogeneous task allocation. However, a variety of heterogeneous objects coexist in real-world SC systems. This dramatically expands the space for searching the optimal task allocation solution, affecting the quality and efficiency of data collection. In this paper, an aggregation-based dual heterogeneous task allocation algorithm is put forth. It investigates the impact of dual heterogeneous on the task allocation problem and seeks to maximize the quality of task completion and minimize the average travel distance. This problem is first proved to be NP-hard. Then, a task aggregation method based on locations and requirements is built to reduce task failures. Meanwhile, a time-constrained shortest path planning is also developed to shorten the travel distance in a community. After that, two evolutionary task allocation schemes are presented. Finally, extensive experiments are conducted based on real-world datasets in various contexts. Compared with baseline algorithms, our proposed schemes enhance the quality of task completion by up to 25% and utilize 34% less average travel distance.

Graphical abstract

Keywords

task allocation / aggregation / shortest path / dual heterogeneous / spatial crowdsourcing

Xiaochuan Lin received his BE degree from Henan Normal University, China in 2020, and is pursuing a master’s degree at Jinan University, China. His research interests include mobile crowdsensing

Kaimin Wei is an associate professor at the College of Information Science and Technology, Jinan University, China. He received the PhD degree in 2015. His primary research interests are in mobile computing and artificial intelligence, with a particular emphasis on algorithm optimization and security technologies in these fields

Zhetao Li is a professor in College of Information Science and Technology, Jinan University, China. He received the BEng degree from Xiangtan University, China in 2002, the MEng degree from Beihang University, China in 2005, and the PhD degree from Hunan University, China in 2010. He is a member of IEEE and CCF

Jinpeng Chen is now an associate professor at the School of Computer Science in Beijing University of Posts and Telecommunications, China. His research interests include social network analysis, recommendation system, data mining, and machine learning

Tingrui Pei received the BS and MS degrees from Xiangtan University, China in 1992 and 1998, respectively, and the PhD degree in signal and information processing from the Beijing University of Posts and Telecommunications, China in 2004. From 2006 to 2007, he was a Visiting Scholar with Waseda University in Japan. He is currently a professor with Jinan University, China. His research interests include the Internet of Things, cloud computing, wireless sensor networks and cyberspace security

References

[1] Tong Y, Zhou Z, Zeng Y, Chen L, Shahabi C . Spatial crowdsourcing: a survey. The VLDB Journal, 2019, 29( 1): 217–250

[2] Wang L, Yu Z, Guo B, Yi F, Xiong F . Mobile crowd sensing task optimal allocation: a mobility pattern matching perspective. Frontiers of Computer Science, 2018, 12( 2): 231–244

[3] Wei K, Huang K, Wu Y, Li Z, He H, Zhang J, Chen J, Guo S . High-performance UAV crowdsensing: a deep reinforcement learning approach. IEEE Internet of Things Journal, 2022, 9( 19): 18487–18499

[4] Zhao S, Qi G, He T, Chen J, Liu Z, Wei K . A survey of sparse mobile crowdsensing: developments and opportunities. IEEE Open Journal of the Computer Society, 2022, 3: 73–85

[5] Liu L, Liu W, Zheng Y, Ma H, Zhang C . Third-eye: a mobilephone-enabled crowdsensing system for air quality monitoring. Proceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies, 2018, 2( 1): 20

[6] Wang J, Wang Y, Zhang D, Wang L, Chen C, Lee J W, He Y . Real-time and generic queue time estimation based on mobile crowdsensing. Frontiers of Computer Science, 2017, 11( 1): 49–60

[7] Schnitzler F, Artikis A, Weidlich M, Boutsis I, Liebig T, Piatkowski N, Bockermann C, Morik K, Kalogeraki V, Marecek J, Gal A, Mannor S, Kinane D, Gunopulos D. Heterogeneous stream processing and crowdsourcing for traffic monitoring: highlights. In: Proceedings of the Joint European Conference on Machine Learning and Knowledge Discovery in Databases. 2014, 520−523

[8] Wang J, Wang F, Wang Y, Wang L, Qiu Z, Zhang D, Guo B, Lv Q . HyTasker: hybrid task allocation in mobile crowd sensing. IEEE Transactions on Mobile Computing, 2020, 19( 3): 598–611

[9] Tong Y, Zeng Y, Ding B, Wang L, Chen L . Two-sided online micro-task assignment in spatial crowdsourcing. IEEE Transactions on Knowledge and Data Engineering, 2021, 33( 5): 2295–2309

[10] Asghari M, Shahabi C. On on-line task assignment in spatial crowdsourcing. In: Proceedings of 2017 IEEE International Conference on Big Data. 2017, 395−404

[11] Chen Z, Cheng P, Zeng Y, Chen L. Minimizing maximum delay of task assignment in spatial crowdsourcing. In: Proceedings of the 35th International Conference on Data Engineering. 2019, 1454−1465

[12] Tao Q, Tong Y, Zhou Z, Shi Y, Chen L, Xu K. Differentially private online task assignment in spatial crowdsourcing: a tree-based approach. In: Proceedings of the 36th International Conference on Data Engineering. 2020, 517−528

[13] Wang J, Wang Y, Zhang D, Wang L, Xiong H, Helal A, He Y, Wang F . Fine-grained multitask allocation for participatory sensing with a shared budget. IEEE Internet of Things Journal, 2016, 3( 6): 1395–1405

[14] Wang L, Yu Z, Zhang D, Guo B . Liu C H. Heterogeneous multi-task assignment in mobile crowdsensing using spatiotemporal correlation. IEEE Transactions on Mobile Computing, 2019, 18( 1): 84–97

[15] Shi D, Tong Y, Zhou Z, Song B, Lv W, Yang Q. Learning to assign: towards fair task assignment in large-scale ride hailing. In: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. 2021, 3549−3557

[16] Wang J, Wang Y, Zhang D, Wang F, Xiong H, Chen C, Lv Q, Qiu Z . Multi-task allocation in mobile crowd sensing with individual task quality assurance. IEEE Transactions on Mobile Computing, 2018, 17( 9): 2101–2113

[17] Han J, Zhang Z, Wu X . A real-world-oriented multi-task allocation approach based on multi-agent reinforcement learning in mobile crowd sensing. Information, 2020, 11( 2): 101

[18] Ding Y, Zhang L, Guo L . Dynamic delayed-decision task assignment under spatial-temporal constraints in mobile crowdsensing. IEEE Transactions on Network Science and Engineering, 2022, 9( 4): 2418–2431

[19] Wang E, Yang Y, Wu J, Liu W, Wang X . An efficient prediction-based user recruitment for mobile crowdsensing. IEEE Transactions on Mobile Computing, 2018, 17( 1): 16–28

[20] Cheung M H, Hou F, Huang J, Southwell R . Distributed time-sensitive task selection in mobile crowdsensing. IEEE Transactions on Mobile Computing, 2021, 20( 6): 2172–2185

[21] Struminskaya B, Toepoel V, Lugtig P, Haan M, Luiten A, Schouten B . Understanding willingness to share smartphone-sensor data. Public Opinion Quarterly, 2021, 84( 3): 725–759

[22] Gao X, Huang H, Liu C, Wu F, Chen G . Quality inference based task assignment in mobile crowdsensing. IEEE Transactions on Knowledge and Data Engineering, 2021, 33( 10): 3410–3423

[23] Jiang W, Chen J, Liu X, Liu Y, Lv S . Participant recruitment method aiming at service quality in mobile crowd sensing. Wireless Communications and Mobile Computing, 2021, 2021: 6621659

[24] Gao G, Huang H, Xiao M, Wu J, Sun Y E, Du Y . Budgeted unknown worker recruitment for heterogeneous crowdsensing using CMAB. IEEE Transactions on Mobile Computing, 2022, 21( 11): 3895–3911

[25] Huang Y, Chen H, Ma G, Lin K, Ni Z, Yan N, Wang Z . OPAT: optimized allocation of time-dependent tasks for mobile crowdsensing. IEEE Transactions on Industrial Informatics, 2022, 18( 4): 2476–2485

[26] Liu Y, Guo B, Wang Y, Wu W, Yu Z, Zhang D. TaskMe: multi-task allocation in mobile crowd sensing. In: Proceedings of 2016 ACM International Joint Conference on Pervasive and Ubiquitous Computing. 2016, 403−414

[27] Sun G, Wang Y, Ding X, Hu R . Cost-fair task allocation in mobile crowd sensing with probabilistic users. IEEE Transactions on Mobile Computing, 2021, 20( 2): 403–415

[28] Schubert E, Sander J, Ester M, Kriegel H P, Xu X . DBSCAN revisited, revisited: why and how you should (still) use DBSCAN. ACM Transactions on Database Systems, 2017, 42( 3): 19

[29] Piorkowski M, Sarafijanovic-Djukic N, Grossglauser M. A parsimonious model of mobile partitioned networks with clustering. In: Proceedings of 2009 First International Communication Systems and Networks and Workshops. 2009, 1−10

[30] Yuan J, Zheng Y, Xie X, Sun G. Driving with knowledge from the physical world. In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2011, 316−324

Acknowledgements

This work was supported by the National Key R&D Program of China (No. 2021YFB3101201), and the National Natural Science Foundation of China (Grant Nos. 61972178, 62032020, U22B2027)

Competing interests

The authors declare that they have no competing interests or financial conflicts to disclose.

RIGHTS & PERMISSIONS

2024 Higher Education Press