包宋建

（重慶文理學(xué)院 電子電氣工程學(xué)院，重慶 402160）

0 引言

光網(wǎng)絡(luò)故障的識別和定位是極其重要的，現(xiàn)有的一些故障定位算法主要有Rete算法、數(shù)據(jù)挖掘算法、圖論里的相關(guān)算法等，但是這些算法對于OBS網(wǎng)絡(luò)而言，缺乏適用性。本文提出了基于探測圈覆蓋的光突發(fā)交換網(wǎng)絡(luò)故障定位方案。該方案分為2個階段：1）收集由故障觸發(fā)的告警信息，組成相應(yīng)的二進(jìn)制告警相關(guān)矩陣；2）采用預(yù)計算的方式，利用告警矩陣進(jìn)行定位，能在兼顧漏告警和誤告警的情況下解決多故障定位問題，找到可能的故障設(shè)備集合，進(jìn)行有效定位。

1 OBS網(wǎng)絡(luò)設(shè)備告警能力分析

對OBS網(wǎng)絡(luò)硬件設(shè)備告警能力分析主要根據(jù)故障發(fā)生時網(wǎng)絡(luò)硬件設(shè)備的反應(yīng)狀況定義。在對硬件設(shè)備的告警能力分析時，主要考慮以下3個特性[1]：

1）自身告警。擁有此特性的設(shè)備可以發(fā)出關(guān)于自身硬故障的告警。

2）外部告警。擁有此特性的設(shè)備可以與管理器進(jìn)行通信，發(fā)出關(guān)于外部其他設(shè)備的故障告警。

3）硬故障屏蔽。擁有此特性的設(shè)備可以屏蔽后面的硬件設(shè)備硬故障。

對光網(wǎng)絡(luò)中硬件設(shè)備具體分類如表1所示。從上面的分析可以看出，在OBS網(wǎng)絡(luò)中，當(dāng)某些網(wǎng)絡(luò)器件發(fā)生故障的時候就有可能產(chǎn)生漏告警以及誤告警的情況，所以在下面的故障定位算法中，考慮了漏告警和誤告警的情況，這樣能夠使網(wǎng)絡(luò)管理者快速有效地定位OBS網(wǎng)絡(luò)故障，并執(zhí)行OBS網(wǎng)絡(luò)故障管理措施，使得整個OBS網(wǎng)絡(luò)有效有序傳輸。

表1 OBS網(wǎng)絡(luò)硬件設(shè)備告警能力

2 OBS網(wǎng)絡(luò)中故障探測和定位算法

在OBS網(wǎng)絡(luò)中，無論是單一故障還是多故障都能被告警器探測到并發(fā)出警報，為了降低故障管理的復(fù)雜度和成本，盡量用最少的監(jiān)視設(shè)備來監(jiān)視整個OBS網(wǎng)絡(luò)元素。干擾告警（誤告警和漏告警）的出現(xiàn)會使得故障定位的難度加大，對此，故障定位方案主要分為2個步驟：1）探測和收集OBS網(wǎng)絡(luò)元素的各種告警信息；2）應(yīng)用提到的故障定位算法，最后得到可能發(fā)生故障的OBS網(wǎng)絡(luò)故障設(shè)備集合。具體流程如圖1所示。

在收到來自監(jiān)視設(shè)備的告警后，無論告警的類型如何，故障定位算法都將運行，把剛收到的告警信息與預(yù)先計算出來的告警矩陣進(jìn)行比較，在這個比較過程中將產(chǎn)生可能發(fā)生故障的OBS網(wǎng)絡(luò)故障設(shè)備集合，然后對發(fā)出和接收的信號進(jìn)行處理和分析，從此集合中確定準(zhǔn)確的故障設(shè)備。

2.1 基于m2圈的OBS網(wǎng)絡(luò)鏈路故障定位算法

在監(jiān)測范圍內(nèi)的OBS網(wǎng)絡(luò)元素?zé)o論何時發(fā)生故障，監(jiān)視設(shè)備都將產(chǎn)生告警。但是OBS網(wǎng)絡(luò)中也經(jīng)常受到錯誤告警和漏告警的干擾，原因在其監(jiān)視設(shè)備中的門限值較低或其在監(jiān)視設(shè)備中的門限值較高[2]。在圖G(V,E)中，鏈路ei∈E(i=1,2,…,L)和m2圈cj兩者的關(guān)系可以定義為一個二進(jìn)制編碼aij表示

每一條鏈路ei對應(yīng)的所有m2圈就可以得到相關(guān)聯(lián)的編碼ai=(ai1,ai2,…,aiM)，此外對于發(fā)生故障時所觸發(fā)的告警mj與m2圈cj也可以得到以下關(guān)系

這樣，所有m2圈的告警編碼就可以表示為m=(m1,m2,…,mM)。一旦接受到m2圈中的告警，那么告警編碼隨即產(chǎn)生。比較告警編碼mj與每條鏈路所相關(guān)的編碼aij，如果鏈路相關(guān)編碼和告警編碼吻合，那么這條鏈路就是故障候選鏈路之一，兩者的比較關(guān)系用異或關(guān)系來衡量，表示為

式中：i=1,2,…,L，如果Fi為0，那么鏈路ei就是告警編碼m=(m1,m2,…,mM)的一個候選故障點。按照以上方法檢查完所有的鏈路相關(guān)編碼aij后，就獲得所有的告警候選集合?？梢灶A(yù)先列舉出所有可能的告警編碼mj，建立相應(yīng)的故障告警集合，當(dāng)故障發(fā)生時可以直接進(jìn)行對比定位，所以這種算法可以節(jié)省大量的故障定位時間。

2.2 OBS網(wǎng)絡(luò)節(jié)點故障定位算法

生存性實施的故障定位只需將故障定位到資源即可[3]。資源是相對于業(yè)務(wù)而言的。下面介紹一種故障定位機制，在這個機制之中C代表所有OBS網(wǎng)絡(luò)器件的集合，M代表所有監(jiān)視器集合，OBS光網(wǎng)絡(luò)器件v的一個告警域（當(dāng)v發(fā)生故障時，引起告警的所有監(jiān)視設(shè)備集合）用Domain(v)表示。定義響鈴的監(jiān)視設(shè)備集合用MR表示（MR?M）。同理，定義MS為沒有響鈴的監(jiān)視設(shè)備集合（MS=M/MR）。設(shè)定C ′是C的一個子集，MA(C ′)為在沒有誤告警和漏告警的情況下，C′中的所有設(shè)備發(fā)生故障時監(jiān)視器都會正常發(fā)出告警。那么當(dāng)告警產(chǎn)生干擾的情況下，MA(C ′)≠MR。誤告警可表示為MF(C ′)=MR/MA(C ′)。同理可得，漏告警可表示為MM(C ′)=MS?MA(C ′)。多故障定位的目標(biāo)就是在覆蓋告警矩陣中所有響鈴的告警（即在告警矩陣中為1的告警）而不是未響鈴告警（即在告警矩陣中為0的告警），盡量使得最終的故障設(shè)備集合最小，達(dá)到精確定位的目的。所以本文想找到C的一個子集C′，其中故障設(shè)備集| |C′的數(shù)量盡量最小，并且沒有誤告警時，上述情況滿足MF(C′)=φ；沒有漏告警的情況滿足MM(C′)=φ。在定位算法中，需要考慮以下4種情況：

1）沒有誤告警和漏告警的故障定位問題

其實在理想情況下的多故障定位問題等同于一個集覆蓋問題（set cover問題），而集覆蓋問題又是一個完全NP問題[4]。為了解決這個問題，本文借鑒集覆蓋中的自適應(yīng)貪婪優(yōu)化算法來對多故障進(jìn)行定位，此算法在告警矩陣中反復(fù)逐一選取告警域中包括最多響鈴告警的故障設(shè)備。

對任意一個OBS網(wǎng)絡(luò)拓?fù)洌紫韧ㄟ^探測圈發(fā)現(xiàn)算法得到一個告警矩陣，然后對其運行故障定位算法，并滿足條件Domain(c)?MR。對于多故障的情況，把收到的告警編碼求并，在定位算法運行期間告警矩陣中的各個網(wǎng)絡(luò)設(shè)備（網(wǎng)絡(luò)節(jié)點）根據(jù)條件逐一進(jìn)行定位比較，即滿足

2）有一個誤告警，沒有漏告警的情況

OBS網(wǎng)絡(luò)是通過時域共享、統(tǒng)計復(fù)用光波長信道來有效支持上層協(xié)議或高層用戶產(chǎn)生的突發(fā)業(yè)務(wù)，所以信道中光信號的有無是隨機的，無光（Loss-of-light）并不意味著一定有故障事件發(fā)生。這使得通過監(jiān)測光信號的有無來確定是否產(chǎn)生告警的故障監(jiān)測點會產(chǎn)生過多的誤告警，以至于故障定位算法無法定位故障，或者由于監(jiān)視設(shè)備中的告警門限值設(shè)置較低時，也可能產(chǎn)生此情況[5]。所以當(dāng)收到響鈴的告警集MR時，其中可能存在一些誤告警，需要確定一個網(wǎng)絡(luò)設(shè)備集FD?C，它有最少的誤告警數(shù)目（即| MF(FD)|最?。┎⑶覞M足MM(C′)=φ。具體算法為：

3）有一個漏告警，沒有誤告警的情況

這是在監(jiān)視設(shè)備中的告警門限值設(shè)置較高時可能產(chǎn)生的情況。需要確定一個網(wǎng)絡(luò)設(shè)備集FD?C，它有最少的漏告警數(shù)目（即| MM(FD)|最?。┎⑶覞M足MF(C ′)=φ。由于漏告警的問題是一個完全NP問題，所以其相對于誤告警的糾正要困難得多[6]，所以應(yīng)該設(shè)置監(jiān)視器的告警門限，使得漏告警的數(shù)目達(dá)到最少，以減少故障定位過程中帶來的干擾。具體算法為：

4）有一個誤告警和一個漏告警的情況

在真實OBS網(wǎng)絡(luò)中，網(wǎng)絡(luò)的運行狀況是很復(fù)雜的，很難確定只有一個漏告警或者只有一個誤告警的發(fā)生，因此本文提出這樣一個算法盡量對兩者同時發(fā)生時共同進(jìn)行考慮。具體算法為：

基于探測圈的故障定位算法考慮了4種情況：1）沒有誤告警和漏告警；2）一個誤告警，沒有漏告警；3）一個漏告警，沒有誤告警；4）一個誤告警和一個漏告警。本算法舉例見表2。

表2 告警相關(guān)矩陣

對于任意一個OBS網(wǎng)絡(luò)拓?fù)?，先確定找到所有的最短長度m圈，然后產(chǎn)生如表2所示的告警矩陣，假如接收到一個告警集合為{1，1，1，0，0}，那么說明M3，M6，M7觸發(fā)了告警，而M1，M13處于未觸發(fā)狀態(tài)。對于情況1）來說，都是正常告警，現(xiàn)在網(wǎng)絡(luò)節(jié)點4的告警域可以表示為Domain(ND4)?MR，同理可以得出Domain(ND6)?MR，Domain(ND10)? MR，Domain(ND12)?MR。根據(jù)多故障定位算法可以得到｛ND4，ND6，ND10，ND12｝屬于故障設(shè)備FC（Faulty Component）；對于情況2），有一個誤告警，那么找到的告警集合就會多出｛（1，1，0，0，0），（1，0，1，0，0），（0，1，1，0，0）｝；對于情況3），告警集合就會多出｛（1，1，1，1，0），（1，1，1，0，1）｝；對于情況4），就會多出｛（0，1，1，1，0），（0，1，1，0，1），（1，0，1，1，0），（1，0，1，0，1），（1，1，0，1，0），（1，1，0，0，1）｝幾個告警集合，然后分別運行多故障定位算法來進(jìn)行定位。

3 仿真性能比較

C.Mas對于WDM光網(wǎng)絡(luò)的故障探測和定位研究做了探討，并且仿真性能證明了二叉樹模型是一種快速有效的故障定位算法[1]。但是隨著網(wǎng)絡(luò)節(jié)點和故障數(shù)目的增加，二叉樹的枝葉數(shù)和各個根節(jié)點的數(shù)目會迅速增長，所以需要超大的存儲空間，并且在最終故障定位的準(zhǔn)確度方面有待提高。本文提出的算法主要是針對以上特點進(jìn)行全面的考慮，在接收到一個告警編碼時，考慮了所有漏告警和誤告警的情況，找到每種情況下可能出現(xiàn)的OBS網(wǎng)絡(luò)故障設(shè)備數(shù)目，然后對其求均值；同理找到傳統(tǒng)二叉樹定位算法的故障設(shè)備數(shù)目的均值，對兩個定位算法進(jìn)行比較，性能比較如圖2和圖3所示。

通過分析C.Mas二叉樹故障定位算法的運行過程，得出如下結(jié)論：

1）網(wǎng)絡(luò)依賴模型二叉樹的建立過程（即預(yù)計算過程）復(fù)雜，網(wǎng)絡(luò)中告警設(shè)備的種類和數(shù)量不能太少，否則就沒有足夠的告警信息進(jìn)行關(guān)聯(lián)，無法準(zhǔn)確地進(jìn)行故障定位。如果輸入的告警信息為0001010000000時，這種算法獲取單個故障定位的結(jié)果不是唯一的，導(dǎo)致了多個故障和漏（誤）告警情況下故障定位的準(zhǔn)確率降低。

2）如果告警設(shè)備集中只有一個告警設(shè)備告警，當(dāng)發(fā)生漏告警時，將無法定位網(wǎng)絡(luò)中發(fā)生故障的設(shè)備。

3）這種基于信道編碼的方法中，每個信道的最后一個設(shè)備的告警設(shè)備集總是為空，如果這些設(shè)備發(fā)生故障，就無法對其進(jìn)行定位。而基于探測圈的故障定位算法在考慮漏（誤）告警的同時，因為借鑒了集覆蓋中的自適應(yīng)貪婪優(yōu)化算法，所以在以上幾方面都有很大的改善，只需要找到告警域中包含最多響鈴告警的故障設(shè)備即可。

由圖2和圖3比較可以看出兩種算法在同樣考慮漏告警和誤告警的情況下，基于探測圈的故障定位算法無論在單一故障還是多故障時，其最終找到的故障設(shè)備數(shù)目要小，使得故障管理人員縮小故障搜索范圍，達(dá)到準(zhǔn)確定位。

4 小結(jié)

本文根據(jù)OBS網(wǎng)絡(luò)拓?fù)涞忍攸c，提出一種基于探測圈覆蓋的故障定位方案。此方案主要針對OBS網(wǎng)絡(luò)鏈路和節(jié)點進(jìn)行雙重定位，使得故障定位更加準(zhǔn)確。對于一個網(wǎng)絡(luò)拓?fù)涫紫壤米疃涕L度m圈算法建立故障監(jiān)視器與網(wǎng)絡(luò)拓?fù)渲械墓?jié)點、鏈路建立相關(guān)性模型，然后分別對其進(jìn)行多故障定位，并且考慮了漏告警與誤告警等常見干擾的情況。由仿真結(jié)果可以看出，在同樣考慮干擾告警的情況下，本文提出的基于探測圈的故障定位算法相對與傳統(tǒng)的二叉樹故障定位算法擁有較精確的定位范圍，能夠最終實現(xiàn)OBS網(wǎng)絡(luò)的快速有效的故障定位。

[1]MAS C，THIRAN P.An efficient algorithm for locating soft and hard failures in WDM networks[J].IEEE Journal on Selected Areas in Communications，2000，18（10）：1900-1911.

[2]NAYEK P，PAL S，CHOUDHURY B，et al.Optimal monitor placement scheme for single fault detection in optical network[C]//Proc.IEEE 2005 7th International Conference on Transparent Optical Networks.Barcelona，Spain：IEEE Press，2005，1：433-436.

[3]WANG Ruyan，CHANG Jiaofa，LONG Keping.A fault detection and location mechanism for optical burst switching networks[J].Journal of Optoelectronics Laser，2006，17（12）：1477-1481.

[4]HOCHBAUM D S.Approximation algorithms for NP-hard problems[M].[S.l.]：Course Technology，1996.

[5]江城，張重陽，余松煜.基于異常檢測與雙流編碼的視頻監(jiān)控系統(tǒng)設(shè)計[J].電視技術(shù)，2011，35（1）：111-114.

[6]CARR R D，DODDI S，KONJEVOD G，et al.On the red-blue set cover problem[EB/OL].[2010-10-09].http：//portal.acm.org/citation.cfm?id=338219.338271.