Journal
IEEE TRANSACTIONS ON MOBILE COMPUTING
Volume 17, Issue 8, Pages 1737-1749Publisher
IEEE COMPUTER SOC
DOI: 10.1109/TMC.2017.2777481
Keywords
Mobile crowd sensing; mechanism design; approximation algorithms
Funding
- NSFC [61628209, 61571335]
- Hubei Science Foundation [2016CFA030, CXZD2017000121]
- Research Grants Council of Hong Kong [17204715, 17225516, C7036-15G]
Ask authors/readers for more resources
Effective incentive mechanisms are invaluable in mobile crowd sensing, for stimulating participation of smartphone users. Online auction mechanisms represent a natural solution for such sensing task allocation. Departing from existing studies that focus on an isolated system round, we optimize social cost across the system lifespan, while considering location constraints and capacity constraints when assigning sensing tasks to users. The winner determination problem (WDP) at each round is NP-hard even without inter-round coupling imposed by user capacity constraints. We first propose a truthful one-round auction, comprising of an approximation algorithm for solving the one-round WDP and a payment scheme for computing remuneration to winners. We then propose an online algorithm framework that employs the one-round auction as a building block towards a flexible mechanism that makes on-spot decisions upon dynamically arriving bids. Through both theoretical analysis and trace-driven simulations, we demonstrate that our online auction is truthful, individually rational, computationally efficient, and achieves a good competitive ratio.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available