(灵碧曰：全局公平的自适应比例公平调度，是什么？实在弄不懂。文中公式图表太多，统统丢失。请阅读原文，这里仅作推广。)
{详见：GB/T 7714
李钊，贾文浩，白玉娇.全局公平的自适应比例公平调度[J].西安电子科技大学学报， 2018，第45卷(1):6-11，22.
MLA
李钊，贾文浩， and 白玉娇.“全局公平的自适应比例公平调度.“西安电子科技大学学报第45卷.1(2018):6-11，22.
APA
李钊，贾文浩，&白玉娇.(2018).全局公平的自适应比例公平调度.西安电子科技大学学报，第45卷，(1)， 6-11，22.}
全局公平的自适应比例公平调度
李钊，贾文浩，白玉娇
(西安电子科技大学综合业务网理论及关键技术国家重点实验室，陕西西安 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 Sg，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．基站采用波束成形(BeamF， BF)的方式向每个用户发送1路数据且时隙同步．简单起见，以下讨论中?NR=1，但所提方法也适用于?NR>1 的情况．
图1中用Hk表示BS与下标为k的用户之间的信道矩阵，其元素相互独立且服从复高斯分布．基站与用户间的信道满足频率平坦衰落和块衰落(Blog)特性，即信道系数在1个传输块(包含连续若干个传输周期)内保持稳定，在块与块之间随机变化．在1个传输周期Ts内，基站首先向用户发送训练序列，各个用户能够准确估计信道，并通过一个低速的无差错链路向基站反馈信道质量信息(el Quality Information，CQI)．基站获取用户反馈的CQI后，调度一组用户，然后进行下行数据传输．
2 传统PF调度算法的公平性分析
基站向已选用户集S中的K个用户同时发送数据，用户k(k∈S)接收到的信号为
?
(1)
其中，sj和pj∈T×1分别为BS发送给MSj的符号以及所采用的预编码向量(j∈S?且?j≠k)，满足?表示求数学期望．等式右端前两项分别表示用户k的期望信号和基站向其他用户传输导致的干扰．nk是零均值、方差为?的加性高斯白噪声．
对Hk进行奇异值分解?其中λk，1为Hk的非零奇异值；0NT-1∈?T-1)，表示零向量??和??分别由λk，1和0NT-1对应的右奇异向量构成；(·)H表示共轭转置．设置预编码向量?接收滤波系数fk为?，(·)*表示共轭，代入式(1)，可得
?
(2)
其中，?由于uk的模值为?的方差仍为?．
基站采用等功率分配，PT平均分配到各个用户的波束上，每个波束的发射功率?P0=?PT/?NT．MSk的信干噪比?γk=?P0?/(?+?k)，其中，?表示BS向其他用户j?(j∈S，j≠k)的传输对用户k造成的干扰．MSk的可达数据速率?Rk= lb(1+?γk)，系统的和速率?
PF调度算法在用户公平性与系统吞吐量之间进行折中，其调度优先级计算公式为
?
(3)
其中，Rk(t)表示用户k在时隙t的瞬时数据速率，?为用户k从初始时刻到时隙?t-1 区间的平均速率．基站在时隙t选择优先级ρk(t)最大的前K个用户组成调度用户集S．在?t+1 时隙，PF调度算法按照下式更新各个用户的平均速率:
?
(4)
其中，α=1/Tc，称为遗忘因子，Tc是时间窗口参数，Tc越大，用户的平均速率更新越缓慢，?信道质量差的用户需要等待更长的时间才能获得调度，一般取?α= 0.01，见文献[7]．
以下对传统PF调度算法的公平性进行分析．以时隙t0作为一段观测区间的起点，全体用户的初始?设置为相等的较小常数(以确保获得调度的用户在?t0+1 时隙的平均速率大于其初始平均速率)，此时MSk的调度优先级ρk(t0)仅由其信道质量决定．为了简便，以?L=2，基站在每个时隙调度1个用户的情况为例进行讨论．假设?R1(t0)>?R2(t0)，即?ρ1(t0)>?ρ2(t0)，MS1首先被调度．下一时隙的平均速率更新为?和?基站在时隙?t0+1 重新计算用户的调度优先级，调度?ρk(t0+1)大的用户．假设?t0+?tp1时隙?ρ2(t0+?tp1)>?ρ1(t0+?tp1)，MS2首次得到调度，由系统模型及式(3)和式(4)可得
?
(5)
?
图2 用户优先级变化示意图(L=2)
根据式(5)，MS2在经过tp1=log1-α?[??(t0)-?(t0)+1]-1个时隙后，获得调度．tp1取决于MS1和MS2的初始信道质量以及遗忘因子α．给定ρ1(t0)ρ2(t0)，MS1和MS2的初始信道质量差距越大(导致?ρ1(t0)-?ρ2(t0)越大)，α越小，则tp1越大．根据以上分析，图2给出两个MS的调度优先级随时间变化的示意图．从时隙t0开始，在接下来的tp1个时隙内，PF调度算法始终调度MS1．MS1和MS2的调度权重分别减小和增大，经过tp1个时隙，二者的调度优先级接近，MS1和MS2交替得到调度．若以mtp1(m为正整数)个时隙作为观测区间，当m较小时(短期观测)，系统公平性差;当m的取值足够大时(长期观测)，公平性改善．因此，对于信道质量差的用户，当其进入系统时间较短，或者在系统中短暂停留时，PF调度算法无法保证其及时地得到调度．为了获得全局公平性的改善，应设法减小tp1．
由于初始时隙t0的选取可以是任意的，可以用任意时隙t代替t0，表示从时隙t开始，经过tp1个时隙后，信道质量差的用户首次得到调度．根据t时隙L个用户调度优先级的方差?当?L=2 时，ξ(t)= 0.5[ρ1(t)-?ρ2(t)]2，可得?ρ1(t)=?ρ2(t)±(2ξ(t))1/2，代入tp1的表达式进行化简，可得
?
(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)如下:
?