This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.
In a mobile wireless network, energy saving of mobile devices is one of the most important features for the extension of devices life time and the network. In mobile networks, the device is expected to have several connections, each with different QoS (Quality of service) requirements. Meeting the QoS requirements on such devices along with better power saving is a challenging task. Moreover, in a real-time scenarios, connections are expected to join and leave the network randomly. Before admitting a connection to the network, its QoS requirement must be checked to make sure that the network has adequate resources to accommodate it. Without a proper admission control mechanism, the system cannot provide the promised QoS to the real-time applications.
In this thesis, we propose a scheduling algorithm and admission control policy for IEEE 802.16e broadband wireless access standard. The proposed scheduling algorithm is designed in a way that guarantees less power consumption for mobile stations, and at the same time it maintains the different QoS requirements for real-time traffic. The proposed algorithm considers the dynamic nature of connection joining and termination. Connections will be allowed to join the network only if their QoS parameters can be met without violating those of existing connections.
The simulation studies collected in this thesis show that our proposed solution is able to support QoS requirement for all connections in the network. It also shows that the mobile station theoretically achieves good sleeping ratio and bandwidth utilization.
Chapter 1: Background
This chapter will give a brief introduction about WiMAX technology. It starts by providing a general overview of WiMAX networks. Then, it defines the QoS service classes supported by the standard, followed by the three power saving classes defined by the WiMAX standard. Finally, the problem statement of this thesis is presented.
Overview of WiMAX Technology
WiMAX is a new standard being developed by the IEEE 802.16 group based on wireless metropolitan area networking (WMAN) standards. WiMAX stands for Worldwide Interoperability for Microwave Access, and it is also called WirelessMAN. It has been defined as a "last mile" technology by the WiMAX Forum . WiMAX is capable of providing services for fixed, nomadic, portable or mobile wireless connectivity. WiMAX does not require a direct line of sight (LOS) with a base station.
The original 802.16 standard was based on a single carrier physical layer with a burst time division multiplexing (TDM) MAC layer. To include non-line of sight (NLOS) applications, the IEEE 802.16 group produced 802.16a (or the fixed WiMAX) that supports fixed applications and uses orthogonal frequency division multiplexing (OFDM). OFDM is a multi-carrier modulation technique in which a large number of subcarriers are used to transmit data. The data is split into several parallel data streams or channels, one for each sub-carrier. OFDM allows only one user on the channel at any given time, as illustrated in Figure 1.1 (a). Each color in the figure represents a different user. WiMAX group then developed IEEE 802.16e that supports mobility using orthogonal frequency division multiple access (OFDMA)-based physical layer. OFDMA is a multi-user OFDM that allows multiple users to transmit using different subcarriers in the same channel, as illustrated in figure 1 (b) , , [7-10].
WiMAX is expected to provide broadband wireless access in a range up to 50kms for fixed stations, and a range of 5 to 15kms for mobile stations. It also provides a maximum data rate of up to 74Mbps .
Figure1.1. IEEE 802.16 physical: (a) OFDM and (b) OFDMA .
Some of the features of WiMAX network that differentiate it from other wireless broadband technology are briefly described below , :
WiMAX uses OFDMA-based physical layer that allows operations in NLOS conditions.
WiMAX is capable of providing very high peak data rates up to 74 Mbps. Furthermore, WiMAX allows a scalable use of data rate according to the channel bandwidth.
WiMAX supports adaptive modulation and coding per subscriber based on the channel conditions.
WiMAX supports Time Division Duplexing (TDD) and Frequency Division Duplexing (FDD) that allows for low-cost implementations.
WiMAX connection-oriented MAC layer provides QoS for different traffic types, such as best-effort (BE), real-time, non-real time, constant bit rate (CBR), and variable bit rate (VBR) traffic.
WiMAX supports security and automatic retransmission response (ARQ).
One important feature of the WiMAX is the power saving feature, in which mobile subscriber stations can operate for longer time without needing to re-charge their batteries.
In power saving mode, the mobile station (MS) will power down one or more of its hardware components to conserve energy when there are no packets to send or receive. By doing so, the MS enters into the sleep state or the sleep window. Sleep window is followed by a listen window, in which the MS wakes up to listen for the incoming data traffic from the base station (BS) .
WiMAX Frame Structure
The WiMAX PHY layer is responsible for slot allocation over the air. The minimum time-frequency resource that can be allocated by a WiMAX system to any user is called a slot. The slot consists of one subchannel over one, two, or three OFDM symbols, depending on the subchannelization scheme applied. WiMAX is flexible in terms of how multiple users and packets are multiplexed on a single frame. The scheduling algorithm could assign data slots to different users based on other QoS requirements, and channel conditions ,.
Figure (1.2) shows an OFDM frame structure when operating in TDD mode. The frame is divided into two sub-frames: downlink (DL) and uplink (UL) sub-frame separated by a small guard interval. The downlink-to-uplink-subframe ratio is varied from 3:1 to 1:1 depending on the traffic profile. The OFDMA structure is the same as shown in Figure 1.2 except that both downlink and uplink will be transmitting simultaneously over different carriers ,.
Figure1.2. A sample TDD frame structure for mobile WiMAX.
A preamble in the frame is used for time synchronization and initial channel estimation. The downlink preamble is followed by a Forward Error Control (FEC), which carries system control information such as modulation type, coding scheme and the length of the DL-MAP message. The downlink and uplink MAP messages (DL-MAP and UL-MAP) define the burst profile for each user (slot allocation), the DL , .
Each burst contains MAC protocol data units (MPDUs), and each MPDU consists of a header followed by a payload and a cyclic redundancy check (CRC).The MAC header is used to carry data and MAC-layer signaling messages. The MAC header contains connection identifier (CID) in addition to other information elements as shown in Table 1.1, .
Table1.1. Generic MAC header fields .
WiMAX QoS Service Classes
WiMAX provides QoS requirements by using a connection-oriented MAC layer. In order to support a wide variety of applications, IEEE 802.16 has defined five different service classes. Each of these classes has certain QoS parameters. Table 1.2  presents QoS parameters for the five service flow classes. Table 1.3  further presents some of the WiMAX applications for different QoS classes, and their related guidelines.
Unsolicited grant service (UGS) class is designed for traffics with a fixed-size packet such as constant bit rate traffic , . Voice over IP (VoIP) without silence suppression is a good example of UFS class.
Real-time Polling Service (rtPS) class is designed for real time traffic. It is designed to support applications with variable-packet size, such as MPEG compressed video , .
Non-real-time Polling Service (nrtPS) class is designed for non-real-time variable bit rate traffic that requires no delay guarantees, such as File Transport Protocol (FTP) traffic. In this class, only minimum data rate is guaranteed , .
Best-effort (BE) service class is designed for data streams. In this class, delay and throughput are not guaranteed. Web browsing traffic is an example of applications using this service class , .
Extended real-time variable rate (Ert-VR) service class is designed for real time applications that have variable data rates such as VoIP with silence suppression. Applications using this class require guaranteed delay , data rate and jitter , .
Service Flow Designation
Defining QoS Parameters
Unsolicited grant services (UGS)
Maximum sustained rate,
Maximum latency tolerance,
Voice over IP (VoIP) without
Real-time Polling service (rtPS)
Minimum reserved rate,
Maximum sustained rate,
Maximum latency tolerance,
Streaming audio and video,
MPEG (Motion Picture Experts
Non-real-time Polling service
Minimum reserved rate,
Maximum sustained rate,
Streaming audio and video,
MPEG (Motion Picture Experts
Best-effort service (BE)
Maximum sustained rate,
Extended real-time Polling service
Minimum reserved rate,
Maximum sustained rate,
Maximum latency tolerance,
VoIP with silence suppression
Table 1.2. Services classes supported in WiMAX .
< 25 ms
VoIP and Video Conferenc
< 160 ms
< 50 ms
Low to high
5 kbps to 2
< 100 ms
Web Browsing and Instant Messaging
10 kbps to 2
Media Content Downloads
> 2 Mbps
Table1.3. WiMAX application classes .
WiMAX Power Saving Classes
The energy dissipation in a mobile station can be reduced through the "sleep mode" operation which extends the life time of the mobile station. IEEE 802.16e has defined three power saving classes. Each connection in a mobile station can select a certain power saving class (PSC).PSC can be defined for a group of connections with common properties. Each power saving class can be activated or deactivated. When the PSC is activated, MS can start alternate sleeping/listening windows of the class to save power. When the PSC is deactivated, MSS will go back to normal operation of the corresponding connection.
Mobile station negotiates the parameters of a power saving class with the base station to decide the power saving parameters, such as the time to sleep and the time to listen, the length of the sleep and the listen intervals .
There are three types of power saving classes with different parameters and different activation/deactivation procedures as illustrated in Figure 1.3.
Power saving class of type I:
In this PSC, MS will first sleep for a period of time then wake up to listen if BS has any downlink data for the MS. If there are no packets buffered in the BS for the MS, then the MS will double the length of the previous sleep window, and the process of doubling the sleep interval continues until the final-sleep window size is reached [1-6], , , , .
Doubling exponentially the sleep interval achieves efficient power saving; however, this will increase the delay. Therefore, type I power saving class is recommended for Best Effort (BE) and non-real time variable rate (NRT-VR) traffic type. PSC of type I is suitable for web browsing and data access services , .
Power saving class of type II:
In this class, the sleep and listen period are fixed; all of the sleep and listen windows are of the same size as the initial-sleep window. In this class, MS repeats the sleep and listen period on a round-robin fashion , .
Unlike PSC of type I, type II PSC avoids increasing the delay by keeping the sleep interval lengh fixed. Therefore, type II PSC is recommended for Unsolicited Grant Service (UGS), real-time variable rate (rt-VR), and extended real-time variable rate (Ert-VR) traffic. This class works well for real-time connections such as voice over IP (VoIP) and video streaming services since such applications have to send or receive packets on a periodic basis , , .
Power saving class of type III:
This power saving class involves only one sleep window and no listening window. This sleep window is specified by final-sleep window parameters. Mobile station will sleep for the predefined sleep period. When the sleep period is expired, the PSC is deactivated and the MS returns to normal operation [1-6], , , , .
Type III power saving class is suitable for management connection as well as multicast connection , .
Figure1.3. Power saving classes defined in IEEE 802.16e .
Power saving for mobile devices is a critical design aspect in wireless networks, such as WiMAX. In WiMAX systems, although three power saving classes have been defined in the standard, these classes are per-connection basis. Therefore, when a MS has multiple connections, power saving efficiency can degrade drastically. MS with multiple connections should determine its actual sleep and listen intervals, by finding a common sleep interval among all connections. Managing multiple connections on a MS without violating QoS of any connection along with power saving is very challenging, and allows MS to operate for longer duration without having to re-charge their batteries.
Another important factor to consider is that in real-time sessions, connections are expected to join and leave the network randomly. Admission control mechanism that can be used to ensure that the incoming connection'QoS parameters will not degrade the QoS of existing connections is not defined by the WiMAX standard.
In this research, we will consider a WiMAX environment with single MS connected to single base station BS and each MS has multiple connections .The first objective of this research is to propose and evaluate a new energy-aware uplink packet scheduling approach at MAC level of WiMAX. This research proposes a new scheduling scheme to handle different connections of UGS traffic classes at a mobile station without violating their QoS parameters (delay, bandwidth requirement.). The proposed schedule guarantees minimum power consumption for a mobile station. The second objective of this research is to propose an efficient Call Admission Control to ensure QoS guarantees for all existing connections.
In this work, the proposed Uplink Packet Scheduling (UPS) and Call Admission Control (CAC) are designed in such a way to support multiple UGS connections on a single mobile station (MS). A matlab simulation model is used to evaluate the proposed scheduling strategies.
Thesis Contribution and Outline
The contributions of this research can be summarized in the following points:
An Uplink Packet Scheduling residing at the BS is proposed to provide QoS guarantee in terms of delay and bandwidth for multiple UGS connection at one MS.
Two-steps efficient Call Admission Control residing at the BS is proposed to decide on accepting or rejecting the new calls requests based on the QoS constraints of the existing calls and the new calls.
The proposed model is simulated and it was found to achieve good sleeping periods and bandwidth utilization of a single MS by utilizing the type-three power saving class defined in the IEEE 802.16e.
The chapters to follow are outlined as shown:
Chapter 2: The second chapter includes the summery of the literature review. It reviews similar work done in the research area.
Chapter 3: This chapter discusses in details the proposed QoS architecture at the base station and its modules (Uplink Packet Scheduling and Call Admission Control ). It also provides pseudo codes algorithms for each of the proposed modules in the QoS architecture.
Chapter 4: It includes the simulation results for two different traffic types scenario. It provides a detailed analysis and discussion for each result. It finds results for two scenarios.
Chapter 5: chapter five is the final chapter which summarizes the findings of this thesis and presents recommendations for future work.
The topic of QoS scheduling in WiMAX has been extensively studied in the recent past. However, QoS scheduling with consideration of power saving at mobile station along with efficient admission control has received little attention from researchers.
This chapter is divided into three sections:
Sections 2.1 reviews some of the QoS architectures that have been proposed to support QoS requirements for all traffic types, and control the acceptance of the incoming flows. However the proposed QoS architectures in section 2.1 do not consider the topic of power efficiency.
Section 2.2 reviews some of the many algorithms that are proposed to reduce the power consumption of a mobile station. Unfortunately, some algorithms are not concerned in maintaining the QoS parameters. Furthermore, no call admission control algorithm was used to decide on the incoming traffic.
Section 2.3 reviews the algorithms that combine between scheduling the packets while maintaining their QoS parameters, and minimizing the sleeping period intervals to save more power at the mobile station. However, very few researches have addressed this issue.
Ayman and Adlen  have classified the scheduling architecture into two main categories; traditional methods and new methods. The traditional methods are based on classical scheduling algorithm such as FIFO, Round Robin, etc. The traditional methods are further divided into simple and hierarchal methods. Hierarchal schemes try to maintain fairness among different classes by preventing high priority connections (UGS,rtPS) from starving the bandwidth of lower priority connections (nrtPS,BE). However the main problem in the hierarchal algorithms is their complexity in the implementation. New scheduling techniques can be either designed to treat all classes together in one scheme or to treat only one class.
Admission control schemes and packet scheduling algorithm are designed to offer QoS services in WiMAX network. A number of studies have investigated these subjects in IEEE 802.16.Unfortunately, these scheduling algorithms do not consider the power consumption of a mobile station. For example, Wongthavarawat and Ganz  proposed the architecture of the uplink scheduler. Their proposed architecture completes the parts undefined by the standard to support all types of service flows. In their proposed architecture as shown in figure 2.1, they have added a detailed Uplink Packet Scheduling (UPS) module and admission control module (at the base station). They have also added Traffic Policing module (at the subscriber station).
The proposed UPS in  consists of three main modules: information module, scheduling database module and service assignment module. The information module processes traffics that issue BW-Request (rtPS, nrtPs, BE) and provides the Scheduling Database with the queue length as obtained from BW-Request. The Scheduling database module creates tables to save data for all type of flows. The Service assignment module uses the database tables created in the scheduling database module to generate the UL-MAP. To support all types of traffic flows, their proposed (UPS) schedules each of the four traffic classes using strict priority bandwidth allocation discipline. Bandwidth allocation per traffic flow follows strict priority, from highest to lowest: UGS, rtPS, nrtPS and BE. They have proposed set of admission control schemes for all traffic types. Admission control module accepts connections only if its QoS requirement in terms of delay and bandwidth can be met, and if the new connection's requirement will not degrade the QoS of existing connections.
In their simulation, they assumed only two types of traffic (rtPS and BE), and that all the traffic is already admitted. The results reveal that their proposed UPS can provide QoS support for rtPS in terms of bandwidth and delay. Unfortunately, the proposed packet scheduling does not arrange the packets in fewer frames, therefore it results in poor power efficiency at the subscriber station.
Figure2.1. Proposed QoS architecture 
Sarat and Anirudha  proposed a QoS architecture at the BS and the SS. They have also proposed an efficient QoS Call Admission Control (CAC) that provides QoS guarantee in terms of bandwidth and delay to all registered connections as per service types. The traffic scheduler, which resides at the BS, decides on the allocation of connections' slots in each frame by considering the connection service type (UGS, rtPS,ntrPS or BE), the QoS parameter values of the connections, the availability of data for transmission and the capacity of the available bandwidth. Their proposed BS architecture is shown in figure 2.2 .When a new connection request is sent to the BS, the request will be classified depending on the type of service into one of the Priority Queues (Priority Order: UGS Queue>RTPS Queue >NRTPS Queue). At the end of each scheduling interval, BE connections will be allocated within the remaining bandwidth (if any). The proposed CAC module in  accesses UGS, rtPS, and nrtPS queues to check if their requested QoS constraints can be met. When a connection is accepted, then the CAC will inform the scheduler at the MS to allocate bandwidth request slots in the next scheduling interval to that connection.  Have outlined the details of their QoS-CAC algorithm for all traffic types; moreover they have proposed pseudo-code of the call admission control algorithm for UGS and rtPS connection only. For variable bit rate flows (rtPS and nrtPS), they have proposed a simple method of estimating the bandwidth which improves the performance of the system in terms of flow acceptance ratio. Simulation result reveals that their QoS-CAC achieves better performance than the conventional BW-CAC in terms of flow acceptance ratio. However, although QoS-CAC ensures QoS guarantee for all registered connections, but optimizing the power consumption when scheduling them connections is not explored.
Figure 2.2. (a) BS proposed architecture (b) SS proposed architecture .
Chakchai,etal, presented an extensive survey of recent packet scheduling research for WiMAX networks. They have discussed the main design factors and key issues that should be considered when designing a scheduler. Many delay-based algorithms that are designed for real-time traffic have been surveyed in the . For example, Largest Weighted Delay First (LWDF) algorithm which chooses packets with largest delay to be scheduled first to avoid missing its deadline is proposed in . Another example is found in , in which Delay Threshold Priority Queuing (DTPQ) algorithm is proposed to schedule packets from real-time and non real-time traffic. Other scheduling approaches for real time connections such as Priority-based algorithms have been also surveyed in . Packet-based algorithms guarantee the QoS to different classes. For example, packets can be prioritized based on their delay value . On the other hand connections from the longest queue will be assigned the highest bandwidth as in . However, none of the surveyed algorithms in  follow a certain power saving scheme to reduce the number of used OFDM frames when scheduling.
The power consumption issue in WiMAX has been widely investigated in several studies, and many algorithms have been suggested to determine the sleeping periods of a mobile station, thus improving its energy efficiency.
In , Min-Gon, etal., have proposed a new Scheduled Power-Saving Mechanism (SPSM). The mechanism synchronizes the starting time of the sleep-mode operation of a new connection with the connections that are already in the sleep-mode. This can be realized through controlling the operating parameters; the minimum and the maximum sleep intervals. This algorithm can be applied on two or more connections in an MS. Unfortunately, their proposed scheme can only be applied when the QoS type of the newly initiated connection is non-real-time connection (low QoS). Simulation results reveal that their scheme achieves better power preservation of the MS than the traditional approach.
Tuan-Che and Jyh-Cheng in  have proposed maximizing unavailability interval (eMUI) for the mixture of type I and type II power saving classes. Unavailability interval can be defined as the time intersection of all activated power saving classes when they are all in their sleep window. During the unavailability interval, there is no communication between the MS and the BS in the downlink direction DL (from BS-to-MS) or in the uplink direction UP (from MS-to.BS) [4,10,11]. Their proposed eMUI does not consider the variable traffic rate; which means that unavailability interval remains unchanged once it is defined. Simulation results (using NS-2) demonstrate that their proposed algorithm reduces power consumption and average packet response time. Furthermore, because power efficiency in sleep mode is improved, the average waiting time at the mobile subscriber station decreases.
In  , Omanande, etal., have proposed an adaptive power saving algorithm which addresses the variable traffic rate problem, and decreases the average delay for packet reception with respect to 802.16e. Their architecture considers only power saving class I, by adapting the minimum time required to sleep (Tmin) according to the downlink traffic pattern. Unfortunately, power saving class II and III are not considered. Analytical model and simulation result are used to evaluate the proposed algorithm.
In , Jaehyuk, etal., have introduced new parameters of the sleep mode operation which are the initial-sleep window size, the final sleep window size and power saving threshold. These parameters were adapted according to different traffic types (CBR and FTP) to achieve efficient power saving. They applied the power saving strategies to different traffic types in order to obtain optimal operational parameters that satisfy different QoS requirements. Unfortunately, in their proposed adaptive power saving strategies they have considered only Power saving Class of type I.
However, none of the above power saving-based approaches propose a module to control the admissibility of the incoming flow that aims to maintain the QoS parameters of the new and existing connections.
2.3 Power Saving With QoS Guarantee
Very few QoS architectures have proposed a complete solution for real-time traffic in terms of reducing the number of awakened OFDM frames, scheduling packets while ensuring their stringent QoS parameters, and performing call admission control to decide on the requested connections at the same time.
Shih-chang, etal., in  proposed three energy efficient scheduling approaches for 802.16e. In their research, they considered multiple MSS with constant bit rate traffic while considering QoS delay constraint. In the three proposed approaches, a minimum length of the sleeping cycle for all MSSs is found for each MS and the number of OFDM frames required for each MS. Moreover, they introduced a QoS scheduling mechanism that finds the theoretical maximum sleeping time for single MS, which can be used as an upper bound for the energy-saving mechanisms in IEEE 802.16e. This theoretical maximum sleeping time is called the Minimum Wakeup Time scheduler. Even though they have considered multiple MS in their proposed approach, each MS has the same fixed number of connections, and all connections are of the same requirements. All established connections are assumed to last the whole time. Unfortunately, admission control unit that monitors the incoming traffic is not discussed. In their work, simulation results are presented to evaluate their scheduling approaches. Simulation results support the advantages of the three proposed approaches in terms of sleeping ratio (Number of frames in sleep mode/total number of frames) and bandwidth utilization. Comparing to the upper bound of sleeping ratio, their approaches suffer only 1.5% performance degradation.
In , Shiao-li and You-lin have proposed two energy-efficient packet scheduling algorithms for real-time connections in a Mobile WiMAX system. The proposed algorithms consider the QoS requirements and guarantee minimum power consumption for multiple mobile stations connections. The first scheme (periodic on-off scheme PS) addresses power-saving class of type II by maximizing the length of a sleep period. They have proposed an algorithm to calculate the length of sleep and listen period according to the radio resources and the QoS constraints. The second scheme (aperiodic on-off scheme AS) utilizes power-saving class of type III to support real-time connections. In this approach, they first determine dynamically when the MS should go to sleep (on a frame basis) that will maximize the length of the sleep period. Admission control is performed by the base station when a new connection is requested or a current connection is released. In these two cases, the base station will re-schedule the sleep mode operation based on the available resources. But if no connection is released or established by the mobile station, the base station will not re-schedule the resources, even if there are recourses released by other mobile stations. Yet, no details of how to achieve this are discussed. Moreover, all MSs are assumed to have a predetermined set of connections. Simulation using C++ is used to evaluate the performance improvement achieved by the two proposed schemes over the traditional approach. The PS approach increases 80-120% more sleep periods than the traditional approach, while the AS approach gains about 15-120% more sleep periods over the traditional approach.
No explicit full solution that was designed to schedule UGS traffic in the minimum number of OFDM frames while meeting their QoS requirement, and at the same time deals with the fact that real-time connections could randomly join or leave the network has been proposed. This research addresses the above issues and provides a full solution that considers the UGS traffic requirement in addition their joining and releasing events and schedule them in a way that improves the energy efficiency of the MS.