Minimum Cost Task Assignment for Vehicle-Based Crowdsensing with Deterministic and Nondeterministic Trajectory
Meimei Tu, Peng Li, Tao Zhang, Qiang Zhou, Qin Liu · 2019
Vehicle-based crowdsensing (VCS) is a special case in crowdsourcing, and task assignment is a basic and important problem. In this paper, we investigate the minimum cost task assignment (MCTA) problem for vehicle-based crowdsensing. The VCS platform hopes to recruit some vehicles to complete given spatial-temporal tasks with the minimum cost. As vehicle trajectories are dynamic, we divide the MCTA problem into two sub-problems, the deterministic trajectory (D-MCTA) problem, and nondeterministic trajectory (N-MCTA) problem. For D-MCTA problem, we prove that the D-MCTA problem is NP-hard, and we propose a greedy algorithm to solve this problem. For N-MCTA problem, firstly, we determine the probability of each vehicle's trajectory through the logistic regression method. Then, we exploit the semi-Markov method to calculate the probability of each vehicle executing the task. Moreover, a greedy algorithm is proposed and the theoretical analysis is given. Finally, extensive simulations have been conducted to show the performance of our proposed algorithms is superior to the other algorithms.