文獻標識碼： A
DOI：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.
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個節點，相鄰節點間距170 m。且本文的信道分配過程只考慮如何減小鏈路干擾，達到以數據流為單位的鏈路干擾最小化信道分配。其余諸如網絡負載等因素的影響則在路由選擇時考慮。干擾模型方面采用文獻[8]中的協議干擾模型，如圖2所示，當鏈路ei、ej節點間跳數不少于兩跳時，才認為二者無相互干擾。雖然該模型是一個NP問題，但其信道分配模型融合于路由算法中，具體分配方式將在后文中詳述。
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個隨機種子進行仿真所得平均值，基本符合網絡數據統計特性。
3.1 不同網絡負載下性能分析
本次仿真采用網絡拓撲如圖1所示，并設12號節點為根節點。
仿真隨機選取5對節點建立固定碼率(Constant Bit Rate，CBR)數據傳輸業務，CBR流速率為600 kb/s到2 Mb/s不等，每組節點在仿真時間內隨機選擇時間發起業務，并持續50 s，如果從發起業務到仿真結束不足50 s，則以仿真結束時間為準。全網可用正交信道數為6，仿真結果如圖3所示。
從圖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]，各節點速率是在0 m/s～2 m/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所示。
從圖中可以看出，在仿真前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.