# A MAP Overhead Aware Two-Dimensional OFDMA Burst Construction Algorithm
## 4 Proposed Algorithm: Enhanced Burst Indexing Aware Algorithm  
In order to achieve the goals in Section 3, the proposed enhanced burst indexing aware algorithm (EHA) is divided into three phases. In the first phase, we determine the burst indexing size (also called the MAP size). In the second phase, the EHA finds the optimal matching between subchannel and connection according to the channel quality and bandwidth request of each connection. In the third phase, the EHA constructs bursts and leaves unused slots/subchannels for remaining bursts. The method is based on the following key concepts:  
* The number of bursts should be under the constraint of the MAP overhead. * One connection can be served by multi-bursts, so bursts should be constructed according to their good channel quality. * To maximize the overall throughput, we should shrink the burst area to minimize internal fragmentation and leave the saved slots to other bursts, if the requested bandwidth has been satisfied. The three EHA functions are MAPCal\((BurstNum)\), SubchCal\((m)\), and MCSCal\((i,m)\). The first one is used to calculate the MAP message size, and the formula is shown in Formula (1), Section 2. SubchCal\((m)\) and MCSCal\((i,m)\) are used to calculate the unused slots in subchannel \(m\), and the modulation coding rate adopted by \(C_{i}\) in subchannel \(m\), respectively. Table 2 shows the pseudo code of EHA. When the MAP becomes larger, the bursts which have been allocated in the downlink subframe have to be reassigned. To allocate bursts under the constraint of the MAP overhead, we give a fixed MAP length by each connection averaging its modulation coding rate schema of each subchannel (line 1, Table 2). After getting the minimum number of bursts that each connection requires, the total number of bursts can be made, and the MAP message size can be confirmed (line 2, Table 2). Considering that the MAP message is allocated within the downlink subframe in the whole column, we can therefore estimate (1) the number of slots occupied in the column of the MAP message and (2) the total number of bursts \(NoB\) that the MAP would provide in the downlink sub-frame from the formula (line 3, Table 2). To allocate available \(NoB\) for each connection \(C_{i}\), we assign the number of bursts \(B\) to each connection based on its bandwidth request (\(BWR_{i}\)) in the percentage of total bandwidth request and round it off to the nearest integer (line 4, Table 2). Since  
Figure 6: Internal fragmentation. the higher \(BWR_{i}\) of connection \(C_{i}\) would use more slots, we will assign sufficient bursts \(B_{i}\) for each connection \(C_{i}\). In order to find the best subchannel for each connection, we revise the Hungarian Algorithm with a row representing a burst for connection \(C_{i}\) and a column representing subchannel \(Y\). Each element in the matrix indicates the throughput of a burst if the subchannel is assigned to the related connection. The throughput of \(C_{i}\) in subchannel \(m\) of unused slots would be calculated by SubchCal\((m)\times\text{MCSCal}(i,m)\) (line 10, Table 2). To find the maximum throughput assignment, we need to transform the profit matrix as the needed cost matrix (line 11, Table 2). Thus, it would be suitable to solve the minimum assignment by the Hungarian Algorithm. After using the Hungarian Algorithm (as shown in Figure 4, Section 2), we can obtain the optimal solution of one subchannel with one connection to allocate the burst (line 12, Table 2). After obtaining the optimal solution \(BuildList[y]\), we construct bursts by one subchannel with one connection in unused slots. Although \(BuildList[y]\) is the optimal solution for this resource allocation, there are different MCSs between assigned subchannels