理论计算机科学电子笔记127(2005)45-60www.elsevier.com/locate/entcs动态故障树到随机Petri网的转换--图变换Daniele Codetta-Raiteri达尼埃莱·科德塔-雷泰里1,2Dipartimento diInformaticaUniversit`adiTorino Torino,Italy摘要本文提出了一种利用图转换规则实现动态故障树到随机Petri网的模型到模型转换的方法 动态故障树(DFT)用于复杂和大型系统的可靠性分析,并通过门来表示组件故障事件的组合或序列如何导致系统的故障。DFT需要的状态空间的解决方案,可以通过转换的DFT到一个随机Petri网:这一任务表示的图形转换规则,并应用到一个系统的关键词:动态故障树,随机Petri网,可靠性。1介绍量化安全或关键任务系统可靠性的一个指标是可靠性(R(t))[9]。作为时间t函数的系统可靠性是系统在区间(0,t)内执行所需功能的概率。系统的不可靠性(U(t))为:系统在时间t失效的概率,等于1−R(t)。的模型的构建是评估(不)可靠性或其他可靠性度量的典型方式。1D.Codetta-Raiteri由MIUR在FIRB PERF RBNE 019 N8 N资助下提供部分支持2电子邮件:codetta@di.unito.it1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2005.02.00546D. Codetta-Raiteri/Electronic Notes in Theoretical Computer Science 127(2005)45故障树(FT)[8]是一种广泛使用的随机模型,用于复杂大型系统的不可靠性分析; FT通过布尔门(逻辑端口)表示组件故障事件的组合如何确定子系统或整个系统的故障在该模型的标准版本中,组件故障事件被假设为统计独立;该假设允许使用组合方法[8]轻松计算系统的不可靠性,但这也限制了FT的建模能力。文献中提出的FT演化之一被称为动态故障树(DFT)[5](第2节)。用于FT的组合解决方案对于DFT是不够的,其中依赖性可以存在于事件或组件状态之间。DFT需要状态空间解;这意味着生成所有可能的系统状态和状态之间的随机转换;换句话说,我们需要获得系统的连续时间马尔可夫链(CTMC)[9从广义随机Petri网(GSPN)[1](第5节)生成CTMC的有效技术已经可用,并在几个工具中实现,如GreatSPN[4]。因此,一种实现DFT的状态空间解的方法包括将DFT转换为等价的GSPN;然后,可以从GSPN生成CTMC,并且在CTMC上计算系统的不可靠度。GSPN中DFT的转换可以归类为模型到模型的转换;这种转换可以通过图形转换规则[6](第6节)来表示,并通过使用GreatSPN实现的现有GSPN求解器实现DFT分析的软件工具(第4节)来实现。2DFT定义尽管它的名字,DFT是一个二分有向无环图(DAG),即使从图形的角度来看它看起来非常类似于树图; DFT的一个例子在图3中报告。节点可以是故障事件或门:故障事件由矩形表示,等效于布尔变量,其值最初为假,当故障事件发生时变为真;门通过弧连接到事件,并有几个输入事件和一个唯一的输出事件,分别连接在门的下方和上方DFT弧始终遵循电路逻辑方向:从输入事件到门,以及从门到其输出事件。由于这个原因,它们的方向没有用图形显示。由带圆圈的矩形表示的事件称为基本事件,D. Codetta-Raiteri/Electronic Notes in Theoretical Computer Science 127(2005)4547对应于系统的物理组件的故障事件;此类事件的发生时间是由概率分布支配的随机变量,通常是负指数分布,其参数λ是组件故障率。内部事件(由白色矩形表示)模拟子系统的故障,是门的输出。当门的输入事件的特定组合发生时,内部事件发生:组合的类型由门的类型确定虽然基本事件不能是任何门的输出,但有一个唯一的事件称为顶部事件(由黑色矩形表示),它只能是门的输出;顶部事件代表整个系统的失败一个事件节点可能属于几个子树,即一个事件节点可能属于几个子树。e.一个事件可以是几个门的输入。DFT可以包含布尔门和动态门。标准FT中引入了布尔门,并对布尔条件进行建模;它们是:• AND(图1.a):给定一组n(n≥ 2)个输入事件X1,. Xn和输出事件Y,如果每个输入事件都失败(真),则Y失败(真)。• OR(图1.b):给定一组n(n≥ 2)个输入事件X1.. Xn和输出事件Y,如果至少一个输入事件失败,则Y失败。• k OUT OF n(图1.c):给定一组n(n≥ 3)个输入事件X1. Xn和输出事件Y,如果至少有k(1