改进的基于网络寿命的RPL路由协议

严利民，张 健，王 峰

(上海大学 微电子研究与开发中心，上海 200444)

0 引 言

无线传感器网络(wireless sensor network，WSN)是物联网的重要组成部分[1]，但是，WSN节点受到能量资源的限制，因此降低节点能耗具有重要意义。同时，人们对节能路由的研究也在进一步深入，节能路由目标主要包括以下3个：

(1)控制数据包的数量最小化：无线传感器网络通常实现融合流量模式，即所有数据包都必须通过汇聚节点(sink)，网关路由再传到Internet。主动路由协议在转发数据到sink中时，能够有效限制控制数据包的数量。例如梯度路由RPL[2]协议；

(2)避免最弱的节点：在汇聚融合流量模式下，sink周边的节点需要转发更多的数据流量，因此会消耗更多的带宽和能量。这种现象会导致MAC层中产生漏斗效应，增加了碰撞次数[3]。对于路由层而言，负载必须在节点之间尽可能均匀地分布，特别是在sink点周围。因此我们将这些瓶颈节点作为关键节点来优化网络生存期；

(3)可靠且节能的链路：不可靠的无线链路也会消耗能量，因为发送点必须在下一跳节点确认之前发送多个相同数据包，所以这些节点很快将耗尽其能量。

因此，本文提出了节能路由层来解决以上问题。采用一种路由度量标准ELT(expected lifetime)，根据剩余能量，链路质量来估计节点的预期使用寿命。并探讨如何估计每个节点的ELT值，同时基于这种节点度量来设计路径算法，从而全局地优化网络生命周期。

1 相关工作内容

1.1 RPL路由协议

低功耗有损网络路由协议(routing protocol for low power and lossy network，RPL)[4]，是一个距离矢量协议，它使用一个或多个路由度量标准构造一个面向目标的有向无环图(destination oriented directed acyclic graph，DODAG)。DODAG的构建是基于节点的等级，而目标函数定义了如何使用路由度量来计算等级，此外，DODAG的构建和维护都是通过所有节点周期性广播DODAG的信息对象(DODAG information object，DIO)消息来保证。在DODAG中，目标函数利用度量和约束条件信息选择最优转发节点，构建有向无环图(directed acyclic graph，DAG)，通过选择最优父节点找到最佳的数据包传输路径，降低能量消耗，提高网络寿命。

1.2 WSN中能量感知路由

目前，基于能量消耗问题，主要有3种不同度量的RPL路由协议，分别是基于链接质量、剩余能量以及其它机制。

1.2.1 基于链接质量的标准

文献[5]提出了评估射频环境中的链路可靠性，定义预期发送次数(expected transmission count，ETX)，用来估计在正确确认接收之前所需的发送次数。

计算式为

(1)

其中，Df表示一个数据包被邻居节点收到的实测概率，Dr表示邻居节点发来的ACK应答包被接收的实测概率。在ETX的度量方式中，选择父节点和默认路由的时候考虑到了链路质量的因素，相比简单的将跳数作为路由度量标准，更加贴近低功耗有损网络的实际特征。

但是，采用该标准将形成一个最小能量路径，通过使用最小能量路径来路由所有数据包，该路径上的节点能量将快速耗尽，这样做不会改善整个网络的生命周期，并且产生的拓扑结构将不能进行能量平衡。

如图1(a)中的拓扑结构，其中路由DAG是基于ETX构建的。E节点可以选择B或C节点作为下一跳。C节点是最合适的选择，因为它相对边界路由器而言，ETX值最低。但是，如果所有节点都产生相同的数据流量，则应优先选B节点平衡能量消耗。

图1 不同路由机制构建的DODAG网络

1.2.2 基于剩余能量的度量

为了提高网络生命周期，节点应该避免选择具有低剩余能量的节点作为下一跳。文献[6]提出了使用剩余能量度量的RPL，但是，他们一方面没有考虑射频链路质量，另一方面，即使将剩余能量与ETX结合成一个加权函数，其中每一个的权重为0.5[7]。尽管如此，他们仍不能识别能量最受约束的节点并使其寿命最长。

如图1(b)所示的拓扑结构，其中路由DAG是基于剩余能量构建的。节点G可以选择节点F或节点C作为下一跳，因为节点F的剩余能量更大，所以它会选择其作为父节点，即使相应的链路质量非常低(ETX=3)，但这将导致节点G重发次数增多，从而G节点的电池快速耗尽，所以C节点将是更合适的选择。

1.2.3 其它机制

文献[8]建议动态调整传感器的传输功率以减少实时通信延迟。正常发送的数据包以较低的功率传输，可以降低能耗。但是，即使此解决方案具有高能效，也不会延长网络的使用寿命。以及文献[9]提到的利用节点剩余能量的损耗率，来避免节点能量的快速消耗，选择下一跳节点时考虑剩余能量消耗的大小，实现能量的均衡消耗，避免某些节点的过早失效，但没有考虑路径的可用性，虽然消耗能量均衡但某些路径传输质量较差。

2 预期寿命

2.1 问题陈述

正如前面所示，在WSN分布式的方式中，并没有对创建的一个路由拓扑进行管理，使其网络的生命周期达到最大化。因此，本文提出了一种路由度量标准，不仅考虑到链路的质量，同时平衡该路径上节点可用能量的负载，全局性地最大化网络生存期[10]。这里所说的能量平衡是指花费相同能量构建的路径。

简而言之，路由度量应满足以下属性：

(1)动态捕获链路质量的变化；

(2)可靠性最大化；

(3)瓶颈的能量消耗最小化(即消耗能量最多的节点)。应优先平衡该部分能量以延长网络寿命。

在本文中，我们提出了一种路由度量ELT，通过构建能量平衡拓扑结构，使得全局网络生命周期最大化。

2.2 ELT的估算方法

我们提出了预估寿命这种路由度量机制。节点N通过以下步骤进行ELT值计算。相关符号见表1。

表1 文中符号定义

(1)估算节点N转发的数据流量，包括自己产生的和子节点即将传送过来的

(2)将N必须传输的流量乘以其首选父节点的平均重传次数 (ETX(N,PN))，需要的重传次数越多，消耗的能量就越多

ELT(N)=Ttotal(N)×ETX(N,PN)

(3)通过考虑数据发送速率来计算占用率

(4)通过将占用率与其无线电的发射功率相乘来计算用于传输所有流量所消耗的能量

(5)最后，计算N的剩余寿命，将剩余能量与传输其流量所花费的能量之间的比率作为其值

(2)

我们将ELT与其它指标进行比较，可以看到该路由度量设法克服了其它的限制，如表2所示，它使用被动测量技术来估计链路质量，并考虑到重传次数和剩余能量以减少能量消耗。由于ETX减少了路径上的重传次数，因此间接地减少了延迟。通过在度量中使用ETX，也设法减少部分延迟。

表2 路由度量机制

3 基于RPL的ELT协议

本文的目标是改善网络寿命，因此，我们需要最大限度地减少最受限制节点(瓶颈)的能耗，也就是让最受约束节点的生存期达到最大化。

为了在RPL梯度路由方案中实现这个最小路径度量，主要需要以下几步：

步骤1 计算瓶颈节点的ELT并沿着DIO中的路径发送该信息；

步骤2 给出算法选择最优下一跳父节点；

步骤3 计算节点的Rank值且要避免网络中出现回路。

3.1 瓶颈节点ELT

本文首先提出度量期望寿命，然后根据式(2)计算节点N的ELT。

假设当节点N想要加入DODAG时，由于瓶颈节点最有可能成为第一个死亡节点，因此新节点必须估计自己的数据包对瓶颈节点寿命的影响。为了估计瓶颈节点B的ELT，节点N需要知道以下信息：

(1)节点B的剩余能量Eres(B)；

(2)考虑瓶颈节点到其父节点的重传次数ETX(B,PB)，计算出瓶颈节点传输一位数据每秒消耗的能量

ETX(B,PB)×PTx(B)

(3)

(3)瓶颈节点处理的总流量

(4)

(4)瓶颈节点传输的速率 (DATA_RATE)，然后，根据式(2)节点B可以估算出自己的生命周期

(5)

为了节省内存和能量，我们需要压缩信息，尽量减少在DIO中插入的字段信息数量。因此把式(5)拆分成以下两个变量，分别是：

随着通信技术的发展,常见的无线通信技术及其性能参数如表1所示,车辆检测系统对无线通信方式的性能要求体现在两个方面:传输速率和传输距离[8]。对比不同的无线通信方式可知WIFI技术在传输速度和通信距离面存在明显的优势,故本文采用无线WIFI通信方式搭建无线传感网络。

1)瓶颈节点为下一跳准确接收数据包所消耗的平均能量

(6)

2)由瓶颈节点转发的现有流量

Ttotal(N)

(7)

通过平均能量和现有流量，可以让新节点N准确估计其数据流量对瓶颈节点B的影响

(8)

其中，Ttotal(N) 是新节点通过瓶颈节点B的路径上所注入的数据流量，每次接收到DIO时，都会更新节点的ELT。因此，每个节点保持最新的信息。

3.2 首选父节点

在选择自己父节点时，节点必须考虑自己的生命周期和瓶颈节点的寿命，以便估计哪个节点成为新的瓶颈节点。因此，我们提出路由算法来选择最佳的父节点。对于每个可能的父节点，即一个小于自身Rank值的邻居节点，节点N将：

(1)选择此父节点时计算其生命周期(第(2)行)；

(2)用该节点注入新数据流量，计算更新该路径上瓶颈节点的生存期(第(3)行)；

(3)保存两者中的最小寿命(第(4)行)。

最后，选择最小寿命里面最大的父节点作为首选父节点，然后计算路径的新瓶颈节点的寿命并更新其DIO中的相应信息。见表3。

表3 选择最优父节点

3.3 改进节点Rank值计算

RPL并未指定如何计算DODAG中节点的等级，因为它取决于所使用的约束条件和路由度量。但是，又明确规定它必须严格单调递减到边界路由节点(sink)，以避免形成环路。由于预期寿命代表沿路径的最小度量，因此其值不能用于计算Rank，这样会使得子DODAG网络中的所有节点都将具有相同的Rank值。

然而，节点可以通过向其首选父节点的Rank添加一个常数步长值和剩余能量来计算

Rank(N)=Rank(PN)+Rank_increase
Rank_increase=Step×MinHopRankIncrease+Eres(N)

(9)

其中，Step是一个标量值，MinHopRankIncrease是RPL参数[12]，取值256。RPL禁止下一跳节点是一个Rank值比自身更大的邻居节点，因此，我们要确保Rank值是单调的，保证无环路[13]。文中通过等级修复和最优父节点的选择，保持最长的网络生命期，同时避免形成循环。

3.4 ELT构建DAG

如图2所示，A、B、C、D、E、F、G分别表示各个节点，其右下角表示ELT值，例如，节点A的ELT为80，节点B的ELT为40。图中有两条链路，分别是D→B→A和G→F→E→C→A且节点A为sink节点，B、C为瓶颈节点，因为B、C在其链路上的ELT值最小。图中虚实线上的值表示ETX，即数据包成功发送所需要的次数，该值越小说明路径上的链路质量越好。假设传输一个数据包需要5个单位的ELT。

图2 基于ELT的DAG构建

在图2中，节点G可以选择节点D或F作为首选父节点，如果它选择了瓶颈能量最大的ELT路径，即选择D→B→A，G节点的ELT值降为25，因为G和D节点之间的链路质量很差(ETX=5)，所以它需要重传很多次才能成功到达D节点，而节点B的ELT值降为35，根据首选父节点算法中Pathp(Bp)=min{eltN,eltB} 可得，它自身将成为新的瓶颈且Pathp(Bp)=min{eltG,eltB}=25。 另一方面，如果节点G选择F节点作为首选父节点，G节点ELT值降为45，F节点的ELT降为42.5，C节点的ELT降为30，根据首选父节点算法可得，Pathp(Bp)=min{eltG,eltC}=30，它将对瓶颈节点C和其自身产生较小影响。所以，节点G将选择节点F，因为它使网络中所有节点之间最小的ELT得到最大化。

3.5 证明网络寿命最大化

设N是无线传感器网络中的一个节点，必须在P和Q节点之间选择其首选父节点，其中P节点提供最佳路径(即最大的ELT)。分别设为ELT(Np) 和ELT(NQ)，如果P、Q节点分别是其首选父节点，则估计节点N的预期寿命。并做一个矛盾的证明。

P节点提供了最优路径，意味着在节点N选择了它作为首选父节点后，通过P节点的新瓶颈节点的ELT大于通过Q节点的瓶颈节点。由于通过P节点的瓶颈可能是P(Bp) 或N(如果其ELT小于ELT(Bp))，我们可以区分两种情况：

(1)new_BP=BP⟹

ELT(BP)>ELT(BQ)&ELT(BP)>ELT(NQ)

(10)

(2)new_Bp=N⟹

ELT(NP)>ELT(BQ)&ELT(NP)>ELT(NQ)

(11)

假设现在不是选择最佳路径，而是选择通过Q节点的路径。这意味着

ELT(new_BQ)>ELT(BP)&ELT(new_BQ)>ELT(NP)

我们可以区分两种情况：

(1)new_BQ=BQ⟹

ELT(BQ)>ELT(BP)&ELT(BQ)>ELT(NP)

(12)

(2)new_BQ=N⟹

ELT(NQ)>ELT(BP)&ELT(NQ)>ELT(NP)

(13)

可以看到这两种情况都是矛盾的，所以一个节点将始终选择最优化的父节点，以最大限度地延长网络的瓶颈和时间。

4 仿真结果及分析

为了对ELT路由度量算法做出一个合理的评价，本文采用仿真器Contiki建立仿真平台，使用Cooja[14]仿真工具进行了仿真实验，网络中的所有节点分别使用ELT、ETX和剩余能量3种度量方式，其余的环境和参数都不发生变化。采用802.15.4 MAC层协议，在物理层使用路径衰落阴影模型，传输率RateData=1 pkt /min。仿真区域设定为300m×300m，节点数分别30、50、70、90且随机分布，仿真时间1小时，每次仿真重复20次，取其平均值作为最终的仿真结果。如表4所示，并通过以下几个方面进行比较。

表4 仿真参数

(1)数据包传输率

3个不同度量标准的RPL的数据包传输率曲线如图3所示。

图3 数据包传输率

从图3可知，数据包的传输率随着节点数增加而增加。ETX的数据包传输率最高，因为ETX方案只考虑链路质量为度量标准，而提出的ELT方案的数据包传输率逼近于ETX方案。此外，剩余能量方案的数据包传输率最低，它倾向于以节能的方式对节点进行特殊优化，而不考虑链路质量，会导致选择错误的链路来转发数据包，导致更多的数据包传输率下降。

(2)网络寿命

根据式(2)，绘制了节点的网络寿命，即网络中第一个节点能量耗尽的时间。最初，能量相同为10 J，保持同样的仿真区域，并增加了节点数量，当网络变得更密集时，由于瓶颈节点将不得不转发更多的数据包，所以网络寿命会减少。

从图4中可以看出ELT的寿命仍然优于ETX和剩余能量，与ETX相比，ELT使网络生命周期增加一倍。ETX拥有比剩余能量更好的生命周期，因为它选择了不需要重传很多次的高质量链路。

图4 网络寿命

(3)能量消耗

图5绘制了能量消耗随离sink节点距离的变化情况。从图5可知，剩余能量的平均能量消耗最少，但是这是以低的PDR为代价的，PDR越低，传输的数据包数量越少，相应地，消耗的能量越少。

图5 能量消耗

与ETX协议相比，ELT的能量消耗更小。此外，ELT设法平衡所有节点的能量消耗，无论距边界路由器的距离如何，平均消耗在60 J左右，这也表明了ELT基本实现了我们的能量平衡目标。

5 结束语

基于网络寿命，本文设计了一个路由度量标准ELT来构建DAG，通过选择最优父节点达到能量平衡负载，以延长网络生命周期。仿真结果表明，通过使用ELT度量，RPL协议在数据包传输率方面，其性能接近ETX，但是，在网络寿命方面是ETX的两倍，在能量消耗方面也实现了一个很好的均衡。后期将对瓶颈节点再预估进一步研究，尽量避免后续节点误选瓶颈节点的情况。