banner.jpg)
相關(guān)專題：
關(guān)鍵詞：IEEE 802.16協(xié)議；寬帶無線接入；加權(quán)公平排隊；服務質(zhì)量
在不久的將來，寬帶城域無線接入(BWA)系統(tǒng)將成為全球通信架構(gòu)中的一個重要的組成部分。隨著無線數(shù)據(jù)服務越來越受歡迎以及用戶多媒體業(yè)務需求的不斷增長，人們提出了對不同層次的業(yè)務提供不同QoS服務的要求。在所有需要被解決的技術(shù)問題中，分組調(diào)度是最重要的(調(diào)度算法提供了帶寬控制、擁塞控制機制)。在傳統(tǒng)的有線網(wǎng)絡(luò)中人們已經(jīng)設(shè)計了許多性能優(yōu)異的公平隊列分組調(diào)度算法，如加權(quán)公平排隊(WFQ)。IEEE 802.16協(xié)議中定義了業(yè)務流的分類和帶寬請求方法，但沒有對具體的調(diào)度算法做出規(guī)定而是將其留給設(shè)備制造商來解決。由于控制消息的統(tǒng)一性，因此采用不同調(diào)度算法的不同廠商的設(shè)備依然可以通用。
1 WFQ分組調(diào)度算法
假設(shè)一個隊列系統(tǒng)總的出口容量為C，F(xiàn) 是建立在這個鏈路上的流的集合，rf, (f∈F )為與每一個流的服務速率。每一個業(yè)務f∈F 建立一個分組隊列，到達的分組以先入先出(FIFO)的順序加入到隊列中，f 中的第i個到達分組的時間戳為t i，第i 個分組的長度為p i(計算單位為字節(jié))，時間戳的計算公式為：
其中VF 為系統(tǒng)的參考虛時鐘，它是由調(diào)度器所保存的變量，F(xiàn) 中所有的隊列都公用一個VF，它是F 中傳輸最后一個分組的時間戳�！ ∈顷犃衒中的第i -1個分組的時間戳，該時間戳定義了分組被調(diào)度的先后順序，WFQ調(diào)度器為每一個到達的分組計算一個時間戳，并以時間戳的順序為服務的順序。虛時鐘VF 是一個分段線性函數(shù)，它用數(shù)學表達式為：
其中B(t 1, t 2)是在時間(t 1, t 2)內(nèi)有業(yè)務的業(yè)務流。當調(diào)度器服務完一個分組后，選擇各個隊列中時間戳最小的分組來服務。
2 IEEE 802.16的QoS架構(gòu)
IEEE 802.16的具體內(nèi)容參見文獻[1]。IEEE 802.16協(xié)議將業(yè)務分為4類：主動授予業(yè)務(UGS)、實時輪詢業(yè)務(rtPS)、非實時輪詢業(yè)務(nrtPS)和盡力傳輸業(yè)務(BE)。
在文獻[2]中，UGS業(yè)務被設(shè)計用來支持實時的、周期性的、固定包大小的業(yè)務流，例如IP語音(VoIP)業(yè)務。在UGS業(yè)務中用戶站(SS)禁止使用任何競爭請求機會，基站(BS)不提供任何單播請求機會給SS，也不允許使用捎帶請求(PiggyBack)。UGS業(yè)務主要的服務參數(shù)為：授予大小、授予間隔、授予抖動。ti為第i個數(shù)據(jù)包被發(fā)送的時間。要求：
t 0+i×授予間隔≤ti≤t 0+i×授予間隔+抖動。
RTPS業(yè)務被設(shè)計用來支持實時的、周期性的、可變包大小的業(yè)務流，例如MPEG流。這項服務需要BS給SS提供周期性的單播輪詢機會以滿足業(yè)務流的實時需要，以便SS去指定想要授予的數(shù)據(jù)傳輸機會的大小。這項服務中SS禁止使用競爭請求和捎帶請求。主要的服務參數(shù)為：輪詢間隔、輪詢抖動、最小預約速率。
nrtPS流被設(shè)計用來支持非實時的、可變包大小的、有一定規(guī)則性的業(yè)務，如高帶寬的FTP。這項服務由BS為其提供單播輪詢請求機會，同時也被允許使用競爭和捎帶請求。關(guān)鍵的服務參數(shù)是：輪詢間隔、最小預約速率、業(yè)務優(yōu)先級。
BE業(yè)務只允許使用競爭和捎帶請求，不允許使用周期性單播請求。主要的QoS參數(shù)是：最小預約業(yè)務速率、業(yè)務優(yōu)先級。
3 WFQ分級分組調(diào)度算法
在文獻[3]中提到了WFQ分級分組調(diào)度算法，其中將業(yè)務分為BE業(yè)務、嚴格的QoS (Hard-QoS)業(yè)務和稍寬松的QoS(Soft-QoS)業(yè)務。
分組調(diào)度算法分兩級共4個部分(見圖1)：
(1)Hard-QoS服務器中的調(diào)度。
(2)Soft-QoS服務器中的調(diào)度。
(3)BE服務器中的調(diào)度。
(4)3個服務器之間的調(diào)度。
(1)、(2)、(3)屬于第二級調(diào)度，(4)屬于第一級調(diào)度。所有這4個部分都是運用WFQ算法來完成的。
文獻[3]中的調(diào)度算法是對分組進行調(diào)度的。IEEE 802.16中最重要的是上行鏈路的帶寬分配策略，本文通過用分級WFQ算法對時隙資源進行調(diào)度來保證各個業(yè)務的QoS。
將IEEE 802.16的QoS定義與分級WFQ算法的定義對應起來，將UGS、rtPS、nrtPS和BE業(yè)務也分為三大類：第一類為周期性固定分配的業(yè)務，這類業(yè)務的B min = B max，包括UGS業(yè)務、rtPS和nrtPS的單播輪詢帶寬請求機會；第二類為有最小帶寬預約的業(yè)務，這類業(yè)務的B min
4 WFQ分級調(diào)度QoS架構(gòu)
本文設(shè)計的結(jié)合WFQ分級調(diào)度算法的QoS架構(gòu)如圖2所示。
WFQ分級調(diào)度算法的QoS架構(gòu)主要由兩個部分組成：調(diào)度控制器、調(diào)度器。
調(diào)度控制器的主要功能包含兩部分：
(1)依據(jù)單播輪詢、競爭、捎帶請求收到的帶寬請求給各個隊列填充適當大小的傳輸機會。調(diào)度器根據(jù)WFQ算法對這些傳輸機會進行調(diào)度。對UGS業(yè)務和周期性的單播輪詢傳輸機會填充特征表[4]。
通過填充特征表，來模擬Hard-QoS周期性規(guī)則數(shù)據(jù)源，只不過在這里數(shù)據(jù)源產(chǎn)生的不是分組，而是一個個的傳輸機會。
對于第二類隊列和第三類隊列，在調(diào)度完一個傳輸機會后必須通過競爭、單播輪詢或捎帶請求來決定下一個傳輸機會的大小，因此調(diào)度控制器負責翻譯接收到的帶寬請求并給各個隊列提供傳輸機會。
(2)調(diào)度控制器根據(jù)收到的各種形式的帶寬請求來控制各個隊列的權(quán)重。第一類隊列中的權(quán)重是以每個第一類隊列的業(yè)務的最小預約帶寬Bmin(f )為權(quán)重。第二類隊列的權(quán)重是以Bmin(f )和priorityf為權(quán)重的。第三類隊列以priorityf為權(quán)重。以上是第二級調(diào)度的權(quán)重分配原則�？傉{(diào)度器即第一級調(diào)度的權(quán)重分配原則為：Hard-QoS調(diào)度器的權(quán)重是
即包括UGS業(yè)務的總帶寬和周期性單播輪詢業(yè)務所占的帶寬；Soft-QoS調(diào)度器的權(quán)重是
即第二類業(yè)務的預約總帶寬；BE調(diào)度器的權(quán)重為：
即除去第一類和第二類業(yè)務所占的帶寬剩余的帶寬。調(diào)度控制器根據(jù)網(wǎng)絡(luò)控制消息和帶寬請求控制所有的隊列和調(diào)度器的權(quán)重。
調(diào)度器的主要功能是根據(jù)各個隊列的權(quán)重對傳輸機會進行二級WFQ調(diào)度。調(diào)度器分4個部分：
(1)Hard-QoS調(diào)度器。
(2)Soft-QoS調(diào)度器。
(3)BE調(diào)度器。
(4)總調(diào)度器。
其中(1)、(2)、(3)屬于第二級調(diào)度，(4)負責對(1)、(2)、(3)調(diào)度器進行第一級調(diào)度。第一類隊列中分組的調(diào)度準則為：
f∈第一類隊列，其中Bmin(f )為第一類隊列中各個業(yè)務流的最小預約帶寬，對于UGS業(yè)務和周期性授予的單播輪詢機會，其最小預約帶寬是Bmin(f )=Bmax(f )，
因此這類業(yè)務所預約的帶寬作為公平排隊算法的權(quán)重經(jīng)過WFQ算法運算過后，選擇所有第一類隊列中的時間戳t i 最小的傳輸機會映射到上行映射(UL-MAP)中去。第二類隊列中分組的調(diào)度準則為：為第二類隊列中的分組計算兩個時間戳
第三類隊列中的分組的調(diào)度原則為：
總調(diào)度器給Hard-QoS調(diào)度器選擇出來的分組計算一個時間戳：
給Soft-QoS調(diào)度器選擇出來的分組計算一個時間戳：
給BE調(diào)度器選擇出來的分組計算一個時間戳：
上面3個時間戳中Vf為總調(diào)度器中保存的傳輸?shù)淖詈笠粋�分組的時間戳，是一個參考虛時間。 是分組所在的第二級調(diào)度器中上一個分組的時間戳。經(jīng)過上面的計算調(diào)度器選擇一個最小的時間戳的分組(即傳輸機會)安排到UL-MAP中。這樣既做到了在3種隊列之間按照權(quán)重分配帶寬又不會造成帶寬的浪費。
5 系統(tǒng)性能分析
WFQ分組調(diào)度算法基于文獻[5]中Bennett和Zhang提出的分級調(diào)度體系結(jié)構(gòu)，將算法應用到IEEE 802.16中，算法本身分析所得到的性能是一樣的。分級公平調(diào)度所采用的算法不一定要限制到WFQ算法上，成熟的公平隊列調(diào)度算法還有改進加權(quán)公平隊列算法(WF2Q)、自時鐘公平隊列算法(SCFQ)、開始時間公平隊列算法(SFQ)等，相應的結(jié)合分級調(diào)度后的算法有分級加權(quán)公平隊列算法(H-WFQ)、分級自時鐘公平隊列算法(H-SCFQ)、分級開始時間公平隊列算法(H-SFQ)、分級改進加權(quán)公平隊列算法(H-WF2Q)等。文獻[4]對各種算法的性能有詳細的仿真結(jié)果。
6 結(jié)論
本文結(jié)合分級WFQ調(diào)度算法，提出了一種適合于IEEE 802.16的有QoS保證的調(diào)度體系結(jié)構(gòu)。該體系結(jié)構(gòu)充分利用IEEE 802.16提供的控制機制，結(jié)合分級WFQ公平隊列調(diào)度算法，在UGS、rtPS、nrtPS和BE業(yè)務之間公平分配帶寬，并保證各種業(yè)務的QoS特性，完成了在IEEE 802.16協(xié)議中留給用戶自己定義的調(diào)度策略。本文只提供一種思路，下一步還應考慮競爭時隙資源的分配和內(nèi)存管理等問題[6]。
7 參考文獻
[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] 李蕾,張曉敏. 應用WFQ的分級、分組調(diào)度算法 [J]. 山東大學學報(工學版),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.
