AODV路由协议研究

AODV路由协议研究（共8篇）

AODV路由协议研究 篇1

0 引言

Ad Hoc网络是复杂的分布式网络系统, 是自组织、自愈网络, 由无线移动节点组成, 节点间的路由通常由多跳组成, 由于移动节点的无线传输范围有限, 两个无法直接通信的节点需要通过多个中间节点的转发来实现通信[1]。Ad Hoc网络不需要通信线路并且摆脱了固定基础设施的束缚, 目前是一个研究热点。

本文旨在研究Ad Hoc网络典型的AODV路由协议, 实现RREQ泛洪攻击方法, 并且利用NS软件进行了仿真实验, 最终的实验数据证明攻击方法十分有效。

1 针对AODV路由协议的RREQ泛洪攻击方法

1.1 AODV路由协议

AODV全称是Ad Hoc按需距离矢量路由协议, 该协议有3种基本的协议控制消息:路由请求 (Route Request, RREQ) 、路由应答 (Route Reply, RREP) 和路由错误 (Route Error, RERR) [2]。路由查找建立的过程主要用到RREQ和RREP两种消息。RREQ消息通过广播来传递, 但是广播会消耗大量的网络资源。AODV路由协议 (以下称路由协议) 通过以下措施来控制RREQ消息的频率与范围, 从而降低RREQ消息消耗网络资源的程度: (1) 路由协议设置了一个最大发送频率数, 限制任何节点发送的RREQ消息数在一秒内不能超过这个数值; (2) 路由协议设置了一个RREQ消息查询往返时间, 节点在广播RREQ消息后, 如果通过RREQ消息查询往返时间内没有收到RREP消息, 则在等待两倍的RREQ消息查询往返时间后, 才能再次发送RREQ消息; (3) RREQ消息广播范围有限制, 开始时先在小范围内广播, 再依次增加广播的范围, 直到路由查找成功或者放弃查找路由, 这些由RREQ消息中的TTL域 (time-to-live) 来进行控制。

源节点发送RREQ消息流程如图1所示。

1.2 泛洪攻击实现步骤

泛洪攻击方法打破了上述方式, 通过故意违反这些规定, 使恶意节点消耗大量网络资源。攻击过程分成两个步骤。

(1) 恶意节点设置路由查询的目标地址。假如知道了网络中所有的节点地址, 它就设置网络内不存在的IP地址作为目标节点地址;假如恶意节点不了解网络中的节点地址范围, 它就设置一些随机的IP地址作为目标节点地址, 这样的话正常节点就不应答, 每个收到RREQ消息的节点就需要暂存RREQ信息, 并且建立反向路由, 这些信息一直到超时后才能删除。这样一来, 垃圾信息就会长时间存放在网络的正常节点中, 从而达到占用网络可用资源的目的。

(2) 恶意节点把前一步设置好的IP地址加入到RREQ消息中, 持续发送一定强度的RREQ消息, 忽视路由协议规定的RREQ消息发送频率数, 并且忽视路由协议规定的查询往返时间限制, 持续不间断地发送RREQ消息, 直接将RREQ消息的路由查找范围定义为最大。

恶意节点的泛洪攻击首先会占用本就有限的网络带宽, 因为网络中会充斥恶意节点发送的大量RREQ消息;其次会占用网络中每一个正常节点宝贵的存储资源, 因为每一个RREQ消息中的源节点地址信息、目的节点地址信息、上游节点地址信息、目的序列号信息以及因此建立的反向路由信息都会被正常节点存储, 这些信息的释放要等待节点收到RREP消息或超时。因为不可能有RREP消息到达, 而RREQ消息又源源不断地到来, 正常节点有限的存储资源就会消耗殆尽。这时, 正常节点路由查找的信息会得不到处理, 正常的路由也无法建立。因此, 当恶意节点进行RREQ泛洪攻击时, 网络性能会明显下降。图2是一个RREQ泛洪攻击的例子, 恶意节点F发送泛洪攻击, 正常节点收到RREQ消息后广播该消息, 导致网络充斥RREQ消息, 网络逐渐瘫痪。

2 仿真实验

2.1 实验环境及参数设定

本文在路由协议编程中添加了RREQ泛洪攻击过程。仿真实验时, 该方法由恶意节点调用。仿真使用的操作系统是Red Hat Linux9.0, 计算机中央处理器参数为Pentium 2.5Ghz, 内存为512MB, 网络模拟程序是NS-2, 版本为2.30。

MAC层协议采用IEEE802.11DCF, 正常节点向相邻节点发送单播消息时使用RTS/CTS控制分组, 减少“隐藏节点”使用“虚载波侦听”和信道预留来实现。采用CSMA/CA协议和使用物理载波侦听来发送RTS和广播分组。节点的相关参数如下:250m无线广播范围, 2Mbps通信带宽, 20个分组的节点存储区。业务分组为CBR分组, 每秒钟发送两个CBR分组。从实验开始到80s之间, 逐渐增加要发送的数据分组移动节点, 也就是增加网络中的数据分组流。

仿真区域为800m×800m的正方形, 40个移动的正常节点分散在其中, 恶意节点在实验开始后加入。节点在仿真区域内以随机的方向和随机的速度移动, 运动期间会停留一定的时间。实验时间为100s, 采用NAM动画演示仿真实验过程。

仿真结束后, 使用GAWK工具 (一种方便而强大的资料处理分析工具) 统计分析产生的TRACE文件数据, 计算出数据分组递交率 (Ratio, 目的节点接收到的分组数/源节点发送的分组数) 以及网络延迟 (Delay, 分组从源节点到达目的节点所用的时间) 等数据。数据分组递交率以及网络延迟是衡量网络性能的重要参数[3]。分组递交率是指网络中目标节点接收到的分组数与源节点发出的数据分组之间的比值, 它可以反映出网络吞吐量以及数据分组的丢失情况, 通过这个数据可以看出网络是否正常运行。网络延迟是指分组从源节点传送到目的节点经历的时间, 它反映出网络的性能情况。

2.2 仿真结果

本文进行了3组RREQ泛洪攻击仿真实验[4], 分别是没有攻击分组、30个/s攻击分组、50个/s攻击分组。

为了详细地分析实验过程, 实验中每10s统计一次, 计算出分组递交率和网络平均延迟, 3种情况下各阶段的分组递交率和网络延迟结果如图3和图4所示。

(单位:个, s)

2.2.1 没有攻击分组

第一组实验是在没有攻击的情况下进行的, 得出正常情况下的平均分组递交率和网络平均延迟分别为4 142/4 341×100%=95.42%和160.64/4 142=0.04s。可以看出在没有攻击的情况下, 网络运行情况优良, 数据递交率达到了95%, 网络延迟低至0.04s。

2.2.2 30个/s攻击分组

本组实验中, 恶意节点攻击分组发送频率为30个/s, 计算出平均分组递交率为:1 574/4 286×100%=36.72%, 网络平均延迟为:1 549.52/1 574=0.98s。

从本组实验数据可以看到, 网络性能在恶意节点每秒发送30个攻击分组的情况下受到了较大的影响。与没有攻击分组情况相比, 平均分组递交率下降了60%以上, 网络延迟平均达到了正常情况下的24倍。本组实验进行到90~100s的时间段时, 分组递交率降到了最低, 只有22.3%。在70~80s, 网络平均延迟达到2.42s。实验中, 最低延迟为0.11s, 是正常情况的2.75倍, 网络性能受到较大影响。整个实验过程只有前20s网络性能还可以, 这是因为大部分移动节点还比较空闲, 网络中数据分组数量还很少。

2.2.3 50个/s攻击分组

本组实验中, 恶意节点攻击分组发送频率为50个/s, 计算出平均分组递交率为:683/4 249×100%=16.07%, 网络平均延迟为861.72/683=1.26s。

从以上数据可以看出, 在恶意节点发送50个/s攻击分组的情况下, 网络性能遭受严重的影响。与没有攻击分组的情况比较, 平均分组递交率下降超过80%, 网络延迟平均达到了正常情况下的31倍。本实验进行到60~70s时间段时, 分组递交率降至最低, 只有9.87%, 在20~30s, 网络平均延迟达到2.47s, 延迟最低也达到了0.79s, 是正常情况的19.75倍, 网络性能在整个实验阶段急剧下降, 几近瘫痪。

3 结语

由以上三组仿真实验数据可以看出, 泛洪攻击十分有效, 攻击强度越大, 网络性能越低。当攻击强度不大, 网络相对空闲的时候, 网络还可以正常工作;但是当攻击达到一定强度, 即使网络空闲, 性能也不能满足需求, 80%以上的数据分组丢失, 网络延迟也达到了严重影响通信的程度。由此可以推导出, 在网络资源非常有限的情况下, 采取一定强度的RREQ分组攻击, 就会迅速耗尽网络资源, 致使网络瘫痪。

摘要：恶意节点在一段时间内发送相当数量的RREQ消息, 正常节点则广播入侵节点的RREQ信息, 从而造成正常节点能源、存储资源和网络带宽耗尽, 网络遭受破坏。研究了AODV路由协议的缺陷, 针对路由请求RREQ消息广播的特性, 实现了RREQ泛洪攻击。用NS对攻击过程进行仿真实验, 用网络性能的两个重要变量 (数据分组递交率和网络延迟) 来衡量攻击结果。实验证明, RREQ泛洪攻击十分有效。

关键词：AODV路由协议,RREQ泛洪攻击,数据分组递交率,网络延迟

参考文献

[1]陈林星, 曾曦, 曹毅.移动Ad Hoc网络——自组织分组无线网络技术[M].北京:电子工业出版社, 2006.

[2]李晓.Ad Hoc网络路由协议AODV的改进研究[D].沈阳:东北大学, 2005.

[3]刘洛琨, 张远, 许家栋.AODV与DSDV路由协议性能仿真与比较[J].计算机仿真, 2006 (2) :119-120.

[4]姜振辉.AODV路由协议两种攻击方法仿真[D].北京:北京邮电大学, 2008.

AODV路由协议研究 篇2

摘要：文章综述了AODV路由协议在路由链路修复、能量控制以及安全保障等方面的最新研究进展，并指出了下一步研究方向。

关键词：自组网；路由协议；AODV协议

引言

移动自组网是由一组带有无线收发装置移动终端组成的一个多跳临时性自治系统。当发生自然灾害、基础通信设施遭到破坏等情况时，这种无中心分布式控制网络就可提供临时通信的便利。路由选择协议是自组网的关键技术之一。近几年，提出了很多自组网路由选择协议，大致可分为表驱动路由协议和按需路由协议两类。AODV协议是一种比较经典的按需路由协议，它借鉴了DSR算法中路由发现和路由维护的思想，又从DSDV中吸取了序列号识别和周期性信号更新等策略，是自组网路由协议研究中的热点。

一、AODV协议概述

AODV协议实质上是DSR和DSDV的综合，它借用了DSR中路由发现和路由维护的基础程序，及DSDV的逐跳路由、顺序编号和路由维护阶段的周期更新机制，又以DSDV为基础，结合DSR按需路由思想加以改进而成。AODV使用了分布式的、基于路由表的路由方式。所以建立路由表项以后，在路由中的每个节点都要执行路由维持、管理路由表的任务，在路由表中都需要保持一个相应目的地址的路由表项。实现逐跳转发。AODV有别于其他协议的最显著特点是引入了组播路由协议扩展，通过序列号的方式解决无限计数问题，这样可以避免发生环路，并容易用编程实现，但需要定期地发送HELLO报文，造成了一定的额外开销。

二、AODV协议的优化研究

AODV是少数几个通过IETF组织批准成为RFC文档的移动自组网路由协议之一，具有很多优点，但也存在着路由表仅维护单一到达指定目的节点的路由，以及没有提供足够的安全保护措施等局限。为了进一步优化AODV协议，路由研发者做了大量研究工作。

(一)AODV协议路由维护研究

AODV协议中每个节点的路由表中只保存到达各目的节点的一条路由，而节点的移动性很容易导致链路断裂从而造成路由失效。文献[1]在AODV协议基础上提出了多路径AOMDV协议，该协议经过一次路由发现可以在源节点与目的节点间建立多条链路不相交或节点不相交路由，这样一旦某条路由因为链路断裂而失效，就可采用另外一条路由继续进行数据包的发送。AOMDV可有效处理由于节点的移动性而造成的路由失败，显著降低分组的丢失率及平均端端延迟。由于路由重构次数降低，网络开销也会相应明显减少。节点不相交路由比链路不相交路由具有更强的独立性。能够为网络提供更好的负载均衡和容错能力。

文献[2]对AOMDV路由数量在不同网络环境下的运行效率进行了多项性能的模拟测试和分析，得出保持三条不相交路由可获得最优性能。

文献[3]在多路径基础上加入了负载平衡技术，将数据流均衡地分布到多条路由上，既可平衡链路负载，更能适应路由变化，降低了单条链路上的拥塞可能，进一步提高了协议的效率。

(二)AODV协议节能控制研究

由于无线节点只能依靠可携带的有限电源提供能量，因此如何提供节能策略也是移动自组网路由协议必须考虑的问题。

文献[4]对当前移动自组网能量保护策略进行了分析和综述，从功率管理和功率控制两个角度分析了各种策略的设计思路和特点，分析了关键的能量保护策略及其在各协议层的分布情况，并在分析了跨层设计在移动自组织网络中的需求后给出了包含若干创新思路的跨层协同能量保护构架。

文献[5]在AODV协议基础上，通过调整节点的发射功率，改变路由代价函数，能动地关闭无线接口，来达到节能的目的。从仿真结果来看，改进后的AODV在节能方面效果明显，但是由于在每个数据包中增加了pt域，降低了网络层以上的数据传送能力，导致数据传送时延增加，并由于将pt作为选路时依据，使丢包率有不同程度增加。

文献[6]在AODV协议基础上提出了ES-AODV协议，在综合考虑节点自身剩余能量，并利用链路上的每个节点使用反比例函数计算出与自身能量成反比的权值(能量越高，权值越小)。再以链路上各个节点的权值和作为链路的代价，选择其中代价最小的链路进行数据传输，进而有效平衡网络中的能量消耗，提高网络中节点的平均生存时间。

(三)AODV协议路由安全研究

由于移动自组网具有开放媒体、动态拓扑结构、缺少中心授权、分布式协作以及受限的网络能力等众多安全方面的弱点，很容易受到各种形式的恶意攻击。AODV协议没有添加任何安全保障机制，而将协议直接建立在网络中各节点都是安全节点的基础之上，因此路由安全是协议发展必将要考虑的问题。

文献[7]在AODV协议基础上提出了SAODV协议，采用公钥认证和Hash链机制来增强AODV协议路由发现过程的安全性，使得可能的攻击节点无法声称一条并不存在的路由；同时，AODV在RREQ和RREP中还增加了与路由跳数相对应的Hash链字段，用以校验分组中的跳数值是否正确。

文献[8冲采用公钥体制对敏感的路由信息进行认证和加密，只有产生路由请求信息RREQ的源节点才能验证这些敏感信息。在一次路径搜索过程中，只需要产生RREP的节点和源节点进行公钥运算，这样就不会过多增加计算开销，但是解密运算由源端节点进行，增加了源端节点的额外负载，并且加密报文由发起RREP的节点一直传输到源端节点，传输距离过长，容易被侦听。

文献[9]利用各个节点的签名机制进行安全防范，路径上的每个节点都参与运算，各个节点运算负载过大，极大地消耗了各个节点的能量，从而导致协议的效率下降。

三、结束语

本文从链路修复、能量控制以及安全保障等方面对目前AODV协议的研究进行了总结和分析，可以看到，虽然AODV协议在其发展过程中进行了一系列卓有成效的改进，但是都只能从某一方面改善AODV协议性能，如何合理有效地选取中介方案，实现AODV协议各方面均衡优化，是当前研究的一个难点。相信随着AODV协议不断改进和完善，必能在未来移动自组网的应用中发挥更加重要作用。

参考文献

[1]MARINA M K,DAS s R Ad hoc on-demand multipath distancevector routing／／Proceeding of 9th IEEE InternationaI Conference onNetwork Protocols(ICNP)[c]CA：Riverside,November 2001，

[2]KIM M S,KWON K J A modified AODV Protocol with mul－ti—paths considering C‘laSses of services／／ICCSA fCl 2004：1159—1168

[3]PHAM P P,PERREAU S Increasing the network performanceusing multi-path routing mechanism with Icad balance[J]lAd HocNetworks，2004(2)：433—459

[4]许力 张继东，郑宝玉，等移动自组网能量保护策略研究进展[J]通信学报，2004，25(9)：93—1D3，

[5]袁明，张连芳，舒炎泰，Ad hoc网络路由协议能量消耗分析[J].计算机工程与应用，2003(15)：146-149

[6]陈稼婴，杨震Ad hoc网络中基于节能的AODV路由算法改进[J]，南京邮电学院学报，2004，24(3)：18—22

[7]Manel Gueerero Zapata Secuer Ad hoc on-demand distancevector(sAODV)routing[z]draft-guerrero-manet-saodv-04，lETFinternet draft，September 2005

[8]杜欣军，葛建华，王莹一种增强AODV路由协议安全性的方案[J]西安电子科技大学学报(自然科学版)，2002,29(6)：819-821，

AODV路由协议研究 篇3

AODV是一种较经典的按需路由协议, 不需要维护去往所有节点的路由, 仅在没有去往目的节点路由的时候才进行按需路由发现, 从而有效地节省了网络资源具有控制开销低、带宽开销小等优点。传统的AODV路由协议仍然存在着一些不足:在负载大的情况下, AODV路由协议性能并不是很好。这是因为AODV路由协议在选择路径时仅仅以最短路径和最快响应作为度量准则, 并未考虑节点传输速率等一些相关因素, 从而导致得到的路径并非最优。

针对传统按需路由协议存在的缺陷, 本文提出了一种基于最大路由速率的AODV路由协议优化方案, 在协议内添加一个期望速率参数, 通过比较每条路由的传输速率, 选取一条速率最大路由, 从而提高传输成功率和保证吞吐量及网络生存期。

1 AODV路由协议分析

1.1 AODV路由协议工作原理

AODV路由协议是一种经典的按需路由协议, 它只在两个节点需要进行通信且源节点没有到达目的节点的路由时, 才会进行路由发现过程。AODV采用的是广播式路由发现机制, 当源节点想与另一节点进行通信时, 源节点会首先查询自己的路由表中是否存在有到达目的节点的路由有效信息。如果包含有目的节点的有效信息, 则源节点就会将数据包传送到目的节点的下一跳节点;如果缺失目的节点的有效的信息, 则源节点会启动路径请求程序, 同时广播RREQ控制包。

而下一跳节点在接收到RREQ报文时, 如果该节点是目的节点, 又或者该节点路由表中存放有到达目的节点的可行路径信息, 则会向源节点回复路由响应报文 (RREP) 。否则就记录相关信息, 用于建立一个反向路径, 让目的节点的RREP遵循此路径返回源节点, 同时将RREQ报文中的跳数字段值加1, 并向该节点的邻居节点转发RREQ报文。这样经过若干中间节点转发最后到达目的节点, 确认路由建立。

路由表项建立以后, 路由中的每个节点都要执行路由维持和管理路由表的任务。如果由于中间节点的移动而导致路由失效, 则检测到路由断链的节点就会向上游节点发送路由出错报文 (RRER) , 而收到出错报文 (RRER) 的节点则会直接发出RREQ来进行路径请求, 如果能在规定好的时间内找到目的节点的路径, 则表示路由成功修复。如果超时还找不到目的节点的路径, 则向源节点发送RERR, 源节点再发出RREQ来重新进行路由请求。

1.2存在的问题

传统的AODV采用基本的路由发现算法来建立从源节点到目的节点的路由时, 路由选择是选择最短路径路由, 即选择最小跳数的路由, 这样就忽略了每两点之间的传输能力, 从而导致产生整条链路吞吐量低、路由不稳定、线路拥塞、延迟甚至数据丢失等严重问题。

2最大路由速率的AODV协议

2.1基本思想

针对传统AODV路由协存在的问题, 提出了一种基于最大传输速率的改进方案, 其基本思想是:用户确定一个期望速率, 源节点在进行路由发现时比较收到的各条路由的实测速率, 选择一条速率最大的路由作为路由, 在源节点使用当前路由发送数据的过程中, 源节点每隔一段时间发出RREQ报文, 以便查找到可能存在的更好的路由, 如果发现一条速率更高的路由且该路由速率大于期望速率, 则执行路由切换, 改用新路由。

2.2数据结构与路由寻找及维护

2.2.1数据结构部分

修改AODV协议的RREQ和RREP, 在RREQ中添加了“期望速率”expect_rate和“实际速率”rate两个字段, 在RREP中添加“实际速率”rate字段, 使得协议支持路由速率的检测及传输。

2.2.2 路由寻找

当源节点需要发送数据时, 首先查找自己的路由表中的信息, 如果当前路由表中不存在到达目的节点的路由信息, 则会发送RREQ查找路由, 并将RREQ中的expect_rate值设置为0;

其他节点接收到RREQ后, 如果此节点是目标节点, 就将实测速率加入到RREP报文中, 然后再返回给源节点;

原路由协议允许任何中间节点发回RREP报文, 修改后的协议仅允许目的节点返回RREP报文, 这是因为其他中间节点可能维护的路由速率是错误的;

源节点比较收到各RREP中的rate, 选择一条速率最大的路由作为路由, 这样就获得了一条初始路由。在上述路由寻找过程中, 我们将路由速率的值定义为路由速率之和与路由跳数之比, 即路由速率= 路由速率之和/ 路由跳数。

2.2.3 路由维护

与原AODV路由协议相似, 当路由中断后, 将通知源节点, 源节点将重新发起路由寻找过程, 但在改进后路由协议中, 添加了路由切换功能, 可自动切换到rate最高的路由。

当源节点到目的节点存在可用路由时, 源节点检测expect_rate的值与当前路rate的值, 此时expect_rate值为用户设定的值。如果当前使用的路由rate已经大于expect_rate, 就不再发送RREQ;如果当前使用的路由rate小于expect_rate, 源节点依然每隔一段时间发出RREQ报文, 以便查找到可能存在的更好的路由;

当中间节点收到一个RREQ报文, 发现该报文所经过的路由的rate已经低于该报文中填入的expect_rate, 就不再转发, 从而也可以减少RREQ占用的网络带宽。

在源节点收到RREP报文后, 如果发现一条新路由的rate大于当前使用路由的rate, 则执行路由切换, 改用新路由。

3 仿真实现

3.1 仿真场景设置

仿真过程是在NS2 软件平台进行的, NS2 是一种面向对象的网络仿真器, 它本身有一个虚拟时钟, 所有的仿真都由离散事件驱动的, 本质上是一个离散事件模拟器。

仿真场景中包括4个节点, 其中节点1~3均为静止, 而节点4 是移动节点, 各节点无线通信距离采取默认设置为250m。其中, 各节点IP地址表见表1。仿真场景图如图1 所示。

3.2 仿真过程

实验在第0 ~ 62.5 秒, 节点4 在 (100, 600) ~ (100, 550) , 从第10 秒开始节点1 向节点4 发送数据, 其仿真设置见表2。

此时, 存在节点1— (3M) —节点2— (5M) —节点3— (1M) —节点4 一条3 跳路由, 最小的链路速率为1Mbps, 因此选择这条3 跳路由, 路由速率为:1Mbps/3=333, 333bps。其仿真路由结果见图2。

实验在第62.5 秒时, 节点4 移动到 (100, 550) 处, 仿真设置见表3。

此时, 存在节点1— (3M) —节点2— (5M) —节点3— (4M) —节点4 和、节点1— (3M) —节点2— (1M) —节点4 两条路由, 其中3 跳路由速率为:3Mbps/3=1Mbps, 2 跳路由速率:1Mbps/2=0.5Mbps, 因此仍然选择3 跳路由。其仿真路由结果见图3。

实验在第75 秒时, 节点3 移动到 (100, 500) 处, 仿真设置见表4。

此时, 存在节点0— (3M) —节点1— (5M) —节点2— (5M) —节点3、节点0— (3M) —节点1— (3M) — 节点3 两条路由, 其中3 跳路由速率为:3Mbps/3=1Mbps, 2 跳路由速率:3Mbps/2=1.5Mbps, 因此按照新的选路策略, 将改用2 跳路由。其仿真路由结果见图4。

实验在第80 秒时, 节点3 移动到 (100, 520) 处, 仿真设置见表5。

此时, 存在节点0— (3M) —节点1— (5M) —节点2— (4M) —节点3、节点0— (3M) —节点1— (1M) — 节点3 两条路由, 其中3 跳路由速率为:3Mbps/3=1Mbps, 2 跳路由速率:1Mbps/2=0.5Mbps, 因此按照新的选路策略, 将改用3 跳路由。其仿真路由结果见图5。

从上面仿真结果可以看出, 改进的AODV协议能自动切换到传输速率最高的一条路由上。因此能有效地应用在高负载的环境下, 解决原始的最短路径算法带来的吞吐量低、路由不稳定的问题。

4 结语

针对传统的AODV路由协议存在的问题提出了基于最大路由速率的AODV协议优化方案, 并在NS2 网络仿真软件环境下进行了仿真。仿真结果表明, 改进后的AODV协议能自动切换到传输速率最高的一条路由上, 从而较好地改善了协议性能。

参考文献

[1]Uupta P, Saxcna P, Ramani AK, etal.Optimized use of battery power in wireless Adhocnetworks[C].Advanced Communication Tcchnology (ICACT) , 2010 The 12th international Conferenceon[s.n.], IEEE, 2010:1093-1097.

[2]Das V V, Vijayakumar R.Designparameters for a securesy stem for mobile ad hocnetwork[C].Proceedings of the 2009 International Conferenceon Advancesin Computing, Control, and Telecommunication Technologies[s.n.], IEEE Computer Socicty, 2009:534-536.

[3]梁建武, 马晓亮.移动AdHoc网络AODV路由协议的研究与优化[J].重庆大学学报, 2015, 38 (4) :152-158.

[4]周德荣, 夏龄等.一种改进的AODV路由协议的实现与仿真[J].实验室研究与探索, 2014, 33 (11) :67-71, 212.

[5]何绵禄, 褚伟, 刘辉舟.AODV路由协议的研究和改进[J].计算机工程, 2015, 41 (1) :110-114, 120.

AODV路由协议研究 篇4

移动ad hoc网络是一种特殊无线移动通信的网络。它与一般无线移动通信网络的不同之处在于, 移动ad hoc网络不需要依赖任何基础设施, 整个网络是由节点组成。在移动ad hoc网络中, 所有节点地位都是平等的, 每一个节点即能够接受消息, 也能够转发消息。即每个节点都同时具有移动终端和路由转发的功能。

移动ad hoc网络最早起源于美国DARPA (Defense Advanced Research Project Agency) 的分组无线网 (PRNET, Packet Radio NETwork) 项目, 研究分组无线网在战场环境下数据通信中的应用。因此, 移动ad hoc网络最早也只限于军事领域中的应用。随着技术的发展与成熟, 移动ad hoc网络现在应用得越来越广泛, ad hoc网络现广泛应用于军事、灾后重建、个人生活以及将其作为一个无线多跳接入网与其它网络进行连接的应用。

移动网络由于其自身的特殊性, 具有以下特点:①无中心性, 移动ad hoc网络由于其所有节点地位相等, 所以其为一个对等性网络;②自组性, 移动ad hoc网络中, 只要节点的距离在一定范围内, 就能够自发地通过某种算法组成网络;③链路带宽及能量有限性, 移动ad hoc网络采用的是无线传输, 所以其信道带宽有限, 且移动ad hoc中的每个节点都具有转发信息的能力, 所以一般节点都要以电池作为其动力, 其节点能量也非常有限;④动态拓扑性, 由于移动ad hoc网络中的节点经常发生变动, 所以其网络拓扑结构也会经常发生变化。

2 移动ad hoc网络中的AODV协议

在移动ad hoc网络中, 一个好的路由协议至关重要。ad hoc网络中, 一般有2种划分路由协议的方法。一种是分为按需路由和按时间路由, 按需路由只在需要路由信息时, 才发起路由请求过程, 从而达到在路由开销相对较小的情况下提供路由;而按时间路由中, 每个节点都采用周期性发送信息包以达到更新路由表的目的, 从而以相对较大的开销来寻找最优路径 (主要指距离最短, 即所经过跳数最少的路径) 。另外一种划分方法是按通信模型, 分为单径路由和多径路由。单径路由在路由发现中只有一条信息通道;而多径路由中, 信息通道最少有两条或者两条以上。协议无线自组网是按需平面距离矢量路由协议 (Ad hoc On-demand Distance Vector Routing, AODV) , 是一种典型的按需单径路由协议。

Aodv协议的传输过程为:在ad hoc网络中, 每个节点都会维护一张自己的路由表, 当源节点 (S节点) 需要向目的节点 (D节点) 发送数据信息时, 首先检查自己的路由表, 查看是否有到达目的节点的路由信息。如果有, 则直接按照路由表上的路径发送;如果没有, 则向周围节点广播一个RREQ用来请求路由信息。当中间节点收到RREQ后, 首先同样会检查自己的路由表是否有到达目的节点的路由信息。如果有, 则按此路径进行发送;如果没有, 中间节点将在此RREQ消息中加入自己的信息后, 继续向其周围节点转发此RREQ请求包, 直到找到有到达目的节点路径的中间节点或者目的节点D节点本身为止。在有到达目的节点路径的中间节点或者目的节点本身收到该RREQ后 (此RREQ含有源节点到目的节点的反向地址信息) , 会回复一个与之对应的应答信息包RREP。这样, RREP沿着对应的RREQ的反向路径信息到达源节点, 从而更新源节点到目的节点的正向路径。

需要指出的是, 为了避免路由环路和网络负载过重, 中间节点和目的节点在收到相同的RREQ信息包时, 会立即将其丢弃。这样在一定程度上避免了路由环路, 减轻了网络负担。但是也正是由于此种机制, 使得网络传输效率不高。特别是在节点不停移动, 链路容易发生断裂的移动ad hoc网络中。因此, 提出一种对AODV协议进行改进的路由协议AODV-T (Ad hoc On-Demand Distance Vector Routing-Time, AODV-T) , 旨在进一步提高ad hoc网络中的传输效率。

3 AODV-T的算法数据结构

3.1 RREQ消息的数据结构

在RREQ消息中新增加了RREQ第一跳、路由记录、RREQ时延。其具体格式如表1所示。其中, RREQ第一跳是记录RREQ消息从源节点到目的节点路径的第一跳, 只要RREQ第一跳不相同, 就是链路不相交路径。路由记录则为记录经过的多条路径。RREQ时延则是记录发出一个RREQ消息后, 到接收到对应的RREP消息的时间。

3.2 RREP消息的数据结构

同样, 在RREP消息中也增添了相对应的最大时延、路由记录、RREP时延选项。其中, 最大时延是设定一个时延最大值, 当等待RREQ的时间超过此最大值时, 默认丢弃掉后来的RREQ消息。路由记录与RREQ相同, 从对应的RREQ消息包中拷贝过来。RREP时延则是记录RREQ到达目的节点的时间, 其结构如表2所示。

4 对AODV协议的改进

AODV协议虽然能满足一定要求的ad hoc网络需求, 但其并不是质量很高的一种路由协议。首先, AODV是单径路由, 在带宽有限的移动ad hoc网络中, 单径路由往往不能满足业务传输要求;其次, AODV协议的各种路由指标参数并不高。因此, 对AODV可以进行适当改进, AODV-T相对于AODV协议, 主要在两方面进行了改善。

一是在路由路径数目方面, 不再只是寻找一条路径进行路由, 而是同时以最短路径和次短路径同时进行路由。这里多条路径记录方法参考AOMDV协议。不同的是在AOMDV多径路由协议中, 是在一次路由发现中, 找到多条路径 (一般不会超过3条) 。在这多条传输路径下以一条最短路径为主路径, 以其它路径为备份路径进行传输。这样在实际传输中, 往往只有一条路径在进行信息传输。而AODV-T协议则是根据时延, 同时选择最短路径和次短路径进行传输。时延最小的为最短路径, 时延次之的为次短路径。时延是指从源节点发起路由寻找的RREQ时刻开始, 到接收对应目的节点回复的RREP数据包为止所经历的时间。时延在一定程度上反应了当前网络状况的好坏, 特别是在网络负载量较大的情况下, 跳数最短的路径往往不是最优路径, 而用时最少的路径才是最优路径, 即时延最少的路径。

二是AODV-T协议同时提供QOS保障, 必须在源节点与目的节点之间寻找必要资源以满足QOS要求的路由。为了找到合适的QOS路径, 选择以该路径的时延作为基本判断参数, 来确定该路径是否满足QOS要求。根据MSR均衡负载的方法, 对源节点搜索的3条 (如果存在) 路径按照权值进行业务分配。使用路由过程中RREQ-I的时延, 即从源节点发送一个RREQ-I的数据包到接收到该数据包对应的RREP-I回复数据包的时间。这个时间反映出了该条链路的状态, 即越稳定越近的链路, 其RREQ-I时延就越小。所以, 该条链路的可用带宽与RREQ时延成反比关系, 可以通过Wi=min{dmax/di, A}表示。其中, Wi为路径权值, dmax为到源节点的多条路径的RREQ-I的最大时延, di为路径i的RREQ-I时延, A是设定的一个边界值, 是为了防止一条路径负载过重。从公式中可以看出, 对于时延越小的路径, 其权值越大, 即路径的稳定性就越高, 可用带宽就越大, 其分配的负载业务相对其它条路径就越大。

5 仿真结果分析

选择网络仿真工具为NS2, 操作系统是在Linux环境下进行的。其它仿真的各项参数为:网络节点数量选取为50个, 网络拓扑范围设置为长500m、宽500m的正方形区域, 网络中的最大连接数为30个, 仿真持续时间设为100s。在相同的仿真环境下, 改变节点的移动速度, 分别对AODV协议和改进的AODV-T协议的分组投递率、平均端到端时延、网络开销进行分析比较。

从图1可以看出, 在节点移动速度较低的情况下, 两种路由协议能较好地将信息传递给目的节点, 而随着节点移动速度的增大, 分组投递率出现下降。而AODV-T的分组投递率比AODV要高, 这是因为AODV-T采用双信道传输, 当一条路径传输因节点移动速度过快而断裂时, 仍然有一条备份路径进行传输信息。

从图2可以看出, 随着节点移动速度的增大, 端到端时延明显增大。而AODV-T协议时延大概比AODV协议低3%左右。这是由于AODV-T选择以时延作为路径选择参数, 优先考虑时延较小的路径作为信息传输路径, 从而降低端到端时延。

从图3可以看出, 随着节点移动速度的增加, 路由开销不断增大。这是由于节点移动速度增加, 使链路断裂几率增大, 从而增加路由寻找次数, 增大路由开销。由于AODV-T采用的是最短路径和次短路径两条路径进行传输, 只有两条路径同时失效时, 才发起路由寻找请求, 从而降低路由请求次数, 降低路由开销。

6 结语

本文针对AODV的不足, 提出了一种以时延为参数的改进多径路由协议AODV-T。此路由协议根据网络当前状况同时以最短路径和次短路径传输信息。经过仿真测试表明, 该路由协议在分组传输率、平均端到端时延、网络开销方面较AODV协议而言, 均有所改善。

摘要：在Ad hoc网络中, AODV协议是一种重要协议, 但是由于AODV协议为单一路径协议, 因而其传输效率不高。在AODV协议的基础上, 提出一种以时延为参数的多径路由协议AODV-T, AODV-T协议能够同时以最短路径和次短路径进行传输信息。仿真测试表明, 该路由协议在分组传输率、平均端到端时延、网络开销方面较AODV协议而言, 均有所改善。

关键词：ad hoc网络,AODV协议,多径路由

参考文献

[1]郑相全.无线自组网技术实用教程[M].北京:清华大学出版社, 2004.

[2]C.K TOH.Ad hoc mobile wireless networks:protocols and system[M].New Jersey:Prentice-Hall PTR, 2006.

[3]IEEE Computer Society LAN/MAN Standards Committee.IEEEstandard for wireless LAN medium access control (MAC) andphysical layer (PHY) specifications[S].1997.

[4]D SENIE.Network address translator (NAT) -friendly applicationdesign guidelines[S].Internet Engineering TaskForce (IETF) , 2002.

[5]石晶林.移动自组织通信网络技术概况及未来前景[J].信息技术快报, 2004 (7) .

[6]舒炎泰, 高德云, 王雷.无线ad hoc网络中的多径源路由[J].电子学报, 2002 (2) .

AODV路由协议研究 篇5

关键词：Ad hoc,AODV,NDP

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) 采用了三种H E L LO消息类型:邻节点请求H E L LO消息 (NRH) , 邻节点响应HELLO消息 (NAH) , 广播HELLO消息 (BH) 。

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

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

(4) N D P不仅仅为AO D V路由协议而设计, 它是完全独立与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是节点在一个HELL O_INTEVERAL时间内没有收到任何其他分组情况下而发送的。

2.2 发送HELLO消息

所有节点在HELLO_INTERVAL时间内必须向邻节点发送一种HELLO消息。为了避免HELLO消息发送同步, 造成物理层碰撞, 所有节点不能以相同的HELLO_INTERVAL发送HELLO消息。为了达到此目的, 这里的做法是设置H E L LO_I N T E R V AL为: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:impera-tives and challenges[J].Ad hoc Networks, 2003, 1 (1) :13-64.

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

[3]Perkins C E, Belding-Royeret, S.Das.“Ad Hoc On-Demand Dis-tance Vector (AODV) ”, Internet-Draft, rfc3561.txt, July 2003.

[4]The Network Simulator (ns-2) http://www.isi.edu/nsnam/ns/

AODV路由协议研究 篇6

关键词：Ad Hoc网络,AODV,NS2

一、前言

Ad Hoc网络是一种移动主机之间进行数据传输的网络。在这种网络中, 不存在中心的基站或者说移动交换中心, 移动主机之间通过对等的多跳技术来进行互联, 而且Ad Hoc网络的拓扑结构也因为主机的移动发生动态的改变, 移动主机与本机无线覆盖范围内的邻机直接通过无线链路通信, 而与远处的移动主机的通信则需要依赖邻机来进行路由转发, 因此, Ad Hoc网络中的移动主机本身都需具备路由功能, 能完成相关的路由转发。近年来, 出现过多种Ad Hoc网络路由协议, 这些路由协议都必须处理移动网络中的典型的问题, 如高能耗、低带宽和高误码率等。现有的路由协议可以大致分成两类:表驱动路由协议和源初始化路由, 本文将AODV路由协议进行描述和改进。

二、AODV路由算法原理

AODV路由协议是一种改进的距离向量路由协议, 具有按需路由协议的特点, 即在AODV路由协议中, 网络中的每个节点在需要进行通信时才发送路由分组, 而不会周期性地交互路由信息以得到所有其它主机的路由;同时具有距离向量路由协议的一些特点, 即各节点路由表只维护本节点到其他目的节点的路由, 而无须掌握全网拓扑结构。

AODV路由协议中有三种类型的消息控制帧:路由请求 (RREQ) , 路由应答 (RREP) 和路由错误 (RERR) 消息。当源节点需要发送数据而又没有到目的节点的有效路由时, 启动一个路由发现过程:向网络广播一个路由请求分组RREQ, AODV允许中间节点响应RREQ, 当收到请求的中间节点或目的节点有一条“足够新”的路由到达目的地时, 中间节点或目的节点以单播的方式向源节点返回一个RREP分组, RREP沿着刚建立的逆向路径返回源节点, 源节点收到该RREP后则开始向对应目的节点发送数据。在数据传输过程中, 当中间节点检测到一条正在传输数据的活动路由的下一跳链路断开或者节点收到去往某个目的地节点的数据报文, 而节点没有到该目的地节点的有效maxmax) 1 (speedahopae dstp snp thValp Value路由时, 中间节点向源节点单播或多播路由错误消息RERR, 源节点收到RERR后就知道存在路由错误, 并根据RERR中指示的不可达目的地重新找路。

每一个接收到RREQ的节点都会保存到源节点的路由, 当到目的节点的路由找到时就能用单播将RREP返回源节点。

三、改进的AODV路由协议BVAL-AODV

1. BVAL-AODV路由协议的基本原理

针对AODV协议的原理进行研究, 在此基础上设计出一个能兼顾延长网络存活时间和局部负载分摊等特点的新的路由协议BVAL-AODV, 使得该协议不仅具有高数据投递率, 低路由平均负载和低端对端数据传输时延的特点, 还能有效实现网络负载均衡等。

在AODV路由查找的过程中, 源节点可能获得不止一条有效的路由回复, 它将选择含最小跳数的路由来传送数据包, 但是最小跳数的路由不一定就是网络中最佳的路由, 因此会大大影响网络的数据投递率和时延。路由表仅维护一条到指定目的节点的路由, 当某条路由失效时, 源节点需重新发起路由发现过程。由于Ad Hoc网络中节点的高移动性以及链路的不稳定性导致路由发现过程频繁启动, 造成路由开销大。在AODV协议的路由发现和路由维护阶段, 利用中间节点已有的路由来直接响应路由请求, 但此时中间节点很可能正在传输数据, 这样将加重某些路段的负荷, 使其出现拥塞, 而与此同时可能存在另外的空闲链路, 这样致使网络负荷在各链路上分配严重不均, 降低了整个网络的性能。因此本文提出的改进的路由协议BVAL-AODV关键是在路由选择阶段, 不再主要根据最小跳数最为标准判断, 而是综合考虑节点的移动性和跳数两种因素。

BVAL-AODV协议算法原理如下:

根据上述两个因素计算路由权值, 公式如下:

Value为每个节点权值, hop表示该节点跳数, speed表示该节点的运动速度, hopmax表示所有节点跳数最大值, speedmax、表示所有节点运动速度的最大值, a是路由控制参数。

用计算出的值Value替代每个节点原有的最小跳数值。在每个节点转发数据包时, 需要将自己的Value值进行累加, 到达目的节点后则构成了整条路径权值:

目的节点选择PathVal值最小的路由, 然后开始路由建立过程。从公式中可以看出, 节点速度越大, 则节点的权值越大, 在路由选择时选中该速度大的节点的可能就越小。用这种方法选择的路由将倾向于选择移动性较低的节点, 可很大程度避免由于节点频繁移动而导致快速更新路由所带来的各种开销, 使选择的路由更稳定, 不会造成局部拥堵的情况。

2. 路由算法实现

在NS2平台上进行路由协议的添加或者修改, 最重要的即如何对接收到的数据包进行处理还有如何寻找路由的问题。AODV协议算法中有专门的recvAODV函数处理接受数据包。网络中每个节点在收到数据包以后, 第一步是判断该数据包的类型, 如果说是路由请求消息RREQ, 那么就需要调用recvRequest () 函数;如果数据包是路由错误消息, 那么就需要调用recvError消息;假如数据包是路由应答消息, 那么我们就应该调用recvReply () 函数。

具体流程如图1所示。网络中的节点判断出收到的数据包是请求消息RREQ后, 则调用recvRequest () 函数, 来判断此数据包是不是就是由本节点自己发出的, 如果是那么接着判断这个是不是更新的路由请求, 或者不是更新请求但是它所经过的路径权值比本节点路由表中的要小, 此时这个节点就按要求更新从它到源节点的反向路由;如果不是由自己发出的, 那么节点会解析所收到的数据包, 并从本节点路由表查找看是否存在来自该节点的RREQ。第二步是判断现在的这个节点是不是目的节点, 如果是目的节点, 需要对各节点Value做累加操作, 计算出每一条路经的总的权值PathVal, 并且找到PathVal值最小的那条路经进行路由应答消息, RREP的发送;假如该节点不是目的节点, 还是需要计算出本节点权值并做累加操作, 然后把数据包转发给邻居节点。由于本文提出的这种路由协议的算法主要通过修改recvRequest完成, 所以不仅在处理请求时要加入计算权值Value的函数, 同时在应答时也需要计算Value。

四、结论

本文提出的BVAL-AODV协议算法, 通过控制参数综合最小跳数和节点移动速度计算出路由选择值, 在路由发现过程中, 在某一条路径上计算路径总的路由权值, 选择其中最小值的路径作为链路路径。当节点移动速度很小时, 改进的协议几乎与原始AODV的性能持平, 当节点移动速度增大时, 选择的链路会因为没有拓扑变化而重新启动, 因此节省了时间, 减轻了路由负载也提高了数据投递率, 从而有效地提高了网络性能。仿真结果证明BVAL-AODV算法有效。

参考文献

[1]武卉明, 李鸥.AODV, DSR和188220C路由协议比较研究[J].通信技术, 2008, 41 (6) :33-35.

[2]舒炎泰, 高德云, 王雷, “无线Ad hoc网络中的多径源路由”, 电子学报2002年2月, Vol.30, No.20

AODV路由协议研究 篇7

1 AODV (Ad Hoc on demand distance vector) 协议简介

AODV[2]路由协议是一种按需路由协议, 它结合了DSDV的路由维护机制和DSR的路由发现机制, 是两者结合的产物[3]。它避免了无穷计数的问题, 实现了无环路由, 大量研究结果表明, AODV的性能在大多数场合中要强于其它已有的路由协议, 并且具有存储资源消耗小, 编程容易以及计算量小等优点, 适合资源有限的嵌入式系统[4]。

2 ADOV在嵌入式系统上的移植

2.1 嵌入式Linux系统的移植

在移植之前首先要建立交叉开发环境, 安装交叉编译工具[5]。Linux内核采用较新的Linux 2.6.28内核。Bootloader、Linux内核和文件系统共同构成了基本的、最小的嵌入式Linux系统。

相对于之前的版本, Linux 2.6内核的编译, 只要运行make命令就行。编译前要对内核代码进行一些修改, 主要有如下步骤:

(1) 修改顶层的Makefile文件。

(2) 修改内核MTD分区。必须保持内核MTD分区与vivi的分区相一致, vivi分区中的地址是引导程序、内核映像以及文件系统下载到NandFlash的真正地址。因为内核启动时, 内核并不是去读vivi分区中的地址, 而是去读内核MTD分区设定的地址。需要修改arch/arm/mach-s3c2410/common-smdk.c文件里的函数mtd_partition smdk_default_nand_part[]={}, 使其地址与vivi中的分区地址一致。

(3) 禁止Flash ECC校验。内核中的ECC码是由S3C6410中的Nand Flash控制器产生的, 所以要禁止内核ECC校验。修改s3c6410.c代码中chip->c.mode=NAND_ECC_NONE。

(4) 启动时挂载devfs。为了让内核支持devfs以及在启动/sbin/init运行之前能自动挂载/dev为devfs文件系统, 应在文件fs/Kconfig中找到menu Pseudofilesystem语句, 然后在其后添加:

(5) 匹配vivi和内核的machine ID。vivi传递给内核的machine ID必须与内核代码中的ID一致, 处理器的值定义在/arch/arm/tools/mach-types文件中。

(6) 内核配置在配置内核时, 对需要的功能进行配置和去除不需要的模块, 以此来减小内核体积。运行make menconfig进行配置, 在s3c6410_defconfig默认配置基础上进行裁减。需要加入MTD分区及NandFlash支持、文件系统ramdisk文件系统。对于AdHoc网络, 还需要加上无线网络、无线网卡驱动、USB驱动、模块可加载及NetFilter等支持。需要选择“IP Userspace queueing via NETLINK (OBSOLETE) ”项支持。

(7) 制作根文件系统。从Linux 2.6.18开始的新版本的udev是一个基于用户空间的设备管理系统。在内核启动时并不能自动创建设备节点, 需要手动在dev/目录下创建各种节点, 即设备文件。涉及系统启动过程的设备有/dev/mtdblock* (MTD块设备) , /dev/tty SAC* (串口) , /dev/console (控制终端) , /dev/null, 只有建立以上设备才能启动系统。

2.2 在嵌入式linux中移植AODV路由协议

目前多数已经发布的AODV实现都利用了Netfilter功能框架。Netfilter是Linux2.4内核实现报文过滤、报文处理、报文转发等的功能框架, 并在linux后续版本中得到延续[6]。本文采用的AODV协议是开源的aodv-uu-0.9.6。AODV路由协议移植即将aodv-uu-0.9.6移植到ARM Linux中, 主要有以下几个方面。

(1) 修改Makefile内核源码路径和编译器版本 (#代表注释内容)

(2) 在lnx/kaodv-debug.h程序中添加头文件#include。在lnx/kaodv-netlink.c中将static DECLARE_MUTEX (kaodvnl_sem) ;改为static

DEFINE_SEMAPHORE (kaodvnl_sem) ;

(3) 编译后, 将在当前目录下生成aodvd可执行文件, 在lnx目录中将生成kaodv.ko模块。

(4) 组建adhoc网络:

3 AODV实现分析

本课题选择通用操作系统Linux作为实现AODV路由协议的平台, 可以利用现有的、成熟的应用框架, 提高开发速度, 同时能保证协议正确实现。但是由于Linux操作系统源代码的开放性, 在实现AODV路由协议过程中, 必须要对操作系统内核架构熟悉。在Linux操作系统中提供了实现网络数据包过滤和控制的模块Netfilter, Netfilter提供了在操作系统内核网络协议堆栈中的多个钩子点 (hook) , 可以在钩子点上注册回调函数, 利用这些回调函数在协议栈不同运行状态下处理数据包, 实现在不修改操作系统源码的情况下添加协议算法。

AODV协议是作为用户层的后台程序实现的, 包括一个可装载的Linux内核模块 (kao_dv) , 采用守护进程的方式运行, 使用Netfilter来截获报文[7]。Netfilter通过返回NF_QUEUE来缓存用户层的所有报文, 同时对用户层报文进行排队, 将所有报文的目的地址与用户层路由缓存匹配, 在用户层缓存需要路由请求的报文, 并立刻返回己存在路由的报文。在AODV路由协议实现的过程中, 除了内核路由表外, 在用户层还需建立了AODV路由表, 用来记录各种路由信息, 路由表条目的建立或更新是基于所收到AODV控制报文信息的[8]。

4 系统测试

本系统在室外进行测试, 将3台具备视频和其他监控功能的终端安置于监控点, 各监控点之间的距离约为50米。以视频为主要参照特征, 在启动系统后, 首先发送“Hello”, 如图1所示, 通知其他节点有新节点加入, 并且取得其他节点的路由信息, 更新本地路由信息, 输出信息如图2所示。各个监控终端将采集到的视频流经H264编码压缩后通过无线网卡自主选择路由路径发送到控制端。远程监控主机对接收到的视频流进行数据实时解码处理并进行显示, 系统视频流畅、图像清晰、实时性强。当某一个通信节点退出通信的时候, 会在整个网络内产生通知, 清理网络内节点的路由, 输出信息如图3所示。其他节点会自动选择其他路由路径传输数据, 网络具备自愈合能力。

5 结论

本文详细论述了AODV路由协议在Linux平台下的实现原理和移植过程, Linux是开源的操作系统, 不但安全稳定、可裁减, 而且具备强大的网络功能。本系统不修改内核基本代码, 利用netfilter提供的HOOK实现AODV路由算法, 在保持Linux系统的路由转发功能不变的情况下, 实现AODV选路功能, 并解决了AODV进程与内核的交互问题。

参考文献

[1]郑少仁, 王海涛, 赵志峰, 等.Ad Hoc网络技术[M].北京:人民邮电出版社, 2005.

[2]C.Perkins, E.Royer.RFC 3561.Ad-hoc On-Demand Distane Vector (AODV) Routing[S].2003-07.

[3]Perkins CE.Royernad5 EM.Das.Ad Hoc on Demand Distance Vector (AODV) Routing.IETF RFC3561, July, 2003.

[4]谢世欢, 郭伟.实现Ad-hoc按需路由协议的关键技术[J].计算机应用, 2006, 26 (3) :517-518.

[5]宋凯, 严丽平, 甘岚, 等.ARM Linux在S3C2410上的移植[J].计算机工程与设计, 2008, 29 (16) :4138-4140.

[6]张纪坤.嵌入式Linux系统开发技术详解[M].人民邮电出版社.

[7]陈林星, 曹曦, 曹毅.移动Ad Hoc网络[M].电子工业出版社.

AODV路由协议研究 篇8

无线移动自组织网是一种移动的、多跳的、无中心的、网络拓扑动态变化的分布式自组织对等网络。无线自组织网中的节点随机分布,不依赖任何网络设置[1,2],节点自己具有网络路由功能。随着多媒体业务在自组网应用中不断发展,人们对自组网的 QoS需求也在不断提高。但由于无线自组织网具有信道易受干扰、共享信道、网络节点移动变化快、处理能力有限等特点[3,4],使QoS的研究面临很大困难。

AODV[5,6]协议是一种按需路由协议,它可以实现移动终端间动态的、自发的路由,使移动终端能够很快地获得到达所需目的地的路由,并且还可以很快地对断链和拓扑变化做出反应。

该文通过协议包的格式进行扩展,添加链路可用带宽和延时的参数,找到一条最优的QoS路径。在建立QoS路由时,如果同时满足带宽、延时和分组丢失率的要求,以达到最优解是一个NP完全问题[7,8]。所以在设计QAODV时,将带宽作为优先考虑的条件,其次是延时和路由开销。

1 QAODV的设计思想

1.1 QAODV链路状态信息(带宽和时延)的获取算法

通过HELLO包计算带宽,图1是示意实际场景中节点发送HELLO协议包的情况,HELLO主要报文格式如下:

假设节点1在t1时刻向邻居节点发送HELLO协议包,并记录t1于hdraodvhello::localtimestamp。节点2在t2时刻收到节点1广播发送的HELLO协议包,并记录t2于AODVNeighbor::localtimestamp。t3时刻节点2的HELLO定时器开始发送HELLO包,节点2从邻居链表中读取邻居节点信息放入HELLO包中,其中hdraodvhello::nbtimestamp=AODVNeighbor::nbtimestamp+(t3-AODVNeighbor::localtimestamp),向周围邻居发送HELLO协议包。节点1在t4时刻收到节点2广播发送的HELLO协议包,从HELLO包中获取节点1的hdraodvhello::nbtimestamp。节点1到节点2之间的链路延时为:delay=t4-hdraodvhello::nbtimestamp。带宽:Bandwidth=2*(发送一个HELLO的比特数+MAC的比特数+RTS的比特数+CTS的比特数)/delay/1 000 000。

1.2 路由发现过程描述

对路径的可用带宽和延时作如下定义:

假设节点u1到节点un之间有一条链路,path(u1,u2,…,un)表示改链路经过的路径(简写为path(u1,un));BW(u,v)表示节点u和节点v之间的链路带宽[9];Delay(u,v)表示节点u和v之间的链路延时;则对路径path(u1,un)有如下定义:

定义1 path(u1,un)的可用带宽BW(u1,un)=min(BW(u1,u2),BW(u2,u3),…,BW(un-1,un))

定义2 path(u1,un)的延时Delayundefined

首先开启HelloTimer定时器[10],HelloTimer定时器每秒发送一个HELLO协议包,用HELLO协议包测试本节点到邻居节点的带宽和延时,得到邻居节点的带宽和延时信息后,将邻居节点的带宽和延时信息保存在邻居链表中。分别用nbbw,nbdelay(nb为neighbour的缩写,bw是bandwidth的缩写)记录本节点到邻居节点的带宽和延时。

路由发现过程整体分为建立反向路径的QoS路由和建立正向路径的QoS路由,反向路径的QoS路由是通过对RREQ包的处理建立起来的,正向路由是通过对RREP包的处理建立起来的。用rt0代表本节点到源节点的反向路由,用rt代表本节点到目的节点的正向路由。在RREQ报文字段里用rreqminbw来标记RREQ协议包所经过沿途路径上的最小带宽,用rreqmaxdelay来标识RREQ协议包所经过沿途路径上延时的和。在RREP报文里用字段rrepminbw来标记RREP报文经过沿途路径上的最小带宽,用rrepmaxdelay来表示RREP报文所经过路径上链路的延时加和。下面写出QoS建立和维护的具体算法:

2 仿真及性能评价

实验采用NS 2[11]网络仿真工具,仿真的网络环境和相关参数设置如下:网络中有50个节点,随机分布在670 m×670 m的范围内,节点的通信范围是250 m,物理信道的带宽为2 Mb/s,节点的移动模型为Random Waypoint Model,节点的移动速度为0～20 m/s,节点移动到位置后停顿时间是600 s,仿真总时间为900 s。节点发送的数据包均为cbr流量的数据包,数据包大小为512 B,各通信节点报文的速度为1 packet/s,2 packet/s,4 packet/s,6 packet/s,8 packet/s。

以发包投递率和链路延时作为对协议性能的评价,其中分组投递率和平均延时分别定义如下:

链路延时的计算方法:一段时间内的包的延时平均值作为链路延时的参考时间。

分组的平均延时undefined分组i的接收时刻-分组i的发送时刻)

分组投递率=目的节点收到的分组数/源节点发送的分组数

仿真结果如表1,表2所示。

从表1可以看出,在网络流量比较小的情况下,AODV和QAODV都能满足业务要求,当网络流量较大时,分组投递率均急剧下降,但是QAODV比AODV的收包率约提高了3%～5%左右。表2可以看出,QAODV比AODV的增加了不到1 s的平均时延,在实际应用中,这个增加的时延是可以接受的。

3 结 语

(1) 使用HELLO消息包测试带宽,HELLO消息包是AODV协议自身支持的协议报文,只需对HELLO消息包进行报文格式扩展,最小限度地降低路由开销。并且测试的带宽是路由层端到端带宽,比用MAC层测试带宽更准确,增加代码的可移植性。这里讲述的HELLO消息包测带宽的方法考虑了实际场景下节点之间大多数情况下时间不能精确同步,不能简单地通过接收到一个HELLO包就测带宽的方法。

(2) 改变传统自组织网的QoS路由协议QAODV中即使中间节点有到目的节点的路由也不能向源节点发送reply的方式,且如果QoS路由中间节点无法满足 QoS后,不进行路由修复,而直接返回QOS-LOST分组给源节点,使中间节点可以向源节点发送reply,降低了额外的延迟和分组控制开销,最大限度地支持了原AODV路由协议。

当然AODV的QOS路由策略是不断完善的,在该基础上增加带宽预约机制或者将业务类型划分为不同的等级,并对不同等级的业务提供不同等级的QoS服务等都不失为有效的QoS-AODV。

参考文献

[1]郑凯.一种基于AODV的QoS路由协议[J].计算机应用,2005,25(12):16-19.

[2]王新生,张昕.MANET环境下AODV协议的研究和改进[J].微机发展,2005,15(12):140-144.

[3]Chen S G.Nahrstedt K.Distributed Quality-of-Service Rou-ting in Ad Hoc Network[J].IEEE Journal on Special Areasin Communications,1997,17(8):1 488-1 505.

[4]英春,史美林.自组织网如何路由[J].计算机世界,2000,44(3):5-7.

[5]方伟,李腊元.一种支持QoS路由的MST算法[J].武汉理工大学学报,2003,27(6):829-832.

[6][美]Tanenbaum A S.Computer Networks[M].3版.熊桂喜,译.北京:清华大学出版社,1998.

[7]于宏毅.无线移动自组织网[M].北京:人民邮电出版社,2005.

[8]李腊元,李春林.计算机网络技术[M].北京:国防工业出版社,2001.

[9]苗建松,孙丹丹,丁炜.移动Ad Hoc网络中的QoS路由研究[J].现代电信科技,2005,3(12):50-53.

[10]Sivakumar R,Sinha P,Bharghavan V.CEDAR.A Core-ex-traction Distributed Ad Hoc Routing Algorithm[J].IEEEJournal of Selected Areas in Communications,1999,17(8):1 488-1 505.