無線Mesh網絡中一種分布式路由方案*

鐘 朗，李廣軍，楊學敏，楊云樂

（電子科技大學 通信與信息工程學院，四川 成都611731）

無線Mesh網絡中一種分布式路由方案*

鐘 朗，李廣軍，楊學敏，楊云樂

（電子科技大學 通信與信息工程學院，四川 成都611731）

在多射頻多信道無線Mesh網絡中，鏈路負載和節點位置的變化將導致網絡性能的下降。針對此問題，在混合無線網狀路由協議反應式路由基礎上，設計了一種新的混合信道分配的分布式路由算法。該算法在路由建立的同時可實現以數據流為單位的最優信道分配，且能避免因單節點失效導致整個網絡崩潰的危險。仿真結果表明，提出的RHCA算法較傳統算法在網絡吞吐量和端到端平均時延方面均有顯著優勢。另外，在節點移動場景下，所提出的分布式路由算法較其他方法能獲得更高的吞吐量和更好的穩健性。

無線Mesh網絡；分布式路由算法；信道分配

0 引言

在無線Mesh網絡中，信道分配和路由協議是較為關鍵的問題，且二者聯系緊密。如何協調其關系以更好地利用網絡資源、提升網絡性能是當前研究熱點之一。對于信道分配的分類，按照網絡中 Mesh節點（Mesh Point，MP）射頻接口數量的不同，可分為單射頻信道分配和多射頻信道分配。由于后者能帶來更大的網絡吞吐量，困此應用更為廣泛[1]。此外，若根據信道更新頻繁程度，又可分為靜態信道分配、動態信道分配和混合信道分配[2]。而對于路由選擇，按照路由建立和業務請求之間的關系，可以分為先驗式路由協議[3]、反應式路由協議[4]和混合式路由協議[5]。

傳統的無線Mesh網絡中，信道分配和路由選擇是分開進行的，一般先進行信道分配，再執行路由選擇。當網絡拓撲以及業務流量相對穩定時，該方式可以充分地利用網絡資源。然而一旦網絡拓撲或鏈路負載發生變動，以上方法無法根據實時信息調整資源配置，致使資源利用率大幅降低，甚至出現節點孤立，影響正常的數據傳輸。

針對上述問題，近年來出現了諸多關于融合信道分配和路由選擇的研究，大致可分為集中式[6]和分布式[7]兩類，其中分布式路由算法不需要中央處理節點，且可避免困單個節點失效導致整個網絡崩潰的危險，困此得到更為廣泛的研究和應用。本文主要針對多射頻多信道(Multi-Radio Multi-Channel，MRMC)無線 Mesh網絡中網絡負載及節點位置實時變化等實際場景，在混合無線網狀路由協議（Hybrid Wireless Mesh Routing Protocol，HWMP）反應式路由基礎上，設計了一種新的混合信道分配的分布式路由算法（Routing based on Hybrid Channel Assignment，RHCA）。

1 信道分配方案

由于本文提出的RHCA方案基于動態網絡設計，困此信道分配策略應采用動態分配或混合分配?？紤]到混合分配方案具有更好的網絡連通性，故選擇后者。

1.1 系統模型

本文無線Mesh網絡模型如圖1所示，采用網格型網絡拓撲，共設置 32個節點，相鄰節點間距 170m。且本文的信道分配過程只考慮如何減小鏈路干擾，達到以數據流為單位的鏈路干擾最小化信道分配。其余諸如網絡負載等困素的影響則在路由選擇時考慮。干擾模型方面采用文獻[8]中的協議干擾模型，如圖 2所示，當鏈路ei、ej節點間跳數不少于兩跳時，才認為二者無相互干擾。雖然該模型是一個NP問題，但其信道分配模型融合于路由算法中，具體分配方式將在后文中詳述。

圖1 網絡拓撲結構

圖2 基于鏈路的協議干擾模型

1.2 接口分配策略和通信協調機制

在接口分配上，所有節點均固定使用一個無線射頻接口搭配標號為1的信道作為固定接口，用于傳遞網絡管理消息，當網絡負載較重時亦可傳送數據。其余接口全部用于數據傳輸，稱為動態接口(Dynamic Radio Interface，DRI)，其分配信道在傳輸過程中可實時切換。

另外，本文的通信協調機制主要通過分析網絡中的相鄰節點DRI信道分配、路徑請求（Path Request，PREQ）消息幀前兩跳DRI信息以及各個節點Metric信息等，得到與下一跳鏈路干擾最小的信道。該機制在路由過程中實施。當源節點發送PREQ，尋得最優路徑之后，目的節點在回復路徑響應（Path Reply，PREP）消息過程中逐一節點綁定通信接口，并分配信道。

1.3 接口釋放機制

本文對源節點的接口釋放機制進行了如下設計。在開始發起數據業務后，數據流監聽模塊隨即啟動，并設置監聽標志位 tags為 1，表示監聽有效。當收到路徑錯誤消息報文（Path Error，PERR）時，需要重新尋路，于是釋放現有路徑上節點所用接口。若沒有收到PERR則將每次監聽時刻同當前源節點最新發送數據時刻做差值，如果該差值小于設定閾值，表示源節點仍在發送數據，否則認為發送完畢，tags置零，監聽停止，并發送 CHCLR，同時等待CLRACK。若源節點收到CLRACK，則執行接口釋放操作，否則重發CHCLR報文；若超過規定重發次數后仍未收到CLRACK，則直接執行接口釋放操作。

2 RHCA路由算法設計

本文提出的RHCA路由算法主要針對網絡拓撲不固定和業務負載多變的場景。算法采用分布式信道分配，且通信協調在路由響應階段完成。由于該方案基于IEEE 802.11s中混合無線網狀路由協議 HWMP的反應式路由算法改進而來，所以在管理消息幀格式、路由判據、PREP和 PREQ等管理信息的廣播和接口釋放機制方面，基本沿用自HWMP算法。

2.1 路由建立過程

在提出的RHCA路由方案中，當發起一項業務時，源節點先判斷是否存在到達目的節點的路由信息，若已存在則只需要按照路由表向目的節點單播PREQ；若沒有則發起到目的節點的PREQ廣播請求，各節點收到請求后，判斷自身是否為目的節點，如果不是則按中間節點處理方式處理PREQ信息，直到目的節點收到請求，進入響應階段。此后目的節點首先判斷收到的消息是否為新的PREQ，若不是則直接丟棄；如果是則按PREQ所尋路徑開始單播回復PREP?；貜瓦^程中逐跳進行接口綁定和信道分配。當PREP返回至源節點后，鏈路的雙向路徑建立完畢，開始數據傳輸。

2.2 路由維護過程

RHCA算法的路由維護在HWMP基礎上，加入了對故障困素的考慮，增加了如下相關操作。

當發現故障時，處于故障上游的節點向源節點單播PERR，源節點接收到 PERR后，執行路徑上各節點接口釋放操作，當上游各節點收到CLRACK后開始廣播到目的節點的PREQ重新尋路；而故障下游節點在未收到CHCLR的情況下，若等待超時，則判定為上游節點故障，遂開始執行鏈路后續節點的接口釋放操作。此方案既保證了路由得到修復，又完成了故障節點下游的接口釋放，避免了故障鏈路占用信道資源。

3 性能仿真分析

為了模擬網絡多變性，仿真分別在不同的網絡負載和網絡拓撲下進行，以便考察提出的RHCA方案的平均吞吐量和時延。同時為了便于比較，加入了HWMP路由分別搭配集中式信道分配(Centralized Hyacinth Channel Assignment，C-HYA)和MRMC HWMP(MMHWMP)路由算法結合節點優先級靜態信道分配(Nodes Priority Fixed Channel Allocation，NPFCA)兩種方案進行對比。仿真系統參數設置如表1所示。所有結果均為采用20個隨機種子進行仿真所得平均值，基本符合網絡數據統計特性。

表1 仿真系統的參數設置

3.1 不同網絡負載下性能分析

本次仿真采用網絡拓撲如圖1所示，并設12號節點為根節點。

仿真隨機選取 5對節點建立固定碼率(Constant Bit Rate，CBR)數據傳輸業務，CBR流速率為 600 kb/s到2 Mb/s不等，每組節點在仿真時間內隨機選擇時間發起業務，并持續 50 s，如果從發起業務到仿真結束不足50 s，則以仿真結束時間為準。全網可用正交信道數為6，仿真結果如圖3所示。

圖3 不同CBR傳輸速率下性能的比較

從圖3(a)可以看出，隨著CBR流速率的增加，三種算法總吞吐量都呈現遞增趨勢，而提出的RHCA路由算法所得網絡總吞吐量明顯高于前兩者，尤其在CBR速率為1.6 Mb/s時，其吞吐量較HWMP和MMHWMP分別高約17.7%和13.5%。

由圖 3(b)可知，隨著 CBR流速率的增加，三種算法的端到端平均時延也逐步增加，MMHWMP與HWMP方案在CBR流速率為＜1.6 Mb/s時平均時延差距不大，當速率大于1.6 Mb/s時差距逐漸拉大；RHCA方案的網絡時延顯著優于前兩者，尤其在CBR流速率為1.8 Mb/s時，分別較MMHWMP和HWMP有約0.06 s和0.12 s的優勢。

3.2 動態拓撲及負載場景下性能分析

初始網絡如圖1所示。設置節點移動模型為“Random Way point Mobility Model”[9]，各節點速率是在0m/s～2m/s中均勻分布的隨機變量，移動范圍限制在圖中二維空間內。網絡中運行兩組CBR數據任務，第一組隨機選取5對節點建立CBR數據業務，流速率為500 kb/s，仿真運行5 s后開始發送數據直至結束；仿真運行100 s后，再從余下的節點中隨機選取5對節點建立第二組CBR數據業務，流速率仍為 500 kb/s，同樣持續至仿真結束。仿真時間總共 200 s。全網可用正交信道數為 6，當仿真開始 20 s后，開啟移動模型。同時還增加了較為靈活的HWMP路由+公共信道分配（Common channel assignment，CCA）組合，以供參考。仿真結果如圖4所示。

圖4 移動環境中網絡吞吐量比較

從圖中可以看出，在仿真前 20 s范圍內，四種方案都處于穩態，此時本文提出的RHCA方案性能最優；當仿真開始20 s后，移動模型開啟，網絡拓撲開始變化，部分鏈路通信中斷，使得在 40 s～60 s期間，所有方案的吞吐量均有較大幅度下降；而在 60 s～100 s之間，隨著網絡拓撲持續變化，部分節點重新建立連接，使得四種方案吞吐量有不同程度回升，其中以RHCA回升最為明顯，最高時甚至超過HWMP+CCA方案近一倍；仿真100 s后，由于引入了 5條新數據流，網絡整體吞吐量有所上升，同樣以RHCA方案升幅最大，其性能領先HWMP-R+CCA約70%。

4 結論

本文主要針對MRMC無線Mesh網絡中，網絡負載可變以及網絡節點可移動的動態場景，在HWMP反應式路由算法基礎上，提出了一種融合信道分配和路由選擇的RHCA算法。仿真結果表明，此算法無論在網絡吞吐量還是端到端平均時延方面均有顯著優勢。同時仿真結果還驗證了在節點可移動的無線Mesh網絡中，RHCA較其他三種方案能獲得更高的吞吐量，同時具有更好的穩健性。

[1]PENG Y，YU Y，GUO L，et al.An efficient joint channel assignment and QoS routing protocol for IEEE 802.11 multi-radio multi-channel wireless Mesh networks[J].Journal of Network and Computer Applications，2013，36(2)：843-857.

[2]Zhang Yang，Luo Jijun，Hu Honglin.Wireless Mesh networking：architectures，protocols and standards[M].New York：Auerbach Publications，2006.

[3]PERKINS C E，WATSON T J.Highly dynamic destination sequenced distance vector routing(DSDV)for mobile computers[C].ACM SIGCOMM’94 Conference on Communications Architectures，1994：234-244.

[4]PERKINS C E，ROYER E M.Ad hoc on demand distance vector(AODV)routing[C].IEEE Workshop on Mobile Computing Systems and Applications，WMCSA(2)，1999：90-100.

[5]RADHAKRISHNAN S，RAO N S，RACHERLA G，et al.DST-A routing protocol for ad hoc networks using distributed spanning trees[C].IEEE Wireless Communications and Networking Conference，WCNC，1999：1543-1547.

[6]AVALLONE S，AKYILDIZ I F，VENTRE G.A channel and rate assignment algorithm and a layer-2.5 forwarding paradigm for multi-radio wireless Mesh networks[J].IEEE/ACM Transactions on Networking，2009，17(1)：267-280.

[7]RANIWALA A，CHIUEH T.Architecture and algorithms for an IEEE 802.11-based multi-channel wireless Mesh network[C].Annual Joint Conference of the IEEE Computer and Communications Societies，INFOCOM(24)，2005：2223-2234.

[8]XU K X，GERLA M，BAE S.How effective is the IEEE 802.11 RTS/CTS handshake in ad hoc networks[C].Global Telecommunications Conference，2002(1)：72-76.

[9]VINOTHINI M，GANDHIMATHI K.Comparison of L-PEDAP routing protocol with random way point mobility model in mobile sensor networks[C].IEEE-International Conference On Advances In Engineering，Science And Management，ICAESM(1)，2012：735-740.

A distributed routing scheme in wireless Mesh networks

Zhong Lang，Li Guangjun，Yang Xuemin，Yang Yunle
(School of Communications and Information Engineering，University of Electronic Science and Technology of China，Chengdu 611731，China)

The performance of Multi-Radio Multi-Channel(MRMC)wireless Mesh networks fluctuates with the change of link load and locations of nodes.For such problems，a routing based on hybrid channel assignment(RHCA)which improved from Hybrid Wireless Mesh Routing Protocol(HWMP)is proposed.This scheme could both achieves route setup and the optimal channel allocation.The simulation results demonstrate that compared to conventional separated schemes，the proposed RHCA has significant advantages on throughput and average transmission delay.In addition，in the nodes motion scenario，RHCA also has much better robustness.

wireless Mesh networks；distributed routing algorithm；channel assignment

TN925.02

A

10.16157/j.issn.0258-7998.2015.07.023

鐘朗，李廣軍，楊學敏，等.無線 Mesh網絡中一種分布式路由方案[J].電子技術應用，2015，41 (7)：81-84.

英文引用格式：Zhong Lang，Li Guangjun，Yang Xuemin，et al.A distributed routing scheme in wireless Mesh networks[J].Application of Electronic Technique，2015，41(7)：81-84.

2015-02-16）

鐘朗（1981-），男，博士研究生，主要研究方向：無線通信網絡、無線資源分配。

李廣軍（1950-），男，教授，主要研究方向：通信信號處理、無線個人通信。

楊學敏（1986-），男，博士研究生，主要研究方向：陣列信號處理、無線通信。

國家自然科學基金（61301155；61176025）