期刊
IEEE TRANSACTIONS ON MOBILE COMPUTING
卷 17, 期 8, 页码 1737-1749出版社
IEEE COMPUTER SOC
DOI: 10.1109/TMC.2017.2777481
关键词
Mobile crowd sensing; mechanism design; approximation algorithms
资金
- NSFC [61628209, 61571335]
- Hubei Science Foundation [2016CFA030, CXZD2017000121]
- Research Grants Council of Hong Kong [17204715, 17225516, C7036-15G]
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据