多汇聚LLN中基于双向父节点选择的 高效RPL路由协议

王朝硕，朱克兰，姚玉坤，赵子军

(1.中国南方电网高压输电公司 信息通信运维中心，广东 广州 510000；2.重庆邮电大学 移动通信技术重庆市重点实验室，重庆 400065)

0 引 言

低功耗有损网络(low power and lossy network，LLN)[1,2]是无线传感器网络(wireless sensor networks，WSN)[3,4]的一类分支，目前被越来越广泛地应用于智能电网[5]、智能建筑[6]、智能家居[7]和环境监测[8]等领域，RPL路由协议(routing protocol for LLN，RPL)[9]作为专为LLN制定的路由协议也受到了关注。当前，RPL路由协议的研究热点为基于单sink的网络负载均衡[10-12]，但相关研究表明基于多sink的LLN与基于单sink的LLN相比具有较大的网络性能优势。文献[13,14]通过对比分析证明了随着sink节点数目的增加，能够有效提升网络性能。然而当前基于多sink节点的RPL路由协议中的研究中仍存在一定的问题。文献[15]提出通过多重身份节点实现数据流量在多个面向目的地的有向无循环图(destination-oriented directed acyclic graph，DODAG)之间的自适应分配，从而均衡多个DODAG的网络负载，但该协议对网络性能的提升不算明显。文献[16]提出一种基于备用sink节点的优化RPL协议，为节点定义了一种压力指数参数，当压力指数超过阈值，节点将主动发起父节点切换过程，将父节点切换到备用sink，直至检测到压力指数低于阈值。但备用节点仅在网络拥塞发生时启用，浪费了网络资源。文献[17]提出一种基于协调框架的RPL路由协议，依据数据包的投递率调整子节点的连接数目，实现了以sink为中心的多个子树间的负载均衡，但该协议不能有效避免DODAG内发生网络拥塞。

针对上述现有研究中存在的问题，本文提出一种多汇聚LLN中基于双向父节点选择的高效RPL路由协议——BPSM-ERPL(efficient RPL in LLNs based on bidirectional parent selection in multiple sinks)加以解决。

1 网络模型及问题描述

1.1 RPL路由协议

RPL路由协议组网的消息交互如图1所示。首先，sink节点广播一个DODAG信息对象消息(DODAG information object，DIO)发起组网过程；sink通信范围内的待入网节点收到DIO消息后，将sink的信息添加到自己的父节点列表，并用单播方式向sink回复一个包含自身信息的目的地通告对象消息(destination advertisement object，DAO)；sink节点对每个接收到的DAO消息均用单播方式回复一个目的地通告对象确认消息(destination advertisement object acknowledgement，DAO -ACK)；待入网节点收到DAO -ACK消息后记录相关信息，至此一个节点的入网过程完成。节点入网后用广播一个包含自身信息的DIO消息。

图2 网络拓扑

1.2 网络模型

网络模型如图2所示，图中S1与S2为sink节点，分属不同的RPL实例。为便于表述，给出如下假设和定义：

(1)网络节点均有路由功能，即节点可以收发消息，网络中的节点分为两种，普通路由节点以及边界路由节点：①普通路由节点：普通节点仅能接收到一个RPL实例的DIO广播消息，也仅能加入一个DODAG，例如节点1、节点2以及节点10；②边界路由节点：边界路由节点能够接收到多个RPL实例的DIO广播消息，故其可以加入多个DODAG，例如节点5、节点6以及节点7。

(2)主父节点指路由节点依据目标函数从备选父节点集中选择的最优父节点，次父节点指路由节点依据目标函数从备选父节点选择的次优父节点。

(3)网络中的路由节点均不具备移动性，网络中的节点除sink节点外均需要考虑路由节点处的能耗及数据处理能力。

1.3 问题描述

经过研究分析当前基于RPL路由协议的相关技术，发现仍存在以下问题：

(1)待入网节点唯一决定父节点选择：在最优父节点的选择中，待入网节点根据接收到的DIO消息从备选父节点集中选择最优父节点，并向选择的最优父节点发送一个DAO消息，接收到DAO消息的节点，不论当前的网络连接状态，都必须建立与子节点的连接。同时，向上继续转发来自子节点的DAO消息。在极端情况下，若此时最优父节点由于已连接的子节点数目较多，子节点均向最优父节点处发送大量数据，导致最优父节点需要承担的转发任务较重，然而受数据处理能力的限制，最优父节点无法处理如此高的数据流量进而造成队列占用率急剧增加，最终导致最优父节点处遇到网络拥塞，影响网络正常数据传输。RPL路由协议针对网络拥塞的问题提出切换最优父节点的策略，但该策略势必导致网络不稳定以及数据传输丢包率上升等问题。

(2)雷鸣效应：雷鸣效应指的是大量的待入网节点建立与网络性能较优的节点的连接，导致节点处连接大量子节点的现象。

如图3的雷鸣效应所示，以队列利用率为路由度量，除sink外的所有节点(节点1-11)按照图1所示的控制消息交互流程开展入网操作：如果节点能够收到父节点广播的DIO消息，则直接与sink节点交互完成入网；如果不能收到，则通过广播DODAG信息请求(DODAG information solicitation，DIS)消息的方式与已入网节点建立联系然后完成入网。节点1及节点3先入网，其队列利用率分别为0.3和0.25，并将该信息添加在DIO消息中广播。随后节点2入网，其队列利用率为0.2，同样广播添加了该信息的DIO消息；这样将导致在其通信范围内的待入网节点在对比备选父节点集中的其它节点后，均选择该节点为最优父节点。而已经入网的节点，例如节点5以及节点6，也可能切换最优父节点，最终导致节点2处连接较多的子节点，也即在节点2上产生了雷鸣效应。在雷鸣效应的作用下，节点2的能量被快速地消耗，而节点1和节点3的资源却未得到充分利用，这将导致网络不稳定。

图3 雷鸣效应

(3)多sink节点间的网络负载不均衡：以每个sink节点为中心节点，可以构建一个DODAG图。在多sink的LLN中，若某个RPL实例内由于网络负载较重，仅在该RPL实例中进行优化，并未有效利用多sink节点的网络拓扑特性，也即网络资源的分配非最优。

2 BPSM-ERPL路由协议

BPSM-ERPL路由协议包括以下3个创新机制，针对问题(1)及问题(2)，提出携带咨询信息的DAO消息机制以及双向父节点选择机制，针对问题(3)，提出一种自适应数据传输机制。下文详细介绍BPSM-ERPL路由协议包含的新机制及具体操作。

2.1 携带咨询信息的DAO消息

携带咨询信息的DAO消息机制的核心思想为，通过改进的M-DAO请求消息，告知父节点当前待入网节点的预估数据传输速率。M-DAO消息的基本对象格式如图4所示，图中字段M代表主父节点，字段C代表强制。

图4 M-DAO消息基本对象格式

与DAO消息的基本对象相比，M-DAO消息的基本对象在格式上改变不大，主要变化在Type字段和保留字段。首先，为了与当前RPL路由协议中的其它控制消息区分，新协议更改了M-DAO消息的Type字段；其次，对原DAO消息的保留字段进行了更改，重新划分为字段M、字段C以及Data字段。字段M占1字节，主要用于通告父节点当前是否为主父节点。若接收M-DAO消息的节点为主父节点，则字段M设1。若接收M-DAO消息的节点为次父节点，则字段M设0。字段C占1字节，主要用于通告父节点当前的入网请求是否是强制请求。若当前待入网节点的备选父节点集中仅有一个节点，则待入网节点发送字段C置1的强制请求。若当前待入网节点的备选父节点集有多个节点，则待入网节点发送字段C置0的非强制请求。Data字段用于携带待入网节点请求的数据传输速率，以实现提前通告父节点的目的。

2.2 双向父节点选择机制

双向父节点选择机制的核心思想是父节点在接收到M-DAO消息后，根据M-DAO消息携带的信息，判断是否建立与待入网节点的连接，详细操作步骤如下。

步骤1 待入网节点发送M-DAO消息，最优父节点接收后，首先读取字段C以及Data字段。首先最优父节点查看字段C，若字段C的值设为1，表明当前的入网请求为强制性请求，最优父节点依据M-DAO消息携带的信息更新路由表并向sink转发M-DAO消息，否则直接执行步骤2。

步骤2 若字段C的值设为0，表明当前的入网请求为非强制性请求。此时，最优父节点将依据Data字段携带的信息判断是否能够在不影响当前的网络服务质量的前提下，建立与待入网节点的连接，判据条件如式(1)所示

(1)

式中：假设待入网节点为节点N，最优父节点为节点P，则dN为待入网节点通过M-DAO消息的Data字段携带的当前请求的一个时间周期内需传输的平均数据包数目，dP为最优父节点的一个时间周期需传输的平均数据包数目，di为最优父节点P当前已连接的子节点请求的一个时间周期内需传输的平均数据包的数目。q表示最优父节点的队列长度，do为最优父节点P的一个时间周期内传输的平均数据包数目，转至步骤3。

步骤3 若待入网节点请求的一个时间周期内需传输的数据包的平均数目满足判据条件，则最优父节点建立与待入网节点的连接。更新路由表，并向上转发M-DAO消息，否则转至步骤4。

步骤4 若待入网节点请求的一个时间周期内需传输的平均数据包数目不满足判据条件，则最优父节点向待入网节点发送请求拒接消息，待入网节点继续从备选父节点集中选择其它节点为最优父节点。转至步骤5。

步骤5 待入网节点在接收到来自sink节点的DAO -ACK消息后入网。已入网的节点将广播添加了自身信息的DAO -ACK 消息。

2.3 自适应数据传输机制

在拥有多个RPL实例的RPL路由协议中，位于实例边界的路由节点可以获取不同RPL实例的DIO消息，加入多个RPL实例。数据传输自适应机制的核心思想是：边界路由节点通过在DIO消息中获取到的最优父节点的链路队列利用率和网络深度等信息，根据属于不同RPL实例的最优父节点的网络状态进行自适应的数据传输，以均衡数据流量在多个RPL实例的分配。自适应数据传输机制的具体操作步骤如下：

步骤1 重新定义DIO消息中的Rank字段，将链路队列利用率Q与网络深度h进行编码[10]，(下文式(2)～式(4)中参数的定义请参见文献[10])。如式(2)所示

RankQU(n)=β(h(n)+1)+(β-1)Q(n)

(2)

边界路由节点对接收到的DIO消息中的Rank字段解码，如式(3)、式(4)所示，从而获取网络深度以及链路队列利用率等信息

(3)

(4)

步骤2 边界路由节点对属于不同RPL实例的DIO消息进行划分，分别计算不同RPL实例的备选父节点的路由度量，并依据式(5)选出最优的属于不同的RPL实例的最优备选父节点。式(5)中hp表示备选父节点p的网络深度，ETX(N,p) 表示待入网节点N与备选父节点p之间的无线链路的质量，λ为备选父节点连接的子节点数量，Qp表示MAC子层的链路队列利用率

R=hp+ETX(N,p)+λQp

(5)

如图2所示，边界路由节点4的备选父节点集中属于实例1的备选父节点为节点1及节点2；属于实例2的备选父节点集为节点9及节点10，转至步骤3。

步骤3 边界路由节点从备选父节点集中选择最优父节点集后，继续查看最优父节点集合的链路队列利用率，检查最优父节点集的关联链路中是否有重负载节点。若最优父节点集的关联链路中没有重负载节点，则边界路由节点根据网络深度分配数据传输速率[15]，并分别向属于不同RPL实例的最优父节点发送Pt字段置1以及字段C置0的M-DAO请求消息，否则直接执行步骤4。

步骤4 若当前最优父节点集的关联链路连接有重负载节点，则边界路由节点向链路未连接重负载节点的最优父节点发送字段M值为1和字段C值为0的M-DAO消息，并向链路连接有重负载节点的最优父节点发送字段M值为0和字段C值为0的M-DAO消息，否则直接执行步骤5。

步骤5 若当前最优父节点集的关联链路均连接有重负载节点，则边界路由节点从备选父节点集中重新选择最优父节点集，然后重复步骤2至步骤4的操作。

2.4 BPSM-ERPL路由协议

BPSM-ERPL路由协议的主要操作[18]如下：

步骤1 待入网节点根据收到的DIO消息的内容，判断自己是否是边界路由节点；若不是，则根据目标函数确定最优路径，选择最优父节点，然后向最优父节点发送包含自身信息的M-DAO消息。

步骤2 如果待入网节点是边界路由节点，则由待入网节点选择最优父节点集。在确定最优父节点集后，检查最优父节点集的关联链路是否连接有重负载节点。若链路未连接重负载节点，则边界路由节点根据网络深度分配数据流量，边界路由节点向最优父节点分别发送包含自己信息的M-DAO消息，否则直接执行步骤3。

步骤3 如果边界路由节点的最优父节点集的关联链路连接有重负载节点，则边界路由节点向链路未连接重负载节点的最优父节点发送字段M值为1的M-DAO消息；并且向链路连接有重负载节点的最优父节点发送字段M值为0的M-DAO消息，否则直接执行步骤4。

步骤4 如果边界路由节点的最优父节点集的关联链路均连接有重负载节点，边界路由节点则重新在备选父节点集中选择最优父节点，然后执行步骤5。

步骤5 最优父节点收到M-DAO消息后，提取该消息携带的信息进行判断；若字段C的值为1，最优父节点须建立与待入网节点的连接，并向sink转发M-DAO消息；否则，最优父节点根据判据条件式(1)进行判断；若满足式(1)，最优父节点建立与待入网节点的连接，并向sink转发M-DAO消息，否则最优节点向待入网节点发送请求拒绝消息。

步骤6 待入网节点收到来自sink的DAO-ACK消息后便完成了入网。已入网节点继续广播添加了自身信息的DIO消息。

BPSM-ERPL路由协议算法流程如图5所示。

图5 BPSM-ERPL路由协议算法流程

3 仿真验证及分析

本文采用网络仿真软件OPNET Modeler 14.5对CF-RPL路由协议、TAAM-RPL路由协议和提出的BPSM-ERPL路由协议进行仿真，在相同的网络场景下对数据传输成功率、网络吞吐量、网络生存时间性能指标进行定量对比及分析[19]。

3.1 仿真统计量

本文选取了吞吐量、成功率以及网络生存时间作为验证新协议性能的仿真统计量。本文所提新协议在原理上能够更有效、合理地利用网络带宽和能量资源，因此对上述3个统计指标有提升作用。

(1)数据传输成功率

数据传输成功率等于目的节点成功收到的数据包的总比特数与源节点发送的总数据比特数的比值，如式(6)所示

(6)

式中：S为数据传输成功率，Dr为被目的节点成功收到的数据包的总比特数，Dt为源节点发送的数据包的总比特数。

(2)网络吞吐量

网络吞吐量表示在有数据包发送的仿真时间内，目的节点成功收到的数据包的总比特数，如式(7)所示

(7)

式中：Ts为有数据发送的仿真时间，T表示网络吞吐量。

3.2 仿真参数设置

网络场景设置为800 m×800 m的正方形区域，网络节点数依次设置为40、80、120、160、200以及240。网络中设置两个sink节点，网络中的路由节点位置均固定。节点发射功率设为30 mW，每个路由节点的通信范围内均设有路由节点，数据分组长度为128 bits，数据发送速率为每秒一个，网络仿真时间为4000 s，主要仿真参数设置见表1。

表1 主要仿真参数

3.3 数据传输成功率

如图6所示，在不同的网络规模下，虽然3种路由协议的数据传输成功率均呈下降趋势，但BPSM-ERPL路由协议的数据传输成功率高于CF-RPL路由协议和TAAM-ERPL路由协议。主要原因是BPSM-ERPL路由协议首先通过双向父节点选择机制，充分考虑了父节点的网络状况和数据处理能力，避免了网络拥塞导致的数据丢包，能够更有效、合理地利用网络带宽资源；同时通过自适应数据传输机制，在充分考虑最优父节点链路负载状态的前提下，实现了数据流量在多个DODAG间的均衡分配；有效均衡了网络负载，降低了网络拥塞发生概率，从而进一步提升了数据传输成功率。

图6 数据传输成功率

3.4 网络吞吐量

如图7所示，在不同的网络规模下，BPSM-ERPL路由协议的网络吞吐量均高于CF-RPL路由协议以及TAAM-ERPL路由协议，并且随着网络规模的扩大，BPSM-ERPL路由协议的性能优势更加显著。分析其原因为，网络吞吐量与数据发送成功率呈正相关，与数据传输的平均端到端时延呈负相关。通过图6可知，BPSM-ERPL路由协议提高了数据发送成功率。其次，由于BPSM-ERPL路由协议能够有效实现网络负载均衡，降低网络拥塞发生的概率，从而能更加合理、有效地利用网络的带宽资源。从而其能够有效降低数据传输的排队时延以及由于丢包导致的数据重传。也即，可以降低数据传输的平均端到端时延。因此，BPSM-ERPL路由协议能够提高网络吞吐量。

图7 网络吞吐量

3.5 网络生存时间

网络生存时间的定义请参见文献[15]。图8显示BPSM-ERPL路由协议能够有效地延长网络生存时间。据分析主要原因是BPSM-ERPL协议通过采用DAO消息携带咨询信息和双向父节点选择的新机制，有效避免了雷鸣效应，而雷鸣效应的直接后果就是发生雷鸣效应的节点处的网络资源以及节点能量等被快速消耗；其次，通过采用自适应数据传输机制，避免了负载较重的节点被选为最优父节点；并且借助边界路由节点实现了数据流量在多个RPL实例间的合理分配，调动了整个网络的资源，使网络资源的利用更加合理，重负载节点的能量能够得到保护。因此，BPSM-ERPL路由协议能够有效延长网络生存时间。

图8 网络生存时间

4 结束语

针对当前RPL相关路由协议存在的雷鸣效应、待入网节点唯一决定父节点选择以及数据在多个RPL实例间分配不合理问题，提出BPSM-ERPL路由协议。BPSM-ERPL路由协议首先优化了DAO消息，通过M-DAO消息携带咨询信息；其次采用了双向父节点选择机制，使父节点根据网络状态能够选择建立或不建立与待入网节点的连接，从而有效地避免了雷鸣效应，提高了网络稳定性。最后，BPSM-ERPL路由协议采用了自适应数据传输机制，通过边界路由节点实现了数据信息在RPL实例间的分配，有效实现了网络负载均衡。理论分析及仿真实验结果表明，BPSM-ERPL路由协议能够有效提升网络性能。在未来的工作中，我们将继续就如何实现多个DODAG间的通信进行研究。