Research On Incentive Mechanisms For Minimizing Social Cost In Mobile Crowd Sensing

The mobile crowdsensing,which is considered to be one of the most important data collection methods in the era of big data,has attracted the attention of researchers at home and abroad.The mobile crowdsensing is also a hot topic in the research field of computer network.The main idea of the mobile crowdsensing is to make use of the collective wisdom and power to accomplish the tasks that are difficult to be completed or need to be completed for a long time.The mobile crowdsensing is based on the participation of a large scale users.The incentive mechanism in mobile crowdsensing plays an important role in enhancing the enthusiasm of users,ensuring the fairness of transactions and improving the data quality.At the same time,the privacy protection and the data quality in mobile crowdsensing are also worthy of attention.Therefore,it is necessary to design the incentive mechanisms for different application scenarios and targets.In this thesis,the incentive mechanisms are designed to minimize the social cost.We modelled the mobile crowdsensing for different application scenarios.The algorithm based on algorithmic game theory is applied to solve the problem of user selection and payment determination.Two different kinds of incentive mechanisms are designed for time window dependent tasks in mobile crowdsensing.In single time window case,an optimal algorithm based on dynamic programming is designed to select users.While the problem is NP-hard in multiple time window case,the greedy approach based approximate algorithm with polynomial time is designed.Moreover,budget constrained mobile crowdsensing is a novel and practical scenario,where the platform expects to maximize the continuous time interval coverage under budget constraint.In this scenario,two budget feasible frameworks are designed,then we extend the budget feasible framework to a more general scenario where each user can also report multiple time interval tasks.According to the requirement of the data quality and privacy protection for mobile crowdsensing,an incentive mechanism based on both of them is considered.Specifically,in the user selection stage,two kinds of score functions are designed to meet the differential privacy requirements.Through rigid theoretical analysis and extensive simulations,demonstrate that the proposed mechanisms both achieve truthfulness and individual rationality.The incentive mechanisms for time window dependent tasks can minimize the social cost,MST is an optimal algorithm based on dynamic programming for single time window case;while in multiple time window case,MMT is based on greedy approach,which approximates the optimal solution within a factor of In||+1.The incentive maximum continuous time interval coverage under budget constraint can minimize the social cost and satisfy the budget feasibility.The incentive mechanism based on differential privacy can achieve approximate social cost minimization and approximate differential privacy.