摘  要: 無線Mesh網(wǎng)絡(luò)是一種特殊的Ad Hoc網(wǎng)絡(luò)。它易于部署、安裝，能有效地構(gòu)建無線骨干網(wǎng)，通常被用作寬帶Internet接入和擴(kuò)展無線LAN的覆蓋范圍。針對(duì)無線Mesh網(wǎng)絡(luò)的特點(diǎn)，提出了一種不同于一般MANET路由協(xié)議的路由算法。該算法基于網(wǎng)絡(luò)拓?fù)?a class="innerlink" href="http://ihrv.cn/tags/生成樹" title="生成樹" target="_blank">生成樹，使用多個(gè)無重疊信道；在解決信道分配問題的同時(shí)，兼顧信道多樣性和信道重用，更好地利用無線頻譜資源，支持鏈路并行傳輸。
關(guān)鍵詞: 無線Mesh網(wǎng)絡(luò); 多信道; 生成樹

    無線Mesh網(wǎng)絡(luò)是一種新型的多跳網(wǎng)絡(luò)技術(shù)。它與MANET大致相同，由一系列可以提供轉(zhuǎn)發(fā)、互相通信的無線節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)既是主機(jī)又是路由器。無線Mesh網(wǎng)絡(luò)具有網(wǎng)狀拓?fù)?，其網(wǎng)絡(luò)架構(gòu)一般由3層組成：最高層是一個(gè)或幾個(gè)Gateway節(jié)點(diǎn)，WMNs通過它們與Internet進(jìn)行有線連接；中間層由許多Mesh路由器組成，它們是網(wǎng)狀拓?fù)涞捻旤c(diǎn)，在WMNs中進(jìn)行接力轉(zhuǎn)發(fā)；底層由一些終端用戶組成，包括移動(dòng)客戶端和靜止客戶端。通常Mesh路由器是靜止的，底層終端用戶無線登錄Mesh路由器，通過Mesh網(wǎng)絡(luò)構(gòu)建局域網(wǎng)并訪問Internet。
    IEEE PHY規(guī)格說明，允許在2.4 GHz的頻帶上使用3個(gè)無重疊信道，在5 GHz頻帶上使用12個(gè)無重疊信道。為了提高WMN的容量，在WMNs中使用多個(gè)無重疊信道，為每個(gè)Mesh路由器配置一個(gè)或多個(gè)無線接口，制定信道分配機(jī)制，挑選合適的路由方案，并把兩者結(jié)合起來，得出可行的路由算法。
1 相關(guān)工作
    隨著WMNs的廣泛應(yīng)用，人們不再滿足于使用一般的MANET路由協(xié)議。MANET路由協(xié)議主要關(guān)注節(jié)點(diǎn)的能量耗費(fèi)和移動(dòng)特征。而由幾乎靜止的Mesh路由器所構(gòu)成的無線骨干網(wǎng)絡(luò)，無能量限制，旨在提供更高的網(wǎng)絡(luò)吞吐量和更低的端到端延遲，以期支持VoIP、實(shí)時(shí)視頻監(jiān)視，寬帶網(wǎng)絡(luò)互聯(lián)通信等大流量服務(wù)[1]。目前已有的專為無線Mesh網(wǎng)絡(luò)設(shè)計(jì)的路由協(xié)議有：
    (1)參考文獻(xiàn)[2]提出的多個(gè)版本的Mesh路由協(xié)議。認(rèn)為大部分流量來自并流向Internet，WMNs中的節(jié)點(diǎn)僅需知道怎樣到達(dá)Gateway；少量的終端用戶間流量可通過其父節(jié)點(diǎn)路由。本質(zhì)上，形成了以Gateway節(jié)點(diǎn)為根的樹。
    (2)參考文獻(xiàn)[1]提出了一種基于狀態(tài)的多接口多信道多路徑的自適應(yīng)路由協(xié)議。協(xié)議為節(jié)點(diǎn)配置多個(gè)無線接口，固定選取接受信道，動(dòng)態(tài)切換發(fā)送信道，以期多鏈路同步傳輸流量。
    (3)多信道技術(shù)作為提高網(wǎng)絡(luò)容量最有效的手段，信道分配（CA）是其重點(diǎn)和難點(diǎn)。多接口多信道無線Mesh網(wǎng)絡(luò)中的信道分配可以分為集中式分配和分布式分配兩大類[4]。集中式分配預(yù)先知道Mesh網(wǎng)絡(luò)的完整信息，在一個(gè)節(jié)點(diǎn)上闡明并解決信道分配問題，計(jì)算結(jié)果再分發(fā)給其他節(jié)點(diǎn)。分布式分配中節(jié)點(diǎn)獨(dú)立運(yùn)行CA算法，計(jì)算出本身所用信道。根據(jù)流量模式又可分為兩種，Gateway導(dǎo)向的CA方法認(rèn)為網(wǎng)絡(luò)中的主要流量流經(jīng)Gateway節(jié)點(diǎn)，CA使用啟發(fā)式方法使近Gateway鏈路分配較高的帶寬。對(duì)等導(dǎo)向的CA方法則認(rèn)為網(wǎng)絡(luò)中流量沒有固定模式，來自任一對(duì)節(jié)點(diǎn)之間，所以要盡可能地適應(yīng)不同類型的網(wǎng)絡(luò)流量[3]。
    本文在參考文獻(xiàn)[2]的基礎(chǔ)上，研究在路由過程中使用多信道，為此提出了一種考慮接口數(shù)目的生成樹方法。為了減少信道切換的耗費(fèi)，采用了靜態(tài)信道分配，節(jié)點(diǎn)在傳送數(shù)據(jù)時(shí)，不用考慮信道選擇問題，可直接從讀取路由信息，快速轉(zhuǎn)發(fā)數(shù)據(jù)。

    除了干擾模型之外，與干擾相關(guān)的限制因素還有：網(wǎng)絡(luò)可用信道數(shù)目，節(jié)點(diǎn)的接口數(shù)目，而節(jié)點(diǎn)部署決定了節(jié)點(diǎn)之間的距離，明顯影響節(jié)點(diǎn)間的干擾關(guān)系。
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存在干擾，兩個(gè)數(shù)據(jù)流不能同時(shí)傳輸。為了消除這兩種干擾，需使相鄰的鏈路AB、BC、DE、EF分配互不相同的信道。
2.4 連通性
    信道分配會(huì)影響網(wǎng)絡(luò)的連通性。使用相同信道的節(jié)點(diǎn)越多，網(wǎng)絡(luò)會(huì)更健壯，但也會(huì)導(dǎo)致更多的干擾。信道分配首先要保證網(wǎng)絡(luò)的連通，在此基礎(chǔ)上盡可能減少?zèng)_突。
    在綜合考慮干擾模型、可用信道數(shù)目、每個(gè)節(jié)點(diǎn)接口數(shù)目、節(jié)點(diǎn)的部署等因素情況下，對(duì)WMN進(jìn)行靜態(tài)信道分配以得到一個(gè)連通網(wǎng)絡(luò)是一個(gè)NP問題。
3 本文方法

    而對(duì)于未分配信道的節(jié)點(diǎn)和新加入網(wǎng)絡(luò)中的節(jié)點(diǎn)以及因接口限制不在V′中的節(jié)點(diǎn)，此時(shí)，可考慮其鄰居節(jié)點(diǎn)，如鄰居節(jié)點(diǎn)有剩余接口，調(diào)用上述分配方法；如所有鄰居節(jié)點(diǎn)均無剩余接口，則為其分配信道相關(guān)節(jié)點(diǎn)集最小的信道，并把游離節(jié)點(diǎn)加入樹結(jié)構(gòu)V′。
4 可行性與優(yōu)點(diǎn)
    無線Mesh網(wǎng)絡(luò)中的Mesh路由器節(jié)點(diǎn)很少移動(dòng)，其構(gòu)成的骨干網(wǎng)絡(luò)除了使用無線通信方式外，還具有有線網(wǎng)絡(luò)穩(wěn)定的優(yōu)點(diǎn)，在WMN中使用先應(yīng)式路由協(xié)議就可免去考慮頻繁更新路由表的問題；同樣認(rèn)為無線Mesh網(wǎng)絡(luò)中大部分流量來自并流向Internet，節(jié)點(diǎn)僅需知道如何到達(dá)Gateway；少量的終端用戶間流量可通過其父節(jié)點(diǎn)路由。對(duì)于一個(gè)連通的網(wǎng)絡(luò)拓?fù)鋱DG′(V，E)來說，必然存在一棵生成樹T。在對(duì)鏈路分配信道時(shí)，生成樹T只有n-1邊，與G′(V，E)相比，整個(gè)網(wǎng)絡(luò)中的鏈路沖突將大大減少，如圖2所示。

    在只有5個(gè)可用信道時(shí)，圖2（a）中的AC與FD、AF與CD、BC與EF之間存在流間干擾，而圖2（b）中則不存在干擾。但這只是一種理想狀況，因?yàn)楣?jié)點(diǎn)還要受到接口數(shù)目的限制。如果節(jié)點(diǎn)C只有2個(gè)接口，最多能為其分配2個(gè)無重疊信道，而不是圖2（a）中所示的4個(gè)無重疊信道。
    本文針對(duì)無線Mesh網(wǎng)絡(luò)的特點(diǎn)，提出了一種樹形路由算法，該路由算法利用對(duì)原網(wǎng)絡(luò)拓?fù)溥M(jìn)行剪枝處理，得到了一棵保證網(wǎng)絡(luò)連通的生成樹，節(jié)點(diǎn)利用生成樹結(jié)構(gòu)構(gòu)建路由表，通過父節(jié)點(diǎn)與其他節(jié)點(diǎn)進(jìn)行通信。在信道分配階段，全面考慮整個(gè)網(wǎng)絡(luò)，只對(duì)生成樹的邊進(jìn)行信道分配，減少了非生成樹邊對(duì)網(wǎng)絡(luò)的干擾；對(duì)鏈路分配信道時(shí)，考慮了該鏈路的整個(gè)干擾區(qū)域，而不是只考慮流經(jīng)該鏈路的線性路徑，盡可能地排除流內(nèi)干擾和流間干擾。對(duì)信道相關(guān)節(jié)點(diǎn)集進(jìn)行排序，有利于信道重用。
參考文獻(xiàn)
[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.