LLN中基于环路避免的高效路由修复算法

姚玉坤, 刘江兵, 李小勇, 任 智

(重庆邮电大学移动通信技术重庆市重点实验室, 重庆 400065)

0 引 言

随着物联网技术[1]的快速发展,无线传感器节点以自组织的方式构成的无线传感器网络(wireless sensor networks, WSN)被广泛地应用于环境监测[2]、医疗保健[3]、工业控制[4]、城市交通[5]和现代化农业[6]等领域。其中,备受人们关注的低功耗有损网络(low power and lossy networks, LLN)[7-8]成为了目前的研究热点。

LLN具有以下两方面的特征:一是网络中的节点内存大小、处理能力和能量均受到限制;二是网络中的链路具有不稳定性和有损性。因此,国际互联网工程任务组(internet engineering task force, IETF)提出了一种基于IPv6的LLN路由协议(routing protocol for LLN, RPL)[9-11]。

目前,针对RPL的研究主要集中于网络负载均衡[12-14],以此达到延长网络寿命的目的。然而,对于RPL路由修复的研究还不够深入。由于LLN因自身固有的特性以及外部环境的干扰极易导致网络拓扑的不稳定,使得链路中断情况时有发生,从而严重影响网络性能。因此,当检测到LLN中链路出现故障后,通过路由修复算法对网络拓扑加以维护,这对提高通信的可靠性和实时性以及延长网络生命周期显得极其重要。

1 相关工作

近年来,在LLN路由修复方面已经开展了一些工作。当检测到网络拓扑出现故障后,文献[9]中首先由链路中断节点广播网络深度值为无穷大的面向目的地的有向无循环图(destination oriented directed acyclic graph, DODAG)信息对象(DODAG information object, DIO)消息通告其所有子节点不再维持连接状态,然后由链路中断节点广播DODAG信息请求(DODAG information solicitation, DIS)消息重新加入到网络中。该算法控制开销和修复时延均较大,且一旦DIO消息丢失极易产生路由环路。

当链路中断节点无备选父节点时,文献[15]提出了一种基于链路反转的RPL路由修复算法(link-reverse repair routing protocol for LLN, LR-RPL),该算法通过引入时序,并结合节点的网络深度值共同决定节点在网络中的位置,从而实现链路中断节点与其子节点之间的链路反转。针对路由环路的问题,文献[16]提出了一种基于路由环路避免的链路反转RPL路由修复(loop-free based link-reverse repair-RPL, LLR-RPL)算法,该算法相比文献[15]在实施链路反转的过程中新增了反转路径的选择策略。文献[17]提出了一种路由环路避免的RPL路由修复算法(loop free based repair-RPL, LFR-RPL),该算法通过维持链路中断节点与其所有子节点的连接状态,仅由链路中断节点广播DIS消息重新加入网络,从而避免路由环路的产生。上述两种算法的控制开销和路由修复时延均较大,且修复后的网络并非最优。文献[18]提出了两种路由环路避免的RPL路由修复方法:一种是基于序列号进行路由修复,即链路中断节点利用本地和全局序列号发现新的路径;另一种是ACK(acknowledgement)消息确认机制,链路中断节点需确保其所有子节点均接收到链路中断节点广播的DIO消息。该机制修复时延同样较大且无法彻底避免路由环路的产生。

然而,上述针对LLN中现有路由修复方案存在以下3个方面的不足:①控制开销较大,不利于网络节能;②路由修复时延较大,不利于网络中数据的传输,影响网络吞吐量;③修复后的网络拓扑并非最优,主要在于链路中断节点的子节点是否继续与之保持连接状态还无明确判定机制。

为了解决上述LLN中现有路由修复算法存在的不足,本文提出一种LLN中基于环路避免的高效路由修复(highly-efficient loop-free based repair-RPL, HLR-RPL)算法,并对其性能进行理论分析和验证。

2 网络模型

以图1所示的网络拓扑模型图为例。其中,根节点为数据汇聚节点,R1～R8为中继节点,S1～S7叶子节点。关于LLN有如下假设:

假设1根节点位于网络区域正上方,其余节点均随机部署,且处于静态或准静态;

假设2除了根节点以外,每个节点的物理构造和属性均相同且能量有限。

图1 网络拓扑模型图Fig.1 Figure of network topology model

为了便于分析,本文给出如下几个定义:

定义1备选父节点集:与节点i的父节点j的网络深度值相同或是网络深度值小于节点j且在节点i的通信范围内的所有节点的集合P(i)。

定义2兄弟节点集:与节点i的网络深度值相同且在节点i的通信范围内的所有节点的集合B(i)。

定义3非亲子节点集:比节点i的网络深度值大1且在节点i的通信范围内的所有节点的集合C(i)。

在叶子节点向根节点进行数据汇聚传输的过程中,由于链路的有损性和不稳定性,容易导致节点间的链路中断。通常链路中断分为4种:①链路中断节点拥有可连接的备选父节点;②链路中断节点无可连接的备选父节点,但拥有可连接的兄弟节点;③链路中断节点既无可连接的备选父节点也无可连接的兄弟节点,但拥有可连接的非亲子节点;④链路中断节点既无可连接的备选父节点也无可连接的兄弟节点,同时又无可连接的非亲子节点。

3 HLR-RPL算法

针对LLN中现有路由修复方案存在控制开销冗余、修复时延较大和路由环路等问题,HLR-RPL算法进行了如下改进:①提出“取消拆路消息”机制,即通过采用一种改进的DODAG信息请求消息(DIS-amend, DIS-A)使得链路中断通告过程和寻路过程同时进行;②提出“减少控制消息回复”机制,避免所有接收到链路中断节点广播的DIS消息的邻居节点均回复DIO消息;③提出“子节点切换”机制,从而达到优化网络拓扑的目的。

3.1 取消拆路消息机制

在取消拆路消息机制中,取消原有路由修复方案中链路中断节点单独发送额外控制消息通告链路故障的步骤,通过使用改进后的DIS-A消息同时实现链路中断通告过程和路由寻路的过程,即链路中断节点通过广播DIS-A消息就可以使得其所有子节点均获得其链路连接中断状态。DIS-A消息的帧格式如图2所示,从DIS消息帧格式中的保留(Reserved)字段中取前3 bits设置为邻居字段(neighbor field, NF),表示当前链路中断节点是否拥有可连接的备选父节点、兄弟节点和非亲子节点,并且在DIS消息帧格式中的选项部分添加节点的网络深度值(Rank)字段。此外,DIS-A消息的Type类型与DIS消息不同。

图2 DIS-A消息帧格式Fig.2 Frame format of the DIS-A message

3.2 减少控制消息回复机制

减少控制消息回复机制的核心思想为链路中断节点的所有邻居节点一旦接收到其广播的DIS-A消息后,并非每个接收到DIS-A消息的邻居节点都需回复DIO消息,而是根据接收到的DIS-A消息中的NF和Rank字段决定是否需要回复DIO消息。仅仅符合作为链路中断节点父节点的邻居节点才需回复DIO消息,不符合作为父节点的邻居节点接收到DIS-A消息后,将其丢弃不做任何处理。

假设链路中断节点的网络深度值为N(N为整数),那么减少控制消息回复机制的具体操作步骤如下。

步骤1邻居节点接收到链路中断节点广播的DIS-A消息后检测DIS-A消息的NF字段。若NF字段的第1位为1,则表明链路中断节点拥有可连接的备选父节点,那么仅网络深度值小于N的邻居节点回复DIO消息;若DIS-A消息中NF字段的第1位为0,表明链路中断节点无可连接的备选父节点,则转至步骤2。

步骤2若邻居节点接收到的DIS-A消息中NF字段的第2位为1,则表明链路中断节点拥有可连接的兄弟节点,那么仅网络深度值等于N的邻居节点回复DIO消息;若DIS-A消息中NF字段的第2位为0,表明链路中断节点无可连接的兄弟节点,则转至步骤3。

步骤3若邻居节点接收到的DIS-A消息中NF字段的第3位为1,则表明链路中断节点拥有可连接的非亲子节点,那么仅网络深度值为(N-1)的邻居节点回复DIO消息;若DIS-A消息中NF字段的第3位为0,则表明链路中断节点无可连接的非亲子节点,那么无邻居节点回复DIO消息。

3.3 子节点切换机制

子节点切换机制的核心思想为当链路中断节点的子节点接收到DIS-A消息后,根据DIS-A消息帧格式中的NF字段判断是否与其父节点继续保持连接状态。具体操作步骤如下。

步骤1当链路中断节点的子节点接收到链路中断节点广播的DIS-A消息后,检测DIS-A消息中的NF字段。若NF字段的第1位为1,表明链路中断节点拥有可连接的备选父节点,那么链路中断节点的子节点继续与其保持连接状态;若DIS-A消息中NF字段的第1位为0,则转至步骤2。

步骤2链路中断节点的子节点检测DIS-A消息中NF字段的第2位。若DIS-A消息中的NF字段的第2位为1,表明链路中断节点拥有可连接的兄弟节点,那么根据链路中断节点的子节点是否拥有可连接的备选父节点决定是否需要与之继续保持连接状态。如果链路中断节点的子节点拥有可连接的备选父节点,则与其不再保持连接状态,即从父节点列表中删除链路中断节点的路由信息。反之,则继续与其保持连接状态;若DIS-A消息中FB字段的第2位为0,则转至步骤3。

步骤3链路中断节点的子节点检测DIS-A消息中NF字段的第3位。若DIS-A消息中NF字段的第3位为1,表明链路中断节点拥有可连接的非亲子节点,那么根据链路中断节点的子节点是否拥有可连接的备选父节点或是可连接的兄弟节点判断是否需要与之继续保持连接状态。如果链路中断节点的子节点拥有可连接的备选父节点或是可连接的兄弟节点,则与其不再保持连接状态,即从父节点列表中删除链路中断节点的路由信息。反之,则继续与其保持连接状态;若DIS-A消息中NF字段的第3位为0,则转至步骤4。

步骤4DIS-A消息中NF字段的第1位、第2位和第3位均为0,表明链路中断节点既无可连接的备选父节点也无可连接的兄弟节点,同时也没有可连接的非亲子节点,那么链路中断节点的所有子节点将不再与其保持连接状态,即从父节点列表中删除链路中断节点的路由信息。

3.4 HLR-RPL算法操作步骤

HLR-RPL算法的具体操作流程如图3所示。

HLR-RPL算法的操作步骤从网络拓扑初始化之后开始,具体实施步骤如下。

步骤1当节点i检测到与其父节点j之间的链路中断后,节点i将节点j从其父节点集P(i)中删除。

步骤2节点i检测其父节点集P(i)是否为空集。若P(i)不为空集,将DIS-A消息中NF字段的第1位设置为1,并广播DIS-A消息。仅P(i)中的节点接收到DIS-A消息后回复DIO消息,然后节点i从回复DIO消息中的节点选择一个节点k1作为父节点,并向其单播一个目的地通告消息(destination advertisement object, DAO),且节点i的子节点接收到DIS-A消息后不作任何处理,继续与之保持连接状态;若P(i)为空集,将DIS-A消息中NF字段的第1位设置为0,并转至步骤3。

图3 HLR-RPL路由修复流程图Fig.3 Flow chart of HLR-RPL routing repair

步骤3节点i检测其兄弟节点集B(i)是否为空集。若B(i)不为空集,将DIS-A消息中NF字段的第2位设置为1,并广播DIS-A消息。仅B(i)中的节点接收到DIS-A消息后回复DIO消息,然后节点i从回复DIO消息中的节点选择一个节点k2作为父节点,并向其单播一个DAO消息,且其子节点接收到DIS-A消息后根据有无可连接的备选父节点决定是否继续与之保持连接状态;若B(i)为空集,将DIS-A消息中NF字段的第2位设置为0,并转至步骤4。

步骤4节点i检测其非亲子节点集C(i)是否为空集。若C(i)不为空集,将DIS-A消息中NF字段的第3位设置为1,并广播DIS-A消息。仅C(i)中的节点接收到DIS-A消息后回复DIO消息,然后节点i从回复DIO消息中的节点选择一个节点k3作为父节点,并向其单播一个DAO消息,且其子节点接收到DIS-A消息后根据有无可连接的备选父节点或兄弟节点决定是否继续保持连接状态;若C(i)为空集,将DIS-A消息中NF字段的第3位设置为0,并转至步骤5。

步骤5节点i广播DIS-A消息,且将其网络深度值更改为无穷大,等待网络拓扑的更新直至全局修复过程的到来。同时,节点i的所有子节点接收到DIS-A消息后均不再与其保持连接状态且重复节点i的处理过程。

3.5 HLR-RPL算法性能的理论分析

假设LLN中有S个中继节点因出现故障而导致链路中断,其中拥有可连接备选父节点的链路中断节点有m个,无可连接备选父节点但拥有可连接兄弟节点的链路中断节点有n个,既无可连接备选父节点也无可连接兄弟节点但拥有可连接的非亲子节点的链路中断节点有h个。另外,不考虑控制消息出现丢包的情况。

关于HLR-RPL算法的性能,提出引理1和引理2。

引理1与现有LLN中路由修复算法相比,HLR-RPL的路由修复控制开销低于LFR-RPL。

(mQ+nM+hN)lD

(1)

lA(m+n+n)

(2)

式中,M表示每个链路故障节点拥有的可连接兄弟节点个数；N表示每个链路故障节点拥有的可连接子节点个数；M和N均大于0。则有

(mQ+2nM+3hN)lR-(nM-2hN)lD

(3)

证毕

引理2与现有LLN中路由修复算法相比,HLR-RPL的路由修复时延低于LFR-RPL。

证明设TH和TL分别表示HLR-RPL和LFR-RPL在相同网络拓扑情况下的路由修复时延,一跳范围内每个DIS消息的传输时延为t1,每个DIS-A消息的传输时延为t2,每个DIO消息的传输时延为t3,每个DAO消息的传输时延t4,故有

TH=m(t2+t3+t4)+n(t2+t3+t4)+h(t2+t3+t4)=

(m+n+h)(t2+t3+t4)

(4)

TL=m(t1+t3+t4)+n(2t1+2t3+t4)+

h(3t1+3t3+t4)=(m+2n+3h)(t1+t3)+

t4(m+n+h)

(5)

证毕

4 仿真实验及结果分析

本文采用OPNET Modeler 14.5仿真软件对HLR-RPL算法的性能进行仿真验证,在相同仿真模拟场景下,选取LR-RPL[12]、LLR-RPL[13]和LFR-RPL[14]算法进行比较和分析。

4.1 统计量定义

4.1.1 归一化控制开销

归一化控制开销指在网络运行时间内网络中除根节点外所有节点发送和转发的控制消息比特数与网络中所有节点发送和转发的控制消息和到达根节点数据包的比特数的比值,表示为

NC=γC/(γC+γD)

(6)

式中,NC表示为节点归一化控制开销;γC表示网络中所有节点发送和转发的控制消息比特数;γD表示网络中所有节点发送和转发的控制消息和到达根节点的数据包的比特数。

4.1.2 路由修复平均时延

路由修复平均时延是指在网络运行时间内当检测到网络出现故障后,所有链路故障节点重新加入到网络中所耗费的平均时间,表示为

(7)

式中,TRi表示网络中的链路故障节点i重新加入到网络中所耗费的时间;n表示在网络运行时间内出现链路故障的节点总数。

4.1.3 网络生存时间

网络生存时间是指在网络运行时间内网络中能量耗尽节点的数量达到节点总数的10%所耗费的时间,表示为

TL=Td-T0

(8)

式中,Td表示网络中死亡节点数量达到总的节点数量10%的时刻;T0表示网络开始运行的时刻。

4.1.4 路由环路产生的概率

路由环路产生的概率是指在网络运行时间内,路由修复过程中出现路由环路的链路故障节点数与链路故障节点总数量的比值,表示为

ρ=NumRL/NumLB

(9)

式中,NumRL表示路由修复过程中出现路由环路的链路故障节点数;NumLB表示网络中链路故障节点数量。

4.2 仿真环境及参数设置

在300 m×300 m的模拟仿真区域内根据节点数量不同设置6个不同仿真场景,场景中的节点均随机分布且位置一旦固定将不再移动。网络中除根节点外,其余节点的初始能量相同且在仿真过程中不补给能量。由于节点受限于能量和处理能力,故节点数据传输速率不宜过高。同时,考虑链路的有损性,应设定链路损耗因子。另外,为了便于节点记录其邻居节点信息,节点采用存储模式。为了使结果更加可靠,在每个场景中分别多次模拟运行上述4种路由修复算法,取平均值作为最终结果。主要参数设置如表1所示。

表1 主要仿真参数

4.3 仿真结果分析

4.3.1 归一化控制开销

如图4所示,HLR-RPL的归一化控制开销均低于LFR-RPL、LR-RPL和 LLR-RPL,而且随着网络规模的扩大,从0.49降低到0.25。HLR-RPL能够减少归一化控制开销的主要原因有以下两点:首先,通过改进后的DIS-A消息能够同时实现链路中断通告过程和寻路过程,省去了链路中断通告开销;其次,通过改进后的DIS-A消息能够避免所有接收到DIS-A消息的邻居结点均回复DIO消息,仅符合作为链路中断节点父节点的邻居节点回复DIO消息,从而有效地降低了控制开销,与引理1分析的结果一致。而控制开销的减少降低了可用信道带宽的占用,从而增加了根节点接收的数据包数量,故控制开销的减少可以有效地降低归一化控制开销。

图4 归一化控制开销比较Fig.4 Comparison of the normalized control overhead

4.3.2 路由修复平均时延

如图5所示,HLR-RPL、LFR-RPL和LR-RPL的路由修复平均时延随着网络规模的扩大变化不大,而LLR-RPL的路由修复平均时延随着网络规模的扩大变化相对较大。且在每个场景中,HLR-RPL的路由修复平均时延明显低于其3种算法,至少降低了32.64%,与引理2分析的结果一致。分析其主要原因在于，HLR-RPL利用DIS-A消息同时实现链路中断通告过程和寻路过程,有效地降低了路由修复时延;其次,符合作为链路中断节点父节点的邻居节点一旦接收到DIS-A消息后立即回复DIO消息即可修复链路故障,对路由修复时延有降低作用。

图5 路由修复平均时延比较Fig.5 Comparison of the average routing repair delay

4.3.3 网络生存时间

如图6所示,与LFR-RPL、LR-RPL和LLR-RPL相比,HLR-RPL算法的网络生存时间至少能够延长9.28%。

图6 网络生存时间比较Fig.6 Comparison of the network survival time

分析其主要原因在于，HLR-RPL通过DIS-A消息同时实现链路中断通告过程和寻路过程,以及减少了不必要回复DIO消息的邻居节点个数,从而降低了节点的能耗;其次,HLR-RPL通过子节点切换机制能够使得修复后的网络拓扑达到最优状态,减少了数据分组的传输跳数,从而降低了数据分组的传输能耗。

4.3.4 路由环路产生的概率

如表2所示,HLR-RPL、LLR-RPL和LFR-RPL在各个场景中的路由环路产生概率均为0,表明均具有较好的可靠性。分析其主要原因在于，当检测到链路出现故障后,HLR-RPL和LFR-RPL中的链路中断节点选择其子节点作为父节点的概率为0;LLR-RPL中的链路故障节点仅选择接收到链路中断通告消息的子节点进行链路反转,从而彻底避免了路由环路的产生;然而,LR-RPL的路由环路产生概率随着网络规模的扩大逐渐发生变化,主要原因在于链路故障节点数量的增加,而一旦当链路中断通告消息丢失就会形成路由环路。

表2 路由环路产生的概率对比

5 结 论

由于LLN中现有路由修复方案存在控制开销冗余、修复时延较大和路由环路等问题,本文提出了HLR-RPL路由算法。为了使路由修复高效,该算法利用DIS-A消息使得链路中断通告过程和寻路过程同时进行;通过减少控制消息回复机制,避免所有接收到DIS-A消息的邻居节点均回复DIO消息;通过子节点切换机制能够优化网络拓扑,有利于数据的传输。理论分析和仿真结果表明,相对现有路由修复方案,HLR-RPL能够有效降低网络控制开销、缩短修复时延和优化网络拓扑,并且能够彻底避免路由环路的产生。在未来工作中,将研究一种适用于动态的LLN路由修复算法。

参考文献：

[1] MINOLI D, SOHRABY K, OCCHIOGROSSO B. IoT considerations, requirements, and architectures for smart buildings-energy optimization and next generation building management systems[J].IEEE Internet of Things Journal,2017,4(1):269-283.

[2] VISCONTI P, ORLANDO C, PRIMICERI P. Solar powered WSN for monitoring environment and soil parameters by specific app for mobile devices usable for early flood prediction or water savings[C]∥Proc.of the 16th International Conference on Environment and Electrical Engineering, 2016: 1-6.

[3] ALAIAD A, ZHOU L. Patients’ adoption of WSN-based smart home healthcare systems: an integrated model of facilitators and barriers[J].IEEE Trans.on Professional Communication,2017,60(1): 4-23.

[4] CHENG B, ZHAO S, WANG S, et al. Lightweight mashup middleware for coal mine safety monitoring and control automation[J]. IEEE Trans.on Automation Science and Engineering, 2017, 14(2): 1245-1255.

[5] HU X, YANG L, XIONG W. A novel wireless sensor network frame for urban transportation[J]. IEEE Internet of Things Journal, 2015, 2(6): 586-595.

[6] ABOUZAR P, MICHELSON D G, HAMDI M. RSSI-based distributed self-localization for wireless sensor networks used in precision agriculture[J]. IEEE Trans.on Wireless Communications, 2016, 15(10): 6638-6650.

[7] KIM H S, IM H, LEE M S, et al. A measurement study of TCP over RPL in low-power and lossy networks[J]. Journal of Communications and Networks, 2015, 17(6): 647-655.

[8] PAEK J. Fast and adaptive mesh access control in low-power and lossy networks[J]. IEEE Internet of Things Journal, 2015, 2(5): 435-444.

[9] RFC 6550. RPL: IPv6 routing protocol for low-power and lossy networks[S]. IETF, 2012.

[10] RFC 6552. Objective function zero for the routing protocol for low-power and lossy networks[S].IETF,2012.

[11] RFC 6719. The minimum rank with hysteresis objective function[S]. IETF, 2012.

[12] KIM H S, KIM H, PAEK J, et al. Load balancing under heavy traffic in RPL routing protocol for low power and lossy networks[J]. IEEE Trans.on Mobile Computing, 2017, 16(4): 964-979.

[13] ZHAO M, HO I W H, CHONG P H J. An energy efficient region-based RPL routing protocol for low-power and lossy networks[J].IEEE Internet of Things Journal,2016,3(6):1319-1333.

[14] 姚玉坤,刘江兵,任智,等.集中式网络拥塞控制的高效RPL路由协议[J].系统工程与电子技术,2017,39(12)：2810-2816.

YAO Y K, LIU J B, REN Z, et al. High-efficient centralized network congestion control for RPL routing protocol[J]. Systems Engineering and Electronics, 2017, 39(12)：2810-2816.

[15] LA C A, HEUSSE M, GRENOBLE A D. Link reversal and reactive routing in low power and lossy networks[C]∥Proc.of the 24th International Symposium on Personal Indoor and Mobile Radio Communications, 2013: 3386-3390.

[16] AUDEOUD H J, KROL M, HEUSSE M, et al. Low overhead loop-free routing in wireless sensor networks[C]∥Proc.of the 11th International Conference on Wireless and Mobile Computing, Networking and Communications, 2015: 443-451.

[17] GUO J, HAN C, ORLIC P, et al. Loop-free routing in low-power and lossy networks[C]∥Proc.of the 6th International Conference on Sensor Technologies and Applications, 2012: 59-66.

[18] KAMPEN A L, OVSTHUS K, KURE Ø. Reconnection strategies in WSN running RPL[C]∥Proc.of the 39 th Conference on Local Computer Networks Workshops, 2014: 602-609.