Location-Based Online Task Assignment and Path Planning for Mobile Crowdsensing

摘要

Mobile crowdsensing has been a promising and cost-effective sensing paradigm for the Internet of Things by exploiting the proliferation and prevalence of sensor-rich mobile devices held/worn by mobile users. In this paper, we study the task assignment and path planning problem in mobile crowdsensing, which aims to maximize total task quality under constraints of user travel distance budgets. We first formulate the problem mathematically when all task and user arrival information is known a priori and prove it to be NP-hard. Then, we focus on studying the scenarios where users and tasks arrive dynamically and accordingly design four online task assignment algorithms, including quality/progress-based algorithm (QPA), task-density-based algorithm (TDA), travel-distance-balance-based algorithm (DBA), and bio-inspired travel-distance-balance-based algorithm (B-DBA). All the four algorithms work online for task assignment upon arrival of a new user. The former three algorithms work in a greedy manner for assigning tasks, one task each time, where the QPA prefers the task leading to largest ratio of task quality increment to travel cost, the TDA tends to guide user to high-task-density areas, and the DBA further considers travel distance balance information. The last algorithm B-DBA integrates the travel-distance-balance-aware metric in the DBA and bio-inspired search for further improved task assignment performance. Complexities of the proposed algorithms are deduced. Simulation results validate the effectiveness of our algorithms; B-DBA has the best performance among the four algorithms in terms of task quality, and furthermore, it outperforms existing work in this area.