基于公共事件的二元決策圖底事件排序方法研究
發(fā)布時間：2018-09-14 08:08
【摘要】：由于二元決策圖(BDD)能夠有效的表示布爾函數(shù),使得它在許多領(lǐng)域都能廣泛使用,包括數(shù)字芯片設(shè)計和系統(tǒng)可靠性分析。尤其是用于在系統(tǒng)可靠性領(lǐng)域來解決故障樹時,二元決策圖技術(shù)顯示了較低的運算復(fù)雜度和高效率的優(yōu)點。 系統(tǒng)故障樹分析,簡稱FTA(Fault Tree Analysis),是系統(tǒng)可靠性工程學(xué)的重要分支,是目前國內(nèi)外公認的評價復(fù)雜系統(tǒng)可靠性與安全性的一種實用方法。故障樹分析作為一種被廣泛采用的方法,通常用來估算工業(yè)領(lǐng)域中各系統(tǒng)失效的概率,從而有效地評估系統(tǒng)風(fēng)險水平。故障樹分析是指獲取導(dǎo)致系統(tǒng)失敗的各種事件組合,這些事件組合也叫最小割集。當基本事件的故障率給定之后,系統(tǒng)失效的概率就能通過對這些最小割集的定量分析給出。但是,當故障樹很大,并且包含重復(fù)事件時,采用傳統(tǒng)的方法來獲取最小割集就變得相當困難,極端情況下甚至不可解。正是為了解決這個問題,將BDD算法引入了系統(tǒng)可靠性領(lǐng)域。使用這種技術(shù)時,需要將故障樹轉(zhuǎn)化成相應(yīng)的輯表達式,也即二元決策圖形式。轉(zhuǎn)化過程中,故障樹的基本事件需要以一定的順序排序。所選擇的排序順序?qū)⒂绊憳?gòu)造的BDD的節(jié)點數(shù),從而影響這種方法的實際效果。但是,只有當能夠轉(zhuǎn)化為BDD并且BDD的大小有限時,這種分析方法才是有效的。所以,問題的關(guān)鍵在于在轉(zhuǎn)化過程中對基本事件的排序。一個好的排序算法能夠產(chǎn)生極為有效的分析過程,而一個糟糕的排序算法甚至不能夠得出BDD。 在故障樹領(lǐng)域內(nèi),大多數(shù)BDD排序算法都基于Bryant提出的限制,這種限制是指,在將故障樹轉(zhuǎn)化為BDD的過程中,必須使基本事件的排序方式保持固定。盡管這種方式產(chǎn)生的BDD是唯一確定的,但是它并不能保證得出的BDD是最小的。在論文中,將應(yīng)用漸進式排序算法來產(chǎn)生BDD,并介紹一種全新的基于公共事件的排序算法。
[Abstract]:Because the binary decision graph (BDD) can represent Boolean function effectively, it can be widely used in many fields, including digital chip design and system reliability analysis. Especially in the field of system reliability to solve the fault tree, binary decision graph technology shows the advantages of low computational complexity and high efficiency. System fault tree analysis, referred to as FTA (Fault Tree Analysis), is an important branch of system reliability engineering and a practical method for evaluating the reliability and security of complex systems at home and abroad. As a widely used method, fault tree analysis is usually used to estimate the failure probability of each system in the industrial field, so as to evaluate the system risk level effectively. Fault tree analysis refers to the acquisition of various combinations of events that lead to system failure, which are also called minimal cut sets. When the failure rate of the basic event is given, the probability of system failure can be obtained by quantitative analysis of these minimal cut sets. However, when the fault tree is very large and contains repeated events, it is very difficult to obtain the minimum cut set by the traditional method, and in extreme cases it is even unsolvable. In order to solve this problem, BDD algorithm is introduced into the field of system reliability. When using this technique, the fault tree needs to be transformed into the corresponding repertoire expression, that is, binary decision graph. In the process of transformation, the basic events of the fault tree need to be sorted in a certain order. The order chosen will affect the number of nodes in the constructed BDD, thus affecting the actual effect of this method. However, this analysis method is effective only when it can be converted to BDD and the size of BDD is limited. Therefore, the key to the problem lies in the sequencing of basic events in the process of transformation. A good sort algorithm can produce a very efficient analysis process, and a bad sort algorithm can't even get BDD. In the field of fault tree, most BDD sorting algorithms are based on the limitation proposed by Bryant, which means that in the process of transforming the fault tree into BDD, the sorting mode of basic events must be kept fixed. Although the BDD produced in this way is only certain, it does not guarantee that the resulting BDD is minimal. In this paper, progressive sorting algorithm is applied to generate BDD, and a new sort algorithm based on common events is introduced.
【學(xué)位授予單位】：上海交通大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2009
【分類號】：C934
本文編號：2242080
[Abstract]:Because the binary decision graph (BDD) can represent Boolean function effectively, it can be widely used in many fields, including digital chip design and system reliability analysis. Especially in the field of system reliability to solve the fault tree, binary decision graph technology shows the advantages of low computational complexity and high efficiency. System fault tree analysis, referred to as FTA (Fault Tree Analysis), is an important branch of system reliability engineering and a practical method for evaluating the reliability and security of complex systems at home and abroad. As a widely used method, fault tree analysis is usually used to estimate the failure probability of each system in the industrial field, so as to evaluate the system risk level effectively. Fault tree analysis refers to the acquisition of various combinations of events that lead to system failure, which are also called minimal cut sets. When the failure rate of the basic event is given, the probability of system failure can be obtained by quantitative analysis of these minimal cut sets. However, when the fault tree is very large and contains repeated events, it is very difficult to obtain the minimum cut set by the traditional method, and in extreme cases it is even unsolvable. In order to solve this problem, BDD algorithm is introduced into the field of system reliability. When using this technique, the fault tree needs to be transformed into the corresponding repertoire expression, that is, binary decision graph. In the process of transformation, the basic events of the fault tree need to be sorted in a certain order. The order chosen will affect the number of nodes in the constructed BDD, thus affecting the actual effect of this method. However, this analysis method is effective only when it can be converted to BDD and the size of BDD is limited. Therefore, the key to the problem lies in the sequencing of basic events in the process of transformation. A good sort algorithm can produce a very efficient analysis process, and a bad sort algorithm can't even get BDD. In the field of fault tree, most BDD sorting algorithms are based on the limitation proposed by Bryant, which means that in the process of transforming the fault tree into BDD, the sorting mode of basic events must be kept fixed. Although the BDD produced in this way is only certain, it does not guarantee that the resulting BDD is minimal. In this paper, progressive sorting algorithm is applied to generate BDD, and a new sort algorithm based on common events is introduced.
【學(xué)位授予單位】：上海交通大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2009
【分類號】：C934
【參考文獻】
相關(guān)期刊論文 前10條
1 蔣樂天,徐國治,應(yīng)忍冬,張昊;系統(tǒng)可靠性和可用性分析技術(shù)[J];電訊技術(shù);2002年04期
2 徐亨成,張建國;基于BDD技術(shù)下的故障樹重要度分析[J];電子機械工程;2003年06期
3 卿和民,鄧林,李勇;可靠性維修性工程軟件的現(xiàn)狀分析與應(yīng)用[J];電子產(chǎn)品可靠性與環(huán)境試驗;2001年04期
4 董玉革,朱文予,陳心昭;模糊故障樹分析及應(yīng)用[J];合肥工業(yè)大學(xué)學(xué)報(自然科學(xué)版);1996年04期
5 趙廷弟,曾聲奎,康銳;計算機輔助可靠性設(shè)計分析系統(tǒng)研究[J];航空學(xué)報;2000年03期
6 華小洋,胡宗武,范祖堯;模糊故障樹分析方法[J];機械強度;1998年01期
7 陶軍,李應(yīng)紅,辛宇峰;控制系統(tǒng)故障樹自動建造方法的研究[J];自動化學(xué)報;1997年06期
8 周經(jīng)倫,孫權(quán);一種故障樹分析的新算法[J];模糊系統(tǒng)與數(shù)學(xué);1997年03期
9 閔蘋;童節(jié)娟;奚樹人;;利用二元決策圖求解故障樹的基本事件排序[J];清華大學(xué)學(xué)報(自然科學(xué)版);2005年12期
10 曾亮,郭欣;多狀態(tài)系統(tǒng)故障樹的一種生成方法[J];系統(tǒng)工程學(xué)報;1998年04期
，本文編號：2242080
本文鏈接：http://sikaile.net/guanlilunwen/tongjijuecelunwen/2242080.html
最近更新
教材專著
