The Performance Optimization Of Task Assignment In Spatial Crowdsourcing

Recently,with the rapid development of mobile networks and dramatic proliferation of advanced mobile devices,Spatial Crowdsourcing(SC)has emerged as an effective paradigm for performing tasks in the real-world.Task assignment is the fundamental challenge in spatial crowdsourcing.An efficient task assignment scheme is crucial for emerging spatial crowdsourcing applications,as it can improve the efficiency of systems by increasing rewards of workers and saving cost of systems.Existing works,due to its complexity,often use heuristics of various kinds to solve task assignment problems.However,these schemes usually only apply some special cases,once the environment changes,the efficiency of algorithms is significantly reduced.Further,to improve the Quality of Service(QoS)in spatial crowdsourcing systems,existing works usually adopt many-to-one strategy – assigning multiple workers as a team for each published task.However,such an allocation scheme fails to consider team characteristics which can strongly affect the QoS for some experience-sensitive collaborative tasks.In this thesis,firstly,we present taxonomy of task assignment considering both task matching and task scheduling in spatial crowdsourcing systems.Secondly,we devise an approximation algorithm for task assignment problem in spatial crowdsourcing and get an efficient solution through some combinatorial optimization methods.We define an important problem,namely,Bounded and Heterogeneous Task Assignment(BHTA),such that the sum of rewards of workers is maximized subject to multiple constraints.We study the hardness of problem and prove that the BHTA problem is NP-hard.Subsequently,we propose a constant-ratio approximation algorithm based on Partition and Shifting(PS)method to achieve the assignment solution.To meet with the workers‘dynamism,we further design a greedy algorithm and provide its theoretical guarantee.Experiments on both synthetic and real datasets demonstrate the efficiency of our proposed method over previous developed methods.Thirdly,for the improvement of QoS in spatial crowdsourcing systems,we jointly consider two team characteristics: Diversity,which is the union of experiences within a team,and Affinity,which is how efficiently team members collaborate with each other.Inspired by these two team characteristics,we study an important problem,namely,Affinity Diversity-Aware Spatial Crowdsourcing(ADA-SC),which aims to find an allocation scheme,such that each team satisfies the affinity requirement of the corresponding task and maximizes the team diversity under budget and spatial constraints.Since the ADA-SC problem is proven to be NP-hard by reduction from the set cover problem with non-linear constraints,we propose two sub-modular approximation algorithms with pruning strategies for two single-task scenarios.Then a greedy-based algorithm is designed for the multi-task scenario.Experiments on both real and synthetic datasets verify the efficiency and effectiveness of our proposed methods.To the best of author's knowledge,this study is the first attempt to give a taxonomy of task assignment in focusing task matching,task scheduling and a combination of both task matching and task scheduling;a constant-ratio approximation solution for the defined task assignment problem;and consideration of team characteristics of diversity and affinity for the defined task assignment problem to improve the QoS in spatial crowdsourcing systems.