分布式离散事件系统的模式故障预测研究

吕舒园，刘富春，赵 锐，邓秀勤，崔洪刚,3

（1.广东工业大学 计算机学院，广东 广州510006；2.广东工业大学 应用数学学院，广东 广州510520；3.东源县科技创新中心，广东 河源517500）

离散事件系统是一种在离散状态和事件上建模的系统。事件集被划分为可观事件集(如传感器的读数)和不可观事件集(如无法被观测到的信息)，其中故障事件一般属于不可观事件。离散事件系统的故障预测是通过观测一系列可观事件序列来预测故障是否将会发生，以提前做出相应的预防措施，因此，研究离散事件系统的故障预测问题，可以增强系统的稳健性和抗风险的能力，具有重要的研究意义和应用价值。故障预测方法被广泛应用于计算机文件处理系统、暖通空调系统、电力系统、智能通讯系统等。

针对离散事件系统的故障诊断研究，已经有大量的相关文献提出了各种诊断算法，其中在1995年由Sampath等[1]提出的通过构造诊断器的故障诊断方法是最早提出的解决离散事件系统故障诊断问题的算法。近年来还有其他故障诊断方法，Chen Z和Lin F[2]提出的离散事件系统框架下的主动诊断方法，也探讨了其在电池系统中的实际应用。Reshmila S和Devanathan R[3]提出了一种新的基于观测器的离散事件系统框架，并将其应用到电力系统。在文献[4]中，笔者所在课题组提出了一种基于模糊离散事件系统的安全诊断算法，可以用于医疗诊断系统。

随着对故障诊断研究的不断深入，思考如何在故障未发生前对其进行提前预测，已成为离散事件系统研究中的另一个热点方向——故障预测。Cao X R[5]首次在离散事件系统框架下提出了可预测性的概念，并且给出了离散事件系统基于语言上可预测的充分条件。You D和Wang S[6]使用带标记的Petri网的方式验证系统的可预测性。Chase C[7]分析了一维离散事件系统的状态依赖关系，提出了一种有监督的一维系统的可预测性方法。Buss S R[8]在耦合自动机的预测问题上提出了一种二分法。Genc S[9]解决了基于语言的部分观测离散事件系统中的重要事件的预测问题。

然而，现实社会中随着互联网的发展，互联网上的信息量的越来越大，用户对于系统的需求及应用系统的功能越来越多，因此数据库的规模和应用系统的规模也变得越来越庞大，集中型的诊断预测方法将直接导致组合搜索的空间爆炸，使得其复杂度随着系统规模的扩大而升高，所以，近年来分布式系统的诊断和预测算法得到广泛重视。Qiu W[10]针对分布式离散事件系统提出了一种分布式状态估计协议，分布式观察者通过有界延迟信道共享状态估计信息，进一步降低了时间和空间复杂度；Pencolé Y[11]研究了基于分布式离散事件系统的诊断问题。Yin X[12]提出了两种分布式协议来研究分布式离散事件系统的预测问题。最近，笔者所在课题组在文献[13]中提出了一种基于分布式离散事件系统的离线故障预测算法，并给出了分布式离散事件系统可预测性的充分必要条件，在文献[14]中本课题组又针对分布式离散事件系统的可靠性预测问题进行了研究。

可以看出，上述文献的离散事件系统都是针对单个故障事件进行诊断和预测，但在实际应用中，有些故障可能不是单个故障事件，而是由一系列重要事件组成的事件序列造成的故障。例如数据库系统中，数据库的读写操作都是正常的事件，若程序员操作不当，可能造成数据的“脏读”。对此，人们提出了模式故障诊断的概念。对于模式故障的诊断，Jéron T，Marchand H等[15]在2006年最先提出了一个监督模式故障模型，该模型被建模为一个自动机，并且它具有足够的通用性，能够捕捉系统过去发生的特定轨迹，许多文献中提出的多个故障、重复故障、重大事件的顺序、故障修复事件等都可以视为该模式故障的一种特殊情况。之后，Genc S[16]基于形式语言的上下文定义了两种不同类型的模式故障：S型模式故障和T型模式故障。基于离散事件系统的模式故障的诊断和预测问题越来越引人重视。在文献[17-18]中，笔者所在课题组对S型模式故障和T型模式故障分别研究了模糊离散事件系统的故障诊断问题和经典离散事件系统安全诊断问题。Dague[19]提出的一种基于分布式系统的模式故障诊断问题的通用性算法。Jéron T[20]提出了一种基于经典集中型离散事件系统的模式故障预测的方法。最近，Geng X N[21]研究了基于随机离散事件系统的模式故障诊断问题。

笔者注意到，关于分布式离散事件系统的模式故障预测问题的研究中依然未见报道，因此本文对分布式离散事件系统的模式故障预测开展研究，提出一个基于分布式离散事件系统的模式故障诊断预测方法。首先对分布式离散事件系统的模式故障可预测性进行形式化。通过构造一个模式故障识别器，从系统所有行为中识别出所发生的模式故障并标记。然后，在模式故障识别器的基础上构建了一个模式故障预测验证器，用于验证分布式系统的可预测性。之后，得出了一个判定分布式离散事件系统模式故障可预测性的充分必要条件，并提出了相应的模式故障预测算法，实现了对分布式离散事件系统的模式故障预测。最后，对模式故障预测验证器的构建和分布式离散事件系统的模式故障预测算法进行了复杂度分析，得到了该分布式模式故障预测算法的复杂度为多项式时间的结论。

本文接下来分成7节，第1节将介绍离散事件系统的一些基础知识，第2节将对分布式离散事件系统的模式故障预测进行形式化定义，第3节将构造一个用于模式故障预测的验证器，第4节将推导模式故障预测的充分必要条件，第5节将对模式故障预测算法的复杂性进行分析，第6节举例说明模式故障预测算法在三罐水位控制系统中的应用，第7节将总结本文所做的工作。

1 离散事件系统

图1 汽车中的模式故障示例Fig.1 Example of a pattern fault in an automobile

2 分布式离散事件系统可预测的形式化

图2 可预测性的直观图表示Fig.2 A direct visual representation of predictability

3 构造模式故障预测验证器

4 分布式离散事件系统的模式故障预测的充分必要条件

5 模式故障可预测算法的复杂性分析

6 实例分析

下面结合三罐水位控制系统(A Three-Tank Water Level Control System，TTW)来说明如何检测分布式系统的模式故障可预测性。

图3 三罐水位控制系统(TTW)Fig.3 The three tank water level control system

例2如图3所示，在三罐水位控制系统(TTW)中，有1个储水池、3个储水罐(T1，T2，T3)、1个抽水泵和7个阀门(V0，V1，V2，V3，V4，V5，V6)。故障模式，如图5所示，其中{A，B，C}表示模式故障的当前状态的标签，它们的含义是：A-表示正常状态；B-表示还未完全被模式故障诊断的中间状态；C-表示已经确定为模式故障的状态。后面在构建模式故障预测验证器的过程中，这些标签将会一直存在，以此来说明系统当前的状态。

图4 TTW的有限状态机Fig.4 The finite-state machine of TTW

图5 TTW的模式故障Fig.5 The patterns fault

其次，根据算法1可以构建出三罐水位控制系统的标记转移系统 Γ如图9所示。并将标记转移系统Γ中的{A，B，C}标签简化为{N，F}标签，得到TTW的模式故障预测验证器VG，如图10所示。

最后，根据图8可以看出模式故障预测验证器的前驱状态为 τ1=(1,N;1,N;1,N)，该前驱状态能被站点1和2同时诊断到模式故障。满足所有的前驱状态最终至少有一个站点可以预测到该模式故障，换句话说，所有通过前驱状态的路径最后都到达i−F状态环，根据定理1可以得到三罐水位控制系统是分布式模式故障可预测的系统。

然后，根据算法1可以构建出三罐水位控制系统的不可观测闭包U(GΩ)；在站点1(储水罐T1)不能观测到储水罐T3的阀门V3和V6，因此站点1的不可观测闭包为U1(GΩ)；在站点2(储水罐T3)不能观测到储水罐T1的阀门V1和V4，因此站点2的不可观测闭包为U2(GΩ)。分别如图6、图7、图8所示。

图6 TTW的不可观测闭包U(GΩ)Fig.6 The unobservable closure of TTW

图7 站点1的不可观测闭包U1(GΩ)Fig.7 The unobservable closure of site 1

图8 站点2的不可观测闭包U2(GΩ)Fig.8 The unobservable closure of site 2

图9 标记转移系统ΓFig.9 The part of the tag transfer system

图10 模式故障预测验证器VGFig.10 The patterns fault prediction verifier

7 结论

本文笔者对离散事件系统的模式故障预测进行了研究，将模式故障看作一个自动机，从而跟系统G组合成一个模式故障识别器。而且考虑到如果集中式的离散事件系统模型状态过多，其预测模型的验证器的状态空间将会很大的问题，为了降低集中式的模型的复杂性，笔者采用了分布式的模型分站点来进行模式故障预测，使得每个模块相对独立，进而使得各个站点只需要关注自己所观测到的事件，得到其自身的不可观测闭包。再由各个站点的不可观测闭包来联合构造出系统G的标记转移系统，最后根据该标记转移系统简化状态标签得到系统G的分布式模式故障预测验证器，解决了分布式系统中的模式故障预测问题。