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

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

作　　者：李新[1] 顾畹仪[1] 

机构地区：[1]北京邮电大学信息光子学与光通信国家重点实验室,北京100876

出　　处：《中兴通讯技术》2011年第6期28-31,共4页ZTE Technology Journal

基　　金：国家重点基础研究发展("973")规划(2010CB328202;2010CB328204);国家自然科学基金(60702005)

摘　　要：解决多故障定位的非多项式完全问题(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.

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

分 类 号：TN929.1[电子电信—通信与信息系统]