基于跨层设计的多子网OLSR路由协议*

郑 重，郭强胜，毛建兵

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

0 引 言

无线移动Ad Hoc网络[1]是一种无中心、分布式的多跳无线网络，因其不依赖于任何固定基站，能快速部署，建立起一套完整、灵活、高抗毁的网络通信系统，提供有效的数据和多媒体通信服务，在很多特殊场合有着广泛的应用。Ad Hoc网络路由协议根据路由发现策略不同[2-3]，主要分为周期性更新拓扑信息的先应式路由协议和根据传输需要来寻找路由的反应式路由协议两大类。

在现代移动网络应用中，为了应对网络节点迅速和不可预料的变化，以及传输实时性高的特点，必须采用先应式路由协议，而面对网络规模越来越大的现状，单子网已经不能满足要求，多子网设计能够在保证实时性的情况下，构建大规模的移动网络。本文将介绍一种基于跨层设计的多子网OLSR[4]路由协议，适用于高实时性大规模移动分布式组网。

1 OLSR路由协议原理

优化链路状态路由协议（Optimized Link State Routing，OLSR）是IETF MANET工作组确定为RFC[5]标准的一种先应式路由协议[6]，它是在传统的链路状态路由协议的基础上改进而成。OLSR路由协议与传统的链路状态路由算法最显著的区别在于MPR[7]（Multipoint Relay）的引入。MPR选举机制实现在全网有效地扩散拓扑信息的同时，大大降低了路由控制消息的洪泛规模。MPR节点的选举原则是MPR为对称邻居节点，通过选出的MPR可以到达所有的两跳邻居节点，并且选出的MPR个 数尽可能少。网络中的每个节点都独立地在自己的对称邻居节点中选举自己的MPR节点集。

图1 MPR选举机制

如图1所示，通过MPR节点的选举，节点3/4/6成为节点0的MPR节点，通过这3个节点的转发，节点0的数据发送可到达其所有的两跳邻居节点。可见，MPR机制提供了洪泛过程的优化转发[8]。

OLSR特别适用于节点多且密集分布的网络。当网络节点越稀疏，该协议的优化程度就越小。当每个节点的邻居都是MPR节点时，该协议就退化成普通的链路状态路由协议。OLSR协议是为了适应Ad Hoc网络的要求，对传统链路状态路由算法进行改进优化而提出的。

2 CLOLSR路由协议

在大规模组网情况下，为了快速响应拓扑变化，缩短邻居节点发现时间，使路由更新时间和全网建立时间更加符合网络使用需求，CLOLSR（Cross-layer Optimized Link State Routing）路由协议创新性的采用了网络层和链路层联合设计的方式，利用链路层已有的控制时隙信息交互来实现邻居节点的快速发现和网关节点的选举。

2.1 基于链路层的快速邻居发现

OLSR设计通过Hello控制消息广播实现邻居节点的发现。Hello控制消息中的信息对于成功完成链路侦听、邻居探测和MPR节点选举有着重要的作用，但Hello消息发送过于频繁，对信道传输资源有不小的占用。链路层设计了基于邻居节点控制时隙（NiB/CNiB）的交互过程，通过节点之间在每个邻居节点控制时隙周期（NiB-Epoch/CNiBEpoch）内周期性的交互，链路层可以快速实现邻居发现。因此，由于链路层已经可以实现对一跳和两跳邻居的发现，OLSR路由协议可以取消Hello控制消息，由链路层提供一跳和两跳邻居信息予以使用。本文采用跨层协同设计的方法，CLOLSR路由协议使用链路层上报的邻居信息来替代Hello消息的功能。

链路层基于NiB/CNiB交互的邻居发现过程如图2所示。可以看出，节点可以在1个Epoch时间内实现对一跳邻居的发现，在2个Epoch时间内实现对两跳邻居的发现。特别说明，这里的邻居发现给出的是对称链路邻居。

链路层持续不断地监测邻居状态，在邻居发生变化时报告给路由模块。路由模块基于链路层上报的邻居发现信息，根据上报内容完善自己的链路状态（Link Set）表、邻居（Neighbor Set）表、两跳邻居（2-hop Neighbor Set）表，并根据表的内容和变化，进行MPR节点集、拓扑变化、路由表的计算和更新。

图2 链路层基于NiB/CNiB的邻居发现

OLSR路由的Hello消息涉及链路侦听、邻居探测和MPR节点选举等三个方面的功能。Hello被取消后，链路侦听和邻居探测通过图2所示的邻居NiB/CNiB交互可以实现，而MPR节点选举结果的通告则需要在链路层和网络层之间协作，以保证更快的网络拓扑响应。邻居及邻居链路的变化将导致节点MPR选举的变化，当节点MPR节点选举结果（即MPR节点集）发生变化时，节点将必须在一个小于Hello消息发送间隔时间内广播发送一个额外的MPR节点集通告控制消息，甚至可以采取立即发送通告控制消息的方式，以加快路由对于链路失效的响应处理。此后，原Hello消息中执行MPR节点集周期性通告的功能将由链路层周期性的NiB/CNiB分组发送通过“MPR邻居ID”字段携带相关信息进行通告。

2.2 子网间路由抽象

以OLSR为代表的先应式路由协议非常适合应对网络中节点位置的迅速变化和传输实时性高的要求，但当网络规模越来越大时，OLSR采用的广播方式扩散路由控制报文就会占用太多的开销，为了控制网络开销，需要将OLSR路由控制报文的广播扩散限制在一个子网范围内，子网与子网之间的路由信息通过网关节点拓扑抽象进行网间扩散。网关节点将抽象后的子网路由表发送给相邻子网的网关节点，通过子网间路由抽象，实现了复杂拓扑的简化，避免了局部网络的拓扑变化波及全网，提高了网络的机动性能。拓扑抽象示意如图3所示。

子网之间互联允许存在多个网关节点，但不允许无限增加。否则，当两个子网所处地域覆盖重叠时，每个节点都有可能成为网关，不合理地消耗子网间数据时隙资源，阻塞子网内数据时隙分配和数据通信。子网之间互联保持2～3个网关节点比较合理，并且这些网关节点间隔至少2跳远，避免相互竞争资源，利于信道的空间复用。两个子网之间的网关节点是一一对应的，不能存在一对多的情况，否则容易出现网关节点拥塞现象。抽象网络拓扑将子网内所有节点都抽象为距离网关节点一跳距离。抽象网络拓扑表达的跳数“距离”信息与子网内路由的跳数“距离”不对等，不能合并等同在一起计算路由，否则可能产生路由环路。可以认为，子网间通信的代价远高于子网内通信。

2.3 网关节点选举

网关节点选取遵循的原则如下：

（1）为了避免拥塞，同一个节点通常情况下只能作为特定两个子网之间的网关，而不能同时作为三个或是更多个子网之间的网关。

（2）两个子网之间保持一定合理数量的网关节点，并且网关节点之间最好间隔2跳距离，利于信道的空间复用。

（3）网关节点选取采取分布式设计，通过启发式算法决定一个节点在普通节点与网关节点之间动态转换身份。

（4）在快速拓扑变换条件下，网关节点选取需要尽量选择能够提供稳定的子网间链路的节点，否则不利于网络的收敛和可靠通信。

网络中每个节点都有机会在NiB时隙（子网间邻居节点控制时隙）中广播发送控制消息。通过侦听接收NiB消息，节点可以获得周围一跳可达范围内其他子网的存在情况。当节点发现周围有稳定的其他子网节点存在时，则节点具备成为网关节点的前提条件。这时，节点需要判断当前子网中是否存在多个连接该子网的网关。由于子网中已经运行了先应式路由协议，因此节点自然掌握了所在子网的完整网络拓扑信息。基于所掌握的拓扑信息以及网关在子网内的通告，节点可以准确获知当前网络中有多少个网关节点，以及这些网关节点距离自己的跳数等。

网关节点选取的算法过程设计如图4所示。其中，持续监测时间Tstab目的在于保证网关跨子网通信链路的稳定性。

图4 网关节点选取算法

如果具备成为网关节点条件的普通节点发现子网内网关节点数量不足，且自身所处网络位置与现有网关节点的距离跳数大于2跳，则节点从普通节点身份转换为网关节点，并向网络中通报连接可达的子网的抽象链路状态更新信息。

3 仿真及结果分析

3.1 仿真条件和基本参数配置

本文使用OPNET Modeler 14.5.A仿真软件建立网络模型，仿真场景为20 km×20 km的区域内放置32～128个节点，假定所有节点都已完成外同步，节点间随机形成最大跳数为8的网络。

仿真中，各节点的仿真模型均相同，物理层采用自由空间模型[9]，链路层采用TDMA（Time Division Multiple Access）分时复用传输机制，信道被划分为子帧和时帧，连续的3个子帧联合并在一起构成一个时帧，一个子帧的时间为46.875 ms，子帧中每个时隙的长度约0.937 5 ms，每个子帧共计划分50个时隙，包括控制时隙和数据时隙。根据控制时隙具体用途的不同，控制时隙具体又分为：NiB时隙、CNiB时隙。根据链路层时帧结构设计，仿真中TDMA参数配置如表1所示。

表1 链路层参数配置

网络层路由协议基本参数配置如表2所示。

表2 路由协议基本参数配置

3.2 仿真结果及分析

为了对CLOLSR协议进行性能评估，在完全相同的参数配置情况下，本文将CLOLSR协议与传统OLSR协议从初始建网时间、邻居节点发现时间、网络局部变化收敛时间、平均路由开销和平均一跳端到端时延五个方面进行仿真对比。

图5是两种协议128节点初始建网时间对比图，为了研究网络收敛情况，配置网络中所有节点位于初始位置不动。从图5中可以看出，CLOLSR路由协议的初始建网时间远小于OLSR路由协议，只有后者的二分之一左右，这主要是因为CLOLSR路由协议采用了划分多子网的方式，每个子网可以迅速完成收敛，且利用子网间的路由抽象完成整个网络的建立，相对于OLSR路由协议需要等到探测消息扩散至全网才能完成网络的收敛，CLOLSR路由协议的初始建网时间要快很多。

图5 128节点初始建网时间

图6 是两种协议的邻居节点发现时间对比图，从图6中可以看出，在同样的条件下，CLOLSR路由协议的邻居节点发现时间小于OLSR路由协议，这是由于CLOLSR协议利用了链路层设计的基于邻居节点控制时隙（NiB/CNiB）的交互，通过节点之间在每个邻居节点控制时隙周期内周期性的交互，可以快速实现邻居发现，而OLSR路由协议则只能通过自身发送Hello消息，通过底层传输到达对端，再收到回复后才能实现邻居发现，因此邻居节点发现时间要慢一些。

图6 邻居节点发现时间

为了测试网络局部变化收敛时间，设定拓扑变化如图7中拓扑1变为拓扑2，通过观察路由表变化，测量子网收敛时间大小。

图7 网络局部变化示意图

两种协议的测量结果如图8所示，从图8中可以看出，对于图7所示的网络局部变化，CLOLSR路由协议基本可以将收敛时间控制在1 s左右，OLSR路由协议则普遍需要2.5 s以上，这是因为CLOLSR协议利用链路层的快速邻居发现机制迅速的完成了一跳和两跳邻居的探测，对于距离两跳以上的节点，只需要收到TC消息即可建立路由，对于OLSR协议，则需要首先利用Hello消息获知一跳和两跳邻居信息，然后通过选举出的MPR节点发送TC消息获知到达两跳以外节点的路由。因此，网络局部变化收敛时间较长。

图8 网络局部变化收敛时间

图9 是两种协议的32节点网络平均路由开销对比图。从图9中可以看出，网络建立伊始，由于网络寻路需求较大，控制开销发送频繁，平均路由开销较高，但随着通信链路的陆续建立，控制消息的发送需求也随之下降，因此平均路由开销逐渐降低，此后平均路由开销只在有限范围内波动。CLOLSR协议平均路由开销始终要低于OLSR协议，这是因为CLOLSR协议取消了Hello消息，而使用链路层上报的邻居信息来替代，从而降低了平均路由开销，节省了带宽资源。

图10是两种协议的平均一跳数据端到端延时对比图，测试数据包长度为512字节。从图10中可以看出，两者的延时相差不大，基本保持一致，说明CLOLSR路由协议在协议本身的性能和开销上有优化，在一定程度上缓解了网络拥塞，但是在网络整体业务流量较低的情况下，链路建立之后，对于业务数据的传输延时改善不大。

图9 32节点网络平均路由开销

图10 平均一跳数据端到端延时

4 结 语

本文为了提升OLSR 协议在高实时性大规模组网条件下网络的整体性能，提出了基于链路层的快速邻居发现和网管节点选举、子网间路由抽象两点改进意见。并将CLOLSR协议与OLSR协议进行了仿真对比，结果表明：CLOLSR协议不仅在初始建网时间、邻居节点发现时间、网络局部变化收敛时间等网络性能指标上有较大提升，还降低了网络平均路由开销，在大规模自组织网络中具有一定的应用前景。