何淵淘 李清秀

摘 要：無線網(wǎng)狀網(wǎng)（Wireless Mesh Network，WMN）是一種多跳的自組織網(wǎng)絡(luò)， WMN路由協(xié)議對網(wǎng)絡(luò)的性能指標(biāo)起到了決定作用。近年來一些WMN路由協(xié)議被提出和實現(xiàn)，例如OLSR，Babel，BMX6。在本文中，作者分析了幾種路由協(xié)議的工作機(jī)制和選路原理，并在真實的環(huán)境下構(gòu)建了測試平臺。實驗的結(jié)果表明BMX6協(xié)議在收斂速度和網(wǎng)絡(luò)開銷上要優(yōu)于Babel和OLSR（Optimized Link State Routing）。

關(guān)鍵詞：無線網(wǎng)狀網(wǎng)；BMX6；OLSR；Babel

1 引言

由于部署的時間和成本的因素，在臨時場所或災(zāi)難地區(qū)進(jìn)行組網(wǎng)存在著較大的困難，WMN就是針對該問題而提出的解決方案[1]。近年來以gufi.net和AWMN為代表的社區(qū)無線網(wǎng)絡(luò)的設(shè)計和部署進(jìn)一步推動其發(fā)展[2-3]，大量私有和開源的WMN路由協(xié)議被提出和實現(xiàn)。其中具有代表性的是OLSR、Babel、BMX6、B.A.T.M.A.N-ADV[4-6]。由于WMN路由協(xié)議會對其性能產(chǎn)生決定性作用，因此掌握其性能特征對WMN網(wǎng)絡(luò)的開發(fā)和對協(xié)議的改進(jìn)具有重要的意義。

本文首先對這幾種網(wǎng)絡(luò)協(xié)議的工作機(jī)制和選路原理進(jìn)行分析和對比，然后在校園網(wǎng)環(huán)境下構(gòu)建了小型WMN測試平臺。最后在此平臺的基礎(chǔ)上，測試這幾種路由協(xié)議的網(wǎng)絡(luò)開銷、收斂速度等指標(biāo)，并對實驗數(shù)據(jù)進(jìn)行分析。

2 WMN路由協(xié)議

WMN是一種典型的Ad-Hoc網(wǎng)絡(luò)，當(dāng)前根據(jù)WMN產(chǎn)生路由表的方式可以將協(xié)議分為主動式、被動式和混合式。主動路由協(xié)議在節(jié)點的鏈路上定期或者觸發(fā)式的傳遞鏈路狀態(tài)信息或路由表，以實現(xiàn)全網(wǎng)可達(dá)。主動式路由協(xié)議適合在設(shè)備供電較為穩(wěn)定的場景，該場景通常有較高的鏈路帶寬，從而降低路由協(xié)議在整體網(wǎng)絡(luò)中的開銷。被動式路由協(xié)議適合設(shè)備供電緊張，節(jié)點移動性高，鏈路帶寬較低的場景。這類路由協(xié)議事先不生成任何路由表，僅在有效數(shù)據(jù)發(fā)送時才進(jìn)行路由信息的計算?；旌闲吐酚蓞f(xié)議則兼具上述兩類路由協(xié)議的特征，本文中所對比的路由協(xié)議屬于主動式路由協(xié)議。

2.1 OLSR路由協(xié)議

OLSR即Optimized Link Status Routing Protocols[5]，是一種典型的鏈路狀態(tài)路由協(xié)議。鏈路狀態(tài)協(xié)議在節(jié)點的鏈路上進(jìn)行鏈路信息的宣告和傳遞，在每個節(jié)點內(nèi)保存整個網(wǎng)絡(luò)拓?fù)洳⒁源藖碛嬎懵酚?。由于無線電資源本身容易受到干擾且802.11中媒體接入控制層的競爭機(jī)制，WMN會因為大量的鏈路狀態(tài)更新而造成較高的開銷。OLSR引入了Multi-Point Relays（MPR）的方案來避免這一問題，MPR是網(wǎng)絡(luò)節(jié)點的一個子集，由參與OLSR協(xié)議的節(jié)點選出。網(wǎng)絡(luò)的拓?fù)鋬H存儲在MRP節(jié)點上，并由MRP節(jié)點來完成洪泛。這種機(jī)制極大減少了鏈路狀態(tài)更新的次數(shù)，也極大提升了端到端的吞吐量。

由于鏈路狀態(tài)協(xié)議在節(jié)點間信息不一致的情況下會產(chǎn)生路由環(huán)路，而WMN節(jié)點的移動性則會加劇節(jié)點間信息不一致的狀況。為了避免這一現(xiàn)象，OLSR增加了魚眼機(jī)制（Fish eye）的支持，即降低對較遠(yuǎn)節(jié)點的鏈路狀態(tài)更新頻率來避免環(huán)路。由于OLSR提出較早而具有較多的實現(xiàn)，本文使用OLSRD來進(jìn)行實驗和性能對比。

2.2 Babel路由協(xié)議

Babel屬于距離向量路由協(xié)議[6]，該協(xié)議不僅支持在無線網(wǎng)絡(luò)也支持有線網(wǎng)絡(luò)。與RIP為代表的有線網(wǎng)絡(luò)協(xié)議相比，Babel不再使用跳數(shù)來進(jìn)行最優(yōu)路徑的選擇，而是使用“期望傳輸跳數(shù)”Expected Transmission Count（ETC）來計算到達(dá)某一節(jié)點的跳數(shù)。ETC不僅考慮了到達(dá)某一節(jié)點的跳數(shù)信息，還綜合考慮了鏈路帶寬、擁塞度等一系列指標(biāo)來作為選路的依據(jù)。然而ETC會由于無線環(huán)境的變化和網(wǎng)絡(luò)節(jié)點的加入/退出不斷變化，這也就造成路由的不斷翻轉(zhuǎn)使得網(wǎng)絡(luò)難以收斂。因此Babel使用歷史感知機(jī)制（History-sensitive）來加速網(wǎng)絡(luò)的收斂，即具有相近ETC值的情況下選擇曾經(jīng)使用過的路徑。與OLSR不同，Babel在網(wǎng)絡(luò)收斂后不會在整個網(wǎng)絡(luò)范圍內(nèi)進(jìn)行周期性的路由更新和宣告，只有當(dāng)節(jié)點信息和狀態(tài)發(fā)生變化時才會被動觸發(fā)更新。

面向Babel協(xié)議的實現(xiàn)主要有Babled和Quagga。Babled是針對Babel的獨立實現(xiàn)，Babeld支持將物理層信息作為選路的依據(jù)，從而降低不同頻率間的干擾。而Quagga則集成了各種路由協(xié)議，除了支持Babel還支持OSPF和BGP等協(xié)議，本文選擇Quagga來做性能對比。

2.3 BMX6路由協(xié)議

BMX6即B.A.T.M.A.N-Experimental version 6是B.A.T.M.A.N路由協(xié)議的一個分支。BMX6是一個主動式路由協(xié)議，也是一個距離向量路由協(xié)議。該協(xié)議使用內(nèi)部描述符表、哈希表、全局描述符表來降低路由協(xié)議所帶來的開銷。內(nèi)部描述符僅存儲鄰接點的信息，全局描述符存儲所有節(jié)點的信息，而哈希表將兩個描述符中的表項做映射。節(jié)點的全局描述符信息在節(jié)點啟動后僅進(jìn)行一次洪泛，而后使用其哈希值來代描述符，從而減少協(xié)議的網(wǎng)絡(luò)開銷。通過這種方式節(jié)點在移動后僅需要重建本地描述符表，減少了節(jié)點移動帶來的網(wǎng)絡(luò)開銷。除此之外BMX6的路由協(xié)議將社會關(guān)系信任模型應(yīng)用到節(jié)點之間的關(guān)系上，通過在節(jié)點間建立信任關(guān)系來作為選路的依據(jù)，從而保證了網(wǎng)絡(luò)的流量從可以信賴的節(jié)點進(jìn)行轉(zhuǎn)發(fā)，這種機(jī)制降低了由于惡意接入而帶來安全問題。由于BMX6的這種安全特征，在社區(qū)無線網(wǎng)絡(luò)中應(yīng)用較多[2]。

當(dāng)前針對BMX6的實現(xiàn)為bmx6d，本論文選擇其作為實驗平臺。

3 實驗設(shè)計和性能對比

本實驗在一棟五層高的大樓內(nèi)進(jìn)行，本次試驗共使用無線節(jié)點七十個，為了減少外界電磁波的干擾，實驗選擇了5.8GHz作為無線頻率。為了實驗和設(shè)備編址方便，對設(shè)備進(jìn)行編號。設(shè)備號碼為1到60，而設(shè)備的接口地址也依照編號進(jìn)行編制。本實驗的設(shè)備為tl-wr2543nd，安裝過OpenWRT和三種路由協(xié)議后開始配置接口。首先將每臺設(shè)備的無線網(wǎng)卡設(shè)置為ad-hoc模式，ssid統(tǒng)一設(shè)定為lab-mesh，然后設(shè)置設(shè)備的wlan0和eth0接口的網(wǎng)絡(luò)層地址。由于BMX6d和Quagga（babel）僅支持ipv6協(xié)議，在針對BMX和Babel的實驗中將其eth0的地址設(shè)定為2001：DA8：5015：3010：：X/64，其中X分別為設(shè)備對應(yīng)的編號，而wlan接口則使用ipv6的本地鏈接地址。針對OLSR的實驗，則使用ipv4進(jìn)行編址，eth0接口的地址為192.168.X.1/16，wlan0接口的地址為10.10.x.1/16，X為設(shè)備的編號。

在實驗中，首先測試了在所有節(jié)點啟動后所產(chǎn)生的網(wǎng)絡(luò)開銷，其結(jié)果見圖一。從圖中可以看出，OLSR協(xié)議在在160ms左右出現(xiàn)了一個流量高峰（58kbps/s），這是因為此時每個節(jié)點都在最大量的發(fā)送并接受鏈路狀態(tài)信息。在此之后網(wǎng)絡(luò)開始緩慢收斂，在收斂狀態(tài)下OLSR協(xié)議所帶來的網(wǎng)絡(luò)開銷穩(wěn)定在25kbps左右。而Babel導(dǎo)致每個節(jié)點啟動后會發(fā)現(xiàn)鄰居節(jié)點，會進(jìn)行路由信息宣告，在25ms左右進(jìn)入網(wǎng)絡(luò)流量的高峰，達(dá)到40kbps/s。由于實驗選用5GHz的頻段，該頻道受干擾較小，網(wǎng)絡(luò)收斂后沒有明顯的鄰居信息的變化，因此Babel協(xié)議不會額外發(fā)送鏈路信息，此時Babel只會周期性探測鄰居點的可達(dá)性量。由于這種開銷僅出現(xiàn)在局部，此時網(wǎng)絡(luò)的開銷僅有即15kbp/s左右。而BMX協(xié)議在整個啟動的過程中會傳遞節(jié)點描述信息，并在在48ms左右進(jìn)入穩(wěn)定狀態(tài)。由于BMX協(xié)議在收斂后僅僅會周期性傳遞節(jié)點信息的哈希值，協(xié)議所帶來的網(wǎng)絡(luò)開銷穩(wěn)定在20kbp/s左右。

在圖二的實驗中，作者每次啟動10個節(jié)點，并收集網(wǎng)絡(luò)的整體流量數(shù)據(jù)。從圖中可以看出，BMX6和Babel中網(wǎng)絡(luò)開銷隨時間增長較慢，而OLSR協(xié)議會隨著網(wǎng)絡(luò)中節(jié)點數(shù)目的增多而迅速增加。這主要是由于OLSR屬于鏈路狀態(tài)協(xié)議，其會在整個網(wǎng)絡(luò)中廣播鏈路狀態(tài)信息。而隨著網(wǎng)絡(luò)的增大，鏈路狀態(tài)信息的數(shù)量也在迅速增多，從而帶來更大的網(wǎng)絡(luò)開銷。而BMX6和Babel則屬于距離矢量路由協(xié)議，在這兩個協(xié)議中都采用了策略來減少網(wǎng)絡(luò)的協(xié)議開銷。

在圖三的實驗中為網(wǎng)絡(luò)收斂速度的實驗，該實驗分別測試了跳數(shù)對網(wǎng)絡(luò)收斂帶的影響。圖中顯示OLSR的收斂時間會隨著跳數(shù)的增加而迅速增加，這是由于OLSR的魚眼機(jī)制所造成的。魚眼機(jī)制通過減少對較遠(yuǎn)節(jié)點的鏈路狀態(tài)更新來避免環(huán)路，這也不可避免的導(dǎo)致較遠(yuǎn)的節(jié)點的收斂速度與跳數(shù)成正比。與OLSR不同，Babel和BMX6的收斂速度基本不受節(jié)點跳數(shù)的影響。起因在于Babel協(xié)議采用了被動更新機(jī)制，當(dāng)其偵測到鄰居的存在狀態(tài)變化時能迅速傳輸新的網(wǎng)絡(luò)拓?fù)湫畔?，這一機(jī)制加快了網(wǎng)絡(luò)的收斂速度。而BMX6協(xié)議只使用了相比于Babel更高的頻率去檢查鄰居點的存在狀態(tài)，并通過周期性的廣播來將網(wǎng)絡(luò)信息發(fā)送出去，這也導(dǎo)致了其具備最高的收斂速度。

4 結(jié)論

本文對WMN的幾個主動式路由協(xié)議，BMX6、Babel、OLSR的工作機(jī)機(jī)制進(jìn)行了深入的分析，并在真實的環(huán)境和測試平臺下對比了這幾個路由協(xié)議的網(wǎng)絡(luò)開銷和收斂速度這幾個性能指標(biāo)。從實驗的結(jié)果來看Babel有著最低的網(wǎng)絡(luò)開銷，同時其收斂速度接近于BMX6。但由于本次實驗所處的電磁波環(huán)境較為安靜，而Babel被動式的路由更新策略必然使其具有最低的開銷。但在真實的網(wǎng)絡(luò)環(huán)境中，電磁干擾和鄰接點信息的變化會讓其不斷進(jìn)行路由信息的更新并使其網(wǎng)絡(luò)開銷迅速增加。因此在復(fù)雜的網(wǎng)絡(luò)環(huán)境中使用BMX6協(xié)議將會具有最好的網(wǎng)絡(luò)性能。

[參考文獻(xiàn)]

[1]方旭明，等.下一代無線因特網(wǎng)技術(shù)：無線Mesh網(wǎng)絡(luò).人民郵電出版社. 2005年5月第1版.pp.108–110.

[2]Luigi Iannone，et al.“Cross-Layer Routing in Wireless Mesh Networks”， Computer Networks. March 2005，445～487.

[3]David Murray，Michael Dixon and Terry Koziniec.An Experimental Comparison of Routing Protocols in Multi Hop Ad Hoc Networks.In Proc.ATNAC 2010.2010.

[4]Jesús Friginal，Juan-Carlos Ruiz，David de Andrés and Antonio Bustos.Mitigating the Impact of Ambient Noise on Wireless Mesh Networks Using Adaptive Link-Quality-based Packet Replication.DSN'2012：1-8.2013.

[5]Hafslund，A.，T nnesen，A.，Rotvik， R.B.，Andersson， J.，Kure，. Secure Extension to the OLSR Protocol.Recent Advances in Intrusion Detection Lecture Notes in Computer Science Volume 3858，2006，pp 330-350.

[6]María E.Villapol，David Pérez Abreu，Carolina Balderama， Mariana Colombo.Performance comparison of mesh routing protocols in an experimental network with bandwidth restrictions in the border router.Revista de la Facultad de Ingeniería U.C.V.，Vol.28，N°1，pp.7-14，2013.