全光网中定位故障链路的探测选择算法

doi:10.3969/j.issn.1001-2400.2018.02.013

西安电子科技大学学报

全光网中定位故障链路的探测选择算法

齐小刚1;王晓琳1;刘立芳2

(1. 西安电子科技大学数学与统计学院，陕西西安 710071;
2. 西安电子科技大学计算机学院，陕西西安 710071)

收稿日期:2017-04-27 出版日期:2018-04-20 发布日期:2018-06-06
作者简介:齐小刚(1973-), 男, 教授, E-mail: xgqi@xidian.edu.cn
基金资助:
国家自然科学基金资助项目(61572435,61472305)；陕西省自然科学基金资助项目(2015JZ002, 2015JM6311)；浙江省自然科学基金资助项目(LZ16F020001)；宁波市自然科学基金资助项目(2016A610035)；空间测控通信创新探索基金资助项目(KJCK1608)

Probe selection algorithm for faulty links localization in all-optical networks

QI Xiaogang1;WANG Xiaolin1;LIU Lifang2

(1. School of Mathematics and Statistics, Xidian Univ., Xi'an 710071, China;
2. School of Computer Science and Technology, Xidian Univ., Xi'an 710071, China)

Received:2017-04-27 Online:2018-04-20 Published:2018-06-06

摘要/Abstract

摘要：

文中研究了全光网中定位故障链路的探测选择算法．目前存在的随机游走算法可以惟一定位出每条故障链路，但在大型网络中定位故障链路时会消耗过多的探测以及平均波长数．首先建立关于故障检测需要的监测路径集合，其次在建立好的监测路径上同时发送探测信号，最后在有故障的路径上执行故障定位；证明了最小监测路径集合问题是非确定多项式完全问题，并提出启发式的监测路径选择算法来找最小监测路径集合; 同时证明了用一个监测站来定位k条故障链路的充分必要条件是，网络为k+1边连通的．对比随机游走算法，探测选择算法在定位故障链路的过程中明显地减少了定位故障链路所需的探测数和每条链路上消耗的平均波长数．

关键词: 故障检测, 故障定位, 监测路径, 探测, 故障链路

Abstract:

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 are set up for failure detection. Second, the probing signals are 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-complete 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.

Key words: failure detection, failure localization, monitoring path, probe, faulty links

齐小刚;王晓琳;刘立芳. 全光网中定位故障链路的探测选择算法[J]. 西安电子科技大学学报, 2018, 45(2): 71-76+115.

QI Xiaogang;WANG Xiaolin;LIU Lifang. Probe selection algorithm for faulty links localization in all-optical networks[J]. Journal of Xidian University, 2018, 45(2): 71-76+115.

参考文献

［1］熊余, 董先存, 李圆圆, 等. 软件定义光网络中基于最小点覆盖的控制平面跨层生存性设计［J］. 电子与信息学报, 2016, 38(5): 1211-1218.
XIONG Yu, DONG Xiancun, LI Yuanyuan, et al. The Cross-layer Survivable Design of Control Plane Based on Minimum Point Covering in Software Defined Optical Network［J］. Journal of Electronics & Information Technology, 2016, 38(5): 1211-1218.
［2］ HARVEY N J A, PATRASCU M, WEN Y G, et al. Non-adaptive Fault Diagnosis for All-optical Networks via Combinatorial Group Testing on Graphs［C］//Proceedings of the 2007 26th IEEE International Conference on Computer Communications. Piscataway: IEEE, 2007: 697-705.
［3］ ALI M L, HO P H, TAPOLCAI J. SRLG Failure Localization Using Nested M-trails and Their Application to Adaptive Probing［J］. Networks, 2015, 66(4): 347-363.
［4］ XUAN Y, SHEN Y, NGUYEN N P, et al. Efficient Multi-link Failure Localization Schemes in All-optical Networks［J］. IEEE Transactions on Communications, 2013, 61(3): 1144-1151.
［5］ ALI M L, HO P H, TAPOLCAI J. A Novel M-trail Allocation Method for SRLG Fault Localization in All-optical Networks［J］. Optical Switching and Networking, 2017, 23(2): 179-188.
［6］ TAPOLCAI J, RONYAI L, HOSSZU E, et al. Signaling Free Localization of Node Failures in All-optical Networks［C］//Proceedings of the 2014 IEEE Conference on Computer Communications. Piscataway: IEEE, 2014: 1860-1868.
［7］刘英挺, 朱睿杰, 杜晓明, 等. 全光网中采用可信度模型的故障定位技术［J］. 西安电子科技大学学报, 2016, 43(6): 152-157.
LIU Yingting, ZHU Ruijie, DU Xiaoming, et al. Mechanism for Fault Location Based on the Credibility Model of All Optical Networks［J］. Journal of Xidian University, 2016, 43(6): 152-157.
［8］ NATU M, SETHI A S, LLOYD E L. Efficient Probe Selection Algorithms for Fault Diagnosis［J］. Telecommunication Systems, 2008, 37(1/3): 109-125.
［9］张新, 常义林, 孙方涛, 等. 一种改进的网络故障监测算法［J］. 西安电子科技大学学报, 2006, 33(3): 416-421.
ZHANG Xin, CHANG Yilin, SUN Fangtao, et al. An Improved Algorithm for Monitoring the Network Fault［J］. Journal of Xidian University, 2006, 33(3): 416-421.
［10］ ALBERT R, BARABASI A L. Statistical Mechanics of Complex Networks［J］. Quantitative Biology, 2001, 74(1): 47-97.
［11］ THAI M T. Group Testing Theory in Network Security: Advanced Solution［M］. New York: Springer, 2012: 3-4.
［12］ ALI M L, HO P H, TAPOLCAI J. SRLG Fault Localization Using Nested M-trails［J］. Computer Networks, 2015, 85: 63-79.
［13］ WANG B, HO P H. Energy-efficient Routing and Bandwidth Allocation in OFDM-based Optical Networks［J］. Journal of Optical Communications and Networking, 2016, 8(2): 71-84.

[1]	陈晓冬;杨翠;向培;刘鹏;邵晓鹏;张小雷;吕洐秋. 光伏型InSb红外探测器瞬态特性界面陷阱效应[J]. 西安电子科技大学学报, 2017, 44(3): 61-65+88.
[2]	刘英挺;朱睿杰;杜晓明;赵永利. 全光网中采用可信度模型的故障定位技术[J]. 西安电子科技大学学报, 2016, 43(6): 152-157.
[3]	党文佳;曾晓东;来志;冯喆珺;曹长庆;霍燿炜. 粗糙目标光外差信号特性对探测阈值的影响[J]. 西安电子科技大学学报, 2016, 43(4): 57-62.
[4]	林涛;刘飞;王怡;张建奇. 红外隐身飞机光谱探测的谱带性能分析方法[J]. J4, 2016, 43(1): 54-59+81.
[5]	董守玲;苏孟辉;林香鑫;李佳 . IPv6校园网拓扑自动节点获取与发现算法 [J]. J4, 2015, 42(2): 116-121.
[6]	付永庆;刘伟 . 主动探测型时间反转电磁波聚焦 [J]. J4, 2015, 42(2): 122-126+198.
[7]	王尔申;张淑芳;蔡明;庞涛. 遗传粒子滤波的GPS接收机自主完好性监测[J]. J4, 2015, 42(1): 136-141.
[8]	赵宝玮;相里斌;吕群波;张桂峰;曾晓茹;郭文记. FPGA和多DSP系统的并行RX探测算法[J]. J4, 2014, 41(3): 152-156.
[9]	张英远;刘飞;韩平丽. 激光告警中来袭激光方向的确定方法[J]. J4, 2014, 41(2): 114-119.
[10]	吴鑫;张建奇;刘德连;黄曦;何国经. CUDA架构下高效红外图像背景预测方法[J]. J4, 2011, 38(6): 44-51.
[11]	胡国平1,2;张守宏2. 多传感器协同探测目标的分类识别研究[J]. J4, 2009, 36(3): 443-447.
[12]	郭建1;金乃咏2. 模型检验中对CTL公式的空属性探测 [J]. J4, 2007, 34(5): 794-799.
[13]	赵铭军(1;2);程惠珍(2);胡永钊(2);曾晓东(1). 扫描成像系统的回波信号检测方法[J]. J4, 2006, 33(1): 66-70.
[14]	史林;姜敏;黄莉. 基于谐波模型的生命探测雷达人体状态识别方法[J]. J4, 2005, 32(2): 179-183.
[15]	王志胜;王道波;蔡宗琰. 用于缓变故障检测的残差检验法[J]. J4, 2004, 31(3): 479-482.

全光网中定位故障链路的探测选择算法

Probe selection algorithm for faulty links localization in all-optical networks

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10