OnlineTaskAssignmentandPathPlanningforMobileCrowdsensing资源-CSDN文库

180 浏览量 2021-02-07 01:10:13 上传评论收藏 1.47MB PDF 举报

### 移动众包感知中的在线任务分配与路径规划 #### 概述移动众包感知（Mobile Crowdsensing）是一种新兴且成本效益高的传感范式，它利用了物联网（Internet of Things, IoT）中传感器丰富的移动设备（如智能手机、可穿戴设备、智能车辆等）的普及性。本文探讨了移动众包感知中的一项关键挑战：如何在用户旅行距离预算的约束下最大化任务质量。研究主要聚焦于在线任务分配和路径规划问题。 #### 问题定义与复杂度分析作者们将任务分配和路径规划问题进行了数学建模，并证明了该问题是NP难问题。这意味着不存在已知的多项式时间算法能够解决这个问题，而只能通过近似算法或者启发式算法来寻找解决方案。 #### 在线场景下的算法设计随后，文章针对用户和任务动态到达的情况，设计了四种在线任务分配算法： 1. **质量/进度基础算法（Quality/Progress-based Algorithm, QPA）**：此算法偏好那些能够以最小的旅行成本获得最大任务质量增量的任务。通过这种方式，可以高效地提高任务完成的整体质量。 2. **任务密度基础算法（Task Density-based Algorithm, TDA）**：TDA算法倾向于引导用户前往任务密度较高的区域。这种方法可以确保在有限的时间内完成尽可能多的任务，从而提高任务完成的效率。 3. **旅行距离平衡基础算法（Travel Distance Balance-based Algorithm, DBA）**：除了考虑任务的质量和任务密度之外，DBA算法还考虑了用户的旅行距离。通过平衡不同用户的旅行距离，可以进一步优化任务分配策略。 4. **生物启发式旅行距离平衡基础算法（Bio-Inspired Travel Distance Balance-based Algorithm, B-DBA）**：这是前三种算法的集成和改进版本。B-DBA算法结合了旅行距离平衡的概念以及生物启发式的搜索方法，旨在进一步提高任务分配的性能。 #### 算法性能分析文章还对所提出的算法进行了复杂度分析，以评估这些算法的实际应用价值。此外，通过模拟实验验证了这些算法的有效性。根据模拟结果，B-DBA算法在所有四种算法中表现最佳，在任务质量方面取得了最好的成绩，并且在该领域现有的工作基础上实现了进一步的性能提升。 #### 结论与展望移动众包感知中的在线任务分配与路径规划是一项具有挑战性的研究课题。通过对动态环境下的任务分配进行细致分析，并设计出有效的在线算法，可以显著提高移动众包感知系统的性能。未来的研究方向可能包括探索更复杂的约束条件、开发适用于更大规模数据集的高效算法，以及进一步优化现有算法的性能等。

资源推荐

资源详情

资源评论

1772 IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, VOL. 68, NO. 2, FEBRUARY 2019

Location-Based Online Task Assignment and Path

Planning for Mobile Crowdsensing

Wei Gong , Baoxian Zhang , Senior Member, IEEE,andChengLi , Senior Member, IEEE

Abstract—Mobile crowdsensing has been a promising and cost-

effective sensing paradigm for the Internet of Things by exploit-

ing the proliferation and prevalence of sensor-rich mobile devices

held/worn by mobile users. In this paper, we study the task as-

signment and path planning problem in mobile crowdsensing,

which aims to maximize total task quality under constraints of

user travel distance budgets. We ﬁrst formulate the problem math-

ematically when all task and user arrival information is known

aprioriand prove it to be NP-hard. Then, we focus on studying

the scenarios where users and t asks arrive dynamically and ac-

cordingly design four online task assignment algorithms, including

quality/progress-based algorithm (QPA), task-density-based algo-

rithm (TDA), travel-distance-balance-based algorithm (DBA), and

bio-inspired travel-distance-balance-based algorithm (B-DBA). All

the four algorithms work online for task assignment upon arrival

of a new user. The former three algorithms work in a greedy man-

ner for assigning tasks, one task each time, where the QPA prefers

the task leading to largest ratio of task quality increment to travel

cost, the TDA tends to guide user to high-task-density areas, and

the DBA further considers travel distance balance information. The

last algorithm B-DBA integrates the travel-distance-balance-aware

metric in the DBA and bio-inspired search for further improved

task assignment performance. Complexities of the proposed algo-

rithms are deduced. Simulation results validate the effectiveness of

our algorithms; B-DBA has the best performance among the four

algorithms in terms of task quality, and furthermore, it outper-

forms existing work in this area.

Index Terms—Mobile crowdsensing, participatory sensing, on-

line task assignment, path planning.

I. INTRODUCTION

HE prevalence of sensor-rich mobile devices (e.g., smart-

phones, wearable devices, and smart vehicles) has been

playing an increasing crucial role in the Internet of Things (IoT)

[1], [2]. This has promoted the emergence of a new mobile-

user-centric sensing paradigm, mobile crowdsensing [3], [4]. In

Manuscript received July 15, 2018; revised September 28, 2018; accepted

November 25, 2018. Date of publication November 30, 2018; date of current

version February 12, 2019. This work was supported in part by the National

Natural Science Foundation of China under Grants 61872331, 61531006, and

61471339, in part by the Natural Sciences and Engineering Research Council

of Canada under Discovery Grant RGPIN-2018-03792, and in part by the In-

novateNL SensorTECH Grant 5404-2061-101. The review of this paper was

coordinated by Prof. J. Misic. (Corresponding author: Baoxian Zhang.)

W. Gong and B. Zhang are with the Research Center of Ubiquitous Sensor

Networks, University of Chinese Academy of Sciences, Beijing 100049, China

(e-mail:,gongwei11@mails.ucas.ac.cn; bxzhang@ucas.ac.cn).

C. Li is with the Faculty of Engineering and Applied Science, Memorial

University, St. John’s, NL A1B 3X5, Canada. He is also afﬁliated with Tianjin

Chengjian University (e-mail:,licheng@mun.ca).

Digital Object Identiﬁer 10.1109/TVT.2018.2884318

the past, in most IoT systems, static wireless sensor networks

(WSNs) played major role in data collection where sensors

are typically untended and have limited resources (e.g., energy,

communications, storage, and computation), which largely af-

fect their capability for providing high quality IoT services.

Mobile crowdsensing integrates the prevalence of smart devices

held/worn by mobile users and also their powerful capability

(e.g., their sensing, computing, and wireless communication

capabilities) into the provisioning of ubiquitous IoT services.

Compared with static WSN based IoT solutions, mobile crowd-

sensing has many advantages: low cost for deployment, inherent

mobility by mobile users, and huge population of mobile devices

and extensive coverage of such devices. Mobile crowdsensing

facilitates wide-range longtime multidimensional sensing data

collection for monitoring the physical world. With the partici-

pation of mobile crowdsensing users, many phenomena in their

vicinity can be easily observed such as noise pollution, road

congestion, surrounding context and environmental pollution.

In this way, mobile crowdsensing has promoted various IoT

services and applications, such as environmental monitoring,

indoor localization, pervasive cloud services, road trafﬁc moni-

toring, smart cities, etc. (see [5]–[12]).

In a typical mobile crowdsensing system, task requesters pub-

lish a set of tasks with task requirement details such as task

deadlines, incentive rewards, and required data amount, accu-

racy, and granularity on a service platform. The platform re-

cruits some mobile users ( also called mobile workers in some

work [13], [14]) to undertake these tasks. Mobile users col-

lect required sensing data when moving to task locations. They

get compensated if they upload valid sensing data to the plat-

form. Based on whether mobile users perform sensing tasks

consciously, mobile crowdsensing is divided into two classes:

opportunistic sensing and participatory sensing. In opportunistic

sensing, active involvement of mobile users is not necessary and

mobile users typically move along pre-determined paths (e.g.,

along with track-based transportation systems) or follow cer-

tain mobility patterns affected by their daily routines, habits, or

preferences (e.g., go to workplace or visit friends). Mobile de-

vices can be programmed to collect sensing data automatically

as the device holders move. In participatory sensing, mobile

users are required to move to speciﬁc task locations to under-

take certain tasks. The moving paths of such users are planned

based on assigned tasks and their involvements are intentional

and controllable.

Task assignment [15] is a crucial problem in mobile crowd-

sensing. One key issue in task assignment is to achieve

See http://www.ieee.org/publications

standards/publications/rights/index.html for more information.

GONG et al.: LOCATION-BASED ONLINE TASK ASSIGNMENT AND PATH PLANNING FOR MOBILE CROWDSENSING 1773

high task quality with limited resources. Major measures for

characterizing task quality include data collection times [16],

spatiotemporal coverage [17], or certain weighted coverage

quality [18]. Resource limitations considered for performing

tasks include incentive budget, device capability, user prefer-

ence, and travel distances. Incentive budget is the incentive

compensation for worker recruitment [16], worker travelling

[19], or data transferring [20]. Device capability includes data

sensing accuracy [21], communication opportunity to ﬁxed in-

frastructure [22], and/or residual energy [17], [23]. User prefer-

ence includes user enthusiasm [24], user privacy concern [25],

and/or user social interaction [26]. Travel distance budget is

the maximum travel distance that a user can take [19], [27]. In

opportunistic sensing, the task assignment problem is how to

select a number of eligible mobile users from a large user pool

to undertake tasks as they move while maximizing task quality

or minimizing resource consumption. The problem is typically

NP-hard and various effective solutions have been proposed

[13], [18], [22], [28]. In participatory s ensing, the platform usu-

ally needs to consider how to make path planning for different

users to maximize total task quality while meeting various re-

source limitations (e.g., travel distances or incentive budgets),

which often makes the assignment problem even harder.

In this paper, we study online task assignment and path plan-

ning in participatory sensing when mobile users have travel

distance budget constraints. The design goal is to maximize the

total task quality subject to travel distance budget constraints

of mobile users. We assume that mobile users and tasks arrive

dynamically. Our major work in this paper is summarized as fol-

lows. First, we formulate the optimal task assignment problem

mathematically when all user and task arrivals are known a pri-

ori and further prove the problem is NP-hard. Second, we design

four efﬁcient polynomial online task assignment algorithms to

address this problem, including Quality/Progress based Algo-

rithm (QPA), Task Density based Algorithm (TDA), Travel-

Distance-Balance-based Algorithm (DBA), and Bio-inspired

Travel-Distance-Balance-based Algorithm (B-DBA). All these

four algorithms work in an online manner such that, upon the

arrival of a new user, a number of tasks are allocated to the

user with an expectation of maximum task quality increment

subject to the user’s travel distance budget. The former three

algorithms work in a greedy way for assigning tasks to the new

user: Each time one task is assigned to the user according to

certain criteria as long as the travel distance budget constraint

is respected, and this process keeps going until no task can be

assigned. In this process, QPA prefers the task with the largest

ratio of task quality increment over travel distance, TDA tends to

guide the user t o high task-density areas, and DBA further takes

the impact of travel distance balance after a task selection into

consideration. The last algorithm B-DBA integrates the travel-

distance-balance-based metric in DBA and bio-inspired search

in [29] for further improved task assignment performance. The

relationship of the four algorithms is as follows. TDA and DBA

extend the idea in QPA by considering task density information

and travel distance balance after task selection, respectively,

and B-DBA combines DBA and bio-inspired search. The com-

plexities of the proposed algorithms are deduced. We conduct

extensive simulations and the results validate the effectiveness

of our algorithms and further B-DBA has the best performance

among the four algorithms in terms of task quality and also it

outperforms existing work in this aspect. A partial version of

this paper was presented at IEEE GLOBECOM 2017 [30].

The remainder of this paper is structured as follows. In

Section II, we review existing work. In Section III, we describe

the system model, formulate the problem under study, and prove

its NP-hardness. In Section IV, we propose four polynomial on-

line task assignment algorithms, present their respective design

details, and also deduce their computational complexities. In

Section V, we present simulation results for performance eval-

uation. Finally, we conclude this paper in Section VI.

II. R

ELATED WORK

Much work has been done for supporting efﬁcient task as-

signment for mobile crowdsensing. In the following, we shall

respectively introduce existing work in the following three as-

pects: User selection in opportunistic sensing, task assignment

in participatory sensing, and task assignment for the orienteering

problem in operational research.

A. User Selection in Opportunistic Sensing

Opportunistic sensing can be divided into ﬁxed-path-based

and probabilistic-visit-based. For ﬁxed-path-based opportunis-

tic sensing, mobile users move along predetermined paths. For

probabilistic-visiting-based opportunistic sensing, users travel

among a few locations in an opportunistic manner based on cer-

tain patterns or probability distribution. In opportunistic sensing,

when a user passes by a task location, he/she can undertake the

task. The optimal task assignment in opportunistic sensing typ-

ically has two different forms: optimally choosing a number of

users for optimizing the task quality subject to given budget

limit, or minimizing the incentive budget while meeting given

task quality.

Typical work for user selection for ﬁxed-path-based oppor-

tunistic sensing is as follows. [13] studied a multi-user selection

problem of maximizing the number of completed tasks and pro-

posed three greedy heuristic algorithms, which iteratively give

priority to the user taking the path with the maximum num-

ber of tasks, with more urgent tasks, and with more unpopular

tasks, respectively. [18] studied a multi-user selection problem

for maximizing a utility function of task quality under incentive

budget constraint and proposed a heuristic algorithm which is

proved to be approximate owing to the utility function’s sub-

modular property.

Typical work for probabilistic-visit-based opportunistic sens-

ing is as follows. [31] studied a multi-objective optimization

problem of user selection to maximize expected task quality and

proposed a greedy algorithm which iteratively chooses the user

with the highest utility. The expected task quality is computed

according to user transition matrix. [22] focused on the prob-

lem of multi-user selection in opportunistic networks to mini-

mize user employment fees, which transfers sensing data from

their data collection locations to Access Points via probabilistic-

encounter-based multi-hop forwarding. [28] focused on the sce-

剩余11页未读，继续阅读

评论收藏

内容反馈

weixin_38702047

粉丝: 3
资源: 967

Online Task Assignment and Path Planning for Mobile Crowdsensing

SOM Neural Network Based Method for Task Assignment of Multi-Agent Systems

Cooperation Aware Task Assignment in Spatial Crowdsourcing.pdf

A hybrid particle swarm optimization algorithm for optimal task assignment in distributed systems

optical network design and planning

matlab.rar_Task Assignment_任务分配_形成编队_编队_编队形成

CS193P IOS APPLICATION DEVELOPMENT Assignment 1 Walkthrough.pdf

数学估算 常量因子近似算法Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks06 bell.pdf

Copy Constructors and Assignment Operators终极解释

UiPath 官网Level 1 Lesson3题库

Assignment03_task01.cpp

Static Single Assignment for Decompilation PDF

The Assignment Problem and The Hungarian Method

for_loop_assignment.rar_assignment

An-Efficient-and-Robust-Addressing-Protocol.rar_assignment

Energy Efficient Task Assignment with Guaranteed Probability Satisfying Timing Constraints for Embedded Systems

Assignment 5_matlab_assignment_

斯坦福iOS 2013-2014Assignment 6 Topregions-assignment6task1-7

Score Analysis程序代码

arguments-read-and-assignment.rar_assignment

Aurora Lane Assignment分配（小tips）

vue-springboot高中信息技术课程在线测试系统java毕业论文.docx

FERRARI - Flexible and Efficient Reachability Range Assignment for Graph Indexing-计算机科学

Assignment-2.zip_assignment

最新资源

数学估算常量因子近似算法Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks06 bell.pdf