基于IEEE 802.11s的無線Mesh網絡路由協議研究

摘 要： 基于IEEE 802.11s的無線Mesh網絡已成為機動寬帶接入技術研究領域的一個研究熱點。對無線Mesh網絡中的關鍵技術——混合無線Mesh協議（HWMP）進行詳細的分析，與傳統按需路由機制相比，該協議既具有先驗式路由協議的靈活性，亦具備按需路由協議的有效性，同時，對該協議度量機制做出改進，其將在應急通信等特殊應用環境中發揮重要作用。

關鍵詞： 無線Mesh網絡； IEEE 802.11s； 混合無線Mesh協議； 樹型路由； 按需路由； 空中傳播時間鏈路判據

中圖分類號： TN711?34； TP393.02 文獻標識碼： A 文章編號： 1004?373X（2013）23?0036?05

Research on hybrid wireless Mesh protocol based on IEEE 802.11s

LI Qian， LIU Jing?wei， ZHOU Ya?nan， HAN Zhong?hua

（North China Institute of Computing Technology， Beijing 100083， China）

Abstract： The wireless Mesh network （WMN） based on IEEE 802.11s has emerged as a research hotspot in the maneuvering BBA technology research field. The hybrid wireless Mesh protocol （HWMP） in wireless Mesh networks is analyzed in detail. Compared with the traditional on?demand routing， the protocol has the flexibility of proactive routing protocol and effectiveness of on?demand routing protocol. The metric mechanism of the protocol was improved. It will play an important role in the application of emergency communication area.

Keywords： wireless Mesh network； IEEE 802.11s； hybrid wireless Mesh protocol； proactive routing； on?demand routing； airtime link metric

0 引 言

無線Mesh網絡是一種多跳、機動性強、抗毀性強的無線網絡結構，靈活的組網方式以及易部署的特點是其在應急系統等特殊環境中應用的重要前提。路由協議的設計是設計無線Mesh網絡的關鍵問題之一，如何進行路由選擇是影響網絡性能的一個重要問題。在探討關鍵技術的同時，應用需求的提出也是各國際標準化組織在多種覆蓋不同物理范圍的無線網絡技術標準中融入對Mesh組網方式的誘因，如支持WLAN的IEEE 802.11[1?2]標準、支持WMAN的IEEE 802.16標準[3]以及支持WPAN的IEEE 802.15標準[4]，這些標準均在支持無線Mesh網絡及其相關關鍵技術方面做出了努力。

本文介紹IEEE 802.11s中的關鍵技術之一——混合無線Mesh協議（Hybrid Wireless Mesh Protocol， HWMP），盡管該協議存在根部節點易形成網絡瓶頸的不足，但其結合了先驗式路由協議的靈活性和按需路由協議的有效性，在應急系統中可以發揮重要作用。因此，改進現有協議以適應特殊領域的應用成為下一步的主要研究內容。

1 IEEE 802.11s標準化情況

IEEE 802.11于2004年7月成立Mesh任務組[5]（802.11 TGs任務組）。TGs任務組研究支持無線分布式系統（Wireless Distribution System，WDS）的協議，在原IEEE 802.11體系結構與協議基礎上提供ESS（Extended Service Station）[6]的Mesh功能，使各WLAN設備能夠無線互連、實現自動拓撲發現并進行動態路徑的配置，同時，對MAC協議進行了擴展，支持單播/多播/廣播，并在MAC層使用無線信道感知機制與多跳拓撲來達到理想的覆蓋范圍，保證網絡的靈活性。IEEE 802.11s的優勢體現在以下方面：增加覆蓋范圍和靈活性；性能可靠；安全；設備間的多媒體傳輸；電池驅動設備的節能機制；互操作性。

WLAN Mesh網絡結構與節點類型[7]如圖1所示。

Mesh節點（Mesh Point，MP）：與相鄰MP建立通信鏈路，參與ESS Mesh網絡服務；

圖1 網絡結構與節點類型

Mesh接入點（Mesh Access Point，MAP）：擁有MP的全部功能，并提供接入服務；

Mesh入口節點（Mesh Portal，MPP）：該節點為數據提供在Mesh網絡與其他分布式系統或非802.11系統間的進出節點；

用戶站（Station，STA）：通過MAP與Mesh網絡通信的站點，通常指傳統的802.11用戶終端，其不在ESS Mesh網絡范圍內。

IEEE 802.11s基于傳統物理層標準，提供WLAN Mesh服務，包括拓撲發現、路徑選擇和轉發、媒體接入協調、Mesh網絡的配置和管理、網絡測量、網絡互連和安全等功能模塊。IEEE 802.11s協議各個功能模塊如圖2所示。

圖2 IEEE 802.11s功能組件結構圖

Mesh拓撲發現、路徑選擇和轉發模塊在MAC協議中具有重要作用，也是IEEE 802.11s中的一個關鍵功能，下面將對IEEE 802.11s定義的HWMP協議進行詳細分析。

2 混合無線Mesh協議（HWMP）

HWMP協議將先驗式路由協議和基于樹型拓撲的反應式路由（即按需路由）協議相結合[8]，廣泛應用于基礎設施Mesh模式和客戶機Mesh模式的無線Mesh網絡。網絡中的節點可以進行最優路由發現和路由維護，或依賴根節點（即MPP）形成的樹型拓撲進行路由發現和路由維護。路由發現過程根據網絡是否配置根節點有所區別。通常，樹型拓撲配置MPP為根節點，在這樣的情況下，其余的MP按需地維護到達根節點的路徑，并且形成樹型拓撲路由。

2.1 幀格式

幀格式如圖3所示。

2.2 消息格式

HWMP協議實現通過路徑請求消息PREQ（Path Request）、路徑響應消息PREP（Path Reply）、路徑錯誤消息PERR（PathError）、路徑響應確認ACK（PREP ACK）和根宣告消息RA（Root Announcement）。PREQ用于路由請求，PREP用于對路由請求消息的應答，PERR用于鏈路發生錯誤時進行的應答或維護，以及RA用于對自己根節點身份的消息的廣播。

2.2.1 PREQ

路徑請求消息PREQ（Path Request）格式如圖4所示。

標志位當Bit 0=0時，為單播；Bit 0=1時，為廣播；Bit 1～7為預留位。PREQ控制標識包括目的標識DO（Destination Only）、回復轉發標識（Reply?and?Forward），其中，DO=0時，表示中間節點接收到PREQ消息產生PREP；DO=1時，表示目的節點產生PREP消息回應該路徑請求，該路徑請求和路徑回復包含了完整路徑并收集當前的metric值，以確保度量值是最新的。TTL（Time to Live）即生存時間，定義了PREQ的跳數范圍。

2.2.2 PREP

路徑響應消息PREP（Path Reply）格式如圖5所示。

圖5 路徑響應消息格式

HWMP允許使用一條PREQ消息尋找到達多個目標的路徑。Mode Flags標志位中，Bit 0～7均為預留位；Life Time為該路徑的有效生存時間。Metric為從目的MAC地址到處理RREP消息的節點之間所積累的度量（metric）。

2.2.3 PERR

路徑錯誤消息PERR（PathError）格式如圖6所示。

圖6 路徑錯誤消息格式

其中，標志位的Bit 0～7為預留位。

2.2.4 PREP ACK

路徑響應確認ACK（PathReply ACK）格式如圖7所示。

圖7 路徑響應確認消息格式

其中，Destination Address為建立路由的目的節點的MAC地址；Source Address為在路由建立過程中發起RREQ消息的節點的MAC地址。

2.2.5 RANN

根宣告消息RANN（Root Announcement）格式如圖8所示。

圖8 根宣告消息格式

Mesh Portal中配置周期性RANN消息，以便使用先驗式的擴展功能。RANN消息中定義了兩個標識：宣告類型標識AN（Announcement Type Flag），用于區分非根Portal（AN=0）與根Portal（AN=1）；注冊標識RE（Registration Flag）用于Mesh節點區分RANN的兩種不同處理模式。

2.3 HWMP協議的按需路由

HWMP協議的按需路由是基于RM?AODV（Radio Metric AODV）的協議[9?10]。HWMP協議中的按需路由使用PREQ和PREP機制在兩節點之間建立路由，節點間使用PREQ和PREP消息進行度量信息交互，并且在PREQ中采用序列號來保證路由的時效性。

當源節點S試圖到達目的節點D時，首先，源節點廣播PREQ消息，并初始化metric為0。當中間節點收到PREQ消息時，該節點創建到源節點S的一條路徑，或PREQ經過的路徑優于當前節點到達源節點S的路徑時，對當前的路徑進行更新。如果路徑進行了創建或更新的過程，則節點更新PREQ消息的路徑標志域并進行轉發，當創建或更新路徑完成后，目的節點D向源節點S回復單播的PREP消息。當中間節點接收到PREP消息后，建立到目的節點D的路徑，并且將PREP向源節點S轉發。源節點S收到PREP消息后，建立到達目的節點D的路徑；若目的節點收到的消息中的路徑優于當前路徑，則節點更新到達源節點S的路徑，并且在該路徑上發送新的PREP給源節點S。以上即為源節點S與目的節點D之間的雙向鏈路的建立過程。

DO和RF機制的目的是為了使得節點利用由中間節點產生PREP消息快速建立路由，并且滿足發送數據幀的路由發現時延較低和較低的緩存要求，當反向路徑建立過程完成后，路由選擇最佳的路徑度量機制。當源節點S到目的節點D之間沒有一條有效的路由，并且需要和目的節點之間建立一條新路由時，源節點設置PREQ消息中的目的DO標志位為0，設置RF標志位為1。正如前文所提到的，RREQ中的DO標志位通常設置為1。

2.4 HWMP協議的樹型路由

HWMP協議將按需路由與先驗式路由相結合，樹型結構將一個MP（通常是MPP）配置為根節點，其他的MP均先驗式地維護到根節點的路徑，生成并維護一個距離矢量樹。HWMP中樹型路由有兩種實現方式：

（1）先驗式樹型路由

通過PREQ消息與PREP消息的交互實現，即HWMP注冊標志位RE未注冊，如圖9所示。首先，根節點廣播PREQ消息，收到PREQ消息的MP進行逐級路由查找并建立路由，從而將根節點到所有MP的路由建立起來，由此先驗式樹型路由建立成功。在該實現方式中，MP可以先驗用PREQ消息和PREP消息進行路由建立，并先驗式維護到根節點的路徑。

（2）按需樹型路由

該方式通過RANN消息實現，即HWMP注冊標志位已注冊，如圖9所示。在拓撲形成過程中，首先根節點廣播RANN消息，RANN消息中包含了到根MP的路由metric。在Mesh中的收到RANN消息的每個MP記錄根節點的信息，同時，向根MP發送一個單播的PREQ消息，根MP會發送一個PREP消息響應接收到的PREQ消息，從而由根節點建立樹型路由。

無論是先驗式樹型路由還是按需樹型路由，被選為根節點的MP要周期性地發送PREQ或RANN以維護和更新樹。一旦MP選擇了到根節點路徑的父MP，它將周期的向父MP發送維護PREQ并接收返回的PREP來維護這條路徑。只要當前父節點不能提供最優路徑，MP 將根據在根節點上配置的策略切換到另一個父節點。如果當前父路徑丟失，MP 立刻廣播拓撲 PREQ 并沿著這個拓撲發送 PRER，使任何包含這條鏈路按需路由的節點能夠從路由表中刪除這個表項。如果在一個時間間隔內沒有找到另一個有到根節點的有效路徑的父 MP，向所有子 MP發送PERR。

圖9 HWMP路由協議的配置選項結構

2.5 ATC度量機制

空中傳播時間鏈路判據（Airtime Link Metric）是IEEE 802.11s設備互操作默認的RA（Radio?aware）路徑度量機制，影響特定鏈路上發送一幀所消耗的信道資源，含空時度量總和最小的路徑為最優路徑。

鏈路的空時損耗ATC（Airtime Cost）[Ca]為：

[Ca=Oca+Op+Btri11-efr] （1）

其中，一幀的信道接入開銷[Oca、]MAC協議開銷[Op、]比特數[Bt]三者均為常數，其值取決于IEEE 802.11傳輸技術。傳輸比特率r Mb/s是在當前的條件下，Mesh節點傳輸大小為[Bt]的幀，差錯率為[efr]時的速率。

2.6 ATCn改進機制

ALM是一種近似的測量方法，其主要目的是為了降低具體實現和交互的難度。該度量機制考慮的是傳輸速率與信道質量。但是，鏈路質量好壞直接影響著路徑的選擇，其也是路由判據中需要考慮的重要因素。在無線Mesh網絡的ALM判據基礎上，增加鏈路質量作為路由判據，可得到式（2）。

鏈路的空時損耗ATCn（Airtime Cost）[Cap]為：

[Cap=minfor channel in the channel listαOca+Op+Btri11-efr] （2）

3 HWMP仿真場景及實驗結果

本文采用NS仿真軟件構建無線Mesh網絡的仿真平臺，對基于ATC度量機制的HWMP協議和ATCn度量機制的HWMP協議進行對比分析驗證。

實驗環境：在1 000 m×1 000 m范圍內，產生5個固定節點、30個節點的隨機拓撲。以Random Waypoint模型仿真移動節點的固定速率隨機移動。節點配置single?radio單接口，傳輸協議采用UDP。

仿真參數的設置見表1。

表1 仿真參數設置

[仿真參數＼數值＼仿真時間 /s＼1 000＼仿真區域 /m2＼1 000×1 000＼數據流數＼10＼數據包大小 /b＼1 024＼隊列大小＼255＼CWmin＼15＼CWmax＼1 023＼]

端到端平均時延，是指所有成功傳遞的分組的接收時間和發送時間差的平均值。如圖10所示，與ATC相比，ATCn機制的平均端到端時延較小。基于鏈路質量的路由判據減少了平均端到端時延。

圖10 ATC機制與ATCn機制端到端時延比較

吞吐量是指目的節點接收的數據包個數/仿真時間。如圖11所示，基于ATCn機制的HWMP協議的吞吐量高于基于ATC機制的HWMP協議。該機制進行鏈路質量選擇，減少了包的沖突數量，且丟包數量降低，從而吞吐量得到了提高。

圖11 ATC機制與ATCn機制吞吐量比較

4 結 語

HWMP協議將按需路由與先驗式路由結合，具有先驗式路由協議的靈活性，亦具有按需路由協議的有效性。對該協議度量機制做出的改進，與ALM機制下的HWMP協議相比，在端到端時延和吞吐量等性能方面都有一定程度的提升。但其也有不足之處，主要表現在：

（1）由于樹狀拓撲流量匯聚，靠近根部的鏈路容易形成網絡流量的瓶頸；

（2）混合路由機制在開始時有較長的時延，特別當消息從Mesh外經網關節點向Mesh內節點傳輸過程；

（3）與傳統的按需路由機制相比，混合路由機制只有確定目的節點在Mesh內的情況下才使用泛洪路徑發現；數據的組播和廣播不再需要泛洪，通過樹型拓撲進行數據的組播和廣播更加有效。

無線Mesh網絡作為一種新型的機動寬帶網絡，組網能力強、靈活且易部署，具有自適應性、可靠性和可擴充性等優點，路由等關鍵技術在無線Mesh網絡中起著重要的作用，相信在不久的將來，靈活方便的無線Mesh網絡將大大提高寬帶無線接入能力，并在應急通信等特殊應用領域中發揮其重要作用。

參考文獻

[1] IEEE 802 Standard Working Group. Wireless LAN medium access control （MAC） and physical layer （PHY） specifications： high?speed physical layer in the 5 GHz band [S]. USA： IEEE 802 Standard Working Group， 1999.

[2] IEEE. Draft standard for information technology?telecommunications and information exchange between systems： local and metropolitan area networks–specific requirements， part 11 [S/OL]. [2012?01?23]. http：// www. ieee.xplore.ieee.org/xpl/articleDetails.jsp？arnumber.

[3] IEEE. IEEE standard for local and metropolitan area networks part 16：air interface for fixed broadband wireless access systems [S/OL]. [2004?10?01]. http：// www. ieeexplore.ieee.org/iel5/9349/29691/01350465.

[4] SHAO Huai?Rong， LIU Yong， SIM Michael， et al. Information technology telecommunications and information exchange between systems?local and metropolitan networks?specific requirements?part 15.5： Mesh enhancements for IEEE 802.15 WPANs [EB/OL]. [2013?03?21]. http：//mentor.ieee.org.

[5] ZHANG Yan， LUO Ji?jun， HU Hong?lin. Wireless Mesh networking： architectures， protocols and standards [M]. [S.l.]： Auerbach Publications， 2006.

[6] IEEE802.11 TGs. Joint SEE?Mesh/Wi?Mesh， proposal to 802.11 TGs [EB/OL]. [2006?06?27]. http：//www.comnets.rwth?aachen.de/typo3conf/ext/cn.../passdownload.

[7] 郭達，張勇，彭小川.無線網狀網：架構、協議與標準[M].北京： 電子工業出版社，2008.

[8] CONNER W S， AOKI H. Proposed extensible approach for WLAN Mesh standardization [EB/OL]. [2008?05?26]. http：//www.citeulike.org/user/PitaGyros/art.

[9] 裴曉萍.HWMP路由協議的研究與仿真[D].西安：西安電子科技大學，2008.

[10] 楊孟珂，楊亞濤，白中英.基于HWNP協議的無線Mesh網絡多網關路由協議研究[J].微電子學與計算機，2009，26（12）：4?8.

作者簡介：李 茜 女，1983年出生，山西人，碩士，工程師。研究方向為無線自組網及無線Mesh網絡。

劉經緯 男，1979年出生，黑龍江人，碩士，工程師。研究方向為無線自組網及無線Mesh網絡。

周雅楠 女，1985年出生，河北人，碩士，助理工程師。研究方向為通信與移動計算。

韓仲華 男，1974年出生，北京人，高級工程師。研究方向為通信與移動計算。