0 概述

随着智能电网^[1]、智能建筑^[2]、智能家居^[3]以及环境监测^[4]等领域的快速发展，无线传感器网络（WSN）^[5-7]得到研究人员的广泛关注。针对链路质量不稳定、网络节点能量及处理能力受限的低功耗有损网络（LLN），互联网任务工作组（IETF）中的低功耗网络工作组（ROLL）提出一种针对LLN的路由协议（RPL）^[8-9]。目前，ROLL工作组制定了2种路由度量，一种为当前节点距离根节点的逻辑位置，称为网络深度^[10]，另一种为期望传输次数（ETX）^[11]，待入网节点依据这2种路由度量标准选择父节点。

RPL是一种网络拓扑呈树形的路由协议，网络中的所有节点均支持多点到点通信、点到多点通信和点到点通信3种数据通信模式。文献[12]针对RPL路由协议负载不均衡导致能量失衡的问题，提出一种负载均衡的多路径机制，待入网节点通过新定义路由度量选择最优多父节点，新的路由度量综合考虑节点剩余能量^[13]、链路质量、缓存区占用率^[14]以及子节点数目等多种因素。同时，文献[12]依据期望寿命^[15]、缓存区占用率、网络深度以及子节点数目等因素定义路径权重，依据路径权重进行多路径数据传输。文献[16]提出基于多父节点的RPL路由协议，通过启发式的贪婪算法实现网络中每个节点的生存时间最大化，同时，通过数据的多路径转发实现网络负载均衡。但是，文献[12, 16]在最优父节点选择时均未考虑备选父节点的上行链路节点网络状态。

文献[17]提出一种考虑父节点及子节点网络状态的目标函数（CAOF），并设计新的基于CAOF的路由度量，称为上下文感知路由度量（CARF）。CARF综合考虑整条链路的队列利用率以及剩余能量，待入网节点依据CARF选择最优父节点，从而减缓高负载网络场景中负载不均衡问题。但是，文献[17]对于如何在控制消息中添加相关信息并未给出具体方案。文献[18]提出一种提前预测的基于多种路由度量的父节点选择机制，其中备选父节点与待入网节点均参与最优父节点选择过程。待入网节点依据多种路由度量标准选择最优备选父节点，最优备选父节点根据自身队列利用情况决定是否接受待入网节点为子节点。但是，该机制由于提前预测导致网络控制开销提升，且在进行最优父节点选择时存在路由度量较为单一的问题。文献[19]通过实验指出在当前Contiki RPL开源系统以下行流量为主的网络场景中，存在ETX路由度量更新不及时的问题，并针对该问题提出改进方案。文献[20]在文献[19]的基础上进行优化，在最优父节点选择时融合网络深度、期望传输次数和队列利用率等多种路由度量，同时通过Trickle Timer^[21]定时器进行快速重置，及时通告网络拥塞情况。但是，上述方案仅考虑网络负载均衡问题，并未解决数据传输时存在的绕路问题。

本文通过改进的最优父节点选择机制以及横向路由建立机制，对当前RPL路由协议进行优化，提出一种高效低时延的RPL跨层优化机制CL-ORPL。

1 网络拓扑构建及问题描述 1.1 网络拓扑构建流程

在LLN中构建面向目的地的有向无环图（DODAG）时，需要DODAG信息（DIO）、DAO（Destination Advertise-ment Object）以及目的地通告对象确认消息（DAO-ACK）3种控制消息。RPL路由算法构建网络拓扑的控制消息交互过程如图 1所示。根节点广播DIO消息发起组网，通信范围内的待入网节点在收到DIO消息后，若选择加入该DODAG中，则将根节点的信息添加到父节点列表中，并向根节点单播回复携带自身信息的DAO消息。根节点对每个接收到的DAO消息均单播回复DAO-ACK消息，待入网节点接收到DAO-ACK消息后完成入网。节点入网后将继续广播发送添加自身相关信息的DIO消息，重复上述过程，直至网络拓扑组建完成。

RPL路由协议的组网流程伪代码如下：

算法1  RPL路由协议组网算法

根节点or已入网节点广播DIO消息

If有一个或多个备选父节点（DIO消息的源节点）

依据路由度量选择最优父节点并单播回复DAO消息

While接收到DAO消息的节点不是根节点

向最优父节点转发DAO消息

根节点单播回复DAO-ACK消息

If接收到DAO-ACK消息

节点已入网

Else节点未入网

Else节点广播DIS请求消息

End

1.2 问题描述

当前针对RPL路由协议的研究存在以下问题：

1）路由度量不完善。当前RPL路由协议的研究中最优父节点选择机制未考虑备选父节点处的网络连接情况，易造成网络拓扑不均衡。

2）不合理的基于队列利用率的路由度量。在当前基于队列利用率的路由度量中，仅考虑备选父节点的队列利用率，若所选最优备选父节点处的整条链路中部分节点的队列利用率较高，此时节点选择该备选父节点为最优父节点将加重链路负载。

3）数据传输存在绕路问题。在数据传输时，当节点发送数据包时的目的节点不是自身时，需向最优父节点转发数据，直至到达公共源节点，由公共源节点依据路由表发送数据。如图 2所示，当节点A向节点E发送数据时，完整的数据传输路径应如图中带箭头的虚线所示，即$ \mathrm{A}\to \mathrm{C}\to \mathrm{R}\to \mathrm{C}\to \mathrm{E} $，但若此时节点E在节点A的通信范围内，就不需要经过多次转发。当网络规模较大时，RPL路由协议中的数据传输绕路问题将更加显著。

2 CL-ORPL机制

本文提出一种高效的CL-ORPL机制，其主要包括最优父节点选择机制和横向路由建立机制2个部分。

2.1 最优父节点选择

最优父节点选择机制的基本思想是综合考虑节点与父节点间的链路质量和网络深度，本文以跳数指代节点网络深度、链路队列利用率以及子节点数目等多种路由度量，从而使得在选择最优父节点时更全面地考虑多个备选父节点及其链路的网络状态，有效实现网络负载均衡。最优父节点选择机制的具体步骤如下：

步骤1  节点根据当前的负载情况计算队列利用率，避免负载较重的节点被选作最优父节点。节点队列利用率的计算公式如下：

$ {Q}_{n}=\frac{{B}_{\mathrm{o}\mathrm{c}\mathrm{c}\mathrm{u}\mathrm{p}\mathrm{a}\mathrm{n}\mathrm{c}\mathrm{y}}\left(n\right)}{{B}_{\mathrm{m}\mathrm{a}\mathrm{x}\_\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}}\left(n\right)} $

(1)

其中，$ {B}_{\mathrm{o}\mathrm{c}\mathrm{c}\mathrm{u}\mathrm{p}\mathrm{a}\mathrm{n}\mathrm{c}\mathrm{y}}\left(n\right) $指节点$ n $当前队列所占数据量，$ {B}_{\mathrm{m}\mathrm{a}\mathrm{x}\_\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}}\left(n\right) $指节点$ n $的队列空间大小。

用$ \mathrm{E}\mathrm{T}\mathrm{X}\left(n, m\right) $表示$ n $与$ m $ 2个节点间的链路质量，其计算公式如下：

$ \mathrm{E}\mathrm{T}\mathrm{X}(n, m)=\frac{{D}_{\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}(n\to m)}}{{D}_{\mathrm{s}\mathrm{u}\mathrm{c}\mathrm{c}\mathrm{e}\mathrm{s}\mathrm{s}(n\to m)}} $

(2)

其中，$ {D}_{\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}(n\to m)} $为节点$ n $发送的总数据量，$ {D}_{\mathrm{s}\mathrm{u}\mathrm{c}\mathrm{c}\mathrm{e}\mathrm{s}\mathrm{s}(n\to m)} $为节点$ m $成功接收的数据量。

步骤2  为了不增加额外的控制开销，通过DIO消息中的Rank字段携带网络深度以及链路队列利用率^[13]，如下：

$ \mathrm{R}\mathrm{a}\mathrm{n}{\mathrm{k}}_{\mathrm{Q}\mathrm{U}}\left(n\right)=\beta \left(h\left(n\right)+1\right)+\left(\beta -1\right)Q\left(n\right) $

(3)

节点在广播DIO消息前需将自身的队列利用率与最优父节点队列利用率进行对比，若自身队列利用率较高，则将自身队列利用率与网络深度进行编码；否则，将最优父节点的队列利用率与网络深度进行编码。

步骤3  节点依据接收到的DAO消息计算子节点数目，并将该信息加入待广播发送的DIO消息中。

步骤4  待入网节点在接收到来自备选父节点的DIO消息后，得到不同备选父节点的网络情况，即网络深度、期望传输次数、链路队列利用率以及子节点数目等信息。通过对改进的Rank字段解码可以得到网络深度以及链路队列利用率的信息，解码过程如式（4）、式（5）所示：

$ h\left( n \right) = \left\lfloor {\frac{{{\rm{Ran}}{{\rm{k}}_{{\rm{QU}}}}\left( n \right)}}{\beta }} \right\rfloor - 1 $

(4)

$ Q\left(n\right)=\frac{\mathrm{m}\mathrm{o}\mathrm{d}\left(\mathrm{R}\mathrm{a}\mathrm{n}{\mathrm{k}}_{\mathrm{Q}\mathrm{U}}\left(n\right), \beta \right)}{\beta -1} $

(5)

步骤5  待入网节点依据式（6）分别计算所有备选父节点的综合路由度量值，选择具有最小路由度量值的节点为最优父节点。

$ R={h}_{p}+\mathrm{E}\mathrm{T}\mathrm{X}\left(n, p\right)+\lambda Q\left(p\right) $

(6)

其中，$ {h}_{p} $为备选父节点$ p $的网络深度，$ \mathrm{E}\mathrm{T}\mathrm{X}(n, p) $为待入网节点$ n $与备选父节点$ p $之间的无线链路质量，$ \lambda $为备选父节点的已连接子节点数目，$ Q\left(p\right) $为链路队列利用率。

2.2 横向路由建立

横向路由建立策略包括携带上一跳节点信息的DAO-ACK消息机制以及跨层旁听DAO-ACK消息机制2个方面，其能够有效缩短数据传输路径，降低数据传输的平均端到端时延。

2.2.1 携带上一跳节点信息的DAO-ACK消息机制

携带上一跳节点信息的DAO-ACK消息机制的基本思路为：用DAO-ACK消息的源地址字段携带上一跳节点地址，节点将DAO-ACK消息的源地址字段内容，从原来保持不变的根节点网络地址调整为当前节点的上一跳节点网络地址。图 3所示为改进的携带上一跳节点信息的DAO-ACK消息具体帧格式。

携带上一跳节点信息的DAO-ACK消息机制的具体操作步骤如下：

步骤1  节点的MAC层在收到DAO-ACK帧后，无论自己是否为目的地，均将帧中的内容（即DAO-ACK消息）取出上传至网络层，并且将帧头的源MAC地址也取出上传至网络层。

步骤2  节点的网络层在接收到来自MAC层传输的源MAC地址后，通过查询所建立的“网络地址-MAC地址”映射表，获取源MAC地址对应的网络地址，即上一跳节点地址，并将该地址放入接收到的DAO-ACK消息的“Previous Hop Address”字段，即原“Source Address”字段。

步骤3  用DAO-ACK消息的目的地址查询路由表获取通往目的地的下一跳节点网络地址。接着，通过查询“网络地址-MAC地址”映射表，获取下一跳节点的MAC地址。最后，将DAO-ACK消息和下一跳节点的MAC地址下传至MAC层。

2.2.2 跨层旁听DAO-ACK消息机制

跨层旁听DAO-ACK消息机制的基本思路为：当网络中其他节点的MAC层接收到DAO-ACK帧时，均将该DAO-ACK帧的内容取出并上传至网络层，网络层读取相关内容，建立其到邻居节点父节点的两跳路由，从而避免数据传输绕路问题。

跨层旁听DAO-ACK消息机制的操作步骤如下：

步骤1  节点依据发送到网络层的信息的帧头源MAC地址，根据“网络地址-MAC地址”映射表获取网络地址，建立邻居节点路由表，即一跳路由表。

步骤2  节点读取帧中的“Previous Hop Address”字段值，根据“网络地址-MAC地址”映射表获取网络地址，建立通过该节点和可到达节点的路由表，即两跳路由表。在图 3中，由于建立了横向路由表，CL-ORPL机制中当节点A向节点E传输数据时，数据传输路径如带箭头实线所示，即$ \mathrm{A}\to \mathrm{E} $。

2.3 CL-ORPL机制组网流程

CL-ORPL机制的组网流程如图 4所示，具体步骤如下：

1）待入网节点依据式（6）依次计算每个备选父节点的综合路由度量值。

2）待入网节点选择综合路由度量值最小的备选父节点为最优父节点，并向最优父节点单播发送DAO消息请求入网。最优父节点接收到DAO消息后更新路由表，并继续向自身的最优父节点转发，直至根节点接收DAO消息。

3）根节点依据DAO消息建立路由表并单播回复DAO-ACK消息。

4）节点在转发的过程中，不断更新DAO-ACK消息中的“Previous Hop Address”字段并继续依据自身的路由表发送DAO-ACK消息。

5）若在MAC层接收到目的地址不是自身的DAO-ACK帧，仍将帧的内容传输至网络层，并依据帧头源MAC地址以及Previous Hop Address建立一跳邻居路由以及通过邻居可到达的两跳路由。

6）待入网节点在接收到DAO-ACK消息后入网。

2.4 CL-ORPL机制理论分析

CL-ORPL机制能有效降低数据传输的平均端到端时延并提高数据传输成功率，理论分析具体如下：

1）CL-ORPL机制能有效降低数据传输的平均端到端时延。

假设数据在网络中传输的端到端时延为发送时延$ {T}_{\mathrm{s}\mathrm{e}\mathrm{n}\mathrm{d}} $、传播时延$ {T}_{\mathrm{t}\mathrm{r}\mathrm{a}} $、处理时延$ {T}_{\mathrm{p}\mathrm{r}\mathrm{o}} $以及排队时延$ {T}_{\mathrm{q}\mathrm{u}\mathrm{e}\mathrm{u}\mathrm{e}} $之和，则总时延T为：

$ T={T}_{\mathrm{s}\mathrm{e}\mathrm{n}\mathrm{d}}+{T}_{\mathrm{t}\mathrm{r}\mathrm{a}}+{T}_{\mathrm{p}\mathrm{r}\mathrm{o}}+{T}_{\mathrm{q}\mathrm{u}\mathrm{e}\mathrm{n}\mathrm{e}} $

(7)

设$ {T}_{\mathrm{Q}\mathrm{U}\mathrm{⁃}\mathrm{R}\mathrm{P}\mathrm{L}} $与$ {T}_{\mathrm{C}\mathrm{L}\mathrm{⁃}\mathrm{O}\mathrm{R}\mathrm{P}\mathrm{L}} $分别为QU-RPL与CL-ORPL的数据传输端到端时延，$ m $与$ n $分别为QU-RPL与CL-ORPL的数据平均发送次数，则有：

$ {T}_{\mathrm{Q}\mathrm{U}\mathrm{-}\mathrm{R}\mathrm{P}\mathrm{L}}=m\times T $

(8)

$ {T}_{\mathrm{C}\mathrm{L}\mathrm{-}\mathrm{O}\mathrm{R}\mathrm{P}\mathrm{L}}=n\times T $

(9)

当网络规模较大时，由于数据传输时横向路由信息的建立，解决了数据包在网络中通过上下行路径传输导致的绕路问题，则有$ {T}_{\mathrm{Q}\mathrm{U}\mathrm{-}\mathrm{R}\mathrm{P}\mathrm{L}} $远大于$ {T}_{\mathrm{C}\mathrm{L}\mathrm{-}\mathrm{O}\mathrm{R}\mathrm{P}\mathrm{L}} $，因此，CL-ORPL机制能有效降低数据传输的端到端时延。

2）CL-ORPL机制能有效提高数据传输成功率。

假设CL-ORPL机制与QU-RPL路由协议的数据传输成功率均为$ \alpha $，则CL-ORPL机制与QU-RPL路由协议的平均数据传输成功率分别为$ {n}^{\alpha } $与$ {m}^{\alpha } $，由于CL-ORPL机制通过横向路由建立机制缓解了数据传输的绕路问题，因此其数据平均发送次数小于QU-RPL路由协议，$ n <m $，则有$ {n}^{\alpha }>{m}^{\alpha } $，即CL-ORPL机制能有效提高数据传输成功率。

3 仿真验证及分析

本文采用OPNET14.5仿真软件，在相同的网络场景下对所提CL-ORPL机制、QU-RPL路由协议以及RPL路由协议的网络性能进行对比与分析。实验中的具体参数设置如表 1所示。

3.1 平均端到端时延

如图 5所示，CL-ORPL机制的数据传输平均端到端时延小于其他路由协议，主要原因为：CL-ORPL机制通过跨层旁听携带上一跳节点信息的DAO-ACK消息，建立横向路由，中间节点转发次数的减少能够有效降低平均端到端时延，此外，CL-ORPL机制在选择最优父节点时综合考虑链路队列利用率以及连接的子节点数目，从而有效降低了部分路由节点处的负载以及数据传输时的排队时延。

3.2 数据传输成功率

如图 6所示，CL-ORPL机制能够提高数据传输的成功率，主要原因在于数据传输成功率与数据的转发次数相关，CL-ORPL机制通过横向路由的建立减少了数据转发次数，同时，随着网络规模的扩大，RPL路由协议与QU-RPL路由协议的绕路问题将更加严重，因此，CL-ORPL机制提高数据传输成功率的效果更为显著。

3.3 网络生存时间

网络生存时间指出现第一个节点的能量降至节点初始能量10%时的网络运行时间。从图 7可以看出，CL-ORPL机制能够有效延长网络生存时间，主要原因在于：1）CL-ORPL机制通过最优父节点选择机制实现网络负载均衡，避免了网络拓扑不均衡导致的部分节点需转发数据量较大的问题，有效降低了部分路由节点的能耗；2）通过跨层旁听携带上一跳节点信息的DAO-ACK消息机制大幅减少了数据转发次数，进一步降低了路由节点的处理能耗。

4 结束语

针对当前RPL路由协议中存在的网络负载不均衡、数据传输绕路等问题，本文提出一种改进的CL-ORPL机制。该机制通过综合网络深度、链路队列利用率、期望传输次数以及子节点数目等多种路由度量，实现网络负载均衡，同时利用跨层旁听携带上一跳节点信息的DAO-ACK消息建立横向路由，以缓解数据传输时的绕路问题。OPNET仿真软件上的实验结果表明，CL-ORPL机制能够有效降低数据传输的平均端到端时延，提高数据传输成功率并延长网络生存时间。下一步将对RPL路由协议中的横向路由进行维护并继续优化数据传输过程。