基于BATMAN_Adv路由协议的自组网系统研究与实现

郑　昱　惠　子　陈　婷

(1.西安电子工程研究所　西安　710100;2.陕西应用物理化学研究所　西安　710061)

0　引言

移动自组网具有无中心抗毁性好、无需基础设施支持、支持高速动态变化的网络拓扑等优点，使其非常适合应用于军用战术网络和民用车载网络[1]。自组网的核心是路由算法，如何使用一个性能优越的路由算法是自组网系统设计的关键。本文对BATMAN_Adv路由协议进行了研究，并基于该协议在ARM嵌入式开发平台上实现了一种自组网系统。

1　BATMAN_Adv路由协议研究

1.1　BATMAN_Adv简介

BATMAN_Adv为移动Ad-Hoc网络更优方案高级版(Better Approach To Mobile Ad-Hoc Networking Advanced)的英文缩写，其源自于对BATMAN(Better Approach To Mobile Ad-Hoc Networking)路由协议的增强和改进。BATMAN路由协议采用了一种先验式的自组网路由算法[2]，它与OLSR等其他先验式自组网路由算法不同，每个节点无需通过获得全网的网络拓扑来找寻到达目的节点的完整路由路径，而只需要获得通过哪些邻居节点够到达目的节点，并从中选择到达目的节点的最佳邻居节点作为数据的下一跳节点。这样使得协议轻量化，能够迅速适应快速变化的网络拓扑，大大减轻了每个节点的处理数据量，从而解决了OLSR等之前的先验式路由算法在网路规模扩大时对节点处理能力要求增加，处理时延增大的问题。

BATMAN_Adv路由协议是针对BATMAN路由协议的改进，其在保持BATMAN基本算法的基础上，主要将路由协议由路由层实现改为MAC层实现，路由协议帧由UDP包改为以太网帧。这样的改进首先使得BATMAN路由算法在软件实现时可以从操作系统的用户层实现转为内核层实现，从而降低软件处理的开销；其次，形成一个虚拟的二层交换网络，各节点如同在一个本地交换网络中进行数据传输，它们无需了解全网拓扑情况；最后，由于在MAC层中运行，所以在其之上可以适配几乎所有网络协议，例如Ipv4、Ipv6、DHCP等，扩展性极强。虽然BATMAN_Adv在MAC层中运行，但是其并不依赖于特定的网络硬件，可以支持任何采用以太网类型的底层网络，例如Wifi、LAN、VPN等[3]。

下面根据BATMAN_Adv的最新实现协议对其各个关键技术方面进行研究分析。

1.2　BATMAN_Adv协议帧

BATMAN_Adv路由协议包含BATADV_IV_OGM，BATADV_BCAST， BATADV_CODED，BATADV_UNICAST，BATADV_UNICAST_FRAG，BATADV_UNICAST_4ADDR，BATADV_ICMP，BATADV_UNICAST_TVLV八种协议帧。其中，BATADV_IV_OGM协议帧主要用于节点发现、链路检测等，BATADV_BCAST和BATADV_UNICAST主要用于承载上层广播和单播的以太网帧。在这八种协议帧中，对于路由算法的正确运行来说最为关键的帧为BATADV_IV_OGM帧，下面就主要对OGM的帧结构进行相应的分析。

BATADV_IV_OGM除去协议名称和版本号的前缀BATADV_IV后，一般称其为OGM帧，OGM为Originator Message(源节点消息)的缩写。其帧格式如图1所示。

图1　OGM帧结构

其中，各主要域的具体表示如下：

1)类型：用于区分BATMAN_Adv八种不同的帧；

2)版本：用于表示协议版本信息；

3)TTL：OGM生存期，即OGM的最大转发次数；

4)FLAG:用于表示路由的相关标识；

5)序号：用于区分新旧OGM帧，是路由选择的关键信息，长度为4字节，循环使用；

6)源地址：生成该OGM的源节点地址；

7)上一跳地址：表示上一跳节点的地址；

8)TQ：表示链路的传输质量。

1.3　BATMAN_Adv滑动窗口机制

BATMAN_Adv通过统计和分析接收到OGM帧的数量来判断已检测到链路的质量。由于自组网网络链路的不确定性，OGM帧在传输过程中可能延迟或者丢失，所以节点可能收到较早的OGM帧，这种较早的OGM帧所携带的链路信息早已失效，应该将其丢弃。BATMAN_Adv通过滑动窗口机制来维护一组有效的OGM帧序号。如图2所示，假设窗口大小为8，当前最新OGM序号为100，则有效的OGM序号为93到100。说明只要收到的OGM帧的序号在这8个序号之内就说明该OGM帧为有效OGM帧，应该将其统计并分析；如果收到的OGM帧的序号不在这8个序号之内，则应该判断该序号在滑动窗口的左侧还是右侧，如果在左侧，则说明该帧为过期失效的OGM帧，应该不做统计分析，直接丢弃，如果在右侧，则说明该帧比当前最新OGM序号还更新，应该调整滑动窗口，将最新OGM序号设置为该帧的序号，滑动窗口相应右移，并对其进行统计分析。

图2　滑动窗口机制

1.4　BATMAN_Adv 源节点表

BATMAN_Adv维护着一个源节点信息表，该表与传统路由表的功能类似，用于存储本节点所获得的所有源节点的信息。

源节点信息表的基本单位为一个源节点信息单元，该单元存储着本节点关于该源节点的所有信息，单元中的表项较多，不仅包含路由所需要的信息，还包含VLAN表、编码表等子表项，以及维护源节点信息表的链表信息，所以下面只对其中最为核心的表项进行相应的分析。

1)orig：用于存储该源节点的以太网MAC地址信息；

2)ifinfo_list：源节点硬件接口信息表，包含了router、last_real_seqno、last_ttl等子表项，其中router中包含了如何路由才能达到该源节点的信息，即到达该源节点的最优下一跳节点信息，last_real_seqno是最后收到的来源于该源节点的OGM帧序号，即1.3节中所指的当前最新OGM序号，last_ttl是最新收到数据包的TTL信息，在一个稳定的网络拓扑中，两节点之间传输的数据包的TTL不会有大的改变，所以通过该信息可以检测目前网络拓扑是否有变化；

3)last_seen：从该源节点收到的数据包的最新时间标识；

4)neigh_list：所有能够到达该源节点的邻居节点信息，能够到达该源节点的邻居节点可能有若干个，路由算法的核心功能就是从中选取一个最佳的邻居节点作为到达该源节点的下一跳节点；

5)bcast_own_sum：用于统计本节点广播发送的OGM包通过该源节点重新广播后又发送回自己的数量，统计这个数量对于计算TQ值至关重要。

1.5　BATMAN_Adv路由算法

在BATMAN_Adv中每一个网络节点都称作一个源节点(Originator)，每一个Originator周期性的广播OGM帧，在邻居节点收到OGM帧后，邻居节点根据以下的判断对OGM帧进行处理：

1)如果OGM帧的版本信息不对，则直接将其丢弃；

2)如果OGM帧中的上一跳地址与本节点地址一致，说明是本节点发送的OGM帧，则直接将其丢弃；

3)如果OGM帧中的源节点地址与本节点地址一致，说明是本节点发送的OGM帧经过邻居节点又广播回来的，可以推定本节点与该邻居节点之间为双向链路，标记与该邻居节点为双向链路，并丢弃该OGM帧；

4)如果OGM帧序号在滑动窗口范围内，则依据1.3节所介绍的滑动窗口机制进行相应处理，且将该OGM重新广播给其他节点。

为了防止OGM被无限制的广播，所有节点在接收到OGM帧时如果发现该OGM帧已经被接收过或者该OGM帧的TTL为2时，都会将其丢弃，这样保证了所有OGM帧只会在每个节点中转发一次，这种选择性的洪泛机制保证了全网不会因为OGM帧产生全网广播风暴，从而保障数据的正常通信。

每个节点针对每一个邻居节点维护一个本地TQ值，该值为回环链路状态EQ与接收链路状态RQ的比值，即

TQ = EQ / RQ

(1)

其中EQ是本节点发给该邻居节点又由该邻居节点转发回本节点的OGM帧数，RQ是所有本节点收到由该邻居节点发送的OGM帧数。

源节点在广播OGM帧时将OGM帧中的TQ值初始化为255，OGM帧在广播的过程中，任何接收到该OGM帧的节点将自己本地TQ值乘以收到OGM帧中的TQ值作为转发的OGM帧的TQ值，这样每个节点收到的该OGM帧的TQ值即是该节点到源节点整个链路的状态质量。每个节点从各个邻居节点中获取到源节点链路的TQ值后，从中选择TQ值最大的邻居节点作为最佳下一跳邻居节点，即是到达源节点的最佳下一跳路由节点。

如图3所示，网络拓扑中有A、B、C、D、E、F六个节点，假设两邻居节点之间相互的本地TQ值相等，链路中的数值为本地TQ值。下面介绍如何确定从A节点到F节点的最佳路由路径。如前所述，全网各节点会周期性的发送OGM帧，F节点发送的OGM帧可以通过F-E-C-A和F-D-C-A两条路径到达A节点，该OGM帧的最初TQ值为255，经过C、D、E三个节点的广播转发后，其TQ值将乘以C、D、E三个节点的本地TQ值作为转发OGM帧的TQ值，所以最后A节点通过两条路径收到的OGM帧中的TQ值分别为85和80，而由于A节点收到的两个不同TQ值的OGM帧都由C节点转发，即A节点到达F节点必须经过C节点，所以A节点到达F节点的最优下一跳节点为C节点。同理递推，C节点通过两条路径收到的OGM帧中的TQ值分别为122和114，所以可以判断C节点到达F节点的最优下一跳节点为E节点。最终得出A节点到F节点的最佳路由路径为A-C-E-F。

图3　网络拓扑演示

2　自组网系统设计与实现

2.1　总体设计

自组网设备通常是一种特殊的路由设备，由物理层、MAC层和路由层组成，而基于BATMAN_Adv的自组网设备由于路由协议运行在MAC层，不存在单独的路由层划分，所以可以归类为一种特殊的交换设备，但是无论是路由设备还是交换设备，都需要物理层协议和MAC层协议的支持。

自组网与其他普通无线局域网最主要区别在于自组网分布式、无中心、支持多跳等特点。IEEE 802.11是目前无线局域网中被应用最广的协议标准，其MAC层协议包含DCF模式[4]，能够很好的支持分布式网络，其物理层协议也能够提供较大的数据速率。如前文所述，自组网的核心在于路由协议，而本系统的重点也在于BATMAN_Adv路由协议的应用，所以本自组网系统采用较为成熟的IEEE 802.11协议作为自组网设备的MAC层和物理层协议。

2.2　硬件选型

在硬件选型方面，本系统采用Raspberry Pi 3B开发板作为系统硬件，如图4所示，其板载基于IEEE 802.11n的无线网卡，可以使用该无线网卡作为系统的物理层和MAC层实现。该开发板体积小，功耗和成本低，可支持运行嵌入式Linux操作系统，非常适合作为自组网开发的验证样机平台。

图4　Raspberry Pi 3B

2.3　Linux内核编译

BATMAN_Adv在Linux系统中以内核驱动的方式运行，其实现方式有两种：一种方式为使用BATMAN_Adv开源程序源代码，在使用的Linux系统下进行编译，形成内核模块后载入操作系统中运行；另外一种方式为使用Linux内核自带的BATMAN_Adv内核模块，在Linux 2.6.38之后的所有内核版本中已经默认集成了BATMAN_Adv内核模块，可以直接载入操作系统运行。

本系统使用的嵌入式Linux操作系统内核版本为Linux 3.0，包含BATMAN_Adv模块，因此系统采用第二种方式实现BATMAN_Adv路由协议。虽然内核带有BATMAN_Adv模块，但是一般开发板厂商提供的内核镜像都没有将其编译包含在内，所以需要自己对内核源码进行编译。编译时可使用menuconfig工具来编辑.config内核配置文件[5]，将BATMAN_Adv内核模块选中，最后保存配置文件进行内核编译。

2.4　系统配置

Linux加载BATMAN_Adv内核模块后，还需进行一定配置才能使得自组网设备正常运行起来。配置主要分为两部分，第一部分是对无线网卡进行配置，使得无线网卡运行在AdHoc模式，第二部分是建立BATMAN_Adv虚拟网络设备，将无线网卡绑定在该虚拟网络设备上，并为该虚拟网络设备设置IP地址。

以上配置成功后，各设备之间的自组网就已经建立起来了。

2.5　以太网桥接

自组网设备是一个路由或交换设备，其自身并没有需要传输的业务，所以自组网设备需要有业务输入功能。开发板上的有线以太网卡能够作为业务输入的接口，但是需要做有线网卡到BATMAN_Adv虚拟网络设备的数据转发。实现数据转发有两种方式：一种是有线网卡与虚拟网络设备采用不同的网络地址，然后使用NAT技术进行地址转换；另外一种是在MAC层上将有线网卡与虚拟网络设备进行桥接。如前文所述，基于BATMAN_Adv的自组网设备是一种特殊的二层交换设备，所以采用以太网桥接的方式更符合其自身特点。

在实现时使用Linux中的Brctl命令进行以太网桥接，设定一个桥接虚拟网卡，并将虚拟网络设备和有线网卡都加入到虚拟网卡中，即完成了以太网桥接功能。任意业务设备插入开发板有线网卡接口后就能像使用本地交换机一样与自组网系统中的其他业务设备进行通信。

3　系统测试

最终包含三个节点的自组网系统实现如图5所示。

图5　系统实现图

为了验证自组网系统的基本性能，进行如下测试：

1)点到点无线性能测试

主要对自组网系统点到点单跳情况下的吞吐量、丢包率、时延进行测试，使用Send/Recv测试软件进行测试吞吐量，使用Ping命令进行测试时延。

吞吐量测试的结果如图6所示：

图6　吞吐量测试结果

丢包率测试的结果如图7所示：

图7　丢包率测试结果

时延测试的结果如图8所示：

图8　时延测试结果

根据测试结果可得该自组网系统的点到点平均吞吐量为45Mbps左右，在速率为36Mbps情况下丢包率为0，平均时延为7ms。

2)端到端无线性能和功能测试

通过降低各节点发射功率形成如图9所示的链状拓扑，对自组网系统端到端两跳情况下的中继功能和性能进行测试。

图9　测试拓扑图

中继功能测试结果为当节点A与节点C无法直接通信，当节点B开启后作为中继节点，节点A就能够通过节点B中继后与节点C通信，当节点B关闭后，节点A又无法与节点C通信。

节点A到节点C的端到端吞吐量测试的结果如图10所示：

图10　吞吐量测试结果

节点A到节点C的端到端丢包率测试的结果如图11所示：

图11　丢包率测试结果

节点A到节点C的端到端时延测试的结果如图12所示：

图12　时延测试结果

根据测试结果可得该自组网系统两跳情况下平均吞吐量为35Mbps左右，在速率为20Mbps情况下丢包率约等于0，平均时延为13ms。

通过以上测试可以得出BATMAN_Adv具有良好的系统性能，在多跳情况下，网络性能并没有大幅度的下降。

4　结束语

BATMAN_Adv是一种高效的轻量级自组网路由算法。它具有路由收敛快，协议开销低，鲁棒性强等优点。并且它作为开源协议，已有现成开源实现代码，可根据应用需求进行进一步改进，大大降低自组网路由开发的难度。因此,本文提出了一种基于BATMAN_Adv路由协议的无线自组网系统设计与实现，并在最后进行了相应的测试。该系统无论在军事领域还是在民用领域都具有很好的应用前景。

《火控雷达技术》征稿简则

《火控雷达技术》是国家科委批准的，由西安电子工程研究所主办的国内外公开发行的科技类刊物。先后被《中国期刊全文数据库》、中国核心期刊(遴选)数据库、《中文科技期刊数据库》、《中国学术期刊综合评价数据库》等收录。本刊以理论与实践相结合为指导方针，侧重于工程应用。主要报导国内外同行在雷达、通讯等电子领域内的研究成果、技术发展动态及有关的新理论、新概念、新技术、新方法。为了把刊物办得更好，进一步明确投稿要求，特制定本简则。

1 投稿约定

1)稿件撰写格式按国家科技论文撰写标准GB7713执行。

2)来稿要求有一定的创新性，观点明确、重点突出、文字简练。字数一般不超过5000字(含图、表)。

3)凡属国家基金资助项目，国家、省、部、委重点攻关课题，国际、国内学术会议宣读论文，硕、博士生论文，请予以注明，将优先刊用。

4)多个作者不同单位的，要标明全部作者单位。作者通信地址要写至二级单位。第一作者需附简历，包括：出生年、性别、职称(学位)、研究方向或主要科研项目。

5)文中的图(JPG格式)、表要有图释和表题。坐标图中，横、纵坐标须标明标示、量和单位。

2 中英文摘要及参考文献要求

2.1 摘要

来稿须有中、英文摘要及关键词。中文摘要300字左右。关键词3～5个。

2.2 参考文献

参考文献应是文中直接引用的公开出版物，在文中引用处用"[文献序号(右上角标])"顺序标注。序号与文末参考文献编码一致。文末参考文献著录格式按国家标准GB7714执行。

1)期刊文献 作者.题目[J].刊名，出版年，卷(期)：起止页码.

2)专著 作者.书名[M].版本(第一版可不标注).出版地：出版社，出版年：起止页码.

3)论文集 作者. 论文题目[C].//编者.论文集名.出版地：出版者，出版年：起止页码.

4)学位论文 作者.题目[D].保存城市名：保存单位(写到二级单位)，出版年.

5)标准 起草责任者.标准代号 标准顺序号-发布年，标准名称[S].出版地：出版者，出版年.

6)科技报告 作者.题目[R].报告题目及编号.出版地：出版者，出版年：起止页码.

7)专利 专利所有者.题名：专利国别，专利号[P].公告日期.

8)电子文献 作者.题名[EB/OL].出版地：出版者，发表或更新日期[引用日期].电子文献地址.

3 其他约定

1)来稿采用与否一般在3个月内答复，逾期未接到通知者，稿件可自行处理。稿件一般不退，请自留底稿。

2)请勿一稿多投。来稿一经发表，付给稿酬并赠送当期刊物一本。作者著作权使用费、上网服务费都在所付稿酬中一次性付清。

3)稿件涉及他人利益者，编辑部不承担任何连带责任。

4)稿件录用，文责自负。编辑有权作适当改动，不允许改动者请预先说明。

4 广告征集

本刊征集企业的形象宣传、雷达/通讯领域的产品广告以及各种相关信息。

5 投稿要求：请作者网上电子邮件投稿，E-mail:hkldjs@163.com联系电话：(029)85617147