無線接入網絡自適應公平調度算法

楊璐，吳清亮

(1. 東南大學 計算機科學與工程學院，江蘇 南京 210096；

2. 東南大學 計算機網絡和信息集成教育部重點實驗室，江蘇 南京 210096）

1 引言

在“面向服務”的無線/移動通信系統中，評價一個系統性能好壞的標準并不局限于系統的總服務流量，更重要的是提供給用戶的服務滿意程度，即對服務提供的質量保障。但是無線網絡的核心矛盾是無線資源匱乏以及無線網絡結構與帶寬的動態特性、大時延、高速移動性等因素對應用服務質量的保障。例如無線網絡中鏈路特性及終端的移動性造成網絡資源的動態變化，為無線網絡資源管理和分配帶來了困難，所以如何有效地動態管理和動態自適應分配網絡資源以滿足用戶對移動性、多元化應用和服務質量保障的需求已成為無線網絡亟需解決的問題。

在傳統的有線網絡中，調度是其中很重要的環節，調度也稱動態資源分配，它可根據不同服務需求保障服務的帶寬分配，并可保障服務的時延要求。調度算法大都以報文或時隙為單位決定流或報文的發送，主要任務包括2方面：一是決定報文的發送時間（即不同用戶報文發送次序），稱為分組調度；二是決定不同流或用戶應得的資源份額，稱為流調度。目前有線網絡中已有很多成熟的公平調度算法，包括加權輪循（WRR， weighted round robin）等基于報文結構的算法以及與廣義處理器共享（GPS， generalized processor sharing）相關的公平調度算法。但是這些調度算法無法直接應用于無線網絡，主要是因為無線信道與有線信道相比具有很大的特殊性，主要表現在無線終端的移動性、無線帶寬的時變性和有限性以及無線信道的高誤碼率。因此無線網絡分組調度算法需要結合無線網絡鏈路的特點對調度策略進行調整，所以為了有效地分配無線信道資源和提高系統服務質量(QoS)，無線網絡分組調度算法需要考慮下列準則：保證用戶之間的公平性；動態適應無線鏈路的變化；滿足特定服務的 QoS 要求；提高系統吞吐量和無線信道利用率；服務質量的平滑過渡和降低系統復雜度等。

最近出現了一些對無線網絡調度算法的研究，提出了許多調度算法和時延保障與滯后補償方式以及再分配模型。文獻[1～3]討論了對不同服務類別采用不同的帶寬補償方式。文獻[1]中，僅針對同類別的服務進行帶寬補償，沒有考慮非同類別的服務補償；文獻[2]提出了一種自適應的分組調度算法，根據超前流與滯后流的隊長極限分別調整其補償權重，具有優化吞吐率和平滑超前流的服務質量的良好效果；而文獻[3]的補償方式僅是簡單地對低級別服務進行懲罰。文獻[1～3]中也考慮了通過自適應調整服務類別權重來保障服務的QoS需求。文獻[4]綜述了一些無線調度算法的研究。

本文提出了一種具有服務區分能力和服務質量保障的二級結構自適應公平調度算法，對剩余帶寬進行公平分配，并且確保時延，保障分組隊列的服務質量平滑降級。考慮到無線信道的特殊性，算法引入了補償和再分配模式。其中補償模式又分為流級和分組級。流級補償針對滯后流按照其預約速率的固定比例進行補償，分組級的補償采用對報文隊列進行不同權重的補償。

2 無線網絡二級結構自適應公平調度模型

本文把無線接入網絡看作是有線網絡的擴展[5]，將它分為2個部分：無線接入部分和有線核心網絡。網絡按區域劃分，每個區域有唯一的基站作為無線接入點，各個區域之間由基站相連。基站和移動終端之間的通信分為上行和下行，由基站統一調度。本文假定一個用戶到基站之間的通信為一個報文數據流，各用戶與基站的通信是獨立的，也就是用戶到基站的鏈路是獨立的；同時假定網絡存在區分服務機制，在有線網絡的邊界路由器將進入無線鏈路的單個服務流按QoS要求分類，聚合成不同的流聚集，聚集信息存儲于流聚集每個報文的 DS（different service）標記域中，稱為 DSCP（differentiated service code point），流聚集通過DSCP標示自己在調度時根據報文頭DSCP提供每跳轉發（PHB）服務。

無線網絡資源調度算法需要結合其鏈路的特點對調度策略進行調整。當由于誤碼或其他原因造成某連接暫時中斷，為了對帶寬進行充分利用，應考慮將這部分閑置的信道分配給其他連接；而當中斷連接恢復傳輸后，應該對其進行補償，實現公平性。這種補償模式正是無線資源調度與有線調度算法的最重要區別。它決定了獲得額外帶寬的流如何對從中斷恢復正常的流進行補償。本文假設整個網絡為無任何鏈路故障的理想狀態，對每個連接對應一個變量flag來區分各個報文數據流的排隊狀態。通過flag的值將報文數據流分為同步流、超前流和滯后流3種狀態[6,7]。

圖1是本文提出的無線接入網絡二級結構自適應公平調度模型。

圖1 無線網絡二級結構自適應公平調度模型

該模型由流級的具有服務區分的自適應公平調度和分組級具有服務質量保障的與隊列平滑服務的分組調度組成。流級和分組級的補償都是必須的，流級補償反映為信道變化時要求重新分配權重，分組級補償反映為不同的發送時間和隊列長度權重分配。流級補償使用比例方式和歸一化的權重分配機制，它能有效地進行服務區分和自適應信道變化，保障無線網絡用戶之間的長期公平性。而分組級補償采用公平分組調度和隊列權重分配機制。該機制的應用能夠保障服務的短期公平性和服務質量，并且有利于保障不同隊列服務質量的平滑過渡。

3 無線網絡二級結構自適應公平調度算法

根據二級結構的無線網絡自適應公平調度模型，本文提出一種無線網絡自適應公平調度算法(TWFS, two-level wireless fair scheduling)。

3.1 流調度

定義1 （額外帶寬）由于鏈路故障，基站（調度器）將原報文數據流所占有帶寬分配給其他的流。這部分帶寬被分配給那些有報文等待的、以可變比特率傳輸的無差錯狀態連接，稱之為額外帶寬[6,7]。

定義2 （時變帶寬）如果出現帶寬的時變性，即動態容量的變化，使得帶寬發生變化，使用歸一化權重比例分配機制，稱為時變帶寬。

本算法按照各個連接的權重對額外帶寬和時變帶寬進行公平分配，每個可變比特率無差錯狀態連接所獲得的額外帶寬正比于它的權重。這里以ri、wn、wb、wl分別表示服務 i、滯后流、超前流和同步流的權重。

當系統有f個流連接時，初始化的權重分配根據服務類型進行比例分配，所以權重的分配即表示了帶寬的分配關系，亦即可以反應在不同的發送速率選擇上。其所有權重分配如式(1)所示：

當有流完成傳輸任務或有新的流加入時，要進行權重的再分配以保持公平性。每當有連接狀態發生變化時（包括監測到故障恢復）或流傳輸結束后，其權重歸還整個系統。

一般一個流地加入其權重的分配，根據其服務類型分配固定比特率連接權重與可變比特率連接權重： rj= rcj+ rvj。

當流k的鏈路發生故障時，其歸還權重 rk，其他的流對其權重進行公平比例分配。

可變比特率連接權重的更新公式為

當流k恢復轉輸的時候，由超前流的可變比特率連接權重進行補償，而同步流和滯后流前期獲得的額外服務并不回吐，根據式(3)：

補償直到該流i成為同步流為止。此時其權重根據其服務類型視同如新流加入一樣分配。同時超前流m因流k而獲得的額外服務完全補償完成時或由超前流變成同步流時停止流m對此流的補償，如果超前流m沒有因此流而獲得額外服務則不在考慮范圍內。

同時，為避免過多的權重計算和減少路由器與端節點重新協商發送速率次數，本文使用一個效用參數即鏈路的使用效率β，即一段時間內當歸還權重少于1-β的時候不進行權重的計算。

3.2 分組調度

TWFS算法的分組級隊列調度算法基礎采用STFQ[8]和WF2Q[9]2種算法相結合的公平調度策略，原理是：當一個報文到達時，更新其時間標志，每個流均由報文序列組成，流中的報文采用FIFO的順序，流f的第i個報文 pj的到達時間是A（pj），ff該報文將被分配一個起始標識S（pj）和一個結束f標識F （ pj），如式(4)所示：f

lj是流f的第j個報文的長度，ψ 是流f的ff權；v (t)是時刻t的虛擬時間B(t)為在t時刻所有的準備就緒的流的集合，C (t)為t時刻的信道容量，流的標識為該流中的第一個報文的起始標識。

當一個報文被傳輸完畢后，下一個報文被選擇，所使用的策略如下：

1) 在所有的起始標識小于等于 v(t) +l的流中，選擇具有最小結束標識的流；

2) 如果沒有這樣的流，那么選擇帶有最小起始標識的流來處理。

在STFQ和WF2Q算法中，其權重值為一固定的值，并不針對隊列長度、帶寬的變化和QoS需求、排隊時延等諸多因素考慮，因此不能很好地自適應于無線網絡的動態變化性。但是，由于無線信道的變化與各用戶服務傳輸需求的差異性，調度算法還應該顧及各用戶等待傳輸數據量的情況。在傳輸“流”的形式數據服務時，信道質量好的用戶對應的等待數據量可能較少，僅調度該隊列的數據服務在高速無線共享信道上傳輸就無法充分利用信道資源，造成系統的無線信道利用率降低。調度器在使用每個資源單元前可以綜合分析信道狀態、隊列中等待數據量和數據報文傳輸時延3方面因素對各用戶調度優先級的影響來確定資源單元的調度方案。

一種新的同時兼顧數據報文的時延、信道狀態變化和各隊列中等待數據量對調度方案影響的下行共享信道調度算法。進行流權重的修改，考慮隊列長度的影響，平滑降低服務質量。

在文獻[4]中不對 3個隊列權重更新，其只更新了超前流的權重和滯后流的權重，對同步流保持不變。如果不進行 3個隊列權重更新，會出現什么情況呢？3個隊列并不進行權重的自適應，會造成其排隊隊列循環出現大隊列的情況，理想的情況是 3個隊列比較合理地分配隊長，并且逐漸減少滯后流，穩定同步流和超前流隊長。

更新3個隊列權重值的方法有2種。

方法1 利用3個隊列（滯后流、同步流、超前流）的隊長比值分配不同的權值。

方法 2 3個隊列權重更新可以根據隊尾報文的虛時間與QoS時延要求之間的差，這個差與排隊時間的比值來決定權值的分配。

本文認為方法1更適合權重值的更新，因為這是一種簡單有效的方法，計算量小，更新不會太頻繁。為了給滯后流更多的補償，可以加大超前流的隊長極值，盡量使用較小的滯后流的隊長閾值。

因此對于分組級隊列權重分配如下，設定ψf的時變表達示ψi(t )，根據流i的到達時間判斷流所屬隊列，而后進行權重的分配，其分配公式如下：

至此得到了一種無線網絡自適應公平動態資源調度算法，該算法可以對流服務類型進行區分和服務質量保障以及報文隊列補償的平滑流服務質量。

4 仿真實驗及結果分析

本文使用的仿真器是ns-2，仿真實驗網絡的拓撲如圖2 所示。節點1至n通過的帶寬為10Mbit/s有線鏈路與節點A相連，而節點B和C則通過帶寬為2Mbit/s無線鏈路連接。

圖2 仿真實驗網絡拓撲結構

通過帶寬的時變性與擁塞發生狀況下服務質量保障與隊列長度變化來考察算法的性能。假設有3服務類 1、2、3，從節點 1、2、3中出來的數據流分別對應3個服務類，也就是說從節點i出來的數據流為服務類i，i=1，2，3。節點A中的緩沖區大小為200kbyte。節點4給出干擾流量。

在實驗中，每個服務類包括一個數據流，其分布和分配的帶寬如表 1所示。音頻（audio）流每20ms發送160byte報文，而視頻（video）流每33ms發送8kbyte的報文，其他數據流發送4kbyte報文，而FTP數據流是持續發送的。

表1 實驗中的數據流

本文實驗中給音頻數據流設定的固定比特率權重參數為 0.3，給視頻數據流設定固定比特率權重參數0.4，其他數據流的固定比特率權重參數為0.1。

圖3顯示了各服務類數據流的權重分布。從圖3中可以看出，TWFS算法能較好地滿足不同服務類型的比例區分。其中權重的隨機小幅波動表現了可變比特率權重和隊列權重分配以及類型 4的On-off流量影響，當類型4的流進行傳輸時，發生網絡擁塞，TWFS算法能夠根據網絡擁塞情況實時調節各服務類的比例權重。

圖3 權重的變化

同時考察TWFS在帶寬的時變性與擁塞發生狀況下的比例公平性之外，本實驗記錄下了這段時間內超前流、同步流、滯后流3個隊列長度的變化情況分別如圖4和圖5所示。

圖4 帶流隊列服務質量平滑的隊列長度變化

圖5 不帶流隊列服務質量平滑的隊列長度變化

圖4 和圖5分別顯示了帶流隊列服務質量平滑與不帶流隊列服務質量平滑的超前流、同步流、滯后流隊列長度的變化情況。從圖中可以看出，由于TWFS算法采用了流隊列服務質量平滑，使得超前流、同步流、滯后流隊列長度保持在一個穩定的狀態下。而不采用流隊列服務質量平滑的隊列長度呈現出較大的波動，系統不能有效地平衡網絡中的超前流、同步流、滯后流于一個穩定狀態。用戶的數據流總是在3種狀態下來回切換，使得服務質量時好時壞。這種情況下用戶服務質量不能得到有效保障，同時也不利于提高網絡利用率。

5 結束語

本文首先對無線網絡自適應公平調度問題進行了深入分析，在此基礎上針對無線網絡應用環境提出了一種具有服務區分與服務質量保障的二級結構自適應公平調度模型，然后在該模型的指導下設計出一種無線網絡自適應公平動態資源調度算法——TWFS。采用二級結構的自適應補償調度策略，可以使公平性和自適應性以及QoS確保都得到保障，為無線網絡的差異性多服務質量傳輸提供了可行方案。最后用仿真方法驗證了TWFS算法的穩定性、短期公平性和長期公平性。下一步的主要工作是在更復雜的隊列模型，如多狀態的馬爾科夫排隊模型中，結合無線網絡流量的固有特性如自相似性、短連接性等對調度算法進行研究。

[1] MOORMAN J, LOCKWOOD J, KANG S. Wireless quality of service using multiclass priority fair queuing [EB/OL]. http: //iwander.vlsi.uiuc.edu/wireless/papers/jsac00.ps,2000.

[2] KUOCHEN W, CHIN Y L. A fair scheduling algorithm with adaptive compensation in wireless networks[A]. GLOBECOM’2001[C]. San Antonio, Texas, 2001. 3543-3547.

[3] ECKHARDT D A, STEENKISTE P. Effort-limited fair (ELF) scheduling for wireless networks[A]. INFOCOM’2000[C]. Tel Aviv, Israel,2000. 1097-1106.

[4] CAO Y, LI V. Scheduling algorithms in broad-band wireless networks[J]. Proceedings of the IEEE, 2001, 1: 76-81.

[5] NANDAGOPAL T, LU S, BHARGHAVAN V. A unified architecture for the design and evaluation of wireless fair queueing algorithms[J].Wireless Networks, 2002, 8(2/3): 231-24.

[6] 宋艦, 李樂民. 一種按比例補償的公平調度算法. 電子與信息學報,2004,26(5):777-782.SONG J, LI L M. Wireless fair scheduling algorithm using proportional compensation mode[J]. Journal of Electronics and Information Technology, 2004,26(5):777-782.

[7] 宋艦, 李樂民. 一種支持服務類別的無線公平調度算法. 電子學報,2004, 32(1): 59-63.SONG J, LI L M. A wireless fair scheduling algorithm supporting CoS[J]. Chinese Journal of Electronics, 2004, 32(1): 59-63.

[8] PAWAN G, HARRICK M V, HAICHEN C. Start-time fair queuing a scheduling algorithm for integrate services packet switching networks[EB/OL]. http://www.acm.org/SIGCOMM, 1996.

[9] JON C R, BENNETT K, HUI Z. WF2Q: Worst - case fair weighted fair queuing [EB/OL]. http:// www1acm1org/ INFOCOM, 1996.