全局公平的自适应比例公平调度

李 钊， 贾文浩， 白玉娇

(西安电子科技大学 综合业务网理论及关键技术国家重点实验室，陕西 西安 710071)

全局公平的自适应比例公平调度

李 钊， 贾文浩， 白玉娇

(西安电子科技大学 综合业务网理论及关键技术国家重点实验室，陕西 西安 710071)

传统的比例公平调度通过牺牲系统的速率性能获得公平性，但该公平性具有“长期”的特点，无法保证进入系统时间较短或在系统中短暂停留的用户的公平性，具有实时业务的用户的时延需求也难以满足．针对以上问题，提出一种全局公平的自适应比例公平调度算法．基站根据全体用户的调度优先级的离散程度，动态调整比例公平算法中的遗忘因子，进而影响用户调度权重的更新．仿真结果表明，与传统的比例公平调度算法相比，自适应比例公平调度算法能够兼顾长期和短期公平性以及系统的和速率，并且能为用户业务保证良好的时延性能．

用户调度;比例公平;自适应;时延

随着移动设备数量的急剧增长和多媒体业务的快速发展，人们对数据速率和服务质量的要求不断提高，选取适当的调度算法将有限的通信资源动态分配给用户、满足用户的通信需求并使资源得到高效的利用更显重要．常见的调度算法包括最大吞吐量(Maximum Throughput， MT)、轮询(Round Robin， RR)和比例公平(Proportional Fair， PF)调度算法等．PF调度算法选择调度优先级(由瞬时信道质量与平均信道质量的比值决定)高的用户，兼顾系统吞吐量和用户间公平性，在实际中得到了广泛应用．PF调度算法能够获得长期的公平性，即在一段较长的观测区间内保证各个用户的调度概率接近．但是，当观测区间较短时，PF调度算法无法保证良好的(短期)公平性[1]．此外，由于无线通信系统的动态特征，对于那些进入系统时间较短或在系统中短暂停留的用户，PF调度算法无法保证其公平性．另一方面，实时性要求高的用户有更严格的时延需求，PF调度算法在追求长期公平性的同时，缺乏对用户业务时延的保证，可能会造成用户数据堆存和连接中断[2]．因此，对于无线通信系统，用户的短期公平性与长期公平性同等重要，并且在获得全局(长期和短期)公平性的同时，还应保证良好的系统吞吐量与时延特性．

为了实现上述目标，一系列改进的PF调度算法被提出．在改善公平性方面，文献[3]提出一种自适应PF调度算法，按照用户的调度优先级与预设控制系数的乘积进行用户选择，当用户的优先级与所有用户优先级的平均值的差值高于某一门限时，控制系数减去一常量，否则增加该常量，以此更好地保证非实时业务的公平性．文献[4]对PF调度算法的调度优先级计算公式进行改造，通过提高信道质量差的用户的优先级，降低信道质量好的用户的优先级，增加前者的调度机会，改善公平性．但计算优先级时引入了指数运算，导致了复杂度的增加．针对有时延要求的实时业务，文献[5]提出一种改进的最大加权时延优先(Modified Largest Weighted Delay First，M-LWDF)调度算法，通过在PF调度算法的优先级计算公式中加入对队列分组等待时延的考虑，使优先级随时延线性增长，但忽略了实时业务的时延约束，导致用户数据包容易因超时而被丢弃．文献[6]设计一种延迟优先调度(Delay-Prioritized Scheduling，DPS)算法，该算法在每个调度时刻计算用户等待时间与其时延容限的差值，选择差值最小的用户进行通信，能够较好地满足用户的时延需求，但在计算优先级时只考虑了用户的时延状况，忽视了信道质量的影响，导致系统的吞吐量降低．上述工作虽然在改善PF调度算法的公平性[3-4]和业务时延[5-6]方面分别进行了研究，但缺少对系统的长期和短期公平性，以及用户时延的综合考虑．此外，文献[3-6]需要系统针对每个用户单独维护控制参数(常量、门限等)，复杂度高且开销较大，实际中控制参数的合理取值也存在困难．

综上，文中在承载实时与非实时业务的蜂窝通信系统中，针对传统的PF调度算法无法保证用户的短期公平性，以及用户的时延需求难以满足的问题，提出一种实现全局公平的自适应比例公平(Adaptive Proportional Fair， APF)调度算法，基站根据系统中全体用户的调度优先级(权重)的离散程度，动态调整PF调度算法中的遗忘因子，从而影响用户的调度权重更新，实现长期和短期公平性以及系统速率的兼顾，并为实时业务用户提供良好的时延保证．

1 系统模型

图1 系统模型

研究单小区多用户多输入多输出(Multiple-Input Multiple-Output，MIMO)下行广播信道，包括一个配置NT根天线的基站(Base Station， BS)和L个配置NR根天线的用户(Mobile Station， MS)，且L>NT，基站发射功率为PT．基站能够同时发送的空域上可分离的数据流个数不超过NT．在1个传输周期(长度为Ts)内，BS调度K(K≤NT) 个MS发送数据，用A表示候选用户集合，|A|=L，用S表示已选用户集，|S|=K．基站采用波束成形(BeamForming， BF)的方式向每个用户发送1路数据且时隙同步．简单起见，以下讨论中NR=1，但所提方法也适用于NR>1 的情况．

图1中用Hk表示BS与下标为k的用户之间的信道矩阵，其元素相互独立且服从复高斯分布．基站与用户间的信道满足频率平坦衰落和块衰落(Block Fading)特性，即信道系数在1个传输块(包含连续若干个传输周期)内保持稳定，在块与块之间随机变化．在1个传输周期Ts内，基站首先向用户发送训练序列，各个用户能够准确估计信道，并通过一个低速的无差错链路向基站反馈信道质量信息(Channel Quality Information，CQI)．基站获取用户反馈的CQI后，调度一组用户，然后进行下行数据传输．

2 传统PF调度算法的公平性分析

基站向已选用户集S中的K个用户同时发送数据，用户k(k∈S)接收到的信号为

(1)

(2)

PF调度算法在用户公平性与系统吞吐量之间进行折中，其调度优先级计算公式为

(3)

(4)

(5)

图2 用户优先级变化示意图(L=2)

(6)

根据式(6)，给定ρ2(t)和ξ(t)，增大α(α∈(0，1))可以减小tp1．扩展至L个用户的情况，给定时隙t全体用户调度优先级的方差ξ(t)，α决定tp1的大小，α越大，tp1越小，各用户的调度权重相互接近的速度越快，公平性越好．

3 自适应PF调度算法

根据上一节的讨论，遗忘因子α越大，用户优先级的方差ξ(t)则以较快的速度减小，因此可以构造函数α(t)=f[ξ(t)]，使α(t)随ξ(t)自适应变化，实现全局公平性和系统速率的兼顾．如图2虚线所示，当ξ(t)较大时，设置较大的α(t)，加快用户优先级接近速度，以获得好的短期公平性; 当ξ(t)较小时，设置较小的α(t)，使信道质量好的用户得到更多调度机会，保证好的速率性能．

由于在实际应用中遗忘因子常取0.01，文中以αref=0.01为基准对α(t)进行动态调整．又因为α(t)随着ξ(t)的增加而增大，若将α(t)视为信号的幅度衰减，则ξ(t)相当于频率，α(t)=f[ξ(t)]，符合低通特性．由于巴特沃斯是一种典型的低通滤波器，参考其函数特性，根据ξ(t)动态调整α(t)如下:

(7)

因为α(t)随着ξ(t)单调递增，为了避免当ξ(t)→0时，α(t)→0，即所有用户的平均信道质量趋于恒定值，从而导致用户的调度权重仅由用户当前的信道质量决定，自适应PF(APF)成为最大吞吐量(MT)调度，信道质量差的用户将长时间得不到调度，则需要设置一个较小的正数ε保证α(t)≠0，使用户的平均信道质量在每个时隙都经历变化，以维护系统的公平性．N(t)是ξ(t)的阶数，当N(t)=0 时，α(t)=αref= 0.01，此时APF成为传统的PF．

阶数N(t)越大，ξ(t)向0收敛越快，系统的短期公平性越好．但根据式(7)，N(t)越大，α(t)→0 的速度越快，若α(t)→0，所有用户的调度优先级将趋于恒定，导致调度集合趋于固定，即一部分用户始终得不到调度，从而使公平性下降．所以，设计N(t)为ξ(t)的单调递增函数如下:

N(t)=g[ξ(t)]=ξ(t)+τ,

(8)

其中，τ是一个接近0的正数，保证N(t)≠0．APF在ξ(t)>1时，N(t)>1，并且N(t)随ξ(t)的增大而单调递增，从而得到大的α(t)，加速各用户优先级的汇聚(即ξ(t)→0)，实现短期公平; 当ξ(t)<1 时，N(t)<1，并且N(t)随ξ(t)的减小而降低，从而减慢α(t)→0 的速度，保证长期公平性．

步骤1 MSk估计信道状态, 并向基站反馈其信道质量qk(t)．

步骤2 基站根据式(3)计算MSk的调度优先级ρk(t)，并调度优先级最大的前K个用户进行数据发送．

4 仿真结果

图3为遗忘因子α(t)对PF调度算法的影响进行的仿真．图3(a)和图3(b)给出某次按Dent模型产生L=10 个用户信道，在连续100个时隙中这10个用户的调度权重的变化情况．如图3(a)所示，信道质量好的用户(如用户8和用户10)较早地得到调度，它们的优先级随之下降; 信道质量差的用户(如用户1和用户9)则需要等待较长时间才能够获得调度．经过足够长的时间(约40个时隙)后，由图3(a)放大部分可以看到，所有用户优先级接近，高低关系交替变化，即用户将公平地获得调度机会．图3(b)表现出的整体规律与图3(a)相似，但由于将α(t)增加至0.05，使信道质量好的用户在被调度后，调度优先级的降幅增加，相应的信道质量差的用户的优先级增幅加大，从而使系统中用户的调度优先级经过较短的时间(约10个时隙)便相互接近，即各用户达到公平状态．

图3 遗忘因子对PF调度算法的影响

图4给出不同算法的和速率性能．对于传统的PF调度算法 (N(t)=0，代入式(7)，可得α(t)=αref= 0.01)，随着时间的增加，系统的和速率下降．采用APF调度算法，在开始的一段时间内(约20个时隙)，由于用户优先级的离散程度较高，遗忘因子α(t)较大，因此信道质量差的用户不需要等待很久便得到调度，导致系统的和速率低于传统PF调度算法的．随着时间继续增加(约30时隙后)，用户优先级逐渐接近，APF调度算法使α(t)自适应减小，因此在维持较好公平性的前提下，信道质量好的用户会获得更多的调度机会，此时APF调度算法的和速率性能优于传统PF调度算法的．采用QAPF调度算法，当ξ(t)>1 时，N(t)越大，则α(t)越大，在起始阶段，对用户优先级调整的程度越大，导致系统的和速率降低; 随着用户优先级逐渐接近，当ξ(t)<1 时，N(t)越大，则α(t)越小，信道质量好的用户得到更多调度机会，系统的和速率提高．对于APF调度算法，在起始阶段N(t)较大，通过牺牲一部分系统速率获得更好的短期公平，当用户优先级逐渐接近，N(t)的取值减小，即在保证较好的公平性的前提下对速率有一定改善．

图5对算法的公平性进行仿真．基站在10个用户中调度4个用户，由Jain’s公平性指数的计算公式，得到所有调度算法公平性指数初始值均为0.4．如图5所示，当N(t)较大时，公平性在经过较短的时间即可获得改善(如公平性指数达到0.5)．在起始阶段(约20时隙)，用户优先级离散程度较大，相比于传统PF调度算法，APF调度算法通过选择较大的遗忘因子，可以获得好的短期公平性; 经过一段时间后(约40时隙)，用户优先级离散程度降低，APF调度算法的公平性劣于α= 0.01的PF调度算法的，即APF调度算法牺牲一定的公平性以换取系统和速率的改善(如图4所示)．QAPF调度算法对α(t)的取值的情况与图4的分析相同，N(t)越大，在起始阶段的公平性改善越显著，但随着时间的推移，用户优先级逐渐接近，公平性逐渐劣于N(t)较小的QAPF调度算法的．与QAPF调度算法相比，APF调度算法的全局公平性更好．综合图4和图5可以发现，APF调度算法牺牲了一定的系统速率，但公平性得到了改善．

图4 系统的和速率性能图5 公平性指数

图6 系统平均等待时延

如图6所示，随着用户数的增加，网络负载加重，系统平均等待时延随之增加．由于传统的PF调度算法固定遗忘因子的取值，ΓPF随L的增加而线性增大．当L较小时，ΓAPF与ΓPF接近; 当L较大时，ΓAPF小于ΓPF．这是因为用户数L较小时，所有用户的优先级在短时间内接近，之后，APF调度算法会给信道质量好的用户更多调度机会，系统平均等待时延较高; 当L较大时，所有用户优先级需要经过较长时间才能接近，APF调度算法给信道质量差的用户更多调度机会，系统平均等待时延较低．QAPF调度算法通过设置非零的阶数使公平性在较短时间内得到改善，但牺牲了起始阶段(约30时隙)的时延性能，虽然此后QAPF调度算法的等待时延优于传统PF调度算法的，但仍劣于APF调度算法的．

5 结 束 语

文中在承载实时与非实时业务的蜂窝通信系统中，针对传统的PF调度算法无法保证用户的短期公平性，以及用户的时延需求难以满足的问题，提出一种实现全局公平的自适应比例公平调度算法，在每个时隙，

基站根据系统中全体用户的调度权重的离散程度，动态调整PF调度算法中的遗忘因子，从而影响用户的调度优先级的更新，实现长期和短期公平性以及系统速率的兼顾，并为实时业务用户提供良好的时延保证．

参考文献：

[1] MISHRA A, VENKITASUBRAMANIAM P. Anonymity and Fairness in Packet Scheduling: a Quantitative Tradeoff[J]. IEEE/ACM Transactions on Networking, 2016, 24(2): 688-702.

[2] ZHAO Y X, ZHANG B X, WANG L, et al. Selective Redundant Transmissions for Real-time Video Streaming over Multi-interface Wireless Terminals[C]//Proceedings of the 2016 IEEE Global Communications Conference. Piscataway: IEEE, 2016: 7842256.

[3] REBEKKA B, SUDHEEP S, MALARKODI B. An Optimal and Priority Based Rate Guaranteed Radio Resource Allocation Scheme for LTE Downlink[J]. Wireless Personal Communications, 2015, 83(3): 1643-1661.

[4] ANDREWS M, KUMARAN K, RAMANAN K, et al. Providing Quality of Service over a Shared Wireless Link[J]. IEEE Communications Magazine, 2001, 39(2): 150-153.

[5] SANDRASEGARAN K, RAMLI H A M, BASUKALA R. Delay-prioritized Scheduling (DPS) for Real Time Traffic in 3GPP LTE System[C]//Proceedings of the IEEE Wireless Communication and Networking Conference. Piscataway: IEEE, 2010: 5506251.

[6] GUPTA N, JAGANNATHAM A K. Multiuser Successive Maximum Ratio Transmission (MS-MRT) for Video Quality Maximization in Unicast and Broadcast MIMO OFDMA-based 4G Wireless Networks[J]. IEEE Transactions on Vehicular Technology, 2014, 63(7): 3147-3156.

[7] CHOI J G, BAHK S. Cell-throughput Analysis of the Proportional Fair Scheduler in the Single-cell Environment[J]. IEEE Transactions on Vehicular Technology, 2007, 56(2): 766-778.

[8] ZHANG G P, LI A, YANG K, et al. Energy-efficient Power and Time-slot Allocation for Cellular-enabled Machine Type Communications[J]. IEEE Communications Letters, 2016, 20(2): 368-371.

[9] 3GPP. 3rd Generation Partnership Project; Technical Specification Group Radio Access Network; Evolved Universal Terrestrial Radio Access (E-UTRA); Radio Frequency (RF) Requirements for LTE Pico Node B (Release 13): TR 36.931 Release 13[S]. Valbonne: 3GPP, 2016.

Adaptiveproportionalfairschedulingwithglobal-fairness

LIZhao，JIAWenhao，BAIYujiao

(State Key Lab. of Integrated Service Networks, Xidian Univ., Xi’an 710071, China)

Conventional proportional fair (PF) scheduling achieves fairness at the cost of the system’s rate performance. Such fairness is characterized by long-term, and hence cannot guarantee the fairness of subscribers who enter the system temporarily or stay for just a short period of time. In addition, the delay requirement of real-time service users can hardly be met. In order to remedy the above problems, we propose an adaptive proportional fair (APF) scheduling algorithm with global-fairness. The base station dynamically adjusts the forgetting factor in the PF algorithm based on the degree of dispersion of all the users’ scheduling priorities so as to influence the update of users’ scheduling weights. Simulation results show that compared to conventional PF scheduling, the APF can achieve both the long-term and short-term fairness and high system sum-rate, and additionally guarantee good delay performance for users’ service.

user scheduling; proportional fair; adaptive; time delay

2017-01-08

时间：2017-06-29

高等学校引智计划基金资助项目(B16037, B08038)； 国家自然科学基金资助项目(61401354, 61401320, 61501285)

李 钊(1981-)，男，副教授，博士，E-mail: zli@xidian.edu.cn．

http://kns.cnki.net/kcms/detail/61.1076.TN.20170629.1734.004.html

10.3969/j.issn.1001-2400.2018.01.002

TN929.5

A

1001-2400(2018)01-0006-06

(编辑： 齐淑娟)