# 3D Deployment of Unmanned Aerial Vehicle-Base Station Assisting Ground-Base Station

Authors: Khaled F. Hayajneh; Khaled Bani-Hani; Hazim Shakhatreh; Muhammad Anan; Ahmad Sawalmeh
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

Unmanned aerial vehicles (UAVs), also named as drones, have become a modern model to provide a quick wireless communication infrastructure. They have been used when conventional base stations’ capacity is suffering in some extreme cases such as congestion inside the cell or a special event. This paper proposes an efficient three-dimension (3D) placement of a single UAV-assisted wireless network in such cases. Our proposed model assists the ground base station (GBS) using the UAV to serve arbitrary distributed users considering the impact of the obstacle blockage over the well-known air-to-ground (A2G) path model. This work is aimed at optimizing the percentage of available bandwidth that must be provided to the UAV in order to maximize the number of served users. In addition, it finds the 3D placement of the UAV base station (UAVBS) that maximizes the number of served users, each with maximum quality-of-service (QoS). The exhaustive search and particle swarm optimization (PSO) algorithms are used to find the problem’s solution.


---

## Body

## 1. Introduction

The evolution of UAVs, commonly known as drones or network flying platforms (NFPs), is a key to enhance wireless communications because of their high coverage, promising rates, low cost, high mobility, adjustable height, and flexible installation. As a result, UAVs are enablers of a wide range of applications including, but not limited to, telecommunications, delivering supplies, rescue operations, surveillance, and monitoring [1, 2].UAVs can operate in wireless networks in different scenarios. On the one side, they are used as aerial base stations to assist the ground base stations in improving the connectivity, coverage, and capacity, especially in case of an extreme event, such as congestion inside the cell or big events (i.e., festival and sport events). On the other side, UAVs can function as aerial user equipment such as carrier aircraft or surveillance drones [3].Compared to typically static GBSs that are published at fixed locations, UAV-assisted communications has the following major advantages. First, UAVBSs can be hurriedly deployed based on demand, such as temporary or unexpected events. Second, they provide high reliable links for communication due to their high altitude above the ground. UAVBSs are more likely to have line-of-sight (LoS) connections with their ground users as compared with terrestrial counterparts. Third, regarding the high mobility of UAVs, UAVBSs own an additional degree of freedom (DoF) to adjust their locations in 3D which enhances communication performance [2, 4]. In this work, the UAV is considered as an aerial base station.The UAVBS coverage advantage is higher than that for the GBS because it has a higher operating altitude. On the one hand, if the altitude of a UAVBS increases, the path loss will increase and the probability of getting LoS links between UAVBS and users will increase. On the other hand, if the altitude of a UAVBS decreases, the path loss will decrease and the probability of getting LoS links between UAVBS and users will decrease [5]. Thus, it is likely to improve the networks’ performance that is served by traditional GBS and UAVBS collectively.A user might be under the coverage of a GBS without getting service from it due to a lack of bandwidth resources and congestion in the network. Such a problem attracts designers to employ UAVs for assisting GBS to get service for the users.In this work with considering the coexistence of ground cellular systems (i.e., GBS with UAVBS together), we investigate how to deploy and determine the 3D location for the UAVBS and optimize the bandwidth allocation between GBS and UAVBS to maximize the number of served users with maximum quality of service (QoS). Despite the number of researches works on UAVBS deployment, for the best of our knowledge, neither work has been done that focused on deploying a UAVBS with a coexistence GBS collectively nor optimizing the bandwidth allocation between GBS and UAVBS that serve the maximum number of arbitrarily distributed users with a maximum QoS. Therefore, this motivates us to investigate this problem. The main contributions of this work are as follows:(1)
We employ a terrestrial communication model and an air-to-ground (A2G) communication model to serve users in a coexistence system. In [?], there is a motivation for selecting an air-to-ground communication model. Due to the high probability of having LoS links, the blocked users from GBS, due to obstacles, can be served. However, when increasing the distance between UAV and receivers, the PL increases. Therefore, the optimum altitude for the UAV should be found(2)
We use the proposed model (i.e., GBS and UAVBS) in order to maximize the number of served users with maximum QoS, according to the unusual events, considering different frequency bands to prevent interference(3)
We study the efficient 3D placement problem for a single UAVBS and solve it by searching exhaustively and using the PSO algorithm to minimize the computational effort(4)
We use exhaustive search and PSO algorithms to optimize the portion of the available bandwidth that must be provided to the UAVBS and GBS


## 2. Related Works

A crucial fundamental issue for designing UAV-aided wireless networks is establishing an A2G channel model since it is essential to have accurate models for efficient use of aerial devices [6]. Recently, statistical modeling methods are utilized to derive path loss expressions in many studies [7–9]. In such studies, the model presented by Al-Hourani et al. is widely used in the literature [7]. In their work, the A2G path loss model for low altitude platforms, including the drone-cells model, has been evolved. A closed-form expression of the A2G path loss model is proposed since the possibilities of LoS and non-line-of-sight (NLoS) links in different scenarios are considered, and the aerial platform ideal height that maximizes the coverage is presented. In their extension work, drone-to-BS (D2B) path loss model is formulated for a suburban scenario based on massive field experiments data [10].One of the significant issues in deploying UAVBSs is finding their 3D placements. Some recent work concentrated on locating the UAVBS in 3D in wireless networks. For example, Bor-Yaliniz et al. suggest using a UAVBS to maximize the network’s revenue [11]. The authors propose a 3D placement problem to maximize the covered users in an area that guarantees a certain path loss threshold. By considering the user’s mobility, they extend their work in [12]. They jointly optimized the 3D location of a UAVBS and the resources offered to each user in order to move to a position with better coverage. Also, Alzenad et al. propose an algorithm to find the UAVBS location that maximizes the number of served users is proposed in [13] and then extended to different QoS requirements in [14]. Specifically, the authors decouple the problem into vertical and horizontal dimensions [13]. For the vertical dimension, the optimum angle and height that maximize the coverage radius are found. In the horizontal dimension, the deployment problem is solved using a circle placement problem. Considering the different QoS requirements, represented by the signal-to-noise ratio (SNR), the approximated optimum height is found numerically via exhaustive search [14]. The heuristic algorithms, such as PSO, are used to reduce the computational difficulties discussed in previous studies with the slightest agreement of the best possible solution [15, 16]. Recently, Shakhatreh et al. propose an efficient 3D placement algorithm for a single UAVBS based on a realistic outdoor-indoor path loss model for users which are distributed inside elevated buildings [17, 18]. The authors find a valid 3D UAV position that minimized the total transmission power when the number of indoor users is equal in each floor, and they have a uniform distribution.Different works expanded the research to multiple UAVBSs. A unique feature of these studies is whether “2D-placement” or “3D-placement” is taken into account. Here, the 3D placement has been studied in [19–24], while the 2D-placement, with fixed altitude, has been studied in [25–28].Using UAVBS to assist GBS is used in modern networks LTE, 5G. Such system is capable of serving traffic with dynamic demands [29]. However, there are several kinds of literary works on UAV deployment. The kinds of drones-assisted ground communications infrastructure have remained scarcely studied so far. Shah et al. propose a distributed algorithm that associates small ground BSs along with UAVBSs to maximize the overall sum rate [30]. Besides, Kalantari et al. optimize the 3D placement of multiple UAVBSs to find the minimum number of UAVBSs so that all users are served [19]. Lai et al. discuss employing multiple UAVBSs cooperating with the terrestrial BSs [31]. The data-driven 3D placement algorithm is proposed to find the proper number, position, height, and coverage of each UAVBS to ameliorate the system sum rate. Sun and Ansari suggest an algorithm to optimize the altitude and user association of the UAVBS jointly to maximize the spectral efficiency of the hot spot area [32]. In addition, the cooperative decode-and-forward (DF) protocol is proposed in which multiple UAVBSs cooperate with macro-BS (MBS) to assist the terminals simultaneously in [33], where the optimal location of UAVBS is studied by formulating the best resource allocations for both hops, simultaneously (i.e., MBS and UAVBS resource allocations). In trajectory optimization algorithms, UAVBS follows a trajectory instead of hovering at an optimal location to serve the users in a given area [34, 35]. Tran et al. investigate the UAV-assisted IoT network by jointly optimizing the UAV trajectory and allocated bandwidth where the total throughput is maximized [34]. Besides, they minimize the total energy consumption by jointly optimizing the UAV trajectory and velocity [35].To the best of our knowledge, considering a coexistence cellular system, employing GBS and UAVBS collectively and trying to serve the maximum number of users that are arbitrarily distributed, has not been addressed.In this work, we discuss how to improve the performance of the wireless network by considering a coexistence of ground cellular systems, such as GBS and UAVBS, in an extreme event (i.e., congestion inside the cell) to find the optimal UAVBS’s location so that the number of served users with maximum QoS is maximized.


## 3. System Model

We consider an urban area served by a GBS that is assisted by a rotary-wing UAVBS (e.g., quadrotor drone) with a fixed transmission power. The location of GBSxg,yg,hg is in the center of the region, and the location of UAVBS is represented by xd,yd,hd, as shown in Figure 1. The xg,yg represents the 2D location of GBS while hg represents the GBS height (i.e., tower height). Similarly, the xd,yd represents the 2D location of UAVBS while hd represents the UAVBS height (i.e., drone height).Figure 1
A single UAVBS-assisted cellular network. The network consists of a single GBS located at the center, a single UAVBS, a mobile switching center (MSC) as backhaul for GBS and UAVBS, and multiple ground users.The UAVBS can move freely in space, but its altitudehd is bounded within a range of (hmin≤hd≤hmax), which rely on the UAV’s capabilities and domestic law restriction.We assume thatNu is the total number of users in the predesigned area. The users are assumed to be arbitrarily distributed on the ground due to unpredictable demand, such as special events (i.e., festival and stadium). The location of each user, ui, i∈1,2,⋯Nu, is represented by xi,yi,hu. The decision of UAVBS placement is controlled by a center around the GBS. A user ui can be served if the QoS, measured by the SNR, is above a predefined threshold.In this work, the BSs (both GBS and UAVBS) have transceiver antennas, and a downlink scenario is assumed, where the frequency division multiple access (FDMA) technique is adopted to transmit data and provide coverage for ground users. Therefore, each user has its dedicated channel for communication as well as there is neither interference nor overlap between GBS and UAVBS channels. Assuming that the GBS and UAVBS provide different bandwidthBj, j∈1,2 for the downlinks in the proposed scenario (i.e., B1 and B2 are the bandwidths provided to the GBS and UAVBS, respectively).We consider that the backhaul for UAVBS is a microwave connection. Whereas the backhaul in GBS is the traditional backhaul (i.e., either fiber or microwave connections).In deploying UAVBS, the maximum benefit can be achieved by determining the optimum 3D placement of UAVBS (xd,yd,hd). Assuming a fixed QoS for all users, the maximum benefit can be obtained by associating the maximum number of users to the UAVBS. The placement of the UAVBS affects both the number of users inside its coverage region and the quality of the channel between each user and the UAVBS.In our scenario, there are two types of channels: UAVBS to ground-user channel and GBS to ground-user channel. Note that we can also consider two other channels: mobile switching center (MSC) to GBS channel and MSC to UAVBS channel. However, considering such channels is outscope of our work in this work. Next, we discuss two different types of communication channels that are used in this proposed model.


### 3.1. UAVBS to Ground-User Channel

We adopt the air-to-ground channel model, A2G, that was proposed by Al-Hourani et al., which is the most well-known radio propagation model for downlink communication between UAV and ground users [7]. In general, it depends on the LoS and NLoS links and their probability of occurrence separately.The A2G channel model considers two propagation groups: LoS propagation and NLoS propagation. Unlike LoS, NLoS signals suffer from much stronger reflections and diffractions. The probability of getting a LoS signalPLoS, which is based on the environment and the deploying the UAVBS, can be formulated as follows [7].
(1)PLoS=11+αexp−βθ−α,whereα and β are constants and their values rely on the environment such as rural area, urban area, etc. Also, θ=arctanhd/rd,i is the elevation angle from the UAVBS to the user ui, hd is the UAVBS altitude, and rd,i is the horizontal distance between the UAVBS and the user ui which it is given by:
(2)rd,i=xd−xi2+yd−yi2+hd−hu2,wherehu is the user’s height and it is constant in our proposed model and equals 1.5m. Thus, the probability of getting a NLoS signal, PNLoS, is given by:
(3)PNLoS=1−PLoS.In particular, there is a trade-off between UAVBS altitude,hd, and the PNLoS. Generally, as the altitude increases, the probability of getting a LoS channel becomes higher, and the PL will increase since the distance increases. Conversely, if the UAV has a lower altitude, the distance will decrease, and the probability of having a LoS channel is lower due to ground obstacles. Therefore, there is an optimal altitude for UAVBS. For instance, at a coverage radius of rd=1000 m, the optimal UAVBS altitude is hd=600 m, where the PL=101 dB is minimal, as shown in Figure 2.Figure 2
Optimal altitude of UAVBS with minimumPL over different horizontal distances (rd) in an urban area scenario.In this model, the total average path loss, considering the LoS and NLoS links, can be calculated as follows [7].
(4)PLhd,rd,idB=10nlog4πfcdi,2c+PLoSζLoS+1−PLoSζNLoS,where the first term represents the free-space path loss (FSPL), wherefc is the carrier frequency, c is the speed of light, n is the PL exponent (i.e., (2≤n≤4) depending on the environment), and the 3D distance di,2=rd,i2+hd−hu2 between the UAVBS and the user ui. Besides, ζLoS and ζNLoS are the average additional losses for LoS and NLoS links in dB, respectively, which are environment-dependent. We effectively create and solve 3D placement problem to achieve maximum number of users within the required area.The received power of userui served by the UAVBS is given by
(5)Pri,2dBm=PUAVdBm−PLhd,rd,idB,wherePUAV is the transmitted power by UAVBS in dBm, PLhd,rd,i is the total average path loss in dB, as shown in Eq. (4).


### 3.2. GBS to Ground-User Channel

In an urban area, we use the independent Rayleigh fading model in order to describe the time varying channel between the GBS and a userui [36, 37]. This time variation arises when the state of obstacles between the transmitter and the receiver is unpredictable due to the obstacles’ movement. Thus, one can notice changes in the amplitudes, delays, and the number of multipath components corresponding to each signal. These changes result a constructive and a destructive addition of multipath components over a much larger time scale.The received power of userui served by the GBS is given as:
(6)Pri,1dBm=PGBSdBm+20loggi−10nlogdi,1,wherePGBS is the transmitted power by GBS in dBm, gi is the Rayleigh fading power for the user ui in dB, and di,1 is the distance between the GBS and the user ui which it is given by:
(7)di,1=xg−xi2+yg−yi2+hg−hu2.However, the proposed work can be applied to different environments where we need to change the parameters of the A2G model as well as the model between the GBS and the users.


## 3.1. UAVBS to Ground-User Channel

We adopt the air-to-ground channel model, A2G, that was proposed by Al-Hourani et al., which is the most well-known radio propagation model for downlink communication between UAV and ground users [7]. In general, it depends on the LoS and NLoS links and their probability of occurrence separately.The A2G channel model considers two propagation groups: LoS propagation and NLoS propagation. Unlike LoS, NLoS signals suffer from much stronger reflections and diffractions. The probability of getting a LoS signalPLoS, which is based on the environment and the deploying the UAVBS, can be formulated as follows [7].
(1)PLoS=11+αexp−βθ−α,whereα and β are constants and their values rely on the environment such as rural area, urban area, etc. Also, θ=arctanhd/rd,i is the elevation angle from the UAVBS to the user ui, hd is the UAVBS altitude, and rd,i is the horizontal distance between the UAVBS and the user ui which it is given by:
(2)rd,i=xd−xi2+yd−yi2+hd−hu2,wherehu is the user’s height and it is constant in our proposed model and equals 1.5m. Thus, the probability of getting a NLoS signal, PNLoS, is given by:
(3)PNLoS=1−PLoS.In particular, there is a trade-off between UAVBS altitude,hd, and the PNLoS. Generally, as the altitude increases, the probability of getting a LoS channel becomes higher, and the PL will increase since the distance increases. Conversely, if the UAV has a lower altitude, the distance will decrease, and the probability of having a LoS channel is lower due to ground obstacles. Therefore, there is an optimal altitude for UAVBS. For instance, at a coverage radius of rd=1000 m, the optimal UAVBS altitude is hd=600 m, where the PL=101 dB is minimal, as shown in Figure 2.Figure 2
Optimal altitude of UAVBS with minimumPL over different horizontal distances (rd) in an urban area scenario.In this model, the total average path loss, considering the LoS and NLoS links, can be calculated as follows [7].
(4)PLhd,rd,idB=10nlog4πfcdi,2c+PLoSζLoS+1−PLoSζNLoS,where the first term represents the free-space path loss (FSPL), wherefc is the carrier frequency, c is the speed of light, n is the PL exponent (i.e., (2≤n≤4) depending on the environment), and the 3D distance di,2=rd,i2+hd−hu2 between the UAVBS and the user ui. Besides, ζLoS and ζNLoS are the average additional losses for LoS and NLoS links in dB, respectively, which are environment-dependent. We effectively create and solve 3D placement problem to achieve maximum number of users within the required area.The received power of userui served by the UAVBS is given by
(5)Pri,2dBm=PUAVdBm−PLhd,rd,idB,wherePUAV is the transmitted power by UAVBS in dBm, PLhd,rd,i is the total average path loss in dB, as shown in Eq. (4).


## 3.2. GBS to Ground-User Channel

In an urban area, we use the independent Rayleigh fading model in order to describe the time varying channel between the GBS and a userui [36, 37]. This time variation arises when the state of obstacles between the transmitter and the receiver is unpredictable due to the obstacles’ movement. Thus, one can notice changes in the amplitudes, delays, and the number of multipath components corresponding to each signal. These changes result a constructive and a destructive addition of multipath components over a much larger time scale.The received power of userui served by the GBS is given as:
(6)Pri,1dBm=PGBSdBm+20loggi−10nlogdi,1,wherePGBS is the transmitted power by GBS in dBm, gi is the Rayleigh fading power for the user ui in dB, and di,1 is the distance between the GBS and the user ui which it is given by:
(7)di,1=xg−xi2+yg−yi2+hg−hu2.However, the proposed work can be applied to different environments where we need to change the parameters of the A2G model as well as the model between the GBS and the users.


## 4. Problem Formulation

The received SNR (γi,j) of the user ui on the ground is formed as:
(8)γi,j=Pri,jN,i=1,2,..Nuandj=1,2,wherePri,j is the received power (in watt) at user ui from j−th BS (i.e., j∈1,2, j=1 if the received power is transmitted from GBS and j=2 if the received power is transmitted from UAVBS). N is the channel noise power in watt, which is calculated by:
(9)N=Nobi,j,whereNo is the power spectral density of noise channel, and bi,j is the channel bandwidth for user ui from j−th BS.We focus on using the UAVBS in the given area in order to maximize the number of the served users, as shown in Figure1. We introduce a binary variable Ui,j,i∈1,2,⋯,Nu and j∈1,2 which denotes whether a user ui is served by BS j or not. Therefore, Ui,j can be written as:
(10)Ui,j=1ifγi,j≥γth,0otherwise,whereγi,j represents the SNR from the user ui to the j−th BS, and γth is the threshold SNR.Then, if userui is served, γi,j≥γth must be satisfied. This conditional expression can be further manipulated as follows:
(11)γi,j≥γth−M1−Ui,j,whereM represents a insignificantly constant greater than the maximum value of γth. The overall available bandwidth provided to each BS (either GBS or UAVBS) cannot exceed its available bandwidth, i.e., B1 and B2 are the available bandwidth to GBS and UAVBS, respectively. Therefore,
(12)∑ibi,jUi,j≤Bj,wherebi,j is the bandwidth allocated to the user ui from j−th BS. Here, the bandwidth granted to each BS is not fixed and must be optimized. The optimized bandwidth depends on many parameters such as available bandwidth, QoS requirement, user demands, environment, and situation.In this work, the bandwidth allocation for each BS,Bj, should be investigated to serve users as many as possible from the total number of users in the proposed area. So, we introduce variable δ, δ∈0,1, denotes the amount of bandwidth should be granted to GBS. The portion of the bandwidth allocated to GBS is given as:
(13)B1=δB.While, the portion of the bandwidth allocated to UAVBS is given as:(14)B2=1−δB.Thereupon, the problem formulation can be formulated as,(15)maxδ,xd,yd,hd∑i=1Nu∑j=12Ui,j,subjecttoC1:γi,j≥γth−M1−Ui,j,i=1,⋯,Nu,C2:∑i=1NubijUi,j≤Bj,i=1,⋯,Nu,andj=1,2,C3:∑j=12Ui,j≤1,i=1,⋯,Nu,andj=1,2,C4:B1=δB,C5:B2=1−δB,C6:xmin≤xd≤xmax,C7:ymin≤yd≤ymax,C8:hmin≤hd≤hmax,C9:0≤δ≤1.Constraint C1 indicates that each userui will be connected to j−th BS if γij≥γth. Constraint C2 implies that the total bandwidth allocated to the user ui by each BS is within the total available bandwidth. In Constraint C3, the user ui should be associated with one BS at most (i.e., GBS or UAVBS) or none of them. Constraints C4 and C5 represent the amount of the bandwidth must be provided to each BS. Constraints C6, C7, and C8 represent allowable values for 3D position of UAVBS (xd,yd,hd), respectively. Constraint 9 (C9) indicates the percentage of bandwidth that should be allocated to GBS.


## 5. Evaluation and Numerical Results

In this chapter, an algorithm for optimizing the UAV position and association of users to BSs (GBS and UAVBS) is proposed. The goal is to provide the highest number of served users in a particular area. It is achieved by finding the best coordinates for the UAVBS by exhaustive search and the percentage of the total available bandwidth provided to each BS. Then, a heuristic algorithm, PSO, is used to find an efficient solution with low computation complexity.In the beginning, the exhaustive search will be used to find the exact solution of the proposed model, the optimal 3D location with maximum number of served users. The exhaustive search algorithm searches step by step with tiny steps to be more accurate.The efficient 3D placement for UAVBS will be found using the PSO algorithm. The PSO is a computational technique that optimizes and determines the placement problem in an iterative manner to find the optimal solution from a set of randomly distributed candidate solutions [38].


### 5.1. Exhaustive Search Algorithm

As the number of users is limited and to find the best solution, the UAV deployment problem can be determined by an exhaustive search algorithm which consists of two phases.In the first phase, the users are randomly distributed within the area and the GBS is positioned at the center of the proposed area. Then, the users associated to GBS must satisfyγi,1≥γth and ∑i=1Ugbi,1Ui,1≤B1 and the associating will start by the users with the highest SNR. Here, Ug is the set of associated users to GBS that having SNR γi,1 greater than the threshold γth, bi,1=200 KHz is the channel bandwidth provided by GBS, Ui,1 is the set of users which are satisfied the SNR condition, and B1 is the available bandwidth in the GBS. The UAVBS will serve the maximum number of users from the unassociated users with the GBS, Ur.In the second phase, the UAVBS is deployed in the positionk, k=1,2,⋯,K, where K is the maximum number of positions. At each position, k, the algorithm calculates the served users by UAVBS, Uuk. The proposed algorithm repeats the process for all K positions, where the best 3D location of UAVBS that can serve the maximum number of users of set Ur is achieved. All the users served by UAVBS should satisfy γi,2≥γth and ∑i=1Urbi,2Ui,2≤B2. Similar to GBS, the associating will start by the users that have the highest SNR. Here, Ur is the set of unserved users by GBS, γi,2 is the SNR of users in Ur from UAVBS, γth is the threshold SNR γth=15 dB, bi,2=200 KHz is the channel bandwidth provided by UAVBS, Ui,2 is the set of the users which are satisfied the SNR condition, and B2 is the available bandwidth in the UAVBS.However, an exhaustive search algorithm will entail considerable computational overhead and may even become impossible in practice, especially when there are many users in the target area.Considering the complexity of the exhaustive search algorithm, it can be formed asOXL×YL×ZL×Ur, where (XL,YL,ZL) is the 3D possible locations of the UAVBS in the proposed area, and ∣Ur∣ is the number of unserved users by GBS. For instance, in our work, we use XL is 300 and YL is 300, as we take step size of 5 m in the range of x∈0,1500 and y∈0,1500, respectively. Also, ZL is 25 as we take step size of 10 m in the range of z∈50,300.Due to increasing the complexity of the exhaustive algorithm, when the number of users increases, it becomes computationally unacceptable. So, using a heuristic algorithm (i.e., PSO) to find an efficient solution will be more valuable.


### 5.2. PSO Algorithm

As mentioned above, locating UAVs is a complicated problem, particularly when their heights are deemed. In order to solve this problem, some heuristic algorithms (e.g., particle swarm, genetic algorithms) could be applicable. Although such heuristic algorithms are suboptimal solution, these algorithms are faster than the optimal algorithms (e.g., exhaustive search) and they are efficient.In this work, the solution was proposed using the PSO algorithm [38, 39]. First, the PSO algorithm initializes a set of (nP) random solutions; in our case, each solution comprises the 3D position of UAVBS. Then, it tries to improve the candidate solutions iteratively based on the best experience of each candidate (PBestj) and the best global experience (GBest).In each iteration, the best location for each particle, which is presented by (PBestj), and the best global location, which is presented by (GBest), are upgraded. Based on them, the locations and velocities of the particles are computed [17]. The velocity is calculated as follows [17].
(16)PVelocityj=ψ∗PVelocityj+ε1∗randVarsize.∗PBestj−Pj+ε2∗randVarsize.∗GBest−Pj,whereψ is the inertia weight that determines the convergence speed, ε1 is the personal learning coefficient, ε2 is the global learning coefficient, and randVarsize is random positive numbers. The location of each particle is upgraded as
(17)Pj=Pj+PVelocityj.Algorithm1 shows the pseudocode of the PSO algorithm. To guarantee the stability, the maximum number of iterations (MIt) must be high enough. In our algorithm, there are two main elements that define the objective value: the available bandwidth and the path loss of users. Both of these elements can affect the next update process.Algorithm 1: PSO algorithm that finds the efficient UAVBS placement.
Input:The lower and upper bounds of decision variable (Varmin,Varmax), construction coefficients (κ,ϕ1,ϕ2), maximum number of iterations (MIt), population size (nP)Initialization:ϕ=ϕ1+ϕ2,X=2κ/2−ϕ−ϕ2−4ϕ0.5,ψ=X,ε1=Xϕ1,ε2=Xϕ2,GBest.Cost=−inf;Forj⟵1 to nPP(j) = unifrnd(Varmin, Varmax, Varsize)PVelocity(j) = zeros(Varsize)PCost(j) = Objectivefunction(P(j))PBest(j) = P(j)PBest.Cost(j) = P_Cost(j)IfPBest.Costj>GBest.CostGBest = P_Best(j)End ifEndPSO loop:ForIt⟵1 to MItForj⟵1 to nPPVelocity(j) =ψ∗PVelocityj+ϵ_1∗randVarsize.∗PBestj−Pj+ϵ2∗randVarsize.∗GBest−PjPj=Pj+PVelocityjPCostj=ObjectivefunctionPjIfPCostj>PBest.CostjPBestj=PjPBest.Costj=PCostjIfPBest.Costj>GBest.CostGBest=PBestjEnd ifEnd ifEndEndFirst, when the 3D placement of UAV is initialized, the connectivity between the UAVBS and the users on the ground is determined by the path loss between them and the available bandwidth in UAVBS.In order to find the 3D placement of the UAVBS using PSO algorithm, first, the users are associated to GBS. The number of served users by GBS is fixed as its location is fixed. The UAVBS will serve user if it is satisfying:γi,2≥γth and ∑i=1Urbi,2Ui,2.The objective function can be formulated as:(18)F=∑i=1UrUi,2,whereUi,2 is the set of served users by UAVBS. The objective value of F will increase by increasing the number of served users.This algorithm finds a doable solution for UAVBS placement in the proposed region based on serving the maximum number of users. The served users by UAVBS will be stored in setUu, and the total served users of the proposed model will be found by Ug+Uu.Considering the complexity of the PSO algorithm, it can be formed asOnP×MIt×∣Ur∣, where nP is a population of random solutions, MIt is the number of iterations, and Ur is the number of the unserved users by GBS. For instance, in our work, we use nP is 20 and MIt is 100.


### 5.3. Numerical Results

In this section, the theoretical proposed model is evaluated numerically using the exhaustive search and PSO algorithms. We also provide simulation results to validate the accuracy of the proposed model for the UAVBS-assisted GBS. We consider 200 users distributed uniformly in an urban area (1500m×1500m) with system parameters provided in Tables 1 and 2. The altitude of UAV ranges from 100 to 300 meters regarding the limitations and laws. Here, we assume GBS and UAVBS transmit powers are 40 and 20 dBm, respectively [40–42]. Matlab software is used as a simulation platform.Table 1
Values of the proposed model parameters.
ParameterValueParameterValueα9.61fc2 GHzβ0.16B40 MHzζLoS1 dBbi,j200 KHzζNLoS20 dBhg20 mPGBS40 dBmhmin50 mPUAV20 dBmhmax300 mγth15 dBhu1.5 mN-127 dBmn(2,4)Table 2
PSO parameters.
ParameterValuePopulation size (nP)20Maximum number of iterations (MIt)100(Varmin,Varmax)(0, 1500)(Varminh,Varmaxh)(50, 300)Varsize3(κ,ϕ1,ϕ2)(1, 2.05, 2.05)In the simulations, we first consider a single GBS and the users associated with it. The UAVBS will be deployed to serve users after the GBS being congested. In both scenarios (Exhaustive Search and PSO algorithms), the UAVBS 3D position which maximizing the number of served users can serve the number of users will be found.In our suggested model, the optimal BW allocation between GBS and UAVBS was evaluated which is explained in Figure3.Figure 3
The number of served users with different BW resource allocation between GBS and UAVBS, using exhaustive search and PSO algorithms.Figure3 shows the number of served users of the UAVBS and GBS using exhaustive search and PSO algorithms at different values of bandwidth percentage provided to the GPS (δ). In the figure, the green curve shows the number of served users by GBS, the blue curve shows the number of served users by UAVBS, the red curve shows the total number of served users when the exhaustive search algorithm is employed, the black curve shows the number of served users by UAVBS, and the cyan curve shows the total number of served users when PSO algorithm is employed. As can be seen from the figure, once the percentage of the bandwidth granted to GBS δ increases, the total number of served users is increased as well until a point with no improvement is reached. At this point, all the users that meet the QoS (i.e., SNR requirement) are served. Similarly, as δ increases, the bandwidth granted to UAVBS is reduced. Thus, the number of served users by UAVBS will be decreased. The red and cyan curves show the total number of served users, i.e., the number of served users by GBS plus the number of served users by UAVBS.Also, one can see that there are two extreme cases as follows:(i)
δ=0, in this case, all the available bandwidth is given to the UAVBS (i.e., there is no GBS). In such a scenario, the system only serves 142 users using the exhaustive search algorithm, that is, 71% of the total number of users. Furthermore, 140 users are served using the PSO algorithm, that is, 70% of the total number of users(ii)
δ=1, in this case, all the available bandwidth is given to the GBS (i.e., there is no UAVBS). In such a scenario, the system only serves 129 users, that is, 64.5% of the total number of usersOne can note that the two algorithms coincide with each other at every value ofδ. In addition, both algorithms show that the optimal value of δ is 0.7. Besides, there is an optimal bandwidth that must be granted to GBS which is equal δ=0.7, where the maximum number of served users is equal to 129. Here, the number of served users by UAVBS using an exhaustive search algorithm is 35, and using the PSO algorithm is 34.After finding the optimal bandwidth allocating (i.e.,δ), the UAVBS 3D placement that maximizes the number of served users is investigated.Figure4 shows the 2D of UAVBS deployment in the proposed area using an exhaustive search algorithm. The users served by GBS, Ug, are shown in green dots, the users served by UAVBS, Uu, are shown in blue dots, and the unserved users, Ur, are shown in red dots, where the GBS and UAVBS are shown in green and blue squares, respectively. The 2D placement of UAVBS in an exhaustive search algorithm is found as x=800 and y=440, serving 35 users.Figure 4
2D UAVBS deployment using exhaustive search. GBS usersUg=129, UAVBS users Uu=35, totalservedusers=164, and serveduserspercent=82%.Similarly, Figure5 shows the 2D of UAVBS deployment using the PSO algorithm. It is observed that the UAVBS is positioned where the distribution of users is more dense. Using the PSO algorithm, the 2D position of the UAVBS is found as x=939.7 and y=614.2, serving 34 users. It is cleared that the PSO algorithm result is very closed to optimal results using the exhaustive search algorithm.Figure 5
2D UAVBS deployment using PSO. GBS usersUg=129, UAVBS users Uu=34, totalservedusers=163, and serveduserspercent=81.5%.The number of users served by GBS is found to be 129, so the total number of served users using the exhaustive search algorithm is 164, and the percent of served users out of all users in the area is 82%. The total number of served users using the PSO algorithm is 163, and the percent of served users out of all users in the area is 81.5%.Figure6 shows the 3D of UAVBS deployment in the proposed area using an exhaustive search algorithm. It is observed that 35 users are served using the exhaustive search, and the 3D placement of UAVBS is found as x=800, y=440, and z=290.Figure 6
3D UAVBS deployment using exhaustive search. GBS usersUg=129, UAVBS users Uu=35, totalservedusers=164, and serveduserspercent=82%.Figure7 shows the 3D of UAVBS deployment using the PSO algorithm. Where 34 users are served using the PSO, and the 3D placement is found as x=939.7, y=614.2, and z=266.1. This shows how PSO algorithm result is greatly matching the ones for optimal result using the exhaustive search algorithm. One can note that the UAVBS raises to almost the maximum altitude to serve more users.Figure 7
3D UAVBS deployment using PSO. GBS usersUg=129, UAVBS users Uu=34, totalservedusers=163, and serveduserspercent=81.5%.In Figure8, the convergence speed of the PSO algorithm is presented, and it is found that the maximum number of served users is achieved at 55 iterations.Figure 8
The convergence speed of the PSO algorithm.


## 5.1. Exhaustive Search Algorithm

As the number of users is limited and to find the best solution, the UAV deployment problem can be determined by an exhaustive search algorithm which consists of two phases.In the first phase, the users are randomly distributed within the area and the GBS is positioned at the center of the proposed area. Then, the users associated to GBS must satisfyγi,1≥γth and ∑i=1Ugbi,1Ui,1≤B1 and the associating will start by the users with the highest SNR. Here, Ug is the set of associated users to GBS that having SNR γi,1 greater than the threshold γth, bi,1=200 KHz is the channel bandwidth provided by GBS, Ui,1 is the set of users which are satisfied the SNR condition, and B1 is the available bandwidth in the GBS. The UAVBS will serve the maximum number of users from the unassociated users with the GBS, Ur.In the second phase, the UAVBS is deployed in the positionk, k=1,2,⋯,K, where K is the maximum number of positions. At each position, k, the algorithm calculates the served users by UAVBS, Uuk. The proposed algorithm repeats the process for all K positions, where the best 3D location of UAVBS that can serve the maximum number of users of set Ur is achieved. All the users served by UAVBS should satisfy γi,2≥γth and ∑i=1Urbi,2Ui,2≤B2. Similar to GBS, the associating will start by the users that have the highest SNR. Here, Ur is the set of unserved users by GBS, γi,2 is the SNR of users in Ur from UAVBS, γth is the threshold SNR γth=15 dB, bi,2=200 KHz is the channel bandwidth provided by UAVBS, Ui,2 is the set of the users which are satisfied the SNR condition, and B2 is the available bandwidth in the UAVBS.However, an exhaustive search algorithm will entail considerable computational overhead and may even become impossible in practice, especially when there are many users in the target area.Considering the complexity of the exhaustive search algorithm, it can be formed asOXL×YL×ZL×Ur, where (XL,YL,ZL) is the 3D possible locations of the UAVBS in the proposed area, and ∣Ur∣ is the number of unserved users by GBS. For instance, in our work, we use XL is 300 and YL is 300, as we take step size of 5 m in the range of x∈0,1500 and y∈0,1500, respectively. Also, ZL is 25 as we take step size of 10 m in the range of z∈50,300.Due to increasing the complexity of the exhaustive algorithm, when the number of users increases, it becomes computationally unacceptable. So, using a heuristic algorithm (i.e., PSO) to find an efficient solution will be more valuable.


## 5.2. PSO Algorithm

As mentioned above, locating UAVs is a complicated problem, particularly when their heights are deemed. In order to solve this problem, some heuristic algorithms (e.g., particle swarm, genetic algorithms) could be applicable. Although such heuristic algorithms are suboptimal solution, these algorithms are faster than the optimal algorithms (e.g., exhaustive search) and they are efficient.In this work, the solution was proposed using the PSO algorithm [38, 39]. First, the PSO algorithm initializes a set of (nP) random solutions; in our case, each solution comprises the 3D position of UAVBS. Then, it tries to improve the candidate solutions iteratively based on the best experience of each candidate (PBestj) and the best global experience (GBest).In each iteration, the best location for each particle, which is presented by (PBestj), and the best global location, which is presented by (GBest), are upgraded. Based on them, the locations and velocities of the particles are computed [17]. The velocity is calculated as follows [17].
(16)PVelocityj=ψ∗PVelocityj+ε1∗randVarsize.∗PBestj−Pj+ε2∗randVarsize.∗GBest−Pj,whereψ is the inertia weight that determines the convergence speed, ε1 is the personal learning coefficient, ε2 is the global learning coefficient, and randVarsize is random positive numbers. The location of each particle is upgraded as
(17)Pj=Pj+PVelocityj.Algorithm1 shows the pseudocode of the PSO algorithm. To guarantee the stability, the maximum number of iterations (MIt) must be high enough. In our algorithm, there are two main elements that define the objective value: the available bandwidth and the path loss of users. Both of these elements can affect the next update process.Algorithm 1: PSO algorithm that finds the efficient UAVBS placement.
Input:The lower and upper bounds of decision variable (Varmin,Varmax), construction coefficients (κ,ϕ1,ϕ2), maximum number of iterations (MIt), population size (nP)Initialization:ϕ=ϕ1+ϕ2,X=2κ/2−ϕ−ϕ2−4ϕ0.5,ψ=X,ε1=Xϕ1,ε2=Xϕ2,GBest.Cost=−inf;Forj⟵1 to nPP(j) = unifrnd(Varmin, Varmax, Varsize)PVelocity(j) = zeros(Varsize)PCost(j) = Objectivefunction(P(j))PBest(j) = P(j)PBest.Cost(j) = P_Cost(j)IfPBest.Costj>GBest.CostGBest = P_Best(j)End ifEndPSO loop:ForIt⟵1 to MItForj⟵1 to nPPVelocity(j) =ψ∗PVelocityj+ϵ_1∗randVarsize.∗PBestj−Pj+ϵ2∗randVarsize.∗GBest−PjPj=Pj+PVelocityjPCostj=ObjectivefunctionPjIfPCostj>PBest.CostjPBestj=PjPBest.Costj=PCostjIfPBest.Costj>GBest.CostGBest=PBestjEnd ifEnd ifEndEndFirst, when the 3D placement of UAV is initialized, the connectivity between the UAVBS and the users on the ground is determined by the path loss between them and the available bandwidth in UAVBS.In order to find the 3D placement of the UAVBS using PSO algorithm, first, the users are associated to GBS. The number of served users by GBS is fixed as its location is fixed. The UAVBS will serve user if it is satisfying:γi,2≥γth and ∑i=1Urbi,2Ui,2.The objective function can be formulated as:(18)F=∑i=1UrUi,2,whereUi,2 is the set of served users by UAVBS. The objective value of F will increase by increasing the number of served users.This algorithm finds a doable solution for UAVBS placement in the proposed region based on serving the maximum number of users. The served users by UAVBS will be stored in setUu, and the total served users of the proposed model will be found by Ug+Uu.Considering the complexity of the PSO algorithm, it can be formed asOnP×MIt×∣Ur∣, where nP is a population of random solutions, MIt is the number of iterations, and Ur is the number of the unserved users by GBS. For instance, in our work, we use nP is 20 and MIt is 100.


## 5.3. Numerical Results

In this section, the theoretical proposed model is evaluated numerically using the exhaustive search and PSO algorithms. We also provide simulation results to validate the accuracy of the proposed model for the UAVBS-assisted GBS. We consider 200 users distributed uniformly in an urban area (1500m×1500m) with system parameters provided in Tables 1 and 2. The altitude of UAV ranges from 100 to 300 meters regarding the limitations and laws. Here, we assume GBS and UAVBS transmit powers are 40 and 20 dBm, respectively [40–42]. Matlab software is used as a simulation platform.Table 1
Values of the proposed model parameters.
ParameterValueParameterValueα9.61fc2 GHzβ0.16B40 MHzζLoS1 dBbi,j200 KHzζNLoS20 dBhg20 mPGBS40 dBmhmin50 mPUAV20 dBmhmax300 mγth15 dBhu1.5 mN-127 dBmn(2,4)Table 2
PSO parameters.
ParameterValuePopulation size (nP)20Maximum number of iterations (MIt)100(Varmin,Varmax)(0, 1500)(Varminh,Varmaxh)(50, 300)Varsize3(κ,ϕ1,ϕ2)(1, 2.05, 2.05)In the simulations, we first consider a single GBS and the users associated with it. The UAVBS will be deployed to serve users after the GBS being congested. In both scenarios (Exhaustive Search and PSO algorithms), the UAVBS 3D position which maximizing the number of served users can serve the number of users will be found.In our suggested model, the optimal BW allocation between GBS and UAVBS was evaluated which is explained in Figure3.Figure 3
The number of served users with different BW resource allocation between GBS and UAVBS, using exhaustive search and PSO algorithms.Figure3 shows the number of served users of the UAVBS and GBS using exhaustive search and PSO algorithms at different values of bandwidth percentage provided to the GPS (δ). In the figure, the green curve shows the number of served users by GBS, the blue curve shows the number of served users by UAVBS, the red curve shows the total number of served users when the exhaustive search algorithm is employed, the black curve shows the number of served users by UAVBS, and the cyan curve shows the total number of served users when PSO algorithm is employed. As can be seen from the figure, once the percentage of the bandwidth granted to GBS δ increases, the total number of served users is increased as well until a point with no improvement is reached. At this point, all the users that meet the QoS (i.e., SNR requirement) are served. Similarly, as δ increases, the bandwidth granted to UAVBS is reduced. Thus, the number of served users by UAVBS will be decreased. The red and cyan curves show the total number of served users, i.e., the number of served users by GBS plus the number of served users by UAVBS.Also, one can see that there are two extreme cases as follows:(i)
δ=0, in this case, all the available bandwidth is given to the UAVBS (i.e., there is no GBS). In such a scenario, the system only serves 142 users using the exhaustive search algorithm, that is, 71% of the total number of users. Furthermore, 140 users are served using the PSO algorithm, that is, 70% of the total number of users(ii)
δ=1, in this case, all the available bandwidth is given to the GBS (i.e., there is no UAVBS). In such a scenario, the system only serves 129 users, that is, 64.5% of the total number of usersOne can note that the two algorithms coincide with each other at every value ofδ. In addition, both algorithms show that the optimal value of δ is 0.7. Besides, there is an optimal bandwidth that must be granted to GBS which is equal δ=0.7, where the maximum number of served users is equal to 129. Here, the number of served users by UAVBS using an exhaustive search algorithm is 35, and using the PSO algorithm is 34.After finding the optimal bandwidth allocating (i.e.,δ), the UAVBS 3D placement that maximizes the number of served users is investigated.Figure4 shows the 2D of UAVBS deployment in the proposed area using an exhaustive search algorithm. The users served by GBS, Ug, are shown in green dots, the users served by UAVBS, Uu, are shown in blue dots, and the unserved users, Ur, are shown in red dots, where the GBS and UAVBS are shown in green and blue squares, respectively. The 2D placement of UAVBS in an exhaustive search algorithm is found as x=800 and y=440, serving 35 users.Figure 4
2D UAVBS deployment using exhaustive search. GBS usersUg=129, UAVBS users Uu=35, totalservedusers=164, and serveduserspercent=82%.Similarly, Figure5 shows the 2D of UAVBS deployment using the PSO algorithm. It is observed that the UAVBS is positioned where the distribution of users is more dense. Using the PSO algorithm, the 2D position of the UAVBS is found as x=939.7 and y=614.2, serving 34 users. It is cleared that the PSO algorithm result is very closed to optimal results using the exhaustive search algorithm.Figure 5
2D UAVBS deployment using PSO. GBS usersUg=129, UAVBS users Uu=34, totalservedusers=163, and serveduserspercent=81.5%.The number of users served by GBS is found to be 129, so the total number of served users using the exhaustive search algorithm is 164, and the percent of served users out of all users in the area is 82%. The total number of served users using the PSO algorithm is 163, and the percent of served users out of all users in the area is 81.5%.Figure6 shows the 3D of UAVBS deployment in the proposed area using an exhaustive search algorithm. It is observed that 35 users are served using the exhaustive search, and the 3D placement of UAVBS is found as x=800, y=440, and z=290.Figure 6
3D UAVBS deployment using exhaustive search. GBS usersUg=129, UAVBS users Uu=35, totalservedusers=164, and serveduserspercent=82%.Figure7 shows the 3D of UAVBS deployment using the PSO algorithm. Where 34 users are served using the PSO, and the 3D placement is found as x=939.7, y=614.2, and z=266.1. This shows how PSO algorithm result is greatly matching the ones for optimal result using the exhaustive search algorithm. One can note that the UAVBS raises to almost the maximum altitude to serve more users.Figure 7
3D UAVBS deployment using PSO. GBS usersUg=129, UAVBS users Uu=34, totalservedusers=163, and serveduserspercent=81.5%.In Figure8, the convergence speed of the PSO algorithm is presented, and it is found that the maximum number of served users is achieved at 55 iterations.Figure 8
The convergence speed of the PSO algorithm.


## 6. Conclusions

In this work, we address the placement of UAVBS using an exhaustive search algorithm and heuristic algorithm (i.e., PSO). In particular, we propose an efficient 3D placement method in which a UAVBS is positioned concerning users’ locations. We investigate the air-to-ground channel model, particularly for an urban area. In this model, the trade-off between UAV height and thePL is explained. It is cleared that as UAVBS altitude increases, it will serve more users. In order to prevent interference, the FDMA technique is addressed in a downlink scenario and the optimal bandwidth allocation for GBS and UAVBS which maximizing the number of served users is investigated.In the performance evaluation, we use Monte Carlo simulations over 100 runs using Matlab software. For an urban area of (1500m×1500m) with 200 arbitrary distributed users and utilizing a bandwidth of 40 MHz, the simulation results show that the optimal bandwidth provided to the GBS is 70% of the total bandwidth, and the rest of 30% of the total bandwidth is provided to the UAVBS. As a result, the proposed model of UAVBS to assist the GBS serves up to 82% of the users when using the exhaustive search algorithm and 81.5% when using the PSO algorithm, whereas using only GBS can serve 64.5% of the users. In this work, it is cleared that the exhaustive search algorithm has a very high computational complexity, and it is overridden using the PSO algorithm, which makes it an efficient track to solve such problems.



---

*Source: 2937224-2021-08-17.xml*