基于三角模算子的RPL协议路由优化算法*

仇英辉，何 霖

（华北电力大学电气与电子工程学院，北京102206）

随着智能建筑、工业环境监测以及智能电网环境监测控制等技术的不断推进，对于通信网络在能量、存储空间以及处理能力等限制条件下的修复力、互动效率和可持续性要求日益提高。鉴于这一需求，IETF提出了低功耗有损网络路由协议［1］RPL（Routing Protocol for LLN），并针对城市网络（包括智能电网）、建筑自动化、工业自动化以及家庭自动化四个领域制定了相应的路由需求［2-5］。

RPL协议是一种基于IPv6路由框架的距离矢量路由协议，拥有独特的路由创建规则。然而目前国内针对RPL协议的研究还相对较少，大多是应用于无线传感器网络的组网功能。文献［6］基于存储式的RPL协议，将RPL中的路由表简化成目的节点集合，并利用布隆过滤器管理这些集合，从而减少了存储开销；文献［7］为解决RPL协议只以跳数为路径选择度量而造成的Sink节点压力多大使其电量过早耗尽，采用了加权融合的方式（W-RPL）综合考虑跳数和节点能量两方面因素进行路径选择，以延长生命周期，然而文中并未对因素的隶属度进行定义，且加权融合的权重分配也并未明确；文献［8］采用簇首竞争机制，借助RPL路由协议中相关参数，通过分簇减少节点到网关的跳数，采用最优父节点优化驱动轮换机制，平衡各节点能耗，达到负载均衡的目的。

为进一步研究适用于LLNs的网络拓扑构建方式和路由方法，本文提出一种基于三角模算子的RPL协议路由优化算法，综合考虑能量指标和逻辑距离对网络构建和路由过程进行优化。

1 RPL协议

RPL协议的拓扑构建主要通过一系列的新型ICMPv6消息来完成，节点之间通过广播方式交换距离矢量等信息，并基于目标函数构建一个有向无环图 DODAG（Destination-Oriented Directed Acyclic Graphs），从而有效地防止了路由环路问题，最后节点通过目标函数进行路由度量以选择最优路径［1］；且目标函数的设置可以根据网络需求的不同进行灵活变动，从而构建相应的网络拓扑［9］。

1.1 DODAG构建过程

RPL中定义了一系列新的ICMPv6消息来控制拓扑结构的形成和交换图的相关信息，其中包括DODAG信息对象DIO（DODAG InformationObject）；DODAG请求信息DIS（DODAG Information Solicitation）和目的广播对象DAO（DestinationAdvertisementObject）。

DODAG图是基于树的网络拓扑结构，其构建一般是从汇集节点开始，也称为边界路由LBR（LLNBorder Router）；首先LBR向邻居节点广播携带有关于图的配置属性的DIO信息，接受到信息的节点通过DIO信息可以了解周围节点的配置属性及其Rank值，并根据约定目标函数决定是否加入该图，若加入，则LBR节点成为其父节点，节点计算更新其Rank值，同时也向邻居节点广播DIO信息，请求更多节点加入该DODAG图［10］，直至所有节点都加入图。另外，节点也可主动向邻居节点发送DIS信息请求图信息，请求加入DODAG图。如此重复以上两个过程，直到所有节点加入到DODAG图，LBR节点即是DODAG根。

图1 DODAG构成流程图

图1为一典型DODAG的构建简化流程图，LBR节点广播包含其自身配置信息的DIO信息，相邻的RA节点都在接收到DIO信息后，通过目标函数判定加入到图中，更新Rank值并向邻居节点（包括其父节点LBR）广播其DIO信息，除了含有目标函数、Rank值等基本信息外，还包含有其父节点信息。RB、RC、RD依次以洪泛形式重复上述过程。

1.2 RPL的路由过程

1.2.1 MP2P路由模型

MP2P（Multipoint-To-Point）路由模型是指多点到一点的路由传输路径，在DODAG图中是“向上”的路径。其路由过程基于DODAG的父子节点关系建立路径，各节点均保留其父节点的地址信息，当需要信息传输时，每个叶子节点都可通过向自己的父节点发送信息，逐级向上传送消息直至根节点，从而完成MP2P的信息传送。

1.2.2 P2MP路由模型

P2MP（Point-To-Multipoint）路由模型是指点到多点的路由传输，即指当有来自LLN网外部的信息，需要从父级节点传送到某一叶子节点的情况。P2MP的实现需要依赖向下路由的构建，其构建过程一般基于上行路径拓扑构建，节点通过发送DAO消息来声明目的节点地址用以完成向下路由的建立。在RPL协议中有两种路由模式：存储模式和非存储模式，二者区别在于存储模式下，每个父节点都存储有其子DODAG图的路由表，各子节点都会向其父节点单播发送DAO信息告知其目的地址；而非存储模式下，由于节点的存储空间有限，所以DODAG图中所有中间节点不需要存储路由表，所有的路由表信息都存储在DODAG根节点处，所以发送信息的子节点首先需按“向上”路径将DAO消息传送到DODAG根节点处进行路由构建［11］。

1.2.3 P2P路由模型

P2P（Point-To-Point）路由模型是指点到点的传输，RPL节点产生数据包沿向上的路径传输，并向该路径上的路由通知目的节点地址，直至找到与目的节点相同的祖先节点，再沿向下的路径传输。当在存储模式下，源节点只需将数据包传送到与目的节点共同的祖先节点处，然后根据祖先节点处存储的路由表信息选择下一跳到达目的节点即可；而非存储模式下，只有DODAG根节点为共同的祖先节点，即数据汇集到根节点处进行向下转发。

1.3 环路避免和环路检测

传统网络中，由于节点信息不同步或是拓扑结构改变，可能会出现暂时的环路现象，为了避免由于环路引起的丢包率突增、信道拥塞问题，所以RPL协议制定了节点“Rank Value”（下文简称R值），即上文所提的Rank值用来避免环路出现。RPL的计算规定叶子节点的父节点的R值必须小于其子节点的R值，因此有以下公式计算节点的R值：

式中：RS表示所求子节点的R值；RF表示所求子节点对应父节点的R值；RD表示所求子节点与其对应父节点的R值差。根据以上所得的R值，RPL有两个规则来避免环路：①最大深度规则，规定图中任何节点不可以选比自己R值还大的作为父节点；②拒绝贪婪规则，规定不允许图中任何节点移动到图中更深位置以增加自己潜在父节点数。

具体来说，检测环路的方法是在RPL路由信息的头部设置相关的bit位作为标记以检测路径的有效性。比如在上行链路中，将bit为设为“upward”，节点收到设置为“upward”的数据包查询路由信息选择合适的父节点向上传输信息。如果发现数据包是向下传输，则出现了临时的环路，数据包被丢弃并触发本地修复。

1.4 本地修复和全局修复

当链路或节点失效以后RPL协议提供修复功能，包括本地修复和全局修复功能。当环路检测到了某条链路失效，或某节点向上没有父节点路由时，本地修复会立即被触发，寻找新的节点替代原路径或原父节点以保证路径畅通。而本地修复一旦被触发，整个网络最优模式下的拓扑结构以及相关的路由信息就会改变，从而根节点会触发全局修复机制重建DODAG图。

1.5 Trickle定时管理算法

由于LLN网络中资源有限，不能使用在TCP等协议中广泛使用的“keepalive”，即周期性发送数据来保证路由的更新。因此，在RPL协议中采用了Trickle算法通过实现一致性来控制DIO消息的发送量。一致性是指检测网络中是否出现环路或者有新的节点加入或退出，如若没有则视为网络稳定，反之则视为网络不一致。当网络一致时，Trickle定时器控制节点减少DIO的发送量；当网络不稳定时，增加DIO的发送尽快解决路由信息不一致问题［12］。

2 基于三角模融合算法的RPL目标函数

2.1 目标量选取

RPL的拓扑构建和路径选择主要是根据节点的Rank值，即到根节点的距离来确定的，然而网络的QoS需要考虑多方面的影响［13］，单纯地选择更近的节点可能造成网络结构不均衡，局部超负荷等不良影响；为解决这一问题，本文中引入三角模算法将多目标量的影响进行融合，以实现各目标量影响间的优势均衡、矛盾中和；以影响LLNs最为直接的逻辑距离和节点剩余能量为目标，对其进行定义和隶属度拟合并作为三角模算法的因子。

2.1.1 逻辑距离

逻辑距离是指信息发送节点发送数据包到达目的节点逻辑上到达的距离，可表达为每一跳的路径长度和，如式（2）。逻辑距离与节点数据上传所需能量成正相关性，且优先选择逻辑距离较小的节点可一定程度上保证多跳网络各分支的均衡性。

式中：D为逻辑距离，Hopi为第i跳路径节点。

2.1.2 节点剩余能量

根据RPL协议的原理，在DODAG图构建初期，每一个节点能量的损耗即为发送或接收DIO信息的能量损耗，因此收发DIO消息的次数间接反映了邻居节点密集度。此外，从节能和生命周期的角度，选择剩余能量较多的节点，可以保证网络负载的均衡，有效延长整个网络的生命周期，避免因局部网络崩溃导致网络重建而消耗多余能量［14］。

2.2 基于三角模算子的目标量融合

2.2.1 目标量隶属度

根据三角模算子的性质可知参与融合的两个参数的取值范围是（0，1）［15］。为实现信息融合，根据RPL路由的逻辑距离值和剩余节点能量的特点，首先对两个参数分别进行归一化，其表达式分别如下：

式（4）表示剩余节点能量值的归一化过程，式中ηE表示剩余节点能量归一化以后的值，Er表示当前计算的父节点剩余能量值，Eo表示计算的父节点初始能量值。

根据逻辑距离值的特点，选用高斯隶属度函数计算其可靠性隶属度，其表达式如下：

式中c、σ为高斯函数期望和标准差，分别决定函数的位置和形状，本文中取c=0，σ=1。逻辑距离值和选取可能性结果成反比，即逻辑距离值越大被选上的可能性越小，所以为偏小型函数，即c=0；此外归一化以后逻辑距离值的取值范围为（0，1），所以σ=1，因此公式（5）变换为：

根据节点剩余能量值得特点，选用反正切函数作为计算其可靠性隶属度函数，其表达式如下：

其中λ，α的取值可根据需求灵活配置，本文中取λ=20，α=0.5，所得隶属度函数图像如图2所示。当节点剩余能量小于0.1（10%）时，则认为其能量水平不足以作为父节点，给定其隶属度为0.01；当节点剩余能量大于0.1（10%）小于0.4（40%）时，可以作为父节点，但相对并不适合，因而其隶属度增加相对缓慢；当节点剩余能量大于0.4（40%）时，则认为节点适合作为父节点，其隶属度随剩余能量的增大迅速增加。

2.2.2 三角模算子计算

三角模算法源于模糊数学，其算子表达式为：

其中a,b∈(0,1)，算子满足以下性质：①同类信息的加强 性 ，即F(a,b)≥max{a,b}，a≥0.5 ，b≥0.5 ，或F(a,b)≤min{a,b}，a≤0.5，b≤0.5；②矛盾信息的调和性，即min{a,b}＜F(a,b)＜ max{a,b}，(a-0.5)和(b-0.5)反号。

图2 节点剩余能量隶属度函数

即引入三角模算子后，可以实现在节点选取过程中既可以增强优势节点被选概率，弱化虚弱节点参与路径的概率；同时也可以调和备选节点中逻辑距离与节点剩余能量情况可能出现的矛盾性，平衡节点选取标准，如：对于逻辑距离和能量水平都处于良好情况时（隶属度均大于0.5），该节点被选中概率则会增大，反之亦然；而若逻辑距离和能量水平出现矛盾（其中之一隶属度高于0.5，另一隶属度低于0.5）则节点选中概率由两者的中和值来决定，从而调和参考因素矛盾性。综上，基于三角模算子的RPL路由优化算法，能够在保证优先距离优势节点的同时，兼顾节点能量水平，从而平衡网络负载，提升网络整体生命周期，避免局部节点提前死亡造成的网络故障，即网络可靠性和有效性得以增强。

3 实验仿真

本文参考Contiki系统平台［16］，基于Matlab仿真工具进行了本文算法与RPL协议以及加权融合RPL协议（W-RPL）的对比分析。在100×100的区域内随机设置100个采集节点，将其按照坐标划分为2个DODAG，分别将其中处于左下方的节点设置为Sink节点；考虑实际节点的能量情况可能具有差异性，节点初始能量设置为0.75～1.00之间的随机值。本文具体的仿真参量设置如表1，各取值可根据环境不同灵活配置。

表1 仿真参量设置

此外，为进一步拟合实际系统应用的通信需求，本文在上述配置基础上增加如下假设：①按照实际的采集需求，设定路由更新周期为每100点数据进行一次路由信息更新；②保证采集数据不缺失，当有节点死亡（能量水平低于5%）时，需要进行更换或充能；③除周期性的Sink节点采集信息外，存在随机的节点间通信业务。

本文目标量的选取主要以能量有效性和负载均衡性为依据，因此，为验证算法有效性，采用网络死亡节点数和网络平均能量消耗作为统计量进行对比分析。

网络死亡节点数主要体现了网络的通信负载均衡性，对于通信量集中的节点便容易提前死亡。本文算法与RPL协议的网络死亡节点数对比如图3所示，可见本文算法中首个节点死亡时间的出现比未改进RPL协议延迟416轮，比W-RPL协议延迟257轮；而同一轮内的节点死亡数也明显减少，相比RPL平均减少57.8%的死亡节点，比W-RPL平均减少40.7%；有效均衡了网络负载，提升了能量利用效率。

图3 网络死亡节点对比图

从横向的角度观察可得出，当网络的节点死亡率达到同一水平时，本文算法所进行的数据采集轮数远高于RPL协议。图4为不同节点死亡比例下的生命周期轮数，由图可见，在相同死亡率下，本文算法有效提升了网络的生命周期，当死亡率分别达到15%、30%及45%时，本文算法相对RPL协议可分别提高89.6%，46.7%，24.5%的数据采集轮数，相对WRPL也有所提升，然而当网络中节点能量都相对较少时，能量参数的权重影响则更为明显，因此网络节点死亡数较多时，W-RPL与本文算法差距较小。综上所述，可见本算法有效提升了网络的生命周期，延长了节点平均寿命，保证了系统的经济性和环保性。

图4 网络生命周期随节点死亡数趋势

本文算法的目标量选取，一方面考虑了节点能量的均衡，另一方面也考虑了节点的逻辑距离，即其通信能量开销，因此对网络的平均能量消耗进行统计分析，其结果如图5所示。前期节点能量还处于相对充裕的阶段，本文算法与RPL的能量消耗相差不大；但由于节点初始设置的能量有一定差别，因此W-RPL与本文O-RPL算法均要考虑一部分能量因素，而原始RPL协议则只考虑距离影响，因此相对而言能量消耗较小；而由于本实验中每96点更新路由的设定，因而在平均能量消耗曲线上体现出较强的波动性；当节点能量水平不均匀时，由于本文算法中节点会优先选择能量充裕且距离Sink节点逻辑距离较小的节点，其能量消耗相比于RPL逐渐体现出性能优势；而且三角模算子的引入能够有效扩大两个因素间的同向效果，因而相比于WRPL，本文算法整体上的能量消耗要较低，实现了在均衡网络负载的同时有效减少网络的能量损耗。

图5 平均能量消耗对比图

4 总结

本文根据当前智能监测控制的通信信息传输服务需求，结合低功耗有损网络协议的特点，提出了一种基于三角模算子的RPL协议路由优化算法，在节点接收DIO信息后的父节点选定过程中，通过基于三角模算子的节点剩余能量和逻辑距离指标融合进行了目标函数改进；并通过实验仿真对算法的优化效果进行验证分析，结果表明算法有效均衡了网络负载，延长了网络生命周期，降低了能量损耗，对于RPL协议的进一步发展和智能监测控制的应用具有重要意义。

［1］WinterT.etal.RFC6550：RPLIPv6RoutingProtocolforLow-Power andLossyNetworks［S］.InternetEngineeringTaskForce，2012.

［2］DohlerM.etal.RFC5548：RoutingRequirementsforUrbanLow-Pow⁃erandLossyNetworks［S］.InternetEngineeringTaskForce，2009.

［3］Pister K.et al.RFC 5673：Industrial Routing Requirements in Low-Power and Lossy Networks［S］.Internet Engineering Task Force，2009.

［4］Brandt A.et al.RFC5826：Home Automation Routing Require⁃ments in Low-Power and Lossy Networks［S］.Internet Engineer⁃ing Task Force，2010.

［5］Martocci J.et al.RFC 5867：Building Automation Routing Re⁃quirements in Low-Power and Lossy Networks［S］.Internet Engi⁃neering Task Force，2010.

［6］杨红，朱红松，，等.B-RPL：低存储开销的RPL路由协议［J］.计算机科学，2015，42（1）：96-100.

［7］胡芹艳，尹长川.无线传感网络中的RPL路由协议研究［J］.物联网技术，2014，1：57-59.

［8］高筱菲.基于RPL的无线传感器网络分簇路由研究与实现［D］.硕士学位论文.北京：北京交通大学，2014.

［9］朱琳，高德云，，等.无线传感器网络的RPL路由协议研究［J］.计算机与技术发展，2008，22（8）：1-4.

［10］Clausen T，Herberg U.et al.A Critical Evaluation of the IPv6 Routing Protocol for Low Power and Lossy Networks（RPL）［J］.Proc IEEE WiMob，2011，11：365-72.

［11］Ancillotti E.et al.The Role of the RPL Routing Protocol for Smart Grid Communications［J］.IEEE Communications Magazine，2013，11：75-83.

［12］Levis P.et al.RFC 6206：The Trickle Algorithm［S］.Internet En⁃gineering Task Force，2011：3.

［13］于淼，白光伟等.多力驱动的无线传感网络QoS路由协议［J］.传感技术学报，2013，26（11）：1564-1572.

［14］马建乐，杨军.基于位置和剩余能量的局部集中式LEACH算法研究［J］.传感技术学报，2013，26（8）：1147-1151.

［15］刘普寅.吴孟达.模糊理论及其应用［M］.长沙：国防大学科技出版社，1998.

［16］Dunkels A.et al.Contiki-a Lightweight and Flexible Operating System for Tiny Networked Sensors［J］.Proc IEEE LCN，2004，4：455-462.