AODV协议

AODV协议（精选8篇）

AODV协议 篇1

摘要：本文通过分析AODV协议, 认为在移动AdHoc网络环境下由于最小跳数并不一定是最佳路由, 因而会影响网络的数据投递和时延, 并针对该问题提出了一种改进的协议算法BVAL-AODV。BVAL-AODV算法在每个节点上加入数据域, 在路由选择时综合考虑最小跳数和节点的移动速度, 通过控制参数计算权值, 并保存到每个节点的数据域。在节点转发数据包时, 将自己数据域的值进行累加, 到达目的节点后则构成了整条路径权值, 将路径权值进行排序, 选择总路径权值最小的路径建立路由。

关键词：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

[3]郑相全等译.《无线自组织网络技术实用教程》.清华大学, 2003.

AODV协议 篇2

关键词：MGeo-aodv;地理位置;能量消耗

中图分类号： TP212.9            文献标识码： A            文章编号： 1673-1069（2016）30-157-2

0  引言

在源结点寻找路由信息时，中间结点会向全网广播RREQ数据包，会导致结点的能量大量消耗[1]。许多研究人员提出基于地理位置的最短路径算法[2][3]，基于地理位置的Geo-aodv[4]路由协议可以首先根据获取的结点位置，限制转发条件，减少中间结点请求消息的发送数量，节省了能量消耗，但是不能对之前通信结点的数据信息进行更新[5]，基于Geo-aodv协议的缺点，本文设计了MGeo-aodv （Modified Geography Ad Hoc On demand Distance Vector）路由协议。

1  MGeo-aodv路由协议描述

网络中的每一个通信结点通过GPS获取自己的地理信息，其地理位置坐标可以用（x，y，z）代表，x，y，z分别表示x轴，y轴，z轴，即三维坐标系空间，这里假设网络中所有通信结点都处于地球平面（z=0）。起初因为并没有建立源结点到目的节点的路由信息，所以源结点会查找Geo路由表，如果在该路由表中没有任何所需目的结点的地理位置信息，将转发角设置成360。，即向整个网络广播RREQ;如果在Geo路由表中可以找到目的结点的地理位置信息，则将转发角设置为90。。当源结点在发送完路由请求消息后，在设定的时间范围内没有收到路由回复信息（RREP），则源结点会重新发送RREQ，同时将转发角设置为180。，如果在规定的时间还没有收到RREP，依次将转发角设置为270。，360。（全网广播）。

如图1所示，Source为源结点，Destination为目的结点，网络中有三个中间结点，分别是NodeN1，NodeN2，NodeN3。NodeN1为上一跳结点，NodeN2为当前转发结点。当转发角为A1，只有NodeN1在搜寻范围内，因此会转发RREQ;如果转发角为A2时，只有NodeN1，NodeN2会发送RREQ，因为NodeN3不在搜寻范围内，所以收到请求消息后会丢弃。

①Geo路由表的管理

Geo路由表中的项目主要包括网络中所有通信结点的序号，地理位置坐标及IP地址（用IPv4表示）。如果中间结点收到RREQ，会在Geo路由表中查找有无源结点的信息，如果没有或Geo路由表的源结点序号小于路由请求消息中的序号，那么通信结点就会及时更新Geo路由表。

②计算搜寻区域

图1中，假设NodeN2收到NodeN1转发的RREQ信息后，结点NodeN2首先判断θ，若θ小于转发角的1/2，那么NodeN2转发RREQ。θ的计算公式：

θ=cos-1 （1）

如图2设α为转发角，由图可知结点NodeN2明显已经远离了目的结点，θ大于转发角的一半，所以NodeN2不在转发请求消息。如果上一跳通信结点到达目的结点的欧式距离小于当前结点到达目的节点的欧式距离，那么我们也认为请求消息的转发已经偏离了目的结点方向，该结点会丢弃请求消息。

<E：＼123＼中小企业管理与科技·下旬刊201610＼97-197＼114-2.jpg>

图2  节点转发情况

2  OPNET介绍

本文采用OPNET网络仿真，OPNET是常用的网络仿真软件之一。

该仿真软件使用离散事件驱动模拟机理对网络模型的功能特性进行仿真。常用的编辑器主要有：项目编辑器（Project Model）、节点编辑器（Node Model）和进程编辑器（Process Model），三个编辑器分别对应建模所需的三个层次模型。它涉及仿真研究的各个阶段，包括模型设计、仿真、数据收集和数据分析。OPNET提供了三层建模机制，分为：网络层、节点层和进程层。分别对应了工程编辑器、节点编辑器和进程编辑器。

3  实验结果分析

3.1 构建仿真环境

随机在2000米×1500米区域内放置了50个通信节点。表1为仿真环境参数，在该实验中，分别设置不同的通信结点数对Geo-aodv和MGeo-aodv两个路由协议进行了仿真比较。

表1  参数设置

<E：＼123＼中小企业管理与科技·下旬刊201610＼97-197＼114-表1.jpg>

3.2 实验结果分析

为了更好地对两个协议的性能进行比较，我们首先定义两个参数的计算公式：

①结点存活率的计算

NSR=  （2）

上式中，用NSR表示存活率，如果该值越大，则说明网络中未耗尽能量的结点越多。n表示结点总数，a为能量耗尽结点的个数。

②请求消息（RREQ信息）发送数量的计算

N=（Ns（i）+Nr（i））（3）

N为网络中传输的请求消息总数，n表示结点总数，Ns（i）和Nr（i）分别表示第i个结点发送和接收请求消息的数量。

如图3所示，随着网络中通信结点数量的增多，路由请求消息的发送数量也会随之增大。在MGeo-aodv算法的设计上，中间结点收到请求消息后会根据设置的转发条件进行判断，满足条件的结点转发RREQ，不满足的结点不再转发。所以与Geo-aodv协议相比，MGeo-aodv在请求消息数量上有较大的改善。

如图4所示，MGeo-aodv协议中通信结点的存活率要远远高于Geo-aodv协议。在MGeo-aodv算法中，对于偏离了目的结点方向的转发结点不再转发请求消息，减少了数据包在网络中的传输，避免了结点不必要的能量消耗。在不同的通信结点个数的网络中，均体现了这一优势。

<E：＼123＼中小企业管理与科技·下旬刊201610＼97-197＼114-4.jpg>

图4  节点存活率

4  小结

本文主要介绍了MGeo-aodv算法，中间结点根据转发角判断其是否在搜寻区域中，并计算到达目的结点的距离，然后和上一跳到达目的结点的距离进行比较，如果小于则转发请求消息。通过设置转发条件，控制请求消息的发送数量，从而达到节省能量消耗的目的，最后通过OPNET仿真验证了该协议的有效性。

参 考 文 献

[1]  Chaitali Biswas Dutta，Utpal Biswas.An energy aware blackhole attack for multipath AODV[C].IEEE International Conference on Business and Information Management （ICBIM），2014：142-147.

[2]  Zainab Senan Mahmood.The Directional Hierarchical AODV （DH-AODV） routing protocol for wireless mesh networks[C]. IEEE International Conference on Computing， Control， Networking， Electronics and Embedded Systems Engineering （ICCNEEE），2015：224-229.

[3]  Wang， Li Y，Yang X Y.Energy-Efficient Localized Routing in Random Multihop Wireless Networks [J]. IEEE Transactions on Parallel and Distributed Systems， 2011， 22（8）： 1249-1257.

AODV协议 篇3

在车载自组织网(Vehicular Ad-hoc NETwork,VANET)中,车辆快速移动以及拓扑频繁变化使得车流密度在完全连通、部分连通或连通性低三种状态来回切换,使得车载网中的路由协议一直处于不稳定状态,链路断裂时有发生。而设计路由的方法是为了提高路由稳定性,提升路由的整体性能,因此进行路由设计时应充分考虑影响路由稳定性的因素,进一步提高链路稳定性,提高端到端的链路持续时间。

按需距离矢量路由协议(Ad hoc On-demand Distance Vector Routing,AODV)是一种典型的按需路由协议[1],当某个节点需要与目的节点建立通信时会发起路由请求。AODV协议借鉴动态源路由协议(Dynamic Source Routing,DSR)路由寻找和路由维护的优点,同时又借鉴目的节点序列距离矢量路由(Destination Sequenced Distance Vector Routing,DSDV)协议的逐条机制、最新目的节点序列号的优点,因此AODV协议无需存储之前的路由,减少了网络开销。AODV路由主要分为路由寻找和路由维护,路由寻找又包括正向路径的建立和反向路径的建立。在路由寻找和路由维护过程中需要用到三种控制包:路由请求包(RREQ)、路由回复包(RREP)和路由错误包(RERR),这三种包都是由UDP产生,是标准的IP包。该协议不能完全适应网络拓扑复杂多变的车载网,其缺点如下:①在路由寻找时采用洪泛机制发送RREQ包,所有接收到路由请求包的节点将都参与转发RREQ,导致网络竞争激烈,浪费网络带宽;②目的节点选择路径时,只考虑最少跳数,即最少跳数的路径为最优路径,而忽略了运动状态如:节点的相对速度,节点角度等影响链路稳定性的关键因素;③路由维护过程采用的本地路由修复,其实质是在断裂处上游节点重新发起路由,并没有考虑如何将断裂处上游节点和下游节点巧妙的连接,修复后的路由长度既大于断裂前的长度,增加了数据传输的时延,同时也浪费了资源。

基于以上AODV的缺点,国内外许多文献对AODV进行了系统的研究与改进,使该路由协议能够更好的适应于车载自组织网络。文献[2]提出一种混合路由协议HLAR,结合基于地理位置的贪婪转发路由AODV-ETX的特点,同时添加本地路由修复的功能寻找一条链路质量最好的路由,使之能更好的适应于车载自组织网络。文献[3]提出一种新的基于地理位置的混合路由协议,在链路出现故障时,该混合协议表现出位置信息的高效扩展功能,能够有效降低路由成本和网络负载,能够更好的适应于紧急智能传输系统。文献[4]提出利用多径路由协议CBM-AODV,该协议结合了端到端的成功投递率和链路质量两个度量提高路由的可靠性、增强通信链路的寿命,使其能够有效预防链路断裂,降低路由修复的成本。文献[5]侧重于多径路由多跳通信的改善,解决了链路稳定性问题,并且提出LLA方法来寻找更为稳定的通信路径,使路由符合Qo S的要求,能够提供实时安全信息服务。文献[6]提出AODV-DFR协议,该协议将定向转发机制和基于地理位置的贪婪转发机制结合,设计一个混合路由方案的定向转发,把节点的位置信息作为路由更新的依据。文献[7]提出AODV-ETX协议,该协议结合期望传输次数(ETX)和跳数两种影响因素选择一条链路质量最好的路由。文献[8]在路由寻找时考虑路侧辅助单元RUS,把连通时间最长的两条路径作为最优、次优路径,同时设置路径阈值,当链路连通时间超过阈值时自动进行最优、次优路径切换,降低链路断裂的几率。文献[9]分析影响路由性能的因素:车辆速度、车辆密度和车辆节点数,基于AODV协议引入群协议进行路由的选择,使数据包能够以高效稳定的传输到目的节点。文献[10]提出了G-AODV协议,该协议将周围邻居节点分为强邻居节点和弱邻居节点自适应发送HELLO;在此基础上按照稳定性和链路长短因素提出主路由和备选路由,提高路由稳定性。文献[11]提出LED-AODV协议,该协议在路由寻找过程中考虑转发角度,减少RREQ发送数目;在路径建立过程添加了路由持续时间进行对路径能持续时长的预测,进一步提高路由稳定性能。

为克服原有AODV协议本身的缺点,提高路由稳定性,降低因链路断裂造成的路由修复成本,本文在结合现有路由协议的基础上,提出一种具有稳定链路的改进AODV路由协议(AODV with Stable Link,AODV-SL)。该协议利用车载GPS定位,在路由发起时结合车辆的相对速度、转发角度及节点负载提出节点稳定度(St);在路由选择时选择链路质量(LQ)最高的两条路径作为最优、次优路径,提高路由稳定性;在路由修复时,既采用最优、次优路由直接切换方式,又采用在同向邻居节点、反向邻居节点进行本地修复方式,节约路由修复成本。仿真结果表明,路由协议AODV-SL对比于AODV以及混合式位置路由协议(Hybrid Location-based Ad hoc Routing,HLAR),在平均端到端时延、数据包投递率和标准化路由开销上都有所改善。

2 AODV-SL协议流程及设计

2.1 节点度量

在经典AODV的路由寻找环节综合考虑了车辆的相对速度、源节点和目的节点以及中继节点构成的转发角度、节点负载等影响路由稳定性的关键因素。将这几种关键因素通过归一化的综合加权方式设计出节点稳定度(St),比较节点稳定度大小选择是否再次转发RREQ报文。设节点i的Ni个邻居节点j构成集合为Φi,将定义节点度量St为

其中,j=1,2,…,Ni;β1,β2,β3为权重因子,且有β1+β2+β3=1;υijnormal、φijnormal及ψijnormal分别为以节点i的视角下其邻居节点j的归一化相对速率、归一化转发角度及归一化节点负载,分别定义如下。

设节点i和其邻居节点j的速度分别为矢量,则归一化相对速率υnormalij定义为

其中,j=1,2,…,Ni;υmax为车辆间最大相对速率,例如城市环境下车辆最大允许速率为60km/h,则车辆间最大相对速率为120km/h。

设节点i、邻居节点j以及目的节点d的坐标为(xi,yi),(xj,yj),(xd,yd),则以节点i为顶点,以节点i-节点j,节点i-节点d为边构成的夹角φi为

则归一化转发角度φijnormal可定义为

其中φmax为最大转发角度,取π。

设邻居节点j的负载为Qi,即该节点缓存队列中存储的数据包个数。令Qmax表示节点缓存的队列总长度,即允许存储的最大数据包个数,取64[12]。则归一化节点负载ψijnormal为:

2.2 路由发起

源节点需要与目的节点进行通信时,AODV-SL通过向邻居车辆广播RREQ发起路由,AODV-SL协议的具体流程如图1所示。接收到RREQ包的节点首先查看是否为环路,是则丢弃该报文;然后查看接收到的报文是否为重复的RREQ,是重复包则丢弃该报文;再查看是否与源节点建立反向路径,否则直接建立反向路径;最后在其邻居列表中获得一跳通信范围内邻居节点的位置、速度及角度(这些运动信息通过HELLO消息周期性的进行信息交互存储于邻居列表中),接收到RREQ的邻居节点通过归一化综合加权的方法计算中继节点的节点稳定度(St),判断自身稳定度是否符合继续参与路由寻找的条件,并将节点稳定度通过累加方式存储在路由请求报文中。具体过程为节点通过归一化综合加权的方法计算节点稳定度,比较节点稳定度与随机数(处于0~1)的大小,稳定度大于随机数将继续参与RREQ的转发,并将满足条件的节点稳定度采用累加的方式存储于RREQ报文中继续广播给下一跳邻居节点,继续参与路由寻找,直到路由请求报文达到目的节点;而节点稳定度小于随机数的节点将放弃继续参与路由寻找过程,减少了路由寻找过程中不满足节点稳定度的节点数,节省了网络资源。在比较节点稳定度与随机数大小时可能存在以下几种极端情况:①当节点稳定度很小但大于随机数从而被选为下一跳中继节点的情况,虽然从一跳看可能该节点会造成链路不稳定,但在AODV-SL中目的节点通过计算链路质量LQ的大小选择最终的最优、次优路由,目的节点通过这种方式在一定程度上补偿了误判带来的性能损失;②邻居节点的节点稳定度都小于随机数,即下一跳中继节点中不存在满足继续路由寻找的条件,该节点将通过存储-携带转发的方式承载着RREQ行驶一段距离后再采用AODV-SL路由发起的方式寻找下一跳满足继续寻找路由的中继节点;③节点稳定度较高但小于该节点产生的随机数,此时该节点将不再参与路由寻找过程,若该节点后续又收到其他节点发送的RREQ时,将重新与随机数比较,而高稳定度的节点连续多次小于随机数的概率很小。AODV-SL协议与AODV协议不同的是,在AODV-SL协议中,接收到RREQ的中继节点本身不是目的节点,但拥有到达目的节点的路径的节点,也将通过上述方法计算出节点稳定度,重新选择是否转发RREQ,原因在于该中继节点虽然有到达目的节点的路径,但由于该路径没有考虑相对速度、转发角度和负载等因素,其路由稳定性不是最好的。

相邻节点间的节点稳定度越大两节点越稳定,节点间发生断裂的几率越低,节点稳定度大小运用归一化综合加权的方法,考虑影响稳定性的因素,如相对速度、转发角度和节点负载因素,使得每跳参与路由寻找的节点具有相对较高的节点稳定度。在AODV-SL路由协议中,当源节点需要与目的节点建立通信时,向通信范围内的邻居节点广播RREQ,RREQ请求报文包含数据包类型、跳数、目的地址、目的节点序列号、源地址、源地址节点序列号、路由请求ID、数据包最大生存时间TTL、节点稳定度累加和。通过这种方式发起路由请求有两点优势:①确保了在路由选择过程中每跳选择的转发节点都具有较高的节点稳定度,降低了因链路断裂的风险;②因为不满足稳定度条件的节点将不再参与路由发起过程,避免了RREQ报文简单的进行全网广播,减少了路由请求包RREQ的转发数目,提高了无线信道带宽的利用率。

2.3 路由选择

选择节点稳定度较高的方法发起路由寻找,并将节点稳定度的累加和封装在RREQ包中,直到RREQ请求包到达目的节点。AODV-SL路由协议在路由选择过程中具体实现流程如图2所示。AODV-SL中目的节点第一次收到RREQ请求包后,将等待一个路由发现周期[13](源节点寻找目的节点允许的最大路由请求时间)接收后续发送的有效RREQ包。在等待时间内会有多条连通源节点与目的节点的路径,因此目的节点会收到多个RREQ报文,获取RREQ包中的节点稳定度累加和,同时结合整条路径所经历的跳数设计出链路质量(LQ),由链路质量的大小评估路径稳定性的高低。最终由目的节点挑选链路质量最高的两条路径作为AODV-SL协议的最优、次优路径,同时产生对应的路由应答报文RREP,在路由应答报文中除了目的节点ID外还将获取到最优、次优路由上所有节点的ID,即最优、次优路由上的任意节点都能知晓两条路由上的所有节点ID,修改该报文的目的是为后续的AODV-SL路由修复做准备。

设从节点i到节点d有Nr条链路,并设其中第m条链路包含Nhm跳,其中m=1,2,…,Nr。定义第m条路径的链路质量为LQm,Stmn为第m条路径第n跳的节点稳定度,其中n=1,2,…,Nhm,则有

如式(6)所示,路径的稳定度累加和越大或跳数越少,链路质量越好,链路稳定性越高;反之,链路稳定性越低。由上述方式选择的路径稳定性比传统的AODV更加可靠,因为克服了传统AODV中选择最优路径仅依赖于最少跳数而没有考虑运动状态因素对路由稳定性影响的缺陷。AODV-SL协议由于在路由发起过程中选择每跳中继节点稳定度是相对较高的,而且目的节点进行路由选择时通过比较每条连接源节点到目的节点的链路质量LQ,选择了链路质量最高的两条路径作为最优、次优路由。

AODV-SL路由选择过程包含反向路径与正向路径的建立。参与转发RREQ请求包的中继节点将主动与源节点建立反向路径,目的节点选择链路质量最高的两条路径沿着反向路径产生路由响应包RREP。在AODV-SL协议中,RREP回复包中除了封装有关目的节点信息、源节点信息和跳数外,还将链路质量LQ和所有参与最优、次优路由的节点ID存储在RREQ包中,以便最优、次优路径中的各节点都能掌握两条路由上的所有节点ID,其目的主要用于路由修复过程。RREP报文包含数据包类型、跳数、最优及次优路由所有节点ID、链路质量LQ、源节点及目的节点地址、数据包生存时间TTL。AODV-SL协议的正向路由建立是通过中继节点计算节点稳定度选择是否对路由请求包进行转发,直到目的节点接收到请求包为止。AODV-SL协议在第一次响应了路由请求包后将在以下两种情况进行路由更新:①当目的节点后续收到RREQ请求包后,通过比较链路质量的大小,当后续的链路质量大于原有最优或次优路径的链路质量时,目的节点响应路由请求,产生路由请求包RREP并发送给源节点,更新原有路径;②当后续产生链路质量与原来的最优、次优路径相同时,比较路径中跳数的多少,在相同链路质量条件下,跳数较少的路径比跳数较多的路径具有更高的稳定性,因此更新原有路径。

2.4 路由修复

AODV本地路由修复机制基本原理是当路由上某个节点检测到下游节点处于非连通状态时,该节点将启动本地路由修复过程,寻找是否有到达目的节点的路径,若存在则本地修复成功,若不存在则向源节点发送RRER错误报文。AODV本地路由修复存在的弊端之一是最大路由修复长度的取值将直接影响到修复报文的传播范围,进一步影响该协议的性能如端到端平均时延、分组投递率、路由请求频率及路由开销;另一个弊端是修复后的路由长度将大于原来路由[14],因此AODV-SL在AODV本地路由修复的基础上做了改进,快速处理数据传输时检测到链路处于断路的突发情况。

根据道路上车辆行驶的运动方向与最优、次优路由方向是否相同,可将断裂处上游节点的邻居节点分为同向邻居节点和反向邻居节点。断裂处上游节点的邻居节点中运动方向与原路由方向相同的节点称为同向邻居节点;而运动方向与原路由方向不同的节点称为反向邻居节点。

在AODV-SL路由选择过程中,只有链路质量LQ最高的两条路径或者后续需要更新路径时目的节点才会产生路由响应,回复RREP报文。在AODV-SL中,RREP报文除封装目的节点信息、源节点信息和跳数等基本信息外,还存储了链路质量LQ及最优、次优路由上所有节点的ID,即最优、次优路由上的任意节点都能知晓两条路由上所有节点的ID。

在AODV-SL协议中数据包首先沿着最优路由发送数据包,当路由维护过程中检测到最优路由上某节点处于非连通状态,断裂处上游节点由于知晓次优路由上所有节点ID,首先查看其邻居列表中是否有次优路径上的任一节点ID(邻居列表中的信息在路由维护过程中周期性发送HELLO消息获得,从而实现相邻节点间信息的交互),若存在则直接将正在发送的数据从最优路由上切换到次优路由上进行传输,由断裂处的上游节点直接启动次优路由。由于车载网中的路由协议受道路的限制(双向六车道的道路设每个车道为5m,其宽度不会超过30m),AODV-SL在路由寻找过程中挑选的最优、次优两条路由可能存在公共的转发节点,即同一节点既在最优路由上,也在次优路由上;对于最优、次优路由而言,其节点稳定度和链路质量相差不大,次优路由上的某些节点也会是最优路由上某些节点的邻居节点,所以最优路由上断裂处上游节点的邻居列表中可能存在次优路由上某节点ID。如果最优路由断裂处上游节点的邻居列表不存在次优路由上的节点ID,则在同向邻居节点和反向邻居节点中启用本地路由修复,优先在同向邻居节点中启用路由修复,若同向邻居节点中路由修复失效,则在反向邻居节点中启动路由修复。若次优路由上某处节点也发生断裂时,则次优路由上断裂处的上游节点也同样在同向邻居节点和反向邻居节点中启动路由修复。

AODV-SL路由修复的具体流程如图3所示。若检测到最优路由某断裂处上游节点的邻居节点中不存在次优路由上节点ID或者次优路由也发生断裂后,断裂处的上游节点将优先在同向邻居节点中采用存储-携带-寻找-转发的方式启动本地路由修复。上游节点先存储正在发送的数据包;然后携带该数据包并在同向邻居节点中点依次由近及远以原路由建立的中继节点为目的节点发起路由请求报文RR-RREQ(Route Repair RREQ),若能从上游节点寻找到达以原路由中继节点为目的节点的路由,则正向路由修复成功,产生路由修复应答报文RR-RREP(Route Repair RREP)给断裂处上游节点;最后将存储在断裂处上游节点的数据包沿着修复路径传给目的节点。如果在同向邻居节点中本地路由修复失效后,则在反向邻居节点中也同样采用存储-携带-寻找-转发的方式进行本地路由修复。如果在同向邻居节点、反向邻居节点中能够寻找到以原路由中继节点为目的节点的路由,则本地路由修复成功;如本地路由修复失败后,则断裂处节点向源节点发送RRER报文,由源节点重新发起路由寻找。

3 性能仿真及分析

3.1 仿真环境设置

为了使AODV-SL路由协议的运动场景更接近真实模型,首先通过交通模拟仿真器SUMO生成城市环境道路图,接着将SUMO文件导入到NS2中。如图4所示,包含了12个交叉口且道路为双向8车道的道路图,车辆在道路上是随机分布的,且车辆的行驶轨迹遵循改进的Krauss跟驰模型,能够在不同道路上行驶。交通仿真参数如表1所示。

当SUMO文件嵌入NS2后,依据表1参数对双向8车道的道路图追踪1500×1500米仿真场景,仿真场景中的节点数从60辆到300辆不同节点数进行性能分析,通过多次测量取平均值的方法作为最终的AODV-SL路由协议的性能分析,在仿真场景中包括单一路由和交叉口,图4方框内为某个交叉口在某时刻1500×1500米仿真场景的道路放大图。在城市环境下车辆的最大运行速度变化为16.7m/s,模拟仿真时间为500s,使用数据流生成工具cbrgen生成CBR业务流,CBR包大小为128字节且数据流速率为4packet/s,节点的停留为0秒,仿真时使用OTcl语言编写NS2中的脚本语言,节点的具体无线仿真参数设置如表2所示。本次实验模拟网络拓扑中节点数从60变化到300比较AODV-SL路由协议和混合路由协议HLAR[2]及AODV路由协议在数据包投递率、平均端到端时延、标准化路由开销上的不同。

3.2 平均端到端时延

平均端到端时延定义为数据包从源节点到达目的节点的总时间与接收到数据包的比值,它包括数据包的传播时延,在队列中等待发送的时延,信道接入时延以及链路断裂后路由修复的时间,平均时延越低,路由协议性能越好。该性能指标反映路由协议运行快慢,影响路由时延的因素包括路由寻找时间、数据包的传输时间、排队等待时间以及路由断裂后路由修复时间。如图5所示为AODV-SL路由协议和HLAR路由协议、AODV路由协议的平均端到端时延性能曲线。整体上看随着节点数的增加,车辆密度流增大,网络拓扑变化相对较小,路由稳定性增强,因此端到端的平均时延大体有所下降。在节点数小于120辆时,三种路由的平均时延相差不大,原因在于车辆处于稀疏场景中,容易造成链路断裂,三种路由都因链路断裂消耗了大量的路由修复的时延,AODV-SL和HLAR两者都有修复机制,所以时延小于AODV协议;AODV-SL在路由修复时既采用从最优路由到次优路由直接切换的方式,又采用在同向邻居节点和反向邻居节点中进行路由修复的方式,节省了路由修复时间,HLAR路由没有最优路由到次优路由的直接切换方式,所以AODV-SL平均时延小于HLAR。随着节点数的增加,车流量密度也随之增大,网络拓扑越来越稳定,三种协议的平均时延差距增大的原因有以下两点:①随着节点数的增加,车辆之间进行其他业务量增大,节点本身负载增大,在AODV-SL路由协议中选择节点负载相对较小的节点,减少了排队时间和信道竞争时间,而HLAR通过计算网络开销率的大小衡量节点的负载,选择网络开效率越小的节点参与路由选择;②AODV-SL在路由寻找时考虑了车辆的相对速度、转发角度和跳数,对比于AODV仅仅考虑跳数而言,AODV-SL提高了路由稳定性,降低了路由断裂几率,缩短了因链路断裂造成的路由修复时间,因此随着节点数增大,AODV-SL和HLAR协议的优势越明显;而当节点数大于240时AODV-SL和HLAR的平均时延缓慢下降而AODV的时延却反而上升,原因在于随着节点数的增大,节点间进行其他信息交互频繁造成网络拥塞,AODV没有考虑节点本身负载,造成排队等待时延和MAC接入时延都增大,所以平均时延呈上升趋势,而AODV-SL在路由寻找时选择负载较小的节点,HLAR通过控制网络的开销率尽量避免了负载较大的节点传输数据。AODV-SL的平均时延小于HLAR是因为AODV-SL除了控制节点负载外,还考虑了节点相对速度和转发角度,提高链路稳定性,节省了路由修复时间。

3.3 数据包投递率

数据包投递率定义为目的节点接收到数据包个数与源节点发送数据包个数的比值,该性能间接反映路由协议能够支持的最大吞吐量,同时衡量网络中数据传输的可靠性。影响路由协议的数据包投递率因素有节点队列达到最大承受负载而不得不做出丢包处理,路由不稳定引起的链路断裂也是影响分组投递率的重要因素。如图6所示为三种路由协议的分组投递率的性能比较,当车辆节点数小于120时处于稀疏环境,网络拓扑变化快,导致路由稳定性差,发送数据包过程中由于链路不稳定容易引起数据包的丢失,三种路由协议的分组投递率相差不大且变化平缓。当节点数从120变化到240时,车流量密度增大,网络拓扑变化相对较小,路由稳定性提高,三种路由协议的分组投递率相差越来越大,一方面是由于AODV-SL在路由发起过程中考虑了节点本身的运动状态,只有那些节点稳定度符合条件的节点才继续参与路由寻找,在路由选择时目的节点通过比较链路质量LQ的大小,选择链路质量高的两条路径作为最优、次优路由,这在很大程度上提高了路由的稳定性,提高了端到端的投递率;另一方面AODV由于没有考虑车辆的运动状态仅仅考虑最小跳数充当最优路由容易引起链路断裂且在城市环境中障碍物的阻挡,链路断裂在所难免,AODV-SL在路由修复时既采用最优路由、次优路由直接切换方式,也启用在同向邻居节点和反向邻居节点中进行路由修复方式,这两方面的原因使得AODV-SL的分组投递率高于AODV;HLAR在路由选择时没有考虑速度、位置和角度等运动状态对路由稳定性的影响,链路稳定性低于AODV-SL,所以HLAR的分组投递率性能低于AODV-SL。当节点数大于240时,AODV路由协议的分组投递率呈下降趋势而AODV-SL和HLAR协议仍缓慢上升,原因是当车流量很大时,AODV-SL和HLAR在路由选择时考虑了节点本身负载,选择节点负载相对较小的节点作为路由的中继节点,而AODV由于没有考虑节点负载使得车辆密度流很高时因为发生碰撞而做出丢包处理,导致一部分正在发送的数据包被迫丢弃,因此AODV的分组投递率呈下降趋势。

3.4 标准化路由开销

标准化路由开销定义为在路由寻找和路由维护过程中,控制报文数目与目的节点接收到总分组数目的比值,在路由寻找和路由维护中发送的控制报文数目越少,目的节点接收到的数据包个数越多,则路由开销越小。图7所示为AODV-SL和HLAR、AODV路由协议的标准化路由开销性能曲线。整体上随着节点数的增加,三种路由协议在路由寻找与路由维护过程中需要发送的控制报文增多,因此路由开销随着节点数的增加而增大。当车辆节点数小于120时,车流量密度较稀疏但仍保持一定的连通性,此时参与转发的节点数不多,在路由寻找和路由维护过程中耗费的控制报文不多,同时由于网络拓扑不稳定容易引起链路断裂,分组投递率较低,使得三种机制的路由开销性能相近。当节点数超过120时,一方面随着节点数的增加,路由稳定性增强,接收端接收到的数据包总数增大,但随着节点数的增加,在路由寻找过程中发送的路由请求报文增大,且路由维护过程中信标消息得到数量会增大;另一方面AODV-SL在路由发起过程中通过比较节点稳定度与随机数的大小,只有节点稳定度满足继续寻找路由的条件才转发RREQ,不满足节点稳定度的将不再参与路由寻找过程,HLAR路由协议运用数据包发送率、带宽大小和数据包大小设计网络开销率减少控制报文的数目,这相比于AODV通过全网广播RREQ寻找路由而言,AODV-SL和HLAR在很大程度上减少了RREQ控制报文的数目,且AODV-SL在路由寻找时考虑了车辆的相对速度、转发角度,提高了路由稳定性,降低了链路断裂的几率,路由维护过程中的控制报文也随之减少,因此AODV-SL的路由开销小于HLAR和AODV的路由开销。当节点数再增大时,AODV-SL的路由开销变化平缓而AODV却快速上升。这是由于当车辆处于密集场景中AODV-SL在路由寻找时只有满足节点稳定度条件的节点转发RREQ,但目的节点接收到的数据包增大,控制报文的增长速率小于接收端的数据包增长速率,所以AODV-SL路由开销变化平缓;来而AODV在车辆密集场景中仍然通过全网广播RREQ,且在路由修复过程中也采用相同方式发送路由修复的请求报文,增加了路由开销同时也给整个网络带来了沉重负担,因此AODV的路由开销的增长速度随着车辆节点数的增加而递增。

4 结束语

为了解决车载自组织网中由于拓扑动态变化导致路由链路不稳定的问题,以AODV为基础并针对其缺陷提出具有链路稳定性的路由协议AODV-SL。该协议在路由寻找中,结合节点稳定度和跳数设计链路的质量,选择最优、次优路由以提高数据包投递率,增加路由稳定性;在路由维护中既采用最优、次优路由直接切换的方式,也采用在同向邻居节点和反向邻居节点进行路由修复的方式,减少路由修复时间,从而降低端到端传输时延并减小路由开销。通过仿真模拟了AODV-SL的平均端到端时延、数据包投递率和标准化路由开销的性能,并与传统的AODV协议以及HLAR进行比较分析,仿真结果表明AODV-SL能够整体提高路由性能,使其更好适应于车载自组织网络。

摘要：车载自组织网中节点拓扑动态变化,针对节点间链路不稳定从而影响路由性能问题,提出了具有稳定链路的改进AODV路由协议。该协议构造了由车辆间相对速度、转发角度以及节点负载等关键因素组成的节点稳定度(St)参量;以节点度量为基础,引入随机数筛选机制完成中继节点的选择;进一步构造链路质量度量(LQ)参量,选择最优及次优路由提高数据包投递率;在路由修复中,使用断点修复机制完成最优及次优路由间快速切换以及断链修复,降低网络开销及数据传输延迟。仿真表明,AODV-SL在平均端到端时延、数据包分组投递率以及标准化路由开销上都优于AODV及HLAR路由协议。

AODV协议 篇4

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.

AODV路由协议断链修复的改进 篇5

Ad Hoc网络是一种没有固定基础设施支持的移动网络, 网络中的节点均由移动主机构成, 每个节点既可以作为终端节点, 又可作为其他节点之间相互通信的路由器。它是一种移动通信和计算机网络相结合的网络, 是移动计算机通信网络的一种类型。Ad Hoc网络与一般网络相比有着自身的一些特点:网络独立性、动态变化的网络拓扑结构、有限的无线通信带宽、有限的主机能源等, 因此, 适用于Ad Hoc的路由协议必然也与传统有线网络的路由协议有着明显的不同。目前对于Ad Hoc路由协议的研究已经很多, 其中AODV (AdHoc On-Demand Distance Vector Routing) 是Ad Hoc中一种及其重要的路由协议, 其技术成熟, 而且是近年来Ad Hoc路由协议研究的热点。AODV吸收了DSR和DSDV的优点, 是DSR与DSDV的完美结合。AODV允许中间节点响应RREQ。发现路由后, 中间节点或目的节点以单播的方式向源节点发送一个RREP分组, RREP沿着刚建立的逆向路径传输。因此, AODV不支持单向链路。在路由维护阶段, 当源节点得到链路中断消息后重启路由发现过程。AODV的显著特点是引入了组播路由协议扩展, 并通过序列号的方式解决了无限计数问题, 避免了环路的产生。但它需要定期地发送hello报文, 造成了一定的额外开销。AODV使用了分布式的、基于路由表的路由方式, 所以建立路由表项以后, 在路由中的每个节点都要执行路由维持、管理路由表的任务, 在路由表中都需要保持一个相应目的地址的路由表项, 实现逐跳转发。

2 A O D V路由协议断链修复的分析

由于Ad Hoc网络有其自身的特点, 动态变化的拓扑结构, 使其不能像常规路由协议那样维护完整的路由表, AODV中每个节点都只维护一个到目的地址的路由。传统的AODV在发现路由断路时使用源节点恢复的办法, 即当RERR传回到源节点, 告知路由已断时, 源节点重新发现路由。该方法虽然可靠但时延很大, 所以最新的AODV中提到了本地修复 (local repair) 的思想, 由于造成断路的节点可能仍然在附近, 因而断链处的上游节点可使用生存时间 (TTL) 比较小的RREQ广播来修复路由。在节点移动性不大、网络拓扑结构变化不剧烈时, 使用本地修复技术可以减小时延, 提高效率。

目前已提出了不少基于AODV的本地修复算法, 文献[1]中首先对路由表做了修改, 将路由表项增加了下两跳结点IP地址域, 保存到达目的节点路径上的下两跳节点的地址。当下一跳链路无效时, 若下两跳节点有效, 则发送本地修复的路由请求分组, 目的地址就是下两跳节点的IP地址;其次, 对RREQ、RREP、RRER分组进行了改动。为了使路由本地修复时能在路由表中获得下两跳节点的地址, RREQ、RREP、RERR分组中分别添加了前两跳节点的IP地址字段, 其他字段均无变动。另外, 为了进行路由的本地修复, 新增加了本地修复的路由请求分组Repair_RREQ、路由应答分组Repair_RREP、NO-TICE分组。节点进行本地修复时, 路由请求是以下两跳节点为目的节点, 但还应该携带修复的路由的真实目的的信息。于是, Repair_们RREP分组在RREP分组基础上添加了以下字段:真实目的节点的IP地址和序列号, 下两跳节点到达真实目的节点的跳数。NOTICE分组用于修复以后修改下一跳节点到目的节点的序列号。此改进将修复限制在断链的局部范围内, 减少了修复时间, 降低了路由开销。但在AODV协议中, 源节点通过广播RREQ信息来查找到通往目的节点的相应路由, 在源节点向目的节点广播RREQ的过程中, 收到RREQ的节点建立起到源节点的反向路由, 但源节点只有接受到目的节点发送的RREP时, 才知道已经建立起通向目的节点的路由。可见, 路由都是通过接收到的数据分组或者控制信息反向建立的, 真正起到建立到目的节点可用路由的作用的是反向发送回来的RREP。而RREQ只是起到查找目的和通知目的回馈RREP的作用, 要想建立一条到目的的路由, 必须在同一路径上来回传输RREQ和RREP才能实现。显然, 在路由建立时取消RREQ的使用是不可能的, 但当目的节点已经接收到源节点发送的RREQ并向源节点发送了RREP, 源节点在还未接收到RREP的时候发生断链时, 由于目的节点在接收到RREQ以后已经知道自身是传输的目的和通向源节点的路由, 甚至在这条路由中的中间节点也知道自己是一条活动路由的中间节点, 所以不必再使用RREQ进行查找和通知目的发出RREP, 而是直接利用已经建立起来的逆向路由对断链进行修复, 这样可以有效利用已经建立起来的逆向链路资源, 避免资源浪费。由于只有当源节点真正接受到了目的节点发送过来的RREP, 源节点到目的节点的链路才算真正建立, 所以把这种发生在目的节点向源节点发送RREP的过程中的断链修复叫做预修复。可以看出文献[1]中对于链路本地修复的改进是在链路建立以后。通过以上分析, 可以把链路修复分成2部分:从目的节点接收到RREQ到源节点接收到RREP之间的链路修复 (预修复) 以及源节点接收到RREP以后的链路修复。本文源节点接收到RREP以后的链路修复也采用文献[1]中的方法。以下着重介绍从目的节点接收到RREQ到源节点接收到RREP之间的链路修复 (预修复) 方法。

3 预修复链路修复方法

本修复方法针对文献[1]的改进是: (1) 采用多路径。图1中N2、N4间存在2条路径, 分别是N2、N3、N4和N2、N6、N4, 即N4会收到2条N1经N2转发的目的节点为N5的RREQ, N4的缓冲区中有2条下两跳节点的地址为N2的记录; (2) 采用链路预修复方法。即在RREP传播过程中出现断链立即进行修复。

如图1所示, N1为源节点, N5为目的节点。当N5收到N1发送过来的RREP后, 在向N1发送RREP的过程中在N4到N3之间发生断链时, 找到断裂处的上游节点N4, 从路由表中找到下两跳节点的地址N2。此时N4查找缓冲区中的路由表, 若存在下2跳节点为N2的其他记录, 则N4从该逆向路由转发RREP到N2。否则, N4针对下两跳节点N2发送RREP的广播消息。每个节点接收到RREP消息后, 检查自己的路由表, 看是否有通向N2的可用路由, 如果没有相应表项, 则在路由表中创建相应表项并转发;若有相应路由表项, 但是目的状态是不可达的, 则根据RREP的消息内容来更新路由表;如果路由表中有相应的到N2的路由信息且是可用的, 则RREP沿此路径, 继续往下传播, 证明已经找到了下两跳节点N2, RREP从节点N2继续向节点N1传播下去。当RREP传播找到节点N2以后, 一方面沿到节点N1的路径继续传播, 以便建立N1到N5的正向路径;另一方面, 由于RREP从节点N4到节点N2传播的过程中已经建立起了N2到N4的路径。所以此时只需从节点N2向节点N4发送一个SIGNAL即可, 目的是通知节点N4不要再广播RREP, 以免造成资源浪费。

4 性能分析

通过仔细分析链路建立的过程, 发现AODV协议中一条链路的建立必须经过从源节点向目的节点发送RREQ广播, 当目的节点收到RREP后再向源节点发送RREP单播的过程。当源节点接收到从目的节点发送过来的RREP之后, 源节点与目的节点之间的链路才算真正建立起来。文献[1]中只是针对当链路真正建立之后如果出现断链如何进行修复, 忽略了由于当目的节点接收到源节点发送来的RREQ, 已经建立起了目的节点通向源节点的逆向链路, 所以当目的节点向源节点发送RREP的过程中如果出现断链, 同样是可以修复的。本文提出把断链修复分成2部分。从目的节点接收到RREQ到源节点接收到RREP之间的链路修复 (预修复) 和源节点接收到RREP以后的链路修复。这样可以有效地扩大断链修复的范围, 充分利用已经建立起来的逆向链路。本文在源节点接收到RREP以后的链路修复中仍采用文献[1]中的方法, 另外本文提出了从目的节点接收到RREQ到源节点接收到RREP之间的链路修复 (预修复) 的思想, 同时采用多路径技术, 提高了断链修复效率, 对文献[1]中的方法是有效的改进。另外引用了一个SIGNAL分组, 简化了第一部分的NOTICE分组。此改进可以充分地利用已经建立起来的逆向链路资源, 对于文献[1]是一个有效的补充。

5 结语

以上提出的思想, 补充了以前断点修复只有当链路建立起来以后, 如果出现节点断裂才进行修复的一贯思路, 提出断点修复, 应该在链路建立之前, 如果目的节点已经收到RREQ, 但是它发送的RREP还没有发送到源节点的时候链路出现断裂, 也应该修复。把断点修复分为2部分, 同时采用多路径技术, 这种对断链修复的改进可以更有效利用资源, 降低了节点建立连接的时延, 使性能获得一定程度的提高。这样有效利用了原来建立好的链路。节省了资源, 缩小了时延, 对断点修复是一种新的启发。

摘要：AdHoc网络 (MANETs) 是一种没有固定路由器、所有节点自由移动, 且都能以任意方式动态地与其他节点保持联系的新型网络, 是移动通信和计算机网络的交叉。AODV是MANETs网络层的一种典型路由协议, 针对其断链修复问题, 已提出的改进协议多是采用修复链路建立后出现的断链, 因此, 提出了一种改进协议, 在链路建立之前即开始对出现的断链进行修复。与过去的改进协议相比, 可以使断链修复的范围扩大, 有效利用已经建立起来的逆向链路, 从而节省了网络资源, 缩短了链路建立时延。

关键词：移动AdHoc网络,AODV协议,断链修复

参考文献

[1]肖百龙, 郭伟, 刘军, 等.AODV的本地修复算法[J].计算机应用与研究, 2007 (3) :231-233, 237.

[2]朱金华于宁宁.无线自组织网络AODV路由协议研究[J].微型计算机信息, 2007 (18) :122-124.

[3]周颜, 李国伟.AODV路由协议局部修复机制的改进[J].中原工学院学报, 2006 (1) :73-75.

[4]洛琨, 张远.AODV与DSDV路由协议性能仿真与比较[J].计算机仿真, 2006 (2) :118-120, 191.

[5]陈玲, 王华.移动Adhoc网络路由协议的研究——一种基于AODV路由协议的改进算法[J].微计算机信息, 2006 (3) :167-169, 202.

[6]关媛, 王振中, 陆建德.带路径收集的移动自组网AODV协议优化[J].计算机工程, 2007, 33 (3) :119-121, 135.

[7]丁莹, 元道华, 尚亚灵.AODV局部连接性管理的性能分析及其改进[J].四川大学学报, 2006, 43 (6) :1241-1247.

[8]张远, 郭虹, 刘洛琨.AODV协议中扩展环搜索与邻节点列表的实现[J].计算机工程, 2006, 32 (10) :113-115.

[9]吴丽杰, 钱雪忠, 窦维江.基于AODV的能量有效路由协议[J].微电子学与计算机, 2006 (10) :219-221.

[10]李吉吉, 刘军.基于AODV协议的自组网络安全机制的研究[J].电子学报, 2006 (2) :272-276.

[11]杨锦亚, 郭红, 胡捍英.自组网路由协议性能比较[J].微计算机信息, 2006, 22 (24) :196-198.

AODV协议 篇6

Adhoc网络是一种无需架设基础设施的无线自组织网络,具有组网灵活快速、抗毁性强和使用方便等特点,广泛应用于抢险救灾、战场等地理环境恶劣的特殊场合[1,2]。Adhoc网络中的移动节点地位平等,且兼具主机和路由器两种功能,节点之间的数据通信需要其他节点进行转发[3,4,5],这就要求在这些节点上运行相应的路由协议。

目前,路由协议的设计与优化是Adhoc网络的研究热点之一,典型的有DSDV(目的节点序列距离矢量)、DSR(动态源路由)和AODV(Adhoc按需距离矢量)等路由协 议[2,3]。其中,AODV是最适合Adhoc网络的路由协议[5],但AODV在路由建立过程中采用广 播洪泛的 方式转发RREQ(路由请求)消息,在网络节点比较密集的情况下很容易引发广播风暴进而使得网络堵塞,造成整体网络性能下降,同时过多地重传不必要的RREQ消息还会加速损耗节点的电池能量,缩减网络的存活时间。本文提出一种基于动态概率转发RREQ消息的方案,该方案的主要思想是利用AODV路由协议中的Hello消息机制来统计节点的邻节点数,并依此来判定以该节点为中心的区域网络的疏密状况,然后用不同的概率转发RREQ消息。

1AODV路由协议的工作机制

1.1AODV路由的建立

AODV是一种按需路由协议,当某个节点需要发送业务数据时,如果在它的路由缓存中没有到达目的节点的活动路由,则会通过广播RREQ消息发起寻找到达目 的节点的 路由。当某 节点X收到RREQ消息时,若自己不是目的节点且没有转发过该RREQ消息,则向其邻节点(信号覆盖范围内的节点)广播转发该RREQ消息;若自己就是目的节点或者其路由缓存中存在一条到达目的节点的活动路由,则发送RREP(路由应答)消息回复其上游节点[6,7],并随之建立一条正向路由,至此源节点就可以利用正向路由发送业务数据到目的节点。

1.2AODV的Hello消息机制

Adhoc网络中的节点是不断移动的,因此网络的拓扑结构也在不断变化,这很可能使前期建立的路由失效。AODV路由协议采用Hello消息机制实现对路由状态的检测[6]。

在AODV路由协议中,节点会周期性地向其邻居节点广播Hello消息来检测路由连通性,该消息实质上是一个特殊的RREP包,其目的IP地址为本节点的IP地址,因其TTL值为1,因此该消息只能被本节点的邻节点接收[5,6,7,8]。邻节点接收到Hello消息后会检查自己与发送该消息的节点是否存在活动路由,如果存在则更新该路由的生存时间;如果没有则新建一个到该节点的路由。如果一个节点在指定的时间间隔内没有 收到邻节 点的Hello消息,则表明该邻节点已不在其通信范围内,与该邻节点的路由失效。

1.3AODV路由协议的缺陷

在AODV路由协议建立路由的过程中,所有接收到RREQ消息的节点都要对该消息进行检查并决定是否继续转发该消息,一个RREQ消息在具有N个节点的网络中广播的次数是N -1次。由于所有节点都以广播的方式转发,因而在业务繁忙的时候很容易引发网络广播风暴,导致网络阻塞,造成网络业务数据传输延迟,加剧节点能源消耗,使得某些节点因电池能源耗尽而提前“死亡”,从而缩短了整个网络的生存时间。

2基于动态概率的AODV路由协议

2.1相关研究

文献[3-4]研究证明,一个节点向它相邻的某个节点转发一个RREQ消息所能增加的有效信号覆盖范围最大约为61%,平均约为41%。当该节点的邻节点数达到4个以上时,重传RREQ消息能增加的有效信号覆盖范围将下降到5%以下,并快速趋于0。这就是说,在一个稠密的Adhoc网络中,广播RREQ消息将会产生大量无效的数据重传,从而影响网络带宽的有效利用率。

文献[3]提出了一种基于邻节点的概率转发方案,该方案的最大问题是算法实现复杂,增加了协议管理的开销,加重了节点的处理负担,网络节点能耗较大,缩短了Adhoc网络的生存时间。

文献[4]提出了一种基于计数的转发方案,该方案每次转发前都要等待T时间,这显然增加了网络的时延,从另一个方面降低了网络性能。

文献[9]提出了基于固定概率的转发方案,该方案的不足之处是没有考虑网络节点的分布密度情况,概率的大小直接决定路由转发的效率。

文献[10]提出了基于智能概率的转发方案,虽然该方案考虑到了网络的疏密情况,但它分别为稠密网络和稀疏网络指定一个固定概率,因此该方案仍然属于一种固定概率的转发方案。

2.2算法描述与分析

本文提出一种简单高效的动态概率转发方案,主要思想是在原有AODV的基础上为每个节点设置一个计数变量Nneighber用于统计其邻节点数,当某个节点接收到一个RREQ消息并判定需要转发该消息时,如果此时Nneighber ≤4,则直接转发该RREQ消息,即转发概率为1;否则按P=4/Nneighber的概率进行转发。

转发概率随着网络密度动态变化,当Nneighber较大时,表明该节点处于一个以它为中心的稠密子网内,RREQ消息需要转发的概率较小;当Nneighber较小时,表明该节点处于一个稀疏的子网内,这时就要以比较大的概率转发RREQ消息,避免产生某些节点不可达并由此而增加路由发现的时延。

改进后的AODV路由协议 称为DP_AODV。在Adhoc网络初始化阶段,由于网络中的节点路由缓存中没有任何路由项,Nneighber=0,此时若发起路由发现,源节点将按原AODV路由协议转发RREQ消息的方式进行处理。此后,由于定期的Hello消息机制使得网络中的节点逐渐清楚其邻节点的个数,因此中间节点再收到RREQ消息时,将采用DP_AODV算法进行处理。由于采用动态概率转发,转发的总次数为,其中Pi为第i个节点的转发概率,N为网络节点数。在稠密网络中,由于Pi «1,此时网络中充斥的RREQ广播包数量将远少于原协议的N -1,从而有效避免了网络广播风暴的产生,网络的有效可用带宽将增加,端到端的延时将变小,网络的吞吐量将有所提升。

在DP_AODV协议中,根据原AODV协议中的定期Hello消息机制,任意一个节点X接收到一个Hello消息时,首先检查是否是第一次接收到该IP地址节点的Hello消息,如果是,则表示该节点是新邻节点,于是将Nneighber自增1,否则表示该邻节点还在自己的通信范围之内,于是增加与该节点的路由生存期;若与某个IP地址节点的路由超时,则表明该IP地址的节点已不在自己的通信范围内,因此变量Nneighber自减1。

2.3算法实现

在recvRequest函数中,对于任意一个节点X,在其第一次收到一个RREQ消息后,将按如下方式处理:

算法中的邻节点数Nneighber按如下算法计算:

在recvHello函数中,对于任意一个节点X :

AODV协议每隔1.5倍的Hello时间间隔周期就会运行nb_purge函数以清除不再可达的邻节点:

3仿真分析和比较

3.1仿真场景设置

仿真的Adhoc网络的应用层采用CBR(恒定比特率)数据流,传输层采用UDP(用户数据 报协议),网络层分别采用AODV和DP_AODV路由协议,MAC(媒体访问控 制)层采用IEEE802.11协议,物理层采用无线传输。仿真场景设定网络节点最大移动速度为10m/s,最大连接数为30,停留时间为0,数据包产生速度为4包/s,节点个数分别设置为10、20、30、40、50、60、70、80、90和100,仿真场景长1km,宽1km,仿真持续时间为100s。

3.2仿真结果分析

对不同仿真场景分别进行10次仿真并取平均值,分别统计协议的平均E2ED(端到端时延)和平均PDF(分组投递率)。

E2ED是指数据包从源节点到达目的节点的时间差,用于衡量网络传递数据包的效率,其计算公式为,式中,Prcv为成功传送的数据包数,即节点接收到的数据包的总数,tri为第i个成功传送的数据包的接收时间,tsi为第i个成功传送的数据包的发送时间。

PDF是目的节点应用层收到的数据包总数与源节点应用层发送的数据包总数的比值,反映网络成功投递数据包的比例,是衡量网络吞吐量的一个主要指标,其计算公式为式中,ri为第i个节点成功接收的数据包数,si为第i个节点发送的数据包数,n为网络节点总数。

仿真结果如图1和图2所示。从图中可 以看出,当网络节点较少时,两种路由转发方案的平均E2ED都较大,平均PDF也不是很高,但两者相差不大,这主要是因为各节点的邻节点相对较少,路由发现比较缓慢,单位时间内的网络吞吐量不高。随着网络节点数的增加,特别是节点数在30~70之间时,两种方案 的平均E2ED大幅下降,同时,平均PDF大幅增大,几乎趋于100%,且都趋于平稳,这主要归功于各节点的邻节点增多,路由发现比较快,单位时间内的网络吞吐量升高。但当节点数 达到80以上时,AODV路由协议的平均E2ED明显增大,平均PDF也随之下滑,这主要是由于在路由发现过程中大量广播RREQ包降低了网络的有效可用带宽。相对而言,DP_AODV路由协议的优势表现突出,虽然平均E2ED有小幅增加,PDF也有小幅下滑,但都变化不大,这主要是由于随着网络节点密度的增加,每个节点的邻节点也相应增多,但每个节点转发RREQ的概率随之减小,使得网络中充斥的数据包数量并没有达到引发网络风暴的级别。

从仿真结果来看,这种改进方案是有效的,特别是在稠密网络中,对降低网络E2ED、提高网络吞吐量是一种有效的优化方案。

4结束语

本文针对Adhoc网络AODV路由协议 在RREQ消息转发过程中存在的不足,提出了一种基于动态概率转发RREQ消息的方案,仿真结果证明了这种改进方案的有效性,特别是在网络节点比较多、网络比较稠密的情况下,能更好地体现这种改进方案的优势。此外,DP_AODV路由协议实现算法简单,对计数变量Nneighber的处理,相对于大量的重复的RREQ广播包而言并没有加重节点的处理负担和能量消耗,相反,在稠密网络中,因为减少了大量的重传次数而节省了节点能源消耗。

摘要：在Ad hoc网络(自组织网络)的路由建立过程中,由于AODV(Ad hoc按需距离矢量)路由采用洪泛方式转发RREQ(路由请求)消息会产生很多不必要的重传,很可能引发广播风暴而影响网络性能。文章提出了一种基于动态概率转发RREQ消息的改进方案,该方案根据邻居节点的个数选择不同的概率转发RREQ消息。仿真结果表明,在网络节点较多且网络比较稠密的情况下,改进方案能有效减少网络端到端时延,提高网络吞吐量和分组投递率。

关键词：Ad hoc网络,AODV路由协议,RREQ消息,仿真

参考文献

[1]洪家军,吴金龙.利用NS-2实现Ad hoc网络仿真平台[J].华侨大学学报:自然科学版,2008,29(3):375-378.

[2]洪家军,吴金龙.基于NS-2的Ad hoc网络路由协议性能仿真[J].江汉大学学报:自然科学版,2007,35(1):67-70.

[3]荆文礼.基于Ad hoc网络的AODV路由协议的研究与改进[D].无锡:江南大学,2013.

[4]Zhang Q,Agrawal D P.Dynamic probabilistic broadcasting in mobile ad hoc networks[C]//Vehicular Technology Conference,2003.VTC 2003-Fall.2003IEEE 58th.IEEE,2003,5:2860-2864.

[5]徐文涛,晁爱农.一种移动Ad Hoc网AODV路由协议的改进方法[J].计算机应用与软件,2013,30(3):225-228.

[6]Perkings C,Royer E,Das S.Ad hoc On-Demand Distance Vector(AODV)Routing[EB/OL].http://tools.ietf.org/html/rfc3561.html,2003-07/2014-06.

[7]龙亮,肖宇峰,张华,等.利用Hello消息改进AODV路由的实时性[J].光通信研究,2014,(1):63-66.

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

[9]Sasson Y,Cavin D,Schiper A.Probabilistic broadcast for flooding in wireless mobile ad hoc networks[C]//Wireless Communications and Networking,2003.WCNC 2003.2003IEEE.IEEE,2003,2:1124-1130.

AODV协议 篇7

移动自组网中的节点通常根据路由表进行数据的传输与转发, AODV协议是一种按需路由协议, 由于该协议本身不提供拥塞控制, 当网络负荷较重时, 实时业务如语音、视频等会产生较大的延时, 甚至大量分组被丢弃, 导致网络性能下降。本文提出一种基于带宽控制策略的AODV改进路由协议, 利用AODV周期性发送Hello分组包的机制, 加入带宽估算和业务进入控制策略, 使路径的带宽能够满足业务的实时要求, 提高网络吞吐量, 降低网络延时和丢包率。

1 AODV路由协议

当源节点想传输数据至目的节点而路由表中又没有相关路由记录时, AODV就会广播RREQ分组查找路由。RREQ分组包含有目的节点IP地址、源节点IP地址和RREQ ID等信息。RREQ ID为一递增的序号, 用来判断当前路由是否为最新以及防止路由环路[5]。在路由建立过程中, RREQ沿途所经过的中间节点都要建立到源节点的反向路由;目的节点收到RREQ分组后, 回传RREP应答分组沿反向路径直到源节点, 此过程各节点会依次建立到目的节点的正向路由。

当节点收到重复的RREQ分组时, 如果后到达的RREQ分组ID比之前收到的RREQ分组ID大或路由跳数更少, 则更新路由信息并回传RREP分组, 否则丢弃该RREQ分组。

当路由失效时, 节点会启动路由维护过程, 即往源节点发送RRER分组, 源节点收到后重新发起路由建立过程, 或由中间节点直接进行本地修复, 直到新的路径产生。

2 对AODV协议的改进

本节对AODV进行优化改进, 形成一种基于带宽控制的改进协议BAC_AODV (Bandwidth Reservation Control AODV) 。主要包括三方面的内容:一是带宽估算;二是信道竞争节点数的确定;三是在路由建立过程中加入Qo S控制管理。

2.1 带宽估算

带宽估算包括业务带宽需求 (BWQ) 、本节点剩余带宽 (RBW) 最小剩余带宽的估算 (Min_RBW) 三部分。

BWQ表示业务流在网络中传输时需要的带宽, 当源节点发起路由寻找时, 会在RREQ分组中携带该数值, 即

式中:R表示分组产生率, 不同的业务流类型具有不同的R值 (如CBR, VBR) ;TDATA表示分组传输时间;C表示物理层传输信息时候的速率。

RBW表示节点自身剩余的带宽, 可通过载波监听的方式计算得到, 即

式中:Ti表示节点在一段TP的监听时间内, 信道呈现为空闲状态的时间;C表示物理层传输信息时的速率。

对AODV协议Hello分组格式进行修改, 加入自身的RBW值, Hello分组会周期性地广播给一跳距离内邻居, 每个节点均可获得其所有邻居节点的剩余带宽N_RBWi。节点收到所有一跳内邻居节点的剩余带宽后, 取最小值记为N_RBW, 即

将式 (2) 和式 (3) 再取最小值, 得

式中:RBW_min为最小剩余带宽, 在路径寻找过程中使用该值进行建立路由的Qo S控制管理。

2.2 带宽竞争节点数的确定

在IEEE802.11无线载波监听机制下, 由于隐藏终端的原因, 节点的通信不仅受到通信范围内节点的影响, 也会受到干扰范围内节点的影响[6]。设干扰范围为通信范围的2倍, 如图1所示, 对B节点而言, 1跳邻居节点A, F, C和2跳邻居节点S, D都会影响自己可以使用的带宽。

定义一个参数Ncn (带宽竞争节点数目) , 表示节点传输RREQ时, 可能会影响自己占用带宽的节点数目 (包含节点自身) , 考虑到RREQ是单向传输, 本文对Ncn做了一种悲观的估算方法, 即

式中:d根据下一跳是否为目的端进行取值;m表示从源段开始的跳数。对于d而言, 有

对于m而言, 设中间节点到源节点的跳数为h, 有m=min (h, 2) 。

2.3 路由建立与维护

当节点的路由表没有去往目的节点的路由记录时, 则会广播发出RREQ分组进行路由发现, BAC_AODV协议对RREQ分组进行了修改, 如图2所示。

修改的RREQ分组利用原有的保留字段来携带BWQ值, 去掉了节点序列号栏位, 采用Flow_ID进行路由寻找和业务通信。不同的业务 (如音频, 视频) 即使是同一个节点发出, 其Flow_ID也会不相同。

中间节点收到RREQ后, 将自己的RBW值与所有1跳邻居节点的N_RBW取最小值, 得最小剩余带宽RBW_min (详见2.1小节所述) , 并根据式 (8) 进行带宽判断。

如果满足该式, 则表明该条路径上的带宽满足于业务带宽的需要, 将相关信息写入路由表, 否则不转发该RREQ, 回传RRER分组, 该路径被删除。

中间节点如果收到具有相同Flow_ID的RREQ, 则比较与先到RREQ分组中的跳数, 选择跳数少的RREQ分组同样使用式 (8) 进行Qo S控制判断后再做转发, 否则直接丢弃该RREQ。

目的节点收到RREQ后, 回传RREP到源节点, RREP分组含有Flow_ID, 中间节点根据Flow_ID建立业务去往目的节点的正向路径。

BAC_AODV协议是以源节点产生的Flow_ID对业务进行标识, 当中间节点发现路由无效时, 不再进行本地局部修复, 而是直接广播携带Flow_ID的RRER分组给周围邻居节点。收到RRER的邻居, 如果其路由表中有此Flow_ID相关信息栏, 则继续转发RRER分组直到源节点;反之邻居节点则不再转发RRER。源节点收到RRER后, 会重新发起路由建立过程。

3 仿真与分析

本文采用NS-2.35软件, 模拟在无线自组网环境下[7], 使用VBR流承载MPEG-4视频业务, 分析比较了在AODV和BAC_AODV两种路由协议下网络所表现出的性能差异。

仿真参数如下:网络范围1 200 m×1 200 m, 50个无线通信节点随机分布;通信距离250 m, 干扰距离500 m;仿真时间200 s, 每隔2 s随机产生一条VBR业务流, 共20条, 根据文献[8], VBR业务流的分组产生率R值取102 packet/s, 适宜于MPEG-4视频格式的传输;MAC层采用IEEE802.11DCF模式, 发送缓冲队列值最大为50 packet/s, 最大业务数据单元MSDU为1 500 byte。

选取网络延时 (Delay) 、网络吞吐量 (Throughput) 、分组丢弃率 (Dropping rate) 和业务流阻塞率 (Blocking rate) 为网络性能指标。其中延时是指发送端到目的端的时间间隔;吞吐量表示单位时间内目的节点成功收到的数据分组;分组丢弃率表示节点丢弃分组与总数据分组的比值;业务流阻塞率表示被限制进入网络的业务流数。图3和图4是VBR业务流在两种协议下的吞吐量对比和延时对比。

可以看出, 业务流在10条的时候达到饱和, 随着业务流的增多, AODV协议的吞吐量会逐渐下降, 平均延时明显增大;由于BAC_AODV采用Qo S允许接入控制策略, 当节点负载过重时, 会拒绝其他业务流的进入, 从而得到一个比较稳定的吞吐量, 而在延时方面, BAC_AODV的性能也优于AODV协议。

图5是两种协议下业务流的阻塞情况比较。AODV协议没有建立业务Qo S机制, 不具备带宽和拥塞控制管理功能, 即便是网络负载非常严重时, 也不会限制业务流的接入, 因此其阻塞率一直为0;而BAC_AODV协议在业务到达饱和后, 通过带宽估计和接入控制, 会限制后续业务流进入网络。从图中可以看到, 当网络负载为15条VBR时, 阻塞率为16%左右, 为20条时, 阻塞率为35%。本次模拟场景中, BAC_AODV协议始终维持网络中的VBR业务流数量在12~13条, 之所以阻塞后续的业务流, 其目的是为了给正在进行通信的业务流提供有效的带宽, 保障网络的Qo S。

当分组重传次数大于设定的最大次数依然无法成功投递, 或分组数多于发送缓冲队列最大值, 都会导致分组被丢弃。图6显示为AODV和BAC_AODV的分组丢弃率比较。

可以看到, 随着业务流数量的增加, 两种协议下的分组丢失率均有不同程度的上升。当网络中业务达到饱和后, BAC_AODV会控制新的业务流进入网络, 避免出现网络过度拥塞使分组大量被丢弃的情况, 因此分组丢弃率保持较低幅度的增长, 总体上没超过15%;而AODV协议的分组丢失率随着网络负载的加重增加非常明显, 甚至超过50%, 总体性能表现不如BAC_AODV优越。

4 结束语

本文在AODV的基础上, 提出一种基于带宽估算的Qo S路由策略BAC_AODV, 利用hello-message包携带带宽信息广播给周围邻居, 并以此作为业务接入网络的依据。节点在收到RREQ后进行控制判断, 使建立的路径满足业务流的带宽需求。从仿真结果可以看出, 在网络负载加重的情形下, BAC_AODV协议能够更好地控制网络流量, 降缓解网络拥塞, 且网络吞吐量和延时性能均比原AODV协议优越, 提升了网络效率。

摘要：无线自组网中的路由协议AODV没有提供流控和拥塞避免机制, 当网络负载较重时, 多媒体业务或产生较大的延时, 或分组被大量丢弃, 使网络性能下降。在AODV协议的基础上, 提出一种基于带宽接入控制的改进协议BAC-AODV, 对节点和路径的可用带宽进行估算, 修改路由建立机制, 使路径满足业务流对带宽的需求, 保证网络的QoS质量。分析和仿真结果表明, 改进后的协议相比原有AODV, 能更有效地控制业务流量, 提高吞吐量, 降低延时。

关键词：带宽估算,业务流,吞吐量

参考文献

[1]陈林星, 曾曦, 曹毅.移动Ad Hoc网络[M].北京:电子工业出版社, 2006.

[2]李鹏, 刘宇, 李庆华.一种基于剩余能量考虑的Ad Hoc网路由协议[J].计算机应用, 2008, 28 (2) :399-401.

[3]KAZANTZIDIS M, GERLA M.End-to-end versus explicit feedback measurement in 802.11 networks[C]//Proc.the Seventh IEEE Symposium on Computers and Communications.Taormina, Italy:IEEE Press, 2002:216-220.

[4]CHEN L, HEINZELMAN W B.QoS-aware routing based on bandwidth estimation for mobile Ad Hoc networks[J].IEEE Journal of Selected Areas on Communications, 2005, 23 (3) :115-120.

[5]周希林.一种改进的AODV路由协议[D].广州:中山大学, 2010.

[6]高凌飞.基于AODV路由协议的可用带宽估计算法的研究[D].哈尔滨:哈尔滨工业大学, 2008.

[7]柯志亨, 程荣祥, 邓德隽.NS2仿真实验—多媒体和无线网络通信[M].北京:电子工业出版社, 2009.

AODV协议 篇8

移动Ad Hoc网MANET(Mobile Ad hoc Networks)是一种有特殊用途的网络,是由一组具有无线收发功能的移动终端组成的一个多跳的临时性的自治系统[1,2]。网络节点地位平等,无需设置任何中心控制节点,节点具有路由和转发的功能。当通信的源节点和目的节点不在通信范围之内时,可以通过中间节点转发进行通信,即数据包要经过多跳能到达目的地[3,4]。由于MANET具有很强的抗毁性,所以主要用于军事通信和紧急救援场合。

虽然Ad Hoc网应用广泛,由于Ad Hoc网存在自组性、动态拓扑、带宽受限等缺点,其对应路由协议一直是自组网中研究的重点和难点[5,6]。随着研究的深入,人们发现按需距离矢量AODV(Ad hoc On Demand Distance Vector)协议更适合MANET,但在实际的应用中还是存在一些问题。例如,路由发现困难,修复路由耗时,没有备份路由,大量洪泛等。许多学者对此进行了相关研究,并提出了一些改进措施。文献[7]提出了基于MPLS的改进的AODV协议,该协议在网络层和数据链路层中加入称为2.5层———MPLS层的方案,可以快速地进行路由发现,提高了路由发现速度,但引入的MPLS层又使得路由负担加大,增大了节点负担,而且也未涉及路由维护问题。文献[8]提出了一种基于节点移动的改进AODV协议,该协议同样提高了路由发现速率,但实验表明此算法更适合稀疏的拓扑结构,而且该算法未涉及路由维护。文献[9]提出了一种基于路由维护改进的AODV协议,但引入了两种报文格式,使节点增加了能耗,并且未涉及路由发现问题。文献[10]提出了新的基于备份路由的AODV协议,但此算法也未涉及路由维护。

综上所述,现有的改进方案主要单一的针对路由发现或路由维护,而未能的兼顾路由发现和路由维护。本文针对AODV协议的路由发现和路由修复的策略,在对ADOV协议内容和前人研究深入分析的基础上提出了一种基于备份路由和本地修复相结合的路由协议。该方案的主要思路是:发现路由时存入至多三条的路由条目,而当链路中断且备份路由失效时,采用2跳内修复的本地修复策略,即Improved_AODV(本文改进后的路由协议)。利用RREQ(报文格式如图1所示)报文中Reserved字段中的前两比特位对AODV路由协议进行扩展与整合来提高网络性能。仿真结果表明,改进协议提高了网络的整体性能。

1 AODV路由协议

AODV协议本质上是DSDV和DSR两种协议的结合,是在DSDV的基础上,结合DSR的按需路由机制改进而得到的,区别在于AODV为了提高带宽采用逐条转发的方式取代了DSR的源路由方式。

AODV是一种纯粹的按需路由,只有当两个节点相互通信时才会进行路由的查找和维护,中间节点提供转发业务。AODV协议假设无线链路是双向的,其路由协议可分为路由发现和路由维护两个过程。

1.1 路由发现

当一个节点需要和某个节点通信而又没有到该节点的有效路由时,则启动路由发现过程。路由发现过程如下:

(1)源节点发起路由请求,发送RREQ报文格式见图2。

(2)中间节点收到RREQ后,进行以下操作:

(1)比较本节点和目的节点的地址,如果本节点是目的节点,则建立或更新到源节点的反向路由条目,并回复RREP(报文格式如图2)报文,否则转步骤(2);

(2)根据RREQ中的<源节点地址、RREQID>判断是否收到过该RREQ,如果收到过则丢弃该请求,否则转步骤(3);

(3)建立或更新到RREQ源节点的反向路由条目。同时RREQ跳数计数器加1,向邻节点广播该RREQ。

(3)节点收到RREP后,如果该节点没有到达目的节点的路由则建立新的路由条目;如果有到目的节点的路由,则比较RREP和路由条目记录的目的节点序列号和跳数,确定是否建立新的路由条目。如果本节点是中间节点,则根据本节点到源节点的路由表继续单播转发RREP;如果本节点是源节点,则路由发现完成,可以发送数据包。

1.2 路由维护

AODV通过Hello包、链路修复及链路断开后发RERR(报文格式如图3所示)报文来进行路由的维护。每个节点周期性的向邻居节点广播Hello包,Hello包的生存时间TTL值为1,因此Hello包只能在相邻节点间传播。一个节点收到一个Hello包就可以新建一个邻居条目或者知道一个邻居节点与自己依然保持连接。如果在一定时间内收不到一个邻居节点的Hello包,则认为该邻居节点与自己不再连接,以这个节点为下一跳的路由都不能再用来传送数据,因此将这些路由设置为无效状态。AODV路由协议允许本地修复(Local Repair),探测到路由无效的节点将启动路由发现过程,广播RREQ以便建立新路由,如果在给定时间里能重新建立起有效路由,就接着发送数据;如果建立路由失败,则向上游节点发送RERR报文,RERR报文中记录着不可达节点列表,不仅包括了链路断开的邻居节点,还包括以此邻居节点为下一跳路由的目的节点。通过RERR的广播,其它节点就知道链路断开了。路由失败后先进行本地修复可以减少数据传送的时延,减少上层控制和网络负荷。但引入大量的广播增加了网络的负担。

2 Improved_AODV协议的描述

Improved_AODV协议利用RREQ报文中的Reserved字段(保留字段)中的前两位比特对AODV路由协议进行扩展,用于备份路由和路由修复。之所以引入两比特位标识,是因为两比特可表示4个状态,分别为:00,01,10,11。其中,00,01,10,用于表示源节点到目的节点最多存储的3条路由并代表一定的优先级,而11用于标记路由修复时Hop count为2的报文。之所以选择3条路由,是因为在实验中发现3条路由可以使得网络性能与能耗比最优,在文献[10]中,作者予以证明。而选择2跳范围,是因为直接面向目的节点的路由发现将导致一些无谓的路由发现,引入大量洪泛,增加开销与时延,从而影响网络的性能与效率;修复限制在2条范围内,网络中传播的控制报文数量将会减少,寻路时间也会缩短。具体改进的算法描述包括路由发现和路由维护两部分。

2.1 路由发现

在源节点与目的节点进行通信时,如果源节点知道到目的节点的路由,则直接传输数据;否则,开启路由发现过程。如图4所示,当A节点需与G节点通信时,A节点利用洪泛方式,将会找到G节点,最终发现到达G节点有五条路径:(a)A→D→G;(b)A→B→C→G;(c)A→F→E→G;(d)A→D→C→G;(E)A→B→C→D→G;然而,五条路径会先后到达G节点,节点G根据路径到达的先后顺序,例如为:(a),(b),(c),(d),(e),于是G点标记出(a),(b),(c)三条路径的Reserved字段的前两比特位分别为00,01,10,并存入缓存中。之所以这样标记,可以一定程度的说明网络的质量情况。由于路由(d),(e)是第四、五条,多于三条,所以丢弃。此时G节点返回Reserved字段前两比特位被标记的3个RREP,先后到达A后,节点A记录3条路由,并缓存。此时,路由建立完成。根据优先级A节点用标识为00的路由进行数据传输。算法流程图如图5所示。

2.2 路由维护

当网络中某个节点离开或某条链路失效,此时发起路由修复。如图4所示,例如节点D离开网络,则(a)A→D→G路由失效,节点A开启路由维护。首先,节点A判断自己是否具有备份路由,此时有(b)、(c)两条路由,则选择(b)路由进行数据传输,因为(b)路由标记为01。节点G收到Reserved字段中的前两比特位为01的路由,知道标记位为00的路由失效,则删除路由(a),再将路由(b)与(c)的标记位改为00,01,并返回RREP给源节点A。假如在某时刻t1,D→G链路失效且D点无备份路由,此时(a)路由失效并开启本地修复,给除上游节点外的邻居节点发送Reserved字段中的前两比特位为11的RREQ报文,Hop Count为2,目的节点为G,源节点为D,序列号为失效路由的序列号,C点收到后发现自己有到G点的路由,且序列号足够“新”,即序列号大于等于RREQ中的序列号,则返回RREP给节点D,此时沿路径A→D→C→G传输G点用此路径取代(a),并Reserved字段中的前两比特位标记为00,将删除路由(a),并给源节点A返回RREP;若C点没有路径到G,则C再传给1跳范围内的节点,只有节点B,B收到报文后,按C相同的方法处理。若一定时间后,D点没有收到RREP或收到RERR报文,则向上游节点A发送RERR错误报文。此时,若A为源节点,A按D的方法继续查找,成功则继续传输,失败,则发起路由发现过程;若A不是源节点,查找失败,再交付给上游节点,直到到达源节点,源节点按的A的做法完成。流程如图6所示。

3 数学分析

根据Ad hoc网络的无线信道的特点,假设:(1)节点间的链路状态相同,相同大小报文在链路上传播时延相同,记为tα;(2)从源节点到目的节点一共有n个节点。则分别对网络中的路由发现和路由修复进行时延分析。

3.1 路由发现

令tF_AODV表示AODV协议的发现路由时间总和,tF_I_AODV表示Improved_AODV协议发现路由的时延总和,则有:

其中,tRREQ为源节点到目的节点的时延,tRREP为目的节点到源节点的响应时间。

其中,tI_RREQ为改进后源节点到目的节点的时间,tI_RREP为改进后目的节点到源节点的响应时间。

因为RREQ报文和I_RREQ(改进后协议RREQ)报文大小一样,所以tRREQ=tI_RREQ又因为:

其中,tβ为原协议中间节点的处理时间。

其中,tβ1为改进协议中间节点的处理时间,tγ中间节点记录备份路由的处理时间。

由式(3)和式(4)可得:

由于tβ1比tβ仅仅多2比特位的处理时间,相对于现在的终端设备处理时间几乎相等;而tγ不影响传输时延,所以Improved_AODV协议相对于AODV而言增加了发现路由的时间,但增加量很小。

3.2 路由修复

令tR_AODV表示AODV协议的修复路由时间总和,tR_I_AODV表示Improved_AODV协议修复路由的时间总和。分为两种情况讨论:

当第k个节点失效且与第k个节点相连的某最长分支有ni个节点,并且都无法到达目的节点(即k节点无备份路由)。则有:

其中t RREQi表示从k节点到i节点的时间,t RERRi表示从第i节点到k节点响应时间。

此时都无法完成本地路由修复,显然Improved-AODV协议节省了大量时间。

当第k个节点失效且在某分支一共有ni节点的第j个节点处,有到目的节点的路径(即存在备份路由)。

其中t RREPj为从节点j到k的响应时间。

其中,tδ为查找备份路由和修改标志位的时间。由于tδ的耗时显然小于tR_AODV,所以Improved_AODV协议节省了大量时间。

4 仿真分析

基于WINDOWS XP+OPNET14.5仿真平台[11,12,13],我们对AODV协议和Improved_AODV协议进行仿真分析。通过建立网络拓扑结构为50个移动节点,各节点随机分布在500 m×500 m的平坦矩形区域内,并以[0 m/s,20 m/s]之间的速度向任意的目的移动,到达目的地后,停留一个暂停时间,然后随机地选择一个目的地和移动速度,如此反复,直到模拟结束。每个节点的带宽是2 Mb/s。模拟时间为30min,每个包的长度是512 bit,每秒产生4个数据包。实验结果见图7-图10(红线为Improved_AODV,蓝线为AODV)。

图7给出了发现路由耗时和时间的关系。由于改进后的路由协议采用路由备份的策略,因为需要修改标志位以及源节点的存储处理,所以一开始发现路由时,耗时较大。但随着时间的推移,由于某些节点存在备份路由所以在后续发现路由时所需的时间减少许多。

图8给出了发送请求包的数量和时间的关系。随着时间的推移,会出现节点移动出范围和链路失效的问题,会导致源路由失效。此时,原AODV协议是利用洪泛机制,会出现大量的RREQ报文;而Improved_AODV协议引入备份路由和本地修复的联合策略,利用备份路由和路由修复时洪泛范围限制在2-hop之内,所以RREQ报文数量大大减少。

图9给出了发送时延和时间的关系。由于Improved_AODV协议利用联合策略可以快速的修复路由,所以发送时延相对于原AODV协议减少很多。

图10给出了吞吐量和时间的关系。同样可以看出Improved_AODV协议明显优于原AODV协议。

5 结语

本文针对AODV协议在实际应用中存在路由的缺陷和前人单一改进策略的局限性,提出了一种利用RREQ报文Reserved字段中的前两比特位对AODV路由协议进行扩展的方法,用于备份路由和路由修复的改进AODV协议。通过仿真实验表明,改进后的AODV协议能够改善路由的发现时间,RREQ包的数量,网络的时延,以及网络的吞吐量等相关性能。但本文没有充分考虑到,如备份路由先失效的问题,以及如何更少耗能的问题,是下一步研究的重点