Computer Science ›› 2019, Vol. 46 ›› Issue (1): 226-231.doi: 10.11896/j.issn.1002-137X.2019.01.035

• Software & Database Technology • Previous Articles     Next Articles

Fault Tree Module Expansion Decomposition Method Based on Liner-time Algorithm

SONG Jun-hua, WEI Ou   

  1. (College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China)
  • Received:2017-12-04 Online:2019-01-15 Published:2019-02-25

Abstract: Fault tree is widely used to analyze the security in many safety-critical fields including nuclear industry,aerospace engineering and traffic control.However,large amount of computation resources are consumed when large-scaled fault tree is analyzed in major industries such as nuclear power station,leading to low efficiency and excessive time consumption.In order to solve this problem,this paper made several extensions based on existing linear-time algorithm,and proposed a new fault tree reduction rules and modular derivation based decomposition algorithm.Firstly,the concept of equivalent event is presented to extend the number of modules decomposed by linear-time algorithm.Based on the consideration of time complexity and resource utilization,new reduction rules are proposed to get rid of the redundant information in fault tree.Experimental results show that the proposed decomposition method can optimize the fault tree ana-lysis effectively,and reduce the time consumption and memory usage when dealing with the large-scaled fault tree.

Key words: Fault decomposition, Module expansion, Equivalent events, Simplification

CLC Number: 

  • TP311
[1]VESELY W E.Fault tree Handbook[J/OL].U.s.nuclear Regulatory Commission Washington,<br /> [2]ZHONGXIN X,WEI C.System Safety Design and Assessment in Civil Aircraft[M].Shanghai:Shanghai Jiao Tong University,2013.<br /> [3]BENGIAMIN N N,BOWEN B A,SCHENK K F.An Efficient Algorithm for Reducing the Complexity of Computation in Fault Tree Analysis[J].IEEE Transactions on Nuclear Science,1976,23(5):1442-1446.<br /> [4]PLATZ O,OLSEN J V.FAUNET:A Program Package for Evaluation of Fault Trees and Networks[J/OL].<br /> [5]SUN H,ANDREWS J D.Identification of independent modules in fault trees which contain dependent basic events[J].Reliability Engineering & System Safety,2004,86(3):285-296.<br /> [6]CAMARINOPOULOS L,YLLERA J.An Improved Top-down Algorithm Combined with Modularisation as a Highly Efficient Method for Fault Tree Analysis[J].Reliability Engineering,1985,11(2):93-108.<br /> [7]KOHDA T,HENLEY E J,INOUE K.Finding modules in fault trees[J].IEEE Transactions on Reliability,1989,38(2):165-176.<br /> [8]ROSENTHAL A.Decomposition methods for fault tree analysis [J].IEEE Transactions on Reliability,1980,29(2):136-138.<br /> [9]YLLERA J.Modularization methods for evaluating fault tree of complex technical system[J].Engineering Risk and Hazard Assessment,1988,2:81-100.<br /> [10]WILSON J M.Modularizing and Minimizing Fault Trees[J].IEEE Transactions on Reliability,1985,34(4):320-322.<br /> [11]DUTUIT Y,RAUZY A.A linear-time algorithm to find modules of fault trees[J].IEEE Transactions on Reliability,1996,45(3):422-425.<br /> [12]RAITERI D C,IACONO M,FRANCESCHINIS G,et al.Repairable Fault Tree for the Automatic Evaluation of Repair Policies//International Conference on Dependable Systems and Networks.IEEE Computer Society,2004:659.<br /> [13]TARJAN E.Depth first search and linear graph algorithms[J].Siam Journal on Computing,1972,1(4):114-121.<br /> [14]DENG Y,WANG H,GUO B.BDD algorithms based on modularization for fault tree analysis[J].Progress in Nuclear Energy,2015,85:192-199.<br /> [15]A repository of fault tree benchmark[OL].<br /> [16]WEILIN L,OU W,MINGYU H.Computing minimal cut sets of fault tree using SAT solver[J].Computer Engineering and Scien-ce,2017,39(4):725-733.<br /> [17]LUO W,WEI O.WAP:SAT-Based Computation of Minimal Cut Sets[C].IEEE International Symposium on Software Reliability Engineering.IEEE Computer Society,2017:146-151.<br /> [18]CONTINI S,MATUZAS V.Analysis of large fault trees based on functional decomposition[J].Reliability Engineering & System Safety,2011,96(3):383-390.<br /> [19]MATUZAS V,CONTINI S.On the efficiency of functional decomposition in fault tree analysis[J].Proceedings of the Institution of Mechanical Engineers Part O Journal of Risk & Reliabi-lity,2012,226(6):635-645.<br /> [20]CONTINI S,MATUZAS V.Coupling decomposition and truncation for the analysis of complex fault trees[J].Proceedings of the Institution of Mechanical Engineers Part O Journal of Risk &Reliability,2012,226(3):249-261.
[1] ZHENG Hong, DENG Wen-xuan, DENG Xiao, LU Xing-jian. Simplification and Verification of Matrix-based Workflow Logic Net Model [J]. Computer Science, 2018, 45(7): 307-314.
[2] QI Jian-jun and WEI Ling. Simplification of Triadic Contexts and Concept Trilattices [J]. Computer Science, 2017, 44(9): 53-57.
[3] DONG Tian-yang, YAO Jia-jie and JI Lei. Research on Three-dimensional Tree Model Simplification for Web Applications [J]. Computer Science, 2016, 43(Z6): 142-148, 167.
[4] TIAN Bing-chuan, SUN Ke and CHAO Han-qing. New Algorithm of Simplifying GCC Syntax Tree [J]. Computer Science, 2015, 42(Z6): 516-518, 530.
[5] ZHAO Ye,ZHOU Chang,WANG Chang. Feature Preserved Mesh Simplification Algorithm Based on Stochastic Sampling [J]. Computer Science, 2011, 38(5): 249-251.
[6] ZHAO Juan-juan, CHEN Jun-jie, LI Guo-qing. Algorithm of Simplifying the Image Emotion Semantic Rules [J]. Computer Science, 2009, 36(10): 240-243.
[7] FU Xin CHEN Rui TANG Yan (Southwest University, Faculty of Computer and Information Science, Chongqing 400715, China). [J]. Computer Science, 2008, 35(7): 216-218.
[8] . [J]. Computer Science, 2007, 34(11): 26-28.
[9] . [J]. Computer Science, 2006, 33(3): 271-274.
Full text



[1] . [J]. Computer Science, 2018, 1(1): 1 .
[2] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[3] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[4] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[5] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[6] 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 .
[7] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[8] 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 .
[9] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[10] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .