A polynomial algorithm for testing diagnosability of discrete-eventsystems

Failure diagnosis in large and complex systems is a critical task. In the realm of discrete-event systems, Sampath et al. (1995) proposed a language based failure diagnosis approach. They introduced the diagnosability for discrete-event systems and gave a method for testing the diagnosability by first constructing a diagnoser for the system. The complexity of this method of testing diagnosability is exponential in the number of states of the system and doubly exponential in the number of failure types. We give an algorithm for testing diagnosability that does not construct a diagnoser for the system, and its complexity is of fourth order in the number of states of the system and linear in the number of the failure types     

A new algorithm for testing diagnosability of fuzzy discrete event systems

Failure diagnosis and detection of fuzzy discrete event systems play a significant role in the study of complex systems. In this paper, we investigate the diagnosability of fuzzy discrete event systems by proposing a new algorithm based on the concept of undistinguishable strings. Moreover, a necessary and sufficient condition for fuzzy diagnosability is obtained in terms of certain properties of the diagnoser, which is constructed with respect to the minimal observable event. The computing process to check the diagnosability of fuzzy DESs and some examples serving to illuminate the applications are developed and described.     

控制系统可诊断性的内涵与研究综述

作为表征控制系统故障诊断能力的属性, 故障可诊断性揭示了故障诊断深层次的内涵.将可诊断性分析纳入控制系统与诊断方案的设计环节, 可以从根本上提高系统对故障的诊断能力, 为研究故障诊断提供新的思路.本文分别从可诊断性的内涵、研究现状以及潜在发展趋势三个角度系统地对可诊断性进行分析.首先, 从定义、影响因素、与已有概念的关系以及应用四个方面剖析了控制系统可诊断性的内涵和研究意义.其次, 分别从可诊断性评价与设计两个方面对可诊断性的研究现状进行分析.最后, 通过对可诊断性已有成果进行总结归纳, 探讨了可诊断性研究存在的不足以及未来发展的趋势.     

Polynomial-time verification of diagnosability of fuzzy discrete event systems

A fuzzy approach to perform diagnosis of fuzzy discrete event systems(FDESs)is proposed by constructing diagnosers,which may more effectively cope with the problems of vagueness and fuzziness arising from failure diagnosis of fuzzy systems.However,the complexity of constructing this kind of diagnosers is exponential in the state space and the number of fuzzy events of the system.In this paper,we present an algorithm for verifying the diagnosability of FDESs based on the construction of a nondeterministic automaton called F-verifier instead of diagnosers.Both the construction of F-verifiers and the verification of diagnosability of FDESs can be realized with a polynomial-time complexity.     

基于比较诊断模型的超立方网络诊断算法

一个有效的诊断算法对多处理器系统而言极其重要。在多处理器系统中,识别所有故障节点的能力称为诊断系统的诊断度。在比较模型下,诊断 的执行是通过一个比较器处理器,给与之相邻的一对处理器发送相同的输入信号,并比较两者间的响应状态。为了提高超立方网络的诊断度,提出了一种新型的基于比较模型的超立方故障诊断算法,其利用超立方网络节点连接的特性生成一个拓扑图ES(k;n),最终得出一个3位二进制的诊断症候集,从而确定系统故障节点。该算法的诊断度最优能达到4n,大于传统超立方的诊断度n。     

A review of the diagnosability of control systems with applications to spacecraft

To achieve the safe, reliable autonomous operation of spacecraft, research on the fault diagnosis of control systems has attracted the attention of engineers and academicians throughout the aerospace field. Diagnosability can characterize the fault diagnosis capability of control systems. Connecting diagnosability analysis to the design of a spacecraft control system’s structure and diagnosis method can fundamentally improve the system’s fault diagnosis capability, improving the safety and reliability of autonomous spacecraft operation. In this paper, the diagnosability of spacecraft control systems is systematically studied from five perspectives: necessity, the current research status, the connotation, a novel index system and current development trends of diagnosability. First, the current status of spacecraft reliability analysis and reliability-based design is briefly reviewed, and existing problems are described, highlighting the advantages and importance of diagnosability research. Furthermore, the basic concepts of diagnosability are briefly introduced. By analyzing the current status of existing research on the diagnosability of both general and spacecraft control systems, the application scope of the diagnosability of spacecraft control systems is summarized. Moreover, the definition and influencing factors of the diagnosability of spacecraft control systems are presented to refine existing concepts, and a universal evaluation index system is proposed for the diagnosability of spacecraft control systems to further enhance the applicability of diagnosability evaluation and diagnosability-based design to spacecraft. Finally, the existing shortcomings and future development trends of diagnosability research for spacecraft control systems are discussed.     

Access point selection in heterogeneous wireless networks using belief propagation

The next generation wireless network will be composed by various heterogenous wireless access networks,such as cellular network,worldwide interoperability for microwave access(WiMAX),wireless local area network(WLAN),etc.Different access networks cooperatively provide high-bandwidth connectivity with bandwidth guarantees.This paper proposes a utility-based access point selection scheme,which selects an accessible point for each user,such that the bandwidth requirement of each user is satisfied,and also the defined utility function is maximized.Due to the NP-complete nature of the problem,the existing proposals apply the greedy method to find a solution.We find that belief propagation is an efficient tool to solve this problem,and thus,we derive the same optimization objective in a new way,and then draw a factor graph representation which describes our combinatorial optimization problem.Afterwards,we develop the belief propagation algorithm,and show that our algorithm converges.Finally,we conduct numerical experiments to evaluate the convergency and accuracy of the belief propagation in load balancing problem.     

动态系统实际故障可诊断性的量化评价研究

提出了一种新颖的动态系统实际故障可诊断性量化评价方法. 该方法无需设计任何诊断算法, 仅通过解析模型即可给出动态系统故障检测和隔离的难易程度, 从而为实现在系统设计阶段提高故障诊断能力的工程目标提供理论指导和参考依据. 首先, 通过标准化模型和等价空间变换, 将状态空间描述的随机动态系统实际故障可诊断性评价问题转化为概率统计中多元分布相似度判别的数学问题; 然后, 根据严格的数学证明, 指出距离相似度判别准则在进行可诊断性量化评价中存在的不足. 进而, 为弥补该不足, 利用故障矢量的分布概率以及不同故障矢量之间的余弦相似度, 设计基于方向相似度的可诊断性量化评价新方法; 最后, 通过数学仿真验证该方法的有效性和优越性.     

具有多项式时间复杂性的离散事件系统安全诊断

离散事件系统的故障诊断能将已发生的不可观故障事件及时诊断出来,但往往容易忽略故障诊断期间系统的安全性.为解决这一问题,提出了一种具有多项式时间复杂性的安全故障诊断方法.先对离散事件系统的安全可诊断性进行了形式化,再通过构造一个非法语言识别器对系统被禁止操作序列进行识别,并在此基础上构建了一个对系统实施安全诊断的安全验证器,得到了一个关于离散事件系统安全可诊断性的充分必要条件,实现了对系统的安全故障诊断.同时,通过对安全验证器的构建与安全可诊断性的判定的复杂性分析,得到了该安全故障诊断方法可在多项式时间内实现等结论.     

Diagnosability of delay-deadline failures in fair real time discrete event models

In this article a method for failure diagnosis of real time discrete event systems (RTDES) with ‘fairness of traces’ has been developed. Discrete event system (DES) modelling framework with provision for associating timing information with the transitions are required for handling real time systems. RTDES models and timed DES (TDES) models are examples of such modelling frameworks. Failure diagnosis in untimed DES models enables only the study of diagnosability of failures resulting in a change in the logical behaviour of the failed system. In addition to logical failures, failure diagnosis in RTDES and TDES models also enables diagnosability of failures that change the timing behaviour of the system but maintain the logical behaviour. Many systems exhibit fairness of traces with respect to transitions in the sense that any trace that visits a state infinitely often has infinitely many occurrences of all the transitions that emanate from that state. The abstraction employed in obtaining their (timed) DES models often obliterates this property. The RTDES and TDES diagnosability conditions, proposed in the literature and which do not consider fairness, are shown to be inadequate in this article. A new diagnosability condition is achieved by taking into account this fairness property in the RTDES models and shown to be necessary and sufficient for such systems. An analysis of time complexity for analysing the diagnosability of systems with fairness of traces is presented.     

Safe diagnosability for fault-tolerant supervision of discrete-event systems

The problem of achieving fault-tolerant supervision of discrete-event systems is considered from the viewpoint of safe and timely diagnosis of unobservable faults. To this end, the new property of safe diagnosability is introduced and studied. Standard definitions of diagnosability of discrete-event systems deal with the problem of detecting the occurrence of unobservable fault events using model-based inferencing from observed sequences of events. In safe diagnosability, it is required in addition that fault detection occur prior to the execution of a given set of forbidden strings in the failed mode of operation of the system. For instance, this constraint could be required to prevent local faults from developing into failures that could cause safety hazards. If the system is safe diagnosable, reconfiguration actions could be forced upon the detection of faults prior to the execution of unsafe behaviour, thus achieving the objective of fault-tolerant supervision. Necessary and sufficient conditions for safe diagnosability are derived. In addition, the problem of explicitly considering safe diagnosability in controller design, termed “active safe diagnosis problem”, is formulated and solved. A brief discussion of safe diagnosability for timed models of discrete-event systems is also provided.     

Diagnosability of Fuzzy Discrete-Event Systems: A Fuzzy Approach

In order to more effectively cope with the real-world problems of vagueness, fuzzy discrete-event systems (FDESs) were proposed by Lin and Ying recently. Then we and Cao and Ying investigated the supervisory control of FDESs independently. In this paper, we are concerned with another important issue of FDESs, the failure diagnosis. More specifically: (1) we propose a ldquofuzzy diagnosabilityrdquo approach by introducing a fuzzy diagnosability function to characterize the diagnosability degree, which takes values in the interval [0,1] rather than { 0,1}; (2) based on the observability of events, we formalize the construction of the diagnosers that are used to perform fuzzy diagnosis; (3) a number of basic properties of the diagnosers are investigated. In particular, we present a necessary and sufficient condition for failure diagnosis of FDESs. Our results generalize the important consequences of the diagnosability for crisp discrete-event systems (DESs) introduced by Sampath et al. The newly proposed approach allows us to deal with the problem of diagnosability for both crisp DESs and FDESs; (4) in addition, a method for checking the fuzzy diagnosability for FDESs is proposed. Also, some examples are provided to illustrate the application of the diagnosability of FDESs.     

Failure diagnosis of discrete-event systems with linear-time temporal logic specifications

The paper studies failure diagnosis of discrete-event systems (DESs) with linear-time temporal logic (LTL) specifications. The LTL formulas are used for specifying failures in the system. The LTL-based specifications make the specification specifying process easier and more user-friendly than the formal language/automata-based specifications; and they can capture the failures representing the violation of both liveness and safety properties, whereas the prior formal language/automaton-based specifications can capture the failures representing the violation of only the safety properties (such as the occurrence of a faulty event or the arrival at a failed state). Prediagnosability and diagnosability of DESs in the temporal logic setting are defined. The problem of testing prediagnosability and diagnosability is reduced to the problem of model checking. An algorithm for the test of prediagnosability and diagnosability, and the synthesis of a diagnoser is obtained. The complexity of the algorithm is exponential in the length of each specification LTL formula, and polynomial in the number of system states and the number of specifications. The requirement of nonexistence of unobservable cycles in the system, which is needed for the diagnosis algorithms in prior methods to work, is relaxed. Finally, a simple example is given for illustration.     

Diagnosability of fuzzy discrete event systems

In this paper, discrete event systems (DESs) are reformulated as fuzzy discrete event systems (FDESs) and fuzzy discrete event dynamical systems (FDEDSs). These frameworks include fuzzy states, events and IF-THEN rules. In these frameworks, all events occur at the same time with different membership degrees. Fuzzy states and events have been introduced to describe uncertainties that occur often in practical problems, such as fault diagnosis applications. To measure a diagnoser’s fault discrimination ability, a fuzzy diagnosability degree is proposed. If the diagnosability of the degree of the system yields one a diagnoser can be implemented to identify all possible fault types related to a system. For any degree less than one, researchers should not devote their time to distinguish all possible fault types correctly. Thus, two different diagnosability definitions FDEDS and FDES are introduced. Due to the specialized fuzzy rule-base embedded in the FDEDS, it is capable of representing a class of non-linear dynamic system. Computationally speaking, the framework of diagnosability of the FDEDS is structurally similar to the framework of diagnosability of a non-linear system. The crisp DES diagnosability has been turned into the term fuzzy diagnosability for the FDES. The newly proposed diagnosability definition allows us to define a degree of diagnosability in a class of non-linear systems. In addition, a simple fuzzy diagnosability checking method is introduced and some numerical examples are provided to illustrate this theoretical development. Finally, the potential applications of the proposed method are discussed.     

赋时离散事件系统的安全诊断

针对一类计时或非计时自动机模型,研究其赋时离散事件系统(TDES)故障诊断的安全性问题.首先对TDES的安全可诊断性进行形式化;然后通过构造一个非法语言识别器对被禁止危险操作序列进行识别,在此基础上构建一个安全诊断器,提出一种基于安全诊断器的安全诊断方法,并得到一个关于TDES安全可诊断性的充分必要条件,从而实现TDES的安全故障诊断.     

Diagnosability of discrete-event systems

Fault detection and isolation is a crucial and challenging task in the automatic control of large complex systems. We propose a discrete-event system (DES) approach to the problem of failure diagnosis. We introduce two related notions of diagnosability of DES's in the framework of formal languages and compare diagnosability with the related notions of observability and invertibility. We present a systematic procedure for detection and isolation of failure events using diagnosers and provide necessary and sufficient conditions for a language to be diagnosable. The diagnoser performs diagnostics using online observations of the system behavior; it is also used to state and verify off-line the necessary and sufficient conditions for diagnosability. These conditions are stated on the diagnoser or variations thereof. The approach to failure diagnosis presented in this paper is applicable to systems that fall naturally in the class of DES's; moreover, for the purpose of diagnosis, most continuous variable dynamic systems can be viewed as DES's at a higher level of abstraction     

基于比较模型的交换超立方网络的(t,k)诊断度研究

故障诊断问题已经被广泛讨论,许多互连网络的诊断度已被深入研究。(t,k)-诊断为最重要的系统级故障诊断策略之一,在故障节点不大于t的前提条件下,每次迭代均可以识别最少故障节点个数为k。针对如何提高交换超立方网络的诊断度的问题,进行了一个基于比较模型的(t,k)-诊断算法研究,根据连通图的特性对交换超立方网络进行连通分子的划分,并计算交换超立方连通图中连接边与节点间的量化关系,从而证明了交换超立方网络是(t,k)-可诊断的。最终表明,本算法下的诊断度,优于其传统精确诊断s 1。     

Diagnosability analysis of hybrid systems cast in a discrete-event framework

This paper addresses the problem of assessing the diagnosability of hybrid systems modeled by a hybrid automaton coupling methods from the continuous and the discrete event model-based diagnosis fields. The discrete states of the hybrid automaton represent the modes of operation of the system for which the continuous dynamics are specified. The diagnosability of the continuously-valued part of the model is first analyzed and the new concept of mode signature is shown to characterize mode diagnosability from continuous measurements. Continuous dynamics are then abstracted by defining a set of signature-events associated to mode signature changes, preserving this way mode diagnosability. The behavior of the abstract hybrid system is then modeled by a prefix-closed language over the original event alphabet enriched by these additional events. Based on this language, diagnosability analysis of the hybrid system is cast into a discrete-event framework and hybrid diagnosability conditions are provided. A case study based on the Attitude and Orbit Control System of a spacecraft illustrates the method.     

交换交叉立方网络的g正确邻结点条件诊断度研究

系统级故障诊断是保障多处理器计算机系统运行可靠性的一种重要手段。为了提高系统的诊断能力,增强系统的可靠性,在条件诊断度的基础上Peng等人进一步提出了[g]正确邻结点条件诊断度,[g]正确邻结点条件诊断度是一种更加适用于大规模多处理器计算机系统的故障诊断方式。以新型互连网络拓扑结构研究的最新成果--交换交叉立方网络为研究对象,在得到交换交叉立方网络的[Rg]点连通度的基础上,首次证得交换交叉立方网络[(ECQ(s,t))]在PMC模型下的[g]正确邻结点条件诊断度为[2g(s+2－g)－1],其中[t≥s>g],进而通过模拟实验验证了结论的正确性和有效性。该研究对于理清交换交叉立方网络的可靠性能并有效推动交换交叉立方网络的应用和推广,有着非常重要的理论价值和现实意义。     

Verification of robust diagnosability for partially observed discrete event systems

In this paper, we study robust failure diagnosis of discrete event systems. Given a set of possible models, each of which has its own nonfailure specification, we consider the existence of a single diagnoser such that, for all possible models, it detects any occurrence of a failure within a uniformly bounded number of steps. We call such a diagnoser a robust diagnoser. We introduce a notion of robust diagnosability, and prove that it serves as a necessary and sufficient condition for the existence of a robust diagnoser. We then present an algorithm for verifying the robust diagnosability condition.