紧急度感知的混合业务分组调度策略

吴大鹏，龚长河，刘乔寿，王汝言

（重庆邮电大学光通信与网络重点实验室，重庆400065）

紧急度感知的混合业务分组调度策略

吴大鹏，龚长河，刘乔寿，王汝言

（重庆邮电大学光通信与网络重点实验室，重庆400065）

长期演进系统在分组交换域内承载业务，延迟和分组丢弃敏感的实时业务服务质量（quality of service，QoS）难以得到满足。根据业务优先级差异、业务对延迟的敏感度等约束条件，提出了一种基于虚拟队列的分组延迟预测方法，进而根据分组延迟的预测结果确定其对系统资源需求的紧急程度，随后根据分组紧急度对缓存中的分组采用分类调度策略，以最大化系统资源利用率。结果表明，本文提出的调度策略能够有效地提高实时业务的QoS，改善网络的性能。

实时业务；调度优先级；服务质量；紧急度

0 引 言

以正交频分多路复用（orthogonal frequency division multiplexing，OFDM）以及多输入多输出（multiple input multiple output，MIMO）为核心技术的长期演进（long term evolution，LTE）系统能够显著提高传统蜂窝无线通信网络的承载能力，大幅度提升用户的移动通信体验［1－2］。由于LTE系统采用分组域承载各类业务，因此，分组调度算法对LTE系统的服务质量（quality of service，QoS）保障至关重要。

相关标准中规定LTE系统主要支持两类业务，分别为实时业务和非实时业务。众所周知，非实时业务对延迟的敏感程度较低，实时业务需要网络提供严格的延迟保障［3］。因此，对于资源相对有限的LTE系统，分组调度过程需要针对不同业务类型确定其传输的紧迫程度，以更加合理地利用系统资源。针对实时业务的QoS保障问题，国内外研究人员提出了相关解决方案，主要包括比例公平算法、指数公平算法、最大权重延迟优先算法，以上算法的共同特点是每个业务流依照特定的判断标准来确定调度优先级，即直接根据影响用户QoS的多个因素来确定调度优先级。正比公平性［4－7］（proportional fair，PF）算法由美国高通公司提出，该算法在对资源进行分配时主要考虑用户信道条件与公平性两个方面因素的影响。然而，由于未考虑队列分组延迟的影响，其无法满足实时业务对QoS的要求。为了支持实时业务，朗讯贝尔实验室提出了最大权值延迟优先［8－9］（modified－longest weighted delay first，M－LWDF）算法，除了上述两方面因素外，所提出的方法还考虑了缓冲区队头分组延迟和最大分组延迟，以更加有效地支持实时业务。但M－LWDF算法吞吐量性能的提升是以牺牲用户之间的公平性为代价的。文献［10］对PF算法进行了改进，利用队头分组延迟和业务允许最大延迟产生相应的调度权重，进而调节其调度优先级，在分组投递率方面获得了一定的提升，但无法兼顾用户的公平性与系统吞吐量。文献［11］把用户瞬时速率、平均速率、分组丢弃率、队头分组等待延迟、最大允许延迟等参数相结合来确定分组的调度优先级，但是直接把这几个参数组合在一起来确定调度优先级缺乏一定的理论依据，反而使得用户的各项性能远不如其他算法，用户QoS得不到保障。文献［12］中以视频业务延迟为参数估计用户优先级，进而为其分配系统资源，但该算法的性能提升是以牺牲吞吐量为代价的，且算法复杂度较高。综上所述，每一种调度策略都有各自的特点，本文提出的调度策略理论依据充足，在兼顾公平性与吞吐量的同时，有效地保证实时业务对延迟性能的需求。

针对上述问题，本文提出了一种带有延迟估计的分组调度机制，系统根据物理队列中分组的历史状态信息，利用虚拟队列预测缓存中分组的等待延迟，在此基础上，确定系统当前所承载的各类分组的传输状态，即紧急程度，进而，根据相关业务的特征确定分组的调度优先级。以在混合业务场景下，有效地为实时业务提供延迟性能保障，同时，在兼顾用户的公平性与系统吞吐量的前提下，达到降低分组丢弃率的目的，实现系统资源分配最优化。

1 延迟预测

如前所述，LTE系统采用分组域承载各类业务，不同分组的排队延迟、传输延迟等均不相同。对于实时业务来说，系统为其确定了最大允许延迟。为了避免浪费有限的系统资源，系统将主动丢弃超过给定延迟阈值的分组。显然，根据不同分组的延迟状态，其等待传输机会的紧急程度不同。越接近丢弃阈值的分组其紧急程度越高，若无法及时地为这些分组分配系统资源，则此类分组将由于无法得到调度而被丢弃，从而导致分组丢弃概率上升，系统性能下降。

为了根据分组的传输状态合理地为其分配系统资源，本文提出了一种带有虚拟队列的延迟预测方法，如图1所示，虚线部分表示虚拟队列，其作用是把缓存中未进入队列等待调度的分组放在虚拟队列中模拟调度，进而根据物理队列中分组历史状态信息来估计虚拟队列中分组的等待延迟，最终确定其调度优先级。可见，采用上述方法可根据分组传输状态获知缓存中分组的等待延迟，提高延迟较大分组的调度优先级，从而避免这些分组超过最大允许延迟而被丢弃，达到改善网络性能的目的。

图1 虚拟队列

根据现有物理队列中分组的历史状态信息，虚拟队列可获知分组到达队列时间间隔及到达时间。到达时间间隔与每个分组到达时间以及分组数量密切相关，虚拟队列记录每个分组到达物理队列的时间，进而统计相邻两个分组到达的时间间隔，并计算分组到达间隔的平均值

式中，tk，i表示分组hi到达物理队列k的时间；nk表示队列k中分组的数量。

LTE系统在每个传输时间间隔（transmission time interval，TTI）按照分组的优先级执行调度。显然，分组等待延迟与单个TTI内所调度的分组数量密切相关。在调度分组之前，系统需要通过信道质量指示（channel quality indicator，CQI）来估计用户x的信道状态，进而确定其在队列k中分组的平均吞吐量。因此，物理队列中第i个分组hi的调度时间Rk，i为

式中，EUx表示用户x的平均吞吐量；TI表示队列I中分组到达间隔时间；EUx×TI描述了在一个TTI内可以调度的分组数量表示向上取整。由于分组等待的间隔数量为整数，因此式（2）需要向上取整。

由式（2）可以获知用户m中分组hn将在第VRk，n个时间间隔得到调度，即

此外，分组等待延迟的估计值与其到达虚拟队列的时间直接相关，该参数主要由前一个分组到达时间与物理队列的到达时间间隔所决定

进而，可获知分组等待延迟

其主要由分组等待调度的时间间隔、分组到达队列时间以及监测到分组时所记录的时间来决定，其中tok表示监测到分组时所记录的时间。

2 分组分类

对于实时业务来说，延迟是最敏感的参数。显然，平均延迟是判断分组紧急状态的重要衡量指标，因此本文采用该参数确定分组的紧急状态。根据每个分组的等待延迟估计值可以得到同种业务下分组的平均等待延迟，其由各个业务分组等待延迟总和的平均值确定

然而，单纯地根据分组的延迟无法确定其紧急状态，如前所述，LTE系统中不同业务对延迟的敏感度不同，因此，针对语音业务和视频业务，本文分别统计其队头分组的平均延迟，然后把用户m中分组hi的等待延迟dm，n与所属业务类别的平均延迟进行比较，当Dm，n＜dm，n时，则将该分组定义为紧急分组，否则为非紧急分组。

显然，紧急分组比非紧急分组更接近延迟阈值，若此类分组长期得不到调度将处于“饿死”状态，甚至直接被丢弃，导致用户QoS无法得到保障。因此，系统需要首先根据分组的紧急程度确定其调度优先级，然后为其分配资源进行调度，其调度优先级按照下式确定：

式中，Tn，max表示业务允许最大延迟；dm，n表示分组等待延迟；W表示该分组的紧急度。即分组等待延迟越大，越接近业务允许最大延迟，使得分组紧急度越高。

但是，单纯地用紧急度来定义分组的优先级并不合理，其主要原因在于LTE中规定了语音业务流的优先级大于视频业务流，为了避免低优先级分组与高优先级分组竞争系统资源，在分组调度优先级确定过程中需要特别考虑语音业务的调度优先级。当业务紧急度相同时，语音业务最大允许延迟较小，接近丢弃阈值的时间较短，其调度优先级应高于视频类业务。因此，本文进一步采用业务允许最大延迟作为辅助衡量参数以确定调度优先级，达到提高语音业务调度优先级的目的。引入分组紧急度是为了提高接近丢弃阈值分组的调度优先级。由此可知，紧急分组的调度优先级需要综合考虑分组紧急度与业务允许最大延迟来制定，如式（8）所示，紧急度越高的分组调度优先级越大，反之则越小，而业务允许最大延迟越大，调度优先级越小，反之则越大。

例如延迟敏感的VoIP语音业务最大允许延迟为20ms［10］，视频业务最大允许延迟为100ms，按照本文所提出的方式，在紧急度相同的情况下，语音分组的调度优先级就得到了提高。

按照上述方式，在系统为紧急度较高的分组分配资源之后，紧急度较低的非实时业务才能得到调度，为了兼顾系统吞吐量以及用户公平性，本文引入瞬时速率和平均速率来确定非紧急分组的调度优先级，瞬时速率是为了保证系统吞吐量而引入的参数，瞬时速率越大，则分组调度优先级越大，反之则越小。平均速率是为了保证公平性而引入的参数，若用户在当前时刻之前所得到的调度机会较多，则其平均速率将随之增加，为了保证各个用户之间的公平性，其调度优先级应相应地降低，从而为其他调度机会较少的用户预留系统资源。其调度优先级为

式中，Rm（t）表示用户m的瞬时速率，可由自适应调制和编码模块（adaptive modulation and coding，AMC）通过CQI反馈信息获知（t）表示用户的历史平均速率，其定义如下：

3 分组调度

本文所提出的分组调度策略基本过程如图2所示。所提出的策略包含4个阶段，分别为虚拟队列建立及延迟预测阶段、平均延迟获知节点、分组分类阶段、调度优先级确定及资源分配阶段。

图2 分组调度过程

步骤1 建立一个虚拟队列，通过对物理队列中分组历史状态信息的统计，可由式（5）预测出分组延迟；

步骤2 通过式（6）获知分组平均延迟；

步骤3 首先根据预测的分组延迟以及平均延迟对分组进行分类，高于平均延迟的为紧急分组，反之，归类为非紧急分组，然后根据式（7）定义分组紧急度；

步骤4 通过式（8）与式（9）对紧急分组以及非紧急分组定义调度优先级，该策略首先为紧急分组分配资源，待紧急分组调度完后，非紧急分组才开始获得调度机会。

4 数值分析

4．1 仿真场景

本部分采用LTE系统仿真平台［13］对所提出的分组调度策略进行验证。仿真场景设置为单小区，视频业务用户数为50%，语音业务用户数为50%，且用户以3km／h的速度移动。其他仿真参数如表1所示。

表1 参数设置

本文用如下公平标准来判断系统的公平性：

式中，k表示用户的数量；xi表示用户i的平均速率。

4．2 数值仿真结果

本部分将本文所提出的分组调度机制（packet scheduling scheme using virtual queue，PSS－VQ）与典型分组调度算法进行了比较，以验证本文提出的机制对实时业务的QoS满足度及对整个系统的影响。其中，文献［10］提出的延迟感知的分组机制（delay－aware packet scheduling，DAPS）策略在PF算法的基础上考虑了延迟参数，以确定用户的调度优先权，在实时业务场景下具有较好的性能。

视频业务的分组丢弃率如图3所示，由结果可知，视频业务的分组丢弃率随着用户数增加而增加，当用户数量超过20后，PSS－VQ与DAPS上升较缓慢，当用户数达到55时，PSS－VQ较M－LWDF与DAPS算法的视频分组丢弃率降低了15%左右。

图3 视频业务的分组丢弃率

视频业务的平均延迟如图4所示，结果表明视频业务的平均延迟随着用户数量的增加而呈现出上升趋势，PSS－VQ较其他几种分组调度算法延迟性能优势明显，当用户数达到55时，平均延迟降低7%左右。

视频业务的公平性如图5所示，从图可知，视频业务的公平性随着用户数的增加而降低，但是PSS－VQ降低幅度最小，从用户数达到30过后优势较明显，当用户数达到55时，公平性提高了9%左右。

图4 视频业务的平均延迟

图5 视频业务的公平性

视频业务吞吐量如图6所示，结果表明视频业务的PSS－VQ相对M－LWDF有所提高，当用户数达到55时，PSS－VQ较其他两种算法性能提高了10%左右。

图6 视频业务的吞吐量

M－LWDF、PSS－VQ、DAPS都不同程度考虑到延迟对视频业务服务质量的影响，但是这3种算法在视频业务性能上有所差异。本文提出的PSS－VQ根据队列状态信息预测分组的紧急程度，将等待传输的分组进行分类，根据不同的调度优先级判断准则为实时业务分配资源。该策略提高了接近延迟阈值分组的调度优先级，避免这类分组超过延迟阈值被丢弃，降低了分组丢弃率，同时提高了用户公平性。此外，在考虑知道调度优先级判断准则时，引入了瞬时速率因素，提高了系统吞吐量。

语音业务的分组丢弃率如图7所示，结果表明随着用户数量的增加，语音业务的分组丢弃率不断增加，当用户数小于40时，所有的分组调度策略分组丢弃率性能相似，当用户数继续增加时PSS－VQ的分组丢弃率较其他两种分组调度策略增加缓慢，其分组丢弃率方面性能最优。当用户数达到55时，分组丢弃率降低了30%左右。

图7 语音业务的分组丢弃率

语音业务的平均延迟如图8所示，由结果可知，当用户数小于20时，3种策略性能相仿，随着用户数量的增加，语音业务的平均延迟不断增加，当用户数达到55时，PSS－VQ较M－LWDF、DAPS提升了15%左右，优势明显。

图8 语音业务的平均延迟

语音业务的公平性如图9所示，由结果可知，3种调度策略的公平性都在小范围内变化，公平性性能差异不大。

语音业务的吞吐量如图10所示，由结果可知，所有的分组调度策略中语音用户的吞吐量都在小范围内波动，各种分组调度策略就语音业务的平均吞吐量性能相仿。

语音业务属于对延迟特别敏感的实时业务。M－LWDF、DAPS调度策略考虑到了延迟对语音业务的性能影响，都加入了与延迟相关的加权因子，其性能差异较小。PSS－VQ调度策略提高了语音业务的调度优先级，在延迟、分组丢弃率性能方面提高显著，其中，当用户数达到55时，平均延迟提高了15%左右，分组丢弃率降低30%左右。LTE系统中语音业务是通过VoIP承载，话音编码器按固定的周期分组输出，VoIP分为激活期和静默期。只有在激活期的才有话音业务数据，静默期无数据输出，因此，语音业务的吞吐量和公平性性能变化不大。

图9 语音业务的公平性

图10 语音业务的吞吐量

4．3 算法时间复杂度分析

对于所提出的PSS－VQ算法，在计算各个业务分组平均延迟时的复杂度为O（n），在计算分组等待延迟时的复杂度为O（1），在计算调度优先级时的复杂度为O（1）。因此，从整个算法流程来看，PSS－VQ算法的时间复杂度为O（n）。

而文献［10］中DAPS算法的时间复杂度为O（nlog2n），经典的M－LWDF算法的时间复杂度为O（n）。因此，PSSVQ算法的时间复杂度与经典的M－LWDF算法相同，DAPS算法的时间复杂度明显高于PSS－VQ算法。

5 结 论

针对实时业务的特殊性，本文提出了带有延迟预测的分组调度机制。其核心思想是利用虚拟队列预测分组等待延迟，以确定分组的紧急度，进而根据不同的分组调度准则来确定其调度优先级。同时，在确定调度优先级的过程中，充分考虑了语音业务及视频业务的优先级，以更加合理地为不同业务分配系统资源。结果表明，采用本文所提出的分组调度方法能够有效地保障语音业务和视频业务的QoS。

［1］Zeng Y H，Zhu G X，Wu W M，et al．Uplink resource schedu－ling algorithms in LTE system［J］．Journal of Chinese Computer Systems，2012，33（5）：1018－1022．（曾宇辉，朱光喜，吴伟民，等．LTE系统中上行资源调度算法研究［J］．小型微型计算机系统，2012，33（5）：1018－1022．）

［2］Wu S J．A channel quality aware scheduling and resource allocation strategy for downlink LTE systems［J］．Journal of Computational Information Systems，2012，8（2）：695－707．

［3］Liu B，Tian H，Xu L．An efficient downlink packet scheduling algorithm for real time traffics in LTE systems［C］∥Proc．of the Consumer Communications and Networking，2013：364－369．

［4］Choi J，Kim Y H，Lee J H，et al．User throughput estimation for the PF scheduling algorithm under MIMO channel environments［J］．IEEE Wireless Communications Letters，2012，1（5）：528－531．

［5］Li X，Li B，Lan B．Adaptive PF scheduling algorithm in LTE cellular system［C］∥Proc．of the Information and Communication Technology Convergence，2010：501－504．

［6］Chao I F，Chiou C S．An enhanced proportional fair scheduling algorithm to maximize QoS traffic in downlink OFDMA sytems［C］∥Proc．of the Wireless Communications and Networking，2013：239－243．

［7］Choi J G，Bahk S．Cell－throughput analysis of the proportional fair scheduler in the single－cell environment［J］．IEEE Trans．on Vehicular Technology，2007，56（2）：766－778．

［8］Lai W K，Tang C L．QoS－aware downlink packet scheduling for LTE networks［J］．Computer Networks，2013，55（7）：1689－1698．

［9］Iosif O，Banica I．On the analysis of packet scheduling in downlink 3GPP LTE system［C］∥Proc．of the 4th International Conference on Communication Theory，Reliability，and Quality of Service，2011：99－102．

［10］Bae S J，Choi B G，Chung M．Delay－aware packet scheduling algorithm for multiple traffic classes in 3GPP LTE system［C］∥Proc．of the 17th Asia－Pacific Conference on Communications，2011：33－37．

［11］Ramli H A M，Basukala R，Sandrasegaran K，et al．Performance of well known packet scheduling algorithms in the downlink 3GPP LTE system［C］∥Proc．of the 9th Conference on Malaysia International Communications，2009：815－820．

［12］Piro G，Grieco L A，Boggia G，et al．Two－level downlink scheduling for real－time multimedia services in LTE networks［J］．IEEE Trans．on Multimedia，2011，13（5）：1052－1065．

［13］Piro G，Grieco L A，Boggia G．Simulating LTE cellular systems：an open－source framework［J］．IEEE Trans．on Vehicular Technology，2011，60（2）：498－513．

E－mail：wudapengphd＠gmail．com

龚长河（1988－），男，硕士研究生，主要研究方向为LTE分组调度。

E－mail：lr1pgch＠163．com

刘乔寿（1979－），男，副教授，硕士，主要研究方向为泛在网络、物联网。

E－mail：liuqs＠cqupt．edu．cn

王汝言（1969－），男，教授，博士，主要研究方向为泛在网络、全光网络理论与技术、多媒体信息处理。

E－mail：wangry＠cqupt．edu．cn

Hybrid business packet scheduling policy of emergency degree aware

WU Da－peng，GONG Chang－he，LIU Qiao－shou，WANG Ru－yan
（Key Laboratory of Optical Communication and Networks，Chongqing Univercity of Posts and Telecommunications，Chongqing 400065，China）

The long－term evolution system carries traffic in the packet－switched domain．The quality of service（QoS）of delay and packet loss－sensitive real－time services is difficult to be satisfied．According to the service priorities difference and the constraint condition of delay sensitivity，a virtual－queue－based packet delay prediction strategy is proposed．In the strategy，the packet urgency is determined by the predictable packet delay，and then the packets are classified according to the packet urgency．Compared with other scheduling strategies，results show that the scheduling strategy can improve the QoS of the real－time business effectively，and the network performance can be improved effectively．

real－time services；scheduling priority；quality of service（QoS）；emergency degree

TP 393．04

A

10．3969／j．issn．1001－506X．2015．06．26

吴大鹏（1979－），男，教授，博士，主要研究方向为泛在无线网络、无线网络服务质量管理。

1001－506X（2015）06－1399－06

2014－04－25；

2014－09－28；网络优先出版日期：2014－10－17。

网络优先出版地址：http：／／www．cnki．net／kcms／detail／11．2422．TN．20141017．1606．006．html

国家自然科学基金（61371097）；重庆市自然科学基金重点项目（CSTC2013JJB40001，CSTC2013JJB40006）；重庆邮电大学青年自然科学基金（A2012－93）资助课题