Research On Task Assignment Algorithms And Incentive Mechanisms For Crowd Sensing Systems

With the widespread adoption of mobile devices with built-in high-performance sensors,the emerging crowd sensing technique has gradually become an effective way to sense,collect and share information in real time.Different from the traditional static sensor network,crowd sensing without the need to deploy a large number of sensor nodes.It takes mobile devices carried by ordinary users as basic sensing unit,and sensing the surrounding environment information at any time and anywhere to realize the sensing tasks distribution and sensing data collection.It is the embodiment of crowdsourcing in the field of mobile data sensing.The task assignment and incentive mechanism is the key issue in the researches of crowd sensing.The task assignment is to select the appropriate sensing users to execute tasks under certain constraints to achieve some optimization goals.And the incentive mechanism is to encourage users actively participate in sensing tasks by reasonable incentive measures to solve the problem of lack of user participation.In this dissertation,the task assignment problem of minimizing sensing cost and the design problem of reward incentive mechanism based on auction are studied.At the same time,combing with the research results,a campus information sharing application based on crowd sensing is developed.Accordingly,the main research work of this dissertation is as follows:(1)In the case of symmetric user information,the task assignment problem of minimizing sensing cost is studied.This problem aims at the shortcomings of the existing researches,and adds the task execution order and the task execution cost to calculate the sensing cost,the optimization goal of minimizing sensing cost can be achieved under the condition that the user can be assigned more than one task.The complexity analysis shows that the problem belongs to the NP-hard problem and can not be solved in polynomial time.For this reason,greedy algorithm,simple geneticalgorithm,partheno-genetic algorithm and improved ant colony algorithm are used to obtain the suboptimal solution respectively.The simulation results show that the above four algorithms have their own characteristics in the performance of sensing cost and running time,and can be reasonably selected according to the specific requirements in practical applications.(2)In the case of asymmetric user information,combing with auction theory,the reward incentive mechanism is designed to solve the problems of high cost of single-task auction,false user quotation and limited platform budget in the existing researches.The incentive mechanism is based on reverse and combinatorial auction.Firstly,the effective bidding task group and its Bidding price are obtained based on the user sensing range and preprocessing mechanism.Secondly,determining the winning user and its reward by using the second price auction mechanism and corresponding constraints in the decision-making scheme.Finally,the theoretical and simulation results show that the incentive mechanism is incentive compatibility,individual rationality,budget feasibility,calculate effectiveness,and it has better performance.(3)In order to realize the real-time sharing of campus information,combining the research results of the aforementioned task assignment algorithm and incentive mechanism,a Android-based campus information sharing platform is developed.The core module of the platform is algorithm implementation module.On the one hand,the platform can select the appropriate users to complete the corresponding news tasks through the task assignment module,on the other hand,we can determine the winning users and its integral reward through the incentive mechanism module in the auction users.The theoretical research results of this dissertation can provide valuable reference for the related researches of crowd sensing.At the same time,the campus application which combines the theory achievement development also has certain realistic significance.