马哲明, 吴宣利, 韩杏玲
(哈尔滨工业大学 电子与信息工程学院,150001 哈尔滨)
摘要:
针对现有LTE系统中调度算法在吞吐量、公平性及丢包率性能指标上难以取得性能平衡的问题，提出一种改进算法，在考虑用户时延的前提下还考虑了用户对资源块（RB）的利用率，从实际获得速率的角度来更精确描述用户对资源的利用能力，更加合理地分配资源.仿真结果表明，该算法的丢包率性能有很大改进，同时在吞吐量、公平性方面也有着较好表现，实现了良好的综合性能，能够更好地满足用户的QoS需求.
关键词: LTE-A 资源利用率 时延 丢包率
DOI：10.11918/j.issn.0367-6234.2016.05.008
分类号:TN929.5
文献标识码:A
基金项目:国家重点基础研究发展规划(2013CB329003)； 国家自然科学基金项目(61301100)； 国家科技重大专项项目(2013ZX03001024-003).
Resource utilization based delay prioritized scheduler algorithm in LTE-A system
MA Zheming, WU Xuanli, HAN Xingling
(School of Electronics and Information Engineering, Harbin Institute of Technology, 150001 Harbin, China)
Abstract:
To overcome the difficulty of reaching a balance of throughput, fairness and packet loss of current LTE scheduling algorithms, an enhanced algorithm is proposed. We take the Resource Block (RB) utilization into consideration on the premise of considering user delay, and hence can describe the resource utilization efficiency of users more precisely, which causes the resource is allocated more properly. Simulation results demonstrate that the algorithm has a great improvement on packet loss rate, and at the same time, it performs better in terms of throughput and fairness. It shows an excellent comprehensive performance and can better satisfy the requirements of users' Quality of Service (QoS).
Key words: LTE-A resource utilization delay packet loss rate
马哲明, 吴宣利, 韩杏玲. LTE-A系统中基于资源利用率的时延优先调度算法[J]. 哈尔滨工业大学学报, 2016, 48(5): 57-61. DOI: 10.11918/j.issn.0367-6234.2016.05.008.
MA Zheming, WU Xuanli, HAN Xingling. Resource utilization based delay prioritized scheduler algorithm in LTE-A system[J]. Journal of Harbin Institute of Technology, 2016, 48(5): 57-61. DOI: 10.11918/j.issn.0367-6234.2016.05.008.
基金项目 国家重点基础研究发展规划（2013CB329003）；国家自然科学基金项目（61301100）；国家科技重大专项项目（2013ZX03001024-003） 作者简介 马哲明(1991-), 男, 硕士研究生;
吴宣利(1980-), 男, 副教授, 博士生导师 通信作者 吴宣利, xlwu2002@hit.edu.cn 文章历史 收稿日期: 2015-06-20
Contents -->Abstract Full text Figures/Tables PDF
LTE-A系统中基于资源利用率的时延优先调度算法
马哲明, 吴宣利
, 韩杏玲 哈尔滨工业大学 电子与信息工程学院, 150001 哈尔滨
收稿日期: 2015-06-20
基金项目: 国家重点基础研究发展规划（2013CB329003）；国家自然科学基金项目（61301100）；国家科技重大专项项目（2013ZX03001024-003）
作者简介: 马哲明(1991-), 男, 硕士研究生;
吴宣利(1980-), 男, 副教授, 博士生导师
通信作者: 吴宣利, xlwu2002@hit.edu.cn
摘要: 针对现有LTE系统中调度算法在吞吐量、公平性及丢包率性能指标上难以取得性能平衡的问题，提出一种改进算法，在考虑用户时延的前提下还考虑了用户对资源块（RB）的利用率，从实际获得速率的角度来更精确描述用户对资源的利用能力，更加合理地分配资源.仿真结果表明，该算法的丢包率性能有很大改进，同时在吞吐量、公平性方面也有着较好表现，实现了良好的综合性能，能够更好地满足用户的QoS需求.
关键词: LTE-A 资源利用率 时延 丢包率
Resource utilization based delay prioritized scheduler algorithm in LTE-A system
MA Zheming, WU Xuanli
, HAN Xingling School of Electronics and Information Engineering, Harbin Institute of Technology, 150001 Harbin, China
Abstract: To overcome the difficulty of reaching a balance of throughput, fairness and packet loss of current LTE scheduling algorithms, an enhanced algorithm is proposed. We take the Resource Block (RB) utilization into consideration on the premise of considering user delay, and hence can describe the resource utilization efficiency of users more precisely, which causes the resource is allocated more properly. Simulation results demonstrate that the algorithm has a great improvement on packet loss rate, and at the same time, it performs better in terms of throughput and fairness. It shows an excellent comprehensive performance and can better satisfy the requirements of users' Quality of Service (QoS).
Keywords: LTE-A resource utilization delay packet loss rate
随着数字多媒体业务的增长，移动通信的重点开始更多地放在数据业务的传输上.相比于3G通信，LTE-A力求实现数据业务更快的传输速率、更高的频谱效率以及更低的时延[1].数据业务中的实时业务对数据传输的要求较为严格，除了一定的传输速率外，还要求具有较低的传输时迟、丢包率以及延迟抖动等.调度算法的设计对于实时业务QoS(quality of service)需求的满足也具有关键作用[2].
经典的分组资源调度算法包括轮询、最大载干比算法和比例公平算法[3]，但这些算法均具有明显缺点[4]，不能很好地满足业务实时性要求.目前应用成熟的算法主要有改进的最大权重延迟优先M-LWDF(modified largest weighted delay first)算法、指数比例公平EXP/PF(exponential PF)算法等[5].但是，这类算法依然无法保证信道质量较差用户的调度，用户由于数据包的时延过大会产生较高丢包率.针对时延问题，文献[6]提出时延优先调度DPS(delay prioritized scheduler)算法，该算法在用户数较少或用户间信道差异较小的理想假设下可以取得非常低的丢包率，在理论上可以满足时延敏感业务的QoS需求.但是该算法缺乏对用户信道质量的考虑，当有多个用户拥有相同优先级时，随机选出的用户可能信道条件较差，即使占用资源也无法满足QoS需求，造成资源的浪费，算法不仅在吞吐量上表现很差，同时丢包率反而会极大升高.文献[7]提出针对DPS算法改进的MDPS算法，在较好满足用户时延要求的基础上，解决了DPS算法当用户数较大时出现的问题，同时由于信道信息的引入显著提升吞吐量，但这一算法的性能依然有继续提升的空间.
针对上述问题，本文在考虑时延的基础上，引入用户对当前信道的利用率，从实际可达速率角度出发，提出基于资源利用率的时延优先调度RUBDPS(resource utilization based delay prioritized scheduler)算法，综合考虑了用户信道条件和传输需求，极大改善了DPS算法中用户吞吐量过低及在用户较多时丢包严重的问题，相比于MDPS算法，性能也有了一定提升.
1 系统模型在LTE-A系统中，时频资源调度的单元是资源块RB(resource block), 一个RB在时域上长度为0.5 ms，频域上包括12个子载波，总共占据180 kHz的频带宽度.不同用户由于其信道质量、业务需求等不同，对资源的需求也有所不同.资源调度需要根据用户信道信息和网络负载情况，决定哪些用户在哪段时间内可以使用哪些无线资源，从而完成对系统内有限时频资源的动态分配.调度器位于基站端，调度的周期是一个TTI(transmission time Interval)，每个TTI是1 ms.
图 1给出了下行资源调度流程[8]. UE接收来自eNodeB的小区专用参考信号，估计信道质量并向eNodeB反馈. eNodeB动态地分配下行资源并产生下行调度信令，随后根据资源分配情况将数据信息填充在相应信道上.用户根据产生的调度信令中的相关内容来选择解码相应信道获取数据.
Figure 1
图 1 下行资源调度流程 在调度过程中，信道质量是一项重要的指标，用户信道信息通常以信道质量指示符CQI(channel quality indicator)的形式上报. CQI根据每个用户的不同SINR值生成，由于用户的移动以及频率选择性衰落，每个用户的CQI数值在不同时间以及不同RB上是不同的. CQI不仅包含了用户信道质量，还指示了用户需要采用的编码调制方式. LTE-A系统采用自适应调制编码技术，根据CQI信息来动态调整编码调制方式，CQI、SINR以及编码调制方式之间的关系如表 1所示.
表 1
表 1 编码调制方式与SINR映射表 
表 1 编码调制方式与SINR映射表
从表 1可以看出，CQI与用户的SINR值呈正相关.当用户信道质量较好时，CQI值较大，系统会采用高阶调制和高编码速率，而不同的编码调制方式将会直接影响用户的数据传输速率.在第t个TTI，用户k在RBn上获得的理论速率为
式中：ns为一个子帧上的OFDM符号数；nc是其中用于控制的符号的个数；nsub为一个资源块上的子载波数；Qmk, n(t)是用户k在当前时隙下每个符号上调制的比特数，由调制方式决定；Ck, n(t)是用户k在第t个TTI时在RBn的符号速率.在LTE-A系统中，每个TTI每次分配的实际上是两个时域上连续的RB，所以nsub=12，ns=14，nc=3(采用常规循环前缀).
分组业务主要以数据包形式传输，在用户的缓冲区中，所有业务的数据包形成一个队列，遵循先进先出原则.对于位于队列首位的数据包，队头数据包HoL(head of line)时延表示该数据包的时延情况，如果HoL时延超过了时延门限，那么该数据包将被丢弃[9].而最后系统总的吞吐量计算以实际成功传输的数据包的数据量为准.
2 基于资源利用率的时延优先调度算法虽然MDPS算法解决了DPS的一些问题，但是其性能仍有提升空间.第一，MDPS算法在计算每个RB上的优先级时采用的是所有RB上的平均频谱效率，有效但不够精确；第二，MDPS算法仅仅考虑的是用户的信道质量，而有时候由于用户实际剩余数据量的限制，用户未必可以在RB上达到预期的高速率传输，给算法造成一定误差.针对以上两点，本文提出了一种全新的基于资源利用率的时延优先调度(RUBDPS)算法，该算法从用户在RB上可达实际速率入手，根据实际的RB利用率来分配资源.
RUBDPS算法在每个RB上计算用户的优先级，在RBn上用户k的优先级表达式如下：
(1) 式中：τk-Wk(t)表示目前该业务允许的时延量；T0为一个TTI的时间长度，在LTE系统中T0=1 ms；c为加权因子，其数值可根据实际需要调整; Ek, n(t)为用户k在RBn上的资源利用率，定义为
(2) Rk, nm是用户k在RBn上可获得的最大速率，与该用户具体的调制方式以及编码有关，由于在LTE-A系统中采用自适应调制编码，所有用户有可能获得的最高理论速率均为CQI=15时的调制编码策略所对应速度，为一个固定值; lk(t)代表在当前TTI下用户k的队头数据包的剩余比特数，lk(t)/T0即为在仅剩当前比特数的情况下在该TTI内所能达到的速率.由于用户实际速率以传输的数据包为准，所以会受到数据包剩余比特数目的限制，简单的频谱效率或CQI数值仅能描述用户当前的信道质量，并不能完全准确地描述用户在RB上获得的速率，所以引入资源利用率表征用户在前状态下对RB的实际利用能力，以此来改进优先级的计算方式，然后在RBn上根据k*=arg max(Mk, n(t))来选出合适的用户.
一般来说实时业务都需要满足一定的保证数据传输速率，所以算法中当某个RB依据优先级公式完成分配后，系统会根据用户的速率情况让已经达到GBR要求的用户退出分配.最终的分配结果以分配向量
输入：
系统资源块数目N;
接入系统用户集合K={1, 2, …, K};
每个用户的时延门限τ1, τ2, …, τk;
每个用户的HoL时延W1, W2, …, Wk.
输出：资源块分配向量A.
1) 在RBn(n从1开始取值)上，计算每个集合中用户在当前TTI下队头数据包剩余比特数lk(t)，根据式(2)计算资源利用率Ek, n(t)，将A的所有元素清零.
2) 根式(1)计算每个用户在当前TTI下在RBn上的优先级数值Mk, n(t).
3) 根据k*=arg max(Mk, n(t))挑选优先级最高的用户k*，分配到RBn上，更新A，令an=k*.
4) 计算k*在RBn上获得速率，并更新k*在该TTI上的速率.
5) 完成在RBn上的分配后判断用户获得数据速率是否达到GBR要求，若用户k*数据速率大于等于GBR，则把k*从服务列表中清除，K=K/{k*}.
6) 令n=n+1，重复上述步骤，直至RB分配完毕.
7) 返回该TTI下资源块分配向量A.
该算法通过考虑用户实际获得速率来改善系统的吞吐量，引入GBR的限制来更新用户列表保证公平性，同时包含对时延的考虑，可以更好地满足业务QoS需求.
3 仿真分析 3.1 仿真环境本文研究的用户分布在半径500m的六边形小区中，用户受到来自周边6个小区的干扰，用户的信道模型加入了路径损耗和阴影衰落，多径衰落信道模型采用TU3.本信道模型从实际角度出发，区别于文献[6]中用户信道相差不多的理论情况.用户传输业务类型为实时视频流，包尺寸分布规律与文献[6]相同，其他仿真参数参见表 2.
表 2
表 2 系统仿真参数设置 
表 2 系统仿真参数设置
3.2 加权因子的确定式(1)中c的数值决定了算法中用户资源利用能力的权重.文献[7]的仿真结果指明DPS算法的公平性最好，吞吐量最差，这是由于该算法完全不考虑用户的信道条件，因此用户信道质量在算法中所占比重将影响算法最终的吞吐量与公平性表现.
图 2和图 3分别给出了系统中存在60个激活用户的条件下，系统的吞吐量和公平性随加权因子c的取值而变化的情况，这里的公平性是以Jain’s指数进行衡量的.从仿真图中可以看出，随着加权因子c的数值增加，系统的吞吐量逐渐提升，但公平性会有一定的下降，即吞吐量与资源利用率权重成正相关，公平性与资源利用率成反相关.在使用中，可以根据实际需求对加权因子的取值综合考虑。从图 2得知，在加权因子大于3.5时，吞吐量增长比较缓慢，这是由于此时对资源利用率的考虑已经比较充分，优先级计算公式已经对数据速率给予了足够高的权重，因此已经能够取得较高的吞吐量。进一步的增大加权因子数值不能换取吞吐量的快速提升，反而会导致公平性的下降，所以从折中角度考虑，本文在后续仿真中选取c=3.5。
Figure 2
图 2 K=60时吞吐量变化 Figure 3
图 3 K=60时公平性指数变化 3.3 不同算法对比仿真结果根据文献[7]的结果，M-LWDF和EXP/PF的性能较为接近，M-LWDF在公平性和丢包率方面稍好一些，所以本文仅对M-LWDF、DPS、MDPS以及RUBDPS这4种算法进行仿真，主要关注丢包率、吞吐量、公平性3个性能指标.
在满足时延和公平性要求的前提下，丢包率会对实时业务的用户体验有明显影响，因此成为实时业务资源分配算法的一项重要指标. 图 4给出了用户的丢包率仿真结果.当用户数目低于50时，RB资源较为充足，几乎所有算法的丢包率都为0.当用户数逐渐增加时，由于无线资源总量的限制，不能满足所有用户的需求，所以会有部分数据包被丢弃，丢包率数值开始上升.当用户数小于80时，可以看到M-LWDF算法的丢包率明显高于其他算法，而其他算法由于在优先级的计算过程中以时延为优先，所以在中载条件下表现出较低的丢包率.随着用户数进一步增多，当用户数超过80时，DPS算法的丢包率急剧上升，远超其他算法，而RUBDPS算法继续保持了良好的性能，在4种算法中丢包率最低.这是由于DPS算法完全没有考虑用户的信道质量，在多个用户拥有相同的时延门限与队列头时延差值时，很可能选出信道条件较差的用户接受调度，而这类用户由于自身信道条件过差，即使接受调度也难以满足QoS要求或需要占用更多的资源来满足要求，而发出的数据包数量并不多，造成资源浪费，也使得大量信道质量较好的用户被闲置，从而出现大量的其他数据包被丢弃的现象. MDPS与RUBDPS算法由于在考虑时延的基础上引入了用户信道信息，所以丢包率保持在较低的水平上. RUBDPS算法由于考虑了用户在RB上的实际传输速率，更为精确地描述了用户对RB的利用能力，所以实现了最低的丢包率.
Figure 4
图 4 4种算法的丢包率对比 图 5为4种算法的吞吐量仿真结果.当K不超过40时，几种算法的吞吐量性能没有太大差别.当K继续增大时，M-LWDF算法开始展现了吞吐量优势，DPS算法由于完全忽略用户的信道质量导致吞吐量表现最差，RUBDPS算法吞吐量表现较好，相比于DPS算法有明显的改进，同时比起MDPS算法也有所提升. RUBDPS算法的吞吐量改善主要有两点原因:第一是在具体的RB上计算优先级，相比于MDPS算法中计算所有RB的平均频谱效率能更精确地表征具体RB上的信道状况；第二是引入了资源利用率概念，通过考虑实际能够获得的速率，使得需要传输较少数据的用户不会占用大量优质资源，从而使RB的分配更加合理，系统吞吐量更高.
Figure 5
图 5 4种算法的吞吐量对比 4种算法的公平性对比如图 6中所示.当系统处于轻载和中载的状况时，不同算法的公平性没有明显差距.当用户数超过70时，这种差距逐渐变得明显. M-LWDF算法由于对用户信道质量的考量权重较大，所以相应地公平性下降最快，DPS算法设计的初衷并非提升公平性，但是由于其不考虑用户信道质量，所以表现出了较高的公平性，这种公平性是以低吞吐量为代价的. RUBDPS算法加入了对信道质量的考虑，相比于M-LWDF算法，牺牲了一部分吞吐量，但是换来了公平性的提升.相比于MDPS，RUBDPS算法由于加入了实际剩余比特数目的限制，避免了资源的浪费，使得资源分配更合理，公平性更好一些.
Figure 6
图 6 4种算法的公平性 4 结论1) 当用户数较多(大于60)时，RUBDPS算法拥有最低的丢包率，不仅有效克服了DPS算法在重载条件下丢包率急剧增加的缺点，而且相比于MDPS算法也有所提升，整体性能持久稳定.
2) 在吞吐量方面，RUBDPS算法引入了资源利用率来描述用户对RB的实际利用能力，同时算法在每个具体的RB上计算优先级，因此使得优质资源更多地分配给数据传输需求较高的用户，实现了吞吐量改进，在用户数大于50时，其吞吐量表现一直好于DPS和MDPS算法.
3) 在公平性方面，RUBDPS算法在重载条件下好于MDPS算法和M-LWDF算法，虽然稍差于DPS算法，但是整体公平性依然较好，同时算法的综合性能十分优秀.
4) RUBDPS算法在吞吐量、公平性和丢包率之间达到了一个良好的均衡点，既能保证实时业务的时延需求，又能保证系统整体的吞吐量和公平性，为下行实时业务的调度提供了一种可行的办法.
参考文献
[1] LIM C, YOO T, CLERCKX B, et al. Recent trend of multiuser MIMO in LTE-advanced[J]. IEEE Communications Magazine, 2013, 51(3): 127-135. DOI:10.1109/MCOM.2013.6476877
[2] SAHOO B P S, PUTHAL D, SWAIN S, et al. A comparative analysis of packet scheduling schemes for multimedia services in LTE networks[C]//International Conference on Computational Intelligence and Networks (CINE). Bhubaneshwar: IEEE, 2015: 110-115.
[3] 孙瑨. TD-LTE无线资源调度算法的研究[D]. 哈尔滨: 哈尔滨工业大学, 2012. http://cdmd.cnki.com.cn/Article/CDMD-10213-1013036191.htm
[4] OSTERBO O. Scheduling and capacity estimation in LTE[C]//International Teletraffic Congress (ITC). San Francisco: ACM, 2011: 63-70.
[5] ITURRALDE M, ALI YAHIYA T, WEI A, et al. Performance study of multimedia services using virtual token mechanism for resource allocation in LTE networks[C]//IEEE Vehicular Technology Conference (VTC Fall). San Francisco: IEEE, 2011: 1-5.
[6] SANDRASEGARAN K, RAMLI H A M, BASUKALA R. Delay-prioritized scheduling (DPS) for real time traffic in 3GPP LTE system[C]//Wireless Communications and Networking Conference (WCNC). Sydney: IEEE, 2010: 1-6.
[7] 吴宣利, 韩杏玲, 赵婉君. LTE系统中一种低丢包率的实时业务调度算法[J]. 哈尔滨工业大学学报, 2015, 47(3): 24-28. DOI:10.11918/j.issn.0367-6234.2015.03.004
[8] SESIA S, TOUFIK I, BAKER M. LTE-the UMTS long term evolution:from theory to practice[M]. New York: John Wiley & Sons, 2009.
[9] PEDERSEN K I, KOLDING T E, FREDERIKSEN F, et al. An overview of downlink radio resource management for UTRAN long-term evolution[J]. IEEE Communications Magazine, 2009, 47(7): 86-93. DOI:10.1109/MCOM.2009.5183477
