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

NP-Complete Problem in Multiple Fault Localization in Pbit/s Optical Networks

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

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.