无线网状网主动路由协议的对比

何渊淘 李清秀

摘 要：无线网状网（Wireless Mesh Network，WMN）是一种多跳的自组织网络， WMN路由协议对网络的性能指标起到了决定作用。近年来一些WMN路由协议被提出和实现，例如OLSR，Babel，BMX6。在本文中，作者分析了几种路由协议的工作机制和选路原理，并在真实的环境下构建了测试平台。实验的结果表明BMX6协议在收敛速度和网络开销上要优于Babel和OLSR（Optimized Link State Routing）。

关键词：无线网状网；BMX6；OLSR；Babel

1 引言

由于部署的时间和成本的因素，在临时场所或灾难地区进行组网存在着较大的困难，WMN就是针对该问题而提出的解决方案[1]。近年来以gufi.net和AWMN为代表的社区无线网络的设计和部署进一步推动其发展[2-3]，大量私有和开源的WMN路由协议被提出和实现。其中具有代表性的是OLSR、Babel、BMX6、B.A.T.M.A.N-ADV[4-6]。由于WMN路由协议会对其性能产生决定性作用，因此掌握其性能特征对WMN网络的开发和对协议的改进具有重要的意义。

本文首先对这几种网络协议的工作机制和选路原理进行分析和对比，然后在校园网环境下构建了小型WMN测试平台。最后在此平台的基础上，测试这几种路由协议的网络开销、收敛速度等指标，并对实验数据进行分析。

2 WMN路由协议

WMN是一种典型的Ad-Hoc网络，当前根据WMN产生路由表的方式可以将协议分为主动式、被动式和混合式。主动路由协议在节点的链路上定期或者触发式的传递链路状态信息或路由表，以实现全网可达。主动式路由协议适合在设备供电较为稳定的场景，该场景通常有较高的链路带宽，从而降低路由协议在整体网络中的开销。被动式路由协议适合设备供电紧张，节点移动性高，链路带宽较低的场景。这类路由协议事先不生成任何路由表，仅在有效数据发送时才进行路由信息的计算。混合型路由协议则兼具上述两类路由协议的特征，本文中所对比的路由协议属于主动式路由协议。

2.1 OLSR路由协议

OLSR即Optimized Link Status Routing Protocols[5]，是一种典型的链路状态路由协议。链路状态协议在节点的链路上进行链路信息的宣告和传递，在每个节点内保存整个网络拓扑并以此来计算路由。由于无线电资源本身容易受到干扰且802.11中媒体接入控制层的竞争机制，WMN会因为大量的链路状态更新而造成较高的开销。OLSR引入了Multi-Point Relays（MPR）的方案来避免这一问题，MPR是网络节点的一个子集，由参与OLSR协议的节点选出。网络的拓扑仅存储在MRP节点上，并由MRP节点来完成洪泛。这种机制极大减少了链路状态更新的次数，也极大提升了端到端的吞吐量。

由于链路状态协议在节点间信息不一致的情况下会产生路由环路，而WMN节点的移动性则会加剧节点间信息不一致的状况。为了避免这一现象，OLSR增加了鱼眼机制（Fish eye）的支持，即降低对较远节点的链路状态更新频率来避免环路。由于OLSR提出较早而具有较多的实现，本文使用OLSRD来进行实验和性能对比。

2.2 Babel路由协议

Babel属于距离向量路由协议[6]，该协议不仅支持在无线网络也支持有线网络。与RIP为代表的有线网络协议相比，Babel不再使用跳数来进行最优路径的选择，而是使用“期望传输跳数”Expected Transmission Count（ETC）来计算到达某一节点的跳数。ETC不仅考虑了到达某一节点的跳数信息，还综合考虑了链路带宽、拥塞度等一系列指标来作为选路的依据。然而ETC会由于无线环境的变化和网络节点的加入/退出不断变化，这也就造成路由的不断翻转使得网络难以收敛。因此Babel使用历史感知机制（History-sensitive）来加速网络的收敛，即具有相近ETC值的情况下选择曾经使用过的路径。与OLSR不同，Babel在网络收敛后不会在整个网络范围内进行周期性的路由更新和宣告，只有当节点信息和状态发生变化时才会被动触发更新。

面向Babel协议的实现主要有Babled和Quagga。Babled是针对Babel的独立实现，Babeld支持将物理层信息作为选路的依据，从而降低不同频率间的干扰。而Quagga则集成了各种路由协议，除了支持Babel还支持OSPF和BGP等协议，本文选择Quagga来做性能对比。

2.3 BMX6路由协议

BMX6即B.A.T.M.A.N-Experimental version 6是B.A.T.M.A.N路由协议的一个分支。BMX6是一个主动式路由协议，也是一个距离向量路由协议。该协议使用内部描述符表、哈希表、全局描述符表来降低路由协议所带来的开销。内部描述符仅存储邻接点的信息，全局描述符存储所有节点的信息，而哈希表将两个描述符中的表项做映射。节点的全局描述符信息在节点启动后仅进行一次洪泛，而后使用其哈希值来代描述符，从而减少协议的网络开销。通过这种方式节点在移动后仅需要重建本地描述符表，减少了节点移动带来的网络开销。除此之外BMX6的路由协议将社会关系信任模型应用到节点之间的关系上，通过在节点间建立信任关系来作为选路的依据，从而保证了网络的流量从可以信赖的节点进行转发，这种机制降低了由于恶意接入而带来安全问题。由于BMX6的这种安全特征，在社区无线网络中应用较多[2]。

当前针对BMX6的实现为bmx6d，本论文选择其作为实验平台。

3 实验设计和性能对比

本实验在一栋五层高的大楼内进行，本次试验共使用无线节点七十个，为了减少外界电磁波的干扰，实验选择了5.8GHz作为无线频率。为了实验和设备编址方便，对设备进行编号。设备号码为1到60，而设备的接口地址也依照编号进行编制。本实验的设备为tl-wr2543nd，安装过OpenWRT和三种路由协议后开始配置接口。首先将每台设备的无线网卡设置为ad-hoc模式，ssid统一设定为lab-mesh，然后设置设备的wlan0和eth0接口的网络层地址。由于BMX6d和Quagga（babel）仅支持ipv6协议，在针对BMX和Babel的实验中将其eth0的地址设定为2001：DA8：5015：3010：：X/64，其中X分别为设备对应的编号，而wlan接口则使用ipv6的本地链接地址。针对OLSR的实验，则使用ipv4进行编址，eth0接口的地址为192.168.X.1/16，wlan0接口的地址为10.10.x.1/16，X为设备的编号。

在实验中，首先测试了在所有节点启动后所产生的网络开销，其结果见图一。从图中可以看出，OLSR协议在在160ms左右出现了一个流量高峰（58kbps/s），这是因为此时每个节点都在最大量的发送并接受链路状态信息。在此之后网络开始缓慢收敛，在收敛状态下OLSR协议所带来的网络开销稳定在25kbps左右。而Babel导致每个节点启动后会发现邻居节点，会进行路由信息宣告，在25ms左右进入网络流量的高峰，达到40kbps/s。由于实验选用5GHz的频段，该频道受干扰较小，网络收敛后没有明显的邻居信息的变化，因此Babel协议不会额外发送链路信息，此时Babel只会周期性探测邻居点的可达性量。由于这种开销仅出现在局部，此时网络的开销仅有即15kbp/s左右。而BMX协议在整个启动的过程中会传递节点描述信息，并在在48ms左右进入稳定状态。由于BMX协议在收敛后仅仅会周期性传递节点信息的哈希值，协议所带来的网络开销稳定在20kbp/s左右。

在图二的实验中，作者每次启动10个节点，并收集网络的整体流量数据。从图中可以看出，BMX6和Babel中网络开销随时间增长较慢，而OLSR协议会随着网络中节点数目的增多而迅速增加。这主要是由于OLSR属于链路状态协议，其会在整个网络中广播链路状态信息。而随着网络的增大，链路状态信息的数量也在迅速增多，从而带来更大的网络开销。而BMX6和Babel则属于距离矢量路由协议，在这两个协议中都采用了策略来减少网络的协议开销。

在图三的实验中为网络收敛速度的实验，该实验分别测试了跳数对网络收敛带的影响。图中显示OLSR的收敛时间会随着跳数的增加而迅速增加，这是由于OLSR的鱼眼机制所造成的。鱼眼机制通过减少对较远节点的链路状态更新来避免环路，这也不可避免的导致较远的节点的收敛速度与跳数成正比。与OLSR不同，Babel和BMX6的收敛速度基本不受节点跳数的影响。起因在于Babel协议采用了被动更新机制，当其侦测到邻居的存在状态变化时能迅速传输新的网络拓扑信息，这一机制加快了网络的收敛速度。而BMX6协议只使用了相比于Babel更高的频率去检查邻居点的存在状态，并通过周期性的广播来将网络信息发送出去，这也导致了其具备最高的收敛速度。

4 结论

本文对WMN的几个主动式路由协议，BMX6、Babel、OLSR的工作机机制进行了深入的分析，并在真实的环境和测试平台下对比了这几个路由协议的网络开销和收敛速度这几个性能指标。从实验的结果来看Babel有着最低的网络开销，同时其收敛速度接近于BMX6。但由于本次实验所处的电磁波环境较为安静，而Babel被动式的路由更新策略必然使其具有最低的开销。但在真实的网络环境中，电磁干扰和邻接点信息的变化会让其不断进行路由信息的更新并使其网络开销迅速增加。因此在复杂的网络环境中使用BMX6协议将会具有最好的网络性能。

[参考文献]

[1]方旭明，等.下一代无线因特网技术：无线Mesh网络.人民邮电出版社. 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.