# Exact Resource Allocation over Fair Wireless Relay Networks

Edgar Arribas  Universidad Cardenal Herrera-CEU, CEU Universities
València, Spain  Vicent Cholvi  Universitat Jaume I
Castelló, Spain  Vincenzo Mancuso  IMDEA Networks Institute
Madrid, Spain

###### Abstract

In relay-enabled cellular networks, the intertwined nature of network agents
calls for complex schemes to allocate wireless resources. Resources need to be
distributed among mobile users while considering how relay resources are
allocated, and constrained by the traffic rate achievable by base stations and
over backhaul links. In this work, we derive a resource allocation scheme that
achieves $\max$–$\min$ fairness across mobile users. Furthermore, the optimal
allocation is found with linear complexity with respect to the number of
mobile users and relays.

##  I Introduction and Related Work

We consider a heterogeneous relay-enabled network [1] formed by a set of fixed
$g\\!N\\!B$s (_Next Generation Node B_) providing wireless service both to
mobile users and relays. Figure 1 shows an illustrative example of the
considered scenario. It can be seen that there are two $g\\!N\\!B$s that
provide service to three relays (a rooftop tower, a bus and a UAV) and also to
one mobile user. On the other hand, relays provide service to other mobile
users (e.g., on the bus, in the stadium or simply close to a relay).

We derive a mechanism that provides a fair throughput distribution to mobile
users. More concretely, we want to guarantee $\max$–$\min$ fairness [1],
aiming to maximize the performance of the worst-case mobile user, so potential
service outages can be minimized. The complexity of relay architectures makes
the analysis quite difficult due to the intertwined nature of all the involved
agents. Indeed, $g\\!N\\!B$ resources must be allocated not only to directly
served users, but also shared with relays, and relays may reuse wireless
resources to serve their mobile users, thus generating interference.
Additionally, the use of $g\\!N\\!B$ resources is also constrained by the
backhaul capacity. Finally, and no less important, wireless resources must be
assigned quickly to be able to adapt to changing scenarios, as guaranteed by
our proposal.

Figure 1: Reference scenario.

### Previous Work

In the last years there has been an increasing number of studies focused on
resource allocation in heterogeneous networks [1]. Here, we review some
previous works, showing the different directions followed by them.

In [2], the authors focus on a downlink wireless network aided by a single
unmanned aerial vehicle (UAV) which serves users aiming to maximize the
minimum average rate among all users. In [3], the authors investigate the
application of the non-orthogonal multiple access technique for the case of a
single UAV relay and solve a joint channel-and-power allocation problem with
an iterative algorithm under $\max$–$\min$ fairness, yet not achieving optimal
results. Those studies cannot be extended to the case of multiple relays
addressed in this paper.

In [4], the authors study proportional and $\max$–$\min$ fairness mechanisms
in cognitive radio networks, where secondary users act as relays, aiming to
provide an acceptable throughput. However, different from us, their analysis
is restricted to IoT scenarios and needs the use of non-convex problems, which
prevents finding optimal results in reasonable time.

In [5], the authors consider a scenario similar to ours. However, they take
restrictive assumptions regarding how resources is allocated, and ignore
inter-cell interference as well as interference between $g\\!N\\!B$s and
relays. With that, they propose a heuristic and show that it can improve
fairness.

### Our Work

We develop a $\max$–$\min$ fair resource allocation algorithm that permits to
jointly allocate resources to both mobile users and relays, considering
interference and backhaul bottlenecks. The proposed algorithm finds the exact
solution for the associated optimization problem, which goes beyond existing
results. Another important feature is that our algorithm has linear complexity
with respect to the number of mobile users and relays, which is a strong
advantage when it comes to practical implementations.

##  II System Model

We consider a wireless relay-enabled network composed by a set of fixed
$g\\!N\\!B$s and a set of relays that provide cellular service to a set of
mobile users in either downlink or uplink. Each $g\\!N\\!B$ is attached to a
wired backhaul network, whereas each relay is attached to one $g\\!N\\!B$ by
means of a wireless backhaul link.

The set of relays attached to $g\\!N\\!B$ $g$ is denoted as $\mathcal{R}_{g}$,
the set of $g\\!N\\!B$-served users is denoted as $\mathcal{U}_{g}$, for each
$g\\!N\\!B$ $g$, the set of users served by relay $r$ is denoted as
$\mathcal{U}_{r}$, and the set of users served by some relay attached to
$g\\!N\\!B$ $g$ is denoted as $\mathcal{U}_{g}^{*}$.

Each $g\\!N\\!B$ $g$ receives a maximum traffic capacity rate (denoted
$\tau_{g}$) from the wired backhaul network, perhaps different from that of
the other $g\\!N\\!B$s. We denote as $W^{g}_{\text{relays}}$ the bandwidth of
$g\\!N\\!B$ $g$ dedicated to relays and as $W^{g}_{\text{users}}$ the
bandwidth of $g\\!N\\!B$ $g$ dedicated to users directly attached to $g$. In
addition, each relay $r$ will allocate its bandwidth, which we denote as
$W^{r}_{\text{users}}$, among the users it serves (note that
$W^{g}_{\text{relays}}$, $W^{g}_{\text{users}}$ and $W^{r}_{\text{users}}$ are
fixed values, since the assignment of spectrum bands to operators is performed
by means of government auctions where only channels of fixed bandwidth are
offered [6]). Such bands for mobile users and relays may be deployed by the
operator as either orthogonal or reused bands. What matters for our analysis
is that interference, if present, is accounted for. After that, operators can
split the assigned bandwidth into smaller portions to allocate sub-channels to
specific groups of users and services, according to their target (e.g.,
optimize a fair network performance).

On another hand, it must be taken into account that practical systems cannot
assign arbitrary a small bandwidth to individual stations or users [7].
Concretely, each relay obtains a minimum bandwidth of
$W^{\text{min}}_{\text{relays}}$, while each served mobile user receives a
minimum bandwidth of $W^{\text{min}}_{\text{users}}$.

Mobile users access wireless resources with an OFDMA scheme, as in 3GPP
networks [6]. Thus, mobile users under the coverage of the same $g\\!N\\!B$ or
relay do not suffer intra-cell interference. However, mobile users can suffer
inter-cell interference if they are attached to different $g\\!N\\!B$s or
relays. In addition, relay links might interfere among themselves.

Although the above-mentioned interference can be reduced by making both
$g\\!N\\!B$s and relays use 3D-beamforming or adopting orthogonal frequencies,
depending on the scenario it will be necessary to take into account the signal
strength of each wireless channel, measured as the SINR (_signal to
interference & noise ratio_). We denote by $\gamma_{g,r}$ the SINR of the
relay link between $g\\!N\\!B$ $g$ and a relay $r$, and by $\gamma_{s,u}$ the
SINR of the access link between a station $s$ (either a $g\\!N\\!B$ or a
relay) and a mobile user $u$.

Table I summarizes the system model parameters that we will use along the
paper.

Table I: System model parameters Parameter |  Description
---|---
$\mathcal{R}_{g}$ |  Set of relays attached to $g\\!N\\!B$ $g$.
$\mathcal{U}_{g}$, $\mathcal{U}_{r}$, $\mathcal{U}^{*}_{g}$ |  Mobile users attached to $g\\!N\\!B$ $g$, mobile users attached to a relay $r$, and mobile users attached to any relay $r$ (i.e., $\bigcup_{r\in\mathcal{R}_{g}}\\!{\cal U}_{r}$).
$\tau_{g}$ |  Maximum traffic rate of $g\\!N\\!B$ $g$.
$W^{g}_{\text{relays}}$, $W^{g}_{\text{users}}$, $W^{r}_{\text{users}}$ |  Bandwidth of $g\\!N\\!B$ $g$ dedicated to relays, bandwidth of $g\\!N\\!B$ $g$ dedicated to mobile users and bandwidth of relay $r$ (dedicated to mobile users).
$W^{\text{min}}_{\text{relays}}$, $W^{\text{min}}_{\text{users}}$ |  Minimum bandwidth allocation to each relay and each mobile user.
$\gamma_{s,y}$ |  SINR between $s$ and $y$, where $s$ is a station (a $g\\!N\\!B$ or a relay) and $y$ is either a mobile user or a station.

##  III The Resource Allocation Problem

The aim of our work is to optimize the $\max$-$\min$ fairness of the
throughput received by mobile users. This is not a trivial task, since all the
involved agents ($g\\!N\\!B$s, relays and mobile users) are intertwined (e.g.,
resources of mobile users from one relay cannot be allocated without knowing
what backhaul resources that relay will get, depending on other relay
resources and the $g\\!N\\!B$ bottleneck over the wired backhaul), while the
interference management also involves different types of colliding wireless
channels. Since at resource allocation the network disposes of the _channel
state information_ (CSI) feedback necessary to know the SINRs of the channels,
each $g\\!N\\!B$ will be able to solve the resource allocation problem for its
relays, its mobile users, and the users of relays attached to that $g\\!N\\!B$
in a concurrent and independent manner, by using the convex program that we
will introduce next.

More formally, it will be necessary to obtain, for each relay $r$ and for each
mobile user $u$, both the share of bandwidth assigned (denoted $w_{r}$ and
$w_{u}$), and the aggregate throughput experienced by the network node
(denoted $T_{r}$ and $T_{u}$).

In Eq. (1) we formulate, for each $g\\!N\\!B$ $g$, the corresponding resource
allocation optimization in a Convex Program (CP):

$\begin{cases}\hskip
85.35826pt\mathclap{\max\min\left\\{T_{u}\,\Huge{\mid}\,u\in\mathcal{U}_{g}\bigcup\;\mathcal{U}^{*}_{g}\right\\},\quad\text{s.t.:
}}\\\ \\\ 1.\leavevmode\nobreak\ \leavevmode\nobreak\ w_{r}\geq
W^{\min}_{\text{relays}},&\forall r\\!\in\\!\mathcal{R}_{g};\\\
2.\leavevmode\nobreak\ \leavevmode\nobreak\
\sum_{r\in\mathcal{R}_{g}}\\!w_{r}=W^{g}_{\text{relays}};&\\\
3.\leavevmode\nobreak\ \leavevmode\nobreak\
T_{r}\\!\leq\\!w_{r}\log_{2}\\!\left(1\\!+\\!\gamma_{g,r}\right),&\forall
r\\!\in\\!\mathcal{R}_{g};\\\ \\\ 4.\leavevmode\nobreak\ \leavevmode\nobreak\
w_{u}\geq W^{\min}_{\text{users}},&\forall
u\\!\in\mathcal{U}_{g}\bigcup\mathcal{U}_{g}^{*};\\\ 5.\leavevmode\nobreak\
\leavevmode\nobreak\
\sum_{u\in\mathcal{U}_{g}}\\!w_{u}=W^{g}_{\text{users}};&\\\
6.\leavevmode\nobreak\ \leavevmode\nobreak\
\sum_{u\in\mathcal{U}_{r}}\\!w_{u}=W^{r}_{\text{users}},&\forall
r\\!\in\\!\mathcal{R}_{g};\\\ \\\ 7.\leavevmode\nobreak\ \leavevmode\nobreak\
T_{u}\leq
w_{u}\log_{2}\\!\left(1\\!+\\!\gamma_{s,u}\right),&\forall(s,u)\\!\in\\!\left(\\!\\{g\\}\\!\bigcup\\!\mathcal{R}_{g}\\!\right)\\!\times\\!(\mathcal{U}_{g}\\!\bigcup\mathcal{U}^{*}_{g});\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\\
8.\leavevmode\nobreak\ \leavevmode\nobreak\
\sum_{u\in\mathcal{U}_{r}}\\!T_{u}\\!\leq T_{r},&\forall
r\\!\in\\!\mathcal{R}_{g};\\\ 9.\leavevmode\nobreak\ \leavevmode\nobreak\
\\!\sum_{u\in\mathcal{U}_{g}}\\!T_{u}\\!+\\!\sum_{r\in\mathcal{R}_{g}}\\!T_{r}\\!\leq\\!\tau_{g}.\\!\\!\\!\\!&\vspace{-0.15mm}\textstyle\end{cases}$
(1)

The first three constraints are related to the backhaul relay allocations. The
first one guarantees that each relay obtains a minimum bandwidth, the second
one states that the aggregated share bandwidth of relays must adjust to the
whole channel bandwidth, and the third one expresses the Shannon capacity.

The fourth constraint guarantees a minimum bandwidth for each served user,
while the fifth and sixth constraints state that the aggregate share bandwidth
of these users must adjust to the whole channel capacity allowed by their
serving station, either the $g\\!N\\!B$ or a relay.

The seventh constraint restricts the throughput allocated to mobile users
(served either by the $g\\!N\\!B$ or by a relay) to the Shannon capacity. The
eighth constraint expresses the fact that the throughput allocated to relay-
served users cannot exceed the wireless backhaul capacity assigned to the
relay. Finally, the ninth constraint states that the aggregated throughput
served by the $g\\!N\\!B$ (to mobile users and relays) cannot exceed the
$g\\!N\\!B$ bottleneck over the wired backhaul.

The optimization of Eq. (1) is a convex problem. Hence, it is solvable in
polynomial time with standard interior-point methods [8]. However, such a
polynomial time is still of cubic order with respect to the number of mobile
users [9], which is prohibitive for real-time applications, specially for
large mobile user populations.

Thus, in the next section, we derive an exact analytical solution that has a
linear complexity in the number of operations both with respect to the number
of mobile users and to the number of relays attached to the $g\\!N\\!B$.
Namely, the complexity is of the order of
$\mathcal{O}(|\mathcal{U}_{g}\bigcup{\cal U}^{*}_{g}|\\!\cdot\\!|{\cal
R}_{g}|)$, in the worst case.

##  IV The Exact $\max$–$\min$ Resource Allocation

In this section we find the exact $\max$–$\min$ resource allocation. For that,
we first introduce the exact solution to a preliminary scenario in Section
IV-A and, upon that, build the final solution to the general case, in Section
IV-B.

###  IV-A The preliminary scenario: One Base Station Without Relays

In this scenario, we consider one base station $s$ (namely, the $g\\!N\\!B$ or
a relay) with no further relays attached to $s$. The CP of Eq. (1) simplifies
considerably since the station only needs to manage resources to be split
among its served users $\mathcal{U}$:

$\begin{cases}\max\min\left\\{T_{u}\,\mid\,u\in\mathcal{U}\right\\}\\!,&\text{s.t.:}\\\
w_{u}\geq W^{\min},&\forall u\\!\in\\!\mathcal{U};\\\
\sum_{u\in\mathcal{U}}\\!w_{u}=W_{\\!\text{users}};&\\!\\!\\\
T_{u}\\!\leq\\!w_{u}\log_{2}\\!\left(1\\!+\\!\gamma_{s,u}\right)\\!,&\forall
u\\!\in\\!\mathcal{U};\\\
\sum_{u\in\mathcal{U}}\\!T_{u}\\!\leq\tau,&\\!\\!\end{cases}$ (2)

where $W_{\\!\text{users}}$ and $W^{\min}$ are the total and minimum allocable
bandwidth of the channel, while $\tau$ is the backhaul limitation.

The exact solution to such problem is derived in Algorithm 1, followed by
Algorithm 2. Algorithm 1 is meant to find the optimal $\max$–$\min$ resource
allocation when there is no capacity limitation (i.e., the $\tau$–constraint
is ignored), while Algorithm 2 ensures that the $\max$–$\min$ rates are
subsequently adjusted in a way that maintains the $\max$–$\min$ fairness found
by Algorithm 1 and the aggregate user rate does not exceed the backhaul
capacity limitation.

In Algorithm 1, we initially set $w_{u}\\!=\\!W^{\min}$ and
$T_{u}\\!=\\!W^{\min}\\!\cdot\\!\log_{2}\\!\left(1\\!+\\!\gamma_{s,u}\right)$,
$\forall u\\!\in\\!\mathcal{U}$ (cf. step 1), and define the set $\mathcal{J}$
as those indices $u$ such that $T_{u}$ is minimum (cf. step 2):

$\displaystyle\mathcal{J}=\left\\{u\in\mathcal{U}\,\mid\,T_{u}=\min\left\\{T_{v}\,\mid\,v\in\mathcal{U}\right\\}\right\\}.$
(3)

While there are resources to allocate, i.e.,
$\sum_{u\in\mathcal{U}}\\!w_{u}\\!<\\!W_{\\!\text{users}}$, and
$|\mathcal{J}|\\!\\!\neq\\!\\!|\mathcal{U}|$, we take index
$v_{0}\\!=\\!\arg\min_{u\notin\\!\mathcal{J}}\\!T_{u}$ so that $T_{v_{0}}$ is
the lowest rate not equal to the minimum rate (cf. step 4). Now, we aim to
increase $w_{u}$ as much as possible in a way that is $\max$-$\min$ fair and
$T_{u}\\!\leq\\!T_{v_{0}}\\!,\forall u\\!\\!\in\\!\\!\mathcal{J}$. Then, we
find $\\{\\!k_{u}\\!\\}_{u\\!\in\\!\mathcal{J}}$ so that
$\\{\\!w_{u}\\!\\}_{u\\!\in\\!\mathcal{J}}$ are increased by $k_{u}$ each. The
optimal way is by setting
$k_{u}\\!=\\!\frac{T_{v_{0}}}{\log_{2}\\!\left(\\!1+\gamma_{s,u}\\!\right)}\\!-\\!w_{u}$,
$\\!\forall u\\!\\!\in\\!\\!\mathcal{J}$ (cf. step 5) and checking if
$\sum_{u\in\mathcal{J}}\\!k_{u}\\!\leq\\!W_{\\!\text{users}}\\!-\\!\sum_{u\in\mathcal{U}}\\!w_{u}$.
If that inequality is not satisfied, then
$k_{u}\\!=\\!\frac{W_{\\!\text{users}}-\sum_{u\notin\mathcal{J}}w_{u}}{\log_{2}\\!\left(\\!1+\gamma_{s,u}\\!\right)\\!\sum_{\\!u\\!\in\\!\mathcal{J}}\\!\\!\frac{1}{\log_{2}(\\!1+\gamma_{s,u}\\!)}}\\!-\\!w_{u}$,
$\forall u\\!\in\\!\mathcal{J}$ (cf. step 7).

Once $k_{u}$ is derived, we assign $w_{u}\\!\leftarrow\\!w_{u}\\!+\\!k_{u}$,
$\forall u\\!\in\\!\mathcal{J}$ (cf. step 9). Now, if we have set
$k_{u}\\!=\\!\frac{T_{v_{0}}}{\log_{2}\\!\left(1+\gamma_{s,u}\right)}-w_{u}$,
$\forall u\\!\in\\!\mathcal{J}$, we re-set $\mathcal{J}$ as
$\mathcal{J}\leftarrow\mathcal{J}\cup\\{v_{0}\\}$ (cf. step 10), and start all
over.

Note 1 shows that the $\\{k_{u}\\}_{u\in\mathcal{J}}$ of each iteration of
Algorithm 1 yields the optimal $\max$–$\min$ fair resource distribution.

Algorithm 1 Resource allocation of without relays.

1: Start: $\\!w_{u}\\!\leftarrow\\!W^{\min}$,
$T_{u}\\!\leftarrow\\!w_{u}\log_{2}\\!\left(1\\!+\\!\gamma_{s,u}\\!\right)$,
$\\!\forall u\\!\in\\!\mathcal{U}$.

2:
$\mathcal{J}\leftarrow\left\\{u\in\mathcal{U}\,\mid\,T_{u}=\min\left\\{T_{v}\,\mid\,v\in\mathcal{U}\right\\}\right\\}$.

3: while $\sum_{u\in\mathcal{U}}w_{u}<W_{\\!\text{users}}$ and
$|\mathcal{J}|\neq|\mathcal{U}|$ do

4: $v_{0}\leftarrow\arg\min\\{T_{u}\,\mid\,u\notin\mathcal{J}\\}$ and
$K\leftarrow 1$.

5: $k_{u}\leftarrow T_{v_{0}}/\log_{2}\left(1+\gamma_{s,u}\right)-w_{u}$,
$\forall u\in\mathcal{J}$.

6: if
$\sum_{u\in\mathcal{J}}k_{u}>W_{\\!\text{users}}-\sum_{u\in\mathcal{U}}w_{u}$
then

7:
$k_{u}\\!\\!\leftarrow\\!\frac{W_{\\!\text{users}}-\sum_{u\notin\mathcal{J}}w_{u}}{\log_{2}\\!\left(\\!1+\gamma_{s,u}\\!\right)\\!\sum\limits_{u\\!\in\\!\mathcal{J}}\\!\\!\frac{1}{\log_{2}\left(\\!1+\gamma_{s,u}\\!\right)}}\\!-\\!w_{u}$,
$\\!\forall u\\!\in\\!\mathcal{J}$ and $K\\!\leftarrow\\!0$.

8: end if

9: $w_{u}\\!\\!\leftarrow\\!w_{u}\\!+\\!k_{u}$, $\\!\forall
u\\!\in\\!\mathcal{J}\\!$ and
$T_{u}\\!\\!\leftarrow\\!w_{u}\\!\log_{2}\\!\left(\\!1\\!+\\!\gamma_{s,u}\\!\right)$,
$\forall u\\!\in\\!\mathcal{J}$.

10: if  $K=1$,  then  $\mathcal{J}\leftarrow\mathcal{J}\cup\\{v_{0}\\}$,  end
if

11: end while

12: Output:  $T\leftarrow\min\left\\{T_{u}\,\mid\,u\in\mathcal{U}\right\\}$.

######  Note 1.

Given a distribution of resources $\\{w_{u}\\}_{u\in\mathcal{U}}$ and
throughput rates $\\{T_{u}\\}_{u\in\mathcal{U}}$ such that
$T_{u}=w_{u}\log_{2}\left(1+\gamma_{s,u}\right)$, $\forall u\in\mathcal{U}$,
we define the set $\mathcal{J}$ as in Eq. (3). Hence, we have that
$w_{u}\log_{2}\\!\left(1\\!+\\!\gamma_{s,u}\right)=w_{k}\log_{2}\\!\left(1\\!+\\!\gamma_{s,k}\right)$,
$\forall u,k\in\mathcal{J}$.

Given $v_{0}=\arg\min\\{T_{u}\,\mid\,u\notin\mathcal{J}\\}$, we want to
increase $\\{w_{u}\\}_{u\in\mathcal{J}}$ as much as possible by $k_{u}$ each
in a $\max$–$\min$ fair way so that
$(\\!w_{u}\\!\\!+\\!\\!k_{u}\\!)\\!\log_{2}\\!\left(\\!1\\!+\\!\gamma_{s,u}\\!\right)\\!\leq\\!T_{\\!v_{0}}$,
$\forall u\\!\in\\!\mathcal{J}$. Hence, we must solve the following convex
program:

$\begin{cases}\max L;\quad\text{s.t.:}&\\\
(w_{u}+k_{u})\log_{2}\left(1+\gamma_{s,u}\right)\geq L,&\forall
u\\!\in\\!\mathcal{J};\\\
k_{u}\leq\frac{T_{v_{0}}}{\log_{2}\left(1+\gamma_{s,u}\right)}-w_{u},&\forall
u\\!\in\\!\mathcal{J};\\\ \sum_{u\in\mathcal{J}}k_{u}\leq
W_{\\!\text{users}}^{g}-\sum_{u\in\mathcal{U}}w_{u}.&\end{cases}\vspace{-0mm}$
(4)

The KKT conditions [10] to solve the CP of Eq. (4) are:

$\displaystyle-\mu_{u}+\mu_{|\mathcal{J}|+u}+\mu_{2|\mathcal{J}|+1}=0,$
$\displaystyle\forall u\\!\in\\!\mathcal{J};$ (5)
$\displaystyle-1+\sum_{u\in\mathcal{J}}\nolimits\mu_{u}/\log_{2}\left(1+\gamma_{s,u}\right)=0;$
(6)
$\displaystyle\mu_{u}\cdot\left(L/\log_{2}(1\\!+\\!\gamma_{s,u})-k_{u}-w_{u}\right)=0,$
$\displaystyle\forall u\\!\in\\!\mathcal{J};$ (7)
$\displaystyle\mu_{|\mathcal{J}|+u}\cdot\left(k_{u}-T_{v_{0}}/\log_{2}(1\\!+\\!\gamma_{s,u})+w_{u}\right)=0,$
$\displaystyle\forall u\\!\in\\!\mathcal{J};$ (8)
$\displaystyle\mu_{2|\mathcal{J}|+1}\\!\cdot\\!\left(\sum_{u\in\mathcal{J}}\nolimits\\!k_{u}-W_{\\!\text{users}}^{g}-\sum_{u\in\mathcal{U}}\nolimits\\!\\!w_{u}\\!\right)=0.$
(9)

If setting
$k_{u}\\!=\\!T_{v_{0}}/\log_{2}\\!\left(1\\!+\\!\gamma_{s,u}\right)\\!-\\!w_{u}$,
$\forall u\\!\in\\!\mathcal{J}$ accomplishes that
$\sum_{u\in\mathcal{J}}k_{u}\leq
W_{\\!\text{users}}^{g}-\sum_{u\in\mathcal{U}}w_{u}$, we have the optimal
solution, as each $k_{u}$ receives the maximum possible value and constraints
hold. Otherwise, $\exists
u_{0}\\!\in\\!\mathcal{J}\\!\\!\,\mid\,\\!\\!k_{u_{0}}\\!<\\!T_{v_{0}}/\log_{2}\\!\left(1\\!+\\!\gamma_{s,u_{0}}\\!\right)\\!-\\!w_{u_{0}}$
and $\mu_{|\mathcal{J}|+u_{0}}\\!=0$ from Eq. (8), and:

$k_{u}=\frac{W_{\\!\text{users}}^{g}-\sum_{u\notin\mathcal{J}}w_{u}}{\log_{2}\left(1+\gamma_{s,u}\\!\right)\sum_{u\in\mathcal{J}}\frac{1}{\log_{2}(1+\gamma_{s,u})}}-w_{u},\forall
u\\!\in\\!\mathcal{J}.$ (10)

∎

If the resource allocation from Algorithm 1 yields a feasible solution, i.e.,
$\sum_{u\in\mathcal{U}}\\!T_{u}\\!\leq\\!\tau$, the optimal $\max$–$\min$
allocation is found. Otherwise, due to the $\max$–$\min$ fairness nature,
every mobile user $u$ such that
$T_{u}\\!>\\!\min_{u\in\mathcal{U}}\\{T_{u}\\}$ disposes of the minimum amount
of resources, $W^{\min}$, and
$T_{u}=W^{\min}\\!\log_{2}\\!\left(\\!1\\!+\\!\gamma_{s,u}\\!\right)$,
$\forall
u\\!\in\\!\mathcal{U}\\!\,\mid\,\\!T_{u}\\!>\\!\min_{u\in\mathcal{U}}\\{T_{u}\\}$
(otherwise, if such mobile users disposed of more than $W^{\min}$ resources,
such exceeded resources could be reallocated to those mobile users with
minimum rate to increase the utility, which is not possible from the
$\max$–$\min$ fairness output).

Hence, as no resources can be removed from any mobile user $u$ such that
$T_{u}>\min_{u\in\mathcal{U}}\\{T_{u}\\}$, and
$\sum_{u\in\mathcal{U}}T_{u}>\tau$, we must apply Algorithm 2 to the set
$\mathcal{U}$ in order to reduce the rates in a way that keeps the
$\max$–$\min$ fairness and accomplishes the $\tau$–constraint. With that, the
$\max$–$\min$ fairness allocation of the CP of Eq. (2) is finally solved.

Algorithm 2 $\max$–$\min$ throughput reduction.

1: Input: Backhaul capacity limitation $\tau$, a set of users $\mathcal{U}$,
and their $\max$–$\min$ fair rates $\\{T_{u}\\}_{u\in\mathcal{U}}$.

2: $A=\sum_{u\in\mathcal{U}}\\!T_{u}$.

3: if $A\\!>\\!\tau$ then

4: $T_{\min}{=}\min\left\\{T_{u}\,\mid\,u\in\mathcal{U}\right\\}$,
$E{=}A{-}\tau$, $S{=}\sum_{u\in\mathcal{U}}\left(T_{u}{-}T_{\min}\right)$.

5: if $S\leq E$ then

6: $T_{u}\\!\leftarrow\\!\tau/|\mathcal{U}|$, $\forall u\\!\in\\!\mathcal{U}$.

7: else

8: $T_{u}\\!\leftarrow\\!T_{u}-E\cdot\frac{T_{u}-T_{\min}}{S}$, $\forall
u\\!\in\\!\mathcal{U}$.

9: end if

10: end if

11: Output:  $\\{T_{u}\\}_{u\in\mathcal{U}}$.

######  Note 2.

Algorithm 2 takes $\max$–$\min$ fair rates $\\{T_{u}\\}$ whose sum $A$ might
exceed the aggregate constraint $\tau$. If that happens, the algorithm
computes the initial $\max$–$\min$ fairness level through the value of
$T_{\min}$ as well as $(i)$ the excess aggregate throughput $E$, computed with
respect to $\tau$, and $(ii)$ the aggregate surplus $S$, i.e., the sum of
throughput values in excess to $T_{\min}$ (cf. step 4). There are two cases.
If the surplus is no more than the excess ($S\leq E$), then eliminating the
surplus will not be enough to meet the constraint on $\tau$. So, the only
solution is to assign each mobile user with equal resources
$\tau/|\mathcal{U}|$ (cf. step 6) which, in turn, will be less (or at most as
much as) the value $T_{\min}$ previously computed. Otherwise, the surplus is
more than the excess and the algorithm will reduce the surplus by exactly $E$,
reducing the individual surplus of each mobile user proportionally to its
initial value (cf. step 8). In all cases, the final rates are $\max$–$\min$
fair and do not exceed the capacity limitation $\tau$. ∎

###  IV-B The general scenario: A Wireless Relay Network

Now we consider the generic case, formulated in Eq. (1), and find the exact
resource allocation in Algorithm 3.

First, to each relay $r\\!\in\\!\mathcal{R}_{g}$, we set the minimum bandwidth
$w_{r}\\!=\\!W_{\\!\text{relays}}^{\min}$ and assign to them the highest
achievable rate,
$T_{r}\\!=\\!w_{r}\log_{2}\\!\left(1\\!+\\!\gamma_{g,r}\right)$ (cf. step 1).
Then, we find the optimal resource allocation at the $g\\!N\\!B$ with
Algorithm 1 and also find the optimal allocation at each relay
$r\\!\in\\!\mathcal{R}_{g}$ using Algorithm 1 and applying next Algorithm 2
with a backhaul capacity limitation of $\tau\\!=\\!T_{r}$. With that, we
dispose of $\\{T_{u}\\}_{u\in\mathcal{U}_{g}}$ and of
$\\{T_{r,u}\\}_{u\in\mathcal{U}_{r}}$, $\forall r\\!\in\\!\mathcal{R}_{g}$.
Note that $\forall r\\!\in\\!\mathcal{R}_{g}$, $\forall
u\\!\in\\!\mathcal{U}_{r}$ it might happen that
$T_{r,u}\\!<\\!w_{u}\log_{2}\\!\left(1\\!+\\!\gamma_{r,u}\right)$ due to the
limitation $T_{r}$. Hence, if $T_{r}$ increases, such $T_{r,u}$’s can also
increase.

Algorithm 3 The exact $\max$–$\min$ resource allocation

1: Start: $w_{r}\\!\leftarrow\\!W_{\text{$g\\!N\\!B$-users}}^{\min}$ and
$T_{r}\\!\leftarrow\\!w_{r}\\!\log_{2}\\!\left(1\\!+\\!\gamma_{g,r}\right)$,
$\forall r\\!\in\\!\mathcal{R}_{g}$.

2: Derive $\\{T_{u}\\}_{u\in\mathcal{U}_{g}}$ by solving optimal resource
allocation with Algorithm 1 and derive also
$\\{T_{r,u}\\}_{u\in\mathcal{U}_{r}}$, $\forall r\\!\in\\!\mathcal{R}_{g}$, by
solving optimal resource allocation for relays with Algorithm 1 and applying
next Algorithm 2 with a backhaul limitation of $\tau\\!=\\!T_{r}$.

3: $\beta\leftarrow 1$.

4: while $\beta=1$ do

5:
$T_{m}\\!\leftarrow\\!\min\\!\left\\{T_{\\!r,u}\\!\,\mid\,\\!T_{\\!r,u}\\!\\!<\\!w_{u}\\!\log_{2}\\!\left(1\\!+\\!\gamma_{g,r}\\!\right)\\!,r\\!\in\\!\mathcal{R}_{g},u\\!\in\\!\mathcal{U}_{r}\right\\}$.

6:
$\mathcal{L}_{m}\\!\leftarrow\\!\left\\{(r,u)\in\mathcal{R}_{g}\times\bigcup_{r\in\mathcal{R}_{g}}\mathcal{U}_{r}\,\mid\,T_{r,u}=T_{m}\right\\}$.

7:
$T_{M}\\!\leftarrow\\!\min\left\\{T_{r,u}\,\mid\,T_{r,u}>T_{m},r\in\mathcal{R}_{g},u\in\mathcal{U}_{r}\right\\}$.

8:
$T_{M_{2}}\\!\leftarrow\\!\min\left(T_{M},\min_{(r,u)\in\mathcal{L}_{m}}w_{u}\log_{2}\left(1+\gamma_{r,u}\right)\right)$.

9:
$\overline{\mathcal{U}}_{r}\\!\leftarrow\\!\left\\{u\in\mathcal{U}_{r}\,\mid\,(r,u)\in\mathcal{L}_{m}\right\\}$,
$\forall r\in\mathcal{R}_{g}$.

10:
$\beta\\!\leftarrow\\!\min\left(1,\,\frac{W_{\mathcal{\\!\text{relays}}}^{g}-\sum_{r\in\mathcal{R}_{g}}w_{r}}{\left(T_{M_{2}}-T_{m}\right)\cdot\sum_{r\in\mathcal{R}_{g}}|\overline{\mathcal{U}}_{r}|/\log_{2}\left(1+\gamma_{g,r}\right)}\right)$.

11:
$w_{r}\\!\leftarrow\\!w_{r}\\!+\\!|\overline{\mathcal{U}}_{r}|\\!\cdot\\!\beta\\!\cdot\\!\left(T_{M_{2}}\\!-\\!T_{m}\right)/\log_{2}\\!\left(1\\!+\\!\gamma_{g,r}\right)$,
$\forall r\\!\in\\!\mathcal{R}_{g}$.

12: $T_{r}\\!\leftarrow\\!w_{r}\log_{2}\left(1+\gamma_{g,r}\right)$, $\forall
r\in\mathcal{R}_{g}$.

13: $T_{r,u}\\!\leftarrow\\!T_{r,u}+\beta\cdot\left(T_{M_{2}}-T_{m}\right)$,
$\forall(r,u)\in\mathcal{L}_{m}$.

14: end while

15: $T_{r}\\!\leftarrow\\!\sum_{u\in\mathcal{U}_{r}}T_{r,u}$, $\forall
r\in\mathcal{R}_{g}$.

16: if
$\sum_{u\in\mathcal{U}_{g}}T_{u}+\sum_{r\in\mathcal{R}_{g}}T_{r}>\tau_{g}$
then

17: Apply Algorithm 2 to progressively decrease highest individual throughput
rates until
$\sum_{u\in\mathcal{U}_{g}}T_{u}+\sum_{r\in\mathcal{R}_{g}}T_{r}=\tau_{g}$.

18: end if

The way of increasing as much as possible the utility is by equally raising
the lowest values of $\\{T_{r,u}\\}_{u\in\mathcal{U}_{r}}$, $\forall
r\in\mathcal{R}_{g}$, as long as constraints are not violated. Then, let

$\displaystyle
T_{m}\\!=\\!\min\\!\left\\{T_{r,u}\\!\\!\,\mid\,\\!T_{r,u}\\!<\\!w_{u}\log_{2}\\!\left(1\\!+\\!\gamma_{r,u}\right),r\\!\in\\!\mathcal{R}_{g},u\\!\in\\!\mathcal{U}_{r}\\!\right\\}$
(11)

be the minimum throughput rate that has not reached the corresponding to the
Shannon capacity (note that if such a $T_{m}$ does not exist, we are done).
Let

$\displaystyle\mathcal{L}_{m}=\left\\{(r,u)\\!\in\\!\mathcal{R}_{g}\times\bigcup_{r\in\mathcal{R}_{g}}\nolimits\\!\\!\mathcal{U}_{r}\,\mid\,T_{r,u}=T_{m}\right\\}$
(12)

be the set of those relay–user links such that the link rate is the same as
the minimum $T_{m}$. Let

$\displaystyle
T_{M}=\min\left\\{T_{r,u}\,\mid\,T_{r,u}>T_{m},r\\!\in\\!\mathcal{R}_{g},u\\!\in\\!\mathcal{U}_{r}\right\\}$
(13)

be the minimum throughput rate among those rates that are not as the minimum
$T_{m}$ (cf. step 7). Let

$\displaystyle
T_{M_{2}}=\min\left(T_{M},\min_{(r,u)\in\mathcal{L}_{m}}\nolimits
w_{u}\log_{2}\left(1+\gamma_{r,u}\right)\right).$ (14)

The goal now is to increase $\\{T_{r,u}\\}_{(r,u)\in\mathcal{L}_{m}}$ as much
as possible not exceeding $T_{M_{2}}$, as long as those involved
$r\in\mathcal{R}_{g}$ can request more resources to increase $T_{r}$. Let
$\beta\in[0,1]$ be an undetermined parameter,
$\\{T_{r,u}\\}_{(r,u)\in\mathcal{L}_{m}}$ will be increased by
$\beta\\!\cdot\\!(T_{M_{2}}-T_{m})$, i.e., at most, by $T_{M_{2}}-T_{m}$ (cf.
step 13). Parameter $\beta$ will be defined later. Let

$\displaystyle\overline{\mathcal{U}}_{r}=\\{u\in\mathcal{U}_{r}\,\mid\,(r,u)\in\mathcal{L}_{m}\\},\quad\forall
r\in\mathcal{R}_{g}\normalsize.$ (15)

Now, we set $T_{r,u}^{{}^{\prime}}=T_{r,u}+\beta\\!\cdot\\!(T_{M_{2}}-T_{m})$,
$\forall(r,u)\in\mathcal{L}_{m}$ to increase the involved throughput rates.
Hence, we set $\forall r\\!\in\\!\mathcal{R}_{g}$:

$\displaystyle T_{r}\\!\\!$ $\displaystyle\\!\\!\\!\\!=\\!\\!\\!\\!$
$\displaystyle\\!\\!\\!\\!\sum\limits_{u\notin\overline{\mathcal{U}}_{r}}\\!\\!T_{r,u}\\!+\\!\\!\\!\sum\limits_{u\in\overline{\mathcal{U}}_{r}}\\!\\!T_{r,u}^{{}^{\prime}}\\!=\\!\\!\sum\limits_{u\notin\overline{\mathcal{U}}_{r}}\\!\\!T_{r,u}\\!\\!+\\!\\!\sum\limits_{u\in\overline{\mathcal{U}}_{r}}\\!\\!\\!\left(T_{r,u}\\!+\\!\beta(T_{M_{2}}\\!-\\!T_{m})\right)\\!=$
(16) $\displaystyle\\!\\!\\!=\\!\\!\\!\\!$
$\displaystyle\\!\\!\sum_{u\notin\overline{\mathcal{U}}_{r}}\nolimits\\!\\!T_{r,u}\\!+\\!\sum_{u\in\overline{\mathcal{U}}_{r}}\nolimits\\!T_{r,u}+|\overline{\mathcal{U}}_{r}|\beta\\!\cdot\\!(T_{M_{2}}\\!-\\!T_{m}).$

Hence, in step 11 we set $\forall r\in\mathcal{R}_{g}$:

$\displaystyle w_{r}^{new}$ $\displaystyle\\!\\!\\!\\!=\\!\\!\\!\\!$
$\displaystyle\frac{T_{r}}{\log_{2}\\!\left(1\\!+\\!\gamma_{g,r}\\!\right)}=\frac{\sum_{u\in\mathcal{U}_{r}}\\!\\!T_{r,u}\\!+\\!|\overline{\mathcal{U}}_{r}|\beta\\!\cdot\\!(\\!T_{M_{2}}\\!\\!-\\!T_{m}\\!)}{\log_{2}\\!\left(1\\!+\\!\gamma_{g,r}\\!\right)}=$
(17) $\displaystyle\\!\\!\\!\\!=\\!\\!\\!\\!$ $\displaystyle
w_{r}+|\overline{\mathcal{U}}_{r}|\beta\\!\cdot\\!(T_{M_{2}}\\!-\\!T_{m})/\log_{2}\left(1+\gamma_{g,r}\right).$

The aggregation of the new relay resource allocation has to be lower than the
total bandwidth, i.e.,

$\displaystyle\\!\\!\\!\\!\\!\\!\\!\\!\\!\sum_{r\\!\in\\!\mathcal{R}_{g}}\nolimits\\!\\!\\!\\!w_{r}^{n\\!e\\!w}\\!\\!\\!$
$\displaystyle\\!\\!\\!\\!=\\!\\!\\!\\!$
$\displaystyle\\!\\!\\!\sum_{r\in\mathcal{R}_{g}}\nolimits\\!\\!\left(w_{r}+\frac{|\overline{\mathcal{U}}_{r}|\beta\\!\cdot\\!(T_{M_{2}}-T_{m})}{\log_{2}\left(1+\gamma_{g,r}\right)}\right)=$
(18) $\displaystyle\\!\\!\\!\\!=\\!\\!\\!\\!$
$\displaystyle\\!\\!\\!\sum_{r\in\mathcal{R}_{g}}\nolimits\\!\\!\\!\\!w_{r}\\!+\\!\beta(T_{M_{2}}\\!\\!-\\!\\!T_{m})\\!\\!\sum_{r\\!\in\\!\mathcal{R}_{g}}\nolimits\\!\\!\\!\\!|\overline{\mathcal{U}}_{r}|/\\!\log_{2}\\!\\!\left(1\\!\\!+\\!\\!\gamma_{g,r}\\!\right)$

has to be lower or equal than $W_{\\!\text{relays}}^{g}$. Hence, isolating
$\beta$ we get that necessarily:

$\displaystyle\beta\leq\frac{W_{\\!\text{relays}}^{g}-\sum_{r\in\mathcal{R}_{g}}w_{r}}{(T_{M_{2}}-T_{m})\sum_{r\in\mathcal{R}_{g}}|\overline{\mathcal{U}}_{r}|/\log_{2}\left(1+\gamma_{g,r}\right)}.$
(19)

Hence, in step 10 we have defined $\beta$ as:

$\displaystyle\beta=\min\left(1,\frac{W_{\\!\text{relays}}^{g}-\sum_{r\in\mathcal{R}_{g}}w_{r}}{(T_{M_{2}}-T_{m})\sum_{r\in\mathcal{R}_{g}}|\overline{\mathcal{U}}_{r}|/\log_{2}\left(1+\gamma_{g,r}\right)}\right)\\!.$
(20)

Once the parameter $\beta$ is derived, we assign $w_{r}=w_{r}^{new}$ and
$T_{r}=w_{r}\log_{2}\left(1+\gamma_{g,r}\right)$, $\forall
r\in\mathcal{R}_{g}$ (cf. step 12). In case that $\beta=1$ (cf. step 4), we
repeat the process defining $T_{m}$ again and increasing the corresponding
throughput rates.

To finalize the allocation and guarantee an exact and feasible solution, we
need to check if the $\tau_{g}$–constraint holds. If not (cf. step 16), then
we reduce the highest individual rates $T_{u}$, $\\!\forall
u\\!\in\\!\mathcal{U}_{g}\\!\cup\\!\bigcup_{r\in\mathcal{R}_{g}}\nolimits\\!\mathcal{U}_{r}$
until
$\sum_{u\in\mathcal{U}_{g}}\\!T_{u}\\!+\\!\sum_{r\in\mathcal{R}_{g}}\\!\sum_{u\in\mathcal{U}_{r}}\\!T_{u}\\!=\\!\tau_{g}$,
by means of using Algorithm 2 with $\tau\\!=\\!\tau_{g}$ (cf. step 17).

###  IV-C Linear complexity of the exact resource allocation

As it has been mentioned in the Introduction, the exact $\max$–$\min$ resource
allocation provided by Algorithm 3 has a linear complexity in the number of
the operations with respect to the number of mobile users and the number of
relays (i.e.,
$\mathcal{O}\left(|\mathcal{U}_{g}\bigcup\mathcal{U}_{g}^{*}|\cdot|\mathcal{R}_{g}|\right)$,
for each $g\\!N\\!B$ $g$). Here, we provide a general overview of that result
(additional details can be found in the Appendix A).

First, let’s assume, without loss of generality, that the unit Shannon
capacity of mobile users (i.e., $\\{\log(1\\!+\\!\gamma_{s,u})\\}$) are sorted
in increasing order. Algorithm 1 is run initially as a subroutine and is
linear with respect to the number of considered mobile users (i.e,
$|\mathcal{U}|$). That happens since the number of its loop iterations is at
most the number of mobile users. In addition, the summations within its loop
can be easily rearranged to be derived incrementally (with only an additional
operation that modifies the results of the previous iteration at each new
iteration), while deriving minimum values is immediate due to sorting.
Algorithm 2 is run as well as a subroutine and is also linear because it has
no loops and there are just a few sums over the number of mobile users.

Now, let us focus on Algorithm 3. It can be seen that the while loop will
have, at most, as many iterations as the number of relay-served mobile users.
That happens because the while loop stops when $\beta\\!<\\!1$. However, that
only happens when there are not enough resources to increase the resources for
links gathered in $\mathcal{L}_{m}$ (which grows, at least, by one link at
each iteration). Then, within the loop, we compute sums over the number of
relays (i.e., $|\mathcal{R}_{g}|$).

Hence, the overall complexity of Algorithm 3 is of the order of
$\mathcal{O}\\!\left(|\mathcal{U}_{g}\bigcup\mathcal{U}_{g}^{*}|\\!\cdot\\!|\mathcal{R}_{g}|\right)$,
in the worst case.

###  IV-D A numerical performance illustration

Here, we provide an illustrative case that shows how our algorithms allocate
resources. The network is formed by one $g\\!N\\!B$ and two relays. The
$g\\!N\\!B$ and the relays serve three mobile users each. Moreover, we dispose
of different SINR values for each component of the network, and a wired
backhaul capacity $\tau_{g}$ of $20$ Mbps.

Algorithm 3 provides the values to be assigned to each mobile user or relay
$y$ (i.e., $w_{y}$ and $T_{y}$). Table II summarizes both the network
parameters as well as the obtained results. As we have shown in the previous
sections, such values are optimal in terms of $\max$–$\min$ fairness.

It can be seen that UE $7$ is the mobile user with lowest SINR value. The
$\max$–$\min$ throughput for mobile users attached to Relay $2$ is achieved
with rates of $2.021$ Mbps, which coincides with their Shannon capacity. On
another hand, Relay $1$ attains enough resources to serve its users (as its
Shannon capacity in the wireless backhaul exceeds the demand), yet its rates
have been reduced since the aggregated user rates exceeded the capacity
bottleneck $\tau_{g}$. The same happens with the $g\\!N\\!B$.

Table II: Resulting exact resource allocation. Rx |  Served by |  SINR [dB] |  $w_{y}$ [MHz] |  $T_{y}$ [Mbps] |  Shannon Capacity [Mbps]
---|---|---|---|---|---
UE 1 |  $g\\!N\\!B$ |  39.23 |  0.2378 |  2.322 |  3.099
UE 2 |  $g\\!N\\!B$ |  37.89 |  0.2461 |  2.322 |  3.099
UE 3 |  $g\\!N\\!B$ |  18.01 |  0.5160 |  2.322 |  3.099
UE 4 |  Relay 1 |  18.93 |  0.4333 |  2.322 |  2.734
UE 5 |  Relay 1 |  28.67 |  0.2870 |  2.322 |  2.734
UE 6 |  Relay 1 |  29.43 |  0.2796 |  2.322 |  2.734
UE 7 |  Relay 2 |  10.42 |  0.5631 |  2.021 |  2.021
UE 8 |  Relay 2 |  22.57 |  0.2692 |  2.021 |  2.021
UE 9 |  Relay 2 |  36.30 |  0.1675 |  2.021 |  2.021
Relay 1 |  $g\\!N\\!B$ |  78.27 |  0.7748 |  6.968 |  20.147
Relay 2 |  $g\\!N\\!B$ |  81.05 |  0.2251 |  6.063 |  6.063

##  V Conclusions

We have solved the optimal allocation of resources in wireless relay-enabled
heterogeneous networks under the condition of being $\max$–$\min$ fair. With
the exact $\max$–$\min$ allocation algorithm we have shown that the optimal
distribution of resources can be found in linear time on the number of mobile
users and relays, which is a key enabler for implementation over cellular
networks. Considering backhaul bottlenecks is crucial to assign resources to
mobile users of one side of the network depending on the allocation to other
relays and users.

## References

  * [1] Y. Xu, G. Gui, H. Gacanin, and F. Adachi, “A survey on resource allocation for 5G heterogeneous networks: Current research, future trends, and challenges,” _IEEE Communications Surveys and Tutorials_ , vol. 23, no. 2, pp. 668–695, 2021.
  * [2] Y. Guo, S. Yin, and J. Hao, “Resource allocation and 3-D trajectory design in wireless networks assisted by rechargeable UAV,” _IEEE Wireless Communications Letters_ , vol. 8, no. 3, pp. 781–784, 2019.
  * [3] D. Zhai, H. Li, X. Tang, R. Zhang, Z. Ding, and F. R. Yu, “Height optimization and resource allocation for NOMA enhanced UAV-aided relay networks,” _IEEE Transactions on Communications_ , vol. 69, no. 2, pp. 962–975, 2021\.
  * [4] N. S. Moayedian, S. Salehi, and M. Khabbazian, “Fair resource allocation in cooperative cognitive radio IOT networks,” _IEEE Access_ , vol. 8, pp. 191 067–191 079, 2020.
  * [5] O. Elgendy, M. Ismail, and K. Elsayed, “Radio resource management for LTE-A relay-enhanced cells with spatial reuse and max-min fairness,” _Telecommunication Systems_ , vol. 68, no. 4, pp. 643–655, 2018.
  * [6] 3GPP, “Evolved universal terrestrial radio access (E-UTRA); user equipment (UE) radio transmission and reception,” accessed: 2023-06-21.
  * [7] Y. Liu, _Introduction to OFDM receiver design and simulation_. Artech House, 2019.
  * [8] Y. Nesterov and A. Nemirovskii, _Interior-point polynomial algorithms in convex programming_. Siam, 1994, vol. 13.
  * [9] S. Bubeck _et al._ , “Convex optimization: Algorithms and complexity,” _Foundations and Trends® in Machine Learning_ , vol. 8, no. 3-4, pp. 231–357, 2015.
  * [10] H. Kuhn and A. Tucker, “Nonlinear programming,” in _Traces and Emergence of Nonlinear Programming_. Springer, 2014, pp. 247–258.

##  Appendix A Linear Complexity of the Exact Resource Allocation of Algorithm
3

The exact $\max$–$\min$ resource allocation provided by Algorithm 3 has a
linear complexity in the number of the operations with respect to the number
of mobile users and the number of relays (i.e.,
$\mathcal{O}\\!\left(|\mathcal{U}_{g}\bigcup\mathcal{U}_{g}^{*}|\cdot|\mathcal{R}_{g}|\right)$,
for each $g$). Here, we provide the details of that result.

As Algorithm 3 runs Algorithms 1 and 2 as subroutines, we analyze the
complexity of both algorithms first and integrate their complexity later to
the full complexity of Algorithm 3.

###  A-A Algorithm 1: Resource allocation of one BS without relays

The complexity of Algorithm 1 is tricky because, apparently, it could seem
that it has a quadratic complexity. However, we show that, instead, it has a
linear complexity of $\mathcal{O}\\!\left(|\mathcal{U}|\right)$.

Basically, on the one hand, the number of loop iterations is, at most, the
number of users. On the other hand, the sums within the loop can be easily
rearranged to be derived with a fixed number of operations, based on what has
been computed in the previous iteration. Also, it can be assumed, without loss
of generality, that the unit Shannon capacities of users (i.e.,
$\\{\log(1\\!+\\!\gamma_{s,u})\\}$) are sorted in increasing order, so that
deriving minimums becomes immediate due to sorting.

More formally, we analyze Algorithm 1 step by step and show that it has indeed
a linear complexity of $\mathcal{O}\\!\left(|\mathcal{U}|\right)$.

First, in step 1 we can assume, without loss of generality, that the unit
Shannon capacities of the input users (i.e.,
$\\{\log(1\\!+\\!\gamma_{s,u})\\}$) are sorted in increasing order. That is
because any BS running Algorithm 1 receives the CSI of each user and can sort
the SINRs $\gamma_{s,u}$ along. Next, in step 2 we compute the set
$\mathcal{J}$ for the first time as those users with minimum rate.

Now, the while loop has, at most, as many iterations as the number of mobile
users, since the loop iterates while the set $\mathcal{J}$ still has users to
gather. But, in step 10, we see that $\mathcal{J}$ gets exactly one user per
iteration, although only when $K=1$. But $K$ is equal to $1$ only when the
condition of step 6 holds, which is equivalent to the condition of the while
loop. Hence, if $K=0$, the loop stops.

From the next step on we see that, apparently, at each iteration the algorithm
must compute some sums over a set of users. However, those sums can be easily
rearranged to be derived with a fixed number of operations, on top of the sums
computed in the previous iteration. To see that, we will need to know, given
some set $\mathcal{J}$, the value $S_{|\mathcal{J}|}$, defined as:

$S_{|\mathcal{J}|}=\sum_{u\in\mathcal{J}}\nolimits\frac{1}{\log_{2}(1+\gamma_{s,u})}.$
(21)

To compute $S_{|\mathcal{J}|}$, we note that there are only $|\mathcal{U}|$
possible sets $\mathcal{J}$ in the execution of Algorithm 1. Indeed, set
$\mathcal{J}$ is composed by those users with minimum rate and then the
algorithm adds exactly one user per iteration to $\mathcal{J}$, which is to
the next user with minimum rate (cf. step 4). Since rates $T_{u}$ are not
modified until they are included in $\mathcal{J}$, we can know before the
while loop what are the $|\mathcal{U}|$ possible sets $\mathcal{J}$, all with
different cardinalities, that Algorithm 1 could use.

Concretely, if we first consider the smallest possible set $\mathcal{J}$ with
one user, we can compute $S_{|\mathcal{J}|}$ as:

$\displaystyle S_{1}=\frac{1}{\log_{2}(1+\gamma_{s,1})}.$ (22)

Now, if instead we consider some possible set $\mathcal{J}$ with more than one
user, it can be readily seen, from Eq. (21), that:

$\displaystyle
S_{|\mathcal{J}|}=S_{|\mathcal{J}|-1}+\frac{1}{\log_{2}(1+\gamma_{s,|\mathcal{J}|})}.$
(23)

Hence, to compute $S_{|\mathcal{J}|}$, we only need the sum of the previous
term $S_{|\mathcal{J}|-1}$ with the term
$\frac{1}{\log_{2}(1+\gamma_{s,|\mathcal{J}|})}$. Since there are, at most,
$|\mathcal{U}|$ possible sets $\mathcal{J}$, we can compute all possible
values of $S_{|\mathcal{J}|}$ with only $|\mathcal{U}|$ sums, before running
the loop.

Now, we can see that within the while loop we need to know the value of
$\sum_{u\in\mathcal{U}}w_{u}$, which depends on the new $w_{u}$ values that
have been derived at the end of the previous iteration in step 9. But that sum
is equal to:

$\displaystyle\sum_{u\in\mathcal{U}}\nolimits
w_{u}=\sum_{u\in\mathcal{J}}\nolimits w_{u}+\sum_{u\notin\mathcal{J}}\nolimits
w_{u}.$ (24)

Now, we can see that, on the one side, users in $\mathcal{J}$ have been
computed in the previous iteration as $w_{u}\leftarrow w_{u}^{old}+k_{u}$ in
step 9 and, checking the value assigned to $k_{u}$ in step 5, we have that, in
reality, $w_{u}=T_{v_{0}}/\log_{2}(1+\gamma_{s,u})$, for those users
$u\in\mathcal{J}$. On the other side, the $w_{u}$ value of those users not
included in $\mathcal{J}$ is equal to $w_{u}=W^{\min}$, because those users
have not been selected yet to be included in $\mathcal{J}$. Hence:

$\displaystyle\\!\\!\\!\\!\\!\\!\\!\\!\sum_{u\in\mathcal{U}}\nolimits w_{u}$
$\displaystyle\\!\\!\\!=\\!\\!\\!$
$\displaystyle\sum_{u\in\mathcal{J}}\nolimits
w_{u}+\sum_{u\notin\mathcal{J}}\nolimits w_{u}=$ (25)
$\displaystyle\\!\\!\\!=\\!\\!\\!$ $\displaystyle
T_{v_{0}}\\!\sum_{u\in\mathcal{J}}\nolimits\frac{1}{\log_{2}(1\\!+\\!\gamma_{s,u})}\\!+\\!(|\mathcal{U}|\\!-\\!|\mathcal{J}|)W^{\min}.$
(26)

Now, we note that the only sum remaining in Eq. (26) is
$\sum_{u\in\mathcal{J}}\frac{1}{\log_{2}(1+\gamma_{s,u})}$, which is the value
of $S_{|\mathcal{J}|}$ computed in advance, before running the loop. Hence,
there is no need to do $|\mathcal{J}|$ sums, as $S_{|\mathcal{J}|}$ is already
known. Thus, computing $\sum_{u\in\mathcal{U}}w_{u}$ can be done with a fixed
number of operations.

Regarding step 4, we note that it incurs no cost because rates $T_{u}$ not
included in $\mathcal{J}$ are still sorted since step 1.

Then, we can rearrange step 5: Let’s define, for each $u\\!\in\\!\mathcal{J}$,
the variable $L_{u}$ (variable $L_{u}$ would be equivalent to
$L_{u}\\!=\\!(k_{u}\\!+\\!w_{u})\log_{2}(1\\!+\\!\gamma_{s,u})$) and change
step 5 by the following line:

$\displaystyle L_{u}\leftarrow T_{v_{0}},\quad\forall u\in\mathcal{J}.$ (27)

Now, step 5 is the same but with a change of variables. With that, we have
$|\mathcal{J}|$ variable assignments with no operations.

Regarding step 6, we need to check whether
$\sum_{u\in\mathcal{J}}k_{u}\\!+\\!\sum_{u\in\mathcal{U}}w_{u}\\!>\\!W_{\text{users}}$.
Thus, since we know that here
$k_{u}\\!=\\!T_{v_{0}}/\log_{2}(1\\!+\\!\gamma_{s,u})-w_{u}$, then:

$\displaystyle\sum_{u\in\mathcal{J}}k_{u}\\!+\\!\sum_{u\in\mathcal{U}}w_{u}=\sum_{u\in\mathcal{J}}\\!\\!\left(\\!\frac{T_{v_{0}}}{\log_{2}(1\\!+\\!\gamma_{s,u})}\\!-\\!w_{u}\\!\\!\right)\\!+\\!\sum_{u\in\mathcal{U}}\\!w_{u}\\!=$
(28) $\displaystyle=\\!\\!\\!\\!\\!$ $\displaystyle
T_{v_{0}}\sum_{u\in\mathcal{J}}\nolimits\frac{1}{\log_{2}(1\\!+\\!\gamma_{s,u})}-\sum_{u\in\mathcal{J}}\nolimits
w_{u}+\sum_{u\in\mathcal{U}}\nolimits w_{u}\\!=$ (29)
$\displaystyle=\\!\\!\\!\\!\\!$ $\displaystyle
T_{v_{0}}\sum_{u\in\mathcal{J}}\nolimits\frac{1}{\log_{2}(1\\!+\\!\gamma_{s,u})}+\sum_{u\notin\mathcal{J}}\nolimits
w_{u}\\!=$ (30) $\displaystyle=\\!\\!\\!\\!\\!$ $\displaystyle
T_{v_{0}}\sum_{u\in\mathcal{J}}\nolimits\frac{1}{\log_{2}(1\\!+\\!\gamma_{s,u})}+\sum_{u\notin\mathcal{J}}\nolimits
W^{\min}\\!=$ (31) $\displaystyle=\\!\\!\\!\\!\\!$ $\displaystyle
T_{v_{0}}\sum_{u\in\mathcal{J}}\nolimits\frac{1}{\log_{2}(1\\!+\\!\gamma_{s,u})}+(|\mathcal{U}|-|\mathcal{J}|)W^{\min}.$
(32)

So, we see that the sum over the users in $\mathcal{J}$ that appears in Eq.
(32) is, indeed, the value $S_{|\mathcal{J}|}$ computed in advance, so that it
needs no extra operations.

For step 7 we can simply observe that this step will be run, at most, once.
That is because if we get to this step, that means that the condition of step
6 holds, which in turn means that the condition of the while loop in step 3
does not hold anymore and the algorithm stops.

Step 9 can be avoided and leave the final assignment of those values $w_{u}$
and $T_{u}$ for when the while loop has finished. The important thing here is,
according to how we have rearranged some steps, how the new variable $L_{u}$
varies at each iteration. Indeed, in order to derive $w_{u}$ and $T_{u}$ of
users in $\mathcal{J}$ once the while loop has finished (since $w_{u}$ and
$T_{u}$ of users not in $\mathcal{J}$ have not changed), we can simply set:

$w_{u}=\frac{L_{u}}{\log_{2}(1+\gamma_{s,u})},\text{ and
}T_{u}=L_{u},\quad\forall u\\!\in\\!\mathcal{J}.$ (33)

As a result, Algorithm 1 does have a linear complexity with respecto to the
number of users $|\mathcal{U}|$, i.e.,
$\mathcal{O}\left(|\mathcal{U}|\right)$.

###  A-B Algorithm 2: $\max$–$\min$ throughput reduction

Algorithm 2 is clearly linear with respect to the number of mobile users
$|\mathcal{U}|$ because there are no loops and there are just a couple of sums
over the number of mobile users. Moreover, deriving the minimum of step 4
would take at most $|\mathcal{U}|$ comparisons, even ignoring that rates could
be sorted.

As a result, Algorithm 2 has a linear complexity of
$\mathcal{O}\\!\left(|\mathcal{U}|\right)$.

###  A-C Overall complexity of Algorithm 3: The exact $\max$–$\min$ resource
allocation

Now, let us focus on Algorithm 3. Initially, Algorithm 1 is run as a
subroutine once for the $g\\!N\\!B$ $g$ and then for each relay $r$ in
$\mathcal{R}_{g}$. Since we have seen that Algorithm 1 has linear complexity
with respect to the number of users, at this point we already have a
complexity of at most
$\mathcal{O}\\!\left(|\mathcal{U}_{g}\bigcup\mathcal{U}_{g}^{*}|\\!\cdot\\!|\mathcal{R}_{g}|\right)$.

After that, basically, it can be seen that the while loop will have, at most,
as many iterations as the number of relay-served users. That happens because
the while loop stops when $\beta\\!<\\!1$. However, that only happens when
there are not enough resources to increase the resources for links gathered in
$\mathcal{L}_{m}$ (which grows, at least, by one link at each iteration).
Then, within the loop, we compute either a fixed number of sums over the
number of relays in $\mathcal{R}_{g}$ or a fixed number of operations for each
relay in $\mathcal{R}_{g}$. Hence, the overall complexity of Algorithm 3 is of
the order of
$\mathcal{O}\\!\left(|\mathcal{U}_{g}\bigcup\mathcal{U}_{g}^{*}|\\!\cdot\\!|\mathcal{R}_{g}|\right)$,
in the worst case.

More formally, let’s see that the number of iterations of Algorithm 3 is lower
than the number of users so that the overall complexity is linear with
respecto to both, the number of users and the number of relays.

Clearly, the while loop ends when $\beta<1$. The goal of that loop is to take
always the lowest rate $T_{m}=T_{r,u}$ and rise that rate as much as possible.
In the case that there were more users with the same minimum rate, the
algorithm rises them all simultaneously, in order to be $\max$–$\min$ fair.
Such users are the ones of the access links contained in the set
$\mathcal{L}_{m}$. Now, the algorithm rises all their rates up to the next
lowest rate (but higher than their own rate), $T_{M}$, taking into account
that in the case that the Shannon capacity of some user would not be enough to
reach $T_{M}$, then the algorithm would rise the rates up to the lowest
Shannon capacity of that user, i.e., $T_{M_{2}}$. Once it is not possible to
reach $T_{M_{2}}$, the algorithm should stop because there would be minimum
rates that could not be risen any more so that the state would already be
$\max$–$\min$ fair.

For those chosen minimum rates $T_{r,u}$ (all with value equal to $T_{m}$)
that have to be risen up to, if possible, $T_{M_{2}}$, we would need to add up
the amount of $(T_{M_{2}}-T_{m})$, since $T_{m}+(T_{M_{2}}-T_{m})=T_{M_{2}}$.
But it is important to notice that we would be rising the rates without having
into account whether the backhaul link of relay $r$ has still the possibility
to take resources that have not been assigned yet. Hence, we do not rise the
rates by $(T_{M_{2}}-T_{m})$ but by $\beta(T_{M_{2}}-T_{m})$ instead, where
$0\leq\beta\leq 1$. Then, the value $\beta$ is computed in Eqs. (16)–(20) in
order to make sure that the amount of assigned backhaul resources is not
higher than the actual amount of available backhaul resources of relays.
Hence, in the case that there are indeed enough available backhaul resources
for relays, $\beta$ will be equal to $1$ and the while loop will keep
iterating. Otherwise, having $\beta<1$ will mean that there were not enough
backhaul resources available to rise the rates as much as planned, i.e., value
$T_{M_{2}}$ will not be reached by the risen rates, and the $\max$–$\min$
state will have been reached and the while loop will end.

Therefore, as within the while loop the algorithm always takes all users with
minimum rate at the beginning of each iteration, in the set $\mathcal{L}_{m}$
the we accumulate those access links of the users with lowest rate. Then, that
set contains always the same links and, at each iteration, it adds at least
one link from one new user. Thus, there will be, at most, as many iterations
as the number of relay-served users, $|\mathcal{U}_{g}^{*}|$.

Now, within the while loop the number of operations are as follows. The
computation of the minimums are immediate if rates are sorted in advance in a
sub-quadratic number of comparisons, which are much faster compared to actual
operations. Hence, what matters is that in step 10 the algorithm computes a
couple of sums over the number of relays, i.e., $|\mathcal{R}_{g}|$, and then
a fixed number of operations, in order to compute the value to be assigned to
$\beta$. Then, in steps 11 and 12 a fixed number of operations is computed for
each relay in $\mathcal{R}_{g}$. Next in step 13, the assigned value to each
$T_{r,u}$ is the same for all those links in $\mathcal{L}_{m}$, so that the
fixed number of operations of that step are computed only once, and then
assigned to each link.

Finally, once the while loop ends, we compute in steps 15 and 16 some sums
over the number of mobile users or the number of relays, which need as many
sums as either the number of mobile users or the number of relays. Next,
Algorithm 2 is maybe applied, which we already know that has linear
complexity.

As a result, integrating the complexity of the subroutines of Algorithms 1 and
2, the overall complexity of Algorithm 3 is linear with respect to both, the
number of mobile users and the number of relays, i.e.,
$\mathcal{O}\\!\left(|\mathcal{U}_{g}\bigcup\mathcal{U}_{g}^{*}|\cdot|\mathcal{R}_{g}|\right)$.