LTE系統(tǒng)中一種低丟包率的實時業(yè)務(wù)調(diào)度算法

吳宣利，韓杏玲，趙婉君

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

目前，移動通信網(wǎng)絡(luò)已經(jīng)開始邁入第四代移動通信——LTE-A(long time evolution-advanced)的大門，基于移動網(wǎng)絡(luò)的實時語音和實時視頻等實時業(yè)務(wù)發(fā)展迅速，成為通信領(lǐng)域的研究重點.良好的實時業(yè)務(wù)調(diào)度算法可以有效地滿足業(yè)務(wù)QoS需求，在決定系統(tǒng)的性能上起到關(guān)鍵作用［1］.

無線網(wǎng)絡(luò)中的實時傳輸要求很低的傳輸延遲、延遲抖動、丟包率，以及足夠的帶寬，以保證業(yè)務(wù)的QoS需求.而早期的分組資源調(diào)度算法如比例公平(proportional fair，PF)算法等是以系統(tǒng)吞吐量和用戶間的公平性為目標，沒有考慮用戶業(yè)務(wù)的QoS需求和緩存隊列信息［2］，使用PF算法處理實時業(yè)務(wù)時，會導(dǎo)致數(shù)據(jù)包有過大延遲而出現(xiàn)很高的丟包率，因此不能很好地滿足業(yè)務(wù)實時性要求.對于實時業(yè)務(wù)的分組調(diào)度算法，目前常用的有改進的最大權(quán)重延遲優(yōu)先(modified largest weighted delay first，M-LWDF)、指數(shù)比例公平(exponential PF，EXP/PF)等算法［3-4］，但是上述算法難以保證信道狀況較差用戶的調(diào)度機會，會導(dǎo)致此類用戶丟包率較高，而且上述算法的計算量較大.為解決此問題，研究人員又提出時延優(yōu)先調(diào)度(delay prioritized scheduler，DPS)算法［5］，DPS 算法在計算用戶優(yōu)先級時只考慮用戶的時延狀況，算法復(fù)雜度較低，而且能夠滿足實時業(yè)務(wù)的QoS需求.但是隨著用戶數(shù)目持續(xù)增多，DPS算法的丟包率性能會急劇變差，而且系統(tǒng)的吞吐量也非常低.

因此針對這些問題本文提出了改進的時延優(yōu)先 調(diào) 度 (modified delay prioritized scheduler，MDPS)算法，該算法在考慮用戶時延條件的基礎(chǔ)上，綜合考慮用戶的信道狀態(tài).因此，相對于DPS算法，MDPS算法可以在保證用戶間公平性的同時，改善系統(tǒng)重載時的丟包率性能，而且系統(tǒng)吞吐量也可得到有效提升.

1 系統(tǒng)模型

考慮一個多小區(qū)的LTE系統(tǒng)，本文中參與調(diào)度的用戶只隨機分布在中心小區(qū)中.中心小區(qū)包含25個物理資源塊(physical resource block，PRB)，占據(jù)5 MHz帶寬.基站位于小區(qū)的中心位置，所有的資源塊都參與中心小區(qū)內(nèi)的用戶調(diào)度.本文中采用的LTE系統(tǒng)的參數(shù)設(shè)置見表1.

表1 LTE下行系統(tǒng)參數(shù)設(shè)置

由于多路徑傳播產(chǎn)生的頻率選擇性衰落和用戶運動導(dǎo)致的時間選擇性衰落，每個用戶的瞬時下行信干噪比(signal to interference plus noise ratio，SINR)值隨物理資源塊PRB和TTI(transmission time interval)的不同而不同.根據(jù)瞬時下行SINR值，用戶在每個 TTI都將相應(yīng)的 CQI(channel quality indicator)值報告給基站，基站可以根據(jù)上報的CQI信息及時調(diào)整和更新用戶的信道狀態(tài)信息，然后系統(tǒng)采用自適應(yīng)調(diào)制編碼(adaptive modulation and coding，AMC)技術(shù)，根據(jù)信道條件的變化來動態(tài)地選擇適當?shù)木幋a調(diào)制方案.當信道條件較好時，采用高階調(diào)制和較高的編碼速率來實現(xiàn)高傳輸速率，獲得較高吞吐量.當信道條件質(zhì)量較差時，采用低階調(diào)制和較低的編碼速率以保證傳輸鏈路的質(zhì)量，從而實現(xiàn)在多用戶情況下進行系統(tǒng)資源最優(yōu)分配.本文利用式(1)來確定用戶k在物理資源塊i

上可以獲得的理論數(shù)據(jù)速率:

式中:N為一個子幀上的OFDM符號數(shù)，M為一個資源塊上的子載波數(shù)，Qk為用戶k一個符號所能攜帶的比特數(shù)，由調(diào)制方式所決定.nbitsi k為根據(jù)用戶的SINR值由表2映射得到的用戶k在物理資源塊i上的編碼速率.

基站為每位用戶分配了一個緩沖區(qū)，在本文中緩沖區(qū)的大小認為是無限的，緩沖區(qū)中每個業(yè)務(wù)流緩存隊列數(shù)據(jù)包采取先進先出策略.對于在基站緩沖區(qū)中排序的每個數(shù)據(jù)包，可計算出隊頭數(shù)據(jù)包(head of line，HoL)的時延.如果HoL數(shù)據(jù)包的時延超過了時延門限，那么該包將被丟棄［8］.

系統(tǒng)中每個TTI中等待接受調(diào)度的用戶都放置在服務(wù)列表中，調(diào)度器根據(jù)采用的調(diào)度算法來決定用戶的優(yōu)先級.調(diào)度算法考慮了某些調(diào)度條件，如用戶信道狀況、HoL數(shù)據(jù)包時延、服務(wù)類型等.如果選定某個用戶開始傳輸，當前用戶傳輸?shù)臄?shù)據(jù)速率將依據(jù)用戶上報的下行瞬時SINR值和用戶緩沖區(qū)內(nèi)待傳送的比特數(shù)來共同確定.在每個TTI，根據(jù)采用的調(diào)度算法結(jié)合用戶需求為用戶分配PRB.在用戶需求得到滿足之后，則此用戶從當前服務(wù)列表中清除.

表2 MCS與SINR映射表［7］

2 算法分析

2.1M－LWDF算法

M-LWDF算法是針對高速實時多媒體業(yè)務(wù)流提出，該算法充分考慮分組數(shù)據(jù)包的時延、業(yè)務(wù)優(yōu)先級、用戶當前信道質(zhì)量等因素［9］.對于物理資源塊i，調(diào)度時選取在當前資源塊上具有最大優(yōu)先級的用戶k，該算法的優(yōu)先級計算公式為

式中:Wk(t)為實時業(yè)務(wù)用戶k的隊列頭時延，)為用戶k在第i個PRB上獲得的理論數(shù)據(jù)傳輸速率，Rk(t)為用戶k在時間窗內(nèi)的平均吞吐量，ak的定義為

式中:δk為實時業(yè)務(wù)用戶k可接受的丟包率，τk為實時業(yè)務(wù)用戶k的時延門限，當數(shù)據(jù)包等待時延超過時延門限時，數(shù)據(jù)包將被丟棄.

由式(2)、(3)可知，M-LWDF算法支持對QoS有不同要求的用戶.隊頭數(shù)據(jù)包δk和τk越小，就能獲得越大指標的ak，在傳輸過程中能獲得更大的優(yōu)先級.該調(diào)度算法表達式中，實時業(yè)務(wù)的優(yōu)先級與HoL等待時間成簡單的線性增長關(guān)系，對于時延敏感的實時業(yè)務(wù)，當HoL數(shù)據(jù)包等待時間接近時延門限時，調(diào)度優(yōu)先級無法快速提高，因此數(shù)據(jù)包超時就會導(dǎo)致丟包的產(chǎn)生.

2.2 EXP/PF算法

EXP/PF算法在M-LWDF調(diào)度算法基礎(chǔ)上提出，對于物理資源塊i，調(diào)度時選取在當前資源塊上具有最大優(yōu)先級的用戶k，其優(yōu)先級為

其中

式中NUE為下行系統(tǒng)中用戶數(shù)目.

由式(4)、(5)可知，EXP/PF調(diào)度算法對時延的敏感程度是時變的，實時業(yè)務(wù)調(diào)度優(yōu)先級與時延呈指數(shù)關(guān)系，因此 EXP/PF算法相對于M-LWDF算法來說具有更好的時延特性.

2.3 DPS算法

針對LTE系統(tǒng)中實時視頻流業(yè)務(wù)對丟包率非常敏感的特點，研究人員提出了DPS算法，該算法的優(yōu)先級為

可看出，隨著用戶Wk的增大，用戶的優(yōu)先級隨之提升.當某個業(yè)務(wù)在緩存隊列中的等待時間越接近于時延門限，業(yè)務(wù)優(yōu)先級越高.因此DPS算法能夠滿足時延敏感業(yè)務(wù)的 QoS需求.但式(6)只考慮了用戶的時延狀況，在用戶數(shù)目較多時，必定存在大量用戶具有相同的優(yōu)先級，對于此類用戶的調(diào)度順序問題DPS算法并未做出明確的說明，而且DPS算法的吞吐量也很低.針對這些問題，本文提出改進算法——MDPS算法.

2.4MDPS算法

本文所提出的MDPS算法在DPS算法的基礎(chǔ)上，綜合考慮了用戶的時延狀況和信道狀態(tài)，每個用戶的優(yōu)先級為

式中Γk(t)為用戶k在所有PRB上的平均頻譜效率，

式中:NPRB是系統(tǒng)中的物理資源塊數(shù)目，φik(t)為用戶k在第i個PRB上獲得的頻譜效率.根據(jù)表2可知，頻譜效率由用戶上報的CQI值所決定，因此Γk(t)可表征用戶的信道狀態(tài).

式(7)中a、b均為常數(shù)，并沒有實際物理意義.a的取值會影響用戶信道狀態(tài)信息在決定用戶優(yōu)先級時的權(quán)重，而b的取值則會影響用戶時延信息在決定用戶優(yōu)先級時的權(quán)重.若a越小，b越大，則用戶的信道狀態(tài)越能決定用戶的調(diào)度順序，而時延信息所占的影響權(quán)重會下降，有助于系統(tǒng)吞吐量的提升，而用戶之間的公平性則會有所降低.經(jīng)過數(shù)學(xué)分析和仿真驗證，從均衡系統(tǒng)吞吐量和用戶公平性的角度出發(fā)，本文選取a=10，b=1.

通過式(7)計算得到服務(wù)列表中用戶的優(yōu)先級數(shù)值后，根據(jù)其優(yōu)先級數(shù)值對用戶進行降序排列，然后根據(jù)式(9)挑選出優(yōu)先級最高的用戶接受調(diào)度.在此用戶調(diào)度請求得到滿足之后，從服務(wù)列表中清除，根據(jù)式(9)重新從服務(wù)列表中挑選用戶接受調(diào)度.

由式(7)可知，Wk(t)和Γk(t)越大，用戶的優(yōu)先級越高.當系統(tǒng)中用戶數(shù)目較多時，在緩沖區(qū)中將有大量的數(shù)據(jù)包時延接近時延門限，而對于時延狀況相同的用戶來說，信道條件越好的用戶優(yōu)先級越高，可以有效地利用條件好的信道盡可能傳送更多的數(shù)據(jù)包.因此MDPS算法可以滿足實時業(yè)務(wù)用戶的時延需求，并提供良好的丟包率性能，同時系統(tǒng)的吞吐量相對于DPS算法可以得到有效地提升.

在MDPS算法中，每個TTI需要計算出所有位于服務(wù)列表中用戶的優(yōu)先級，然后優(yōu)先級最高的用戶優(yōu)先選取信道條件最好的PRB，直至滿足其業(yè)務(wù)要求的保證數(shù)據(jù)傳輸速率(guaranteed bit rate，GBR)，將此用戶從服務(wù)列表中清除，并重新尋找優(yōu)先級最高的用戶接受調(diào)度，循環(huán)上述過程直至所有的資源塊分配完畢.本文采用的調(diào)度算法的調(diào)度流程如下:

輸入:

系統(tǒng)調(diào)度時隙數(shù)目:NTTⅠ

系統(tǒng)資源塊數(shù)目:NPRB

接入系統(tǒng)用戶數(shù)目:NUE

每個用戶時延門限:τ1，τ2…τk

每個用戶的HoL時延:W1，W2…Wk

用戶GBR要求:GBR輸出:

資源塊分配矩陣:allocation-RB

1)賦值i_TTⅠ=1;

2)根據(jù)式(8)計算每個用戶在當前TTⅠ在整個帶寬上的平均頻譜效率:Γ1(i-TTⅠ)，Γ2(i-TTⅠ)…Γk(i-TTⅠ);

3)根據(jù)式(7)計算每個用戶在當前TTⅠ的優(yōu)先 級 數(shù) 值:M1(i-TTⅠ)，M2(i-TTⅠ)…Mn(i-TTⅠ);

4)根據(jù)式(9)挑選優(yōu)先級最高用戶K接受調(diào)度;

5)從未分配出PRB中挑選出用戶K信道條件最好的PRB;

6)在選出的PRB上傳輸用戶K的數(shù)據(jù)，將此PRB標記為已分配，并更新資源塊分配矩陣allocation-RB;

7)判斷當前用戶獲得數(shù)據(jù)速率＜GBR，若小于，則重復(fù)步驟5)-7)，直至用戶K數(shù)據(jù)速率≥GBR，然后把此用戶從服務(wù)列表中清除;

8)判斷PRB是否分配完畢，若沒有，則重復(fù)步驟4)-8)，直至PRB分配完畢;

9)i-TTⅠ=i-TTⅠ+1;

10)判斷i-TTⅠ是否等于NTTⅠ，若不相等，則重復(fù)步驟2)～10)直至i-TTⅠ=NTTⅠ;

11)返回資源塊分配矩陣allocation-RB.

3 仿真分析

3.1 仿真環(huán)境

本文主要對上述提到的4種算法MLWDF、EXP/PF、DPS和 MDPS算法從吞吐量、丟包率和公平性等3個方面進行性能仿真.主要仿真參數(shù)設(shè)置如表3所示.

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

本文采用的方案是在一個半徑為500 m正六邊形小區(qū)，一定數(shù)目的UE隨機分布在小區(qū)中，所以小區(qū)中用戶之間的信道狀況相差極大，這與提出DPS算法的文獻［5］有所不同，在文獻［5］中所有用戶都一致地分布在基站周圍，這樣會導(dǎo)致所有用戶信道狀況相差不大，因此本文的仿真環(huán)境要更接近于實際系統(tǒng).所有用戶仿真的業(yè)務(wù)均為實時視頻流業(yè)務(wù)，要求保證數(shù)據(jù)傳輸速率為256 kbps，時延門限設(shè)置為20 ms.具體視頻業(yè)務(wù)參數(shù)見文獻［10］.

3.2 仿真結(jié)果

在滿足最低時延和較好公平性指數(shù)的情況下，丟包率的大小將明顯影響實時業(yè)務(wù)的用戶體驗［11］.因此丟包率是評價實時業(yè)務(wù)調(diào)度算法的重要指標.圖1對用戶的丟包率進行了仿真.從圖1知，隨著用戶數(shù)目的增多，由于PRB資源有限，難以保證所有用戶需求，因此會有更多的包被丟棄，所以4種算法的PLR也隨之提升.在用戶數(shù)目低于40時，此時系統(tǒng)中的資源能夠保證所有實時業(yè)務(wù)用戶需求，因此4種算法PLR均為零.當用戶數(shù)目為40～70時，M-LWDF和EXP/PF算法開始不能保證信道質(zhì)量較差用戶的PLR性能，而DPS和MDPS算法此時仍可獲得較低的PLR.隨著用戶數(shù)目的持續(xù)增多，此時DPS算法的PLR性能急劇變壞，這是由于用戶數(shù)目較多時，根據(jù)式(6)，此時具有相同優(yōu)先級的用戶非常多，信道條件差的用戶可能會優(yōu)先接受調(diào)度，某些高質(zhì)量的信道被閑置，所以導(dǎo)致PLR急劇上升.與前3種算法對比發(fā)現(xiàn)，可以看出本文提出的MDPS算法PLR性能遠遠好于前3種算法.在相同仿真參數(shù)設(shè)置的情況下，MDPS算法能支持更多的用戶，而且隨著用戶數(shù)目的持續(xù)增多，在相同時延條件下，MDPS算法會優(yōu)先選擇信道條件好的用戶接受調(diào)度，因此在PRB數(shù)目有限的情況下，會充分利用高質(zhì)量的信道，能發(fā)出更多的包，因此MDPS算法能夠提供較低的丟包率性能.

圖2對系統(tǒng)的吞吐量進行了仿真.從圖2可看出，隨著用戶數(shù)目的增多，4種算法的系統(tǒng)吞吐量會隨之提升.在用戶數(shù)目＜40時，此時系統(tǒng)中的PRB足夠支持所有的用戶業(yè)務(wù)，但是當用戶數(shù)目繼續(xù)增多時，DPS和MDPS算法吞吐量開始低于MLWDF和EXP/PF算法，這是由于在此用戶數(shù)目下，DPS和MDPS算法仍然能夠保證信道質(zhì)量較差用戶的PLR性能，這部分PLR性能上的提升是通過犧牲吞吐量的方式獲得的.但是當用戶數(shù)目＞70時，此時系統(tǒng)資源已經(jīng)不能保證所有用戶的業(yè)務(wù)需求，相比于DPS算法來講，MDPS算法優(yōu)先選擇信道條件好的用戶接受調(diào)度，在PRB資源有限的情況下，充分利用高質(zhì)量的信道，盡可能發(fā)出更多的包，因此可以獲得更高的系統(tǒng)吞吐量.

圖3對用戶間的公平性進行了仿真.從圖3可知，在用戶數(shù)目較少時，4種算法的公平性指數(shù)相差不大，隨著用戶數(shù)的增多，M-LWDF和EXP/PF算法公平性指數(shù)急劇下降，而DPS和MDPS算法變化要緩慢一些.MDPS算法公平性與DPS算法相比略有下降.與M-LWDF和EXP/PF算法相比，MDPS算法犧牲了一部分系統(tǒng)吞吐量換取了公平性性能上的提升，而與DPS算法相比，MDPS算法則是通過犧牲小部分公平性換取了系統(tǒng)吞吐量的提升.總之，其他3種算法相比，MDPS算法在系統(tǒng)吞吐量和公平性之間取得了良好的折中.

圖1 丟包率對比

圖2 系統(tǒng)吞吐量對比

圖3 用戶間的公平性指數(shù)對比

4 結(jié)語

本文主要研究LTE系統(tǒng)下行鏈路實時資源調(diào)度算法的性能.在DPS算法的基礎(chǔ)上提出改進的MDPS算法，同時把M-LWDF和EXP/PF算法作為對比算法，對上述4種算法進行仿真分析.根據(jù)仿真結(jié)果可知，在LTE系統(tǒng)中，當負載較輕(用戶數(shù)目＜40)時，4種算法性能相差不大，但是隨著負載的增加(用戶數(shù)目40～70)，此時MLWDF和EXP/PF算法已經(jīng)不能保證信道質(zhì)量較差用戶的丟包率性能，而DPS和MDPS算法則通過犧牲一部分系統(tǒng)吞吐量的方式來保證用戶的丟包率.因此在丟包率和公平性指數(shù)上，DPS和MDPS算法要遠好于M-LWDF和EXP/PF算法.當負載繼續(xù)增加(用戶數(shù)目＞70)時，此時DPS的PLR性能急劇變壞，而MDPS算法在PLR上表現(xiàn)出其持久性能，MDPS算法系統(tǒng)吞吐量也遠好于DPS算法.與 M-LWDF和 EXP/PF算法相比，MDPS算法雖然犧牲了一部分系統(tǒng)吞吐量但是卻換取了PLR性能上的大大提升.因此，與本文提到的其他3種算法相比，MDPS算法取得系統(tǒng)吞吐量和公平性之間良好折中的同時，獲得了更好的丟包率性能.

［1］RAMLI H A M，SANDRASEGARAN K，BASUKALA R，et al. Resource allocation technique for video streaming applications in the LTE system［C］//Wireless and Optical Communications Conference(WOCC)，2010 19thAnnual.Shanghai:IEEE，2010:1-5.

［2］ KWAN R，LEUNG C，ZHANG Jie.Proportional fair multiuser scheduling in LTE［J］.Signal Processing Letters，IEEE，2009，16(6):461-464.

［3］PIRO G，GRIECO L A，BOGGIA G，et al.Two-level downlink scheduling for real-time multimedia services in LTE networks［J］.Multimedia，IEEE Transaction on，2011，13(5):1052-1065.

［4］ Basukala R，Mohd Ramli H A，Sandrasegaran K.Performance analysis of EXP/PF and M-LWDF in downlink 3GPP LTE system［C］//First Asian Himalayas International Conference on， AH - ICI 2009.Kathmandu:IEEE，2009:1-5.

［5］ SANDRASEGARANK， MOHDRAMLIH A，BASUKALA R.Delay-prioritized scheduling(DPS)for real time traffic in 3GPP LTE system［C］//Wireless Communications and Networking Conference(WCNC)，2010 IEEE.Sydney:IEEE，2010:1-6.

［6］CAPOZZI F，PIRO G，GRIECO L A，et al.Downlink packet scheduling in lte cellular networks:Key design issues and a survey［J］.IEEE Communications Surveys＆ Tutorials，2012，15(2):678-700.

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

［8］PEDERSEN K I，KOLDING T E，F(xiàn)REDEROLSEN F，et al.An overview of downlink radio resource management for UTRAN long-term evolution［J］.IEEE Communications Magazine，2009，47(7):86-93.

［9］吳大鵬，嚴海升，羅仁澤.面向?qū)崟r業(yè)務(wù)的快速公平性分組調(diào)度算法［J］.重慶郵電大學(xué)學(xué)報:自然科學(xué)版，2013，25(1):85-89.

［10］RAMLI H A M，BASUKALA R，SANDRASEGARAN K，et al.Performance of well known packet scheduling algorithms in the downlink 3GPP LTE system［C］//Communications(MICC)，2009 IEEE 9th Malaysia International Conference on.Kuala Lumpur:IEEE，2009:815-820.

［11］ZHANG Cheng wen，LIU Xin，TAN Xue zhi.Joint resource allocation for MIMO OFDM video transmission systems with unequal error protection［J］.Journal of Harbin Institute Of Technology(New Seriers)，2012，19(2):119-124.