馬哲明， 吳宣利， 韓杏玲

(哈爾濱工業(yè)大學(xué) 電子與信息工程學(xué)院，150001 哈爾濱)

?

LTE-A系統(tǒng)中基于資源利用率的時延優(yōu)先調(diào)度算法

馬哲明， 吳宣利， 韓杏玲

(哈爾濱工業(yè)大學(xué) 電子與信息工程學(xué)院，150001 哈爾濱)

摘要:針對現(xiàn)有LTE系統(tǒng)中調(diào)度算法在吞吐量、公平性及丟包率性能指標(biāo)上難以取得性能平衡的問題，提出一種改進(jìn)算法，在考慮用戶時延的前提下還考慮了用戶對資源塊(RB)的利用率，從實際獲得速率的角度來更精確描述用戶對資源的利用能力，更加合理地分配資源. 仿真結(jié)果表明，該算法的丟包率性能有很大改進(jìn)，同時在吞吐量、公平性方面也有著較好表現(xiàn)，實現(xiàn)了良好的綜合性能，能夠更好地滿足用戶的QoS需求.

關(guān)鍵詞:LTE-A; 資源利用率；時延; 丟包率

經(jīng)典的分組資源調(diào)度算法包括輪詢、最大載干比算法和比例公平算法[3]，但這些算法均具有明顯缺點[4]，不能很好地滿足業(yè)務(wù)實時性要求. 目前應(yīng)用成熟的算法主要有改進(jìn)的最大權(quán)重延遲優(yōu)先M-LWDF(modified largest weighted delay first)算法、指數(shù)比例公平EXP/PF(exponential PF)算法等[5]. 但是，這類算法依然無法保證信道質(zhì)量較差用戶的調(diào)度，用戶由于數(shù)據(jù)包的時延過大會產(chǎn)生較高丟包率. 針對時延問題，文獻(xiàn)[6]提出時延優(yōu)先調(diào)度DPS(delay prioritized scheduler)算法，該算法在用戶數(shù)較少或用戶間信道差異較小的理想假設(shè)下可以取得非常低的丟包率，在理論上可以滿足時延敏感業(yè)務(wù)的QoS需求. 但是該算法缺乏對用戶信道質(zhì)量的考慮，當(dāng)有多個用戶擁有相同優(yōu)先級時，隨機(jī)選出的用戶可能信道條件較差，即使占用資源也無法滿足QoS需求，造成資源的浪費，算法不僅在吞吐量上表現(xiàn)很差，同時丟包率反而會極大升高. 文獻(xiàn)[7]提出針對DPS算法改進(jìn)的MDPS算法，在較好滿足用戶時延要求的基礎(chǔ)上，解決了DPS算法當(dāng)用戶數(shù)較大時出現(xiàn)的問題，同時由于信道信息的引入顯著提升吞吐量，但這一算法的性能依然有繼續(xù)提升的空間.

針對上述問題，本文在考慮時延的基礎(chǔ)上，引入用戶對當(dāng)前信道的利用率，從實際可達(dá)速率角度出發(fā)，提出基于資源利用率的時延優(yōu)先調(diào)度RUBDPS(resource utilization based delay prioritized scheduler)算法，綜合考慮了用戶信道條件和傳輸需求，極大改善了DPS算法中用戶吞吐量過低及在用戶較多時丟包嚴(yán)重的問題，相比于MDPS算法，性能也有了一定提升.

1系統(tǒng)模型

在LTE-A系統(tǒng)中，時頻資源調(diào)度的單元是資源塊RB(resource block), 一個RB在時域上長度為0.5 ms，頻域上包括12個子載波，總共占據(jù)180 kHz的頻帶寬度. 不同用戶由于其信道質(zhì)量、業(yè)務(wù)需求等不同，對資源的需求也有所不同. 資源調(diào)度需要根據(jù)用戶信道信息和網(wǎng)絡(luò)負(fù)載情況，決定哪些用戶在哪段時間內(nèi)可以使用哪些無線資源，從而完成對系統(tǒng)內(nèi)有限時頻資源的動態(tài)分配. 調(diào)度器位于基站端，調(diào)度的周期是一個TTI(transmission time Interval)，每個TTI是1 ms.

圖1給出了下行資源調(diào)度流程[8]. UE接收來自eNodeB的小區(qū)專用參考信號，估計信道質(zhì)量并向eNodeB反饋. eNodeB動態(tài)地分配下行資源并產(chǎn)生下行調(diào)度信令，隨后根據(jù)資源分配情況將數(shù)據(jù)信息填充在相應(yīng)信道上. 用戶根據(jù)產(chǎn)生的調(diào)度信令中的相關(guān)內(nèi)容來選擇解碼相應(yīng)信道獲取數(shù)據(jù).

圖1　下行資源調(diào)度流程

在調(diào)度過程中，信道質(zhì)量是一項重要的指標(biāo)，用戶信道信息通常以信道質(zhì)量指示符CQI(channel quality indicator)的形式上報. CQI根據(jù)每個用戶的不同SINR值生成，由于用戶的移動以及頻率選擇性衰落，每個用戶的CQI數(shù)值在不同時間以及不同RB上是不同的. CQI不僅包含了用戶信道質(zhì)量，還指示了用戶需要采用的編碼調(diào)制方式. LTE-A系統(tǒng)采用自適應(yīng)調(diào)制編碼技術(shù)，根據(jù)CQI信息來動態(tài)調(diào)整編碼調(diào)制方式，CQI、SINR以及編碼調(diào)制方式之間的關(guān)系如表1所示.

表1　編碼調(diào)制方式與SINR映射表

從表1可以看出，CQI與用戶的SINR值呈正相關(guān). 當(dāng)用戶信道質(zhì)量較好時，CQI值較大，系統(tǒng)會采用高階調(diào)制和高編碼速率，而不同的編碼調(diào)制方式將會直接影響用戶的數(shù)據(jù)傳輸速率. 在第t個TTI，用戶k在RBn上獲得的理論速率為

式中：ns為一個子幀上的OFDM符號數(shù)；nc是其中用于控制的符號的個數(shù)；nsub為一個資源塊上的子載波數(shù)；Qmk,n(t)是用戶k在當(dāng)前時隙下每個符號上調(diào)制的比特數(shù)，由調(diào)制方式?jīng)Q定；Ck,n(t)是用戶k在第t個TTI時在RBn的符號速率. 在LTE-A系統(tǒng)中，每個TTI每次分配的實際上是兩個時域上連續(xù)的RB，所以nsub=12，ns=14，nc=3(采用常規(guī)循環(huán)前綴).

分組業(yè)務(wù)主要以數(shù)據(jù)包形式傳輸，在用戶的緩沖區(qū)中，所有業(yè)務(wù)的數(shù)據(jù)包形成一個隊列，遵循先進(jìn)先出原則. 對于位于隊列首位的數(shù)據(jù)包，隊頭數(shù)據(jù)包HoL(head of line)時延表示該數(shù)據(jù)包的時延情況，如果HoL時延超過了時延門限，那么該數(shù)據(jù)包將被丟棄[9]. 而最后系統(tǒng)總的吞吐量計算以實際成功傳輸?shù)臄?shù)據(jù)包的數(shù)據(jù)量為準(zhǔn).

2基于資源利用率的時延優(yōu)先調(diào)度算法

雖然MDPS算法解決了DPS的一些問題，但是其性能仍有提升空間. 第一，MDPS算法在計算每個RB上的優(yōu)先級時采用的是所有RB上的平均頻譜效率，有效但不夠精確；第二，MDPS算法僅僅考慮的是用戶的信道質(zhì)量，而有時候由于用戶實際剩余數(shù)據(jù)量的限制，用戶未必可以在RB上達(dá)到預(yù)期的高速率傳輸，給算法造成一定誤差. 針對以上兩點，本文提出了一種全新的基于資源利用率的時延優(yōu)先調(diào)度(RUBDPS)算法，該算法從用戶在RB上可達(dá)實際速率入手，根據(jù)實際的RB利用率來分配資源.

RUBDPS算法在每個RB上計算用戶的優(yōu)先級，在RBn上用戶k的優(yōu)先級表達(dá)式如下：

(1)

式中：τk-Wk(t)表示目前該業(yè)務(wù)允許的時延量；T0為一個TTI的時間長度，在LTE系統(tǒng)中T0=1 ms；c為加權(quán)因子，其數(shù)值可根據(jù)實際需要調(diào)整;Ek,n(t)為用戶k在RBn上的資源利用率，定義為

(2)

一般來說實時業(yè)務(wù)都需要滿足一定的保證數(shù)據(jù)傳輸速率，所以算法中當(dāng)某個RB依據(jù)優(yōu)先級公式完成分配后，系統(tǒng)會根據(jù)用戶的速率情況讓已經(jīng)達(dá)到GBR要求的用戶退出分配. 最終的分配結(jié)果以分配向量A∈C|N×1表示，其中A中的第n個元素an=k表示用戶k被分配到RBn上. 完整的RUBDPS調(diào)度算法在每個TTI中的流程如下：

輸入：

系統(tǒng)資源塊數(shù)目N;

接入系統(tǒng)用戶集合K={1, 2, …,K};

每個用戶的時延門限τ1,τ2,…,τk;

每個用戶的HoL時延W1,W2,…,Wk.

輸出： 資源塊分配向量A.

1)在RBn(n從1開始取值) 上，計算每個集合中用戶在當(dāng)前TTI下隊頭數(shù)據(jù)包剩余比特數(shù)lk(t)，根據(jù)式(2)計算資源利用率Ek,n(t)，將A的所有元素清零.

2)根式(1)計算每個用戶在當(dāng)前TTI下在RBn上的優(yōu)先級數(shù)值Mk,n(t).

3)根據(jù)k*=arg max(Mk,n(t))挑選優(yōu)先級最高的用戶k*，分配到RBn上，更新A，令an=k*.

4)計算k*在RBn上獲得速率，并更新k*在該TTI上的速率.

5)完成在RBn上的分配后判斷用戶獲得數(shù)據(jù)速率是否達(dá)到GBR要求，若用戶k*數(shù)據(jù)速率大于等于GBR，則把k*從服務(wù)列表中清除，K=K/{k*}.

6)令n=n+1，重復(fù)上述步驟，直至RB分配完畢.

7)返回該TTI下資源塊分配向量A.

該算法通過考慮用戶實際獲得速率來改善系統(tǒng)的吞吐量，引入GBR的限制來更新用戶列表保證公平性，同時包含對時延的考慮，可以更好地滿足業(yè)務(wù)QoS需求.

3仿真分析

3.1仿真環(huán)境

本文研究的用戶分布在半徑500m的六邊形小區(qū)中，用戶受到來自周邊6個小區(qū)的干擾，用戶的信道模型加入了路徑損耗和陰影衰落，多徑衰落信道模型采用TU3. 本信道模型從實際角度出發(fā)，區(qū)別于文獻(xiàn)[6]中用戶信道相差不多的理論情況. 用戶傳輸業(yè)務(wù)類型為實時視頻流，包尺寸分布規(guī)律與文獻(xiàn)[6]相同，其他仿真參數(shù)參見表2.

表2　系統(tǒng)仿真參數(shù)設(shè)置

3.2加權(quán)因子的確定

式(1)中c的數(shù)值決定了算法中用戶資源利用能力的權(quán)重. 文獻(xiàn)[7]的仿真結(jié)果指明DPS算法的公平性最好，吞吐量最差，這是由于該算法完全不考慮用戶的信道條件，因此用戶信道質(zhì)量在算法中所占比重將影響算法最終的吞吐量與公平性表現(xiàn).

圖2和圖3分別給出了系統(tǒng)中存在60個激活用戶的條件下，系統(tǒng)的吞吐量和公平性隨加權(quán)因子c的取值而變化的情況，這里的公平性是以Jain’s指數(shù)進(jìn)行衡量的. 從仿真圖中可以看出，隨著加權(quán)因子c的數(shù)值增加，系統(tǒng)的吞吐量逐漸提升，但公平性會有一定的下降，即吞吐量與資源利用率權(quán)重成正相關(guān)，公平性與資源利用率成反相關(guān). 在使用中，可以根據(jù)實際需求對加權(quán)因子的取值綜合考慮。從圖2得知，在加權(quán)因子大于3.5時，吞吐量增長比較緩慢，這是由于此時對資源利用率的考慮已經(jīng)比較充分，優(yōu)先級計算公式已經(jīng)對數(shù)據(jù)速率給予了足夠高的權(quán)重，因此已經(jīng)能夠取得較高的吞吐量。進(jìn)一步的增大加權(quán)因子數(shù)值不能換取吞吐量的快速提升，反而會導(dǎo)致公平性的下降，所以從折中角度考慮，本文在后續(xù)仿真中選取c=3.5。

圖2　K=60時吞吐量變化

圖3　K=60時公平性指數(shù)變化

3.3不同算法對比仿真結(jié)果

根據(jù)文獻(xiàn)[7]的結(jié)果，M-LWDF和EXP/PF的性能較為接近，M-LWDF在公平性和丟包率方面稍好一些，所以本文僅對M-LWDF、DPS、MDPS以及RUBDPS這4種算法進(jìn)行仿真，主要關(guān)注丟包率、吞吐量、公平性3個性能指標(biāo).

在滿足時延和公平性要求的前提下，丟包率會對實時業(yè)務(wù)的用戶體驗有明顯影響，因此成為實時業(yè)務(wù)資源分配算法的一項重要指標(biāo). 圖4給出了用戶的丟包率仿真結(jié)果. 當(dāng)用戶數(shù)目低于50時，RB資源較為充足，幾乎所有算法的丟包率都為0. 當(dāng)用戶數(shù)逐漸增加時，由于無線資源總量的限制，不能滿足所有用戶的需求，所以會有部分?jǐn)?shù)據(jù)包被丟棄，丟包率數(shù)值開始上升. 當(dāng)用戶數(shù)小于80時，可以看到M-LWDF算法的丟包率明顯高于其他算法，而其他算法由于在優(yōu)先級的計算過程中以時延為優(yōu)先，所以在中載條件下表現(xiàn)出較低的丟包率. 隨著用戶數(shù)進(jìn)一步增多， 當(dāng)用戶數(shù)超過80時，DPS算法的丟包率急劇上升，遠(yuǎn)超其他算法，而RUBDPS算法繼續(xù)保持了良好的性能，在4種算法中丟包率最低. 這是由于DPS算法完全沒有考慮用戶的信道質(zhì)量，在多個用戶擁有相同的時延門限與隊列頭時延差值時，很可能選出信道條件較差的用戶接受調(diào)度，而這類用戶由于自身信道條件過差，即使接受調(diào)度也難以滿足QoS要求或需要占用更多的資源來滿足要求，而發(fā)出的數(shù)據(jù)包數(shù)量并不多，造成資源浪費，也使得大量信道質(zhì)量較好的用戶被閑置，從而出現(xiàn)大量的其他數(shù)據(jù)包被丟棄的現(xiàn)象. MDPS與RUBDPS算法由于在考慮時延的基礎(chǔ)上引入了用戶信道信息，所以丟包率保持在較低的水平上. RUBDPS算法由于考慮了用戶在RB上的實際傳輸速率，更為精確地描述了用戶對RB的利用能力，所以實現(xiàn)了最低的丟包率.

圖4　4種算法的丟包率對比

圖5為4種算法的吞吐量仿真結(jié)果. 當(dāng)K不超過40時，幾種算法的吞吐量性能沒有太大差別. 當(dāng)K繼續(xù)增大時，M-LWDF算法開始展現(xiàn)了吞吐量優(yōu)勢，DPS算法由于完全忽略用戶的信道質(zhì)量導(dǎo)致吞吐量表現(xiàn)最差， RUBDPS算法吞吐量表現(xiàn)較好，相比于DPS算法有明顯的改進(jìn)，同時比起MDPS算法也有所提升. RUBDPS算法的吞吐量改善主要有兩點原因: 第一是在具體的RB上計算優(yōu)先級，相比于MDPS算法中計算所有RB的平均頻譜效率能更精確地表征具體RB上的信道狀況；第二是引入了資源利用率概念，通過考慮實際能夠獲得的速率，使得需要傳輸較少數(shù)據(jù)的用戶不會占用大量優(yōu)質(zhì)資源，從而使RB的分配更加合理，系統(tǒng)吞吐量更高.

圖5　4種算法的吞吐量對比

4種算法的公平性對比如圖6中所示. 當(dāng)系統(tǒng)處于輕載和中載的狀況時，不同算法的公平性沒有明顯差距. 當(dāng)用戶數(shù)超過70時，這種差距逐漸變得明顯. M-LWDF算法由于對用戶信道質(zhì)量的考量權(quán)重較大，所以相應(yīng)地公平性下降最快，DPS算法設(shè)計的初衷并非提升公平性，但是由于其不考慮用戶信道質(zhì)量，所以表現(xiàn)出了較高的公平性，這種公平性是以低吞吐量為代價的. RUBDPS算法加入了對信道質(zhì)量的考慮，相比于M-LWDF算法，犧牲了一部分吞吐量，但是換來了公平性的提升. 相比于MDPS，RUBDPS算法由于加入了實際剩余比特數(shù)目的限制，避免了資源的浪費，使得資源分配更合理，公平性更好一些.

圖6　4種算法的公平性

4結(jié)論

1)當(dāng)用戶數(shù)較多(大于60)時，RUBDPS算法擁有最低的丟包率，不僅有效克服了DPS算法在重載條件下丟包率急劇增加的缺點，而且相比于MDPS算法也有所提升，整體性能持久穩(wěn)定.

2)在吞吐量方面，RUBDPS算法引入了資源利用率來描述用戶對RB的實際利用能力，同時算法在每個具體的RB上計算優(yōu)先級，因此使得優(yōu)質(zhì)資源更多地分配給數(shù)據(jù)傳輸需求較高的用戶，實現(xiàn)了吞吐量改進(jìn)，在用戶數(shù)大于50時，其吞吐量表現(xiàn)一直好于DPS和MDPS算法.

3)在公平性方面，RUBDPS算法在重載條件下好于MDPS算法和M-LWDF算法，雖然稍差于DPS算法，但是整體公平性依然較好，同時算法的綜合性能十分優(yōu)秀.

4)RUBDPS算法在吞吐量、公平性和丟包率之間達(dá)到了一個良好的均衡點，既能保證實時業(yè)務(wù)的時延需求，又能保證系統(tǒng)整體的吞吐量和公平性，為下行實時業(yè)務(wù)的調(diào)度提供了一種可行的辦法.

參考文獻(xiàn)

[1] LIM C, YOO T, CLERCKX B, et al. Recent trend of multiuser MIMO in LTE-advanced[J]. IEEE Communications Magazine, 2013, 51(3): 127-135.

[2] SAHOO B P S, PUTHAL D, SWAIN S, et al. A comparative analysis of packet scheduling schemes for multimedia services in LTE networks[C]//International Conference on Computational Intelligence and Networks (CINE). Bhubaneshwar: IEEE, 2015: 110-115.

[3] 孫瑨. TD-LTE無線資源調(diào)度算法的研究[D]. 哈爾濱：哈爾濱工業(yè)大學(xué)，2012.

[4] OSTERBO O. Scheduling and capacity estimation in LTE[C]// International Teletraffic Congress (ITC). San Francisco:ACM, 2011: 63-70.

[5] ITURRALDE M, ALI YAHIYA T, WEI A, et al. Performance study of multimedia services using virtual token mechanism for resource allocation in LTE networks[C]//IEEE Vehicular Technology Conference (VTC Fall).San Francisco:IEEE, 2011: 1-5.

[6] SANDRASEGARAN K, RAMLI H A M, BASUKALA R. Delay-prioritized scheduling (DPS) for real time traffic in 3GPP LTE system[C]//Wireless Communications and Networking Conference (WCNC).Sydney: IEEE, 2010: 1-6.

[7] 吳宣利, 韓杏玲, 趙婉君. LTE 系統(tǒng)中一種低丟包率的實時業(yè)務(wù)調(diào)度算法[J]. 哈爾濱工業(yè)大學(xué)學(xué)報, 2015, 47(3): 24-28.

[8] SESIA S, TOUFIK I, BAKER M. LTE-the UMTS long term evolution: from theory to practice[M]. New York: John Wiley & Sons，2009．

[9] PEDERSEN K I , KOLDING T E, FREDERIKSEN F, et al. An overview of downlink radio resource management for UTRAN long-term evolution [J]. IEEE Communications Magazine，2009，47(7)：86-93.

(編輯王小唯苗秀芝)

Resource utilization based delay prioritized scheduler algorithm in LTE-A system

MA Zheming, WU Xuanli, HAN Xingling

(School of Electronics and Information Engineering, Harbin Institute of Technology, 150001 Harbin, China)

Abstract:To overcome the difficulty of reaching a balance of throughput, fairness and packet loss of current LTE scheduling algorithms, an enhanced algorithm is proposed. We take the Resource Block (RB) utilization into consideration on the premise of considering user delay, and hence can describe the resource utilization efficiency of users more precisely, which causes the resource is allocated more properly. Simulation results demonstrate that the algorithm has a great improvement on packet loss rate, and at the same time, it performs better in terms of throughput and fairness. It shows an excellent comprehensive performance and can better satisfy the requirements of users’ Quality of Service (QoS).

Keywords:LTE-A; resource utilization; delay; packet loss rate

中圖分類號:TN929.5

文獻(xiàn)標(biāo)志碼:A

文章編號:0367-6234(2016)05-0057-05

通信作者:吳宣利, xlwu2002@hit.edu.cn.

作者簡介:馬哲明(1991—)，男，碩士研究生；吳宣利(1980—),男,副教授,博士生導(dǎo)師.

基金項目:國家重點基礎(chǔ)研究發(fā)展規(guī)劃(2013CB329003)； 國家自然科學(xué)基金項目(61301100)； 國家科技重大專項項目(2013ZX03001024-003).

收稿日期:2015-06-20.

doi：10.11918/j.issn.0367-6234.2016.05.008