# Joint Optimization of 3D Placement and Radio Resource Allocation for per-UAV
Sum Rate Maximization

Asad Mahmood, Thang X. Vu, , Symeon Chatzinotas, ,
Björn Ottersten This work was supported by the Luxembourg National Research
Fund via project 5G-Sky, ref. FNR/C19/IS/13713801/5G-Sky, and project RUTINE,
ref. FNR/C22/IS/17220888/RUTINE.
The part of this work has been accepted for publication at the IEEE
VTC2023-Spring, Italy [1]
The authors are with the Interdisciplinary Centre for Security, Reliability
and Trust (SnT), University of Luxembourg, 4365 Luxembourg City, Luxembourg.
Email: {asad.mahmood, thang.vu, symeon.chatzinotas<EMAIL_ADDRESS>
###### Abstract

Unmanned aerial vehicles (UAV) have emerged as a practical solution that
provides on-demand services to users in areas where the terrestrial network is
non-existent or temporarily unavailable, e.g., due to natural disasters or
network congestion. In general, UAVs’ user-serving capacity is typically
constrained by their limited battery life and the finite communication
resources that highly impact their performance. This work considers the
orthogonal frequency division multiple access (OFDMA) enabled multiple
unmanned aerial vehicles (multi-UAV) communication systems to provide on-
demand services. The main aim of this work is to derive an efficient technique
for the allocation of radio resources, $3$D placement of UAVs, and user
association matrices. To achieve the desired objectives, we decoupled the
original joint optimization problem into two sub-problems: (i) $3$D placement
and user association and (ii) sum-rate maximization for optimal radio resource
allocation, which are solved iteratively. The proposed iterative algorithm is
shown via numerical results to achieve fast convergence speed after fewer than
10 iterations. The benefits of the proposed design are demonstrated via
superior sum-rate performance compared to existing reference designs.
Moreover, results showed that the optimal power and sub-carrier allocation
help to mitigate the inter-cell interference that directly impacts the
system’s performance.

###### Index Terms:

5G, multi UAV communication, convex optimization, internet of things (IoT).

##  I Introduction

The $5$G communication system aims to provide massive connectivity, ultra-
reliable low-latency communication, and ensure the end-user quality of
service. In contrast, according to [2, 3], terrestrial networks have not yet
covered most remote areas due to the sparse human activities in these regions.
Similarly, the goal of providing massive connectivity services is highly
compromised in the case of an emergency where the existing communication
system is disrupted due to natural disasters or faces congestion caused by the
temporal increment in the number of users. Moreover, the excessive demand for
the users’ resources and connectivity represents a challenging task in meeting
the objectives mentioned earlier [4]. To overcome the above-mentioned
challenges, different solutions have been proposed, e.g., device-to-device
communication (D2D), to provide a wide range of communication services that
allow devices in the vicinity of each other to communicate without relaying
account the base station (BS). However, due to the adverse nature of wireless
communication channels in emergency scenarios, it is challenging to optimize
the route between the users [5]. Second, satellite communication emerges as an
effective solution for providing on-demand communication services to users in
emergency scenarios, despite the low data rate and high latency that act as
bottlenecks for widespread adoption, e.g., GEO satellites. [6]. Furthermore,
due to characteristics such as flexibility, adaptive altitude, and effortless
deployment, unmanned aerial vehicles (UAVs) are emerging as an effective
solution for providing reliable communication services to a user located in a
particular location [4].

UAVs, colloquially referred to as drones or flying base stations (BSs), have
gained substantial attention in academia and industries, with applications
ranging from photography to search and rescue operations, package delivery,
agriculture, and other real-time applications [7]. One of the promising but
challenging tasks in UAV communication systems is determining how to deploy
UAVs to provide massive coverage to user equipment (UEs) while meeting quality
of service (QoS) requirements and improving network energy efficiency [8]. Due
to limited battery capacity, it should be carefully considered when designing
the UAV deployment plan, together with other issues such as security, privacy,
and flight regulations [9]. In multi-UAV systems, the placement problem is
more challenging to guarantee a balanced trade-off between shadowing, path
loss, and interference. Recent studies show that an increase in the altitude
of UAVs leads to an increase in the probability of line-of-sight
communication; in contrast, it also adds additional path loss [10]. Hence,
considering the joint UAV deployment in 3D cartesian coordinates and resource
allocation is of great importance to enhance the UAV communication systems in
emergency scenarios. Based on the above motivation, this work focuses on the
joint 3D placement and resource allocation to improve the power efficiency of
the multi-UAV network. The following subsection studies related works on UAV
communication, followed by the main contributions of this paper.

###  I-A Related Works

The study on the UAV placement problem has recently been investigated in both
$2$D [11, 12, 13, 14] and $3$D [15, 16] cartesian coordinates. By employing a
UAV as a relying node, the sum rate of the two-way relaying network can be
improved via a joint optimization of the UAV trajectory and resource
allocation while assuring the user QoS requirements [11]. The authors of [12]
considered a UAV-enabled wireless power communication network to maximize
common throughput by optimizing the trajectory and communication resources
simultaneously while taking the UAV’s maximum speed and users’ energy
neutrality into account. In [13], the authors maximize the UAV communication
network’s average secrecy rate by designing an optimal path and transmission
power control. To improve QoS and provide communication services to edge
users, the authors of [14] considered an OFDMA-enabled UAV relay network. In
[15], authors proposed a UAV placement algorithm to maximize served users
using minimum transmission power. Furthermore, in [16], the authors considered
a wireless sensor network scenario in which UAVs follow an optimal trajectory
to maximize the data collection rate.

The works above optimize the UAV deployment for a single-UAV network, which
may not be applicable in high-demand scenarios. In such cases, employing
multiple UAVs simultaneously could significantly improve the system
performance if the UAV placement, user association, and transmission power
control are properly designed [17, 18, 2, 19, 20, 7]. In multi-UAV systems, 3D
placement design has been proven to be more efficient in terms of the sum rate
than 2D placement via optimizing the UAVs’ altitude to maximize the UAV’s
coverage and minimize inter-UAV interference [17, 18, 2]. Besides providing
massive connectivity and ultra-reliable low-latency communication, energy
efficiency and efficient utilization of resources are also essential
performance metrics. To provide the same user demands, the smaller number of
deployed UAVs is, the higher UAV utilization we have. The authors of [19]
proposed a bisection-based algorithm to determine the minimum number of UAVs
among candidate locations which can provide service to all IoT users. It is
noted that no bandwidth or power allocation was considered therein. The
authors of [20] maximized the average capacity by deploying a minimum number
of UAVs while ensuring that deployed UAVs can cover all massive or scattered
users. A similar approach was considered in [7], which minimizes the number of
UAVs in a 3D coordinate for different system scenarios.

###  I-B Contributions

This work studies the performance of an OFDMA-enabled multi-UAV system
deployed to provide on-demand communication services to ground users. OFDMA is
regarded as a promising candidate for the beyond $5$G wireless networks due to
its numerous benefits, such as flexible bandwidth and power allocation over
users. [21]. Therefore, it fits well into our UAV-enabled wireless
communication network to maximize the system sum rate and minimize the number
of deployed UAVs while meeting given QoS requirements through joint
optimization of $3$D placement, sub-carrier allocation, and power control. The
most related works in the literature to ours are presented in [14, 20]. In
[14], a single OFDMA-based UAV acts as the relay to provide services to cell-
edge users of a BS. Whereas in [20], a 2D-based UAV placement algorithm was
proposed to maximize the average capacity of the UAV. It is noted that the
solution in [20] does not consider power and bandwidth allocation.
Furthermore, [20] considers only the free-space LoS channel model, while we
consider the practically probabilistic channel model. Our contributions are as
follows:

  1. 1.

We consider the joint design of the 3D placement, sub-carrier allocation, and
power control for the per-UAV sum-rate maximization in the downlink OFDMA-
enabled multi-UAV communications to serve users in areas where the existing
communication network is highly compromised by congestion or natural disaster.

  2. 2.

We formulate a joint optimization of 3D UAV placement, user association, sub-
carrier allocation, and transmit power to maximize the system sum rate while
deploying a minimum number of active UAVs. Due to the inherent non-convexity,
the original problem is decoupled into two sub-problems: i) path loss
minimization and ii) sum rate maximization, which is then iteratively solved
to provide the (local) optimal solution to the original joint problem.

  3. 3.

To solve the first sub-problem, we propose a heuristic algorithm to determine
the minimum required UAVs based on the user demands and the ergodic capacity
each UAV can provide, followed by an iteration algorithm to optimize the UAV
3D placement and user association. To tackle the non-convexity of the rate
function in the second sub-problem, a successive convex approximation
(SCA)-based iterative algorithm is proposed. In addition, a binary relaxation
with a proper penalty function is implemented to accelerate the computation
time. We show that the convergence to at least a local optimum of the proposed
iterative algorithm is theoretically guaranteed.

  4. 4.

The effectiveness of the proposed approach is demonstrated by the numerical
results, which show a significant improvement in the number of served users,
power efficiency, and sum rate when deploying a minimum number of UAVs while
adhering to the quality of service constraint of each user.

###  I-C Organization

The following sections summarize the rest of the paper: Section II summarizes
the proposed system model and problem statement. Section III presented an
algorithm for efficient $3D$ UAV deployment and resource allocation. Likewise,
Section IV contains the simulation results. The paper is finally concluded in
Section V

##  II System Model and Problem Formulation

In this work, we consider a down-link UAV-assisted wireless communication
system that provides on-demand services to users in areas where the
terrestrial network is non-existent or temporarily unavailable, e.g., due to
natural disasters or network congestion, as shown in Fig. 1. The considered
system model consists of $M$ available UAVs equipped with $U$ antennas and $N$
users, which are represented by the sets
$\mathcal{M}=\\{1,2,\cdots{\rm{M\\}}}$ and
$\mathcal{N}=\\{1,2,\cdots{\rm{N\\}}}$, respectively. In order to improve
UAVs’ deployment usage, only $L\leq M$ UAVs will be activated to serve the
users. The set of active UAVs is denoted by $\mathcal{L}\subset\mathcal{M}$.
We consider $3D$ coordinates, in which the location of the $l$-th UAV is
represented by $(x^{l},y^{l},h^{l})$, which satisfy:

$\small\left\\{{\begin{array}[]{*{20}{c}}x_{min}\leq{x^{l}}\leq{x_{\max}}\\},{\forall
l}\\\ y_{\min}\leq{y^{l}}\leq{y_{\max}}\\},{\forall l}\\\
h_{\min}\leq{h^{l}}\leq{h_{\max}}\\},{\forall l}\end{array}}\right..$ (1)

where $(.)_{min}$ and $(.)_{max}$ represent the lower and upper bound of
$l$-th UAV coordinates, respectively. The coordinates of the users are denoted
by $\\{x_{n},y_{n},0\\}$. For notation convenience, we denote
${z^{l}}\triangleq\\{{x^{l}},{y^{l}}\\}$ and
${v_{n}}\triangleq\\{{x_{n}},{y_{n}}\\}$ as the horizontal coordinates of
$l$-th UAV and $n$-th UE. The UAVs are assisted by a central controller that
provides information about UE’s location[8]. The total users are divided into
clusters, each of which will be served by one active UAV. In order to minimize
interference, each UAV serves its connected users via OFDMA [14], which
consists of $K$ sub-channels denoted by
$\mathcal{K}=\left\\{{1,\cdots,K}\right\\}$. We note that although there is no
intra-cluster interference, there exists inter-cluster interference caused by
the transmission of neighbouring UAVs.

Figure 1: System model.

Let us denote the sub-channel allocation matrix by
$\textbf{A}\\!\\!=\\!\\![a_{n}^{k,l}{{\rm{]}}_{N\\!\times\\!K\\!\times\\!L}}$,
where $a_{n}^{k,l}=1$ indicates that sub-channel $k$ served by UAV $l$ is
allocated to user $n$ and $a_{n}^{k,l}=0$ otherwise. In addition, we denote
$p_{n}^{k,l}$ as the transmit power from UAV $l$ to user $n$ over sub-channel
$k$. Since UAV $l$ only consumes power on sub-channel $k$ for user $n$ if that
sub-channel is assigned to user $n$, we introduce the following constraint:

$\small{p_{n}^{k,l}\leq a^{k,l}_{n}P_{t}^{Max}},p_{n}^{k,l}\geq
0,a_{n}^{k,l}\in\\{0,1\\},\forall n,k,l.$ (2)

where $P_{t}^{Max}$ is the maximum transmit power of the UAV. The transmit
power constraint (2) not only facilitates the rate function, as will be shown
later in this section but also guarantees no transmit power on sub-channel $k$
if it is not assigned to user $n$. To avoid mutual interference among the
users, each sub-channel in one cluster (served by one UAV) is allocated to
only one user, which imposes the following constraint:

$\small{\sum}_{n\in\mathcal{N}}{{\rm{a}}_{n}^{k,l}}\leq 1,\forall k,l.$ (3)

Similarly, the user association
$\textbf{J}\\!\\!=\\!\\![J_{n}^{l}]_{N\\!\times L}$ is a binary matrix, in
which each entity $J_{n}^{l}$ represents the connection between $l$-th UAV and
$n$-th UE, i.e., $J_{n}^{l}=1$ if user $n$ is associated with UAV $l$, and
$J_{n}^{l}=0$ otherwise. Consequently, the following constraint must be met as
one subchannel is only allocated to a user if it is connected to the
corresponding UAV:

$\small{\sum}_{k\in{\cal K}}{{\rm{a}}_{n}^{k,l}}\leq
J_{n}^{l},\;\;J_{n}^{l}\in\\{0,1\\},\forall n,l.$ (4)

###  II-A Path Loss Model

We consider the general probabilistic channel modelling in which the channel
between UAVs and their associated users includes both LOS and non-LOS (NLOS)
parts. The probability of LoS is primarily determined by the 3D geographical
location of UAVs and users on the ground, as well as the surrounding
environment, as given below [15]:

$\small
PLos_{n}^{l}=\frac{1}{1+{b_{1}}\exp\left({-{b_{2}}(\theta_{n}^{l}-{b_{1}})}\right)}.$
(5)

In (5), $b_{1}$ and $b_{2}$ are the constants representing the environment
condition, and
$\theta_{n}^{l}={180}/\left(\pi\sin\left(h_{l}/d_{n}^{l}\right)\right)$ is the
angle of elevation between the $l$-th UAV and the $n$-th UE,

where $d_{n}^{l}=\sqrt{||z^{l}-v_{n}||^{2}+{h^{l}}^{2}}$ is the distance
between the $l$-th UAV and $n$-th user. The probability of non-line of sight
(PNLos) communication is represented by $PNLos_{n}^{l}=1-PLos_{n}^{l}$.

The air-to-ground (A2G) path loss model of both LoS and NLoS between $l$-th
UAV and $n$-th user is given as

$\small\hat{PL_{n}^{l}}=\left\\{{\begin{array}[]{*{20}{c}}\xi_{LoS}K_{o},\;\;for\;\;LoS\\\
\xi_{NLoS}K_{o},\;for\;\;NLoS\end{array}}\right.,$ (6)

where $\xi_{NLoS}$ and $\xi_{LoS}$ represent the attenuation factors for both
NLoS and LoS links, respectively;
$K_{o}={\left({\frac{{4\pi{f_{c}d_{n}^{l}}}}{c}}\right)^{\alpha}}$; $f_{c}$,
$\alpha$ and $c$ respectively represent the carrier frequency, path loss
exponent and speed of light. Therefore, the UAV-User path loss is given as
follows [22]:

$\small{PL}_{n}^{l}=K_{o}\left[PLos_{n}^{l}\xi_{LoS}+{\xi_{NLoS}}PNLos_{n}^{l}\right].$
(7)

###  II-B Transmission Model

Let $\boldsymbol{h}^{k,l}_{n}\in\mathbb{C}^{U\times 1}$ be the small-scale
fading from UAV $l$ to user $n$ on sub-channel $k$. To improve the receive
SNR, we employ the maximum ratio transmission preceding, which results in an
effective channel gain
$g_{n}^{k,l}=|(\boldsymbol{h}_{n}^{k,l})^{H}\boldsymbol{h}_{n}^{k,l}|^{2}/{PL}_{n}^{l}$,
where ${PL}_{n}^{l}$ is given in (7). transmit ratio The downlink signal
received on the $k$-th subchannel at user $n$ from UAV $l$ is given as
follows:

$\small
y_{n}^{k,l}=\underbrace{\sqrt{p_{n}^{k,l}}g_{n}^{k,l}s_{n}^{k,l}}_{\text{Information
signal}}+\underbrace{\sum_{l^{\prime}\neq l}{\Big{(}{\sum_{n^{\prime}\neq
n}\sqrt{p_{n^{\prime}}^{k,l^{\prime}}}}\Big{)}}g_{n}^{k,l^{\prime}}s_{n^{\prime}}^{k,l^{\prime}}}_{\text{Inter-
cell interference}}+n_{n}^{k}.$ (8)

where $p_{n}^{k,l}$ and $s_{n}^{k,l}$ represent the transmission power of
$l$-th UAV and information transmitted signal with
$\mathbb{E}|s_{n}^{k,l}|^{2}=1$, respectively, and $n_{n}^{k}$ is the Gaussian
noise with zero mean and variance $\sigma^{2}$. The first term on the right-
hand side of (8) represents the information signal transmitted over the sub-
carrier $k$ by the $l$-th UAV to the $n$-th user. The second term represents
the interference caused by other UAVs’ transmission on the same sub-carrier
$k$. Therefore, the signal-to-interference plus noise ratio (SINR) of sub-
channel $k$ of at user $n$ from UAV $l$ is given as

$\gamma{{}_{n}^{k,l}}={p_{n}^{k,l}g_{n}^{k,l}}/(\Phi_{n}^{k,l}+{\sigma^{2}}),$
(9)

where $\Phi_{n}^{k,l}=\sum_{l\neq l^{\prime}}{\left({\sum_{n\neq
n^{\prime}}p_{n^{\prime}}^{k,l^{\prime}}}\right)}g_{n}^{k,l^{\prime}}$ is the
aggregated interference imposed by other UAVs. Thus, the achievable rate of
$n$-th UE connected to $l$-th UAV is calculated as

${R_{n}^{l}}={B}{\sum}_{k\in\mathcal{K}}{\log_{2}}\left({1+\gamma{{}_{n}^{k,l}}}\right).$
(10)

###  II-C Problem Formulation

Unlike previous works, which target only the sum-rate maximization, we also
optimize the system-wise energy usage. Therefore, our objective is to maximize
the ratio between the system sum rate and the number of active UAVs, which is
given as $\Upsilon=\frac{{{R_{sum}}}}{L}=\frac{\sum_{n,l}R_{n}^{l}}{L}$, where
$R_{n}^{l}$ is calculated in (10), and $L$ is the number of active UAVs. We
aim to jointly optimize the UAVs’ 3D placement, user association, power and
subcarrier allocation to maximize the objective function $\Upsilon$. For ease
of presentation, we introduce short-hand notations
$\textbf{W}=\left[{W^{l}\triangleq{x^{l}},{y^{l}},{h^{l}}}\right]$,
$\textbf{P}=[{p_{n}^{k,l}}]{{}_{N\times K\times L}}$,
$\textbf{J}=[{J_{n}^{l}}]{{}_{N\times L}}$, and
${{\textbf{A}=[a}}_{n}^{k,l}{{\rm{]}}_{N\times K\times L}}$. Furthermore, let
us denote $r_{0n}$ as the QoS requirement of user $n$, and
$C^{l}_{Min},C^{l}_{Max}$ as the minimum and maximum numbers of users the UAV
can serve, respectively. Then the joint optimization is formulated as follows:

$\displaystyle\mathbb{P}_{0}:\mathop{\max}_{L,\textbf{W},\textbf{P},\textbf{J},\textbf{A}}\frac{1}{L}{\sum}_{l\in\mathcal{L}}{\sum}_{n\in\mathcal{N}}R_{n}^{l}$
(11a)
$\displaystyle\text{s.t.}\;\text{\lx@cref{creftypeplural~refnum}{Bounds},
\lx@cref{refnum}{Power allocation}, \lx@cref{refnum}{Subcarrier 1}
and~\lx@cref{refnum}{Subcarrier 2}}.$ (11b)
$\displaystyle\;\;\;\;R_{n}^{l}\geq J_{n}^{l}r_{0n},\forall n,l,$ (11c)
$\displaystyle\;\;\;\;{\sum}_{l\in\mathcal{L}}{J_{n}^{l}}\leq 1,\forall n,$
(11d)
$\displaystyle\;\;\;\;{\sum}_{{n}\in\mathcal{N}}{{J_{n}^{l}}\in[C^{l}_{Min},C^{l}_{Max}]},\forall
l,$ (11e)
$\displaystyle\;\;\;\;{\sum}_{n\in\cal{N}}{{\sum}_{k\in\mathcal{K}}{p_{n}^{k,l}\leq
P_{t}^{Max}}},\forall l,$ (11f)
$\displaystyle\;\;\;\;{\sum}_{n\in\cal{N}}{{\sum}_{l\in\cal{L}}}J_{n}^{l}\geq\lambda
N,$ (11g)
$\displaystyle\;\;\;\;\mathop{\|{{W^{l}}-{W^{l^{\prime}}}}\|}\geq{d_{{}_{o}}},{\forall
l}.$ (11h)

Our objective in this work is to deploy a minimum number of UAVs to maximize
the average serving rate, subject to QoS and system resource requirements. In
problem $\mathbb{P}_{0}$, constraint (11c) ensures the QoS requirement of
corresponding UE-UAV link; (11d) guarantees that no UE is connected to more
than one UAV; (11e) represents the bounds of the serving capacity of each UAV;
(11f) restricts the total transmit power at each UAV should not exceed the
maximum power; (11g) guarantees the minimum $\lambda$ per cent of the UEs
should be served; finally, (11h) constraints the distance between the two
neighbouring UAVs not exceeding the minimum allowable distance to avoid a
collision. Note that by setting $\lambda$ equals to 1, constraints (11g)
together with (11c) assure the QoS requirements for all users.

##  III Framework for Optimal 3D Placement, User Association, and Radio
Resource Allocation

The optimization problem in (11) is mixed-integer non-linear programming
(MINLP) and NP-hard due to the integer nature of the user association matrix
J, and sub-carrier allocation matrix A. Furthermore, it is challenging to get
optimal results as it involves non-linear, non-convex objective function and
constraints. Towards an efficient solution to problem $\mathbb{P}_{0}$ in
(11), we decouple the original optimization problem into two sub-problems: i)
the first sub-problem, denoted by $\mathbb{P}_{1}$, optimizes the number of
active UAVs, their optimal 3D placement, and the user association to minimize
the average path loss; ii) and the second sub-problem, denoted by
$\mathbb{P}_{2}$, optimizes the radio resources (power and subcarrier
allocation) to minimize inter-cell interference and maximize the sum rate of
users. In the following, we will detail the sub-problems, whose overview
diagram of the problem decomposition is shown in Fig. 2.

Figure 2: Road-map of iterative algorithms.

###  III-A Solving $\mathbb{P}_{1}$: Optimal 3D Placement and User Association

The first sub-problem is directly obtained from the original problem by
treating the radio resources ($\boldsymbol{A}$ and $\boldsymbol{P}$) as
constants, which is formulated as follows:

$\displaystyle\mathbb{P}_{1}:\mathop{\max}_{L,\textbf{W},\textbf{J}}~{}~{}\frac{1}{L}{\sum}_{l\in\mathcal{N}}{\sum}_{n\in\mathcal{N}}R_{n}^{l}$
(12) $\displaystyle\text{s.t.}\;\text{\lx@cref{creftypeplural~refnum}{Bounds},
\lx@cref{refnum}{Subcarrier 2}, \lx@cref{refnum}{C1}, \lx@cref{refnum}{C2},
\lx@cref{refnum}{C3_4}, \lx@cref{refnum}{C6} <EMAIL_ADDRESS>
Jointly optimizing the number of active UAVs, their 3D locations, and user
association is challenging. To address this issue, we initially present a
practical and effective heuristic approach to determine the optimal number of
required UAVs denoted by $L$. Intuitively, $L$ should depend on factors such
as the number of ground users, the QoS requirements, and the average capacity
of the networks [23]. By employing Shannon’s capacity bound, the average
spectral efficiency of any arbitrary user can be calculated as follows:

$\Lambda=\mathbb{E}\Big{[}\log_{2}\Big{(}1+\frac{P_{t}^{max}}{f_{c}\sigma^{2}}\Big{(}\frac{|\textbf{h}^{H}\textbf{h}|^{2}}{{PL}}\Big{)}\Big{)}\Big{]}.$
(13)

Based on equation (7), the path loss is primarily determined by the LoS
channel, which is dependent on the 3D geographical locations of the UAVs. We
assume that the UAVs are positioned in a manner that ensures LoS dominance,
i.e., $PLos\simeq 1$. Hence, the maximum data rate that a user can achieve
over the bandwidth $B$ is represented by $R^{max}=B\times\Lambda$. To satisfy
the QoS requirement $r_{0n}$, the maximum number of user equipment (UEs) that
each UAV can support is given by
${C^{\max}}=\left\lfloor\frac{R^{max}}{r_{0n}}\right\rfloor,\forall n$.
Consequently, we employ a heuristic approach to determine the number of active
UAVs denoted by $L=\left\lceil{\frac{\lambda N}{{{C^{\max}}}}}\right\rceil$,
where $\lambda$ denotes the percentage of users that need to be served. Let
$\mathcal{L}$ represent the set of active UAVs.
Once the number of active UAVs $L$ is determined, the sub-problem
$\mathbb{P}_{1}$ focuses on optimizing the placement of active UAV’s in 3D
space and their user associations. The altitude of each UAV is a critical
factor in determining the probability of the line-of-sight (LoS) channel
$PLos_{n}^{l}$. As the altitude of the UAV increases, so does the angle of
elevation $\left(\theta_{n}^{l}\right)$, resulting in an increase in the value
of $PLos_{n}^{l}$. However, higher altitude also leads to greater path losses
between the UAV and its associated users, resulting in reduced sum rate [24].
Thus, the primary objective of the first sub-problem is to minimize path
losses. To achieve this goal, the UAVs should be placed in locations where the
probability of LoS communication is greater than or equal to a threshold value
$\phi$, i.e., $PLos_{n}^{l}\left(\theta_{n}^{l}\right)\geq\phi$. Additionally,
each user should only be associated with the UAV located at a distance less
than $h^{l}/\sin(PLos_{n}^{l}{{}^{-1}}(\phi))$.

####  III-A1 User Association

Based on the above analysis, we propose to solve the first sub-problem via an
alternative optimization algorithm, which treats each of the UAVs’ locations
and the user association matrix independently, assuming the other is fixed.
Therefore, we model an iterative mathematical framework for optimal $3$D
placement and user association to minimize the path loss between the UAVs and
their associated users. Following that, the UEs association problem, given the
location of UAVs and UEs, can be formulated as follows:

$\displaystyle\mathbb{P}_{1}^{a}:$
$\displaystyle\;\mathop{\min}_{\bf{J}}{\sum}_{n\in\cal{N}}{{\sum}_{l\in\cal{L}}{{J_{n}^{l}}{{\left\|{{{\bf{V}}_{n}}-{{\bf{W}}_{l}}}\right\|}^{2}}}}$
(14a) $\displaystyle~{}\text{\lx@cref{creftypeplural~refnum}{C2},
\lx@cref{refnum}{C3_4} and~\lx@cref{refnum}{C6}},$ (14b)
$\displaystyle{J_{n}^{l}}\left\|{{{\bf{V}}_{n}}-{{\bf{W}}_{l}}}\right\|\leq\frac{{{h_{l}}}}{\sin(PLos_{n}^{l}{{}^{-1}}(\phi))},\forall
n,l.$ (14c)

where ${{\bf{V}}_{n}}\triangleq\left({{x_{n}},{y_{n}},0}\right)$ represents
the location of user $n$. The optimization problem mentioned in (14) is
integer linear programming and convex in nature and can be solved using the
standard methods, e.g., integer linear programming (ILP).

####  III-A2 UAV’s Location

Given the user association matrix J calculated in problem (14), the location
of the UAV is updated such that the distance between the UAV and associated
UEs is minimized. Denote $Q^{l}$ $\in$ $\mathcal{Q}$ as the number of UEs
associated with the $l$-th UAV, the UAVs’$3$D placement problem can be
formulated as follows:

$\displaystyle\mathbb{P}_{1}^{b}:$
$\displaystyle\mathop{\min}_{\mathbf{W}}{\sum}_{n\in{\cal{Q}}^{l}}{\left[{{{\left({{x_{n}}-{x_{l}}}\right)}^{2}}+{{\left({{y_{n}}-{y_{l}}}\right)}^{2}}+h_{l}^{2}}\right],\forall
l},$ (15a)
$\displaystyle{\left({{x_{n}}-{x_{l}}}\right)^{2}}+{\left({{y_{n}}-{y_{l}}}\right)^{2}}+h_{l}^{2}\xi\leq{\rm{0,}}\forall
n\in{\cal{Q}}^{l},$ (15b)
$\displaystyle\text{\lx@cref{creftypeplural~refnum}{Bounds}
<EMAIL_ADDRESS>(15c)

The parameter $\xi=1-1/\sin(PLos_{n}^{l}{{}^{-1}}(\phi))$ is introduced in
constraint (15b) to ensure that the UAV is placed at the point where the angle
of elevation calculated based on its geographical location should satisfy
$PLos_{n}^{l}\left(\theta_{n}^{l}\right)\geq\phi$. Because the objective
function and the first constraint are both quadratic, hence (15) is a
quadratic constraint quadratic programming problem (QCQP). Lemma 1: Problem
(15) can be equivalently formulated as a following QCQP problem:

$\displaystyle\mathbb{P}_{1}^{b,1}$
$\displaystyle:\mathop{\min}_{\textbf{W}}\frac{1}{2}{{\textbf{{W}}}^{T}}{\textbf{H}_{o}}\textbf{W}+\mathbf{F}_{o}^{T}{\textbf{W}}+{\kappa_{\rm{o}}},\forall
l$ (16a)
$\displaystyle\frac{1}{2}{{\bf{W}}^{T}}{\textbf{H}_{n}}+\mathbf{F}_{n}^{T}{{\textbf{W}+}}{\kappa_{n}}\leq
0,\forall n\in{\cal{Q}}^{l}.$ (16b)

Where

$\small{\textbf{H}_{o}}=\begin{bmatrix}2Q^{l}&0&0\\\ 0&2Q^{l}&0\\\
0&0&2Q^{l}\end{bmatrix},{\textbf{H}_{n}}=\begin{bmatrix}2&0&0\\\ 0&2&0\\\
0&0&\xi\end{bmatrix}.$ (17)

${\textbf{F}_{o}}\\!\\!=\\!\\!\begin{bmatrix}-2\\!\\!\\!\sum\limits_{n\in
Q^{l}}\\!\\!\\!{x_{n}}&\\!\\!\\!\\!\\!-2\\!\\!\\!\sum\limits_{n\in
Q^{l}}\\!\\!\\!{y_{n}}&0\end{bmatrix}^{T}\\!\\!,{\textbf{F}_{n}}\\!\\!=\\!\\!\begin{bmatrix}-2x_{n}&0y_{n}&0\end{bmatrix}^{T}.$
(18) $\kappa_{o}={\sum}_{n\in Q^{l}}{x_{n}^{2}}+{\sum}_{n\in
Q^{l}}{y_{n}^{2}},\;\;\;\kappa_{n}=x_{n}^{2}+y_{n}^{2}.$ (19)

###### Proof:

See Appendix A. ∎

Solving a QCQP optimization, in general, is challenging because of its NP-hard
nature [25]. Fortunately, there is a subclass of QCQP problems in which both
the objective function and constraint are convex in nature, as demonstrated in
(17). This subclass of problems can be efficiently solved using the second-
order cone programming method [26].

By iteratively solving problems (16) and (14), the average path loss and the
user association can be optimized, whose steps are listed in Algorithm 1.

1 Initialization:  $PL_{old}$, error;

2 Execution: ;

3 while  _error $>$ $\epsilon$_ do

4 Given the random location of UAV’s Solve (14) Using Branch and Bound (BnB)
algorithm to get the User association matrix J.

5 Based upon the User Association matrix, update the location of UAV by
solving (15)

6 Compute Path Loss using using (7) to obtain $PL_{*}$

7 Compute error = $|PL_{*}$-$PL_{old}|$

8 Update $PL_{old}$=$PL_{old}-PL_{*}$

9 end while

Algorithm 1 Iterative Algorithm to solve (14) and (16)

####  III-A3 Convergence and Complexity Analysis of Algorithm 1

##### Convergence Analysis

$\small\mathbb{F}(\textbf{W}^{t+1})\leq\mathbb{F}(\textbf{W}^{t}),\;\;\mathbb{F}(\textbf{J}^{t+1})\leq\mathbb{F}(\textbf{J}^{t}).$
(20)

Equation (20) perceives that the objective function values of (14) and (16)
decrease as with the iterations; as a result path loss $PL(\mathbf{W,J})$
starts decreasing and converges to a finite value when the difference between
the current and previous iteration is less than epsilon $\epsilon$, i.e.,
$PL^{t}-PL^{t-1}\leq\epsilon$.

##### Complexity Analysis

This section provides the per iteration worst-case complexity analysis of
Algorithm 1 that solves (14) and (16) iteratively. Since the (14) is the least
square minimization problem and convex in nature, it can be solved efficiently
using integer programming. More specifically, a convex problem (14) involves
${NL}$ decision variables and $2{NL}+2{L}+2{L}+1$ constraints. Because of
this, we can express $\left(NL\right)^{3}\left(2{NL}+2{L}+2{L}+1\right)$ as
the complexity required to solve (14) in each iteration. On the other hand, in
optimization problem (16), compromise of $3Q^{l}$ decision variables and
$Q^{l}+7L$ constraints. Likewise, to solve (16), the required per-iteration
complexity is $\left(3Q^{l}\right)^{0.5}\left(Q^{l}+7L\right)$. Furthermore,
assuming that $t_{m}$ are a total number of iterations, the total complexity
of Algorithm 1 is
$\mathcal{O}\left(t_{m}\\!\left(\\!\left(NL\right)^{3}\\!\left(2{NL}\\!\\!+2{L}+\\!2{L}\\!+1\right)\\!+\\!\left(3Q^{l}\right)^{0.5}\\!\\!\left(Q^{l}+7L\right)\right)\\!\\!\right)$.

###  III-B Solving $\mathbb{P}_{2}$: Joint Optimization of Transmit Power and
Subcarrier Allocation

Once the UAVs’ location and the user association matrix are defined, the
second subproblem will jointly optimize the transmit power at the UAVs and the
subcarrier allocation to maximize the sum rate while guaranteeing users’ QoS.
Mathematically, the second subproblem is formulated as follows:

$\displaystyle\mathbb{P}_{2}^{a}:\;\;$ $\displaystyle\mathop{\max}_{\textbf{P,
A}}{\sum}_{n\in\mathcal{N}}{{\sum}_{l\in\mathcal{L}}R_{n}^{l}}$ (21a)
$\displaystyle{R_{n}^{l}\geq J_{n}^{l}r_{0n}},\forall
n\in\mathcal{N},l\in\mathcal{L},$ (21b)
$\displaystyle\text{\lx@cref{creftypeplural~refnum}{C5},
\lx@cref{refnum}{Power allocation}, \lx@cref{refnum}{Subcarrier 1}
and~\lx@cref{refnum}{Subcarrier 2}}.$ (21c)

where $R^{l}_{n}$ is given in (10). The problem (21) is non-convex in nature
due to $R^{l}_{n}$ in objective function and constraint (21b). To tackle this
difficulty, we introduce auxiliary variables $\eta_{n}^{l},s_{n}^{k,l},\forall
n,l$ and reformulate (21) as

$\displaystyle\mathbb{P}_{2}^{a,1}:$
$\displaystyle\;\mathop{\max}_{{\bf{A}},{\bf{P}},{\bf{\eta}},{\mathfrak{s}}}{\sum}_{n\in
N}{{\sum}_{l\in L}{\eta_{n}^{l}}}$ (22a)
$\displaystyle\begin{split}&\;{\sum}_{k\in\mathcal{K}}\log\left(\Phi_{n}^{k,l}+\delta^{2}+p_{n}^{k,l}g_{n}^{k,l}\right)\geq\frac{{\log(2)\eta_{n}^{l}}}{B}\\\
&\qquad+{\sum}_{k\in\mathcal{K}}s_{n}^{k,l},\forall
n\in\mathcal{N},l\in\mathcal{L},\end{split}$ (22b)
$\displaystyle\;\Phi_{n}^{k,l}+\delta^{2}\leq e^{s_{n}^{k,l}},\forall n,l,k,$
(22c) $\displaystyle\;\eta^{l}_{n}\geq J^{l}_{n}r_{0n},\forall
n\in\mathcal{N},l\in\mathcal{L},$ (22d)
$\displaystyle\text{\lx@cref{creftypeplural~refnum}{C5},
\lx@cref{refnum}{Power allocation}, \lx@cref{refnum}{Subcarrier 1}
and~\lx@cref{refnum}{Subcarrier 2}}.$ (22e)

where (22d) guarantee the QoS requirement, and (LABEL:T2C1) and (22c)
equivalently represent $R_{n}^{l}\geq\eta_{n}^{l}$. Solving (22) is still
challenging due to the non-convex constraint (22c). Fortunately, it has a form
of different-of-convex (DC) constraint; hence we can employ the first-order
approximation to convexify the right-hand-side of (22c), which can be
reformulated as follows:

$\displaystyle\mathbb{P}_{2}^{a,2}:$
$\displaystyle\;\mathop{\max}_{{\bf{A}},{\bf{P}},{\bf{\eta}},{\mathfrak{s}}}{\sum}_{n\in
N}{{\sum}_{l\in L}{\eta_{n}^{l}}}$ (23a)
$\displaystyle\;{\Phi_{n}^{k,l}+\delta^{2}\leq
e^{{s_{o}}_{n}^{k,l}}\left(s_{n}^{k,l}-{s_{o}}_{n}^{k,l}+1\right)}$
$\displaystyle\qquad\qquad\qquad\qquad\forall
n\in\mathcal{N},k\in\mathcal{K},l\in\mathcal{L},$ (23b)
$\displaystyle\text{\lx@cref{creftypeplural~refnum}{C5},
\lx@cref{refnum}{T2C1}, \lx@cref{refnum}{C3T2}, \lx@cref{refnum}{Power
allocation}, \lx@cref{refnum}{Subcarrier 1} and~\lx@cref{refnum}{Subcarrier
2}}.$ (23c)

where ${s_{o}}_{n}^{k,l}$ is a feasible point of constraint (23). Since the
objective is linear and all constraints are either convex or linear with
binary variables $a^{k,l}_{n}$, problem (23) can be solved by the standard
branch-and-bound method via, e.g., Mosek solver. This method, however, incurs
exponential complexity with the problem size. Therefore, we relax the binary
variables into continuous ones. In addition, a penalty function
$\Psi_{n}^{l}={\sum}_{k\in\mathcal{K}}((a_{n}^{k,l})^{2}-a_{n}^{k,l})$ is
added to the original objective function to promote the convergence. However,
since $\Psi_{n}^{l}$ is convex, it cannot be added to the objective function.
In order to accomplish this, we employ its first-order approximation, computed
as

${\Psi}_{n}^{l}={\sum}_{k\in\mathcal{K}}\left(2a_{o,n}^{k,l}a_{n}^{k,l}-(a_{o,n}^{k,l})^{2}-a_{o,n}^{k,l}\right).$
(24)

By using (24) as the approximated penalty function, a relaxed resource
allocation optimization problem with penalty parameter $\mu$ can be formulated
as follows:

$\displaystyle\mathbb{P}_{2}^{b}:$
$\displaystyle\;\mathop{\max}_{{\bf{A}},{\bf{P}},{\bf{\eta}},{\mathfrak{s}}}{\sum}_{n\in
N}{\sum}_{l\in L}\left(\eta_{n}^{l}+\mu\Psi_{n}^{l}\right)$ (25a)
$\displaystyle\;0\leq a_{n}^{k,l}\leq 1,$ (25b)
$\displaystyle\text{\lx@cref{creftypeplural~refnum}{C5},
\lx@cref{refnum}{Power allocation}, \lx@cref{refnum}{Subcarrier 1}
and~\lx@cref{refnum}{Subcarrier 2}},$ (25c)
$\displaystyle\text{\lx@cref{creftypeplural~refnum}{T2C1},
\lx@cref{refnum}{C3T2} <EMAIL_ADDRESS>
It is observed that problem (25), which is the relaxed version of (23), is
convex in nature because of the linear objective function and convex
constraints. Thus, problem (25) can be solved efficiently using standard
methods, e.g., the interior point. We note that problem (25) provides a (sub)
optimal solution to problem (23) since it satisfies all constraints of this
problem. In order to narrow the gap to the optimal solution of problem (23),
an iterative Algorithm 2, constitute a sequence of convex optimization
problems, is proposed. The key idea behind Algorithm 2 is to have better
values of feasible variables in the approximated optimization problem.

1 Initialization:  $s_{o}$, $\eta_{old}$, error;

2 Execution: ;

3 while  _error $>$ $\epsilon$_ do

4 Given the location of UAVs and user association matrix form Algorithm 1,
Solve (23) to get the optimal value of $\eta_{*}$,$a_{*}$, $p_{*}$,$s_{*}$

5 Compute error = $|\eta_{*}$-$\eta_{old}|$

6 Update $\eta_{old}$=$\eta_{*}$,$s_{o}$=$s_{*}$

7 end while

Algorithm 2 Iterative Algorithm to solve (21) TABLE I: Environment values. H-RB: High-Rise Buildings [3] Environment | Sub-Urban | Urban | Dense-Urban | H-RB
---|---|---|---|---
$\xi_{LoS}$ | 1 | 1 | 1.6 | 2.3
$\xi_{NLoS}$ | 21 | 20 | 23 | 34
$b_{1}$ | 4.88 | 9.61 | 12.08 | 27.23
$b_{2}$ | 0.43 | 0.16 | 0.11 | 0.08
TABLE II: Simulations Parameters Parameters | Values | Parameters | Values
---|---|---|---
N | 10 - 50 users | $\phi$ | 55% - 95%
K | 8 | $r_{0n}$ | 1 Mbps
B | 20MHz | $N_{o}$ | -170 dBm/Hz
$\alpha$ | 4 | $f_{c}$ | 900 MHz
$h_{min},h_{max}$ | 21m, 100m | $P^{Max}_{t}$ | 0.2W

####  III-B1 Initialization

Algorithm 2 works iteratively to find the optimal solution; for this, they
need initial values for the inner approximation of (23). Furthermore, in an
iterative algorithm, the feasibility of the solution is primarily determined
by the initialization step. The most common approach to find the initial value
for inner approximation is to solve the feasible problem, i.e., (23), without
the objective function so that the solution satisfies all of the constraints
mentioned. However, it is unattainable because of constraint (23), as directly
solving (23) also requires inner approximation, which is again an iterative
process. Therefore, to determine the feasible initial value of
$\mathfrak{s}_{o}$, we solve the left-hand side of (23) with equal power
transmission and by heuristically adjusting the sub-carrier allocation matrix
to satisfy the constraints in (2),(3) and (4). This solution’s output is
referred to as the initial value of $\mathfrak{s}$.

####  III-B2 Convergence and Complexity Analysis of Algorithm 2

##### Convergence Analysis

Denote
$\mathbf{\Pi}=\left(\textbf{A}^{*},\textbf{P}^{*},\mathbf{\eta^{*},\mathfrak{s}^{*}}\right)$
as the optimal solution to problem (23) at iteration $t$. Furthermore, the
objective functions of the original (21) and approximated (23) optimization
problem are represented by $\mathbb{F}_{1}\left(\mathbf{\Pi}\right)$ and
$\mathbb{F}_{2}\left(\mathbf{\Pi}\right)$, respectively. Because the
approximated problem’s feasible region is a subset of the original
optimization problem’s feasible region. we have
$\mathbb{F}_{1}\left(\mathbf{\Pi}\right)\geq\mathbb{F}_{2}\left(\mathbf{\Pi}\right),\forall\mathbf{\Pi}$.
Furthermore, the objective function value of 3 improves iteratively, i.e.,
$\mathbb{F}\left(\mathbf{\Pi}^{t+1}\right)\geq\mathbb{F}\left(\mathbf{\Pi}^{t}\right)$,
according to the authors in [27]. The objective function value is bounded by
transmission power and QoS constraints and will converge to a local optimal
solution. Although it does not guarantee the global optimal solution, where
the performance gap to achieve the global optimal solution is left for future
work.

##### Complexity Analysis

The complexity of Algorithm 2 is determined in this section by considering the
number of decision variables and constraints in optimization problem (23).
Since optimization problem (23) is convex, the interior-point method is
applied to find the efficient solution. Specifically, $3NKL+NL$ decision
variables and $8NKL+5NL+KL+L$ constraints in convex problem (23) results in
the per iteration complexity
$\mathcal{O}(\left(3NKL\\!+\\!NL\right)^{3}\\!\left(8NKL\\!+\\!5NL\\!+\\!KL\\!+\\!L\right))$
[28, 29]. Furthermore, assuming that $t_{m}$ are a total number of iterations,
the overall complexity of Algorithm 2 is
$\mathcal{O}\left(t_{m}\\!\left(\left(3NKL\\!+\\!NL\right)^{3}\\!\left(8NKL\\!+\\!5NL\\!+\\!KL\\!+\\!L\\!\right)\\!\right)\\!\right)$.

##  IV Results and Discussion

This section demonstrates the effectiveness of the proposed algorithm via
extensive Monte-Carlo simulations using the simulation parameter listed in
Table II. In our simulations, the $N$ users are distributed randomly across a
$1\text{Km}\times 1\text{Km}$ area. Furthermore, UAVs are deployed to provide
communication services using the OFDMA protocol. Depending on the
communication environment, Table I lists additional attenuation coefficients
for path loss $\left(\xi_{LoS},\xi_{NLoS}\right)$ and parameters
$\left(b_{1},b_{2}\right)$ related to the probability of line-of-sight
communication. Furthermore, the performance of the proposed scheme is
evaluated for different KPIs, e.g., path loss and sum rate. In addition, the
numerical results for path loss and sum rate are compared to the respective
benchmark schemes.

In the first section of the proposed framework, optimal $3$D placement and
user association were achieved by iteratively solving the (16) and (14). The
goal of path loss minimization is achieved, as described in Section III-A, by
selecting the $L$ number of active UAVs while taking into account the total
number of ground users, network average capacity and users’ QoS requirements,
e.g., constraint (11c). Furthermore, the proposed design is compared with the
following references:

  * •

K-Mean Clustering: This scheme employs the $K$-Mean clustering algorithm to
partition the $N$ number of users into $L$ clusters. The location of centroids
is regarded as the $2$D location of the UAVs.

  * •

K-Medioid Clustering: This scheme is used $K$-Medioid clustering algorithm to
cluster the N number of users into the $L$ distant set.

  * •

Mean-Shift Clustering: The Mean-Shift clustering algorithm determines the $2$D
location of UAVs using the Mean-shift algorithm, which works on the principle
of kernel density estimation function.

  * •

Random Association: In this scheme, $L$ number of UAVs are optimally deployed
using (16), while users are randomly assigned to the UAVs.

  * •

Random Deployment: In scheme, $L$ number of UAVs are distributed randomly over
an area. whereas the user are allocated to the UAVs using (14)

After determining the optimal 3D location of the UAVs and the users’
association matrix, an efficient resource allocation problem (23) is solved to
achieve the maximum sum rate that satisfies the QoS. Moreover, to demonstrate
the Proposed Scheme’s advantages for sum rate maximization, we compared the
results to the following relevant benchmark schemes:

  * •

Ref. [1]: In this scheme, optimal UAV locations and user association matrices
are calculated by solving (16) and (14), respectively, while optimal
transmission power and sub-carrier allocation is accomplished by solving (23).
Whereas the selection of active UAVs were carried out without considering the
QoS constraint of users by using the formula $L=\lceil{\frac{\lambda
N}{K}}\rceil$.

  * •

Equal Power Allocation: This scheme employs the optimal sub-carrier allocation
with an equal transmission power allocation to all users.

  * •

Random Sub-Carrier Allocation: In this scheme, sub-carriers are allocated at
random, while transmission power is allocated optimally.

  * •

Random Power: This scheme allocates sub-carriers optimally while allocating
transmission power randomly to ensure service quality for all users.

  * •

Joint Power and Bandwidth Allocation[4]: In this scheme, A2G communication is
carried out over an orthogonal frequency band to minimize inter-cell
interference, while UE’s sum rate is maximized by optimizing transmission
power, bandwidth, and the 3D location of UAV’s simultaneously.

Furthermore, we perform Monte Carlo simulations, and average results are
produced over an independent channel.

(a) Algorithm 1

(b) Algorithm 2

Figure 3: Convergence Analysis of Algorithm $1$ & Algorithm $2$ Figure 4: Time
Complexity

###  IV-A Performance Analysis.

In Fig.3, the convergence of proposed algorithms is demonstrated and compared
with different stimulation parameters. Fig.3(a) represents the convergence
graph of Algorithm 1 by considering path loss as a performance matrix. Results
reveal that as the number of iterations increases, the path loss of the
network also decreases. This trend is because UAVs update their locations and
user association matrix incrementally. As a result, the distance between UAVs
and associated users decreases, and path loss decreases as well. On the other
hand, the convergence time for various simulation parameters tends to vary. As
the number of users increases, more stimulation parameters are added to the
system, requiring more computation to find a feasible solution that minimizes
the path loss values. Based on the UAV’s optimal $3$D locations and user
association matrix solved by Algorithm 1, we solve the optimal resource
allocation optimization problem using Algorithm 2. Results in Fig. 3(b)
represent the convergence behaviour of both (23) and (25) in terms of sum rate
as a performance matrix. Results reveal that the algorithm converges to a
stable (feasible) point after some iterations.

Fig. 3(b) also confirms the effectiveness of the relaxed problem (25) compared
with the mixed binary problem (23), which is revealed via an acceptable
tolerance gap between two curves. Although having a slightly degraded
performance, the relaxed problem (25) significantly reduces the computation
time compared with the mixed binary problem (23), as shown in Fig. 4. For the
small number of users, the time required to compute (23) and (25) is small. In
contrast, the computational time required to solve the mixed binary problem
grows exponentially with the number of users compared to the relaxed version.

###  IV-B Pathloss and Sum Rate Performance

Because the system sum rate largely depends on the path loss between the UAV
and its serving users, we evaluate both path loss and sum rate as the
performance matrices of the proposed algorithms.

Fig. 5(a) represents the comparative analysis of the proposed scheme by
considering path loss as a performance metric. The outcome reveals that the
proposed scheme outperforms all other schemes. In our design, the optimal
number of UAVs are selected and placed in the $3$D cartesian coordinate system
by considering the user QoS. Likewise, users are connected only to the UAV
located at the closest distance compared to others.

Fig. 5(b) compares the sum rate of the proposed algorithm with other reference
schemes as a function of the users. Superior performance is observed by the
proposed algorithm compared with the reference solutions. Furthermore, results
reveal a fundamental trade-off between optimal resource allocation and equal
power allocation. Results demonstrate that for a small number of users, an
equal power allocation scheme performs better than the optimal power
allocation; on the other hand, as the number of users increases, the optimal
power allocation scheme starts to perform better than others. This trend is
because inter-cell interference also increases with the increment in the
number of users; as a result, the sum rate starts decreasing in an equal power
allocation scheme.

(a)

(b)

Figure 5: Comparison of proposed solution Figure 6: Impact of the probability
of line of sight on the system performance. Figure 7: Outage Probability

(a)

(b)

Figure 8: Impact of working environment on the system performance.

Similarly, in a UAV communication system, the probability of line-of-sight
$(\phi)$ communication is a significant performance-influencing parameter. In
practice, not all users have a line-of-sight communication link and have
higher path loss than others, hence their QoS compromise. Whereas in our
proposed scheme, the selection and deployment of UAVs are carried out by
taking into account the QoS requirement of each user and the probability of
line of sight, respectively. To analyze the impact, simulations are carried
out for different values of $\phi$, and $N=20$ users are sorted in ascending
order according to path loss as shown in Fig. 6. Results reveal that the sum
rate increases as the number of users increases. On the other hand, as there
are users with NLoS links, the system sum rate starts decreasing. This trend
is because more transmission power is required to satisfy these users’ QoS
requirements; hence, the sum rate decreases significantly. In the same way,
results show that a higher probability of LoS communication results in a
higher system sum rate.

To further reveal the proposed scheme’s effectiveness, numerical results are
compared with the Ref. [1], in which the number of UAVs is selected regardless
of the user QoS requirements. The results of the Ref. [1] for different $\phi$
demonstrate that at $\phi=95\%$, Ref. [1] can accommodate the number of non-
line of sight users. In contrast, for $\phi={85,75}\%$ number of non-line of
sight users are more significant as compared to $\phi=95\%$; hence UAVs do not
have enough required transmission power to accommodate them; as a result, sum
rate decrease significantly for $\phi=85\%$ and goes to zero for $\phi=75\%$
respectively. The proposed approach’s significance in comparison to the
theoretical minimum approach can be seen more explicitly by considering outage
probability as a performance metric across varying spectral efficiency, as
shown in Fig. 7. The findings demonstrate the effectiveness of the proposed
approach in comparison to others.

Similarly, simulations were carried out to further analyze the performance for
path loss and sum rate problems in suburban, urban, dense-urban, and high-
raised building environments. Results in Fig. 8(a) demonstrate that the sub-
urban environment constitutes minimal path loss. On the other hand, as we move
toward other working environments, values of the additional coefficient for
path loss increase as given in Table I. Following that, the system’s
performance is further evaluated for the sum rate performance metric under
different environments, as shown in Fig. 8(b). Results reveal that the system
sum rate is higher for a sub-urban working environment than others because of
its minimal path loss. Similarly, Fig. 8 illustrates the working environment’s
impact on the system’s performance.

Next, the proposed scheme performance is further validated by taking into
account the UAV-UE connectivity and individual sum rate of different UAVs for
$N$$=$$30$ as shown in Fig. 9. In particular, Fig. 9(a) shows UAV-UE
connectivity, where the proposed scheme requires 5 UAVs to serve 30 UEs.
According to the proposed scheme, UAVs are deployed optimally at a point such
that the distance between UAVs and associated users is minimized. Moreover,
the impact of the proposed association scheme can be seen in Fig.9(b) by
plotting the sum rate of individual UAVs. It can be observed that our approach
produces a load-balanced system configuration, and there is no significant
deviation among the load of different UAVs.

(a) UAV-UE connectivity

(b) Rate per UAV

Figure 9: UAV-UE connectivity and individual UAV rate for N=30 .

##  V Conclusions and Discussions

In this work, we have considered an ODFMA-enabled multiple UAV communication
system to provide on-demand communication services in emergency scenarios. In
this context, We formulate a noval problem to maximize the sum rate via a
joint optimization of the number of active UAVs, their 3D placement, and the
radio resource allocation under a limited transmit power budget and users’ QoS
requirements. Since the original optimization problem is not convex, we first
decoupled it into sub-problems, which we then solved iteratively to find the
best feasible solution. Furthermore, the effectiveness of the proposed scheme
is illustrated via numerical results. Results demonstrate that the proposed
scheme outperforms the benchmark schemes in terms of both path loss and user
sum rate. We showed that optimal deployment and user association minimize path
loss, directly impacting the system sum rate. The results also demonstrated
that by increasing the probability of the light-of-sight channel, the path
loss decreases significantly, thereby improving the system sum rate.

The outcomes of this work suggest several promising research topics. The first
topic is to consider the user dynamic, in which the number of users is time-
varying. In such cases, the number of active UAVs should be planned jointly
with the prediction of active users. The second topic is studying the UAV
movement in the deployment design. This may reduce the number of active UAVs;
however, the problem will be more challenging.

##  Appendix A Proof of LEMMA 1

We can prove the expressions $\textbf{H}_{o}$, $\textbf{H}_{n}$,
$\textbf{F}_{o}$, $\textbf{F}_{n}$, $\kappa_{o}$ and $\kappa_{n}$ by
considering the objective function and constraints of (15), which are
represented by $f_{1}$ and $f_{2}$ respectively:

$\small
f_{1}(\mathbf{W})={\sum}_{n=1}^{{Q^{l}}}{\left[{{{\left({{x_{n}}-{x_{l}}}\right)}^{2}}+{{\left({{y_{n}}-{y_{l}}}\right)}^{2}}+h_{l}^{2}}\right],\forall
l}.$ (26) $\small
f_{2}(\mathbf{W})={\left({{x_{n}}-{x_{l}}}\right)^{2}}+{\left({{y_{n}}-{y_{l}}}\right)^{2}}+h_{l}^{2}\xi\leq\rm{0}.$
(27)

In (16), $\mathbf{H_{o}}$, and $\mathbf{H_{n}}$ represent the positive semi-
definite matrices that can be calculated by using the second partial
derivatives of $f_{1}$ and $f_{2}$, respectively. As a result, the Hessian of
$f_{1}(\mathbf{W})$ and $f_{2}(\mathbf{W})$ can be defined as follows:

$\small\mathbf{H_{o}}={\nabla^{2}}f_{1}(\mathbf{W})=\left[{\begin{array}[]{*{20}{c}}2Q^{l}&0&0\\\
0&2Q^{l}&0\\\ 0&0&2Q^{l}\end{array}}\right]=2Q^{l}\mathbf{I_{3}}.$ (28)
$\small\mathbf{H_{n}}={\nabla^{2}}f(\mathbf{W})=\left[{\begin{array}[]{*{20}{c}}2&0&0\\\
0&2&0\\\ 0&0&\xi\end{array}}\right].$ (29)

Equation (28) and (29) represents the Hessian matrix of $f_{1}$ and $f_{2}$,
whose all the elements are zeros except the diagonal elements such that
$\left|{{\nabla^{2}}(f_{1}(\mathbf{W}))}\right|>0$ and
$\left|{{\nabla^{2}}(f_{2}(\mathbf{W}))}\right|>0$. As a result, the objective
function and constraints C1 specified in (15) are convex in nature.

Following that, the transformation from (15) to (16) can be proven by simply
expanding and rearranging the quadratic terms in (26) and (27) in the
following manner:

$\displaystyle
f_{1}(\mathbf{W})\\!\\!=\\!\\!\underbrace{{\sum}_{n=1}^{Q^{l}}\\!\\!\left({x^{l}}^{2}\\!\\!\\!\\!+\\!{y^{l}}^{2}\\!\\!\\!\\!+\\!{h^{l}}^{2}\right)}_{\text{OT1}}\\!+\\!\\!\underbrace{{\sum}_{n=1}^{Q^{l}}\\!\\!\left(\\!-\\!2x_{n}{x^{l}}\\!\\!\\!-\\!2y_{n}{y^{l}}\right)}_{\text{OT2}}$
(30)
$\displaystyle\\!+\\!\underbrace{{\sum}_{n=1}^{Q^{l}}\\!\\!\left(\\!x_{n}^{2}\\!+\\!y_{n}^{2}\right)}_{\text{OT3}}.$

Similarly,

$\displaystyle
f_{2}(\mathbf{W})\\!\\!=\\!\\!\underbrace{\left({x^{l}}^{2}\\!\\!\\!\\!+\\!{y^{l}}^{2}\\!\\!\\!\\!+\\!\xi{h^{l}}^{2}\right)}_{\text{CT1}}\\!+\\!\\!\underbrace{\left(\\!-\\!2x_{n}{x^{l}}\\!\\!\\!-\\!2y_{n}{y^{l}}\right)}_{\text{CT2}}\\!+\\!\underbrace{\left(x_{n}^{2}\\!+\\!y_{n}^{2}\right)}_{\text{CT3}}.$
(31)

To prove the transformation of (15a) to (16a), we start solving (30) and find
the value of OT1, OT2 and OT3 respectively. As perceived from (30) we have

$\small\text{OT1}={\sum}_{n=1}^{Q^{l}}\\!\\!\left({x^{l}}^{2}\\!\\!\\!\\!+\\!{y^{l}}^{2}\\!\\!\\!\\!+\\!{h^{l}}^{2}\right),$
(32)

whereas ${x^{l}}^{2}\\!\\!\\!\\!+\\!{y^{l}}^{2}\\!\\!\\!\\!+\\!{h^{l}}^{2}$ in
matrix notation can be represented as follows:

$\small{x^{l}}^{2}\\!\\!\\!\\!+\\!{y^{l}}^{2}\\!\\!\\!\\!+\\!{h^{l}}^{2}=\begin{bmatrix}x^{l}\\\
y^{l}\\\ h^{l}\end{bmatrix}^{T}\begin{bmatrix}1&0&0\\\ 0&1&0\\\
0&0&1\end{bmatrix}\begin{bmatrix}x^{l}\\\ y^{l}\\\
h^{l}\end{bmatrix}=\mathbf{W}^{T}\mathbf{I_{3}}\mathbf{W},$ (33)

Putting the value of (33) in (32), we have

$\small\vspace{-2mm}\text{OT1}={\sum}_{n=1}^{Q^{l}}\mathbf{W}^{T}\mathbf{I_{3}}\mathbf{W}=\mathbf{W}^{T}Q^{l}\mathbf{I_{3}}\mathbf{W},$
(34)

Whereas, form (28), $Q^{l}\mathbf{I_{3}}=\frac{1}{2}\mathbf{H_{o}}$ and by
putting the value in (34), we have

$\small\text{OT1}=\frac{1}{2}\mathbf{W}^{T}\mathbf{H_{o}}\mathbf{W}.$ (35)

Similarly from (30), OT2 in matrix notation can be represented as follows:

$\small\text{OT2}=\\!\sum\limits_{n=1}^{Q^{l}}\\!\\!\left(\\!-\\!2x_{n}{x^{l}}\\!\\!\\!-\\!2y_{n}{y^{l}}\right)\\!=\\!\\!\underbrace{\begin{bmatrix}-2\\!\\!\sum\limits_{n=1}^{Q^{l}}\\!x_{n}\\!\\\
-2\\!\\!\sum\limits_{n=1}^{Q^{l}}\\!y_{n}\\!\\\
0\end{bmatrix}^{T}}_{\mathbf{F}_{o}}\\!\\!\\!\\!\\!\\!\begin{bmatrix}x^{l}\\\
y^{l}\\\ h^{l}\end{bmatrix}\\!=\\!\mathbf{F}_{o}^{T}\mathbf{W}.$ (36)

Similarly from (30), OT3 represented as

$\small\text{OT3}={\sum}_{n=1}^{Q^{l}}\left(x_{n}^{2}\\!+\\!y_{n}^{2}\right)=\kappa_{o}.$
(37)

Following the same procedure, we find the value of
$\text{CT1}=\frac{1}{2}\mathbf{W}^{T}\mathbf{H_{n}}\mathbf{W}$,
$\text{CT2}=\mathbf{F}_{n}\mathbf{W}$ and
$\text{CT3}=\kappa_{n}=x_{n}^{2}+y_{n}^{2}$.

Putting the value of OT1, OT2 and OT3 in (30) and CT1, CT2 and CT3 in (31) we
have
$f_{1}(\mathbf{W})=\frac{1}{2}{{\mathbf{{W}}}^{T}}{\textbf{H}_{o}}\mathbf{W}+\mathbf{F}_{o}^{T}{\textbf{W}}+{\kappa_{o}}$
and
$f_{2}(\mathbf{W})=\frac{1}{2}{{\mathbf{{W}}}^{T}}{\textbf{H}_{n}}\mathbf{W}+\mathbf{F}_{n}^{T}{\mathbf{W}}+{\kappa_{n}}$,

which completes the proof.

## References

  * [1] A. Mahmood, T. X. Vu, S. K. Sharma, S. Chatzinotas, and B. Ottersten, “Multi-objective optimization for 3d placement and resource allocation in ofdma-based multi-uav networks,” _arXiv preprint arXiv:2304.12798_ , 2023\.
  * [2] A. A. Khuwaja _et al._ , “Optimum deployment of multiple UAVs for coverage area maximization in the presence of co-channel interference,” _IEEE Access_ , vol. 7, pp. 85 203–85 212, 2019.
  * [3] R. I. Bor-Yaliniz _et al._ , “Efficient 3-D placement of an aerial base station in next generation cellular networks,” in _2016 IEEE International Conference on Communications (ICC)_ , 2016, pp. 1–5.
  * [4] P. Li and J. Xu, “Placement optimization for UAV-enabled wireless networks with multi-hop backhauls,” _Journal of Communications and Information Networks_ , vol. 3, no. 4, pp. 64–73, 2018.
  * [5] A. Masaracchia _et al._ , “An energy-efficient clustering and routing framework for disaster relief network,” _IEEE Access_ , vol. 7, pp. 56 520–56 532, 2019.
  * [6] O. Kodheli _et al._ , “Satellite communications in the new space era: A survey and future challenges,” _IEEE Communications Surveys & Tutorials_, vol. 23, no. 1, pp. 70–109, 2021.
  * [7] E. Kalantari _et al._ , “On the number and 3D placement of drone base stations in wireless cellular networks,” in _2016 IEEE 84th Vehicular Technology Conference (VTC-Fall)_ , 2016, pp. 1–6.
  * [8] Y. Zeng _et al._ , “Accessing from the sky: A tutorial on UAV communications for 5G and beyond,” _Proceedings of the IEEE_ , vol. 107, no. 12, pp. 2327–2375, 2019.
  * [9] M. Mozaffari _et al._ , “A tutorial on UAVs for wireless networks: Applications, challenges, and open problems,” _IEEE Communications Surveys Tutorials_ , vol. 21, no. 3, pp. 2334–2360, 2019.
  * [10] M. Mozaffari _et al._ , “Drone small cells in the clouds: Design, deployment and performance analysis,” in _2015 IEEE Global Communications Conference (GLOBECOM)_ , 2015, pp. 1–6.
  * [11] Y. Liang _et al._ , “Joint trajectory and resource optimization for UAV-aided two-way relay networks,” _IEEE Transactions on Vehicular Technology_ , vol. 71, no. 1, pp. 639–652, 2022.
  * [12] L. Xie, J. Xu, and R. Zhang, “Throughput maximization for UAV-enabled wireless powered communication networks,” _IEEE Internet of Things Journal_ , vol. 6, no. 2, pp. 1690–1703, 2019.
  * [13] G. Zhang, Q. Wu, M. Cui, and R. Zhang, “Securing UAV communications via joint trajectory and power control,” _IEEE Transactions on Wireless Communications_ , vol. 18, no. 2, pp. 1376–1389, 2019.
  * [14] S. Zeng _et al._ , “Trajectory optimization and resource allocation for ofdma UAV relay networks,” _IEEE Transactions on Wireless Communications_ , vol. 20, no. 10, pp. 6634–6647, 2021.
  * [15] M. Alzenad _et al._ , “3-D placement of an unmanned aerial vehicle base station (UAV-bs) for energy-efficient maximal coverage,” _IEEE Wireless Comm. Letters_ , vol. 6, pp. 434–437, 2017.
  * [16] C. You and R. Zhang, “3D trajectory optimization in rician fading for UAV-enabled data harvesting,” _IEEE Transactions on Wireless Communications_ , vol. 18, no. 6, pp. 3192–3207, 2019.
  * [17] F. Huang _et al._ , “Multiple-UAV-assisted swipt in internet of things: User association and power allocation,” _IEEE Access_ , vol. 7, pp. 124 244–124 255, 2019.
  * [18] L. Xie _et al._ , “Common throughput maximization for UAV-enabled interference channel with wireless powered communications,” _IEEE Transactions on Communications_ , vol. 68, no. 5, pp. 3197–3212, 2020.
  * [19] Z. Rahimi _et al._ , “An efficient 3-D positioning approach to minimize required UAVs for iot network coverage,” _IEEE Internet of Things Journal_ , vol. 9, no. 1, pp. 558–571, 2022.
  * [20] R. Chen, X. Li, Y. Sun, S. Li, and Z. Sun, “Multi-UAV coverage scheme for average capacity maximization,” _IEEE Communications Letters_ , vol. 24, no. 3, pp. 653–657, 2020.
  * [21] J. G. Andrews _et al._ , “What will 5G be?” _IEEE Journal on Selected Areas in Comm_ , vol. 32, no. 6, pp. 1065–1082, 2014.
  * [22] X. Liu _et al._ , “Trajectory design and power control for multi-UAV assisted wireless networks: A machine learning approach,” _IEEE Tran. on Vehicular Technology_ , vol. 68, pp. 7957–7969, 2019.
  * [23] H. El Hammouti, M. Benjillali, B. Shihada, and M.-S. Alouini, “Learn-as-you-fly: A distributed algorithm for joint 3D placement and user association in multi-uavs networks,” _IEEE Transactions on Wireless Communications_ , vol. 18, no. 12, pp. 5831–5844, 2019.
  * [24] A. Al-Hourani _et al._ , “Modeling air-to-ground path loss for low altitude platforms in urban environments,” in _2014 IEEE Global Communications Conference_ , 2014, pp. 2898–2904.
  * [25] C. Lu, S.-C. Fang, Q. Jin, Z. Wang, and W. Xing, “KKT solution and conic relaxation for solving quadratically constrained quadratic programming problems,” _SIAM Journal on Optimization_ , vol. 21, no. 4, pp. 1475–1490, 2011.
  * [26] M. S. Lobo, L. Vandenberghe, S. Boyd, and H. Lebret, “Applications of second-order cone programming,” _Linear algebra and its applications_ , vol. 284, no. 1-3, pp. 193–228, 1998.
  * [27] A. Beck _et al._ , “A sequential parametric convex approximation method with applications to nonconvex truss topology design problems,” _Journal of Global Optimization_ , vol. 47, no. 1, pp. 29–51, 2010.
  * [28] T. S. Abdu _et al._ , “Flexible resource optimization for GEO multibeam satellite communication system,” _IEEE Transactions on Wireless Communications_ , vol. 20, no. 12, pp. 7888–7902, 2021.
  * [29] T. X. Vu _et al._ , “Dynamic bandwidth allocation and precoding design for highly-loaded multiuser MISO in beyond 5G networks,” _IEEE Transactions on Wireless Communications_ , vol. 21, no. 3, pp. 1794–1805, 2022.