Subscribe Now Subscribe Today
Research Article
 

A Two-Layer Channel-Aware Scheduling Algorithm for IEEE 802.16 Broadband Wireless Access Systems



R. Ghazizadeh, P. Fan and Y. Pan
 
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail
ABSTRACT

In this study, a two-layer channel-aware scheduling algorithm, named Adaptive Credit-Based Fair Queuing (ACFQ) Based on Credit-Based Fair Queuing (CBFQ) is introduced. The proposed algorithm adapts the error-free CBFQ with the multi-rate nonideal environment considering the Adaptive Modulation and Coding (AMC) at the radio link layer and provides packet-level Quality of Service (QoS) over the wireless fading channel. It is shown that the introduced AMC architecture and compensation model in two-layer scheduling provide fair sharing while ensuring high bandwidth efficiency. Furthermore, the proposed scheduler exhibits very low complexity, thus suitable for practical implementation.

Services
Related Articles in ASCI
Search in Google Scholar
View Citation
Report Citation

 
  How to cite this article:

R. Ghazizadeh, P. Fan and Y. Pan, 2009. A Two-Layer Channel-Aware Scheduling Algorithm for IEEE 802.16 Broadband Wireless Access Systems. Journal of Applied Sciences, 9: 449-458.

DOI: 10.3923/jas.2009.449.458

URL: https://scialert.net/abstract/?doi=jas.2009.449.458
 

INTRODUCTION

The increasing demand for high-speed Internet access and multimedia services such as voice over IP, video conferencing and video on demand have led to a rapid growth in demand for broadband networks access. The rapid dissemination of broadband wired access technologies such as leased line based on fiber-optic links and digital for subscriber line (xDSL) access networks aim to support this demand. Meanwhile, access to broadband wired technologies can be too expensive for users who are located in the environments such as rural and suburban areas, where, there is slow development of traditional wired technologies. In this way, one of the most promising alternatives for the last-mile access is Broadband Wireless Access (BWA) technologies which represent low cost and high scalability. In the last few years, IEEE 802.16 working group have developed standards for fixed BWA system operating at 10-66 GHz (i.e., IEEE 802.16) or 2-11 GHz band (i.e., IEEE 802.16a). Furthermore, to exploit advanced technologies and provide more flexibility, the other versions named IEEE802.11d/e is currently developed which promises to support mobility up to speed 70-80 mi h-1, Hybrid Automatic Repeat Request (HARQ) and Adaptive Modulation Coding (AMC) (IEEE Std. 802.16e, 2006).

Although IEEE802.16 standard, known in the trade press as the world interoperability for microwave access (WiMAX), incorporates several advanced radio transmission technologies but it presents very challenging aspects in term of radio resource management. One of the fundamental challenges is the provision of Quality of Service (QoS) guarantees for different categories of applications with various QoS requirements such as allocated bandwidth, packet loss and maximum delay. On the other hand, in the nonideal channel where fair assignment of resources can be disturbed due to the channel quality, providing the fair resource allocation is another challenge. In these conditions, fair radio resource management through scheduling algorithms plays a key role in QoS provision. However, currently, the standard leaves the QoS support based packet-scheduling algorithms and efficient radio resource management as an open issue to research.

Many scheduling methods have been proposed in ideal channel networks where the physical channel is error-free. Cicconetti et al. (2006, 2007) described the QoS framework of IEEE 802.16 where classical algorithm is applied. Deficit Round-Robin (DRR) as the downlink scheduler and Weighted Round-Robin (WRR) as the uplink scheduler were recommended. Moreover, hybrid scheduling with different disciplines was introduced by Wongthavarawat and Ganz (2003). Wireless Fair Queuing

(WFQ), Earliest Deadline First (EDF), WRR and First-in-First-out (FIFO) were applied for different classes of traffic. Chen et al. (2005) proposed a hierarchical scheduling structure of the bandwidth allocation using a deficit fair priority queue for multiple services. Meanwhile, those schedulers cannot directly apply to the wireless environment due to highly variable and unpredictable characteristics of the wireless medium both on a time-dependent basis and a location-dependent basis. To achieve efficient performance and diverse quality of service guarantees, the schedulers need to monitor the channel and employ dynamic variation of wireless channel characteristics on the packet scheduling. Some fair scheduling algorithms have been proposed for wireless networks. Meanwhile, most of them have assumed the channel is either in a good or a bad state. Transmissions in a good state succeed and completely fail in a bad channel. Fattah and Leung (2002) introduced wireless DRR (WDRR) based on DRR which enjoys compensation components in the wireless channel. A scheduling algorithm that provides scheduling guarantees for continuous channel model was proposed by Liu et al. (2003). Lera et al. (2007) defined a technique for channel error compensation coupled with a WF2Q+ based scheduling algorithm.

In this study, a two-layer channel-aware fair scheduler operating in the downlink WiMAX environment based on the Credit-Based Fair Queuing (CBFQ) scheduling algorithm is proposed. The CBFQ algorithm is an error-free credit-based algorithm which employs counters to keep track of the credit accumulated by each flow. Despite of the time-stamped algorithm family which relies on a common-reference virtual clock and consequently introduces more complexity by the simulation of the Generalized Processor Sharing (GPS, idealized fluid flow model that services all flows simultaneously), the CBFQ uses simple bounded counters and introduces a simple and efficient algorithm. In this study, the CBFQ algorithm is extended by considering WiMAX specific characteristics in the nonideal wireless channel where the AMC and the ARQ mechanisms are applied. Applying the AMC mechanism enables the stations to choose a channel data rate based on the channel conditions dynamically. In this case, the scheduler should provide fair temporal access. In the fair temporal access, each user captures the medium in the form of fair share of the time which the CBFQ is unable to support it. Temporal fairness guarantees that the user with the poor channel cannot reduce the throughput of other stations.

IEEE802.16 BROADBAND WIRELESS NETWORKS

IEEE802.16/WiMAX supports two operation modes for sharing the medium to provide more flexibility for different applications: point-to-multipoints (PMP) mode and mesh mode. In the point-to-multipoints (PMP) which is the focus of this study, a single BS interconnects multiple subscriber stations (SSs) located in the same network to the Internet. All SSs receive the same information from BS while transmissions from SSs are directed by the BS. On the other hand, in the mesh mode, traffic can be routed through meshing among the SSs. IEEE802.16/WiMAX supports a connection-oriented MAC protocol which managed by the BS. 16-bit connection identifier (CID) is used primarily to identify each connection to the BS. Service Data Unit (SDU) generated by applications are encapsulated in the form of Protocol Data Unit (PDU) with 6-byte header. MAC layer can fragment SDU to multiple PDUs if the SDU is larger than PDU size.

Two transmission modes are provided for duplexing uplink and downlink subframes in IEEE802.16/WiMAX: Frequency-Division Duplex (FDD) and Time-Division Duplex (TDD) transmission modes. In the FDD, the uplink and the downlink subframe operate on separate frequencies while they occur at the same time. On the other hand, in the TDD, uplink and downlink subframe share the same frequency on the separate time. In this study, we refer to TDD mode. In this case, time is equally divided into fixed durations, named frame. Each frame consists of a downlink and an uplink sub-frame with Tx/Rx Transmission Gap (TTG) and Rx/Tx transmission gap (RTG). At the beginning of the downlink frame, the BS transmits a sequence of physical preamble to let the SSs recover synchronization and channel estimation. After that, the BS broadcasts the uplink and the downlink MAP messages, UL-MAP and DL-MAP, respectively. These messages enable each SS to know, when and how long it can receive and transmit data to the BS during forthcoming the downlink and the uplink sub-frames. In the downlink sub-frame, all SSs listen to the data transmitted by the BS. Each SS processes only the MAC PDUs contains its own CID and discards the other PDUs. In the uplink subframe, any SS transmits a burst of MAC PDU to the BS in the Time-Division Multiple Access (TDMA) manner.

IEEE802.16/WiMAX introduces five classes of services which provide various QoS requirements. These services are: Unsolicited Grant Service (UGS), real-time polling service (rtPS), extended real-time polling service (ertPS), non-real-time Polling Service (nrtPS) and Best Effort (BE):

UGS supports real-time applications with strict delay and loss requirements which generate fixed packet size at periodic intervals. BS grants unsolicited bandwidth to a connection in a static manner. The size and the period of allocated bandwidth are negotiated in the initialization process. After that, the BS assigns allocated bandwidth periodically and the connection never requests bandwidth. This service provides guarantees on throughput, latency and jitter
rtPS supports real-time applications which generate variable-size data packets on periodic intervals such as Moving Pictures Expert Group (MPEG) video. As the length of packets is variable, instead of UGS, the required bandwidth in each frame is variable and depends on the amount of the data buffered in the queue
ertPS is defined to better support real-time applications such as voice over IP with silence suppression. Therefore, similar to UGS, the default bandwidth corresponding to maximum sustained traffic rate is provided to support traffic flows
nrtPS reserves a minimum amount of bandwidth only. Therefore, this service is suitable for applications that do not have specified delay requirements such as File Transfer Protocol (FTP)
BE service provides no guarantees on delay or throughput and does not reserve any bandwidth

GENERAL CBFQ ALGORITHM

Simplicity, robustness and fairness are important properties which queuing discipline should posses in broadband networks. The scheduling disciplines should be simple to allow practical implementation and also robust to protect well-behaved source from misbehaving ones. Furthermore, it should be able to distribute available bandwidth fairly among active traffic flows.

Many scheduling algorithms have been proposed which attempt to approximate the same Fluid Fair Queuing (FFQ) policy (Parekh and Gallager, 1993). FFQ policy is an idealized, efficient, flexible and fair scheduler which services all flows simultaneously. WFQ (Demers et al., 1989), worst-case fair packet fair queuing (WF2Q) (Bennett and Zhang, 1996) and Self Clock Fair Queuing (SCFQ) (Golestani, 1994) are three schedulers which search that policy. They are a family of virtual time-based algorithms which relies on virtual clock and assigns each packet a virtual start time and a virtual finish time based on virtual arrival time, packet length and reserved transmission rate. WFQ and W2FQ need to emulate a reference FFQ server which is computationally expensive. One simpler packet approximation algorithm of FFQ is SCFQ which approximates the system’s virtual time by virtual time of the packet that currently being serviced. The main limitation of SCFQ is that it increases the maximum delay incurred by packets significantly. However, in the virtual time-based family, since the time tag is an increasing function of the time, the virtual clock cannot be reinitialized to zero until the system is completely empty and all session are idle. Therefore, the virtual time can be extremely large and needs huge buffers. To avoid the complexity of the virtual time approach, the Deficit Round Robin (DRR) has been proposed by Shreedhar and Varghese (1996). Although this algorithm is very simple but depending on the choice of parameters of the system, the fairness bound can arbitrarily derivate from the bounds provided by virtual time-based algorithm. Furthermore, the maximum delay bound can be arbitrarily high since the weights of the different flows are arbitrary numbers. Finally, CBFQ (Bensaou et al., 2001) provides bounded counter value which avoids the overflow problem that may be encountered in the virtual time-based algorithm and provides same fairness and end-to-end delay bound as the SCFQ algorithm with lesser complexity. In this study, the CBFQ algorithm as an error-free algorithm is adapted to WiMAX characteristics in the nonideal wireless environment. At the rest of this section, the CBFQ algorithm is described.

Suppose a set N of flows share the outgoing channel with each flow having a weight (φ) and a credit value (k). A counter in each flow stores the number of credits earned by corresponding traffic flow. Flow selection criteria to transmit of its head of line (HOL) packet is based on the size of HOL packets, the credits and the weights of backlogged flows in the system which satisfy following expression:

Image for - A Two-Layer Channel-Aware Scheduling Algorithm for IEEE 802.16 Broadband Wireless Access Systems
(1)

where, B denotes the set of backlogged flows and Li is the length of the HOL packet of flow i. When a HOL packet of selected flow, say one, is transmitted, its credit value is set to zero regardless of its value and the credit of other flows update according a following equation:

Image for - A Two-Layer Channel-Aware Scheduling Algorithm for IEEE 802.16 Broadband Wireless Access Systems
(2)

Once a flow becomes unbacklogged (i.e., queue becomes empty) or new flow enters the system, its credit value is set to zero.

Due to characteristics of the wireless channels such as location-dependent and bursty errors, the fair queuing algorithms for wireline networks do not apply directly to the wireless networks. Therefore, to provide fairness and efficient performance in the wireless environment, each scheduler generally should maintain following components: Error-free service model, lead/lag model and compensation model, that is:

Error-free service model is a fair service algorithm which provides service to flows with the error-free channel. Our proposed algorithm utilizes the CBFQ algorithm as an error-free service model and modify it to exploit multi-rate capacity while provide packet-level QoS in the presence of channel errors
Lead/lag model determines which flow and how much is leading, lagging or in sync with the error-free service model. The lag counter of a selected flow increases, if it is unable to transmit due to the channel conditions. On the other hand, the lead counter of a substitute flow increases fairly which allows the compensation model to provide fairness among flows
Compensation model allows the scheduler to compensate a lagging flow at the expense of a leading flow when the lagging flow link change to transmit status

TWO-LAYER CHANNEL-AWARE SCHEDULING ALGORITHM

Here, first, the two-layer hierarchical scheduler consists of an aggregate scheduler and three class schedulers corresponding to rtPS, nrtPS and BE traffic is described. As the UGS traffic is assigned fixed bandwidth periodically and ertPS traffic enjoy a default bandwidth corresponding to the maximum sustained traffic rate, scheduling for these types of classes are not required and only three types of classes, rtPS, nrtPS and BE, are considered for scheduling. Then, the design of the Adaptive Credit-Based Fair Queuing (ACFQ) in the multi-rate WiMAX environment is explained. Finally, to provide fairness in the wireless medium, the self lead/lag and the compensation model are described.

As it is mentioned here, IEEE802.16/WiMAX provides five types of classes supporting different quality of service requirements. Therefore, each flow is classified to one of available classes (UGS, rtPS, ertPS, nrtPS and BE) during connection initialization phase. Classification is based on QoS requirement of applications. Consequently each class can maintain several flows. All received packets of a flow is buffered to queue that they belong to. As it is shown in Fig. 1, the two-layer hierarchical scheduling using an ACFQ in each layer has employed.

Image for - A Two-Layer Channel-Aware Scheduling Algorithm for IEEE 802.16 Broadband Wireless Access Systems
Fig. 1: Two-layer channel-aware scheduler

In the first layer, each class scheduler, scheduler belong to each class, enjoys an ACFQ scheduler to serves HOL packets of its flows queue. The scheduler assigns to each flow a credit counter and selects packets based on the HOL packet size, the credit value and the channel data rate among the classmate flows (flows in the same class). In the second layer, an aggregated scheduler allocates a credit counter to each class queue which is updated based on the credit counter and the transmission time of transmitted packet. The packet selection process is similar to first layer scheduling. Packets are selected among the HOL packet of classes queue. This type of scheduling distributes the bandwidth among the flow adaptively.

Since, the both layer use the same scheduler, ACFQ, we describe the ACFQ operation which is based on the CBFQ algorithm. The CBFQ as an error-free scheduler can serve flows in an error-free medium with a fixed channel data rate. However, in the nonideal channel, the performance of an error-free scheduler decreases dramatically due to blind transmission in a fixed channel data rate. Therefore, to improve spectrum efficiency, the channel-aware scheduling using an AMC mechanism is unavoidable.

Now, to support the multi-rate environment and provide fair temporal access, the CBFQ algorithm is modified. In this way, the Eq. 1 is redefined as follows:

Image for - A Two-Layer Channel-Aware Scheduling Algorithm for IEEE 802.16 Broadband Wireless Access Systems
(3)

where, Li represents the HOL packet size of flow i, Ci denotes the channel data rate of the flow corresponding to Li and ki is the credit value of flow i in terms of time. In this case, each backlogged flow will receive a fair share in terms of transmission time and consequently system performance will be improved by multiplexing better channel conditions across the users. On the other hand, all flows will receive time shares in proportion of their weights governed by the QoS requirements.

However, when the HOL packet of a flow, say j, is transmitted, the credit of the flow is updated based on the transmission time of its HOL packet as shown in the following equations. As it is assumed that the credit is a positive value, if selected flow (j) does not accumulate enough credit to transmit of its HOL packet, the scheduler will add so credit to all backlogged queues that the selected flow earns enough credit for transmission of its packet. Adding credit to other flows is proportion with their weight:

Image for - A Two-Layer Channel-Aware Scheduling Algorithm for IEEE 802.16 Broadband Wireless Access Systems
(4)

Image for - A Two-Layer Channel-Aware Scheduling Algorithm for IEEE 802.16 Broadband Wireless Access Systems
(5)

As, the HOL packet selection criteria depends on the channel conditions, the scheduler requires collecting the channel information of each active SS. Therefore, each SS monitors its channel status continuously and sends the required information to the BS. At the beginning of each frame, according to the received channel information, a rate selection scheme determines the channel data rate of each SS and marks flows which their channel data rate are zero as blocked flows. The scheduler assumes that the channel data rate remains constant in the whole of forthcoming frame duration. But it is allowed to vary from frame to frame.

To provide fairness among the flows in a class and let a blocked flow to compensate in the future, the class scheduler should employ a lead/lag counter for each flow and update it when a selected flow gives up packet transmission to another flow as a substitute flow. The lead/lag counter allows a compensation model to know and how much time each leading flow should give up and lagging flow should compensate in the future. Applying the ACFQ scheduler among the flows in the same class (class scheduler) can automatically provide the lead/lag counter and the compensation model. When a rate selection scheme blocks a flow due to the dirty channel (a channel with high packet error rate), the scheduler bypasses the flow and schedules other flows. However, during blocking period, the bypassed flow collects credits as a lead/lag tag (Eq. 5) while the other classmate flows are served. Note that, the bandwidth belongs to the blocked flow is properly distributed among the backlogged classmate flows. Finally, when the lagging flow perceives a clean channel, it will have smallest tag and be able to catch up on its lag. Meanwhile, a lagging flow that has been in an error-prone channel for a long time can capture the channel for a long time after it perceives a clean channel. To solve the problem and prove a guarantee for maximum delay, the amount of credit can be bounded by a maximum value which leads to bounding the amount of compensation. This structure introduces a simple fair scheduling which is an important property in practical implementation.

CHANNEL MODEL AND CHANNEL RATE SELECTION SCHEME

WiMAX supports AMC mechanism to achieve efficient bandwidth utilization. In this section, we introduce AMC design for time-vary wireless channel similar to that Liu et al. (2005) proposed. The objective of AMC is to maximize the channel data rate by adjusting transmission mode to the channel variation while maintaining a prescribed packet error rate (PER, P0).

IEEE 802.16 provides seven physical modes with various modulations and coding rate operating based on OFDM technology. BPSK, QPSK, 16 QAM and 64 QAM modulations with convolution coding in different rates provide capabilities of communicating at different channel data rate.

To model the physical channel, suppose that the channel is frequency flat and remains invariant per constant time period, namely frame. Therefore, channel quality can be expressed by the received Signal to Noise Ratio (SNR) and, the general Nakagami-m model can be applied to this channel. To model a slow Nakagami fading channel, a Finite State Markov Channel (FSMC) with K+1 states is assumed. The received SNR (γ) at the receiver is partitioned into the finite number of non-overlapping consecutive intervals. Let γ01<...γK+1 be the thresholds of the received SNR for different states. The channel is said to be in the state n if γn <γ <γn+1 n = 0,1,...K. To avoid deep channel fades, no data are sent when γ01 (mode 0). Suppose seven transmission modes introduced in IEEE802.16 are corresponding to the states of a FSMC (with 8 states). It means that when the channel is in the state n, mode n will be used and packets will be transmitted with the channel data rate associated with that mode.

Now, to find out the thresholds and the state transition matrix of the FSMC, first, average packet error rate is computed. Since there is no exact closed-form expression for the Packet Error Rate (PER) in coded modulations. In this study, without loss of generality, the upper bounds of PER equations (Proakis, 2000) are utilized and for simplicity approximated with the following formula (Liu et al., 2005):

Image for - A Two-Layer Channel-Aware Scheduling Algorithm for IEEE 802.16 Broadband Wireless Access Systems
(6)

where, n is mode index, an, gn and γth are constant parameters which are determined through the fitting algorithm. Average PER in mode n, Image for - A Two-Layer Channel-Aware Scheduling Algorithm for IEEE 802.16 Broadband Wireless Access Systems is found to be (Liu et al., 2005):

Image for - A Two-Layer Channel-Aware Scheduling Algorithm for IEEE 802.16 Broadband Wireless Access Systems
(7)

where, Image for - A Two-Layer Channel-Aware Scheduling Algorithm for IEEE 802.16 Broadband Wireless Access Systems represents average received SNR, m denotes the Nakagami fading parameter (Rayleigh channel m = 1), Pr(n) denotes probability of chosen mode n, Г(m, x) is the complementary incomplete Gamma function and Г(m) is Gamma function.

Similar to Liu et al. (2005), it is assumed that the average PER is the same and equals to a prescribed target packet error in all modes Image for - A Two-Layer Channel-Aware Scheduling Algorithm for IEEE 802.16 Broadband Wireless Access Systems. Therefore, the received SNR thresholds can be calculated with the assumption γN+1 = ∞, γ0 = 0 and above equation through a simple searching algorithm. Finally, using the determined thresholds, the BS can easily find out channel mode once receives SNR. Readers can find more details about the computing of thresholds and state transition matrix of the FSMC from Liu et al. (2005, 2006) and Zhang and Kassam (1999).

RESULTS AND DISCUSSION

Here, we evaluate proposed two-layer hierarchical ACFQ in various scenarios and compare its performance in terms of throughput and temporal fairness with the CBFQ in the error-free channel and the error-prone channel. The scheduler with the awareness and unawareness of the channel is considered in the error-prone channel. Unaware-channel scheduler sends packet blindly regardless of the channel conditions resulting in huge packet loss in the dirty channel (high packet error rate state) and wasting the bandwidth. On the other hand, the channel-aware scheduler stops transmission at the high packet error rate conditions and lets the other users with the clean channel to use the bandwidth efficiently.

Table 1: Traffic parameters
Image for - A Two-Layer Channel-Aware Scheduling Algorithm for IEEE 802.16 Broadband Wireless Access Systems

Finally, the performance of the scheduler is compared with the scenario that adjusts the channel data rate using the AMC mechanism and introduced channel selection scheme (i.e., Dynamic in legends). To best concept of proposed scheduler operation, CBRs flows with the same characteristics are simulated for each class. The packet size is 60-byte and the maximum sustained rate vary from 100 to 800 Kbps. However, the performance of the scheduler is also evaluated in the presence of specific traffic models such as MPEG model for rtPS traffic and WEB traffic model for nrtPS and BE.

To provide a heterogeneous traffic environment, a single cell IEEE 802.16/WiMAX network with five SSs maintaining various traffic flows is simulated. The simulation is written in C++. The MAC protocol works in the OFDMA/TDD mode and frame size is 5 m. Maximum 360 symbols out of 1250 symbols considered at each frame are assigned to the downlink subframe. the scheduler can utilize a AMC mechanism with seven transmission modes in the presence of the Rayleigh fading channel by assuming Fading parameter (m), Doppler frequency and prescribed PER equal to 1, 0 Hz, 10 E-4, respectively. The type of traffic in each station is specified at the Table 1. Station one has three type of traffic flows (rtPS, nrtPS and BE), the type of traffic flows of station 2 are rtPS and nrtPS, station 3 has rtPS and BE traffic flows and the type of traffic flows of station 4 and 5 are nrtPS and BE, respectively. Packet buffer size of each flow is limited to 300 packets. Therefore, all arriving packets finding full buffer will be dropped. Furthermore, those packets with delay more than their maximum tolerated delay will be removed as well.

Weight of classes (4, 2 and 1 for rtPs, nrtPS and BE, respectively) is chosen arbitrarily to provide different level of bandwidth access. Meanwhile, the weights can be chosen dynamically by the scheduler according to the network conditions such as queue size, arrival rate and packet delay. Furthermore, it is assumed that the weight of classmate flows is equal to one. Similar to Lera et al. (2007), the rtPS, nrtPS and BE classes are mapped over the ITU QoS classes 1, 4 and 5, respectively which is Y.1541 recommendation of International Telecommunication Union Telecommunication (ITU-T) standardization sector. Two type of transmission are assumed, fixed and dynamic transmission. In the fixed transmission scenario, stations select the fixed transmission mode specified in Table 1. But in the dynamic transmission, the transmission mode is selected by rate selection scheme, introduced in the previous section, according to channel quality.

Figure 2 compares the throughput of the rtPS, nrtPS and BE traffic versus maximum sustained rate per flow in the presence of the ideal channel for CBFQ and ACFQ. Below saturation level, all flows can capture required bandwidth. But, by increasing bandwidth demand, all available capacities are occupied and, first BE and then nrtPS flows cannot gain their required bandwidth and consequently throughput degrades. However, all types of the traffic in the ACFQ demonstrate better performance than those of the CBFQ. Providing the temporal fairness by ACFQ improves the throughput in the multi-rate environment. In this case, the classmate flows share the allocated time duration equally and provide more chance for high data rate flows to access the medium. The temporal fairness among the classmate flows is shown in Fig. 3. Since the CBFQ attempts to provide throughput fairness among the classmate flows, low data rate flows capture higher transmission time than high data rate flows. The worse conditions can happen when the low data rate flow with the poor channel catch up the medium. In this case, the flow can reduce the throughput of other flows to arbitrarily low levels while the ACFQ provide performance isolation and achieves a high temporal fairness in the nonideal channel by the compensation model.

Figure 4 shows the throughput of the scheduler over the ideal channel and, channel-aware and channel-unaware scheduler over the nonideal channel. Scheduling in the case of unawareness of channel conditions demonstrates the impact of the nonideal channel on bandwidth utilization. While the transmission in the dirty channel causes the packet transmission failure and consequently staying more packets in the queue, more dropping and more delay, the channel-aware scheduling improves the throughput by granting the bandwidth of blocked flows in the dirty channel to others with the clean channel in the same class. Furthermore, the compensation technique makes fair bandwidth distribution among the flows.

As the channel quality can change dynamically, using the AMC mechanism and selecting the channel data rate according to the channel conditions through introduced channel data rate selection scheme guarantees the further improvement of the system performance. Figure 5 shows the throughput improvement in all classes using a dynamic channel data rate selection scheme in comparison with those of with the fixed multi-rate channel data rate.

Image for - A Two-Layer Channel-Aware Scheduling Algorithm for IEEE 802.16 Broadband Wireless Access Systems
Fig. 2: Throughput of ACFQ and CBFQ over ideal channel

Image for - A Two-Layer Channel-Aware Scheduling Algorithm for IEEE 802.16 Broadband Wireless Access Systems
Fig. 3: Temporal fairness in ACFQ and CBFQ over ideal channel

Image for - A Two-Layer Channel-Aware Scheduling Algorithm for IEEE 802.16 Broadband Wireless Access Systems
Fig. 4: Throughput over ideal channel, nonideal channel with a channel-aware and a channel-unaware scheduler

While in the fixed channel data rate scenario, the scheduler only serve the flows that are in the clean channel with the fix channel data rate, the dynamic channel data rate provide the various transmission rates based on channel quality.

Finally, to best appreciate of the scheduler, Fig. 6 and 7 show the total throughput and total delay for CBFQ in the ideal channel and the nonideal channel and, ACFQ in nonideal channel with fixed and dynamic transmission rate.

Image for - A Two-Layer Channel-Aware Scheduling Algorithm for IEEE 802.16 Broadband Wireless Access Systems
Fig. 5: Throughput over nonideal channel with fixed transmission rate and dynamic transmission based on channel quality

Image for - A Two-Layer Channel-Aware Scheduling Algorithm for IEEE 802.16 Broadband Wireless Access Systems
Fig. 6: Total throughput over ideal channel and nonideal channel with channel-aware and channel-unaware scheduler

Image for - A Two-Layer Channel-Aware Scheduling Algorithm for IEEE 802.16 Broadband Wireless Access Systems
Fig. 7: Total packet delay over ideal channel and nonideal channel with channel-aware and channel-unaware scheduler

To evaluate the temporal fairness among the classmate flows, we use the Jain’s fairness index introduced by Jain et al. (1984) which is defined as follows:

Image for - A Two-Layer Channel-Aware Scheduling Algorithm for IEEE 802.16 Broadband Wireless Access Systems
(8)

where, xi is the effective transmission time achieved by flows i and m is the No. of flows in the same class. Table 2 shows the fairness index of the ACFQ over the ideal channel, the nonideal channel with the fixed and the dynamic transmission rate and the CBFQ over the nonideal channel. As it is obvious, using a compensation technique in the ACFQ provides a proper fairness among the classmate flows in the nonideal channel.

Image for - A Two-Layer Channel-Aware Scheduling Algorithm for IEEE 802.16 Broadband Wireless Access Systems
Fig. 8: Throughput over ideal channel, nonideal channel with a channel-aware and a channel-unaware scheduler

Table 2: Temporal fairness index
Image for - A Two-Layer Channel-Aware Scheduling Algorithm for IEEE 802.16 Broadband Wireless Access Systems

Finally, to show the effectiveness of present proposed algorithm, we testified the ACFQ at the presence of the following traffic models. A video source model is served for rtPS traffic. The source model is a trace of a real MPEG4 video stream of an e-learning session (Arizona state university http://trace.eas.asu.edu/ TRACE/trace.html) with 440 Kb sec-1 mean arrival rate and 2200 bytes mean packet size. The nrtPS and BE traffic use an Internet traffic with packet sizes drawn from Pareto distribution (with the shape factor = 1.1 mode = 4.5 KB and cutoff threshold = 200 KB) while packet inter arrival time are distributed exponentially (with average 0.2 in nrtPS traffic and 0.5 in BE traffic). It is assumed that all stations have all types of traffic (rtPS, nrtPS and BE) with one of defined average SNR (13, 15 and 18 dB). However, the number of stations with different received SNR is the same in the network.

Figure 8 shows system throughput in the different scenario similar to Fig. 4 at the new traffic models. Furthermore, it is obvious that the high weight traffic (rtPS flows) can capture their required bandwidth even though the lower weight traffic (nrtPS flows) offers more traffic than high weight traffic.

Image for - A Two-Layer Channel-Aware Scheduling Algorithm for IEEE 802.16 Broadband Wireless Access Systems
Fig. 9: Throughput over ideal channel, non-ideal channel with a channel-aware and a dynamic scheduler

Finally, using the dynamic selection rate scheme according to channel quality shows performance improvement significantly especially in overloaded conditions (Fig. 9).

CONCLUSIONS

In this study, a two-layer scheduling algorithm has been proposed for providing QoS guarantees and fairness in IEEE 802.16 networks over the wireless error-prone channels. The ACFQ enjoys a CBFQ as an error-free scheduler which is adapted with the channel conditions and the multi-rate environment. The HOL packet of flows is scheduled according to the credit of flows and the channel data rate. The AMC architecture and the rate selection scheme provides the best channel data rate for the physical channel of each SS at the beginning of each frame based on prescribed PER. Using AMC, ARQ and compensator components cause the proposed scheduler can attain considerable improvement in terms of throughput, packet delay and temporal fairness among the flows. On the other hand, the low complexity of scheduling discipline allows practical implementation.

ACKNOWLEDGMENT

This study was supported by the National 863 High-Tech R&D Program under the Grant No. 2007AA01Z228 and the 111 Project under the grant No. 111-2-14.

REFERENCES

1:  Bennett, J.C.R. and H. Zhang, 1996. WF2Q: Worst-case fair weighted fair queuing. Proceeding of the INFOCOM, March 24-28, 1996, San Francisco, CA, pp: 1-9
Direct Link  |  

2:  Bensaou, B., H.K. Tsang and K.T. Chan, 2001. Credit-based fair queuing (CBFQ): A simple service-scheduling algorithm for packet-switching networks. Transact. Network., 9: 591-604.
Direct Link  |  

3:  Chen, J., W. Jiao and H. Wang, 2005. A service flow management strategy for IEEE 802.16 broadband wireless access systems in TDD mode. Proc. ICC, 5: 3422-3426.
Direct Link  |  

4:  Cicconetti, C., L. Lenzini, E. Mingozzi and C. Eklund, 2006. Quality of service support in IEEE 802.16 networks. IEEE Networks, 20: 50-55.
CrossRef  |  Direct Link  |  

5:  Cicconetti, C., A. Erta, L. Lenzini and E. Mingozzi, 2007. Performance evaluation of the IEEE 802.16 MAC for QoS Support. IEEE Transact. Mobile Comput., 6: 26-38.
Direct Link  |  

6:  Demers, A., S. Keshav and S. Shenkar, 1989. Analysis and simulation of a fair queuing algorithm. Proceedings of the Symposium on Communications Architectures and Protocols, September 25-27, 1989, ACM New York, USA., pp: 1-12
CrossRef  |  Direct Link  |  

7:  Fattah, H. and C. Leung, 2002. An efficient scheduling algorithm for packet cellular networks. VTC-Fall, 4: 2419-2423.
Direct Link  |  

8:  Golestani, S.J., 1994. A self-clocked fair queuing scheme for broadband applications. Proceedings of the 13th INFOCOM’94, Networking for Global Communications, June 12-16, 1994, Toronto, Ont., Canada, pp: 636-646
CrossRef  |  Direct Link  |  

9:  IEEE, 2006. IEEE standard for local and metropolitan area networks-part16: Air interface for fixed and mobile broadband wireless access systems. Proceedings of the IEEE Std. 802.16e-2005 and IEEE Std. 802.16-2004, February 2006, IEEE Xplore, London, pp: 1-822
CrossRef  |  Direct Link  |  

10:  Jain, R., D. Chiu and W. Hawe, 1984. A quantitative measure of fairness and discrimination for resource allocation in shared computer systems. DEC Technical Report TR-301, September 1984. http://www.cse.wustl.edu/~jain/papers/fairness.htm.

11:  Lera, A., A. Molinaro and S. Pizzi, 2007. Channel-aware scheduling for QoS and fairness provisioning in IEEE802.16/ WiMAX broadband wireless access systems. IEEE Networks, 21: 34-41.
Direct Link  |  

12:  Liu. Q., S. Zhou and G.B. Giannakis, 2005. Queuing with adaptive modulation and coding over wireless links: Cross-layer analysis and design. IEEE Trans. Wireless Commun., 4: 1142-1153.
Direct Link  |  

13:  Liu, Q., X. Wang and G.B. Giannakis, 2006. A cross-layer Scheduling algorithm with QoS support in wireless networks. IEEE Trans. Vehicular Technol., 55: 839-847.
Direct Link  |  

14:  Liu, Y., S. Gruhl and E.W. Knightly, 2003. WCFQ: An opportunistic wireless scheduler with statistical fairness bounds. IEEE Trans. Wireless Commun., 2: 1017-1028.
Direct Link  |  

15:  Parekh, A.K. and R.G. Gallager, 1993. A generalized processor sharing approach to flow control in integrated service network: The single node case. IEEE Trans. Network., 1: 344-357.
Direct Link  |  

16:  Proakis, G.J., 2000. Digital Communications. 4th Edn., MacGraw-Hill, New York, ISBN: 0072321113

17:  Shreedhar, M. and G. Varghese, 1996. Efficient fair queuing using deficit round robin. IEEE Trans. Network., 4: 375-385.
Direct Link  |  

18:  Wongthavarawat, K. and A. Ganz, 2003. Packet scheduling for quality support in IEEE 802.16 broadband wireless access systems. Int. J. Commun. Syst., 16: 81-96.
CrossRef  |  Direct Link  |  

19:  Zhang, Q. and A.S. Kassam, 1999. Finite-state Markov model for Rayleigh fading channels. IEEE Transact. Commun., 47: 1688-1692.
Direct Link  |  

©  2021 Science Alert. All Rights Reserved