Computational Analysis and Efficient Algorithms for Micro and Macro OFDMA Downlink Scheduling

Orthogonal frequency-division multiple access (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 determines which of 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 subproblems, referred to as macro and micro scheduling. We analyze the computational complexity of these subproblems and develop efficient algorithms for solving them.