基于模糊层次分析法的RPL路由优化协议

原 豪,曹亚楠

(1.中国人民解放军61846部队,河北 涿州 072750;2.北京邮电大学网络体系构建与融合北京市重点实验室,北京 100876)

低功耗有损网络LLNs(Low-Power and Lossy Networks)[1-2]是一种广泛应用于城市网络、智能电网等不同领域的网络。LLNs中的节点在存储能力、能耗及处理能力等方面受限。节点之间的链路不稳定。为此,IETF(Internet Engineering Task Force,),提出了专门应用于该类网络的路由协议—RPL(Routing Protocol for Low-power and Lossy Networks)。

RPL是一种距离矢量路由协议[3]。它根据目标函数构建有向无环图DODAG(Destination Oriented Directed Acyclic Graph)[4]。之后再根据相关约束条件和目标函数计算出最优路径。目前,关于RPL的研究在拓扑构建和路由选择时均未综合全面考虑各个方面的路由度量[5](如候选父节点的剩余能量、ETX(Expected Number of Retransmissions)、端到端时延及跳数等)。此外,也有学者提出考虑个别的路由度量,以不同的权重系数侧重不同的路由度量以评估候选父节点(邻居节点)成为偏好父节点的可能性(如文献[6-7])。但各个路由度量的权重系数多是基于专家的个人经验,主观性太强。

可见现有的对RPL的改进仍存在缺陷。为解决上述问题,本文提出基于模糊层次分析法的RPL路由协议—RPL-FAHP(RPL Based on Fuzzy Analytic Hierarchy Process,RPL-FAHP)。RPL-FAHP在节点选择偏好父节点(下一跳节点)时全面综合考虑候选父节点的剩余能量、ETX、端到端时延及跳数。并构建新的复合路由度量及目标函数。同时采用模糊层次分析法[8]确定复合度量中各个路由度量的权重系数。节点根据新提出的复合路由度量和目标函数构建网络拓扑结构和选择路由,进而有效的改善网络各方面的性能。

本文后续部分内容安排如下:第1节介绍低功耗有损网络路由协议RPL;第2节详述新提出的RPL-FAHP协议并对其进行性能分析;第3节进行仿真分析;最后第4节总结全文并简介未来工作。

1 RPL路由协议

RPL主要通过一组ICMPv6[9]消息构建网络拓扑。即节点通过目标函数计算自己的Rank值(在DODAG中节点相对于根节点的位置)并构建有向无环图。该有向无环图有效地防止了路由环路的问题。之后,节点通过目标函数选择最优路由传输数据。且目标函数的设置和节点Rank值的计算方法可根据网络的不同需求灵活变动,从而构建相应的网络拓扑,满足相应的应用要求。以下将详述RPL路由协议。

1.1 ICMPv6

RPL中用到的ICMPv6消息主要有DIO(DODAG Information Object)、DAO(Destination Advertisement Object)、DIS(DODAG Information Solicitation)及DAO-ACK(Destination Advertisement Object Acknowledgement)等。表1简单介绍了这几类ICMPv6消息。

表1 RPL控制消息

1.2 目标函数

目标函数(Objective Function,OF)[10-12]定义了低功耗有损网络中拓扑构建和路径选择的规则,如“最小ETX”。OF可根据不同的应用场景设计不同的规则,满足不同的优化标准。OF主要规定了RPL节点的以下3个规则:①怎样获取和更新路由度量信息;②如何计算自己的Rank值;③怎样选择偏好父节点。

1.3 DODAG

有向无环图(DODAG)[13-14]中所有节点以类似于树状的拓扑结构连接,所有路径均指向DODAG的根(Root)节点。其构建过程如下:

如图1所示,Root节点和普通RPL节点随机分布在网络区域中。DODAG的构建一般从根节点(边界路由器或Sink节点)开始。即Root节点首先向自己的邻居节点广播带有DODAG相关配置信息的DIO消息,其邻居节点如节点1通过DIO获得发送节点的相关信息。若节点1决定加入该DODAG,则节点1成为Root的子节点,之后节点1将自己的相关信息写入DIO中,并向邻居节点广播。节点1的邻居节点2收到来自节点1的DIO消息后,若决定加入该DODAG,则节点2更新来自节点1的DIO消息,并向自己的邻居广播DIO消息,并给节点1回复DAO消息。以此类推,网络中的其他节点逐渐加入DODAG。若网络中仍有节点未收到来自其他节点发送的DIO消息,但该节点想加入该DODAG,如节点4。则节点4可主动向自己的邻居广播DIS消息以请求加入DODAG。DODAG中的节点如节点2收到节点4的DIS消息后,会向节点4发送DIO消息以便节点4加入DODAG。

图1 DODAG的简单构建过程

1.4 现有RPL路由协议存在的问题

RPL及其最新的相关改进协议主要存在以下问题:①在路径选择过程中均未综合全面考虑各方面的路由度量如候选父节点的剩余能量、ETX、端到端时延及跳数等,以至于节点不能选择最优路径传输数据,进而在一定程度上影响网络的性能。②在路径选择过程中,若同时考虑2个或3个路由度量时,各个路由度量的权重系数多是基于专家的个人经验而确定,这样的权重系数确定方法主观性太强,易影响网络性能。③当节点的候选父节点集合中只有一个节点时,仍然执行偏好父节点选择计算过程,造成不必要的额外开销和一定延时。

2 RPL-FAHP

基于上文所述RPL路由协议及其最新的相关改进协议存在的问题,本文提出一种新的适用于低功耗有损网络的路由协议—RPL-FAHP。RPL-FAHP主要包括以下内容:①在进行路径选择时全面综合的考虑了候选父节点的剩余能量、ETX、端到端时延及跳数4个方面的路由度量。更加全面的分析网络中各个节点的性能,选出相对最优的节点为偏好父节点(下一跳节点)。②构造包含上述4种路由度量的复合路由度量和目标函数。③提出采用模糊层次分析法确定复合路由度量中各个路由度量的权重系数。这样的权重系数确定方法更加客观、切合网络实际情况,更好的改善网络性能。④当候选父节点数为1时,提出新的改进方法,进一步减少网络资源消耗,改善网络性能。

2.1 RPL-FAHP考虑的路由度量

①跳数HC(Hop Count)

跳数是指候选父节点到根节点之间的跳数。如式(1)所示,HCmax表示所有候选父节点中到根节点的最大跳数;HC(i)表示候选父节点i到根节点所需的跳数。到根节点所需最小跳数的候选父节点将被选为偏好父节点。

(1)

②节点剩余能量RE(Residual Energy)

如式(2)所示,E0(i)和Enow(i)分别表示节点的最大初始能量和当前剩余能量。利用式(2)可选择剩余能量较多的节点作为偏好父节点,有效地改善网络寿命,且避免网络中局部节点的死亡导致网络重建而引起更大的时延和消耗更多的能量。

(2)

③端到端时延EED(End-to-End Delay)

如式(3)所示,EEDmax表示节点通过某一候选父节点(所有候选父节点中)到根节点之间的路径的最大端到端时延;EED(i)表示节点通过候选父节点i到根节点之间路径所需的时延。如果节点通过某一候选父节点到达根节点所需的时延最小,则选该候选父节点为偏好父节点。

(3)

④ETX

ETX表示在链路上成功传输数据分组所需的传输(重传)次数。如式(4)所示,ETXmax表示节点从某一候选父节点到根节点的路径所需的最大ETX;ETX(i)表示节点从候选父节点i到根节点所需的ETX。若节点从某一候选父节点到根节点的路径具有最小ETX,则选该候选父节点为偏好父节点。

(4)

上述4种路由度量对路径选择均有重要影响,因此,在网络拓扑构建和路径选择时需全面综合考虑上述4种路由度量。为此,本文提出的RPL-FAHP协议全面综合考虑了上述4种路由度量,并提出包含上述4种路由度量的复合度量和目标函数。

2.2 构建复合路由度量及目标函数

如式(5)所示,F(i)为复合路由度量,其中a1,a2,a3,a4为权重系数(用于调整各个路由度量在复合度量中的重要程度),n表示候选父节点总数。

(5)

如式(6)所示,OF为构建的目标函数。

(6)

根据式(5)和式(6),在选择偏好父节点时综合考虑节点剩余能量、端到端时延、跳数及ETX。进而选出最优节点为偏好父节点,有效地改善网络性能。

由式(5)和式(6)可知权重系数在偏好父节点的选择过程中尤为关键。不同的权重系数可导致不同的选择结果。现有的关于复合度量的权重系数的确定多是基于专家的个人经验,主观性太强。为此本文提出的RPL-FAHP协议采用模糊层次分析法确定复合度量中各个路由度量的权重系数。RPL-FAHP结合各候选父节点评价的层次结构、模糊一致性矩阵及层次分析法对各个路由度量的权重因子进行定性和定量的分析,实现各个路由度量最优的权重分配方案,进而选择最优的候选父节点为偏好父节点,有效地改善网络性能。

2.3 FAHP

层次分析法AHP(Analytic Hierarchy Process)[15]是一种简捷、实用的定性与定量分析相结合的决策方法,其关键在于以一定标度把人的主观感觉数量化。它通过把复杂问题中的各种因素划分为相互联系的有序层次;然后依据一定的客观现实判断,把专家意见和分析的客观判断结果直接有效地结合起来,将同一层次元素两两比较的重要性进行定量描述;最后利用数学方法计算所有元素的相对权重的排序向量。

模糊层次分析法FAHP(Fuzzy Analytic Hierarchy Process)是在传统的层次分析法基础上,考虑到人们对复杂事物判断的模糊性,引入模糊一致性矩阵的决策方法。模糊层次分析法很好地解决了AHP判断矩阵的一致性问题。本文在具体采用模糊层次分析法确定各个路由度量权重系数之前,首先作如下假设:

假设第i(i=1,2,3…n)个候选父节点的第j(j=1,2,3,4)个路由度量的归一化值为xij(1≤i≤n,1≤j≤m,m=4),则各个候选父节点的各个路由度量的归一化值的样本集可写为{xij|i=1,2,…,n;j=1,2,…,m},可记为矩阵形式,称为初始判决矩阵,如式(7)所示。

(7)

假设第j个路由度量对应的权重系数为aj(j=1,2 …m),称f(i)(i=1,2…n)为候选父节点的综合评价函数,由路由度量的权重与路由度量归一化值xij加权求和得出,如式(8)所示。

(8)

通过对各个路由度量合理的权重分配a=(a1,a2,a3,…,am),得到所有候选父节点的综合评价值f(i)(i=1,2…n)。则具有最小(或最大)f(i)值对应的候选父节点可优先选为偏好父节点。而权重分配a=(a1,a2,a3,…,am)为一个单位矢量,aj表示第j个路由度量的权重系数,该单位矢量应满足如下约束条件:

(9)

可见偏好父节点的选择为一个约束寻优问题,即在给定初始判决矩阵X且满足式(9)的约束条件下用FAHP求解各路由度量的权重系数,进而计算出n个候选父节点的综合评价值f(i),则偏好父节点即为minf(i)(或maxf(i))对应的节点。

本文的综合评价函数采用式(5),且根据式(6)选择偏好父节点,即选择综合评价函数最小值对应的候选父节点为偏好父节点。以下将详细介绍采用FAHP法求解复合路由度量中各个路由度量的权重系数的过程。

2.4 FAHP确定权重系数

定义1设矩阵R=(rij)n×m,若有0≤rij≤1,则称矩阵R是模糊矩阵。

定义2设矩阵R=(rij)n×m,若有rij+rji=1,则称矩阵R是模糊互补矩阵。

定义3设有模糊矩阵R=(rij)n×m,若对任意k,有rij=rik-rjk+0.5,则称矩阵R是模糊一致性矩阵。

2.4.1FAHP实现步骤

①构建评价层次分析模型

本文建立3层评价层次结构,如图2所示。

②计算图2中准则层的准则权重,确定权重相量

步骤1 建立模糊判断矩阵R=(rij)n×n,rij表示本层次中第i个元素与第j个元素之间模糊关系的相关度(即相对重要程度)。为了能够定量地描述任意两个路由度量之间的相对重要程度,本文采用表2所示的0.1～0.9标度法[8]。

图2 层次化评价模型

标度说明0.5两元素相比较,同等重要0.6两元素相比,一个元素比另一个元素稍微重要0.7两元素相比,一个元素比另一个元素明显重要0.8两元素相比,一个元素比另一个元素重要得多0.9两元素相比,一个元素比另一个元素极端重要0.1～0.4反比较;若元素ri与元素rj比较得到评判rij,则元素rj与元素ri比较得到的评判是rji=1-rij

步骤2 求解模糊一致性矩阵。

为避免矩阵变化中的一致性检验,首先按照式(10)对判断矩阵R求行和:

(10)

再利用式(11)做变换,

(11)

从而得到模糊一致性矩阵R′。

步骤3 利用式(12),对模糊一致性矩阵R′ 进行行和归一化处理,从而求得权重向量a=(a1,a2,…,am)。

(12)

2.4.2 具体实现

①构建模糊判断矩阵R:

②求解模糊一致性矩阵R′:

③对模糊一致性矩阵进行行和归一化处理,从而求得权重向量a=(a1,a2,…,am):

a=[0.221 875 0.290 625 0.240 625 0.246 875]

按照该权重系数分配方案计算各个候选父节点的综合评价值。即将该权重系数带入式(5),即可求得各个候选父节点的综合评价值。再由式(6),即可选出偏好父节点。即选择综合评价函数最小值对应的候选父节点为偏好父节点。

2.5 候选父节点数为1时改进处理方法

若节点只有一个候选父节点,则该节点首先等待一段时间以便接收来自其他节点的DIO消息,以判断是否还有其他节点会成为自己的候选父节点。之后若该节点的候选父节点数量大于等于2,则该节点通过执行RPL-FAHP算法选择偏好父节点。若该节点的候选父节点数量仍为1,则该节点无需执行RPL-FAHP算法,直接将这一个候选父节点选为自己的偏好父节点。这样可在一定程度上减少网络资源的消耗,改善网络性能。

3 仿真实验

本文将RPL-FAHP与最新经典的RPL路由协议(0.8×ETX+0.2×RE和0.6×HC+0.4×RE)通过 OPNET14.5 仿真软件平台进行性能比较。考察的性能参数主要有:平均分组丢失率、平均端到端时延及网络寿命等。

3.1 仿真参数设置

节点随机分布在500 m×500 m的网络环境中。数据分组的到达服从泊松分布。节点的初始能量是0.75 J～1 J之间的随机值。当节点的剩余能量小于其初始能量的5%时,认为节点死亡。其他相关的关键参数如表3所示。

表3 仿真参数设置

表3中E(k,d)[16]可由式(13)计算得出。

(13)

式(13)中的相关参数如表4所示。

表4 E(k,d)的参数设置

3.2 仿真结果分析

①平均分组丢失率

图3显示了RPL-FAHP、0.8×ETX+0.2×RE和0.6×HC+0.4×RE在不同节点密度下的平均分组丢失率。可见在不同节点密度下RPL-FAHP的平均分组丢失率均明显低于0.8×ETX+0.2×RE和0.6×HC+0.4×RE。表明RPL-FAHP通过综合考虑各方面的路由度量,并采用FAHP确定各路由度量最优的权重系数,进而求出最优偏好父节点传输数据。所以RPL-FAHP可明显降低分组丢失率,改善网络性能。

图3 平均分组丢失率

②平均端到端时延

图4显示了RPL-FAHP、0.8×ETX+0.2×RE和0.6×HC+0.4×RE在不同节点密度下的平均端到端时延。可见在不同节点密度下RPL-FAHP的平均端到端时延均明显低于0.8×ETX+0.2×RE和0.6×HC+0.4×RE。表明RPL-FAHP可明显降低网络时延。

③平均端到端时延

图5可看出:在不同节点密度情况下,RPL-FAHP平均存活的节点数大于0.8×ETX+0.2×RE和0.6×HC+0.4×RE。表明RPL-FAHP综合考虑各个路由度量,全面综合评价候选父节点,从而选择最优节点为偏好父节点,改善网络性能。

图4 平均分端到端时延

图5 平均存活节点数

4 结束语

为使低功耗有损网络路由协议(RPL)在拓扑构建及路由选择时综合全面考虑各方面的路由度量,且更加客观的确定各个路由度量的权重系数,本文提出一种新的基于模糊层次分析法的RPL路由协议—RPL-FAHP。RPL-FAHP在选择偏好父节点时同时考虑节点剩余能量,端到端时延、跳数及ETX共4种路由度量;并构建新的复合路由度量和目标函数;同时采用模糊层次分析法更加客观的确定复合路由度量中各个路由度量的权重系数。进而求得各个候选父节点的综合评价函数值。最小的综合评价函数值对应的候选父节点即为偏好父节点。仿真实验表明RPL-FAHP在分组丢失率、平均端到端时延、网络寿命等方面均优于现有的较新的典型的算法(0.8×ETX+0.2×RE和0.6×HC+0.4×RE)。

在未来的工作中,拟通过研究学习其他的权重系数确定方法进一步优化路由度量的权重系数,构建更加合适的复合度量和目标函数进一步优化低功耗有损网络的性能。