基于光通路状态感知的分簇式故障定位机制

熊 余 张 鸿 王汝言 吴大鹏



基于光通路状态感知的分簇式故障定位机制

熊 余①②张 鸿*①王汝言①吴大鹏①

①(重庆邮电大学光纤通信技术重点实验室 重庆 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