精华内容
下载资源
问答
  • OLSR协议
    2022-05-08 09:54:22

    ● 最优化链路状态(Optimized Link State Routing)协议
    ● 主动式路由协议

    特征

    ● OLSR协议是经典链路状态算法的最优化版本,以满足移动无线局域网的要求
    ● OLSR协议使用逐跳路由,即每个节点使用其本地信息为分组选择传输路由
    ● OLSR协议中的主要概念是多点中继(MultiPoint Relay, MPR)
    ● MPR是专门选定的节点,用于在泛洪过程中转发广播消息.

    ● OLSR协议采用三种优化技术
    ● 第一种优化是采用多点中继技术,在网络泛洪时只允许MPR节点转发广播消息,而不像经典泛洪机制那样每个节点重传其第一次接收到的每个消息,从而大幅度降低消息开销
    ● 第二种优化就是只允许选作MPR的节点产生链路状态信息,因此在网络中泛洪的控制消息最少
    ● 第三种优化是MPR节点可能选择只报告其自己与其MPR选择器之间的链路状态

    ● 对比经典链路状态算法, OLSR协议的局部链路状态信息分布在网络中
    ● 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 计划的一个组成部分)中开发出来的

    概述

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

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

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

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

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

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

    ● OLSR协议不要求对IP分组格式做任何改变。因此,在使用现有IP协议栈时,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接口的地址。
      a. 单OLSR接口节点必须使用其唯一的OLSR接口地址作为其主地址
      b. 多OLSR接口节点必须选择其中一个OLSR接口地址作为其“主地址”(等效于“路由器识别码ID”或者“节点识别码ID")
      c. 一个节点选择哪个地址并不重要,但是应该总是使用同一个地址作为其主地址。
    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

    适用性

    ● OLSR是一个主动式MANET路由协议
    ● 由于MPR在规模大、节点密度高的移动网络中表现良好,网络规模越大、节点密度越高,MPR优化的效果越好
    ● 因此OLSR协议特别适用于规模大、节点密度高的移动网络
    ● OLSR协议也非常适用于在较大的节点组之间进行随机、零星的传输,而几乎总是排斥在较小的特定节点组之间进行传输
    ● OLSR协议作为一个主动式路由协议也适用于通信节点对随着时间的流逝而变化的场合
    ● 在这种场合下,OLSR协议一直在为所有已知目的节点维护路由,因而不会产生额外的控制开销

    多点中继

    ● 多点中继的思想是通过降低相同区域内的冗余重传而将消息在网络中的泛洪开销降低到最低程度
    ● 网络中的每个节点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消息中的选择器节点来说明

    更多相关内容
  • OLSR协议

    千次阅读 2021-02-09 11:44:03
    移动ad hoc网络中的一些路由协议OLSR协议OLSR概述OLSR术语OLSR协议OLSR概述OLSR术语 OLSR协议 OLSR概述 OLSR术语 OLSR协议 OLSR概述 对于传统链路状态路由算法来说,我们让网络拓扑中的每个节点(路由器)向其他所有...

    一、OLSR协议

    1、OLSR概述

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

    2、OLSR术语

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

    3、多点中继(MPR)

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

    4、分组处理以及转发流程

    对于网络中的每一个节点,维护一个“重复元组”(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、信息储存

    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。

    6、多接口

    但如果一个节点有多个接口运行OLSR该怎么办呢?我们可以用MID信息去判断。
    下图为MID消息格式,MID消息是OLSR消息格式中的数据组成部分(分组长度,序列号等未画出)
    在这里插入图片描述
    接口地址不包含主接口,因为主接口在OLSR协议的分组格式中已经在“消息源节点地址”中列出。如果只有一个接口运行OLSR,不产生任何MID信息。

    6.1、MID消息转发

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

    6.2、MID消息处理

    通过采用MID消息交换的信息来更新多接口关联信息库
    在这里插入图片描述
    通过MID信息,我们可以从任意一个接口推断出其节点主地址

    7、HELLO消息

    接下来我们需要讨论如何建立本地链路信息库以及相邻接点信息库,我们需要有一种能够互相交换的机制,即互相周期性的发送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选择器。

    8、TC消息

    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、路由表计算

    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

    10、参考文献

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

    展开全文
  • 高速移动自组网OLSR路由协议研究与改进,对想要学习自组网的人来说非常有参考价值!
  • 此代码演示了在优化链路状态路由 (OLSR) 路由协议中选择多点中继节点的算法。 选择器脚本分两个主要步骤工作: 1- 选择覆盖隔离的第二跳邻居的第一跳邻居。 2- 根据最大​​覆盖标准选择额外的第一跳邻居。 当所有...
  • ns2仿真将olsr协议与aodv协议和dsr协议比较,基于aodv设计一种更有效的路由协议
  • olsr协议规范源码

    2015-04-29 09:46:36
    本文档为olsr协议的规范源码,英文版本,有需要的同学拿去。
  • AODV和OLSR协议仿真脚本文件
  • 提出了一种基于跨层快速邻居感知的OLSR协议――FS-OLSR,协议在采用hello消息进行链路感知和邻居探测的基础上,结合链路层反馈的信息对网络层邻居表进行更新,以增强节点的邻居感知能力;并将邻居节点的新鲜度作为...
  • 【Ad Hoc】叁 OLSR 协议详解

    千次阅读 多人点赞 2020-03-14 10:58:22
    1、LSR 协议 LSR 为基于链路状态的路由算法。如何判断链路状态呢?在无线通信的环境下,只需要节点能够收到另一节点的包,就说明链路有效。另一方面,为了建立端到端的路径,路由算法需要发现并检查一跳由多个单跳...

    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 addressDestination’s MPRMPR SelectorSequence NumberHolding 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 OriginatorMPR SelectorMPR Selector Sequence
    MA1
    MB1
    MC1

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

    Destination addressDestination’s MPRMPR SelectorSequence Number
    AM1
    BM1
    CM1

    网络中周期性的通过 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 在这里


    参考

    展开全文
  • 根据Linux操作系统中路由体系结构的特点,设计了实现OLSR协议的整体框架,描述实现OLSR协议的程序架构,介绍了在这种架构中实现协议的关键技术,分析支持IPv6地址所需要的实现OLSR协议的主要困难并给出解决方法;...
  • Linux操作系统基于IPv6地址的OLSR协议实现方案.pdf
  • 1.下载olsr协议的源码 olsr协议源码 2.将下载好的OLSR协议源码压缩包um-olsr-1.0.tgz拷贝到ns-allinone-2.35/ns-2.35目录下。 tar zxvf um-olsr-1.0.tgz 3.在ns-allinone-2.35/ns-2.35目录下,创建一个连接 sudo ...

    1.下载olsr协议的源码
    olsr协议源码
    在这里插入图片描述

    2.将下载好的OLSR协议源码压缩包um-olsr-1.0.tgz拷贝到ns-allinone-2.35/ns-2.35目录下。

    在这里插入图片描述
    在ns-2.35目录下

    tar zxvf um-olsr-1.0.tgz
    

    在这里插入图片描述

    3.在ns-allinone-2.35/ns-2.35目录下,创建一个连接

    sudo ln -s ./um-olsr ./olsr
    

    在这里插入图片描述
    4. 在ns-allinone-2.35/ns-2.35目录下,打OLSR补丁

    sudo patch -p1 < olsr/um-olsr_ns-2.35_v1.0.patch
    

    (2.35表示对应的NS版本,目录下还有其他版本的补丁)
    在这里插入图片描述
    5.进入ns-allinone-2.35目录下,执行以下命令

    sudo apt-get update      #更新源列表
    sudo apt-get upgrade   #更新已安装的包
    #安装依赖包:
    sudo apt-get install build-essential
    sudo apt-get install tcl8.5 tcl8.5-dev tk8.5 tk8.5-dev
    sudo apt-get install libxmu-dev libxmu-headers
    sudo ./install
    

    出现以下错误
    在这里插入图片描述解决方案:
    在common/packet.h中添加olsr

    在这里插入图片描述
    6.再次返回到ns-allinone-2.35目录下,执行以下命令

    sudo apt-get update      #更新源列表
    sudo apt-get upgrade   #更新已安装的包
    #安装依赖包:
    sudo apt-get install build-essential
    sudo apt-get install tcl8.5 tcl8.5-dev tk8.5 tk8.5-dev
    sudo apt-get install libxmu-dev libxmu-headers
    sudo ./install
    

    出现以下内容,说明NS2再次已经安装成功,此时olsr协议也已经加进来了
    在这里插入图片描述
    在这里插入图片描述
    6.测试
    测试文件在我的百度云盘里
    https://pan.baidu.com/s/1DIgrCIndoRvyem3H6BHhaQ
    密码为 jh81
    将olsr的测试文件都复制到ns-2.35目录下:
    在这里插入图片描述
    执行

    ns olsr.tcl
    

    出现以下错误
    在这里插入图片描述
    解决方案:

    sudo apt install ns2
    

    在这里插入图片描述
    再次执行

    ns olsr.tcl
    

    出现以下错误
    在这里插入图片描述
    解决方案:

    sudo apt install tclsh
    sudo cp ns-allinone-2.35/bin/ns /usr/local/bin/ns
    

    在这里插入图片描述
    如果这个不能移动的话,可以试试以下命令

    sudo make clean
    sudo make
    sudo make install
    

    再次执行

    ns olsr.tcl
    

    在这里插入图片描述

    先按ctrl+c停止当前的操作

    执行以下操作

     nam olsr.nam 
    

    出现以下错误:
    在这里插入图片描述
    解决方案

    sudo apt install nam
    

    在这里插入图片描述
    再次执行以下操作

     nam olsr.nam 
    

    出现这个图片

    在这里插入图片描述

    展开全文
  • 根据Linux操作系统中路由体系结构的特点,设计了实现OLSR协议的整体框架,描述实现OLSR协议的程序架构,介绍了在这种架构中实现协议的关键技术,分析支持IPv6地址所需要的实现OLSR协议的主要困难并给出解决方法;...
  • 分析了自组网中 OLSR(Optimized Link State Routing Protocol)路由协议的脆弱性以及它可能遭受的各种攻 击。针对这些潜在的攻击,将公钥机制和信任模型结合,提出了一种防御方案,该方案结合了以反应式 PKI为基 础进行...
  • Linux虚拟机下OLSR协议的安装

    千次阅读 2018-04-07 10:57:35
    简单来说,OLSR协议是用于MANET网络的路由协议,不说废话,开始OLSR协议安装过程。(1)装一个Linux虚拟机(2)新装的Linux虚拟机没有bison以及flex(两个语法分析器) 获取管理员权限: 安装bison语法分析器: ...
  • 无线Mesh网中基于OLSR协议的区域移动性网络端管理方案,何炬,,为使移动用户在切换无线Mesh网络中不同的WLAN接入点时,不会因为接入点和终端IP地址的变化而失去原有端到端数据连接,提出了一个涵��
  • OLSR路由协议详解 一

    千次阅读 2021-09-28 16:23:35
    OLSR路由协议,全称为Optimized Link State Routing,中文名为优化链路状态路由协议。 下面可能会用到的概念: 邻居节点:如果节点可以监听到节点 X,则节点 X 是节点的邻居节点。 2 跳邻居:通过邻居节点监听到...
  • OLSR协议包括一个“内核”功能模块和一个辅助功能模块,内核功能模块对于OLSR操作总是需要的 ● 根据其功能,内核详细说明一个协议能够为一个独立的MANET网络提供路由 ● 每个辅助功能提供其他适用于特定情形的...
  • 非常通透
  • Ad Hoc网络又称为多跳网络、无固定基础设施的网络或自组织网络,是由一组带有无线收发装置的自主的无线节点或终端通过相互合作形成的网络,可以独立于固定的基础设施,是一种自创造、自组织和自管理的网络。
  • OLSR协议原版

    2011-11-23 20:51:06
    经典路由协议之一,属于表驱动路由协议,是无线网络领域的经典。原版文献。
  • Linux linux linux linux
  • (可参考“OLSR路由协议 小细节_xihuanmadaima的博客-CSDN博客) 最后,若数据包被判断为需要处理,则根据Message Type的类型进行相应的处理。 数据包转发过程 遇到以下情况,数据包不会被转发: 节点的重复集合中...
  • nbsplinux/Unix相关Linux操作系统基于IPv6OLSR协议实现方案.pdf5页本文档一共被下载:次,您可全文免费在线阅读后下载本文档。 下载提示1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的...
  • 比较了aodv协议和olsr协议在城市环境的车载网中的性能指标差异。
  • 【程序老媛出品,必属...资源名:matlab aodv路由协议 程序源码.zip 资源类型:程序源代码 源码说明: 基于matlab实现aodv路由协议的程序 包含完整源码和注释 非常适合借鉴学习 适合人群:新手及有一定经验的开发人员
  • OLSR路由协议基础知识【路由协议

    万次阅读 多人点赞 2018-10-26 14:47:48
    OLSR 协议基础介绍 本文描述了一个针对移动 Ad Hoc 网络的链路状态协议 OLSR。该协议是针对移动无线局域网需求的经典链路状态算法的优化协议协议中关键概念是MPRs。MPR 称之为多中继依赖节点,它是协议中消息洪泛...
  • 想问一下公司olsr协议在Linux里怎么做数据收发</p>
  • 用的人不多,呵呵,所以分稍微高点. 该代码是用来测试OLSR协议性能的,另外还带了能量模型

空空如也

空空如也

1 2 3 4 5 ... 19
收藏数 366
精华内容 146
关键字:

OLSR协议