TY - JOUR
T1 - Nonredundant information collection in rescue applications via an energy-constrained UAV
AU - Liang, Yan
AU - Xu, Wenzheng
AU - Liang, Weifa
AU - Peng, Jian
AU - Jia, Xiaohua
AU - Zhou, Yingjie
AU - Duan, Lei
N1 - Publisher Copyright:
© 2014 IEEE.
PY - 2019/4
Y1 - 2019/4
N2 - Unmanned aerial vehicles (UAVs) are emerging as promising devices to provide valuable information in rescue applications, which can be dispatched to take photographs for points of interests in disaster areas where humans are hard to approach. Most existing studies focused on the limited energy capacity issue of UAVs when they take photographs, which however ignored an important fact, that is, the photographs taken by the UAVs usually are highly redundant. In this paper we study a novel monitoring quality maximization problem to find a flying tour for an energy-constrained UAV, such that the amount of nonredundant information of the photographs taken by the UAV in its tour is maximized. Due to NP-hardness of the problem, we first propose an approximation algorithm with a quasi-polynomial time complexity. We then devise a fast yet scalable heuristic algorithm for the problem. We finally evaluate the performance of the proposed algorithms via both a real dataset and extensive simulations. Experimental results show that the proposed algorithms are very promising. Especially, the amounts of nonredundant information by the proposed approximation and heuristic algorithms are about 11% and 8% larger than that by the state-of-the-art, respectively. To the best of our knowledge, we are the first to consider the novel problem of collecting nonredundant information with an energy-constrained UAV.
AB - Unmanned aerial vehicles (UAVs) are emerging as promising devices to provide valuable information in rescue applications, which can be dispatched to take photographs for points of interests in disaster areas where humans are hard to approach. Most existing studies focused on the limited energy capacity issue of UAVs when they take photographs, which however ignored an important fact, that is, the photographs taken by the UAVs usually are highly redundant. In this paper we study a novel monitoring quality maximization problem to find a flying tour for an energy-constrained UAV, such that the amount of nonredundant information of the photographs taken by the UAV in its tour is maximized. Due to NP-hardness of the problem, we first propose an approximation algorithm with a quasi-polynomial time complexity. We then devise a fast yet scalable heuristic algorithm for the problem. We finally evaluate the performance of the proposed algorithms via both a real dataset and extensive simulations. Experimental results show that the proposed algorithms are very promising. Especially, the amounts of nonredundant information by the proposed approximation and heuristic algorithms are about 11% and 8% larger than that by the state-of-the-art, respectively. To the best of our knowledge, we are the first to consider the novel problem of collecting nonredundant information with an energy-constrained UAV.
KW - Approximation algorithms
KW - constrained optimization
KW - flying tour planning
KW - nonredundant information collection
KW - unmanned aerial vehicles (UAVs)
UR - http://www.scopus.com/inward/record.url?scp=85055683226&partnerID=8YFLogxK
U2 - 10.1109/JIOT.2018.2877409
DO - 10.1109/JIOT.2018.2877409
M3 - Article
SN - 2327-4662
VL - 6
SP - 2945
EP - 2958
JO - IEEE Internet of Things Journal
JF - IEEE Internet of Things Journal
IS - 2
M1 - 8502870
ER -