周暢

摘 要：隨著信息技術(shù)的快速發(fā)展，計算機網(wǎng)絡(luò)日趨復(fù)雜，故障定位技術(shù)作為網(wǎng)絡(luò)管理的核心一直是研究的熱點。由于網(wǎng)絡(luò)的互聯(lián)性，網(wǎng)絡(luò)故障存在著一定的關(guān)聯(lián)，而計算機網(wǎng)絡(luò)故障定位則是需要依據(jù)事件的相互關(guān)系，從多個故障事件中定位故障源。提出專家系統(tǒng)技術(shù)，基于主動輪詢技術(shù)，基于拓?fù)浣Y(jié)構(gòu)，圖論技術(shù)對此課題展開研究，并且詳細(xì)介紹了基于蟻群的高效優(yōu)化算法，大大提高了工作效率，為之后的故障定位技術(shù)的研究有著重要的借鑒意義。

關(guān)鍵詞：故障定位；專家系統(tǒng)技術(shù)；網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)；圖論；蟻群算法

中圖分類號：TP393.0 文獻(xiàn)標(biāo)識碼：A

1 引言（Introduction）

隨著各路網(wǎng)絡(luò)應(yīng)用的興起，用戶對于服務(wù)質(zhì)量有著更高的要求。最關(guān)鍵問題之一就是維護計算機網(wǎng)絡(luò)的可靠性。在計算機網(wǎng)絡(luò)中故障是不可避免的，因此立即定位與處理是十分關(guān)鍵的[1]。故障管理過程通常分為四個階段：故障檢測、故障定位、修理和測試。其中的故障定位是為了解釋報警而分析的一系列故障暗示，準(zhǔn)確地發(fā)現(xiàn)故障的位置[2]。為了提高網(wǎng)絡(luò)的可靠性，能夠迅速，準(zhǔn)確地定位故障尤為重要。盡管前人對故障定位技術(shù)進(jìn)行了不懈的研究，這些方法是從計算機科學(xué)的不同領(lǐng)域衍生出來的，包括人工智能、神經(jīng)網(wǎng)絡(luò)、信息論和自動化理論。但目前為止在復(fù)雜的通信系統(tǒng)中故障定位仍然是一個難題，還有許多問題有待于解決，本文則通過研究多種分析方法來實現(xiàn)故障定位。

2 專家系統(tǒng)技術(shù)（The expert system technology）

在故障定位和診斷中應(yīng)用最為廣泛的就是專家系統(tǒng)技術(shù)。專家系統(tǒng)試圖去反應(yīng)人類專家的行為，它們基于模仿一個人的，可能是從經(jīng)驗，或是基于它們的原則去理解系統(tǒng)行為。

2.1 規(guī)則庫系統(tǒng)

僅僅依賴表面知識的方法是基于規(guī)則的推理系統(tǒng)，它不需要去深入理解底層系統(tǒng)結(jié)構(gòu)和操作原則。所以對于小系統(tǒng)而言，它則可以提供一個強有力的工具去消除最不可能的假設(shè)。但是規(guī)則庫系統(tǒng)也有許多缺點，例如難以更新知識，以及難以維持。因為通常系統(tǒng)包括硬編碼的網(wǎng)絡(luò)配置，基于觀察得出的統(tǒng)計數(shù)據(jù)雖然已經(jīng)自動派生出相關(guān)規(guī)則，但是當(dāng)系統(tǒng)配置被改變時一定會再生出大部分的相關(guān)規(guī)則，可見規(guī)則庫系統(tǒng)是效率低下的和不能處理不精確的情況。缺乏結(jié)構(gòu)的規(guī)則庫系統(tǒng)通常很難允許使用在分層構(gòu)建的分布式系統(tǒng)中。

2.2 案例庫系統(tǒng)

案例庫系統(tǒng)是專家系統(tǒng)的一個特殊類別?；诮?jīng)驗以及過去情況，它試圖通過之前解決方案的相關(guān)信息去處理被提出的問題。當(dāng)一個問題被解決時，解決方案可以被用來解決后續(xù)的問題。然而，在解決過程中需要一個應(yīng)用程序特定的模型，以及效率低可能使我們不能用于報警相關(guān)。

2.3 決策樹

決策樹是通過用戶觀察到的癥狀去定位問題的根本原因的方法。它是對于專家知識的一個簡單表達(dá)性的展現(xiàn)。然而，它的使用性受限于具體應(yīng)用，以及因存在噪聲使其準(zhǔn)確度退化。

3 主動輪詢技術(shù)（Active polling technology）

主動輪詢技術(shù)是網(wǎng)絡(luò)管理過程中主動去輪流查詢整個計算機網(wǎng)絡(luò)中設(shè)備的各個狀態(tài)，即去訪問簡單網(wǎng)絡(luò)管理協(xié)議代理的信息管理庫，并且等待系統(tǒng)響應(yīng)。如果所得的返回結(jié)果正常，則只是簡單的將查詢結(jié)果存檔。但是如果等到超時，還是沒有結(jié)果，則是系統(tǒng)發(fā)生故障，需要管理員發(fā)出告警信息，進(jìn)行故障定位。

其中的定時輪詢用到了VC中MFC類庫中的窗口時間事件響應(yīng)函數(shù)，即CSnmpWnd：：OnTimer（UINT nIDEvent）。在窗口的初始化函數(shù)BOOL OnInitDialog（）中添加實現(xiàn)函數(shù)SetTimer（nIDEvent，time，NULL）來設(shè)定輪流查詢的周期，接著在事件函數(shù)中添加輪流查詢的具體代碼，如下：

voidCSnmpWnd：：OnTimer（UINT nIDEvent）

{CWnd：：OnTimer（nIDEvent）；

m_GetSnmpHistoryList.AddString（strAsyncGetRequest

（m_strOid））；}

主動輪詢技術(shù)具有全面，可靠收集網(wǎng)絡(luò)信息的特點，可以發(fā)現(xiàn)網(wǎng)絡(luò)故障，進(jìn)行診斷和定位。但是雖然所掌握的網(wǎng)絡(luò)參數(shù)以及狀態(tài)全面，但是耗時長。在準(zhǔn)備階段必須權(quán)衡故障查詢速度與所占網(wǎng)絡(luò)帶寬。顯然，故障查詢速度越快，網(wǎng)絡(luò)帶寬消耗越大，將會直接影響到通信系統(tǒng)地正常運行。

4 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)（Topological structure）

為了實現(xiàn)故障定位，我們將故障定位系統(tǒng)的體系結(jié)構(gòu)分為四個模塊，分別為拓?fù)浒l(fā)現(xiàn)、告警收集、告警關(guān)聯(lián)及故障定位模塊。

拓?fù)浒l(fā)現(xiàn)模塊的目的是用于自動發(fā)現(xiàn)單個管理域，以及Internet主干網(wǎng)絡(luò)拓?fù)?，并且盡可能減少對網(wǎng)絡(luò)的假設(shè)條件。按發(fā)現(xiàn)拓?fù)鋱D的方法可分為三種。一是基于探測程序，通過開發(fā)專門的探針程序分布在計算機網(wǎng)絡(luò)中，在程序之間相互測量，從而獲得一些關(guān)于網(wǎng)絡(luò)拓?fù)涞男畔?。二是利用一些通用協(xié)議構(gòu)建拓?fù)鋱D。三是利用網(wǎng)絡(luò)設(shè)備保存的實際數(shù)據(jù)，其中利用SNMP協(xié)議獲得網(wǎng)絡(luò)設(shè)備中保存的MIB數(shù)據(jù)構(gòu)造拓?fù)鋱D是非常有效的拓?fù)浒l(fā)現(xiàn)方法。

當(dāng)一個網(wǎng)絡(luò)設(shè)備發(fā)生故障時，可產(chǎn)生大量的告警信息。這些告警信息可以用于故障定位?？墒钱?dāng)告警過多致使網(wǎng)絡(luò)管理中心癱瘓時，就需要使用某種機制減少告警信息，因此告警相關(guān)的出現(xiàn)解決了這個問題。告警關(guān)聯(lián)則是通過告警信息在時間與空間上進(jìn)行相關(guān)處理，從而減少告警信息數(shù)，大大減少了網(wǎng)絡(luò)故障修復(fù)的時間。告警關(guān)聯(lián)從時間與空間兩個方面展開。時間方面是針對每一個告警攜帶的時間戳，從時間序列角度關(guān)聯(lián)各個告警序列。而空間方面則是從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中關(guān)聯(lián)告警序列。因此，可以通過依賴搜索樹模型實現(xiàn)告警關(guān)聯(lián)。其主要思想是根據(jù)各節(jié)點的依賴關(guān)系，將網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)構(gòu)造成樹狀結(jié)構(gòu)，其中樹狀結(jié)構(gòu)中的每一個節(jié)點都記錄著與其直接依賴節(jié)點的相關(guān)信息。而由于計算機網(wǎng)絡(luò)拓?fù)涞膹?fù)雜性，往往構(gòu)造出的樹狀是森林。但對于特定的計算機網(wǎng)絡(luò)而言，樹狀結(jié)構(gòu)變化非常小，因而我們可以將此作為搜索節(jié)點信息的依據(jù)，從而得到其中隱藏拓?fù)浣Y(jié)構(gòu)中的信息。

接著運用貪心算法來處理告警信息，實現(xiàn)故障定位。貪心算法的核心思想則是通過問題的局部最優(yōu)解來解決整個問題的最優(yōu)解，即先將一組數(shù)據(jù)排序找出最優(yōu)值，進(jìn)行分析處理，再找出最優(yōu)值，進(jìn)行分析處理，直到得到最期望的結(jié)果，找到告警信息的最佳解釋，從而實現(xiàn)故障定位的目的。

根據(jù)目前的網(wǎng)絡(luò)管理協(xié)議（如SNMP），每個征兆被獨立報告，并且由于一個故障源可能導(dǎo)致大量故障征兆，所以很難在大量征兆中找到故障源。我們發(fā)現(xiàn)大量的告警信息之間存在相關(guān)性，于是對告警信息進(jìn)行關(guān)聯(lián)處理之后，再進(jìn)行故障定位。此方法為計算機網(wǎng)絡(luò)提供可靠性高，實用性強的網(wǎng)管平臺，對于故障定位方面具有重要的意義。

5 圖論技術(shù)（Gragh theory）

圖形理論技術(shù)依賴于一個系統(tǒng)圖形模型，該模型被稱為故障傳播模型。該故障傳播模型包括所有故障及發(fā)生在系統(tǒng)中故障癥狀的全部體現(xiàn)，其中的節(jié)點表示故障癥狀。故障傳播模型采用因果圖與依賴圖的形式。

因果關(guān)系圖是一個有向無環(huán)圖Gc（E，C），其節(jié)點E表示事件及邊緣C表示事件之間的因果關(guān)系。邊（ei，ej）∈C表示事件ei引起事件ej的事實，被表示為ei→ej。因果圖中的邊可以通過因果的概率被標(biāo)記。而依賴圖是有向圖G=（O，D），其中O是有限的非空集合的對象，D是對象之間的一組邊。有向邊（oi，oj）∈D表示oi中的錯誤或故障可能導(dǎo)致oj中的錯誤的事實，同樣可以在邊上設(shè)置概率值來表現(xiàn)其依賴強度。

5.1 上下文無關(guān)法

上下文無關(guān)法是允許從子表達(dá)式中構(gòu)建表達(dá)式，即從已定義的對象中構(gòu)建出復(fù)合網(wǎng)絡(luò)對象，從而用于分層組織通信系統(tǒng)。對于有限類的上下無關(guān)模型的定位故障源問題在語義上等價于依賴圖模型，可以被轉(zhuǎn)換為0—1整數(shù)線性規(guī)劃問題。

5.2 碼本技術(shù)

碼本技術(shù)的故障傳播模型是由問題碼的矩陣表示。在確定性技術(shù)中，碼字是由0、1序列組成。第i個位置的碼字1表示問題pj與癥狀si的因果關(guān)系。碼本技術(shù)中認(rèn)為數(shù)據(jù)是在一個離散無記憶有損信道上進(jìn)行傳播，其輸入的字母表是一組最優(yōu)化代碼以及輸出的字母表是一組所有可能癥狀的集合。有了這樣的解釋，相關(guān)事件等效于將一個已經(jīng)收到的輸出符號解碼成有效的輸入符號。在相關(guān)事件問題中已經(jīng)收到的符號也來自于{0，1}序列，其中1表示出現(xiàn)特定癥狀，而0則表示沒有觀察到特定癥狀。信道錯誤導(dǎo)致癥狀丟失或是虛假，碼本以及解碼方案決定了可被檢測和糾正的錯誤數(shù)量。

碼本技術(shù)運用最小符號距離作為決策方案。在概率模型中，d（a，b）表示兩個概率a，b∈[0，1]之間的距離，被計算為log（a/b）。其中l(wèi)og（0/0）=0和log（a/0）=a。一旦執(zhí)行編碼，碼本技術(shù)是非常有效的。然而，它的計算復(fù)雜度被（k+1）log（p）所限制，其中k是解碼階段被矯正的錯誤數(shù)目，p是故障的數(shù)量。當(dāng)有多個故障產(chǎn)生，或是發(fā)生重疊時，碼本技術(shù)的精確度很難被預(yù)測。此外，由于配置系統(tǒng)的改變需要再生碼本，可見這是一個耗時的過程，因此，碼本技術(shù)不適用于動態(tài)改變依賴關(guān)系的環(huán)境。

5.3 貝葉斯置信網(wǎng)模型

基于傳感器數(shù)據(jù)以及人們的感知信息的貝葉斯網(wǎng)絡(luò)是固定的，每個貝葉斯網(wǎng)絡(luò)包括兩層：故障層和故障癥狀層[3]。貝葉斯在2015年提出了一種基于信號觀察與在正常情況下信號重建之間差異的故障診斷的研究[4]。并且貝葉斯置信網(wǎng)對于故障定位也有重要意義。貝葉斯置信網(wǎng)實際上是基于概率的不確定性推理網(wǎng)絡(luò)，其網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)就是用概率來表示變量之間相互關(guān)系的有向無環(huán)圖。其中節(jié)點表示變量，有向邊則表示變量之間的相互關(guān)系。貝葉斯也提出：在推理過程中，知識并不是以聯(lián)合概率分布形式表現(xiàn)的，而是以變量之間的相關(guān)性和條件相關(guān)性表現(xiàn)的，即用條件概率表示。在故障定位中，根據(jù)Pearl理論，對節(jié)點x={x1，…，xi，…，xn}的概率P（x）可以表示為xi與其父節(jié)點之間一系列條件概率與邊緣分布的乘積，即

貝葉斯網(wǎng)絡(luò)是一種網(wǎng)絡(luò)變量關(guān)系的直接表示，而不是推理過程。因此，有向邊所指的方向是真正的關(guān)系方向，而不是推理過程的流向。

6 蟻群高效優(yōu)化算法（Highly efficient optimization

algorithm based on ant colony）

在這一節(jié)中，針對計算機網(wǎng)絡(luò)故障定位，一種基于蟻群的高效優(yōu)化算法被提出。最近，在解決工程問題中，群集智能的方法引起了廣泛的關(guān)注，基于連接的蟻群優(yōu)化也已經(jīng)成功應(yīng)用到工程領(lǐng)域的研究中。蟻群優(yōu)化是一個多代理系統(tǒng)，他有許多功能。例如分布式長期記憶的使用，強化學(xué)習(xí)模式的相似功能，以及基于隨機組件的一種整體與局部的搜索能力。

我們的算法不同于現(xiàn)有的網(wǎng)絡(luò)故障研究定位技術(shù)，因為它結(jié)合了主動與被動測量，通過發(fā)送與終止數(shù)據(jù)來檢測故障，以及用主動測量來定位故障。蟻群優(yōu)化相對于其他的主動測量都要好，因為螞蟻可以智能行動，因此可以更加高效的定位故障節(jié)點[1]。

考慮一個網(wǎng)絡(luò)，數(shù)據(jù)從客戶端發(fā)送到服務(wù)器，于是我們考慮到端的數(shù)據(jù)就可檢測網(wǎng)絡(luò)中的故障組件[5]。在所提到的算法中主要有兩個方面。第一，一組節(jié)點作為目標(biāo)節(jié)點（服務(wù)器）和一組節(jié)點作為源（客戶端），然后基于主動測量選擇一組節(jié)點移動到目標(biāo)節(jié)點。在目標(biāo)節(jié)點中通過螞蟻估計每個節(jié)點的故障。第二，候選節(jié)點通過被動測量被用于測試。下面將對每一步做詳細(xì)的說明。

將一個或多個服務(wù)器視為目標(biāo)節(jié)點，以及客戶端被認(rèn)為源節(jié)點，源節(jié)點被認(rèn)為是螞蟻的巢，螞蟻需要移動到服務(wù)器。每個螞蟻由二進(jìn)制數(shù)組組成，數(shù)組的長度是所有網(wǎng)絡(luò)節(jié)點的數(shù)量。數(shù)組的每一個元素表示網(wǎng)絡(luò)中的節(jié)點，這些元素僅由0、1兩個數(shù)值表示。當(dāng)一個螞蟻從源節(jié)點移動到目標(biāo)節(jié)點，過程中通過的每一個節(jié)點的值在數(shù)組中都等于1。在圖1中，有一個目標(biāo)節(jié)點（D=1）和三個源節(jié)點（S=3），以及七個在它們之間的節(jié)點（N=7）。一共有五只螞蟻，分別為a1、a2、a3、a4、a5?？梢钥闯鑫浵伒臄?shù)量由源節(jié)點上輸出邊的數(shù)量決定。當(dāng)螞蟻通過一個節(jié)點時，螞蟻數(shù)組就被刷新。當(dāng)螞蟻到達(dá)目標(biāo)節(jié)點時將有五個數(shù)組，為{A1，…，A5}。用S1={a1，a2}，S2={a3，a4}和S3={a5}分別表示每個螞蟻屬于的一個源（S1、S2或S3），從一個公共源出發(fā)的螞蟻進(jìn)行OR邏輯運算符操作。因此，在上面的例子中將有三個數(shù)組。圖2展現(xiàn)的是OR操作符之后的數(shù)組，即每個數(shù)組表示同一個源的一系列節(jié)點。

根據(jù)以上描述，對于每個節(jié)點的故障概率為pi，通過方程式（1）得到。其中N是出現(xiàn)的網(wǎng)絡(luò)節(jié)點的總數(shù)。對于每個節(jié)點可以通過方程式（2）獲得mi，mi是數(shù)組的節(jié)點。在等式（2）中S（j，i）表示第j個數(shù)組的第j個元素。例如，在等式（2）中，m1=2，m2=1，m3=1，m4=1，m5=1，m6=1和m7=2。通過等式（1）可以計算出P1=0.22，P2=0.11，P3=0.11，P4=0.11，P5=0.11，P6=0.11和P7=0.22。

（1）

（2）

在計算出故障概率后，應(yīng)用蟻群優(yōu)化選擇最佳節(jié)點用于測試。螞蟻開始從客戶端（源節(jié)點）到服務(wù)器（目標(biāo)節(jié)點），一個基于故障概率為pi及節(jié)點上具有信息素的螞蟻需要選擇將要移動到的下一個節(jié)點。由于故障概率與信息素互相依賴，所以螞蟻可以依照以下兩個標(biāo)準(zhǔn)去選擇接下來的節(jié)點：（1）第i個節(jié)點的故障概率；（2）在下一個節(jié)點的信息素濃度。首先，假設(shè)所有節(jié)點的信息素濃度都相同，于是可以基于等式（3），螞蟻選擇具有最高p的下一步去移動。

（3）

（4）

信息素（ni）表示第i個節(jié)點上信息素的濃度。B是衡量信息素與pi相關(guān)性的參數(shù)。q是以[0，1]均勻分布下被隨機選擇的值。q0（0≤q0≤1）是一個參數(shù)，是針對有高概率pi與高信息素的節(jié)點。S是螞蟻k選擇移動到下一節(jié)點的概率。

一般來說，信息素被全局或局部更新所改變，即當(dāng)螞蟻從一個節(jié)點轉(zhuǎn)移到另一節(jié)點時，信息素依據(jù)等式（4）所更新。

phermone（ni）=（1-）.phermone（ni）+.pi （5）

在等式（5）中，是0與1之間的數(shù)。如果=1，則信息素更新取決于故障概率。如果=0，那么信息素的更新取決于在ni信息素的濃度。在0與1之間取值，該值決定了故障概率與ni信息素濃度對于信息素的影響強度。

蟻群算法結(jié)束后，具有更多信息素的節(jié)點被選為測試。確定蟻群算法的最后條件是在每次巡回（螞蟻從客戶端到服務(wù)器叫一次巡回）的最后，信息素的濃度是否有影響。如果節(jié)點上的信息素在幾次連續(xù)重復(fù)中沒有改變，則應(yīng)該被停止，從而選擇一個具有更高信息素濃度的節(jié)點。本文所提出的蟻群算法可以在迭代中運行直到所有的故障組件被定位。圖3展現(xiàn)了蟻群算法的流程圖。

7 結(jié)論（Conclusion）

隨著計算機網(wǎng)絡(luò)應(yīng)用的大規(guī)模普及，網(wǎng)絡(luò)已經(jīng)成為我們生活中不可或缺的設(shè)備。與此同時，網(wǎng)絡(luò)的復(fù)雜性也日益加大，因此檢測定位并排除故障，保障用戶網(wǎng)絡(luò)安全與通暢尤為重要。本文提出了基于專家系統(tǒng)技術(shù)、主動輪詢、網(wǎng)絡(luò)拓?fù)?、圖論的故障定位方法，并且著重討論了一種基于蟻群的高效優(yōu)化算法。利用蟻群算法良好的正反饋與容錯性的特點，對復(fù)雜的計算機網(wǎng)絡(luò)進(jìn)行故障定位。該算法大大減少了操作者的運算量，并且使網(wǎng)絡(luò)管理速率大幅度提高。

參考文獻(xiàn)（References）

[1] GARSHASBI M S.Fault Localization Based on Combines Active and Passive Measurements in Computer Networks by Ant Colony Optimization[J].Reliability Engineering and System Safety，2016，152：205-212.

[2] Bing W，et al.Fault Localization Using Passiveend-to-End Measurement Sand Sequential Testing for Wireless Sensor Networks[J].IEEE Trans Mobile Comput，2012，11：439-452.

[3] CaiB，et al.Multi-Source Information Fusion Based Fault Diagnosis of Ground-Source Heat Pump Using Bayesian Network[J].Apply Energy，2014，114：1-9.

[4] BaraldiP，et al.Comparison of Data-Driven Reconstruction Methods for Fault Detection[J].Reliab，IEEE Trans，2015，64（3）：852-860.

[5] SteinderM，AdarshpalS.Probabilistic Fault Localization in Communication Systems Using Belief Networks[J].IEEE/ACM Trans Netw，2004，12：809-821.

作者簡介：

周 暢（1996-），女，本科生.研究領(lǐng)域：通信工程.