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

1、改进的移动自组网dsr协议路径缓存策略摘 要：动态源路由协议在ad hoc网络拓扑结构变化频繁时，缓存中的路由得不到及 时更新会经常失效，从而导致网络性能卜降，木文对dsr(dynamic source routing)路由 协议的缓存管理进行了研究。基于aodv i办议局部连接性管理机制捉出了一种带错误 路由主动发现机制的改进dsr协议，该协议口j以提高缓存中路由信息的准确率，较好 的适应了 ad hoc网络动态的网络拓扑结构变化。仿真结果表明，该方法可以有效提高 分组投递率，同时降低路由开销及传输延迟。关键字：移动自组网络；dsr；缓存管理；局部连接性管理；ns2；optimized ca

2、ching strategies in dsr routing protocol forwireless 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

3、something 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 informat

4、ion, 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, loc

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

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

7、高度反应式的服务确保数据分组在节点移 动或者其他网络条件变化的条件下仍然能够止确地递交。dsr主要包括路由建立和路由 维护两个过程内，下而对其路由机制进行详细分析。2.1 dsr协议的运行机制2.1.1 dsr协议的路由发现机制(1) 产生路由请求当源节点需要与某目的节点进行通信时，它首先在本节点维护的路由缓存中查找是 否有到达该目的节点的路由。若路由缓存中己包含了到达该目的节点的有效路由，贝ij立 即使用此路由发送数据分组，否则它将向所有邻居广播rreq (route request)分组， 以启动一个路由发现过程來找到一条到达该目的节点的可用路由。(2) 节点处理路由请求 如果接收rreq

8、的节点是该路由请求的目的节点，则向发起rreq的源节点返 回rrep分组。 收到rreq的节点检杳口己是否已经包含在rreq携带的源路由节点列表中， 如果是则将rreq分组丢弃。 如果协议要求使用双向链路，节点要检查前一节点是否在口己的通信范围内，如 果不在则丢弃该rreq包;如果不确定则向前一节点发送一 ttl值为的rreq分组, 如果前一节点回复rrep,则表示两节点之间是双向链路，继续处理rreq分组，否则 将rreq分组丢弃。 接收rreq的节点在本地缓存小查看有无与rreq请求路由对相对应的入口， 如有则将现在收到的rreq分组丢弃。 如果接受rreq的节点的本地缓存小没有此rreq

9、对应的表项，则按以下步骤 处理该rreq请求分组：将节点自己的ip地址追加到rreq分组的源路出节点列表中； 为修改后的rreq分组在节点的路由请求表中创建一入口；将新改好的rreq拷贝广 播发送出去。(3) 中间节点回复rrep分组 小间节点将从自己路由缓存小得到的路径追加到rreq分组头小的源路由地址 列农中，这样就得到耍发给rreq源节点的完整路由，然后将得到的源路由封装在rrep 包中发送给发起rreq的源节点。 中间节点发送完路由缓存回复后，不再继续广播rreq分组，直接将rreq分 组丢弃。(4) 处理并转发路由回复b的节点收到rreq分组得到完整的源节点到目的节点的路市后，将此路

10、由封装在 rrep分组屮，然后发送给源节点。rrep分组可以封装成一个单独的ip分组传递给源 节点，或封装在其他有数据耍传输给源节点的ip分组中被捎带回源节点。目的节点将 自己的ip地址追加到rreq携带的节点的ip地址列表屮，将得到的ip地址列表作为 返回给源节点的完整路由封装在rrep分组屮。rrep数据分组的源ip地址设为发送rrep分组的节点的ip地址，目的ip地址设为发起rreq的源节点的ip地址。如果使 用的底层mac协议支持双向路由，rrep数据分组可沿rrep选项中携带的源路由的 逆向路由依次传输，否则a的节点为此rrep选项发起新的路由发现过程，且要将rrep 选项封装在新产

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

12、组是否被下一跳节点止确接收到，如果得到确 认信息则说明现有路径是正确的，否则说明本节点到下一跳节点之间的链路发生断裂。(2) 如果节点通过确认机制发现到下一跳节点的链路已经断裂，则要初始化一路 由错误分组rerr向数据分组的源节点报告链路断裂信息。错误分组屮要包含本节点ip 地址和不能到达的下一跳节点ip地址。发送rerr分组后，节点口j能试图抢修遇到路 由出错的数据分组而不是丢弃它。节点搜索口己的路由缓存查找到路由出错的数据分组 的冃的节点的路由，如果找到就通过用自c缓存中的路由替换路由出错分组中的源路由 來抢修数据分组。(3) 收到或者串听到rerr分组的节点检查自己的路由缓存，将含冇re

13、rr分组 中断裂链路的所有路由项全部删除，并11接收节点要对rerr分组进行转发。(4) 源节点收到rerr分组后，将失效路由从路由缓存中删除，为路由出错的数 据分组触发一次新的路由建立过程。2. 2 dsr协议路由缓存机制的缺陷在dsr协议中，每个节点把自己所知的任何新的完整路由信息都存储在自己的路 由缓存里，而不管是以何种方式获得的路由信息。当节点有数据分组需要发送时，只要 缓存中有到目的节点的路由，或者有经过目的节点的路由，节点就将其作为数据分组的 源路由封装在数据分组头部，将数据分组发送出去，只有当缓存中没有合适的路ft!时才 为数据分组启动新的路由发现过程。路由缓存中存放的是到目的节

14、点的完整的路由，当节点耍发送数据分组到路由上的 中间节点的时候，可以直接从缓存中现有路由中得到到中间节点的路由，不用为中间节 点重新启动新的路由建立过程。此外，缓存中可以同时存放到同一目的节点的多条路径, 从而可以为用户提供更好的qos服务叫无线自组网络的拓扑结构是经常变化的，相邻的节点随时可能会移动从而不在彼此 的通信范围之内。但是dsr缓存中的路市不会随着网络拓扑结构的变化及时得到更新, 因为在dsr协议屮，只有在数据分组传输的过程中，遇到使用的路径发生断裂的情况 下才会有引起断链的中间节点向源节点发送rerr报文，报告路由的断裂。也就是说源节点只有在数据分组已经发送出去，之后收到rerr

15、错误报告报文的时 候才会知道缓存屮的路由已经失效，才再次为发送失败的数据分组启动路由发现过程寻 找新的路径，这就增加了数据分组的传输延迟，増加了不必要的路由分组与正常的数据 分组争用有限的传输带宽，从而增加了冲突产生的机率，这些都是由于dsr协议中的 路由缓存不能对其中的路由进行及时更新的结果。3改进的dsr路由协议策略3.1 aodv协议局部连接性管理机制分析aodv协议使用逐跳路曲，路由表中只保存到目的节点的唯一一条路由的下一跳节 点信息。但是，aodv协议路由表中的路由都是比较新的、能反映最新网络拓扑结构的 路由。这主要是因为aodv协议使用局部连接性管理机制，及时检测链路中断情况， 使

16、已经失效的路由能够及时的从路由表中删除。aodv协议局部连接性管理机制的工作过程是：节点维护一张列表，记录与自己 相邻而且处于通信状态的节点，这个列表称为“邻居列表s正在进行通信的节点在一段 时间内如果没有发送任何数据，就主动在自己的直接通信范围内广播一个消息，通知邻 居节点111己的存在，这个消息称为"hello"消息；收到hello消息的节点延长相应邻节点 的生存时间，如果该消息来自一个新的邻节点，则在邻居列表中增加一个记录；节点周 期性的检测邻节点的有效性，如杲超时，则认为该节点离开了原来的位置，经过该邻节 点的路由中断。特别地，节点在发送hello消息吋并不更新自己

17、的序列号。3. 2基于局部连接性管理机制的路由缓存改进策略aodv的局部连接性管理机制使得节点能够主动的发现路由表屮的失效路由，避免 了使用失效路由來传输数据分组所造成的传输时延和带宽浪费，使得源节点能及时的为 相应口的节点重新建立有效路由。然而，dsr路由协议采用路由缓存机制，过分依赖路 由缓存，网络拓扑变化快时，dsr面临多跳路由的选择一般是跳数最小的，而跳数最小 的有可能是已经失效的路由，口 dsr缓存中的路由只有当有数据分组使用该路由的过 程屮遇到路径断裂的情况下才能发现路由过期，然后重新进行新的路由发现过程。所以 在节点运动剧烈的情况下dsr的数据分组屮会用到过期路由，导致数据分组发

18、送失败, 从而降低了分组发送成功率。也正是由于dsr协议的分组发送成功率低，使其推迟了 路由重建的时间和数据分组正常传输的时间，这种数据分组传输延迟对用户来说是不能 允许的，尤其是某些紧急场合如救灾现场和战场上。i大i此，dsr协议中谋用失效路由的 情况急需改善。基于上而的分析对比可以考虑将aodv的局部连接性管理机制引入dsr i办议，使 其尽快发现缓存中的失效路出从而避免使用已经火效的路曲來传输数据分组，尤其在节 点运动剧烈的情况下。事实上，局部性连接管理机制大体思想的引入，在基于dsr亦 议的qos路由协议nsr和aqor冈中就存在了，这两种qos路出协议通过周期性广播 qos状态信息包

19、來进行qos路由的状态通知，以实现dsr协议中的qos路由选择。但 是nsr协议和aqor协议小的周期性广播也引入了局部性连接管理机制的缺点，即周 期性的广播报文会产生大量的路曲负载，减小了移动自组网中冇限的带宽资源，降低了 路由协议的总体性能。考虑到在节点运动不剧烈的情况下，dsr协议的数据分组传输成功率和路由负载等 性能要优于aodv协议，如果此时也要定期发送hello广播报文反而会降低dsr协议 的性能，所以本文在引入aodv协议局部连接性管理机制的同时，亦对其进行相应的 改进，使得这种设计思想能更好的应用于dsr协议。本文使用双向链路网络环境，将 加入局部连接性管理机制的dsr协议称为

20、dsr-erad (dsr with error route active discovery),即带错误路由主动发现机制的dsr协议。一条路径一般由多跳节点组成，当其中任何两跳相邻节点移动到不在彼此通信范围 z内时，两跳节点z间的链路就断裂了，通过此段链路的所自路径就成为失效路由。为 实现路由失效主动探测，每个节点都要维护一个邻节点表，本文中定义为hellotable, 记录与之通信的邻节点的有关信息，每个邻节点在heliotable中有一个入口 hellotableenryo当检测到某个邻节点不在口己的通信范围内时，就将此邻节点的对应 信息从邻节点表屮删除，同时将路由缓存小使用此跳链路的路

21、由从路由缓存小删除，并 向和应路由的源节点发送rerr分组，使源节点以及中间逆向转发rerr的节点清除与 该跳链路有关的路由，使断裂路径上的所有节点都能够及时清除失效的路由，源节点收 到rerr分组后可为刚失效的目的节点启动新的路出建立过程，也口j等到有数据分组要 发送到相应目的节点时再为其启动路由建立过程，以保持dsr按需路由的本质。当检 测到一个新的节点进入其通信范围z内时，就在节点的hellotable中为其建立相应的 hellotableentryo在节点运动不剧烈的情况下，则应大大减少hello消息的发送数量。结合上述邻节 点表结构和本文大量测试数据，本文中以邻节点表中大多数(本文使

22、用75%)邻居节点 在大于等于100秒的时间内依然在此节点的通信范围内为条件，如果符合此条件则认为 此节点周围的网络环境比较平稳，节点开始减少hello消息的发送数量，具体方法见卜 文。这种以邻节点表屮大多数邻居节点长期与木节点处于通信范围之内为前提的网络稳 定性，是一种灵活的相对的网络稳定性，它并不是指整个网络中的节点都静止不动，而 是指节点与其大多数邻居节点的相对运动保持在一个合理的范围内，使得节点和邻居节 点在这种网络环境中较长时间的处于彼此的通信范围之内。使用错误路由主动发现机制的节点如果在hello消息的发送周期内没有发送任何 rreq广播消息，则主动发送一 ttl值为1的hello

23、广播消息，以通知邻节点自己的存 在。当节点收到某个邻节点的rreq广播报文或是hello消息时，就将邻节点表中对应 的邻节点的生存周期延长。如果节点收到一个新的节点的hello消息，就在邻节点表中 为其建立一邻节点表入口 hellotableentry,以记录其相关信息。节点每隔一 hello消息 的发送周期就检查自己的邻节点表，看有没有邻节点过期，如果有的邻节点已经过期则 将其对应的hellotableentry删除，并在节点的路由缓存耳喳找是否有的路由经过已经到 期的邻居节点，如果存在这样的路由就将英删除，防止冇的数据分组使用此无效路由进 彳亍传输。节点每隔100秒还要定期检查邻节点表，看

24、节点周围的网络环境是否处于稳定状态, 进而是否需要减小hello消息的发送数量，这主要是通过改变hello消息的广播周期來 实现的，首先木文作如下符号定义：hellosendperiod表示hello消息的发送周期，一个 发送周期由两个hellolnterval组成，hellolntewal的初始值按照aodv屮的规定设为“1 秒二相应节点网络稳定状态检查算法步骤如下：(1) 若通过检测邻节点表中有大于等于75%的邻节点在表小的停留时间超过100 秒，则将hellolnterval值为50秒，和应的hellosendperiod赋值为100秒，节点每隔100 秒0广播一次hello消息。(2)

25、 若在检查邻节点表时，表中停留时间超过100秒的邻节点的数目小于75%11 大于等于 40%,则做如下赋值改变：hellointerval=hellointerval/2 秒，hellosendperiod 也相应改变。(3) 若经检测表中停留吋间超过100秒的节点的数目小于40%,则值hellolnterval 二1 秒，hellosendperiod 为 2 秒。经过以上改进就大大减少了在节点稳定吋所发送的hello报文消息数量，改进了 aodv协议中hello消息要按固定周期进行广播，造成路由负载开销大的缺点。4实验仿真4.1仿真实验设计实验采用ns2仿真软件91,0,建立规模为50个节

26、点，范围是1000m*600m的仿真 场景，所有节点以020m/s范围内的任意速度随机移动，每个节点随机选择口的节点发 送分组，分组大小为256字节，发送速率为4packets/s。改进后的dsr路由协议主要 对网络分组传送成功率、端到端延迟以及负载有一定的影响，因此下文将主要围绕这三 个指标对各协议的性能进行比较测试。现对相关性能参数作如下说明：(1) 分组传送成功率：目的节点成功接收到的数据包数占源节点发送出的数据包 数的比率。(2) 数据包的平均端到端延迟：所有成功接收到的数据包的接收时间与其发送时 间的弟值的平均值。(3) 路由负载：模拟通信过程中所有节点发送或转发的路由信息包的数量。

27、4. 2仿真结果分析dath received xtio图41为三种协议的分组传送成功率的对比图，从图中可以清楚的看到改进后的 dsr-erad协议不仅没冇影响原dsr协议的分组传送成功率，还提高了分组传送成功 率，尤其在节点运动剧烈的情况下。图中显示三种协议随着节点移动速率的降低，分组 传送成功率均逐渐提高，在节点运动趋于平缓的环境下即节点的停顿时间超过10()秒z 后，分组传送成功率逐渐稳定，dsr-erad和原dsr协议的稳定在0.98以上，aodv也均在0.95以上。.2 scragc tr 苗 nsbk dcetydsraodvdsrerad0.05, 0.0111*11111102

28、00300400500600700800900pause time/s图42数据传输延迟对比图图42是三种路由协议平均数据传输延迟的对比图，可以看出总体上dsr-erad 协议和aodv协议的平均端到端延迟比较接近，而且明显低于原dsr协议，最大茅值 接近2.5秒。但dsr-erad协议的平均数据传输延迟还是要高于aodv协议，这主要 是由于dsr-erad协议也是使用源路由的协议，屮间节点在转发携带源路由的数据分 组时以及在转发rrep分组时，都耍对分组携带的源路由进行分析提取，以存储节点可 以使用的更多路由，这无疑会增加数据分组的传输延迟，因此dsr-erad协议的平均 数据传输延迟要高于

29、aodv协议。oug overhead图43路由负载对比图图牛3为三种协议的路由负载的对比图，可以看!li dsr-erad协议除了具有较高的 分组传输成功率、较低的平均传输延迟外，述具有较低的路由负载，也即具有较低的网 络消耗量。在节点运动不剧烈的情况下，dsr-erad协议的路曲负载略高于原dsr协议; 在节点运动并常剧烈的情况下，dsr-erad协议和aodv协议可以主动及时的清除失效 的路由，避免了路由重建和多余的数据分组与要正常传输的数据分组的冲突，所以路由 负载比原dsr协议耍低。而dsr-erad协议在节点运动异常剧烈的情况下除了能及吋清 除失效路由避免不必要的路由重建过程外，述

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

31、真结果证明dsr-erad协议很好的提高了 dsr 协议的性能。参考文献11余旭淘，毕光国等.ad hoc网络按需路由协议的改进j计算机学报，2004, 27(6)： 838 8442 于宏毅.无线移动自组织网m|.北京：人民邮电出版社，2006:171-182.3 d.johnson, y.hu,d.maltz. the dynamic source routing protocol(dsr) for mobile ad hoc networks for ipv4s. http： /www. rfc-editor. org/rfc/rfc4728.txt, 2007.4 johnson db, maltz da，hu yc- the dynamic source routing protocol for mobile ad hoc networks(dsr) s