程序员经验分享-hwhale

【Ad Hoc】叁 OLSR 协议详解

2023-05-16

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 在这里。

参考

  • Ad Hoc Networks: Routing, QoS and Optimization
  • RFC 3626 Optimized Link State Routing
  • Optimized Link State Routing Protocol for Ad Hoc Networks
  • OLSR: Optimized Link State Routing
  • OLSR routing protocol in NS2
  • OLSR 路由算法原理
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

【Ad Hoc】叁 OLSR 协议详解 的相关文章

  • 04 Mybatis的增删改查

    1 mybatis中sql语句的占位符与parameterType 与 parameterType 表示一个占位符 向占位符输入参数 mybatis自动进行java类型和jdbc类型的转换 程序员不需要考虑参数的类型 比如传入字符串 myb

  • C++链表的各种操作

    题目描述 代码 include lt iostream gt include lt algorithm gt using namespace std struct sqList int data sqList next sqList Lis

  • HJ001 字符串最后一个单词的长度

    目录 题目描述 输入描述 输出描述 输入 输出 做题思路 AC代码 题目描述 计算字符串最后一个单词的长度 xff0c 单词以空格隔开 输入描述 输入一行 xff0c 代表要计算的字符串 xff0c 非空 xff0c 长度小于5000 输出

  • 盲签名 blind signature 简介

    转 https blog csdn net zhang hui cs article details 8728776 盲签名 Blind Signature 定义 是一种数字签名的方式 在消息内容被签名之前 对于签名者来说消息内容是不可见的

  • VMware 虚拟机安装 OpenWrt 作旁路由 单臂路由 img 镜像转 vmdk 旁路由无法上网 没网络

    重要注意事项 由于布线原因笔记本只能采用无线的方式连接路由器 xff0c 在Windows10的环境下使用无线网卡桥接 xff0c 结果软路由无法上网 xff0c 翻阅了各种帖子最终发现跟系统底层的协议栈有关系 xff0c 随即放弃使用有线

  • HJ002 计算某字母出现的次数

    目录 题目描述 输入描述 输出描述 输入 输出 做题思路 1 AC代码 1 做题思路 2 AC代码 2 题目描述 写出一个程序 xff0c 接受一个由字母 数字和空格组成的字符串 xff0c 和一个字母 xff0c 然后输出输入字符串中该字

  • HJ003 明明的随机数

    目录 题目描述 输入描述 输出描述 输入 输出 说明 做题思路 AC代码 题目描述 明明想在学校中请一些同学一起做一项问卷调查 xff0c 为了实验的客观性 xff0c 他先用计算机生成了N个1到1000之间的随机整数 xff08 N 10

  • new，delete使用详解（动态多维数组空间申请）

    C语言中利用库函数malloc和free来分配和撤销空间的 C 43 43 中的new与delete是运算符 xff0c 不是函数 xff0c 所以执行效率更高 但C 43 43 中也是可以使用malloc和free的 但是一来不方便 xf

  • 局部，全局（外部），static等变量详解

    首先 xff0c 必须明白一个程序是包含若干个源文件 xff0c 每个源文件又是包含若干个函数 xff0c 每个源文件 函数中又定义了若干个变量 但是每个变量都有自己的作用范围 xff0c 也就是自己的作用域 只有在作用域内才可以访问变量

  • 函数的可变参数的实现

    stdarg h stdarg h是C语言中C标准函数库的头文件 xff0c stdarg是由standard xff08 标准 xff09 arguments xff08 参数 xff09 简化而来 xff0c 主要目的为让函数能够接收可

  • 常见的注入方式

    设计模式中常见的注入方式 依赖注入 最近在求职 xff0c 耽搁了 xff0c 对于应届生来讲想找个大数据相关的工作何其困难 所以在填充一些自己不足之处 xff0c 希望与君共勉 一 依赖注入DI 开发过程中 xff0c 如果发现客户程序依

  • 部分Fortify代码扫描高风险解决方案

    部分Fortify代码扫描高风险解决方案 一 Category Access Control Database 问题描述 xff1a Database access control 错误在以下情况下发生 xff1a 1 数据从一个不可信赖的

  • 中标麒麟高级服务器V7安装

    中标麒麟高级服务器V7安装 中标麒麟高级服务器操作系统软件 xff08 兆芯版 xff09 一 安装步骤 准备 xff1a 1 相关中标麒麟镜像 2 vncviewer xff0c 由它去远程连接服务器上的机器节点 1 首先进入界面呈现 该

  • Hive--OR-AND使用方法

    OR AND 数据源 xff1a 1 22 1 21 2 22 1 20 select from id age where id 61 1 or id 61 2 and age 61 22 表示 xff1a 查询id 61 1 同时age

  • gdb 打印内存和数组

    打印数组 xff1a p arrayPtr 64 256 打印256个数组元素类型元素值 xff0c 二元操作符 64 左边数组第一个元素 xff0c 右边数组长度 p x char arrayPtr 64 256 以16进制打印256个以

  • Hive--清除/删除Hive表数据,where条件

    清除Hive表数据 hive删除表 xff1a drop table table name hive删除表中数据 xff1a truncate table table name hive按分区删除数据 xff1a alter table t

  • Mysql--查询时使用SQL将字段的数据类型转换(varchar-＞int)

    查询时使用SQL将数据类型转换 在 span class token keyword sql span 里面String转 span class token keyword int span span class token punctua

  • Mysql项目实践常用操作汇总(不断更新)

    MySQL 1 主键 xff0c 索引 xff0c 引擎 CREATE TABLE 96 表名 96 96 列名1 96 int 11 NOT NULL 96 列名2 96 varchar 255 NOT NULL PRIMARY KEY

  • 大文件处理方案

    处理海量数据问题 xff0c 无非就是 xff1a 分而治之 hash映射 43 hash统计 43 堆 快速 归并排序 xff1b Bloom filter Bitmap xff1b Trie树 数据库 倒排索引 xff1b 外排序 xf

  • spark读取嵌套json代码测试示例

    示例一 示例数据 xff1a span class token punctuation span span class token string 34 name 34 span span class token operator span

随机推荐

  • Redis集群原理和总结

    Redis集群原理 节点主从 xff08 镜像全量 xff09 43 哈希slot xff08 分片 xff09 无主模型 遵循 CAP原则 C一致性 A可用性 P分区容错性 xff0c 三者不可兼得 数据放在大数据集群中的方式 集群承载数

  • Hbase基础

    Hbase 谷歌 BigTable论文 海量存储 列式存储 极易扩展 RS HDFS 高并发 稀疏性 主要是针对Hbase列的灵活性 xff0c 在列族中 xff0c 你可以指定任意多的列 xff0c 在列数据为空的情况下 xff0c 是不

  • Flink

    Flink 一 简介 Flink核心是一个流式的数据流执行引擎 xff0c 其针对数据流的分布式计算提供了数据分布 数据通信以及容错机制等功能 基于流执行引擎 xff0c Flink提供了诸多更高抽象层的API以便用户编写分布式任务 xff

  • SUMO学习入门 （二）路网文件的生成

    声明 xff1a 该文章为博主转载自知乎用户 xff1a 侘寂升平 xff0c 侵删 xff01 非常感谢知乎朋友无私分享的sumo系列文章 xff0c 给了我很多的指导 xff01 欢迎读者关注该博主 xff01 以下为转载正文 xff1

  • 第七章 结构体

    文章目录 前言一 结构体与结构体指针1 结构体的定义 引用与初始化2 结构体指针3 typedef的使用A typedef结构体B typedef整型 二 C 43 43 的引用1 数字2 指针 前言 本文主要介绍结构体的使用 一 结构体与

  • Mapreduce实例（七）：二次排序

    系统环境 Linux Ubuntu 16 04 jdk 7u75 linux x64 hadoop 2 6 0 cdh5 4 5 hadoop 2 6 0 eclipse cdh5 4 5 jar eclipse java juno SR2

  • WiFiduino+blinker+小爱同学打造智慧卧室

    系列文章目录 文章目录 系列文章目录前言一 实现功能二 所需材料三 导线连接四 软件开发1 开发环境搭建2 编写程序 五 手机操作部分1 blinkerAPP2 米家APP3 小米音箱APP 六 实物部分1 实物图片 总结 前言 本科二年级

  • 深度学习实际—手写体识别

    文章目录 前言1 什么是机器识别手写数字 xff1f 2 MNIST数据集是什么 xff1f 3 显示MNIST数据集4 名词解释4 1 图像4 2 卷积层4 3 池化层4 4 线性层4 5 激活函数4 6 损失函数 https blog

  • 简易计时器开发

    一 项目场景 xff1a 事情是这样的 xff0c 学校给了一个网页 xff0c 让我们去学习 xff0c 网页超过5分钟无操作会自动跳出 xff0c 需要一个定时器来提醒我们每隔一段时间去操作网页 xff0c 我在网上查了几个定时器 xf

  • 第9章 无监督学习

    系列文章目录 第1章 绪论 第2章 机器学习概述 第3章 线性模型 第4章 前馈神经网络 第5章 卷积神经网络 第6章 循环神经网络 第7章 网络优化与正则化 第8章 注意力机制与外部记忆 第9章 无监督学习 第10章 模型独立的学习方式

  • 第1章 计算机组成原理概述

    文章目录 前言1 0 课程简介1 0 1 课程的地位1 0 2 课程学习思路1 0 3 课程组成 1 1 计算机系统简介1 1 1 计算机组成1 计算机的类型2 计算机的组成3 软件组成 1 1 2 计算机系统的层次结构1 物理层方面2 程

  • ASGCN之图卷积网络(GCN)

    文章目录 前言1 理论部分1 1 为什么会出现图卷积网络 xff1f 1 2 图卷积网络的推导过程1 3 图卷积网络的公式 2 代码实现参考资料 前言 本文从使用图卷积网络的目的出发 xff0c 先对图卷积网络的来源与公式做简要介绍 xff

  • 深度学习领域的多任务学习综述

    文章目录 前言1 什么是多任务学习 xff1f 2 为何要使用多任务学习 xff1f 3 多任务学习有哪些类型 xff1f 3 1 基于硬参数共享的多任务学习3 2 基于软参数共享的多任务学习 4 为什么多任务学习能提升模型的性能 xff1

  • ASGCN之依存句法图的构建

    文章目录 前言1 理论部分1 1 依存句法理论1 2 依存句法分析1 3 依存句法的应用 2 代码实践2 1 数据集2 2 代码实现2 3 效果查看 总结 前言 本文首先介绍依存句法理论 xff0c 之后通过代码实现ASGCN中的依存句法图

  • 关于语言信息的理解

    文章目录 前言1 语法与语义的区别与联系1 1 语法1 1 1 含义1 1 2 使用Spacy获取文本的语义信息的方法 1 2 语义1 2 1 含义1 2 2 使用Spacy获取文本的语法信息的方法 2 代码实现语法与语义的获取2 1 常见

  • 对抗攻击和防御

    目录 对抗攻击防御References 对抗攻击 在计算机视觉任务中可能存在以下现象 xff0c 对输入样本故意添加一些人类无法察觉的细微干扰 xff0c 将会导致模型以高置信度输出一个错误的分类结果 xff0c 这被称为对抗攻击 对抗攻击

  • openstack 网络发展简史

    openstack 网络发展简史 研究openstack有2个月的时间 xff0c 这段时间从网上获取N多宝贵资料 xff0c 对我的学习有很大帮助 xff0c 在加上我自己的研究 xff0c 终于对openstack整个网络体系有了个浅显

  • SphereFace：深度超球面embedding(CVPR2017)

    目录 前置内容Center LossContrastive Loss 摘要1 Introduction2 Related Work2 1 Metric learning2 2 Deep face recognition 3 Deep Hyp

  • Pytorch 分布式并行DDP 卡死 挂起

    问题描述 xff1a 1 使用A30显卡 xff0c 使用分布式并行Distributed Data Parallel xff0c 运行程序时显卡显存充满 xff0c 卡在设置local rank处 xff0c 并未启动进程组 2 如图 x

  • 【Ad Hoc】叁 OLSR 协议详解

    1 LSR 协议 LSR 为基于链路状态的路由算法 如何判断链路状态呢 xff1f 在无线通信的环境下 xff0c 只需要节点能够收到另一节点的包 xff0c 就说明链路有效 另一方面 xff0c 为了建立端到端的路径 xff0c 路由算法

热门标签