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

针对离散事件系统的故障诊断研究，已经有大量的相关文献提出了各种诊断算法，其中在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 离散事件系统

离散事件系统通常被建模为确定型有限状态自动机 $G = (Q,\varSigma ,\delta ,{q_0})$ ，其中 $Q$ 为状态集， $\varSigma $ 为事件集，事件集 $\varSigma $ 可划分为可观事件集 ${\varSigma _{\rm{o}}}$ 和不可观事件集 ${\varSigma _{{\rm{uo}}}}$ ，它们满足 $\varSigma = {\varSigma _{\rm{o}}}\cup{\varSigma _{{\rm{uo}}}}$ 。 $\delta :Q \times \varSigma \to Q$ 为状态转移函数， ${q_0} \in Q$ 为系统的初始状态。 $\varSigma^*$ 的子集被称作系统 $G$ 的语言，用 $L(G)$ 或 $L$ 表示， ${L_{\sim f}}$ 表示未发生故障事件的语言， ${L_F}(G)$ 表示最终到达标记状态的语言。

离散事件系统中的连接运算：

设任意2个事件串 ${L_a},{L_b} \subseteq {\varSigma ^*}$ ，则它们的连接运算为 ${L_a}.{L_b} = \{ s \in {\varSigma ^*}:(s = {s_a}{s_b})({s_a} \in {L_a})({s_b} \in {L_b})\} $ 。

$\overline L $ 为 $G$ 的前缀闭包语言，满足 $\overline L \subseteq {\varSigma ^*}$ ，设 $s$ 为离散事件系统中的事件集元素按照某种顺序组成的事件串，也可称作为路径。当存在一个事件串 $t$ ，满足 $s.t \in L(G)$ ，则这些满足条件的事件串 $s$ 组成系统 $G$ 的前缀闭包语言，即 $\overline L = \{ s \in {\varSigma ^*}:(\exists t \in {\varSigma ^*})[s.t \in L]\} $ 。它表示 $\overline L $ 包含语言 $L$ 中所有事件串的前缀，即 $L \subseteq \overline L $ 。

给定一个事件串 $s \in L$ ，那么 $s$ 的后缀语言为 $L/s = \{ t \in \varSigma^*:s.t \in L\} $ 。

系统 $G$ 的路径可观映射函数为 $P:{\varSigma ^*} \to \varSigma _{\rm{o}}^*$ ，它表示将路径 $s$ 中的不可观的事件移除， $\varepsilon $ 表示一个空串，满足 $P(\varepsilon ) = \varepsilon $ 。对于任意路径 $s \in \varSigma^*$ 和可观事件 $\sigma \in {\varSigma _{{\rm{uo}}}}$ 有

$ P(s\sigma )=\left\{\begin{aligned} & P(s)\sigma ,\;\;{\text{如果}}\sigma \in {\varSigma }_{\rm{o}}\\& P(s),\;\;{\text{其他}} \end{aligned} \right.$

对于路径 ${s_{\rm{o}}} \in \varSigma _{\rm{o}}^*$ ，路径 ${s_{\rm{o}}}$ 的逆投影为 ${P^{ - 1}}({s_{\rm{o}}}) = \{ s' \in {\varSigma ^*}:P(s') = {s_{\rm{o}}}\} $ 。

给定一个系统 $G$ 上的路径 $\mu $ ，定义它的相容路径为 $\left[\kern-0.15em\left[ \mu \right]\kern-0.15em\right]$ ：

$\left[\kern-0.15em\left[ \mu \right]\kern-0.15em\right]\triangleq \left\{\begin{aligned} & {P}^{-1}(\mu )\cap L(G)\cap {\varSigma }^{*}.{\varSigma }_{\rm{o}}\;\;,{\text{如果}}\mu \ne \varepsilon \\& \varepsilon, \qquad\qquad\qquad\quad\;\;\;\;\;\;\;\;\;{\text{其他}} \end{aligned} \right.$

它表示所有与路径 $\mu $ 映射相同的并以可观事件结尾的路径集。

定义1(模式故障)　一个系统的模式故障可以定义为自动机

$\varOmega = ({Q_\varOmega },{\varSigma _\varOmega },{\delta _\varOmega },q_\varOmega ^0,{F_\varOmega }),$

其中 ${Q_\varOmega }$ 为模式故障状态集， ${\varSigma _\varOmega }$ 为模式故障事件集， ${\delta _\varOmega }:{Q_\varOmega } \times {\varSigma _\varOmega } \to {Q_\varOmega }$ 为模式故障的状态转移函数， $q_\varOmega ^0 \in {Q_\varOmega }$ 为该模式故障的初始状态， ${F_\varOmega }$ 为终止状态集，也叫标记状态集， ${L_m}(\varOmega )$ 为模式故障自动机产生的到达标记状态的语言。

例1 　在小汽车没有制动时，拉上手刹或打开车门都是属于正常事件，但在汽车正常行驶的过程中，再拉上手刹或打开车门都是被禁止的操作，这种由一系列正常事件按某种顺序发生的事件串，可以看作模式故障，这类故障建模为自动机，如图1所示。

设系统中 ${f_1}$ 表示汽车正常行驶， ${f_2}$ 表示打开车门， ${f_3}$ 表示拉上手刹。可以看出，在该自动机中， ${Q_\varOmega } = \{ 1,2,3,4\}$ ， ${\varSigma _\varOmega } = \{ {f_1},{f_2},{f_3}\} $ ，初始状态为0，终止状态为4，模式故障为 $\left\{ {\left\{ {{f_1},{f_2}} \right\}} \right.$ , $\left\{ {{f_1},{f_3}} \right\}$ , $\left\{ {{f_2},{f_1}} \right\}$ , $\left. {\left\{ {{f_3},{f_1}} \right\}} \right\}$ 。可以看到在发生模式故障后，将会到达终止状态且不会改变，这涉及到终止状态的稳定性。

终止状态集 ${F_\varOmega }$ 具有稳定性，稳定性的意思为一旦自动机 $\varOmega $ 到达终止状态时，它将永远保持在终止状态不会改变。 ${L_m}(\varOmega )$ 表示由模式故障自动机产生的，从初始状态出发到达标记状态的语言。稳定性可以描述为 $\forall s \in {L_m}(\varOmega ),\,\forall s' \in \varSigma _\varOmega ^*,\,\;ss' \in {L_m}(\varOmega )$ 。

设分布式离散事件系统 $G$ 有 $m$ 个观测站点， ${I_M}$ 表示站点的集合 $\{ 1,2, \cdots ,m\} $ ，在站点 $i$ 上的观测映射函数为 ${P_i}:{\varSigma ^*} \to \varSigma _{{\rm{o}},i}^*$ $(i \in {I_M} = \{ 1,2, \cdots ,m\} )$ ，在站点 $i$ 上观测到的系统 $G$ 可表示为 ${G_i} = (Q,{\varSigma _{{\rm{o}},i}},\delta ,q_i^0)$ 。为简单起见，下面仅考虑两个站点的分布式系统模型，即站点个数 $m = 2$ 。

定义2(同步)　设分布式系统中的2个自动机分别为 ${G_1} = ({Q_1},{\varSigma _1},{\delta _1},q_1^0)$ 和 ${G_2} = ({Q_2},{\varSigma _2},{\delta _2},q_2^0)$ ，则它们的分布式同步模型为

${G_1}|{|_{{\varSigma _s}}}{G_2} = ({Q_1} \times {Q_2},{\varSigma _1} \cup {\varSigma _2},{\delta _{1||2}},(q_1^0,q_2^0)),$

其中 ${Q_1}$ 和 ${Q_2}$ 分别为2个子系统的有限状态空间， ${Q_1} \times {Q_2}$ 为分布式系统的状态空间， ${\sum\nolimits_i} = {\varSigma _{{\rm{uo}}}} \cup {\varSigma _{\rm{o}}}(i = 1,2)$ 为有限事件集合， ${\varSigma _S} = {\varSigma _1} \cap {\varSigma _2}$ 表示子系统1和2的共享事件集， $(q_1^0,q_2^0)$ 为整个分布式系统的初始状态，转移函数 ${\delta _{1||2}}$ 被定义为：

${\delta _{1||2}}(({q_1},{q_2}),\sigma ) = \left\{ \begin{array}{l} ({q_1}',{q_2}')\;,\;\;\;\;\;\;{\text{当}}\sigma \in {\varSigma _S}{\text{时}}\\ ({q_1}',{q_2})\;,\;\;\;\;\;\;\;{\text{当}}\sigma \in {\varSigma _1}\backslash {\varSigma _S}{\text{时}}\\ ({q_1},{q_2}')\;,\;\;\;\;\;\;\;{\text{当}}\sigma \in {\varSigma _2}\backslash {\varSigma _S}{\text{时}} \end{array} \right.$

其中 ${q_1},{q_2}$ 满足 $ {\delta }_{1}({q}_{1},\sigma )={q}_{1}',\;{\delta }_{2}({q}_{2},\sigma )={q}_{2}'$ 。

定义3 　设分布式系统中的2个子系统为 ${G_i} = ({Q_i},{\varSigma _i},{\delta _i},q_i^0)\;,\;i = 1,2$ ，它们的同步积定义为

${G_1} \times {G_2} \triangleq ({Q_1} \times {Q_2},\varSigma ,{\delta _{1 \times 2}},(q_{{G_1}}^0,q_{G_2}^0)),$

其中 ${\delta _{1 \times 2}}$ 表示2个子系统的同步转移函数为 ${\delta _{1 \times 2}}: ({Q_1} \times {Q_2}) \times \varSigma \to ({Q_1} \times {Q_2})$ ，对于任意事件 $\sigma $ 有 ${\delta _{1 \times 2}}(({q_1},{q_2}), \sigma ) = ({q_1}',{q_2}')$ ，其在相应的子系统中都有转移 ${\delta }_{1}({q}_{1},\sigma )= {q}_{1}',\;{\delta }_{2}({q}_{2},\sigma )={q}_{2}'$ 。

很明显地可以得到同步系统产生的语言为 $L({G_1} \times {G_2}) = L({G_1}) \cap L({G_2})$ ，对于终止状态 ${F_i} \subseteq {Q_i}\;, \;i = 1,2$ ，它们满足以下关系 ${L_{{F_1} \times {F_2}}}({G_1} \times {G_2}) = {L_{{F_1}}}({G_1}) \cap {L_{{F_2}}}({G_2})$ 。同样地，如果子系统标记状态集 ${F_i}$ 在 ${G_i}$ 是稳定的，同步后的状态集 ${F_1} \times {F_2}$ 在 ${G_1} \times {G_2}$ 上也是稳定的。

定义4(延迟闭包)　给定一个自动机 $G = (Q,\varSigma , \delta ,{q^0})$ ，它相对于可观事件集 ${\varSigma _{\rm{o}}} \subseteq \varSigma $ 的延迟闭包定义为 $U(G) = (Q,{\varSigma _{\rm{o}}},{\delta _U},{q^0})$ 。对于任意可观事件 $\sigma $ 都有 ${\delta _U}(q,\sigma ) = q'$ ，且都满足 $\exists s \in (\varSigma \backslash {\varSigma _{\rm{o}}})*$ ， ${\delta _U}(q,s\sigma ) = q'$ 。

由文献[22]可以得到延迟闭包所产生的语言与系统 $G$ 的语言经过可观映射后相等，即 $L(U(G)) = P(L(G))$ 和 ${L_F}(U(G)) = P({L_F}(G))$ 。

定义5(模式故障可诊断性)　系统 $G$ 称为关于模式故障 $\varOmega $ 是可诊断的当且仅当 $\exists n \in N$ ， $\forall s \in L(G) \cap {L_F}(\varOmega )$ ， $\forall t \in L(G)/s$ ，如果 $|t| \geqslant n$ ，则对 $\forall p \in L(G)$ ，有 $P(p) = P(s.t) \Rightarrow p \in {L_F}(\varOmega )$ 成立，其中 ${L_F}(\varOmega )$ 表示系统 $G$ 中可被模式故障诊断的语言。

直观上，如果系统 $G$ 关于模式故障 $\varOmega $ 是可诊断的，那么系统 $G$ 中的任意一条含有模式故障的路径 $s$ 都可被诊断，若路径 $s$ 存在足够长的扩展路径 $t$ ，任何与路径 $s.t$ 映射相同的路径也能被模式故障 $\varOmega $ 诊断。

定义6^[23](模式故障 $\varOmega $ -可预测)　设系统 $G$ 为离散事件系统， $L$ 表示系统 $G$ 生成的语言， ${L_{{F_\varOmega }}}$ 表示可以被模式故障所诊断的语言。如果满足以下条件，则称 $G$ 为模式故障 $\varOmega $ -可预测的：

$ \begin{array}{l}\exists n\in {\rm{N}}^{\rm{+}},\;\forall s\in {L}_{{F}_{\varOmega }}\cap L\cap {\varSigma }^{*}.{\varSigma }_{\rm{o}},\\ \exists t\in (L\cap {\varSigma }^{*}.{\varSigma }_{\rm{o}})\cup \left\{\varepsilon \right\},\;t<s\;\wedge \;t\notin {L}_{{F}_{\varOmega }}\\ {\text{当且仅当}}\\ \forall u\in \left[\kern-0.15em\left[P(t)\right]\kern-0.15em\right],\;\forall v\in L/u,\;\left|\right|P(v)\left|\right|\;\geqslant \;n\;\Rightarrow \;u.v\in {L}_{{F}_{\varOmega }}\end{array}$

直观上，上面定义表示对于任何能被模式故障诊断的路径 $s$ ，存在未被模式故障诊断的前缀 $t$ ，任何与观测路径 $P(t)$ 映射相同的相容路径 $u$ ，可扩展为路径 $u.v$ 且路径 $u.v$ 可以被模式故障 $\varOmega $ 诊断出来。也就是说，如果模式故障 $\varOmega $ 是可预测的，那么在这个模式故障 $\varOmega $ 发生之前，总能通过可观测的路径来预测模式故障 $\varOmega $ 的发生。

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

上一节考虑的是集中型的模式故障预测，下面将给出分布式离散事件系统的模式故障可预测性形式化定义。

定义7(分布式模式故障 $\varOmega $ 可预测性定义)　设在一个有m个站点的分布式系统 $G$ 中， $i \in {I_M} = \{ 1,2, \cdots ,m\} $ 表示任意站点， $L$ 表示系统 $G$ 生成的语言， ${L_{{F_\varOmega }}}$ 表示可以被模式故障所诊断的语言。如果满足以下条件，则称 $G$ 为分布式模式故障 $\varOmega $ -可预测的：

$ \begin{array}{l}\exists n\in {\rm{N}}^{\rm{+}},\;\forall s\in {L}_{{F}_{\varOmega }}\cap L\cap {\varSigma }^{*}.{\varSigma }_{\rm{o}},\\ \exists t\in (L\cap {\varSigma }^{*}.{\varSigma }_{\rm{o}})\cup \left\{\varepsilon \right\},\;t<s\;\wedge \;t\notin {L}_{{F}_{\varOmega }}\\ {\text{当且仅当}}\\ \exists i\in {I}_{\rm{M}},\forall u\in \left[\kern-0.15em\left[{P}_{i}(t)\right]\kern-0.15em\right],\;\forall v\in L/u,\;\left|\right|{P}_{i}(v)\left|\right|\geqslant n\Rightarrow u.v\in {L}_{{F}_{\varOmega }}\end{array}$

直观上，该定义表示对于任何能被模式故障所诊断的，并以可观事件结尾的路径 $s$ ，如果它都存在一个不被模式故障诊断的并以可观事件结尾的前缀 $t$ ，至少存在一个站点 $i$ ，可以观测到所有与路径 $t$ 映射相同的路径，且在 $n$ 步后都一定会被模式故障 $\varOmega $ 诊断出来。

图2为可预测性在语言层面的解释，对于任何可被模式故障诊断的轨迹 $s$ ，都存在一个严格的还未被模式故障诊断的前缀 $t$ ，使得任何与映射 $P(t)$ 相容的轨迹 $u$ ，其扩展轨迹 $u.v$ 都可以被模式故障诊断出来。也就是说，通过对 $P(t)$ 的观测，这个模式故障虽然尚未被识别，但是已经可以预测到该模式故障是否将会发生。

现在笔者将讨论模式故障 $\varOmega $ 可预测和模式故障 $\varOmega $ 可诊断的概念之间的关系。通过文献[21]及模式故障 $\varOmega $ 可预测和模式故障 $\varOmega $ 可诊断的定义可知，系统 $G$ 是模式故障 $\varOmega $ 可预测的，那么它一定也是模式故障 $\varOmega $ 可诊断的，反之则不成立。

定义8(先导状态)　在 ${G_\varOmega }$ 的不可观闭包 $U({G_\varOmega }) = ({Q_{{G_\varOmega }}},{\varSigma _o}, \to 'U,q_{{G_\varOmega }}^0)$ 中，如果满足 $\forall q \in {Q_{{G_\varOmega }}}$ ，有 $(q,l){\xrightarrow{\sigma }} U (q',{F_\varOmega })$ ，其中 $\sigma \in {\varSigma _{\rm{o}}}$ ，那么定义 $q$ 为先导状态，记为 $q \in Q_U^{{\rm{Pr}}}$ 。

它的含义是：如果存在一个状态 $q$ ，经过一个可观事件 $\sigma $ ，可以到达能被模式故障诊断的终止状态，则这样的状态 $q$ 称为先导状态。

定义9(前驱状态集) 　设在模式故障预测验证器 ${V_G} = ({Q_G},{\varSigma _{\rm{o}}},{ \to _G},q_G^0)$ 中如果存在一个状态为 $\tau \in (q, {\rm{N}};{q_1},{\rm{N}}; \cdots ;{q_m},{\rm{N}})$ ，其中 $m$ 为站点个数，如果它经过一个事件 $\sigma \in {\varSigma _{\rm{o}}}$ 且满足 $(q,{\rm{N}} ;{q_1},{\rm{N}} ; \cdots ;{q_m},{\rm{N}} ){\xrightarrow{\sigma }_\varGamma }(q,{\rm{F}} ;{q_1}, {\rm{N}} ; \cdots ; {q_i},{\rm{F}} ; \cdots ;{q_m},{\rm{N}} )$ ，其中 $i \in \{ 1, \cdots ,m\} $ ，那么它被称为前驱状态，在模式故障预测验证器 ${V_G}$ 中这样的前驱状态集合被称为前驱状态集 $Q_\varGamma ^{\Pr }$ 。

定义10(可达部分)　设在模式故障预测验证器 ${V_G} = ({Q_G},{\varSigma _{\rm{o}}},{ \to _G},q_G^0)$ 中的任意一个状态 $\tau $ ，如果 ${Q_\varGamma }$ 满足 ${Q_\varGamma }' = \{ \tau ' \in {Q_\varGamma }|\exists s \in \varSigma _{\rm{o}}^*,\;\;\tau {\xrightarrow{s}_\varGamma }\tau '\} $ ，那么该状态 $\tau $ 的可达部分可表示为 $A({V_G},\tau )$ ，它被定义为一个自动机：

$A({V_G},\tau ) = ({Q_G}',{\varSigma _{\rm{o}}},{ \to _G},\tau )$

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

在本节笔者将说明如何构造模式故障预测验证器来验证分布式系统的模式故障可预测性，首先需要构造一个模式故障预测验证器，再进行判断，下面给出构造模式故障预测验证器的方法。

步骤1 　构造模式故障识别器，即同步积为 ${G_\varOmega } = G \times \varOmega = ({Q_{{G_\varOmega }}},\varSigma ,{\delta _{{G_\varOmega }}},q_{{G_\varOmega }}^0)$ ，模式故障识别器终止状态集 $F = {Q_G} \times {F_\varOmega }$ ，利用同步积的性质，由于 $\varOmega $ 是完备的，可以得到 $L({G_\varOmega }) = L(G) \cap L(\varOmega ) = L(G)$ 和 ${L_F}({G_\varOmega }) = L(G) \cap {L_{{F_\varOmega }}}(\varOmega )$ ，因此在终止状态集 ${F_\varOmega }$ 中，模式故障识别器 ${G_\varOmega }$ 可诊断的路径恰好是在 ${F_\varOmega }$ 中可被模式故障 $\varOmega $ 诊断的路径。

步骤2 　构造模式故障识别器 ${G_\varOmega }$ 的不可观闭包 $U({G_\varOmega }) = ({Q_{{G_\varOmega }}},{\varSigma _{\rm{o}}}, \to _U',q_{{G_\varOmega }}^0)$ ，及各个站点的不可观测闭包 ${U_1}({G_\varOmega })$ ， ${U_2}({G_\varOmega })$ 。

步骤3 　根据定义3构造标记转移系统(Label Transfer System，简称LTS) $\varGamma $ 。

$ \begin{array}{l} \varGamma = ({Q_\varGamma },{\varSigma _{\rm{o}}},{ \to _\varGamma },{\tau ^0})=U({G_\varOmega }) \times {U_1}({G_\varOmega }) \times {U_2}({G_\varOmega })=\\ ({Q_{{G_\varOmega }}} \times {Q_{{G_\varOmega }1}} \times {Q_{{G_\varOmega }2}},{\varSigma _{\rm{o}}},{ \to _\varGamma },(q_{{G_\varOmega }}^0,q_{{G_\varOmega }1}^0,q_{{G_\varOmega }2}^0)) \end{array} $

其中标记转移系统的初始状态为 ${\tau ^0} = ({q^0},{\rm{N}} ;q_1^0,{\rm{N}} ; q_2^0,{\rm{N}} )$ ，转移函数定义为

$ \begin{split} & (q,l;{q}_{1},{l}_{1};{q}_{2},{l}_{2}){\stackrel{\sigma }{\to }}\\&{\varGamma }\left\{\begin{array}{l}(q',l';{q}_{1},{l}_{1};{q}_{2}',{l}_{2}');\\ (q',l';{q}_{1},{l}_{1};{q}_{2}',{l}_{2}');\\ (q',l';{q}_{1}',{l}_{1}';{q}_{2}',{l}_{2}');\end{array}\begin{array}{c}{\text{当}}\sigma \in {\varSigma }_{\rm{o}}-{\varSigma }_{\rm{o,1}}{\text{时}}\;\\ {\text{当}}\sigma \in {\varSigma }_{\rm{o}}-{\varSigma }_{\rm{o,2}}{\text{时}}\;\\ {\text{当}}\sigma \in {\varSigma }_{\rm{o,1}}\cap {\varSigma }_{\rm{o,2}}{\text{时}}\end{array}\right. \end{split}$

步骤4 　根据定义9计算并标记出先驱状态 $\tau \in Q_\varGamma ^{\Pr }$ ，且算出其可达部分 $A(\varGamma ,\tau )$ 。

步骤5 　将以上步骤生成的标记转移系统 $\varGamma $ 进一步简化处理得到模式故障预测的验证器 ${V_G}$ ，对于其中任意状态 $\tau \in (q,{\rm{N}} ;{q_1},{\rm{N}} ; \cdots ;{q_m},{\rm{N}} )$ 有转换 $(q,l;{q_1}, {l_1};{q_2},{l_2}) \to (q,l';{q_1},{l_1}';{q_2},{l_2}')$ ，转换规则为

$ {l}_{i}'=\left\{\begin{array}{ll} {\rm{F}},& {\text{如果}}{l}_{i}={F}_{\varOmega }\\ {\rm{N}},& {\text{其他}}\end{array}\right.$

其中{N，F}标签的含义是N-正常状态；F-已被模式故障诊断的状态。

经过以上5个步骤，可以构造出一个精简的模式故障预测的验证器 ${V_G}$ ，它的先驱状态仍为 $\tau \in Q_\varGamma ^{\Pr }$ ，并且根据定义10算出其可达部分为 $A({V_G},\tau )$ 。下一节将会给出分布式离散事件系统的模式故障预测的充分必要条件，根据验证器 ${V_G}$ 来判断分布式离散事件系统 $G$ 是否为模式故障可预测的。

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

定义11( $i - {\rm{F}} $ 状态环)　设模式故障预测验证器 ${V_G}$ 中任意状态为 $\tau = (q,l;{q_1},{l_1}; \cdots ;{q_m},{l_m}) \in {Q_\tau }$ ，如果满足 $l = {\rm{F}} \wedge {l_i} = {\rm{F}} ,i \in {I_M} = \{ 1, \cdots ,m\} $ 则它被称为 $i - {\rm{F}} $ 状态。由 $\tau $ 组成的自循环被称作 $i - {\rm{F}} $ 状态环。

定理1(模式故障可预测的充分必要条件)　若系统 $G$ 是一个分布式模式故障可预测的系统，当且仅当验证器 ${V_G}$ 的前驱状态集 $Q_\varGamma ^{\Pr }$ 的可达部分 $A({V_G},\tau )$ 的环都是 $i - {\rm{F}} $ 状态环。

证明 　下面先用反证法证明必要性。设 $G$ 是一个分布式模式故障可预测的系统。

对于任意模式故障，总有某个站点 $i$ 可以预测到该故障，其中 $i \in I = \{ 1, \cdots ,m\} $ 。已知模式故障预测验证器的初始状态为 ${\tau ^0} = ({q^0},{\rm{N}} ;q_1^0,{\rm{N}} ;q_2^0,{\rm{N}} )$ ，如果模式故障预测验证器 ${V_G}$ 的可达模式故障的前驱状态集 $Q_\varGamma ^{\Pr }$ 的可达部分中至少存在一个环不是 $i - {\rm{F}} $ 状态环，即验证器的标记状态至少存在一个不能被任何站点识别的状态 $\tau ' = (q,{\rm{F}} ;{q_1},{\rm{N}} ; \cdots ;{q_i},{\rm{N}} ; \cdots {q_m},{\rm{N}} )$ 。

设验证器 ${V_G}$ 存在一个可被模式故障诊断的标记状态为 ${\tau _2} = (q,{\rm{F}} ;{q_1},{\rm{N}} ; \cdots ;{q_i},{\rm{F}} ; \cdots ;{q_m},{\rm{N}} ) \in Q_\varGamma ^F$ ，存在一条可被模式故障诊断的路径 $s$ ( $s \in {L_m}(\varOmega )$ )，满足 ${\tau ^0}\xrightarrow{s}{\tau _2}$ 。设存在一个先驱状态为 ${\tau _1} = (q,{\rm{N}} ;{q_1},{\rm{N}} ; \cdots ; {q_m},{\rm{N}} ) \in Q_\varGamma ^{\Pr }$ ，存在一条属于路径 $s$ 的前缀闭包并且未发生模式故障的路径 $t \in \overline s \cap {L_{\sim f}}(\varOmega )$ ，满足 ${\tau ^0}\xrightarrow{t}{\tau _1}$ ，其中 ${L_{\sim f}}(\varOmega )$ 表示不能被故障模式 $\varOmega $ 诊断的语言。根据模式故障预测验证器的构造过程可知，存在一条与 $t$ 投影相同的路径 $u$ ，对于 $i$ 站点满足 ${P_i}(t) = {P_i}(u)$ ，则 ${\tau ^0}\xrightarrow{u}{\tau _1}$ 。存在 $v \in L(G)/u \cap {L_{\sim f}}(\varOmega )$ ，满足 $||v|| \geqslant n$ 且 $u.v \notin {L_F}(\varOmega )$ ，其中 $n$ 为任意自然数。根据定义7 (分布式模式故障可预测性定义)，可以得到 $G$ 不是分布式模式故障可预测的系统，这与上面的假设相矛盾。

下面再用反证法证明充分性。设模式故障预测验证器的前驱状态集 $Q_\varGamma ^{\Pr }$ 的可达部分的环都是 $i - {\rm{F}} $ 状态环。假设 $G$ 不是一个分布式模式故障可预测的系统，根据定义6，设存在一条可被模式故障诊断的路径 $s \in {L_F}(\varOmega )$ ，对任意路径 $t \in \overline s \cap {L_{\sim F}}(\varOmega )$ ，存在一条与 $t$ 投影相同的路径 $u$ ，存在一个 $i$ 站点满足 ${P_i}(t) = {P_i}(u)$ ，有 $v \in (L(G)/u) \cap {L_{\sim F}}(\varOmega )$ ，满足 $||v|| \geqslant n$ 且 $u.v \notin {L_F}(\varOmega )$ ，其中 $n$ 为任意自然数。

设模式故障预测验证器存在一个先驱状态为 ${\tau _1} = (q,{\rm{N}} ;{q_1},{\rm{N}} ; \cdots ;{q_m},{\rm{N}} ) \in Q_\varGamma ^{\Pr }$ ，已知该模式故障预测验证器的初始状态为 ${\tau ^0} = ({q^0},{\rm{N}} ;q_1^0,{\rm{N}} ;q_2^0,{\rm{N}} )$ ，设 ${\tau _1}$ 满足 ${\tau ^0}\xrightarrow{t}{\tau _1}$ ，则 ${\tau ^0}\xrightarrow{u}{\tau _1}$ ，又因为 $v \in L(G)/u \cap {L_{\sim f}}(\varOmega )$ ，满足 $||v|| \geqslant n$ ， $n$ 足够大则该路径一定形成环，即先驱状态 ${\tau _1}$ 的可达部分 $A({V_G},{\tau _1})$ 一定能形成环。又因为 $u.v \notin {L_F}(\varOmega )$ ，则在可达部分 $A({V_G},{\tau _1})$ 中至少存在一个环不是 $i - {\rm{F}} $ 状态环。这与上面的假设相矛盾。

根据定理1，可以通过检验定理1中的条件是否满足来验证 $G$ 是否为分布式模式故障可预测的系统，下面给出检验分布式离散事件系统的模式故障可预测性的算法。

算法1 (检验分布式离散事件系统的模式故障可预测算法)

步骤1 　对于给定的系统 $G$ 和模式故障 $\varOmega $ ，构造模式故障识别器 ${G_\varOmega } = G \times \varOmega = ({Q_{{G_\varOmega }}},\varSigma ,{\delta _{{G_\varOmega }}},q_{{G_\varOmega }}^0)$ 。

步骤2 　构造模式故障识别器 ${G_\varOmega }$ 的不可观闭包 $U({G_\varOmega }) = ({Q_{{G_\varOmega }}},{\varSigma _{\rm{o}}}, \to _U',q_{{G_\varOmega }}^0)$ ，及各个站点的不可观测闭包 ${U_i}({G_\varOmega })$ ，其中 $i \in I = \{ 1, \cdots ,m\} $ 。

步骤3 　构造标记转移系统(LTS)

$ \varGamma = ({Q_\varGamma },{\varSigma _{\rm{o}}},{ \to _\varGamma },{\tau ^0})=U({G_\varOmega }) \times {U_1}({G_\varOmega }) \times {U_2}({G_\varOmega }) $

步骤4 　计算并标记出先驱状态 $\tau \in Q_\varGamma ^{\Pr }$ ，且算出其可达部分 $A(\varGamma ,\tau )$ 。

步骤5 　将生成的标记转移系统 $\varGamma $ 进一步简化处理得到模式故障预测验证器 ${V_G}$ 。

步骤6 　检查模式故障预测验证器的前驱状态集 $\tau \in Q_\varGamma ^{\Pr }$ 的可达部分 $A({V_G},\tau )$ 的环是否都为 $i - {\rm{F}} $ 状态环，如果是则系统 $G$ 是模式故障可预测的，否则 $G$ 为模式故障不可预测的系统。

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

设 $G = (Q,\;\varSigma ,\;\delta ,\;{q_0})$ 是一个离散事件系统，模式故障 $\varOmega = ({Q_\varOmega },\;{\varSigma _\varOmega },\;{\delta _\varOmega },\;q_\varOmega ^0,\;{F_\varOmega })$ 是一个自动机， ${V_G} = ({Q_G}, {\varSigma _{\rm{o}}}, \to G,q_G^0)$ 是系统 $G$ 的模式故障预测的验证器。 ${G_i} = (Q,{\varSigma _{{\rm{o}},i}},\delta ,q_i^0)$ 是在站点 $i \in I = \{ 1,2, \cdots ,m\} $ 上的观测子系统。根据定理1可知，为了分析分布式离散事件系统模式故障预测算法的复杂性，需要考虑两方面的复杂性：一是构造模式故障预测验证器 ${V_G}$ 的复杂性，二是根据验证器 ${V_G}$ 判断系统 $G$ 是否为模式故障可预测的复杂性。

定理2 　 $G = (Q,\varSigma ,\delta ,{q_0})$ 是一个分布式离散事件系统，记 $||Q|| = {n_1}$ ， $||\varSigma || = {n_2}$ ， $||I|| = m$ 。则对于模式 $\varOmega $ 构造出 $G$ 的验证器 ${V_G}$ 的复杂度为 $O(n_1^{m + 1}{n_2}m)$ 。

证明 　根据验证器的构造过程，构造模式识别器 ${G_\varOmega } = G \times \varOmega = ({Q_{{G_\varOmega }}},\varSigma ,{\delta _{{G_\varOmega }}},q_{{G_\varOmega }}^0)$ 的复杂度为 $O({n_{\rm{1}}}{n_2})$ ，构造 ${G_\varOmega }$ 的不可观闭包 $U({G_\varOmega }) = ({Q_{{G_\varOmega }}},{\varSigma _{\rm{o}}}, \to _U',q_{{G_\varOmega }}^0)$ 的复杂度为 $O({n_{\rm{1}}}{n_2})$ ，由于有 $m$ 个站点联合预测，验证器 $\varGamma = U({G_\varOmega }) \times {U_1}({G_\varOmega }) \times \cdots \times {U_m}({G_\varOmega })$ 的构造复杂度为 $O(n_1^{m + 1}{n_2}m)$ 。

接下来，根据验证器 ${V_G}$ 判断系统 $G$ 是否为模式故障可预测的，由算法1的第6步可以得出判断可预测性需要检查可达部分中的状态环是否都是 $i - {\rm{F}} $ 状态环，通过使用有向图来验证系统是否存在 $i - F$ 状态环。

定义12 　设 ${V_G} = ({Q_\varGamma },{\varSigma _{\rm{o}}},{ \to _\varGamma },q_\varGamma ^0)$ 是 $G$ 的模式故障预测的验证器，构造 $\varGamma $ 的定向图为 ${\rm{DG}}_{\varGamma} = ({V_\tau },{E_\tau })$ ，其中 ${\rm{DG}}_\varGamma$ 的顶点集 ${V_\tau }$ 和边集 ${E_\tau }$ 分别定义如下：

$ \begin{array}{l} {V_\tau } = \{ \tau = (q,l;{q_1},{l_1}; \cdots ;{q_m},{l_m}) \in {Q_\varGamma }| \\ ({l_i} = N) \wedge (\exists s \in \varSigma _{\rm{o}}^*) \wedge ({\tau ^0}{\xrightarrow{s}_\varGamma }\tau )\} \\ {E}_{\tau }=\{({\tau }_{i},{\tau }_{j})\in {V}_{\tau }^{2}|\\ {\tau }_{i},{\tau }_{j}\in {Q}_{\varGamma },\exists \sigma \in {\varSigma }_{\rm{o}},{\text{满足}}{\tau }_{i}{\stackrel{\sigma }{\to }}_{\varGamma }{\tau }_{j}\} \end{array} $

引理1^[12] 　设 ${\rm{DG}}_v = ({V_{{\rm{DG}}}},{E_{{\rm{DG}}}})$ . 是一个定向图，关于 ${\rm{DG}}_v$ 中是否存在环的判定复杂性为 $O(||{V_{{\rm{DG}}}}|| + ||{E_{{\rm{DG}}}}||)$ 。

定理3 　设 ${V_G} = ({Q_G},{\varSigma _{\rm{o}}},{ \to _G},q_G^0)$ 是 $G$ 的模式故障预测的验证器，判断验证器 ${V_G}$ 中前驱状态集的可达部分 $A({V_G},\tau )$ 中的状态环是否都是 $i - {\rm{F}} $ 状态环的复杂性为 $O(n_1^{m + 1}{n_2}m)$ 。

证明 　由定义12可得

$ \begin{array}{l} |{V_\tau }| \leqslant |Q| \times {(2|Q|)^m} = {n_1}{(2{n_1})^m}\\ |{E_\tau }| \leqslant |{V_\tau }| \times (m + 2)|{\varSigma _{\rm{o}}}| \leqslant {n_1}{(2{n_1})^m}(m + 2){n_2}。\end{array} $

由引理1可得判断定向图 $D{G_\varGamma }$ 是否存在 $i - F$ 状态环的复杂度为 $O(||{V_\tau }|| + ||{E_\tau }||) \leqslant $ $O({n_1}{(2{n_1})^m} + {n_1}{(2{n_1})^m}\cdot (m + 2){n_2}) = O(n_1^{m + 1}{n_2}m)$ 。

定理4 　设 $G = (X,\varSigma ,{\delta _G},{x_0})$ 是一个离散事件系统，其中 $||X|| = {n_1}$ ， $||\varSigma || = {n_2}$ 。判定 $G$ 是否为分布式模式故障可预测的复杂性为 $O(n_1^{m + 1}{n_2}m)$ 。

证明 　根据定理1可知，判定 $G$ 是否为模式故障可预测系统需要考虑两方面的复杂性：一是构造模式故障预测验证器 ${V_G}$ 的复杂性，二是根据验证器 ${V_G}$ 判断系统 $G$ 是否为模式故障可预测的复杂性。定理2已经证明了构造模式故障预测验证器 ${V_G}$ 的复杂度为 $O(n_1^{m + 1}{n_2}m)$ ，而定理3已经证明了使用模式故障预测验证器判断系统 $G$ 是否为分布式模式故障可预测系统的复杂度为 $O(n_1^{m + 1}{n_2}m)$ 。因此，判定系统 $G$ 是否为分布式模式故障可预测系统的复杂度为 $O(n_1^{m + 1}{n_2}m)+ O(n_1^{m + 1}{n_2}m)=O(n_1^{m + 1}{n_2}m)$ 。

由文献[20]可以得到集中式的离散事件系统模式故障可预测性的复杂度为 $O({n_1}^2{2^{{n_2}}})$ ，由定理4可知分布式的离散事件系统模式故障可预测性的复杂度为 $O(n_1^{m + 1}{n_2}m)$ 。当集中式的离散事件系统状态空间足够大时， ${n_1}$ 和 ${n_2}$ 将趋向于无穷大，又因为指数型函数的增长速度远大于多项式函数，集中式的离散事件系统模式故障可预测性的复杂度大于分布式的离散事件系统模式故障可预测性的复杂度，所以当系统的状态空间过大时，最好将复杂的系统分解为分布式系统来进行观测，将大大降低系统的模式故障预测的复杂性。

6 实例分析

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

例2 　如图3所示，在三罐水位控制系统(TTW)中，有1个储水池、3个储水罐(T₁，T₂，T₃)、1个抽水泵和7个阀门(V₀，V₁，V₂，V₃，V₄，V₅，V₆)。

首先，将储存池装满水，此时，打开抽水泵，记为P^ON，打开阀门V₀，记为 $V_0^{{\rm{ON}}}$ ，则水可以注入到储水罐T₁。当阀门V₁和V₂打开时，水可以依次注入到储水罐T₂和T₃。最终水可以通过阀门V₃、V₄、V₅和V₆回到存储池。假设储水罐T₁和T₃被储水罐T₂挡住，外部只能同时观测到储水罐T₁、T₂和其对应的阀门或者储水罐T₂、T₃和其对应的阀门。

首先，将该三罐水位控制系统建模成一个有限状态机，如图4所示。事件集为{Increase，Decrease，P^ON，P^OFF， $V_0^{{\rm{ON}}}$ ， $V_1^{{\rm{ON}}}$ ， $V_2^{{\rm{ON}}}$ ， $V_3^{{\rm{ON}}}$ ， $V_4^{{\rm{ON}}}$ ， $V_5^{{\rm{ON}}}$ ， $V_6^{{\rm{ON}}}$ ， $V_0^{{\rm{OFF}}}$ ， $V_1^{{\rm{OFF}}}$ ， $V_2^{{\rm{OFF}}}$ ， $V_3^{{\rm{OFF}}}$ ， $V_4^{{\rm{OFF}}}$ ， $V_5^{{\rm{OFF}}}$ ， $V_6^{{\rm{OFF}}}$ }，其中 $\{P^{{\rm{OFF}}}, V_0^{{\rm{OFF}}}$ ， $V_1^{{\rm{OFF}}}$ ， $V_2^{{\rm{OFF}}}$ ， $V_3^{{\rm{OFF}}}$ ， $V_4^{{\rm{OFF}}}$ ， $V_5^{{\rm{OFF}}}$ ， $V_6^{{\rm{OFF}}}$ }为不可观事件集，在站点1(储水罐T₁)可以观测到的事件集为{Increase，Decrease，P^ON， $V_0^{{\rm{ON}}}$ ， $V_1^{{\rm{ON}}}$ ， $V_2^{{\rm{ON}}}$ ， $V_4^{{\rm{ON}}}$ ， $V_5^{{\rm{ON}}}$ }；在站点2(储水罐T₃)可以观测到的事件集为{Increase，Decrease，P^ON， $V_0^{{\rm{ON}}}$ ， $V_2^{{\rm{ON}}}$ ， $V_3^{{\rm{ON}}}$ ， $V_5^{{\rm{ON}}}$ ， $V_6^{{\rm{ON}}}$ }。定义{P^OFF，Decrease}为故障模式，如图5所示，其中{A，B，C}表示模式故障的当前状态的标签，它们的含义是：A-表示正常状态；B-表示还未完全被模式故障诊断的中间状态；C-表示已经确定为模式故障的状态。后面在构建模式故障预测验证器的过程中，这些标签将会一直存在，以此来说明系统当前的状态。

然后，根据算法1可以构建出三罐水位控制系统的不可观测闭包 $U({G_\Omega })$ ；在站点1(储水罐T₁)不能观测到储水罐T₃的阀门V₃和V₆，因此站点1的不可观测闭包为 ${U_1}({G_\Omega })$ ；在站点2(储水罐T₃)不能观测到储水罐T₁的阀门V₁和V₄，因此站点2的不可观测闭包为 ${U_2}({G_\Omega })$ 。分别如图6、图7、图8所示。

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

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

7 结论

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