离散事件系统故障的极小观测序列

欧阳丹彤　李江娜　耿雪娜

摘要：为了提高可诊断离散事件系统故障的在线诊断效率，本文从判定故障发生的可观测事件的角度，提出了故障极小观测序列方法。文中选取有限状态自动机对离散事件系统进行建模。首先，在离线状态下，建立系统的故障模型，以排除对于判定系统故障无关的路径。然后，根据故障模型进一步建立判定系统故障的极小观测序列模型。当离散事件系统在线诊断时，仅需将逐步增加的在线观测事件序列与故障的极小观测序列模型进行比对。若能找到满足该模型的任何一条路径，则说明路径终止状态上故障标签对应的系统故障发生；否则，说明系统无故障发生。文中对可诊断离散事件系统进行实验对比，通过故障的极小观测序列模型能尽快判定有无故障发生，以及发生了哪些故障。该模型能有效地缩小系统在线诊断的时间，提高系统在线诊断的效率。

关键词：离散事件系统；故障模型；极小观测序列模型；故障诊断

中图分类号：TP301 文献标识码：A

近些年来，基于模型诊断方法成为人工智能领域比较热门的研究课题。基于模型诊断方法具有设备独立性，易于更新和维护。因而，不少领域使用基于模型诊断方法对离散事件系统进行诊断研究，比如大型通信网络故障诊断、配电站故障诊断、航天器故障诊断、汽车故障诊断、软件测试等。基于模型诊断中诊断相关的极小化研究增强了诊断的精细程度。诊断相关的极小化研究包括：极小诊断、极小故障事件集、判定可诊断性的极小事件集等。极小诊断是在部件级别上对故障部件的候选冲突集进行求碰集，从而得到故障部件的诊断结果。使用不同的方法求碰集，得到系统极小诊断的效率有所不同。例如，通过减少一致性检测的数量，避免对极小化冲突集的计算，求解系统的极小诊断。极小故障事件集则考虑故障事件的先后顺序对系统的影响，将故障事件构成的序列进行极小化，从而得到系统故障事件的极小序列诊断。而可诊断性的极小事件集则是通过减少可观测事件的种类，使系统仍保持可诊断性，求解保证系统可诊断性的极小事件集。以上极小化相关研究都未曾从在线诊断角度考虑如何尽快地确定发生的故障。为了提高系统在线诊断的效率，使在线诊断时尽快地判定出故障的发生，本文对判定故障发生的可观测事件序列进行研究并建立相应的模型，使得在系统故障发生后尽快确定该故障的发生。假定待测的离散事件系统是完备且可诊断的。

本文给出了判定系统故障发生的极小观测序列模型G_mos以及建立故障极小观测序列模型的算法（约束转换法）。对于给定的离散事件系统，首先建立该系统模型相对应的故障模型G_f，然后在故障模型基础上求得系统故障的极小观测序列模型G_mos。通过故障的极小观测序列模型可以得到某个或某类故障发生的极小观测序列集。这样，系统在线实时诊断时，将传感器逐步接收到的观测与系统故障的极小观测序列模型进行比对，若满足该模型中的某个观测序列，则说明系统发生了该序列终止状态标签相对应的故障；否则，系统判定没有故障发生。根据系统故障的极小观测序列模型，能在故障发生后尽快地判定出系统发生了哪些故障。

本文结构如下：第1部分给出了相关概念和定义；第2部分给出了故障极小观测序列模型的构建算法（约束转换法）；第3部分给出了相关证明；第4部分给出了实验及分析；第5部分对本文工作进行总结。

1 预备知识

本部分给出了文中相关的概念及模型的定义。

定义1（系统模型）

系统模型是一个有限自动机G_s=（S，E，T，S₀，S_f）。其中S为状态集合；S₀为初始状态；S_f为终止状态集合；T为状态转换函数集合，T→S×E×S。E为事件集合，包括可观测事件集E和不可观测事件集E_uo，E_uo又分为故障事件集和非故障事件集。

定义2（观测可达） 状态s_i∈S经事件e∈E。可达状态s_i∈s（其中s_i和s_j间事件除e外还可存在非连续的不可观测事件）则称s_i在e下可达，记作s_i[e]。状态s_i称为观测可达状态，记作R（s_i，e）。

图2中表示观测可达的几种情况，其中a，b∈E_o，v，u∈E_uo，则有R（S₀，a）={S₁}，R（S₁，b）={S₂，S₃}，R（S₃，c）={S₅}。

为了便于对系统模型中故障进行筛选，给出了故障模型的定义。

为提出建立故障模型的算法，给出以下定义。

由于传感器无法观测到不可观测事件，现定义观测。

本文目的是求解系统故障的极小观测序列模型，因此定义了故障的极小观测序列以及故障的极小观测序列模型。

定义7（故障的极小观测序列）

存在可观测事件序列o₁o₂…o_n和o₁o₂…o_no_n+1…o_n+k（其中o₁，…，o_n+k∈E₀且k>0）均可判定某故障发生，而序列o₁o₂…o_n-1无法确定该故障发生，则称序列o₁o₂…o_n为该故障的极小观测序列。所有故障的极小观测序列构成的模型称为系统故障的极小观测序列模型。

图1当接收到观测a，无法判定f发生，a6能判断f发生，abc也可以，可见a6为判定f发生的一个极小观测序列。

根据模型中状态标签的不同，提出了定义模糊状态和标签可达。

定义9（模糊状态） 状态x_i∈X中既含标签F∈F^*又含标签N，则x_i为模糊状态。

定义10（标签可达） 模糊状态x_i∈X，存在可观测事件e∈E_o'，若仅使得带标签N的状态s_ij其中（s_ij，N）∈i）可达，称x_i在e下N标签可达；若仅使带标签F∈F^*的状态可达，称x_i在e下F标签可达；若同时存在，称x_i在e下NF标签可达。

T_mos（x_i，e）定义之前，先定义局部转换函数T_mos（（s_ij，l（s_ij）），e），来表示状态间通过事件连接的关系（其中（s_ij，l（s_ij））∈x_i）。

根据以上对3种状态下转换函数的定义，可知终止状态可由仅含N标签状态、模糊状态以及仅含F标签状态经转换函数T_mos得到。

2 故障的极小观测序列模型

2.1 故障模型

建立系统故障的极小观测序列模型需要给定系统的故障模型，本节首先给出了算法1（筛选法）用于构建系统的故障模型。

算法1构建系统模型Gra_s的故障模型Gra_f

算法1中2-5行将系统模型图Gra_s中故障路径集合t_f加入到图Gra_f。7-9行每条故障路径t_fi∈t_f，找到其预故障路径t_pf，取得与观测obs（t_pfi）有相同部分观测的路径t，将t加入到图Gra_f中。

2.2 极小观测序列模型构建算法

根据系统的故障模型建立判定故障发生的极小观测序列模型。本节给出了算法2（约束转换法）用于构建系统故障模型的极小观测序列模型。

算法2 构建系统故障模型Gra_f的极小观测序列模型Gra_mos

算法2中第2行的isNotEnd（X_i）表示X_i节点不为终止节点，isTerminal（X_i）表示X_i节点为终端节点。第7行的Gra_mos←（X_i-→xH_i+1）表示将由状态X_i通过事件e到状态XH_i+1的状态转换加入到极小观测序列模型的图Gra_mos中。3-9行表示Gra_mos中仅含N标签的节点进行状态转换。10-23行表示模糊节点进行状态转换，包括NF标签可达（12-16行）和F标签可达（17-21行）。24-30行表示Gra_mos中仅含F标签的节点进行状态转换。

算法2中trans（（s_i，z（s_i）），P）表示状态的局部转换函数。

函数trans（（s_i，l（s_i）），P）的第1行R（s_i，e）表示状态s_i通过事件e所有可达状态构成的集合；2-3行指故障不包含在路径t（s_i，r）时，转换后标签不变；4-8行指故障包含在路径时，转换后状态标签的情况：5-6行指原有状态标签为N时，转换后状态标签为故障标签；7-8行指原有状态标签为故障标签时，转换后状态标签为两个标签的并集。

3 证明

算法2求得的极小观测序列模型包含系统中所有故障的所有极小观测序列。

证（正确性） 极小观测序列模型中终止状态出现在三种状态转换后：模糊状态、仅含有N标签的状态以及仅含有F标签的状态。由于系统是可诊断的，则故障标签一定可以分离。对于模糊状态（或者仅含有F标签的状态）经转换到终止状态的过程为故障分离的过程，而且首次进行分离，所以满足极小性；而对于仅含有N标签的状态，经转换到终止状态的过程为正常状态首次到达的含有F标签的状态，所以满足极小性。可见，极小观测序列模型中的序列满足极小性。

（完备性） 极小观测序列模型是根据故障模型得到的，需要证明故障模型是完备的。故障模型由系统模型中的故障路径以及与预故障路径相同部分观测的路径组成。故障的极小观测序列一定存在于故障路径中，故障发生后，影响故障发生判定的路径只有与预故障路径相同部分观测的路径，所以故障模型是完备的，则极小观测序列模型也是完备的。

（复杂性分析） 极小观测序列模型的在线诊断时间取决于实时接收的观测与离线建立的极小序列模型的比较时间，当观测序列长度为n时，比较时间复杂度为0（n），故在线诊断的时间复杂度为0（n）。

4 实验及实例分析

4.1 实验

由于本文的研究建立在完备且可诊断的离散事件系统基础上，且此类研究没有统一的benchmark数据测试集，故选取相关论文中满足本文假设的部分系统模型以及满足条件的系统模型进行以下两种对比实验。情形1：使用系统故障的极小观测序列模型，记作Mos；情形2：不使用故障的极小观测序列模型，记作Ori。对于相同长度的故障极小观测序列且相同节点个数的系统（单故障系统）进行实验，分别得到Mos和Ori的在线诊断的时间如表1所示：

实验数据表明，在相同条件的系统中，Mos诊断时间均比Ori短，为了更形象地说明两者的时间差距，诊断时间差图3如下。

由图3可得，对于单故障系统，Mos的故障诊断时间均比Ori的故障诊断时间短，即Mos下，系统有较高的诊断效率。尤其对于节点个数多且故障极小观测序列较长的系统模型，Mos比Ori在线诊断时间有更好的优势。

实验表明：离线建立系统的极小观测序列模型用于在线故障诊断，能有效地提高系统在线故障诊断的效率。既能够尽快地发现故障发生，也能尽快地排除故障的发生。

4.2 实例分析

图4为多故障系统模型G5，根据算法2得到该系统故障的极小观测序列模型G_mos，如图5所示。可得故障f₁的极小观测序列为abc，acb，故障f_i的极小观测序列为abb。

系统在初始状态0下，当接收到观测a时，在G_mos中存在可达状态，当再接收到观测c，也有可达状态，若继续接收到观测6到达G_mos中的带标签F₁的终止节点，此时可以判定故障f₁发生。同理，当接收到观测序列abc，可判定故障f₁发生；接收到观测abb，可判定故障f_i发生。

5 结论

本文提出了系统故障的极小观测序列模型，用于提高系统在线故障诊断的效率。文中给出了相关概念定义以及构建系统故障的极小观测序列模型的算法，而且通过对比实验证明了将故障的极小观测序列模型用于系统在线故障诊断，可以有效地减少系统故障诊断的时间，从而使系统尽快地判定有无故障发生。