LTE系統中一種低丟包率的實時業務調度算法

吳宣利，韓杏玲，趙婉君

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

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

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

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

1 系統模型

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

表1 LTE下行系統參數設置

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

上可以獲得的理論數據速率:

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

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

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

表2 MCS與SINR映射表［7］

2 算法分析

2.1M－LWDF算法

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

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

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

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

2.2 EXP/PF算法

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

其中

式中NUE為下行系統中用戶數目.

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

2.3 DPS算法

針對LTE系統中實時視頻流業務對丟包率非常敏感的特點，研究人員提出了DPS算法，該算法的優先級為

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

2.4MDPS算法

本文所提出的MDPS算法在DPS算法的基礎上，綜合考慮了用戶的時延狀況和信道狀態，每個用戶的優先級為

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

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

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

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

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

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

輸入:

系統調度時隙數目:NTTⅠ

系統資源塊數目:NPRB

接入系統用戶數目:NUE

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

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

用戶GBR要求:GBR輸出:

資源塊分配矩陣:allocation-RB

1)賦值i_TTⅠ=1;

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

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

4)根據式(9)挑選優先級最高用戶K接受調度;

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

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

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

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

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

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

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

3 仿真分析

3.1 仿真環境

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

表3 系統仿真參數設置

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

3.2 仿真結果

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

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

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

圖1 丟包率對比

圖2 系統吞吐量對比

圖3 用戶間的公平性指數對比

4 結語

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

［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無線資源調度算法的研究［D］.哈爾濱:哈爾濱工業大學，2012.

［8］PEDERSEN K I，KOLDING T E，FREDEROLSEN 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］吳大鵬，嚴海升，羅仁澤.面向實時業務的快速公平性分組調度算法［J］.重慶郵電大學學報:自然科學版，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.