A QoS-sensitive Task Assignment Algorithm For Mobile Crowdsensing

Mobile crowdsensing is a new paradigm.It collects multiple smart device users to cooperatively complete huge scale sensing tasks,which traditional networks cannot cope with.Usually,these smart devices,which are equipped with multiple processors and sensors,can compute and sense complex tasks.High quality and low cost are two metrics,which decides whether to make use of mobile crowdsensing to complete sens-ing tasks or not.Therefore,how to complete these tasks with high quality and low cost is of great significance.We study a QoS-sensitive task assignment problem for mobile crowdsensing.Due to the unprofessional of users,their sensing habits have influence on the QoS of tasks.Hence,how to ensure the QoS of tasks is very important.Based on this situation,this paper proposes two different QoS-sensitive task assignment problems,and provides solutions to these problems.The main contributions of our paper are listed in the following:· First of all,we study a QoS-sensitive problem,whose optimization is to mini-mize the cost of crowdsensing.Unlike existing works,we consider a variable task assignment problem,which is composed of two parts:variable tasks and flexible rewards.Each user can conduct one or more tasks,and the number of tasks assigned to each user is variable.The reward paid to the user is related to the assigned tasks.To ensurie the QoS of tasks,each task might be assigned to multiple users.We prove the problem to be NP-hard.Then,we design a QoS-sensitive task assignment algorithm which is based on a greedy strategy.Finally,we prove that our algorithm outperforms than existing algorithms through theo-retical analysis and simulations.· Further,after analyzing characteristic of tasks and users’ sensing habits,we in-troduce a multi-dimension QoS-sensitive task assignment problem.To complete a task,all of its QoS should be satisfied.Since the QoS of each task is multi-dimensioned,we design a new method to calculate the QoS.Then,we design a multi-dimension QoS utility function,based on which we propose a greedy al-gorithm.The algorithm always selects a triple which can maximize the QoS of tasks with cost minimum,till the QoS of all tasks satisfy.Finally,we analyze the performance of the algorithm through theoretical proof and plenty of experiments.Our task assignment model and incentive mechanism are both adaptable to many cases.Besides,the QoS-sensitive task assignment algorithm can cope with many QoS-required mobile crowdsensing system.Therefore,it is of great significance to the de-velopment of mobile crowdsensing.