一种基于负载均衡的移动Ad Hoc网络AODV协议改进

王 钰，田 杰 ，徐 磊

（武警工程学院 西安 710086）

1 引言

移动无线自组网[1](mobile Ad Hoc network，MANET)是由具有无线通信能力的移动节点组成的，是一种能够迅速展开使用的网络体系。它不需要依靠现有固定的通信网络基础设施，是没有任何中心节点的自组织、自愈合网络。在MANET中，每一个节点既充当了主机的角色，又充当了路由器的角色。由于节点的传输距离有限，当通信的源节点和目的节点间的距离超出传输范围时，它们之间的通信就必须通过中间节点转发。由于移动节点的传输能力和能量有限，所以处在网络拓扑结构中心的若干个节点，将会收到更多的路由请求，成为更多路径的中间节点。它们在负载压力和能耗方面都将远远大于其他节点，容易超出负载及耗尽能量，进而造成网络拥塞。如何控制网络负载和提高网络生存时间成为了Ad Hoc网络所面临的一个重要问题。

2 路由协议描述

Ad Hoc路由协议可分为先验式(proactive)路由协议和反应式 (reactive)路由协议两类，也可称为表驱动(table-driven)路由协议和按需驱动(on-demand)路由协议。表驱动路由协议的主要特点是要求每个节点维护一个或多个路由信息，并在网络拓扑结构发生改变时及时更新。按需驱动路由协议[2]的主要特点是它只有在源节点需要时才进行路由发现，路由一经建立，就会对其进行维护，直至目的节点无法到达或该路径不再被需要为止。相关研究[3]表明，与先验式路由协议相比，反应式路由协议虽然传送时延较大，但路由开销小、分组投递率高，更适合移动自组网络。本文将要改进的AODV[4]路由协议就是一种按需驱动的路由协议。

AODV路由协议采用逐跳 （hop-by-hop）方式转发分组，路由表中记录了到目的节点的下一跳信息。它不需要在报文中携带完整的路由信息，当源节点中没有到达目的节点的路由时，广播一个RREQ。每个接收到RREQ的中间节点记录下到源节点的逆向路径（以便为之后的RREP提供路由），然后查询路由表中是否有到达目的节点的路由，若有则利用记录在报文中的逆向路径回复RREP，否则重新广播RREQ。当RREQ到达目的节点时，目的节点利用记录在报文中的逆向路径发送RREP。每个接收到RREP的节点记录了本节点到目的节点的路径，用以传送后续报文。另外，每个节点都维护有一个目的序列号，当节点需要建立到目的节点的路径和接收到以自己为目的节点的RREQ时，其值自动加1。该序列号附带在其发出的RREQ、RREP中，网络中其他节点在收到包含节点路径信息的控制报文（RREQ、RREP）时，对比此序列号和本地路由缓存中该节点路由的序列号，来判别路由的新旧程度，避免环路的产生。路由请求信息中包含了TTL（time to live），避免了路由请求带来的全网广播。AODV协议通过节点周期广播hello消息提供与相邻节点的连接信息，检测链路状态。

3 改进后的AODV协议

在移动Ad Hoc网络中，包含拥塞节点的一条路由，即使是通往目的节点的最短路由也未必是最佳路由。因此，在路由选择的时候应尽力避开拥塞节点。采用负载相对较轻的路由，不但有利于保证传输时延，也均衡了全网的负载，有助于提升网络整体性能。AODV的开销主要来自于建立路由的泛洪广播的路由请求报文RREQ。对其进行改进,提出PS-AODV协议。节点收到RREQ分组后先检查其负载值，若节点负载过大，则拒绝转发RREQ分组，直到负载降低以后，再重新转发RREQ分组。在此引入一种MAC层和路由层之间交换信息的跨层机制，网络中每个节点监视自己的MAC层接口队列，加入metric值来对网络中节点的能量和负载进行度量。网络中从源节点到目的节点的链路负载状况，取决于链路中负载大的节点。即该链路的metric(m)值为 m=max(m1,m2,m3,…，mn)。设该链路中第 i个节点的metric值为mi=li/bi。其中bi为该节点的可用能量百分比，li为该节点MAC层接口队列的当前占用率li=qi/ci，其中qi为节点i的MAC层接口队列缓存的分组数量，ci为节点i的MAC层接口队列能容纳的最大长度。假设所有节点的规格都是一样的，则ci=c。所以到达目的节点的为了简化计算，可将c去掉，则

目的节点或者拥有到达目的节点路由信息的中间节点，在回复RREP分组的时候，若存在多条路径，可凭借metric值进行最优选择。PS-AODV在路由请求RREQ中添加一个字段metric(m)，来记录所经过节点的最大负载，当源节点发起路由请求时，它计算m值，并把m值写入RREQ分组中，然后进行广播。同时在节点路由表中添加一个字段mt，记录从源节点到该节点的m值。中间节点收到RREQ后，计算m值来确定当前节点的负载状况和可用能量。根据节点的m值以及是否有目的节点的路由信息，决定该节点是否可以作为中间节点。节点有3种状态。瘫痪:m≥a；拥塞:b≤m≤a；正常:m

网络中每个节点可根据其负载状况和可用能量决定转发或丢弃收到的RREQ分组。当一个中间节点处于“瘫痪”状态时，除非它是该链路的目的节点，否则将不处理任何路由请求，丢弃所有收到的RREQ，使其不能再成为中间节点。当节点处于“拥塞”状态时，只有其路由表中已经存在了此路由请求目的节点的路由信息或它是该链路的目的节点，它才会回复其路由请求，否则将丢弃该路由请求，以此来减少由于RREQ广播造成的网络负载和降低路由发现的端到端时延。当节点处于“正常”状态时，如果首次收到新的RREQ，则把路由表中的相应路由值设为该RREQ中的m值。然后比较m和该节点的metric值，将大的m值记录在RREQ的mt中，最后转发RREQ。如果节点已经收到过来自同一源节点的相同广播ID的RREQ，则比较m和mt。如果m值较小，则丢弃RREQ。否则，更新路由表的mt值，并将指向前一跳节点的指针指向发送该RREQ的节点，并且不再转发该RREQ。收到第一个RREQ后，目的节点等待一段时间来获得可能的更多路由，然后从中选择拥有最小m值的路由回复RREP。

4 仿真和分析

下面在NS2[5]上进行仿真。以下描述仿真环境、性能参数和试验结果。物理信道的带宽为2 Mbit/s。链路层采用IEEE 802.11MAC层协议的分布式协调功能(distributed coordination function，DCF)。PS-AODV 的 b 值取 0.5，a值取0.7。将50个节点随机地分布在1 200 m×800 m的范围内，节点的通信范围是250 m，最大移动速度为 5 m/s，节点初始能量为200 J，暂停时间为50 s，仿真运行500 s。信源采用固定比特率(constant bit rate，CBR)，每个分组长度为512 byte，一共启动40个CBR流。仿真通过改变信源发送分组的频率来改变网络负荷。

4.1 仿真参数

以下是本文选取的协议性能比较参数：

平均端到端时延=路由发现过程所需时间+分组在缓存中的排队时间+链路层重传时间+传播时间；

4.2 仿真结果

图1反映了随着网络负载增加，AODV和PS-AODV分组传送率的变化曲线。结果显示随着网络负载的增加，两者的分组传送率都在下降，当负载为0～480 kbit/s时，AODV和PS-AODV的分组传送率下降不明显，差距不大，但随着负载增加，两者的分组传送率都急剧下降，但PS-AODV的下降幅度比AODV小，当负载达到1 440 kbit/s时，PS-AODV的分组传送率比AODV高7%。由此可见，PS-AODV在分组传送率上比AODV拥有更大的优势，尤其是在高负载情况下优势更加明显。这是因为AODV没有考虑负载均衡问题，在高负载环境下，处于网络中心的若干节点负荷急剧增加，当流量超出节点传输极限时，其分组丢失率迅速提高，导致分组传送率急剧下降。而PS-AODV根据metric值选择传输路径，并且高负载的节点能有选择地回复RREQ分组，有效地对数据流量进行了分流，均衡了负载，间接提高了分组传送率。

图2显示了随着网络负载的增加，AODV和PS-AODV的平均端到端时延变化情况。随着网络负载增加，两者的平均端到端时延开始上升，PS-AODV的平均端到端时延总体低于AODV,当负载达到1 440 kbit/s时，PS-AODV比AODV的平均端到端时延低240 ms，该图反映出PS-AODV比AODV拥有更低的平均端到端时延。这是因为PS-AODV根据metric值选择路径，而metric值的决定性因子是MAC层接口队列缓存的分组数量，而端到端时延主要由排队时间产生，所以PS-AODV会选择排队时间较小的路由，从而减小了网络时延。

图3显示了PS-AODV和AODV的路由开销随网络负载变化时的变化情况。随着网络负载增加，数据分组所占比例不断提高，两者的路由开销降低。PS-AODV的路由开销总体低于AODV，当负载为1 120 kbit/s时两者差距达到最高的0.9。由于AODV的路由开销主要来自于建立路由时泛洪广播的路由请求报文RREQ。在PS-AODV中，处于“瘫痪”和“拥塞”状态中的节点会有选择性地丢弃RREQ分组。且PS-AODV提高了分组传送率，减少了路由重传的次数，从而减少了初始化路由发现的次数，有效地降低了RREQ分组的产生。在路由发现过程中，收到同一源节点相同广播ID的中间节点，会通过比较metric值后删除m值大的路径，减少了RREQ的转发，从而减少了网络路由开销，所以PS-AODV的路由开销要低于AODV。

图4显示了网络生存时间随网络负载变化情况，在此项分析中，选用了第一个节点与第n/2个节点死亡时间的中值作为网络生存时间，这是因为当网络中第n/2个节点死亡以后，整个网络将会急剧恶化，失去其使用价值。当网络负载增加时，PS-AODV和AODV的网络生存时间都降低，PS-AODV的网络生存时间要长于AODV,这主要由于PS-AODV会根据节点负载情况选择负载更小的节点，使整个网络的能量消耗更加均衡，避免了网络中心的节点过早耗尽的能量，从而延长了网络的生存时间。

5 结束语

本文在AODV基础上提出了一个基于路径选择和应答拒绝算法的改进MANET路由协议PS-AODV。它根据本地节点的负载情况和可用能量来决定是否应答，并根据RREQ分组和节点中的metric值进行路径选择，从而实现负载均衡的目的。PS-AODV降低了因为网络中心的节点能耗过快、负载过重而造成的网络拥塞概率。仿真显示PS-AODV在分组传送率、平均端到端时延、路由开销和网络生存时间等性能指标上较AODV有一定提高。今后的工作主要是将PS-AODV协议与其他负载平衡协议[6]对比，并对协议进行进一步改进，提高其性能。

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

2 Best P,Gundeti S,Pendse R.Self-learning Ad Hoc routing protocol.In:Proc of the 58th Vehicular Technology Conference,Orlando,Florida,USA,2003

3 Eshghi F,Elhakeem A K.Performance analysis of Ad Hoc wireless LANs for real-time traffic.IEEE Journal on Selected Areas in Communications,2003,21(2):204～215

4 IETF RFC 3561.Ad Hoc on-demand distance vector(AODV)routing,2003

5 于斌，孙斌，温暖等，NS-2与网络模拟.北京：人民邮电出版社，2007

6 Lee S J,Gerla M.Dynamic load-aware routing in Ad Hoc networks.In:IEEE International Conference on Communications(ICC),Helsinki,Finland,2001