优化链路状态路由协议的低开销拓扑维护算法

任 智，周 舟，吴本源，陈加林

（重庆邮电大学通信与信息工程学院，重庆 400065）

0 概述

移动自组织网络（MobileAd Hoc Network，MANET）是一种移动无线设备的自配置动态网络［1］，其由一些可自由移动的节点构成，这些节点间通过无线连接进行通信，不需要任何基础网络架构。在MANET中，节点可以任意改变移动的方向和自身位置，使整个网络呈现一种动态的网络拓扑［2-3］。由于MANET路由协议能实现网络的自我创建、组织和管理而无需人为参与，因此其被广泛应用于车联网、无人机和物联网等领域［4-6］。

优化链路状态路由（Optimized Link State Routing，OLSR）协议是一种分布式主动路由协议［7］，其通过在一跳邻居范围内选取多点中继（Multipoint Relay，MPR）节点来减少拓扑控制消息的发送和转发，进而通过HELLO 和拓扑控制（Topology Control，TC）消息发送来实现链路状态和拓扑信息的全网分发［8］。OLSR 协议需要频繁地交换控制信息以维持全网拓扑更新。相比动态源路由（Dynamic Source Routing，DSR）协议和无线自组网按需平面距离向量（Ad Hoc On-Demand Distance Vector，AODV）路由协议，OLSR 协议具有更高的网络吞吐量和更低的端到端时延，因此适用于网络规模大、节点数目多的大型密集网络［9-11］。

为解决OLSR 协议拓扑发现和维护过程中开销过大的问题，文献［10］将MPR 集的选择依赖条件扩展到三跳邻居的本地数据库，每个MPR 候选节点都被赋予新的信息来进行MPR 的选取，从而进一步减少TC 消息的冗余转发。文献［12-13］提出使用全局最优MPR 集代替局部最优MPR 集，优先将已经被其他节点选为MPR 的一跳邻居节点选为MPR 节点，在不增加控制开销的前提下减少网络中TC 消息的数量。文献［14］将传统MPR 选择和蚁群算法相结合，在MPR 集选取过程中添加信息素并引入补偿-惩罚规则，将节点的当前移动状态信息加入计算过程，有效地降低了MPR 集中的冗余。

在稳定性方面，文献［15］提出一种启发式MPR选择算法，节点间通过HELLO 消息交互移动状态，优先选择移动性较小的节点作为MPR 节点，提升链路的保持时间。文献［16］在HELLO 包中加入节点的位置信息，在MPR 选择时考虑链路稳定性，减少MPR 节点切换次数，增加路由表项的有效时间。PRAJAPATI 等［17］在MPR 集选择过程中引入能量因素，优先将剩余能量高的节点选为MPR 节点，在一定程度上延长网络整体寿命，但选出的MPR 节点个数不是最少的。

文献［18］基于OLSR 协议提出一种残差预测优化链路状态路由（HTR-OLSR）协议，在相邻节点的状态信息未知时，引入残差预测算法，从其他节点获取所需信息，并将原始协议中的HELLO-Interval 和TC-Interval 分别下调到1 和3。通过频繁获取节点数据信息来降低节点能量级预测时的不准确性。该算法在一定程度上提高了节点寿命和网络吞吐量，但增大了网络开销。

OLSR 协议通过广播机制发现节点间链路信息和网络拓扑可能产生的冗余重传和无线电资源浪费等问题，SOUIDI 等［19］提出一种基于地理转发规则的OLSR 协议。该协议使用节点的地理位置信息将网络分为不同的虚拟区域，在广播控制消息时避免其在不同区域间重复传输。该算法有效减少TC 消息的冗余传播，但区域划分和区域间通信增加了算法实现的复杂度。

本文提出一种针对优化链路状态路由的低开销拓扑维护（Low Cost Topology Maintenance based on Optimized Link State Routing，LCTM-OLSR）算法。该算法去除MPR 集选取时存在的冗余，进而根据节点MPR 选择集的变化情况，在稳定量与变动量之间截取最小量作为TC 消息内容进行发送。在此基础上，利用历史变动信息动态调整TC 消息的发送间隔，实现网络拓扑的低开销维护。

1 OLSR 协议的拓扑发现与维护机制

通过周期性地泛洪TC 消息以实现OLSR 协议的拓扑发现和维护，相比传统LSR 协议，OLSR 协议提出的MPR 机制极大地减少了TC 消息的发送内容和转发数量。由于节点的TC 消息需要在全网范围内转发，因此发送TC 消息造成的开销将直接影响网络性能。

1.1 TC 消息的产生及其交互机制

TC 消息发送前需进行MPR 集的计算，传统OLSR 协议中每个节点独立进行MPR 集的选取，选取过程应遵循以下规则：1）源节点的MPR 集应当只能从本节点的一跳对称邻居中选取；2）选择出来的MPR 集能覆盖本节点所有的两跳邻居，并且MPR 集中的元素个数要尽可能少。

OLSR 协议中只有当节点的MPR 选择集不为空时才允许发送TC 消息，消息内容为MPR 选择集中节点的地址。整个网络中所有的节点都能接收并处理该消息，但是只有MPR 节点才能转发TC 消息。参照RFC3626［8］相关协议规范，TC 消息的收发和相关处理流程按如下步骤进行。

步骤1节点判断自己的MPR 选择集是否为空，当其不为空时，将MPR 选择集中的内容加入到TC 消息的消息体中进行广播。

步骤2当节点收到TC 消息后，如果重复表中有一个表项的消息源地址与TC 消息的源地址相同，并且其消息序号大于等于当前TC 消息的消息序号，说明已经处理过更新的TC 消息，则丢弃该消息不作处理，否则，执行步骤3。

步骤3如果拓扑表中存在表项的“T_last”与TC 消息源发送者的地址相同并且对应的序号大于TC 消息中的序号，表明该消息已过期，丢弃不作处理，否则，执行步骤4。

步骤4如果拓扑表中存在表项的“T_last”和TC 消息的源发送者地址相同，则按TC 消息中的内容对其进行更新；否则，添加新的条目，其“T_last”为TC 消息的源地址，“T_dest”为TC 消息的内容部分。

步骤5当TC 消息的上一跳地址在MPR 选择集中并且消息中的“TTL”字段的值大于等于1 时，先将该字段的值减1，进而将该TC 消息进行广播转发。

1.2 问题描述

在OLSR 的拓扑维护过程中，节点在收到HELLO 消息后计算自己的MPR 集，当TC 消息发送定时器到期时，对自己MPR 选择集中的地址进行广播，被其MPR 节点进一步转发，直至全网，从而实现了节点本地拓扑信息的全网通告。

1.2.1 传统MPR 选择算法

在OLSR 协议中，MPR 集是采取贪心策略进行计算的，每个节点依次将那些连接两跳邻居数目最多的一跳邻居加入MPR 集，直到选出的MPR 集能够覆盖所有两跳邻居为止。广播中继泛洪如图1 所示，节点S 按传统MPR 选择算法计算的MPR 集为｛b，c，d，f｝，而实际最小MPR 集为｛b，d，f｝，存在冗余。由于只有MPR 节点才能发送和转发TC 消息，因此MPR 集中元素增加将会导致更多的节点发送TC 消息，以及TC 消息的转发次数会增多，从而造成控制开销增大。

图1 广播中继泛洪示意图Fig.1 Schematic diagram of broadcast relay flooding

1.2.2 TC 消息冗余发送

OLSR 协议中由于TC 消息的发送周期固定，并且每个周期发送的内容相互独立，因此可能造成拓扑信息冗余发送和带宽资源浪费。拓扑变动前后对比如图2 所示。

图2 拓扑变动前后对比Fig.2 Comparison before and after topology change

从图2 可以看出，带有阴影部分的节点为该网络拓扑下的MPR 节点，只有这些节点才产生和转发拓扑控制消息。根据图2 中拓扑变动前后关系计算每个节点的MPR 选择集如表1 所示。

表1 拓扑变动前后节点的MPR 选择集Table 1 MPR selection set of nodes before and after topology change

从图2 和表1 可以看出，当网络拓扑变化时网络中MPR 集的依赖关系也会相应改变。相比网络拓扑变动前，节点A 的MPR 选择集增加了一个元素；节点D 改变了一个元素；节点B 和节点E 的MPR 选择集保持不变。按照OLSR 原始协议的TC 发送流程，节点A 当前发送的TC 消息中将包含｛B，C，D，E，F，H｝的地址，其中｛C，D，E，F，H｝在上一周期中已经发送过，因此重复发送将导致网络带宽浪费；节点D的MPR 选择集变化较小，如果全部发送则会造成网络控制开销增大。

原始协议中TC 消息采用固定周期进行发送，将导致以下两方面的问题：1）当网络拓扑变动时，固定的发送间隔不能及时将拓扑变动通告全网，可能导致网络拓扑更新不及时使丢包率增大；2）当节点周围网络拓扑较稳定时，较短的发送周期将会导致网络控制开销和端到端时延增大。

2 LCTM-OLSR 算法

为了解决上述问题，本文提出一种低开销的LCTM-OLSR 算法。该算法首先去除传统MPR 选择算法中存在的冗余，减少了TC 消息的产生数量和转发次数；其次LCTM-OLSR 算法根据网络拓扑的变动情况自适应地上下调整TC 发送间隔以实现网络拓扑维护，并且当节点周围拓扑变动较小时，采用发送变量信息代替全量信息以减少拓扑信息的冗余发送。

2.1 算法流程

综上所述，本文提出一种低开销的拓扑维护算法，该算法流程如图3 所示。

图3 LCTM-OLSR 算法流程Fig.3 Procedure of LCTM-OLSR algorithm

LCTM-OLSR 算法先通过最小MPR 选择机制，将一跳邻居按照连接度从小到大实行退出MPR 选择，进而将关键的一跳邻居节点依次加入MPR 集，去除传统MPR 选择算法中存在的冗余。在当前MPR 选择集不为空时，节点判断当前MPR 选择集和上一发送周期相比是否变动，相应地发送TC_KEEP、TC_NORM、TC_DEL 消息，并动态地调整发送周期的大小，从而降低网络拓扑信息的冗余发送，提高网络的适应能力。

LCTM-OLSR 算法在控制开销较少的情况下使网内的每个节点掌握全网的拓扑信息，由于无线信道的特性，易受到干扰而丢包，可能造成部分TC 消息丢失而产生错误迭代。因此在每隔5 个TC 发送周期后，需发送一次正常的TC 消息，即TC 重置消息，进行全网拓扑矫正。当有新节点加入时，由于只能获取部分网络拓扑信息，当其有数据进行传输时可先将数据包发送至MPR 邻居，然后由MPR 邻居转发至全网，待TC 重置消息到来后便可获得全网拓扑进行正常流程通信。

2.2 算法设计

为了使全网节点掌握自身的拓扑信息，网络中的MPR 节点会周期性地泛洪TC 消息，消息内容由所有将自己选为MPR 一跳邻居的地址组成并且只能由该节点选择的MPR 节点转发。

2.2.1 最小MPR 集选择机制

传统MPR 选择算法采用贪心策略计算MPR集，以一跳邻居连接的两跳连接度作为MPR 选择的唯一依据，没有考虑反向两跳邻居和一跳邻居间的关联性，可能产生冗余的MPR 节点，影响网络性能。广播中继泛洪拓扑扁平化如图4 所示。

图4 广播中继泛洪拓扑扁平化Fig.4 Topological flattening of broadcast relay flooding

在上述分析的基础上，本节提出一种最小化的MPR 集选取策略，以图4 为例最小化MPR 集的选择步骤如下：

第一，中英两国文化的差异。 由于地理位置、历史等诸多方面的原因，中英两国的文化在民族思想、宗教信仰、价值观念、习俗等方面有着巨大差异。 基督教对英国的文化有着很大的影响，而对中国文化产生重大影响的宗教是佛教。 中国文化体现出群体性的特征，往往是不允许个人价值凌驾于群体利益之上的。 但是，英国文化体现出个体性的特征，即崇尚个人价值，宣扬个人主义，竭力表现自我和发展自我。

步骤1统计一跳邻居和两跳邻居的连接关系，可得f=｛H｝，a=｛A，B｝，b=｛A，B，C，D｝，c=｛B，C，D，E，F｝，d=｛E，F，G｝，e=｛G｝，g=｛｝。根据连接两跳邻居的个数从小到大将一跳邻居进行排序并删除连接度为0 的节点，可得排序后的一跳邻居为N1(i)=｛e，f，a，d，b，c｝。

步骤2对两跳邻居N2(i)=｛A，B，C，D，E，F，G，H｝分别计算其连接一跳邻居的数目，得关联度Link=｛2，3，2，2，2，2，2，1｝。

步骤3如果N2(i)为空，则执行步骤5；否则将N1(i)中的节点按从左到右的顺序试着退出MPR 的选取，判断将该节点连接N2(i)中节点对应的Link 数组中的计数值减1 后，对应元素减完后的值是否都大于等于1。如果是，说明该节点为冗余节点，将其从N1(i)中剔除，Link 数组中对应的元素减1，并继续执行步骤3；否则执行步骤4。

步骤4将该节点加入MPR 集并将其从N1(i)中剔除，将该节点连接的两跳邻居从N2(i)中剔除，继续执行步骤3。

步骤5此时N2(i)为空，最小MPR 集计算结束。

步骤3 将一跳邻居按连接度从小到大的顺序尝试退出MPR 集选取，针对图4 中的拓扑，一跳邻居g、e、a、c 依次退出MPR 的选取，节点f、d、b 依次被选为MPR节点，此时选出的MPR 集｛b，d，f｝是最小MPR 集。

2.2.2 TC 消息自适应发送机制

TC 消息自适应发送机制分为发送内容自适应发送机制和发送周期自适应发送机制。

在自组织网络中，当前TC 发送周期的MPR 选择集由在上一发送周期的MPR 选择集的基础上减去删减量再加上新增量组成，如式（1）所示：

其中：ξlast为上一周期MPR 选择集中的内容；ξkeep、ξadd和ξdel分别为当前MPR 选择集相较于上一周期的不变、增加和删减部分，ξkeep=ξcur∩ξlast。由式（1）可知，当网络拓扑变动不剧烈时，当前TC 消息内容和上次发送的内容会有较大的冗余，如果重复发送会造成较多的网络带宽浪费。针对此问题，LCTM-OLSR 算法提出了TC 内容自适应发送机制，改进后TC 消息内容如式（2）所示：

当前周期TC 消息内容可根据网络拓扑的变动情况而动态调整，按MPR 选择集的变动情况将TC消息分为3 种类型，具体发送步骤如以下2 种情况：

（1）当节点周围拓扑发生变动时，如果ξdel<ξkeep，则由删减量和新增量组成TC_DEL 消息进行发送；反之，则由不变量和新增量组成TC_NORM 消息进行发送。

（2）当节点周围拓扑保持不变时，发送消息体为空的拓扑保持消息TC_KEEP，节点接收该消息后更新拓扑表项的生存时间。

为适应改进机制变动，TC 消息包格式将Reserved 字段划分为TC_Type 和Del_len 两部分，分别表示当前TC 消息的类型和消息体中前Del Len 个地址为删减部分，其中Del_len 字段的值在消息类型为TC_KEEP 和TC_NORM 时为0，改进后的TC 消息格式如图5 所示。

图5 改进后的TC 消息包格式Fig.5 Improved TC message packet format

对比图2（a）和图2（b）的拓扑变动，在变动后原始协议和改进协议发送的TC 消息内容如表2所示。

表2 拓扑变动后原始和改进协议TC 消息内容Table 2 Original and improved protocol TC messages after topology change

从表2 可以看出，拓扑变动后只有A、B、D、E 4 个节点的MPR 选择集不为空，按原始协议它们需要将自己MPR 选择集中的地址装入TC 消息中发送出去。按照改进机制，节点D 的MPR 选择集的减少量为｛E｝，不变量为｛A，K，M｝，增加量为｛C｝，减少量小于不变量，故D 节点当前发送内容为｛E，C｝；同理，节点A 只需发送增加量｛B｝，节点B 和E 的MPR选择集没有发生变化，只需要发送消息体为空的TC_KEEP 消息即可，有效地降低了拓扑维护时的控制开销。

2）TC 消息周期自适应发送机制

在RFC3626［8］中，OLSR 协 议TC 消息的 发送周期为恒定值Tmid=5 s，当网络拓扑变动较频繁时，不能及时更新网络拓扑信息而导致丢包率增大；当网络拓扑较稳定时，较短的发送周期将导致网络控制开销增大，因此固定TC 发送周期不能很好地适应自组织网络中网络拓扑的变动。

基于此，LCTM-OLSR 算法将当前TC 发送间隔（TC Emission Interval，TCEI）以原始发送周期5 s 为中点划分为5 个层级，从小到大依次为Tmin、Tless、Tmid、Tlong、Tmax，并且网络拓扑变动越频繁，TC值设置得越小，由历史上的发送周期大小和链路信息保持状态综合决定当前TC 消息的发送频率。其中，触发TC 消息发送周期变动的条件为：

（1）当节点MPR 选择集变动，即MPR 选择集增加或减少元素时，如果上一次的发送周期表明历史上至少一个周期内节点周围网络拓扑未变动，此时网络正由较稳定转变为不稳定状态，下一次的发送周期应重置为；否则在的基础上下降一个层级。

（2）当节点MPR 选择集在一个发送周期内维持不变时，如果此时，表明历史上节点周围拓扑较不稳定，并且此时网络正由不稳定向稳定状态转变，则下一次发送周期应该重置为Tmid；否则在的基础上上调一个层级。

在拓扑关系变动时，为了使网络中其他节点感知到拓扑改变，MPR 节点应尽快将改变后的拓扑信息发送出去。TC 消息快速发送时间分析如图6所示。

图6 TC 消息快速发送时间分析Fig.6 Analysis on the fast sending time of TC messages

从图6 可以看出，t1为上次发送TC 消息的时间，t2为当前时间，t3为当前时间加上变动后TC的时间点，t4为预计下次发送时间。假设节点在t2时刻MPR选择集发生改变，按LCTM-OLSR 算法将TC 下一周期发送时长下调一级，如果t3

2.3 LCTM-OLSR 算法的性能分析

在自组织网络中由于网络拓扑的动态变化，影响网络性能指标的因素主要有网络中节点的总数、节点的发包速率、包的大小、节点的移动速度等［20］。在OLSR 协议中，路由信息主要通过节点周期性地交互HELLO 和TC 消息来进行更新维护。网络相关运行参数的定义如下：

N：整个自组织网络中节点的总数；

NMS：网络中选取MPR 节点的总数，其值与网络规模N 和MPR 选择算法相关；

Nm：网络中每个节点平均选取MPR 节点的个数；

Shello：发送的HELLO 消息的单条平均长度；

STC：发送的TC 消息的单条平均长度；

Thello：HELLO 消息的发送周期；

TTC：TC 消息的发送周期。

因此，自组织网络运行时网络中某个节点i在单位时间内总共产生的HELLO 消息长度如式（3）所示：

同理，MPR 节点j单位时间内可产生TC 消息的长度如式（4）所示：

考虑到多点中继，同一条TC 消息需要向其Nm个MPR 邻居节点进行转发，因此在单位时间内MPR 节点j需转发总的TC 消息长度为：

只有MPR 节点才产生和转发TC 消息，那么单位时间内整个自组织网络所产生的总路由开销为：

由式（6）可知，降低HELLO 和TC 消息的长度或减少网络中MPR 节点个数均可以降低OLSR 协议的控制开销。本文提出LCTM-OLSR 算法采用TC 消息自适应发送的方法降低了STC，增大了TTC，并且最小MPR 集选择机制有效地减少了网络中MPR 节点的个数，有效地降低了OLSR 协议拓扑维护的控制开销，提升了网络的吞吐量。

3 实验与结果分析

选取标准OLSR协议，参考文献［18］中的HTR-OLSR协议与本文的LCTM-OLSR 协议作为分析比较对象，通过仿真实验对比分析它们之间的发包成功率、端到端时延、吞吐量。

3.1 仿真参数设置

本文使用Windows XP 平台上OPENT Modeler 14.5 仿真软件，对OLSR、HTR-OLSR 和LCTM-OLSR协议进行仿真对比，设置5 个仿真场景。假设实验中每个节点的发射和接收功率都相同，节点的最大通信距离为200 m，TC 消息的发送周期变动范围｛Tmin，Tless，Tmid，Tlong，Tmax｝在本次仿真实验中分别设置为｛3 s，4 s，5 s，6 s，7 s｝。仿真具体参数如表3 所示，本实验每个场景实验做5 次，取实验结果的平均值，主要考察不同移动速度对网络性能的影响。

表3 仿真参数设置Table 3 Simulation parameters setting

3.2 仿真结果分析

3.2.1 吞吐量

OLSR、HTR-OLSR 和LCTM-OLSR 算法的吞吐量对比如图7 所示。LCTM-OLSR 算法的吞吐量比文献［18］中的HTR-OLSR 算法平均提高了7.84%，比标准OLSR 平均提高了10.14%。因最小MPR 选择算法减少了MPR 节点个数，从而减少了TC 消息的发送和转发次数，同时TC 自适应发送机制通过对发送内容进行优化，减少了网络控制开销，提高了吞吐量。当节点速度加快时，网络拓扑变动加快，数据包丢失概率增大，吞吐量明显下降。此时LCTMOLSR 算法会自适应地降低TC 消息发送间隔，及时更新变化后的网络拓扑，进而提高数据包接收的成功率；并且该算法TC 数据包比其他两种算法小，有效降低了冗余拓扑信息的传输，所以在节点移动速度加快时，该算法相较于其他两种算法能够一直维持较高的网络吞吐量。

图7 OLSR、HTR-OLSR 和LCTM-OLSR 算法吞吐量对比Fig.7 Throughput comparison of OLSR，HTR-OLSR and LCTM-OLSR algorithms

3.2.2 端到端平均时延

OLSR、HTR-OLSR 和LCTM-OLSR 算法的端到端时延对比如图8 所示。改进后的LCTM-OLSR 算法具有更低的端到端传输时延，相比HTR-OLSR 算法平均降低了10.24%，比标准OLSR 平均降低了19.87%。当节点移动速度加快时，网络拓扑变动更频繁，此时LCTM-OLSR 算法会自适应地加快TC 消息的发送频率，使网络中的节点能更及时地获取到其他节点最新的拓扑信息，从而计算出当前时间到达目的节点的最佳路由，因而LCTM-OLSR 算法仍然能够维持较低的端到端时延。HTR-OLSR 算法虽然通过减少HELLO 和TC 消息的发送间隔能在一定程度上降低端到端传输时延，由于该算法在MPR 选取时考虑节点的能量因素，使节点计算出的路径不是最短，导致时延增大。

图8 OLSR、HTR-OLSR和LCTM-OLSR算法端到端时延对比Fig.8 End-to-end delay comparison of OLSR，HTR-OLSR and LCTM-OLSR algorithms

3.2.3 发包成功率

OLSR、HTR-OLSR 和LCTM-OLSR 算法的发包成功率对比如图9 所示。LCTM-OLSR 算法的发包成功率高于其他两种算法，相比文献［18］中的HTR-OLSR 算法平均提高了3.37%，比标准OLSR平均提高了8.63%，并且当节点移动速度变快时三种算法的发包成功率均明显下降。当节点移动速度加快时，网络拓扑变化加快，节点的拓扑信息和路由信息的有效时间缩短，从而导致数据包丢包率增加。LCTM-OLSR 算法根据节点周围网络拓扑的历史变动信息，自适应地调节TC 消息的发送周期，在网络拓扑变动频繁的情况下通过加快TC 消息的发送，及时更新节点路由表中因为拓扑变动而失效的路由表项，从而有效提升了数据包的发包成功率。

图9 OLSR、HTR-OLSR 和LCTM-OLSR 算法发包成功率对比Fig.9 Contract success rate comparison of OLSR，HTROLSR and LCTM-OLSR algorithms

4 结束语

本文通过对OSLR 协议中MPR 集的选取过程进行优化，提出一种低开销拓扑维护算法。该算法在稳定量与删减量中选择较小量与新增量组成TC消息进行发送，并根据拓扑变动消息能自适应地调整TC 消息发送。实验结果表明，相比OLSR 和HTR-OLSR 算法，LCTM-OLSR 算法减少了网络控制开销同时提高了网络吞吐量和网络应对拓扑变化的适应能力。下一步将对邻居发现机制进行研究以减少网络中因邻居发现而产生的冗余，提高网络性能。