一种轻量化无线Mesh网络路由协议的设计与实现

刘作学, 代健美, 盛懿君, 王子凡

(1.装备学院信息装备系,北京101416; 2.装备学院研究生管理大队,北京101416)

一种轻量化无线Mesh网络路由协议的设计与实现

刘作学1, 代健美1, 盛懿君2, 王子凡2

(1.装备学院信息装备系,北京101416; 2.装备学院研究生管理大队,北京101416)

BATMAN(better approach to mobile Ad-hoc networking)是一种新的无线Mesh路由协议。分析了BATMAN协议的数据格式和算法思想,设计了具有多Wi-Fi模块的无线Mesh节点,在节点上基于嵌入式Linux开发环境设计实现了BATMAN路由协议,并对BATMAN协议在多跳无线Mesh原型网络中的实际使用性能进行了分析。结果表明：BATMAN协议具有轻量化、快收敛、高效运行等特点,其吞吐量、时延等特性,可以满足无线Mesh网络数据的实时、宽带传输的要求。

BATMAN路由协议;无线Mesh网络;Wi-Fi模块

1 无线Mesh网络路由协议现状

无线Mesh网络(wireless Mesh network)[1-2]是一种融合了WLAN和Ad-hoc网络优势的多跳网络,其伸缩性更强、健壮性更好[3],更适合与IEEE802.11、802.16、802.20等宽带通信技术相结合,提供更高的带宽和更好的可扩展性,在智慧城市建设、抢险救灾应急通信、试验靶场宽带信息接入、战场通信网络互联等方面具有广阔的应用空间。

路由协议是无线Mesh网络的关键技术,是制约网络性能的主要因素。现有应用于无线Mesh网络的路由协议主要有以下3类：

第一类是以优化链路状态路由协议OLSR为代表的先验式路由及其改进版本,包括基于信噪比的OLSR路由协议[4]、基于信誉的OLSR扩展路由协议[5]、基于链路质量的OLSR协议[6]、基于认知的LC-OLSR协议[7]等,此类路由协议在路由判据上有所差别,但其基本思想是一致的,即都属于表驱动的逐跳路由协议范畴,在选择路由时主要考虑了“最小跳数”这个约束条件,且在路径的评判标准上比较单一,没有考虑网络负载的平衡性问题。

第二类是以距离向量路由协议AODV为代表的按需式路由及其改进版本,包括利用Wi-Fi网络自适应速率切换机制的Wi-Fi-AODV[8]、考虑多路径特性的AOMDV协议[9]、基于链路状态加权的路由协议[10]以及多判据跨层优化ACRO路由协议[11]等。与先验式路由不同的是,此类路由协议只有当需要发送消息的时候才进行路由计算,避免了周期性发送控制报文带来的系统开销,但其未考虑无线链路的稳定性问题,当出现非对称链路时,极易产生路由环路,以及丢包率增高、时延增大等现象。

第三类是以802.11s工作组专门为无线Mesh网络开发制定的HWMP(hybrid wireless mesh protocol)[12]为代表的综合路由协议及其改进版本,此类路由协议结合了反应式路由协议和基于树状拓扑的先验式路由协议的优点,能较好地适应无线Mesh网络特点,但协议缺乏有效的拥塞控制策略,也没有充分考虑到公平性和负载均衡的问题,当网络中有大量数据要传输时,会产生网络根节点流量过载的情况。

BATMAN是一种新的引入了综合人工智能(collective intelligence)思想的路由协议[13]。与上述路由协议不同的是,网络拓扑信息不是单由一个节点进行处理,而是分布在整个网络中,因而能够更好地对抗由于网络波动而引起的边界效应并补偿其不稳定性;节点不保存完整的路由表而只保存最佳下一跳节点的信息,使得协议更加轻量化,收敛速度更快,运行效率更高,非常适用于传输质量不稳定的无线Mesh网络。BATMAN有BATMAN Daemon(BATMAND)和BATMAN Advanced(BATMAN-ADV)2种版本,分别在网络层和链路层实现,本文主要对其BATMAND版本进行研究。

2 BATMAN协议分析

2.1 数据包格式

BATMAN通过周期性地广播OGM消息(originator message)来完成路由的发现、建立和拆除。图1描述了BATMAN路由包的基本样式,长度为12个字节的OGM消息包括：

1)版本号(Version),用1个字节表示,用于区分不同的无线网络,协议通过判断接收到的OGM消息的Version值与自身OGM消息的Version值是否相同来决定转发或丢弃该消息;

2)直连链路标志(U),标志该节点是否是直连邻居节点;

3)对称链路标志(D),标志该邻居节点是否双向可达;

4)生存时间TTL(time to live),该字段定义了OGM消息的发送次数,最大值为255,TTL值随着OGM转发次数的增加而递减,当TTL降为0时,该OGM消息被丢弃;

5)网关标志(GWFlags),用1个字节表示,主要用于设定是否为网关节点及其上下行带宽;

6)序列号(Sequence Number),用2个字节表示,在TTL周期内,该号码随着OGM转发次数的增加而递增;

7)发起者地址(Originator Address)用4个字节表示,用于记录生成OGM消息的IPV4地址,只有在该地址与接收节点的地址不一致的情况下,该消息才能被继续处理。除了固定长度的OGM消息之外,路由包还包括可选的主机网络地址(HNA)消息,主要用于设定或查看网络地址(Network Address)和子网掩码(Netmask)等信息。

图1 BATMAN包格式

2.2 路由算法

BATMAN将网络建模为G=(N,E),其中N代表1组节点,而E代表节点对之间的1组链路。对于任意1个包含于N的节点都存在1组单跳邻居节点K。假设s代表源节点,d代表目的节点,如果d∈K,则源节点s到目的节点d的消息在Llink(s,d)上传输,Llink(s,d)∈E;如果d∉K,则该消息需要多跳传输,其链路由Llink(s,i)和Rroute(i,d)构成,其中i是K中的1个成员, Llink(s,i)是链路组E中的1条链路,Rroute(i,d)代表从节点i到节点d的路由,该路由从属于S子网络,可以建模为S=(N-{s},E-{(s,i)：i∈K})。

路由思想为：

1)在网络G中,假设路由消息m需要从s发送到d,估计所有Llink(s,i),其中i是K中的1个成员;

2)判断每条链路的权重Wsi;

3)选择具有最大权重的链路传送m;

4)如果i不是目的节点d,则构建网络子集S,并重复1)～4)。

假设某网络有5个节点,其网络拓扑如图2所示,节点1～5的IP分别为“192.168.0.2”“192.168.0.3”“192.168.0.4”“192.168.0.5”和“192.168.0.6”,假设节点1要给节点5发送消息,其路由过程为：

1)节点2、节点3∈K为节点1的邻居节点,则节点1到其邻居节点的链路集Llink(1,2)和Llink(1,3)∈E;

2)选择链路集E中的权重最高者为最佳链路,假设Llink(1,2)是最佳链路,则消息m沿此链路进行发送;

3)由于节点2不是目的节点,缩小图N为图S;

4)考虑节点2与其邻居节点3、节点4∈KI的链路集Llink(2,3)和Llink(2,4)∈EI;

5)选择链路集EI中的权重最高者为最佳链路,假设Llink(2,4)是最佳链路,则消息m沿此链路进行发送;

6)由于节点4不是目的节点,继续缩小图S为图S′;

7)考虑节点4与其邻居节点3、节点5∈KII的链路集Llink(4,3)和Llink(4,5)∈EII;

8)选择链路集EII中的权重最高者为最佳链路,假设Llink(4,5)是最佳链路,则沿着这条链路发送m;

9)节点5是目的节点,路由完成。

图2 网络拓扑及路由变化图

2.3 最佳链路选择

最佳链路的选择是实现有效路由的主要问题,BATMAN通过链路权重指标Wsi来衡量链路性能的优劣,Wsi充分考虑了由于网络波动而引起的不稳定性以及无线链路上下行信道的差异性,由分别代表节点s与节点i上、下行链路连通特性的和2部分构成。

式中：Qsi是在当前滑动窗口内节点s通过邻居节点i收到的目的节点发出的OGM消息数量;Qsd是节点s收到的由目的节点d发起的OGM消息总数。假设节点s的邻居节点数为X,则Qsd与 Qsi的关系可表示为

式中：Ss中表示节点s发送给节点i的OGM消息数量;Rs表示节点s收到的由节点i转发的发起者为节点s本身的OGM消息数量。由于节点s和节点i之间存在多种可能的路径,而且无线链路总会存在丢包现象,因而总会小于1。

基于此思想,全网各节点都保存了1张包含最佳邻居节点信息的邻居节点表,将源节点到目的节点之间的所有最佳邻居节点串联起来,就构成了1条最佳链路。

3 BATMAN协议在自主无线Mesh网络节点上的设计与实现

3.1 无线Mesh网络节点设计

节点使用Atheros公司的高性能网络处理器AR7161(主频680 MHz)作为主控单元,利用Mini-PCI接口最多可连接4个Wi-Fi模块,使用16 MB SPI FLASH和128 MB DDR内存分别作为系统存储器和高速数据交换设备,扩展了有线网口和串口,便于性能测试和应用扩展。

3.2 协议模块设计

参考Open WRT开源社区提供的BATMAN协议框架[14],基于嵌入式Linux2.6.32系统以及mips-uclibc-gcc_4.3.3交叉编译器,在自研节点上设计实现了BATMAN 3层路由协议。协议分为应用层接口模块和内核层模块2部分,应用层接口模块主要完成协议的配置工作,如工作模式查询或变更、已知网络的加入或删除,以及调试级别的设置等;内核层模块主要完成路由数据包的发送、接收、处理和转发,邻居节点信息列表的建立和路由的选择等功能,下面重点对邻居节点信息获取模块、邻居节点列表创建模块和路由选择模块进行分析。

3.2.1 邻居节点信息获取模块

邻居节点信息获取模块主要完成对接收到的OGM包的分析与处理。如图3所示,模块在设定的超时时间内对OGM包进行接收,接收端口为4305端口。如果在超时之前收到有效的BATMAN包,则解析BATMAN包,获取包序列号、网关标志、版本号、双向链路标志、发起者IP地址、前一发送者IP地址以及邻居节点IP地址等信息;否则重新设定定时器并进入下一次接收过程。如果收到的OGM包的版本号与本节点版本号一致,则对OGM包内的“发起者地址”进行分析,否则丢弃该OGM包;如果收到的OGM包的发送地址是一个广播地址,则丢弃该OGM包;如果OGM包内的“发起者地址”与本节点的IP地址一致,说明存在邻居节点,进而判断链路的双向特性;如果OGM包的直连链路标志(U)为1,则记录OGM包中的“前一发送地址”,并更新邻居节点列表项。需要说明的是,如果收到了来自于单跳邻居节点发起的OGM包,或者来自于非邻居节点且具有全新的生存时间(TTL)的OGM包,则该OGM包应该被再次广播转发。

图3 邻居节点信息获取模块

3.2.2 邻居节点列表创建及路由选择模块

本模块用于创建和维护邻居节点列表,列表主要包括以下6项内容：

1)Neigh_addr,记录邻居节点的IP地址;

2)New_seqno,表示的是在固定滑动窗口内收到的OGM包序号,由于节点会收到多个来自同一发起者的OGM包,这里只是记录最新收到的但尚未被标记的序号;

3)PCount_S,在滑动窗口内收到的由本节点发起的OGM包数量,此条目可作为该邻居节点到本节点之间路径质量的度量依据,包计数值越大,表示链路质量越好;

4)PCount_O,在滑动窗口内收到的由非本节点发起的OGM包数量,此条目可作为该邻居节点到发起者之间路径质量的度量依据,包计数值越大,表示链路质量越好;

5)Last_VLD_TimeStamp,记录的是通过该邻居获取到的最新OGM消息的时间戳;

6)Last_TTL,记录了通过该邻居获取到的最新OGM消息的生存时间。

以2.2节给出的原型网络为例,节点1的邻居节点列表如表1所示。

表1 邻居节点列表

路由选择过程如图4所示。

图4 路由选择过程

4 BATMAN协议性能分析

目前大多数针对路由协议的分析都是基于仿真工具完成的,由于仿真环境往往较为理想,其仿真结果仅能给出性能的大致估计,并不能代表协议的实际使用特性;另外,使用不同的仿真软件,其仿真结果也不尽相同。为此,本文在自主构建的无线Mesh原型网络中实际测试分析了BATMAN协议的使用效能。

试验区域为50 m×50 m的空间,每个节点安装2个Router Board公司的Atheros 92xx系列Wi-Fi模块,各节点在邻近节点覆盖范围内自由移动(移动速度约为1 m/s),工作在802.11n模式,使用正交信道,发送功率设为0 dBm,其无线信号覆盖半径约为5 m,保持相邻节点间的直线距离约为9 m。

BATMAN路由算法的设置如下：OGM间隔为1 s;TTL为255;窗口大小为100。

首先利用Ix Chariot软件对吞吐量进行了测试,Ix Chariot服务器端设置网络协议为TCP协议,服务质量为H263CIF,连接数为10对,各跳测试时间均为10 min。测试结果如图5所示,在单跳情况下,平均吞吐量可达到78.237 Mb/s;当跳数增加为2跳时,无线信道中的数据碰撞增加,用于路由的OGM消息也相应增加,吞吐量下降为52.474 Mb/s;随着跳数进一步增加为3跳、4跳时,吞吐量进一步下降为44.431 Mb/s和37.568 Mb/s。可以看出,吞吐量随着跳数的增加逐渐下降,但得益于BATMAN协议较少的OGM包和基于统计方法的路由查找策略,并没有像传统路由那样随着跳数n的增加呈现1/n的趋势急剧下降[15-16]。

图5 吞吐量测量结果示意图

另外还进行了高速视频多跳传输试验,测试发现,在中继节点静止的情况下,视频传输流畅,无明显丢包现象;在中继节点移动的情况下,由于发生了路由链路的更新,视频传输偶尔有丢包现象,但恢复时间很快,不影响显示效果;多跳后的视频传输时延不超过450 ms,具有良好的实时性,能够满足视频的实时传输需要。

5 结束语

本文对BATMAN路由协议的数据包结构、算法思想进行了深入研究,自主研发了多接口的无线Mesh网络节点,并在自主构建的无线Mesh网络原型系统上设计实现了BATMAN路由协议,最后对BATMAN协议的实际使用性能进行了分析。得益于BATMAN协议轻量化的设计思想和基于统计方法的路由查找策略,该算法在原型系统中具有良好的带宽和时延特性,能够满足小型Mesh网络的实时、宽带数据传输要求。下一步将针对拓扑动态变化大、节点数量较多(超过30个)的无线Mesh网络进行协议应用与分析。

References)

[1]AKYILDIZ I F,WANG X,WANG W.Wireless mesh networks：a survey[J].Computer Networks Journal(Elsevier), 2005,47(4)：445-487.

[2]方旭明.下一代无线因特网技术：无线Mesh网络[M].北京：人民邮电出版社,2006：1-10.

[3]AKYILDIZ I F,WANG Xudong.A survey on wireless mesh network[J].IEEE Communications Magazine,2005,43(9)：23-30.

[4]ELSHAIKH M,KAMEL N,AWANG A.High throughput routing algorithm metric for olsr routing protocol in wireless mesh networks[C]//IEEE.Proceedings of the 5thInternational Colloquium on Signal Processing&Its Applications. Kuala Lumpur：IEEE,2009：445-448.

[5]DING Qing,JIANG Ming,LI Xi,et al.RePro：a reputation based proactive routing protocol for the wireless mesh backbone[C]//IEEE.Proceedings of the 5thInternational Joint Conference on INC,IMS and IDC.Seoul：IEEE,2009：516-521.

[6]PASCHOALINO C R,MADEIRA E R M.A scalable link quality routing protocol for multi-radio wireless mesh networks[C]//IEEE.Proceedings of the 16thInternational Conference on Communications and Networks.Honolulu：IEEE, 2007：1053-1058.

[7]王靖,李芳芳,于全.基于认知的多信道无线Mesh网络路由协议研究[J].计算机科学,2012(10)：40-44.

[8]魏翼飞.一种适用于Wi-Fi Mesh网络的AODV改进路由协议[J].北京邮电大学学报,2007,30(4)：120-124.

[9]庞朝飞,夏清国.两种无线Mesh网络路由协议与仿真比较[J].科学技术与工程,2011(30)：7386-7392.

[10]符云清,王松健,吴中福.基于链路状态加权的无线Mesh网络路由协议[J].计算机研究与发展,2009(1)：137-143.

[11]李劼.基于跨层设计的多判据AODV路由优化机制[J].四川大学学报：工程科学版,2008(4)：153-159.

[12]LAN/MAN Standards Committee of the IEEE Computer Society.IEEE 802.11s(tm)/D2.0.Draft Standard for information technology-telecommunications and information exchange between systems-local and metropolitan area networks-specific requirements-part 11：wire1ess LAN medium access control(MAC)and physical 1ayer(PHY) specifications amendment：mesh networks[S].New York：The institute of Electrical and Electronics Engineers, Inc.2008.

[13]NEUMANN A,AICHELE C,LINDNER M et al.Better approach to mobile Ad-hoc networking[EB/OL].(2008-04-07)[2013-10-01].http：//datatracker.ietf.org/doc/draftwunderlich-openmesh-manet-routing/.

[14]NTLATLAPA N,JOHNSON CA D.Simple pragmatic approach to mesh routing using BATMAN[C]//IEEE.In 2ndIFIP International Symposium on Wireless Communications and Information Technology in Developing Countries, CSIR.Pretoria,South Africa：IEEE,2008：6-7.

[15]CHEN Rongdi.Performance comparison of two wireless mesh networks[D].Tsinghua：Network Research Center of Tsinghua University,2005：10

[16]STEFAN A,WOLFGANG S.Performance measurements in wireless 802.11g multi-hop networks[D].Hogskolani Halmstad：MASTER'S THESIS for the University of Hogskolani Halmstad,2006：5.

(编辑：孙陆青)

The Design and Realization of
a Lightweight Wireless Mesh Network Routing Protocol

LIU Zuoxue1, DAI Jianmei1, SHENG Yijun2, WANG Zifan2

(1.Department of Information Equipment,Equipment Academy,Beijing 101416,China; 2.Department of Graduate Management,Equipment Academy,Beijing 101416,China)

BATMAN(better approach to mobile Ad-hoc networking)is a new wireless Mesh network routing protocol.The data format and algorithm of BATMAN protocol are analyzed,and the BATMAN protocol is designed based on the embedded Linux and realized on the self-developed wireless Mesh node mounting multiple Wi-Fi modules.The pragmatic performance is tested in the multihop Mesh prototype network.The result shows that the characteristics of latency of BATMAN protocol which is lightweight,rapid convergence,and efficient can meet the real-time and broadband transmission requirement of wireless Mesh network.

BATMAN routing protocol;wireless Mesh network;Wi-Fi module

TP 393.0

2095-3828(2014)02-0065-06

ADOI10.3783/j.issn.2095-3828.2014.02.016

2013-10-18

刘作学(1962-),男,教授,硕士.主要研究方向：军事无线通信技术.lzx626@sohu.com.