# A MAP Overhead Aware Two-Dimensional OFDMA Burst Construction Algorithm
## 3 Problem Statement  
In this section, we give a formal problem statement for the two-dimensional downlink burst construction. We present basic notations needed for the definition and analysis of the problem in Table 1.  
Let a set of downlink connections as \(L=\{C_{1},\ldots,C_{n}\}\), and let \(n\) represent the number of downlink connections. A downlink subframe is composed of \((X,Y)\) slots where \(X\) is the number of symbols and \(Y\) is the number of subchannels. Also \(C_{i}\) represent the \(i\)-th connection after flow scheduling. \(BWA_{i}\) and \(BWR_{i}\) denote its number of allocated slots and the requested bandwidth, respectively, in the flow scheduling. When each connection queues in the flow scheduling, the flow scheduler estimates quality of service (QoS) requirements, power saving policy, channel quality variation, and it also considers many other factors to do this estimation. Therefore, the throughput provided by \(BWA_{i}\) may be lower than \(BWR_{i}\) since the flow scheduler does not allocate sufficient slots for \(i\)-th connection. One connection can transmit in different bursts with different MCSs in different subchannels, let \(B_{i}=\left\{B_{i}^{1},\ldots,B_{i}^{n}\right\}\) be a set of downlink burst allocated for \(C_{i}\). That is, connection \(C_{i}\) can be served by multi-bursts \(B_{i}^{1}\), \(B_{i}^{2},\ldots,B_{i}^{n}\), and \(B_{i}^{j}\) denote the \(j\)-th burst of connection \(C_{i}\). To estimate the MAP size, we assume that each connection adopts its best MCS, and then determine how many bursts would be created in downlink sub-frame. After obtaining the size of the MAP, we can derive total number of bursts \(NoB\) that the MAP would calculate based on the Formula (1). Therefore, the problem statement: According to the above parameters, given an downlink subframe, a set of \(L=\{C_{1},\ldots,C_{n}\}\) including each of connection \(BWR_{i}\) and \(BWA_{i}\), and the MCS matrix \(M\), construct a fixed MAP size and then allocate all bursts \(B_{i}=\left\{B_{i}^{1},\ldots,B_{i}^{n}\right\}\) in remaining space to maximize the total throughput \(\sum\limits_{i=1}^{N}Tp_{i}\). Several examples are provided here based on the above problem statement. Figure 4 shows four bursts and the MAP size in a downlink subframe. The MAP message is transmitted with the most robust MCS, i.e., quadrature phase shift keying (QPSK)\(1/2\). Since the MAP message is allocated within the downlink subframe in a column-wise order and the whole column, it would have extra space for building more bursts. Figure 4 shows the unused slots in the MAP is six slots. Therefore, we would construct more than four bursts under a fixed MAP size. \begin{table}
\begin{tabular}{c c} \hline \hline
**Notation** & **Definition** \\ \hline \(T\) & The two-dimensional allocation matrix. \\ L & A set of downlink connections. \\ \(X\) & The number of symbols in a downlink subframe. \\ \(Y\) & The number of subchannels in a downlink subframe. \\ n & The number of downlink connections. \\ \(C_{i}\) & The \(i\)-th connection after flow scheduling. \\ \(BWA_{i}\) & The number of available slots for \(C_{i}\) after flow scheduling. \\ \(BWR_{i}\) & The requested bandwidth for \(C_{i}\). The unit is bytes. \\ \(B_{i}^{j}\) & The \(j\)-th burst allocated for connection \(C_{i}\). \\ \(MCS_{i}^{j}\) & The modulation coding scheme (MCS) adopted by \(B_{i}^{j}\) of \(C_{i}\). \\ \(NoB\) & Total number of bursts in downlink-subframe (DL-subframe) \\ \(S_{i}^{j}\) & The number of slots occupied by \(B_{i}^{j}\) of \(C_{i}\). \\ \(M\) & The two-dimensional matrix for each connection in different \\  & subchannels. \(M\)(\(i\),\(j\)) specifies the MCS used by \(C_{i}\) in the \(j\)-th subchannel. \\ \(Tp_{i}\) & Throughput achieved by \(C_{i}\). \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Used notation. On the other hand, when allocating a burst, we need to consider the characteristics of subchannel diversity.