Computationally efficient algorithms for multiple fault diagnosis in large graph-based systems推荐.pdf

IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART A: SYSTEMS AND HUMANS, VOL. 33, NO. 1, JANUARY 2003 73 Computationally Efficient Algorithms for Multiple Fault Diagnosis in Large Graph-based Systems Fang Tu, Student Member, IEEE, Krishna R. Pattipati, Fellow, IEEE, Somnath Deb, Senior Member, IEEE, and Venkata Narayana Malepati, Member, IEEE Abstract— Graph-based systems are models wherein the nodes In this paper, we consider the multiple fault diagnosis MFD represent the components and the edges represent the fault propa- problem in graph-based systems represented by digraph models gation between the components. For critical systems, some compo- DG , wherein denotes the set of components or nents are equipped with smart sensors for on-board system health management. When an abnormal situation occurs, alarms will be tests, and an edge denotes the fact that a fault triggered from these sensors. This paper considers the problem at node propagates to node . Based on fault propagation of identifying the set of potential failure sources from the set of times, systems are classified into two categories: zero-time and ringing alarms in graph-based systems. However, the computa- nonzero-time systems. In the zero-time systems, fault propa- tional complexity of solving the optimal multiple fault diagnosis gation appears to be instantaneous to an observer (a human (MFD) problem is exponential. Based on Lagrangian relaxation and subgradient optimization, we present a heuristic algorithm to being or a machine). These systems are abstracted by taking the find approximately the most likely candidate fault set. A computa- propagat