(靈碧曰：全局公平的自適應比例公平調度，是什麼？實在弄不懂。文中公式圖表太多，統統丟失。請閱讀原文，這裏僅作推廣。)
{詳見：GBT7714
李釗，賈文浩，白玉嬌.全局公平的自適應比例公平調度[J].西安電子科技大學學報，2018，第45卷(1):6-11，22.
MLA
李釗，賈文浩，and白玉嬌.“全局公平的自適應比例公平調度.“西安電子科技大學學報第45卷.1(2018):6-11，22.
APA
李釗，賈文浩，白玉嬌.(2018).全局公平的自適應比例公平調度.西安電子科技大學學報，第45卷，(1)，6-11，22.}
全局公平的自適應比例公平調度
李釗，賈文浩，白玉嬌
(西安電子科技大學綜合業務網理論及關鍵技術國家重點實驗室，陝西西安)
摘要：?傳統的比例公平調度通過犧牲係統的速率性能獲得公平性，但該公平性具有“長期”的特點，無法保證進入係統時間較短或在係統中短暫停留的用戶的公平性，具有實時業務的用戶的時延需求也難以滿足．針對以上問題，提出一種全局公平的自適應比例公平調度算法．基站根據全體用戶的調度優先級的離散程度，動態調整比例公平算法中的遺忘因子，進而影響用戶調度權重的更新．仿真結果表明，與傳統的比例公平調度算法相比，自適應比例公平調度算法能夠兼顧長期和短期公平性以及係統的和速率，並且能為用戶業務保證良好的時延性能．
關鍵詞：?用戶調度;比例公平;自適應;時延
隨著移動設備數量的急劇增長和多媒體業務的快速發展，人們對數據速率和服務質量的要求不斷提高，選取適當的調度算法將有限的通信資源動態分配給用戶、滿足用戶的通信需求並使資源得到高效的利用更顯重要．常見的調度算法包括最大吞吐量(MaximumThroughput，MT)、輪詢(RoundRobin，RR)和比例公平(ProportionalFair，PF)調度算法等．PF調度算法選擇調度優先級(由瞬時信道質量與平均信道質量的比值決定)高的用戶，兼顧係統吞吐量和用戶間公平性，在實際中得到了廣泛應用．PF調度算法能夠獲得長期的公平性，即在一段較長的觀測區間內保證各個用戶的調度概率接近．但是，當觀測區間較短時，PF調度算法無法保證良好的(短期)公平性[1]．此外，由於無線通信係統的動態特征，對於那些進入係統時間較短或在係統中短暫停留的用戶，PF調度算法無法保證其公平性．另一方麵，實時性要求高的用戶有更嚴格的時延需求，PF調度算法在追求長期公平性的同時，缺乏對用戶業務時延的保證，可能會造成用戶數據堆存和連接中斷[2]．因此，對於無線通信係統，用戶的短期公平性與長期公平性同等重要，並且在獲得全局(長期和短期)公平性的同時，還應保證良好的係統吞吐量與時延特性．
為了實現上述目標，一係列改進的PF調度算法被提出．在改善公平性方麵，文獻[3]提出一種自適應PF調度算法，按照用戶的調度優先級與預設控製係數的乘積進行用戶選擇，當用戶的優先級與所有用戶優先級的平均值的差值高於某一門限時，控製係數減去一常量，否則增加該常量，以此更好地保證非實時業務的公平性．文獻[4]對PF調度算法的調度優先級計算公式進行改造，通過提高信道質量差的用戶的優先級，降低信道質量好的用戶的優先級，增加前者的調度機會，改善公平性．但計算優先級時引入了指數運算，導致了複雜度的增加．針對有時延要求的實時業務，文獻[5]提出一種改進的最大加權時延優先(ModifiedLargestWeightedDelayFirst，M-LWDF)調度算法，通過在PF調度算法的優先級計算公式中加入對隊列分組等待時延的考慮，使優先級隨時延線性增長，但忽略了實時業務的時延約束，導致用戶數據包容易因超時而被丟棄．文獻[6]設計一種延遲優先調度(Delay-PrioritizedScheduling，DPS)算法，該算法在每個調度時刻計算用戶等待時間與其時延容限的差值，選擇差值最小的用戶進行通信，能夠較好地滿足用戶的時延需求，但在計算優先級時隻考慮了用戶的時延狀況，忽視了信道質量的影響，導致係統的吞吐量降低．上述工作雖然在改善PF調度算法的公平性[3-4]和業務時延[5-6]方麵分別進行了研究，但缺少對係統的長期和短期公平性，以及用戶時延的綜合考慮．此外，文獻[3-6]需要係統針對每個用戶單獨維護控製參數(常量、門限等)，複雜度高且開銷較大，實際中控製參數的合理取值也存在困難．
綜上，文中在承載實時與非實時業務的蜂窩通信係統中，針對傳統的PF調度算法無法保證用戶的短期公平性，以及用戶的時延需求難以滿足的問題，提出一種實現全局公平的自適應比例公平(AdaptiveProportionalFair，APF)調度算法，基站根據係統中全體用戶的調度優先級(權重)的離散程度，動態調整PF調度算法中的遺忘因子，從而影響用戶的調度權重更新，實現長期和短期公平性以及係統速率的兼顧，並為實時業務用戶提供良好的時延保證．
1係統模型
?
圖1係統模型
研究單小區多用戶多輸入多輸出(Multiple-InputMultiple-Output，MIMO)下行廣播信道，包括一個配置NT根天線的基站(BaseStation，BS)和L個配置NR根天線的用戶(MobileStation，MS)，且?L?NT，基站發射功率為PT．基站能夠同時發送的空域上可分離的數據流個數不超過NT．在1個傳輸周期(長度為Ts)內，BS調度K?(K≤NT)個MS發送數據，用A表示候選用戶集合，|A|=L，用S表示已選用戶集，|S|=K．基站采用波束成形(BeamForming，BF)的方式向每個用戶發送1路數據且時隙同步．簡單起見，以下討論中?NR=1，但所提方法也適用於?NR1的情況．
圖1中用Hk表示BS與下標為k的用戶之間的信道矩陣，其元素相互獨立且服從複高斯分布．基站與用戶間的信道滿足頻率平坦衰落和塊衰落(BlockFading)特性，即信道係數在1個傳輸塊(包含連續若幹個傳輸周期)內保持穩定，在塊與塊之間隨機變化．在1個傳輸周期Ts內，基站首先向用戶發送訓練序列，各個用戶能夠準確估計信道，並通過一個低速的無差錯鏈路向基站反饋信道質量信息(ChannelQualityInformation，CQI)．基站獲取用戶反饋的CQI後，調度一組用戶，然後進行下行數據傳輸．
2傳統PF調度算法的公平性分析
基站向已選用戶集S中的K個用戶同時發送數據，用戶k(k∈S)接收到的信號為
?
(1)
其中，sj和pj∈CNT×1分別為BS發送給MSj的符號以及所采用的預編碼向量(j∈S?且?j≠k)，滿足?表示求數學期望．等式右端前兩項分別表示用戶k的期望信號和基站向其他用戶傳輸導致的幹擾．nk是零均值、方差為?的加性高斯白噪聲．
對Hk進行奇異值分解?其中λk，1為Hk的非零奇異值；0NT-1∈?C1×(NT-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)
其中，α=1Tc，稱為遺忘因子，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．