P比特光网络多故障定位的NP-complete问题研究

基金项目：国家重点基础研究发展(“973”)规划(2010CB328202、2010CB328204)；国家自然科学基金(60702005)

    随着超大容量(P比特级)光网络规模的扩大和传输速率的提高，使得网络遭受自然灾害破坏、人工操作失误和软件配置错误等多重故障的概率增加，将降低光网络带宽提供的可靠性，增加保护恢复资源配置冗余和调度的复杂性。超大容量(P比特级)光网络采用基于时空标记的分类服务方法，从时空角度对网络资源(包括路由、波长、链路、节点等)进行整合与优化。多业务端到端服务质量(QoS)需求与光网络时空多重故障生存性之间存在复杂的关系。由于光网络元素(节点、链路)的故障能够向业务流的下游节点进行传播，而使时空多重故障情况下故障管理中心收到大量的告警包，其中包含大量的冗余告警包，造成故障管理中心告警包数目急剧增多。理论已经证明，依据收到的告警包进行多故障的甄别属于非多项式完全问题(NP-complete)问题：通常情况下得不出准确的故障发生的数目和故障发生的位置[1]。光网络多故障定位困难可以描述为：可以在多项式时间内判定一个故障的集合是不是观测到的检测设备发出告警的原因，但是无法在多项式时间内根据观测到的告警集合推断出故障的集合。

    网络拓扑复杂化和承载业务的多样性是P比特级光网络两个基本的特点，而多故障定位NP-complete问题的困难与网络拓扑和网络承载的业务相关。在P比特级光网络里多故障定位的NP-complete属性：更难寻找包含故障元素最少的故障集合和寻找包含故障元素最少的故障集合的时间与网络拓扑的输入规模成指数增长关系。由于多故障定位属于NP-complete问题，很难得到故障的准确的数目和位置。默认的约定是：在保证推断出的故障集合一定能产生故障管理中心收到的告警情况下认为故障集合中的元素越少越是最有可能发生。已有的故障定位机制最后给出的故障集合都是在这种约束下给出的，但在这种约束条件下得到的故障集合并不一定是网络真实发生的故障，而且在这种约束下网络存在一些故障情况使得任何故障定位算法都无法处理。

1 多故障定位算法
    多故障定位机制主要分为集中式和分布式，应用的光网络类型为非全光网和全光网[2]。在非全光网中光路的中间节点对光信号进行光电转化，能够检测到故障并且可以屏蔽某些类型的故障向下游的传播。全光网中只有光路的宿节点或者所经过域的边界节点才对信号进行光电转换，才能检测到故障。一般情况下，集中式方法需要详细的网络元素模型用于故障定位，分布式机制依靠持久连接(Keep-alive)或通知消息甄别出故障的根源[3]。

    表1列出了已有的故障定位机制，透明的故障定位算法(层1)、推理算法(层1)、运行长度探测算法(层1)、启发式生成树M-cycle算法(层1、2、3)属于集中式的故障定位算法，链路管理协议(层3)、端到端故障检测和定位协议(层3)、有限区域向量匹配协议(LVM)协议属于分布式故障定位协议。

    文献[4]研究透明光网络中故障管理的常规问题，对网络中的设备进行建模，得到每个设备可能检测到的故障和可能屏蔽的故障，然后根据得到的告警包去遍历一个告警的二叉树，最后得到可能的故障元素。该算法可应付4种故障：功率下降、波长错误部署、带内干扰、带外干扰。

    文献[5]研究真实环境中的多故障定位(观察到的告警可以是不可靠的)。核心问题为离散优化问题。目标是要找到故障集合和告警集合，最小化成本函数。文献[5]提出了启发式算法的解决方案。该算法的复杂度集中在一个预先计算阶段，需要遍历一个二叉树。

    文献[8]链路管理协议(LMP)是通用多协议标记交换(GMPLS)协议栈的重要组成部分，通过在一对节点之间交换活动状态通道(Channel Active)和失效状态通道(Channel Fail)消息来实现不透明或透明网络中的故障定位，而不必关心编码格式。LMP协议并不单一运行在一个平面，涉及到控制平面和数据平面的协同工作。

    文献[10]LVM协议的核心是如果两条光路同时经过一段链路，若这两个业务的目的节点都检测到故障，就认为这个故障的链路就是这个共享风险的链路。这个协议为单故障定位设计。扩展的LVM协议支持多故障定位。

2 多故障定位问题描述
    对于超大容量(P比特级)光网络，影响到故障定位复杂度的因素主要包括：多故障时空随机出现、网络复杂度(无标度网络、随机网络)、承载业务的多样性(业务种类、业务级别、QoS)。通常情况下多故障定位的目标是根据得到的告警指示，找出可能的故障集合，并且认为得到的集合中的故障数目越少越好。下面描述一般意义下故障定位的困难，然后阐述解决NP-complete在P比特级光网络中变得更加困难，且随着网络规模的增大定位的计算复杂度和计算时间与网络的输入规模成指数增长关系。

    多故障定位的线性规划形式：

    t时刻可能出现的故障集合F(t):F1,F2,F3,F4……
    t时刻故障管理中心收到的告警集合A(t)：a,b,c,d,e,f,g,h……

    约束条件：A(F1)+A(F2)+A(F3)+A(F4)+……=A(t)。其中函数A(F )表示仅仅故障F触发的告警的集合。
目标函数：min(CTF ),C=(1，0，1……)。C中元素为1或者0的列向量，目的是寻找一个包含故障数目最少的集合。

    根据光网络拓扑和网络中的业务分布，我们得到如图1所示故障和告警关系的二部图。图的下面是故障管理中心收到的告警的集合，上面是可能的故障元素。故障定位的任务是根据关系图，找到一个故障的集合，使得故障集合中的故障数目最少。多故障定位可分两阶段完成：

    (1)获得故障和告警的关系图。这个关系图有两个约束：光网络拓扑的约束和承载业务的分布约束。

    (2)根据得到的关系图，运用有效的算法得到包含故障数最少的故障集合，其中第二阶段中寻找最少数目的故障集合属于NP-complete问题。

    多故障定位的目标是寻找包含故障数目最少的故障集合。即使能够寻找到计算性能优良的启发式算法解决了NP-complete的困难，但是最少数目的故障集合可能不止一个，如何选择和处理这些集合仍困难。况且最少数目的故障集合并不一定是真实网络中一定发生的故障，网络管理者只是认为最少数目的故障集合更有理由发生。

    多故障时空随机出现、网络复杂化(无标度网络、随机网络)、承载业务的多样性是P比特级光网络的显著特征。其中网络复杂化(无标度网络、随机网络)、承载业务的多样性增加了多故障定位第一个阶段的复杂度，使得获得的故障和告警的关系图更加复杂、耗时，而且得到的关系图不再是静态而是动态变化的。多故障时空随机出现增加了多故障定位的第二个阶段的复杂度，因为收到的告警包是随机达到故障管理中心的，不同的告警集合及故障集合有着明显的区别，如何处理告警包的随机性，成为研究的关键。

3 模糊故障定位和蚁群优化
    为了解决P比特级光网络对多故障定位两阶段带来的影响，本文针对每个阶段提出了各自的优化策略：故障和告警关系的模糊化(第一阶段)、蚁群优化算法(第二阶段)。

    由于承载业务的多样性使得获得的故障和告警的关系图更加复杂并且是动态变化的，此时故障和告警的关系不再是确定性的必然事件。我们用模糊数学的隶属关系来描述故障和告警，告警是在一定程度上隶属于触发它的故障，得出这样的结论的依据是：

    (1)承载业务的多样性、业务动态的拆建使得故障管理中心无法实时地得到下游的节点告警，告警和故障的关系不再是确定性关系。而根据业务到达的分布，可以得到告警和故障的隶属度。

    (2)网络复杂化(无标度网络、随机网络)使得业务的路由多样化。相同源和宿业务的路由在不同时刻有着不同的路由，使得故障和告警的关系图动态变化。基于路由的多样性，可以得到告警和故障的隶属度。

    (3)随着网络的运行时间的增长，伴随着故障定位问题的成功和失败，可以根据以往成功的经验建立专家系统。这个专家系统需要能够很好地描述网络故障和告警的关系。

    隶属函数是模糊故障定位的基石，已有隶属函数的确定方法[11]：

    (1)模糊统计法
    模糊统计法的基本思想是对论域上的一个确定元素是否属于论域上的一个可变动的清晰集合做出清晰的判断。

    (2)例证法
    例证法的主要思想是从已知有限个μA的值，来估计论域μ上的模糊子集A的隶属函数。

    (3)专家经验法
    专家经验法是根据专家的实际经验给出模糊信息的处理算式或相应权系数值来确定隶属函数的一种方法。在许多情况下，经常是初步确定粗略的隶属函数，然后再通过学习和实践检验逐步修改和完善，而实际效果正是检验和调整隶属函数的依据。

    这样在得到的故障和告警的关系图中，故障和告警之间不再是确定的关系，每条故障和告警之间的连接都将赋予一个隶属度(0~1)，这个隶属度反映网络拓扑和业务分布在一段时间内对告警和故障关系的影响。我们采用例证法来进行隶属度的计算。蚁群算法(ACO)是一种基于种遍历所有告警群的启发式仿生进化算法[12]。ACO已经成功用于解决许多组合优化问题，最早的应用就是解决旅行推销员、货郎问题(TSP)问题。蚁群算法是对自然界蚂蚁的觅食寻路方式进行模拟而得出的一种仿生算法，充分利用了选择、更新和协调的优化机制。即通过个体之间的信息交流与相互协作最终找到最优解，使它具有很强的发现较优解的能力。假如将告警作为图的节点，而故障作为经过的链路，多故障定位很容易转化为旅行售货商问题。蚂蚁经过一个告警并为这个告警选择相应的产生此告警的故障。当所有蚂蚁遍历所有的告警后，就得到故障的一个集合。蚂蚁释放的信息素与故障集合的元素的个数成反比，故障元素的数目越少。释放的信息素越多。启发式信息与每个故障节点的度成正比。

4 仿真验证
    本文在波长交换光网络(WSON)仿真平台上实现模糊隶属关系和蚁群优化算法的多故障定位。平台基本功能采用了IETF的GMPLS协议。COST239仿真拓扑如图2所示。有11个物理链路节点和25条物理链路。网络类型为全光网(只有每条光路的宿节点或者域的边界节点可以检测到故障)。仿真仅仅考虑链路故障。1～25条物理链路上随机的3条链路出现故障。产生故障的光路的宿节点都能够检测到故障。物理拓扑上任意两个节点承载的业务采用泊松分布。业务的路由采用D算法实现，不考虑资源约束。方案旨在验证多故障定位方案。仿真结果如图3所示，分别进行了蚁群多故障和扩展的LVM协议多故障定位。红黑曲线计算多故障定位成功率的方式为故障数目和定位的故障与预先设置的故障数目和故障完全一致则认为多故障定位成功，否则失败。蓝绿曲线计算多故障定位成功率的方式为成功的故障数目除以得到的故障集合的故障数目。左边的仿真结果图为3故障，右边的仿真结果图为4故障，从成功率对比可以看出，随着故障数目的增加，蚁群要逐渐优于扩展的LVM协议，在大规模和多故障情况下，蚁群算法能取得更优的性能。

5 结束语
    本文主要研究网络出现多重故障下快速的故障定位机制，为后续的受损业务的恢复以及故障的维修提供可靠的时间保证。模糊数学以不确定性的事物为其研究对象。模糊集合的出现是适应描述复杂事物的需要。依据模糊集合的理论找到解决模糊性对象加以确切化，从而使研究确定性对象的数学与不确定性对象的数学沟通起来。蚁群算法是一种源于自然界中生物的仿生类模拟进化算法，对求解复杂组合优化问题有如下的优势：较强的鲁棒性、具有并行性。基于P比特级光网络的多故障时空随机出现、网络复杂化、承载业务多样性的特点，本文将模糊数学和蚁群算法相结合提出了多故障定位的两个阶段的优化策略，分别为模糊的告警故障隶属度关系和蚁群优化多故障定位算法。仿真验证给出了在两种策略下P比特级光网络寻找最优故障集合解过程的成功率。

6 参考文献

[1] RAO N S V. Computational complexity issues in operative diagnosisof graph-based systems [J]. IEEE Transactions on Computers, 1993,42(4):447-457.
[2] KOBAYASHI Y, TADA Y, MATSUOKA S, et al. Supervisory systems for all-optical network transmission systems [C]//Proceedings of the Global Telecommunications Conference (GLOBECOM'96), Vol 2, Nov 18-22,1996, London, UK. Piscataway, NJ, USA: IEEE, 1996: 933-937.
[3] PINART C. A multilayer fault localization framework for IP over all-optical multilayer networks [J]. IEEE Network, 2009,23(3):4-9.
[4] MAS C, TOMKOS I, TONGUZ O K. Failure location algorithm for transparent optical networks [J]. IEEE Journal on Selected Areas in Communications, 2005,23(8): 1508-1519.
[5] BOULOUTAS A T, CALO S, FINKEL A. Alarm correlation and fault identification in communication networks [J]. IEEE Transactions on Communications, 1994,42(2/3/4): 523-533.
[6] WEN Y, CHAN V W S, ZHENG L. Efficient fault-diagnosis algorithms for all-optical WDM networks with probabilistic link failures [J]. Journal of Lightwave Technology, 2005,23(10):3358-3371.
[7] ZENG H, HUANG C, VUKOVIC A. A novel fault detection and localization scheme for mesh all-optical networks based on monitoring cycles [J]. Photonic Network Communications, 2006, 11(3): 277-286.
[8] RFC 4204. Link management protocol (LMP) [S]. IETF, 2005.
[9] ZENG H, VUKOVIC A, HUANG C. A novel end-to-end fault detection and localization protocol for wavelength-routed WDM networks [C]//Proceedings of the Conference on Photonics North, Sep 12, 2005, Toronto, Canada. SPIE 5970. Bellingham, WA, USA: Society of Photo-Optical Instrumentation Engineers, 2005:719-726.
[10] SICHANI A V, MOUFTAH H T. Limited-perimeter vector matching fault-localization protocol for transparent all-optical communication networks [J]. IET Communications, 2007,1(3):472-478.
[11] ZADEH L A. Fuzzy sets [J]. Information and Control, 1965,8(3):338-353.
[12] DORIGO M, STUTZLE T. 蚁群优化 [J]. 张军,等译. 北京: 清华大学出版社, 2007.

收稿日期：2011-09-15

[摘要] 解决多故障定位的非多项式完全问题(NP-complete)在P比特级光网络中变的更加困难。计算复杂度、计算时间与网络的输入规模成指数增长关系。文章阐述已有的多故障定位算法以及协议，包括透明的故障定位算法、推理算法、深度探测算法、启发式生成树算法以及有限区域向量匹配协议(LVM)等，深入分析了P比特级光网络中多故障定位NP-complete问题的难点所在，同时提出一种基于蚁群优化进行告警的遍历和包含故障元素最少的故障集合的寻找方法。

[关键词] P比特光网络；多故障定位；蚁群优化

[Abstract] NP-complete in multiple fault localization in Pbit/s optical networks has become more difficult to solve. Computational complexity and computing time grow exponentially with the size of the network. This paper introduces fault localization mechanisms, including transparent fault location algorithm, inference algorithm, run-length probing algorithm, heuristic spanning tree with m-cycle, and limited-perimeter vector matching (LVM) fault-localization protocol. Difficulties in NP-complete of multiple fault localization in a Pbit/s optical network are analyzed, and an ant colony optimization algorithm is proposed to determine the minimum number of failures.

[Keywords] Pbit/s optical network; multiple fault localization; ant colony optimization