一种在支撑系统中使用无向环网识别算法识别传输环网结构的方法

郭 麟

（中国移动通信集团贵州有限公司，贵阳 550081）

1 现有技术的缺点及本申请提案要解决的技术问题

该技术方案就是要解决业务路径拓扑图中没有单独识别环网结构，无法在业务路径的环网出现单边运行情况下进行预警的问题，通过创新性方法，将数据库中基于业务绘制出的A、Z端连接信息，进行无向的识别绘制，最终识别出路径上存在的环网个数。

2 本方法的技术方案的详细阐述

2.1 算法思路

第一步，根据AZ端连接信息，画出无向图。

第二步，根据无向图，以邻接矩阵方式表示该无向图并存储。

第三步，从该无向图中，计算有邻接关系的次数（邻接数之和用字母S表示），将次数小于2的行删除形成新的矩阵。

第四步，在新的矩阵中将与被删除的行对应结点有邻接关系的列去掉，形成新的矩阵。

第五步，循环执行第四步，直到剩余的行其邻接数之和S都大于1时停止。

第六步，在剩余的矩阵中，各行为一个集合，用传统DFS优先深度搜索算法计算所有回路即可。

2.2 算法详细阐述

拓扑数据整理即无向图转化成邻接矩阵

（1）例如从传输EMS采集到的某传输光路拓扑如下：

图1

该图是一个典型的无向图，通过数据矩阵，我们可以将该无向图以邻接矩阵的方式进行存储，即将所有元素按任意顺序排列做为上标（用字母R表示），该排序的反序排列做为下标（用字母V表示），因此该拓扑无向图的邻接矩阵记为G（VR），矩阵中R与V有连接关系的用1表示，无连接关系用0表示，R与V中结点相同时用0表示。

图1中，R={B，C，A，D，E，F，I，G，H}，V={H，G，I，F，E，D，A，C，B}，其邻接矩阵为图2：

图2

（2）在该矩阵中，对每一行进行数字相加，得到下图：

图3

（3）图3中，去掉“邻接数之和少于2”的行，并按邻接数之和按倒序排列，留下的矩阵为：

图4

（4）在图3中，剔除的行为I，A，B，接下来，在图4中，我们将V与R的邻接关系凡是与被除的行有关联的邻接关系重新全记为0，（例：在去除的I，A，B行中，与此有关系的列有I-→F，A-→C，B→C，既然I、A、B元素已经排除不可能在回路中，因此，与该元素有关系的其他元素其连接关系可不计，因此置为零，即在剩下的行中，F行与I列的连接关系可置为0，C与A、B的连接关系可置为0）并重新记算“邻接数之和”，将值小于2的行再次删除，将重新按邻接数之和重新排序。重复该步骤，直到“邻接数之和”全大于1，此时得到矩阵图为：

图5

（5）此时，在图5中，V{f，d，h，g，e}将最有可能有回路即环。我们将V中各行以集合存储，即：

F={E，G}

D={E，H}

H={D，G}

G={F，H}

E={D，F}

（该集合可以理解为，F与E、G有连接关系，D与E、H有连接关系，H与D、G有连接关系，G与F、H有连接关系，E与D、F有连接关系）

（6）在得到的集合中，通过DFS优先搜索算法（该算法是一个传统无向图搜索算法，在此不在累赘），即可很快得到所有需要的回路即环，本例中计算的回路即环为（D，E，F，G，H，D），即下图：

绘制出的环网如下：

图6

（7）识别出来的SNCP环网存入数据库，可由目前各种主流的拓扑图呈现插件通过读取数据库中的环网数据后直接进行呈现。

最终系统中呈现效果为：

图7

2.3 本算法创新点

用传统DFS算法最大成本是：o（n!）n为元素个数。通过无向图邻接矩阵方式计算优化后，其成本节约为：o（（n-j）!）n为元素个数，j为不可能是环中结点的个数。

（1）成环识别流程图

（2）成环识别功能模块图

（3）实现基础

数据库具备专线业务光路路径数据，数据中必须包含A端网元、Z端网元、A端端口、Z端端口。

3 与现有技术相比，本申请提案有何技术优点

无需知晓环网方向，只需利用数据库中网元矩阵，通过几次筛选，即可得到具有连接关系的环网网元，直接绘制成环关系。

通过方案中的矩阵去掉一部分网元，减少计算数量，提高系统效率。

图8

图9

识别环网后，为后续业务路径中环网出现故障时，对业务单点运行进行准确判断和系统提升预警级别创造了技术条件。

本方案数据库使用MySQL，采用了数据库SQL语言进行抽数、JAVA语言编写计算逻辑，由上层拓扑图Qunee处理技术进行拓扑整合，使之具有了该优点。