摘  要： AODV路由协议每次在源节点只建立一条通向目的节点的路由，未能充分利用从中间节点或者目的节点返回的路由应答信息，针对这一问题，提出了一个改进的方法。在源节点处建立一条主路由的基础上，利用路由应答信息，建立一条备份路由，并且每次将最优的设为主路由，次优的设为备份路由。仿真结果表明，改进的协议和原协议相比，降低了端到端的延时，提高了包投递率

　　关键词： Ad Hoc网络；路由协议；AODV协议；备份路由

　　移动自组织网络MANET（Mobile Ad Hoc Network）是一种移动、自组织的系统。MANET是对等网络，每个节点既可以作为主机，也可以作为路由器，数据包通过网络进行逐跳转发。由于它组网灵活、不依赖于现有的网络基础设施，在军事和紧急救援领域应用前景十分广阔。目前Ad Hoc网络的路由协议可分为3大类，表驱动路由协议有OLSR、WRP、DSDV[1]，按需路由协议有AODV[2]、DSR，基于约束的路由协议有ABR、LAR。

　　AODV是一种按需路由协议，并已经成为IETF的标准化路由协议。它的主要特点是使用序列号来表示一条路由的新旧程度，同时用来避免出现路由环路，AODV主要有路由发现和路由维护两个过程。

　　本文针对AODV路由协议出现链路断开时只能通过本地修复机制来进行链路修复的不足，利用从中间节点或者目的节点返回的路由应答信息，在建立一条主路由的基础上，再建立一条备份路由，并且每次将最优的设为主路由，次优的设为备份路由，使得出现链路断开的上游节点能够利用备份路由进行数据的传输，有效地降低了时延和提高了分组投递率，通过仿真软件NS2验证了改进后的协议具有更好的性能。

1 AODV路由协议概述

　　1.1 路由发现过程

　　当源节点要向目的节点发送数据时，创建一个路由请求包RREQ，并向邻居节点进行广播，进行泛洪路由发现过程[3]。

　　中间节点收到路由请求之后，首先根据RREQ中的广播号判断是否是已经处理过的RREQ，如果是，则丢弃；如果是新收到的RREQ，就建立或者更新到源节点的反向路由，使得反向路由表中到源节点的路由序列号大于RREQ中的序列号或者序列号相同并且有更少的跳数。然后查找路由表，如果没有到目的节点的积极路由，就继续广播RREQ，如果有到目的节点的积极路由，并且路由中的目标节点序列号大于或者等于RREQ中的序列号，就沿着反向路由向源节点单播路由应答RREP。

　　目的节点收到RREQ后，不再广播，建立反向路由，产生一个含有最新序列号的路由应答RREP，沿反向路由向源节点单播。中间节点收到RREP后，建立到目的节点的正向路由，并更新路由信息。源节点收到RREP后，建立到目的节点的正向路由，并开始向目的节点传输数据。

　　路由发现过程如图1所示。如果节点S需要对节点D进行通信，节点S没有到节点D的积极路由，节点S广播一个路由请求RREQ。节点1收到RREQ，假设其没有到节点D的积极路由，节点1会继续广播此RREQ。假设节点2中有一条到达目的节点D的积极路由，节点3和节点4中没有到节点D的积极路由。最终节点S将会先后收到由节点2和节点D分别发送的包含S-1-2-D和S-3-4-D的路由应答RREP，由于节点D发送的RREP具有更高的序列号，所以路由S-1-2-D将被丢弃，即使这条路由也是有效的。这样当节点S与节点3链路断开，节点S进行链路失效处理时就无法使用路由S-1-2-D，而可能进行局部修复，从而造成了延时。设想如果能将S-1-2-D路由作为备份加以保留，那么在S-3-4-D路由断裂时，就可以转换到使用备份路由上来。

　　1.2 路由维护

　　路由维护[4]可以及时发现节点因移动或其他原因而引起的链路断开，每个包含路由的节点，周期地广播HELLO消息，并且TTL值为1，因此只能与其相邻节点传播。一个节点收到HELLO消息便知道自己与邻节点保持连接，如果在一定时间内收不到HELLO消息，则进行链路失效的处理。如果链路断开处离目的节点较近，将进行链路的局部修复，即由链路断开处的上游节点发起到目的节点的路由发现过程。如果在给定的时间内重新建立起有效的路由，就继续发送数据；如果未能成功建立，则向上游发送RERR。如果链路断开处离目的节点较远，则不进行局部修复，直接将路由设为失效状态，并向上游发送RERR。设想如果有一条备份路由存在于链路断开处离目的节点较远的地方，就可以直接使用备份路由而不必进行泛洪路由发现过程。

2 基于备份路由的改进方法

　　对AODV路由协议的分析表明，源节点接收到路由应答RREP后，将序列号最大或者序列号相同且有较少的跳数作为判据，因此只保留了一条到目的节点的路由，如果这条路由失效，就会重新发起路由发现过程，从而增大了网络的开销。为了充分利用源节点接收到的路由应答信息，同时又能避免路由环路的出现[5]，对AODV协议作了改进。

　　在路由表项中添加标记主路由或备份路由的主/备份标志位，并且初始化为0，表示主路由（1表示备份路由），在链路未出现断开的情况下，均默认使用主路由。

　　为了能够实现添加备份路由的功能，对源节点接收到RREP的处理过程作了修改，如图2所示。在路由发现过程中，源节点接收到RREP后建立主路由。如果接收到的RREP的序列号比存在的到该目的节点的主路由序列号大，或者序列号相同但是有更少的跳数，并且是第一次接收到RREP的话，更新主路由。如果不是第一次接收到RREP并且没有备份路由，则更改原来主路由的标志位，设为备份路由，添加新的主路由并更新；如果有备份路由，更改原来主路由中的标志位，设为备份路由，更改原来备份路由中的标志位，设为主路由并更新。

　　如果源节点接收到的RREP的序列号没有比存在的到目的节点的主路由序列号大，或者序列号相同但是没有更少的跳数，而且没有备份路由，则添加此RREP序列号对应的路由为备份路由；如果存在备份路由，并且现接收序列号比备份路由序列号大，或者序列号相同但是有更少的跳数，则更新备份路由，否则丢弃RREP。

　　这样通过以上过程，就能使得每次在路由发现过程以及可能的修复过程中建立两条路由，而且主路由和备份路由是最优的两条路由，同时主路由优于备份路由。如图1所示，通过改进的方法，在与之前相同的情况下，节点S与节点D之间便建立了一条主路由S-3-4-D和一条备份路由S-1-2-D。在整个网络的路由发现过程中，除了前述改进方法中源节点通过接收到的RREP建立备份路由时要查找本地路由表中是否有到目的节点的备份路由外，其他的节点均只查找本地路由表中是否有到目的节点的主路由，从而保证了优先使用主路由。

　　在路由维护阶段，如图3所示，如果节点S要向节点D传输数据，在建立的主路由S-1-4-5-D中，节点1和节点4之间发生链路中断，这时，节点1要对链路断开进行处理。如果之前节点1向节点D传输过数据，并且通过本文前述改进的方法在路由发现过程中建立了备份路由1-2-3-D（节点1曾经担任过源节点），且该备份路由有效，则节点1使用备份路由发送数据，从而减少了延时，提高了分组的投递率；如果该备份路由已经失效，则进行与原AODV协议相同的操作。

3 仿真环境和结果

　　用仿真软件NS2进行了模拟实验[6]，网络拓扑结构是一个包含50个移动节点的网络模型，各节点随机分布在1 000 m×300 m的平面矩形区域内，并随机地以均匀分布在0~20 m/s之间的速度向区域内任意目的地移动，到达目的地后停留一段时间，然后再随机地选择一个目的地移动，如此反复，直到模拟结束。总模拟时间为300 s，若停留时间为0，则节点到达目的地后不停留，若停留时间为300 s，则节点静止。每个节点的数据速率为1 Mb/s，MAC层协议采用IEEE 802.11，采用CBR业务类型，CBR流的个数为10。

　　端到端的延时是指一个数据分组从源节点的IP层到目的节点的IP层所需要的平均时间，从图4中可以看到两种协议的平均端到端延时随着节点暂停时间的增加都在减小，但是，新协议的端到端延时比原协议更小。

　　分组投递率是目的节点应用层接收到的分组数与源节点发送的分组数之比，从图5中可以看到两种协议的分组投递率随着节点暂停时间的增加都在增加，但是新协议有更高的分组投递率。

　　本文对AODV路由协议进行了分析，针对AODV路由发现过程中源节点未能充分利用路由应答的问题进行了改进，建立备份路由，并通过改进主路由和备份路由的选择机制，使得当链路断开时，链路断开处的上游节点可以使用备份路由发送数据，尽管在建立备份路由的过程中占用一定的时间和资源，但仿真结果明显表明，其减少了端到端的时延和提高了分组投递率。

　　参考文献

　　[1] PERKINS C， BHAGWAT P. Highly dynamic destination sequenced distance vector(DSDV）routing for mobile compu-ters[C]. Proceedings of ACMSIGCOMM′94， 1994：234-244.

　　[2] PERKINS C， ROYER E. RFC 3561 Ad-hoc on-demand distance vector（AODV） routing[S]. 2003-07.

　　[3] 高兴国，王汉星，胡细.一个优化的AODV路由协议[J].计算机工程与应用，2007，43（3）：128-130.

　　[4] 肖百龙，郭伟，刘军，等.AODV的本地修复算法[J].计算机应用研究，2007，24（3）：231-237.

　　[5] 李世宝，洪利.基于邻居缓存的AODV路由协议[J].计算机应用，2011，31（7）：1931-1943.

　　[6] 马崇霄，吴长奇.基于网络仿真器NS2的Ad hoc网络路由协议仿真[J].电子测量技术，2008，31（5）：75-79.