基于二分圖模型的通信信息網絡故障聯合定位

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

（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)