一种基于超立方体网络的高效故障诊断并行算法

doi:10.11896/j.issn.1002-137X.2019.05.011

计算机科学 ›› 2019, Vol. 46 ›› Issue (5): 73-76.doi: 10.11896/j.issn.1002-137X.2019.05.011

一种基于超立方体网络的高效故障诊断并行算法

郭杨^1,2, 梁家荣^1,2, 刘峰^1,2, 谢敏¹

(广西大学计算机与电子信息学院南宁530004)¹
(广西多媒体通信与网络技术重点实验室南宁530004)²

收稿日期:2018-03-29 修回日期:2018-06-04 发布日期:2019-05-15
作者简介:受国家自然科学基金项目(61363002),广西自然科学基金项目(2016GXNSFAA380134)资助。
郭杨(1992-),男,硕士生,主要研究方向为网络与并行计算、系统级故障诊断;梁家荣(1966-),博士,教授,CCF会员,主要研究方向为网络与并行计算,E-mail:gxuliangjr@163.com(通信作者);刘峰(1991-),男,硕士生,主要研究方向为网络与并行计算、系统级故障诊断;谢敏(1974-),女,博士生,副教授,主要研究方向为网络与并行计算、网络控制。
基金资助:
国家自然科学基金项目(61363002),广西自然科学基金项目(2016GXNSFAA380134)资助。

Novel Fault Diagnosis Parallel Algorithm for Hypercube Networks

GUO Yang^1,2, LIANG Jia-rong^1,2, LIU Feng^1,2, XIE Min¹

(School of Computer and Electronics Information,Nanning 530004,China)¹
(Guangxi Key Laboratory of Multimedia Communications and Network Technology,Nanning 530004,China)²

Received:2018-03-29 Revised:2018-06-04 Published:2019-05-15

摘要/Abstract

摘要： 超立方网络是一种重要的网络拓扑结构。针对现有的超立方网络故障诊断算法复杂度高的问题,引入故障扇的概念,采用并行深度优先搜索策略设计算法,通过算法寻找超立方体网络中的故障扇,确定该网络的故障节点,以便替换或修复,为增强网络的可靠性提供了一条重要的新途径。最后对所提算法的复杂性进行了分析,证明了该算法的时间复杂度不超过O(N),远优于现有复杂度超过平方级的算法。

关键词: 超立方网络, 故障扇, 故障诊断, 系统级诊断

Abstract: Hypercube is one of valuable interconnection networks.Aiming at the problem of high complexity of existing fault diagnosis algorithm in hypercube network,this paper proposed a concept of fault fan.The parallel depth-first search strategy algorithm is used to find the fault fan in hypercube networks,and the fault node of network is determined in order to replace or repair it,which provides a significant way for enhancing the reliability of network.In the end,the complexity of the proposed algorithm was analyzed.It is proved that the time complexity of the algorithm does not exceed O(N),which is far better than the algorithm with more than square complexity.

Key words: Fault diagnosis, Fault fans, Hypercube network, System level diagnosis

中图分类号:

TP373

郭杨, 梁家荣, 刘峰, 谢敏. 一种基于超立方体网络的高效故障诊断并行算法[J]. 计算机科学, 2019, 46(5): 73-76. https://doi.org/10.11896/j.issn.1002-137X.2019.05.011

GUO Yang, LIANG Jia-rong, LIU Feng, XIE Min. Novel Fault Diagnosis Parallel Algorithm for Hypercube Networks[J]. Computer Science, 2019, 46(5): 73-76. https://doi.org/10.11896/j.issn.1002-137X.2019.05.011

参考文献

[1]ZHOU S,LIN L,XU L,et al.The t/k-Diagnosability of Star Graph Networks[J].IEEE Transactions on Computers,2015,64(2):547-555.
[2]LIANG J R,ZHANG Q,LI H.Structural Properties and t/s-Diagnosis for Star Networks based on the PMC Model[J].IEEE Access,2017,5(11):26175-26183.
[3]CHENG E,LIPTÁK L.Linearly many faults in Cayley graphs generated by transposition trees[J].Information Sciences,2007,177(22):4877-4882.
[4]GUO L,HOU W,GUO P.Designs of 3D mesh and torus optical Network-on-Chips:Topology,optical router and routing module[J].China Communications,2017,14(5):17-29.
[5]LIN L,ZHOU S,XU L,et al.The Extra Connectivity and Con-ditional Diagnosability of Alternating Group Networks[J].IEEE Transactions on Parallel & Distributed Systems,2015,26(8):2352-2362.
[6]YE L C,LIANG J R,LIN H X.A fast pessimisticDiagnosis Algorithm for Hypercube-Like Networks under the Comparison Model[J].IEEE Transactions on Computers,2016,65(9):2884-2888.
[7]YE T L,HSIEH S Y.A Scalable Comparison-Based Diagnosis Algorithm for Hypercube-Like Networks[J].IEEE Transactions on Reliability,2013,62(4):789-799.
[8]LEE S C,HOOK L R.Logic and Computer Design in Nanospace[J].IEEE Transactions on Computers,2008,57(7):965-977.
[9]ROOSE D,BOMANS L,HEMPEL R.The Argonne/GMD macros in FORTRAN for portable parallel programming and their implementation on the Intel iPSC/2[J].Parallel Computing,1990,15(1):119-132.
[10]ZHU Q.On conditional diagnosability and reliability of the BC networks[J].Journal of Supercomputing,2008,45(2):173-184.
[11]YE L C,LIANG J R.Five-Round Adaptive Diagnosis in Hamiltonian Networks[J].IEEE Transactions on Parallel & Distributed Systems,2015,26(9):2459-2464.
[12]TSAI C H,CHEN J C.Fault isolation and identification in ge-neral biswapped networks under the PMC diagnostic model [J].Theoretical Computer Science,2013,501(3):62-71.
[13]CHANG G Y,CHANG G J,CHEN G H.Diagnosabilities of Regular Networks[J].IEEE Transactions on Parallel & Distributed Systems,2005,16(4):314-323.
[14]LAI P L,TAN J J M,CHANG C P,et al.Conditional Diagno-sability Measures for Large Multiprocessor Systems[J].IEEE Transactions on Computers,2005,54(2):165-175.
[15]CHESSA S,ERRICO W,MAESTRINI P,et al.Self-diagnostic tools of the APEmille parallel machine[J].IEE Proceedings-Computers and Digital Techniques,2002,149(6):273-279.
[16]PREPARATA F P,METZE G,CHIEN R T.On the Connection Assignment Problem of Diagnosable Systems[J].IEEE Transactions on Electronic Computers,1967,16(6):848-854.
[17]LIANG J,ZHANG Q.The t/s-diagnosability of HypercubeNetworks under the PMC and Comparison Models[J].IEEE Access,2017,5(1):5340-5346.
[18]CHANG N W,HSIEH S Y.Conditional Diagnosability of (n,k)-Star Graphs under the PMC Model[J].IEEE Transactions on Dependable & Secure Computing,2016,15(2):207-216.
[19]CHANG N W,HSIEH S Y.Structural Properties and Condi-tional Diagnosability of Star Graphs by Using the PMC Model[J].IEEE Transactions on Parallel & Distributed Systems,2014,25(11):3002-3011.
[20]YUAN J,LIU A,MA X,et al.The g-Good-Neighbor Conditio-nal Diagnosability of,-Ary,-Cubes under the PMC Modeland MM^* Model[J].IEEE Transactions on Parallel & Distributed Systems,2014,26(4):1165-1177.
[21]SULLIVAN G F.An O(t³＋｜E｜) fault identification algorithm for diagnosable systems[J].IEEE Transactions on Computers,1988,37(4):388-397.
[22]DAHBURA A T,MASSON G M.An O(n^2.5) Fault Identification Algorithm for Diagnosable Systems[J].IEEE Transactions on Computers,1984,33(6):486-492.
[23]MEYER G G L.A fault diagnosis algorithm for asymmetricmodular architectures[J].IEEE Transactions on Computers,1981,30(1):81-83.
[24]HAKIMI S L,AMIN A T.Characterization of Connection Assignment of Diagnosable Systems[J].IEEE Transactions on Computers,1974,23(1):86-88.
[25]徐俊明.组合网络理论[M].北京:科学出版社,2007:96.
[26]AHARONI R.Menger’s Theorem for Graphs Containing no Infinite Paths[J].European Journal of Combinatorics,1983,4(3):201-204.

相关文章 15

[1]	雷剑梅, 曾令秋, 牟洁, 陈立东, 王淙, 柴勇. 基于整车EMC标准测试和机器学习的反向诊断方法 Reverse Diagnostic Method Based on Vehicle EMC Standard Test and Machine Learning 计算机科学, 2021, 48(6): 190-195. https://doi.org/10.11896/jsjkx.200700204
[2]	王焘, 张树东, 李安, 邵亚茹, 张文博. 一种面向异常传播的微服务故障诊断方法 Anomaly Propagation Based Fault Diagnosis for Microservices 计算机科学, 2021, 48(12): 8-16. https://doi.org/10.11896/jsjkx.210100149
[3]	朱晓玲, 李琨, 张长胜, 杜付鑫. 基于Gabor小波变换和多核支持向量机的电梯导靴故障诊断方法 Elevator Boot Fault Diagnosis Method Based on Gabor Wavelet Transform and Multi-coreSupport Vector Machine 计算机科学, 2020, 47(12): 258-261. https://doi.org/10.11896/jsjkx.200700039
[4]	林毅, 吉鸿江, 韩佳佳, 张德平. 一种基于马氏距离的系统故障诊断方法 System Fault Diagnosis Method Based on Mahalanobis Distance Metric 计算机科学, 2020, 47(11A): 57-63. https://doi.org/10.11896/jsjkx.190900174
[5]	王岩, 罗倩, 邓辉. 基于变分贝叶斯的轴承故障诊断方法 Bearing Fault Diagnosis Method Based on Variational Bayes 计算机科学, 2019, 46(11): 323-327. https://doi.org/10.11896/jsjkx.180901719
[6]	张刚, 高俊鹏, 李红威. 级联三稳态随机共振的特性研究及应用 Research on Stochastic Resonance Characteristics of Cascaded Three-steady-state and Its Application 计算机科学, 2018, 45(9): 146-151. https://doi.org/10.11896／j.issn.1002-137X.2018.09.023
[7]	张斌,滕俊杰,满毅. 改进的并行fp-growth算法在工业设备故障诊断中的应用研究 Application Research of Improved Parallel Fp-growth Algorithm in Fault Diagnosis of Industrial Equipment 计算机科学, 2018, 45(6A): 508-512.
[8]	薛善良,杨佩茹,周奚. 基于模糊神经网络的WSN无线数据收发单元故障诊断 WSN Wireless Data Transceiver Unit Fault Diagnosis with Fuzzy Neural Network 计算机科学, 2018, 45(5): 38-43. https://doi.org/10.11896/j.issn.1002-137X.2018.05.006
[9]	张妮,车立志,吴小进. 基于数据驱动的故障诊断技术研究现状及展望 Present Situation and Prospect of Data-driven Based Fault Diagnosis Technique 计算机科学, 2017, 44(Z6): 37-42. https://doi.org/10.11896/j.issn.1002-137X.2017.6A.008
[10]	陈秒江,梁家荣,张乾. 基于比较诊断模型的超立方网络诊断算法 Hypercube Network Diagnosis Algorithm under Comparison Model 计算机科学, 2017, 44(6): 83-90. https://doi.org/10.11896/j.issn.1002-137X.2017.06.014
[11]	葛诗春,刘雄飞,周锋. CRH2型动车组列车信息传输网络流量建模与预测 Modeling and Prediction on Train Communication Network Traffic of CRH2 EMUs 计算机科学, 2017, 44(10): 91-95. https://doi.org/10.11896/j.issn.1002-137X.2017.10.017
[12]	周奚,薛善良. 基于改进的粗糙集和神经网络的WSN故障诊断 WSN Fault Diagnosis with Improved Rough Set and Neural Network 计算机科学, 2016, 43(Z11): 21-25. https://doi.org/10.11896/j.issn.1002-137X.2016.11A.005
[13]	陈云风,王红军,杨燕. 基于聚类集成的高铁故障诊断分析 Fault Diagnosis of High-speed Rail Based on Clustering Ensemble 计算机科学, 2015, 42(6): 233-238. https://doi.org/10.11896/j.issn.1002-137X.2015.06.049
[14]	王雪洁,黄海燕. 基于免疫优势克隆文化算法的故障诊断方法及其在TE过程中的应用 Fault Diagnosis Method Based on Immunodominance Clone Cultural Algorithm and its Application in TE Process 计算机科学, 2015, 42(5): 255-259. https://doi.org/10.11896/j.issn.1002-137X.2015.05.051
[15]	贾志淳,邢星. 基于贝叶斯与多故障推理的Web服务诊断 Diagnosis of Web Service Based on Bayes and Multi-faults Reasoning 计算机科学, 2014, 41(6): 225-230. https://doi.org/10.11896/j.issn.1002-137X.2014.06.044

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

一种基于超立方体网络的高效故障诊断并行算法

Novel Fault Diagnosis Parallel Algorithm for Hypercube Networks

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0