# <center><i class="fa fa-edit"></i>Relaxed & Original SRA Problem</center>
###### tags: `Internship`
:::success
The study objectives were to:
- Obtain in-depth knowledge on Relaxed & Original SAR problems
- Find out the most appropriate algorithm solution for each problem
:::
:::spoiler Click to view the preliminary knowledge about the problems, you can skip this if you already understand
### The Optimization Problem
The SRA problem consists of two tasks: (i) split the bandwidth into one or multiple RUs and (ii) allocate the RUs to users (SU-MIMO) or user groups (MU-MIMO). The constraints are:
- 1. A user or user group can only be assigned with no more than one RU.
- 2. MU-MIMO transmission only applies to RUs larger than 106 subcarriers, in other words, $l≤L−3$.
- 3. The number of users allocated on $RU(l,i)$ is between 1 and $M(l)$.

$M(l)$ is the maximum number of users allowed on $RU(l,i)$ and it is a function of $l$. If the AP transmits in joint $MU-MIMO$ and $OFDMA$ mode and $l≤L−3$, $RU(l,i)$ can be used for $MU-MIMO$ and $M(l)=⌊N_T/N_R⌋$, otherwise $RU(l,i)$ is used for $SU-MIMO$ and $M(l)=1$. With all the above constrains, the SRA of 802.11ax can be formed as an optimization problem

\begin{align*} & \max\limits_{g\in \mathcal{G}}R_{ZFBF}(g)\\ st&\quad 0\leq\sum\limits_{j} c_{j,k}\leq 1\tag{1}\\ & 1 \leq\sum\limits_{k}c_{j,k}\leq M(l_{j})\\ & c_{j,k}\in\{0,1\},\end{align*}

where $c_j,k$ indicates if user k is allocated on the $j_{th}$ $RU$, and $G$ is the set of all valid user schedules.

### The Relaxed SRA Problem
Constraint 1) makes the SRA problem complicated since it requires taking into consideration all users scheduled on each RU. Now consider the problem which relaxes Constraint 1), i.e., a user or user group can be assigned with multiple RUs and the first constraint in Problem is gone. Now, the SRA on different RUs can be solved independently.

### The Original SRA Problem
The original SRA problem with Constraint 1) can not be solved by the divide and conquer algorithm, since the subproblems are solved independently on the user set U, thus when the user schedules of the subproblems are merged, it is possible that a user shows up on multiple RUs. The original problem can of course be solved by exhaustive search (for small scale scenarios) and by a greedy algorithm (leading to suboptimal solutions).
:::
# Module 1: Scheduling Algorithms
## A. The Relaxed Scheduling and Resource Allocation Problem
We can use the subcarriers as a single RU $RU(l,i)$ and allocate some users to $RU(l,i)$, otherwise, we need to split the subcarriers into multiple RUs at higher levels and allocate users to each of them. After we split the subcarriers of $RU(l, i)$ into one or multiple RUs, we can select optimal user groups for each RU independently, since the relaxed SRA problem does not require Constraint 1). Note that we need to make sure the subcarriers are split optimally and the user grouping on each RU is also optimal.


$Figure\ 6$

- Illustration above is shown a divide step:
- The subcarriers of $RU(l, i)$ are first split into two RUs $RU(l+1,2i)$ and $RU(l+1,2i+1)$.
- Each of these two RUs can be further split.
- The SRA problem on $RU(l, i)$ becomes two subproblems on $RU(l+1,2i)$ and $RU(l+1,2i+1)$ which can be solved independently.

> Let the optimal user schedules on $RU(l+1,2i)$ and $RU(l+1,2i+1)$ be $g_{opt}(l+1,2i)$ and $g_{opt}(l+1,2i+1)$ respectively, irrespectively of whether they are used as a single RU or split into multiple RUs.

- In merge step, we can conclude:
- $gopt(l+1,2i)$ and $gopt(l+1,2i+1)$ can be merged into a user schedule on $RU(l,i)$.
- Denote this user schedule as $g_m(l,i)$, where the subscript $m$ means there are multiple RUs in this user schedule.
- For a single RU $RU(l,i)$ all the subcarriers $s∈RU(l,i)$ are allocated to a single user or user group.

> Note that there is another optimal user schedule candidate on $RU(l,i)$, which uses all the subcarriers of $RU(l,i)$ as a single RU. Let the optimal user schedule in this case be denoted by $g_{s}(l,i)$, where the subscript s means there is only one RU in this user schedule.

At this point, we have two user schedule candidates $gs(l,i)$ and $gm(l,i)$ for $RU(l,i)$. The optimal user schedule on $RU(l,i)$ is
\begin{equation*} g_{opt}(l, i)= \mathop{\text{arg max}}_{g\in\{g_{s}(l,i),g_{m}(l,i)\}}(R_{ZFBF}(g)). \tag{2} \end{equation*}

>The optimal user schedule of the relaxed problem is $g_{opt}=g_{opt}(0,0)$.

$Table\ 2\ :$ Notation Glossary

### Algorithm 1 Divide-and-Conquer $(U,l,i)$

#### Lemma 1
> The optimal user schedule of the relaxed SRA problem can be obtained by the divide and conquer algorithm.

#### Proof
- If L=1, the lemma is obviously true.
- Lemma 1 is also true for L+1.
- Suppose there is another user schedule g′ which is different from gopt obtained by the divide and conquer algorithm and $RZFBF(g′)>RZFBF(g_{opt})$.
- If g′ consists of only one RU, then its sum rate is larger than $RZFBF(gs(0,0))$, which contradicts the fact that $gs(0,0)$ is the optimal user group on $RU(0,0)$.
- If g′ consists of multiple RUs, its sum rate is $RZFBF(g′(1,0))+RZFBF(g′(1,1))$ and $RZFBF(g′(1,0))+RZFBF(g′(1,1))>RZFBF(g_{m}(1,0))+RZFBF(g_{m}(1,1))$, which contradicts the fact that $g_{m}(1,0)$ and $g_{m}(1,1)$ are optimal user schedules on $RU(1,0)$ and $RU(1,1)$ respectively.

#### Lemma 2
> The sum rate of the optimal user schedule of the relaxed SRA problem is an upper bound for the original SRA problem.

#### Proof
The optimal user schedule of the original SRA problem satisfies all the constraints of the relaxed SRA problem and thus is also a feasible solution of the relaxed SRA problem, the sum rate of the optimal user schedule of the relaxed SRA problem is no less than the sum rate of the optimal user schedule of the original SRA problem.

## B. The Original Scheduling and Resource Allocation Problem
### 1) Exhaustive Search
The exhaustive search traverses all the possible user schedules to search the optimal solution. It guarantees to find the optimal user schedule, but it is impractical in WiFi networks due to its time complexity. To get the size of the search space, consider the number of user schedules $τ(n,l)$ which allocates exactly n users to the subcarriers of a RU at level $l$.
#### Case 1
All the subcarriers make up a single RU.So the number of possible user schedules in this case is
\begin{equation*} \tau_{s}(n, l)=\begin{cases} 1& n\leq M(l)\\ 0& \mathrm{otherwise} \end{cases}. \tag{3} \end{equation*}
#### Case 2
The subcarriers are split into multiple RUs. The number of possible user schedules in this case is
\begin{equation*} \tau_{m}(n, l)=\begin{cases} \sum\limits_{k=1}^{n-1}\begin{pmatrix}n\\ k\end{pmatrix}\tau(k, l+1)\tau(n-k, l+1) & l < L-1\\ 0 & \mathrm{otherwise}\end{cases}.\tag{4}\end{equation*}
> Note that $τ(n,l)=τ_{s}(n,l)+τ_{m}(n,l)$ and τ(1,l)=1, and, using Equations (3) and (4), τ(n, l) can be calculated recursively.


$Figure\ 7$
- The time complexity of exhaustive search is shown in illustration above:
- The number of user schedules as a function of N and L.
- The size of the search space increases very fast as N and L increase.
- Clearly the exhaustive search is computational too expensive and thus impractical for real world 802.11ax networks.

### 2) Greedy Algorithm
- First selects a level l to operate at and then splits the whole bandwidth such that the partition p consists of RUs of equal size.
- The level l is chosen such that each RU can be assigned with at least one user/user group.
- Given a total number of $N$ users with say $N_R$=1 antenna each, if every RU were to be assigned with the maximum possible number of users $N_T$ (forming a maximum size user group), then we could assign users to $N/N_T$ RUs.
> $l=min(L−1,⌊log_2(N)⌋)$ for OFDMA mode or $ol=min(L−3,⌊log_2(N⋅N_R/N_T)⌋)$ for joint MU-MIMO and OFDMA mode.

## C. Recursive Scheduling
In order to satisfy Constraint 1), recursive scheduling excludes the users of $g_{opt}(l+1,2i)$ from the user set when solving $g_{opt}(l+1,2i+1)$ and vice versa.

### Algorithm 2 Recursive-Scheduling $(U,l,i)$
- The basic operation of recursive scheduling is user selection.
- Recursive scheduling on an RU calls recursive scheduling 4 times and user selection once at level l<L−1, and calls user selection once at level L−1.
- The number of user selection operations, ϕ, is a function of l and equals
\begin{equation*} \phi(l)=\begin{cases} 4\phi(l+1)+1 & l < L-1\\ 1 & l=L-1 \end{cases}. \tag{5} \end{equation*}

# Simulations
Consider downlink MU transmissions in a single 802.11ax basic service set (BSS) in a 50m×50m office area with central frequency of 5GHz, where the wireless channel can be modeled with the WINNER II model. According to WINNER II, the path loss is given as
\begin{equation*} PL=A\log_{10}(d[m])+B+C\log_{10}(f_{c}[GHz]/5.0)+X, \tag{12} \end{equation*}
| Variable | Meaning |
| -------- | -------- |
| $d$ | distance between the user |
| $AP, A,B,C\ and\ X$ | parameters related with scenarios |


$Figure\ 8:$ The topology of the 802.11ax BSS

## A. Divide and Conquer Versus Exhaustive Search
The divide and conquer algorithm is compared with exhaustive search to evaluate the tightness of the upper bound.


$Figure\ 9:$ The gap between exhaustive search and divide and conquer

- Figure 9 shows that:
- The sum rate of divide and conquer is slightly higher than exhaustive search, which is expected since it allows assigning multiple RUs to a user while exhaustive search does not.
- The gap between the sum rate of exhaustive search and divide and conquer is very small.
- The sum rate achieved by the divide and conquer algorithm is a tight upper bound of the optimal user schedule

## B. Comparison Between Divide and Conquer, Greedy, and Recursive Scheduling

$Figure\ 10:$ Comparison of the sum rate between different algorithms

- Figure 10 shows that:
- The sum rate of recursive scheduling is very close to divide and conquer, which means it is also close to the optimal user schedule achieved by exhaustive search.

## C. Impact of Different Type of Users

$Figure\ 11:$ Impact of different type of users

- Figure 11 shows that:
- The sum rate of the greedy algorithm is, as expected, lower than that of the other two algorithms.
- The gap is larger when there are a few users with small path loss (first group).
- This is because the greedy algorithm allocates a smaller portion of the RUs to them in comparison to what the recursive scheduling and divide and conquer algorithm do.
> As before, divide and conquer and recursive scheduling have very similar performance.

## D. Impact of the Number of Users

$Figure\ 12:$ Impact of number of users

- Figure 12 shows that:
- The sum rate increases as N increases since there are more users which are close to the AP.
- The greedy algorithm has lower sum rate and the sum rate of the recursive scheduling is very close to the divide and conquer.

## E. Impact of the Number of Antennas at the AP

$Figure\ 13:$ Impact of number of antennas

- Figure 13 shows that:
- The sum rate increases as $N_T$ increases, since there are more spatial streams in each MU-MIMO group.
- The sum rate of recursive scheduling is close to that of divide and conquer as $N_T$ increases.
- The sum rate increases faster in joint MU-MIMO and OFDMA mode because the channel capacity of MIMO is related to both the SNR and the rank of the channel matrix $H_s$

> Since the total transmit power $P_s$ is constant, the sum rate does not change linearly with $N_T$.