基于光通路狀態感知的分簇式故障定位機制

熊 余 張 鴻 王汝言 吳大鵬

?

基于光通路狀態感知的分簇式故障定位機制

熊 余①②張 鴻*①王汝言①吳大鵬①

①(重慶郵電大學光纖通信技術重點實驗室 重慶 400065)②(重慶大學計算機學院 重慶 400030)

針對現有故障定位機制定位時間長和對業務分布依賴高等問題，該文提出基于光通路狀態感知的分簇式故障定位機制。該機制根據網絡分簇約束條件，以最小支配集理論為基礎，建立兩級網絡模型。并且根據算法特點，定義了適用于該算法的“矩陣與”運算。故障后簇頭節點以及匯聚節點通過對各節點發送的矩陣進行“矩陣與”運算實現快速準確的故障定位。仿真表明，該機制以較低的復雜度和資源開銷，有效地降低了對業務分布的依賴，極大地提升了故障定位率，減少了故障定位時間。

光網絡；故障定位；分簇；最小支配集

1 引言

波分復用(Wavelength Division Multiplexing, WDM)技術的發展使得光網絡的帶寬得到了極大提升。但這也使網絡發生故障時將導致大量的業務中斷。因此，網絡的抗毀設計至關重要，而快速準確地找出故障發生的位置是構建高抗毀光網絡的前提[1,2]。

為此，文獻[3-5]中提出了監測圈(monitoring- cycle, m-cycle)故障定位機制。它利用圈形的監測通路覆蓋全網鏈路并構造告警代碼表。故障后通過查找告警代碼表來實現故障定位。雖然監測圈能快速地找出故障，但其不能達到100%的故障定位率。為此文獻[6-8]提出監測跡(monitoring-trails, m- trails)，其和監測圈不同的是，它可以使用任意形狀的監測通路。為進一步減少開銷，文獻[9]又提出監測樹(monitoring-tree, m-tree)故障定位機制，同時文獻[10,11]提出了監測樹的啟發式算法，有效降低了算法的復雜度。但是監測樹機制要求節點具有多播能力，存在一定局限性。上述機制雖然故障定位性能都較好，但每條監測通路都要配置監測器，占用了較多的波長資源，定位的成本較高。

為實現低開銷的故障定位，文獻[12]利用貝葉斯網絡定位通信網故障，然而其不能達到較高的故障定位率且計算復雜度較高。文獻[13]提出一種分布式的有限周邊矢量匹配(Limited perimeter Vector Matching, LVM)協議。該協議通過節點感知的信息，將故障限制在一個小區域(Limited-Perimeter, LP)內，然后通過所限區域內的節點交換通路的狀態信息，并巧妙地利用節點間信息的關聯性實現準確的故障定位。LVM無需在網絡中配置監測器及監測波長，節省了大量成本，顯然業務分布的情況對該協議的性能有重要影響。為此，文獻[14,15]以最大化故障定位率和最小化故障定位時間為目標建立整數線性規劃(Integer Linear Programming, ILP)模型來優化業務分布，同時提出了啟發式算法，減少了計算復雜度。雖然LVM解決了故障定位成本高的問題，但其存在對業務分布依賴大的缺陷。必須至少要兩條光通路經過同一條鏈路，且這兩條通路必須要有不同的源宿節點才能實現故障的準確定位。同時LVM包括廣播、競爭、多播、匹配、故障定位等多個環節，節點之間需要多次交換信息，因此其故障定位時間也較長。

為進一步降低對業務分布的依賴性及減少故障定位時間，本文提出了一種基于光通路狀態感知的分簇式(lightpath Status Aware using Cluster Allocation, SACA)故障定位機制。該機制分為基于最小支配集的網路分簇算法(Cluster Allocation Algorithm, CAA)和基于光通路狀態感知的分布式故障定位算法(Fault Location Algorithm, FLA)。CAA引入最小支配集理論對網絡進行最優化分簇，建立兩層的網絡結構。第1層結構包括簇頭(Cluster Head, CH)節點和簇內成員(Cluster Member, CM)節點，第2層結構包括CH節點和匯聚節點(Sink Node, SN)。FLA通過在各個簇內感知光通路的通斷狀態構建矩陣，并通過“矩陣與”運算實現分布式故障定位。

2 基于最小支配集的網絡分簇算法(CAA)

分簇方法已經被廣泛運用于無線傳感器網絡中[16,17]，在光網絡的故障恢復及業務量疏導中也有相應研究[18,19]。本文在光網絡故障定位研究中引入分簇，利用多個CH節點實現分布式的快速故障定位。既消除了只有一個節點才能定位故障的約束，同時也縮小了節點發送信息的區域，極大降低了故障定位的時間。

2.1 分簇約束條件

在故障定位過程中，各個CH節點收集本簇CM節點感知的故障信息后，通過計算各個節點間信息的關聯性完成分布式的故障定位。如果各個CH節點無法獨立完成故障定位，將由SN節點統一進行故障定位。為了快速定位故障，要求CH節點和SN節點能快速收集信息；同時由于SN節點定位需要較長時間，應盡量使故障能夠在CH節點被定位。可見，對網絡分簇時應遵循以下約束。

2.2 算法步驟

步驟3 網絡分簇。將最優支配集中的節點設為CH節點，并在網絡中遍歷所有節點。如果節點與某個CH節點鄰接，則將該節點加入該CH節點所在簇；如果節點與多個CH節點鄰接，則將該節點同時加入多個CH節點所在簇。如果有兩個CH節點鄰接，則將兩個CH節點分別加入與其鄰接的CH節點所在簇，這時這兩個CH節點同時有兩個身份：一個是本簇的CH節點和其它簇的成員節點。

3 基于光通路狀態感知的分布式故障定位算法(FLA)

3.1“矩陣與”運算

根據本算法特點，提出一種新的適用于本算法的運算式“矩陣與”。

圖1 網絡分簇示意圖

3.2 算法步驟

當網絡發生故障后，各個CH節點同時進行分布式的故障定位，如果CH節點沒有定位出故障，則各個CH節點將信息發送給SN節點，由SN節點進行統一的故障定位。FLA算法的具體步驟如下：

(1)當節點為光通路的目的節點時，LI中包括光通路經過的鏈路以及光通路的狀態。

(2)當節點為光通路的中間節點時，LI中包括光通路從源節點到本節點所經過的鏈路以及從源節點到本節點這部分光通路的狀態。

當光通路狀態位為1時，表示光通路斷開；當光通路狀態位為0時，表示光通路正常。下面給出一個構造LIT的實例。圖2中鏈路6-7發生故障后。節點6產生的LIT如表1所示，其中NULL為填充字段。此時有兩個光通路經過節點6，因此LIT中包括兩個LI。

節點6為光通路1-4-5-6的目的節點，該光通路正常工作，狀態位置0。由于節點6為光通路1-3-6-7的中間節點，雖然對節點7來說該光通路已中斷，但是對節點6來說，部分光通路1-3-6是正常的，所以其狀態位置仍為0。

圖2 構造LIT示例圖

表1節點6構造的LIT示意表

鏈路狀態 1-44-55-60 1-33-6NULL0

步驟2 生成故障鏈路向量(Fault Link Vector, FLV)。若某節點的LIT中所有LI狀態位都是0，則表示該節點感知到的所有鏈路都正常，那無需產生FLV，跳過步驟2轉到步驟3。當構造LIT后，各個節點(CH節點和CM節點)將LIT中的所有LI逐一與匹配對象(Matching Object, MO)進行匹配，得到二進制向量表(Binary Vector Table, BVT)并生成FLV。

首先，各個節點在LIT中查找狀態為1且經過的鏈路數最少的LI，即搜索中斷的最短光通路并將該LI保存的光通路作為本節點的MO。顯然，故障鏈路必在MO中。然后將MO逐一與LIT中的每一個LI(除了MO)匹配。每次匹配的結果都是一個二進制向量(Binary Vector, BV)。所有的匹配結果都保存在一個BVT中，如表2所示，是一個BVT的示例。每個BV包含了MO中的鏈路以及對應鏈路的狀態。若該鏈路狀態為0，則表示該鏈路正常；若該鏈路狀態為1，則表示該鏈路有可能發生故障。匹配規則如下。

表2 BVT結構示意表

鏈路 MO1-33-6 BV10 11

(1)當需要匹配的LI狀態位為0時，表示該LI中的鏈路都正常。則如果MO與該LI中有相同的鏈路，則將BV中該鏈路對應的值設為0，反之為1。

(2)當需要匹配的LI狀態位為1時，表示該故障鏈路必然在該LI中且該LI中的鏈路都有可能是故障鏈路。則如果MO與該LI中有相同的鏈路，則將BV中該鏈路對應的值設為1，反之為0。

當匹配完成之后，將BVT中所有BV進行邏輯與操作，生成FLV。該FLV中含有本節點處理后的故障鏈路信息。FLV的生成實例如表3。

表3 FLV生成實例

(1)如果該節點已經產生FLV，采用式(8)構造。

(2)如果該節點沒有產生FLV，即該CH節點接收到的所有LI的狀態位都是0。采用式(9)構造。

但是業務分布如圖3所示的情況時，簇間鏈路可以被CH節點定位。圖3中，光通路-----與光通路-----同時經過簇間鏈路-。當簇間鏈路-發生故障后，簇間鏈路的端節點會感知到光通路---與光通路---發生中斷且這兩條中斷的光通路必然同時經過故障鏈路，而這兩條中斷的光通路只有簇間鏈路-重合。因此根據故障的唯一性，通過“矩陣與”運算后即可定位故障鏈路-。

圖3 簇間鏈路故障示意圖

4 仿真分析

由于SACA通過光通路狀態感知進行故障定位，因此業務光通路的分布模型在很大程度上影響著SACA的性能，使用以下業務分布模型與SACA, LVM兩種算法結合仿真。

(1)基于路徑長度Dijkstra最短路徑算法的經典業務分布模型，簡稱為Dijkstra業務分布模型。

(2)基于文獻[15]中啟發式算法Greedy模式的業務分布模型，簡稱為Greedy業務分布模型。

仿真的性能指標如下所示。

定義2 故障定位率(Fault Location Rate, FLR)為可被定位的鏈路數與總鏈路數之比。如式(12)。

定義3 隨機故障定位時間(Random Fault Location Time, RFLT)為故障鏈路隨機的情況下，SACA定位故障所用時間。

定義4 簇間鏈路故障定位比(Inter-cluster Link fault location Rate, ILR)為可以被CH節點定位的簇間鏈路數與總的簇間鏈路數之比，如式(13)。

定義5 簇間鏈路平均故障定位時間(Inter- cluster link Average fault location Time, IAT)為所有簇間鏈路故障定位時間之和與簇間鏈路數之比，如式(14)所示。

4.1故障定位率

圖4~圖6分別為3個網絡的FLR仿真圖。可以看出，當SACA與LVM同時使用Dijkstra業務分布模型時，SACA在FLR上明顯優于LVM。這是因為SACA機制降低了對業務的依賴性，即只需要一條光通路經過一條鏈路，當該鏈路故障后即可快速定位故障。而LVM卻需要兩條不同源目的節點的光通路同時經過該鏈路才可定位故障。當LVM結合Greedy業務分布模型之后，故障定位率得到了一定的提升，因為Greedy的目的是盡量讓鏈路滿足LVM故障定位的條件。同時當SACA結合Greedy業務分布模型后，FLR也得到了明顯的提升，因為Greedy在一定程度上使用了負載均衡的思想，優先使用只有一條光通路被占用或者空閑的鏈路。這在一定程度上也滿足SACA的定位條件。

圖4 COST239網絡FLR仿真圖

圖5 USNET網絡FLR仿真圖

圖6 NSF網絡FLR仿真圖

4.2 隨機故障定位時間

在圖8，圖9中LVM的RFLT較大，已經達到50 ms左右。這是因為USNET網絡較大和NSF網絡連通度較小，而LVM需要向網絡中每個節點廣播消息，同時業務通路較長，導致LP區域也增大，且LVM需要在LP區域中交換兩次信息，導致LVM需要較長的故障定位時間。因此LVM并不適合在大中型網絡和連通度較小的網絡中應用。SACA機制利用多個CH節點在網絡中進行定位，每個CM節點都可以通過單跳鏈路將信息傳輸到CH節點。因此SACA機制在大中型網絡中亦可應用，且性能較好。但是當CH節點無法獨立進行定位時，需要將信息傳輸到SN節點進行統一定位，此時則需要較長的時間，然而此時較長的定位時間仍然遠遠小于LVM的故障定位時間。而不同的業務分布模型下的故障定位時間大致相當，這是因為Greedy的主要目的是優化故障定位率。

4.3 簇間鏈路的故障定位比與平均故障定位時間

簇間鏈路發生故障后的定位性能對整個機制性能有重要影響，這可以通過ILR和IAT的仿真來評估。圖10和圖11為ILR, IAT在不同網絡中的性能情況，其業務分布模型為分布較均勻的Greedy業務分布模型。可以看出隨著業務的增多，ILR逐漸上升，這是因為業務較多后，有較大的概率使業務通路滿足如圖3所示的定位條件。同樣可以看出隨著負載的增大，IAT逐漸減小，這是由于當負載增大后，較多的簇間鏈路可以被CH節點定位，而CH節點定位時間較少，從而導致IAT逐漸減小。

5 結束語

為了解決現有故障定位機制資源開銷大、對業務依賴性高、定位速度低等缺陷，本文提出基于光通路狀態感知的分簇式故障定位機制(SACA)。首先將網絡進行最優化分簇，當故障發生后，各個簇頭節點接收成員節點的簇內矩陣，并進行“矩陣與”運算生成簇頭矩陣。若簇頭矩陣中沒有準確顯示故障，則將簇頭矩陣發送給匯聚節點并計算出定位矩陣，故障鏈路必為定位矩陣中值為1的鏈路。結果表明，SACA能解決資源消耗問題、降低了機制對業務的依賴性，并且極大降低了故障定位時間。對于未來工作，可以通過優化網絡分簇模型和業務分布模型，來進一步提升故障定位機制的性能。

圖7 COST239網絡RFLT仿真圖

圖8 USNET網絡RFLT仿真圖

圖9 NSF網絡RFLT仿真圖

圖10 各網絡ILR仿真圖

圖11 各網絡IAT仿真圖

[1] Chao C S and Lu S P. Toward efficient multi-link failure diagnosis by using monitoring cycle for all-optical mesh networks[C]. International Conference on Information Networking (ICOIN), Indonesia, 2012: 228-233.

[2] Xiong Yu, Xiong Zhong-yang, Wu Da-peng,Multi-fault aware parallel localization protocol for backbone network with many constraints[J]., 2012, 24(3): 210-218.

[3] Wu Bin, Yeung K L, and Ho P H. Monitoring cycle design for fast link failure localization in all-optical networks[J]., 2009, 27(10): 1392-1401.

[4] Wu Bin, Yeung K L, and Ho P H. M2-cycle: an optical layer algorithm for fast link failure detection in all-optical networks[J]., 2011, 55(3): 748-758.

[5] Mao Min-jing and Yeung K L. Super monitor design for fast link failure localization in all-optical networks[C]. Preceedings of the IEEE International Conference on Communications (ICC), Kyoto, 2011: 1-5.

[6] Tapolcai J, Wu Bin, Ho P H,A novel approach for failure localization in all-optical mesh networks[J]./, 2011, 19(1): 275-285.

[7] Wu Bin, Ho P H, Yeung K L,Optical layer monitoring schemes for fast link failure localization in all-optical networks[J]., 2011, 13(1): 114-125.

[8] Tapolcai J, Ronyai L, and Ho P H. Link fault localization using bi-directional m-trails in all-optical mesh networks[J]., 2012, 61(1): 1-10.

[9] Doumith E A, Zahr S A, and Gagnaire M. Monitoring-tree: an innovative technique for failure localization in WDM translucent networks[C]. Preceedings of the IEEE Global Telecommunications Conference(GLOBECOM), Miami, FL, 2010: 1-6.

[10] Doumith E A, Zahr S A, and Gagnaire M. A novel meta-heuristic approach for optical monitoring-tree design in WDM networks[C]. Preceedings of 16th International Conference on Optical Network Design and Modeling (ONDM), Colchester, 2012: 1-6.

[11] Huang Yi-fan, Huang Jun, and LiXin. A heuristic for monitoring tree design[C].Preceedings of the 2012 International Conference on Measurement, Information and Control (MIC), Harbin, 2012: 971-975.

[12] 張成, 廖建新, 朱曉民. 一種基于增量貝葉斯疑似度的事件驅動故障定位算法[J]. 電子與信息學報, 2009, 31(6): 1501-1504.

Zhang Cheng, Liao Jian-xin, and Zhu Xiao-min. An event- driven fault localization algorithm based on incremental bayesian suspected degree[J].&, 2009, 31(6): 1501-1504.

[13] Sichani A V and Mouftah H T. Limited-perimeter vector matching fault-localisation protocol for transparent all- optical communication networks[J]., 2007, 1(3): 472-478.

[14] Khair M G, Kantarci B, Zheng Jun,Optimization for minimizing fault localization time in all-optical networks[C]. Preceedings of 10th International Conference on Transparent Optical Networks(ICTON), Athens, 2008: 63-66.

[15] Khair M G, Kantarci B, and Mouftah H T. Optimization for fault localization in all-optical networks[J]., 2009, 27(21): 4832-4840.

[16] Chaudhary M Hand Vandendorpe L.Performance of power-constrained estimation in hierarchical wireless sensor networks[J]., 2013, 61(3): 724-739.

[17] Lee Jin-shyan and Cheng Wei-liang. Fuzzy-logic-based clustering approach for wireless sensor networks using energy predication[J]., 2012, 12(9): 2891-2897.

[18] Hwang I S, Tu M Y, Tseng W D,A novel dynamic fault restoration mechanism using cluster allocation approach in WDM mesh networks[J]., 2006, 29(18): 3921-3932.

[19] Chen B, Rouskas G N, and Dutta R. Clustering methods for hierarchical traffic grooming in large-scale mesh WDM networks[J]./, 2010, 2(8): 502-514.

[20] 吳大鵬, 李陽, 王汝言. 基于騎士巡游的Mesh光網絡鏈路故障定位策略[J]. 重慶郵電大學學報(自然科學版), 2011, 23(1): 1-5.

Wu Da-peng, Li Yang, and Wang Ru-yan. A link failure localization strategy based on knight’s tour for mesh optical network[J].(), 2011, 23(1): 1-5.

熊 余： 男，1982年生，副研究員，博士生，研究方向為寬帶網絡可靠性理論及抗毀技術.

張 鴻： 男，1987年生，碩士生，研究方向為光網絡故障管理.

王汝言： 男，1969年生，教授，研究方向為空間光通信、光網絡理論與技術、光信息處理、通信網絡可靠性與故障管理.

Fault Location Mechanism Based on Lightpath Status Aware Using Cluster Allocation

Xiong Yu①②Zhang Hong①Wang Ru-yan①Wu Da-peng①

①(,,400065,)②(,,400030,)

A fault location mechanism is proposed based on lightpath status aware using cluster allocation to solve the issues of long fault location time and high service dependence. According to the constraints of network clustering, two-layer network model is established through the minimum dominating set theory. In addition, a new operation called “matrix and” is defined in the proposed mechanism. When a link failure occurs, the cluster head and sink node will achieve fast and accurate fault location via the operation of “matrix and”. The simulation shows that the fault location rate and fault location time are significantly improved with lower complexity and resource cost.

Optical network; Fault location; Cluster; Minimum dominating set

TN915.07

A

1009-5896(2014)01-0041-07

10.3724/SP.J.1146.2013.00214

2013-02-20收到，2013-07-02改回

國家自然科學基金(60972069, 61001105)，重慶市自然科學基金(2011BA2041)，重慶市教委科學技術研究項目(KJ110531)和重慶市高校優秀人才支持計劃(2011-29)資助課題

張鴻 zhanghong1987824@qq.com