基于增量信息最小化控制开销的OLSR 路由协议

◆崔忠林 王衡 胡春

（1.中国电子科技集团公司第三十八研究所 安徽 230000；2.空装驻合肥地区第一军事代表室 安徽 230000；3.重庆邮电大学 通信与信息工程学院 重庆 400065）

随着近年来军事朝着无人化，智能化方向发展，传统的移动自组织网络越来越受到重视[1]。其中高效组网协议是研究的重点部分，移动自组网网络层路由协议分为先验式路由和反应式路由[2]，OLSR 路由协议是先验式路由协议的代表。由于先验式路由在本地具有全局拓扑信息，因此OLSR 路由协议具有时延低，适用于节点密度高的场景[3]。由于OLSR 路由协议需要依靠广播控制消息来维持全网的拓扑信息，其中每个节点都定期广播HELLO 消息，部分节点全网洪泛TC 消息，随着网络规模扩大和节点密度的增加，网络的控制开销会快速增加，信道利用率快速减小[4-8]。对于减少OLSR 协议的控制开销，针对这个问题，文献[9]提出了将OLSR 将应用在无线网格网络中，通过自适应地最大化广播消息间隔，最小化路由开销，但是该协议只适用于低动态网络。文献[10]提出了利用博弈论减小OLSR 控制开销，发送和接受控制消息时，每个节点都策略性的更新消息，但是该协议只能保证平均吞吐量不变。文献[11]提出了在计算MPR 时，将三跳邻居信息加入MPR 计算决策，但是该协议，没有保证MPR集最小。文献[12]提出了通过动态地调整刷新间隔的值，但是该机制在高动态环境下性能不如预期。

针对OLSR 路由协议控制开销大，本文提出一种基于增量信息机制的OLSR 协议（incremental information OLSR，II-OLSR）。

1 OLSR 路由协议的问题

目前OLSR 协议定期发送的HELLO 和TC 消息中，含有大量冗余信息，下面详细介绍这个问题。

1.1 控制包冗余信息

由于OLSR 路由协议的网络拓扑的构建需要依靠HELLO 消息定期广播和TC 消息定期洪泛。如图 1 所示，以1 号节点为例，广播的控制消息包含一跳邻居信息，当5 号节点新加入网络时，控制消息内容中增加5 号节点信息，当5 号节点脱离网络时，控制消息内容中去除5 号节点信息。由于1 号节点一跳邻居都广播控制消息，导致信道被大量控制消息占用。由于广播的控制信息中含有大量冗余消息，如果1 号节点一跳邻居没有发生变化，定期发送的控制消息都是相同的，严重增加控制开销。

图1 网络拓扑模型

1.2 广播包丢失

OLSR 路由协议的HELLO 消息和TC 消息主要是以广播传输的，由于广播包没有ACK 机制，无线信道的传输特性较差，广播包大小影响接收成功率。由于OLSR 协议存在大量冗余信息导致控制包接收成功率较低。

2 改进协议II-OLSR 介绍

针对OLSR 协议控制包存在冗余信息和广播包发送成功率低，提出一种基于增量信息的控制包发送机制。

2.1 机制一：增量HELLO 消息

HELLO 消息发送间隔为THELLO，由于接收节点对HELLO 消息内容的保存时间为3THELLO，当网络拓扑长时间不发生变化时，发送空包表示一跳邻居没有发生变化。

当一跳邻居发生变化，如图 2 所示，4 号节点为新加入节点，1号节点发现一跳邻居节点有新节点，发送正常的HELLO 消息进行邻居感知，当1 号节点完成邻居感知，在后面连续3 个HELLO 消息发送只发送增量信息4，告知2 号和3 号节点一跳邻居变化。

图2 新增一跳邻居节点

当有一跳邻居脱离，在之后发送的3 个HELLO 消息为正常的HELLO 消息，包含完整的一跳邻居信息。

关于该机制一跳邻居发生变化连续发送3 个周期HELLO 消息的说明：如果连续3 个周期邻居节点收到广播消息发生错码，导致接收失败。则邻居节点将从本地去除该节点的信息。再次进入邻居感知过程。

通过该机制保证在网络拓扑变化缓慢时，只需交换增量信息，大幅减少HELLO 控制开销。

2.2 机制二：新增TC 消息

由于TC 消息需要进行全网泛洪，控制开销随着节点数增加，呈现指数增长，因次减少TC 消息包长能够有效减小控制开销。

TC 消息发送间隔为TTC，接收节点对TC 消息保存时间为3TTC。

当网络没有新入网节点，且节点需要发送的TC 消息不变时，如图 3 所示，在接下来发送的2 个空包TC 消息，表示拓扑没有变化，发送的第3 个 TC 消息为正常的TC 消息，包含完整的拓扑信息。

图3 TC 消息维护阶段

当网络有新入网节点或TC 消息的减少时，如图4 所示，接下来发送2 个完整的TC 包，保证新入网节点能够及时掌握全网拓扑，之后转入正常的维护阶段。

图4 新入网节点或TC 内容减少更新阶段

当TC 消息的内容增加时，如图5 所示。

图5 本地TC 消息更新阶段

3 理论性能分析

II-OLSR 协议是通过减小控制开销，提高信道利用率，使改进后的OLSR 协议在控制开销，发包成功率，吞吐量和时延得到明显改善，具体分析如下：

3.1 控制开销分析

定义：M 为节点密度，V 为节点移动速度，P 为控制开销，R 为网络拓扑变化率。

II-OLSR 协议发送控制包分为3 种种类：

（1）网络拓扑信息增加时，用发送增量信息代替发送完整信息，减小控制开销。

（2）网络拓扑不变时，发送空包维持拓扑不变，减少了控制开销。

（3）网络拓扑发生过期时，发送完整信息，通知周围节点更新拓扑，控制开销保持不变。

改进协议的控制开销由上述3 类组成，如公式1 所示，

由于种类（1）、（2）控制开销比原协议小，因此有PII-OLSR≤POLSR。

引理1：当节点速度V 越小，网络的拓扑变化率R 越小。

当节点密度M 越大，节点速度V 越小时，网络开销Pa和Pb越小，网络总开销越小。

3.2 发包成功率和吞吐量分析

定义：S 为发包成功率，L 为信道利用率，F 为网络层数据量，H 为吞吐量，I 为业务数据量。

引理2：当MAC 层和物理层保持不变时，信道利用率L 和网络层向下发送的数据量F 成正向关系。

网络层数据量F=P+I。

当网络层数据量保持不变时，由于II-OLSR 协议减少了控制开销P，因此提高了业务数据量，增加了网络的吞吐量。

当业务数据量I 保持不变时，由于II-OLSR 协议减少了控制开销P，减小了F，降低了信道利用率，由于信道拥塞减小，提高了发包成功率。

3.3 时延分析

时延D ∝（S ∗K）其中K 为信道负载。由于改进后的协议大幅度减小控制开销的发送，使得信道负载K 得到减轻，同时由于发包成功率S 增加，改进的协议减小了网络时延特性。

4 仿真验证

取II-OLSR 和OLSR 作为比较对象，通过仿真比较分析他们在发包成功率，时延，控制开销，吞吐量等重要指标。

4.1 仿真参数设置

使用Windows XP 平台上的OPNET 仿真软件对OLSR 和II-OLSR 协议进行仿真。设置了在4 个仿真场景，分别为20，40，60，80 个节点在10km*10km 的矩形区域均匀分布，节点最大移动速度为50m/s，最大通信距离2km。仿真参数如表格 1 所示，MAC 层使用IEEE802.11a 标准。每个场景实验做5 次，取平均值。

表1 仿真参数设置

4.2 仿真结果及分析

4.2.1 控制开销

在20，40，60，80 个节点的场景中，控制开销对比如图 6，OLSR协议的控制开销为：25.1Mb，99.3Mb，120.5Mb，175.7Mb，II-OLSR协议的控制开销为：23.8Mb，91.8Mb，107.6Mb，150.7Mb，分别减少4.9%，7.2%，10.3%，14.2%；改进协议相比原始协议控制开销有较明显的较少，而且在节点密度高的场景下，改善越明显，符合理论分析。

图6 控制开销比较

4.2.2 时延

从图 7 可以看出，在20，40，60，80 个节点的场景OLSR 协议的平均时延分别为：2.1ms，3.9ms，6.0ms，6.3ms，II-OLSR 协议的平均时延为：1.9ms，3.9ms，5.9ms，6.3ms。改进协议相比原始协议时延有明显改善，符合理论分析。

图7 时延比较

4.2.3 发包成功率

从图8 可以看出，在20，40，60，80 个节点的场景OLSR 协议的发包成功率为：0.94，0.89，0.85，0.81，II-OLSR 协议的发包成功率为：0.98，0.93，0.92，0.87。相较于原协议，II-OLSR 协议发包成功率分别提高了0.04，0.04，0.07，0.06，改进后的协议在发包成功率得到明显改善。

图8 发包成功率比较

4.2.4 吞吐量

从图 9 可以看出，在20，40，60，80 个节点的场景OLSR 协议的吞吐量为：2.00Mbps，1.95 Mbps，1.7 8Mbps，1.64 Mbps，II-OLSR协议的吞吐量为：2.15 Mbps，1.95 Mbps，1.84 Mbps，1.75 Mbps 。相较于原协议，II-OLSR 协议吞吐量分别提高了0.15 Mbps，0.11 Mbps，0.06 Mbps，0.11 Mbps。由于减少了控制开销，改进后的协议在吞吐量得到明显改善。

图9 吞吐量比较

4.2.5 移动速度对控制开销的影响

分别统计节点在最大移动速度10m/s，20m/s，30m/s，40m/s，50m/s，在节点数为40 个时控制开销情况，如图 10 所示，当节点速度越快，网络拓扑变化越剧烈，II-OLSR 协议减少的控制开销越小，说明该协议在低动态网络场景中更加适用。

图10 节点速度对控制开销的影响

5 结束语

本文提出来一种基于增量信息最小化控制开销的OLSR 路由协议（II-OLSR 路由协议），通过去除控制开销信息中的冗余信息，用发送增量信息代替发送完整信息，减少了控制开销。由于控制开销的减小，在相同的负载情况下，提高了信道的吞吐量。在相同网络吞吐量的情况下，由于控制开销减少，信道负载更加小，降低了发包时延，提高了发包成功率。经仿真实验表明：新提出的协议能够减小控制开销，提高发包成功率和网络吞吐量，减小端到端时延，提高了OLSR路由协议性能。在未来工作中，将深入研究节点移动速度的问题，解决II-OLSR 路由协议在高动态场景的性能表现。