一种基于GO图的故障树自动生成方法

宛伟健，黄志球，沈国华，尹小花

(南京航空航天大学计算机科学与技术学院，南京211106)

(南京航空航天大学高安全系统的软件开发与验证技术工业和信息化部重点实验室，南京211106)

E-mail:wanweijianxs@163.com

1 引言

随着现代科学技术的不断发展，出现了大量多功能的复杂系统.复杂系统有软硬件结合和能执行多种功能任务的特性.大规模的复杂系统给人们带来巨大的经济利益，但是一旦出现故障则需要及时将故障排除，否则就会造成重大损失.FTA作为经典的安全性分析方法，被广泛应用于不同的领域［1-5］，在系统实现过程中加强设备的可靠性设计以及在后期系统运用中实现故障的全面诊断、快速排查和维护具有重要意义.然而，传统故障树通常基于分析师的经验建立，需要彻底了解系统功能原理并正确转化为布尔逻辑，对于简单系统，可以通过手动构建故障树，但是随着系统复杂度的提升，人工方式已基本无法构造和修改故障树［6］.

GO法［7-9］(GO Method)最早于60年代中期由凯曼科学公司(Kaman Sciences Corporation)开发出来，应用于国防和航天工业领域，它应用GO图模型来计算系统的可靠性和可用性，适用于有时序和实际物流的系统可靠性分析，由于其与系统功能原理图的相似性，通常易于构建［10］，且原理图中的构件与GO图的操作符之间常常有非常明显的一一对应关系，不会变得像故障树模型那样十分膨胀［11］.基于GO图的故障树生成技术为解决大型复杂系统故障树生成问题提供了一种新思路.本文基于GO图，提出一种故障树的自动生成方法，首先，定义操作符到故障树节点的语义映射规则;然后，根据定义的语义映射规则，提出一个GO图到故障树的自动转换算法，并对生成的故障树进行简化，删除冗余的逻辑门.最后通过一个数控机床液压系统案例说明转换的详细过程，并分别与手工构建的故障树进行定性分析，通过定性分析的结果对比，发现该故障树与手工建立故障树逻辑相同，验证了该方法的正确性与可行性，为大型复杂系统的故障树自动构建方法提供了一种新思路.

本文章节安排如下:第二部分介绍由GO图自动生成故障树的步骤以及GO图理论;第三部分详细介绍了GO图到故障树的自动生成方法，主要包括操作符到故障树节点的语义映射规则、GO图到原始故障树的转换和对原始故障树的化简;第四部分通过对数控机床液压系统的故障树自动构建案例分析验证了所提方法的合理性;第五部分为相关工作对比，最后为总结与展望.

2 基于GO图的故障树自动生成步骤以及GO图理论

基于GO图生成故障树的研究较少，本文通过定义被工业界广泛应用的操作符到故障树的映射规则，并提出自动转换算法，实现自动化转换.由GO图导出故障树的方法主要包括三步骤，如图1所示，分别为建立操作符到故障树节点的语义映射规则、根据自动转换算法生成原始故障树和原始故障树的化简，删除冗余的逻辑门.

图1 由GO图自动生成故障树的步骤Fig.1 Steps to automatically generate a fault tree from a GO map

GO方法作为一种以输出成功为导向的系统概率分析技术，适用于对具有多态和时序特征的复杂系统进行建模，特别是对具有流动或过程的系统(例如液体流动、电流和气流等)［12］.用GO方法对复杂系统进行建模，即生成GO图，GO图由操作符和信号组成:操作符描述系统中的功能部件;信号描述功能部件间的实际物流或信号.GO图是通过将系统原理框图或电路图等模型中的功能部件和物流、信号按照规则转换为操作符和信号获得，人为因素的影响较小.

GO图共有17种操作符，可分为功能操作符和逻辑操作符.逻辑操作符表示不包括任何自身状态的逻辑运算，功能操作符不仅表示逻辑关系，还包括自身状态.在GO图的17种逻辑操作符中，类型1，2，3，5，6，10、11 和 15 被广泛应用于实际工程中［13］.其中类型 1、3、5、6 为功能操作符，类型 2、10、11、15为逻辑操作符.本文对上述被广泛应用于实际工程中的操作符进行分析，定义操作符到故障树节点的映射规则，操作符类型7、8、16、17表达的逻辑含义可以通过上述操作符组合表达，生成相应的故障树节点，其他5类操作符无法直接的定义其到故障树节点的语义映射规则，且由于其在工业实践中并不常见，本文将不再赘述.

操作符类型1是一个两状态单元，具有一个输入和两个操作状态(成功或失效);类型2是包含N个输入信号的逻辑OR门;类型3是一个触发生成器，有三个输入:过早、成功、失效;类型5是信号发生器;类型6代表有信号而导通的元件，表示当次级致动信号到来且主输入信号同时存在时产生输出［7`］;类型10是包含N个输入信号的AND门;类型11用来对N个单元中有K个发生的情况进行建模;类型15是数值/概率门，根据输入的值来控制输出.本文考虑的GO图到故障树的转换中，生成的故障树基本事件只有成功和失效两种情况，且不考虑修复和时间延迟属性.

3 基于GO图的故障树生成方法

本节主要介绍如何从GO图自动生成故障树，根据图1可知，基于GO图的故障树生成方法可分为三个步骤进行描述，本节将分三小节展开，每小节对应一个步骤进行详细描述.

3.1 操作符到故障树节点的语义映射规则定义

本文对工业界中被广泛应用的操作符类型1、2、3、5、6、10、11和15定义语义映射规则.如前文所述，将上述操作符进行分类，并分别定义语义映射规则.其中类型1、3、5、6为功能操作符，其余均为逻辑操作符.本文仅考虑故障树事件具有工作(成功)和失效两种状态，且事件不可修复.

3.1.1 功能操作符的映射规则

功能操作符的映射规则包括图形转换和数据转换.在故障树分析中只考虑事件的故障状态，因此，对于生成的故障树基本事件，我们只选择功能运算符的故障状态(SF，StateFail)进行分析.

1)对于操作符类型1，输入信号的状态表示为:S∈(0，1，…，N)，操作符自身的状态表示为:C∈(1，2)，输出信号的状态表示为:R∈(0，1，…，N).在GO方法中，每个状态的最大值表示故障状态，因此，当S为状态N时，表示输入信号为故障状态，我们用SF表示，同理，我们用CF和RF分别表示操作符自身和输出信号的故障状态.所以对应于故障树逻辑，操作符类型1到故障树节点的映射规则如图2(a)所示，当输入信号处于状态SF或者操作符本身处于状态CF时，输出信号将会处于故障状态RF，即RF=SF∨CF.

2)操作符类型3与操作符类型1类似，不同之处在于操作符自身状态数量，操作符类型3自身状态包含预定义状态，其故障机理与操作符类型1相同，输入信号的状态为:S∈(0，1，…，N)，操作符自身的状态为:C∈(0，1，2)，输出信号的状态为:R∈(0，1，…，N).与故障树对应的故障机理为:当输入信号处于状态SF或者操作符本身处于状态CF时，输出信号处于故障状态RF，即RF=SF∨CF，映射规则如图2(b)所示.

3)操作符5是GO图的起始运算符，操作符自身状态包含N 个状态，可表示为:C∈(0，1，…，N)，输出信号表示为:R∈(0，1，…，N).用CF代表操作符本身的故障状态，RF表示输出信号的故障状态，其映射规则如图2(c)所示，即RF=CF.

4)操作符6通常用于模拟输出只能由两个输入信号触发的特定组件.两个输入信号分别记为{S1，S2}，它们的状态值相同，记为 Si∈(0，1，…，N)(i=1，2)，操作符自身状态为:C∈(0，1，2)，输出信号状态为:R∈(0，1，…，N).由于输入信号的数量不为1，所以将输入信号的故障状态记为:SiF(i=1，2)，CF代表操作符本身的故障状态，RF表示输出信号的故障状态.操作符6的映射规则如图2(d)所示，其故障机理为:当输入信号中的任意一个处于故障状态，或者操作符自身处于故障状态，将会导致输出信号处于故障状态，可表示为:RF=S1F∨S2F∨CF.

图2 操作符的映射规则Fig.2 Mapping rule of operator

3.1.2 逻辑操作符的映射规则

GO图是面向成功的模型，而故障树是面向故障的模型，因此，逻辑OR和逻辑AND在转换过程中要做相应的转换.以下分别介绍逻辑操作符2、10、11和15的语义映射规则.

1)操作符类型2是OR门，将其转换成对应的故障树AND门，输入信号代表相应的AND门的输入事件.其映射规则如图2(e)所示.

2)操作符类型10是AND门，相应的将其转换成故障树的OR门，输入信号对应OR门的输入事件.映射规则如图2(f)所示.

3)操作符类型11是选举门，当K=M时，可以将其装换成对应的故障树选举门，且故障树选举门的K=N－M+1，相似地，输入信号对应故障树选举门地输入事件.映射规则如图2(g)所示.

4)操作符类型15是限制概率门，根据其构造原理，当输入信号不处于故障状态时，输出信号为故障状态，可以对应的将其映射到故障树非门，同样地，用SF表示输入信号的故障状态，用RF表示输出信号的故障状态，映射规则如图2(h)所示.

3.2 GO图到原始故障树的自动转换算法

根据定义好的语义映射规则，提出一个GO图到故障树的自动转换算法，完成GO图到故障树的自动转换.

GO图由操作符和边组成，可以将其形式化表示为如下二元组:G=(V，E)，其中操作符用节点来表示，所以GO图中所有操作符可表示为节点集合如下:V={v1，v2，…，vn}，表示该GO图中共有n个操作符.操作符之间通过边表示，GO图中边集定义如下:E={e1，e2，…，em}，表示图中共有m条边.

由于GO图通常基于流的方式对系统建模，因此，GO图是个有向无环连通图.可以根据GO图是有向无环图的性质，利用反向推理的方式，从终节点开始，逆着边的传播方向，提出自动转换算法，逐步将整个GO图转换成故障树.转换算法思想可分为以下3个步骤实现:

步骤1.从终节点vj处开始，调用负责根据映射规则将终结点操作符节点转换成相应的故障树节点的子函数，实现终节点vj到对应故障树节点的转换;

步骤2.然后根据边的传递关系，找到指向节点vj的相邻节点vi(0≤i＜n)，调用转换子函数，实现该节点到对应故障树节点的转换，并将节点vi存入辅助栈Stack中;重复执行步骤2，直到vi为空，即找到所有的相邻节点.实现所有邻接节点的转换并将所有邻接结点存入辅助栈Stack中，跳转到步骤3;

步骤3.对辅助栈Stack做出栈操作，出栈节点记为vk，并令vj=vk，执行步骤2;若Statck为空，则结束程序.

至此完成对GO图所有的节点的转换，生成相应的原始故障树.

具体的算法设计如下，首先对GO图进行预处理操作，GO图中每个操作符节点作为一个类，包含结点编号v.number和节点类型v.type，若节点为功能操作符，则还应包含节点自身状态v.item;然后将所有边通过 Map集合存储，即Map＜vstart，vend＞.然而，Map集合中键值不能重复存储，但是在GO图中存在一个节点指向多个节点的情况，所以通过重写hasCode()方法和equals()方法实现一个节点指向多个节点情况的边存储.并将单个节点转换成对应故障树节点单独封装成一个函数，可以根据输入操作符节点的类型完成相应转换.具体算法如下:

算法1中，根据输入GO图、边存储Map集合和GO图终结节点，调用CreatTree创建整棵故障树的根节点，然后调用CreatSubTree创建该根节点的子节点，依次从根节点向下生成子节点.

算法2中，根据传入的边集合Map和根节点生成子故障树.利用辅助栈S帮助完成遍历，每遍历到一个父节点相连的相邻子节点，根据映射规则将其转换成相应的故障节点，并压入栈S中存储，待该父节点所有的相邻子节点转换完成后，出栈并重新调用该函数，继续遍历GO图，当辅助栈S为空时表示已经遍历完连通有向图GO图的所有节点，完成GO图到故障树的转换.该算法为递归算法，依据顶事件到初始结点的个数N，最大分叉数为K，该递归函数的最大时间复杂度为O(n).

3.3 原始故障树的化简规则

使用上述自动转换算法生成的故障树中会存在大量的冗余逻辑门，将其称为原始故障树，如图6(a)所示.因此，需要在不改变逻辑关系的基础上简化原始故障树，删除冗余的逻辑门.主要采取压缩规则，把紧随其后相同类别的逻辑门压缩成一个单独的逻辑门，获得AND门和OR门交替序列的结构.如图3所示.

图3 压缩原则示例Fig.3 Example of compression principle

4 机床液压系统案例分析

本章针对文献［14］中机床液压系统案例进行分析，详细说明GO图到故障树的转换，并对生成的故障树进行化简，最后与文献［14］中的故障树模型进行对比，通过定性分析，由所求割集相同，可见GO图自动生成的故障树与手动建立得到的故障树等效，验证了该文所提方法的正确性与可靠性行.

4.1 机床液压系统GO图到故障树的转换

文献［14］首先根据故障树原理和方法，通过逐层深入分析顶事件、中间事件、底事件，通过手工建树的方式建立某加工中心机床液压系统的故障树模型，如图4所示.其中各个符号表示的事件含义为:T为机床液压系统故障;H1为机床液压系统压力不足;H2为机床液压系统流量不稳定;H3为溢流阀调压错误或磨损;H4为油箱缺油;H5为液压缸、阀、管接头、压力连接头等密封元件损坏导致的泄露;H6为泵故障;H7为阀节流口磨损;H8为过滤网、阀和管道堵塞;H9为流量调整阀或方向阀故障;H10为过滤网堵塞;H11为阀或管道杜塞;X1为液压油有固体颗粒或不干净;X2为人为错误;X3为邮箱漏油;X4为人为错误;X5为液压油有固体颗粒导致的磨损;X6为油冷装置故障;X7为液压油生化腐蚀金属壁;X8为压力过大损坏密封件;X9为泵疲劳损坏，X10为电气接线错误;X11为液压油有固体颗粒磨损;X12为液压油不干净;X13为过滤网时间过长未更换;X14为液压油流速过慢;X15为液压油有杂质;X16为锈蚀或固体颗粒卡死;X17为电气系统故障;X18为人为错误.

图4 某加工中心机床液压系统故障树Fig.4 Hydraulic system fault tree of a machining center

根据文献［14］，机床液压系统的GO图如图5所示，可以看出机床液压系统GO图包含三种基本类型的操作符，分别为操作符类型2或门操作符，操作符类型5信号发生器操作符和操作符类型10与门操作符.利用算法1和算法2可以将该GO图自动化生成对应的机床液压系统故障树，先对GO图进行预处理，将GO图中所有的边存储到Map＜vstart，vend＞(0＜start＜28，1＜end＜29)中，并初始化辅助栈 Stack，其具体生成过程如下:

步骤1.首先从终点操作符10-10开始，将操作符10-10记为vj=v10-10，调用算法1，初始化故障树生成的顶事件T和其相连的逻辑门，根据映射规则，操作符10-10对应于故障树的OR门，OR门名称记为10-10;

步骤2.然后调用算法2，利用反向推理的方式，遍历Map中所有的边，找到vend=v10-10的边，并将对应的vstart节点转换成相应的故障树节点，然后将其压入辅助栈Statck中，本例中遍历Map发现v10-8、v10-9指向v10-10节点，所以根据转换规则将v10-8、v10-9转换成相应的故障树节点，分别将v10-8、v10-9转换成OR门，且分别将两个OR门记为10-8、10-9，然后将操作符节点v10-8、v10-9压入辅助栈，然后判断是否已经将所有与vend=v10-10相连的vstart节点压栈，如果已经全部压入栈，则转向步骤3;否则，继续遍历，直到将所有与vend=v10-10相连的vstart节点压入辅助栈Stack中;

图5 机床液压系统GO图Fig.5 Machine tool hydraulic system GO map

步骤3.将辅助栈栈顶元素vk出栈，并令vj=vk，该例中，首先将v10-8出栈，令vj=v10-8，然后重复执行步骤2，遍历Map中所有的边，找出所有与vend=v10-8节点对应的vstart节点，根据转换规则将其转换成对应的故障树节点，本例中，可以找到所有与 vend=v10-8节点相连的节点为 v10-1、v10-2、v10-3、v10-4，根据转换规则，都是类型10的操作符，分别将其转换成OR门，记为 10-1、10-2、10-3、10-4，然后都压入辅助栈 Stack 中;若此时辅助栈Stack为空，则生成过程结束，完成GO图到故障树的转换，否则，重复步骤3;

通过执行上述三个步骤，可以生成机床液压系统的原始故障树如图6(a)所示，再通过压缩规则约减冗余的逻辑门可以得到化简后的故障树如图6(b)所示.

4.2 机床液压系统故障树定性对比分析

对图6(b)所示故障树进行定性分析，采用下行法，即Fuseell-vesely 算法［15］进行分析，易得最小割集为:{C1}、{C2}、{C3}、{C4}、{C5}、{C6}、{C7}、{C8}、{C9}、{C10}、{C11}、{C12，C13}、{C14，C15}、{C16}、{C7}、{C8}，对图4所示故障树进行定性分析，得到其最小割集为{X1}、{X2}、{X3}、{X4}、{X5}、{X6}、{X7}、{X8}、{X9}、{X10}、{X11}、{X12，X13}、{X14，X15}、{X16}、{X7}、{X8}，其中Xi与Ci代表的事件含义相同，故两个故障树最小割集相同，即由GO图自动生成化简后的故障树与普通FTA法得到的故障树等效.验证了该方法的正确性和可行性.

5 相关工作

图6 基于GO图自动生成的故障树((a)未化简的原始故障树;(b)化简后的故障树)Fig.6 Fault tree automatically generated based on GO map

故障树的自动生成技术一直是基于故障树的系统安全性与可靠性分析领域的研究热点之一，文献［16］基于已经建立的矩阵模型开发了一种生成故障树的方法，该方法提高了初步故障树分析的效率，但是矩阵模型的建立较为复杂;文献［17］利用Altarica模型生成故障树，Altarica模型在设计中自带故障信息，但是该方法没有转换规则，需要手工配置实现故障树的生成.文献［18］提出利用UML顺序图、用例图和结构图生成故障树，输入UML结构行为信息，利用混合的转换语言ATL实现故障树的生成，但是转换语言的实现比较复杂.因此，上述故障树构建方法，要么构建过程复杂、不能实现完全的自动化构建，要么生成故障树时基于的模型建立过程复杂.众所周知，GO图直接从系统原理图、流程图或工程图中建立，与系统原理具有很高的相似性，可以很容易的构建GO模型，而且GO图是以输出成功为导向的系统可靠性分析技术，其操作符可以和故障树节点相互映射，可以实现基于GO图的完全自动化的故障树生成.但是，基于GO模型的故障树自动生成方法研究很少，文献［10］提出了部分GO图操作符到故障树节点的映射规则，但对有些被广泛应用于工程中的操作符并未描述，例如操作符类型11和类型15，且未提出GO图到故障树的自动转换算法，对生成原始故障树的化简规则也没有进行描述.文献［13］定义了工业界常用的操作符到故障树节点的转换，但是并未提出明确的自动转换算法且对生成的案例并未进行正确性验证.本文重新定义被广泛应用于实际工程中的操作符到故障树的语义映射规则，并提出自动转换算法，实现GO图到故障树的自动化转换，且明确了故障树的约减规则，最后通过机床液压系统案例分析并验证了该方法的合理性和有效性.

6 结束语

本文所提的基于GO图的故障树自动生成方法规范并简化了故障树的建立过程.该方法以GO图模型为出发点，减弱了建树过程中人为因素的影响，定义了GO图操作符到故障树节点的映射规则，并提出了一套自动转换算法，将FTA和GO法结合在一起，增强了对系统可靠性的分析能力;同时解决了针对大型复杂系统的故障树建模，传统基于手工构建的方式存在的建模周期长且对建模者要求较高、容易发生遗漏和错误等问题.机床液压系统的例子表明由GO图自动生成的故障树与传统方法构建的故障树在逻辑上等效，验证了该方法的正确性与可行性.本文通过清晰的步骤来说明该方法，这有助于在计算机上实现该文所提方法，本文未来的工作主要集中在设计完善相应的工具，将所提方法融入工具中.

但是本文只针对工业界中常用的8种GO图操作符定义其到故障树的语义映射规则，其余9种操作符，操作符类型7、8、16、17可以通过已经论述的8种操作符进行组合表达，但是另外5种操作符无法直接定义其到故障树节点的语义映射规则，本文的未来工作将对此继续进行研究，完成所有GO图操作符到故障树节点的转换.