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

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)系統(tǒng)將成為全球通信架構(gòu)中的一個(gè)重要的組成部分。隨著無線數(shù)據(jù)服務(wù)越來越受歡迎以及用戶多媒體業(yè)務(wù)需求的不斷增長，人們提出了對(duì)不同層次的業(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ù)流的分類和帶寬請(qǐng)求方法，但沒有對(duì)具體的調(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ìng)爭(zhēng)請(qǐng)求機(jī)會(huì)，基站(BS)不提供任何單播請(qǐng)求機(jī)會(huì)給SS，也不答應(yīng)使用捎帶請(qǐng)求(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禁止使用競(jìng)爭(zhēng)請(qǐng)求和捎帶請(qǐng)求。主要的服務(wù)參數(shù)為：輪詢間隔、輪詢抖動(dòng)、最小預(yù)約速率。

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

    BE業(yè)務(wù)只答應(yīng)使用競(jìng)爭(zhēng)和捎帶請(qǐng)求，不答應(yīng)使用周期性單播請(qǐng)求。主要的QoS參數(shù)是：最小預(yù)約業(yè)務(wù)速率、業(yè)務(wù)優(yōu)先級(jí)。

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

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

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

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

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

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

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

    (2)調(diào)度控制器根據(jù)收到的各種形式的帶寬請(qǐng)求來控制各個(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)重。以上是第二級(jí)調(diào)度的權(quán)重分配原則。總調(diào)度器即第一級(jí)調(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ò)控制消息和帶寬請(qǐng)求控制所有的隊(duì)列和調(diào)度器的權(quán)重。

    調(diào)度器的主要功能是根據(jù)各個(gè)隊(duì)列的權(quán)重對(duì)傳輸機(jī)會(huì)進(jìn)行二級(jí)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)屬于第二級(jí)調(diào)度，(4)負(fù)責(zé)對(duì)(1)、(2)、(3)調(diào)度器進(jìn)行第一級(jí)調(diào)度。第一類隊(duì)列中分組的調(diào)度準(zhǔn)則為：       

    f∈第一類隊(duì)列，其中Bmin(f  )為第一類隊(duì)列中各個(gè)業(yè)務(wù)流的最小預(yù)約帶寬，對(duì)于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)先級(jí)。通過比較這兩個(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)先級(jí)參數(shù)。通過給不同的業(yè)務(wù)分配不同的優(yōu)先級(jí)參數(shù)來給不同的隊(duì)列分配不同的加權(quán)值，從而在業(yè)務(wù)之間按優(yōu)先級(jí)不同分配不同的帶寬資源。
總調(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í)間。            是分組所在的第二級(jí)調(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提出的分級(jí)調(diào)度體系結(jié)構(gòu)，將算法應(yīng)用到IEEE 802.16中，算法本身分析所得到的性能是一樣的。分級(jí)公平調(diào)度所采用的算法不一定要限制到WFQ算法上，成熟的公平隊(duì)列調(diào)度算法還有改進(jìn)加權(quán)公平隊(duì)列算法(WF2Q)、自時(shí)鐘公平隊(duì)列算法(SCFQ)、開始時(shí)間公平隊(duì)列算法(SFQ)等，相應(yīng)的結(jié)合分級(jí)調(diào)度后的算法有分級(jí)加權(quán)公平隊(duì)列算法(H-WFQ)、分級(jí)自時(shí)鐘公平隊(duì)列算法(H-SCFQ)、分級(jí)開始時(shí)間公平隊(duì)列算法(H-SFQ)、分級(jí)改進(jìn)加權(quán)公平隊(duì)列算法(H-WF2Q)等。文獻(xiàn)[4]對(duì)各種算法的性能有具體的仿真結(jié)果。

6 結(jié)論
    本文結(jié)合分級(jí)WFQ調(diào)度算法，提出了一種適合于IEEE 802.16的有QoS保證的調(diào)度體系結(jié)構(gòu)。該體系結(jié)構(gòu)充分利用IEEE 802.16提供的控制機(jī)制，結(jié)合分級(jí)WFQ公平隊(duì)列調(diào)度算法，在UGS、rtPS、nrtPS和BE業(yè)務(wù)之間公平分配帶寬，并保證各種業(yè)務(wù)的QoS特性，完成了在IEEE 802.16協(xié)議中留給用戶自己定義的調(diào)度策略。本文只提供一種思路，下一步還應(yīng)考慮競(jìng)爭(zhē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的分級(jí)、分組調(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.

楊博，西安電子科技大學(xué)ISN國家重點(diǎn)實(shí)驗(yàn)室在讀碩士生，主要從事無線寬帶城域網(wǎng)絡(luò)的研究。

劉琰，西安電子科技大學(xué)ISN國家重點(diǎn)實(shí)驗(yàn)室在讀碩士生，主要從事無線寬帶城域網(wǎng)絡(luò)和擴(kuò)頻通信方面的研究。

劉乃安，西安電子科技大學(xué)ISN國家重點(diǎn)實(shí)驗(yàn)室MCN室主任，教授。主要從事移動(dòng)計(jì)算網(wǎng)絡(luò)、擴(kuò)展頻譜通信、無線通信、移動(dòng)通信的研究工作。已發(fā)表論文20余篇，出版教材和著作3部、譯著1部，承擔(dān)國家自然科學(xué)基金項(xiàng)目、國家“863”計(jì)劃項(xiàng)目及中外合作項(xiàng)目多項(xiàng)。