LTE 系统视频业务的调度算法

2016-06-13丁家瑞刘凯孙婕刘志敏

电信科学 2016年4期

关键词：传输速率时延信道

丁家瑞，刘凯，孙婕，刘志敏

（北京大学信息科学技术学院，北京 100871）

LTE 系统视频业务的调度算法

丁家瑞，刘凯，孙婕，刘志敏

（北京大学信息科学技术学院，北京 100871）

实时性是评价实时视频业务的重要指标之一，目前针对实时视频业务的已有调度算法还存在严重的时延拖尾现象。重点研究了该问题，在分析已有调度算法的基础上，提出了“最大吞吐率—最大权重时延优先”（modified largest weighted delay first，MT-LWDF ）算法；理论分析了算法中 β 参数的取值范围，并通过仿真确定 β 的最优解，在此基础上，对视频业务的平均时延、最大时延、业务速率、丢帧率等性能进行了仿真，并与其他 6种算法进行对比。结果表明，提出的 MT-LWDF 算法在优化视频业务的速率的基础上，有效降低时延拖尾现象。

LTE；调度算法；视频业务；仿真

1 引言

随着通信技术的飞速发展，在基于 OFDM（orthogonal frequency division multiplexing）的 LTE（Long term evolution）［1］系统中实现的技术越来越多，然而无线通信系统视频资源有限，如何高效地利用有限的资源支持高质量的业务是现代无线通信技术的一个瓶颈，因此引起了下行链路调度算法的研究热潮。

实时视频业务因其实时性和高数据速率对调度算法提出了更高的要求。根据 LTE 系统中对视频业务质量的要求［2］，实时视频业务视频帧的平均时延在 100 ms 以内，分组丢失率（packet loss rate，PLR）为 1‰ ，考虑到一帧之中有 8 个视频分组，可以计算视频丢帧率（frame loss rate，FLR）为 1-（1-PLR）8=8‰。

目前，在 LTE 系统中适用于视频业务的调度算法主要分为两类：一类是具有时延约束的，如最早截止时间优先（earliest deadline first，EDF）算法、最大权重时延优先（largest weighted delay first，LWDF）算法、改进的最大权重时延优先（modified largest weighted delay first，M-LWDF）算法、PPM（packet prediction mechanism）算法；一类是没有时延约束的，如轮询（round robin，RR）、比例公平（proportional fair，PF）、最优信道质量（best CQI，BCQI）或称最大吞吐率（max throughput）、QoE（quality of experience）导向的算法。

［3］将 LTE 系统信道质量反馈与视频编解码进行结合以降低视频误码率，在一定程度上使边缘用户实时业务质量得到保证，但系统时延却较高，因此该方法不在本文讨论范围内；参考文献［4］将 RR、PF、BCQI 3 种算法进行了归纳总结；参考文献［5］基于 EDF 算法与比例公平（PF）算法改变优先级函数，进行用户调度；参考文献［6］将EDF、LWDF 和 M-LWDF 算法进行了归纳总结，并指出 EDF算法在有效控制系统时延的同时，很大程度上牺牲了吞吐率，因此不适合信道质量较差的无线通信，而 M-LWDF 由于基于 PF 算法在有效控制时延的同时能得到接近于 PF算法的吞吐量，在试验控制和吞吐量上都优于 RR 调度算法；参考文献［7］提出了兼顾时延和吞吐量的 PPM （packet prediction mechanism）算法，该算法同时对时延做出了预测；参考文献［8］提出了一种 QoE 导向的算法，该算法监测用户信道质量退化情况，信道质量退化越严重，用户优先级越高。

本文在对以上8种算法进行分析的基础上提出了一种改进型算法，称为 “最大吞吐率—最大权重时延优先”（max throughput-largest weighted delay first，MT-LWDF）算法，并与已有的算法进行了性能对比。

2 几种典型的调度算法

本文分析现有的视频业务调度算法，包括 RR、PF、BCQI、EDF、LWDF、M-LWDF、PPM、QoE 导向的算法。

2.1 RR 调度算法

RR算法轮流为扇区内的用户提供资源，旨在给用户平等的机会获得系统的 RB 资源，该算法下用户的优先级函数可以表示如下。

其中，NUE代表扇区内用户总数，P1～discrete Uniform（1，NUE），Pj=（P0+j）mod（NUE+1）；j≠1。

RR算法使用用户按照设定的顺序，以均等的机会获得时域和频域资源。如果用户对资源的请求是等概率的，那么该算法在保证系统长期公平性的同时也保证了系统在短期内也是公平的，是资源分配算法中最公平的算法。然而，RR 算法仅仅关注系统的公平性，却没有考虑用户的信道质量是不同且时变的，因此该算法提供的传输可靠性并不高，从而导致系统吞吐率降低。所以 RR算法用户传输速率的公平性较差。由于 RR算法具有最高的公平性，通常被当作参考算法，用来和其他算法进行比较。

2.2 PF 调度算法

PF 算法将单个用户的瞬时传输速率（信道质量的衡量指标之一）和该用户在一个时间窗格内传输速率的平均值进行结合，如果传输速率平均值较大，说明在当前时间窗内该用户的调度时间较长，其调度优先级需要被适当降低。由此，PF 算法兼顾了公平性和用户传输速率，实现了两者之间的均衡，在第 n 个时隙内，用户的调度优先级函数可以表示如下。

其中，rj（n）表示单个用户 j的瞬时传输速率，Rj（n-1）表示一个时间窗 tc内用户 j的平均传输速率，且：

其物理意义是用户在当前时间窗内的平均传输速率，等效于传输速率以一定时间内的链路质量为权重因子进行加权平均。

PF 算法将信道的时变特性考虑在内，根据该算法，若某用户获得更多的传输资源，其调度时间就会增加，那么该用户的优先级就会降低，此前优先级较低的用户就会获得更高的传输机率。所以，PF 算法的公平性和系统传输效率介于 BCQI算法和 RR 算法之间。

2.3 BCQI调度算法

BCQI算法以使系统获得最大吞吐率为目的，最大化利用无线信道的时变性特点，同速率的资源请求条件下，使信道质量最好的用户获得最多的资源。在第n个时隙内，该算法下用户优先级函数可以表示为：

由于该算法在计算优先级时只考虑了用户的信道质量，只要信道质量更好的用户有资源请求，信道质量较差的用户就不会被调度，也就无法得到资源。

2.4 EDF 调度算法

EDF 算法只考虑用户等待时延，将传输队列最前端用户的等待时延 τHOL，j作为优先级参数，优先级与该参数正相关，时延越大优先级越高。

其中，τmax，j表示用户 j的最大时延。

2.5 LWDF 调度算法

LWDF 算法在 EDF 算法的基础上考虑了用户误码率和最大时延上限，用户优先级函数可以表示为：

其中，τHOL，j表示用户 j待传输数据分组队列头的等待时延，αj表示对应的权重，δj表示第 j个用户的最大误码率。

由于 LWDF 算法没有考虑信道质量的时变性，因此系统吞吐量不高。

2.6 M-LWDF 调度算法

M-LWDF 算法将 PF 调度算法与 LWDF 算法进行了结合，在考虑时延的同时也考虑了信道质量，在时延和系统吞吐量之间实现了一种均衡。优先级函数可以表示为：

2.7 PPM 调度算法

该算法将用户数据分组时延（包含预测时延）和用户移动性结合，在降低用户时延的同时也能兼顾系统吞吐量和误码率。该方法主要分为 5个步骤，具体如下。

步骤 1 通过用户端反馈的 CQI （channel quality indicator）确定用户的移动性。

步骤2 根据用户队列中数据分组的剩余时延确定调度优先级，剩余时间越少，优先级越高。

步骤 3 预测用户队列中数据分组的延时情况，若预测该数据分组不会超时，则不执行步骤 4，否则执行。

步骤 4 若预测队列中有数据分组会超时，则优先处理，直至把所有预计超时的数据分组处理完毕。

步骤5 针对不同速率的用户采用不同的调度算法。

由于该算法兼顾时延和吞吐量，其性能会介于 BCQI算法和 EDF 算法之间。

2.8 QoE 导向的算法

该算法在用户端对用户不同时隙的信道质量波动进行检测，得出信道质量退化指标并反馈给基站，基站通过该指标配置用户优先级，用户信道质量退化越大，优先级越高，这样能保证信道质量波动较大的用户获得足够的带宽资源。为了保证状态太差的用户不会长时间占用系统资源，该算法给每个用户设定了最大调度时间上限。该算法流程如图 1所示。

图1 QoE 导向的算法流程

该算法使信道质量较差的用户能得到较好的资源分配，但同时需要一定的检测时间，根据仿真结果，短时间内该算法的吞吐量低于 RR 算法，一定时间后会高于 RR算法。

2.9 典型调度算法的总结

RR 算法只考虑资源分配时用户的公平性，所以，其在资源分配上最为公平，但用户传输速率较差；BCQI算法只考虑了用户的信道质量，系统速率较高，相反，用户资源分配公平性较差；PF 算法将信道的时变特性考虑在内，算法的公平性和系统传输速率介于 BCQI算法和 RR 算法之间。QoE 导向的算法主要考虑信道质量变差的用户，算法公平性较好，但系统吞吐量不高。这 4种算法均没有考虑时延。

EDF 算法将传输队列最前端用户的等待时延作为优先级参数，最大程度上降低了系统传输时延，同时也牺牲了系统传输速率；LWDF 算法在 EDF 算法的基础上考虑了时延上限，但没有考虑信道质量，因此系统吞吐量也不高；M-LWDF 算法将 PF 调度算法与 LWDF 算法进行了结合，在考虑时延的同时也考虑了信道质量，实现了时延和系统吞吐量之间的均衡。PPM 兼顾时延和吞吐量，同样实现了时延和系统吞吐量之间的均衡。

3 最大吞吐率—最大权重时延优先算法

根据前文讨论，现有调度算法在时延处理和吞吐率优化方面各有优缺点，为了在保证时延的基础上提升吞吐率，本文将 EDF 算法和 BCQI算法进行结合来优化调度算法。

由于 EDF 算法没有考虑信道质量，致使其吞吐率过低，而 M-LWDF 算法中乘以 PF 算法相关因子，来自信道质量的影响因子不够强。为此，本文首先依据 BCQI算法，在式（5）中乘以吞吐率相关的因子，以提高信道质量的影响进而提升吞吐率。该优化算法称为线性时延权重优先算法（LIN-LWDF），旨在同时优化时延和吞吐率。

该优化算法下用户优先级表达式为：

其中相关参数如前文所示。类似于 M-LWDF 算法，LIN-LWDF 算法可能存在时延“拖尾”问题，为此，本文对时延较高的数据分组采用了指数型非线性影响因子。此外，在LTE 系统中，可以根据来自用户反馈的 MCS 等级，进而进行传输块（TB）索引［9］映射（集合 iTBS=｛1，2，… ，26，27｝），得到高于线性增长率的非线性对应关系。

本文将这种时延指数型非线性关系映射到优先级上的算法，称为“最大吞吐率—最大权重时延优先”（MT-LWDF）算法。优先级表达式为：

由于 LTE 系统中最小的调度单位是子帧，也即 1 ms，所以在仿真实时视频业务时，将毫秒（ms）作为时延的单位。

假设某一用户为 j，其等待传输的数据分组队列为 k，队列头的等待时延为。 τmin=1，视频业务中，每个用户的数据分组平均时延最高为100 ms，考虑到个别数据分组存在较大时延的偶然性以及兼顾信道的随机性，设定 τmax=150。

由于该算法的相对优先级同时受到时延和速率的影响，所以提出以下约束条件来确定 β的取值范围。

约束 1 延迟参数 τHOL，j的影响因子不能为 0，也即BCQI算法的 ri不能完全决定不同用户的相对优先级大小，否则，该算法将等同于 BCQI算法。约束关系表示为：

约束 2 BCQI算法的 ri的影响因子不能为 0，也即LWDF 算法的 τHOL，j不能完全决定不同用户的相对优先级大小，否则，该算法将等同于 LWDF 算法。约束关系表示为：

约束 3 τHOL，j取最大值，rj取最小值时，该算法的优先级不能小于 τHOL，j取最小值，rj取最大值时的优先级。约束关系表示为：

参考文献［1］中规定了 rj的取值范围，当 iTBS分别取18、17 时式（10）比值最小，其变换后的表达式为：

可得：

式（11）变换后的表达式为：

可得：

式（12）变换后的表达式为：

可得：

综合式（16）～式（18）可得 β的取值范围为：

基于 BCQI算法对不同 iTBS、β取值下的相对优先级进行了仿真，如图 2 所示。图 2 中，圆圈表示优先级，下方竖条表示时延因子对优先级的影响。当 β取值较小（β=10）时相对优先级变化不明显，优先级变化范围重叠很多；当 β取值较大（β=1 500）时，时延因子对优先级的影响太小，因此，采用的 β的范围为 β∈［10，100］。

4 调度算法的仿真分析

由于视频业务中用户随机接入并请求发送数据，其数据传输时间由具有随机性的数据分组大小和信道速率决定。而半马尔科夫过程（semi-Markov process，SMP）是采用了指数形式的无记忆模型，因此数据传输时间不能直接用该方法分析建模。本文根据延时约束采用仿真方法来确定β的取值，然后分析提出的新算法和现有算法在吞吐率和时延方面的性能。

实时视频业务源模型，采用 3GPP［10］和 IEEE 视频业务文档［11］的定义。视频业务的基本单位是视频帧，其周期为100 ms，每个视频帧含 8 个数据分组，其长度及间隔服从截断 pareto 分布。该业务源模型参数见表 1。根据该业务源模型产生的数据分组的分布如图 3所示。

图2 不同 iTBS、β 取值下的相对优先级（BCQI 算法与 MT-LWDF 算法）

本文采用的仿真平台基于 TD-LTE 系统级仿真平台［12］，仿真参数见表 2。

根据前面理论推导确定了 β的范围为 β∈ ［10，100］，在该范围内进行离散化仿真可得如图 4所示的仿真结果。

表1 实时视频业务源模型参数

图3 实时视频业务源模型

根据该仿真结果可以确定当 β∈［35，40］时系统时延取得极小值，而同时系统速率取得局部极大值，由于本文算法在时延参数上基于 EDF 算法，故设定 β取值为 35。由仿真得到最优的 β数值后，在 TD-LTE 仿真平台中，对不同的调度算法的性能进行仿真，得到不同的仿真结果。

表2 TD-LTE 系统级仿真平台仿真参数

从图 5 可以看出，在系统速率方面 BCQI算法优于PF 算法，MT-LWDF 算法相对于 M-LWDF 算法提升约 6%，相对于 EDF 算法则有更高的提升，但略低于 BCQI算法；LIN-LDWF 算法和 MT-LWDF 算法基本相同。时延方面，BCQI算法最高，与理论结果相符；MT-LWDF 算法相对于M-LWDF 算法降低约 5%；LIN-LDWF 算法平均时延接近于M-LWDF，因为其采用线性因子，所以时延改进不明显，由于指数因子的引进，长时延的数据分组优先级被提高，MT-LWDF 算法降低时延的同时也在很大程度上减少了拖尾现象。

图4 扇区速率与系统平均时延随参数 β 变化关系

图5 7种调度算法下的系统速率和时延均值

从图 6 可以看出，在非满负载情况下，EDF 算法速率分布范围最小，BCQI算法速率分布最大，说明这两种算法的用户公平性一个最高一个最低，其他 5种算法速率分布差异性较小，公平性处于两者之间。

图6 7种调度算法下 UE 平均速率 CDF 曲线

时延分布是评价用户 QoS 的一个重要参数，因此时延拖尾现象将拉长时延分布，降低用户 QoS。

从图 7 中可以看出，M-LWDF 算法拖尾比较长，超出了时延上限，而采用线性因子的 LIN-LWDF 算法并没能解决该现象。MT-LWDF 算法因指数因子的引进有效降低了拖尾现象，将时延分布上限由 160 ms 降低到 90 ms，拖尾范围降低了 44%，使得 MT-LWDF 算法时延范围接近于EDF 算法，说明该算法在改善拖尾现象的同时优化了系统速率。

图7 7种调度算法下 UE 平均时延 CDF 曲线

图8 7种调度算法下 UE 最大时延 CDF 曲线

除平均时延分布外，图 8中的最大时延分布也能反映拖尾现象。和图 7 的 UE 平均时延类似，在最大时延方面，MT-LWDF 算法降低了 M-LWDF 算法中的拖尾现象。使最大时延上限由 220 ms 降低到 110 ms，降低了 50%。同平均时延一样，LIN-LWDF 算法在最大时延分布方面没能得到有效改善。

在前文提到，视频业务理论丢帧率（FLR）为 8‰。从图 9可以看出，EDF、M-LWDF、MT-LWDF、LIN-LWDF 4 种算法都能满足丢帧率要求，而 RR、PF、BCQI算法则不能满足丢帧率要求。而实际上，由于不同算法下系统速率不同，实际传输的视频帧数目也不同，针对丢帧率没有很高的研究意义。

5 结束语

首先，本文重点针对视频业务延时问题，在分析了已有调度算法的基础上，将系统速率纳入算法的考虑范围，并基于时延和系统速率提出了具有指数型非线性权重的MT-LWDF 算法。

然后，根据理论分析得出 β的取值范围为 β∈［10，100］，由于 MT-LWDF 算法中时延和速率两个参数的随机性，无法通过理论计算推导出最优 β的解析解，所以采用仿真的方法确定 β=35 时系统时延可在局部取得极小值，同时系统速率在局部取得极大值。

最后，将 β=35 设为仿真参数对 7 种调度算法进行仿真得到不同指标下的仿真结果，并根据这些指标将优化的MT-LWDF 算法与其它算法对比分析，得出：MT-LWDF 算法有效降低了拖尾现象，将时延分布上限由 160 ms 降低到 90 ms，拖尾范围降低了 44%，同时将最大时延上限由220 ms 降低到 110 ms，拖尾范围降低了 50%。

图9 7种调度算法下的系统的丢帧率与总传输帧数

参考文献：

［1］ 3GPP.Group radio access network-requirements for evolved UTRA （E-UTRA）and evolved UTRAN （E-UTRAN）：3GPP TS 25.913［S］.2007.

［2］ Standardized QCI characteristics.Group services and system aspects-policy and charging control architecture （Release 13）：3GPP TS 23.203［S］.2015.

［3］ RADHAKRISHNAN R，NAYAK A.Cross layer design for efficient video streaming over LTE using scalable video coding［C］／The 2012 IEEE International Conference on Communications（ICC），June 10-15，2012，Ottawa，ON，Canada.New Jersey：IEEE Press，2012：6509-6513.

［4］刘壮.LTE 系统中下行链路的分组调度算法研究［D］. 北京：北京邮电大学，2014. LIU Z.Research on the downlink packet scheduling algorithm in LTE system ［D］.Beijing：Beijing University of Posts and Telecommunications，2014.

［5］ LIU B，TIAN H，XU L L.An efficient downlink packet scheduling algorithm for real time traffics in LTE systems ［C］／／The 2013 Consumer Communications and Networking Conference （CCNC），Jan 11-14，2013，Las Vegas，NV，USA. New Jersey：IEEE Press，2013：364-369.

［6］ CAPOZZI F，PIRO G，GRIECO L A，et al.Downlink packet scheduling in LTE cellular networks：key design issues and a survey［J］.IEEE Communications Surveys&Tutorials，2013（15）：678-700.

［7］ WEI K L，CHIH W H，HUAN K T，et al.A LTE downlink scheduling mechanism with the prediction of packet delay［C］／／The 2015 7th International Conference on Ubiquitous and Future Networks （ICUFN），July 7-10，2015，Sapporo，Japan. ［S. l.：s.n.］，2015：257-262.

［8］ LIU Y L，ZHU D L，WEI M，et al.A QoE-oriented scheduling scheme for HTTP streaming service in LTE system ［C］／2015IEEE Symposium on Computers and Communication （ISCC），July 6-9 ，2015 ，Larnaca ，Cyprus.New Jersey ：IEEE Press，2015：889-894.

［9］ Technical Specification Group Radio Access Network.Physical layer procedures for universal terrestrial radio access （UTRA）（Release 12）：3GPP TR36.213［S］.2015.

［10］3GPP R1-070674.Feasibility study for OFDM for UTRAN enhancement：3GPP TR 25.892（Release 6）［S］.2004.

［11］IEEE 802.16 Task Group m.IEEE 802.16m evaluation methodology document （EMD）［S］.2009.

［12］何金薇，丁璐，刘志敏.LTE 系统级仿真建模实现及其优化［J］.计算机工程与应用，2012，48（22）：104-108. HE J W，DING L，LIU Z M.The realization of modeling and optimization ofLTE system-levelsimulation ［J］.Computer Engineering and Application，2012，48（22）：104-108.

A scheduling algorithm for optimizing video traffic

DING Jiarui，LIU Kai，SUN Jie，LIU Zhimin
School of Electronics Engineering and Computer Science，Peking University，Beijing 100871，China

Real-time is an important criterion for evaluation of the real-time video traffic.Most of the existing scheduling algorithms have a wide distribution of user time delay.Firstly，based on the analysis of the existing scheduling algorithms and system rate，an algorithm called MT-LWDF was proposed.Secondly，obtained the range of β after the theoretical analysis，the optimal value of β was got by computer simulation.Then，β was set with the optimal value，the simulation relating to average delay of the system，maximum delay of the users，rate of the system，video frame loss rate and other performance was done.And the results indicate that MT-LWDF algorithm can reduce the distribution of user delay at the same time of optimizing the rate of the system.

LTE，scheduling algorithm，video traffic，simulation

The National High-tech R&D Program （863 Program）（No.2012AA011401）

TN92

：A

10.11959／j.issn.1000-0801.2016109