DSR ( Dynamic Source Routing )路由协议

DSR 协议是一种基于源路由方式的按需路由协议。

在 DSR 协议中,当发送者发送报文时,在数据报文头部携带到达目的节点的路由信息,该路由信息由网络中的若干节点地址组成,源节点的数据报文就通过这些节点的中继转发到达目的节点。

与基于表驱动方式的路由协议不同的是, 在 DSR 协议中,节点不需要实时维护网络的拓扑信息,因此在节点需要发送数据时 ,如何能够知道到达目的节点的路由是 DSR 路由协议需要解决的核心问题。

DSR 路由协议:主要由路由发现和路由维护两部分组成。

– 路由发现过程主要用于帮助源节点获得到达目的节点的路由。

– DSR协议通过路由维护过程来监测当前路由的可用情况,当监测到路由故障时,将调用新的一轮路由发现过程。如路由中的节点由于移动、关机等原因无法保证到达目的节点时,当前的路由就不再有效了。

– 同时为了提高系统性能,在 DSR 协议中,还引入了一 系列的优化技术,如路由缓冲( Route Cache )等。 下面分别介绍这三部分内容。

1 .路由发现

=节点通过路由发现过程获得到达其他节点的路由。

源节点首先向其邻节点广播“路由请 求”( Route Request )报文。报文中包括“目的节点地址”、“路由记录”以及“请求ID” 等字段。

– 其中“路由记录”字段用于记录从源节点到目的节点路由中的中间节点地址,当路由请求报文到达目的节点时,该字段中的所有节点地址即构成了从源节点到目的节点的路由。

– “请求ID” 字段由源节点管理分配

– 中间节点维护 < 源节点地址,请求 ID> 序列对列表, < 源节点地址,请求 ID> 序列用于惟一标识一个路由请求报文,防止收到重复的路由请求。

中间节点在收到源节点的路由请求报文后 ,按照以下步骤处理报文:

– ( 1 )如果路由请求报文的 < 源节点地址,请求 ID> 存在于本节点的序列对列表中,表明此 请求报文已经收到过,节点不用处理该请求; 否则转步骤( 2 );

– ( 2 )如果节点的地址已在路由记录字段中存在,节点不用处理该请求;否则转步骤 3 ;

– ( 3 )如果请求报文的目的节点就是本节点, 则路由记录节点中的节点地址序列构成了从源节点到目的节点的路由。节点向源节点发送 “路由响应”报文,同时将该路由拷贝到“路由响应”报文中;否则转步骤( 4 );

– 4 )该节点是中间节点。将节点地址附在报文 的“路由记录”字段后,同时向邻节广播该路

通过这种方法,路由请求报文将最终到达 目的节点。

如下图所示为节点 A 到节点 D 的路由请求 过程。虚线箭头代表路由请求消息发送, 括号中的内容代表消息中的路由记录。由请求。

几个注意的问题:

(1)由于节点B已经收到节点A的路由请求,因此不再处理节点F的路由请求消息;

(2)节点D可能会同时收到节点C和E 的路由请求消息,造成消息碰撞,反而收不到正确的路由请求,因此在 Ad Hoc 网络中,广播并非完全可靠。可以采用一定的策略来避免,如节点随机延时发送,或者节点间采用证实机制等。

目的节点根据收到的源节点路由请求报文回送“路由响应”报文。目的节点在将“路由响应”报文转发到源节点时,需要考虑这样几种情况:

( 1 )目的节点有到达源节点的路由。此时目的节点可以直接使用该路由回送响应报文;

( 2 )如果目的节点没有到源节点的路由,此时需要考虑节点通信信道问题:

· 1 如果网络中所有节点间的通信信道是对称的,此时目的节点到源节点的路由即为源节点到目的节点的反向路由;

· 2 如果信道是非对称的,目的节点就需要发起到源节点的路由请求过程,同时将路由响应报文捎带在新的路由请求中。

如下图所示为 DSR 的路由响应过程。假设信道是双向信道,节点 D 根据最短路由原 则选择了路由( A-B-C-D )作为最终路由 ,将此信息通过反向路由发送至源节点 A。

2 .路由维护

传统的路由协议中通过周期性广播路由更新消息将路由发现和路由维护过程合二为一。而在 DSR 协议中,由于没有这种周期性的广播,节点必须通过路由维护过程检测路由的可用性。

按照路由维护的不同检测方法,可以将路由维护分为以下两种:

( 1 )点到点证实机制,又称为逐跳证实机制。

– 即相邻节点间通过数据链路层的消息证实或者高层应用层之间的消息证实机制,来检测路由中各邻节点的可达性。当发现节点间的传输故障,即路由不再有效时,向上级节点发送“路由差错”报文,收到路由差错报文的节点根据此信息将该路由从本节点的路由缓冲区中删除 。

( 2 )端到端证实机制。在有些应用中要 求端到端节点间的证实,通过端到端的证 实机制可以用来检测整个路由的有效性。

3 .路由缓冲技术优化策略

在 DSR 协议中,为了提高系统效率,协议中采用了路由缓冲优化策略。

– 由于无线广播信道的特点,节点可以处于“混合听”状态,即可以听到相邻节点发出的所有报文,包括路由请求、路由响应等。这些报文中携带了网络的一些路由信息,节点通过缓存这些路由信息,可以尽量减少每次发送新报文时启动的路由发现过程,以提高系统的效率 。

如下图所示,节点 A 通过发起目的节点为D的路由请求过程,获得路由 A-B-C-D , 同时节点 A 也获得了到达该路由中所有节点(如节点B、C)的路由,节点B等中间节点也获得了到达节点D的路由。

同时,中间节点在收到源节点的路由请求 时,如果本节点路由缓冲区中有到目的节点的路由,可以直接回复路由响应消息。

– 如节点 F 在发起到节点 D 的路由请求时,当报 文到达节点 B 时,节点 B 中有缓冲路由 B-C- D ,此时节点 B 可以直接回复路由响应( F-B- C-D )。这样一方面加快了路由请求的响应, 同时也减少了路由请求消息的广播。

尽管路由缓冲技术能够在一定程度上提高系统的效率,但同时一些错误或过期的路由缓冲信息(如由于某些节点的移动使得 路由失效)也会对网络带来负面影响,这 些错误的路由信息可能会影响和感染其他 节点。

对此,可以采用一定的策略来减少其影响 。

– 如为缓冲路由设定有效期,超过有效期的路由 将被认为无效,将其从缓冲区中删除。

4 . DSR 协议的优缺点 DSR 协议具有

( 1 )仅在需要通信的节点间维护路由, 减少了路由维护的代价;

( 2 )路由缓冲技术可进一步减少路由发现的代价;

( 3 )由于采用了路由缓冲技术,因此在一次路由的发现过程中,会产生多种到达目的节点的路径;

(4 )支持非对称传输信道模式。

DSR 协议存在一些问题和不足:

( 1 )由于采用源节点路由,每个数据报文的头部都要携带路由信息,增加了报文长度;

( 2 )用于路由发现的控制报文可能会波及全网各节点,造成一定的耗费;

( 3 )“路由响应风暴”( Route Reply Storm )问题。由于采用路由缓冲技术,中间节点根据自己的缓冲路由,对路由请求直接应答,源节点会同时收到多个路由响 应,造成路由响应信息之间的竞争;

( 4 )“错误”缓冲路由对其他节点的影响。如果中间节点的路由缓冲记录已经过时,当该节点根据缓冲路由回复路由请求时,其他监听到此“错误”路由的节点会更改自己的缓冲路由记录,造成“错误”缓冲路由的污染传播。