Truthful incentive mechanisms for mobile crowd sensing with dynamic smartphones

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 bee...

Full description

Saved in:
Bibliographic Details
Published in:Computer networks (Amsterdam, Netherlands : 1999) Netherlands : 1999), 2018-08, Vol.141, p.1-16
Main Authors: Cai, Hui, Zhu, Yanmin, Feng, Zhenni, Zhu, Hongzi, Yu, Jiadi, Cao, Jian
Format: Article
Language:English
Subjects:
Algorithms
Computational mathematics
Computer simulation
Computing time
Credibility
Data acquisition
Detection
Electronic devices
Incentives
Optimization
Smartphones
Task complexity
Ubiquitous computing
User behavior
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 12-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−1e). Rigorous theoretical analysis and extensive simulations have been performed, and the results demonstrate our proposed auction mechanisms achieve truthfulness, individual rationality and computational efficiency.
ISSN:1389-1286
1872-7069
DOI:10.1016/j.comnet.2018.05.016