Energy-Efficient UAV Trajectory Planning based on Flexible Segment Clustering Algorithm

Limei Peng

¹ School of Computer Science and Engineering, Kyungpook National University, Deagu, South Korea

Email: ¹{meihaoran, auroraplm}@knu.ac.kr

*Corresponding author

This paper plans the energy-efficient UAV trajectory when a UAV gathers data from massive IoT devices in a given area. The UAV trajectory design is addressed by two steps, i.e., IoT node clustering and UAV flight path planning for scanning the clusters, which are formulated as Cluster Minimization (CM) problem and Traveling Salesman Problem (TSP) in this work, respectively. The CM aims to contribute fewest clusters with minimal overlap to cover all the IoT devices and the per cluster size approaching the UAV communication coverage. On the other hand, the TSP seeks to design the shortest flight path to cover all the grouped clusters while minimizing energy consumption. Specifically, this work mainly focuses on the CM problem since the TSP issues have been well addressed in the past. In particular, we design a two-stage ILP optimization model to formulate the CM problem and propose two flexible clustering algorithms with low complexity, i.e., segment clustering (SC) and its variant, saying shifted SC (SSC). For the proposed ILP model and algorithms, we conduct extensive simulations under five different topologies and compare the performance results with existing methods. The simulation results indicate that the performance achieved by the proposed SSC algorithm is closest to the optimal results obtained from the ILP model. Moreover, it outperforms the existing methods under most topologies regarding cluster numbers, trajectory path length, and power consumption.

IoT, UAV, ILP, clustering, trajectory planning, data collection

Haoran Mei and Limei Peng (2023). Energy-Efficient UAV Trajectory Planning based on Flexible Segment Clustering Algorithm. Journal of Networking and Network Applications, Volume 3, Issue 3, pp. 109–118. https://doi.org/10.33969/J-NaNA.2023.030302.

[1] H. Shakhatreh, A. H. Sawalmeh, A. Al-Fuqaha, Z. Dou, E. Almaita, I. Khalil, N. S. Othman, A. Khreishah, and M. Guizani, “Unmanned aerial vehicles (uavs): A survey on civil applications and key research challenges,” IEEE Access, vol. 7, pp. 48 572–48 634, 2019.

[2] L. Gupta, R. Jain, and G. Vaszkun, “Survey of important issues in uav communication networks,” IEEE Communications Surveys Tutorials, vol. 18, no. 2, pp. 1123–1152, 2016.

[3] Y. Zeng, R. Zhang, and T. J. Lim, “Wireless communications with unmanned aerial vehicles: opportunities and challenges,” IEEE Communications Magazine, vol. 54, no. 5, pp. 36–42, 2016.

[4] S. Li et al., “Dynamic online trajectory planning for a uav-enabled data collection system,” IEEE Transactions on Vehicular Technol-ogy, vol. 71, no. 12, pp. 13 332–13 343, 2022.

[5] X. Bresson and T. Laurent, “The transformer network for the traveling salesman problem,” 2021.

[6] M. Chen, W. Liang, and Y. Li, “Data collection maximization for uav-enabled wireless sensor networks,” in 2020 29th International Conference on Computer Communications and Networks (ICCCN), 2020, pp. 1–9.

[7] X. Ji, X. Meng, A. Wang, Q. Hua, F. Wang, R. Chen, J. Zhang, and D. Fang, “E2pp: An energy-efficient path planning method for uav-assisted data collection,” Security and Communication Networks, vol. 2020, p. 8850505, Dec 2020. [Online]. Available: https://doi.org/10.1155/2020/8850505

[8] J. R. Martinez-de Dios, K. Lferd, A. de San Bernabé, G. Núñez, A. Torres-González, and A. Ollero, “Cooperation between uas and wireless sensor networks for efficient data collection in large environments,” Journal of Intelligent & Robotic Systems, vol. 70, no. 1, pp. 491–508, Apr 2013. [Online]. Available: https://doi.org/10.1007/s10846-012-9733-2

[9] D.-T. Ho, E. I. Grøtli, P. B. Sujit, T. A. Johansen, and J. B. Sousa, “Optimization of wireless sensor network and uav data acquisition,” Journal of Intelligent & Robotic Systems, vol. 78, no. 1, pp. 159–179, Apr 2015. [Online]. Available: https://doi.org/10.1007/s10846-015-0175-5

[10] M. Chen, W. Liang, and S. K. Das, “Data collection utility max-imization in wireless sensor networks via efficient determination of uav hovering locations,” in 2021 IEEE International Conference on Pervasive Computing and Communications (PerCom), 2021, pp. 1–10.

[11] L. Perron et al., “Or-tools,” Google. [Online]. Available: https: //developers.google.com/optimization/

[12] B. Zhu et al., “Uav trajectory planning for aoi-minimal data collec-tion in uav-aided iot networks by transformer,” IEEE Transactions on Wireless Communications, vol. 22, no. 2, pp. 1343–1358, 2023.

[13] K. Akkaya and M. Younis, “A survey on routing protocols for wireless sensor networks,” Ad Hoc Networks, vol. 3, no. 3, pp. 325–349, 2005. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S1570870503000738

[14] H. J. Gulczynski D.J. and P. C.C., “The close enough traveling sales-man problem: A discussion of several heuristics,” in [Perspectives in Operations Research: Papers in Honor of Saul Gass’ 80th Birthday], vol. 36. Springer, 2006.

[15] M. Rezapour and D. der Naturwissenschaften, “Network design with facility location approximation and exact techniques,” 2015.

[16] T. Zhang, R. Ramakrishnan, and M. Livny, “Birch: An efficient data clustering method for very large databases,” in Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, ser. SIGMOD ’96. New York, NY, USA: Association for Computing Machinery, 1996, p. 103–114. [Online]. Available: https://doi.org/10.1145/233269.233324

[17] M. Ester, H.-P. Kriegel, J. Sander, and X. Xu, “A density-based algorithm for discovering clusters in large spatial databases with noise,” in Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, ser. KDD’96. AAAI Press, 1996, p. 226–231.

[18] “Dji website (2020), phantom 4 specifications.” [Online]. Available: https://www.dji.com/phantom-4-pro-v2/specs

[19] J. Zhang, J. F. Campbell, D. C. Sweeney II, and A. C. Hupman, “Energy consumption models for delivery drones: A comparison and assessment,” Transportation Research Part D: Transport and Environment, vol. 90, p. 102668, 2021. [Online]. Available: https: //www.sciencedirect.com/science/article/pii/S1361920920308531

[20] H. Mei et al., “Energy-efficient segment clustering algorithm for uav trajectory,” in 2022 IEEE International Conference on Communica-tions Workshops (ICC Workshops), 2022, pp. 1071–1076.

[21] M. Mozaffari, W. Saad, M. Bennis, and M. Debbah, “Mobile internet of things: Can uavs provide an energy-efficient mobile architecture?” in 2016 IEEE Global Communications Conference (GLOBECOM), 2016, pp. 1–6.

[22] A. Merwaday and I. Guvenc, “Uav assisted heterogeneous networks for public safety communications,” in 2015 IEEE Wireless Commu-nications and Networking Conference Workshops (WCNCW), 2015, pp. 329–334.