李 釗， 賈文浩， 白玉嬌

(西安電子科技大學 綜合業(yè)務網(wǎng)理論及關鍵技術國家重點實驗室，陜西 西安 710071)

全局公平的自適應比例公平調(diào)度

李 釗， 賈文浩， 白玉嬌

(西安電子科技大學 綜合業(yè)務網(wǎng)理論及關鍵技術國家重點實驗室，陜西 西安 710071)

傳統(tǒng)的比例公平調(diào)度通過犧牲系統(tǒng)的速率性能獲得公平性，但該公平性具有“長期”的特點，無法保證進入系統(tǒng)時間較短或在系統(tǒng)中短暫停留的用戶的公平性，具有實時業(yè)務的用戶的時延需求也難以滿足．針對以上問題，提出一種全局公平的自適應比例公平調(diào)度算法．基站根據(jù)全體用戶的調(diào)度優(yōu)先級的離散程度，動態(tài)調(diào)整比例公平算法中的遺忘因子，進而影響用戶調(diào)度權重的更新．仿真結(jié)果表明，與傳統(tǒng)的比例公平調(diào)度算法相比，自適應比例公平調(diào)度算法能夠兼顧長期和短期公平性以及系統(tǒng)的和速率，并且能為用戶業(yè)務保證良好的時延性能．

用戶調(diào)度;比例公平;自適應;時延

隨著移動設備數(shù)量的急劇增長和多媒體業(yè)務的快速發(fā)展，人們對數(shù)據(jù)速率和服務質(zhì)量的要求不斷提高，選取適當?shù)恼{(diào)度算法將有限的通信資源動態(tài)分配給用戶、滿足用戶的通信需求并使資源得到高效的利用更顯重要．常見的調(diào)度算法包括最大吞吐量(Maximum Throughput， MT)、輪詢(Round Robin， RR)和比例公平(Proportional Fair， PF)調(diào)度算法等．PF調(diào)度算法選擇調(diào)度優(yōu)先級(由瞬時信道質(zhì)量與平均信道質(zhì)量的比值決定)高的用戶，兼顧系統(tǒng)吞吐量和用戶間公平性，在實際中得到了廣泛應用．PF調(diào)度算法能夠獲得長期的公平性，即在一段較長的觀測區(qū)間內(nèi)保證各個用戶的調(diào)度概率接近．但是，當觀測區(qū)間較短時，PF調(diào)度算法無法保證良好的(短期)公平性[1]．此外，由于無線通信系統(tǒng)的動態(tài)特征，對于那些進入系統(tǒng)時間較短或在系統(tǒng)中短暫停留的用戶，PF調(diào)度算法無法保證其公平性．另一方面，實時性要求高的用戶有更嚴格的時延需求，PF調(diào)度算法在追求長期公平性的同時，缺乏對用戶業(yè)務時延的保證，可能會造成用戶數(shù)據(jù)堆存和連接中斷[2]．因此，對于無線通信系統(tǒng)，用戶的短期公平性與長期公平性同等重要，并且在獲得全局(長期和短期)公平性的同時，還應保證良好的系統(tǒng)吞吐量與時延特性．

為了實現(xiàn)上述目標，一系列改進的PF調(diào)度算法被提出．在改善公平性方面，文獻[3]提出一種自適應PF調(diào)度算法，按照用戶的調(diào)度優(yōu)先級與預設控制系數(shù)的乘積進行用戶選擇，當用戶的優(yōu)先級與所有用戶優(yōu)先級的平均值的差值高于某一門限時，控制系數(shù)減去一常量，否則增加該常量，以此更好地保證非實時業(yè)務的公平性．文獻[4]對PF調(diào)度算法的調(diào)度優(yōu)先級計算公式進行改造，通過提高信道質(zhì)量差的用戶的優(yōu)先級，降低信道質(zhì)量好的用戶的優(yōu)先級，增加前者的調(diào)度機會，改善公平性．但計算優(yōu)先級時引入了指數(shù)運算，導致了復雜度的增加．針對有時延要求的實時業(yè)務，文獻[5]提出一種改進的最大加權時延優(yōu)先(Modified Largest Weighted Delay First，M-LWDF)調(diào)度算法，通過在PF調(diào)度算法的優(yōu)先級計算公式中加入對隊列分組等待時延的考慮，使優(yōu)先級隨時延線性增長，但忽略了實時業(yè)務的時延約束，導致用戶數(shù)據(jù)包容易因超時而被丟棄．文獻[6]設計一種延遲優(yōu)先調(diào)度(Delay-Prioritized Scheduling，DPS)算法，該算法在每個調(diào)度時刻計算用戶等待時間與其時延容限的差值，選擇差值最小的用戶進行通信，能夠較好地滿足用戶的時延需求，但在計算優(yōu)先級時只考慮了用戶的時延狀況，忽視了信道質(zhì)量的影響，導致系統(tǒng)的吞吐量降低．上述工作雖然在改善PF調(diào)度算法的公平性[3-4]和業(yè)務時延[5-6]方面分別進行了研究，但缺少對系統(tǒng)的長期和短期公平性，以及用戶時延的綜合考慮．此外，文獻[3-6]需要系統(tǒng)針對每個用戶單獨維護控制參數(shù)(常量、門限等)，復雜度高且開銷較大，實際中控制參數(shù)的合理取值也存在困難．

綜上，文中在承載實時與非實時業(yè)務的蜂窩通信系統(tǒng)中，針對傳統(tǒng)的PF調(diào)度算法無法保證用戶的短期公平性，以及用戶的時延需求難以滿足的問題，提出一種實現(xiàn)全局公平的自適應比例公平(Adaptive Proportional Fair， APF)調(diào)度算法，基站根據(jù)系統(tǒng)中全體用戶的調(diào)度優(yōu)先級(權重)的離散程度，動態(tài)調(diào)整PF調(diào)度算法中的遺忘因子，從而影響用戶的調(diào)度權重更新，實現(xiàn)長期和短期公平性以及系統(tǒng)速率的兼顧，并為實時業(yè)務用戶提供良好的時延保證．

1 系統(tǒng)模型

圖1 系統(tǒng)模型

研究單小區(qū)多用戶多輸入多輸出(Multiple-Input Multiple-Output，MIMO)下行廣播信道，包括一個配置NT根天線的基站(Base Station， BS)和L個配置NR根天線的用戶(Mobile Station， MS)，且L>NT，基站發(fā)射功率為PT．基站能夠同時發(fā)送的空域上可分離的數(shù)據(jù)流個數(shù)不超過NT．在1個傳輸周期(長度為Ts)內(nèi)，BS調(diào)度K(K≤NT) 個MS發(fā)送數(shù)據(jù)，用A表示候選用戶集合，|A|=L，用S表示已選用戶集，|S|=K．基站采用波束成形(BeamForming， BF)的方式向每個用戶發(fā)送1路數(shù)據(jù)且時隙同步．簡單起見，以下討論中NR=1，但所提方法也適用于NR>1 的情況．

圖1中用Hk表示BS與下標為k的用戶之間的信道矩陣，其元素相互獨立且服從復高斯分布．基站與用戶間的信道滿足頻率平坦衰落和塊衰落(Block Fading)特性，即信道系數(shù)在1個傳輸塊(包含連續(xù)若干個傳輸周期)內(nèi)保持穩(wěn)定，在塊與塊之間隨機變化．在1個傳輸周期Ts內(nèi)，基站首先向用戶發(fā)送訓練序列，各個用戶能夠準確估計信道，并通過一個低速的無差錯鏈路向基站反饋信道質(zhì)量信息(Channel Quality Information，CQI)．基站獲取用戶反饋的CQI后，調(diào)度一組用戶，然后進行下行數(shù)據(jù)傳輸．

2 傳統(tǒng)PF調(diào)度算法的公平性分析

基站向已選用戶集S中的K個用戶同時發(fā)送數(shù)據(jù)，用戶k(k∈S)接收到的信號為

(1)

(2)

PF調(diào)度算法在用戶公平性與系統(tǒng)吞吐量之間進行折中，其調(diào)度優(yōu)先級計算公式為

(3)

(4)

(5)

圖2 用戶優(yōu)先級變化示意圖(L=2)

(6)

根據(jù)式(6)，給定ρ2(t)和ξ(t)，增大α(α∈(0，1))可以減小tp1．擴展至L個用戶的情況，給定時隙t全體用戶調(diào)度優(yōu)先級的方差ξ(t)，α決定tp1的大小，α越大，tp1越小，各用戶的調(diào)度權重相互接近的速度越快，公平性越好．

3 自適應PF調(diào)度算法

根據(jù)上一節(jié)的討論，遺忘因子α越大，用戶優(yōu)先級的方差ξ(t)則以較快的速度減小，因此可以構造函數(shù)α(t)=f[ξ(t)]，使α(t)隨ξ(t)自適應變化，實現(xiàn)全局公平性和系統(tǒng)速率的兼顧．如圖2虛線所示，當ξ(t)較大時，設置較大的α(t)，加快用戶優(yōu)先級接近速度，以獲得好的短期公平性; 當ξ(t)較小時，設置較小的α(t)，使信道質(zhì)量好的用戶得到更多調(diào)度機會，保證好的速率性能．

由于在實際應用中遺忘因子常取0.01，文中以αref=0.01為基準對α(t)進行動態(tài)調(diào)整．又因為α(t)隨著ξ(t)的增加而增大，若將α(t)視為信號的幅度衰減，則ξ(t)相當于頻率，α(t)=f[ξ(t)]，符合低通特性．由于巴特沃斯是一種典型的低通濾波器，參考其函數(shù)特性，根據(jù)ξ(t)動態(tài)調(diào)整α(t)如下:

(7)

因為α(t)隨著ξ(t)單調(diào)遞增，為了避免當ξ(t)→0時，α(t)→0，即所有用戶的平均信道質(zhì)量趨于恒定值，從而導致用戶的調(diào)度權重僅由用戶當前的信道質(zhì)量決定，自適應PF(APF)成為最大吞吐量(MT)調(diào)度，信道質(zhì)量差的用戶將長時間得不到調(diào)度，則需要設置一個較小的正數(shù)ε保證α(t)≠0，使用戶的平均信道質(zhì)量在每個時隙都經(jīng)歷變化，以維護系統(tǒng)的公平性．N(t)是ξ(t)的階數(shù)，當N(t)=0 時，α(t)=αref= 0.01，此時APF成為傳統(tǒng)的PF．

階數(shù)N(t)越大，ξ(t)向0收斂越快，系統(tǒng)的短期公平性越好．但根據(jù)式(7)，N(t)越大，α(t)→0 的速度越快，若α(t)→0，所有用戶的調(diào)度優(yōu)先級將趨于恒定，導致調(diào)度集合趨于固定，即一部分用戶始終得不到調(diào)度，從而使公平性下降．所以，設計N(t)為ξ(t)的單調(diào)遞增函數(shù)如下:

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

(8)

其中，τ是一個接近0的正數(shù)，保證N(t)≠0．APF在ξ(t)>1時，N(t)>1，并且N(t)隨ξ(t)的增大而單調(diào)遞增，從而得到大的α(t)，加速各用戶優(yōu)先級的匯聚(即ξ(t)→0)，實現(xiàn)短期公平; 當ξ(t)<1 時，N(t)<1，并且N(t)隨ξ(t)的減小而降低，從而減慢α(t)→0 的速度，保證長期公平性．

步驟1 MSk估計信道狀態(tài), 并向基站反饋其信道質(zhì)量qk(t)．

步驟2 基站根據(jù)式(3)計算MSk的調(diào)度優(yōu)先級ρk(t)，并調(diào)度優(yōu)先級最大的前K個用戶進行數(shù)據(jù)發(fā)送．

4 仿真結(jié)果

圖3為遺忘因子α(t)對PF調(diào)度算法的影響進行的仿真．圖3(a)和圖3(b)給出某次按Dent模型產(chǎn)生L=10 個用戶信道，在連續(xù)100個時隙中這10個用戶的調(diào)度權重的變化情況．如圖3(a)所示，信道質(zhì)量好的用戶(如用戶8和用戶10)較早地得到調(diào)度，它們的優(yōu)先級隨之下降; 信道質(zhì)量差的用戶(如用戶1和用戶9)則需要等待較長時間才能夠獲得調(diào)度．經(jīng)過足夠長的時間(約40個時隙)后，由圖3(a)放大部分可以看到，所有用戶優(yōu)先級接近，高低關系交替變化，即用戶將公平地獲得調(diào)度機會．圖3(b)表現(xiàn)出的整體規(guī)律與圖3(a)相似，但由于將α(t)增加至0.05，使信道質(zhì)量好的用戶在被調(diào)度后，調(diào)度優(yōu)先級的降幅增加，相應的信道質(zhì)量差的用戶的優(yōu)先級增幅加大，從而使系統(tǒng)中用戶的調(diào)度優(yōu)先級經(jīng)過較短的時間(約10個時隙)便相互接近，即各用戶達到公平狀態(tài)．

圖3 遺忘因子對PF調(diào)度算法的影響

圖4給出不同算法的和速率性能．對于傳統(tǒng)的PF調(diào)度算法 (N(t)=0，代入式(7)，可得α(t)=αref= 0.01)，隨著時間的增加，系統(tǒng)的和速率下降．采用APF調(diào)度算法，在開始的一段時間內(nèi)(約20個時隙)，由于用戶優(yōu)先級的離散程度較高，遺忘因子α(t)較大，因此信道質(zhì)量差的用戶不需要等待很久便得到調(diào)度，導致系統(tǒng)的和速率低于傳統(tǒng)PF調(diào)度算法的．隨著時間繼續(xù)增加(約30時隙后)，用戶優(yōu)先級逐漸接近，APF調(diào)度算法使α(t)自適應減小，因此在維持較好公平性的前提下，信道質(zhì)量好的用戶會獲得更多的調(diào)度機會，此時APF調(diào)度算法的和速率性能優(yōu)于傳統(tǒng)PF調(diào)度算法的．采用QAPF調(diào)度算法，當ξ(t)>1 時，N(t)越大，則α(t)越大，在起始階段，對用戶優(yōu)先級調(diào)整的程度越大，導致系統(tǒng)的和速率降低; 隨著用戶優(yōu)先級逐漸接近，當ξ(t)<1 時，N(t)越大，則α(t)越小，信道質(zhì)量好的用戶得到更多調(diào)度機會，系統(tǒng)的和速率提高．對于APF調(diào)度算法，在起始階段N(t)較大，通過犧牲一部分系統(tǒng)速率獲得更好的短期公平，當用戶優(yōu)先級逐漸接近，N(t)的取值減小，即在保證較好的公平性的前提下對速率有一定改善．

圖5對算法的公平性進行仿真．基站在10個用戶中調(diào)度4個用戶，由Jain’s公平性指數(shù)的計算公式，得到所有調(diào)度算法公平性指數(shù)初始值均為0.4．如圖5所示，當N(t)較大時，公平性在經(jīng)過較短的時間即可獲得改善(如公平性指數(shù)達到0.5)．在起始階段(約20時隙)，用戶優(yōu)先級離散程度較大，相比于傳統(tǒng)PF調(diào)度算法，APF調(diào)度算法通過選擇較大的遺忘因子，可以獲得好的短期公平性; 經(jīng)過一段時間后(約40時隙)，用戶優(yōu)先級離散程度降低，APF調(diào)度算法的公平性劣于α= 0.01的PF調(diào)度算法的，即APF調(diào)度算法犧牲一定的公平性以換取系統(tǒng)和速率的改善(如圖4所示)．QAPF調(diào)度算法對α(t)的取值的情況與圖4的分析相同，N(t)越大，在起始階段的公平性改善越顯著，但隨著時間的推移，用戶優(yōu)先級逐漸接近，公平性逐漸劣于N(t)較小的QAPF調(diào)度算法的．與QAPF調(diào)度算法相比，APF調(diào)度算法的全局公平性更好．綜合圖4和圖5可以發(fā)現(xiàn)，APF調(diào)度算法犧牲了一定的系統(tǒng)速率，但公平性得到了改善．

圖4 系統(tǒng)的和速率性能圖5 公平性指數(shù)

圖6 系統(tǒng)平均等待時延

如圖6所示，隨著用戶數(shù)的增加，網(wǎng)絡負載加重，系統(tǒng)平均等待時延隨之增加．由于傳統(tǒng)的PF調(diào)度算法固定遺忘因子的取值，ΓPF隨L的增加而線性增大．當L較小時，ΓAPF與ΓPF接近; 當L較大時，ΓAPF小于ΓPF．這是因為用戶數(shù)L較小時，所有用戶的優(yōu)先級在短時間內(nèi)接近，之后，APF調(diào)度算法會給信道質(zhì)量好的用戶更多調(diào)度機會，系統(tǒng)平均等待時延較高; 當L較大時，所有用戶優(yōu)先級需要經(jīng)過較長時間才能接近，APF調(diào)度算法給信道質(zhì)量差的用戶更多調(diào)度機會，系統(tǒng)平均等待時延較低．QAPF調(diào)度算法通過設置非零的階數(shù)使公平性在較短時間內(nèi)得到改善，但犧牲了起始階段(約30時隙)的時延性能，雖然此后QAPF調(diào)度算法的等待時延優(yōu)于傳統(tǒng)PF調(diào)度算法的，但仍劣于APF調(diào)度算法的．

5 結(jié) 束 語

文中在承載實時與非實時業(yè)務的蜂窩通信系統(tǒng)中，針對傳統(tǒng)的PF調(diào)度算法無法保證用戶的短期公平性，以及用戶的時延需求難以滿足的問題，提出一種實現(xiàn)全局公平的自適應比例公平調(diào)度算法，在每個時隙，

基站根據(jù)系統(tǒng)中全體用戶的調(diào)度權重的離散程度，動態(tài)調(diào)整PF調(diào)度算法中的遺忘因子，從而影響用戶的調(diào)度優(yōu)先級的更新，實現(xiàn)長期和短期公平性以及系統(tǒng)速率的兼顧，并為實時業(yè)務用戶提供良好的時延保證．

參考文獻：

[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

(編輯： 齊淑娟)