The amount of internet traffic generated during mass public events is significantly growing in a way that requires methods to increase the overall performance of the wireless network service. Recently, legacy methods in form of mobile cell sites, frequently called cells on wheels, were used. However, modern technologies are allowing the use of unmanned aerial vehicles (UAV) as a platform for network service extension instead of ground-based techniques. This results in the development of flying base stations (FBS) where the number of deployed FBSs depends on the demanded network capacity and specific user requirements. Large-scale events, such as outdoor music festivals or sporting competitions, requiring deployment of more than one FBS need a method to optimally distribute these aerial vehicles to achieve high capacity and minimize the cost. In this paper, we present a mathematical model for FBS deployment in large-scale scenarios. The model is based on a location set covering problem and the goal is to minimize the number of FBSs by finding their optimal locations. It is restricted by users' throughput requirements and FBSs' available throughput, also, all users that require connectivity must be served. Two meta-heuristic algorithms (cuckoo search and differential evolution) were implemented and verified on a real example of a music festival scenario. The results show that both algorithms are capable of finding a solution. The major difference is in the performance where differential evolution solves the problem six to eight times faster, thus it is more suitable for repetitive calculation. The obtained results can be used in commercial scenarios similar to the one used in this paper where providing sufficient connectivity is crucial for good user experience. The designed algorithms will serve for the network infrastructure design and for assessing the costs and feasibility of the use-case.

Department of Telecommunications Faculty of Electrical Engineering and Communication Brno University of Technology Technicka 12 616 00 Brno Czech Republic

Institute of Automation and Computer Science Brno University of Technology Technicka 2 616 69 Brno Czech Republic

Unit of Electrical Engineering Tampere University Korkeakoulunkatu 7 337 20 Tampere Finland

Zobrazit více v PubMed

Gerasimenko M., Pokorny J., Schneider T., Sirjov J., Andreev S., Hosek J. Prototyping Directional UAV-Based Wireless Access and Backhaul Systems; Proceedings of the 2019 IEEE Global Communications Conference (GLOBECOM); Big Island, HI, USA. 9–13 December 2019; Piscataway, NJ, USA: IEEE; 2019. pp. 1–6.

Wolpert D.H., Macready W.G. No free lunch theorems for optimization. IEEE Trans. Evol. Comput. 1997;1:67–82. doi: 10.1109/4235.585893. DOI

Kritter J., Brévilliers M., Lepagnot J., Idoumghar L. On the optimal placement of cameras for surveillance and the underlying set cover problem. Appl. Soft Comput. 2019;74:133–153. doi: 10.1016/j.asoc.2018.10.025. DOI

Shanthasheela A., Shanmugavadivu P. Cuckoo Search Based Forest Cover Classification. J. Comput. Theor. Nanosci. 2019;16:3550–3553. doi: 10.1166/jctn.2019.8322. DOI

Sadeghi F., Avokh A. Load-balanced data gathering in Internet of Things using an energy-aware cuckoo-search algorithm. Int. J. Commun. Syst. 2020;33:e4385. doi: 10.1002/dac.4385. DOI

Zhang Y., Yu Y., Zhang S., Luo Y., Zhang L. Ant colony optimization for Cuckoo Search algorithm for permutation flow shop scheduling problem. Syst. Sci. Control. Eng. 2019;7:20–27. doi: 10.1080/21642583.2018.1555063. DOI

Thirugnanasambandam K., Prakash S., Subramanian V., Pothula S., Thirumal V. Reinforced cuckoo search algorithm-based multimodal optimization. Appl. Intell. 2019;49:2059–2083. doi: 10.1007/s10489-018-1355-3. DOI

Cai X., Niu Y., Geng S., Zhang J., Cui Z., Li J., Chen J. An under-sampled software defect prediction method based on hybrid multi-objective cuckoo search. Concurr. Comput. Pract. Exp. 2020;32:e5478. doi: 10.1002/cpe.5478. DOI

Fotouhi A., Ding M., Hassan M. Service on demand: Drone base stations cruising in the cellular network; Proceedings of the 2017 IEEE Globecom Workshops (GC Wkshps); Singapore. 4–8 December 2017; Piscataway, NJ, USA: IEEE; 2017. pp. 1–6.

Fotouhi A., Ding M., Hassan M. Flying drone base stations for macro hotspots. IEEE Access. 2018;6:19530–19539. doi: 10.1109/ACCESS.2018.2817799. DOI

Mignardi S., Verdone R. On the performance improvement of a cellular network supported by an unmanned aerial base station; Proceedings of the 2017 29th International Teletraffic Congress (ITC 29); Genoa, Italy. 4–8 September 2017; Piscataway, NJ, USA: IEEE; 2017. pp. 7–12.

Huang S., Teo R.S.H., Leong W.L., Martinel N., Forest G.L., Micheloni C. Coverage Control of Multi-Unmanned Aerial Vehicles: A Short Review. Unmanned Syst. 2018;6:1–14.

Cicek C.T., Gultekin H., Tavli B., Yanikomeroglu H. UAV base station location optimization for next generation wireless networks: Overview and future research directions; Proceedings of the 2019 1st International Conference on Unmanned Vehicle Systems-Oman (UVS); Muscat, Oman. 5–7 February 2019; Piscataway, NJ, USA: IEEE; 2019. pp. 1–6.

Storn R., Price K. Differential evolution—A simple and efficient heuristic for global optimization over continuous spaces. J. Glob. Optim. 1997;11:341–359. doi: 10.1023/A:1008202821328. DOI

Gonzalez V., Monje C.A., Garrido S., Moreno L., Balaguer C. Coverage Mission for UAVs Using Differential Evolution and Fast Marching Square Methods. IEEE Aerosp. Electron. Syst. Mag. 2020;35:18–29. doi: 10.1109/MAES.2020.2966317. DOI

Wang Z., Liu R., Liu Q., Thompson J.S., Kadoch M. Energy Efficient Data Collection and Device Positioning in UAV-Assisted IoT. IEEE Internet Things J. 2019;7:1122–1139. doi: 10.1109/JIOT.2019.2952364. DOI

Adhikari D., Kim E., Reza H. A fuzzy adaptive differential evolution for multi-objective 3D UAV path optimization; Proceedings of the 2017 IEEE Congress on Evolutionary Computation (CEC); San Sebastián, Spain. 5–8 June 2017; Piscataway, NJ, USA: IEEE; 2017. pp. 2258–2265.

Yang X.S., Deb S. Cuckoo search via Lévy flights; Proceedings of the 2009 World Congress on Nature & Biologically Inspired Computing (NaBIC); Coimbatore, India. 9–11 December 2009; Piscataway, NJ, USA: IEEE; 2009. pp. 210–214.

Zhang Y.Z., Li H., Ma Y.H., Zhang J.D., He J.L. Cooperative reconnaissance mission planning for heterogeneous UAVs with DCSA; Proceedings of the 2019 IEEE 15th International Conference on Control and Automation (ICCA); Edinburgh, UK. 16–19 July 2019; Piscataway, NJ, USA: IEEE; 2019. pp. 417–422.

Zhu K., Xu X., Han S. Energy-efficient UAV trajectory planning for data collection and computation in mMTC networks; Proceedings of the 2018 IEEE Globecom Workshops (GC Wkshps); Abu Dhabi, UAE. 9–13 December 2018; Piscataway, NJ, USA: IEEE; 2018. pp. 1–6.

Góez-Sánchez G.D., Jaramillo-Garzón J.A., Velásquez R.A. Performance comparison of particle swarm optimization and Cuckoo search for online route planning. IEEE Aerosp. Electron. Syst. Mag. 2018;33:40–50. doi: 10.1109/MAES.2018.170116. DOI

Zhang S., Sun X., Ansari N. Placing multiple drone base stations in hotspots; Proceedings of the 2018 IEEE 39th Sarnoff Symposium; Newark, NJ, USA. 24–25 September 2018; Piscataway, NJ, USA: IEEE; 2018. pp. 1–6.

Qin J., Wei Z., Qiu C., Feng Z. Edge-Prior Placement Algorithm for UAV-Mounted Base Stations; Proceedings of the 2019 IEEE Wireless Communications and Networking Conference (WCNC); Marrakech, Morocco. 15–18 April 2019; Piscataway, NJ, USA: IEEE; 2019. pp. 1–6.

Wang H., Zhao H., Wu W., Xiong J., Ma D., Wei J. Deployment algorithms of flying base stations: 5G and beyond with UAVs. IEEE Internet Things J. 2019;6:10009–10027. doi: 10.1109/JIOT.2019.2935105. DOI

Sivalingam T., Manosha K.S., Rajatheva N., Latva-aho M., Dissanayake M.B. Positioning of Multiple Unmanned Aerial Vehicle Base Stations in future Wireless Network; Proceedings of the 2020 IEEE 91st Vehicular Technology Conference (VTC2020-Spring); Antwerp, Belgium. 25–28 May 2020; Piscataway, NJ, USA: IEEE; 2020. pp. 1–6.

Zhao H., Wang H., Wu W., Wei J. Deployment algorithms for UAV airborne networks toward on-demand coverage. IEEE J. Sel. Areas Commun. 2018;36:2015–2031. doi: 10.1109/JSAC.2018.2864376. DOI

Chen Y., Li N., Wang C., Xie W., Xv J. A 3D placement of unmanned aerial vehicle base station based on multi-population genetic algorithm for maximizing users with different QoS requirements; Proceedings of the 2018 IEEE 18th International Conference on Communication Technology (ICCT); Chongqing, China. 8–11 October 2018; Piscataway, NJ, USA: IEEE; 2018. pp. 967–972.

Sun J., Masouros C. Deployment strategies of multiple aerial BSs for user coverage and power efficiency maximization. IEEE Trans. Commun. 2018;67:2981–2994. doi: 10.1109/TCOMM.2018.2889460. DOI

Lai C.C., Chen C.T., Wang L.C. On-demand density-aware UAV base station 3D placement for arbitrarily distributed users with guaranteed data rates. IEEE Wirel. Commun. Lett. 2019;8:913–916. doi: 10.1109/LWC.2019.2899599. DOI

Adam N., Tapparello C., Heinzelman W., Yanikomeroglu H. Placement optimization of multiple UAV base stations; Proceedings of the 2021 IEEE Wireless Communications and Networking Conference (WCNC); Nanjing, China. 29 March 2021; Piscataway, NJ, USA: IEEE; 2021. pp. 1–7.

Becvar Z., Mach P., Plachy J., de Tudela M.F.P. Positioning of Flying Base Stations to Optimize Throughput and Energy Consumption of Mobile Devices; Proceedings of the 2019 IEEE 89th Vehicular Technology Conference (VTC2019-Spring); Kuala Lumpur, Malaysia. 28 April–1 May 2019; Piscataway, NJ, USA: IEEE; 2019. pp. 1–7.

Li J., Lu D., Zhang G., Tian J., Pang Y. Post-Disaster Unmanned Aerial Vehicle Base Station Deployment Method Based on Artificial Bee Colony Algorithm. IEEE Access. 2019;7:168327–168336. doi: 10.1109/ACCESS.2019.2954332. DOI

Hydher H., Jayakody D.N.K., Hemachandra K.T., Samarasinghe T. Intelligent UAV deployment for a disaster-resilient wireless network. Sensors. 2020;20:6140. doi: 10.3390/s20216140. PubMed DOI PMC

ReVelle C., Toregas C., Falkson L. Applications of the location set-covering problem. Geogr. Anal. 1976;8:65–76. doi: 10.1111/j.1538-4632.1976.tb00529.x. DOI

Church R., ReVelle C. The maximal covering location problem. Pap. Reg. Sci. 1974;32:101–118. doi: 10.1007/BF01942293. DOI

Current J.R., Storbeck J.E. Capacitated covering models. Environ. Plan. B Plan. Des. 1988;15:153–163. doi: 10.1068/b150153. DOI

Gerrard R.A. Ph.D. Thesis. University of California; Santa Barbara, CA, USA: 1995. The Location of Service Facilities Using Models Sensitive to Response Distance, Facility Workload, and Demand Allocation.

Seda P., Seda M., Hosek J. On Mathematical Modelling of Automated Coverage Optimization in Wireless 5G and beyond Deployments. Appl. Sci. 2020;10:8853. doi: 10.3390/app10248853. DOI

Plane D.R., Hendrick T.E. Mathematical programming and the location of fire companies for the Denver fire department. Oper. Res. 1977;25:563–578. doi: 10.1287/opre.25.4.563. DOI

Murray A.T. Optimising the spatial location of urban fire stations. Fire Saf. J. 2013;62:64–71. doi: 10.1016/j.firesaf.2013.03.002. DOI

Chauhan D., Unnikrishnan A., Figliozzi M. Maximum coverage capacitated facility location problem with range constrained drones. Transp. Res. Part C Emerg. Technol. 2019;99:1–18. doi: 10.1016/j.trc.2018.12.001. DOI

Church R.L., Gerrard R.A. The multi-level location set covering model. Geogr. Anal. 2003;35:277–289. doi: 10.1111/j.1538-4632.2003.tb01115.x. DOI

Yang W., Yang H., Tang S. Optimization and control application of sensor placement in aeroservoelastic of UAV. Aerosp. Sci. Technol. 2019;85:61–74. doi: 10.1016/j.ast.2018.11.050. DOI

Song P.C., Pan J.S., Chu S.C. A parallel compact cuckoo search algorithm for three-dimensional path planning. Appl. Soft Comput. 2020;94:106443. doi: 10.1016/j.asoc.2020.106443. DOI

Huang P.Q., Wang Y., Wang K., Yang K. Differential Evolution With a Variable Population Size for Deployment Optimization in a UAV-Assisted IoT Data Collection System. IEEE Trans. Emerg. Top. Comput. Intell. 2019;4:324–335. doi: 10.1109/TETCI.2019.2939373. DOI

Alliance N. Radio access performance evaluation methodology. NGMN White Pap. 2008;1:36.

Rochim A.F., Harijadi B., Purbanugraha Y.P., Fuad S., Nugroho K.A. Performance comparison of wireless protocol IEEE 802; 11 ax vs 802.11 ac. In Proceedings of the 2020 International Conference on Smart Technology and Applications (ICoSTA); Surabaya, Indonesia. 20 February 2020; Piscataway, NJ, USA: IEEE; 2020. pp. 1–5.

Zhu X., Doufexi A., Kocak T. Throughput and coverage performance for IEEE 802.11 ad millimeter-wave WPANs; Proceedings of the 2011 IEEE 73rd Vehicular Technology Conference (VTC Spring); Budapest, Hungary. 15–18 May 2011; Piscataway, NJ, USA: IEEE; 2011. pp. 1–5.

3GPP . Requirements for Further Advancements for Evolved Universal Terrestrial Radio Access (E-UTRA) (LTE-Advanced) 3rd Generation Partnership Project (3GPP); Valbonne, France: 2018. Technical Report (TR) 36.913; Version 15.0.0.

Hornyák J., Skřivánek P., Mikuláštík K., Radek Z. Interactive Map of Deployed BTS in Czech Republic. [(accessed on 30 June 2021)]; Available online: http://gsmweb.cz/