一種在支撐系統(tǒng)中使用無向環(huán)網識別算法識別傳輸環(huán)網結構的方法

郭 麟

（中國移動通信集團貴州有限公司，貴陽 550081）

1 現(xiàn)有技術的缺點及本申請?zhí)岚敢鉀Q的技術問題

該技術方案就是要解決業(yè)務路徑拓撲圖中沒有單獨識別環(huán)網結構，無法在業(yè)務路徑的環(huán)網出現(xiàn)單邊運行情況下進行預警的問題，通過創(chuàng)新性方法，將數(shù)據庫中基于業(yè)務繪制出的A、Z端連接信息，進行無向的識別繪制，最終識別出路徑上存在的環(huán)網個數(shù)。

2 本方法的技術方案的詳細闡述

2.1 算法思路

第一步，根據AZ端連接信息，畫出無向圖。

第二步，根據無向圖，以鄰接矩陣方式表示該無向圖并存儲。

第三步，從該無向圖中，計算有鄰接關系的次數(shù)（鄰接數(shù)之和用字母S表示），將次數(shù)小于2的行刪除形成新的矩陣。

第四步，在新的矩陣中將與被刪除的行對應結點有鄰接關系的列去掉，形成新的矩陣。

第五步，循環(huán)執(zhí)行第四步，直到剩余的行其鄰接數(shù)之和S都大于1時停止。

第六步，在剩余的矩陣中，各行為一個集合，用傳統(tǒng)DFS優(yōu)先深度搜索算法計算所有回路即可。

2.2 算法詳細闡述

拓撲數(shù)據整理即無向圖轉化成鄰接矩陣

（1）例如從傳輸EMS采集到的某傳輸光路拓撲如下：

圖1

該圖是一個典型的無向圖，通過數(shù)據矩陣，我們可以將該無向圖以鄰接矩陣的方式進行存儲，即將所有元素按任意順序排列做為上標（用字母R表示），該排序的反序排列做為下標（用字母V表示），因此該拓撲無向圖的鄰接矩陣記為G（VR），矩陣中R與V有連接關系的用1表示，無連接關系用0表示，R與V中結點相同時用0表示。

圖1中，R={B，C，A，D，E，F(xiàn)，I，G，H}，V={H，G，I，F(xiàn)，E，D，A，C，B}，其鄰接矩陣為圖2：

圖2

（2）在該矩陣中，對每一行進行數(shù)字相加，得到下圖：

圖3

（3）圖3中，去掉“鄰接數(shù)之和少于2”的行，并按鄰接數(shù)之和按倒序排列，留下的矩陣為：

圖4

（4）在圖3中，剔除的行為I，A，B，接下來，在圖4中，我們將V與R的鄰接關系凡是與被除的行有關聯(lián)的鄰接關系重新全記為0，（例：在去除的I，A，B行中，與此有關系的列有I-→F，A-→C，B→C，既然I、A、B元素已經排除不可能在回路中，因此，與該元素有關系的其他元素其連接關系可不計，因此置為零，即在剩下的行中，F(xiàn)行與I列的連接關系可置為0，C與A、B的連接關系可置為0）并重新記算“鄰接數(shù)之和”，將值小于2的行再次刪除，將重新按鄰接數(shù)之和重新排序。重復該步驟，直到“鄰接數(shù)之和”全大于1，此時得到矩陣圖為：

圖5

（5）此時，在圖5中，V{f，d，h，g，e}將最有可能有回路即環(huán)。我們將V中各行以集合存儲，即：

F={E，G}

D={E，H}

H={D，G}

G={F，H}

E={D，F(xiàn)}

（該集合可以理解為，F(xiàn)與E、G有連接關系，D與E、H有連接關系，H與D、G有連接關系，G與F、H有連接關系，E與D、F有連接關系）

（6）在得到的集合中，通過DFS優(yōu)先搜索算法（該算法是一個傳統(tǒng)無向圖搜索算法，在此不在累贅），即可很快得到所有需要的回路即環(huán)，本例中計算的回路即環(huán)為（D，E，F(xiàn)，G，H，D），即下圖：

繪制出的環(huán)網如下：

圖6

（7）識別出來的SNCP環(huán)網存入數(shù)據庫，可由目前各種主流的拓撲圖呈現(xiàn)插件通過讀取數(shù)據庫中的環(huán)網數(shù)據后直接進行呈現(xiàn)。

最終系統(tǒng)中呈現(xiàn)效果為：

圖7

2.3 本算法創(chuàng)新點

用傳統(tǒng)DFS算法最大成本是：o（n!）n為元素個數(shù)。通過無向圖鄰接矩陣方式計算優(yōu)化后，其成本節(jié)約為：o（（n-j）!）n為元素個數(shù)，j為不可能是環(huán)中結點的個數(shù)。

（1）成環(huán)識別流程圖

（2）成環(huán)識別功能模塊圖

（3）實現(xiàn)基礎

數(shù)據庫具備專線業(yè)務光路路徑數(shù)據，數(shù)據中必須包含A端網元、Z端網元、A端端口、Z端端口。

3 與現(xiàn)有技術相比，本申請?zhí)岚赣泻渭夹g優(yōu)點

無需知曉環(huán)網方向，只需利用數(shù)據庫中網元矩陣，通過幾次篩選，即可得到具有連接關系的環(huán)網網元，直接繪制成環(huán)關系。

通過方案中的矩陣去掉一部分網元，減少計算數(shù)量，提高系統(tǒng)效率。

圖8

圖9

識別環(huán)網后，為后續(xù)業(yè)務路徑中環(huán)網出現(xiàn)故障時，對業(yè)務單點運行進行準確判斷和系統(tǒng)提升預警級別創(chuàng)造了技術條件。

本方案數(shù)據庫使用MySQL，采用了數(shù)據庫SQL語言進行抽數(shù)、JAVA語言編寫計算邏輯，由上層拓撲圖Qunee處理技術進行拓撲整合，使之具有了該優(yōu)點。