Abstract: As a result of the popularity of mobile devices, Mobile Crowd Sensing(MCS) has attracted a lot of attention.Task allocation is a significant problem in MCS.Most previous studies mainly focused on stationary spatial tasks while neglecting the changes of tasks and workers.In this paper, the proposed hybrid two-phase task allocation algorithm considers heterogeneous tasks and diverse workers.For heterogeneous tasks, there are different start times and deadlines.In each round, the tasks are divided into urgent and non-urgent tasks.The diverse workers are classified into opportunistic and participatory workers.The former complete tasks on their way, so they only receive a fixed payment as employment compensation, while the latter commute a certain distance that a distance fee is paid to complete the tasks in each round as needed apart from basic employment compensation.The task allocation stage is divided into multiple rounds consisting of the opportunistic worker phase and the participatory worker phase.At the start of each round, the hiring of opportunistic workers is considered because they cost less to complete each task.The Poisson distribution is used to predict the location that the workers are going to visit, and greedily choose the ones with high utility.For participatory workers, the urgent tasks are clustered by employing hierarchical clustering after selecting the tasks from the uncompleted task set.After completing the above steps, the tasks are assigned to participatory workers by extending the Kuhn-Munkres(KM) algorithm.The rest of the uncompleted tasks are non-urgent tasks which are added to the task set for the next round.Experiments are conducted based on a real dataset, Brightkite, and three typical baseline methods are selected for comparison.Experimental results show that the proposed algorithm has better performance in terms of total cost as well as efficiency under the constraint that all tasks are completed.

Key words: Mobile Crowd Sensing(MCS), two-phase task allocation, Kuhn-Munkres(KM) algorithm, opportunistic worker, participatory worker

摘要： As a result of the popularity of mobile devices, Mobile Crowd Sensing(MCS) has attracted a lot of attention.Task allocation is a significant problem in MCS.Most previous studies mainly focused on stationary spatial tasks while neglecting the changes of tasks and workers.In this paper, the proposed hybrid two-phase task allocation algorithm considers heterogeneous tasks and diverse workers.For heterogeneous tasks, there are different start times and deadlines.In each round, the tasks are divided into urgent and non-urgent tasks.The diverse workers are classified into opportunistic and participatory workers.The former complete tasks on their way, so they only receive a fixed payment as employment compensation, while the latter commute a certain distance that a distance fee is paid to complete the tasks in each round as needed apart from basic employment compensation.The task allocation stage is divided into multiple rounds consisting of the opportunistic worker phase and the participatory worker phase.At the start of each round, the hiring of opportunistic workers is considered because they cost less to complete each task.The Poisson distribution is used to predict the location that the workers are going to visit, and greedily choose the ones with high utility.For participatory workers, the urgent tasks are clustered by employing hierarchical clustering after selecting the tasks from the uncompleted task set.After completing the above steps, the tasks are assigned to participatory workers by extending the Kuhn-Munkres(KM) algorithm.The rest of the uncompleted tasks are non-urgent tasks which are added to the task set for the next round.Experiments are conducted based on a real dataset, Brightkite, and three typical baseline methods are selected for comparison.Experimental results show that the proposed algorithm has better performance in terms of total cost as well as efficiency under the constraint that all tasks are completed.

关键词: Mobile Crowd Sensing(MCS), two-phase task allocation, Kuhn-Munkres(KM) algorithm, opportunistic worker, participatory worker

CLC Number: 

• TP393