Computational Analysis and Efficient Algorithms for Micro and Macro OFDMA Downlink Scheduling Reuven Cohen Liran Katzir Department of Computer Science Technion–Israel Institute of Technology Haifa 32000, Israel
Abstract—OFDMA is one of the most important modulation and access methods for the future mobile networks. Before transmitting a frame on the downlink, an OFDMA base station has to invoke an algorithm that determineswhichof the pending packets will be transmitted, what modulation should be used for each of them, and how to construct the complex OFDMA frame matrix as a collection of rectangles that fit into a single matrix with fixed dimensions. We propose efficient algorithms, with performance guarantee, that solve this intricate OFDMA scheduling problem by breaking it down into two sub-problems, referred to as macro and micro scheduling. We analyze the computational complexity of these sub-problems and develop efficient algorithms for solving them.
I. INTRODUCTION OrthogonalFrequencyDivision Multiple Access (OFDMA) is one of the most important modulation and multiple access methods for the future mobile networks. It is an extension of OFDM, which is today the modulation of choice for nonmobile wireless access systems such as IEEE 802.11 (WiFi) and IEEE 802.16(WiMax). OFDM divides a single frequency band into dozens of sub-carriers for parallel transmissions by the same user. This division increases the tolerance to noise and multipath effects, while enabling more efficient use of bandwidthallocation.OFDMAextendsOFDMbydividingthe originalbandintomanysubchannels,eachcomprisingagroup oforthogonalcarriers.VariousmodulationsandFEC(Forward Error Correction) techniques are used for each subchannel, in order to provide improved coverage and throughput. Unlike OFDM, OFDMA has many intricate constraints on its frame structure. The structure of an OFDMA downlink frame is depicted in Figure 1. The frame can be viewed as a 2-dimensional matrix, with the y-axis indicating the number of subchannels, each consisting of several orthogonal and not necessarily adjacent frequencies, and the x-axis indicating the time. The frame starts with a Frame Control Header (FCH), which contains information about the code rate, modulation level, and the length of the downlink (DL) and uplink (UL) maps. The data messages (PDUs) are transmitted in multiple bursts. There are 7 bursts shown in Figure 1. Each burst is transmitted by the base station using a specific combination ofmodulationtechnique,coderate,anderrorcorrectingcodes. Such a combination is referred to as PHY-profile. Due to OFDMA-relatedconstraints,eachdata burst must beallocated arectangularregionwithintheframe.Aburstmaycontainone or more PDUs destined for one or more receivers. To ensure correct decoding of the received signals, certain PHY-profile
subchannel logical number
time (OFDMA symbol number)
p r e a m b l e FCH downlink & uplink map downlink & uplink map
downlink burst #2
downlink burst #4
downlink burst #7
burst #3
downlink burst #1 downlink burst #6
downlink burst #5
downlink
Fig. 1. The Structure of an OFDMA Downlink Frame
information about every burst is required. This information is included as overhead in the DL burst map. The DL and UL maps are transmitted using a pre-determined and robust PHY-profile. This paper studies combinational aspects of scheduling on an 802.16/WiMax downlink OFDMA channel. Before transmitting a downstream frame, typically once every few ms., the base station has to invoke a scheduling algorithm that will generate the frame matrix as shown in Figure 1. To this end, the scheduler needs to address the following decision problems: • To decide which PHY-profile will be used for each PDU. There are several dozen potential profiles, each with its own bandwidth requirement and robustness against transmission errors. It is not possible to use all profiles in one frame. Moreover, each profile introduces a fixed significant overhead in the DL map field of the frame, and therefore, because of throughput considerations, the scheduler should try to minimize the number of profiles accommodated in every frame. • To determine which PDU will be transmitted in the next frame. This decision has to take into account many factors, such as: (a) Quality of Service, since some of the PDUs have a guaranteed upper bound on their maximumdelay;(b)totalthroughputmaximization,since transmission to some of the hosts is difficult and requires more bandwidth for reliable delivery, and (c) fairness. • To decide where exactly in the frame every burst will be located. Here there are also several constraints, some
