1、LSR 协议

LSR 为基于链路状态的路由算法。如何判断链路状态呢？在无线通信的环境下，只需要节点能够收到另一节点的包，就说明链路有效。另一方面，为了建立端到端的路径，路由算法需要发现并检查一跳由多个单跳链接组成的多条链路的可用性，这就需要不断的洪泛广播(flooding)来进行。这种洪泛的方式是非常浪费的。

在这里插入图片描述

为了在网络中同步节点状态，需要各个节点进行洪泛广播，产生大量冗余的通信，在能源受限的移动网络中是非常不经济的。OLSR 通过有选择的洪泛转发(MPR: Multi-Point Relay)来解决这个问题。

2、OLSR 协议

OLSR（Optimized Link State Routing: RFC 3626, October 2003）是一种基于连接状态的表驱动无线路由协议，它在 Ad Hoc 路由协议中的位置如下图所示。

在这里插入图片描述

OLSR 包使用 IP 地址作为其在网络中的唯一标识，兼容 IPv4 和 IPv6 两种格式，下面以 IPv4 为例说明其包格式：

在这里插入图片描述

OLSR 包由以下几部分组成：

  • Packet length 包的字节长度
  • Packet sequence number 包的序列号
  • Message type 消息类型
    • 1 -> Hello
    • 2 -> topology control(TC)
    • 3 -> multiple interface declaration(MID)
    • 4 -> host and network association(HNA)
  • Vtime 节点接收消息后消息的有效时间
  • Message size 消息的字节长度
  • Originator address 产生消息的节点的地址
  • TTL 最大跳数
  • Hop count 当前跳数
  • Message sequence number 消息的序列号
  • Data 真正的消息

3、OLSR 协议的操作

3.1 邻节点探测

OLSR 的节点中存储了大量的数据表，主要有以下三种：

  • MPR selector set 这个表记录了本地选为 MPR 的节点
  • neighbor set 这个表记录了所有的一跳邻节点
  • Two-hop neighbor set 这个表记录了可通过一跳邻节点接触的节点，可能包括上述一跳邻节点

由于发送消息至一跳邻节点、两跳邻节点和定义 MPR 都需要用到 HELLO 消息，所以首先介绍一下 HELLO 消息。下图是 HELLO 消息的格式，它位于 OLSR 包的 data 域，传播 HELLO 消息的 OLSR 包的 Message Type 和 TTL 域都为1。

在这里插入图片描述

HELLO 消息由以下几个部分组成：

  • Reserved 设为0000000000000
  • HTime 该接口 HELLO 消息的发送间隔
  • Willingness 一个节点为其他节点传播消息的意愿，分为 WILL_NEVER，WILL_ALWAYS 和 WILL_DEFAULT
  • Link code
  • Neighbor type 表明一个连接时 symmetric，asymmetric 还是 failed link
  • Link type 表明连接的节点是一个一跳邻节点，MPR 还是不可用节点
  • Link message size 从当前 Link Code 到下一个 Link Code 的长度
  • Neighbor interface address 一个邻节点的接口地址

OLSR 通过周期性地广播 HELLO 消息来进行邻节点探测，建立邻居表，一般检测两个节点之间链路状态的流程如下：

在这里插入图片描述

以 A 和 B 两个节点举例，想要检测它们之间链路的状态，需要进行以下几步：

  1. A 向 B 发送空的 HELLO 消息。
  2. B 接收到消息后，由于没有在消息中找到 B 自己的地址，所以将 A 设为非对称邻节点。2秒后，B 向 A 发送携带 A 地址的 HELLO 消息。
  3. A 接收到消息后，在消息中找到了自己的地址，所以将 B 定义为对称链路，接着再向 B 发送带有 B 地址的 HELLO 消息。
  4. B 收到最新消息后，将 A 视为对称邻节点。

基于这个机制，OLSR 中的节点可以进行邻节点的探测，如果与某个邻节点的连接状态变为双向对称连接，则记录在 neighbor set 中，并开放接口连接邻节点；如果连接状态建立失败，则删除记录。

通过 HELLO 消息广播过程，可以让网络中所有节点都能知晓距离自己两跳及以内的邻居的信息。

3.2 MPR 的选择

基于上述过程建立的邻居信息表，节点可以选择出邻居 MPR 节点集合。一个节点选定的 MPR 是负责转发此节点的广播消息的节点，通过控制 MPR 集合的大小可以减少洪泛的开销。

如下图所示情况为例，左侧为经典的洪泛技术，每个中心节点需要传播信息到其所有邻节点；右侧为引入 MPR 技术的 OLSR 协议，每个节点只需将信息传送到其 MPR 节点集合，并由它们广播消息。

在这里插入图片描述

MPR 的选择主要分为两步：

  1. 首先选择能够覆盖孤立两跳邻节点的一跳邻节点。这里的孤立两跳邻节点是指仅通过一个邻节点同目标节点相连的两跳邻节点。
  2. 在余下的一跳邻节点中，按照覆盖二跳邻节点的数量从高到低依次选择，直到覆盖所有的两跳邻节点。

为了方便理解，以下图中的情况为例，找出“1”节点的最小 MPR 集合。

在这里插入图片描述

首先定义其所有的两跳邻节点（不包括一跳邻节点）。

在这里插入图片描述

然后找到其孤立两跳邻节点 2 和 24，然后将连接它们的一跳邻节点 4 和 22 加入 MPR 集合。

在这里插入图片描述

最后按照覆盖二跳邻节点的数量从高到低依次选择，其中15覆盖4个，18、5、10覆盖三个，因为选择5和10都可以满足覆盖所有两跳邻节点，所以选择它们两个中任意一个即可。

在这里插入图片描述 在本地节点被选作 MPR 后，它会向其邻节点发送初始化为 MPR_NEIGH 的 HELLO 消息，邻节点收到消息后更新其 MPR selector set，此表表明节点应该转发来自哪些节点广播消息。

3.3 拓扑管理

邻节点探测使用了 HELLO 消息，拓扑管理则是用另一种格式的消息：Topology Control 消息。MPR 会定期发送 TC 消息，其中包含了选择这个节点作为 MPR 的节点的集合。

在这里插入图片描述

  • ANSN 与接收消息邻节点关联的序列号，代表信息的新鲜度
  • Reserved 这个字段固定设为0000000000000000
  • Advertised neighbor main address 是选择这个节点作为 MPR 的节点的集合，也称为 MPR Selector

基于 TC 消息的交换，各个节点可以维护一个 Topology Table（拓扑表），拓扑表的结构如下：

Destination address Destination’s MPR MPR SelectorSequence Number Holding Time
       
  • Destination address 目标地址
  • Destination’s MPR 目标地址的 MPR 节点
  • MPR SelectorSequence Number 序列号
  • Holding Time 该条目的保持时间

上面提到 TC 消息中包含的是发送节点的 MPR Selector 列表。那么当另一节点收到 TC 消息时，将 TC 条目中的 MPR Selector 作为目标地址，则发送节点即为其 MPR 节点，然后填入 TC 消息中的 Sequence Number，已经预定义的 Holding Time。

下面举一个例子说明拓扑管理的过程，这个例子中 A、B、C 三个节点均将 M 作为自己的 MPR 节点，那么 M 会建立如下的 MPR Selector 列表：

TC Originator MPR Selector MPR Selector Sequence
M A 1
M B 1
M C 1

作为 MPR，M 会将其 MPR Selector 列表通过 TC 消息广播出去。当 Y 收到 M 发出的 TC 消息时，将 TC 消息中包含的 MPR Selector 信息转化成拓扑表 (Holding Time 省略)：

Destination address Destination’s MPR MPR SelectorSequence Number
A M 1
B M 1
C M 1
… … …

网络中周期性的通过 TC 消息保持拓扑表更新，通过拓扑表可以计算出全局路由表。

3.4 路由表计算

基于拓扑表和邻节点信息，网络中的每个节点都维护一张路由表（Routing Table），路由表格式如下图所示：

在这里插入图片描述

  • R_dest_addr 目的地址
  • R_next_addr 下一跳地址
  • R_dist 本地节点到目的地址估计的距离
  • R_iface_id 是到达目的地址的本地接口编号

每次更新拓扑信息，路由表都需要重新计算，计算步骤如下：

  1. 删除之前的所有记录
  2. 添加所有一跳对称邻节点，R_dist 通常设为1
  3. 添加超过1跳（1+h）的目的节点。如果拓扑表中的 Destination address 在路由表的 R_dest_addr 中没有对应的话，就新添加一条路由： a. R_dest_addr = Destination address b. R_next_addr 设为 R_dest_addr 与拓扑表中 Destination’s MPR 相等的路由表记录的 R_next_addr c. R_dist = h + 1
  4. 计算完路由表后，如果想节省空间，可以删除拓扑表中没有用到的字段。

OLSR 协议相对 AODV 复杂，RFC 页数就是其2倍，以上内容是我根据相关材料进行的总结。

此外，我们组研读了 OLSR 协议的 RFC，整理的完整版 PDF 在这里。

参考