Paper Info
Title
Minimizing the Number of Deployed UAVs for Delay-bounded Data Collection of IoT Devices
Abstract
In this paper, we study the deployment of Unmanned Aerial Vehicles (UAVs) to collect data from IoT devices, by finding the data collection tour of each UAV. To ensure the `freshness' of the collected data, a strict requirement is that the total time spent in the tour of each UAV, which consists of UAV flying time and data collection time, must be no greater than a given maximum data collection delay B, e.g., 20 minutes. In this paper, we consider a problem of using the minimum number of UAVs and finding their data collection tours, subject to the constraint that the total time spent in each tour is no greater than B. 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 variant is that a UAV is able to collect the data of the IoT device as long as their Euclidean distance is no greater than a given wireless transmission range. For the first variant of the problem, we propose a novel 4-approximation algorithm, which improves the best approximation ratio 4 4/7 so far. For the second variant, we design the first constant factor approximation algorithm. In addition, we evaluate the performance of the proposed algorithms via extensive experiments, and experimental results show that the average numbers of UAVs deployed by the proposed algorithms are from 11% to 19% less than those by existing algorithms.
Year
DOI
Venue
2021
10.1109/INFOCOM42981.2021.9488887
IEEE INFOCOM 2021 - IEEE Conference on Computer Communications
Keywords
DocType
ISSN
Mobile data collection,multiple UAV scheduling,minimum cycle cover with neighborhoods,approximation algorithms
Conference
0743-166X
ISBN
Citations 
PageRank 
978-1-6654-3131-6
2
0.36
References 
Authors
0
8
Name
Order
Citations
PageRank
Junqi Zhang130.71
Zheng Li221.37
Wenzheng Xu331521.18
Jian Peng45911.21
Weifa Liang51676134.75
Zichuan Xu65910.45
Xiaojiang Ren71577.09
Xiaohua Jia84609303.30