一种面向智能终端自组网的BATMAN-Adv协议优化设计方法

摘要

本发明公开了一种面向智能终端自组网的BATMAN‑Adv协议优化设计方法。首先，在控制层面的路径质量度量值TQ计算上，不再采用原协议中将丢包造成的TQ值变化和原先稳定链路的TQ值进行平均操作的算法，改为将邻居节点发来的最新序列号的OGM包中消息字段的TQ值作为从该邻居节点到达此OGM源节点的路径质量度量值的参考；其次，在数据层面节点转发数据帧去往目的地的时候，不再采用原协议中如果此刻下一跳邻居节点为不可达状态，直接丢弃数据帧的做法，改为将数据帧缓存一段时间的机制。本发明在拓扑变更时的控制层面路由重收敛优化和数据层面数据缓存转发机制相结合，能够在网络连接发生波动时进行快速的路由更新同时提高收到的数据的完整性。

权利要求

1.一种面向智能终端自组网的BATMAN‑Adv协议优化设计方法，其特征在于：包括步骤：步骤一：本地节点记录关于任意一个源节点始发的源节点消息OGM中最新的序列号；当某一节点收到邻居节点发来的始于某一源节点的OGM包，查看其序列号大小，如果该序列号比本地所记录的关于该源节点的最新消息的序列号小，将该OGM包丢弃；如果该序列号比本地所记录的关于该源节点的最新消息的序列号大，将其OGM包中的消息字段中的路径质量度量值TQ值覆盖在原先这条从该邻居节点到达源节点的路径的TQ值上，完成对该邻居节点到达源节点的路径质量度量值更新，并转入步骤二；

步骤二：将更新之后的该邻居节点到达源节点的路径质量度量值TQlocal与该节点到该邻居节点的路径质量度量值TQOGM进行乘法运算，得到从该节点以该邻居节点为下一跳，到达源节点的总路径质量度量值，记为TQglobal；并将其写入OGM包中的消息字段，然后将该OGM包泛洪转发给其余邻居节点，并转入步骤三；

步骤三：重复步骤一和步骤二，该节点分别记录自己的所有邻居节点传来的最新OGM消息字段中的TQOGM值与自身到该邻居的TQlocal进行乘法计算后的TQglobal，选出最大的TQglobal，并将其对应的邻居节点作为该节点传递给源节点的最优下一跳；当收到通信请求时，转入步骤四；

步骤四：某一节点收到其邻居节点传来的数据帧，查看其目的地址，查询自身路由表中是否有与之对应的路由，如果不存在，将数据帧丢弃；如果存在，按路由进行转发，进入步骤五；

步骤五：若自身与下一跳节点的链接状态正常，则自身的数据转发任务结束；若链路此时为down的状态，数据帧无法传递，则将该数据帧存入缓存，并立即向其所有的邻居节点通告OGM，该OGM的序列号为最新的，其消息字段的该链路的TQ值置为0，转入步骤六；

步骤六：等待设定时间，如果在这段时间内，链接状态恢复正常，立即通过该路径将数据帧传递给该下一跳，并立刻向其所有的邻居节点通告OGM，该OGM的序列号为最新的，其消息字段的TQ值为按原协议数学算法重新计算的；如果直至最大缓存时间结束，链接状态仍未恢复正常，则丢弃数据帧。

2.根据权利要求1所述的BATMAN‑Adv协议优化设计方法，其特征在于：所述设定时间为OGM周期更新时间的四倍。

说明书

一种面向智能终端自组网的BATMAN‑Adv协议优化设计方法

技术领域

[0001] 本发明属于无线通信技术领域，涉及针对BATMAN‑Adv协议在网络拓扑变更时的重收敛性能不佳以及数据端到端丢失问题，对其在控制层面与数据层面的双优化措施。

背景技术

[0002] 智能终端自组网，利用智能手机、平板、PDA等终端所携带的Wifi、蓝牙、红外线等天线组成设备间的Mesh网。它是一种移动Ad hoc网络，不依赖基础通信设施，具有自组织、
自恢复、高抗毁的能力，可以支撑数据、话音、视频等多媒体业务的多跳传输，可应用于野外
作业、临时会议、楼宇通信、无线监测、车辆组网、公安消防、反恐特勤、矿井作业、抢险救灾
等近距离通信组网场合。

[0003] BATMAN协议是应用在无线网络中的一个优秀的距离矢量路由协议，依靠各个节点周期性地发送源节点消息(Originator Messages，OGM)的机制来工作。这些OGM通告了站点
的位置，同时也用于发现和保持路径。通过泛洪消息，网络中的每个节点就可以知道其他节
点的存在，同时也维护了一个到达其他节点的可行的下一跳。而在可行的下一跳当中，会使
用Bellman‑Ford算法选择一个最好的下一跳，选择的根据是链路的质量度量值，称为TQ值。

[0004] BATMAN协议在2007年以后，实现了一个新的改进版本，被称为 BATMAN‑Adv，而之前的版本也逐渐不再使用。它是BATMAN协议在OSI模型二层运行的实现，并通过以太网帧来
传输路由信息。协议封装并转发所有数据直接到达目的节点，模拟出一个虚拟的网络交换
环境。因此，所有节点就像处于本地链接，它们不了解网络的拓扑情况，也不会受到网络变
化的影响。这种设计有一些有利的特点。如对于网络层的透明性，由于协议工作在数据链路
层，网络层的协议是不可知的，设备中协议在启动时，并不一定要分配IP地址后才能工作。
网络层的透明性大大提高了协议的可扩展性。

[0005] BATMAN‑Adv协议拥有较为出众的网络性能，同时具有很多其他协议不具有的特性，但是该协议的收敛性能表现不佳，应用在智能终端自组网环境下，由于终端的频繁移
动，网络拓扑变动较大，可能会造成路由的动荡，丢包率过高甚至路由环路的出现。

[0006] 通过分析发现，协议为了快速建立网络拓扑，会严格地按照本地链路的平均 TQ值来转发消息，而这种消息处理方式是欠妥的。BATMAN‑Adv协议用序列号来标记每个帧，用以
检查路由的新旧程度，所以在这种转发机制中，假如有一个含有更新的序列号是通过次优
路径到达某节点的话，该节点也会将最优路径上的平均值写入消息的字段，然后广播出去。
这种快速转发机制使得节点对于路径的变化不敏感，当原先最优路径发生改变的时候，节
点在一定时间内还按照原先最优路径的平均值来重新广播OGM消息，这就很容易产生次优
路径甚至环路，下面举一个例子来阐述原BATMAN‑Adv协议的机制和产生的问题：

[0007] 如图1(左)所示，假设一个运行了原BATMAN‑Adv协议的网络拓扑中有四个节点，设节点1为源节点，节点1发送OGM消息，通过各节点的计算形成了图1中的各本地TQ值。由左图
中的TQ值大小可以看出，节点4虽然与节点 1是直连的，但是其去往节点1走节点2的路径质
量更优，所以当前节点4向节点1传输数据的最优路径为4‑>2‑>1。图1(右)是某一时刻节点2
突然失效，所有与节点2相关的无线链路都发生了故障，节点4不再能够通过节点2接收来自
节点1的OGM消息，而是直接接收来自节点1的消息。由于快速转发机制的存在，节点4在对外
重新广播OGM的时候，仍然使用这时候的最优TQ值，即 30。那么节点4认为传输数据给节点1
目前最优的下一跳为节点3，同理，节点 3认为与节点1通信的最优下一跳为节点4。那么当
节点4发数据给节点1的时候，数据帧会发给节点3，节点三收到之后再次转发给节点4，这样
数据帧就在节点3、4之间来回传递，直到TTL值变为0，该数据丢失。所以，需要一个避免环
路，增强BATMAN‑Adv协议重收敛性能和降低数据丢失率的方法。

发明内容

[0008] 本发明的目的是解决BATMAN‑Adv协议中路由控制层面在拓扑变更时的重收敛性能不佳问题和对数据层面当下一跳不可达时数据帧会直接被丢弃的做法导致数据丢失的
优化改进，在降低数据丢失率的同时加快了重收敛速度，使数据传输更为稳定。

[0009] 一种面向智能终端自组网的BATMAN‑Adv协议优化设计方法，包括步骤：

[0010] 步骤一：本地节点记录关于任意一个源节点始发的OGM中最新的序列号；当某一节点收到邻居节点发来的始于某一源节点的OGM包，查看其序列号大小，如果该序列号比本地
所记录的关于该源节点的最新消息的序列号小，将该OGM 包丢弃；如果该序列号比本地所
记录的关于该源节点的最新消息的序列号大，将其OGM包中的消息字段中的路径质量度量
值TQ值覆盖在原先这条从该邻居节点到达源节点的路径的TQ值上，完成对该邻居节点到达
源节点的路径质量度量值更新，并转入步骤二；

[0011] 步骤二：将更新之后的该邻居节点到达源节点的路径质量度量值TQlocal与该节点到该邻居节点的路径质量度量值TQOGM进行乘法运算，得到从该节点以该邻居节点为下一
跳，到达源节点的总路径质量度量值，记为TQglobal；并将其写入 OGM包中的消息字段，然后
将该OGM包泛洪转发给其余邻居节点，并转入步骤三；

[0012] 步骤三：重复步骤一和步骤二，该节点分别记录自己的所有邻居节点传来的最新OGM消息字段中的TQOGM值与自身到该邻居的TQlocal进行乘法计算后的 TQglol，选出最大的
TQglobal，并将其对应的邻居节点作为该节点传递给源节点的最优下一跳；当收到通信请求
时，转入步骤四；

[0013] 步骤四：某一节点收到其邻居节点传来的数据帧，查看其目的地址，查询自身路由表中是否有与之对应的路由，如果不存在，将数据帧丢弃；如果存在，按路由进行转发，进入
步骤五；

[0014] 步骤五：若自身与下一跳节点的链接状态正常，则自身的数据转发任务结束；若链路此时为down的状态，数据帧无法传递，则将该数据帧存入缓存，并立即向其所有的邻居节
点通告OGM，该OGM的序列号为最新的，其消息字段的该失效链路的TQ值置为0，转入步骤六；

[0015] 步骤六：等待设定时间，如果在这段时间内，链接状态恢复正常，立即通过该路径将数据帧传递给该下一跳，并立刻向其所有的邻居节点通告OGM，该 OGM的序列号为最新
的，其消息字段的TQ值为按原协议数学算法重新计算的；如果直至最大缓存时间结束，链接
状态仍未恢复正常，则丢弃数据帧。

[0016] 所述设定时间为OGM周期更新时间的四倍。

[0017] 有益效果：本发明在拓扑变更时的控制层面路由重收敛优化和数据层面数据缓存转发机制相结合，能够在网络连接发生波动时进行快速的路由更新同时提高收到的数据的
完整性。

附图说明

[0018] 图1为运行原协议的运行原协议的初始拓扑(左)和节点故障后的拓扑(右)。

[0019] 图2为路径质量度量值更新流程图。

[0020] 图3为数据转发流程图。

[0021] 图4为转发算法演示拓扑图。

[0022] 图5为改进的BATMAN‑Adv协议的TQ值更新及比较算法实例图。

[0023] 图6为改进的BATMAN‑Adv协议在拓扑变更时的反应步骤实例图。

具体实施方式

[0024] 下面结合附图和具体实施例，进一步阐明本发明。

[0025] 本发明通过引入数据帧的缓存机制，结合改进的路径质量度量值更新算法，实现对BATMAN‑Adv协议在路由重收敛及数据传输的网络性能上的优化。首先，在控制层面的路
径质量度量值TQ计算上，不再采用原协议中将丢包造成的TQ 值变化和原先稳定链路的TQ
值进行平均操作的算法，改为将邻居节点发来的最新序列号的OGM包中消息字段的TQ值作
为从该邻居节点到达此OGM源节点的路径质量度量值的参考；其次，在数据层面节点转发数
据帧去往目的地的时候，不再采用原协议中如果此刻下一跳邻居节点为不可达状态，直接
丢弃数据帧的做法，改为将数据帧缓存一段时间的机制。

[0026] 具体步骤如下：

[0027] 步骤一：当某一节点收到邻居节点发来的始于某一源节点的OGM包，查看其序列号大小，如果该序列号比本地所记录的关于该源节点的最新消息的序列号小，即意味着该OGM
包中记录的去往该源节点的路径信息是比本地更旧的，就将该OGM包丢弃；如果该序列号比
本地所记录的关于该源节点的最新消息的序列号大，即意味着该OGM包中记录的去往该源
节点的路径信息是比本地更新的，就将其消息字段中的TQ值覆盖在原先这条从该邻居节点
到达源节点的路径的 TQ值上，完成对该邻居节点到达源节点的路径度量值更新，并转入步
骤二。该路径度量值更新部分如图2流程图所示。

[0028] 步骤二：将更新之后的该邻居节点到达源节点的路径TQlocal值与该节点到邻居节点的TQOGM值进行乘法运算，计算之后的新TQ值便为从该节点以这一邻居节点为下一跳，到
达源节点的总路径质量度量值，记为TQglobal。将该TQ值写入OGM中的消息字段，然后将OGM泛
洪转发给其余邻居节点，并转入步骤三。

[0029] 步骤三：重复步骤一至步骤二，该节点分别记录自己的所有邻居节点传来的最新OGM消息字段中的TQOGM值与自身到该邻居的TQlocal进行乘法计算后的 TQglobal，选出最大的
那个TQglobal，并将其对应的邻居作为数据传递给源节点的最优下一跳，即意味着：自己将数
据传递给该邻居，继而逐跳到达最终接收者的这一路径是最优的。

[0030] 步骤四：重复步骤一至步骤三，每个节点都计算出去往任意其他节点的具有最大TQglobal的路径；当收到数据通信请求时，转入步骤五。

[0031] 步骤五：某一结点收到其邻居节点传来的数据帧，查看其目的地址，查询自身路由表中是否有与之对应的路由，如果不存在，将数据帧丢弃；如果存在，按路由进行转发，进入
步骤六。

[0032] 步骤六：自身与下一跳节点的链接状态正常，数据帧可以顺利传递给下一跳，则自身的数据转发任务结束。如果链路此时为down的状态，数据帧无法传递，则将该数据帧存入
缓存，同时转入步骤七。等待一段时间(设为 MAX_CACHE_TIME，在本发明中，该时间设置视
情况而定，一般设置为OGM 周期更新时间的四倍)：如果在这段时间内，链接状态恢复正常，
立即通过该路径将数据帧传递给该下一跳，同时转入步骤八；如果直至最大缓存时间结束，
链接状态仍未恢复正常，则丢弃数据帧。步骤五、六的数据转发流程图如图3所示。

[0033] 步骤七：立即向其所有的邻居节点通告OGM，该OGM的序列号为最新的，其消息字段的该失效链路的TQ值置为0。邻居节点收到了该OGM后便可得知这一路径失效了，从而数据
传输时不会再使用这条路径。

[0034] 步骤八：立刻向其所有的邻居节点通告OGM，该OGM的序列号为最新的，其消息字段的TQ值为按原协议数学算法重新计算的。

[0035] 具体实施例：

[0036] 假设有模型为N＝(X,L)的网络，其中，X代表一组节点，L代表各对节点之间的链路。对于任意一个包含于N内的节点，都存在一组单跳邻居节点P。假设s代表源节点，d代表
目的节点，如果d∈P，则从源节点s到目的节点d的数据在link(s,d)上传输，link(s,d)∈N；
如果d不属于P，则该数据需要经过多跳传输，其链路由link(s,i)构成，其中i是P中的一个
成员，link(s,i)是链路组L中的一条链路。子网络S＝(X‑{s}，L‑{(s,i),i∈P})。

[0037] BATMAN‑Adv协议的数据转发思路如下：

[0038] (1)在网络N中，假设消息信息m需要从s发到d，删除所有不与源节点在一跳范围内的链路，确定所有与源节点在一跳范围内的链路link(s,i)。

[0039] (2)为每一个链路赋予一个权重wsi，权重wsi表示的是根据在当前滑动窗口从邻居节点i收到的目的节点的源节点消息包的数量，即OGM消息的数量，计算得出的TQ值。

[0040] (3)找到具有最大权重wsi(即TQ值)的那条链路，然后通过这条链路link (s,i)发送消息m。

[0041] (4)如果i不是目的节点，则构建网络子集S，并重复步骤(1)～(4)；直到最后消息m成功到达目的节点d。

[0042] 下面设计一个场景，将数据转发过程进行演示。

[0043] 假设某网络N有五个节点，其网络拓扑图如图4所示，当节点1需要发消息给节点5的时候，其转发过程具体为：

[0044] (1)节点2、3为节点1的邻居节点，则节点1到邻居节点的链路为link(1,2) 和link(1,3)。

[0045] (2)选择两条链路中的权重最高者为最佳链路，假设link(1,3)是最佳链路，则消息m沿此链路发送。

[0046] (3)由于节点3不是目的节点，减少图N为图S。

[0047] (4)考虑节点3与其邻居节点2、4的链路集link(3,2)和link(3,4)。

[0048] (5)选择两条链路中的权重最高者为最佳链路，假设link(3,4)是最佳链路，则消息m沿此链路发送。

[0049] (6)由于节点4不是目的节点，减少图S为图S‘。

[0050] (7)考虑节点4与其邻居节点3、5的链路集link(4,3)和link(4,5)。

[0051] (8)选择两条链路中的权重最高者为最佳链路，假设link(4,5)是最佳链路，则消息m沿此链路发送。

[0052] (9)节点5是目的节点，数据转发过程完成。

[0053] 本发明对BATMAN‑Adv协议的优化改进在控制层面便体现在上述过程中的权重计算和路由更新上，下面具体解释路径质量度量值TQ的更新算法和路由更新机制。

[0054] 对于任意一个源节点o，任一本地节点记录下了关于o的最新的序列号，用 S(o)表示。因为S(o)可能会从邻居列表中的任意一个下一跳节点中获得，用Sx(o)来表示从邻居节
点x获得的关于该源节点的最新序列号。可以得到：

[0055] S(o)＝max(Sx(o))

[0056] 改进后，通过邻居节点x到达源节点o的TQ值为从x接收到的最新序列号的TQ值。将这个TQ值与本地节点到邻居结点x之间链路的TQ值按原协议的数学算法进行乘运算，得出
的最终TQ值便为从本地节点以邻居节点x为下一跳，最终到达源节点o的总路径质量度量
值，并将其赋值给该路径权重w。当本地节点收到去往o的数据帧，比较其以每个邻居结点为
下一跳，最终到达源节点o 的总路径权重值，选择出最大的路径权重，以该条路径进行数据
转发。

[0057] 下面设计一个场景，将改进的BATMAN‑Adv协议的TQ值更新及比较过程进行演示。

[0058] 如图5所示，已经记录的关于节点1的最大序列号中的TQ值如下：link(2,1) 的TQ＝3，link(3,1)的TQ＝2，link(4,2)的TQ＝4(Seq＝100)，link(4,3)的 TQ＝3(Seq＝98)。假
设节点4从节点2收到了一个新的OGM包，其中序列号为 101，TQ＝5，由于新OGM包的序列号
101大于当前记录的以节点2为下一跳去往节点1的最大序列号100，所以节点4会对以节点2
为下一跳去往节点1的链路link(4,2)的TQ值进行更新，更新之后的TQ值为5。假设节点4又
从节点 3收到了一个新的OGM包，其中序列号为97，TQ＝4，由于新OGM包的序列号 97小于当
前记录的以节点3为下一跳去往节点1的最大序列号98，所以节点4 直接丢弃该OGM包，不对
TQ值作更新。

[0059] 现在节点4想要传数据给节点1，假设经原协议中的整体路径质量度量值算法计算后，节点4以2为下一跳最终到达节点1的总TQ为14，节点4以3为下一跳最终到达节点1的总
TQ为5，则赋予各链路权重w21＝3，w31＝2，w42＝14， w43＝5。此时节点4传递数据给节点1，先
对link(4,2)的权重w42和link(4,3) 的权重w43进行比较，经比较w42更大，所以节点4选择将
数据传递给节点2；节点2收到数据后，也会比较它到目的节点1的所有路径的权重w，该例节
点2到节点1只有一条路径link(2,1)，所以节点2将数据直接交付给节点1，完成数据传递过
程。

[0060] 下面设计一个场景，将改进的BATMAN‑Adv协议在发生拓扑变更时的反应过程进行演示。

[0061] 如图6所示，假设在之前的例子中，节点2到节点1的连接由于某些原因中断了，那么经改进的BATMAN‑Adv协议会在数据层面和控制层面进行如下反应：

[0062] 首先，在数据层面，如果此时节点2仍需转发节点4的数据给节点1，节点 2不会因为节点1此时不可达而立即丢弃数据帧，而是将数据存入缓存中，等待一个最大缓存时间
(MAX_CACHE_TIME，可根据实际情况进行设置)，如果在这段时间内，节点2到节点1的连接恢
复正常，则节点2立即将数据帧发送给节点1；如果直到最大缓存时间结束，节点2到节点1的
连接仍未恢复正常，则节点2将数据帧丢弃。

[0063] 其次，在控制层面，无论是节点2由于连接问题检测到节点1不可达，还是节点2在缓存时间内检测到连接恢复正常，节点2都会立刻向周围的邻居广播一个新的OGM。

[0064] 在此例中，节点2到节点1不可达的情况下，节点2即立刻向节点4广播 OGM，该OGM的序列号为最新的，消息字段的TQ值置为0。节点4收到了这类OGM后，便可迅速计算出通过
节点2去往节点1的总路径TQ为0，即这条路径不可到达节点1，此时去往节点1走下面的以节
点3为下一跳的路径为优，数据便通过节点3转发给节点1。

[0065] 另一种情况，节点2在缓存时间内检测到连接恢复正常，节点2即立刻向节点4广播OGM，该OGM的序列号为最新的，消息字段的TQ值为重新计算的。节点4收到了该OGM后，便重
新计算去往节点1的各路径TQ值，选出最大的，今后发送数据去往节点1时优选TQ最大的那
条路径。

[0066] 本说明书中未作详细描述的内容属于BATMAN‑Adv协议的现有算法和功能。

[0067] 本技术方案适用于Ad hoc网络，弥补了现有BATMAN‑Adv协议在拓扑变更后重收敛上性能表现不佳的弊端。

[0068] 本发明创造的主要保护技术点：

[0069] (1)改进了BATMAN‑Adv协议的路径质量度量值的更新机制。

[0070] (2)控制层面与数据层面相结合，增加了数据帧的缓存机制和拓扑变更时的快速重收敛机制，降低了数据的丢失率，提高了传输质量。

[0071] 以上详细描述了本发明的优选实施方式，但是本发明并不限于上述实施方式中的具体细节，在本发明的技术构思范围内，可以对本发明的技术方案进行多种等同变换(如数
量、形状、位置等)，这些等同变换均属于本发明的保护。