Aerospace Science and Technology 143 (2023) 108731

Contents lists available at ScienceDirect

Aerospace Science and Technology

journal homepage: www.elsevier.com/locate/aescte

3D deployment of UAV-mounted base stations for heterogeneous access

requirements
Xiaolin Ai a , Zhiqiang Pu a,b,∗ , Xinghua Chai c , Jinlin Lei d,∗∗ , Jianqiang Yi a,b
a Institute of Automation, Chinese Academy of Sciences, Beijing, 100190, China
b School of Artificial Intelligence, University of Chinese Academy of Sciences, Beijing, 100049, China
c 54th Research Institute of China Electronics Technology Group Corporation, Shijiazhuang, 050081, China
d Electronic Information Engineering College, Beihang University, Beijing 100191, China

A R T I C L E I N F O A B S T R A C T

Communicated by Roberto Sabatini Recently, unmanned aerial vehicles (UAVs) have been reported a lot as aerial base stations (BSs) to assist wireless
communication in Internet of Things (IoT). However, most results for UAV deployment require uniform access
Keywords:
requirements and obstacle-free environment. This paper considers multi-UAV-mounted BSs deployment problem
Three-dimensional (3D) deployment
Multi-UAV-mounted base stations (BSs) in obstacle-laden environment to achieve on-demand coverage for ground user equipments (UEs), with the goal
Non-uniform quality of service (QoS) of minimizing the number of required UAVs for full coverage of all UEs by optimizing the three-dimensional (3D)
requirements positions of UAVs as well as UE clustering. On one hand, the considered problem is challenging as the constraints
Obstacle avoidance on the non-uniform Quality of Service (QoS) requirements, the service ability of each UAV, the beamwidth of
the directional antenna equipped by each UAV and obstacle avoidance are jointly taken into account. On the
other hand, these practical considerations contribute to broadening the scope of applications. We formulate the
problem as a mixed-integer programming problem and develop a three-step placement algorithm to achieve the
goal. First, the maximum allowed service radius of each UE is derived based on the Karush-Kuhn-Tucker (KKT)
condition to satisfy required signal-to-interference-plus-ratio (SINR) threshold. Second, a greed-prior chaotic
search enabled adaptive artificial bee colony (GP-CA2 BC) algorithm is proposed to group the UEs such that the
minimum number of required UAVs can be obtained. Third, the 3D position of each UAV is optimized to further
enhance the QoS. Finally, some simulation results are presented to demonstrate the superiority of the proposed
scheme in decreasing the number of required UAVs as well as improving the QoS compared with the existing
works.

1. Introduction BSs to assist wireless communication networks, especially to establish

emergence networks. The motivation behind this focus mainly lies in
With the explosive increase of the number of ground user equip- that thanks to the cost-effectiveness and high maneuverability [3–5],
ments (UEs) in Internet of Things (IoT), it is becoming great challenging UAV-mounted BSs can be quickly deployed to cover large and scattered
for terrestrial networks to satisfy the diversified access requirements target areas with reduced labor costs while providing better Quality of
nowadays. Examples are the difficult-to-reach or disaster-affected areas Service (QoS) for ground UEs with a higher probability of establishing
where terrestrial base stations (BSs) cannot be efficiently deployed to Line of Sight (LoS) links [6–12]. Moreover, compared to ground BSs,
provide guaranteed communication service [1,2]. Thus, there is an ur- UAV-mounted BSs are also more flexible to satisfy the non-uniform ac-
gent need for rapidly deployable cellular networks to achieve flexible cess requirements of various UEs. These merits make UAV-mounted BSs
and on-demand coverage ability. become promising techniques in the field of IoT and how to optimally
Recently, with the development of unmanned aerial vehicles deploy the UAVs to achieve on-demand coverage for ground UEs is the
(UAVs), it has observed a paradigm shift toward using UAVs as aerial fundamental issue worthing much attention.

* Corresponding author at: Institute of Automation, Chinese Academy of Sciences, Beijing, 100190, China.
** Corresponding author.
E-mail addresses: [email protected] (Z. Pu), [email protected] (J. Lei).

https://doi.org/10.1016/j.ast.2023.108731
Received 6 July 2022; Received in revised form 17 June 2023; Accepted 10 November 2023
Available online 17 November 2023
1270-9638/© 2023 Elsevier Masson SAS. All rights reserved.
X. Ai, Z. Pu, X. Chai et al. Aerospace Science and Technology 143 (2023) 108731

1.1. Related works may be practically non-uniform because of different features of ground
UEs, leading to non-uniform SINR constraints. Secondly, the UAVs may
1.1.1. Single UAV deployment be equipped with directional antennas to further enhance the QoS for
In general, UAV-mounted BSs are not particularly new and have UEs, under which situation the constraint on beamwidth notably affects
been used for many years in the field of IoT. Several attempts have the efficient coverage region and should be considered in the algo-
been made to develop the deployment algorithms from various typical rithm development. Finally, the ground UEs may be distributed in dense
topics. Early works mainly focused on exploring the deployment of a and complex environment such that the UAVs must be deployed in the
single UAV in the literature. The authors in [13] firstly established a obstacle-free areas to ensure safety. These challenges raise difficulty on
statistical propagation model for predicting the air-to-ground path loss the algorithm development and too little work has been reported to
between a low altitude platform (LAP) and a terrestrial BS, based on place multi-UAV-mounted BSs under these challenging scenarios.
which they further provided an analytical approach in [14] to optimize Motivated by the above observations, this paper intends to place as
the altitude of LAPs to achieve maximum coverage on the ground UEs. few as possible UAVs to achieve full coverage for all ground UEs with
In [15], the authors formulated the 3D drone-cell placement problem non-uniform SINR requirements in a 3D obstacle-laden environment,
as a quadratically-constrained mixed integer nonlinear programming while taking into consideration of the constraints on the beamwidth of
problem and proposed a computationally efficient numerical solution to antenna and the number of covered UEs by each UAV (service ability).
it. An optimal placement algorithm was presented in [16] to maximize A comprehensive comparison between this study and the related works
the number of covered UEs by decoupling the 3D UAV-BS deployment is detailedly discussed in Table 1. The main contributions of this article
problem in the vertical and horizontal dimension. The authors in [17] are as follows.
optimized the UAV-BS 3D location based on the gradient descent algo- 1) We formulate the 3D deployment problem incorporating the con-
rithm to cover ground UEs with minimum energy consumption. straints on the non-uniform SINR requirements, the service ability of
each UAV, the beamwidth of the directional antenna equipped by each
1.1.2. Multi-UAV 2D deployment UAV and obstacle avoidance as a mixed-integer programming problem
Using only a single UAV with limited energy capacity to assist the with NP-hard complexity.
wireless communication networks may be challenging due to the un- 2) We propose a three-step placement algorithm, consisting of max-
even distribution and the non-uniform QoS requirements of UEs. Recent imum allowed service radius determination, UE clustering and 3D posi-
studies have reported that multi-UAV-mounted BSs consisting of a large
tion deployment, to solve the considered problem. To be specific, in the
number of low-cost UAVs can efficiently complete on-demand coverage
first step, the maximum allowed service radius is theoretically derived
in these challenging scenarios [18–23]. The authors in [24] proposed a
based on the KKT condition for each UE such that the constraint on the
highly energy-efficient deep reinforcement learning-based approach for
SINR can be transfer to that on the service radius; given the maximum
a group of UAVs with joint consideration of communication coverage,
allowed service radius, a greed-prior chaotic search enabled adaptive
fairness, energy consumption and connectivity. To guarantee full cover-
artificial bee colony (GP-CA2 BC) algorithm is proposed in the second
age of all ground UEs, the authors in [25] proposed a polynomial-time
step to realize UE clustering with the constraint on the UAV’s service
algorithm to place the UAVs sequentially starting on the edge of the tar-
ability, under which the minimum number of required UAVs are deter-
get area along a spiral path toward the center such that all UEs could
mined; the third step finally optimizes the 3D positions for UAVs using
be successfully covered by minimum number of UAVs. Similarly, the
CA2 BC to further improve the QoS for UEs.
elephant herding optimization algorithm was applied in [26] to estab-
3) The superiority of the proposed algorithm is demonstrated
lish monitoring of all targets with the least possible number of UAVs.
through simulations, showing that compared with the benchmarks, the
In [27], the authors constructed UAV-based airborne networks for on-
presented scheme can significantly reduce the number of required UAVs
ground users with the constraint on the maximum number of UEs served
for full coverage of UEs while enhancing the QoS.
by each UAV while reducing the number the required number of UAVs.
Thereafter, the authors extended the results in [27] to maximize the
1.3. Organization
load balance among UAVs with on-demand coverage in [28].

1.1.3. Multi-UAV 3D deployment The rest of the paper is organized as follows. In Section 2, the system
Recognizing that UAV-mounted BSs can be placed at a higher alti- model is introduced based on which the considered problem is formu-
tude to provide enhanced QoS for ground UEs, several attempts have lated for multi-UAV BSs deployment. Section 4 provides our placement
been made to consider the 3D deployment of UAVs [30–33]. In [34], algorithm to address the considered problem. In Section 5, we give some
the circle packing theory was utilized to determine the 3D locations simulation results to demonstrate the superiority of our algorithm. Fi-
of UAVs aiming to maximize the total coverage area and the coverage nally, Section 6 concludes the paper.
lifetime. The authors in [35] proposed an edge-prior 3D placement al-
gorithm to minimize the number of required UAVs with limited service 1.4. Notation
ability while guaranteeing full coverage of all ground UEs subject to
a given signal-to-interference-plus-noise ratio (SINR) threshold. There- In the paper, let 𝑎, 𝒂 and , respectively, represent a scalar, a vector
after, they considered to further enhance the QoS for UEs by optimizing and a set. ℝ𝑀×𝑁 denotes the 𝑀 ×𝑁 -dimensional space of real numbers.
the 3D positions of UAVs as well as the frequency band allocation The operator ‖𝒂‖ stands for the standard Euclidean norm of vector 𝒂.
in [29]. In [36], the 3D placement and resource allocation of UAV- Given two sets 1 and 2 , 1 ⊆ 2 indicates that 1 is a subset of 2 ;
mounted BSs in an uplink IoT network were investigated with joint and operation 1 ⧵ 2 excludes the elements of 2 from 1 . Moreover,
consideration of the limited channel resource and the SINR constraint. notations || and ∅ stand for the cardinality of set  and an empty set,
The authors in [37] aimed to maximize energy efficiency of a UAV- respectively.
enabled cloud network by minimizing the number of needed UASs while
minimizing the cost associated with servicing the UEs under some QoS 2. Preliminaries
constraints.
In this paper, the main objective is to deploy UAVs in 3D space
1.2. Motivation and contributions to provide communication access service for 𝐾 ground UEs. Let  =
{1, 2, … , 𝐾} represent the set{of UEs which are randomly distributed }
Despite of the recent advances in multi-UAV-mounted BSs, there still in a 2D rectangular area  = (𝑥, 𝑦) |𝑥min ≤ 𝑥 ≤ 𝑥max , 𝑦min ≤ 𝑦[ ≤ 𝑦max] ,
remain some key challenges to be desired. Firstly, the QoS requirements and each UE 𝑘 ∈  is assumed to have a fixed location 𝝎𝑘 = 𝑥𝑘 , 𝑦𝑘 ∈

2
X. Ai, Z. Pu, X. Chai et al. Aerospace Science and Technology 143 (2023) 108731

Table 1
A comprehensive comparison between this paper and the related works.

Scenario Reference Main objective 3D deployment Service ability SINR threshold Beamwidth constraint Obstacle avoidance

Lyu [25] Minimizing the number of UAVs

No No No No No
for full coverage of all UEs
Strumberger [26]
Zhao [27] Minimizing the number of UAVs No Yes Uniform No No
with guaranteed connectivity
Wang [28] Minimizing the number of UAVs No Yes Uniform No No
while maximizing the load balance

Multi-UAV Mozaffari [34] Maximizing the coverage area and Yes No No No No

placement coverage lifetime of UAVs
Qin [35] Minimizing the number of UAVs Yes Yes No No No
for full coverage of all UEs
Zhang [29] Yes Yes Uniform No No
Liu [36] Minimizing the total transmission Yes No Uniform No No
power with limited channel
resources
Nouri [37] Minimizing the number of UAVs Yes No Uniform No No
and the cost associated with
serving the UEs
This paper Minimizing the number of UAVs Yes Yes Non-uniform Yes Yes
for full coverage of all UEs

Fig. 1. Existing works.

. We intend to place 𝑀 UAVs to cover all UEs. Let  = {1, 2, … , 𝑀}

represent the set of UAVs, which should be placed in a 3D area
{ }
 = (𝑥, 𝑦, ℎ) |𝑥min ≤ 𝑥 ≤ 𝑥max , 𝑦min ≤ 𝑦 ≤ 𝑦max , ℎ[ min ≤ ℎ ≤ ℎ
] max , and
the position of each UAV is denoted by 𝒑𝑚 = 𝑥𝑚 , 𝑦𝑚 , ℎ𝑚 ∈  . With
the consideration of the resource limitation for UAVs, the service abil-
ity of UAVs is restricted by 𝑁max , which indicates that the maximum
number of UEs served by each UAV should be no more than 𝑁max .
To provide better insight on the considered problem, the channel
model of wireless communication, which plays a key role in IoT, should
be established in advance [38–40]. We consider a downlink wireless
communication systems between UAVs and UEs, where the UAV is
equipped with a directional antenna with equal azimuth and elevation
half-power beamwidths denoted by 𝜙 [41] and each UE is equipped
with an omni-directional antenna. Thereby, as illustrated in Fig. 2, the
maximum service radius of UAV 𝑚 corresponds to a disk region of ra-
dius 𝑟𝑚 = ℎ𝑚 tan 𝜙 with center on the UAV horizontal projection. Fig. 2. The considered multi-UAV assisting communication scenario.
As UAVs are deployed in an obstacle-laden environment such as
buildings and plants, the link between UAVs and UEs may be blocked
by obstacles and this leads to a mixture of LOS and NLoS channels. As
( ) 1
presented in [42], the probability of existing an LOS link between UAV 𝑃LoS 𝜃𝑚,𝑘 = ( ( )) (1)
𝑚 and UE 𝑘 can be determined by 1 + 𝑎 exp −𝑏 180
𝜋
𝜃𝑚,𝑘 − 𝑎

3
X. Ai, Z. Pu, X. Chai et al. Aerospace Science and Technology 143 (2023) 108731

ℎ𝑚 ℎ𝑚
where 𝜃𝑚,𝑘 = arctan = arctan √ denotes the eleva- constraint (5b) determines the value of the indicator function 𝛾𝑚,𝑘 ; con-
𝑑𝑚,𝑘
(𝑥𝑚 −𝑥𝑘 )2 +(𝑦𝑚 −𝑦𝑘 )2 straint (5c) indicates that each UE must be served by one UAV to ensure
tion angle between UAV 𝑚 and UE 𝑘 as shown in Fig. 1, and 𝑎 and 𝑏 full coverage of all UEs; constraint (5d) confines the service ability of
denote the modeling parameters related to the environment (see [15] UAVs such that the number of UEs served by each UAV should be no
for more (details).
) Subsequently,
( )the probability of a NLoS link is given more than 𝑁max ; and constraint (5e) means that the link between UAV
by 𝑃NLoS 𝜃𝑚,𝑘 = 1 − 𝑃LoS 𝜃𝑚,𝑘 . With these circumstances, the large- 𝑚 and UE 𝑘 can be successfully established only when the SINR require-
scale channel coefficient of the link between UAV 𝑚 and UE 𝑘 can be ment is satisfied.
modeled as [42] As the SINR of each UE is coupled with the relative distance between
{
( ) 𝛽0 𝑠−𝛼 LoS link the UAV and the UE, it raises challenging difficulty in determining the
𝛽𝑚,𝑘 𝑠𝑚,𝑘 = 𝑚,𝑘 (2) optimal solution to problem (5). To simplify the original problem, we
𝜅𝛽0 𝑠−𝛼
𝑚,𝑘
NLoS link
can convert the SINR constraint into the distance constraint. It can be
where 𝛽0 is the path loss at the reference distance of one meter for seen from (4), the SINR involves the power of the transmit signal 𝑃𝑡 ,
LoS link, 0 < 𝜅 < 1 denotes the additional attenuation factor due to the the power of the additive white Gaussian noise 𝜎 2 and the interference
NLoS propagation, 𝛼 is the modeling parameter related to the path loss, power 𝐼𝑘 . As demonstrated in [29], the power of the transmit signal
√ 𝑑𝑚,𝑘 and the upper bound of the white Gaussian noise can be specified in
and 𝑠𝑚,𝑘 = ℎ2𝑚 + 𝑑𝑚,𝑘
2 = represents the distance between UAV
cos 𝜃𝑚,𝑘 advance, and the interference power can be neglected by allocating dif-
𝑚 and UE 𝑘. ferent frequency bands for UAVs. In line with these circumstances, it is
With the facts presented above, we can define the channel gain be- reasonable to transfer the SINR constraint to a constraint on the chan-
tween UAV 𝑚 and UE 𝑘 as follows: nel gain 𝑔𝑚,𝑘 , i.e., 𝑔𝑚,𝑘 ≥ 𝑔̄𝑘 with 𝑔̄𝑘 being the channel gain threshold at
( ) ( ) ( ) UE 𝑘. Then problem (5) can be concerted into the following problem:
𝑔𝑚,𝑘 𝑠𝑚,𝑘 , 𝜃𝑚,𝑘 = 𝑃LoS 𝜃𝑚,𝑘 𝛽0 𝑠−𝛼
𝑚,𝑘 + 𝑃NLoS 𝜃𝑚,𝑘 𝜅𝛽0 𝑠𝑚,𝑘
−𝛼
(3)
Subsequently, we can refer to SINR of each UE as the index of QoS given min || (6)
{𝒑𝑚 },{𝛾𝑚,𝑘 }
by
s.t. 𝒑𝑚 ∈  ⧵  (6a)
𝑃𝑚,𝑘 𝑔𝑚,𝑘 × 𝑃𝑡
𝐸𝑚,𝑘 = = (4)
𝛾𝑚,𝑘 ∈ {0, 1}, ∀𝑘 ∈ , ∀𝑚 ∈  (6b)
𝐼𝑘 + 𝜎 2 𝐼𝑘 + 𝜎 2
∑
where 𝑃𝑚,𝑘 denotes the received power at UE 𝑘, 𝑃𝑡 is the power of the 𝛾𝑚,𝑘 = 1, ∀𝑘 ∈  (6c)
transmit signal, 𝜎 2 stands for the power of the additive white Gaussian 𝑚∈
∑
noise, and 𝐼𝑘 represents the interference power at UE 𝑘. Practically, 𝛾𝑚,𝑘 ≤ 𝑁max , ∀𝑚 ∈  (6d)
only when 𝐸𝑚,𝑘 ≥ 𝐸̄ 𝑘 is achieved, the communication link between UE 𝑘∈
𝑘 and UAV 𝑚 can be successfully established, where 𝐸̄ 𝑘 denotes the
𝑔𝑚,𝑘 ≥ 𝛾𝑚,𝑘 𝑔̄𝑘 , ∀𝑘 ∈ , ∀𝑚 ∈  (6e)
threshold of the allowable SINR for UE 𝑘. It should be noted that the
considered SINR threshold is non-uniform as the access requirements It should be noted that the considered problem involves continuous
of different UEs may be practically heterogeneous. Moreover, to ensure variables and integer variables, and thereby it belongs to a mixed-
full coverage of all UEs, we assume that the SINR constraint 𝐸𝑚,𝑘 ≥ 𝐸̄ 𝑘 integer programming problem with NP-hard complexity. As is known,
for each UE can be satisfied when the UAV is deployed at the minimum it is of great challenges to determine optimal solutions to NP-hard
altitude ℎmin . problems [43]. This paper will provide a suboptimal solution to the
considered deployment problem (5).
3. Problem formulation
4. Algorithm development
To model the considered multi-UAV placement problem, we firstly
define an indicator function 𝛾𝑚,𝑘 to determine the connection between 4.1. Overview of the proposed algorithm
UAV 𝑚 and UE 𝑘. To be specific, if UE 𝑘 is served by UAV 𝑚, then
𝛾𝑚,𝑘 = 1 and 𝛾𝑚,𝑘 = 0 otherwise. This section provides a three-step deployment algorithm to address
This paper aims to use the minimum number of UAVs to provide problem (6) as illustrated in Fig. 3. As the primary goal of the paper
full coverage of all UEs with the constraints on the SINR and the ser- is to deploy as less UAVs as possible to realize full coverage of UEs,
vice ability of UAVs. Moreover, to ensure a safe deployment, the UAVs UAVs are encouraged to cover the UE at its maximum allowed ser-
should be placed far away from obstacles. Let  ⊆  be the 3D space vice radius where the channel gain constraint is satisfied. Therefore,
occupied by the obstacles, and then the feasible deployment space is de- the maximum allowed service radius 𝑟∗𝑘 of each UE is firstly derived
termined by  ⧵ , In the considered multi-UAV deployment problem, such that the channel gain constraint in (6e) can be converted into the
the positions of UAVs and the connection between UAVs and UEs are distance constraint, i.e. 𝑑𝑚,𝑘 ≤ 𝛾𝑚,𝑘 𝑟∗𝑘 . Then, the UEs are classified into
jointly optimized in this paper as follows: { { }}
several groups 𝑚 = 𝑘 ∈ |𝛾𝑚,𝑘 = 1 by a clustering algorithm ac-
cording to the maximum allowed service radius such that the minimum
min || (5)
{𝒑𝑚 },{𝛾𝑚,𝑘 } number of UAVs can be { obtained
} to ensure full coverage of all UEs. Fi-
nally, the 3D positions 𝒑𝑚 of UAVs are determined to further improve
s.t. 𝒑𝑚 ∈  ⧵  (5a)
the QoS.
𝛾𝑚,𝑘 ∈ {0, 1}, ∀𝑘 ∈ , ∀𝑚 ∈  (5b)
∑ 4.2. Maximum allowed service radius
𝛾𝑚,𝑘 = 1, ∀𝑘 ∈  (5c)
𝑚∈
∑ We define the maximum allowed service radius 𝑟∗𝑘 , 𝑘 ∈  as the
𝛾𝑚,𝑘 ≤ 𝑁max , ∀𝑚 ∈  (5d)
largest 2D distance between UAV 𝑚 and UE 𝑘 such that the constraint
𝑘∈
𝑔𝑚,𝑘 ≥ 𝑔̄𝑘 is achieved. Then, according to (1)-(3), the problem of maxi-
𝐸𝑚,𝑘 ≥ 𝛾𝑚,𝑘 𝐸̄ 𝑘 , ∀𝑘 ∈ , ∀𝑚 ∈  (5e) mizing the allowed service radius can be formulated as follows:
where the cost function (5) is to minimize the number of deployed
UAVs; constraint (5a) restricts the feasible space of UAVs’ positions; min − 𝑟𝑘 (7)
𝑟𝑘 ,𝜃𝑘

4
X. Ai, Z. Pu, X. Chai et al. Aerospace Science and Technology 143 (2023) 108731

Fig. 3. The flow chart of the proposed algorithm.

( ( )) ( )−𝛼
1 + 𝑎𝜅 exp −𝑏 180 𝜃 −𝑎 𝜕𝑔𝑘∗ 𝛽0 𝑟∗𝑘 ∕ cos 𝜃𝑘∗
𝜋 𝑘 𝛽0 𝑟−𝛼
𝑘 =
s.t. 𝑔̄𝑘 − ( ( )) ⋅ ( )−𝛼 ≤ 0 (7a) 𝜕𝜃𝑘∗ (1 + 𝑎 exp (Θ∗ ))2
1 + 𝑎 exp −𝑏 180 𝜃 − 𝑎 cos 𝜃𝑘 𝑘
𝜋 𝑘 ⏟⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏟⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏟
( )
ℎmin − 𝑟𝑘 tan 𝜃𝑘 ≤ 0 (7b) 𝑔1 𝑟∗𝑘 ,𝜃𝑘∗
( ( ) ( ( )) ( ( )))
180
𝑟𝑘 tan 𝜃𝑘 − ℎmax ≤ 0 (7c) ⋅ (1−𝜅) 𝑎𝑏 exp Θ∗𝑘 −𝛼 tan 𝜃𝑘∗ 1+𝑎𝜅 exp Θ∗𝑘 1+𝑎 exp Θ∗𝑘
𝜋
⏟⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏟⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏟
𝜋∕2 − 𝜙 − 𝜃𝑘 ≤ 0 (7d) ( )
𝑔2 𝜃𝑘∗
𝜃𝑘 − 𝜋∕2 ≤ 0 (7e)
(11)
( )
Problem (7) can be solved according to the KKT condition. The La- 180 ∗
Θ∗𝑘 = −𝑏 𝜃 −𝑎 (12)
grange function can be described by: 𝜋 𝑘
( ) According to (8k), if > 0 then 𝜆∗5 𝜃𝑘∗
= 𝜋∕2, which indicates that
𝐿 𝑟𝑘 , 𝜃𝑘 , 𝜆1 , 𝜆2 , 𝜆3 , 𝜆4 , 𝜆5
𝑟∗𝑘 approaches zero. Therefore, 𝜆∗5 = 0 should be satisfied all the time.
( ( ))
⎡ ⎤ Moreover, if 𝜆∗2 > 0 and 𝜆∗3 > 0 then ℎmin = 𝑟∗𝑘 tan 𝜃𝑘∗ = ℎmax holds, which
⎢ 1 + 𝑎𝜅 exp −𝑏 180
𝜋 𝑘
𝜃 −𝑎 𝛽0 𝑟−𝛼 ⎥
= −𝑟𝑘 + 𝜆1 ⎢𝑔̄𝑘 − ( ( )) ⋅ (
𝑘
)−𝛼 ⎥ contradicts with the fact ℎmax > ℎmin . Similarly, if 𝜆∗4 > 0 and 𝜆∗5 > 0
⎢ 180
1 + 𝑎 exp −𝑏 𝜋 𝜃𝑘 − 𝑎 cos 𝜃𝑘 ⎥ (8) then 𝜋∕2 − 𝜙 = 𝜃𝑘∗ = 𝜋∕2 holds, which is also invalid. Then, the optimal
⎣ ⎦ value of 𝑟∗𝑘 and 𝜃𝑘∗ can be derived case by case as follows:
( ) ( )
+ 𝜆2 ℎmin − 𝑟𝑘 tan 𝜃𝑘 + 𝜆3 𝑟𝑘 tan 𝜃𝑘 − ℎmax Case 1: If 𝜆∗2 = 𝜆∗3 = 𝜆∗4 = 0, then equations (8l) and (8m) can be
( ) ( ) rewritten as:
+ 𝜆4 𝜋∕2 − 𝜙 − 𝜃𝑘 + 𝜆5 𝜃𝑘 − 𝜋∕2
𝜕𝐿 𝜕𝑔 ∗
where 𝜆𝑖 (𝑖 = 1, 2, 3, 4, 5) denotes the Lagrange multipliers, and the opti- = −1 − 𝜆∗1 ∗𝑘 = 0 (13)
𝜕𝑟𝑘
∗ 𝜕𝑟𝑘
mal solutions 𝑟∗𝑘 , 𝜃𝑘∗ , 𝜆∗𝑖 (𝑖 = 1, 2, 3, 4, 5) can be determined by the follow-
ing conditions: 𝜕𝐿 𝜕𝑔 ∗ ( ) ( )
= −𝜆∗1 𝑘∗ = −𝜆∗1 𝑔1 𝑟∗𝑘 , 𝜃𝑘∗ 𝑔2 𝜃𝑘∗ = 0 (14)
( ) 𝜕𝜃𝑘
∗ 𝜕𝜃𝑘
𝑔̄𝑘 − 𝑔𝑘∗ 𝑟∗𝑘 , 𝜃𝑘∗ ≤0 (8a) ( )
According to (13), it is easy to obtain 𝜆∗1 > 0. Then, as 𝑔1 𝑟∗𝑘 , 𝜃𝑘∗ > 0,
( )
ℎmin − 𝑟∗𝑘 tan 𝜃𝑘∗ ≤ 0 (8b) 𝑔2 𝜃𝑘∗ = 0 holds according to (14), with which 𝜃𝑘∗ can be determined
by using the bisection search. Thereafter, with 𝜆∗1 > 0 and (8g), we have
𝑟∗𝑘 tan 𝜃𝑘∗ − ℎmax ≤ 0 (8c) ( )
𝑔̄𝑘 − 𝑔𝑘∗ 𝑟∗𝑘 , 𝜃𝑘∗ = 0, yielding that
𝜋∕2 − 𝜙 − 𝜃𝑘∗ ≤0 (8d) ( ( ( )) )1∕𝛼
𝛽0 1 + 𝑎𝜅 exp Θ∗𝑘
𝜃𝑘∗ − 𝜋∕2 ≤ 0 (8e) 𝑟∗𝑘 = ( ( )) cos 𝜃𝑘∗ (15)
𝑔̄𝑘 1 + 𝑎 exp Θ∗𝑘
𝜆∗𝑖 ≥ 0, ∀𝑖 = 1, 2, 3, 4, 5 (8f)
Case 2: If 𝜆∗3 = 𝜆∗4 = 0 and 𝜆∗2 > 0, then we have 𝑟∗𝑘 tan 𝜃𝑘∗ = ℎmin
( ( ))
𝜆∗1 𝑔̄𝑘 − 𝑔𝑘∗ 𝑟∗𝑘 , 𝜃𝑘∗ = 0 (8g) according to (8h). Equations (8l) and (8m) can be rewritten as:
( ) 𝜕𝑔 ∗
𝜆∗2 ℎmin − 𝑟∗𝑘 tan 𝜃𝑘∗ = 0 (8h) 𝜕𝐿
= −1 − 𝜆∗1 ∗𝑘 − 𝜆∗2 tan 𝜃𝑘∗ = 0 (16)
( ) 𝜕𝑟𝑘
∗ 𝜕𝑟𝑘
𝜆∗3 𝑟∗𝑘 tan 𝜃𝑘∗ − ℎmax = 0 (8i)
( ) 𝜕𝐿 𝜕𝑔 ∗ ( ) ( ) 𝜆∗ 𝑟∗𝑘
𝜆∗4 𝜋∕2 − 𝜙 − 𝜃𝑘∗ = 0 (8j) = −𝜆∗1 𝑘∗ = −𝜆∗1 𝑔1 𝑟∗𝑘 , 𝜃𝑘∗ 𝑔2 𝜃𝑘∗ − 2 ∗ = 0 (17)
𝜕𝜃𝑘
∗ 𝜕𝜃𝑘 cos2 𝜃𝑘
( )
𝜆∗5 𝜃𝑘∗ − 𝜋∕2 = 0 (8k) According to (17), the following equation holds:
𝜕𝐿 𝜕𝑔 ∗ 𝜆∗2 𝑟∗𝑘
= −1 − 𝜆∗1 ∗𝑘 − 𝜆∗2 tan 𝜃𝑘∗ + 𝜆∗3 tan 𝜃𝑘∗ = 0 (8l) 𝜆∗1 = − ( ) ( ) >0 (18)
𝜕𝑟∗𝑘 𝜕𝑟𝑘
𝑔1 𝑟∗𝑘 , 𝜃𝑘 𝑔2 𝜃𝑘∗ cos2 𝜃𝑘∗
∗

𝜕𝐿 𝜕𝑔 ∗ 𝜆∗ 𝑟∗ 𝜆∗ 𝑟∗𝑘
= −𝜆∗1 𝑘∗ − 2 𝑘 ∗ + 3 ∗ − 𝜆∗4 + 𝜆∗5 =0 (8m) Similar to Case 1, equation (15) also holds. Solving (15) with 𝑟∗𝑘 tan 𝜃𝑘∗ =
𝜕𝜃𝑘∗ 𝜕𝜃𝑘 cos2 𝜃𝑘 cos2 𝜃𝑘 ℎmin , the optimal values of 𝜃𝑘∗ and 𝑟∗𝑘 can be determined.
with Case 3: If 𝜆∗2 = 𝜆∗4 = 0 and 𝜆∗3 > 0, then we have 𝑟∗𝑘 tan 𝜃𝑘∗ = ℎmax
( ) ( )−𝛼 according to (8i). Equations (8l) and (8m) can be rewritten as:
( ) 1 + 𝑎𝜅 exp Θ∗𝑘 𝛽0 𝑟∗𝑘
𝑔𝑘∗ 𝑟∗𝑘 , 𝜃𝑘∗ = ( ) ( ⋅ )−𝛼 (9) 𝜕𝐿 𝜕𝑔𝑘∗
1 + 𝑎 exp Θ∗𝑘 cos 𝜃𝑘∗ = −1 − 𝜆 ∗
+ 𝜆∗3 tan 𝜃𝑘∗ = 0 (19)
𝜕𝑟∗𝑘 1 𝜕𝑟∗
𝑘
( ∗ ) ( ∗ )−𝛼−1
𝜕𝑔𝑘∗ −𝛼𝛽0 1 + 𝑎𝜅 exp Θ𝑘 𝑟𝑘 𝜕𝐿 𝜕𝑔 ∗ ( ) ( ) 𝜆∗ 𝑟∗𝑘
= ⋅ ( ) ⋅ (10) = −𝜆∗1 𝑘∗ = −𝜆∗1 𝑔1 𝑟∗𝑘 , 𝜃𝑘∗ 𝑔2 𝜃𝑘∗ + 3 ∗ = 0 (20)
𝜕𝑟∗𝑘 cos 𝜃𝑘∗ 1 + 𝑎 exp Θ∗ cos 𝜃𝑘∗ 𝜕𝜃𝑘
∗ 𝜕𝜃𝑘 cos2 𝜃𝑘
𝑘

5
X. Ai, Z. Pu, X. Chai et al. Aerospace Science and Technology 143 (2023) 108731
∑
Similar to Case 2, it is easy to verify from (20) that 𝜆∗1 > 0 and (15) 𝛾𝑚,𝑘 ≤ 𝑁max , ∀𝑚 ∈  (24d)
hold. Solving (15) with 𝑟∗𝑘 tan 𝜃𝑘∗ = ℎmax , the optimal values of 𝜃𝑘∗ and 𝑟∗𝑘 𝑘∈
𝑐
can be determined. 𝛾𝑚,𝑘 𝑑𝑚,𝑘 ≤ 𝑟∗𝑘 , ∀𝑘 ∈ , ∀𝑚 ∈  (24e)
Case 4: If 𝜆∗2 = 𝜆∗3 = 0 and 𝜆∗4 > 0, then we have 𝜃𝑘∗ = 𝜋∕2 − 𝜙 accord-
ing to (8k). Equations (8l) and (8m) can be rewritten as: and In the subsequent text, we propose GP-CA2 BC to solve the cluster
problem. Algorithm 1 presents the process of clustering UEs, which is
𝜕𝐿 𝜕𝑔 ∗ also described as follows.
= −1 − 𝜆∗1 ∗𝑘 = 0 (21)
𝜕𝑟𝑘
∗ 𝜕𝑟𝑘 Let 𝑈 ⊆  be a set consisting of all uncovered UEs and we have
𝜕𝐿 ( ) ( ) 𝑈 =  in the first iteration. In the 𝑚-iteration, we firstly formulate
= −𝜆∗1 𝑔1 𝑟∗𝑘 , 𝜃𝑘∗ 𝑔2 𝜃𝑘∗ − 𝜆∗4 = 0
}each UE 𝑘 ∈ 𝑈
(22) the uncovered UEs as a graph
𝜕𝜃𝑘∗ { and the neighbor set of
can be determined by 𝑘 = 𝑖 ∈ 𝑈 | ‖ ‖
‖𝝎𝑖 − 𝝎𝑘 ‖ ≤ 2𝑟𝑘 . Along with this
∗
( )
As 𝜆∗1 > 0 holds according to (21), then if requires that 𝑔2 𝜃𝑘∗ < 0 to line, the degree of each UE can be calculated by ||𝑘 ||. Notably, a UE
make (22) hold. If this is the case, then submitting 𝜃𝑘∗ = 𝜋∕2 − 𝜙 into who has smaller allowed service radius and less neighbors is more diffi-
(15) to obtain 𝑟∗𝑘 . cult to be served with other UEs by one UAV. Therefore, we cluster the
Case 5: If 𝜆∗2 = 0 and 𝜆∗3 , 𝜆∗4 > 0, then we have 𝜃𝑘∗ = 𝜋∕2 − 𝜙 and UE with smallest allowed service radius and smallest degree among un-
𝑟𝑘 = ℎmax ∕ tan 𝜃𝑘∗ according to (8i) and (8j). Then submitting 𝜃𝑘∗ and 𝑟∗𝑘
∗ covered UEs in priority. Subsequently, we can find the UEs with smallest
into (8a), (8g), (8l) and (8m) to check whether these equations hold allowed service{radius among uncovered } UEs and pick them up as fea-
simultaneously. ture set 0 = 𝑖 ∈ 𝑈 |𝑟∗𝑖 = min𝑘∈𝑈 𝑟∗𝑘 . Then, the UE with smallest
Case 6: If 𝜆∗3 = 0 and 𝜆∗2 , 𝜆∗4 > 0, then we have 𝜃𝑘∗ = 𝜋∕2 − 𝜙 and
degree is chosen as the feature UE 𝑘0 = arg min𝑖∈0 ||𝑖 ||. Notably, UEs
𝑟∗𝑘 = ℎmin ∕ tan 𝜃𝑘∗ according to (8h) and (8j). Then submitting 𝜃𝑘∗ and 𝑟∗𝑘
at a distance of more than 2𝑟∗𝑘 away from UE 𝑘0 are impossible to be
into (8a), (8g), (8l) and (8m) to check whether these equations hold 0
severed by the same UAV with UE 𝑘0 . Therefore, only the UEs in the
simultaneously.
neighbor set 𝑘0 of 𝑘0 are considered to be served by the same UAV.
All possible solutions of problem (7) are given. If the 2D distance
between UE 𝑘 and UAV 𝑚 satisfies 𝑑𝑚,𝑘 ≤ 𝑟∗𝑘 then 𝑔𝑚,𝑘 ≥ 𝑔̄𝑘 is achieved. Such process can greatly reduce the invalid solution space of CA2 BC al-
Therefore, the channel gain constraint given in (6e) can be transfered gorithm. After that, the cluster center is optimized by using the CA2 BC
into the constraint on the allowed service radius and problem (6) can algorithm with the goal of maximizing the number of UEs in the clus-
be rewritten as follows: ter and a cluster of UEs 𝑚 ⊆ 𝑈 ⊆  is obtained as well as the cluster
center 𝑭 𝑐𝑚 ∈  ⧵ 2 and the cluster radius 𝑟𝑐𝑚 . It should be noted that
min || (23) we require the feature UE 𝑘0 must be included in 𝑚 , that is 𝑘0 ∈ 𝑚 .
{𝒑𝑚 },{𝛾𝑚,𝑘 } This can be achieved by appropriately generating the initial solution of
s.t. 𝒑𝑚 ∈  ⧵  (23a) the CA2 BC algorithm. To this end, for each UE 𝑙 ∈ 𝑚 we have 𝛾𝑚,𝑙 = 1
indicating that this cluster of UEs are served by UAV 𝑚. Finally we can
𝛾𝑚,𝑘 ∈ {0, 1}, ∀𝑘 ∈ , ∀𝑚 ∈  (23b) remove the UEs in 𝑚 from 𝑈 to finish the 𝑚-iteration. Repeating the
∑ above process until all UEs are grouped, i.e. 𝑈 = ∅, to finish the al-
𝛾𝑚,𝑘 = 1, ∀𝑘 ∈  (23c)
𝑚∈
gorithm. Notably, the iterations of the above process are the minimum
∑ number of UAVs to be deployed while ensure full coverage of all UEs.
𝛾𝑚,𝑘 ≤ 𝑁max , ∀𝑚 ∈  (23d) Fig. 4 illustrates the flow chart of Algorithm 1.
𝑘∈

𝛾𝑚,𝑘 𝑑𝑚,𝑘 ≤ 𝑟∗𝑘 , ∀𝑘 ∈ , ∀𝑚 ∈  (23e) Algorithm 1 GP-CA2 BC-based UE clustering.

{ } { }
It should be noted that problem (23) is also a mixed-integer program- Input: , 𝝎𝑘 |𝑘 ∈ { , 𝑟∗𝑘 |𝑘 ∈} { } { }
ming problem and thereby is difficult to obtain the optimal solution. Output: ||,  = 𝑚 |𝑚 ∈  , 𝑐 = 𝑭 𝑐𝑚 ∈  ⧵ 2 |𝑚 ∈  , 𝑐 = 𝑟𝑐𝑚 |𝑚 ∈ 
1: Initialization: 𝑚 = 1, 𝑈 = ,  = ∅
The subsequent text will provide a deployment algorithm to address 2: while  ≠ ∅ do { }
problem (23). The developed algorithm consists of two parts. Firstly, 3: { Calculate the neighbor set  = 𝑘 |𝑘 ∈ 𝑈 with 𝑘 =
}
the GP-CA2 BC is presented to cluster all UEs such that the minimum 𝑖 ∈ 𝑈 | ‖ 𝝎
‖ 𝑖 − 𝝎 ‖ ≤ 2𝑟∗ .
𝑘‖ 𝑘 { }
number of UAVs can be determined. Then, the 3D position of each UAV 4: Find the feature set 0 = 𝑖 ∈ 𝑈 |𝑟∗𝑖 = min𝑘∈𝑈 𝑟∗𝑘 in which the UE has the small-
est allowed service radius.
is decided according to the distribution of UEs in each cluster.
5: Find the feature UE 𝑘0 = arg min𝑖∈0 ||𝑖 || who has the smallest degree.
6: Apply the CA2 BC algorithm (Algorithm 2) to obtain set 𝑚 ,the cluster center 𝑭 𝑐𝑚
4.3. UE clustering and the cluster radius 𝑟𝑐𝑚 .
7: Update 𝑈 ← 𝑈 ⧵ 𝑚 and 𝑚 = 𝑚 + 1.
8: Respectively add 𝑚 , 𝑭 𝑐𝑚 and 𝑟𝑐𝑚 to , 𝑐 and 𝑐 .
UE clustering contributes to many practical applications of UAVs
9: end while
[44,45]. As the UEs are distributed in a 2D area, the UE clustering pro- 10: return , 𝑐 , 𝑐
cess is also performed
{ in this area
} according to the distance constraint
(23e). Let 𝑚 =[ 𝑘 ∈ |𝛾 ] 𝑚,𝑘 = 1 , 𝑚 ∈  be a cluster with center lo-
cated at 𝑭 𝑐𝑚 = 𝑥𝑐𝑚 , 𝑦𝑐𝑚 ∈  ⧵ 2 , where 2 denotes the projection of
obstacles onto  to ensure safety of the cluster center. It should be Remark 1. As the QoS requirements of UEs are non-uniform, we in-
noted that the cardinality of group 𝑚 must be no more than 𝑁max and tend to deploy UAV for the UE with smallest allowed service radius in
for any 𝑘 ∈ 𝑚 we have 𝑑𝑚,𝑘 𝑐 = ‖𝝎 − 𝑭 𝑐 ‖ ≤ 𝑟∗ . Therefore, the UE clus- priority (see line 4 of Algorithm 1). Notably, the proposed placement
‖ 𝑘 𝑚‖ 𝑘
tering problem is formulated as follows: process can be also used for the case with uniform QoS requirement,
i.e. 𝑟∗𝑖 = 𝑟∗𝑗 , ∀𝑖, 𝑗 ∈ . If this is the case, then the placement process be-
min || (24) gins with the UE with least neighbors (see line 5 of Algorithm 1). Some
{𝑭 𝑐𝑚 },{𝛾𝑚,𝑘 } related works have also been reported to address the 2D or 3D mulit-
s.t. 𝑭 𝑐𝑚 ∈  ⧵ 2 (24a) UAV deployment problem with uniform QoS requirement [25,35,29].
However, the constraint on the beamwidth and the safety of UAVs are
𝛾𝑚,𝑘 ∈ {0, 1}, ∀𝑘 ∈ , ∀𝑚 ∈  (24b) not taken into account simultaneously, which renders their algorithms
∑ are not applicable to our problem. Moreover, the algorithms developed
𝛾𝑚,𝑘 = 1, ∀𝑘 ∈  (24c)
in [25,35,29] begin with the placement process with the UE located in
𝑚∈

6
X. Ai, Z. Pu, X. Chai et al. Aerospace Science and Technology 143 (2023) 108731

Algorithm 2 CA2 BC algorithm.

{ }
Input:  , 2 , 𝝎𝑘 |𝑘 ∈  , 𝑘0 ,  , 𝑟∗𝑘 , 𝑁𝑝 , 𝑇𝑠 , 𝑇𝑖𝑡𝑒 , 𝑇𝑡𝑒𝑟 , 𝑇𝑐
0
Output: 𝑚 , 𝑭 𝑐𝑚 , 𝑟𝑐𝑚
{ }
1: Initialization: randomly initialize the set of possible solutions  = 𝑭 1 , … , 𝑭 𝑁𝑝
{ }
2: Calculate the fitness value set  = 𝐽𝑖 |1 ≤ 𝑖 ≤ 𝑁𝑝 for all solutions in  according to
(25).
𝑐 𝑐
3: {
Record the greatest } fitness value 𝐽𝑚 = max  and the optimal solution 𝑭 𝑚 =
𝑭 𝑙 |𝑙 = arg max  .
4: for 𝑡 = 1 ∶ 𝑇𝑖𝑡𝑒 do
Employed Bees Phase:
5: for 𝑖 = 1 ∶ 𝑁𝑝 do
6: Generate a new solution 𝑭 𝑛𝑒𝑤 in the neighborhood of 𝑭 𝑖 according to (26) and
project it onto  by
(27).
7: Calculate the fitness value 𝐽𝑛𝑒𝑤 for the new solution 𝑭 𝑛𝑒𝑤 .
8: if 𝐽𝑛𝑒𝑤 ≥ 𝐽𝑖 then
9: Update 𝑭 𝑖 ← 𝑭 𝑛𝑒𝑤 and 𝐽𝑖 ← 𝐽𝑛𝑒𝑤 .
10: end if
11: end for
Onlooker Bees Phase: { }
12: Calculate the probability set 𝑃𝑖 |1 ≤ 𝑖 ≤ 𝑁𝑝 according to (28).
13: for 𝑗 = 1 ∶ 𝑁𝑝 do
14: for 𝑖 = 1 ∶ 𝑁𝑝 do
15: if 𝑟𝑎𝑛𝑑𝑜𝑚() < 𝑃𝑖 then
16: Break.
17: end if
18: if 𝑖 == 𝑁𝑝 then
19: 𝑖 = 1.
20: end if
21: end for
22: Generate a new solution 𝑭 𝑛𝑒𝑤 in the neighborhood of 𝑭 𝑖 according to (26)
and project it onto  using
(27).
23: Calculate the fitness value 𝐽𝑛𝑒𝑤 for the new solution 𝑭 𝑛𝑒𝑤 .
24: if 𝐽𝑛𝑒𝑤 ≥ 𝐽𝑖 then
25: Update 𝑭 𝑖 ← 𝑭 𝑛𝑒𝑤 and 𝐽𝑖 ← 𝐽𝑛𝑒𝑤 .
26: end if
27: end for
28: if max  ≥ 𝐽𝑚𝑐 then { }
29: Update the optimal solution 𝑭 𝑐𝑚 = 𝑭 𝑙 |𝑙 = arg max  and the corresponding
beset fitness value 𝐽𝑚 = 𝑐

max  .
30: end if
Scout Bees Phase: ( )
31: If any solution 𝑭 𝑖 1 ≤ 𝑖 ≤ 𝑁𝑝 remains unchanged after 𝑇𝑠 iterations, then using
chaotic search process to
generate a new solution 𝑭 𝑛𝑒𝑤 and update 𝑭 𝑖 ← 𝑭 𝑛𝑒𝑤 .
Fig. 4. The flow chart of Algorithm 1.
Terminal Phase:
32: If the optimal solution 𝑭 𝑐𝑚 remains unchanged for 𝑇𝑡𝑒𝑟 consecutive iterations, then
Break.
the edge of the uncovered area. It should be noted that a UE located in 33: end for { }
the edge of the uncovered area may still have more neighbors than that 34: Calculate the cluster 𝑚 = 𝑙 ∈ 𝑘0 | ‖ 𝑐 ‖
‖𝑭 𝑚 − 𝝎𝑙 ‖ ≤ 𝑟𝑘 and the cluster radius 𝑟𝑚 =
∗ 𝑐
0

located in the center of the uncovered area such that it have greater max𝑙∈𝑚 ‖ 𝑐
‖𝑭 𝑚 − 𝝎𝑙 ‖.
‖
possibility to be severed with its neighbors by the same UAV. Thus, 35: return 𝑚 , 𝑭 𝑐𝑚 , 𝑟𝑐𝑚

placing UAV for the UE with least neighbors in priority as done in line
5 of Algorithm 1 contributes to minimizing the number of UAVs. { }
2) Fitness function: Let ̄ = 𝑙 ∈ 𝑘0 | ‖ ‖
‖𝑭 𝑖 − 𝝎𝑙 ‖ ≤ 𝑟𝑘0 be the set
∗
𝑖
( )
Algorithm 1 invokes the CA2 BC algorithm to determine the center of of UEs covered by the solution 𝑭 𝑖 1 ≤ 𝑖 ≤ 𝑁𝑝 with radius 𝑟∗𝑘 . By tak-
0
cluster 𝑚 (see line 6 of Algorithm 1). The presented CA2 BC algorithm ing the safety and the service ability of UAVs into consideration, the
denotes a variant of the conventional ABC algorithm by introducing fitness function 𝐽𝑖 for each solution 𝑭 𝑖 , 1 ≤ 𝑖 ≤ 𝑁𝑝 is defined as:
chaotic search process and adaptive weights. The idea behind the al- {∑
| |
gorithm is also to find proper solutions by imitating the behavior of ( )
𝑙∈̄ 𝑖 1∕ ||𝑙 || 𝑭 𝑖 ∈  ⧵ 2 and |̄ 𝑖 | ≤ 𝑁max
𝐽𝑖 𝑭 𝑖 = | | (25)
employed bees, onlooker bees and scout bees [46]. Algorithm 2 gives 0.001 otherwise
the process of the CA2 BC algorithm and some key operators are de-
The fitness function indicates that the number of UEs covered by 𝑭 𝑖
scribed in detail as follows.
should be no more than 𝑁max and the solution 𝑭 𝑖 should be located
1) Initialization: To ensure that the feature UE 𝑘0 is included in clus-
in the given area  ⧵ 2 ; otherwise it will be given a penalty factor.
ter 𝑚 , the solution space is restricted as
Furthermore, the solution 𝑭 𝑖 , which covers the UEs with less neighbors,
{ ‖√( }
‖ )2 ( )2 ‖
‖
is more likely to be chosen
{ as the optimal
} solution. Based on (25), the
= (𝑥,
̄ 𝑦) ̄ ∈  |‖‖ 𝑥̄ − 𝑥𝑘0 + 𝑦
̄ − 𝑦 𝑘0
‖
‖ ≤ 𝑟∗
𝑘0 . fitness value set  = 𝐽𝑖 |1 ≤ 𝑖 ≤ 𝑁𝑝 can be obtained. Subsequently,
{ }
‖ ‖ the optimal solution 𝑭 𝑐𝑚 = 𝑭 𝑙 |𝑙 = arg max  and the corresponding
‖ ‖
{ } optimal fitness value 𝐽𝑚𝑐 = max  can be determined.
Then, we can generate the initial solution  = 𝑭 1 , … , 𝑭 𝑁𝑝 with 3) Employed Bees Phase: In this phase, an employed bee searches for
[ ]
𝑭 𝑖 = 𝑥̄ 𝑖 , 𝑦̄𝑖 ∈  , where 𝑁𝑝 denotes the total number of solutions. new position 𝑭 𝑛𝑒𝑤 for solution 𝑭 𝑖 in its neighborhood as follows:

7
X. Ai, Z. Pu, X. Chai et al. Aerospace Science and Technology 143 (2023) 108731
(( ) )
𝑡 ( ) 𝑡 ( )
𝑭 𝑛𝑒𝑤 = 𝑭 𝑖 + Δ 1− 𝑭𝑖 −𝑭𝑙 + 𝑭 𝑖 − 𝑭 𝑐𝑚 (26) 4.4. 3D position optimization
𝑇𝑖𝑡𝑒 𝑇𝑖𝑡𝑒
[ ]
where 𝑙 ≠ 𝑖 is randomly selected, Δ ∈ [−1, 1] represents a random num- Let 𝑷 2𝑚 = 𝑥𝑚 , 𝑦𝑚 ∈  be the
{ projection}of UAV 𝑚’s position 𝒑𝑚 onto
ber, 𝑡 denotes the current iteration, and 𝑇𝑖𝑡𝑒 stands for the maximum  . Then given UE cluster  = 𝑚 |𝑚 ∈  obtained by Section 4.3, if
iterations. Contrary to the conventional ABC algorithm, the presented UAV 𝑚 is deployed at the cluster center, i.e. 𝑷 2𝑚 = 𝑭 𝑐𝑚 , then UEs in
CA2 BC applies the adaptive weight 𝑡∕𝑇𝑖𝑡𝑒 to balance exploration and ex- 𝑚 can be successfully covered by UAV 𝑚 with radius 𝑟𝑐𝑚 . It should be
ploitation when generating a new solution noted that Section 4.3 only considers the UE clustering problem, while
( as illustrated
) ( in (26).
) To be
specific, in the early stage, i.e. 𝑡 ≪ 𝑇𝑖𝑡𝑟 , 1 − 𝑡∕𝑇𝑖𝑡𝑒 𝑭 𝑖 − 𝑭 𝑙 is dom- the cluster radius is not optimized simultaneously. As indicated in Sec-
inant and it attempts to discover new possible position in the solution tion 2, decreasing the distance between the UE and UAV contributes to
space, which avoids( falling into local optimal solution prematurely; improving the QoS indeed. Therefore, this subsection further optimizes
)
when 𝑡 ≈ 𝑇𝑖𝑡𝑒 , 𝑡∕𝑇𝑖𝑡𝑒 𝑭 𝑖 − 𝑭 𝑐𝑚 is dominant and it prefers to search bet- the UAV’s position to enhance the QoS.
ter solution in the neighborhood of current optimal one 𝑭 𝑐𝑚 . It should With the constraint on the beamwidth, the optimal altitude ℎ𝑚 and
be noted that the new solution 𝑭 𝑛𝑒𝑤 generated by (26) may be out of the maximum service radius 𝑟𝑚 of UAV 𝑚 is coupled. Therefore, we
the solution space, i.e. 𝑭 𝑛𝑒𝑤 ∉  , yielding an invalid solution. We fur- can optimize UAV 𝑚’s 2D position 𝒑2𝑚 (𝑚 ∈ ) first to decrease the 2D
ther project 𝑭 𝑛𝑒𝑤 onto  to solve this problem as follows: distance between UAV 𝑚 and the UEs in 𝑚 as much as possible, which
can be formulated as follows:
( )
𝑭 𝑛𝑒𝑤 = 𝑃 𝑭 𝑛𝑒𝑤 = arg min ‖ ‖
‖𝑭 𝑛𝑒𝑤 − 𝒒 ‖ (27) ‖ ‖
𝒒∈ min max ‖𝝎𝑙 − 𝒑2𝑚 ‖ (30)
𝒑2𝑚 𝑙∈𝑚 ‖ ‖
where 𝑃 ∶ ℝ2→  denotes the projection operator. Then, we can ob-
s.t. 𝒑2𝑚 ∈  ⧵ 2 (30a)
tain the fitness value 𝐽𝑛𝑒𝑤 for 𝑭 𝑛𝑒𝑤 and compare it with 𝐽𝑖 . If 𝐽𝑛𝑒𝑤 ≥ 𝐽𝑖 ,
we replace 𝑭 𝑖 by 𝑭 𝑛𝑒𝑤 . Affecting by the obstacles, problem (30) maybe non-convex. We can use
4) Onlooker Bees Phase: Onlooker bees search in the neighborhood of the CA2 BC algorithm
{ to solve (30). To be specific,
} the solution space is
‖ ‖
the candidate solutions according to a probabilistic model. For each so- defined as ̄ = 𝒑2𝑚 ∈  | ‖𝒑2𝑚 − 𝑭 𝑐𝑚 ‖ ≤ 2𝑟𝑐𝑚 and the fitness function is
‖ ‖
lution 𝑭 𝑖 , the probability of being chosen by an onlooker bee is defined designed as
as [46]: { ‖ ‖
( ) −max ‖𝝎𝑙 − 𝒑2𝑚 ‖ 𝒑2𝑚 ∈  ⧵ 2
0.9𝐽𝑖 𝐽̄𝑖 𝒑2𝑚 = {𝑙∈𝑚 ‖ ‖ } (31)
𝑃𝑖 = + 0.1 (28)
max  − max 𝑥max − 𝑥min , 𝑦max − 𝑦min otherwise
Based on (28), every onlooker bee generates a random real number Then, repeating the Employed Bees, Onlooker Bees and Scout Bees pro-
𝑟𝑎𝑛𝑑𝑜𝑚() ∈ (0, 1). If 𝑟𝑎𝑛𝑑𝑜𝑚() < 𝑃𝑖 , then the onlooker bee selects 𝑭 𝑖 as cesses in Algorithm 2, we can obtain the 2D deployed position 𝒑2𝑚 for
the candidate. Then, similar with the process in Employed Bees Phase, we UAV 𝑚, and the maximum service radius of UAV 𝑚 is determined by
generate a new solution 𝑭 𝑛𝑒𝑤 in the neighborhood of 𝑭 𝑖 and project it ‖ ‖
𝑟𝑚 = max𝑙∈𝑚 ‖𝝎𝑙 − 𝒑2𝑚 ‖. Subsequently, the deployed altitude of UAV 𝑚
onto the solution space  using (26)-(27). Then, the one with greater ‖ ‖
is given by
fitness value remains in the solution  . ( ) ( )
5) Scout Bees Phase: Similar with other evolutionary algorithms, ABC ⎧ 𝑟 ∕ tan max 𝜃 ∗ 𝑟 ∕ tan max 𝜃 ∗ >ℎ
⎪ 𝑚 𝑚
𝑘∈𝑚 𝑘 𝑘 min
also encounters the problem of “premature convergence” [47]. That is ℎ𝑚 = ⎨ (𝑘∈𝑚 ) (32)
if solution 𝑭 𝑖 remains unchanged after 𝑇𝑠 iterations, it may fall into ⎪ ℎmin 𝑟𝑚 ∕ tan max 𝜃𝑘∗ ≤ ℎmin
local optima. Therefore, we apply chaotic search process to generate a ⎩ 𝑘∈𝑚
new solution 𝑭 𝑛𝑒𝑤 near 𝑭 𝑖 . Firstly, we transform each coordinate of 𝑭 𝑖 Hereto, the suboptimal solution of deployment problem (5) is ob-
(0)
into (0, 1) to generate the initial chaotic vector 𝒔𝑖 . Then, we update tained for multi-UAV-mounted BSs. It is easy to obtain( that the )com-
the chaotic vector for 𝑇𝑐 iterations by using the following logistic map putational complexity of 3D position optimization is  || 𝑁max and
( )
[48]: | |
thereby the complexity of the overall algorithm is  𝑇𝑖𝑡𝑒 𝑁𝑝2 |𝑘0 ||| .
( ) | |
𝒔(𝜄+1)
𝑖 = 4𝒔(𝜄) (𝜄)
𝑖 ⊙ 1 − 𝒔𝑖 (29)
5. Simulation results
where ⊙ denotes the element-wise product
( ) of two vectors. After that,
𝑇 This section provides some simulation results to demonstrate the
we can obtain the final chaotic vector 𝒔𝑖 𝑐 and transform it into the
superior performance of the proposed algorithm. We consider a so-
solution space  to obtain a new solution 𝑭 𝑛𝑒𝑤 . Finally, we replace 𝑭 𝑖
phisticated urban environment with obstacles in the simulation. The
by 𝑭 𝑛𝑒𝑤 to jump out of local optima while increasing the diversity of
simulation parameters are summarized in Table 2, which can refer
solutions.
to [29,36,42] for more details. As the related works only focused on
6) Terminal Phase: The iteration will be finished if the iteration time
deploying UAVs for UEs with uniform SINR threshold, we carry out
is up to the maximum value 𝑇𝑖𝑡𝑒 or the optimal solution 𝑭 𝑐𝑚 remains
the simulations with uniform and non-uniform SINR threshold, respec-
unchanged for 𝑇𝑡𝑒𝑟 consecutive iterations. And thus the UEs located in
tively, and the SINR threshold is replaced by the gain channel constraint
the circle with center 𝑭 𝑐𝑚 and radius 𝑟∗𝑘 are grouped in set 𝑚 , and the
0 in the subsequent text.
cluster radius can be obtained by 𝑟𝑐𝑚 = max𝑙∈𝑚 ‖ 𝑐 ‖
‖𝑭 𝑚 − 𝝎𝑙 ‖ .
Fig. 5 illustrates the flow chart of Algorithm 2. Notably, the com- 5.1. Simulation results with uniform channel gain threshold
plexity of Algorithm 1 is  (||). For Algorithm (2, the complexity
) of
( ) | |
line 1 is  𝑁𝑝 , the complexity of lines 4-33 is  𝑁𝑝2 |𝑘0 | , and the The most similar work with this paper was given in [28], where an
| | ordered ABC (O-ABC) was presented to solve the UE clustering problem
| |
complexity of line 34 is |𝑘0 |. Therefore, the complexity of Algorithm 2
( ) | | with uniform channel gain threshold in obstacle-free environment. Con-
| |
is  𝑇𝑖𝑡𝑒 𝑁𝑝2 |𝑘0 | and the computational complexity of the proposed trary to our scheme, the UE far away from the center of the uncovered
| | ( ) area is selected as the feature one in O-ABC algorithm and then ABC
| |
algorithm for user clustering is  𝑇𝑖𝑡𝑒 𝑁𝑝2 |𝑘0 | || . To this end, by is applied to cluster the UEs. Simulation results illustrated in [28] have
| |
performing Algorithms 1 and 2, the UE cluster  and the cluster center demonstrated the superiority of O-ABC in terms of minimizing the num-
𝑐 can be obtained. This concludes the UE clustering process. ber of required UAVs compared with other existing schemes, such as

8
X. Ai, Z. Pu, X. Chai et al. Aerospace Science and Technology 143 (2023) 108731

Fig. 5. The flow chart of Algorithm 2.

K-means clustering, ordered particle swarm optimization (O-PSO), and lations with O-ABC, GP-ABC, and GP-CA2 BC for comparison by setting
edge-prior placement (EPP) algorithm. Therefore, we carry out simu- the channel gain threshold uniformly. It should be noted that we also

9
X. Ai, Z. Pu, X. Chai et al. Aerospace Science and Technology 143 (2023) 108731

Fig. 6. Comparison of number of required UAVs under different conditions using various algorithms.

Table 2
Simulation parameters.

Parameter Physical meaning Value

𝑥min , 𝑦min Lower bound of the 2D UE area  0m

ℎmin , ℎmax Lower and upper bound of the altitude of UAVs 50 m, 500 m
𝑎, 𝑏, 𝛼 Modeling parameters related to the environment 11.95, 0.14, 2
𝛽0 Path loss parameter 7 × 10−5
𝜅 Attenuation loss parameter 0.01
𝜙 Beamwidth of the directional antenna 𝜋∕3
𝑇𝑖𝑡𝑒 Maximum iterations of CA2 BC algorithm 1000
𝑁𝑝 Population size of CA2 BC algorithm 100
𝑇𝑠 Largest searching time of scout bees 80
𝑇𝑡𝑒𝑟 Terminal condition on the consecutively unchanged time of the optimal solution 20
𝑇𝑐 Maximum iterations of chaotic search 10

modify O-ABC and GP-ABC algorithms such that the UAVs are deployed 100, 150, 200, 250, 300, the channel gain threshold 𝑔̄𝑘 = −104, −102,
in obstacle-laden area. Moreover, it should be noted that the computa- −100, −98, −96 dB, ∀𝑘 ∈ , and the UAV’s service ability 𝑁max =
tional complexity of the proposed algorithm is equal to that of O-ABC 6, 7, 8, 9, 10. Figs. 6 and 7 give the results of comparing the number of
and GP-ABC. required UAVs  and the time consumes 𝑇 𝑖𝑚𝑒, respectively, for differ-
To demonstrate the superiority of our algorithm, we carry out ent algorithms under varying conditions. Each point shows the average,
the simulations with various conditions, i.e. the area length 𝑥max = the maximum and the minimum results of 100 runs. To provide better
𝑦max = 4000, 5000, 6000, 7000, 8000 m, the number of UEs || = insight on the performance improvement of the proposed algorithm, the

10
X. Ai, Z. Pu, X. Chai et al. Aerospace Science and Technology 143 (2023) 108731

Fig. 7. Comparison of time consumes under different conditions using various algorithms.

Fig. 8. Multi-UAV deployment with non-uniform channel threshold using GP-CA2 BC (UAV: Sphere, UE: Star).

11
X. Ai, Z. Pu, X. Chai et al. Aerospace Science and Technology 143 (2023) 108731

Fig. 9. Comparison of number of required UAVs under different conditions when the SINR threshold is non-uniform.

Table 3 Table 4
Comparison of required number of UAVs with Comparison of required number of UAVs with
varying regional area using different algorithms, varying number of UEs using different al-
where || = 200, 𝑔̄𝑘 = −100 dB, 𝑁max = 8. gorithms, where 𝑥max = 𝑦max = 6000 m, 𝑔̄𝑘 =
 −100 dB, 𝑁max = 8.
O-ABC GP-ABC GP-CA2 BC
𝑥(𝑚) 
O-ABC GP-ABC GP-CA2 BC
4000 25.80 25.52 25.47 
5000 28.49 27.85 27.75 100 25.70 25.44 25.40
6000 33.61 32.62 32.09 150 29.85 29.46 29.00
7000 40.12 39.57 39.35 200 33.61 32.62 32.09
8000 46.79 46.79 46.60 250 37.35 36.31 36.11
300 41.66 40.6 40.51

average number of UAVs and the average time consumes are also sum-
marized in Tables 3–6 and Tables 7–10, respectively. It can be seen from coverage of all UEs as well as more time consume to finish the deploy-
these figures and tables that compared with the benchmark schemes, ment as the UE distribution is less dense, which makes it more difficult
the proposed greed-prior algorithms significantly perform better in min- to cover enough UEs by one UAV. This phenomenon also occurs when
imizing the number of UAVs. Moreover, using CA2 BC contributes to increasing the number of UEs as illustrated in Figs. 6(b) and 7(b). The
further decreasing the required time consumes compared with the con- number of required UAVs and the time consume with varying chan-
ventional ABC. nel gain threshold are respectively given Figs. 6(c) and 7(c). It can be
Figs. 6(a) and 7(a) present the comparisons of UAVs’ number and seen how that when the channel gain threshold is relatively large, the
time consume with varying area length. As shown in these figures, en- number of required UAVs and the time consume grow. This is due to
larging the regional area requires more UAVs to provide efficient full that the larger the channel gain threshold is, the smaller the maximum

12
X. Ai, Z. Pu, X. Chai et al. Aerospace Science and Technology 143 (2023) 108731

Fig. 10. Comparison of number of required UAVs under different conditions when the SINR threshold is non-uniform.

Table 5 Table 6
Comparison of required number of UAVs with Comparison of required number of UAVs with
varying channel gain threshold using differ- varying service ability using different algorithms,
ent algorithms, where || = 200, 𝑥max = 𝑦max = where || = 200, 𝑥max = 𝑦max = 6000 m, 𝑔̄𝑘 =
6000 m, 𝑁max = 8. −100 dB.
 
O-ABC GP-ABC GP-CA2 BC O-ABC GP-ABC GP-CA2 BC
𝑔(𝑑𝐵)
̄ 𝑁max
-104 25.53 25.23 25.25 6 37.41 36.56 35.59
-102 27.53 26.89 26.42 7 35.03 34.12 34.02
-100 33.61 32.62 32.09 8 33.61 32.62 32.09
-98 43.75 42.59 42.33 9 33.14 32.33 32.24
-96 57.16 56.55 56.03 10 32.63 32.10 32.03

find better solution with less time consume, which definitely verifies
allowed service radius of the UE is, meaning that the UAV should be the superiority of the proposed scheme.
placed closer to the UE to achieve successful coverage. Figs. 6(d) and
7(d) present the simulation results with varying service ability. Notably, 5.2. Simulation results with non-uniform channel gain threshold
with growing the service ability, the number of required UAVs and the
time consumes decrease as one UAV can serve more UEs at the same To further demonstrate the performance of the proposed algorithm,
time. we also carry out simulations with non-uniform channel gain thresh-
In summary, the simulation results demonstrate that no matter how old. To be specific, the channel gain threshold 𝑔̄𝑘 , ∀𝑘 ∈  is randomly
the conditions change, the proposed GP-CA2 BC algorithm can always selected within the interval [−104, −96] dB. Fig. 8 presents the sim-

13
X. Ai, Z. Pu, X. Chai et al. Aerospace Science and Technology 143 (2023) 108731

Table 7 sition optimization process in Section 4.4 to further enhance the QoS
Comparison of time consumes with varying re- for UEs. The effectiveness of improving the QoS by optimizing the
gional area using different algorithms, where 3D position of each UAV can be evaluated by examining the average,
|| = 200, 𝑔̄𝑘 = −100 dB, 𝑁max = 8. the minimum and the maximum values of channel gain improvement
𝑇 𝑖𝑚𝑒 𝑔𝑚,𝑘 − 𝑔̄𝑘 , 𝑘 ∈ . The comparison of the channel gain improvement be-
O-ABC GP-ABC GP-CA2 BC
𝑥(𝑚)
4000 23.40 22.81 22.57
fore and after 3D position optimization under varying conditions is
5000 25.65 25.18 24.62 illustrated in Fig. 10. Each point shows the average, the maximum and
6000 30.20 29.36 28.13 the minimum results of 100 runs. It can be seen how the minimum value
7000 35.44 34.86 33.58 of channel gain improvement equals to zero, meaning that the channel
8000 40.99 40.90 40.12
gain constraint is satisfied by all UEs and the link between each UE and
its corresponding UAV is successfully established. Moreover, we can
Table 8 also find that no matter how the simulation setting changes, the chan-
Comparison of time consumes with varying num- nel gain improvement after 3D position optimization always increases,
ber of UEs using different algorithms, where indicating the effectiveness of optimizing UAV’s positions in improving
𝑥max = 𝑦max = 6000 m, 𝑔̄𝑘 = −100 dB, 𝑁max = 8. the QoS.
𝑇 𝑖𝑚𝑒
O-ABC GP-ABC GP-CA2 BC

100 22.87 22.46 21.84 6. Discussion
150 26.66 26.31 25.44
200 30.20 29.36 28.13 This paper investigated the 3D deployment problem of multi-UAV
250 33.22 32.72 32.02
mounted BSs for UEs with non-uniform access requirements in obstacle-
300 37.11 36.80 36.19
laden environment. A three-step algorithm was developed to achieve
full coverage of all UEs with guaranteed QoS requirements. Simulation
Table 9 results explicitly demonstrated the efficiency of the proposed algorithm
Comparison of time consumes with varying chan- with various area length, the number of UEs, channel gain threshold,
nel gain threshold using different algorithms, the number of obstacles as well as UAV’s service ability as expected.
where || = 200, 𝑥max = 𝑦max = 6000 m, 𝑁max = 8.
The potential applications of the proposed algorithm include UAV-aided
𝑇 𝑖𝑚𝑒
O-ABC GP-ABC GP-CA2 BC communication after disasters, temporary communication network es-
𝑔̄
-104 23.39 22.58 21.92 tablishment for difficult-to-reach areas, and communication support for
-102 25.05 24.63 23.16 large events. However, there still remain some key problems deserv-
-100 30.20 29.36 28.13 ing future research. Firstly, only static UEs are considered in the paper
-98 38.91 38.28 36.21
while practical scenarios are full of mobile UEs. Secondly, the intra-
-96 50.33 49.91 48.04
communication network among UAVs is not considered in the paper.

Table 10 7. Conclusion
Comparison of time consumes with varying service
ability using different algorithms, where || =
In this paper, we proposed a three-step algorithm to obtain the sub-
200, 𝑥max = 𝑦max = 6000 m, 𝑔̄𝑘 = −100 dB.
optimal solution for deploying multi-UAV-mounted BSs to serve ground
𝑇 𝑖𝑚𝑒
O-ABC GP-ABC GP-CA2 BC UEs located in obstacle-laden environment, with the consideration of
𝑁max
6 23.39 33.19 32.74 the non-uniform QoS requirements of the UEs, the service ability of the
7 25.05 30.72 29.59 UAVs as well as the beamwidth constraint of the directional antenna
8 30.20 29.36 28.13
equipped by the UAVs. First, the maximum allowed service radius sat-
9 29.74 28.65 27.77
10 29.21 27.90 27.02 isfying the SINR requirement was derived based on the KKT condition
for each UE. Second, we developed a GP-CA2 BC algorithm to determine
the minimum number of required UAVs by optimizing the UE cluster-
ulation result obtained by the proposed GP-CA2 BC algorithm with ing. Third, given the UE clustering, the 3D positions of the UAVs were
|| = 200, 𝑥max = 𝑦min = 6000 m, and 𝑁max = 8. It is shown that 48 optimized through CA2 BC such that the QoS was further improved. Fi-
UAVs are deployed in obstacle-free area to realize full coverage of all nally, we presented some simulation results to demonstrate the superior
UEs while satisfying the constraints. performance of the proposed algorithm in terms of decreasing the re-
The simulation results with various conditions, i.e. the area length, quired number of UAVs and enhancing the QoS. Future work will focus
the number of UEs, the UAV’s service ability and the number of obsta- on guidance of multi-UAV-mounted BSs to provide communication ser-
cles, are presented in Fig. 9, illustrating the number of required UAVs vice for mobile UEs.
to achieve full coverage of all UEs. Each point shows the average, the
maximum and the minimum results of 100 runs. Similar conclusions List of abbreviations
can be found as those in Fig. 6. That is, with enlarging regional area
or increasing the number of UEs or decreasing the service ability, more UAV Unmanned aerial vehicle
UAVs are needed to cover the UEs. Moreover, it can be also seen from BS Base station
Fig. 9 that, only a slight decrease of required UAVs can be observed IoT Internet of Things
with the increase of obstacles’ number. This is mainly due to that the 3D Three-dimensional
targets’ distribution becomes denser as the environment becomes more UE User equipment
complex such that the UAV can cover as many targets as possible. How- QoS Quality of Service
ever, compared with the results in Fig. 6, the number of required UAVs LoS Line of Sight
grows when the channel gain threshold is non-uniform. The aforemen- LAP Low altitude platform
tioned results explicitly demonstrate the effectiveness of the proposed SINR signal-to-interference-plus-noise ratio
algorithm when dealing with non-uniform channel gain threshold case. GP-CA2 BC greed-prior chaotic search enabled adaptive artificial
It is shown in Section 4.3 that the 3D deployment can be achieved bee colony
after the UE clustering process. However, we still introduce the 3D po- KKT Karush-Kuhn-Tucke

14
X. Ai, Z. Pu, X. Chai et al. Aerospace Science and Technology 143 (2023) 108731

Declaration of competing interest [21] Z. Mou, Y. Zhang, F. Gao, H. Wang, T. Zhang, Z. Han, Deep reinforcement learning
based three-dimensional area coverage with UAV swarm, IEEE J. Sel. Areas Com-
mun. 39 (10) (2021) 3160–3176.
The authors declare that they have no known competing financial
[22] I. Muhammad Mubashir, A. Zain Anwar, K. Rehan, S. Muhammad, Motion planning
interests or personal relationships that could have appeared to influence of UAV swarm: Recent challenges and approaches, IntechOpen, Rijeka, 2022, Ch. 3,
the work reported in this paper. https://doi.org/10.5772/intechopen.106270.
[23] M. Radmanesh, M. Kumar, P.H. Guentert, M. Sarim, Overview of path-planning
Data availability and obstacle avoidance algorithms for UAVs: a comparative study, Unmanned Syst.
06 (02) (2018) 95–118.
[24] C.H. Liu, Z. Chen, J. Tang, J. Xu, C. Piao, Energy-efficient UAV control for effective
No data was used for the research described in the article. and fair communication coverage: a deep reinforcement learning approach, IEEE J.
Sel. Areas Commun. 36 (9) (2018) 2059–2070.
Acknowledgements [25] J. Lyu, Y. Zeng, R. Zhang, T.J. Lim, Placement optimization of UAV-mounted mobile
base stations, IEEE Commun. Lett. 21 (3) (2017) 604–607.
[26] I. Strumberger, N. Bacanin, S. Tomic, M. Beko, M. Tuba, Static drone placement by
The authors would like to thank the editor and all anonymous re- elephant herding optimization algorithm, in: 2017 25th Telecommunication Forum
viewers for their valuable comments and suggestions. This work was (TELFOR), 2017, pp. 1–4.
supported in part by the National Key Research and Development [27] H. Zhao, H. Wang, W. Wu, J. Wei, Deployment algorithms for UAV airborne net-
Program of China under Grant 2020AAA0103404; in part by the Na- works toward on-demand coverage, IEEE J. Sel. Areas Commun. 36 (9) (2018)
2015–2031.
tional Natural Science Foundation of China under Grants 62073323 and [28] H. Wang, H. Zhao, W. Wu, J. Xiong, D. Ma, J. Wei, Deployment algorithms of
61806199; and in part by the Strategic Priority Research Program of flying base stations: 5G and beyond with UAVs, IEEE Int. Things J. 6 (6) (2019)
Chinese Academy of Sciences under Grant XDA27030204. 10009–10027.
[29] C. Zhang, L. Zhang, L. Zhu, T. Zhang, Z. Xiao, X.G. Xia, 3d deployment of multiple
UAV-mounted base stations for UAV communications, IEEE Trans. Commun. 69 (4)
References
(2021) 2473–2488.
[30] H.E. Hammouti, M. Benjillali, B. Shihada, M. Alouini, Learn-as-you-fly: a distributed
[1] Z. Ullah, F. Al-Turjman, L. Mostarda, Cognition in UAV-aided 5G and beyond com- algorithm for joint 3D placement and user association in multi-UAVs networks, IEEE
munications: a survey, IEEE Trans. Cogn. Commun. Netw. 6 (3) (2020) 872–891. Trans. Wirel. Commun. 18 (12) (2019) 5831–5844.
[2] B. Salau, A. Rawal, D.B. Rawat, Recent advances in artificial intelligence for wireless [31] J. Yao, J. Xu, Joint 3D maneuver and power adaptation for secure UAV communica-
Internet of things and cyber-physical systems: a comprehensive survey, IEEE Int. tion with comp reception, IEEE Trans. Wirel. Commun. 19 (10) (2020) 6992–7006.
Things J. 9 (15) (2022) 12916–12930. [32] S.A. Al-Ahmed, M.Z. Shakir, S.A.R. Zaidi, Optimal 3D UAV base station placement
[3] X. Ai, J. Yu, Flatness-based finite-time leader–follower formation control of multiple by considering autonomous coverage hole detection, wireless backhaul and user
quadrotors with external disturbances, Aerosp. Sci. Technol. 92 (2019) 20–33. demand, J. Commun. Netw. 22 (6) (2020) 467–475.
[4] X. Ai, J. Yu, Fixed-time trajectory tracking for a quadrotor with external distur- [33] M. Hua, L. Yang, Q. Wu, A.L. Swindlehurst, 3D UAV trajectory and communication
bances: a flatness-based sliding mode control approach, Aerosp. Sci. Technol. 89 design for simultaneous uplink and downlink transmission, IEEE Trans. Commun.
(2019) 58–76. 68 (9) (2020) 5908–5923.
[5] K. Hang, X. Lyu, H. Song, J.A. Stork, A.M. Dollar, D. Kragic, F. Zhang, Perching and [34] M. Mozaffari, W. Saad, M. Bennis, M. Debbah, Efficient deployment of multiple
resting—a paradigm for UAV maneuvering with modularized landing gears, Sci. unmanned aerial vehicles for optimal wireless coverage, IEEE Commun. Lett. 20 (8)
Robot. 4 (28) (2019) eaau6637. (2016) 1647–1650.
[6] X. Li, A.V. Savkin, Networked unmanned aerial vehicles for surveillance and moni- [35] J. Qin, Z. Wei, C. Qiu, Z. Feng, Edge-prior placement algorithm for UAV-mounted
toring: a survey, Future Internet 13 (7) (2021) 1–21. base stations, in: 2019 IEEE Wireless Communications and Networking Conference
[7] Z. Wang, L. Duan, R. Zhang, Adaptive deployment for UAV-aided communication (WCNC), 2019, pp. 1–6.
networks, IEEE Trans. Wirel. Commun. 18 (9) (2019) 4531–4543. [36] Y. Liu, K. Liu, J. Han, L. Zhu, Z. Xiao, X.G. Xia, Resource allocation and 3-D place-
[8] A.V. Savkin, H. Huang, Range-based reactive deployment of autonomous drones for ment for UAV-enabled energy-efficient iot communications, IEEE Int. Things J. 8 (3)
optimal coverage in disaster areas, IEEE Trans. Syst. Man Cybern. Syst. 51 (7) (2021) (2021) 1322–1333.
4606–4610. [37] N. Nouri, J. Abouei, A.R. Sepasian, M. Jaseemuddin, A. Anpalagan, K.N. Platani-
[9] A.V. Savkin, H. Huang, Deployment of unmanned aerial vehicle base stations for otis, Three-dimensional multi-UAV placement and resource allocation for energy-
optimal quality of coverage, IEEE Wirel. Commun. Lett. 8 (1) (2019) 321–324. efficient IoT communication, IEEE Int. Things J. 9 (3) (2022) 2134–2152.
[10] B. Li, Z. Fei, Y. Zhang, UAV communications for 5G and beyond: recent advances [38] L. Zhou, X. Zhao, X. Guan, E. Song, X. Zeng, Q. Shi, Robust trajectory planning for
and future trends, IEEE Int. Things J. 6 (2) (2019) 2241–2263. UAV communication systems in the presence of jammers, Chin. J. Aeronaut. 35 (10)
[11] H. Huang, A.V. Savkin, Deployment of heterogeneous UAV base stations for optimal (2022) 265–274.
quality of coverage, IEEE Int. Things J. 9 (17) (2022) 16429–16437. [39] I.A. Elnabty, Y. Fahmy, M. Kafafy, A survey on UAV placement optimization
[12] J. Lyu, Y. Zeng, R. Zhang, Cyclical multiple access in UAV-aided communications: a for UAV-assisted communication in 5G and beyond networks, Phys. Commun. 51
throughput-delay tradeoff, IEEE Wirel. Commun. Lett. 5 (6) (2016) 600–603. (2022) 101564.
[13] A. Al-Hourani, S. Kandeepan, A. Jamalipour, Modeling air-to-ground path loss for [40] J. Won, D.-Y. Kim, Y.-I. Park, J.-W. Lee, A survey on UAV placement and trajec-
low altitude platforms in urban environments, in: 2014 IEEE Global Communica- tory optimization in communication networks: from the perspective of air-to-ground
tions Conference, 2014, pp. 2898–2904. channel models, ICT Express.
[14] A. Al-Hourani, S. Kandeepan, S. Lardner, Optimal lap altitude for maximum cover- [41] N. Tang, H. Tang, B. Li, X. Yuan, Joint maneuver and beamwidth optimization for
age, IEEE Wirel. Commun. Lett. 3 (6) (2014) 569–572. UAV-enabled multicasting, IEEE Access 7 (2019) 149503–149514.
[15] R.I. Bor-Yaliniz, A. El-Keyi, H. Yanikomeroglu, Efficient 3-D placement of an aerial [42] Y. Zeng, Q. Wu, R. Zhang, Accessing from the sky: a tutorial on UAV communica-
base station in next generation cellular networks, in: 2016 IEEE International Con- tions for 5G and beyond, Proc. IEEE 107 (12) (2019) 2327–2375.
ference on Communications (ICC), 2016, pp. 1–5. [43] S. Burer, A.N. Letchford, Non-convex mixed-integer nonlinear programming: a sur-
[16] M. Alzenad, A. El-Keyi, F. Lagum, H. Yanikomeroglu, 3-D placement of an unmanned vey, Surv. Oper. Res. Manag. Sci. 17 (2) (2012) 97–106.
aerial vehicle base station (UAV-BS) for energy-efficient maximal coverage, IEEE [44] Q. Bian, B. Nener, J. Wang, X. Liu, J. Ma, A fitness sharing based ant clustering
Wirel. Commun. Lett. 6 (4) (2017) 434–437. method for multimodal optimization of the aircraft longitudinal automatic carrier
[17] J. You, S. Jung, J. Seo, J. Kang, Energy-efficient 3-D placement of an unmanned landing system, Aerosp. Sci. Technol. 122 (2022) 107392.
aerial vehicle base station with antenna tilting, IEEE Commun. Lett. 24 (6) (2020) [45] J. Shen, S. Wang, X. Zhan, Multi-UAV cluster-based cooperative navigation with
1323–1327. fault detection and exclusion capability, Aerosp. Sci. Technol. 124 (2022) 107570.
[18] M.Y. Arafat, S. Moh, Localization and clustering based on swarm intelligence in [46] D. Karaboga, B. Basturk, A powerful and efficient algorithm for numerical function
UAV networks for emergency communications, IEEE Int. Things J. 6 (5) (2019) optimization: artificial bee colony (ABC) algorithm, J. Glob. Optim. 39 (3) (2007)
8958–8976. 459–471.
[19] L. Hong, H. Guo, J. Liu, Y. Zhang, Toward swarm coordination: topology- [47] W.-J. Yu, Z.-H. Zhan, J. Zhang, Artificial bee colony algorithm with an adaptive
aware inter-UAV routing optimization, IEEE Trans. Veh. Technol. 69 (9) (2020) greedy position update strategy, Soft Comput. 22 (2) (2018) 437–451.
10177–10187. [48] R.M. May, Simple mathematical models with very complicated dynamics, Nature
[20] L. Zhou, S. Leng, Q. Liu, Q. Wang, Intelligent UAV swarm cooperation for multiple 261 (5560) (1976) 459–467.
targets tracking, IEEE Int. Things J. 9 (1) (2022) 743–754.

15