基于簇父集协作通信的低功耗有损网络路由算法优化

姚玉坤，刘江兵，李小勇

(移动通信技术重庆市重点实验室(重庆邮电大学)，重庆400065)

基于簇父集协作通信的低功耗有损网络路由算法优化

姚玉坤，刘江兵*，李小勇

(移动通信技术重庆市重点实验室(重庆邮电大学)，重庆400065)

(*通信作者电子邮箱liujb_cqupt@163.com)

针对当前低功耗有损网络(LLN)中基于簇父集协作通信的路由算法(CRPL)没有考虑节点剩余能量,存在不能有效地均衡节点能耗和最大化延长网络寿命的问题，提出一种高效的基于簇父集协作通信的低功耗有损网络路由(RPL)算法(HE-CRPL)。所提算法采取了三个优化思路:一是同时考虑节点间无线链路质量和节点剩余能量进行簇父节点的选择；二是在簇父节点优先级判定和最优簇父集的选择过程中把节点间的无线链路质量和簇父节点的期望寿命(ELT)相结合；三是在网络拓扑初始化的过程中通过利用目的地通告对象(DAO)消息携带簇父节点优先级列表告知最优簇父集中簇父节点的优先级顺序。仿真结果表明，与CRPL算法相比，HE-CRPL算法在延长网络生存时间、提高数据包投递成功率和减少数据包重传次数等方面的性能得到了提升，其中网络生存时间提高了18.7%，数据包重传次数降低了15.9%。

低功耗有损网络；簇父集；协作通信；优先级列表；剩余能量；期望寿命

0 引言

近年来，随着信息与通信技术和物联网技术的快速发展，低功耗有损网络(Low Power and Lossy Network, LLN)在工业控制[1]、医疗保健[2]和环境检测[3]等领域的应用越来越广泛; 然而，LLN因为无线传感器节点的处理能力、内存大小和功率等性能方面的缺陷以及无线通信链路质量的不稳定而受到制约。因此，LLN的上述特征给LLN中的路由协议设计带来极大挑战[4-5]。

LLN通常用于一些特殊的应用场景，使得无线传感器节点的电池不易更换因而能量受限，因此在最小化节点能量消耗的同时最大化延长网络寿命是LLN中路由协议设计的关键。已有的路由协议，如移动Ad-Hoc网络中的按需距离矢量路由协议(Ad-Hoc On-demand Distance Vector, AODV)[6]和动态源路由(Dynamic Source Routing, DSR)[7]因为路由开销较大而不适用于LLN的应用场景，因此互联网工程任务组(Internet Engineering Task Force, IETF)的低功耗路由算法工作组(Routing over LLN, ROLL)制定了一种基于IPv6的按需低功耗有损路由协议(Routing Protocol for Low Power and Lossy Networks, RPL)[8]。

随着工业界和学术界对LLN的深入研究，目前已取得大量研究成果。为了满足不同应用场景的多样化需求，ROLL工作组在文献[9]中提出了适用于LLN中的多种路由度量标准和约束条件，但未对每种路由度量标准和约束条件进行详细量化。

目前，ROLL工作组规定了两种目标函数：一种是将跳数作为度量标准的零目标函数(Objective Function Zero, OF0)[10],OF0仅考虑源节点到根节点之间的传输跳数加快了无线链路质量较差的节点的能耗速率；另一种是将期望传输次数(Expected Transmission Count, ETX)作为度量标准的具有迟滞性的最小网络深度目标函数(Minimum Rank with Hysteresis Objective Function, MRHOF)[11]，MRHOF仅考虑ETX，加快了无线链路质量较好的节点的能量消耗速率。

由于基于上述两种目标函数的RPL路由算法均无法均衡网络中节点能耗和最大化网络寿命，文献[12]在单路径RPL路由的基础上提出了一种缠绕多路径的改进策略。该策略将大量连续数据流按链路的路径权重分发到不同的路径上传输，能够均衡负载的能耗。但在路径权重的计算中未考虑节点的剩余能量，不能有效地延长网络寿命。

文献[13]提出了一种基于多边界路由器的负载均衡路由协议。该协议通过网关检测边界路由器的流量信息，判断流量是否过载。当流量过载时，利用网关计算网络的不均衡度并和切换阈值进行比较决定是否通知边界路由器启动负载均衡机制。该协议的缺陷在于当网络的不均衡度低于切换阈值时，不能达到负载均衡的目的，无法彻底解决网络拥塞问题。

文献[14]提出了一种基于节点期望寿命(Expected LifeTime, ELT)的均衡节点能量消耗的RPL路由算法。该算法通过计算网络拓扑中每个节点的ELT，根据ELT判断每条路径上的能量瓶颈节点，通过减少能量瓶颈节点的能耗达到延长网络寿命的目的。但在减少能量瓶颈节点的能耗过程中，加快了其他节点的能耗，同时子节点频繁更换父节点会产生网络震荡，并不能有效地延长网络寿命。

文献[15]提出了一种负载均衡的机会RPL路由算法(Opportunistic Routing Protocol for LLN, ORPL)，该算法在RPL路由协议的基础上融入机会路由算法，根据中继节点当前剩余能量和通信情况不断地调整中继节点的唤醒间隔。唤醒间隔的大小反映出中继节点转发数据包的概率，即唤醒间隔越大，中继节点转发数据包的概率越小。通过控制中继节点的唤醒间隔达到控制节点的能耗的目的。该算法的缺陷在于传输数据包时未考虑节点间的无线链路质量，导致丢包率上升，从而增加了发送节点的能量开销。

文献[16]提出了一种基于簇父集协作通信的RPL路由算法 (Cluster parent set based Routing Protocol for LLN, CRPL)，该算法的核心思想是通过簇父集协作转发数据包到达根节点。在簇父集协作通信的算法中考虑无线链路质量，能够达到均衡节点能耗和延长网络寿命的目的。但是在该算法中并未考虑簇父节点的剩余能量，导致簇父集中剩余能量不足但优先级较高的簇父节点的能量过早耗尽，不能有效地均衡节点能耗和延长网络寿命。

针对上述路由算法的缺陷，本文在CRPL算法的基础上提出一种高效的基于簇父集协作通信的RPL路由算法(High-Efficient Cluster parent set based Routing Protocol for LLN, HE-CRPL)并进行了仿真验证。

1 网络模型及问题描述

1.1 网络模型

针对由N个无线传感器节点(中继节点和叶子节点)和1个根节点(边界路由器)组成的低功耗有损网络模型，如图1所示。

图1 基于HE-CRPL算法的网络拓扑模型Fig. 1 Network topology model based on HE-CRPL algorithm

为了便于问题分析，给出以下假设：

1)所有无线传感器节点均部署在一个正方形监测区域内，根节点位于正方形监测区域正上方。所有无线传感器节点位置一旦确定，将不再发生移动。

2)网络拓扑初始化时，所有无线传感器节点的性能和参数保持一致，即节点的初始能量、传输功率、内存大小和数据处理能力等均相同。

3)根节点一直处于工作状态(时刻保持监听状态)，不进入休眠模式。其余所有无线传感器节点的休眠时间均较短，在通信范围内都能够监听到邻居节点的工作状态。

4)根节点的能量可以无限制补充，网络中其余所有无线传感器节点的能量均不能补充，由电池提供能量，且中途不更换电池，直至电池能量耗尽。

5)叶子节点只产生数据分组，不转发其他节点的数据分组。中继节点既能够产生数据分组，又可以转发其他节点的数据分组。

为了便于问题分析，给出以下定义。

定义1 最大簇父集。最大簇父集是指由一个子节点的所有簇父节点组成的集合。如图1所示，节点H的最大簇父集为节点B、C、D组成的集合{B,C,D}。

定义2 期望寿命因子系数。期望寿命因子系数是指最大簇父集中各个簇父节点的ELT在最大簇父集中所占权重的倒数，用θ表示。

1.2 问题描述

CRPL算法的核心思想是通过计算选出LLN中每个节点(根节点除外)的最优簇父集，通过最优簇父集协作转发数据包到达根节点，完成数据包的汇聚过程。该算法将节点间的无线链路质量作为簇父节点的选择标准；其次依据簇父节点成功传输一个数据包到达根节点的传输代价判断簇父节点的优先级顺序；然后依据源节点成功传输一个数据包经过簇父集到达根节点的累积传输代价选择最优簇父集；最后通过将最优簇父集中的簇父节点的优先级列表添加到待发送数据包的头部告知最优簇父集中簇父节点的优先级顺序。通过深入研究，作者发现该算法存在以下3个问题：

1)选择簇父节点时仅依据节点之间的无线链路质量，而当剩余能量较低的节点被选择为簇父节点时，由于没有考虑簇父节点的剩余能量，会加剧剩余能量不足的簇父节点的能耗速率，无法有效地达到节点能耗均衡的目的，降低了网络生存时间。

2)簇父节点优先级的高低依据簇父节点成功传输一个数据包到达根节点的传输代价大小决定，而未考虑源节点成功传输一个数据包到达簇父节点的传输代价。此外，传输代价的计算仅仅考虑了节点间的无线链路质量，未考虑簇父节点的ELT，从而影响簇父节点优先级的判定。同样，在选择最优簇父集的过程中也因为未考虑簇父节点的ELT而影响最优簇父集的选择。

3)源节点将优先级列表添加到需发送数据包的头部，通过数据包的传输告知簇父集中簇父节点的优先级顺序。由于无线链路有损特性，无法确定最优簇父集中所有簇父节点均接收到携带有簇父节点优先级列表的数据包，从而无法确保最优簇父集中所有簇父节点都获知优先级列表。一旦某个簇父节点未成功接收到数据包将会导致源节点在传输下一个数据包时，需再次将优先级列表添加到数据包的头部，从而增大了源节点的能耗。

2 HE-CRPL路由算法的优化机制

本文针对CRPL算法中存在的上述三个问题提出改进算法HE-CRPL，在HE-CRPL算法中提出了四种优化机制，分别是簇父节点选择机制、簇父节点优先级判定机制、最优簇父集选择机制和优先级列表携带机制。

2.1 簇父节点选择机制

簇父节点选择机制涉及一个父节点作为理想的簇父节点应满足两个条件：第一，父节点与子节点之间的无线链路质量高于设定的链路质量阈值；第二，父节点的剩余能量同样应高于设定的能量阈值。在LLN中构建面向目的地有向无环图(Destination Oriented Directed Acyclic Graph, DODAG)的过程中，中继节点将自身的剩余能量信息和无线链路质量信息添加到DODAG信息对象(DODAG Information Object, DIO)中。当某一节点接收到邻居节点广播的DIO消息后，判断邻居节点的网络深度值(Rank)是否低于自身的Rank值。如果上述条件满足，该节点则从收到的DIO消息中获取邻居节点的无线链路质量信息和剩余能量信息，并分别判断无线链路质量和节点剩余能量是否满足要求。

随着网络中节点的能量不断消耗和网络拓扑周期性的重建，当某一节点与其全部父节点之间的无线链路质量均低于无线链路质量阈值时，选取无线链路质量相对较高的无线链路对应的父节点作为簇父节点。当某一节点的全部父节点的剩余能量均低于能量阈值时，选取剩余能量相对较高的父节点作为簇父节点。具体判断方法遵循图2所示的流程。

2.2 簇父节点优先级判定机制

簇父节点优先级判断机制是指在网络拓扑初始化过程中，分别计算源节点成功传输一个数据包经过其各个簇父节点到达根节点的传输代价，传输代价值越小，赋予簇父节点的优先级越高。在簇父集中，优先级越高的簇父节点具有优先转发数据包的特性。簇父节点优先级的具体判定步骤如下：

图2 簇父节点的选择流程Fig. 2 Flow chart of cluster parent node selection

步骤1 在网络拓扑周期性的构建过程中，子节点获得与簇父节点之间的无线链路质量信息和簇父节点剩余能量信息后，计算每个簇父节点的期望寿命ELT[17]。ELT的计算如式(1)，式(1)中各个度量值的物理意义如表1所示。

(1)

其中：Ttotal(j)和ETX(j,CPS(j))的计算如式(2)和式(3)所示:

(2)

(3)

其中：Tgen(j)表示簇父节点j产生的数据包，Ttotal(b)表示簇父节点j收到其子节点b发送的数据包，pjl表示节点j与其簇父节点l之间的无线链路质量。

表1 ELT的计算公式中各度量值的物理意义Tab. 1 Physical meaning of each metric in ELT

步骤2 根据式(4)计算簇父节点j的期望寿命ELT(j)在最大簇父集中所占的权重。

(4)

步骤3 根据式(5)计算每一个簇父节点的期望寿命因子系数θ。

θj=1/Kj

(5)

步骤4 根据式(6)分别计算源节点成功传输一个数据包经过其各个簇父节点到达根节点的传输代价，并根据传输代价值的大小判定簇父节点的优先级顺序。

(6)

式中:Pi, j∈CPS(i)表示节点i与簇父集CPS(i)中各簇父节点之间的无线链路质量，Cj表示簇父节点j成功传输一个数据包到达根节点的传输代价，Ci→j∈CPS(i)→Root表示节点i成功传输一个数据包经过其簇父节点j到达根节点的传输代价。根据传输代价值Ci→j∈CPS(i)→Root的大小可以判断簇父集中各个簇父节点的优先级，即Ci→j∈CPS(i)→Root越小，簇父节点优先级越高，Ci→j∈CPS(i)→Root越大，簇父节点优先级越低。

2.3 最优簇父集选择机制

最优簇父集选择机制是指簇父节点优先级判定之后，源节点分别计算成功传输一个数据包经过其各个簇父集到达根节点的传输累积代价，传输累积代价最小值对应的簇父集为最优簇父集。端到端传输累积代价的计算与簇父节点优先级判定类似，也需要同时考虑节点间的无线链路质量和簇父节点的ELT。传输累积代价的计算步骤如下：

步骤1 通过簇父节点选择机制选出合适的簇父节点，将簇父节点划分为不同的簇父集。例如在图1中，节点K有三个簇父节点E、H和G，其簇父集组合方式则有7种，分别为{E}、{H}、{G}、{E,H}、{E,G}、{H,G}和{E,H,G}。

步骤2 通过簇父节点优先级判定机制获知子节点的每个簇父节点的优先级顺序。例如在图1中，假设节点K与其簇父节点E、H和G之间的无线链路质量分别为0.8、0.6和0.7，如何计算节点间的无线链路质量不在本文考虑范围内，由数据链路层决定。同时假设通过式(1)计算得知节点E、H和G的期望寿命分别为50、25和25，且节点E、H和G成功传输一个数据包到达根节点的传输代价分别为4、3和2。根据式(6)计算得知节点K分别成功传输一个数据包经过簇父节点E、H和G到达根节点的传输代价大小为H>G>E，故簇父节点E、H和G的优先级顺序为E>G>H。

步骤3 分别计算节点K成功传输一个数据包到达其各簇父集的联合代价和各簇父集成功转发一个数据包到达根节点的剩余路径代价。联合代价的计算如式(7)所示，剩余路径代价的计算如式(8)所示:

(7)

(8)

步骤4 根据步骤3计算得知的联合代价ETXCPS(i)和剩余路径代价RCCPS(i)，由式(9)分别计算节点K成功传输一个数据包经过其各个簇父集到达根节点的传输累积代价CCPSi,CPS(i)，CCPSi,CPS(i)最小值对应的簇父集为最优簇父集。计算得知节点K成功传输一个数据包经过簇父集{E,G}到达根节点的CCPSi,CPS(i)最小，故最优簇父集为{E,G}。

CCPSi,CPS(i)=ETXCPS(i)+RCi,CPS(i)

(9)

2.4 簇父节点优先级列表携带机制

簇父节点优先级列表携带机制是指在网络拓扑初始化的过程中，首先依据簇父节点优先级判断机制获知子节点的簇父节点优先级顺序，然后通过最优簇父集判定机制获知子节点的最优簇父集后，子节点将其最优簇父集中簇父节点优先级列表添加到目的地通告对象(Destination Advertisement Object, DAO)中，通过回复携带优先级列表的DAO消息告知簇父节点在最优簇父集中的优先级顺序。簇父节点收到携带优先级列表的DAO消息后，检查优先级列表中是否包含其自身信息。如果包含其自身信息，则提取节点优先级列表并存储。反之，如果不包含自身信息则丢弃DAO消息。

3 HE-CRPL路由算法的操作步骤

HE-CRPL路由算法的核心思想在于利用簇父节点协作转发数据包，均衡网络中节点能耗，同时降低数据包的丢包率，减少数据包的重传，能够高效地利用带宽资源、延长网络整体寿命和提升数据包的投递成功率。例如在图1中，假设节点H的最优簇父集为{B,C,D}，且最优簇父集中簇父节点B、C和D的优先级顺序为C>D>B。如图3所示，最优簇父集{B,C,D}协作通信的步骤如下。

图3 簇父集协作通信示意图Fig. 3 Diagram of cluster parent set collaborative communication

步骤1 网络拓扑初始化完成后，节点H开始传输数据包并开启重传计时器T1。

步骤2 最优簇父集{B,C,D}中的节点C收到数据包后，先将其缓存，然后判断在最优簇父集中的优先级顺序。节点C检测到其优先级最高，于是向节点H回复ACK消息，并向上一跳转发先前缓存的该数据包。本文中不考虑ACK消息发生丢包情况，因为它可以通过复杂的编码技术恢复.

步骤3 节点D收到数据包后，同样先缓存该数据包，然后检测其在最优簇父集中的优先级顺序。节点D检测到优先级顺序低于节点C，于是开启ACK计时器T2，开始监听节点C是否向节点H回复ACK消息。如果节点D监听到节点C已回复ACK消息，则丢弃先前缓存的数据包，且停止ACK计时器T2并归零。如果节点D在ACK计时器T2到期后依旧未监听到节点C向节点H回复ACK消息，节点D则立刻向节点H回复ACK消息，并向上一跳转发先前缓存的该数据包。

步骤4 节点B重复节点D的处理过程，开启ACK计时器T3，开始监听节点C和D是否向节点H回复ACK消息。如果在ACK计时器T2到期后，节点B未监听到节点C或D向节点H回复ACK消息，节点B则立刻向节点H回复ACK消息，并向上一跳转发先前缓存的该数据包.

步骤5 只要节点H收到最优簇父集{B,C,D}中的任意一个簇父节点回复的ACK消息，节点H则取消重传计时器T1，并向最优簇父集{B,C,D}传输下一个数据包。如果节点H在重传计时器T1到期后依旧未收到其最优簇父集{B,C,D}中任意一个簇父节点回复的ACK消息，则重传上一个数据包，重置重传计时器T1，并重复上述所有步骤。

4 仿真实验及结果分析

本文采用contiki2.7操作系统的COOJA软件进行仿真平台搭建，选取RPL算法、ORPL算法和CRPL算法作为参照对象，在相同场景条件下通过仿真对比分析与HE-CRPL算法在不同节点数量的网络中的网络生存时间、数据包投递成功率和数据包重传次数性能指标上的差异。

4.1 网络场景及参数设置

为了评估HE-CRPL路由算法的性能相对于RPL算法、ORPL算法和CRPL算法的优越性，在300 m×300 m的正方形区域构建节点数分别为20、40、60、80且节点随机分布的低功耗有损网络，其无线信道采用阴影衰落模型。LLN中的节点通常有两种工作模式：存储模式和非存储模式。在仿真过程中节点选择存储模式，且每次仿真重复10次，最终取平均值作为仿真结果。具体仿真参数设置如表2所示。

表2 仿真参数设定Tab. 2 Simulation parameters setting

4.2 仿真结果分析

1)网络生存时间。

网络生存时间定义为网络初始化过后出现第一个能量耗尽的节点所耗费的时间，是衡量网络性能的一项重要指标。从图4中可以得知随着网络中节点数量的增加，4种算法的网络生存时间均呈下降趋势。这是因为随着节点数量的增加，网络密度增大，导致根节点附近的节点转发数据包的数量急剧增加，加快了附近节点能量消耗，因而网络生存时间呈下降趋势。但是HE-CRPL算法明显优于其他3种算法，相对于RPL算法和ORPL算法，HE-CRPL算法通过簇父集协作通信降低了发送节点数据包重传消耗的能量，同时使簇父节点的能耗实现均衡；相对于CRPL算法， HE-CRPL算法选择簇父节点时考虑了节点的剩余能量，从而不选择优先级较高但剩余能量不足的节点作为簇父节点。此外，通过DAO消息携带簇父节点优先级列表，在数据传输过程中能够有效地避免因丢包重复将优先级列表添加到数据包中，从而降低了发送节点的能量开销。

图4 网络生存时间比较Fig. 4 Comparison of network lifetime

2)数据包投递成功率。

数据包投递成功率是指数据包成功到达根节点的个数与网络中源节点发送数据包总数的比值。从图5可以得知随着网络中节点数量的增加，4种算法的数据包投递成功率均不断降低。因为随着节点数量的增加，网络密度增大，数据包的传输距离相对增大，由于无线链路有损特性，导致丢包率增加。但是HE-CRPL算法优于其他3种算法，原因在于相对于RPL算法和ORPL算法，HE-CRPL算法通过簇父集协作通信方式传输数据包，降低了数据包因丢包而重传的概率，从而提高了数据包的投递成功率；相对于CRPL算法，HE-CRPL算法在判定簇父节点的优先级顺序和选择最优簇父集时综合考虑了簇父节点的ELT，使得簇父节点的优先级判定更加准确，最优簇父集的选择更加合理，从而有利于数据包的传输；同时ELT的计算过程中考虑了节点中缓存的数据包数量，能够有效地降低网络拥塞发生的概率，从而降低了数据包因发生网络拥塞而产生的丢失率。

图5 数据包投递成功率比较Fig. 5 Comparison of packet delivery rate

3)数据包重传次数。

若中继节点未成功收到源节点发送的数据包则会导致源节点重传该数据包。图6是不同节点数量的网络对不同路由算法数据包重传次数影响的仿真结果。从图中可以得知随着网络规模的扩大，4种算法的数据包重传次数均不断增加。但HE-CRPL算法优于其他3种算法，相对于RPL算法和ORPL算法，原因在于HE-CRPL算法通过簇父集协作转发数据包，可以尽可能避免因数据包在某一条链路上发生丢包而导致源节点重传该数据包，能够最大化提高数据包投递成功率，从而最大限度地降低了数据包的重传次数；相对于CRPL 算法，HE-CRPL算法在计算簇父节点的ELT时考虑了节点中数据包的缓存数量，能够有效地降低数据包因缓存或是网络拥塞而导致丢包发生的概率，从而降低了数据包重传次数。

图6 数据包重传次数比较Fig. 6 Comparison of the number of data packet retransmission

5 结语

本文针对LLN的相关特点，提出一种高效的基于簇父集协作通信的RPL路由算法(HE-CRPL)。该算法在CRPL算法的基础上进行优化，通过与现有RPL能量均衡相关算法的有效结合，能够使网络中的节点能耗均衡并进一步延长网络生存时间。HE-CRPL算法在选择簇父节点时在保证通信质量的前提下同时考虑节点的剩余能量；在簇父节点的优先级判定和最优簇父集的选择过程中引入节点期望寿命，从而有效地延长网络寿命；另外，将优先级列表通过DAO消息携带，在数据传输过程中避免了因丢包而重传携带优先级列表的数据包，从而降低了发送节点的能量开销。通过实验仿真结果表明，相对于CRPL算法，HE-CRPL算法能够有效地实现节点能耗均衡，最大化地延长网络生存时间和减少数据包重传次数，其中网络生存时间提高了18.7%，数据包重传次数降低了15.9%。

References)

[1] DIAS J, RIBEIRO F, CAMPOS R, et al. Evaluation of an RPL/6LoWPAN/IEEE 802.15.4g solution for smart metering in an industrial environment[C]// Proceedings of the 2016 12th Annual Conference on Wireless On-demand Network Systems and Services. Piscataway, NJ: IEEE, 2016: 1-4.

[2] GARA F, SAAD L B, AYED R B, et al. RPL protocol adapted for healthcare and medical applications[C]// Proceedings of the 2015 International Wireless Communications and Mobile Computing Conference. Piscataway, NJ: IEEE 2015: 690-695.

[3] QUYNH T N, LE-MANH N, NGUYEN K N. Multipath RPL protocols for greenhouse environment monitoring system based on Internet of things[C]// Proceedings of the 2015 12th International Conference on Electrical Engineering/Electronics, Computer, Telecommunications and Information Technology. Piscataway, NJ: IEEE, 2015: 1-6.

[4] HERBERG U, CLAUSEN T. Study of multipoint-to-point and broadcast traffic performance in the “IPv6 routing protocol for low power and lossy networks” [J]. Journal of Ambient Intelligence and Humanized Computing, 2011, 2(4): 293-305.

[5] KO J G, TERZIS A, DAWSON-HAGGERTY S, et al. Connecting low-power and lossy networks to the Internet[J]. Communications Magazine, 2011, 49(4): 96-101.

[6] KHELIFA S, MAAZA Z M. An energy multi-path AODV routing protocol in Ad Hoc mobile networks[C]// Proceedings of the 2010 5th International Symposium on I/V Communications and Mobile Network. Piscataway, NJ: IEEE, 2010: 1-4.

[7] BADAL D, KUSHWAH R S. A energy efficient approach to DSR based routing protocol for Ad Hoc network[J]. International Journal of Computer Applications, 2015, 118(4):14-17.

[8] WINTER T, THUBERT P, BRANDT A, et al. RPL: IPv6 routing protocol for low power and lossy networks: RFC 6550 [S]. Geneva: IETF, 2012:1-157.

[9] VASSEUR J, KIM M, PISTER K, et al. Routing metrics used for path calculation in low-power and lossy networks: RFC 6551 [S]. Geneva: IETF, 2012:1-30.

[10] THUBERT P. Objective function zero for the routing protocol for low-power and lossy networks: RFC 6552 [S]. Geneva: IETF, 2012: 1-14.

[11] GNAWALI O, LEVIS P. The minimum rank with hysteresis objective function: RFC 6719 [S]. Geneva: IETF, 2012:1-14.

[12] 张宗杰, 刘彤, 马皛源, 等. 无线传感器网络RPL路由协议优化[J]. 中国科技论文在线精品论文，2014，7(8)：715-721.(ZHANG Z J, LIU T, MA J Y, et al. Wireless sensor network RPL routing protocol optimization[J]. Highlights of Sciencepaper Online, 2014, 7(8): 715-721.)

[13] 胡婷婷, 秦雅娟, 高德云. IPv6无线传感网负载均衡路由协议研究[J].计算机技术与发展, 2015,25(7):27-30.(HU T T, QIN Y J, GAO D Y. Research on multi-sink load-balanced routing protocol for IPv6 wireless sensor networks[J]. Computer Technology and Development, 2015, 25(7): 27-30.)

[14] 宋海龙, 张书真. 基于期望寿命与均衡能量消耗的RPL路由协议[J]. 计算机工程,2016,42(1):77-82. (SONG H L, ZHANG S Z. RPL routing protocol based on expected lifetime and balance energy consumption[J]. Computer Engineering, 2016, 42(1): 77-82.)

[15] MICHEL M, DUQUENNOY S, QUOITIN B, et al. Load-balanced data collection through opportunistic routing[C]// Proceedings of the 2015 International Conference on Distributed Computing in Sensor Systems. Piscataway, NJ: IEEE, 2015: 62-70.

[16] ZHAO M, SHWE H Y, CHONG P H J. Cluster-parent based RPL for low-power and lossy networks in building environment[C]// Proceedings of the 2015 12th Annual Consumer Communications and Networking Conference. Piscataway, NJ: IEEE, 2015: 779-784.

[17] IOVA O, THEOLEYRE F, NOEL T. Improving the network lifetime with energy-balancing routing: application to RPL[C]// Proceedings of the 2014 7th Wireless and Mobile Networking Conference. Piscataway, NJ: IEEE, 2014: 1-8.

This work is partially supported by the National Natural Science Foundation of China (61379159), the Foundation and Frontier Research Project of Chongqing (cstc2015jcyjBX008).

YAO Yukun, born in 1964, M. S., professor. Her research interests include network management and application, network coding.

LIU Jiangbing, born in 1989, M. S. candidate. His research interests include routing of wireless networks.

LI Xiaoyong, born in 1992, M. S. candidate. His research interests include wireless network coding.

Optimized routing algorithm based on cooperative communication of cluster parent set for low power and lossy network

YAO Yukun, LIU Jiangbing*, LI Xiaoyong

(KeyLaboratoryofMobileCommunicationTechnology(ChongqingUniversityofPostsandTelecommunications),Chongqing400065,China)

To deal with the problems that the routing algorithm based on Collaborative communication of Cluster Parent (CRPL) for Low Power and Lossy Network (LLN) can’t balance the energy consumption of the node and maximize the extension of the lifetime for network efficiently due to take no account of the residual energy of the node, a high-efficient routing algorithm based on collaborative communications of cluster parent set HE-CRPL was proposed. The proposed algorithm chiefly carried out three optimization schemes. Firstly, the wireless link quality and the residual energy of node could be considered during the cluster parent selection. Secondly, the wireless link quality and the Expected LifeTime (ELT) of cluster parent node were combined while estimating the priority of the cluster parent node and selecting the optimal cluster parent set. Thirdly, the cluster parent nodes were notified the priority list by Destination Advertisement Object (DAO) message during the initialization of the network topology. The simulation results show that, compared with the CRPL algorithm, the performance of the HE-CRPL algorithm is improved obviously in prolonging the network lifetime, increasing the packet delivery success rate and reducing the number of packet retransmissions, and that the lifetime of network prolonging by more than 18.7% and the number of retransmissions decrease by more than 15.9%.

Low power and Lossy Network (LLN); cluster parent set; collaborative communication; priority list; residual energy; Expected LifeTime (ELT)

2016-10-21;

2016-12-13。

国家自然科学基金资助项目(61379159); 重庆市基础与前沿研究计划项目(cstc2015jcyjBX0085)。

姚玉坤(1964—)，女，重庆人，教授，主要研究方向：网络管理与应用、网络编码； 刘江兵(1989—)，男，重庆人，硕士研究生，主要研究方向：无线组织网络路由； 李小勇(1992—)，男，湖北荆州人，硕士研究生，主要研究方向：无线网络编码。

1001-9081(2017)05-1300-06

10.11772/j.issn.1001-9081.2017.05.1300

TP393

A