OLSR协议

对于传统链路状态路由算法来说，我们让网络拓扑中的每个节点（路由器）向其他所有节点广播自己的链路状态分组，这个过程被称为泛洪。其中每个链路状态分组均包含节点所连接的链路标识和开销。最终经过泛洪的网络拓扑中的每个节点都能得到一幅相同的网络拓扑图。而OLSR（最优化链路状态协议）对传统算法进行优化。其中每个节点选择自己的邻居节点中的一部分来作为MPR节点（多点中继），只允许MPR节点进行泛洪广播并传播控制消息，从而减少了传输信息量。对于网络中的任意节点A，若它被它的一条邻居对称节点选为MPR节点，则A在网络中周期性的广播其链路状态控制信息。
OLSR协议可以通过改变最大传输时间间隔从而改变对网络拓扑变化的反应，此外通过全分布方式工作，无中心节点，不要求可靠传输（节点周期发送控制信息，总有一个是对的对吧）
因此，OLSR协议适用于规模大、节点密度高的场合

术语以及各种消息格式见RFC3626，懒得写了
注意一点，一个节点可以有多个OLSR接口，每个OLSR接口分配一个IP。主地址则是一个运行OLSR协议的接口的IP地址

网络拓扑中的任意节点S从其对称一跳相邻节点集合中选取一个集合（MPR集），只有位于MPR集合中的节点会广播从S点发送的消息，而其余节点只会处理该传播信息而并不会进行广播。MPR集也被写作MPR（S）。
选出的MPR集需要能够传输信息到S节点的所有对称严格二跳节点。计算MPR集所需要的信息通过节点之间周期性的交换HELLO信息获取。
来个图片，下图中带阴影的节点就是MPR节点

对于网络中的每一个节点，维护一个“重复元组”（Duplicate Tuple）
(D_addr, D_seq_num, D_retransmitted, D_iface_list,D_time)
其中D_addr是本消息源节点地址，D_seq_num是本消息序列号，D_retransmitted是布尔值，用于判断本消息是否被转发过，D_iface_list是已经收到本消息的接口地址列表，D_time是本消息的生存剩余时间（TTL）
分组处理算法

分组处理以及转发流程

5.1、多接口关联信息

用于将不同接口以及对应节点相联系起来，一般用于多OLSR接口节点
(I_iface_addr, I_main_addr, I_time)，I_iface_addr, I_main_addr为节点接口地址以及对应节点地址，I_time是TTL

5.2、本地链路信息

储存本地节点链路信息
(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过期时，该链路被视为丢失。

5.3、相邻节点信息

本信息库储存相邻节点集、二跳相邻节点集、MPR集、MPR选择器集，见RFC3626 P23 4.3
e.g. 如果节点A将他的邻居节点B选做MPR，则A是B的MPR选择器

5.4、拓扑信息

即网络拓扑信息，描述网络的物理或者逻辑布局。
网络中的每个节点都维护着网络的拓扑信息。这些信息是从TC信息中获取的，用于路由表的计算。
因此，对于网络中的每一个目的地，至少会记录一个 “拓扑元组”(T_dest_addr, T_last_addr, T_seq, T_time)。
T_dest_addr是本节点的主地址，从主地址为T_last_addr的节点跳一跳就可以到达。换言之T_last_addr为源节点（邻居节点），T_dest_addr为目的节点（本节点）。通常，T_last_addr是T_dest_addr的MPR。T_seq是一个序列号，T_time指定了这个元组的TTL。

但如果一个节点有多个接口运行OLSR该怎么办呢？我们可以用MID信息去判断。
下图为MID消息格式，MID消息是OLSR消息格式中的数据组成部分（分组长度，序列号等未画出）

接口地址不包含主接口，因为主接口在OLSR协议的分组格式中已经在“消息源节点地址”中列出。如果只有一个接口运行OLSR，不产生任何MID信息。

6.1、MID消息转发

采用默认转发算法，见分组转发算法

6.2、MID消息处理

通过采用MID消息交换的信息来更新多接口关联信息库

通过MID信息，我们可以从任意一个接口推断出其节点主地址

接下来我们需要讨论如何建立本地链路信息库以及相邻接点信息库，我们需要有一种能够互相交换的机制，即互相周期性的发送HELLO信息。与MID消息一样，HELLO消息格式仍然借用OLSR协议的通用分组格式，见RFC3626 6.1，HELLO消息可以进行链路探测以及生成各种集合

为了检测该节点接口与相邻接点接口的链路，本地节点接口需要进行链路探测，并且将本地节点的相邻结点接口广播到每个接口上。

7.1、链路探测

每个节点都要探测与其邻节点间的链路，由于无线传播的不确定性，某些链路可能会被认为是单向的。因此，所有链路必须双向验证才被认为是可用的。链路感知是通过 HELLO 分组的周期性交互实现的。本地链路信息表存储了该节点到邻居节点的链路信息。节点发送 HELLO 分组时，本地链路信息表作为消息的内容。节点收到 HELLO 分组，更新本地链路信息表。
接收到HELLO分组，如果HELLO分组的源节点地址不存在于本地链路信息表的邻居节点列表中，则在本地信息库中新建一个邻居节点，此时链路只能判断是单向的（本地节点并没有去往外发送信息）

如果HELLO分组的源节点地址存在于本地链路信息表的邻居节点列表中，则更新：
L_ASYM_TIME=当前时间+有效时间
如果本地节点的接口信息存在于HELLO分组的链路信息中，说明邻居节点曾经接收过本地节点的信息，链路为双向，更新如下：

7.2、相邻节点集生成

相邻节点集与本地链路信息库有着紧密联系，每次收到HELLO消息之后，更新本地链路信息库，随后根据链路的改变增添或者删减相邻节点。确保做到每一条链路都对应一个节点，每一个节点至少对应一条链路。

7.3、二跳相邻节点集生成

在初始化阶段, 如下图所示, 当节点A收到一个来自于邻居节点B的HELLO分组, A将B放入自己的邻居集中, 并将到B的链路标记为非对称状态, 然后, 在A向B发送HELLO分组时, 在HELLO分组之中包含非对称链路状态信息。在分组到达B以后，B将链路状态更新为对称的，最后B在把HELLO分组发送给A

二跳相邻节点集是有一条对称链路到达对称相邻节点的节点集合
当一个本地节点A接收到其相邻节点B发来的一个HELLO分组时，应该更新其二跳相邻节点集，如果HELLO消息是相邻节点B发来的并且B在A的本地链路信息库中（即找到了L_neighbor_iface_addr）并且对称链路时效未过，说明A,B为对称链路。此时B发出的HELLO消息中的相邻节点大部分均为二跳相邻节点。
如果HELLO中的相邻节点为A，丢弃该节点；
如果HELLO中的相邻节点类型为对称相邻节点或MPR相邻节点，将该相邻节点视为二跳相邻节点；
如果HELLO中的相邻节点类型为非对称相邻节点，将该相邻节点从二跳相邻节点中删除；

7.4、MPR集生成

对于网络中的节点，该节点的所有MPR节点的对称一跳相邻区域包含该节点的对称严格二跳相邻区域，还是这张图，当然MPR最少肯定是这四个点，不过如果把MPR节点集看做是S的所有相邻一跳节点我也没意见，但这样会使得OLSR协议开销变大

当然，由于MPR集的相邻节点覆盖二跳节点，因此当对称相邻节点或者对称严格二跳相邻节点变化的时候，需要重新计算MPR集。

7.4.1、MPR集生成算法

（本节算法来自于郑伟明《OLSR路由协议研究及仿真》）

接下来我们详细介绍该算法，我们利用该算法求出节点0的MPR集

首先介绍一些之后会用到的重要概念。
N：一个节点的一跳邻居节点集，如上图中的节点 1 到节点 6 为节点 0 的 N。
N2：一个节点的两跳邻居节点集，如上图中的节点 a 到节点 f，但其中不包括：

1. 只能通过集合 N 中某成员到达的节点，而此成员的 willingness （意愿）为WILL_NEVER。如上图中，节点 a 只能通过 N 中成员节点 1 到达，若节点 1 的 willingness 为 WILL_NEVER，则节点 a 不属于 N2。
2. 进行计算的这个节点。如上图中节点 0 不属于 N2。
3. 所有的对称邻居：它们与此节点的某些接口间存在对称链路。如上图中的节点 2，他虽然可以通过节点 1 两跳到达，但与节点 0 具有对称链路，所以不属于 N2。

D(y)：一跳邻节点 y 的深度(y 为 N 的一个成员)，被定义为节点 y 对称邻节点的数量，不包括 N 的所有成员以及进行计算的这个节点。如上图，节点 1 的深度为 2，包括了节点 a 和节点 b。
Reachability：可达性，此概念在进行 MPR 集计算时用到。表示在去除所有此时的 MPR 集节点及其覆盖的两跳节点后。某一跳邻节点的对称邻节点数量，不包括 N 的所有成员以及进行计算的这个节点。如上图，若此时只有节点 1 被选为MPR，则计算节点 2 的到达性为 2，包括节点 c 和节点 d，而不包括被节点 1 覆盖的节点 b。
算法具体过程如下：

1. 开始的 MPR 集由 N 中所有 N_willingness 为 WILL_ALWAYS 的成员构成；
2. 对于所有 N 中的节点 y，计算 D(y)；
3. 将 N 中满足如下条件的节点加入到 MPR 集：它是到达 N2 中某一节点的唯一节点。举例来说，如上图，N2 中的节点 a 只能通过对称链路到达 N 中的节点 1，则将 1 加入 MPR 集。移除 N2 中目前被 MPR 集覆盖的节点。
4. 当 N2 中存在不被 MPR 集中任何节点覆盖的节点，执行以下过程。若不存在，算法结束。
   1. 对 N 中的每个节点，计算其到达性。
   2. 在 N 中到达性非 0 且具有最高 N_willingness 的节点中选择一个 MPR，有多个选择时，选择可达性最高的。还有多个选择时，选择 D(y)高的。移除 N2 中目前被 MPR 集覆盖的节点。回到第 3 步。
5. 将节点每个接口的 MPR 集组合在一起，则建立起该节点的 MPR 集。
   下图说明了一个标准 MPR 选择算法选择 MPR 集的具体例子：在第一步，节点 N 选择节点 1 作为其 MPR，因为其节点 1 是到节点 a 的唯一节点。在第二步，N 选择节点 2 为其 MPR，因为节点 2 覆盖了两个未被覆盖的两跳节点且具有最高的深度。之后根据算法流程，节点 3 覆盖了节点 e，节点 4 覆盖了节点 f，相继入选 MPR。最终覆盖所有两跳节点。
   
   但是本算法有个缺点，即不能保证MPR集的最优

7.5、MPR选择器集生成

当本地节点收到HELLO消息以后，在消息列表中查询自己的接口地址，如果信息中标明自己的接口地址的相邻节点类型为MPR_NEIGH（MPR相邻节点），更新MPR选择器集合，如果不存在该项则创建该项，如果存在该项更新该项生存时间。之后删除已经过期的MPR选择器。

TC消息用于描述网络拓扑，从而计算路由，其中至少需要包含所有MPR选择器集。

8.1、TC消息格式

RFC3626 P43 9.1
ANSN为广播相邻节点序列号，每次加1用来判断更新

8.2、TC消息处理

拓扑表中的表项是根据 TC 分组中的拓扑信息建立的。在 TC 分组重复记录表中登记了 TC 分组后，就在拓扑表中记录相关信息，步骤如下

1. 如果拓扑表中存在某个表项，其 T_last_addr 对应于 TC 分组发送源节点地址且其T_seq 大于收到消息中的ANSN的值，那么，就不再对 TC 分组做进一步处理，丢弃该 TC 分组。
2. 删除拓扑表中所有 T_last_addr 对应于 TC 分组发送源节点地址，且其 T_seq 小于收到分组中ANSN的值的表项。
3. 对从 TC 分组中接收到的每个 MPR选择器的地址：如果拓扑表中存在某个条目，其 T_dest_addr 对应于 TC 分组中的 MPR选择器地址，且其 T_last _addr对应于 TC 分组中初始发送节点地址，则更新该条目的保持时间T_time； 否则，就在拓扑表中记录新的拓扑条目。

9.1、路由表格式

(R_dest_addr, R_next_addr, R_dist, R_iface_addr)
R_dest_addr：目的节点地址
R_next_addr：到目的节点地址的下一跳接口地址
R_dist：本地节点到目的节点的跳数
R_iface_addr：本地接口地址

9.2、路由表计算

参考周懿《Ad Hoc网中多信道OLSR路由协议研究》
算法思路大致如下：
首先先将跳数h=1的节点（邻居节点）放入路由表中，之后将跳数h=2的节点（二跳邻居节点）放入路由表中，最后一步步添加距离为h，h+1的路由表项，直到最后一遍无新增表项后停止。
具体按照如下的步骤进行：

1. 删除路由表中的所有表项记录
2. 从对称的邻居节点开始，将它们作为距离为一跳的目的节点(h=1)，加
   入路由表
   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 = main address of the neighbor
   R_next_addr = L_neighbor_iface_addr
   R_dist = 1
   R_iface_addr = L_local_iface_addr
3. 对每个两跳邻居节点，按照下面的方法将它们作为距离为两跳的目的
   节点(h=2)，增加路由表项
   R_dest_addr = the main address of the 2-hop neighbor;
   R_next_addr = R_next_addr，等号右边的式子是在路由表中找到此二跳邻居节点的邻居节点，是这个邻居节点的R_next_addr
   R_dist = 2
   R_iface_addr = R_iface_addr，等号右边的式子是在路由表中找到此二跳邻居节点的邻居节点，是这个邻居节点的R_iface_addr
4. 接下来向路由表中添加距离为(h＋1)的目的节点的路由表项，从 h＝2 开始，按照下面方法
   1. 对于本地节点拓扑表中的每个表项，如果在路由表中没有任何一
      条 表 项 的 R_dest_addr 等 于 T_dest_addr （拓扑表中的目的节点）， 同 时 在 路 由 表 中 存 在R_dest_addr 等于 T_last_addr（对应T_dest_addr的上一个拓扑节点），它的那么为路由表增加一条新的表项
      R_dest_addr = T_dest_addr;
      R_next_addr = 已有的具有如下特征的路由表表项的R_next_addr：其R_dest_addr==T_last_addr
      R_dest_addr = T_last_addr
      R_dist = h+1
      R_iface_addr = 已有的具有如下特征的路由表表项的 R_iface_addr：其R_dest_addr == T_last_addr

陈林星等著《移动Ad Hoc网络——自组织分组无线网络技术》
T. Clausen and P. Jacquet. Optimized Link State Routing Protocol (OLSR). RFC3626, October 2003.
郑伟明《OLSR路由协议研究及仿真》
周懿《Ad Hoc网中多信道OLSR路由协议研究》
[美]斯特凡诺·巴萨尼等著《移动Ad Hoc网络》