WiMAX Mesh網絡中一種分布式時隙分配算法

張新有，伸桂林

西南交通大學 信息科學與技術學院，成都 610031

1 引言

隨著無線通信技術的發展，寬帶無線接入技術成為了人們關注的熱點。WiMAX[1]以其更大的覆蓋面積，更高的傳輸速率和更可靠的傳輸性能受到了人們的關注。其中具有多跳性和自組織性的WiMAX Mesh網絡引起研究人員的極大興趣。WiMAX Mesh網絡標準中沒有定義與WiMAX PMP網絡類似的業務分類和QoS級別，也沒有定義相應的資源調度算法和QoS保障機制，因此WiMAX Mesh網絡的QoS保障技術急需進一步深入研究。

IEEE802.16標準為WiMAX Mesh網絡定義了兩種調度機制：集中式調度和分布式調度。集中式調度下所有節點的帶寬請求都需要匯聚到BS，由BS進行統一調度和分配；分布式調度中節點以競爭的方式發送帶寬請求消息，通過三次握手協商分配所有的帶寬資源。無論是集中式調度還是分布式調度，其帶寬調度算法都會對整個網絡性能造成很大的影響。本文對WiMAX Mesh網絡下的分布式調度機制進行了分析，提出一種基于區分服務的微時隙動態預留分配算法。

2 相關工作

目前較多文獻對WiMAX Mesh分布式調度進行了研究，主要集中在兩個方面：即鄰居節點間對MSH-DSCH消息發送時序的競爭和對數據子幀微時隙的分配方式。盡管這些研究取得了一些進展，但仍然還有許多方面需要進一步的改進和完善。

IEEE802.16標準[1]中對鄰居節點間MSH-DSCH帶寬請求消息發送時序的競爭提出了一種解決方法。文獻[2]分別對幾種消息發送時序競爭模型進行了分析，并對各模型節點的競爭概率進行了較深入的研究；文獻[3]提出了一種動態調整休眠參數的方式改變節點間的消息競爭秩序，節點每競爭成功一次發送MSH-DSCH帶寬請求消息都要進行一定時間的休眠，該文獻以當前請求帶寬的節點隊列長度作為判斷節點休眠的依據，根據隊列長度對節點設置不同的休眠參數，從而避免節點間大量的競爭導致帶寬利用率降低。

對IEEE802.16 MAC幀中數據子幀的微時隙分配是另一個研究重點。文獻[4]提出了一種分布式的微時隙分配算法，該算法每次為請求節點分配時隙時，都找最少能滿足當前需求的時隙段來分配，最大化地減少時隙碎片，提高每幀的時隙利用率。

文獻[5]提出了一種分布式多跳預約微時隙算法M-HBRP。傳統分布式調度節點間以三次握手形式來建立連接，當多跳節點間需要發送數據時總是在相鄰兩個節點間三次握手，成功后再進行下一次的兩個相鄰節點三次握手，以此逐跳地申請帶寬。而M-HBRP算法在上兩個節點進行三次握手的同時，向下一節點發送握手申請，多個節點間同步地進行微時隙申請。仿真表明該算法在保證QoS的同時，可以一定程度上減小端到端的時延。

文獻[6]將業務流劃分為高優先級和低優先級業務流組，并且設置兩個檢查點和閾值，當檢查點的數據子幀微時隙使用數低于閾值時認為網絡狀態良好，高優先級業務流和低優先級業務流同等對待，而當檢查點的數據子幀微時隙使用數高于閾值時則認為網絡出現一定程度的擁塞，只允許高優先級的業務流，低優先級業務流的請求返回失敗信息。這種方法雖然能夠保證高優先級業務的優先權，但會使得低優先級業務被嚴重影響。

文獻[7]將資源預留的思想引入到了協同分布式調度當中，在每個Mesh幀的數據子幀中預留P個微時隙，高優先級業務流分配時隙時從數據子幀的起始位置查找滿足要求的時隙段，直到查找到數據子幀末尾，低優先級業務總是從P+1開始往后查找。這種分配方式有個較為明顯的缺陷：由于P值固定，而網絡狀態隨時在變化，因此網絡擁塞時可能會造成大量的微時隙浪費。

文獻[8]在文獻[7]的基礎上進行了改進，預留的微時隙數是可以動態變化的，并且以高優先級業務和低優先級業務在隊列中所占用的比例來作為動態調整預留微時隙的依據，每次判定高優先級業務請求數大于低優先級業務請求數時認為網絡擁塞，預留時微隙數P增加步長St，而高優先級業務請求數小于低優先級業務請求數時認為網絡正常，預留時微隙數P減少步長St。該算法可以實現根據網絡狀態動態地調整預留微時隙，但以業務數量的比較來作為網絡擁塞的判定依據并不合理，在高優先級業務數和低優先級業務數都較少時網絡并未擁塞，而此算法無法做出正確的判斷。

本文綜合文獻[7]、文獻[8]的方法，提出一種新的微時隙預留調整機制，可以根據網絡業務狀態動態地調整微時隙分配格局，以達到高低業務流間的動態平衡。

3 WiMAX分布式調度機制

IEEE802.16d規定每個Mesh幀包含控制子幀和數據子幀兩部分，控制子幀和數據子幀都可以劃分為更小的時序（slot）或微時隙（minislot），控制子幀中時序數由MSH-NCFG消息中Network description IE中的MSH_CTRL_LEN參數決定，數據子幀用于傳輸業務數據，每個數據子幀包含256個微時隙。

控制子幀又可以分為網絡控制子幀和調度控制子幀，二者不會同時出現在同一個Mesh幀內。網絡控制子幀包括節點入網（MSH-NENT）消息和節點交換與網絡配置（MSH-NCGF）消息，用來創建和維護不同節點間的協調工作。調度控制子幀包括集中式調度（MSH-CSCH）和分布式調度（MSH-DSCH）兩種消息，為節點間數據交換進行調度，合理分配帶寬，避免數據傳輸產生沖突。

分布式調度有兩種類型：即協調分布式調度和非協調分布式調度，由MSH-DSCH消息中的Coordination Flag字段來區分。其中“非協調”是指Mesh中的節點通過競爭獲得minislot，所以可能發生碰撞；“協調”是指節點在控制子幀里發送分布式調度消息（MSH-DSCH），通過請求-授權-授權確認三次握手的過程，協商節點間數據子幀里minislot的分配，為節點間提供無碰撞的傳輸數據。協調分布式調度是本文研究的重點。

3.1 MSH-DSCH消息結構

MSH-DSCH消息包括MAC消息頭和若干信息單元，MAC頭中包含了CID（Connection ID），該CID中包含了該數據單元的可靠性、優先級、丟棄優先級及對應的Link ID等參數[1]。信息單元用來協調節點的時隙分配與調度，主要包含以下四個部分[5]：

（1）調度信息單元（Scheduling IE）：該單元存放節點自身和鄰居節點的下一次發送MSH-DSCH消息的時間間隔Next Xmt Mx和Xml Holdoff Exponent參數，節點通過這些參數計算出鄰居節點下一次發送MSH-DSCH消息的時間范圍，從而確定將同自己一起參與MSH-DSCH發送時序競爭的鄰居集合，并通過MeshElection（）函數[9]來判斷競爭結果。

（2）可用資源信息單元（Availability IE）：該單元存放當前節點可利用的帶寬信息，包括起始幀號（Start Frame number）、微時隙起始位置（minislot start）、一幀中微時隙的總數（minislot range）、連續經歷的幀數（Persistence）、資源信息（Direction，0表示不可用，1表示可用于發送，2表示可用于接收，3表示既可發送也可接收）、信道序號（Channel）。

（3）請求信息單元（Request IE）：該單元存放節點的帶寬請求相關信息，包括與此節點通信的（Link ID）、節點的時隙請求數（Demand Level）和所有時隙請求必須連續分布的幀數（Demand Persistence）。

（4）授權信息單元（Grants IE）：該單元表明已被授權的帶寬相關的信息。包括與此節點通信的Link ID、授權的起始幀號（Start Frame number）、授權的微時隙起始位置（Minislot start）、一幀中微時隙的總數（Minislot range）、連續經歷的幀數（Persistence）、資源信息起始幀號（Start Frame number）、信道序號（Channel）、授權狀態（Direction，1表示授權，0表示授權確認）。

3.2 三次握手過程

節點根據所收到鄰居節點的MSH-DSCH消息對自己可用微時隙狀態進行更新。Mesh模式分布式調度的三次握手過程如圖1所示。

圖1 分布式調度三次握手過程

節點間一次數據連接的建立需要經過“請求-授權-確認”三個步驟。首先請求節點廣播發送MSH-DSCH請求消息，且在MSH-DSCH的Request IE中指明Link ID、需要的時隙數、數據幀持續個數及節點自身的時隙使用情況（Availabilities IE）；授權節點根據Request IE的請求，采用合適的時隙分配算法尋找自身AvailabilitiesIE中適合的微時隙，若尋找成功則廣播MSH-DSCH Grant IE（direction=1）授權消息，指明已授權的微時隙的標記；請求節點在收到授權節點的Grant IE后，復制該條消息內容并設置direction=0，在下一個MSH-DSCH發送機會時將Grant IE（direction=0）授權消息發送給授權節點。

4 區分服務微時隙分配算法

4.1 Mesh業務分類

WiMAX標準為PMP網絡模式定義了4種業務類型[1]：主動授權業務（UGS），實時輪詢業務（rtPS），非實時輪詢業務（nrtPS），盡力而為業務（BE），且每種數據業務都與一系列的QoS參數相關聯。而Mesh網絡中只在Mesh CID（Connection Identifier）中定義了 Type、Reliability、Priority、Drop precedence等服務參數。本文通過區分MAC頭CID中的Priority字段將業務分為兩類：高優先級業務和低優先級業務，高優先級業務對時延相對敏感，低優先級業務可以容忍一定的時延。這種業務分類和PMP的4種業務類型可以沒有明顯的對應關系，也可以有對應關系，比如UGS和rtPS對應高優先級業務，nrtPS和BE對應低優先級業務。

4.2 算法描述

本文以高優先級業務和低優先級業務占用微時隙的狀況來作為網絡擁塞（時隙不足）的判定依據，動態調整預留微時隙時是以連續網絡擁塞或網絡正常的次數來作為調整時隙預留的依據，借鑒快加速、快后退的思想來保證高優先級業務的服務質量。該算法需要在MSH-DSCH消息中添加動態預留時隙Pt、記錄高優先級業務引起的連續擁塞次數和網絡連續空閑次數congestion_num、free_num。算法流程如圖2所示。算法說明如下。

（1）根據請求幀中的CID參數可以將請求業務區分為高優先級業務的低優先級業務，該算法的目的是確保高優先級業務優先獲得微時隙，同時確保低優先級業務不被“餓死”。

（2）授權節點設定每一MAC幀的數據子幀中最大預留時微隙數Pt_Max和最小預留微時隙數Pt_Min以及時隙變化步長St，設置高業務時隙占用比閾值TH1，低業務時隙占用比閾值TH2；初值設定congestion_num=0，free_num=0，Pt=Pt_Min 。

（3）節點要記錄每一數據子幀微時隙分配情況。高（低）優先級業務微時隙占用比閾值為一個比值，分子是高（低）優先級業務占用微時隙數，分母是此算法此時分配給高（低）優先級業務微時隙總數。

（4）雖然圖1中顯示一個請求節點的連接過程，但由于一個請求MAC幀的消息中可能包含多個（可以來自不同節點）時隙分配請求，所以授權節點需要逐個處理內個業務請求。

（5）若請求節點發送的數據請求是高優先級的業務流請求則在Availabilities IE中從每幀的起始minislot[0]開始往后查找符合條件的時隙直到minislot[Pt-1]，如果查找成功，返回Grant IE（direction=0），否則返回失敗信息；若請求節點發送的數據請求是低優先級的業務流請求則在Availabilities IE中從每幀的minislot[Pt]開始往后查找符合條件的時隙，直到末尾，如果查找成功，返回Grant IE（direction=0），否則返回失敗信息。

圖2 Request IE請求幀的時隙分配過程

（6）圖2中的①表示沒有得到所需微時隙的Request IE以失敗告終，授權節點將不做任何處理；另一種方法是對高優先級業務請求繼續保存在請求隊列，參與下一幀的微時隙分配，而低優先級業務以請求失敗告終（流程中沒有反映此種情況）；圖2中的②表示當節點處理完所有請求后，對得到微時隙請求的節點授權Grant IE將在該節點隨后競爭到的MSH-DSCH消息時序中廣播發出，沒有得到資源的請求將不作回應。

4.3 算法分析

相比文獻[6]使用的設定固定監測點方法，采用計算微時隙占用比更能精確反映時隙的來判斷時隙的使用情況。因為數據子幀的微時隙經過歷史節點間請求、分配的操作后，會造成空閑時隙分配不均形成空洞，固定監測點方法無法回避此問題。此算法也改進了文獻[7]中P值固定的問題，靈活地分配高低優先級業務占用時隙的比例，從而提高了時隙的利用率。相比文獻[8]的高（低）優先級業務請求數之比判斷時隙利用率的方法，本文微時隙占用比的方法更加準確有效。

本算法的改進主要體現在統計高低優先級業務的時隙占用比以及微時隙動態預留算法上，通過參數的設置和適當調整實現預期功能，與參考文獻[6-8]相比，沒有增加算法復雜性，仍然是線性查找的算法復雜性O(n)。

5 仿真結果及分析

5.1 仿真環境

采用網絡模擬器NS2-2.33對算法進行仿真，基于802.16d-2004標準的mesh開源補丁Ns2mesh80216[10]。定義本文算法為A3，文獻[6]算法為A0，文獻[7]算法為A1，文獻[8]算法為A2。仿真將所有業務流分為高優先級實時業務流和低優先級盡力業務流兩種業務流，高優先級業務流用恒定速率的CBR流來表示，CBR分組長度為1 000 Byte，以恒定速率512 kb/s的速率發送，發送間隔30 ms；低優先級業務流采用可變速率的VBR流表示，VBR分組大小在100～300 Byte之間隨機產生，發送間隔200 ms，發送速率120 kb/s近似于實際網絡中的HTTP業務。設定本文算法A3的參數Pt_Min=128，Pt_Max設為總時隙數的3/4，即Pt_Max=192。檢查點閾值在A0、A1算法中都設為158，檢查點設為此幀之前的第5幀，A2中固定預留時隙長度設為158，步長St為4，A3算法中的步長St設定為2，TH1設為80%，TH2設為90%。仿真中VBR的業務流條數固定為15條不變，CBR業務流逐漸增加，仿真時間60 s。

仿真分析設置了三個考察指標：端到端的時延、節點的請求失敗率以及幀的時隙利用率。仿真中通過改變節點的數量對比其他幾種調度算法來進行仿真實驗，對仿真數據進行統計分析。仿真參數設置見表1。

5.2 實驗結果分析

圖3為業務流的平均分組時延比較，從圖中可以看到在固定VBR流條數不變的情況下，隨著CBR流傳輸節點的增加，CBR流和VBR流的平均分組時延都逐漸增大，由于在時隙分配時對業務設定了優先級，VBR流的平均分組時延大于CBR流。CBR業務流下算法A0、A1、A2的平均分組時延依次減小，本文提出的A3算法與A2較為接近，比A2算法略佳；在VBR業務流下情況則正好相反，但和A2算法相比，A3算法的時延隨著節點增加反而下降。一方面較為明顯地體現出了區分服務的特性，高優先級的業務流得到了較低的時延；另一方面顯示了A3算法對低優先級業務的時延保證。

表1 仿真參數設置列表

圖3 算法平均分組延遲對比

圖4為VBR流數據分組的請求失敗率比較，從圖中可以看出，當實時CBR流增加以后，由于CBR流具有較高的優先級，因此CBR流越多，VBR流的數據分組請求失敗率就越大，其中A0算法的失敗率最高，這是由于A0算法在檢查到網絡處于擁塞狀況后低優先級的VBR流直接返回請求失敗，而A1、A2、A3算法在網絡處于擁塞時低優先級業務僅僅是初始搜索空閑時隙的位置不同，A1算法由于預留的微時隙是固定不變的，在最初時節點較少時由于預留微時隙比A2、A3要高，所以請求失敗率比A2、A3算法要高，但隨著CBR流節點增加后，A1算法的VBR流數據分組的請求失敗率反而要比A2算法低。隨著節點數量的增加，A3算法的請求失敗率增加緩慢。

圖5為微時隙利用率比較，網絡中通信節點越多節點的時隙利用率越大，從圖中的對比可以看出在時隙利用率上A0算法的時隙利用率最差遠低于A1、A2、A3算法，本文提出的A3算法由于在時隙預留調整上，出現擁塞后預留時隙以步長指數倍的增長，機動性最大，所以在整個時隙利用率的比較中占有絕對的優勢，比A2和A1算法都表現得更好。

圖4 算法請求失敗率對比

圖5 算法時隙利用率對比

綜合以上對時延和分組請求失敗率和時隙利用率的仿真實驗，可以看出盡管A0、A1、A2、A3四種算法都實現了分類業務的QoS。同時可以看出，本文提出的A3算法表現出了更優的性能，兼顧了時延、請求失敗率和時隙利用率。

6 結束語

本文提出了一種WiMAX Mesh網絡中基于資源預留的微時隙分配算法，算法首先將業務分為高優先級業務和低優先級業務兩類，對高優先級的業務在MAC幀中預留一定的微時隙作為分配高優先級業務的時隙，預留微時隙數量可以根據數據子幀中微時隙的利用率動態調整，仿真表明該算法在滿足高優先級業務QoS的同時兼顧業務的請求失敗率與時隙的利用率，降低分組的平均時延，提高整個網絡的性能。仿真中A3算法不同的參數設置進行比較，如本算法中的參數TH1和TH2取值對結果有較大影響。在授權節點的時隙分配過程中需要時隙可用狀態，本文將時隙的狀態僅分為可用，不可用是不夠的。因此如何進一步合理地設置各個參數使網絡性能達到最佳還需要進一步研究。而且WiMAX Mesh網絡QoS問題不僅與時隙分配算法有關，也與網絡的接納控制、路由、包管理器等環節有關，這些都是下一步的研究重點。

[1]IEEE Standard802.16-2004.IEEE standard for local and metropolitan area networks-part16：air interface for fixed broadband wireless access systems[S].2004.

[2]Cao Min，Ma Wenchao，Zhang Qian.Analysis of IEEE 802.16 Mesh mode scheduler performance[J].IEEE Transactions on Wireless Communications，2007，6（4）：1455-1464.

[3]Rostami A，Rostami A，Zokaei S，et al.A new two-stage dynamic holdoff time scheme for enhancement of signaling messages in IEEE 802.16 Mesh networks[C]//International Conference on Communication Technology（ICCT），2011：1-25.

[4]Peng Limin，Sun Suyun.Coordinated distributed data scheduling scheme in IEEE 802.16 Mesh networks[C]//International Conference on Internet Computing and Information Services，2011：389-392.

[5]Li Yun，Zhang Xin，Zhuang Hongcheng，et al.An end-to-end QoS assurance method in IEEE 802.16 Mesh networks[C]//Global Telecommunications Conference（GLOBECOM 2010），2010：1-6.

[6]Liu Fuqiang，Zeng Zhihui，Tao Jian，et al.Achieving QoS for IEEE 802.16 in Mesh mode[C]//Proceedings of the 8th International Conference on Computer Science and Informatics，2005：3102-3106.

[7]曾智慧，劉富強，陶健，等.IEEE 802.16 Mesh模式下MAC調度機制的研究[J].計算機工程與應用，2005，41（23）：135-138.

[8]汪麗萍，劉富強，王新紅，等.IEEE 802.16 Mesh模式下區分服務時隙調度算法[J].計算機工程與應用，2006，42（34）：105-108.

[9]Shukaili A A，Chilamkurti N，Zeadally S.Enabling“Quality of Service”in IEEE802.16 networks for distributed mesh topologies[C]//2010 Australasian Telecommunication Networks and Applications Conference，2010：135-140.

[10]Ns2mesh80216[EB/OL].[2013-03-20].http：//cng1.iet.unipi.it/wiki/index.php/Ns2mesh80216.