[發明專利]一種基于最小支配集分簇的光網絡故障定位方法

有效

• 申請號: 201210307758.0
• 申請日: 2012-08-27
• 公開（公告）號: CN102801468A
• 公開（公告）日: 2012-11-28
• 發明（設計）人: 熊余;張鴻;王汝言;吳大鵬
• 申請（專利權）人: 重慶郵電大學
• 主分類號: H04B10/08
• 分類號: H04B10/08
• 代理公司: 重慶市恒信知識產權代理有限公司 50102
• 代理人: 劉小紅

技術領域

本發明涉及光通信技術領域，具體涉及光波分復用網絡中一種故障定位方法。

背景技術

隨著波分復用（WDM）技術在全光網絡中的應用，光纖所能承載的業務量不斷增大，單光纖傳輸速率已能達到40Gbit/s甚至更高。而一個短暫的網絡故障，特別是經常發生的光纖斷裂等鏈路故障將會引起海量數據丟失。因此，網絡的生存性管理尤其重要，其中故障定位是恢復丟失業務的前提和保證。準確快速地感知光網絡傳輸質量和故障位置，將有效地降低網絡故障所帶來的損失。

目前光網絡的故障定位方法主要有兩大類。第一類可以歸納為基于監測設備的故障定位方法，主要采用監測設備覆蓋全網的方法定位故障。即通過一定的方法將監測波長覆蓋整個網絡并安放監測器，當網絡出現故障時，收集各個監測器的故障告警代碼，然后查找故障代碼表，最后定位出故障鏈路。如Hongqing?Zeng等人在“A?novel?fault?detection?an?localization?scheme?for?mesh?all-optical?networks?based?on?monitoring?cycles”【Photonic?Network?Communications,?May.2006,?11（3）:277-286】中提出的經典M-cycle（Monitoring?cycles）算法。該算法利用構造圈將整個網絡覆蓋，使每一條鏈路具有唯一的故障告警代碼，當網絡發生故障后M-cycle算法可以快速的定位故障。這類故障定位方法雖然能實現快速有效的光網絡鏈路故障定位，但難以做到完全故障定位并需要產生大量的額外開銷（監測器和監測波長的開銷），同時該類方法需要監測波長多次覆蓋同一條鏈路，進一步增加了故障定位的成本。

另一類故障定位方法是基于業務感知的故障定位方法。其主要是通過感知業務光通路的中斷與否來完成故障定位，因此它在實現準確故障定位的基礎上，節省了大量監測器和監測波長的開銷。如Hussein?T.?Mouftah等人在專利“Limited?perimeter?vector?matching?fault?localization?protocol?for?survivable?all-optical?networks”【United?States,?US20070787201，Dec?6,?2007】中提出了有限周邊矢量匹配協議（Limited-perimeter?vector?matching?protocol，LVM）的故障定位方法。該方法無需額外的監測器件和監測波長，可以節省大量的定位成本，但其對業務依賴性較高，必須至少要兩個光通道經過一條鏈路才能準確定位故障，且這兩個光通道必須要有不同的源節點和目的節點。同時LVM需要節點間多次交換信息導致定位時間較長。因此，對于LVM這種基于業務感知的故障定位方法，如何提高故障定位的速度和減小對業務的依賴性，仍是目前亟待解決的難題。

發明內容

本發明所要解決的技術問題：針對現有光網絡的鏈路故障定位方法成本開銷高、定位速度慢、業務依賴大等問題，本發明提出一種基于最小支配集分簇的故障定位方法。該方法屬于業務感知的定位方法，主要基于最小支配集理論，把光網絡的各個節點優化地劃分在不同簇中，通過簇頭節點和匯聚節點快速收集鏈路信息，從而實現全網的故障定位。本發明實現了低開銷下對網絡單鏈路故障的準確定位，同時相比現有方法提升了故障定位的速度和降低了對業務的依賴。

本發明解決其技術問題所采用的技術方案：提出一種基于最小支配集分簇的光網絡故障定位方法，該方法包括離線計算和在線計算兩部分。離線計算是將網絡根據物理拓撲進行最優化分簇，在線計算是當網絡出現故障時通過簇頭節點收集鏈路信息表以及匯聚節點收集簇頭矩陣，節點將收集到的信息進行匹配后定位出故障鏈路。

離線計算：首先根據網絡物理拓撲確定網絡的所有最小支配集，并利用最短路徑算法分別計算各最小支配集的直徑，將直徑最小的支配集作為最優的最小支配集。然后將最優的最小支配集中節點設為簇頭節點，隨后遍歷網絡中的所有節點，將簇頭節點鄰接的節點作為成員節點加入該簇頭所在的簇。簇頭節點承擔收集簇內成員節點的鏈路信息表和將簇頭矩陣發送給匯聚節點的任務。最后在簇頭節點中選取匯聚節點，選取匯聚節點的規則為：首先利用最短路徑算法計算每一個簇頭節點到其他任意簇頭節點的最大距離，然后選取該最大距離最小的簇頭節點作為匯聚節點。匯聚節點可同時作為簇頭節點和匯聚節點。此時網絡被分為兩層簇結構，第一層是簇頭節點和簇內成員節點所組成的多個星形網絡結構，第二層是簇頭節點和匯聚節點組成的星形網絡結構。