基于普通节点负载均衡的RPL路由协议*

仇英辉，陈　玲

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

基于普通节点负载均衡的RPL路由协议*

仇英辉*，陈玲

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

传统的RPL路由协议并未涉及到节点负载均衡的问题，容易造成网络局部负载过重导致部分节点死亡。阐述了RPL路由协议的拓扑构建、路由过程及一些现有的目标函数，定义了邻居距离和剩余能量级别两个参考指标，通过划分能量级别和改变通信半径两重负载均衡方法，提出了一种基于普通节点负载均衡的RPL路由协议——OLB-RPL。通过实验仿真验证结果证明改进后的协议可以实现网络中普通节点的负载均衡，并且在减少节点能量消耗的同时延长了整个网络的生存时间。

低功耗有损网络；RPL路由协议；剩余能量级别；邻居距离；负载均衡

EEACC:6150Pdoi:10.3969/j.issn.1004-1699.2016.07.021

在低功耗有损网络LLNs（Low-power and Lossy Networks）中［1］，路由器往往受到处理能力、存储能力和能量或电池功率方面的限制。它们之间的连接具有高丢包率、低带宽和不稳定的特点。而RPL路由协议LLNs（Routing Protocol for LLNs）是IETF提出的针对LLN网络特点的路由协议［2-3］。

目前，国内外对RPL的研究热点主要是在路由算法、拓扑控制和协议安全这几个方面［4-6］。在负载均衡［6-9］方面文献［6］提出了一种基于RPL的多Sink节点的负载均衡的方法LB-RPL，通过均衡网络的负载延长了网络的生存时间，但是文中只针对多Sink节点考虑负载平衡，却没有考虑普通传感节点的过负荷情况，这样以来容易使普通节点因提前耗尽能量而死亡，造成通信障碍。为进一步研究适用于LLNs的网络拓扑构建方式和路由方法，并且避免不同传感节点负载不均衡的情况，本文提出一种基于普通节点负载均衡的RPL路由协议的优化算法——OLB-RPL，综合考虑能量指标和传感器邻居节点集范围对网络构建和路由过程进行优化。

1　RPL路由协议

RPL是一个距离矢量路由协议，通过目标函数和度量集合构建一个具有目的地的有向无环图DODAG（Destination Oriented Directed Acyclic Graph），然后根据路由度量和约束条件选择最优路径完成路由过程。RPL路由协议中定义了三种ICMPv6控制消息用来交换图的相关信息并构建网络拓扑：DODAG信息对象DIO（DODAG information object），用于通告有关DODAG的参数；DODAG请求信息DIS（DODAG Information Solicitation），用于向邻居节点请求DODAG信息；目的广播对象DAO（Destination Advertisement Object），用于构建向上的路由［2，4］。

如图1所示，是整个DODAG图的构建。DODAG图是基于树的网络拓扑结构，其构建一般从根节点开始，即边界路由LBR（LLN Border Router）或sink节点。如图1所示，LBR节点和普通RPL节点随机分布在传感区域内，首先LBR向自己发送功率半径范围内的邻居节点广播携带有关于图的配置属性的DIO信息，节点A通过DIO获取发送节点的配置属性及其Rank值，决定是否加入图中。若加入图中，LBR成为A的父节点，此时A节点根据DIO中的信息计算自己的Rank值，并修改DIO中的信息向周围的节点广播DIO数据包，处于A节点发送功率半径内的节点B收到A发来的DIO后决定加入图中，计算自己的Rank值，然后向周围节点发送自己的DIO消息，并回送给A一个DAO消息。以此类推节点C也加入图中。假设一个节点收到了几个DIO消息，则选择使自己Rank值最小的DIO帧的发送节点作为父节点。此时，未收到DIO的节点D也想加入图中，它主动向自己的邻居节点A发送DIS信息请求加入DODAG中，A收到DIS后向节点D发送DIO信息邀请D加入图中，D加入图中后回送DAO信息。重复上述过程，直到所有节点加入到DODAG图中，LBR节点即是整个DODAG的根，如图1所示。

图1　DODAG的构建

值得注意的是，在非存储模式下，叶子节点回复的DAO消息需要发送至根节点，在根节点处计算整个网络的DODAG图；而存储模式下，叶子节点将DAO发送至父节点转发至根节点的过程中，父节点要维护一个记录到达各个叶子节点路由的下一跳的路由表。

2　目标函数

目标函数OF（Objective Function）定义了路由度量标准和路由限制条件，即定义了怎样在一个RPL实例中选择父节点和最优路由。OF具体内容包括：如何获取更新度量信息；如何计算每个节点的Rank值；如何选出最佳父节点。

路由度量（metric）是计算路径损失及最短路径的重要标准，用于评估路径代价，一般可以累加，OF需要结合路由度量来寻找父节点并计算最佳路径。IETF发布的RFC6551文档中，阐述了RPL路由协议中可以使用的几种度量标准［10］。以下简单介绍两种以不同的度量标准为准则的目标函数。

2.1目标函数OF0

目标函数OF0是官方文件RFC6552文档中明确规定的，它以跳数（HC）为最佳选路标准，是RPL协议中最简单的目标函数［5-6，11］。

OF0（Object Function Zero）的目标是使节点加入一个连通性足够好的DODAG中，而不要求路由对某一度量做出特殊的优化［12］。假设P为某节点N的父节点，那么OF0中Rank值计算如下：

OF0在运作的时候会根据自己的路由度量计算出一个Rank的阶梯值，然后沿着阶梯值计算Rank的增加值Rank_increase，选择Rank_increase最小的节点作为自己的父节点。但OF0只考虑跳数，在选路的时候选择了跳数最短的路径，每一跳的距离却可能变长，如此以来会降低链路的质量。

2.2目标函数MRHOF

目标函数 MRHOF（The Minimum Rank with Hysteresis Objective Function）是一种带有滞回作用的目标函数。MRHOF的主要目标是当选择路径损耗最小的路径时，避免因为度量的略微变化而引起拓扑的抖动［5-6］。

MRHOF中采用了三种路由度量：跳数（Hop-Count）、时延（Latency）、ETX。ETX表示节点成功发送一个数据包所期望的传输次数，ETX的计算方法有很多，ContikiRPL用EWMA函数来计算ETX［13］：

其中ETXnew指包成功被发送或接收前传输的总次数，一般a设为0.9。MRHOF的Rank值的计算是给ETX乘了一个因子，此处不再具体赘述。MRHOF的运作是在初次加入图中，节点选择Rank值最小的节点作为自己的父节点，当网络中出现了新的备选父节点不会立马更换，比较当前父节点与备选父节点所在路径的开销，当开销的差值大于预先设定的门限值，才会改变父节点，选择新出现的备选父节点。

3　基于普通节点负载均衡的RPL路由协议

RPL网络一般选择能量充足存储能力较强的节点作为Sink节点，目标函数OF0选路时只考虑跳数（HC）的问题，上文所提到的LB-RPL只考虑了多Sink节点间的负载均衡，两者均未对普通节点进行负载均衡，如此若普通节点负载较多，能耗较大，比如在数据采集网络中，若该节点正在参与数据采集的过程，一旦能量耗尽死亡，则会出现监测盲点，甚至会导致网络分裂，部分数据无法传回Sink节点［14］。为此，本文提出了一种基于普通节点负载均衡的RPL路由协议——OLB-RPL，通过修改目标函数，不仅减小了普通节点的能量消耗，而且延长了整个网络的生存时间。

3.1参考度量

本文以节点邻居距离di和节点剩余能量级别REL为依据来计算路径，以寻找最优传感器网络邻居节点范围为路由算法来实现RPL网络中普通节点的负载均衡。

3.1.1节点邻居距离di

本文定义的节点邻居距离针对每个节点，指每个节点的邻居节点集内的节点距该节点的欧式距离。

图2　节点邻居距离示意图

如图2所示为节点i的邻居距离示意图，整个网络初始时刻每个节点的功率发送范围半径为R0，即为节点i的广播域或通信半径。由图中看出周围有节点1～6处于通信半径中，那么这些节点的集合即为当前节点i的邻居节点集，通过测试信号节点i记录各邻居节点到该节的距离即节点邻居距离di：

其中k表示第k个邻居节点。

3.1.2节点剩余能量级别REL

本文引入剩余能量级别REL，一方面避免了网络更新过快带来的抖动，另一方面通过设置每个能级RELi对应的负载数目阈值Fi实现节点的负载均衡，即剩余能量多的RPL节点负载多一些，而剩余能量少的RPL节点负载相对少一些。负载数阈值Fi的值视具体情况而定，会受到节点发送功率、节点密度、剩余能量及邻居距离等因素的影响。设网络节点最初能量为E0，设每个节点有m个能量级别，那么每个等级的能量为Eaverage=E0/m，设每个节点i的当前的剩余能量为Ei_cur，则可以得到某时刻网络中某个节点i的剩余能量级别为［15］：

［Ei_cur/Eaverage］表示大于［Ei_cur/Eaverage］的最小整数。由式（4）得到每个节点的剩余能量级别的取值范围是［1，m］内的正整数。能量级别m的选取对整个优化协议的性能有重要影响，可依据整个网络平均节点密度来设置，根据不同网络对通信质量的要求m可以灵活设置。若m取值较小则不能体现出每个节点剩余能量的差异，根据剩余能量级设定的负载数目不会有明显改变，负载均衡的效果会很不明显［15-17］。

3.2基于普通节点负载均衡的目标函数

3.2.1均衡策略

图3所示为基于普通节点负载均衡的RPL路由协议流程图，算法如下：

S1进行网络的初始化，初始半径为R0，通过测试信号来记录邻居节点及各节点邻居距离di；

S2初始化以后，每个普通节点计算自己的剩余能量级别RELi，并统计自己所携带的负载数目fi；

S3判断当前节点所携带的负载数目fi是否大于当前节点剩余能量级别RELi所对应的负载数门限Fi；

S4一旦fi大于门限值Fi则对当前节点的通信半径Ri调整，减小相应的调整值；

S5若fi小于门限值Fi则当前节点保持通信半径Ri不变，不必进行接下去的负载均衡机制。

上述算法所述通信半径调整值Δ为当前邻居节点集内所有节点的平均节点邻居距离。当通信半径变小以后，邻居节点集中邻居节点的个数变少，父节点断开与多出来的负载节点的连接，这些负载节点可以寻找新的剩余能量级别较大的节点作为父节点。若当前节点在当前剩余能量级内所带负载个数小于相应的负载数目阈值，则节点停留在原来的深度不变，并且不必进行负载均衡机制，等待定时器到下一个时刻更新后再进行条件判断是否进行负载均衡。

图3　基于普通节点负载均衡的RPL路由协议流程图

3.2.2通信半径调整策略

图4所示为某时刻对某节点i当前通信半径Ri调整示意图。为方便描述，图4将树形拓扑暂时画为星形拓扑，且节点i通信半径范围内的节点都是i的叶子节点。某一时刻节点i的通信半径为Ri，调整后的通信半径为Ri+1。起初节点i通信半径范围覆盖的子节点有节点1～n，当检测到节点i的剩余能量级别小于门限值并且i所带负载数目大于阈值时，计算通信半径的调节值Δ：

则新的通信半径为

从新的通信半径覆盖范围看出，只有节点2、4、n位于通信半径范围内，故其他节点不能再以当前节点i作为父节点，而需要重新寻找距离较近并且节点剩余能量级别高的节点为父节点。依次类推每个节点都执行这个策略即可实现负载均衡。

图4　节点通信半径调整示意图

4　仿真验证

本文使用Matlab仿真平台进行验证，将本文的OLB-RPL路由协议与RPL路由协议进行了对比分析。为了验证本文算法的有效性，选取网络死亡节点数、网络平均能量消耗以及网络生存时间为衡量指标进行对比分析。网络死亡节点数随着网络建立后时间延长而增加，增加的快慢程度可反映网络均衡的性能；平均总能量消耗指平均每轮所有节点消耗的能量的总和；网络生存时间指网络中出现第一个节点能量耗尽所用的时间，用轮数表示，为拟合实际通信系统，当剩余能量小于5%时即认为节点失效死亡。

在100×100的区域内随机设置200个传感节点，按区域分为两个DODAG，并手动设置每个DODAG的Sink节点，分别是每个区域内横纵坐标最小的节点。由于无线传感器网络为自组网络，网络初始化时每个节点的初始能量均不同，而一般已选的Sink节点是能量比较充足的节点，考虑到以上情况，将Sink节点的初始能量设为1.00，为了可以突出剩余能量级别的差异，将其余普通节点的初始能量设为0.50～1.00之间的随机值。可根据表1设置其他仿真参量。

表1　仿真参量设置

本文的仿真参量的设置可以根据具体情况及网络大小来灵活配置。仿真中RPL和OLB-RPL的路由更新周期都是96，但由于OLB-RPL是实时更新的，而每一轮能耗过小一般能级不会改变，所以本文仿真中设置每50轮执行一次负载均衡机制进行更新。发送信息能量消耗采用无线通信距离与能量消耗的模型E=δ·d3，δ取值为δ=0.000 1（1/253）。能量级别m的选择对协议的性能有影响，所以m的取值至关重要，本文根据整个传感区域节点的平均密度来选取m的值，本文m取值为10，则RPL共有10个级别。

网络生存时间指网络中出现第一个节点能量耗尽的时间，而网络死亡节点数目也可以体现出算法对整个网络每个节点的负载均衡性能。本文算法OLB-RPL与RPL的网络死亡节点对比如图5所示。

图5　网络死亡节点对比图

图5中数据采集为等间隔采样，因此采样轮数反映了网络生存时间的长短，当出现第一个死亡节点时，轮数越大，网络生存时间越长图5记录了每一轮对应的死亡节点数，由图知，RPL算法中，第一次出现死亡节点是在第74轮，而在本文的OLB-RPL算法中，第一次出现死亡节点是在第204轮，因此，说明本算法的改进较大程度地提高了网络的生存时间；此后的数据采集过程中，同样的数据采集轮数下，采用OLB-RPL算法的网络死亡节点数也小于采用RPL算法的网络产生的死亡节点数，而且随着采集轮数的增加，两种算法产生的死亡节点数的差值进一步增加，当采集轮数为6 000轮时，差值扩大到80个死亡节点数，说明RPL网络死亡节点数目的增长速率大于OLB-RPL。由此证明了OLB-RPL确实可以均衡网络的负载，延长整个网络的寿命。

图6所示为网络平均能量消耗对比图，网络初始化时，由于两种算法采用相同的路由建立过程，因此，初始能耗一致，但此后，本文OLB-RPL算法的仿真中网络平均每50轮执行一次动态路由选择，更新网络路由拓扑，按算法原理，网络中节点负载数大于其能级对应的数量阈值时，节点将减小自己的负载数目到阈值以下，网络得到均衡优化，所以图中出现开始一段骤降的情形；随着时间的推移，能耗才逐渐缓慢增加；最终，本算法建立起的网络在死亡节点、重启节点以及整个网络之间建立起一种动态平衡，能耗也趋于稳定。较之RPL算法，本文OLB-RPL算法的能耗也有明显下降，在实现负载均衡的同时也降低了能耗。

图6　平均能量消耗对比图

图7为网络规模与生存时间关系图，反映了网络规模即网络节点总数与生存时间的关系。为保证较为准确的反映两者关系，避免偶然性的发生，实验中，在某一网络规模下，仿真执行50次就取其对应的生存时间的均值作为参考值，由于采样间隔一致，网络生存时间用采样轮数表示。从图7可以看出，两种算法的对应曲线都大致呈递减趋势，即两者都是随着网络节点数的增加，网络生存时间逐渐减小，这是由于节点数增加，导致网络密度增加，网络中平均每个节点的负载数目增加而引起的节点能耗增加引起的。但相较于RPL路由算法，本文算法OLB-RPL明显改善了网络负载不均衡性，提高了网络生存时间。

图7　网络规模与生存时间的关系

5　结论

本文结合了低功耗有损网络的特点，提出了一种基于普通节点负载均衡的RPL路由协议OLBRPL，改善了网络的负载均衡机制，降低网络能耗。本文提出的算法通过节点能量分级和改变通信半径两个负载均衡办法改进了RPL的目标函数；并通过实验仿真对算法的有效性进行了验证分析，实验数据表明采用本文的算法网络负载得到有效均衡，网络的损耗明显降低，整个网络的生命周期得以延长，而且由此带来的跳数增加和网络抖动可以接受。本改进算法进一步完善了RPL路由协议并在实时监控数据采集等领域的应用具有很重大意义。

［1］ Dohler M，Watteyne T，Winter T，et al.RFC 5548：Routing Requirments for Urban Low-Power and Lossy Networks［S］.Internet Engineering Task Force，2009.

［2］ Winter T，Thubert P，Brandt A，et al.RFC 6550：RPL IPv6 Routing Protocol for Low-Power and Lossy Networks［S］.Internet Engineering Task Force，2012.

［3］ 董立卿.面向LLN的发布订阅系统仿真研究［D］.北京：北京理工大学，2014.

［4］ 朱琳.无线传感器网络RPL路由协议研究与改进［D］.北京：北京交通大学，2013.

［5］ 吴晗.低功耗有损网络路由协议RPL的实现与改善［D］.北京：北京邮电大学，2015.

［6］ 胡婷婷，秦雅娟，高德云.IPv6无线传感网负载均衡路由协议研究［J］.计算机技术与发展，2015（7）：27-30.

［7］ 郑相全，郭伟.自组网中的负载均衡路由协议［J］.计算机科学，2004（11）：40-45.

［8］ Chekka R T；Ting Miao，Ki-Hyung Kim.Implementation of Adaptive Binary Exponential Backoff（ABEB）Algorithm with Dynamical Sizing Buffer for Load-Balanced RPL［C］//Ubiquitous and Future Networks（ICUFN），2014 Sixth International Conf on，2014（l）：562-564，8-11.

［9］ Liu Xinxin，Guo Jianlin，Bhatti G，et al.Load Balanced Routing for Low Power and Lossy Networks［C］//Wireless Communications and Networking Conference（WCNC），2013 IEEE，2013（l）：2238-2243，7-10.

［10］Vasseur J P，Kim M，Pister K，et al.RFC 6551：Routing Metrics Used for Path Calculation in Low-Power and Lossy Networks［S］. Internet Engineering Task Force，2012.

［11］Thubert P.RFC 6552：Objective Fuction Zero for the Routing Pertocal for Low-Power and Lossy Networks［S］.Internet Engineering Task Force，2012.

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

［13］Gnawali O，Levis P.The ETX Objective Function for RPL［J］. 2010.

［14］尹安，汪秉文，胡晓娅，等.无线传感器网络负载均衡路由协议［J］.华中科技大学学报（自然科学版），2010（1）：88-91.

［15］徐卫，刘端阳，暴占兵.基于剩余能量的可分负载WSN能耗均衡研究［J］.计算机工程，2015（6）：66-70.

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

［17］张文祥，马银花.基于梯度和剩余能量的WSN路由算法研究［J］.传感技术学报，2009（8）：1182-1185.

仇英辉（1975-），男，河北定州人，副教授，博士，主要研究方向为智能电网和电力系统通信；

陈玲（1992-），女，宁夏银川人，硕士研究生，主要研究方向为智能电网与电力系统通信，382685891@qq.com。

The RPL Routing Protocal Based on Load Balance of Ordinary Node*

QIU Yinghui*，CHEN Ling
（College of Electrical and Electronic Engineering，North China Electric Power University，Beijing 102206，China）

Traditional RPL routing protocol does not involve the load balance strategies，which is easy to cause local networks over load even leads to the deaths of some nodes.This paper expounds the topological construction and the routing process of RPL routing protocol and some existing Objective Function，then it defines two reference indexes which are the Node Neighbor Distance and Remaining Energy Level.The paper proposes a OLB-RPL routing protocol based on load balance of ordinary node through dividing the energy level and changing the communication radius.At last，we proved that the improved routing protocol achieve the load balancing of the ordinary node through simulation verification，andthenewprotocolreducesthenodeenergyconsumption，andprolongthesurvivalofthewholenetwork.

low-power and lossy networks；RPL routing protocol；remaining energy level；neighbor distance；load balance

TP393.04

A

1004-1699（2016）07-1077-06

项目来源：中央高校基本科研业务费专项资金项目（12MS18）

2016-01-05修改日期：2016-02-18