A truthful incentive mechanism for mobile crowd sensing with location-Sensitive weighted tasks

Mobile crowd sensing has emerged as an appealing paradigm to provide sensing data for its efficient economy. A large number of incentive mechanisms has been proposed for stimulating smartphone users to participate in mobile crowd sensing applications. Different from existing work, in addition to sensing tasks with diverse weights, we uniquely take into consideration the crucial dimension of location information when performing sensing tasks allocation. However, the location-sensitive weighted tasks are more vulnerable to the real life where each sensing task has the evident distinction. Meanwhile, the location sensitiveness leads to the increase of theoretical and computational complexity. In this paper, we investigate a truthful incentive mechanism which consists of two main components, winning bids determination algorithm and critical payment scheme. Since optimally determining the winning bids is NP hard, a near-optimal algorithm with polynomial-time computation complexity is proposed, which further approximates the optimal solution within a factor of 1+ln(n), where n is the maximum number of sensing tasks that a smartphone can accommodate. To guarantee the truthfulness, a critical payment scheme is proposed to induce smartphones to disclose their real costs. Through both rigid theoretical analysis and extensive simulations, we demonstrate that the proposed mechanism achieves truthfulness, individual rationality and high computation efficiency.