# A Novel QoS-Aware ARQ Scheme for Multi-User Transmissions in IEEE802.11 ax WLANs
## 3 Methods
### The Greedy Algorithm  
Because the frame transmissions in the WLANs demand a timely response according to the scheduling mechanism of WLANs, a greedy algorithm [24], which searches for a sub-optimal solution but largely shortens the processing time, is recommended here. Moreover, three methods are adopted in the algorithm to further reduce the processing time by considering the computation load, the range of candidates, and parallel processing. The greedy algorithm divides the original optimization problem into multiple steps, and there is a sub-problem in each step. For each sub-problem, the precondition is the result of previous steps. When the objective value does not converge to the upper bound, and the A-MPDU can contain another sub-frame according to the constraints, the sub-problem searches for one packet that achieves the best performance under the precondition and increases the number of backups for the packet by 1. In each step, the number of backups for each packet determined by the previous steps is defined as  
\[\vec{R}^{\prime}=(r^{\prime}_{1}\text{ }r^{\prime}_{2}\text{ }...\text{ }r^{\prime}_{L-1}\text{ }r^{\prime}_{L}), \tag{12}\]  
and the initial status used in the first step is \((0\text{ }0\text{ }...\text{ }0\text{ }0)\). Thus, the number of backups for each packet updated in the current step when the l-th packet is chosen is described as \[\vec{R^{\prime}}_{l}=(r^{\prime}_{1}\ \ r^{\prime}_{2}\ \...\ r^{\prime}_{l}+1\ \...\ r^{\prime}_{L-1}\ r^{\prime}_{L}), \tag{13}\]  
The selection of packet in each step is based on the following equation:  
\[max_{l}\ E[S](\vec{R^{\prime}}_{l}), \tag{14}\]  
\[\textit{s.t.}\ \ \ \ len_{MACheader}+len_{payload,l}+\sum_{j=1}^{L}((1+r^{ \prime}_{j})\times(len_{MACheader}+len_{payload,j}))\leq len_{maxampdu},\]  
\[\frac{len_{MACheader}+len_{payload,l}+\sum_{j=1}^{L}((1+r^{ \prime}_{j})\times(len_{MACheader}+len_{payload,j}))}{rate}\leq T_{sche},\]  
\[B_{upper}-E[S](\vec{R^{\prime}})>C,\]  
\[1\leq l\leq L\ \textit{and}\ l\in\mathbf{Z}.\]  
After the optimal solutions in all sub-problems are found, the backup status updated in the last step is considered the sub-optimal solution of Equation (9). The time complexity of the greedy algorithm is \(O((N-L)\times L)\), and the space complexity is \(O(L)\). To find the optimal solution for the sub-problem, we compare the objective values when two different solutions are applied, i.e., two different packets are selected, respectively. In each comparison, the candidate with a smaller sequence number is called the u-th packet, and another one is called the v-th packet. The difference between the two expected number of uploaded  
\[E[S](\vec{R^{\prime}}_{u})-E[S](\vec{R^{\prime}}_{v})=(\prod_{i=1}^{u-1}(1-P^{ \prime}_{e,i}))(1-e)((A+B)\times P^{\prime}_{e,u}-B\times P^{\prime}_{e,v}). \tag{18}\]  
Because other factors in Equation (18) are always positive, whether or not the result is positive, is determined by the decision function, which is given by  
\[D(u,v)=(A+B)\times P^{\prime}_{e,u}-B\times P^{\prime}_{e,v}. \tag{19}\]  
The decision function only depends on parameters of the prepared packets whose sequence number is greater than the smaller candidate between the two, so the computation load is reduced. In each comparison, the u-th packet is selected if \(D(u,v)\) is greater than zero; otherwise, the v-th packet is better. After all the candidates are compared, the optimal solution of the sub-problem is achieved. For each sub-problem, the range of candidates can also be narrowed in advance according to the decision function. Because \(D(u,v)\) is definitely positive when \(P^{\prime}_{e,u}\) is equal to \(P^{\prime}_{e,v}\), i.e., \(r^{\prime}_{u}\) is equal to \(r^{\prime}_{v}\), the packet with the smallest sequence number is always selected among the packets that have the same number of backups in the precondition. Consequently, we can classify those packets into a group, and the comparisons are performed among packets whose sequence number is the smallest in their respective groups.