文/劉迪 祚禹 劉庚 孟明磊（遼寧省煙草公司沈陽(yáng)市公司）

1.背景

隨著計(jì)算機(jī)與網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，計(jì)算機(jī)與網(wǎng)絡(luò)己經(jīng)成為當(dāng)今社會(huì)生產(chǎn)、生活必不可少的一部分，對(duì)社會(huì)經(jīng)濟(jì)的快速發(fā)展起著巨大的推動(dòng)作用。如何有效、合理的管理現(xiàn)代的大規(guī)模網(wǎng)絡(luò)，使網(wǎng)絡(luò)高效、可靠、安全的運(yùn)行是網(wǎng)絡(luò)管理領(lǐng)域所面臨的緊迫問(wèn)題。網(wǎng)絡(luò)故障診斷現(xiàn)在已經(jīng)成為一個(gè)迫切需要解決的問(wèn)題。

隨著網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大，網(wǎng)絡(luò)逐步向異構(gòu)性、動(dòng)態(tài)性與智能化的方向發(fā)展。這些變化對(duì)網(wǎng)絡(luò)故障診斷問(wèn)題也提出了越來(lái)越高的要求。故障診斷領(lǐng)域早在上世紀(jì)五、六十年代就有相關(guān)的研究，隨著上世紀(jì)五十年代計(jì)算機(jī)網(wǎng)絡(luò)的出現(xiàn)及網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大，網(wǎng)絡(luò)故障智能診斷領(lǐng)域也逐步進(jìn)行了不斷的探索與研究。國(guó)內(nèi)的網(wǎng)絡(luò)故障診斷領(lǐng)域的研究主要集中在把智能診斷技術(shù)與人工智能領(lǐng)域的相關(guān)知識(shí)相結(jié)合，以適應(yīng)網(wǎng)絡(luò)系統(tǒng)的不斷變化及現(xiàn)實(shí)需求。這些網(wǎng)絡(luò)故障診斷技術(shù)都有各自的優(yōu)點(diǎn)能解決特定的網(wǎng)絡(luò)環(huán)境中出的故障，但是這些方法也有各自缺點(diǎn)。

本文提出了考慮時(shí)間因素的基于關(guān)聯(lián)圖和案例庫(kù)的故障定位算法，此算法在關(guān)聯(lián)圖出現(xiàn)環(huán)路時(shí)考慮時(shí)間因素即當(dāng)關(guān)聯(lián)圖中出現(xiàn)環(huán)路時(shí)依據(jù)關(guān)聯(lián)圖中各頂點(diǎn)所代表的故障事件的發(fā)生時(shí)間定位故障，最早發(fā)生故障的事件很有可能就是故障源。

2.關(guān)聯(lián)圖算法

故障事件之間不是相互獨(dú)立的，這些故障事件之間是存在著一定關(guān)聯(lián)關(guān)系，例如一種故障事件是由另一種故障事件引起的。網(wǎng)絡(luò)故障事件之間的關(guān)系是可以用有向圖的形式表示的。有向圖的每個(gè)節(jié)點(diǎn)表示一個(gè)故障事件或一個(gè)故障事件集合，有向圖的弧，表示各個(gè)節(jié)點(diǎn)所代表的故障事件之間的關(guān)聯(lián)關(guān)系。入度為零的單事件頂點(diǎn)代表的網(wǎng)絡(luò)故障事件是相互獨(dú)立的而不是由其他網(wǎng)絡(luò)故障事件引發(fā)的，就是我們要找的可能的故障源。

假設(shè)U為某網(wǎng)絡(luò)中的全局故障事件，當(dāng)網(wǎng)絡(luò)故障定位模塊檢測(cè)到一個(gè)故障事件序列故障事件序列用本算法可得到對(duì)應(yīng)關(guān)聯(lián)圖的鄰接矩陣如下：

本文提出了考慮時(shí)間因素的基于關(guān)聯(lián)圖的網(wǎng)絡(luò)故障定位算法，此算法可以在關(guān)聯(lián)圖出現(xiàn)環(huán)時(shí)定位故障。算法的詳細(xì)描述如下：

·輸出：故障源集合S。

·步驟：

否則：如果每列都不全為0，則選擇這樣的一列對(duì)應(yīng)的頂點(diǎn)事件作為故障源：該列對(duì)應(yīng)的頂點(diǎn)為且中只有一個(gè)元素且則

步聚5：將此故障定位的發(fā)生故障事件序列、發(fā)生故障事件對(duì)應(yīng)的時(shí)間序列、故障定位的結(jié)果作為一個(gè)新案例加入到案例庫(kù)中

考慮時(shí)間因素的基于關(guān)聯(lián)圖和案例庫(kù)的故障定位算法可以解決帶環(huán)的關(guān)聯(lián)圖的故障定位問(wèn)題。根據(jù)故障發(fā)生的時(shí)間來(lái)定位故障，發(fā)生時(shí)間早的故障很有可能就是故障源。

3.算法實(shí)現(xiàn)

通過(guò)對(duì)以上的模擬，可以看出應(yīng)用此算法所得出的故障定位結(jié)論都是正確的。在實(shí)驗(yàn)中可以看出，考慮時(shí)間因素的基于關(guān)聯(lián)圖和案例庫(kù)的故障定位算法是能夠正確的進(jìn)行網(wǎng)絡(luò)故障定位的。

4.總結(jié)

本文針對(duì)網(wǎng)絡(luò)故障的傳播特性，在現(xiàn)有的網(wǎng)絡(luò)故障定位技術(shù)的基礎(chǔ)上給出了一種考慮時(shí)間因素的基于關(guān)聯(lián)圖和案例庫(kù)的故障定位算法。該算法在沒(méi)有專家知識(shí)支持的條件下，能夠準(zhǔn)確的隔離和定位故障源。同時(shí)算法能夠解決關(guān)聯(lián)圖出現(xiàn)環(huán)時(shí)的故障定位問(wèn)題且擁有較高的效率。通過(guò)實(shí)例的檢驗(yàn)，證明了該算法的可行性。