基于限制广播域和节点剩余能量的按需路由算法研究

高媛

（徐州工业职业技术学院，江苏徐州，221008）

基于限制广播域和节点剩余能量的按需路由算法研究

高媛

（徐州工业职业技术学院，江苏徐州，221008）

按需路由协议AODV的路由发现使用洪泛方式的扩散法，导致网络超负荷运行和拥塞，而且在选择转发路由时，总是选择最少跳数的路由，造成无线传感网络中节点能量不均，减少网络寿命。本文提出了AODV-DE算法，该算法引入广播域的概念，限制RREQ分组的转发范围，同时避免使用剩余能量低的节点转发数据分组，选择路由路径时选择总剩余能量最多的路径进行信息的传送。仿真结果表明，AODV-DE协议在路由开销、网络寿命和端到端的延迟这三个方面表现出了优势。

AODV；广播域；剩余能量

0 引言

AODV协议是一种经典按需路由协议，算法简单且扩展性好[1]。当源节点需要与目标节点进行通信而路由表中没有相应表项时开始路由发现的过程，AODV的路由发现本质上还是使用洪泛方式的扩散法[2]，当网络规模增大，节点数较多时，RREQ等路由控制报文迅速增加，导致网络超负荷运行和拥塞，大大降低了网络的性能[3]。另外，AODV协议在选择转发路由时，总是选择最少跳数的路由[4]。这就使得最短路径中的某些节点由于频繁使用而提前耗尽能量，造成无线传感网络中节点能量的不均衡。

针对上述不足，本文提出一种改进协议AODV-DE（routing algorithm based on restricted broadcast domain and node surplus energy），该协议综合考虑RREQ分组的广播范围以及路由节点的剩余能量。在进行RREQ分组的转发时，引入广播域的概念，限制RREQ分组的转发范围；为了使路由节点的能量能够均衡地消耗，AODV-DE协议避免使用剩余能量低的节点进行转发数据，而是选择发现的路由路径中所有节点剩余总能量最多的路径进行信息的传送，从而延长网络寿命。实验表明，该改进协议在路由开销、网络寿命方面都有所改善。

1 AODV-DE路由算法

1.1 基于广播域的改进

为了限制RREQ消息的广播范围，在RREQ消息的帧结构中增加了节点的坐标信息，用来存储RREQ发送到本节点的前一跳节点的坐标，在泛洪的过程中节点的坐标信息会扩散到整个网络。当源节点进行一次新的路由发现时，源节点会按照改进的RREQ消息结构产生一个携带有本节点坐标信息的RREQ消息，并对此RREQ消息进行广播。在广播时每个中间节点要进行判断，在广播域中继续转发RREQ消息，避免向将RREQ消息转发至本节点的上一跳节点重复转发。

1.2 广播域模型的建立

在广播的过程中，如图1所示，当源节点0想与节点6通信，而它的路由表中没有相应的路由信息，节点0将发起路由发现过程。节点0向周围节点广播RREQ分组（图a），节点1、2、3收到RREQ分组后建立到节点0的反向路由，并继续向周围节点广播RREQ分组（图b）。从图c中可以看到，节点4在收到了来自节点1、2、3的RREQ分组后，开始向周围节点广播RREQ分组，它周围的节点有1、2、3、5、6，其中，节点1、2、3又重复收到了RREQ分组，这样就使网络中路由控制报文数量太多，有可能造成网络拥塞，同时降低了网络性能。为避免此种情况的发生，需确定合理有效的广播域，即控制RREQ分组的转发范围，使其只能发送给未向本节点转发过此分组的节点。

以节点4为例，如图2，为使节点4不再将RREQ分组重复发送给节点1、2、3，节点1、2、3共同确定的灰色区域为禁止广播区域，将此区域在数学模型中表示：A、B、C、D四点分别代表节点1、4、3、2。

图1 AODV路由建立过程

图2 节点4 RREQ的广播过程

图3 抽象出的数学模型

由图3，假设A点坐标为（ax，ay），B点坐标为（bx，by），C点坐标为（cx，cy），D点坐标为（dx,dy），

首先比较A、C、D三点横坐标的大小，以此确定最大夹角。

由图3得知，xC＞xD＞xA

，所以，A点与C点间夹角θ最大。

计算角θ的大小：

广播域的角度γ可以通过下式求得：

扩展至一般情况：

设将RREQ数据分组转发给M节点的上一跳节点的集合为S[n]。当集合中只有一个上一跳节点时，则M节点就只向集合中节点之外的节点转发；当集合中的上一跳节点大于一个时，首先比较这些节点的横坐标大小，取横坐标最大以及最小的节点，与本节点确定的夹角为θ，广播域的角度即为γ=2π-θ，临界边即为确定γ角的两节点各自与本节点的向量。

1.3 基于能量均衡的改进

为了使路由节点的能量能够均衡地消耗，本方案在LEAR协议[5]的能量门限值思想基础上，再综合考虑整条路由路径节点剩余总能量，以延长网络寿命。

算法描述如下：当一个源节点想要到达一个目标节点时，需在广播域内进行路由发现，当中间节点收到RREQ数据分组时，先将自己的剩余能量与预先规定的门限值相比较，如果剩余能量高于门限值，那么此节点就可在广播域内广播请求到所有邻节点；反之，则该节点拒绝RREQ包,并忽略请求。当目标节点收到第一个RREQ包时，并不马上按此路径回复RREP分组，而是等待少许时间，待后续的RREQ分组也都到达时，比较所有路由路径中节点剩余的总能量大小，选取剩余能量最大的一条路径回复RREP分组。为实现此算法，需对原来AODV协议RREQ分组格式进行改进，添加节点剩余能量。改进后的RREQ分组格式如图4所示。

图4 改进后的RREQ分组格式

2 AODV-DE协议的仿真与分析

2.1 仿真环境的参数设置

我们在NS仿真环境下进行仿真[6]，模拟人员定位系统的实际应用，设置仿真环境为400m×80m的方形区域。路由节点通信范围设定为20m，路由节点的个数从80个一直增加到140个，每次增加10个路由节点。在仿真过程中节点或者静止或者移动，移动时以1m/s的速度向某一目标点匀速移动，到达目标节点后停留一段时间，然后继续向随机目标点移动，反复以上过程直至仿真结束。设最大移动速度为2m/s，停留时间为30s。

2.2 仿真与结果分析

在仿真中加入AODV协议进行对比。

图5 随节点数目增大路由开销的变化

图6 节点生存时间

（1）路由开销分析：由图5可以看出，在源节点数相同的情况下，两种协议的路由开销都随着路由节点数的增加而增加，但是，AODV-DE协议的路由开销要明显低于AODV协议，这是因为，在进行路由发现的时候，AODV-DE协议的RREQ分组只向广播域内转发，减少了不必要的控制分组。

（2）节点的存活时间分析：设置每个节点的初始能量设为10J，节点的发送功率为0.660W，节点的接收功率为0.395W，初始能量较小，发射功率和接收功率较大，可在较短时间内对比出两种协议的性能。仿真时间为100s，节点数为100。仿真结果如图6所示，AODV-DE节点的存活时间明显要比AODV的长，这是因为对节点能量进行了控制。原协议节点是分散死亡的，而AODV-DE协议的节点死亡时间较为统一，AODV-DE在进行路由发现时避免使用剩余能量低的节点，固定的门限值限制了能量的减少，使大部分节点的剩余能量可以稳定在门限值附近，节点消耗的能量都比较均衡。

图7 随节点数目增大端到端的延迟的变化

（3）端到端的延迟分析：由图7可知，随着路由节点数目的增加，AODV-DE协议比AODV协议的端到端的延迟要长，这是因为为了使路由节点能量的消耗达到均衡，AODV-DE协议要比较节点剩余能量和门限值的大小以及路径节点总剩余能量的大小，而且如果所有的路径中都有中间节点的剩余能量低于门限值，还需要调低门限值，重新进行路径的发现；而AODV协议不考虑能量问题，直接进行路径的发现。故AODV-DE协议比AODV协议的端到端的延迟要长。由此可以看出，AODV-DE协议网络寿命的延长是以增长的端到端的延迟为代价的。

3 小结

本文提出一种按需路由协议的设计方案，此方案继承了AODV协议的优点：只在需要传输数据时才开始路由发现；去除了AODV协议的缺点：提出广播域的概念，有效地控制了控制分组的转发范围，避免了盲目泛洪的路由发现方式所导致的网络超负荷运行和拥塞，节省了能量。并且在能量均衡方面作出了详细的设计，延长了网络的寿命。此算法可以使移动分站的电池能量均衡地消耗，避免了频繁地更换电池，虽然端到端的延迟有所增加，但是增加的并不多，都是毫秒数量级的，在实际应用中，基本不会有影响。

[1] 无线自组织网络按需路由协议研究[J].卢山,宋志群,周凌宇,刘倩楠.无线电工程.2015(11).

[2]AODV路由协议的研究和改进[J].何绵禄,褚伟,刘辉舟.计算机工程.2015(01).

[3]基于AODV的多度量无线路由算法研究[J].郑硕,胡寿伟,陈佳品,李振波.半导体光电.2016(06).

[4]一种基于AODV的均衡优化协议[J].贾皓强,赵富康,杨振洁,张涛.信息通信.2017(03).

[5]于宏毅.无线移动自组织网[M].北京：人民邮电出版社,2005：138，176-182，267-268，277-280.

[6]谢佳，徐山峰.AODV、AOMDV和AODV-UU路由协议性能仿真与分析[J].中国电子科学研究学院学报，2011,6（6）：592-596.

Research on on-demand routing algorithm based on restricted broadcast domain and node residual energy

Gao Yuan
（Xuzhou College of Industrial Technology，Xuzhou Jiangsu，221008）

This paper presents the AODV-DE algorithm, the proposed algorithm introduces the concept of broadcast domains, RREQ forwarding, and avoid using the low residual energy of nodes forwarding the data packet transmission, routing path selection path of total residual energy of most information. Simulation results show that the AODV-DE protocol has advantages in three aspects, routing overhead, network lifetime and end-to-end delay.

AODV; broadcast domain; residual energy

江苏省高校自然科学研究面上项目(编号:16KJB480006)