On Variable Ordering Heuristics Of Bdd-Based Fault Tree Analysis

Fault Tree Analysis (FTA) is one of the most commonly used methods for reliability engineering, which provides both qualitative and quantitative analysis of system reliability. The binary decision diagram (BDD) is already proved to be of considerable use in reliability analysis and provides a more efficient means to analyze a fault tree model. There is a problem, however, the size of BDD, and therefore the efficiency of the whole methodology, depends dramatically on the choice of variable ordering. The ordering that leads a smallest size of BDD is the optimal variable ordering. Previous studies have showed that finding optimal variable ordering is an NP-Complete problem.Heuristics are often used to get good orderings. Current research focuses on how to design a high-performance heuristic to get an approximate optimal variable ordering. Detailed and in-depth studies are carried out on this issue, specifically, includes the following aspects:1) Fault tree benchmark is the base for the study on analysis performance of different variable ordering heuristics. The fault tree samples must have different structure characteristics, thus either the manual generation methods or the computer-aided generation methods is useful. Proposes a random top-down algorithm to generation fault trees with randomness and controllability. This algorithm has many parameters, such as the proportion of gate node、the proportion of Logic OR gates、the proportion of repeated nodes and the distribution law of gate-fanout.2) The DFLM (Deep-First-Left-Most) heuristic is the most widely used variable ordering heuristic. It is shown that its performance is still only vaguely understood, and not much formal work has been done. By dividing the fault trees into two categories: NRFT (Fault Tree without Repeated variables) and RFT (Fault Tree with Repeated variables), this paper does a systematical study on the performance of DFLM heuristic. For NRFT, the DFLM heuristic is proved to be the optimal variable ordering heuristic. For RFT, the experiments data show that the DFLM heuristic has a good performance in RFT with small number of repeated variables. 3) One very important research direction is to design more powerful heuristics than DFLM heuristics. To improve the performance of DFLM heuristic, a large number of experiments are performed to compare the performance of traditional DFLM heuristic with weighting DFLM (WDFLM) heuristic and repeated-event-priority DFLM (RDFLM) heuristic. This paper also presents a new weighting DFLM (NWDFLM) heuristic based on the experimental results and conclusions on the performance comparison, and a practical suggestion of order of heuristic selection to process a large fault tree is:NWDFLM<WDFLM<RDFLM.4) One very important common feature for good static heuristics is to respect modules. This paper provides the definitions and some basic properties of variable-compact fault tree, and establishes a set of redundant variable absorption rules by extending the Boolean algebra laws (idempotent law, the absorption law, distributive law). It also designs a simplification algorithm by combining the modularization techniques and absorption rules. With the help of simplification and modularization, a module-respect ordering heuristic is developed. An example is proposed as a negative response to the question of whether module-respect ordering heuristic can always be the optimal ordering heuristic. It is proved that under certain condition there always exists an optimal ordering that respects modules. This condition is that there is always a bddi*∈MinBDD(mi),0≤i≤k, where each included module variable appears only once.As a summary, this paper focuses on the variable ordering problem in BDD-based fault tree analysis, and DFLM is our basic variable ordering heuristic. It is proved that for NRFT DFLM heuristic is the optimal variable ordering heuristic. With the randomly generated fault trees, both the experimental results and conclusions on the performance comparison among DFLM heuristic, WDFLM heuristic and RDFLM heuristic are given. It also presents a new weighting DFLM heuristic (NWDFLM), which can achieve better analysis performance. By extending the laws of Boolean algebra, it uses the modularization techniques and proposes module-respect ordering heuristic, and give a sufficient condition for it being optimal ordering heuristic.