系统级故障诊断集团算法的研究及方程解决
|
摘要
系统级故障诊断通过系统内各处理机相互测试，然后对所有结果进行逻辑分析
从而找出系统中的故障处理机。随着网络和多机系统的不断发展，作为提高系统
可靠性重要手段的系统级故障诊断的研究、仿真和实现日趋显得重要。本人在张
大方教授等人提出的基于集团的系统级故障诊断的理论基础上，重新构建了系统
级故障诊断的理论基础，定义了系统级故障诊断测试模型的三值表示；改进了系
统级故障诊断的矩阵方法，重新定义了测试矩阵、邻接矩阵、结点对、结点对的
相连运算、极大准集团和斜加矩阵，由此能直观、简便地生成集团和极大独立点
集；补充和完善了各类测试模型的系统级故障诊断的集团算法，通过定义集团测
试边和绝对故障集，简化了集团诊断图，由此能较易地找到所有的相容故障模式，
即使不满足t-可诊断性，大大减少了系统级故障诊断的复杂度，尤其是对强t-可
诊断系统；首次分析探讨了各类测试模型的方程解决，由此从另一角度能系统地、
高效率地求出所有的相容故障模式(CFP)：扩充了系统级故障诊断仿真系统的功
能，快速、直观和随机地模拟实验运行环境，进行清晰和正确的诊断，同时提供
大量的实验数据用于理论研究，优化算法和设计。最后探讨了系统级故障诊断的
应用热点和发展趋势，讨论了传统网络管理的缺陷性和基于CORBA规范和系统级
故障诊断算法的多网管系统的体系结构及优越性，为系统级故障诊断的更深一步
研究作好准备。
System-Level Fault Diagnosis can find all fault processors by ex-test of all
proceSsors in the system and analyzing logically all results of ex-test. With the
development of the network and the multi-processor system, the research, simulation
and the imPemeni of the system-level fault diagnosis which is the very important
means to increase the reliability of the system, are becoming more and more important.
On the system-leve1 fault diagnosis,based on the group theory of system-level fault
diagnosis that has been put forward by Pro f Zhang, the paPer constructs newly the
theory bases, improves on the matrix method, reinforces and consummates group
arithmetic of all kinds of test mode, for the first time,analyses and discusses the
equation solution of all kinds of models, so al1 the consistent fault patterns(CFP)
could be found, straightly and high efficiently, even if the sufficient and necessary
condition of t-diagnosable is dissatisfied and the complexity of system-level fault
diagnosis is greatly decreased, especialy in strong t-diagnosabl6 system. Last the
simulation System's function has been extended and the aPplication hotspot and the
development trend have been disscussed.
从而找出系统中的故障处理机。随着网络和多机系统的不断发展，作为提高系统
可靠性重要手段的系统级故障诊断的研究、仿真和实现日趋显得重要。本人在张
大方教授等人提出的基于集团的系统级故障诊断的理论基础上，重新构建了系统
级故障诊断的理论基础，定义了系统级故障诊断测试模型的三值表示；改进了系
统级故障诊断的矩阵方法，重新定义了测试矩阵、邻接矩阵、结点对、结点对的
相连运算、极大准集团和斜加矩阵，由此能直观、简便地生成集团和极大独立点
集；补充和完善了各类测试模型的系统级故障诊断的集团算法，通过定义集团测
试边和绝对故障集，简化了集团诊断图，由此能较易地找到所有的相容故障模式，
即使不满足t-可诊断性，大大减少了系统级故障诊断的复杂度，尤其是对强t-可
诊断系统；首次分析探讨了各类测试模型的方程解决，由此从另一角度能系统地、
高效率地求出所有的相容故障模式(CFP)：扩充了系统级故障诊断仿真系统的功
能，快速、直观和随机地模拟实验运行环境，进行清晰和正确的诊断，同时提供
大量的实验数据用于理论研究，优化算法和设计。最后探讨了系统级故障诊断的
应用热点和发展趋势，讨论了传统网络管理的缺陷性和基于CORBA规范和系统级
故障诊断算法的多网管系统的体系结构及优越性，为系统级故障诊断的更深一步
研究作好准备。
System-Level Fault Diagnosis can find all fault processors by ex-test of all
proceSsors in the system and analyzing logically all results of ex-test. With the
development of the network and the multi-processor system, the research, simulation
and the imPemeni of the system-level fault diagnosis which is the very important
means to increase the reliability of the system, are becoming more and more important.
On the system-leve1 fault diagnosis,based on the group theory of system-level fault
diagnosis that has been put forward by Pro f Zhang, the paPer constructs newly the
theory bases, improves on the matrix method, reinforces and consummates group
arithmetic of all kinds of test mode, for the first time,analyses and discusses the
equation solution of all kinds of models, so al1 the consistent fault patterns(CFP)
could be found, straightly and high efficiently, even if the sufficient and necessary
condition of t-diagnosable is dissatisfied and the complexity of system-level fault
diagnosis is greatly decreased, especialy in strong t-diagnosabl6 system. Last the
simulation System's function has been extended and the aPplication hotspot and the
development trend have been disscussed.
引文
[1] Preparata F P, Metze G, Chien R T. On the connection assignment problem of diagnosable systems. IEEE Trans on Electronic Computer, 1967, 16(12) :848?54．
[2] Bassi F, Gradoni F, Meastrini P. A theory of diagnosability Aithout repair. IEEE Trans Comput, 1976 (C-25) : 585?93
[3] Chwa K Y, Hakimi S L. Scheme for Fault-tolerant Computing: a Comparison of Modularly Redundant and t-diagnosable System. Information Control, 1981, 49:212?38
[4] Malek M. A comparison connection assignment for diagnosis of multiprocessor systems. In: Proc. 7th Symp. Comput Architecture. IEEE, 1980:31 ?35
[5] Hakimi S L and Amin A T. Characterization of the connection assignment of diagnosable systems. IEEE Trans. Comp. ,1974, (1) :86?8
[6] 张大方，江招生．基于集团的系统级故障诊断研究．计算机学 报，1998，21(4) ：308～314
[7] 张大方等．基于矩阵的极大独立点集生成算法．电子学报，1999，(1) ：202～206
[8] Andrzej P. Optimaal diagnosis of heterogeneous systems with random faults. IEEE Trans. Computer, 1998, 47(3) :298?04
[9] Sunggu Lee, Kang Geun Shin. Probabilistic Diagnosis of Multiprocessor Systems. ACM Computing Surveys, March 1994,26(1) :121 ?39
[10] Lee S and Shin K G. Optimal and efficient probabilistic distributed diagnosis schemes. IEEE Trans. Comput, 1993, (7) :882?86
[11] Horst R, Jarett D, and Lenoski D. The risk of data corruption in microprocessor-based systems. Dig. Papers, FTCS-23, 1993, (7) :576?85
[12] Blough and Pelc A. Diagnosis and repair in multiprocessor systems. IEEE Trans. Comput, 1993, (2) :205?17
[13] Bianchini R P, Buskens R W. Implementation of On-Line Distributed
Ssytem-level Diagnosis Theory. IEEE Trans. Comput, 1992, 41 (30) :616?25
[14] 01son L, Blackwell A. Understanding network management with OOA. IEEE Network Magazine, 1990, (4)
[15] Bianchini R P, Goodwin K, Nydick D S. Practical Application and Implementation of distributed system-level diagnosis theory. In: Proc 20th Symp. Fault Tolerance Comput. IEEE, 1990:332?39
[16] Stefano Chessal and Paolo Santi2． Comparison-Based System-Level Fault Diagnosis in Ad-Hoc Networks[C]. Proc. In:IEEE SRDS 2001, Symposium on Reliable and Distributed Systems. New Orleans, October 2001
[17] Somani A K, Agrawal V K, and Avis D. A generalized theory for system level diagnosis. IEEE Trans. Comput, 1987, (6) :560?66
[18] Hoseini S H, Kuhl J G, Reddy S M. A diagnosis algorithm for distributed computing system with dynamic failure and repair. IEEE Trans. Comput, 1984, 33:223?33
[19] Hakimi S L, Nakajima K. On adaptive system diagnosis. IEEE Trans. Comput, 1984, (3) :234?40
[20] Kuhl J G and Reddy S M. Distributed fault-tolerance for large multiprocessor systems. 7th Symp. on Computer Architecture, ACM, New York, 1980,23?0
[21] Maheswari S H, Hakimi S L. On models for diagnosable systems and probabilistic fault diagnosis. IEEE Trans. Comput, 1976, (3) :228?36
[22] Huang, S. XU, J., and Chen T.. 1989 Characterization and design of sequentially t_diagnosagle systems. Dia. Pagers, FTCS-19, (7) :554?59
[23] Berman P, Pelc A. Distributed probabilistic fault diagnosis in multiprocessor systems. Dig. Papers FTCS-20, (7) :340?46
[24] Yang C L, Masson.G M. A distributed algorithm for fault diagnosis in systems with soft failures. IEEE Trans. Comput, 37(11) : 1476?479
[25] Somani A K, Agrawal V K. Diagnosis algorithms for regular inerconnected structures. IEEE Trans. Comput, 41, (7) :899?06
[26] 宣恒农．怎样把BGM测试模型表示为一个方程．计算机工程与应 用，2001，23
[27] 宣恒农．Chwa&Hakimi测试模型的方程表示．计算机工程，2001，27(10) ：
39～40
[28] 谢兵．基于CORBA技术和系统级故障诊断算法的多网管系统．邵阳师范高 等专科学校学报，2001，23(2) ：53～55
[29] 谢兵．基于比较的异步总线差错控制．邵阳师范高等专科学校学报， 2000，22(2) ：25～28
[30] 陈兴华．系统级故障诊断有效算法的分析与研究：[硕士学位论文]．长沙： 湖南大学计算机与通信学院，2000
[31] Hsien-Sheng Hsiao Yeh-hao chin, Wei-pang Yang. Reaching fault diagnosis agreement under a hybrid fault model [J]. IEEE Trans. On Computers, 2000,49(9)
[32] 谢高岗、张大方、闵应华等．层次式网络管理系统研究与实现．见：面向新 世纪的中国测试技术(2000年全国测试学术会议论文集)．北京：装甲兵学院， 2000
[33] 杨雅辉、王行刚．一种面向对象的被管网络资源的管理维护模型．计算机 学报，1999，22(8)
[34] 胡谷雨．网络管理系统的综合．电信科学，1999，(9)
[35] 李天剑、曾文方．网络管理协议的分析与展望．计算机系统应用，1999，(5)
[36] 张大方．系统级故障诊断的矩阵方法．计算机工程与科 学，1996，(2) ：173～177
[37] 闵应骅．容错计算二十五年．计算机学报，1995，(12) ：930～941
[38] 李兢，李长林，申石虎．关于图的极大独立点集的理论及生成方法．电子 学报，1995，(8) ：78～79
[39] 蔡兵，周六丁，陈廷槐．关于链路故障的分布式故障诊断．计算机科学， 1994，21：72～74
[40] 冯斐玲，吴荣泉．一种可变结构分布式系统的故障诊断．计算机学 报，1993，(1) ：73～76
[41] 史维更．一个新系统诊断模型．计算机学报，1986，(9) ：273～280
[42] 万兆泉等．Delphi 5编程指南．北京：北京希望电子出版社，2000
[43] R．Otte，P．Patrick，M．Roy．CORBA教程-公共对象请求代理体系结构．北 京：清华大学出版社，1999
[44] 岑贤道、安常青．网络管理协议及应用开发．北京：清华大学出版社，1998
[2] Bassi F, Gradoni F, Meastrini P. A theory of diagnosability Aithout repair. IEEE Trans Comput, 1976 (C-25) : 585?93
[3] Chwa K Y, Hakimi S L. Scheme for Fault-tolerant Computing: a Comparison of Modularly Redundant and t-diagnosable System. Information Control, 1981, 49:212?38
[4] Malek M. A comparison connection assignment for diagnosis of multiprocessor systems. In: Proc. 7th Symp. Comput Architecture. IEEE, 1980:31 ?35
[5] Hakimi S L and Amin A T. Characterization of the connection assignment of diagnosable systems. IEEE Trans. Comp. ,1974, (1) :86?8
[6] 张大方，江招生．基于集团的系统级故障诊断研究．计算机学 报，1998，21(4) ：308～314
[7] 张大方等．基于矩阵的极大独立点集生成算法．电子学报，1999，(1) ：202～206
[8] Andrzej P. Optimaal diagnosis of heterogeneous systems with random faults. IEEE Trans. Computer, 1998, 47(3) :298?04
[9] Sunggu Lee, Kang Geun Shin. Probabilistic Diagnosis of Multiprocessor Systems. ACM Computing Surveys, March 1994,26(1) :121 ?39
[10] Lee S and Shin K G. Optimal and efficient probabilistic distributed diagnosis schemes. IEEE Trans. Comput, 1993, (7) :882?86
[11] Horst R, Jarett D, and Lenoski D. The risk of data corruption in microprocessor-based systems. Dig. Papers, FTCS-23, 1993, (7) :576?85
[12] Blough and Pelc A. Diagnosis and repair in multiprocessor systems. IEEE Trans. Comput, 1993, (2) :205?17
[13] Bianchini R P, Buskens R W. Implementation of On-Line Distributed
Ssytem-level Diagnosis Theory. IEEE Trans. Comput, 1992, 41 (30) :616?25
[14] 01son L, Blackwell A. Understanding network management with OOA. IEEE Network Magazine, 1990, (4)
[15] Bianchini R P, Goodwin K, Nydick D S. Practical Application and Implementation of distributed system-level diagnosis theory. In: Proc 20th Symp. Fault Tolerance Comput. IEEE, 1990:332?39
[16] Stefano Chessal and Paolo Santi2． Comparison-Based System-Level Fault Diagnosis in Ad-Hoc Networks[C]. Proc. In:IEEE SRDS 2001, Symposium on Reliable and Distributed Systems. New Orleans, October 2001
[17] Somani A K, Agrawal V K, and Avis D. A generalized theory for system level diagnosis. IEEE Trans. Comput, 1987, (6) :560?66
[18] Hoseini S H, Kuhl J G, Reddy S M. A diagnosis algorithm for distributed computing system with dynamic failure and repair. IEEE Trans. Comput, 1984, 33:223?33
[19] Hakimi S L, Nakajima K. On adaptive system diagnosis. IEEE Trans. Comput, 1984, (3) :234?40
[20] Kuhl J G and Reddy S M. Distributed fault-tolerance for large multiprocessor systems. 7th Symp. on Computer Architecture, ACM, New York, 1980,23?0
[21] Maheswari S H, Hakimi S L. On models for diagnosable systems and probabilistic fault diagnosis. IEEE Trans. Comput, 1976, (3) :228?36
[22] Huang, S. XU, J., and Chen T.. 1989 Characterization and design of sequentially t_diagnosagle systems. Dia. Pagers, FTCS-19, (7) :554?59
[23] Berman P, Pelc A. Distributed probabilistic fault diagnosis in multiprocessor systems. Dig. Papers FTCS-20, (7) :340?46
[24] Yang C L, Masson.G M. A distributed algorithm for fault diagnosis in systems with soft failures. IEEE Trans. Comput, 37(11) : 1476?479
[25] Somani A K, Agrawal V K. Diagnosis algorithms for regular inerconnected structures. IEEE Trans. Comput, 41, (7) :899?06
[26] 宣恒农．怎样把BGM测试模型表示为一个方程．计算机工程与应 用，2001，23
[27] 宣恒农．Chwa&Hakimi测试模型的方程表示．计算机工程，2001，27(10) ：
39～40
[28] 谢兵．基于CORBA技术和系统级故障诊断算法的多网管系统．邵阳师范高 等专科学校学报，2001，23(2) ：53～55
[29] 谢兵．基于比较的异步总线差错控制．邵阳师范高等专科学校学报， 2000，22(2) ：25～28
[30] 陈兴华．系统级故障诊断有效算法的分析与研究：[硕士学位论文]．长沙： 湖南大学计算机与通信学院，2000
[31] Hsien-Sheng Hsiao Yeh-hao chin, Wei-pang Yang. Reaching fault diagnosis agreement under a hybrid fault model [J]. IEEE Trans. On Computers, 2000,49(9)
[32] 谢高岗、张大方、闵应华等．层次式网络管理系统研究与实现．见：面向新 世纪的中国测试技术(2000年全国测试学术会议论文集)．北京：装甲兵学院， 2000
[33] 杨雅辉、王行刚．一种面向对象的被管网络资源的管理维护模型．计算机 学报，1999，22(8)
[34] 胡谷雨．网络管理系统的综合．电信科学，1999，(9)
[35] 李天剑、曾文方．网络管理协议的分析与展望．计算机系统应用，1999，(5)
[36] 张大方．系统级故障诊断的矩阵方法．计算机工程与科 学，1996，(2) ：173～177
[37] 闵应骅．容错计算二十五年．计算机学报，1995，(12) ：930～941
[38] 李兢，李长林，申石虎．关于图的极大独立点集的理论及生成方法．电子 学报，1995，(8) ：78～79
[39] 蔡兵，周六丁，陈廷槐．关于链路故障的分布式故障诊断．计算机科学， 1994，21：72～74
[40] 冯斐玲，吴荣泉．一种可变结构分布式系统的故障诊断．计算机学 报，1993，(1) ：73～76
[41] 史维更．一个新系统诊断模型．计算机学报，1986，(9) ：273～280
[42] 万兆泉等．Delphi 5编程指南．北京：北京希望电子出版社，2000
[43] R．Otte，P．Patrick，M．Roy．CORBA教程-公共对象请求代理体系结构．北 京：清华大学出版社，1999
[44] 岑贤道、安常青．网络管理协议及应用开发．北京：清华大学出版社，1998