Survey of Down Link Data Allocation Algorithms in IEEE 802.16 WiMAX
---
paper_title: Fundamentals of WiMAX: Understanding Broadband Wireless Networking

paper_content:

This is the eBook version of the printed book. Praise for Fundamentals of WiMAX "This book is one of the most comprehensive books I have reviewed ... it is a must-read for engineers and students planning to remain current or who plan to pursue a career in telecommunications. I have reviewed other publications on WiMAX and have been disappointed. This book is refreshing in that it is clear that the authors have the in-depth technical knowledge and communications skills to deliver a logically laid out publication that has substance to it." Ron Resnick, President, WiMAX Forum "This is the first book with a great introductory treatment of WiMAX technology. It should be essential reading for all engineers involved in WiMAX. The high-level overview is very useful for those with non-technical background. The introductory sections for OFDM and MIMO technologies are very useful for those with implementation background and some knowledge of communication theory. The chapters covering physical and MAC layers are at the appropriate level of detail. In short, I recommend this book to systems engineers and designers at different layers of the protocol, deployment engineers, and even students who are interested in practical applications of communication theory." Siavash M. Alamouti, Chief Technology Officer, Mobility Group, Intel "This is a very well-written, easy-to-follow, and comprehensive treatment of WiMAX. It should be of great interest." Dr. Reinaldo Valenzuela, Director of Wireless Research, Bell Labs "Fundamentals of WiMAX is a comprehensive guide to WiMAX from both industry and academic viewpoints, which is an unusual accomplishment. I recommend it to anyone who is curious about this exciting new standard." Dr. Teresa Meng, Professor, Stanford University, Founder and Director, Atheros Communications "Andrews, Ghosh, and Muhamed have provided a clear, concise, and well-written text on 802.16e/WiMAX. The book provides both the breadth and depth to make sense of the highly complicated 802.16e standard. I would recommend this book to both development engineers and technical managers who want an understating of WiMAX and insight into 4G modems in general." Paul Struhsaker, VP of Engineering, Chipset platforms, Motorola Mobile Device Business Unit, former vice chair of IEEE 802.16 working group "Fundamentals of WiMAX is written in an easy-to-understand tutorial fashion. The chapter on multiple antenna techniques is a very clear summary of this important technology and nicely organizes the vast number of different proposed techniques into a simple-to-understand framework." Dr. Ender Ayanoglu, Professor, University of California, Irvine, Editor-in-Chief, IEEE Transactions on Communications "Fundamentals of WiMAX is a comprehensive examination of the 802.16/WiMAX standard and discusses how to design, develop, and deploy equipment for this wireless communication standard. It provides both insightful overviews for those wanting to know what WiMAX is about and comprehensive, in-depth chapters on technical details of the standard, including the coding and modulation, signal processing methods, Multiple-Input Multiple-Output (MIMO) channels, medium access control, mobility issues, link-layer performance, and system-level performance." Dr. Mark C. Reed, Principal Researcher, National ICT Australia, Adjunct Associate Professor, Australian National University "This book is an excellent resourc...
---
paper_title: eOCSA: An algorithm for burst mapping with strict QoS requirements in IEEE 802.16e Mobile WiMAX networks

paper_content:

Mobile WiMAX systems based on the IEEE 802.16e standard require all downlink allocations to be mapped to a rectangular region in the two dimensional subcarrier-time map. Many published resource allocation schemes ignore this requirement. It is possible that the allocations when mapped to rectangular regions may exceed the capacity of the downlink frame, and the QoS of some flows may be violated. The rectangle mapping problem is a variation of the bin or strip packing problem, which is known to be NP-complete. In a previous paper, an algorithm called OCSA (One Column Striping with non-increasing Area first mapping) for rectangular mapping was introduced. In this paper, we propose an enhanced version of the algorithm. Similar to OCSA, the enhanced algorithm is also simple and fast to implement; however, eOCSA considers the allocation of an additional resource to ensure the QoS. eOCSA also avoids an enumeration process and so lowers the complexity to O(n2).
---
paper_title: Fundamentals of WiMAX: Understanding Broadband Wireless Networking

paper_content:

This is the eBook version of the printed book. Praise for Fundamentals of WiMAX "This book is one of the most comprehensive books I have reviewed ... it is a must-read for engineers and students planning to remain current or who plan to pursue a career in telecommunications. I have reviewed other publications on WiMAX and have been disappointed. This book is refreshing in that it is clear that the authors have the in-depth technical knowledge and communications skills to deliver a logically laid out publication that has substance to it." Ron Resnick, President, WiMAX Forum "This is the first book with a great introductory treatment of WiMAX technology. It should be essential reading for all engineers involved in WiMAX. The high-level overview is very useful for those with non-technical background. The introductory sections for OFDM and MIMO technologies are very useful for those with implementation background and some knowledge of communication theory. The chapters covering physical and MAC layers are at the appropriate level of detail. In short, I recommend this book to systems engineers and designers at different layers of the protocol, deployment engineers, and even students who are interested in practical applications of communication theory." Siavash M. Alamouti, Chief Technology Officer, Mobility Group, Intel "This is a very well-written, easy-to-follow, and comprehensive treatment of WiMAX. It should be of great interest." Dr. Reinaldo Valenzuela, Director of Wireless Research, Bell Labs "Fundamentals of WiMAX is a comprehensive guide to WiMAX from both industry and academic viewpoints, which is an unusual accomplishment. I recommend it to anyone who is curious about this exciting new standard." Dr. Teresa Meng, Professor, Stanford University, Founder and Director, Atheros Communications "Andrews, Ghosh, and Muhamed have provided a clear, concise, and well-written text on 802.16e/WiMAX. The book provides both the breadth and depth to make sense of the highly complicated 802.16e standard. I would recommend this book to both development engineers and technical managers who want an understating of WiMAX and insight into 4G modems in general." Paul Struhsaker, VP of Engineering, Chipset platforms, Motorola Mobile Device Business Unit, former vice chair of IEEE 802.16 working group "Fundamentals of WiMAX is written in an easy-to-understand tutorial fashion. The chapter on multiple antenna techniques is a very clear summary of this important technology and nicely organizes the vast number of different proposed techniques into a simple-to-understand framework." Dr. Ender Ayanoglu, Professor, University of California, Irvine, Editor-in-Chief, IEEE Transactions on Communications "Fundamentals of WiMAX is a comprehensive examination of the 802.16/WiMAX standard and discusses how to design, develop, and deploy equipment for this wireless communication standard. It provides both insightful overviews for those wanting to know what WiMAX is about and comprehensive, in-depth chapters on technical details of the standard, including the coding and modulation, signal processing methods, Multiple-Input Multiple-Output (MIMO) channels, medium access control, mobility issues, link-layer performance, and system-level performance." Dr. Mark C. Reed, Principal Researcher, National ICT Australia, Adjunct Associate Professor, Australian National University "This book is an excellent resourc...
---
paper_title: Fundamentals of WiMAX: Understanding Broadband Wireless Networking

paper_content:

This is the eBook version of the printed book. Praise for Fundamentals of WiMAX "This book is one of the most comprehensive books I have reviewed ... it is a must-read for engineers and students planning to remain current or who plan to pursue a career in telecommunications. I have reviewed other publications on WiMAX and have been disappointed. This book is refreshing in that it is clear that the authors have the in-depth technical knowledge and communications skills to deliver a logically laid out publication that has substance to it." Ron Resnick, President, WiMAX Forum "This is the first book with a great introductory treatment of WiMAX technology. It should be essential reading for all engineers involved in WiMAX. The high-level overview is very useful for those with non-technical background. The introductory sections for OFDM and MIMO technologies are very useful for those with implementation background and some knowledge of communication theory. The chapters covering physical and MAC layers are at the appropriate level of detail. In short, I recommend this book to systems engineers and designers at different layers of the protocol, deployment engineers, and even students who are interested in practical applications of communication theory." Siavash M. Alamouti, Chief Technology Officer, Mobility Group, Intel "This is a very well-written, easy-to-follow, and comprehensive treatment of WiMAX. It should be of great interest." Dr. Reinaldo Valenzuela, Director of Wireless Research, Bell Labs "Fundamentals of WiMAX is a comprehensive guide to WiMAX from both industry and academic viewpoints, which is an unusual accomplishment. I recommend it to anyone who is curious about this exciting new standard." Dr. Teresa Meng, Professor, Stanford University, Founder and Director, Atheros Communications "Andrews, Ghosh, and Muhamed have provided a clear, concise, and well-written text on 802.16e/WiMAX. The book provides both the breadth and depth to make sense of the highly complicated 802.16e standard. I would recommend this book to both development engineers and technical managers who want an understating of WiMAX and insight into 4G modems in general." Paul Struhsaker, VP of Engineering, Chipset platforms, Motorola Mobile Device Business Unit, former vice chair of IEEE 802.16 working group "Fundamentals of WiMAX is written in an easy-to-understand tutorial fashion. The chapter on multiple antenna techniques is a very clear summary of this important technology and nicely organizes the vast number of different proposed techniques into a simple-to-understand framework." Dr. Ender Ayanoglu, Professor, University of California, Irvine, Editor-in-Chief, IEEE Transactions on Communications "Fundamentals of WiMAX is a comprehensive examination of the 802.16/WiMAX standard and discusses how to design, develop, and deploy equipment for this wireless communication standard. It provides both insightful overviews for those wanting to know what WiMAX is about and comprehensive, in-depth chapters on technical details of the standard, including the coding and modulation, signal processing methods, Multiple-Input Multiple-Output (MIMO) channels, medium access control, mobility issues, link-layer performance, and system-level performance." Dr. Mark C. Reed, Principal Researcher, National ICT Australia, Adjunct Associate Professor, Australian National University "This book is an excellent resourc...
---
paper_title: WiMAX Technology and Network Evolution

paper_content:

Written and edited by experts who have developed WiMAX technology and standards WiMAX, the Worldwide Interoperability for Microwave Access, represents a paradigm shift in telecommunications technology. It offers the promise of cheaper, smaller, and simpler technology compared to existing broadband options such as DSL, cable, fiber, and 3G wireless. WiMAX Technology and Network Evolution is the first publication to present an accurate, complete, and objective description of mobile WiMAX technology. Each chapter was written and edited by experts, all of whom have been directly engaged in and lead the development of WiMAX either through the IEEE 802.16 Working Group or the WiMAX Forum. As a result, the book addresses not only key technical concepts and design principles, but also a wide range of practical issues concerning this new wireless technology, including: Detailed description of WiMAX technology features and capabilities from both radio and network perspectives WiMAX technology evolution in the near and long term Emerging broadband services enabled by the WiMAX networks Regulatory issues affecting WiMAX deployment and global adoption WiMAX accounting, roaming, and network management Each chapter ends with a summary and a list of references to facilitate further research. Wireless engineers, service designers, product managers, telecommunications professionals, network operators, and academics will all gain new insights into the key issues surrounding the development and implementation of mobile WiMAX. Moreover, the book will help them make informed management and business decisions in devising their own WiMAX strategies.
---
paper_title: WiMAX Networks: Techno-Economic Vision and Challenges

paper_content:

Ignited by the mobile phone's huge success at the end of last century, the demand for wireless services is constantly growing. To face this demand, wireless systems have been and are deployed at a large scale. These include mobility-oriented technologies such as GPRS, CDMA or UMTS, and Local Area Network-oriented technologies such as WiFi. WiMAX Networks covers aspects of WiMAX quality of service (QoS), security, mobility, radio resource management, multiple input multiple output antenna, planning, cost/revenue optimization, physical layer, medium access control (MAC) layer, network layer, and so on.
---
paper_title: Wimax Technology for Broadband Wireless Access

paper_content:

WiMAX Broadband Wireless Access Technology, based on the IEEE 802.16 standard, is at the origin of great promises for many different markets covering fixed wireless Internet Access, Backhauling and Mobile cellular networks. WiMAX technology is designed for the transmission of multimedia services (voice, Internet, email, games and others) at high data rates (of the order of Mb/s per user). It is a very powerful but sometimes complicated technique. The WiMAX System is described in thousands of pages of IEEE 802.16 standard and amendments documents and WiMAX Forum documents. WiMAX: Technology for Broadband Wireless Access provides a global picture of WiMAX and a large number of details that makes access to WiMAX documents much easier. All the aspects of WIMAX are covered. Illustrations and clear explanations for all the main procedures of WiMAX are pedagogically presented in a succession of relatively short chapters Topics covered include WiMAX genesis and framework, WiMAX topologies, protocol layers, MAC layer, MAC frames, WiMAX multiple access, the physical layer, QoS Management, Radio Resource Management, Bandwidth allocation, Network Architecture, Mobility and Security Features a glossary of abbreviations and their definitions, and a wealth of explanatory tables and figures Highlights the most recent changes, including the 802.16e amendment of the standard, needed for Mobile WiMAX Includes technical comparisons of WiMAX vs. 802.11 (WiFi) and cellular 3G technologies This technical introduction to WiMAX, explaining the rather complex standards (IEEE 802.16-2004 and 802.16e) is a must read for engineers, decision-makers and students interested in WiMAX, as well as other researchers and scientists from this evolving field.
---
paper_title: Burst Construction and Packet Mapping Scheme for OFDMA Downlinks in IEEE 802.16 Systems

paper_content:

In this paper, we propose a burst construction and packet mapping scheme in the orthogonal frequency-division multiple access (OFDMA) downlinks of IEEE 802.16 systems. In the standard of the systems, there are some restrictions on the usage of downlink radio resources and they are defined in the physical layer (PHY) specification. One of the main restrictions is that a rectangular region, which is called Burst, is defined on a two-dimensional domain of time and frequency, and packets must be allocated within the region. However, how to define the burst and allocate data packets within the burst is left implementation dependent. Therefore, we consider a burst construction and packet mapping scheme that is easy to realize on systems and attains efficient usage of radio resources. By computer simulation, it has been confirmed that the proposed scheme can decrease not only the control data ratio within the rectangles, but also control data that must be transmitted at the head of every frame, which can result in higher throughput.
---
paper_title: WiMAX Downlink OFDMA Burst Placement for Optimized Receiver Duty-Cycling

paper_content:

Mobile wireless broadband access networks are now becoming a reality, thanks to the emerging IEEE 802.16e standard. This kind of network offers different challenges when compared to the fixed ones, as power consumption becomes a major concern. In this standard, a strict organization of the downlink bursts is not guaranteed in the OFDMA frame and this may lead to extra power consumption for the receiver, decreasing the device's lifetime. In the present paper, we introduce an optimization algorithm capable of reducing the activity of each receiver in the system for decoding its addressed bursts, thanks to a better time-frequency organization of the bursts. We first work on fitting bursts within the smallest frame, and show that the minimal number of OFDM symbols is enough in 70 to 80% of the cases, while one extra is needed otherwise. Using a binary tree implementation of an exhaustive burst placement search, we also show that we can gain 20 to 30% in duty-cycling of the receivers by selecting the best configuration, hence gaining the corresponding energy. This holds for receivers decoding either their bursts only or all the bursts from the beginning of the frame up to their own bursts before sleeping, depending on the scenario. The full search is sustainable for up to 8 user bursts per frame.
---
paper_title: Two-Dimensional Resource Allocation for OFDMA System

paper_content:

The resource allocation problem in OFDMA system is how to assign two-dimensional blocks covering time and frequency to multi-users. Resource allocation is crucial to system performance but is not defined in IEEE 802.16 standards. We proved that the problem of resource allocation in IEEE 802.16 standard is NP-complete. To approximately solve the problem in real time, we present a fast heuristic algorithm with O(n2) computational complexity based on topology evaluation. Simulation results show that the allocation result is competitive.
---
paper_title: A Cross-Layer Framework for Overhead Reduction, Traffic Scheduling, and Burst Allocation in IEEE 802.16 OFDMA Networks

paper_content:

IEEE 802.16 orthogonal frequency-division multiple access (OFDMA) downlink subframes have a special 2-D channel-time structure. Allocation resources from such a 2-D structure incur extra control overheads that hurt network performance. Existing solutions try to improve network performance by designing either the scheduler in the medium access control layer or the burst allocator in the physical layer, but the efficiency of overhead reduction is limited. In this paper, we point out the necessity of “codesigning” both the scheduler and the burst allocator to efficiently reduce overheads and improve network performance. Under the partial-usage-of-subcarriers model, we propose a cross-layer framework that covers overhead reduction, real-time and non-real-time traffic scheduling, and burst allocation. The framework includes a two-tier priority-based scheduler and a bucket-based burst allocator, which is more complete and efficient than prior studies. Both the scheduler and the burst allocator are tightly coupled together to solve the problem of arranging resources to data traffic. Given available space and bucket design from the burst allocator, the scheduler can well utilize the frame resource, reduce real-time traffic delays, and maintain fairness. On the other hand, with priority knowledge and resource assignment from the scheduler, the burst allocator can efficiently arrange downlink bursts to satisfy traffic requirements with low complexity. Through analysis, the cross-layer framework is validated to give an upper bound to overheads and achieve high network performance. Extensive simulation results verify that the cross-layer framework significantly increases network throughput, maintains long-term fairness, alleviates real-time traffic delays, and enhances frame utilization.
---
paper_title: Optimal WiMAX frame packing for minimum energy consumption

paper_content:

Minimizing energy consumption is an urgent and challenging problem. As in any communication system, high energy efficiency in WiMAX systems should be maintained by increasing resource efficiency. Thus, WiMAX resources should be properly utilized by optimizing the construction of downlink (DL) bursts. This paper proposes an energy-efficient scheme that maximizes the use of resources at the base station (BS) by reducing the energy wasted caused by sending padding bits instead of useful data. The problem was formulated as nonlinear integer programming model. Due to the complexity of the problem, this paper presents first the formulation of the base model for optimal DL bursts construction problem assuming the packet is represented by one burst. Then, the formulation is expanded to allow the representation of packets by several bursts. The results show an improvement in data packing that maximizes the utilization of frames, and minimizes energy wastage.
---
paper_title: A Linear-Complexity Burst Packing Scheme for IEEE 802.16e OFDMA Downlink Frames

paper_content:

The problem of efficiently shaping downlink data bursts into rectangles and packing them in the OFDMA subframe is not addressed by the IEEE 802.16 standard, and is left as an implementation issue. In this paper, we propose a linear complex- ity bursts packing algorithm to maximize radio resources usage on the OFDMA downlink. Our scheme shapes the bursts into identical width, places them in column direction and maximally fills the columns by shifting the bursts on different columns. By simulation, we show that the scheme can push the radio resource usage over 95%, which is on average 20% improvement compared with the simple 2D fixed-bin strip packing and 8% improvement with the exhaustive search. Moreover, the proposed scheme is also power-efficient, because subscriber stations (SSs) do not need to receive a large aggregated burst created for packing problem complexity reduction.
---
paper_title: Greedy scheduling algorithm (GSA) - Design and evaluation of an efficient and flexible WiMAX OFDMA scheduling solution

paper_content:

WiMAX is one of the most promising technologies to provide broadband wireless access in the near future. In this paper we focus on the study of the combined performance of a WiMAX Base Station MAC downlink scheduler and OFDMA packing algorithm which mainly determine the usage efficiency of the available radio resources. We design and analyze an efficient and flexible solution, greedy scheduling algorithm (GSA), and evaluate its performance as compared to several relevant alternative solutions. Specifically, we analyze performance differences with respect to efficiency, flexibility to provide per subscriber station burst shape preferences, interference mitigation and computational load. Our results show that GSA achieves a performance similar to the one of the competing approaches considered in terms of efficiency, even better in some cases, and significantly outperforms them in flexibility to provide per subscriber station burst shape preferences, interference mitigation and computational load. As a conclusion, the proposed GSA solution is a promising candidate to maximize the utilization of the available WiMAX radio resources at a low computational cost while at the same time being able to fulfill a wide range of requirements based on operators' preferences and/or network environment specifics.
---
paper_title: An energy-efficient scheme for WiMAX downlink bursts construction

paper_content:

One of the challenges in WiMAX networks is to increase resource and power efficiency by optimizing the downlink (DL) burst construction. This paper proposes an energy-efficient scheme that maximizes the use of resources at the base station (BS) while reducing the energy wasted caused by sending padding bits instead of useful data. This paper presents the derivation of the general optimization problem that was formulated as a nonlinear integer programming model. A simple case formulation is used to illustrate the general application. The results show an improvement in data packing that maximizes the utilization of frames, and minimizes energy wastage.
---
paper_title: Condensed Downlink MAP Structures for IEEE 802.16e Wireless Metropolitan Area Networks (MANs)

paper_content:

The new mobile wireless metropolitan area network (WMAN) architecture imposes a demanding performance requirement on the radio resource to provide broadband internet access. The radio resource is partitioned as bursts in time and frequency domains and used by mobile stations (MS) in an exclusive manner. The base station (BS) functionally serves as a resource controller for traffic to and from the MSs associated with it, and thus naturally generates the proper downlink (DL) and uplink (UL) MAPs for active MSs based on service and traffic requirements. However, the DL-MAP construction scheme in IEEE 802.16e OFDMA standard, which was designed for handling irregular traffic pattern of MS, often produces a large DL-MAP, as a certain small amount of data distribution to MSs will render a potential overhead of information elements (IE) in DL-MAP and limit the overall capacity. Moreover, the robustness requirement on MAP broadcasting would further cause severe system overhead. As a solution, we propose two exclusive condensed DL-MAP structures, which only carry partial information of each rectangular burst in order to reduce the size of IE in DL-MAP. For each condensed DL-MAP structure, the algorithms for BS to produce the condensed DL-MAP structure and the scheme for MS to precisely reconstruct the original DL-MAP structure are provided. As confirmed by the analytical results, the proposed condensed DL-MAP can achieve significant DL-MAP size reduction compared with standard DL-MAP structure.
---
paper_title: Efficient downlink scheduling with power boosting in mobile IEEE 802.16 networks

paper_content:

In current mobile broadband wireless access (BWA) technologies, which are based on orthogonal frequency division multiple access (OFDMA), terminals close to cell edge experience poor channel quality, due to severe path-loss and high interference from concurrent transmissions in nearby cells. To mitigate this problem we propose: (a) to partition the set of sub-channels into chunks, which are assigned different power levels; (b) the design of a data scheduling and allocation algorithm positioned in the medium access control (MAC) layer of the base station (BS), exploiting such a partitioning. The framework is analyzed in a multi-cell IEEE 802.16 network by means of system-level packet-based simulations, with detailed MAC and physical layer abstractions in combination with realistic models of the wireless channel and interference.
---
paper_title: OBBP: An Efficient Burst Packing Algorithm for IEEE802.16e Systems

paper_content:

Mobile communications have witnessed a phenomenal increase in the amount of users, services, and applications. Orthogonal Frequency Division Multiple Access (OFDMA) targets to provide broadband connectivity to wide area coverage, in mobile environments, for Next Generation Networks (NGNs), which results in significant design challenges in the MAC (Medium Access Control) layer to provide an efficient resource allocation in a cost-effective manner. This paper proposes a two-dimensional (2D) Burst Packing (BP) algorithm for OFDMA downlink (DL) subframe that can provide the service providers with an efficient, fast, flexible, and high-spectral efficiency method to allocate system resources among the Mobile Stations (MSs). The proposed Orientation-Based Burst Packing (OBBP) algorithm uses the Orientation Factors (OFs) of the bursts as a criteria to achieve the challenging issues in the BP problem. The simulation results show that OBBP algorithm can achieve a high packing efficiency up to 99.2% when the burst size ratio (BSR) is 50%.
---
paper_title: Cross-layer design for radio resource allocation based on priority scheduling in OFDMA wireless access network

paper_content:

The orthogonal frequency-division multiple access (OFDMA) system has the advantages of flexible subcarrier allocation and adaptive modulation with respect to channel conditions. However, transmission overhead is required in each frame to broadcast the arrangement of radio resources to all mobile stations within the coverage of the same base station. This overhead greatly affects the utilization of valuable radio resources. In this paper, a cross layer scheme is proposed to reduce the number of traffic bursts at the downlink of an OFDMA wireless access network so that the overhead of the media access protocol (MAP) field can be minimized. The proposed scheme considers the priorities and the channel conditions of quality of service (QoS) traffic streams to arrange for them to be sent with minimum bursts in a heuristic manner. In addition, the trade-off between the degradation of the modulation level and the reduction of traffic bursts is investigated. Simulation results show that the proposed scheme can effectively reduce the traffic bursts and, therefore, increase resource utilization.
---
paper_title: eOCSA: An algorithm for burst mapping with strict QoS requirements in IEEE 802.16e Mobile WiMAX networks

paper_content:

Mobile WiMAX systems based on the IEEE 802.16e standard require all downlink allocations to be mapped to a rectangular region in the two dimensional subcarrier-time map. Many published resource allocation schemes ignore this requirement. It is possible that the allocations when mapped to rectangular regions may exceed the capacity of the downlink frame, and the QoS of some flows may be violated. The rectangle mapping problem is a variation of the bin or strip packing problem, which is known to be NP-complete. In a previous paper, an algorithm called OCSA (One Column Striping with non-increasing Area first mapping) for rectangular mapping was introduced. In this paper, we propose an enhanced version of the algorithm. Similar to OCSA, the enhanced algorithm is also simple and fast to implement; however, eOCSA considers the allocation of an additional resource to ensure the QoS. eOCSA also avoids an enumeration process and so lowers the complexity to O(n2).
---
paper_title: A downlink data region allocation algorithm for IEEE 802.16e OFDMA

paper_content:

IEEE 802.16e specifies a connection-oriented centralized medium access control (MAC) protocol, based on time division multiple access (TDMA), which adds mobility support to the MAC protocol defined by the IEEE 802.16 standard for fixed broadband wireless access. To this end, orthogonal frequency division multiple access (OFDMA) is specified as the air interface. In OFDMA, the MAC frame extends over two dimensions: time, in units of OFDMA symbols, and frequency, in units of logical sub-channels. The base station (BS) is responsible for allocating data into the MAC frames so as to meet the quality of service (QoS) guarantees of the admitted connections of the mobile stations (MSs). This is done on a frame-by-frame basis by defining the content of map messages, which advertise the position and shape of data regions reserved for transmission to/from MSs. We refer to the latter operation as data region allocation. In this paper, we propose a sample data region allocation algorithm (SDRA), and we evaluate its performance by means of Monte Carlo analysis. The effectiveness of SDRA is assessed in several scenarios, involving mixed voice over IP (VoIP) and best effort MSs, different modulations, and frequency re-use plans.
---
paper_title: Two-dimensional downlink burst construction in IEEE 802.16 networks

paper_content:

Several burst construction algorithms for orthogonal frequency division multiple access were proposed. However, these algorithms did not meet the downlink burst characteristics specified in the IEEE 802.16 standard. This article therefore proposes the best corner-oriented algorithm (BCO). BCO not only complies with downlink burst characteristics, but also considers the three issues to obtain high throughput, as follows: BCO maintains all free slots as a continuous area by constructing each burst in the corner of the available bandwidth area for minimizing external fragmentation; BCO shrinks the burst area to minimize internal fragmentation, if the requested bandwidth has been satisfied; and for exploring the continuous subchannels with good channel quality, BCO ensures that the burst adopts an optimal modulation coding scheme by selecting the excellent corner that can generate the maximal throughput. The simulation results indicate that BCO achieves 2-9 times the throughput achieved by the previous algorithms under a heavy load.
---
paper_title: An Efficient Downlink Data Mapping Algorithm for IEEE802.16e OFDMA Systems

paper_content:

In the IEEE 802.16e OFDMA systems, the data mapping algorithm maps the data to the appropriate rectangular regions in the two-dimensional matrix of time and frequency domain. Each region is described by an Information Element (IE) which is used for signaling and occupies a slot. The IEs as well as vacant slots in the allocated rectangular region result in a substantial amount of overhead. In order to minimize the overhead so as to increase system throughput, the paper proposes a "Mapping with Appropriate Truncation and Sort" (MATS) algorithm. Extensive simulations are conducted in terms of mapping efficiency, mapping cost and system throughput to evaluate the performance of MATS. The results show that compared with Raster, MATS can increase the mapping efficiency by up to 2.4% and reduce the mapping cost by up to 80% and 37% for constant bit rate traffic and variable bit rate traffic, respectively. Moreover, system throughput is increased by more than 3% in the 10 MHz bandwidth network. Consequently, MATS can substantially reduce the overhead and achieve high system throughput.
---
paper_title: Piggybacking Scheme of MAP IE for Minimizing MAC Overhead in the IEEE 802.16e OFDMA Systems

paper_content:

This paper analyzes Media Access Control(MAC) overhead of the IEEE 802.16e systems and shows that it causes to degrade system performance critically. MAP, a control message about resource allocation, is broadcasted with high robustness and uses a great amount of radio resource for it. This paper also proposes an advanced scheme which transmits MAP IE, a component of MAP, piggybacked on data packets, and uses fast feedback to conserve the transmission reliability of the MAP IE. Then, MAP IEs can be transmitted with high data rate, and the amount of radio resource for transmitting MAP IEs becomes extremely small. Numerical analysis and simulation results show that the proposed scheme can significantly improve the MAC overhead.
---
paper_title: eOCSA: An algorithm for burst mapping with strict QoS requirements in IEEE 802.16e Mobile WiMAX networks

paper_content:

Mobile WiMAX systems based on the IEEE 802.16e standard require all downlink allocations to be mapped to a rectangular region in the two dimensional subcarrier-time map. Many published resource allocation schemes ignore this requirement. It is possible that the allocations when mapped to rectangular regions may exceed the capacity of the downlink frame, and the QoS of some flows may be violated. The rectangle mapping problem is a variation of the bin or strip packing problem, which is known to be NP-complete. In a previous paper, an algorithm called OCSA (One Column Striping with non-increasing Area first mapping) for rectangular mapping was introduced. In this paper, we propose an enhanced version of the algorithm. Similar to OCSA, the enhanced algorithm is also simple and fast to implement; however, eOCSA considers the allocation of an additional resource to ensure the QoS. eOCSA also avoids an enumeration process and so lowers the complexity to O(n2).
---

Title: Survey of Down Link Data Allocation Algorithms in IEEE 802.16 WiMAX

Section 1: INTRODUCTION
Description 1: Provide an overview of WiMAX technology, its advantages, and the challenges associated with resource allocation in WiMAX systems. Introduce the importance of scheduling and data packing algorithms, and highlight the paper's focus on downlink packing algorithms.

Section 2: WIMAX OVERVIEW
Description 2: Offer a general description of WiMAX as a wireless broadband solution, its standards, and key features.

Section 3: PHY layer overview
Description 3: Detail the physical layer specifications of WiMAX including the operating bands, OFDMA, modulation schemes, and frame structures.

Section 4: MAC layer overview
Description 4: Discuss the MAC layer, including its sublayers, functions such as PDU construction, QoS scheduling, call admission control, and bandwidth allocation.

Section 5: WIMAX FRAME ALLOCATION
Description 5: Explain the frame allocation process in TDD WiMAX, including the use of DL-MAP and UL-MAP messages, and the packing data into downlink and uplink frames.

Section 6: DL-Map and its overhead
Description 6: Illustrate how WiMAX assigns slots to users in downlink, the structure and impact of DL-MAP on the overall system, and an example scenario to highlight DL-MAP overhead.

Section 7: Wastages slots in downlink frame
Description 7: Provide a scenario to show how the packing process can lead to wastage slots in the downlink frame and discuss the implications on system performance.

Section 8: SURVEY OF DOWNLINK PACKING ALGORITHMS
Description 8: Conduct a comprehensive survey of various downlink packing algorithms, discuss their focus and efficiency based on different factors like fragments, power consumption, DL_MAP overhead, and cross-layer design considerations.

Section 9: Some considerations and design factors for downlink packing algorithm
Description 9: Discuss the considerations and design factors essential for developing an efficient downlink packing algorithm, emphasizing the trade-offs among different performance aspects.

Section 10: CONCLUSION
Description 10: Summarize the study, reiterate the importance of optimizing trade-offs in downlink data packing algorithms, and point out the need for comprehensive comparative analysis of existing algorithms under varied traffic classes.