全局公平的自適應比例公平調度

李 釗， 賈文浩， 白玉嬌

(西安電子科技大學 綜合業務網理論及關鍵技術國家重點實驗室，陜西 西安 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

(編輯： 齊淑娟)