离散事件系统基于模式的安全故障诊断

刘富春 唐顺桥 赵 锐 邓秀勤 崔洪刚

(1.广东工业大学计算机学院,广东广州 510006;2.广东工业大学应用数学学院,广东广州 510006;3.广东省东源县科技创新中心,广东河源 517500)

1 引言

近年来，离散事件系统的故障诊断研究引起了国内外众多学者的高度关注.自Sampath等人在文献[1]中提出基于诊断器的故障诊断方法以来,这种方法就被广泛使用.Zad等人[2]提出了一种基于状态的故障诊断机制.Moreira等人[3]将文献[1]的诊断算法进行优化,提出了一种具有多项式时间复杂度的故障诊断方法.文献[4]针对随机系统提出了一种随机离散事件系统的故障诊断方法.笔者在文献[5]中提出了一种适用于处理不精确和不确定特性的模糊离散事件系统的模糊故障诊断方法.吉林大学欧阳丹彤教授等人在文献[6]中深入研究了不完备离散事件系统的故障诊断等问题.

然而,上述文献中的故障诊断方法都是将引起故障的操作视为一个事件(即故障事件).近年来,针对由多个事件组成的故障(称为故障模式),也引起了许多学者的关注.例如,Sahika等人在文献[7]中提出了基于模式的故障诊断方法,将Sampath等人提出基于诊断器的故障诊断方法[1]推广至对故障模式的诊断;文献[8]对离散事件系统基于模式的故障诊断方法提出了一种语义分析方法,对文献[7]中的模式诊断方法进行了改进;文献[9]对离散事件系统中的模式语句进行了预测.

虽然运用上述不同的故障诊断方法都可以在故障发生后的一定时延内将所发生的故障诊断出来,但在故障在发生后系统仍然可能会执行一些被禁止的非法操作,为此,Paoli等人[10]在文献[1]的基础上对故障诊断提出了安全性要求,得到了一种安全故障诊断方法;随后,Deng等人[11]也提出了基于状态诊断的离散事件系统的安全诊断方法.文献[12]对文献[10]中的方法进行了改进,提出了一种具有多项式时间复杂度的安全诊断方法.

本文继续文献[7,10]的工作,针对离散事件系统基于模式的故障诊断的安全性问题,提出一种基于模式的安全故障诊断方法.先根据目前最常用的S型和T型两种模式,引入S型和T型模式的可诊断条件和安全性条件,对离散事件系统基于模式的安全可诊断性进行形式化.再通过构造一个非法语言识别器对非法操作进行识别.然后在非法语言识别器的基础上,构建相应的安全诊断器,对系统发生的故障模式实施安全诊断.最后,分别得到一个关于S型和T型模式的系统安全可诊断性的充分必要条件.该方法不仅能将触发系统的故障模式诊断出来,还保证了系统在诊断期间不会执行任何被禁止的不安全操作.

2 离散事件系统

一个离散事件系统是指有限状态自动机[7]

其中:X为有限状态集合;Σ为事件集;x0∈X为系统初始状态;δ为状态转移函数,δ:X ×Σ→2X;F⊆X为标记状态集;事件集Σ可分为可观察事件集Σo和不可观察事件集Σuo,即Σ=Σo∪Σuo.

定义1给定两个事件串t和u,如果u=stv,则称t为u的子串,记为tΞu;如果删除事件串u中零个或多个事件(可连续也可不连续)后得到事件串t,则称t为u的子序列,记为tΥu.给定一个事件串集K,定义集合S为将K中事件串作为子序列的事件串集合,即S={s∈L|(∃u∈K)(uΥs)};定义集合T为将K中的事件串作为子串的事件串集合,即T={s∈L|(∃u∈K)(uΞs)}.

它表示S中所有以K中元素结尾的事件串集;记集合ΨT(K)为T中所有以K中元素结尾的事件串集,即

3 安全可诊断的形式化

基于模式的安全可诊断的目的是将系统中引发故障的故障模式及时诊断出来,并要求在诊断期间不能执行被禁止操作.

定义2设Ω为离散事件系统G的被禁止事件串集,G的S型非法语言定义为

G的T型非法语言定义为

定义3如果离散事件系统G同时满足以下条件,则称G为基于S型模式的安全可诊断系统:

i)S型模式可诊断条件:

其中条件DS为P−1P(st)∩L ⊆S.

ii)S型模式安全性条件:

其中tc为满足i)中条件DS中t的最短事件串.

定义4如果离散事件系统G同时满足以下条件,则称G为基于T型模式的安全可诊断系统：

i)T型模式可诊断条件:

其中条件DT为P−1P(st)∩L ⊆T.

ii)T型模式安全性条件:

其中tc为满足i)中条件DT中t的最短事件串.

4 基于S型模式的安全故障诊断

先引入一种标记自动机及其并行器.

定义5设G为一个基于S型模式诊断的离散事件系统,s=σ1σ2σ3···σm为一个触发S型模式故障的子序列,则G的标记自动机构造为有限状态自动机HS(s)=(QS,Σ,δS,,FS),其中QS={0,1,2,···,‖s‖}为状态集,δS为转移函数δS:QS×Σ→QS,对于qS∈QS{‖s‖},σ∈Σ,若σ=σqS+1,则δS(qS,σ)=qS+1;若σ≠σqS+1,则δS(qS,σ)=qS;且δS(‖s‖,σ)=‖s‖.

定义6设G为一个基于S型模式诊断的离散事件系统,设所有触发S型模式故障的子序列为K={s1,s2,···,si},则G的并行器GlS构造为有限状态自动机,其中状态集为,初始状态为=(x0,0,···,0),转移函数δlS:QlS×Σ→QlS定义为δlS(qlS,σ)=(δ(x,σ),δS1(qS1,σ),···,δSi(qSi,σ)),这里qlS=(x,l1,l2,···,li)∈QlS,σ∈Σ.

再构造非法语言识别器以对非法语言进行识别.先引入一个标识符ΦS={S1,S2,B},其中:标识S1表示系统没有发生S型模式故障;标识S2表示系统发生了S型模式故障,但此后没有发生被禁止事件串;标识B表示系统发生了S型模式故障,并且其发生之后又执行被禁止操作.

定义7设G为基于S型模式诊断的离散事件系统,所有触发S型模式故障的子序列为K={s1,s2,···,si},则非法语言识别器GrS构造为有限状态自动机GrS={QrS,Σ,δrS,,FrS},其中:QrS⊆QlS×ΦS为状态集合;为初始状态;δrS:QrS×Σ→QrS为转移函数,对任意σ∈Σ,s∈Σ∗和s′∈K,δrS的转移规则如下:

定义8设G为基于S型模式诊断离散事件系统,其S型模式安全诊断器GvS构造为有限状态自动机GvS=,其中QvS为状态集合;=(x0,0,0,···,0,S1)为初始状态;δvS:QvS×Σo→QvS为转移函数,它满足

定义9设GvS是离散事件系统G的S型模式安全诊断器,qvS∈QvS.如果对任意qrS=(qlS,ΦS)∈qvS,都有F∈qlS,则称qvS为F-确定状态.如果存在qrS=(qlS,ΦS),=(,)∈qvS使得F∈qlS,F/∈,则称qvS为F-不确定状态.

下面给出S型模式安全可诊断的充分必要条件.

定理1给定基于S型模式诊断的离散事件系统G=(X,Σ,δ,x0,F),其S型模式安全诊断器为GvS. G为S型模式安全可诊断的充分必要条件是S型模式安全诊断器GvS同时满足以下条件:

1)不存在F-不确定状态qvS∈QvS,使得(qlS,ΦS)∈qvS,其中:F∈qlS,B∈ΦS.

证下面先用反证法证明定理1的充分性.

假设G满足定理1中的条件1)和2),但G不是S型模式安全可诊断的.

i)若G不满足S型模式可诊断性条件,则存在事件串u,v,使P(u)=P(v),u∈ΨS(K),v/∈ΨS(K).并且在GvS中,一定存在状态qvS∈QvS,其中qrS,∈qvS,且qrS=δrS(,P(u))=(qlS,ΦS),,F∈qlS,F/∈,那么qvS是F-不确定状态;并且B∈ΦS,B/∈,这与满足定理1中的条件1)的这一假设相矛盾.

ii)若G不满足安全性条件但满足诊断条件,不妨设u=u1u2σ满足诊断条件,其中:u1∈ΨS(K),u2∈ζfS,σ∈Σo,因为G不满足安全性条件,所以对任意tc,都有∩ζfS=∅,tc为u中满足诊断条件中DS的最短事件串.令tc=u2σ,即经过u1u2σ时故障刚好能够被诊断出来;在GvS中存在状态qvS,∈QvS,其中:qvS=并且qvS是F-不确定状态,是F-确定状态,又因为u2∈ζfS,所以在中存在qrS=(qlS,ΦS),B∈ΦS,即不满足定理1中的条件2),这与假设相矛盾.

再用反证法证明定理1的必要性.

假设系统G是S型模式安全可诊断的,但其安全诊断器GvS不满足定理1中的条件1)或2).

i)若G不满足条件1),则存在F-不确定状态qvS∈QvS,使得(qlS,ΦS)∈qvS,其中F∈qlS,B∈ΦS.由于qvS为F-不确定状态,则一定存在使qrS=(qlS,ΦS),F∈,由此可知,在G中存在事件串u,v使得P(u)=P(v),其中u∈ΨS(K),v/∈ΨS(K),即不满足S型模式可诊断条件.

ii)若G不满足条件2),即存在qvS,∈QvS,其中qvS和为分别F-不确定状态和F-确定状态,且存在e∈Σo,使 得,其中F∈,B∈.取s=ue,令,则存在u′,v使得u′v∈P−1(u),u′∈ΨS(K),v/∈ΨS(K),再令u=u1u2,u1/∈ΨS(K).因为G是S 型模式安全可诊断的,所以存在t∈L/u1,且t满足条件DS,此时满足条件DS的最短事件串为tc=u2e.又因为,其中B∈,即u2e∩ζf≠∅,即G不是S型模式安全可诊断的,这与假设相矛盾. 证毕.

注1设基于S型模式诊断的离散事件系统G,其系统状态数为‖X|=n1,事件数‖Σ‖=n2,在安全诊断器GvS中,其状态数与事件数最多分别为2n1和n2,则构造GvS的复杂度为O(2n1·n2).当判断定理1中的条件1)时,需要遍历安全诊断器GvS中的所有状态,所以复杂度为O(2n1),当判断定理1中的条件2)时,需要遍历所有的状态及事件,即复杂度为O(2n1×n2).根据定理1,验证G的S型模式安全可诊断性的复杂度为O(n2·2n1).

例1考虑图1中系统G1,其中:Σo={b,d,σs},Ω={σs},故障模式集K1={d,c}.

图1 离散事件系统G1Fig.1 Discrete-event system G1

分别构造状态标记器和并行器如图2和图3所示.

图2 标记器HS(s)Fig.2 The label automaton HS(s)

分别构造S型模式非法语言识别器和安全诊断器如图4和图5所示.

由图5 可知,状态{(x3,1,S1),(x6,F,S2)}为F-不确定状态,并且在(x3,1,S1)与(x6,F,S2)中都没有标识符B;且由F-不确定状态{(x3,1,S1),(x6,F,S2)}经过可观事件d 到达F-确定状态{(x8,F,S2),(x7,F,S2)},即GvS满足定理1条件,所以系统G1是S型模式安全可诊断的.

图3 并行器GlSFig.3 Parallel automaton GlS

图4 S 型模式非法语言识别器GrSFig.4 S-type recognizer of illegal language GrS

图5 S 型安全诊断器GvSFig.5 S-type safe diagnoser GvS

5 基于T型模式的安全故障诊断

定义10设G为一个基于T型模式诊断的离散事件系统,s=σ1σ2σ3···σm为触发T型模式故障的子串,则G的标记自动机构造为有限状态自动机

其中:QT={0,1,···,‖s‖}为状态集合,δT为转移函 数,δT:QT×Σ→QT,对 于qT∈QT{‖s‖},σ∈Σ,如果σ=σqT+1,则δT(qT,σ)=qT+1;如果σ≠σqT+1,则δT(qT,σ)=0;且δT(‖s‖,σ)=‖s‖.

定义11设G为一个基于T型模式诊断的离散事件系统,所有触发T 型模式故障子串为K={s1,s2,···,si},G 的并行自动机GlT构造为有限状态自动机

下面构造非法语言识别器GrT以对非法操作进行识别.引入禁止标识符ΦT={S1,S2,B},其中标识S1表示系统没有发生T型模式故障;标识S2表示系统发生了T型模式故障,但其发生之后没有发生被禁止事件串;标识B表示系统即发生了T型模式故障又执行了被禁止事件串.

定义12设G=(X,Σ,δ,x0,F)为一个基于T型模式诊断的离散事件系统,所有触发T型模式故障的子串为K={s1,s2,···,si},G的T型模式非法语言识别器GrT构造为有限状态自动机

定义13设基于T型模式诊断的离散事件系统G=(X,Σ,δ,x0,F),其T 型模式安全诊断器GvT构造为有限状态自动机GvT=(QvT,Σo,δvT,,FvT),其中:QvT⊆2QrT为状态集;δvT为转移函数,对于qvT∈QvT,σ∈Σo,其转移规则如下:

定义14设GvT为T型模式安全诊断器,如果对任意qrT=(qlT,ΦT)∈qvT,都有F∈qlT,则称qvT为F-确定状态.如果存在qrT=(qlT,ΦT),=(,)∈qvT使得F∈qlT,F/∈,则称qvT为F-不确定状态.

下面给出T型模式安全可诊断的充分必要条件.

定理2设基于T型模式诊断的离散事件系统G=(X,Σ,δ,x0,F),其T型模式安全诊断器为GvT=(QvT,Σo,δvT,,FvT),则G为T型模式安全模式诊断的充分必要条件是GvT同时满足以下条件:

1)不存在F-不确定状态qvT,使得(qlT,ΦT)∈qvT,其中:F∈qlT,B∈ΦT.

2)不存在状态qvT,∈QvT,其中qvT为F-不确定状态,为F-确定状态,并且存在e∈Σo和(,)∈,使得=δvT(qvT,e),其中:F∈,B∈.

证利用反证法证明定理2的充分性.

假设系统G满足定理2中的条件1)和2),但是G不是T型模式安全模式诊断.

i)若G不满足可诊断性条件,则存在事件串u,v且P(u)=P(v),u∈ΨT(K),v/∈ΨT(K).在T 型 模式安全诊断器中GvT中存在状态qvT∈QvT,其中qrT,∈qvT,且qrT=(qlT,ΦT),=(,),F∈qlT,F/∈,则qvT为F-不确定状态;由于B∈ΦT,B/∈,这与假设相矛盾.

ii)若G不满足安全性条件但满足诊断条件,设事件串u=u1u2σ满足诊断条件,其中:u1∈ΨT(K),u2∈ζfT,σ∈Σo.因G不满足安全性条件,所以对任意,有∩ζfT=,为u中满足诊断条件中DT的最短事件串,令tc=u2σ,即经过事件串u1u2σ时故障刚好能够被诊断出来,在GvT中存在qvT,∈QvT,使得=δvT(qvT,σ),且qvT为F-不确定状态,为F-确定状态,又因为u2∈ζfT,所以在中存在qrT=(qlT,ΦT),且B∈ΦT,即不满足定理2 中的条件2),与假设相矛盾.

再利用反证法证明定理2的必要性.

i)假设G是T型模式安全可诊断的系统,但是GvT不满足定理2中的条件1),则在GvT中存在一个F-不确定状态qvT,且(qlT,ΦT),(,Φ′)∈qvT,其中F∈qlT,F/∈,B∈ΦT.设事件串s∈,且qvT=δvT(,s),则在并行器GlT中必然存在事件串u,v∈P−1(s),使得qlT=;又因为F∈qlT,所以设u=u1u2,且u1∈ΨT(K).存在t∈L/u1,满足可诊断条件,令t′=u1t(t=u2tc),又因为B∈ΦT,所以u2∈ζfT,u2tc∩ζfT∅,这与假设相矛盾.

ii)假设G是T型模式安全可诊断的系统,但是GvT不满足定理2中的条件2),即存在qvT,∈QvT,其中qvT是F-不确定状态;是F-确定状态,并存在e∈Σo,使;存在∈,其中F∈,B∈;设事件串s∈,且qvT,则在并行器GlT中存在事件串u,v∈P−1(s),使得qlT1=δlT,qlT2=δlT(,v),F∈qlT1,F/∈qlT2;再令u=u1u2,并且使u1∈ΨT(K),G是T型模式安全可诊断的,存在t∈L/u1,满足诊断条件DT,因为是F-确定状态,所以tc=u2e,即诊断器经过事件串se时故障恰好能够被诊断出来,则存在,因为B∈Φ′,所以u2e∈ζfT,即∩ζfT∅,这同样与假设相矛盾. 证毕.

注2与S型模式安全可诊断复杂性类似,构造GvT的复杂度为O(2n1×n2),判断定理2中的条件1)2)的复杂度分别为O(2n1)和O(2n1·n2).因此,根据定理2,验证G的T型模式安全可诊断性的复杂度为O(n2·2n1),其中n1,n2为G的状态数和事件数.

图6 离散事件系统G2Fig.6 Discrete-event system G2

例1考虑图6中系统G2,其中:Σo={a,d,σs},Ω={σs},故障模式集K2={ab}.

构造T型模式标记器和安全诊断器如图7和图8所示.

图7 标记器HT(s)Fig.7 The label automaton HT(s)

图8 T型模式安全诊断器GvTFig.8 T-type safe diagnoser GvT

由图8中可知,GvT中仅有状态{(x7,F,S1),(x8,0,S1)}为F-不确定状态,且在(x7,F,S1)与(x8,0,S1)中没有标识符B,即GvT满足定理2中条件1);而F-确定状态{(x9,F,B)}由F-不确定状态{(x7,F,S1),(x8,0,S1)}经过可观事件σs到达,并且在(x9,F,B)中有标识符B,即GvT不满足定理2中条件2),所以G2不是T型模式安全可诊断的.

6 总结

本文讨论了离散事件系统基于模式故障诊断的安全性问题,提出了一种对故障模式进行安全诊断的方法,它不仅能将S型模式和T型模式的故障在其发生之后诊断出来,又能确保系统在模式诊断期间不执行任何被禁止的不安全操作.该方法通过构造非法语言识别器和安全诊断器,得到了一个关于离散事件系统可安全模式诊断的充分必要条件.