基于线性时间复杂度的故障树检测模块划分

基于线性时间复杂度的故障树检测模块划分

故障树分析技术最初由h.a.waton（196.196）在研究洲际导弹发射控制系统的过程中提出，该系统已经运行了近40年的历史，并在许多重要的安全领域广泛传播。缺陷树提供了系统是如何失败的一个清晰的解释。分析故障树的重要一点是，我们可以获得系统的不同缺陷的完整解释，并有效解决设计中的问题，但大失败树的分析需要更高的计算成本。解决此困难的方法是在故障树中检测独立模块，单独处理，然后从模块结果中综合提取整个故障树的分析结果。失败树的每个模块都是独立的子树。子树的基本事件不在失败树的其他地方。例如，在计算故障树的初始事件时计算故障树的概率（系统的不可靠度），并寻求最小片段集。有些研究已经提出了对故障树分块的几种方法,例如文献,这些方法把故障树的布尔表示式按照一定的规则重新化简为一个等价式,然后在这个式子中再寻找故障树的模块.这些方法的缺点是过程比较复杂.当故障树比较大时,故障树分块算法的复杂度显得更加重要,例如线性复杂度在实际应用中就会比二次性复杂度效率高得多.本文的故障树分块方法是根据文献所提出的用于检测一个图中具有强连接元素的算法衍变而来的,因为它只具有线性复杂度,因此效果很好.1事件模块的组合故障树一般分为具有耦合的和没有耦合的两类.任何事件只会在一个逻辑门的输入中出现的故障树就叫做没有耦合的故障树.相反,如果有的事件出现在多于一个逻辑门的输入中,则这样的故障树叫做具有耦合的故障树.故障树中的事件分为基本事件、中间事件和顶事件三类.图1描述了一个简单的具有耦合的故障树,该故障树中总共含有7个基本事件(E1～E7),分别描述系统中7个基本单元的失效(假设失效之间彼此独立).中间事件或者由基本事件通过逻辑门(与门、或门等)的组合来表示,或者由其它中间事件通过逻辑门的组合来表示,图1中共有6个中间事件(G1～G6).任何一个故障树中只有一个顶事件(T),其发生,即表示整个系统失效.实际上,一个故障树可以看作一个有向非循环图.其中所有的事件可以被看作有向图中的节点,事件之间的连接可看作有向图中的边.从故障树模块的定义来看,所有的基本事件和顶事件自然都是模块.为了简洁,本文以下所说的模块只是针对中间事件而言.2dflm遍历方法深度优先最左(DFLM-DepthFirstLeftMost)遍历是应用于有向图或无向图的最常用的一种搜索方法.假设初始状态是图中所有的节点未曾被访问,则DFLM遍历可从图中某个节点出发,先访问此节点,然后依次从此节点的相邻节点出发进行相应的DFLM遍历,直至图中所有和该节点有路径相通的节点都被访问到;若此时图中尚有节点未被访问到,则另选图中一个未曾被访问的节点作为始点,重复上述过程,直至图中所有节点都被访问到为止.当采用邻接表作为图的存储结构时,如果被遍历的图共含有n个节点和e条边,则DFLM遍历方法的时间复杂度与n+e呈线性关系,因此具有较高的效率.如果一个有向图中任意两个不同节点之间都存在连通的路径,则该有向图是强连通图.有向图中的极大强连通子图称作有向图的强连通分量.基于文献给出的寻找有向图中强连通分量的算法,通过对故障树对应的有向图进行两次DFLM遍历来检测其所含有的独立模块,在每次遍历时都相应刷新计数器中的内容.图1所示故障树对应的有向图如图2,以此为例说明DFLM遍历的执行过程.首先从顶点T出发进行搜索,在访问了T之后,选择其最左边的相邻节点G1.因为G1未曾被访问过,则从G1出发进行搜索.依次类推,接着从G2、G4、E1、E2出发进行搜索.在访问了E2之后,因E2没有任何子节点可访问,则搜索过程回溯到G4,进一步从G2的相邻右子节点G5继续开始搜索,直到搜索过程重新回到顶节点T为止.图2所示的有向图的DFML遍历过程见表1,给出了各遍历步骤依次访问的节点.由表1可得如下结论:(1)每个中间事件对应的节点至少被遍历两次,第一次是当从它的父节点向下遍历时,第二次是当从它的最右子节点返回时.(2)基本事件仅仅被遍历一次.(3)一个节点下面的子图不会被遍历第二次.例如G5下面的子图在从G2向下时被遍历,但当从G3遍历到G5时,G5下面的子图不再被遍历.3基于故障诊断的连接模块故障树分块的算法基于以下规则:假设G表示故障树的一个中间事件,ti是DFLM遍历过程中第i次访问G的时刻(i=1,2),则G是一个模块,当且仅当其所有子节点在遍历过程中只在t1和t2之间被访问.换句话说,如果一个节点的所有子节点没有在该节点的第一次访问之前被访问过,并且也没有在该节点的第二次访问之后被访问过,那么该节点就是一个模块.根据上述规则,从表1中可看出:G5是一个模块,因为E3和E4都在第8步(第一次访问G5的时刻)之后,并在第11步(第二次访问G5的时刻)之前被访问;G2不是一个模块,因为G5在第14步被访问,处于第二次访问G2的时刻(第12步)之后;G3也不是一个模块,因为G5在第8步被访问,处于第一次访问G3的时刻(第13步)之前.为了执行故障树的分块算法,需要:(1)定义访问的含义;(2)跟踪和区分每个节点的不同访问(第一次访问、第二次访问和最后一次访问);(3)得到每个节点的所有子节点的最小和最大访问时间,进行比较,进而判断该节点是否是一个模块.算法的执行过程中需要定义以下变量:(1)存放访问次数的变量,该变量保存在计数器中.(2)对已访问过的节点进行标记的阵列.(3)每个节点对应3个变量(tfv,tsv,tlv),分别表示第一次访问、第二次访问和最后一次访问该节点的时刻.(4)每个节点还对应2个极限变量(tmax,tmin),分别表示该节点的所有子节点的最大访问时刻和最小访问时刻.基于上述的变量定义,故障树的分块算法如下:(1)所有的变量初始化为0.(2)执行图的第一次DFLM遍历.每当有一个节点被访问,计数器变量加1,变量tfv、tsv、tlv的数值就是相应访问该节点时计数器变量的数值.对于基本事件,tfv和tsv的数值是相同的.(3)执行故障树的第二次DFLM遍历.对于每个节点,搜索其所有子节点中最小的tfv和最大的tlv,分别存放在变量tmin和tmax中.(4)判断节点是否为一个模块.如果tmin>tfv,并且tmax<tsv,则该节点是一个模块.图2两次DFLM遍历的结果如表2所示,只给出了中间事件对应各变量的数值.由表2,根据算法进行验证,得到图2含有的模块为:G1、G4、G5、G6.因此,就可对这些模块进行