Rational Task Assignment and Path Planning Based on Location and Task Characteristics in Mobile Crowdsensing
Rational Task Assignment and Path Planning Based on Location and Task Characteristics in Mobile Crowdsensing
复制标题
移动群智中基于位置和任务特征的合理任务分配和路径规划
DOI：
10.1109/tcss.2021.3095946
复制
发表时间：
2022-06
影响因子：
5
通讯作者：
Xuetao Wei
中科院分区：
文献类型：
--
作者：
Bo Yin;Jiaqi Li;Xuetao Wei
随着智能设备的飞速发展，移动的人群感知（MCS）已经成为数据收集的一种创新模式。任务分配是MCS系统和应用中的一个基本问题。以往的研究只关注单个任务的分配，而忽略了从更高的层次上对任务加工进行规划，在任务位置和工作人员之间进行分配，这对人群感知性能产生不利影响。此外，任务特性，例如，路径距离、任务相似度和任务优先级对访问顺序的合理性和众测服务质量有很大影响。在这篇文章中，我们解决了合理的任务分配和路径规划问题的MCS，其目的是分配一组任务的位置，一组工人和位置访问序列产生。我们通过考虑地理信息和任务特征来衡量分配合理性，即，路由距离、任务相似度和任务优先级。我们证明了计算合理性最大化任务分配的问题是NP难的。对于单个工作人员的情况下，我们减少了一个更简单的问题，只有路由距离和任务的优先级标准，因为相似性度量有一个固定的值。我们提出了一个有效的贪婪算法。对于多工人的情况下，我们首先扩展了贪婪的想法，考虑所有三个标准，然后提出了一种有效的方法，通过减少计算复杂度的相似性度量。大量的实验表明，我们提出的方法取得了可喜的成果。
With the great development in smart devices, mobile crowdsensing (MCS) has been an innovative paradigm for data gathering. Task assignment is a fundamental problem in MCS systems and applications. Previous studies only focused on the assignment of individual tasks, neglecting planning the task processing from a higher level, e.g., making assignments between task locations and workers, which impacts the crowdsensing performance adversely. Furthermore, task characteristics, e.g., route distance, task similarity, and task priority, have a great impact on the rationality of a visiting order and the quality of crowdsensing services. In this article, we tackle the problem of rational task assignment and path planning for MCS, which aims to assign a set of task locations to a set of workers and generate location visiting sequences. We measure the assignment rationality by taking into account geographical information and task characteristics, i.e., route distance, task similarity, and task priority. We prove that the problem of computing the rationality maximization task assignment is NP-hard. For the single-worker scenario, we reduce the problem to a simpler problem with respect to only route distance and task priority criteria since the similarity measurement has a fixed value. We propose an effective greedy algorithm. For the multiple-worker scenario, we first extend the greedy idea by considering all three criteria and then propose an effective approach by reducing the computational complexity of similarity measurement. Extensive experiments show that our proposed approaches achieve promising results.