基于改进聚类算法的电力通信网可靠性优化算法

付佳佳　吴赞红　施展

摘   要：随着电力通信网规模的逐渐扩大，已有电力通信网可靠性优化算法的计算时间复杂度较高。为此，提出了基于改进聚类算法的电力通信网可靠性优化算法。该算法首先采用模拟退火算法与遗传算法结合的FCM算法将大规模网络划分为多个社团。其次，通过社团间可靠性分析与备份方法、社团内可靠性分析与备份方法两个过程，对电力通信网的关键资源进行识别和备份，从而提升了电力通信网的可靠性。在仿真实验部分，从备份资源数量在总资源中的占比、网络连通度两个方面，将本算法与已有算法进行比较，验证了本文算法有效提升了电力通信网的可靠性。

关键词：电力通信网;可靠性;聚类;社团;SDN

中图分类号：TP393                                         文献标识码：A

Reliability Optimization Algorithm for Power Communication

Network Based on Improved Clustering Algorithm

FU Jia-jia ，WU Zan-hong，SHI Zhan

（Power Grid Dispatching Control Center，Guangdong Power Grid Co.，Ltd，Guangzhou，Guangdong 510600，China）

Abstract：With the gradual expansion of the scale of power communication networks，the time complexity of existing power communication network reliability optimization algorithms is relatively high. In order to solve this problem，this paper proposes a reliability optimization algorithm for power communication network based on improved clustering algorithm. The algorithm firstly uses the FCM algorithm combined with simulated annealing algorithm and genetic algorithm to divide large-scale network into multiple communities. Secondly，through the two processes of reliability analysis and backup method，intra-community reliability analysis and backup method，the key resources of the communication network are identified and backed up，thereby improving the reliability of the power communication network. In the simulation experiment，the algorithm is compared with the existing algorithms from the aspects of the proportion of backup resources in total resources and network connectivity. It is verified that the proposed algorithm effectively improves the reliability of the power communication network.

Key words：power communication network;reliability;clustering;community;SDN

随着各种新型电力业务的快速发展和应用，实际环境中电力通信网的管理和维护更加困难，迫切需要可以应用于实际环境下的电力通信网的可靠性分析方法[1-2]。在网络可靠性提升方面，典型的研究成果包括采用遗传算法优化路由策略从而实现路由均衡[3]、优化网络的关键资源从而提升网络可靠性[4]、同时优化电力通信网相关系统和通信网相关设备等研究方法[5]，在提升电力通信网可靠性方面取得了较好的结果。在电力设备可靠性提升方面，典型的研究成果包括采用优化后的混合半云模型优化配电系统可靠性[6]、采用频率优化策略实现电网可靠性评估[7]。另外，在电力设备可靠性提升方面引入了一些新技术，例如SDN技术已成为新型网络可靠性的关键技术[8]、基于关联规则的Apriori-AHP算法的主动可靠性保障技术[9]、使用链路已使用情况进行网络可靠性研究的方法[10]。

已有研究分析可知，在电力通信网的可靠性研究方面已经取得了较好的研究成果。但是，已有算法主要关注新的方法和技术在电力通信网可靠性提升方面的应用。在电力通信网规模越来越大的趋势下，急需能够有效解决大规模环境下网络可靠性问题的研究成果。为此，采用模拟退火算法与遗传算法结合的FCM算法将大规模网络划分为多个社团，提出了基于改进聚类算法的电力通信网可靠性優化算法。通过仿真实验，验证了本算法有效提升了电力通信网的可靠性。

1   问题描述

一般来说，网络节点和网络链路构成电力通信网。网络节点为电力业务提供计算服务，网络链路为电力业务提供通信连接服务。使用G = （V，E）表示电力通信网，其中，V表示网络节点集合，E表示网络链路集合。在电力通信网的可靠性方面，节点的度De（ni）是一个非常关键的属性。度数越大，相连的边越多，承载在其上的电力业务的可靠性越高。如果发掘度数少的节点，且该节点在网络中处于重要位置，可以通过为其分配备份资源，提升网络的可靠性。

因为电力通信网的规模较大，如果通过算法对整个电力通信网的属性进行分析，会导致运算复杂度较高。为此，采用聚类算法，发掘网络节点之间的关联关系，从而将电力通信网划分为多个小规模的网络。因为模糊C-均值聚类（FCM）具有运算速度快、分类结果较好等优点[11]，本文采用FCM算法对电力通信网进行聚类分析。

使用V = {v1，v2，…，vn}表示网络节点集合。假设将网络节点划分为c（2≤c≤n）个节点集合，则使用U = {A1，A2，…，Ac}表示划分后的网络节点子集合。子集合的中心使用{k1，k2，…，kc}表示。为了评判子集合的划分效果，定义目标函数Jb并使用公式（1）评判聚类划分的效果。其中，μk（xi）表示各个网络节点vi相对于类Ak的隶属度（简化标记为μk），dik表示网络节点vi和类Ak的聚类中心ki的欧几里得距离。b表示加权参数，1≤b≤∞。

Jb（U，v） = ∑ni=1∑ck=1（uik）b（dik）2       （1）

因为电力通信网的规模较大，FCM算法属于一种局部搜索算法，所以FCM算法搜索的结果可能是局部最优。为此，基于模拟退火算法与遗传算法对FCM算法进行优化，从而得到全局最优的结果。

2   算   法

为解决大规模环境下网络可靠性优化算法性能低的问题，提出了优化算法包括社团划分、社团间可靠性分析与备份方法、社团内可靠性分析与备份方法三个步骤。下面首先对三个步骤的关键知识进行详细描述，之后对算法过程进行分析。

2.1    社团划分

在社团划分时，采用基于模拟退火算法与遗传算法的FCM算法对电力通信网进行划分。划分时包括三个过程：（1）初始化控制参数;（2）对每个聚类中心计算个体的适应度值;（3）对群体实施选择、交叉和变异等遗传操作。

在初始化控制参数时，控制参数包括种群大小SP、最大优化代数MG、变异概率Pm、交叉概率Pc、温度降低系数k、退火开始温度T0、退火结束温度Tend。首先通过随机生成c个聚类中心，并划分为初始种群CM。为评价每个聚类的划分是否合适，需要给每个聚类中心应用公式（1）求解个体的目标函数Jb，并将其值赋值给适应度fi，其中i=1，2，…，SP。其次，使用公式（2）计算每个个体的隶属度，对群体CM进行选择、交叉和变异等后，使用公式（3）计算聚类的新中心。在判定是否结束方面，从遗传代数、降温两个维度对算法是否结束进行判定。

μik = ■     （2）

vij = ■     （3）

2.2   社团间可靠性分析与备份方法

将电力通信网划分为多个子网络（即多个社团）时，每个子网络内部关系比较紧密，各个子网络之间的链路比较稀疏。此时，各个子网络之间链路的可靠性对于电力通信网的整体连通性起到了非常关键的作用。当任意两个子网络之间的链路出现故障时，子网络之间失去连通性。所以，如何确保子网络之间链路的可靠性，对于电力通信网的可靠性至关重要。

在社团间可靠性提升时，以当前社团的外链边数在所有社团的外链边数的比值进行衡量，称为社团外链能力。此时，社团外链能力越强，电力通信网的可靠性越高。使用Vxy = {（u，v）∈E，u∈Cx，v∈Cy，x≠y}表示社团x和社团y的链路集合。使用v（x，y） = Vxy表示社团x和社团y之间的链路数量。基于上述分析，使用公式（4）计算社团x的可靠性。其中，Vx = ∑y∈EVxy表示与社团x相连接的所有社团的外链链路之和。通过社团间可靠性分析，将可靠性最低的社团的边及其相连的节点进行备份，从而提升网络的可靠性。

CR（x） = ■       （4）

2.3   社团内可靠性分析与备份方法

从社团划分的计算过程可知，在每个社团内，网络节点的距离较近，关联性较高。所以，在分析社團内的可靠性时，采用内部节点中心度进行衡量。使用公式（5）计算每个社团内的网络节点ni∈N的可靠性。其中，dij表示节点ni和节点nj之间最少的链路数量，nj∈ψ（ni）表示电力通信网删除ni∈N后的节点集合。通过社团内可靠性分析，将可靠性最低的内部节点进行备份。

CC（ni） = ∑nj∈Ψ（ni）dij       （5）

2.4   算法描述

为解决大规模环境下网络可靠性优化算法性能低的问题，提出的优化算法包括三个步骤。（1）、采用模拟退火算法与遗传算法结合的FCM算法将大规模网络划分为K个社团;（2）、社团间可靠性分析与备份;（3）、社团内可靠性分析与备份。算法描述如表1所示。

算法：基于改进聚类算法的电力通信网可靠性优化算法

（1）采用模拟退火算法与遗传算法结合的FCM算法将大规模网

络划分为K个社团;

（a）初始化SP、MG、Pc、Pm、T0、Tend等控制参数;

（b）采用公式（1）求解各个聚类中个体的fi;

（c）采用公式（2）、（3）计算新个体的μik，以及各个聚类的新中心

和f  ′i。

（d）如果f  ′i > fi，说明新个体的划分比旧个体更优，用其代替旧个体。反之，采用P = exp（（fi - f  ′i）T）的概率从新旧个体中进行选择。

（e）如果存在gen < MG，此时gen = gen + 1，向上跳转到c。

（f）如果存在Ti < Tend，此时的解就是最优解;反之，向上跳转到c。

（2）社团间可靠性分析与备份方法：

（a）使用公式（4）计算社团的可靠性;

（b）将可靠性最低的W个社团的外链边及其相连的节点，进行备份;

（3）对每一个社团，进行社团内可靠性分析与备份：

（a）使用公式（5）计算内部节点可靠性;

（b）将可靠性最低的Z个内部节点，进行备份。

在步骤1中，主要包括控制参数初始化（过程a）、计算适应度值（过程b）、个体的隶属度评价（过程c）、更新个体（过程d）四个主要过程。在步骤2中，主要包括计算社团的可靠性（过程a）、对可靠性最低的W个社团的外链边及其相连的节点进行备份（过程b）两个主要过程。在步骤3中，主要包括计算内部节点中心度（过程a）、可靠性最低的内部节点进行备份（过程b）。

3   仿   真

3.1   环境

实验部分使用BRITE工具生成电力通信网环境[12]。为了验证不同网络规模下算法的性能。实验中，使用了100个到500个之间变化的网络节点环境。为了验证网络的可靠性，采用端到端的最短路径模拟电力通信业务。其中，电力业务的源节点使用随机选择的10%网络节点进行模拟，电力业务的终点使用除源节点之外的互不相同的网络节点进行模拟。

在算法性能分析时，将本算法ROAoIC与传统算法ROAnoC进行比较。其中，传统算法ROAnoC是指仅仅基于网络节点的特性进行备份，而不采用聚类算法对网络进行划分。评价指标包括备份资源数量在总资源中的占比、网络连通度。其中，备份资源数量在总资源中的占比是指社团中的备份资源、社团之间的备份资源在总的资源中的比例。网络连通度是指电力通信网节点和链路产生故障后，网络最大连通分量的节点数 与电力通信网的节点总数 的比值，使用S（G）表示，采用公式（6）计算。其中，Sf （G） = ■表示网络故障后的网络连通度，So （G）表示网络无故障时的网络连通度。

S（G） = ■       （6）

为了验证网络的可靠性，采用的攻击模型分为随机性攻击和选择性攻击两种。随机性攻击的对象是从网络资源中随机选取。选择性攻击是以较大的概率从社团间的可靠性较低的链路中、或从社团内部可靠性较低的网络资源中选择被攻击的对象。

3.2   结果分析

（1）备份资源数量

备份资源数量比较的实验结果如图1所示，其中，x轴表示网络节点规模，y轴表示备份资源数量。从图可知，本算法ROAoIC的备份资源量与传统算法ROAnoC的备份资源量都维持在25%左右。说明两种算法对网络资源的利用率相近。

（2）随机性攻击环境下的网络连通度

随机性攻击环境下的网络连通度比较的实验结果如图2所示，其中，x轴表示网络节点规模，y轴表示随机性攻击环境下的网络连通度。从图可知，本算法ROAoIC的网络连通度维持在0.77左右，传统算法ROAnoC的网络连通度维持在0.57左右。说明本算法有效提升了随机性攻击环境下的网络连通度。

（3）选择性攻击环境下的连通度

选择性攻擊环境下的网络连通度比较的实验结果如图3所示，其中，x轴表示网络节点规模，y轴表示选择性攻击环境下的网络连通度。从图可知，本算法ROAoIC的网络连通度维持在0.62左右，传统算法ROAnoC的网络连通度维持在0.43左右。说明本算法有效提升了选择性攻击环境下的网络连通度。

4   结   论

随着电力通信网的规模逐渐扩大，电力通信网在智能电网中的作用越来越重要。电力通信网的可靠性优化已成为一个重要的研究内容。为解决大规模环境下的网络可靠性优化问题，采用模拟退火算法与遗传算法结合的FCM算法将大规模网络划分为多个社团，提出了基于改进聚类算法的电力通信网可靠性优化算法。通过仿真实验，验证了本算法有效提升了电力通信网的可靠性。但是在资源备份方面，与已有算法一样，需要备份较多的资源，导致网络资源利用率降低。

参考文献

[1]    石天伟.电力通信网可靠性分析[J]. 通讯世界，2016，（10）：20-22.

[2]    杨林慧，孙少华.电力通信网节点重要度的评估算法[J]. 智能电网，2017，5（07）：656-659.

[3]    孙方楠，梁后健，张课，等. 基于改进遗传算法的电力通信网路由优化研究[J].  自动化与仪器仪表，2018，（6）：25-28.

[4]    朱明波. 基于遗传算法的计算机网络可靠性优化设计[J].  课程教育研究，2018，（19）：232-234.

[5]    曾伟忠，袁咏诗. 兼顾可靠性与通信效率的电力通信网络协调优化方法[J].  电气自动化，2018，40（4）：102-104.

[6]    陈绍南，李克文，秦丽文，等. 考虑不规则风速概率分布特性的配电系统可靠性评估[J].  广西电力，2019，42（2）：17-21.

[7]    郭经，刘文霞，张建华，等. 计及控制功能失效的微电网信息物理系统可靠性评估[J].  现代电力，2019，36（2）：73-80.

[8]    吴路明，裘愉涛，陈琦. 基于 SDN 的电力通信网络关键技术综述[J].  江苏电机工程，2018，（03）：134-144.

[9]    吕顺利，杨济海，邓伟，等. Apriori-AHP 算法在电力通信网业务风险评估中的研究及应用[J].  计算机与数字工程，2018，46（4）：667-671.

[10]  尹军，李炅菊，黄宏光. 基于链路已用率的电力通信网脆弱性分析[J].  电力系统保护与控制，2018，46（2）：31-36.

[11]  WU X，KUMAR V，QUINLAN J R，et al. Top 10 algorithms in data mining[J].Knowledge & Information Systems，2008，14（ 1）：15-36.

[12]  Brite. http：//www.cs.bu.edu/brite/.