無線Mesh網絡中多信道生成樹路由算法*

孫 暖,周繼鵬

（暨南大學 信息科學技術學院計算機系，廣東 廣州510632）

無線Mesh網絡是一種新型的多跳網絡技術。它與MANET大致相同，由一系列可以提供轉發、互相通信的無線節點組成，每個節點既是主機又是路由器。無線Mesh網絡具有網狀拓撲，其網絡架構一般由3層組成：最高層是一個或幾個Gateway節點，WMNs通過它們與Internet進行有線連接；中間層由許多Mesh路由器組成，它們是網狀拓撲的頂點，在WMNs中進行接力轉發；底層由一些終端用戶組成，包括移動客戶端和靜止客戶端。通常Mesh路由器是靜止的，底層終端用戶無線登錄Mesh路由器，通過Mesh網絡構建局域網并訪問Internet。

IEEE PHY規格說明，允許在2.4 GHz的頻帶上使用3個無重疊信道，在5 GHz頻帶上使用12個無重疊信道。為了提高WMN的容量，在WMNs中使用多個無重疊信道，為每個Mesh路由器配置一個或多個無線接口，制定信道分配機制，挑選合適的路由方案，并把兩者結合起來，得出可行的路由算法。

1 相關工作

隨著WMNs的廣泛應用，人們不再滿足于使用一般的MANET路由協議。MANET路由協議主要關注節點的能量耗費和移動特征。而由幾乎靜止的Mesh路由器所構成的無線骨干網絡，無能量限制，旨在提供更高的網絡吞吐量和更低的端到端延遲，以期支持VoIP、實時視頻監視，寬帶網絡互聯通信等大流量服務[1]。目前已有的專為無線Mesh網絡設計的路由協議有：

(1)參考文獻[2]提出的多個版本的 Mesh路由協議。認為大部分流量來自并流向Internet，WMNs中的節點僅需知道怎樣到達Gateway；少量的終端用戶間流量可通過其父節點路由。本質上，形成了以Gateway節點為根的樹。

(2)參考文獻[1]提出了一種基于狀態的多接口多信道多路徑的自適應路由協議。協議為節點配置多個無線接口，固定選取接受信道，動態切換發送信道，以期多鏈路同步傳輸流量。

(3)多信道技術作為提高網絡容量最有效的手段，信道分配（CA）是其重點和難點。多接口多信道無線Mesh網絡中的信道分配可以分為集中式分配和分布式分配兩大類[4]。集中式分配預先知道Mesh網絡的完整信息，在一個節點上闡明并解決信道分配問題，計算結果再分發給其他節點。分布式分配中節點獨立運行CA算法，計算出本身所用信道。根據流量模式又可分為兩種，Gateway導向的CA方法認為網絡中的主要流量流經Gateway節點，CA使用啟發式方法使近Gateway鏈路分配較高的帶寬。對等導向的CA方法則認為網絡中流量沒有固定模式，來自任一對節點之間，所以要盡可能地適應不同類型的網絡流量[3]。

本文在參考文獻[2]的基礎上，研究在路由過程中使用多信道，為此提出了一種考慮接口數目的生成樹方法。為了減少信道切換的耗費，采用了靜態信道分配，節點在傳送數據時，不用考慮信道選擇問題，可直接從讀取路由信息，快速轉發數據。

2 問題描述

2.1 網絡模型

無線Mesh網絡通常用作骨干網絡，這里所說的網絡指的是由Mesh路由器及其之間的無線鏈路所形成的網絡。為了在Mesh網絡中使用多信道，假定網絡中的節點靜止，每個節點配置一個或多個無線接口卡，網絡中有多個無重疊信道可供使用。

網 絡 G(V，E)，V={v1，v2，v3，… ，vn}；?v1，v2∈V，若(v1，v2)∈E，則 v1的接口和 v2的接口分配有相同的信道，并且它們在該信道的電波傳輸范圍之內；I(vi)表示節點vi的無線接口數目，網絡所有可用信道集是 F={f1，f2，f3，…，fk}，RT(i)表示信道 fi上電波的傳輸半徑，RI(i)表示信道fi上電波的干擾半徑。

2.2 干擾模型

干擾是降低無線網絡性能的首要因素，信道分配就是利用多接口多信道最小化WMN中的干擾。目前，有協議和物理兩種干擾模型用來描述干擾問題。物理干擾模型較協議模型頗為復雜。本文采用一種協議干擾模型，它規定節點vi在信道fm上向節點vj成功傳輸數據流，要求：(1)節點 vi、vj上均有接口分配信道 fm；(2)||vjvi||≤RT(m)，節點 vj到節點 vi的距離在信道 fm的電波傳輸范圍之內；(3)任意其他節點 vk若要使用信道 fm，則||vk-vi||>RI(m)且||vk-vj||>RI(m)。

除了干擾模型之外，與干擾相關的限制因素還有：網絡可用信道數目，節點的接口數目，而節點部署決定了節點之間的距離，明顯影響節點間的干擾關系。

2.3 信道多樣性

信道多樣性可為相鄰的鏈路分配不同信道，使它們可以并行傳輸，不發生干擾。好的信道區分可以避免兩種干擾：流內干擾和流間干擾，如圖1所示。

圖1（a）中，分配信道后，流 A→C與流 D→E不存在干擾，而流A→C中，鏈路AB和BC之間存在干擾。而圖 1（b）中不存在流內干擾，但流 A→C和流 D→E存在干擾，兩個數據流不能同時傳輸。為了消除這兩種干擾，需使相鄰的鏈路AB、BC、DE、EF分配互不相同的信道。

2.4 連通性

信道分配會影響網絡的連通性。使用相同信道的節點越多，網絡會更健壯，但也會導致更多的干擾。信道分配首先要保證網絡的連通，在此基礎上盡可能減少沖突。

在綜合考慮干擾模型、可用信道數目、每個節點接口數目、節點的部署等因素情況下，對WMN進行靜態信道分配以得到一個連通網絡是一個NP問題。

3 本文方法

3.1 生成樹方法

考慮到要在生成樹中合理分配信道，在構建生成樹時，要同時考慮節點的鄰居節點集和該節點的接口數目，使節點的最大度受限于鄰居節點個數和接口數目。

從Gateway節點開始進行選取子節點操作，使V′={vg}，遞歸遍歷生成樹結構V′，并調用選取子節點方法。

節點v選取子節點：

節點v從未選入V′的鄰居節點中選擇，選擇子節點的數目不大于v已剩接口數目；為了使得到的生成樹深度盡可能小（即節點到Gateway節點的跳數較少），每次都要選擇可能有最多子節點的鄰居節點。可能有最多子節點意味著 min(|Hvi-V′|，Ivi)最大。

3.2 信道分配

為生成樹的邊分配信道，需注意：（1）因近根鏈路負載較重，所以盡可能保證近根鏈路的信道差異性，使這些鏈路減少沖突，并行傳輸數據。有助于提高整個網絡吞吐量。（2）信道重用原則：在沒有信號沖突的情況下，盡量使用較少信道，以留給后來節點更多可選擇信道。（3）鑒于可用信道有限的現實，網絡中各鏈路不可能均無干擾。以鏈路干擾為代價，優先保證網絡連通性。

網絡所有可用信道集為 F={f1，f2，f3， …，fk}。 信道分配方法如下：

廣度遍歷生成樹結構V′，由根開始為每對父子節點間鏈路調用信道分配算法。為鏈路vf→vc分配信道算法如下：

起始條件：為每個信道創建集合 ch1、ch2，…，chk，其中chk指使用信道fk的節點集合。并且初始為空集。

將鄰居節點集 Hf∪Hc按順序與 ch2，…，chk做交運算，若為空，為 vf→vc，將 vf、vc加入相應的信道相關節點集，ch2，…，chk按照集的勢呈降序排序 （實現信道重用）。若均不為空，暫不分配。

而對于未分配信道的節點和新加入網絡中的節點以及因接口限制不在V′中的節點，此時，可考慮其鄰居節點，如鄰居節點有剩余接口，調用上述分配方法；如所有鄰居節點均無剩余接口，則為其分配信道相關節點集最小的信道，并把游離節點加入樹結構V′。

4 可行性與優點

無線Mesh網絡中的Mesh路由器節點很少移動，其構成的骨干網絡除了使用無線通信方式外，還具有有線網絡穩定的優點，在WMN中使用先應式路由協議就可免去考慮頻繁更新路由表的問題；同樣認為無線Mesh網絡中大部分流量來自并流向Internet，節點僅需知道如何到達Gateway；少量的終端用戶間流量可通過其父節點路由。對于一個連通的網絡拓撲圖G′(V，E)來說，必然存在一棵生成樹T。在對鏈路分配信道時，生成樹T只有 n-1邊，與 G′(V，E)相比，整個網絡中的鏈路沖突將大大減少，如圖2所示。

在只有 5個可用信道時，圖 2（a）中的 AC與 FD、AF與 CD、BC與 EF之間存在流間干擾，而圖 2（b）中則不存在干擾。但這只是一種理想狀況，因為節點還要受到接口數目的限制。如果節點C只有2個接口，最多能為其分配 2個無重疊信道，而不是圖 2（a）中所示的 4個無重疊信道。

本文針對無線Mesh網絡的特點，提出了一種樹形路由算法，該路由算法利用對原網絡拓撲進行剪枝處理，得到了一棵保證網絡連通的生成樹，節點利用生成樹結構構建路由表，通過父節點與其他節點進行通信。在信道分配階段，全面考慮整個網絡，只對生成樹的邊進行信道分配，減少了非生成樹邊對網絡的干擾；對鏈路分配信道時，考慮了該鏈路的整個干擾區域，而不是只考慮流經該鏈路的線性路徑，盡可能地排除流內干擾和流間干擾。對信道相關節點集進行排序，有利于信道重用。

[1]DEEPTI S N,NAGESH S N.DHARMA P A.Adaptive statebased multi-radio multi-channel multi-path routing in Wireless Mesh Networks[J].Pervasive and Mobile Computing,2009，5(1):93-109.

[2]JANGEUN J,MIHAIL L S.MRP:wireless mesh networks routing protocol[J].Computer Communications,2008，31(7):1413-1435.

[3]MAO Xu Fei，LI Xiang Yang，MAKKI S K.Static channel assignment for multi-radio multi-channel multi-hop wireless networks.[2006-06-16].http://www.asee-ncsection.org/papers/122.pdf.

[4]SI Wei Sheng,SELVAKENNEDY S,ZOMAYA A Y.An overview of channel assignment methods for multi-radio multi-channel wireless mesh networks[J].Journal of Parallel Distributed Computing,2010，70(5)：505-524.