Research On Spatial Crowdsourcing Task Assignment Algorithm

Spatial crowdsourcing consists of requester,worker and platform.Good task allocation algorithms can take into account the interests of workers,task requesters and the platform to achieve the global optimal goal.The biggest difficulty of task allocation lies in the dynamic nature of spatial crowdsourcing.Generally,in the spatial crowdsourcing platform,the emergence and end of spatial tasks are dynamic and random.Workers are free to join or leave crowdsourcing activities.There is no information about new tasks and workers in the task distribution server.How to optimize the quantity and quality of task allocation in the context of dynamic spatial crowdsourcing is still a problem to be solved.This thesis accomplishes the following work in terms of task allocation:Firstly,to solve the problem of idealization of space crowdsourcing models,this thesis puts forward a reasonable worker and task model based on the application background.Add type attributes for workers and tasks,and assign different scores according to whether the types match,and then model them as an optimization problem with the goal of maximizing the total score of task assignment,constrained by the time and space of workers and tasks.It is also proposed to use batch processing mode for task allocation,and convert the maximum score problem into a bipartite graph matching problem for optimization in each time slice.Secondly,to solve the problem of only local optimization when task allocation is performed in batch mode,this thesis proposes a task allocation algorithm based on prediction,that is,in the allocation process of the current time slice,the task distribution of each future time slice is firstly predicted through historical data,and then follow the guidance of the prediction results to make the workers appear in the areas where the tasks are distributed as much as possible,thereby improving the effect of task assignment.Thirdly,due to the deceptive behavior of workers,there is a probability of failure in task completion.This thesis proposes reliability to measure the probability of task completion.The definition of reliability includes worker credibility,task type,and worker skill matching.Worker credibility is determined by the initial credibility and completion of the task,and the task completion record of the worker is dynamically updated;at the same time,reliability is affected by the task type and worker skills.When the worker skills and task types are consistent Time,reliability will increase.Furthermore,a task assignment algorithm based on reliability is proposed to increase the priority of task assignment with high reliability,reduce the probability of task completion failure,and improve the quantity and quality of task completion.Finally,using real data sets to evaluate the performance of the proposed algorithm,this thesis compares with other algorithms to verify the effectiveness of the proposed algorithm in improving the task allocation effect.