一种高能效低时延的LLN路由修复算法

钮 靖,2，于俊洋3，王秋红

(1.南阳医学高等专科学校，河南 南阳 473061；2.信阳师范学院 计算机与信息技术学院，河南 信阳 464000；3.河南大学 软件学院，河南 开封 475001)

1 引 言

低功耗有损网络[1](Low-power and Lossy Network,LLN)是一种由功耗较低的无线传感器节点组成且节点间无线链路不保证可靠性的多跳网络，主要有点到点、点到多点和多点到点3种通信模式，其中多点到点的通信模式是近年来的研究热点。传统的无线多跳网络路由协议[2-4]因能耗较大不能满足LLN网络的应用需求，因此互联网工程任务组提出了一种全新的基于IPv6的LLN网络路由协议(IPv6 based Routing Protocol for LLN,RPL)。由于LLN网络拥有广泛的应用场景[5-7]以及固有属性(不稳定性和有损性)，在外部复杂环境的干扰下极易导致链路故障的发生，因此，当检测到LLN网络中出现链路故障后，为了提高通信的可靠性和实时性，通过路由修复算法对网络拓扑进行修复具有较高的研究价值。

当前，对于LLN网络中出现的链路故障已开展了一些研究，提出了多种算法[8-11]。但是，现有路由修复算法主要存在以下不足：一是路由修复控制开销冗余，增大了节点的能耗速率，从而不能达到高能效的目的；二是路由修复时延较大，导致数据包端到端传输时延增大，从而影响数据的传输；三是链路故障修复后的网络拓扑结构未能达到最佳状态，主要原因在于对链路故障节点的子节点未进一步处理。

为了解决上述所存在的不足，本文提出了一种高能效低时延的LLN网络路由修复算法(Energy Efficient and Low Delay based Repair Routing Protocol for LLN,EELDR-RPL)，并对其性能进行了理论分析和数值验证。

2 网络模型

LLN网络的拓扑结构不同于传统的无线传感器网络，结合其自身特点，本文给出如下定义：

定义1 备选父节点集。在节点通信范围内且网络深度值小于或等于节点当前父节点的邻居节点的集合，被称之为节点的备选节点集，记为P。

定义2 兄弟节点集。在节点通信范围内且网络深度值与其相同的邻居节点的集合，被称之为节点的兄弟节点集，记为B。

定义3 子节点集。网络深度值大于当前节点且在当前节点通信范围内的邻居节点的集合，被称之为当前节点的子节点集，记为C。子节点集又包含非亲子节点集和亲子节点集，其中直接与当前节点处于连接状态的子节点集被称之为亲子节点集；反之，则被称之为非亲子节点集。

定义4 邻居节点集。在节点通信范围内的所有邻居节点的集合，被称之为节点的邻居节点集，记为N，其中P、B和C均被包含于C中。

EELDR-RPL算法的数学模型标记为G=(V,E)，其中V表示节点集合，E表示无线链路集合。网络中节点的邻居节点集合表示为Vn={V1,V2,V3},其中,V1={P1,P2,…,Pi}表示为节点的备选父节点集，V2={B1,B2,…,Bi}表示为节点的兄弟节点集，V3={C1,C2,…,Ci}表示为节点的子节点集。EELDR-RPL算法的网络模型如图1所示。

图1 EELDR-RPL算法的网络模型图Fig.1 Network model of EELDR-RPL

3 EELDR-RPL算法

针对LLN网络中现有路由修复算法存在控制开销冗余以及路由修复时延较大等问题，EELDR-RPL算法在路由修复的过程中进行了如下改进：

(1)为了避免增加额外的控制开销，提出了一种“零额外控制开销通告链路故障及邻居节点信息”机制，即对相关控制消息的帧格式稍作修改，使得链路故障节点的子节点能够及时获知链路故障以及链路故障节点的邻居节点情况；

(2)为了使得链路故障节点能够快速地重新接入网络，提出了一种“自适应调整节点网络深度值”机制，即链路故障节点根据其邻居节点信息自适应地调整自身的网络深度值；

(3)为了使得修复之后的网络拓扑更优，提出了一种“链路故障节点子节点自适应切换”机制，即链路故障节点的子节点通过控制消息获取到的链路故障节点邻居节点信息以及自身邻居节点信息进行自适应地切换当前链路连接状态。

3.1 零额外控制开销通告链路故障及邻居节点信息机制

为了避免增加额外的控制开销，设计了一种新的面向目的地有向无循环图(Destination Oriented Directed Acyclic Graph,DODAG)信息请求消息(New DODAG Information Solicitation,N-DIS)。该控制消息利用DIS控制消息中保留字段，将其第一位设置为无线链路故障通告字段L。其值为0时，表明当前节点为申请加入网络的新节点；其值为1时，表明当前节点与其最优父节点之间的无线链路处于故障状态。同时，将保留字段的第二位和第三位设置为当前节点的邻居节点信息字段N。当该字段的值为11时，表明当前节点拥有可建立连接的备选父节点；当该字段的值为10时，表明当前节点仅拥有可建立连接的兄弟节点；当该字段的值为01时，表明当前节点仅拥有可建立连接的子节点；当该字段的值为00时，表明当前节点无可建立连接的邻居节点。N-DIS控制消息的帧格式如图2所示。

图2 N-DIS控制消息的帧格式图Fig.2 Frame format of N-DIS control message

当检测到任意节点与其最优父节点之间的无线链路出现故障后，通过广播N-DIS控制消息重新申请接入到LLN网络中。当链路故障节点的子节点接收到上述N-DIS控制消息后，根据L字段便可获知链路故障节点与其最优父节点之间的当前无线链路连接状态。同时，链路故障节点的子节点根据N-DIS控制消息的N字段便可获知链路故障节点的邻居节点信息，从而便于“链路故障节点子节点自适应切换机制”的实施和操作。

3.2 自适应调整节点网络深度值机制

网络深度值的大小反映出节点在网络中的大致位置。距离根节点位置越近，节点的网络深度值相对越小。为了避免路由环路的产生，子节点的网络深度值必须小于其父节点的网络深度值[6]。

当检测到LLN网络中出现链路故障节点时，提出了一种新的网络深度值表示方法，即利用小数表示节点更新后的网络深度值，以便于链路故障节点能够根据其缓存的邻居节点信息自适应的调整自身的网络深度值，从而快速地重新接入网络而不受RPL标准的约束。

假设链路故障节点Q的当前网络深度值为m，其中m为整数，那么节点Q的网络深度值Rank将根据公式(1)进行自适应地调整：

(1)

当链路故障节点Q的网络深度值为m.1时，相对于其他节点，其网络深度值为(m+1)；当链路故障节点Q的网络深度值为m.2时，相对于其他节点，其网络深度值为(m+2)。那么，链路故障节点Q的网络深度值自适应调整策略具体如下：

(1)当链路故障节点Q从其缓存中检测到自身拥有可建立连接的备选父节点时，其网络深度值Rank保持不变，同时将N-DIS控制消息中的L字段设置为1，N字段设置为11，并向其备选父节点集组播N-DIS控制消息便可快速地重新申请接入到网络中；

(2)当链路故障节点Q从其缓存中检测到自身仅拥有可建立连接的兄弟节点时，将其网络深度值Rank更新为m.1，同时将N-DIS控制消息中的L字段设置为1，N字段设置为10，并向其兄弟节点集组播N-DIS控制消息便可快速地重新申请接入到网络中；

(3)当链路故障节点Q从其缓存中检测到自身仅拥有可建立连接的子节点时，将其网络深度值Rank更新为m.2，同时将N-DIS控制消息中的L字段设置为1，N字段设置为01，并向其子节点集组播N-DIS控制消息便可快速地重新接入到网络中；

(4)当链路故障节点Q从其缓存中检测到自身无可建立连接的邻居节点时，将其网络深度值Rank更新为，同时将N-DIS控制消息中的L字段设置为1，N字段设置为00，并广播N-DIS控制消息将其链路故障状态通告给其子节点，等待新一轮网络拓扑的重构。

3.3 链路故障节点子节点自适应切换机制

为了优化链路故障修复后的网络拓扑结构，需要对链路故障节点的子节点当前连接状态进行相应的调整。链路故障节点的子节点依据链路故障节点广播的N-DIS控制消息以及自身邻居节点信息进行自适应地更换与当前链路故障节点之间的连接状态，以此达到优化链路故障修复之后的网络拓扑结构的目的。链路故障节点子节点自适应切换机制的具体实施过程如下：

(1)当链路故障节点的子节点监听到链路故障节点发送的N-DIS控制消息后，检查N-DIS控制消息中的L字段。如果L字段的值为1，则继续检查N-DIS控制消息中的N字段。

(2)如果N字段的值为11，表明链路故障节点当前拥有可直接建立连接的备选父节点，那么链路故障节点的子节点则继续与其维持父子关系，也即对链路故障节点的子节点不作任何处理。

(3)如果N字段的值为10，表明链路故障节点当前仅拥有可直接建立连接的兄弟节点，那么链路故障节点的子节点检测自身的备选父节点集是否为空集。如果其备选父节点集不为空集，那么该链路故障节点的子节点将不再与当前链路故障节点继续维持父子关系，并从备选父节点集中选取一个节点建立新的连接状态，反之，该链路故障节点的子节点则继续与当前链路故障节点维持父子关系，并将其当前网络深度值更新为(m+1.1)。

(4)如果N字段的值为01，表明链路故障节点当前仅拥有可直接建立连接的子节点，那么链路故障节点的子节点检测自身的备选父节点集或是兄弟节点集是否为空集。如果该链路故障节点的备选父节点集或是兄弟节点集不为空集，那么该链路故障节点的子节点将不再与当前链路故障节点继续维持父子关系，并从备选父节点集或是兄弟节点集中选择一个合适的节点建立新的连接状态；反之，该链路故障节点的子节点则继续与当前链路故障节点维持父子关系，并将其当前网络深度值更新为(m+1.2)。

(5)如果N字段的值为00，表明链路故障节点无可建立连接的邻居节点，那么链路故障节点的所有子节点均不再与当前链路故障节点维持父子关系，并从邻居节点集中选择一个合适的节点建立新的连接状态。

3.4 EELDR-RPL算法操作步骤

EELDR-RPL算法的详细操作步骤如下：

Step1 在网络拓扑初始化创建过程中，每个节点均存储邻居节点的信息，并周期性地监听其亲子节点的邻居节点信息。

Step2 节点周期性地检测其链路是否发生故障，若发生故障则检测其备选父节点集是否为空集。若其备选父节点集不为空集，则向其备选父节点集组播N-DIS控制消息；反之，则进入Step 4。

Step3 链路故障节点选择其备选父节点集中最先回复DIO控制消息的节点作为新的父节点，且其子节点根据监听链路故障节点组播的N-DIS控制消息决定继续与其维持父子关系。

Step4 链路故障节点检测其兄弟节点集是否为空集，若其兄弟节点集不为空集，则向其兄弟节点集组播N-DIS控制消息；反之，则进入Step 6。

Step5 链路故障节点选择其兄弟节点集中最先回复DIO控制消息的节点作为新的父节点，并将其当前网络深度值加上0.1，且其子节点根据监听链路故障节点组播的N-DIS控制消息以及其备选父节点集是否为空集，从而决定是否继续与当前链路故障节点继续维持父子关系。

Step6 链路故障节点检测其非亲子节点集是否为空集，若其非亲子节点集不为空集，则向其非亲子节点集组播N-DIS控制消息；反之，则进入Step 8。

Step7 链路故障节点选择其非亲子节点集中最先回复DIO控制消息的节点作为新的父节点，并将其当前网络深度值加上0.2，且其子节点根据监听链路故障节点组播的N-DIS控制消息以及其备选父节点集或是兄弟节点集是否为空集，从而决定是否继续与当前链路故障节点维持父子关系。

Step8 链路故障节点向其亲子节点集中邻居节点为非空集的子节点组播N-DIS控制消息，且选择其亲子节点集中最先回复DIO消息的节点作为新的父节点，为了避免路由环路的产生，最先回复DIO控制消息的亲子节点需要将当前链路故障节点从其父节点列表中删除，且其他子节点根据监听链路故障节点组播的N-DIS消息以及其备选父节点集或是兄弟节点集或是子节点集是否为空集，从而决定是否继续与当前链路故障节点维持父子关系。

4 仿真实验及结果分析

为了定量验证EELDR-RPL算法的性能，本文通过OPNET 14.5仿真工具搭建模拟仿真平台分别实现FRR-RPL[13]、LRR-RPL[15]和EELDR-RPL算法的仿真验证，并对它们的性能进行定量比较和分析。

4.1 仿真环境及参数设置

在350 m×350 m的正方形区域内分别构建不同网络规模大小的模拟仿真场景，其中，网络规模大小分别为30、50、70、90和110，节点的通信半径为50 m，仿真时间为3 600 s。为了节点获知更多的邻居信息以便于链路故障修复，节点工作在存储模式。此外，为了确保网络场景的稳定性，网络中所有节点均采用静态或准静态模型。HLR-RPL算法在仿真过程中用到的其他主要参数设置如表1所示。

表1 其他主要仿真参数Tab.1 The main simulation parameters

4.2 仿真结果分析

4.2.1归一化控制开销比较

图3表明，随着网络规模的变化，EELDR-RPL算法的归一化控制开销明显低于FRR-RPL算法和LRR-RPL算法。通过深入分析，发现其主要原因在于：FRR-RPL算法和LRR-RPL算法在进行路由修复的过程中，均需要从链路故障节点处进行大量的信息交互操作之后链路故障节点才能够重新加入到网络中，这种操作越多，导致控制开销也就越大；而EELDR-RPL算法在进行路由修复的过程中，仅需要将DIS控制消息的帧格式稍作修改以及对链路故障节点及其子节点网络深度值进行自适应的调整，便可减少在路由恢复过程中的信息交互操作，从而降低了大量控制开销。

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

4.2.2链路故障平均修复时延比较

图4显示，随着网络规模的扩大，LRR-RPL算法的链路故障平均修复时延逐渐增大，而FRR-RPL算法和EELDR-RPL算法的链路故障平均修复时延变化不大，但EELDR-RPL算法的链路故障平均修复时延均低于LRR-RPL算法和FRR-RPL算法。其主要原因在于：LRR-RPL算法在路由修复过程中，需要先发送控制消息到达根节点，然后接收到根节点的反馈信息后才能实施链路反转操作；FRR-RPL算法在路由修复过程中，链路故障节点向其邻居节点发送控制消息，由邻居节点依次向上一跳转发，直至转发至网络深度值小于链路故障节点的上游节点，然后沿原路返回修改节点网络深度值，直至链路故障节点的网络深度值修改完成后才完成链路故障的修复；而EELDR-RPL算法在路由修复过程中，仅需要链路故障节点与其邻居节点进行少量的信息交互，使得链路故障节点能够快速地重新接入到网络中，从而有效地避免了FRR-RPL算法和EELDR-RPL算法中的冗余操作。

图4 链路故障平均修复时延比较Fig.4 Comparison of the average link failure repair delay

4.2.3根节点平均吞吐量比较

图5表明，FRR-RPL、LRR-RPL和EELDR-RPL算法的根节点平均吞吐量均随着网络规模的扩大而逐渐增大，但是EELDR-RPL算法的根节点平均吞吐量均明显高于FRR-RPL算法和LRR-RPL算法。通过分析发现，其主要原因在于：EELDR-RPL算法在路由修复过程中，链路故障节点根据其获知的邻居节点信息自适应地对自身的网络深度值进行调整后，通过少量的控制消息便可较快地重新接入网络，能够有效降低数据包端到端平均传输时延，而根节点平均吞吐量与数据包端到端平均传输时延成反比关系；EELDR-RPL算法在路由修复过程中，链路故障节点的子节点根据接收到的N-DIS控制消息以及其邻居节点信息判断是否需要维持与当前链路故障节点的连接状态，优化了链路故障修复后的网络拓扑结构，降低了数据包的平均传输跳数，相当于降低了数据包端到端平均传输时延。

图5 根节点平均吞吐量比较

5 结束语

针对LLN网络中现有路由修复算法存在控制开销冗余以及路由修复时延较大等问题，本文提出了EELDR-RPL算法。该算法包含3个创新机制：首先，通过采用零额外控制开销通告链路故障及邻居节点信息机制，使得链路故障节点的子节点能够及时获知链路故障状态以及链路故障节点的邻居情况；其次，通过采用自适应调整节点网络深度值机制，使得链路故障节点能够快速地重新接入网络；最后，通过采用链路故障节点子节点自适应切换机制，使得链路故障节点的子节点能够根据接收到的N-DIS控制消息及自身缓存的邻居节点情况进行自适应地切换与当前链路故障节点的连接状态，达到优化链路故障修复后的网络拓扑结构的目的。仿真结果表明，相对LLN网络中现有路由修复算法，EELDR-RPL算法能够有效地减少网络控制开销和降低路由修复时延，并且使得修复之后的网络拓扑结构能够达到更优状态。下一步将对移动汇聚节点场景下的链路故障修复策略进行研究。