Skip to main content
Article
Minimizing the Deployment Cost of UAVs for Delay-Sensitive Data Collection in IoT Networks
IEEE/ACM Transactions on Networking
  • Wenzheng Xu
  • Tao Xiao
  • Junqi Zhang
  • Weifa Liang
  • Zichuan Xu
  • Xuxun Liu
  • Xiaohua Jia
  • Sajal K. Das, Missouri University of Science and Technology
Abstract

In this paper, we study the deployment of Unmanned Aerial Vehicles (UAVs) to collect data from IoT devices, by finding a data collection tour for each UAV. To ensure the `freshness' of the collected data, the total time spent in the tour of each UAV that consists of the UAV flying time and data collection time must be no greater than a given delay B, e.g., 20 minutes. In this paper, we consider a problem of deploying the minimum number of UAVs and finding their data collection tours, subject to the constraint that the total time spent in each tour of any UAV is no greater than B. Specifically, we study two variants of the problem: one is that a UAV needs to fly to the location of each IoT device to collect its data; the other is that a UAV is able to collect the data of an IoT device if the Euclidean distance between them is no greater than the wireless transmission range of the IoT device. For the first variant of the problem, we propose a novel 4-approximation algorithm, which improves the best approximation ratio 4 4/7 for it so far. For the second variant, we devise the very first constant factor approximation algorithm. We also evaluate the performance of the proposed algorithms via extensive experiment simulations. Experimental results show that the numbers of UAVs deployed by the proposed algorithms are from 11% to 19% less than those by existing algorithms on average.

Department(s)
Computer Science
Publication Status
Early Access
Comments
The work of Sajal K. Das was supported in part by NSF Grants under Award CCF-1725755, Award CNS-1818942, Award SCC-1952045, and Award SaTC-2030624.
Keywords and Phrases
  • Approximation Algorithms,
  • Approximation Algorithms.,
  • Data Collection,
  • Dispatching,
  • Minimum Cycle Cover with Neighborhoods,
  • Minimum Numbers of UAV Deployments,
  • Mobile Data Collection,
  • Monitoring,
  • Multiple UAV Scheduling,
  • Sensors,
  • Unmanned Aerial Vehicles,
  • Wireless Communication
Document Type
Article - Journal
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2021 Association for Computing Machinery (ACM), All rights reserved.
Publication Date
11-13-2021
Publication Date
13 Nov 2021
Disciplines
Citation Information
Wenzheng Xu, Tao Xiao, Junqi Zhang, Weifa Liang, et al.. "Minimizing the Deployment Cost of UAVs for Delay-Sensitive Data Collection in IoT Networks" IEEE/ACM Transactions on Networking (2021) ISSN: 1558-2566; 1063-6692
Available at: http://works.bepress.com/sajal-das/231/