一种故障树结构匹配算法及其应用

doi:10.11896／j.issn.1002-137X.2018.09.033

计算机科学 ›› 2018, Vol. 45 ›› Issue (9): 202-206.doi: 10.11896／j.issn.1002-137X.2018.09.033

一种故障树结构匹配算法及其应用

岳鑫¹, 杜军威¹, 胡强¹, 王延平²

青岛科技大学信息科学与技术学院山东青岛266100¹
中国石化青岛安全工程研究院山东青岛266000²

收稿日期:2017-08-30 出版日期:2018-09-20 发布日期:2018-10-10
通讯作者: 杜军威(1974-),男,博士,教授,CCF会员,主要研究方向为智能软件工程与安全工程,E-mail:d-jw@163.com
作者简介:岳鑫(1992-),女,硕士生,CCF会员,主要研究方向为基于机器学习的安全分析技术;胡强(1982-),男,博士,讲师,主要研究方向为服务计算;王延平(1968-),男,高级工程师,主要研究方向为安全工程。
基金资助:
本文受国家自然科学基金(61273180),山东省自然基金项目(ZR2012FL17),山东省重点研发计划项目(2018GGX101052,2016GGX101031),山东省优秀中青年科学家科研奖励基金(BS2015DX010)资助。

Fault Tree Structure Matching Algorithm and Its Application

YUE Xin¹, DU Jun-wei¹, HU Qiang¹, WANG Yan-ping²

School of Information Science and Technology,Qingdao University of Science & Technology,Qingdao,Shandong 266100,China¹
Sinopec Research Institute of Safety Engineering,Qingdao,Shandong 266000,China²

Received:2017-08-30 Online:2018-09-20 Published:2018-10-10

摘要/Abstract

摘要： 面对以故障树形式汇集的大量历史事故案例,故障树结构匹配是借鉴历史经验在有限时间、人力和成本下实现对新事故准确和全面调查的有效手段。根据事件演化的时序和因果推理的结构特征,提出一种故障树结构匹配算法。通过构造故障树结构匹配的隐马尔可夫模型,利用维特比算法预测待匹配序列的最佳序列。实验数据显示,相对于基于节点的结构匹配算法,该算法在匹配的准确性、结构缺陷的检测效果等方面有显著提升。

关键词: 故障树, 结构匹配, 事故分析, 维特比算法, 隐马尔可夫模型

Abstract: A large number of fault trees have been designed and stored with the occurrence of numerous historical accident cases.Structure matching is an effective way to achieve accurate and comprehensive investigation of new accidents by using the existing fault trees with the limited time,manpower and cost.Based on the timing of event evolution and the structural features of causal reasoning,a fault tree structure matching algorithm was proposed.The hidden Markov model of fault tree is constructed and then the Viterbi algorithm is used to predict the optimal matching sequences.Compared with the node-based structure matching algorithm,this algorithm has significant improvement in the accuracy of matching and the detection of structural defects.

Key words: Accident analysis, Fault tree, Hidden Markov model, Structure matching, Viterbi algorithm

中图分类号:

TP399

岳鑫, 杜军威, 胡强, 王延平. 一种故障树结构匹配算法及其应用[J]. 计算机科学, 2018, 45(9): 202-206. https://doi.org/10.11896／j.issn.1002-137X.2018.09.033

YUE Xin, DU Jun-wei, HU Qiang, WANG Yan-ping. Fault Tree Structure Matching Algorithm and Its Application[J]. Computer Science, 2018, 45(9): 202-206. https://doi.org/10.11896／j.issn.1002-137X.2018.09.033

参考文献

[1]XU B F,HUANG Z Q,HU J,et al.Time Property Analysis Method for State/Event Fault Tree[J].Journal of Software,2015,26(2):427-446.(in Chinese)
徐丙凤,黄志球,胡军,等.一种状态事件故障树的时间特性分析方法[J].软件学报,2015,26(2):427-446.
[2]TANAKA H,FAN L T,LAI F S,et al.Fault-Tree Analysis by Fuzzy Probability[J].IEEE Transactions on Reliability,2009,R-32(5):453-457.
[3]CUI T J,MA Y D.Establishment of DSFT and determination of spatial distribution of probability of failure [J].Systems Engineering-Theory & Practice,2016,36(4):1081-1088.(in Chinese)
崔铁军,马云东.DSFT的建立及故障概率空间分布的确定[J].系统工程理论与实践,2016,36(4):1081-1088.
[4]ALIEE H,ZARANDI H R.A Fast and Accurate Fault Tree
Analysis Based on Stochastic Logic Implemented on Field-Programmable Gate Arrays[J].IEEE Transactions on Reliability,2013,62(1):13-22.
[5]NI J,TANG W,XING Y.A Simple Algebra for Fault Tree
Analysis of Static and Dynamic Systems[J].IEEE Transactions on Reliability,2013,62(4):846-861.
[6]LI Z F,REN Y,LIU L L,et al.Parallel algorithm for finding modules of large-scale coherent fault trees[J].Microelectronics Reliability,2015,55(9／10):1400-1403.
[7]DOOHWAN O H,WON WOO R O.High Performance Pattern Matching algorithm with Suffix Tree Structure for Network Security[J].Pattern matching,2014,51(6):110-116.
[8]LIU P.Tree structure matching pursuit based on Gaussian scale mixtures model[J].Proc Spie,2011,8135(1):813520-813520-8.
[9]ZHANG H W,JIE X F,DUAN Y Y,et al.A directed graph based subgraph matching query algorithm based on adaptive structure outline[J].Chinese Journal of Computers,2017,40(1):52-71.(in Chinese)
张海威,解晓芳,段媛媛,等.一种基于自适应结构概要的有向标签图子图匹配查询算法[J].计算机学报,2017,40(1):52-71.
[10]LI R Y,HONG L.A subgraph matching method based on inclusion degree[J].Journal of Software,2018,29(6):1792-1812.(in Chinese)
李瑞远,洪亮.一种基于包含度的子图匹配方法[J].软件学报,2018,29(6):1792-1812.
[11]LV Q,QIAO Y,ANSARI N,et al.Big Data Driven Hidden
Markov Model Based Individual Mobility Prediction at Points of Interest[J].IEEE Transactions on Vehicular Technology,2017,PP(99):1.
[12]CHOI K W,HOSSAIN E.Estimation of Primary User Parameters in Cognitive Radio Systems via Hidden Markov Model[J].IEEE Transactions on Signal Processing,2013,61(3):782-795.
[13]SOUALHI A,CLERC G,RAZIK H,et al.Hidden Markov
Models for the Prediction of Impending Faults[J].IEEE Tran-sactions on Industrial Electronics,2016,63(5):3271-3281.
[14]HAGENAUER J.Source-controlled channel decoding[J].IEEE Transactions on Communications,2002,43(9):2449-2457.
[15]NING A,LI X,WANG C.ASE Approach for Large Graphs
Matching[J].Information Technology Journal,2013,12(14):2969-2974.

相关文章 15

[1]	费星瑞, 谢逸. 基于HMM-NN的用户点击流识别 Click Streams Recognition for Web Users Based on HMM-NN 计算机科学, 2022, 49(7): 340-349. https://doi.org/10.11896/jsjkx.210600127
[2]	王欣, 向明月, 李思颖, 赵若成. 基于隐马尔可夫模型的铁路出行团体关系预测研究 Relation Prediction for Railway Travelling Group Based on Hidden Markov Model 计算机科学, 2022, 49(6A): 247-255. https://doi.org/10.11896/jsjkx.210500001
[3]	展万里, 胡军, 谷青范, 荣灏, 祁健, 董彦宏. 基于模型的故障树自动生成方法 Model-based Fault Tree Automatic Generation Method 计算机科学, 2021, 48(12): 159-169. https://doi.org/10.11896/jsjkx.200800177
[4]	魏德宾,杨鹏,杨力,石怀峰. 一种基于卫星网络的虚拟网络功能快速映射算法 Virtual Network Function Fast Mapping Algorithm over Satellite Network 计算机科学, 2020, 47(3): 248-254. https://doi.org/10.11896/jsjkx.190300383
[5]	张经, 杨健, 苏鹏. 语音识别中单音节识别研究综述 Survey of Monosyllable Recognition in Speech Recognition 计算机科学, 2020, 47(11A): 172-174. https://doi.org/10.11896/jsjkx.200200006
[6]	张成伟, 罗凤娥, 代毅. 基于数据挖掘的指定航班计划延误预测方法 Prediction Method of Flight Delay in Designated Flight Plan Based on Data Mining 计算机科学, 2020, 47(11A): 464-470. https://doi.org/10.11896/jsjkx.200600001
[7]	徐丙凤, 何高峰, 张黎宁. 基于状态事件故障树的信息物理融合系统风险建模 Risk Modeling for Cyber-physical Systems Based on State/Event Fault Trees 计算机科学, 2019, 46(5): 105-110. https://doi.org/10.11896/j.issn.1002-137X.2019.05.016
[8]	宋俊花, 魏欧. 基于线性时间算法的故障树模块扩展分解方法 Fault Tree Module Expansion Decomposition Method Based on Liner-time Algorithm 计算机科学, 2019, 46(1): 226-231. https://doi.org/10.11896／j.issn.1002-137X.2019.01.035
[9]	宫法明,朱朋海. 基于自适应隐马尔可夫模型的石油领域文档分词 Word Segmentation Based on Adaptive Hidden Markov Model in Oilfield 计算机科学, 2018, 45(6A): 97-100.
[10]	佟振明, 刘志鹏. 大型多人在线角色扮演游戏的下一地点预测 Next Place Prediction of Massively Multiplayer Online Role-playing Games 计算机科学, 2018, 45(11A): 453-457.
[11]	张晓策,燕雪峰,周勇. 一种基于动态故障树的SBDD方法 Method of SBDD Based on Dynamic Fault Tree 计算机科学, 2017, 44(9): 195-199. https://doi.org/10.11896/j.issn.1002-137X.2017.09.037
[12]	李东民,李静,林华锋. 基于故障树分析的嵌入式系统AADL模型可靠性分析方法 Reliability Analysis Method of Embedded System AADL Model Based on Fault Tree Analysis 计算机科学, 2017, 44(6): 182-188. https://doi.org/10.11896/j.issn.1002-137X.2017.06.031
[13]	崔铁军,李莎莎,王来贵. 完备与不完备背景关系中蕴含的系统功能结构分析 System Function Structure Analysis in Complete and Incomplete Background Relationship 计算机科学, 2017, 44(3): 268-273. https://doi.org/10.11896/j.issn.1002-137X.2017.03.055
[14]	黄鸣宇,魏欧,胡军. 基于故障配置的故障树生成 Fault Tree Generation Based on Fault Configuration 计算机科学, 2017, 44(2): 182-191. https://doi.org/10.11896/j.issn.1002-137X.2017.02.029
[15]	范亚琼,陈海燕. 基于时序关系的系统失效可达图生成方法 System Failure Reachability Graph Generation Method Based on Temporal Relation 计算机科学, 2017, 44(12): 169-174. https://doi.org/10.11896/j.issn.1002-137X.2017.12.032

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

一种故障树结构匹配算法及其应用

Fault Tree Structure Matching Algorithm and Its Application

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0