曾媛

摘 要： BGM的方式诊断，当故障节点测试故障节点时，结果为1，但是PMC的方式诊断，当故障节点测试故障节点时，结果不确定。本文以条件诊断系统为研究对象，首先对条件诊断系统的互测PMC 模型进行研究，把传统诊断系统的有向图表达式 G（ V，E） 转换成互测有向图表达式 G（ F，T，M，HF） ，然后对条件诊断互测有向图表达式中相互关联的定理进行研究，最后提出一种基于互测 PMC 模型的条件诊断算法，并证明在该算法下，BGM测试一块网络故障与否的结论与PMC测试结果一致。

关键词： 网络；BGM；PMC；条件成立

1.引言

近年来随着互联网信息技术的不断更新和发展，多处理器系统中可能存在着成百上千个处理器，在运行过程中，这些处理器会出现各种故障，这些故障的出现会对系统正常运行产生影响。因此如何对这类系统级故障进行准确的诊断，在这种需求下“系统级故障诊断”课型，PMC模型，这是用他们三人的姓名首字母来命名的。该系统设计的目的是保证多处题在1967年正式被Preparata、Metze 和Chien 提出，这三人共同提出了一个经典的故障诊断模理器系统或者 VLSI/WSI计算系统的正常运行，在出现故障时及时进行判断，找出故障处理器的过程。PMC模型中，每个节点u和节点v都可以通过向边连接进行检测处理，通常我们称u点为测试节点处理器，v称之为被测节点处理器。当用一个正确的节点来检测另一个正确的节点时，得到的检测结果被认为是正确的通常用0表示。当用一个正确的节点来测试一个错误的节点时，得到的结果即为错误的通常用1表示。在处理器被测出错误，其后续的测试的结果必然别认为是有错误的。在此之后很多学者对PMC模型进行了更深入的研究，在PMC模型基础上了研究出了如BGM、MM等模型。

BGM的方式诊断，当故障节点测试故障节点时，结果为1，但是PMC的方式诊断，当故障节点测试故障节点时，结果不确定；本研究主要目的是找出条件，证明在条件之下，BGM测试一块网络故障与否的结论与PMC测试结果一致。

2.定理与引理

t故障可诊断系统是目前较为常用的系统处理器诊断系统，它指的是当在有n个节点诊断系统中，出现故障节点数不超过t个时，都可以不回置的被诊断出来，具有这种特点的系统被称之为t可诊断系统。它有3个定理，以下我们来进行简单的介绍。

定理一 ：在 t故障诊断系统中，系统有向图的总结点个数为n2t +1。

定理二：在t故障诊断系统中，每个系统结点都被t个结点测试。可以理解为f1和f2可区分性，当存在此种链接时，即可表示为f1和f2是可区分。

定理三： 如该系统是t 故障可诊断系统，那么在f1和f2这对故障模式中，就存在有|f1|、|f2| ≤t，若 f1≠f2，就一定会存在一个V-（ f1∪f2） 的结点到 f1Δf2（f1Δf2=？（ f1- f2） ∪（ f2-f1） ） 的存在一个结点有边链接。如图1所示。

图1 F1F2故障模式示意图

引理一： 在互测 PMC 模型中，如果（ u，v） ∈E，存在着σ（ u，v） =0，σ（ v，u） = 1，那么可以确定结点 u 是错误结点，如表 1 所示，同理如果存在σ（ u，v） = 1，σ（ v，u） = 0，那么可以确定结点 v 是错误结点。

证明反证法，如果存在σ（ u，v） =0，σ（ v，u） =1，那么我们就可以得出，如果已经确定u是正确的，根据PMC模型，当σ（ v，u） =1我们可知v点必定是一个错误结点，当σ（ v，u） =0，则可判定为v点是必定是一个正确的结点。所以v结点是错误的，可以反证出σ（？u，v）= 1，当v是正确的，也可反证出σ（ u，v） =0。

这与已知条件σ（ u，v） = 0 相矛盾，所以假设错误.同理可以证明如果存在着σ（ u，v） = 1，σ（ v，u） = 0，那么结点 v 是错误结点，所以引理 1 可证。

引理二： 在互测 PMC 模型中，如果（ u，v） ∈E，当σ（ u，v） = 0，σ（ v，u） = 0，表示为u点和v结点要么都是正确的，要么都是错误的。

证明反证法，假设存在σ（u，v） =0，σ（ v，u） =0，如果结点v和u两个中间一个是正确的一个是错误的，根据PMC模型σ（ u，v） =1的性质，这与给出的已知条件是σ（ u，v）=0 ，σ（ v，u） =0存在矛盾，所以推出该假设是错误的。可推出引理 2 是正确的。

引理三：PMC模型中的结点均是可互测的，当该系统为t故障可诊断系统时，

mi∈M，mi∩f =，|mi| >t -|f|，可以证明得出mi中关联的结点均是正确的。

证明反证法，假设 mi中的结点存在着错误结点，那么必定 mi中所有结点都是错误结点，由于 mi∩F= ，这时候已经确定的错误结点数目为 |mi| + |F|个，由于已知条件有|mi|>t-|F|，所以显然有|mi| + |F|> t，这和 t 故障可诊断系统的定义相矛盾，所以假设错误，所以引理 3 可证。

3.算法与举例

基于互测 PMC 模型的条件诊断算法分以下 5 个过程进行。

Step1 根据互测有向图的定义，同时根据引理 1、2 的规则，建立起初始化的互测有向图 G （ F，T，M，HF）。

Step2 按照定义 4 的要求需要对具有相同结点的集合进行合并，也就是对 M 中元素进行等值合并处理。

Step3 通过引理 3、4、5、6、7、定理 7、8 可以确定部分结点的取值，把判定是正确的结点加入到 T 集合，把判定是错误的结点加入到 F 集合中。

Step4 经过 Step3 之后 T、F 集合的元素发生了变化，由引理 3、4，根据 T、F 集合的元素进一步确定 M 集合中部分元素 mi的取值。然后根据 HF 的元素（ u，v） 至少有一个错误结点的特点进行判断处理，如果（ u，v） ∈HF，当 u∈T 那么 v = 1，同样当 v∈T，那么？u = 1。

Step5 判断在给定症侯条件下系统是否有唯一故障模式。

举例 1 以图 1为例.

Step1 初始化互测有向图 G（ F，T，M，HF） ： t = 3，n= 7，F = { b，e} ，T =，M = { { a，b} ，{ c，d} ，（ f，g） } ，設m1= { a，b} ，m2= { c，d} ，m3= { f，g} ，HF = { （ a，d） ，（ b，

f） ，（ c，e） ，（ d，e） ，（ g，a） ，（ g. e） } .

Step2 mi（ i =1，2，3） 都不满足合并条件；

Step3 F = { b，e} ，T =.

Step4 F = { a，b，e} ，T = { g，c，f，d} .

Step5 得出最终的唯一的故障模式是： a = 1，b =1，c = 0，d = 0，e = 1，f = 0，g = 0.

参考文献

[1]F P Preparata，G Metze，RT Chien.On the connection as-signment problem of diagnosable systems[J].IEEE Trans Electronic Computers，1967，16（ 12） ： 848-854.

[2]Barsi F，Grandoni F，Maestrini PA theory of diagnosability of digital systems[J].IEEE Transactions on Computers，1976，25（ 6） ： 585-593.

[3]M Malek.A comparison connection assignment for diagno-sis of multiprocessor systems[A].1980，31-35.