计算机科学 ›› 2019, Vol. 46 ›› Issue (5): 73-76.doi: 10.11896/j.issn.1002-137X.2019.05.011
郭杨1,2, 梁家荣1,2, 刘峰1,2, 谢敏1
GUO Yang1,2, LIANG Jia-rong1,2, LIU Feng1,2, XIE Min1
摘要: 超立方网络是一种重要的网络拓扑结构。针对现有的超立方网络故障诊断算法复杂度高的问题,引入故障扇的概念,采用并行深度优先搜索策略设计算法,通过算法寻找超立方体网络中的故障扇,确定该网络的故障节点,以便替换或修复,为增强网络的可靠性提供了一条重要的新途径。最后对所提算法的复杂性进行了分析,证明了该算法的时间复杂度不超过O(N),远优于现有复杂度超过平方级的算法。
中图分类号:
[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 3+|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(n2.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. |
[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 |
|