無線網(wǎng)狀網(wǎng)主動(dòng)路由協(xié)議的對(duì)比

何淵淘 李清秀

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

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

1 引言

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

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

2 WMN路由協(xié)議

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

2.1 OLSR路由協(xié)議

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

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

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）來計(jì)算到達(dá)某一節(jié)點(diǎn)的跳數(shù)。ETC不僅考慮了到達(dá)某一節(jié)點(diǎn)的跳數(shù)信息，還綜合考慮了鏈路帶寬、擁塞度等一系列指標(biāo)來作為選路的依據(jù)。然而ETC會(huì)由于無線環(huán)境的變化和網(wǎng)絡(luò)節(jié)點(diǎn)的加入/退出不斷變化，這也就造成路由的不斷翻轉(zhuǎn)使得網(wǎng)絡(luò)難以收斂。因此Babel使用歷史感知機(jī)制（History-sensitive）來加速網(wǎng)絡(luò)的收斂，即具有相近ETC值的情況下選擇曾經(jīng)使用過的路徑。與OLSR不同，Babel在網(wǎng)絡(luò)收斂后不會(huì)在整個(gè)網(wǎng)絡(luò)范圍內(nèi)進(jìn)行周期性的路由更新和宣告，只有當(dāng)節(jié)點(diǎn)信息和狀態(tài)發(fā)生變化時(shí)才會(huì)被動(dòng)觸發(fā)更新。

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

2.3 BMX6路由協(xié)議

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

當(dāng)前針對(duì)BMX6的實(shí)現(xiàn)為bmx6d，本論文選擇其作為實(shí)驗(yàn)平臺(tái)。

3 實(shí)驗(yàn)設(shè)計(jì)和性能對(duì)比

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

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

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

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

4 結(jié)論

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