近年来，离散事件系统的故障检测研究引起了国内外许多学者的广泛关注. 尽管目前关于系统故障检测的方法有很多，包括基于数学模型的定量分析方法和专家系统等人工智能方法，但由Sampath等^[1]提出的基于诊断器方法是离散事件系统故障诊断研究中最被广泛使用的方法^[2]. Qiu和Kumar^[3]将这种基于诊断器方法由集中式系统推广至分布式系统，提出了一种分布式系统故障诊断方法. Chen和Lin^[4] 等将故障诊断与系统监控相结合，提出了一种活性诊断方法，并将其应用于电池能源系统的故障诊断. Kwong和Yonge-Mallo^[5]研究了一类不完备离散事件系统的故障诊断问题，提出了一种通过构造具有自我学习功能诊断器的故障诊断方法. 欧阳丹彤等^[6]也探讨了不完备模型下离散事件系统的故障诊断问题. 李志武等^[7]对分布式离散事件系统发生故障后的可重构性进行了深入研究，提出了一种通过设计虚拟协调器与子系统之间的通信协议实现最优协调控制的动态重构方法. 本文作者则对模糊离散事件系统提出了一种模糊故障诊断方法^[8].

上述故障诊断是一种“事后诊断”，即在故障已经发生的情况下，判断系统是否能够将该故障及时诊断出来. 显然，这种故障诊断对进一步采取相应的故障隔离或系统修复等补救措施具有重要作用. 但是，对于严重影响系统运行甚至导致系统不可逆转的故障，这种“事后诊断”存在很大的局限性，因为它无法提前阻止该故障的发生. 为此，故障预测方法就应运而生. 故障预测是在故障尚未发生的情况下，预测系统在未来是否会有故障发生. 显然，故障预测能对系统故障进行提前预报和事先维护，对增强系统稳定性、消除系统安全隐患极为重要^[9].

在离散事件系统的故障预测方面，Genc和Lafortune^[9]对基于正则语言模型的离散事件系统提出了一种故障预测方法. Takai和Kumar^[10]针对一类带有界时延通讯的离散事件系统，提出了一种基于推理的分布式故障预测方法. Khoumsi和Chakib^[11]运用局部预测信息融合技术提出了一种基于合取与析取逻辑模式的分散预测方法. Sanchez等^[12]探讨了一类在初始状态和初始输出信息均未知的情况下 Petri 网结构序列检测问题. 舒少龙等^[13]用状态估计方法分别对系统的不可分辨性、强可检测性、强周期可检测性进行了深入研究. 本文作者也对分布式离散事件系统提出了一种分散故障预测方法^[14]和一个相应的多项式时间算法^[15].

本文研究随机离散事件系统的故障预测问题. 虽然离散事件系统研究在过去数十年内取得了一大批研究成果，但大多数系统模型还是局限于以经典自动机为模型的逻辑离散事件系统^[16]. 随着计算机等相关领域的迅猛发展，数据的计算和处理能力越来越强大，对数据处理后得到的数据结果的精确度要求也越来越高. 仅仅使用逻辑离散事件系统来进行数据建模，已经很难满足相关要求. 为了能够更加精确地描述一个数据模型，人们开始引入了随机自动机的概念. 随机离散事件系统将逻辑离散事件系统和随机自动机进行有效结合，通过增加概率描述的方式，可以更加精确地描述一个事件系统. 针对随机离散事件系统，David Thorsley^[17]提出了一种基于随机自动机理论的随机离散事件系统的故障诊断方法，通过构造随机诊断器模型实现对故障事件的实时诊断. 笔者也对随机离散事件系统提出了一种分散故障诊断方法^[18]和一种安全诊断方法^[19].

本文继续笔者在文献[14-15, 18-19]的工作，研究基于随机自动机模型的随机离散事件系统的故障预测方法. 先对随机离散事件系统的故障可预测性进行形式化，要求具有可预测性的系统能确保对无法预测故障事件发生的概率充分小(即能够预测故障事件发生的概率足够大). 再通过引入概率转移矩阵，构建一个故障预测器自动机，得到关于随机离散事件系统的故障可预测性的充分必要条件. 因此，在所构建的故障预测器的基础上，通过计算其扩展马尔可夫矩阵，根据该充分必要条件，可判定随机离散事件系统是否具有故障可预测性，从而实现对故障事件在其发生之前的准确预测. 值得指出的是，本文与文献[20-21]有明显不同，主要在于文献[20]是一种基于状态估计的预测方法，文献[21]是一种带有固定转移步数的预测方法，而本文是一种基于事件的预测方法，提出的通过构建预测器自动机实现对故障事件的预测也是本文的创新之处.

1 随机离散事件系统

一个随机离散事件系统是指一个四元组有限状态自动机^[17-19]

$G = (\varSigma ,{ X},p,x{}_0),$

其中Σ是有限事件集，X是有限状态集， $p$ 是概率转移函数，对于 $x,{x'} \in {X},e \in \varSigma ,p({x'},e|x)$ 表示当事件 $e$ 发生时系统由当前状态 $x$ 转移到 ${x'}$ 的概率， ${x_0}$ 是初始状态.

一个由 $\varSigma $ 中各元素按照一定顺序组成的序列称为串，记为 $s$ ，并用 $\left\| s \right\|$ 表示串 $s$ 的长度. 由 $\varSigma $ 中所有串的集合记为 ${\varSigma ^*}$ ，也称为 $\varSigma $ 的克林闭包. ${\varSigma ^*}$ 中的任一子集称为一个语言；用 $L$ 表示 $G$ 的生成语言，并用 $\bar L$ 表示 $L$ 的前缀闭包. 对于串 $s \in L$ ，用 $L/s$ 表示 $s$ 在 $L$ 中的后接语言，即 $L/s = \{ t \in {\varSigma ^*}:st \in L\} $ ； $L\backslash \sigma $ 表示 $L$ 中不包含 $\sigma $ 的语言，即 $L\backslash \sigma = \{ l \in L:\sigma \notin l\} $ ； ${s_f}$ 表示串 $s$ 的最后一个事件，即

${s_f} = \{ {s_f} \in \varSigma ,s \in L,t \in s:s = t{s_f}\}; $

$\varPsi (\sigma ,L)$ 表示 $L$ 中所有以事件 $\sigma $ 为结尾的串的集合，形式化定义为

$\varPsi (\sigma ,L) = \{ s\sigma \in L:s \in {\varSigma ^*},\sigma \in \varSigma \} ;$

$L(G,x)$ 表示所有 $G$ 中以状态 $x$ 为起始状态的串的集合， ${L_{\rm{o}}}(G,x)$ 表示从状态 $x$ 开始以第一个可观事件结尾的串的集合，即

${L_{\rm{o}}}(G,x) = \{ s \in L(G,x):s = u\sigma ,u \in \varSigma _{{\rm{uo}}}^*,\sigma \in {\varSigma _{\rm{o}}}\}; $

${L_\sigma }(G,x)$ 表示在 ${L_{\rm{o}}}(G,x)$ 以特定可观事件 $\sigma $ 结尾的串的集合，即 ${L_\sigma }(G,x) = \{ s \in {L_{\rm{o}}}(G,x):{s_f} = \sigma \} $ .

在随机离散事件系统 $G$ 中，若状态 $x$ 经过事件 $e$ 触发后到达状态 ${x'}$ ，则定义

$\begin{array}{l}\delta :{X} \times \varSigma \to {X},\\\delta (x,e) = {x'} \Rightarrow p({x'},e|x) > 0.\end{array}$

其中， $\delta (x,e) = {x'}$ 表示 $G$ 的转移函数. 特别地，若触发事件为空，可表示为 $\delta (x,\varepsilon ) = x$ ；若触发事件为多个事件的事件串，则转移函数可进一步扩展为

$\delta (x,se) = \delta (\delta (x,s),e). $

为方便起见，类似文献[17-19]引入如下两个假设.

假设1　随机离散事件系统 $G$ 的生成语言 $L$ 是活性语言，即

$\mathop \varSigma \limits_{{x'} \in { X}} \mathop \varSigma \limits_{e \in \varSigma } p({x'},e|x) = 1.$

它表示 $G$ 的任一状态 $x$ 经过所有可能的事件到达下一个状态的概率之和为1.

假设2　随机离散事件系统 $G$ 中不存在不可观事件环，即

$\exists {n_0} \in {\rm N}$ ， $\forall ust \in L,s \in \varSigma _{{\rm{uo}}}^* \Rightarrow \left\| s \right\| \leqslant {n_0}$ ，其中N为正整数.

通常有限事件集 $\varSigma $ 由两部分组成， $\varSigma = {\varSigma _{\rm{o}}}\dot \cup {\varSigma _{{\rm{uo}}}}$ ，其中 ${\varSigma _{\rm{o}}}$ 和 ${\varSigma _{{\rm{uo}}}}$ 分别表示可观事件集和不可观事件集；故障事件集 ${\varSigma _f} \subseteq {\varSigma _{{\rm{uo}}}}$ . 直观上，可观事件集 ${\varSigma _{\rm{o}}}$ 表示可被系统检测到的事件集，而不可观事件集 ${\varSigma _{{\rm{uo}}}}$ 则表示不可被系统检测到的事件集. 在 ${\varSigma ^*}$ 上，可定义一个投影映射 ${P_j}:{\varSigma ^*} \to \varSigma _{\rm{o}}^*$ ，对于事件 $\sigma $ ， $\sigma \in \varSigma $ ， $\varepsilon $ 为空串，

$\begin{array}{l}{P_j}(\varepsilon ) = \varepsilon, \\{P_j}(\sigma ) = \left\{ {\begin{array}{*{20}{l}}{\sigma ,{\text{若}}\sigma \in {\varSigma _{\rm{o}}}};\\{\varepsilon ,{\text{若}}\sigma \in {\varSigma _{{\rm{uo}}}}}.\end{array}} \right.\end{array}$

对于 $s \in {\varSigma ^*},\sigma \in \varSigma $ ，则定义为 ${P_j}(s\sigma ) = {P_j}(s){P_j}(\sigma )$ . ${P_j}$ 的逆映射定义为

$P_{jL}^{ - 1}({s_{\rm{o}}}) = \{ s \in L:{P_j}(s) = {s_{\rm{o}}}\} ,\;s \in {\varSigma ^*},{s_{\rm{o}}} \in \varSigma _{\rm{o}}^*.$

为进一步简化，上述 $p({x'},e|x)$ 可简写为 $p(e|x)$ ，并引入符号 $P_r (e|x) = p(e|x)$ ，且若状态 $x$ 经过事件 $e$ 触发后，再经过事件串 $s$ 后到达某个状态，则其概率定义为

$P_r (es|x) = p(e|x)p(s|\delta (x,e)). $

2 随机离散事件系统故障事件可预测性的形式化

定义1(逻辑可预测性)^[9] 　设 $G$ 是一个离散事件系统， $L$ 为系统 $G$ 的生成语言， ${\sigma _p} \in \varSigma $ 为故障事件，若下列条件满足，则称 ${\sigma _p}$ 在 $L$ 中是可预测的：

$(\exists n \in {\rm N})(\forall s \in \varPsi ({\sigma _p},L))(\exists t \in \bar s)[({\sigma _p} \notin t) \wedge P],$

其中P为

$\begin{array}{l}P:(\forall u \in L)(\forall v \in L/u)[({P_j}(u) = {P_j}(t)) \wedge \\({\sigma _p} \notin u) \wedge (\left\| v \right\| \geqslant n) \Rightarrow ({\sigma _p} \in v)].\end{array}$

直观上，它表示对任意一个故障事件串 $s$ ，一定存在它一个前缀 $t$ ，使得所有与 $t$ 有相同投影的事件串 $u$ 都将有故障事件 ${\sigma _p}$ 发生，即都能够预测故障事件 ${\sigma _p}$ 的发生^[9].

例1　考虑逻辑自动机 ${G_1}$ ，如图1所示，其语言为 ${L_1} = \overline {(a + b){a^*}fc{d^*}} $ . 若可观事件集 ${\varSigma _{\rm{o}}} = \{ a,b,c,d\} $ ， ${\varSigma _{\rm uo}} = \{ f\} $ 为故障事件集. 根据定义1可知，当观测到事件 $a$ 或 $b$ 的发生之后，可能会发生 $f$ 也可能会发生 $a$ . 因此，无法确定 $f$ 是否会发生，即 $f$ 在 ${L_1}$ 上为不可预测的.

定义2(随机可预测性)　设 $G$ 是一个随机离散事件系统， $L$ 为 $G$ 的生成语言， ${\sigma _p} \in \varSigma $ 为故障事件，若下列条件满足，则称 ${\sigma _p}$ 在 $L$ 中是可预测的：

$\begin{array}{l}(\forall \varepsilon > 0)(\exists I \in {\rm N})(\forall s \in \Psi ({\sigma _p},L)),\\(\exists t \in (\bar s \cap {L_{{{\tilde \sigma }_p}}}) \wedge n \geqslant N),\\\{ {P_r}(t:P(t) = 0|t \in (\bar s \cap {L_{{{\tilde \sigma }_p}}})) < \varepsilon \} .\end{array}$

其中， ${L_{{{\tilde \sigma }_p}}} = L \cap {(\varSigma \backslash {\sigma _p})^*}$ ， $P(t)$ 为可预测条件函数，

$P(t) = \left\{ {\begin{array}{*{20}{l}}{1, \;{\text{如果}}(\forall v \in L/{L_u}(t))[\left\| v \right\| \geqslant n \Rightarrow {\sigma _p} \in v]};\\{0, \; {\text{否则}}}.\end{array}} \right.$

这里 ${L_u}(t) = P_j^{ - 1}(t) \cap {(\varSigma \backslash {\sigma _p})^*} \cap L$ .

直观上，它表示对任意一个故障事件串 $s$ ，一定存在它一个前缀 $t$ ，使得所有与 $t$ 有相同投影的事件串 $u$ 都能够使得无法预测故障事件 ${\sigma _p}$ 发生的概率充分小(即 ${P_r}(t:P(t) = 0|t \in (\bar s \cap {L_{{{\tilde \sigma }_p}}})) < \varepsilon $ ).

例2　考虑随机自动机 ${G_2}$ ，如图2所示，其语言为 ${L_2} = \overline {(a + b){a^*}fc{d^*}} $ . 显然，随机自动机 ${G_2}$ 是在逻辑自动机 ${G_1}$ 中添加相应的概率得到的. 对于随机自动机 ${G_2}$ ，若在逻辑预测框架下(即按照定义1)，则在例1中已经得到了 $f$ 是不可预测的结论. 但是在随机预测框架下(即按照定义2)，则 $f$ 是可预测的，这是由于当 ${G_2}$ 运行 $n + 1$ 步后，无法预测故障事件 $f$ 发生的概率可以充分小：以 $(a + b){a^*}$ 中的串 $b{a^{n/2}}{a^{n/2}}$ 为例，其概率为

${P_r}(b{a^{n/2}}{a^{n/2}}) = 0.7 \times {(0.9)^{n/2}}{(0.3)^{n/2}}. $

显然，随着 $n$ 的不断增大，概率 ${P_r}(b{a^{n/2}}{a^{n/2}})$ 将趋向于0，它表示当自动机 ${G_2}$ 运行 $n + 1$ 步后， $f$ 不发生的概率 ${P_r}(f:f \notin (a + b){a^*})$ 趋于0. 因此，可以认为当随机自动机 ${G_2}$ 运行 $n(n \to \infty )$ 步后，故障事件 $f$ 在 ${L_2}$ 上经过一定事件串后将必将发生的概率可以充分大，即在随机预测框架下，故障事件 $f$ 的发生在 ${L_2}$ 上是可预测的.

3 构造随机离散事件系统预测器

为执行随机系统框架下的故障预测，将随机离散事件系统 $G$ 的随机预测器 ${D_G}$ 构建为如下有限状态自动机：

${D_G} = ({Q_d},{\varSigma _{\rm{o}}},{\delta _d},{q_0},{{\varPhi}} ,{\phi _0},{\sigma _p}).$

其中 ${Q_d}$ 表示逻辑元素集； ${\varSigma _{\rm{o}}}$ 表示可观事件集； ${\delta _d}$ 表示预测器转移函数； ${q_0}$ 表示初始逻辑元素，定义为 $\{ ({x_0}, N )\} $ ； ${{\varPhi}} $ 表示为概率转移矩阵； ${\phi _0}$ 表示在 ${q_0}$ 的初始概率函数块，通常取 ${\phi _0} = 1$ ； ${\sigma _p}$ 表示需要预测的故障事件. 具体定义如下： ${Q_d}$ 为所有由 ${q_0}$ 经过 ${\delta _d}$ 而得到的逻辑元素集合，其中逻辑元素具有以下形式：

${q_d} = \{ ({x_1},{l_1}),({x_2},{l_2}), \cdots ,({x_n},{l_n})\} ({x_i} \in {X_0},{l_i} \in \varOmega ).$

在逻辑元素 ${q_d}$ 中将一个状态标签对 $({x_i},{l_i})$ 称为组件， ${q_d}$ 中组件的个数记为 $\left\| {{q_d}} \right\|$ . 为方便起见，逻辑元素 ${q_d}$ 的组件 $({x_i},{l_i})$ 也可表示为 ${c_i} = ({q_d},{x_i},{l_i})$ . 定义故障标签集 ${\varOmega _f} = \{ {F_1},{F_2}, \cdots ,{F_m}\} $ ，它表示在原系统 $G$ 中可能存在的 $m$ 种形式的故障事件的集合. $\varOmega $ 表示为预测器中状态可能带有的标签集合 $\varOmega = \{ N\} \cup {2^{\{ {\varOmega _f}\} }}$ ，其中 $N$ 表示为无故障事件发生的正常状态标签， ${F_i}$ 表示系统中第 $i$ 种形式的故障事件至少发生过一次.

${{ X}_{\rm{o}}}$ 为可观状态集，定义为

$\begin{array}{l}x \in {{X}_{\rm{o}}} \Rightarrow (x = {x_0}) \vee (\exists s \in L:\delta \left( {{x_0},s} \right) = \\x \wedge {s_f} \in {\varSigma _{\rm{o}}}).\end{array}$

${Q_{\rm{o}}}$ 表示在预测器中可能存在的所有逻辑元素集合， ${Q_{\rm{o}}} = {2^{{{X}_{\rm{o}}} \times \varOmega }}$ .

在预测器中，标签传递函数 $ LP:{X_{\rm o}} \times \varOmega \times$ $ \varSigma _{\rm{o}}^* \to \varOmega $ 定义为

$LP(x,l,s) = \left\{ {\begin{array}{*{20}{l}}{\{ N\} , \; {\text{如果}}l = \{ N\} \wedge \forall i[{\varSigma _{{f_i}}} \notin s]};\\{\{ {F_i}:{F_i} \in l \vee {\varSigma _{{f_i}}} \in s\} ,{\text{否则}}}.\end{array}} \right.$

预测器转移函数定义为

${\delta _d}(q,\sigma ) = \mathop \cup \limits_{(x,l) \in q} \mathop \cup \limits_{s \in {L_\sigma }(G,x)} \{ (\delta (x,s),LP(x,l,s))\}. $

逻辑元素中组件间的转移函数：

${\delta _{{\rm comp}}}(q,x,l,s) = ({\delta _d}(q,{P_j}(s)),\delta (x,s),LP(x,l,s)).$

定义逻辑元素概率转移矩阵集

$\begin{array}{l}{{{\varPhi}} _{ij}}(q,{\sigma _{\rm{o}}}) = \sum\limits_{s \in {L_{{\sigma _{\rm{o}}}}}(G,{x_i}):(\delta ({x_i},s),LP({x_i},{l_i},s)) = ({x_i},{l_j})} {P_r (s)}= \\P_r ({c_{{\delta _d}(q,{\sigma _{\rm{o}}}),j}},{\sigma _{\rm{o}}}|{c_{q,i}})\end{array}$

例3 　例2中给出的随机自动机 ${G_2}$ 的预测器可构建为如图3所示的 ${D_{{G_2}}}$ . 对于如图4所示的随机自动机 ${G_3}$ ，其中 ${\varSigma _{\rm{o}}} = {\rm{\{ }}a,b,c,d{\rm{\} }}$ ， ${\varSigma _{{\rm{uo}}}} = \{ u,f\} $ ， ${\varSigma _f} = \{ f\} $ ，其预测器可以构建为如图5所示的 ${D_{{G_3}}}$ .

4 随机离散事件系统故障事件可预测性的充分必要条件

令 ${F_D}$ 为预测器 ${D_G}$ 中只带 $N$ 标签的正常状态的集合，且该类状态的下一个继承状态将为带有故障标签的非正常状态，即

$\begin{array}{l}{F_D} = \{ {x_D} \in Q_D^N:\exists {y_D} = {\delta _D}({x_D},{\sigma _{\rm{o}}}),\\({\sigma _{\rm{o}}} \in {\varSigma _{\rm{o}}},{y_D} \notin Q_D^N)\}.\end{array} $

定义3　设 ${D_G}$ 为离散事件系统 $G$ 的预测器，如果逻辑元素 $q$ 中的任一组件 $(x,l) \in q$ 都有 ${F_i} \in l$ ，则称逻辑元素 $q$ 为确定状态(certain state). 反之，称 $q$ 为非确定状态(uncertain state).

显然，如果 $q$ 为确定状态，则所有到达 $q$ 的串 $s$ 都至少包含一个故障事件，即 $\sigma \in s(\sigma \in {\varSigma _{{f_i}}})$ .

这里还需要马尔可夫链的一些相关概念. 假设 $a$ 和 $b$ 是马尔可夫链上的两个状态， ${\rho _{ab}}$ 表示 $a$ 到 $b$ 的概率，若 ${\rho _{ab}} > 0$ 表示 $a$ 可到达 $b$ ；若 ${\rho _{aa}} = 1$ ，则称该状态为重复态(recurrent)；若 ${\rho _{aa}} < 1$ ，则称该状态为瞬时态(transient). 在马尔可夫链系统中如果某个状态为重复态，则在到达这个状态后将再次无限次的回到该状态；反之，在马尔可夫链系统中如果某个状态为瞬时态，则在离开这个状态后将来永远不再回到该状态.

引理1^[17] 　设 ${X}$ 为一马尔可夫链上的有限状态空间， ${ T} \subset { X}$ 为瞬时态集， $x \in { X}$ 为其中的任一状态， $t$ 为以状态 $x$ 作为起始点的任意序列的事件串，则有以下关系式： $\forall \varepsilon > 0,\exists n \in {\rm N}$ ，使得

$P_r (t:\delta \left( {x,t} \right) \in {\rm T}|t \in L(G,x) \wedge \left\| t \right\| = n) < \varepsilon .$

下面将给出随机离散事件系统故障事件可预测性的充分必要条件.

定理1 　设 $G = (Q,\varSigma ,p,{q_0})$ 为一个随机离散事件系统， $L$ 为 $G$ 的生成语言， ${D_G} = ({Q_D},{\varSigma _{\rm{o}}},{\delta _D},{q_{D,0}},{\sigma _p})$ 为 $G$ 的预测器， ${\sigma _p}$ 为待预测的故障事件. ${\sigma _p}$ 在 $L$ 上是随机可预测的充分必要条件为：对于任一 ${q_D} \in {F_D}$ ，所有由 $Ac({D_G},{q_D})$ 可达的包含有重复态组件的逻辑元素都是确定状态.

证明 　先证明必要性. 设 ${\sigma _p}$ 在 $L$ 上是随机可预测的，下面用反证法来证明任一 ${q_D} \in {F_D}$ ，所有由 $Ac({D_G},{q_D})$ 可达的包含有重复态组件的逻辑元素都是确定状态.

假设存在 ${q_D} \in {F_D}$ 使得由 $Ac({D_G},{q_D})$ 可达的包含有重复态组件的逻辑元素 $q$ 为非确定状态，即 $q$ 中包含带有正常标签 $N$ 的重复态组件或 $q$ 为包含有带故障标签 ${F_i}$ 的重复态组件的非确定状态.

1) 若逻辑元素 $q$ 中包含带有正常标签 $N$ 的重复态组件 ${c_r}$ ，则该重复态组件 ${c_r}$ 经过 $n$ 步转移后得到的组件仍为 ${c_r}$ ，即对于 $s \in \varPsi ({\sigma _p},L)$ ， $t \in \bar s({\sigma _p} \notin t)$ ，与 $t$ 映射相同的 $u({\sigma _p} \notin u)$ ， ${P_j}(t) = {P_j}(u)$ ， $u$ 在 $L$ 中的后接语言 $v = L/u$ ，在系统 $G$ 中由初始状态 ${x_0}$ 经过 $uv$ 转移到状态 $\delta ({x_0},uv)$ ，令 $x$ 为 $c_r$ 中的原系统 $G$ 的状态 $x \in Q$ ，且令状态 $x = \delta ({x_0},uv)$ ，因为 $c_r$ 为带正常标签 $N$ 的重复态组件，由标签传递关系可知串 $uv$ 中不会包含故障事件，即 ${\sigma _p} \notin uv$ . 从而有可预测条件函数 $P(t) = {\rm{0}}$ . 由此，有

${P_r}(t:P(t) = 0|t \in (\bar s \cap {L_{{{\tilde \sigma }_p}}})) = 1. $

所以， ${P_r}(t:P(t) = 0|t \in (\bar s \cap {L_{{{\tilde \sigma }_p}}})) > {\rm{1 - }}\varepsilon $ .

根据定义2得， ${\sigma _p}$ 在 $L$ 上不是随机可预测的，这与假设 ${\sigma _p}$ 在 $L$ 上是随机可预测相矛盾.

2) 若逻辑元素 $q$ 为包含有带故障标签 ${F_i}$ 的重复态组件的非确定状态，不妨设该重复态组件为 ${c_f}$ . 设 ${c_0} = ({q_0},{x_0},{l_0})$ 为预测器 ${D_G}$ 中的初始组件，其中 ${l_0} = N$ . 令 ${c_0}$ 经过事件串 ${\omega _1}$ 后得到 ${c_f}$ ，即 ${c_f} = {\delta _{\rm comp}}({c_0},{\omega _1})$ ， ${c_f} \in q$ ，由于 $q$ 为非确定态，即 $q$ 中存在正常标签 $N$ ，此时将存在某个串 ${s_1}$ ， ${P_j}({s_1}) = {P_j}({\omega _1})$ ， $q = {\delta _d}({q_0},{P_j}({s_1}))$ ， ${s_1}$ 为不含任何故障事件的串，若假设 ${s_1} = uv$ ，则对于 $s \in \varPsi ({\sigma _p},L)$ ， $t \in \bar s({\sigma _p} \notin t)$ ，与 $t$ 映射相同的 $u({\sigma _p} \notin u)$ ， ${P_j}(t) = {P_j}(u)$ ， $u$ 在 $L$ 中的后接语言 $v = L/u$ ，一定存在 ${\sigma _p} \notin v$ ( $({\sigma _p} \notin ({s_1} = uv)) \Rightarrow {\sigma _p} \notin v$ )，因此可以得到 ${P_r}(t:P(t) = 0|t \in (\bar s \cap {L_{{{\tilde \sigma }_p}}})) > {\rm{1 - }}\varepsilon $ ；由于 ${c_f}$ 为重复态组件，有 ${c_f} = {\delta _{\rm comp}}({c_f},{({\sigma _1}{\sigma _2}\cdots{\sigma _n})^k})$ ，则可得 ${c_f} = $ $ {\delta _{\rm comp}}({c_0},{\omega _1}{({\sigma _1}{\sigma _2}\cdots{\sigma _n})^k})$ ，同理存在与串 ${s_1}$ 类似的串 ${s_2}$ ， ${P_j}({s_2}) = {P_j}({\omega _1}{({\sigma _1}{\sigma _2}\cdots{\sigma _n})^k})$ ， $q = {\delta _d}({q_0},{P_j}({s_2}))$ ，使得 ${s_2} = uv$ ， ${\sigma _p} \notin v$ . 因此，在经过 ${({\sigma _1}{\sigma _2}\cdots{\sigma _n})^k}$ 后也有 ${P_r}(t:P(t) = 0|t \in (\bar s \cap {L_{{{\tilde \sigma }_p}}})) > {\rm{1 - }}\varepsilon $ . 因此， ${\sigma _p}$ 在 $L$ 上不是随机可预测的，这也与假设相矛盾.

再证明充分性. 设对于任一 ${q_D} \in {F_D}$ ，所有由 $Ac({D_G},{q_D})$ 可达的包含有重复态组件的逻辑元素都是确定状态，下面证明 ${\sigma _p}$ 在 $L$ 上是可预测的.

设 $C$ 为预测器 ${D_G}$ 中所有组件的集合， ${T_c}$ 为瞬时态组件集合 ${T_c} \in C$ ， ${R_c}$ 为重复态组件的集合 ${R_c} \in C$ . 由引理1得

$P_r (t:{\delta _{\rm comp}}\left( {c,t} \right) \in {{\rm T}_c}|t \in L(G,x) \wedge \left\| t \right\| = n) < \varepsilon, $

(1)

即在系统 $G$ 中，某事件串 $\omega $ 由初始状态出发经过 $n$ 步后到达重复态组件的概率为 $1 - \varepsilon $ . 因为至少会到达一个重复态组件，且该重复态组件包含在一个确定状态的逻辑元素中，因此必有 ${\sigma _p} \in \omega $ . 不妨设该包含重复态组件的逻辑元素为 $q$ ， $q = $ $ {\delta _d}({q_D},{s_{\rm{o}}})({s_{\rm{o}}} \in \varSigma _{\rm{o}}^*)$ ，由于 ${q_D}$ 为不带故障标签的逻辑元素，若 $q$ 为带故障标签的确定态逻辑元素，说明由 $q$ 到 ${q_D}$ 将要发生故障，从而对于任意 $s \in {{\varPsi}} ({\sigma _p},L)$ 和 $t \in \bar s({\sigma _p} \notin t)$ ，与 $t$ 映射相同的 $u({\sigma _p} \notin u)$ ， ${P_j}(t) = {P_j}(u)$ ， $u$ 在 $L$ 中的后接语言 $v = L/u$ ，令 $\omega = uv$ ，则 ${\sigma _p} \in v$ . 由此，可预测条件函数为 $P(t) = 1$ . 在式(1)中，当 $n$ 趋向于无穷大时，系统可预测的概率：

${P_r}(t:P(t) = 1|t \in (\bar s \cap {L_{{{\tilde \sigma }_p}}})) > 1 - \varepsilon ,$

即 ${P_r}(t:P(t) = 0|t \in (\bar s \cap {L_{{{\tilde \sigma }_p}}})) < \varepsilon $ . 根据定义2得， ${\sigma _p}$ 在 $L$ 上是可预测的.

根据定理1可知，判断故障事件的随机可预测性只需要考虑包含有重复态组件的逻辑元素是否满足定理1条件. 为了计算随机离散事件系统 $G$ 中的所有重复态，我们引入一个关于预测器的扩展马尔可夫转移矩阵. 定义 ${{\varGamma}} :{Q_d} \times {Q_d} \to {{\rm M}_{[0,1]}}$ 为

${{\varGamma}} ({q_i},{q_j}) = \sum\limits_{{e_{\rm{o}}} \in {\varSigma _{\rm{o}}}:\delta ({q_i},{e_{\rm{o}}}) = {q_j}} {{{\varPhi}} ({q_i},{e_{\rm{o}}})} ,$

其中矩阵 ${{\varGamma}} ({q_i},{q_j})$ 的格式为 $\left\| {{q_i}} \right\| \times \left\| {{q_j}} \right\|$ ，若不存在 ${q_i}$ 到 ${q_j}$ 的转移，则定义 ${{\varGamma}} ({q_i},{q_j})$ 为0. 文献[17]中已证明如下 ${{\varPi}} ({D_G})$ 为一个马尔可夫转移矩阵

${{\varPi}} ({D_G}) = \left[ {\begin{array}{*{20}{c}} {{{\varGamma}} ({q_1},{q_1})}& \cdots &{{{\varGamma}} ({q_1},{q_n})} \\ \vdots & {\rm{}} & \vdots \\ {{{\varGamma}} ({q_n},{q_1})}& \cdots &{{{\varGamma}} ({q_n},{q_n})} \end{array}} \right].$

例如，图3中随机自动机 ${G_2}$ 的预测器的扩展马尔可夫转移矩阵为

$\begin{array}{*{20}{c}} {}&{({q_1},1,N)}&{({q_2},2,N)}&{({q_3},4,F)} \\ {({q_1},1,N)}&0&1&0 \\ {({q_2},2,N)}&{0.9}&0&{0.1} \\ {({q_3},4,F)}&0&0&1 \end{array}$

即 ${{\varPi}} ({D_{{G_2}}}) = \left[ {\begin{array}{*{20}{c}} 0&1&0 \\ {0.9}&0&{0.1} \\ 0&0&1 \end{array}} \right]$ . 从矩阵中可看出，逻辑元素 ${q_3}$ 经过某一事件后返回 ${q_3}$ 的概率为1，即 ${q_3}$ 中的组件 $c = ({q_3},4,F)$ 为一个重复发生的组件，类似于一个状态环.

例4　考虑例3中的随机自动机 ${G_3}$ ，如图4所示，其中 ${\varSigma _{\rm{o}}} = \{ a,b,c,d\} $ ， ${\varSigma _{{\rm{uo}}}} = \{ u,f\} $ ， ${\sigma _p} = f$ . 记 ${G_3}$ 的生成语言为 ${L_3}$ ，并构建 ${G_3}$ 的预测器 ${D_{{G_3}}}$ ，如图5所示. 因此，预测器 ${D_{{G_3}}}$ 的扩展马尔可夫矩阵 ${{\varPi}} ({D_{{G_3}}})$ 为

${{\varPi}} ({D_{{G_3}}}) \!=\! \left[\!\! {\begin{array}{*{20}{c}} 0\!&\!1\!&\!0\!&\!0\!&\!0\!&\!0\!&\!0\!&\!0\!&\!0\!&\!0 \\ 0\!&\!0\!&\!{0.7}\!&\!{0.3}\!&\!0\!&\!0\!&\!0\!&\!0\!&\!0\!&\!0 \\ 0\!&\!0\!&\!0\!&\!0\!&\!0\!&\!1\!&\!0\!&\!0\!&\!0\!&\!0 \\ 0\!&\!0\!&\!0\!&\!0\!&\!{0.5}\!&\!0\!&\!{0.5}\!&\!0\!&\!0\!&\!0 \\ 0\!&\!0\!&\!0\!&\!0\!&\!0\!&\!0\!&\!0\!&\!1\!&\!0\!&\!0 \\ 0\!&\!0\!&\!0\!&\!0\!&\!0\!&\!0\!&\!0\!&\!0\!&\!1\!&\!0 \\ 0\!&\!0\!&\!0\!&\!0\!&\!0\!&\!0\!&\!0\!&\!0\!&\!0\!&\!1 \\ 0\!&\!0\!&\!0\!&\!0\!&\!{0.5}\!&\!0\!&\!0\!&\!0\!&\!0\!&\!{0.5} \\ 0\!&\!0\!&\!0\!&\!0\!&\!0\!&\!0\!&\!0\!&\!0\!&\!1\!&\!0 \\ 0\!&\!0\!&\!0\!&\!0\!&\!0\!&\!0\!&\!0\!&\!0\!&\!0\!&\!1 \end{array}} \!\!\right].$

从 ${{\varPi}} ({D_{{G_3}}})$ 中可以看出，逻辑元素 ${q_7}$ 和 ${q_8}$ 分别包含有重复态组件 ${c_7} = ({q_7},5,N)$ 和 ${c_8} = ({q_8},7,F)$ ，并且从图5可知， ${q_8}$ 为确定状态，而 ${q_7}$ 为非确定状态. 因此，取 ${F_D} = \{ (3,N),(6,N)\} $ ，则由 $Ac({D_G},{q_D})$ 可到达的包含有重复态组件的逻辑元素不都是确定状态. 根据定理1得， ${\sigma _p}$ 在 ${L_3}$ 上不是随机可预测的.

例5　考虑随机自动机 ${G_4}$ ，如图6所示，其中 ${\varSigma _{\rm{o}}} = \{ a,b,c,d\} $ ， ${\varSigma _{{\rm{uo}}}} = \{ u,f\} $ ， ${\sigma _p} = f$ .

设随机自动机 ${G_4}$ 的生成语言为 ${L_4}$ ，构建 ${G_4}$ 的预测器 ${D_{{G_4}}}$ ，如图7所示.

由预测器 ${D_{{G_4}}}$ 得，预测器的扩展马尔可夫矩阵 ${{\varPi}} ({D_{{G_4}}})$ 为

${{\varPi}} ({D_{{G_4}}}) = \left[ {\begin{array}{*{20}{c}} 0&{0.3}&{0.7}&0&0&0&0&0 \\ 0&0&0&{0.4}&{0.6}&0&0&0 \\ 0&0&0&{0.5}&0&{0.5}&0&0 \\ 0&0&0&{0.8}&0&0&{0.2}&0 \\ 0&0&0&{0.8}&0&0&{0.2}&0 \\ 0&0&0&{0.5}&0&0&0&{0.5} \\ 0&0&0&0&0&0&1&0 \\ 0&0&0&{0.5}&0&0&0&{0.5} \end{array}} \right].$

从 ${{\varPi}} ({D_{{G_4}}})$ 中可知，逻辑元素 ${q_5}$ 中包含有重复态组件 ${c_5} = ({q_5},7,F)$ ，且由图7得， ${q_5}$ 为确定状态. 取 ${F_D} = \{ \{(5,N)\},\{(5,N),(4,N)\}\} $ ，则所有由 $Ac({D_G},{q_D})$ 可到达的包含有重复态组件的逻辑元素是确定状态. 因此，根据定理1得， ${\sigma _p}$ 在 ${L_4}$ 上是可预测的.

5 结论

本文针对随机离散事件系统模型，提出了一种相应的故障预测方法，该方法将逻辑离散事件系统的故障预测方法拓展到带有概率结构的离散事件系统. 通过对随机离散事件系统的故障可预测性的形式化，并引入概率转移矩阵构建了一个故障预测器自动机，得到了一个关于随机离散事件系统的故障可预测性的充分必要条件. 由此得到了判定随机离散事件系统是否具有故障可预测性的方法，从而实现对故障事件在其发生之前的准确预测.

在本文研究的基础上，可以将集中型系统拓展至分布式系统，进一步考虑分布式随机离散事件系统的故障预测问题. 同时，如何对本文提出的故障预测方法应用到实际应用系统中，并通过相关算法编程和应用MATLAB等仿真工具，解决故障预测编程语言的算法实现与算法优化等也是非常有意义的问题. 在后续研究中，笔者将在本文的基础上进一步深入探讨.