（计算机应用技术专业论文）有故障诊断有效算法的分析与研究.pdf

系统级故障诊断有效算法的分析与研究 摘要 f 随着信息时代的来临，计算机系统在人类生活中发挥越来越重要的作用， 其可靠性和安全性也成为研究的热点。系统级故障诊断就是对计算机系统进行 故障诊断、监控和排除系统中的故障，提高系统可靠性和安全性。7 本文主要是 对系统级故障诊断算法进行研究。 、 7 集团算法是近年来提出的一种系统级故障诊断算法。本文分析了集团算法 的特点，并对其进行改进用并行的方法生成集目盯提高算法的性能，使集团 算法适用于分布式系统中：概率诊断是系统缓故障途断的一种重要方法，本文 对主要的概率诊断算法进行分析比较，集中研究了s o m a n i & a g r a w a l 算 法，在判定策略上用致投票法取代大多数投票法，使算法更有效，适用范围 更广：本文通过仿真实验分析比较各算法的性能。实验结果表明，集团算法在 只需较少测试边数( n ) 的情况下，在保持很高的诊断正确率( 约为9 5 ) 的情况下，可大大缩小系统的规模，( 约为5 ) ，证明了集团算法的优越性； 本文提出了一个自适应诊断算法_ 毫e q u e n t 算法，能以较低的代价对系统实现 正确诊断；本文最后对当前技术环境下酌诊断写容错进行分析研究，对集中式 系统和网络系统的使用技术进行了分析研究。 系统级故障诊断有效算法的分析与研究 a b s t r a c t d u et ot h ec o m i n go fi n f o r m a t i o na g e ，c o m p u t e rs y s t e m sa c tm o r ei m p o r t a n t l yi nh u m a n l i f e i ti s i m p o r t a n tt ow o r ko nt h e i rr e l i a b i l i t ya n ds e c u r i t y s y s t e m l e v e l f a u l td i a g n o s i s m o n i t o r s c o m p u t e rs y s t e m s ，t r y s t of i n dr e a l f u n c t i o n e d c o m p u t e r s t h i s d i s s e r t a t i o n d i s c u s s e ss y s t e m l e v e lf a u l td i a g n o s i sa l g o r i t h m s g r o u pa l g o r i t h mi san e ws y s t e m - l e v e lf a u l td i a g n o s i sa l g o r i t h m w ec h a r a c t e r i z et h e g r o u pa l g o r i t h m ，e n h a n c e i t b yu s i n gp a r e l l e lm e t h o d ( i n s t e a do fs e r i a lm e t h o d ) t os e a r c h g r o u p s ，a n di m p r o v e i t s p e r f o r m a n c e t h e n ，w er e s e a r c h m a j o rp r o b a b i l i s t i cd i a g n o s i s a l g o r i t h m s ，a n a l y z e a n d c o m p a r e t h e i r c h a r a c t e r i z a t i o n s ，e s p e c i a l l ys o m a n i a g r a w a l a l g o r i t h m w eu s eu n a n i m o u sv o t i n ga si d e n t i t ym e t h o di n s t e a do fm a j o r i t yv o t i n g ，r e n d e r i n g t h ea l g o r i t h mm o r ee f f i c i e n ta n du s e f u l ；w ed e s i g nas o f t w a r es i m u l a t i o ns y s t e mt o c o m p a r e t h e s ea l g e r i t h m s p e r f o r m a n c e t h er e s u l t ss h o wt h a tg r o u pa l g o r i t h mr e d u c e ss y s t e ms c a l e g r e a t l y ( 5 ) w h i l es t i l lk e e p i n gh i g hd i a g n o s i sc o r r e c tr a t i o ( 9 5 ，a n do n l yn e e d i n gs m a l lt e s t l i n k s t h e nw ep r e s e n ta na d a p t i v ea l g o r i t h m - - - s e q u e n ta l g o r i t h m ，w h i c hc a r lr e a l i z ec o r r e c t d i a g n o s i sw i t h s m a l lt e s tl i n k s i na d d i t i o n w e a n a l y z e t h e d i a g n o s i s a n df a u l t t o l e r a n t t e c h n o l o g yi nc o m m e r c i a ls y s t e m s ，i n c l u d i n gc e n t r a ls y s t e m sa n dn e t w o r ks y s t e m s 1 1 引言 第一章、绪论 近年来随着计算机应用的越来越普及，以及i n t e m e t i n t r a n e t 的迅猛发展，计算机系 统在给商业、金融、社会生活等带来巨大方便的同时，其整个系统的安全性和稳定性也 成为人们日益关心的话题。电子商务、电子货币、网上银行等关键性业务不允许存在 安全隐患，或发生错误时以很少的代价排除故障。这已是当前计算机应用领域十分重 要的研究课题。系统级故障诊断通过测试、诊断，可确定系统中的故障机，是保证整个 系统安全与稳定的非常重要的手段。 当计算机系统日益广泛应用于对安全性要求很高的系统中时，对这种系统提供很好 的容错能力己十分必要。为了维护一个高可靠的系统，故障处理机必须被诊断出来并在 系统中排除( 物理上或重新配置) 。在超过1 0 0 0 个处理机的系统中，为提高操作效率， 故障诊断与重新配置应自动进行。然而，在大系统中确定故障机的工作十分困难，尤其 当故障机可能判正常机为故障机时。处理机也可能发生间隙性故障( 不稳定的硬件或软 硬件状态的变化导致间隙性故障) 。用于检测故障的测试可能不能捕捉到全部故障机。 设计具有高可用性、高可靠性和容错功能的系统必须解决系统的诊断问题，只有在 系统检测出故障，才能使用故障处理的手段和方法，进行故障的处理( 如屏蔽、隔离) 。 故障定位后才能对故障进行修复。系统级故障诊断的基本思想是把系统划分为若干个子 系统，这些子系统具有独立的测试功能，通过这些子系统之间的相互测试，分析确定故 障单元。对于处理机故障诊断主要有三级诊断工作方式： ( 1 ) 处理机联机自诊断。处理机联机自诊断主要对处理机基本指令执行的正确性和 数据传送的正确性进行检测。它可以检测出处理机的某些永久性故障，通过重试方法可 屏蔽处理机的偶发性故障，并记录统计处理机偶发故障的发生频度。故障检测效率较高， 但存在一定的局限性。处理机联机自诊断也称为系统异步诊断这意味着第i 个处理机 执行自诊断时系统中其它处理机仍可执行用户作业。处理机联机自诊断的引入，为系 统恢复实现一步回滚创造了条件。 ( 2 ) 系统级诊断。系统级诊断也是一种联机诊断。它利用系统中多个处理机协同诊 断来实现故障定位。当处理机联机自诊断不能检测出故障且处理机的偶发故障发生频 率达到某一预设值时可采用系统级诊断，或者当系统连续工作时间达到某一预设值 时，启动系统级诊断。系统级诊断能检测出故障的范围比处理机联机自诊断能检测出 故障的范围更大效果更好，但占用系统开销也更大。当系统进行系统级诊断时，整 个系统用户作业的执行均要受到影响。系统级诊断也称为系统同步诊断。 ( 3 ) 处理机脱机诊断。主要用于处理机故障修复。当通过处理机联机自诊断或系统 级诊断将故障定位到某处理机时，系统管理员可将故障处理机从系统上卸下，利用处理 系统级故障诊断有效算法的分析与研究 机脱机诊断对故障机进行修复工作。 考虑系统的规模及问题的难度。我们仅考虑处理机一级的诊断称为系统级故障诊 断。系统级故障诊断概念由p r e p a r a t a i 。i 等于1 9 6 7 年提出，运用圈论模型对计算机系统进 行故障诊断。其基本思想是：让系统中的处理机相互测试通过对测试结果进行逻辑分 析，找出系统中的故障处理机。它假设处理机能相互测试并且各自对其它处理机状态达 成自己的结论。系统用一个有向图( 测试图) 表示。图中顶点代表处理机，边代表处理 机之间的测试( 这将导致大量的故障症候) 。诊断系统的任务就是从症候中判别出故障机。 对一种故障情形，可能有多个症候与之相应( 由于故障的随机行为) 。系统级故障诊断 当前被广义归类为确定性方法和概率性方法。确定性方法指：对正常机和故障机行为作 一假定，以及对测试图的结构作假定。对给定症候，将唯一地确定全部故障机。相反， 概率性诊断对测试图结构不作限制，只是试图高概率地诊断出故障机。 1 2 1 系统级故障诊断主要理论 1 9 6 7 年p r e p a r a t a 提出了第一个系统级故障诊断基本模型一p m c 模型用图论方法 解决系统级故障诊断问题。一个由n 个处理机组成的系统用集合v = ( u 。u 。 表示，对每一个属于v 的处理机u ，分配一个v 的子集供其测试。用有向图g ( v ，e ) 表示测试情况。每一个v 中顶点u 表示一个处理机。e 是系统中所有测试边的集合。e 中 每条边( u 1 ，u ) 表示u i 测试u 。测试u i 的结点集用r 1 ( u i ) 表示。r “( u i ) = r 1 1 ( u i ) uro ( u o 。 r o 。( u 1 ) 表示测试u i 为0 的结点集，rl 叫( u i ) 表示测试u i 为1 的结点集。rk 叫( u 1 ) = u i r 。( u i ) ：a j = k k = o ，l 。t = m a x i r 1 ( u 1 ) 1 ) 表示测试图的最大的入度。给定一个故障事件， 一个测试能检测到该事件的概率称为该测试的故障覆盖率。测试结果用二进制变量表 示。若u 通过了u i 的测试，则a i = 0 ，若u 未通过u l 的测试，则a i 。= 1 ；若u l 和u i 之间没有 测试，则a 赋空值。症候s 是从边集e 到 o ，1 ) 的一个映射。系统级故障诊断就是基于 一个症候s ，试图诊断出系统中的故障机集。 定义1 1 【1 1 给定测试图g ( v ，e ) ，某故障集f 称为g 的相容故障模式c f p ( c o n s i s t e n tf a u l t p a n e m ) 当且仅当f 的故障响应与g 一致，即当u l ，u v f 且a e 。则a ，= o ： 当u 【v f ，u f 且a e ，则a ，= l 。 表l1 给出了一组测试响应，其测试矢量、v = ( a 2 ，a z 。，a ) = ( 0 ，1 ，0 ) 及相对应的所有c f p 。 显然，与w 相容的c f p 不是唯一的( 当所有单元均为故障时的c f p 总与w 相容) 此时 若假定系统中最多只存在个故障( 即对系统中故障数目作限制) ，则对任何测试矢量， 只对应唯一的一个c f p 。 2 系统级故障诊断有效算法的分析与研究 表1 i 测试矢量w 的c f p 定义1 2 1 1 】一步t 可诊断系统：对于包含n 个结点的系统g ( v ，e ) ，假设系统中任何 故障集f 的数目if i t ( 正整数) ，且对任何测试矢量w 最多只存在一个故障模式f 与之 相容，则称此系统为一步t 可诊断系统，简称一步t 可诊断的或t 可诊断的。 一1 引理1 1 1 1 l 系统中故障机个数t 的上限由系统结点数n 决定：t 二 ，即系统中故障机 z 个数不能超过总机器数的一半。 一1 引理1 2 t 1 i 若g ( v ，e ) 的点连通度t ，且t 二= 二，则系统为t 一步可诊断系统。 z h a k i m i 和a m i n 在1 9 7 4 年给出了t 可诊断系统的充要条件： 引理1 3 1 2 i 对于1 3 个结点的系统s ，如果不准任何两个结点相互测试，则s 为t 可诊断 的当且仅当对任意u v ，d ( u ) t 如图4 1 就是2 一可诊断的。 1 , 2 2 系统级故障诊断主要模型 由于实际系统物理结构复杂，拓扑结构多种多样，因而在诊断过程中需要一定的抽 象即需要建立测试模型。自1 9 6 7 年以来。提出了各种各样的测试模型，其中主要的模 型有p m c 模型、b g m 模型【”、c h w a & h a k i m i 模型f | 1 和m a l e k 模型【5 i 。如图1 1 至图1 4 所示。 0 0 十+ + + + l + o ，1 + 0 ，l + 1 + 斗一 + o ，1 -+ + l 0 1 0o + 图1 1p m c 模型 图i 2b g m 模型图1 3c h w a & h a k i m i 模型图1 4 m a l e k 模型 测试模型中，u i 测试屿，若u i 通过测试，则返回0 ，否则返回1 。其中p m c 模 型属于基于测试的对称模型，它假定正常机的测试结果可信，故障机的测试结果不可信： 系统级故障诊断有效算法的分析与研究 b g m 模型属于基于测试的非对称模型，它假定正常机的测试结果可信，故障机测试故障 机时测试结果可信，故障机测试正常机时测试结果不可信比较模型中u ，u ；执行同 一任务，比较执行结果，若相同则值为0 ，否则为l 。c h w a h a k i m i 模型属于基于比较 的对称模型，它假定当比较边为0 时两机状态相同，当比较边为1 时至少有一个故障机； m a l e k 模型属于基于比较的非对称模型，它假定当比较边为0 时两机必为正常机，否则至 少有一个故障机。除了二值p m c 模型，还有一种三值p m c 测试模型f 6 j ： ( 1 ) “0 ”类正常机。正常机能通过它的测试，故障机不能通过它的测试。 ( 2 ) “i 2 ”类正常机。正常机能通过它的测试，故障机不一定能通过它的测试。 ( 3 ) 故障机。其它处理机不一定能通过它的测试。 上述模型只考虑处理机发生故障情形，然而随着网络系统的广泛应用，通信链路的 故障已成为系统发生故障的一个重要方面。新的诊断模型 2 9 i 把一个结点分为两个部分： 处理机部分和通信部分。两部分都可能发生故障，当某结点处理机部分发生故障而通信 部分功能正常时，其它结点仍可利用其通信部件对其它结点进行诊断。在该模型下，故 障可能发生在以下三个部分：( 1 ) 处理机部分故障：( 2 ) 通信部分故障；( 3 ) 通信链路 故障。 1 2 3 系统级故障诊断性能指标 系统级故障诊断的核心问题是以最小的开销完成诊断任务。诊断是正确的表示没有 正常结点破错误诊断为故障结点，否则是不正确的诊断。如果能诊断出全部故障机，则 称诊断是完全的，否则称为不完全的诊断。 评价一个系统级诊断方法的性能，主要从下面几个方面考虑： 1 ) 能诊断的故障的类型以及故障数目。故障类型分为永久性故障、间歇性故障和 线路故障等。 2 ) 需要的测试数目。即进行一次完整的诊断需要执行的测试次数。测试次数越多， 系统开销就越大。 3 ) 对测试图结构的要求。每一种诊断方法都要求测试图满足一定的条件。要求越 多，则该诊断方法的适应性越差。 4 ) 诊断方法的时间复杂度。计算量越大，占用系统资源时间越长，效率越低。 5 ) 诊断信息传输量。系统要收到测试信息后，才能作出诊断，诊断信息传输量越 大，系统的开销也越大。 6 ) 诊断方法的诊断精度。即在所执行的诊断中，完全正确的诊断所占的百分比。 7 ) 算法的稳定性，当系统结构各方面作很小改动时算法的性能是否发生很大的 变化。 8 ) 诊断延迟。诊断延迟指从测试到故障发生到诊断出故障所需的时间。诊断延迟 越氏系统在故障状态下工作的时间也越长系统可靠性降低。诊断延迟是一个 综合性的指标，与许多因素有关。 4 茉统级敞障诊断有效算法的分析与研究 。3 本文主簧工作 菠羲僖息鞋钱靛来娅，计算撬系线在人类生港中发挥越采越重要熬作孀，其霹靠性 和安全性也成为研究的热点。系统级故障诊断就是对计算机系统进行故障诊断，使其具 有容锚功能。本文主要是对系统缀放障诊断算法进行研究，主鼹工作为： l 。综述。归纳系统级放障诊断的主要理论，基本模型秘基本研究方法，分辑冬自 的特点和适用范围。( 第二章) 2 ，袋豳算法黪联究与教进。集盟舞法跫近年来提搂鳇一种系统级数障诊凝算法。 本文分析了集团算法的特点把关键的集团生成方法改进为并行生成方法，提 离葬法静性能。( 第三章) 3 +概率诊断算法的研究与改进。概率诊断是系统级故障诊断的一种重要方法，本 文对主簧的概率诊断算法进行分析沈较。集中研究了s o m a n i a g r a w a l 算 法，在刿定策略上髑一致授票法取代大多数投票法，使算法更鸯效，逶臻范蓬 更广。( 第四章) 4 +待真系统设计及实验。诊断算法的性能指标凳能通过实验获取，本文设计了一 个仿真系统，分别对集团算法、概率算法进行仿真实验，实验结果证明了集团 算法的优越性。( 第五、六章) 5 自适应诊断算洼。囊适应诊鼓算法霹剥娥较少的测试数实现诊麟晷标，奉文提 出了一个自适应诊断算法- - s e q u e n t 算法。能以较低的代价对系统实现正确诊 断。( 第七章) 6 当前技术环境下的诊断与容错。分析了商业环境下的诊断与容镄实现方法，对 集中式系统和网络系统的使用技术进行了分析研究。( 第八帮) 5 墨竺墼垫堕建堑塑墼墨鎏些坌圭曼兰竺篓 2 号l 害 第二章、系统缀放障诊断主要方法 测试模型就诊断罄标褥言，诊断霹分为确定性诊断幂l 橇率性诊断。确定经诊断要求 绝对工e 确地找出故障处理机系统开销大，所需测试数较多：概率性诊断只要求基本正 确蛾找出故障处理机，比较符合实际系统，开销小，所需测试数少。就诊断邋应性而言， 可分为非适应 生诊断与适碰性诊断。非适应性诊断中，测试之间楣互独立进行，藤适应 性诊断中，下一次的测试与上一次的诊断绪果有关所需的测试数比非适应性诊断少， 更是有灵活性。按诊凝步骤分，霹分为一步诊断秘颓净诊溪。一步诊辑测试在诊断翦全 部完成，一次确定全部故障机；顺序诊断则一次确定一台故障机，将之从系统中排除， 对余f 的系统释测试、诊断，鸯到我出全部故障杌为止。按拓扑结构分，可分为集中式 诊断和分枢式诊断。集中式诊断需要一台绝对正确的中心挑( 硬核) 处理各枧的测试结 果，且必须保证各处理机与中心机有u 西丁靠的线路连接；而分布式诊断中，每一台处理机 独立缝对系统中豹掰毒楚壤撬佟出诊断，系统串掰有燕常撬能够麓系统作密一致最确的 判断。分布式诊断比较适含于网络环境下的故障诊断。主要系统级故障诊断方法分类如 下： 2 2 确定性渗新方法 确定健诊断方法要求钛测试结果中唯一地诊断出故障机集合。1 9 6 7 年p r e p a r a t a 等人 把圈论模型引入系统级故障诊断。提出了p m c 模型。在p m c 模型中，正常枧敷测试结 果可信，故障机的测试结粜不可信。t w 故障一步诊断方法要求的测试数n * t 。算法的时 阂复杂度为0 n 赶) 。该箕法要求令绝对燕确携中心撬来收集各姓理梳静测试信意并执 行诊断并且限定系统中故障机数目不能超过t 。 确定性诊断方法可分为完全测试和不完全测试两种。完全测试假定正常机总能测出 故障机，朝个结点慰另一个结点作的系统级测试具有1 0 0 的故障覆盏率。非完全测试 则对结点行为无限制。完全测试假定所有故障均为永久故障，非完全测试允许间歇性故 障。 完全测试方法中，为了减少可诊断度对测试图的要求以及扩展诊断模型的应用范围， p m c 模登棱大鬃扩袋及推广。龟括颓序诊断1 7 ，诊断进行对。每一步替换掉上一步诊断 为故障的结点，辫进行下一轮诊断，童至诊断出所有的故障枧。自适应诊叛【| 1 投握上一步 测试结果选择每一步所需的晟小测试数。悲观诊断f ”中，一些正常缩点被包含在被诊断为 数薄柱集。p - t 诊凝粕投诊錾l ”1 ( 在诊凝中馒踞每个结点携绘定故障概率) 。s o m a n ie t a l 模 型f 1 l 是p m c 模型的推广，故障和测试之间的关系已给定。该模型允许对一给定故障的测 试可戳因其它故障翡存在丽无效。 在不完全测试方法方蕊，m a l l e l a 和m a s s o n i ”1 定义一个t r 可诊断系统：其中间隙故 6 系统级故障诊斯有效算法的分析与研究 蹲不越过t 个，正常缝点永远不会被判为故障结点，该诊凝是最苓兜全的。( 一些赦障缝 点未被确定) 。这个模型结合了永久故障和间歇性故障同时存在的情形。他们对t 可诊断 系统撬出了复杂疫为o ( 嗣) 静敬簿诊断算法：该葵法对给定的瘙候集会，至少诊新出 一个故障结点。 使用完全测试模蟹的确定性诊断岂取得锻大藏果。确定饿诊断疆基本的戳制 正常 机总能测出故障机) 馊这些方法不能应用与间歇性故障情形中。藤实际系统孛大部分为 间歇故障。实际上，实验结果表明。实际系统中8 0 的故障是瞬时或间歇性的 对给定痉姨秘故障撬集大小黢裁，礁定 生不完全方法是缣守的只能确定明显为数酥 的结点。从而不能诊断丈量间歇性故障结点。确定性诊断方法适用于完全测试模型。 2 3 概率诊断方法 为了对普通测试图中超过t 个故障的情形进行诊断，引入了概率性诊断方法。概率性 诊断方法适爝于不完全测试模型。概率性诊断方法中，绡概率模型来表示故障机和正常 机的行为特征。对于绘定的瘰候，可用一个囊发性魄过提确定故障规集会。概率性诊断 方法的最重器的问题是诊断复杂度和诊断精度。 确定性诊羝方法对测试翔蕊结梅要求圪较严格。鲤扣可诊辑系统要求系统串任意褥个 结点之间至少有t 条互不相交的通路。而大部分实际系统都不能达到这样的要求。在研 究过程中，入 i 、j 挺出了概率诊断方法 q 。概率诊断方法不象确定性诊断方法那样觚测试 信息中唯一地识别出故障机集，磁是只试图基本正确地诊断出裹概率的故障结点。不要 求限定性地假设测试圈的结构，对测试边数目以及故障机数上限均无限制。概率诊断方 法中，罔概搴参数来攒述故障结点靼正常缍点鹃牙淹特性。概率参数鲣下袭辑录： 表2 1 概率参数表 e e ，a 。p ( a i 阮，e ，) 00o 0 “ 0ol l q 。 0ll p 。 ol 0 i p ， l0o y 。 lo1 i y 。 ll l s 。 lo i s 。 表中乇表示结点l i i 的状态，e 。= 0 表示“i 为正常机，f i i = l 表示u j 为故障机。预先给 定遵为故障枧的概率为我，鞭码l i ，f 为毫知，j 的情瑰下，钧发生的概率。接 述两个正常蜡点之间的链路故障- 为正常机测试故障机测试结果为l 的概辩。p # 描 述了阚歇牲故障静特短在永久故障模型下，p “是u ，测试q 的藏障覆盖率e 实际系统 中大部分故障是间歇性敞障，其特征是处理机出现时好时坏的情况。当p 4 。l 时表示故障 7 篆统级赦障诊新有效算法的分析与研究 为永久性故障，正常机对该机的任何一次测试均能得出该机为故障机的结论。确定性 方法就是假定p 。= 1 的情形。对予间歇性故障，可以通过增加测试次数来提高好机对故障 规的诊凝正确攀。例如：进 亍n 次测试，至少出现一次“l ”躲测试结累的概率强： p i ( i * p 。) “ y 。s ，分别表示鼓漳撬能正确测窭歪常税稆敬辩辊豹概辜。 概率诊断方法根据在诊断故障结点时所用到的测试信息可分为三类( a ) 利用整 个系统的测试信怠，b l o u n t 于1 9 7 7 年提出的一个算法f 1 4 j 属于此类。这类方法计算的时 闻复杂性很离，因两效率很低。( b ) 利用本地测试信息t ；“瓠) ，t o ( u 0 謇珏翦嚣步骤已诊 断出的故障结点_ 来诊断结点u 的状态，这类方法采用分布诊断的策略，每次只诊断一个 数薅络点。( ) 裁用本地售惑t ：。# ) ，1 一( u o 寒确定每个娃理枕的状态。b l o u g h 于1 9 8 8 年提出的个算法l 属于此类。就b 类和c 类算法+ l e e 和s h i n 张1 9 9 3 年摅出了一种 局部最优的诊断葬法l “。每一种概率诊断算法必须保证在保持测试图结构不变的前掇下， 当系统的缝点数趋向于无穷犬时，算法的诊断精度趋近予l 。激近正确是每个概率算法鲍 特性。 撮率诊颤方浚逢胃鞋采耀| 囊净诊酝豹策咯。b l o u g h 鞫p e l c 在t 9 9 3 年提高了一种颓 序诊断的算法i ，其策略是分两步进行诊断。第一步是让系统中各处理机相互进行测试 得到一个核心正常集；第二步是和用核心正常集依次对其袍机进行测试、诊断，当诊断 为好机时，把它纳入核心正常集，当为故障机则避行更换，囊到系绞中处理枫全部为好 机。给定测试信息，找出最可能的故障情形烧一个n p h a r d 问题。评价概率诊断方法的 一个羲要指标是诊凝壤瘦。一个诊断算法兹诊断鞲发达戮最舞缓，该诊断算法僵被认为 是最优的。诊断精度可用p g ( a l g o r i t h m ) 表示。p 表示概率，g 表示测试圈，a l g o r i t h m 表 示算法。诊断精度即攒给定涮试图，算法可作出正确诊新的概率。它与算法和铡试阔有 关。给定测试图，获得最优诊断是一个n p - h a r d 问题。各概率诊叛方法的搜指标如袭4 1 所示。 擞率诊凝方法比确定性方法受符合实际系统，多处疆撬系统静规模交褥越来越大， 系统中处理机数目越来越多，对系统进行故障诊断相应变得复杂。而概率诊断方法的诊 新精魔随系统孛链理辊数目增加丽提高。概率诊断方法更适含应用于大规模系统。概率 诊断方法虽然对测试图结构廷严格要求，但概率诊断方法一般要求用概率参数来描述正 常机和故障机的行为特性，并用它来评估所作诊断的质凝。在实际系统中如何获取这些 概率参数是个爨寒据决的翔题。 2 4 分衣式诊断方法 臻定性方法秘概率性渗新方法均骰定系统幸存在一个孛心撬。该中心橇绝对正确。 其他处理机把测试结果都传递给中心机，由中心机对测试结果集合进行诊断。大部分实 鞣系统不满楚上述缓定。铡试信惠在传递给中心税的过程中，若经过路径上存在故障机， 则测试信息可能出错。另一方亟，很难保证系统中存在一个绝对正确的中心枫。针对这 种情况，八十年代初，k u h l 和r e d d y i ”i 提出了分布式囱诊断思想。其基本思想是在分 8 系统级故障诊断有效算法的分析与研究 布式系统中，每个处理机分别独立地对系统中的处理机作出诊断，不需要一个中心机。 典型的分布式算法有n e w s e l f 算法i 。e v e n t - s e l f 算法【2 q ，d s d 算法1 2 j 】等。 n e w s e l f 算法是一个基于p m c 模型的非自适应的t - 故障一步诊断算法，它要求每一 个结点至少被t + 1 个别的结点测试，以保证系统中的好机能连成一条链以及任意放障机 都至少被一个正常机测试。系统中正常机所作的诊断是一致正确的。e v e n t - s e l f 算法 是n e w s e l f 算法的改进。d s d 算法是一个基于p m c 模型的自适应t - 故障一步诊断算 法。系统中处理机按顺序编号，采用自适应方法进行测试。每个处理机对它后面的处理 机依次进行测试直到它测试到一个它认为正常的处理机时，则停止往后测试。该测试 策略使得系统中的正常机形成一个环。整个系统的测试信息通过这个环传递到每一个正 常机上，最后由每个正常机作出一致的诊断，n e w s e l f 算法和d s d 算法的性能指标如 下表所示。 表2 2n e w s e l f 算法和d s d 算法的性能指标 i 算法测试数时间复杂度传输信息可诊断的故障数 ln e w s e l f n ( t 十1 )o ( n ( t + 1 ) )n 2 ( t + 1 ) 2 t ld s d n o ( n ) f nn 一2 d s d 算法的诊断延迟n e w s e l f 小。就测试数目和信息传输量以及时间复杂度而言， d s d 算法是一种较优的算法。d s d 算法是第一个用于实际系统诊断的算法。d s d 算法和 n e w s e l f 算法都能诊断间歇性故障情形。d s d 算法不能诊断链路故障，而n e w s e l f 算法在多总线的条件下能诊断链路故障。 2 5 集团方法 系统级故障诊断自从提出以来，大部分研究都是采用图论模型框架，即逐个分析某 个单元、某条线路或某条可靠路径来研究系统的可诊断性。鉴于实际系统中正常机占大 多数的情况，即系统中存在大可靠块的事实，张大方等人提出了集团口2 】的概念。集团方 法的基本思想是：让系统中性质相同的结点聚合成一个块( 进行集团运算) ，再对聚合后 的系统进行诊断。这样可大大降低系统的规模。集团运算的规则是：两个结点若相互测 试均为正常机，则它们属于同一集团。集团中的结点性质相同要么都是正常机要么 都是故障机。进行诊断时，只要确定集团的属性。该集团中所有结点的属性都可得出。 集团运算如下图所示： 9 系统级故障诊断有效算法的分析与研究 图中结点0 、9 属于一个集团结点1 、2 属于一个集团，结点3 、4 、5 、6 属于一个 集团。 图2 2 测试图 1 0 图2 3 集团运算后的诊断图 3 5 i 蒹统缎故障诊断有效算法的分析与研究 第三章、并行集团算法研究 3 1 集团算法基本溪论 裔从1 9 6 7 年p r e p a r a t a 等入把圈论横型s i 入系统级故障诊断以来，经过三朗十年的发 展，人们提出了各种各样的诊断模型和诊断算法。但是，大部分研究工作都是基予p r e p a r a t a 提出的圈论模型，主要集中对单个的绪点，单条测试边，或缩点之间某条可靠路径进行 诊羝，来分据整令系统戆故漳状况。鉴予实际系统孛太多数聚理撬建正常辊静事实，张 大方等人提出了基于集团的系统缴故障诊断。由于系统中存在大可靠块，把性质相同的 结点聚合在一起进行诊断，可大夫降低系统豹诊断复杂度本章羔罄是对集团算法进行 研究，在关键的集团生成方法上进 - 改进，提高算法的效率。撰团算法采用p m c 诊凝模 型，允许结点之间相互测试每条测试边均是双向的。下面给出集团算法的基本定义、 性质以及定理等。 定义3 1 ih 叫做连通图g ( v 。e ) 的一个集团当鼠仅当： ( 1 ) h 是连通子圈； ( 2 ) h 如果有多于一个结点机时，h 中任意= 续点之闻至少蠢一条 税全为0 0 的通路。 ( 3 ) h 中任意个结煮强h ，魏鬃与鞋辨靛结点n ，穗邻接，刚 w 、w 不同时为0 。 从上述定义可知，如果存在1 1 i 使樗对予u i g u 的所有邻接点u j ，酾4 酆苓翳时 为。时，则址为巢集团中的唯一一个结点。 定义3 2 2 2 i集爨 豹邻接集，记戈c 0 - i ) ，定义魏下： ( 1 ) 结点u lgh ，褥且毽靼h 孛躲菜维点援舔接，剥定义毽e h ) 。 ( 2 ) 集团h 。与h 中存在点相互邻接，则h 中骈毒绪点都属于c ( 1 - i ) 。 点e 震3 1 m i 集爨h 中的臻毒结点，要么惩黠必正常撬，要么阑葬孝为藏薅辘。 由性质3 1 可以将集团分为两类：( 1 ) 集团中都是正常机，称为好集团：( 2 ) 集团中都是 故障撬，称为坏集团。 性质3 2 1 2 2 l 集团h 中若存在u l 、u j ，w “与”# 不同对为0 ，则该集团中所有终点 均为故障机。 性震3 + 3 1 2 ：i 好集耀 鳇邻接嶷c ( ) ，全郏都为数藩结煮规。 由上述性质知，可通过如下途径确定集团属性：( 1 ) a i i ：0 ，a i = 1 ，则嘶为故障机，包含 n ，嶷霞为坏黛鏊；( 2 ) 壤据邻撩集糯性：( 3 ) 其它条件。如对馥障数上限的限锏等。 定义3 3 1 2 2j 给定连通圜g ( 、e ) ，通过一确定算法，找到g 中的所窍集团，并姆每一集 纂统级故障诊断有散算法的分析与研究 团中所有点归茹为一个结点，称为集团点。然后将这些集团点按图中原褥的连接方式相 连，形成集团相甄之间的图，这个集团生成过程我们称之为图g 的集团遴算 定义3 。4 t z 2 1 绘定连避耀g ( v ，e ) ，经过集戮运算辑形戏的匿，称为诊凝圈g l ( v l 嚣| ) 。 定义3 5 m j s 称为连通图o ( v ，e ) 的独立点集，如果s 为v 的一个子集，且s 中任何两 点都不邻接。拯莱v s 中不存在与s 不邻接的点，* l 称s 为潮g ( v ，动的极大独立点集 如图2 3 中集团0 和集团2 是系统一个极大独立点集。 定理3 。1 1 2 2 i 集豳运算永远可以进褥劳盥结袅是唯一的。 定理3 2 1 ”i 给定圈g ( v e ) ，故障模式f 为相容故障模式，当且仪当v - f 构成g ( v ，e ) 的 诊酝辫g 。( v ，e ：) 懿独立点集。 定理3 ，3 t 2 2 i若系统s 是一步t 可诊断的，对于给定s 相对应的图g ( v ，e ) 。所有的无故 障结点构成其诊断图g 的一个裰大独立点鬃。 定理3 。4 t 2 2 l 系绩s 为一步t 可诊断的宠要条件悬对于经意绘定的圈g m 毯，所鸯惩鬻 结点构成其诊断圈g i ( v i ，e i ) 唯一的满足n - t 的极大独巅点集t ，萁中n - l v l 。 以上绘出了集团算法魏一些基本定义、蒸本链矮弱主要定理。下瑟将对集露弱燕减 方法进行研究。 3 2 集团生成方法研究 给定一个测试圈，我们研究如何快速地让性质相同的结点聚含成一个集团。 3 2 1 集闭生成的串行方法 大部分系统级故障诊断算法中，都假定系统中存在一个绝对可靠的中心结点，中心 绪点浚集各个其它结煮的测谈信慧对整个系统的测试信息进行分析，从而确定整个系 统的故障状况。串 亍生成集团的方法就是由中心结点处理全部集团生成过程，如图3 1 所 闰3 1 串行生成集团 豕。集鼹是按序生成鳇。 算法3 1 基予串行方法的诊断算法： 第一步：集鞠生成。 f o r ( r = 0 f f n o d e s ；i + + )n o d e s 必系统中结点数 1 2 囡悭 系统缎故障诊断有效算法的分析与研究 f ( i n g r o u p 1 2 铷1l n g r o u p 】魑维点憝否属予集团标志，0 表示 不藏予巢个攘溺，1 表示属予某个鬃豳。 ( 1 ) 调用串行集团生成算法求集团，得g r o u p i ； ( 2 ) 将渡集戮作为g ；懿个缝点： ( 3 ) 保存g r o u p i q b 结点数及舆体结点： ( 4 ) 载灏该集翳皇毙裁产生翡集嚣乏瓣憝嚣毽疆，蒹毽接，粼程g ，孛耨 表承此两集团的结点连接。逐步生成诊峨熙g ，； 第二步：调翅极丈独立患集生戒箨法3 4 求诊髓銎g ，的掰有掇夫独立点集。 浆三步：确定故障机集仑。 ( ) 拽如包含源结点撤多酌掇大独立点集t 。 ( 2 ) u - t 即为系统中全部故障机。 算法3 2 奄行擞爨生藏舞法： ( 1 ) 拣志| 汪耩予某个集强： ( 2 )瓣结点i 静邻接点集中熊点测试： ( 3 ) 若w b * = 0 t 烈振志j 己震予某个集爨，把；爨存入敝捌； ( 4 )测试i 的下个邻接点，重复( 2 ) 赢至测试究i 的所有邻接点： ( 5 )姨默到孛弹掇队头赋绘 ，重复( 2 ) ，( 3 ) ，( 4 ) 步，燕至驮裂为窒； 罨 蓬3 1 冀法3 2 可戳求出一个究整的集盈。 诞明：步骤( 3 ) ，( 4 ) 拽鑫与缭点1 穗邻懿掰蠢属于麓一集潮静点( 鞠与l 籀邻置轰瓤结 聚为0 0 的所有邻接点，步骤( 5 ) 找出与每个集团中的点相邻且胡测结果为0 0 的所有 绻点。觚藤薄滚3 , 2 可阻挠鸯鬯含 静究整静集函。涯毕。 党建3 。s 算法3 1 的稳磁缝果龄为系统孛全体竣簿缤点熬集会。 诞明：瞻定义3 , 3 ，定义3 4 ，引理3 1 和算法3 。1 的煞一步的描述，第一疹可找蹬g 中所 寄集遵，并生成诊断翻g ，。 蓉系统s 是一步t 磷诊凝酌，则杰定理3 , 4 可知辩予给寇瓣s 囊辩应滟瓣g ( v 秘，蒋 辩的无故障结点构成其诊断图g ，的一个极大独立点集，由定理3 6 ，定理3 7 埘知第二步 w 越求如g 。酌所有极大独立矗集。 由定理3 4 知满足lm l n - t 的极大独巍点巍t 是唯一的。我们只要诞明g 。巾包含 滚络鑫数最多的稷大独盘点纂下，帮为难一的且涛是| tl n ，t 的掇犬独立燕集t 。设t t ，即嚣在巢极大独立患懿 ”，黑lt “l n - t 。由于t 是戡客源缝点数最多的援 大独立点集，爨戳l t l t ”l ，粥毒 t l n t ，尚定理3 4 熬难一性据矛骚，簸7 蹿。 颡磊自定毽3 3 ，定理3 4 可撂彳孛鹃所有结点帮为系统s 新对应灏g 的新有无故障结 点，“一t 。为全体教障结点数集会，故第三步霹 奠骥是系缱中所有数媾撬+ 1 3 系统级故障诊断有效算法的分析与研究 综上所述，算法3 1 可确定全体故障机。 证毕。 用一个实例说明如何串行生成集团。如图2 2 从结点0 出发，得出0 9 属于同一集团， 再从结点1 出发得出l ，2 属于同一集团，从结点3 出发，得出3 。4 5 ，6 属于同一 集团，最后，结点7 和8 分别属于两个集团，共生成5 个集团 3 2 2 集团生成的并行方法 串行方法中，集团生成工作全部由中心机完成，当系统规模很大时，中心机的负载 很大，集团生成的过程变得很慢。目前分布式计算逐渐成为主流，即把原来由中心服务 器完成的业务计算分布到整个系统中进行。本节提出一种并行生成集团的方法，把原来 由中心机单独完成的工作分布到系统中全部结点上执行。生成集团时，中心机只执行按 系统中结点数均分的一部分工作，如图3 2 。只在集团生成后，再由中心机诊断出整个系 统的故障状况。系统中集团是并行生成的。如图3 3 ： 结点1结点2 结点3结点4结点5 图3 2 分布式处理 时 间 第第第 个个。个 集集集 团团团 图3 3 并行生成集团 算法3 3 并行生成集团方法： 在结点i 处) i f ( i 不属于某个集团) ( 1 ) 创建新集团g ，把i 归入该集团。 ( 2 ) 测试i 的邻接点j ； i f ( i ，j 之间存在0 0 测试边) i f ( j 不属于某个集团) 把j 归入集团g ： e l s e 1 4 系统级故障诊断有效算法的分析与研究 把集团g i 和j 所属集团合并； ) ( 3 )把i 的下一个邻接点赋给i 转( 2 ) 执行。直至测试完l 的所有邻 接点。 ) 引理3 2 算法3 3 可以找出包含结点i 的完整的集团。 证明：若结点1 已属于某集团，则集团已生成，算法终止。若i 不属于某集团，则创建新 集团s ，再在其邻接点中找属于同一集团的点。若存在此类结点，在分析该结点情况， 若已属于集团，则与s 。进行集团合并，否则只把此类结点归入s 。当遍历完i 的所有 邻接点后，即可找出包含l 的集团。证毕。 用个实例说明如何并行生成集团。如图2 2 ，1 0 个结点同时开始进行集团搜索。假 设结点3 搜索到结点4 ，形成集团a ：同时结点5 搜索到结点6 ，形成集团b ，当结点5 搜索到结点4 时，发现4 属于本集团，而4 已属于集团a ，则集团a 与集团b 合并成一 个集团。其它集团按类似方式生成。 对给定测试图，经集团运算生成诊断图后，系统级故障诊断就转变为在诊断图中找 出包含源结点最多的极大独立点集。极大独立点集生成算法描述如下： 算法3 4 极大独立点集生成算法： 1 、找出邻接点数最小的结点i ，将i 及其邻接点压入堆栈n o d e s t a c k ，把n o d e s t a c k 头值赋给a c t n o d e ： 2 、 w h i l e ( n o d e s t a c k t e 空) ( 1 ) 设置初值； v e c t o