Depth-First Event Ordering in BDD-Based Fault Tree Analysis

Authors

  • Yuchang Mo Department of Computer Science, Zhejiang Normal University, Jinhua
  • Farong Zhong Department of Computer Science, Zhejiang Normal University, Jinhua
  • Huawen Liu Department of Computer Science, Zhejiang Normal University, Jinhua
  • Quansheng Yang School of Comppute Science and Engineering, Southeast University, Nanjing
  • Gang Cui School of Computer Science and Technology, Harbin Institute of Technology, Harbin

Keywords:

Fault tree analysis, benchmark, event ordering, binary decision diagram

Abstract

In BDD-based fault tree analysis, the size of BDD encoding fault trees heavily depends on the chosen ordering. From a theoretical point of view, finding the best ordering is an intractable task. So, heuristics are used to get good orderings. The most simple, and often one of the best heuristics is depth first left most (DFLM) heuristic. Although having been used widely, the performance of DFLM heuristic is still only vaguely understood, and not much formal work has been done. This paper starts from two different research objects: fault tree without repeated events (NRFT) and fault tree with repeated events (RFT). For NRFT, the BDD generated according to DFLM ordering is proved to be the smallest BDD with the size equal to the total number of events. For RFT, a randomized algorithm is firstly proposed to create reliable benchmarks including large number of random fault trees with different specificities. Then, these benchmarks are used to perform two types of experiments to study the performance of DFLM heuristic. For RFT with small number of repeated events, it is found that the sizes of the BDD built over DFLM orderings are only slightly larger than the sizes of the RFT with different specificities. However, with the increase of the number of repeated events, we encounter the size explosion problem, and the change of repeated event distribution patterns will have a significant impact on the sizes of the BDD built over DFLM orderings. We also find that the number of repeated events is the more important measure than some other specificities (shape, logical type of top gate and OR/AND gate distribution) to estimate the level of the difficulty in BDD-based fault tree analysis.

Downloads

Download data is not yet available.

Downloads

Published

2013-01-30

How to Cite

Mo, Y., Zhong, F., Liu, H., Yang, Q., & Cui, G. (2013). Depth-First Event Ordering in BDD-Based Fault Tree Analysis. Computing and Informatics, 31(6+), 1401–1416. Retrieved from http://147.213.75.17/ojs/index.php/cai/article/view/1324