一種改進的M-LWDF 動態業務調度方法

劉海客，李集林，張華健

（北京衛星信息工程研究所 北京 100086）

一種改進的M-LWDF 動態業務調度方法

劉海客，李集林，張華健

（北京衛星信息工程研究所 北京 100086）

隨著地面無線通信技術的高速發展，無線通信網絡將承載越來越多的高速多媒體業務，為使用戶獲得良好的業務體驗，需要為其提供靈活可靠的服務質量保障。高速業務流的調度方法作為系統QoS保障的重要一環。傳統業務調度方法有的僅考慮業務流的絕對優先級、有的依據業務包等待時延的長短進行調度，這些方法缺乏隨信道質量及吞吐量變化情況的動態調控能力。針對上述問題，提出一種改進型的M-LWDF動態調度方法，通過引入公平性參數與優先級參數，提升業務調度器的性能。通過仿真驗證，改進后的動態調度方法可以使業務流獲得更好的時延及抖動指標。

無線通信網絡；M-LWDF；業務調度算法；實時性業務；公平性

目前地面寬帶無線通信系統發展迅猛，多媒體應用已全面接入無線網絡中，無線通信網絡承載高速業務流的種類將更為繁多。隨著系統中新增業務提供不斷增加，用戶對業務體驗的要求也子不斷提升。因此需要在寬帶無線通信網絡中，為用戶提供良好的服務質量保障功能，針對不同的業務特性，提供不同的QoS保障策略，在用戶無感知的情況下，提升用戶的業務體驗。

在無線通信系統中，業務由有線傳輸到無線發射間的業務調度功能對業務流的延遲、吞吐量、抖動等QoS指標具有較大的影響，因此好的業務流調度器及調度算法將更好的保障業務流的QoS要求[1-2]。傳統調度算法一般采用嚴格優先級調度或加權公平調度等方法，但是該方法在調度的過程中缺乏一種動態調控的功能，不能根據信道質量的變化情況及吞吐量的最低保障要求，在每次調度周期對調度優先級進行有效的調整[3-4]。這種缺乏動態變化的業務調度策略并不能較好的滿足當前網絡中多媒體業務爆炸式增長的現狀。

因此在寬帶無線通信系統的業務調度算法中需引入業務流之間的公平性與差異性調控指標，進而更好的完成高速多媒體業務的調度發送功能。

1　無線高速業務動態調度算法

在當前星狀網絡拓撲結構的寬帶無線通信系統中，系統承載越來越多的高速多媒體業務流，因此中心站到終端站下行業務以及終端站到中心站上行業務的調度算法性能是保障系統業務服務質量的重要環節[5-6]。

由于寬帶無線通信系統主要承載語音、視頻、游戲、上網等多媒體業務，在中心站與終端站中需各實現一個多業務流的調度器結構，并在此調度器結構的基礎上依據設計的調度算法完成業務流調度發送。處于MAC層與IP層之間的業務調度器，其功能是以一定的算法將不同隊列中的業務數據包調度至MAC層中的調度緩沖區中等待發送。業務調度器依照調度算法與系統預設的QoS參數為業務提供調度服務。

1.1業務調度器

在中心站與終端站之間傳輸的數據包括：信令、實時性業務流與非實時性業務流。信令數據應在系統中接受可靠保障，實時性業務流應接受優先保障，而非實時性業務則應接受盡力而為的服務質量保障[7]。為在系統中針對不同類型的數據流提供不同的服務質量保障級別，在業務調度器中建立兩種屬性的QoS隊列：專用隊列和默認隊列。專用隊列主要用來承載系統中的實時性業務流，如語音、視頻等實時流或緩沖流。默認隊列主要分為兩種，一種為專門承載系統信令數據的隊列，可稱之為信令默認隊列，一種為承載非實時性業務流的隊列，可稱為業務默認隊列。

根據系統所承載業務的QoS保障要求，在中心站與終端站中建立多個專用隊列和業務默認隊列，完成系統對實時性業務及非實時性業務的QoS保障及調度發送功能。同時建立一個承載系統信令數據的信令默認隊列，以完成信令數據的周期性發送功能。由專用隊列與默認隊列組成的業務調度器采用多級調度的策略。中心站與終端站業務調度器結構如圖1和圖2所示。

圖1　中心站業務調度器結構

圖2　終端站業務調度器結構

對于承載實時性業務的各種專用隊列，采用實時性調度算法將其中的數據包調度至調度緩沖區中的緩沖隊列中，等待發送。而對于承載系統信令的信令默認承載，采取周期性插入到調度緩沖隊列的調度策略。對業務默認隊列采用優先級調度策略，由于其承載非實時性業務，所以將業務默認隊列的優先級置為最低，即當實時性業務專用隊列為空時，若有空閑的資源則對其進行調度。

中心站的業務調度器與終端站有所不同，由于中心站采用廣播式的方式向所有終端站發送業務數據，因此在調度器中針對非實時性業務引入終端優先級的概念，即發往不同終端的非實時性業務應按優先級接收調度。

具體調度過程如下：首先，通過實時性調度算法計算所有專用隊列的調度優先級，按照優先級次序將各個專用隊列中的分組調度至緩沖區隊列中，同時周期性向緩沖區隊列中插入信令默認隊列中的信令數據。一次調度周期T中，在無線資源未被所有專用隊列占滿的情況下，調度業務默認隊列中的非實時性業務。

1.2改進的M-LWDF算法

在寬帶無線通信系統中，對于實時性業務的調度算法性能將直接關系到系統QoS保障的效果，尤其是當前無線通信系統承載種類繁多的高速多媒體業務流。根據上節所述的業務調度器結構，本節提出一種改進的M-LWDF算法，該算法在調度實時性業務時，將綜合考慮業務流本身的QoS屬性要求與當前信道質量情況。

M-LWDF算法是針對無線高速業務流提出的，其主要思想是將分組包的時延和如何有效利用信道信息平衡考慮，其用戶優先級的計算不僅和用戶當前的信道質量有關，還和數據包的隊列時延有關[8-9]。

對于M-LWDF分組調度算法，分組隊列調度優先級函數表示為：

其中，i和j分別表示用戶和業務類型；Pi，j（t）表示用戶i 的j類業務分組隊列在調度時刻t得到的調度優先級；Rj表示業務j所支持的最大比特速率，其值越高，那么用戶的優先級就越高；r~i，j（t）為用戶i的j類業務在調度周期內所獲得的平均數據率；wi，j（t）為t時刻用戶i的j類業務分組隊列列首的等待時間；Tj和δj分別表示j類業務分組的傳輸時延和丟包率界限。當分組在隊列中的等待時延超過Tj，分組就被丟掉，因此時延限制越大，分組包丟棄的概率就越小。在每個調度周期中將會調度優先級最高的用戶i的j類業務。

M-LWDF算法是一種非公平算法，對于那些由于信道質量下降引起的吞吐量下降的業務流，該算法會造成這類業務的數據包在中心站或終端站側有較大的時延，當時延超過用戶的最大容忍時間時就會被拋棄，進而使得該業務流不能滿足系統預設的QoS保障要求，影響用戶的業務體驗[10-11]。為了降低數據業務流包被丟棄的概率，在中心站側需要對信道條件差的用戶進行補償。基于用戶公平性，在保證用戶分組最小吞吐量的條件下最大化實時業務的用戶數。

同時，寬帶無線通信系統承載多種多樣的多媒體業務流，為了在業務調度的過程中體現不同業務流QoS保障要求的差異性，需要在調度算法中引入QoS標識參數，使具有較高QoS標識優先級的業務獲得更高的調度優先級。假如系統中承載語音、實時視頻、緩沖視頻等業務流，設定語音業務流優先級大于實時視頻流大于緩沖視頻流，則可規定3種業務流的QoS標識分別為1、2、3，因此可以看出，標識數值越大，業務流優先級越低。

針對上述分析，寬帶無線通信系統的業務調度算法需綜合考慮系統的公平性與特定業務流的QoS保障要求。

在M-LWDF算法中引入Q參數與W參數。Q參數用來表示QoS標識，W參數表示吞吐量參數。調度規則為：

其中，Q=qi，j，

qi，j為QoS標識，D為預先定義的用戶最小吞吐量，ci為用戶平均吞吐量的估計，考慮到用戶的公平性，對信道條件好的用戶限制其優先級，使信道條件差的用戶可以得到服務。

算法不僅考慮到信道條件和用戶時延的影響，還考慮到了用戶最小吞吐量保證。對于平均吞吐量開始低于最小吞吐量的用戶，通過一個W權值參數來提高低吞吐量用戶的優先級，增加了系統中用戶之間的公平性。

同時通過引入Q參數，使算法在保證實時性業務分組時延的同時，兼顧QoS標識優先級，并在一定程度上控制了QoS標識對調度判決的影響。

Q參數與W參數可被分別稱為優先級參數與公平性參數，兩者組成的函數采用指數形式，該函數具有非負性，并保持單調遞增趨勢，這種設計方式可以保障被調度業務流吞吐量的平穩性。這種調度算法在調度判決中為高QoS標識的業務數據包提供更多的調度機會，從而適應端到端QoS保障的需求，滿足不同業務數據流對QoS標識優先等級的差異化需求。

可證明采用下列判決表達式的一類調度算法的穩定性：

其中fi，j（·）為非負、無界遞增函數。只要所有的業務分組到達速率之和不超過系統的容量范圍[12-13]。依據該判決表達式設計出的調度算法可保障系統業務流吞吐量最優，因此文中所提的改進型M-LWDF算法具有算法穩定性。

2　算法仿真

為驗證改進型的M-LWDF算法的優越性，在matlab中對改進型M-LWDF算法進行仿真，對比改進前后兩種算法對高速實時性業務數據包的調度延時，并比較兩種算法的優劣性。

在業務建模中建立3種實時性業務流隊列，其中一種用于模擬聚合話音業務，另兩種為普通視頻流業務，在3種業務中將聚合話音業務的QoS標識設置為1，則該業務被映射成為最高優先級。在通信系統中，通常認為話音業務是固定比特速率業務，當通話處在已連接狀態時，可以認為其占用的帶寬是近似不變的。為模擬3種業務信道質量的不同，將聚合話音業務的傳輸速率設置為最低，由此可以模擬承載此業務的無線信道在資源不足情況下，改進型M-LWDF算法對此業務的補償能力。

當大量用戶進行話音業務的連接和掛斷的操作時，此類聚合的話音業務流按統計信息來描述可表示為：用戶業務到達服從泊松分布，通話服務時間間隔服從負指數分布[14-15]。

假設話音業務到達率為λp，均值為μv，則話音業務的到達時間和服務時間可由公式（4）和公式（5）得到。

話音業務可采用馬爾科夫On/Off模型，如圖3所示，從On狀態向Off狀態轉換的速率為μ，從Off狀態向On狀態的轉換速率為λ，用戶處于On狀態和Off狀態的時間分別服從均值為μon和μoff的指數分布，那么話音業務的激活因子為：av=μon/（μon＋μoff）。因此話音業務的平均傳輸速率為avRv，Rv表示語音業務在網絡中傳輸速率[16-18]。

圖3　聚合流話音業務模型

圖4和圖5為M-LWDF算法與改進型M-LWDF算法在業務數據包時延方面的比較圖。其中橫坐標為流入話音隊列中的數據分組個數，縱坐標為第n個數據分組進入隊列的時間與調出隊列時間的差值，也就是聚合話音業務等待調度的時延參數。圖4為使用M-LWDF算法時每個聚合話音分組的調度時延，圖5為使用改進型M-LWDF算法時的調度時延。在系統中模擬較大的鏈路延遲以及丟包情況，用來構造較低信道質量的場景。從圖中可以看出改進型的M-LWDF平均時延小于原算法的平均延時，即使在聚合語音業務所在信道質量較低的情況下，也可以較好地保障其服務質量，在降低平均延時的同時其延時抖動也有較大改善。

圖4　M-LWDF算法業務分組調度時延

圖6為聚合話音業務隊列分組的平均延時，圖中縱坐標為每個分組的延時累加/業務分組個數。從圖中可以看出改進型的M-LWDF算法可使聚合話音業務的分組平均延時降低，故性能好于M-LWDF算法。

圖5　改進型M-LWDF算法業務分組調度時延

圖6　兩種算法業務平均時延對比圖

3　結束語

文中根據無線通信系統業務承載發展情況，提出了一種基于專用隊列和默認隊列的上下行業務調度器結構，針對不同隊列采用不同的調度策略。同時為更好的保障實時性業務的服務質量，提出了一種改進型的實時隊列調度算法，在MLWDF算法中引入優先級參數與公平性參數，使得業務發送調度既可滿足業務流的QoS保障要求，又可對信道質量的變化情況進行響應，提升系統中用戶的業務體驗，并通過matlab仿真驗證其合理性與優越性。

[1]仉娟娟，楊豐瑞.HSDPA中M-LWDF實時業務分組調度算法的改進[J].無線電工程，2009，39:11-13.

[2]XIAN Yong-ju，TIAN Feng-chun.Analysis of M-LWDF fairness and an enhanced M-LWDF packet scheduling mechanism[J].Journal of China Universities of Posts&Telecommunications，2011，18（4）:82-88.

[3]胡永東，吳國新，徐逸卿.M-WiMAX中馬爾可夫預測的MLWDF調度算法研究[J].計算機科學，2014，4（4）:31-35.

[4]Hu L，Ning C，Mao M.Research and simulation on wireless packet scheduling scheme based on High-Speed packet access network[J].Open Mechanical Engineering Journal， 2014，8（1）:92-95.

[5]解冰.未來無線通信系統面向QoS保障的資源分配研究[D].北京郵電大學，2011.

[6]Foronda A，Ohta C，Tamaki H.Scheduling algorithm to provide QoS over a shared wireless link[J].Ieice Trans Commun，2009，92（6）:2160-2167.

[7]Xu C，Xian Y.An enhanced M-LWDF packet scheduling algorithm[M].Recent Advances in Computer Science and Information Engineering.Springer Berlin Heidelberg，2012: 333-338.

[8]Lee J Y，Sorour S，Valaee S，et al.Dynamic parameter adaptation for M-LWDF/M-LWWF scheduling[J].IEEE Transactions on Wireless Communications，2012，11（3）:927-937.

[9]楊鵬，閆俊杰，王汝言.LTE中隊列狀態感知的優化MLWDF調度算法[J].重慶郵電大學學報；自然科學版，2015.

[10]Khan N，Martini M G，Staehle D.QoS-aware composite scheduling using fuzzy proactive and reactive controllers[J]. Eurasip Journal on Wireless Communications&Networking，2014，2014（12）:1189-1200.

[11]Afroz F，Barua S，Sandrasegaran K.Performance Analysis of FLS，EXP，LOG and M-LWDF packet scheduling algorithms in downlink 3GPP LTE System[J].International Journal of Wireless&Mobile Networks，2014，6（5）:77-91.

[12]Alghamdi M，Alghamdi M.Performance comparison of downlink packet scheduling algorithms in LET Network[J]. International Conference on Electrical Engineering Computer Science&Informatics，2014.

[13]姚丹，崔維嘉，季仲梅.基于QCI優先級的分組調度算法[J].計算機工程，2011（9）:141-143.

[14]馮星華，李艷慧.典型話務模型的呼叫中心系統資源計算算法[J].郵電設計技術，2014（6）:76-79.

[15]Sung D H，Park H H，Chung J H，et al.Method for transmitting VoIP packet:WO，US8391311 B2[P].2013.

[16]Ivan R J D S V，Kleinschmidt J H.Capture and analysis of malicious traffic in VoIP environments using a low interaction honeypot[J].Latin America Transactions IEEE，2015，13.

[17]代家強，孫智卿.基于無線網絡技術的智能家居能量管理系統開發及需求側管理應用研究[J].陜西電力，2013 （10）：39-43.

[18]牛博，姚林，曹小行，等.基于3G物聯網的高壓輸電線路多狀態信息監測系統[J].陜西電力，2013（12）：56-60，70.

An improved M-LWDF dynamic traffic scheduling method

LIU Hai-ke，LI Ji-lin，ZHANG Hua-jian
（Beijing Institute of Satellite Information Engineering，Beijing 100086，China）

With the rapid development of wireless communication technology，wireless communication network will carry more and more high-speed multimedia services.It requires a flexible and reliable QoS function to provide users with a good service experience.The scheduling method of high speed traffic flow is an important part of QoS system.The traditional traffic schedule algorithms only consider the absolute priority of the traffic flows，or the waiting time before the packets scheduled. These methods lack the ability of dynamic regulation with the change of channel quality and traffic throughput.In view of the above problems，an improved M-LWDF dynamic scheduling method is proposed.By introducing the fairness parameter and priority parameter，improve the performance of the traffic scheduler.The simulation results show that the improved dynamic scheduling method can make the traffic flows get better delay and jitter index.

wireless communication network；M-LWDF；traffic scheduling algorithm；real-time traffic；fairness

TN915.41

A

1674－6236（2016）22-0026-04

2015-11-18稿件編號：201511166

劉海客（1986—），男，河北秦皇島人，博士研究生。研究方向：計算機網絡、SDN網絡。