高鑫

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

關(guān)鍵詞故障定位；網(wǎng)絡(luò)管理；DVB-RCS；二分圖；故障傳播模型

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1671-7597（2014）12-0032-03

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

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

1基于二分圖的FPM

為基于二分圖的FPM，由故障節(jié)點(diǎn)集合F、癥狀節(jié)點(diǎn)集合S、邊集合組成。與均非空且，其中n表示故障節(jié)點(diǎn)的數(shù)量，m表示癥狀節(jié)點(diǎn)的數(shù)量。表示故障節(jié)點(diǎn)引發(fā)癥狀節(jié)點(diǎn)出現(xiàn)的因果關(guān)系。圖1表示了由3個(gè)故障節(jié)點(diǎn)和4個(gè)癥狀節(jié)點(diǎn)組成的基于二分圖的故障傳播模型。

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

2MCRA故障定位算法

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

2.1 相關(guān)概念定義及算法分析

設(shè)癥狀域，代表與癥狀相關(guān)聯(lián)的所有故障的集合；故障域，代表與相關(guān)聯(lián)的所有癥狀的集合。

定義1：故障在觀察到的癥狀節(jié)點(diǎn)集合中解釋癥狀數(shù)量與其在癥狀節(jié)點(diǎn)集合S中解釋癥狀數(shù)量的比值稱為癥狀覆蓋率，其表達(dá)式如式（1）所示。

（1）

MCRA故障定位算法的主要思想為：通過啟發(fā)式的探測(cè)策略，找出最有可能產(chǎn)生這些癥狀的故障，實(shí)現(xiàn)對(duì)的最小覆蓋；對(duì)癥狀域中每個(gè)故障求解癥狀覆蓋率，構(gòu)成集合，并按癥狀覆蓋率大小進(jìn)行排序。當(dāng)中前k個(gè)最大癥狀覆蓋率所對(duì)應(yīng)的故障完全覆蓋了可觀察到的癥狀時(shí)，就認(rèn)為找到了最小覆蓋集合。

MCRA故障定位算法對(duì)故障加入最小覆蓋集合的評(píng)估方法進(jìn)行了修改，由引發(fā)集合中出現(xiàn)癥狀的絕對(duì)數(shù)量轉(zhuǎn)變?yōu)槌霈F(xiàn)癥狀的比例，放大了集合中備選故障之間的差別。將加入至最小覆蓋集合之后，也未對(duì)所對(duì)應(yīng)的癥狀從中刪除。這兩方面可以避免絕對(duì)數(shù)量過少而使得絕對(duì)數(shù)量也過少，也避免了因?yàn)閯h除交叉癥狀引起后續(xù)備選故障選擇的誤差，從而導(dǎo)致故障被加入最小覆蓋集合之前而丟棄情況的發(fā)生。同時(shí)對(duì)中備選故障僅需要一次癥狀覆蓋率，降低了時(shí)間復(fù)雜度。

2.2 MCRA算法

執(zhí)行故障定位后的輸出能夠?qū)ψ龀鲎顑?yōu)解釋的故障假設(shè)集合H具有以下性質(zhì)：1）中的每個(gè)癥狀可被故障假設(shè)中的至少一個(gè)故障所解釋；2）故障假設(shè)集合H所包含的故障，具有可能產(chǎn)生中的癥狀。MCRA算法步驟如下：

Begin

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

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

；

3）對(duì)應(yīng)中的每一個(gè)故障，計(jì)算其癥狀覆蓋率，加入集合中；按癥狀覆蓋率對(duì)集合中故障降序排序；

4）依次取出循環(huán)執(zhí)行，直到；

獲取所對(duì)應(yīng)的；如果，則，；

5）輸出故障假設(shè)集合。

End

在最壞情況下，所有可觀察的癥狀都出現(xiàn)，即，每一個(gè)故障只能解釋一個(gè)癥狀，即。MCRA對(duì)求解一次癥狀覆蓋率，其時(shí)間復(fù)雜度為O（），較MCA故障定位算法降低了倍。實(shí)現(xiàn)了更快速地完成故障定位，可以將其應(yīng)用于實(shí)時(shí)系統(tǒng)的故障定位中。

3數(shù)值實(shí)例

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

（2）

（3）

其中，表示實(shí)際發(fā)生的故障集合，表示由故障定位算法所輸出的故障假設(shè)集合，表示故障場(chǎng)景中的仿真案例數(shù)量。

表1仿真模型參數(shù)

仿真參數(shù) 參數(shù)取值

節(jié)點(diǎn)之間距離d 集合{1，2，3，…，100}中隨機(jī)取值

仿真案例數(shù)量 500

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

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

網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量 10-100

OR 50%

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

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

按仿真場(chǎng)景參數(shù)取值來執(zhí)行仿真，圖2對(duì)MCRA、BSD以及MCA算法所取得的故障檢測(cè)率進(jìn)行了比較。由圖2可知，MCRA的故障檢測(cè)率為74.00%~99.80%，平均為96.87%；BSD的故障檢測(cè)率為76.67%~99.70%，平均為96.79%；MCA的故障檢測(cè)率為78.58%~95.93%，平均為92.10%。

endprint

圖2故障檢測(cè)率比較

圖3故障檢測(cè)率方差比較

按仿真場(chǎng)景參數(shù)取值來執(zhí)行仿真，圖3對(duì)MCRA、BSD以及MCA算法所取得的故障檢測(cè)率方差進(jìn)行了比較。由圖3可知，MCRA的故障檢測(cè)率方差為0.000602~0.088112，平均為0.0097；BSD的故障檢測(cè)率方差為0.001019~0.073509，平均為0.0099；MCA的故障檢測(cè)率為方差0.013985~0.069121，平均為0.0261。

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

圖4故障誤判率比較

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

4結(jié)論

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

參考文獻(xiàn)

[1]鄭秋華.網(wǎng)絡(luò)故障智能定位關(guān)鍵技術(shù)的研究[D].杭州：浙江大學(xué)，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]張成，廖建新，朱曉民.基于貝葉斯疑似度的啟發(fā)式故障定位算法[J].軟件學(xué)報(bào)，2010，21（10）：2610-2621.

[5]黃曉慧，鄒仕洪，褚靈偉，等.Internet服務(wù)故障管理：分層模型和算法[J].軟件學(xué)報(bào)，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故障檢測(cè)率比較

圖3故障檢測(cè)率方差比較

按仿真場(chǎng)景參數(shù)取值來執(zhí)行仿真，圖3對(duì)MCRA、BSD以及MCA算法所取得的故障檢測(cè)率方差進(jìn)行了比較。由圖3可知，MCRA的故障檢測(cè)率方差為0.000602~0.088112，平均為0.0097；BSD的故障檢測(cè)率方差為0.001019~0.073509，平均為0.0099；MCA的故障檢測(cè)率為方差0.013985~0.069121，平均為0.0261。

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

圖4故障誤判率比較

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

4結(jié)論

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

參考文獻(xiàn)

[1]鄭秋華.網(wǎng)絡(luò)故障智能定位關(guān)鍵技術(shù)的研究[D].杭州：浙江大學(xué)，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]張成，廖建新，朱曉民.基于貝葉斯疑似度的啟發(fā)式故障定位算法[J].軟件學(xué)報(bào)，2010，21（10）：2610-2621.

[5]黃曉慧，鄒仕洪，褚靈偉，等.Internet服務(wù)故障管理：分層模型和算法[J].軟件學(xué)報(bào)，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故障檢測(cè)率比較

圖3故障檢測(cè)率方差比較

按仿真場(chǎng)景參數(shù)取值來執(zhí)行仿真，圖3對(duì)MCRA、BSD以及MCA算法所取得的故障檢測(cè)率方差進(jìn)行了比較。由圖3可知，MCRA的故障檢測(cè)率方差為0.000602~0.088112，平均為0.0097；BSD的故障檢測(cè)率方差為0.001019~0.073509，平均為0.0099；MCA的故障檢測(cè)率為方差0.013985~0.069121，平均為0.0261。

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

圖4故障誤判率比較

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

4結(jié)論

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

參考文獻(xiàn)

[1]鄭秋華.網(wǎng)絡(luò)故障智能定位關(guān)鍵技術(shù)的研究[D].杭州：浙江大學(xué)，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]張成，廖建新，朱曉民.基于貝葉斯疑似度的啟發(fā)式故障定位算法[J].軟件學(xué)報(bào)，2010，21（10）：2610-2621.

[5]黃曉慧，鄒仕洪，褚靈偉，等.Internet服務(wù)故障管理：分層模型和算法[J].軟件學(xué)報(bào)，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