高负载场景下基于负载均衡的LLN路由协议

秦 峰，曾 浩，2，林开东

1.重庆邮电大学 通信与信息工程学院，重庆400065

2.重庆邮电大学 电工理论与新技术实验室，重庆400065

1 引言

低功耗有损网络（Low-power and Lossy Networks，LLN）[1-2]被认为是一种特殊的无线传感器网络，在物联网[3-4]等领域中具有广泛的应用前景。LLN 通常由大量的嵌入式设备组成，然而组成LLN 的这些嵌入式设备往往受到一定的限制，譬如能量供应不足，存储空间较小和处理能力较弱。因此，鉴于LLN 的广泛应用前景和其特有的性质，设计出一种适用于LLN 的路由协议显得尤为重要。

2008 年，国际互联网任务工程组制定了一种基于IPv6 的低功耗有损网络路由协议（Routing Protocol for Low-power and Lossy network，RPL）[5]。RPL是一种基于距离矢量的先验式路由协议，由根节点发起并逐级完成整个面向目的地的有向无环图（Destination Oriented Directed Acyclic Graph，DODAG）的构建。此外，DODAG中的每个嵌入式设备均需要定期广播DODAG 信息对象消息（DODAG Information Object，DIO），该消息主要用于维护网络拓扑结构的稳定性，且该消息的发送周期间隔由溪流计时器[6]控制。

目前，学术界对RPL 已展开了大量研究工作。文献[7]在构建DODAG时将传输跳数作为路由度量，能够在一定程度上提高数据传输的实时性，但忽略了数据传输的可靠性。文献[8]在构建DODAG 时将期望传输次数作为路由度量，能够对数据传输的可靠性有一定提升，却忽略了数据传输的实时性。尤其是在高负载场景下，依据文献[7]和[8]中的路由度量所构建的DODAG均无法较好地实现网络负载均衡，将会对网络各方面的性能造成严重的影响。

为了减少在构建DODAG 时仅考虑节点一跳范围内的期望传输次数所产生的能量瓶颈节点的数量，文献[9]在构建DODAG 的过程中考虑了当前节点至根节点整条传输路径上的期望传输次数，在一定程度上能够减少能量瓶颈节点产生的数量，但效果不是很显著。文献[10]在构建DODAG 的过程中，综合考虑了当前节点至根节点整条路径上的期望传输次数和节点转发数据包的概率，即根据当前节点至根节点整条路径的数据传输代价进行最优父节点的选择。此种方式虽然能够在整体上降低数据的传输代价，却未考虑负载不均衡对网络性能所产生的负面影响。文献[11]在单路径RPL协议的基础上，提出了一种多路径RPL协议。该协议为了降低网络中能量瓶颈节点的能耗速率，节点在传输数据时根据每条路径中能量瓶颈节点的期望寿命进行数据流量的分配，并实现数据的分流传输。该协议能够在一定程度对网络整体寿命进行延长，但忽略了数据传输的可靠性。文献[12]在构建DODAG的过程中综合考虑了节点的期望传输次数和节点剩余能量，在保证数据传输可靠性的前提下，能够避免剩余能量不足的节点被选作为最优父节点。

当检测到节点发生网络拥塞时，文献[13-14]均通过周期性广播的DIO 控制消息将网络拥塞状态通告给网络中的其他节点，并进一步对当前网络拥塞进行处理。然而，当网络拓扑结构相对稳定时，DIO 控制消息的发送周期间隔相对较大，故通过周期性广播的DIO控制消息无法快速地将节点的网络拥塞状态通告给网络中的其他节点，从而影响当前网络拥塞的处理。文献[15]针对文献[13-14]中存在的问题，通过对溪流计时器的重置便可快速的将节点当前的网络拥塞状态通告给网络中的其他节点。然而，多次的将溪流计时器重置将会增加大量不必要的控制开销，且对数据的传输也会产生一定的影响。

2 网络模型和问题描述

2.1 网络模型

如图1 所示为HSLB-RPL 协议的网络拓扑模型图。其中，sink 节点也被称之为根节点，主要用于对下游节点向上游节点传输的数据流量进行汇聚；R1～R8为中继节点，主要用于转发所有叶子节点所产生的数据流量；S1～S7为叶子节点，主要用于产生数据流量，并向上游节点传输所产生的数据流量。

图1 HSLB-RPL协议网络模型

关于HSLB-RPL协议的网络模型有如下假设：

（1）网络中所有节点的物理构造、属性和性质均相同，其中根节点除外。

（2）为了尽可能保证网络的稳定性，网络中所有节点均工作于静态模式下。

（3）虽然节点的存储空间受限，但网络中每个节点均有足够的队列空间对路由表项进行缓存。

（4）网络中每个节点既可作为消息的发布者，也可作为消息的接收者。

2.2 问题描述

通过深入研究发现，在高负载场景下已有RPL协议存在以下几个问题：

（1）在DODAG 的构建过程中，节点在选择最优父节点时通常仅考虑与其备选父节点之间的期望传输次数，而未考虑其备选父节点与其备选父节点的上一跳节点之间的期望传输次数，使得拥有期望传输次数较大的父节点的节点被其邻居节点选作为最优父节点的概率增大，从而导致节点所选择的最优父节点并非最优。

（2）当检测到网络中某些节点的负载较重时，并未对此类节点的DIO 控制消息的广播周期间隔进行一定调整，从而导致此类节点的负载极有可能持续加重，且加快了此类节点的能耗速率，并对数据的传输造成了一定的影响。

（3）在数据传输过程中，当检测到网络中节点出现网络拥塞时，利用周期性广播的DIO控制消息无法及时的将当前网络拥塞节点的网络拥塞状态通告给其邻居节点。此外，重置溪流计时器虽然能够尽快的将当前网络拥塞节点的网络拥塞状态通告给其邻居节点，但会增加大量不必要的控制开销，且对数据的传输也会造成一定的影响。

为了解决上述问题，本文提出了一种高负载场景下基于负载均衡的LLN 路由协议（HSLB-RPL）。该协议包含3 种改进策略：（1）最优父节点选择策略。为了避免拥有期望传输次数较大的父节点的备选父节点被其邻居节点选作为最优父节点，综合考虑当前备选节点和其父节点的期望传输次数。（2）溪流计时器调整策略。当检测到节点负载较重时，为了降低其被邻居节点选作为最优父节点的概率，对其DIO控制消息的发送时间间隔进行一定调整。（3）网络拥塞状态通告策略。当检测到节点发生网络拥塞时，设计一种网络拥塞通告消息（NCN），及时将当前网络拥塞状态通告给其邻居节点。

3 HSLB-RPL协议

3.1 最优父节点选择策略

在DODAG 构建过程中，节点在选择最优父节点时，通常会依据不同的路由度量对最优父节点进行确定，譬如传输跳数、节点剩余能量、期望传输次数和节点缓存占用率等。其中，传输跳数能够大致反映数据传输的实时性；期望传输次数能够大致反映数据传输的可靠性。为了兼顾数据传输的可靠性和实时性，本文将结合传输跳数和期望传输次数两种路由度量。

此外，最优父节点选择策略的核心之处在于，节点在选择最优父节点时，不仅需要考虑与当前一跳范围内的备选父节点之间的期望传输次数，而且还需要考虑其备选父节点与其备选父节点上一跳节点之间的期望传输次数，降低期望传输次数较高的备选父节点被选作为最优父节点的概率，从而达到均衡网络负载的目的。以节点k 为例，其当前拥有两个备选父节点m 和n ，那么，节点k 在选择最优父节点时的具体实施步骤如下：

步骤1 节点k 的备选父节点m 和n 分别计算各自的期望传输次数。期望传输次数为节点间无线链路质量的倒数，表示节点成功传输一个数据包到达其父节点需要传输的平均次数，其计算如公式（1）所示：

步骤2 节点m 和n 分别将各自的期望传输次数与各自的传输跳数进行汇聚处理[15]，并通过周期性广播的DIO控制消息中的RANK字段携带汇聚处理后的结果，并将汇聚后的结果通告给节点k。期望传输次数与传输跳数汇聚处理如公式（3）所示：

步骤3 节点k 接收到节点m 和n 广播的DIO控制消息后，分别解析出节点m 和n 的传输跳数和期望传输次数。期望传输次数与传输跳数解析处理如公式（3）和公式（4）所示：

步骤4 节点k 解析出节点m 和n 的期望传输次数后，判断是否需要对与节点m 和n 之间的期望传输次数进行调整，其调整如公式（5）所示：

步骤5 节点k 分别计算与节点m 和n 之间的路由度量值，并选择路由度量值较小的节点作为最优父节点。路由度量值的计算如公式（6）所示：

3.2 溪流计时器调整策略

在RPL协议中，DIO控制消息的发送间隔由溪流计时器控制，可通过调整溪流计时器实现对DIO控制消息进行周期性的发送。当检测到网络出现不一致（网络结构发生较大变化）时，溪流计时器通常会被重置，从而使得节点更快的适应网络的变化；而当网络拓扑结构较为稳定时，DIO 控制消息的发送时间间隔将会逐渐增大，从而避免不必要的控制开销。因此，为了降低负载较重节点被其邻居节点选作为最优父节点的概率，对溪流计时器发送DIO控制消息的策略进行一定改进，即根据节点的负载状态适当延长DIO 控制消息的发送间隔。溪流计时器调整策略实施具体流程，如图2所示。

图2 溪流计时器调整策略

溪流计时器中用到的主要参数如下：

（1）Imin：发送DIO控制消息的最小时间间隔长度。

（2）Imax：发送DIO控制消息的最大时间间隔长度。

（3）k：冗余常量。

（4）I ：当前DIO控制消息发送的时间间隔长度。

（5）t：时间值，介于[I/2,I]之间。

（6）c：冗余计数器。

那么，溪流计时器调整策略的具体实施步骤如下：

步骤1 网络初始化时，将I 设置为介于[Imin,Imax]之间的任意一个值，并开始第一个时隙。

步骤2 将冗余计数器c 的值初始化为0，t 设置为介于[I/2,I]之间的任意一个值，该时隙终止于I 处。

步骤3 Trickle定时器每接收到一个“一致性”传输，则将冗余计数器c 的值自增1。

步骤4 在时刻t 时，Trickle定时器检查冗余计数器c 的值是否小于冗余常量k。如果c ＜k，再判断当前节点的队列利用率是否超过预设的阈值，所预设的阈值大小为0.6。如果当前节点的队列利用率超过预设的阈值，Trickle 定时器将会延长DIO 控制消息的发送间隔，则将其发送间隔增大1 倍；反之，则当前节点可以向其邻居节点广播DIO 控制消息。如果c ＞k ，则当前节点被禁止向其邻居节点广播DIO控制消息。

步骤5 当时隙I 结束后，将I 的值增大到原来的两倍，并重复步骤2。如果加倍后的I 大于Imax，则将I 的取值设置为Imax。

步骤6 一旦接收到“不一致”传输时，Trickle定时器立刻被重置，即将c 的值重新归位于0，并将时间间隔I设置为Imin并重复步骤3，直至网络运行时间结束。

3.3 网络拥塞状态通告策略

通常，当检测到网络中的节点处于网络拥塞状态时，需要网络拥塞节点将当前的网络拥塞状态通告给其子节点，以便其子节点对当前的网络拥塞进行一定处理，譬如对当前数据的传输路径进行更换或是调整当前数据包的传输速率。在RPL协议中，通用方式是利用周期性广播的DIO控制消息携带节点当前网络拥塞状态，并将节点当前网络拥塞状态通告给其子节点。然而，此种方式并不能及时的将节点当前网络拥塞状态通告给其子节点和邻居节点；此外，通过重置溪流计时器虽然能够快速地对节点当前网络拥塞状态进行通告，但是，此操作会导致DIO控制消息的发送间隔变小，从而增加了大量不必要的控制开销，且会对数据的传输造成一定的影响。

为了尽量减少不必要的控制开销，并且能够及时地将节点当前网络拥塞状态通告给其子节点和邻居节点，设计了一种新的网络拥塞通告控制消息（NCN）。NCN控制消息的帧格式与DIO控制消息的帧格式区别不大，除了消息的类型不同之外，在NCN 控制消息中新增了网络拥塞状态（NC）字段。为了避免增加NCN 控制消息的大小，利用其保留字段中的1 bit 设置为NC 字段。当该字段的值为1 时，表明当前节点处于网络拥塞状态；反之，当前节点处于正常状态。因此，当节点检测其当前处于网络拥塞状态时，无需对溪流计时器进行重置，仅需向其子节点组播NCN 控制消息便可及时地实现网络拥塞状态通告的目的。

4 性能评估

为了验证HSLB-RPL协议的性能，本文采用Contiki 2.7操作系统中的Cooja 仿真器对文献[8]、文献[10]所提协议以及本文所提协议进行模拟仿真，并对它们以下三种性能指标分别进行对比和分析。

（1）网络平均寿命：以网络中最先死亡的节点的生存时间作为网络平均寿命，其中死亡节点是指当前剩余能量仅为初始能量的1%的节点。

（2）根节点平均吞吐量：根节点平均吞吐量表示为在单位时间内网络中成功传输的数据包的数量，是衡量LLN网络性能的一项重要指标。

（3）归一化控制开销：归一化控制开销是指在网络运行时间内，网络中所有节点传输的控制消息比特数与网络中所有节点传输的控制消息比特数和根节点接收的数据包比特数的比值。

4.1 仿真环境

在200 m×200 m 的仿真区域构建节点数为21 且节点随机分布的LLN 网络，其中根节点的数量为1，普通节点的数量为20。此外，根节点的初始能量不受限制，而普通节点的初始能量将会受到一定限制。本文所提协议与其他两种对比协议采用相同的网络模型，且为了网络模型的稳定性，其中所有节点均工作于静态模式。模拟仿真过程中用到的主要仿真参数如表1所示。

表1 仿真参数设置

4.2 性能分析

4.2.1 网络平均寿命

如图3表明，随着节点数据包传输速率增加，HSLBRPL 协议的网络平均寿命均比文献[8]和文献[10]协议高，且至少提升了23.57%。分析其原因主要体现在以下三点：（1）HSLB-RPL 协议中，在构建DODAG 时，综合考虑了当前节点与其备选父节点之间的期望传输次数以及其备选父节点与其备选父节点上一跳节点之间的期望传输次数，能够避免期望传输次数较大的备选父节点被选作为最优父节点，从而降低了节点因数据包重传所耗费的能量。（2）在数据传输过程中，当检测到节点负载较重时，对其DIO控制消息的发送时间间隔进行调整，能够降低此类重负载节点被其邻居节点选作为最优父节点的概率，从而避免了此类重负载节点的能耗速率持续增加。（3）当节点发生网络拥塞时，设计了一种网络拥塞通告消息（NCN），能够避免重置溪流计时器所产生大量不必要控制开销，同时还能够将节点当前网络拥塞状态及时地通告给其子节点和邻居节点，从而加快了当前网络拥塞的缓解，降低了网络拥塞节点的能耗。

图3 网络平均寿命比较

4.2.2 根节点平均吞吐量

从图4 中发现，随着节点数据包传输速率的增加，HSLB-RPL 协议的根节点平均吞吐量均比文献[8]和文献[10]协议高，且至少提升了14.52%。通过分析发现其主要原因在于：HSLB-RPL 协议中，在构建DODAG 时，综合考虑了当前节点与其备选父节点之间的期望传输次数以及其备选父节点与其备选父节点上一跳节点之间的期望传输次数，能够避免期望传输次数较大的备选父节点被选作为最优父节点，从而有效地降低了数据包的重传次数；当检测到网络中节点发生网络拥塞时，设计了一种网络拥塞通告消息（NCN），能够避免重置溪流计时器产生大量不必要控制消息，同时能够及时地将节点当前网络拥塞状态通告给其子节点和邻居节点，从而有效地避免了重置溪流计时器对数据传输的影响。

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

4.2.3 归一化控制开销

如图5显示，随着节点数据包传输速率的增加，HSLBRPL 协议的归一化控制开销均比文献[8]和文献[10]协议低，且至少降低了12.87%。分析其原因主要有以下两点：（1）HSLB-RPL协议中，在构建DODAG时，综合考虑了当前节点与其备选父节点之间的期望传输次数以及其备选父节点与其备选父节点上一跳节点之间的期望传输次数，能够避免期望传输次数较大的备选父节点被选作为最优父节点，从而有效地降低了数据包的重传次数。（2）HSLB-RPL协议中，当检测到网络中节点发生网络拥塞时，设计了一种网络拥塞通告消息（NCN），能够避免重置溪流计时器所产生大量不必要控制消息，同时还能够及时地将当前网络拥塞状态通告给其子节点和邻居节点，从而有效地降低了当前网络拥塞状态通告的控制开销，并减少了数据传输带宽的占用。

图4 归一化控制开销比较

5 结论

本文提出了一种高负载场景下基于负载均衡的LLN路由协议（HSLB-RPL）。HSLB-RPL协议包含三种策略：（1）最优父节点选择策略，在组网的过程中，联合节点传输跳数和期望传输次数两种路由度量；（2）溪流计时器调整策略，在数据传输过程中，对重负载节点的DIO 控制消息的发送周期进行一定调整；（3）网络拥塞状态通告策略，当检测到网络发生拥塞时，通过NCN控制消息及时地将当前网络拥塞状态进行通告。仿真结果表明，HSLB-RPL协议能够有效地改善网络各方面的性能。在今后的工作中，基于动态网络场景下的负载均衡将是研究的重点。