P比特光網絡多故障定位的NP-compIete問題研究

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

關鍵詞：P比特光網絡；多故障定位；蟻群優化

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

網絡拓撲復雜化和承載業務的多樣性是P比特級光網絡兩個基本的特點，而多故障定位NP－complete問題的困難與網絡拓撲和網絡承載的業務相關。在P比特級光網絡里多故障定位的NP－complete屬性：更難尋找包含故障元素最少的故障集合和尋找包含故障元素最少的故障集合的時間與網絡拓撲的輸入規模成指數增長關系。由于多故障定位屬于NP－compJere問題，很難得到故障的準確的數目和位置。默認的約定是：在保證推斷出的故障集合一定能產生故障管理中心收到的告警情況下認為故障集合中的元素越少越是最有可能發生。已有的故障定位機制最后給出的故障集合都是在這種約束下給出的，但在這種約束條件下得到的故障集合并不一定是網絡真實發生的故障，而且在這種約束下網絡存在一些故障情況使得任何故障定位算法都無法處理。

1、多故障定位算法

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

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

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

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

鏈路管理協議(LMP)是通用多協議標記交換(GMPLS)協議棧的重要組成部分，通過在一對節點之間交換活動狀態通道(Channel Active)和失效狀態通道(channel FatD消息來實現不透明或透明網絡中的故障定位，而不必關心編碼格式。LMP協議并不單一運行在一個平面，涉及到控制平面和數據平面的協同工作。

LVM協議的核心是如果兩條光路同時經過一段鏈路，若這兩個業務的目的節點都檢測到故障，就認為這個故障的鏈路就是這個共享風險的鏈路。這個協議為單故障定位設計。擴展的LVM協議支持多故障定位。

2、多故障定位問題描述

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

多故障定位的線性規劃形式：

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

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

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

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

根據光網絡拓撲和網絡中的業務分布，我們得到如圖1所示故障和告警關系的二部圖。圖的下面是故障管理中心收到的告警的集合，上面是可能的故障元素。故障定位的任務是根據關系圖，找到一個故障的集合，使得故障集合中的故障數日最少。多故障定位可分兩階段完成：

(1)獲得故障和告警的關系圖。這個關系圖有兩個約束：光網絡拓撲的約束和承載業務的分布約束。

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

多故障定位的目標是尋找包含故障數目最少的故障集合。即使能夠尋找到計算性能優良的啟發式算法解決了NP－complete的困難，但是最少數目的故障集合可能不止一個，如何選擇和處理這些集合仍困難。況且最少數目的故障集合并不一定是真實網絡中一定發生的故障，網絡管理者只是認為最少數目的故障集合更有理由發生。

多故障時空隨機出現、網絡復雜化(無標度網絡、隨機網絡)、承載業務的多樣性是P比特級光網絡的顯著特征。其中網絡復雜化(無標度網絡、隨機網絡)、承載業務的多樣性增加了多故障定位第一個階段的復雜度，使得獲得的故障和告警的關系圖更加復雜、耗時，而且得到的關系圖不再是靜態而是動態變化的。多故障時空隨機出現增加了多故障定位的第二個階段的復雜度，因為收到的告警包是隨機達到故障管理中心的，不同的告警集合及故障集合有著明顯的區別，如何處理告警包的隨機性，成為研究的關鍵。

3、模糊故障定位和蟻群優化

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

由于承載業務的多樣性使得獲得的故障和告警的關系圖更加復雜并且是動態變化的，此時故障和告警的關系不再是確定性的必然事件。我們用模糊數學的隸屬關系來描述故障和告警，告警是在一定程度上隸屬于觸發它的故障，得出這樣的結論的依據是：

(1)承載業務的多樣性、業務動態的拆建使得故障管理中心無法實時地得到下游的節點告警，告警和故障的關系不再是確定性關系。而根據業務到達的分布，可以得到告警和故障的隸屬度。

(2)網絡復雜化(無標度網絡、隨機網絡)使得業務的路由多樣化。相同源和宿業務的路由在不同時刻有著不同的路由，使得故障和告警的關系圖動態變化。基于路由的多樣性，可以得到告警和故障的隸屬度。

(3)隨著網絡的運行時間的增長，伴隨著故障定位問題的成功和失敗，可以根據以往成功的經驗建立專家系統。這個專家系統需要能夠很好地描述網絡故障和告警的關系。

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

(1)模糊統計法

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

(2)例證法

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

(3)專家經驗法

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

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

4、仿真驗證

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

5、結束語

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