基于公共事件的二元决策图底事件排序方法研究

发布时间：2018-09-14 08:08

【摘要】：由于二元决策图(BDD)能够有效的表示布尔函数,使得它在许多领域都能广泛使用,包括数字芯片设计和系统可靠性分析。尤其是用于在系统可靠性领域来解决故障树时,二元决策图技术显示了较低的运算复杂度和高效率的优点。系统故障树分析,简称FTA(Fault Tree Analysis),是系统可靠性工程学的重要分支,是目前国内外公认的评价复杂系统可靠性与安全性的一种实用方法。故障树分析作为一种被广泛采用的方法,通常用来估算工业领域中各系统失效的概率,从而有效地评估系统风险水平。故障树分析是指获取导致系统失败的各种事件组合,这些事件组合也叫最小割集。当基本事件的故障率给定之后,系统失效的概率就能通过对这些最小割集的定量分析给出。但是,当故障树很大,并且包含重复事件时,采用传统的方法来获取最小割集就变得相当困难,极端情况下甚至不可解。正是为了解决这个问题,将BDD算法引入了系统可靠性领域。使用这种技术时,需要将故障树转化成相应的辑表达式,也即二元决策图形式。转化过程中,故障树的基本事件需要以一定的顺序排序。所选择的排序顺序将影响构造的BDD的节点数,从而影响这种方法的实际效果。但是,只有当能够转化为BDD并且BDD的大小有限时,这种分析方法才是有效的。所以,问题的关键在于在转化过程中对基本事件的排序。一个好的排序算法能够产生极为有效的分析过程,而一个糟糕的排序算法甚至不能够得出BDD。在故障树领域内,大多数BDD排序算法都基于Bryant提出的限制,这种限制是指,在将故障树转化为BDD的过程中,必须使基本事件的排序方式保持固定。尽管这种方式产生的BDD是唯一确定的,但是它并不能保证得出的BDD是最小的。在论文中,将应用渐进式排序算法来产生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.
【学位授予单位】：上海交通大学
【学位级别】：硕士
【学位授予年份】：2009
【分类号】：C934

【参考文献】