Zhang Hanyi,Su Xin

(Wireless and Mobile Communication Technology R&D Center of Tsinghua University， Tsinghua National Laboratory for Information Science and Technology， Beijing 100084， China)

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.

C urrently,IEEE 802.I6 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 WiMAXand 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 QoSunder 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 WiMAXand 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 SScorresponds 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 Tiis 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,BScan get the Channel Status Information(CSI)of each SSon every subcarrier in a real-time way from the SS's feedback.

The working principle of the system modelis 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'QoSand CSI,and schedules the SS'data packets in a way that enables one subcarrier to be assigned to one SSin 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 modelis illustrated in Figure I.

As shown in Figure I,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 wellas 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［I］.Assuming at time t,the effective Signal-to-Noise Ratio(SNR)of SS i on subcarrier m isγi［m,t］,and the PERrequirement 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(I)is modified as:

▲Figure 1. System model block diagram.

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 PFalgorithm 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,PFalgorithm 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 SSfor 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,mindicates the assignment status of subcarrier.When the data of SS i are sent on subcarrier m,ρi,m=I;otherwise,ρi,m=0.tcis the delay threshold of SS i.

The stricter requirement imposed on delay,the smaller tcis.

Taking into account both users'actual transmission rates and fairness,PFalgorithm 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 QoSand 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(I0).

Compared with PFalgorithm,M-LWDFalgorithm can better meet the scheduling requirements of real-time services as it includes the parameters closely related to real-time services,including QoSand delay.

3 Enhanced Algorithms

PFalgorithm 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 QoSand the maximum delay of data packet,M-LWDFalgorithm 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-LWDFalgorithm,and introduce a new one,i.e.size of waiting data of SS i (Bi,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-LWDFalgorithm,,and the queue load information,

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βIis 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-LWDFalgorithm.That is to say,the larger Wi,M-LWDF,the higher the user's scheduling priority is.That is,

whereβ2is 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(I4)and(I 5):

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-LWDFalgorithm,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=I;otherwiseρi,m=0.Bi,m,allocationis the actual data size of SS i that are transmitted on subcarrier m.

The flow of packet scheduling with EM-LWDFalgorithm at BSside is illustrated in Figure 2.

4 System Simulation

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

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-LWDFalgorithm with real-time update performs almost the same as M-LWDFalgorithm in terms of system throughput and packet loss ratio,and they excel EM-LWDFalgorithm with non-real-time update and have a clear advantage over PFalgorithm.

Figure 5 compares average delays of the four algorithms.As to delay performance,simulation results show that when the users reach a certain number,PFalgorithm performs the best,while EM-LWDFperforms 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:

Figure 2.?BS packet scheduling with EM-LWDF aAlgorithm.

where Bi(△)and Bj(△)are services actually obtained by SS i and SS j within the time period△.Biand Bjare services pre-assigned to SS i and SS j respectively.The more SFIapproaches 0,the better the user fairness of an algorithm is.According to Figure 6,the user fairness in EM-LWDFis better than that in PFand M-LWDFalgorithms.

▼Table 1. System simulation parameters

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 PFand M-LWDFalgorithms,EM-LWDFintroduces 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.

▲Figure 4. Comparison of packet loss ratios of four algorithms.

▲Figure 5. Comparison of average delays of four algorithms.

▲Figure 6. Comparison of SFIs of four algorithms.