UNIVERSITY OF VAASA FACULTY OF TECHNOLOGY TELECOMMUNICATION ENGINEERING Md.Syedul Arif SUBCARRIER AND POWER ALLOCATION IN WIMAX Master´s thesis for the degree of Master of Science in Technology submitted for inspection, in Vaasa, 24 th of May, 2010. Supervisor D.Sc. (Tech.) Mohammed Salem Elmusrati Instructor M. Sc (Tech) Reino Virrankoski 2 ACKNOWLEDGEMENTS First of all, I would like to express my sincere gratitude to my supervisor Professor Mohammed Elmusrati for his endless support, encouragement, constant consultation and guidance during my thesis work. I am really grateful for his resourceful course lectures especially for the Radio resource management and Digital communication which has helped me to accomplish this Master’s thesis successfully. I am also extremely thankful to my instructor Mr. Reino Virrankoski for providing useful information during coursework for Matlab and Wireless communication networks. In addition, I would like to thank all of my friends at the University of Vassa. Especially I would like to thanks Mr. Ruifeng Duan, Fahim Ahmed, Tobias Glocker ,Arifnoor Chowdhury and Sheikh Mohsin Habib for their help, discussion and inspiration during the thesis work. Finally, I would like to thank to my parents, my brother and sister for their continuous mental support and precious prayers and endless love which helped me to continue until the completion of this thesis. Md. Syedul Arif Vaasa, 24 th of May, 2010. 3 TABLE OF CONTENTS ACKNOWLEDGEMENTS 2 SYMBOLS AND ABBREVIATIONS 5 ABSTRACT 10 1. INTRODUCTION 11 2. OVERVIEW OF WIMAX 13 2.1. Background and Evolution of WiMAX Standard 13 2.1.1. IEEE 802.16-2001 14 2.1.2. IEEE 802.16-2002 15 2.1.3. IEEE 802.16-2003 15 2.1.4. IEEE 802.16-2004 15 2.1.5. IEEE 802.16-2005 16 2.2. Essential Features of WiMAX 17 2.3. Application of WiMAX 19 2.4. Deployment Challenges for WiMAX 20 2.5. Protocol Architecture of IEEE 802.16 21 3. IEEE 802.16 PHYSICAL AND MEDIUM ACCESS CONTROL LAYER 23 3.1. Types of Air interface for IEEE 802.16 Physical Layer 23 3.1.1. WirelessMAN-SC 23 3.1.2. WirelessMAN-SCa 24 3.1.3. WirelessMAN-OFDM 24 3.1.4. WirelessMAN-OFDMA 24 3.1.5. WirelessMAN-HUMAN 25 3.2. OFDM-PHY 25 3.2.1. Introduction to OFDM. 28 3.2.2. Implementation of an OFDM system 30 4 3.2.3. Guard Time and Cyclic Prefix 32 3.2.4. OFDM System Design Requirement 32 3.2.5. Essential OFDM Design Parameters in WiMAX 33 3.2.6. Advantages and Disadvantages of OFDM. 34 3.3. OFDMA-PHY 35 3.3.1. OFDMA Basic 35 3.3.2. Scalable OFDMA 36 3.3.3. OFDMA Symbol Structure and Sub-channelization 37 3.3.4. Multiuser Diversity and AMC 40 3.3.5. Hybrid Automatic Repeat Request 41 3.3.6. Adaptive Antenna System (AAS) 42 3.4. MAC LAYER 43 3.4.1. Architecture of MAC Layer 43 3.4.2. Packet Header Suppression 45 3.4.3. MAC PDU Formats and Transmission 46 3.4.4. Security 48 3.4.5. MAC Scheduling Services 50 3.4.6. Power Saving Features Mobility 52 3.4.7. Mobility 56 4. RESOURCE ALLOCATION TECHNIQUES FOR OFDMA. 60 4.1. Subcarrier and Power Allocation Algorithm 61 4.1.1. Maximum Sum Rate (MSR). 61 4.1.2. Maximum Fairness (Max-Min). 67 4.1.3. Proportional Rate Constraints. 69 5. ALGORITHMS ANALYSIS AND SIMULATIONS 75 6. CONCLUSION AND FUTURE WORK 85 BIBLOGRAPHY 87 5 ABBREVIATIONS 3G Third Generation Mobile Communication System AAS Advanced Antenna System ADSL Asymmetric Digital Subscriber Line AES Advanced Encryption Standard AMC Adaptive Modulation and Coding ATM Asynchronous Transfer Mode BE Best-Effort Service BER Bit Error Rate BS Base Station CID Connection Identifier CMAC Cipher-based Message Authentication Code CP Cyclic Prefix CPS Common-part Sublayer CQI Channel Quality Indicator CRC Cyclic Redundancy Check CS Convergence Sub-layer DES Data Encryption Standard DFS Dynamic Frequency Selection DFT Discrete Fourier Transform DL Downlink EAP Extensible Authentication Protocol http://en.wikipedia.org/wiki/Discrete_Fourier_transform 6 EAP Extensive Authentication protocol ERTPS Extended Real-Time Polling services ETSI European Telecommunications Standards Institute FBSS Fast base station switching FDD Frequency Division Duplex FDM Frequency Division Multiplexing FEC Forward Error Correction FFT Fast Fourier Transform FTP File Transfer Protocol FUSC Full Usage of Subchannels H-FDD Half Duplex Frequency Division Duplex ICI Inter-carrier Interference IDFT Inverse Discrete Fourier transform IEEE Institute of Electrical and Electronics Engineers IFFT Inverse Fast Fourier Transform ISI Inter-symbol Interference LDPC Low Density Parity Check Code LOS Line of Sight LPF Low-pass Filter MCM Multicarrier Modulation MDHO Macro diversity handoff MF Maximum Fairness MS Mobile Station http://en.wikipedia.org/wiki/European_Telecommunications_Standards_Institute http://en.wikipedia.org/wiki/Discrete_Fourier_transform http://en.wikipedia.org/wiki/Institute_of_Electrical_and_Electronics_Engineers 7 MSR Maximum Sum Rate NLOS Non Line of Sight NRTPS Non-Real-Time Polling Services OFDM Orthogonal Frequency Division Multiplexing OFDMA Orthogonal Frequency Division Multiple access OFUSC Optional Full Usage of Subchannels OPUSC Optional Partial Usage of Subchannels PAR Peak-to-Average Power Ratio PDU Protocol Data Units PHS packet header suppression PHSF packet header suppression Field PHSI Packet Header Suppression Index PHSM packet header suppression Mask PHY Physical Layer PK public key PKM Privacy and key management protocol PMP Point-to-Multipoint PTP Point-to-Point PUSC Partial Usage of Subchannels QAM Quadrature Amplitude Modulation QoS Quality of service QPSK Quadrature Phase-Shift- Keying http://www.google.com/url?sa=t&source=web&ct=res&cd=3&ved=0CCAQFjAC&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.127.4909%26rep%3Drep1%26type%3Dpdf&rct=j&q=peak+to+average+power+ratio+(+PAR)&ei=71ntS7LtJ4j3OfCmvKAI&usg=AFQjCNEtrtDxZudxovkf19C5LDVX3bH-lA 8 RTPS Real-Time Polling services SDMA Space (or Spatial) Division (or Diversity) Multiple Access SDU Service Data Units SFID Service Flow Identifier SINR Signal-to-noise Ratio SOFDMA Scalable Orthogonal Frequency Division Multiple access SS Subscriber Station TDD Time Division Duplex TDM Time-division multiplexing TDMA Time Division Multiple Access TUSC Tile Usage of Subcarriers UGS Unsolicited Grant Service UL Uplink VoIP Voice over Internet Protocol WF Water Filling Wi-Fi. Wireless Fidelity 9 SYMBOLS Γ Signal to noise ratio gap σ 2 Additive white Gaussian noise γ Signal to noise ratio Ωk Set of subcarriers assigned to user k Є Element of a set Ø Predefined constant value  Subcarrier set λ Water filling level Neff (t) Scheduled subcarriers after WF at time t Rk Data rate for user k Hk,n Channel to noise ratio Pk, n Power for user k on subcarrier n Ck, n Channel assignment indicator K Number of user N Number of subcarrier 10 UNIVERSITY OF VAASA Faculty of technology Author: Md. Syedul Arif Topic of the Thesis: Subcarrier and Power Allocation in WiMAX Supervisor: Mohammed Elmusrati Instructor: Reino Virrankoski Degree: Master of Science in Technology Department: Department of Computer Science Degree Programme: Master’s Program in Telecommunication Engineering Major of Subject: Telecommunication Engineering Year of Entering the University: 2007 Year of Completing the Thesis: 2010 Pages: 92 ABSTRACT Worldwide Interoperability for Microwave Access (WiMAX) is one of the latest technologies for providing Broadband Wireless Access (BWA) in a metropolitan area. The use of orthogonal frequency division multiplexing (OFDM) transmissions has been proposed in WiMAX to mitigate the complications which are associated with frequency selective channels. In addition, the multiple access is achieved by using orthogonal frequency division multiple access (OFDMA) scheme which has several advantages such as flexible resource allocation, relatively simple transceivers, and high spectrum efficient. In OFDMA the controllable resources are the subcarriers and the allocated power per subband. Moreover, adaptive subcarrier and power allocation techniques have been selected to exploit the natural multiuser diversity. This leads to an improvement of the performance by assigning the proper subcarriers to the user according to their channel quality and the power is allocated based on water-filling algorithm. One simple method is to allocate subcarriers and powers equally likely between all users. It is well known that this method reduces the spectral efficiency of the system, hence, it is not preferred unless in some applications. In order to handle the spectral efficiency problem, in this thesis we discuss three novel resources allocation algorithms for the downlink of a multiuser OFDM system and analyze the algorithm performances based on capacity and fairness measurement. Our intensive simulations validate the algorithm performances. KEYWORDS: WiMAX, OFDMA, Downlink, Water-Filling, Maximum Sum Rate, Maximum Fairness, Proportional Rate Constraint. 11 1. INTRODUCTION The increasing interest in multimedia applications and high rate data services has lead to a growth in the development of wireless communication systems. Wireless systems have the capacity to cover broad geographic areas without the costly infrastructure, required to deploy the cabled links and satisfy the users’ requirements both in nomadic and mobile application scenarios. For this reason a variety of new wireless technologies, new standards have been emerging day by day, for example the modern cellular systems, third generation (3G) , fourth generation (4G) cellular networks and also some are under research such as the long term evolution (LTE), cognitive radio etc. In particular, Worldwide Interoperability for Microwave Access (WiMAX) system, based on IEEE 802.16 has gained much attention recently for its capability to support high transmission rates and quality of services (QoS) for different applications. Strong QoS control can be achieved by allocating the scare radio resources in an appropriate way. The challenges to ensure the fulfillment of this requirement arise from the limited availability of frequency spectrum, power and the time varying nature of wireless channel. To solve this issue WiMAX proposes intelligent radio resource management algorithm support in both physical (PHY) and medium access control (MAC) layer and implements orthogonal frequency division multiplexing (OFDM) technique for higher performance in the physical layer. The OFDM modulation technique is used to divide the broadband channel into several narrow band channels and to transmit a low rate data stream through each narrowband subchannel. For a single user OFDM system, a user can use all the subchannels and the available power to fulfill its requirement but in a multiuser OFDM system, a perfect resource allocation algorithm is required to distribute the available subcarrier and the power among the users in such a way that fulfill each user data rate and guarantees the individual QoS requirement. The main objective of this Master’s thesis is to analyze and explore the resource allocation algorithms for the downlink of a WiMAX system, focusing on certain 12 allocation objectives and bridging between theoretical and practical aspects through several simulations. 13 2. OVERVIEW OF WIMAX WIMAX (Worldwide Interoperability for Microwave Access) based on Wireless Metropolitan Area Network, is one of the latest Broadband Wireless Access (BWA) technology that has been revealed recently to provide broadband services in an area of large coverage with a high data rate. It is a revolutionary innovation in the history of wireless technology as it provides its user, Wi-Fi grade throughput with mobility like cellular system. It supports both Line-of-Sight (LOS) and Non-Line-of-Site (NLOS) applications. It works for fixed, nomadic, portable and mobile applications. Moreover, WiMAX supports interoperability and coexistence among different Broadband Wireless Access technologies from different vendors in a cost effective way. This technology has been standardized by Institute of Electrical and Electronics Engineers (IEEE 802.16) working group and later adopted by both European Telecommunications Standards Institute (ETSI) and IEEE group. It provides higher data rate (up to 70 Mbps) and coverage (in LOS condition up to 50km) in comparison to previous technology as Wi- Fi. For the business operator, it opens the door of a huge market as it combines the traditional cellular system and broadband technology (Optic fiber or ADSL) which offers more business opportunities through accommodating large client base with a low deployment cost. Its base stations are comparatively cheaper and require less planning than the existing system which offers more worthwhile for the case where the infrastructure cost is a major issue. This chapter explains the evolution of different WiMAX standards and their architectural diagrams, which end up through providing a brief description of their applications and the implementation challenges. 2.1. Background and Evolution of IEEE 802.16 Standards IEEE 802.16 is a standard formulating group, which offers different options to design a standard based Wireless Metropolitan Area Network air interface, for widespread and http://en.wikipedia.org/wiki/Institute_of_Electrical_and_Electronics_Engineers http://en.wikipedia.org/wiki/European_Telecommunications_Standards_Institute http://en.wikipedia.org/wiki/European_Telecommunications_Standards_Institute 14 worldwide effective deployment. According to the history, in the late 1990 several companies started manufacturing and developing BWA product according to their own catalysts. However the industries were needed for an interoperable standard. To solve such problem a meeting was held between the U.S. National Institute of Standard and Technology (NIST) and the IEEE organization and thus a group was formed to develop the standard named IEEE 802.16. In order to support the conformance test and interoperability for the implementation of this standard another team was formed (with 25 member companies) as named Worldwide Interoperability for Microwave Access (WiMAX). This IEEE 802.16 standard group is nowadays commonly known as WiMAX, and is responsible for further development. Basically IEEE802.16 standard defines the physical layer (PHY) and Medium Access Control layer (MAC) specification. The first version of this standard was accomplished in October 2001 and published on 8th April 2002. After performing a lot of amendment including different features and functionalities, variety of Standards were evolved which supports both licensed and licensed exempt spectrum (Eklund, Marks & Stanwood, Wang 2002; Marks 2003). The evolutions of these standards are outlined in the following sub- sections: 2.2.1. IEEE 802.16-2001 This first issue of standard specifies a set of PHY and MAC layer specification intended to provide fixed broadband wireless access in a point to point (PTP) and point to multipoint (PTM) system within the 10-66GHz licensed spectrum under Line of Sight conditions. This high frequency band is expensive but it has less interference. The standard based on single carrier physical layer and time division multiplexed MAC layer was approved finally in December, 2001. This standard supports three different modulation schemes such as QPSK, 16QAM and 64QAM, which can be changed from frame to frame and subscriber station to subscriber station, based on the channel condition. It supports both the Time Division Duplex (TDD) and Frequency Division Duplex (FDD) as a duplexing technique. (Andrew, Ghosh & Muhamed 2007:33-34.) 15 One of the most important features of IEEE 802.16 standard is its ability to support different quality of service (QoS) by MAC layer. “A service flow ID does QoS check. Service flows are characterized by their QoS parameters, which can then be used to specify parameters like maximum latency and tolerated jitter. Service flows can be originated either from base station (BS) or subscriber station (SS)” (Hasan 2007). 2.1.2. IEEE 802.16c-2002 IEEE Standard Board approved this amendment IEEE 802.16c in December 2002. In this amendment a detailed system profiles for 10-66GHz were included and some errors and inconsistencies of the previous version in IEEE 802.16-2001 of the standard were also corrected. (IEEE Std. 802.16c.) 2.1.3. IEEE 802.16a-2003 This is an improved version of IEEE 802.16-2001 standard, where some additional features have been introduced to make it workable for NLOS application within 2-11 GHz band using OFDM based physical layer. In this amendment the MAC layer has been modified to support multiple physical layer specification and also added some additional Physical layer specification in order to operate between 2-66 GHz frequency bands (IEEE Std. 802.16a). Due to NLOS operation multipath propagation becomes a problem, to deal with this problem a multipath propagation and interference mitigation features were included in this standard. A dynamic frequency selection (DFS) mechanism was also included in this technique which enables the SS to switch between different radio frequency (RF) channels on the basis of certain channel measurement criteria, such as signal-to-noise ratio (Ahson & Ilyas 2008:21). 2.1.4. IEEE 802.16d-2004 It is an improved version that combines the standards of IEEE 802.16-2001, 802.16- 2003 and 802.16c, and targeted for fixed device related application. Because of fixed device related application it is called fixed WiMAX. Initially it was published as a name 16 of IEEE802.16REVd, which changed later and published in a new name. (IEEE Std. 802.16-2004.) 2.1.5. IEEE 802.16e -2005 The main focus of all the previous standards were to provide service to a fixed broadband system, but in December 2005 IEEE group published a new standard named as IEEE 802.16e , after adding the provision of mobility and portability features with the previous version of IEEE802.16-2004. This standard was originally developed to achieve a certain goal which was to support large number of users. A key feature of this standard is the implementation of scalable OFDMA technique, which is highly robust against network congestion and presence of interference. Because of its mobility feature it is also called Mobile WiMAX. (IEEE 802.16e 2005.) Table 1: Comparison between IEEE 802.16 standards for WIMAX system. IEEE 802.16 - 2001 IEEE 802.16a - 2003 IEEE 802.16d - 2004 IEEE 802.16e - 2005 Spectrum 10-66GHz 2-11 GHz 2-11 GHz 2-6 GHz Application LOS NLOS NLOS NLOS Bandwidth 20,25,28 MHz 1.25-28 MHz 1.25-28 MHz 1.25-20 MHz Modulation Scheme QPSK,16QAM (optional in UL),64QAM OFDM,QPSK,1 6QAM,64QAM (Optional) OFDM,QPSK,1 6QAM, 64QAM OFDM,QPSK,1 6QAM, 64QAM Transmission Scheme Single carrier only single carrier, 256 OFDM, 2048 OFDMA single carrier, 256 OFDM, 2048 OFDMA single carrier, Scalable OFDM with 128, 256, 1024,2048 subcarrier Data rate Up to 134 bps 1-75 Mbps 1-75 Mbps 1-75 Mbps MAC Architecture PTP PTP,PMP, Mesh PTP,PMP, Mesh PTP,PMP, Mesh 17 2.2. Essential Features of IEEE 802.16 standard. WiMAX is one of the most popular BWA technologies that have been proved recently through providing a rich set of features and a lot of flexibilities in terms of implementation, quality of service (QoS) and adaption with different networks. Some of the most important key features are presented in the subsequent paragraphs. Interoperability: There are two leading factors namely interoperability and last mile connectivity, which are working behind the WiMAX for its acceleration of widespread adaptation. The WiMAX-forum was made up from different telecom companies that set the standard and test the WiMAX equipment of different vendors. In this way equipment price becomes cheaper and more accessible from which user gets the freedom of choice to select their product from different certified vendors (Rao & Radhamani 2008:341). In addition WiMAX supports the IP (IPV4,IPV6,) based services in such a way that it can easily interoperate with the existing IP (DSL, Cable, or 3G) based communication technology. (Ahson & Ilyas 2008:118.) Robust against Multipath: Because of having OFDM based physical layer WiMAX is highly robust against multipath fading and it promotes to operate in NLOS condition. (Andrew et all. 2007:37.) High capacity and data rate: A large number of users can be supported by single WiMAX tower. It can provide a data transfer rate up to74Mbps within a target range of 50km in LOS and 15 km in Non-Line-Of-Sight (NLOS) environments. It is possible to increase the bandwidth by applying higher modulation techniques. (Ahson & Ilyas 2008:43; Katz & Fitzek 2009:48.) Scalable bandwidth: The OFDMA based physical layer of WiMAX has scalability feature which provides data rate based on the available channel bandwidth like 1.25, 3.5, and 5 up to 20MHz thus user get the access of roaming facility across different networks with different bandwidths. These scalability features are done by selecting the 18 FFT size (128, 256, 512, 1024, 2048), while fixing the subcarrier spacing. Here FFT size indicates number of subcarrier. (WiMAX forum 2006.) QoS Support: The design of WiMAX Mac layer has been done in such a way that can support the variety of services, like voice, data and multimedia based on user demand. It has the capability to provide constant bit rate, variable bit rate, real and non real time traffic flows according to the service requirement. (Andrew et all. 2007:38). Mobility: It is one of the most attractive features of WiMAX that provides the user to move at vehicular speed inside the coverage area during data service session and also supports handover scheme when user moves from one base station to another base station through accepting some delay tolerance. Flexible key management and other security functions are also applied during handover period (Ahson & Ilyas 2008:44). Power saving technique: WiMAX Mac layer infrastructure offers battery operated portable devices a variety of power saving mode in order to switch it off when it is not actively transmitting or receiving data. (Andrew et all. 2007:51). Security: WiMAX provides the users’ robust security through adopting some techniques called state-of-the-art methods which prevents user from unauthorized access, ensure data privacy and supports user mobility. It also offer data encryption facility to all the subscribers using AES, 3DES algorithm, which provides the users data privacy and EAP authentication by means of providing username and password. Besides this, Privacy key management protocol and message digest scheme, AES based CMAC are also used to protect control messages over the air. (Hasan & Qadeer 2009) Mesh Topology: Mesh topology, which is an important amendment in IEEE 802.16a. It is a wireless data network that helps the SS to perform better communication than the traditional transmitter or receiver. For example, in PMP network system all the data must be transferred through the base station but in mesh network each subscriber performs as an access point and by doing this it can transfer data to its neighbor SS, thus coverage area increases (Ahson & Ilyas 2008:44). 19 2.3. Application of WiMAX Because of high data rate and NLOS application and large coverage, WiMAX offers a wide variety of application scenarios some of which can be outlined as follows: Cellular application: The most suitable application for WiMAX can be the area of mobile services. Most of the cellular systems use T1 (refers to a specific type of copper or fiber optic telephone line that can carry more data than traditional telephone lines) lines for backhaul implementation, which is a leased line and very expensive. WiMAX can be used instead of T1 lines. In addition, data transmission in WiMAX is far greater as compared to cell phone infrastructure where the data can be voice, TV, mobile data, video conferencing, etc. Moreover WiMAX can be implemented as a backhaul for Wi- Fi hotspots which are heavily used in an indoor environment. Rural areas: It is very challenging task for the broadband service providers to offer services in the rural areas, where the population density is very low. In such an environment it is very difficult to serve BWA using wired technology, due to high cost (Backhaul cost increases with distance), too remote and huge time consuming to implement the system, compared to WiMAX system. It is therefore, WiMAX can be the best option for supporting BWA in such an area (Intel 2003). Corporate Network: By using point to multipoint topology WiMAX can connect several remote offices to a central office providing secured, high speed and reliable data transfer. It can be used in a wide range of areas like education, local government, health, business and other public organizations. Military application: WiMAX has the capability to support the military applications as it uses higher frequency than the traditional military communication service, it just need to communicate between the existing tower and WiMAX cell tower. The U.S army Fortdix already has started the preliminary deployment of WiMAX to testify”The pre- standard WiMAX gear and Xacta secure wireless system for point-to-point and point- to-multipoint communications” (Ahson & Ilyas 2008:47-49). http://www.wisegeek.com/what-is-copper.htm http://www.wisegeek.com/what-are-fiber-optics.htm 20 Medical application: There are a lot of applications in medical sector such as e-health where a patient can be monitored by a doctor providing continuous information staying far away. Disaster application: WiMAX can be used to support disaster areas like earthquake or flood where the normal wired system has break down (Ahson & Ilyas 2008:47-49). Figure 1. A typical Application scenario of WiMAX (Eklund, Marks, Ponnuswamy, Stanwood and Waes 2006: 7). 2.4. Deployment Challenges for WiMAX Though, WiMAX is a very promising technique, still it is facing a lot of challenges to prove itself as a technology of the future. To achieve success it needs to support users, better performance than the existing technology, for example Wi-Fi or 3G.That means if 21 WiMAX want to compete with the existing technologies it has to offer all services under the defined constraint which are being offered by those technology. To fulfill such condition WiMAX is facing a lot of challenges, some of the key challenges are given below-  As compared to users, the available spectrum is very limited, so WiMAX needs to achieve higher spectral efficiency and coverage to provide broadband service to the user.  Mobility support by roaming and seamless handover  Hardwire design has to be such a way that it consumes low power and off- course without compromising the data rate.  To provide WiMAX highly secured technology, the current cryptographic security method needs to change as it is constantly receiving threat from malicious element from the cyber world and a new security method have to develop. (Hasan et al. 2009) 2.5. Protocol Architecture of IEEE 802.16 Figure 2. The logical architecture of IEEE 802.16 (IEEE Std. 802.16a). 22 WiMAX is based on IEEE 802.16 Wireless Metropolitan Area Network technology family, which consists of two different Layers, Physical Layer and MAC Layer. The MAC Layer of WiMAX further divided into three distinct sublayers namely: The service specific convergence sublayer (CS), Common-part sublayer (CP) and Security sublayer. The main task of Physical layer is to transfer information or data from transmitter to receiver reliably through the physical medium like copper wires, light wave or radio frequency. It also defines various types of modulation and power control techniques. Physical layer of WiMAX considers two types of transmission techniques OFDM and OFDMA and both uses FDD and TDD for duplexing purpose. This physical layer is not responsible for the quality of service, even for the type of applications, for instance FTP, HTTP etc. The MAC layer that resides at the top of the physical layer is actually responsible for controlling and multiplexing such type of applications through the physical medium. The MAC layer basically acts as an interface between the physical layer and the higher layer. It also performs scheduling and multiple access technique. The MAC layer takes data packet from higher layer and organizes for transmissions through the air. At the receiver side it performs the opposite. The Sub-layers of MAC performs various tasks for instance, the convergence sub-layer that interfaces with different higher layer protocol like asynchronous transfer mode(ATM), Time division multiplexing (TDM), Voice, and internet protocol (IP) etc. and perform operations based on the nature of the protocol such as header suppression and address mapping. The common part Sublayer is responsible for connection setup, automatic repeat request (ARQ), Bandwidth allocation and QoS control. The security sublayer provides subscriber privacy support and strong protection from theft of service. (Mac-layer) 23 3. IEEE 802.16 PHYSICAL AND MEDIUM ACCESS CONTROL LAYER This chapter explains the details about the transmission techniques used for the PHY and MAC layers in WiMAX and some additional features to support their functionality. At first, different variants of the PHY layer with their capabilities and conditions of operation are discussed. After that a brief description is given about OFDM and OFDMA modulation /multiplexing technique with their benefits and drawbacks. Finally this chapter concludes by providing the MAC layer operations with different QoS features. 3.1. Types of Air interface for IEEE 802.16 Physical Layer IEEE 802.16 supports multiple PHY layer specification and any of them can be used to combine with the MAC layer to provide a suitable end-to-end link. IEEE 802.16-2004 and IEEE 802.16e-2005 amendment defines five PHY alternatives that are described below along with their supported functionalities. 3.1.1. WirelessMAN-SC This is the first and only physical layer specification which has been designed to operate within 10-66 GHz frequency band using a single carrier line-of-sight (LOS) modulation, for point-to-point communication. In this variant a BS (downlink) normally transmits a time division multiplexing signal with individual user time slots serially. It utilizes a burst deign technique that allows both TDD and FDD where the alternatives of both TDD and FDD can be implemented to assign the transmission parameters, for instance modulation and coding scheme dynamically, to each user on a frame-by-frame basis. Besides TDD and FDD it also supports H-FDD SSs which is less expensive than full duplex FDD, as it does not transmit and receive simultaneously. The access technique in UL (uplink) direction are based on time division multiple access (TDMA) and demand assigned multiple access) DAMA. In addition, in DL it also specifies the modulation, forward error correction and Data randomization scheme (Ohrtman 2005: 22-24). 24 3.1.2. WirelessMAN-SCa This PHY is also based on single carrier modulation format but designed for NLOS environment to operate below 11GHz spectrum, providing a point-to-point communication. Time division multiple accesses (TDMA) are used in uplink direction and in downlink, access is done by either TDM or TDMA. TDD and FDD definitions are also included. It performs FEC for both UL and DL. Moreover it also includes framing structure which activates improved equalization and channel estimation for NLOS environment (IEEE802.16 std. 2004). 3.1.3. WirelessMAN-OFDM WirelessMAN-OFDM air interface is based on OFDM (orthogonal frequency division multiplexing) modulation technique which supports point-to-multipoint communication. This multicarrier modulation technique uses 256-subcarrier which operates within 2- 11GHz frequency band in a NLOS environment. Access is done by TDMA. Like other air interface, it implements TDD and FDD. Finally, as an optional support like transmit diversity and AAS (advanced antenna system) are also included here. Because of orthogonality between subcarriers, it saves almost half bandwidth than single carrier technique. This air interface is the most suitable candidate to support fixed SS related applications (Ohrtman 2005: 19-20). 3.1.4. WirelessMAN-OFDMA This PHY uses orthogonal frequency division multiple access (OFDMA) with at least one of the following FFT size 128, 512, 1024, 2048 support, to provide fixed and mobile BWA service in a NLOS environment. In this system multiple access are done by mapping a subset of carrier to individual receiver. Operations are performed under 11GHz frequency band in a PMP communication system. This option to choose any of the FFT size facilitates, to support various channel bandwidths. All other framing structure are same as OFDM PHY ,the notable exceptions are in OFDM-PHY a single time slot are defined for a single user where in this technique multiple user can share 25 same time slot with a group of subcarriers. This PHY has been accepted by WiMAX forum for portable and mobile operations (Ohrtman 2005; IEEE 802.16 Std 2005). 3.1.5. Wireless HUMAN Wireless HUMAN (Wireless High Speed Unlicensed metropolitan area network) PHY specification is similar to the OFDM based PHY which is targeted only for unlicensed frequency band below 11GHz. DFS is obligatory and for duplexing operation, it uses TDD only (Ergen 2009:271). Table 2: Air interface nomenclature (IEEE 802.16 std., 2004). Designation Frequency Band Duplexing Technique LOS/NLOS Function WirelessMAN- SC 10-66 GHz TDD, FDD LOS Point-to-Point WirelessMAN- SCa 2-11 GHz licensed bands TDD, FDD NLOS Point-to-multipoint WirelessMAN- OFDM 2-11 GHz licensed bands TDD, FDD NLOS Point-to-multipoint WirelessMAN- OFDMA 2-11GHz licensed bands TDD, FDD NLOS Point-to-multipoint Wireless HUMAN 2-11GHz licensed Exempt band TDD NLOS Point-to-multipoint 3.2. OFDM-PHY OFDM-PHY is the first standard of WiMAX PHY layer which uses orthogonal frequency division multiplexing technique for data transmission and it is being implemented worldwide in the area of fixed applications. It uses 256 fixed sub-carriers where 192 subcarriers are for carrying data, for channel estimation and synchronization 26 purpose 8 subcarriers are used called pilot subcarrier and the rest of the subcarrier are reserved for guard band. To overcome delay spread due to multipath and maintain frequency orthogonality it allows accepting variable guard time value 4, 8, 16, 32. If the channel is bad a high value of guard time is used otherwise the opposite will be considered. 3.2.1. Introduction to OFDM. The concept of orthogonal frequency division multiplexing came from the multi-carrier modulation technique (MCM). The idea behind the MCM technique is quite simple; to divide the transmitted high rate serial data stream into multiple parallel low rate sub- streams and then mapped each sub-stream with individual data sub-carrier. From Figure-3 we can see that high data rate stream R bps are divided into L parallel sub streams then each multiplied by individual carrier frequency. The number of sub-stream is chosen in such a way that gives the assurance that each sub-channel bandwidth is less than coherence bandwidth. Here the data rate and bandwidth on each sub-channel is much lower than the total data rate and the total system bandwidth. To protect subcarrier from overlapping, a guard band is used and at the receiver side a Low Pass Filter (LPF) is employed, to separate the spectrum of individual subcarrier (Goldsmith 2005:374). As compared to single carrier system, a single fade or interference can be a reason to fail the entire link but in multicarrier system only a small percentage of subcarrier will be distorted. OFDM is a special case of spectrally efficient multicarrier modulation technique which applies a closely spaced orthogonal overlapping subcarrier. Because of orthogonality nature among subcarriers, low pass filters are no longer required in receiver and the bandwidth can be used efficiently without causing ICI. In OFDM system by allowing subcarrier to overlap and removing the guard band, the required bandwidth greatly reduces, which is almost half compared to Non-overlapping MCM system. The orthogonality between subcarrier is achieved by implying IFFT to the input bit stream. Figure 4 shows that, because of, the combination of several multiple low data rate 27 stream in parallel fashion, OFDM provides a composite high data rate with longer symbol duration than multipath delay spread that reduces or sometimes completely removes the ISI (Nee & Prasad 2000: 21). However, to eliminate ISI effect completely OFDM introduces guard time interval, and during guard interval a cyclic extension of each OFDM symbol is also added to protect further from inter-carrier interferences (ICI), accepting some degradation of throughput (Fazel & Kaiser 2008: 31). Figure 3. A conventional multicarrier (FDM) transmitter. Figure 4. Comparison between conventional FDM and OFDM (Wu 2006). 28 3.2.2. Implementation of an OFDM system. The idea of using parallel data transmission by means of FDM was found between early 50’s and 60’s. But the implementation was delayed for lack of equipment which can support the digital implementation of Fast Fourier transform and Inverse Fast Fourier transform. Cooley and Tukey in 1965 published a paper reinventing the algorithm and described how to perform FFT efficiently (wiki). The first Fourier transform (FFT) and the inverse first Fourier transform (IFFT) are merely a rapid mathematically equivalent version of discrete Fourier transform (DFT) and inverse discrete Fourier transform (IDFT), but it can be implemented more efficiently, for example, an N point IDFT requires N 2 complex multiplication but IFFT drastically reduces the number operation from N 2 to NlogN (Nee et al. 2000: 21-24). The DFT and its counterparts IDFT is basically used for transforming data between time domain and frequency domain. For instance IDFT is used to convert data from frequency domain to time domain, where the transformations are performed by mapping frequency domain data onto orthogonal subcarriers, and to do this, it correlates frequency domain input data with its orthogonal basis functions (Litwin & Pugel 2001). The implementation of OFDM technique is presented in Figure 5, where the input data stream is first modulated by a QAM modulator, results a complex symbol stream X [0], X [1] …X [N-1]. Figure 5. A simplified OFDM Transmitter. 29 This stream is then fed to a serial to parallel converter, whose output is a set of N parallel QAM symbols X[0], X[1]….., X[N-1] corresponding to the symbols transmitted over each of the subcarriers. The transformation of symbol from serial-to- parallel, results an increased in symbol duration, thus helps to protect data from ISI. Now, these N complex symbol output from S\P converter are the discrete frequency components of the OFDM modulator output S(t). To create S(t) we need to convert the frequency domain component into time samples by performing IDFT for every symbol which can be implemented efficiently through IFFT algorithm. The IFFT creates one OFDM symbol containing the sequence x[n] = x [0], x [1]………...x [N-1] of length N, where     1Nn,0eiX N 1 nx Nij2 1N 0i      (3.1) Each complex symbols X[i] are modulated by N orthogonal sinusoid e j2πit/T(n) ,i=0,……,N-1 and each input symbol determines the phase and amplitude of the sinusoid. After performing IFFT operation, cyclic prefix are added at the beginning of each OFDM symbol and the resulting time samples  nx ~ are then passed through P/S converter to arrange it serially. At the end, this digital data are converted from digital to analog, resulting an OFDM signal )( ~ tx and then up-converted to carrier frequency f0 for transmission to the channel. At the receiver side the opposite procedure are performed where the received signal r(t) is first down converted to baseband signal and then passed into LPF to remove the higher frequency components. The received signal y[n] is found after A/D conversion and can be expressed as       1Nnμ , v[n]+ nh |n x= ny  (3.2) 30 Figure 6. A simplified OFDM receiver. Where -µ denotes the cyclically extended signal which had been added at the beginning of each OFDM symbol. In this stage first -µ samples are removed from received signal then data are transformed from serial to parallel. Now DFT are applied by FFT algorithm to this ISI free N time samples which results an original multicarrier demodulated sequence  iX , in frequency domain.     1Ni,0enx N 1 iX j2Π2Πni 1N 0n      (3.3) Moreover after DFT operation the output Y[i] without noise lookalike     ,1Ni,0iH*iXΥi  (3.4) Where H[i] is the flat fading channel gain associated with each subcannel. At last this sequence again converted from parallel to serial and passed through a QAM demodulator results the recovered original data (Goldsmith 2005: 386-388). 3.2.3. Guard Time and Cyclic Prefix One of the major problems in most wireless communication systems is the presence of multipath channel. When the transmitted signal travels through the air it reflects, 31 diffracts, thus a multiple delayed version of transmitted signal reaches to receiver which causes the received signal to be distorted. Multipath channel causes two different types of problem in OFDM, namely ISI, which occurs when the received symbol distorted by the previous transmitted symbol (Inter-symbol interference) and ICI (Inter-carrier interference) which occurs within the OFDM symbol, by crosstalk between subcarriers. The orthogonality among sub-channels can be maintained and each sub-channel can be separated completely by the FFT at the receiver when there is no such problem introduced by the transmission channel. In order to mitigate this effect OFDM performs data segmentation. This segmentation of data from Serial to parallel increases the symbol duration, thus it helps to reduce the effect multipath delay spread Max signal. From the Figure-7 it can be seen that only few samples of OFDM symbol is affected by ISI. Max < Ts = Td * Ns , Ns= Total subcarrier, Td= serial data symbol duration, Ts = Total symbol duration after S/p transform. Figure 7. Example Inter-symbol interference. The green symbol was transmitted first followed by the blue symbol. However, this method does not eliminate ISI problem completely. To mitigate this effect OFDM includes a guard time interval after each symbol. This guard time is chosen larger than the expected delay spread, so that multipath components of one symbol cannot interfere to the next symbol (Litwin et al. 2001). Then the total symbol duration can be expressed as, Ttotal = Ts + Tg . These guard intervals may contain no 32 signal at all, as it will be discarded at the receiver side. In practice this empty guard band introduces the ICI problem, because of crosstalk between subcarriers, which indicates the subcarriers are no more orthogonal. ICI in OFDM is prevented by cyclically extending the OFDM signal or cyclic prefix, within guard interval, which is the replica of the last part of an OFDM symbol (Ts), append at the beginning of each symbol. This ensures the presence of integer number of cycles in the symbol time, as long as delay is smaller than the guard time, which makes the transmitted signal periodic. By providing periodicity to the OFDM source signal, CP gives assurance that the subsequent subcarriers are orthogonal thus ICI and ISI can be removed completely (Matie 1998; Litwen et al. 2001). Figure 8. Example cyclic prefix in frequency domain (Matie 1998). 3.2.4. OFDM system design requirement There are several requirements that need to be considered to design an OFDM system. The choices of these parameters are very critical and often conflicting. The aim of an OFDM system is to decrease the data rate at the subcarriers, so that the symbol duration increases, thus the multipath effects are efficiently removed. The guard time directly affect delay spread. Higher values of cyclic prefix during guard time gives better result against delay spread but it also increases the loss of signal-to-noise ratio. So the tradeoff between these requirements must be considered for a reasonable design. The following three are the main requirement to design OFDM system (Nee et al. 2000:46). 33  Bandwidth: Bandwidth is the most crucial and scarce resource in wireless communication system. The available bandwidth plays an important role to determine the number of subcarriers because large bandwidth allows increasing symbol duration with reasonable guard space.  Required bit rate: The system should support the required bit rate specified by the user.  Tolerable delay spread: Delay spread depends on the specific environment where the user will implement this system. So according to delay spread the length of cyclic prefix should be determined (Rahman, Das & Fitzek 2005). 3.2.5. Essential OFDM Design Parameters in WiMAX. The design parameters of OFDM in WiMAX are determined based on the system requirement. There are two types of OFDM parameter used in WiMAX, (primitive and derived) which characterizes the OFDM symbol completely. Derived one can be calculated from the primitive ones, as it has the fixed relation among them. Primitive parameters: (1) Available channel bandwidth (BW), (2) Number of used subcarrier (data and pilot), (3) Sampling factor (n=Fs/BW), (4) Cyclic prefix or guard time (G), Derived parameters: 1. Fast Fourier Transform size (NFFT) . 2. Sampling frequency Fs 3. Subcarrier frequency spacing (Δf = Fs/NFFT) 4. Useful symbol time (Tb = 1/ Δf) 5. Cyclic prefix time (Tg=G.Tb) 6. OFDM symbol duration (Ts= Tb+Tg) 7. Sampling time (Tb/NFFT) (IEEE 802.16 std, 2004). 34 Table 3: OFDM parameters used in Fixed and Mobile WiMAX (Andrew et al. 2007:42). 3.2.6. Advantages and Disadvantages of OFDM. There are lots of advantages of OFDM technique. As we have explained before that how OFDM combats with ISI and reduce ICI problem. Besides those benefits, there are some other benefits which OFDM provide are as follows:  FFT reduces the OFDM implementation complexity, which is much lower than single carrier system.  High spectral efficiency which is maintained by orthogonality nature of subcarrier.  It is useful for high-data-rate transmission. 35  Robust against multipath because it affects only small portion of subcarrier (Nee et al. 2000:24).  It’s resistance to frequency selective fading is more than single carrier system.  To use maximum likelihood detection is possible in OFDM with reasonable complexity.  Single frequency networks are possible by OFDM which is especially attractive for broadcast application (Rahman et al. Fitzek 2005). On the other hand there are also some disadvantages compared to single carrier modulation technique which are as follows:  OFDM is more sensitive to time and frequency synchronization error. Demodulation of an OFDM signal with frequency offset provides high bit error rate (Nee et al. 2000:24).  OFDM system has higher peak-to-average power ratio (PAR) than single carrier system. High PAR makes difficult to implement ADC and DAC in OFDM system (Rahman 2005). Besides it also reduces the efficiency and increases the cost of power amplifier (Andrew et al. 2007: 131).  Loss of spectral efficiency due to cyclic prefix insertion (Fazel et al. 2008:35). 3.3. OFDMA-PHY This section explains the OFDMA method and some additional features which help to improve the performance of this technique. 3.3.1. OFDMA Basic OFDMA-PHY is based on OFDMA technique which is a multiple access/multiplexing 36 scheme closely related to OFDM. In OFDM the input data is divided into multiple parallel sub-streams of reduced data rate and each sub-stream is modulated (by IFFT) and transmitted on a different orthogonal subcarrier. OFDM allows only one user at any given time, to allow multiple accesses it implements TDMA or FDMA. OFDMA (Hybrid FDMA and TDMA) works one step further it provides multiplexing operations of data streams from multiple users onto the downlink sub-channels and uplink multiple access by means of uplink sub-channel. It is actually a multiuser OFDM which distributes subcarriers among users so that every user can transmit and receive data at the same time within a single channel. This PHY model is widely used in IEE802.16e standard also called mobile WiMAX. OFDMA has a lot of advantages compared to fixed WiMAX modulation technique OFDM, is its potential to reduce the transmit power and peak-to-average-power ratio problem. By dividing the subcarrier among the users thus each SS uses a group of subcarrier which transmits a lower PAPR as PAPR increases with the number of subcarriers and less power than it had to transmit through the entire bandwidth (Andrew et al. 2007: 204). 3.3.2. Scalable OFDMA One of the most important features of OFDMA in IEEE802.16e is its scalability nature. In mobile WiMAX, FFT size is scalable within 128 to 2048 where, FFT size indicates the number of subcarrier. Because of this OFDMA subcarrier structure, it can support a wide range of bandwidth. Scalability is performed by adjusting the FFT size to the appropriate channel bandwidth (1.25-20 MHz) while keeping the subcarrier spacing 10.94 KHz. Smaller FFT size is given to lower bandwidth channels and larger FFT size to wider bandwidth channels. By keeping the sub-carrier spacing constant, SOFDMA reduces the system complexity of smaller channels and improves the performance of wider channels (Wimax_part1 2006). By fixing the symbol duration and subcarrier spacing the basic unit of physical resource- time and frequency can be fixed, for this reason the impact to higher layers during bandwidth scaling becomes minimal. Table 3.3.1 shows the scalability parameters used in mobile WiMAX. One immediate advantage of this scalability feature is the flexibility of deployment. By doing a little 37 modification to this air interface, it is possible to deploy OFDMA system in various frequency band intervals to flexibly address the need for various spectrum allocations and usage model requirement (Yin & Alamouti 2006). Table 4: OFDMA scalability parameters. Parameters Values System Channel Bandwidth 1.25 2.5 5 10 20 Sampling frequency (Fs, MHz) 1.429 2.875 5.714 11.429 22.857 FFT Size (NFFT) 128 256 512 1024 2048 Sample time (1\Fs) 700 350 175 88 44 Sub-Carrier Frequency Spacing 11.16071429 Useful Symbol Time (Tb= 1/f) 89.6 µs Guard time(Tg=Tb/8) 11.2 µs OFDMA symbol time (Ts =Tb+Tg) 100.8 µs 3.3.3. OFDMA Symbol Structure and Sub-channelization An OFDMA symbol structure consists of a number of sub-carrier which is equal to FFT size and these sub-carriers are further divided into three groups 1. Data subcarrier used for data transmission 2. Pilot sub-carrier used for various synchronization and channel estimation purpose. 3. Null sub-carrier no transmission at all, it is used for guard band and DC subcarrier (Yagoobi 2004). 38 Figure 9. OFDMA subcarrier structure (Wimax_part1 2006). To support multiple accesses in OFDMA the available active subcarriers (data and pilot) are divided into multiple groups of Subcarriers called sub-channels. Sub- channelization forms sub channel that can be allocated to a user depending on their channel condition and data rate. Using sub-channelization within a single time slot, a BS can allocate lower transmit power to MS with higher signal-to-noise ratio and higher transmit power to the subscriber stations which has lower SINR. In uplink direction sub-channelization scheme saves user device transmit power because it only concentrate certain sub-channel which has been allocated to it, that’s why it is widely used in mobile WiMAX. Figure 10. Sub-Channelization OFDM Vs OFDMA (Ministry of Communication & Technology India). 39 However, Fixed WiMAX which is based on OFDM-PHY allow sub-channelization only in uplink. On the other hand OFDMA-PHY allows sub-channelization in both uplink and downlink direction. A sub-channel is basically a logical collection of subcarriers. The number and distribution of this subcarrier depends on the permutation mode. WiMAX offers two types of permutation modes, distributed and contiguous. In general distributed subcarrier permutation mode performs well in mobile applications because it provides higher frequency diversity. On the other hand, contiguous permutation mode are more desirable for fixed, portable and low-mobility application as it offers multiuser diversity by allocating subcarrier based on their frequency response (Andrew et al. 2007: 43-45). Diversity Permutation This is also known as distributed permutation. It creates sub-channel by distributing the subcarrier in pseudo-random way. This permutation mode offers Downlink Full Usages of Subcarrier, DL partial usages of subcarrier and UL partial usages of subcarrier and some additional optional permutation modes like OPUSC, OFUSC and Tile Usages of Subcarrier (DL TUSC1 and DL TUSC2). Contiguous permutation Sub-channelization scheme based on contagious permutation are also known in WiMAX as band Adaptive Modulation and Coding (AMC) which creates sub-channel by arranging all the subcarriers which are adjacent to each other. This permutation mode offers AMC both in UL and DL direction (Wimax_part1 2006). 40 Table 5: Permutation Tradeoff (Ministry of Communication & Technology India). Contiguous subcarrier permutation (AMC) Diversity subcarrier permutation (PUSC, FUSC) Benefits Sub-channelization gain; Frequency selective loading gain Sub-channelization gain; Frequency diversity; Inter-cell Interference averaging Scheduling Advanced frequency scheduler to explore frequency selectivity gain Simple scheduler; Rely on frequency diversity to achieve robust transmission Channel condition Stationary channel Fast-changing channel Favorable smart antenna technology Beamforming MIMO 3.3.4. Multiuser Diversity and AMC In order to maximize the throughput of an OFDMA system, the subcarrier and power allocation should be performed based on the channel condition. There are two key mechanisms which enable high performance in OFDMA system; one is the multiuser diversity, which is basically describes the available gains by selecting a user or a group of users having good conditions. Adaptive modulation and Coding (AMC), is another important amendment in IEEE802.16e which is being used to increase the overall system capacity. In order to get such benefits OFDMA based PHY supports a variety of modulation and coding schemes which may change on a burst-by- burst basis per link, based on their channel condition. By using channel quality indicator (CQI), MS sends to the BS the downlink channel quality and from the received signal BS estimates the uplink channel information. The basic idea of AMC is to take the advantage in the randomness of the channel. When the channel is good transmit as high data rate as possible and transmit lower data rate when the channel condition (SINR) is poor in order to avoid excessive packet loss 41 (Ergen et al. 2009:183). Lower data rates are achieved by using small constellation size (like QPSK) and low error correcting codes (1/2 convolution or turbo codes). Higher data rates are achieved by using large constellation size (64QAM) and higher error correcting codes (LDPC codes or ¾ convolution codes). Table 3.3.3 shows the various modulations and coding scheme used in WiMAX (Andrew et al. 2007:206). Table 6: Data rates for various modulation and coding scheme (Andrew et al. 2007: 47). 3.3.5. Hybrid Automatic Repeat Request (HARQ) In addition to improve the link performance through AMC and CQI, IEEE-802.16e has also introduced HARQ at the physical layer to speed up the retransmission of frames which has been received in error. In an ordinary ARQ system only the error detection codes are used to decide retransmission but in H-ARQ not only error detection but error correction code (FEC) also used during transmission. WiMAX offers two types of H- ARQ called chase combining and incremental redundancy. 42 In chase combining, data blocks with CRC are fist encoded using FEC coder before transmission and retransmission is requested only when the decoder fails to decode the received block. This technique combines the received coded block (with error) with the retransmitted coded block and improves the chances of correctly decoding by FEC decoder. In incremental redundancy, which is an optionally support H-ARQ where each retransmitted block is coded differently to increase the performance gain (Ergen et al. 2009:31; Andrew et al. 2007: 56). 3.3.6. Adaptive Antenna System (AAS) AAS is an advanced antenna technology that has been introduced in IEEE 802.16e standard to improve the system capacity gain and spectral efficiency. In an Adaptive Antenna system a BS adaptively tracks mobile receivers when it enters into the coverage area and focuses it’s transmit energy to the direction of the receiver. While receiving, it also focuses on the transmitting device. The technique used in AAS is called beam steering or beam forming, that are performed by adjusting the width and height of the antenna radiation pattern. AAS creates narrow beam to communicate with the intended user, which helps to eliminates interference to or from unintended user and improves carrier to interference ratio (C\I) and frequency reuse, giving rise to spectral efficiency. In addition AAS also included SDMA technique which offers multiple antenna support to serve multiple SS separately at the same time with higher throughput (Zhang & Chen 2008b: 406; AAS 2009). Figure 11. Adaptive antenna technique (Zhang et al. 2008b: 405). 43 3.4. MAC LAYER This Section explains the details of various sublayers inside the MAC and their operational procedure, in addition some other features like mobility, power saving and scheduling technique has also been explained which enhances the MAC layer performance. 3.4.1. Architecture of MAC Layer In general, WiMAX standard has designed MAC layer in such a way that it can support a point-to-multipoint architecture with a central BS handling multiple independent sectors simultaneously. On the downlink, data to the subscriber stations are multiplexed in TDM fashion and the UL is shared by the SSs using TDMA technique (Eklund & Wang 2002). WiMAX provides a connection oriented MAC layer, the primary task of this layer is to provide an interface between the physical layer and the higher layer. It performs by taking packets from higher layer-called service data units (SDUs)-then it organizes the packets into MAC protocol data units (MPDUs) for transmission to the destination through the air. As we have described before, the MAC layer consists of three different sublayers where each sublayer performs different task (Andrew et al. 2007:47). The first sublayer in MAC, which takes packet from higher layer, is called Service specific convergence sublayer often simply known as convergence sublayer (CS). WiMAX standard has defined two general service specific convergence sublayers for mapping services to and from MAC connection, one is ATM based, however WiMAX forum has decided not to use it right now and another one is packet based services such as IPv4, IPv6, Ethernet and VLAN etc. The main task of this sublayer is to classify service data units (SDUs) to the appropriate MAC connection, preserve QoS and enable bandwidth allocation. To perform, it map’s the higher layer address of the Service Data Unit’s for example IP address onto the identity of the PHY and MAC connection which will be used for its transmission. This mapping takes place in several ways depending on the type of service. In addition to this basic function it also performs more 44 sophisticated functions like Packet header suppression and reconstruction- which will be described in the next section -to enhance airlink efficiency (Ohrtman 2005:34; Eklund et al. 2002). The other two sublayers are Common Part Sublayer and Security sublayer respectively. Figure 12. WiMAX medium access control (MAC) layer. The second part called Common Part Sublayer (CPS), is the core functional sublayer of WiMAX MAC layer. This sublayer is independent from higher-layer protocol and handles several operations for instance ARQ, modulation, bandwidth allocation, connection establishment, connection management, QoS management and code rate selection. MAC SDUs are gathered from the CS layer through the MAC service access point (SAP) to the CPS and converted into MPDUs. This sublayer is also responsible for packing and fragmentation of SDUs which will be described in details in the next section. Security sub layer is the third sublayer of IEEE 802.16 MAC layer which ensures security for reliable transmissions and receptions of MAC PDU through the medium (Andrew et al. 2007: 312; Zhang et al. 2008b). 45 3.4.2. Packet Header Suppression One of the main tasks of Convergence sublayer is to perform packet header suppression. Header suppression is performed by removing the repetitive part from the each SDU, for example, if the service data unit transferred to the CS is IP packet then the header (contains source and destination address) of each packet will be same thus can be removed before transmission over the air. Similarly on the receiver side the header can be inserted back again into each SDU before delivering to the higher layer. It is an optional feature in WiMAX but most of the systems like to implement this as it increases the efficiency of a network when the packet size becomes very small such as in VoIP. Figure 13. A basic operation of header suppression in WiMAX. The PHS operation is setup during the dynamic service flow creation between BS and MS. There are several predefined PHS rules are used in this operation which contains all the parameter related to header suppression of SDUs. The PHS rules depend on the type of service it is dealing with such as VoIP, HTTP, FTP, etc. as the number of bytes will be suppressed in the header vary from service to service. When CS receives a SDU from higher layer it first checks whether there is any PHS rule exist for that SDU. Once a matching rule is found, it provides a SFID (SFID is an identifier used to identify a 46 particular service flow also called MAC transport service, used for transmission of UL and DL traffic and contains a unique set of QoS parameter), a CID (a logical unidirectional connection between BS and MS) and other PHS related parameter which helps to determine the portion of the header will be suppressed called PHSF and the part will not to be suppressed referred as PHS mask (PHSM). Suppressed MAC PDU is then added to the PHSI according to PHS rule. It is also possible to verify the PHSF using PHSV which is basically compares the PHSF with what is expected according to PHS rule. If it does not match then PHSI is set to 0. In the receiver side PHSI is used to find out the PHSF and PHSM from the PHS rule to reconstruct the removed portion of SDUs (Ergen 2009:312; Andrew et al. 2007: 309-312). 3.4.3. MAC PDU Formats and Transmission MAC SDUs arriving at the MAC Common-part sublayer from the higher layer are concatenated or fragmented to create MAC PDU. The decisions are taken based on the size of the pay load unit, either multiple SDUs will be carried on a single MAC PDU or a single SDU will be fragmented to be carried over multiple MAC PDUs. During fragmentation each fragment within the service data unit (SDU) is tagged by a sequence of number so that in receiver side the MAC layer can assemble the SDU from its fragment in the correct order. Moreover to use the physical resources efficiently, MAC layer at the transmitter also concatenates multiple MAC PDUs, which destined to the same receiver and transmits through a single transmission opportunity as shown in Figure 14. Now before transmission this fragment may need another modification that is, if the connections which will be used for transmission are not Automatic-Repeat- Request (ARQ) enabled, and then each fragment of SDU will be transmitted sequentially. For ARQ enabled connections, each SDU is partitioned into fixed length ARQ blocks (Length is defined by BS for each CID) and each block is assigned by block sequence number (BSN). This partition remains active until all the blocks received and acknowledged by the receiver. After the partition, the MAC SDUs is assembled into MAC PDUs in a normal fashion as described before. 47 Figure 14. Segmentation and concatenation of MAC SDUs. A MAC PDU not only consists of fragmented SDU (Payload unit) but it contains also cyclic redundancy check (CRC), a header and may contain subheader as shown in Figure 15. Figure 15. Generic MAC PDU format (Nuaymi, Bouida, Lahbil & Godlewski 2007). WiMAX uses two types of PDU. One for carrying, data and MAC layer signaling message (referred as Generic MAC PDU) and other one is called bandwidth request PDU, used by MS to indicate BS that more bandwidth is required in UL. An important thing of bandwidth request PD is, it consists of only bandwidth-request header with no payload and no CRC. Besides generic and bandwidth request header WiMAX also defines five different subheaders, which can be used in generic MAC PDU, are as follows- 48  Mesh subheader is used during mesh networking.  Fragmentation subheader indicates SDU is fragmented over multiple MAC PDUs.  Packing subheader indicates multiple MAC SDUs or SDU fragments are packed into a single MAC PDU and placed at the beginning of each SDU or SDU fragment  Fast-feedback allocation subheader describe that PDU contains feedback information from MS about DL channel state information.  Grant-management subheader is used to carry information about bandwidth management such as polling and additional bandwidth request. It is more suitable than bandwidth request header as there is no need for transmitting a new PDU (Andrew et al. 2007:312-315). After constructing a MAC PDU it is handed over to the scheduler, which schedules the MAC PDUs over the available PHY recourses. This scheduler checks the CID and SFID to determine the required QoS of MAC PDUs. Based on the required QoS of MAC PDUs, which belong to different CIDs, scheduler determines the optimum PHY resource allocation for all MPDUs on a frame by frame by frame basis. QoS is achieved by implementing AMC and ARQ for each CID’s individually. Finally MAC PDUs are passed through Security sublayer to prevent from theft of service (Tran, Halls, Nix, Doufexi & Beach 2009). 3.4.4. Security Security is one of the most important parts of any BWA communication system. WiMAX offers a robust security mechanism by its security sublayer which lies between MAC CPS and PHY layer. This sublayer is responsible for encryption and decryption of data travelling to and from the physical layer and also used for secure key exchange and authentication of user/device. Besides it also supports security enhancement for fast handover technique. The basis for WiMAX security is provided by privacy and key management protocol of version1/2 (PKMV1/2). The fixed WiMAX supports only 49 version1 while mobile WiMAX uses both of them. The key aspects of WiMAX security are as follows: Device/User authentication When Mobile WiMAX device is active it tries to connect to a BS. However a reliable connection between BS and SS has to be ensured. This can be done by mutual or one sided authentication (the BS authenticates the MS). To support this authenticity mobile WiMAX uses PKM (Privacy and key management protocol) which allows securely transferring of keying material from BS to MS. It also allows periodically reauthorizing and refreshing the keys. PKM introduces/produces various types of authentication frame work like EAP (Extensive Authentication protocol), X.509 digital certificate with RSA based public key encryption algorithm. Besides there is also another option which is RSA based authentication followed by the EAP authentication. The PKM authentication framework creates a shard secret key called Authorization key (AK) between BS and SS. After the establishment AK, the key encryption key (KEK) is derived from it which is later used to encrypt subsequent PKM exchanges of traffic encryption key (TEK). (Analysis of Handoff Performance 2007: 21-23; Airspan Communications Limited 2007: 24). Traffic Data Encryption Mobile WiMAX uses robust cryptographic scheme such as AES (Advanced encryption standard) or 3DES (Triple Data Encryption Standard) for the encryption of user data thus it ensures user data privacy across the communication link. A 128-bit or 256-bit key is used here (called TEK) to derive the cipher text which is generated during the authentication process and is periodically refreshed for additional protection (Cuilan 2009). Protection of control messages WiMAX standard also provides security mechanism for the control/management 50 message by using message digest schemes such as AES based CMAC (Cipher Message Authentication code) and MD5 based HMAC (Hashed Message Authentication Code). Fast handover support IEEE 802.16e standard also included fast handover support for the privacy of the data exchanged during the change of BS so that the Man-in-the-middle attack problem becomes possible to prevent. To do this it allows the SS to use pre-authentication, which means it can perform authentication with a target BS before the initiation of handover session in order to facilitate accelerated reentry (Analysis of Handoff Performance 2007:23). 3.4.5. MAC Scheduling Services One of the key functions of MAC layer in WiMAX is scheduling which has a direct effect on its performance. Basically scheduling technique helps to provide service guarantees to composite classes of traffic where each traffics represents a different QoS requirement (Zhang 2008a: 33). In WiMAX, MAC layer has been designed such a way that it can provide broadband data service including voice, data, and video over the time varying wireless channel. To support a wide variety of application MAC layer uses five UL scheduling services, also called data handling mechanism for data transport on a connection (Wimax_part1 2006), are as follows  Unsolicited Grant Service (UGS): It has been designed to support real-time service flows that creates fixed size data packet at a constant data rate with periodic basis transmission requirements for example T1/E1 and VoIP without silence suppression. It also offer real-time periodic-basis fixed size grants that’s why SS does not need to explicitly request bandwidth thus it can reduce the overhead and latency associated with bandwidth request.  Real-Time Polling services (rtPS): This service is designed to support a real- time service flow like UGS but here it deals with variable size data packets generated on a periodic basis, for example MPEG (Motion Pictures Experts 51 Group) video stream. In this service BS offers SS unicast polling opportunities to request bandwidth and these opportunities are frequent enough that it can fulfill the latency requirements of a real-time service. The rtPS creates more request overhead than UGS but offers optimum transport efficiency for variable size data packet.  Non-Real-Time Polling Services (nrtPS): It Supports delay tolerant data streams for example an FTP, which requires variable size grants with minimum guaranteed rate. It works like rtPS but the only exception is that in UL it also can use contention-based polling to request bandwidth. It also has unicast polling opportunities to request bandwidth but the average duration between two opportunities is larger than rtPS. This service has one disadvantage that is, all the SS belong to this group can request resources during unicast polling which may create collisions thus require additional attempt.  Best-Effort service: BE service is intended for such traffic which does not require a minimum service level guarantee such as Web browsing. Here data can be sent whenever resources are available and do not require any other scheduling service classes. To request bandwidth, SS uses only contention based polling opportunity.  Extended Real-Time Polling services (ertPS): The ertPS is a new scheduling service has been added in IEEE 802.16e which is the combination of both rtPS and UGS scheduling services. It supports real-time application like VoIP but require guaranteed data rate and delay. Here the BS offers unicast grant service in an unsolicited manner thus it saves the latency of a bandwidth request. In this case BS provides periodic uplink allocation that can be used either for data transmission or for requesting bandwidth. This feature allows ertPS to offer data services for variable bandwidth required user whose requirement changes with time (IEEE802.16 Std. 2004: 138-141). 52 3.4.6. Power Saving Features Mobile devices are intended to add day by day more and more processing units and functionalities which have a negative effect on battery life. To support such battery operated devices IEEE 802.16e standard has introduced power saving features which allow mobile SS to operate longer time without having recharge. This power saving mechanism is achieved by switching off some parts of the MS when it is not actively transmitting or receiving packet. Mobile WiMAX uses Idle mode and Sleep mode signaling method to maintain connection during this inactive period (Andrew et al 2007:52). Sleep mode, In WiMAX Sleep mode is being used as an optional mode of operation (for MS but mandatory for BS) where MS switched itself off and becomes unavailable for a predefined time (timing is scheduled before hand between BS and MS). The length of this time is dependent on power saving class of sleep mode operation and is called sleep window. After each sleep window there is a listen window during which MS restores its connection. In Figure 14, when all the MS’s are within the period of sleep window is referred to as unavailability interval, during this time MS neither receive nor transmit so the MS may power down one or more of its physical components and can save power. Figure 16. Sleep-mode operation in IEEE 802.16e with two power saving class (IEEE802.16e Std. 2005: 228-232). 53 Further IEEE802.16 has divided Sleep mode into three different classes based on different scheduling services such as PSC-I, PSC-II and PS-III. The detail of each PSC is as follows. Power Saving Class I This power saving class is recommended for the Best effort (BE) or Variable-Rate NonReal-Time (VR-NRT) traffic. In this class a variable duration of sleep window is used. This procedure begins with a sleep request message from MS to BS and in response BS sends initial and final sleep window size to the MS. After that it enters into sleep mode which follows a small listening window to check whether any downlink packets exist or not. If negative results appear then the next sleeping window starts with double length compared to first one and repeats doubling until it reach to the final window, else it performs normal operation to receive DL packet. At any time BS can reset the window size, in DL reset happens if the listening window is not sufficient to send all packet and in UL if the MS requests. Figure 17. Power Saving Class I operation. 54 Power Saving Class II It supports delay sensitive real time constant or constant bit rate traffic. It is recommended for UGS and real-time variable rate services like VoIP or real time video streaming. Because of delay sensitive service, its sleep and listen window size are fixed and each time period is maintained according to real time service. Another difference compare to PSC-I is here transmission and reception of data are done within listen window then goes to sleep window but in PSC-I for incoming traffic during listen window MS returns to normal operation. Figure 18. Power Saving Class II operation (Kwon & Cho 2009). Power Saving Class III Unlike other classes, it is a base station initiated sleeping mode operation, consists of a single sleep window (Final-sleep window) and no listening window, which is recommended for multicast traffic or MAC management operation such as periodic ranging. For multicast traffic BS may guess when the next portion of data will appear based on that it allocates sleep window in between arrival of data. If it cannot guess it initiates sleep window for all time (till final sleep window). After that it may initiates another power saving class. From Figure 15, we can see MS also initiates and stops sleeping window based on TLV (Type/Length/Value) encoded in RNG-RSP message 55 where the difference between TLV’s encoding indicates the size of the next sleeping window. It starts normal operation at the next frame if difference becomes zero (Zhang 2008a: 181; Kwon et al. 2009). Figure 19. Power Saving Class III operation (Kwon et al. 2009). Idle mode, is an optional features in WiMAX even it allows more power savings than sleep mode operation. This mechanism offers MS to completely switch off and also allows MS (without UL transmission) to receive broadcast downlink traffic from the BS without registering itself with any specific BS. It helps the MS by removing the active requirements for handover process and also helps the BS to reserve its PHY and MAC resources which need during handoff session. Idle mode works by dividing the BS’s into several logical groups called paging group. During idle mode MS periodically scans the DL transmission of the network to find out the existing paging group where it is located and if any movement found it updates the paging information and informs the current paging group. Without the paging area technique network would need to page MS to the entire BS’s inside the network thus it reduces the signaling overhead. The paging area should make large enough so that the most of the MS stays within the same paging group and do not need to update paging area too often and also small enough in order to avoid excess paging overhead. The BS groups are overlap each other and also a BS may belong to more than one paging group (IEEE802.16e std. 2005:259-260; Andrew et al. 2007: 327). 56 Figure 20. Example of paging group (IEEE802.16e std. 2005:259). 3.4.7 Mobility Mobility management is one of the most important amendments in IEEE 802.16e which has made mobile WiMAX version the future of the wireless Metropolitan area network (WMAN). Basically IEEE 802.16e has defined the signaling mechanism to track the MS when it moves from one BS’s coverage area to another when active-called handover- or as it moves from one paging group to another when it is idle- called roaming. It also supports seamless handover. Besides fixed broadband access, WiMAX also proposed four mobility related usage scenarios, they are as follows  Nomadic: The user is allowed to take a fixed SS and the user can reconnect from different point of attachment.  Portable: Nomadic access is provided to the portable devices for example PC card with the expectation of a best effort handover.  Simple mobility: In this scenario a user can move up to 60 kmph speed with interruptions less than 1 sec during handoff. 57  Full mobility: In full mobility user get the opportunity to move at a vehicular speed up to 120kmph with seamless handoff while maintain connection. It also supports latency of less than 50ms along with packet loss less than 1%. WiMAX offers three handoff techniques to provide users mobility of which one is mandatory called hard handover (HHO) and other two are optional named fast base station switching (FBSS) and macro diversity handover (MDHO). Hard handover (HHO): It is a mandatory and the only handover type which is initially implemented by the mobile WiMAX. Hard handover signifies a sudden transfer of connection from one base station to another as the MS is allowed to communicate with one BS at a time. That’s why all the connection with the serving BS are broken before a new connection is established. The handover decision can be made by the BS, MS or third party on the basis of the periodic measurement done by the MS (A MS periodically scans and measures the signal quality of the neighboring BS). Once the handover decision is made, the SS starts the process of synchronization with the downlink transmission of the target BS, performs ranging if it had not been done before, and terminates the connection with the previous BS (Andrew et al. 2007:53; Hasan et al. 2009). Figure 21. Hard handover (Dotted line indicates threshold for HHO execution) (Zhang 2008a:156). 58 Fast base station switching (FBSS): In this method MS maintains a valid connection with more than one BS. The MS maintains a list of BS’s referred to as active set then monitors continuously. During monitoring it does ranging and maintains a valid CID with each of them within the active set. Nevertheless, it is allowed to communicate only with one BS called anchor base station. Whenever a change of anchor BS needed, the connection just switched to new anchor BS without performing handoff signaling as the MS only sends the new anchor BS’s Id on the CQICH. Figure 22. Fast Base Station Switching (Hasan et al. 2009). Macro diversity handoff (MDHO): Like FBSS, MDHO is also a form of soft handover; the only difference is, in MDHO method the MS communicates with all the base stations in the downlink and uplink within the active set, called diversity set. 59 Figure 23. Macro Diversity Handoff (Hasan et al. 2009). In downlink MS receives multiple copies of packet from different BS then it combines the data using the well-known diversity-combining method. On the other hand for the uplink traffic, MS transmits data to multiple base stations and selection diversity is performed at the receiver to receive data, on the basis of best (Hasan et al. 2009; Zhang 2008a: 156-158). 60 4. RESOURCE ALLOCATION TECHNIQUES FOR OFDMA. One of the most challenging issues for future wireless communication system is to support a large number of subscribers and to guarantee the fulfillment of required quality-of-service, given the limited availability of the resources, frequency spectrum and power (Zhang and Letaief 2009). To solve this issue WiMAX utilizes orthogonal frequency division multiple access technique which is an extension of OFDM technique for multiuser applications, in which each user is assigned a subset of subcarriers and each subcarrier, is allocated exclusively to just one user (Gao, Cui & Li 2006). The subcarriers, generated by OFDM are allocated to different users, based on feedback information about the channel conditions so that the subcarriers and power are assigned to the user which see good channel gain on them ,to exploit system diversity such as frequency channel diversity and multiuser diversity (Zhang et al.2009). There are several ways to take advantage of multiuser diversity and adaptive modulation in OFDMA systems. Algorithms that take advantage of these gains are not specified by WiMAX standard which has been left off for the WiMAX developer to develop their own innovative procedures (Andrew et all. 2007:209). However, the main idea is to develop algorithms for determining which users to schedule, how to allocate subcarriers to them and how to determine the appropriate power levels for each user on each subcarrier (Khedr, El-Rube, Hanafy and Abou-zeid 2008). In this chapter we have considered some of the possible approaches of resource allocation algorithm for the downlink of an OFDMA system. In the downlink of an OFDMA system each user measure and feed-back the channel state information to the central BS where subcarrier and power are determined based on users’ CQI. Once the subcarrier determination is complete, each user is informed by the BS about the subcarriers which subcarriers have been allocated to it. This subcarrier mapping must be sent to all users all the time whenever the resource allocation changes. Based on different optimization objectives and constraints, subcarrier and power allocation algorithm are divided into two different categories: (1) Margin adaptive (MA) 61 algorithms, to minimize the overall transmit power with constraints on individual and/or system data rates. (2) Rate adaptive algorithms (RA) to maximize the system throughput under a total and/or individual transmit power constraints (Gao et al. 2006). The first category/objective is best suited for fixed rate applications such as voice and the second one is more appropriate for bursty applications, for example, data and IP related applications. For our case we have only focused on the Rate Adaptive algorithms (2 nd category), as it is more relevant to the applications of WiMAX systems. 4.1. Subcarrier and Power Allocation Algorithm In this section there are three different subcarrier allocation algorithms for the downlink of an OFDMA system is proposed where each algorithm has been designed to achieve certain objectives under fixed constraints. These algorithms are further divided into two sub problems: the subcarrier assignment and power allocation. In each algorithm channel state information is used to assign subcarrier to users, and power allocation to subcarrier is done in two ways: water filling (WF) and equal power allocation (EPA). It can be proved that water filling power allocation gives the optimal performance compared to equal power allocation. The details of all the algorithm’s functional procedure and their mathematical operations are provided sequentially in the next subsection. 4.1.1. Maximum Sum Rate (MSR). As the name indicates, the objective of MSR algorithm is to maximize the sum rate of all users given a total transmit power constraint. This algorithm is optimal if the goal is to transmit as much data as possible through the system. The sum capacity is maximized if the total throughput in each subcarrier is maximized. According to Jang & Lee (2003:171-178) in a multiuser OFDM system, each of the multiple users’ signals may undergo independent fading because of the distance variation of different user. So, the probability that every users signal on a same subcarrier are in deep fading is very low. 62 Therefore, for a specific subcarrier, if a user’s signal is in deep fading, the others may not be in deep fading and the user in a good channel condition will be allowed to transmit data on that subcarrier offering multiuser diversity. For this reason if each subcarrier is assigned to the user with the largest channel gain and the power is (using water filling algorithm) distributed according to channel gain, then the sum capacity will be maximized. However this algorithm has a drawback, it is likely that users who have excellent channel conditions (users who are close to the base station) will be allocated all the system resources, and unfortunately a user may not be assigned any subcarrier if the user has no best subcarrier on it (Khedr et al. 2008) . System Model: Figure 24. Block diagram for K users in an OFDMA system where base station has allocated different set of subcarriers to each user. We consider a block diagram for the downlink of a typical OFDMA system as shown in Figure 21. Where bits (bi) for each of the different K users are allocated to the N subcarriers by the base station transmitter and each subcarrier n )1( Nn  of user k )1( Kk  is assigned a power Pk, n. It is assumed that each subcarrier is allocated to only one user at a time. If the total system bandwidth is B then each subcarrier holds a bandwidth of B/N. It is also assumed that each user experiences independent fading and the channel gain of each user k, in subcarrier n is denoted by gk,n , with additive white 63 Gaussian noise σ 2 = N0*B/N. Here N0 is represents single sided noise power spectral density. Now the corresponding subchannel signal to noise ratio denoted as 22 ,, /nknk gh  (4.1) and finally the kth users received signal-to-noise ratio on subcarrier n can be expressed as (Wong, Shen, Evans, and Andrews 2004) nknknk hP ,,, * (4.2) The channel is assumed to be slowly time varying because it is necessary that each user estimates the channel and feedback this information to the BS where the resource allocation algorithm runs, before the information considered being obsolete (Khedr et al. 2008). Now in order to meet the required BER (10 -3 ), we divide the subchannel signal-to-noise-ratio by a constant SINR gap (Γ= ln (5BER)/1.6) (Because in practice there is a gap between the achieved data rate and the maximum (Shannon rate) rate, this gap is called a SINR gap of a few dB) and we get the effective subchannel signal-to- noise ratio Hk, n = hk, n/Γ. Finally kth users received signal-to-noise-ratio on subcarrier n can be written as,  )//(g* P = H* P = 22 nk,nk,nk,nk,nk , (4.3) Now using the famous Shannon capacity formula, we get the achievable data rate for user k on subcarrier n, and it is denoted b , 2 , log (1 ) k n k n B r N   then the total data rate for user k can be expressed as, )4.4()1(logR 1 ,,2,k    N n nknknk Hpc N B After these definitions we can formulate the objective function of MSR algorithm as an 64 optimization problem and define in the following way (where MSR maximizes the sum capacity by maximizing the throughput in each subcarrier). Problem formulation: .,allfor0,0 allfor1 (4.6) kallfor )5.4()1(log)( ,, 1 , , 1 1 1 1 ,,2, nkcp nc Ppct to: Subje Hpc N B RMaximize nknk K i nk totalnk N k N n K k N n nknknk D             PC, Where C is a KN  matrix of which elements consists of channel allocation index Ck, n’s, P is also a KN  matrix of allocated power to user k on subcarrier n, Pk,n’s, and Ptotal is the total available power on the base station. Now if we look at the rate maximization problem in (4.5) we will see it is neither convex nor concave regarding to {C, P} and because of this reason it becomes more difficult to obtain a globally optimum solution (Kim, Kim and Han 2004; Wong et al. 2004; Khedr et al. 2008). However to solve this problem, in a real OFDMA system it is relaxed to be a real number in [0, 1] to make the maximization problem tractable which means that ck,n holds a value of 0 or 1, where a value of 1 indicates that subcarrier n is assigned to user k and 0 for otherwise. Moreover it can be seen from (Kim et al. 2004) that, this relaxation does not affect the optimal solution thus the computational complexity reduces, and the problem becomes easier to solve. Even though our problem has become easier to solve but we need an iterative algorithm to solve it explicitly, thus based on Jang et al. (2003:171-178) we divide the problem into two parts- Proposition 1: (Subcarrier assignment for users) to maximize the data rate of a specific subcarrier, it should be allocated to users who has the best channel gain and should not be allowed to be shared by multiple users. 65 Proposition 2: (Power allocation to subcarriers) at this stage we determine the amount of power needed for the subcarriers in order to maximize the overall data rate. When the subcarrier assignment is done by proposition 1, the multiuser OFDM system can be viewed as a single user OFDM system virtually and need to consider only the transmit power allocation for subcarriers. Now the total data rate (4.5) and power constraint (4.6) can be rewritten as *2 *, 1 * 1 * 1, 2, , log (1 ) and Where , arg max{ , ................... } for n=1, 2….N. N D k n k n n N k n total n n k n n k n B R p H N p P k H H H         (4.7) Now using the standard lagrangian multiplier technique similar procedure like in Ma (2008:3267-3274) in Equation (4.7), we can find the optimal power in each selected subcarrier as,  * * * * * * * * 2 , 1 1 * , , , , log 1 (4.8) whereλ is the lagrangian multiplier.Now we differentiate (4.8) with respect to and set the derivatives equal to 0. 0 ln 2 (1 ) ln 2 N N totalk n k n k n n n k n k n k n k n k n k B L P H P P N P HL B P N H P HB N                       * * * * * * , * , , , 1 0 (1 ) 1 1 ln 2 1 1 , , 0 ( ) ( ) . . (4.9) n k n k n k n k n k nk n k n N totalk n n H P P N H B so P p t H t s t p p                            66 Where λ (t) is the water filling threshold which makes the sum of power equal to the maximum power constraint and 0 0 0 ( ) x if x if x x           . Moreover, λ(t) is time varying which means that at each time t we have to find a water-filling threshold to solve, nk P * . After some manipulation we can get the threshold equivalent to (4.9) as )10.4( )( 1 /)( 1 *            N n nk total tH pNt Suboptimal Solutions: It is clear that the optimal solution is not fully practical since it needs to know full information about the channel as well as noise and interference. Hence, it would be better to find suboptimal solutions which may relax some of the requirements at low sacrificing in the performance. Algorithm I :( Greedy subcarrier allocation) Step 1: For each subcarrier, rank users according to their channel SNR. Step 2: For k= 1 to K (n={12,3,………….N}) (a) Find n satisfying )()( ,, tHtH mknk  for all mn and allocate subcarrier to the user who has the largest Hk, n. Step 3: Repeat step 1 and 2 until all subcarriers are allocated. Step 4: After subcarrier allocation, Power allocation is done using water filling algorithm (II.) (Ma 2008). Algorithm II :( WF Power allocation algorithm) After water filling not necessary all the subcarrier will be used because of weak SNR at some subcarriers, which can’t meet WF threshold (λ (t) ≤ Hk,n). Let the number of 67 scheduled subcarriers after WF at time t denoted by Neff (t) and holds 1 ≤ Neff(t) ≤ N. Now to provide efficient procedure to implement (4.9) and (4.10) a very low complexity iterative water filling algorithm is proposed in (Ma 2008) which will be used for the simulation. Step 1: for each (t), let Neff(t) = N. Rank  N nnk tH 1, )(*  in descending order where )(.......)( ,1, ** tHtH Nkk  holds. Let the power allocation solution for )( ,* tH Nk be denoted by nk P * (t). Step 2: Find λ (t) using (4.10), with N and )( ,* tH Nk being replaced by Neff(t) and )( ,* tH Nk . Step 3: Check if λ (t) ≤ )( )( * , tH teffNk holds. If true go to step 4. Else, remove )( )( * , tH teffNk from the set  )(.......)( )(