Research On Theory And Methods For Task Allocation In Crowdsensing

Because of the popularization of portable electronic devices and the progress of wireless communication technologies,crowdsensing has become a promising sensing paradigm,which attracts extensive attentions from industry and academia.These devices are equipped with many sensors,such as accelerometer,camera,microphone and Global Positioning System(GPS),which can be used to collect various sensing data.On the other hand,these devices also have wireless communication modules,make them able to send collected sensing data to base stations.Based on widely-distributed sensing devices and ubiquitous wireless networks,crowdsensing creates a scheme where people can collect and share sensing data.Crowdsensing has a broad application prospect in reality,including environment monitoring,traffic monitoring,health management,and social interaction.A typical crowdsensing system consists of a central server located in the cloud(named platform)and a lot of mobile sensing device users.Different from traditional wireless sensor networks,each sensing device can communicate with the platform directly.The main advantage of crowdsensing is that it saves the cost for sensor deployment and maintenance.The process of data collection in a crowdsensing network is described in the following.A series of sensing requests arrive at the platform,i.e.,sensing tasks.Then,for each sensing task,a proper user is chosen to process it,which is called task allocation.When doing task allocation,the platform needs to take into consideration the requirements of sensing tasks in terms of time,location and data quality,as well as the locations,mobilities and abilities of users.Note that processing sensing tasks will incur certain costs on users due to the consumption of energy,network bandwidth and so on.To maximize the system-wide performance,the platform needs to balance the utilities obtained by completing sensing requests and the costs incurred on users for processing sensing tasks.We summarize four characteristics of crowdsensing,including 1)sensing devices are mobile;2)the resources on a sensing device are limited;3)participating users are rational or strategic;4)sensing devices are owned by users.Due to these characteristics,task allocation turns to be a very challenging problem.Considering different applications with different features of sensing tasks and users,different task allocation algorithms are in demand.In this thesis,we first classify crowdsensing systems according to the dynamism of sensing tasks and the proactivity of user,respectively.Then,optimal or near-optimal task allocation algorithms are designed for different types of crowdsensing systems,which are summarized as follows.1.Distributed optimal task allocation algorithm.Consider an offline crowdsensing system with static sensing tasks and users,in which sensing tasks are collecting sensing data during an arbitrary period.Rational users actively choose their sensing time,with the objective of maximizing their own payoffs.To encourage the participation of users,the platform pays to users according to their sensing time.The system-wide performance criterion is social welfare,which is equal to the utility obtained by the platform minus the total cost incurred on users.Considering cost information of users is their privacy,we design a distributed algorithm providing an appropriate price to each user,which is proved to achieve the optimal social welfare.Simulation results show that our algorithm converges faster than an existing algorithm,and applies to large-scale crowdsensing systems.2.Near-optimal online task allocation algorithm.Consider an online crowdsensing system with cooperative users,where heterogeneous sensing tasks dynamically arrive to the platform in real time.Three important controls need to be made by the platform,i.e.,1)request admission control,2)task allocation,and 3)task scheduling on each user.Note that we consider users passively accept the tasks allocated to them.It is particularly challenging to make control decisions in real time,taking task processing throughput,system stability and user experience into account.Based on the Lyapunov optimization theory,we design an online control algorithm and mathematically prove that our algorithm can achieve near-optimal time-averaged performance and guarantee the system stability.3.Strategic user-oriented online task allocation algorithm.Urban monitoring is an important type of applications of crowdsensing,which needs to continuously collect spatial-temporal sensing data in an area of interest.Firstly,we observe that sensing data exhibits spatial and temporal correlations.Thus,collecting a subset of complete sensing data can reduce the total cost for data collection.The rest missing data can be recovered by interpolation algorithms.Moreover,strategic users are considered,who may cheat the platform for obtaining more payments.An efficient incentive mechanism is necessary to maintain the truthfulness of users.Our approach consists of an online near-optimal task allocation algorithm and a truthful payment policy.Extensive simulations based on real datasets show that our approach performs well.