低功耗有损网络路由协议的组网优化算法研究

程克非 陈慈飞 李 栋 吴佳琪

(重庆邮电大学通信与信息工程学院 重庆 400065)

0 引 言

近年来，随着物联网技术[1]的快速发展，低功耗有损网络可以应用在多种场景，包括工业监控[2]、智能电网自动计量基础设施(Advanced metering infrastructure,AMI)[3]和无线传感器网络(Wireless Sensor Network,WSN)[4]，研究低功耗有损网络(Low power and lossy networks,LLN)的路由协议具有重要意义。浮空器上设备自组网是由具有数据采集、处理、传输能力的无线设备组成，其中包括飞控设备、红外成像设备等，其主要特点是低动态拓扑、多数据流量形式、高可靠性、高稳定性等。浮空器上设备自组网受限于有限的资源，属于低功耗有损网络的一种应用场景，但是网络规模要小于普通无线传感器网络。

现在，大部分的低功耗有损网络的部署都采用基于开放式和标准化的IPv4/IPv6体系结构与互联网连接，这种方法使得LLN更具有互操作性、灵活性和多功能性。低功耗有损网络中的无线节点资源有限，并且网络中节点之间的链路质量不能保持长期稳定，这种情况让路由协议的研究带来了很多挑战。国际互联网工程任务组(The Internet Engineering Task Force，IETF)的低功耗有损网络路由(Routing over Low Power and Lossy Networks,ROLL)小组在对比了OLSR[5]、AODV[6]等路由协议后，于2012年提出了RPL路由协议[7]，制定了标准RFC6550，以此引入基于IPv6的标准化协议。

目前，针对RPL路由协议的拥塞控制[8-9]和构建过程[10]等方面已经进行了相关研究。针对近根节点需要转发大量的DAO消息导致网络发生拥塞，文献[11]提出一种改进的DelayDAO定时器机制，以控制DAO的转发速率，避免拥塞，但是并未减少DAO消息的数量，同时增加了路由建立过程的收敛时间。文献[12]提出了一种快速的DODAG形成机制，通过根据接收到的DIS(DODAG Information Solicitation)消息数量缩短DIO(DODAG Information Object)消息的传输间隔，这样虽然加快了路由构建的速度，但是每个节点增加了至少一次DIO消息的发送，产生了控制开销。文献[13]通过将上下行路由构建过程完全分开，先通过逐跳发送DIO消息，以此建立上行路由，再由叶子节点向根节点逐跳回复DAO消息，以此建立下行路由。这种方式在一定程度上降低了开销，但是由于低功耗有损网络中链路状态不稳定，控制消息的丢失，就会使得整条路径上的路由构建失败，这导致收敛时间和控制开销的增加。

对现有RPL路由协议分析，低功耗有损网络中存储模式的路由构建过程存在着以下的缺点：

1) 在路由构建的时候，网络是从根节点周围逐层进行路由构建，节点最后收到DAO-ACK(Destination Advertisement Object-Acknowledge)消息后，才完成路由构建过程，然后向下一跳广播DIO消息，这将导致整个网络的路由构建时间过长。当节点收到DIO消息后，都需要立即向最优父节点发送DAO消息，DIO消息是单跳内广播，而DAO消息经过多跳传输到根节点，这就导致网络中，尤其是在靠近根节点的地方，DAO消息的数量过多，造成网络拥塞。

2) 在路由构建时，当节点收到DIO消息后，需要立即回复一个DAO消息来加入DODAG，但是每个节点可能会有多个父节点，即短时间内会有多个节点发送DIO消息，节点按顺序接收DIO消息，当节点选择第一个DIO消息的发送者为最优父节点后，若再次收到链路状况更好的DIO消息，则需要进行切换，导致网络结构的不稳定，产生不必要的控制开销。

本文将针对构建过程中控制开销过大及网络收敛时间过长的问题，从DODAG的构建过程出发，综合考虑DAO定时器以及消息聚合等机制，对RPL路由协议进行改进，通过实验对改进协议进行验证分析。

1 RPL路由协议原理

RPL路由协议是距离矢量路由协议，可以工作在不同的MAC层之上[14]。RPL基于有向无环图(Destination Oriented Directed Acyclic Graph,DODAG)的拓扑概念，这是一种典型的树状路由，每个节点都通过目标函数选择一个最优父节点，以此构建一个有向无环图。

如图1所示，路由的构建由根节点发起，根节点上电后，通过Trickle定时器[15]向周围广播DIO消息来通告自身的存在，DIO消息中包括实例号、DODAG ID、自身的Rank以及网络的配置信息。当周围节点A收到根节点的DIO消息后，首先将根节点加入到自身的父节点列表中，再通过目标函数(Object Function,OF)和父节点的Rank值计算自身的Rank值，并且向根节点单播回复一个DAO消息，根节点收到DAO消息后，添加子节点信息，并且回复DAO-ACK消息，节点A收到DAO-ACK消息后，即完成入网过程。

图1 路由构建过程

节点A完成路由构建后，将计算后的自身Rank值和网络配置信息添加至DIO消息中，向周围广播。节点B收到DIO消息后，计算Rank值后，将节点A添加到父节点列表，若该节点为最优父节点，则向节点A回复DAO消息，以建立下行路由。节点A收到该DAO消息后，添加至子节点列表中，并且将该DAO消息转发到根节点。

根节点收到DAO消息后向节点B发送DAO-ACK消息，节点B收到DAO-ACK消息后，完成入网过程。

当新节点C需要加入到网络中时，向周围节点周期性广播DIS消息以请求加入到网络中，周围已经加入DODAG的邻居节点B收到该DIS消息后，会向节点C发送DIO消息，节点C收到以后，向父节点发送DAO消息，最后收到DAO-ACK消息后，完成入网过程。

路由构建过程中，目标函数使用路由度量，如跳数和期望传输次数ETX，计算节点的Rank值，Rank值也将作为选择最优父节点的依据，节点通过比较父节点列表中父节点的Rank值，选择最优父节点。

RPL路由协议的构建分为存储模式和非存储模式。在存储模式下，每个节点收到DAO消息都需要存储子孙节点的信息，并且建立路由表后，再将DAO消息转发给自身的最优父节点。在非存储模式下，DAO消息直接发送给DODAG根节点，中间节点不存储DAO消息内容，仅将自己的地址添加在DAO消息中，发送给自己的最优父节点，只有根节点拥有全网每个节点的路由信息。

2 RPL路由协议组网优化算法

针对低功耗有损网中RPL路由协议构建的收敛时间过长以及构建过程中控制消息过多的问题，本文提出了一种RPL路由协议的组网优化算法，其中包括“跨节点聚合DAO”和“自适应DAO定时器”两部分，从而有效减少了构建过程中的收敛时间和降低构建过程中RPL的控制开销。

2.1 跨节点聚合DAO

在RPL路由协议的存储模式下，DAO数据包不是单播到DODAG的根节点，而是单播给自身的最优父节点，然后最优父节点添加完路由信息后发送给自身的父节点，这些DAO数据包以逐跳的方式到达DODAG的根节点，从而建立起RPL路由协议的下行路由。

“跨节点聚合DAO”机制在DIO消息中Reserved保留字段引入了DAO-Aggregation字段，在路由构建过程中，节点通过判断DIO消息中的DAO-Aggregation，以此决定是否需要聚合子节点DAO消息，以减少DAO消息的发送数量。其DIO消息的消息格式如图2所示。

图2 DIO消息格式

图2中的字段Agg是DAO消息聚合标志位，即DAO-Aggregation，占用8 bit保留字段中的1 bit。当DAO-Aggregation为1时，则表示节点需要聚合DAO消息，DAO-Aggregation为0时，节点立即回复DAO消息。

为了更好地兼容原有协议，聚合后的DAO消息采用原协议中的Target选项，Target选项用于指示沿DODAG可以到达的目的IPv6地址，即表示目标IPv6地址节点的可到达性。

本文将对聚合机制中的Target选项的包格式进行重新设计，如图3所示。

图3 改进后的Target选项

Option Length为整个Target选项的长度，DAO-PRI为优先级标志位，占用2 bit，告知父节点此消息能否被聚合，Prefix Length为IPv6地址的前缀长度。

对于聚合DAO消息中最大能聚合的地址数量，本文定义为Targetmax，其计算公式为：

(1)

DAOoverhead=IPv6h+ICMPv6h+DAOh+Tageth

(2)

式中：MTU为网络中的最大传输单元，由网络层而决定。IPv6h、ICMPv6h、DAOh、Targeth为控制消息中的IPv6头部、ICMPv6头部、DAO头部和目标选项的头部大小。

“跨节点聚合DAO”机制的算法流程如图4所示。

图4 “跨节点聚合DAO”流程图

整个DODAG的构建由根节点发起，将DIO消息中的DAO-Aggregation置为1,向周围节点广播DIO消息，让邻居节点能够加入到当前网络中。节点收到的DIO消息的DAO-Aggregation字段与自身发出的DIO消息中的DAO-Aggregation字段相反。

步骤一当节点收到DIO消息后，从DIO中获取DODAG信息，选择是否加入到网络中，若不加入网络，则返回继续监听。若选择加入到网络中，则添加路由信息，转至步骤二。

步骤二判断DAO-Aggregation是否为1，若该字段不为1，则添加完路由信息后，立即向自身最优父节点发送DAO消息，通告自身的目的地信息。若该字段为1，则不立即回复DAO消息，设置定时器以聚合DAO消息，转至步骤三。

步骤三设置完定时器后，将DIO消息中的DAO-Aggregation设置为0，并且向自身的周围节点进行广播。

步骤四在定时器到期前，若收到子节点的DAO消息，判断此时聚合数量是否已达上限，若未达到上限，则将该DAO消息聚合至自身的DAO消息中。若已达上限，则进行保存第二个DAO消息中，并转至步骤五。

步骤五在定时器到期后，节点将聚合后的DAO消息发送给自身的最优父节点。

2.2 自适应DAO定时器

DAO定时器决定了等待聚合的时间，起着非常重要的作用。在实际中，如果DAO定时器的时间值设置得比较小，节点在收到DAO消息后，将在很短的时间就发送给自身的父节点，无法达到聚合的最佳效果，尤其是在位于根节点附近的节点，无法降低近根节点周围的开销和缓解网络拥塞。而如果DAO定时器的时间设置得比较大，虽然很大程度上降低了控制开销，但是整个网络中，因为在各个设置DAO定时器的节点上会产生较大的延时，导致网络构建时间加长。因此，传输DAO消息的延时时间需要和拓扑信息结合。与此同时，节点收到DIO消息后，立即回复DAO消息，也使得构建过程中发生切换父节点的次数增加，增加网络的不稳定性。

本文提出一种“自适应DAO定时器”，节点在收到DIO消息之前，通过收到的DIS消息，掌握自身的邻居节点情况。定义Tdelaydao为DAO定时器的延时时间：

Tdelaydao=TRTT+Tprocess×Nneighbor

(3)

式中：TRTT为节点与子节点的单跳往返时延，Tprocess为节点处理DAO数据的平均时间。Nneighbor为节点的邻居数。

在DODAG根节点广播DIO消息前，普通节点都处于未加入DODAG的状态，需向周围周期性广播DIS消息。普通节点根据收到的DIS消息判断自身周围邻居节点的数量，并且自定义自身的DAO定时器。

当节点开启DAO定时器后，等待子节点的DAO消息的时间内，通过比较定时时间内收到的DIO消息，以决定最优父节点，增加链路的稳定性，减少切换父节点造成的不必要开销。对于需要聚合DAO消息的节点而言，DAO定时器将一定程度上增加其组网时间，降低响应实时性，但是对整个DODAG的构建来说，一次对DODAG的两层节点进行路由构建取代了原有逐层进行路由构建，缩短了整个DODAG的路由构建的收敛时间。

3 RPL路由协议组网优化算法实验

本节将模拟浮空器上设备自组网的应用场景进行实现和验证。为了验证RPL路由协议的组网优化算法的性能，采用基于OpenWRT(嵌入式Linux的发行版)系统的JS9331低功耗Wi-Fi开发板，单跳覆盖范围为30 m。对比协议为原始RPL路由协议、文献[12]中的RPL路由协议。

3.1 RPL路由协议的实现框架

整个协议的实现包括两个部分，分别为“路由控制模块”和“数据转发模块”，分别位于用户空间和内核空间。“路由控制模块”分为DIO、DAO、DAO-ACK、DIS消息的发送及处理模块、侦听模块、Trickle定时器模块、目标函数模块、路由更新模块等关键子模块，“数据转发模块”分为Pre-routing、Post-routing模块、虚拟文件模块等关键子模块。

系统整体框架如图5所示。“路由控制模块”通过DIO、DAO、DAO-ACK、DIS等控制信息的交互，获取链路信息，产生路由表信息，并将路由表信息通过PROC文件共享至内核空间。“数据转发模块”采用Netfilter框架，通过hook技术在挂载点进行嵌入，当数据包进入到Linux操作系统协议栈后，依据“路由控制模块”的路由信息，对数据包进行解析和处理，实现数据包的正确寻路、传输。

图5 整体实现框架

3.2 实验参数配置

实验中，为了模拟真实的设备节点，实验节点间的距离为20 m，根据不同的节点数量设置6种不同的网络拓扑。节点数为5、6的DODAG有同样的网络深度，深度为3；节点数为7、8的DODAG有同样的网络深度，深度为4；节点数为9的DODAG网络深度为5。本文实验环境的主要具体参数配置如表1所示。

表1 参数配置

续表1

3.3 实验结果分析

本文为评估优化后的RPL路由协议的性能，将从路由构建时间、控制开销两个方面对所提出的RPL路由协议组网优化算法进行验证。为了保证数据的可靠性，每次实验测试重复10次，最终取平均值作为最后结果。下面将对性能指标进行定义。

1) 路由构建时间：从根节点开机后发起组网至网络中全部节点都收到DAO-ACK消息，加入到DODAG中的时间。

2) 路由构建总控制开销：路由构建时间内，网络中节点发送DIO、DAO、DAO-ACK、DIS控制消息的总字节数。

如图6所示，随着DODAG中节点的数量增加，构建时间也在增加。其中当网络深度增加的时候，DODAG的构建时间增加幅度要相对高一些。对比图中，优化后的RPL路由协议，控制开销降低了至少9.3%。分析其主要原因为：网络初始化构建时，原始的RPL路由协议是逐层进行路由构建，并进行确认，“跨节点聚合DAO”机制和“自适应DAO定时器”每一次是针对DODAG中两层的节点进行入网确认，使得构建过程中减少了DAO消息和DAO-ACK消息的交互次数，从而有效地减少路由构建时间。

图6 路由构建时间比较

如图7所示为构建过程中的控制开销对比图。随着网络中节点的数量增加，控制开销的数量也在增加。如图7(a)所示，本文优化后的RPL路由协议相比于其他协议，DAO消息的数量得到了明显的下降。如图7(b)所示为路由构建的总控制开销对比，优化的RPL路由协议比现有RPL路由协议在路由构建过程的总控制开销至少降低了10.6%。

(a) DAO消息数量

(b) 路由构建总控制开销图7 路由构建控制开销比较

分析其主要原因：首先，“跨节点聚合DAO”机制将子节点的地址聚合成一个DAO消息，有效减少了向根节点发送的DAO消息的字节数，其次，“自适应DAO定时器”减少了DAO消息聚合节点的父节点切换次数，即减少了路由切换时的DAO消息的数量。最后，组网优化算法对聚合后的节点进行统一确认也降低了DAO-ACK消息的数量，从而减少了路由构建的总控制开销。

4 结 语

本文针对RPL路由构建过程中收敛时间过长以及控制开销过多的问题，提出一种RPL路由协议的组网优化算法，其包括了“跨节点聚合DAO”机制和“自适应DAO定时器”两种新机制。该算法对网络中的DAO消息进行有效聚合，并且通过对聚合的DAO消息进行统一的确认。实验测试表明，RPL路由协议的组网优化算法不仅能够有效降低控制开销，并且能缩短路由构建过程的收敛时间。在未来的工作中，我们将对父节点的选择机制进行研究，进一步增强网络的稳定性。