The Research Of Relevant Theory And Techniques For Spatial Crowdsourcing

The proliferation of GPS-enabled smart devices and increased availability of wireless network have enabled people to move as sensors and participate various location-based tasks.Spatial Crowdsourcing(SC)is a recently proposed concept and framework.One of the main research problems in SC is task assignment,in which the SC server assigns the suit-able tasks to workers in order to guarantee these tasks can be completed without violating the spatio-temporal constraints of workers and tasks.However,due to the spatio-temporal constraints and randomness of workers and tasks,there are many deficiencies in task as-signment.Firstly,an important goal of task assignment is to maximize the total number of assigned tasks,which is proved to be NP hard.In practice,however,there are a large number of workers and tasks to be assigned,which means using inefficient task assignment algorithms will lead to the incompletion of tasks.The reason behind it is that workers tend to quit the assigned tasks when they have to wait a long time for assignment.Secondly,the uncertainty of workers in SC systems cannot provide the quality guarantee of task results.In other words,some workers may give the false or fake preferences,and further submit the unsatisfying task results to SC platforms.Thirdly,the travel cost is a critical factor in SC since workers must physically go to the designated locations in order to perform the assigned tasks on SC platforms.Meanwhile,the travel cost of a worker is closely associ-ated with her reward(obtained by accomplishing the tasks),which affects the acceptance of tasks and quality of task completion.Fourthly,ignorance of the spatio-temporal con-straints and dynamic spatio-temporal distributions of workers and tasks in SC can often lead to poor assignment results and affect user experience.Finally,there inevitably exist some SC applications,in which an individual worker may not efficiently conduct a task by her-self.Therefore,the workers have to form a stable group or a coalition to jointly complete the tasks that exceed the capabilities of individual workers,which is a huge challenge.This thesis deeply studies on the above problems in SC and obtains the following re-search results.1)This thesis proposes an exact and efficient task assignment algorithm by utilizing the tree-decomposition technique to isolate the dependency among workers,and organize them into a balanced tree structure,such that the workers in sibling nodes of the tree do not share the same valid tasks.The tree can be traversed in a depth-first manner to find the optimal assignment.This algorithm is applied in the destination-based task assignment scenario,where its practicability is demonstrated.2)This thesis takes an important step toward effective task assignment in SC based on workers’ temporal preferences.To be specific,the tensor decomposition method is proposed to model workers’ temporal preferences for different task categories based on the historical task-performing data of workers,and then several task assignment strategies are developed to achieve the optimal task assignment by taking workers’ preferences into consideration.Extensive empirical study demonstrates our proposed methods can significantly improve the effectiveness of task assignment.3)A novel spatial crowdsourcing problem is studied,namely Predictive Task Assign-ment(PTA),which aims to maximize the number of assigned tasks by taking into account both current and future workers/tasks that enter the system dynamically with location un-known in advance.This thesis proposes a two-phase data-driven framework.The prediction phase hybrids different learning models to predict the spatio-temporal distributions of fu-ture workers and tasks.In the assignment component,both greedy algorithm for large-scale applications and optimal algorithm with a graph partition based technique are designed.4)This thesis proposes a novel spatial crowdsourcing problem,called Coalition-based Task Assignment(CTA),where the spatial tasks may require more than one worker(form-ing a coalition)to complete in order to maximize the overall rewards of workers.To tackle the CTA problem,this thesis designs both contract-based greedy method and equilibrium-based method to efficiently and effectively assign tasks.In particular,the contract-based method aims to form a set of worker coalitions greedily to perform the tasks by formu-lating a contract,with which workers leaving coalitions will be punished.Moreover,an equilibrium-based algorithm is proposed,which uses the best-response strategy to reach a Nash equilibrium(i.e.,a suitable task assignment)by converting the CTA problem into an exact potential game.Meanwhile,the simulated annealing scheme is adopted to find a better Nash equilibrium.