二元决策图ITE算法在.NET平台的实现与应用*

凌 牧，袁海文

（北京航空航天大学 自动化科学与电气工程学院，北京 100191）

二元决策图ITE算法在.NET平台的实现与应用*

凌 牧，袁海文

（北京航空航天大学 自动化科学与电气工程学院，北京 100191）

故障树作为系统可靠性分析的一种工具，在实际工程中已得到广泛应用。二元决策图作为常用的故障树分析法，通过其结构优势可快速得到故障树的不交化割集，通过分析割集集合确定系统失效集合以及计算系统失效概率等指标，确定系统可靠性。在.NET平台上使用 ITE算法实现故障树对二元决策图的转化，并在通用的 CAN总线监测诊断平台上实现，平台使用SQL Server作为知识库存储信息数据，以故障树信息和监测数据作为输入，实时对系统报警做出诊断。

二元决策图；故障树；ITE算法；CAN总线

0　引言

故障树分析法[1]是在实际工程应用中判断系统安全性与可靠性常用的方法，在理论分析方面已经发展得非常成熟，其研究多数集中于计算顶事件发生概率和分析系统薄弱环节的算法上，如文献[2]中的智能故障树诊断方法，按照计算所得底事件的故障率确定故障诊断的最优顺序，是典型的故障树静态分析方法。利用故障树法诊断实时诊断的系统也有一些研究成果，如文献[3]提出了一种实时预测故障的方法，引入底事件工作状态隶属度的概念，实时计算顶事件发生概率，对薄弱系统环节进行预测。但是这种方法仅能作为预测软件，并未达到实时诊断系统故障的效果。

二元决策图[4-5]（Binary Decision Diagram，BDD）本质上是变量集的布尔函数，这与故障树的割集[6]概念一致，由于BDD的结构规范，对比故障树节点更少，对于存储器空间占用少，有利于快速得出故障失效的不交化割集。

在实际工程应用中，现场操作人员虽然有现场数据，但对于复杂系统故障不一定具备诊断知识，因此很难现场准确诊断故障原因[7]。对于以上问题，本文提出了一种针对具有总线报警的实时监控系统，根据总线节点的报警代码，利用ITE算法将故障树转化为 BDD，在线实时诊断系统故障，对于分析系统故障模式，不断完善修正故障树有一定实际意义。

1　ITE算法及实现

1.1ITE算法基本原理

BDD是一种非闭环有向图，是一组变量的布尔表达式的图形化表示，在BDD中除了变量节点，还存在两种基本终结点“0”和“1”，从层数最高的“1”节点沿着所有节点的“1”脚回溯至BDD的顶节点，得到的变量集合之和即为该 BDD的布尔表达式。ITE(if-else-then)算子采用香农分解式的思想，将BDD按变量排序顺序依次展开，比传统二元决策图转换算法复杂度低，其表达式如式(1)所示。

采用式(1)算子对图 1故障树进行 BDD转换，假设其底事件排序为：abcd，那么依次得到故障树中各个门的ITE表达式如下：

由该故障树的顶事件（TOP）ITE表达式可得图1故障树的割集为：{ab, acd，cd}。

图1　故障树范例

1.2ITE算法实现

由于BDD特殊的结构形式，每个节点的结构都是相同的，适合使用递归方法实现。首先，对于ITE节点定义，如表1所示。

表1　ITE结构类itenode

从表1中可以看出形成BDD的ITE结构节点定义中使用了自引用的方式，其中它的nodehigh、nodelow属性也是itenode的类结构，这样使得在ITE节点连接时可以使用递归方式，形成的合并节点也都为相同结构。

使用 ITE算法将故障树转换为BDD主要有两个步骤：(1)对于门形成该门的 ITE结构；(2)将所有门的 ITE结构连接起来形成最终BDD。具体算法如表2、3所示。

表2中形成子门所有底事件的ITE函数将所有该门下的底事件连接形成ITE函数，由于在连接底事件的时候不存在两个ITE间的操作，只需编辑被连接节点的左右脚即可，如节点b需要连接节点a时，判断b节点父门的类型，若是“或”门，b节点的ITE结构中第2个元素中放入a节点，第3个元素置“0”；若是“与”门，b节点的ITE结构中第3个元素中放入a节点，第2个元素置“1”，如此循环至该门下所有节点均连接完成，最后返回该门所有底事件的ITE结构。

表3中ITE连接函数有3个变量，变量f、g表示2个待连接的ITE节点，变量op表示连接类型。两个 ITE节点连接主要分为3种情况：(1)f、g节点中有一个是“0/ 1”节点，根据op类别返回相应ITE节点；(2)计算表中已经有节点 f、g的相关操作，直接返回操作值；(3)以上 2种情况均不符合，则按照ITE结构递归连接。

对于整棵树的 ITE求解步骤为：(1)对所有门，求取其门下所有底事件的ITE合并结构；(2)从层数最多的门开始求解ITE，逐步替代其上层门的输入直到顶门。最终得到顶门的ITE结构就是该故障树的BDD形式。

表2　形成子门所有底事件的ITE函数

表3　ITE连接函数

2　算法实现平台

作为一个通用的嵌入式软件平台[9-10]，对于一个具有CAN总线结构的系统，合理设置故障报警节点，以所有故障节点作为故障树的顶事件建立多棵故障树，通过GUI界面将所有故障树信息录入软件平台。监控界面实时显示系统数据，当有报警信号时，操作人员可判读是否需要进行诊断，如要现场诊断，则进入诊断推理界面，根据报警信号找到相应故障树，采用 ITE算法，进行定性分析，确定发生故障的割集集合，给出结果及修复信息，系统结构如图2所示。

图2　系统结构

2.1故障树建模模块

在实际监控诊断工作开始之前，首先需要建立本系统的故障树模型。在建立故障树时，出于软件通用性考虑，将建立故障树与录入监测参数分开。首先将所有的系统参数录入，在建树的过程中直接选择相应底事件对应的参数，这样避免了不同底事件在依赖同样特征参数时的重复操作，提高了建树效率及准确性。

2.2数据库模块

数据库是平台系统存储故障树信息和原始系统数据的重要环节，如图3所示是系统的数据库结构。ADO.NET平台具有执行速度快、网络传输时间短的优点，适用于平台的分布式数据传输环境，基于以上原因，数据库采用 SQL Server软件平台开发[8]，与界面设计软件 Visual Studio有良好的接口。

图3　数据库结构

数据库主要存储了包括故障树信息、原始特征参数值(总线数据)、推理过程中得到的各种中间信息(割集)、报警信息和解决问题后输出结果信息(修复方法)等。总线数据分为报警信息和征兆参数值两部分。在导入故障树信息时，将各参数对应的CAN总线关联对象的ID、关联指针、对象长度一并导入，根据这些信息，系统可以将收到的数据帧转换为有意义的参数值。如图3中的WriteData_SQL表记录所有的总线原始数据，通过查找parameters表将原始二进制数据翻译成参数实际值提供给监控界面显示。

3　应用

3.1案例分析

车辆液压控制系统中包含液压机械设备、控制电路等复杂结构，发生故障的可能性也随之增大。某些故障不但会影响车辆正常运转，还可能会导致整个系统的故障。

如图4所示为某液压控制系统故障树，本文假设所有事件是二态的，即故障或正常。故障树信息如表4所示。本系统故障树特点在于底事件可分两类：人工判断类及自动判断类。其中，人工判断类底事件只对应一个特征参数，即需要人工判断该特征参数的状态。而对于自动判断类底事件，出于通用性考虑，为每个底事件预留3个特征参数，且3个特征参数之间的布尔关系可编辑，系统将在后台根据现场数据及用户给出的布尔关系判断该底事件是否发生。

图4　实验故障树

表4　故障树信息

顶事件为主泵异常，底事件主要分为电控回路故障、电缆故障、阀件故障等。对与每个底事件有相应的征兆，如X1电源故障，可通过电源电压U判断X1的状态；而有的底事件可能对应多个征兆，如X8阀件卡滞对应的征兆有控制电流I和系统压力P两个参数，这两个参数之间也存在布尔关系，当两个参数同时异常时X8故障。

3.2模拟环境拓扑结构

分别采用两台PC机作为现场环境模拟机和诊断机，其拓扑结构如图5所示。上位机模拟发送总线数据以及故障注入，下位机运行本诊断软件。

图5　模拟环境拓扑结构图

3.3实验结果分析

在模拟开始前，将上文故障树信息输入诊断软件，并将该系统的模拟总线数据输入上位机。注入液位高度故障数据，在升车过程进行到 20 s时注入报警帧，报警代码为101。接到报警后，软件提示是否立即诊断，如图6所示，即转入诊断推理界面，如图7所示，诊断结果为油液高度异常。

图6　监控界面

4　结论

本文将二元决策图ITE算法应用于实际系统，实现了在线系统故障诊断软件的设计仿真，根据仿真结果可得出：

(1)算法通用性强，可靠性高。二元决策图 ITE算法可应用于任何结构的系统，具有一定的工程意义。

图7　诊断推理界面

(2)诊断效率高，实时诊断故障原因并给出解决方案。

(3)良好的人机交互界面，完整的数据知识存储机制，对于完善已有故障树，从而提升整个系统的可靠性有一定的应用价值。

[1]王少萍.工程可靠性[M].北京：北京航空航天大学出版社，2000.

[2]倪绍徐，张裕芳，易宏，等.基于故障树的智能故障诊断方法[J].上海交通大学学报.2008(8).

[3]董豆豆，周忠宝.基于故障树的系统安全风险实时监测方法[J].国防科技大学学报.2006(28).

[4]张超.基于 BDD的动态故障树优化研究[D].西安：西北工业大学，2004.

[5]袁静，胡昌华，徐瑞，等.基于改进 BDD算法的导弹安控系统故障树仿真分析[J].系统仿真学报，2007(19).

[6]朱大奇，于盛林.基于故障树最小割集的故障诊断方法研究[J],数据采集与处理，2002，17(3).

[7]朱大奇，于盛林，陈小平.基于故障树分析及虚拟仪器的电子部件故障诊断技术研究[J].仪器仪表学报，2002，23(1).

[8]张勇.基于 ACCESS数据库的 CAN总线数据采集方法的设计与实现[J].制造业自动化.2011(21).

[9]JOANNE B D，KEVIN J S.Developing a low-cost highquality software tool for dynamic fault-tree analysis.IEEE Trans.Reliability，2000(40)：49-59.

[10]Zhou Zhiwei，Zhuang Ming.Design of a real-time fault diagnosis expert system for the EAST cryoplant.Fusion Engineering and Design，2012(87)：2002-2006.

Implementation and application of BDD using ITE algorithm on.NET platform

Ling Mu，Yuan Haiwen
(School of Automation Science and Electrical Engineering，Beihang University，Beijing 100191，China)

Fault tree analysis method is a useful reliability analysis tool，and it is used in applications of practical engineering widly.Binary Decision Diagram(BDD)is a common used fault tree analysis method,the disjoint cut sets of the fault tree can be quickly obtained by its structure advantage.The reliability indexes of the system such as the failure sets of the system and the failure probability of the system are determined by analyzing the collection of cut sets.An algorithm achieve transformation from fault tree to binary decision diagram is proposed.This algorithm is applied in a CAN-bus monitoring and diagnosis platform using SQL Server as information database,fault tree information and real-time bus data as input.

binary decision diagram；fault tree；ITE algorithm；CAN-bus

TP202.1

A

10.16157/j.issn.0258-7998.2016.01.027

国家自然科学基金（61273165）

2015-09-05)

凌牧（1987-），女，博士研究生，主要研究方向：系统可靠性分析、系统可靠性建模。

袁海文（1968-），男，教授，博士，主要研究方向：独立电源系统故障诊断与预测、检测技术与自动化装置。

中文引用格式：凌牧，袁海文.二元决策图ITE算法在.NET平台的实现与应用[J].电子技术应用，2016，42(1)：104-107.

英文引用格式：Ling Mu，Yuan Haiwen.Implementation and application of BDD using ITE algorithm on.NET platform[J].Application of Electronic Technique，2016，42(1)：104-107.