郭戈

摘 要：基于6LoWPAN标准的RPL协议实现了低功耗有损网络上运行IPv6协议的节点间路由功能，但是现有的RPL协议并未包含拥塞避免机制。文中提出一种拥塞感知负载均衡多径RPL协议，将缓冲区占用率引入RPL协议，实现拥塞感知，并采用多径传输的方式进行负载均衡。仿真结果表明，协议达到了提高数据传输成功率、平衡节点能量消耗的目的。

关键词：低功耗有损网络；RPL路由协议；负载均衡；拥塞避免

中图分类号：TP393 文献标识码：A 文章编号：2095-1302（2018）09-00-04

0 引 言

物联网技术是新一代信息革命的核心技术之一，它基于低功耗有损网络（Low Power and Lossy Networks，LLNs）实现物与物的通信，能够极大地拓展人类感知与控制的范围。低功耗有损网络由许多能量与计算能力有限的节点组成，节点间通过低速、不稳定的无线或有线网络进行连接。由于IP协议对内存与带宽的需求较高，以往被认为不适合直接在低功耗有损网络上使用，需要ZigBee等专有协议通过复杂的应用网关转换，才能实现低功耗有损网络节点接入互联网的功能。但6LoWPAN[1]标准的制定改变了这种状况，它基于IEEE 802.15.4[2]运行轻量级IPv6协议栈，实现了低功耗有损网络节点无缝接入下一代互联网的目标，为物联网的大规模应用奠定了坚实的基础。

由于传统的路由协议都不适合低功耗有损网络，IETF的ROLL工作组制定了RPL[3]协议，以满足低功耗、低速率、链路动态变化等低功耗有损网络的路由需求。RPL是一种距离向量协议，以一个Sink节点为根，通过某种目标函数（Object Function，OF）把网络中的节点组织到一个或多个有向无环图（Destination Oriented Directed Acyclic Graph，DODAG）中，从而实现节点间数据的传输。DODAG以类似树结构的形式进行构造，在一组邻居节点中选择一个作为其最优父节点（preferred parent），并将其设为默认路由，把数据传给根Sink或者其他节点。

但是RPL协议标准并未包含拥塞避免机制。当某个节点数据包到达的速度超过其转发出去的速度时，便会产生拥塞。在使用RPL协议构建的网络中，拥塞多发生于两处节点。一处是距离Sink节点较近的节点，这是由于RPL协议采用类似树形的结构构建DODAG，因此靠近根的节点有最多的数据转发量；另一处是临近事件突发处的节点，由于需要转发大量检测到的突发事件信息而产生拥塞。严重的拥塞会导致大量数据包的丢失与重传，节点的能量被浪费，网络的生存时间会因此而缩短。

此外，由于DODAG中每个非根节点只选择一个最优父节点将其作为发往Sink节点数据的唯一途径，因此会导致子节点较多的节点承担更大的数据转发压力。这种负载不均衡的状况使得某些节点因为能量消耗过大而过早死亡，可能造成网络空洞甚至网络分区。

为此，本文提出一种RPL改进算法，即拥塞感知负载均衡多径RPL（Congestion Awareness Load Balanced Multipath RPL，CALBM-RPL）协议。该算法将缓冲区占用率引入RPL协议，实现拥塞感知，并采用多径传输的方式进行负载均衡，从而达到提高数据传输成功率（Packet Delivery Ratio，PDR）、平衡节点能量消耗的目的。

1 RPL概述

RPL协议包含用来与其他网络相连接的根节点（Sink节点）、用以将数据转发给根节点的中间节点以及叶子节点。RPL可對网络变化做出快速反应，能在通往根节点的缺省路径无法连通时选取一条替代路径。

RPL使用基于ICMPv6的DIO（DODAG Information Object，DIO），DIS（DODAG Information Solicitation，DIS）及DAO（Destination Advertisement Object，DAO）三种控制消息实现DODAG的构建。DODAG根节点首先使用DIO控制消息向周围邻居进行广播，宣布自己作为父节点。其他节点收到广播后，会根据其中包含的信息计算自身的rank值，产生新的DIO消息继续向外广播。节点在收到多个DIO消息时，会使用相应的OF进行计算比较，选择结果值最小的节点作为自己的最优父节点，并根据该节点的rank和到达的路径开销得到自身的rank值。这一过程持续进行，最终将网络中所有可达节点包含进DODAG中，每个加入的节点便拥有了送往Sink的上行路径。

为了获得自Sink节点至其他节点的下行路径，每个节点在选择出最优父节点后，向最优父节点发送DAO控制消息。收到DAO控制消息后，父节点将该子节点加入到路由表（存储模式）或包含在下一个DAO消息中（非存储模式），并把新生成的DAO消息继续向上传递，直至Sink节点。

如果某个节点在一段时间内未收到DIO消息，那么广播一个DIS消息以请求加入DODAG。收到该消息的邻居节点会重置DIO时钟以加快DIO消息的发送频率。为了节省重复发送DIO消息的能量消耗，RPL使用涓流时钟（Trickle Timer）控制DIO的发送频率。每收到一个显示网络状态稳定的DIO，该时钟就以几乎加倍的数量延长定时时长，以降低发送频率，减少发送DIO包数量。而一旦发现网络状态发生改变，如最优父节点的rank值改变或与其失联，则该时钟会重置为最小值，提高DIO的发送频率，使网络尽快收敛。

2 相关工作

文献[4]提出一种通过均衡负载延长网络生命周期的多径路由机制。在该机制中，网络被划分成多个区域。Sink节点向所有其他节点发送区域的信息，每个节点收到后都会根据自己的位置加入一个区域，并把自己的剩余能量和流量情况发送给Sink节点。Sink节点计算每个区域的剩余能量后，通知信息源节点沿着最少被使用（即剩余能量最多）的多个区域发送数据。这种多径传输的机制实现了流量和能量的均衡。

文献[5]提出一种负载均衡RPL（LB-RPL）协议，用以解决RPL中由于缓冲区有限导致的丢包问题。当一个节点检测到网络负载增大，缓冲区占有率超过门限值后，便暂缓DIO消息的发送。拥塞的程度越高，暂缓的时间越长。这就使得该节点的子节点因为长时间收不到DIO消息而切换其最优父节点，从而将流量均衡分配。但是该机制一方面可能会导致“羊群效应”（Herding Effect），即多个子节点同时切换到另一个父节点而将新的父节点拥塞；另一方面，因为采用涓流算法发送的DIO消息间隔周期可能会长至数分钟之久，所以不能及时传递拥塞情况。

文献[6]提出一种针对移动Sink的基于DAG的多径路由协议，该协议使得节点在与主Sink节点的连接丢失时，可通过替代路径连接到其他Sink节点。替代路径的寻找采用被动按需的方式，当一个节点检测到与主Sink节点连接失效时，会向其他Sink节点发起连接请求，一个新的DODAG会随之建立，进而实现向Sink数据传输的恢复。

文献[7]提出的多径RPL协议工作于IEEE 802.15.4之上。该协议的目标是为数据传输提供QoS服务。它采用跨层设计的方式实现，构造DAG的过程使用由IEEE 802.15.4层提供的链路质量信息。普通数据仍然使用单径转发，只有对延迟敏感的高优先级数据才会以多径的方式进行转发，以保证传输质量。

文献[8]提出一种帶时间因子的拥塞避免多径路由协议。由于针对危险气体检测的应用场景对数据传输的时延要求非常严格，因此该协议设计了一种新的路由度量，使发送至Sink节点的时延减到最小。综合考虑该度量与ETX，rank值及接收数据包的个数，计算路径的权重大小，将其作为多径路由时的选择依据。

3 CALBM-RPL协议

如前所述，当数据包到达的数量超过节点发送能力时，便会产生拥塞。距离Sink节点较近的节点、子节点数目较多的节点以及突发事件发生处周边的节点，都会因为转发的数据包较多而发生拥塞。为了降低拥塞对网络性能带来的影响，需要将节点的拥塞状况通知其周边的节点，从而能让一个子节点在其最优父节点发生拥塞时选择其他路径转发数据包。

本文CALBM-RPL协议分成拥塞检测和拥塞避免两个部分。

3.1 拥塞检测

CALBM-RPL协议将缓冲区的占用率作为拥塞状况的指标。每个节点设定一个用以计算缓冲区占用率的定时器，定时器的时长设为发送DIO消息的最小间隔值Imin（4 s）。每当一个数据包到达时，节点发送缓冲区的大小就会被累加。定时器到期时，这段时间内的缓冲区平均占用率便会计算出来。正常情况下，该指标数值会在发送DIO消息时一并捎带给周边的邻居节点，以避免产生额外的通信负担。然而，如果缓冲区占用率超过了设定的拥塞门限值，那么一个用于紧急通知拥塞发生的DIO消息会被马上发出，以使其子节点能够尽快调整转发路径。之所以使用平均占用率而非即时占用率，是为了避免出现持续时间较短的通信量陡变的情形导致网络震荡。

当拥塞发生时，发送缓冲区被占满，随后待发的数据都会被丢弃。由于节点发送的所有数据包共用同一块缓冲区，因此用来通知周边节点已经发生拥塞的DIO消息也会被丢弃。这种不分优先级的丢弃策略会导致子节点继续向拥塞的父节点发送数据，继而导致拥塞的进一步恶化，更多的数据被丢弃。为了避免这一问题，CALBM-RPL协议中将DIO消息设置为高优先级。因为前者包含了最新的缓冲区占用率，所以一旦有DIO消息发送，若缓冲区已被占满，且已经有一个待发送的DIO消息，则将用新的DIO消息替换掉旧的；若缓冲区中无目的地址为广播地址的DIO消息，则删除最后一个进入队列的数据包，并将其空间分给DIO消息，保证DIO通知消息不会因为拥塞而被丢弃。

3.2 拥塞避免

每个节点在收到邻居节点发来的DIO消息时，将其中的缓冲区占用率记录在该邻居节点的属性中。

每个节点在发送数据包时，首先判断该数据包的下一跳节点是否为自己的最优父节点，若是，则检查最优父节点的缓冲区占用率是否超过拥塞门限。如果超过，则寻找缓冲区占用率小于拥塞门限的次优父节点。找到后，子节点会将该节点设为数据包的下一跳并进行发送。如此，协议便增加了发送路径，实现多径传输与负载均衡，从而达到提高吞吐量与数据传输成功率的目的。

4 性能评估

4.1 仿真模型及参数

为了测试CALBM-RPL协议的性能，在Cooja[9]模拟器上进行仿真与评估。Cooja是运行于Contiki[10]之上基于Java编写的无线传感网络模拟器，是一个能在真实硬件设备上运行的物联网微操作系统，具有开源、可移植、多任务、支持6LoWPAN等特性，在科研和商用领域都有着广泛应用。本文采用Cooja模拟环境的相关参数见表1所列。

考虑到真实应用中的不同场景，分别在格状排列和随机排列两种场景中进行协议测试。两个场景的拓扑结构分别如图1、图2所示。两种场景中都有三种类型的节点：1个Sink节点，位于网络一角；25个低频率发送数据节点，每分钟分别向Sink节点发送1个数据包；5个高频率发送数据节点，用以模拟由于检测到某种事件的发生而向Sink节点密集发送通知信息，位于网络中Sink节点的对角处，分别在0.5个/s，

1个/s，2个/s，4个/s的发送频率下进行测试。为了保证结果的准确性，每种测试都以随机的初始种子值运行10次然后取平均值作为实验结果。

为了全面评估CALBM-RPL协议，分别从传输成功率、端到端时延和能量消耗等三个方面进行分析，并与标准RPL进行性能比较。为了简化描述，格状拓扑在性能对比图中以“G-”标注表示，随机拓扑的标注则以“R-” 标注表示。

4.2 仿真结果分析

4.2.1 数据传输成功率

Sink節点在两种场景不同发送频率下接收数据包的传输成功率如图3所示。从图3的数据可以看出，CALBM-RPL协议在两种场景中传输成功率都优于标准RPL协议。其中，在格状拓扑下数据包以2个/s的频率发送时，CALBM-RPL较标准RPL高出54%。同时，格状拓扑中由于替代的路径更多而比随机拓扑拥有更好的传输成功率，并且伴随事件检测节点发送频率的升高，传输成功率会由于拥塞逐渐严重而相应降低。

4.2.2 端到端时延

在事件监测节点数据包以4个/s的频率发送时，数据到达Sink节点的端到端时延情况如图4所示。由图4可知，两种场景下CALBM-RPL协议较标准RPL的传输时延更大，因为最优父节点发生拥塞后，数据要选择次优父节点进行转发，导致这些数据需要经过ETX较差的链路或者更多的跳数才能到达Sink，从而增加了时延。这是提高数据传输率所付出的代价。

此外，格状拓扑场景下平均端到端时延明显少于随机拓扑场景，这是由于随机场景下传感节点距Sink节点的跳数更多所致。

4.2.3 能量消耗

在不同发送频率下两种协议每比特平均传输能耗如图5所示，该指标通过在模拟时间内总的能耗除以总发送及接收比特数计算而得。由图5可知，虽然CALBM-RPL协议会在拥塞发生时以多路径的方式进行传输，但是并未带来能量消耗的大幅提高，反而比标准RPL还要略低一点。这是由于CALBM-RPL较高的传输成功率使其丢失的数据包相对较少，从而减少了中间节点转发数据时由于丢失导致的能量浪费。

5 结 语

本文提出拥塞感知负载均衡多径RPL，该算法将缓冲区占用率引入数据转发过程，在最优父节点的缓冲区占用率超过设定门限值后触发负载均衡机制，将一定的流量分发给次优父节点，通过增加路径减轻最优父节点的转发压力，从而达到提高PDR和网络性能的目的。仿真结果表明，该协议的数据传输率明显提升，并且保持能量消耗基本不变，但同时也付出了端到端时延增加的代价。因此，该协议适用于需要高传输率而对时延性能要求不严的场景。未来计划进一步扩展该协议功能，使其支持移动节点和多Sink场景。

参考文献

[1] KUSHALNAGAR N，MONTENEGRO G，SCHUMACHER C.IPv6 over Low-Power Wireless Personal Area Networks（6LoWPANs）：overview，assumptions，problem statement，and goals [J].Heise Zeitschriften Verlag ，2007.

[2] IEEE 802.15.4-2011：IEEE standard for local and metropolitan area networks – Part.15.4：Wireless Medium Access Control（MAC）and Physical Layer（PHY）Specifications for Low-Rate Wireless Personal Area Networks（LR-WPANs）[S].Standard for Information Technology，2011.

[3] WINTER T，THUBERT P，BRANDT A，et al.RPL：IPv6 routing protocol for low power and lossy networks，RFC 6550[S].IETF，2012.

[4] LI B，CHUANG P.Efficient multimedia transmission in wireless sensor networks[C]// Intelligent Signal Processing and Communications Systems（ISPACS），Taiwan，2012.

[5] LIU X，GUO J，BHATTI G，et al.Load balanced routing for low power and lossy networks[C]// Proceedings of Wireless Communications and Networking Conference（WCNC），China，2013.

[6] XU G，LU G.Multipath routing protocol for DAG-based WSNs with mobile sinks[C]// Proceedings of the 2nd International Conference on Computer Science and Electronics Engineering（ICCSEE），China，2013.

[7] PAVKOVI B，THEOLEYRE F，DUDA A.Multipath opportunistic RPL routing over IEEE 802.15.4[C]// Proceedings of the 14th ACM International Conference on Modeling，Analysis and Simulation，USA，2011.

[8] TANG W，MA X，HUANG J，et al.Toward improved RPL：a congestion avoidance multipath routing protocol with time factor for wireless sensor networks[J].Journal of sensors，2016（7）：1-7.

[9] OSTERLIND F，DUNKELS A，ERIKSSON J，et al.Cross-Level sensor network simulation with COOJA[C]// Local computer networks，proceedings 2006 31st IEEE conference，2006.

[10] DUNKELS A，GRONVALL B，VOIGT T.Contiki - a lightweight and flexible operating system for tiny networked sensors[C]// Proceedings of the IEEE workshop on embedded networked sensors，USA，2004.