改进的移动自组网DSR协议路径缓存策略

1、高级网络结课论文改进的移动自组网DSR协议路径缓存策略摘 要：动态源路由协议在Ad Hoc网络拓扑结构变化频繁时，缓存中的路由得不到及时更新会经常失效，从而导致网络性能下降，本文对DSR(Dynamic Source Routing)路由协议的缓存管理进行了研究。基于AODV协议局部连接性管理机制提出了一种带错误路由主动发现机制的改进DSR协议，该协议可以提高缓存中路由信息的准确率，较好的适应了Ad Hoc网络动态的网络拓扑结构变化。仿真结果表明，该方法可以有效提高分组投递率，同时降低路由开销及传输延迟。关键字：移动自组网络；DSR；缓存管理；局部连接性管理；NS2；Optimized Cac

2、hing Strategies in DSR Routing Protocol for Wireless Ad Hoc NetworksAbstract：The route cache of dynamic source routing protocol is often failed because of not timely updates, when the Ad Hoc network topology changes frequently, which leads to network performance degradation. This paper has studied s

3、omething about the cache management in DSR routing protocols, and proposes an improvement DSR protocol with initiative discovery of misrouted mechanism based on the local connectivity management mechanism of AODV protocol. The improved protocol can improve the accuracy of the cache routing informati

4、on, and better adapted to the network topology changes dynamically. The simulation results show that this method can effectively improve the packet delivery ratio, and reducing the routing overhead and transmission delay at the same time.Keyword: mobile ad hoc networks, DSR, caching strategies, loca

5、l connectivity manage mechanism, NS21 引言Ad Hoc网络是一种无中心自组织的网络，具有无中心自组织性、多跳性和对等性，网络拓扑动态变化等特点，广泛应用在军事、灾难救助、偏远山区作业等特殊场合1。Ad Hoc网络的拓扑结构是动态变化的，主机之间通信均采用无线传输技术，中间的每个结点既是一个移动的主机又是一个路由器2，这就使得Ad Hoc网络的路由协议有别于传统的路由协议。目前已有多种针对Ad Hoc网络的路由协议，他们都有着自己的特点，适用于不同的应用环境。DSR路由协议2是一种基于源路由方式的按需路由协议，在DSR协议中，每一个分组的分组头中包含整条路由

6、的信息，其优点是中间结点不需要维持当前的路由信息，分组自己带有路由信息；再加上按需路由的特性，就避免了周期性的路由广播和邻结点的检测。DSR路由协议为了提高性能加入了路由缓存技术，然而动态变化的网络拓扑结构，使得缓存中的路由信息经常失效，这就降低了数据传输的成功率，并增加了传输延时为了提高缓存的准确率，本文基于AODV协议局部连接性管理机制提出了一种带错误路由主动发现机制的DSR，从而减少失效路由对整个网络的影响，提高DSR路由的性能。2 动态源路由协议DSR协议是一种基于源路由的按需路由协议，设计DSR的目的在于创建开销非常低同时又能快速响应网络变化的路由协议，以高度反应式的服务确保数据分组

7、在节点移动或者其他网络条件变化的条件下仍然能够正确地递交。DSR主要包括路由建立和路由维护两个过程34，下面对其路由机制进行详细分析。2.1 DSR协议的运行机制2.1.1 DSR协议的路由发现机制（1）产生路由请求当源节点需要与某目的节点进行通信时，它首先在本节点维护的路由缓存中查找是否有到达该目的节点的路由。若路由缓存中已包含了到达该目的节点的有效路由，则立即使用此路由发送数据分组，否则它将向所有邻居广播RREQ（Route Request）分组，以启动一个路由发现过程来找到一条到达该目的节点的可用路由。（2）节点处理路由请求如果接收RREQ的节点是该路由请求的目的节点，则向发起RREQ的

8、源节点返回RREP分组。收到RREQ的节点检查自己是否已经包含在RREQ携带的源路由节点列表中，如果是则将RREQ分组丢弃。如果协议要求使用双向链路，节点要检查前一节点是否在自己的通信范围内，如果不在则丢弃该RREQ包；如果不确定则向前一节点发送一TTL值为“1”的RREQ分组，如果前一节点回复RREP，则表示两节点之间是双向链路，继续处理RREQ分组，否则将RREQ分组丢弃。接收RREQ的节点在本地缓存中查看有无与RREQ请求路由对相对应的入口，如有则将现在收到的RREQ分组丢弃。如果接受RREQ的节点的本地缓存中没有此RREQ对应的表项，则按以下步骤处理该RREQ请求分组：将节点自己的IP

9、地址追加到RREQ分组的源路由节点列表中；为修改后的RREQ分组在节点的路由请求表中创建一入口；将新改好的RREQ拷贝广播发送出去。（3）中间节点回复RREP分组中间节点将从自己路由缓存中得到的路径追加到RREQ分组头中的源路由地址列表中，这样就得到要发给RREQ源节点的完整路由，然后将得到的源路由封装在RREP包中发送给发起RREQ的源节点。中间节点发送完路由缓存回复后，不再继续广播RREQ分组，直接将RREQ分组丢弃。（4）处理并转发路由回复目的节点收到RREQ分组得到完整的源节点到目的节点的路由后，将此路由封装在RREP分组中，然后发送给源节点。RREP分组可以封装成一个单独的IP分组传

10、递给源节点，或封装在其他有数据要传输给源节点的IP分组中被捎带回源节点。目的节点将自己的IP地址追加到RREQ携带的节点的IP地址列表中，将得到的IP地址列表作为返回给源节点的完整路由封装在RREP分组中。RREP数据分组的源IP地址设为发送RREP分组的节点的IP地址，目的IP地址设为发起RREQ的源节点的IP地址。如果使用的底层MAC协议支持双向路由，RREP数据分组可沿RREP选项中携带的源路由的逆向路由依次传输，否则目的节点为此RREP选项发起新的路由发现过程，且要将RREP选项封装在新产生的RREQ数据分组中以防止出现路由发现过程的反复进行。2.1.2 DSR协议的路由维护机制路由维

11、护可以在节点通信过程中及时发现节点所用路径出现的断链以检测路由的可用性，并对其进行相应的补救措施。出现断链主要是由于无线自组网的拓扑结构发生变化，使得节点本身或其邻居节点移动离开节点原来的位置，从而使得现有的某些链路断裂不能再被使用。DSR协议支持主动应答和被动应答两种链路状态监测方法，路由维护通过路由错误分组RERR和确认分组来实现。DSR协议的路由维护主要分为以下几个阶段：（1）转发数据分组的节点根据数据分组头中携带的源路由将其转发给下一跳节点。然后转发节点要使用确认机制确定数据分组是否被下一跳节点正确接收到，如果得到确认信息则说明现有路径是正确的，否则说明本节点到下一跳节点之间的链路发生

12、断裂。（2）如果节点通过确认机制发现到下一跳节点的链路已经断裂，则要初始化一路由错误分组RERR向数据分组的源节点报告链路断裂信息。错误分组中要包含本节点IP地址和不能到达的下一跳节点IP地址。发送RERR分组后，节点可能试图抢修遇到路由出错的数据分组而不是丢弃它。节点搜索自己的路由缓存查找到路由出错的数据分组的目的节点的路由，如果找到就通过用自己缓存中的路由替换路由出错分组中的源路由来抢修数据分组。（3）收到或者串听到RERR分组的节点检查自己的路由缓存，将含有RERR分组中断裂链路的所有路由项全部删除，并且接收节点要对RERR分组进行转发。（4）源节点收到RERR分组后，将失效路由从路由缓

13、存中删除，为路由出错的数据分组触发一次新的路由建立过程。2.2 DSR协议路由缓存机制的缺陷在DSR协议中，每个节点把自己所知的任何新的完整路由信息都存储在自己的路由缓存里，而不管是以何种方式获得的路由信息。当节点有数据分组需要发送时，只要缓存中有到目的节点的路由，或者有经过目的节点的路由，节点就将其作为数据分组的源路由封装在数据分组头部，将数据分组发送出去，只有当缓存中没有合适的路由时才为数据分组启动新的路由发现过程。路由缓存中存放的是到目的节点的完整的路由，当节点要发送数据分组到路由上的中间节点的时候，可以直接从缓存中现有路由中得到到中间节点的路由，不用为中间节点重新启动新的路由建立过程。

14、此外，缓存中可以同时存放到同一目的节点的多条路径，从而可以为用户提供更好的QoS服务5。无线自组网络的拓扑结构是经常变化的，相邻的节点随时可能会移动从而不在彼此的通信范围之内。但是DSR缓存中的路由不会随着网络拓扑结构的变化及时得到更新，因为在DSR协议中，只有在数据分组传输的过程中，遇到使用的路径发生断裂的情况下才会有引起断链的中间节点向源节点发送RERR报文，报告路由的断裂。也就是说源节点只有在数据分组已经发送出去，之后收到RERR错误报告报文的时候才会知道缓存中的路由已经失效，才再次为发送失败的数据分组启动路由发现过程寻找新的路径，这就增加了数据分组的传输延迟，增加了不必要的路由分组与正

15、常的数据分组争用有限的传输带宽，从而增加了冲突产生的机率，这些都是由于DSR协议中的路由缓存不能对其中的路由进行及时更新的结果。3 改进的DSR路由协议策略3.1 AODV协议局部连接性管理机制分析AODV协议使用逐跳路由，路由表中只保存到目的节点的唯一一条路由的下一跳节点信息。但是，AODV协议路由表中的路由都是比较新的、能反映最新网络拓扑结构的路由。这主要是因为AODV协议使用局部连接性管理机制，及时检测链路中断情况，使已经失效的路由能够及时的从路由表中删除。AODV协议局部连接性管理机制6的工作过程是：节点维护一张列表，记录与自己相邻而且处于通信状态的节点，这个列表称为“邻居列表”；正在

16、进行通信的节点在一段时间内如果没有发送任何数据，就主动在自己的直接通信范围内广播一个消息，通知邻居节点自己的存在，这个消息称为“Hello”消息；收到Hello消息的节点延长相应邻节点的生存时间，如果该消息来自一个新的邻节点，则在邻居列表中增加一个记录；节点周期性的检测邻节点的有效性，如果超时，则认为该节点离开了原来的位置，经过该邻节点的路由中断。特别地，节点在发送Hello消息时并不更新自己的序列号。3.2 基于局部连接性管理机制的路由缓存改进策略AODV的局部连接性管理机制使得节点能够主动的发现路由表中的失效路由，避免了使用失效路由来传输数据分组所造成的传输时延和带宽浪费，使得源节点能及时

17、的为相应目的节点重新建立有效路由。然而，DSR路由协议采用路由缓存机制，过分依赖路由缓存，网络拓扑变化快时，DSR面临多跳路由的选择一般是跳数最小的，而跳数最小的有可能是已经失效的路由，且DSR缓存中的路由只有当有数据分组使用该路由的过程中遇到路径断裂的情况下才能发现路由过期，然后重新进行新的路由发现过程。所以在节点运动剧烈的情况下DSR的数据分组中会用到过期路由，导致数据分组发送失败，从而降低了分组发送成功率。也正是由于DSR协议的分组发送成功率低，使其推迟了路由重建的时间和数据分组正常传输的时间，这种数据分组传输延迟对用户来说是不能允许的，尤其是某些紧急场合如救灾现场和战场上。因此，DSR

18、协议中误用失效路由的情况急需改善。基于上面的分析对比可以考虑将AODV的局部连接性管理机制引入DSR协议，使其尽快发现缓存中的失效路由从而避免使用已经失效的路由来传输数据分组，尤其在节点运动剧烈的情况下。事实上，局部性连接管理机制大体思想的引入，在基于DSR协议的QoS路由协议NSR7和AQOR8中就存在了，这两种QoS路由协议通过周期性广播QoS状态信息包来进行QoS路由的状态通知，以实现DSR协议中的QoS路由选择。但是NSR协议和AQOR协议中的周期性广播也引入了局部性连接管理机制的缺点，即周期性的广播报文会产生大量的路由负载，减小了移动自组网中有限的带宽资源，降低了路由协议的总体性能。

19、考虑到在节点运动不剧烈的情况下，DSR协议的数据分组传输成功率和路由负载等性能要优于AODV协议，如果此时也要定期发送Hello广播报文反而会降低DSR协议的性能，所以本文在引入AODV协议局部连接性管理机制的同时，亦对其进行相应的改进，使得这种设计思想能更好的应用于DSR协议。本文使用双向链路网络环境，将加入局部连接性管理机制的DSR协议称为DSR-ERAD（DSR with Error Route Active Discovery），即带错误路由主动发现机制的DSR协议。一条路径一般由多跳节点组成，当其中任何两跳相邻节点移动到不在彼此通信范围之内时，两跳节点之间的链路就断裂了，通过此段链路

20、的所有路径就成为失效路由。为实现路由失效主动探测，每个节点都要维护一个邻节点表，本文中定义为HelloTable，记录与之通信的邻节点的有关信息，每个邻节点在HelloTable中有一个入口 HelloTableEnry。当检测到某个邻节点不在自己的通信范围内时，就将此邻节点的对应信息从邻节点表中删除，同时将路由缓存中使用此跳链路的路由从路由缓存中删除，并向相应路由的源节点发送RERR分组，使源节点以及中间逆向转发RERR的节点清除与该跳链路有关的路由，使断裂路径上的所有节点都能够及时清除失效的路由，源节点收到RERR分组后可为刚失效的目的节点启动新的路由建立过程，也可等到有数据分组要发送到相

21、应目的节点时再为其启动路由建立过程，以保持DSR按需路由的本质。当检测到一个新的节点进入其通信范围之内时，就在节点的HelloTable中为其建立相应的HelloTableEntry。在节点运动不剧烈的情况下，则应大大减少Hello消息的发送数量。结合上述邻节点表结构和本文大量测试数据，本文中以邻节点表中大多数（本文使用75）邻居节点在大于等于100秒的时间内依然在此节点的通信范围内为条件，如果符合此条件则认为此节点周围的网络环境比较平稳，节点开始减少Hello消息的发送数量，具体方法见下文。这种以邻节点表中大多数邻居节点长期与本节点处于通信范围之内为前提的网络稳定性，是一种灵活的相对的网络稳

22、定性，它并不是指整个网络中的节点都静止不动，而是指节点与其大多数邻居节点的相对运动保持在一个合理的范围内，使得节点和邻居节点在这种网络环境中较长时间的处于彼此的通信范围之内。使用错误路由主动发现机制的节点如果在Hello消息的发送周期内没有发送任何RREQ广播消息，则主动发送一TTL值为1的Hello广播消息，以通知邻节点自己的存在。当节点收到某个邻节点的RREQ广播报文或是Hello消息时，就将邻节点表中对应的邻节点的生存周期延长。如果节点收到一个新的节点的Hello消息，就在邻节点表中为其建立一邻节点表入口HelloTableEntry，以记录其相关信息。节点每隔一Hello消息的发送周期

23、就检查自己的邻节点表，看有没有邻节点过期，如果有的邻节点已经过期则将其对应的HelloTableEntry删除，并在节点的路由缓存中查找是否有的路由经过已经到期的邻居节点，如果存在这样的路由就将其删除，防止有的数据分组使用此无效路由进行传输。节点每隔100秒还要定期检查邻节点表，看节点周围的网络环境是否处于稳定状态，进而是否需要减小Hello消息的发送数量，这主要是通过改变Hello消息的广播周期来实现的，首先本文作如下符号定义：HelloSendPeriod表示Hello消息的发送周期，一个发送周期由两个HelloInterval组成，HelloInterval的初始值按照AODV中的规定设

24、为“1秒”。相应节点网络稳定状态检查算法步骤如下：（1）若通过检测邻节点表中有大于等于75的邻节点在表中的停留时间超过100秒，则将HelloInterval值为50秒，相应的HelloSendPeriod赋值为100秒，节点每隔100秒才广播一次Hello消息。（2）若在检查邻节点表时，表中停留时间超过100秒的邻节点的数目小于75且大于等于40，则做如下赋值改变：HelloInterval=HelloInterval/2秒，HelloSendPeriod也相应改变。（3）若经检测表中停留时间超过100秒的节点的数目小于40，则值HelloInterval =1秒，HelloSendPeri

25、od为2秒。经过以上改进就大大减少了在节点稳定时所发送的Hello报文消息数量，改进了AODV协议中Hello消息要按固定周期进行广播，造成路由负载开销大的缺点。4 实验仿真4.1 仿真实验设计实验采用NS2仿真软件910，建立规模为50个节点，范围是1000m*600m的仿真场景，所有节点以020m/s范围内的任意速度随机移动，每个节点随机选择目的节点发送分组，分组大小为256字节，发送速率为4 packets/s。改进后的 DSR 路由协议主要对网络分组传送成功率、端到端延迟以及负载有一定的影响，因此下文将主要围绕这三个指标对各协议的性能进行比较测试。现对相关性能参数作如下说明：（1）分组

26、传送成功率：目的节点成功接收到的数据包数占源节点发送出的数据包数的比率。（2）数据包的平均端到端延迟：所有成功接收到的数据包的接收时间与其发送时间的差值的平均值。（3）路由负载：模拟通信过程中所有节点发送或转发的路由信息包的数量。4.2 仿真结果分析图4-1分组传送成功率对比图图4-1为三种协议的分组传送成功率的对比图，从图中可以清楚的看到改进后的DSR-ERAD协议不仅没有影响原DSR协议的分组传送成功率，还提高了分组传送成功率，尤其在节点运动剧烈的情况下。图中显示三种协议随着节点移动速率的降低，分组传送成功率均逐渐提高，在节点运动趋于平缓的环境下即节点的停顿时间超过100秒之后，分组传送成

27、功率逐渐稳定，DSR-ERAD和原DSR协议的稳定在0.98以上，AODV也均在0.95以上。图4-2数据传输延迟对比图图4-2是三种路由协议平均数据传输延迟的对比图，可以看出总体上DSR-ERAD协议和AODV协议的平均端到端延迟比较接近，而且明显低于原DSR协议，最大差值接近2.5秒。但DSR-ERAD协议的平均数据传输延迟还是要高于AODV协议，这主要是由于DSR-ERAD协议也是使用源路由的协议，中间节点在转发携带源路由的数据分组时以及在转发RREP分组时，都要对分组携带的源路由进行分析提取，以存储节点可以使用的更多路由，这无疑会增加数据分组的传输延迟，因此DSR-ERAD协议的平均数

28、据传输延迟要高于AODV协议。图4-3 路由负载对比图图4-3为三种协议的路由负载的对比图，可以看出DSR-ERAD协议除了具有较高的分组传输成功率、较低的平均传输延迟外，还具有较低的路由负载，也即具有较低的网络消耗量。在节点运动不剧烈的情况下，DSR-ERAD协议的路由负载略高于原DSR协议；在节点运动异常剧烈的情况下，DSR-ERAD协议和AODV协议可以主动及时的清除失效的路由，避免了路由重建和多余的数据分组与要正常传输的数据分组的冲突，所以路由负载比原DSR协议要低。而DSR-ERAD协议在节点运动异常剧烈的情况下除了能及时清除失效路由避免不必要的路由重建过程外，还能利用路由缓存中的完

29、整源路由信息相对AODV协议节省更多的路由建立过程，所以在节点运动异常剧烈的情况下DSR-ERAD协议具有最低的路由负载。5 结束语移动自组网的按需路由控制协议DSR是最有实用前景的移动白组网路由协议之一，针对DSR协议不能及时发现路由缓存中的失效路由的缺陷，本文基于AODV局部连接性管理机制提出了DSR路由缓存改进策略。重点剖析了DSR协议的运行机制，分析了协议缓存机制中存在的缺陷，提出一种带错误路由主动发现机制的DSR-ERAD，详细描述了DSR-ERAD协议运行机制，并使用网络模拟软件NS2对DSR-ERAD协议、原DSR协议和AODV协议性能进行仿真，仿真结果证明DSR-ERAD协议很

30、好的提高了DSR协议的性能。参考文献1 余旭淘，毕光国等Ad Hoc网络按需路由协议的改进J计算机学报，2004，27(6)：8388442 于宏毅.无线移动自组织网M. 北京：人民邮电出版社，2006:171-1823 D.Johnson，Y.Hu,D.Maltz. The Dynamic Source Routing Protocol(DSR) for Mobile Ad Hoc Networks for IPv4Shttp：/wwwrfc-editorOrg/rfc/rfc4728.txt，20074 Johnson DB，Maltz DA，Hu YCThe dynamic Source routing protocol for mobile Ad Hoc