Aggregation-based dual heterogeneous task allocation in spatial crowdsourcing

doi:10.1007/s11704-023-3133-6

Front. Comput. Sci.

2024, Vol. 18

Issue (6) : 186605 https://doi.org/10.1007/s11704-023-3133-6

RESEARCH ARTICLE

Aggregation-based dual heterogeneous task allocation in spatial crowdsourcing

Xiaochuan LIN^1,^2,³, Kaimin WEI^1,^2,³(

), Zhetao LI^1,^2,³, Jinpeng CHEN⁴, Tingrui PEI^1,^2,³

¹. College of Information Science and Technology & Cyberspace Security, Jinan University, Guangzhou 510632, China
². National & Local Joint Engineering Research Center of Network Security Detection and Protection Technology, Guangzhou 510632, China
³. Guangdong Provincial Key Laboratory of Data Security and Privacy Protection, Guangzhou 510632, China
⁴. School of Computer Science, Beijing University of Posts and Telecommunications, Beijing 100876, China

Download: PDF(13642 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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.

Keywords task allocation aggregation shortest path dual heterogeneous spatial crowdsourcing

Corresponding Author(s): Kaimin WEI

Just Accepted Date: 04 July 2023 Issue Date: 27 September 2023

Cite this article:

Xiaochuan LIN,Kaimin WEI,Zhetao LI, et al. Aggregation-based dual heterogeneous task allocation in spatial crowdsourcing[J]. Front. Comput. Sci., 2024, 18(6): 186605.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-023-3133-6
https://academic.hep.com.cn/fcs/EN/Y2024/V18/I6/186605

Fig.1 An illustration of multi-heterogeneous task allocation

Symbol	Description
$T$	A set of tasks in SC
$t i$	Task $t i$
$t t i l t$	A tuple of task $t i$ ’s location and deadline
$t t i s$	A set of sensors required by task $t i$
$t t i b$	The budget of task $t i$
$t t i p$	The number of workers required for task $t i$
$W$	The collection of workers in SC
$w j$	Worker $w j$
$w w j s$	A collection of sensors owned by the worker $w j$
$s w j l t$	The location and current time of worker $w j$
$Q o T t i$	The completion quality of task $t i$
$D t i$	The distance that workers move to carry out task $t i$
$N (μ, σ 2)$	The normal distribution with $μ$ and $σ$
$r a n d i (a, b)$	Generate a random integer between $a$ and $b$

Tab.1 Symbol explanation

Tasks	Location(lat, lng)	Deadline
Air Quality Monitorin ( $t 1$ )	(?122.425, 37.7846)	12:40:00
Road Condition Monitoring ( $t 2$ )	(?122.424, 37.784)	12:10:00
Noise Level ( $t 3$ )	(?122.424, 37.784)	12:32:00
Water Quality Inspection ( $t 4$ )	(?122.428, 37.781)	12:10:00

Tab.2 The spatio-temporal details of task examples

Tasks	Sensors	Budget	Sample size
Air Quality Monitorin ( $t 1$ )	$s 1$ , $s 2$ , $s 3$	＄30	[2, 4]
Road Condition Monitoring ( $t 2$ )	$s 1$ , $s 2$ , $s 3$ , $4$	＄6	[1, 4]
Noise Level ( $t 3$ )	$s 1$ , $s 3$	＄12	[2, 3]
Water Quality Inspection ( $t 4$ )	$s 1$ , $s 2$ , $s 4$	＄13	[1, 3]

Tab.3 The sensing requirements of task examples

Workers	Location(lat, lng)	Current time
$w 1$	(?122.427, 37.783)	12:00:00
$w 2$	(?122.422, 37.783)	12:00:00
$w 3$	(?122.422, 37.784)	12:00:00
$w 4$	(?122.429, 37.781)	12:00:00
$w 5$	(?122.425, 37.781)	12:00:00

Tab.4 The spatio-temporal details of worker examples

Workers	Description (sensor type, expected payment, workload)
$w 1$	( $s 1$ , ＄0, 3), ( $s 2$ , ＄2, 2), ( $s 3$ , ＄2, 3), ( $s 4$ , ＄4, 3)
$w 2$	( $s 1$ , ＄0, 1), ( $s 2$ , ＄3, 4), ( $s 3$ , ＄2, 3)
$w 3$	( $s 1$ , ＄4, 3), ( $s 2$ , ＄0, 4), ( $s 3$ , ＄3, 2), ( $s 4$ , ＄2, 3)
$w 4$	( $s 1$ , ＄2, 3), ( $s 2$ , ＄0, 3), ( $s 3$ , ＄2, 3), ( $s 4$ , ＄2, 3)
$w 5$	( $s 1$ , ＄2, 3), ( $s 2$ , ＄0, 2), ( $s 3$ , ＄3, 2), ( $4$ , ＄0, 3)

Tab.5 The abilities and privacy’s details of worker examples

Fig.2 An overview of the aggregation-based dual heterogeneous multi-task allocation algorithm

Parameters	Values
$p t i$	$20 %$
$T S t i$	$N (4, 1)$
$u p t i$	$N (4, 1)$
$N t i m i n$	$r a n d i (2, 4)$
$N t i m a x$	$r a n d i (4, 6)$
$N S c o m$	$10$
$N S p a r$	$2$

Tab.6 Rules for generating attributes of tasks

Parameters	Values
$p p h w j$	$50 %$
$p p s w j$	$50 %$
$d u p$	2
$b u p$	1
$v$	$2 m / s$
$w l w j s j$	$r a n d i (5, 10)$
$E P w j s j$	$r a n d i (2, 5)$

Tab.7 Rules for generating attributes of workers

Fig.3 Experiment results with different numbers of workers. (a) Cabspotting; (b) Cabspotting; (c) Cabspotting; (d) T-Drive; (e) T-Drive; (f) T-Drive

Fig.4 Experimental results with different number of tasks. (a) Cabspotting; (b) Cabspotting; (c) Cabspotting; (d) T-Drive; (e) T-Drive; (f) T-Drive

1	Y, Tong Z, Zhou Y, Zeng L, Chen C Shahabi . Spatial crowdsourcing: a survey. The VLDB Journal, 2019, 29( 1): 217–250
2	L, Wang Z, Yu B, Guo F, Yi F Xiong . Mobile crowd sensing task optimal allocation: a mobility pattern matching perspective. Frontiers of Computer Science, 2018, 12( 2): 231–244
3	K, Wei K, Huang Y, Wu Z, Li H, He J, Zhang J, Chen S Guo . High-performance UAV crowdsensing: a deep reinforcement learning approach. IEEE Internet of Things Journal, 2022, 9( 19): 18487–18499
4	S, Zhao G, Qi T, He J, Chen Z, Liu K Wei . A survey of sparse mobile crowdsensing: developments and opportunities. IEEE Open Journal of the Computer Society, 2022, 3: 73–85
5	L, Liu W, Liu Y, Zheng H, Ma C Zhang . 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	J, Wang Y, Wang D, Zhang L, Wang C, Chen J W, Lee Y He . Real-time and generic queue time estimation based on mobile crowdsensing. Frontiers of Computer Science, 2017, 11( 1): 49–60
7	F, Schnitzler A, Artikis M, Weidlich I, Boutsis T, Liebig N, Piatkowski C, Bockermann K, Morik V, Kalogeraki J, Marecek A, Gal S, Mannor D, Kinane D Gunopulos . 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	J, Wang F, Wang Y, Wang L, Wang Z, Qiu D, Zhang B, Guo Q Lv . HyTasker: hybrid task allocation in mobile crowd sensing. IEEE Transactions on Mobile Computing, 2020, 19( 3): 598–611
9	Y, Tong Y, Zeng B, Ding L, Wang L Chen . Two-sided online micro-task assignment in spatial crowdsourcing. IEEE Transactions on Knowledge and Data Engineering, 2021, 33( 5): 2295–2309
10	M, Asghari C Shahabi . 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	J, Wang Y, Wang D, Zhang L, Wang H, Xiong A, Helal Y, He F Wang . Fine-grained multitask allocation for participatory sensing with a shared budget. IEEE Internet of Things Journal, 2016, 3( 6): 1395–1405
14	L, Wang Z, Yu D, Zhang B Guo . Liu C H. Heterogeneous multi-task assignment in mobile crowdsensing using spatiotemporal correlation. IEEE Transactions on Mobile Computing, 2019, 18( 1): 84–97
15	D, Shi Y, Tong Z, Zhou B, Song W, Lv Q Yang . 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	J, Wang Y, Wang D, Zhang F, Wang H, Xiong C, Chen Q, Lv Z Qiu . Multi-task allocation in mobile crowd sensing with individual task quality assurance. IEEE Transactions on Mobile Computing, 2018, 17( 9): 2101–2113
17	J, Han Z, Zhang X Wu . A real-world-oriented multi-task allocation approach based on multi-agent reinforcement learning in mobile crowd sensing. Information, 2020, 11( 2): 101
18	Y, Ding L, Zhang L Guo . 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	E, Wang Y, Yang J, Wu W, Liu X Wang . An efficient prediction-based user recruitment for mobile crowdsensing. IEEE Transactions on Mobile Computing, 2018, 17( 1): 16–28
20	M H, Cheung F, Hou J, Huang R Southwell . Distributed time-sensitive task selection in mobile crowdsensing. IEEE Transactions on Mobile Computing, 2021, 20( 6): 2172–2185
21	B, Struminskaya V, Toepoel P, Lugtig M, Haan A, Luiten B Schouten . Understanding willingness to share smartphone-sensor data. Public Opinion Quarterly, 2021, 84( 3): 725–759
22	X, Gao H, Huang C, Liu F, Wu G Chen . Quality inference based task assignment in mobile crowdsensing. IEEE Transactions on Knowledge and Data Engineering, 2021, 33( 10): 3410–3423
23	W, Jiang J, Chen X, Liu Y, Liu S Lv . Participant recruitment method aiming at service quality in mobile crowd sensing. Wireless Communications and Mobile Computing, 2021, 2021: 6621659
24	G, Gao H, Huang M, Xiao J, Wu Y E, Sun Y Du . Budgeted unknown worker recruitment for heterogeneous crowdsensing using CMAB. IEEE Transactions on Mobile Computing, 2022, 21( 11): 3895–3911
25	Y, Huang H, Chen G, Ma K, Lin Z, Ni N, Yan Z Wang . 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	G, Sun Y, Wang X, Ding R Hu . Cost-fair task allocation in mobile crowd sensing with probabilistic users. IEEE Transactions on Mobile Computing, 2021, 20( 2): 403–415
28	E, Schubert J, Sander M, Ester H P, Kriegel X Xu . DBSCAN revisited, revisited: why and how you should (still) use DBSCAN. ACM Transactions on Database Systems, 2017, 42( 3): 19
29	M, Piorkowski N, Sarafijanovic-Djukic M Grossglauser . 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	J, Yuan Y, Zheng X, Xie G Sun . 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

[1]

FCS-23133-OF-XL_suppl_1

Download

[1]	Jiantong HUO, Zhisheng HUO, Limin XIAO, Zhenxue HE. Research on performance optimization of virtual data space across WAN[J]. Front. Comput. Sci., 2024, 18(6): 186505-.
[2]	Xinwen GAO, Shaojing FU, Lin LIU, Yuchuan LUO. BVDFed: Byzantine-resilient and verifiable aggregation for differentially private federated learning[J]. Front. Comput. Sci., 2024, 18(5): 185810-.
[3]	Jiaran LI, Richong ZHANG, Samuel MENSAH, Wenyi QIN, Chunming HU. Classification-oriented dawid skene model for transferring intelligence from crowds to machines[J]. Front. Comput. Sci., 2023, 17(5): 175332-.
[4]	Hongyang LI, Xinghua LI, Qingfeng CHENG. A fine-grained privacy protection data aggregation scheme for outsourcing smart grid[J]. Front. Comput. Sci., 2023, 17(3): 173806-.
[5]	Zhusen LIU, Zhenfu CAO, Xiaolei DONG, Xiaopeng ZHAO, Haiyong BAO, Jiachen SHEN. A verifiable privacy-preserving data collection scheme supporting multi-party computation in fog-based smart grid[J]. Front. Comput. Sci., 2022, 16(1): 161810-.
[6]	Zhixin ZENG, Xiaodi WANG, Yining LIU, Liang CHANG. MSDA: multi-subset data aggregation scheme without trusted third party[J]. Front. Comput. Sci., 2022, 16(1): 161808-.
[7]	Kaushal SHAH, Devesh JINWALA. Privacy preserving secure expansive aggregation with malicious node identification in linear wireless sensor networks[J]. Front. Comput. Sci., 2021, 15(6): 156813-.
[8]	Tao HAN, Hailong SUN, Yangqiu SONG, Yili FANG, Xudong LIU. Find truth in the hands of the few: acquiring specific knowledge with crowdsourcing[J]. Front. Comput. Sci., 2021, 15(4): 154315-.
[9]	Jiangfan LI, Chendie YAO, Junxu XIA, Deke GUO. Guaranteeing the response deadline for general aggregation trees[J]. Front. Comput. Sci., 2020, 14(6): 146504-.
[10]	Zhenghui HU, Wenjun WU, Jie LUO, Xin WANG, Boshu LI. Quality assessment in competition-based software crowdsourcing[J]. Front. Comput. Sci., 2020, 14(6): 146207-.
[11]	Liang WANG, Zhiwen YU, Bi GUO, Fei YI, Fei XIONG. Mobile crowd sensing task optimal allocation: a mobility pattern matching perspective[J]. Front. Comput. Sci., 2018, 12(2): 231-244.
[12]	Weiyi LIU,Kun YUE,Hui LIU,Ping ZHANG,Suiye LIU,Qianyi WANG. Associative categorization of frequent patterns based on the probabilistic graphical model[J]. Front. Comput. Sci., 2014, 8(2): 265-278.
[13]	Deying LI, Qinghua ZHU, Jiannong CAO, . Approximation algorithm for constructing data aggregation trees for wireless sensor networks[J]. Front. Comput. Sci., 2009, 3(4): 524-534.

Viewed

Full text

Abstract

Cited

Shared

Discussed