The emergence of ubiquitous mobile devices has given rise to mobile crowd sensing, as a new data collection paradigm to potentially produce enormous economic value. Fully aware of the paramount importance to incentivize smartphone users' participation, a wide variety of incentive mechanisms have been proposed, however, most of which have made the impractical assumption that smartphones remain static in the system and sensing tasks are known in advance. Designing truthful incentive mechanisms for mobile crowd sensing system has to address four major challenges, i.e., dynamic smartphones, uncertain arrivals of tasks, strategic behaviors, and private information of smartphones. To jointly address these four challenges, we propose two truthful auction mechanisms, OT-OFMCS and NOT-ONMCS, with respect to the offline and online case of mobile crowd sensing, aiming at selecting an optimal set of winning bids with low costs for maximizing the social welfare. The OT-OFMCS mechanism features an optimal task allocation algorithm with the polynomial-time computational complexity where the information of all smartphones and tasks are known a priori. The NOT-ONMCS mechanism is comprised of a critical payment scheme and an online allocation algorithm with a 1/2-competitive ratio, where the real-time allocation decisions are made based on current active smartphones. To improve the theoretical competitive ratio, we investigate a modified online approximation algorithm RWBD with the ratio of (1 - 1/e). Rigorous theoretical analysis and extensive simulations have been performed, and the results demonstrate our proposed auction mechanisms achieve truthfulness, individual rationality and computational efficiency. (C) 2018 Elsevier B.V. All rights reserved.
