要害詞：IEEE 802.16協議；寬帶無線接入；加權公平排隊；服務質量

Abstract:The (WFQ) packet scheduling algorithm and the QoS architecture of IEEE 802.16 are introdUCed. Based on the control mechanism supported by the Hierarchical WFQ packet scheduling algorithm and IEEE 802.16 PRotocols, a QoS architecture for Broadband Wireless access Systems (BWA) is proposed. This architecture can make better use of IEEE 802.16 control mechanism and realize fair bandwidth allocation among the Unsolicited grant Service (UGS), Real Time Polling Service (rtPS), non-Real Time Polling Service (nrtPS) and Best Effort (BE) transmission service. It can also guarantee the QoS of various services, thus implementing the scheduling reserved by IEEE 802.16 for users to make specific definitions.

Key Words:IEEE 802.16 protocol; broadband wireless access; weighted fair queueing (WFQ); QoS

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

1 WFQ分組調度算法
    假設一個隊列系統總的出口容量為C，F 是建立在這個鏈路上的流的集合，rf, (f∈F )為與每一個流的服務速率。每一個業務f∈F 建立一個分組隊列，到達的分組以先入先出(FIFO)的順序加入到隊列中，f 中的第i個到達分組的時間戳為t i，第i 個分組的長度為p i(計算單位為字節)，時間戳的計算公式為：

    其中VF 為系統的參考虛時鐘，它是由調度器所保存的變量，F 中所有的隊列都公用一個VF，它是F 中傳輸最后一個分組的時間戳。        是隊列f中的第i -1個分組的時間戳，該時間戳定義了分組被調度的先后順序，WFQ調度器為每一個到達的分組計算一個時間戳，并以時間戳的順序為服務的順序。虛時鐘VF 是一個分段線性函數，它用數學表達式為：

    其中B(t 1, t 2)是在時間(t 1, t 2)內有業務的業務流。當調度器服務完一個分組后，選擇各個隊列中時間戳最小的分組來服務。

2 IEEE 802.16的QoS架構
    IEEE 802.16的具體內容參見文獻[1]。IEEE 802.16協議將業務分為4類：主動授予業務(UGS)、實時輪詢業務(rtPS)、非實時輪詢業務(nrtPS)和盡力傳輸業務(BE)。

    在文獻[2]中，UGS業務被設計用來支持實時的、周期性的、固定包大小的業務流，例如ip語音(VoIP)業務。在UGS業務中用戶站(SS)禁止使用任何競爭請求機會，基站(BS)不提供任何單播請求機會給SS，也不答應使用捎帶請求(PiggyBack)。UGS業務主要的服務參數為：授予大小、授予間隔、授予抖動。ti為第i個數據包被發送的時間。要求：
t 0+i×授予間隔≤ti≤t 0+i×授予間隔+抖動。

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

    nrtPS流被設計用來支持非實時的、可變包大小的、有一定規則性的業務，如高帶寬的FTP。這項服務由BS為其提供單播輪詢請求機會，同時也被答應使用競爭和捎帶請求。要害的服務參數是：輪詢間隔、最小預約速率、業務優先級。

    BE業務只答應使用競爭和捎帶請求，不答應使用周期性單播請求。主要的QoS參數是：最小預約業務速率、業務優先級。

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

    分組調度算法分兩級共4個部分(見圖1)：

    (1)Hard-QoS服務器中的調度。
    (2)Soft-QoS服務器中的調度。
    (3)BE服務器中的調度。
    (4)3個服務器之間的調度。

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

    將IEEE 802.16的QoS定義與分級WFQ算法的定義對應起來，將UGS、rtPS、nrtPS和BE業務也分為三大類：第一類為周期性固定分配的業務，這類業務的B min = B max，包括UGS業務、rtPS和nrtPS的單播輪詢帶寬請求機會；第二類為有最小帶寬預約的業務，這類業務的B min <B max，包括rtPS和nrtPS，這類業務為了保證rtPS的實時性，并將rtPS和nrtPS業務進行隔離，對rtPS設計了比nrtPS更高的優先權，即當rtPS的時間戳和nrtPS的時間戳一樣的時候，優先選擇rtPS來傳輸；第三類為沒有最小帶寬預約的業務，這類業務B min=0，因此這類業務包括BE業務和最小預約帶寬為0的nrtPS業務。

4 WFQ分級調度QoS架構
    本文設計的結合WFQ分級調度算法的QoS架構如圖2所示。

    WFQ分級調度算法的QoS架構主要由兩個部分組成：調度控制器、調度器。
調度控制器的主要功能包含兩部分：

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

    對于第二類隊列和第三類隊列，在調度完一個傳輸機會后必須通過競爭、單播輪詢或捎帶請求來決定下一個傳輸機會的大小，因此調度控制器負責翻譯接收到的帶寬請求并給各個隊列提供傳輸機會。

    (2)調度控制器根據收到的各種形式的帶寬請求來控制各個隊列的權重。第一類隊列中的權重是以每個第一類隊列的業務的最小預約帶寬Bmin(f )為權重。第二類隊列的權重是以Bmin(f )和priorityf為權重的。第三類隊列以priorityf為權重。以上是第二級調度的權重分配原則?？傉{度器即第一級調度的權重分配原則為：Hard-QoS調度器的權重是

即包括UGS業務的總帶寬和周期性單播輪詢業務所占的帶寬；Soft-QoS調度器的權重是
                                                  
即第二類業務的預約總帶寬；BE調度器的權重為：

即除去第一類和第二類業務所占的帶寬剩余的帶寬。調度控制器根據網絡控制消息和帶寬請求控制所有的隊列和調度器的權重。

    調度器的主要功能是根據各個隊列的權重對傳輸機會進行二級WFQ調度。調度器分4個部分：

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

    其中(1)、(2)、(3)屬于第二級調度，(4)負責對(1)、(2)、(3)調度器進行第一級調度。第一類隊列中分組的調度準則為：       

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

    因此這類業務所預約的帶寬作為公平排隊算法的權重經過WFQ算法運算過后，選擇所有第一類隊列中的時間戳t i 最小的傳輸機會映射到上行映射(UL-MAP)中去。第二類隊列中分組的調度準則為：為第二類隊列中的分組計算兩個時間戳

f∈第二類隊列，Vf為第二類隊列中保存的全局虛擬時間變量；

f∈第三類隊列，Vf為第三類隊列中保存的全局虛擬時間變量，priorityf為第三類隊列的優先級。通過比較這兩個時間戳選擇一個最小的進行調度，若該傳輸機會是由Soft-QoS調度器負責調度，則只增加Soft-QoS調度器中的虛擬時間變量；若BE調度器負責調度，則只增加BE調度器中的虛擬時間變量，調度器間互相不影響。這樣第二隊列中的分組就做到了由Soft-QoS調度器和BE調度器聯合調度。

    第三類隊列中的分組的調度原則為：

f∈第三類隊列，priorityf 為業務f的優先級參數。通過給不同的業務分配不同的優先級參數來給不同的隊列分配不同的加權值，從而在業務之間按優先級不同分配不同的帶寬資源。
總調度器給Hard-QoS調度器選擇出來的分組計算一個時間戳：

給Soft-QoS調度器選擇出來的分組計算一個時間戳：

給BE調度器選擇出來的分組計算一個時間戳：

    上面3個時間戳中Vf為總調度器中保存的傳輸的最后一個分組的時間戳，是一個參考虛時間。            是分組所在的第二級調度器中上一個分組的時間戳。經過上面的計算調度器選擇一個最小的時間戳的分組(即傳輸機會)安排到UL-MAP中。這樣既做到了在3種隊列之間按照權重分配帶寬又不會造成帶寬的浪費。

5 系統性能分析
    WFQ分組調度算法基于文獻[5]中Bennett和Zhang提出的分級調度體系結構，將算法應用到IEEE 802.16中，算法本身分析所得到的性能是一樣的。分級公平調度所采用的算法不一定要限制到WFQ算法上，成熟的公平隊列調度算法還有改進加權公平隊列算法(WF2Q)、自時鐘公平隊列算法(SCFQ)、開始時間公平隊列算法(SFQ)等，相應的結合分級調度后的算法有分級加權公平隊列算法(H-WFQ)、分級自時鐘公平隊列算法(H-SCFQ)、分級開始時間公平隊列算法(H-SFQ)、分級改進加權公平隊列算法(H-WF2Q)等。文獻[4]對各種算法的性能有具體的仿真結果。

6 結論
    本文結合分級WFQ調度算法，提出了一種適合于IEEE 802.16的有QoS保證的調度體系結構。該體系結構充分利用IEEE 802.16提供的控制機制，結合分級WFQ公平隊列調度算法，在UGS、rtPS、nrtPS和BE業務之間公平分配帶寬，并保證各種業務的QoS特性，完成了在IEEE 802.16協議中留給用戶自己定義的調度策略。本文只提供一種思路，下一步還應考慮競爭時隙資源的分配和內存治理等問題[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的分級、分組調度算法 [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.

楊博，西安電子科技大學ISN國家重點實驗室在讀碩士生，主要從事無線寬帶城域網絡的研究。

劉琰，西安電子科技大學ISN國家重點實驗室在讀碩士生，主要從事無線寬帶城域網絡和擴頻通信方面的研究。

劉乃安，西安電子科技大學ISN國家重點實驗室MCN室主任，教授。主要從事移動計算網絡、擴展頻譜通信、無線通信、移動通信的研究工作。已發表論文20余篇，出版教材和著作3部、譯著1部，承擔國家自然科學基金項目、國家“863”計劃項目及中外合作項目多項。