离散事件系统是由离散事件按照一定的运行规则相互作用而导致状态演化的一类动态系统.它已经被广泛地应用到计算机集成制造系统、交通运输、军事指挥、计算机网络、柔性生产线以及通讯网络^[1].在实际应用中, 可以对事物, 如机械、进程等进行离散化建模得到一个离散事件系统, 但系统运行的某个失误或系统操作的某种不当易使离散事件系统中出现一些故障.因此, 容错离散事件系统从一定意义上来说是更加符合实际的一类离散事件系统.

近年来, 对离散事件系统容错控制的研究引起了国内外的广泛关注.文献[2-15]阐述了离散事件系统对故障事件的处理及其相应模型, 其中文献[2-4]运用错误模式的方法, 把离散事件系统分成多个模式.文献[8]在全可观的情况下, 研究系统的容错性及错误恢复.文献[9-10]研究传感器发生错误时, 控制器如何采取相应的措施—控制器会被转换^[9]或重新配置^[10].又如, 在自动公路系统(automated highway systems)中, 错误应对模块必须对故障事件实施纠错, 以防止车辆碰撞^[11-12].相关的研究还包括文献[13-14], 其中文献[13]研究Petri网的容错性; 文献[14]研究分布式容错控制.文献[15]基于错误矩阵方程, 研究消错学理论.

本文研究离散事件系统的可纠错性, 为离散事件系统的可靠性提供理论支持.在文献[16-17]中, 一个系统是非屏蔽容错(nonmasking fault-tolerant)的当且仅当系统遇到错误后, 系统仍然符合规范.本文正是在文献[16-17]的基础上, 考虑系统在受监控的情况下如何实现它的非屏蔽容错性.事实上, 可纠错性是非屏蔽容错性的必要条件, 即当系统遇到错误后, 可纠错系统可转移到可接受状态.因此, 实现系统的可纠错性是实现系统非屏蔽容错性的重要一步, 对系统避免入侵、保证系统安全有重要意义.

在图论中, 树图可表示根节点到叶子节点的各个路径.类似地, 状态树可表示根节点状态到各叶子状态的各个路径.当一棵状态树的叶子节点全是可接受状态时, 根节点一定能转移到可接受状态, 而这一性质正是可纠错状态的必要条件.在下文可以知道, 状态树可加上约束变为判定树, 判定树能构造出可纠错状态的充要条件.因此, 状态树是描述可纠错状态的可靠模型.本文基于状态树, 给出了可纠错状态的形式化定义, 并证明了可纠错状态一定能转移到可接受状态这一性质.

此外, 本文给出判定可纠错状态的算法, 此算法通过一个状态能构造出的最小递归深度的状态树, 判定该状态的可纠错性, 并且此算法具有多项式时间复杂度.

1 离散事件系统可纠错性的非形式讨论

首先引入控制器的概念.如图 1所示, 控制器是对离散事件系统传送指令的部件.

控制器具有以下3种功能:

(1) 强制添加可控事件, 在不可控事件发生之前时, 控制器可启动事件, 对当前状态实施控制.本文假定控制器只能强制添加可控事件.

(2) 使接下来的可控事件不生效(disable).

(3) 终止系统.当系统出现严重错误时, 控制器终止系统.

规定控制器具有上述3个功能是合理的, 比如, 通常的电灯开关系统可以视为一个控制器, 事件“开”和“关”都是可控的, 如果想电灯由关变为开, 则可添加事件(也就是拨动开关)“开”; 如果想让电灯保持开状态, 则可禁止(也就是不让其生效)事件“关”发生.如果事件“开”发生, 电灯仍保持关状态(电灯可能损坏了), 则可令系统终止.

在实际应用中, 离散事件系统的运行有时会出现故障, 这些故障称为故障事件.当故障事件发生后, 系统停留在不可接受状态, 此时控制器传送指令, 对系统实施控制, 使得系统重新停留在可接受状态, 这一过程称作纠错.

例1:设自动机如图 2所示, 并设事件a是不可控的, 事件b是可控的.当系统停留在状态1时, 控制器可强制添加可控事件b, 使得系统停留在可接受状态3.因此, 当系统停留在状态1时, 控制器可实行纠错.

例2:在例1中, 重新假设事件a是可控的, 事件b是不可控的.当系统停留在状态1时, 如果事件a发生, 那么控制器可使事件a不生效, 系统仍然停留在状态1, 而事件b发生, 系统停留在可接受状态3.因此, 当系统停留在状态1时, 控制器可使系统不能转移到状态2, 从而当系统发生状态转移时, 系统一定是转移到可接受状态3.综上所述, 当系统停留在状态1时, 控制器可实行纠错.

例3:设自动机如图 3所示, 并设所有事件都是不可控事件, 当系统停留在状态1时, 系统是可纠错的.理由如下:系统在状态1发生任何状态转移, 系统都会停留在可接受状态.因此, 在这种情况下, 控制器不实行任何纠错行动, 系统依然是可纠错的.

2 离散事件系统可纠错性的形式化

综合上述情况, 可以对离散事件系统的可纠错性形式化.

定义1   (离散事件系统):离散事件系统是一个5元组:

$ G: = \left( {Q, \Sigma, \delta, {q_0}, {Q_{\rm{a}}}} \right), $

其中, Q为状态集, Σ为事件集, δ:Q×Σ→Q为转移函数, q₀为起始状态, Q_a为可接受状态集且Q_a⊆Q.

状态集分为可接受状态集和不可接受状态集, 不可接受状态集记为Q_ua, Q_ua=Q-Q_a.事件集分为可控事件集和不可控事件集, 可控事件集记为Σ_c, 不可控事件集记为Σ_uc, Σ_uc=Σ-Σ_c.令Σ^*为事件集Σ的kleene闭包, 令ε表示空字符串, 对于任意的q∈ Q, 有δ(q, ε)=q.对于给定的q∈ Q, σ∈Σ, 如果δ(q, σ)未定义, 则记为δ (q, σ) $\tilde !$; 如果δ(q, σ)有定义, 则记为δ(q, σ)!.同理, 对于给定的q∈ Q, σ′∈Σ^*, 如果δ(q, σ′)未定义, 则记为δ(q, σ′)$\tilde !$; 如果δ(q, σ′)有定义, 则记为δ(q, σ′)!.

定义2   (邻域):设一个状态q∈ Q, 则集合{p∈ Q |∃a∈Σ(δ(q, a)=p)}称为q的邻域, 记q的邻域为N(q).集合

$ \{ p \in {\rm{ }}Q{\rm{ }}|\exists a \in {\Sigma _{\rm{c}}}(\delta \left( {q, a} \right) = p)\} $

称为q的可控邻域, q的可控邻域为N_c(q).集{p∈ Q |∃a∈Σ_uc(δ(q, a)=p)}称为q的不可控邻域, 记q的不可控邻域为N_uc(q).

显然, 对于任意q∈Q, N_uc(q)⊆N(q), N_c(q)⊆N(q).

例4:设自动机如图 4所示, 状态1的邻域N(1)是状态集{2, 3, 4}, 状态4的邻域N(4)是状态集{5, 6}, 其余状态的邻域为空集.进一步设事件a和d是可控事件, 其余事件为不可控事件, 那么状态1的可控邻域N_c(1)={2}, 不可控邻域N_uc(1)={3, 4};状态4的可控邻域N_c(4)={5}, 不可控邻域N_uc(4)={6}.

定义3  (状态树):设状态树的集合为T, 一个状态树t∈T是一个递归二元组:

$ t: = ({n_{\rm{r}}}, R({n_{\rm{r}}})). $

其中n_r∈ Q是t的根节点, R(n_r)是二元关系, R(n_r)⊆{n_r}×T.

定义4   (子树):设t=(n_r, R(n_r))∈T是状态树, t的子树集为T_s(t), T_s(t)⊆T.

(1) t是t本身的子树, 即t∈T_s(t).

(2) 如果对于任意状态树t′∈T, (n_r, t′)∈ R(n_r), 则称t′是t的直系子树.如果t′是t的直系子树, 则t′∈T_s(t).记t的直系子树集为T_dl(t).

(3) 对于任意状态树t₁t₂…t_n, 如果对于任意正整数k(1 < k≤n), t_k∈T_dl(t_k-1), 则t_n∈T_s(t₁).

定义5  (节点):设t=(n_r, R(n_r))∈T是状态树, 记t的节点集为n_s(t), n_s(t)⊆Q.

(1) t的根节点n_r是t的节点.即n_r∈n_s(t).

(2) 对于任意状态树

$ t = (n',R({{n'}_{\rm{r}}})) \in T, $

如果t′∈T_s(t), 则n′_r∈n_s(t).

设状态树t∈T, t的直系子树的根节点称为t的直系节点, 记t的直系节点集为n_dl(t).

在不发生混淆的情况下, 本文用状态树的所有节点来表示状态树.

定义6  (叶子):设

$ t = \left( {{n_{\rm{r}}}, R\left( {{n_{\rm{r}}}} \right)} \right), t\prime = \left( {{{n'}_{\rm{r}}}, R\left( {n{\prime _{\rm{r}}}} \right)} \right) \in T $

是状态树, 如果t′是t的子树且R(n_r′) =φ, 其中φ表示空集, 则称t′是t的叶子.

注意, 叶子本质上是状态树(只有一个节点的状态树).在不发生混淆的情况下, 叶子既可看作节点, 也可看作状态树.当叶子被看作节点时, 称叶子为叶子节点.

定义7    (递归深度):设t=(n_r, R(n_r))∈T是状态树, 记t的递归深度为D(t), D(t)∈ $ \mathbb{Z}$.如果t是叶子, 则D(t)=0.否则,

$ D\left( t \right) = {\rm{max}}\{ D\left( {t\prime } \right) + 1|\left( {{n_{\rm{r}}}, t\prime } \right) \in R({n_{\rm{r}}})\}, $

如果D(t)是有限的, 则称t是有限状态树.

定义8   (判定树):设t=(n_r, R(n_r))∈T是状态树, 对于t的任意子树

$ t^\prime = \left( {n{ _{\rm{r}}^\prime}, R\left( {n{ _{\rm{r}}^\prime}} \right)} \right) \in {T_{\rm{s}}}(t), $

如果t′满足

$ {n_{{\rm{dl}}}}\left( {t^\prime } \right) = \left( {{N_{{\rm{uc}}}}\left( {n{ _{\rm{r}}^\prime}} \right)} \right) \vee \left( {{n_{{\rm{dl}}}}\left( {t^\prime } \right) \subseteq {N_{\rm{c}}}\left( {n{ _{\rm{r}}^\prime}} \right)} \right), $

(1)

则称t是判定树.

例5:在例4中, 进一步设可接受状态集为{2, 3, 6}, 其余状态为不可接受状态, 事件e是可控事件, 其余事件是不可控事件.考虑图 5的状态树t={1, 2, 3, 4, 6}:

状态树t有5棵子树, 分别是{1, 2, 3, 4, 6}、{2}、{3}、{6}和{4, 6}.树{1, 2, 3, 4, 6}的根节点是状态1, 而状态1的不可控邻域等于其直系节点, 即n_dl(1)=N_uc(1), 因此树{1, 2, 3, 4, 6}符合定义8的式(1).而n_dl(2)=φ⊆N_c(2), 其中φ表示空集, 因此树{2}也符合定义8的式(1), 同理, 树{3}和树{6}符合式(1), 对于树{4, 6}, n_dl(4)={6}⊆N_c(6), 符合式(1).根据定义8, 状态树t是判定树.

定义9    (可纠错状态):设离散事件系统G=(Q, Σ, δ, q₀, Q_a), 状态q∈ Q, 如果存在以q为根节点的有限判定树t=(q, R(q)), 使得t的所有叶子节点都是可接受状态, 则q是可纠错状态; 记可纠错状态集为I.

简单来说, 如果一个状态q∈ Q的可控邻域存在可纠错状态, 则q是可纠错状态, 如果q的不可控邻域的元素全是可纠错状态, 则q也是可纠错状态.

例6:在例5中, 树t={1, 2, 3, 4, 6}是判定树, 根节点是状态1, 且树t的叶子节点全是可接受状态, 因此状态1是可纠错状态.

定理1   如果一个状态q∈ Q 是可纠错的, 则存在事件串s∈Σ^*, 使得

$ \delta \left( {q, s} \right) \in {\rm{ }}{Q_{\rm{a}}}. $

证  如果q是可纠错状态, 根据定义9, 存在以q为根节点的有限判定树t, 使得t的所有叶子节点全是可接受状态.对递归深度D(t)作归纳证明:

基础步:设D(t)=0, 则t是叶子, 且叶子的根节点q∈ Q_a, 显然δ(q, ε)∈ Q_a, 所以∃s∈Σ^*(δ(q, s)∈ Q_a).定理成立.

归纳步:设D(t)=k, 因为t是判定树, 且根据定义4, t是t本身的子树, q是t的根节点.根据定义8推出:

(n_dl(t)=N_uc(q))∨(n_dl(t)⊆N_c(q)), 再推出

n_dl(t)⊆N(q), 再推出

∀q′∈n_dl(t)∃a∈Σ(δ(q, a)=q′).根据定义7可推出

∀(q′, R(q′))∈T_dl(t)(D(q′, R(q′)) < D(t)=k), 再根据归纳假设推出

∀q′∈n_dl∃s∈Σ^*(δ(q, s)∈Q_a), 结合以上式子推出

∀q′∈n_dl(t)∃a∈Σ∃s∈Σ^*(δ(q, a)=

q′∧δ(q′, s)∈Q_a), 再推出

∃s∈Σ^*(δ(q, s)∈ Q_a), 定理成立.

综上所述, 如果一个状态q∈Q是可纠错的, 则∃s∈Σ^*(δ(q, s)∈ Q_a).证明完毕.

定理1对可纠错模型有着重要意义, 它表明:如果一个状态是可纠错的, 则此状态能转移到可接受状态.在现实应用中, 一个控制规范K往往是由能转移到可接受状态的字符串组成的, 因此可纠错性往往是可控性的充分条件.

3 可纠错状态的判定算法

算法1(判定可纠错状态):

(1) 创建一个初始为空的状态集合A, A称作待判定状态集, 再创建一个初始为空的状态集B, B称作当前可纠错状态集.

(2)把所有可接受状态加入到状态集B中, 把所有不可接受状态加入到状态集A中.如果状态集B为空, 则跳到第5步.

(3) 如果状态集A为空, 则跳到第5步.否则, 从A中取出第1个状态q₁, 判定q₁:如果∃e∈Σ_c(δ(q₁, e)∈B), 则把状态q₁加入到状态集B中, 从A中删除状态q₁, 重新开始第3步.否则, 从A中取出第2个状态q₂, 用上述方法判定q₂, 如此类推, 直到从A中取出最后1个状态q_n, 并判定q_n.

(4) 从A中取出第1个状态q₁, 判定q₁:如果N_uc(q₁)⊆B, 则把状态q₁加入到状态集B中, 从A中删除状态q₁, 跳到第3步.否则, 从A中取出第2个状态q₂, 用上述方法判定q₂, 如此类推, 直到从A中取出最后一个状态q_n, 并判定q_n.

(5) 把状态集A设定为不可纠错状态集, 状态集B设定为可纠错状态集.

算法结束.

算法1中, 程序每跳到第3步一次, 则称作一次迭代.从算法1中可得以下性质:

性质1  全部状态的可纠错性只需m次迭代即可得到判定, 其中m≤|Q|.

因为在一次迭代中, 如果此次迭代不是最后一次迭代, 则有且只有一个状态的纠错性得到判定, 而状态数目为|Q|, 因此迭代次数小于等于|Q|.

性质2  第k次迭代最多需进行|δ|-k+1次比较, 其中|δ|表示转移函数(作为一个集合)的基数.一般地, 0≤|δ|≤|Q|×|Σ|, 其中|Q|、|Σ|分别表示状态数和事件数.

结合性质1、2, 可得算法的时间复杂度.

性质3  算法1的时间复杂度是Ο(|δ|³)的.

4 结论

在故障可诊断但不可控的前提下, 本文研究了离散事件系统基于状态树的可纠错性, 给出了可纠错性的形式化定义, 使得可纠错模型符合现实应用中的规范.同时给出了判定可纠错状态的算法, 使得算法具有多项式时间复杂度.