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.     

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

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.     

Decentralized fault diagnosis approach without a global model for fault diagnosis of discrete event systems

Diagnosability property ensures that a predefined set of faults are diagnosable by a centralized diagnoser built using a global model of the system, while co-diagnosability guarantees that these faults are diagnosed in decentralized manner using a set of local diagnosers. A fault must be diagnosed by at least one local diagnoser by using its proper local observation of the system. The aim of using decentralized diagnosis approaches is to overcome the space complexity and weak robustness of centralized diagnosis approaches while at the same time preserving the diagnostic capability of a centralized diagnosis. However, co-diagnosability property is stronger than diagnosability property. If a system is co-diagnosable, then it is diagnosable, while a diagnosable system does not ensure that it is co-diagnosable. Therefore, the challenge of decentralized diagnosis approaches is to perform local diagnosis and to verify that it is equivalent to the centralized one without the need for a global model. In this paper, an approach is proposed to obtain co-diagnosable decentralized diagnosis structure of discrete event systems without the use of a global model. This approach is based on the synchronization of local diagnosis decisions in order to solve the ambiguity between local diagnosers. This synchronization allows obtaining local diagnosis equivalent to the global one without the use of a global model.     

An analysis of self-diagnosis model by conditional fault set

Diagnosability and syndrome decoding of a self-diagnosis model is studied with a conditional fault set. The conditional fault set is a fault set which is induced under such a condition that some subset of units are faulty (or fault-free).The diagnosability defined on the model is generalized to include such information as (1) the maximum number of units to be identified as faulty; (2) the maximum number of units to be identified as fault-free; and (3) the maximum number of units whose states are definitely identified, when the upper bound on the number of faulty units is assumed.Furthermore, we discuss the problem of finding minimal fault set. This problem is formulated in mathematical programming with the conditional fault set. A syndrome decoding algorithm is also presented which uses the conditional fault set in a similar manner to Hamming distance used in syndrome decoding of error-correcting codes.