TY - JOUR
T1 - Joint Deployment Optimization and Flight Trajectory Planning for UAV Assisted IoT Data Collection
T2 - A Bilevel Optimization Approach
AU - Han, Shoufei
AU - Zhu, Kun
AU - Zhou, Mengchu
AU - Liu, Xiaojing
N1 - Funding Information:
This work was supported in part by the National Natural Science Foundation of China under Grant 62071230 and Grant 62061146002, and in part by the Natural Science Foundation of Jiangsu Province under Grant BK20211567, and in part by the Fundo para o Desenvolvimento das Ciencias e da Tecnologia (FDCT) under Grant 0047/2021/A1.
Publisher Copyright:
© 2000-2011 IEEE.
PY - 2022/11/1
Y1 - 2022/11/1
N2 - This work investigates an unmanned aerial vehicle (UAV) assisted IoT system, where a UAV flies to each foothold to collect data from IoT devices, and then return to its start point. For such a system, we aim to minimize the energy consumption by jointly optimizing the deployment and flight trajectory of UAV. It is a mixed-integer non-convex and NP-hard problem. In order to address it, a bilevel optimization approach is proposed, where an upper-level method aims to optimize the deployment of UAV and a lower-level one aims to plan UAV flight trajectory. Specifically, the former optimizes the number and locations of footholds of UAV. This work proposes an improved dandelion algorithm with a novel encoding strategy, in which each dandelion represents a foothold of UAV and the entire dandelion population is seen as an entire deployment. Then, two mutation strategies are designed to adjust the number and locations of footholds. Based on the footholds of the UAV provided by the former, the latter transforms flight trajectory planning into a traveling salesman problem (TSP). This work proposes an iterated greedy algorithm to solve it efficiently. The effectiveness of the proposed bilevel optimization approach is verified on ten instances, and the experimental results show that it significantly outperforms other benchmark approaches.
AB - This work investigates an unmanned aerial vehicle (UAV) assisted IoT system, where a UAV flies to each foothold to collect data from IoT devices, and then return to its start point. For such a system, we aim to minimize the energy consumption by jointly optimizing the deployment and flight trajectory of UAV. It is a mixed-integer non-convex and NP-hard problem. In order to address it, a bilevel optimization approach is proposed, where an upper-level method aims to optimize the deployment of UAV and a lower-level one aims to plan UAV flight trajectory. Specifically, the former optimizes the number and locations of footholds of UAV. This work proposes an improved dandelion algorithm with a novel encoding strategy, in which each dandelion represents a foothold of UAV and the entire dandelion population is seen as an entire deployment. Then, two mutation strategies are designed to adjust the number and locations of footholds. Based on the footholds of the UAV provided by the former, the latter transforms flight trajectory planning into a traveling salesman problem (TSP). This work proposes an iterated greedy algorithm to solve it efficiently. The effectiveness of the proposed bilevel optimization approach is verified on ten instances, and the experimental results show that it significantly outperforms other benchmark approaches.
KW - Bilevel optimization
KW - UAV
KW - dandelion algorithm
KW - deployment optimization
KW - flight trajectory planning
KW - iterated greedy algorithm
KW - machine learning
UR - http://www.scopus.com/inward/record.url?scp=85133797282&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85133797282&partnerID=8YFLogxK
U2 - 10.1109/TITS.2022.3180288
DO - 10.1109/TITS.2022.3180288
M3 - Article
AN - SCOPUS:85133797282
SN - 1524-9050
VL - 23
SP - 21492
EP - 21504
JO - IEEE Transactions on Intelligent Transportation Systems
JF - IEEE Transactions on Intelligent Transportation Systems
IS - 11
ER -