面向实时业务的快速公平性分组调度算法

吴大鹏，严海升，罗仁泽，林艳芳，徐 蕾

(1.重庆邮电大学宽带泛在接入技术研究所，重庆 400065;2.中国移动通信集团设计院有限公司重庆分公司，重庆 400042;3.无锡源清高新技术研究所有限公司传感网研究中心，江苏 无锡 214000)

0 引言

长期演进系统(long term evolution，LTE)是3G技术的长期演进，它改进并增强了3G的空中接入技术，采用了正交频分复用技术(orthogonal frequency division multiplexing，OFDM)和多入多出技术(multiple input multiple output，MIMO)作为其无线网络演进的唯一标准。其主要技术指标是在20 MHz频谱效率下能够提供下行100 Mbit/s与上行50 Mbit/s的峰值速率［1］。由于LTE在频谱利用率、网络性能、扁平的网络结构方面都有比较明显的技术优势，因此，LTE被全球多个运营商认可为下一代无线通信的主流技术。

LTE系统的无线资源管理功能主要由分组调度算法来实现，且分组调度算法能够有效地提高系统传输速率，保障业务的服务质量。

根据业务特性的不同，LTE系统支持非实时和实时两类业务，非实时业务可以容忍一定的时延，如背景类业务和交互类业务，而实时业务对时延的要求较高，如语音业务和流媒体业务。针对非实时业务，美国高通公司提出的正比公平(proportional fair，PF)算法［2］，这种算法同时兼顾了系统吞吐量和用户公平性，但该算法没有考虑到分组队列的时延以及数据服务质量的要求，不能很好的支持实时业务［3］。为了支持实时业务，朗讯贝尔实验室提出了最大权值时延优先(modified large weighted delay first，M-LWDF)算法［4］，并从理论上证明了该算法在吞吐量具有较好的性能［3］。但M-LWDF算法的吞吐量性能的提升是以牺牲用户之间的公平性为代价的，信道条件较差用户的数据包在基站队列中等待，而一旦超过等待时间阈值，这些数据包将被丢掉，可见，其在用户公平性方面存在一定缺陷。为了降低分组被丢弃的概率，提高用户之间的公平性，本文对M-LWDF算法进行了改进，根据用户对公平性的需求，调整了分组数据被调度的优先级，从而在保证用户公平性的情况下实现了实时业务的快速调度。

1 M-LWDF算法的分析与改进

如前所述，M-LWDF算法的主要思想是综合考虑分组队列的时延和信道状态信息。M-LWDF算法中，用户k在第n个发送时间间隔(transmission time interval，TTI)优先级定义如式(1)所示

(1)式中:pk(n)表示用户k调度的优先级，系统始终为优先级最高的用户提供服务;δk表示用户的QoS参数;μk(n)表示用户第n个TTI内最大的数据传输速率，该参数反映信道的瞬时状态，信道条件越好，支持的最大传输速率越大，则用户的优先级也越高;Rk(t)代表第k个用户在时间t内的平均吞吐量，考虑到用户的公平性，对信道条件好的用户限制其优先级;Dk(n)代表用户所在队列时延，分组在队列中等待的时间越长，其优先级也越高，它也是公平性的一个体现;Tk指用户可以容忍的最大时延。当分组所在队列时延超过此值时，分组就会被丢弃［5-7］。

从式(1)可知，用户 k的优先级与 μk(n)和Dk(n)成正比，与Rk(t)和Tk成反比，可见，该算法为一种非公平性的算法。虽然考虑到分组队列时延对调度优先级的影响，但分组在队列中的时延超过Tk，仍没有得到调度，该数据包就会被丢弃。

1.1 线性优先级调度方法

由M-LWDF算法的基本原理可知，当信道条件较差时，数据包被调度的优先级也较低，对应分组用户的时延也越高，当分组队列的时延超过阈值Tk时，该数据包就会被丢弃。为了提升用户之间的公平性，本文提出了一种基于线性优先级的M-LWDF算法。综合考虑将所有用户的平均时延作为参考，当某个用户的时延高于平均时延时，则表明该用户处的信道条件相对较差，进而，其被优先调度的概率也较低。为了有效地提高系统中用户公平性，此种状态下需要设计相应的机制提升该用户的优先级。相反，若某个用户的时延低于平均时延，则表明其信道条件相对较好，因此，该用户得到调度的概率也相对越高，则可以适当地降低调度该用户的优先级。

按照上述原理，本文所提出的用户优先级调整方法如式(2)所示

显然，单纯地补偿信道条件较差用户的优先级，将对系统的吞吐量有较大的影响，降低网络资源利用率。按照本文所提出的基于平均值的优先级调度方法，系统能够在吞吐量和用户公平性上得到有效的折中。

1.2 非线性优先级调度方法

为了进一步降低分组数据包被丢弃的概率，提升用户之间的公平性。本文提出了一种基于非线性优先级的M-LWDF算法，其主要目的是进一步提升高时延用户的优先级，同时降低低时延用户的优先级。根据上述原理，自适应调整因子需要满足以下条件:当m ＜1时，f(m)＜m，且f(m)单调递增;当m ＞1时，f(m)≥m，且也是单调递增;当m=1时，f(m)=m。根据单位圆x2+y2=1内|x|+|y|=1性质，可见，可以采用单位圆来构造上述调整函数，进而确定调整因子。在具体执行过程中，只需将单位圆在坐标轴上平移，并取其中的部分圆弧就可以得到满足上述条件的函数。具体做法如下:当0＜m＜1时，将单位圆向上平移1个单位，取右下四分之一圆弧，当1＜m＜2时，将单位圆向上平移1个单位再向右平移2个单位取左上四分之一圆弧。其表达式如(4)式所示。函数f(m)的图形如图1所示。可见，当0＜m＜1时，为m2+(f(m)－1)2=1的右下半部分;当1＜m＜2时，为(m－2)2+(f(m)－1)2=1的左上半部分。

图1 函数f(m)的图形Fig.1 Graphic of f(m)

2 仿真结果与分析

2.1 仿真场景设置

本部分采用LTE-Sim平台［8］对所提出的机制进行了计算机仿真，并将其与典型的PF算法和MLWDF算法进行了比较。仿真场景为单小区;文中采用的是128 kbit/s的固定比特速率视频流业务，小区内用户以3 km/h的速度移动，轨迹服从随机移动模型［9］。传播损耗模型如下所示。

1)路径损耗

PL=128.1+37.6log(d)，d为基站到用户的距离，单位为km;

2)多径衰落:Jakes model;

3)渗透损失:10 dB;

4)阴影衰落:符合对数分布。

其他参数的设置如表1所示。

表1 LTE下行仿真参数设置Tab.1 LTE downlink simulation parameter settings

2.2 仿真结果

本部分对4种调度算法的性能进行了比较，分别为PF算法、M-LWDF算法、基于线性优先级调度的M-LWDF算法(M-LWDF-LIN)和基于非线性优先级调度的M-LWDF算(M-LWDF-NON)，比较性能主要包括公平性、时延、丢包率和吞吐量4个方面。

不同分组调度算法下的用户公平性如图2所示。从结果可知，与M-LWDF算法相比，基于线性优先级和非线性优先级的M-LWDF算法，用户公平性都得到了一定的改善，在60个用户的情况下，MLWDF-LIN算法用户公平性提升了4%左右，而MLWDF-NON算法用户公平性提升了8%左右。

图2 用户公平性Fig.2 User fairness

用户的平均时延比较如图3所示，从结果中可知，3种算法的平均时延都差不多，其主要原因在于M-LWDF算法中设置了最大的时延阈值Tk，当时延超过阈值Tk，数据包就会被丢弃。

不同调度算法的丢包率如图4所示，从结果中可知，随着小区中用户数量的增加，丢包率也随着增大，基于线性优先级和非线性优先级调度的M-LWDF算法丢包率都得到了一定的改善，在小区中用户数量为60的情况下，M-LWDF-LIN算法丢包率降低了10%左右，而M-LWDF-NON算法的丢包率降低了16%左右。

图3 用户的平均时延Fig.3 Average delay of user

图4 视频业务丢包率Fig.4 Packet loss ratio of video service

不同算法的系统吞吐量如图5所示，从结果中可知，吞吐量随着小区内用户数量增加而不断的增大，同时，也可以看出M-LWDF算法具有较好的吞吐量，两种改进算法的吞吐量均呈现出一定程度的降低。M-LWDF-LIN算法系统吞吐量降低了3%左右，而M-LWDF-NON算法系统吞吐量降低了5%左右。

图5 系统吞吐量Fig.5 Throughout of system

同时从仿真结果可以看出，对于实时业务来说，M-LWDF算法具有较好的表现，无论是在用户公平性、丢包率和系统吞吐量都要优于正比公平性算法，但随着用户数目增多，用户的公平性也随之下降，导致丢包率逐渐增大。M-LWDF-LIN算法在牺牲少量吞吐量的情况下，改善了用户之间公平性和降低了视频业务的丢包率。M-LWDF-NON使用户公平性和丢包率获得了更大的改善，但其牺牲的系统吞吐量也相对较多。

3 总结

针对M-LWDF算法在公平性方面的缺陷，本文提出了相应的改进算法，通过线性优先级调度方法对信道条件差的用户进行补偿和对信道条件较好的用户进行逆补偿，在几乎不牺牲系统吞吐量的情况下，提升了用户之间的公平性，降低了视频业务的丢包率。通过非线性优先级调度的M-LWDF算法虽获得了较好的公平性和丢包率，但也是牺牲系统吞吐量为代价的。同时，也说明了公平性和系统吞吐量是很难兼顾的。

［1］杨勇，石惠，郑秀萍.LTE系统下行链路中无线资源分组调度算法研究［J］.科技情报开发与经济，2009，19(19):136-138.YANG Yong，SHI Hui，ZHENG Xiuping.A Research on Packet Scheduling Algorithms for LTE Downlink System［J］.SCI-Tech Information Development ＆ Economy，2009，19(19):136-138.

［2］JALALI A，PADOVANI R，PANKAJ R.Data Throughput of CDMA-HDR a High Efficiency-High DataRate Personal Communication Wireless System［C］//IEEE.Vehicular Communication Conference.USA:IEEE，2000:1854-1858.

［3］HUDA A M R，RIYAJ B，KUMBESAN S，et al.Performance of Well Known Packet Scheduling Algorithms in the Downlink 3GPP LTE System［C］//IEEE.The 9th Malaysia InternationalConference. Malaysia: IEEE，2009:815-820.

［4］ANDREWS M，KUMARAN K.CDMA Data QoS Scheduling on the Forward Link with Variable Channel Conditions［R］.BellLabs Technical Memo No.10009626000404205TM，2000:1-45.

［5］仉娟娟，杨丰瑞.HSDPA中M-LWDF实时业务分组调度算法的改进［J］.无线电工程，2009，39(4):11-13.ZHANG Juanjuan，YANG Fengrui.Modified M-LWDF Packet Scheduling Algorithm for HSDPA［J］.Radio Engineering，2009，39(4):11-13.

［6］BASUKALA R，MOHD R H A，SANDRASEGARAN K.Performance Analysis of EXP/PF and M-LWDF in Downlink 3GPP LTE System［C］//IEEE.First Asian Himalayas international conference.Nepal:IEEE，2009:1-5.

［7］AMEIGEIRAS P，WiIGARD J，MOGENSEN P.Performance of the M-LWDF scheduling algorithm for streaming services in HSDPA［C］//IEEE.Vehicular Technology Conference.USA:IEEE，2004:999-1003.

［8］PIRO G，GRIECO L，BOGGIA G，et al.Simulating let cellular systems:an open source framework［J］.Transaction on Vehicular Technology，2011:498-513.

［9］CAMP T，BOLENG J，DAVIES V.A survey of mobility models for ad hoc network research［J］.Wireless Commun.Mobile Comput，2002:483-502 .