摘 要: 無線Mesh網(wǎng)絡是一種特殊的Ad Hoc網(wǎng)絡。它易于部署,、安裝,，能有效地構建無線骨干網(wǎng)，通常被用作寬帶Internet接入和擴展無線LAN的覆蓋范圍,。針對無線Mesh網(wǎng)絡的特點,，提出了一種不同于一般MANET路由協(xié)議的路由算法。該算法基于網(wǎng)絡拓撲生成樹,，使用多個無重疊信道,；在解決信道分配問題的同時，兼顧信道多樣性和信道重用,，更好地利用無線頻譜資源,，支持鏈路并行傳輸。
關鍵詞: 無線Mesh網(wǎng)絡; 多信道; 生成樹
無線Mesh網(wǎng)絡是一種新型的多跳網(wǎng)絡技術,。它與MANET大致相同,，由一系列可以提供轉(zhuǎn)發(fā)、互相通信的無線節(jié)點組成,，每個節(jié)點既是主機又是路由器,。無線Mesh網(wǎng)絡具有網(wǎng)狀拓撲，其網(wǎng)絡架構一般由3層組成：最高層是一個或幾個Gateway節(jié)點,，WMNs通過它們與Internet進行有線連接,；中間層由許多Mesh路由器組成,，它們是網(wǎng)狀拓撲的頂點，在WMNs中進行接力轉(zhuǎn)發(fā),；底層由一些終端用戶組成,，包括移動客戶端和靜止客戶端。通常Mesh路由器是靜止的,，底層終端用戶無線登錄Mesh路由器,，通過Mesh網(wǎng)絡構建局域網(wǎng)并訪問Internet。
IEEE PHY規(guī)格說明,，允許在2.4 GHz的頻帶上使用3個無重疊信道,，在5 GHz頻帶上使用12個無重疊信道。為了提高WMN的容量,，在WMNs中使用多個無重疊信道,，為每個Mesh路由器配置一個或多個無線接口，制定信道分配機制,，挑選合適的路由方案,，并把兩者結合起來，得出可行的路由算法,。
1 相關工作
隨著WMNs的廣泛應用,，人們不再滿足于使用一般的MANET路由協(xié)議。MANET路由協(xié)議主要關注節(jié)點的能量耗費和移動特征,。而由幾乎靜止的Mesh路由器所構成的無線骨干網(wǎng)絡,，無能量限制，旨在提供更高的網(wǎng)絡吞吐量和更低的端到端延遲,，以期支持VoIP,、實時視頻監(jiān)視，寬帶網(wǎng)絡互聯(lián)通信等大流量服務[1],。目前已有的專為無線Mesh網(wǎng)絡設計的路由協(xié)議有：
(1)參考文獻[2]提出的多個版本的Mesh路由協(xié)議,。認為大部分流量來自并流向Internet，WMNs中的節(jié)點僅需知道怎樣到達Gateway,；少量的終端用戶間流量可通過其父節(jié)點路由,。本質(zhì)上，形成了以Gateway節(jié)點為根的樹,。
(2)參考文獻[1]提出了一種基于狀態(tài)的多接口多信道多路徑的自適應路由協(xié)議,。協(xié)議為節(jié)點配置多個無線接口，固定選取接受信道,，動態(tài)切換發(fā)送信道，以期多鏈路同步傳輸流量,。
(3)多信道技術作為提高網(wǎng)絡容量最有效的手段,，信道分配（CA）是其重點和難點,。多接口多信道無線Mesh網(wǎng)絡中的信道分配可以分為集中式分配和分布式分配兩大類[4]。集中式分配預先知道Mesh網(wǎng)絡的完整信息,，在一個節(jié)點上闡明并解決信道分配問題,，計算結果再分發(fā)給其他節(jié)點。分布式分配中節(jié)點獨立運行CA算法,，計算出本身所用信道,。根據(jù)流量模式又可分為兩種，Gateway導向的CA方法認為網(wǎng)絡中的主要流量流經(jīng)Gateway節(jié)點,，CA使用啟發(fā)式方法使近Gateway鏈路分配較高的帶寬,。對等導向的CA方法則認為網(wǎng)絡中流量沒有固定模式，來自任一對節(jié)點之間,，所以要盡可能地適應不同類型的網(wǎng)絡流量[3],。
本文在參考文獻[2]的基礎上，研究在路由過程中使用多信道,，為此提出了一種考慮接口數(shù)目的生成樹方法,。為了減少信道切換的耗費，采用了靜態(tài)信道分配,，節(jié)點在傳送數(shù)據(jù)時,，不用考慮信道選擇問題，可直接從讀取路由信息,，快速轉(zhuǎn)發(fā)數(shù)據(jù),。
除了干擾模型之外，與干擾相關的限制因素還有：網(wǎng)絡可用信道數(shù)目,，節(jié)點的接口數(shù)目,，而節(jié)點部署決定了節(jié)點之間的距離，明顯影響節(jié)點間的干擾關系,。
2.3 信道多樣性
信道多樣性可為相鄰的鏈路分配不同信道,，使它們可以并行傳輸，不發(fā)生干擾,。好的信道區(qū)分可以避免兩種干擾：流內(nèi)干擾和流間干擾,，如圖1所示。
圖1（a）中,，分配信道后,，流A→C與流D→E不存在干擾，而流A→C中,，鏈路AB和BC之間存在干擾,。而圖1（b）中不存在流內(nèi)干擾，但流A→C和流D→E存在干擾，兩個數(shù)據(jù)流不能同時傳輸,。為了消除這兩種干擾,，需使相鄰的鏈路AB、BC,、DE,、EF分配互不相同的信道。
2.4 連通性
信道分配會影響網(wǎng)絡的連通性,。使用相同信道的節(jié)點越多,，網(wǎng)絡會更健壯，但也會導致更多的干擾,。信道分配首先要保證網(wǎng)絡的連通,，在此基礎上盡可能減少沖突。
在綜合考慮干擾模型,、可用信道數(shù)目,、每個節(jié)點接口數(shù)目、節(jié)點的部署等因素情況下,，對WMN進行靜態(tài)信道分配以得到一個連通網(wǎng)絡是一個NP問題,。
3 本文方法
而對于未分配信道的節(jié)點和新加入網(wǎng)絡中的節(jié)點以及因接口限制不在V′中的節(jié)點，此時,，可考慮其鄰居節(jié)點,，如鄰居節(jié)點有剩余接口，調(diào)用上述分配方法,；如所有鄰居節(jié)點均無剩余接口,，則為其分配信道相關節(jié)點集最小的信道，并把游離節(jié)點加入樹結構V′,。
4 可行性與優(yōu)點
無線Mesh網(wǎng)絡中的Mesh路由器節(jié)點很少移動,，其構成的骨干網(wǎng)絡除了使用無線通信方式外，還具有有線網(wǎng)絡穩(wěn)定的優(yōu)點,，在WMN中使用先應式路由協(xié)議就可免去考慮頻繁更新路由表的問題,；同樣認為無線Mesh網(wǎng)絡中大部分流量來自并流向Internet，節(jié)點僅需知道如何到達Gateway,；少量的終端用戶間流量可通過其父節(jié)點路由,。對于一個連通的網(wǎng)絡拓撲圖G′(V，E)來說,，必然存在一棵生成樹T,。在對鏈路分配信道時，生成樹T只有n-1邊,，與G′(V,，E)相比,，整個網(wǎng)絡中的鏈路沖突將大大減少，如圖2所示,。
在只有5個可用信道時,，圖2（a）中的AC與FD,、AF與CD,、BC與EF之間存在流間干擾，而圖2（b）中則不存在干擾,。但這只是一種理想狀況,，因為節(jié)點還要受到接口數(shù)目的限制。如果節(jié)點C只有2個接口,，最多能為其分配2個無重疊信道,，而不是圖2（a）中所示的4個無重疊信道。
本文針對無線Mesh網(wǎng)絡的特點,，提出了一種樹形路由算法,，該路由算法利用對原網(wǎng)絡拓撲進行剪枝處理，得到了一棵保證網(wǎng)絡連通的生成樹,，節(jié)點利用生成樹結構構建路由表,，通過父節(jié)點與其他節(jié)點進行通信。在信道分配階段,，全面考慮整個網(wǎng)絡,，只對生成樹的邊進行信道分配，減少了非生成樹邊對網(wǎng)絡的干擾,；對鏈路分配信道時,，考慮了該鏈路的整個干擾區(qū)域，而不是只考慮流經(jīng)該鏈路的線性路徑,，盡可能地排除流內(nèi)干擾和流間干擾,。對信道相關節(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.