Most of IEEE 802.16e resource allocation proposals only focus on how to allocate the resources to meet QoS parameters such as throughput, delay, and delay-jitter. However, as described in the standard, the mapping from the allocation into downlink subframe for each subscriber needs to be in a rectangular shape. The rectangle mapping problem is a variation of bin or strip packing problem, which is known to be NP-complete. However, the mapping decision needs to be made within a few milliseconds for each Mobile WiMAX frame. In this paper we introduce a heuristic algorithm, called One Column Striping with non-increasing Area first mapping (OCSA). The algorithm is fast and simple to implement and minimizes the unused slots in the frame.
Complete paper in Adobe Acrobat format.