Author_Institution :
Sch. of Comput. Sci. & Technol., Nanjing Univ. of Posts & Telecommun., Nanjing, China
Abstract :
Mobile crowdsensing can enable numerous attractive novel sensing applications due to the prominent advantages such as wide spatiotemporal coverage, low cost, good scalability, pervasive application scenarios, etc. In mobile crowdsensing applications, incentive mechanisms are necessary to stimulate more potential smartphone users and to achieve good service quality. In this paper, we focus on exploring truthful incentive mechanisms for a novel and practical scenario where the tasks are time window dependent, and the platform has strong requirement of data integrity. We present a universal system model for this scenario based on reverse auction framework and formulate the problem as the Social Optimization User Selection (SOUS) problem. We design two incentive mechanisms, MST and MMT. In single time window case, we design an optimal algorithm based on dynamic programming to select users. Then we determine the payment for each user by VCG auction; while in multiple time window case, we show the general SOUS problem is NP-hard, and we design MMT based on greedy approach, which approximates the optimal solution within a factor of In|W| + 1, where |W| is the length of sensing time window defined by the platform. Through both rigorous theoretical analysis and extensive simulations, we demonstrate that the proposed mechanisms achieve high computation efficiency, individual rationality and truthfulness.
Keywords :
computational complexity; data integrity; dynamic programming; incentive schemes; mobile commerce; smart phones; MMT; MST; NP hard problem; SOUS problem; VCG auction; approximation ratio; data integrity; dynamic programming; incentive mechanism; mobile crowdsensing; optimal algorithm; reverse auction; smartphone user simulation; social optimization user selection; time window dependent task analysis; universal system model; Approximation methods; Dynamic programming; Heuristic algorithms; Mobile communication; Noise level; Sensors; Wireless communication; Mobile crowdsensing; approximation ratio; auction; incentive mechanism; mobile crowdsensing; optimal algorithm; strategic behavior;