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

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

RIGHTS & PERMISSIONS

Higher Education Press