系统级故障诊断的研究现状与发展前景

宣恒农 苗春玲 赵冬 张润驰 刘田田

摘要：随着大数据时代的到来，人们对于计算机系统的稳定性要求日益增高，如何快速而准确地找出系统中的故障点，成为了人们的研究热题，对系统级故障诊断算法的研究逐渐受到了人们的重视。本文首先对现有的系统级故障诊断算法进行了分类，进而阐述了系统级故障诊断算法的近期主要研究成果，最后预测了该领域的未来研究方向与发展前景。

关键词：系统级故障诊断；诊断模型；集团诊断算法；方程诊断算法；智能诊断算法Achievement and prospects of system-level fault diagnosis

XuanHeng-nongMiaoChun-lingZhao-DongZhangRun-chiLiuTian-tian

(School of Information Engineering,Nanjing University of Finance and Economics,Nanjing,Jiangsu 210046,China)

Abstract:With the arrival of the era of big data, it requires the stability of any computer systems，and how to identify the faulty nodes in the system quickly and accurately has become a hot topic for researchers, system-level fault diagnosis algorithm research gradually attack people's attention.The paper firstly classify the existing system-level fault diagnosis algorithms,and then describes the main research results of the system-level fault diagnosis algorithm recently,finally predict the future prospects of the research and development in the field.

Key words:System-level fault diagnosis;diagnosis model;Group diagnostic algorithm;Equation diagnostic algorithm;I ntelligent diagnosis algorithm近年來，随着云计算、数据中心的日益普及和Internet的迅猛发展，在计算机带来极大便利的同时，其安全性和稳定性也越来越重要。如果计算机系统不能在规定的时间内稳定可靠地工作，将会造成巨大的损失，而保证这些系统的安全性与稳定性则是需要研究的关键问题之一。系统级故障诊断的方法通过测试、诊断，迅速确定系统中的故障机，是保证整个系统安全与稳定的非常重要之手段。

系统级故障诊断是由Preparata、Metze和Chien等人[1]首次提出。其大致思想是：利用网络中各节点的通信和处理能力进行相互测试，通过对测试结果的分析，从而找出故障点。对系统级故障诊断的研究是建立在故障模型基础之上的，若以“+”代表正常机，“-”代表故障机，“0”表示通过测试，“1”表示未通过测试，按照测试方式与故障症候的不同，故障模型主要分为以下四种：

PMC模型(基于测试的对称模型)

BGM模型(基于测试的非对称模型)

Chwa&Hakimi模型(基于比较的对称模型)

Malek模型(基于比较的非对称模型)

1系统级故障诊断算法的分类

1.1 按诊断精确度分类

根据诊断的目标精确度，可以把诊断算法分为精确性诊断算法和非精确性诊断算法。精确性诊断算法要求所有的故障结点机都能被诊断出来（完全诊断），并且要求所有被识别出来的故障结点的确是存在故障的；非精确性诊断算法允许系统中有一定数量的无故障结点被错误地诊断为故障结点，或存在少部分的故障点未被诊断出来。

1.2 按诊断步骤分类

根据在一次诊断过程中诊断出的系统故障结点数目，可以把系统级故障诊断算法分为一步故障诊断算法与顺序故障诊断算法。一步故障诊断算法要求通过结点机相互测试获得一个完整症候，一次性完全地识别出全部故障结点机；顺序故障诊断算法由多个诊断阶段构成，每个阶段，先诊断出一个或多个故障点，然后对诊断出的故障点进行修复或者更换，将被修复或者替换后的结点重新加入到系统中，让其参与下一阶段的诊断，如此反复，找到所有的故障结点。

1.3 按诊断方式分类

按诊断方式进行划分可以分为：集中式诊断算法和分布式诊断算法。集中式诊断算法要求除了系统内部互相测试之外，还需要把所有产生的测试结果送到系统外的一台高可靠机(即中心机)进一步处理，由该中心机根据症候来判断识别出系统中的故障结点机；分布式诊断算法的基本思想是：不需要一个绝对可靠的中心机，在进行诊断时，系统中的各个结点分别独立地对其余结点进行测试获得所需症候，然后独立地根据得到的症候进行诊断。

2系统级故障诊断发展现状

根据算法所用核心工具的不同，系统级故障诊断算法主要包括以下三大类：

2.1 基于图论原理的集团诊断算法

基于图论的诊断算法将测试症候矩阵与图论原理相结合，通过逻辑推导与图论运算，求出各单元的故障状态。鉴于实际系统中存在大可靠块的事实，张大方等人首次将图论中的极大独立点集理论用于系统级故障诊断领域，提出了集团的概念。集团诊断算法[2]的基本思想是：让系统中性质相同的结点聚合成一个块(进行集团运算)，再对聚合后的系统进行诊断，集团中的结点性质相同，要么都是正常机，要么都是故障机。

2.2 方程诊断算法

笔者等人[3]首次对基于互测的PMC故障模型提出“方程诊断”的有关概念，并且把这些模型等价地转换为一个代数方程组(也可以转换为一个代数方程)，而后通过运用“集团”和引入“绝对故障基”等工具，对一般情形下的各模型，找到了求全体相容故障模式的具体方法，即方程诊断算法.这种诊断算法既不必用“t可诊断性”作假设，也无需以“相信大多数”做前提，并且即使故障机数超过处理机总数的一半（甚至全体处理机均出现故障），依然能求出全部相容故障模式。PMC模型可表示为如下方程：

定理1 设A为一个n维的PMC故障模型，X为标

准向量库，则下列命题等价：

(i)x为A的一个PMC型解;

(ii)

(iii)

文献[4-6]分别提出将BGM、Chwa&Hakimi和Malek模型等价地转换成方程的形式进行诊断，方程表示形式分别如下：

BGM模型方程：

Chwa&Hakimi模型方程：

Malek模型方程：

随后，宣等人将t-可诊断性和方程算法相结合，提出了二分诊断算法[7]，将测试系统拆分为相对正常机集合和相对故障机集合，在对各个故障机集合采用自适应的的算法进行诊断。

2.3 基于现代群体智能算法的诊断算法

智能诊断算法往往具有自适应能力强、鲁棒性好、迭代求解速度快等特征，因此在实际领域应用广泛。

遺传算法 GA(Genetic Algorithm) 是一种借鉴生物界自然选择和群体基因遗传机理的随机和自适应优化的搜索算法，模拟了自然选择和遗传过程中发生的繁殖、杂交和突变现象。文献[8]首次用遗传算法解决系统级故障诊断问题。邓伟等人[9]通过分析Elhadef和Ayeb等人的不足之处，改进了种群的初始化方法，针对PMC模型提出结点状态与诊断图中一定症候相容时结点状态应满足的方程，然后设计基于该方程的适应度函数。使得对最终求得的适应度为1的解的即为问题的解，理论和实验仿真证明了改进后的算法大大优于Elhaedf等人的算法。

人工神经网络（artificial neural network）是一种应用类似大脑神经突触联接的结构进行信息处理的数学模型或计算模型。文献[10]提出了用Hopfield神经网络解决系统级故障诊断问题，取得了不错的效果；Mourad Elhadef和Amiya Nayak[11]首次将BP神经网络应用到Chwa&Hakimi模型下的系统级故障诊断。由于BP神经网络具有较好的自组织、自学习能力，因此算法的泛化性十分优越，同时诊断正确率很高，但其“学习--反馈--学习”的循环机制导致迭代次数较大，因此时间复杂度较高。

3结束语

随着未来网络的发展[12-13]，新型分布式大型网络系统的出现，对现有的各类诊断算法的兼容性也提出了挑战。下一步的研究方向包括如何进一步完善方程诊断算法、集团诊断算法以及各种智能诊断算法等，这些理论的发展将会不断完善系统级故障诊断技术。通过对多种不同诊断技术的融合，可将系统级故障诊断系统集成化，从而可充分发挥各自方法的优点，进一步提高算法的综合诊断能力。

[参考文献]

[1]Preparate F P,Metze G, Chien R T.On the connection assignment problem of diagnosable system[J].IEEE Transactions on Electronic Computer,1967,16(12):845-854.

[2]Zhang Dafang,Xie Gaogang,Min yinghua.Node grouping in system-level fault diagnosis[J].Journal of Computer Science & Technology,2001,24(5):474-479.

[3]宣恒农,张大方,张明.PMC故障模型的方程诊断[J].电子学报，2003,05:694-697.

[4]宣恒农.用方程表示BGM故障模型的方法研究[J].计算机工程与应用，2001,23:93-94.

[5]宣恒农,张明,张大方,张廷选.Chwa & Hakimi故障模型方程诊断的理论基础[J].计算机应用,2003,04:16-18.

[6]文学志,宣恒农.Malek故障模型的方程诊断算法设计[J].计算机工程与应用,2005,29:39-41+60.

[7]宣恒农,何涛,许宏,孙明明.基于Chwa &Hakimi故障模型的二分诊断算法[J].计算机工程与应用,2010,05:66-68.

[8]Elhadef M,Ayeb B.An evolutionary algorithm for identifying faults in t-diagnosable systems[C].Reliable Distributed Systems,2000. SRDS-2000.Proceedings The 19th IEEE Symposium on.IEEE,2000: 74-83.

[9]邓伟,杨小帆,吴中福.面向系统级故障诊断的高效遗传算法[J].计算机学报,2007,07:1115-1124.

[10]Elhadef, M."Solving the PMC-Based System-Level Fault Diagnosis Problem Using Hopfield Neural Networks",Advanced InFORmation Networking and Applications (AINA),2011 IEEE.