Theory And Technology Of Task Assignment For Spatial Crowdsourcing System

With the rapid development of mobile Internet and the increasing popularity of smart mobile devices,Spatial Crowdsourcing(SC),as a new computing model,shows great potential in the fields of smart cities and sharing economy.Among the technologies contained in SC,task assignment is the core issue,and incentive mechanism is the premise and guarantee of task assignment,and these two technologies are often closely combined in research.Although these two technologies have been widely studied,they still face the following challenges due to the randomness and spatial attribute of workers and tasks.Firstly,workers in SC have uncertain properties.On the one hand,the number of participants is uncertain.Due to the spatial attribute,it costs workers to move from their current locations to the designated locations of tasks,which is related to the benefits and interests of workers.Therefore,the number of workers that can be attracted by different tasks is uncertain.On the other hand,the quality of tasks completed by workers is uncertain,that is,the preferences and skill proficiency of different workers directly lead to different task completion quality.Secondly,the various attributes of tasks in SC lead to multiple constraints.When assigning tasks,it needs to consider the constraints of time,location,cost,effective range,dependencies,and multi-skills.Ignoring these constraints will affect the task completion rate.Finally,a single SC platform can not deal with the aggregation effect and randomness of tasks.For a single SC platform,the number of online workers is limited.When task aggregation occurs,the number of tasks in the peak period increases several times or even dozens of times,making the platform unable to respond to all tasks.In addition,the randomness of tasks leads to the uneven distribution of workers and tasks,resulting in the serious imbalance of the supply-demand ratio of workers and tasks in different regions.To solve the above challenges,the main research of this paper is as follows.(1)For the uncertainty of workers in SC,this paper proposes an incentive mechanism for data collection tasks in SC.The designed incentive mechanism draws on Stackelberg-game theory and auction mechanism.Specifically,in each round of bidding,workers develop strategies to maximize their benefits.Then,according to the strategies of workers,the SC platform selects the workers who can maximize the platform’s benefit to continue the next round of bidding.Based on convex optimization theory,it can be proved that the incentive mechanism can reach stability after multiple rounds of bidding.The proposed incentive mechanism considers the spatial attribute of workers and tasks,as well as the differences in the quality of tasks completed by workers.In addition,it also takes into account the benefits of platforms and workers,and can ensure the number of participants.Moreover,the incentive mechanism meets the characteristics of sincerity,credibility,individual rationality,profitability,and computational efficiency required by an auction mechanism.(2)Considering the multi-attributes of tasks,this paper proposes a problem of multi-stage complex task assignment in SC,and designs effective task assignment algorithms,which can assign tasks to workers to maximize the overall benefits under the constraints of dependencies,multi-skills,effective range,budget,and time.Firstly,it is proved that the problem is NP-hard.Secondly,based on the mode of platform-assigned tasks,a greedy algorithm is proposed to obtain approximate assignment results quickly,and the property of the submodular function is used to prove the boundary value of the result obtained by the greedy algorithm.Finally,based on the mode of worker-selected tasks,a game algorithm is designed,and it is proved that the algorithm can reach Nash equilibrium by applying potential game theory.(3)To solve the problems of a single platform in coping with tasks aggregation and randomness,this paper proposes a solution based on platforms aggregation(PA),studies the problem of online assignment of heterogeneous tasks,and designs task assignment algorithms based on balanced search tree structure.Specifically,due to the limited number of online workers in a single platform,the random occurrence of tasks leads to the uneven distribution of workers and tasks,which affects the task completion rate.In addition,in practical applications,tasks are heterogeneous,which can be divided into real-time processing tasks and reservation processing tasks,and the online response to heterogeneous tasks puts the platform in a more severe test.Therefore,a solution framework based on PA is proposed,in which the order platform can aggregate other platforms and hire workers to deal with tasks.Based on PA,a problem of online assignment of heterogeneous tasks is studied,aiming at assigning heterogeneous tasks in real-time to maximize the benefits of the order platform.To solve this problem,a tree-based greedy search algorithm(TGS)and a threshold-based TGS algorithm(TTGS)are designed by applying balanced search tree structure,and the complexity and competition ratio of the algorithms are also analyzed.