基于BDD的动态故障树优化分析研究
|
摘要
现今，故障树分析法已广泛地应用到系统可靠性和安全性的评价中。本文研究了动态建造故障树的方法，以及基于BDD的故障树定性分析、定量分析和模块分析方法。主要做了以下几方面的工作：
首先，提出了一种基于Windows界面的计算机辅助动态建造故障树的设计思想和实现方法，并在此基础上设计开发了一套可视化动态建造故障树软件，解决了当前建树方法通用性差和工作量大的问题。
其次，用基于结构重要度和基于神经网络两种方法实现了底事件最优指标顺序的确定，解决了底事件指标顺序对BDD规模的影响问题。依据布尔函数Shannon分解和BDD图的关系，用递归法实现了故障树向BDD转化。
再次，在基于BDD的故障树定性分析研究中，提出并实现了基于BDD和素数法相结合的单调关联故障树最小割集求解的新方法，用迭代法实现了非单调关联故障树质蕴含的求解。在基于BDD的故障树定量分析研究中，实现了顶事件发生概率和绝对失效强度的求解。为解决大型复杂故障树的简化分析问题，提出并实现了基于深度优先最左遍历和BDD相结合的故障树模块分析法。实现了计算机自动化故障树分析。通过这些方法，解决了基于布尔代数的故障树分析中长期存在的“组合爆炸”问题。
最后，探讨了故障树分析法和可靠性框图法在系统可靠性研究中的关系，首次得出两者分析结果满足互补关系。
Nowadays, Fault Tree Analysis (FTA) has been widely used in the assessing of reliability and safety of systems. An active FTA constructing method, qualitative and quantitative as well as module analysis of FTA based on Binary Decision Diagram (BDD) was researched in this thesis. Including the following areas of contents:
First, based on Windows interface, a design and implementation method of computer aided active FTA constructing method was presented. According to this method, the visualized active fault tree construction software was developed. And the worse versatility and huge working load problems of FTA construction were solved.
Then, the optimal ordering permutation for the basic events of fault tree was produced by structural importance and neural network methods respectively, and the resulting size problem of BDD affected by the basic events' order was solved. According to the relationship of Shannon's formula of Boolean functions and BDD, the fault tree structure to BDD conversion was accomplished by recursive method.
After then, a new method of solving the minimal cuts of s-coherent tree based on BDD and prime number was given in the qualitative analysis of FTA based on BDD, the prime implicant sets of non s-coherent tree was calculated by an iterative method. The probability and unconditional failure intensity of top event was computed in the quantitative analysis of FTA based on BDD. A Fault Tree Module Analysis (FTMA) based on. depth-first left-most traversals and BDD was presented to solve large complicated FTA problems. And the automatic computer analysis was implemented. The long exist NP (Non-deterministic Polynomial) problems of FTA based on Boolean algebra was solved by these methods.
Finally, the relationship of FTA and Reliability Block Diagram Analysis (RBDA) was studied, and the complementation relation of their results was first verified.
首先，提出了一种基于Windows界面的计算机辅助动态建造故障树的设计思想和实现方法，并在此基础上设计开发了一套可视化动态建造故障树软件，解决了当前建树方法通用性差和工作量大的问题。
其次，用基于结构重要度和基于神经网络两种方法实现了底事件最优指标顺序的确定，解决了底事件指标顺序对BDD规模的影响问题。依据布尔函数Shannon分解和BDD图的关系，用递归法实现了故障树向BDD转化。
再次，在基于BDD的故障树定性分析研究中，提出并实现了基于BDD和素数法相结合的单调关联故障树最小割集求解的新方法，用迭代法实现了非单调关联故障树质蕴含的求解。在基于BDD的故障树定量分析研究中，实现了顶事件发生概率和绝对失效强度的求解。为解决大型复杂故障树的简化分析问题，提出并实现了基于深度优先最左遍历和BDD相结合的故障树模块分析法。实现了计算机自动化故障树分析。通过这些方法，解决了基于布尔代数的故障树分析中长期存在的“组合爆炸”问题。
最后，探讨了故障树分析法和可靠性框图法在系统可靠性研究中的关系，首次得出两者分析结果满足互补关系。
Nowadays, Fault Tree Analysis (FTA) has been widely used in the assessing of reliability and safety of systems. An active FTA constructing method, qualitative and quantitative as well as module analysis of FTA based on Binary Decision Diagram (BDD) was researched in this thesis. Including the following areas of contents:
First, based on Windows interface, a design and implementation method of computer aided active FTA constructing method was presented. According to this method, the visualized active fault tree construction software was developed. And the worse versatility and huge working load problems of FTA construction were solved.
Then, the optimal ordering permutation for the basic events of fault tree was produced by structural importance and neural network methods respectively, and the resulting size problem of BDD affected by the basic events' order was solved. According to the relationship of Shannon's formula of Boolean functions and BDD, the fault tree structure to BDD conversion was accomplished by recursive method.
After then, a new method of solving the minimal cuts of s-coherent tree based on BDD and prime number was given in the qualitative analysis of FTA based on BDD, the prime implicant sets of non s-coherent tree was calculated by an iterative method. The probability and unconditional failure intensity of top event was computed in the quantitative analysis of FTA based on BDD. A Fault Tree Module Analysis (FTMA) based on. depth-first left-most traversals and BDD was presented to solve large complicated FTA problems. And the automatic computer analysis was implemented. The long exist NP (Non-deterministic Polynomial) problems of FTA based on Boolean algebra was solved by these methods.
Finally, the relationship of FTA and Reliability Block Diagram Analysis (RBDA) was studied, and the complementation relation of their results was first verified.
引文
[1] 梅启智等．系统可靠性工程基础．科学出版社．1992
[2] 黄祥瑞等．可靠性工程．清华大学出版社．1990．10．
[3] 郭永基等．可靠性工程原理．清华大学出版社．2002．1
[4] 章国栋等．系统可靠性和维修性的分析与设计．北京航空航天大学出版社．1990．7
[5] 田双亮等．功能层次模型及故障树的构建．西北民族学院学报．2000．12
[6] 陶军等．控制系统故障树自动建造方法的研究．自动化学报．1997．6
[7] 金星等．直接不交化方法在故障树定量分析中的应用．中国空间科学技术，2001，6(3)：60-64．
[8] 曾亮等．多状态系统故障树的一种生成方法．系统工程学报．1998．4
[9] 于晓丹等．故障树最小路集设计的新方法．吉林工业大学学报．1996．4
[10] 朱敏波等．计算机辅助故障树的建立与分析．计算机辅助工程．1998．1
[11] 贾玉双．基于故障树模型的系统可靠性分析与仿真．湘潭大学自然科学学报．2001．4
[12] 周经伦．一种故障树分析的新算法．模糊系统与数学．1997．3
[13] 于晓丹．Auto LISP在绘制机械设备故障树中的应用．辽宁工学院学报．1998．3：57-58．
[14] 马勇等．基于单元输入输出模型控制系统故障树自动建造的一种方法．1999．33(11)．
[15] 桑怀胜等．动态建造故障树的计算机实现．现代计算机．1999．70(1)：49-52．
[16] 周海等．故障树分析软件研究．哈尔滨工业大学学报．2001．33(10)：666-667．
[17] 陆愈实等．故障树可视化分析系统．中国安全科学学报．2000．10(5)：44-48．
[18] 郭淑芬．图形技术在航空发动机故障树绘制中的应用．推进技术．1998．19(3)：70-73．
[19] M.S.Elliott.Computer-Assisted Fault-Tree Construction Using A Knowledge-Based Approach.IEEE transactions on reliability. 1994.1
[20] J.A.Bogarin Geymayr.Fault-tree Analysis:A knowledge-Engineering Approach. IEEE transactions on reliability. 1995.1
[21] K.K.Vemuri.Automatic Synthesis of Fault Trees for Computer-based Systems. IEEE transactions on reliability. 1999.4
[22] S.B.Akers, "Binary decision diagrams",IEEE Transaction on Computer, Vol 27,1978,pp509-516.
[23] Coudert O,Madre J.Fault tree analysis:10~(20)prime implicants and beyond,Proceedings Annual Reliability and Maintainability symposium, 1993
[24] A.Rauzy, "A brief introduction to binary decision diagrams",European J.Automation,Vol 30,No 8,1996,pp1033-1050.
[25] Bryant R.E., "Graph-based algorithms for Boolean function manipulation",IEEE Transactions on Computers,Vol 35,No 8,1986,pp677-691.
[26] Antoine Rauzy,"New algoriththms for fault tree analysis", Reliability Engineering and System
Safety, Vol 40,No 3, 1993,pp203-211.
[27] Sinnamon R.M. and Andrews J.D., "New Approaches to Evaluating Fault Trees", Reliability Engineering and System Safety, Vol 58, 1997, pp89-96.
[28] Sinnamon R.M and Andrews J.D.,"Improved Efficiency in Qualitative Fault Tree Analysis", Quality and Reliability Engineering International, Vol 13, 1997, pp293-298.
[29] Sinnamon R.M and Andrews J.D., "Improved Accuracy in Quantitative Fault Tree Analysis", Quality and Reliability Engineering International, Vol 13, 1997, pp285-292.
[30] Sinnamon R.M. and Andrews J.D., "Quantitative Fault Tree Analysis Using Binary Decision Tables", European Journal of Automation, Vol 30, No 8, 1996, pp1051-1071.
[31] Bartlett L.M. and Andrews J.D., "Efficient Basic Event Ordering Schemes for Fault Tree Analysis", Quality and Reliability Engineering International, Vol 15, No 2, 1999,pp95-101.
[32] Andrews J.D, and Dunnett S.J., "Event Tree Analysis using Binary Decision Diagrams", IEEE Transactions on Reliability, Vol 49, No 2, June 2000. pp230-239.
[33] Bartlett L.M. and Andrews J.D, "An Ordering Heuristic to Develop the BDD based on Structural hnportance", Reliability Engineering and System Safety, Vol 72, 2001, pp31-38.
[34] Bartlett L.M. and Andrews J.D, "Choosing a Heuristic for the "Fault Tree to Binary Decision Diagram" Convertion, Using Neural Networks", The IEEE Transactions on Reliability. Vol 51, No 3, September 2002, pp344-349.
[35] Andrews J.D. "The Use of Not Logic in Fault Tree Analysis", accepted for publication in Quality and Reliability Engineering International. Vol 17, 2001, pp143-150.
[36] Bartlett L.M. and Andrews J.D., "Comparison of Two New Approaches to Variable Ordering" for Binary Decision Diagrams", accepted for publication in Quality and Reliability Engineering International. Vol 17, 2001 pp151-158.
[37] Beeson S. and Andrews J.D., "Birnbaum's Measure of Importance for Non-coherent Systems", The IEEE Transactions on Reliability. Vol 52, No 2, June 2003, pp213-219.
[38] Karen A.Reay and Andrews J.D., "A fault tree analysis using binary decision diagrams" Reliability Engineering and System Safety, Vol 78,2002, pp45-56.
[39] Steven J.Friedman and Kenneth j.Supowit. "Finding the optimal variable ordering for binary decision diagrams",IEEE Transactions on computer, Vol 39,No 5, 1990,pp710-713.
[40] 胡守仁等．神经网络导论．国防科技大学出版社．1993，10．
[41] 张乃尧等．神经网络与模糊控制．清华大学出版社．1998，10．
[42] 许东等．基于MATLAB 6.x的系统分析与设计——神经网络(第二版)．西安电子科技出版社．2002．9．
[43] 郑申白等．网络参数对神经BP算法预报结果的影响．钢铁研究学报，1997，9(1)：42-45．
[44] 张玲等．前向神经网络设计问题的回顾与探索．计算机工程与科学，1998，20(4)：1-10．
[45] 徐勇等．系统可靠性分配的神经网络模型．系统工程电子学报，2001，23(1)：90-92．
[46] C.M.Bishop,Neural networks for pattern recognition:Clarendin Press,1995.
[47] R.E.Bryant.Graph-based algorithoms for Boolean functions using a graphical represention.IEEE Trans On Comput.,8,C-35,1986.
[48] Sheldon B.Akers.Binary Decision Diagrams.IEEE Trans on Comput.6,C-27.1978.
[49] Kenneth D.Russell, "Fault tree reduction and quantification——an overview of IRRAS algorithms",Reliability Engineering and System Safety, Vol 40, 1993,pp149-164.
[50] Hae Sang.Lee. and Chang Hoon.Lie, "A computation method for Evaluating importance-measures of gates in a fault tree",IEEE Transactions on Reliability, Vol 46,No 3,September 1997,pp360-365.
[51] 周经纶等．非单调关联故障树顶事件发生概率的新算法．国防科技大学学报，1999，21(2)：104—107．
[52] 谭元发．非单调关联系统故障树分析．数学理论与应用，2001，21(2)：50-53．
[53] Yves Dutit and Antoine Rauzy, "A linear-time algorithm to find modules of fault tree", IEEE Transactions on Reliability, Vol 45, No 3,September 1996, pp422-425.
[54] Kohda T, "Finding modules in.fault trees ",IEEE Transactions on Reliability, Vol 38,No 2, June 1989, pp165-176.
[55] Anand A, "Hiearchical analysis of fault trees with dependencies,using decomposition",RAMS Proceedings, 1998,pp69-75.
[56] Camarinopoulous L and Yllera J., "An improved top-down algorithm combined with modularization as highly efficient method for fault tree analysis",Reliability Engineering, Vol 11,No 6,1985,pp93-10.
[57] Tarjan R.E., "Depth first search and linear graph algorithm",Computer, Vol 1,4,1972,pp146-160.
[2] 黄祥瑞等．可靠性工程．清华大学出版社．1990．10．
[3] 郭永基等．可靠性工程原理．清华大学出版社．2002．1
[4] 章国栋等．系统可靠性和维修性的分析与设计．北京航空航天大学出版社．1990．7
[5] 田双亮等．功能层次模型及故障树的构建．西北民族学院学报．2000．12
[6] 陶军等．控制系统故障树自动建造方法的研究．自动化学报．1997．6
[7] 金星等．直接不交化方法在故障树定量分析中的应用．中国空间科学技术，2001，6(3)：60-64．
[8] 曾亮等．多状态系统故障树的一种生成方法．系统工程学报．1998．4
[9] 于晓丹等．故障树最小路集设计的新方法．吉林工业大学学报．1996．4
[10] 朱敏波等．计算机辅助故障树的建立与分析．计算机辅助工程．1998．1
[11] 贾玉双．基于故障树模型的系统可靠性分析与仿真．湘潭大学自然科学学报．2001．4
[12] 周经伦．一种故障树分析的新算法．模糊系统与数学．1997．3
[13] 于晓丹．Auto LISP在绘制机械设备故障树中的应用．辽宁工学院学报．1998．3：57-58．
[14] 马勇等．基于单元输入输出模型控制系统故障树自动建造的一种方法．1999．33(11)．
[15] 桑怀胜等．动态建造故障树的计算机实现．现代计算机．1999．70(1)：49-52．
[16] 周海等．故障树分析软件研究．哈尔滨工业大学学报．2001．33(10)：666-667．
[17] 陆愈实等．故障树可视化分析系统．中国安全科学学报．2000．10(5)：44-48．
[18] 郭淑芬．图形技术在航空发动机故障树绘制中的应用．推进技术．1998．19(3)：70-73．
[19] M.S.Elliott.Computer-Assisted Fault-Tree Construction Using A Knowledge-Based Approach.IEEE transactions on reliability. 1994.1
[20] J.A.Bogarin Geymayr.Fault-tree Analysis:A knowledge-Engineering Approach. IEEE transactions on reliability. 1995.1
[21] K.K.Vemuri.Automatic Synthesis of Fault Trees for Computer-based Systems. IEEE transactions on reliability. 1999.4
[22] S.B.Akers, "Binary decision diagrams",IEEE Transaction on Computer, Vol 27,1978,pp509-516.
[23] Coudert O,Madre J.Fault tree analysis:10~(20)prime implicants and beyond,Proceedings Annual Reliability and Maintainability symposium, 1993
[24] A.Rauzy, "A brief introduction to binary decision diagrams",European J.Automation,Vol 30,No 8,1996,pp1033-1050.
[25] Bryant R.E., "Graph-based algorithms for Boolean function manipulation",IEEE Transactions on Computers,Vol 35,No 8,1986,pp677-691.
[26] Antoine Rauzy,"New algoriththms for fault tree analysis", Reliability Engineering and System
Safety, Vol 40,No 3, 1993,pp203-211.
[27] Sinnamon R.M. and Andrews J.D., "New Approaches to Evaluating Fault Trees", Reliability Engineering and System Safety, Vol 58, 1997, pp89-96.
[28] Sinnamon R.M and Andrews J.D.,"Improved Efficiency in Qualitative Fault Tree Analysis", Quality and Reliability Engineering International, Vol 13, 1997, pp293-298.
[29] Sinnamon R.M and Andrews J.D., "Improved Accuracy in Quantitative Fault Tree Analysis", Quality and Reliability Engineering International, Vol 13, 1997, pp285-292.
[30] Sinnamon R.M. and Andrews J.D., "Quantitative Fault Tree Analysis Using Binary Decision Tables", European Journal of Automation, Vol 30, No 8, 1996, pp1051-1071.
[31] Bartlett L.M. and Andrews J.D., "Efficient Basic Event Ordering Schemes for Fault Tree Analysis", Quality and Reliability Engineering International, Vol 15, No 2, 1999,pp95-101.
[32] Andrews J.D, and Dunnett S.J., "Event Tree Analysis using Binary Decision Diagrams", IEEE Transactions on Reliability, Vol 49, No 2, June 2000. pp230-239.
[33] Bartlett L.M. and Andrews J.D, "An Ordering Heuristic to Develop the BDD based on Structural hnportance", Reliability Engineering and System Safety, Vol 72, 2001, pp31-38.
[34] Bartlett L.M. and Andrews J.D, "Choosing a Heuristic for the "Fault Tree to Binary Decision Diagram" Convertion, Using Neural Networks", The IEEE Transactions on Reliability. Vol 51, No 3, September 2002, pp344-349.
[35] Andrews J.D. "The Use of Not Logic in Fault Tree Analysis", accepted for publication in Quality and Reliability Engineering International. Vol 17, 2001, pp143-150.
[36] Bartlett L.M. and Andrews J.D., "Comparison of Two New Approaches to Variable Ordering" for Binary Decision Diagrams", accepted for publication in Quality and Reliability Engineering International. Vol 17, 2001 pp151-158.
[37] Beeson S. and Andrews J.D., "Birnbaum's Measure of Importance for Non-coherent Systems", The IEEE Transactions on Reliability. Vol 52, No 2, June 2003, pp213-219.
[38] Karen A.Reay and Andrews J.D., "A fault tree analysis using binary decision diagrams" Reliability Engineering and System Safety, Vol 78,2002, pp45-56.
[39] Steven J.Friedman and Kenneth j.Supowit. "Finding the optimal variable ordering for binary decision diagrams",IEEE Transactions on computer, Vol 39,No 5, 1990,pp710-713.
[40] 胡守仁等．神经网络导论．国防科技大学出版社．1993，10．
[41] 张乃尧等．神经网络与模糊控制．清华大学出版社．1998，10．
[42] 许东等．基于MATLAB 6.x的系统分析与设计——神经网络(第二版)．西安电子科技出版社．2002．9．
[43] 郑申白等．网络参数对神经BP算法预报结果的影响．钢铁研究学报，1997，9(1)：42-45．
[44] 张玲等．前向神经网络设计问题的回顾与探索．计算机工程与科学，1998，20(4)：1-10．
[45] 徐勇等．系统可靠性分配的神经网络模型．系统工程电子学报，2001，23(1)：90-92．
[46] C.M.Bishop,Neural networks for pattern recognition:Clarendin Press,1995.
[47] R.E.Bryant.Graph-based algorithoms for Boolean functions using a graphical represention.IEEE Trans On Comput.,8,C-35,1986.
[48] Sheldon B.Akers.Binary Decision Diagrams.IEEE Trans on Comput.6,C-27.1978.
[49] Kenneth D.Russell, "Fault tree reduction and quantification——an overview of IRRAS algorithms",Reliability Engineering and System Safety, Vol 40, 1993,pp149-164.
[50] Hae Sang.Lee. and Chang Hoon.Lie, "A computation method for Evaluating importance-measures of gates in a fault tree",IEEE Transactions on Reliability, Vol 46,No 3,September 1997,pp360-365.
[51] 周经纶等．非单调关联故障树顶事件发生概率的新算法．国防科技大学学报，1999，21(2)：104—107．
[52] 谭元发．非单调关联系统故障树分析．数学理论与应用，2001，21(2)：50-53．
[53] Yves Dutit and Antoine Rauzy, "A linear-time algorithm to find modules of fault tree", IEEE Transactions on Reliability, Vol 45, No 3,September 1996, pp422-425.
[54] Kohda T, "Finding modules in.fault trees ",IEEE Transactions on Reliability, Vol 38,No 2, June 1989, pp165-176.
[55] Anand A, "Hiearchical analysis of fault trees with dependencies,using decomposition",RAMS Proceedings, 1998,pp69-75.
[56] Camarinopoulous L and Yllera J., "An improved top-down algorithm combined with modularization as highly efficient method for fault tree analysis",Reliability Engineering, Vol 11,No 6,1985,pp93-10.
[57] Tarjan R.E., "Depth first search and linear graph algorithm",Computer, Vol 1,4,1972,pp146-160.