基于网络内在特征的电力通信网探测站点选择算法

胡文建，王长宁，杨宇皓，李旭东，孙 静，杨 阳

(国网河北省电力有限公司石家庄供电分公司，石家庄 050051)

0 引言

电力通信网是智能电网重要组成部分，是保证智能电网安全、稳定运营的关键因素[1-2]。为提高电力通信网安全性和稳定性，网络管理人员必须实时掌握电力通信网设备的运行状况。但是，现有网络管理系统采用SNMP协议，被管设备周期性的给网络管理系统上报设备运行信息，容易导致网络发生故障后才被管理人员发现，而且被管设备上报的信息不便于故障定位和恢复。

为解决此问题，主动探测技术被提出[3]，并且在故障管理领域得到了较多的应用。在主动探测技术中，探测站点的选择对网络运行状态信息的获取起到了非常关键的作用。如果探测站点选择的合适，会极大减少主动探测过程给网络带来的负面影响。如何通过选择较少的探测站点实现对网络的主动监控，已成为当前的一个研究热点[4-5]。一般来说，探测站点的选择是基于网络中节点的位置和路由协议等信息进行选择[6]。根据选择过程不同，可分为固定周期选择探测站点模型[7]和交互式探测站点选择模型[8]2种。固定周期选择探测站点模型一次性求解出所有合适的探测站点，虽然计算时使用的网络模型比较复杂，但是一次性就可以求解出最佳的探测站点集合。交互式探测选择方法每次只选择一个最优的探测站点，经过多次优化，最终得到最佳的探测站点集合。但是该方法需要经过多次重复计算，而且每次计算网络节点的信息增益都需要花费大量的时间。考虑到当前的电力通信网规模比较大，如果采用交互式探测站点选择方法，需要进行多次计算，工作量较大。

为解决电力通信网规模较大导致探测站点部署效率低的问题，基于电力通信网的特性提出了探测站点选择的策略，基于网络内在特征的电力通信网探测站点选择算法，从电力通信网的网络节点中，选择最少的网络节点作为探测站点，通过发送探测监控到所有网络节点的运行状态信息，以最少的探测站点达到最好的探测效果。

1 电力通信网络特征

1.1 动态路由特性

在电力通信网中，一般来说，网络设备都启用了动态路由协议。鉴于动态路由协议在路由选择时具有动态特性，所以，探测是否经过某个网络节点具有概率性。

为了描述从探测站点发送探测到网络节点x的探测路径是否经过网络节点nj，文中使用概率公式进行描述。使用P(PSPath(x)，nj)表示从探测站点集合PS中的探测站点发送探测到网络节点x的探测路径经过网络节点nj的概率。

1.2 探测路径的重叠特性

探测站点是指具备发送和接收探测数据包能力的网络节点。通常，一个网络节点被选为探测站点需要满足2个条件:可以使用TCP或UDP协议发送和接收探测数据包；从该节点发送的探测数据包构成的路径与其它探测站点发送数据包构成的路径尽可能独立，并且独立路径的数量尽可能多。从上述2个条件可知，处于网络边缘的节点一般不会被选择为探测站点。因为处于网络边缘的节点具有较少的边数，从而导致其不会具有较多的独立路径。文中使用pi表示第i个探测站点，使用PS表示探测站点集合。使用nj表示第j个网络节点，使用N表示网络节点集合。一般来说，从探测站点到目标网络节点的探测，都会经过多条网络链路l。为便于描述探测站点发出的探测路径，文中使用P(p，nj)表示探测路径p经过网络节点nj的概率。例如，图1是包含2个探测站点的网络拓扑示意，图中A、G为2个探测站点。A→C的探测路径和G→C的探测路径是相互独立的。但是，A→E的探测路径和G→E的探测路径中，C→D→E路径是相互重叠的。此时，A→C和G→C的探测结果互相独立，但是A→E和G→E的探测结果互相重叠。所以，相对于A、G 2个探测站点，网络节点D和网络节点E为阴影节点。

图1 包含2个探测站点的网络拓扑示意

为判断2个探测路径之间的独立性，文中定义探测路径p1和p2之间的非重叠函数为BF(I(p1，p2))，使用公式(1)进行计算。其中，nj∈node(p1)∩node(p2)表示探测路径p1和p2经过的节点的交集。该公式表示两条路径的非重叠概率。当取值越大，表示2条探测路径之间重叠的概率越小。

当已选择部分探测站点之后，在选择新的探测站点时，以新探测站点到达阴影节点的探测路径的独立性为评判标准。例如，对于新的可选探测站点c，需要计算它到阴影节点x的探测路径的独立性。使 用 BF(I(PSPath(x)，Path(c，x)))表示新探测站点到达阴影节点的探测路径的独立性，使用公式(2)计算。其中，nj∈PSPath(x)∩Path(c，x)表示“已有探测到达阴影节点x的路径”与“节点c到达阴影节点x的路径”的重叠路径所经过的节点。

在获得每一个新探测站点到达阴影节点的探测路径BF取值后，可以将大于阈值Thd的BF取值对应的新探测站点加入探测站点集合。

1.3 最大故障数目

在电力通信网中，当只有一个故障时，可以通过在一个探测站点发送探测到所有网络节点确定故障节点的位置。当故障节点数量增加时，就需要更多的探测站点发送探测确定故障节点的位置。所以，电力通信网中故障节点的数量对探测站点的数量产生重要影响。根据长期运营数据可知，电力通信网中同时发生故障的次数非常少，基于此，文中设置电力通信网中同时发生故障的最大个数为k，非探测站点如果包含k条独立的探测路径，该节点即为可以被探测到的非阴影节点。但当网络节点nj的度数d小于k时，最多只能存在d条独立的探测路径。此时，只需找到d条独立路径，就可将网络节点nj判断为非阴影节点。

2 探测站点选择算法

2.1 算法流程

文中提出的基于网络内在特征的电力通信网探测站点选择算法如图2所示。该算法以探测站点数量达到最大值或阴影节点集合为空作为终止条件，从网络节点中逐步选择可以使阴影节点集合中阴影节点数量最少化的新的网络节点作为探测节点。下面对各个步骤进行详细解释。

图2 基于网络内在特征的电力通信网探测站点选择算法

在步骤1中，新建探测站点集合PS，并初始化为空；新建阴影节点集合SN，并将网络节点集合N中的所有网络节点放入阴影节点集合。在步骤2中，选择节点度数最大的网络节点作为第1个探测节点；如果存在多个网络节点都有最大的度数，计算每个节点到其它节点的链路距离，选择链路距离最短的核心节点作为第1个探测节点。假设第1个被选择的探测节点为u，则采用公式(3)计算探测节点u对于网络节点集合中任意网络节点的探测路径概率。

式中:w，v∈N。

在步骤3中，以最小化阴影节点集合为目标，从网络节点集合N中选择下一个网络节点作为探测节点。在步骤4中，分析第3步得到的每个节点的独立路径数量PathCount(nj)。当PathCount(nj)大于等于最大故障数量k时，网络节点nj可以被探测站点探测到。当PathCount(nj)小于最大故障数量k，但是等于网络节点nj的度数时，此时网络节点nj可以被探测站点探测到。否则，表明网络节点nj仍然还是阴影节点，需要进一步寻找探测节点。此时，将网络节点nj加入到阴影节点集合。当判断完所有的网络节点之后，如果阴影节点集合不空，返回到步骤3。否则，算法结束。

2.2 探测节点的选择过程

为了验证网络中是否还存在阴影节点，已有研究表明，当网络中的非探测站点都存在K条独立的探测路径时，已确定的探测站点集合可以检测出任意K个非探测站点的故障。此时，电力通信网的网络节点都属于可探测节点，不存在阴影节点。在网络节点中选择探测节点时，以阴影节点集合中阴影节点数量最小化为目标。下面对网络节点集合N中选择下一个网络节点作为探测节点的过程进行说明。该步骤包括5个子过程。

a.在网络节点集合N中选择下一个探测站点时，使用公式(4)计算候选探测站点c提供的到达阴影节点x的独立探测路径的非重叠函数BF，用于判断阴影节点x是否属于候选探测站点c的阴影节点。其中，n∈PSPath(x)∩Path(c，x)，表示“探测站点集合中的探测站点到达候选探测站点c的路径”与“候选探测站点c到达阴影节点x的路径”的重叠链路经过的网络节点。

b.如果BF(I(PSPath(x)，Path(c，x)))＞T Hd，表明路径PSPath(x)和路径Path(c，x)是相互独立的，将PathCount(c，x)的值加1；否则，阴影节点x是候选探测站点c的阴影节点，并将x加入c的阴影节点集合S(c)。

c.选择可以使阴影节点数目最少的候选探测站点c作为探测站点，并将探测节点c加入探测站点集合PS中。

d.设置S(c)为新的阴影节点集合，使用公式(5)更新PathCount(n)。其中，公式(5)表示将网络节点集合N中的每个网络节点n的独立路径数量更新为加上探测站点c之后的独立路径数量。

e.如果阴影节点集合S(c)为空，或者探测站点集合PS中的探测站点数量超过允许的最大数量，算法结束。否则，返回第1步执行。

3 探测站点选择算法验证分析

为验证本文提出的基于网络内在特征的电力通信网探测站点选择算法PSA-NF的性能，实验中将此算法与随机选择探测站点算法PSA-RD进行了比较。比较的指标包括选择的探测站点数量和选择探测站点的时长。实验中使用BRITE[9]工具生成电力通信网拓扑。其中，网络节点的数量从100到500，以50为步长进行增加。为了验证网络节点度数对算法的影响，生成了平均度数为4和平均度数为7两种网络拓扑。每次实验中，设定故障同时发生的最大数量为4个。

实验结果如图3—6，其中图3—4是探测站点数量的比较。图5—6是探测选择时长的比较。图3和图4的探测站点数量的比较结果可知，算法PSA-NF和算法PSA-RD的探测站点数量随着网络节点数量的增加都在增加。其中，算法PSARD的探测站点数量增加较快，算法PSA-NF的探测站点数量增加相对较慢。图3和图4的比较可知，随着网络拓扑中网络节点平均度数增加，2种算法的探测站点的数量都在降低。

图3 平均度数为4的网络拓扑的探测站点数量比较

图4 平均度数为7的网络拓扑的探测站点数量比较

图5 和图6的探测选择时长的比较结果可知，算法PSA-NF和算法PSA-RD的探测选择时长都随着网络拓扑规模的增加而增加。其中，算法PSA-RD的探测选择时长增加较慢，算法PSANF的探测选择时长增加较快。图5和图6的比较可知，随着网络拓扑中网络节点平均度数增加，2种算法的探测选择时长都在增加。

图6 平均度数为7的网络拓扑的探测选择时长比较

综上所述，虽然本文算法PSA-NF在探测选择时长方面比算法PSA-RD较长，但是本文算法在2种网络拓扑中选择的探测站点数量都相对较少。在当前的云计算环境下，可以通过增加虚拟机分配提升运算环境，从而降低探测选择时长。所以，本文算法适合当前的网络运行环境。

4 结束语

智能电网快速发展的环境下，电力通信网规模较大导致探测站点部署效率低的问题。为解决此问题，本文针对电力通信网的特性提出了探测站点选择的策略，以网络内在特征为依据，将文中算法与传统算法进行比较，文中算法从电力通信网的网络节点中，通过选择最少的网络节点作为探测站点，可以通过发送探测监控到所有网络节点的运行状态信息，即以最少的探测站点达到最好的探测效果。下一步将基于本文的研究成果，进一步分析网络节点删除和增加的环境下，如何快速更新探测站点集合，减少网络节点变动对主动探测产生的影响。