WSNs中RPL路由的研究与下行算法的改进*

孙懋珩，倪升武

(同济大学 电子与信息工程学院，上海 201804)

WSNs中RPL路由的研究与下行算法的改进*

孙懋珩，倪升武

(同济大学 电子与信息工程学院，上海 201804)

RPL是IETF ROLL工作组针对低功耗有损网络所提出的IPv6路由协议，而无线传感网络属于低功耗有损网络之一。通过详细分析RPL协议中上下行路由的构建过程，发现下行路由构建过程中DAO消息发送数量较多，从而导致能量损耗较大的问题。针对此问题提出了新的算法，并使用Contiki系统的COOJA仿真器对网络进行仿真。与现有的算法进行比较验证，改进后的算法使DAO消息数量减少到原来的30%，从而大大降低了能量的消耗。

低功耗有损网络；无线传感网；RPL；COOJA

0 引 言

低功耗有损网络（Low Power and Lossy Networks，LLNs）是目前最重要也最具挑战性的研究领域之一。它包括无线个域网（Wireless Personal Area Networks，WPANs）、低功耗电力线通信网（Power Line Communication Networks，PLCs）和无线传感网（Wireless Sensor Networks，WSNs）。LLN是由功率、存储空间以及处理能力等资源受限的嵌入式设备组成，所以具有低数据率、有限能量以及可能出现的链路损坏等特点。

由于LLN的上述特点，路由的设计成为了LLN中最重要的问题之一。IETF ROLL（Routing Over Low Power and Lossy Networks）[1]工作组评估目前已经存在的路由协议（如OSPF、OLSR、AODV等），发现这些路由协议并不适合LLN。因此，该工作组研究制定了RPL（Routing Protocol for Low Power and Lossy Networks）协议，并于2012年3月发布了其协议标准RFC6550[2]。

本文将对RPL协议相关概念做简要描述，讨论其上下行路由的建立过程，并对现有下行路由过程中DAO消息发送数量过多的问题提出改进方案，最后使用Contiki系统中的COOJA仿真工具对新提出的算法进行仿真与分析，以验证其合理性。

1 RPL路由协议

1.1 网络拓扑的基本要素

RPL是LLN中基于IPv6的距离矢量路由协议。目标导向的有向无环图（Destination Oritented Directed Acyclic Graph，DODAG）是RPL中的一个基本元素。它是由根节点根据目标函数（Objective Function，OF）[3]以及一些度量和约束条件[4]构建的。每个DODAG中的节点（根节点除外）会选择一个父节点作为沿着DODAG向上的默认路由，OF的作用是对特定的度量（如跳数、时延、能量等）和约束条件来寻找最优的路径。在RPL中，指定以下四个参数来确定和维护一个网络拓扑图[5]：

（1）RPL实 例 号（RPLInstanceID）： 由DODAG根节点产生，用来指示RPL实例的标识号。

（2）DODAG ID号（DODAGID）：由DODAG根节点产生，是一个IPv6地址，用来作为当前DODAG的标识符，并唯一标识当前的DODAG。

（3）DODAG版本号（DODAGVersionNumber）：用来指示当前的DODAG版本。当网络出现更新时，该值会不断增加，用以动态更新当前网络的版本。

（4）Rank值：用来指示节点在网络中的位置。离根节点越远，该值越大。

内部控制管理体制的不完善，导致高校在招标过程中，缺少必要的监督制度与严格的操作过程以及容易受行政干扰，导致采购的物质质量、价格和售后服务都很难得到保证，极易滋生腐败。另外，高校在物资采购和验收时，存在一人同时负责这两项工作的情况，严重违反分工控制准则。在设备采购后，高校中出现不把新采购设备计入固定资产项目的情况，导致国有资产流失严重。

一个RPL实例包含一个或多个DODAG，每个DODAG有自身的DODAG ID号，即RPL实例号和DODAG ID号唯一确定了一个DODAG。在一个DODAG中，当网络出现故障或者有新的节点加入DODAG中时，当前的DODAG需要更新，版本号也随之增加。另外，在一个DODAG中，不同的节点根据自身与根节点的距离具有不同Rank值，节点只能选取比自身Rank值小的节点作为自己的父节点，如图1所示。

图1 RPL实例

RPL路由协议支持三种不同的通信模式[6]：点到点通信（Point-to-Point，P2P）、多点到点通信（Multipoint-to-Point，MP2P）和点到多点通信（Point-to-Mutipoint，P2MP）。同时，RPL路由协议可以工作在两种不同的模式下：存储模式和非存储模式。存储模式中，节点可以存储路由表和下一跳节点信息；非存储模式中，只有根节点能够存储整个路由表信息。

1.2 RPL上行路由的建立

MP2P即上行路由。该路由的建立需要发送DIO消 息（DODAG Information Object）。DODAG根节点将DIO消息中的Rank值设为1，然后广播DIO消息给自己的邻节点。当邻节点收到DIO消息后，它将判断是否是第一次接收DIO，如果是，就将发送节点加到自己的父节点列表中，并根据DIO消息中的OF来计算自己的Rank值以及自己到发送节点间的开销。如果不是第一次接收，那么该节点会将该DIO消息中的Rank值和自己的Rank值进行比较，若小于自己的Rank值，就适当减小自己的Rank值，并将其作为自己的父节点，同时删除父节点列表中与自己新的Rank值相同的父节点；若大于自己的Rank值，将丢弃此DIO消息。处理完DIO消息后，再将新的DIO消息以多播的形式转发给自己的邻节点，直到抵达叶节点为止。

DIO消息处理的伪算法如下：

在MP2P中，存储模式和非存储模式的节点都将父节点作为默认的下一跳路由，通过父节点转发数据到根节点。当一个新的节点想要加入网络时，它需要等待DIO信息的到来，或者它也可以主动向自己通信范围内的节点多播DIS消息。收到该DIS消息的节点会单播DIO消息给请求节点，这样新节点就可以顺利加入网络。DIS消息主要是在稳定环境中使用，如DODAG已经基本形成后，节点由于某种原因想再次获取图信息。

1.3 RPL下行路由的建立

P2MP即下行路由。该路由的建立需要发送DAO消 息（Destination Advertisement Object）。DODAG中的节点会触发它子图中的节点，向上发送DAO消息。该触发信息存储于DIO消息的某个字段中，称为DAO触发序列号（DAO Trigger Sequence Number，DTSN）。DAO消息的另一个触发方式是收到子节点发送的DAO消息，根据该消息中DAOSequence字段来决定是否向上发送DAO消息。在非存储模式中，如果节点收到的DIO消息中DTSN增加了，那么它也会增加自身的DTSN，然后将更新的DIO转发给子节点。同时，它会单播一个DAO消息，经过默认父节点到根节点。收到DAO消息的节点不对其做任何处理，沿着DODAG向上转发。在该模式中，只有根节点存有到下面节点的路由表，所以根节点会根据路由表构建到其余节点的源路由。在存储模式中，当节点收到更新的DIO消息后启动定时器。当定时时间到达时，向父节点单播DAO消息。DAO消息中包含节点的地址和头部，收到DAO消息的节点更新其路由表，将发送DAO的节点作为目的地址的下一跳，并转发更新后的DAO消息直到根节点。在该模式中，根节点只会存储到达目的节点的下一跳地址，所有节点都得向父节点发送一条DAO消息来建立根节点到自己的路由。

两种模式的过程如图2所示。

存储模式的伪算法如下：

从文献[7]中的仿真结果也可以看出，在DIO、DIS和DAO三个消息中，DAO消息的发送是RPL路由开销的主要因素。DAO消息之所以开销如此之大，主要有两个原因：第一，正如上文所分析的那样，每个节点在收到父节点发来的DIO消息后，都需要向上发送一条DAO消息，因为DAO消息中只携带了发送节点的地址；第二，DAO消息比DIO消息发送的数量多得多，因为DAO消息是多跳发送到根节点，而DIO消息仅仅在单跳范围内广播，所以DAO消息的量远远大于DIO消息的量。

图2 P2MP中非存储模式和存储模式

2 下行路由算法的改进

针对已有的问题，本文对现有的路由算法做了如下两部分的改进：

第一，当节点收到DIO消息后，判断自己是否为叶节点。若不是叶节点，处理完DIO消息后不向父节点发送DAO消息，只等待子节点发送DAO消息；如果是叶节点，则向其父节点发送DAO消息，开始建立下行路由。

伪算法如下：

第二，当节点收到子节点发来的DAO消息后，首先解析DAO消息，更新自己的路由表，然后将自己的地址信息添加到DAO消息的选项中，再发送给它的父节点。

改进的算法具有两个优点：第一，实现了上行路由和下行路由的分开建立；第二，保证网络中的每个叶节点到根节点的路径上，每个节点只发送或转发一次DAO消息，从而大大降低了能量的消耗。

下面将对该机制进行仿真，并与现有的机制作比较，评估其性能。

3 网络仿真与分析

本文使用Contiki系统中的COOJA模拟器对RPL进行仿真与评估。如图3所示，假设在区域内放置10个节点，节点8为根节点，节点9和10为叶子节点，其他均为路由节点，每个节点的通信范围为50 m。

图3 节点的网络拓扑

RPL路由协议在网络中实现的过程，即根节点节点启动过程、节点收到DIO消息并扩散DIO消息、节点发送DIS请求消息以及节点向父节点发送DAO消息的过程。从图4的仿真结果中可以看出，DAO消息的发送是由DIO消息所触发，即没有DIO消息发送的时候，也没有DAO消息的发送。但是，DAO消息的数量要远远大于DIO和DIS的数量。因为除了节点本身向上发送DAO外，还要转发子节点发送的DAO消息。

图4 路由建立过程中不同消息的个数（改进前）

图5为改进的RPL路由协议中三个控制消息的数量图。从图5中可以看出，在本文所提出的算法中，DIO消息和DIS消息没有显著的变化，而DAO消息的数量明显减少，约是改进前的1/3，从而大大减少了下行路由建立过程中能量的损耗。另外，由于改进算法中，下行路由是从叶节点开始建立的，所以路由建立时间要比改进前慢30 s左右，但这并不影响网络的性能。

图5 路由建立过程中不同消息的个数（改进后）

4 结 语

本文介绍了RPL路由协议的相关概念以及上下行路由的建立过程，并对现有的下行路由中存在的不足做了适当的改进。同时，使用COOJA对新算法进行了性能仿真。从仿真结果中可以看出，经过改进后，下行路由的建立过程中所需要发送的DAO消息明显减少，从而大大降低了路由过程中能量的损耗。同时，本文提出的机制实现了上下行路由的分开建立。后续工作可以从定时器的角度出发，可在具有不同Rank值的节点在DAO消息发送的时间设定上做一些算法研究，保证路由顺利建立的前提下，减少路由的开销，同时降低网络的拥塞。

[1] IETF WG.Routing Over Low Power and Lossy Networks[S]. http://tools.ietf.org/wg/roll.

[2] T. Winter.RPL:Routing Protocol for Low Power and Lossy Networks[S].http://tools.ietf.org/html/rfc6550.

[3] Thubert P.Objective Function Zero for the Routing Protocol for Low-Power and Lossy Networks (RPL)[S]. http://tools.ietf.org/html/rfc6552.

[4] Vasseur J.Routing Metrics Used for Path Calculation in Low Power and Lossy Networks[S].http://tools.ietf.org/ html/rfc6551.

[5] Tripathi J,Oliveira JC de,Jean-Philippe V.A Performance Evaluation Study of RPL:Routing Protocol for Low Power and Lossy Networks[C].Information Sciences and Systems (CISS),2010 44th Annual Conference on.IEEE,2010.

[6] Gaddour O,Koubâa A.RPL in A Nutshell:A Survey[J] Computer Networks,2012,56(14):3163-3178.

[7] Accettura N,Grieco LA,Boggia G,et al.Performance Analysis of the RPL Routing Protocol[C].Mechatronics (ICM),2011 IEEE International Conference on.IEEE,2011.

孙懋珩（1957—），男，博士，副教授，主要研究方向为数字图像处理、嵌入式、传感网；

倪升武（1990—），男，硕士，主要研究方向为传感网。

RPL Research and Improvement of Down Routing Algorithms in WSNs

SUN Mao-heng，NI Sheng-wu
(College of Electronic and Information Engineering, Tongji University, Shanghai 201804, China）

RPL is an IPv6 routing protocol proposed by the IETF ROLL Working Group for Low Power and Lossy Networks which contains Wireless sensor networks. This paper analyzes the process of building RPL up and down routing in detail, and finds a problem, a large energy loss during constructing the down routing, because of the large number of DAO messages sending. This paper proposes a new algorithm in terms of this problem and a simulator COOJA of Contiki system will be used to simulate and verify that the proposed algorithm reduces the number of DAO messages to 30% of original, thus greatly reduces energy consumption.

LLN;WSN;RPL;COOJA

TN929.5；TP212.9

：A

：1002-0802(2016)-06-0718-05

10.3969/j.issn.1002-0802.2016.06.013

2016-02-14;

：2016-05-06 Received date:2016-02-14;Revised date:2016-05-06