一種分級WFQ的寬帶無線接入系統(tǒng)QoS架構(gòu)

　　摘要：文章介紹了加權(quán)公平排隊(duì)(WFQ)分組調(diào)度算法和IEEE 802.16的QoS架構(gòu)。在此基礎(chǔ)上，文章結(jié)合分級WFQ分組調(diào)度算法和IEEE 802.16協(xié)議中所提供的控制機(jī)制提出了一種適合于BWA系統(tǒng)的QoS架構(gòu)。該架構(gòu)充分利用IEEE 802.16提供的控制機(jī)制，結(jié)合分級WFQ公平隊(duì)列調(diào)度算法，在主動(dòng)授予業(yè)務(wù)(UGS)、實(shí)時(shí)輪詢業(yè)務(wù)(rtPS)、非實(shí)時(shí)輪詢業(yè)務(wù)(nrtPS)和盡力傳輸業(yè)務(wù)(BE)之間公平分配帶寬，并保證各種業(yè)務(wù)的QoS特性，完成了在IEEE 802.16協(xié)議中留給用戶自己定義的調(diào)度策略。

　　關(guān)鍵詞：IEEE 802.16協(xié)議；寬帶無線接入；加權(quán)公平排隊(duì)；服務(wù)質(zhì)量


　　在不久的將來，寬帶城域無線接入(BWA)系統(tǒng)將成為全球通信架構(gòu)中的一個(gè)重要的組成部分。隨著無線數(shù)據(jù)服務(wù)越來越受歡迎以及用戶多媒體業(yè)務(wù)需求的不斷增長，人們提出了對不同層次的業(yè)務(wù)提供不同QoS服務(wù)的要求。在所有需要被解決的技術(shù)問題中，分組調(diào)度是最重要的(調(diào)度算法提供了帶寬控制、擁塞控制機(jī)制)。在傳統(tǒng)的有線網(wǎng)絡(luò)中人們已經(jīng)設(shè)計(jì)了許多性能優(yōu)異的公平隊(duì)列分組調(diào)度算法，如加權(quán)公平排隊(duì)(WFQ)。IEEE 802.16協(xié)議中定義了業(yè)務(wù)流的分類和帶寬請求方法，但沒有對具體的調(diào)度算法做出規(guī)定而是將其留給設(shè)備制造商來解決。由于控制消息的統(tǒng)一性，因此采用不同調(diào)度算法的不同廠商的設(shè)備依然可以通用。


1 WFQ分組調(diào)度算法
　　假設(shè)一個(gè)隊(duì)列系統(tǒng)總的出口容量為C，F(xiàn) 是建立在這個(gè)鏈路上的流的集合，rf, (f∈F )為與每一個(gè)流的服務(wù)速率。每一個(gè)業(yè)務(wù)f∈F 建立一個(gè)分組隊(duì)列，到達(dá)的分組以先入先出(FIFO)的順序加入到隊(duì)列中，f 中的第i個(gè)到達(dá)分組的時(shí)間戳為t i，第i 個(gè)分組的長度為p i(計(jì)算單位為字節(jié))，時(shí)間戳的計(jì)算公式為：


　　其中VF 為系統(tǒng)的參考虛時(shí)鐘，它是由調(diào)度器所保存的變量，F(xiàn) 中所有的隊(duì)列都公用一個(gè)VF，它是F 中傳輸最后一個(gè)分組的時(shí)間戳�！　　　∈顷�(duì)列f中的第i -1個(gè)分組的時(shí)間戳，該時(shí)間戳定義了分組被調(diào)度的先后順序，WFQ調(diào)度器為每一個(gè)到達(dá)的分組計(jì)算一個(gè)時(shí)間戳，并以時(shí)間戳的順序?yàn)榉��?wù)的順序。虛時(shí)鐘VF 是一個(gè)分段線性函數(shù)，它用數(shù)學(xué)表達(dá)式為：


　　其中B(t 1, t 2)是在時(shí)間(t 1, t 2)內(nèi)有業(yè)務(wù)的業(yè)務(wù)流。當(dāng)調(diào)度器服務(wù)完一個(gè)分組后，選擇各個(gè)隊(duì)列中時(shí)間戳最小的分組來服務(wù)。


2 IEEE 802.16的QoS架構(gòu)
　　IEEE 802.16的具體內(nèi)容參見文獻(xiàn)[1]。IEEE 802.16協(xié)議將業(yè)務(wù)分為4類：主動(dòng)授予業(yè)務(wù)(UGS)、實(shí)時(shí)輪詢業(yè)務(wù)(rtPS)、非實(shí)時(shí)輪詢業(yè)務(wù)(nrtPS)和盡力傳輸業(yè)務(wù)(BE)。


　　在文獻(xiàn)[2]中，UGS業(yè)務(wù)被設(shè)計(jì)用來支持實(shí)時(shí)的、周期性的、固定包大小的業(yè)務(wù)流，例如IP語音(VoIP)業(yè)務(wù)。在UGS業(yè)務(wù)中用戶站(SS)禁止使用任何競爭請求機(jī)會(huì)，基站(BS)不提供任何單播請求機(jī)會(huì)給SS，也不允許使用捎帶請求(PiggyBack)。UGS業(yè)務(wù)主要的服務(wù)參數(shù)為：授予大小、授予間隔、授予抖動(dòng)。ti為第i個(gè)數(shù)據(jù)包被發(fā)送的時(shí)間。要求：
t 0+i×授予間隔≤ti≤t 0+i×授予間隔+抖動(dòng)。


　　RTPS業(yè)務(wù)被設(shè)計(jì)用來支持實(shí)時(shí)的、周期性的、可變包大小的業(yè)務(wù)流，例如MPEG流。這項(xiàng)服務(wù)需要BS給SS提供周期性的單播輪詢機(jī)會(huì)以滿足業(yè)務(wù)流的實(shí)時(shí)需要，以便SS去指定想要授予的數(shù)據(jù)傳輸機(jī)會(huì)的大小。這項(xiàng)服務(wù)中SS禁止使用競爭請求和捎帶請求。主要的服務(wù)參數(shù)為：輪詢間隔、輪詢抖動(dòng)、最小預(yù)約速率。


　　nrtPS流被設(shè)計(jì)用來支持非實(shí)時(shí)的、可變包大小的、有一定規(guī)則性的業(yè)務(wù)，如高帶寬的FTP。這項(xiàng)服務(wù)由BS為其提供單播輪詢請求機(jī)會(huì)，同時(shí)也被允許使用競爭和捎帶請求。關(guān)鍵的服務(wù)參數(shù)是：輪詢間隔、最小預(yù)約速率、業(yè)務(wù)優(yōu)先級。


　　BE業(yè)務(wù)只允許使用競爭和捎帶請求，不允許使用周期性單播請求。主要的QoS參數(shù)是：最小預(yù)約業(yè)務(wù)速率、業(yè)務(wù)優(yōu)先級。


3 WFQ分級分組調(diào)度算法
　　在文獻(xiàn)[3]中提到了WFQ分級分組調(diào)度算法，其中將業(yè)務(wù)分為BE業(yè)務(wù)、嚴(yán)格的QoS (Hard-QoS)業(yè)務(wù)和稍寬松的QoS(Soft-QoS)業(yè)務(wù)。


　　分組調(diào)度算法分兩級共4個(gè)部分(見圖1)：

　　(1)Hard-QoS服務(wù)器中的調(diào)度。
　　(2)Soft-QoS服務(wù)器中的調(diào)度。
　　(3)BE服務(wù)器中的調(diào)度。
　　(4)3個(gè)服務(wù)器之間的調(diào)度。


　　(1)、(2)、(3)屬于第二級調(diào)度，(4)屬于第一級調(diào)度。所有這4個(gè)部分都是運(yùn)用WFQ算法來完成的。
文獻(xiàn)[3]中的調(diào)度算法是對分組進(jìn)行調(diào)度的。IEEE 802.16中最重要的是上行鏈路的帶寬分配策略，本文通過用分級WFQ算法對時(shí)隙資源進(jìn)行調(diào)度來保證各個(gè)業(yè)務(wù)的QoS。


　　將IEEE 802.16的QoS定義與分級WFQ算法的定義對應(yīng)起來，將UGS、rtPS、nrtPS和BE業(yè)務(wù)也分為三大類：第一類為周期性固定分配的業(yè)務(wù)，這類業(yè)務(wù)的B min = B max，包括UGS業(yè)務(wù)、rtPS和nrtPS的單播輪詢帶寬請求機(jī)會(huì)；第二類為有最小帶寬預(yù)約的業(yè)務(wù)，這類業(yè)務(wù)的B min

4 WFQ分級調(diào)度QoS架構(gòu)
　　本文設(shè)計(jì)的結(jié)合WFQ分級調(diào)度算法的QoS架構(gòu)如圖2所示。


　　WFQ分級調(diào)度算法的QoS架構(gòu)主要由兩個(gè)部分組成：調(diào)度控制器、調(diào)度器。
調(diào)度控制器的主要功能包含兩部分：


　　(1)依據(jù)單播輪詢、競爭、捎帶請求收到的帶寬請求給各個(gè)隊(duì)列填充適當(dāng)大小的傳輸機(jī)會(huì)。調(diào)度器根據(jù)WFQ算法對這些傳輸機(jī)會(huì)進(jìn)行調(diào)度。對UGS業(yè)務(wù)和周期性的單播輪詢傳輸機(jī)會(huì)填充特征表[4]。
通過填充特征表，來模擬Hard-QoS周期性規(guī)則數(shù)據(jù)源，只不過在這里數(shù)據(jù)源產(chǎn)生的不是分組，而是一個(gè)個(gè)的傳輸機(jī)會(huì)。


　　對于第二類隊(duì)列和第三類隊(duì)列，在調(diào)度完一個(gè)傳輸機(jī)會(huì)后必須通過競爭、單播輪詢或捎帶請求來決定下一個(gè)傳輸機(jī)會(huì)的大小，因此調(diào)度控制器負(fù)責(zé)翻譯接收到的帶寬請求并給各個(gè)隊(duì)列提供傳輸機(jī)會(huì)。


　　(2)調(diào)度控制器根據(jù)收到的各種形式的帶寬請求來控制各個(gè)隊(duì)列的權(quán)重。第一類隊(duì)列中的權(quán)重是以每個(gè)第一類隊(duì)列的業(yè)務(wù)的最小預(yù)約帶寬Bmin(f )為權(quán)重。第二類隊(duì)列的權(quán)重是以Bmin(f )和priorityf為權(quán)重的。第三類隊(duì)列以priorityf為權(quán)重。以上是第二級調(diào)度的權(quán)重分配原則�？傉{(diào)度器即第一級調(diào)度的權(quán)重分配原則為：Hard-QoS調(diào)度器的權(quán)重是

即包括UGS業(yè)務(wù)的總帶寬和周期性單播輪詢業(yè)務(wù)所占的帶寬；Soft-QoS調(diào)度器的權(quán)重是　　　　　　　　
即第二類業(yè)務(wù)的預(yù)約總帶寬；BE調(diào)度器的權(quán)重為：

即除去第一類和第二類業(yè)務(wù)所占的帶寬剩余的帶寬。調(diào)度控制器根據(jù)網(wǎng)絡(luò)控制消息和帶寬請求控制所有的隊(duì)列和調(diào)度器的權(quán)重。


　　調(diào)度器的主要功能是根據(jù)各個(gè)隊(duì)列的權(quán)重對傳輸機(jī)會(huì)進(jìn)行二級WFQ調(diào)度。調(diào)度器分4個(gè)部分：


　　(1)Hard-QoS調(diào)度器。
　　(2)Soft-QoS調(diào)度器。
　　(3)BE調(diào)度器。
　　(4)總調(diào)度器。


　　其中(1)、(2)、(3)屬于第二級調(diào)度，(4)負(fù)責(zé)對(1)、(2)、(3)調(diào)度器進(jìn)行第一級調(diào)度。第一類隊(duì)列中分組的調(diào)度準(zhǔn)則為：　　

　　f∈第一類隊(duì)列，其中Bmin(f )為第一類隊(duì)列中各個(gè)業(yè)務(wù)流的最小預(yù)約帶寬，對于UGS業(yè)務(wù)和周期性授予的單播輪詢機(jī)會(huì)，其最小預(yù)約帶寬是Bmin(f )=Bmax(f )，


　　因此這類業(yè)務(wù)所預(yù)約的帶寬作為公平排隊(duì)算法的權(quán)重經(jīng)過WFQ算法運(yùn)算過后，選擇所有第一類隊(duì)列中的時(shí)間戳t i 最小的傳輸機(jī)會(huì)映射到上行映射(UL-MAP)中去。第二類隊(duì)列中分組的調(diào)度準(zhǔn)則為：為第二類隊(duì)列中的分組計(jì)算兩個(gè)時(shí)間戳

f∈第二類隊(duì)列，Vf為第二類隊(duì)列中保存的全局虛擬時(shí)間變量；

f∈第三類隊(duì)列，Vf為第三類隊(duì)列中保存的全局虛擬時(shí)間變量，priorityf為第三類隊(duì)列的優(yōu)先級。通過比較這兩個(gè)時(shí)間戳選擇一個(gè)最小的進(jìn)行調(diào)度，若該傳輸機(jī)會(huì)是由Soft-QoS調(diào)度器負(fù)責(zé)調(diào)度，則只增加Soft-QoS調(diào)度器中的虛擬時(shí)間變量；若BE調(diào)度器負(fù)責(zé)調(diào)度，則只增加BE調(diào)度器中的虛擬時(shí)間變量，調(diào)度器間互相不影響。這樣第二隊(duì)列中的分組就做到了由Soft-QoS調(diào)度器和BE調(diào)度器聯(lián)合調(diào)度。


　　第三類隊(duì)列中的分組的調(diào)度原則為：

f∈第三類隊(duì)列，priorityf 為業(yè)務(wù)f的優(yōu)先級參數(shù)。通過給不同的業(yè)務(wù)分配不同的優(yōu)先級參數(shù)來給不同的隊(duì)列分配不同的加權(quán)值，從而在業(yè)務(wù)之間按優(yōu)先級不同分配不同的帶寬資源。
總調(diào)度器給Hard-QoS調(diào)度器選擇出來的分組計(jì)算一個(gè)時(shí)間戳：


給Soft-QoS調(diào)度器選擇出來的分組計(jì)算一個(gè)時(shí)間戳：


給BE調(diào)度器選擇出來的分組計(jì)算一個(gè)時(shí)間戳：



　　上面3個(gè)時(shí)間戳中Vf為總調(diào)度器中保存的傳輸?shù)淖詈笠粋�(gè)分組的時(shí)間戳，是一個(gè)參考虛時(shí)間�！　　　　　∈欠纸M所在的第二級調(diào)度器中上一個(gè)分組的時(shí)間戳。經(jīng)過上面的計(jì)算調(diào)度器選擇一個(gè)最小的時(shí)間戳的分組(即傳輸機(jī)會(huì))安排到UL-MAP中。這樣既做到了在3種隊(duì)列之間按照權(quán)重分配帶寬又不會(huì)造成帶寬的浪費(fèi)。


5 系統(tǒng)性能分析
　　WFQ分組調(diào)度算法基于文獻(xiàn)[5]中Bennett和Zhang提出的分級調(diào)度體系結(jié)構(gòu)，將算法應(yīng)用到IEEE 802.16中，算法本身分析所得到的性能是一樣的。分級公平調(diào)度所采用的算法不一定要限制到WFQ算法上，成熟的公平隊(duì)列調(diào)度算法還有改進(jìn)加權(quán)公平隊(duì)列算法(WF2Q)、自時(shí)鐘公平隊(duì)列算法(SCFQ)、開始時(shí)間公平隊(duì)列算法(SFQ)等，相應(yīng)的結(jié)合分級調(diào)度后的算法有分級加權(quán)公平隊(duì)列算法(H-WFQ)、分級自時(shí)鐘公平隊(duì)列算法(H-SCFQ)、分級開始時(shí)間公平隊(duì)列算法(H-SFQ)、分級改進(jìn)加權(quán)公平隊(duì)列算法(H-WF2Q)等。文獻(xiàn)[4]對各種算法的性能有詳細(xì)的仿真結(jié)果。


6 結(jié)論
　　本文結(jié)合分級WFQ調(diào)度算法，提出了一種適合于IEEE 802.16的有QoS保證的調(diào)度體系結(jié)構(gòu)。該體系結(jié)構(gòu)充分利用IEEE 802.16提供的控制機(jī)制，結(jié)合分級WFQ公平隊(duì)列調(diào)度算法，在UGS、rtPS、nrtPS和BE業(yè)務(wù)之間公平分配帶寬，并保證各種業(yè)務(wù)的QoS特性，完成了在IEEE 802.16協(xié)議中留給用戶自己定義的調(diào)度策略。本文只提供一種思路，下一步還應(yīng)考慮競爭時(shí)隙資源的分配和內(nèi)存管理等問題[6]。


7 參考文獻(xiàn)
[1] IEEE 802.16-2001 IEEE Standard for Local and Metropolitan Area Networks Part 16: Air Interface for Fixed Broadband Wireless Access Systems [S].
[2] Janez Bostic, Gorazd Kandus. MAC Scheduling for Fixed Broadband Wireless Access Systems [EB/OL]. http://www.cs.ucr.edu/~michalis/COURSES/260-03/papers/janez802-16.pdf.
[3] 李蕾,張曉敏. 應(yīng)用WFQ的分級、分組調(diào)度算法 [J]. 山東大學(xué)學(xué)報(bào)(工學(xué)版),2002,32(4): 167?171.
[4] Chu Guosong, Wang Deng, Mei Shunliang. A QoS Architecture for the MAC Protocol of IEEE 802.16 BWA System [C]. ICCCAS2002.
[5] Bennett J C R, Zhang Hui. Hierarchical Packet Fair Queuing Algorithms [EB/OL]. http://www.acm.org/sigs/sigcomm/ccr/archive/1996/conf/
bennett.pdf.
[6] Performance Evaluation of Scheduling Mechanisms for Broadband Networks [EB/OL]. Performance Evaluation of Scheduling Mechanisms for Broadband Networks.