基于剩余级别负载均衡的RPL路由协议

2018-05-03冯馨于仇英辉

传感技术学报 2018年4期

冯馨于,仇英辉

(华北电力大学电气与电子工程学院,北京 102206)

低功耗有损网络[1]LLNs(Low Power and Lossy Networks),一种比较特殊的无线传感器网络。由于构成该网络的嵌入式设备在功率、存储空间、处理能力等资源方面受到制约,容易造成数据在网络传输过程中的丢失。为了设计适用于 LLNs的路由协议,IETF(Internet Engineering Task Force)的ROLL(Routing Over Low power and Lossy)工作组提出了一种针对LLNs的路由协议RPL[2](Routing Protocol for Low-Power and Lossy Networks)。RPL路由协议对节点能量受限、链路不稳定等网络有较强的适应能力,因此有十分广阔的应用前景。

目前,国内外学者针对RPL的研究主要集中在能量均衡、负载均衡等方面。能量均衡方面,文献[3]提出了一种基于三角模算子的 RPL 协议路由优化算法,基于三角模融合算法,重新定义了网络节点的能量指标和逻辑距离隶属度并进行了融合,更为合理地进行父节点选定,降低了能量损耗。在负载均衡方面,文献[4]提出了一种基于普通节点负载均衡的RPL路由协议OLB-RPL,采用划分能量级别和改变通信半径两重负载均衡办法。但是文章对能量级别的划分不够灵活,这样在负载均衡进行到一定程度的时候无法继续进行负载均衡。为了更好地实现负载均衡,本文提出了一种基于剩余级别进行负载均衡的RPL路由协议的优化算法WLB-RPL。

1 RPL路由协议

RPL是规定在IPV6无线传感器网络WSN(Wireless Sensor Networks)中的一种距离路由矢量协议。RPL的核心思想是通过建立面向根节点的有向无环图DODAG(Destination Oriented Directed Acyclic Graph),最终实现网络中每一个节点都有一条到达根节点的路径,进而完成整个网络的路由拓扑图[5-6]。在这一过程中,RPL是通过使用目标函数和路由度量约束条件来完成DODAG构建的。

1.1 RPL路由过程

1.1.1 RPL控制消息

在RPL路由协议的整个组网过程中,DODAG拓扑的构建依靠RPL控制消息的交互。RPL严格的遵从IPV6架构,主要使用3种控制消息,分别是DIO,DAO,DIS。

①DODA信息对象DIO(DODAG Information Objection):是DODAG向下路径中的消息,主要包含节点所在DODAG相关的信息,比如DODAGID,Rank值等。

②DODAG目的广播对象DAO(Destination Advertisement Object):沿DODAG向上传播目的地信息通告。

③DODAG请求信息DIS(DODAG Information Solicitation):节点未收到DIO消息时,可以向周围节点广播DIS,用来请求DIO消息。

1.1.2 DODAG构建过程

DODAG的构建过程基于邻居发现机制,步骤具体如下:

①DODAG根节点广播DIO消息;

②节点A、B收到来自根节点的DIO消息,包括DODAGID、Rank值、目标函数等信息,节点据此判断是否加入该DODAG。如果节点决定加入该DODAG,就将带有自身路由前缀信息的DAO消息回复给根节点。节点B在决定加入DODAG之后,更新自己的Rank值并继续周期性的广播DIO消息。

③同理,节点C在收到来自节点B的DIO消息之后,判断是否加入该DODAG,若加入,则回复给父节点B一个DAO消息。

④节点B收到来自节点C的路由前缀信息DAO后,节点B也重复这一步骤,传回到根节点。

⑤假设节点D一直没有收到来自DODAG中的DIO消息,节点D可以主动给节点A发送一个DIS请求信息,请求加入DODAG。

⑥节点A发送DIO消息给节点D。

⑦节点将整合之后的路由前缀信息(包括自己及子节点的信息)传给父节点,该父节点再传给其父节点,节点反复重复这一步骤,直到根节点已经获得整个DODAG的前缀信息。至此,DODAG构建完成。

1.1.3 路由构建过程

①向上路由:由叶子节点向根节点的数据传输过程。

②向下路由:由根节点向叶子节点的数据传输过程。向下路由按照实际情况可以分为非存储模式和存储模式。

(a)非存储模式:所有的前缀信息由DODAG根节点保存,普通节点不保存任何子节点的前缀信息。例如图1中的C,传送DAO消息直到到达根节点。需要向下路由时,需要从根节点处查询到目的节点的转发路径。

图1 DODAG构建过程

(b)存储模式:节点保存其子节点的前缀信息。在构建向下路由的时候,只需要查找路由表,匹配子节点的前缀信息即可。父节点在收到子节点的DAO消息后,会将DAO消息中的地址信息存储在路由表中,整合之后传给根节点。据此,根节点和每个路由节点均知道通往子孙节点的下一跳信息。需要向下路由时直接查询路由表项即可。

1.2 RPL的路由策略

RPL的路由策略,取决于RPL关于目标函数OF(Objection Function)的定义。在同一个RPL实例中,必须使用同一个于目标函数。OF定义了怎么选取最佳父节点,怎么确定每个节点的Rank值以及根据哪一种路由度量和约束条件进行路径的选择。值得注意的是,OF表明了应该采用哪一种路由选取策略。此外,OF本身是多个函数的集合体,而不是指某一个单一的函数。不同的目标函数对应不同的应用场景。

1.2.1 RPL的路由度量和约束条件

无线传感器网络WSN(Wireless Sensor Network)不同于传统的网络以及ad hoc网络,据此,RPL在进行路径计算的时候采用的是特殊的度量和路由约束条件。

WSN中存在多种路由度量[7],主要分类如表1所示。

节点度量包括节点状态和属性、节点能量及节点跳数。节点能量描述的是和节点能量相关的信息,比如剩余能量所占百分比的估值以及供电模式(电源供电还是电池供电等)。

链路度量则包括节点的吞吐量、时延、可靠性等。

表1 不同的路由度量

在构建DODAG的时候,不同的应用场景要求不同的路由选择标准。例如在对网络生存时间要求较高或者能量极度受限的情况下,节点选择最佳路由的标准是剩余能量。

1.2.2 目标函数的实施

父节点的选取是目标函数的重要任务之一。任何可能会引起下一跳信息更新的事件比如父节点失效、定时器过期等,都会引发目标函数进行父节点的选择。

而Rank值也取决于目标函数。节点Rank值的计算方法如下面公式所示:

newRank=Rank+RankIncrease

(1)

newRank表示节点的新Rank值,Rank表示候选节点的Rank值,RankIncrease表示路由度量的增量值,即节点到候选父节点的相对位置的值。RankIncrease的具体数值取决于目标函数。

典型的目标函数如表2所示,主要包括OF0[8]、MRHOF[9]以及 ETXOF这3种。

表2 几种典型的目标函数

2 基于剩余级别进行负载均衡的RPL路由协议

目前提到的诸多RPL路由协议在一定程度上延长了网络寿命,但仍存在诸多能量消耗不均匀,负载不均衡等问题。文献[3]中提到的OLB-RPL引入剩余能量级别,以寻找最优传感器网络邻居节点范围为路由算法来实现RPL网络中普通节点的负载均衡。当负载数大于设置的对应阈值的时候,采取的办法是调整当前节点的通信半径(缩小通信半径)。因为能量的消耗,节点剩余能量级别会越来越小,对应的阈值也会相应的减小,所以在节点轮数更新的时候,会及时调整通信半径减少负载数来达到相应的负载均衡的效果。但是随着轮数的增加,剩余能量级别的下降趋势会趋于稳定,不利于负载均衡的继续进行。本文提出统计节点当前剩余能量的分布情况,然后对能级密集分布的节点进行更细的能量分级,以期达到更好的负载均衡。

2.1 参考度量

文献[3]RPL路径选择的主要依据是节点邻居距离di以及节点剩余能量级别REL,然而在考虑到节点能耗问题时应该考虑到节点的总能耗会随着邻居节点距离的增大而增大,所以定义了新的参考度量:节点剩余级别RL,在考虑节点的剩余能量的同时也考虑到了邻居节点的平均距离,通过加权来完善这一参考度量。

2.1.1 节点邻居距离

在网络初始时刻,设每个节点的通信半径为R0,也就是每个节点的功率发送的半径范围。每个节点都有自己的邻居节点集,对节点i而言,邻居节点集是指处于自己通信半径范围之内的节点的集合。通过测试信号i来记录各邻居节点到该节点的距离,该距离即为节点邻居距离d(i)neighbor:

d(i)neighbor=Dist(nodei,nodeineighbork)

(2)

式中:k表示第k个邻居节点。

2.1.2 剩余级别RL

本文引入剩余级别RL,通过对节点的的当前剩余能量以及节点之间的平均距离进行加权[10-14]来综合考虑能耗。另外,文章设置了每个能级RL对应的负载数目阈值Fi来实现负载均衡,即剩余能量少且平均邻居距离大的节点对应的负载少一点,剩余能量多且平均距离小的节点对应的负载相对多一点。剩余级别定义如下:

(3)

式中:Eicur(r)表示每个节点i的当前剩余能量,Eaverage表示每个等级的能量,其定义为:

Eaverage=E0/m

(4)

式中:E0表示节点最初能量,m表示节点有m个能量级别,D为到邻居节点的平均距离,其定义为:

(5)

式中:d(i)neighbor为节点邻居距离,n为周围邻居节点的总数。

(6)

式中:α是自适应调节因子,β为能量调节因子。随着采集轮数r的逐渐增加,节点当前剩余能量Eiour(r)逐渐减小。与此对应的是,β在区间[0,1]内逐渐减小,而a在区间[1/2,1]呈现逐渐增大的趋势。这样随着信息采集轮数的增多,a的逐渐增大,剩余能量这一权值因子在剩余级别中所占的比例会越来越大,以保证剩级别这一参数的合理性。

图2 流程图

2.2 WLB-RPL路由协议

图2为改进之后的动态的m的流程图。

步骤如下:

S1 初始化,设置节点初始半径。发送测试信号,统计邻居节点及节点邻居距离di;

S2 对每个节点进行能级划分,设每个节点有m个能量级别,取m=10;

S3 统计每个节点的当前剩余能量,记为Ei_cur;

S4 找出最多节点数的能级,记为n;

S5 统计该能级以及该能级前后的能级,即能级数分别为n,n+1,n-1这3个能级的节点总数,若节点总数没有占到当前存活节点总数的一半以上,如下公式所示。

(7)

则每个节点各自计算自己的剩余级别RLi_cur,并确认当前剩余能量级别RELi_cur所对应的负载门限Fi。统计自己所携带的负载数fi,判断Fi是否小于fi;

S6 若Fi小于fi,则对当前通信半径进行调整,减少通信半径。通信半径调整策略描述如下:

设某一时刻节点i的通信半径为Ri,调整后的通信半径为Ri+1,起初节点i通信半径范围覆盖的子节点有节点1～n,当检测到负载门限Fi小于携带负载数fi时,计算通信半径的调整值Δ:

Δ=(d1+d2+d3+…+dn)/n

(8)

则新的通信半径为

Ri+1=Ri-Δ

(9)

显然,Ri+1

若Fi大于fi,则保持通信半径不变,不必进行接下来的负载均衡机制。

S7 若这3个能级的节点总数占到了当前存活节点总数的一半以上,如下公式所示。

(10)

则对位于这3个能级的节点进行更细的节点能量分级(取m=20),负载均衡机制参考S5,S6。

3 仿真实验结果

本文对算法性能进行了评估,通过与RPL相比较,验证了WLB-RPL在数据采集轮数下的网络总能耗、网络死亡节点数等方面的性能。

本文通过MATLAB仿真平台进行仿真实验,在实验中设置了250个网络节点,随机分布在100×100的区域内。把区域划分成两个DODAG,并手动选取区域内横纵坐标最小的节点作为DODAG分区内各自的Sink节点。Sink节点的初始能量设置为1.0,普通节点的能量则设置为0.45～1.0之间的随机值。

表3 仿真参数设置

仿真参数的设置能够根据网络大小等具体情况来实现灵活地配置,但也应该拟合实际系统的通信的需求。因此,仍需要增加以下假设:①当节点剩余能量小于5%时,即认为节点失效死亡。②仿真中RPL和WLB-RPL的更新周期都是96,但WLB-RPL也是实时更新的,每50轮更新一次。③发送信息能耗采用的能量模型是E=δ·d3,δ取值为δ=0.000 1(1/253)。

负载均衡的主要指标有网络总能耗以及网络死亡节点数目。网络总能耗可以直观反映节点能量消耗的平均情况。由于负载过重的节点容易提前死亡,所以网络节点死亡数目可以体现网络的通信负载均衡性能。

为了验证WLB-RPL性能的优越性,本文分别比较了RPL和WLB-RPL在一定数据采集轮数下的网络死亡节点数和网络总能耗。

图3 网络平均能耗对比图

WLB-RPL和RPL的网络平均能量消耗对比图如图3所示。由图3可知改进的算法能量消耗更加均衡,各个阶段的能量消耗都少于RPL算法。网络初始化阶段,由于RPL和WLB-RPL使用相同的路由建立过程,因此初始能耗一致。随着采集轮数的增加,RPL的网络总能耗稳步增加,而WLB-RPL出现了一段骤降。本文的WLB-RPL算法中网络的拓扑更新周期是50,即每50轮重新进行一次动态路由选择。依据算法的原理,网络中的节点负载数超过能级对应的阈值时,节点通过调整通信半径的方法把自己的负载数调整到阈值范围内,网络得到均衡优化,这就是出现骤降的原因;随着时间的推移,能耗逐渐增加,直至最后达到动态平衡。

图4呈现的是数据采集轮数和网络死亡节点数目的关系。由图4可得,RPL最早出现死亡节点数出现在105轮,而WLB-RPL的死亡节点数最早出现在227 轮,比未改进的RPL延迟了122轮;而同一轮内的死亡节点数也明显减少,相比RPL平均减少39.6%的死亡节点。从纵向的角度观察可得出,在横坐标相同的时候,即同样的数据采集轮数下,WLB-RPL的网络死亡节点数也少的多。由此证明达到了网络负载均衡的效果。

图4 网络节点死亡数对比图

从横向的角度观察可得出,当网络的死亡节点数达到同样的水平时,WLB-RPL所完成的数据采集轮数远远大于RPL协议。从这个角度来说,该算法大大提高了网络的生命周期。同时,当死亡节点数分别为50,100,150的时候,WLB-RPL相对RPL算法的数据采集轮数提高的比例分别是49.27%,33.89%,41.79%。总之,可见本算法有效提升了网络的生命周期,延长了节点平均寿命,保证了系统的经济性和环保性。

4 结论

本文针对低功耗有损网络的特点,在原有负载均衡的基础上,提出了一种基于加权的WLB-RPL路由协议,降低了网络能耗,实现了更好的负载均衡。本文提出的算法针对能级降到一定程度无法继续进行负载均衡的情况,对于能级分布过于密集的节点采用更细的能级划分,并提出了关于能级的新的加权的函数,更好的完善了负载均衡机制。仿真实验表明,算法有效均衡了网络负载,降低了能量损耗,延长了网络生命周期。

参考文献:

[1] Kulau U,Müller S,Schildt S,et al. Energy Efficiency Impact of Transient Node Failures when Using RPL[C]//IEEE,International Symposium on A World of Wireless,Mobile and Multimedia Networks. IEEE,2017:1-6.

[2] Tahir Y,Yang S,Mccann J A. BRPL:Backpressure RPL for High-Throughput and Mobile IoTs[J]. IEEE Transactions on Mobile Computing,2017,PP(99):1-1.

[3] 仇英辉,何霖. 基于三角模算子的RPL协议路由优化算法[J]. 传感技术学报,2015,28(12):1861-1866.

[4] 仇英辉,陈玲. 基于普通节点负载均衡的RPL路由协议[J]. 传感技术学报,2016,29(7):1077-1082.

[5] 杨及开. 无线传感器网络中的RPL路由协议研究[D]. 重庆:重庆邮电大学,2016.

[6] 高筱菲. 基于RPL的无线传感器网络分簇路由研究与实现[D]. 北京:北京交通大学,2014.

[7] 周兰. IPv6无线传感网网络层协议研究[D]. 南京:南京邮电大学,2013.

[8] Thubert P. Objective Function Zero for the Routing Protocol for Low-Power and Lossy Networks(RPL)[J]. 2012,rfc 6552.

[9] Gnawali O. The Minimum Rank with Hysteresis Objective Function The[J]. RFC 6719(Proposed Standard,2012.).

[10] 张祎江,余金森,郝平. 基于线性参数加权评估机制的无线传感器网络节点定位[J]. 计算机工程,2017,43(2):156-162.

[11] 周兰. IPv6无线传感网网络层协议研究[D]. 南京:南京邮电大学,2013.

[12] 胥楚贵,邓晓衡,邹豪杰. 无线传感器网络通信半径动态调整的能耗均衡策略[J]. 传感技术学报,2009,22(5):712-716.

[13] 朱光辉,张修如,刘卫彪. 无线传感器网络中能量有效的加权分簇算法[J]. 传感器世界,2007,26(4):102-105.