基于二分图模型的通信信息网络故障联合定位

崔力民，何清素，王俊生，石欣

（1.华北电力大学经济与管理学院，北京102206；2.国家电网新疆电力公司信息通信公司，新疆 乌鲁木齐 830018；3.国家电网电子商务有限公司，北京 100053）

基于二分图模型的通信信息网络故障联合定位

崔力民1,2，何清素3，王俊生3，石欣3

（1.华北电力大学经济与管理学院，北京102206；2.国家电网新疆电力公司信息通信公司，新疆 乌鲁木齐 830018；3.国家电网电子商务有限公司，北京 100053）

国家电网信息通信网络依靠两套运维系统，分别实现对信息网络与通信网络的故障定位与分析，然而通信网络故障往往会引发信息网络故障，如何高效精确地进行通信信息网络故障联合定位是亟需解决的问题。针对信息通信网络的联合故障定位问题，提出了基于二分图模型的故障联合定位算法。首先依据通信网网络节点的关联性对网络分簇，并将每一簇作为一个子域。其次在每个子域内建立基于二分图的故障关联影响模型，最终利用目标排序法并行地对多个子域内网络故障进行分析，从而实现通信信息网络关联故障高效精确的联合定位。实验结果表明，该联合故障定位分析方法的故障诊断率达85%～95%。

故障联合定位；网络分簇；二分图故障关联模型

1 引言

国家电网数据网络由信息网络与通信网络两部分组成，网络架构如图1所示，通信网主要负责信息的传输，信息网负责信息的处理。当前信息通信网络分别由不同的网络运维系统管理：通信网络运维通过通信网络管理系统实现，信息网络运维通过信息网络管理系统实现。然而通信网络故障往往会关联引发信息网络故障，从而导致网络异常时不能准确及时地定位故障源，确定故障影响范围。因此，分析通信网络与信息网络故障关联影响，实现高效准确的通信信息网络联合故障定位是十分必要的。

目前的故障定位算法有以下几种。

（1）基于故障依赖关系图的故障定位方法

杜晓丽等人[1]基于链路故障和节点故障之间的依赖关系改进了故障依赖图，并提出一种启发算法；He M[2]根据智能电网的马尔可夫网络模型中网络节点之间的依赖关系建立有向图，通过某一条件下马尔可夫网络的相关矩阵进行故障定位。

（2）基于贝叶斯网络的故障定位方法

邓歆等人[3]提出了通信网功能分层结构的思想，建立不同网络层次间的贝叶斯网络故障传播模型；王开选等人[4]指出了故障传播模型下的故障定位问题是NP（nondeterministic polynomial）难题，并提出一种启发式的最小损失故障定位算法。

（3）基于模糊逻辑推理的故障定位方法

曾飞等人[5]分析了时序推理与模糊推理应用于电力系统故障诊断的可行性，并构建了一种时序模糊逻辑推理故障定位模型；Yu L等人[6]提出了一种基于模糊理论的改进的遗传算法应用于分布式通信网络，该算法改善了传统故障定位中的由于信号传输失真造成的问题以及标准遗传算法中的过早收敛和收敛慢的问题。

（4）基于神经网络的故障定位方法

戚勇等人[7]通过建立前向多层神经网络模型（BP模型），通过样本对神经网络进行训练，根据期望输出与实际输出的差值，不断调节各神经元之间的连接权值，使实际的输出值以要求的精度逼近期望值；张禹[8]则采用了基于模糊神经网络的故障诊断方法，对故障告警信息进行模糊化后再对模糊化的数据进行神经网络训练。

（5）基于二分图模型的故障定位方法

赵灿明等人[9]采用了二分图模型考虑了通信网中故障位置对告警信息的影响，旨在解决大范围的故障告警下故障定位问题。

针对通信信息网络的大规模网络，建立贝叶斯网络模型复杂度高，求解最大可能解的计算复杂度也较高。另外建立神经网络故障诊断模型也需要经历较长时间的模型训练才能获得贴近实际情况的模型。模糊逻辑推理方法需要大量样本信息且假设条件过于苛刻。因此，上述方法都不适用于国家电网数据网络这样的大体量网络环境。其次，参考文献[6，8，9]只考虑了通信网络故障定位，并没有考虑故障传播影响所引发的联合网络故障定位问题。虽然参考文献[3]中提出建立了贝叶斯传播模型，但该模型是建立在同一网络不同网络层之间的故障传播模型。参考文献[9]中提出的二分图故障定位模型分析网络故障位置对告警信息的影响。该模型的两层结构适用于通信网络和信息网络之间的故障影响分析。综上所述，本文针对电网数据网络中通信网络和信息网络间的故障传播，利用二分图模型进行故障关联分析，实现不同网络间的故障联合定位，提高了故障定位的准确率，其方法可以归纳为以下几个步骤。

图1 国家电网信息通信网络结构

为了在提高故障定位准确性的同时提高网络故障定位分析的效率，本文首先对网络节点进行分簇处理，从而大大降低了相关故障定位模型规模以及问题求解时间；根据通信网络节点之间的故障关联度对网络进行分簇，将每一簇作为一个网络子域进行独立的网络故障分析。其次，针对每个网络子域建立二分图[10]故障关联分析模型。该模型依据通信信息网络的故障传播特性，以通信网故障节点作为根源故障层，以信息网故障节点作为关联故障层，通过源故障节点和关联故障节点之间的故障传播关联关系，实现通信信息网的联合定位。最后，利用目标排序法求解联合故障定位问题，实现信息通信网络间的高效准确的联合故障定位。

2 系统模型

本文针对国家电网当前的通信信息网络结构进行联合故障定位分析。信息网络与通信网络工作在网络协议的不同层：通信网络是信息传输的骨干网络，工作在网络物理层；而信息网络直接承载运行业务，工作在网络链路层、网络层。通信网络故障会关联引发信息网络故障。定义通信网络故障为源故障，而信息网络故障为关联故障。假设，在某时刻通信网中的源故障集合为 T=（T1，…，Tm，…，TM），其中 Tm表示该时刻通信网络层第 m个节点发生故障，M表示该时刻通信网络层发生的故障总数；而信息网的关联故障集合C=（C1，…，Cn，…，CN），其中 Cn表示该时刻信息网络层第 n个节点发生故障，N表示该时刻信息网络层发生的关联故障总数。联合故障定位的关键在于由信息网络关联故障集合状态，准确定位到引发该关联故障的通信网络源故障集合。

为了提高故障定位分析效率，首先通过网络分簇对通信信息网络节点进行划分。如图1所示，基于通信网络节点相关性将整体网络划分为若干子域。

图2 通信网信息网的分簇与故障影响

其次，针对通信网络故障对信息网络故障的关联影响，对每一个网络子域建立二分图故障关联模型。图2中箭头表明相关通信网络故障节点会关联引发信息网络故障。该模型参数可以通过历史网络故障信息统计得到，反映网络的真实故障关联关系。最后，根据已知条件，对通信信息网络联合故障定位问题进行建模求解。

3 基于分簇的网络子域划分

网络子域的划分基于对通信网络根源故障节点相关性的描述与定义。首先，利用二项集支持度[11]的定义，将通信网络节点间的相关性表示为：

其中，Aij表示通信网源故障节点 Ti和节点Tj在同一时间段发生故障的数目，A表示通信网络发生的故障的总数，该比值越大说明相关程度越高，反之则越低。若源故障节点 Ti和节点Tj经常发生通信行为，说明若一方发生故障则另一方会受到影响。用 Dij表示源故障节点 Ti和节点 Tj之间的通信次数，D表示通信网络中节点的总通信次数。同理，比值越大则关联性越高，否则关联性低。设置门限值 γ（0＜γ＜1），当 Cor（i，j）＞γ时，认为两个节点的相关性强，否则相关性弱，或者说不相关。

根据以上对通信网络节点相关性的定义，进一步定义通信网络节点关联度指示函数f：

每个节点的自身相关性强，因此，将每个节点其自身相关性定义为0，从而构建通信网络关联矩阵：

关联矩阵R为对称矩阵，第i行和第i列均表示节点i与其他节点之间的关联程度。进一步，本文定义了通信网络节点Tl的关联度：

当d（Tl）=0时，则通信网络节点Tl与其他的通信网络节点的关联度越高，反之，当d（Tl）数值越来越大时，则关联性较弱。根据通信网络节点关联度进行网络分簇的算法具体步骤如下。

步骤 1利用通信网络节点之间的关联度构建出关联矩阵R，初始化迭代因子h=1，孤立顶点集合分簇集合

步骤2找到所有d（tl）的节点，更新

步骤3剩余节点集合

步骤4分簇：

（1）判断R是否为全零矩阵，是则转向步骤（3），否则转向步骤（2）；

步骤5用顶点bh重新构造关联矩阵R，若R≠0且|bh|≠1，更新迭代因子h=h+1，转步骤3；否则Uh+1=bh。

步骤6将孤立顶点集合s中的顶点添加到每一簇中。

基于通信网络源故障节点分簇划分结果以及已知的通信网络与信息网络故障关联关系，将与每个簇源故障节点相关联的信息网络关联故障节点添加到簇中，形成包含通信网络节点与信息网络节点的完整网络分簇划分。该网络划分方法将通信信息网络关联性强的网络节点划分为一个网络子域，在每个子域中进行联合故障定位分析。

4 基于二分图的故障联合定位分析

二分图故障模型是一种故障因果关系模型，它不但可以准确描述通信网源故障节点和信息网关联故障节点的关联关系，而且模型简单易于求解。对每个网络子域建立故障关联二分图模型。如图3所示，该模型以通信网源故障节点作为根源故障层，以信息网关联故障节点作为关联故障层，通过源故障节点和关联故障节点之间的故障影响关联关系，实现通信信息网的联合故障定位。

图3 通信网信息网故障传播二分图模型

不失一般性，以任一网络子域为例讨论联合故障定位问题。假设在时刻t时某一子域内通信网的故障状态用源故障集合T=（T1，T2，…，TK）表示，K为这一时刻子域内通信网的故障总数。信息网的故障状态用关联故障集合C=（C1，C2，…，CG）表示，G为这一时刻子域内信息网的关联故障总数。通信网相关节点发生故障时，Ti取值为1，反之则取为0。同理，信息网络节点故障状态用Cj表示。

图2所示的二分图故障关联模型G（V，E）由3部分组成。首先，二分图下侧顶点表示通信网络源故障节点，即T⊂V；其次，二分图上侧顶点表示信息网络关联故障节点，即C⊂V；最后，边集合E包含通信网络节点指向信息网络节点的边，其指示通信网源故障节点对信息网关联故障的影响。设为边（Ti，Cj）的权重，表示通信网源故障节点Ti对信息网关联故障节点Cj的故障传播概率。图2给出了一个故障关联模型的具体实例。应用中可以由真实网络故障统计数据获得通信信息网故障关联二分图模型以及故障传播概率，因此该二分图故障关联模型具有较强的实际应用性。

在此二分图模型的基础上，联合故障定位问题可以表述为：在候选的通信网的源故障集中找到故障假设集合X，使得发生实际观察到的信息网的关联故障集H时，该故障假设发生的概率最大。

根据贝叶斯法则有：

因为P（H）为常数，所以式（7）可以化简为：

定义K维向量x，则源故障Ti与故障假设向量x的关系如下：

其中:

假设源故障x发生时，信息网关联故障发生的概率为：

得到该问题的目标函数：

为了方便计算将目标函数取对数可以表示为：

由于1n（1-pTi）的大小与未知数无关，可以直接消除，假设：

则目标函数最终转化为：

对于每一个信息网的关联故障集H，系统的最优诊断定位中应该至少包含一个通信网的源故障。源故障可以解释关联故障的前提是将作为矩阵元素构建源故障和关联故障的关联关系矩阵B。该矩阵的每一行表示一个关联故障 Cj对应的源故障（即这些故障可以导致该关联故障发生），该约束可以表示为：

最终该联合故障定位问题可以转化为下列最小化问题：

该问题为 0-1规划问题。其求解方法主要分为两类：一类是精确算法，如动态规划法、隐枚举法等；另一类是启发式算法，如贪心算法、遗传算法、模拟退火算法和拉格朗日松弛法等。贪心算法不一定能够保证求得最优解或次优解；遗传算法和模拟退火算法则具有计算量较大的缺点。

本文采用隐枚举法[12]中的目标排序法求解该问题。该方法不需要过滤条件，也略去了用过滤条件检验每个目标函数的工作。在用过滤法求出解集中各解点 z的基础上，将z值按大小排序，然后按 z值顺序检验各解的可行性，确保通过检验的第一个可行解即最优解。这种直接以z值大小顺序检验的解法，坚持了按序检验的优点，同时又消除了迂回排序和重复检验带来的困扰。具体算法分为以下3步。

步骤1求出解集中各解点的值。

步骤2然后将值按大小排序。

步骤3由于0-1规划问题是最小化问题，因此本文从值的最小解开始检验是否符合约束条件，第一个可行解就是目标函数的最优解。

5 仿真结果分析

仿真将故障诊断率[10]作为评价故障定位算法的指标参数。故障诊断率的定义为：

TP为故障发生后对故障进行正确诊断的概率，表示诊断方法的故障定位准确率。仿真选取国网新疆电力公司信息通信公司某一局域网网络维护系统的离线数据作为仿真数据。该仿真数据包含2015年10月1日网络维护中的320条告警数据以及20个根源故障。首先，使用该数据的故障事件集确定二分图模型故障关联影响参数。其次，使用得到的关联模型进行联合故障定位分析，将故障诊断结果与真实数据比较从而判断故障定位的准确性。产生仿真数据的局域网络包含30个网络节点，通过选取不同数目网络节点的相关数据从而改变仿真规模与设置。为了评价本文提出算法的故障诊断率，本文选取了网络故障诊断算法MLCP[5]进行比较。

图4为网络分簇与否的联合故障定位时间仿真结果。仿真中将全网划分为两个子域并分别进行联合故障定位分析。仿真结果显示，当节点数为28时，未分簇的联合故障定位时间近似为350 ms，而分簇的联合故障定位时间近似为150 ms，分簇后的处理速度为未分簇时的2.33倍。通过网络分簇，每个子域并行的进行故障定位分析，从而降低故障定位分析时间，提高分析效率。

图4 诊断时间比较

图5为本文所提出的联合故障定位算法在不同网络节点数时的诊断率TP。将本文提出的联合故障定位算法与MLCP定位算法进行比较。如图5所示，本文中的算法的诊断率明显优于MLCP定位算法。MLCP定位算法的诊断率的均值为0.68，方差为0.000 5；本文提出的算法的故障诊断率均值为0.948 2，方差为0.002 6，诊断率均值提升了26.82%。其次，MLCP定位算法的诊断率波动比较大，而本文的算法的诊断率则比较稳定。

图5 故障诊断性能比较

针对不同网络节点数，将本文提出的基于故障关联模型联合故障定位算法与基于非关联模型的传统故障定位方法进行了比较。图6中为两种方法分别得到的故障诊断率。其结果显示，基于关联模型的故障诊断率明显优于基于非关联模型的故障诊断方法。非关联模型的诊断率均值为0.710 3，方差为0.000 2。关联模型的诊断率的均值0.948 2，方差为0.002 6，关联模型的故障诊断率均值提升了33.49%。该结果表明，基于二分图故障关联模型的网络故障联合定位方法提高了信息通信网络联合故障定位准确率。

图6 关联模型与不关联模型故障诊断率比较

为了考察本文方法在一般网络环境中的应用性能，检测了该方法在不确定模型参数条件下的故障诊断率。选取20个网络节点作为仿真实验样本，首先使用网络故障数据确定故障关联模型以及关联影响参数。其次，针对得到的故障关联模型，假设模型中故障关联影响参数服从以值为期望的正态分布，并改变正态分布的方差值，从而模拟实际网络环境中的随机过程。在试验中以步长0.05分别测试了取值0.05～0.3的方差值，将故障诊断结果与实际数据比较得到不同参数下的故障诊断率，实验结果如图7所示。在不同参数方差条件下，该算法诊断率的均值仍高达83.83%，相比于MLCP定位算法，诊断率提升了23.27%，说明该算法适用于实际中包含随机事件的场景，并具有较高的故障诊断准确率。

图7 不同模型参数的故障诊断率

6 结束语

快速准确的网络故障定位对通信信息网络的运维有非常重大的意义。本文提出了一种基于二分图模型的通信信息网络联合故障定位模型。通过分簇将全网划分为多个子域，从而将故障定位局限在较小的范围内，缩减故障检测范围，提高故障定位效率。建立子域内的故障关联定位分析二分图网络故障关联模型，实现了通信信息网络的联合故障关联分析以及联合故障定位。通过仿真实验验证，本算法可以在通信信息网络中实现高效且准确的联合故障定位。

[1] 杜晓丽,朱程荣,熊齐邦.一种基于依赖图的故障定位算法[J].计算机应用,2004(24):67-69. DU X L,ZHU C R,XIONG Q B.A fault location algorithm based on dependency graph[J].Journalof Computer Applications, 2004(24):67-69.

[2]HE M,ZHANG J.A dependency graph approach for fault detection and localization towards secure smart grid[J].IEEE Transactions on Smart Grid,2011,2(2):342-351.

[3] 邓歆，孟洛明.基于贝叶斯网络的通信网告警相关性和故障诊断模型[J].电子与信息学报，2007（5）:1182-1186. DENG X,MENG L M.Bayesian networks based alarm correlation and fault diagnosis in communication networks[J].Journal of electronics&Information Technology,2007(5):1182-1186.

[4]王开选,杨峥,邱雪松,等.面向影响分析的电力通信网故障定位算法[J].北京邮电大学学报，2014(4). WANG K X,YANG Z,QIU X S,et al.Algorithm of fault locating on impact analysis in power communications network[J].Journal of Beijing University of Posts and Telecommunications,2014(4).

[5]曾飞,张勇,刘玙,等.电力系统故障诊断的时序模糊逻辑推理方法[J].华北电力大学学报(自然科学版),2014,41(1):7-14. ZENG F,ZHANG Y,LIU Y,et al.A temporal and fuzzy logic inference based method for power system fault diagnosis[J]. Journal of North China Electric Power University(Natural Science Edition),2014,41(1):7-14.

[6]YU L,SUN Y,LI K J,et al.An improved genetic algorithm based on fuzzy inference theory and its application in distribution network fault location[C]//2016 IEEE 11th Conference on Industrial Electronics and Applications (ICIEA),June 5-7,2016,Hefei, China.New Jersey:IEEE Press,2016:1411-1415.

[7]戚勇,李千目,刘凤玉.基于BP神经网络的网络智能诊断系统[J].微电子学与计算机,2004,21(10):10-13. QI Y,LIQ M,LIU F Y.Network fault intelligentdiagnosis base on BP neural network[J].Microelectronics&Computer,2004,21(10): 10-13.

[8]张禹．模糊神经网络在移动通信网故障诊断中的应用[D]．天津：天津理工大学，2010:22-32．ZHANG Y.The application of fuzzy neural network in mobile communication network fault diagnosis[D].Tianjin:Tianjin University of Technology,2010：22-32．

[9]赵灿明,李祝红,陶磊,等.基于故障传播模型与监督学习的电力通信网络故障定位[J].计算机应用,2016(4):905-908. ZHAO C M,LI Z H,TAO L,et al.Fault localization for electric power communication network based on fault propagation model and supervised learning[J].Journal of Computer Applications, 2016(4):905-908.

[10]杨娇.二分图网络故障传播模型与故障诊断算法研究[D].沈阳:东北大学，2011. YANG J.Bipartion Graph Fault Propagation Model and Diagnosis Algorithm[D].Shenyang:Northeastern University,2011.

[11]张敏，姚良威，侯宇.基于向量和矩阵的频繁项集挖掘算法研究[J].计算机工程与设计,2013,34(3):939-943. ZHANG M,YAO L W,HOU Y.Research of frequent itemsets mining algorithm based on vector and matrix[J].Computer Engineering and Design,2013,34(3):939-943.

[12]温大伟，谢文环.求解整数规划的一种隐枚举法 [J].数学教学研究,2012,31(11):60-61. WEN D W,XIE W H.An implicit enumeration method for solving integer programming[J].Journal of Mathematical Study, 2012,31(11):60-61.

Network fault location based on bipartite graphs for comm unication and inform ation networks

CUI Limin1,2,HE Qingsu3,WANG Junsheng3,SHI Xin3
1.College of Economics and Management,North China Electric Power University,Beijing 102206,China
2.China State Grid Xinjiang Information and Telecommunication Company,Urumqi 830018,China
3.State Grid Electronic Commerce Co.,Ltd.,Beijing 100053,China

The current State Grid communication and information networks rely on two separate network management systems.Such managementstructure brings challenges to network fault location,which calls for jointnetwork faultanalyze method.Grasping the transmission correlation of network nodes,a joint network fault location mechanism based on bipartite graph modelwas proposed.Firstly,network nodes were clustered into multiple sub-domains based on their fault correlation.Then,the bipartite graph faultcorrelation modelwas established foreach sub-domain.Finally,the targetsorting method was applied to locate network faults in every sub-domain simultaneously.Simulation experiments show that this method can locate network faults with high accuracy.

fault correlation location,network clustering,bipartite graph fault correlation model

TP393

：A

10.11959/j.issn.1000-0801.2017077

崔力民（1973-），男，华北电力大学经济与管理学院、国家电网新疆电力公司信息通信公司高级工程师，长期从事电力通信运行管理工作，主要研究方向为电力通信网评估。

何清素（1977-），男，国网电子商务有限公司高级工程师，主要研究方向为电力物联网、信息通信、电力系统自动化、能源互联网及产品研发等。

王俊生（1978-），男，国家电网电子商务有限公司工程师，主要研究方向为电力物联网、信息通信、电力系统自动化、能源互联网及产品研发等。

石欣（1992-），女，国家电网电子商务有限公司工程师，主要研究方向为信息通信、电力系统自动化、能源互联网等。

2016-11-22；

2017-02-17

何清素，heqingsu@sgec.sgcc.com.cn

国家电网公司科技项目“信息通信网络联合故障定位与交叉影响分析关键技术研究”（No.526802150008）

Foundation Item:The Science and Technology Projectof State Grid Corporation of China：The Research on the Key Technology of The Joint Fault Location and Cross Impact Analysis of Information and Communication Network(No.526802150008)