一种高效低时延的RPL 跨层优化机制

姚玉坤，朱克兰，杨 迪，赵子军

（1.重庆邮电大学通信与信息工程学院，重庆 400065；2.重庆邮电大学移动通信技术重点实验室，重庆 400065）

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

图1 节点入网的消息交互过程Fig.1 Message interaction process of the nodes entering the network

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

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

1.2 问题描述

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

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

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

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

图2 数据转发过程示意图Fig.2 Schematic diagram of data forwarding process

2 CL-ORPL 机制

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

2.1 最优父节点选择

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

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

其中，Boccupancy(n)指节点n当前队列所占数据量，Bmax_size(n)指节点n的队列空间大小。

用ETX(n，m) 表示n与m2 个节点间的链路质量，其计算公式如下：

其中，Dtotal(n→m)为节点n发送的总数据量，Dsuccess(n→m)为节点m成功接收的数据量。

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

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

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

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

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

其中，hp为备选父节点p的网络深度，ETX(n，p)为待入网节点n与备选父节点p之间的无线链路质量，λ为备选父节点的已连接子节点数目，Q()p为链路队列利用率。

2.2 横向路由建立

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

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

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

图3 携带上一跳节点信息的DAO-ACK 消息Fig.3 DAO-ACK message with information of last hop node

携带上一跳节点信息的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 传输数据时，数据传输路径如带箭头实线所示，即A →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 消息后入网。

图4 CL-ORPL 机制组网流程Fig.4 The networking procedure of CL-ORPL mechanism

2.4 CL-ORPL 机制理论分析

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

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

假设数据在网络中传输的端到端时延为发送时延Tsend、传播时延Ttra、处理时延Tpro以及排队时延Tqueue之和，则总时延T为：

设TQU⁃RPL与TCL⁃ORPL分别为QU-RPL 与CL-ORPL的数据传输端到端时延，m与n分别为QU-RPL 与CL-ORPL 的数据平均发送次数，则有：

当网络规模较大时，由于数据传输时横向路由信息的建立，解决了数据包在网络中通过上下行路径传输导致的绕路问题，则有TQU-RPL远大于TCL-ORPL，因此，CL-ORPL 机制能有效降低数据传输的端到端时延。

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

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

3 仿真验证及分析

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

表1 仿真参数设置Table 1 Simulation parameters setting

3.1 平均端到端时延

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

图5 平均端到端时延变化情况Fig.5 Variation of average end-to-end delay

3.2 数据传输成功率

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

图6 数据传输成功率变化情况Fig.6 Variation of success rate of data transmission

3.3 网络生存时间

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

图7 网络生存时间变化情况Fig.7 Variation of network lifetime

4 结束语

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