摘 要 缓存技术是影响按需路由协议性能的关键因素，如何组织缓存结构并及时更新缓存信息是缓存技术目前的主要研究方向。本文分析了DSR协议两种缓存存储结构，路径缓存和链路缓存，提出了一种针对链路缓存的链路生命周期的预测方法，并使用OPNET对使用了链路生命周期预测方法后的DSR协议进行仿真分析，结果表明新的协议比原协议在包传输率、平均端到端时延和路由开销方面都有所改善。

关键词 链路缓存；生命周期；DSR

1 引言

移动Ad hoc网络是由一组带有无线收发装置的移动终端组成的一个多跳、临时和无中心网络。由于没有固定基础设施的支持，路由协议是Ad hoc网络和核心问题。目前Ad hoc网络的路由协议有表驱动路由协议和按需路由协议。从移动自组网的移动性、拓扑动态性、带宽受限、功率约束等特点来看，按需驱动路由更能适应移动网络的需要^[1-2]。按需路由协议为了避免每次发送数据分组前都要进行一次路由发现过程，使用了缓存技术来存储得到的路由信息，如何合理地组织缓存结构并及时更新缓存信息是影响按需路由协议性能的关键因素。

2 DSR协议的缓存技术分析

DSR协议中，在路由发现过程中返回给源节点是一条完整的路由信息。当把这条路径信息独立存储起来时，就构成了路径缓存结构，路径缓存实现起来比较简单，当有数据分组需要发送时，可以很容易的从缓存中搜索出到目的节点的路由信息。在链路缓存中，节点把获得的路由信息按照每条链路的方式存储到节点关于网络的拓扑图中，当有数据要发送时，节点执行图的搜索算法，比如Dijkstra算法，查找到目的节点的路由^[3]。

与路径缓存相比，链路缓存能够更加有效地利用路由信息。当回复的路由信息相同时，使用链路缓存方式往往能找到比路径缓存更多的路由。在发现某条链路中断时，使用路径缓存的节点要删除包含断开链路的整条路由信息；而使用链路缓存的节点只需删除断开的链路信息，这条路由上的其它链路信息仍然可用。例如，节点A在路由回复中得到2条路由信息A-B-C-E和A-C-D-E-F，当使用路径缓存时，节点A的缓存结构如图1所示。当使用链路缓存时，节点A的缓存结构如图2所示。当链路A-C中断后，在路径缓存中将删除所有包含链路A-C的路由，从而找不到到节点D和F的路由。如果有数据分组要发往节点D或F，那么节点必须进行一次新的路由发现过程，产生较大的路由开销；而在链路缓存中，节点A只会在拓扑图中删除链路A-C的信息，通过图的搜索算法A仍能找到到节点D和F的路由信息A-B-C-D和A-B-C-E-F，从而避免一次新的路由发现过程。因此，使用链路可以充分利用路由信息，避免不必要的洪泛过程。

图1 路径缓存

图2 链路缓存

3 链路生存时间预测方法

由于在Ad hoc网络中节点节点可以任意移动，当两个节点移动出彼此的通信范围之外时，它们之间的链路就会中断，因此一条链路的生存时间是有限的。在按需路由协议中，链路的状态只有在使用时才会被发现，如果使用了过期路由大量的路由错误，还会造成分组的丢失。因此，能否及时删除过期的路由信息是影响协议性能的重要因素。

一种常用的方式是为每个链路设定一个生存时间，当超过这个生存时间后将链路从缓存中删除。这个生存时间应该真实的反映链路实际的生命周期，如果这个时间设置得过小，那么过早删除会导致不必要的路由发现过程；如果设置得过大，那么使用无效路由会导致大量分组丢失。下面介绍一种能够准确估计链路生存时间的方法。

Ad hoc网络中通信链路的中断多是由于节点的移动造成的，如果网络中各节点收发器工作特性一致，则无线节点间的信号衰减规律是自由空间模型和双射线反射模型的一种结合，即当无线节点间的距离较小时，节点间的信号变化规律符合自由空间模型；而当节点间的距离较大时，符合双射线地面反射模型，函数形式为：

式中，P₀为发送器信号发送强度，P_r为接收器端的信号接收强度；r为某两直接通信节点间的距离，n随着传输距离在2到4之间变化，当节点间的距离大到一定程度时，接收端信号强度低于接收器的接收灵敏度，信号不能被正确接收，两点间的链路断开，这时它们之间的距离就是最大有效距离。也就是说，随着节点间的运动，当它们超出了它们之间最大的通信距离，该链路就会断开。

在路由发现过程中，要求每个节点添加自己坐标及运动参数(运动速度和运动方向)，在路由回复时回复这些信息，以便对每条链路的生存时间进行预测。预测方法如下：

首先假定N₁，N₂为两个运动中的节点，v₁，v₂分别为两个节点的平均移动速度，θ₁，θ₂为节点主机的移动方向，(x₁，y₁)和(x₂，y₂)分别为节点N₁和N₂的坐标，由于我们只研究这两个节点的相对运动，因此我们可以设N₁静止在坐标原点，N₂相对于N₁在运动，那么此时N₁的坐标为(0，0)，N₂的坐标为(x₂- x₁，y₂

- y₁)。

将N₂相对N₁的运动速度正交分解，在X上的速度为，Y轴上的速度为，设

那么经过时间t后，N₂的新坐标为(a+ct，b+dt)，此时N₁与N₂的距离为r，则

当r为两点间的有效传输距离时，此时的t就是两点间能保持连接的最短时间，也就是链路的估计生存时间(LIFETIME)。

为了避免根据瞬态的两节点的运动状态进行预测带来的偏差，我们使用统计的方法以加权的方式对预测值进行修正。

统计的生存时间值是在链路从缓存中移除时计算的。当链路是由于收到路由错误分组的原因删除时，剩余生存时间L如下计算：

L=当前时间-链路加入缓存时间

当链路是由于过期删除时：

L=上次使用时间-链路加入缓存时间

链路估计生存时间LIFETIME计算如下：

LIFETIME=(1-a)LIFETIME + aL

其中a取值为0.05。

4 仿真及结果分析

4.1 仿真环境与实验参数

本文采用OPNET Modeler10.5网络仿真器对使用路径缓存的DSR协议及使用改进算法后的链路缓存DSR协议(DSR_CSA)进行仿真和性能比较，仿真直接在OPNET自带的MANET模块上进行。

节点链路层采用IEEE802.11标准MAC协议DCF，节点的通信范围是250m。

网路模型由50个节点组成，移动范围为1500m×500m的矩行区域，移动模型使用random waypoint模型，节点移动速度在0—20m/s随机选择。

仿真时间是900s，仿真采用CBR流量源，以每秒 4 个的速率发送包，每个包的大小均为 64 字节，网络中有20个CBR源^[4]。

4.2 性能参数

(1)包传输率：目的节点正确接收到的分组个数与源节点产生分组数个数之比。

(2)平均端到端延时：从源节点产生数据包到目的节点接收到数据报的平均延时。

(3)归一化路由开销：每交付给目的节点一个数据分组所需要发送的路由分组的数量。

4.3 仿真结果

4.3.1 包传输率

图3 包传输率

从图3中可以看出，使用了链路缓存和新的生存时间估计方法后，协议的包传输率比路径缓存有所提高。原因是新的存储方法可以从回复信息中组合出更多的路由信息，当使用路径缓存找不到到目的节点的路由时，链路缓存可能会使用图的搜索算法找到至目的节点的路由。

4.3.2 平均端到端时延

图4 平均端到端延时

从图4可以看出，使用了链路缓存和新的链路生存时间估计方法后，端到端时延比原来有所下降。原因是节点在发送数据分组时，源节点往往可以找到最佳路由，从而避免了使用过期路由后再次重新选择路由进行发送的时间。同时新的方法能够及时删除过期路由，避免使用无效路由造成的时延。

4.3.3 归一化路由开销

图5 平均端到端时延

从图5可以看出，使用了链路缓存和新的链路生存时间估计方法后，路由开销有所降低，因为新的方法能够查找到更多的路由信息，避免不必要路由发现带来的巨大网络开销，并且新的方法能够及时删除过期路由。

5 结束语

缓存存储结构对按需路由性能影响很大，使用链路缓存能够更加充分利用节点所知的关于网络拓扑的信息。本文通过一种基于移动预测的方法来对缓存中链路的生存时间进行预测，以便及时地删除缓存中的过期路由信息，并且使用统计平均的方法来避免根据瞬时状态进行预测带来的偏差。仿真结果表明新的方法在包传输率、传输延时和路由开销等性能上都有改善。

参考文献

[1] 陈林星，曾 曦，曹 毅. 移动Ad Hoc网络[M]. 北京：电子工业出版社，2006.

[2] HU Y C， JOHNSON D B. Caching strategies in on-demand routing protocols for wireless ad hoc networks[A]. Proceedings of MobiCom 2000[C]. New York，USA，2000.

[3] MALTZ D， BROCH J， JETCHEVA J， et al. The effects of on-demand behavior in routing protocols for multi-hop wireless ad hoc networks[J]. IEEE Journal on Selected Areas in Communications， 1999， 17(3)：1439-1453.

[4] BROCH J， MALTZ D， JOHNSON D， et al. A performance comparison of multi-hop wireless ad hoc network routing protocols[A]. Proceedings of Fourth Annual ACM/IEEE International Conference on Mobile Computing and Networking[C]. New York，USA，1998.