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

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

緊急度感知的混合業(yè)務分組調度策略

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

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

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

實時業(yè)務；調度優(yōu)先級；服務質量；緊急度

0 引 言

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

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

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

1 延遲預測

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

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

圖1 虛擬隊列

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

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

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

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

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

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

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

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

2 分組分類

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

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

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

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

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

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

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

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

3 分組調度

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

圖2 分組調度過程

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

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

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

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

4 數值分析

4．1 仿真場景

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

表1 參數設置

本文用如下公平標準來判斷系統(tǒng)的公平性：

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

4．2 數值仿真結果

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

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

圖3 視頻業(yè)務的分組丟棄率

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

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

圖4 視頻業(yè)務的平均延遲

圖5 視頻業(yè)務的公平性

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

圖6 視頻業(yè)務的吞吐量

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

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

圖7 語音業(yè)務的分組丟棄率

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

圖8 語音業(yè)務的平均延遲

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

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

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

圖9 語音業(yè)務的公平性

圖10 語音業(yè)務的吞吐量

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

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

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

5 結 論

針對實時業(yè)務的特殊性，本文提出了帶有延遲預測的分組調度機制。其核心思想是利用虛擬隊列預測分組等待延遲，以確定分組的緊急度，進而根據不同的分組調度準則來確定其調度優(yōu)先級。同時，在確定調度優(yōu)先級的過程中，充分考慮了語音業(yè)務及視頻業(yè)務的優(yōu)先級，以更加合理地為不同業(yè)務分配系統(tǒng)資源。結果表明，采用本文所提出的分組調度方法能夠有效地保障語音業(yè)務和視頻業(yè)務的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系統(tǒng)中上行資源調度算法研究［J］．小型微型計算機系統(tǒng)，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－h(huán)e，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；網絡優(yōu)先出版日期：2014－10－17。

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

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