Incentive Mechanisms for Time Window Dependent Tasks in Mobile Crowdsensing

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 broken vertical bar W broken vertical bar + 1, where broken vertical bar W broken vertical bar 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.