基于状态估计的分布式离散事件系统可诊断性研究

戴 维，刘富春，赵 锐，邓秀勤，崔洪刚,3

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

离散事件系统(discrete event systems, DESs)是指一类状态为离散情形且状态演化由事件驱动的动态系统。离散事件系统在国防军事、交通控制、计算机集成制造系统、电子通讯网络、物联网技术和机器人技术等领域被广泛应用。近年来，关于离散事件系统故障诊断的研究吸引了众多学者的注意，涌现出了大量的研究成果，如文献[1-4]。离散事件系统的故障诊断主要包括2种情形：基于状态的诊断和基于事件的诊断。例如，Zad等[5]提出了一种基于状态的故障诊断方法。Sampath等[6]则提出了一种基于事件的故障诊断方法，并且给出了基于诊断器的系统可诊断的验证算法。Yoo等[7]提出了一种新的验证器算法，将基于诊断器的故障诊断方法的复杂度降至多项式。文献[8]将基于事件的故障诊断方法推广到模糊离散事件系统。Thorsley等[9]研究了随机离散事件系统的故障诊断问题，并提出了2种故障诊断概念：A-可诊断以及AA可诊断。Chen等[10]则提出了一种具有多项式复杂度的随机离散事件系统可诊断算法。叶彬彬等[11]将随机离散事件系统的故障诊断推广至故障预测。文献[12]通过用Petri网构建诊断器的方法，实现了较低复杂度下的故障诊断。Reshmila等[13]将离散事件系统故障诊断方法应用于电网系统的故障诊断。Chen等[14]则对蓄电组系统故障进行了深入研究。

分布式离散事件系统通过多个站点共同监督的方式，减少单个站点的信息获取，提高了离散事件系统整体的诊断效率。Qiu等[15]将Sampath提出的基于事件的方法由集中式推广至分布式，提出了经典分布式离散事件系统的故障诊断。在经典分布式离散事件系统的基础之上，Xu等[16]提出具有通信机制的分布式状态估计算法,首次将通信机制引入到分布式系统中去。经典分布式系统诊断方法不具有通信机制，这使得系统各站点之间无法接受和传递其他站点的信息，一旦发生站点丢失或站点无法正常工作的情况，就会影响诊断结果，降低诊断效率。考虑到经典分布式离散事件系统诊断方法存在的部分问题，文献[17-18]中介绍的具有通信机制的分布式离散事件系统的故障诊断方法可以解决经典分布式离散事件系统没解决的部分问题：分布式离散事件系统中的各个站点可以进行通信，降低了全局系统与各站点之间信息的耦合；允许较小通信延迟的存在，降低各站点之间信息的耦合。

在文献[15]的基础之上，Keroglou等[19]将通信机制引入经典分布式离散事件系统，提出了一种基于交并集优化的诊断算法，利用生成状态评估图进行故障信息的分类与提炼，最后得出故障事件的相关信息。因此，本文提出的算法不需要各站点间实时同步，也不要求通信机制具有较小的时间延迟，只需通信机制在诊断系统工作的时间段内能够工作就能进行事件信息的交互。与文献[15]相比，本文系统中各站点之间可以相互进行通信，并且各站点均存储有分布式系统当前所观察到的事件信息。

1 离散事件系统

离散事件系统 G通过有限不确定状态自动机来表示，可表示为一个四元组[16]

若事件σ ∈Σ可被站点i观察到，则σ ∈Σi，否则就为ϵ， ϵ表示事件 σ无法被站点i观察到，其中 Σi是站点i的可观事件的集合[19]。

2 分布式离散事件系统的状态评估

各站点在观察到系统发生事件后，通过通信机制接收其他站点传来的事件信息以及本站点观察所得的事件信息进行状态评估操作，同时更新本站点的状态评估图。为方便描述和分析，本文假设系统故障都是永久性故障且不可恢复。若这些站点的状态评估图中的状态集合存在故障状态，就需要对状态评估图中的状态集合进行故障的分析。本文假设各站点在信息传输过程中无信息丢失，通信时延ω为有限时延，且观察得到的事件序列具有保序性。站点i在观察到系统发生事件后，更新本站点的状态评估图 Ei。

定义1给定站点i的状态评估图 Ei， Ei为 G的子自动机，本文为区别 G中路径π，定义 Ei中的路径为℘i，且满足∀i ∈I,L(Ei)⊆L(G)。

定义 2给定系统G 中 任意一条路径π=x0σ0x1σ1···σnxn∈Π(G)，其轨迹是指[16]

其中，σ0···σn表示从状态 x0到状态 xn所需要经过的事件串。

定义3给定站点i当前状态评估图 Ei，其中任意一条路径为℘i=xkσk···σqxq，定义状态评估图 Ei的状态集合为X(℘i)=xk···xq。

定义4给定站点i的标签函数 lbli，I={1,···,m}，其作用是为路径 ℘i中的状态集贴标签

其中，X(℘i)表示路径 ℘i中的状态集。

定义5将站点i的状态评估图 Ei中当前到达的状态集合定义为

其中， xe为状态评估图 Ei中被标签函数 lbli贴上标签有待诊断的状态。

3 分布式离散事件系统的可诊断性

定义6给定一个诊断函数D:2X→{N,F,A},它满足如下条件

定义7(可诊断定义)若分布式离散事件系统G可 诊断，则满足以下条件

其中， Mi为站点i对tr(π)的可观映射，tr(π)为系统 G中路径 π的轨迹， N 和 F为诊断标签。直观上，系统G 可诊断，诊断系统中的各站点对系统G 中任意路径π ∈Π(G)进行观察之后，更新其状态评估图Ei。再接收来自其他站点的事件信息，其状态集合为。对于中的任意元素 xe，经诊断函数诊断之后，有且仅有xe∈N 或xe∈F。

定理1设G=(X,Σ,α,Xo)是一个离散事件系统，站点索引集合为I={1,···,m}， ℘i是站点i状态评估图 Ei中的路径，为站点i中状态评估图 Ei的状态集合，则系统G 可诊断的充分必要条件是

根据定理1，下面提出用于验证基于状态估计的分布式离散事件系统可诊断性的算法。

步骤1初始化站点i的状态评估图Ei(i ∈I)。

步骤1.1初始化路径。

站点i从系统 G的初始状态集合 Xo开始，寻找包含站点i不可观事件的路径 π，并从这些路径 π开始对站点i 的 Ei进行初始化。

步骤1.2初始化标签。

站点i在上一步得到的 Ei中，利用标签函数 lbli对本站点 Ei中路径 ℘i的末状态 x进行标记。

步骤2站点i观察到可观事件，更新其 Ei。

步骤2.1站点i 观察到事件α，α∈Σi，更新 Ei中的路径 ℘i。

它表示系统 G的事件α∈Σi能被站点i观察到，即Mi(α)=α。由步骤1可知，路径π 属于旧路径 ℘oild，因此路径 π的末状态应标记有i标签，即i ∈lbli(last(π))。其中， π′为 Ei中新生成的路径，包含在更新后的路径 ℘i中。

这一时期属于印尼建国初期，政府面临着严峻的政治经济形势，将发展的重点放在政治与经济上。苏加诺政府提倡“积极自主”外交，苏加诺总统先后访问了很多国家，其中与苏联和中国的关系较为密切。由于国内动乱频发，苏加诺总统认为当时的“会议民主”不适合印尼的国家统一，因此于1956年提出“民主、宗教、共产”的民族主义(NASAKOM)组阁方案。根据该方案，内阁由军队、宗教组织和印尼共产党代表组成。可见，苏加诺总统的政治倾向为社会主义，而中国是社会主义国家，所以华文教育在此时期有良好发展的政治环境。

步骤2.2更新标签。

它表示在上一步操作之后，从站点i 的 Ei中得到更新后的路径 ℘i，在其中找到包含事件 α的子路径sub(℘i)，并将原来子路径sub(℘i)中首状态的i标签，从路径π 的首状态转移到其末状态上去。

步骤3站点i接收到站点 j对事件 β的观察信息，β∈Σj。

步骤3.1更新路径。

步骤3.2更新标签。

由于站点i接收到站点 j对事件 β的观察信息，站点i需要对 Ei进行更新。因此站点i需要在 Ei中，找出上一步更新得到的路径 ℘i，并在 ℘i中找到包含事件η的子路径sub(℘i)，同时将路径 ℘i的子路径中，状态的 j标签从路径π 的首状态向末状态传递。

步骤4对站点i的Ei中冗余历史记录进行修剪操作。

站点i 和 j之间进行通信后，站点i 的 Ei中路径℘i的i标签和 j标签都传递到更新后的路径 ℘i上。这里的事件 o表示任意站点可观的事件或事件串(事件α 或事件β,也可能是两者组成的事件串)。因此，路径π′的状态没有标签，为无用历史路径，站点i需要截去不包含任何标签的路径 π′，以节约诊断系统的存储空间。

步骤5对分布式离散事件故障诊断系统中任意2个站点最后生成的状态评估图进行比较，若(∀i,j ∈I)Ei=Ej，则进入到下一步的诊断结果输出环节，否则重复以上步骤。

步骤6利用诊断函数对系统G当前状态集合进行故障诊断，同时分析系统G的可诊断性。

图 1 算法流程Figure 1 Algorithm flowchart

文献[16]仅提出一种分布式状态估计算法，没有将这种算法运用到故障诊断中去；文献[19]提出利用基于状态估计的分布式离散事件系统对系统故障进行诊断，但由于文中对分布式集合交互精炼算法(DiSIR)的构造过程过于复杂，难以将其应用到实际系统中。本文在文献 [19]的基础上,将文献[16]提出的具有通信机制的分布式故障诊断方法引入到文献[19]提出的基于状态估计的故障诊断方法中去，提出一种新的分布式离散事件系统可诊断性验证算法。

4 算例分析

本文结合上述算法，给出一种对高速公路状况的可诊断性验证的方法。由于大雾天气使得高速公路的能见度降低，危害车辆安全行驶，在本例中视其为故障诱因；同时，高速公路上车速较高，若发生道路损毁，容易引发危险，也应视为故障诱因。因此，为避免事故的发生，保证高速公路系统的正常运作，需要利用不同的站点来共同对高速公路中出现的安全隐患进行排查。为简单起见，将“大雾天气”视为一类故障诱因，“道路损毁”视为另一类故障诱因。只有2种诱因同时存在，才能引发道路故障。并设诊断系统包含有两类站点(即I={1,2})：第1类站点为站点1，可以观察高速公路天气状况；第2类站点为站点2，可以观察高速公路路面状况。

一个完整的系统G=(X,Σ,α,Xo)，表示某一时段内高速公路系统的路况(如图2所示)。

图 2 系统GFigure 2 System G

站点1和站点2为安装在车辆上，由相关通信设备和传感器所构成的两类站点，站点1可以识别高速公路的路面状况，站点2可以识别高速公路的天气状况。各站点间可以通过通信机制，同时利用本站点观察所得的事件信息与其他不同类型的站点进行信息交换。

假设对站点1，事件a表示雨天，事件b表示大雾天气，事件c表示雪天，事件d表示道路损毁(站点1无法观察)，事件u表示道路发生交通事故(两类站点均无法观察)；对站点2，事件a表示路面潮湿，事件b表示大雾天气(站点2无法观察)，事件c表示路面积雪，事件d表示道路损毁，事件u表示道路发生交通事故(两类站点均无法观察)，系统G的各状态表示事件发生之后系统所处于的对应状态。用两类站点的可观映射来表示上述事件，即

如表1所示。

表 1 站点与可被此站点观察到的事件Table 1 Each site and its events that can be observed by this site

假设系统G在某一时间段内发生了事件串abdc，诊断系统从当前G所处的初始状态集合Xo={1,3}，开始对G进行故障诊断。系统G在状态1到状态3之间发生了交通事故u，无法被两类站点所观察到，为避免事件u对系统G的影响，对系统G的状态进行划分：Xn={1,2,3,4,5,6,7,9,10}，Xf={8}。

从图1可知，系统G从初始状态集合出发，发生abdc的事件串后，产生2条不同的路径：经过路径1a2b4d7c8到达状态8；经过路径3a5b9d4c6会到达状态6。系统G在状态1到状态3之间发生了交通事故u，无法被两类站点所观察到，且由路径1u3a5b9d4c6会到达状态6。为避免事件u对系统G的诊断结果产生影响，对系统G的状态进行划分：Xn={1,2,3,4,5,6,7,9,10}为正常状态集合；Xf={8}为故障状态集合。

1) 站点1的状态评估过程。

(1) 站点1的初始化。事件u表 示高速公路发生交通事故，对2个站点均不可观。由算法1，站点1对状态的路径和标签进行初始化。站点1的E1初始化如图3所示。

图 3 初始化站点1的E1Figure 3 Initialize E1 for Site 1

(2) 更新路径和标签(站点1观察到G发生事件a)。由于事件a对站点1可观，站点1从贴上“1”标签的状态开始，对E1中的路径 ℘1进行更新；事件d对站点1不可观，所以E1中存在的路径为1a2或3a5，3a5d9，3a5d9d4，3a5d9d4d7。由本文算法可知，“1”标签传递到状态2、5、9、4和7。站点1更新后生成的E1如图4所示。

图 4 站点1观察到 G发生事件a 后生成的E1Figure 4 E1 generated by Site1 after observing eventa

(3) 更新路径和标签(站点1观察到G发生事件b)。由于站点1和站点2之间存在着通信延迟，假设此时站点1在收到站点2传来事件a的信息前，站点1先观察到G发生事件b。因事件b对站点1可观，所以站点1从贴有“1”标签的路径 ℘1开始更新E1。由于事件d对站点1不可观，因此站点1的E1更新后的路径为5b9、5b9d4、5b9d4d7或2b4、2b4d7。站点1更新后生成的E1如图5所示。

图 5 站点1观察到事件串 ab后的E1Figure 5 E1generated by Site1 after observing event stringab

(4) 更新路径和标签(站点1收到站点2对事件a的观察信息)。由图4可知，状态1和3贴有“2”标签。因事件b对站点2是不可观的，所以“2”标签的转移路径为1a2、1a2b4或 3a5、3a5b9，并最终转移到状态4和9上。站点1更新后生成的E1如图6所示。

图 6 站点1接收到来自站点2的事件a 后生成的E1Figure 6 E1 generated by Site1 after receiving event a from Site 2

(5) 冗余历史路径的修剪。由图6所示，两站点通信后，状态1和3上的标签均已传递到更新后的状态中去，状态1和3没有标签，应将包含状态1和3的无用路径截去。站点1更新后生成的E1如图7所示。

(6) 重复步骤(2) ～ (5)，直到两站点最终生成完全一致的状态评估图，即E1=E2，如步骤(7)所示。

(7) 冗余历史路径的修剪。最终得知状态4和7上没有标签，应对E1中冗余历史路径进行修剪。根据本文算法，站点1需将包含状态4和7的无用路径截去。站点1最终生成的E1如图8所示。

图 7 站点1进行修剪操作后生成的E1Figure 7 E1 generated by Site1 after trim operation

图 8 站点1进行修剪操作后最终生成的E1Figure 8 The final E1generated by Site1 after trim operation

2) 站点2的状态评估过程。

站点2的状态评估过程中，除以下步骤外，其余步骤与站点1相同，在此不做赘述。

(1) 更新路径和标签(站点2观察到G发生事件d)。由于站点1和站点2之间存在着通信延迟，假设此时站点2先观察到系统发生了事件d，再从站点1收到站点1对事件a的观察信息。若此时G在状态5发生事件d，则站点2需要为E2中 5d9的状态9贴上“2”标签，若G沿路径5b9d4行进，E2中的状态9不能贴上“2”标签。因为路径3a5b9d4在标签传递的过程中违背了本文算法对标签更新的规则：在E2中的“ 3a5”和“ 9d4”之间存在对站点2不可观的事件b。因此将E2中状态9分成2两个状态：9和9′，其中 9′看作是9 的克隆。站点2更新后生成的E2如图9所示。

图 9 站点2观察到事件b 后生成的E2Figure 9 E2generated by Site 2 after observing eventb

(2) 更新路径和标签(站点2接收到站点1对事件a的观察信息)。站点2在接收到站点1对事件a的观察信息后，E2中的“1”标签从状态1和状态3分别传递到状态2和状态5。由于事件d对站点1不可观，因此“1”标签传递到克隆状态 9′。站点2更新后生成的E2如图10所示。

图 10 站点2接收到来自站点1的事件a 后生成的E2Figure 10 E2generated by Site 2 after receiving event afrom site 1

(3) 冗余历史路径的修剪(站点2接收到站点1对事件c的观察信息)。最终站点2中E2的“1”标签和“2”标签从状态4、9和7分别传递到状态6和8。因此状态4、9和7不存在任何标签，站点2截去E2中冗余历史路径。站点2最终生成的E2如图11所示。

图 11 站点2进行修剪操作后最终生成的E2Figure 11 The final generated by Site 2 after trim operationE2

3) 诊断函数对系统G当前状态集合进行故障诊断。

站点1和站点2在系统G发生事件串abdc后，两站点均生成完全一致的状态评估图，即两站点最后有E1=E2。因系统G在发生事件串abdc后，到达故障状态8和正常状态6，系统G最终到达的状态集合Xˆi中既有属于Xf的元素，又有属于Xn的元素，所以D(℘i)=A。由定理1得知系统G是不可诊断的，即诊断系统在系统G发生事件串abdc后无法判断高速公路当前是否处于因“大雾天气”和“道路损毁”所引发的故障状态。

若考虑事件u可能对高速公路上运行的车辆产生危害，而将其作为故障诱因，从而将系统状划分改为Xf={6,8}，Xn={1,2,3,4,5,7,9,10}，最终可得D(℘i)=F。因此，由定理1得知系统G在这种情况下是可诊断的，即分布式离散事件诊断系统在系统G发生事件串abdc后得出高速公路当前处于由“交通事故”、“大雾天气”和“道路损毁”所引发的故障状态，此系统具有可诊断性。

5 总结

本文提出了一种基于状态评估的分布式离散事件系统可诊断性的验证算法，该方法能利用不断更新状态评估图使分布式离散事件系统中的每个站点都获得整个系统的状态评估信息，从而判断其是否具有可诊断性。同时，算法中对冗余历史记录的修剪操作可以去除对最终诊断结果无影响的历史记录，从而节约诊断系统的信息存储空间，进一步提高诊断系统的诊断效率。

在本文的研究基础之上，下一步将研究基于状态评估的分布式模糊离散事件系统故障诊断问题[15,20]，并考虑构造验证器对此类系统的可诊断性进行验证，使其复杂度降至多项式级别。