ad hoc网络的路由协议

1、无线自组织网络无线自组织网络 路由协议路由协议 2 提纲提纲 p路由协议概述 pAd hoc网络与Internet网络路由设计的区别 pAd hoc网络路由协议分类 表驱动（Table Driven）路由协议 按需驱动（On-demand Driven）路由协议 混合式（Hybrid）路由协议 p典型路由协议 DSR、AODV DSR路由仿真演示 3 应用层 传输层 网络层 数据链路层(MAC) 物理层 需要确定从起始源节点 到最终目的节点（端到 端）的有效路由 需要解决相邻节点 间(点到点)的信道 接入问题 2 3 1 4 511 6 8 9 7 1014 12 13 15 自组织网络协议栈

2、结构自组织网络协议栈结构 4 路由协议概述路由协议概述 p路由协议：通信网络中的一套将业务数据从源 节点指引到目的节点的机制。 p路由设计目标 正确性、简单性 健壮性（robustness）、稳定性 公平性、最优性 p路由协议构成： 路由生成（Path Generation） 路径选择（Path Selection） 路径维护（Path Maintenance） 5 Ad hoc网络网络与与互联网路由设计互联网路由设计的区别的区别 pAd hoc网络中节点既是终端又是路由器，参 与分组转发；因特网中终端和路由器的角色 由不同节点担任。由于应用环境和功能的差 异，二者在路由协议设计上存在诸多区别

3、： Ad hoc网络中存在单向链路。基于双向链路的传统路 由选择算法在ad hoc网络中已不再适用。 无线环境中可能存在很多“多余”链路。传统的有线 网络中，任意两个网络之间通常只会配置一个或均匀 配置少量的路由器。而无线网络中由于节点的移动性， 某时刻源节点或转发节点周围可能会密集分布多个节 点，这些节点均处于临近节点的传输范围内，容易形 成多条等效的转发链路。这些链路的代价相同，可以 认为是多余的。 6 Ad hoc网络网络与与互联网路由设计互联网路由设计的区别的区别 pAd hoc网络与Internet网络在路由协议设计上 存在的区别： 无线节点通常是能量受限的终端。无线网络中的节点 通

4、常依靠电池提供能量，因此节能很大程度上决定了 无线节点的使用寿命。传统Internet网络中的路由协议 大多需要路由器间频繁的信息交互，这对于有稳定能 量供应的有线网络而言可能无足轻重，而对于能量受 限的无线节点而言却是无法承受的。 无线环境中动态变化的网络拓扑。传统的路由协议是 针对网络拓扑结构相对稳定的有线网络而设计的，当 应用于无线网络中时，会出现大量的问题。收敛速度 是衡量路由协议性能的重要指标。由于无线网络中节 点移动频繁，需要交互更多的变化的拓扑信息，路由 协议的收敛相对较慢。 7 Ad hoc网络路由协议的分类网络路由协议的分类 p现有Ad hoc网络的路由协议根据发现路由的 驱

5、 动 方 式 的 不 同 可 分 为 表 驱 动 （ Ta b l e Driven）、按需驱动（On-demand Driven）和 混合式（Hybrid）路由协议三类。 Ad Hoc网络路由协议 混合式路由协议 DSDVWRPAODVDSRLAR 按需驱动路由协议表驱动路由协议 ZRP 8 Ad hoc网络路由协议的分类网络路由协议的分类 表驱动（Table Driven）路由协议 又称先验式路由协议，主要是沿用了传统有线网络中路 由协议的基本思想，即节点通过查询预先配置的路由 表来实现分组的转发。节点间周期性地交互各自的路 由信息，每个节点试图维护到网络中所有其他节点的 路由信息。节点在

6、检测到周围网络拓扑发生变化时， 会及时地发送路由更新，收到路由更新的节点将更新 自己的路由表。 表驱动路由协议的时延较小，但路由协议的开销较大。 由于其先验性，每个节点都必须维护路由表，而通常 网络中只有少数节点承担着数据分组的转发任务，不 会参与分组转发的节点实际上并没有维护路由表的必 要，这样就大大浪费了宝贵的无线带宽资源。 9 Ad hoc网络路由协议的分类网络路由协议的分类 按需驱动（On-demand Driven）路由协议 又称反应式路由或被动路由。节点无需实时维护整个网 络的拓扑结构信息，其路由信息是按需建立的。当节 点有数据分组需要发送时，才尝试发起路由发现过程。 通常源节点采

7、用洪泛（Flooding）的方式向邻居节点 广播路由请求消息，目的节点收到该路由请求消息时， 向源节点返回路由应答，路由应答消息中包含着从源 节点到目的节点的全路由信息。 按需路由不需要节点周期性的交互各自的路由信息，节 省了一定的带宽资源，只需要参与转发的节点维护部 分网络拓扑信息，减少了内存的占用。但是当源节点 没有到达目的节点的路由时，要实时发起路由寻找过 程，数据分组的传输有一定的延时，因而按需驱动的 路由方式不利于数据的实时传输。 10 Ad hoc网络路由协议的分类网络路由协议的分类 混合式（Hybrid）路由协议 很多具体的ad hoc网络场合中，单纯的采用按需驱动或 表驱动的路

8、由方式并不能完全解决路由问题。于是， 许多研究工作尝试结合按需驱动路由协议和表驱动路 由协议各自的优点来设计混合式路由协议。 然而，混合式路由协议的具体实现也面临着很多困难， 如具体表驱动和按需驱动路由协议的搭配方式等问题。 11 p DSR（Dynamic Source Routing ） 基于源路由方式的按需路由协议。 节点需要发送数据分组时才进行路由发现过 程。 发送节点在路由分组中包含了源源-目的节点的目的节点的 完整路由信息完整路由信息，该路由信息由网络中的若干 节点地址组成，各个节点按照该路由信息来 转发分组。 按需驱动路由协议按需驱动路由协议 12 pDSR（Dynamic So

9、urce Routing ） 节点不需要实时地维护网络的拓扑信息，那 么在节点需要发送数据时，如何获知源-目的 节点的路由？ 按需驱动路由协议按需驱动路由协议 13 p DSR（Dynamic Source Routing ） 路由发现（Route Discovery）和路由维护（Route Maintenance）两部分： 路由发现： -节点需要发送数据分组时才启动； -帮助源节点获得到达目的节点的路由。 路由维护 -在源节点给目的节点发送数据时监测当前路由的可 用情况； -当网络拓扑变化导致路由故障时，切换到另一条路 由或者重新发起路由发现过程。 按需驱动路由协议按需驱动路由协议 14 p

10、DSR（Dynamic Source Routing ） 路由发现： （1）当一个节点要发送分组给某一目的节点时，它会 首先查看自己的路由缓存中是否已有现成的路由信息 可以使用。如果存在一条到达目的节点的路由，并且 其生存期没有到期，则直接使用此路由发送分组； （2）如果路由缓存中没有通向目的节点的路由,则启动 路由发现(route Discovery)过程。路由发现过程使用洪 泛路由（flooding routing）技术。 按需驱动路由协议按需驱动路由协议 15 pDSR路由发现过程 路由发现的基本操作 （1）源节点向邻居节点广播路由请求（RREQ）报文 RREQ中包含以下信息： 源节点地

11、址； 目的节点地址； 路由记录（按顺序累积记录此路由请求报文所经过的 节点的地址）； 请求ID（由源节点自己产生的序号，同一个节点所发 送的路由请求报文中的请求标识均不同）。 一组可以唯一确定一个路由请求报文。 按需驱动路由协议按需驱动路由协议 16 pDSR路由发现过程 路由发现的基本操作 （2）中间节点收到路由请求报文后，需要进行请求报 文检测。 中间节点收到来自同一个源节点，并且请求ID相同的 路由请求报文，则直接将该报文丢弃。 按需驱动路由协议按需驱动路由协议 17 pDSR路由发现过程 路由发现的基本操作 （2）中间节点收到路由请求报文后，需要进行请求报 文检测。 中间节点收到路由请

12、求报文中的路由记录已经包含本 中间节点，则直接将该报文丢弃。 中间节点的缓存中已经有到达目的节点的路由，直接 向源节点发送路由应答报文进行应答。 按需驱动路由协议按需驱动路由协议 18 pDSR路由发现过程 路由发现的基本操作 （2）中间节点收到路由请求报文后，需要进行请求报 文检测。 若路由请求报文是未处理过的，中间节点则： -将自己的地址附在路由记录中； -将该路由请求报文作为本地广播分组发送给邻居节点。 按需驱动路由协议按需驱动路由协议 19 pDSR路由发现过程 路由发现的基本操作 （3）如果接收节点就是目的节点，这时路由记录字段 中记录的节点地址序列，就构成了从源节点到目的节 点的路

13、由信息，把此路由信息加入到路由应答报文中， 并将此报文回送给源节点。 按需驱动路由协议按需驱动路由协议 20 pDSR路由发现过程 按需驱动路由协议按需驱动路由协议 21 pDSR路由发现过程：路由应答 路由应答的基本操作 目的节点接收到路由请求后，把路由信息加入到路由应 答报文（RREP）中，并将此报文回送给源节点。 如果目的节点路由缓存中有到达发起节点的路由，此时 目的节点可以直接使用该路由回送路由应答。如果目 的节点路由缓存中没有到达发起节点的路由，此时需 要考虑节点通信链路的方向性问题。 如果源-目的是双向通信链路，此时目的节点到发起节 点的路由即为发起节点到目的节点路由的反向路由。

14、如果源-目的是单向通信链路，目的节点就需要发起到 源节点的路由发现过程，同时将路由应答报文捎带在 新的路由请求中。 源节点接收到RREP后在路由缓存中存储路由信息。 按需驱动路由协议按需驱动路由协议 22 pDSR路由发现过程：路由应答 按需驱动路由协议按需驱动路由协议 23 pDSR（Dynamic Source Routing ） 路由维护： （1）点对点证实方式，又称为逐跳证实方式。在点对 点证实方式中，相邻节点间通过数据链路层的消息或 者应用层DSR软件之间的消息证实机制，来检测路由 中各相邻节点的可达性。 （2）端到端证实方式。在这种工作机制中，结点以混 杂模式运行，当结点传送报文给

15、相邻结点时，它可以 侦听到它的相邻结点所传送的报文，并以此来判断对 方是否还在传送范围内。 按需驱动路由协议按需驱动路由协议 24 pDSR（Dynamic Source Routing ） 路由维护： 如果一个分组的发送次数已经达到最大重传限制，但节 点仍未证实其下一跳节点已经成功地接收到该分组， 那么该节点认为从自身到其下一跳节点间的链路中断， 节点将删除其路由缓存表中包含该链路的路由记录， 并向该分组的源节点返回一个路由错误（ROUTE ERROR）。 源节点收到该路由错误后，查找其路由缓存表中是否存 在能到达目的节点的其他路由，若存在这样的路由， 则源节点用此新路由来发送分组。否则，源

16、节点将启 动新一轮路由发现过程。 按需驱动路由协议按需驱动路由协议 25 pDSR（Dynamic Source Routing ） 路由维护优化： （1）分组抢修。 中间节点检测到下一跳链路已经中断时，除了发送路由 错误外，还应进行路由抢修，查找其路由缓存表中是 否存在到达分组目的节点的替代路由。若存在，则按 照该新路由进行分组的转发。在抢救一个分组时，为 该分组维护一个计数器，用于记录该分组已经被抢救 的次数，以便防止一个分组被无休止的抢救。 按需驱动路由协议按需驱动路由协议 26 pDSR（Dynamic Source Routing ） 路由维护优化： （2）路由缩短。 如下图所示，图

17、中节点D侦听到节点B转发给节点C的一 个数据分组，该分组随后将被转发给节点D和节点E。 在这种情况下，节点D将回送一个无请求路由应答给 节点A。该无请求路由应答给出一条更短的路由，由 两部分合并而成：第一部分是从源节点到被侦听分组 的发送节点为止的部分源路由；第二部分则是从回送 无请求路由应答节点开始到分组目的节点的一段缓存 路由。 按需驱动路由协议按需驱动路由协议 27 pDSR（Dynamic Source Routing ） 优点： （1）仅在需要通信的节点间维护路由，减少了路由维 护的开销； （2）采用了路由缓存技术，路由发现的过程中，会产 生多条到达目的节点的路径，能减少路由发现的代

18、价； （3）支持非对称传输信道模式。 不足： （1）采用源节点路由，每个路由报文的头部都要携带 路由信息，增加了报文长度； （2）用于路由发现的控制报文可能会涉及全网各节点， 造成较大的耗费； （3）过时或错误的缓存路由会对网络中其他节点产生 影响。“脏”缓存路由的污染传播。 按需驱动路由协议按需驱动路由协议 28 pAODV（Ad Hoc On Demand Distance Vector Routing ）按需距离矢量路由协议 按需路由，机制与DSR相仿。 通往目的节点路径上的各节点均建立和维护路由表， 路由报文头部不再需要携带完整路径，减少了报文头 部路由信息对信道的占用，提高了系统效率。 本地存储下一跳路由信息：RREQ获得反向路由信息， RREP获得正向路由信息。 路由条目中包含“目的节点序列号”，序列号越大路 由越新越有效，进行信息及时更新，避免环路。 局部连接拓扑探测：在一定时间内没有和一跳邻居通 信（任意数据/控制包），发送Hello（节点发送Hello 不增加自己的序号）。 按需驱动路由协议按需驱动路由协议 29 pAODV（Ad Hoc On Demand Distance Vector Routing ）按需距离矢量路由协议 AODV只支持双向链路路由。在路由请求消息的广播 过程中需要建立反向路由，供路由响应报文寻路，网 络要满足双向传输信道的要求； 路