4.7 Article

A Truthful Online Mechanism for Location-Aware Tasks in Mobile Crowd Sensing

Journal

IEEE TRANSACTIONS ON MOBILE COMPUTING
Volume 17, Issue 8, Pages 1737-1749

Publisher

IEEE COMPUTER SOC
DOI: 10.1109/TMC.2017.2777481

Keywords

Mobile crowd sensing; mechanism design; approximation algorithms

Funding

  1. NSFC [61628209, 61571335]
  2. Hubei Science Foundation [2016CFA030, CXZD2017000121]
  3. 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

Primary Rating

4.7
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available