Computer Science

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

PDF (PC)

569

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: Equivalent events, Fault decomposition, Module expansion, Simplification

CLC Number: 

  • TP311
[1]VESELY W E.Fault tree Handbook[J／OL].U.s.nuclear Regulatory Commission Washington,http://xueshu.baidu.com/s?wd=paperuri%3A%2814eb29c24997cefbf1482a3df590f622%29&filter=sc_long_sign&sc_ks_para=q%3DFault%20Tree%20Handbook&sc_us=&tn=SE_baiduxueshu_c1gjeupa&ie=utf-8.<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].https://core.ac.uk/display/13791161.<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].http://web.arch-ive.org/web/20061204235930/http://iml.univ_mrs.fr/~arauzy.arilia/benchmark.html<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] REN Shuai, WANG Meng, FAN Ao-xiong, GAO Ze, XU Jie, Shahzad KHURRAM, ZHANG Tao. Zero-high-resolution Information Hiding Algorithm for 3D Mesh Model [J]. Computer Science, 2020, 47(7): 328-334.
[2] 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.
[3] QI Jian-jun and WEI Ling. Simplification of Triadic Contexts and Concept Trilattices [J]. Computer Science, 2017, 44(9): 53-57.
[4] 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.
[5] TIAN Bing-chuan, SUN Ke and CHAO Han-qing. New Algorithm of Simplifying GCC Syntax Tree [J]. Computer Science, 2015, 42(Z6): 516-518.
[6] ZHAO Ye,ZHOU Chang,WANG Chang. Feature Preserved Mesh Simplification Algorithm Based on Stochastic Sampling [J]. Computer Science, 2011, 38(5): 249-251.
[7] 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.
[8] 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.
[9] . [J]. Computer Science, 2007, 34(11): 26-28.
[10] . [J]. Computer Science, 2006, 33(3): 271-274.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.