# Efficient 3D Positioning of UAVs and User Association Based on Hybrid PSO-K-Means Clustering Algorithm in Future Wireless Networks

Authors: Majd Shakhatreh; Hazim Shakhatreh; Ahmad Ababneh
Journal: Mobile Information Systems
 (2023)

---

## Abstract

Unmanned aerial vehicles (UAVs) play an important role in the future of 5G and 6G communication networks. UAV-assisted communication offers the benefits of improved network capacity and coverage. A typical communication setup is for UAVs to connect users to the core network via a backhaul channel. Some of the challenges in such a setup include user-UAV association and management of the backhaul channel. These two challenges are greatly impacted by the positioning of the UAVs in the network. In this article, we address these challenges by considering a joint UAV placement and user association problem under data rate, signal to interference and noise ratio, and bandwidth constraints. To overcome this problem, a hybrid PSO-K-means clustering algorithm is used in two stages. In the first stage, we use a K-means algorithm to cluster users and determine their horizontal locations. In the second stage, we use particle swarm optimization (PSO) to find the efficient 3D position of UAVs to maximize various network designs, namely, the network-centric approach and the user-centric approach. The performance of the proposed solution is verified using simulation results.


---

## Body

## 1. Introduction

Massive network capacity, low latency, and high data rates are some of the significant demands and goals of future wireless networks. These necessitate a practical transformation and efficient improvements in the current wireless communication network. Therefore, to meet these requirements, many technologies as promising candidates are considered for future wireless networks, including network densification, massive multiple-input and multiple-output (MIMO), and millimeter-wave (mmWave) communication. By operating millimeter-wave (mmWave) with large bandwidth where the frequency ranges from 30 to 300 GHz, we can enhance the data rate and capacity performance to a gigabit/s level [1–4].Recently, it has become difficult to predict user traffic patterns within certain regions. This requires the rapid and massive deployment of ground stations. However, this is impossible due to expenditures, either capital or operational. In these scenarios, UAVs as base stations (BSs) have become a promising solution in future wireless networks. UAV-BSs can help a terrestrial BS network provide high data rate coverage at any time and place it is required [5–7]. Also, UAV-BSs can deal with the issue of temporary coverage in rural and poorly populated areas and when terrestrial wireless infrastructure has been harmed by a natural catastrophe [8–10].Along with the motivations mentioned above, there are numerous challenges in integrating the mmWave band with UAV-BSs. First of all, shorter wavelengths, for instance, cause smaller objects (i.e., humans) to become radio propagation obstructions in the line-of-sight (LoS) [11, 12]. Therefore, it is critical to take the blockage caused by the human body into consideration when analyzing the performance or when mmWave-BS deployment is being planned. On the contrary, the path loss (PL) in higher frequencies increases dramatically with the increasing distance between a transmitter and a receiver [13, 14]. At mmWave bands, it is another challenge. Consequently, there is a trade-off between locating a UAV at the maximum altitude (where the LoS improves) and maintaining a low PL (where PL increases with the increasing distance). Secondly, in contrast to the ground base stations (GBSs), UAVs have wireless backhaul between them and the core network. Consequently, as the data rates of access links between users and UAV-BS have been substantially increased, the capacity of the backhaul link becomes relatively limited [15, 16]. Therefore, there is a need to consider the constraints of the wireless backhaul link as one of the limitations in the design and deployment of the UAV-BSs.Thirdly, a few articles have focused on the user-UAV association and UAV positioning issues [17–21]. In the context of a single UAV, the authors of [17] examine UAV 3D location to increase the number of served users. The association problem between the users and the UAV was addressed by using the signal-to-noise ratio (SNR). In [18], the problem of efficient 3D positioning of the UAV was examined. Two metrics were used: user-centric and network-centric to maximize the sum rate and the number of served users. Also, they imposed constraints including backhaul data rates and bandwidth and addressed the association problem by maximum path loss. Nevertheless, in the previous works [17, 18], the authors employed exhaustive search algorithms to solve the association problem. The algorithms are computationally expensive and thus impractical to employ. In the context of multiple UAVs, the authors in [19] seek to determine the least number of UAVs needed to service a set of users with high data rate requirements while placing multiple UAVs in 3D. The users’ association with UAV depends on the best signal-to-interference-plus-noise ratio (SINR) value. It is worth noting that the authors used a particle swarm optimization (PSO) algorithm to solve this problem. Nevertheless, they still suffer from high computational costs. The authors in [20] developed and studied the association problem with UAV-hubs using a simple greedy algorithm by taking into account the following constraints: the backhaul data rate of the link between the core network and the mother-UAV hub; the maximum bandwidth of each UAV-hub available for small-cell base stations; the maximum number of links that every UAV-hub can support; and the minimum SINR. In [21], authors employed an unsupervised learning-based k-means clustering technique for deploying, followed by the association of the small-cell base stations (SCBSs) by taking into account the same constraints that were mentioned in [20]. Nonetheless, one of the limitations of this work is the fact that the UAVs are all assumed to be the same height, which might not be practically possible or advisable.Finally, quite a few schemes [22–24] have been proposed to address the resource allocation problem in UAV-assisted communication. In [22], the authors employ two sleep scheduling policies for massive machine-type communication devices, which are defined by three different multiple access protocols. Moreover, they develop closed-form formulas for the massive machine-type communication devices’ peak age of information (AoI), which are formulated as the optimization objective under the constraints of energy harvesting power, status update rate, and stability conditions. For the underwater data collection to be efficiently completed, a heterogeneous autonomous underwater vehicle (AUV) auxiliary information collection system was proposed in [23]. The AUV trajectory with low time complexity was obtained by PSO. Additionally, to iteratively balance the trade-off between energy efficiency and system queue backlog, a two-stage joint optimization algorithm based on Lyapunov optimization was created. By jointly optimizing the UAV trajectory and radio resource allocation for multiple access techniques, the authors of [24] characterized the capacity region of a UAV for multiple users. The authors demonstrated that nonorthogonal multiple access significantly outperforms orthogonal multiple access in terms of rate regions for multiple users, while frequency division multiple access achieves higher rate regions than time-division multiple access.To address these issues, we investigate the efficient deployment of a mmWave-UAV-BS by taking into account the properties of mmWave communication, where a human body may be able to block the LoS link by assuming UAVs are hovering in the quasi-stationary form at a specific height and the height of the mmWave-UAV-BS is comparable to the altitude of the BSs mounted on the building walls [25]. In our optimization problem, we utilize the terrestrial and air-to-ground (A2G) channel models [26]. In addition, we investigate optimizing efficient 3D positioning of UAVs and users-UAVs association to maximize the number of served users for various network designs by considering multiple communication-related constraints. To cope with this optimization problem, UAV positions are determined using a hybrid PSO-K-means clustering algorithm in two stages. In addition, a greedy algorithm with low complexity is proposed to solve the user-UAV association problem.These paper’s contributions can be summarized as follows:(i)
To account for human body blockage, we adopt a terrestrial mmWave channel model for air-to-ground mmWave communication.(ii)
To solve the user-UAV association problem, we propose an efficient greedy algorithm for the association problem by using multiple communication-related factors, including the maximum backhaul data rate, the maximum bandwidth of each UAV, and the maximum number of links that every UAV can support.(iii)
We propose a joint user-UAV of data rate assignment optimization problem.(iv)
To solve the efficient 3D positions of UAVs problem that maximizes the objective function of the overall system, we propose a hybrid PSO-K-means clustering algorithm.(v)
To solve the backhaul data rate assignment problem, we formulate the data assignment problem as a binary optimization problem. The goal of this problem is to maximize the objective function by using multiple communication-related constraints.The rest of this article is structured as follows. In Section2, the system model is presented. In Section 3, the optimization problem is formulated. In Section 4, the proposed approach is described. After that, the simulation results are presented in Section 5. Finally, the conclusions are shown in Section 6.


## 2. System Model

In our model, we assumed a downlink wireless heterogeneous network (HetNet) area that consists of three major nodes, namely, users, UAVs, and a core network gateway, as shown in Figure1. We assume a crowded temporary event. Therefore, we will have offloaded users due to the increase in their numbers or since their data rate exceeds the determined capacity.Figure 1
The deployment scenario.LetI be the set of all offloaded users where the total number of elements of the set is defined by N where i∈I=1,2,…,N. The location of the ith user being ri=xi,yi. These users, who are considered human blockers, are designed as cylinder shapes. It is worth mentioning that we assume all users are blockers to each other, where the mobile phone is located at the altitude hi. On the other hand, UAVs are denoted as J where M denotes the total number of elements of the set, where j∈J=1,2,…,M. We suppose that the control information, including backhaul data rate, available bandwidth, and SINR, is shared by all UAVs. In the examined model, each user is associated with their own UAV. In addition, the wireless backhaul link between each UAV and the core network gateway is a mmWave link. In our assumption, the proposed system model is assumed to be static for the time of operation.To communicate between the UAVs and users, we adopted the A2G standard linear model. The A2G model has two components: line-of-sight (LoS) and non-line-of-sight (NLoS) communication links at mmWave frequencies. For a givenjth UAV and ith user, the standard linear PL models for two components are modeled as follows [26]:(1)LijLoS=αL+βLlog10Dij,LijNLoS=αN+βNlog10Dij,where α and β are the floating intercept and the line slope parameters, respectively. The 3D distance between the UAV and user Dij is expressed by(2)Dij=xi−xj2+yi−yj2+hi−hj2.To account for the blockage in the human body, the probability of LoS was adopted [27], PLoS, and given as(3)PLoS=exp−λgBsijhB−hihj−hi.Also,PNLoS=1−PLoS, where λ and gB are the density and the diameter of human blockers, respectively. The parameters denote hj, hi, and hB represent the height of UAV, user, and human blocker, respectively, and the 2D distance between user and UAV sij is given as(4)sij=xi−xj2+yi−yj2.Then, the average PL betweenith user and jth UAV, in decibel (dB), is expressed by(5)LijdB=PLoSLijLoS+PNLoSLijNLoS.We assumePj is the transmit power for each UAV. Thus, when the jth UAV transmits a frame, the user ith receives the frame with power PjgijLij, where gij denotes multipath fading and is assumed to follow an exponential distribution with a mean of μ. Then, the SINR value is given as follows:(6)SINRij=PjgijLij∑z=1z≠jMPzgizLiz+σ2,where Lij=10−LijdB/10 and σ2 is the power of additive white Gaussian noise.


## 3. Problem Formulation

As we assumed, the network is in a download case where the data download from the ground core network getaway toN users by M UAVs. Furthermore, we suppose that the users in Cartesian coordinates are distributed randomly. There is a need to estimate the required number of UAVs such that all users can be handled. In order to accomplish this, each UAV can handle the maximum number of links up to Lj from a total number of N users. Consequently, the required M can be expressed by(7)M=NLj,where . is the ceiling function. Let Q be a user-UAV association matrix. The entries of this matrix are denoted as qi,j, where the row and column indicate the user and UAV indexes, respectively. Thus, qi,j is given as(8)qi,j=1,ifQi=j,0,otherwise.Assuming the desired data rate of users from the UAV is defined byrij, this implies that the required bandwidth of users from the UAV is given as(9)bij=rijlog21+SINRij.The objective is to obtain efficient 3D positioning with a predefined efficient number of UAVs to maximize various network design parameters. These parameters include the sum rate and the number of served users for various rate demands of the overall network. To this end, the optimization problem is formulated as follows:(10)maxxj,yj,hj,qij∑j=1M∑i=1Nαijqij.Subject to:(10a)∑i=1Nrijqij≤Rj,(10b)∑i=1Nbijqij≤Bj,∀j,(10c)∑i=1Nqij≤Lj,∀j,(10d)SINRijqij≥SINRmin,∀i,j,ifqij≠0,(10e)xmin≤xj≤xmax,∀j,(10f)ymin≤yj≤ymax,∀j,(10g)hmin≤hj≤hmax,∀j,(10h)∑j=1Mqij≤1,∀i,(10i)qij∈0,1,∀i,j.Constraint (10a) ensures that the total data rates of all UAVs do not exceed the data rate allowed by the backhaul channel Rj. This is used as a QoS requirement. Constraint (10b) forces the total bandwidth allocated by each UAV not to exceed the allowable bandwidth for that particular UAV Bj. Constraint (10c) limits on the number of users associated with each UAV not to exceed a certain number Lj. One reason to justify such a requirement is to limit any possible interference, thus providing a better QoS. Constraint (10d) ensures that the SINR between a user and their UAV does not fall below a certain threshold given by SINRmin. This implies that users with severely degraded channels are not included in the association process. Constraints (10e)–(10g) specify the limits of the spatial dimension of the UAVs. Constraint (10h) indicates the binary nature of the association problem.For the cost function in (10), we consider the following scenarios:(i)
Scenario 1:αij=rij in this scenario, the setup is called the user-centric approach, and the purpose is to maximize the total sum rate of the network(ii)
Scenario 2:αij=1 in this scenario, the setup is called the network-centric approach, and the purpose is to maximize the number of served users of the network.


## 4. Hybrid PSO-K-Means Clustering Algorithm

The objective function in (10) is a binary optimization problem. Such problems are shown to be NP-hard. This implies the high computational complexity of providing an optimal solution. This requires the development of efficient solutions that have low computational complexity. A two-stage solution is presented to deal with high computational complexity for efficient UAV positions. In the first stage, we clustered the ground users and determined their 2D location by using the k-means clustering algorithm. In the second stage, 3D UAV positions are determined using the PSO algorithm to maximize various network designs, whether they are a user-centric approach or a network-centric approach.


### 4.1.K-Means Clustering Algorithm

Thek-means clustering algorithm is an unsupervised algorithm that was proposed by Stuart Lloyd of Bell Labs in 1957 [28]. Ṫhe algorithm attempts to divide I users into M predefined clusters, with each user being assigned to only one group. K-means is also a measure of intracluster similarity and intercluster dissimilarity that is maximized through iterative hill-climbing. In our context, the k-means clustering algorithm deals with the 2D placement of the ground users. Algorithm 1 illustrates the k-means clustering method’s pseudo-code, which was inspired by the k-means algorithm [29].As we mentioned before, there is a need to divide a set of usersI into M clusters, where each user belongs to the cluster with the closest mean. According to Algorithm 1, selecting the number of clusters (i.e., M) is the key stage in our algorithm before randomly initializing clusters centroids (i.e., step 5). The algorithm performs two tasks throughout each iteration: (1) stage of cluster assignment and (2) stage of centroids moving (step 6). In the stage of assigning clusters, each point is examined by the algorithm, which selects the nearest centroid and assigns the point to it. In the moving centroids stage, the algorithm determines the cluster’s mean point and shifts the centroids there. This two-step procedure is repeated until the algorithm converges. When the assignments stop changing, the algorithm converges. The temporal complexity of the k-means clustering technique is ONM, where N is the number of users and M denotes the number of clusters. Based on the suggested algorithm, we assume that each cluster will only have one UAV covered. After it has finished clustering the users, it uses the PSO algorithm to determine the location of the UAV in three dimensions to maximize the overall network total sum rate and the number of served users based on the applied approach.Algorithm 1:K-means clustering algorithm.
(1)
Input:(2)
The placements ofI ground users.(3)
The number of clustersM.(4)
Start(5)
Initialize the locations of the centroidsμ1,μ2,….μM randomly(6)
Repeat until convergenceFor every ground useri∈I, setϵi=argmaxj∈Mri−μj2For each clusterj∈M, setμj=∑i∈I,ϵi=jri/∑i∈I,ϵi=j1(7)
Output:(8)
M Clusters.


### 4.2. Efficient 3D Positioning of UAVs

One of the most popular intelligence approaches and evolutionary global optimization techniques is the particle swarm optimization (PSO) algorithm. The algorithm was first proposed in [30] and was inspired by social animal group behavior including bird flocks and fish swarms. These sociable creatures are well-known for cooperating to maximize their accessibility to food by exchanging information among themselves. The finding sparked the idea of random agents collaborating to find better solutions [30]. In PSO, each individual agent, also called a particle, changes its search velocity based on its best performance as well as the best performance of its group. In this stage, we apply the PSO algorithm to find an efficient 3D position of the UAV to maximize the objective function. Specific steps are illustrated as follows:(a)
Initialization. The maximum number of iterations is determined in this first stage, along with initializing the population position and setting the maximum particle speed. The position information is used to determine the search space, and initialization is done by selecting random points within the speed range and search space. The initial flying speed of each particle is then chosen at random, with M designating the size of the particle swarm. The beginning population is set as the initial position of the UAV because the objective of this approach is to find the most efficient UAV 3D position.(b)
Function of Fitness. The objective function must satisfy multiple communication-related factors, including (1)–(4) constraints in order to maximize the objective function, whether it is the total sum rate or the number of served users, in a user-centric approach or a network-centric approach, respectively. Consequently, the objective function can be used as the evaluation function as follow maxxj,yj,hj,qij∑j=1M∑i=1Nαijqij.(c)
Update Position and Speed. Following that, the fitness value of each particle is computed using the fitness function in an iterative manner to improve the candidate solutions based on two best values, i.e., the best local experience of each particle ωibest, and the best global experience ωiglobalbest. The best local location for each particle ωibest and the best global location ωiglobalbest are updated in each iteration, and based on them, the particle positions and velocities are determined [19]. How much the position can change is indicated by the speed Vi value, which is provided by(11)Vi=w×Vi+c1×randvsize×ωibest−ωi+c2×randVsize×ωiglobalbest−ωi,where randVsize is uniformly distributed random variables with independent distributions in the range 0,1, c1 and c2 are positive parameters known as acceleration coefficients, that determine the maximum step size between iterations, and w is the inertia weight. Additionally, each particle position ωi is updated as follows:(12)ωi=ωi+Vi.The computational cost of the algorithm is determined by the number of iterationsTmax, candidate solutions Npop, and iterations used to update each particle’s velocity and position ω. As a result, OωTmaxNpop gives the PSO algorithm’s worst-case complexity. In comparison to other meta-heuristic algorithms (i.e., Artificial Bees Colony (ABC), Genetic Algorithm (GA), and Ant Colony), the PSO algorithm is less complicated and takes less time to run.Having determined the location of the UAVs via the PSO-K-means deployment scheme, we turn our attention towards the UAV-User association. The association problem is an NP-hard binary problem that is computationally intensive. To solve this problem, we propose a greedy approach, which consists of two stages that are described below.(i)
SINR Ranking. The purpose of this step is for UAVs to estimate the SINR values at the user side. This is necessary since the SINR values are not known beforehand and are sensitive to channel effects. To produce this estimate, the UAV initializes communication with a predetermined signal to the users. Each user calculates the SINR value at their side. Next, a user orders the M SINR values corresponding to M UAV and chooses the user with the maximum SINR value. We note that the user excludes all UAVs with corresponding SINR values that violate the minimum SINR values set in the constraint (A4). Upon determining the UAV with maximum SINR value, say the jth UAV, it sends confirmation feedback to that UAV. Combining all user feedback to the UAVs, an association matrix Q can be constructed. The Q matrix is a binary N×M matrix in which the i,jth entry corresponds to the association between the ith user and jth UAV. For ith user, if the jth UAV is the UAV with the max SINR then Qi,j=1, otherwise it is set at 0.(ii)
Q-Matrix Pruning.We note that the association matrixQ established in the previous step is only concerned with ensuring that the SINR requirement is met. In order to satisfy the other constraints simultaneously with maximizing the objective function in (10), the association matrix Q needs to be pruned. For pruning the Q matrix, each UAV attempts to find the users who are willing to provide service from the set of users who send feedback requests to UAVs. In other words, for the jth UAV, the goal is to prune the jth column (i.e., column Q:,m).To achieve this, we propose a greedy association algorithm shown in Algorithm2. In this algorithm, the association is locally decided at each UAV, where the decision process is sequential in nature. We consider two cases; the user-centric scenario and the network-centric scenario objectives.(i)
Scenario 1 (User-Centric Scenario). In this scenario, the goal is to maximize the sum of data rates served by the UAV. Thus, the objective function in (10) is such that αij=rij. To maximize the objective, the proposed algorithm associates users to each UAV in a sequential greedy fashion. The idea is to select the users with the maximum data rates and keep adding them to an association vector as long as the constraints (i.e., A1, A2 and A3) are not violated. Let Im denote the association vector of the jth UAV. The vector Im is an Nm×1 vector with Nn denoting the number of non-zero entries in the jth column of Q denoted as Q:,m. Furthermore, let 1q,m denote the vector of user indexes corresponding to nonzero entries in the column Q:,m. Moreover, let r⟶users denote the set of data rate required corresponding to the user 1q,m. We are now ready to explain the steps of the proposed algorithm. The first step is to find the maximum rate in the vector r⟶users. Assume that it corresponds to the index ith, then the first user to be associated is the ith user. Next, the association vector Im is updated to have a non-zero entry in the index ith. The constraints are then modified and checked for binary validity. The association process continues until at least the constraints are violated.(ii)
Scenario 2 (Network-Centric Scenario).This is similar to the previous scenario, except for the fact that the goal here is to maximize the number of users associated with each UAV. To achieve this, theαij in the cost function is modified such that αij=1. This combined with the rate constraint implies that users should be added in a way that gives more priority to users with low data rates. This is in contrast to the user-centric approach explained earlier. Thus, we can employ the same greedy algorithm described where above but with the following modification instead of the descending ordering used earlier. The entity of the r⟶users vector is selected in ascending order.Algorithm 2: Users association with UAVs.
Input: Rj,Bj,rij,bij,SINRij,Lj,N,MOutput: QInitialize: Q = ϕ(1)
Step 1(2)
fori= 1 to Ndo(3)
Create a list of UAVs that satisfyA4 constraint(4)
end for(5)
Step 2(6)
forj= 1 to Mdo(7)
ifScenario1then(8)
choose users having maximum data rate (i.e., max.rij)(9)
end(10)
else ifScenario2then(11)
choose users having minimum data rate (i.e., min.rij)(12)
end(13)
Counters Initialize:TLj=0,TBj=0,TRj = 0, for all j(14)
whileTLj<Lj∧TBj<Bj∧TRj<Rjdo(15)
ifTBj+bij≤Bj and TRj+rij≤Rj(16)
Updateqij = 1, TLj=TLj−1, TBj=TBj+bij, and TRj=TRj+rij(17)
end if(18)
end while(19)
end for


## 4.1.K-Means Clustering Algorithm

Thek-means clustering algorithm is an unsupervised algorithm that was proposed by Stuart Lloyd of Bell Labs in 1957 [28]. Ṫhe algorithm attempts to divide I users into M predefined clusters, with each user being assigned to only one group. K-means is also a measure of intracluster similarity and intercluster dissimilarity that is maximized through iterative hill-climbing. In our context, the k-means clustering algorithm deals with the 2D placement of the ground users. Algorithm 1 illustrates the k-means clustering method’s pseudo-code, which was inspired by the k-means algorithm [29].As we mentioned before, there is a need to divide a set of usersI into M clusters, where each user belongs to the cluster with the closest mean. According to Algorithm 1, selecting the number of clusters (i.e., M) is the key stage in our algorithm before randomly initializing clusters centroids (i.e., step 5). The algorithm performs two tasks throughout each iteration: (1) stage of cluster assignment and (2) stage of centroids moving (step 6). In the stage of assigning clusters, each point is examined by the algorithm, which selects the nearest centroid and assigns the point to it. In the moving centroids stage, the algorithm determines the cluster’s mean point and shifts the centroids there. This two-step procedure is repeated until the algorithm converges. When the assignments stop changing, the algorithm converges. The temporal complexity of the k-means clustering technique is ONM, where N is the number of users and M denotes the number of clusters. Based on the suggested algorithm, we assume that each cluster will only have one UAV covered. After it has finished clustering the users, it uses the PSO algorithm to determine the location of the UAV in three dimensions to maximize the overall network total sum rate and the number of served users based on the applied approach.Algorithm 1:K-means clustering algorithm.
(1)
Input:(2)
The placements ofI ground users.(3)
The number of clustersM.(4)
Start(5)
Initialize the locations of the centroidsμ1,μ2,….μM randomly(6)
Repeat until convergenceFor every ground useri∈I, setϵi=argmaxj∈Mri−μj2For each clusterj∈M, setμj=∑i∈I,ϵi=jri/∑i∈I,ϵi=j1(7)
Output:(8)
M Clusters.


## 4.2. Efficient 3D Positioning of UAVs

One of the most popular intelligence approaches and evolutionary global optimization techniques is the particle swarm optimization (PSO) algorithm. The algorithm was first proposed in [30] and was inspired by social animal group behavior including bird flocks and fish swarms. These sociable creatures are well-known for cooperating to maximize their accessibility to food by exchanging information among themselves. The finding sparked the idea of random agents collaborating to find better solutions [30]. In PSO, each individual agent, also called a particle, changes its search velocity based on its best performance as well as the best performance of its group. In this stage, we apply the PSO algorithm to find an efficient 3D position of the UAV to maximize the objective function. Specific steps are illustrated as follows:(a)
Initialization. The maximum number of iterations is determined in this first stage, along with initializing the population position and setting the maximum particle speed. The position information is used to determine the search space, and initialization is done by selecting random points within the speed range and search space. The initial flying speed of each particle is then chosen at random, with M designating the size of the particle swarm. The beginning population is set as the initial position of the UAV because the objective of this approach is to find the most efficient UAV 3D position.(b)
Function of Fitness. The objective function must satisfy multiple communication-related factors, including (1)–(4) constraints in order to maximize the objective function, whether it is the total sum rate or the number of served users, in a user-centric approach or a network-centric approach, respectively. Consequently, the objective function can be used as the evaluation function as follow maxxj,yj,hj,qij∑j=1M∑i=1Nαijqij.(c)
Update Position and Speed. Following that, the fitness value of each particle is computed using the fitness function in an iterative manner to improve the candidate solutions based on two best values, i.e., the best local experience of each particle ωibest, and the best global experience ωiglobalbest. The best local location for each particle ωibest and the best global location ωiglobalbest are updated in each iteration, and based on them, the particle positions and velocities are determined [19]. How much the position can change is indicated by the speed Vi value, which is provided by(11)Vi=w×Vi+c1×randvsize×ωibest−ωi+c2×randVsize×ωiglobalbest−ωi,where randVsize is uniformly distributed random variables with independent distributions in the range 0,1, c1 and c2 are positive parameters known as acceleration coefficients, that determine the maximum step size between iterations, and w is the inertia weight. Additionally, each particle position ωi is updated as follows:(12)ωi=ωi+Vi.The computational cost of the algorithm is determined by the number of iterationsTmax, candidate solutions Npop, and iterations used to update each particle’s velocity and position ω. As a result, OωTmaxNpop gives the PSO algorithm’s worst-case complexity. In comparison to other meta-heuristic algorithms (i.e., Artificial Bees Colony (ABC), Genetic Algorithm (GA), and Ant Colony), the PSO algorithm is less complicated and takes less time to run.Having determined the location of the UAVs via the PSO-K-means deployment scheme, we turn our attention towards the UAV-User association. The association problem is an NP-hard binary problem that is computationally intensive. To solve this problem, we propose a greedy approach, which consists of two stages that are described below.(i)
SINR Ranking. The purpose of this step is for UAVs to estimate the SINR values at the user side. This is necessary since the SINR values are not known beforehand and are sensitive to channel effects. To produce this estimate, the UAV initializes communication with a predetermined signal to the users. Each user calculates the SINR value at their side. Next, a user orders the M SINR values corresponding to M UAV and chooses the user with the maximum SINR value. We note that the user excludes all UAVs with corresponding SINR values that violate the minimum SINR values set in the constraint (A4). Upon determining the UAV with maximum SINR value, say the jth UAV, it sends confirmation feedback to that UAV. Combining all user feedback to the UAVs, an association matrix Q can be constructed. The Q matrix is a binary N×M matrix in which the i,jth entry corresponds to the association between the ith user and jth UAV. For ith user, if the jth UAV is the UAV with the max SINR then Qi,j=1, otherwise it is set at 0.(ii)
Q-Matrix Pruning.We note that the association matrixQ established in the previous step is only concerned with ensuring that the SINR requirement is met. In order to satisfy the other constraints simultaneously with maximizing the objective function in (10), the association matrix Q needs to be pruned. For pruning the Q matrix, each UAV attempts to find the users who are willing to provide service from the set of users who send feedback requests to UAVs. In other words, for the jth UAV, the goal is to prune the jth column (i.e., column Q:,m).To achieve this, we propose a greedy association algorithm shown in Algorithm2. In this algorithm, the association is locally decided at each UAV, where the decision process is sequential in nature. We consider two cases; the user-centric scenario and the network-centric scenario objectives.(i)
Scenario 1 (User-Centric Scenario). In this scenario, the goal is to maximize the sum of data rates served by the UAV. Thus, the objective function in (10) is such that αij=rij. To maximize the objective, the proposed algorithm associates users to each UAV in a sequential greedy fashion. The idea is to select the users with the maximum data rates and keep adding them to an association vector as long as the constraints (i.e., A1, A2 and A3) are not violated. Let Im denote the association vector of the jth UAV. The vector Im is an Nm×1 vector with Nn denoting the number of non-zero entries in the jth column of Q denoted as Q:,m. Furthermore, let 1q,m denote the vector of user indexes corresponding to nonzero entries in the column Q:,m. Moreover, let r⟶users denote the set of data rate required corresponding to the user 1q,m. We are now ready to explain the steps of the proposed algorithm. The first step is to find the maximum rate in the vector r⟶users. Assume that it corresponds to the index ith, then the first user to be associated is the ith user. Next, the association vector Im is updated to have a non-zero entry in the index ith. The constraints are then modified and checked for binary validity. The association process continues until at least the constraints are violated.(ii)
Scenario 2 (Network-Centric Scenario).This is similar to the previous scenario, except for the fact that the goal here is to maximize the number of users associated with each UAV. To achieve this, theαij in the cost function is modified such that αij=1. This combined with the rate constraint implies that users should be added in a way that gives more priority to users with low data rates. This is in contrast to the user-centric approach explained earlier. Thus, we can employ the same greedy algorithm described where above but with the following modification instead of the descending ordering used earlier. The entity of the r⟶users vector is selected in ascending order.Algorithm 2: Users association with UAVs.
Input: Rj,Bj,rij,bij,SINRij,Lj,N,MOutput: QInitialize: Q = ϕ(1)
Step 1(2)
fori= 1 to Ndo(3)
Create a list of UAVs that satisfyA4 constraint(4)
end for(5)
Step 2(6)
forj= 1 to Mdo(7)
ifScenario1then(8)
choose users having maximum data rate (i.e., max.rij)(9)
end(10)
else ifScenario2then(11)
choose users having minimum data rate (i.e., min.rij)(12)
end(13)
Counters Initialize:TLj=0,TBj=0,TRj = 0, for all j(14)
whileTLj<Lj∧TBj<Bj∧TRj<Rjdo(15)
ifTBj+bij≤Bj and TRj+rij≤Rj(16)
Updateqij = 1, TLj=TLj−1, TBj=TBj+bij, and TRj=TRj+rij(17)
end if(18)
end while(19)
end for


## 5. Simulation Results and Discussion

We suppose the geographic area is 1km2 in which 100 users are uniformly distributed in the Cartesian coordinates. Each UAV can accommodate 30 requests. According to (7), we have 4 UAVs. Furthermore, we assume that each UAV flies at a low altitude of [100–400] m. Now we allocate the data rates at random from the vector r⟶users and use the procedure described in Algorithm 2 to obtain the results. Table 1 lists the simulation parameters. The results are simulated for two different scenarios:(i)
Scenario 1:αij=rij where the priority is given to users who have the maximum data rate and minimum bandwidth.(ii)
Scenario 2:αij=1 where the priority is given to users who have the minimum data rate and minimum bandwidth.Table 1
Simulation parameters.
ParameterValueParameterValueParameterValueαL61.4βL2Rj0.6 GbpsαN72βN2.92Bj700 MHzhi1.3hB1.7Lj30gB0.5Pj5 WSINRmin−5 dBμ1σ2−125 dBfc28 GHzr⟶users{10, 20, 30, 40, 50} MbpsAs mentioned before, the network selects the user based onαij. The network-centric approach attempts to serve as many users as feasible, regardless of the required data rate. When using a network-centric, most of the serviced users have a low data rate. 5 G networks require a distinction between the applications and users; thus, offering the service to users with a low data rate is not fair. From this point, we used a user-centric approach to identify user priorities, where the network selects the user to maximize the total sum rate and prioritize the users with the highest data rate.In the two proposed scenarios, the results of Algorithm2 are examined for both network designs. Figure 2(a) and 2(b) depict the users’ distribution and the efficient 3D positioning of UAVs for user-centric and network-centric approaches, respectively. In both approaches, we observed that the UAVs move to the maximum potential altitude to maximize the objective function. Also, as we can see, in the user-centric approach, the service will be provided to fewer users compared to the network-centric approach. Most service providers tend to choose the network-centric approach, which is considered the most favorable option in that it requires less payment for using the spectrum. The license fee depends on the amount of bandwidth consumed per user across a geographic area. Table 2 illustrates the numerical performance of Figure 2 and compares the two proposed approaches (i.e., user-centric and network-centric) in terms of total associated users, total bandwidth consumption, total sum rate, and percentage of users in an outage. Overall, we note that network-centric is superior to user-centric in terms of the number of connected users and the percentage of users experiencing an outage from the service. This is due to the priority that was previously explained.Figure 2
3D location of UAVs and user-UAVs association in (a) user-centric approach and (b) network-centric approach.
(a)(b)Table 2
Comparison of numerical results.
Evaluation parametersUser-centric approachNetwork-centric approachTotal associated users7893Total bandwidth consumption (GHz)2.392.34Total sum rate (Gbps)2.42.35Users in outage (%)227To have a better understanding of the proposed algorithm and limitations, we run a few experiments in the following to study the effects of various limitations due to constraints (A1), (A2), and (A2) on the objective function equation (11), i.e., total sum rate and number of served users of the overall system. Furthermore, we discuss the impact of the constraints on the number of associated users.


### 5.1. Backhaul Data Rate Effect

To study the backhaul data rate effect (i.e., (10a) constraint), Figure 3 illustrates the total sum data rate of the served users versus different ranges of Rj, which is the peak data rate backhaul limit to the sum of the demanded data rate by the Lj users for a single value of Rj. For the user-centric and network-centric approaches, the ratio Rj is kept the same by changing the backhaul data rate limit according to the demanded sum data rate of users. Additionally, by offering more resources than necessary, other restrictions like those on bandwidth and the number of links are relaxed. This is done so that the impact of the backhaul data rate may be easily recognized. We can notice that the sum data rate increases with the increase in ratio Rj until the ratio reaches Rj = 0.8 Gbps. Then, the sum data rate remains the same even with the increase in Rj because, beyond Rj = 0.8 Gbps, the algorithm has already associated all users. Thus, providing extra resources is unnecessary.Figure 3
Total sum rate of served users versus different backhaul data rates with restrictionsBj = 5 GHz.Figure4 illustrates the effect of the Rj constraint on the number of served users in the two approaches. As shown in the figure, we severely limited the total number of served users due to the low backhaul data rate. Also, with the increased data rate backhaul per UAV in the two approaches, the total number of served users increases as well. At a certain data rate for backhaul (i.e., 1 Gbps), the increase in the overall number of users serviced is nearly constant. This is attributed to bandwidth resource exhaustion. Thus, the UAVs cannot serve more users.Figure 4
The total number of served users versus different backhaul data rates with restrictionsBj = 5 GHz.In the user-centric approach, the rate of rising in the number of serviced users is practically constant (note the fixed slope of the blue dashed line), while in the network-centric approach, it declines (take note of the red dashed lines’ descending slope). This fixed slope is due to the proposed scenario where the users with a high data rate are served first. Therefore, the backhaul capacity will increase, and users with a low data rate will receive service. However, in the network-centric approach, the slope is not constant but decreasing. In this scenario, the users with low data rate are served first. Consequently, a few users with a high data rate obtain service, and in each step, the amount of increment in backhaul capacity is decreased by increasing the backhaul capacity.


### 5.2. Bandwidth Limit Effect

To study the effect of bandwidth constraint (i.e., (10b) constraint), Figure 5 illustrates the total achievable sum rate versus different ranges of Bj. The two approaches show that the sum rate increases exponentially with the increase in bandwidth for each UAV, which is intuitive as users will be able to associate with more users due to increased bandwidth. We also note that the performance is almost similar in both approaches. The total sum rate remains the same at a certain bandwidth value (i.e., 0.8 GHz). This is since the data rate backhaul is exhausted and all users have already associated.Figure 5
Total sum data rate of users versus available bandwidth limit with constraintRj = 5 Gbps.Figure6 illustrates the effect of the Bj constraint on the number of associated users in the two proposed approaches. By increasing the available bandwidth of each UAV, the total number of served users increases in the two approaches. Also, the network-centric approach can be noticed that the maximum number of served users is achievable. At a particular bandwidth value (i.e., 1 GHz), the increase in the total number of served users remains the same. This is attributed to the high data rate of backhaul exhaustion. Thus, the UAVs cannot serve more users. As for the slope, it bears the same interpretation that was previously illustrated in Figure 4.Figure 6
The number of served users versus the bandwidth limit for the association algorithm with constraintRj = 5 Gbps.


### 5.3. Number of Links Limit Effect

To study the effect of the number of links limit (i.e., (10c) constraint), Figure 7 illustrates the performance of the total sum rate when the number of connections accommodated by UAVs is raised from 5 to 40 links. The backhaul data rate and bandwidth constraints are provided such that they do not affect the association of users. As a result, the influence of the number of links can be seen entirely. Keep in mind that the number of UAVs remains the same (i.e., M = 4). With the increase of Lj, the achieved sum rate by user-centric is greater than network-centric. This is due to the priority proposed in our greedy algorithms. Furthermore, in the two proposed approaches, the sum-rate value does not increase at a specific value (i.e., Lj = 30) because all the users are served at that point.Figure 7
Evaluation of total sum rate with different number of links constraint:Bj = 5 GHz and Rj = 5 Gbps.Back to the topic of work, Figure8 illustrates the initial and final position of UAVs for the user-centric and network-centric approaches, respectively. The 3D positions of UAVs are shown in Figures 8(a), and 8(d), and the 2D positions of UAVs are shown in Figures 8(b) and 8(e). The UAVs adjust their positions dynamically, starting from their initial points (uncolored circles), which are chosen at random, and moving in the direction of the users they are serving in a few steps until arriving at their final efficient places (colorful stars). The initial (uncolored circles) and final (colored circles) altitudes of UAVs are clearly illustrated in Figures 8(c) and 8(f), where these heights are plotted versus UAVs in X-coordinates. The result demonstrates how UAVs modify their heights to alleviate interference, serve as many users as possible, and improve the LoS probability between the users and UAVs.Figure 8
(a) 3D UAVs trajectories for user-centric approach, (b) 2D UAVs trajectories for user-centric approach, (c) altitudes of UAVs for user-centric approach, (d) 3D UAVs trajectories for network-centric approach, (e) 2D UAVs trajectories for network-centric approach, and (f) altitudes of UAVs for network-centric approach.
(a)(b)(c)(d)(e)(f)


## 5.1. Backhaul Data Rate Effect

To study the backhaul data rate effect (i.e., (10a) constraint), Figure 3 illustrates the total sum data rate of the served users versus different ranges of Rj, which is the peak data rate backhaul limit to the sum of the demanded data rate by the Lj users for a single value of Rj. For the user-centric and network-centric approaches, the ratio Rj is kept the same by changing the backhaul data rate limit according to the demanded sum data rate of users. Additionally, by offering more resources than necessary, other restrictions like those on bandwidth and the number of links are relaxed. This is done so that the impact of the backhaul data rate may be easily recognized. We can notice that the sum data rate increases with the increase in ratio Rj until the ratio reaches Rj = 0.8 Gbps. Then, the sum data rate remains the same even with the increase in Rj because, beyond Rj = 0.8 Gbps, the algorithm has already associated all users. Thus, providing extra resources is unnecessary.Figure 3
Total sum rate of served users versus different backhaul data rates with restrictionsBj = 5 GHz.Figure4 illustrates the effect of the Rj constraint on the number of served users in the two approaches. As shown in the figure, we severely limited the total number of served users due to the low backhaul data rate. Also, with the increased data rate backhaul per UAV in the two approaches, the total number of served users increases as well. At a certain data rate for backhaul (i.e., 1 Gbps), the increase in the overall number of users serviced is nearly constant. This is attributed to bandwidth resource exhaustion. Thus, the UAVs cannot serve more users.Figure 4
The total number of served users versus different backhaul data rates with restrictionsBj = 5 GHz.In the user-centric approach, the rate of rising in the number of serviced users is practically constant (note the fixed slope of the blue dashed line), while in the network-centric approach, it declines (take note of the red dashed lines’ descending slope). This fixed slope is due to the proposed scenario where the users with a high data rate are served first. Therefore, the backhaul capacity will increase, and users with a low data rate will receive service. However, in the network-centric approach, the slope is not constant but decreasing. In this scenario, the users with low data rate are served first. Consequently, a few users with a high data rate obtain service, and in each step, the amount of increment in backhaul capacity is decreased by increasing the backhaul capacity.


## 5.2. Bandwidth Limit Effect

To study the effect of bandwidth constraint (i.e., (10b) constraint), Figure 5 illustrates the total achievable sum rate versus different ranges of Bj. The two approaches show that the sum rate increases exponentially with the increase in bandwidth for each UAV, which is intuitive as users will be able to associate with more users due to increased bandwidth. We also note that the performance is almost similar in both approaches. The total sum rate remains the same at a certain bandwidth value (i.e., 0.8 GHz). This is since the data rate backhaul is exhausted and all users have already associated.Figure 5
Total sum data rate of users versus available bandwidth limit with constraintRj = 5 Gbps.Figure6 illustrates the effect of the Bj constraint on the number of associated users in the two proposed approaches. By increasing the available bandwidth of each UAV, the total number of served users increases in the two approaches. Also, the network-centric approach can be noticed that the maximum number of served users is achievable. At a particular bandwidth value (i.e., 1 GHz), the increase in the total number of served users remains the same. This is attributed to the high data rate of backhaul exhaustion. Thus, the UAVs cannot serve more users. As for the slope, it bears the same interpretation that was previously illustrated in Figure 4.Figure 6
The number of served users versus the bandwidth limit for the association algorithm with constraintRj = 5 Gbps.


## 5.3. Number of Links Limit Effect

To study the effect of the number of links limit (i.e., (10c) constraint), Figure 7 illustrates the performance of the total sum rate when the number of connections accommodated by UAVs is raised from 5 to 40 links. The backhaul data rate and bandwidth constraints are provided such that they do not affect the association of users. As a result, the influence of the number of links can be seen entirely. Keep in mind that the number of UAVs remains the same (i.e., M = 4). With the increase of Lj, the achieved sum rate by user-centric is greater than network-centric. This is due to the priority proposed in our greedy algorithms. Furthermore, in the two proposed approaches, the sum-rate value does not increase at a specific value (i.e., Lj = 30) because all the users are served at that point.Figure 7
Evaluation of total sum rate with different number of links constraint:Bj = 5 GHz and Rj = 5 Gbps.Back to the topic of work, Figure8 illustrates the initial and final position of UAVs for the user-centric and network-centric approaches, respectively. The 3D positions of UAVs are shown in Figures 8(a), and 8(d), and the 2D positions of UAVs are shown in Figures 8(b) and 8(e). The UAVs adjust their positions dynamically, starting from their initial points (uncolored circles), which are chosen at random, and moving in the direction of the users they are serving in a few steps until arriving at their final efficient places (colorful stars). The initial (uncolored circles) and final (colored circles) altitudes of UAVs are clearly illustrated in Figures 8(c) and 8(f), where these heights are plotted versus UAVs in X-coordinates. The result demonstrates how UAVs modify their heights to alleviate interference, serve as many users as possible, and improve the LoS probability between the users and UAVs.Figure 8
(a) 3D UAVs trajectories for user-centric approach, (b) 2D UAVs trajectories for user-centric approach, (c) altitudes of UAVs for user-centric approach, (d) 3D UAVs trajectories for network-centric approach, (e) 2D UAVs trajectories for network-centric approach, and (f) altitudes of UAVs for network-centric approach.
(a)(b)(c)(d)(e)(f)


## 6. Conclusion

In summary, this paper presented the efficient 3D position of UAVs to provide mmWave backhaul connectivity to ground users with different rate requirements with the ground core network, using a hybrid PSO-K-means algorithm. The user-UAV association is constrained by factors such as backhaul data rate, bandwidth available, the number of requests a UAV can accommodate, and the minimum SINR criterion. Furthermore, the objective function is done based on two approaches, namely, the user-centric approach that maximizes users’ sum rate by giving priority to users having a maximum data rate and the network-centric approach that maximizes the total number of served users having a minimum data rate. Simultaneously, consuming less bandwidth in the two approaches is considered since the bandwidth resources will be finite in the 5G network. Furthermore, we ran a few experiments to study the effects of various limitations due to constraints on peak data rate backhaul and bandwidth on the objective function. In addition, we discuss the effect of the constraints on the number of associated users.



---

*Source: 6567897-2023-01-27.xml*