基于最大癥狀覆蓋率的故障定位算法

高鑫

摘要針對基于貝葉斯疑似度（Bayesian Suspected Degree，BSD）故障定位算法依賴于故障先驗概率和條件概率的缺陷，設計了基于最大癥狀覆蓋率（Maximum Covering Rate algorithm，MCRA）的故障定位算法。MCRA算法以二分圖作為故障傳播模型，引入了癥狀覆蓋率概念。通過啟發式的探測策略，對癥狀域中每個故障求解癥狀覆蓋率。如果前k個最大癥狀覆蓋率所對應的故障完全覆蓋可觀察癥狀集合時，則將這k個故障作為定位結果。MCRA突破了缺乏歷史故障統計與分析而無法獲取故障發生先驗概率和條件概率的限制，利用癥狀覆蓋率實現對貝葉斯疑似度的近似估計，實現在缺乏歷史故障統計數據故障定位中的應用。

關鍵詞故障定位；網絡管理；DVB-RCS；二分圖；故障傳播模型

中圖分類號：TP393 文獻標識碼：A 文章編號：1671-7597（2014）12-0032-03

故障定位是從癥狀和故障之間的非確定性對應關系推理出故障所在精確位置的過程。基于圖論的故障定位不受樣本條件的限制，成為一種有效的故障定位方法[1]，分為兩部分：故障傳播模型[2]（Fault Propagation Model，FPM）的建立和故障定位技術。二分圖作為一種特殊的因果圖[3]，簡化了故障與癥狀之間的耦合關系，具有較低的計算復雜度，因此采用基于二分圖的FPM。建立FPM之后將故障定位問題轉化為遍歷二分圖，從故障集合中尋找出對癥狀集合的最小覆蓋。現有求解癥狀集合最小覆蓋的故障定位算法[4-6]依賴于故障發生先驗概率和條件概率，而它們受歷史數據統計和專家主觀判斷的影響，使得這類算法無法適用于缺乏歷史統計數據的故障定位應用中。

借鑒貝葉斯疑似度算法（Bayesian Suspected Degree，BSD）[4]設計了基于最大癥狀覆蓋率（Maximum Covering Rate Algorithm，MCRA）算法，使得MCRA算法不依賴于故障發生先驗概率和條件概率。

1基于二分圖的FPM

為基于二分圖的FPM，由故障節點集合F、癥狀節點集合S、邊集合組成。與均非空且，其中n表示故障節點的數量，m表示癥狀節點的數量。表示故障節點引發癥狀節點出現的因果關系。圖1表示了由3個故障節點和4個癥狀節點組成的基于二分圖的故障傳播模型。

圖1基于二分圖的故障傳播模型

2MCRA故障定位算法

通過借鑒貝葉斯疑似度提出了癥狀覆蓋率的概念，使得MCRA具有和基于貝葉斯疑似度的求解癥狀集合最小覆蓋算法相同的時間復雜度。同時MCRA不依賴于故障先驗概率和條件概率，實現在缺乏歷史數據統計故障定位系統中應用。

2.1 相關概念定義及算法分析

設癥狀域，代表與癥狀相關聯的所有故障的集合；故障域，代表與相關聯的所有癥狀的集合。

定義1：故障在觀察到的癥狀節點集合中解釋癥狀數量與其在癥狀節點集合S中解釋癥狀數量的比值稱為癥狀覆蓋率，其表達式如式（1）所示。

（1）

MCRA故障定位算法的主要思想為：通過啟發式的探測策略，找出最有可能產生這些癥狀的故障，實現對的最小覆蓋；對癥狀域中每個故障求解癥狀覆蓋率，構成集合，并按癥狀覆蓋率大小進行排序。當中前k個最大癥狀覆蓋率所對應的故障完全覆蓋了可觀察到的癥狀時，就認為找到了最小覆蓋集合。

MCRA故障定位算法對故障加入最小覆蓋集合的評估方法進行了修改，由引發集合中出現癥狀的絕對數量轉變為出現癥狀的比例，放大了集合中備選故障之間的差別。將加入至最小覆蓋集合之后，也未對所對應的癥狀從中刪除。這兩方面可以避免絕對數量過少而使得絕對數量也過少，也避免了因為刪除交叉癥狀引起后續備選故障選擇的誤差，從而導致故障被加入最小覆蓋集合之前而丟棄情況的發生。同時對中備選故障僅需要一次癥狀覆蓋率，降低了時間復雜度。

2.2 MCRA算法

執行故障定位后的輸出能夠對做出最優解釋的故障假設集合H具有以下性質：1）中的每個癥狀可被故障假設中的至少一個故障所解釋；2）故障假設集合H所包含的故障，具有可能產生中的癥狀。MCRA算法步驟如下：

Begin

1）故障假設集合Φ，初始化癥狀集Φ；

2）找出中每一個癥狀的可能故障源，構成待選故障集合；

；

3）對應中的每一個故障，計算其癥狀覆蓋率，加入集合中；按癥狀覆蓋率對集合中故障降序排序；

4）依次取出循環執行，直到；

獲取所對應的；如果，則，；

5）輸出故障假設集合。

End

在最壞情況下，所有可觀察的癥狀都出現，即，每一個故障只能解釋一個癥狀，即。MCRA對求解一次癥狀覆蓋率，其時間復雜度為O（），較MCA故障定位算法降低了倍。實現了更快速地完成故障定位，可以將其應用于實時系統的故障定位中。

3數值實例

本節首先建立故障定位仿真模型，然后分別利用MCRA、BSD以及最大覆蓋故障定位算法（Max Covering Algorithm，MCA）來執行故障定位。對不同算法所產生結果進行比較，并分析其中的原因。采用檢測率（Detection Rate，DR）和檢測率方差（Variance of Detection Rate，VDR）來評估它們的性能，其定義如式（2）和式（3）：

（2）

（3）

其中，表示實際發生的故障集合，表示由故障定位算法所輸出的故障假設集合，表示故障場景中的仿真案例數量。

表1仿真模型參數

仿真參數 參數取值

節點之間距離d 集合{1，2，3，…，100}中隨機取值

仿真案例數量 500

故障發生概率 服從[0.001，0.01]的均勻分布

故障與癥狀之間的條件概率 服從（0，1）的均勻分布

網絡節點數量 10-100

OR 50%

故障定位仿真模型運行在配置為1.8GHz Inter（R） Core（TM）2 Duo CPU和內存為2.0GB的計算機中進行，其參數如表1所示。首先隨機產生包含n個節點的無向網絡G，網絡G中邊的權值隨機產生，表示節點之間的距離d。利用普里姆（Kruskal）算法求出網絡G的最小生成樹，利用迪杰斯特拉（Dijkstra）算法求出最小生成樹中任意兩節點之間的路徑，得出路徑矩陣。網絡G中的邊稱為鏈路（Link），根據路徑矩陣可知一條路徑由多個鏈路構成。如果一條鏈路出現中斷，則導致了多條路徑出現異常。因此，將鏈路中斷表示為故障，而將路徑的異常現象表示為癥狀。顯然，一個故障的發生將引起多個癥狀的出現。在網絡G中，故障總數量為，癥狀總數量為。然后通過遍歷路徑矩陣，確定故障集合F與癥狀集合S之間的映射關系，建立基于二分圖的FPM 。故障發生概率和故障和癥狀之間的條件概率都隨機產生。

在每一個仿真案例中，隨機選擇故障集合作為發生的故障，設定集合包括實際發生故障數量為1，2，3，4，6的比例為30%，25%，20%，15%，10%。從癥狀集合S中隨機選取實際能夠觀察到的癥狀集合表示為可觀察癥狀集合，故障觀察率（OR）為。從所有癥狀中隨機選擇個癥狀構成可觀察癥狀集合，之后取與中故障可引發癥狀的集合的交集，構成實際癥狀集合。分別利用MCRA、BSD以及MCA算法來確定故障原因，并分析不同故障定位算法的性能。

按仿真場景參數取值來執行仿真，圖2對MCRA、BSD以及MCA算法所取得的故障檢測率進行了比較。由圖2可知，MCRA的故障檢測率為74.00%~99.80%，平均為96.87%；BSD的故障檢測率為76.67%~99.70%，平均為96.79%；MCA的故障檢測率為78.58%~95.93%，平均為92.10%。

endprint

圖2故障檢測率比較

圖3故障檢測率方差比較

按仿真場景參數取值來執行仿真，圖3對MCRA、BSD以及MCA算法所取得的故障檢測率方差進行了比較。由圖3可知，MCRA的故障檢測率方差為0.000602~0.088112，平均為0.0097；BSD的故障檢測率方差為0.001019~0.073509，平均為0.0099；MCA的故障檢測率為方差0.013985~0.069121，平均為0.0261。

圖4給出了故障誤判率的比較結果。由某一故障而引發對應癥狀出現的數量具有一定的不確定性，而所引發癥狀也具有一定的隨機性。MCRA在無法獲取故障發生的先驗概率和條件概率的條件下，通過計算癥狀覆蓋率來評估每個故障發生的可能性，實現了與BSD近似相同的故障檢測率。同時在集合中不刪除故障可以解釋的癥狀，直到覆蓋整個為止，避免了因為刪除交叉癥狀引起后續備選故障選擇的誤差。MCA算法只找出解釋癥狀數量最多的故障加入至故障假設集合，只是考慮了出現癥狀的絕對數量；從中刪除symptom（f）的形成新的，直至，影響了后續備選故障的準確選擇。在仿真場景中任意數量網絡節點的情況下，MCRA和BSD算法的故障檢測率始終高于MCR算法的故障檢測率。

圖4故障誤判率比較

盡管在實際系統中無法準確獲取故障發生的先驗概率和轉移概率，但BSD算法得出的故障檢測率和誤判率可以作為一種理論極限。MCRA通過計算癥狀覆蓋率來代替貝葉斯疑似度，盡管在故障檢測率方面可以實現和BSD算法一樣的性能，但其故障檢測率變化幅度也相對較大。原因是由于MCRA算法未考慮故障發生的先驗概率和轉移概率，得到最小覆蓋集合所包括故障的數量多于BSD。

4結論

本文通過引入癥狀覆蓋率而提出了以二分圖作為故障傳播模型的MCRA故障定位算法。MCRA利用癥狀覆蓋率實現對貝葉斯疑似度的近似估計， 避免了依賴故障發生先驗概率和條件概率的限制。如何將MCRA與主動故障定位技術相結合，利用探針來提升故障檢測率并降低誤檢率成為下一步的研究內容。

參考文獻

[1]鄭秋華.網絡故障智能定位關鍵技術的研究[D].杭州：浙江大學，2007.

[2]Steinder M， Sethi A S. Probabilistic Event-driven Fault Diagnosis Through Incremental Hypothesis Updating. IFIP/IEEE International Symposium on Integrated Network Management （IM）， Colorado Springs， USA， March 24-28，2003.

[3]Yemini S， Kliger A， Mozes S， et al. High Speed and Robust Event Correlation. Communications Magazine， 1996，34（5）：82-90.

[4]張成，廖建新，朱曉民.基于貝葉斯疑似度的啟發式故障定位算法[J].軟件學報，2010，21（10）：2610-2621.

[5]黃曉慧，鄒仕洪，褚靈偉，等.Internet服務故障管理：分層模型和算法[J].軟件學報，2007，18（10）：2584-2594.

[6]Steinder M， Sethi A S. Probabilistic Fault Localization in Communication Systems Using Belief Networks. IEEE/ACM Transactions on Networking，2004，12（5）：809-822.

endprint

圖2故障檢測率比較

圖3故障檢測率方差比較

按仿真場景參數取值來執行仿真，圖3對MCRA、BSD以及MCA算法所取得的故障檢測率方差進行了比較。由圖3可知，MCRA的故障檢測率方差為0.000602~0.088112，平均為0.0097；BSD的故障檢測率方差為0.001019~0.073509，平均為0.0099；MCA的故障檢測率為方差0.013985~0.069121，平均為0.0261。

圖4給出了故障誤判率的比較結果。由某一故障而引發對應癥狀出現的數量具有一定的不確定性，而所引發癥狀也具有一定的隨機性。MCRA在無法獲取故障發生的先驗概率和條件概率的條件下，通過計算癥狀覆蓋率來評估每個故障發生的可能性，實現了與BSD近似相同的故障檢測率。同時在集合中不刪除故障可以解釋的癥狀，直到覆蓋整個為止，避免了因為刪除交叉癥狀引起后續備選故障選擇的誤差。MCA算法只找出解釋癥狀數量最多的故障加入至故障假設集合，只是考慮了出現癥狀的絕對數量；從中刪除symptom（f）的形成新的，直至，影響了后續備選故障的準確選擇。在仿真場景中任意數量網絡節點的情況下，MCRA和BSD算法的故障檢測率始終高于MCR算法的故障檢測率。

圖4故障誤判率比較

盡管在實際系統中無法準確獲取故障發生的先驗概率和轉移概率，但BSD算法得出的故障檢測率和誤判率可以作為一種理論極限。MCRA通過計算癥狀覆蓋率來代替貝葉斯疑似度，盡管在故障檢測率方面可以實現和BSD算法一樣的性能，但其故障檢測率變化幅度也相對較大。原因是由于MCRA算法未考慮故障發生的先驗概率和轉移概率，得到最小覆蓋集合所包括故障的數量多于BSD。

4結論

本文通過引入癥狀覆蓋率而提出了以二分圖作為故障傳播模型的MCRA故障定位算法。MCRA利用癥狀覆蓋率實現對貝葉斯疑似度的近似估計， 避免了依賴故障發生先驗概率和條件概率的限制。如何將MCRA與主動故障定位技術相結合，利用探針來提升故障檢測率并降低誤檢率成為下一步的研究內容。

參考文獻

[1]鄭秋華.網絡故障智能定位關鍵技術的研究[D].杭州：浙江大學，2007.

[2]Steinder M， Sethi A S. Probabilistic Event-driven Fault Diagnosis Through Incremental Hypothesis Updating. IFIP/IEEE International Symposium on Integrated Network Management （IM）， Colorado Springs， USA， March 24-28，2003.

[3]Yemini S， Kliger A， Mozes S， et al. High Speed and Robust Event Correlation. Communications Magazine， 1996，34（5）：82-90.

[4]張成，廖建新，朱曉民.基于貝葉斯疑似度的啟發式故障定位算法[J].軟件學報，2010，21（10）：2610-2621.

[5]黃曉慧，鄒仕洪，褚靈偉，等.Internet服務故障管理：分層模型和算法[J].軟件學報，2007，18（10）：2584-2594.

[6]Steinder M， Sethi A S. Probabilistic Fault Localization in Communication Systems Using Belief Networks. IEEE/ACM Transactions on Networking，2004，12（5）：809-822.

endprint

圖2故障檢測率比較

圖3故障檢測率方差比較

按仿真場景參數取值來執行仿真，圖3對MCRA、BSD以及MCA算法所取得的故障檢測率方差進行了比較。由圖3可知，MCRA的故障檢測率方差為0.000602~0.088112，平均為0.0097；BSD的故障檢測率方差為0.001019~0.073509，平均為0.0099；MCA的故障檢測率為方差0.013985~0.069121，平均為0.0261。

圖4給出了故障誤判率的比較結果。由某一故障而引發對應癥狀出現的數量具有一定的不確定性，而所引發癥狀也具有一定的隨機性。MCRA在無法獲取故障發生的先驗概率和條件概率的條件下，通過計算癥狀覆蓋率來評估每個故障發生的可能性，實現了與BSD近似相同的故障檢測率。同時在集合中不刪除故障可以解釋的癥狀，直到覆蓋整個為止，避免了因為刪除交叉癥狀引起后續備選故障選擇的誤差。MCA算法只找出解釋癥狀數量最多的故障加入至故障假設集合，只是考慮了出現癥狀的絕對數量；從中刪除symptom（f）的形成新的，直至，影響了后續備選故障的準確選擇。在仿真場景中任意數量網絡節點的情況下，MCRA和BSD算法的故障檢測率始終高于MCR算法的故障檢測率。

圖4故障誤判率比較

盡管在實際系統中無法準確獲取故障發生的先驗概率和轉移概率，但BSD算法得出的故障檢測率和誤判率可以作為一種理論極限。MCRA通過計算癥狀覆蓋率來代替貝葉斯疑似度，盡管在故障檢測率方面可以實現和BSD算法一樣的性能，但其故障檢測率變化幅度也相對較大。原因是由于MCRA算法未考慮故障發生的先驗概率和轉移概率，得到最小覆蓋集合所包括故障的數量多于BSD。

4結論

本文通過引入癥狀覆蓋率而提出了以二分圖作為故障傳播模型的MCRA故障定位算法。MCRA利用癥狀覆蓋率實現對貝葉斯疑似度的近似估計， 避免了依賴故障發生先驗概率和條件概率的限制。如何將MCRA與主動故障定位技術相結合，利用探針來提升故障檢測率并降低誤檢率成為下一步的研究內容。

參考文獻

[1]鄭秋華.網絡故障智能定位關鍵技術的研究[D].杭州：浙江大學，2007.

[2]Steinder M， Sethi A S. Probabilistic Event-driven Fault Diagnosis Through Incremental Hypothesis Updating. IFIP/IEEE International Symposium on Integrated Network Management （IM）， Colorado Springs， USA， March 24-28，2003.

[3]Yemini S， Kliger A， Mozes S， et al. High Speed and Robust Event Correlation. Communications Magazine， 1996，34（5）：82-90.

[4]張成，廖建新，朱曉民.基于貝葉斯疑似度的啟發式故障定位算法[J].軟件學報，2010，21（10）：2610-2621.

[5]黃曉慧，鄒仕洪，褚靈偉，等.Internet服務故障管理：分層模型和算法[J].軟件學報，2007，18（10）：2584-2594.

[6]Steinder M， Sethi A S. Probabilistic Fault Localization in Communication Systems Using Belief Networks. IEEE/ACM Transactions on Networking，2004，12（5）：809-822.

endprint