Journal
IEEE TRANSACTIONS ON MOBILE COMPUTING
Volume 16, Issue 10, Pages 2764-2777Publisher
IEEE COMPUTER SOC
DOI: 10.1109/TMC.2017.2653774
Keywords
Mobile crowdsourcing; incentive mechanism; randomized auction; diversity; quality; truthfulness; rational; social cost
Funding
- 973 Program [2014CB340303]
- 863 Program [2015AA015303]
- NSFC [61472254, 61170238, 61420106010]
- STCSM [14511107500, 15DZ1100305]
- Research Grant for Young Faculty in Shenzhen Polytechnic [601522K30015]
- SZSTI [JCYJ20160407160609492]
- Singapore NRF (CREATE E2S2)
- Program for New Century Excellent Talents in University of China
- Program for Changjiang Young Scholars in University of China
- Program for Shanghai Top Young Talents
Ask authors/readers for more resources
Crowdsourcing to mobile users has emerged as a compelling paradigm for collecting sensing data over a vast area for various monitoring applications. It is of paramount importance for such crowdsourcing paradigm to provide effective incentive mechanisms. State-of-the-art auction mechanisms for crowdsourcing to mobile users are typically deterministic in the sense that for a given sensing job from a crowdsourcer, only a small set of smartphones are selected to perform sensing tasks and the rest are not selected. One apparent disadvantage of such deterministic auction mechanisms is that the diversity with respect to the sensing job is reduced. As a consequence, the quality of the collected sensing data is also decreased. This is due to failure to exploit the intrinsic advantage of the large set of diverse mobile users in a mobile crowdsourcing network. In this paper, we propose a randomized combinatorial auction mechanism for the social cost minimization problem, which is proven to be NP-hard. We design an approximate task allocation algorithm that is near optimal with polynomial-time complexity and use it as a building block to construct the whole randomized auction mechanism. Compared with deterministic auction mechanisms, the proposed randomized auction mechanism increases the diversity in contributing users for a given sensing job. We carry out both solid theoretical analysis and extensive numerical studies and show that our randomized auction mechanism achieves approximate truthfulness, individual rationality, and high computational efficiency.
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