《adhoc网络的路由协议剖析》由会员分享，可在线阅读，更多相关《adhoc网络的路由协议剖析（31页珍藏版）》请在金锄头文库上搜索。
1、无线自组织网络 路由协议,2,提纲,路由协议概述 Ad hoc网络与Internet网络路由设计的区别 Ad hoc网络路由协议分类 表驱动（Table Driven）路由协议 按需驱动（On-demand Driven）路由协议 混合式（Hybrid）路由协议 典型路由协议 DSR、AODV DSR路由仿真演示,3,需要确定从起始源节点到最终目的节点（端到端）的有效路由,需要解决相邻节点间(点到点)的信道接入问题,2,3,1,4,5,11,6,8,9,7,10,14,12,13,15,自组织网络协议栈结构,4,路由协议概述,路由协议：通信网络中的一套将业务数据从源节点指引到目的节点的机制。
2、路由设计目标 正确性、简单性 健壮性（robustness）、稳定性 公平性、最优性 路由协议构成： 路由生成（Path Generation） 路径选择（Path Selection） 路径维护（Path Maintenance）,5,Ad hoc网络与互联网路由设计的区别,Ad hoc网络中节点既是终端又是路由器，参与分组转发；因特网中终端和路由器的角色由不同节点担任。由于应用环境和功能的差异，二者在路由协议设计上存在诸多区别： Ad hoc网络中存在单向链路。基于双向链路的传统路由选择算法在ad hoc网络中已不再适用。 无线环境中可能存在很多“多余”链路。传统的有线网络中，任意两个网络
3、之间通常只会配置一个或均匀配置少量的路由器。而无线网络中由于节点的移动性，某时刻源节点或转发节点周围可能会密集分布多个节点，这些节点均处于临近节点的传输范围内，容易形成多条等效的转发链路。这些链路的代价相同，可以认为是多余的。,6,Ad hoc网络与互联网路由设计的区别,Ad hoc网络与Internet网络在路由协议设计上存在的区别： 无线节点通常是能量受限的终端。无线网络中的节点通常依靠电池提供能量，因此节能很大程度上决定了无线节点的使用寿命。传统Internet网络中的路由协议大多需要路由器间频繁的信息交互，这对于有稳定能量供应的有线网络而言可能无足轻重，而对于能量受限的无线节点而言却是
4、无法承受的。 无线环境中动态变化的网络拓扑。传统的路由协议是针对网络拓扑结构相对稳定的有线网络而设计的，当应用于无线网络中时，会出现大量的问题。收敛速度是衡量路由协议性能的重要指标。由于无线网络中节点移动频繁，需要交互更多的变化的拓扑信息，路由协议的收敛相对较慢。,7,Ad hoc网络路由协议的分类,现有Ad hoc网络的路由协议根据发现路由的驱动方式的不同可分为表驱动（Table Driven）、按需驱动（On-demand Driven）和混合式（Hybrid）路由协议三类。,8,Ad hoc网络路由协议的分类,表驱动（Table Driven）路由协议 又称先验式路由协议，主要是沿用了传
5、统有线网络中路由协议的基本思想，即节点通过查询预先配置的路由表来实现分组的转发。节点间周期性地交互各自的路由信息，每个节点试图维护到网络中所有其他节点的路由信息。节点在检测到周围网络拓扑发生变化时，会及时地发送路由更新，收到路由更新的节点将更新自己的路由表。 表驱动路由协议的时延较小，但路由协议的开销较大。由于其先验性，每个节点都必须维护路由表，而通常网络中只有少数节点承担着数据分组的转发任务，不会参与分组转发的节点实际上并没有维护路由表的必要，这样就大大浪费了宝贵的无线带宽资源。,9,Ad hoc网络路由协议的分类,按需驱动（On-demand Driven）路由协议 又称反应式路由或被动路
6、由。节点无需实时维护整个网络的拓扑结构信息，其路由信息是按需建立的。当节点有数据分组需要发送时，才尝试发起路由发现过程。通常源节点采用洪泛（Flooding）的方式向邻居节点广播路由请求消息，目的节点收到该路由请求消息时，向源节点返回路由应答，路由应答消息中包含着从源节点到目的节点的全路由信息。 按需路由不需要节点周期性的交互各自的路由信息，节省了一定的带宽资源，只需要参与转发的节点维护部分网络拓扑信息，减少了内存的占用。但是当源节点没有到达目的节点的路由时，要实时发起路由寻找过程，数据分组的传输有一定的延时，因而按需驱动的路由方式不利于数据的实时传输。,10,Ad hoc网络路由协议的分类,
7、混合式（Hybrid）路由协议 很多具体的ad hoc网络场合中，单纯的采用按需驱动或表驱动的路由方式并不能完全解决路由问题。于是，许多研究工作尝试结合按需驱动路由协议和表驱动路由协议各自的优点来设计混合式路由协议。 然而，混合式路由协议的具体实现也面临着很多困难，如具体表驱动和按需驱动路由协议的搭配方式等问题。,11,DSR（Dynamic Source Routing ） 基于源路由方式的按需路由协议。 节点需要发送数据分组时才进行路由发现过程。 发送节点在路由分组中包含了源-目的节点的完整路由信息，该路由信息由网络中的若干节点地址组成，各个节点按照该路由信息来转发分组。,按需驱动路由协议
8、,12,DSR（Dynamic Source Routing ） 节点不需要实时地维护网络的拓扑信息，那么在节点需要发送数据时，如何获知源-目的节点的路由？,按需驱动路由协议,13,DSR（Dynamic Source Routing ） 路由发现（Route Discovery）和路由维护（Route Maintenance）两部分： 路由发现： -节点需要发送数据分组时才启动； -帮助源节点获得到达目的节点的路由。 路由维护 -在源节点给目的节点发送数据时监测当前路由的可用情况； -当网络拓扑变化导致路由故障时，切换到另一条路由或者重新发起路由发现过程。,按需驱动路由协议,14,DSR（D
9、ynamic Source Routing ） 路由发现： （1）当一个节点要发送分组给某一目的节点时，它会首先查看自己的路由缓存中是否已有现成的路由信息可以使用。如果存在一条到达目的节点的路由，并且其生存期没有到期，则直接使用此路由发送分组； （2）如果路由缓存中没有通向目的节点的路由,则启动路由发现(route Discovery)过程。路由发现过程使用洪泛路由（flooding routing）技术。,按需驱动路由协议,15,DSR路由发现过程 路由发现的基本操作 （1）源节点向邻居节点广播路由请求（RREQ）报文 RREQ中包含以下信息： 源节点地址； 目的节点地址； 路由记录（按顺序
10、累积记录此路由请求报文所经过的节点的地址）； 请求ID（由源节点自己产生的序号，同一个节点所发送的路由请求报文中的请求标识均不同）。 一组可以唯一确定一个路由请求报文。,按需驱动路由协议,16,DSR路由发现过程 路由发现的基本操作 （2）中间节点收到路由请求报文后，需要进行请求报文检测。 中间节点收到来自同一个源节点，并且请求ID相同的路由请求报文，则直接将该报文丢弃。,按需驱动路由协议,17,DSR路由发现过程 路由发现的基本操作 （2）中间节点收到路由请求报文后，需要进行请求报文检测。 中间节点收到路由请求报文中的路由记录已经包含本中间节点，则直接将该报文丢弃。 中间节点的缓存中已经有到
11、达目的节点的路由，直接向源节点发送路由应答报文进行应答。,按需驱动路由协议,18,DSR路由发现过程 路由发现的基本操作 （2）中间节点收到路由请求报文后，需要进行请求报文检测。 若路由请求报文是未处理过的，中间节点则： -将自己的地址附在路由记录中； -将该路由请求报文作为本地广播分组发送给邻居节点。,按需驱动路由协议,19,DSR路由发现过程 路由发现的基本操作 （3）如果接收节点就是目的节点，这时路由记录字段中记录的节点地址序列，就构成了从源节点到目的节点的路由信息，把此路由信息加入到路由应答报文中，并将此报文回送给源节点。,按需驱动路由协议,20,DSR路由发现过程,按需驱动路由协议,
12、21,DSR路由发现过程：路由应答 路由应答的基本操作 目的节点接收到路由请求后，把路由信息加入到路由应答报文（RREP）中，并将此报文回送给源节点。 如果目的节点路由缓存中有到达发起节点的路由，此时目的节点可以直接使用该路由回送路由应答。如果目的节点路由缓存中没有到达发起节点的路由，此时需要考虑节点通信链路的方向性问题。 如果源-目的是双向通信链路，此时目的节点到发起节点的路由即为发起节点到目的节点路由的反向路由。 如果源-目的是单向通信链路，目的节点就需要发起到源节点的路由发现过程，同时将路由应答报文捎带在新的路由请求中。 源节点接收到RREP后在路由缓存中存储路由信息。,按需驱动路由协议
13、,22,DSR路由发现过程：路由应答,按需驱动路由协议,23,DSR（Dynamic Source Routing ） 路由维护： （1）点对点证实方式，又称为逐跳证实方式。在点对点证实方式中，相邻节点间通过数据链路层的消息或者应用层DSR软件之间的消息证实机制，来检测路由中各相邻节点的可达性。 （2）端到端证实方式。在这种工作机制中，结点以混杂模式运行，当结点传送报文给相邻结点时，它可以侦听到它的相邻结点所传送的报文，并以此来判断对方是否还在传送范围内。,按需驱动路由协议,24,DSR（Dynamic Source Routing ） 路由维护： 如果一个分组的发送次数已经达到最大重传限制，
14、但节点仍未证实其下一跳节点已经成功地接收到该分组，那么该节点认为从自身到其下一跳节点间的链路中断，节点将删除其路由缓存表中包含该链路的路由记录，并向该分组的源节点返回一个路由错误（ROUTE ERROR）。 源节点收到该路由错误后，查找其路由缓存表中是否存在能到达目的节点的其他路由，若存在这样的路由，则源节点用此新路由来发送分组。否则，源节点将启动新一轮路由发现过程。,按需驱动路由协议,25,DSR（Dynamic Source Routing ） 路由维护优化： （1）分组抢修。 中间节点检测到下一跳链路已经中断时，除了发送路由错误外，还应进行路由抢修，查找其路由缓存表中是否存在到达分组目的
15、节点的替代路由。若存在，则按照该新路由进行分组的转发。在抢救一个分组时，为该分组维护一个计数器，用于记录该分组已经被抢救的次数，以便防止一个分组被无休止的抢救。,按需驱动路由协议,26,DSR（Dynamic Source Routing ） 路由维护优化： （2）路由缩短。 如下图所示，图中节点D侦听到节点B转发给节点C的一个数据分组，该分组随后将被转发给节点D和节点E。在这种情况下，节点D将回送一个无请求路由应答给节点A。该无请求路由应答给出一条更短的路由，由两部分合并而成：第一部分是从源节点到被侦听分组的发送节点为止的部分源路由；第二部分则是从回送无请求路由应答节点开始到分组目的节点的一
16、段缓存路由。,按需驱动路由协议,27,DSR（Dynamic Source Routing ） 优点： （1）仅在需要通信的节点间维护路由，减少了路由维护的开销； （2）采用了路由缓存技术，路由发现的过程中，会产生多条到达目的节点的路径，能减少路由发现的代价； （3）支持非对称传输信道模式。 不足： （1）采用源节点路由，每个路由报文的头部都要携带路由信息，增加了报文长度； （2）用于路由发现的控制报文可能会涉及全网各节点，造成较大的耗费； （3）过时或错误的缓存路由会对网络中其他节点产生影响。“脏”缓存路由的污染传播。,按需驱动路由协议,28,AODV（Ad Hoc On Demand Distance Vector Routing ）按需距离矢量路由协议 按需路由，机制与DSR相仿。 通往目的节点路径上的各节点均建立和维护路由表，路由报文头部不再需要携带完整路径，减少了报文头部路由信息对信道的占用，提高了系统效率。 本地存储下
