面向输电线故障信息传输的多播路由

陈 岩，李晓卉+，丁月民，刘振兴

(1.武汉科技大学 信息科学与工程学院，湖北 武汉 430081；2.天津理工大学 计算机科学与工程学院，天津 300384)

0 引 言

作为电力系统的重要组成部分，智能电网(smart grid，SG)输电线路故障发生后需将故障信息实时发送给巡检区域内所有巡检人员，以便巡检人员及时处理。多播作为一点对多点的通信，是提高因特网多媒体信息传输实时性和节省网络带宽的有效方法之一[1]。然而，与多媒体信息实时多播不同，智能电网应用下的信息多播通信不仅要具有实时性，更需要可靠性和经济高效等特点[2]。因此，因特网的多播路由算法不能直接应用于智能电网通信。

近几年来，不少学者结合智能电网应用背景对多播路由技术进行改进，并取得了显著效果。文献[3]分析了支持多播路由的智能电网中潜在的网络安全问题，针对电网网络安全和用户隐私提出了一种安全、高效的多播路由协议。文献[4]为多跳mesh网络中PMU通信提出了一种自适应分布式多播路由方法，以提高电力通信系统的鲁棒性。文献[5]提出了一种基于需求响应能力约束的多播路由算法，该算法将时延和目的节点需求响应能力作为约束条件构造多播树，稳定电网频率，保证电网的可靠性。为满足智能电网广域控制(WAC)通信的实时性要求，最大限度减少带宽约束下广域网(WAN)的端到端时延，文献[6]提出了一种适用智能电网WAC的多播路由约束优化方法。目前，大多数多播技术集中在智能电网需求响应、网络安全和广域控制等方面的应用，而有关多播技术应用于输电线路故障信息传输的研究相对较少。

在智能电网中，通常采用无线传感器网络(wireless sensor network，WSN)对输电线路上的信息进行传输[7]。然而，WSN应用于输电线路故障信息传输中存在以下问题：①故障发生时，巡检区域内各巡检人员位置不一，人为设置多播树时延上限不能保证故障信息传输的实时性；②输电线路通信量大，无线节点能量和内存受限，过高的通信代价会给WSN带来负担[8]。

为了解决上述问题，本文提出了一种输电线路故障传输多播路由算法(multicast routing algorithm for the transmission of fault information on power transmission line，MRFT)。该算法①为了保证实时性，以时延最短路径树(SPT)的最大端到端时延作为多播树时延上限；②为了减小多播树通信代价，基于最小代价启发函数连接剩余叶子节点，保证在满足时延约束下使通信代价达到最小。

1 网络模型及多播问题描述

1.1 网络描述

一般输电线路故障信息传输WSN网络模型如图1所示。输电线上均匀部署着用于监控输电线路状态的WSN静态节点，巡检人员在输电线路的两边进行巡检作业，并携带WSN节点用于WSN通信。输电线路上的WSN静态节点和巡检人员携带的WSN低速移动节点共同构成了WSN网络。

图1 输电线路故障信息传输的WSN网络模型

故障发生后，故障源节点向巡检区域内的所有巡检人员发送故障信息。假设每个巡检人员都以正常步行速度进行巡检作业，且无特殊情况发生。忽略信息在无线链路上的转发和排队时延，重点考虑传播时延，由于信息在WSN中的传播速率为20 kbps～250 kbps[9]，远远超过常人的步行速度，巡检人员是低速移动节点，相对于传播时延，低速移动后的位置所造成的时延可以忽略不计。因此可以将故障信息WSN传输网络当作静态网络进行分析。

1.2 问题描述

本文中所使用的主要符号见表1。

表1 符号

定义1 输电线路故障信息实时传输网络可以用一个无向的权重图G(V,E)表示，其中V表示无线节点集，E表示通信范围内相邻节点间的通信链路集。c(e) 表示链路e上的代价，d(e) 表示链路e上的传播时延。

定义2 设L(v,w) 表示从节点v到节点w的路径，v,w∈V。T(s,D) 表示多播树，故障源节点s∈V为多播树的源节点，巡检人员集合D∈V为该多播树的叶子节点集，d∈D为叶子节点。

定义3 设R为正实数集，对于任意链路e∈E，时延函数d(e):E→R，代价函数c(e):E→R。

定义4 设T(s,D) 表示一棵多播树，则式(1)表示路径L(s,d) 的端到端时延，式(2)表示多播树T(s,D) 的代价

(1)

(2)

定义5 多播树时延上限问题：

一棵多播树的时延通常由这棵树中端到端时延的最大值决定。由于所有多播树的最短时延不会比最短时延多播树的时延还小，设Lspd(s,D) 为源节点s到叶子节点集D的最短时延路径集合，则多播树时延上限定义为

δ=max(d(Lspd(s,D)))

(3)

假设路径Lx(s,dx)∈Lspd(s,D) 为满足条件路径，记Lx(s,dx) 为时延上限路径，节点dx为时延上限节点。

定义6 输电线路故障信息多播路由问题：

输电线路故障信息多播路由问题就是要找到一棵满足时延约束δ下的最小代价树，即找到一棵多播树T(s,D) 满足

min(c(T(s,D)))
s.t.d(L(s,d))≤δ,∀d∈D

(4)

2 MRFT算法

式(4)是一个带约束条件的斯坦纳树问题，已经证明是一个NP完全问题，通常采用启发式方法求解[10]。为了使巡检区域内所有巡检人员能实时接收故障信息、降低通信代价，本文提出了一种基于最小代价启发函数的输电线路故障传输多播路由算法(MRFT)。为了提高实时性，该算法通过式(3)确定多播树时延上限。为了在满足时延约束的情况下减小通信代价，当时延上限路径接入多播树后，算法采用一个最小代价启发函数连接剩余叶子节点。MRFT算法主要包括4个步骤：①源节点监测到故障事件后，将叶子节点集加入到网络；②求解多播树时延上限；③判断MST是否满足时延约束，若不满足执行步骤④；④将时延上限路径接入多播树，基于最小代价启发函数连接剩余叶子节点。

2.1 最小代价启发函数

设集合K={dx,k1,k2,…,kn,s} 为时延上限路径Lx(s,dx) 中的节点集，其中k1是与dx直接相连的节点，n为路径Lx(s,dx) 中路由节点个数。为了减少通信代价，定义MRFT算法最小代价路径选择启发函数fc(k,du)

(5)

其中，k∈K，du∈{{D}-dx}，Lspc(k,du) 为节点k到叶子节点du的最小代价路径，ε(k) 为多播树中源节点s到节点k的时延。由于多播树时延上限δ已经是当前情况下的最优值，因此，在连接剩余叶子节点时，启发函数fc并没有尽可能减小时延，而是寻找一条满足时延约束的最小代价路径。

2.2 MRFT算法流程

根据MRFT算法的4个主要步骤，其伪代码和具体流程描述如下：

Algorithm:MRFT(G,s,D)

(1)δ←max(d(Lspd(s,D)));T1←Tmst(s,D);

(2)IFmax(d(Lmst(s,D)))≤δthenreturnT1as solution;

(3)T2←Lx(s,dx);

(4)Foralldu∈{{D}-dx}Do

(5)Forallk∈KDo

(6)IFε(k)+d(Lspc(k,du))≤δthen

(7)T2←Lspc(k,du);break;

(8)EndIF

(9)IF((k=s)andd(Lspc(s,du)>δ))then

(10)T2←Lspd(s,du);

(11)EndIF

(12)EndFor

(13)EndFor

(14)returnT2as solution;

步骤1 网络模型初始化。在节点间通信链路上添加传输代价和传输时延权重值。在电网模型中随机选择一个节点作为源节点s，将多播叶子节点集D加入到网络;

步骤2 求出源节点s到所有叶子节点的最短时延路径集合Lspd(s,D)，根据式(3)求出多播树时延上限δ;

步骤3 采用MST计算最小代价多播树Tmst(s,D)，若∀Lmst(s,d)∈Tmst(s,D) 满足d(Lmst(s,d))≤δ，则Tmst就是满足式(4)的多播树，否则进入步骤4;

步骤4 将时延上限路径Lx(s,dx) 接入多播树，将时延上限节点dx从叶子节点集D中删除。

从叶子节点集D中任选一个节点du作为预连接节点。根据式(5)，依次从集合K中选取节点k，求出节点k到节点du的最小代价路径Lspc(k,du)。 若ε(k)+d(Lspc(k,du)) 满足时延约束，则将路径Lspc(k,du) 接入多播树。若当k=s时仍无法满足时延约束条件，则将源节点s到叶子节点du的最短时延路径Lspd(s,du) 接入多播树。预连接节点du接入多播树后，将其从集合D中删除，再从集合D中任选一个节点作为下一个预连接节点，依次循环，直到所有叶子节点全部接入多播树。

3 仿真结果分析

为了验证MRFT算法在智能电网输电线路故障信息传输中的有效性，在MATLAB 2014a中建立输电线路故障信息传输的WSN网络模型。在相同情况下，将MRFT算法与经典时延受限多播路由算法——KPP算法[10]进行对比，从以下3个方面进行仿真分析：①多播树时延；②端到端时延方差；③多播树代价。

3.1 仿真场景及参数

输电线路故障信息传输的WSN仿真场景由输电线路监测场景和巡检人员巡检场景两部分构成。对于输电线路监测场景，仿真区域为1000m×100m，4条输电线分别由4条直线表示：y=80、y=60、y=40和y=20，输电线上均匀部署着用于传输故障信息的传感器节点。对于巡检人员巡检场景，巡检人员有两个活动区域，区域1由函数y=0，y=10和x=0，x=1000围成，区域2由函数y=90，y=100和x=0，x=1000围成。网络内节点间链路采用Salama算法[11]生成，节点间链路概率函数如下

(6)

其中，distance(v,w) 为节点v、w之间的欧式距离，Len为任意两点间的最大距离，α用于调节短链路的密度，β用于调节链路密度。当输电线上的WSN静态节点总数分别为40、80、120、160、200时，α相应取值为0.12、0.08、0.073、0.068和0.063，β始终为2.2。

设网络中节点间的链路代价为节点间距离，链路时延为节点间距离乘以0～1之间的随机数。从输电线上随机选择一个节点作为源节点，叶子节点在巡检人员区域内随机分布。令KPP算法的时延上限Δ与MRFT算法的时延上限δ相同，仿真中每个数据点的值为100次实验的平均值。

3.2 仿真结果分析

3.2.1 多播树时延

由于SPT算法构建的多播树时延较小，因此仿真以SPT算法作为参照，比较MRFT算法和KPP算法所构建多播树的相对时延。相对时延函数表示如下

(7)

分别从以下两种情况进行仿真：①当叶子节点为10，网络节点数与Edelay的关系；②当网络节点数为40，叶子节点数与Edelay的关系。

如图2、图3所示，当网络中节点数与叶子节点较少时，MRFT算法生成的多播树的时延性能与KPP算法的时延性能比较接近。随着节点总数和叶子节点数不断增加，MRFT算法的相对时延虽有所波动，但总体变化趋势较为稳定；而KPP算法的相对时延却随着网络规模的增大呈上升趋势，当网络节点为200时，二者多播树时延相差约为50%。

图2 网络节点数与Edelay的关系

图3 叶子节点数与Edelay的关系

3.2.2 端到端时延方差

当网络节点数为40，端到端相对时延方差对比图如图4 所示。时延方差越小说明时延数据越稳定，理想状态下，当方差为0时，各个巡检人员会同时收到故障信息。由于有关优化端到端时延方差的研究较少，考虑到SPT算法在优化多播树时延上具有较好表现，因此，在仿真时仍然以SPT算法为参考计算相对时延方差。端到端相对时延方差函数表示如下

(8)

如图4所示，MRFT算法在不同叶子节点数下的端到端相对时延方差值均为负值，说明MRFT算法构建的多播树端到端时延小于SPT算法所构建的多播树的端到端时延。KPP算法构造的多播树端到端时延方差比SPT算法平均高出一倍有余，远大于MRFT算法。MRFT算法基于最小代价启发函数连接剩余叶子节点，最小代价启发函数旨在寻找一条满足时延约束的最小代价路径，因此，采用MRFT构造的多播树端到端时延方差较小。

图4 叶子节点数与Evar的关系

3.2.3 多播树代价

由于MST算法不考虑时延约束，得到的多播树代价较小，因此仿真以MST算法作为参照，比较MRFT算法和KPP算法所构建多播树的相对代价。相对代价函数表示如下

(9)

分别从以下两个方面进行仿真：①当叶子节点为10，网络节点数与Ecost的关系；②当网络节点数为40，叶子节点数与Ecost的关系。

区域内节点总数和叶子节点个数对多播树代价的影响分别如图5、图6所示。随着网络节点数和叶子节点个数的增加，多播树规模逐渐变大，从而占用更多的资源，因此多播树代价逐渐升高。由于MST算法不考虑时延约束，并且MRFT和KPP算法在构造多播树时根据SPT的最大端到端时延确定多播树时延上限，时延约束比较严格，可选链路较少。因此，与MST算法所构造的多播树相比，MRFT和KPP算法构造的多播树代价相对较高。尽管如此，本文所提出的MRFT算法在不同叶子节点数和网络节点数下的代价均优于KPP算法。

图6 叶子节点数与Ecost的关系

3种情况下的仿真结果表明，本文提出的电网输电线路故障信息传输多播路由算法——MRFT在多播树时延、端到端时延方差和多播树代价3个方面的表现均优于KPP算法。尽管相对MST算法来说，MRFT算法构建的多播树代价较高，但由于MRFT算法的多播树时延与端到端时延较低，且故障事件发生的概率较低，因此，短时间、低频率的故障信息传输行为不会对WSN网络造成太大负担。

4 结束语

本文提出了一种智能电网输电线路故障信息传输多播路由算法，该算法根据SPT的最大端到端时延确定多播树时延上限，当时延上限边接入多播树后，基于最小代价启发函数连接剩余叶子节点。仿真结果表明，该算法构造的多播树能够在满足时延约束的同时降低通信代价，确保故障信息能实时发送给巡检人员。本文的仿真实验是在静态网络模型中进行的，下一步将结合巡检人员速度信息对该算法进行改进，使其应用于半动态输电线路故障信息传输WSN网络。