# Beam Selection Assisted UAV-BS Deployment and Trajectory for Beamspace mmWave Systems

Authors: Xingxuan Zuo; Jiankang Zhang; Sheng Chen; Xiaomin Mu
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

Exploiting unmanned aerial vehicles (UAVs) as base stations (UAV-BS) can enhance capacity, coverage, and energy efficiency of wireless communication networks. To fully realize this potential, millimeter wave (mmWave) technology can be exploited with UAV-BS to form mmWave UAV-BS. The major difficulty of mmWave UAV-BS, however, lies in the limited energy of UAV-BS and the multiuser interference (MUI). Beam division multiple access with orthogonal beams can be employed to alleviate the MUI. Since each user has dominant beams around the line of sight direction, beam selection can reduce the power consumption of radio frequency chain. In this paper, we formulate the problem of maximizing the sum rate of all users by optimizing the beam selection for beamspace and UAV-BS deployment in the mmWave UAV-BS system. This nonconvex problem is solved in two steps. First, we propose a signal-to-interference plus noise ratio-based greedy beam selection scheme to ensure that all the ground users in the given area can be served by the UAV-BS, where a zero forcing precoding scheme is used to eliminate the MUI. Then, we utilize the continuous genetic algorithm to find the optimal UAV-BS deployment and beam pattern to maximize the sum rate of all users. Moreover, considering the mobility of the UAV-BS, the UAV-BS trajectory and beam selection for beamspace are optimized in the mmWave UAV-BS system. The simulation results demonstrate the effectiveness of the proposed design for the mmWave UAV-BS system.


---

## Body

## 1. Introduction

Unmanned aerial vehicles (UAVs) have drawn growing attention in a wide range of applications, such as disaster rescue, surveillance and monitoring, aerial imaging, and cargo delivery [1, 2]. Wireless communication utilizing UAVs is a promising technology to achieve fast deployment and flexible reconfiguration [3, 4]. Specifically, UAVs as different types of wireless communication platforms, such as UAV base stations (UAV-BS), aerial relays, and UAV swarms, assist and enhance terrestrial communications [5, 6]. Employing UAV-BS in particular is a cost-effective solution to assist the existing terrestrial communication infrastructure by providing seamless coverage and improving the network performance. Recent researches on UAV-BS can be divided into two main categories.In the first category, UAVs are considered aerial quasi-stationary BSs. The altitude and horizontal positions of UAVs can be separately or jointly optimized to obtain a better air-ground channel for meeting different requirements of ground users [7–9]. Specifically, in [7], the altitude of the UAV-BS was optimized to achieve the maximum coverage for the terrestrial users. By contrast, with the fixed altitude, the horizontal placement of UAV-BS was jointly optimized with the user association in [8]. Furthermore, the joint optimization of altitude and horizontal positions of UAV-BS was investigated in [9], where the aim of the UAV-BS placement is to maximize the number of covered users with minimum transmit power.For the second category, UAVs are considered mobile BSs. By exploiting the mobility of UAV-BS, the communication distance between the UAV-BS and terrestrial users can be significantly shortened via careful design on the trajectory of UAV-BS. In [10], a joint optimization of the UAV-BS trajectory and transmit power for multiple users was developed to dynamically establish short-distance line of sight (LoS) links and thus to improve the throughput of the system. A joint optimization of the UAV-BS trajectory and user scheduling for a UAV-enabled secure system was proposed in [11] to maximize the minimum secrecy rate under the required constraints of UAV-BS and ground users. In [12], a joint optimization of the UAV trajectory and nonorthogonal multiple access (NOMA) precoding was investigated for a UAV-assisted NOMA network, where the UAV trajectory and NOMA precoding are jointly optimized to maximize the sum rate of users served by the UAV-BS and NOMA-network BS.Early researches mainly focused on the UAV-BS working in microwave frequencies with a single antenna owing to the strict constraint of size. Because the UAV-BS also has limited on-board energy, the signals of a single antenna may be significantly attenuated due to the long communication distance between the UAV-BS and ground users [13]. However, by exploiting the small wavelengths of millimeter wave (mmWave) signals, mmWave frequencies can be adopted to the UAV-BS to pack large antenna arrays in small dimensions [14, 15].The combination of UAV-BS and mmWave communication technology therefore offers advantages of enhancing coverage, improving energy efficiency, and providing sufficient bandwidth [16]. An UAV-BS mmWave system can naturally establish LoS links between UAV-BS and ground users to support the connectivity of existing ground wireless networks [17]. Because of limited scattering of air-to-ground links in the mmWave band, the path loss is dominant by LoS. The authors of [18] developed a 3D beamforming approach to achieve efficient and flexible coverage in mmWave UAV-BS communications. In [19], the impact of adaptive navigation on mmWave UAV-BSs was investigated to enhance the system performance. Furthermore, the mmWave UAV-BS deployment optimization is an important issue to improve the performance. In [20], the optimized mmWave UAV-BS deployment, which includes the optimal height, horizontal coordinates, and coverage radius, was analyzed by taking into account human body blockage. Xiao et al. [21] presented a mmWave UAV-BS deployment optimization with a constant modulus beamforming to maximize the sum rate of all ground users. However, since mmWave UAV-BSs place large antenna arrays in a small area, the power consumption of radio frequency (RF) chains is considerable [22], but UAV-BSs typically have limited energy supply. In addition, to support simultaneous transmissions between the mmWave UAV-BS and ground users, the multiuser interference (MUI) mitigation is necessary.Since mmWave UAV-BS signals propagate mainly through LoS paths, users from different directions can be simultaneously served by orthogonal beams, which is known as beam division multiple access (BDMA) [16]. By employing orthogonal beams, MUI can be effectively decreased to improve the system performance [23]. In particular, the discrete lens array (DLA), which points signals in different directions, was employed in BDMA to transform the conventional spatial channel into a beamspace channel [24]. To exploit the sparsity of the beamspace channel, beam selection was investigated in [25] to achieve near-optimal performance with fewer RF chains. In [26], a comparison among different kinds of beam selection schemes was evaluated, in terms of the required number of RF chains as well as the trade-off between spectral efficiency and energy efficiency. Furthermore, the power allocation for BDMA transmission was analyzed in [27] with only statistical channel state information (CSI). In [28], considering the power leakage and the imperfect channel statistics estimation, the RF chains were further reduced after the beamspace transformation in the lens antenna array.There exist increasing interests in the use of the genetic algorithm (GA) for wireless communication and signal processing [29–31], since GA can attain the global optimal solutions of challenging optimization problems with affordable computational complexity and it does not require derivative information [32]. The work [31] applied several evolutionary algorithms, including continuous GA (CGA), to solve the difficult problem of joint channel estimation and turbo multiuser detection/decoding. Compared with discrete GA [32], CGA has high precision, low storage, and high speed without the requirement of prior decoding. In [33], GA was utilized to find the optimal deployment of drones to cover the target area with the lowest cost. However, the method of [33] is based on the single transmit antenna, which can be improved by taking the multiple transmit antennas and MUI into account.The comparison of the recent researches in UAV-BS and BDMA is summarized in Table1. Inspired by the existing research, we focus on the mmWave UAV-BS system, where the mmWave-frequency antenna array and DLA are employed by the UAV-BS to direct signals to different directions and to form the beamspace channel. We propose a beam selection optimization for beamspace and UAV-BS deployment to maximize the sum rate of all ground users. Due to the sparse nature of the beamspace channel in BDMA, the dominant beams are near the LoS directions of the ground users. By properly designing the horizontal positions of the mmWave UAV-BS, not only can the better channel gain be achieved but also the interfering channel distance among the ground users can be enlarged to alleviate the MUI, while imposing lower number of RF chains. However, this design problem is nonconvex and difficult to solve directly. To tackle this challenging optimization problem, we decompose it into two subproblems by first designing the beam selection scheme for beamspace and then finding the optimal positions and beam pattern of the mmWave UAV-BS. For the first subproblem, we propose a signal-to-interference plus noise ratio- (SINR-) based greedy beam selection scheme. When the UAV-BS communicates with its served users, if the served users have different dominant beams, the UAV-BS will naturally select their corresponding dominant beams. However, in the scenario that two or more users have the same dominant beam, the UAV-BS can select the beams to users according to the SINR-based greedy beam selection scheme. Zero forcing (ZF) precoding is used to further eliminate the MUI. Given the SINR-based greedy beam selection, we design a CGA to solve the second subproblem, namely, the optimal deployment of the mmWave UAV-BS system. Similarly, considering the mobility of the mmWave UAV-BS, we also optimize the trajectory of the mmWave UAV-BS by the CGA scheme, given the SINR-based greedy beam selection. The main contributions of this paper are recapped below.
(1)
In this paper, we consider a mmWave UAV-BS, which is equipped with the lens antenna array to serve the multiple ground users. Aimed at maximizing the sum rate of all ground users, the optimization problem of beam selection and UAV deployment is complicated to solve, which is decomposed into two subproblems(2)
First, we propose an SINR-based greedy beam selection scheme for the users which share the same dominant beams, where ZF precoding is employed to further minimize the MUI. Then, the CGA of UAV-BS deployment is designed to optimize the UAV deployment and beam pattern by maximizing the sum rate of ground users(3)
We also formulate an optimization problem of beam selection and UAV-BS trajectory in the multiuser mmWave system to maximize the sum rate of all ground users with the speed constraint of UAV-BS. Given the suboptimal SINR-based greedy beam selection, the CGA-based mmWave UAV-BS trajectory optimization is proposedTable 1
Reference comparison of recent researches.
[7][8][9][10][11][12][18][20][21][25][26][28][33]2016201920172018201820192019201820202016201520182019UAV-BS√√√√√√√√√Deployment√√√√3D deployment√√√√Trajectory√√√mmWave√√√√√Beamforming√√√√√BDMA√√√ZF√√√Beam selection√√√SINR√√√Multiuser√√√√√√√√√√√√Multiuser interference√√√GA√The paper is structured as follows. Section2 introduces the system model and problem formulation. The optimizations of beam selection in beamspace as well as mmWave UAV-BS deployment and trajectory are addressed in Section 3. The design analysis and achievable performance are provided and discussed in Section 4. Section 5 concludes the paper.In this paper,ℝ and ℂ denote the real and complex number fields, respectively. The boldfaced lowercase and uppercase letters stand for vectors and matrices, respectively. ∥·∥ denotes the Euclidean norm, while the transpose and Hermitian transpose operators are denoted by ·T and ·H, respectively. The inverse operation is denoted by ·−1, while tr· represents the trace operation. The operator A\B denotes the set consisting of all elements in A excluding those in B. The integer ceiling operation is denoted by ·, 0K is the K-dimensional zero vector, and IK is the K×K-dimensional identity matrix, while Ai,:i∈I denotes the submatrix consisting of the rows of A with the row indices given by the index set I. The cardinality of the set I is denoted by ∣I∣, and the jth element of I is denoted as Ij, while wk,: and w:,k denote the kth row and kth column of W, respectively.


## 2. System Model and Problem Formulation

As illustrated in Figure1, we consider an mmWave downlink multiuser communication system, where a rotary-wing UAV-BS employs Nt transmit antennas and NRF RF chains to simultaneously communicate with K terrestrial users. The different users are served by different beams. Each ground user is equipped with a single antenna, and the horizontal coordinate of the kth ground user is given by uk=xkykT∈ℝ2×1, 1≤k≤K. We assume that the UAV-BS flies at a constant altitude H (m) above the ground and the location of UAV-BS projected on the ground in the 3D rectangular coordinate system is defined by q=qxqyT∈ℝ2×1.Figure 1
A mmWave UAV-BS serving multiple ground users.


### 2.1. Channel Model

Owing to the flexibility of the UAV-BS, the LoS can be naturally established in low-altitude platforms [34], and scattering is relatively rare in mmWave frequencies for the air-to-ground links. Thus, we assume that the wireless links between the UAV-BS and the ground users are dominant by the LoS paths [18, 35]. Then, the effective channel model between the UAV-BS and the kth ground user can be expressed as [36]
(1)hk=βkaθk,where aθk∈ℂNt×1 is the array steering vector of the kth ground user and βk is the gain of the LoS path for this ground user. The channel coefficient βk depends on the path loss at the mmWave frequency and is given by [37, 38]
(2)βk=14πfm,m×109/c·dkαL,where dk=H2+q−uk2 is the distance between the UAV-BS and the kth ground user, c=3×108 m/s is the speed of light, fm,m is the carrier frequency, and αL is the parameter of the LoS path loss model. In our investigation, fm,m=28 GHz is allocated and αL=0.95 is adopted. In addition, the spatial direction θk is defined as θk=cosϕk, where ϕk is the real angle of departure of the kth ground user. Hence, the range of θk is −1,1. A uniform linear array (ULA) is employed in the mmWave UAV-BS, and the array steering vector for the kth ground user is expressed as [26]
(3)aθk=e−j2πdλ1−Nt2θk⋯e−j2πdλl−Nt−12θk⋯e−j2πdλNt−12θkT,l=0,1,⋯Nt−1,where λ is the signal wavelength and d=λ/2 is the antenna element spacing.


#### 2.1.1. UAV-BS Deployment

For the mmWave UAV-BS deployment, the spatial direction of thekth user θk is related to the placement of the UAV-BS, given as the cosine value of the direction vector from the kth ground user to the UAV-BS and the UAV-BS forward direction vector 100T [21]. Thus, the spatial direction θk is defined as
(4)θk=xkyk0−qxqyH·100Txkyk0T−qxqyHT∥·∥100T=xk−qxxk−qx2+yk−qy2+H2.


#### 2.1.2. UAV-BS Trajectory

To take into account the mobile nature of the UAV-BS, the UAV-BS trajectory should be considered. Specifically, the fly-hover communication protocol [39] of rotary-wing UAV-BS can be adopted to realize the communication with users. The UAV-BS serves the ground users with a constant mission time T, which can be equally divided into N+1 time slots. For this fly-hover communication protocol, the UAV-BS successively visits the N optimized hovering locations and communicates with the ground users when it is hovering at the optimized locations. Since the UAV-BS flies at a constant altitude H, the horizontal coordinate in the nth time slot is defined as qn=qxnqynT, n=0,1,⋯,N+1. In practice, the trajectory of the UAV-BS should satisfy the following constraints:
(5)Atra=q0=qI,qN+1=qF,qn+1−qn≤vmax,0≤n≤N,qn∈qx,l,qx,h×qy,l,qy,h,∀n,where qI,qF∈ℝ2×1 denote the initial and final horizontal locations of the UAV-BS, respectively, and vmax is the maximum speed of the UAV-BS, that is, the UAV-BS velocity v≤vmax, while qx,l,qx,h×qy,l,qy,h denotes the UAV-BS flying area. The forward direction vector of the UAV-BS is related to the location of the next time slot and is defined as qfn=qxn+1−qxnqyn+1−qyn0T, n=0,1,⋯,N. Thus, the spatial direction of the kth user at the nth time slot can be expressed as
(6)θk,n=xkyk0−qxqyH·qfnxkyk0T−qxqyHT∥·∥qfn.


### 2.2. Beamspace Representation

By employing an elaborately designed DLA, the traditional channel (1) in the spatial domain can be translated into an equivalent one in the beamspace or angular domain [40]. In particular, let U∈ℂNt×Nt be the spatial discrete Fourier transform (DFT) matrix representing the operation of the DLA, which is acquired by the steering vectors at the Nt fixed spatial frequencies with uniform spacing [41, 42]. Thus, the DFT matrix U, which contains the Nt orthogonal beams that cover the whole space, is defined as
(7)U=1Ntaψ1aψ2⋯aψNt,where ψn=1/Ntn−Nt+1/2, n=1,2,⋯,Nt, are the predefined spatial directions. The DFT matrix U forms the basis of the Nt-dimensional spatial orthogonal signal space.Letx∈ℂK×1 be the transmitted symbol vector to the K ground users and y∈ℂK×1 be the received signal vector at the K ground users. Then, the system model in the beamspace domain can be expressed as
(8)y=H~HWx+n,where n~CN0k,σn2IK is the additive white Gaussian noise (AWGN) vector with the covariance matrix σn2IK, W∈ℂNt×K is the precoding matrix, and the beamspace channel H~∈ℂNt×K is defined as
(9)H~=hb,1hb,2⋯hb,K=Uh1Uh2⋯UhK=UH,where H∈ℂNt×K is the spatial channel for all the K users and hb,k∈ℂNt×1 is the beamspace channel of the kth user. The beamspace channel H~ indicates that the signals of each user are mapped in the Nt orthogonal beams, and each element of hb,k denotes one of the Nt beams supported by the DLA.


### 2.3. Problem Formulation

#### 2.3.1. UAV-BS Deployment Problem Formulation

Let the UAV hovering areaAdep be defined by
(10)qx,l≤qx≤qx,u,qy,l≤qy≤qy,u,where qx,l and qy,l denote the minimum values of qx and qy, respectively, while qx,u and qy,u represent the maximum values of qx and qy, respectively. The UAV-BS deployment problem is to determine the position q∈Adep to deploy the UAV-BS. Due to the sparse nature of the beamspace channel [24], there are only a few dominant entries of the beamspace channel for each user. The use of the beamspace channel allows us to select the corresponding beams to reduce the dimension of the mmWave UAV-BS system without significant performance loss. The reduced system model in the beamspace domain is given by
(11)y~=H~rHWrx+n,where H~r=H~b,:b∈B and B consists of the indices of the selected beams, while Wr is the precoding matrix with the corresponding reduced dimension. Thus, the received signal at the kth user can be expressed as
(12)y~k=h~rk,:Hw~r:,kxk+∑j=1,j≠kKh~rk,:Hw~r:,jxj+nk,where y~k is the kth element of y~. Based on the above discussion, for the UAV-BS transmission with multiple users, the average achievable rate of the kth user is
(13)Rk=log21+Pt/Kh~rk,:Hw~r:,k2σn2+Pt/K∑j=1,j≠kKh~rk,:Hw~r:,j2,where Pt is the total transmission power of the UAV-BS. Thus, the sum rate of all the users is Rsum=∑k=1KRk.Note that the beamspace channelH~ is a function of the UAV-BS position q, and hence, B also depends on q as well as the way of beam selection. Therefore, Rsum depends on both q and B, and the UAV-BS placement problem in the beamspace domain can be formulated as
(14)maxq,BRsumq,B,s.t.q∈Adep.


#### 2.3.2. UAV-BS Trajectory Problem Formulation

The UAV-BS trajectory problem is to determine the mission trajectoryqnn=0N∈Atra of the UAV-BS. At the nth time slot, given the UAV-BS position qn, the beamspace channel H~ is known. Let Bn be the corresponding selected beam set. In order to study the performance of the UAV-BS trajectory, we consider the sum rate of the kth user served by the UAV-BS in the nth time slot of a mission, which is expressed as
(15)Rkn=log21+Pt1/Kh~rk,:Hnw~r:,kn2σn2+Pt1/K∑j=1,j≠kKh~rk,:Hnw~r:,jn2,where h~rk,:n is the reduced beamspace channel vector of the kth user in the nth time slot, Pt1 denotes the transmit power at the UAV-BS for each time slot, and w~r:,kn is the reduced precoding vector of the kth user in time slot n. Therefore, the sum rate for all the users over the N+1 time slots can be expressed as Rsum,N=∑k=1K∑n=0NRkn.Based on the above discussion, we can formulate the sum rate maximization problem for the UAV-BS trajectory as(16)maxqnn=0N,Bnn=1NRsum,Nqnn=0N,Bnn=1N,s.t.qnn=0N∈Atra.Bnn=1N depends on the UAV-BS trajectory qnn=1N and how the beams are selected at each time slot n.


## 2.1. Channel Model

Owing to the flexibility of the UAV-BS, the LoS can be naturally established in low-altitude platforms [34], and scattering is relatively rare in mmWave frequencies for the air-to-ground links. Thus, we assume that the wireless links between the UAV-BS and the ground users are dominant by the LoS paths [18, 35]. Then, the effective channel model between the UAV-BS and the kth ground user can be expressed as [36]
(1)hk=βkaθk,where aθk∈ℂNt×1 is the array steering vector of the kth ground user and βk is the gain of the LoS path for this ground user. The channel coefficient βk depends on the path loss at the mmWave frequency and is given by [37, 38]
(2)βk=14πfm,m×109/c·dkαL,where dk=H2+q−uk2 is the distance between the UAV-BS and the kth ground user, c=3×108 m/s is the speed of light, fm,m is the carrier frequency, and αL is the parameter of the LoS path loss model. In our investigation, fm,m=28 GHz is allocated and αL=0.95 is adopted. In addition, the spatial direction θk is defined as θk=cosϕk, where ϕk is the real angle of departure of the kth ground user. Hence, the range of θk is −1,1. A uniform linear array (ULA) is employed in the mmWave UAV-BS, and the array steering vector for the kth ground user is expressed as [26]
(3)aθk=e−j2πdλ1−Nt2θk⋯e−j2πdλl−Nt−12θk⋯e−j2πdλNt−12θkT,l=0,1,⋯Nt−1,where λ is the signal wavelength and d=λ/2 is the antenna element spacing.


### 2.1.1. UAV-BS Deployment

For the mmWave UAV-BS deployment, the spatial direction of thekth user θk is related to the placement of the UAV-BS, given as the cosine value of the direction vector from the kth ground user to the UAV-BS and the UAV-BS forward direction vector 100T [21]. Thus, the spatial direction θk is defined as
(4)θk=xkyk0−qxqyH·100Txkyk0T−qxqyHT∥·∥100T=xk−qxxk−qx2+yk−qy2+H2.


### 2.1.2. UAV-BS Trajectory

To take into account the mobile nature of the UAV-BS, the UAV-BS trajectory should be considered. Specifically, the fly-hover communication protocol [39] of rotary-wing UAV-BS can be adopted to realize the communication with users. The UAV-BS serves the ground users with a constant mission time T, which can be equally divided into N+1 time slots. For this fly-hover communication protocol, the UAV-BS successively visits the N optimized hovering locations and communicates with the ground users when it is hovering at the optimized locations. Since the UAV-BS flies at a constant altitude H, the horizontal coordinate in the nth time slot is defined as qn=qxnqynT, n=0,1,⋯,N+1. In practice, the trajectory of the UAV-BS should satisfy the following constraints:
(5)Atra=q0=qI,qN+1=qF,qn+1−qn≤vmax,0≤n≤N,qn∈qx,l,qx,h×qy,l,qy,h,∀n,where qI,qF∈ℝ2×1 denote the initial and final horizontal locations of the UAV-BS, respectively, and vmax is the maximum speed of the UAV-BS, that is, the UAV-BS velocity v≤vmax, while qx,l,qx,h×qy,l,qy,h denotes the UAV-BS flying area. The forward direction vector of the UAV-BS is related to the location of the next time slot and is defined as qfn=qxn+1−qxnqyn+1−qyn0T, n=0,1,⋯,N. Thus, the spatial direction of the kth user at the nth time slot can be expressed as
(6)θk,n=xkyk0−qxqyH·qfnxkyk0T−qxqyHT∥·∥qfn.


## 2.1.1. UAV-BS Deployment

For the mmWave UAV-BS deployment, the spatial direction of thekth user θk is related to the placement of the UAV-BS, given as the cosine value of the direction vector from the kth ground user to the UAV-BS and the UAV-BS forward direction vector 100T [21]. Thus, the spatial direction θk is defined as
(4)θk=xkyk0−qxqyH·100Txkyk0T−qxqyHT∥·∥100T=xk−qxxk−qx2+yk−qy2+H2.


## 2.1.2. UAV-BS Trajectory

To take into account the mobile nature of the UAV-BS, the UAV-BS trajectory should be considered. Specifically, the fly-hover communication protocol [39] of rotary-wing UAV-BS can be adopted to realize the communication with users. The UAV-BS serves the ground users with a constant mission time T, which can be equally divided into N+1 time slots. For this fly-hover communication protocol, the UAV-BS successively visits the N optimized hovering locations and communicates with the ground users when it is hovering at the optimized locations. Since the UAV-BS flies at a constant altitude H, the horizontal coordinate in the nth time slot is defined as qn=qxnqynT, n=0,1,⋯,N+1. In practice, the trajectory of the UAV-BS should satisfy the following constraints:
(5)Atra=q0=qI,qN+1=qF,qn+1−qn≤vmax,0≤n≤N,qn∈qx,l,qx,h×qy,l,qy,h,∀n,where qI,qF∈ℝ2×1 denote the initial and final horizontal locations of the UAV-BS, respectively, and vmax is the maximum speed of the UAV-BS, that is, the UAV-BS velocity v≤vmax, while qx,l,qx,h×qy,l,qy,h denotes the UAV-BS flying area. The forward direction vector of the UAV-BS is related to the location of the next time slot and is defined as qfn=qxn+1−qxnqyn+1−qyn0T, n=0,1,⋯,N. Thus, the spatial direction of the kth user at the nth time slot can be expressed as
(6)θk,n=xkyk0−qxqyH·qfnxkyk0T−qxqyHT∥·∥qfn.


## 2.2. Beamspace Representation

By employing an elaborately designed DLA, the traditional channel (1) in the spatial domain can be translated into an equivalent one in the beamspace or angular domain [40]. In particular, let U∈ℂNt×Nt be the spatial discrete Fourier transform (DFT) matrix representing the operation of the DLA, which is acquired by the steering vectors at the Nt fixed spatial frequencies with uniform spacing [41, 42]. Thus, the DFT matrix U, which contains the Nt orthogonal beams that cover the whole space, is defined as
(7)U=1Ntaψ1aψ2⋯aψNt,where ψn=1/Ntn−Nt+1/2, n=1,2,⋯,Nt, are the predefined spatial directions. The DFT matrix U forms the basis of the Nt-dimensional spatial orthogonal signal space.Letx∈ℂK×1 be the transmitted symbol vector to the K ground users and y∈ℂK×1 be the received signal vector at the K ground users. Then, the system model in the beamspace domain can be expressed as
(8)y=H~HWx+n,where n~CN0k,σn2IK is the additive white Gaussian noise (AWGN) vector with the covariance matrix σn2IK, W∈ℂNt×K is the precoding matrix, and the beamspace channel H~∈ℂNt×K is defined as
(9)H~=hb,1hb,2⋯hb,K=Uh1Uh2⋯UhK=UH,where H∈ℂNt×K is the spatial channel for all the K users and hb,k∈ℂNt×1 is the beamspace channel of the kth user. The beamspace channel H~ indicates that the signals of each user are mapped in the Nt orthogonal beams, and each element of hb,k denotes one of the Nt beams supported by the DLA.


## 2.3. Problem Formulation

### 2.3.1. UAV-BS Deployment Problem Formulation

Let the UAV hovering areaAdep be defined by
(10)qx,l≤qx≤qx,u,qy,l≤qy≤qy,u,where qx,l and qy,l denote the minimum values of qx and qy, respectively, while qx,u and qy,u represent the maximum values of qx and qy, respectively. The UAV-BS deployment problem is to determine the position q∈Adep to deploy the UAV-BS. Due to the sparse nature of the beamspace channel [24], there are only a few dominant entries of the beamspace channel for each user. The use of the beamspace channel allows us to select the corresponding beams to reduce the dimension of the mmWave UAV-BS system without significant performance loss. The reduced system model in the beamspace domain is given by
(11)y~=H~rHWrx+n,where H~r=H~b,:b∈B and B consists of the indices of the selected beams, while Wr is the precoding matrix with the corresponding reduced dimension. Thus, the received signal at the kth user can be expressed as
(12)y~k=h~rk,:Hw~r:,kxk+∑j=1,j≠kKh~rk,:Hw~r:,jxj+nk,where y~k is the kth element of y~. Based on the above discussion, for the UAV-BS transmission with multiple users, the average achievable rate of the kth user is
(13)Rk=log21+Pt/Kh~rk,:Hw~r:,k2σn2+Pt/K∑j=1,j≠kKh~rk,:Hw~r:,j2,where Pt is the total transmission power of the UAV-BS. Thus, the sum rate of all the users is Rsum=∑k=1KRk.Note that the beamspace channelH~ is a function of the UAV-BS position q, and hence, B also depends on q as well as the way of beam selection. Therefore, Rsum depends on both q and B, and the UAV-BS placement problem in the beamspace domain can be formulated as
(14)maxq,BRsumq,B,s.t.q∈Adep.


### 2.3.2. UAV-BS Trajectory Problem Formulation

The UAV-BS trajectory problem is to determine the mission trajectoryqnn=0N∈Atra of the UAV-BS. At the nth time slot, given the UAV-BS position qn, the beamspace channel H~ is known. Let Bn be the corresponding selected beam set. In order to study the performance of the UAV-BS trajectory, we consider the sum rate of the kth user served by the UAV-BS in the nth time slot of a mission, which is expressed as
(15)Rkn=log21+Pt1/Kh~rk,:Hnw~r:,kn2σn2+Pt1/K∑j=1,j≠kKh~rk,:Hnw~r:,jn2,where h~rk,:n is the reduced beamspace channel vector of the kth user in the nth time slot, Pt1 denotes the transmit power at the UAV-BS for each time slot, and w~r:,kn is the reduced precoding vector of the kth user in time slot n. Therefore, the sum rate for all the users over the N+1 time slots can be expressed as Rsum,N=∑k=1K∑n=0NRkn.Based on the above discussion, we can formulate the sum rate maximization problem for the UAV-BS trajectory as(16)maxqnn=0N,Bnn=1NRsum,Nqnn=0N,Bnn=1N,s.t.qnn=0N∈Atra.Bnn=1N depends on the UAV-BS trajectory qnn=1N and how the beams are selected at each time slot n.


## 2.3.1. UAV-BS Deployment Problem Formulation

Let the UAV hovering areaAdep be defined by
(10)qx,l≤qx≤qx,u,qy,l≤qy≤qy,u,where qx,l and qy,l denote the minimum values of qx and qy, respectively, while qx,u and qy,u represent the maximum values of qx and qy, respectively. The UAV-BS deployment problem is to determine the position q∈Adep to deploy the UAV-BS. Due to the sparse nature of the beamspace channel [24], there are only a few dominant entries of the beamspace channel for each user. The use of the beamspace channel allows us to select the corresponding beams to reduce the dimension of the mmWave UAV-BS system without significant performance loss. The reduced system model in the beamspace domain is given by
(11)y~=H~rHWrx+n,where H~r=H~b,:b∈B and B consists of the indices of the selected beams, while Wr is the precoding matrix with the corresponding reduced dimension. Thus, the received signal at the kth user can be expressed as
(12)y~k=h~rk,:Hw~r:,kxk+∑j=1,j≠kKh~rk,:Hw~r:,jxj+nk,where y~k is the kth element of y~. Based on the above discussion, for the UAV-BS transmission with multiple users, the average achievable rate of the kth user is
(13)Rk=log21+Pt/Kh~rk,:Hw~r:,k2σn2+Pt/K∑j=1,j≠kKh~rk,:Hw~r:,j2,where Pt is the total transmission power of the UAV-BS. Thus, the sum rate of all the users is Rsum=∑k=1KRk.Note that the beamspace channelH~ is a function of the UAV-BS position q, and hence, B also depends on q as well as the way of beam selection. Therefore, Rsum depends on both q and B, and the UAV-BS placement problem in the beamspace domain can be formulated as
(14)maxq,BRsumq,B,s.t.q∈Adep.


## 2.3.2. UAV-BS Trajectory Problem Formulation

The UAV-BS trajectory problem is to determine the mission trajectoryqnn=0N∈Atra of the UAV-BS. At the nth time slot, given the UAV-BS position qn, the beamspace channel H~ is known. Let Bn be the corresponding selected beam set. In order to study the performance of the UAV-BS trajectory, we consider the sum rate of the kth user served by the UAV-BS in the nth time slot of a mission, which is expressed as
(15)Rkn=log21+Pt1/Kh~rk,:Hnw~r:,kn2σn2+Pt1/K∑j=1,j≠kKh~rk,:Hnw~r:,jn2,where h~rk,:n is the reduced beamspace channel vector of the kth user in the nth time slot, Pt1 denotes the transmit power at the UAV-BS for each time slot, and w~r:,kn is the reduced precoding vector of the kth user in time slot n. Therefore, the sum rate for all the users over the N+1 time slots can be expressed as Rsum,N=∑k=1K∑n=0NRkn.Based on the above discussion, we can formulate the sum rate maximization problem for the UAV-BS trajectory as(16)maxqnn=0N,Bnn=1NRsum,Nqnn=0N,Bnn=1N,s.t.qnn=0N∈Atra.Bnn=1N depends on the UAV-BS trajectory qnn=1N and how the beams are selected at each time slot n.


## 3. Solution of the Problem

By evaluating the Hessian matrices of the objective functions for the problems (14) and (16), it can be seen that both the optimization problems are nonconvex and highly complex. Therefore, it is challenging to solve the problems (14) and (16) by the existing optimization tools. We focus on the optimization problem of UAV-BS deployment first by separating the problem (14) into two subproblems. The “inner” subproblem determines the selected beam set B giving the UAV-BS position q. A suboptimal SINR beam selection algorithm is introduced to incrementally maximize the sum rate of the mmWave UAV-BS system. With this SINR beam selection scheme, the “outer” subproblem then solves the UAV-BS deployment by employing the CGA algorithm. Next, we solve the optimization problem (16) for UAV-BS trajectory in a similar way. Specifically, the CGA is designed to optimize the UAV-BS trajectory with the proposed suboptimal SINR beam selection scheme.


### 3.1. Beam Selection

Given the UAV-BS positionq, the beamspace channel H~ is known. The proposed SINR beam selection scheme is composed of two parts. The ground users having unique dominant beams can select the dominant beams to communicate with the UAV-BS, while the users having overlap dominant beams will search for the proper beams from the unselected beams by incrementally maximizing the SINR of the mmWave UAV-BS system, where ZF is utilized to further eliminate the MUI.Due to the sparse structure of the beamspace channel in the mmWave UAV-BS system, the beamspace channel for thekth user has dominant values near the LoS direction [25]. Since the dominant beams have the most transmission power, they can be selected for the transmission to reduce the number of RF chains with minor performance loss. In order to reduce the number of RF chains NRF to the minimum, we consider that each user is served by only one beam, and hence, NRF=K. Let the index of the selected dominant beam for user k be Bmax,k, which is defined as [43]
(17)Bmax,k=i⋆=argmax1≤i≤Nthb,ki2,where hb,ki denotes the ith element of the kth column of the beamspace channel H~.Given the beamspace channel vectorshb,k and the corresponding selected beam indexes (17) for 1≤k≤K, the K users can be assigned into the two groups, the nonoverlap group GN and the overlap groups GO. The group GN includes the users having the unique dominant beams, while a user in the group GO has the same selected beam with some other users in GO. In particular, the selected beam set or index of a nonoverlap user i satisfies Bmax,i∩∪j≠i,1≤j≤KBmax,j=∅. On the other hand, if Bmax,i′∩∪j≠i′,1≤j≤KBmax,j≠∅, the i′th user is an overlap user and is assigned to GO. Obviously, GN and GO satisfy GN∪GO=1,2,⋯,K and GO∩GN=∅. We consider an example of K=6 and Nt=8, where Bmax,1=1, Bmax,2=4, Bmax,3=7, Bmax,4=7, Bmax,5=8, and Bmax,6=8. Then, GN=1,2 and GO=3,4,5,6.For nonoverlap userk∈GN, the beam with index Bmax,k will be directly selected, since this dominant beam contains most of the transmission power and causes few interferences to other users. Let BGN denote the selected beams for the nonoverlap users in GN. For the overlap users in GO, the beams should be reselected to communicate with the UAV-BS by maximizing the sum rate of all users. To incrementally maximize the sum rate, the beams which result in the maximum increase in SINR should be selected. In order to mitigate the MUI with the user group GN, the beams for the users in GO are selected from the beam set BR=1,2,⋯,Nt\BGN. Let BGO denote the selected beams for the overlap users in GO.Algorithm 1: Greedy SINR-based beam selection.
Input: H~, Bmax,k for 1≤k≤KOutput: Bsel, H~r1:fork=1⟶K2:ifBmax,k∩∪k′≠k,1≤k′≤KBmax,k′=∅3:k∈GN4:else5:k∈GO6:end7:BGN=∩k∈GNBmax,k8:BGO=∅9:BR=1,2,⋯,Nt\BGN10:forj′=1⟶K−GN11:j=1,2,⋯,K\GNj′12:fori′=1⟶BR13:i=BRi′14:Ci=H~b,:b∈BGN∪BGO∪i15:Fi=CiCiHCi−116:αi=Pt/trFiFiH17:end18:ij⋆=argmax∀iαi219:BGO=BGO∪ij⋆20:BR⟵BR\BRij⋆21:end22:Bsel=BGO∪BGN23:H~r=H~b,:b∈BselThe precoding matrixWr for all the users with the selected beams Bsel=BGO∪BGN can be expressed as
(18)Wr=αFr,where α is the power normalization factor given by
(19)α=PttrFrFrH,and Fr is the ZF precoding matrix expressed as
(20)Fr=H~rH~rHH~r−1,in which H~r=H~b,:b∈Bsel. The SINR with the ZF precoding for user k can be expressed as [44]
(21)SINRk,ZF=Ptα2Kσn2.Thus, the maximization of the SINR can be transformed to the maximization of the normalization factorα with respect to the selected beam set BGO for the overlap users in GO.Hence, we can select the required beams for the overlap users inGO one by one based on a greedy-type beam selection algorithm that identifies the beams with the maximal gains in terms of SINR. Specifically, at each selection stage, a beam is selected for an overlap user in GO which maximizes the gain in the SINR. This greedy beam selection algorithm is summarized in Algorithm 1.


### 3.2. Continuous Genetic Algorithm for UAV-BS Deployment

For givenq, we use Algorithm 1 to select the beam set Bdepq=Bselq. Express the objective function of the UAV-BS deployment problem for this beam selection scheme as fdepq=Rsumq,Bdepq. Hence, with this greedy SINR-based beam selection scheme, the optimization of the UAV-BS deployment can be expressed as
(22)q⋆=argmaxq∈Adepfdepq.We propose to apply the CGA [30, 45, 46] to solve this optimization problem. With Pdep denoting the population size and g being the generation index, the procedure of the CGA-based UAV-BS deployment is detailed below.
(1)
Initialization: atg=0, the initial population of Pdep chromosomes or candidate UAV-BS locations qg,pp=1Pdep are randomly generated over the UAV hovering area Adep. Algorithm 1 is utilized to select the beam set Bdepqg,p for every chromosome qg,p, and then, the fitness value Fdepg,p=fdepqg,p is calculated, for 1≤p≤Pdep. The Pdep chromosomes are ranked from top to bottom according to their fitness values. Denote this ranked population as qg,p;Fdepg,pp=1Pdep with the fitness values Fdepg,1≥Fdepg,2≥⋯≥Fdepg,Pdep(2)
Selection: setg=g+1. The Pkeep,d previous chromosomes with the highest fitness values will survive into the next generation, i.e., qg,p=qg−1,p;Fdepg,p=Fdepg−1,pp=1Pkeep,d, and these high-fitness chromosomes also form a mating pool, where Pkeep,d=Pdep·γdep is the size of the mating pool. The selection ratio γdep decides how many chromosomes are to be chosen for the mating pool from the total Pdep chromosomes. The mating pool is used to select parents to provide Pdep−Pkeep,d offspring for the next generation to maintain a constant-size populationThe rank weighting, a roulette wheel weighting [30], is used to choose chromosomes for mating. With this weighting, the chromosome with the largest fitness has the greatest probability of mating, while the chromosome with the smallest fitness has the lowest probability of mating. Let Pmdep be the probability of selecting the mth chromosome for mating from the Pkeep,d chromosomes, which is calculated as
(23)Pmdep=Pkeep,d−m+1∑m=1Pkeep,dm,1≤m≤Pkeep,d.Then,Pmdep is turned into the cumulative probability Pc,mdep for deciding which chromosome can be selected as a parent. In particular, when a random number Pmum between 0 and 1 is generated, if Pc,m−1dep<Pmum≤Pc,mdep, the mth chromosome will be selected as a parent (mum). For instance, let Pkeep,d=4, and the corresponding Pmdep∈0.4,0.3,0.2,0.1. Then, Pc,mdep∈0.4,0.7,0.9,1. If Pmum=0.33, the first chromosome is selected as “mum.” Similarly, the “dad” chromosome is chosen in the same manner. We adopt two parents producing two offspring as a common form of mating. Thus, Pdep−Pkeep,d parents are required for mating to create new offspring. We will assume that Pdep−Pkeep,d is an even number, and we have selected Pdep−Pkeep,d/2 pairs of parents.
(3)
Crossover: each pair of parents selected for the crossover operation can be expressed as(24)qg,mum=qx,g,mumqy,g,mumT,qg,dad=qx,g,dadqy,g,dadT.They are used to produce two offspringqg,os1 and qg,os2.The single crossover point scheme is utilized to combine the parents’ information. A crossover pointqpc is randomly selected between x and y. If y is selected as the crossover point, i.e., qpc=y, the two new offspring are produced as
(25)qg,os1=qx,g,mumqpc,g,os1T,qg,os2=qx,g,dadqpc,g,os2T,with
(26)qpc,g,os1=qpc,g,mum−μqpc,g,mum−qpc,g,dad=qy,g,mum−μqy,g,mum−qy,g,dad,qpc,g,os2=qpc,g,dad+μqpc,g,mum−qpc,g,dad=qy,g,dad+μqy,g,mum−qy,g,dad,where μ is a random value uniformly selected in the range of 0,1. Similarly, if x is selected as the crossover point, i.e., qpc=x, the crossover operation produces the two corresponding offspring from the pair of parents.Algorithm1 selects the beam set for every offspring, and its fitness value is calculated. After the crossover, the new generation of the chromosomes include the Pkeep,d elitist chromosomes from the previous generation and their Pdep−Pkeep,d offspring. These Pdep chromosomes are ranked from top to bottom according to their fitness values as qg,p;Fdepg,pp=1Pdep.
(4)
Mutation: the elementqpm,g,p of chromosome qg,p is randomly selected to mutate; thereby, the mutated element is replaced by a new random value qpm,l≤qpm,g,p≤qpm,u, where pm=x or y, while 2≤p≤Pdep. We opt to not mutate the best chromosome with the highest fitness found so far, i.e., qg,1. The number of elements that will mutate in each generation is governed by a mutation probability Mdep [45, 46]. Thus, the total number of mutated elements is 2Pdep−1Mdep since each chromosome has 2 elements. The mutation operation is crucial to providing sufficient diversity for the CGAAlgorithm 2: Continuous GA for UAV-BS deployment.
Input: Adep, Pdep, γdep, Gmax,dep, MdepOutput: q⋆, Bdepq⋆1: Setg=0, randomly generate Pdep chromosomes qg,p∈Adep, determine Bdepqg,p with Algorithm 1, and calculate fitness values Fdepg,p, for 1≤p≤Pdep2: RankPdep chromosomes according to their fitness values from top to bottom as qg,p;Fdepg,pp=1Pdep3:Pkeep,d=Pdep·γdep4:whileg≤Gmax,dep5:g=g+16:qg,p;Fdepg,pp=1Pkeep,d=qg−1,p;Fdepg−1,pp=1Pkeep,d7:Pmdep=Pkeep,d−m+1/∑m=1Pkeep,dm,Pmdep⟶Pc,mdep,1≤m≤Pkeep,d8:fori=1⟶Pdep−Pkeep,d/29:     Select pair of parents withPc,mdep from mating pool10:     Use single-point crossover to generate two offspring11:     Calculate their beam sets and fitness values12:end for13:    RankPkeep,d survivals and Pdep−Pkeep,d offspring according to their fitness values from top to bottom as qg,p;Fdepg,pp=1Pdep14:forp=2⟶Pdep15:     Mutateqg,p with mutation probability Mdep16:     If mutated, re-calculate beam set and fitness value17:end for18:     Rank mutated population according to their fitness values from top to bottom asqg,p;Fdepg,pp=1Pdep19:ifg>Gmax,dep20:q⋆=qg,1, Bdepq⋆=Bdepqg,1break21:end if22:end whileAlgorithm1 then selects the beam sets for the mutated chromosomes, and their fitness values are calculated. Afterward, the mutated population of the Pdep chromosomes is ranked again from top to bottom according to their fitness values as qg,p;Fdepg,pp=1Pdep.
(5)
Termination: ifg>Gmax,dep, where Gmax,dep is the maximum number of generations, the procedure stops and the chromosome with the highest fitness is chosen as the solution, i.e., q⋆=qg,1. Otherwise, the procedure repeats from step (2)The CGA-based UAV-BS deployment algorithm is summarized in Algorithm2. The population size Pdep, the maximum number of generations Gmax,dep, the selection ratio γdep, and the mutation probability Mdep are the problem-dependent algorithmic parameters, which need to be carefully chosen.


### 3.3. Continuous Genetic Algorithm for UAV-BS Trajectory

With the initial and final locationsqI and qF fixed, the UAV-BS trajectory has N locations, which is expressed as
(27)qN=qT1qT2⋯qTNT.For givenqn at time slot n, we use Algorithm 1 to select the beam set Btraqn=Bselqn. Denote the overall beam set selected for qN by Algorithm 1 as BtraqN=Bselqnn=1N. Then, the optimization of the UAV-BS trajectory is reduced to
(28)qN⋆=argmaxqN∈AtraftraqN,where the objective function of the UAV-BS trajectory problem is ftraqN=Rsum,NqN,BtraqN. We also apply the CGA to solve this optimization problem. From (27), each chromosome has 2N coordinates, and the pth chromosome in the gth generation can be expressed as
(29)qNg,p=qg,pnn=1N=qx,g,p1qy,g,p1qx,g,p2qy,g,p2⋯qx,g,pNqy,g,pNT.With the population sizePtra, the procedure of the CGA for the UAV-BS trajectory is now detailed.
(1)
Initialization: atg=0, the initial population of Ptra chromosomes qNg,pp=1Ptra is randomly generated, constrained inside Atra. Algorithm 1 then selects the beam sets BtraqNg,pp=1Ptra, and the corresponding fitness values Ftrag,p=ftraqNg,pp=1Ptra are calculated. Then, these Ptra chromosomes are ranked from top to bottom according to their fitness values as qNg,p;Ftrag,pp=1Ptra with the fitness values Ftrag,1≥Ftrag,2≥⋯≥Ftrag,Ptra(2)
Selection: setg=g+1, and retain the Pkeep,t previous chromosomes with the highest fitness values in the next generation as qNg,p=qNg−1,p;Ftrag,p=Ftrag−1,pp=1Pkeep,t, which also form a mating pool, where Pkeep,t=Ptra·γtra with γtra being the selection ratio. As usual, the mating pool is used to select parents to provide Ptra−Pkeep,t offspring for the next generation to maintain a constant-size populationThe rank weight is also adopted to select parents from the mating pool. The probabilityPmtra of the mth chromosome to be selected from the mating pool is again defined by
(30)Pmtra=Pkeep,t−m+1∑m=1Pkeep,tm,1≤m≤Pkeep,t,and Pmtra is converted into the cumulative probability Pc,mtra to choose chromosomes as parents from the mating pool.
(3)
Crossover: the mating strategy with two parents producing two new offspring is utilized, and hence, a total ofPtra−Pkeep,t/2 pairs of parents are selected. A generic pair of two parents selected from the mating pool can be expressed as(31)qNg,mum=qx,g,mum1qy,g,mum1⋯qx,g,mumnqy,g,mumn⋯qx,g,mumNqy,g,mumNT,qNg,dad=qx,g,dad1qy,g,dad1⋯qx,g,dadnqy,g,dadn⋯qx,g,dadNqy,g,dadNT.Algorithm 3: Continuous GA for UAV-BS trajectory.
Input: Atra, Nl, Ptra, γtra, Gmax,tra, MtraOutput: qN⋆, BtraqN⋆1: Setg=0, randomly generate Ptra chromosomes qNg,p∈Atra, determine BtraqNg,p with Algorithm 1, and calculate fitness values Ftrag,p, for 1≤p≤Ptra2: RankPtra chromosomes according to their fitness values from top to bottom as qNg,p;Ftrag,pp=1Ptra3:Pkeep,t=Ptra·γtra4:whileg≤Gmax,tra5:g=g+16:qNg,p;Ftrag,pp=1Pkeep,t=qNg−1,p;Ftrag−1,pp=1Pkeep,t7:Pmtra=Pkeep,t−m+1/∑m=1Pkeep,t‍m,Pmtra⟶Pc,mtra,1≤m≤Pkeep,t8:fori=1⟶Ptra−Pkeep,t/29:     Select pair of parents withPc,mtra from mating pool10:repeat11:      Randomly generateμ12:      Use2Nl-points crossover to produce two offspring qNg,os1, qNg,os213:untilqNg,os1,qNg,os2∈Atra14:     Calculate beam sets and fitness values of two offspring15:end for16:   Rank survivals and offspring according to their fitness values from top to bottom asqNg,p;Ftrag,pp=1Ptra17:forp=2⟶Ptra18:     SelectqNg,p with probability Mtra19:repeat20:      Randomly mutate2Nl elements of qNg,p21:until Mutated chromosome satisfies Atra22:      Calculate beam set and fitness value of mutated chromosome23:end for24:     Rank mutated population according to their fitness values from top to bottom asqNg,p;Ftrag,pp=1Ptra25:ifg>Gmax,tra26:qN⋆=qNg,1, BtraqN⋆=BtraqNg,1break27:end if28:end whileThe number of crossover points depends on the UAV-BS flying areaqx,lqx,h×qy,lqy,h and the maximum speed constraint vmax. In particular, the longest straight flying distance is the diagonal line qx,h−qx,l2+qy,h−qy,l2; thereby, the minimum required number of time slots to fly across the UAV-BS flying area can be expressed as
(32)Nl=qx,h−qx,l2+qy,h−qy,l2vmax−1.Thus, the2Nl-point crossover scheme is utilized to guarantee the offspring satisfying the constraints Atra. Specifically, the first crossover point n is randomly selected from 1,2,⋯,N−Nl+1, and the two offspring produced can be expressed, respectively, as
(33)qNg,os1=qx,g,mum1qy,g,mum1⋯qx,g,mumn−1qy,g,mumn−1qx,g,os1nqy,g,os1nqx,g,os1n+1⋯qx,g,os1n+Nl−1qy,g,os1n+Nl−1qx,g,dadn+Nlqy,g,dadn+Nl⋯qx,g,dadNqy,g,dadNT,qNg,os2=qx,g,dad1qy,g,dad1⋯qx,g,dadn−1qy,g,dadn−1qx,g,os2nqy,g,os2nqx,g,os2n+1⋯qx,g,os2n+Nl−1qy,g,os2n+Nl−1qx,g,mumn+Nlqy,g,mumn+Nl⋯qx,g,mumNqy,g,mumNT.Each offspring contains portions of the “genes” from both parents. Specifically, offspring os1 has mum’s genes before the first crossover point n and dad’s genes after the last crossover point n+Nl−1, while offspring os2 has dad’s genes before the first crossover point n and mum’s genes after the last crossover point n+Nl−1. The new coordinates qx and qy at the crossover points are the combinations of the coordinates from both parents, which can be expressed as
(34)qx/y,g,os1nl=qx/y,g,mumnl−μqx/y,g,mumnl−qx/y,g,dadnl,qx/y,g,os2nl=qx/y,g,dadnl+μqx/y,g,mumnl−qx/y,g,dadnl,for n≤nl≤n+Nl−1, where μ is a random value uniformly selected from 0,1. If the new coordinates produced do not satisfy the maximum speed constraint of Atra, μ is reselected until the new coordinates meet the requirements of Atra.The beam set of every offspring is then selected using Algorithm1, and its fitness value is calculated. The new generation of the chromosomes, including the Pkeep,t elitist chromosomes from the previous generation and their Ptra−Pkeep,t offspring, is ranked from top to bottom according to their fitness values as qNg,p;Ftrag,pp=1Ptra.
(4)
Mutation: the chromosomesqNg,p, 2≤p≤Ptra, are subject to random mutation with the mutation probability Mtra to explore other area of Atra so as to avoid local maxima. Specially, 2Nl points of a chromosome, qx,g,pn,qy,g,pn,⋯,qx,g,pn+Nl−1,qy,g,pn+Nl−1, are randomly chosen to be mutated. If the mutated chromosome does not satisfy the requirement of Atra, the chromosome is remutated until the constraints Atra are met. Given the mutation probability Mtra, a total of 2MtraNPtra−1 elements will be mutatedThe beam sets for the mutated chromosomes are selected with Algorithm1, and their fitness values are calculated. The mutated population of the Ptra chromosomes is ranked again from top to bottom according to their fitness values as qNg,p;Ftrag,pp=1Ptra.
(5)
Termination: ifg>Gmax,tra, where Gmax,tra denotes the maximum number of generations, the procedure stops with the solution qN⋆=qNg,1. Otherwise, the procedure repeats from step (2)This CGA for the UAV-BS trajectory optimization is summarized in Algorithm3.


### 3.4. Complexity Analysis

The complexity of the proposed CGA for the UAV-BS deployment optimization with the aid of the greedy SINR beam selection algorithm is specified by the numberNGA,dep of the cost function evaluations and the complexity per cost function evaluation. Given the population size Pdep and the maximum number of generation Gmax,dep, we have NGA=Pdep·Gmax,dep, whereas the complexity per cost function is derived according to Rsum and the greedy SINR beam selection algorithm. The complexity evaluations of Rsum and the greedy SINR beam selection algorithm are listed in Table 2.Table 2
Complexity in number of operations.
Number of operationshb,ki2∀i,kNtKFK−GN∑i=1K−GNNt−GN−i3GN+i3+2GN+i2αK−GN∑i=1K−GNNt−GN−i2GN+i2+1Rsum2K2+KThus, the complexity of the proposed CGA for the UAV-BS deployment optimization with the aid of the greedy SINR beam selection algorithm isNGA,dep·K−GN∑i=1K−GNNt−GN−i3GN+i3+4GN+i2+1+2K2+Nt+1K. In a similar way, the number NGA,tra of the cost function evaluations of the proposed CGA for the UAV-BS trajectory optimization with the aid of the greedy SINR beam selection algorithm is NGA,tra=Ptra·Gmax,tra, and the complexity of the proposed CGA for the UAV-BS trajectory optimization with the aid of the greedy SINR beam selection algorithm is N·NGA,tra·K−GN∑i=1K−GNNt−GN−i3GN+i3+4GN+i2+1+2K2+Nt+1K.


## 3.1. Beam Selection

Given the UAV-BS positionq, the beamspace channel H~ is known. The proposed SINR beam selection scheme is composed of two parts. The ground users having unique dominant beams can select the dominant beams to communicate with the UAV-BS, while the users having overlap dominant beams will search for the proper beams from the unselected beams by incrementally maximizing the SINR of the mmWave UAV-BS system, where ZF is utilized to further eliminate the MUI.Due to the sparse structure of the beamspace channel in the mmWave UAV-BS system, the beamspace channel for thekth user has dominant values near the LoS direction [25]. Since the dominant beams have the most transmission power, they can be selected for the transmission to reduce the number of RF chains with minor performance loss. In order to reduce the number of RF chains NRF to the minimum, we consider that each user is served by only one beam, and hence, NRF=K. Let the index of the selected dominant beam for user k be Bmax,k, which is defined as [43]
(17)Bmax,k=i⋆=argmax1≤i≤Nthb,ki2,where hb,ki denotes the ith element of the kth column of the beamspace channel H~.Given the beamspace channel vectorshb,k and the corresponding selected beam indexes (17) for 1≤k≤K, the K users can be assigned into the two groups, the nonoverlap group GN and the overlap groups GO. The group GN includes the users having the unique dominant beams, while a user in the group GO has the same selected beam with some other users in GO. In particular, the selected beam set or index of a nonoverlap user i satisfies Bmax,i∩∪j≠i,1≤j≤KBmax,j=∅. On the other hand, if Bmax,i′∩∪j≠i′,1≤j≤KBmax,j≠∅, the i′th user is an overlap user and is assigned to GO. Obviously, GN and GO satisfy GN∪GO=1,2,⋯,K and GO∩GN=∅. We consider an example of K=6 and Nt=8, where Bmax,1=1, Bmax,2=4, Bmax,3=7, Bmax,4=7, Bmax,5=8, and Bmax,6=8. Then, GN=1,2 and GO=3,4,5,6.For nonoverlap userk∈GN, the beam with index Bmax,k will be directly selected, since this dominant beam contains most of the transmission power and causes few interferences to other users. Let BGN denote the selected beams for the nonoverlap users in GN. For the overlap users in GO, the beams should be reselected to communicate with the UAV-BS by maximizing the sum rate of all users. To incrementally maximize the sum rate, the beams which result in the maximum increase in SINR should be selected. In order to mitigate the MUI with the user group GN, the beams for the users in GO are selected from the beam set BR=1,2,⋯,Nt\BGN. Let BGO denote the selected beams for the overlap users in GO.Algorithm 1: Greedy SINR-based beam selection.
Input: H~, Bmax,k for 1≤k≤KOutput: Bsel, H~r1:fork=1⟶K2:ifBmax,k∩∪k′≠k,1≤k′≤KBmax,k′=∅3:k∈GN4:else5:k∈GO6:end7:BGN=∩k∈GNBmax,k8:BGO=∅9:BR=1,2,⋯,Nt\BGN10:forj′=1⟶K−GN11:j=1,2,⋯,K\GNj′12:fori′=1⟶BR13:i=BRi′14:Ci=H~b,:b∈BGN∪BGO∪i15:Fi=CiCiHCi−116:αi=Pt/trFiFiH17:end18:ij⋆=argmax∀iαi219:BGO=BGO∪ij⋆20:BR⟵BR\BRij⋆21:end22:Bsel=BGO∪BGN23:H~r=H~b,:b∈BselThe precoding matrixWr for all the users with the selected beams Bsel=BGO∪BGN can be expressed as
(18)Wr=αFr,where α is the power normalization factor given by
(19)α=PttrFrFrH,and Fr is the ZF precoding matrix expressed as
(20)Fr=H~rH~rHH~r−1,in which H~r=H~b,:b∈Bsel. The SINR with the ZF precoding for user k can be expressed as [44]
(21)SINRk,ZF=Ptα2Kσn2.Thus, the maximization of the SINR can be transformed to the maximization of the normalization factorα with respect to the selected beam set BGO for the overlap users in GO.Hence, we can select the required beams for the overlap users inGO one by one based on a greedy-type beam selection algorithm that identifies the beams with the maximal gains in terms of SINR. Specifically, at each selection stage, a beam is selected for an overlap user in GO which maximizes the gain in the SINR. This greedy beam selection algorithm is summarized in Algorithm 1.


## 3.2. Continuous Genetic Algorithm for UAV-BS Deployment

For givenq, we use Algorithm 1 to select the beam set Bdepq=Bselq. Express the objective function of the UAV-BS deployment problem for this beam selection scheme as fdepq=Rsumq,Bdepq. Hence, with this greedy SINR-based beam selection scheme, the optimization of the UAV-BS deployment can be expressed as
(22)q⋆=argmaxq∈Adepfdepq.We propose to apply the CGA [30, 45, 46] to solve this optimization problem. With Pdep denoting the population size and g being the generation index, the procedure of the CGA-based UAV-BS deployment is detailed below.
(1)
Initialization: atg=0, the initial population of Pdep chromosomes or candidate UAV-BS locations qg,pp=1Pdep are randomly generated over the UAV hovering area Adep. Algorithm 1 is utilized to select the beam set Bdepqg,p for every chromosome qg,p, and then, the fitness value Fdepg,p=fdepqg,p is calculated, for 1≤p≤Pdep. The Pdep chromosomes are ranked from top to bottom according to their fitness values. Denote this ranked population as qg,p;Fdepg,pp=1Pdep with the fitness values Fdepg,1≥Fdepg,2≥⋯≥Fdepg,Pdep(2)
Selection: setg=g+1. The Pkeep,d previous chromosomes with the highest fitness values will survive into the next generation, i.e., qg,p=qg−1,p;Fdepg,p=Fdepg−1,pp=1Pkeep,d, and these high-fitness chromosomes also form a mating pool, where Pkeep,d=Pdep·γdep is the size of the mating pool. The selection ratio γdep decides how many chromosomes are to be chosen for the mating pool from the total Pdep chromosomes. The mating pool is used to select parents to provide Pdep−Pkeep,d offspring for the next generation to maintain a constant-size populationThe rank weighting, a roulette wheel weighting [30], is used to choose chromosomes for mating. With this weighting, the chromosome with the largest fitness has the greatest probability of mating, while the chromosome with the smallest fitness has the lowest probability of mating. Let Pmdep be the probability of selecting the mth chromosome for mating from the Pkeep,d chromosomes, which is calculated as
(23)Pmdep=Pkeep,d−m+1∑m=1Pkeep,dm,1≤m≤Pkeep,d.Then,Pmdep is turned into the cumulative probability Pc,mdep for deciding which chromosome can be selected as a parent. In particular, when a random number Pmum between 0 and 1 is generated, if Pc,m−1dep<Pmum≤Pc,mdep, the mth chromosome will be selected as a parent (mum). For instance, let Pkeep,d=4, and the corresponding Pmdep∈0.4,0.3,0.2,0.1. Then, Pc,mdep∈0.4,0.7,0.9,1. If Pmum=0.33, the first chromosome is selected as “mum.” Similarly, the “dad” chromosome is chosen in the same manner. We adopt two parents producing two offspring as a common form of mating. Thus, Pdep−Pkeep,d parents are required for mating to create new offspring. We will assume that Pdep−Pkeep,d is an even number, and we have selected Pdep−Pkeep,d/2 pairs of parents.
(3)
Crossover: each pair of parents selected for the crossover operation can be expressed as(24)qg,mum=qx,g,mumqy,g,mumT,qg,dad=qx,g,dadqy,g,dadT.They are used to produce two offspringqg,os1 and qg,os2.The single crossover point scheme is utilized to combine the parents’ information. A crossover pointqpc is randomly selected between x and y. If y is selected as the crossover point, i.e., qpc=y, the two new offspring are produced as
(25)qg,os1=qx,g,mumqpc,g,os1T,qg,os2=qx,g,dadqpc,g,os2T,with
(26)qpc,g,os1=qpc,g,mum−μqpc,g,mum−qpc,g,dad=qy,g,mum−μqy,g,mum−qy,g,dad,qpc,g,os2=qpc,g,dad+μqpc,g,mum−qpc,g,dad=qy,g,dad+μqy,g,mum−qy,g,dad,where μ is a random value uniformly selected in the range of 0,1. Similarly, if x is selected as the crossover point, i.e., qpc=x, the crossover operation produces the two corresponding offspring from the pair of parents.Algorithm1 selects the beam set for every offspring, and its fitness value is calculated. After the crossover, the new generation of the chromosomes include the Pkeep,d elitist chromosomes from the previous generation and their Pdep−Pkeep,d offspring. These Pdep chromosomes are ranked from top to bottom according to their fitness values as qg,p;Fdepg,pp=1Pdep.
(4)
Mutation: the elementqpm,g,p of chromosome qg,p is randomly selected to mutate; thereby, the mutated element is replaced by a new random value qpm,l≤qpm,g,p≤qpm,u, where pm=x or y, while 2≤p≤Pdep. We opt to not mutate the best chromosome with the highest fitness found so far, i.e., qg,1. The number of elements that will mutate in each generation is governed by a mutation probability Mdep [45, 46]. Thus, the total number of mutated elements is 2Pdep−1Mdep since each chromosome has 2 elements. The mutation operation is crucial to providing sufficient diversity for the CGAAlgorithm 2: Continuous GA for UAV-BS deployment.
Input: Adep, Pdep, γdep, Gmax,dep, MdepOutput: q⋆, Bdepq⋆1: Setg=0, randomly generate Pdep chromosomes qg,p∈Adep, determine Bdepqg,p with Algorithm 1, and calculate fitness values Fdepg,p, for 1≤p≤Pdep2: RankPdep chromosomes according to their fitness values from top to bottom as qg,p;Fdepg,pp=1Pdep3:Pkeep,d=Pdep·γdep4:whileg≤Gmax,dep5:g=g+16:qg,p;Fdepg,pp=1Pkeep,d=qg−1,p;Fdepg−1,pp=1Pkeep,d7:Pmdep=Pkeep,d−m+1/∑m=1Pkeep,dm,Pmdep⟶Pc,mdep,1≤m≤Pkeep,d8:fori=1⟶Pdep−Pkeep,d/29:     Select pair of parents withPc,mdep from mating pool10:     Use single-point crossover to generate two offspring11:     Calculate their beam sets and fitness values12:end for13:    RankPkeep,d survivals and Pdep−Pkeep,d offspring according to their fitness values from top to bottom as qg,p;Fdepg,pp=1Pdep14:forp=2⟶Pdep15:     Mutateqg,p with mutation probability Mdep16:     If mutated, re-calculate beam set and fitness value17:end for18:     Rank mutated population according to their fitness values from top to bottom asqg,p;Fdepg,pp=1Pdep19:ifg>Gmax,dep20:q⋆=qg,1, Bdepq⋆=Bdepqg,1break21:end if22:end whileAlgorithm1 then selects the beam sets for the mutated chromosomes, and their fitness values are calculated. Afterward, the mutated population of the Pdep chromosomes is ranked again from top to bottom according to their fitness values as qg,p;Fdepg,pp=1Pdep.
(5)
Termination: ifg>Gmax,dep, where Gmax,dep is the maximum number of generations, the procedure stops and the chromosome with the highest fitness is chosen as the solution, i.e., q⋆=qg,1. Otherwise, the procedure repeats from step (2)The CGA-based UAV-BS deployment algorithm is summarized in Algorithm2. The population size Pdep, the maximum number of generations Gmax,dep, the selection ratio γdep, and the mutation probability Mdep are the problem-dependent algorithmic parameters, which need to be carefully chosen.


## 3.3. Continuous Genetic Algorithm for UAV-BS Trajectory

With the initial and final locationsqI and qF fixed, the UAV-BS trajectory has N locations, which is expressed as
(27)qN=qT1qT2⋯qTNT.For givenqn at time slot n, we use Algorithm 1 to select the beam set Btraqn=Bselqn. Denote the overall beam set selected for qN by Algorithm 1 as BtraqN=Bselqnn=1N. Then, the optimization of the UAV-BS trajectory is reduced to
(28)qN⋆=argmaxqN∈AtraftraqN,where the objective function of the UAV-BS trajectory problem is ftraqN=Rsum,NqN,BtraqN. We also apply the CGA to solve this optimization problem. From (27), each chromosome has 2N coordinates, and the pth chromosome in the gth generation can be expressed as
(29)qNg,p=qg,pnn=1N=qx,g,p1qy,g,p1qx,g,p2qy,g,p2⋯qx,g,pNqy,g,pNT.With the population sizePtra, the procedure of the CGA for the UAV-BS trajectory is now detailed.
(1)
Initialization: atg=0, the initial population of Ptra chromosomes qNg,pp=1Ptra is randomly generated, constrained inside Atra. Algorithm 1 then selects the beam sets BtraqNg,pp=1Ptra, and the corresponding fitness values Ftrag,p=ftraqNg,pp=1Ptra are calculated. Then, these Ptra chromosomes are ranked from top to bottom according to their fitness values as qNg,p;Ftrag,pp=1Ptra with the fitness values Ftrag,1≥Ftrag,2≥⋯≥Ftrag,Ptra(2)
Selection: setg=g+1, and retain the Pkeep,t previous chromosomes with the highest fitness values in the next generation as qNg,p=qNg−1,p;Ftrag,p=Ftrag−1,pp=1Pkeep,t, which also form a mating pool, where Pkeep,t=Ptra·γtra with γtra being the selection ratio. As usual, the mating pool is used to select parents to provide Ptra−Pkeep,t offspring for the next generation to maintain a constant-size populationThe rank weight is also adopted to select parents from the mating pool. The probabilityPmtra of the mth chromosome to be selected from the mating pool is again defined by
(30)Pmtra=Pkeep,t−m+1∑m=1Pkeep,tm,1≤m≤Pkeep,t,and Pmtra is converted into the cumulative probability Pc,mtra to choose chromosomes as parents from the mating pool.
(3)
Crossover: the mating strategy with two parents producing two new offspring is utilized, and hence, a total ofPtra−Pkeep,t/2 pairs of parents are selected. A generic pair of two parents selected from the mating pool can be expressed as(31)qNg,mum=qx,g,mum1qy,g,mum1⋯qx,g,mumnqy,g,mumn⋯qx,g,mumNqy,g,mumNT,qNg,dad=qx,g,dad1qy,g,dad1⋯qx,g,dadnqy,g,dadn⋯qx,g,dadNqy,g,dadNT.Algorithm 3: Continuous GA for UAV-BS trajectory.
Input: Atra, Nl, Ptra, γtra, Gmax,tra, MtraOutput: qN⋆, BtraqN⋆1: Setg=0, randomly generate Ptra chromosomes qNg,p∈Atra, determine BtraqNg,p with Algorithm 1, and calculate fitness values Ftrag,p, for 1≤p≤Ptra2: RankPtra chromosomes according to their fitness values from top to bottom as qNg,p;Ftrag,pp=1Ptra3:Pkeep,t=Ptra·γtra4:whileg≤Gmax,tra5:g=g+16:qNg,p;Ftrag,pp=1Pkeep,t=qNg−1,p;Ftrag−1,pp=1Pkeep,t7:Pmtra=Pkeep,t−m+1/∑m=1Pkeep,t‍m,Pmtra⟶Pc,mtra,1≤m≤Pkeep,t8:fori=1⟶Ptra−Pkeep,t/29:     Select pair of parents withPc,mtra from mating pool10:repeat11:      Randomly generateμ12:      Use2Nl-points crossover to produce two offspring qNg,os1, qNg,os213:untilqNg,os1,qNg,os2∈Atra14:     Calculate beam sets and fitness values of two offspring15:end for16:   Rank survivals and offspring according to their fitness values from top to bottom asqNg,p;Ftrag,pp=1Ptra17:forp=2⟶Ptra18:     SelectqNg,p with probability Mtra19:repeat20:      Randomly mutate2Nl elements of qNg,p21:until Mutated chromosome satisfies Atra22:      Calculate beam set and fitness value of mutated chromosome23:end for24:     Rank mutated population according to their fitness values from top to bottom asqNg,p;Ftrag,pp=1Ptra25:ifg>Gmax,tra26:qN⋆=qNg,1, BtraqN⋆=BtraqNg,1break27:end if28:end whileThe number of crossover points depends on the UAV-BS flying areaqx,lqx,h×qy,lqy,h and the maximum speed constraint vmax. In particular, the longest straight flying distance is the diagonal line qx,h−qx,l2+qy,h−qy,l2; thereby, the minimum required number of time slots to fly across the UAV-BS flying area can be expressed as
(32)Nl=qx,h−qx,l2+qy,h−qy,l2vmax−1.Thus, the2Nl-point crossover scheme is utilized to guarantee the offspring satisfying the constraints Atra. Specifically, the first crossover point n is randomly selected from 1,2,⋯,N−Nl+1, and the two offspring produced can be expressed, respectively, as
(33)qNg,os1=qx,g,mum1qy,g,mum1⋯qx,g,mumn−1qy,g,mumn−1qx,g,os1nqy,g,os1nqx,g,os1n+1⋯qx,g,os1n+Nl−1qy,g,os1n+Nl−1qx,g,dadn+Nlqy,g,dadn+Nl⋯qx,g,dadNqy,g,dadNT,qNg,os2=qx,g,dad1qy,g,dad1⋯qx,g,dadn−1qy,g,dadn−1qx,g,os2nqy,g,os2nqx,g,os2n+1⋯qx,g,os2n+Nl−1qy,g,os2n+Nl−1qx,g,mumn+Nlqy,g,mumn+Nl⋯qx,g,mumNqy,g,mumNT.Each offspring contains portions of the “genes” from both parents. Specifically, offspring os1 has mum’s genes before the first crossover point n and dad’s genes after the last crossover point n+Nl−1, while offspring os2 has dad’s genes before the first crossover point n and mum’s genes after the last crossover point n+Nl−1. The new coordinates qx and qy at the crossover points are the combinations of the coordinates from both parents, which can be expressed as
(34)qx/y,g,os1nl=qx/y,g,mumnl−μqx/y,g,mumnl−qx/y,g,dadnl,qx/y,g,os2nl=qx/y,g,dadnl+μqx/y,g,mumnl−qx/y,g,dadnl,for n≤nl≤n+Nl−1, where μ is a random value uniformly selected from 0,1. If the new coordinates produced do not satisfy the maximum speed constraint of Atra, μ is reselected until the new coordinates meet the requirements of Atra.The beam set of every offspring is then selected using Algorithm1, and its fitness value is calculated. The new generation of the chromosomes, including the Pkeep,t elitist chromosomes from the previous generation and their Ptra−Pkeep,t offspring, is ranked from top to bottom according to their fitness values as qNg,p;Ftrag,pp=1Ptra.
(4)
Mutation: the chromosomesqNg,p, 2≤p≤Ptra, are subject to random mutation with the mutation probability Mtra to explore other area of Atra so as to avoid local maxima. Specially, 2Nl points of a chromosome, qx,g,pn,qy,g,pn,⋯,qx,g,pn+Nl−1,qy,g,pn+Nl−1, are randomly chosen to be mutated. If the mutated chromosome does not satisfy the requirement of Atra, the chromosome is remutated until the constraints Atra are met. Given the mutation probability Mtra, a total of 2MtraNPtra−1 elements will be mutatedThe beam sets for the mutated chromosomes are selected with Algorithm1, and their fitness values are calculated. The mutated population of the Ptra chromosomes is ranked again from top to bottom according to their fitness values as qNg,p;Ftrag,pp=1Ptra.
(5)
Termination: ifg>Gmax,tra, where Gmax,tra denotes the maximum number of generations, the procedure stops with the solution qN⋆=qNg,1. Otherwise, the procedure repeats from step (2)This CGA for the UAV-BS trajectory optimization is summarized in Algorithm3.


## 3.4. Complexity Analysis

The complexity of the proposed CGA for the UAV-BS deployment optimization with the aid of the greedy SINR beam selection algorithm is specified by the numberNGA,dep of the cost function evaluations and the complexity per cost function evaluation. Given the population size Pdep and the maximum number of generation Gmax,dep, we have NGA=Pdep·Gmax,dep, whereas the complexity per cost function is derived according to Rsum and the greedy SINR beam selection algorithm. The complexity evaluations of Rsum and the greedy SINR beam selection algorithm are listed in Table 2.Table 2
Complexity in number of operations.
Number of operationshb,ki2∀i,kNtKFK−GN∑i=1K−GNNt−GN−i3GN+i3+2GN+i2αK−GN∑i=1K−GNNt−GN−i2GN+i2+1Rsum2K2+KThus, the complexity of the proposed CGA for the UAV-BS deployment optimization with the aid of the greedy SINR beam selection algorithm isNGA,dep·K−GN∑i=1K−GNNt−GN−i3GN+i3+4GN+i2+1+2K2+Nt+1K. In a similar way, the number NGA,tra of the cost function evaluations of the proposed CGA for the UAV-BS trajectory optimization with the aid of the greedy SINR beam selection algorithm is NGA,tra=Ptra·Gmax,tra, and the complexity of the proposed CGA for the UAV-BS trajectory optimization with the aid of the greedy SINR beam selection algorithm is N·NGA,tra·K−GN∑i=1K−GNNt−GN−i3GN+i3+4GN+i2+1+2K2+Nt+1K.


## 4. Performance Analysis

We evaluate the performance of the proposed CGA for the UAV-BS deployment optimization and the proposed CGA for the UAV-BS trajectory optimization, with the aid of the greedy SINR beam selection algorithm. We consider an UAV-BS simultaneously serving several (K) ground users in a mmWave system. The terrestrial users are randomly distributed in the square area of 0,100×0,100 (m2), and the UAV-BS deployment area/flying area is also this 0,100×0,100 (m2) square area. The main default parameters of this simulated UAV-BS mmWave system are listed in Table 3.Table 3
Default system parameters.
ParameterValueNetworkHeight of UAV-BSH100 mNumber of transmit antennas at UAV-BSNt16AWGNσn2-94 dBmFrequencyfm,m28 GHzLoS parameterαL0.95UAV-BS deploymentPopulation sizePdep20Mutation probabilityMdep0.2Selection ratioγdep0.5Number of generationGmax,dep50UAV-BS trajectoryPopulation sizePtra100Mutation probabilityMtra0.05Number of time slotsN10Maximum speed of UAV-BSvmax50 (m/s)Selection ratioγtra0.5Number of generationGmax,tra50


### 4.1. Performance of the CGA for UAV-BS Deployment

We first quantify the performance of the proposed CGA-based UAV-BS deployment with the aid of the greedy SINR beam selection scheme.Figure2 depicts the achievable sum rate as the function of the number of users for the proposed CGA-optimized UAV-BS deployment, in comparison with the performance attained by the random UAV-BS deployment. Both deployments are aided by the greedy SINR beam selection. The system has the total transmission power Pt=20 dBm. The position of the mmWave UAV-BS in the random deployment is randomly chosen in the square area of 0,100×0,100 m2. As expected, the CGA-optimized UAV-BS deployment outperforms the random deployment. In particular, for the system with K=8 users, the sum rate attained by the proposed optimized approach is about 5 bits/s/Hz higher than that of the random deployment.Figure 2
Comparison of achievable sum rates versus number of users for the CGA-optimized deployment and random deployment, both with the aid of the greedy SINR beam selection, given total transmission powerPt=20 dBm.We also evaluate the achievable sum rates as the functions of the transmit powerPt for our CGA-optimized UAV-BS deployment and the random UAV-BS deployment in Figure 3, for the system of K=4 ground users. Again, the greedy SINR beam selection is utilized by both deployments. It can be seen that our CGA-optimized UAV-BS deployment outperforms the random deployment by around 8 bits/s/Hz.Figure 3
Comparison of achievable sum rates versus total transmit powerPt for the CGA-optimized deployment and random deployment, both with the aid of the greedy SINR beam selection, given K=4 ground users.Next, we investigate the convergence performance of the proposed CGA with the aid of the greedy SINR beam selection for UAV-BS deployment. The system hasK=4 ground users with the total transmission power Pt=20 dBm. Figure 4 depicts the maximum sum rate and the mean sum rate of the population as the function of the number of generations, averaged over 100 independent deployments. It can be observed from Figure 4 that the CGA converges within 30 generations.Figure 4
Convergence performance of the CGA with the aid of greedy SINR beam selection for optimizing UAV-BS deployment, averaged over 100 runs. The system hasK=4 ground users and total transmission power Pt=20 dBm.Our greedy SINR beam selection scheme selects one beam per user by incrementally maximizing the SINR, and it requiresNRF=K RF chains. The maximum channel magnitude selection (MCMS) scheme in [43] is selected as a reference to the proposed greedy SINR beam selection scheme. For the MCMS scheme, by calculating the hb,ki for each beam, m strongest beams can be chosen for each user. To demonstrate its effectiveness, we compare its sum rate performance versus the system transmit power Pt with those of the MCMS scheme with 1 beam per user and 2 beams per user. Again, the system has K=4 ground users. For fair comparison, the CGA-optimized UAV-BS position is used for all the three cases. To mitigate MUI and for a fair comparison, the ZF precoding is also employed in the MCMS scheme. The MCMS scheme chooses the required number of dominant beams for each user, which may result in selecting the same beam for different users. Note that for the scheme with 2 beams per user, the required RF chains are NRF=2K. Figure 5 compares the sum rate performance of these three beam selection schemes as the functions of the transmission power Pt. Observe that our proposed beam selection scheme, which has 1 beam per user, significantly outperforms the MCMS scheme with 1 beam per user. Given Pt=25 dBm, for example, the sum rate of our greedy SINR selection scheme is 13 bits/s/Hz higher than that of the latter. This is because this MCMS scheme selects the strongest beam of each user. But some users may share the same strongest beam, and hence, this scheme may result in interference from selecting the same beams for different users. It was further observed that the sum rate of the MCMS scheme with 2 beams per user is only marginally better than that of our greedy SINR selection scheme of 1 beam per user. This is because although utilizing the second strongest beam for each user is beneficial for enhancing the achievable rate of the individual user, some second strongest beams may be shared by different users too, resulting in the increased interference. Hence, the performance gain of the MCMS scheme by using 2 beams per user is very slight compared with our greedy SINR beam selection scheme.Figure 5
Comparison of achievable sum rates versus total transmit powerPt for three beam selection schemes. The system has K=4 ground users, and the UAV-BS is deployed at the CGA-optimized position.In order to see the trade-off between sum rate performance and RF complexity, we need to investigate the transmit energy efficiency, which is defined by [47]
(35)η=RPt+NRF·PRFbits/s/Hz/W,where R (bits/s/Hz) is the sum rate and PRF (W) represents the power consumed in each RF chain, and PRF=34.4 mW is adopted as the practical value [47]. For the same system setup as in Figures 5 and 6, compare the energy efficiency against the total transmit power Pt achieved by the three beam selection schemes. As observed from Figure 6, the energy efficiency of the MCMS scheme with 2 beams per user is far inferior to that of its counterpart of 1 beam per user, except for high Pt situation. Our greedy SINR selection scheme with 1 beam per user significantly outperforms both MCMS schemes, in terms of energy efficiency. In particular, for Pt=20 dB, although the sum rate of the MCMS scheme with 2 beams per user is about 1 bit/s/Hz better than that of our scheme of 1 beam per user, as shown in Figure 5, the energy efficiency of our greedy SINR beam selection scheme is 57 bits/s/Hz/mW higher than that of the former.Figure 6
Comparison of energy efficiency performance versus total transmit powerPt for three beam selection schemes. The system has K=4 ground users, and the UAV-BS is deployed at the CGA-optimized position.Figure7 shows the achievable sum rate of the proposed CGA-optimized UAV-BS deployment and the random UAV-BS deployment when Nt=256. Both deployments are aided by the greedy SINR beam selection. The system has the total transmission power Pt=20 dBm. As shown in Figure 7, when the number of users is 100, the sum rate of the CGA-optimized UAV-BS deployment is better than that of the random deployment. It can conclude that the proposed CGA-optimized UAV-BS deployment is still robust when the number of users is 100.Figure 7
Comparison of achievable sum rates versus number of users for the CGA-optimized deployment and random deployment, both with the aid of the greedy SINR beam selection, given total transmission powerPt=20 dBm and Nt=256.


### 4.2. Performance of the CGA for UAV-BS Trajectory

In the first experiment, there areK=4 randomly located ground users, whose locations are indicated in Figure 8. The UAV-BS flying trajectory starts from qI=0100T and ends at qF=1000T. The transmit power of the UAV-BS for each time slot is Pt1=20 dBm. Figure 8 depicts the CGA-optimized UAV-BS trajectory and the straight-line UAV-BS trajectory, both with the aid of the greedy SINR beam selection scheme. For the CGA-optimized UAV-BS trajectory, the UAV-BS is able to serve the ground users better by flying closer to them to achieve a higher sum rate. Specifically, the sum rate of the CGA-optimized UAV-BS trajectory is more than 57 bits/s/Hz higher than that achieved by the straight-line trajectory.Figure 8
Comparison of the CGA-optimized UAV-BS trajectory and the shortest straight-line UAV-BS trajectory, both with the aid of the greedy SINR beam selection scheme. The system hasK=4 ground users, and the transmit power per time slot is Pt1=20 dBm.In Figure9, we investigate the convergence performance of the CGA for optimizing UAV-BS trajectory with the aid of the greedy SINR beam selection scheme for the same system of K=4 ground users with the transmit power per time slot Pt1=20 dBm. The curves of the maximum sum rate and mean sum rate in Figure 9 are averaged over 100 runs. It can be seen that the CGA converges within 50 generations. Evidently, the UAV-BS trajectory optimization is much more challenging than the UAV-BS deployment optimization.Figure 9
Convergence performance of the CGA with the aid of greedy SINR beam selection for optimizing UAV-BS trajectory, averaged over 100 runs. The system hasK=4 ground users, and transmit power per time slot is Pt1=20 dBm.Figure10 compares the achievable sum rates as the functions of the number of users K for the CGA-optimized UAV-BS trajectory and the straight-line UAV-BS trajectory, both adopting the greedy SINR beam selection. The transmit power per time slot is Pt1=20 dBm. The UAV-BS’s initial and final coordinates are qI=0100T and qF=1000T, respectively. As shown in Figure 10, the CGA-optimized UAV-BS trajectory outperforms the straight-line UAV-BS trajectory considerably. Furthermore, the sum rate gain of the CGA-optimized UAV-BS trajectory over the straight-line UAV-BS trajectory increases with K.Figure 10
Comparison of achievable sum rates versus number of users for the CGA-optimized UAV-BS trajectory and straight-line UAV-BS trajectory, both with the aid of greedy SINR beam selection, given transmit power per time slotPt1=20 dBm.Figure11 compares the achievable sum rates as the functions of transmit power per time slot Pt1 for the CGA-optimized UAV-BS trajectory and the straight-line UAV-BS trajectory, both adopting the greedy SINR beam selection. K=4 ground users are randomly distributed in the square area of 0,100×0,100 m2. From the results of Figure 11, we observe that the sum rate of the CGA-optimized UAV-BS trajectory is consistently more than 60 bits/s/Hz higher than that achieved by the straight-line UAV-BS trajectory, over the whole range of Pt1 evaluated. When the target sum rate is 600 bits/s/Hz, the CGA-optimized UAV-BS trajectory attains 2.5 dBm gain in Pt1 compared with the straight-line UAV-BS trajectory.Figure 11
Comparison of achievable sum rates versus transmit power per time slotPt1 for the CGA-optimized UAV-BS trajectory and straight-line UAV-BS trajectory, both adopting greedy SINR beam selection. The system has K=4 ground users.For the system adopting the CGA-optimized UAV-BS trajectory with the transmit power per time slotPt1=20 dBm, Figure 12 compares the sum rates versus the number of ground users for the three beam selection schemes, namely, the proposed greedy SINR beam selection with 1 beam per user as well as the MCMS scheme with 1 beam per user and 2 beams per user. It can be seen from Figure 12 that the MCMS scheme with 2 beams per user achieves a slightly better sum rate than our greedy SINR beam selection scheme with 1 beam per user, while our beam selection scheme significantly outperforms the MCMS scheme with 1 beam per user, in terms of sum rate. Our greedy SINR beam selection is the most energy-efficient scheme, while the MCMS scheme with 2 beams per user has the worst energy efficiency, as shown in Figure 13.Figure 12
Comparison of sum rates versus number of usersK for three beam selection schemes, given the system with the CGA-optimized UAV-BS trajectory and transmit power per time slot Pt1=20 dBm.Figure 13
Comparison of energy efficiency performance versus number of users for three beam selection schemes for the system with the CGA-optimized UAV-BS trajectory and transmit power per time slotPt1=20 dBm.Figure14 compares the achievable sum rates of the CGA-optimized UAV-BS trajectory and the straight-line UAV-BS trajectory with Nt=256. Both schemes employ the greedy SINR beam selection. The transmit power per time slot is Pt1=20 dBm. The UAV-BS’s initial and final coordinates are qI=0100T and qF=1000T, respectively. As shown in Figure 10, when the number of users is 50, the sum rate of the CGA-optimized UAV-BS trajectory outperforms that of the straight-line UAV-BS trajectory.Figure 14
Comparison of achievable sum rates versus number of users for the CGA-optimized UAV-BS trajectory and straight-line UAV-BS trajectory, both with the aid of greedy SINR beam selection, given transmit power per time slotPt1=20 dBm and Nt=256.


## 4.1. Performance of the CGA for UAV-BS Deployment

We first quantify the performance of the proposed CGA-based UAV-BS deployment with the aid of the greedy SINR beam selection scheme.Figure2 depicts the achievable sum rate as the function of the number of users for the proposed CGA-optimized UAV-BS deployment, in comparison with the performance attained by the random UAV-BS deployment. Both deployments are aided by the greedy SINR beam selection. The system has the total transmission power Pt=20 dBm. The position of the mmWave UAV-BS in the random deployment is randomly chosen in the square area of 0,100×0,100 m2. As expected, the CGA-optimized UAV-BS deployment outperforms the random deployment. In particular, for the system with K=8 users, the sum rate attained by the proposed optimized approach is about 5 bits/s/Hz higher than that of the random deployment.Figure 2
Comparison of achievable sum rates versus number of users for the CGA-optimized deployment and random deployment, both with the aid of the greedy SINR beam selection, given total transmission powerPt=20 dBm.We also evaluate the achievable sum rates as the functions of the transmit powerPt for our CGA-optimized UAV-BS deployment and the random UAV-BS deployment in Figure 3, for the system of K=4 ground users. Again, the greedy SINR beam selection is utilized by both deployments. It can be seen that our CGA-optimized UAV-BS deployment outperforms the random deployment by around 8 bits/s/Hz.Figure 3
Comparison of achievable sum rates versus total transmit powerPt for the CGA-optimized deployment and random deployment, both with the aid of the greedy SINR beam selection, given K=4 ground users.Next, we investigate the convergence performance of the proposed CGA with the aid of the greedy SINR beam selection for UAV-BS deployment. The system hasK=4 ground users with the total transmission power Pt=20 dBm. Figure 4 depicts the maximum sum rate and the mean sum rate of the population as the function of the number of generations, averaged over 100 independent deployments. It can be observed from Figure 4 that the CGA converges within 30 generations.Figure 4
Convergence performance of the CGA with the aid of greedy SINR beam selection for optimizing UAV-BS deployment, averaged over 100 runs. The system hasK=4 ground users and total transmission power Pt=20 dBm.Our greedy SINR beam selection scheme selects one beam per user by incrementally maximizing the SINR, and it requiresNRF=K RF chains. The maximum channel magnitude selection (MCMS) scheme in [43] is selected as a reference to the proposed greedy SINR beam selection scheme. For the MCMS scheme, by calculating the hb,ki for each beam, m strongest beams can be chosen for each user. To demonstrate its effectiveness, we compare its sum rate performance versus the system transmit power Pt with those of the MCMS scheme with 1 beam per user and 2 beams per user. Again, the system has K=4 ground users. For fair comparison, the CGA-optimized UAV-BS position is used for all the three cases. To mitigate MUI and for a fair comparison, the ZF precoding is also employed in the MCMS scheme. The MCMS scheme chooses the required number of dominant beams for each user, which may result in selecting the same beam for different users. Note that for the scheme with 2 beams per user, the required RF chains are NRF=2K. Figure 5 compares the sum rate performance of these three beam selection schemes as the functions of the transmission power Pt. Observe that our proposed beam selection scheme, which has 1 beam per user, significantly outperforms the MCMS scheme with 1 beam per user. Given Pt=25 dBm, for example, the sum rate of our greedy SINR selection scheme is 13 bits/s/Hz higher than that of the latter. This is because this MCMS scheme selects the strongest beam of each user. But some users may share the same strongest beam, and hence, this scheme may result in interference from selecting the same beams for different users. It was further observed that the sum rate of the MCMS scheme with 2 beams per user is only marginally better than that of our greedy SINR selection scheme of 1 beam per user. This is because although utilizing the second strongest beam for each user is beneficial for enhancing the achievable rate of the individual user, some second strongest beams may be shared by different users too, resulting in the increased interference. Hence, the performance gain of the MCMS scheme by using 2 beams per user is very slight compared with our greedy SINR beam selection scheme.Figure 5
Comparison of achievable sum rates versus total transmit powerPt for three beam selection schemes. The system has K=4 ground users, and the UAV-BS is deployed at the CGA-optimized position.In order to see the trade-off between sum rate performance and RF complexity, we need to investigate the transmit energy efficiency, which is defined by [47]
(35)η=RPt+NRF·PRFbits/s/Hz/W,where R (bits/s/Hz) is the sum rate and PRF (W) represents the power consumed in each RF chain, and PRF=34.4 mW is adopted as the practical value [47]. For the same system setup as in Figures 5 and 6, compare the energy efficiency against the total transmit power Pt achieved by the three beam selection schemes. As observed from Figure 6, the energy efficiency of the MCMS scheme with 2 beams per user is far inferior to that of its counterpart of 1 beam per user, except for high Pt situation. Our greedy SINR selection scheme with 1 beam per user significantly outperforms both MCMS schemes, in terms of energy efficiency. In particular, for Pt=20 dB, although the sum rate of the MCMS scheme with 2 beams per user is about 1 bit/s/Hz better than that of our scheme of 1 beam per user, as shown in Figure 5, the energy efficiency of our greedy SINR beam selection scheme is 57 bits/s/Hz/mW higher than that of the former.Figure 6
Comparison of energy efficiency performance versus total transmit powerPt for three beam selection schemes. The system has K=4 ground users, and the UAV-BS is deployed at the CGA-optimized position.Figure7 shows the achievable sum rate of the proposed CGA-optimized UAV-BS deployment and the random UAV-BS deployment when Nt=256. Both deployments are aided by the greedy SINR beam selection. The system has the total transmission power Pt=20 dBm. As shown in Figure 7, when the number of users is 100, the sum rate of the CGA-optimized UAV-BS deployment is better than that of the random deployment. It can conclude that the proposed CGA-optimized UAV-BS deployment is still robust when the number of users is 100.Figure 7
Comparison of achievable sum rates versus number of users for the CGA-optimized deployment and random deployment, both with the aid of the greedy SINR beam selection, given total transmission powerPt=20 dBm and Nt=256.


## 4.2. Performance of the CGA for UAV-BS Trajectory

In the first experiment, there areK=4 randomly located ground users, whose locations are indicated in Figure 8. The UAV-BS flying trajectory starts from qI=0100T and ends at qF=1000T. The transmit power of the UAV-BS for each time slot is Pt1=20 dBm. Figure 8 depicts the CGA-optimized UAV-BS trajectory and the straight-line UAV-BS trajectory, both with the aid of the greedy SINR beam selection scheme. For the CGA-optimized UAV-BS trajectory, the UAV-BS is able to serve the ground users better by flying closer to them to achieve a higher sum rate. Specifically, the sum rate of the CGA-optimized UAV-BS trajectory is more than 57 bits/s/Hz higher than that achieved by the straight-line trajectory.Figure 8
Comparison of the CGA-optimized UAV-BS trajectory and the shortest straight-line UAV-BS trajectory, both with the aid of the greedy SINR beam selection scheme. The system hasK=4 ground users, and the transmit power per time slot is Pt1=20 dBm.In Figure9, we investigate the convergence performance of the CGA for optimizing UAV-BS trajectory with the aid of the greedy SINR beam selection scheme for the same system of K=4 ground users with the transmit power per time slot Pt1=20 dBm. The curves of the maximum sum rate and mean sum rate in Figure 9 are averaged over 100 runs. It can be seen that the CGA converges within 50 generations. Evidently, the UAV-BS trajectory optimization is much more challenging than the UAV-BS deployment optimization.Figure 9
Convergence performance of the CGA with the aid of greedy SINR beam selection for optimizing UAV-BS trajectory, averaged over 100 runs. The system hasK=4 ground users, and transmit power per time slot is Pt1=20 dBm.Figure10 compares the achievable sum rates as the functions of the number of users K for the CGA-optimized UAV-BS trajectory and the straight-line UAV-BS trajectory, both adopting the greedy SINR beam selection. The transmit power per time slot is Pt1=20 dBm. The UAV-BS’s initial and final coordinates are qI=0100T and qF=1000T, respectively. As shown in Figure 10, the CGA-optimized UAV-BS trajectory outperforms the straight-line UAV-BS trajectory considerably. Furthermore, the sum rate gain of the CGA-optimized UAV-BS trajectory over the straight-line UAV-BS trajectory increases with K.Figure 10
Comparison of achievable sum rates versus number of users for the CGA-optimized UAV-BS trajectory and straight-line UAV-BS trajectory, both with the aid of greedy SINR beam selection, given transmit power per time slotPt1=20 dBm.Figure11 compares the achievable sum rates as the functions of transmit power per time slot Pt1 for the CGA-optimized UAV-BS trajectory and the straight-line UAV-BS trajectory, both adopting the greedy SINR beam selection. K=4 ground users are randomly distributed in the square area of 0,100×0,100 m2. From the results of Figure 11, we observe that the sum rate of the CGA-optimized UAV-BS trajectory is consistently more than 60 bits/s/Hz higher than that achieved by the straight-line UAV-BS trajectory, over the whole range of Pt1 evaluated. When the target sum rate is 600 bits/s/Hz, the CGA-optimized UAV-BS trajectory attains 2.5 dBm gain in Pt1 compared with the straight-line UAV-BS trajectory.Figure 11
Comparison of achievable sum rates versus transmit power per time slotPt1 for the CGA-optimized UAV-BS trajectory and straight-line UAV-BS trajectory, both adopting greedy SINR beam selection. The system has K=4 ground users.For the system adopting the CGA-optimized UAV-BS trajectory with the transmit power per time slotPt1=20 dBm, Figure 12 compares the sum rates versus the number of ground users for the three beam selection schemes, namely, the proposed greedy SINR beam selection with 1 beam per user as well as the MCMS scheme with 1 beam per user and 2 beams per user. It can be seen from Figure 12 that the MCMS scheme with 2 beams per user achieves a slightly better sum rate than our greedy SINR beam selection scheme with 1 beam per user, while our beam selection scheme significantly outperforms the MCMS scheme with 1 beam per user, in terms of sum rate. Our greedy SINR beam selection is the most energy-efficient scheme, while the MCMS scheme with 2 beams per user has the worst energy efficiency, as shown in Figure 13.Figure 12
Comparison of sum rates versus number of usersK for three beam selection schemes, given the system with the CGA-optimized UAV-BS trajectory and transmit power per time slot Pt1=20 dBm.Figure 13
Comparison of energy efficiency performance versus number of users for three beam selection schemes for the system with the CGA-optimized UAV-BS trajectory and transmit power per time slotPt1=20 dBm.Figure14 compares the achievable sum rates of the CGA-optimized UAV-BS trajectory and the straight-line UAV-BS trajectory with Nt=256. Both schemes employ the greedy SINR beam selection. The transmit power per time slot is Pt1=20 dBm. The UAV-BS’s initial and final coordinates are qI=0100T and qF=1000T, respectively. As shown in Figure 10, when the number of users is 50, the sum rate of the CGA-optimized UAV-BS trajectory outperforms that of the straight-line UAV-BS trajectory.Figure 14
Comparison of achievable sum rates versus number of users for the CGA-optimized UAV-BS trajectory and straight-line UAV-BS trajectory, both with the aid of greedy SINR beam selection, given transmit power per time slotPt1=20 dBm and Nt=256.


## 5. Conclusions

In this paper, we have investigated the challenging problems of optimizing the UAV-BS deployment and the UAV-BS trajectory in mmWave systems. We have formulated the optimal deployment/trajectory problem as the one that maximizes the sum rate among the ground users subject to the deployment/trajectory constraints. To solve this highly complex and nonconvex problem, we have decomposed it into two subproblems. First, we have proposed a greedy SINR beam selection scheme for the mmWave UAV-BS multiuser system with one beam per user. Specifically, the users with the unique nonsharing dominant beams use their dominant beams, while the other users select the beams by incrementally maximizing the SINR. With the aid of this greedy SINR beam selection, we have proposed to use the CGA to solve the deployment/trajectory optimization problem to maximize the sum rate. The sum rate and energy efficiency as well as convergence performance have been evaluated for the proposed CGA-optimized UAV-BS deployment and CGA-optimized UAV-BS trajectory. Our studies have demonstrated that the proposed solutions achieve excellent performance, in terms of both sum rate and energy efficiency. The results have also shown that the CGA converges sufficiently fast even for the very challenging UAV-BS trajectory optimization.Our future work will consider that each user is equipped with multiple antennas. The receive beamforming and beam selection can be designed to compensate for the path loss in mmWave frequency.



---

*Source: 1363586-2021-09-30.xml*