## 1 Introduction  
The IEEE 802.16e Mobile WiMAX standard [1] uses Orthogonal Frequency Division Multiple Access (OFDMA) in order to achieve high data rate, long distance coverage, and mobility supports. In Mobile WiMAX OFDMA systems, the entire channel (wireless spectrum) is divided into multiple subcarriers. The number of subcarriers is proportional to the channel spectral width. These subcarriers are also grouped into a number of subchannels. Each mobile station (MS) is assigned a group of subchannels for a certain amount of times, as shown by the two dimensional diagram in Figure 1.  
Figure 1: A Sample OFDMA Frame Structure: PUSC [3]. In Figure 1, the vertical axis is frequency (subcarriers or logical subchannels). The horizontal axis is time. The time is measured in units of OFDM (Orthogonal Frequency Division Multiplexing) symbols. Mobile WiMAX uses a fixed frame-based allocation. Basically, each frame is of 5 ms duration [2]. The frame starts with a downlink preamble and Frame Control Header (FCH) followed by downlink (DL) and uplink (UL) maps (DL-MAP and UL-MAP). These maps contain the information elements (IEs) that specify the profile for each burst which consists of a number of OFDM symbols and subchannels. The profile consists of burst-start time, burst-end time, modulation type, and Forward Error Control (FEC) used or to be used in each burst. Figure 1 also shows a ranging region in the uplink subframe. This region is used to determine the distance between a base station (BS) and mobile stations (MSs) so that the transmission start times at various stations can be properly synchronized. This region helps to set the right transmit power level for each mobile station. A CQI&ACK region is used to send Channel Quality Indication (CQI) feedback and acknowledgements (ACKs). TTG (Transmit to Transmit Gap) and RTG (Receive to Transmit Gap) separate the downlink and uplink subframes. The resource allocation problem in IEEE 802.16e Mobile WiMAX Networks [3, 4, 5, 6] is about how to schedule resources, _i.e._, number of slots, for each mobile user in each Mobile WiMAX frame. Note that each slot consists of one subchannel allocated for the duration of some numbers of OFDM symbols. The number of subcarriers in the subchannel and the number of OFDM symbols in the slot depend upon the link direction (uplink or downlink) and subchannelization modes. The subchannelization mode or the mapping from logical subchannel to multiple physical subcarriers is called a permutation. Basically, there are two types of permutations: distributed and adjacent. The distributed subcarrier permutation is suitable for mobile users while adjacent permutation is for fixed (stationary) users. For example, in the Partially Used Sub-Channelization (PUSC) scheme, one of the distributed permutation modes, one slot consists of one subchannel over two OFDM symbol periods for downlink and one subchannel over three OFDM symbol periods for uplink. Others include Fully Used Subchannelization (FUSC) and Adaptive Modulation and Coding (band-AMC) [1, 2]. In this paper, we focus on the PUSC mode, commonly used in a mobile wireless environment [2, 4]. The IEEE 802.16e standard supports bi-directional communications as a frequency division duplexing (FDD) and a time division duplexing (TDD). For FDD, the uplink and the downlink use different frequency bands. For TDD, the uplink traffic follows the downlink traffic in the time domain. All scheduling schemes discussed in this paper can be used for both FDD and TDD systems. However, to keep the discussion focused, we use TDD throughout this paper. Although the IEEE 802.16e standard allows several configurations, such as mesh networks and relay networks, our focus is only on point to multipoint networks. Thus, the resource allocation problem is basically that the base station is the single resource controller for both uplink and downlink directions for each mobile station.