离散事件系统故障的极小观测序列*
2016-06-01欧阳丹彤李江娜耿雪娜
欧阳丹彤，李江娜，耿雪娜
(1.吉林大学 计算机科学与技术学院，吉林 长春 130012；2. 吉林大学 符号计算与知识工程教育部重点实验室，吉林 长春 130012)
离散事件系统故障的极小观测序列*
欧阳丹彤1,2†，李江娜1,2，耿雪娜1,2
(1.吉林大学 计算机科学与技术学院，吉林 长春130012；2. 吉林大学 符号计算与知识工程教育部重点实验室，吉林 长春130012)
摘要：为了提高可诊断离散事件系统故障的在线诊断效率，本文从判定故障发生的可观测事件的角度，提出了故障极小观测序列方法.文中选取有限状态自动机对离散事件系统进行建模.首先，在离线状态下，建立系统的故障模型，以排除对于判定系统故障无关的路径.然后，根据故障模型进一步建立判定系统故障的极小观测序列模型.当离散事件系统在线诊断时，仅需将逐步增加的在线观测事件序列与故障的极小观测序列模型进行比对.若能找到满足该模型的任何一条路径，则说明路径终止状态上故障标签对应的系统故障发生；否则，说明系统无故障发生.文中对可诊断离散事件系统进行实验对比，通过故障的极小观测序列模型能尽快判定有无故障发生，以及发生了哪些故障.该模型能有效地缩小系统在线诊断的时间，提高系统在线诊断的效率.
关键词：离散事件系统；故障模型；极小观测序列模型；故障诊断
近些年来，基于模型诊断[1-3]方法成为人工智能领域比较热门的研究课题.基于模型诊断方法具有设备独立性，易于更新和维护.因而，不少领域使用基于模型诊断方法对离散事件系统进行诊断[4-6]研究，比如大型通信网络故障诊断、配电站故障诊断[7]、航天器故障诊断、汽车故障诊断、软件测试等.基于模型诊断中诊断相关的极小化研究增强了诊断的精细程度.诊断相关的极小化研究包括：极小诊断、极小故障事件集、判定可诊断性的极小事件集等.极小诊断是在部件级别上对故障部件的候选冲突集进行求碰集，从而得到故障部件的诊断结果.使用不同的方法求碰集，得到系统极小诊断的效率有所不同.例如，通过减少一致性检测的数量，避免对极小化冲突集的计算，求解系统的极小诊断[8].极小故障事件集则考虑故障事件的先后顺序对系统的影响，将故障事件构成的序列进行极小化，从而得到系统故障事件的极小序列诊断[9].而可诊断性的极小事件集则是通过减少可观测事件的种类，使系统仍保持可诊断性，求解保证系统可诊断性的极小事件集[10].以上极小化相关研究都未曾从在线诊断角度考虑如何尽快地确定发生的故障.为了提高系统在线诊断的效率，使在线诊断时尽快地判定出故障的发生，本文对判定故障发生的可观测事件序列进行研究并建立相应的模型，使得在系统故障发生后尽快确定该故障的发生.假定待测的离散事件系统是完备且可诊断的.
本文给出了判定系统故障发生的极小观测序列模型Gmos以及建立故障极小观测序列模型的算法(约束转换法).对于给定的离散事件系统，首先建立该系统模型相对应的故障模型Gf，然后在故障模型基础上求得系统故障的极小观测序列模型Gmos.通过故障的极小观测序列模型可以得到某个或某类故障发生的极小观测序列集.这样，系统在线实时诊断时，将传感器逐步接收到的观测与系统故障的极小观测序列模型进行比对，若满足该模型中的某个观测序列，则说明系统发生了该序列终止状态标签相对应的故障；否则，系统判定没有故障发生.根据系统故障的极小观测序列模型，能在故障发生后尽快地判定出系统发生了哪些故障.
本文结构如下：第1部分给出了相关概念和定义；第2部分给出了故障极小观测序列模型的构建算法(约束转换法)；第3部分给出了相关证明；第4部分给出了实验及分析；第5部分对本文工作进行总结.
1预备知识
本部分给出了文中相关的概念及模型的定义.
定义1(系统模型)系统模型是一个有限自动机Gs= (S,E,T,S0,Sf).其中S为状态集合；S0为初始状态；Sf为终止状态集合；T为状态转换函数集合，T→S×E×S.E为事件集合，包括可观测事件集Eo和不可观测事件集Euo，Euo又分为故障事件集和非故障事件集.
定义2(观测可达)状态si∈S经事件e∈Eo可达状态sj∈S(其中si和sj间事件除e外还可存在非连续的不可观测事件)则称si在e下可达，记作si[e].状态sj称为观测可达状态，记作R(si,e).
图2中表示观测可达的几种情况，其中a,b∈Eo，v,u∈Euo，则有R(S0,a) = {S1}，R(S1,b) = {S2,S3} ,R(S3,c) = {S5}.
为了便于对系统模型中故障进行筛选，给出了故障模型的定义.
定义3(故障模型)故障模型为一个有限自动机Gf= (S’,E’,T’,S0,Sf’)，其中S’⊆S，E’⊆E，T’⊆T，Sf’⊆Sf.
为提出建立故障模型的算法，给出以下定义.
图1 单故障系统模型Gs
图2 观测可达
由于传感器无法观测到不可观测事件，现定义观测.
定义6 (观测)事件序列O=o1o2…on(其中o1,…,on∈E)的观测表示为obs(O)，定义如下：
obs(oi)={φ}，当oi∈Euo；
obs(oj)={oj}，当oj∈Eo；
obs(O=t1o)=obs(t1)obs(o) ，当t1∈E*，o∈E.
其中E*={
例如O=abucfcd，其中u,f∈Euo，a,b,c,d∈Eo，得obs(O)=abccd.
本文目的是求解系统故障的极小观测序列模型，因此定义了故障的极小观测序列以及故障的极小观测序列模型.
定义7(故障的极小观测序列)存在可观测事件序列o1o2…on和o1o2…onon+1…on+k(其中o1，…,on+k∈Eo且k>0) 均可判定某故障发生，而序列o1o2…on-1无法确定该故障发生，则称序列o1o2…on为该故障的极小观测序列.所有故障的极小观测序列构成的模型称为系统故障的极小观测序列模型.
图1当接收到观测a，无法判定f发生，ab能判断f发生，abc也可以，可见ab为判定f发生的一个极小观测序列.
定义8 (故障的极小观测序列模型)极小观测序列模型为一个有限自动机：Gmos= (X,Eo’,Tmos,X0,Xf).其中Eo’⊆E’为可观测事件集.X0=(S0,{N})为初始状态.Tmos为状态转换函数集合.X为状态集合，X={xi|xi= {(s1,l1) , …, (sn,ln)} ,s1, …,sn∈S’,l1, … ,ln∈{N,F*}，F*={
根据模型中状态标签的不同，提出了定义模糊状态和标签可达.
定义9 (模糊状态)状态xi∈X中既含标签F’∈F*又含标签N，则xi为模糊状态.
定义10 (标签可达) 模糊状态xi∈X,存在可观测事件e∈Eo’,若仅使得带标签N的状态sij其中 (sij,N)∈i)可达，称xi在e下N标签可达；若仅使带标签F∈F*的状态可达，称xi在e下F标签可达；若同时存在，称xi在e下NF标签可达.
Tmos(xi,e)定义之前，先定义局部转换函数Tmos((sij,l(sij)),e) , 来表示状态间通过事件连接的关系(其中(sij,l(sij))∈xi).
定义11 (局部转换函数)局部转换函数Tmos((sij,l(sij)),e) ,其中l(sij)∈{N,F*}，当fk∉t(sij,R(sij,e))时，则Tmos((sij,l(sij)),e) = (R(sij,e) ,l(sij)).否则，当l(sij) =N时，Tmos((sij,l(sij)),e) = {R(sij,e) ,Fk)}；l(sij)≠N时，Tmos((sij,l(sij)),e) = {R(sij,e) ,l(sij)∪Fk}.
根据局部转换函数进一步定义极小观测序列模型中状态间的转换关系，称为转换函数Tmos.
定义12 (转换函数Tmos)：极小观测序列模型中转换函数Tmos(xi,e).根据状态标签不同进行以下分类说明.
(R1)仅含N标签的状态xi= {(s1,N) ,…, (sn,N)}，其中s1,…,sn∈S’，存在可观测事件e∈Eo’，那么Tmos(xi,e) = {Tmos((sj,l(sj)),e) |∀sj[e] ,sj∀{s1,…,sn}}.
(R2)模糊状态xi= {(s1,N) ,…, (sk,N) , (sk+1,Fk+1) ,…, (sm,Fm)}，Fk+1,…,Fm∈F*，对于可观测事件e∈Eo’存在sj[e] …st[e] ，且满足j∈[1,k],t∈(k,m]或者满足j,t∈(k,m]，那么Tmos(xi,e) = {Tmos((sj,l(sj)),e) ,…,Tmos((st,l(st)),e)}.
(R3)仅含F标签的状态xi= {(s1,F1) ,…, (sn,Fn)}，F1,…,Fn∈F*,n≥2,存在事件e∈Eo’，令SF’ = {si|∀si[e] ,si∈{s1,…,sn}},那么Tmos(xi,e) = {Tmos((sj,l(sj)),e) |∀sj∈SF’}.
根据以上对3种状态下转换函数的定义，可知终止状态可由仅含N标签状态、模糊状态以及仅含F标签状态经转换函数Tmos得到.
2故障的极小观测序列模型
2.1故障模型
建立系统故障的极小观测序列模型需要给定系统的故障模型，本节首先给出了算法1(筛选法)用于构建系统的故障模型.
算法1构建系统模型Gras的故障模型Graf
Function: FmBuild(Gras);
Input:Gras;//系统模型对应的图
Output:Graf;//故障模型对应的图
Begin
1: Initialization:
Graf←S0;
2: for ∀t∈tGs∧fi∈tdo
3:tf←t
4:Graf←tf;
5: end for
6: for eachtfi∈tf,find thetpfido
7: ift’∈tGs∧t’∉tf∧t’ =t1’t2’∧
(obs(t1’) =obs(tpfi))then
8:Graf←t’;
9: end if
10: end for
End
算法1中2-5行将系统模型图Gras中故障路径集合tf加入到图Graf.7-9行每条故障路径tfi∈tf,找到其预故障路径tpf,取得与观测obs(tpfi)有相同部分观测的路径t’，将t’加入到图Graf中.
2.2极小观测序列模型构建算法
根据系统的故障模型建立判定故障发生的极小观测序列模型.本节给出了算法2(约束转换法)用于构建系统故障模型的极小观测序列模型.
算法2构建系统故障模型Graf的极小观测序列模型Gramos
Function: MosmBuild(Graf);
Input:Graf; //故障模型对应的图
Output:Gramos; //极小观测序列模型对应的图
Begin
1: Initialization:
X0←(S0,{N});
Gramos←X0;
X←X0;
2:forXi∈X∧isNotEnd(Xi)∧isTerminal(Xi) do
3: ifXi= {(s1,N), ..., (sn,N)}then
4:for ∀e∈Eo∧si[e]do
5:Xi+1←trans((si,l(si)),e);
6:X←Xi+1;
8: end for
9: end if
10: ifXi= {(s1,N), …, (sk,N), (sk+1,Fk+1),…,
(sn,Fn)}then
11: for ∀e∈Eo∧sj[e],…,st[e]do
12:ifj∈[1,k]∧t∈(k,n]then
13:Xi+1←trans((si,l(si)),e);
14:X←Xi+1;
16:end if
17:ifj∈(k,n]then
18:Xi+1←trans((si,l(si)),e);
19:X←Xi+1;
21:end if
22: end for
23:end if
24: ifXi= {(s1,F1), ..., (sn,Fn)}then
25:for ∀e∈Eo∧si[e]do
26:Xi+1←trans((si,l(si)),e);
27:X←Xi+1;
29:end for
30:end if
31:end for
End
算法2中trans((si,l(si)),e)表示状态的局部转换函数.
Function:trans((si,l(si)),e);
Inputs:si;//状态
l(si) ;//状态的标签
e; //可观测事件
Begin
1: forr∈R(si,e)do
2:iffj∉t(si,r)then
3:x←(r,l(si));
4:else
5:ifl(si) =Nthen
6:x←(r,Fj);
7:else
8:x←(r,l(si)∪Fj);
9:end if
10:end if
11:end for
12:returnx;
End
函数trans((si,l(si)),e)的第1行R(si,e)表示状态si通过事件e所有可达状态构成的集合;2-3行指故障不包含在路径t(si,r)时，转换后标签不变；4-8行指故障包含在路径时，转换后状态标签的情况：5-6行指原有状态标签为N时，转换后状态标签为故障标签；7-8行指原有状态标签为故障标签时，转换后状态标签为两个标签的并集.
3证明
算法2求得的极小观测序列模型包含系统中所有故障的所有极小观测序列.
证(正确性)极小观测序列模型中终止状态出现在三种状态转换后：模糊状态、仅含有N标签的状态以及仅含有F标签的状态.由于系统是可诊断的，则故障标签一定可以分离.对于模糊状态(或者仅含有F标签的状态)经转换到终止状态的过程为故障分离的过程，而且首次进行分离，所以满足极小性；而对于仅含有N标签的状态，经转换到终止状态的过程为正常状态首次到达的含有F标签的状态，所以满足极小性.可见，极小观测序列模型中的序列满足极小性.
(完备性)极小观测序列模型是根据故障模型得到的，需要证明故障模型是完备的.故障模型由系统模型中的故障路径以及与预故障路径相同部分观测的路径组成.故障的极小观测序列一定存在于故障路径中，故障发生后，影响故障发生判定的路径只有与预故障路径相同部分观测的路径，所以故障模型是完备的，则极小观测序列模型也是完备的.
(复杂性分析)极小观测序列模型的在线诊断时间取决于实时接收的观测与离线建立的极小序列模型的比较时间，当观测序列长度为n时，比较时间复杂度为O(n)，故在线诊断的时间复杂度为O(n).
4实验及实例分析
4.1实验
由于本文的研究建立在完备且可诊断的离散事件系统基础上，且此类研究没有统一的benchmark数据测试集，故选取相关论文[9]中满足本文假设的部分系统模型以及满足条件的系统模型进行以下两种对比实验.情形1：使用系统故障的极小观测序列模型，记作Mos；情形2：不使用故障的极小观测序列模型，记作Ori.对于相同长度的故障极小观测序列且相同节点个数的系统(单故障系统)进行实验，分别得到Mos和Ori的在线诊断的时间如表1所示：
表1 诊断的时间对比
实验数据表明，在相同条件的系统中，Mos诊断时间均比Ori短，为了更形象地说明两者的时间差距，诊断时间差图3如下.
系统节点个数
由图3可得，对于单故障系统，Mos的故障诊断时间均比Ori的故障诊断时间短，即Mos下，系统有较高的诊断效率.尤其对于节点个数多且故障极小观测序列较长的系统模型，Mos比Ori在线诊断时间有更好的优势.
实验表明：离线建立系统的极小观测序列模型用于在线故障诊断，能有效地提高系统在线故障诊断的效率.既能够尽快地发现故障发生，也能尽快地排除故障的发生.
4.2实例分析
图4为多故障系统模型Gs，根据算法2得到该系统故障的极小观测序列模型Gmos，如图5所示.可得故障f1的极小观测序列为abc，acb，故障f2的极小观测序列为abb.
图4 多故障系统Gs
图5 极小观测序列模型Gmos
系统在初始状态0下，当接收到观测a时，在Gmos中存在可达状态，当再接收到观测c，也有可达状态，若继续接收到观测b到达Gmos中的带标签F1的终止节点，此时可以判定故障f1发生.同理，当接收到观测序列abc，可判定故障f1发生；接收到观测abb，可判定故障f2发生.
5结论
本文提出了系统故障的极小观测序列模型，用于提高系统在线故障诊断的效率.文中给出了相关概念定义以及构建系统故障的极小观测序列模型的算法，而且通过对比实验证明了将故障的极小观测序列模型用于系统在线故障诊断，可以有效地减少系统故障诊断的时间，从而使系统尽快地判定有无故障发生.
参考文献
[1]PENCOLE Y. Diagnosability analysis of distributed discrete event systems[C] //Proceedings of the 16th European Conference on Artificial Intelligence (ECAI-04). Valencia, Spain, 2004:43-47.
[2]RIBOT P, PENCOLE Y, COMBACAU M. Design requirements for the diagnosability of distributed discrete event systems[C] //Proceedings of the 19thInternational Workshop on Principles of Diagnosis (DX-08). Blue Mountains:NSW, 2008: 98-106.
[3]张立明,赵剑,赵相福,等.基于因果关系的模型诊断[J].吉林大学学报:工学版,2009,39(4):1052-1056.
ZHANG Li-ming, ZHAO Jian, ZHAO Xiang-fu,etal. New method of using causal relations for model-based fault diagnosis[J]. Journal of Jilin University: Engineering and Technology Edition, 2009, 39(4):1052- 1056.(In Chinese)
[4]CASSANDRAS G C, LAFORTUNE S. Introduction of discrete event systems [M].2nd ed. Springer Science+ Business Media, 2008.
[5]SAMPATH M, SENGUPTA R, LAFORTUNE S,etal. Daignosability of discrete event systems[J]. IEEE Transactions on Automatic Control, 1995, 40(9):1555- 1575.
[6]SAMPATH M, SENGUPTA R, LAFORTUNE S,etal. Failure diagnosis using discrete event systems[J]. IEEE Transactions on Control Systems Technology, 1996, 4(2): 105-124.
[7]李帅虎,曹一家,刘光晔,等.UHV对接入区域高压配电网安全稳定的影响[J].湖南大学学报:自然科学版,2014, 41(10)：71-76.
LI Shuai-hu, CAO Yi-jia, LIU Guang-ye,etal. Influence of UHV on the security and stability of the high voltage distribution network of integration area[J]. Journal of Hunan University: Natural Sciences Edition, 2014, 41(10)：71-76. (In Chinese)
[8]SHCHEKOTYKHIN K, FRIEDRICH G, RODLER P,etal. A direct approach to sequential diagnosis of high cardinality faults in knowledge-bases[C] //Proceedings of the 25thInternational Workshop on Principles of Diagnosis (DX-14).Graz:Austria, 2014.
[9]ZHAO Xiang-fu, LAMPERTI G, OU-YANG Dan-tong. Minimal sequential diagnosis of discrete-event systems[C] //Proceedings of Diagnosis(DX-13).Jerusalem: Palestine, 2013:154-159.
[10]BASILIO J C, LINA S T S, LAFORTUNE S,etal. Computation of minimal event bases that ensure diagnosability[J]. Discrete Event Dynamic Synst, 2012:249-292.
Minimal Observation Sequences of Faults in Discrete Event System
OUYANG Dan-tong1,2†，LI Jiang-na1,2，GENG Xue-na1,2
(1.College of Computer Science and Technology,Jinlin Univ, Changchun,Jinlin130012,China; 2.Symbol Computation and Knowledge Engineering of Ministry of Education, Jinlin Univ, Changchun,Jinlin130012,China)
Abstract:In order to improve the efficiency of online diagnose of faults in discrete event system, from the viewpoint of the observable events judging occurrence of faults, this paper proposed a method called minimal observation sequences of faults. The finite state automaton was selected to model the discrete event system. First, a fault model of system was established in the offline, which was used to exclude the path independent of the system failure. Then, a minimal observation sequence model of faults was established according to the fault model. When the discrete event system is diagnosed online, it is necessary to compare the observations received by sensors with the model of minimal observation sequences. If any path in the model is found to satisfy the online observations, the fault in the termination state of the path will be described. Otherwise, no fault occurs. By comparing with the experiment results, the model of minimal observation sequences of faults can be used to determine the occurrence of faults as soon as possible. That is to say, the model for the system can find the faults timely and save the cost of online diagnosis.
Key words:discrete event system; faults model; minimal observation sequences model; fault diagnosis
中图分类号：TP301
文献标识码：A
作者简介：欧阳丹彤(1968-)，女，吉林长春人，吉林大学教授，博士†通讯联系人，E-mail:ouyangdantong@163.com
基金项目：国家自然科学基金资助项目(61133011, 61272208,61402196,61003101, 61170092)，National Natural Science Foundation of China(61133011，61272208，61402196，61003101，61170092)；吉林省科技发展计划项目基金(20140520067JH)
收稿日期：2015-03-16
文章编号：1674-2974(2016)04-0147-06
