摘  要： 基于自适应移动多跳Ad Hoc网络，针对其DSR协议的路由缓存机制，分析不足之处，探索对现有的路由缓存机制的优化方法。提出了缓存路由有效期的概念，为网络中节点的路由表添加一个用于反馈的“缓存路由跳数”参数，节点选择此参数值最小者的路由信息。仿真实验表明，经过改进的缓存机制有效地避免了响应冲突问题，实现了路由的最短优化，在平均传输延迟、分组投递率、吞吐量性能方面都有提高。
关键词： DSR；路由缓存；缓存路由有效期；跳数；NS2

    Ad Hoc网络[1]是一种特殊的无线移动通信网络，网络中所有的节点地位平等，无需设置任何的中心控制节点。对于Ad Hoc网络而言，路由协议算法是最关键的技术。目前存在的Ad Hoc网络路由协议分为表驱动路由协议和按需路由协议两种。近年来，对于DSR协议已经做了一系列研究，DSR协议的不足有：(1)用于路由发现的控制报文会波及全网各节点，耗费较大；(2)路由响应风暴问题，源节点会同时收到多个路由响应，造成了响应冲突；(3)无效缓存路由问题，过期的路由信息会传染其他节点。目前的研究结果主要有：庄春梅等[2]提出了DSR的邻居表结构，根据节点状态缩短路由，同时节点通过延迟转发路由发现包的时间来选择生存时间长的路由；AYUB J等[3]用一组参数描述节点的运动规律，论述了基于链路稳定性评估的路由协议的研究；Chen Jiaxu等[4]采用节点局部自适应机制，对于路由断路绕远等问题进行自动恢复调整，对DSR协议的缓存机制进行了改进；TAMILARASI M等[5]提出了节点局部自适应机制，对于路由断路绕远等问题进行自动恢复调整；Zhou Nianjun等[6]针对DSR协议传输报文时，遇到阻塞的路由开销进行了改进；李学桥等[7]提出了分布式的缓存更新机制，让各个节点异步地保持最新路由信息。但是上述文献中考虑的只是对已有路由失效后的策略，并未避免路由响应冲突问题。  
1 DSR协议
    DSR协议是一种基于源路由方式的按需路由协议，主要包括路由发现和路由维护两个过程。当源节点有报文发送要求时，首先检查自己的缓存里是否有到达目的节点的路由，若存在则直接使用，否则发送r_req路由请求消息。当中间节点接收到r_req时，检查是否收到过此消息，若收到过则停止转发，并回复路由响应；若没有，则先检查自己缓存中是否有到达目的节点的路由，若有则加入该路由并返回r_rep，若没有则将自己的地址加到r_req再转发此r_req，直到源节点成功地接收到路由响应信息r_rep。在传输报文过程中，当中间节点检测到通往目的节点的下一跳链路中断时，它将从自己的缓存中删去包含该链路的路由并向源节点返回一个r_err出错分组，源节点收到r_err后，重新进行路由发现。Fu Z等[8]测试了TCP协议代理下的传输吞吐量与报文丢失的数据，发现DSR协议在吞吐量方面有缺陷。
    由于无线广播信道的特点，节点可以处于“混合监听”状态，这样会出现“隐终端”问题，会产生报文响应冲突，进而造成传输阻塞。
2 基于冲突避免的优化
2.1 优化的算法
    本文提出的优化建立在DSR协议已有的路由缓存机制上，因为节点处于移动状态，某节点在某一时刻可能正在运动，也可能停止不动，并且运动的速度也有大有小。主要目标是针对DSR协议的路由寻找与路由回复阶段产生的响应冲突问题。
    本文为网络中节点的路由表添加一个用于反馈的“缓存路由跳数”参数。各节点自有的缓存路由不会长时间有效，根据运动速度的大小和停留时间确定缓存路由的有效期。在有效期内，源节点或中间节点向下一节点发送路由请求后，可能会收到两个或多个中间节点的路由响应，这时，发送路由请求的节点查看收到的路由响应对应的缓存路由跳数值，并选择最小者的路由信息。一旦超过有效期，节点就启动路由缓存更新，重新进行路由发现，并删除无效路由信息。如图1、图2所示，经过改进的路由请求报文r_req比原有的r_req增加的字段有缓存路由跳数m和缓存路由有效期TTL。

    改进后的协议DSR-BCA(DSR based on Collision Avoi-
dance)运作方式如下：
    (1)如果源节点S的下一节点就是目的节点D，则节点D直接填充路由请求记录字段，缓存此路由，记录跳数m=1，并回复r_rep报文；否则转到步骤(2)；
    (2)源节点S的下一节点是中间节点，中间节点在收到r_req报文后，查看若发现自己的缓存路由信息中已有到达目的节点的路由，则直接回复r_rep报文，这样减少了路由请求消息的广播，否则转到步骤(3)；
    (3)源节点S的下一节点是中间节点，且r_req报文中的源节点地址请求类型ID存在于此中间节点的序列对列表中，表明此r_req报文已经收到过，此中间节点不需处理该请求；否则转到步骤(4)；
    (4)如果中间节点的地址已在r_req报文的路由请求记录字段中，表明经过此中间节点的路由跳数必不是最小的，回复一个r_rep报文给上一节点，通知其再寻找下一跳节点；否则转到步骤(5)；
    (5)如果此中间节点不满足步骤(3)和步骤(4)，则将自己的地址添加到路由请求记录字段，然后向邻节点广播该路由请求，此中间节点仍然要缓存这个路由信息，记录跳数；然后转到步骤(6)；
    (6)若r_req报文经过转发到达了目的节点D，则报文中的路由请求记录字段中节点地址序列构成了从源节点S到目的节点D的完整路由信息，节点D会缓存此信息，记录跳数，并回复r_rep报文。
    (7)在路由维护阶段，对于不同运动速度的节点，设置不同的TTL。当节点运动速度大时，它附近网络的拓扑变化就快，缓存路由的TTL就小；反之则大。一旦时长达到TTL，参与报文传输的节点丢弃原有的路由信息，再次启动路由发现过程。

    dsrbca_bitreq只比dsr_bitreq多了两个字段，即2 bit，而n可达到101或102，故BDSR>>BDSR-BCA。
3 仿真分析与性能比较
3.1 仿真平台与性能指标
    本文使用NS2 version 2.35仿真平台[9]，操作系统为Red Flag Linux 6.0。在仿真前要配置节点参数，利用仿真结果进行性能分析。性能指标有以下3个：平均传输时延，指从源节点发出一个分组到目的节点接收到此分组的时间间隔的平均值；分组投递率，指目的节点接收到的报文数与源节点发送的报文数之比；归一化路由开销，指平均每发送一个分组所需要的路由控制分组数占总分组数的比例。
3.2 仿真场景设置与结果分析
    利用NS2仿真平台对优化前后的协议性能进行测试。节点运动模型采用Random Way Point模型，仿真平台的参数设置如表1所示。

     如图4所示，随着节点的运动速度增大，DSR和DSR-BCA协议的分组投递率缓慢减小。这是因为失效路由增多，有用的数据传输受到的阻碍也会变大，源节点发送的报文也随之丢失。从图中可以看出，节点运动速度在15 m/s以内时，分组投递率可以在98%以上，在这个指标上，DSR-BCA比DSR的性能只是提高了一点。

    如图5所示，随着节点的运动速度增大，DSR和DSR-BCA协议的归一化路由开销都在增加。随着网络拓扑结构的变化，路由更新的次数增多，用于路由维护的控制报文也增多了。DSR-BCA协议的路由维护过程的额外耗费比DSR协议的少，在节点移动速度达到40 m/s时可以少约18%，速度越大越明显。

    Ad Hoc网络因其节点具有移动、无中心、多跳的特点，从而导致了网络拓扑的动态变化，因此路由协议的研究一直是热点与难点。DSR协议作为按需路由的一种，其现有的路由机制仍然有一些缺陷，如路由响应风暴问题、失效路由问题。本文提出了缓存路由有效期、缓存路由跳数的概念并将其应用到DSR协议中优化。NS2仿真结果表明，DSR-BCA的性能比DSR的优越。
参考文献
[1] 郑少仁，王海涛，赵志峰，等.Ad Hoc网络技术[M].北京：人民邮电出版社，2005：1-48.
[2] 庄春梅，王利利，陆建德.DSR协议的路由缓存策略[J]. 计算机工程，2010，36(2)：100-101.
[3] AYUB J，GARRIDO G，MARANDIN D.A linkcache invalidation mechanism for dynamic source routing(DSR) in Ad Hoc networks[J].IEEE Journal on Selected Areas in Communications，2007(7)：1144-1148.
[4] Chen Jiaxu，Tang Yazhe，Fu Dian，et al.On the improving strategies upon the route cache of DSR in MANETs[C]. International Conference on Ubiquitous Intelligence and Computing，Xi′an，2010：26-29.
[5] TAMILARASI M，PALANIVELU T G.An efficient Hop  count based adaptive route cache timeout(HART) mechanism for on-demand routing in MANETs[J].IETETechnical  Review，2007(6)：68-73.
[6] Zhou Nianjun，Wu Huaming，ABOUZEID A A.The impact  of traffic patterns on the overhead of reactive routing protocols[J].IEEE Journal on Selected Areas in Communications，2005(3)：547-560.
[7] 李学桥，赵磊，贾小爱，等.DSR协议Cache管理策略的优化[J].通信技术，2009，42(2)：85-87.
[8] FU Z，ZERFOS P，LUO H，et al.The impact of multi hop wireless channel on TCP throughput and loss[C].Proceedings of the 22nd Annual Joint Conference of the IEEE Computer  and Communications Societies，San Francisco，2003：1744-1753.
[9] 王辉.NS网络模拟器的原理和应用[M].西安：西北工业大学出版社，2008：30-56.