动态移动众包任务分配与路径规划优化
170 浏览量
更新于2024-08-28
收藏 1.47MB PDF 举报
在线任务分配与路径规划是移动众包（Mobile Crowdsensing）领域的重要研究课题，特别是在物联网（IoT）时代，随着智能手机和其他传感器丰富的设备在用户中的普及，这一技术的应用潜力巨大。本文发表于2019年2月的《IEEE Transactions on Vehicular Technology》第68卷第2期，作者Wei Gong、Baoxian Zhang和Cheng Li均为IEEE高级会员。
研究的核心问题在于，在用户有限的旅行距离预算下，如何最大化整体任务质量。首先，论文对已知所有任务和用户到达信息的情况进行了数学建模，并证明了该问题属于NP难问题，即寻找最优解复杂度极高，通常难以在多项式时间内找到。
接着，面对动态的任务和用户到达情况，文章着重探讨了四种在线任务分配算法。这些算法包括：
1. 质量/进度基于算法（Quality/Progress-based Algorithm, QPA）：该算法考虑了任务完成的质量以及用户的执行进度，旨在平衡任务完成的效率和质量。
2. 任务密度基于算法（Task-Density-based Algorithm, TDA）：这种算法重点关注任务分布的密集区域，根据用户当前位置和任务需求来决定任务分配，以提高整体的感知效率。
3. 旅行距离平衡基于算法（Travel-Distance-Balance-based Algorithm, DBA）：这个算法的目标是均衡用户之间的旅行距离，通过合理的任务分配，减少用户之间的不均衡负担，提升用户满意度。
4. 生物启发式旅行距离平衡算法（Bio-Inspired Travel-Distance-Balance-based Algorithm, B-DBA）：这是借鉴生物进化策略的一种方法，如遗传算法或蚁群优化，通过模拟自然界的进化过程，寻找更加全局最优的任务分配方案，同时兼顾用户旅程的公平性。
这些在线算法的设计旨在适应现实世界中的动态环境，提高任务执行的效率和响应性，确保在有限的资源条件下实现最佳的性能。研究结果对于优化移动众包系统的资源调度和用户体验具有重要意义，有助于推动该领域的进一步发展。
1774 IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, VOL. 68, NO. 2, FEBRUARY 2019
nario where task requesters and data collectors are all moving
in the same area. The paper deduced the inter-meeting time dis-
tributions among users and proposed efficient task assignment
algorithms to minimize the t ask completion time. [32] stud-
ied both deterministic and probabilistic models in vehicle-based
mobile crowdsensing and proposed efficient vehicle recruitment
algorithms to minimize the overall recruitment cost.
B. Task Assignment in Participatory Sensing
Participatory sensing can be classified into discontinuous-
moving-based and continuous-moving-based. In discontinuous-
moving-based participatory sensing, a mobile user can perform
multiple tasks in his/her moving range, each at a distinct loca-
tion. In this case, only the distance from the resident location
of the user to each task location is counted. Continuous mov-
ing between different task locations is not considered. Such
discontinuous-moving assumption can greatly simplify the task
assignment problem and also largely reduce the complexity for
solving the task assignment problem. In continuous-moving-
based participatory sensing, the platform determines each user’s
moving path and also tasks to perform. The problem has close
similarity with the well-known Traveling Salesman Problem
(TSP) problem. In this case, design of sophisticated task assign-
ment schemes is usually needed to maximize the task quality or
minimize the total incentive cost.
Typical discontinuous-moving-based participatory sensing
mechanisms are as follows. [14] aims to maximize task com-
pletion rate and also platform profit under constraints of task
deadlines, task performing capacity, and Euclidean travel dis-
tance constraints. The authors modeled the problem as a maxi-
mum weight bipartite matching problem, and proposed an online
approximate matching algorithm. [33] studied the assignment
problem of minimizing incentive payout under constraints of
travel distance and expected task quality.
Some typical continuous-moving-based participatory sensing
mechanisms are as follows. [34] proposed a task management
framework which aims to maximize the task completion rate
and the coverage area of sensor trajectories simultaneously. [27]
aims to maximize the platform profit (defined as incomes from
task requesters minus rewards paid to users) subject to user
travel distance budget and proposed an approximate algorithm
by applying local-ratio technique such that the task assignments
and itineraries for all users are determined in an offline manner.
The objective in [19] is to maximize the number of completed
tasks and also minimize the sum of travel distance of all mo-
bile users. The problem was first modeled using minimum cost
maximum flow theory. A heuristic solution was then proposed,
which restricts each mobile user to select tasks from his/her
closest k tasks. [35] studied the moving path scheduling prob-
lem to minimize total task tardiness penalty. Tardiness penalty
is an increasing function of task expiration time. The authors de-
signed a genetic algorithm to address this problem. A common
assumption on user movement in [19], [27], [35] is that mobile
users only have starting points but without destination points.
[36] focused on the online task assignment where mobile users
and tasks arrive dynamically. The objective is to maximize total
task quality under constraints of users’ travel distance budgets
and task performing capacity (more exactly, maximum amount
of tasks that each user is allowed to perform during an itinerary).
In [36], each user is assumed to have a start point, a destination
point, and a travel distance budget. In [36], a Quality-Aware On-
line Task Assignment algorithm (QAOTA) was proposed and it
uses depth-first search with branch and bound for optimal task
assignment for each arriving user. The computational complex-
ity of QAOTA is O(N
M
), where M and N are the task perform-
ing capacity of a user and the total number of tasks, respectively.
Our work in this paper belongs to the continuous-moving-based
participatory sensing category and the user- and task- related
assumptions used in this paper are the same to those in [36].
However, we do not put restriction on task capacity to achieve
improved task assignment performance.
C. Task Assignment for the Orienteering Problem in
Operational Research
Task assignment and path planning in participatory sensing is
very similar to the orienteering problem in operational research.
Orienteering problem is to find a path (with limited length) that
visits some vertices (each with a score) to maximize the sum of
scores.
Many researchers had proposed heuristics [29], [37]–[41]
to tackle the orienteering problem. [37] proposed a Monte-
Carlo-based stochastic algorithm, a sector-separating-based
deterministic algorithm, and a route-improvement algorithm.
[38] designed a heuristic including four phases: vertex inserting,
cost improvement, vertex deletion, and maximal insertions.
[39] first uses a greedy method to construct an initial solution
and improves the solution by four steps: one-point movement,
two-point exchange, clean up, and reinitialization. [29] pro-
posed a heuristic based on Pareto Ant Colony Optimization
(PACO) and a post-processing procedure. The post-processing
procedure includes three improvement methods: path shorten-
ing, vertex inserting, and vertex exchanging. Path shortening
is to reduce the path length by rearranging the vertex sequence.
Path shortening is the most important one among these three
methods since it can make room for vertex inserting and vertex
exchanging. The method used for path shortening in [29] is
2-opt local improvement algorithm which selects two vertices
in the path and reverses the vertex sequence between these two
vertices. [42] proved t hat upper bounds on the average number
of iterations by 2-opt with n vertices in a Euclidean square is
O(n
10
logn) for any n ≥ 8, which is computationally intensive.
Vertex inserting is to insert a vertex out of the path into the
path. Vertex exchanging is to replace a vertex in the path with
another vertex out of the path. Vertex inserting and vertex
exchanging can increase the total score of a path. [40] showed
that the PACO algorithm in [29] is a competitive solution for
the orienteering problem and also it outperforms the algo-
rithms proposed in [37]–[39]. For more information regarding
solutions for the OP problem, please refer to [40], [41].
Team orienteering problem is one variant of orienteering
problem and its objective is to determine several paths, one
for each member in a team. Several algorithms for this problem
剩余11页未读，继续阅读
点击了解资源详情
点击了解资源详情
点击了解资源详情
2021-02-09 上传
2018-03-20 上传
2021-09-11 上传
2009-12-03 上传
2021-03-19 上传
2021-04-23 上传
weixin_38702047
- 粉丝: 3
- 资源: 967
我的内容管理
展开
最新资源
- WordPress作为新闻管理面板的实现指南
- NPC_Generator：使用Ruby打造的游戏角色生成器
- MATLAB实现变邻域搜索算法源码解析
- 探索C++并行编程：使用INTEL TBB的项目实践
- 玫枫跟打器：网页版五笔打字工具，提升macOS打字效率
- 萨尔塔·阿萨尔·希塔斯：SATINDER项目解析
- 掌握变邻域搜索算法：MATLAB代码实践
- saaraansh: 简化法律文档，打破语言障碍的智能应用
- 探索牛角交友盲盒系统：PHP开源交友平台的新选择
- 探索Nullfactory-SSRSExtensions: 强化SQL Server报告服务
- Lotide：一套JavaScript实用工具库的深度解析
- 利用Aurelia 2脚手架搭建新项目的快速指南
- 变邻域搜索算法Matlab实现教程
- 实战指南：构建高效ES+Redis+MySQL架构解决方案
- GitHub Pages入门模板快速启动指南
- NeonClock遗产版：包名更迭与应用更新
