LLN中基于负载均衡的单路径路由协议

陈苏海，党向盈

(1.徐州工程学院 信电工程学院，江苏 徐州 221000；2.中国矿业大学 信息与控制学院，江苏 徐州 221000)

0 引 言

低功耗有损网络(low power and lossy networks，LLN)[1-5]通过网关或者边界路由器直接与互联网进行数据交互，使得LLN拥有较好的互操作性和灵活性。因此，LLN在工业控制、智能家居和医疗保健等领域拥有较好的应用前景。考虑到LLN广泛的应用场景，国际互联网工程任务组提出了一种适用于LLN网络的IPv6路由协议(IPv6 based routing protocol for LLN，RPL)[6,7]。

当前，学术界已对单路径RPL路由协议展开大量研究。文献[8]仅将传输跳数作为选择最优父节点的路由度量，而未考虑无线链路质量，可能导致网络中链路质量不佳的节点被选作为父节点，从而使数据包的丢包率上升，增大节点的能耗。为了避免将无线链路不佳的节点选作父节点，文献[9]中将数据包的期望传输次数作为选择父节点的判据，却忽略了节点的剩余能量，极有可能将剩余能量不足的节点选作当前父节点，从而加快了此类节点的能量消耗速率，缩短了网络生存时间。为了避免将剩余能量不足的节点选作父节点，文献[10]中将节点的剩余能量作为选择父节点的路由判据，可能导致无线链路质量较差而拥有充足剩余能量的节点被选作为父节点，增加了其子节点丢包重传的次数，从而降低了网络吞吐量和增加了节点能耗。为了避免文献[9]和文献[10]中存在的问题，文献[11]中综合考虑了节点剩余能量和无线链路质量。然而，由于文献[11]未将节点当前缓存占用率考虑在内，一旦遇到突发紧急情况需要传输大量数据时，容易产生网络拥塞，从而严重影响数据的传输。文献[12]仅将节点的缓存占用率作为路由度量，而未考虑节点间的无线链路质量，从而加剧了节点丢包重传的能耗。

上述针对单路径RPL路由协议的研究主要存在以下两个方面的不足：①在网络拓扑初始化的过程中，路由度量的选择过于单一，无法有效地实现网络负载均衡，从而不能延长网络寿命；②在选择最优父节点的过程中，仅仅考虑一跳范围内的数据传输代价而未考虑整条路径上的数据传输代价影响了最优父节点的选择，导致无法有效地提升网络各方面的性能。

为了尽可能地解决上述所存在的问题，本文提出了一种基于负载均衡的单路径LLN路由协议(load balance-based single path routing protocol for LLN，LB-RPL)，并对该协议的具体操作过程进行了详实的分析以及对该协议的网络性能进行了模拟仿真对比和验证。

1 RPL路由构建原理

在创建面向目的地有向无循环图(destination oriented directed acyclic graph，DODAG)的过程中，RPL路由协议制定了3种常用的控制消息：DODAG信息对象消息(DODAG information object，DIO)、面向目的地有向无循环图请求消息(DODAG information solicitation，DIS)以及面向目的地有向无循环图目的地通告消息(destination advertisement object，DAO)。DIO消息的主要功能是为了创建上行路由和维护网络拓扑的连通性，由sink节点发起；在DODAG构建过程中，DAO消息主要用于回应DIO消息，从而完成下行路由的构建；DIS消息主要用于路由请求，链路故障节点或是新节点均可通过广播DIS消息可以主动请求加入到DODAG中。DODAG构建流程如图1所示。

图1 DODAG构建流程

DODAG的构建具体步骤如下：①sink节点向其邻居节点周期性的广播DIO消息；②sink节点的邻居节点A成功接收到sink节点广播的DIO消息之后，将sink节点作为父节点，并回复包含自身路由前缀信息的DAO消息；③节点A重复sink节点的操作过程，节点B重复节点A的操作过程；④由于节点C在一段时间内未接收到其邻居节点广播的DIO消息，于是主动广播DIS消息；⑤节点B接收到节点C广播的DIS消息后，向节点C单播一个DIO消息；⑥节点C接收到DIO消息后，向节点B回复一个DAO消息；⑦节点A和节点B转发该DAO消息直至根节点，至此DODAG构建完成。

2 LB-RPL路由协议

针对LLN中现有单路径路由协议在网络拓扑构建过程中考虑的路由度量过于单一，以及在选择最优父节点时仅依据一跳范围内的数据传输代价而无法有效地均衡节点能耗和延长网络寿命等问题，LB-RPL路由协议中主要提出了以下3种优化策略：①在备选父节点的选择过程中，对选择备选父节点的条件进行限制，从而选出合适的最优父节点；②在路由度量值的计算过程中，综合考虑多种路由度量，避免单一路由度量对网络性能所带来的影响；③在选择最优父节点的过程中，考虑整条路径上的数据传输代价，最终选择数据传输代价相对较小的备选父节点作为最优父节点。

2.1 备选父节点的选择

在DODAG的构建过程中，为了降低单一路由度量对最优父节点的选择所产生的影响，在选择备选父节点时需满足以下3个限制条件：第一，节点与其备选父节点之间的无线链路质量应高于预设的链路质量阈值，从而避免选择无线链路质量较差的节点作为父节点。在本文中，无线链路质量低于0.7的节点将不能作为备选父节点；第二，为了使节点的能耗均衡，剩余能量较低的节点(低于能量阈值)不能作为备选父节点。在本文中能量阈值为节点初始能量的20%；第三，备选父节点的缓存占用率应低于预设的网络拥塞阈值，从而避免选择高负载的节点作为父节点。在本文中网络拥塞阈值设定为节点最大缓存的80%。

在网络拓扑初始化过程中，网络中每个节点为了获知彼此之间的内存空间占用情况、剩余能量和链路质量，分别将上述3种信息添加到周期性广播的DIO消息中。因此，节点在选择备选父节点时，只需依次判断其邻居节点的上述3种信息是否满足要求。若满足要求，则将该邻居节点作为备选父节点；反之，则将该DIO消息丢弃。图2所示为LB-RPL路由协议选择备选父节点的流程。

图2 备选父节点的选择

2.2 路由度量值的计算

在网络构建过程中，当节点获知其所有备选父节点信息之后，计算与各个备选父节点之间的路由度量值。在路由度量值的计算过程中，为了有效地避免选择单一路由度量对网络性能所产生的不良影响，因此需要将多种路由度量进行有效地融合。下面以网络中的节点i为例，对多种路由度量有效融合的实际操作步骤如下：

步骤1 根据节点i的当前剩余能量计算其期望寿命，从而有利于避免潜在子节点选择剩余能量非最佳的备选父节点作为最优父节点。节点当前期望寿命[13]可由如下几个过程获取：

(1)统计节点i的数据包发送速率，如式(1)所示。其中，Tgen(i)表示节点i的数据包发送速率，Tj表示其子节点j的数据包发送速率

(1)

(2)计算节点i将在一段时间内所收集的数据包成功发送至其最优父节点k大致所需要发送的平均次数，如式(2)所示。其中，ETX(i,k)表示节点i成功发送单个数据包到达其最优父节点k大致所需要发送的平均次数

Ni=Ti×ETX(i,k)

(2)

(3)计算节点i将在一段时间内所收集的数据包成功发送至其最优父节点k大致所耗费的时间，如式(3)所示。其中，data_rate表示节点i的数据包传输速率

(3)

(4)计算节点i将在一段时间内所收集的数据包成功发送至其最优父节点k的能量大致消耗速率，如式(4)所示。其中，Ptx(i)被定义为节点i的数据包发送功率

(4)

(5)最后，依据节点i的当前剩余能量以及能量消耗速率便可计算出其期望寿命，如式(5)所示。其中，Eres(i)表示节点i当前剩余能量

(5)

步骤2 计算节点i的缓存占用率，从而有利于避免节点i的下游节点选择高负载的备选父节点作为最优父节点

(6)

式中：buffer_occupancyi反映了节点i的缓存空间被占用的情况，buffer_size被定义为节点i的缓存空间大小。

步骤3 在LLN网络创建过程中，节点i根据所统计子节点发回的DAO消息的个数便可获得当前处于连接状态的子节点数量，从而有利于避免节点i的下游节点选择子节点数量较多的备选父节点作为最优父节点。

步骤4 节点i将其期望寿命、缓存占用率和当前子节点数量相关度量信息添加到DIO消息中，并广播携带上述度量信息的DIO消息。

步骤5 节点i的邻居节点从接收到的DIO消息中提取出节点i的期望寿命、缓存占用率以及其当前子节点数量后，根据式(7)计算与节点i之间的路由度量值，路由度量值的大小能够反映出节点的数据传输代价，即路由度量值越大，节点的传输代价相对越小

(7)

2.3 最优父节点选择策略

在DODAG的构建过程中，在选择最优父节点时综合考虑整条路径的数据传输代价。通过计算整条传输路径上的总度量值大小判断备选父节点的优先级。总度量值越大，备选父节点的优先级越高，最终选择优先级最高的备选父节点作为最优父节点。最优父节点选择策略的具体操作步骤为：

步骤1 当sink节点发起DODAG的构建时，其一跳范围内的邻居节点N选择根节点作为最优父节点，并计算出度量值，且将度量值的大小添加到周期性广播的DIO消息中。

步骤2 节点M接收到其邻居节点周期性广播的DIO消息后，根据备选父节点选择策略选出备选父节点。

步骤3 节点M根据DIO消息中携带的相关信息计算与所有备选父节点之间的度量值，然后根据式(8)计算每条路径上的总度量值

(8)

式中：Metric(M→N→sink)表示节点M通过其备选父节点N到达sink节点的总度量值，φ表示节点M的网络深度值。

步骤4 节点M根据计算所得的每条路径上的总度量值的大小选择最优父节点，即选择总度量值最大的备选父节点作为最优父节点。如果计算得到一个节点拥有两个总度量值相同的备选父节点，则选择度量值方差较小的备选父节点作为最优父节点。

步骤5 节点M将当前总度量值添加到周期性广播的DIO消息中，其下游节点接收到该DIO消息后重复节点M的处理过程，直至网络构建完成。

如图3所示，节点I有两个备选父节点D和E，即节点I到sink节点有两条路径，分别为I→D→A→sink和I→E→B→sink。而这两条路径的总的度量值分别为17和15，根据最优父节点选择策略，则节点I选择备选节点D作为最优父节点。

图3 基于LB-RPL路由协议的网络拓扑构建

3 实验及结果分析

使用OPNET14.5仿真工具进行平台的搭建和仿真，将本文提出的LB-RPL路由协议与RPL-OF0[8]和ETX-RPL[9]路由协议从以下4个方面进行对比和分析，分别为数据包投递率、网络生存时间、平均端到端传输时延和根节点平均吞吐量。

3.1 仿真环境及参数设置

在300 m×300 m的模拟仿真场景中创建网络规模大小分别为10、30、50、70、90和110的LLN网络，且每个场景中的所有节点均随机放置。除此之外，网络中每个节点均工作在存储模式下，且初始能量相同。在网络创建初期，所有节点均采用静态模型，即位置一旦被确定将不再进行改变。仿真中用到的其它参数见表1。

表1 主要仿真参数

3.2 统计量定义

(1)数据包投递率

数据包投递率(packet delivery ratio，PDR)被定义为从源节点成功传输到根节点的数据包数量与源节点发送数据包的比值，计算公式为

(9)

式中：Pi表示成功到达根节点的数据包数量，Dj表示源节点发送的数据包数量。

(2)网络生存时间

网络生存时间是指在网络拓扑初始化之后网络中出现第一个能量耗尽的节点所耗费的时间，计算公式为

TL=Td-T0

(10)

式中：Td表示网络中出现第一个能量耗尽节点的时刻，T0表示网络开始运行的时刻。

(3)平均端到端时延

平均端到端时延被定义为所有从源节点成功传输到达根节点的所有数据包的端到端传输时延总和与数据包个数的比值，计算公式为

(11)

式中：Ti表示第i个数据包到达根节点的传输时延，Dj表示第j个源节点成功传输到达根节点的数据包数量。

(4)根节点平均吞吐量

根节点平均吞吐量被定义为在一定时间内根节点成功接收到的总的数据包比特数，计算公式为

(12)

式中：ps表示成功到达根节点的数据包比特数，T表示网络运行的时间。

3.3 仿真结果分析

3.3.1 数据包投递率

由图4可知，3种路由协议的PDR均随着网络规模的扩大呈下降趋势。但是，LB-RPL路由协议的PDR明显高于RPL-OF0和ETX-RPL路由协议，分析其主要原因有以下两点：①在DODAG构建的过程中，LB-RPL路由协议在计算度量值的过程中综合考虑了多种路由判据，譬如链路质量、节点缓存占用率和中继节点当前子节点数量，能够最大化地实现负载均衡，从而有效地降低了节点因高负载而导致的丢包数量；②LB-RPL路由协议在选择最优父节点的过程中依据整条路径的数据传输代价，能够有效地降低数据包从源节点到达sink节点整条路径上的丢包概率。

图4 数据包投递率

3.3.2 网络生存时间

从图5中可以发现，随着网络规模的扩大，RPL-OF0、ETX-RPL和LB-RPL路由协议的网络生存时间均逐渐降低，但LB-RPL路由协议的网络生存时间明显高于RPL-OF0和ETX-RPL路由协议。分析其主要原因有以下3点：①在选择备选父节点的过程中，LB-RPL路由协议将节点当前剩余能量和节点当前缓存占用率进行了有效地融合，其中考虑节点当前剩余能量能够避免将剩余能量不足的节点选作为备选父节点，而考虑节点的缓存占用率，能够延长高负载节点的能耗；②LB-RPL路由协议在计算度量值的过程中综合考虑多种路由判据能够有效地提高数据包的投递率，从而降低了数据包因丢包而重传的能耗；③LB-RPL路由协议依据整条路径的数据传输代价进行最优父节点的选择，能够有效地降低整条路径上的节点能耗。

图5 网络生存时间

3.3.3 平均端到端时延

图6表明，LB-RPL路由协议的平均端到端时延在随着网络规模的扩大的过程中均低于RPL-OF0和ETX-RPL路由协议。分析其主要原因有以下3点：①在网络拓扑的组建过程中，LB-RPL路由协议将节点当前缓存占用率有效地考虑到其中，能够有效地降低重负载节点出现的概率，从而缩短了排队时延；②LB-RPL路由协议通过结合多种路由判据能够最大化地实现网络负载均衡，提高了数据包的投递率，从而降低了节点因丢包重传而耗费的时间；③在选择最优父节点的过程中，LB-RPL路由协议依据整条路径的数据传输代价能够有效地降低数据整体端到端传输时延。

图6 平均端到端时延

3.3.4 根节点平均吞吐量

由图7可知，根节点的平均吞吐量随着网络规模的扩大均逐渐增大，其中LB-RPL路由协议的根节点平均吞吐量明显高于RPL-OF0和ETX-RPL路由协议。分析其主要原因在于LB-RPL路由协议在DODAG的构建过程中将多种路由判据有效结合能够最大化地均衡网络负载，降低了数据包的丢包率；其次，在计算路由度量值的过程中，LB-RPL路由协议将节点当前缓存占用率考虑其中，从而对数据包的排队时延有缩减趋势，以及降低了数据包因缓存而导致丢包重传的次数，故其根节点平均吞吐量相比较于RPL-OF0和ETX-RPL路由协议有所提高。

图7 根节点平均吞吐量

4 结束语

本文针对LLN中现有单路径RPL路由协议在DODAG构建过程中，仅考虑一跳范围之间的数据传输代价而未考虑整条路径上的传输代价，导致不能有效地均衡节点能耗以及延长网络寿命等问题，提出一种基于负载均衡的单路径LLN路由协议(LB-RPL)。该协议从3个方面进行了改进：首先，在选择备选父节点的过程中对无线链路质量、节点剩余能量和缓存占用率进行限制；其次，在度量值的计算过程中将多种路由判据有效地结合，旨在避免单一路由判据对网络性能产生的影响；最后，依据整条路径上的数据传输代价进行最优父节点的选择。仿真结果表明，LB-RPL路由协议在均衡节点能耗方面有一定的改善，且能够有效地延长网络生存时间以及相应地提高数据传输的可靠性。在未来的工作中，我们将研究LLN中基于负载均衡的多路径RPL路由协议。