实时系统的故障树最小割集求解

摘要

对于传统系统，实时系统的安全性和可靠性的分析缺乏类似的定量评价方法。故障树分析是已被广泛应用于许多行业的系统可靠性分析方法，然而，由于它的语义表达能力有限，因此不能够在实时系统中进行与复杂顺序依赖和时间约束有关的可靠性分析。文章将故障树的语义进行延伸，使复杂顺序依赖和时间约束可以够被故障树所表示，并使故障树分析方法应用到实时系统中。
　　但是，故障树的最小割集的不能由传统方法求解在延伸语义之后。针对此问题，文章采用时间自动机对实时系统的故障树进行建模，并在其基础上使用模型检验的方法求解最小割集。验证表明，扩展故障树模型后，模型检验得出时间自动机的最小割集可以适用于实时系统的安全性和可靠性分析。
　　本文首先阐述了本课题背景、课题目的、课题现状及课题思路，介绍了本课题的相关基础概念;然后描述了针对实时系统的特点所扩展的故障树语法与语义，提出了实时系统故障树最小割集的求解算法，针对扩展后的故障树语义，设计其转换算法使其能够转换成为时间自动，并在此基础上设计最小割集的求解算法，并在在故障树的转换算法和最小割集的求解算法上设计了优化算法;最后，使用实时系统建模及验证工具UPPAAL表示转换后的时间自动机以及进行性质检验，并使用C++语言编写辅助的枚举验证程序调用UPPAAL的验证工具，从而获得实时系统故障树的最小割集。
　　本文已经完成扩展故障树实时语义和求解实时系统故障树的最小割集的工作，为将来优化最小割集的求解算法奠定了基础。

目录

声明

摘要

第1章 绪论

1．1 课题背景

1．2 课题目的

1．3 课题研究现状

1．4 课题思路

1．5 论文结构

第2章 相关理论概念

2．1 传统故障树分析基本概念

2．1．1 故障树的基本单元

2．1．2 故障树建造的基本原则

2．1．3 最小割集基本概念

2．2 传统故障树最小割集求法

2．2．1 下行法

2．2．2 上行法

2．3 模型检验技术

2．3．1 时间自动机

2．3．2 时间计算树路逻辑

2．3．3 实时系统建模及验证工具UPPAAL

2．4 本章小结

第3章 传统故障树语义扩展

3．1 时间约束

3．1．1 或门上的时间约束

3．1．2 与门上的时间约束

3．1．3 其他门上的时间约束

3．2 复杂的顺序依赖扩展

3．3 本章小结

第4章 故障树的算法转换

4．1 传统故障树的转换算法

4．2 实时系统故障树的转换

4．3 本章小结

第5章 故障树最小割集求解及算法优化

5．1 UPPAAL验证求最小割集

5．2 故障树转换算法优化

5．3 最小割集求解算法优化

5．3．1 简单剪枝优化

5．3．2 双向广度优先搜索优化

5．3．3 限制层数的启发式搜索算法优化

5．3．4 部分最小割集优化

5．4 本章小结

第6章 结论与展望

6．1 课题结论

6．2 展望未来

参考文献

致谢