AD-HOC自组网路由协议

中间节点维护动态路由表项
本地HELLO消息：用于决定本地连接

可以减少路由请求的响应时间 在必要时，可以触发更新
解决信息新鲜度问题 节点顺序号 广播IDAODV（1）

路由条目和序列号绑定


每个节点维护两个计数器

15
AODV（3）- 路由请求

当节点N想和节点M通信，但是没有到节点M的路由时，节点N 会发起对M的路由请求 节点N广播一个RREQ(Route Request)的报文给它的邻居 顺序号
LSDB A-B A-C
LSDB A-B
LSDB B-D A-C B-C
LSDB B-D
LSDB A-B A-C B-C C-D
B-C C-D
A
C
D
A
C
D
B
LSDB A-B B-C
B
LSDB
LSA from D
A-B B-C A-C C-D
hello
LSA from C
10
AD-HOC路由 VS. 传统路由

应用场景
军事，比如一个小分队偏远地区/无人区/敌区实施任务 救灾，通信基础设施被破坏，营救团队之间的通信 传感器网络，没有通信基础设施 智慧家庭

BTS Backhau BSC l
Network Core MSC Netwo rk 3
AD-HOC网络简介（2）- 标准化情况

Wifi MESH over 802.11 (802.11s)
OLSR：优化的链路状态路由协议
Performance： AODV vs OLSR
AD-HOC网络简介（1）- 为啥需要AD-HOC

Ad hoc: 拉丁语，意为“for this purpose only”， 也即是某种特殊用途的网络。

核心要点：不依赖于已有的基础架构，比如wifi AP或者 基站，由通信实体自己组网通信
•产生数据报文 •接收数据报文 •低功耗、电池供电设备
6
ZIGBEE - 特点
低功耗
5号电池>半年
低成本
< $2 per chip
低速率
<250Kbps
近距离
<100m p2p
高容量
Flat:254; Hier:65000
高安全
AES128
ISM频段
2.4G(global); 915M(USA) 868M(EU)

14
AODV（2）- 基本概念

纯的按需路由协议
一个网络节点不会主动发起路由发现或者维护，除非它需要知 道某个路由，或者它作为中间节点提供服务 不在有效路径上的节点不维护路由信息，不参与路由表信息交 换



使用广播路由发现机制 使用报文每跳路由（hop-by-hop routing）



每个节点根据整个网络每个节点的邻接信息构造网图，使用最短路 径优先算法计算路由

消息类型 Hello: 邻居发现，仅在链路层发送，TTL=1 Router LSA(Link State Advertisement): 节点邻接消息，在整个 域（Area）广播
LSDB A-B B-C C-D
22
OLSR（1）
Optimized Link State Routing protocol


RFC3626，IETF实验性文档
参考

Rfc3626.txt:

https:///link?url=4CDgV9178IFcLgFmGiJO 7qovkDSPk58O2ywEZjhFo7aWLEwceQvR5YcNiTfZJHcb&w d=&eqid=def805c200003ea700000002584e8aba https:///wg/manet/draft-ietf-manetolsrv2/draft-ietf-manet-olsrv2-03-from-02.wdiff.html
Since 2001 最新3.0标准，2016


IEEE802.15.4个人局域网(PAN)无线标 准

物理层和链路层标准

ZigBee-PRO NWK 网络层
定义了基本要求。具体路由协议没有定 义。 常见路由协议


AODVjr Cluster-Tree: 分级路由，适合静态网络，链 路状态路由类型
1
RREQ
4
6 7

节点1发送一个RREQ给它的邻居

2
3
5
源地址=1 目的地址=7 广播ID=广播ID+1 源顺序号=源顺序号+1 宿顺序号=上次收到节点7的宿顺 序号
18
AODV（6）- 路由请求示例

1 4 6 7 2 3 5
节点2和4确认这是一个新的 RREQ，


节点2和节点4转发RREQ

检查是否是新的RREP，或者是需要发送 的RREP，

节点1收到RREP，计算路由

本例中，是新的RREP，使用反向路由，回 送给节点1 RREP中的跳数加1
等路由计算完毕后，想发送的报文才能 开始发送
21
AODV（9）- 路由维护

路由改变可以通过下面方式侦测到：

收不到HELLO消息 物理层错误指示

源顺序号是“新”的，刷新到 节点1的反向路由
为节点1更新顺序号 增加RREQ的跳数
1
4
6 7

节点6收到RREQ

2
3
5 RREQ RREP

节点3、5也会转发RREQ，最 终发现是冗余的
19
如果RREQ里面的宿顺序号小于 等于节点6记录的节点7的顺序 号，回送RREP
AODV（7）- 路由响应

按需被动式路由


混合式

13
AODV（1）

Ad Hoc On-demand Distance Vector routing protocol

RFC3561，IETF实验性文档

参考
RFC3561 https:///link?url=c2Hu5dnwZ8fXJ84d nZ2EUlCcotXofNPBsO7FCvUOQHQ3DwJ3XIOUXT_y 0YfXIJmIalcCcTska9JBPEP1rKR9_&wd=&eqid=8907b86700003b83000000 04584f94f2

路由表：节点依据路由表发送数据报文

<目的节点/网络，下一跳，接口，属性>
路由协议：终极目标就是构造节点上的路由表
8
传统路由算法（2）- DISTANCE VECTOR路由 算法

代表协议：RIP（Routing Information Protocol），IGRP（Interior Gateway Routing Protocol） 每个（物理）链路的“距离”是重要衡量指标，DV的一个目标是使得 路径的距离最短 一个简单的计算方法是：一个link，距离就是1，也可以看成1跳 DV路由表 <目的节点/网络，下一跳，接口，跳数> 核心概念：路由表信息仅通告邻居
Ad-Hoc路由 节点移动性 信号干扰 快速移动 强，无线电磁环境复 杂 传统路由 基本静止 弱，有线噪声容易 屏蔽
链路对称性
接收两端接收能力、 路径衰减状况等复杂 因素
弱，移动设备电源消 耗限制
基本是对称链路
节点计算能力
强
轻量级开 销
路由快速 收敛
11
AD-HOC 路由简介（1）
路由计算时机
主动式（Proactive）或者表驱动（Table-Driven），维 护路由表 被动式（Reactive）或按需（On-demand） ，在需要 时决定路由

20
AODV（8）- 路由响应示例
接slide14 节点6知道到节点7的路径，因此构造 RREP，发送给节点4。RREP内容为：
Dest 7 Next 4
1
Hops 3
4
RREP 6 7
2
3
5

节点4收到RREP


源地址=1 宿地址=7 宿顺序号=max（自己记录的节点7的顺 序号，RREQ中的宿顺序号） 跳数=1
源顺序号：指明反向路由的新鲜度 宿顺序号：指明正向路由的新鲜度



每个邻居收到RREQ：
要么使用RREP返回给节点N， 要么把RREQ转发给它的邻居


<源地址，广播ID>唯一决定RREQ
每次发送RREQ，广播ID加1 接收者能够判定和丢弃重复RREQ

16
AODV（4）- 路由请求


网络结构

扁平结构

AODV，OLSR
比如，可以在一个簇或者域里面采用主动式路由，而在簇头之 间采用被动式路由
层级结构

12
AD-HOC 路由简介（2）- 路由分类

扁平主动式路由

Link state Fish-Eye Routing, GSR, OLSR Table driven: Destination-Sequenced Distance Vector (DSDV), WRP) Ad hoc On-demand Distant Vector (AODV) Dynamic Source Routing (DSR) Zone Routing ZRP, SHARP (proactive near, reactive long distance) Safari (reactive near, proactive long distance)
短时延
Wakeup time<15ms
7
传统路由算法（1）

路由需要解决的问题

路由就是找路：能够将数据报文，从源节点发送到目的节点， 中间需要跨越多个节点或者局域网

链路层协议解决点到点（物理链路）的通信

一定需要路由协议吗？


静态路由：路是可以“永久性”建好的，比如 ATM/PPP/OTN/MPLS-TP等等 动态路由：动态的建设
B
Dest Next Met C C 1 A A 1
B
Dest Next Met C C 1 A A 1 D C 2
9
传统路由算法（3）- LINK STATE路由算法

代表协议：OSPF（Open Shortest Path First），ISIS （ Intermediate system to intermediate system ） 核心概念 每个节点都对外发布自己的邻接信息
5
ZIGBEE– 网络层节点分类
协调器(ZigBee Coordinator)
•每个ZigBee网络一个 •初始化网络信息：网络标识符， 信道等 •安全认证（集中控制） •也是路由器和终端节点
路由器（ZigBee Router）
•路由数据报文 •Always-On •也是终端节点
终端节点(ZigBee EndPoint)

二层的Ad-Hoc路由
BT MESH （BT 6.0?），还没有成为标准 Zigbee over 802.15.4 IETF MANET over MAC (802.11，802.15.4)

重点在路由协议 基于IP

4
ZIGBEE - 简介

目标：可靠，高性价比，低功耗 ZigBee联盟和ZigBee协议

侦测到路由改变的上游节点构造RERR（Route ERRor）

新的宿序列号和无穷大跳数
源（或者路由上的其他节点）可以通过构造新的RREQ，试图 重新构造到宿节点的路由
RERR 1 4 6 7 2 3 5 7
• • •
假定节点7移动，导致link<6,7>断开 6发现这个断开，发起RERR到节点1，因 为它知道节点1请求过这个路由 节点1收到RERR，可以再发起到节点7的 RREQ
如果收到RREQ的节点自己有到宿的路径，或者它本身就 是宿，那么它构造单播RREP，回送给发给它RREQ的邻 居 中间节点使用反向路径回传RREP，直到源节点

中间节点可能多次收到RREP
第一个RREP无条件沿反向路径回传 后续的RREP丢弃，除非宿顺序号更大，或者宿序列号相同，但是跳数 更小

如果一个节点无法响应RREQ（也就是无法回送 RREP）
把RREQ的跳数加1 节点保存相关信息，构造一个反向路径

转发RREQ的邻居 宿IP地址 源IP地址 广播ID 源节点顺序号 路由老化时间

17
AODV（5）- 路由请求示例
4
1
6 7
2
3
5
场景和假设 节点1需要发送数据报文给节点7 假定节点6知道一个到7的路径 假定其他节点都不知道到7的路径
Dest Next Met B B 1 A A 1 D D 1 Dest Next Met B B 1 A A 1 D D 1



Dest Next Met B B 1 C C 1
A
C
D
Dห้องสมุดไป่ตู้st Next Met C C 1
Dest Next Met B B 1 C C 1 D C 2
A
C
D
Dest Next Met C C 1 A C 2 B C 2
AD-HOC自组网路由协议介绍 AD-HAD-HOC自组网路由协议介绍 路由协议介绍 AD-HOC自组网路由协议介绍
2016.12.12 wangdeqiang1234@
内容
Ad-hoc网络简介 ZigBee简介 传统路由算法 Ad-hoc路由 vs. 传统路由 AODV：按需距离向量路由协议