• 相邻节点探测的作用是建立相邻区域信息库
  • 相邻节点探测涉及到各个节点及其主地址

  • 相邻节点探测机制就是周期性交换HELLO消息

    相邻节点集的生成

  • 一个节点根据链路数组维护一个相邻节点数组集合

  • 根据链路集合的变化更新相应信息
  • 链路集合保存有关链路的信息，而相邻节点集合保存有关相邻节点的信息

  • 这两个集合之间的关系非常明显，这是因为当且仅当一个节点和另一个节点之间至少存在一条链路时，那么这个节点就是另外一个节点的一个相邻节点

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

  • 一个链路数组的“关联相邻节点数组(associated neighbor tuple)”若存在的话，则等于该相邻节点数组
  • 其中N_neighbor_main_addr = L_neighbor_iface_addr的主地址
  • 一个相邻节点数组的“关联链路数组(associated link tuples)”等于所有的链路数组

  • 其中N_neighbor_main_addr = L_neighbor_iface_addr 的主地址

  • 必须通过维护链路数组和关联相邻节点数组之间的适当关系来建立相邻节点集合，具体如下:

    • 数组建立(Creation)

每当出现一条链路的时候，也就是每当建立一个链路数组的时候，假如其关联相邻节点数组不存在
则必须建立，采用的数值如下:
N_neighbor_main_addr = L_neighbor_iface_addr 的主地址(来自本链路数组)
无论如何，必须按照下面描述的操作步骤计算N_status (该相邻节点的状态)

  • 更新(Update)

每当一条链路变化时，也就是每当一个链路数组的信息被修改的时候
该节点必须确保其关联相邻节点数组的状态N status 满足以下特性:
假如该相邻节点有一个关联链路数组指出一条对称链路(即: L _SYM time 2 current time(当前时间))
则将N_status设为SYM (对称相邻节点)
否则，将N_status 设为NOT_SYM (非对称相邻节点)

  • 删除(Removal)

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

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

  • 对HELLO消息的处理描述如下:

    • 一条HELLO消息的“消息源节点地址”等于产生和发送本条消息的节点的主地址
    • 同样，必须根据该条HELLO消息的愿意组成域设置计算“愿意”设置
    • 一个节点接收到一条HELLO消息后,应该按照前面描述的方法首先更新其链路集合
    • 然后应该按照如下方法更新其相邻节点集合:

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

二跳相邻节点集的生成

  • 二跳相邻节点集合描述有一条对称链路到达一个对称相邻节点的节点的集合

  • 通过如下描述的周期性交换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= 该二跳相邻节点的主地址

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. 一个接口的相邻节点
    1. 假如一个本地节点上的一个接口存在一条链路到达一个相邻节点的任何一个接口，那么这个本地节点就是“该接口的一个相邻节点”
  2. 从一个接口可达的二跳相邻节点
    1. 指一个节点的二跳相邻节点列表，从该接口的相邻节点可达该节点
  3. 一个接口的MPR集合
    1. 指一个接口的相邻节点集合(子集)，这些相邻节点被设置成愿意为其他节点转发信息，通过这些选定的相邻节点，从该接口可达所有严格二跳相邻节点
  4. 集合N
    1. 表示一个节点的相邻节点子集，这些相邻节点是每个接口I的相邻节点
  5. 集合N2
    1. 表示从每个接口I可达的二跳相邻节点集合，但是不包括:
      • 只能通过集合N的不愿意为其他节点转发信息的成员节点到达的那些节点;
      • 正在执行该MPR计算的那个节点;
      • 全部对称相邻节点。对于这些相邻节点，在某个接口.上存在一条链路到达该节点。
  6. D(y)
    1. 表示一个一跳相邻节点y的密度(这里y是集合N中的一个成员节点)，定义为节点y的对称相邻节点的数量，但是不包含集合N的所有成员节点以及正在执行该MPR计算的那个节点
  • OLSR协议的搜索方法如下:
  • 第一，从一个MPR集合开始计算，该MPR集合由集合N的全部成员节点组成

其Nwillingness 域设为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而不会造成其他的性能损失

MPR选择器集的生成

  • 一个节点n的MPR选择器集合由已经将节点n选作MPR的节点的主地址构成

  • 通过发送HELLO消息来通知MPR的选择

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

  • 必须根据本条HELLO消息头部的接收信息有效时间(Vtime)域计算其“有效时间(ValidityTime)”

  • 然后应该按照以下方法更新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选择器数组

相邻区域和二跳相邻区域变化

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

  • 一个链路数组的L_SYM_time域时间已经结束

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

  • 在链路集合中添加了一个其L_SYM_time 域时间还没有结束的新链路数组，

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

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

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

  • 发生相邻节点丢失时其N_neighbor_main_addr等于该丢失相邻节点主地址的所有二跳相邻节点数组必须被删除
  • 发生相邻节点丢失时，其MS_main_addr等于该丢失相邻节点主地址的所有MPR选择器数组必须被删除
  • 当检测出丢失或者出现一个相邻节点时，或者当检测出二跳相邻区域内发生了变化时，必须重新计算MPR集合
  • 当MPR集合变化时，可以为此单独发送一条 HELLO消息