基于网络均衡的AODV协议改进

张世显，梁 俊

（空军工程大学 电讯工程学院，西安 710077）

1 AODV路由协议

AODV路由协议是在DSDV协议基础上结合类似DSR中的按需路由机制进行改进后提出的，既借用了DSR的路由发现和路由维护机制，又利用了DSDV的逐跳路由、顺序编号和路由维持阶段的周期性更新，还加入了对组播路由QoS的支持，其最显著的特点是为路由表中每个项都使用了目的序列号，因而还可以避免环路的发生，并且很容易编程实现。基于上述优点，AODV成为自组网路由协议研究中的热点。

当源节点想与另外一个节点通信，而它的路由表中又没有相应的路由信息时，它就会发起路由发现过程，发送RREQ消息分组。当RREQ消息分组从一个源节点转发到不同的目的地时，沿途所经过的节点都要自动建立到源节点的反向路由。节点通过记录收到的第一个RREQ分组的邻居地址来建立反向路由，这些反向路由将会维持一定的时间，该段时间足够RREQ分组在网内转发以及产生的RREP分组返回源节点。当分组到达了目的节点,目的节点就会产生分组，并利用建立的反向路由来转发RREP。

2 AODV协议中路由存在的问题

如上节所述，AODV路由协议是按最快到达目的节点的RREQ消息分组所经多的路径，即最小延时路径，不考虑网络的传播时延，就是最小跳数路由。

图1 路由选择方式

如图1(a)所示的一个简单的Ad Hoc网络中，假设节点3要向节点7发送数据，如果采用最小跳数路由算法，则选择的路径为3-4-7，且节点3向节点7发送的数据量很大，使得节点4的链路层缓存接近饱和。此时，若节点3也要向节点6发送数据，根据AODV算法，节点选择其中跳数最小的路径2-4-6，这样，两条路径均通过节点4，使得网络中的所有数据都将通过节点4，因此可能会出现下面两种不利情况：

1）由于节点4要转发网络中的所有数据，因此其能量消耗远大于网络中的其他节点，一旦节点中的能量耗尽，网络的拓扑结构就会发生改变，如图1(b)所示，此时，节点与网络中其它节点的连接就会中断，且不能发送或者接收任何数据，这样无论是对整个网络还是对节点而言，显然都不希望出现这种情况；

2）当源节点产生大量数据使得数据到达节点的速率超过了链路层处理数据的速率，此时数据将在链路层的缓冲队列中排队等待，随着缓冲队列中数据的增加,分组延时也将增加。如果一直保持该状态，将使链路层存储数据的缓存队列发生溢出，造成分组丢失，而源节点在规定的时间内没有收到目的节点发回的确认消息，将继续保留并重传该分组，从而进一步加剧了该路径上各节点的拥塞，最终造成链路中断。

3 基于网络均衡的优化度量

从以上分析中不难看出，AODV算法中采用的以最小跳数作为路由选择的度量方式会导致网络中某些“中心定位节点”被过多的选用。当大量数据通过少量节点时,将造成网络阻塞，从而增大数据包的发送时延,甚至造成数据包丢失。同时，这些节点在多于其他节点几倍的接收和转发任务下，能量会迅速消耗殆尽，最终可能促使网络分裂成几个相互难以覆盖的“子网”，使网络过早地陷于瘫痪。

因此,在路由算法的设计中有必要考虑各节点的负载状况，对网络的负载进行均衡，使网络保持连续、高效、稳定的运行，网络的综合性能达到最优。

实现均衡网络负载的路由算法称为负载均衡路由算，目前已经提出了一些负载均衡路由算法，比如DLAR、LBAR和LSR，它们对网络节点负载定义也不一样。DLAR将输出排队中分组的个数定义为网络节点负载；LBAR将节点负载定位为经过自己和邻居节点的路由数目；LSR将网络负载定义为节点和邻居节点上输出排队的分组个数之和，通过在选路过程中将负载作为路径选择优化函数，在一定程度上实现了负载均衡。本文定义节点负载为节点输出排队中分组个数，设一条路由l包含节点ni，i=1:N，每个节点负载为：

根据网络均衡的优化度量准则，提出一种NBAODV（Network Balance Aodv）的协议。

4 基于网络均衡的协议(NB-AODV)实现

4.1 消息结构修改

如表1所示，对AODV的RREQ消息报文添加了路由负载一项参数。其定义为RREQ消息经过的所有节点的负载最大数，即中间节点接到RREQ消息分组，先判断自己是否是目的节点，如果不是，判断本节点的数据转发缓冲队列分组个数与消息中的路由负载哪个大，分组个数大，把消息中的路由负载用分组个数替代，进行转发，如果不是，原样转发。

表1 RREQ报文格式

4.2 路由寻找过程

源节点发送RREQ消息分组，中间节点收到的第一个RREQ分组时，启动一个定时器，在定时器规定的时间内,节点从所有的路由请求RREQ消息分组中选择路由负载值最小的邻居地址来建立反向路由，并利用建立的反向路由来转发RREP。

4.3 仿真比较

为了比较NB-AODV、AODV、DLAR协议之间的性能差别，搭建了基于OPNET的仿真平台。网络覆盖面积为：1000m×800m，移动节点速率为10m/s，节点个数为50个，改变分组发送速率分别为1、2、4、6、8和10packets/s，从数据成功接收率、平均端到端延时两个方面对路由算法进行比较。

图2 数据成功接收率

图3 平均端到端延时

5 结束语

本文对现有AODV协议中的最小延时路由问题进行了分析和仿真，并提出基于网络均衡度量优化准则的改进方案，给出具体实现方法。该改进方案避免了最小延时路由带来的“中心节点”负载过重，延时较大的问题，仿真结果表明，新方案的数据分组成功接收率和平均端到端延时的性能指标比AODV明显增强，提高了网络数据的传输效率。

[1] 王新生,张昕.MANET环境下AODV协议的研究和改进[J].微机发展,2005,12.

[2] Johnson J,Maltz D. Dynamic source routing in Ad hoc wireless networks [M].Kluwer Academic: Mobile Computing,1996.

[3] Lee S J,Mario G.AODV-BR: Backup Routing in Ad hoc Networks[C].Wireless Communications and Networking Conference, 2000.WCNC. 2000 IEEE,2000,3:1311-1316.

[4] 王翠荣,陈书义,杨孝宗.基于AODV协议的动态路由管理算法[J].东北大学学报(自然科学版),2005,11.

[5] 朱金华,于宁宁.无线自组织网络AODV路由协议研究[J].微计算机信息.2007,18.

[6] 朱西平,鲁荣波,李宗寿,李方军.基于NS2移动自组网路由协议性能评价的仿真实现[J].中南林学院学报,2004,02.

[7] 任智,郭伟;多跳无线网路由协议研究进展[J].电信科学,2003,08.