二分圖網(wǎng)絡故障傳播模型與故障診斷算法研究.pdf

1、隨著信息技術的不斷發(fā)展，計算機網(wǎng)絡故障管理日益重要。網(wǎng)絡故障診斷是網(wǎng)絡管理的核心部分。如何提高網(wǎng)絡故障診斷能力，實現(xiàn)高效準確的故障診斷，對降低網(wǎng)絡維護成本以及提高系統(tǒng)服務的可靠性非常重要。本文以實現(xiàn)高效的網(wǎng)絡故障診斷為目標，針對網(wǎng)絡中存在大量故障傳播的特點，進行了故障傳播模型、故障診斷算法的研究與改進。
　　首先，對網(wǎng)絡中出現(xiàn)的故障傳播現(xiàn)象做了研究，本文利用拓撲排序與廣度優(yōu)先搜索的思想去除傳統(tǒng)因果圖故障傳播模型中的冗余信息。并引進

2、分層診斷思想，提出了自頂而下的分層二分圖故障傳播模型。本模型改善了傳統(tǒng)模型計算量大、模型復雜等缺點。
　　其次，針對不同網(wǎng)絡規(guī)模和要求提出兩種不同的故障診斷算法。將啟發(fā)式思想引入遞歸故障診斷算法中，提出了基于啟發(fā)式改進遞歸故障診斷算法;該算法不但可靠性高而且克服了傳統(tǒng)遞歸故障診斷算法時間復雜度高的缺點。但隨著網(wǎng)絡節(jié)點增加，基于啟發(fā)式故障診斷算法的診斷時間大幅度增加，不適用于大規(guī)模網(wǎng)絡環(huán)境。通過對故障診斷問題目標函數(shù)變化，將故障診斷

3、問題轉化為0-1整數(shù)規(guī)劃問題。拉格朗日算法是有效解決0-1優(yōu)化問題的方法之一，進而提出了基于故障傳播模型的拉格朗日診斷算法(LDA，Lagrangian Diagnosis Algorithm)，通過仿真實驗分析，表明LDA具有準確性高、用時少、適用于大規(guī)模網(wǎng)絡系統(tǒng)的特點。而啟發(fā)式改進遞歸故障診斷算法適用于診斷可靠性要求高的中小規(guī)模網(wǎng)絡系統(tǒng)。
　　最后，在此基礎上建立起一套具有故障診斷能力的網(wǎng)絡故障診斷系統(tǒng)。系統(tǒng)采用分布式體系結構