梁龙，姚金杰

（中北大学 信息探测与处理技术研究所 山西 太原030051）

0 引言

本文在AODV的基础上，提出一种新的双径路由改进方案。数据可以在一条路径失效的情况下，通过备用路径继续传输。有效的降低了路由发现次数，减小了路由开销，提高了网络的健壮性，增强了网络对拓扑变化的适应能力。

1 AODV算法

1.1 路由发现过程

当有数据需要发送时，源节点首先广播一个携带目的节点信息的路由分组（RREQ），其邻居节点依次向周围节点广播此路由分组，广播RREQ前会建立此节点到源节点的路由，直到路由分组到达目的节点或者一个包含到目的节点路由信息的中间节点，就不再广播RREQ。此过程中，会建立一个从目的节点到源节点的反向路由，然后该节点将沿着反向路由发回一个RREP，RREP到达源节点后路由发现过程结束。为避免路由循环，每一个路由分组中都包含一个sequence ID(SID)作为唯一标志，如果一个节点收到一个SID比它当前保留的SID小的数据包，表明该数据包是过时的，它将不予处理，而是简单的丢弃。发现多跳路由时，源节点会选择一条SID大、跳数少的最优路由[3]。

1.2 路由维护过程

由于节点移动等导致链路断开，其邻居节点发现链路失效并向上游节点发送链路失效消息（RERR），一直传到源节点，然后源节点重新发起路由发现，或者也可以由发现链路失效的节点发起路由发现。只要路由是活动的，路由表就要一直维护下去。如果链路上不再有数据包传递，一段时间之后，链路就会过期，最终路由信息将从中间节点的路由表中删除 。

2 AODV存在的问题

由以上AODV的工作过程中可以看出，AODV中路由表仅维护一条到指定目的节点的路由，当某条路由失效时，源节点需重新发起路由发现过程。而在Ad Hoc网络中由于节点的高移动性和无线链路的不稳定性，网络拓扑在不断变化，造成链路的频繁失效，这样网络就会频繁地启动路由发现过程，会带来大量的路由负载，从而增加了网络的负荷[4]。又节点的路由发现机制采用泛洪式，而在路由回复时只有最早收到请求的节点提供路由回复，这样，很大一部分请求发送时占用的路由资源就白白浪费了[5]。

3 AODV路由协议的改进

3.1 对路由发现的改进

如1.1中介绍，在路由发现过程中，当源节点向邻节点广播RREQ时，RREQ包会被很多节点收到并转发，但是只有一个RREP回复给源节点，这样广播的时候所占用的资源没有得到利用，浪费了很多的路由资源。本文提出在目的节点收到RREQ后，按不同的路径回复两个应答信息RREP。对于有到目的节点有效路由的中间节点收到RREQ后，只要有一个中间节点回复RREP给源节点即可。这样就意味着，源节点可以收到至少两个到目的节点的RREP。改进后算法在源节点保存最先到达的两个RREP中的路由，然后存储到路由表中。最先到达的RREP里保存的路由作为源节点发送数据给目的节点的主路由。第二个到达的RREP里保存的路由作为备用路由。如果主路由失效，源节点可以不必发起路由请求，直接调用备用路由即可。改进后的双径路由模型如图1所示。

图1 双径路由模型

3.2 对路由维护的改进

如1.2中介绍，由于节点的移动性，网络的拓扑结构也发生相应的变化。如果移动的节点不是要使用的路由上的节点，则不做任何处理。如果源节点移动，则可以重新发起路由发现过程查找新的路由。当目的节点或中间节点移动时，发送一个RERR消息给源节点。如果下一跳无法到达，则由上一跳节点发送RERR消息，包含新的序列号并设置跳数为无穷大。节点收到RERR消息以后，将路由表中相应的路由设置为无效，并采用相同的方式继续传播RERR消息。源节点收到RERR消息后，可以采用备用路由发送数据。如果没有备用路由，将重新启动路由发现过程。

4 仿真结果及性能分析

仿真实验使用NS-2网络仿真工具，版本为2.30，仿真环境为Cygin。仿真场景设置如下：30个节点随机会分布在1000m×1000m的正方形区域内；MAC层协议采用IEEE802.11；无线电传播模型为TwoRayGround；天线模型为全向天线；使用CBR作为数据业务流，数据包大小为1000字节。本仿真中设置一对特定的数据流业务。根据运动模型，每个节点随机地向一个目的地移动，平均移动速度为10m/s，仿真时间为100s。所有仿真结果均为多次实验的平均值。用NS2自带的动画演示工具nam可以演示整个仿真过程，某时刻仿真场景如图2所示。

图2 nam演示的仿真场景图

4.1 时延分析

端到端时延是指分组从源节点发送到达目的节点所经历的时间间隔，从图3可以看出，在使用了改进算法以后，分组的时延有一定程度的减小。这是由于改进后的协议采用双路由的策略，这样当一条路由失效后，可以从源节点找到另一条备用路由，就不需要源节点重新广播来寻找新的路由，所以端到端的延迟减小了。 (图中aodvg为改进后的算法)

4.2 数据包丢失分析

数据包在传送过程中要发生丢失现象，由发送数据包总数减去接收到的数据包总数所得。数据包丢失越少说明网络的传输效率越高。由图4可看出，改进后的算法比原算法数据包丢失数目有一定程度的的减小。这是由于在节点移动时，原算法由于链路断开而重新泛洪请求时，信息大部分来自于邻居节点而无法获得最新的网络信息，导致丢包数增加。而改进后的算法在链路断开时，可改用备选路径，迅速建立链接。因此丢包数会较原协议减少[6]。

图3 aodv与aodvg的时延比较

图4 aodv与aodvg的数据包丢失比较

4.3 吞吐量分析

吞吐量由所接收的封包大小总和除以所花费的时间得到。由图5可以看到改进后的算法较原算法吞吐量量有一定的增加。由4.1和4.2的分析可容易得出，延时减小，数据包丢失减少，吞吐量得到提升。

图5 aodv与aodvg的吞吐量比较

5 结论和未来工作

针对AODV路由协议中对路由发现和路由维护存在的不足，本文提出一种新的Ad Hoc双路径路由机制。这种路由机制通过在源节点和目的节点之间建立两条路径来增强路由的健壮性，通过模拟测试显示，该算法在端到端时延、 数据包丢失、 吞吐量等方面有较好的改善。但是针对Ad Hoc网络的具体现实情况，如何将这些算法应用到实际当中去，这是一个值得探讨的问题，也是以后工作的重点。

[1]米志超,郑少仁.Ad hoc网络技术讲座[J].中国数据通信，2003，32（12）：84-85.

[2]李国强,武穆清.Ad Hoc网络中一种新的多径路由机制研究[J].信息传输与接入技术，2008，34 （1）：22-24.

[3]Multi-path Routing in wireless Ad hoc networks[C].Proceedings of IEEE Local Computer Networks(LCN),2004(11),19-20.

[4]方路平,刘世华.NS-2网络模拟基础与应用[M].北京：国防工业出版社,2008：147-148.

[5]杨少雯.基于NS2的无线自组网路由协议研究[D].哈尔滨：哈尔滨理工大学电气与电子工程学院,2007：28-36.

[6]陈跃泉,郭晓峰.基于网络最大流的Ad-Hoc多路径路由算法[J].电子学报,2004,32（8）：1329-1300.