计算机科学 ›› 2016, Vol. 43 ›› Issue (10): 70-73, 92.doi: 10.11896/j.issn.1002-137X.2016.10.013

• 2015 第五届全国可信计算学术会议 • 上一篇    下一篇

基于多值决策图的动态故障树分析方法

王斌,吴丹丹,莫毓昌,陈中育   

  1. 浙江师范大学数理与信息工程学院 金华321004,浙江师范大学数理与信息工程学院 金华321004,浙江师范大学数理与信息工程学院 金华321004,浙江师范大学数理与信息工程学院 金华321004
  • 出版日期:2018-12-01 发布日期:2018-12-01
  • 基金资助:
    本文受国家基金面上项目(61272007,2)资助

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

摘要: 针对具有动态故障模式的复杂系统,动态故障树分析一直是很重要的可靠性分析技术。为了提升可靠性分析效率,已有研究提出了各种模块化方法,但是对于实际动态故障树模型中由于事件关联导致的大型动态子树,这些模块化方法的状态空间爆炸问题仍然很突出。因此介绍了一种基于多值决策图(Multiple-valued Decision Diagrams,MDD)来分析动态故障树的方法,通过多值变量编码动态门,利用单一系统MDD模型刻画各种动态和静态可靠性行为,有效地缓解了状态爆炸问题。通过一个具体的实例说明了多值决策图方法的应用和优势。

关键词: 多值决策图,动态故障树,马尔科夫,可靠性

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!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75, 88 .
[2] 夏庆勋,庄毅. 一种基于局部性原理的远程验证机制[J]. 计算机科学, 2018, 45(4): 148 -151, 162 .
[3] 厉柏伸,李领治,孙涌,朱艳琴. 基于伪梯度提升决策树的内网防御算法[J]. 计算机科学, 2018, 45(4): 157 -162 .
[4] 王欢,张云峰,张艳. 一种基于CFDs规则的修复序列快速判定方法[J]. 计算机科学, 2018, 45(3): 311 -316 .
[5] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[6] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[7] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[8] 刘琴. 计算机取证过程中基于约束的数据质量问题研究[J]. 计算机科学, 2018, 45(4): 169 -172 .
[9] 钟菲,杨斌. 基于主成分分析网络的车牌检测方法[J]. 计算机科学, 2018, 45(3): 268 -273 .
[10] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99, 116 .