Location-based Online Task Scheduling in Mobile Crowdsensing

Smart devices with a rich set of low-cost sensors enable a new sensing paradigm called mobile crowdsensing. In mobile crowdsensing, tasks are distributed at a variety of locations. Mobile users travel through different task locations to perform different tasks. The diversity of task locations and user trajectories makes the optimal scheduling problem intractable. In this paper, we mathematically formulate the optimal task scheduling problem as a continuous path planning problem, which is known to be NP-hard. Then we propose two online heuristic algorithms to maximize the task quality improvement for each newly arriving user. These algorithms work in a hop by hop manner for task selection and adopt different measures and strategies including: (1) ratio of task quality increment and travel cost and (2) task spatial density. We present detailed algorithm design and deduce their computational complexity. Extensive simulation results show that our algorithms outperform existing work.