Research On Quality And Budget-aware Task Assignments For Spatial Crowdsourcing

With the rapid development of wireless network communication technologies(e.g.,4G)and the increasingly ubiquity of mobile devices(e.g.smart phones,tablet PCs,PDAs),various spatial crowdsourcing platforms have been appeared and widely used in our daily lives,such as Uber,Didi Taxi,CrowdFlower,Gigwalk,Gimission,Foursquare.Also,spatial crowdsourcing has attracted much attention and become a new research hotspot in academic communication,and put forward many challenging problems in theory and engineering.In spatial crowdsourcing,task publishers and mobile workers are the main participants.Each worker has his/her own location,trajectory.Each spatial task is associated with the time,location attributes and always required to be complete by more than one worker.In the crowdsourcing mode,the workers should make a decision voluntarily on whether to perform the tasks which assigned to them or not,according to their own interests,wills rather than mandatory.The task publishers always focus on the number of workers who complete the task,the quality of task result,the reward paid to the workers,etc.The factors that affect the worker's decision are more complex,such as traffic routes and costs(time,energy,money,etc),reward,interest and so on.Therefore,task assignment problem has become a core issue in spatial crowdsourcing for both task publishers and workers.However,the complex and variable spatio-temporal factors,such as the timeliness and position distribution of the tasks,the mobility and the itinerary route of workers make it to be a challenging problem.Most researches aim to study the task assignment problem under the single constraint,such as the number of workers,the quality of task result,and the total budget.Very few researchers work on the task assignment problem under the multiple constraints.Based on the requirements of the task publisher and the workers,this paper focuses on the task assignment problem in spatial crowdsourcing.The main work and contributions of this paper are listed as follows:1.A model of task assignment in spatial crowdsourcing is proposed.On this basis,this paper proposes a task assignment problem under multiple constraints for task publishers and a task assignment problem for mobile workers.2.For the task assignment problem of task publishers,two algorithms are proposed to maximize the task assignment quality(the probability that task is completed by a certain number of workers)and minimize the budget,respectively.The task allocation scheme calculated by these two algorithms can satisfy the constraints,such as the number of workers to complete the task,the quality and budget of the task allocation.But also,the former can ensure the task publisher obtain the highest-quality task result while the latter can guarantee the task publisher obtain the task results with as little budget as possible.3.For the task assignment problem of workers,a branch and bound algorithm and two approximate algorithms are proposed to maximize the sum reward of workers.Based on the worker's current position,the algorithms aim to assign a travel route for the worker to perform the tasks.If the worker performs the tasks according to the route,he/she can not only successfully complete the tasks on time,but also obtains as much reward as possible.4.This paper uses the real data collected from a geographically-based check-in site which is called Gowalla,as the experimental data set and compares the efficiency and effectiveness of algorithms.Experimental results show that the proposed algorithms have achieved good operating efficiency and experimental results.