# Energy Efficient D2D Communications Using Multiple UAV Relays

Ahmad Alsharoa${}^{\text{1}}$ and Murat Yuksel${}^{\text{2}}$

${}^{\text{1}}$Missouri University of Science and Technology (MST), Rolla,
Missouri, USA. Email<EMAIL_ADDRESS>${}^{\text{2}}$University of Central
Florida (UCF), Orlando, Florida, USA. Email<EMAIL_ADDRESS>
###### Abstract

In this paper, we propose a novel optimization model for multiple Unmanned
Areal Vehicles (UAVs) working as relays and helping Device-to-Device (D2D)
communications at the same time. The goal of the UAVs is to operate in an
energy-efficient manner while not only optimizing the available bandwidth and
power allocations of the D2D links, but also act as relays when needed to
maintain the communication between ground users. We formulate an optimization
problem that maximizes the energy-efficient utility while respecting the
resource availability including the UAVs’ energy consumption, UAV-user
association, and trajectory constraints. Due to the non-convexity of the
problem, we propose to solve it in three steps using Taylor series
approximation to optimize the power and the bandwidth, and use a heuristic
algorithm for optimizing the UAVs’ trajectory and UAV-user associations.

##  I Introduction

Recently, Device-to-Device (D2D) communication has been considered an
innovative feature of next-generation cellular networks. It facilitates
interoperability between close proximity wireless users using direct link and
with minimal help from network infrastructures. More specifically, direct
communication between nearby users enhances the spectrum utilization, overall
throughput and data transfer rate, energy efficiency, and latency while
enabling new peer-to-peer and location-based applications and services [1].

D2D communication becomes more challenging if a dynamic environment is
considered. When infrastructure support does not exist (e.g., during or after
a disaster), LTE-Direct will not be available [2]. UAVs can practically serve
as base stations to organize and optimize communications among a swarm of
devices while also acting as a relay to extend the devices’ communication
range. In [3], a dynamic protocol was proposed to enable inter-cell D2D
communication using a relay device. The performance of the dynamic environment
can be significantly improved by using UAVs to organize the D2D resources in
the network and help in maintaining the communication links between out-of-
range devices by working as a mobile relay.

As another dimension, optimizing the trajectories of UAVs supporting D2D
communications among ground users can significantly enhance the network
performance by determining the best coverage areas for the D2D links, and
thus, optimize the resources. Few works in the literature discuss the
trajectory optimization of the UAVs in this context. For instance, in [4],
Selim et. al propose a novel trajectory optimization approach under a self-
healing management framework, where multiple UAVs need to optimize their
trajectories to heal the devices associated to a failed base station. The UAV
trajectory optimization using sequential convex optimization technique has
been studied in [5] for a point-to-point system model using only one UAV. In
[6], the authors solve a one-dimensional placement problem and consider one
UAV serving multiple ground users in a time sharing manner. This work
simplifies the complexity of the optimization problem but limits applicability
in practice. The work in [7] proposed an energy efficiency management
framework that optimizes the 3D trajectory of a UAV under cognitive radio
system, where the authors proposed to optimize the 3D trajectory after
minimizing the UAVs’ energy consumption.

Coexistence between one UAV and underlaid D2D communication received notable
attention. A downlink scenario is studied in [8], where the UAV can serve only
one device at a time and needs to travel from one stop point to another to
serve other devices. The UAV does not manage or organize the D2D links, and
considers it as interference to the UAV device. However, this approach limits
the practicality of using a UAV as a base station and may consume a large
amount of energy by forcing the UAV to travel from one point to another. In
[9], we proposed for the first time an approach, called UAV-Direct, consisting
of one UAV managing the resources of the D2D users. However, this approach
does not take the energy efficiency and UAVs’ battery level into
consideration. Furthermore, it is only limited to one UAV. The problem becomes
more challenging when energy efficiency and multiple UAVs are considered
serving multiple D2D users. Our proposed work in this paper considers multiple
UAVs and their charging needs to serve D2D communications on the ground. This
will firstly change the objective function and the goal of the problem and add
more constraints in the resource allocation and trajectory optimization.

In this paper, we propose a new and novel energy-efficient framework where
multiple UAVs optimize the power and bandwidth allocations for D2D users and
work as relays when needed to maintain the communication links between users
within or outside of communication range of each others. Thanks to their
mobility, the UAVs are more robust against environmental changes and their
trajectories can be optimized based on devices’ dynamic locations. To the best
of our knowledge, energy-efficient optimization of trajectories for multiple
UAVs that organize D2D communications is reported for the first time in this
paper.

##  II System Model

We consider a wireless system composed with $L$ UAVs, mobile user pairs
$u=1,..,U$ aiming to exchange data between each other using a direct D2D
communication link (i.e., D2D users) or via one of the UAVs (i.e., relay
users), and one UAV charging station located at the middle as shown in Fig. 1.
We denote $N$ and $M$ as the total pairs of users that communicate using
direct D2D links and UAV relay links, respectively. We assume that the UAVs
manage the resource allocations for both D2D and relay links.

We consider a 3D coordinate system where the coordinate of user $u$ and UAV
$l$ at time instant $\zeta$ are given, respectively, as
$\mathbb{W}_{u}(\zeta)=[x_{u}(\zeta),y_{u}(\zeta),0]^{t}$ and
$\mathbb{J}_{l}(\zeta)=[x_{l}(\zeta),y_{l}(\zeta),z_{l}(\zeta)]^{t}$, where
$[.]^{t}$ denotes the transpose operator. We assume that the time duration for
the optimization $T$ is discretized into $t=1,..,\tilde{T}$ equal time slots
such that $T=\tilde{T}\tau$, where $\tau$ is small enough that the movements
of the users and the UAVs are negligible from our optimization problem’s point
of view. Note that the choice of $\tau$ depends on the mobility of the UAVs
and users. Without loss of generality, we assume that all UAVs cannot exceed
their maximum speed denoted by $\bar{V}$. Therefore, the following trajectory
constraints should be satisfied

$||\mathbb{J}_{l}[t+1]-\mathbb{J}_{l}[t]||^{2}\leq\bar{V}\tau,\forall
l=1,.,L,t=1,.,\tilde{T},$ (1)

where $\bar{V}\tau$ is the maximum distances that the UAV $l$ can travel
during each time slot $t$. For simplicity, We assume that the total bandwidth
$B$ is divided into two main fractions: $B^{d}$ for the D2D links and $B^{r}$
for the relay links. Further, we assume that all D2D links use $B^{d}$ at the
same time while $B^{r}$ is divided to non-overlapping subfractions $B^{r}_{m}$
such that $\sum_{m=1}^{M}B^{r}_{m}=B^{r}$, where $B^{r}_{m}$ is the
subfractional bandwidth assigned to the relay link $m$. This is considered a
plausible assumption since the transmit power used of D2D users111We will
sometimes refer to the set of direct D2D links in the system as ‘D2D users’,
which means the pairs of users communicating directly via D2D link. is much
less than the transmit power of the relay users222We will sometimes refer to
the set of relay D2D links in the system as ‘relay users’, which means the
pairs of users communicating via a UAV. due to the fact that the shadowing and
fading for short range communications have much less effect on the channel
gain compared to the large scale range of the relay links. Hence, using the
same bandwidth for D2D users will not cause a large interference compared to
relay users.

Figure 1: System Model.

For relay user $m$, a binary variable $\epsilon^{r}_{lm}[t]$ is introduced,
where it is equal to 1 if the relay user $m$ associated with UAV $l$ for the
relay link at time $t$. We assume that each relay user can be associated with
at most one UAV during time slot $t$, on the other hand, each UAV can
associate to multiple users. Thus, the following constraint should be
respected: $\sum_{l=1}^{L}\epsilon^{r}_{lm}[t]\leq 1,\forall m,t.$

###  II-A Channel Model

As discussed in [8] and [10], the ground and air receivers can receive two
types of signals in addition to the Line-of-Sight (LOS) signal. The first one
is strong reflected Non Line-of-Sight (NLoS) signal and the second one is
multiple reflected signal type that causes fading. As shown in [10], these
types can be considered separately with different Probability of Occurrence
(PoO). In this case, there will be a probability to obtain a LoS link between
the UAV and users in the relay link. The Path Loss (PL) between the UAV $l$
positioned at a position $\mathbb{J}_{0}$ and a ground user $m$ in urban
environments for LoS and NLoS is given, respectively as [10]:

$PL^{\text{LoS}}_{ml}[t]=\xi_{\text{LoS}}\left(\frac{4\pi\delta_{ml}[t]}{\lambda_{0}}\right),PL^{\text{NLoS}}_{ml}[t]=\xi_{\text{NLoS}}\left(\frac{4\pi\delta_{ml}[t]}{\lambda_{0}}\right),$
(2)

where $\delta_{ml}[t]=||\mathbb{J}_{l}-\mathbb{W}_{m}||$ is the distance
between UAV $l$ and relay user $m$. $\lambda_{0}$ is the wavelength of the
radio signal. $\xi_{\text{LoS}}$ and $\xi_{\text{NLoS}}$ are the additional
loss to the free space propagation for LoS and NLoS links, respectively, due
to the shadowing effect and the reflection of signals from obstacles. The LoS
probability is given by [11],
$p^{\text{LoS}}_{ml}[t]=1/(1+\nu_{1}\exp(-\nu_{2}[\theta_{ml}[t]-\nu_{1}])),$
where
$\theta_{ml}[t]=\frac{180}{\pi}\sin^{-1}\left(\frac{z_{l}[t]}{\delta_{ml}[t]}\right)$
is the elevation angle between the UAV and the user $m$ in degree. $\nu_{1}$
and $\nu_{2}$ are constant values that depend on the environment. The NLoS
probability is, then, equal to $1-p^{\text{LoS}}_{ml}[t]$. Using this PL
model, the average PL for ground-to-air link is given by,
$\text{PL}_{ml}[t]=p^{\text{LoS}}_{ml}[t]PL^{\text{LoS}}_{ml}[t]+(1-p^{\text{LoS}}_{ml}[t])PL^{\text{NLoS}}_{ml}[t].$
Therefore, the channel gain between user $m$ and the UAV in the relay link is
given as $h^{r}_{ml}[t]=1/\text{PL}_{ml}[t].$

###  II-B UAV Power Model

We consider both the transmission and operation power modes of the UAVs. For
the transmission power level, each UAV can be either in an active mode if it
is in communication with one of the users or in an idle mode otherwise. For
simplicity, the total transmit power consumption of UAV $l$ during a time slot
$t$ to serve the associated relay users can be approximated by a linear model
as [12],
$P^{r}_{l}[t]=\alpha_{l}\sum_{m=1}^{M}\epsilon^{r}_{lm}[t]P^{r}_{l\acute{m}}[t]+\beta_{l},$
where $\alpha_{l}$ corresponds to the power consumption that scales with the
radiated power due to amplifier and feeder losses and $\beta_{l}$ models an
offset of site power which is consumed independently of the average transmit
power. $P^{r}_{l\acute{m}}[t]$ is the transmit power of UAV $l$ during time
slot $t$ to forward the data from relay user $m$ to user $\acute{m}$. Besides
the power consumed for the transmission, the UAV consumes additional power for
hovering and hardware, denoted by $P^{f}_{l}[t]$, and can be expressed as [13]
$P^{f}_{l}[t]=\sqrt{\frac{(m_{\text{tot}}g)^{3}}{2\pi
r_{p}^{2}\omega_{p}\rho}}+\frac{P_{\text{full}}-P^{s}}{\bar{V}}V_{l}[t]+P^{s},$
where $m_{\text{tot}}$, $g$, and $\rho$ are the UAV mass in Kg, earth gravity
in m$/\text{s}^{2}$, and air density in $\text{Kg}/\text{m}^{3}$,
respectively. The parameter $r_{p}$ and $\omega_{p}$ are the radius and the
number of the UAV’s propellers, respectively. $P_{\text{full}}$ and $P^{s}$
are extra hardware power consumptions when the UAV is moving at full speed and
when it stops in a static position (i.e., $V_{l}[t]=0$), respectively. Thus,
the total power consumption of UAV $l$ during time slot $t$ is given by
$P_{l}[t]=P^{r}_{l}[t]+P^{f}_{l}[t].$

###  II-C Rate Calculation

The transmission rate from relay user $m$ to the UAV in the relay link can be
expressed as

$R^{r}_{ml}[t]=B^{r}_{m}[t]\log_{2}\left(1+\frac{P^{r}_{ml}[t]h^{r}_{ml}[t]}{B^{r}_{m}[t]N_{0}}\right),$
(3)

where $B^{r}_{m}[t]$ is the transmission bandwidth allocated to relay user $m$
in the relay link during time slot $t$, and $N_{0}$ is the noise power.
$P^{r}_{ml}[t]$ is the transmit power of relay user $m$ to UAV $l$ during time
slot $t$. For simplicity and to make the problem more tractable, we assume
that all relay users access the spectrum sparsely (allocate different
bandwidth to different user, thus, no interference between users).

Similarly, the transmission rate from UAV $l$ to user $\acute{m}$ (the paired
user) can be expressed as

$R^{r}_{l\acute{m}}[t]=B^{r}_{m}[t]\log_{2}\left(1+\frac{P^{r}_{l\acute{m}}[t]h^{r}_{l\acute{m}}[t]}{B^{r}_{\acute{m}}[t]N_{0}}\right).$
(4)

Therefore, the end-to-end maximum transmission rate at the destination (i.e.,
$\acute{m}$) using decode-and-forward (DF) approach where the UAVs decode the
signals first before broadcasting it to the destination can be expressed
as[14] $R^{r}_{m}[t]=1/2\min\left(R^{r}_{ml}[t],R^{r}_{l\acute{m}}[t]\right).$

The transmission rate from user $n$ to the paired user $\acute{n}$ in the D2D
link can be expressed as

$R^{d}_{n}[t]=B^{d}\log_{2}\left(1+\frac{P^{d}_{n\acute{n}}[t]h^{d}_{n\acute{n}}[t]}{\sum_{\begin{subarray}{c}k=1,k\neq
n\end{subarray}}^{N}P^{d}_{k\acute{k}}[t]h^{d}_{k\acute{n}}[t]+B^{d}N_{0}}\right),$
(5)

where $\sum_{\begin{subarray}{c}k=1\\\ k\neq
n\end{subarray}}^{N}P^{d}_{k\acute{k}}[t]h^{d}_{k\acute{n}}[t]$ is the
interference power signal from other D2D users.

##  III Problem Formulation

In this section, we formulate our optimization problems aiming to maximize the
energy efficiency of the system respecting the UAVs’ battery levels. In
general, the total energy consumption of UAV $l$ during time slot $t$ can be
expressed as

$E^{c}_{l}[t]=\tau\frac{||\mathbb{J}_{l}[t]-\mathbb{J}_{0}||^{2}}{||\mathbb{J}_{l}[t]-\mathbb{J}_{0}||^{2}+\tilde{J}}\left(P^{f}_{l}[t]+P^{r}_{l}[t]\right)$
(6)

where $\mathbb{J}_{0}$ and $\tilde{J}$ are the location of the charging
station and a very small number, respectively. In (6), the ratio
$||\mathbb{J}_{l}[t]-\mathbb{J}_{0}||^{2}/(||\mathbb{J}_{l}[t]-\mathbb{J}_{0}||^{2}+\tilde{J})$
is to ensure that the UAVs will not consume energy when located at the
charging station. So it is 0 when UAV $l$ is in the charging station and very
close to 1 otherwise. On the other hand, we assume that UAV $l$ can be charged
with a fix amount of power equal to $P^{ch}$ for each time instant when it is
plugged to the charging station. Therefore, the total charging energy of UAV
$l$ during time slot $t$ can be expressed as

$E^{ch}_{l}[t]=\tau\left(1-\frac{||\mathbb{J}_{l}[t]-\mathbb{J}_{0}||^{2}}{||\mathbb{J}_{l}[t]-\mathbb{J}_{0}||^{2}+\tilde{J}}\right)P^{ch}.$
(7)

We assume that the UAVs are battery-powered devices. Therefore, the stored
energy by UAV $l$ at the end of time slot $t$, denoted by $S_{l}[t]$, is given
by $S_{l}[t]=S_{l}[t-1]+E^{ch}_{l}[t]-E^{c}_{l}[t].$ We assume that,
initially, each battery is charged by an amount of energy denoted by
$S^{0}_{l}$. In the sequel, we aim to maximize the energy efficiency utility
of the system by optimizing the followings parameters: 1) transmit power
levels of the users and UAVs, 2) bandwidth allocation to each user, 3)
association between UAVs and users, and 4) trajectory of the UAVs. Therefore,
the optimization problem can be formulated as follows

$\displaystyle\underset{\begin{subarray}{c}B^{d}[t],B^{r}_{m}[t],\mathbb{J}_{l}[t],\epsilon^{r}_{lm}[t]\\\
P^{r}_{ml}[t],P^{r}_{l\acute{m}}[t],P^{d}_{n\acute{n}}[t]\end{subarray}}{\text{maximize}}\quad\mathcal{U}(R^{d}_{n}[t],R^{d}_{m}[t])$
(8) subject to: $\displaystyle 0\leq
P^{d}_{n\acute{n}}[t]\leq\bar{P}_{u},\quad\forall n\quad\forall t,$ (9)
$\displaystyle 0\leq P^{r}_{ml}[t]\leq\bar{P}_{u},\quad\forall m\quad\forall
t,$ (10)
$\displaystyle\sum\limits_{m=1}^{M}\epsilon^{r}_{lm}[t]P^{r}_{l\acute{m}}[t]\leq\bar{P}_{l},\quad\forall
l,\forall t,$ (11) $\displaystyle
B^{d}[t]+\sum\limits_{m=1}^{M}\sum\limits_{l=1}^{L}\epsilon^{r}_{lm}[t]B^{r}_{m}[t]\leq\bar{B},\quad\forall
m,\forall t,$ (12)
$\displaystyle\frac{||\mathbb{J}_{l}[t]-\mathbb{J}_{l}[0]||^{2}}{\bar{V}}P^{f}_{l}[t]|_{V_{l}=\bar{V}}+E^{c}_{l}[t]\leq
S_{l}[t-1],\quad\forall l,\forall t,$ (13) $\displaystyle
S_{l}[t-1]+E^{ch}_{l}[t]\leq\bar{S},\quad\forall l,\forall t,$ (14)
$\displaystyle||\mathbb{J}_{l}[t+1]-\mathbb{J}_{l}[t]||^{2}\leq
V_{l}\tau,\quad\forall l,\forall n,$ (15)
$\displaystyle\sum\limits_{l=1}^{L}\epsilon^{r}_{lm}[t]\leq 1,\quad\forall
m,\forall t$ (16)

where $\mathcal{U}(R^{d}_{n}[t],R^{d}_{m}[t])$ denotes the energy efficiency
utility of all users. Constraints (9), (10), and (11) represent the peak power
constraints at D2D users, relay users, and UAVs, respectively. Constraint (12)
is to ensure the system bandwidth limitation. Constraint (13) is also
equivalent to
$\sum_{\iota=1}^{t}E^{c}_{l}[\iota]-\sum_{\iota=1}^{t-1}E^{ch}_{l}[\iota]\leq
S^{0}_{l}$, where the consumed energy is less than the stored energy in the
previous time slot. In constraint (13), we assume that the UAVs’ return speed
to the charging station is $\bar{V}$. Thus, the term
$\frac{||\mathbb{J}_{l}[t]-\mathbb{J}_{l}[0]||^{2}}{\bar{V}}P^{f}_{l}[t]|_{V_{l}=\bar{V}}$
is added to ensure that the UAV has enough battery to return to the charging
station when needed. Constraint (14) is equivalent to
$S^{0}_{l}+\sum_{\iota=1}^{t}E^{ch}_{l}[\iota]-\sum_{\iota=1}^{t-1}E^{c}_{l}[\iota]\leq\bar{S}$,
where the charging energy that added to previous stored energy shouldn’t
exceed the UAV battery capacity (i.e., maximum stored energy $\bar{S}$).
Constraint (15) indicates the trajectory constraint as explained in Section
II.

In this work, we select to use Max-Min utility. The Max-Min utilities are a
family of utility functions attempting to maximize the minimum data rate in
the network [15]. By increasing the priority of users having lower rates, Max-
Min utilities lead to more fairness in the network. In order to simplify the
problem for this approach, we define a new decision variable
$R_{\min}[t]=\underset{m,n}{\min}(R^{d}_{n}[t],R^{d}_{m}[t])$. Therefore, our
optimization problem becomes:

$\underset{\begin{subarray}{c}B^{d}[t],B^{r}_{m}[t],\mathbb{J}_{l}[t],\epsilon^{r}_{lm}[t]\\\
P^{r}_{ml}[t],P^{r}_{l\acute{m}}[t],P^{d}_{n\acute{n}}[t]\end{subarray}}{\text{maximize}}\quad\frac{R_{\min}[t]}{\sum\limits_{n=1}^{N}E^{d}_{n}[t]+\sum\limits_{m=1}^{M}E^{r}_{ml}[t]+\sum\limits_{l=1}^{L}E^{c}_{l}[t]}\vspace{-2cm}$
(17)

subject to:

$\displaystyle\frac{1}{2}R^{r}_{l\acute{m}}[t]\geq R_{\min}[t]\quad\forall
m,\forall l,\forall t$ (18) $\displaystyle\frac{1}{2}R^{r}_{ml}[t]\geq
R_{\min}[t]\quad\forall m,\forall l,\forall t,$ (19) $\displaystyle
R^{d}_{n}[t]\geq R_{\min}[t]\quad\forall n,\forall t,$ (20)
$\displaystyle\eqref{powern},\eqref{powerm},\eqref{power_r},\eqref{BW},\eqref{power_rbattery},\eqref{tra1},\eqref{Asso},$
(21)

where $E^{d}_{n}[t]=\tau P^{d}_{n\acute{n}}[t]$ and $E^{r}_{ml}[t]=\tau
P^{r}_{ml}[t]$.

##  IV Proposed Solution

The formulated optimization problem is a non-convex problem due to constraints
(17)-(21). We propose to solve it in three iterative steps. At the beginning,
we firstly optimize the power allocations by assuming fixed bandwidths,
associations, and UAV trajectories. In this step, we approximate the solution
by converting our formulated problem to a convex one. We secondly optimize the
bandwidth allocations for both D2D and relays users with a similar
approximation technique. Finally, we employ a recursive heuristic search
algorithm to optimize the UAV trajectories and UAV-user associations together.
These steps are repeated until convergence.

###  IV-A Transmit Power Allocations

For fixed bandwidth allocations and UAV trajectories, the optimization problem
can be given as

$\displaystyle\textbf{(\text{P1}):}\underset{\begin{subarray}{c}P^{r}_{l,m}[t],P^{r}_{l\acute{m}}[t],\\\
P^{d}_{n\acute{n}}[t],R_{\min}[t]\end{subarray}}{\text{maximize}}\quad\mathcal{U}(R_{\min}[t])$
$\displaystyle\text{subject to:}\eqref{min1}-\eqref{other_constraint}.$ (22)

This problem is quasi-concave (i.e., 1/(objective function) is quasi-convex)
except constraint (20) since its objective function,
$\mathcal{U}(R_{\min}[t])$, is a fraction of a concave function and a linear
function and the other constraints are convex. Hence, the goal is to convert
constraint (20) into a convex one in order to solve the problem efficiently.
This constraint is neither concave nor convex with respect to
$P^{d}_{n\acute{n}}$. We can expand the left hand side of constraint (20) as
follows:

$\displaystyle R^{d}_{n}[t]=$
$\displaystyle\underbrace{B^{d}[t]\log_{2}\left(B^{d}[t]N_{0}+\sum\limits_{k=1}^{N}P^{d}_{k\acute{k}}[t]h^{d}_{k\acute{n}}[t]\right)}_{\tilde{R}^{d}_{n,1}[t]}$
(23)
$\displaystyle\underbrace{-B^{d}[t]\log_{2}\left(\sum\limits_{\begin{subarray}{c}k=1\\\
k\neq
n\end{subarray}}^{N}P^{d}_{k\acute{k}}[t]h^{d}_{k\acute{n}}[t]+B^{d}[t]N_{0}\right).}_{\tilde{R}^{d}_{n,2}[t]}$

Now, the main goal is to convert (23) to a concave form in order for P1 to
become convex. Note that $\tilde{R}^{d}_{n,1}[t]$ is concave, because the
$\log$ of an affine function is concave [16]. Also, $\tilde{R}^{d}_{n,2}[t]$
is a convex function, and thus, it needs to be converted to a concave
function. To tackle the non-concavity of $\tilde{R}^{d}_{n,2}[t]$, the
Successive Convex Approximation (SCA) technique can be applied where in each
iteration, the original function is approximated by a more tractable function
at a given local point. Recall that $\tilde{R}^{d}_{n,2}[t]$ is convex in
$P^{d}_{n\acute{n}}[t]$, and any convex function can be globally lower-bounded
by its first order Taylor expansion at any point. Therefore, given
$P^{d}_{n\acute{n}}(r)[t]$ in iteration $r$, we obtain the following lower
bound for $\tilde{R}^{d}_{n,2}(r)[t]$:

$\displaystyle\tilde{R}^{d}_{n,2}(r)[t]\geq$
$\displaystyle-B^{d}[t]\log_{2}\left(\psi(r)[t]\right)$
$\displaystyle-\frac{h^{d}_{k\acute{n}}[t]}{\ln(2)\psi(r)[t]}(P^{d}_{k\acute{k}}[t]-P^{d}_{k\acute{k}}(r)[t])$
(24)

where $\psi(r)[t]=\sum_{\begin{subarray}{c}k=1,k\neq
n\end{subarray}}^{N}P^{d}_{k\acute{k}}(r)[t]h^{d}_{k\acute{n}}[t]+B^{d}[t]N_{0}$.

At this stage, P1 is a quasi-convex optimization. Hence, its solution is
equivalent to finding the root of the scalar function
$\mathcal{U}(R_{\min}[t])=1/\mathcal{F}(\kappa)$, which can be solved using
the bisection method. Here, $\mathcal{F}(\kappa)$ is a convex, continuous, and
strictly decreasing function with respect to $\kappa$, and is defined as
$\mathcal{F}(\kappa)=\min\left(\mathcal{N}-\kappa\mathcal{D}\right)$, where
$\mathcal{N}$ and $\mathcal{D}$ represent the nominator and denominator of
$\mathcal{F}(\kappa)$, respectively. The last step to solve P1 is to apply SCA
to find the best approximation of constraint (IV-A).

###  IV-B Bandwidth Allocations

For given power allocations, association, and UAV trajectories, the problem
for optimizing the bandwidth allocations can be given as

$\textbf{(\text{P2}):}\underset{\begin{subarray}{c}B^{d}[t],B^{r}_{m}[t],R_{\min}[t]\end{subarray}}{\text{maximize}}\quad\mathcal{U}(R_{\min}[t])\vspace{-3mm}$
(25)

subject to: (18)-(21).

The objective function (25) is quasi-convex and all constraints of P2 are
convex functions except (18)-(20). These constraints are neither concave nor
convex with respect to the bandwidth allocations. In the sequel, we
approximate constraint (20) to a convex function. The same approximation
approach can be applied for the other two constraints, i.e., (18) and (19).
333We omit the details of these approximations due to space limitations. The
left hand side of (20) can be expanded as follows

$\displaystyle R^{d}_{n}[t]=$
$\displaystyle\underbrace{B^{d}[t]\log_{2}\left(B^{d}[t]N_{0}+\sum\limits_{k=1}^{N}P^{d}_{k\acute{k}}[t]h^{d}_{k\acute{n}}[t]\right)}_{\tilde{R}^{d}_{n,1}[t]}$
(26)
$\displaystyle\underbrace{-B^{d}[t]\log_{2}\left(\sum\limits_{\begin{subarray}{c}k=1\\\
k\neq
n\end{subarray}}^{N}P^{d}_{k\acute{k}}[t]h^{d}_{k\acute{n}}[t]+B^{d}[t]N_{0}\right).}_{\tilde{R}^{d}_{n,2}[t]}$

To prove the quasi-convexity of the optimization problem formulated in P2, we
need to prove that both $\tilde{R}^{d}_{n,1}[t]$ and $\tilde{R}^{d}_{n,2}[t]$
are concave. Let us start with $\tilde{R}^{d}_{n,2}[t]$. We refer to the
following lemma in [16]:

Lemma 1: If $f$ and $g$ are concave, positive, with one non-decreasing and the
other non-increasing, then $fg$ is concave.

It can be noticed that $-B^{d}[t]$ is concave and non-increasing while
$\log_{2}\left(\sum_{\begin{subarray}{c}k=1,k\neq
n\end{subarray}}^{N}P^{d}_{k\acute{k}}[t]h^{d}_{k\acute{n}}[t]+B^{d}[t]N_{0}\right)$
is concave and non-decreasing in terms of $B^{d}[t]$. Hence,
$\tilde{R}^{d}_{n,2}[t]$ is a concave function.

Using the same approach, we can prove that $\tilde{R}^{d}_{n,1}[t]$ is a
convex function (i.e., by proving that $-\tilde{R}^{d}_{n,1}[t]$ is a concave
function). Therefore, $\tilde{R}^{d}_{n,1}[t]$ needs to be converted to a
concave function in order to make constraint (20) concave. To tackle the non-
concavity of $\tilde{R}^{d}_{n,1}[t]$, the SCA technique can be applied
(similar to P1) where in each iteration, the original function is approximated
by its first order Taylor expansion. Therefore, given $B^{d}(r)[t]$ in
iteration $r$, we obtain the following lower bound for
$\tilde{R}^{d}_{n,1}$(r)[t]:

$\displaystyle\tilde{R}^{d}_{n,1}(r)[t]\geq$ $\displaystyle\phi_{2}(r)[t]+$
(27) $\displaystyle\left[\frac{B^{d}(r)[t]N_{0}}{\ln
2\phi_{1}(r)[t]}+\phi_{2}(r)[t]\right](B^{d}[t]-B^{d}(r)[t]).\vspace{-10mm}$

where
$\phi_{1}(r)[t]=B^{d}(r)[t]N_{0}+\sum_{k=1}^{N}P^{d}_{k\acute{k}}[t]h^{d}_{k\acute{n}}[t]$
and $\phi_{2}(r)=B^{d}(r)\log_{2}(\phi_{1}(r))$. By applying the same
procedure to the other constraints (i.e., (18) and (19)), P2 becomes a quasi-
convex optimization and it can be solved efficiently using SCA.

###  IV-C UAV Trajectories and Association Optimization

In this subsection, we consider optimizing the trajectories and associations
of the UAVs for fixed resource allocations (i.e., transmit powers and
bandwidth allocations). Even with fixed resource allocations, the problem is
still non-convex and it is very difficult to find an approximate solution due
to the channel expression and the association binary variables
$\epsilon^{r}_{lm}[t]$. Therefore, we introduce a quick and efficient
algorithm based on a recursive shrink-and-realign process. The main advantages
of this algorithm over other heuristic algorithms can be summarized as
follows: (i) it is easy to implement by using a simple search process with few
parameters to manipulate, (ii) it has low computational cost, and (iii) it
provides fast convergence to a close-to-optimal solution.

We propose a Recursive Uniform Search (RUS) algorithm to optimize the UAV
trajectories and associations. We assume that the association between UAVs and
users can be done based on the best favorite channel, where the user is
associated with the best UAV link. Our algorithm starts by generating initial
$Q$ high-efficiency next position candidates for each UAV
$\mathbb{J}^{q}_{l},\;q=1\cdots Q,\forall l$ with a total of $Q^{L}$
candidates for all UAVs to identify promising candidates and to form initial
populations ${\mathcal{Q}}$. We select to distribute the candidates uniformly
over the surface of a sphere (we start by assuming the radius of this sphere
$r_{0}$ equal to half of the UAV coverage radius) and the initial candidate is
its center (where the UAV is currently located). Then, it determines the
objective function achieved by each candidate by solving P1 and P2, and this
will guide us to the direction of the best candidate. Note that the
association depends on the trajectory of each UAV and also depends on the
channel between UAVs and users. After that, it finds the initial best local
candidate $q^{i,\text{local}}[t]$ that provides the best solution for
iteration $i$. Then, we start recursive sampling with uniform distribution
over a new sphere with a radius _shrunk_ to half of the previous sphere (i.e.,
$r_{i-1}/2$) and its center realigned to $q^{i,\text{local}}[t]$. Using this
shrink-and-realign process, we find the best solution $q^{*}$ and the
corresponding trajectory $\mathbb{J}^{q^{*}}$. This shrink-and-realign
procedure is repeated until the size of the sample space, i.e., the volume of
the sphere, decreases below a certain threshold or reach a maximum iteration
count of $I_{\text{iter}}$. The details of the joint optimization approach are
given in Algorithm 1.

Algorithm 1 Joint optimization algorithm

1: i=1.

2: Generate an initial population ${\mathcal{Q}}$.

3: while Not converged or reaching maximum iteration do

4: for $q=1\cdots Q^{L}$ do

5: Initialize
$P^{r}_{ml}[t],P^{r}_{l\acute{m}}[t],P^{d}_{n\acute{n}}[t],B^{d}[t],B^{r}_{m}[t]$

6: while Not converged do

7: Find
$P^{r}_{ml}[t],P^{r}_{l\acute{m}}[t],P^{d}_{n\acute{n}}[t],B^{d}[t],B^{r}_{m}[t]$
by solving P1 and P2 optimization problems for candidate $q$ after using the
approximation approaches described in Sections IV.

8: end while

9: end for

10: Find
$q^{\text{i,local}}[t]=\arg\underset{q}{\mathrm{max}}\,\mathcal{U}(R_{\min}[t])$,
(i.e., $q^{\text{i,local}}[t]$ indicates the index of the best local candidate
that results in the highest objective function for iteration $i$).

11: Initially $r_{0}=\bar{V}\tau$.

12: if $q^{\text{i,local}}[t]\leq q^{\text{i-1,local}}[t]$ then

13: Re-align the center of sample space to the new point.

14: Start recursive sampling with uniform distribution over a sphere with
center equal to $q^{i,\text{local}}[t]$.

15: else

16: Shrink the sample space by updating the radius.

17: end if

18: i=i+1.

19: end while

##  V Selected Numerical Results

In this section, we provide selected numerical results to show our system’s
performance. We consider a system with $L=5$ UAVs flying at 60 m elevation,
connected with different number of ground users distributed randomly within an
area of 800m $\times$ 800m. We assume that $\bar{P}_{l}$ is the same for all
UAVs and $\bar{P}_{u}$ is the same for all ground users. The noise power
$N_{0}$ is assumed to be $2.5\times 10^{-25}$ W/Hz [8]. The constant values
are selected to be $\nu_{1}=9.6$ and $\nu_{2}=0.29$ for a low-elevation
atmosphere where the UAVs will be flying [8].

The charging station is located at the center (400m, 400m, 60m). Initially we
assume that the locations, i.e., x and y coordinates, of the UAVs are in
meters as [(400,400,60), (200,200,60), (200,600,60), (600,200,60),
(600,600,60)]. Also, we assume that the initial battery level of the UAVs are
given respectively as ($\bar{S},\bar{S}/2,\bar{S}/2,\bar{S}/2,\bar{S}/2$). In
Table I, we present the values of the remaining environmental parameters used
in the simulations, which are found to be representative for low-flying UAVs
[17].

Table I:  System parameters Parameter | Value | Parameter | Value | Parameter | Value
---|---|---|---|---|---
$\bar{B}$(MHz) | $20$ |  $\xi_{\text{LoS}}$ (dB) | 1 |  $\xi_{\text{NLoS}}$ (dB) | 12
$\lambda$ (m) | 0.125 | $Q$ | $10$ | $I_{\text{iter}}$ | 10
$\alpha_{l}$ | 4 |  $\beta_{l}$ (W) | 6.8 |  $\bar{S}$ (kJ) | $15$
$r_{p}$ (cm) | $20$ | $\omega_{p}$ | 4 |  $P^{s}$ (W) | 0.5
$P^{ch}$ (W) | $10$ |  $\bar{V}$ (m/s) | 15 |  $m_{\text{tot}}$ (Kg) | 1

Figure 2: The proposed trajectory example with $\bar{P}_{l}=36$ dBm,
$\bar{P}_{u}=20$ dBm, $M=10$ and $N=10$.

Figure 3: System performance versus UAV transmit power $\bar{P}_{l}$ with
fixed $\bar{P}_{u}=20$ dBm, for two different user densities.

We start our simulation results by showing how the UAV trajectories update if
users move to new locations. Fig. 2 considers an example of this effect. It
shows that when some users move to certain directions, the UAVs update their
trajectories to maintain an energy-efficient solution. We assumed that for a
given time, the locations of users are given in Fig. 2-a. Based on the
optimization solution, only 3 out of 5 UAVs are needed to maximize the energy
efficiency for these user locations. However, when users start moving, such as
some of them moving to the left side (i.e., the users inside the oval shape in
Fig. 2-b), we update the optimization problem based on the battery level of
the UAVs. This may increase the number of needed UAVs as shown in Fig. 2-b (in
this case a fourth UAV is moving from the charging station in the center to an
optimize serving location.) This proves that our solution is a dynamic
solution taking into consideration the users’ movements.

The system performance is discussed in Fig. 3. We consider low and high user
density scenarios, $U$=40 and $U$=100, respectively, where we assume $M=N$ in
both scenarios and users’ power budget is $\bar{P}_{u}=20$ dBm. In Fig. 3-a,
we plot the average minimum user throughput versus UAVs’ transmit power
$\bar{P}_{l}$. In terms of minimum throughput, we notice that the minimum
achievable throughput is improving with the increase of $\bar{P}_{l}$ up to a
certain point and then it remains almost constant, due to the fact that the
minimum throughput also depends on the $R^{r}_{m,l}$ (the uplink between the
user $m$ and UAV $l$) that is dependent on $P^{r}_{m,l}$ and limited by
$\bar{P}_{u}$. On the other hand, Fig. 3-b plots the average energy J/s versus
$\bar{P}_{l}$. We have two remarks, firstly, serving more users increases the
energy consumption, and secondly, as $\bar{P}_{l}$ increases, the coverage
area of the UAVs increases which allow more flexibility in sending UAVs from
charging station to serve users. Fig. 3-c plots the average energy efficiency
versus $\bar{P}_{l}$.

Fig. 5 compares between our proposed solution and uniform case, where we
distribute the power and bandwidth equally to the users. Please note that, we
assume fixed power $\bar{P}_{u}$ for simplicity only. The figure shows that
our proposed solution outperforms the uniform case. For instance, our proposed
solution can achieve 50% improvement in energy efficacy compared to uniform
case by using $\bar{P}_{l}=25$ dBm by acheiving around $6\times 10^{4}$
bits/s/J instead of $4\times 10^{4}$ bits/s/J. In addition, we can see that
the confidence interval is around 94%.

Figure 4: Proposed versus uniform solutions.

Figure 5: Convergence speed.

Finally, the convergence speed of our approximation is shown in Fig. 5. We
plot the energy efficiency versus the number of iterations for two user
densities to solve the optimization problems P1 and P2 for $\bar{P}_{l}=36$
dBm, and $\bar{P}_{u}=20$ dBm. The results shows that we can reach convergence
with only few iterations (fewer than 8 iterations). Note that an iteration in
Fig. 5 corresponds to one iteration of the “while loop” given in Algorithm 1
(i.e., line 6-8). This implies that the UAVs will be able to calculate their
near-optimal resource allocation in real-time as each iteration of the while
loop takes a small amount of time, i.e., 1-2 seconds with a typical CPU.

##  VI Conclusion

In this paper, we proposed a new approach to manage the resource allocation
for D2D communications using multiple moving UAVs. The UAVs can work as relays
when needed. We formulated an optimization problem that maximizes the energy
efficient utility while taking into consideration the power and bandwidth
limitations, in addition to the association constraints. The optimization
framework enables the UAVs to optimize their trajectories as well as the
transmit power and bandwidth allocations of the D2D links while also deciding
which user devices on the ground are going to be associated to which UAV. Due
to non-convexity of the problem, we proposed an approximated solution based on
Taylor series expansion for resource allocation and a recursive shrink-and-
realign process for trajectory and UAV-user association optimization. In our
next challenging task, we are going to improve our system model by considering
multi-hop relays among the multiple UAVs trying to facilitate D2D
communications among the user devices on the ground. This will add more
complexity to the problem, but on the other hand, it will further improve the
performance.

## References

  * [1] A. Asadi, Q. Wang, and V. Mancuso, “A survey on device-to-device communication in cellular networks,” _IEEE Communications Surveys Tutorials_ , vol. 16, no. 4, pp. 1801–1819, Fourthquarter 2014.
  * [2] _Disaster Information Reporting System_ , Dec. 2015.
  * [3] A. Murkaz and et.al, “Architecture and protocols for inter-cell device-to-device communication in 5G networks,” in _Proc. of the 14th IEEE International Conference on Dependable, Autonomic and Secure Computing, Auckland, New Zealand_ , Aug. 2016, pp. 489–492.
  * [4] M. Selim, A. Alsharoa, and A. Kamal, “Hybrid cell outage compensation in 5G networks: Sky-ground approach,” in _Proc. of the IEEE ICC, Kansas City, MO, USA_ , May 2018.
  * [5] Y. Zeng and R. Zhang, “Energy-efficient UAV communication with trajectory optimization,” _IEEE Transactions on Wireless Communications_ , vol. 16, no. 6, pp. 3747–3760, June 2017.
  * [6] Y. Zeng, R. Zhang, and T. J. Lim, “Throughput maximization for UAV-enabled mobile relaying systems,” _IEEE Transactions on Communications_ , vol. 64, no. 12, pp. 4983–4996, Dec 2016.
  * [7] H. Ghazzai, M. B. Ghorbel, A. Kadri, M. J. Hossain, and H. Menouar, “Energy-efficient management of unmanned aerial vehicles for underlay cognitive radio systems,” _IEEE Transactions on Green Communications and Networking_ , vol. 1, no. 4, pp. 434–443, Dec 2017.
  * [8] M. Mozaffari, W. Saad, M. Bennis, and M. Debbah, “Unmanned aerial vehicle with underlaid device-to-device communications: Performance and tradeoffs,” _IEEE Transactions on Wireless Communications_ , vol. 15, no. 6, pp. 3949–3963, June 2016.
  * [9] A. Alsharoa and M. Yuksel, “UAV-Direct: Facilitating D2D communications for dynamic and infrastructure-less networking,” in _Proceedings of the 4th ACM Workshop on Micro Aerial Vehicle Networks, Systems, and Applications (DroNet workshop), Munich, Germany_ , 2018, pp. 57–62.
  * [10] A. Al-Hourani, S. Kandeepan, and A. Jamalipour, “Modeling air-to-ground path loss for low altitude platforms in urban environments,” in _Proc. of the IEEE GLOBECOM, Austin, TX, USA_ , Dec. 2014.
  * [11] Y. W. Y. Zheng and F. Meng, “Modeling and simulation of pathloss and fading for air-ground link of haps within a network simulator,” in _IEEE CyberC, Beijing, China_ , Oct. 2013.
  * [12] “Energy efficiency analysis of the reference systems, areas of improvements and target breakdown,” _Energy Aware Radio and neTwork tecHnologies_ , Dec. 2010.
  * [13] J. V. Dries Hulens and T. Goedeme, “How to choose the best embedded processing platform for onboard UAV image processing,” in _International Joint Conference Computer Vision, Imaging and Computer Graphics Theory and Applications, Berlin, Germany_ , Mar. 2015.
  * [14] G. Kramer, M. Gastpar, and P. Gupta, “Cooperative strategies and capacity theorems for relay networks,” _IEEE Transactions on Information Theory_ , vol. 51, no. 9, pp. 3037–3063, Sept. 2005.
  * [15] Y. Song, G.and Li, “Cross-layer optimization for OFDM wireless networks-Part I: Theoretical framework,” _IEEE Transactions on Wireless Communications_ , vol. 4, no. 2, pp. 614–624, Apr. 2005.
  * [16] S. Boyd and L. Vandenberghe, _Convex Optimization_. New York, NY, USA: Cambridge University Press, 2004.
  * [17] A. Alsharoa, H. Ghazzai, A. Kadri, and A. E. Kamal, “Spatial and temporal management of cellular hetnets with multiple solar powered drones,” _IEEE Transactions on Mobile Computing_ , pp. 1–15, Feb. 2019.


* [63] J.M. Link et al. (FOCUS), Phys. Lett. B 681, 14 (2009), 0905.4846
  * [64] J. Gasser, A. Rusetsky, Eur. Phys. J. C 78, 906 (2018), 1809.06399
  * [65] B. Aubert et al. (BaBar), Phys. Rev. D 78, 034023 (2008), 0804.2089
  * [66] A. Bondar, A. Poluektov, _On model-independent measurement of the angle phi(3) using Dalitz plot analysis_ , in _4th International Workshop on the CKM Unitarity Triangle (CKM 2006)_ (2007), hep-ph/0703267
  * [67] A. Bondar, A. Poluektov, Eur. Phys. J. C 55, 51 (2008), 0801.0840
  * [68] L.M. Zhang et al. (Belle), Phys. Rev. Lett. 99, 131803 (2007), 0704.1000
  * [69] J.P. Dedonder, R. Kaminski, L. Lesniak, B. Loiseau, Phys. Rev. D 89, 094018 (2014), 1403.2971
  * [70] S. Kopp et al. (CLEO), Phys. Rev. D 63, 092001 (2001), hep-ex/0011065
  * [71] N. Lowrey et al. (CLEO), Phys. Rev. D 84, 092005 (2011), 1106.3103
  * [72] H. Muramatsu et al. (CLEO), Phys. Rev. Lett. 89, 251802 (2002), [Erratum: Phys.Rev.Lett. 90, 059901 (2003)], hep-ex/0207067
  * [73] I. Adachi et al. (BaBar, Belle), Phys. Rev. D 98, 112012 (2018), 1804.06153
  * [74] J. Adler et al. (MARK-III), Phys. Lett. B 196, 107 (1987)
  * [75] J.C. Anjos et al. (E691), Phys. Rev. D 48, 56 (1993)
  * [76] P.L. Frabetti et al. (E687), Phys. Lett. B 331, 217 (1994)
  * [77] R. Aaij et al. (LHCb), JHEP 03, 176 (2019), 1810.03138
  * [78] M. Ablikim et al. (BESIII), Phys. Rev. D 105(11), 112001 (2022), 2203.01555
  * [79] J.F. Donoghue, E. Golowich, B.R. Holstein, _Dynamics of the standard model_ , 2nd edn. (Cambridge University Press, 2014)
  * [80] M. Gronau, Phys. Rev. Lett. 83, 4005 (1999), hep-ph/9908237
  * [81] M. Suzuki, Phys. Rev. 144, 1154 (1966)
  * [82] M. Bauer, B. Stech, M. Wirbel, Z. Phys. C 34, 103 (1987)
  * [83] A. Anisovich, H. Leutwyler, Phys.Lett. B375, 335 (1996), hep-ph/9601237
  * [84] J.M. Blatt, V.F. Weisskopf, _Theoretical nuclear physics_ (Springer, New York, 1952), ISBN 978-0-471-08019-0