# A MAP Overhead Aware Two-Dimensional OFDMA Burst Construction Algorithm
## 4 Proposed Algorithm: Enhanced Burst Indexing Aware Algorithm
\begin{table}
\begin{tabular}{l l} \hline \hline
**EHA Algorithm:** & \\ \hline \multirow{2}{*}{**Input:**} & A frame \(T(x,y)\) a set of connections \(L=\{C_{1},C_{2},\ldots,C_{n}\}\) in which every \(C_{i}\in L\) has \\  & a \(BWA_{i}\) and a \(BWR_{i}\), and the MCS matrix \(M\). \\ \multirow{2}{*}{**Output:**} & A maximal throughput \(\sum_{i=1}^{N}Tp_{i}\) of \(T(x,y)\) under DL-MAP overhead. \\ \hline
1: & For each \(C_{i}\), \(avgMCS_{i}:=\sum_{j=1}^{Y}M(i,j)/Y\) \& \(B_{i}:=BWR_{i}/avgMCS_{i}/Y\) \\
2: & Let \(BurstNum=B_{1}+B_{2}+B_{3}+\cdots B_{i}\) and then do \(MAPCal(BurstNum)\) \\
3: & Get number of column of DL-MAP size \& derive \(NoB\) \\
4: & For each \(B_{i}\) of \(C_{i}\), do \\
5: & \(B_{i}:=\frac{BWR_{i}}{\sum_{i=1}^{N}BWR_{i}}\times NoB+0.5\) \\
6: & \(f\sum_{k=1}^{i}B_{k}<NoB\), \\
7: & subtract or add the minimum bandwidth request of \(B_{i}\). \\
8: & until \(NoB=\sum_{k=1}^{i}B_{k}\) \\
9: & End for \\
10: & Let \(t:=\max\{NoB,y\}\) Create a matrix with \(t\times t\) element. Each element \\ \(Tp[n][m]:=MCSCal(i,m)\times SubChCal(m)\) \\
11: & Find \(t:=\{\maxTp[n][m]\}\) then \(Tp[n][m]:=|t-Tp[n][m]|\) \\
12: & Find the optimal solution \(BuildList[y]\) by hungarian algorithm, \\
13: & For each \(C_{i}\), find its \(optimal\_channel[m]\) from \(BuildList[y]\) and \\  & \(sorted\_optimal[m]:=\text{Sort}(\text{MCSCal}(i,\,optimal\_channel[m]))\) \\
14: & End for \\
15: & For each \(sorted\_optimal[m]\), let as \(:=\min\{\text{SubchCal}(m)\), \(BWA_{i}\}\) \\
16: & if \((BWA_{i}>0\) \& \(\&\&\)\(BWR_{i}>0)\) \\
17: & For \(S:=1\) to \(as\) do \\
18: & \(TpCal(B_{i}^{j}):=S\times\text{MCSCal}(i,m)\) \\
19: & End for \\
20: & If \(TpCal(B_{i}^{j})\geq BWR_{i}\) then \\
21: & break; \\
22: & End \\
23: & \(B_{i}^{j}:=[(SSN_{m},m),(SSN_{m}+S,m)]\); \\
24: & \(NoB:=NoB-1\) \\
25: & \(BWA_{i}:=BWA_{i}-S\); \\
26: & \(BWR_{i}:=BWR_{i}-TpCal(B_{i}^{j})\); \\
27: & \(Build(B_{i}^{j})\) \\
28: & End If \\
29: & End For \\
26: & If \(NoB>0\) \& \(BWR_{i}>0\), go to line 4. \\ \hline \hline \end{tabular}
\end{table} 
Table 2: EHA Algorithm. of each connection. Assign each connection to use higher subchannel qualities first, rather than using worse ones (line 13, Table 2). To reduce internal fragmentation, \(B_{i}^{j}\) should occupy sufficient slots for transmitting data (line 15, Table 2). The unused slots in a subchannel can be used by other bursts. \(B_{i}^{j}:=[(SSN_{m},m),\ (SSN_{m}+S,m)]\) indicates the available area of a burst is from slot \((SSN_{m},m)\) to slot \((SSN_{m}+S,m)\) in subchannel \(m\). Function \(\text{Build}(B_{i}^{j})\) indicates the \(j\)-th burst allocated for connection \(C_{i}\) and marks all slots occupied by \(B_{i}^{j}\). If the throughput of \(B_{i}^{1},\ldots,B_{i}^{1+n}\) is sufficient to satisfy \(BWR_{i}\) of connection \(C_{i}\), EHA revokes the latter subchannel, which has not constructed a burst for connection \(C_{i}\) yet. After finishing the first mapping process, if there are remaining \(NoB\) and bandwidth request, line 4 again should be repeated. We present an example of EHA to construct bursts for connection \(C_{1},C_{2}\), and \(C_{3}\) in a downlink subframe within \(8\times 8\) slots, where the requested bandwidths are \(BWR_{1}=290\) bytes, \(BWR_{2}=320\) bytes, and \(BWR_{3}=180\) bytes, respectively, and the allocated slots are \(BWA_{1}=11\), \(BWA_{2}=12\), and \(BWA_{3}=8\). The matrix \(M\) represents the adopted MCSs for each connection in each subchannel. \[M=\left[ \begin{array}{c}0\\ 1\\ 2\\ 3\\ 4\\ 5\\ 6\\ 7\end{array} \right]=\left[ \begin{array}{cccc}C_{1}&C_{2}&C_{3}\\ 27&12&9\\ 18&6&9\\ 24&27&12\\ 27&27&6\\ 12&24&24\\ 6&18&27\\ 9&12&6\end{array} \right]\]  
We give a fixed MAP length by assuming each connection adopt its best MCS and then calculate how many bursts would be created in a downlink subframe. Therefore, \(C_{1}\) requires at least two bursts to transmit its data. \(C_{2}\) and \(C_{3}\) require at least two bursts and one burst to transmit.