Spatial crowdsourcing (SC) plays a vital role in smart cities. Task allocation is a crucial problem in spatial crowdsourcing, which directly determines the quality and efficiency of task completion. Existing research on spatial crowdsourcing task allocation mainly focuses on the heterogeneity of tasks or workers. However, heterogeneous tasks and workers with different privacy preferences coexist in actual SC systems. To solve the problem, a research team led by WEI published their new work on Spatial crowdsourcing in Frontiers of Computer Science co-published by Higher Education Press and Springer Nature.
First, the dual heterogeneous task allocation problem is investigated, and its NP-hardness is also proved. Second, an aggregation-based dual heterogeneous task allocation algorithm is proposed to maximize the quality of task completion while minimizing the total travel distance. Finally, the proposed algorithm is evaluated by extensive experiments. Compared with baseline approaches, the proposed algorithm achieves more task completion quality and less average travel distance.
The research analyzes multiple heterogeneous characteristics of tasks and workers in a real spatial crowdsourcing environment. The coexistence of heterogeneous tasks and workers causes a considerable increase in the search space for task assignment solutions. In order to solve this problem, they proposed an aggregation-based dual heterogeneous task allocation algorithm to improve task completion quality and reduce workers' travel distance.
Firstly, they aggregate tasks that are close in location and have similar sensing requirements into task groups. In the same group, task share budgets to reduce task failures due to insufficient budget. Then, a path-planning approach is developed to reduce the travel distances and costs of workers in a community. Finally, two task allocation schemes based on linear weighting and profit of distance are proposed, respectively. Experimental results show that the proposed schemes achieve greater task completion quality and lower average travel distance compared with the baseline methods. What’s more, their performance advantages become more significant as the number of tasks (workers) increases.
DOI: 10.1007/s11704-023-3133-6