朱國暉， 張 煜

(1.西安郵電學(xué)院通信工程系， 陜西 西安 710061； 2.陜西省電信公司鐘樓分局， 陜西 西安 710001)

0 引 言

從光纖通信技術(shù)來看，光網(wǎng)絡(luò)是一個(gè)非?；钴S的領(lǐng)域.光網(wǎng)絡(luò)技術(shù)的進(jìn)一步發(fā)展，給我們帶來了更高的帶寬和更多的業(yè)務(wù)量，但同時(shí)在故障監(jiān)控管理上也給網(wǎng)絡(luò)運(yùn)營商帶來了新的挑戰(zhàn)[1-3].由于OTN中一旦有一個(gè)故障產(chǎn)生就會(huì)觸發(fā)多個(gè)報(bào)警，因此必須找到有效的方法來定位故障，提高網(wǎng)絡(luò)整體的使用效率.

1 OTN故障定位概述

網(wǎng)絡(luò)的保護(hù)恢復(fù)對時(shí)間有嚴(yán)格的要求，保護(hù)一般在50 ms內(nèi)完成，恢復(fù)要求在200 ms內(nèi)完成[1].對于全光網(wǎng)而言，如果網(wǎng)絡(luò)得不到及時(shí)的保護(hù)和恢復(fù)，將造成業(yè)務(wù)的大量損失；而保護(hù)和恢復(fù)都依賴于故障準(zhǔn)確定位，所以故障定位必須要在最短時(shí)間內(nèi)準(zhǔn)確完成.

在OTN中，生存性的重要性日益突出.對故障定位提出了新的要求，即要將故障定位分為實(shí)時(shí)和非實(shí)時(shí)兩個(gè)部分，實(shí)時(shí)的部分主要解決生存性，而非實(shí)時(shí)的部分主要解決故障的維護(hù)和管理.因?yàn)樯嫘允强烤W(wǎng)絡(luò)的保護(hù)和恢復(fù)機(jī)制來保證的，而保護(hù)和恢復(fù)都是靠資源的重新選擇和分配來完成的，所以為生存性故障定位僅僅需要定位到具體的鏈路、光纖、波長和節(jié)點(diǎn)這些具體的資源即可.在OTN中，實(shí)時(shí)的故障定位可以通過控制信息來完成，非實(shí)時(shí)的部分主要由網(wǎng)管和網(wǎng)絡(luò)操作者來解決.

2 基于二進(jìn)制樹故障定位算法的參數(shù)的定義與假設(shè)

算法中的元件包括以下3種[4]：

(1)設(shè)備 CP：定義包括：①它屬于某個(gè)分類，②是某分類中的某個(gè)設(shè)備.定義這樣的一系列網(wǎng)絡(luò)設(shè)備為N.

(2)告警 A：定義包括：①告警的發(fā)出設(shè)備，②告警的內(nèi)容.

(3)信道 CHi = {CPj}：可以看出是許多設(shè)備的一個(gè)集合.這里規(guī)定信道都是單向的，雙向的視為一對單向信道.同時(shí)，定義一個(gè)位置函數(shù)Pos(CP, CHi)，表示在信道CHi上的CP的位置.若CP不在CHi上，則Pos(CP, CHi) = 0.

算法的輸入有5種：

(1)設(shè)備序列：當(dāng)網(wǎng)絡(luò)建立或更改時(shí)，它的值會(huì)有添加、修改或者刪除.

(2)信道序列：當(dāng)信道建立或更改時(shí)，它的值會(huì)有添加、修改或者刪除.

(3)告警序列：管理器接收到新告警信息，則算法會(huì)給出可能故障的設(shè)備.

(4)漏報(bào)警門限：定義為m1，根據(jù)具體情況設(shè)定.

(5)誤報(bào)警門限：定義為m2，根據(jù)具體情況設(shè)定.

m1和m2被統(tǒng)稱為不匹配門限，它們的存在使二進(jìn)制故障定位算法的實(shí)用性得到加強(qiáng).

3 基于二進(jìn)制樹的故障定位算法

3.1 單故障的定位

整個(gè)算法的實(shí)施可以分為兩步.第一步是預(yù)運(yùn)算(PCP)[4]，也是整個(gè)算法的核心步驟.在預(yù)運(yùn)算過程中，要完成對各個(gè)元件軟硬件故障告警設(shè)備集的計(jì)算，并建立起二進(jìn)制樹；第二步是故障定位，即在遍歷二進(jìn)制樹后，通過對葉子節(jié)點(diǎn)的查詢，確定故障發(fā)生的位置.

在預(yù)運(yùn)算過程中，會(huì)用到4個(gè)參數(shù)，分別是硬故障告警設(shè)備集HD(CP)、合并告警設(shè)備集Ct、二進(jìn)制轉(zhuǎn)換向量集合Bin(Ct)、可能故障設(shè)備集U(Ct).

圖1 單故障定位的網(wǎng)絡(luò)模型

(1)計(jì)算告警設(shè)備集.由圖1及上一節(jié)中的運(yùn)算函數(shù)可以計(jì)算出每個(gè)元件發(fā)生故障時(shí)的告警設(shè)備集：

HD(P1)={E3,E4}，HD(P2)={E3,E4}，HD(P3)={E1,E3,E4}，HD(P4)={E1}，HD(P5)={E1}，HD(P6)={ E4}，HD(P7)={E2,E4}，HD(P8)={E2}，HD(P9)={E2}，HD(E1)=NULL，HD(E2)=NULL，HD(E3)={E4}，HD(E4)=NULL.

(2)合并告警設(shè)備集.將告警設(shè)備集相同的情況進(jìn)行合并，以盡可能地減少儲存空間.合并后如下：

C1=HD{P1}=HD{P2}=HD{E3,E4}，C2=HD{P3}={E1,E3,E4}，C3=HD{P4}=HD{P5}={E1}，C4=HD{P6}=HD{E3}={E4}，C5=HD{P7}={E2,E4}，C6=HD{P8}=HD{P9}={E2}.

圖2 理想狀況下單故障的二進(jìn)制故障樹

(3)構(gòu)建二進(jìn)制轉(zhuǎn)換向量.將上一步所得到的集合進(jìn)行二進(jìn)制化，即變?yōu)橐粋€(gè)二進(jìn)制向量.向量中的1是上一步集合中的Ei.若集合中存在Ei，則向量第i位為1，否則為0.因此也可以知道，向量的長短即取決于告警設(shè)備的個(gè)數(shù)：Bin(C1)=(0011)，Bin(C2)=(1011)，Bin(C3)=(1000)，Bin(C4)=(0001)，Bin(C5)=(0101)，Bin(C6)=(0100).

(4)由(3)中的Bin(Ct)，再根據(jù)(2)中的等式，可以得到可能故障的設(shè)備集： U(C1)={P1,P2}，U(C2)={P3}，U(C3)={P4,P5}， U(C4)={P6,E3}，U(C5)={P7}，U(C6)={P8,P9}.

(5)通過(3)、(4)構(gòu)建二進(jìn)制故障樹，如圖2所示.二進(jìn)制樹的深度就是二進(jìn)制向量的長，也就是告警設(shè)備個(gè)數(shù).在網(wǎng)絡(luò)內(nèi)發(fā)生故障時(shí)，通過查詢二進(jìn)制樹的路徑，到達(dá)某一節(jié)點(diǎn)，便可找到對應(yīng)的可能發(fā)生故障的設(shè)備集，從而定位故障.

舉例來說，假設(shè)管理器接收到了E1、E3和E4的報(bào)警，那么可得二進(jìn)制向量為Bin(Ct)=(1011)，對應(yīng)的葉節(jié)點(diǎn)為U(C2)={P3}，則可知故障元件為P7.

在非理想狀況下，如圖2中的情況，有些向量所對應(yīng)的節(jié)點(diǎn)是空的.如果最終定位在這些空節(jié)點(diǎn)，則說明在定位過程中發(fā)生了錯(cuò)誤.這樣的錯(cuò)誤可能是誤報(bào)警或者漏報(bào)警，那么這時(shí)便要引入不匹配門限m1和m2了.

①當(dāng)m1=1，m2=0時(shí).這種狀況表示有漏報(bào)警情況，將這種狀況下轉(zhuǎn)換來的二進(jìn)制向量記作Bin1(Ct)，此時(shí)可根據(jù)以下公式得到Bin(Ct)對應(yīng)的Bin1(Ct)：

Bin1(Ct) OR Bin(Ct) = Bin(Ct)，W[Bin1(Ct)] = W [Bin(Ct)]-m1

其中W[Bin(Ct)]表示碼字的重量.

②當(dāng)m1=0，m2=1時(shí).這種狀況表示有誤報(bào)警情況，轉(zhuǎn)換來的二進(jìn)制向量記作Bin2(Ct)，此時(shí)：

Bin2(Ct) OR Bin(Ct) = Bin2(Ct)， W[Bin2(Ct)] = W [Bin(Ct)]+m2

③當(dāng)m1=1，m2=1時(shí).這種狀況表示既有漏報(bào)警也有誤報(bào)警的情況，轉(zhuǎn)換的二進(jìn)制向量記作Bin3(Ct)，此時(shí)：

W[Bin(Ct)⊕Bin3(Ct)] = m1+m2， W[Bin(Ct)] = W[Bin3(Ct)]+m1-m2

4 多故障的定位算法

一般來說，同時(shí)發(fā)生3個(gè)及以上故障的可能性較低[5]，這里將以發(fā)生2個(gè)故障的例子來說明多故障的情況.

4.1 多重故障時(shí)的告警設(shè)備集

假設(shè)兩個(gè)元件CPi和CPj，其告警設(shè)備集為Ci、Cj，當(dāng)它們同時(shí)故障時(shí)，其告警設(shè)備集為Ck，則可以發(fā)現(xiàn)Ck = Ci ∪ Cj.進(jìn)一步可知轉(zhuǎn)化的二進(jìn)制向量：Bin(Ck) = Bin(Ci ∪ Cj) = Bin(Ci) ∪ Bin(Cj)，由此不難得到合并后的可能故障設(shè)備集：U(Ck) = U(Ci ∪ Cj) = {CPi, CPj}，此時(shí)U(Ck)對應(yīng)的Bin(Ck)有兩種可能：第一種是Bin(Ck)和已存在的某個(gè)故障的Bin(Ci)一樣：Bin(Ci) ∪ Bin(Cj) = Bin(Ci) 或 Bin(Ci) ∪ Bin(Cj) = Bin(Cj)； 第二種是Bin(Ck)完全不同于之前的向量，此時(shí)就是一個(gè)新的葉子節(jié)點(diǎn)：Bin(Ci) ∪ Bin(Cj) = Bin(Ck).

將其加入二進(jìn)制樹的空節(jié)點(diǎn)，之后繼續(xù)填充，若2個(gè)故障的情況討論完后仍有空著的葉子節(jié)點(diǎn)，則可以考慮發(fā)生了更多故障的情況[6].

下面給出發(fā)生2個(gè)故障時(shí)的具體的建樹過程(參考圖1).

(1)計(jì)算告警設(shè)備集：

HD(P1)={E3,E4}，HD(P2)={E3,E4}，HD(P3)={E1,E3,E4}，HD(P4)={E1}，HD(P5={E1}，HD(P6)={ E4}，HD(P7)={E2,E4}，HD(P8)={E2}，HD(P9)={E2}， HD(E1)=NULL，HD(E2)=NULL，HD(E3)={E4}， HD(E4)=NULL.

(2)合并告警設(shè)備集：

C1=HD{P1}=HD{P2}=HD{E3,E4}，C2=HD{P3}={E1,E3,E4}，C3=HD{P4}=HD{P5}={E1}，C4=HD{P6}=HD{E3}={E4}，C5=HD{P7}={E2,E4}，C6=HD{P8}=HD{P9}={E2}.

(3)計(jì)算發(fā)生2個(gè)故障的告警設(shè)備集：

C1∪C2={E1,E3,E4}，C1∪C3={E1,E3,E4}， C1∪C4={E3,E4}， C1∪C5={E2,E3,E4}，C1∪C6={E2,E3,E4}，C2∪C3={E1,E3,E4}，C2∪C4={E1,E3,E4}，C2∪C5={E1,E2,E3,E4}，C2∪C6={E1,E2,E3,E4}，C3∪C4={E1, E4}，C3∪C5={E1,E2,E4}，C3∪C6={E1,E2}， C4∪C5={E2,E4}，C4∪C6={E2,E4}，C5∪C6={E2,E4}.

(4)合并相同的告警設(shè)備集：

C3={E1}，C4={E4}，C6={E2}，C7=C3∪C6={E1，E2}，C8=C5=C4∪C5=C4∪C6=C5∪C6={E2,E4}，C9=C1=C1∪C4={ E3,E4}，C10=C3∪C4={E1, E4}， C11= C3∪C5={E1,E2,E4}， C12=C2=C1∪C2=C1∪C3=C2∪C3=C2∪C4={E1,E3,E4}，C13=C1∪C5=C1∪C6={E2,E3,E4}，C14=C2∪C5=C2∪C6={E1,E2,E3,E4}.

(5)二進(jìn)制轉(zhuǎn)換：

Bin(C3)=(1000)，Bin(C4)=(0001)， Bin(C6)=(0100)，Bin(C7)=(1100)，Bin(C8)=(0101)，Bin(C9)=(0011)，Bin(C10)=(1001)， Bin(C11)=(1101)，Bin(C12)=(1011)，Bin(C13)=(0111)，Bin(C14)=(1111).

4．2 多種設(shè)備的故障定位

這里所說的多種設(shè)備包括P，A1，A2，A3，M，其故障定位的思路與兩種設(shè)備時(shí)基本相同.下面，按照給出的圖3為例來說明多設(shè)備時(shí)基于二進(jìn)制樹的故障定位算法[7，8].

圖3 多故障定位的網(wǎng)絡(luò)模型

這里對圖3的幾個(gè)元件進(jìn)行分析.首先寫出告警設(shè)備集并進(jìn)行合并：

C1=HD{E1}={E1,E3,E8,E9}，C2=SD{E1}={E3,E8}，C3=HD{E2}={E2,E3,E5,E6}，C4=SD{E2}={E3,E5}，C5=HD{E3}=HD{P1}={E3,E5,E6,E8,E9}，C6=SD{E3}=SD{P1}={E3,E5,E8}，C7=HD{E4}={E4,E5,E6,E8,E9}，C8=SD{E4}=SD{P2}={E5,E8}，C9=HD{E5}={E5,E6}，C10=SD{E5}={E5}，C11=HD{P2}={C5,C6,C8,C9}，C12=HD{E7}={E7,E8,E9}，C13=SD{E7}=SD{P4}={E8}，C14=HD{E8}=HD{P4}={E8,E9}.

相應(yīng)二進(jìn)制轉(zhuǎn)換：Bin(C1)=(101000011)，Bin(C2)=(001000010)，Bin(C3)=(011011000)，Bin(C4)=(001010000)，Bin(C5)=(001011011)，Bin(C6)=(001010010)，Bin(C7)=(000111011)，Bin(C8)=(000010010)，Bin(C9)=(000011000)，Bin(C10)=(000010000)，Bin(C11)=(000011011)，Bin(C12)=(000000111)，Bin(C13)=(000000010)， Bin(C14)=(000000011).

據(jù)此便可構(gòu)建出深度為9的二進(jìn)制故障樹，再通過遍歷此樹來確定故障元件以實(shí)現(xiàn)定位.例如，經(jīng)遍歷后路徑為011011000，那么可以斷定故障的設(shè)備可能是E2，E3，E5，E6.

圖4 二進(jìn)制四叉故障 樹示意圖

4.3 關(guān)于二進(jìn)制樹故障定位算法的改進(jìn)思路

在多設(shè)備故障定位中，如果P4同時(shí)發(fā)生硬故障和軟故障，那么在定位時(shí)就可能要去排查E7和E8兩個(gè)可能故障的元件，雖然這樣做在理論上來講是可以的，但如果假設(shè)實(shí)際的網(wǎng)絡(luò)情況更加復(fù)雜的話，那么可能涉及到的需要排查的元件會(huì)更多，這就大大增加了維護(hù)人員的工作量[9].針對這種情況，將每個(gè)報(bào)警設(shè)備的狀態(tài)改為兩位二進(jìn)制數(shù)字，這兩位分別代表硬故障和軟故障，這樣便可以使工作量在一定程度上有所減少.用00表示無故障，10表示有硬故障，01表示有軟故障，11表示同時(shí)有硬故障和軟故障. 對于圖3，通過上述方法重新定義的告警設(shè)備集用XD(CP)表示，經(jīng)合并后最終有：

Bin (C1)=Bin(XD{E1})=(10 00 11 00 00 00 00 11 10)，Bin (C2)=Bin(XD{E2})=(00 10 11 00 11 10 00 00 00)，Bin (C3)=Bin(XD{E3})=Bin(XD{P1})=(00 00 11 00 11 10 00 11 10)，Bin (C4)=Bin(XD{E4})=(00 00 00 10 11 10 00 11 10)，Bin (C5)=Bin(XD{E5})=(00 00 00 00 11 10 00 00 00)，Bin (C6)=Bin(XD{P2})=(00 00 00 00 11 10 00 11 10)，Bin (C7)=Bin(XD{E7})=(00 00 00 00 00 00 10 11 10)，Bin (C8)=Bin(XD{P4})=(00 00 00 00 00 00 00 11 10).

如果按照這樣的話，那么建樹的時(shí)候其實(shí)也就變成了四叉樹，如圖4所示(未給出完全樹圖).每個(gè)節(jié)點(diǎn)會(huì)分出4個(gè)新的節(jié)點(diǎn)，雖然圖會(huì)稍顯復(fù)雜，但在定位故障時(shí)卻更高效了，更容易直接確定到元件的故障[10].

需要說明的是，在上面的敘述中，其實(shí)考慮的情況只是某元件同時(shí)發(fā)生軟故障和硬故障，因此上面給出的告警設(shè)備集也不是完全的情況，甚至只是一少部分葉子節(jié)點(diǎn).在很多情況下，某元件只有硬故障告警設(shè)備集或軟故障告警設(shè)備集，例如E8只有硬故障告警集，則第二位均為0：Bin (C9)=Bin(HD{E8})=(00 00 00 00 00 00 00 10 10).

即我們同時(shí)還要定義4.2中的那些告警設(shè)備集，只是第一位或第二位要定義全0，以E1為例，除了本節(jié)中定義的設(shè)備及外，還要有：Bin (C10)=Bin(HD{E1})=(10 00 10 00 00 00 00 10 10)，Bin (C11)=Bin(SD{E1})=(00 00 01 00 00 00 00 01 10).其它元件也是如此，這里不再詳細(xì)給出.

5 結(jié)束語

本文研究了基于二進(jìn)制樹的故障定位算法，實(shí)現(xiàn)了理想狀況下和非理想狀況下兩種簡單設(shè)備的單故障定位、多故障定位，并進(jìn)一步擴(kuò)展到了對多設(shè)備網(wǎng)絡(luò)信道模型的故障定位，同時(shí)提出了利用兩位二進(jìn)制構(gòu)建四叉故障樹的改良思路.

實(shí)際網(wǎng)絡(luò)中，一旦組網(wǎng)情況復(fù)雜起來，該算法要求的存儲量還是比較大的，尤其是在改進(jìn)的思路中，雖然提高了定位的準(zhǔn)確性，但是也相應(yīng)地提高了存儲量的要求，這是需要進(jìn)一步改進(jìn)的.

參考文獻(xiàn)

[1] 張 杰，宋鴻升.自動(dòng)交換光網(wǎng)絡(luò)(ASON)[R].北京郵電大學(xué)，2002.

[2] 趙季紅，曲 樺.多層傳送網(wǎng)的故障定位算法[J].南京郵電學(xué)院學(xué)報(bào)，2003，(23)(3)：20-24.

[3] Carmen Mas，Patricr Thiran.An efficient algorithm for soft and hard failures in WDM networks[R].IEEE,2000.

[4] Carmen Mas，Patrick Thiran.An efficient fault localization algorithm for IP/WDM networks[Z].ICA EPFL,2010.

[5] 張曉艷.下一代智能光網(wǎng)絡(luò)故障定位算法的研究[R].國防科學(xué)技術(shù)大學(xué)研究生院，2005.

[6] Hongqing Zeng，Alex Vukovic，Changcheng Huang.Fast fault detection and localization in WDM networks[R].SPIE Newsroom，2006.

[7] 李明芳.WDM網(wǎng)絡(luò)的故障定位[J].光通信研究，2005，(37):52-55.

[8] CAO Xiao-jun，ANAND Vishal，QIAO Chunming.A waveband switching architecture and algorithm[J].IEEE Communications Letters，2003,(4):61-65.

[9] Haradak，Shimizu，Kudout，etal.Hierarchical optical path cross-connect systems for large scale WDM network[C].Proc.OFC，1999.

[10] 周厚清，張 杰，桂 烜.多粒度光網(wǎng)絡(luò)故障定位[J].光通信技術(shù)，2006,(1):78-82.