孫 暖,周繼鵬

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

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

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

1 相關工作

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

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

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

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

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

2 問題描述

2.1 網絡模型

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

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

2.2 干擾模型

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

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

2.3 信道多樣性

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

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

2.4 連通性

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

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

3 本文方法

3.1 生成樹方法

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

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

節(jié)點v選取子節(jié)點：

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

3.2 信道分配

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

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

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

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

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

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

4 可行性與優(yōu)點

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

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

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

[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.