OLSR 协议MPR 覆盖度对网络性能的影响分析*

黄 佳，赵 佳，刘小娟，汪偲怡

（武汉中原电子集团有限公司，湖北 武汉 430205）

0 引言

无线移动自组网（Mobile Ad-hoc Networks，MANETs）是一组由不需要中心管理和无固定网络基础设施的无线移动节点组成的多跳临时自治系统。随着现代通信对网络移动性和组网灵活性的需求，无线自组网的应用范围大大扩展，特别适用于军事通信领域。

MANETs 每个节点的地位是平等的。当某些节点不在相互的传播范围内时，为实现通信需要中间节点进行中继，这使得MANETs 中每个节点均是潜在的路由器，必要时能担负起路由的功能。当前无线移动网络中，组网使用的路由协议主要分为两类：被动式协议与主动式协议。

被动式路由协议即按需路由协议，包括源前驱动路由协议（Ad hoc On-Demand Distance Vector Routing，AODV）[1]、动态源路由协议（Dynamic Source Routing，DSR）[2]和临时 预定路 由算法（Temporally Ordered Routing Algorithm，TORA）[3]等，这类协议在没有数据传输时不需要交换控制信息。路由发现过程由源节点需要与新的目的节点进行数据传输时启动，包含两步：首先源节点在网络中泛洪路由请求包；然后目的节点若能收到请求包，则进行单播回复，从而建立起路由。被动式路由协议需要大量的泛洪，一方面，给网络带来了大量的控制开销，另一方面，路由建立的时延也较大。

主动式路由协议，如优化链路状态路由（Optimized Link State Routing，OLSR）[4]、基于拓扑广播的反向路径转发（Topology Broadcast Based on Reverse Path Forwarding，TBRPF）[5]等，需要周期性地交互路由控制信息，在网络中产生了数据流量外的额外流量，不过节点持续地检测网络拓扑使得优化控制流量成为可能，典型的如OLSR 使用多点中继[6-7]（Multipoint Relay，MPR）技术来控制广播信息的开销。由于节点实时维护网络的动态信息变化，主动式路由协议能在需要时迅速建立路由，从而降低数据的传输时延。

由于时延的要求，特别是考虑到战场上态势的瞬息变化，军事通信领域往往倾向于采取主动式路由协议，因此OLSR 得到了广泛的关注[8-9]。近年来，很多学者针对不同的应用场景对MPR 选举机制进行了研究。

文献[10]考虑链路稳定问题和节点剩余能量（生存时间）因素，提出一种新的MPR 选择算法，根据MPR集的更新频繁程度控制拓扑控制（Topology Control，TC）消息的洪泛周期，降低了网络的开销和能源的消耗。其针对传统OLSR 协议应用于无人机自组网中时可能会选取与源节点间链路连接易断开并且剩余能量低的节点作为MPR 的不足。

文献[11]对传统的MPR 选取算法进行改进，改进后的LEC-OLSR 协议中MPR 选取算法综合考虑了节点间链路生存时间、节点剩余能量和节点深度这3 种影响因素，利用层次分析法构建判断矩阵精确地计算各影响因素的权重因子，并将它们的加权和作为MPR 节点的选取标准。

文献[12]提出一种基于链路质量的低开销路由协议（LQLR-OLSR），针对飞行自组网（Flying Ad-Hoc Network，FANET）中的MPR 集进行优化，减少冗余的MPR 节点，并修改基于期望传输计数（Expected Transmission Count，ETX），使其作为路由度量，融合正向传输成功率、反向传输成功率、链路分组大小和链路带宽4 个特征，实现路由多径自适应。OPNET 仿真结果表明，FANET 环境下LQLR-OLSR 在平均吞吐量、发包成功率、路由开销和平均端到端时延性能方面明显优于GlobalOPOLSR[13]和OLSR。

传统的MPR 算法只是减少了同一区域内相同消息的泛洪，并没有考虑网络中新加入节点获取全网拓扑信息的时间问题。文献[14]针对该问题进行了研究，并提出一种高效的MPR 选择算法，该算法有三个步骤：首先，减少了部分拓扑控制（Topology Control，TC）消息冗余问题；其次在选择MPR 时考虑有效覆盖面积，让新加入的节点获取全网拓扑信息所需的时间缩短；最后，考虑到移动性对网络拓扑的影响，基于历史信息预估下一时刻节点的位置，增强了链路的稳定性。通过仿真，将改进的MPR 算法与传统算法进行比较，端到端时延降低，数据包的传递成功率也有所提升。

基于优化链路状态路由协议的MPR 集选择算法（GLOBALOPMPR）在网络拓扑稳定的情况下能有效减少网络中的MPR 节点数，但在网络拓扑变化的情况下会出现冗余。为此，文献[15]提出一种能适应网络拓扑变化的MPR 集选择算法（GLOBALADMPR）。该算法在不增加复杂度的情况下，通过将选定的MPR 节点再次遍历去除冗余，从而得到更优的MPR 节点集合。实验结果表明，与GLOBALOPMPR 算法相比，GLOBALADMPR 算法能有效降低数据包传输时延及网络开销，提高网络吞吐量。

OLSR 路由协议与一般的链路状态协议相比，其采纳了MPR 机制，在一定程度上抑制了网络中广播控制信息的洪泛，从而降低了网络的控制开销。但是这种机制是否会影响路由的鲁棒性是值得探讨的问题，目前的众多研究成果都集中对MPR 算法进行改进，降低路由开销，而忽略了MPR 选举算法对网络鲁棒性的影响。本文设计了相应的MPR选举算法，并对MPR 覆盖度对网络性能的影响进行了仿真分析。

本文的剩余部分内容安排如下：第1 节简要介绍OLSR 协议；第2 节介绍本文提出的MPR 覆盖度算法；第3 节是仿真与分析；第4 节总结全文。

1 OLSR 协议

OLSR 是一种链路状态协议，本节首先对链路状态协议进行介绍。在链路状态协议中，MANETs中的两个节点能监听到彼此，则称这对节点间存在链路。鉴于单向链路使用的协议不同于双向链路，本文重点研究双向链路下的协议，故略掉单向链路的介绍。多跳的数据传输由路径上的各个节点之间的链路组成。链路状态协议中每个节点都获知网络中存在的链路，从而计算出到网络各个节点的最短路径链路，这得益于每个节点都必须执行下述两个过程。

（1）邻居发现：探测毗邻链路。最普遍的邻居发现机制是周期性地在一跳范围内广播HELLO包，其中HELLO 包包含该节点所监听到的邻居。通过对收到的HELLO 包进行解析，并将其和本地存储的邻居链路信息进行对比，即可获得邻接的双向链路。

（2）拓扑广播：在整个网络中将重要的邻接链路信息广而告之。初始简单的链路状态协议将TC 包在整个网络中进行泛洪，其中TC 包中包含该节点与其所有邻居节点之间的链路信息。在泛洪中，通过TC 包的序列号避免同一个节点的反复转发。在包传输不出错的情况下，这种机制使得TC 包的前传次数等于网络中的节点数目。

若假设HELLO 包和TC 包的传输率分别为α和β，那么如图1（a）所示，其中圆圈表示节点，线段表示TC 包的传播途径，以包为单位的控制开销为：

为了优化网络中的控制开销，OLSR 应运而生。OLSR 主要通过选择MPR 节点的方式进行控制包的转发，减小控制开销，其中MPR 节点为所考察节点的一跳邻居节点的子集，且该子集能够覆盖到该考察节点的所有二跳节点。具体地，MPR 对TC 包进行了如下两种方式的优化。

（1）TC 包产生优化。对于TC 消息的产生优化，存在两种方式：一种是只在MPR 节点而非网络中所有节点产生TC 包；另一种优化是在MPR 节点产生的TC 包中只包括MPR selectors，这种优化的效果取决于网络拓扑的稠密程度。

（2）TC 包广播优化。对于TC 包的广播，只通过MPR 节点进行，即MPR 节点只转发来自自己的MPR selectors 的TC 消息。值得注意的是，这里的MPR selectors 同时也是其他节点选择出来的MPR 节点（因为如上条所述，只有MPR 节点产生TC 包）。

类似的，若假设HELLO 包和TC 包的传输率分别为α和β，那么如图1（b）所示，其中圆圈表示节点，黑色圆圈表示选择出的MPR 节点，线段表示TC 包的传播途径，以包为单位的控制开销为：

式中：M为网络中总的MPR 个数，M

从这个意义上讲，MPR 集合越小，越有利于网络中控制开销的下降。然而，Andreas[2]提出一种担忧，这种优化可能是以牺牲路由协议的鲁棒性为代价的。RFC3626 中指出，MPR 节点的选择需要保证二跳邻居节点中至少有一个是MPR 覆盖的。那么MPR 节点应该怎样选取以及以何种程度覆盖二跳节点呢？

首先，引入MPR 覆盖度的概念，MPR 覆盖度定义为任一严格二跳邻居对应的MPR 节点数目。MPR 覆盖度若为m，则任一严格二跳邻居节点对应的MPR 节点数为m。如图2 所示，其中图2（a）中MPR 覆盖度为1，图2（b）中MPR 覆盖度为2，黑色节点为选择的MPR 节点。这里要指出的是，不是所有的二跳邻居节点都有两个MPR 节点进行覆盖，因为有的二跳节点由于通信范围的限制，只有一个一跳节点连通。

图2 MPR 覆盖度

其次，为了分析MANETs 中MPR 覆盖度对网络的路由性能的影响，本文提出了覆盖度可伸缩的MPR 选择算法。

2 MPR 算法

寻找最优的MPR 集合被证明是一个NP 完全问题，对此出现了多种启发式算法来寻找OLSR 协议的MPR 集合。

RFC3626 中提出了一种简单的启发式MPR 选择算法。该算法选取的MPR 集合能够覆盖所有的对称严格的二跳邻居，且MPR 节点的意愿度不是WILL_NEVER。节点的意愿度是指节点愿意成为MPR 的程度。影响节点意愿度的因素较多，MANETs 中主要考察节点的剩余能量，这是因为节点的能量需要通过电池来提供，一般是有限的，而成为MPR 意味着更多的能量消耗。

具体地，MPR 选择算法使用到的参数见表1。

表1 网络描述参数

该启发式算法的流程如图3所示，具体步骤如下。

图3 MPR 选择流程

（1）将节点意愿度N_willingness为WILL_ALWAYS的一跳邻居节点设置为MPR 节点。

（2）对所有的一跳邻居计算D(y)。

（3）对于只有一条链路可达的N2节点，将其链接的一个邻居节点设置为MPR 节点。

（4）对于N2中还未被至少一个MPR 节点覆盖到的节点执行如下操作：对于N中的每个节点，计算其可达性，即该节点可以链接到剩余N2集合中的节点数目；然后依次依据N中节点的N_willingness、可达性和D(y)选择MPR。具体地，首先选择N_willingness高且可达性非零的节点；其次若N_willingness相同，选择可达性高的；若可达性也一致，选择D(y)较高的。移除已选MPR 节点覆盖到的N2 节点，重复执行该步骤，直到N2 空为止。

（5）MPR 集合优化。依N_willingness从小到大的次序进行MPR 集的遍历。在每一步中，若节点移除后，N2 节点仍然被全部覆盖，且当前考察节点的willingness不等于WILL_ALWAYS，则将该节点从MPR 集中移除。

为了探索MPR 覆盖度对于网络路由性能的影响，本文遵循上述启发式算法选择MPR 的思想，即尽可能保留N_willingness和度数高的节点为MPR 节点，设计了MPR 覆盖度参数可变的MPR 算法，该算法的流程如图4 所示，具体步骤如下。

图4 MPR 覆盖度可变的MPR 选取流程

（1）求取当前节点的严格二跳邻居集合，并将严格二跳邻居的MPR 覆盖度设置为对应一跳邻居的数目，且这些一跳邻居均被设置为MPR 候选节点。

（2）对所有的一跳邻居计算D(y)。

（3）依下列规则对MPR 候选节点集合进行排除：依N_willingness从小到大和度数从小到大的顺序对MPR 候选节点进行遍历，若MPR 候选节点对应的严格二跳邻居的MPR 覆盖度均大于给定MPR覆盖度，则删除该MPR 候选节点，并将该MPR 候选节点对应的严格二跳邻居的MPR 覆盖度减去1；否则保留该节点。

算法的有效性分析：当MPR 覆盖度取1 时，本文算法选取的MPR 节点与RFC3626 算法选取的MPR 节点一致。

算法复杂度分析：

（1）计算严格两跳邻居集合时，首先遍历二跳邻居节点，然后遍历该邻居节点的一跳邻居节点，因此MPR 覆盖度参数可变的MPR 算法的步骤（1）的算法复杂度为σ(n2)。

（2）计算所有一跳邻居度数，首先遍历一跳邻居节点，然后遍历统计该节点的严格两跳邻居节点的个数，因此MPR 覆盖度参数可变的MPR 算法的步骤（2）的算法复杂度为σ(n2)。

（3）对已经选出的MPR 候选节点按一定规则进行删除。首先依N_willingness从小到大和度数从小到大遍历MPR 候选节点；其次遍历该候选节点的严格两跳节点，判断该两跳节点的MPR 覆盖度是否都大于给定的MPR 覆盖度。MPR 覆盖度参数可变的MPR 算法的步骤（3）的复杂度为σ(M×N×n2)，其中M为N_willingness的等级个数，N为最大的度数，在有限规模的网络中M和N都为常数，因此MPR 覆盖度参数可变的MPR 算法的步骤（3）的算法复杂度为σ(n2)。

算法的复杂度为3 个步骤的复杂度相加：

RFC3626 中MPR 选择算法的复杂度也为σ(n2)，本算法与之相比，复杂度相当。

3 仿真与分析

为了验证MPR 覆盖度对于网络路由性能的影响，本节在OPNET 网络仿真软件中进行了仿真实验。

具体地，仿真中用到的参数如表2 所示。

表2 网络仿真参数

分别对同一网络拓扑如图5 的静态场景和如 图6 的动态场景进行了联合测试。其中，前100 s为静态场景，每个节点保持静止；100 s 时动态场景中两个节点以极快的速度运动出邻居节点的通信范围；100 s 后剩余节点组成的网络为节点规模稍小的静态场景。

图5 静态场景

图6 动态场景

路由算法的衡量参数主要分为路由控制包开销和路由收敛时间，其中路由控制包开销主要是HELLO 包和TC 包，而HELLO 包每个节点都产生且只在一跳范围内广播，网络拓扑固定后HELLO包的开销也相对稳定，则TC 包是主要的比较对象。如图7 所示，随着MPR 覆盖度的上升，路由控制包开销也随之增加。对比100 s 前后，可以发现随着网络规模的降低（两个MPR 节点移出），路由控制开销也随之降低。

图7 路由开销

路由收敛时间考察网络初始化或网络拓扑发生变化后，重新获得路由的时间。如图8 所示，当网络初始和节点快速移出网络中其他节点的通信范围这两种情况下，随着MPR 覆盖度的上升，路由收敛所需时间减少。

图8 路由表计算

综上所述，MPR 覆盖度的增加，虽然一定程度上增大了网络中的控制开销，但是加速了路由的收敛。因此对于拓扑变化频繁的网络，建议保留一定的MPR 冗余，以增加网络控制开销的代价，保证路由的收敛和数据的正常传输，提高网络的 健壮性。

4 结语

路由开销的控制优化是MANETs 中的一个关键问题。本文从MPR 覆盖度入手，设计了MPR 寻找算法，并通过仿真的手段分析了不同的MPR 覆盖度下，MANETs 网络的性能。分析结果表明，随着MPR 覆盖度的增大，在路由开销也会增加的代价下，降低了路由收敛时间，一定程度上保证了MANETs的健壮性。

基于以上分析，对于拓扑动态变化的网络，建议将MPR覆盖度设置较高，以便促进路由快速收敛。