Task Assignment For Mobile Crowdsensing:Algorithm Design And Optimization

Mobile crowdsensing is a novel sensing paradigm for Internet of Things which exploits the mobility,sensing,computation and communication capability of ubiquitous smart devices to collect multiple-dimensional long-term large-scale information of physical world.Mobile crowdsensing has salient properties such as low cost,high mobility,high scalability and human-involved intelligence.Mobile crowdsensing has tremendous applications in areas such as environmental protection,smart transportation,smart city,indoor localization,and public safety,etc.Task allocation is a key issue in mobile crowdsensing.There are many factors having significant impact on the performance of task allocation including sensing capability,communication capability,mobility model of mobile users and spatiotemporal distribution and sensing quality requirement of sensing tasks.How to design effective task allocation mechanisms in various mobile crowdsensing scenarios to improve performance of task allocation and reduce system costs is a challenging issue.This thesis designs and optimizes task allocation models and algorithms for mobile crowdsensing in various scenarios with different design objectives and constraints.The proposed frameworks and algorithms can significantly improve the performance of task allocation.The main contributions of this thesis are summarized as follows.1.Distance-based online task allocation for participatory sensing.In this thesis,the problem of optimizing the overall task quality under constraints of travel distance budget is presented.The NP-hardness of this problem is proved.Four effective online task allocation algorithm are proposed,including Quality/Progress based Algorithm(QPA),Task Density based Algorithm(TDA),Travel-Distance-Balance-based Algorithm(DBA),and Bio-inspired Travel-Distance-Balance-based Algorithm(B-DBA).Simulation results show that the first three algorithms achieve competitive performance with low computational complexity and the last one is better than all the existing work.2.Task allocation problem in semi-opportunistic sensing paradigm.Targeted at the deficiencies of participatory sensing and opportunistic sensing,in this thesis,a new sensing paradigm called semi-opportunistic sensing paradigm is proposed,which achieves low user recruitment cost and high task coverage simultaneously.Two algorithms are proposed to address the problem,including Best Path/Task first algorithm and LP-Relaxation based algorithm.The computational complexities of these algorithms are deduced.Trace-driven simulations show significant performance gain of proposed algorithms.3.Task allocation problems in eco-friendly mobile crowdsensing systems.The properties of different transportation types in urban environment are analyzed.The task allocation problem to minimize carbon emissions under task deadline constraints is proposed.The task allocation problems in online and offline scenarios are presented,respectively.The problem is modeled as bipartite graph matching.Task allocation algorithm for online and offline scenarios are proposed,including processes of transportation selection and task-user matching.The computational complexities of these algorithms are deduced.Simulation results validate the optimized task allocation performance achieved by proposed algorithms.4.Privacy-aware task allocation problem in mobile crowdsensing.In this thesis,a privacy-aware task allocation scheme for mobile crowdsensing is proposed.The scheme is composed of three components including incentive mechanism,user's task selection strategy and platform's user selection strategy.In this scheme,each mobile user determines the privacy-preservation level for himself/herself.Simulation results show that the proposed privacy-aware task allocation framework achieves high task completion ratio.