# A MAP Overhead Aware Two-Dimensional OFDMA Burst Construction Algorithm
## 1 Introduction  
As orthogonal frequency division multiple access (OFDMA) adopted by long-term evolution (LTE) acquires enormous 4G market success because it makes signal detection relatively simple [1]. For OFDMA systems, resource blocks are orthogonally divided in time and frequency, which are called bursts, and allocated to connections. The bandwidth allocation therefore becomes a two-dimensional bin packing problem. That is, the burst construction can be regarded as the process of placing items of variable heights, widths, and values into a two-dimensional area to maximize the total value of all items in the area.  
Subchannel diversity must be considered during burst construction to efficiently utilize the bandwidth resources. Subchannel diversity means that a user locating different locations may encounter different channel qualities in different subchannels, and the connection have different modulation coding scheme (MCS) on various subchannels [2]. Thus, burst should be placed on thesubchannel with the best channel quality (called best subchannels), while considering the subchannel diversity. Various burst construction methods have been proposed to solve the subchannel diversity issue [3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14].  
The conventional OFDMA burst construction methods, however, can only support a limited number of connections due to the map overhead (also called MAP overhead) and corresponding limitations in the numbers of orthogonal resources blocks, which limits the capacity of current 4G and the following 5G networks [1]. The MAP overhead is the size of the index of each burst, and it increases along with number of bursts, while the index indicates the position and size of each burst. The more bursts that exist, the bigger the MAP overhead that occurs, leading to more bandwidth resources that are wasted to transmit MAP overhead. Optimizing the burst indexing becomes an urgent need to support a massive number of and dramatically different classes of users and applications in 4G and following 5G networks. However, the methods in References [3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14] do not consider the burst index optimization problem.  
This study therefore provides a novel OFDMA burst construction algorithm, enhanced burst indexing aware algorithm (EHA), which try to maximize the throughput while considering the subchannel diversity and optimizing burst indexing issues mentioned above. The basic idea of EHA is to transform the burst construction problem, which is a two-dimensional bin packing problem, to the max-weighted bipartite matching problem, which assigns different numbers of subchannels to connections according to the channel quality of connections, given the constrains of the MAP overhead. The EHA also uses a burst to accommodate the connections belonging to a user in order to decrease the MAP overhead. Furthermore, the EHA minimizes the internal fragmentation of a burst by flexibly constructing the burst area in a subchannel that the requested bandwidth is satisfied, and thus the remaining slots in a subchannel can be used by other connections. Based on the above design, the two contributions of EHA are: (1) the overhead of burst indexing decreases because massive numbers of connections can be accommodated by one burst; and (2) the overall throughput increases if that one connection with a large data transferring requirement can be split and distributed into several bursts and placed on the subchannels with good channel quality to adopt better MCS.  
The rest of this paper is organized as follows. In Section 2, we describe the background in the OFDMA network and previous related works. Section 3 presents the problem statement of the downlink burst allocation. In Section 4, our proposed EHA algorithm is described in detail. Then, the performance evaluation is presented in Section 5. Finally, some conclusions are given in Section 6 by summarizing the gains.