Abstract: Wireless networks are characterized by time-varying nature as well as scarce resources. The data rate of wireless radio frequency channel is limited by Shannon’s capacity law. Traditional methods including opportunistic scheduling algorithms segregates packet scheduling and resource allocation is inefficient. Though fairness and throughput are inversely related, a wise compromise between the two will result in acceptable QoS (Quality of Service) levels with comparable throughput. To improve the utilization of limited capacity, packet scheduling as well as resource allocation should be inter linked for maintaining throughput as well as fairness issue. This type of interaction between physical and medium access layer refers to cross-layer resource scheduling. The study presents a scheduler for packet scheduling and resource allocation taking queue and channel states in to account. In first level of scheduling, users to be given chance are selected based on certain conditions which include backlogged queues, fairness and delay in users. The second level of scheduling includes resource allocation for selected users using OFDM (Orthogonal Frequency Division Multiplexing) technique. Token Bank Fair Queuing (TBFQ) is based on leaky-bucket mechanism with each flow keeps track of number of tokens borrowed from or given to the token bank using a counter. Tokens overflowing the pool are stored in the bank. Priority of a connection in borrowing tokens is based on the counter value and token generation rate. As the flow is serviced, the value of counter varies which changes the priority level for further processing so that starving flows are also given service in this algorithm. The flow which has highest priority is called for amount of budget needed and based on the budget, sub carrier is allocated using OFDM. The channel conditions are measured using SNR (Signal to Noise Ratio) and given as feedback so that modulation scheme is varied as per the channel conditions for effective performance. This Adaptive TBFQ (ATBFQ) scheduling scheme can improve the wide spreading of Wi-max technology for future enhancements.

INTRODUCTION

The tremendous growth in 1G and 2G wireless networks paved way for development of next generation networks. To meet the growing demands in the number of subscribers, rates required for high speed data transfer and multimedia applications 3G standards started evolving. Now, the approaching 4G wireless communication services aims to develop an innovative concept in radio access in order to achieve high flexibility and scalability with respect to data rates and radio environments. In rural areas, Broad-band Wireless Access (BWA) (Gidlund and Wang, 2009) represents an economically viable solution to provide last mile access to the internet. Standard activities for BWA are being developed within IEEE project 802, Working group 16, often referred to as 802.16 (Liang et al., 2009). Scheduling algorithms at the Medium Access Control (MAC) layer relies on a variety of parameters including QoS (Quality of Service) requirements, resource allocation mechanisms and link qualities from the corresponding layers. Traditional scheduling algorithms rely on backlogged queue conditions. However, this assumption is not always correct due to varying number of packets in the buffer. In a Weighted Fair Queuing (WFQ) scheduling scheme proposed, the largest share of the radio resource is given to the users with the best instantaneous channel conditions. There are chances of starvation that may happen to some users based on the weight assigned to the flow. So it is necessary to find a novel scheduling scheme considering both channel and queue states in to account. The merging of packet scheduling and resource allocation refers to cross-layer scheduling scheme, which emphasis on fairness among users with acceptable throughput. In the first level of scheduling, users to be served are selected based on Token Bank Fair Queuing (TBFQ) algorithm (Bokhari, 2007; Bokhari et al., 2009). Based on network loading and user channel conditions, the second level of scheduling assigns resources to selected users in an adaptive manner using OFDM (Orthogonal Frequency Division Mutiplexing). The performance of ATBFQ (Adaptive Token Bank Fair Queuing) is compared with Round Robin (RR) and Weighted Fair Queuing (WFQ) scheduling algorithms.

MATERIALS AND METHODS

TBFQ algorithm: The TBFQ algorithm (Wong et al., 2004) was initially developed for wireless packet scheduling in the downlink of TDMA systems and was later modified for wireless multimedia services using uplink as well. Its concept was based on the leaky-bucket mechanism which policies flows and conforms them to a certain traffic profile. A traffic flow belonging to user I shown in Fig. 1 is characterized by the following parameters:

Each L-byte packet consumes L tokens. For each flow i, E_i is a counter that keeps track of the number of tokens borrowed from or given to the token bank. As tokens are generated at rate r_i the token overflowing from the token pool are added to the token bank and E_i is incremented by the same amount. When the token pool is depleted and there are still packets to be served, tokens are withdrawn from the back by flow i and E_i is decreased by the same amount. Thus, during periods when the incoming traffic rate of flow i is less than its token generation rate, the token pool always has enough tokens to serve arriving packets and E_i increases and becomes positive and increasing.

Fig. 1:	Traffic flow considered

On the other hand, during periods when the incoming traffic rate of flow i is greater than its token generation rate, the token pool is emptied at a faster rate than it can be refilled with tokens. In this case, the connection may borrow tokens from the back. The priority of a connection in borrowing tokens from the bank is determined by the priority index (p_i) given by:

(1)

By prioritizing in this manner, it is ensured that flows belonging to UTs that are suffering from severe interference and shadowing conditions in particular will have a higher priority index, since they will contribute to the bank more often.

ATBFQ algorithm: The TBFQ algorithm (Bokhari, 2007) originally proposed for single carrier TDMA system and it is improved by introducing adaptive parameter selection and can be extended to suit OFDM systems. The motivation behind this modification is to incorporate the design and performance requirements of the scheduler in 4G networks in to the original scheme. In such networks, the utilization of resources and hence the performance of the network can be enhanced by making use of the multiuser diversity provided by the multiple access scheme being used. In order to make use of the channel feedback, faster scheduling is required. Another requirement is the ability to maintain fairness and provide a minimum acceptable QoS performance to all users.

The system model considered for design is shown in Fig. 2. The basic time frequency resource unit in OFDM is denoted as a chunk.

Fig. 2:	System model

It consists of a rectangular time frequency area that comprises a number of subsequent OFDM symbols and a number of adjacent subcarriers. Packets from the traffic flows are exclusively mapped on to these chunks based on QoS requirements obtained from the higher Radio Link Control (RLC) layer along with the channel feedback received from the physical layer. The channel feedback comprises Signal to Noise Ratio (SNR) which is measured in frame j at the UT’s (User Terminal). This feedback is then provided to the frame j + 1 and can be utilized for scheduling purposes at the MAC layer. ATBFQ is same as TBFQ in operation. A debt limit d_i is set as a threshold to limit the amount a UT can borrow from the bank. It also acts as a measure of prevent malicious UTs from borrowing extensively. The packets are queued in subqueues in a Per-Flow Queuing (PFQ) based on the service classes. The following steps are executed for implementing the ATBFQ algorithm.

Step 1: At the scheduler, information is retrieved from the higher layer about all active users. An active user is defined as a backlogged queue which has packets waiting to be served.

Step 2: Based on the list of active users, a priority is calculated using Eq. 1. This step returns the user with the highest priority.

Step 3: A certain budget is calculated for the priority user. This depends on the value of the excess counter and the debt limit given by E_i-d_i. E_i keeps track of how much the user has borrowed or given to the bank. The d_i keeps track of how much a user can further borrow from the bank in order to accommodate the burstiness of the traffic over the long term.

Step 4: If the calculated budget is less than the bank size, resources are allocated to the user i. This is the second level of scheduling and deals with allocation of chunk resources to the selected user i. This allocation is based on the maximum SNR principle. This is the most opportunistic of all scheduling algorithms for time-slotted networks. This means that the Adaptive Modulation and Coding (AMC) policy maximally exploits the frequency diversity of the time frequency resource (Liu et al., 2006), where a chunk is allocated to only one user and a user have multiple chunks in a scheduling instant.

Step 5: The resource mapping is done by using OFDM (Orthogonal Frequency Division Multiplexing). The block diagram representation of OFDM implementation (Huang and Niu, 2007) is shown in Fig. 3.

Fig. 3:	OFDM implementation

Step 6: This step updates the token bank, excess counter and the allocated budget. The selected user gets to transmit as long as its queue remains backlogged and the allocated budget is less than total bank size. If either of the conditions is not satisfied, the user is classified as non-active. A new priority is calculated for new updated active users and steps 1-6 are repeated. This procedure is repeated until there are no chunk resources available or there are no active users.

The parameters for ATBFQ algorithm are initialized with 53 bytes of token pool, -530 bytes as debt limit and the token generation rate varies for different type of inputs, which includes rt-ps (real time polling service), nrt-ps (non real time polling service) and best effort service. The token generation rate is taken as three times the packet arrival rate.

RESULTS AND DISCUSSION

In round robin scheduling all the users have equal chances of getting the service. Also delay sensitive applications suffer from severe starvation with lack of service e.g., video conferencing. In weighted fair queuing, the chances of getting service are based on the weight assigned to the user. Obviously more weights are assigned to the delay sensitive applications e.g., rt-ps service. Hence starvation is unavoidable for non-delay sensitive applications.

In the ATBFQ algorithm, as the packets are serviced the priorities assigned for the flow decreases subsequently. So, fairness will be maintained among all types of users even though the throughput of delay sensitive applications is somewhat reduced. This also helps in preventing denial of service to obedient users with negotiated traffic profile than that of greedy users. The comparison between the designed ATBFQ algorithm with WFQ and RR algorithms is shown in Table 1. For simplicity only three users performances in terms of fairness provision are shown in the Table 1.

Table 1:	Fairness provision using ATBFQ

Table 2:	Obtained performance measures

The delay and spectral efficiency is measured for various types of services classes and compared with the IEEE 802.16 Standard values shown in Table 2 (Hossain and Bhargava, 2004). From Table 2, it is understand that the ATBFQ algorithm achieves better performance in terms of both spectral efficiency (4 b/s/Hz compared to 3.75 b/s/Hz) and end-to-end delay of (40-50 ms) for non real time and best effort users and in terms end-to-end delay (42 ms) for real time users.

CONCLUSION

In this study, the performance of the ATBFQ scheduling algorithm with adaptive parameter selection is presented. It is a queue and channel-aware scheduling algorithm which attempts to maintain fairness among all users. The results are compared with that of round robin and weighted fair queuing scheduling schemes. ATBFQ is a credit-based scheme which aims to accommodate the burstiness of users by assigning them more resources in the short term provided that long term fairness is maintained. The observed delay and spectral efficiency indicate the superiority of the ATBFQ algorithm.