緊急度感知的混合業務分組調度策略

吳大鵬，龔長河，劉喬壽，王汝言

（重慶郵電大學光通信與網絡重點實驗室，重慶400065）

緊急度感知的混合業務分組調度策略

吳大鵬，龔長河，劉喬壽，王汝言

（重慶郵電大學光通信與網絡重點實驗室，重慶400065）

長期演進系統在分組交換域內承載業務，延遲和分組丟棄敏感的實時業務服務質量（quality of service，QoS）難以得到滿足。根據業務優先級差異、業務對延遲的敏感度等約束條件，提出了一種基于虛擬隊列的分組延遲預測方法，進而根據分組延遲的預測結果確定其對系統資源需求的緊急程度，隨后根據分組緊急度對緩存中的分組采用分類調度策略，以最大化系統資源利用率。結果表明，本文提出的調度策略能夠有效地提高實時業務的QoS，改善網絡的性能。

實時業務；調度優先級；服務質量；緊急度

0 引 言

以正交頻分多路復用（orthogonal frequency division multiplexing，OFDM）以及多輸入多輸出（multiple input multiple output，MIMO）為核心技術的長期演進（long term evolution，LTE）系統能夠顯著提高傳統蜂窩無線通信網絡的承載能力，大幅度提升用戶的移動通信體驗［1－2］。由于LTE系統采用分組域承載各類業務，因此，分組調度算法對LTE系統的服務質量（quality of service，QoS）保障至關重要。

相關標準中規定LTE系統主要支持兩類業務，分別為實時業務和非實時業務。眾所周知，非實時業務對延遲的敏感程度較低，實時業務需要網絡提供嚴格的延遲保障［3］。因此，對于資源相對有限的LTE系統，分組調度過程需要針對不同業務類型確定其傳輸的緊迫程度，以更加合理地利用系統資源。針對實時業務的QoS保障問題，國內外研究人員提出了相關解決方案，主要包括比例公平算法、指數公平算法、最大權重延遲優先算法，以上算法的共同特點是每個業務流依照特定的判斷標準來確定調度優先級，即直接根據影響用戶QoS的多個因素來確定調度優先級。正比公平性［4－7］（proportional fair，PF）算法由美國高通公司提出，該算法在對資源進行分配時主要考慮用戶信道條件與公平性兩個方面因素的影響。然而，由于未考慮隊列分組延遲的影響，其無法滿足實時業務對QoS的要求。為了支持實時業務，朗訊貝爾實驗室提出了最大權值延遲優先［8－9］（modified－longest weighted delay first，M－LWDF）算法，除了上述兩方面因素外，所提出的方法還考慮了緩沖區隊頭分組延遲和最大分組延遲，以更加有效地支持實時業務。但M－LWDF算法吞吐量性能的提升是以犧牲用戶之間的公平性為代價的。文獻［10］對PF算法進行了改進，利用隊頭分組延遲和業務允許最大延遲產生相應的調度權重，進而調節其調度優先級，在分組投遞率方面獲得了一定的提升，但無法兼顧用戶的公平性與系統吞吐量。文獻［11］把用戶瞬時速率、平均速率、分組丟棄率、隊頭分組等待延遲、最大允許延遲等參數相結合來確定分組的調度優先級，但是直接把這幾個參數組合在一起來確定調度優先級缺乏一定的理論依據，反而使得用戶的各項性能遠不如其他算法，用戶QoS得不到保障。文獻［12］中以視頻業務延遲為參數估計用戶優先級，進而為其分配系統資源，但該算法的性能提升是以犧牲吞吐量為代價的，且算法復雜度較高。綜上所述，每一種調度策略都有各自的特點，本文提出的調度策略理論依據充足，在兼顧公平性與吞吐量的同時，有效地保證實時業務對延遲性能的需求。

針對上述問題，本文提出了一種帶有延遲估計的分組調度機制，系統根據物理隊列中分組的歷史狀態信息，利用虛擬隊列預測緩存中分組的等待延遲，在此基礎上，確定系統當前所承載的各類分組的傳輸狀態，即緊急程度，進而，根據相關業務的特征確定分組的調度優先級。以在混合業務場景下，有效地為實時業務提供延遲性能保障，同時，在兼顧用戶的公平性與系統吞吐量的前提下，達到降低分組丟棄率的目的，實現系統資源分配最優化。

1 延遲預測

如前所述，LTE系統采用分組域承載各類業務，不同分組的排隊延遲、傳輸延遲等均不相同。對于實時業務來說，系統為其確定了最大允許延遲。為了避免浪費有限的系統資源，系統將主動丟棄超過給定延遲閾值的分組。顯然，根據不同分組的延遲狀態，其等待傳輸機會的緊急程度不同。越接近丟棄閾值的分組其緊急程度越高，若無法及時地為這些分組分配系統資源，則此類分組將由于無法得到調度而被丟棄，從而導致分組丟棄概率上升，系統性能下降。

為了根據分組的傳輸狀態合理地為其分配系統資源，本文提出了一種帶有虛擬隊列的延遲預測方法，如圖1所示，虛線部分表示虛擬隊列，其作用是把緩存中未進入隊列等待調度的分組放在虛擬隊列中模擬調度，進而根據物理隊列中分組歷史狀態信息來估計虛擬隊列中分組的等待延遲，最終確定其調度優先級。可見，采用上述方法可根據分組傳輸狀態獲知緩存中分組的等待延遲，提高延遲較大分組的調度優先級，從而避免這些分組超過最大允許延遲而被丟棄，達到改善網絡性能的目的。

圖1 虛擬隊列

根據現有物理隊列中分組的歷史狀態信息，虛擬隊列可獲知分組到達隊列時間間隔及到達時間。到達時間間隔與每個分組到達時間以及分組數量密切相關，虛擬隊列記錄每個分組到達物理隊列的時間，進而統計相鄰兩個分組到達的時間間隔，并計算分組到達間隔的平均值

式中，tk，i表示分組hi到達物理隊列k的時間；nk表示隊列k中分組的數量。

LTE系統在每個傳輸時間間隔（transmission time interval，TTI）按照分組的優先級執行調度。顯然，分組等待延遲與單個TTI內所調度的分組數量密切相關。在調度分組之前，系統需要通過信道質量指示（channel quality indicator，CQI）來估計用戶x的信道狀態，進而確定其在隊列k中分組的平均吞吐量。因此，物理隊列中第i個分組hi的調度時間Rk，i為

式中，EUx表示用戶x的平均吞吐量；TI表示隊列I中分組到達間隔時間；EUx×TI描述了在一個TTI內可以調度的分組數量表示向上取整。由于分組等待的間隔數量為整數，因此式（2）需要向上取整。

由式（2）可以獲知用戶m中分組hn將在第VRk，n個時間間隔得到調度，即

此外，分組等待延遲的估計值與其到達虛擬隊列的時間直接相關，該參數主要由前一個分組到達時間與物理隊列的到達時間間隔所決定

進而，可獲知分組等待延遲

其主要由分組等待調度的時間間隔、分組到達隊列時間以及監測到分組時所記錄的時間來決定，其中tok表示監測到分組時所記錄的時間。

2 分組分類

對于實時業務來說，延遲是最敏感的參數。顯然，平均延遲是判斷分組緊急狀態的重要衡量指標，因此本文采用該參數確定分組的緊急狀態。根據每個分組的等待延遲估計值可以得到同種業務下分組的平均等待延遲，其由各個業務分組等待延遲總和的平均值確定

然而，單純地根據分組的延遲無法確定其緊急狀態，如前所述，LTE系統中不同業務對延遲的敏感度不同，因此，針對語音業務和視頻業務，本文分別統計其隊頭分組的平均延遲，然后把用戶m中分組hi的等待延遲dm，n與所屬業務類別的平均延遲進行比較，當Dm，n＜dm，n時，則將該分組定義為緊急分組，否則為非緊急分組。

顯然，緊急分組比非緊急分組更接近延遲閾值，若此類分組長期得不到調度將處于“餓死”狀態，甚至直接被丟棄，導致用戶QoS無法得到保障。因此，系統需要首先根據分組的緊急程度確定其調度優先級，然后為其分配資源進行調度，其調度優先級按照下式確定：

式中，Tn，max表示業務允許最大延遲；dm，n表示分組等待延遲；W表示該分組的緊急度。即分組等待延遲越大，越接近業務允許最大延遲，使得分組緊急度越高。

但是，單純地用緊急度來定義分組的優先級并不合理，其主要原因在于LTE中規定了語音業務流的優先級大于視頻業務流，為了避免低優先級分組與高優先級分組競爭系統資源，在分組調度優先級確定過程中需要特別考慮語音業務的調度優先級。當業務緊急度相同時，語音業務最大允許延遲較小，接近丟棄閾值的時間較短，其調度優先級應高于視頻類業務。因此，本文進一步采用業務允許最大延遲作為輔助衡量參數以確定調度優先級，達到提高語音業務調度優先級的目的。引入分組緊急度是為了提高接近丟棄閾值分組的調度優先級。由此可知，緊急分組的調度優先級需要綜合考慮分組緊急度與業務允許最大延遲來制定，如式（8）所示，緊急度越高的分組調度優先級越大，反之則越小，而業務允許最大延遲越大，調度優先級越小，反之則越大。

例如延遲敏感的VoIP語音業務最大允許延遲為20ms［10］，視頻業務最大允許延遲為100ms，按照本文所提出的方式，在緊急度相同的情況下，語音分組的調度優先級就得到了提高。

按照上述方式，在系統為緊急度較高的分組分配資源之后，緊急度較低的非實時業務才能得到調度，為了兼顧系統吞吐量以及用戶公平性，本文引入瞬時速率和平均速率來確定非緊急分組的調度優先級，瞬時速率是為了保證系統吞吐量而引入的參數，瞬時速率越大，則分組調度優先級越大，反之則越小。平均速率是為了保證公平性而引入的參數，若用戶在當前時刻之前所得到的調度機會較多，則其平均速率將隨之增加，為了保證各個用戶之間的公平性，其調度優先級應相應地降低，從而為其他調度機會較少的用戶預留系統資源。其調度優先級為

式中，Rm（t）表示用戶m的瞬時速率，可由自適應調制和編碼模塊（adaptive modulation and coding，AMC）通過CQI反饋信息獲知（t）表示用戶的歷史平均速率，其定義如下：

3 分組調度

本文所提出的分組調度策略基本過程如圖2所示。所提出的策略包含4個階段，分別為虛擬隊列建立及延遲預測階段、平均延遲獲知節點、分組分類階段、調度優先級確定及資源分配階段。

圖2 分組調度過程

步驟1 建立一個虛擬隊列，通過對物理隊列中分組歷史狀態信息的統計，可由式（5）預測出分組延遲；

步驟2 通過式（6）獲知分組平均延遲；

步驟3 首先根據預測的分組延遲以及平均延遲對分組進行分類，高于平均延遲的為緊急分組，反之，歸類為非緊急分組，然后根據式（7）定義分組緊急度；

步驟4 通過式（8）與式（9）對緊急分組以及非緊急分組定義調度優先級，該策略首先為緊急分組分配資源，待緊急分組調度完后，非緊急分組才開始獲得調度機會。

4 數值分析

4．1 仿真場景

本部分采用LTE系統仿真平臺［13］對所提出的分組調度策略進行驗證。仿真場景設置為單小區，視頻業務用戶數為50%，語音業務用戶數為50%，且用戶以3km／h的速度移動。其他仿真參數如表1所示。

表1 參數設置

本文用如下公平標準來判斷系統的公平性：

式中，k表示用戶的數量；xi表示用戶i的平均速率。

4．2 數值仿真結果

本部分將本文所提出的分組調度機制（packet scheduling scheme using virtual queue，PSS－VQ）與典型分組調度算法進行了比較，以驗證本文提出的機制對實時業務的QoS滿足度及對整個系統的影響。其中，文獻［10］提出的延遲感知的分組機制（delay－aware packet scheduling，DAPS）策略在PF算法的基礎上考慮了延遲參數，以確定用戶的調度優先權，在實時業務場景下具有較好的性能。

視頻業務的分組丟棄率如圖3所示，由結果可知，視頻業務的分組丟棄率隨著用戶數增加而增加，當用戶數量超過20后，PSS－VQ與DAPS上升較緩慢，當用戶數達到55時，PSS－VQ較M－LWDF與DAPS算法的視頻分組丟棄率降低了15%左右。

圖3 視頻業務的分組丟棄率

視頻業務的平均延遲如圖4所示，結果表明視頻業務的平均延遲隨著用戶數量的增加而呈現出上升趨勢，PSS－VQ較其他幾種分組調度算法延遲性能優勢明顯，當用戶數達到55時，平均延遲降低7%左右。

視頻業務的公平性如圖5所示，從圖可知，視頻業務的公平性隨著用戶數的增加而降低，但是PSS－VQ降低幅度最小，從用戶數達到30過后優勢較明顯，當用戶數達到55時，公平性提高了9%左右。

圖4 視頻業務的平均延遲

圖5 視頻業務的公平性

視頻業務吞吐量如圖6所示，結果表明視頻業務的PSS－VQ相對M－LWDF有所提高，當用戶數達到55時，PSS－VQ較其他兩種算法性能提高了10%左右。

圖6 視頻業務的吞吐量

M－LWDF、PSS－VQ、DAPS都不同程度考慮到延遲對視頻業務服務質量的影響，但是這3種算法在視頻業務性能上有所差異。本文提出的PSS－VQ根據隊列狀態信息預測分組的緊急程度，將等待傳輸的分組進行分類，根據不同的調度優先級判斷準則為實時業務分配資源。該策略提高了接近延遲閾值分組的調度優先級，避免這類分組超過延遲閾值被丟棄，降低了分組丟棄率，同時提高了用戶公平性。此外，在考慮知道調度優先級判斷準則時，引入了瞬時速率因素，提高了系統吞吐量。

語音業務的分組丟棄率如圖7所示，結果表明隨著用戶數量的增加，語音業務的分組丟棄率不斷增加，當用戶數小于40時，所有的分組調度策略分組丟棄率性能相似，當用戶數繼續增加時PSS－VQ的分組丟棄率較其他兩種分組調度策略增加緩慢，其分組丟棄率方面性能最優。當用戶數達到55時，分組丟棄率降低了30%左右。

圖7 語音業務的分組丟棄率

語音業務的平均延遲如圖8所示，由結果可知，當用戶數小于20時，3種策略性能相仿，隨著用戶數量的增加，語音業務的平均延遲不斷增加，當用戶數達到55時，PSS－VQ較M－LWDF、DAPS提升了15%左右，優勢明顯。

圖8 語音業務的平均延遲

語音業務的公平性如圖9所示，由結果可知，3種調度策略的公平性都在小范圍內變化，公平性性能差異不大。

語音業務的吞吐量如圖10所示，由結果可知，所有的分組調度策略中語音用戶的吞吐量都在小范圍內波動，各種分組調度策略就語音業務的平均吞吐量性能相仿。

語音業務屬于對延遲特別敏感的實時業務。M－LWDF、DAPS調度策略考慮到了延遲對語音業務的性能影響，都加入了與延遲相關的加權因子，其性能差異較小。PSS－VQ調度策略提高了語音業務的調度優先級，在延遲、分組丟棄率性能方面提高顯著，其中，當用戶數達到55時，平均延遲提高了15%左右，分組丟棄率降低30%左右。LTE系統中語音業務是通過VoIP承載，話音編碼器按固定的周期分組輸出，VoIP分為激活期和靜默期。只有在激活期的才有話音業務數據，靜默期無數據輸出，因此，語音業務的吞吐量和公平性性能變化不大。

圖9 語音業務的公平性

圖10 語音業務的吞吐量

4．3 算法時間復雜度分析

對于所提出的PSS－VQ算法，在計算各個業務分組平均延遲時的復雜度為O（n），在計算分組等待延遲時的復雜度為O（1），在計算調度優先級時的復雜度為O（1）。因此，從整個算法流程來看，PSS－VQ算法的時間復雜度為O（n）。

而文獻［10］中DAPS算法的時間復雜度為O（nlog2n），經典的M－LWDF算法的時間復雜度為O（n）。因此，PSSVQ算法的時間復雜度與經典的M－LWDF算法相同，DAPS算法的時間復雜度明顯高于PSS－VQ算法。

5 結 論

針對實時業務的特殊性，本文提出了帶有延遲預測的分組調度機制。其核心思想是利用虛擬隊列預測分組等待延遲，以確定分組的緊急度，進而根據不同的分組調度準則來確定其調度優先級。同時，在確定調度優先級的過程中，充分考慮了語音業務及視頻業務的優先級，以更加合理地為不同業務分配系統資源。結果表明，采用本文所提出的分組調度方法能夠有效地保障語音業務和視頻業務的QoS。

［1］Zeng Y H，Zhu G X，Wu W M，et al．Uplink resource schedu－ling algorithms in LTE system［J］．Journal of Chinese Computer Systems，2012，33（5）：1018－1022．（曾宇輝，朱光喜，吳偉民，等．LTE系統中上行資源調度算法研究［J］．小型微型計算機系統，2012，33（5）：1018－1022．）

［2］Wu S J．A channel quality aware scheduling and resource allocation strategy for downlink LTE systems［J］．Journal of Computational Information Systems，2012，8（2）：695－707．

［3］Liu B，Tian H，Xu L．An efficient downlink packet scheduling algorithm for real time traffics in LTE systems［C］∥Proc．of the Consumer Communications and Networking，2013：364－369．

［4］Choi J，Kim Y H，Lee J H，et al．User throughput estimation for the PF scheduling algorithm under MIMO channel environments［J］．IEEE Wireless Communications Letters，2012，1（5）：528－531．

［5］Li X，Li B，Lan B．Adaptive PF scheduling algorithm in LTE cellular system［C］∥Proc．of the Information and Communication Technology Convergence，2010：501－504．

［6］Chao I F，Chiou C S．An enhanced proportional fair scheduling algorithm to maximize QoS traffic in downlink OFDMA sytems［C］∥Proc．of the Wireless Communications and Networking，2013：239－243．

［7］Choi J G，Bahk S．Cell－throughput analysis of the proportional fair scheduler in the single－cell environment［J］．IEEE Trans．on Vehicular Technology，2007，56（2）：766－778．

［8］Lai W K，Tang C L．QoS－aware downlink packet scheduling for LTE networks［J］．Computer Networks，2013，55（7）：1689－1698．

［9］Iosif O，Banica I．On the analysis of packet scheduling in downlink 3GPP LTE system［C］∥Proc．of the 4th International Conference on Communication Theory，Reliability，and Quality of Service，2011：99－102．

［10］Bae S J，Choi B G，Chung M．Delay－aware packet scheduling algorithm for multiple traffic classes in 3GPP LTE system［C］∥Proc．of the 17th Asia－Pacific Conference on Communications，2011：33－37．

［11］Ramli H A M，Basukala R，Sandrasegaran K，et al．Performance of well known packet scheduling algorithms in the downlink 3GPP LTE system［C］∥Proc．of the 9th Conference on Malaysia International Communications，2009：815－820．

［12］Piro G，Grieco L A，Boggia G，et al．Two－level downlink scheduling for real－time multimedia services in LTE networks［J］．IEEE Trans．on Multimedia，2011，13（5）：1052－1065．

［13］Piro G，Grieco L A，Boggia G．Simulating LTE cellular systems：an open－source framework［J］．IEEE Trans．on Vehicular Technology，2011，60（2）：498－513．

E－mail：wudapengphd＠gmail．com

龔長河（1988－），男，碩士研究生，主要研究方向為LTE分組調度。

E－mail：lr1pgch＠163．com

劉喬壽（1979－），男，副教授，碩士，主要研究方向為泛在網絡、物聯網。

E－mail：liuqs＠cqupt．edu．cn

王汝言（1969－），男，教授，博士，主要研究方向為泛在網絡、全光網絡理論與技術、多媒體信息處理。

E－mail：wangry＠cqupt．edu．cn

Hybrid business packet scheduling policy of emergency degree aware

WU Da－peng，GONG Chang－he，LIU Qiao－shou，WANG Ru－yan
（Key Laboratory of Optical Communication and Networks，Chongqing Univercity of Posts and Telecommunications，Chongqing 400065，China）

The long－term evolution system carries traffic in the packet－switched domain．The quality of service（QoS）of delay and packet loss－sensitive real－time services is difficult to be satisfied．According to the service priorities difference and the constraint condition of delay sensitivity，a virtual－queue－based packet delay prediction strategy is proposed．In the strategy，the packet urgency is determined by the predictable packet delay，and then the packets are classified according to the packet urgency．Compared with other scheduling strategies，results show that the scheduling strategy can improve the QoS of the real－time business effectively，and the network performance can be improved effectively．

real－time services；scheduling priority；quality of service（QoS）；emergency degree

TP 393．04

A

10．3969／j．issn．1001－506X．2015．06．26

吳大鵬（1979－），男，教授，博士，主要研究方向為泛在無線網絡、無線網絡服務質量管理。

1001－506X（2015）06－1399－06

2014－04－25；

2014－09－28；網絡優先出版日期：2014－10－17。

網絡優先出版地址：http：／／www．cnki．net／kcms／detail／11．2422．TN．20141017．1606．006．html

國家自然科學基金（61371097）；重慶市自然科學基金重點項目（CSTC2013JJB40001，CSTC2013JJB40006）；重慶郵電大學青年自然科學基金（A2012－93）資助課題