故障诊断中t/k诊断策略及遗传诊断算法研究

论文摘要

随着信息技术的高速发展,为了解决宇宙学、气象、流体力学、材料等重大科学应用领域的计算问题,大规模并行处理机向着高性能、大规模、多样性、多功能的方向发展。随之而来的一个问题就是系统的容错性和维护问题,特别是在应用于某些重要部门（如军事和金融）的多机系统中,故障的危害不仅可能涉及个人和生命财产,甚至可能关系国家和民族的安危。由于系统的规模越来越大,从中发现故障结点的工作也越来越繁重,花费也越来越高。随着芯片集成技术的提高,目前的处理结点一般都具备了一定的通信和处理能力,那么一个很自然的想法就是充分利用结点这些能力,让它们相互测试,然后再根据测试结果和拓扑结构等条件,最终得出正确的诊断结果,这就是系统级故障诊断的基本思想。这种方法不必使用专用设备测试,在不增加系统额外成本的情况下就可实现系统的快速自诊断。本文的工作就是研究如何采用系统级故障诊断的方法解决多机系统的故障诊断问题,主要围绕着增强超立方体的t/k-诊断度及诊断算法,局部扭立方体的t/k-诊断度,BC图的t/k-诊断算法,t-可诊断系统的遗传诊断算法等四方面展开,并分别得出了相应的结论。1.增强超立方体的t/k-诊断度（k≤2）及诊断算法。为了提高系统级故障诊断中的诊断度,人们以牺牲很小一部分结点不能正确诊断为代价,提出以t/k-诊断策略。增强超立方体是超立方体的一种变体,它在如直径、平均结点间距离、通信密度等方面均具有较好的性能。为了确认其诊断度,我们首先证明了当故障结点集|F| < 2n时,增强超立方体的最大连通分图的结点数≥2n– |F|– 1;当故障结点集|F| < 3n– 2时,增强超立方体的最大连通分图的结点数≥2n– |F|– 2。然后基于以上结论,证明了其t/2-诊断度为3n– 2,并给出了一个O（N log2N）的t/k-诊断算法（k≤2）。目前,上述成果尚未文献报导。2.局部扭曲立方体的t/k-诊断度。局部扭曲立方体是一种新的的变形立方体结构,它具有很多很好拓扑特性。我们证明局部扭曲立方体与超立方体有相同的t/k-诊断度。该个结论也在最近的一篇文章中被得出,但是我们的采用的证明方法与其是完全不同的,从另一个侧面证明了这个重要的结论。3.BC图的t/k-诊断算法。BC图是包括了超立方体和交叉立方体、M?bius立方体、扭曲立方体、局部扭曲立方体等多种变形立方体的一类图。人们证明了BC图的t/k-诊断度,但是未给出相应的t/k-诊断算法。对于结点总数为N的n维BC图,本文首先证明了当故障结点集|F| < （n + 1）n– （n + 1）（ n + 2）/2 + 1时,BC图的最

论文目录

• 摘要
• ABSTRACT
• 1 绪论
• 1.1 概述
• 1.1.1 多机系统的故障诊断
• 1.1.2 系统级故障诊断简介
• 1.2 系统级故障诊断研究内容
• 1.2.1 诊断模型
• 1.2.2 诊断方法
• 1.2.3 诊断范围
• 1.2.4 诊断目标
• 1.2.5 按状态值数量的模型分类
• 1.2.6 测试策略
• 1.2.7 故障诊断问题组合
• 1.3 已经取得的系统级故障诊断研究成果
• 1.3.1 针对特征问题的研究所取得的成果
• 1.3.2 针对可诊断问题的研究所取得的成果
• 1.3.3 针对诊断算法问题的研究所取得的成果
• 1.3.4 针对最优问题的研究所取得的成果
• 1.3.5 发展动态
• 1.4 与本文相关的前人已经完成的工作
• 1.4.1 基于t/k-故障诊断的研究概况
• 1.4.2 基于t-可诊断系统的遗传诊断算法的研究概况
• 1.5 本文的主要研究工作
• 1.5.1 主要研究工作简介
• 2 t/k-诊断策略引入
• 2.1 常用多机内联拓扑简介
• 2.1.1 超立方体
• 2.1.2 星图
• 2.1.3 格网
• 2.1.4 增强超立方体
• 2.1.5 扭曲立方体
• 2.1.6 M（o|¨）bius 立方体
• 2.2 t/k-诊断策略概述
• 3 增强超立方体的t/k-诊断度及诊断算法
• 3.1 增强超立方体介绍
• 3.2 预备知识
• 3.3 当故障结点小于≤2n-1时的最大连通分图
• 3.4 当故障结点小于3n-3时的最大连通分图
• 3.5 增强超立方体的高效诊断算法
• 3.6 本章小结
• 4 局部扭曲立方体的t/k-诊断度
• 4.1 局部扭曲立方体介绍
• 4.2 预备知识
• 4.3 局部扭曲立方体中k 个结点的最小邻点数
• 4.4 局部扭曲立方体的t/k-诊断度
• 4.5 本章小结
• 5 BC 图的t/k-诊断算法
• 5.1 BC 图简介
• 5.2 预备知识
• 5.3 存在故障结点时BC图的最大连通子图
• 5.4 诊断算法
• 5.5 仿真实例
• 5.6 本章小结
• 6 t-可诊断系统的遗传诊断算法
• 6.1 遗传算法简介
• 6.2 相关定义
• 6.3 Elhadef 的演化算法概略和不足
• 6.4 一个改进的演化算法
• 6.4.1 字串表示
• 6.4.2 初始种群
• 6.4.3 适应度函数
• 6.4.4 演化操作
• 6.5 算法实现与分析
• 6.5.1 算法分析
• 6.5.2 参数选择
• 6.5.3 算法比较
• 6.6 本章小结
• 7 总结与进一步工作
• 7.1 总结
• 7.2 进一步工作
• 致谢
• 参考文献
• 附录 A：攻读博士学位期间发表论文及参加科研情况
• 1. 发表论文:
• 2. 参加科研: