基于负载均衡的高能效LLN路由协议

黄 欣 赵志刚

1(广西农业职业技术学院网络信息中心 广西 南宁 530007)2(广西大学计算机与电子信息学院 广西 南宁 530004)

0 引 言

低功耗有损网络LLN[1]通常是由几十、几百甚至成千上万个嵌入式网络设备所组成的网络，在智能电网[2]、工业控制[3]和物联网[4]等领域具有广阔地应用前景。在电气电子工程师协会IEEE、国际互联网工程任务组IETF以及Zigbee等标准化组织的支持下，物联网系统现已拥有多种应用于大规模部署的协议和标准。其中，IETF提出的一种基于IPv6的LLN路由协议RPL(IPv6-based Routing Protocol for LLN)[5]成为了当下的研究热点。

然而，由于LLN的网络结构呈树形且LLN中的嵌入式设备通常是由能量受限的无线传感器节点组成，从而极易因负载不均衡导致能量瓶颈节点的出现，一旦未对能量瓶颈节点及时处理，将会对网络各方面性能产生严重影响。因此，在LLN中如何有效地解决能量瓶颈节点的问题，以及最大化地均衡节点能耗具有极其重要的研究价值。

1 相关工作

目前，针对LLN的负载均衡方面已经取得了大量的研究成果。文献[6]在组网的过程中将缓存占用率作为选择最优父节点的路由度量，虽然能够提高网络吞吐量，但是由于未考虑节点的剩余能量，从而无法有效均衡节点能耗。为了避免选择重负载节点作为最优父节点，文献[7]同样参考了缓存占用率。此外，当网络拥塞出现时，通过对溪流计时器(Trickle timer)[8]重置策略的改进，使得网络拥塞节点的子节点以一定概率进行切换，但是其同样未考虑节点剩余能量以及未考虑节点因负载较重而出现能量瓶颈状态的情况。文献[9]在组网的过程中考虑了多种路由度量，其中包括节点剩余能量，但同样未考虑高负载场景下能量瓶颈节点出现的情况以及对其提出相关解决方法。文献[10]中将节点剩余能量作为构建路由的判据，能够有效减轻剩余能量不足节点的负载。但是，一旦剩余能量充足但链路质量较差的节点被选作为最优父节点时，将会使此类节点的能耗速率加快。为了弥补文献[10]中的缺陷，文献[11]在组网时结合了期望传输次数和节点剩余能量，可以有效避免剩余能量相对充足但无线链路质量相对较差的节点被选作为最优父节点。为了延长网络生存时间，文献[12]中通对节点所需传输的数据流量按比例分配进行多路径传输，旨在使网络中瓶颈节点的能耗均衡，其不足在于增添了额外控制开销且未考虑如何处理网络中出现剩余能量不足节点的情况。文献[13]提出了一种机会RPL路由算法ORPL(Opportunistic Routing Protocol for LLN)。该算法根据节点当前剩余能量和通信忙闲程度对其休眠间隔进行一定调整，但是该算法会导致剩余能量充足的节点拥有大量的子节点，从而加快了其能耗速率。文献[14]提出了一种基于期望寿命与能量消耗的RPL路由协议ELT-BE-RPL(Expected Life Time Balance Energy based Routing Protocol for LLN)，该协议将节点期望寿命作为路由度量，在选择最优父节点时采用最大最小原则，从而最小化每条路径上的剩余能量最小节点的能耗速率。

综上所述，现有研究并未对网络中的能量瓶颈节点进行考虑，也并未对此种情况进行处理。因此，为了尽量避免网络中出现的能量瓶颈节点对网络性能造成严重影响，本文提出了一种基于负载均衡的高能效RPL路由协议LBEE-RPL。

2 网络模型

如图1所示，LLN是由大量无线传感器节点所组成且呈树形结构。其中，节点共包括3种类型：根节点、能量瓶颈节点和普通节点。根节点主要功能是进行数据的汇聚，通常其能量不受限制；能量瓶颈节点的主要特征在于其剩余能量不足，即将处于能量耗尽的状态；普通节点的主要功能在于数据的收集和转发，初始能量有限且自始自终均不能补充。此外，本文研究的对象均处于静态，即节点的位置一旦被确定，将不再改变其所处的位置。

图1 LLN网络模型图

为了便于阐述，本文给出以下几个定义：

定义1能量阈值：网络中节点(除根节点外)的剩余能量与自身初始能量的比值为0.2时，此节点当前剩余能量被称为能量阈值。

定义2期望寿命阈值：网络中节点的当前期望寿命与节点初始期望寿命的比值为10%时，此节点当前期望寿命被称之为期望寿命阈值。

定义3期望寿命安全阈值：网络中节点的当前期望寿命与节点初始期望寿命的比值为30%时，此节点当前期望寿命被称之为期望寿命安全阈值。

定义4能量瓶颈节点：当节点的期望寿命第一次低于期望寿命阈值或是节点的剩余能量低于能量阈值时，此节点为能量瓶颈节点；如果节点的期望寿命并非第一次低于期望寿命阈值，则只有当此节点的剩余能量低于能量阈值时，此节点才被称之为能量瓶颈节点。

定义5死亡节点：当网络中节点的剩余能量低于节点初始化时能量的1%时，此节点被称之为死亡节点。

3 改进的路由协议

本文提出的路由协议进行了如下改进：

(1) 提出一种Trickle timer重置改进策略，即一旦当网络中的节点处于能量瓶颈状态时，通过对Trickle timer的重置策略进行改进，从而将能量瓶颈节点的能量状态尽快通告给其子节点和邻居节点。

(2) 提出一种能量瓶颈节点的子节点切换机制，即能量瓶颈节点采用集中式的方式决定其子节点的切换，旨在降低能量瓶颈节点的能耗，从而延长网络生存时间。

3.1 Trickle timer重置改进策略

在RPL标准[5]中，面向目的地的有向无循环图DODAG(Destination Oriented Directed Acyclic Graph)信息对象消息DIO(DODAG Information Object)主要用于上行路由的构建和网络拓扑的维护，其发送由Trickle timer[8]控制。而在现有DIO控制消息的发送策略中，仅当网络拓扑结构发生重大变化时Trickle timer才会被重置，否则DIO控制消息的发送周期将会成倍递增。因此，当检测到网络中节点处于能量瓶颈状态时，由于Trickle timer控制发送DIO控制消息的时间间隔较大，将会延迟节点能量瓶颈状态的通告，从而加快了能量瓶颈节点的死亡速率。

当网络中的节点第一次处于能量瓶颈状态不是因其剩余能量不足所导致时，若对能量瓶颈节点的子节点进行部分切换，能量瓶颈节点的当前期望寿命将会高于期望寿命阈值，则当前能量瓶颈节点便能够快速地解除能量瓶颈状态。但是，随着时间的推移，该节点可能再次出现期望寿命低于期望寿命阈值的情况。如果一旦上述情况发生就对Trickle timer进行重置，将会增加大量额外控制开销。因此，当检测到网络中的节点处于能量瓶颈状态时，应当判断该节点处于能量瓶颈状态是由于节点负载较重所导致还是由于节点当前剩余能量过低所导致。如果节点处于能量瓶颈状态是因为当前剩余能量过低所导致，那么Trickle timer至始至终仅需被重置一次；如果节点处于能量瓶颈状态是因为节点负载较重所导致，那么Trickle timer的重置需要考虑多种情况。首先，判断该能量瓶颈节点是否是首次出现能量瓶颈状态。如果是，则立即对Trickle timer进行重置；否则，只有当该能量瓶颈节点的剩余能量低于能量阈值时Trickle timer才被重置。Trickle timer的重置改进策略的具体实施过程如图2所示。

图2 Trickle timer重置改进流程图

Trickle timer重置改进策略的具体实施步骤如下：

步骤1当网络拓扑初始化构建开始时，每个节点用C(n)统计自身出现能量瓶颈状态的次数，并将其值初始化设置为0。

步骤2网络拓扑初始化构建结束后，每当节点检测到自身处于能量瓶颈状态时，便将统计量C(n)自增1。

步骤3节点根据自身C(n)的值判定是否第一次处于能量瓶颈状态。如果C(n)=1，则表明当前节点是第一次处于能量瓶颈状态，则进入步骤4；否则，进入步骤7。

步骤4该能量瓶颈节点立刻重置Trickle timer，及时通过广播DIO控制消息将其能量瓶颈状态通告给其子节点和邻居节点。

步骤5能量瓶颈节点的子节点接收到上述DIO控制消息后，按照下一小节中的能量瓶颈节点子节点切换机制对能量瓶颈节点子节点的数据传输路径进行更换；能量瓶颈节点的邻居节点接收到上述DIO控制消息后，记录下能量瓶颈节点的能量状态。

步骤6对能量瓶颈节点的子节点进行处理后，判断该节点的剩余能量是否小于预设的能量阈值。如果该节点的剩余能量小于预设的能量阈值，则结束；反之，则返回至步骤2。

步骤7判断该节点剩余能量是否小于预设的能量阈值。如果该节点剩余能量小于预设的能量阈值，则立刻重置Trickle timer；反之，则解除当前节点的能量瓶颈状态，并返回至步骤2。

3.2 能量瓶颈节点的子节点切换机制

为了更好地使能量瓶颈节点的子节点获知该能量瓶颈节点的能量瓶颈状态信息以及不增加额外的控制开销，利用DIO控制消息中的保留字段中的第1 bit，将其设置为节点能量瓶颈状态字段，用S表示。当该字段的值为1时，表明当前节点处于能量瓶颈状态；当该字段的值为0时，则表明当前节点处于能量充足状态。

网络中的节点通过周期性广播的DIO控制消息将自身备选父节点的剩余能量状态信息共享给父节点，利用DIO控制消息的保留字段中的第2 bit，将其设置为节点备选父节点的能量瓶颈状态字段，用B表示。当该字段的值为1时，则表明节点的备选父节点处于能量瓶颈状态；当该字段的值为0，则表明节点的备选父节点处于能量充足状态。因此，能量瓶颈节点通过接收到其子节点周期性广播的DIO控制消息便能获知它所有子节点的备选父节点的剩余能量状态信息。但是，在能量瓶颈节点的子节点切换过程中，其子节点可能同时切换到另外一个节点，发生“羊群效应”，从而增大了该节点出现能量瓶颈状态的概率，且极有可能导致网络出现震荡现象。为了避免能量瓶颈节点的子节点在切换的过程中出现“羊群效应”，因而制定了一种完善的能量瓶颈节点的子节点切换机制，其具体实施过程如下：

步骤1当检测到LLN网络中出现能量瓶颈节点时，判断该节点是否是首次出现能量瓶颈状态。如果非首次出现，则进入步骤8；反之，则进入步骤2。

步骤2判断该能量瓶颈节点出现能量瓶颈状态的原因。如果能量瓶颈节点的能量瓶颈状态不是因为节点当前剩余能量低于节点能量阈值所引起，则进入步骤5；反之，则进入步骤3。

步骤3只要该能量瓶颈节点子节点的备选父节点的剩余能量高于能量安全阈值，该能量瓶颈节点就将这类子节点添加到子节点切换列表中，并将子节点切换列表添加到DIO控制消息的选项字段中，同时将DIO控制消息中的EBS字段的值设置为1，通过广播该DIO控制消息通告给其子节点。

步骤4能量瓶颈节点的子节点接收到上述DIO控制消息后，首先检查DIO控制消息中的S字段，如果该字段的值为0，则表明子节点当前父节点处于能量充足状态，并按照常规的路由判据决定是否需要切换当前父节点；如果该字段的值为1，表明节点当前父节点处于能量瓶颈状态，于是该节点从接收到的能量瓶颈节点广播的DIO控制消息的选项字段中提取出子节点切换列表，并查看其中是否包含自身信息。如果包含其自身信息，则在内存中将当前父节点标记为能量瓶颈状态，并从其父节点列表中删除当前能量瓶颈节点的信息，同时从父节点列表中选取一个备选父节点作为新的父节点，并将原父节点的瓶颈状态信息通过DIO控制消息通告给新的父节点；反之，若不包含其自身信息，则继续与能量瓶颈节点保持连状态。

步骤5能量瓶颈节点将可切换的子节点按照节点发包率的大小由高到低排序，依次计算排除掉需切换的子节点后的能量瓶颈节点新的期望寿命，直至能量瓶颈节点新的期望寿命高于期望寿命安全阈值，达到解除能量瓶颈状态的目的为止，并将排除掉的子节点添加到子节点切换列表中。若切换掉所有可切换的子节点后，能量瓶颈节点的期望寿命依旧低于期望寿命安全阈值，那么只有切换掉满足切换条件的当前所有子节点。

步骤6能量瓶颈节点将其子节点切换列表添加到DIO控制消息的选项字段中，同时将DIO控制消息中的S字段的值设置为1，通过广播该DIO控制消息通告给其子节点。

步骤7能量瓶颈节点的子节点接收到上述DIO控制消息后，重复步骤4。

步骤8判断该节点出现能量瓶颈状态的原因。如果该节点出现能量瓶颈状态是因为节点当前期望寿命小于节点期望寿命阈值，为了避免增加额外的控制开销以及避免网络拓扑结构频繁的发生变化，因此将对其不作任何处理，直到其剩余能量低于能量阈值时，返回至步骤3；如果能量瓶颈节点出现能量瓶颈状态是因为节点当前剩余能量低于节点能量阈值所引起，则直接返回至步骤3。

在瓶颈节点的子节点切换策略执行过程中，如果已切换的子节点的当前父节点因后续出现能量瓶颈状态而再度切回到先前能量瓶颈状态节点，那么会导致先前能量瓶颈节点再度快速地出现能量瓶颈状态。因此，每个因为先前父节点处于能量瓶颈状态而切换的子节点均需记录先前父节点的能量瓶颈状态信息，并将其通过DIO控制消息共享给当前父节点。

4 仿真实验及结果分析

采用Contiki 2.7仿真软件对本文方法各方面网络性能进行模拟仿真验证，并选取ORPL[13]和ELT-BE-RPL[14]在相同仿真模拟场景下进行比较分析，主要对比分析了网络生存时间、节点死亡率和根节点平均吞吐量三个方面的性能。

4.1 仿真环境及参数设置

在500 m×500 m的仿真区域内根据节点数量不同设置6种不同的模拟仿真场景，网络规模大小分别为30、50、70、90、110和130，仿真周期为4 800 s，每个场景中节点随机分布且位置固定，除根节点外，其余所有节点的能量均受限，初始能量为10 J，且在仿真过程中不补给能量。节点的发包速率介于1 pkt/s到4 pkt/s之间，且每个数据包的大小均为1 500 B。节点的最大发射功率为50 MW，发送单位比特数据的能耗为65 nJ/bit。

4.2 仿真结果分析

图3为网络生存时间的对比。网络生存时间是指网络中首次出现死亡节点所耗费的时间。从图3中可以发现，随着网络规模的不断扩大，与ORPL和ELT-BE-RPL相比，本文方法的网络生存时间至少能够提升10.53%。其主要原因有以下两点：(1) 当检测网络中出现能量瓶颈节点时，通过对Trickle timer重置策略进行改进，能够及时将节点能量瓶颈状态通告给其子节点，从而迅速地对能量瓶颈节点的子节点进行处理；(2) 能量瓶颈节点的子节点切换机制能够使得能量瓶颈节点的负载减轻，有效地降低能量瓶颈节点的能耗速率，从而延长了能量瓶颈节点的生存时间。

图3 网络生存时间比较

图4所示为节点死亡率的对比。节点死亡率是指在网络运行时间内网络中的死亡节点数与网络中总的节点数的比值。从图4中可以发现，随着网络中节点数量的增多，本文方法的节点死亡率均低于ORPL和ELT-BE-RPL，且至少降低了18.59%。其主要原因在于当检测到LLN中出现能量瓶颈节点后，通过对Trickle timer重置策略的改进，能够及时地将能量瓶颈节点的能量瓶颈状态通知给其子节点，进而快速地对能量瓶颈节点子节点进行切换，降低了能量瓶颈节点的能耗速率，从而延长了能量瓶颈节点的生存时间，有效地减少了死亡节点的数量。

图4 节点死亡率比较

图5所示为根节点平均吞吐量的对比。根节点平均吞吐量是指根节点在单位时间内平均收到的数据流量。可以发现，3种方法的根节点平均吞吐量均随着网络规模的扩大而逐渐张增大。但是本文方法在每种场景中的根节点平均吞吐量均明显高于ORPL和ELT-BE-RPL，至少提高了8.76%。通过分析发现其主要原因在于当LLN中检测出能量瓶颈节点后，能够对能量瓶颈节点的子节点进行快速的处理，有效地延长了网络生存时间和降低了节点死亡率，从而提高了根节点的平均吞吐量。

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

5 结 语

由于LLN中现有负载均衡路由算法未对检测出的能量瓶颈节点及时进行处理，进而严重影响网络各方面性能，因此本文提出了改进的路由协议。该协议通过对Trickle timer重置策略的改进，及时将能量瓶颈节点的能量瓶颈状态通告给其子节点，并进一步快速地对能量瓶颈节点的子节点进行处理，降低了能量瓶颈节点的能耗速率，从而能够有效地延长能量瓶颈节点的生存时间。理论分析和仿真结果表明，相比较于现有路由算法，本文方法能够有效延长网络生存时间、降低节点死亡率和提升根节点平均吞吐量。在接下来的研究中，将重点对动态网络场景下的能量瓶颈节点进行研究。