Research On Multi-level Preprocessing Method For Complex Fault Trees

Fault Tree Analysis(FTA)is an important and widely used method of reliability analysis.The currently widely used fault tree analysis methods is based on Boolean algebra and Binary Decision Diagrams(BDD).In order to improve the efficiency of fault tree analysis and overcome the difficulty of solving complex fault trees,it is necessary to study efficient fault tree preprocessing technology.In this thesis,we propose a multi-level preprocessing method for complex fault trees,which includes fault tree simplification,fault tree structural decomposition and fault tree functional decomposition.Fault tree simplification method prunes redundant nodes of fault tree to avoid unnecessary calculation in the fault tree analysis;then structural decomposition of fault tree can transform complete fault tree analysis into analysis of several subtrees,which can greatly reduce the complexity of fault tree analysis;finally,functional decompose the subtrees which can not be solved after structural decomposition.The major research interests of this thesis includes the following three parts:Firstly,in the dimension of fault tree structure,a new module expansion decomposition method based on linear time algorithm is proposed,which is an improvement of the existing structural decomposition algorithm.In this method,we first define the concept of equivalent event,which is used to identify the equivalent events of the fault tree.As a basis for dividing into modules,the number of modules decomposed by the linear time algorithm is increased.Later,considering the basis of time complexity and resource utilization,we propose a new set of simplification rule,so that the fault tree after eliminating redundant nodes can identify more modules and reduce the complexity of fault tree analysis.Secondly,in the logical relationship dimension of fault tree,we propose a new fault tree functional decomposition algorithm based on satisfiability problem(SAT),which breaks the limitation of traditional fault tree structural decomposition method,that is,the number of modules to be decomposed is limited by the structure of the fault tree.First,we first give the framework of the algorithm.Then,we introduce the details of the fault tree deep functional decomposition algorithm based on SAT from the aspects of fault tree coding,decomposition variable selection,sub-function reduction algorithm and sub-function merging.Finally,at the tool implementation level,based on the proposed multi-level preprocessing method of complex fault tree,we implement the tool for solving the fault tree Minimum Cut Set(MCS)that integrates the preprocessing method of this thesis—FDNUAAFTA.The tool contains three major modules:Preprocessing,Computing,and Merge.Finally,through an example,we demonstrate the whole calculation process,and verify the effectiveness of the multi-level preprocessing method of complex fault tree proposed in this thesis.