Conditional diagnosability and strong diagnosability of shuffle-cubes under the comparison model

The growing size of multiprocessor systems increases the vulnerability to component failures. It is crucial to locate and replace faulty processors to maintain the system's high reliability. Processor fault diagnosis is essential to the reliability of a multiprocessor system and the diagnosabilities of many well-known networks (such as hierarchical hypercubes and crossed cubes [S. Zhou, L. Lin and J.-M. Xu, Conditional fault diagnosis of hierarchical hypercubes, Int. J. Comput. Math. 89(16) (2012), pp. 2152–2164 and S. Zhou, The conditional diagnosability of crossed cubes under the comparison model, Int. J. Comput. Math. 87(15) (2010), pp. 3387–3396]) have been investigated in the literature. A system is t-diagnosable if all faulty nodes can be identified without replacement when the number of faults does not exceed t, where t is some positive integer. Furthermore, a system is strongly t-diagnosable if it is t-diagnosable and can achieve (t+1)-diagnosability except for the case where a node's neighbours are all faulty. In addition, conditional diagnosability has been widely accepted as a new measure of diagnosability by assuming that any fault-set cannot contain all neighbours of any node in a multiprocessor system. In this paper, we determine the conditional diagnosability and strong diagnosability of an n-dimensional shuffle-cube SQ_n, a variant of hypercube for multiprocessor systems, under the comparison model. We show that the conditional diagnosability of shuffle-cube SQ_n (n=4k+2 and k≥2) is 3n?9, and SQ_n is strongly n-diagnosable under the comparison model.     

On conditional diagnosability and reliability of the BC networks

An n-dimensional bijective connection network (in brief, BC network), denoted by X _n , is an n-regular graph with 2 ⁿ nodes and n2 ^n?1 edges. Hypercubes, crossed cubes, twisted cubes, and Möbius cubes all belong to the class of BC networks (Fan and He in Chin. J. Comput. 26(1):84–90, [2003]). We prove that the super connectivity of X _n is 2n?2 for n≥3 and the conditional diagnosability of X _n is 4n?7 for n≥5. As a corollary of this result, we obtain the super connectivity and conditional diagnosability of the hypercubes, twisted cubes, crossed cubes, and Möbius cubes.     

基于不确定观测下离散事件系统可诊断性的研究

在实际应用系统中,由于传感器故障、传感器限制和网络中的数据包丢失等原因,事件的可观测值变得不确定,使得观测系统行为变得尤为复杂。针对离散事件系统中,同个事件串可能有多个观测值以及不同状态下同个事件观测值也可能不同的问题,提出一种不确定观测下故障诊断验证的方法。首先对不确定观测的离散事件系统的可诊断性进行形式化,然后构建出用于上述故障诊断验证的验证器;基于验证器提出了系统基于不确定观测下可诊断的充要条件及验证算法;最后,实例说明不确定观测下故障诊断验证算法的应用。与现有研究相比,提出的方法对故障事件的观测值没有约束,可以为0个或多个观测值,使此方法应用的场景更为广泛。     

Design for diagnosability of multistation manufacturing systems based on sensor allocation optimization

System monitoring and diagnosing can be achieved through measuring sensing data. Meanwhile, diagnosability is the capability of a system in terms of diagnosing dimensional variation and root cause identification. In order to obtain enough sensing data, special attention should be taken to the sensor allocation optimization within the framework of ensuring system diagnosability, which can lower sensing cost and reduce time to diagnosis. This paper investigates both theoretically and experimentally the effect of sensor allocation optimization on the diagnosability of a multistation manufacturing system (MMS). The design for diagnosability (DFD) is formulated and implemented in the early design phase. Three indices, namely detectability, locatability, and isolability, are proposed to measure the system diagnosability. A two-step process of diagnosing variation sources is presented to specify the variation transmission between stations and variation diagnosis within a station. An optimal methodology of sensor allocation is then proposed. A typical machining process is demonstrated as an example of the analytical procedure and reference for sensor allocation in practice. Four sensing strategies are conducted for performance comparison. Results indicate that the optimal sensor allocation yields less sensing cost and shorter time to diagnosis without loss of diagnosability.     

State Observation and Diagnosis of Discrete-Event Systems Described by Stochastic Automata

The problems ofstate observation and diagnosis are solved for discrete–eventsystems, which are described by stochastic automata. As manysystems are not observable in the sense that it is possible toreconstruct the state unambiguously, the observation problemis set up as the problem of determining the smallest possibleset of states that are compatible with the measured input andoutput sequences. The diagnostic problem is shown to be, in principle,an observation problem. Conditions for the observability anddiagnosability of stochastic automata are presented. The resultsare illustrated by examples.     

Conditional diagnosability of hypermesh optical multiprocessor systems under the PMC model

The hypermeshes are a family of promising optical interconnection topologies for multiprocessor systems. In this paper, the conditional diagnosability of the hypermesh optical multiprocessor systems, under the PMC model, is determined. We derive that the conditional diagnosability of k ⁿ -hypermesh is 4n(k?1)?4k+1, where n≥3 and k≥5. This result shows that the hypermesh optical multiprocessor systems possess strong self-diagnosing abilities.     

离散事件系统基于模式的安全故障诊断

基于模式的故障诊断方法能将触发系统故障的事件串诊断出来,但在诊断期间系统仍然可能执行被禁止的不安全操作.为此,提出了一种离散事件系统基于S型和T型模式的安全诊断方法.先对离散事件系统基于模式的安全可诊断性进行形式化,再通过构造非法语言识别器和安全诊断器对系统发生的故障模式实施安全诊断,最后分别得到了一个关于S型和T型模式的系统安全可诊断性的充分必要条件,实现了离散事件系统基于模式的安全故障诊断.     

面向系统级故障诊断的高效遗传算法

Elhadef和Ayeb首次提出采用遗传算法来进行系统级故障诊断,其适应度函数通过比较实际症候与当前猜测故障集产生的症候得到.上述算法的一个缺点是其适应度函数只考虑了故障集随机生成的一个症候,因而会漏掉绝大多数有效的故障集.对此首先针对PMC模型提出结点状态与诊断图中一定症候相容时结点状态应满足的方程,然后通过设计基于该方程的适应度函数,提出针对t-可诊断系统的遗传算法.理论分析和模拟实验均表明文中算法在迭代步数上大大地优于原算法.此外,还确认了Elhadef提出的产生初始种群的方法的高效性.     

基于状态估计的分布式离散事件系统可诊断性研究

针对分布式离散事件系统,提出了一种验证基于状态估计的分布式离散事件系统可诊断性的方法。首先对离散事件系统的可诊断性进行形式化定义,然后提出一种基于状态估计的分布式离散事件系统的可诊断性验证算法,进而推导出分布式离散事件系统可诊断的充分必要条件,最后结合实际算例对该算法的可行性进行验证分析。相比现有算法,本文提出的算法无需各站点进行实时同步,仅要求在有限时延内各站点间能进行通信即可,且算法的时间复杂度也明显降低。     

Diagnosis of Intermittent Faults

The diagnosis of intermittent faults in dynamic systems modeled as discrete event systems is considered. In many systems, faulty behavior often occurs intermittently, with fault events followed by corresponding reset events for these faults, followed by new occurrences of fault events, and so forth. Since these events are usually unobservable, it is necessary to develop diagnostic methodologies for intermittent faults. Prior methodologies for detection and isolation of permanent faults are no longer adequate in the context of intermittent faults, since they do not account explicitly for the dynamic behavior of these faults. This paper addresses this issue by: (i) proposing a modeling methodology for discrete event systems with intermittent faults; (ii) introducing new notions of diagnosability associated with fault and reset events; and (iii) developing necessary and sufficient conditions, in terms of the system model and the set of observable events, for these notions of diagnosability. The definitions of diagnosability are complementary and capture desired objectives regarding the detection and identification of faults, resets, and the current system status (namely, is the fault present or absent). The associated necessary and sufficient conditions are based upon the technique of diagnosers introduced in earlier work, albeit the structure of the diagnosers needs to be enhanced to capture the dynamic nature of faults in the system model. The diagnosability conditions are verifiable in polynomial time in the number of states of the diagnosers.