TRAC: Truthful auction for location-aware collaborative sensing in mobile crowdsourcing

In this paper, we tackle the problem of stimulating smartphone users to join mobile crowdsourcing applications with smartphones. Different from existing work of mechanism design, we uniquely take into consideration the crucial dimension of location information when assigning sensing tasks to smartphones. However, the location awareness largely increases the theoretical and computational complexity. In this paper, we introduce a reverse auction framework to model the interactions between the platform and the smartphones. We rigorously prove that optimally determining the winning bids is NP hard. In this paper we design a mechanism called TRAC which consists of two main components. The first component is a near-optimal approximate algorithm for determining the winning bids with polynomial-time computation complexity, which 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. The second component is a critical payment scheme which, despite the approximation of determining winning bids, guarantees that submitted bids of smartphones reflect their real costs of performing sensing tasks. Through both rigid theoretical analysis and extensive simulations, we demonstrate that the proposed mechanism achieves truthfulness, individual rationality and high computation efficiency.