NPO-BAND: Number and placement optimization for backhaul-aware UAV network deployment^✩

Abstract

In emergency communication scenarios, exploiting Unmanned Aerial Vehicles (UAVs) as relays to provide wireless communication services for ground users has emerged as a promising application. A key challenge in this resource-constrained application is deploying the minimum number of UAVs to form an aerial backhaul network to ensure coverage, which composes the Number and Placement Optimization for the Backhaul-Aware Network Deployment (NPO-BAND) problem. In this paper, we first formulate the NPO-BAND problem based on the geometric disk coverage model. Then, we propose a low-complexity heuristic method to solve this NP-hard problem. The proposed method contains a Very Important Point-Choosing (VIPC) strategy and a Backhaul-Aware Local Coverage (BALC) algorithm. Specifically, the VIPC strategy weighs up the backhaul connectivity constraint and the ground user coverage to choose the VIP, while the BALC algorithm solves the extended 1-center problem to determine the deployment location of each UAV. Simulation results show that the proposed method can effectively reduce the number of deployed UAVs, saving up to 25%-50% of that compared to existing methods across varying numbers and area sizes in clustered distribution patterns of ground users.

Keywords

Unmanned aerial vehicles / Multi-UAV network / Backhaul-aware deployment / Number optimization

CRediT authorship contribution statement

Sining Yang: Writing – review & editing, Writing – original draft, Visualization, Validation, Software, Resources, Methodology, Investigation, Conceptualization. Bo Zhang: Writing – review & editing, Supervision, Project administration, Funding acquisition, Formal analysis, Conceptualization. Jinshu Su: Writing – review & editing, Supervision, Project administration, Funding acquisition, Conceptualization.

Declaration of competing interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Acknowledgements

The research was supported by the Natural Science Foundation of China under Grant No. 91948303.

References

[1] M. Jaber, M.A. Imran, R. Tafazolli, A. Tukmanov, 5G backhaul challenges and emerging research directions: a survey, IEEE Access 4 (2017) 1743-1766.

[2] M.M. Ahamed, S. Faruque, 5G backhaul: requirements, challenges, and emerging technologies, in: Broadband Communications Networks: Recent Advances and Lessons from Practice, vol. 43, 2018, pp. 18-20.

[3] S.A.R. Naqvi, S.A. Hassan, H. Pervaiz, Q. Ni, Drone—aided communication as a key enabler for 5G and resilient public safety networks, IEEE Commun. Mag. 56 (1) (2018) 36-42.

[4] A. Otto, N. Agatz, J. Campbell, B. Golden, E. Pesch, Optimization approaches for civil applications of unmanned aerial vehicles or aerial drones: a survey, Networks 72 (4) (2018) 411-458.

[5] S. Hashima, Z.M. Fadlullah, M.M. Fouda, E.M. Mohamed, K. Hatano, B.M. El—Halawany, M. Guizani, On softwarization of intelligence in 6G networks for ultra—fast optimal policy selection: challenges and opportunities, IEEE Netw. 37 (2) (2022) 190-197.

[6] X. Li, Q. Tang, C. Sun, Energy—efficient link selection scheme in a two—hop relay scenario with considering a mobile relay, IET Commun. 9 (18) (2015) 2287-2292.

[7] G.S. Avellar, G.A. Pereira, L.C. Pimenta, P. Iscold, Multi—UAV routing for area coverage and remote sensing with minimum time, Sensors 15 (11) (2015) 27783-27803.

[8] J. Zhang, Z. Li, W. Xu, J. Peng, W. Liang, Z. Xu, X. Ren, X. Jia, Minimizing the number of deployed UAVs for delay—bounded data collection of iot devices, in: IEEE INFOCOM 2021—IEEE Conference on Computer Communications, IEEE, 2021, pp. 1-10.

[9] W. Xu, T. Xiao, J. Zhang, W. Liang, Z. Xu, X. Liu, X. Jia, S.K. Das, Minimizing the deployment cost of UAVs for delay—sensitive data collection in iot networks, IEEE/ACM Trans. Netw. 30 (2) (2021) 812-825.

[10] L. Yin, N. Zhang, C. Tang, On—demand UAV base station deployment for wireless service of crowded tourism areas, Pers. Ubiquitous Comput. 26 (4) (2022) 1137-1149.

[11] S. Sharafeddine, R. Islambouli, On—demand deployment of multiple aerial base stations for traffic offloading and network recovery, Comput. Netw. 156 (2019) 52-61.

[12] A. Sawalmeh, N.S. Othman, G. Liu, A. Khreishah, A. Alenezi, A. Alanazi, Power—efficient wireless coverage using minimum number of UAVs, Sensors 22 (1) (2021) 223.

[13] J. Lyu, Y. Zeng, R. Zhang, T.J. Lim, Placement optimization of UAV—mounted mobile base stations, IEEE Commun. Lett. 21 (3) (2017) 604-607.

[14] J. Qin, Z. Wei, C. Qiu, Z. Feng, Edge—prior placement algorithm for UAV—mounted base stations, in: 2019 IEEE Wireless Communications and Networking Conference (WCNC), IEEE, 2019, pp. 1-6.

[15] E. Catté, M. Sana, M. Maman, Cost—efficient and qos—aware user association and 3d placement of 6G aerial mobile access points, in: 2022 Joint European Conference on Networks and Communications & 6G Summit (EuCNC/6G Summit), IEEE, 2022, pp. 357-362.

[16] H. Zhao, H. Wang, W. Wu, J. Wei, Deployment algorithms for UAV airborne networks toward on—demand coverage, IEEE J. Sel. Areas Commun. 36 (9) (2018) 2015-2031.

[17] J. Sabzehali, V.K. Shah, Q. Fan, B. Choudhury, L. Liu, J.H. Reed, Optimizing number, placement, and backhaul connectivity of multi—UAV networks, IEEE Int. Things J. 9 (21) (2022) 21548-21560.

[18] P. Ladosz, H. Oh, G. Zheng, W.—H. Chen, A hybrid approach of learning and model—based channel prediction for communication relay UAVs in dynamic urban environments, IEEE Robot. Autom. Lett. 4 (3) (2019) 2370-2377.

[19] U. Challita, W. Saad, Network formation in the sky: unmanned aerial vehicles for multi—hop wireless backhauling, in: GLOBECOM 2017—2017 IEEE Global Communications Conference, IEEE, 2017, pp. 1-6.

[20] P. Foroughi, H. Beyranvand, M. Gagnaire, S.A. Zahr, User association in hybrid UAV—cellular networks for massive real—time iot applications, in: IEEE INFOCOM 2020 — IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), 2020, pp. 243-248.

[21] J. Chen, D. Gesbert, Efficient local map search algorithms for the placement of flying relays, IEEE Trans. Wirel. Commun. 19 (2) (2019) 1305-1319.

[22] A. Al—Hourani, S. Kandeepan, S. Lardner, Optimal lap altitude for maximum coverage, Wirel. Commun. Lett. IEEE 3 (6) (2014) 569-572.

[23] A. Srinivas, G. Zussman, E. Modiano, Construction and maintenance of wireless mobile backbone networks, IEEE/ACM Trans. Netw. 17 (1) (2009) 239-252.

[24] P.K. Agarwal, C.M. Procopiuc, Exact and approximation algorithms for clustering, Algorithmica 33 (2) (2002) 201-226.

[25] N. Megiddo, Linear—time algorithms for linear programming in r³ and related problems , SIAM J. Comput. 12 (4) (1983) 759-776.

[26] J. Nocedal, S.J. Wright, Numerical Optimization, Springer, 1999.

[27] A. ITU, Propagation Data and Prediction Methods for the Design of Terrestrial Broadband Millimetric Radio Access Systems, 2003.

[28] L. Zhou, H. Mao, X. Deng, J. Zhang, H. Zhao, J. Wei, Real—time radio map construction and distribution for UAV—assisted mobile edge computing networks, IEEE Int. Things J. 11 (12) (2024) 21337-21346.

[29] Y. Li, H. Ma, L. Wang, S. Mao, G. Wang, Optimized content caching and user association for edge computing in densely deployed heterogeneous networks, IEEE Trans. Mob. Comput. 21 (6) (2020) 2130-2142.

[30] V.K. Shah, S. Roy, S. Silvestri, S.K. Das, Ctr: cluster based topological routing for disaster response networks, in: 2017 IEEE International Conference on Communications (ICC), IEEE, 2017, pp. 1-6.

[31] V.K. Shah, S. Silvestri, B. Luciano, S.K. Das, X—chant: a diverse dsa based architecture for next—generation challenged networks, in: IEEE INFOCOM 2019—IEEE Conference on Computer Communications, IEEE, 2019, pp. 586-594.