IEEE802.16d Mesh網絡及其關鍵機制分析

原建勝，謝 剛，趙哲峰

（太原理工大學 信息工程學院，山西 太原030024）

當前無線網絡對網絡覆蓋和吞吐量的需求越來越高，多跳網絡與無線Mesh機制的研究得到更廣泛關注。而為無線城域網（WMAN）而制定的IEEE802.16/WiMax標準也包含了其相應的Mesh運行模式[1-2]。這里在介紹了IEEE802.16d標準下的無線Mesh模式和IEEE 802.16j移動多跳中繼網絡[3]的網絡結構的基礎上，重點分析了基于IEEE802.16d的Mesh網絡中的調度、功率控制和路由等3個關鍵機制。

1 IEEE 802.16d Mesh模式

在IEEE 802.16d標準中支持2種運行模式：

1）PMP（點對多點）模式業務流直接由 BS（Base Station）流向 SS（Subscriber Station）或者由 SS 流向 BS。

2）Mesh模式 業務流直接在SS之間傳送，無需經過BS路由。這意味著SS無需直接與BS相連。

在PMP的模式下，SS之間不能直接互相通信，任何網絡結點間的通信均轉換成SS與BS之間的通信。在Mesh模式中，網絡中任何節點間在可通信范圍內都可通過一跳的方式連接，BS不再是獨自承擔所有接點間通信的中轉站。

1.1 Mesh網絡與移動多跳中繼網絡

在IEEE802.16d標準定義的 Mesh網絡由單個中心節點控制，將該節點定義為Mesh基站 （BS），作為IEEE802.16d Mesh網絡與外網的接口。其網絡結構[4]見圖1。

圖 1 IEEE802.16d（WiMax）Mesh 網絡Fig.1 IEEE802.16d （WiMax） Mesh network

圖1中，傳統的IEEE802.16 PMP網絡與無線Mesh 網絡實現融合，在此網絡結構中，Mesh BS與主干網絡相連接，作為WiMax Mesh網絡到外網的出口，并實現本網絡的寬帶接入；MSS節點則除了實現本地用戶的寬帶接入之外，又可通過多次轉發將來自其他MSS節點的數據傳輸到目的節點。

隨著IEEE802.16協議的不斷發展與完善，IEEE移動多跳中繼（Mobile Multi-hop Relay，簡稱MMR）標準制定工作組開始制定了具有中繼功能的IEEE 802.16j協議。IEEE 802.16j移動多跳中繼網絡主要是在原有網絡基礎上加入了中繼站（Relay Station，簡稱RS）進行中繼通信，以此擴大小區網絡覆蓋范圍，并解決非視距傳輸、邊緣效應、信號盲點等問題[5]。圖 2所示為IEEE802.16d Mesh網絡與 IEEE802.16j多跳中繼網絡拓撲圖對比。其主要區別就在于：IEEE802.16d Mesh網絡由MSS實現通信中數據的中轉，而IEEE802.16j多跳中繼網絡則由RS實現。另外，IEEE802.16d-Mesh網絡包含星型與樹形拓撲2種結構，而IEEE802.16j多跳中繼網絡則只包含樹形拓撲結構。

圖2網絡拓撲圖對比Fig.2 Comparison of networks topology

基于以上2種網絡結構，文獻[6]提出了一種協同中繼技術的組網方案，該方案擬通過將多跳技術和協同技術的融合使網絡的功能大于每個組成部分的功能之和，從而解決更廣域和更深入的無縫覆蓋，并且同時為用戶提供高速率的無線接入服務，提高對網絡的資源利用率。

1.2 IEEE802.16d隨機接入機制

IEEE802.16d Mesh網絡拓撲結構中，每一個新節點進入Mesh網絡都需要尋找一個網絡內的節點作為其負責節點（Sponsor Node），負責節點為新節點開放負責信道，幫助其完成基本容量協商、節點ID獲取等接入過程[7]。具體為:

1）搜索網絡，與網絡建立粗同步 在初始化或丟失信號之后，節點應該搜索MSH-NCFG消息來獲取與網絡的粗同步。

2）獲得網絡參數 節點接收的MSH-NCFG消息，使其能和網絡保持同步。

3）開放負責信道 當新節點選擇它的一個鄰點作為候選負責節點，此新節點就成為候選節點。在進一步的初始化過程中，候選節點要請求候選負責節點建立臨時調度，以在候選節點初始化過程中進行消息傳遞。

4）協商基本容量 在Mesh網絡拓撲結構，2個節點間建立邏輯鏈路后，要進行基本的容量的協商。請求建立邏輯鏈路的節點以網絡中用戶節點的身份發出SBC-REQ消息。

5）節點的鑒權 新節點需要經過鑒權才能進入網絡。

6）節點注冊 注冊是給一個節點安排節點ID的過程。

7）建立IP連接 節點通過DHDP獲得IP地址，此過程在負責信道上發生。

8）獲得網絡時間 Mesh網絡中的節點需要通過IETF RFC868中定義的協議來獲得網絡時間。此消息通過UDP在負責信道上傳播。

9）傳遞操作參數 獲得IP地址后，節點要使用FTP下載參數文件。

10）建立預備的傳輸參數 在PMP網絡拓撲結構中，通過使用DSx消息建立基于連接的QoS預備；在Mesh網絡拓撲結構中，Mesh CID逐包地進行預備，Mesh節點在傳輸操作參數的過程中獲得鑒權的QoS參數集。

11）和鄰點建立連接 進入網絡后，節點成為網絡的完全功能節點，可以和負責節點以外的點建立直接鏈路。

12）負責節點工作 當界定成為網絡的完全功能節點，可以和負責節點以外的點建立直接鏈路時，負責節點的工作就完成了，可以關閉負責信道。

通過以上接入過程，一個新的節點就成為了網絡節點的新加入節點，該節點可以和鄰節點直接通信，并且可以通過中繼聯系到網絡中的任意節點。

雖然標準已經對新節點接入需要遵循的一般步驟做了具體規定，但其接入的成功率及接入延時等問題仍然值得關注。文獻[8]分析了標準所定義的節點接入算法，指出了現有算法所存在的問題，并給出了相應改進后的算法以及其仿真結果。

2 IEEE 802.16d Mesh關鍵機制分析

針對Mesh網絡結構的特殊性，目前IEEE 802.16d Mesh關鍵機制的研究主要集中在網絡調度機制、功率控制機制和網絡路由機制3個方面。

2.1 網絡調度機制

在IEEE 802.16d Mesh網絡中，主要有2種分配無線資源的機制：集中式調度（Centralized Scheduling）和分布式調度（Distributed Scheduling）。 在 IEEE 802.16d Mesh模式的調度機制研究中，主要也都是基于以上2種調度方式的研究，但也有就以上2種調度方式的存在的問題做討論和研究，并提出新的調度模型。文獻[9]提出了一種分層帶寬調度模型，并分析、求解了分層調度的最優解，這是一種調度機制跨層設計思想，這也為IEEE 802.16d Mesh模式下的調度機制提供一種新的研究思路。

2.1.1集中式調度

在集中式調度里，調度由MBS集中控制，MBS定義MSS的發送時間，根據MSS的資源請求決定流安排。MBS收集在一定跳數范圍內所有MSS的資源請求，以獲取拓撲信息和信道信息。然后它建立一個樹形的路由結構，確定各條鏈路上的突發屬性，并在MSH-CSCF消息中廣播。同時，它還決定網絡中各條鏈路上下行所獲得的資源的數量，并通過MSHCSCF消息通知給所有的MSS。該消息并不包含確切的調度，但包含了各個MSS可用以計算確切調度的參數。如圖3所示，集中式調度中，MBS和MSS同處于一棵調度樹中，其中MBS位于調度樹的根部，MSS位于調度樹的各個樹枝節點處，網絡中的數據流在調度樹的樹枝上沿箭頭方向雙向傳輸。該調度方式主要用于MSS的數據需要通過MBS路由至外部網絡或其他MBS的情況。

圖3調度機制Fig.3 Scheduling mechanism

集中式調度機制中，MBS負責整個網絡通信過程中MSS之間的資源分配關系，因此在一定程度上可以避免鏈路上的傳輸碰撞問題，有效解決MSS之間對于資源的競爭。但也容易出現問題。例如，由于數據都是往來于MBS，越靠近MBS的節點，需要中繼的數據越多，因此越可能成為影響網絡吞吐量的瓶頸節點。目前有較多文獻研究集中式調度算法[10-11]，以提高集中式調度網絡的吞吐效率。也有提出采用定向天線來提高網絡吞吐量的方法，文獻[12]則提出了一種利用多波束智能天線提高WiMax Mesh網絡集中調度性能的方法，其主要思想就是在網絡節點上（尤其是在瓶頸節點上）使用多波束智能天線，使更多鏈路并行傳輸，從而達到有效解決瓶頸問題的目的。近年來，結合智能天線技術的優勢來提高網絡的吞吐效率和調度性能也成為了一個新的研究方向。

2.1.2分布式調度

分布式調度與集中式調度的區別在于流量的分布和調度方式的不同。如圖3所示，集中式調度方式，數據流只能在調度樹中的樹枝上沿箭頭方向雙向傳輸，而分布式調度的數據流不但可以發生在調度樹枝上，也可以發生在虛線所示的不屬于調度樹的鏈路上。因此，分布式調度減少了對MBS的依賴，與此同時也增加了通信中鏈路發生沖突碰撞的可能性。為此分布式調度又根據調度消息的發送是否存在協調機制分為協調式分布調度 （Coordinated Distributed Scheduling）和非協調分布調度（Uncoordinated Distributed Scheduling）。協調分布式調度，各個節點使用每幀的部分或全部控制子幀部分周期性地發送自己的調度結果，并基于PMP方式對所有的鄰居節點請求調度改變。所以在兩跳范圍內的所有節點的傳輸都將是協調的。非協調分布式調度，可快速以Ad-Hoc方式逐條鏈路地建立調度，調度通過2個節點之間的直接請求或準許而得以建立，并保證數據傳輸將不與協調分布式調度以及集中式調度方式所調度的數據和控制流相沖突。

分布式調度中，在MSH-DSCH消息中用一個專用的比特來表示，比特值為0，表示是協調分布式調度；為1，則表示是非協調分布式調度。在協調和非協調分布式調度里，所有的節點都要有規律地間隔發送分布式調度包，來告訴所有的鄰點自己的調度。協調分布式調度信息由MSH-DSCH消息來承載。協調分布式調度的MSH-DSCH在控制子幀中發送，非協調分布式的MSH-DSCH在數據子幀中發送。因此，在協調分布式調度中，控制子幀使用無碰撞的方式來傳輸調度包；而在非協調分布式調度中，傳輸調度包則部分的采用競爭方式，容易發生碰撞。

IEEE802.16d Mesh模式中的協調和非協調分布式調度都采用三次握手方式[13]，如圖4所示，源-目標節點通過請求、許可、認證3個過程確定用于傳輸數據的微時隙，完成對數據部分的調度。并且在協議規定了各個節點計算自己發送機會的調度算法，以實現各個節點之間發送機會的公平性。

圖43次握手過程Fig.4 Process of three-way handshake

2.2 網絡功率控制

在IEEE802.16d Mesh網絡中采用功率控制機制，不但能夠降低對鄰近節點的干擾、保障用戶的QoS，還可以降低網絡能耗，提高信道的空間復用度，最終提高整個網絡的容量。IEEE802.16d Mesh網絡是一種新型的分布式網絡結構。結合其網絡特性，目前IEEE802.16d Mesh網絡中的功率控制機制的研究重點在于對分布式功率控制技術的研究。

分布式功率控制[14]是一種由網絡中節點自行進行功率控制的方法，以在接收端接收到的SIR是否相等，來進行相應的網絡功率控制。該算法首先在窄帶蜂窩系統中提出，通過迭代法近似實現最佳功率控制。分布式功率控制需要的網絡信息較少，控制方法簡單，控制速度快，而且符合分布式網絡的特性，因此在分布式網絡中大多使用分布式功率控制。

在IEEE802.16協議中并未對功率控制的具體算法做出明確規定，因此這就為分布式功率控制研究提供很大空間。目前，在眾多的基于傳統蜂窩網絡的分布式控制算法中，Grandhi等[15]人提出的分布式帶約束的功率控制是被學術界廣泛接收的算法之一，也有文獻[16]對基于遺傳算法的功率控制方法做了一定研究，這些都為IEEE802.16d Mesh網絡中的功率算法研究提供參考。如何在結合IEEE802.16d Mesh網絡本身特點的同時，發揮出分布式功率算法的優勢，使之更好適用于IEEE802.16d Mesh網絡，是IEEE802.16d Mesh網絡功率控制機制研究的重點之一。另外，基于博弈論的分布式功率控制機制[17]也是解決IEEE802.16d Mesh網絡功率控制問題的另一個研究熱點。

2.3 網絡路由機制

根據調度方式的不同，IEEE802.16d Mesh網絡中的路由算法可分為集中式路由和分布式路由。集中式路由為樹形結構，目標是建立并周期性維護一棵由網絡內所有參與集中式調度的激活節點構成的路由樹。該類路由大致可以分為3類：面向拓撲的路由、面向負載的路由和面向干擾的路由。而對于IEEE802.16d Mesh網絡中的分布式路由，則可以充分借鑒Ad-Hoc網絡中的路由算法[18-19]，較為經典的算法有AODV、WRP、DSR等。然而，由于無線城域網中的IEEE802.16d Mesh網絡并非像Ad-Hoc網絡那樣在局域網內具有完全分布式的網絡結構，因此其相對應的路由算法也需要更多地以時延、吞吐量、可靠性、作為優先考慮的指標來做更進一步的研究與改進。

3 結 論

從本文分析來看，IEEE802.16d Mesh網絡的關鍵機制的研究已不僅局限于沖突避免、無線調度、無線路由等機制上的改進或是算法上的優化了，而是開始逐漸融合其他先進的物理層技術。分析和評估諸如智能天線、UWB、MIMO等先進技術的特點，并將其引入到IEEE802.16d Mesh網絡中以提高網絡性能，這也成為了IEEE802.16d Mesh網絡關鍵機制研究的一個重要方向。

[1]IEEE 802.16-2004 IEEE standard for local and metropolitan area networks part 16:Air interface for fixed broadband wireless access systems[S].2004.

[2]IEEE 802.16e-2005 IEEE standard for local and metropolitan area networks part 16:Air interface for fixed and mobile broadband wireless access systems-amendment for physical and medium access control layers for combined fixed and mobile operation in licensed bands[S].2005.

[3]IEEE 802.16j D2 Baseline document for draft standard for local and metropolitan area networks Part 16:Air interface for fixed and mobile broadband wireless access systemsmulti hop relay specification[S].2007.

[4]高澤華，趙國安，寧帆，等.寬帶無線城域網—WiMAX技術與應用[M].北京:人民郵電出版社，2008.

[5]張峻愷，馮穗力，葉梧，等.IEEE 802.16j集中和分布控制模式傳輸效率分析與仿真[J].桂林電子科技大學學報，2009（2）:92-93.ZHANG Jun-kai，FENG Sui-li，YE Wu，et al.Analysis and simulation of the transmission efficiency in relay-based IEEE 802.16j centralized and distributed scheduling[J].Journal of Guilin University of Electronic Technology，2009（2）:92-93

[6]李丹丹，靳浩.多跳網絡技術在WiMAX網絡中的應用[J].數據通信，2008（3）:21-22.LI Dan-dan，JIN Hao.The application of multi-hop network technology in the WiMAX network[J].Data Communications，2008（3）:21-22.

[7]劉覓，彭木根，王文博.基于 IEEE 802.16標準的Mesh機制研究[J].數據通信，2005（5）:24-26.LIU Mi，PENG Mu-gen，WANG Wen-bo.The research of mesh mechanism in IEEE802.16 standard[J].Data Communications，2005（5）:24-26.

[8]姚星鷹，李云.基于IEEE802.16 Mesh網絡節點接入過程的研究[J]．通信技術，2009（2）:114-115.YAO Xing-ying，LI Yun.Research of network entry in IEEE 802.16 mesh network[J].Communications Technology，2009（2）:114-115.

[9]關艷峰，胡愛群，陳立全.Mesh模式的IEEE802.16系統的帶寬調度研究[J]．應用科學學報，2006（4）:355-358.GUAN Yan-feng，HU Ai-qun，CHEN Li-quan.Bandwidth schedule in IEEE 802.16 systems based on Mesh mode[J].Journal of Applied Sciences， 2006（4）:355-358.

[10]劉圣海，馮穗力，葉梧，等.一種基于 IEEE802.16無線MESH網絡集中調度機制的時隙分配方法[J].電路與系統學報，2009（1）:43-44.LIU Sheng-hai，FENG Sui-li，YE Wu，et al.A slot allocation algorithm for the IEEE802.16 based on wireless mesh networks in centralized scheduling scheme[J].Journal of Circuits and Systems，2009（1）:43-44.

[11]沈明玉，羅維思.一種提高WiMax mesh網絡吞吐量的方案[J].合肥工業大學學報：自然科學版，2008（10）:1632-1633.SHENG Ming-yu，LUO Si-wei.Throughput enhancement in WiMax Mesh networks[J].Journal of Hefei University of Technology，2008（10）:1632-1633.

[12]劉圣海，馮穗力，葉梧，等.利用多波束智能天線提高Wimax MESH網絡集中調度性能的方法[J].科學技術與工程，2008（22）:6016-6017.LIU Sheng-hai，FENG Sui-li，YE Wu，et al.Method to improve the performance ofcentralized scheduling for WIMAX Mesh networks by using multi-beam smart antennas[J].Science Technology and Engineering，2008 （22）:6016-6017.

[13]曾智慧，劉富強，陶健，等.IEEE 802.16 Mesh模式下MAC調度機制的研究[J].計算機工程與應用，2005（23）:136-137.ZENG Zhi-hui，LIU Fu-qiang，TAO Jian，et al.Research on MAC scheduling mechanism in IEEE 802.16 Mesh mode[J].Computer Engineering and Applications，2005 （23）:136-137.

[14]彭木根，王英杰，王文博.寬帶無線Mesh網絡的應用與挑戰[J].數據通信，2007（1）:4-5.PENG Mu-gen，WANG Ying-jie，WANG Wen-bo.The applications and challenges of broadband wireless Mesh network[J].Data Communications，2007（1）:4-5.

[15]Grandhi S A， Zander J，Yates R.Constrained power control[J].Wireless Personal Communications， 1995（1）:257-270.

[16]文曉聰，張會生，張玲霞.一種基于遺傳算法的聯合功率和速率控制算法[J].系統仿真學報，2008（18）:4957-4958.WEN Xiao-cong，ZHANG Hui-sheng，ZhANG Ling-xia.Joint power and rate control algorithm based on genetic algorithm[J].Journal of System Simulation，2008（18）:4957-4958.

[17]滿成圓，劉雁，周文安.基于博弈論的寬帶無線系統功率控制算法研究[J].北京郵電大學學報，2005（5）:122-123.MAN Cheng-yuan，LIU Yan，ZHOU Wen-an.Research on the power control based on game theory in broadband wireless systems [J].Journal of Beijing University of Posts and Telecommunications，2005（5）:122-123.

[18]孫曉艷，李建東，張光輝，等.Ad Hoc中的常用路由算法分析[J].現代電子技術，2003，（13）:20-21.SUN Xiao-yan，LI Jian-dong，ZHANG Guang-hui，et al.Analysis of the several routing algorithms in Ad Hoc[J].Modern Electronics Technique，2003（13）:20-21.

[19]劉元安，唐碧華，胡月梅.Ad hoc網絡中的路由算法[J]．北京郵電大學學報，2004（2）:2-4.LIU Yuan-an，TANG Bi-hua，HU Yue-mei.Routing algorithms in mobile Ad hoc Networks[J].Journal of Beijing University of Posts and Telecommunications，2004（2）:2-4.