KLI

Time-Constrained Task Allocation and Worker Routing in Mobile Crowd-Sensing Using a Decomposition Technique and Deep Q-Learning

Metadata Downloads
Abstract
Mobile crowd-sensing (MCS) is a data collection paradigm, which recruits mobile users with smart devices to perform sensing tasks on a city-wide scale. In MCS, a key challenge is task allocation, especially when MCS applications are time-sensitive, and the platform needs to consider task completion order (since a worker may perform multiple tasks and different task completion orders lead to different travel costs and response times, i.e., the times needed to arrive at the task venues), requirements of tasks (such as deadline and required sensor) and workers heterogeneity. In other words, the task allocation problem consists of multiple task completion order problems, which is challenging to solve due to the large solution space. Therefore, in this paper, we first formulate the considered problem into two related integer linear programming problems (i.e., assignment and task completion order problems) using a decomposition technique in order to reduce the problem size and enable the use of diverse searching strategies. Then, a deep Q-learning (DQN)-based algorithm, namely assignment DQN with a local search (A-DQN w/ LS), is proposed to determine the task-worker assignments, which iteratively employs an asymmetric traveling salesman (ATSP) heuristic to find the task completion orders of the workers. The local optimizer is applied at the end of the A-DQN algorithm to deal with the computation time and local optima. Simulation results show that the proposed method outperforms existing approaches under different sensing dynamics in terms of total cost.
Author(s)
악터 샤티Thi-Nga Dao윤석훈
Issued Date
2021
Type
Article
Keyword
Deep reinforcement learningmobile crowd-sensingPerformance evaluationResource managementSensorsSmart devicestabu searchtask allocationTask analysisTraveling salesman problemsUnmanned aerial vehicles
DOI
10.1109/ACCESS.2021.3094528
URI
https://oak.ulsan.ac.kr/handle/2021.oak/9017
https://ulsan-primo.hosted.exlibrisgroup.com/primo-explore/fulldisplay?docid=TN_cdi_doaj_primary_oai_doaj_org_article_1c3189725ee9459ab3a35ba5107c3359&context=PC&vid=ULSAN&lang=ko_KR&search_scope=default_scope&adaptor=primo_central_multiple_fe&tab=default_tab&query=any,contains,Time-Constrained%20Task%20Allocation%20and%20Worker%20Routing%20in%20Mobile%20Crowd-Sensing%20Using%20a%20Decomposition%20Technique%20and%20Deep%20Q-Learning&offset=0&pcAvailability=true
Publisher
IEEE ACCESS
Location
미국
Language
영어
ISSN
2169-3536
Citation Volume
9
Citation Number
1
Citation Start Page
95808
Citation End Page
95822
Appears in Collections:
Engineering > Electrical engineering
Authorize & License
  • Authorize공개
Files in This Item:
  • There are no files associated with this item.

Items in Repository are protected by copyright, with all rights reserved, unless otherwise indicated.