窄带自组网OLSRv2协议减少带宽占用量方法研究*

赖增桂，许 里，李默嘉，莫 娴

（中国电子科技集团公司第三十研究所，四川 成都610041）

0 引 言

动态路由协议能够根据网络拓扑的变化，在一段网络信息的交互时间之后，获得网络的当前拓扑结构，重新计算出新的、正确的路由。这种路由技术能够及时反映网络拓扑变换，根据最新的网络拓扑实时计算出最佳的路由，适合于拓扑变化频繁、具有动态结构的网络，如典型的Ad Hoc网络、战术通信网络、应急通信网络等。

动态路由协议的运行会增加额外的网络流量，占用较多额外的网络带宽，降低用户实际的业务传输速率。尤其是在窄带无线自组网环境中，由于带宽资源有限、传输链路不稳定造成的网络拓扑变化频繁等原因，减少网络维护信息的带宽占用量，提高数据业务的带宽利用率显得尤为重要，尤其是降低动态路由协议的带宽占用量，一直都是窄带无线通信网络研究的重点和难点。

1 基本原理分析

动态路由协议依据其交互路由信息的时机不同，通常被划分为主动路由协议（Proactive Protocols，也译为先应式路由协议）和被动路由协议（Reactive Protocols，也译为反应式路由协议）两种。

主动路由协议也被称为表驱动路由协议（Table Driver），在主动路由协议中，网络中每一个节点都要周期性地向其他节点交换路由信息，并且当网络拓扑结构发生变化时，节点就在全网内广播路由更新信息，这样每一个节点就能连续不断地获得网络信息，通过网络信息的交互形成网络拓扑表和路由表等。典型的主动路由协议有OLSR（Optimized Link State Routing，优选链路状态路由协议）[1-2]、WRP（Wireless Routing Protocol，无线路由协议）[3]、DSDV（Destination-Sequenced Distance-Vector Routing Protocol，目的序列距离矢量路由协议）[4]等。

被动路由协议也叫按需（On-Demand）路由协议，在这类路由协议中，节点并不保存及时准确的路由信息，当源节点需要向目的节点发送数据报文时，源节点通过网络发起查找过程，找到相应的路由后，根据找到的路由发送数据报文。为了提高效率，节点可以将找到的路由保存在缓存中供后续的数据报文发送使用。典型的被动路由协议有AODV（Ad hoc On-Demand Distance Vector Routing Protocol，自组网按需距离矢量路由协议）[5]、DSR（Dynamic Source Routing，动态源路由协议）[6]等。

另外，还有一种结合了主动和被动路由协议优点的混合路由协议也较常见。

以主动路由协议为例，路由信息通常包括邻居维护信息（hello）和拓扑维护信息（Topology Control，TC）两部分，其中拓扑维护信息又包括了源产生拓扑信息和转发拓扑信息两部分，针对如下定义的自组织网络，

N：网络总的节点数；

n：每个节点的平均邻居数，其具体数值跟网络拓扑相关，参考文献[7]给出了其具体计算方法，这里不再赘述。

定义如下路由协议的运行参数：

szhello：平均单条hello消息大小；

szTC：平均单条TC消息大小；

fhello：邻居维护频度，发送hello消息的频度；

fTC：拓扑维护频度，发送TC消息的频度。

那么，网络中某一节点i在单位时间内产生的hello消息总量为，

同样，其源产生的TC消息总量为，

假设不考虑多点中继等方式，节点i转发的TC消息总量为网络中所有其他节点在本单位时间周期内产生的TC消息，即为，

若网络为非广播网络，则同一条TC消息需要向n个邻居均转发1次，则产生的总的转发信息量为，

则网络中单个节点单位时间内产生的路由信息总量为：

那么，网络中单位时间产生的路由信息总量为：

根据以上公式，可以对主动路由协议采用以下几种方法来减少动态路由协议的带宽占用量。

（1）调整路由协议参数，降低fhello、fTC。

（2）压缩路由信息，减小szhello、szTC。

（3）采用广播更新机制，利用广播特性将n次分别转发变为1次转发。

（4）采用指定路由器（Designated Router，DR）更新机制，将网络中N个节点产生TC消息转变为仅1个节点产生TC消息。

（5）采用模糊视距（Fuzzy Sighted）机制，降低fTC。

（6） 采 用 多 点 中 继（MPR：Multi-Point Relay）机制，需要转发的节点数量n。

（7）跨层借用路由信息，fhello置为0。

（8）采用增量更新机制，减少TC消息转发，实际是减小fTC。

（9）路由信息钝化处理，减少TC消息转发，实际是减小fTC。

（10）路由信息批次发送，减小消息头开销，实质是减小fTC和szTC。

另外，还可以借助一些特殊的携带、跨层等方式进行优化，减少路由信息量。

路由信息携带；

拓扑信息可靠校验；

跨层结合优化。

虽然主动路由协议和被动路由协议在机理上有一定差异，但是以上减少主动路由协议带宽占用量的方法通常也同样适用于被动路由协议，当然也适用于混合路由协议。下面分析一下以上减少带宽占用量方法的基本原理、优缺点及使用相应方法的典型路由协议。

1.1 调整路由协议参数

将路由协议的诸如邻居维护周期、路由更新周期、超时周期等参数调整延长，降低路由节点路由维护信息的发送频繁程度，减少网络内单位时间发送的路由报文数量，以达到减少路由信息总量、降低网络开销的目的。

但是，此种方法往往会增加网络路由的收敛时间，降低对网络拓扑快速变化的适应能力。

此种方式的一种变种方法就是根据网络状态动态的调整路由协议参数吗，也即网络拓扑变化快时缩短相关参数，网络拓扑变化慢时延长相关参数，以实现减少路由信息量和适应快速拓扑变化之间的平衡。

1.2 压缩路由信息

将路由节点需要发送的路由信息采用特定的压缩算法进行压缩，或者针对路由信息本身的特点进行压缩编码，降低单条路由信息的长度，以达到减少路由信息总量、降低带宽占用量的目的。

但是，压缩与解压缩的过程会增加路由节点的本地计算量，在计算与存储能力快速增长的背景下，这种以本地计算换取无线带宽的方法是一种较优的方式，正在被越来越多的路由协议采用。

典型的采用此方法的路由协议包括OLSRv2等。

1.3 采用广播/组播更新机制

现有路由协议通常采用针对邻居进行点对点的路由更新维护方法，而对于无线网络这种典型的广播型网络，可以针对网络的广播特性，减少点对点更新维护方式，尽量采用广播/组播更新维护的方式，减少路由节点路由更新维护信息发送的次数，从而减少网络内路由更新维护信息的数量，达到减少路由信息总量、降低网络开销的目的。

但是，这种方式对于需要可靠传播的路由信息（如前述的增量更新路由维护信息）则需要增加广播网络环境下的可靠传输保障机制予以支撑，使网络协议体系变得复杂。

目前多数路由协议均支持此种更新机制。

1.4 采用DR更新机制

为减少在广播和非广播多路接入（Non-broadcast Multi-access，NBMA）类型的网络上多路由节点之间需要传递的路由信息的数量，可以引入了DR更新机制。而窄带无线网络是典型的单跳广播型网络，在其上选取或者指定一个DR，由DR负责该单跳广播网络的全网路由广播更新，而不是网络内所有节点都参与全网路由维护信息的广播更新，将传统意义上需要进行N×（N-1）/2次的路由维护信息交互缩减到2N次，从而减少路由信息量、降低网络开销。

但是，DR的选取/指定也会带来一定的弊端：DR采用选取的方式必然会增加一定的网络带宽占用量；DR采用指定的方式则会面临网络拓扑变化后部分节点信息不可达的问题，尤其是当指定的DR出现故障时，网络根本无法正常运转。

典型的采用此方法进行优化的路由协议包括OSPFv2[8]等。

1.5 采用模糊视距机制

在网络节点的关系中，两个节点距离越远（传输度量Metric越大），节点之间的相对移动性越小，远端节点的拓扑结构改变对本地节点的影响就越小，根据此原理，通过在时间、空间上对路由信息的传播进行限制可以大大减少路由信息量。具体来说，网络拓扑变化越频繁，路由节点发送路由信息的间隔就越短，但其泛洪的范围就越近；拓扑变化越慢，则路由节点发送路由信息的间隔就越长，但其泛洪的范围就越远，这样在时间上、空间上对路由信息的传播进行限制后，网络中路由信息减少，路由开销降低，从而使得路由协议能支持规模更大和移动性更强的网络。

但是，由于采用了模糊视距的方式，全网的拓扑数据库在某一时刻并不能完全真正的反应实际的拓扑，偶尔会造成路由路径非最佳的情况。当然，这种非最佳的路由并不影响全网数据的可达性。

此种方式适用于主动路由协议。典型的采用此方法进行优化的路由协议包括鱼眼状态路由（Fisheye State Routing，FSR）[9]等。

1.6 采用MPR机制

一个节点的MPR集合是它的邻节点的子集，MPR集合的邻节点无线传输范围可覆盖所有两跳外的节点。在进行路由信息的洪泛（FLOOD）更新时，只需要MPR集合的节点对路由信息进行转发，减少路由信息的冗余转发而使得消息在网络中的洪泛开销降低到最低程度，从而降低路由信息量。

但是，这种方式的MPR选举需要额外的计算能力和网络传输量。虽然会有一定的代价，但与其他洪泛机制相比，该优化机制仍然有较大的优化收益，所以目前已被很多路由协议采用。

这种方式对主动/被动路由协议均适用。典型的采用此方法进行优化的路由协议包括OLSRv2、OSPFv2针对Ad Hoc网络的多点中继扩展[10]等。

1.7 跨层借用路由信息

无线自组网在进行链路层（主要是媒体接入控制（MAC）层）的维护过程中，往往都需要进行邻居的发现，这个邻居发现过程与路由协议的邻居发现过程具有相同的作用和结果，路由协议可以直接“借用”MAC的邻居表信息，无需再单独发送邻居维护信息，从而减少路由信息量。

但是，同路由信息携带方式一样，这种方法需要结合下层信息，破坏了网络层与链路层之间相互独立关系，对系统可靠性容易造成影响。

典型的采用此方法的路由协议包括OLSRv2等。

1.8 采用增量更新机制

每次发送的路由维护信息，仅包含在前一次更新后发生变化（包括新增加、原有的发生改变以及原有的消失三种变化情况）的信息，由于每次更新仅发送变化的信息，未变化的信息不需要发送，这样就可以减少路由维护信息的重复发送，从而减少路由信息总量，降低网络开销。

但是，增量更新机制是在前一次更新的基础上进行的拓扑维护，具有严格的上下文关系，这需要复杂的可靠传输保障机制确保数据报文的成功传输，以确保各路由节点保存的拓扑数据库/表的完全一致，尤其是广播网络环境下的可靠传输保障机制将使系统变得较为复杂。

典型的采用此方法的路由协议包括OSPFv2等。

1.9 路由信息钝化处理

在高动态的无线网络中，往往会出现短暂的拓扑变化，对于采用触发式更新的路由协议，一旦出现拓扑变化则立即发起路由更新，而在前述的短暂的拓扑变化过程中，甚至可能出现上次更新尚未完成收敛，而拓扑又恢复到原状需要重新更新的情况，为避免此种情况发生，可引入“钝化”处理机制。所谓“钝化”处理是指在发生拓扑变化时，并不立即触发路由更新，而是延缓一定时间（此时间根据网络实际情况选取）确认拓扑稳定后再触发路由更新，从而减少不必要的冗余路由更新信息，降低路由协议的网络开销。

当所有节点都采用“钝化”处理机制后，则“泛洪”式的事件触发式更新机制则转变为了时间周期更新机制了。

但是采用“钝化”处理会增加路由协议收敛的时间，同时，针对不同场景选取合理的“钝化”延时也有一定难度。

这种方式对采用触发更新机制的路由协议适用。典型的采用此方法的路由协议包括OLSRv2等。

1.10 路由信息批次发送

由于无线网络的特点，每发送一次路由信息均需要进行一次无线信道的接入，而无线信道的接入过程往往开销较大，在进行路由信息的更新过程中，可将多个（一批）路由信息在一次无线信道接入过程中一起发送，减少无线信道的接入次数，从而减少路由协议的网络开销。

但是这种方法的使用，网络需要等待一段时间收集多个路由信息形成发送批，这就会增加路由协议的收敛时间。

典型的采用此方法的路由协议包括OLSRv2等。

1.11 路由信息携带

同路由信息分批发送机制的原因一样，为减少网络接入引起的额外网络开销，部分路由信息可结合上层应用，在上层应用信息完成信道接入并完成应用信息的发送后，在上层应用信息之后携带发送路由信息，从而降低路由协议的网络开销。

但是这种方法需要结合上层信息，破坏了应用层与网络层之间相互独立关系，对系统可靠性容易造成影响，同时由于携带的时机存在不确定性，路由协议的运行流程和状态也变得更加复杂。

1.12 拓扑信息可靠校验

路由协议中大多数的拓扑更新报文都需要被可靠的传输，以确保所有路由节点获取的网络拓扑的一致性。对于点对点的环境，这种可靠传输可以采用应答机制给予确保，但是点对多点尤其是广播环境下采用简单的应答机制不仅大大降低了路由协议的收敛速度，更会增加较多的网络开销。如前述采用增量更新、广播更新优化方法就会面临以上问题。针对以上问题，结合路由协议的特点，可采用拓扑信息可靠校验的方式给予解决并减少路由信息量。

所谓拓扑信息可靠校验是指：

（1）发送节点在进行拓扑更新的时候，不管采用什么更新机制，均对本节点保存的当前拓扑进行校验计算，并将校验结果携带至本更新信息内一并发送；

（2）接收节点接收该更新信息后，首先根据更新信息和本地保存信息对该发送节点相关的拓扑进行计算，并将计算所得的拓扑进行校验计算，然后将校验结果与更新信息中携带的校验结果进行对比，若校验结果一致，则认为之前的更新信息均正确，完成本次更新操作；若校验结果不一致，则认为之前有部分更新信息发生错误或丢失，则接收节点向发送节点发起点对点的初始化请求，并将本次更新信息置为无效并丢弃；

（3）收到初始化请求的节点立即/或在下一更新周期到达时，将本地状态机恢复初始状态进行更新。

采用此机制后，将单纯的某一报文的广播确认通过携带的方式换成了对前序更新报文的全部确认，同时采用默认确认（即不发送初始化请求则认为传输正确）的方式，减少确认信息发送，从而减少路由信息总量，降低路由协议开销。

但是，此种方式会增加路由协议状态机复杂程度，甚至会影响整个协议的运行机制，需慎重采用此种优化方式。当然此种方式还需要更多的存储器，用于实现对每个路由节点曾经发送的拓扑状态的存储。

1.13 跨层结合优化

所谓跨层结合优化就是路由协议结合其他层次的协议特点，进行统一的相关性优化处理，以达到提升网络整体效能的效果。例如，链路层采用载波侦听多路访问（Carrier Sense Multiple Access，CSMA）随机接入方式时，可在路由协议中增加随机的发送时延来避免多节点同时发送路由协议报文，降低冲突概率，从而提升CSMA接入效率，达到整体提升网络效率的效果。

此种优化方式需要充分了解整个网络协议栈特性，设计优化难度较大。同时，由于存在相关性优化，网络各层次/模块耦合程度较高，通用性不强，所以，该优化方式在非必要情况下不建议使用。

2 OLSRv2现有方法分析

OLSRv2作为无线自组网的重要路由协议之一，在设计之初就考虑了很多减少路由信息带宽占用量的方法，具体包括：

2.1 采用组播更新机制

OLSRv2的邻居维护信息和拓扑更新信息均采用组播发送的方式（IPv4组播地址：224.0.0.109，IPv6组播地址：FF02:0:0:0:0:0:0:6D），杜绝了点对点信息的发送，大大的减少了路由信息总量。

2.2 压缩路由信息

相对于压缩路由信息的优化方法，OLSRv2采用了RFC5444标准文档定义的报文格式，报文中使用到的地址信息、时间度量信息以及链路度量信息，OLSRv2都进行了相应的压缩处理以减少路由信息总量。对于地址信息，OLSRv2采用地址块压缩机制对路由信息进行压缩；对于时间度量信息，OLSRv2采用RFC5497标准文档中定义的特殊编码方式将原需要32比特位表示的时间度量压缩至8比特位；对于链路度量，OLSRv2也采用了特殊的编码方式将原24比特位表示的链路度量压缩至12比特位。

2.3 采用MPR机制

OLSRv2采用了MPR算法减少路由信息量，其同时应用了两组MPR集合，一组是“泛洪MPR”，还有一组是“路由MPR”。其中，“泛洪MPR”用于减少路由信息的冗余转发，仅在“泛洪MPR”集合中的路由节点才可以转发TC信息，从而实现网络内路由信息总量的减少；“路由MPR”集合中的路由节点的功能类似于前述指定路由器的功能，仅在“路由MPR”集合内的路由节点才可以发起TC信息（发送原始的TC信息），从而减少原始TC信息的数量，达到减少全网路由信息总量的目的。当然，同一个路由器可同时被选举为“泛洪MPR”和“路由MPR”。

2.4 采用模糊视距机制

OLSRv2可通过对拓扑更新报文跳数（TC_HOP_LIMIT）参数的设置来支持模糊视距算法。当将TC_HOP_LIMIT设置为固定常数时，则协议不支持模糊视距算法；当将TC_HOP_LIMIT设置为一组动态变化的数组时，协议就可以通过动态控制TC消息的扩散范围来支持模糊视距算法，降低部分TC消息的传输跳数，从而降低网络路由信息总量。

2.5 跨层借用路由信息

RFC6310[11]和RFC7181两个标准文档中都明确表示：“如果能够获得而且适合使用的话，可以使用链路层信息”，也就是说，OLSRv2协议支持借用链路层的信息来完成邻居维护，从而消减HELLO报文数量或长度，减少网络的路由信息总量，只不过在标准文档中尚未明确给出借用的方法或协议，下文将明确提出一种借用的方式。

2.6 路由信息钝化处理

OLSRv2协议中可通过设置拓扑信息最小更新周期（TC_MIN_INTERVAL）参数来实现对网络抖动引起的快速路由更新信息的钝化，当将TC_MIN_INTERVAL参数值设置为等于拓扑信息更新周期（TC_INTERVAL）参数值时，则实现了拓扑信息严格的周期性更新，从而可有效降低路由信息总量。

2.7 跨层结合优化

OLSRv2定义了延时参数（包括周期信息延时参数TP_MAXJITTER、触发信息延时参数TT_MAXJITTER以及转发延时参数F_MAXJITTER）用于减少路由协议同时产生的报文数量，以提升底层协议性能（如降低物理层冲突概率等），达到提升自组网整体性能的目的，从而实现对路由协议自身性能的提升。

2.8 路由信息批次发送

在OLSRv2协议的标准中，并未明确提出批量更新的手段，但在协议的某些实现实例中，通过报文的延时打包过程，可以将多个MSG信息打包到同一个报文，以实现批量更新功能，从而提升协议性能。

3 OLSRv2进一步优化

根据OLSRv2协议运行机制，结合前述的优化方法，针对大规模宽带自组网，如美军联合作战无线系统（Joint Tactical Radio System，JTRS）项目宽带网络波形[12]定义的网络），可尝试对OLSRv2补充采用以下优化改进方法。

（1）取消HELLO信息，结合链路层信息，简化邻居维护过程

假设自组网采用的链路层协议在进行资源分配过程中，能够快速识别邻居（含1跳及2跳邻居）状态，如美军宽带网络波形链路层协议。则仅需要在链路层协议及本路由协议之间定义一个接口（由链路层定时/触发通知本路由协议邻居的状态）即可完成邻居维护过程。其邻居维护过程如图1所示。

图1 邻居维护过程

路由协议根据链路层通知的邻居状态进行邻居添加、邻居删除、多点中继（Multi-point-relay，MPR）计算等操作，并将MPR计算结果通过TC报文进行携带传输，从而实现完整的邻居维护过程。

（2）对TC信息进行报文压缩

除采用协议已有的压缩/编码方法外，在TC信息发送前/接收后，对TC信息均采用标准压缩/解压算法（如ITUv.44标准定义的LZJH算法）进行压缩/解压，进一步降低报文长度。

（3）更改TC信息的泛洪更新机制为逐跳更新机制

路由节点在收到TC信息后，并不直接进行泛洪，而是将拓扑更新信息进行整合，形成新的拓扑更新信息并进行存储，待拓扑更新周期到达时再进行TC信息的发送，从而实现严格的周期化逐跳更新。此时发送的拓扑更新信息应该是本路由节点已知的全部网络拓扑。

需要注意的是，进行拓扑更新信息整合时，需要结合MPR机制，以减少重复信息的发送。

（4）对拓扑信息的更新采用增量更新机制

在拓扑更新周期到达需要进行TC信息的发送时，根据当前需要发送的拓扑信息以及上一周期已经发送的拓扑信息的差异程度，重新构造增量更新TC信息并进行发送。

增量更新TC信息分为三种：一是初始化信息，该信息表示本路由节点所获知的完整拓扑信息，用于首次进行TC信息的发送，或者是在其他路由节点请求初始化信息的时候发送（迟入网或传输出现错误），此时，该路由节点处于初始化状态；二是拓扑保持信息，该信息表示两次更新之间拓扑没有发生变化；三是拓扑变化信息，该信息表示两次更新之间拓扑发生的变化。

需要进行增量更新TC信息发送的时候，增量更新TC信息的构造及发送原则如下：

1）若本路由节点处于初始化状态，则发送初始化信息；否则，进入2）；

2）若本周期内本路由节点已知拓扑信息未发生改变，则仅需要发送一条拓扑保持信息；否则，进入3）；

3）仅发送发生改变的拓扑信息，改变信息的描述主要针对链路情况进行，包括链路质量变化、新增链路、消失链路等几种情况。

需要注意的是，由于增量更新的TC信息存在严格的上下文关联，需要采用前文所述“拓扑信息可靠校验方式”对增量更新报文进行可靠校验，一旦校验失败，则通过向源信息路由节点发送重新初始化请求以使源路由节点进入初始化状态。

增量更新状态转移关系如图2所示。

4 性能评估

采用OPNET14.5构建如下仿真环境，

（1）网络总的节点数N为100；

（2）网络节点均匀分布在1 000 m×1 000 m的正方形区域内；

（3）节点在该区域内随机移动；

（4）每个节点传输距离均为150 m（即除去边缘效应，平均邻居数n约为7个）；

（5）物理层采用标准IEEE 802.11无线接口；

路由协议采用标准OLSR。

（6）在此仿真环境下进行如下四次仿真。

第一次采用OLSR协议默认参数Hello_interval=2 s，Tc_interval=5 s进行仿真；第二次调整OLSR参数Hello_interval=3 s，Tc_interval=10 s进行仿真；第三次在第二次仿真场景的基础上，增加路由信息压缩功能；第四次在第三次仿真场景的基础上，采用借用链路层邻居信息的方式进行邻居维护。四次仿真均能够正常收敛，统计四次仿真的全网路由信息量如图3所示。

图3 四种仿真场景下的全网路由开销

其中，情况一的曲线表示第一次仿真的路由信息量，基本保持在375 kbit/s左右，情况二的曲线表示第二次仿真的路由信息量，基本保持在200 kbit/s左右，情况三的曲线表示第三次仿真的路由信息量，基本保持在100 kbit/s左右，情况四的曲线表示第四次仿真的路由信息量，基本保持在90 kbit/s左右，可以看出，每增加一种优化方法，路由信息量均有相应的减少，证明以上优化方式均能够有效减少路由信息的带宽占用量。

另外，参考文献[7]也通过建模计算和仿真的方式证明了采用MPR机制、路由信息批次发送、采用模糊视距机制等能够有效减少OLSR路由协议的带宽占用量。同样的，可以证明其他优化方式也能够起到减少路由信息带宽占用量的作用。

5 结 语

本文分析了窄带无线网络动态路由协议的典型减少带宽占用量的优化方法及其工作原理，并针对一种典型应用场景综合采用多种优化方法对OLSRv2路由协议进行了优化设计，对OSLRv2路由协议的综合性能有较大的提升，尤其是路由信息量大大的减少，能够有效提升窄带无线自组网的性能。但是，路由协议的优化，不仅仅是减少带宽占用量为目的，还需要综合考虑其他性能要求，也不是如前所述几种方式的简单应用，更不是将多种前述方式进行叠加堆砌，而是针对实际的应用环境，综合运用上述多种优化手段，综合考虑多种优化目标，取其最优组合而获得最佳的运行效果。