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