一種適應信道的WiMax分級調(diào)度架構

　　摘要： 針對無線信道中與時間和位置相關性錯誤，本文簡要介紹了IEEE 802.16d協(xié)議的QoS服務模型，在對WiMax的QoS機制和調(diào)度策略進行了深入的研究后，提出了一種新的MAC層分級分組調(diào)度架構。以滿足不同類型業(yè)務的QoS需求，解決了無線信道特殊性帶來的調(diào)度問題。

　　關鍵詞： 無線城域網(wǎng)規(guī)范;服務質(zhì)量;調(diào)度;無線信道

　　引言

　　隨著VoIP電話、視頻會議和在線視頻等多媒體業(yè)務迅猛發(fā)展，對網(wǎng)絡性能提出了與傳統(tǒng)的網(wǎng)頁瀏覽、FTP服務、E-mail等業(yè)務不同的需求，不同類型的業(yè)務具有各自明確的服務質(zhì)量(QoS，Quality of Service)成為現(xiàn)代通信網(wǎng)絡的一大特征。旨在提供傳輸距離更遠、速度更高的無線城域網(wǎng)規(guī)范—WiMax標準中，無線信道的位置依賴性、突發(fā)和高的信道誤碼也成為其QoS要面對的首要問題。針對不同的應用需求，802.16d標準中為QoS定義了四種業(yè)務類型，明確規(guī)范了交互機制，但將調(diào)度等內(nèi)容留待開發(fā)者自行解決。

　　文獻[2]提出一種新型的CIF-Q調(diào)度算法，能夠較好地適應無線特性、滿足實時要求，但缺乏對多類型業(yè)務的區(qū)別服務。文獻[3]提出的CSDPS算法能夠不依賴于信道特性，卻無法保證時延限制。將文獻[4]提出的分級體系結構應用到WiMax的QoS調(diào)度架構中，提出了兩層的分組調(diào)度算法，針對不同類型業(yè)務的QoS需求，在良好適應無線特性的同時，實現(xiàn)對不同業(yè)務應用的支持。

　　IEEE 802.16d的服務類型

　　主動授予服務(UGS，Unsolicited Grant Service)

　　UGS業(yè)務用于傳輸周期性的、包大小固定的實時數(shù)據(jù)業(yè)務，其典型業(yè)務是VoIP電話。UGS業(yè)務一旦申請成功，在傳輸過程中就不需要再去申請。BS周期性地強制調(diào)度，不接收來自SS的競爭請求機會，同時禁止使用捎帶請求，這樣避免了帶寬請求引入的開銷和時延。

　　實時輪詢服務(rtPS，Real-time Polling Service)

　　rtPS主要用于支持周期性的、包大小可變的實時業(yè)務，如MPEG視頻業(yè)務。rtPS提供周期性的單播輪詢帶寬請求機會，從而使得該連接能夠周期地改變帶寬請求。BS也不接收來自SS的其他競爭請求機會和捎帶請求。這種服務比UGS的請求開銷大，但能按需動態(tài)分配帶寬。

　　非實時輪詢服務(nrtPS，Non-Real-time Polling Service)

　　nrtPS主要用于支持非周期、變長分組的非實時VBR服務流，如高帶寬的FTP業(yè)務流，它有最小速率要求。BS提供比rtPS輪詢間隔更長的周期或不定期的單播請求機會，SS也可以使用競爭和捎帶請求的方式來請求帶寬。

　　盡力而為服務(BE，Best Effort Service)

　　BE主要用于支持非實時、無任何速率和時延要求的分組數(shù)據(jù)業(yè)務，其穩(wěn)定性由高層協(xié)議來保證。典型業(yè)務是Telnet和Http服務。SS可以隨時提出帶寬申請，允許使用任何類型的競爭請求機會和捎帶請求，但是不允許它們使用任何單播輪詢請求機會。

　　QoS調(diào)度架構的設計

　　本架構的設計見圖 1。服務請求通過分類器后，按照QoS需求特性，將業(yè)務流分組放入不同隊列。從隊列中取出的請求加以流量監(jiān)控，保證在對用戶流量進行規(guī)約的同時，允許保持業(yè)務流限定范圍內(nèi)的突發(fā)性。通過流量監(jiān)控后的服務請求先進入下層調(diào)度，針對同種排隊類型的業(yè)務進行調(diào)度，包括實時調(diào)度、非實時調(diào)度和BE調(diào)度。上層總調(diào)度針對不同種排隊類型業(yè)務進行總體統(tǒng)籌安排。下面將對這些模塊進行深入分析。主要由下面幾個部分組成：

圖1 調(diào)度構架圖

　　調(diào)度控制器

　　四種類型業(yè)務的帶寬請求方式不同，對時延、抖動和速率等參數(shù)的要求也不同?？紤]到無線信道特性，采用如下調(diào)度控制策略：為UGS業(yè)務預留一定帶寬BUGS，維持特征表，用于定期給SS分配相應的帶寬來發(fā)送UGS業(yè)務流。對于rtPS業(yè)務，通過確定其單播輪詢間隔的參數(shù)值，可以調(diào)整實時業(yè)務傳輸機會的多寡和帶寬分配量。對于nrtPS業(yè)務，通過確定其單播輪詢間隔來調(diào)整獲取傳輸機會的周期，保證非實時業(yè)務的最小速率。并檢查帶寬的空余量，決定是否對nrtPS業(yè)務的競爭和捎帶請求進行授權。按照上述思想，將周期性的、具有恒定速率的UGS業(yè)務流、rtPS和nrtPS的輪詢流放至實時隊列，將nrtPS業(yè)務流的帶寬請求放至非實時隊列，而將沒有QoS要求的BE業(yè)務流放至BE隊列。

　　流量監(jiān)控

　　為了使上游流量適應可用的帶寬資源，避免不必要的報文丟棄和擁塞，系統(tǒng)要對分類后的業(yè)務流進行流量監(jiān)控。本模塊采用令牌桶算法，策略如下：當報文到來后，只要令牌桶中有令牌，無論數(shù)量是否足夠，都可以轉(zhuǎn)發(fā)報文，同時令牌桶中的令牌量按報文的長度做相應的減少。當令牌數(shù)量小于報文長度時，就可以欠債轉(zhuǎn)發(fā)，即轉(zhuǎn)發(fā)后令牌桶中令牌數(shù)目為負，在下次添加令牌的時候，先還清所欠債務，再繼續(xù)轉(zhuǎn)發(fā)報文。這種借貸處理方法在處理突發(fā)報文時有優(yōu)勢，能夠在限制流量的同時，保證報文發(fā)送的連續(xù)性，很好地除抖動的影響。系統(tǒng)為實時業(yè)務流預留一定的帶寬，并優(yōu)先處理實時業(yè)務。非實時業(yè)務流和BE業(yè)務流的突發(fā)性較高，業(yè)務量相對繁重，這類業(yè)務是流量監(jiān)控的工作主要對象。

　　實時調(diào)度器

　　實時調(diào)度器負責對帶寬和延時要求比較嚴格的實時業(yè)務流，包括UGS業(yè)務流、rtPS業(yè)務流和nrtPS業(yè)務的輪詢流。由于業(yè)務的實時性，在業(yè)務延時后，無法也無需補償其帶寬。也就是說一定要保證實時業(yè)務的時延需要，盡量避免某一實時業(yè)務長時間等待現(xiàn)象，同時使各業(yè)務流的延時在可容忍的門限內(nèi)?？紤]到這些因素，實時調(diào)度器中采用不依賴于信道狀態(tài)的包公平排隊CIF-Q(Channel Independent Fair Queuing)算法。CIF-Q算法的核心是起始時間公平排隊(SFQ，Start time Fair Queuing)算法，通過參考無錯服務系統(tǒng)，業(yè)務流可劃分為領先流、落后流和正常流三類。流的落后(領先)度為無錯服務和真實服務之差。如果領先流獲得了一個調(diào)度機會，則以概率α放棄它，被放棄的機會分配給具有最大落后度的落后流。在這種補償策略下，落后流可以接受額外服務，而同步流不會受到干擾，領先流將會優(yōu)美地降低它們的服務。概率α的值是由網(wǎng)絡狀態(tài)和實時業(yè)務流的QoS參數(shù)(授權大小、輪詢間隔、最大輪詢時延抖動和最小預約速率等)決定的。

　　下面是對算法模型的偽代碼描述，并將在NS2仿真中采用C++實現(xiàn)。

　　參數(shù)初始值：

　　Vi=max(Vi, min{Vj | j∈A})

　　lagi=0

　　參數(shù)更新：

　　Vi+=packetik. length / ratei

　　lagi±=packetik·length

　　業(yè)務調(diào)度：

　　選擇業(yè)務流i = min{Vi | iA};若業(yè)務流i落后，并可正常發(fā)送，則調(diào)度業(yè)務流i，更新Vi;若業(yè)務流i落后，但不可正常發(fā)送，則選擇業(yè)務流j = max{lagk/rk | k∈A ∧packetjk可發(fā)送}進行調(diào)度，更新Vi、lagi、lagj;若業(yè)務流i領先，則以概率1-a正常調(diào)度業(yè)務流i，更新Vi;概率a放棄調(diào)度業(yè)務流i，選擇業(yè)務流j=max{lagk/rk | k∈A ∧packetjk可發(fā)送}進行調(diào)度，更新Vi、lagi、lagj;

　　其中：Vi：業(yè)務流i的虛擬時間

　　lagi：業(yè)務流i的落后/領先度

　　packetik：業(yè)務流i的第k個包

　　ratei：業(yè)務流i的速率

　　非實時調(diào)度器

　　非實時調(diào)度器主要負責實時性較弱的nrtPS業(yè)務流。非實時業(yè)務對延時的要求不高，更加關注的是在適應無線鏈路特性的同時，如何應對繁重的業(yè)務流、保證吞吐量?；谶@些理由，非實時調(diào)度器采用基于業(yè)務類型排隊(CBQ，Class-Based Queuing)的適應無線信道狀態(tài)調(diào)度算法CSDPS(Channel State Dependent Packet Scheduling)。CSDPS部分用于處理無線鏈路的變化，它將每一個SS的分組數(shù)據(jù)信息都保存在一個獨立的隊列中，并按照先入先出(FIFO)順序處理每個隊列中的分組數(shù)據(jù)。設置一個鏈路狀態(tài)監(jiān)視器，用來監(jiān)視所有SS的鏈路狀態(tài)信息，當某無線鏈路處于異常狀態(tài)時，則標記該隊列，使之暫停服務。一段時間后取消對它的標記，該隊列可以重新進行資源調(diào)度。CBQ跟蹤每個SS隊列在確定時間間隔內(nèi)收到的業(yè)務數(shù)量，并且限制超過應分配共享帶寬的SS在未來分配資源的大小，提供整個無線信道共享的公平性機制。

　　參數(shù)初始化：

　　blocktimei=0

　　consumei=0

　　參數(shù)更新：

　　blocktimei+=d

　　consumei+= packetik·length

　　業(yè)務調(diào)度：

　　每間隔d時間重新初始化consumei;更新blocktimei;blocktimei >a，取消對隊列SSi的標注;選擇未被標注且consumei未超標的隊列SSi;若隊列SSi的數(shù)據(jù)流可正常發(fā)送，則調(diào)度packetik，并更新consumei;若隊列SSi的數(shù)據(jù)流不可正常發(fā)送，則標注SSi，并初始化blocktimei;

　　其中：blocktimei：隊列SSi的暫停時間

　　consumei：隊列SSi已消耗的數(shù)據(jù)量

　　packetik：隊列SSi的第k個數(shù)據(jù)包

　　a：當隊列被標注后，恢復正常所需時間

　　d：時間間隔量

　　BE調(diào)度器

　　BE調(diào)度器主要負責對服務質(zhì)量不作要求的BE業(yè)務流，不須為其提供完備的QoS保證?？紤]到BE業(yè)務流的典型業(yè)務是Internet網(wǎng)絡瀏覽等，實時性要求較低，無須考慮服務中斷的應對，采用簡單的先入先出(FIFO，F(xiàn)irst In First Out)算法即可滿足其需求。

　　總調(diào)度器

　　總調(diào)度器負責對不同類型的業(yè)務進行調(diào)度，在體現(xiàn)各種業(yè)務享有不同級別服務質(zhì)量的同時，還要在三種子調(diào)度之間找到一個平衡點，達到相對公平的目的，防止諸如實時業(yè)務壟斷帶寬或?qū)崟r業(yè)務被阻塞等現(xiàn)象的發(fā)生。這包含兩個方面的內(nèi)容：一、穩(wěn)定三類業(yè)務間的結構;二、適應業(yè)務流變化。為此，總調(diào)度器采取如下策略和措施：為實時業(yè)務預留一部分帶寬BUGS，為突發(fā)流預留一部分帶寬Bburst，其余的帶寬按一定比例分配給三類業(yè)務流。當請求比例外帶寬時，優(yōu)先授權予實時業(yè)務，非實時業(yè)務次之，BE業(yè)務最低優(yōu)先級。當三類業(yè)務流間的帶寬需求結構發(fā)生變化時，要適當調(diào)整帶寬的分配比例?？紤]到對帶寬的充分利用，當由于無線信道誤碼或其他原因造成某一正在傳遞數(shù)據(jù)的連接暫時中斷，系統(tǒng)會將連接所占帶寬臨時分配給別的連接，為了實現(xiàn)公平性，在暫時中斷服務的連接恢復正常后，系統(tǒng)應對中斷連接作出帶寬補償。UGS等業(yè)務流實時性很強，若連接恢復后再對連接作出帶寬補償沒有多大意義。對于BE業(yè)務，調(diào)度不保證其服務質(zhì)量，因此BE業(yè)務也無補償。而nrtPS流業(yè)務量繁重，一旦中斷連接必然導致大量數(shù)據(jù)滯留，必須考慮連接恢復后的帶寬補償問題。

　　總調(diào)度器算法模型偽代碼描述如下：

　　檢查進入調(diào)度的數(shù)據(jù)流的類型，確定此類型的比例帶寬(Brt或Bnrt或BBE)是否有剩余：若有，則進入相應的子調(diào)度器，并更新剩余的比例帶寬;若無，則進入brust業(yè)務處理方法。

　　brust業(yè)務：若Bbrust+Bremain>0，則按照rtPS>nrtPS >BE的優(yōu)先順序處理數(shù)據(jù)流，并更新Bbrust、Bremain。對未取得Bbrust的業(yè)務標識為NeedCompensate。

　　業(yè)務補償：若Bremain>0，則對標識為NeedCompensate的業(yè)務分配Bremain的帶寬，進入相應子調(diào)度，并更新Bremain。

　　BUGS：UGS業(yè)務保留帶寬

　　Brt、Bnrt、BBE：實時業(yè)務、非實時業(yè)務和BE業(yè)務的比例帶寬

　　Bremain：剩余帶寬

　　仿真結果

　　由UC Berkeley開發(fā)的免費、開源的多協(xié)議網(wǎng)絡仿真軟件NS-2是一個事件驅(qū)動的模擬器，它可以屏蔽對操作系統(tǒng)的實際訪問，近乎真實地模擬網(wǎng)絡環(huán)境。由于NS-2本身中不包含WiMax模塊，這里采用對QoS支持較為完善的長庚大學開發(fā)的WiMax 2.03模塊。本文對調(diào)度架構中所涉及的調(diào)度算法用C++進行描述，然后采用Otcl腳本語言建立WiMax模擬場景，并獲取的仿真數(shù)據(jù)結果。針對無線信道特性導致的高誤碼率，本文模擬1個BS(Base Station)和4個SS(subscriber station)組成的WiMax網(wǎng)絡，仿真場景如圖 2所示。誤碼率設為1%，最大誤碼時長16個時間間隔。通過對仿真數(shù)據(jù)的分析和對比，可以得到算法的吞吐量、延時和速率等性能參數(shù)。本架構算法與通常調(diào)度算法的對比見圖 3、圖 4(取樣時間為0.1秒)。

圖 2 仿真場景圖

　　圖 3是UGS、rtPS等實時業(yè)務在采用CIFQ算法和FIFO算法時的延時對比?？梢钥闯?，在業(yè)務擁擠，出現(xiàn)信道錯誤時，F(xiàn)IFO算法會產(chǎn)生峰值毛刺，出現(xiàn)長延時現(xiàn)象。相比之下，雖然CIFQ算法的總延時增加2%，但延時波動較為平穩(wěn)，且無長延時現(xiàn)象，這證明CIF-Q算法能夠在有效應對信道錯誤的同時，滿足了實時業(yè)務的延時和抖動需求。

圖3 實時業(yè)務延時對比圖

表1 主要性能參數(shù)對比表

　　圖 4是非實時業(yè)務在采用CBQ-CSDPS算法和FIFO算法時的吞吐量對比。明顯可以看出，在信道現(xiàn)在錯誤時，F(xiàn)IFO算法會導致吞吐量急劇下降。而CBQ-CSDPS算法能夠很好應對信道錯誤，持續(xù)高吞吐量作業(yè)，總的吞吐量比FIFO算法多出近15%。這證明CBQ-CSDPS算法更有利于非實時業(yè)務高效率地使用帶寬。

圖4 非實時業(yè)務吞吐量對比圖

　　在仿真無線特性的高誤碼的場景下，本架構的延時、吞吐量和丟包等方面的表現(xiàn)見表 1。采用本架構后，實時業(yè)務的延時/抖動有明顯改善的同時，吞吐量有了一定的提升，丟包率減少了約30%;對于非實時業(yè)務在采用本架構后吞吐量提升十分顯著，丟包率也減少了約30%，但代價是延時增加了近15%。表面上看，本架構似乎有得有失，但內(nèi)在卻有了質(zhì)的變化：本架構以總延時的少量增加換得對延時抖動的限制、丟包率和吞吐量的提升，從而滿足實時業(yè)務的延時和抖動需求;非實時業(yè)務以其非注重的總延時兌得吞吐量的極大提升，滿足了非實時業(yè)務的高速率暢行。這說明本調(diào)度架構的算法在高誤碼率的狀況下，能夠較好地滿足各類型業(yè)務需求。

　　結語

　　本文結合CIF-Q和CBQ-CSDPS等調(diào)度算法，提出一種適合于WiMax的MAC層QoS調(diào)度架構。該架構結合分級分組調(diào)度算法，充分利用帶寬控制、資源預留和流量監(jiān)控等策略和機制。通過NS仿真對算法進行仿真，得出如下結論：①能夠適應時間、位置相關的等無線信道特性的高誤碼率;②為不同類型業(yè)務采用相應算法，滿足UGS和rtPS業(yè)務的實時性，保證了nrtPS業(yè)務的最小速率，兼顧了BE業(yè)務的需求;③系統(tǒng)整體具有較高吞吐量、公平性和較小時延。但在無線功耗、分布式無線網(wǎng)絡的位置相鄰等問題，還需要進一步探討。

　　參考文獻：

　　1. IEEE 802.16-2004. Part 16: Air Interface for Fixed Broadband Wireless Access Systems[S]. Apr, 2004. http://www.ieee802.org/16/tg1/docs/802161-99_00.pdf.

　　2. T.S.Eugene Ng, Ion Stoica, Hui Zhang，. Packet Fair Queueing Algorithms for Wireless Networks with Location-Dependent Errors[C]. Proc Of IEEE INFOCOM'98. 1998,3(3):103-1 111.

　　3. Bhagwat P, Bhattacharya P, Krishna A, et， Enhancing Throughput over Wireless LANs Using Channel State Dependent Packet Scheduling[J]. INFOCOM'96, San Francisco, California. 1996:1133-1140.

　　4. Bennett JCR, Zhang Hui， Hierarchical Packet Fair Queuing Algorithms [EB/OL]. 1997.

　　5. 宣孝英，石冰心，鄒玲，無線網(wǎng)絡包調(diào)度算法綜述[J].計算機工程與應用，2003，39(17):20-21.

　　6. Lyu-han Chen，Credit-based Low Latency Packet Scheduling Algorithm for Real-time Applications[D]. Master. Computer Science and Information Engineering. 2007,6.

　　7. M. Hawa ，D.W. Petr.，Quality of service scheduling in cable and broadband wireless access systems[C]. In IEEE International Workshop on Quality of Service. 2002,5:247-255.

　　8. S Walsh, E Garcia-Palacios, S Sezer， Delay-bound Preservation through Packet Scheduling at Wireless Access Point Nodes, EE Mobility Conference, Bangkok, Oct 2006.

　　9. 崔維嘉，劉勤讓，一種基于業(yè)務分類的大規(guī)模用戶高速流量監(jiān)控策略[J]，電信科學,2006,22(10):51-54.

　　10. 彭木根，李茗，王文博，WiMax系統(tǒng)中QoS機制研究[J]，中興通訊技術，2005,11(2):25-30.

　　11. NS-2 simulator. http://www.isi.edu/nsnam/ns.