# IEEE 802.11 ax OFDMA Resource Allocation with Frequency-Selective Fading
## 5 Scheduling  
### Greedy Algorithm  
Let us, first, show a brief outline of the designed algorithm. All the STAs are sorted in the descending order of increments \(\lambda(s,r,c)\) of the utility function. After that, the first STA in the list is assigned to the widest available RU, i.e., such an RU that the STA's increment \(\lambda(s,r,c)\) is non-zero. Then, the second STA is assigned to the widest of the remaining RUs, etc. This process continues until the list of STAs or the list of RUs are exhausted. The result is a set of assignments at fixed MCS \(c\). The AP builds such sets for each MCS from \(C\) and then selects the best one. Let us consider this algorithm in more detail (see Algorithm 1). First, let us fix the MCS \(c\). Then, the gain \(\lambda(s,r,c)\) of the utility function for \(r\in R_{242}\) is calculated for each STA, where \(R_{242}\) is the set of 242-tone RUs of the channel (242-tone RU corresponds to 20 MHz band). Channel conditions for these RUs can differ significantly because of the frequency selective fading. We choose the maximum gain as follows:  
\[\lambda_{sort}(s)=\max_{r\in R_{242}}\lambda(s,r,c). \tag{3}\]  
The sorting is done according to the 242-tone RUs as a result of trade-off. On the one hand, these RUs are quite large, and therefore, the \(\lambda_{sort}\) values characterize the \"average\" channel quality. On the other hand, we do not consider larger RUs because the average channel properties in a very wide RU poorly represent the potential of OFDMA, but we still want to exploit the OFDMA feature of dividing the channel by frequency. ```
1:Parameters:
2:\(R_{size}\): the set of \(size\)-tone RUs in the channel
3:ChannelWidth: number of tones in full channel
4:Output:
5:\(X_{best}\leftarrow\emptyset\): resulting STA-RU assignment
6:\(gain_{best}\gets 0\): cumulative metric gain for the resulting assignment
7:\(c_{best}\): MCS for the resulting STA-RU assignment
8:for all\(c\in C\)do
9:\(X\leftarrow\emptyset\)
10:for all\(s\in S\)do
11:\(\lambda_{sort}(s)\leftarrow\max_{r\in R_{242}}\lambda(s,r,c)\)
12:endfor
13: Sort STAs in the descending order of \(\lambda_{sort}\) in \(S\)
14:while\(i\
eq|S|\)or there are unoccupied RUs do
15:for\(size\leftarrow\) ChannelWidth to 26-tones do
16:for all\(r\in R_{size}\)and \(r\) is unoccupied do
17:if\(\lambda(s_{i},r,c)>0\)then
18:\(\lambda(s_{i},r,c)>0\) if STA \(s_{i}\) is able to transmit to the AP in RU \(r\) at MCS \(c\)
19:\(X\gets X\cup\{s_{i},r\}\)
20:goto label
21:endif
22:endfor
23:endfor
24: label:
25:endwhile
26:\(gain\leftarrow\sum_{(s_{f})\in X}\lambda(s,r,c)\)
27:if\(gain>gain_{best}\)then
28:\(X_{best}\gets X\)
29:\(c_{best}\gets c\)
30:\(gain_{best}\gets gain\)
31:endif
32:endfor
```  
**Algorithm 1** Greedy Scheduling Algorithm. The STAs are sorted in the descending order of \(\lambda_{sort}\). The first STA in this list (i.e., the STA with the largest utility function gain) is assigned to the widest RU in which this STA can transmit at MCS \(c\) (i.e., its increment \(\lambda(s,r,c)\) is non-zero for the considered RU \(r\) and MCS \(c\)). The second STA is assigned to the widest remaining available RU, i.e., the second STA has to have enough power to transmit in this RU, and the resulting assignment \(X\) of two STAs should satisfy restrictions (1). This procedure is repeated for all the STAs in the list until the end of the list, or until there are no available RUs for all the remaining STAs. For the resulting assignment \(X\), we calculate the cumulative gain:  
\[\sum_{(s,r)\in X}\lambda(s,r,c). \tag{4}\]  
The algorithm builds allocations for every MCS in the same way. After that, the algorithm chooses such MCS \(c\) and respective assignment \(X\) that the value of the total utility function (4) is maximal. The algorithm contains a cycle through all MCSs, and for each MCS, the algorithm performs a search on all STAs, which is limited either by the number of STAs or by the number of available RUs.