OLSR路由协议学习

OLSR路由协议

• 概述
• • 两种分组
  • 路由发现与维护
• 算法步骤
• • 链路感知
  • 邻居侦听
  • MPR选择
  • 拓扑建立
  • 路由表的建立与维护
• 总结

概述

• 优化链路状态路由（Optimized Link State Routing）协议，即 OLSR 路由协议是一种平面拓扑的先验式路由协议（主动式路由协议）。
• 节点通过周期性地与自己的邻居节点交换分组信息来完成链路感知和邻居侦测过程，进而建立起自己的拓扑结构。并通过接收拓扑控制分组获知全网的拓扑信息，以此为依据计算出一张从自身节点到达全网各个节点传输路径的路由表。
• 当节点有通信需求时可以通过查询路由表获得所需的路由信息。

1. 通过HELLO分组的周期性交互，执行链路检测、邻居发现的功能；
2. 通过拓扑控制（TC）分组的周期性交互执行多点中继节点（MPR）信息声明功能；
3. 最终以这些分组所建立起来的拓扑结构为基础，进行基于 MPR 的路由计算。

两种分组

OLSR 协议中主要用到两种分组格式，为 HELLO 消息和 TC 分组。

• HELLO 消息主要用于链路感知、邻居侦听过程，节点之间通过交换 HELLO 消息建立自己的本地连接库、邻居信息库；
• TC 分组为拓扑控制分组，用于节点建立拓扑信息库，然后据此计算节点到网络中每个目的节点的路由。

路由发现与维护

算法步骤

链路感知

每个节点都要探测与其邻节点间的链路，由于无线传播的不确定性，某些链路可能会被认为是单向的。因此，所有链路必须双向验证才被认为是可用的。可以双向交互的链路是对称链路，可以双向交互的两个节点是对称节点。

链路感知是通过 HELLO 分组的周期性交互实现的。本地链路信息表存储了该节点到邻居节点的链路信息。节点发送 HELLO 分组时，本地链路信息表作为消息的内容。节点收到 HELLO 分组，更新本地链路信息表。

邻居侦听

每个节点必须检测它与哪些邻节点间具有双向链路。HELLO 分组中携带了节点的邻节点信息和链路状态。HELLO 分组只在一跳范围内传输。通过 HELLO 分组的周期性交互，节点生成了邻居信息库。

邻居侦听的过程如下图 所示，在初始化阶段，当节点 A 收到一个来自于邻居节点 B 的 HELLO分组，A 将 B 放入自己的邻居集中，并将到 B 的链路标记为非对称状态，然后，在 A 向 B 发送 HELLO 分组时，在 HELLO 分组中就包含有 B 是 A 的非对称状态的邻居节点的信息，当 B 收到该 HELLO 分组时，B 将在邻居集中将 A 的状态更新为对称状态。同理，在 B 再次向 A 发送 HELLO 分组时，HELLO 分组中就包含了 A 是 B 的对称状态的邻居节点的信息，当 A 收到该 HELLO 分组时，A 就在邻居集中将 B 的状态更新为对称状态。之后，A、B 再分别计算自己的 MPR，在后面的 HELLO 分组交互中会包含各自的 MPR 信息。

从一个对称邻居中接收到一个 HELLO 分组，节点应更新其两跳邻居集。

MPR选择

多点广播中继即 MPR 技术作为 OLSR 路由协议中的一个重要组成部分，可以有效地减少网络中控制分组的发送数量，其基本思想就是网络中的每个节点都要选出本地节点的部分 1 跳邻居节点加入 MPR 集，只有 MPR 节点才能参与拓扑控制消息（即 TC 分组）的转发，相较于传统协议中所有邻居节点参与转发的洪泛机制，MPR 技术在很大程度上减小了网络开销。

每个节点都会从自己的 1 跳对称邻居节点内进行 MPR 节点的选择，在优先考虑节点的转发意愿的基础上，把严格对称 2 跳邻居集内节点连接度高的节点选作MPR 节点，MPR 集的详细计算过程将在后文进行细致的介绍与分析。 仅有MPR 中的节点有权利将收到的节点信息进行转发，而其他邻节点仅处理信息而不转发。

节点A的——

1跳邻居集合： N N N

2跳邻居集合：   N 2 \ N_2  N2​

MPR集合： M M M

D ( y ) D(y) D(y)：N中节点y的连接度（除N中节点和A外，y的对称邻居数量）

  N 2 \ N_2  N2​中不包括：

（1）只通过集合 N 中转发意愿为 WILL_NEVER 的节点才可达的节点；

（2）执行 MPR 集计算的 A 节点本身；

（3）节点 A 的所有对称邻居，即与节点 A 之间存在直接的对称链路的节点。

选择算法：

1. 把 N 中的所有转发意愿为 WILL_ALWAYS 的节点加入M；
2. 计算集合 N 中的所有节点 y 的连接度 D(y)；
3. 将 N 中对 N2 中的某个节点 b 提供唯一可达性的节点添加进 M 中，移除N2中可通过M中节点到达的节点；
4. 如果在N2 中存在某节点通过M不可达，则计算 N 中节点的可达性（即通过此节点可达的现在 N2 中节点的数目），对比 N 中节点的可达性，在所有可达性非 0 的节点中，将转发意愿 N_willingness 最高的节点加入 M 。如果多个节点的转发意愿相同，则选择可达性最高的节点；如果可达性相同，则选择连接度 D(y) 最高的节点。然后，移除N2中可通过M中节点到达的节点；
5. 若 N2 集不为空，则回退到步骤（3）；N2 集为空，则集合 M 为节点 A 最终的 MPR 集。

拓扑建立

OLSR 协议通过MPR节点在全网范围内周期性地发送和转发拓扑控制（TC）分组来获取拓扑信息，并形成一个拓扑信息表。其中，TC只能由MPR节点产生和转发，且其分组内容至少包括其MPR选择集的所有节点。通过这个表，节点可以知道网络中各个MPR节点以及它的选择方的拓扑信息。节点接收到MPR的TC分组时的处理过程如图所示。

路由表的建立与维护

OLSR 协议中每个节点都需要计算并维持一张不断更新的路由表。节点依据本地链路信息库和拓扑信息表中储存的信息，根据 Djisktra 算法以最小跳数为依据建立路由表。由于路由表是基于本地链路信息库和拓扑信息表中的信息建立的，所以每当网络中拓扑发生链路断裂、拓扑变更、链路到期等变化时，节点的本地链路信息库或拓扑信息表中的内容也会发生相应变化，此时节点会自发的进行路由表的重新计算。

总结

OLSR 协议特别适用于大型和密集的网络，因为 MPR 机制的引入使得OLSR 协议的路由开销相对固定，只与网络规模成正相关，与网络负载的关系较小。此外，由于 OLSR 协议采用主动路由的方式建立与维护路由表，不需要临时发起路由发现过程，因此 OLSR 协议的数据传输的平均端到端时延往往很低，所以 OLSR 协议在网络流量分布随机且节点位置分布稀疏的网络条件下通常有较好的传输性能。