計算機網絡中的故障定位研究

周暢

摘 要：隨著信息技術的快速發展，計算機網絡日趨復雜，故障定位技術作為網絡管理的核心一直是研究的熱點。由于網絡的互聯性，網絡故障存在著一定的關聯，而計算機網絡故障定位則是需要依據事件的相互關系，從多個故障事件中定位故障源。提出專家系統技術，基于主動輪詢技術，基于拓撲結構，圖論技術對此課題展開研究，并且詳細介紹了基于蟻群的高效優化算法，大大提高了工作效率，為之后的故障定位技術的研究有著重要的借鑒意義。

關鍵詞：故障定位；專家系統技術；網絡拓撲結構；圖論；蟻群算法

中圖分類號：TP393.0 文獻標識碼：A

1 引言（Introduction）

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

2 專家系統技術（The expert system technology）

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

2.1 規則庫系統

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

2.2 案例庫系統

案例庫系統是專家系統的一個特殊類別。基于經驗以及過去情況，它試圖通過之前解決方案的相關信息去處理被提出的問題。當一個問題被解決時，解決方案可以被用來解決后續的問題。然而，在解決過程中需要一個應用程序特定的模型，以及效率低可能使我們不能用于報警相關。

2.3 決策樹

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

3 主動輪詢技術（Active polling technology）

主動輪詢技術是網絡管理過程中主動去輪流查詢整個計算機網絡中設備的各個狀態，即去訪問簡單網絡管理協議代理的信息管理庫，并且等待系統響應。如果所得的返回結果正常，則只是簡單的將查詢結果存檔。但是如果等到超時，還是沒有結果，則是系統發生故障，需要管理員發出告警信息，進行故障定位。

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

voidCSnmpWnd：：OnTimer（UINT nIDEvent）

{CWnd：：OnTimer（nIDEvent）；

m_GetSnmpHistoryList.AddString（strAsyncGetRequest

（m_strOid））；}

主動輪詢技術具有全面，可靠收集網絡信息的特點，可以發現網絡故障，進行診斷和定位。但是雖然所掌握的網絡參數以及狀態全面，但是耗時長。在準備階段必須權衡故障查詢速度與所占網絡帶寬。顯然，故障查詢速度越快，網絡帶寬消耗越大，將會直接影響到通信系統地正常運行。

4 網絡拓撲結構（Topological structure）

為了實現故障定位，我們將故障定位系統的體系結構分為四個模塊，分別為拓撲發現、告警收集、告警關聯及故障定位模塊。

拓撲發現模塊的目的是用于自動發現單個管理域，以及Internet主干網絡拓撲，并且盡可能減少對網絡的假設條件。按發現拓撲圖的方法可分為三種。一是基于探測程序，通過開發專門的探針程序分布在計算機網絡中，在程序之間相互測量，從而獲得一些關于網絡拓撲的信息。二是利用一些通用協議構建拓撲圖。三是利用網絡設備保存的實際數據，其中利用SNMP協議獲得網絡設備中保存的MIB數據構造拓撲圖是非常有效的拓撲發現方法。

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

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

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

5 圖論技術（Gragh theory）

圖形理論技術依賴于一個系統圖形模型，該模型被稱為故障傳播模型。該故障傳播模型包括所有故障及發生在系統中故障癥狀的全部體現，其中的節點表示故障癥狀。故障傳播模型采用因果圖與依賴圖的形式。

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

5.1 上下文無關法

上下文無關法是允許從子表達式中構建表達式，即從已定義的對象中構建出復合網絡對象，從而用于分層組織通信系統。對于有限類的上下無關模型的定位故障源問題在語義上等價于依賴圖模型，可以被轉換為0—1整數線性規劃問題。

5.2 碼本技術

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

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

5.3 貝葉斯置信網模型

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

貝葉斯網絡是一種網絡變量關系的直接表示，而不是推理過程。因此，有向邊所指的方向是真正的關系方向，而不是推理過程的流向。

6 蟻群高效優化算法（Highly efficient optimization

algorithm based on ant colony）

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

我們的算法不同于現有的網絡故障研究定位技術，因為它結合了主動與被動測量，通過發送與終止數據來檢測故障，以及用主動測量來定位故障。蟻群優化相對于其他的主動測量都要好，因為螞蟻可以智能行動，因此可以更加高效的定位故障節點[1]。

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

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

根據以上描述，對于每個節點的故障概率為pi，通過方程式（1）得到。其中N是出現的網絡節點的總數。對于每個節點可以通過方程式（2）獲得mi，mi是數組的節點。在等式（2）中S（j，i）表示第j個數組的第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）

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

（3）

（4）

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

一般來說，信息素被全局或局部更新所改變，即當螞蟻從一個節點轉移到另一節點時，信息素依據等式（4）所更新。

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

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

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

7 結論（Conclusion）

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

參考文獻（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-），女，本科生.研究領域：通信工程.