適應信道的WiMax分級調度架構

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

引言

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

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

IEEE 802.16d的服務類型

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

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

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

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

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

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

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

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

QoS調度架構的設計

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

圖1 調度構架圖

調度控制器

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

流量監控

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

實時調度器

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

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

參數初始值：

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

lagi=0

參數更新：

Vi+=packetik. length / ratei

lagi±=packetik·length

業務調度：

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

其中：Vi：業務流i的虛擬時間

lagi：業務流i的落后/領先度

packetik：業務流i的第k個包

ratei：業務流i的速率

非實時調度器

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

參數初始化：

blocktimei=0

consumei=0

參數更新：

blocktimei+=d

consumei+= packetik·length

業務調度：

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

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

consumei：隊列SSi已消耗的數據量

packetik：隊列SSi的第k個數據包

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

d：時間間隔量

BE調度器

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

總調度器

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