AD-HOC自组网路由协议
14
AODV(2)- 基本概念
纯的按需路由协议
一个网络节点不会主动发起路由发现或者维护,除非它需要知 道某个路由,或者它作为中间节点提供服务 不在有效路径上的节点不维护路由信息,不参与路由表信息交 换
使用广播路由发现机制 使用报文每跳路由(hop-by-hop routing)
OLSR:优化的链路状态路由协议
Performance: AODV vs OLSR
AD-HOC网络简介(1)- 为啥需要AD-HOC
Ad hoc: 拉丁语,意为“for this purpose only”, 也即是某种特殊用途的网络。
核心要点:不依赖于已有的基础架构,比如wifi AP或者 基站,由通信实体自己组网通信
侦测到路由改变的上游节点构造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
检查是否是新的RREP,或者是需要发送 的RREP,
节点1收到RREP,计算路由
本例中,是新的RREP,使用反向路由,回 送给节点1 RREP中的跳数加1
等路由计算完毕后,想发送的报文才能 开始发送
21
AODV(9)- 路由维护
路由改变可以通过下面方式侦测到:
收不到HELLO消息 物理层错误指示
Ad-Hoc路由 节点移动性 信号干扰 快速移动 强,无线电磁环境复 杂 传统路由 基本静止 弱,有线噪声容易 屏蔽
链路对称性
接收两端接收能力、 路径衰减状况等复杂 因素
弱,移动设备电源消 耗限制
基本是对称链路
节点计算能力
强
轻量级开 销
路由快速 收敛
11
AD-HOC 路由简介(1)
路由计算时机
主动式(Proactive)或者表驱动(Table-Driven),维 护路由表 被动式(Reactive)或按需(On-demand) ,在需要 时决定路由
AD-HOC自组网路由协议介绍 AD-HAD-HOC自组网路由协议介绍 路由协议介绍 AD-HOC自组网路由协议介绍
2016.12.12 wangdeqiang1234@163.com
内容
Ad-hoc网络简介 ZigBee简介 传统路由算法 Ad-hoc路由 vs. 传统路由 AODV:按需距离向量路由协议
二层的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协议
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
如果一个节点无法响应RREQ(也就是无法回送 RREP)
把RREQ的跳数加1 节点保存相关信息,构造一个反向路径
转发RREQ的邻居 宿IP地址 源IP地址 广播ID 源节点顺序号 路由老化时间
17
AODV(5)- 路由请求示例
4
1
6 7
2
3
5
场景和假设 节点1需要发送数据报文给节点7 假定节点6知道一个到7的路径 假定其他节点都不知道到7的路径
网络结构
扁平结构
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)
5
ZIGBEE– 网络层节点分类
协调器(ZigBee Coordinator)
•每个ZigBee网络一个 •初始化网络信息:网络标识符, 信道等 •安全认证(集中控制) •也是路由器和终端节点
路由器(ZigBee Router)
•路由数据报文 •Always-On •也是终端节点
终端节点(ZigBee EndPoint)
中间节点维护动态路由表项
本地HELLO消息:用于决定本地连接
可以减少路由请求的响应时间 在必要时,可以触发更新
解决信息新鲜度问题 节点顺序号 广播IDAODV(1)
路由条目和序列号绑定
每个节点维护两个计数器
15
AODV(3)- 路由请求
当节点N想和节点M通信,但是没有到节点M的路由时,节点N 会发起对M的路由请求 节点N广播一个RREQ(Route Request)的报文给它的邻居 顺序号
源顺序号:指明反向路由的新鲜度 宿顺序号:指明正向路由的新鲜度
每个邻居收到RREQ:
要么使用RREP返回给节点N, 要么把RREQ转发给它的邻居
<源地址,广播ID>唯一决定RREQ
每次发送RREQ,广播ID加1 接收者能够判定和丢弃重复RREQ
16
AODV(4)- 路由请求
如果收到RREQ的节点自己有到宿的路径,或者它本身就 是宿,那么它构造单播RREP,回送给发给它RREQ的邻 居 中间节点使用反向路径回传RREP,直到源节点
中间节点可能多次收到RREP
第一个RREP无条件沿反向路径回传 后续的RREP丢弃,除非宿顺序号更大,或者宿序列号相同,但是跳数 更小
Since 2001 最新3.0标准,2016
IEEE802.15.4个人局域网(PAN)无线标 准
物理层和链路层标准
ZigBee-PRO NWK 网络层
定义了基本要求。具体路由协议没有定 义。 常见路由协议
AODVjr Cluster-Tree: 分级路由,适合静态网络,链 路状态路由类型
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. 传统路由
短时延
Wakeup time<15ms
7
传统路由算法(1)
路由需要解决的问题
路由就是找路:能够将数据报文,从源节点发送到目的节点, 中间需要跨越多个节点或者局域网
链路层协议解决点到点(物理链路)的通信
一定需要路由协议吗?
静态路由:路是可以“永久性”建好的,比如 ATM/PPP/OTN/MPLS-TP等等 动态路由:动态的建设
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
Dest 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
•产生数据报文 •接收数据报文 •低功耗、电池供电设备
6
ZIGBEE - 特点
低功耗
5号电池>半年
低成本
< $2 per chip
低速率
<250Kbps
近距离
<100m p2p
高容量
Flat:254; Hier:65000
高安全
AES128
ISM频段
2.4G(global); 915M(USA) 868M(EU)
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
路由表:节点依据路由表发送数据报文
<目的节点/网络,下一跳,接口,属性>
路由协议:终极目标就是构造节点上的路由表
8
传统路由算法(2)- DISTANCE VECTOR路由 算法
代表协议:RIP(Routing Information Protocol),IGRP(Interior Gateway Routing Protocol) 每个(物理)链路的“距离”是重要衡量指标,DV的一个目标是使得 路径的距离最短 一个简单的计算方法是:一个link,距离就是1,也可以看成1跳 DV路由表 <目的节点/网络,下一跳,接口,跳数> 核心概念:路由表信息仅通告邻居
源顺序号是“新”的,刷新到 节点1的反向路由
为节点1更新顺序号 增加RREQ的跳数
1
4
6 7
节点6收到RREQ
2
3
5 RREQ RREP
节点3、5也会转发RREQ,最 终发现是冗余的
19
如果RREQ里面的宿顺序号小于 等于节点6记录的节点7的顺序 号,回送RREP
AODVபைடு நூலகம்7)- 路由响应
每个节点根据整个网络每个节点的邻接信息构造网图,使用最短路 径优先算法计算路由
消息类型 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://www.baidu.com/link?url=4CDgV9178IFcLgFmGiJO 7qovkDSPk58O2ywEZjhFo7aWLEwceQvR5YcNiTfZJHcb&w d=&eqid=def805c200003ea700000002584e8aba https://tools.ietf.org/wg/manet/draft-ietf-manetolsrv2/draft-ietf-manet-olsrv2-03-from-02.wdiff.html
应用场景
军事,比如一个小分队偏远地区/无人区/敌区实施任务 救灾,通信基础设施被破坏,营救团队之间的通信 传感器网络,没有通信基础设施 智慧家庭
BTS Backhau BSC l
Network Core MSC Netwo rk 3
AD-HOC网络简介(2)- 标准化情况
Wifi MESH over 802.11 (802.11s)
按需被动式路由
混合式
13
AODV(1)
Ad Hoc On-demand Distance Vector routing protocol
RFC3561,IETF实验性文档
参考
RFC3561 https://www.baidu.com/link?url=c2Hu5dnwZ8fXJ84d nZ2EUlCcotXofNPBsO7FCvUOQHQ3DwJ3XIOUXT_y 0YfXIJmIalcCcTska9JBPEP1rKR9_&wd=&eqid=8907b86700003b83000000 04584f94f2
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 ) 核心概念 每个节点都对外发布自己的邻接信息