4.1 最优化链路状态路由（OLSR）协议

OLSR协议是为MANET网络开发的。OLSR协议是表格驱动、主动式路由协议，即有规律地与网络中其他节点交换拓扑信息。每个节点从其相邻节点中选择一组节点作为MPR。在OLSR协议中，只有选作MPR的节点才负责转发控制消息，将控制消息传播到整个网络中。MPR提供一种高效的控制消息泛洪机制，减少了所要求的传输量。

选作MPR的节点还必须负责向网络中报告链路状态信息。对OLSR协议提供到达所有目的节点的最短路径的唯一要求是，MPR节点声明其MPR选择器的链路状态信息。也可以利用其他有效链路状态信息，比如冗余度信息。

已经被某些相邻节点选作MPR的节点周期性地在其控制消息中播发链路状态信息。因此，一个节点向网络中播发已选择自己作为MPR节点的那些相邻节点与自己之间的可达性。在计算路由的时候，利用各个MPR节点构成从一个给定节点到达网络中任何目的节点的路由。OLSR协议使用MPR来简化控制消息在网络中的有效泛洪。

节点从其一跳远范围内的对称（即双向连接）相邻节点中选择MPR。因此，通过MPR选择路由自动避免了有关在单向链路上传输数据分组的问题（例如，无法接收到数据分组的一跳链路层应答，因为链路层采用这种技术进行单目标传输）。

OLSR协议的操作独立于其他协议，对低层链路层未做任何假设。

OLSR协议沿袭HIPERLAN的转发和中继概念。OLSR协议是在IPANEMA项目（欧几里德计划的一个组成部分）和PRIMA项目（RNRT计划的一个组成部分）中开发出来的。

4.1.1 OLSR协议概述

OLSR协议继承了链路状态算法的稳定性。由于OLSR协议的主动操作特性，所以OLSR协议在需要路由的时候能够立即得到路由。OLSR协议对经典链路状态协议作了优化，以便适用于MANET。

OLSR协议只使用专门选定的MPR节点转发控制消息，从而使控制消息泛洪的开销达到最低程度。这种技术大幅度地减少了将一条消息泛洪到网络中的所有节点所要求的转发次数。OLSR协议提供最短路径路由时只需要局部链路状态信息。所需要的链路状态的最小集合就是所有被选作MPR的节点必须广播到达其MPR选择器的链路。

OLSR协议可以通过缩短周期性发送控制消息的最大间隔时间来优化对拓扑变化的反应。OLSR协议连续维护到达网络中所有目的节点的路由，因此有利于如下流量模式：一个大节点子集与另外一个大节点子集进行通信，并且[源节点，目的节点]对随着时间的流逝而发生变化。

OLSR协议按照全分布式方式工作，不依靠任何中心实体。OLSR协议不要求控制消息的可靠传输。每个节点周期性发送控制消息，因此能够支持某些控制消息的合理丢失。这种消息丢失在无线网络中经常发生，这是由于碰撞或者其他传输问题的缘故。

OLSR协议也不要求消息的按序交付。每条控制消息包含一个序列号，对于每条消息其序列号增一。因此，假如需要的话，一条控制消息的接收节点能够容易识别出哪个信息是最新的，即使各条消息在传输过程中被重新排序也是如此。

OLSR协议提供诸如休眠方式操作、多目标路由等协议扩展支持。可能需要给协议引入这些扩展能力，同时又能够向后兼容以前的版本。

OLSR协议不要求对IP分组格式做任何改变。因此，在使用现有IP协议栈时，OLSR协议只需与路由表管理交互。

1.OLSR术语

（1）节点（Node）：一个节点指一个实现和完成本文说明的OLSR协议的MANET路由器。

（2）OLSR接口（OLSR Inteface）：指参与运行OLSR协议的MANET网络中的一种网络装置。一个节点可以有几个OLSR接口，每个OLSR接口分配有一个唯一的IP地址。

（3）非OLSR接口（Non OLSR Inteface）：指一种网络装置，但是不参与运行OLSR协议的MANET网络。一个节点可以有几个非OLSR接口（无线的和/或者有线的）。来自非OLSR接口的路由信息可以注入到OLSR路由区域中。

（4）单OLSR接口节点（Single OLSR Inteface Node）：指只有一个OLSR接口的节点，参与OLSR路由区域。

（5）多OLSR接口节点（Multiple OLSR Inteface Node）：指含有多个OLSR接口的节点，参与OLSR路由区域。

（6）主地址（Main Address）：表示一个节点的主地址，在OLSR控制消息传输中用作本节点发送的所有消息的“源节点地址（Originator Address）”。该地址就是本节点某个OLSR接口的地址。

单OLSR接口节点必须使用其唯一的OLSR接口地址作为其主地址。

多OLSR接口节点必须选择其中一个OLSR接口地址作为其“主地址”（等效于“路由器识别码ID”或者“节点识别码ID”）。一个节点选择哪个地址并不重要，但是应该总是使用同一个地址作为其主地址。

（7）相邻节点（Neighbor Node）：假如节点Y能够接收到节点X发送的信息，那么节点X就是节点Y的一个相邻节点（即节点X的一个OLSR接口与节点Y的一个OLSR接口之间存在一条链路）。

（8）二跳相邻节点（2-Hop Neighbor）：指能够被一个相邻节点接收的一个节点。

（9）严格二跳相邻节点（strict 2-Hop Neighbor）：指一个二跳相邻节点，该节点既不是该节点本身，也不是该节点的一个相邻节点，而是该节点的一个相邻节点的一个相邻节点、其愿意设置不等于WILL_NEVER（从不愿意为其他节点转发信息）。

（10）多点中继（MultiPoint Relay，MPR）：指一个节点被其一个一跳相邻节点X选定，将其从节点X接收到的所有广播消息“重新广播”出去，但是要求该消息不是重复消息，并且其有效时间域的时间大于1。

（11）多点中继选择器（MultiPoint Relay Selector，MS）：指一个节点已经选择其一个一跳相邻节点X作为多点中继，该节点叫做节点X的多点中继选择器。

（12）链路（Link）：一条链路是一对能够相互接收对方发送的OLSR接口，这两个OLSR接口属于两个不同的节点。当节点A的其中一个接口存在一条链路到达另一个节点B的其中一个接口时，就说节点A存在一条链路到达节点B。

（13）对称链路（Symmetric Link）：指两个OLSR接口之间的一条已被证实的双向链路。

（14）非对称链路（Asymmetric Link）：指两个OLSR接口之间的一条已被证实的单向链路。

（15）对称一跳相邻区域（Symmetric 1-Hop Neighborhood）：任一节点X的对称一跳相邻区域是一组节点，该组节点至少存在一条对称链路到达节点X。

（16）对称二跳相邻区域（Symmetric 2-Hop Neighborhood）：任一节点X的对称二跳相邻区域是一组节点（不包括节点X本身），该组节点存在一条对称链路到达节点X的对称一跳相邻区域。

（17）对称严格二跳相邻区域（Symmetric Strict 2-Hop Neighborhood）：任一节点X的对称严格二跳相邻区域是一组节点（不包括节点X本身和其相邻节点），该组节点存在一条对称链路到达节点X的某个对称一跳相邻节点、其愿意设置不等于WILL_NEVER。

2.OLSR协议的适用性

OLSR是一个主动式MANET路由协议。由于MPR在规模大、节点密度高的移动网络中表现良好，网络规模越大、节点密度越高，MPR优化的效果越好，因此OLSR协议特别适用于规模大、节点密度高的移动网络。

OLSR协议也非常适用于在较大的节点组之间进行随机、零星的传输，而几乎总是排斥在较小的特定节点组之间进行传输。OLSR协议作为一个主动式路由协议也适用于通信节点对随着时间的流逝而变化的场合；在这种场合下，OLSR协议一直在为所有已知目的节点维护路由，因而不会产生额外的控制开销。

3.多点中继

多点中继的思想是通过降低相同区域内的冗余重传而将消息在网络中的泛洪开销降低到最低程度。网络中的每个节点N从其对称一跳相邻区域（任一节点N的对称一跳相邻区域是一组节点，该组节点至少存在一条对称链路到达节点N）中选择一个节点集（称为节点N的MPR集），该相邻区域可能重传该节点N发送的消息。不在节点N的MPR集中的那些相邻节点仍然接收和处理广播消息，但是不重传从节点N接收到的广播消息。

每个节点从其一跳对称相邻节点中选择其MPR集。选出的MPR集覆盖（按照传输距离来衡量）全部对称严格二跳节点。节点N的MPR集表示为MPR(N)，是节点N的对称一跳相邻区域的、满足以下条件的任意子集：节点N的对称严格二跳相邻区域中的每个节点必须有一条链路到达MPR(N)。MPR集越小，OLSR路由协议的控制传输开销越低。

每个节点维护有关已经选择其作为MPR的相邻节点集的信息。这个相邻节点集称为该节点的“多点中继选择器集”。一个节点从其相邻节点周期性发送的HELLO消息中获取多点中继选择器集信息。

假定来自节点N的任意一个MPR选择器的、需要传播到整个网络中的一条广播消息被节点N重传，其前提是节点N迄今还未接收到这条广播消息。MRP集可能随着时间的流逝而变化（即，当一个节点选择另外一个MPR集的时候），并且通过其HELLO消息中的选择器节点来说明。

4.1.2 OLSR协议功能

本节概述OLSR协议的整个功能。

OLSR协议包括一个“内核”功能模块和一个辅助功能模块，内核功能模块对于OLSR操作总是需要的。

根据其功能，内核详细说明一个协议能够为一个独立的MANET网络提供路由。

每个辅助功能提供其他适用于特定情形的功能，比如一个节点正在提供本MANET网络和另外一个路由区域之间的连接。

所有辅助功能都是兼容的，在一定程度上任何辅助功能集（子集）可以使用内核模块来实现。OLSR协议允许网络中存在不同类型的节点，即实现不同的辅助功能子集的节点。

将OLSR协议的功能划分成内核功能和辅助功能集是为了提供一个简单且易于理解的协议，以及提供一种只增加复杂性的方法来提供所需要的其他特定功能。

1.内核功能

OLSR协议的内核功能详细说明节点（配置有OLSR接口且加入MANET网络，运行OLSR协议）的操作情况，其中包括OLSR协议消息及其在网络中的传输、链路探测、拓扑传播、路由计算的通用规范。OLSR协议内核由以下部分组成：

（1）分组格式与分组转发。分组格式、泛洪优化机制的通用规范作为所有OLSR控制通信的传输机制。

（2）链路探测。通过周期性往接口上发送HELLO消息来实现链路探测，并且据此检查连通性。为每个接口单独产生和发送HELLO消息。链路探测得到的是一个本地链路集，该集合描述了“本地接口”与“远端接口”（即相邻节点的接口）之间的链路。假如链路层提供足够的信息，那么这些信息可以用来替代HELLO消息交换而构成本地链路集。

（3）相邻节点的探测。假定一个网络的组成节点只有一个接口，那么节点可以从链路探测交换的信息中直接得到相邻节点集：根据定义，单接口节点的“主地址”就是该节点的唯一的那个接口的地址。

在多接口节点的网络中，需要额外的信息将接口地址映射为主地址（并由此映射到节点）。通过多接口声明（Multiple Interface Declaration，MID）消息来获得这些额外的信息。

（4）MPR选择和MPR信令。选择MPR的作用是为了让一个节点选择其相邻节点的一个子集，使得子集中的相邻节点转发的广播消息能够被二跳远以外的所有节点所接收到。计算得到的一个节点的MPR集对于每个接口均满足这个条件。计算MPR集所需要的信息通过周期性交换的HELLO消息来获取。

（5）拓扑控制（Topology Control，TC）消息的传播。广播拓扑消息是为了给网络中的每个节点提供计算路由所需要的足够多的链路状态信息。

（6）路由计算。假定给定节点的接口配置，以及通过周期性消息交换获取链路状态信息，那么就能够计算出每个节点的路由表。

这些机制的主要概念是MPR关联关系。

2.辅助功能

除了OLSR协议的内核功能以外，还存在需要其他功能的情形。其中包括这样的情形：一个节点有多个接口，其中若干个接口参与另外的路由算法区域；网络硬件接口设计按照链路层通知的形式提供额外的信息；要求以协议开销为代价提供冗余拓扑信息。

OLSR协议的辅助功能包括非OLSR接口、链路层通知、高级链路探测、冗余拓扑、冗余MPR泛洪。假如需要某种辅助功能特征，则应该按照相应规定提供。

4.1.3 OLSR协议内核

1.分组格式与分组转发

OLSR协议对跟其有关的所有数据采用统一的分组格式进行通信。其目的是为了便于OLSR协议的功能扩充和强化，以及版本升级，而又不会影响OLSR协议的向后兼容性；同时提供一种简易方法，将不同“类型”的信息组合在一起进行一次传输，因而有利于采用网络提供的最大分组。这些分组可以嵌入在UDP数据报中在网络中传输。本版本采用IPv4地址。

每个分组封装一条或者多条消息。各条消息共享一个公共分组头格式，使得各个节点能够正确接收和转发未知类型的消息（假如适当的话）。

消息可以泛洪到整个网络中，或者泛洪到某一直径（离本消息源节点的跳数距离）的有限范围内。因此，将一条消息发送给一个节点的相邻区域正好是泛洪的一种特殊情形。当泛洪任一控制消息时，就地排除该消息拷贝的重传（即每个节点维护一个拷贝集，用于防止对同一条OLSR控制消息发送两次或者两次以上），采用随后描述的MPR将控制消息在整个网络中的重传次数降低到最低程度。

此外，一个节点可以检查消息的头部，获取有关到达该消息源节点的跳数距离。这种特征在有些场合可能非常有用。例如，存储在节点中的、来自所接收控制消息的时间信息取决于到达本消息源节点的距离。

1）OLSR协议和端口号

OLSR协议中的分组采用UDP进行通信。IANA已经将端口698分配给OLSR协议专门使用。

2）主地址

对于只包含单个接口的一个节点，根据“OLSR协议术语”，该节点的主地址必须设为该接口的地址。

3）分组格式

OLSR协议中任何分组的格式如图4-1所示（图中省略了IP头和UDP头）。

（1）分组头

分组头包含分组长度、分组序列号两个组成部分，详细说明如下：

① 分组长度（Packet Length）。本域表示本分组的字节长度。

② 分组序列号（Packet Sequence Number，PSN）。每当发送一个新的OLSR分组的时候，必须将分组序列号PSN加1。按照4.1.6节描述的方法处理序列号的返转（Wrap-Around）问题。为每个接口单独维护一个分组序列号，这样在一个接口上发送的分组被连续添加序列号编号。

从分组的IP头中获取发送本分组的接口的地址。假如一个分组没有任何消息（即，分组长度小于或者等于分组头的长度），则必须丢掉该分组。对于IPv4地址，这就意味着分组长度小于16个字节的分组被丢掉。

（2）消息头

消息头由消息类型、接收信息有效时间、消息长度、消息源节点地址、消息发送有效时间、跳数、消息序列号组成，详细说明如下。

① 消息类型（Message Type）。本域说明随后的“消息”的类型。本文的消息类型编码为0～127，今后有可能进一步扩充。

② 接收信息有效时间（Vtime）。本域说明一个节点必须考虑本消息中包含的信息在被接收之后的有效时间长度，除非接收到本信息的一个最近更新。有效时间用本域高部4 比特表示的尾数和本域低部4比特表示的指数来共同表示，即：

有效时间 = C×(1+a/16)×2b（秒）

其中：a表示本域高部4比特表示的整数，b表示本域低部4比特表示的整数。比例因子C的建议值见4.1.5节。

③ 消息长度（Message Size）。本域给出本条消息的长度，以字节为单位，从“消息类型”开始计算到下一条“消息”开始的位置为止（假如后面没有其他消息，则到本分组最后字节为止）。

④ 消息源节点地址（Originator Address）。本域包含产生本条消息的源节点的主地址。不应该混淆本域与IP头中的源地址，后者随着每当到达一个转发本条消息的中间接口地址而变化。本域在本分组的整个传输过程中必须保持不变。

⑤ 消息发送有效时间（Time To Live，TTL）。本域说明本条消息将被发送传输的最大跳数。在发送本条消息前，必须将本域的值减一。当一个节点接收到一条消息发送有效时间等于0 或者1的消息后，在任何条件下都不必转发该消息。一般情况下，节点不会接收到TTL等于0的消息。

因此，消息的源节点通过设置TTL的值就能够限制消息的泛洪范围。

⑥ 跳数（Hop Count）。本域说明本条消息已经传输通过的转发跳数。在一条消息被转发之前，必须将其跳数加1。开始的时候，消息的源节点将本域设为0。

⑦ 消息序列号（Message Sequence Number）。当产生消息的时候，消息的源节点给其产生的每条消息分配一个唯一的识别码号码。将这个号码插入到本条消息的序列号组成域。一个节点每产生一条消息，就将消息序列号加一。按照4.1.6节描述的方法处理消息序列号的返转问题。消息序列号用来确保一条消息不会被任何一个节点转发两次或者两次以上。

4）分组处理和消息泛洪

一个节点接收到一个基本分组后，检查其中包含的每个“消息头”。根据“消息类型”的取值，该节点就能够决定该消息的最终结果。一个节点可能对同一条消息接收到多次。因此，为了避免重复处理某些已经被接收过和处理过的消息，每个节点维护一个拷贝集合。节点将有关最近所接收到的消息的信息记录在拷贝集合中，从而避免一条消息的重复处理。对于一条消息，每个节点在拷贝集合中记录一个“拷贝数组”（D_addr，D_seq_num，D_retransmitted，D_iface_list，D_time），其中：D_addr表示本条消息的源节点地址，D_seq_num表示本条消息的消息序列号，D_retransmitted表示本条消息是否已经被转发过的布尔指示标志，D_iface_list表示依次接收到本条消息时的各个接口的地址的列表，D_time表示本数组的有效期满时间，在期满时间结束时必须删除本数组。一个节点的拷贝数组集合就是该节点的“拷贝集合”。

在本小节，将“消息源节点地址”用作发送本条消息的节点的主地址，将“发送节点接口地址”用作发送本条消息的接口的发送节点地址（假定在包含本条消息的本分组的IP头中），将“接收接口地址”用作接收本条消息的节点的接口地址。

因此，一个节点接收到一个基本分组后，必须对其中封装的每条消息执行以下操作：

第一步，假如该分组没有包含任何消息（即：分组长度小于或者等于分组头的长度），则必须丢掉该分组。对于IPv4地址，这就意味着分组长度小于16字节的分组必须丢掉。

第二步，假如本条消息的TTL小于或者等于0，或者假如本条消息是该节点发送的（即本条消息的消息源节点地址等于本节点的主地址），则必须丢掉该分组。

第三步，处理条件如下：

（1）假如本拷贝集合中存在一个数组，使得同时满足

● D_addr == Originator Address(本条消息的消息源节点地址)；

● D_seq_num == Message Sequence Number（本条消息的消息序列号）。

则本条消息已经被完全处理过，不必再处理。

（2）否则，假如该节点认可本条消息的消息类型，则必须按照本条消息所属类型的规范进行处理。

第四步，转发条件如下：

（1）假如本拷贝集合中存在一个数组，使得同时满足

● D_addr == Originator Address(本条消息的消息源节点地址)；

● D_seq_num == Message Sequence Number（本条消息的消息序列号）；

● 接收接口地址在D_iface_list列表中。

则本条消息已经被考虑转发过，不必再转发。

（2）否则：

● 假如该节点认可本条消息的消息类型，则必须按照本条消息所属类型的规范考虑转发该条消息。

● 否则（即该节点不认可本条消息的消息类型），则应该按照下面描述的默认转发算法处理该条消息。

默认转发算法描述如下：

第一步，假如在该节点的对称一跳相邻区域内没有检测到本条消息的发送节点接口地址，则必须就此停止执行本转发算法，也不必转发本条消息。

第二步，假如本拷贝集合中存在一个数组，使得同时满足

● D_addr == Originator Address(本条消息的消息源节点地址)；

● D_seq_num == Message Sequence Number（本条消息的消息序列号）。

那么当且仅当同时满足下列条件时应该进一步考虑本条消息的转发：

● 标志D_retransmitted设为false（假）；

● 接收本条消息的接口（地址）不在D_iface_list列表中。

第三步，否则，假如本拷贝集合中不存在这样的条目，则进一步考虑本条消息的转发。

假如经过上述三步的处理后不再考虑本条消息的转发，则本节点的处理就此完毕（即随后的第四步到第八步的处理被忽略）；否则，假如仍然继续考虑本条消息的转发，则采用以下算法：

第四步，假如发送节点接口地址等于本节点一个MPR选择器的地址，并且本条消息的TTL大于1，则必须转发本条消息（见随后的第六步到第八步）。

第五步，假如本拷贝集合中存在一个条目，具有相同的消息源节点地址、相同的消息序列号，那么本条目更新如下：

● D_time = current time + DUP_HOLD_TIME；

● 将该接收接口（地址）添加到D_iface_list列表中；

● 将标志D_retransmitted设为true（真）。

否则，在本拷贝集合中记录一个条目如下：

● D_addr = Originator Address(本条消息的消息源节点地址)；

● D_seq_num = Message Sequence Number（本条消息的消息序列号）；

● D_time = current time + DUP_HOLD_TIME；

● D_iface_list包含该接收接口地址；

● 当且仅当按照第四步转发本条消息，则将标志D_retransmitted设为真。

假如当且仅当按照第四步必须转发本条消息，则执行下一步操作：

第六步，将本条消息的TTL减1。

第七步，将本条消息的跳数加1。

第八步，将本条消息广播到所有的接口上（注意：本条消息的其余组成域保持不变）。

应该注意，消息的处理和转发是两种不同的操作，取决于不同规则。消息的处理涉及消息内容的利用，而消息的转发则涉及将同一条消息转发给网络中的其他节点。

本规范包含每种已知消息类型的转发和处理。使用OLSR默认转发算法时不必盲目地转发类型已知的消息。转发以及正确设置被转发已知消息的消息头是OLSR默认转发算法完成的任务，即详细说明如何处理该消息，假如必要的话还要详细说明如何转发该消息。这就能够为消息指定消息类型，使得消息在传输过程中能够被修改（例如反映该消息已经通过的路由信息）。假如由于某种原因而需要经典泛洪一条消息，则可以将MPR泛洪机制关闭。经典泛洪法详细说明了如何处理消息：对消息采取简单地重复广播，而与MPR无关。

通过定义一个消息类型集合，就可能给OLSR协议引入其他的消息类型，而同时仍然能够保持兼容以前的版本。定义的消息类型集合必须被所有的OLSR协议实现所认识。OLSR协议内核功能要求的消息类型如下：

● HELLO消息：用于完成链路探测、相邻节点探测、以及MPR信令任务；

● TC消息：用于完成拓扑声明任务（广播链路状态）；

● MID消息：用于完成声明一个节点存在多个接口的任务。

其他消息类型见随后小节，以及今后可能增加诸如使能节能/休眠方式、多目标路由、单向链路支持、自动配置/地址分配等消息类型。

5）消息发送与抖动时间

作为一个基本的实现要求，应该避免控制消息的同步。因此，OLSR控制消息的发送应该避免同步。

由于各种原因（主要是分组处理的定时器相互作用的缘故），将所接收到的相邻节点的控制消息重新发送出去可能需要同步，以便若干个相邻节点同时尝试发送控制消息。根据链路层的特点，这可能会引起碰撞，以及由此产生的分组丢失，可能丢失随后同一类型的数条消息。

采用如下消息发送控制策略避免这种发送同步问题。一个节点应该给消息的产生间隔时间添加一定的抖动时间（Jitter）。对于每条产生的消息，其抖动时间必须是一个随机数值。因此，对于使用抖动时间的一个节点，则有：

消息的实际间隔时间 = MESSAGE_INTERVAL（消息间隔时间）−抖动时间

其中：抖动时间是一个从[0，MAXJITTER]范围内随机选出的数值，MAXJITTER表示最大抖动时间；MESSAGE_INTERVAL（消息间隔时间）是为发送本条消息而指定的消息间隔时间（例如HELLO_INTERVAL（HELLO消息发送间隔时间）、TC_INTERVAL（TC消息发送间隔时间），等等）。

转发消息的时候也应该引入抖动时间。可以采用下列简单策略：当一条消息被一个节点转发的时候，该条消息应该在该节点中保存如下长度的一段时间：

消息保存时间 = 抖动时间（Jitter）

其中：抖动时间是一个从[0，MAXJITTER]范围内随机选出的数值。

当一个节点发送一条控制消息时，可以顺便携带其他的消息（在其保存时间结束之前），以便减少分组的传输数量。

注意：采用最小控制消息发送速率。假如有利于特定的应用，那么节点可以采用较高速率发送控制消息。

2.信息的存储

每个节点通过交换OLSR控制消息积累网络信息。按照下列描述存储网络信息。

1）多接口关联信息库

为网络中的每个目的节点记录一个“接口关联数组（Interface Association Tuple）”（I_iface_addr，I_main_addr，I_time），其中：I_iface_addr表示一个节点的一个接口地址；I_main_addr表示该节点的主地址；I_time表示该数组的有效期满时间，期满时间结束后必须删除该数组。在一个节点中，其“接口关联集合”等于接口关联数组集合。

2）链路探测：本地链路信息库

本地链路信息库存储到达相邻节点的有关链路的信息。

一个节点记录一个“链路数组（Link Tuple）”集合。链路数组为（L_local_iface_addr，L_neighbor_iface_addr，L_SYM_time，L_ASYM_time，L_time），其中：L_local_iface_addr表示本地节点（即本条链路的一个端节点）的接口地址；L_neighbor_iface_addr表示相邻节点（即本条链的另一个端节点）的接口地址；L_SYM_time表示认为本条链路为对称链路的有效时间长度；L_ASYM_time表示认为能够接收到本条链路相邻节点的相邻节点接口上的信息的有效时间长度；L_time表示本数组有效期满时间，期满时间结束后必须删除本数组。当L_SYM_time和L_ASYM_time的有效时间均已经结束时，则认为本条链路丢失。当在HELLO消息中声明相邻节点接口时就需要使用链路数组集合信息。

参数L_SYM_time用来决定所声明的相邻节点接口的链路类型：假如L_SYM_time有效时间没有结束，则必须声明本条链路是对称链路；假如L_SYM_time有效时间已经结束，则必须声明本条链路是非对称链路；假如L_SYM_time和L_ASYM_time的有效时间均已经结束时，则必须声明本条链路已经丢失。在一个节点中，其“链路集合”等于链路数组集合。

3）相邻节点探测：相邻区域信息库

相邻区域信息库存储有关相邻节点、二跳相邻节点、MPR，以及MPR选择器的信息。

（1）相邻节点集。一个节点记录一个“相邻节点数组”集合，用于其相邻节点的描述。相邻节点数组为（N_neighbor_main_addr，N_status，N_willingness），其中：N_neighbor_main_addr表示一个相邻节点的主地址；N_status说明该相邻节点是对称（SYM）的，还是非对称的（NOT_SYM）；N_willingness是位于[0，7]之间的一个整数，说明该节点是否愿意承载其他节点的信息及其愿意程度。

（2）二跳相邻节点集。一个节点记录一个“二跳相邻节点数组”集合，用于其相邻节点和对称二跳相邻区域之间的对称链路描述（以及根据定义，MPR链路也是对称链，因此还包含MPR的描述）。二跳相邻节点数组为（N_neighbor_main_addr，N_2hop_addr，N_time），其中：N_neighbor_main_addr表示一个相邻节点的主地址；N_2hop_addr表示一个具有对称链路到达N_neighbor_main_addr的二跳相邻节点的主地址；N_time表示本数组有效期满时间，期满时间结束后必须删除本数组。在一个节点中，其“二跳相邻节点集合”等于二跳相邻节点数组集合。

（3）MPR集。一个节点维护一个被选作MPR的相邻节点的集合，各个相邻节点的主地址被列在MPR集合中。

（4）MPR选择器集。一个节点记录一个MPR选择器数组集合，用于已经将本节点选作MPR的相邻节点的描述。MPR选择器数组为（MS_main_addr，MS_time），其中：MS_main_addr表示一个已经将本节点选作MPR的节点的主地址；MS_time表示本数组有效期满时间，期满时间结束后必须删除本数组。在一个节点中，其“MPR选择器集合”等于MPR选择器数组集合。

4）拓扑信息库

网络中的每个节点均维护网络拓扑信息。从TC消息中获取网络拓扑信息，并用于路由表的计算。

因此，对于网络中的每个目的节点，至少记录一个“拓扑数组”（T_dest_addr，T_last_addr，T_seq，T_time），其中：T_dest_addr表示从主地址T_last_addr节点能够一跳到达的一个节点的主地址，通常情况下T_last_addr节点就是T_dest_addr节点的一个MPR；T_seq表示一个序列号；T_time表示本数组有效期满时间，期满时间结束后必须删除本数组。在一个节点中，其“拓扑集合”等于拓扑数组集合。

3.主地址与多接口

对于单OLSR接口节点，其主地址等于该OLSR接口地址。但是，对于多OLSR接口节点，则通过交换MID消息来定义其各个OLSR接口地址和相应主地址之间的关系。下面描述如何交换和处理MID消息。

每个具有多个接口的节点必须周期性地将其接口配置广播给网络中的其他节点。这不是通过MPR泛洪机制、而是通过将MID消息泛洪到网络中的所有节点来实现。

网络中的每个节点维护网络中其他节点的接口信息。从MID消息中获取其他节点的接口信息，并用于路由表的计算。

特别地，多接口声明MID将一个节点的多个接口的地址（而且也涉及到该节点的主地址）填写到每个节点的多接口关联库中。

1）多接口声明（MID）消息的格式

一条MID消息的格式如图4-2所示。

MID消息作为前面描述的通用分组格式中的数据组成部分来发送，其“消息类型”设为MID_MESSAGE（MID消息类型）；TTL应该设为最大值255，以便于将本条消息广播到整个网络中；Vtime相应地设为MID_HOLD_TIME（MID消息保持时间）。

图4-2中的“OLSR接口地址”域包含本节点的一个OLSR接口的地址，但是不包含本节点主地址（已经在消息源节点地址域中表示本节点的主地址）。

除了消息源节点主地址以外，将所有的接口地址都放在MID消息中。假如已经达到所允许的消息长度的最大值，但是仍然还有接口地址不能放入到本MID消息中，则需要产生多条MID消息，直到将全部接口地址发送完毕为止。

2）MID消息的产生

一个节点向网络中发送一条MID消息，用于声明其多个接口信息（假定该节点有多个接口）。例如，一条MID消息包含跟其主地址有关的一张接口地址列表。这个接口地址列表可以作为每条MID消息的一个组成部分（例如由于网络规定的消息长度限制），但是必须在一定的刷新周期（MID_INTERVAL）内完成对描述一个节点的接口集合的全部MID消息的分析。通过MID消息发送到网络中的接口信息有助于每个节点计算其路由表。只有一个接口地址的MANET网络节点（即运行OLSR协议的MANET网络节点）不必产生任何MID消息。

一个节点尽管有多个接口，但是其中只有一个接口参与MANET网络和运行OLSR协议（例如一个节点连接有线网络，同时又连接一个MANET网络），则不必产生任何MID消息。

一个节点有多个接口，其中多个接口参与MANET网络和运行OLSR协议，则必须按照规定产生MID消息。

3）MID消息的转发

MID消息被MPR广播和转发，以便于传播到整个网络中。必须采用“默认转发算法”转发MID消息。

4）MID消息的处理

采用通过MID消息交换的信息来记录多接口关联集合中的数组。

接收到一条MID消息后，必须根据该消息头中接收信息有效时间域（Vtime）计算“有效时间”。按照如下步骤和规则更新多接口关联信息库。

第一，假如本条消息的发送节点接口（注意：不是消息的源节点）不在本节点的对称一跳相邻区域内，则必须丢掉本条消息。

第二，对于本条MID消息中列出的每个接口地址：

（1）假如接口关联集合中存在一个数组同时满足以下条件：

● I_iface_addr == interface address（接口地址）；

● I_main_addr == originator address（本条消息的源节点地址）。

那么，将本数组的保持时间设为：

I_time = current time + validity time。

（2）否则，则在接口关联集合中记录一个新的数组：

● I_iface_addr = interface address（接口地址）；

● I_main_addr = originator address（本条消息的源节点地址）；

● I_time = current time + validity time。

5）根据一个接口地址解析主地址

一般情况下，OLSR协议中要求使用“接口地址”的唯一组成部分是链路探测。OLSR协议的其余组成部分对节点起作用，由其“主地址”唯一确认（一个节点的主地址就是其“节点识别码ID”，为了方便起见，这个主地址等于其中一个接口的地址）。如果一个网络的每个节点只有一个接口，那么根据定义，每个节点的主地址就等于该节点的那个接口的地址。假如一个网络的节点具有多个接口，并且在一个公共OLSR区域内工作，则要求能够将任意一个接口地址映射为相应的主地址。

MID消息的交换提供一种方法，用于网络节点获取接口信息。因此，假如已知一个节点的其中一个接口地址，则有可能识别出该节点的“主地址”。

给定一个接口地址：

（1）假如接口关联集合中存在一个数组满足：

I_iface_addr = interface address（接口地址）

那么，搜索主地址的结果就是该数组的源节点地址I_main_addr。

（2）否则，搜索主地址的结果就是该接口地址本身。

4.HELLO消息的格式与产生

采用一个公共机制来建立本地链路信息库和相邻区域信息库，这个机制就是周期性交换HELLO消息。下面描述一般性的HELLO消息机制。

1）HELLO消息的格式

采用一种类似于通用分组格式的方法提供链路探测、相邻区域探测、MPR选择信令，以及今后的协议扩充。HELLO消息的格式如图4-3所示。

HELLO消息作为前面描述的通用分组格式中的数据组成部分来发送，其“消息类型”被设为HELLO_MESSAGE（HELLO消息类型），TTL设为1，Vtime相应地设为NEIGHB_HOLD_TIME（HELLO消息保持时间）。对图4-3的各个组成域详细说明如下：

（1）保留（Reserved）：保留域必须设为全0，以便与本规范保持一致。

（2）HELLO消息发送周期（Htime）：本域指定本节点在某个特定接口上发送HELLO消息的间隔时间，即发送下一条HELLO消息之前的时间。可以将这个时间信息用于链路探测。HELLO消息发送间隔时间用本域高部4比特表示的尾数和本域低部4比特表示的指数来共同表示，即：

HELLO消息发送周期 = C×(1+a/16)×2b（秒）

其中：a表示本域高部4比特表示的整数，b表示本域低部4比特表示的整数。比例因子C的建议值见4.1.5节。

（3）愿意（Willingness）：本域说明一个节点愿意承载和转发其他节点的信息。一个将本域设为WILL_NEVER（总是不愿意）的节点决不会被任何节点选作MPR。一个将本域设为WILL_ALWAYS（总是愿意）的节点必定总是被选作MPR。在默认情况下，一个节点应该广播本域为WILL_DEFAULT（默认）。

（4）链路编码（Link Code）：本域说明发送节点接口与随后相邻节点接口列表之间的有关链路信息。本域也可以说明一个相邻节点的有关状态信息。丢掉节点不认识的链路编码。

（5）链路消息长度（Link Message Size）：本域表示一条链路消息的长度，单位是字节，从“链路编码”域开头开始计算，到下一个“链路编码”域开始时结束长度计算（假如不存在多种链路类型，则到本条消息结尾处结束长度计算）。

（6）相邻节点接口地址（Neighbor Interface Address）：本域表示一个相邻节点的其中一个接口的地址。

下面根据链路类型和相邻节点类型的链路编码，说明小于16的链路编码的处理。假如链路编码小于或者等于15，则必须按照两个不同的域（每个域长2比特）来解释该链路编码，如图4-4所示。

OLSR协议需要如下四种“链路类型”：

（1）UNSPEC_LINK：表示没有特定信息的链路。

（2）ASYM_LINK：表示非对称链路（即相邻节点接口能够接收的链路）。

（3）SYM_LINK：表示使用该接口的链路是对称链路。

（4）LOST_LINK：表示该条链路已经丢失。

OLSR协议需要如下三种“相邻节点类型”：

（1）SYM_NEIGH：表示这些相邻节点与本节点之间至少有一条对称链路。

（2）MPR_NEIGH：表示这些相邻节点至少有一条对称链路到达本发送节点，而且这些相邻节点已经被本发送节点选作MPR。

（3）NOT_NEIGH：表示这些节点不再是对称相邻节点或者至今还未变成对称相邻节点。

在具体实现中，应该细心，既不要混淆链路类型和相邻节点类型，也不要混淆各个常数（比如，混淆SYM_NEIGH和SYM_LINK）。

同时满足下列条件的一个链路编码广播是无效的：

（1）Link Type == SYM_LINK（对称链）；

（2）Neighbor Type == NOT_NEIGH（非对称相邻节点）。

必须丢掉这样广播的任何链路，无需对其做任何处理。

同样，不等于SYM_NEIGH（对称相邻节点）、MPR_NEIGH（MPR相邻节点）、NOT_NEIGH（非对称相邻节点）的相邻节点类型无效。必须丢掉这样广播的任何链路，无需对其做任何处理。

2）HELLO消息的产生

HELLO消息的产生涉及到链路集合、相邻节点集合，以及MPR集合的发送。原则上，一条HELLO消息完成以下三个独立的任务：链路探测，相邻节点探测，MPR选择信令。

三个任务都是基于一个节点相邻区域内的周期性信息交换来提供“本地拓扑建立”服务。因此，根据本地链路信息库中的本地链路集合、相邻节点集合，以及MPR集合中存储的信息产生HELLO消息。

一个节点必须在每个接口上进行链路探测，以便检测该接口与相邻节点接口之间的链路。为了进行相邻节点探测，一个节点必须将其整个对称一跳相邻区域广播到每个接口上。因此，对于一个给定接口，一条HELLO消息包含该接口上（跟链路类型有关）的链路列表，以及整个相邻区域（跟相邻节点类型有关）的列表。

HELLO消息各个组成域的设置是：将接收信息有效时间（Vtime）域设为本节点参数NEIGHB_HOLD_TIME的数值；将HELLO消息发送周期（Htime）域设为本节点参数HELLO_INTERVAL的数值；将愿意（Willingness）域设为本节点的愿意设置，以便转发其他节点的信息。

在一条HELLO消息中声明的地址列表是相邻节点接口地址列表，其计算如下：

对于链路集合中的每个数组，若L_local_iface_addr等于本条HELLO消息发往的接口的地址，L_time≥当前时间（即有效时间还没有结束），则广播L_neighbor_iface_addr，其设置如下：

第一步，链路类型设置如下：

（1）若L_SYM_time≥current time（有效时间还没有结束），则设置Link Type =SYM_LINK（对称链路）。

（2）否则，若L_ASYM_time ≥ current time（有效时间还没有结束），并且L_SYM_time <current time（有效时间已经结束），则设置Link Type = ASYM_LINK（非对称链路）。

（3）否则，若L_ASYM_time < current time（有效时间已经结束），并且L_SYM_time < current time（有效时间已经结束），则设置Link Type = LOST_LINK（丢失链路）。

第二步，相邻节点类型设置如下：

（1）若MPR集合包含等于L_neighbor_iface_addr的主地址，则：Neighbor Type = MPR_NEIGH（MPR相邻节点）。

（2）否则，若相邻节点集合包含等于L_neighbor_iface_addr的主地址，则：

● 若N_status == SYM，则设置Neighbor Type = SYM_NEIGH（对称相邻节点）。

● 否则，若N_status == NOT_SYM，则设置Neighbor Type = NOT_NEIGH（非对称相邻节点）。

对于相邻节点集合中的每个数组，采用前述算法已经广播的一个关联链路数组不存在相应的L_neighbor_iface_addr地址，则随同下列链路类型和相邻节点类型信息一起广播N_neighbor_main_addr：①Link Type = UNSPEC_LINK；②相邻节点类型按照上述第二步方法设置。

对于一个单OLSR接口的节点，其主地址等于该OLSR接口的地址，即，对于一个单OLSR接口节点，对应于L_neighbor_iface_addr地址的主地址就是L_neighbor_iface_addr地址。

一条HELLO消息可能被分成若干块（由于系统规定的消息长度有限）发送到每个接口上，其规则如下：在一个预先规定的刷新周期REFRESH_INTERVAL内，每条链路和每个相邻节点必须至少引用一次。为了保持跟踪连通性的快速变化，在每个HELLO_INTERVAL周期内至少必须发送一条HELLO消息，HELLO_INTERVAL周期小于或者等于刷新周期REFRESH_INTERVA。

为了限制控制消息丢失造成的影响，尽量将一条消息（包括通用分组头）封装到一个MAC分组中。

3）HELLO消息的转发

产生的每条HELLO消息由其源节点广播到与其相邻节点连接的一个接口上（即，该条HELLO消息就是为该接口产生的）。HELLO消息决不能被转发。

4）HELLO消息的处理

节点处理其接收到的HELLO消息，以便引导链路探测、相邻节点探测，以及MPR选择器集合的建立。

5.链路探测

链路探测的作用是建立本地链路信息库。链路探测只涉及到OLSR接口地址以及在OLSR接口之间交换分组的能力。链路探测机制就是周期性地交换HELLO消息。

使用到达相邻节点的各条链路构成链路集合。链路集合的生成过程就是“链路探测”，通过HELLO消息的交换来实现，从而更新每个节点的本地链路信息库。

网络中的每个节点应该探测其与各个相邻节点之间的各条链路。无线传播的不确定性可能使某些链路是单向链路。因此，必须从两个方向检查所有的链路，以便于考虑链路的有效性。采用一对接口来描述一条“链路”：一个本地接口和一个远端接口。

为了进行链路探测，必须使用某种相关状态表示每个相邻节点（更确切地说，到达每个相邻节点的一条链路）当前所在的状态：或者“对称”状态，或者“非对称”状态。“对称”状态表示到达该相邻节点的链路已经被证实是双向链路，即可以从两个方向发送数据。“非对称”状态表示本节点发出的HELLO消息已经被该相邻节点接收到（即该相邻节点能够接收到本节点发送的信息），但是不能肯定本节点能够接收消息（即不能肯定本节点是否能够接收到该相邻节点发送的信息）。通过链路探测获得的信息以及链路探测使用的信息均记录在链路集合中。

一条HELLO消息的“消息源节点地址”就是发送本条消息的节点的主地址。一个节点接收到一条HELLO消息后，应该更新其链路集合。注意：HELLO消息决不能被转发，也决不能被记录在拷贝集合中。

一条HELLO消息被接收后，必须根据本条消息头部的接收信息有效时间（Vtime）域计算其“有效时间（Validity Time）”，然后按照以下方法更新链路集合：

第一，一条HELLO消息被接收后，若不存在满足如下条件的链路数组：

L_neighbor_iface_addr == Source Address（源节点地址），

则产生如下一个新链路数组：

L_neighbor_iface_addr = Source Address（源节点地址）；

L_local_iface_addr = 接收到本条HELLO消息的接口地址；

L_SYM_time = current time -1 (已经期满)；

L_time = current time + validity time。

第二，若链路数组（现有的或者新的）满足如下条件：

L_neighbor_iface_addr == Source Address（源节点地址），

则按照下列方法更新该链路数组：

（1）L_ASYM_time = current time + validity time；

（2）若该节点发现本条链路消息中列出的地址中包含接收到本条HELLO消息的接口的地址，则修改本链路数组如下：

● 若链路类型等于LOST_LINK（链路已丢失），则

L_SYM_time = current time -1 (即，已经期满)。

● 若链路类型等于SYM_LINK（对称链路）或者ASYM_LINK（非对称链路），则

L_SYM_time = current time + validity time，

L_time = L_SYM_time + NEIGHB_HOLD_TIME。

（3）L_time = max(L_time，L_ASYM_time)。

L_time的设置规则如下：至少在所产生的本条HELLO消息中所广播的一个“有效时间”周期内，仍然应该继续广播失去对称性的链路。这样相邻节点才能够检测出链路中断。

6.相邻节点探测

相邻节点探测的作用是建立相邻区域信息库。相邻节点探测涉及到各个节点及其主地址。相邻节点探测机制就是周期性交换HELLO消息。

1）相邻节点集的生成

一个节点根据链路数组维护一个相邻节点数组集合。根据链路集合的变化更新相应信息。链路集合保存有关链路的信息，而相邻节点集合保存有关相邻节点的信息。这两个集合之间的关系非常明显，这是因为当且仅当一个节点和另一个节点之间至少存在一条链路时，那么这个节点就是另外一个节点的一个相邻节点。

现将链路和相邻节点之间的正式关系定义如下：

一个链路数组的“关联相邻节点数组（associated neighbor tuple）”若存在的话，则等于该相邻节点数组，其中N_neighbor_main_addr == L_neighbor_iface_addr的主地址。

一个相邻节点数组的“关联链路数组（associated link tuples）”等于所有的链路数组，其中N_neighbor_main_addr == L_neighbor_iface_addr的主地址。

必须通过维护链路数组和关联相邻节点数组之间的适当关系来建立相邻节点集合，具体如下：（1）数组建立（Creation）。每当出现一条链路的时候，也就是每当建立一个链路数组的时候，假如其关联相邻节点数组不存在，则必须建立，采用的数值如下：

N_neighbor_main_addr = L_neighbor_iface_addr的主地址(来自本链路数组)

无论如何，必须按照下面描述的操作步骤计算N_status（该相邻节点的状态）。

（2）更新（Update）。每当一条链路变化时，也就是每当一个链路数组的信息被修改的时候，该节点必须确保其关联相邻节点数组的状态N_status满足以下特性：

假如该相邻节点有一个关联链路数组指出一条对称链路（即：L_SYM_time ≥ current time（当前时间）），则将N_status设为SYM（对称相邻节点）；否则，将N_status设为NOT_SYM（非对称相邻节点）。

（3）删除（Removal）。每当一条链路被删除时，也就是每当一个链路数组被删除时，若其关联相邻节点数组不再有任何关联链路数组，则必须将其删除。

这些规则确保每个链路数组严格存在一个关联相邻节点数组，以及每个相邻节点数组至少有一个关联链路数组。

对HELLO消息的处理描述如下：

一条HELLO消息的“消息源节点地址”等于产生和发送本条消息的节点的主地址。同样，必须根据该条HELLO消息的愿意组成域设置计算“愿意”设置。

一个节点接收到一条HELLO消息后，应该按照前面描述的方法首先更新其链路集合，然后应该按照如下方法更新其相邻节点集合：

若消息源节点地址等于相邻节点集合中一个相邻节点数组中的N_neighbor_main_addr，则应该更新该相邻节点数组：N_willingness = 本条HELLO消息中的willingness。

2）二跳相邻节点集的生成

二跳相邻节点集合描述有一条对称链路到达一个对称相邻节点的节点的集合。通过如下描述的周期性交换HELLO消息来维护该信息集合。

一条HELLO消息的“消息源节点地址”等于产生和发送本条消息的节点的主地址。一个节点接收到一个对称相邻节点发送来的一条HELLO消息后，应该更新其二跳相邻节点集合。再次提请注意：HELLO消息决不能被转发，也决不能被记录到拷贝集合中。

接收到一条HELLO消息后，必须根据本条消息头部的接收信息有效时间（Vtime）域计算其“有效时间（Validity Time）”。

若消息源节点地址等于链路集合中一个链路数组中的L_neighbor_iface_addr，并且L_SYM_time ≥ current time (有效时间还没有结束)，换句话说，若消息源节点地址是一个对称相邻节点，则应该按照如下方法更新二跳相邻节点集合：

第一，对于本条HELLO消息中列出的每个地址（下面用二跳相邻节点地址描述），并且其相邻节点类型等于SYM_NEIGH（对称相邻节点）或者MPR_NEIGH（MPR相邻节点）：

（1）若该二跳相邻节点地址的主地址等于该接收节点的主地址，则丢掉该二跳相邻节点地址。

（2）否则，建立一个满足以下条件的二跳相邻节点数组：

● N_neighbor_main_addr = Originator Address（本条消息的源节点地址）；

● N_2hop_addr = 该二跳相邻节点的主地址；

● N_time = current time + validity time。

该数组可以替代具有相同N_neighbor_main_addr和N_2hop_addr的类似的旧数组。

第二，对于本条HELLO消息中列出的每个地址，并且其相邻节点类型等于NOT_NEIGH（非对称相邻节点），删除同时满足以下条件的全部二跳相邻节点数组：

● N_neighbor_main_addr == Originator Address（本条消息的源节点地址）；

● N_2hop_addr == 该二跳相邻节点的主地址。

3）MPR集的生成

MPR用于将控制消息从一个节点泛洪到整个网络，同时减少某个区域内的重传次数。因此，MPR概念是经典泛洪机制的一种优化。

网络中的每个节点独立地从其对称一跳相邻区域内选择自己的MPR。将各个MPR之间的对称链路及其链路类型MPR_NEIGH（用MPR相邻节点替代SYN_NEIGH链路类型）写入HELLO消息中，再将该HELLO消息广播出去。

一个节点必须按照如下方法计算其MPR集合：该节点通过其MPR集合中的相邻节点能够到达所有对称严格二跳相邻节点。（注意：若节点A是另一个节点B的直接相邻节点，则节点A不是节点B的严格二跳相邻节点）。这就意味着：各个MPR节点的对称一跳相邻区域组合在一起，则包含这个对称严格二跳相邻区域。

当对称相邻区域或者对称严格二跳相邻区域发生变化的时候，则应该重新计算MPR集合。计算出每个接口的MPR，再将每个接口的MPR集合组合在一起构成本节点的MPR集合。

尽管没有必要使MPR集合最小，但是通过选定的MPR节点能够到达所有严格二跳相邻节点则是必要的。一个节点选定的MPR集合应该让任何严格二跳相邻节点至少被一个MPR节点所覆盖。将MPR集合保持最小确保OLSR协议的开销保持在最低程度。

MPR集合能够与整个对称相邻节点集合保持一致。网络初始化的时候就是这样（而且符合经典链路状态路由）。

下面说明选择MPR的一种搜索方法。建立一个MPR集合，使得一个节点通过一个MPR节点的转发能够到达对称严格二跳相邻区域中的任何一个节点，该MPR节点被设置成愿意为其他节点转发信息。必须对每个接口I应用这个搜索。一个节点的MPR集合就是为每个接口建立的MPR集合的组合。描述该搜索方法时采用了如下术语：

（1）一个接口的相邻节点。假如一个本地节点上的一个接口存在一条链路到达一个相邻节点的任何一个接口，那么这个本地节点就是“该接口的一个相邻节点”。

（2）从一个接口可达的二跳相邻节点。指一个节点的二跳相邻节点列表，从该接口的相邻节点可达该节点。

（3）一个接口的MPR集合：指一个接口的相邻节点集合（子集），这些相邻节点被设置成愿意为其他节点转发信息，通过这些选定的相邻节点，从该接口可达所有严格二跳相邻节点。

（4）集合N。表示一个节点的相邻节点子集，这些相邻节点是每个接口I的相邻节点。

（5）集合N2。表示从每个接口I可达的二跳相邻节点集合，但是不包括：

● 只能通过集合N的不愿意为其他节点转发信息的成员节点到达的那些节点；

● 正在执行该MPR计算的那个节点；

● 全部对称相邻节点。对于这些相邻节点，在某个接口上存在一条链路到达该节点。

（6）D(y)。表示一个一跳相邻节点y的密度（这里y是集合N中的一个成员节点），定义为节点y的对称相邻节点的数量，但是不包含集合N的所有成员节点以及正在执行该MPR计算的那个节点。

OLSR协议的搜索方法如下：

第一，从一个MPR集合开始计算，该MPR集合由集合N的全部成员节点组成，其N_willingness域设为WILL_ALWAYS（总是愿意为其他节点转发信息）。

第二，计算集合N中所有节点的D(y)，y是集合N中的一个成员节点。

第三，将集合N中如下成员节点添加到MPR集合中：它们是提供可达集合N2中的一个节点的唯一节点。例如，若集合N2中的节点B只能通过到达集合N中的节点A的一条对称链路到达，那么将节点A添加到MPR集合中。删除集合N2中的那些现在已经被MPR集合中的一个节点所覆盖的节点。

第四，尽管集合N2中仍然存在未被MPR集合中任何节点所覆盖的节点，但是：

（1）对于集合N中的每个节点，计算其可达性，即，集合N2中仍然未被MPR集合中任何节点所覆盖的、但是通过该一跳相邻节点可达的节点的数量；

（2）从集合N中选择一个节点作为MPR，该节点的愿意程度在集合N中最高，而且可达性不等于0。存在多种选择时，则选择到达集合N2中节点的数量最多的那个节点。若存在多个节点提供相同数量的可达性，则选择作为MPR的那个节点，其D(y)较大。删除集合N2中的那些现在已经被MPR集合中的一个节点所覆盖的节点。

第五，将一个节点的每个接口的MPR集合组合在一起，则建立该节点的MPR集合。作为一种优化，以递增愿意参数N_willingness的方式依次处理MPR集合中的每个节点y。假如N2集合中的所有节点仍然被MPR集合中至少一个节点所覆盖（节点y除外），而且假如节点y的愿意参数N_willingness小于WILL_ALWAYS，那么可以从MPR集合中删除节点y。

也可能有其他算法，也可能对本算法进行改进。例如，在一个多接口方案中，节点A和节点B之间存在多条链路。若节点A为其一个接口选择节点B作为MPR，则节点B可以被节点A的任何其他接口选择作为MPR而不会造成其他的性能损失。

4）MPR选择器集的生成

一个节点n的MPR选择器集合由已经将节点n选作MPR的节点的主地址构成。通过发送HELLO消息来通知MPR的选择。

一个节点接收到一条HELLO消息后，若从本条HELLO消息列表中找到自己的其中一个接口地址的相邻节点类型为MPR_NEIGH（MPR相邻节点），则必须将本条HELLO消息中的信息记录到MPR选择器集合中。

必须根据本条HELLO消息头部的接收信息有效时间（Vtime）域计算其“有效时间（Validity Time）”，然后应该按照以下方法更新MPR选择器集合：

第一，若不存在“MS_main_addr == Originator Address（本条HELLO消息的源节点地址）”的MPR选择器数组，则产生一个“MS_main_addr = Originator Address”的新MPR选择器数组。

第二，然后将满足“MS_main_addr == Originator Address”的MPR选择器数组（新的或者原有的）作如下修改：MS_time = current time + validity time。

按照下面的“相邻区域和二跳相邻区域变化”的描述，删除定时器时间已经结束或者链路已经中断的MPR选择器数组。

5）相邻区域和二跳相邻区域的变化

在以下情况下检测到相邻区域内发生了变化：

（1）一个链路数组的L_SYM_time域时间已经结束。假如这个期满链路数组描述的链路是连接一个相邻节点的最后一条链路（与此相反的是，连接一个接口的一条链路可能已经中断，同时连接这个相邻节点的另一个接口的一条链路仍然存在，不会将这种变化情况认为是发生了相邻区域变化），则认为这种相邻区域变化情况已经导致一个相邻节点丢失。

（2）在链路集合中添加了一个其L_SYM_time域时间还没有结束的新链路数组，或者对链路集合中一个L_SYM_time域时间已经结束的链路数组作了修改而使其L_SYM_time域时间变成没有结束。假如还不存在描述连接一个相邻节点的一条链路的链路数组，则认为这种相邻区域变化情况出现了这个相邻节点。

当一个二跳相邻节点数组期满结束时，或者一个二跳相邻节点数组被删除时，则检测出二跳相邻区域内发生了变化。

当相邻区域或者二跳相邻区域内发生变化时，进行以下处理：

（1）发生相邻节点丢失时，其N_neighbor_main_addr等于该丢失相邻节点主地址的所有二跳相邻节点数组必须被删除。

（2）发生相邻节点丢失时，其MS_main_addr等于该丢失相邻节点主地址的所有MPR选择器数组必须被删除。

（3）当检测出丢失或者出现一个相邻节点时，或者当检测出二跳相邻区域内发生了变化时，必须重新计算MPR集合。

（4）当MPR集合变化时，可以为此单独发送一条HELLO消息。

7.拓扑建立

OLSR协议的链路探测和相邻节点探测基本上为每个节点提供了一张相邻节点列表、分组格式和分组转发、MPR优化泛洪机制，使用这张相邻节点列表可以直接进行通信。在此基础之上，将拓扑信息传播到整个网络中。下面描述链路探测和相邻节点探测得到的哪些信息需要被传播到整个网络中，以及如何被用来建立路由。

1）TC消息的格式

拓扑控制（Topology Control，TC）消息的格式如图4-5所示。

TC消息作为前面描述的通用分组格式中的数据组成部分来发送，其“消息类型”被设为TC_MESSAGE（TC消息类型）；TTL应该设为最大值255，以便于将本条消息传播到整个网络中；Vtime相应地设为TOP_HOLD_TIME（TC消息保持时间）。对图4-5的各个组成域详细说明如下：

（1）广播相邻节点序列号（Advertised Neighbor Sequence Number，ANSN）。本域表示与一个广播相邻节点集合有关的序列号。一个节点每当检测出其广播相邻节点集合发生变化后，递增其序列号（对返转问题的处理见4.1.6节）。发送ANSN是为了保持跟踪最新的信息。一个节点接收到一条TC消息后，就能够根据其ANSN决定本条TC消息源节点的广播相邻节点的有关信息是否比已有的新。

（2）广播相邻节点主地址。本域表示一个相邻节点的主地址。TC消息中包含其源节点的广播相邻节点的全部主地址。假如根据网络规定的最大长度，一条TC消息不能容纳全部广播相邻节点的地址，则需要使用多条TC消息把全部广播相邻节点的地址传输完毕。假如需要一定的冗余度，则在TC消息中还可以包含相邻节点的其他主地址。

（3）保留（Reserved）。保留今后使用，必须设为全0，以便与本规范保持一致。

2）广播相邻节点集

网络中的一个节点发送一条TC消息，用于向网络声明一个链路集合，这个集合叫作广播链路集合（Advertised Link Set），其中必须至少包含到达该节点MPR选择器集合中的所有节点的链路，其MPR选择器集合就是已经选择该节点作为MPR的相邻节点组成的集合。假如由于某种原因需要分发TC冗余信息，则参考有关冗余拓扑信息的描述。

广播相邻节点集合的序列号ANSN随着该列表一起被发送。当从广播相邻节点集合中删除链路的时候，或者当给广播相邻节点集合中添加链路的时候，均必须递增其序列号ANSN。

3）TC消息的产生

为了建立拓扑信息库，已经被选作MPR的每个节点广播TC消息。利用各个MPR将TC消息泛洪到网络中的所有节点。采用MPR具有更好的分发拓扑信息的可扩展性。

由于网络规定的消息长度有限，所以每条TC消息可能容纳部分地址列表，但是必须在一定的刷新周期时间（TC_INTERVAL）内完成对描述一个节点的广播链路集合的全部TC消息的分析。通过TC消息传播到整个网络中的信息有助于每个节点计算其路由表。

当一个节点的广播链路集合变成一个空集的时候，该节点仍然应该以周期时间等于其已发送TC消息的“有效时间（Validity Time）”发送TC消息（消息为空），这个有效时间通常等于TOP_HOLD_TIME（TC消息保持时间），以便使已发送的TC消息无效。直到某个节点被添加到这个广播链路集合后，然后该节点才应该停止发送TC消息。

一个节点可以发送额外的TC消息，以便加快对链路中断的反应。当检测出MPR选择器集合发生了变化，而该变化可能是链路中断造成的，则应该在经过一段小于TC_INTERVAL的时间后发送一条TC消息。

4）TC消息的转发

TC消息由MPR广播和转发，以便于传播到整个网络中。必须按照“默认转发算法”转发TC消息。

5）TC消息的处理

接收到一条TC消息后，必须根据本条消息头部的Vtime域计算其“有效时间”，然后应该按照以下方法更新拓扑集合（采用4.1.6节描述的方法进行ANSN比较）：

第一，若本条TC消息的发送节点（注意：不是本条消息的源节点）接口不在本节点的对称一跳相邻区域内，则必须删除本条TC消息。

第二，若拓扑集合中存在一个拓扑数组，且有：

T_last_addr == originator address（本条TC消息的源节点地址）

T_seq > ANSN（本条TC消息的广播相邻节点序列号），

则不必进一步处理本条TC消息，而是将其丢掉（情形：所接收到的消息是乱序的）。

第三，将拓扑集合中同时满足以下条件的所有数组必须删除：

T_last_addr == originator address（本条TC消息的源节点地址）；

T_seq < ANSN（本条TC消息的广播相邻节点序列号）。

第四，对于从本条TC消息中接收到的每个广播相邻节点主地址：

（1）若拓扑集合中存在某个数组同时满足:

T_dest_addr == 广播相邻节点主地址，

T_last_addr == originator address（本条TC消息的源节点地址）

则必须将该数组的保持时间设为：

T_time = current time + validity time。

（2）否则，必须在拓扑集合中记录一个新的数组：

T_dest_addr = 广播相邻节点主地址，

T_last_addr = originator address（本条TC消息的源节点地址），

T_seq = ANSN（本条TC消息的广播相邻节点序列号），

T_time = current time + validity time。

8.路由表的计算

每个节点维护一张路由表，根据这张路由表为传输到网络中任何其他节点的数据提供路由。路由表是根据本地链路信息库和拓扑集合中的信息计算出来的。因此，若其中任何一个集合发生了变化，则必须重新计算路由表，更新到达网络中每个目的节点的路由信息。路由表中记录的路由条目的格式如下：

（1）R_dest_addr R_next_addr R_dist R_iface_addr

（2）R_dest_addr R_next_addr R_dist R_iface_addr

（3）… … … …

路由表中记录的每个路由条目（即一条路由）包含R_dest_add（r目的节点地址）、R_next_addr（到达R_dest_addr的下一跳节点的接口地址）、R_dist（本地节点与R_dest_addr之间的跳数距离）、R_iface_addr（本地接口地址）四个元素。每个路由条目说明以下三层意义：①由地址R_dest_addr确定的目的节点估计离本节点的距离为R_dist跳；②具有接口地址R_next_addr的对称相邻节点是到达R_dest_addr的下一跳节点；③这个相邻节点通过R_iface_addr可达。在路由表中为网络中每个已知到达路由的目的节点记录相应的路由条目。凡是其到达路由中断或者不完全知道的目的节点则不记录在路由表中。

更加确切地说，每当检测出以下变化之一时就更新路由表：①链路集合变化；②相邻节点集合变化；③二跳相邻节点集合变化；④拓扑集合变化；⑤多接口关联信息库变化。

或者更加确切地说，每当发生以下情况之一时，则重新计算路由表：①出现或者丢失一个相邻节点；②建立或者删除一个二跳相邻节点数组；③建立或者删除一个拓扑数组；④多接口关联信息库发生变化。这种路由信息更新既不会产生或者触发任何消息被发送到整个网络中，也不会产生或者触发任何消息被发送到一跳相邻区域内。

为了建立节点X的路由表，需要在一张定向图上运行最短路径算法，定向图包含以下三条弧线：①弧X→Y，Y是节点X的任一对称相邻节点（其相邻节点类型为SYM）；②弧Y→Z，节点Y是一个愿意域设置不等于WILL_NEVER（从不愿意为其他节点转发信息）的相邻节点，二跳相邻节点集合中存在一个条目将节点Y作为N_neighbor_main_addr地址和将节点Z作为N_2hop_addr地址；③弧U→V，拓扑集合中存在一个条目将节点V作为T_dest_addr地址和将节点U作为T_last_addr地址。

下面以一个计算（或者重新计算）路由表的例子给出路由表计算的规程：

第一，将路由表中全部条目删除。

第二，给路由表中添加新的路由条目：从将对称相邻节点（h=1）作为目的节点开始添加。因此，对于相邻节点集合中其状态N_tatus=SYM的每个相邻节点数组（存在一条对称链路到达该相邻节点），以及对于该相邻节点的每个关联链路数组，其L_time ≥ current time，则在路由表中记录一个新的路由条目：

R_dest_addr = 该关联链路数组的L_neighbor_iface_addr，

R_next_addr = 该关联链路数组的L_neighbor_iface_addr，

R_dist = 1（跳），

R_iface_addr = 该关联链路数组的L_local_iface_addr。

假如上面不存在等于该相邻节点的主地址的R_dest_addr地址，则必须在路由表中再添加一个新的路由条目：

R_dest_addr = 该相邻节点的主地址，

R_next_addr = 一个L_time ≥ current time的关联链路数组的L_neighbor_iface_addr，

R_dist = 1（跳），

R_iface_addr = 该关联链路数组的L_local_iface_addr。

第三，对于集合N2中的每个节点，即一个既不是相邻节点也不是节点本身的二跳相邻节点，二跳相邻节点集合中至少存在一个条目，其N_neighbor_main_addr地址等于一个其愿意域设置不等于WILL_NEVER（从不愿意为其他节点转发信息）的相邻节点，则选择一个二跳相邻节点数组，并在路由表中建立一个路由条目：

R_dest_addr = 该二跳相邻节点的主地址，

R_next_addr = R_next_addr（路由表中R_dest_addr == 该二跳相邻节点数组的N_neighbor_main_addr的路由条目的R_next_addr），

R_dist = 2（跳），

R_iface_addr = R_iface_addr（路由表中R_dest_addr == 该二跳相邻节点数组的N_neighbor_main_addr的路由条目的R_iface_addr）。

第四，将h+1跳的目的节点的新路由条目记录在路由表中。从h=2开始，必须对h的每个取值执行如下计算规程。每执行一次，则将h加1。假如在计算规程重复执行过程中没有新的路由条目需要记录，则停止计算规程的执行。

（1）对于拓扑表中的每个条目，若其T_dest_addr不等于路由表中任何条目的R_dest_addr，并且其T_last_addr等于某个R_dist等于h的路由条目的R_dest_addr，则必须给路由表中添加一个新的路由条目（假如还不存在的话）：

R_dest_addr = T_dest_addr，

R_next_addr = R_next_addr（一个已记录的R_dest_addr == T_last_addr的路由条目的），

R_dist = h+1（跳），

R_iface_addr = R_iface_addr（一个已记录的R_dest_addr == T_last_addr的路由条目的）。

（2）可能需要使用若干个拓扑条目为可达目的节点R_dest_addr选择其下一跳节点R_next_addr。当h=1时，应该做出选择，以便优先选择MPR选择器和愿意域设置最高的节点作为下一跳节点。

第五，对于多接口关联信息库中的每个条目，若存在一个R_dest_addr == 该多接口关联条目的I_main_addr的路由条目，并且不存在R_dest_addr == I_iface_addr的路由条目，则在路由表中添加一个新的路由条目：

R_dest_addr = 该多接口关联条目的I_iface_addr，

R_next_addr = 已记录的一个路由条目的R_next_addr，

R_dist = 已记录的一个路由条目的R_dist，

R_iface_addr = 已记录的一个路由条目的R_iface_addr。

9.节点配置

按照如下方法配置节点，以便于节点参与OLSR MANET网络的操作。

（1）地址分配。应该按照确定的地址顺序给MANET网络中的节点分配地址，即MANET网络中的节点应该是通过网络地址和掩码地址（Netmask）可寻址的。同样，每个关联网络中的节点也应该按照确定的地址顺序分配得到地址，这种地址顺序不同于MANET网络中使用的地址顺序。

（2）路由配置。含有主机或者连接着关联网络的任何一个MANET网络节点都应该被配置，以便于建立到达含有关联网络或者主机的接口的路由。

（3）数据分组的转发。OLSR协议本身不转发分组，而是维护基本操作系统中的路由表，假定基本操作系统按照RFC1812转发分组。

4.1.4 OLSR协议的辅助功能

1.非OLSR的接口

一个节点可能配置有多个接口，其中有些接口不参与OLSR MANET网络操作。这些非OLSR接口可能通过点对点方式连接其他单个主机或者单个网络。

为了提供OLSR MANET接口和非OLSR接口之间的连接，一个节点应该能够将外部路由信息注入到OLSR MANET网络中。

将路由信息从OLSR MANET网络注入非OLSR接口超出本规范的讨论范围。但是，应该清楚：OLSR MANET网络路由信息可以从拓扑表中提取或者可以从OLSR路由表中直接得到，并且应该注入到非OLSR接口，不论这些非OLSR接口提供何种机制（路由协议、静态配置、等等）。给出一个例子如下：一个节点通过一个固定网络（比如以太网）连接到一个较大的网络，同时配备有运行OLSR协议的无线网络接口。注意：这种一个节点同时具有OLSR接口和非OLSR接口的情况不同于一个节点同时具有“多接口”情况，后者是全部接口都运行OLSR协议，参与MANET网络操作。

为了使一个具有非OLSR接口的节点能够将外部路由信息注入到OLSR MANET网络，该节点周期性发送主机和网络关联（Host and Network Association，HNA）消息，HNA包含接收节点适当建立一个路由表所需要的足够多的信息。

1）HNA消息的格式

HNA消息的格式如图4-6所示。

HNA消息作为前面描述的通用分组格式中的数据组成部分来发送，其“消息类型”被设为HNA_MESSAGE（HNA消息类型）；TTL应该设为最大值255；Vtime相应地设为HNA_HOLD_TIME（HNA消息保持时间）。对图4-6的各个组成域详细说明如下：

网络地址（Network Address）：表示关联网络的网络地址。

掩码地址（Netmask）：对应于网络地址的掩码地址。

2）主机和网络关联信息库

每个节点维护可以作为“网关”连接到关联主机和关联网络的有关节点的信息，其方法是记录“关联数组（Association Tuple）”（A_gateway_addr，A_network_addr，A_netmask，A_time），其中：A_gateway_addr表示本网关的一个OLSR接口的地址；A_network_addr和A_netmask分别表示一个通过本网关可达的一个网络的网络地址和掩码地址；A_time表示本数组的有效期满时间，期满时间结束后必须删除本数组。一个节点的全部关联数组组成的集合叫做“关联集合（Association Set）”。

应该注意：HNA消息可以看成“广义化的”TC消息，HNA消息和TC消息的源节点都向外声明其他哪些主机“可达”。因为根据每个主机来声明可达性，所以TC消息不需要使用掩码地址。在HNA消息中，通常宁愿通过网络地址和掩码地址声明可达一个地址序列，而不愿意声明可达单个的主机地址。

HNA消息和TC消息之间的重要区别是：TC消息对以前的信息具有删除作用（假如其ANSN是递增的），而HNA消息中的信息是唯一根据期满时间来删除的。

3）HNA消息的产生

连接关联主机和/或者关联网络的节点应该周期性产生HNA消息。HNA包含所连接的主机和网络的地址对（网络地址，掩码地址）。应该以HNA_INTERVAL作为HNA消息的发送周期时间。Vtime相应地设为HNA_HOLD_TIME（HNA消息保持时间）。没有连接任何关联主机和/或者关联网络的节点不应该产生HNA消息。

4）HNA消息的转发

接收到一条HNA消息后，而且符合本版OLSR通用分组格式，必须按照OLSR分组转发方法转发该条HNA消息。

5）HNA消息的处理

在本节，术语“源节点地址”用于表示OLSR MANET网络中最初发送一条HNA消息的节点的主地址。

一条HNA消息被接收后，必须根据本条消息头部的Vtime域计算其“有效时间”，然后应该按照以下方法更新主机和网络关联信息库：

第一，若本条消息的发送节点（注意：不是消息的源节点）接口不在该节点的对称一跳相邻区域内，则必须丢掉本条消息。

第二，否则，对于本条消息中的每对地址（网络地址，掩码地址）：

（1）若关联集合中存在一个数组条目（即关联数组）：

A_gateway_addr == originator address（本条HNA消息的源节点地址）

A_network_addr == network address（网络地址）

A_netmask == netmask（掩码地址），

则本关联数组的保持时间设为：

A_time = current time + validity time。

（2）否则，在关联集合中记录一个新的关联数组：

A_gateway_addr = originator address（本条HNA消息的源节点地址）

A_network_addr = network address（网络地址）

A_netmask = netmask（掩码地址）

A_time = current time + validity time。

6）路由表的计算

除了前面描述的路由表计算（内核功能之一）以外，还必须按照以下方法添加主机和网络关联集合：

对于关联集合中的每个关联数组：

第一步，若路由表中不存在路由条目：

R_dest_addr == A_network_addr/A_netmask（网络地址/掩码地址）

则建立一个新的路由条目。

第二步，若按照第一步建立了一个新的路由条目，或者路由表中存在一个路由条目：

R_dest_addr == A_network_addr/A_netmask（网络地址/掩码地址），

R_dist > 到达当前关联集合数组的A_gateway_addr的跳数据离，

则将该路由条目修改如下：

R_dest_addr = A_network_addr/A_netmask（网络地址/掩码地址），

R_next_addr = 从本节点到达A_gateway_addr的路由上的下一跳，

R_dist = 到达A_gateway_addr的跳数距离，

必须使R_next_addr和R_iface_addr分别等于路由集合中R_dest_addr == A_gateway_addr的路由数组中的R_next_addr和R_iface_addr。

7）互操作考虑

没有实现非OLSR接口支持的节点能够共存于包含真正支持非OLSR接口的节点的网络，通用分组格式和消息转发确保HNA消息被所有节点正确转发。因此，支持非OLSR接口的节点可以根据本节的规则发送和处理HNA消息。不支持非OLSR接口的节点不能利用本节说明的功能，但是仍然能够正确转发HNA消息。

2.链路层通知

OLSR协议并不有意利用或者需要链路层的任何特定信息。但是，假如一个节点能够从链路层得到有关链路中断的信息，那么该节点就可以按照本节的描述使用这种信息。

若能够得到描述与相邻节点连接的链路层信息（即，诸如接收不到链路层应答的连接丢失信息），则可以联合利用该信息和HELLO消息中的信息来维护相邻节点信息库和MPR选择器集合。因此，接收到一个关于一个节点和一个相邻节点之间的链路已经中断的链路层通知后，就链路探测采取以下操作：

除了在OLSR协议内核中描述的链路探测及本地链路信息库操作以外，本地链路集合中的每个链路数组应该包含一个L_LOST_LINK_time组成域。L_LOST_LINK_time表示一个定时器，用于在一条已建立链路变得即将中断之时声明该条链路已经丢失。（注意：这就是在链路滞后作用中介绍的一个子集，因此，链路层滞后作用和链路层通知能够共存）。

HELLO消息的产生应该考虑以下这些组成域：

（1）若时间L_LOST_LINK_time还没有结束，则使用链路类型LOST_LINK（链路丢失）广播该条链路。此外，在更新关联相邻节点数组时不用将这条链路考虑为一条对称链路。

（2）若到达一个对称（或者不对称）相邻节点接口的链路已经中断，则将对应的链路数组修改如下：将L_LOST_LINK_time和L_time均设成current time + NEIGHB_HOLD_TIME。

（3）认为本条链已经丢失，而且应该按照相邻区域和二跳相邻区域变化的处理规则进行适当的处理。

链路层通知为一个节点提供了另外一个准则，即确定到达一个相邻节点的链路是否丢失的准则。一旦检测出一条链路已经丢失，则根据本版规范前面描述的规则广播这条链路。

3.链路滞后作用（Link Hysteresis）

已建立的链路应该是尽可能的可靠，以便防止分组丢失。这就意味着链路探测应该具有抗链路突发丢失和节点间短暂连接的能力。因此，为了强化链路探测机制，应该考虑下列实现建议。

1）本地链路集

除了在OLSR协议内核中描述的链路探测及本地链路信息库操作以外，本地链路集合中的每个链路数组应该包含一个L_link_pending域、一个L_link_quality域和一个L_LOST_LINK_time域，其中：L_link_pending是一个布尔标志，用于说明是否认为本条链路即将中断（即：认为本条链路没有建立）；L_link_quality是一个位于0和1之间的无穷小数，用于描述本条链路的质量；L_LOST_LINK_time表示一个定时器，用于在一条已建立链路变得即将中断之时声明该条链路已经丢失。

2）HELLO消息的产生

HELLO消息的产生应该考虑以下这些组成域：

（1）若时间L_LOST_LINK_time还没有结束，则使用链路类型LOST_LINK（链路丢失）广播该条链路。

（2）否则，若时间L_LOST_LINK_time已经结束，并且标志L_link_pending设为“真”，则根本不应该广播该条链路。

（3）否则，若时间L_LOST_LINK_time已经结束，并且标志L_link_pending设为“假”，则根据HELLO消息的描述广播该条链路。

对于同时满足以下条件的每个链路数组，节点认为自己存在一条对称链路：①时间L_LOST_LINK_time已经结束，②标志L_link_pending设为“假”，③时间L_SYM_time还没有结束。在计算一个相邻节点的状态N_status时，应该使用这个“对称链路”定义来更新关联相邻节点数组。因此，在计算MPR集合时以及路由表计算第一步的寻找“对称相邻节点”中，应该将这个对称链路定义作为寻找对称相邻区域的基础。

除了上面的描述以外，前面的描述没有涉及到链路数组中的这些高级链路探测域。L_link_pending、L_link_quality、L_LOST_LINK_time三个组成域专门根据本节的描述来更新。本节对链路数组的其他组成域不作功能修改。

3）滞后作用策略

一个节点和其一个相邻节点的其中一个接口之间的链路可能质量很差，即有时这条链路刚好让HELLO消息传输完毕就立即衰落。在这种情况下，相邻节点信息库应该将一条质量差的链路维护一段至少等于“有效时间（Validity Time）”的时间。应该采用下列滞后作用策略来处理这种情况。

对于接口I能够接收到的每个相邻节点接口NI，由相应链路数组的L_link_quality决定是否建立该条链路。L_link_quality的取值可以与两个固定在0 和1 之间的门限值HYST_THRESHOLD_HIGH、HYST_THRESHOLD_LOW进行比较，HYST_THRESHOLD_HIGH≥ HYST_THRESHOLD_LOW。

该链路数组的L_link_pending标志设置如下：

（1）若L_link_quality ＞ HYST_THRESHOLD_HIGH，则：

L_link_pending = false（假），

L_LOST_LINK_time = current time -1（期满时间已经结束）。

（2）否则，若L_link_quality ＜ HYST_THRESHOLD_LOW，则：

L_link_pending = false（假），

L_LOST_LINK_time = min (L_time，current time + NEIGHB_HOLD_TIME)。

然后认为本条链路已经丢失，这有可能导致一个相邻节点丢失。

（3）否则，若HYST_THRESHOLD_LOW ≤ L_link_quality ≤ HYST_THRESHOLD_HIGH，则L_link_pending标志和L_LOST_LINK_time时间保持不变。

因此，考虑建立一条链路的条件比考虑丢失一条链路的条件严格。所以，可以根据定时器定时时间结束来丢失一条链路，或者可以根据L_link_quality低于门限HYST_THRESHOLD_LOW来丢失一条链路。

即使根据链路滞后作用认为一条链路没有建立，但是由于所接收到的每条HELLO消息，其链路数组仍然得到更新。这就特别意味着：不论链路滞后作用是否认为一条链路已经建立，除了链路数组的L_time时间决定该数组的期满时间以外，链路集合中的链路数组是不会期满的。

作为一个基本的实现要求，链路质量的估计必须得到维护并存储在L_link_quality域。假如能够得到接收消息时的信号电平/噪声电平的测量数据（例如作为一个链路层通知），那么将其标准化处理之后就可以作为对应链路的估计。假如从链路层得不到信号电平/噪声电平测量数据或者其他链路质量信息，那么可以采用下列算法（这是一个对传输成功率进行指数平滑移动平均的算法）。该算法采用取值固定在0和1之间的一个比例参数HYST_SCALING来表示。对于接口I能够接收到的每个相邻节点接口NI，第一次NI被接口I所接收，L_link_quality设为HYST_SCALING（L_link_pending标志设为真，L_LOST_LINK_time时间设为current time-1。

根据下面两个规则更新链路数组。每当相邻节点接口NI发送的一个OLSR分组被接口I所接收到的时候，则采用稳定性规则：

L_link_quality = (1-HYST_SCALING)×L_link_quality + HYST_SCALING。

每当相邻节点接口NI发送的一个OLSR分组被接口I丢失的时候，则采用不稳定性规则：

L_link_quality = (1-HYST_SCALING)×L_link_quality。

通过跟踪每个接口上的丢失分组序列号，以及一个节点“长时间静默”来检测OLSR分组的丢失。因此，“长时间静默”可以被检测出来：假如在接口NI上的HELLO消息发送周期（根据最近从接口NI上接收到的HELLO消息中的Htime域数据来计算）内没有从接口I上接收到接口NI发送来的OLSR分组，则检测出已经丢失一个OLSR分组。

4）互操作考虑

一个节点到达一个相邻节点的链路被认可或者被拒绝的准则由链路滞后作用决定。网络节点可以根据通信媒介的特性采用不同的准则。一旦一条链路被认可，则立即根据本版规范前面描述的规则广播该条链路。

4.冗余拓扑信息

为了给拓扑信息库提供冗余度，一个节点的广播链路集合可能包含到达不属于该节点的MPR选择器集合的相邻节点的链路，也可能包含到达该节点所有相邻节点的链路。任何一个节点能够在其TC消息中广播的最小链路集合就是到达其MPR选择器的链路组成的集合。可以按照下列规则和根据本地参数TC_REDUNDANCY建立广播链路集合。

1）TC_REDUNDANCY参数

本地参数TC_REDUNDANCY为一个本地节点指定TC消息中可能包含的信息数量。本地参数TC_REDUNDANCY解释如下：

（1）若本节点的参数TC_REDUNDANCY等于0，则该节点的广播链路集合被限制为其MPR选择器集合；

（2）若本节点的参数TC_REDUNDANCY等于1，则该节点的广播链路集合等于其MPR集合与其MPR选择器集合的并集。

（3）若本节点的参数TC_REDUNDANCY等于2，则该节点的广播链路集合等于全部相邻节点链路集合。

一个愿意域设为WILL_NEVER（从不愿意为其他节点传输信息）的节点应该使其TC_REDUNDANCY等于0。

2）互操作考虑

一个节点将一条TC消息发送到网络中，用于声明一个链路集合，这个集合叫做广播链路集合，其中必须至少包含到达其MPR选择器集合中所有节点（即：已经选择该发送节点作为MPR的相邻节点）的链路。这些信息足够保证能够完成OLSR协议路由计算内核功能。

本节说明可以采用参数TC_REDUNDANCY来声明其他信息的方法。TC_REDUNDANCY等于0意味着所声明的信息正好相当于MPR选择器集合。TC_REDUNDANCY的其他取值说明声明其他的信息。也就是说MPR选择器集合的内容总是会被声明的。因此，TC_REDUNDANCY取值不同的各个节点可以共存于一个网络中：控制消息被所有节点传输，所有节点至少能够接收到建立路由所需要的链路状态信息。

5.MPR冗余度

MPR冗余度说明一个节点选择多余MPR的能力。节点应该将其MPR集合选择得尽可能的小，以便降低协议开销。选择MPR的准则是：所有严格二跳节点必须至少通过一个MPR节点可达。MPR集合的冗余度影响所广播的链路数量、进行链路广播的节点的数量、以及MPR泛洪机制的效率，因而影响协议开销。但是，MPR集合的冗余度确保一个节点的可达性被多个节点所广播，因此其他的链路被传播到网络中。

尽管一般情况下一个最小MPR集合具有最低协议开销，但是有些时候为了其他的考虑而对协议开销进行折中考虑。例如，一个节点需要观察其相邻节点信息库由节点移动造成的很多变化时可能决定增大其MPR集合覆盖范围，否则保持小MPR集合覆盖范围。

1）MPR_COVERAGE参数

MPR覆盖范围由参数MPR_COVERAGE定义，说明任意一个二跳节点被多少个MPR节点所覆盖。MPR_COVERAGE=1说明OLSR协议开销保持在最低程度，以及按照MPR集生成规则进行MPR选择。MPR_COVERAGE=m确保：假如可能的话，一个节点选择其MPR集合，使得一个接口的所有严格二跳节点至少通过该接口上的m个MPR节点可达。MPR_COVERAGE的取值是大于0的整数。必须对每个接口I使用这个搜索过程。一个节点的MPR集合就是在每个接口上发现的MPR集合的并集。

可以在本地调整参数MPR_COVERAGE而不会影响OLSR协议的一致性。例如，网络中的各个节点可以采用各自不相等的参数MPR_COVERAGE来操作。

2）MPR集的计算

使用MPR覆盖范围的时候，采用如下一个定义延伸MPR选择搜索过程：

欠覆盖节点（Poorly Covered Node）：一个欠覆盖节点是N2集合中的一个节点，集合N中存在覆盖该节点的节点数量少于MPR_COVERAGE个。

因此，本规范建议的MPR选择搜索规程如下：

第一，从一个MPR集合开始搜索。该集合由集合N中的愿意域设为WILL_ALWAYS（总是愿意为其他节点转发信息）的全部成员节点构成。

第二，为集合N中的全部成员节点计算D(y)，y表示集合N中的一个成员节点。

第三，将集合N中覆盖集合N2中欠覆盖节点的那些节点选为MPR，然后从集合N2中删除这些节点，以便于剩余的计算。

第四，尽管集合N2中仍然存在未被MPR集合中至少MPR_COVERAGE个节点所覆盖的节点，但是：

（1）对于集合N中的每个节点，计算其可达性，即集合N2中仍然未被MPR集合中至少MPR_COVERAGE个节点所覆盖的节点的数量，而且这些节点通过本一跳相邻节点可达；

（2）将集合N中愿意域设置最高、可达性不等于0的那个节点选为一个MPR。存在多个节点选择时，则选择提供可达集合N2中节点的数量最多的那个节点作为MPR。若多个节点提供相同的可达性，则选择其D(y)较大的那个节点作为MPR。将集合N2中现在已被MPR集合中MPR_COVERAGE个节点所覆盖的那些节点删除。

第五，一个节点的MPR集合由每个接口的MPR集合的并集得到。作为一种优化，按照愿意程度递增方式依次处理MPR集合中的每个节点y。假如集合N2中的所有节点仍然被MPR集合中至少MPR_COVERAGE个节点所覆盖，并且还假如节点y的愿意域小于WILL_ALWAYS（总是愿意为其他节点转发信息），那么可以从MPR集合中删除节点y。

MPR集合被全部计算完毕后，将所有相应主地址存储在该MPR集合中。

3）互操作考虑

根据MPR集的生成规则，一个节点计算其MPR集合必须要求：该节点通过MPR集合中的相邻节点能够到达所有对称严格二跳相邻节点。这通过本节介绍的搜索过程对所有的MPR_COVERAGE > 0进行搜索来实现。MPR_COVERAGE是每个节点的一个本地参数，其设置只影响网络局部的冗余度。对于MPR_COVERAGE = 1，本节介绍的搜索完全等同于MPR集生成规则的搜索。

MPR_COVERAGE取值不同的各个节点可以共存于一个网络：控制消息被所有节点传输，所有节点至少能够接收到建立路由所需要的链路状态信息。

4.1.5 有关常量的建议值

下面列出描述OLSR协议时使用的常数数值。

1.发送间隔时间和保持时间的设置

常数C的取值为：C = 1/16 s（0.0625s）。

常数C是一个比列因数，用于“有效时间（Validity Time）”的计算（消息头中的“接收信息有效时间（Vtime）”域和“HELLO消息发送周期（Htime）”域）。广播“Vtime”时间是为了网络中的各个节点可以具有不相等的、单独可调的发送间隔时间，同时仍然保持完全互操作。对于OLSR协议进行的协议功能和互操作性，有：

（1）广播保持时间必须始终大于广播信息的刷新间隔时间。而且，建议按照稍后的说明维持发送间隔时间和保持时间之间的关系，以容许合理的分组丢失。

（2）常数C应该设为建议值。为了实现互操作，所有节点的常数C必须相同。

（3）可以为每个节点单独选择发送间隔时间和广播保持时间（受到上述限制）。

一个给定的OLSR协议实现的定时器分辨率依靠精确刷新时间，或者精确期满时间不足以唤醒系统。OLSR协议实现应该对“有效时间”（分组的“Vtime”和“Htime”）四舍五入，以便补偿比较粗糙的定时器分辨率，至少在“有效时间”可能小于发送间隔时间与最大定时器平均误差之和的时候能够补偿。

2.发送间隔时间

HELLO_INTERVAL = 2s

REFRESH_INTERVAL = 2s

TC_INTERVAL = 5s

MID_INTERVAL = TC_INTERVAL（TC消息发送周期）

HNA_INTERVAL = TC_INTERVAL（TC消息发送周期）

3.保持时间

NEIGHB_HOLD_TIME = 3×REFRESH_INTERVAL

TOP_HOLD_TIME = 3×TC_INTERVAL

DUP_HOLD_TIME = 30s

MID_HOLD_TIME = 3×MID_INTERVAL

HNA_HOLD_TIME = 3×HNA_INTERVAL

消息头中的Vtime域、HELLO消息中的Htime域用于保存上述有关数值的信息，这些数值采用尾数和指数格式（四舍五入）表示。换句话说：

数值 = C×(1+a/16)×2b（s）

其中：a表示本域高部4比特表示的整数，b表示本域低部4比特表示的整数。

注意：对于前面建议的常数C（1/16 s），可以采用上述公式按照二进制定点数或者二进制浮点数与至少8比特分数部分表示而将其存储下来，而且不会损失其精确度。这相当于NTP时间邮戳和单精度IEEE标准754浮点数。

给定上述的一个保持时间，一个数T（单位：s）的尾数/指数表示计算方法如下：

（1）找出最大整数“b”使得：T/C≥2b。

（2）计算表达式16×(T/(C×(2b))−1)，结果可能不等于整数，则四舍五入，得到“a”的值。

（3）若a等于16，则将b加1，将a设为0。

（4）现在，a和b应该均等于0～5之间的整数，该域是一个取值为a×16+b的字节。

例如，对于数值2s、6s、15s、30s，其a和b的取值分别为：(a=0，b=5)、(a=8，b=6)、(a=14，b=7)、(a=14，b=8)。

4.消息类型

HELLO_MESSAGE = 1（HELLO消息）

TC_MESSAGE = 2（拓扑控制消息）

MID_MESSAGE = 3（多接口声明消息）

HNA_MESSAGE = 4（主机和网络关联消息）

5.链路类型

UNSPEC_LINK = 0

ASYM_LINK = 1

SYM_LINK = 2

LOST_LINK = 3

6.相邻节点类型

NOT_NEIGH = 0

SYM_NEIGH = 1

MPR_NEIGH = 2

7.链路滞后作用

HYST_THRESHOLD_HIGH = 0.8

HYST_THRESHOLD_LOW = 0.3

HYST_SCALING = 0.5

8.愿意设置程度

WILL_NEVER = 0

WILL_LOW = 1

WILL_DEFAULT = 3

WILL_HIGH = 6

WILL_ALWAYS = 7

一个节点的愿意设置程度可以设为0～7之间的任一整数，说明该节点到底有多愿意为其他节点转发信息。节点的默认愿意设置程度为WILL_DEFAULT（等于3）。愿意程度WILL_NEVER（等于0）表示一个节点不愿意为其他节点转发信息，比如由于资源限制（例如电池能量低）而不愿意。愿意程度WILL_ALWAYS（等于7）表示一个节点总是愿意被选择为其他节点转发信息，例如由于资源充足（例如持久的电能供应、到达其他节点的高容量接口）而愿意。一个节点可以随着其条件变化而动态改变其愿意设置程度。

例如，一种可能的应用是：一个节点如果连接有持久电能和使用充电饱满的电池，则向外广播其愿意设置程度WILL_ALWAYS（总是愿意为其他节点转发信息）；如果与持久电能连接断开（例如，一个PDA从充电器中取出后），则向外广播其愿意设置程度WILL_DEFAULT（愿意为其他节点转发信息）；随着电池能量的不断消耗，其愿意设置程度不断降低（取值变小），首次到达WILL_DEFAULT和WILL_LOW之间的值，然后到达WILL_LOW值，最后等于WILL_NEVER，此时该节点的电池供电不再支持该节点转发其他节点的信息。

9.其他考虑

TC_REDUNDANCY = 0

MPR COVERAGE = 1

MAXJITTER = HELLO_INTERVAL / 4

4.1.6 序列号

OLSR协议使用序列号的目的是为了丢掉“旧”信息（即，所接收到的乱序消息）。但是，使用有限的若干比特表示序列号，会出现返转问题（即，序列号从最大值开始递增到零）。为了防止这个问题干扰OLSR协议的操作，必须遵守以下规则。

术语MAXVALUE指定随后一个可能的最大序列号。若序列号S1、S2满足下列条件，则说序列号S1大于序列号S2：

S1 > S2 AND S1- S2 ≤ MAXVALUE/2，

或者S2 > S1 AND S2- S1 > MAXVALUE/2。

因此，当比较两条消息时，即使出现返转问题，也能够确定哪条消息包含最新的信息。

4.1.7 流量控制和拥塞控制

由于主动操作特性，OLSR协议自然具有控制其控制消息传输流的能力。各个节点按照由预先确定的刷新间隔时间决定的预定速率发送控制消息。而且MPR优化节省了大量控制开销。从两个方面降低了控制开销：第一方面，广播拓扑的分组小得多，这是因为只需要广播MPR选择器；第二方面，信息泛洪的代价被大幅度降低，这是因为只有MPR节点转发广播分组。在高节点密度网络中，与使用经典泛洪的路由协议（例如OSPF）对比，OLSR协议的控制传输量减少数个数量级。OLSR协议的这种特征自然提供更多的带宽传输数据，进一步将拥塞推向边沿（进一步减轻拥塞）。因为控制消息流是连续周期性的，所以路由中使用的链路的质量保持得更加稳定，而在反应式路由协议中，路由寻找和路由修复采用突发泛洪，这些链路上的许多碰撞可能对其链路质量造成短时间损害，从而产生路由修复调用暴。但是，在一些OLSR协议的选项中，可以提前（在最终期限结束之前）发送某些控制消息，以便增强OLSR协议对拓扑变化的反应。这可能导致局部控制消息流短暂而小幅提高。

4.1.8 其他考虑

1）IPv6考虑

本版描述的OLSR协议采用IPv4时的所有操作和所有参数完全等同于OLSR协议采用IPv6时的所有操作和所有参数。采用IPv6操作时，唯一要求做的变化就是用IPv6地址代替IPv4地址。考虑到IPv6地址较长，应该相应调整分组最小长度和消息最小长度（在原来的长度下，将会受到IPv6的拒绝）。

2）IANA考虑

OLSR协议定义控制消息的“消息类型”。已经为消息类型域的取值进行新的注册，其值分配如表4-1所示。

今后可以使用标准操作分配范围5～127之间的其他消息类型。范围128～255之间的数值保留为专用/局部使用。