一种面向无线传感网络的AODV改进路由协议*

刘 蓉,李红艳

(长沙医学院信息工程学院,长沙 410219)

通着现代电子技术的发展,无线传感网络 WSNs(Wireless Sensor Networks)在多类应用中得到广泛使用[1]。然而,WSNs受到多类资源的限制,包括能量、功耗、存储容量以及传输距离。目前,网络层的路由协议已成为WSNs的研究热点[2-4]。

与传统无线网络不同,WSNs具有一些鲜明特性,如节点分布式、节点能量有限、通信链路易受到外界环境影响。依据路由驱动方式的不同,可将现存的WSNs划分为3类:(1)表驱动式路由,如OLSR[5]、DSDV[6];(2)按需路由,如AODV[7]、ABR[8];(3)混合式路由,如ZRP[9]。这3类路由协议的性能如表1所示。

从表1可知,按需路由更适应于拓扑变化的WSNs。而混合式路由复杂性较高,并不实用。因此按需路由受到广泛关注。然而,作为传统的按需路由协议的代表,AODV协议也存在一些不足。目前,研究人员提出不同的AODV改进协议。如文献[10]提出了一种AODV的改进协议B-AODV。B-AODV 对路由决策过程和路由维护阶段进行改,降低了传输时延,但B-AODV只研究双向链路,并没有对单向链路进行研究。

此外,文献[11]提出了基于链路生存时间的改进路由协议SV_AODV(Enhanced Routing Protocol on Ad Hoc On-demand Distance Vector with Speed Variance)。SV_AODV路由协议计算每条链路的速度方差,再选择速度方差最小的路径传输数据,提高了链路的稳定性。此外,文献[12]也提出了AODV路由的改进协议AODV_D。AODV_D协议依据MAC层的节点竞争信息和接口队列时延信息决策路由,降低了传输时延。

而文献[13]也提出AODV的优化协议。先基于单播和广播结合策略,实现路由探测,并通过降低广播帧数量,增强路由稳定性。此外,文献[14]提出了基于链路质量的改进AODV协议,通过设定链路质量阈值,丢弃链路质量差链路,提高了路径稳定性。而文献[15]是从能量角度对AODV路由进行改进,延长了网络生存时间。

为此,本文以AODV路由协议为基础,对其路由决策机制进行修改,提出基于路径稳定和路径能量的改进AODV路由协议I-AODV-SE。I-AODV-SE协议考虑了网络拓扑的稳定性和节点能量信息,并计算了基于路径稳定和路径能量的路径权重,并择优选择权重小的路径传输数据包。同时,也避免了节点能量空洞问题,提高了网络生存时间。实验结果表明,提出的I-AODV-SE协议能够有效地提高数据包传输率,避免了因节点能量问题而降低了数据包丢包率,并延长网络生存时间。

1 AODV概念及问题描述

自组织按需距离矢量AODV(Ad hoc On-Demand distance Vector)路由属于反应式路由。AODV允许在多个移动节点间实现动态、自发式多跳通信连通。当需要建立一条路由传输数据包时,节点(源节点)就向一跳邻居节点广播请求数据包RREQ(Route Request),触发路由发现过程。RREQ控制包含有节点的相关信息,包括节点位置信息。一旦接收了RREQ包,节点就转发RREQ包,直到RREQ包被传递到目的节点。

一旦目的节点接收了RREQ包,它就沿着此路径向源节点回复RREP(Route Replay),并且忽略随后所接收的RREQ包。换而言之,目的节点是选择第一条到达的路径作为数据传输路径。AODV的路由发现过程,如图1所示。如图1(a)所示,源节点1广播RREQ控制包,其邻居节点通过广播,将RREQ传输到目的节点8。

图1 AODV路由发现阶段

从上述分析可知,AODV协议在路由决策过程中选取的是最短路径。然而,在实际环境中,最短路径缩减了传输跳数,但增加每跳的距离。距离越长,链路受到外界环境的概率越大,链路断裂的风险也就越大。换而言之,长距离的传输容易遭受到噪声、障碍物等影响,这必然降低链路质量。

此外,在无线传感网络中,节点能量直接影响了节点的工作。一旦节点能量消耗殆尽,它就无法转发数据,那么它所参与的路由就遭遇断裂的风险。而传统的AODV协议并没有考虑到节点能量问题,这容易产生热点现象[16],如图2所示。

图2 热点现象

从图2可知,节点8和节点6、节点7均选择了节点5向信宿转发数据,导致节点5过度使用,增加了其能量消耗速率。这就是热点现象。一旦节点5能量耗尽,就出现能量空洞,多条传输路将受到影响。而一旦路径断裂,又需重新启动路由发现,增加了控制开销,也提高了传输时延。

为此,本文从路由发现过程和缓解能量空洞两方面,对传统的AODV协议进行改进。这也是AODV和I-AODV-SE两个路由协议的不同处所。具体而言,I-AODV-SE路由首先在选择路径的策略上做了改进,不再只选择最先到达的路径传输数据,而是计算依据路径权重,选择路径,其次,它考虑了节点能量问题。而传统的AODV并没有考虑。

2 I-AODV-SE协议

I-AODV-SE协议充分考虑了路径稳定性和节点能量。由于节点移动,I-AODV-SE协议利用邻居集的变化率估计路径稳定,进而提高数据传输的流畅性。同时,考虑到节点能量,避免部分节点因能量耗尽而导致链路断裂。为此,利用路径稳定性和节点能量估计路径权重,并择优选择路径传输数据包。

2.1 路径稳定性

在WSN中,节点移动以及节点自身硬件故障,导致部分节点不在自己的传输范围内。一旦节点不在自己的传输范围内,就与它的通信连接将断裂,这必然会影响到路径的稳定性。因此,利用节点的邻居集变化率估计路径稳定性。

当节点j离节点i的欧式距离Dij小于R,则节点j便可纳入节点i的邻居节点集Ni:

Ni={j|Dij≤R}

(1)

式中:R表示节点传输半径。注意到式(1),Dij为两点间的欧式距离,不存在方向性,其定义如式(2)所示:

(2)

式中:(xi,yi)、(xj,yj)分别表示节点i、节点j的坐标。

AODV协议利用传输RREQ包,获取周围拓扑信息。若节点i能够直接收到来自节点j转发的RREQ,则说明节点j位于节点i的一跳通信范围内,即节点j是节点i的邻居。因此,节点完全可以估计自己的邻居节点。

(3)

从NCR定义可知,NCR只反映了同一个节点在两个相邻时刻的局部拓扑变化,并没有体现一段时间内节点的邻居节点变化情况。为此,基于NCR,引出另一变量:拓扑稳定因子。计算过程如下:

首先,每个节点周期地估计自己的NCR,并缓存最近的m个NCR,再计算均值,如式(4)所示:

(4)

对于m值的选择需要谨慎。若m过大,过长时间所得到的NCR已失去时效性,并无实际意义。而m过小,也无法反映一段时间内局部拓扑的稳定情况。

最后,计算局部拓扑稳定因子。节点i的拓扑稳定σi:

(5)

从式(5)可知,σi越小,说明在最近一段时间内,邻居节点变化越缓慢,局部拓扑越稳定。那么由节点i组建的路径更为稳定。

最后,计算路径P的稳定性。若路径P有n个节点,那路径P的稳定性σP:

σp=min{σ1,σ2,…,σn}

(6)

2.2 节点能量

假定每个节点的初始能量相同,且表示为Einitial。而节点的剩余能量为Eremain。对于节点i,利用初始能量与剩余能量比值表示其能量状态Ei,其定义如(7)所示:

(7)

假定某条路径P,其有n个节点组成。路径P的能量指标等于n个节点的能量状态的最小值,如式(8)所示:

Ep=min{E1,E2,…,En}

(8)

(9)

式中:Hop表示路径P的跳数。接下来,对θ进行归一化处理,如式(10)所示:

(10)

最后,计算路径能量因子Ee,其定义如式(11)所示:

Ee=(1-Ep/Einitial)β

(11)

从式(11)的定义可知,路径能量因子Ee整合了路径能量以及节点的平均能量。Ee越小,路径能量越稳定。

此外,节点在传输转发自己RREQ包时,将自己的剩余能量载入RREQ中,便以计算路由权值。

2.3 路由判据权值

在传统的AODV路由协议中,目的节点只选择最短路径。为此,I-AODV-SE协议考虑多条路径,并计算每条路径的路径权重,再选择权重最小的路径传输数据包。

具体而言,路径P的权重融合了路由稳定性和路径能量,如式(12)所示:

W=ασP+βEP

(12)

式中:a、β为路径稳定性、路径能量因子的权重,且a+β=1。此外,在多数无线传感网络中,传输路径的稳定性比路径能量更为重要。因为,多数传感网络是采用密集部署。因此,仿真过程中,选择a=0.6;β=0.4。

2.4 数据包传输流程

一旦节点需要传输数据包,它就向邻居节点传输RREQ包。由于I-AODV-SE协议需要计算路径权重,在传统的RREQ包中添加了路径稳定性、路径能量。RREQ包的格式如图3所示。

图3 改进后的RREQ包

每个接收节点,就将自己能量状态和拓扑稳定因子载入RREQ,再传输。当目的节点接收后,就依据参与此路径上的所有节点的能量状态Ei和拓扑稳定因子σi计算整条路径上的σP和EP值,并选择路径权重最小的路径回复RREP。

值得注意的是,利用RREQ控制包传输节点及网络拓扑信息是可行。有多类文献[11-14,17]都是利用RREQ控制包传输这些信息。如文献[17]提出基于链路质量和节点能量的AODV路由算法,该算法就是利用RREQ传输节点的剩余能量信息和跳数。

图4 路由发现过程

RREQ和RREP的传输流程如图4所示。假定源节点i发送了RREQ包,其邻居节点j接收了RREQ包。一旦接收RREQ包,节点j就首先判断是否之前已接收过同样ID的数据包,若是,则丢弃此RREQ。再判断自己是否为目的节点,若是,则依据式(12)计算路径判据权重,并选择权重最小的路径回复RREP。

若不是目的节点,就将自己的路径稳定性、路径能量信息加入RREQ,并转发,直至RREQ传输至目的节点。

3 实验分析

3.1 仿真模型

为了更好地分析I-AODV-SE路由性能,利用Castalia仿真器[18]建立仿真平台。Castalia仿真器是以OMNET++平台为基础[19],并基于Linux操作系统的网络仿真器。同时选择AODV、E-AODV、L-AODV 作为参照,并与I-AODV-SE路由进行比较。同时,选择网络生存时间、数据包分组率作为性能指标。

考虑100 m×100 m区域,节点随机分布,并且信宿位于仿真区域中心。节点数从20至120变化。每个节点发包率为1 packet/s,节点以CC2420模块为无线发射模块。仿真时间100 s,每次实验独立重复100次,取平均值作为最终数据。具体的仿真参数如表2所示。

表2 仿真参数

3.2 仿真结果及分析

3.2.1 实验1

本次实验考查节点密度(节点数)对路由性能的影响,包括网络生存时间、端到端传输时延和数据包传递率。

首先分析节点数对网络生存时间的影响。节点数从20至120变化。四个协议的网络生存时间随节点数的变化曲线如图5所示。

图5 网络生存时间随节点数的变化曲线

从图5可知,节点数的增加提高了网络生存时间。原因在于:节点数的增加,提高了路径选择概率。与AODV、L-AODV相比,E-AODV和I-AODV-SE协议的网络生存时间得到提高。例如,当节点数为120时,AODV协议的生存时间只有42 min,而I-AODV-SE协议的生存时间增加至58 min,比AODV协议的生存时间提高了16 min。

此外,从图5可知,随着节点数的增加,I-AODV-SE协议在网络生存时间上的优势越明显。原因在于:I-AODV-SE 协议考虑了节点能量问题,并优化数据传输路径,避免了热点现象,进而延长网络生存时间。从这些网络生存时间方面数据看,I-AODV-SE协议生存时间提高的并不多。原因在于:一方面I-AODV-SE协议通过优化路径,避免能量空洞问题,降低能量消耗率;另一方面,I-AODV-SE在估计路径权重时也加大了能量消耗,即增加路由成本。

图6反映了四个协议的平均端到端传输时延。传输时延受多个因素影响,如信道接入机制以及路由策略。四个协议都是采用相同的信道接入机制(MAC协议),因此下面只从路由策略方面,分析四个协议的传输时延的差异性。

图6 平均传输时延随节点数的变化曲线

I-AODV-SE协议的平均端到端传输时延最低,且较平稳,并没有随节点数变化而波动。而AODV协议的平均端到端传输时延较高,较高于L-AODV、E-AODV协议。这主要是因为AODV协议在进行路由发现阶段,采取了RREQ和RREP控制包,增加了一定的时延。而L-AODV协议的端到端传输时延略低于AODV,这主要归结于L-AODV协议在路由决策时,考虑了链路质量,提高了路径稳定性,进而降低了端到端传输时延。而E-AODV协议的时延低略高于L-AODV协议,原因在于:E-AODV协议只考虑了节点能量,并没有考虑链路质量问题。

最后,分析协议的数据包传递率。从图7可知,节点数的增加降低了数据包传递率。这主要是因为:节点数的增加,增加路径的平均跳数,提高了丢包率,进而降低了数据包传递率。从图7可知,相比于AODV和E-AODV协议,I-AODV-SE和L-AODV协议的数据包传递率得到提高。原因在于:AODV和E-AODV在路由决策时,并没考虑链路质量,降低了路径稳定性。

图7 数据包传递率随节点数的变化曲线

与L-AODV协议相比,I-AODV-SE协议的数据包传递率得到有效地提高。尽管L-AODV和I-AODV-SE协议在路由选择时均考虑了链路质量,但是I-AODV-SE 协议不仅考虑了从路径稳定性,还考虑了节点能量问题,避免了因节点能量耗尽而产生的路径断裂,提高了路径稳定性,增加数据传输的稳定性。

3.2.2 实验2

本次实验分析流量对路由性能的影响,即数据包产生率对数据包丢失率和端到端传输时延的影响,其中数据包产生率从1 packet/s至14 packet/s变化,数据包产生率越大,网络流量越大。

图8显示了数据包丢失率随流量的变化情况。从图8可知,流量的增加降低了数据包丢失率,原因在于:数据包产生率越高,网络内正在传输的数据包数越多,它们均在占用网络资源,导致资源竞争,必然导致一些数据包丢失。相比于其他路由协议,I-AODV-SE 路由具有较低的数据包丢失率,对网络流量具有一定的强健性。

图8 数据包丢失率随数据包产生率的变化曲线

随后,分析了流量对数据包传输的端到端传输时延的影响,如图9所示。

图9 端到端传输时延随网络流量的变化曲线

从图9可知,提出的I-AODV-SE的端到端传输时延最低,而传统的AODV的端到端传输时延最高,并且随数据包产生率的增加,呈增长态势。原因在于:I-AODV-SE协议从路由稳定性角度决策路由,避免路径断裂率高的链路,减少了重建路由的次数,最终缩短了传输时延。

4 总结

针对无线传感网络的路由问题,提出基于路径稳定和网络能量的改进AODV路由协议I-AODV-SE。I-AODV-SE路由对AODV的路由决策机制进行改进。通过计算路径稳定性和能量,估计路径权重,进而提高了数据传输稳定性,也缓解能量空洞问题。仿真数据表明,提出的I-AODV-SE路由能有效地延长网络生存时间,也提高了数据包传递率。

本文考虑的无线传感网络环境,后期,将改进 I-AODV-SE 路由,使其适用于车联网等自组织网络环境。这将是后期的工作方向。