Deployment Optimization of Drone Base Stations in Cellular Networks

UAV-aided cellular coverage is anticipated to be an important part of future cellular networks due to a high demand of data and societies being more dependent on fast and reliable wireless internet coverage. However, there are still several concerns regarding operating a swarm of drones that needs to be addressed. A vital role in determining cost and risks of an operation is the specified number of drones and their locations. In this thesis, a framework, called Drone Location Problem (DLP), is proposed to optimize deployment of multiple drone base stations (DBS) for covering users. This framework includes two main stages in which the number of drones and their locations are optimized, respectively. DBSP-I is the first stage which is circle placement problem and DBSP-II is the second stage which is smallest enclosing circle problem. Since DBSP-I is a complex problem and it may require a long time to be solved optimally when the number of users are large, two heuristics are proposed to produce similar results in shorter time. These two heuristics are called KMDLP-I and KMDLP-II, respectively. KMDLP-I is uses k-means clustering algorithm to deploy drones for area coverage operation. However, since clustering algorithms suffer from local minima problems which is dependent on how clusters are initialized, two initialization methods were tested, k-means ++ and random. Moreover, KMDLP-II was developed which uses a bottom-up approach to improve the result obtained by KMDLP-I. Two classes of instances were created in order to investigate the effect of distribution of users in the region on execution time and number of deployed drones by heuristics. In the first class, users were distributed in a way to represent scenarios such as sports events and gatherings where they form clusters while in the second class of instances, users were distributed uniformly. Comprehensive experiments on instances with different numbers of users demonstrate that although DLP can find the optimal number of drones and their locations for instances with a up to 25 and 150 users for the first and second class of instances, it requires several hours to find an optimal solution when number of users increases and may not converge to optimality within 2 hours. Heuristics are shown to be more effective in terms of execution time and are able to solve instances with more than 120 users in a few seconds; however, the results obtained by them are not always the same as DLP. KMDLP-I is shown to perform very well on the first class of instances and produced results similar DLP. However, as the number of uniformly distributed users increases, the gap between number of deployed drones by DLP, and KMDLP-I increases. Experiments demonstrate that this problem can be mitigated and the gap between KMDLP I and DLP can be reduced when k-means ++ is used as it outperforms the random initialization methods in term of deploying a smaller number of drones on average. My experiments show that KMDLP-II methods improve the results even further by 10% compared to KMDLP-I. Also, they suggest that KMDLP-I or KMDLP-II can be used at the cost of utilizing more drones when it is critical to find a solution very fast like during a search and rescue mission or post disaster network restoration. On other hand, if enough time is available in advance to plan ahead for an operation, DLP framework should be used since it can find optimal number of drones and their location for providing cellular coverage regardless of how many users are in the region and how they are distributed.