A Budget Feasible Incentive Mechanism for Weighted Coverage Maximization in Mobile Crowdsensing

摘要

Mobile crowdsensing is a novel paradigm to collect sensing data and extract useful information about regions of interest. It widely employs incentive mechanisms to recruit a number of mobile users to fulfill coverage requirement in the interested regions. In practice, sensing service providers face a pressing optimization problem: How to maximize the valuation of the covered interested regions under a limited budget? However, the relation between two important factors, i.e., Coverage Maximization and Budget Feasibility, has not been fully studied in existing incentive mechanisms for mobile crowdsensing. Furthermore, the existing approaches on coverage maximization in sensor networks can work, when mobile users are rational and selfish. In this paper, we present the first in-depth study on the coverage problem for incentive-compatible mobile crowdsensing, and propose BEACON, which is a Budget fEAsible and strategy-proof incentive mechanism for weighted COverage maximizatioN in mobile crowdsensing. BEACON employs a novel monotonic and computationally tractable approximation algorithm for sensing task allocation, and adopts a newly designed proportional share rule based compensation determination scheme to guarantee strategy-proofness and budget feasibility. Our theoretical analysis shows that BEACON can achieve strategy-proofness, budget feasibility, and a constant-factor approximation. We deploy a noise map crowdsensing system to capture the noise level in a selected campus, and evaluate the system performance of BEACON on the collected sensory data. Our evaluation results demonstrate the efficacy of BEACON.