基于AODV的Ad Hoc网络多路径路由协议

周 杰

（安徽电子信息职业技术学院 软件学院，安徽 蚌埠 233030）

0 引 言

Ad Hoc网络[1]是一种无中心，并具有高效、自组织性的移动通信网络，由于它具有多跳转发技术、支持动态变换的网络拓扑结构，以及抗毁性等特点，在事故突发现场、军事战术环境等领域被采用。然而，由于Ad Hoc网络的拓扑结构频繁地变化，使得传统的互联网路由协议不能在该网络使用，如ospf和rip。因而，Ad Hoc网络所采用的路由协议一直是研究重点。

其中，按需路由协议AODV[2]是Ad Hoc网络中一种极其重要的路由协议，它吸取了DSR[3]和DSDV[4]的优点，技术成熟，是 DSR与 DSDV的完美结合。它不必维护去往所有节点的路由，仅在没有去往目的节点路由的时候才按需进行路由发现，从而有效地节省了网络资源。

但是，使用AODV路由协议的Ad Hoc网络仍然有两个问题亟待解决[5]。其一，源节点仅维护一条到指定目的节点的单路径路由[6]，当因某种因素（转发节点位置移动）使得这条单路径路由失效，从而使源节点需要重新进行到达目的节点的路由发现过程，因此，在网络拓扑频繁变化的Ad Hoc网络中，这将会影响整个网络的传输性能。其二，源节点采用泛洪广播的方式发送RREQ报文来建立路由的发现过程，但不论中间节点还是目的节点都只对收到的第一个RREQ报文进行处理，发送RREP报文或建立反向路由，然而大部分其它后到达的RREQ报文会被节点没有利用地直接丢弃，从而浪费了Ad Hoc网络带宽。因此，针对AODV路由协议在这两方面存在的不足，文中对AODV路由协议进行了改进，形成了新的AODV路由协议，即多路径AODV 路由协议 （MultiPath AODV，MPAODV）。

1 MP－AODV路由协议的研究

通过对AODV路由协议两方面的改进和扩展，形成了MP－AODV路由协议。这两方面的改进分别为中间节点如何处理收到的RREQ报文和节点是如何选取不重复多路径路由的，下面进行具体介绍。

1.1 MP－AODV路由协议对RREQ报文的处理

在使用AODV路由协议的Ad Hoc网络中，当源节点需要和目的节点通信但无有效路径可用时，便启动路由发现过程，产生RREQ报文路由请求消息，并以泛洪方式在全网范围内广播，所以，多个相同RREQ报文（＜源节点序列号，RREQ ID＞相同）可能都会被中间节点收到。但是因为AODV路由协议是单路径路由协议，所以，中间节点只会处理第一个到达的RREQ报文，其它随后到达相同的RREQ报文直接就会被丢弃掉。这个中间节点处理RREQ报文的过程，使得有限的Ad Hoc网络带宽被浪费了。

然而，在 MP－AODV路由协议中，若中间节点在接收到多个相同的RREQ报文时，不会不做处理地丢弃掉这些相同的RREQ报文，而是让后到达的RREQ报文和第一到达的RREQ报文进行比较，从而决定是否丢弃后到达的RREQ报文。其过程为中间节点收到第一个RREQ报文时，会将报文中的跳数值这个参数保存在缓存中，并建立反向路由，接着把该RREQ报文转发给邻居节点。然而，该中间节点再次收到相同RREQ报文（＜源节点序列号，RREQ ID＞相同）时，它会比较这个RREQ报文中的跳数值和自己缓存中的跳数值，若小于或者等于自己缓存中的跳数值，则该中间节点会建立另外一个反向路由，并将该RREQ报文继续转发给它的相邻节点；若大于自己缓存中的跳数值，那么该节点会将该RREQ报文不做处理地丢弃掉。

一个包含5个节点的Ad Hoc网络如图1所示。

图1 一个包含5个节点的Ad Hoc网络

当前源节点S需要向目的节点D传输数据，但是源节点S的路由表中没有相关的路由，那么源节点S将启动路由的发现过程，并产生和广播RREQ报文。

在AODV路由协议中，节点处理RREQ报文的情况如图2所示。

图2 AODV路由协议，节点处理RREQ报文

中间节点c可以收到两个相同的分别来自节点S和节点a的RREQ报文，但是中间节点c只处理先到达来自节点S的RREQ报文来建立反向路由，然而后到达来自节点a的RREQ报文，会不被处理地被节点c丢弃掉。节点b和节点D同样也只处理最先到达的RREQ报文。

在MP－AODV路由协议中，节点处理RREQ报文的情况如图3所示。

图3 MP－AODV路由协议，节点处理RREQ报文

中间节点c可以收到两个相同的分别来自节点S和节点a的RREQ报文，然而节点c会将首先接收到的来自节点S的RREQ报文进行处理，将报文中跳数为1的值记录在自己的缓存中，中间节点c将会对后到达来自节点a的RREQ报文中的跳数值和自己缓存中的值进行比较后，决定该报文被丢弃，因为该报文中的跳数值为2大于中间节点c缓存中的值1。中间节点b可以收到两个相同的分别来自节点a和节点c的RREQ报文，因为这两个报文中跳数值都相同（都为2），所以，这两个RREQ报文不论谁先到达还是后到达，都不会被中间节点b丢弃。

1.2 MP－AODV路由协议中不重复多路路由的选取

在MP－AODV路由协议中，目的节点最终可以收到多条来自不同路径但相同的RREQ报文，若它根据这些报文形成多路径的反向路由，并向源节点发送RREP报文的话，最终源节点就会学习到多条到达目的节点的路由。但是这些路由的中间节点有可能出现重复，只有中间节点不重复[3]，才能保证Ad Hoc网络的稳定性。

在图3中，最终源节点S的路由表中存在3条去往目的节点D的路径，其分别为S→c→D，S→a→b→D，S→c→b→D，可以发现，这3条路径中，中间节点b和中间节点c重复属于不同路径，因而有可能因为其中某一节点的失效，造成该节点所连接的路径都失效，所以，这3条路径因为节点重复必将使Ad Hoc网络的稳定性受到影响。

为了使MP－AODV路由协议在路由发现的过程中，学习并形成节点不重复多路径路由，在原来的RREQ协议帧中新添加“路由记录列表”一项，形成新的RREQ协议帧。该帧中的“路由记录列表”记录RREQ报文从源节点到目的节点所经过的中间节点地址。也就是当RREQ报文传送到中间节点时，中间节点会把自己的地址添加到该帧的“路由记录列表”中，并转发。

新RREQ协议帧中的“路由记录列表”如图4所示。

图4 新RREQ协议帧中的“路由记录列表”

在图4中，当源节点S广播发送一个RREQ报文时，中间节点a和中间节点c接收到该报文后，若该报文有效，且该报文中的“路由记录列表”中没有自己节点地址，节点a和节点c会将自己的地址添加到“路由记录列表”中，接着该RREQ报文再转发给它的邻居，当中间节点b接收到该RREQ报文后，会采用相同的处理，在该RREQ报文的“路由记录列表”中添加上自己的地址，因而当该报文到达目的节点D时，目的节点D就可通过报文中“路由记录列表”中的值，得知从源节点到目的节点存在几条路径。

MP－AODV路由协议通过新的RREQ报文，发现节点不重复多路径路由非常容易，当目的节点接收到一个新RREQ报文到达时，若是第一个，目的节点会将该报文中的“路由记录列表”的值保存在自己的缓存中，同时，目的节点会按反向路由发送RREP报文。如果目的节点再次收到相同的新的RREQ报文时，会比较它的缓存中值和该报文中“路由记录列表”的值，以判断是否存在相同的节点 （源节点除外）。如果存在相同的节点，则丢弃掉该报文；如果不存在相同的节点，则将该报文中“路由记录列表”的值也保存在缓存中，同时，目的节点也会按反向路由发送RREP报文。

由图4可知，当路径为S→c→D的新RREQ报文最先到达目的节点D时，目的节点D将会把该报文中“路由记录列表”中的值S，c保存在自己的缓存中，并发送反向RREP报文，当目的节点D收到相同的RREQ报文，但路径为S→c→b→D时，会比较该报文“路由记录列表”和自己缓存中的值，比较后发现中间节点c重复了，所以目的节点会丢弃该RREQ报文。当第3个相同的RREQ报文到达目的节点D，但路径为S→a→b→D时，再次比较自己缓存中的值和该报文中“路由记录列表”中的值，比较后发现没有节点重复，此时目的节点D也会将该报文“路由记录列表”中的值S，a，b保存在自己的缓存中，并发送反向RREP报文。当这两条RREP报文到达源节点S后，源节点S就学习到，到达目的节点D存在两条节点不重复路由，如图5所示。

图5 不重复节点的多路径路由

2 仿真结果及分析

为了验证MP－AODV路由协议比AODV路由协议有效，使用NS2[8]模拟软件来仿真AODV和MP－AODV路由协议，仿真环境为一个包含50个移动节点的网络模型，各节点随机分布在1000m×1000m的矩形区域内，并在100m的模拟时间内，随机以最小为0m／s的速度，最大从0m／s到60m／s的速度向任意目的地移动，到达目的地后，停留时间为0s，然后继续随机地选择另一个节点移动。

2.1 数据报传输成功率的比较

通过模拟软件NS2对AODV和MP－AODV的仿真实验，将得到网络节点在不同速度下数据报传输成功率的数据，并绘制出折线图，如图6所示。

1）当节点移动速度小于35m／s时，网络节点之间的链路比较稳定，数据包很少丢失，所以，这两个路由协议的数据报传输成功率较接近且较高。

图6 两种路由协议的数据报传输成功率

2）当节点移动速度大于35m／s时，AODV的数据报传输成功率下降非常快，但MP－AODV的数据报传输成功率仍然维持较高水平（80%左右）。因而节点以比较快的速度移动时，网络拓扑结构会发生较大变化，从而容易造成源节点到目的节点失效的路由路径，传输过程中易出现数据包丢失。这个时候AODV中的源节点只能重新广播RREQ报文来学习新的路由路径。然而，此时在MP－AODV中源节点会启动备份路由来发送数据，无需学习新的路由路径。

2.2 平均延迟时间的比较

用同样的方法，最终将得到节点在不同速度下平均延迟时间的数据，并绘制出折线图，如图7所示。

图7 两种路由协议的平均延迟时间

1）当节点移动速度小于35m／s时，网络节点之间的链路比较稳定，所以两种路由协议的平均延迟时间都比较接近且值小。但AODV的平均的延迟时间有时会低于MP－AODV，出现这样的情况原因是MP－AODV的目的节点需要通过比较多个RREQ报文来决定是否发送RREP报文，而且源节点还通过接受到多条RREP报文来建立多条节点不重复路由，因此，花费时间要比AODV路由协议多。

2）当节点移动速度大于35m／s时，AODV的平均延迟时间会迅速增加，而MP－AODV的平均延迟时间增加缓慢。这是因为当网络节点以较快速度移动时，Ad Hoc网络拓扑结构会较大变化，容易造成源节点到目的节点的路由失效，传输的数据包也容易丢失。此时AODV中的源节点只能重新广播RREQ请求报文，以便学习到新的路由。但是，在MP－AODV协议中源节点会启动备份路由来发送数据，无需学习新的路由路径。

3 结 语

Ad Hoc网络因组网灵活简便、生存能力强，所以具有极其广泛的应用前景，同时其路由协议一直是研究的重点。文中针对Ad Hoc网络中典型路由协议AODV存在的问题，对其进行改进，提出了MP－AODV路由协议。通过NS－2软件的仿真结果表明，在网络节点以较大速度移动时，MP－AODV路由协议的数据报传输成功率和平均延迟都比AODV路由协议有所提高，从而使Ad Hoc网络数据传输效率得到提高。

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

[2]Perkins C，Belding－Royer，Das S.Ad hoc On－demand Distance Vector（AODV）Routing[EB／OL].RFC 3561.[2003－05－10]http：／／www.ietf.org／rfc／rfc3561.txt：July.

[3]王申涛，杨浩，周熙，等.Ad Hoc网络DSR路由协议仿真性能分析[J].无线电通信技术，2006（5）：54－65.

[4]Perkins C E，Bhagwat P.Highly dynamic Ddestination－Sequenced Ddistance－Vector Routing （DSDV）for mobile computers[C]／／ Processing of SIGCOMM’94，ACM SIGCOMM’94Communications Architectures.New York：ACM Press.，1994.

[5]毛靖添，马光胜，李洪升.基于AODV动态自适应多路径路由[J].长春工业大学学报：自然科学版，2006，27（2）：75－79.

[6]朱彦松，万润泽，罗飞，等.Ad hoc网络单路径路由算法的比较研究[J].计算机与数字工程，2007，（8）：101－110.

[7]Gou Yiao－Feng，Chen Yue－Quan.An aggregated multipath routing scheme for Ad Hoc networks[J].Jounral of Software，2004，15（4）：594－603.

[8]徐雷鸣，庞博，赵耀.NS与网络模拟[M].北京：人民邮电出版社，2003.