Crowdsensing offers an efficient approach to meet the demand in large scale sensing applications. In crowdsensing, it is of great interest to find the optimal task allocation, which is challenging since sensing tasks with different requirements of quality of sensing are typically associated with specific locations and mobile users are constrained by time budgets. We show that the allocation problem is NP hard. We then focus on approximation algorithms, and devise an efficient local ratio based algorithm (LRBA). Our analysis shows that the approximation ratio of the aggregate rewards obtained by the optimal allocation to those by LRBA is 5. This reveals that LRBA is efficient, since a lower (but not tight) bound on the approximation ratio is 4. We also discuss about how to decide the fair prices of sensing tasks to provide incentives since mobile users tend to decline the tasks with low incentives. We design a pricing mechanism based on bargaining theory, in which the price of each task is determined by the performing cost and market demand (i.e., the number of mobile users who intend to perform the task). Extensive simulation results are provided to demonstrate the advantages of our proposed scheme.

Toward optimal allocation of location dependent tasks in crowdsensing