Computer Science ›› 2016, Vol. 43 ›› Issue (10): 70-73, 92.doi: 10.11896/j.issn.1002-137X.2016.10.013

Previous Articles     Next Articles

Dynamic Fault Tree Analysis Based on Multiple-valued Decision Diagrams

WANG Bin, WU Dan-dan, MO Yu-chang and CHEN Zhong-yu   

  • Online:2018-12-01 Published:2018-12-01

Abstract: In the system reliability analysis,dynamic fault trees analysis has been used as a very important technique for many years.However,when these kinds of large dynamic subtrees appear,which abound in models of real-world dyna-mic software and embedded computing systems,the state explosion problem is too serious to be removed.In order to improve computing efficiency,this paper introduced an efficient,multiple-valued decision-diagram (MDD)-based DFT analysis approach.This approach restricts the state-space methods only to the subtree components associated with dynamic failure behaviors.By using multiple-valued variables to encode the dynamic gates,a single compact MDD is then generated.Finally,the failure probability is calculated to describe the reliability of the system.Applications and advantages of the proposed approach are illustrated through detailed analysis of a practical case study.

Key words: Multiple-valued decision diagram (MDD),Dynamic fault tree (DFT),Markov,Reliability

[1] Vemuri K K,et al.Automatic synthesis of fault trees for computer-based systems[J].IEEE Trans.Rel.,1999,48(4):394-402
[2] Sullivan J K,et al.The Galileo fault tree analysis tool[C]∥Proc 29th Annu.Int.Symp.Fault-Tolerant Comput.,Madison,WI,USA,1999:232-237
[3] Meshkat L,et al.Dependability analysis of systems with on-demand and active failure modes,using dynamic fault trees[J].IEEE Trans.Rel.,2002,51(2):240-251
[4] Huang C Y,Chang Y R,An improved decomposition scheme for assessing the reliability of embedded systems by using dynamic fault trees[J].Rel.Eng.Syst.Safety,2007,92(10):1403-1412
[5] Amari S,et al.A new approach to solve dynamic fault trees[C]∥Proc.IEEE Annu.Rel.Maintainability Symp..Tampa,FL,USA,2003:374-379
[6] Dugan J B,et al.Developing a low-cost high quality softwaretool for dynamic fault tree analysis[J].IEEE Trans.Rel.,2000,49(1):49-59
[7] Miller D M.Multiple-valued logic design tools[C]∥Proc.23rd Multiple-Valued Logic (ISMVL).1993:2-11
[8] Xing L,Dugan J B.Dependability analysis using multiple- valued decision diagrams[C]∥Proc.6th Probabilistic Safety Assessment Manag.,2002
[9] Xing L,Dai Y,A new decision diagram based method for efficient analysis onmulti-state systems[J].IEEE Trans.Dependable Secure Comput.,2009,6(3):161-174
[10] Ou Y,Dugan J B.Sensitivity analysis of modular dynamic fault trees[C]∥Proc.Compute.Perform.Dependability Symp..2000:35-43
[11] Tarjan R.Depth first search and linear graph algorithms[J].Sensors,2006,4(4):114-121
[12] Gao Shun-chuan.Methods and Implementation of Dynamic Fault Tree Analysis[D].Changsha:National University of Defense Technology,2005(in Chinese) 高顺川.动态故障树分析方法及其实现[D].长沙:国防科技大学,2005
[13] Gu Ying-kui,Li Jing.Importance Analysis of Multi-state System Based on Multipe-valued Decision Diagram[J].China Safety Scien-ce Journal,2014,4(6):44-50(in Chinese) 古莹奎,李晶,基于多值决策图的多状态系统重要度分析[J].中国安全科学学报,2014,4(6):44-50
[14] Zhang Hong-lin,Zhang Chun-yuan,Liu Dong.An Identification Method of Independent Module Applying to Dynamic Fault Tree with Interdependent Basic Events and Repeated Events[J].Cinese Journal of Computers,2012,5(2):229-243(in Chinese) 张红林,张春元,刘东.一种适用于具有相互依赖基本事件和重复事件的动态故障树独立模块识别方法[J].计算机学报,2012,5(2):229-243
[15] Cheng Ming-hua,Yao Yi-ping.Application of Dynamic FaultTree Analysis to Software and Hardware Fault-tolerant Control Computer Systems[J].Acta Aeronautica et Astronsutica Sinica,2000,21(1):34-37(in Chinese) 程明华,姚一平.动态故障树分析方法在软、硬件容错计算机系统中的应用[J].航空学报,2000,21(1):34-37

No related articles found!
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[3] 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 .
[4] 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 .
[5] 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 .
[6] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[7] 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 .
[8] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[9] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[10] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99, 116 .