多跳无线Ad Hoc网络中AODV路由协议的改进研究

开篇：润墨网以专业的文秘视角，为您筛选了一篇多跳无线Ad Hoc网络中AODV路由协议的改进研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：本文提出了一种E-AODV，对AODV做了两大改进：设计了一种邻节点发现程序（NDP），该程序为AODV设计而独立于AODV，可以被移植到其他路由协议中，它为路由协议提供了一种检测链路状态和邻节点发现的底层支持，并避免了单向链路和不稳定链路的产生。基于NS的仿真结果显示，E-AODV在增加分组开销不大的情况下，分组投递延时和分组递交率均有了明显的提高。

关键词：Ad hoc AODV NDP

中图分类号：TN929.5；TP212.9 文献标识码：A 文章编号：1007-9416（2013）03-0048-03

1 AODV存在的问题分析

多跳无线ad hoc网络是由一组带有无线收发装置的移动终端节点组成的一个多跳的临时性的自治系统。由于网络中节点的移动，网络拓扑会不断的变化，因此传输数据的路由也会随着不断的重建或者更新，因此，路由协议的设计是Ad Hoc网络最具有挑战性的问题之一[1]。aodv（Ad-hoc On-demand Distance Vector）[2][3]是多跳无线Ad Hoc网络中最经典和最广泛被研究的按需驱动路由协议之一，它允许移动终端很快的获得许多路径到达它所想要到达的目的地，而且并不要求这些移动终端在没有激活的通信业务的时候去维护这些到目的端的路径。

1.1 单向链路的处理

AODV协议主要用于建立双向链路进行通信，但是由于无线电波的传输特性，单向链路是必然存在的。在路由过程中必须尽量避免使用单向链路，在AODV协议处理RREQ消息的过程中，在逻辑上存在一个问题：假设在一个由A、B和C 三个节点并排组成的Ad Hoc网络，当节点B接收到源节点A产生的RREQ消息时，实际存在的是源节点A到节点B的链路，但是节点B在路由表中建立的链路是节点B到源节点A的链路，如果源节点A和节点B之间是双向链路，那么不存在任何问题，但是如果二者之间的链路是单向链路，一旦这条链路被扩散开，则必然会导致网络资源的浪费，因为这条链路实际上无法到达节点A。原协议提到此时可以再由B发起路由请求，建立到A的路由。这种方法不是很合适，因为在发现之前网络资源已经浪费一部分，再建立新的路由必然会对网络延时产生较大影响。如果在建立链路时加入一些简单的限制条件，以避免单向链路的产生，就可以避免上述情况。

为了达到此目的，为每个节点设置一个邻节点表，记录自己所有的一跳可达邻节点，当收到来自某个邻节点的RREQ时，首先查邻居节点表，看该邻节点在邻节点表中是否有效，如果无效，直接丢弃RREQ；如果有效，按照原协议进行相关操作。这样，可以很大程度的避免了单向链路的产生。

为了保证邻节点表的有效性，本文设计了一个邻节点发现程序（Neighbor Discovery Procedure，标记为NDP），该邻节点发现程序的的功能是使每个节点迅速的检测到所有的邻节点，并避免使用单向链路和不稳定链路。它的最大特点就是使用一种改进的HELLO消息机制来发现邻节点，并能避免单向链路的使用。

1.2 静态链路和瞬态链路

假设存在如下情况：Ad Hoc网络种的节点比较密集，有某一个节点以相对比较快的速度在网络中到处移动，如果这个节点出现在源节点到目标节点的路由中，将导致至少一个RREP消息被抛弃，或者产生至少一条RERR消息，这事对网络资源的极大浪费。因为该节点的移动速度快，导致它和邻节点之间的链路都是暂时性的，依据AODV协议的生存处理，在路由表中这类未过期路由实际上已经断开了。所以必须找到新的处理方法来解决这个问题。本文引入了静态链路和瞬态的概念，有效解决了这个问题。

静止或者缓慢移动的节点之间的链接可以认为是连续存在的，称为静态链路。快速移动节点之间的链路存在时间较短，称为瞬态链路。寻路过程中，应尽量使用静态链路以避免因网络拓扑结构的改变而导致链路断开。考虑到Ad Hoc网络拓扑结构的无法预知性，不可能准确判断某个链路是静态还是瞬态的。但是可以通过制定一些规则，来估计某个节点在下一个时刻消失的概率。根据一般的状态，可以认为一个刚刚建立起来的链接相对于已经存在了一段时间的链路更容易断开。因此，刚建立的链路称为瞬态链路，存在一段时间后（可以由实验得到一个门限值），变为静态链接。假如属于 {|是一个静态链接，}。内的节点称为的静态链接。的节点称为瞬态邻节点。当在本文中，将态链路和瞬态链路的判断工作放在NDP中处理，具体做法是在节点收到来自邻节点的消息若干次时，才标记为可用链路。AODV通过查询由NDP提供的邻节点表来建立链路。

2 邻节点发现程序（NDP）

2.1 邻节点发现程序概述

邻节点发现程序（NDP）具有以下特点：

（1）采用了三种HELLO消息类型：邻节点请求HELLO消息（NRH），邻节点响应HELLO消息（NAH），广播HELLO消息（BH）。

（2）为了减少引入HELLO消息带来的路由开销，根据Ad Hoc网络的原理，引入了一种优化策略，在不影响性能的情况下最大限度的减少HELLO消息的数量。

（3）为了使该程序能够为路由协议使用，每个节点都维护一个邻节点表。

（4）NDP不仅仅为AODV路由协议而设计，它是完全独立与AODV协议的。它可以被移植到其他协议中去。

邻节点表如表1所示，其中，邻节点ID是邻节点号；链路状态有四种：暂时、单向、双向和断路；当节点首次收到邻节点的任何HELLO分组时，首先都设置为暂时，表示与邻节点存在目前还不确定是否稳定的链路，单向链路表示存在从邻节点到本节点的单向稳定链路，双向链路表示链路正常，可供路由；生存时间在链路状态为双向时为链路的存在时间，记为时钟1，当时钟过期时触发NRH，在链路状态为断路时为等待NAH的时间，记为时钟2。节点序列号为最近收到邻节点的序列号。HELLO消息次数在链路状态为暂时用来为链路状态从瞬态到静态的阀门；在链路状态为单向时为对该节点还可重传HELLO消息的次数，初设值实际就是允许HELLO消息最大的失败次数；在链路状态为断开时，为允许NRH失败的最大次数（MAX_NRH_NBR）。

HELLO消息的格式如表2所示：类型分为NRH、NAH和BH。序列号是该HELLO消息的当前序列号，每次发送一个HELLO消息，该值都增一。本节点ID为发送该HELLO消息的节点号；邻节点ID给出了需要对该HELLO消息处理的邻节点。BH是节点在一个HELLO_INTEVERAL时间内没有收到任何其他分组情况下而发送的。

2.2 发送HELLO消息

所有节点在HELLO_INTERVAL时间内必须向邻节点发送一种HELLO消息。为了避免HELLO消息发送同步，造成物理层碰撞，所有节点不能以相同的HELLO_INTERVAL发送HELLO消息。为了达到此目的，这里的做法是设置HELLO_INTERVAL为：HELLO_INTERVAL+D，这里D为一个在[0，MAX_D]中随机变化的偏移量。为了防止无效的HELLO消息而引起错误的链路，每次发送任何一种HELLO消息时，节点的当前HELLO消息序列号都增一。HELLO消息的发送很大程度取决于邻节点表的内容。

节点刚入网时，邻节点表为空，节点首先侦听信道两个HELLO_INTERVAL，如果没有收到任何HELLO消息，则发送BH，如果连续几次（HELLO_MAX_NBR）没有收到任何NRH，则表示该节点独立于网络。继续侦听信道，按照此过程执行。

2.3 接收HELLO消息

由于Ad Hoc网络是基于同频共享信道时分收发分配技术的，因此当某节点处于有效发送时，其相邻节点（即在无线传输覆盖范围的其他节点） 都能够接收或侦听到该发送信息。一般协议中，节点仅对发送给自己的信息以及广播消息分析处理，而丢弃其他相邻节点间的交换信息，尽管其已被正确收到。依据无线传输互易性原理，这些被丢弃的信息实际也表示了该节点与相邻信息发送节点间无线传输链路有效联通的内在含义，因此可将这部分信息充分利用到协议中，以提高协议效率，尤其在网络无线带宽与业务负载矛盾突出的情况下将更加显著。

根据此原理，所有能收到邻节点的任何一种HELLO消息的邻节点，都至少表示该链路单向存在；如果规定节点在设定的时间间隔内需要发送HELLO分组，而当节点在几个时间间隔内都没有收到邻节点的任何HELLO分组，则表示该邻节点已经断路或者变成单向。

2.4 本地链路修复

当链路状态由双向变为断路时，NDP并不立即删除此项，而是首先做修复尝试。如果修复尝不成功，再删除链路，并向路由层发出断路通知。

3 仿真分析

笔者的研究工作全部是在一台PC机（2.4GHZ四核，2G RAM）上完成，使用的操作系统是Red Hat Linux 9.0，模拟平台是NS2.35（Network Simulator Version 2.35）[4]。模拟的基本方法是改变网络的场景平均移动速度，分别看各种路由协议的性能变化。模拟中，移动模式采用移动因子[5]，其他参数的设置如表3所示，AODV协议参数如表4所示。

在以上仿真环境中，笔者做了四种版本的AODV协议仿真：路由层使用HELLO消息（AODV-H）；依据MAC的消息来判断链路状态，路由层不再发送HELLO（AODV-M）；路由层和MAC层都发送（AODV-M-H）；引入NDP（E-AODV）。仿真结果如图1所示。

具有链路状态检测或者邻节点发现的底层支持的路由协议性能更稳定，如采用邻节点发现程序的AODV、借助MAC消息同时又发送HELLO消息的AODV，即使在网络拓扑变化非常剧烈的时候，它们的分组递交率仍然稳定在95%以上，其中采用邻节点发现程序的AODV在控制分组开销增加不大的情况下，相比其他版本，分组平均延时和分组递交率两个性能上都有了比较明显的提高；而依赖于周期性的广播分组来检测链路状态的路由协议性能较低，如仅使用HELLO消息的AODV，在网络拓扑变化剧烈时，分组递交率仅仅在50%左右。

4 结语

本文对AODV路由协议进行了分析，针对AODV协议中单向链路和RERR消息丢弃的问题，设计了一种邻节点发现规程。改进的路由协议在不明显增加分组开销的情况下，分组投递延时和分组递交率均有了明显的提高。

参考文献

[1]Chlamtac I，Conti M，Liu J.Mobile ad hoc networking：imperatives and challenges[J].Ad hoc Networks，2003，1（1）：13-64.

[2]C.E.Perkins and E.M.Royer，”Ad-Hoc On-Demand Distance Vector Routing，” Proceed -ings of 2nd IEEE Workshop on Mobile Computing Systems and Applications， pp .90-100，February 1999.

[3]Perkins C E，Belding-Royeret，S.Das.“Ad Hoc On-Demand Distance Vector（AODV）”，Internet-Draft， rfc3561.txt， July 2003.

[4]The Network Simulator（ns-2） http：//www.isi.edu/nsnam/ns/

[5]何海浪，孙献璞，马龙.多跳无线Ad hoc网络路由协议的模拟和性能比较[J].电子科技，2005（03）.