# Space Deployment Algorithm for UAV-IRS-Based Systems Using a Ck++ Optimizer

Authors: Hao Lu; Minghe Mao; Jianjun Sun
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

With the popularity of 5G mobile communication services, the number of users has increased dramatically, as well as the nonuniformity of user density distribution; many users are in nonideal channel conditions, so unmanned aerial vehicle (UAV) as a passive relay equipment platform has gradually entered people’s vision. Intelligent reflective surfaces (IRSs) capable of reconfiguring electromagnetic absorption and reflection properties in real-time are offering unprecedented opportunities to enhance wireless communication experience in challenging environments. In this paper, we start from the point of minimizing the energy consumption and nodes of UAV passive relay; the paper proposes to install intelligent reflecting surface (IRS) on UAV as a new passive relay and establish the communication coverage model of UAV-IRS. Then, the main relationship between the coverage radius and hover height of UAV-IRS is verified. In view of different distribution densities of target users, a CK++ (cyclick-means++) is proposed to solve the spatial deployment problem of UAV-IRS, where the optimal solution of the system is obtained through cyclic clustering. And the algorithm is verified to effectively improve the performance of urban mobile communication and user communication service quality through numerical stimulation.


---

## Body

## 1. Introduction

Today, the communication network is increasingly developed. Especially with the maturity of 5G technology, higher requirements are placed on the communication network. Wireless relay, as an effective means to expand the transmission range and an important way to improve the transmission capacity, can be achieved by using fixed relay nodes or mobile relay platforms. With the diversified development of relay network scenarios, unmanned aerial vehicles (UAVs) appear more and more in wireless relay scenarios in recent years [1–4]. Due to UAVs having the advantages of low cost, high flexibility, and rapid deployment [5], installing the relay equipment on them to form UAV-IRSs can provide more effective communication services. UAV-assisted wireless communication networks also face many challenges, such as how to improve energy efficiency, ensure lower latency, improve resource utilization, and optimize mobility management strategies, so UAV-assisted wireless communication networks require further research. As an aerial relay platform, UAV has some differences from fixed ground relay deployment:
(1)
Deployment can be more convenient owing to the flexibility of UAV-IRS. After obtaining the deployment location, UAV-IRS can reach the specified location quickly to complete the deployment, and the deployment location of UAV-IRS can be changed at any time. However, the fixed relay has a fixed deployment location, a long deployment period, and a confined service range(2)
The link between UAV-IRSs is different from that between fixed relay nodes. UAV is above the user, and it is very easy to build a line-of-sight link, while the link between fixed relay nodes will experience various fading and various line-of-sight obstacles, and most of the links are non-line-of-sight links(3)
The load, airborne time, power, and energy supply of the UAV-IRS are limited, and the height of the UAV directly affects the size of the communication coverage, while the fixed relay node does not need to consider the energy problem when deployingThe flexibility of UAV-IRS can make the deployment more convenient. However, due to the deficiency of the current battery technology, the load, airborne time, and power of the UAV-IRS are also restricted, and for the height of UAV directly affecting the coverage range of communication, energy efficiency needs to be considered in the deployment of UAV-IRS network. Therefore, this paper considers studying the minimum number of UAV-IRS deployment, which could both ensure real-time communication of users and minimize the total energy consumption of UAV.To address the technical problem of limited onboard energy due to UAV battery limitations, an intuitive approach is to use lightweight, low-power relay devices on UAVs; another effective energy-saving solution is to use an intelligent reflecting surface [6]: IRS only reflects incident signals and meets the requirement of passive relay. By adjusting the reflection coefficient, the IRS changes the phase difference of the incident electromagnetic wave, which can subtly reconfigure the signal transmission environment, improve the power of the received signal, or suppress the interference signal [7]. Since all of these surfaces used to reflect signals are passive, a small amount of energy is consumed only when the reflective surface controller needs to intelligently control the orientation of the surface. Besides, combined with its lightweight and passive nature [8], it will significantly reduce the power consumption of the UAV, thereby greatly extending the runtime of the UAV-IRS.At present, some research has been carried out on the deployment of UAV-IRS at home and abroad. In existing studies, the convex hull algorithm [9], deep Q network particle [10], swarm optimization [11], and BRB-DA [12] are used to deploy UAVs, but most of them do not consider the user’s receiving power interference. In addition, some literatures consider the special situation of interference. For example, the literature [13] only considers the deployment of two UAVs under interference conditions, but the number of UAVs is too small to be universal. Although another literature [14] considers various situations, it is assumed that the distribution of ground users is set as uniform distribution, which is not universal.To get closer to practical applications, this paper examines a spatial deployment algorithm of UAV-IRS based on the cyclick-means++ algorithm. This paper mainly considers deploying multiple UAV-IRSs in one region. Due to the difference in user density, the quality of communication varies in different hotspot areas. Therefore, UAV-IRSs need to be deployed through changes in horizontal position and height, as well as increase or reduce the number to improve the communication quality of different hotspot users. Therefore, in order to minimize UAV-IRS energy consumption and minimum relay nodes, the cyclic k-means++ algorithm is adopted; that is, given the number and location information of ground users and the maximum load number of each UAV-IRS, use the cyclic k-means++ algorithm to deduce the optimal two-dimensional position of the UAV and output the required number of UAV-IRSs and each UAV-IRS. The coverage radius of the UAV-IRS unit can be extended. In the second subproblem, the optimal altitude of the UAV is determined by optimizing the total transmission power of the UAV-IRS, and finally, the space deployment of the UAV-IRS is completed.


## 2. System Model

In the IRS-assisted cellular network system of UAV, 5G base station, UAV-IRS, and user equipment with nonideal channel conditions are regarded as communication nodes in the IRS-assisted cellular network of UAV, and UAVs in the system all carry IRS relay components. Since the location of 5G base station is known and fixed and users with nonideal channel conditions are disorderly and random, the deployment location of UAV-IRS node needs to be reasonably designed according to the location information of 5G base station and user equipment with nonideal channel conditions.As shown in Figure1, under the problem of performance degradation during communication dead zones or peak user periods, weak signals from the base station will cause connection interruption or force the user device to increase its transmitting power. To solve this problem, UAV-IRSs are deployed to provide communication services to target users and restore target user communications. In this case, the UAV carrying the IRS relaying component is positioned within the coverage of the base station as a passive aerial relay for users with nonideal channel conditions.Figure 1
The map of system model.


## 3. Analysis of UAV Optimal Hover Height

Different from the traditional fixed relay, the radio signal is reflected by UAV-IRS travels in a free space. From the most widely used air-ground communication models [15], it can be seen that the main propagation of communication signals is the line of sight or equivalent line of sight, and some are non-line-of-sight propagation through reflection and diffraction. In this paper, the model is adopted, and the expected value of the spatial path loss can be expressed as
(1)E=PLoS∙LLoS+PNLoS∙LNLoS.In the formula,LLoS and LNLoS are the average spatial path loss of line-of-sight propagation and non-line-of-sight propagation, respectively. According to the hypothesis of Friis equation, it can be expressed as
(2)LLos=20log104πdλ+ηLos,LNLos=20log104πdλ+ηNLos.In the formula,d is the straight-line distance between UAV-IRS and user, d=h2+r2; λ is electromagnetic wave length, λ=c/f; c is the speed of light; f is the carrier frequency; ηLos and ηNLos are the path loss under line-of-sight propagation and non-line-of-sight propagation, respectively.Figure2 shows the path loss relation diagram corresponding to different elevation angles of users in different urban environments.Figure 2
The calculated line-of-sight probabilities, with their relatedS-curve fitting for different urban environments.PLoS and PNLoS are the probability of line-of-sight propagation and non-line-of-sight propagation, respectively, which are related to the propagation environment coefficient and elevation angle. The probability of line-of-sight propagation can be fitted by sigmoid function and can be expressed as
(3)PLoS=PLoS,θ=11+ae−bθ−a,PNLoS=1−PLoS.In the formula,a and b are arguments to the sigmoid function; θ is the elevation angle of the user and UAV-IRS, θ=tan−1h/r, h is the vertical flight height of the UAV-IRS, and r is the distance from the user to the projection point of the horizontal position of the UAV-IRS. When the frequency of a and b is 2000 MHz, the parameters in different geographical environments can be found in Table 1.Table 1
Different environmental parameters.
Urban environmentsabηLosηNLosSuburban4.880.430.121Urban9.610.281.020Dense urban12.080.161.623Highrise urban27.230.122.334According to the literature [16], the higher the height of UAV-IRS, the larger the communication coverage area:
(4)θ=tan−1hr.Substitute the above formula to obtain(5)E=ηLos−ηNLos1+ae−btan−1h/r−a+10log10h2+r2+20log104πfc+ηNLos.According to the analysis of the formula, the average spatial path loss function of signals transmitted in air-ground channel is a nonlinear function abouth and r, according to which the signal intensity received by ground users is strictly dependent on h and r. In order to ensure the communication quality of users on the ground, it is assumed that the received power P must exceed a certain threshold Pmin, which is equivalent to the path loss of the UAV-IRS to any user must be less than or equal to a certain threshold Lth, so as to ensure the basic communication of users. When the path loss between the UAV-IRS and the user exceeds the threshold, the link is interrupted. By solving ∂r/∂h=0, the maximum coverage radius rmax and the optimal flight height h∗=rmax∙tanθ can be obtained. The optimal flight height of UAV-IRS corresponding to different path losses is shown in Figure 3. And the relationship between the height and the coverage radius is shown in Figure 4.Figure 3
The coverage zone by a low altitude platform.Figure 4
Relationship between the height and the coverage radius of UAV-IRS.


## 4. System Energy Consumption Analysis

In this section, the power consumption model of UAV-IRS auxiliary communication system is proposed. The total power consumption of the system consists of the reflected power of the base station, the power consumption of the base station hardware equipmentPBS, the power consumption PIRS of IRS, and the power consumption PUAV of the UAV.Therefore, total power consumption of the system can be expressed as(6)Pt=PS+PBS+PIRS+PUAV.The power consumption of IRS depends on the nature and resolution of the reflector for effective phase shift of the incident signal. Assuming that each reflector isI phase shifter, the power consumption of IRS composed of a reflector PIRS=NPib,i∈1,2,⋯,I is given, representing the power consumed by the circuit for a phase shifter with bit resolution. Reference [17] provides some typical values for IRS.PUAV includes the energy consumed by the UAV in flight and hovering. According to Reference [18], the power of the UAV can be expressed as
(7)PUAV=a1v3+a2v,where a1 and a2 are constants, depending on the UAV’s weight, wing size, and air density, representing the average flight speed of the UAV. Therefore, the minimum power consumption of UAV is [18]
(8)PUAVmin≜3−3/4+31/4a11/4a23/4.


## 5. Description of Algorithm

Under the assumption that users are randomly distributed and their positions are known, the path loss of downlink is taken into account, and the UAV-IRS should be in the optimal working state as far as possible under the premise of satisfying user communication quality. In this paper, since the distance between the 5G base station and UAV-IRS is much larger than that between the user and UAV-IRS, it can be assumed that the signal power reflected by each UAV-IRS is equal. This article innovatively considers capacity constraints when deploying relays. Since the working bandwidth of a single UAV-IRS is limited, in order to meet the communication quality requirements of users, each UAV-IRS serves a fixed number of users. It is assumed that the upper limit of users covered by UAV-IRS isL.According to the above situation, adjusting the flight height of UAV-IRS toh∗ allows the UAV-IRS to reach the maximum coverage radius rmax of the ground user. If the communication coverage is carried out with the maximum coverage radius, more users will be served. In the coverage area with higher user density, UAV-IRS overload will be caused; Through theoretical analysis [16], the energy loss of UAV is closely related to its coverage radius and flight altitude. Based on the above, the UAV-IRS coverage problem is transformed into an optimal coverage problem with minimum energy loss.


### 5.1. UAV Deployment Positioning Analysis

There is a horizontal projection relative distance between the relays of each UAV. If the horizontal projection relative distance between the relays of adjacent UAVs is less than the preset threshold, the UAV will move away from its neighbor UAV in order to ensure that UAVs will not excessively gather in one area and repeatedly cover a certain area. If the distance between two adjacent UAVs is greater than the threshold and smaller than the communication radius, the UAVs move to the neighbor UAV to minimize the coverage of the blind area. If the distance between two UAVs is equal to the threshold or greater than the communication radius, the relative distance between two UAVs will not affect the movement of UAVs. The deployment mode of three UAVs relay is shown in Figure5.Figure 5
Schematic diagram of multiple UAV relay deployment technology.Theoretically, when the three UAVs relayU1, U2 and U3 want to achieve optimal coverage, the area of coverage blind area O is 0 and the coverage area can be expressed as
(9)S=2∙S∆U1U2U3+SU12π−2∙∠1+SU22π−2∙∠2+SU32π−2∙∠3.When the coverage area is the largest, the relation can be deduced as(10)∠1:∠2:∠3=1r12:1r22:1r32.


### 5.2.k-Means++ Algorithm

At present, the static coverage deployment of UAV-IRS assumes that global information such as location service requirements of ground users is known, and the location of the UAV-IRS is adjusted by a centralized deployment optimization method. According to the summary of the UAV static deployment method of relay, it can be seen that most static deployment methods do not consider the load capacity of UAV-IRS and the transmission rate of a certain bandwidth; at the same time, the number of users is certain, so the load capacity is one of the important factors affecting relay deployed drones. In order to optimize transmission power, this paper investigates the spatial deployment of multiple UAVs as aerial relays considering the load capacity of UAVs.Assuming that the user distribution and location are known and considering the downlink situation, the goal is to minimize the total transmission power of UAV-IRS while meeting the quality of service requirements of the user. In addition, under the premise of user service quality and load capacity of UAV-IRS, multiple UAV-IRSs are deployed in a three-dimensional space and the height and horizontal position of each UAV are obtained. In order to determine the optimal position and coverage radius of each UAV, the 3D deployment problem was decomposed into two subproblems. In the first subproblem, given the number of ground users and location information and the maximum load number of each UAV-IRS, the circulark-means algorithm is used to deduce the optimal two-dimensional position of UAV and calculate the coverage radius of each UAV unit. In the second subproblem, the optimal height of UAV is determined by optimizing the total transmission power of UAV-IRS, and finally, the spatial deployment of UAV-IRS is completed.Algorithm 1: Deployment Algorithm.
Initialization:Initialize the initial position of the user node, and calculate the number of UAV-IRS in theory;1. A random point is selected from the input user node location and then it will be set as the first cluster center;2. For each pointx in the data set, calculate its distance Dxfrom the nearest cluster center (selected cluster center);3. A new data point is selected as the new clustering center, and the selection principle is as follows: the point with largerDx has a higher probability of being selected as the clustering center;4. Repeat steps 2 and 3 until k cluster centers are selected.5. The k initial clustering centers are used to run the standard K-means algorithm.Step 3 ReflectDx to the probability of point selection. The specific algorithm is as follows:1. Let us start with a random seed from our database;2. For each point, we calculate its straight-line distanceDx from the nearest seed point and store it in an array. Then we add up the distances to get SumDx;3. Then, a random value is taken and the next seed point is calculated in the way of weight. The algorithm is realized by taking a random value “Random” that can fall in SumDx and then using Random=−SumDx until it is not greater than 0, at which point the next seed point is taken;4. Repeat steps 2 and 3 until k cluster centers are selected;5. These k initial clustering centers are used to run the standard k-means++ algorithm.Thek-means algorithm is a typical distance-based clustering algorithm. Typically using Euclidean distance as the similarity index of clusters, data point objects are divided into K clusters, and each object is divided into the cluster nearest to the center of the cluster. The k-means algorithm first randomly determines the location of k cluster centers and then connects each user to the nearest center of mass. The centroid position is then updated by getting the Euclidean distance value for the user position connected to each centroid. Repeat this operation until the cluster center position does not change or the maximum number of iterations is reached.However, the numberk of k-means algorithm’s clustering centers needs to be given in advance, but in practice, the selection of k value is difficult to estimate. In many cases, it is not known in advance how many categories a given dataset should be divided into. The k-means require manual determination of initial cluster centers, and different initial cluster centers can lead to completely different cluster results.Therefore, according to the scenario in this paper, thek-means algorithm is improved and the k-means++ algorithm is adopted. The basic idea of selecting seeds in the k-means++ algorithm is that the distance between the initial clustering centers should be as far as possible. The deployment algorithm is described in Algorithm 1.


### 5.3. Optimal Height of UAV-IRS

After the above circulark-means++ algorithm is used to determine the projection position of UAV-IRS on the horizontal plane, the height of each UAV-IRS is determined. To minimize power, you can minimize path losses. Then, the optimization function is as follows:
(11)min∑iϵK20log4πfcri2+hi2c+PLoSηLoS−ηNLoS+ηNLoS.Figure6 simulates the relationship between coverage radius and height when UAV-IRS fc=2 GHz and path loss is 120 dB in different environments. It can be seen from Figure 4, with the increase of UAV height, coverage radius increases after the first decreases and is not a monotonic function; for a particular user, when the service environment with the UAV-IRS is determined, there is maximum coverage radius; the tow corresponding heights—the maximum and minimum height—were referred to as high domain. For a user of UAV-IRS service, each user has a height domain, and the intersection of the height domain of all users is called the total height domain. In this paper, the method of rising in the total height domain is adopted to determine the UAV-IRS height, and the height corresponding to the minimum value found is the optimal height.Figure 6
Relationship between the height and coverage radius of UAV-IRS.


### 5.4. Steps of Algorithm

The main idea of unmanned aerial vehicle passive relay spatial deployment algorithm based onk-means++ is to use the k-means++ algorithm to divide ground users into K clusters according to the load capacity of UAV-IRS to obtain the horizontal position coordinates of UAV-IRS and then optimize the height of each UAV-IRS in order to minimize transmission power and finally obtain the 3D coordinates of each UAV-IRS.The specific steps of UAV-IRS spatial deployment algorithm based onk-means++ are as follows:
(Step 1)
Enter the number of users and their location information; the maximum load number of UAV-IRS isL.(Step 2)
Use thek-means++ algorithm to divide all users into k clusters, and detect the number of users in each cluster.(Step 3)
If the number of users in the cluster is greater thanL, k=k+1, go to Step 1. If no, go to Step 4.(Step 4)
Calculate the coverage radius of each UAV-IRS; that is, the horizontal distance between the cluster center and the furthest user in the class.(Step 5)
Formula (8) is used to calculate the optimal height of each UAV-IRS.(Step 6)
Get the 3D position of each UAV-IRS.


## 5.1. UAV Deployment Positioning Analysis

There is a horizontal projection relative distance between the relays of each UAV. If the horizontal projection relative distance between the relays of adjacent UAVs is less than the preset threshold, the UAV will move away from its neighbor UAV in order to ensure that UAVs will not excessively gather in one area and repeatedly cover a certain area. If the distance between two adjacent UAVs is greater than the threshold and smaller than the communication radius, the UAVs move to the neighbor UAV to minimize the coverage of the blind area. If the distance between two UAVs is equal to the threshold or greater than the communication radius, the relative distance between two UAVs will not affect the movement of UAVs. The deployment mode of three UAVs relay is shown in Figure5.Figure 5
Schematic diagram of multiple UAV relay deployment technology.Theoretically, when the three UAVs relayU1, U2 and U3 want to achieve optimal coverage, the area of coverage blind area O is 0 and the coverage area can be expressed as
(9)S=2∙S∆U1U2U3+SU12π−2∙∠1+SU22π−2∙∠2+SU32π−2∙∠3.When the coverage area is the largest, the relation can be deduced as(10)∠1:∠2:∠3=1r12:1r22:1r32.


## 5.2.k-Means++ Algorithm

At present, the static coverage deployment of UAV-IRS assumes that global information such as location service requirements of ground users is known, and the location of the UAV-IRS is adjusted by a centralized deployment optimization method. According to the summary of the UAV static deployment method of relay, it can be seen that most static deployment methods do not consider the load capacity of UAV-IRS and the transmission rate of a certain bandwidth; at the same time, the number of users is certain, so the load capacity is one of the important factors affecting relay deployed drones. In order to optimize transmission power, this paper investigates the spatial deployment of multiple UAVs as aerial relays considering the load capacity of UAVs.Assuming that the user distribution and location are known and considering the downlink situation, the goal is to minimize the total transmission power of UAV-IRS while meeting the quality of service requirements of the user. In addition, under the premise of user service quality and load capacity of UAV-IRS, multiple UAV-IRSs are deployed in a three-dimensional space and the height and horizontal position of each UAV are obtained. In order to determine the optimal position and coverage radius of each UAV, the 3D deployment problem was decomposed into two subproblems. In the first subproblem, given the number of ground users and location information and the maximum load number of each UAV-IRS, the circulark-means algorithm is used to deduce the optimal two-dimensional position of UAV and calculate the coverage radius of each UAV unit. In the second subproblem, the optimal height of UAV is determined by optimizing the total transmission power of UAV-IRS, and finally, the spatial deployment of UAV-IRS is completed.Algorithm 1: Deployment Algorithm.
Initialization:Initialize the initial position of the user node, and calculate the number of UAV-IRS in theory;1. A random point is selected from the input user node location and then it will be set as the first cluster center;2. For each pointx in the data set, calculate its distance Dxfrom the nearest cluster center (selected cluster center);3. A new data point is selected as the new clustering center, and the selection principle is as follows: the point with largerDx has a higher probability of being selected as the clustering center;4. Repeat steps 2 and 3 until k cluster centers are selected.5. The k initial clustering centers are used to run the standard K-means algorithm.Step 3 ReflectDx to the probability of point selection. The specific algorithm is as follows:1. Let us start with a random seed from our database;2. For each point, we calculate its straight-line distanceDx from the nearest seed point and store it in an array. Then we add up the distances to get SumDx;3. Then, a random value is taken and the next seed point is calculated in the way of weight. The algorithm is realized by taking a random value “Random” that can fall in SumDx and then using Random=−SumDx until it is not greater than 0, at which point the next seed point is taken;4. Repeat steps 2 and 3 until k cluster centers are selected;5. These k initial clustering centers are used to run the standard k-means++ algorithm.Thek-means algorithm is a typical distance-based clustering algorithm. Typically using Euclidean distance as the similarity index of clusters, data point objects are divided into K clusters, and each object is divided into the cluster nearest to the center of the cluster. The k-means algorithm first randomly determines the location of k cluster centers and then connects each user to the nearest center of mass. The centroid position is then updated by getting the Euclidean distance value for the user position connected to each centroid. Repeat this operation until the cluster center position does not change or the maximum number of iterations is reached.However, the numberk of k-means algorithm’s clustering centers needs to be given in advance, but in practice, the selection of k value is difficult to estimate. In many cases, it is not known in advance how many categories a given dataset should be divided into. The k-means require manual determination of initial cluster centers, and different initial cluster centers can lead to completely different cluster results.Therefore, according to the scenario in this paper, thek-means algorithm is improved and the k-means++ algorithm is adopted. The basic idea of selecting seeds in the k-means++ algorithm is that the distance between the initial clustering centers should be as far as possible. The deployment algorithm is described in Algorithm 1.


## 5.3. Optimal Height of UAV-IRS

After the above circulark-means++ algorithm is used to determine the projection position of UAV-IRS on the horizontal plane, the height of each UAV-IRS is determined. To minimize power, you can minimize path losses. Then, the optimization function is as follows:
(11)min∑iϵK20log4πfcri2+hi2c+PLoSηLoS−ηNLoS+ηNLoS.Figure6 simulates the relationship between coverage radius and height when UAV-IRS fc=2 GHz and path loss is 120 dB in different environments. It can be seen from Figure 4, with the increase of UAV height, coverage radius increases after the first decreases and is not a monotonic function; for a particular user, when the service environment with the UAV-IRS is determined, there is maximum coverage radius; the tow corresponding heights—the maximum and minimum height—were referred to as high domain. For a user of UAV-IRS service, each user has a height domain, and the intersection of the height domain of all users is called the total height domain. In this paper, the method of rising in the total height domain is adopted to determine the UAV-IRS height, and the height corresponding to the minimum value found is the optimal height.Figure 6
Relationship between the height and coverage radius of UAV-IRS.


## 5.4. Steps of Algorithm

The main idea of unmanned aerial vehicle passive relay spatial deployment algorithm based onk-means++ is to use the k-means++ algorithm to divide ground users into K clusters according to the load capacity of UAV-IRS to obtain the horizontal position coordinates of UAV-IRS and then optimize the height of each UAV-IRS in order to minimize transmission power and finally obtain the 3D coordinates of each UAV-IRS.The specific steps of UAV-IRS spatial deployment algorithm based onk-means++ are as follows:
(Step 1)
Enter the number of users and their location information; the maximum load number of UAV-IRS isL.(Step 2)
Use thek-means++ algorithm to divide all users into k clusters, and detect the number of users in each cluster.(Step 3)
If the number of users in the cluster is greater thanL, k=k+1, go to Step 1. If no, go to Step 4.(Step 4)
Calculate the coverage radius of each UAV-IRS; that is, the horizontal distance between the cluster center and the furthest user in the class.(Step 5)
Formula (8) is used to calculate the optimal height of each UAV-IRS.(Step 6)
Get the 3D position of each UAV-IRS.


## 6. Results and Discussion

In this chapter, Python software is adopted to simulate the spatial deployment algorithm of UAV-IRS based onk-means++. The task area is a square area with side length of 1 km. Two different users are distributed in different ways in this area, and the simulation experiment of UAV-IRS deployment is carried out. Table 2 shows some experimental parameters.Table 2
Simulation parameters.
ParametersValuea9.61b0.28ηLos1.0 dBηNLos20 dBC (m/s)3.0e+8Iterations1000Maximum number of UAV-IRS service users50


### 6.1. Analysis of Simulation Results of CK++

In this section, it is assumed that mobile users are randomly distributed on the ground, and 400 groups of 2D ground movement coordinates are generated within1km∗1km by random function. The Ck++ algorithm is used to calculate this data set, as shown in Figure 7, and the algorithm deployment result is obtained. The ground mobile users are represented by different colored dots, and different colors represent different clusters. The multicolored pentagonal star in the center represents the two-dimensional deployment position of UAV-IRS, and the coverage area of each UAV-IRS is represented by a red circle.Figure 7
400 users are distributed in the task area. (a) 2D position of UAV-IRSs and ground user. (b) The space position of UAV-IRSs.
(a)(b)The theoretical initialK value for UAV-IRS deployment is 8, but the actual result is that 14 UAV-IRSs are required in the area to provide communications services. It can be seen that the service coverage radius of each UAV-IRS is not equal, because the total number of users aggregated by each cluster after clustering is different and the two-dimensional distribution position is different. Each user is provided relay service by the nearest UAV-IRS. The number of UAV-IRS deployments in the areas with higher user density is significantly higher than that in the areas with lower user density. This is because when the user density is higher, the resources of UAV-IRS are already utilized by the nearest users, resulting in its inability to serve further users. In addition, in the left side of the low-density area, the higher the height, the more users can improve the relay service.


### 6.2. Compared with Traditionalk-Means Clustering Algorithm

In this section, it is assumed that mobile users are randomly distributed on the ground, and 300 groups of coordinates are generated within1km∗1km by random function. The dataset was calculated by the k-means clustering algorithm and Ck++ algorithm, respectively, as shown in Figures 8 and 9, two different algorithm deployment results are obtained, and the 2D coordinates of UAV-IRS deployment as well as the 3D deployment coordinates of coverage and UAV-IRS are drawn, respectively. The black dots in Figure 8(a) represent edge users not covered by UAV-IRS.Figure 8
k-means algorithm results. (a) 2D position of UAV-IRSs and ground user. (b) The space position of UAV-IRSs.
(a)(b)Figure 9
CK++ algorithm results. (a) 2D position of UAV-IRSs and ground user. (b) The space position of UAV-IRSs.
(a)(b)As can be seen from Figure8, the number of UAV-IRS deployed using the Ck++ algorithm is 6, and the coverage rate is less than 100%. As the k value of the k-means algorithm is fixed, the relay service for edge users cannot be provided, so some users still cannot communicate normally.As it can be seen from Figure9, the number of UAV-IRS deployed using the Ck++ algorithm is two more than the k-means, but the coverage rate reaches 100%. This is because the Ck++ algorithm optimizes the initial clustering center during initialization and circulates clustering by increasing k value when the UAV-IRS service is found to be full.As can be seen from Figure10, the relation curves between user density and coverage of the two algorithms are drawn. As the number of users gradually increases, that is, the coverage of the k-means clustering algorithm is getting lower and lower. It can be seen that in the scenario of high user density, the coverage of the Ck++ algorithm is better than that of the traditional k-means clustering algorithm.Figure 10
Comparison of coverage betweenk-means and CK++.


### 6.3. Compared with Divide-and-Conquer Algorithm

In this section, it is assumed that mobile users are randomly distributed on the ground, and different numbers of user coordinates are generated within1km∗1km through random functions. The divide-and-conquer algorithm proposed in this paper and the drone based on the Ck++ algorithm also consider the trunk deployment method under the premise that the UAV relay load capacity and ground users are fully covered. The basic idea of the divide-and-conquer algorithm is that when the total number of users in a cluster is detected to be greater than the maximum load number of UAV-IRS, it is similar to dividing the cluster into four clusters by cell division. As can be seen from Figure 11, with the gradual increase of the number of users, namely, the increasing user density, both algorithms meet the communication requirements of ground mobile users by increasing the number of UAV-IRS deployment. However, the number of UAV-IRS deployed by the Ck++ algorithm proposed in this paper is always less than that of the divide-and-conquer algorithm. In terms of saving the number of UAV-IRS deployments, the Ck++ algorithm proposed in this chapter is superior to the divide-and-conquer algorithm in the same case.Figure 11
Relationship between the number of USERS of divide-and-conquer and CK++ and the number of UAV-IRS deployments.


## 6.1. Analysis of Simulation Results of CK++

In this section, it is assumed that mobile users are randomly distributed on the ground, and 400 groups of 2D ground movement coordinates are generated within1km∗1km by random function. The Ck++ algorithm is used to calculate this data set, as shown in Figure 7, and the algorithm deployment result is obtained. The ground mobile users are represented by different colored dots, and different colors represent different clusters. The multicolored pentagonal star in the center represents the two-dimensional deployment position of UAV-IRS, and the coverage area of each UAV-IRS is represented by a red circle.Figure 7
400 users are distributed in the task area. (a) 2D position of UAV-IRSs and ground user. (b) The space position of UAV-IRSs.
(a)(b)The theoretical initialK value for UAV-IRS deployment is 8, but the actual result is that 14 UAV-IRSs are required in the area to provide communications services. It can be seen that the service coverage radius of each UAV-IRS is not equal, because the total number of users aggregated by each cluster after clustering is different and the two-dimensional distribution position is different. Each user is provided relay service by the nearest UAV-IRS. The number of UAV-IRS deployments in the areas with higher user density is significantly higher than that in the areas with lower user density. This is because when the user density is higher, the resources of UAV-IRS are already utilized by the nearest users, resulting in its inability to serve further users. In addition, in the left side of the low-density area, the higher the height, the more users can improve the relay service.


## 6.2. Compared with Traditionalk-Means Clustering Algorithm

In this section, it is assumed that mobile users are randomly distributed on the ground, and 300 groups of coordinates are generated within1km∗1km by random function. The dataset was calculated by the k-means clustering algorithm and Ck++ algorithm, respectively, as shown in Figures 8 and 9, two different algorithm deployment results are obtained, and the 2D coordinates of UAV-IRS deployment as well as the 3D deployment coordinates of coverage and UAV-IRS are drawn, respectively. The black dots in Figure 8(a) represent edge users not covered by UAV-IRS.Figure 8
k-means algorithm results. (a) 2D position of UAV-IRSs and ground user. (b) The space position of UAV-IRSs.
(a)(b)Figure 9
CK++ algorithm results. (a) 2D position of UAV-IRSs and ground user. (b) The space position of UAV-IRSs.
(a)(b)As can be seen from Figure8, the number of UAV-IRS deployed using the Ck++ algorithm is 6, and the coverage rate is less than 100%. As the k value of the k-means algorithm is fixed, the relay service for edge users cannot be provided, so some users still cannot communicate normally.As it can be seen from Figure9, the number of UAV-IRS deployed using the Ck++ algorithm is two more than the k-means, but the coverage rate reaches 100%. This is because the Ck++ algorithm optimizes the initial clustering center during initialization and circulates clustering by increasing k value when the UAV-IRS service is found to be full.As can be seen from Figure10, the relation curves between user density and coverage of the two algorithms are drawn. As the number of users gradually increases, that is, the coverage of the k-means clustering algorithm is getting lower and lower. It can be seen that in the scenario of high user density, the coverage of the Ck++ algorithm is better than that of the traditional k-means clustering algorithm.Figure 10
Comparison of coverage betweenk-means and CK++.


## 6.3. Compared with Divide-and-Conquer Algorithm

In this section, it is assumed that mobile users are randomly distributed on the ground, and different numbers of user coordinates are generated within1km∗1km through random functions. The divide-and-conquer algorithm proposed in this paper and the drone based on the Ck++ algorithm also consider the trunk deployment method under the premise that the UAV relay load capacity and ground users are fully covered. The basic idea of the divide-and-conquer algorithm is that when the total number of users in a cluster is detected to be greater than the maximum load number of UAV-IRS, it is similar to dividing the cluster into four clusters by cell division. As can be seen from Figure 11, with the gradual increase of the number of users, namely, the increasing user density, both algorithms meet the communication requirements of ground mobile users by increasing the number of UAV-IRS deployment. However, the number of UAV-IRS deployed by the Ck++ algorithm proposed in this paper is always less than that of the divide-and-conquer algorithm. In terms of saving the number of UAV-IRS deployments, the Ck++ algorithm proposed in this chapter is superior to the divide-and-conquer algorithm in the same case.Figure 11
Relationship between the number of USERS of divide-and-conquer and CK++ and the number of UAV-IRS deployments.


## 7. Conclusion

In this paper, the optimal space deployment of UAV passive relay is solved under the premise of considering UAV relay load capacity. Firstly, a multi-UAV-IRS network coverage user system model was established, and an unmanned aerial vehicle passive relay spatial deployment algorithm based on Ck++ was proposed. Then, based on the deficiency of the traditionalk-means clustering algorithm, the Ck++ algorithm was proposed to obtain the two-dimensional coordinates and coverage radius of each UAV, and then the optimal hovering height of UAV-IRS was calculated with the coverage radius. Finally, being compared with the traditional k-means clustering algorithm, it was shown that the proposed algorithm had a better coverage. Then, on the premise of all users being covered, the UAV load ability of the proposed algorithm with the same partition algorithm on the basis of the comparison was considered. After using the deployment of less UAV, the feasibility of the partition algorithm was proved.



---

*Source: 7916305-2022-09-05.xml*