Study On The Efficiency And Quality Of Time-continuous Spatial Crowdsourcing Tasks

With the widely use of smart mobile devices,a new form of crowdsourcing,spa-tial crowdsourcing,occurs.Spatial crowdsourcing requires workers to physically go to the specified locations to complete tasks.In this work,we put forward a new type of spatial crowdsourcing,called time-continuous spatial crowdsourcing(TCSC in short).The difference between TCSC and the previous spatial crowdsourcing is TCSC tasks need long time to finish.TCSC supports broad applications in the real life,including environmental monitoring,traffic surveillance and so on.However,due to limited budgets and limited availability of workers in practice,TCSC tasks can not be finished in all task duration.Thus,the data collected is often incomplete,incurring data deficiency problem.To tackle that,in this work,we use interpolation to estimate the missing values,which may further affects the data preci-sion problem.Therefore,in TCSC's applications,quality is an essential task measure.Based on that,the dissertation proposes an entropy-based quality metric,and investi-gates quality-aware task assignment methods for both single-and multi-task scenarios,whose content is as follows:(1)The dissertation proposes the novel TCSC problem and related definitions,and puts forward the TCSC task quality function,and studies the task assignment algorithms with aim of optimizing the task quality.(2)In the single task assignment scenarios,the dissertation proposes single-task quality maximization problem,and analyses the time complexity of the problem.Next,the dissertation proves that the problem is NP-hard,and designs polynomial-time al-gorithms with guaranteed approximation ratios.At the same time,in order to improve the efficiency of the algorithm,the dissertation also puts forward a set of optimization strategies.(3)In the multiple task assignment scenarios,the dissertation puts forward multiple-task summation quality maximization problem and multiple-task minimum quality maximization problem.In the multiple-task summation quality maximization problem,the dissertation finds the correlations among tasks,and proposes the parallel framework for speeding up the optimization process.In the multiple-task minimum quality maximization problem,the dissertation uses the heuristic algorithm to complete the task assignment.(4)Based on the real and synthetic data sets,the dissertation shows the effect of dif-ferent parameters on the algorithms through the experimental analysis.For the single-task quality maximization problem in the single-task assignment scenario,the com-parison experiment shows that the optimization strategies can improve the efficiency of the algorithm.In the multi-task allocation scenario,for the multiple-task summation quality maximization,the dissertation compares the experimental results of the without-parallelization algorithm,the independent task group level parallelization algorithm and the task-level parallelization algorithm,showing the high efficiency of the task-level parallelization algorithm.For the multi-task minimum quality maximization problem,the comparison experiment shows the effectiveness of our proposals.