Packet Scheduling Algorithm for Real-Time Services in Broadband WMAN

This work was funded by the National High Technology Research and Development Program (“863” Program) of China under Grant No. 2007AA01Z289.

    Currently, IEEE 802.16 standard is the generally-recognized air interface specification for broadband Wireless Metropolitan Area Network (WMAN) in the world. Based on this standard, Worldwide Interoperability for Microwave Access (WiMAX) system was developed and has been put into commercial use in some countries. In China, Tsinghua University has proposed its proprietary broadband WMAN system called BRadio and applied it in the construction of Tianjin broadband WMAN. Both WiMAX and BRadio systems can accommodate a great number of users, provide carrier-class Quality of Service (QoS) and support diversified multimedia services, including voice, video and packet data services.

    To ensure QoS under the conditions of high-bandwidth transmission and a great number of users, a broadband WMAN requires not only a proper connection-oriented transmission mechanism, but also a reasonable packet scheduling algorithm.

1 System Model of Broadband WMAN
Both WiMAX and BRadio systems support Point-to-MultiPoint (PMP) topology, and their physical layers can adopt WirelessMAN Orthogonal Frequency Division Multiplexing Access (OFDMA) scheme with Time-Division Duplex (TDD). The study in this paper is based on such a model. In order to study downlink scheduling of a cell, we assume one Base Station (BS) provides services for N Subscriber Stations (SSs) and each SS corresponds to one service stream. Within the BS, N queue buffers are set up (for the purpose of study, we assume the queues are indefinitely long) for storing the data of N SSs which are to be sent respectively. The data packets are scheduled into the queues on the principle of First-In First-Off (FIFO). For each data packet of SS i , a delay threshold Ti is set. If the waiting time of a data packet in the queue exceeds this threshold, the packet will be dropped.

    Meanwhile, the system’s bandwidth is divided into M subcarriers. Supposing the channels of all SSs are independent, BS can get the Channel Status Information (CSI) of each SS on every subcarrier in a real-time way from the SS’s feedback.

    The working principle of the system model is as follows: Before a frame is sent, the packet scheduling algorithm decides how timeslots of the frame and subcarriers are assigned based on queue condition, the SS’ QoS and CSI, and schedules the SS’ data packets in a way that enables one subcarrier to be assigned to one SS in one timeslot. The scheduled data packets are then modulated and coded by the Adaptive Modulation and Coding (AMC) module into subcarrier signals. These signals, upon processed with Inverse Fast Fourier Transform (IFFT) and added with cyclic prefixes, are finally sent to the SS. The system model is illustrated in Figure 1.

    As shown in Figure 1, the scheduling algorithm should work with AMC to effectively use physical resources and improve the system’s spectral efficiency. In this way, it can meet the Packet Error Rate (PER) requirement as well as adaptively adjust the modulation and coding scheme based on the channel status, thus maximizing transmission rate. For the system model discussed in this paper, AMC mechanism can be approximated with the method proposed in Reference [1]. Assuming at time t , the effective Signal-to-Noise Ratio (SNR) of SS i on subcarrier m  is γi[m,t ], and the PER requirement for SS i  is Γi, the bits that can be carried in a single Orthogonal Frequency Division Multiplexing (OFDM) character of SS i  on subcarrier m is

    where

For the system adopting adaptive
M-ary Quadrature Amplitude Modulation (QAM), Expression (1) is modified as:

2 PF and M-LWDF Algorithms
Proportional Fairness (PF) algorithm[2] is widely used in wireless mobile networks. It was first proposed in Code Division Multiple Access High Data Rate (CDMA-HDR) systems, and then applied in many other systems. It can better balance the system’s maximum throughput and the fairness among the SSs.

    Theoretically, the PF algorithm satisfies Formula (4):

    where Ri (P ) is the average transmission rate of SS i  in case of PF algorithm, and Ri (S ) is the average transmission rate of SS i  in any other algorithm S . The system has totally N SSs[3].

    In actual single-carrier systems, PF algorithm is often expressed as follows:

    where ri (t ) is the maximum transmission rate of SS i  in current slot, and Ri (t )  is the average transmission rate of SS i  up to the moment. At each packet scheduling, the system assigns available timeslots to the SS i * whose r (t )/R (t ) is the largest for transmission.
In multi-carrier systems, PF algorithm is also applied[3-5]. A simplified PF algorithm for multi-carrier system works like this: At any scheduling, the algorithm finds out the right SS for a subcarrier and assigns the subcarrier to the SS. That is,

    where ri,m (t ) is the maximum transmission rate of SS i on subcarrier m .

    Upon each packet scheduling, the average transmission rate Ri (t )  of SS i is updated using the following formula:   

    where

    ρi ,m  indicates the assignment status of subcarrier. When the data of SS i  are sent on subcarrier m , ρi ,m =1; otherwise, ρi ,m =0. tc  is the delay threshold of SS i. The stricter requirement imposed on delay, the smaller tc  is.

    Taking into account both users’ actual transmission rates and fairness, PF algorithm meets scheduling requirements of non-real-time services. But it is not ideal for delay-sensitive real-time services because it does not consider the delay of data packet. To solve this problem, some researchers proposed Modified Largest Weighted Delay First (M-LWDF) algorithm[6] and further, others suggested EXP/PF algorithm[7].
Compared with PF, M-LWDF algorithm introduces two new parameters: User’s QoS and data packet delay. For a single-carrier system, channel resources are assigned to the users satisfying Expression (9):

    For a multi-carrier system, M-LWDF algorithm is adopted for each subcarrier assignment[8], and the assignment formula is (10).

    where  is the maximum delay of the data packet of SS i  in the transmission queue, αi is QoS parameter of SS i, which is defined as:

    Ti  is the allowed maximum delay of SS i, and δi is the maximum probability of the event ＞Ti , which can be expressed as:

    Compared with PF algorithm, M-LWDF algorithm can better meet the scheduling requirements of real-time services as it includes the parameters closely related to real-time services, including QoS and delay.

3 Enhanced Algorithms
PF algorithm is simple, and guarantees the fairness among users very well. But it only considers channel status and user rate, so its overall performance is greatly affected. By introducing two parameters, i.e. the user’s QoS and the maximum delay of data packet, M-LWDF algorithm is more applicable to real-time services and enhances the system’s overall performance. However, this algorithm lacks enough information for evaluating user queue. In particular, it does not consider the size of user data to be transmitted. Besides, due to limitations of the parameters themselves, even if all parameters are updated in a real time way after each packet scheduling, some users may occupy a channel for a long time, thus the fairness among users is impaired.

    To address the above issues, we suggest an enhanced M-LWDF algorithm, i.e. EM-LWDF. This algorithm keeps the critical parameters of M-LWDF algorithm, and introduce a new one, i.e. size of waiting data of SS i (B i,wait(t )), in order to evaluate the load of user queue more accurately.

    In the enhanced algorithm, the weighting information Wi (t ) for packet scheduling is a function of the weighting information of M-LWDF algorithm,, and the queue load information, Wi,Load= Bi,wait(t ). The expression is as follows: 

    Under the condition that the users’ other parameters are the same values, the user with the heaviest queue load will be scheduled first to avoid long delay and lots of packets being lost, so

    where β 1 is a constant independent of Wi,Load .

    If the queue loads of all users are the same, the algorithm adopts a scheduling policy similar to M-LWDF algorithm. That is to say, the larger Wi,M-LWDF, the higher the user’s scheduling priority is. That is,

    where β 2 is a constant independent of Wi,M-LWDF.

    As the constant has no impact on the weighting, the packet scheduling weighting function of the enhanced algorithm can be obtained from Formulae (14) and (15):

    That is to say, subcarrier m is assigned to the user that satisfies the following condition:

    In the above formula, Ri (t ) and Bi,wait(t ) are statistics of users and queues, and they should be updated timely. Traditionally, they are updated after each packet scheduling, as in Formulae (7) and (8). In this update method, update is done after all subcarriers have been assigned, so we call it non-real-time update. On the contrary, in EM-LWDF algorithm,
real-time update policy is adopted. That is to say, the update is done after every subcarrier is assigned. Compared with non-real-time update, the real-time update approach is much timely, and reflects the degree where the user is served and the real conditions of queues. Moreover, it is much more flexible in packet scheduling.

    In the real-time update approach, Ri(t ) and Bi,wait(t ) are updated as follows:

• When each packet scheduling begins, count current Bi,wait (t ), and let

• Upon assignment of a subcarrier, update Ri (t ) and Bi,wait (t ) with the following formulae:

    where ri,m (t ) is the maximum transmission rate of current SS i  on subcarrier m . When SS i’s data are sent via subcarrier m, ρi,m =1; otherwise ρi,m =0. Bi,m,allocation is the actual data size of SS i that are transmitted on subcarrier m .

    The flow of packet scheduling with EM-LWDF algorithm at BS side is illustrated in Figure 2.

4 System Simulation
To compare the performance of PF, M-LWDF, EM-LWDF with non-real-time update approach and EM-LWDF with real-time update approach, we conduct system simulations. The simulation parameters are listed in Table 1.

    Figures 3 and 4 compare the system throughputs and packet loss ratios of the four algorithms respectively. From the two figures, it can be seen that EM-LWDF algorithm with real-time update performs almost the same as M-LWDF algorithm in terms of system throughput and packet loss ratio, and they excel EM-LWDF algorithm with non-real-time update and have a clear advantage over PF algorithm.

    Figure 5 compares average delays of the four algorithms. As to delay performance, simulation results show that when the users reach a certain number, PF algorithm performs the best, while EM-LWDF performs better than M-LWDF.

    Figure 6 is the comparison of the four algorithms in user fairness. The criterion for measuring user fairness is Service Fairness Index (SFI)[9], which is defined as:

    where Bi (Δ) and Bj (Δ) are services actually obtained by SS i  and SS j  within the time period Δ. Bi  and Bj  are services pre-assigned to SS i  and SS j respectively. The more SFI approaches 0, the better the user fairness of an algorithm is. According to Figure 6, the user fairness in EM-LWDF is better than that in PF and M-LWDF algorithms.

5 Conclusions
In this paper, we propose the EM-LWDF algorithm, a packet scheduling algorithm that is applicable to real-time services of broadband WMANs. Compared with traditional PF and M-LWDF algorithms, EM-LWDF introduces a new parameter for evaluating the load of user queue and adopts real-time update approach, which help to improve the system’s overall performance and allow the scheduling to be more flexible. Simulation results show that this algorithm performs quite well in terms of system throughput and packet loss ratio, has clear advantage over other algorithms in delay and better guarantees the fairness among users.

References
[1] QIU Xiaoxin, CHAWLA Kapil. On the performance of adaptive modulation in cellular systems [J]. IEEE Transactions on Communications, 1999, 47(6): 884-895.
[2] JALALI A, PADOVANI R, PANKAJ R. Data throughput of CDMA-HDR a high efficiency-high data rate personal communication wireless system [J]. IEEE Vehicular Technology Conference (VTC2000-Spring Tokyo), 2000, 3(5): 1854-1858.
[3] KIM Hoon, HAN Youngnam. A proportional fair scheduling for multicarrier transmission systems [J]. IEEE Communications Letters, 2005, 9(3): 210-212.
[4] SUH Changho, PARK Seunghoon, CHO Youngkwon. Efficient algorithm for proportional fairness scheduling in multicast OFDM systems [J]. IEEE Vehicular Technology Conference(VTC 2005-Spring), 2005, 3(5): 1880-1884.
[5] KANEKO Megumi, POPOVSKI Petar, DAHL Joachim. Proportional fairness in multi-carrier system: upper bound and approximation algorithms [J]. IEEE Communications Letters, 2006 10(6): 462-464.
[6] ANDREWS Matthew, KUMARAN Krishnan, RAMANAN Kavita. Providing quality of service over a shared wireless link [J]. IEEE Communications Magazine, 2001, 39(2): 150-154.
[7] RHEE Jonghun, HOLTZMAN J M., KIM Dongku. Performance analysis of the adaptive EXP/PF channel scheduler in an AMC/TDM system [J]. IEEE Communications Letters, 2004, 8(8): 497-499.
[8] KIM Kanghee, KOO Insoo, SUNG Seokjin, etc. Multiple QoS support using M-LWDF in OFDMA adaptive resource allocation [J]. The 13th IEEE Workshop on Local and Metropolitan Area Networks, 2004, (4): 217-222.
[9] YU Guanding, ZHANG Zhaoyang, QIU Peiliang, etc. Fair resource scheduling algorithm for wireless OFDM systems [J]. Communications, Circuits and Systems, 2005, 1(5): 374-377.

[Abstract] Packet scheduling algorithm is the key technology to guarantee Quality of Service (QoS) and balance the fairness between users in broadband Wireless Metropolitan Area Network (WMAN). Based on the research of Proportional Fairness (PF) algorithm and Modified Largest Weighted Delay First (M-LWDF) algorithm, a new packet scheduling algorithm for real-time services in broadband WMAN, called Enhanced M-LWDF (EM-LWDF), was proposed. The algorithm phases in new information to measure the load of service queues and updates the state parameters in real-time way, which remarkably improves system performance.Simulation results show that comparing with M-LWDF algorithm, the proposed algorithm is advantageous in performances of queuing delay and fairness while guaranteeing system throughput.