﻿ 动态故障树的边值多值决策图分析
 计算机系统应用  2018, Vol. 27 Issue (12): 123-128 PDF

Analysis of Edge-Value Multiple-Valued Decision Diagrams of Dynamic Fault Tree
LI Li, LIU Cui-Jie, WANG Zheng, REN Yi-Fei
Department of Electronic and Information Engineering, Beijing Electronics Science and Technology Institute, Beijing 100070, China
Foundation item: Natural science Foundation of Beijing Municipality (4152048)
Abstract: Dynamic fault tree analysis is an important reliability analysis technique for complex systems. However, there are serious state space explosion problems in traditional modular methods such as binary decision diagrams. This paper systematically introduces a dynamic fault tree analysis method of edge-value decision diagram, in which the Edge-Value Multiple-valued Decision Diagram(EVMDD) has a more compact representation function than other existing decision diagrams. By reducing the number of states, the computation time is shortened and the state space explosion problem can be effectively alleviated. The example demonstrates the method and advantage of EVMDD for multi-state systems and multi-functional systems.
Key words: Edge-Value Multiple-valued Decision Diagram (EVMDD)     multiple-valued decision diagrams     fault tree analysis

1 引言

2 边值二叉决策图 2.1 二叉决策图

2.2 多比特函数二叉决策图

 图 1 布尔函数f和f的二叉决策图

2.3 多比特函数边值二叉决策图

(1) 所有节点0-边总是具有零权重, 即0-边的边值为0.

(2) 节点1-边的边值为当其子节点取值为0且其它节点取值相同, 该节点取值为1时的函数值与取值为0时的函数值之差. 即节点xi的1-边的边值e为:

 \begin{aligned}e = & f\left( {{x_1}, \cdots ,{x_{i - 1}},1,0,{x_{n + 2}},\cdots,{x_n} } \right)\\& - f\left( {{x_1}, \cdots ,{x_{i - 1}},0,0,{x_{n + 2}},\cdots,{x_n} } \right)\end{aligned}

 图 2 二叉决策图BDD

 图 3 sinX的边值二叉决策图EVBDD

(1) 对边值二叉决策图由下至上进行递归判断, 判断是否存在冗余节点;

(2) 对存在冗余的同名节点, 保留一个节点即可, 直至边值二叉决策图中不再存有冗余节点.

 图 4 缩减后的边值二叉决策图EVBDD

3 边值多值决策图 3.1 多值决策图

 $\begin{array}{l}f({x_1},{x_2}, \cdots ,{x_{{\rm{i}} - 1}},\alpha ,{x_{i + 1}}, \cdots ,{x_{n }}) \le \\f({x_1},{x_2}, \cdots ,{x_{i - 1}},\beta ,{x_{i + 1}}, \cdots ,{x_{n }})\\\alpha ,\beta \in {R_i},{\text{且}}\alpha \le \beta . \end{array}$

 $\begin{array}{l}{f_0}\left( {{x_1},{x_2},{x_3}} \right) = {x_1} + {x_2} + 2{x_3},\\{x_1}\left( {0,1,2} \right),{x_2}\left( {0,1,2} \right),{x_3}\left( {0,1} \right). \end{array}$
 $f = \left\{ \begin{array}{l}0,{\rm{ }}{f_0} = 0\\1,{\rm{ }}{f_0} \in \left[ {1,2} \right]\\2,{\rm{ }}{f_0} \in \left[ {3,4} \right]\\3,{\rm{ }}{f_0} \in \left[ {5,6} \right]\end{array} \right.$

3.2 边值多值决策图

 图 5 多值函数f的MDD

 图 6 多值函数f的EVMDD

4 案例研究 4.1 高度可靠的网络计算系统

 图 7 高可靠性网络计算系统

 图 8 高可靠性网络计算系统的初始MDD

 图 9 高可靠性网络计算系统动态门的MDD

4.2 环境检测物联网络

 图 10 高可靠性网络计算系统动态门的EVMDD

 图 11 环境检测物联网络的MDD

 图 12 环境检测物联网络的EVMDD

5 结束语

 [1] 高顺川. 动态故障树分析方法及其实现[硕士学位论文]. 长沙: 国防科学技术大学, 2005. [2] 段凌昊, 郭爱民, 潘勇. 动态故障树分析算法研究综述. 电子产品可靠性与环境试验, 2013, 31(4): 59-63. DOI:10.3969/j.issn.1672-5468.2013.04.014 [3] Nagayama S, Sasao T, Butler JT. Analysis of multi-state systems with multi-state components using EVMDDs. Proceedings of the 42nd IEEE International Symposium on Multiple-Valued Logic. Victoria, BC, Canada. 2012. 122–127. [4] 张红林, 付剑, 张春元, 等. 基于同构节点的动态故障树分析方法. 计算机工程与设计, 2011, 32(1): 1-4. [5] 古天龙. 一类新型抽象数据类型: 有序二叉决策图. 桂林电子科技大学学报, 2010, 30(5): 374-388. DOI:10.3969/j.issn.1673-808X.2010.05.002 [6] 凌牧, 袁海文, 马钊, 等. 改进的动态故障树转化为二元决策图的成分组合算法与应用. 系统工程与电子技术, 2016, 38(7): 1600-1605. [7] 高迎平, 李洋, 田楷. 基于有序二元决策图的动态故障树定性分析方法. 计算机与数字工程, 2016, 44(12): 2342-2347. DOI:10.3969/j.issn.1672-9722.2016.12.012 [8] 李佩昌, 袁宏杰, 兰杰, 等. 基于顺序二元决策图的动态故障树分析. 北京航空航天大学学报, 2017, 43(1): 167-175. [9] 钟艳如, 黄美发, 古天龙. 装配序列生成的有序二叉决策图技术研究. 计算机集成制造系统, 2008, 14(10): 1996-2004. [10] 张超. 基于BDD的动态故障树优化分析研究[硕士学位论文]. 西安: 西北工业大学, 2004. [11] Nagayama S, Sasao T. Complexities of graph-based representations for elementary functions. IEEE Transactions on Computers, 2009, 58(1): 106-119. DOI:10.1109/TC.2008.134 [12] Doyle SA, Dugan JB. Dependability assessment using binary decision diagrams (BDDs. Proceedings of the 25th Inter-national Symposium on Fault-Tolerant Computing. Pasadena, CA, USA. 1995. 249–258. [13] Nagayama S, Sasao T. On the optimization of heterogeneous MDDs. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2005, 24(11): 1645-1659. DOI:10.1109/TCAD.2005.852290 [14] 王斌, 吴丹丹, 莫毓昌, 等. 基于多值决策图的动态故障树分析方法. 计算机科学, 2016, 43(10): 70-73, 92. DOI:10.11896/j.issn.1002-137X.2016.10.013 [15] Nagayama S, Sasao T, Butler JT. A systematic design method for two-variable numeric function generators using multiple-valued decision diagrams. IEICE Transactions on Information and Systems, 2010, E93.D(8): 2059-2067. DOI:10.1587/transinf.E93.D.2059 [16] 王宁, 胡大伟. 基于多态多值决策图的多态故障树重要度计算方法. 计算机集成制造系统, 2015, 21(5): 1301-1308. [17] 季会媛, 孟亚, 孙权, 等. 一种容错系统可靠性分析方法. 计算机工程与科学, 2001, 23(5): 36-38, 50. DOI:10.3969/j.issn.1007-130X.2001.05.009 [18] 冯雪, 王喜富. 基于动态故障树的计算机联锁系统可靠性及性能分析研究. 铁道学报, 2011, 33(12): 78-82. DOI:10.3969/j.issn.1001-8360.2011.12.013