Computer Science ›› 2019, Vol. 46 ›› Issue (5): 73-76.doi: 10.11896/j.issn.1002-137X.2019.05.011

Previous Articles     Next Articles

Novel Fault Diagnosis Parallel Algorithm for Hypercube Networks

GUO Yang1,2, LIANG Jia-rong1,2, LIU Feng1,2, XIE Min1   

  1. (School of Computer and Electronics Information,Nanning 530004,China)1
    (Guangxi Key Laboratory of Multimedia Communications and Network Technology,Nanning 530004,China)2
  • Received:2018-03-29 Revised:2018-06-04 Published:2019-05-15

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: Hypercube network, Fault diagnosis, Fault fans, System level diagnosis

CLC Number: 

  • TP373
[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.
[26]AHARONI R.Menger’s Theorem for Graphs Containing no Infinite Paths[J].European Journal of Combinatorics,1983,4(3):201-204.
[1] ZHU Xiao-ling, LI Kun, ZHANG Chang-sheng, DU Fu-xin. Elevator Boot Fault Diagnosis Method Based on Gabor Wavelet Transform and Multi-coreSupport Vector Machine [J]. Computer Science, 2020, 47(12): 258-261.
[2] LIN Yi, JI Hong-jiang, HAN Jia-jia, ZHANG De-ping. System Fault Diagnosis Method Based on Mahalanobis Distance Metric [J]. Computer Science, 2020, 47(11A): 57-63.
[3] WANG Yan, LUO Qian, DENG Hui. Bearing Fault Diagnosis Method Based on Variational Bayes [J]. Computer Science, 2019, 46(11): 323-327.
[4] ZHANG Gang, GAO Jun-peng, LI Hong-wei. Research on Stochastic Resonance Characteristics of Cascaded Three-steady-state and Its Application [J]. Computer Science, 2018, 45(9): 146-151.
[5] ZHANG Bin,TENG Jun-jie,MAN Yi. Application Research of Improved Parallel Fp-growth Algorithm in Fault Diagnosis
of Industrial Equipment
[J]. Computer Science, 2018, 45(6A): 508-512.
[6] XUE Shan-liang, YANG Pei-ru and ZHOU Xi. WSN Wireless Data Transceiver Unit Fault Diagnosis with Fuzzy Neural Network [J]. Computer Science, 2018, 45(5): 38-43.
[7] ZHANG Ni, CHE Li-zhi and WU Xiao-jin. Present Situation and Prospect of Data-driven Based Fault Diagnosis Technique [J]. Computer Science, 2017, 44(Z6): 37-42.
[8] CHEN Miao-jiang, LIANG Jia-rong and ZHANG Qian. Hypercube Network Diagnosis Algorithm under Comparison Model [J]. Computer Science, 2017, 44(6): 83-90.
[9] ZHOU Xi and XUE Shan-liang. WSN Fault Diagnosis with Improved Rough Set and Neural Network [J]. Computer Science, 2016, 43(Z11): 21-25.
[10] CHEN Yun-feng, WANG Hong-jun and YANG Yan. Fault Diagnosis of High-speed Rail Based on Clustering Ensemble [J]. Computer Science, 2015, 42(6): 233-238.
[11] WANG Xue-jie and HUANG Hai-yan. Fault Diagnosis Method Based on Immunodominance Clone Cultural Algorithm and its Application in TE Process [J]. Computer Science, 2015, 42(5): 255-259.
[12] JIA Zhi-chun and XING Xing. Diagnosis of Web Service Based on Bayes and Multi-faults Reasoning [J]. Computer Science, 2014, 41(6): 225-230.
[13] FANG Huan,FANG Xian-wen and LI De-quan. Review on Fault Diagnosis Theory and Application Based on Petri Nets [J]. Computer Science, 2014, 41(3): 17-22.
[14] SHANG Xing-hong,SHANG Xi-yue,ZHANG Jing and QIAN Huan-yan. Research on Fault Diagnosis of Wireless Sensor Nodes [J]. Computer Science, 2013, 40(Z6): 327-329.
[15] MI Xiao-ping and LI Xue-mei. Study on Fault Diagnosis of Gear Pump Based on Normal Cloud Neutral Network [J]. Computer Science, 2013, 40(8): 266-267.
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[2] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[3] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[4] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[5] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[6] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[7] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[8] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[9] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .
[10] WANG Zhen-chao, HOU Huan-huan and LIAN Rui. Path Optimization Scheme for Restraining Degree of Disorder in CMT[J]. Computer Science, 2018, 45(4): 122 -125 .