Link aware earliest deadline scheduling algorithm for WiMAX.
WiMAX is one of the heterogeneous wireless communication technologies, which supports five different scheduling services. It has a large coverage area per base station which can be up to 30 miles in radius . To increase the coverage and throughput, relay stations were introduced by IEEE (WiMAX FORUM) . This eventually increases the chance of more traffic to compete for the limited bandwidth. To handle for all these traffics, WiMAX supports adaptive modulation and coding, such that the distance between the subscriber station (SS) and the base station (BS) determines the type of modulation to be used 2]. The BS communicates with all the subscriber stations in the downlink zone; and the reverse process is through the uplink zone. The downlink and the uplink are multiplexed by either frequency division duplex (FDD) or time division duplex (TDD) , . In frequency division duplex, simultaneous communication is achieved using different subchannels. In time division duplex, the communication is achieved using the same subchannels in different time slot . In the TDD mode, the downlink and uplink are separated by transmitreceive transition gap (TTG) and between the uplink and subsequent downlink are separated by receive-transmit transition gap (RTG) .
In WiMAX, the minimum resource that can be allocated to SS is a slot. The definition of a slot depends on the type of permutation used. Four types of permutations are used in WiMAX; partial usage sub channelization (PUSC), full usage sub channelization FUSC, Adaptive modulation and coding (AMC) and tile usage sub channelization (TUSC) . Bandwidth request by SS is either by unicast polling, multicast group polling piggyback or the request through ranging channel . When the BS responded, the bandwidth can be granted by grant per subscriber station (GPSS) or by grant per connection (GPC). In GPSS, the BS grants a bandwidth on per subscriber basis such that, all its connection is treated as a block. Hence, there is need for a local scheduler at SS to control the service order and maintain its QoS. In GPC mode, the bandwidth is granted per every connection packet. The request of this kind is by piggyback.
The five scheduling services supported in WiMAX are namely; Unsolicited Grant Service (UGS), real time polling service (rtPs), extended real time polling service (ertPs), nonreal time polling service (nrtPs) and best effort (BE) . The UGS is a real time application service with CBR; each packet has a fixed size and transmitted at equal interval of time. The rtPs is another real time application service with VBR; each packet may have different sizes transmitted at unequal interval of time. The ertPs is like UGS except that there is silence suppress associated with it. The nrtPs is an application which does not required real time transmission; the application has VBR with packets having different size transmitted at unequal interval of time. The last is the BE which is also non-real time but requires the minimum bit error rate in transmission. Each of this type has different scheduling algorithm that performed best for that scheduling service. It was shown in  that, UGS is best scheduled with first in first out algorithm (FIFO), rtPs is best scheduled with earliest deadline first algorithm (EDF), nrtPs is best scheduled with weighted fair queuing (WFQ) while best effort is best scheduled with round robin (RR). Implementing different algorithms may render the system inefficient; moreover the complexity of the scheduling process will increase.
In this paper, we focus on the downlink of mobile WiMAX in TDD mode. The mode of communication is point to multipoint whereby the BS communicates with all SSs in the downlink. The scheduler at BS scheduled packets and transmits to SSs during the downlink duration. A simple but efficient scheduling algorithm using priority earliest deadline; link quality and buffer consideration for packet scheduling of four different service flows in mobile WiMAX is presented in this paper. The paper is organized as follows, Section 2 focuses on related work, Section 3 deals with the system model, Section 4 discusses on the proposed algorithm. Simulation results are presented in Section 5 and Section 6 concludes the paper.
2. Literature Review
The IEEE802.16 standard defines five scheduling classes, but it does not provide any information about the standard algorithms that should be used to provide QoS to the service flows (SFs). Call admission control (CAC) plays an important role especially when combined with scheduling service, since they are meant to manage and guarantee the QoS requirements. A single CACs algorithm cannot guarantee at all the QoS without the support of scheduling algorithm and vice versa . Although the two algorithms can be designed separately, each has to be efficient in managing the network resources. The CAC handles the performance of the bandwidth while the scheduling handles other QoS parameters like packet delay, jitter, latency and slot allocation.
Several research works have been conducted in order to provide QoS in IEEE 802.16 networks -. In , QoS scheduling architecture for the MAC protocol in 802.16 networks is presented. It is based on dynamic bandwidth allocation in the CAC and different scheduling algorithm was implemented for the service flows, UGS is scheduled with FIFO, rtPs is scheduled with EDF, nrtPs is scheduled with WFQ and best effort is scheduled RR. However, implementing different scheduling algorithm may increase the complexity of the system. In , a hierarchical structure for bandwidth allocation was presented. It used one scheduling algorithm for all the traffics, the algorithm is called deficit fair priority queue which is deployed to serve different types of service flows in both uplink and downlink, fixed modulation is used and there is no buffer management which is very important in WiMAX. The CAC algorithm was based on conventional CAC for both uplink and downlink sub frame.
In order to improve the work of , a QoS CAC was presented in  by considering delay as additional QoS parameter. The architecture is called QoS CAC and GPC mode is used employing fixed modulation. It is primarily aimed at reducing packet delay and bandwidth guarantee for various applications while achieving high system utilization with fewer figures of merit. This is at the expense of flow acceptance when compared to .
To improve the service flow acceptance and service level differentiation in , a partition-based architecture in  was presented, called partition-based CAC (PB-CAC). It is targeted at improving the capacity utilization and the flow acceptance ratio. By considering link quality, the approach performed better than  in term of service flow acceptance. Nevertheless, packet scheduling is not explained in the paper. In -, the actual link quality was not considered in either CAC or scheduling algorithm. In the actual implementation of WiMAX network, link quality is considered in order to choose the appropriate modulation schemes between BS and SS , , . The algorithm in  considered the link quality in call admission control only, but how packet should be schedule is not mention. The services of WiMAX is expected to be extend to other wireless networks like WiFi , therefore considering link quality in CAC and scheduling algorithm will enhanced the overall system throughputs. It has been shown in ,  that using the link quality will improve the overall throughput of the system.
Our main contribution in this paper is the use of link quality, current buffer state information and packet delay to scheduled all the services flows using earliest deadline algorithm called link aware earliest deadline first scheduling algorithm (LAEDF). We compare the performance of the proposed LAEDF with earliest deadline that does not consider link quality ,  we called it fixed modulation earliest deadline first (FMEDF) scheduling algorithm. Henceforth the word subscriber station (SS), traffic and service flow will be use interchangeable in the text.
3. System Model
The system was modeled with one central base station (BS) surrounded by many subscriber stations. Subscriber stations (SS) are randomly deployed with random coordinates in the coverage area of the BS. At the start traffics were initialized and admitted based on the resources needed by each subscriber station. Terrain C of Erceg model  was chosen for this simulation. The CAC implemented here is given in  and a detail mathematic model was presented in . Since in WiMAX adaptive modulation is implemented, the type modulation scheme to be use between base station and subscriber station depends on the location of the subscriber station within the cell. A user at the cell edge requires more robust modulation scheme than those close to the base station ,[ 2]. To estimate how far a subscriber station is from base station, before negotiating the modulation scheme, we use Erceg Model given in  to compute the total path loss between SS and BS which is a function of distance from the BS, and it is expressed by equation (1) given in . L = 20 log(4[pi][d.sub.0])/[lambda] + 10[gamma]log(d/[d.sub.0]) + ....
6log(/72000) - 10.8log(h/2) + sh (1)
for d > [d.sub.0]
Where [lambda] is a wavelength, [d.sub.o] is the reference distance (100m), [gamma] is path loss exponent, d is the Euclidean distance between SS and the BS whose magnitude is greater than the reference distance [d.sub.0]. f is the transmission frequency, h is the receiver antenna height and sh is the shadowing. The total path loss (L) can be computed using equation (1), from which the signal to noise ratio is obtained using equation (2) .
SNR = 20[log.sub.10]([P.sub.t][G.sub.t][.sub.r]) (2)
Where [P.sub.t] is the total transmits power from the BS, [G.sub.t] is BS antenna gain, [G.sub.r] is SS antenna gain and S is the receiver sensitivity.
We assumed that a tail-biting convolutional code (CC) is used and the SNR values can be determined for the respective modulation scheme and coding rate as shown in Table 1 . The standard in  defines 3-modulation scheme for Mobile WiMAX with seven different coding rates when using tail-biting convolution code. However, additional BPSK is required when using Reed-Solomon convolutional coding (RS-CC). In the standard, the minimum SNR value needed is 5dB for CC coding. When it's less than 5dB, no modulation is employed. For any value of SNR higher than 20dB, the highest modulation scheme and coding rate is assigned (64-QAM, 3/4). Table 1 shows the range of SNR for each modulation scheme and coding rate i.e. SNR in the range of 5dB - 8dB QPSK with V coding rate is employed.
Once the modulation scheme is known, the amount of resource (slots) required by each packet is obtained based on the type of permutation of the frame. Four different type of permutations were define in WiMAX , , these are full usage sub channelization (FUSC), partial usage sub channelization (PUSC), tile usage sub channelization (TUSC) and band AMC . Each permutation has its own definition depending on the sub frame. A slot is one subchannel in OFDMA symbol, for PUSC permutation, in the downlink a slot is one subchannel in two OFDMA symbols . Each subchannel in the downlink has 24 subcarriers for PUSC permutation in one OFDMA duration .
A slot is the minimum resource that can be allocated to a user , . A slot has 48 subcarriers since it has two OFDMA symbols in one subchannel. X is the total number of bits that can be transmitted by one slot is thus computed as;
X = [N.sub.OFDM] * [N.sub.SUBC] * [C.sub.r] * log(m) (3)
Where NOFDM is the number of OFDM in each slot, [N.sub.SUBC] is the number of subcarriers per slot, [C.sub.r] is the coding rate and m is the modulated symbol. The total data rate per slot (Y) is given by;
Y = X/fr (4)
fr is the frame duration in seconds. The total number of slots (Z) on each PUSC in the downlink sub-frame can be expressed mathematically by;TN
Z = [TN.sub.SUBC] * [TN.sub.OFDM]/2 (5)
Where [TN.sub.SUBC] is the number of subchannels in the downlink sub-frame and [TN.sub.OFDM] is the number of OFDM in the downlink sub-frame. The number of slots (TZ) in every second required by each traffic can be determine by;-
TZ = ceil w(i,t)/X (6)
Where w(i ,t) is the data rate of traffic i at time t.
The standard packet size for mobile WiMAX was given in  to be [2.sup.N] byte, were N is an integer ranging from 4 to 10. We consider the packet size for UGS traffics to be 512byte (in this case N=9) and for the remaining service flows, random values of N in the range of 4 to 10 was used. Since UGS traffics required a constant bit rate, fixed numbers of packets were scheduled in every second to adhere with data rate of the traffics. We used mod function to schedule the packet in order to adhere with its QoS in term of constant bit rate, and each packet is scheduled based on earliest deadline to ensure that no packet is lost. The number of slots requires for each packet (PZ), depends on its size (P) and the link condition since it determines the modulation scheme and is given in equation (7)
PZ = ceil (8 * P)/X (7)
We defined a parameter called frame index for UGS traffics. Frame index define as particular frame serial number in which UGS packets are scheduled to ensure a constant bit rate. The frame index is obtained as follows;- frame_index = mod (fr, j) (8)
Where j is packets inter arrival time at the receiver. Packets are scheduled when the frame index is evaluated to zero. The formulae in equation (8) is simplified as;-
frame_index = mod (Nfr, Q) (9)
Where Nfr is the number of frames in one second and Q is the packet spacing given by;_
Q = ceil w(i,t)/8 * P (10)
4. Proposed LAEDF Algorithm
The proposed link aware earliest deadline (LAEDF) algorithm scheduled packet based on 3-criterions; one is the link quality which is use in chosen modulation; each service flow has a separate buffer and the buffer status is used as second criterion and thirdly based on earliest deadline for each packet. The priority for scheduling using LAEDF algorithm is as follows; the packets arrive in random manner from the SSs. Each packet has service flow identification (SFID) with associated connection identifier (CID) therefore each packet is destined to its respective buffer. Four different buffers are used for each service flow. For UGS buffer, the packets are scheduled when the servicing frame number is a frame index or when the buffer reached 98% of its capacity. For best effort buffer, since they don't require any QoS, the packets are scheduled when the BE buffer reached 98% or more of its full capacity. For none real time traffics, the packets are scheduled when the oldest packet deadline reached 95% of its latency or when the buffer reached 98% of its capacity. Finally real time packets are always schedule if none of the above condition is satisfied. The priority of selecting the buffer is as follows; rtPs buffer is the first to be scheduled, followed by any of the 3-remaining buffers that reaches 98% of its capacity. However, when two or more buffers reaches 98% simultaneously, the second priority in the algorithm is used as follows; for UGS the scheduler check if its frame scheduling index, it schedules the UGS packets else for none real time, it check if the present oldest packet reaches 95% of its latency. We assumed that only admitted SSs transmit their packets to BS during the uplink session. The admission control algorithm in  is used in this work. The overall algorithm is as follows;
For fn=1: frame no % scheduler algorithm While time <= uplink duration All subscribers with packets transmit SS feedback estimated SNR to BS BS assigns serial number, service flow identification and arrival time Packets are stored in their respective buffer End while While time <= downlink duration Get the duration of the oldest packer (op) from nrtPs buffer If frame_index == 0 or if UGS buffer [greater than or equal to] 98% Schedule UGS else If BE buffer > 98% Schedule best effort packets Elseif op [greater than or equal to] 95% of the latency 0r nrtPs buffer [greater than or equal to] 98% Schedule nrtPs else Schedule rtPs packets End if End while End for
For scheduling the actual packet in the downlink, the scheduler determines if the frame is a new frame or it is the currently servicing frame in which some slots are already being allocated to packets. The scheduler checks the remaining slots on the servicing frame before it schedules the next packets, the approximate algorithm for checking new and servicing frame is as follows,
While time < = downlink duration) For all packets from the selected buffer Get the packets with earliest deadline Evaluate no of slots for each packet based on link quality If frame = new %(fresh frame no packet on it) Scheduled the packet with minimum latency Marked the used slots Next packet Else if frame = servicing frame (carrying some packets) If required slots <= Unmarked slots Schedule the packets with minimum latency Marked the used slots Next packet Else Wait for the next new frame If packet delay >= latency Drop the packets Next packets End if End if End for End while
The developed algorithm is compared with earliest deadline that used fixed modulation scheme called fixed modulation earliest deadline first (FMEDF) algorithm which is similar to LAEDF, but does not consider the link quality. Instead all packets are transmitted using 16-QAM with 3/4 coding rate irrespective of the SNR value of the link.
5. Simulation Results
The simulation parameters settings are shown in Table 2, during the uplink session all service flows with packet transmit. We assumed that all the subscriber stations participating has been admitted as in . Base station received all transmitted packets from subscriber stations, assigned packet serial number, packet service flow identification (SFID), connection identifier (CID), arrival time and stores the packet in appropriate buffer of the service flow. Each transmitted packet has its own estimated SNR value, which can be obtained by calculating the total path loss in equation (1) than substituting to equation (2) to get the SNR value.
During the downlink session, the scheduler in the BS scheduled the packets base on the proposed algorithm in section 4. Two parameters (packet size and SNR) are used to allocate the required number of slots of each packet. If the number of slots on the current serving frame is not enough to schedule the current packet, its delay to the next frame provided its latency will not be reached otherwise the packet is loss. The buffer size is fixed to 200 packets at a time, if the buffer is full, any incoming packet is lost. Each packet scheduled, is removed from the buffer and the memory is declared empty so that it can be used to store the next packet.
The partitioning of the downlink and uplink according to standard in  is given by 47-n, n where n is the number of OFDMA in the uplink with typical value of 12[greater than or equal to]n[greater than or equal to]21. In this paper, n is set to the minimum value of 12 which is the number of OFDMA in the uplink. According to , the number of OFDMA symbol in the downlink is 35. Since the OFDMA are equally space, using 20ms frame duration, the uplink duration was thus evaluated as (12/47) * 20ms which is equal to 5.2ms and the downlink (35/47) * 20ms which is 14.8ms. The frame duration defined by standard in [1, 2] can be 2ms, 2.5ms, 5ms, 10ms, 20ms etc. The simulation time was set to 20s, in which 1000 frames are used in the scheduling. The simulation results were shown in the Figures below.
Fig 1 shows the overall system throughput for the two algorithm. The throughput obtained when different modulation scheme is used called adaptive modulation based on link quality, is higher than the fixed modulation scheme. Therefore using different modulation scheme and coding rate in mobile WiMAX increase the overall system throughput. The proposed LAEDF algorithm outperformed FMEDF in term of throughput as shown in Fig. 1.
Fig. 2 shows the frame utilization, each sub frame in the downlink has a total of 225 slots. The frames can be seen to carry different data size depending on the link quality and packet size. The black line is for LAEDF algorithm, it can seen that some frame carries no data due the link condition, if the SNR value of the link is less than 5dB according to standard there will be no transmission. The red line is for FMEDF algorithm, it can be seen that FMEDF is nearly constant on each frame irrespective of the link quality.
Fig. 3 shows the actual throughput of each service flow for the first 200 packets, it can be seen that the throughput falling when the system load increases with time. The UGS has the highest throughput followed by rtPs. Best effort and none real time traffics have almost the same throughput.
Fig. 4 shows the actual duration of the packets in the buffer which can be obtain by finding the difference between the arrival time and the departure time. It can be seen that, each arrival packet is scheduled before its latency. It is very important to note that real time packets has the minimum waiting time in the buffer followed by UGS packet. The first none real time packet was scheduled at the 800ms of the simulation which is 98% of the latency of the oldest packet. For best effort, the first packet was scheduled when the simulation time reached 2000ms, this is the time at which the buffer of the best effort first reached 98% of its full capacity.
Fig. 5 shows the link quality of the first few scheduled packets as a function of the arrival time, and the SNR varies from 7dB to 33dB. This covers all the available modulation scheme and coding rate given in Table 1.
Fig. 6. shows a specific case for UGS traffics, whereby the packet size is 512 byte at different link quality. It can be seen that, the schedular at BS allocates different number of slots to transmit the packet to SSs. This is primarily due to the fact that different modulation scheme and coding rate are used. At highest SNR value of 20dB and above, 18 slots are required while at the lowest value of the SNR (<10dB), 57 slots are required. This can be variefied numerically using equation (3) and (7) in which the total number of slots per packet is computed. The relationship between the number of slots required by each packet and the corresponding link quality can be obtain by drawing line of best fit as shown in Fig. 6. The better the quality of the link the less number of slots required by a packet.
[FIGURE 1 OMITTED]
[FIGURE 2 OMITTED]
[FIGURE 3 OMITTED]
[FIGURE 4 OMITTED]
[FIGURE 5 OMITTED]
[FIGURE 6 OMITTED]
In this paper, we presented a scheduling algorithm in Mobile WiMAX. The proposed algorithm LAEDF which uses link quality was found to perform better than FMEDF algorithm which assumes fixed modulation irrespective of the link quality. The results showed how the wireless link affects the throughputs and the frame utilization. Since WiMAX uses adaptive modulation and coding, the link quality should be taken into consideration in scheduling. The simulation showed a fair scheduling among the service flows despite the use of the wireless link condition in scheduling. The proposed approach has achieved high throughputs and good frame utilization.
The authors would like to thank to all the reviewers for their insightful comment. This work was sponsored by the Research Management Unit, Universiti Teknologi Malaysia.
 WiMAX Forum, Krishna Ramadas and Raj Jain, "WiMAX System Evaluation Methodology" version 2.1 July 2008
 IEEE Std. 802.16e, "IEEE Standard for local and metropolitan area networks, part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems, Amendment 2: Physical and Medium Access Control Layers for Combined Fixed and Mobile Operation in Licensed Band and Corrigendum 1", May 2005
 K. Wongthavarawat, and A. Ganz, "Packet Scheduling for QoS Support in IEEE 802.16 Broadband Wireless Access Systems", International Journal of Communication Systems, Vol. 16, p81-96, 2003
 Jianfeng Chen, W. Jiao, and H. Wang, "A Service Flow Management Strategy for IEEE 802.16 Broadband Wireless Access Systems in TDD Mode," IEEE International Conference on Communication, ICC 2005.
 Sarat Chandra and Anirudha Sahoo "An Efficient Call Admission Control for IEEE802.16 Networks Proc of the 15th IEEE Workshop on Local and Metropolitan Area Networks, Princeton, New jersey, pp 188-193, June 2007
 D. S. Shu'aibu, S. K. Syed-Yusof and N. Fisal "Partition -Based Bandwidth Management for Mobile WiMAX IEEE802.16e," International Review on Computers and Software,. Vol 5 no. 4, pp 445-452 Jul. 2010
 Wernhuar Tarng , Nai-Wei Chen, Li-Zhong Deng, KuoLiang Ou, Kun-Rong Hsie, Mingteh Chen. "The Integration of Heterogeneous Wireless Networks (IEEE802.11/IEEE802.16) and its QoS Analysis," International Journal of Communication Networks and Information Security, Vol. 2, No 3, pp. 141-150, 2010.
 J. Faezah and K. Sabira, "Adaptive Modulation for OFDM Systems," International Journal of Communication Networks and Information Security, Vol. 1, No 2, pp.1-8 .2009
 D. S. Shu'aibu and S. K. Syed-Yusof "Slot Allocation Algorithm for Real Time and None Real Time Traffics of Mobile WiMAX IEEE802.16e," International Journal of Computer Applications, Vol 8 no. 7, pp.1216.2010
 Bernard Sklar 'Digital Communications Fundamentals and Application second edition, Prentice-Hall International Inc Upper Saddle River, New Jersey USA pp. 286- 289, 2001.
D. S. Shu'aibu (1) and S. K. Syed-Yusof (2)
(1,2) Department of Radio Communication, Faculty of Electrical Engineering, Universiti Teknologi Malaysia email@example.com
Table I. Receiver snr in (db) Modulation type Coding rate SNR (dB) QPSK V 5.0 3/4 8.0 16-QAM 1/2 10.5 3/4 14.0 64-QAM 1/2 16.0 2/3 18.0 % 20.0 Table 2. parameter settings Parameter Settings FFT Size 1024 Bandwidth 10MHz DL/UL ratio 35:12 No. of Subchannels 15 (downlink only) Frame duration 20ms Permutation PUSC (downlink) Packets sizes (UGS) 512 byte Packets sizes for others [2.sup.N] (5[less than or equal to] N [less than or equal to] 10) bytes Latency for UGS 150ms Latency for rtPs 200ms Latency for nrtPs 900ms Latency for BE 10 seconds Path loss model Erceg Transmission frequency 3.45GHz Path loss exponents 4.0 Shadowing component 8.9 BS transmitting power 42 (dBm) BS antenna gain 16 (dBi) Receiver sensitivity -107.1 (dBm) Receiver antenna gain -1.10 (dB)
|Printer friendly Cite/link Email Feedback|
|Author:||Shu'aibu, D.S.; Syed-Yusof, S.K.|
|Publication:||International Journal of Communication Networks and Information Security (IJCNIS)|
|Date:||Apr 1, 2011|
|Previous Article:||A fuzzy-based routing strategy for multihop cognitive radio networks.|
|Next Article:||Throughput parameter optimization of adaptive ARQ/HARQ scheme.|