摘要：解決多故障定位的非多項(xiàng)式完全問題(NP－complete)在P比特級光網(wǎng)絡(luò)中變的更加困難。計(jì)算復(fù)雜度、計(jì)算時(shí)間與網(wǎng)絡(luò)的輸入規(guī)模成指數(shù)增長關(guān)系。文章闡述已有的多故障定位算法以及協(xié)議，包括透明的故障定位算法、推理算法、深度探測算法、啟發(fā)式生成樹算法以及有限區(qū)域向量匹配協(xié)議(LVM)等，深入分析了P比特級光網(wǎng)絡(luò)中多故障定位NP－corrIplete問題的難點(diǎn)所在，同時(shí)提出一種基于蟻群優(yōu)化進(jìn)行告警的遍歷和包含故障元素最少的故障集合的尋找方法。

關(guān)鍵詞：P比特光網(wǎng)絡(luò)；多故障定位；蟻群優(yōu)化

隨著超大容量(P比特級)光網(wǎng)絡(luò)規(guī)模的擴(kuò)大和傳輸速率的提高，使得網(wǎng)絡(luò)遭受自然災(zāi)害破壞、人工操作失誤和軟件配置錯(cuò)誤等多重故障的概率增加，將降低光網(wǎng)絡(luò)帶寬提供的可靠性，增加保護(hù)恢復(fù)資源配置冗余和調(diào)度的復(fù)雜性。超大容量(P比特級)光網(wǎng)絡(luò)采用基于時(shí)空標(biāo)記的分類服務(wù)方法，從時(shí)空角度對網(wǎng)絡(luò)資源(包括路由、波長、鏈路、節(jié)點(diǎn)等)進(jìn)行整合與優(yōu)化。多業(yè)務(wù)端到端服務(wù)質(zhì)量(Qos)需求與光網(wǎng)絡(luò)時(shí)空多重故障生存性之間存在復(fù)雜的關(guān)系。由于光網(wǎng)絡(luò)元素(節(jié)點(diǎn)、鏈路)的故障能夠向業(yè)務(wù)流的下游節(jié)點(diǎn)進(jìn)行傳播，而使時(shí)空多重故障情況下故障管理中心收到大量的告警包。其中包含大量的冗余告警包，造成故障管理中心告警包數(shù)目急劇增多。理論已經(jīng)證明，依據(jù)收到的告警包進(jìn)行多故障的甄別屬于非多項(xiàng)式完全問題(NP－compJete)問題：通常情況下得不出準(zhǔn)確的故障發(fā)生的數(shù)目和故障發(fā)生的位置。光網(wǎng)絡(luò)多故障定位困難可以描述為：可以在多項(xiàng)式時(shí)間內(nèi)判定一個(gè)故障的集合是不是觀測到的檢測設(shè)備發(fā)出告警的原因，但是無法在多項(xiàng)式時(shí)間內(nèi)根據(jù)觀測到的告警集合推斷出故障的集合。

網(wǎng)絡(luò)拓?fù)鋸?fù)雜化和承載業(yè)務(wù)的多樣性是P比特級光網(wǎng)絡(luò)兩個(gè)基本的特點(diǎn)，而多故障定位NP－complete問題的困難與網(wǎng)絡(luò)拓?fù)浜途W(wǎng)絡(luò)承載的業(yè)務(wù)相關(guān)。在P比特級光網(wǎng)絡(luò)里多故障定位的NP－complete屬性：更難尋找包含故障元素最少的故障集合和尋找包含故障元素最少的故障集合的時(shí)間與網(wǎng)絡(luò)拓?fù)涞妮斎胍?guī)模成指數(shù)增長關(guān)系。由于多故障定位屬于NP－compJere問題，很難得到故障的準(zhǔn)確的數(shù)目和位置。默認(rèn)的約定是：在保證推斷出的故障集合一定能產(chǎn)生故障管理中心收到的告警情況下認(rèn)為故障集合中的元素越少越是最有可能發(fā)生。已有的故障定位機(jī)制最后給出的故障集合都是在這種約束下給出的，但在這種約束條件下得到的故障集合并不一定是網(wǎng)絡(luò)真實(shí)發(fā)生的故障，而且在這種約束下網(wǎng)絡(luò)存在一些故障情況使得任何故障定位算法都無法處理。

1、多故障定位算法

多故障定位機(jī)制主要分為集中式和分布式，應(yīng)用的光網(wǎng)絡(luò)類型為非全光網(wǎng)和全光網(wǎng)。在非全光網(wǎng)中光路的中間節(jié)點(diǎn)對光信號進(jìn)行光電轉(zhuǎn)化，能夠檢測到故障并且可以屏蔽某些類型的故障向下游的傳播。全光網(wǎng)中只有光路的宿節(jié)點(diǎn)或者所經(jīng)過域的邊界節(jié)點(diǎn)才對信號進(jìn)行光電轉(zhuǎn)換，才能檢測到故障。一般情況下，集中式方法需要詳細(xì)的網(wǎng)絡(luò)元素模型用于故障定位，分布式機(jī)制依靠持久連接(Keep－alive)或通知消息甄別出故障的根源。

表1列出了已有的故障定位機(jī)制，透明的故障定位算法(層1)、推理算法(層1)、運(yùn)行長度探測算法(層1)、啟發(fā)式生成樹M－cycle算法(層1、2、31屬于集中式的故障定位算法，鏈路管理協(xié)議(層3)、端到端故障檢測和定位協(xié)議(層3)、有限區(qū)域向量匹配協(xié)議(LVM)協(xié)議屬于分布式故障定位協(xié)議。

研究透明光網(wǎng)絡(luò)中故障管理的常規(guī)問題，對網(wǎng)絡(luò)中的設(shè)備進(jìn)行建模，得到每個(gè)設(shè)備可能檢測到的故障和可能屏蔽的故障，然后根據(jù)得到的告警包去遍歷一個(gè)告警的二叉樹，最后得到可能的故障元素。該算法可應(yīng)付4種故障：功率下降、波長錯(cuò)誤部署、帶內(nèi)干擾、帶外干擾。

研究真實(shí)環(huán)境中的多故障定位(觀察到的告警可以是不可靠的)。核心問題為離散優(yōu)化問題。目標(biāo)是要找到故障集合和告警集合，最小化成本函數(shù)。提出了啟發(fā)式算法的解決方案。該算法的復(fù)雜度集中在一個(gè)預(yù)先計(jì)算階段，需要遍歷一個(gè)二叉樹。

鏈路管理協(xié)議(LMP)是通用多協(xié)議標(biāo)記交換(GMPLS)協(xié)議棧的重要組成部分，通過在一對節(jié)點(diǎn)之間交換活動狀態(tài)通道(Channel Active)和失效狀態(tài)通道(channel FatD消息來實(shí)現(xiàn)不透明或透明網(wǎng)絡(luò)中的故障定位，而不必關(guān)心編碼格式。LMP協(xié)議并不單一運(yùn)行在一個(gè)平面，涉及到控制平面和數(shù)據(jù)平面的協(xié)同工作。

LVM協(xié)議的核心是如果兩條光路同時(shí)經(jīng)過一段鏈路，若這兩個(gè)業(yè)務(wù)的目的節(jié)點(diǎn)都檢測到故障，就認(rèn)為這個(gè)故障的鏈路就是這個(gè)共享風(fēng)險(xiǎn)的鏈路。這個(gè)協(xié)議為單故障定位設(shè)計(jì)。擴(kuò)展的LVM協(xié)議支持多故障定位。

2、多故障定位問題描述

對于超大容量(P比特級)光網(wǎng)絡(luò)，影響到故障定位復(fù)雜度的因素主要包括：多故障時(shí)空隨機(jī)出現(xiàn)、網(wǎng)絡(luò)復(fù)雜度(無標(biāo)度網(wǎng)絡(luò)、隨機(jī)網(wǎng)絡(luò))、承載業(yè)務(wù)的多樣性(業(yè)務(wù)種類、業(yè)務(wù)級別、QOS)。通常情況下多故障定位的目標(biāo)是根據(jù)得到的告警指示，找出可能的故障集合，并且認(rèn)為得到的集合(f)的故障數(shù)目越少越好。下面描述一般意義下故障定位的困難，然后闡述解決NP－complete在P比特級光網(wǎng)絡(luò)中變得更加困難，且隨著網(wǎng)絡(luò)規(guī)模的增大定位的計(jì)算復(fù)雜度和計(jì)算時(shí)間與網(wǎng)絡(luò)的輸入規(guī)模成指數(shù)增長關(guān)系。

多故障定位的線性規(guī)劃形式：

f時(shí)刻可能出現(xiàn)的故障集合F_(t)F₁，F(xiàn)₂，F(xiàn)₃，F(xiàn)₄……

t時(shí)刻故障管理中心收到的告警集合A_(t)：a，b，c，d，e，f，g，h……

約束條件：A(F_t)＋A(F₂)+A(F₃)＋A(F₄)+……=A(_t)其中函數(shù)A(F)表示僅僅故障F觸發(fā)的告警的集合。

目標(biāo)函數(shù)：main(C^TF)，C＝(1，O，1……)。C中元素為1或者0的列向量，目的是尋找一個(gè)包含故障數(shù)日最少的集合。

根據(jù)光網(wǎng)絡(luò)拓?fù)浜途W(wǎng)絡(luò)中的業(yè)務(wù)分布，我們得到如圖1所示故障和告警關(guān)系的二部圖。圖的下面是故障管理中心收到的告警的集合，上面是可能的故障元素。故障定位的任務(wù)是根據(jù)關(guān)系圖，找到一個(gè)故障的集合，使得故障集合中的故障數(shù)日最少。多故障定位可分兩階段完成：

(1)獲得故障和告警的關(guān)系圖。這個(gè)關(guān)系圖有兩個(gè)約束：光網(wǎng)絡(luò)拓?fù)涞募s束和承載業(yè)務(wù)的分布約束。

(2)根據(jù)得到的關(guān)系圖，運(yùn)用有效的算法得到包含故障數(shù)最少的故障集合，其中第二階段中尋找最少數(shù)目的故障集合屬于NP－eomplete問題。

多故障定位的目標(biāo)是尋找包含故障數(shù)目最少的故障集合。即使能夠?qū)ふ业接?jì)算性能優(yōu)良的啟發(fā)式算法解決了NP－complete的困難，但是最少數(shù)目的故障集合可能不止一個(gè)，如何選擇和處理這些集合仍困難。況且最少數(shù)目的故障集合并不一定是真實(shí)網(wǎng)絡(luò)中一定發(fā)生的故障，網(wǎng)絡(luò)管理者只是認(rèn)為最少數(shù)目的故障集合更有理由發(fā)生。

多故障時(shí)空隨機(jī)出現(xiàn)、網(wǎng)絡(luò)復(fù)雜化(無標(biāo)度網(wǎng)絡(luò)、隨機(jī)網(wǎng)絡(luò))、承載業(yè)務(wù)的多樣性是P比特級光網(wǎng)絡(luò)的顯著特征。其中網(wǎng)絡(luò)復(fù)雜化(無標(biāo)度網(wǎng)絡(luò)、隨機(jī)網(wǎng)絡(luò))、承載業(yè)務(wù)的多樣性增加了多故障定位第一個(gè)階段的復(fù)雜度，使得獲得的故障和告警的關(guān)系圖更加復(fù)雜、耗時(shí)，而且得到的關(guān)系圖不再是靜態(tài)而是動態(tài)變化的。多故障時(shí)空隨機(jī)出現(xiàn)增加了多故障定位的第二個(gè)階段的復(fù)雜度，因?yàn)槭盏降母婢请S機(jī)達(dá)到故障管理中心的，不同的告警集合及故障集合有著明顯的區(qū)別，如何處理告警包的隨機(jī)性，成為研究的關(guān)鍵。

3、模糊故障定位和蟻群優(yōu)化

為了解決P比特級光網(wǎng)絡(luò)對多故障定位兩階段帶來的影響，本文針對每個(gè)階段提出了各自的優(yōu)化策略：故障和告警關(guān)系的模糊化(第一階段)、蟻群優(yōu)化算法(第二階段)。

由于承載業(yè)務(wù)的多樣性使得獲得的故障和告警的關(guān)系圖更加復(fù)雜并且是動態(tài)變化的，此時(shí)故障和告警的關(guān)系不再是確定性的必然事件。我們用模糊數(shù)學(xué)的隸屬關(guān)系來描述故障和告警，告警是在一定程度上隸屬于觸發(fā)它的故障，得出這樣的結(jié)論的依據(jù)是：

(1)承載業(yè)務(wù)的多樣性、業(yè)務(wù)動態(tài)的拆建使得故障管理中心無法實(shí)時(shí)地得到下游的節(jié)點(diǎn)告警，告警和故障的關(guān)系不再是確定性關(guān)系。而根據(jù)業(yè)務(wù)到達(dá)的分布，可以得到告警和故障的隸屬度。

(2)網(wǎng)絡(luò)復(fù)雜化(無標(biāo)度網(wǎng)絡(luò)、隨機(jī)網(wǎng)絡(luò))使得業(yè)務(wù)的路由多樣化。相同源和宿業(yè)務(wù)的路由在不同時(shí)刻有著不同的路由，使得故障和告警的關(guān)系圖動態(tài)變化?；诼酚傻亩鄻有裕梢缘玫礁婢凸收系碾`屬度。

(3)隨著網(wǎng)絡(luò)的運(yùn)行時(shí)間的增長，伴隨著故障定位問題的成功和失敗，可以根據(jù)以往成功的經(jīng)驗(yàn)建立專家系統(tǒng)。這個(gè)專家系統(tǒng)需要能夠很好地描述網(wǎng)絡(luò)故障和告警的關(guān)系。

隸屬函數(shù)是模糊故障定位的基石，已有隸屬函數(shù)的確定方法：

(1)模糊統(tǒng)計(jì)法

模糊統(tǒng)計(jì)法的基本思想是對論域上的一個(gè)確定元素是否屬于論域上的一個(gè)可變動的清晰集合做出清晰的判斷。

(2)例證法

例證法的主要思想是從已知有限個(gè)μA的值，來估計(jì)論域μ上的模糊子集A的隸屬函數(shù)。

(3)專家經(jīng)驗(yàn)法

專家經(jīng)驗(yàn)法是根據(jù)專家的實(shí)際經(jīng)驗(yàn)給出模糊信息的處理算式或相應(yīng)權(quán)系數(shù)值來確定隸屬函數(shù)的一種方法。在許多情況下，經(jīng)常是初步確定粗略的隸屬函數(shù)，然后再通過學(xué)習(xí)和實(shí)踐檢驗(yàn)逐步修改和完善，而實(shí)際效果正是檢驗(yàn)和調(diào)整隸屬函數(shù)的依據(jù)。

這樣在得到的故障和告警的關(guān)系圖中，故障和告警之間不再是確定的關(guān)系，每條故障和告警之間的連接都將賦予一個(gè)隸屬度(0～1)，這個(gè)隸屬度反映網(wǎng)絡(luò)拓?fù)浜蜆I(yè)務(wù)分布在一段時(shí)間內(nèi)對告警和故障關(guān)系的影響。我們采用例證法來進(jìn)行隸屬度的計(jì)算。蟻群算法(ACO)是一種基于種遍歷所有告警群的啟發(fā)式仿生進(jìn)化算法。ACO已經(jīng)成功用于解決許多組合優(yōu)化問題，最早的應(yīng)用就是解決旅行推銷員、貨郎問題(TSP)問題。蟻群算法是對自然界螞蟻的覓食尋路方式進(jìn)行模擬而得出的一種仿生算法，充分利用了選擇、更新和協(xié)調(diào)的優(yōu)化機(jī)制。即通過個(gè)體之間的信息交流與相互協(xié)作最終找到最優(yōu)解，使它具有很強(qiáng)的發(fā)現(xiàn)較優(yōu)解的能力。假如將告警作為圖的節(jié)點(diǎn)，而故障作為經(jīng)過的鏈路，多故障定位很容易轉(zhuǎn)化為旅行售貨商問題。螞蟻經(jīng)過一個(gè)告警并為這個(gè)告警選擇相應(yīng)的產(chǎn)生此告警的故障。當(dāng)所有螞蟻遍歷所有的告警后，就得到故障的一個(gè)集合。螞蟻釋放的信息素與故障集合的元素的個(gè)數(shù)成反比，故障元素的數(shù)目越少。釋放的信息素越多。啟發(fā)式信息與每個(gè)故障節(jié)點(diǎn)的度成正比。

4、仿真驗(yàn)證

本文在波長交換光網(wǎng)絡(luò)(WSON)仿真平臺上實(shí)現(xiàn)模糊隸屬關(guān)系和蟻群優(yōu)化算法的多故障定位。平臺基本功能采用了IETF的GMPLS協(xié)議。COST239仿真拓?fù)淙鐖D2所示。有11個(gè)物理鏈路節(jié)點(diǎn)和25條物理鏈路。網(wǎng)絡(luò)類型為全光網(wǎng)(只有每條光路的宿節(jié)點(diǎn)或者域的邊界節(jié)點(diǎn)可以檢測到故障)。仿真僅僅考慮鏈路故障。1～25條物理鏈路上隨機(jī)的3條鏈路出現(xiàn)故障。產(chǎn)生故障的光路的宿節(jié)點(diǎn)都能夠檢測到故障。物理拓?fù)渖先我鈨蓚€(gè)節(jié)點(diǎn)承載的業(yè)務(wù)采用泊松分布。業(yè)務(wù)的路由采用D算法實(shí)現(xiàn)，不考慮資源約束。方案旨在驗(yàn)證多故障定位方案。仿真結(jié)果如圖3所示，分別進(jìn)行了蟻群多故障和擴(kuò)展的LvM協(xié)議多故障定位。紅黑曲線計(jì)算多故障定位成功率的方式為故障數(shù)目和定位的故障與預(yù)先設(shè)置的故障數(shù)目和故障完全一致則認(rèn)為多故障定位成功，否則失敗。藍(lán)綠曲線計(jì)算多故障定位成功率的方式為成功的故障數(shù)目除以得到的故障集合的故障數(shù)目。左邊的仿真結(jié)果圖為3故障，右邊的仿真結(jié)果圖為4故障，從成功率對比可以看出，隨著故障數(shù)目的增加，蟻群要逐漸優(yōu)于擴(kuò)展的LVM協(xié)議，在大規(guī)模和多故障情況下，蟻群算法能取得更優(yōu)的性能。

5、結(jié)束語

本文主要研究網(wǎng)絡(luò)出現(xiàn)多重故障下快速的故障定位機(jī)制，為后續(xù)的受損業(yè)務(wù)的恢復(fù)以及故障的維修提供可靠的時(shí)間保證。模糊數(shù)學(xué)以不確定性的事物為其研究對象。模糊集合的出現(xiàn)是適應(yīng)描述復(fù)雜事物的需要。依據(jù)模糊集合的理論找到解決模糊性對象加以確切化，從而使研究確定性對象的數(shù)學(xué)與不確定性對象的數(shù)學(xué)溝通起來。蟻群算法是一種源于自然界中生物的仿生類模擬進(jìn)化算法，對求解復(fù)雜組合優(yōu)化問題有如下的優(yōu)勢：較強(qiáng)的魯棒性、具有并行性。基于P比特級光網(wǎng)絡(luò)的多故障時(shí)空隨機(jī)出現(xiàn)、網(wǎng)絡(luò)復(fù)雜化、承載業(yè)務(wù)多樣性的特點(diǎn)，本文將模糊數(shù)學(xué)和蟻群算法相結(jié)合提出了多故障定位的兩個(gè)階段的優(yōu)化策略，分別為模糊的告警故障隸屬度關(guān)系和蟻群優(yōu)化多故障定位算法。仿真驗(yàn)證給出了在兩種策略下P比特級光網(wǎng)絡(luò)尋找最優(yōu)故障集合解過程的成功率。