Aggregation-based dual heterogeneous task allocation in spatial crowdsourcing

doi:10.1007/s11704-023-3133-6

Frontiers of Computer Science

2024, Vol. 18

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

本期目录

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

全文: PDF(13642 KB) HTML

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.

Key words： task allocation aggregation shortest path dual heterogeneous spatial crowdsourcing

收稿日期: 2023-02-19 出版日期: 2023-09-27

Corresponding Author(s): Kaimin WEI

引用本文:

. [J]. Frontiers of Computer Science, 2024, 18(6): 186605.
Xiaochuan LIN, Kaimin WEI, Zhetao LI, Jinpeng CHEN, Tingrui PEI. Aggregation-based dual heterogeneous task allocation in spatial crowdsourcing. Front. Comput. Sci., 2024, 18(6): 186605.

链接本文:

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

Fig.1

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

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

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

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

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

Fig.2

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

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

Fig.3

Fig.4

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

Viewed

Full text

Abstract

Cited

Shared

Discussed