基于AODV协议的无线传感器网络多路径路由改进机制

贵彩虹

1 引言

由于AODV协议在存储容量、算法复杂度、实用性以及拓扑变化适应性等方面表现出较优的性能，同时由于Adhoc网与无线传感器网络在网络拓扑结构和数据传输中的相似性，近些年基于AODV协议的无线传感器网络的路由研究比较多。AODV协议在无线传感器网络的路由中使用单一路径进行数据分组的传输，当需要数据传输时，节点首先得寻找一条到目的节点的路径；若在数据传输中，一旦该路径中某个节点或链路断开，就需要重新进行路由发现，因此中间节点会因较大的传输延迟和一段时间内负载的相对集中，易出现能量较早耗尽而死亡，从而导致网络拓扑不稳定，数据传输效率低的问题。在本文提出的改进方案中可使每个节点保存两条最短路径，当数据需要传输时，从这两条最短路径中选择剩余能量多的下一跳节点作为中转节点；如果遇到路径断链，可通过另一条路径进行本地路由恢复；若这两条最短路径都失效，网络才进行路由查找，同时对Hello机制进行改造，即通过定期发送Hello包不仅进行路由的监测，同时实现路由表中的路由能量值的更新。

2 AODV协议工作工程

2.1 路由的获取

AODV协议采用广播路由的机制按需发现路由，当源节点需要向目的节点发送数据时，它就广播一条路由请求（RREQ）消息，中间节点通过分析收到的RREQ建立一条到达源节点的反向路由，同时转发该RREQ消息。收到RREQ消息的目的节点向源节点发送路由应答（RREP）消息以建立正向路由。如果源节点在超时前没有收到RREP消息，它采用扩展环机制重新广播一条新的RREQ消息，直到超过最大重新广播次数，仍没有任何RREP，则应该将所有对应目的节点的数据分组从缓存中丢弃。

2.2 路由的保持

路由建立以后，如果在路由过期时间内没有被使用，或者节点确定的有效路由的下一跳无法到达时，该路由无效，便将一条出错（RERR）消息向所有将此节点作为下一跳节点的相邻节点广播并在本节点路由表中标记相应路由信息为无效。同时，AODV路由协议通过广播HELLO消息来监视链路连通性，实现有效路由的保持。当节点监测到某一条路由无效时，它将该路由从路由表中删除并广播路由出错分组RERR，收到RERR的中间节点将路由表中相应路由设置为无效，并采用相同的原则继续广播RERR，源节点收到RERR后重新启动路由发现过程。

2.3 路由的维护

如果一条活动路由上发生链路中断，则这个节点可能会选择在本地修复。为了修复链路，节点增加目的节点的序列号，然后广播关于目的节点的RREQ进行路由发现，在本地修复过程中数据分组需缓存。如果路由查找周期结束节点仍然没有收到关于目的节点的RREP，则发送该节点的RERR。

3 AODV的改进方案

为了有效利用两条最短路径减少时延、降低开销，本文在AODV路由表中加入了两个字段，同时进行了三方面的改进：多路径路由的建立、多路径路由的保持和维护。

3.1 RREQ、RREP和HELLO消息与路由表的改进

路由表中新添加了zdf_cout、zdz_cout和energy三个字段。

RREQ、RREP和HELLO消息中分别添加了zdf_energy、zdz_energy和he_energy字段。这三个字段分别标识收到RREQ、RREP或者HELLO消息的节点的前一跳节点的剩余能量，其值由节点自动产生。

zdf_cout字段用于标识路由表中反向路径的条数，其初值为0。

zdz_count字段用于标识路由表中正向路径的条数，其初值为0。

energy字段用于标识节点两条正向、反向最短路径的剩余能量。其值是在向路由表进行正、反向路由添加时从相应RREQ、RREP或者HELLO消息的各自能量字段复制得到。

3.2 多路径路由的建立

根据AODV，当启动了路由查找，收到RREQ的节点进行消息分析，首先判断此消息是不是自己产生，若是就丢弃，否则看之前有没有收到过此分组，若是就丢弃，否则将收到的广播分组存入Broadcase ID Cache中，接下来便通过本文改进的字段进行两条最短路径的选择，即查看路由表中的zdf_cout字段，如果其值小于等于2，则把RREQ中的相关信息按照AODV协议添加为路由表的反向路由，并给zdf_cout加1；否则用RREQ中的序号和跳数与路由表中与其消息具有相同目的节点的反向路由条目的相应字段比较，若RREQ中的序号大于路由表中的两条最短路径中任意一条的序号，或者在序号相同的情况下，RREQ中的跳数小于路由表中两条最短路径跳数中任意一条的跳数值，就将RREQ的相关信息存入路由表代替序号最小或者序号相同的情况下跳数最大的反向路由。同理，在RREQ发送至目标节点，目标节点回复路由应答时，即查看节点路由表中zdz_cout字段，如果其值小于等于2，则把RREP中的相关信息添加为路由表的正向路由，zdz_cout加1；否则用RREP中的序号和跳数与路由表中与其消息具有相同目的节点的正向路由条目的相应字段比较，若RREP中的序号大于路由表中的两条最短路径中任意一条的序号，或者在序号相同的情况下，RREP中的跳数小于路由表中两条最短路径任意一条跳数的值，就将RREP的相关信息存入路由表代替序号最小，或者序号相同的情况下跳数最大的正向路由。剩下的路由发现过程与AODV的相同。

3.3 多路径路由的保持和维护

路由建立以后，节点进行数据分组传输时，根据数据分组是传给源节点还是目的节点，选择路由表中两条正向或者反向路由中energy值大的下一跳节点进行转发。如果在活动路由上发生了链路中断，节点选择路由表中到达目的节点的另一条最短路径中下一跳节点进行数据转发，从而实现正向或者反向路由本地路由恢复，同时设置当前节点的此路由为无效。当遇到两条最短路径同时失效，才由当前节点发出RREQ，启动路由发现过程，以便路径及时恢复、数据分组及时传输。AODV协议定时发送HELLO消息，收到此消息的节点，不仅更新自己的邻居表或者有效期限，同时通过Hello消息中的he_energy字段，更新路由表中相应energy值。除此以外的路由保持和维护过程与AODV的相同。

4 改进方案的仿真及性能分析

传统的AODV协议，只有一条传输路径，如果路由断链，数据分组的转发只能等到路由重新获取成功才能进行，所以传输的延迟大，本文采用了多路径机制，提出的两条最短路径选择方案，除了选取了两条跳数最小、最新的传输路径外，还保证了当其中一条路径断链便可在本地启用另一条路径，使传输路径得到及时修复的作用，从而减少了传输路径上的延迟（如图1）。

图1 各节点能量变化值

同时，只有这两条最短路径都失效，节点才进行路由发现，从而也减少了原AODV协议中路由发现的次数，有效地降低开销。在数据分组进行传输时，选用两条路径中剩余能量最大（能耗小）的下一条节点，避免了采用本方案可能存在的因节点相交而导致的某中间节点长期使用而过大的能量消耗，实现了中间节点能量均衡的目的（如图2）。

图2 端到端的延迟

5 结束语

本文引入的多路由机制，采用了两条最短路径保证数据分组的有效传输，减少了路由发现的次数，并且通过选用能量大的节点进行数据转发，实现了对能耗大的节点的能量均衡，从而可提高网络的传输效率。为了进一步提高基于AODV协议的无线传感器网络的传输效率，下一步工作将着眼于考虑数据分组传输所需的整条路径上的能耗均衡情况。