Keywords
|
| Bandwidth allocation, Bandwidth request, CAC, Wimax |
INTRODUCTION
|
| IEEE 802.16 is designed to support high bandwidth for wide area networks. WiMAX will provide fixed and mobile wireless broadband connectivity without the need for direct Line of Sight (LoS) to BS. In a typical cell radius deployment of 3 to 10Km, WiMAX forum certified systems can be expected to deliver capacity of up to 40 Mbps per channel for fixed and portable access applications. WiMAX coverage is approximately 40Mbps and is going to touch 1Gbps for fixed users which can access the range of 50Km (30miles) and for mobile users the WiMAX coverage is from 5 to 15Km (3 to 10miles). |
| In 802.16, two modes are present. They are Point-to-Multipoint (PMP) and Mesh mode. A cellular structure is formed in the PMP mode. Within the one sector, the base station (BS) supports a set of subscriber stations (SSs) in a broadcast mode. In mesh mode, scheduling is distributed in the nodes which are organized ad hoc. The uplink (from SS to BS) and downlink (from BS to SS) data transmissions in IEEE 802.16 are frame based method for the transmission of variable size data packets such as video and voice. |
WIMAX ARCHITECTURE
|
| WiMAX defines signalling mechanisms between Base Station (BS) and Subscriber Station (SS) considering both fixed and mobile wireless broadband. The main issues are 1) Grant per SS (GPSS) to adhere to each SS rather than each connection. SS can flexibly respond to different Quality of Service (QoS) requirements of the connections. 2) Grand per Connection scheme (GPC) not feasible for SS and to be adaptive to connections of real time applications which are supported by bandwidth allocation algorithm. There are five service flow types. They are Unsolicited Grant Services (UGS), real time Polling Service (rtPS), extended real time Polling Service (ertPS), non real time Polling Service (nrtPS) and Best Effort (BE) service. |
| The 802.16 standard essentially standardizes 2 aspects of the air interface - the physical layer (PHY) and the Media Access Control layer (MAC). IEEE 802.16d provides air Interface for fixed broadband wireless access system. IEEE 802.16e uses Scalable OFDMA to support the bandwidth in between 1.25 MHz and 20 MHz having 2048 sub-carriers. It can able to support adaptive modulation and coding. In the good channel conditions, highly efficient 64 QAM coding scheme is used. In the bad channel conditions, BPSK coding mechanism is used. |
| The dynamic assignments of uplink and downlink burst profiles are performed in MAC layer according to link conditions. WiMAX MAC is a demand assignment protocol. In the Convergence Sub layer (CS), the classifications are made according to QoS parameters of the incoming packets and the specific service flow is assigned with service flow identifier number [10]. The variable length packets are framed as Protocol Data Unit (PDU) and the multiple PDU are concatenated into single burst. In MAC layer, Service Data Unit (SDU) is concatenated into single payload which save MAC header overhead. In the MAC frame structure, one frame is considered with downlink sub frame and uplink sub frame. |
| In uplink sub frame, the initial ranging contention, Bandwidth request contention and payload are considered. In downlink subframe, burst preamble, DL-MAP or UL-MAP and downlink payload are considered. Adaptive Modelling and Coding (AMC) is deployed in the physical layer and number of bytes in each time slot can carry depends on coding and modulation scheme. The modulation and coding scheme is chosen based on the uncertainty of channel conditions. |
| QoS is a fundamental part of 802.16 Medium Access Control (MAC) layer design. QoS is provided by the bandwidth allocation and Call Admission Control (CAC) in the networks. Because 802.16 MAC is connection-oriented this gives a greater control over the network resources sharing amongst individual connections and making it possible to provide better QoS. In WiMAX, there are five types of service flow with distinct QoS requirements. The service flow details are tabulated in the table I. The cons and QoS parameters for different service flow are given in table II. |
| This paper is organized as the bandwidth request made to have the connection between SS and BS is discussed in chapter III. In chapter IV, the Call Admission Control scheme is briefly discussed. In chapter V, the various bandwidth allocation mechanisms are discussed and its comparative are tabulated. Finally we concluded in chapter VI. |
BANDWIDTH REQUEST MECHANISMS
|
| A request/grant bandwidth allocation is employed in WiMAX systems for transferring data, videos and voice. Before the data transmission, SS should get grant from BS with sufficient bandwidths which are essential to transmit data to BS. The amount of bandwidth can be reserved or adjusted by the SS via sending bandwidth requests (BR). BRs are unicast polling and contention resolution mechanisms [1]. |
Unicast Polling
|
| The BS allocate small amount of bandwidth to the target SS. The allocated bandwidth can be considered as unicast polling Transmission Opportunities (TxOPs). Utilizing this TxOPs, SS can request a needed bandwidth for transmission. Based on the availability of bandwidth at BS, SS request is granted. Otherwise it is rejected [1]. |
Contention Resolution
|
| During contention period, SS may have no opportunities to transmit Bandwidth Request (BR). BS scheduled a few contention TxOPs for a group of SSs. If the SS failed to get the opportunities in the contention period, it would enter into the back off procedure for preparing its next attempt. |
| The contention resolution in MAC is analysed by using a two dimensional Markov Chain (MC) model [1]. W is the current Back off window size. The operation procedure is explained in figure 2. When the back off counter reaches zero, SS send BR. It is possible to have more than one SS whose back off counter reaches zero at the same time. In the same time, several SS send BR utilizing the same TxOPs. In that time, collisions occur. |
| SS cannot have the ability to detect the collision in the UL (UpLink) connections. It waits for fixed number of subsequent UL map messages. If SS failed to get UL map, then it double the back off window size and repeat the same procedure until it get the grant from BS. |
| The distinct service flows use any one of the bandwidth request method to attain QoS. The bandwidth request methods for distinct flows are indicated in table III. Each type of BR mechanism has its own advantages and disadvantages. They are tabulated in table IV. |
| The contention resolution outperforms unicast polling when the probability of making bandwidth requests is low. The connection in each scheduling class has its own QoS requirements. The priorities are not employed in the contention resolution since the BS fixes the initial and maximum back off windows and each SS in the system uses the same value for all connections [1]. |
CALL ADMISSION CONTROL MECHANISMS
|
| The main objective of a CAC mechanism is to limit the number of active connections/flows so that the QoS performances can be guaranteed for all the active connections. Then, the call admission decision is made to accept or reject an incoming connection. Call Admission control is used at each subscriber station to limit the number of ongoing connections through that subscriber station. At each subscriber station, traffic from all uplink connections is aggregated into a single queue [3]. The size of this queue is finite in which some packets will be dropped if the queue is full upon their arrivals. For Point to Multipoint Mode (PMP), Threshold based CAC and Queue aware CAC algorithms are followed [3]. The connection and packet-level performances of both CAC schemes have been studied based on the queuing theory. Poisson process is considered for the connection arrival and the packet arrival for a connection by Markov Model of Poisson Process (MMPP) process. For Mesh mode there is no distributed CAC algorithms available. The conventional method is used to accept or reject the call. This introduces an unbounded delay during connection initiation [2]. |
Threshold Based CAC algorithm
|
| In this algorithm, threshold C is set to limit the number of ongoing connections. When a new call wanted to connect, the admission module check whether the total number of connections should be less than or equal to the threshold C. If it is true, then the new connection is accepted, otherwise it is rejected. It is analytically analysed. As the length of a frame T is very small compared with connection arrival and departure rates, the maximum number of arriving and departing connections in a frame is one. Otherwise it is increased or decreased depending on the state [3]. In [3], the performance is evaluated and it shows that when the connection arrival rate increases, the number of ongoing connections and connection blocking probability increase. |
Queue aware CAC algorithm
|
| This algorithm works based on connection acceptance probability which is determined based on the queue status. The packet arrival for a connection follows MMPP which is identical for all connections in the same queue. The connection inter-arrival time and the duration of a connection are assumed to be exponentially distributed. An MMPP is a stochastic process in which the intensity of a Poisson process is defined by the states of a Markov chain [3]. While the threshold-based CAC scheme simply fixes the number of active connections, the queue-aware CAC scheme considers the number of packets in the queue for the admission control decision to make a new connection. The performances such as connection blocking probability, the average number of active connections are evaluated analytically. The same parameters are also evaluated numerically. The average length of queue, the average delay and the average queue throughput are evaluated. The performance measurement not depend the queue size and the number of active connection. The bandwidth allocation is made for the call connected user. The user demand must satisfy with the allotment of bandwidth. If the number of user is increased then the call admission is made based on available bandwidth. |
| The call admission control is given in figure 3 [3]. Numerical results show that, the performance parameters of connection-level and packet-level are significantly impacted by the connection-level rate. Threshold level CAC and queue aware CAC schemes result the better packet-level performances compared with those without CAC scheme. When channel quality is better, then the performances based on the packet transmission become better. The performance based on the connection-level for the threshold-based CAC scheme and those without CAC scheme are not impacted by the channel quality when this later becomes better. The admission control decision for the queue-aware CAC based on the queue status which is desirable for a system with high traffic fluctuations. |
BANDWIDTH ALLOCATION ALGORITHM
|
| The ability of a network is to provide improved service of selected network traffic. The scheduling algorithm is carried out at BS as well at SS. Up Link Scheduling is performed at BS for uplink traffic in WiMAX (Traffic from SS to BS) and Down Link Scheduling is performed at SS to distribute the Bandwidth allocation from BS among its connection. Band width request is crediting with the data packet. For bandwidth grant, there are two mechanisms 1) Grant per Connection (GPC) 2) Grant per Subscriber station (GPSS). |
| The data transmissions require bandwidth request/allocation procedure. Acknowledgement packets have a separate uplink connection. This causes increase in RTT of downlink TCP flow and in turn decreases its throughput. The uplink traffic does not have all the information about SSs such as queue size [11]. Two scheduling algorithms are followed. |
| 1) Frame based scheduling 2) Sorted based scheduling. In frame based scheduling Weighted Round Robin (WRR) and Deficit Round Robin (DRR) are shown their major involvement. In sorted based scheduling, Weighted Fair Queue Scheduling (WFQ) also known as Packet based generalized processor sharing, modification in WFQ as Worst Case Fair Queuing (WCFQ) and Self Clock Fair Queuing (SCFQ) are involved. |
Uplink Scheduling Algorithm
|
Round Robin (RR) Scheduling algorithm
|
| It distributes channel resources to all SS without any priority. It is not suitable for systems with different levels of priority and systems with strongly varying sizes of traffic [11]. |
Weighted Round Robin (WRR) algorithm
|
| It is based on static weights. To differentiate prioritization SS flows enable various service rates. It assigns a weight to each queue. The weight of the individual queue is equal to the relative share of the available system bandwidth. The number of packets de queued from a queue varies according to the weight assigned to that queue [11]. |
Earliest Dead line First (EDF) algorithm
|
| In this deadline is assigned to each packet. It allocates bandwidth to the Ss that has the packet with the earliest deadline which can be assigned to packets of SS based on the SS’s maximum delay requirement. It is suitable for UGS & rtPS [11]. |
Weighted Fair Queue (WFQ) Scheduling algorithm
|
| This algorithm is packed based approximation. It is for variable size packets and superior than WRR. Packets are taken as bits and it is scheduled separately. The virtual finishing time is calculated. It will serve packets even if they wouldn’t have started service under the generalized processor system s. It does not consider the start time of a packet [11]. |
Priority Queue (PQ) based uplink scheduler
|
| The uplink scheduler keeps the data grants in three types of queus-Type1, Type2 and Type3. The scheduler allocates the resources by following strict priority from Type1 to Type3 queue [6]. Type 1 queue stores the periodic grants and unicast requests that must be scheduled in the next frame. Type 2 queue stores the bandwidth requests of rtPS and nrtPS connections. Type 3 queue stores the bandwidth requests of BE connections. |
Reinforcement Learning algorithm
|
| The packet scheduling is based on Learning Automation [4] in BS with QoS requirements. Learning Automation is used to learn a scheduling policy in response to feedback from the network about the delay experienced by each traffic class. The traffic was modelled by discrete time arrival process where a fixed length time slot is required to transmit a packet and at most one packet can be serviced at each time slot. The role of scheduler is to decide which queue should be serviced at each time slot and it is shown in figure 4 [11]. Learning Automation is to optimize the scheduling policy of our queue management system. In this algorithm, reward function is awarded based on incoming packets with delay requirement. Positive reward was provided when packets were serviced with in delay requirement and a negative reward was provided when packets were serviced late. |
RESULTS
|
| The results for various algorithms are compared and tabulated. In table V shows that the comparison of bandwidth allocation in uplink direction. |
| It is found that mean delay is increased when the traffic is high expect UGS flow. Because the reserved bandwidth is allocated for UGS and for other flows the bandwidth is polled based on the incoming traffic. |
| The bandwidth is allocated for rtPS service at periodic polling of incoming packets. So delay is minimized. For ertPS, the delay is in accordance with rtPS and UGS flow. For BE service, the delay is might be more for all traffic conditions because it takes least priority value. In uplink traffic, the appropriate throughput is considered for various scheduling algorithm and it is tabulated in table VI and also shown in the figure 5. In uplink traffic, the appropriate average delay is considered for various scheduling algorithm and it is tabulated in table VII. |
| In table VIII shows that the comparison of bandwidth allocation in downlink direction. It is found that [5] mean delay is increased for BE and nrtPS when compared with UGS and rtPS flows when the system is overloaded. Flow priority and delay tolerant traffic are the main parameters for providing bandwidth for UGS and rtPS flows. The UGS, ertPS and rtPS traffic has the largest throughput value. Strict priority scheduler causes bandwidth starvation for low priority traffic types [3]. WRR distributes the bandwidth to all traffic types according there weights. |
CONCLUSIONS
|
| In IEEE 802.16, QoS is optimum when connection admission rate is higher with maximum bandwidth utilization. To attain QoS, Bandwidth Request mechanism, Call Admission Control and Bandwidth allocation are essential. The scheduling algorithm is to be chosen with maximum throughput and minimum delay consideration based on the service flow types. When the network is in contention state any one of the QoS parameter is satisfied with neglecting other parameters. In this work, few methods are analyzed and their performances are tabulated. |
| |
Tables at a glance
|
 |
|
|
|
| Table 1 |
Table 2 |
Table 3 |
Table 4 |
|
|
|
|
| Table 5 |
Table 6 |
Table 7 |
Table 8 |
|
Figures at a glance
|
 |
 |
 |
 |
 |
| Figure 1 |
Figure 2 |
Figure 3 |
Figure 4 |
Figure 5 |
|
| |
References
|
- David Chuck, Kuan-Yu Chen, and J.Morris Chang, “A Comprehensive Analysis of Bandwidth Request Mechanisms in IEEE 802.16Networks”, IEEE transaction on vehicular tehnology, Vol.59, No.4, May 2010.
- R.SaravanaManickam and C.Siva Ram Murthy, “An Instantaneous Call Admission Control using Information Dissemination for WiMAXMesh Networks”, International conference on Communication Systems and Networks, Bangalore, Jan. 2011, pp.1-8.
- Abdelali El Bouchti, Said El Kafhali and AbdelkrimHaqiq, “Performance Modelling and Analysis of Connection Admission Control inOFDMA based WiMAX System with MMPP Queuing”, World of Computer Science and Information Technology Journal (WCSIT), Vol. 1,No. 4, 148 – 156, 2011.
- SaeidM.Jafari and M.R.Meybodi, “Bandwidth Allocation in WiMAX Networks Using Reinforcement Learning”, World Applied SciencesJournal 13(3): 487-492, 2011.
- R.Mahmood, M.I.Tariq and M.S.H.Khiyal, “A Novel Parameterized QoS based Uplink and Downlink Scheduler for Bandwidth/DataManagement over IEEE 802.16d Network”, ACEEE International Journal on Network Security, Vol 1, No.2, July 2010.
- Gurpreet Singh and Akashdeep, “Priority Based Uplink Scheduler for IEEE 802.16 Networks”, International Journal on Computer Science andEngineering, Vol.3 No.6, June 2011.
- K.A.Noordin and G.Markarian, “Providing QoS support through scheduling in WiMAX systems”, International Journal of the PhysicalSciences Vol. 6(16), pp. 4070-4081, 18 August, 2011.
- R Murali Prasad and P.Satish Kumar, “A Joint Routing and Bandwidth Allocation Protocol for IEEE 802.16 WiMAX Mesh Networks”,IACSIT International Journal of Engineering and Technology, Vol.2, No.5, October 2010.
- Chiapin Wang, Wan-Jhen Yan and Hao-Kai Lo, “Dynamic admission control and bandwidth reservation for IEEE 802.16e mobile WiMAXnetworks”, EURASIP Journal on Wireless Communications and Networking, 2012.
- P.Saravanaselvi, Dr.P.Latha, “Design and analysis of WiMAX physical layer”, International journal of electronics and communicationengineering and technology, Volume 3, pp.280-286, December 2012.
- MajidTaghipoor, SaeidMJafari and VahidHosseini (2012), “Scheduling Algorithm and Bandwidth Allocation in WiMAX”, “Quality ofService and Resource Allocation in WiMAX”, Dr. Roberto Hincapie (Ed.), ISBN:978-953-307-956-1,InTech, Available from: http:// www.intechopen.com/books/quality-of-service-and-resource-allocation-inwimax.
|
Menu