一种适用于宽带无线城域网实时业务的分组调度算法

基金项目：国家高技术研究发展计划(“863”计划)资助项目(2007AA01Z289)

    随着现代信息技术的飞速发展，电信网、计算机网和广播电视网趋向于相互渗透和相互融合，正逐步形成“三网合一”的局面。为解决“三网合一”过程中所引入的接入网问题，宽带无线城域网应运而生，并成为宽带无线移动领域的研究热点。

    IEEE802.16标准是目前国际上流行的宽带无线城域网的空中接口规范，以此为基础的WiMAX系统已在一些国家得到了商用。在中国，清华大学提出了具有完全自主知识产权的清华宽带无线城域网系统——BRadio，并将其应用于天津宽带无线城域网的建设中。WiMAX和BRadio两种系统均支持大容量用户，可提供电信级的服务质量(QoS)保证，并全面支持语音、视频、数据等多媒体业务的应用。

    在高带宽传输与高容量用户的背景下，为了保证业务的服务质量，宽带无线城域网不仅需要提供完善的面向连接的传送机制，还需要采用合理的分组调度算法。

1 宽带无线城域网系统模型
    WiMAX和BRadio系统均支持点到多点(PMP)的拓扑结构，物理层可采用时分双工(TDD)的无线城域网正交频分多址(WirelessMAN-OFDMA)方式，因此本文的研究也基于这样的模型。考虑单小区的下行链路调度情况，假设小区中的基站(BS)为N个用户站(SS)提供服务，每个SS对应一个服务流。BS内开辟了N 个队列缓存(为了研究方便，假设队列长度无限长)，分别存放N 个SS的待发送数据。数据包以先进先出(FIFO)方式进入队列，对于用户i，每个数据包都有一个时延期限Ti。如果数据包在队列中的等待时延超过了时延期限，那么这个数据包将会被丢弃。

    系统带宽被划分为M 个子载波。假定各个用户的信道相互独立，BS可通过SS的反馈实时获得每个用户在每个子载波上的信道状态信息(CSI)。在每帧发送之前，分组调度算法根据队列信息、用户QoS信息以及信道状态信息等确定这一帧内各个时隙以及各个子载波的分配情况，对用户的数据包进行调度，每个子载波在一个时隙内只分给一个用户。被调度的数据包通过自适应编码调制模块进行调制和编码，所得到的各个子载波的信号再经过快速傅里叶逆变换(IFFT)处理，添加循环前缀，最后发送至SS端。系统模型如图1所示。

    在图1中，为了有效地利用物理资源，提高系统频谱效率，调度算法需要和自适应编码调制(AMC)相结合，从而在满足一定误包率要求的同时，根据信道状况的变化自适应地调整编码和调制方式，以实现传输速率的最大化。对于本文的系统模型而言，AMC机制可采用文献[1]中所提到的方法来近似。假设第t 个时刻，用户i 在子载波m上的有效信噪比(SNR)为γi[m,t ]，用户i 的误码率要求为Γi，则用户i 在子载波m上的单位正交频分复用(OFDM)符号内所能承载的比特数为：

ci  [m ,t ]=log 2 (1+β·γi  [m ,t ])      (1)

    其中

    对于采用自适应多阶正交振幅调制(MQAM)的系统，ci  [m ,t ]表达式被修正为：

2 PF算法和M-LWDF算法
    比例公平调度算法(PF)[2]是一种在无线移动网络中广为使用的调度算法，最早在码分多址高速数据率(CDMA-HDR)系统中被提出，继而被许多其它系统采用，它可以为系统最大吞吐量和用户间的公平性提供很好的平衡。

    理论上比例公平算法满足公式(4)：

    其中Ri (P )指比例公平调度算法下用户i的平均传输速率，Ri (S )指任意调度算法S 下用户i 的平均传输率，系统中共有N 个用户[3]。

    在实际单载波系统中，比例公平调度算法一般采用下面的表达式：

    其中，ri (t )表示用户i在当前时隙的最大传输速率，Ri (t ) 表示用户i 截至当前时刻的实际平均传输速率。在每个分组调度时刻，系统选择两者比值最大的用户i *，分配当前可用时隙，令其传输。

    在多载波系统中，PF算法同样得以应用[3-5]，其中一种简化的多载波PF算法为在任一调度时刻，在每个子载波上找到该子载波最适合分配的用户，并分配该子载波给此用户。即

式中ri,m (t )表示当前用户i 在子载波m上的最大传输速率。

    每次分组调度结束后，用户实际平均传输速率Ri (t ) 根据下式更新：

    其中

    ρi ,m 反映了子载波的分配情况，当子载波m上发送用户i 的数据时，ρi ,m =1，否则ρi ,m =0。tc 反映了用户i的时延约束，对时延要求越严格，则tc越小。

    PF算法兼顾了用户实际传输速率和公平性，能够很好地满足非实时业务的要求。但是由于这种算法并没有考虑数据包的时延，因此对于时延敏感的实时业务效果并不理想。针对此问题，有研究者提出了修正的最大加权时延优先(M-LWDF)调度算法[6]，并在此基础上进一步提出了指数比例公平(EXP/PF)算法[7]。
M-LWDF算法的基本思想是引入了用户的QoS参数和数据包时延。对于单载波系统，选择满足式(9)的用户分配信道资源：

    对于多载波系统，在每个子载波上独立采用M-LWDF算法来进行子载波分配[8]，如公式(10)：

    其中为用户i 待传输队列中数据包的最大等待时延；αi为用户i的QoS参数，其定义为：

Ti 为用户i 的最大允许时延，δi 表示＞Ti 事件发生的最大概率，即

    相比于PF算法，M-LWDF算法由于充分考虑了与实时业务密切相关的用户QoS、时延等参数，因而可以更好地满足实时业务的调度要求。

3 改进算法
    PF算法机制简单，用户之间的公平性能够得到很好的保障，但是由于仅仅考虑了信道条件和用户速率的要求，因此整体性能受到了很大的影响。M-LWDF算法引入了用户的QoS参数以及数据包的最大等待时延两项参数，对实时业务更加适用，提高了系统的整体性能。

    针对上述状况，本文提出一种改进的M-LWDF算法——EM-LWDF。该算法保留了M-LWDF算法中的关键参数，同时引入一个新的参量——用户i 的待传输数据量B i,wait(t )，以便更好地衡量用户队列的负载情况。

    对于改进算法，决定分组调度的权重信息Wi(t)应是M-LWDF算法原有权重信息 与新引入的队列负载信息Wi,Load= Bi,wait(t )的函数，即

    当用户的其他参数指标相同时，负载大的用户应优先得到调度，以避免可能产生的高时延以及因等待时间过长造成大量丢包的情况。即有：

    式中β1为一个与Wi ,Load无关的常数。

    当队列负载相同的情况下，采用与M-LWDF算法相似的调度策略，Wi,M-LWDF权重越高的用户调度优先级越高，即：

    式中β2为一个与Wi,M-LWDF无关的常数。
联合公式(14)和公式(15)，考虑到常数对于权重没有影响，可以得到改进算法的分组调度权重函数为：

即将子载波m分配给满足下列条件的用户i *：

    在上述公式中，Ri(t )和Bi,wait(t )是关于用户和队列的统计量，需要进行及时的更新。传统的更新方法是在每次分组调度结束后进行的，如公式(7)、(8)所示，此时所有子载波资源已完成分配，不妨称这种更新方法为非实时更新。作为改进，在EM-LWDF算法中采用实时更新的策略，即更新是在每个子载波资源完成分配后进行的。与非实时更新相比，实时更新的方法时效性更强，能够更好地反映用户被服务程度以及队列信息的真实状态，并且在分组调度时具有更强的灵活性。

• 采用实时更新的Ri(t )和Bi,wait(t )的更新方法如下：
• 在每次分组调度开始时，统计当前Bi,wait(t )，并令:

• 每完成一个子载波分配后，按如下公式更新：

    其中ri,m(t )表示当前用户i 在子载波m上的最大传输速率。当子载波m上发送用户i 的数据时，ρi,m =1，否则ρi,m =0。Bi,m,allocation为用户i 在子载波m上实际传输的数据量。

    BS侧采用EM-LWDF算法进行分组调度的流程图如图2所示。

4 系统仿真
    对PF算法、M-LWDF算法、采用非实时更新的EM-LWDF算法以及采用实时更新的EM-LWDF算法进行系统仿真比较。仿真参数如表1所示。

    图3和图4分别给出了4种算法的系统吞吐量和丢包率的比较。可以看出，采用实时更新的EM-LWDF算法在系统吞吐量和丢包率方面与M-LWDF算法基本相当，二者的性能优于采用非实时更新的EM-LWDF算法，并且和PF算法相比优势明显。

    图5给出了4种算法的平均时延比较。从图5中可以看出，在用户数量达到一定程度后PF算法的时延性能最好，而EM-LWDF算法的时延性能优于M-LWDF算法。

    图6给出了4种算法的用户公平性比较，所采用的衡量指标为服务公平指数(SFI)[9]。其定义为：

其中Bi (Δ)和Bj (Δ)分别表示用户i 和用户j 在Δ时间段内实际得到的服务量，Bi 和Bj 分别表示预先分配给用户i 和用户j 的服务量。SFI指数越接近于0，表示算法的公平性越好。

    由图6我们可以看到，EM-LWDF算法的公平性优于PF算法和M-LWDF算法。

5 结束语
    本文提出了一种适用于宽带无线城域网实时业务的分组调度算法——EM-LWDF算法。与传统的PF算法和M-LWDF算法相比，本算法引入了新的衡量服务队列负载的信息，并采用了实时更新状态参数的方法，有利于提高系统的整体性能，并且具有更强的调度灵活性。仿真结果表明，本算法在系统吞吐量、丢包率方面具有优良的性能，在时延性能方面优势明显，同时更好地保证了用户之间的公平性。

6 参考文献
[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.

收稿日期：2009-03-26

[摘要] 对宽带无线城域网(WMAN)而言，分组调度算法是保证用户服务质量(QoS)、平衡用户间公平性的关键。在研究比例公平调度算法(PF)算法与修正的最大加权时延优先算法(M-LWDF)的基础上，一种新的适用于宽带无线城域网实时业务的分组调度算法被提出，此算法引入了新的衡量服务队列负载的信息，能够实时地更新状态参数，提高了系统性能。仿真结果表明，此算法在保证系统吞吐量的同时，比M-LWDF算法具有更好的时延特性和公平性。

[关键词] 宽带无线城域网；分组调度；实时业务

[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 was proposed. The algorithm phases in new information to measure the load of service queues and updates the state parameters on time, which remarkably improves system performance. Simulation results show that comparing with M-LWDF algorithm, the proposed algorithm obtains advantages in performances of queuing delay and fairness while guaranteeing system throughput.

[Keywords] broadband WMAN; packet scheduling; real-time service