Deadline-sensitive User Recruitment for mobile crowdsensing with probabilistic collaboration

摘要

Mobile crowdsensing is a new paradigm in which a group of mobile users exploit their smart devices to cooperatively perform a large-scale sensing job over urban environments. In this paper, we focus on the Deadline-sensitive User Recruitment (DUR) problem for probabilistically collaborative mobile crowdsensing. Unlike previous works, mobile users in this problem perform sensing tasks with probabilities, and multiple users might be recruited to cooperatively perform a common task, ensuring that the expected completion time is no larger than a deadline. Owing to such a probabilistic collaboration, DUR can be formalized as a non-trivial set cover problem with non-linear programming constraints and an optimization objective of real function. We first prove that the DUR problem is NP-hard. Then, we propose a greedy DUR algorithm, called gDUR, to solve this problem. Next, we prove that the gDUR algorithm can achieve a logarithmic approximation ratio. Furthermore, we extend the problem to a more complex case where sensing duration is taken into consideration, and we propose a sensing-duration-aware user recruitment algorithm, called dDUR. Finally, we validate the performance of the proposed algorithms through extensive simulations, based on a real mobile social network trace and a synthetic trace.