一种能量均衡的AODV路由协议研究

1.引言

无线自组网(Ad Hoc)是由一组带有无线通信收发装置的移动终端节点组成的一个多跳、临时和无中心的网络，具有不依赖于固定基础设施、抗毁性强、可快速展开等优点，适用于军用和抢险救灾的应急通信。

武警部队是国家保障公民生命财产安全、反对恐怖主义和处置突发事件的重要力量，要求在事发地域能够快速、有效地建立起应急通信保障平台。本文在AODV路由协议的基础上，提出了一种改进的AODV路由协议，目的在于均衡网络中每个节点的负载，提高网路的生存时间。

2.Ad hoc路由协议

目前针对Ad Hoc网络提出的路由协议可以分为表驱动(table driven)路由和按需路由(demand based)两大类。

表驱动路由协议又称为先应式(proactive)路由协议，它的目的是为网络中的每一个节点维护到所有其它节点的一致和最新的路由信息，因而要求每个节点维护一个或多个路由表来保存这些信息。当网络拓扑发生变化(事件驱动)时，相关的节点在整个网络中发布更新信息，来确保路由信息的一致性。此外，即使网络拓扑没有发生变化，每个节点也需要周期性地(时间驱动)广播它的路由表。表驱动路由协议的优点是它减少了节点获得路由的延迟，使源节点能够立即判断目的节点的可达性，缺点是消耗了较多的网络资源，并且耗费了一些资源来建立和重建那些根本没有被使用的路由。主要的表驱动协议有：DSDV、WRP、CGSR、OLSR、FSR.

按需路由协议又称为需求驱动(demanddriven)或反应式(reactive)路由协议。

当采用这种路由协议时，源节点只有在需要建立一条到达目的节点的路由时，才产生一个路由发现过程来建立相应的路由。建立了路由后，源节点产生一个路由维护过程来维护该路由，直到到目的端的每一条路由都不可达或者不再需要该路由时。按需路由的优点是不需要花费资源来维护无用的路由，但路由发现过程的费用比较昂贵，而且源节点事先无法预测能否发现到目的节点的路由，此外发现路由的延迟与表驱动路由协议中确定的查表时间相比，也是不可预测的。

3.改进的AODV路由协议

3.1 AODV路由协议

AODV是一种按需的距离向量路由协议，它不仅具有按需路由协议的特点，即网络中的每个节点只在需要进行通信时才建立路由，而不用周期性的交换路由信息来获得到网络其它节点的路由信息;还具有距离向量路由协议的特性，即各个节点的路由表只维护本节点到其它节点的路由，而无需掌握全网拓扑结构。

AODV协议中有五类控制消息：路由查询消息(RREQ)、路由回复消息(RREP)、路由错误消息(RERR)、RREP应答消息(RREPACK)、HELLO消息。RREO消息主要用于节点在进行路由查询时向邻居节点发送的消息，该消息的发送以广播的方式实现;RREP消息由目的节点或具有最新有效路由的中间节点发出，用于告知源节点通往目的节点的路由;RERR消息由检测到路由失效的节点发出，用于通知所有使用失效路由的节点，使这些节点能够及时的寻找新的路由;RREPACK由源节点应目的节点的要求发出，主要用于应答目的节点的RREP消息;HELLO消息是一类特殊的RREP消息，该消息用于节点保持和邻居节点之间的有效链路。

AODV协议中规定节点保存的数据结构主要有：路由表、先驱表、单向链路黑名单(black list)。路由表中保存节点到每一个目的节点的路由。先驱表用来保存使用相对应的路由的所有邻居节点，使得一旦出现链路失效，本节点能够快速的通知到相关的邻居节点。单向链路黑名单主要用于记录于本节点间存在单向链路的上游节点。

3.2 改进的AODV路由协议

在P改进AODV协议中，只更改了RREQ和RREP消息的数据结构，在RREQ和RREP消息中新增了metric(M)项，修改后AODV的RREQ报文格式如表1、表2所示。

当源节点发起路由请求时，由于源节点与目的节点肯定会存在于链路中，故它们的metric值不作为路径选择因子，将RREQ中metric值置0,然后进行广播。中间节点收到RREQ后，根据节点的m值以及是否有目的节点的路由信息，决定该节点是否可以作为中间节点。节点有三种状态：瘫痪、拥塞、正常。网络中每个节点可根据其负载状况和可用能量决定转发或丢弃收到的RREQ分组。

当一个中间节点处于“瘫痪”状态时，除非它是该链路的目的节点，否则将不处理任何路由请求，丢弃所有收到的RREQ,使其不能再成为中间节点。当节点处于“拥塞”状态时，只有当它是该链路的目的节点或者其路由表中已经存在了目的节点的路由信息，才会回复其路由请求，否则将丢弃该路由请求，以此来减少由于RREQ广播造成的网络负载和降低路由发现的端到端时延。当节点处于“正常”状态时，首先判断它是否该路由的目的节点或路由表中存在目的节点的路由信息。若是则回复RREP,若否，则比较节点md值与RREQ中的metric值，若md值大，则更新metric值，转发该RREQ包，若metric值大，则直接转发RREQ.如果是重复收到RREQ,则按前段所述处理。处理流程如图1所示。

4.NS2仿真实验

NS2[6,7](Network Simulator)是由美国加州大学伯克利分校(UniversityofCalifornia,Berkley)开发的一种免费、公开源代码的网络模拟软件，其本质上是一个面向对象的、由离散事件驱动的网络模拟器。

仿真参数如表3所示。

实验中两种路由协议的性能比较如图2~5,改进后的AODV路由协议为PS-AODV.

图2随着网络负载的增加，两者的分组传送率都在下降，当负载在0到480kb/s时，AODV和PS-AODV的分组传送率下降不明显，差距不大，但随着负载增加，两者的分组传送率都急剧下降，但PS-AODV的下降幅度比AODV小。当负载达到1440kb/s时，PS-AODV的分组传送率比AODV高7%.图3随着网络负载增加，两者的平均端到端时延开始上升，PS-AODV的平均端到端时延总体低于AODV,当负载达到1440kb/s时，PS-AODV比AODV的平均端到端时延低了240ms,该图反映出PSAODV比AODV拥有更低的平均端到端时延。图4随着网络负载增加，数据分组所占比例不断提高，两者的路由开销降低。PS-AODV的路由开销总体低于AODV,当负载为1120kb/s时两者差距达到最高的0.9.图5显示了在节点以5m/s速度随机运动的条件下，网络生存时间随网络负载变化情况，在此项分析中，选用第一个节点与第n/2个节点死亡时间的中值作为网络生存时间，这是因为当网络中第n/2个节点死亡以后，整个网络将会急剧恶化，失去其使用价值。当网络负载增加时，PS-AODV和AODV的网络生存时间都降低，PS-AODV的网络生存时间要长于AODV,这主要由于PS-AODV会根据节点负载情况选择负载更小的节点，使整个网络的能量消耗更加均衡，避免了网络中心的节点过早耗尽的能量，从而延长了网络的生存时间。

5.结束语

本文提出了一种能量均衡的路由协议PS-AODV.通过对该路由协议的分析和性能仿真，该路由协议在平均端到端的延迟、平均端到端的吞吐量、网络生存时间、路由开销方面都比已有的经典路由协议如AODV更具优越性。笔者将在后续工作中采用不同的移动速度和移动模型该路由协议进行性能分析，比较试验结果。