摘要
文中研究了全光网中定位故障链路的探测选择算法.目前存在的随机游走算法可以惟一定位出每条故障链路,但在大型网络中定位故障链路时会消耗过多的探测以及平均波长数.首先建立关于故障检测需要的监测路径集合,其次在建立好的监测路径上同时发送探测信号,最后在有故障的路径上执行故障定位;证明了最小监测路径集合问题是非确定多项式完全问题,并提出启发式的监测路径选择算法来找最小监测路径集合;同时证明了用一个监测站来定位k条故障链路的充分必要条件是,网络为k+1边连通的.对比随机游走算法,探测选择算法在定位故障链路的过程中明显地减少了定位故障链路所需的探测数和每条链路上消耗的平均波长数.
This paper studies the probe selection problem in all-optical networks for achieving unambiguous faulty links localization.The existing random walk algorithm can find feasible solutions for localizing the faulty link unambiguously,but it consumes a large number of probes and wavelengths in large-size networks.First,monitoring paths arc set up for failure detection.Second,the probing signals arc sent out through all monitoring paths,and then the failure localization is performed on every faulty path.The proposed scheme proves that the problem of the minimal monitoring path set is NP-complctc and can be solved by the heuristic monitoring path selection algorithm.It is also proved that a network must be k+1 edge connectivity for localizing k faulty links with one monitoring node.Compared with random walk,the probe selection algorithm greatly shortens the number of probes and consumed wavelengths per link.
作者
齐小刚
王晓琳
刘立芳
QI Xiaogang;WANG Xiaolin;LIU Lifang(School of Mathematics and Statistics,Xidian Univ.,Xi'an 710071,China;School of Computer Science and Technology,Xidian Univ.,Xi'an 710071,Chi)
出处
《西安电子科技大学学报》
EI
CAS
CSCD
北大核心
2018年第2期71-76,115,共7页
Journal of Xidian University
基金
国家自然科学基金资助项目(61572435
61472305)
陕西省自然科学基金资助项目(2015JZ002
2015JM6311)
浙江省自然科学基金资助项目(LZ16F020001)
宁波市自然科学基金资助项目(2016A610035)
空间测控通信创新探索基金资助项目(KJCK1608)
关键词
故障检测
故障定位
监测路径
探测
故障链路
failure detection
failure localization
monitoring path
probe
faulty links