0 引言

离散事件系统(discrete event system，DES)是一类以事件为驱动，离散的动态系统^[1]，状态估计是DES研究中的一个基本问题，其在自动机领域和PNs(petri nets)中有着广泛的研究^[2-4]。然而状态估计无法准确地、唯一地确定系统当前状态，为此SHU等在状态估计的基础上提出了可测性^[5]。可测性要求系统根据已观察到的系统的行为，确定系统当前状态及系统未来所处的状态^[5-10]。

在实际生活中，许多系统大多采用分布式框架^[11-13]，由于集中式系统无法解决物理分布复杂的、含有多个局部站点的分布式系统的相关问题，为此前人将集中式DES的相关研究推广至分布式DES中，近年来分布式DES的研究也受到众多关注^[11-13]。文[5-10]有关可测性的研究都是基于集中式系统展开的，为处理分布式DES的可测性的问题，文[12]在经典分布式DES框架下提出了协同可测性，解决了分布式DES的可测性相关问题。

在实际生活中存在这样一类自动机：发生状态转移时会携带对应定量信息的系统^[13-20]，如时间自动机、(max，+)自动机等，定量信息可代表时间、权重或资源等。传统DES和PNs的事件只能描述系统状态间的逻辑转移，无法准确描述的状态转移过程中会存在对应的定量信息的系统，而加权自动机(weighted automata，WA)是一类被广泛研究的DES模型，其状态转移会伴随着一个可代表时间、资源或开销等实际意义的权值^[13-20]，LAI等在文[19-20]中对无歧义加权自动机(unambiguous weighted automata，UWA)的可测性进行了深入研究。

本文在文[19-20]的基础上，以加权自动机为模型解决了传统DES在状态转移间无法携带定量信息的问题，研究分布式加权离散事件系统(decentralized weighted discrete event system，DWDES)的协同可测性，提出了基于各分站点观察器构造协同观察器的算法，并由此给出强协同可测性和弱协同可测性的充要条件。

1 基本知识

加权离散事件系统G=(X，Σ，μ，δ，Q₀)^[19-20]，其中X、Σ分别为G的状态集和事件集；μ：Σ→ S^|X|×|X|是事件的权值矩阵，S^|X|×|X|是一个|X|行|X|列的矩阵，Σ中的每个事件都有一个对应的权值矩阵，记录了该事件在转移间产生的权值。若存在一个事件串ι=a₁…a_k∈Σ^*，则有定义μ(ι)= μ(a₁)+…+μ(a_k)，用μ_xx′(a)表示状态x经过事件a到达状态x′的权值；δ：X×Σ×X→D为转移函数，D表示取值为实数的权值的集合；Q₀是初始状态集。

事件集Σ=Σ_o∪Σ_uo，沿用文[19-20]的方法，不可观事件集Σ_uo中的事件都用u表示，Σ_o为可观事件集。p_ref(ι)表示事件串ι的前缀闭包，||ι||表示事件串ι的长度，空串λ的长度为0。

长度为k的路径，其对应的加权事件串为φ(υ)=(a₁，τ₁)(a₂，τ₂)…(a_k，τ_k)∈(Σ×D)^*，其中τ₁ = μ_x0x1(a₁)₁，τ_j = τ_j-1+μ_xj-1xj(a_j)，j = 2，…，k。

G中状态x经过事件串ι=a₁a₂…a_k∈Σ^*到达状态x′的路径的集合，记为

若∃X₁，X₂⊆X，则有：

假设G有m个分站点(站点集I={1，2，…，m})，第i个分站点G_i=(X，Σ，μ，δ_i，Q₀)的可观事件集为Σ_i，o。G_i的投影定义为P_i：(Σ×D)^*→(Σ_i，o×D)^*，其中P_i(λ)=λ，

G的总站点G_t=(X，Σ，μ，δ_t，Q₀)，其可观事件集为G的可观事件集，即，G_t的投影为P_t：(Σ×D)^*→(Σ_t，o×D)^*，转移函数δ_t：X×Σ×X→D定义为

G_t的加权语言L_t为

L_t={s∈(Σ×D)^*|∃x∈X，∃ι∈Σ^*，∃ω∈f(Q₀，ι，{x})：φ(ω)=s}，P_t(L_t)是G_t的可观加权语言。Σ^∞表示Σ^*中长度趋向无穷的事件串集，G_t中所有长度趋向无穷的加权事件串的集合L_t^ω={s∈(Σ×D)^∞|p_ref(s)⊂L_t}。

2 DWDES的协同可测性的形式化

沿用文[19-20]的方法，假设G是无死锁、无歧义，并且G中不包含u^*循环。

定义1  假设分站点G_i中存在可观加权事件串s∈P_i(L_t)，可观加权事件串s可到达状态的集合记为R_i(s)：

定义2  给定一个DWDES G，若它满足条件：

(1)

则G是强协同可测的。

直观上，G为强协同可测的是指对于G的任意一条无限长的路径，都至少存在一个站点能够在经过有限步观测延时后确定系统G的当前状态。

定义3  给定一个DWDES G，如果它满足条件：

(2)

则G是弱协同可测的。

直观上，G为弱协同可测的是指G存在某条无限长的路径，使得至少存在一个站点能够在经过有限步观测延时后确定系统G的当前状态。

3 协同观察器的构造

记状态集X子集X′的不可观到达为U_reach(X′)=X′∪{x′∈X|∃x∈X′，∃i∈{0，1，…，|X|-1}：f(x，uⁱ，x′)!}。

要构建DWDES的协同观察器，首先要先为各分站点和总站点构造其观察器，然后再构建协同观察器。

在文[19]中提出的构造加权自动机观察器的基础上，给出构造加权离散事件系统观察器的算法：

算法1  构造加权离散事件系统的观察器：

输入：系统G=(X，Σ，μ，δ，Q₀)，Σ_o。

输出：G的观察器G_obs=(X_obs，E_obs，δ_obs，Q₀^obs)。

步骤1：构造非确定有限状态自动机G_o=(X_o，E_obs，δ_o，Q₀)：X_o=X₁∪Q₀，X₁是可观事件可达状态集X₁={x′∈X|∃x∈X，∃σ∈Σ_o：δ(x，σ，x′)!}；事件集为E_obs={(σ，τ)∈Σ_o×D|∃x∈X_o，∃x′∈X，∃i∈{0，…，|X|-1}，μ(uⁱσ)_xx′=τ}；状态转移集δ_o⊆X_o×E_obs×X_o：δ_o(x，(σ，τ)，x′)!当且仅当μ_xx′(uⁱσ)=τ≠ε，i∈{0，…，|X|-1}。

步骤2：对G_o确定化，构造确定有限状态自动机G_obs^′=(X_obs^′，E_obs，δ_obs^′，q_0，obs^′)=Ac(2^X_o，E_obs，δ_obs^′，q_0，obs^′)，其中q_0，obs^′=Q₀，Ac(·)表示去除掉其中所有不可到达的状态及其对应的转移；状态转移函数δ_obs^′：2^X_o×E_obs→2^X_o：δ_obs^′(x_obs^′，(σ，τ))={x′∈X_o|∃x∈x_obs^′，(σ，τ)∈E_obs：δ_o(x，(σ，τ)，x′)!}。

步骤3：  构造观察器G_obs=(X_obs，E_obs，δ_obs，Q₀^obs)。将G_obs^′中的每个状态替换为它们的不可观到达：Q₀^obs=U_reach(q_0，obs^′)；X_obs={U_reach(x_obs^′)|∃x_obs^′∈X_obs^′}；δ_obs：X_obs×E_obs→X_obs，其中：

注1  由于G_o的转移最多为|X|⁴×|Σ_o|，而G_obs^′状态数为|X_obs^′|=2^|X|-1，转移最多为(2^|X|-1)×|X|³×|Σ_o|，并且G_obs的转移最多为(2^|X|-1)×|X|³×|Σ_o|，因此，算法1复杂度为O(2^|X|×|X|³×|Σ_o|)。

下面给出构造DWDES协同观察器的算法：

算法2  构造DWDES的协同观察器：

输入：  G_i，obs(i∈I)，G_t，obs。

输出：  G的协同观察器G_co，obs=(Y，E_co，obs，δ_co，y₀) =(X_1，obs…X_m，obsX_t，obs，E_co，obs，δ_co，y₀)。

步骤1：  初始状态y₀=(y₀(1)，…，y₀(m)，y₀(m+1))=(Q_1，0^obs，…，Q_m，0^obs，Q_t，0^obs)。

步骤2：  加权事件集E_co，obs=E_t，obs。

步骤3：  对于y=(y(1)，…，y(m+1))∈Y，σ∈E_co，obs，定义转移函数δ_co(y，σ)为

其中，

其中i∈I，加权事件s_i=(ω，τ)的初始值为空(λ，ε)即ω=λ，τ=ε；x_σ、τ_σ分别为加权事件σ的事件和权值。

注2  由于G_obs的状态数最多为2^|X|-1，而G_co，obs的状态数|Y|=(2^|X|-1)^m+1，并且G_obs的事件数为|X|³×|Σ_o|，所以G_co，obs的事件数|E_co，obs|=|E_t，obs|=|X|³×|Σ_o|。因此，算法2的复杂度为O(2^(m+1)|X|×|X|³×|Σ_o|)。

4 协同可测性的充要条件

设G_t存在s_o=(e₁，τ₁)…(e_k，τ_k)∈P_t(L_t)，s_o在E_co，obs^*的等价形式^[19]为s_o^elem=(e₁，τ₁)(e₂，τ₂-τ₁)…(e_k，τ_k-τ_k-1)，k≥2，并且P_t(L_t)^elem={s∈(Σ_t，o×D)^*|∃s_o∈P_t(L_t)：s_o^elem=s}。

协同观察器G_co，obs中含单态元素的状态的集合记为Y_co，obs^single={y|∃i∈I，y∈Y，|Y_i(y)|=1}，Y_i(y)表示y中第i个站点的状态集。把G_co，obs中所有的基本循环记为Loop：

定理1  DWDES G是强协同可测的当且仅当协同观察器G_co，obs满足条件：

(3)

证明  充分性：用反证法证明。设G是强协同可测的且G_co，obs满足(∃(y，s)∈Loop)(∃s₁∈E_co，obs^*)δ_co(y，s₁)∉Y_co，obs^single。令v∈E_co，obs^*且δ_co(y₀，v)=y，因为∃s₁∈E_co，obs^*使得δ_co(y，s₁)∉Y_co，obs^single，因此δ_co(y₀，vs₁)∉Y_co，obs^single。又因为∃(y，s)∈Loop，因此δ_co(y₀，vs^js₁)∉Y_co，obs^single。令P_t(s₁^′)^elem=vs^js₁，有Y_i(δ_co(y₀，s^elem))=R_i(P_i(s))。又δ_co(y₀，P_t^elem(s₁^′))=δ_co(y₀，vs^js₁)，因此(∀i∈I)|Y_i(δ_co(y₀，P_t^elem(s₁^′)))|≠1⇒|R_i(P_i(s₁^′))|≠1。取j尽可能大，vs^js₁∈L_t^ω，有s₁∈L_t^ω，这与G是强协同可测矛盾。

必要性：用反证法证明。假设G不是强协同可测的，则(∀n∈N)(∃s∈L_t^ω)(∃s′∈p_ref(s))||P_t(s′)||>n⇒(∀i∈I)|R_i(P_i(s′))|≠1，并且设n=|Q_co，obs|，系统存在无限长的加权事件串s∈L_t^ω，s的某个前缀s′在总站点G_t的投影之后得到的可观加权事件串长度大于n，即||P_t(s′)||>n，此时系统存在某个站点能使|R_i(P_i(s′))|≠1。因为||P_t(s′)||>n=|Q_co，obs|，则在协同观察器中，当发生加权事件串P_t^elem(s′)∈E_co，obs^*后，G_co，obs当前的状态一定会位于G_co，obs的某个基本循环(y，s₁)中；令v∈E_co，obs^*且δ_co(y₀，v)=y，s₂∈E_co，obs^*满足P_t^elem(s′)= vs₂，所以δ_co(y，s₂)位于Loop中。再根据假设有(∃(y，s₁)∈Loop)(∃s₂∈E_co，obs^*)δ_co(y，s₂)∉Y_co，obs^single。

定理2  DWDES G是弱协同可测性的当且仅当其协同观察器G_co，obs满足条件：

(4)

证明  充分性：设G的协同观察器G_co，obs满足(∃(y，s)∈Loop)(∀s₁∈p_ref(s))δ_co(y，s₁)∈Y_co，obs^single。让v∈E_co，obs^*且δ_co(y₀，v)=y，设s₁=vs^j∈P_t(G_t)，其中j是一个无限大的正整数，从假设可知δ_co(y₀，vs^js₂)∈Y_co，obs^single。令n=|v|∈N，从而Y_i(δ_co(y₀，s₁^elem))=R_i(P_i(s₁))且∀s₂∈p_ref(s)，令s₁^′=p_ref(s₁)可得，定义3的式(2)成立，所以，是弱协同可测性的。

必要性：设G是弱协同可测的，即：

因为s∈L_t^ω，因此P_t^elem(s)一定经过G_co，obs的某个基本循环(y，s₁)∈Loop，此时必然存在v∈E_co，obs^*使得δ_co(y₀，v)=y；从而(∃i∈I)|R_i(P_i(s′))|=1。又由于(∀s₂∈p_ref(s₁))δ_co(y₀，vs₂)∈Y_co，obs^single，δ_co(y₀，v)=y，可得(∀s₂∈p_ref(s₁))δ_co(y，s₂)∈Y_co，obs^single。

5 实例分析

无线传感器网络系统能代替人检测物理环境，它是由一个或多个基站及多个不同类型的传感器节点组成的一种自组织网络。系统中传感器节点通过无线方式通信，节点使用微型电池实现续航，发送信息时会消耗能量，会面临着电池电量耗尽的实际问题；由于物理环境的复杂性节点可能会失效，会存在信息丢失的情况。因此在信息传输过程中确定信息的位置和了解节点电量变化显得尤为重要。

问题是：一个已经设计好的无线传感器网络系统在信息传输的过程中，是否能准确地确定信息位置和清晰地了解传感器节点的电量变化？考虑某个测量沙漠温度和湿度的无线传感器网络系统，由于每个基站负责处理的信息类型不相同，因此该系统可以看成分布式系统如图 1所示，其中Σ_1，o={a，b，c，d，e，f}，Σ_2，o={a，b，c，d，e，g}。

如图 1所示，信息传输的过程中节点的电量损耗用权值表示，节点间的信息传输用事件表示。节点的初始电量都为100，由于节点物理距离的不同，信息传输的电量损耗不同。测温度传感器和测湿度传感器分别用Ⅰ类传感器和Ⅱ类传感器表示，在图 1中，节点1、节点4、节点5为Ⅰ类传感器，节点2、节点3、节点6为Ⅱ类传感器，节点7、节点8是基站。事件描述及每次事件消耗单位电量(mA·h) 如表 1所示。

根据算法1构造总站点观察器G_t，obs，如图 2所示。

然后再生成协同观察器G_co，obs，如图 3所示。由图 3可知G_co，obs处于Loop的状态有{{7}{7}{7}}、{{8}{8}{8}}、{{4}{8}{8}}、{{7}{6}{7}}，而这些状态都属于Y_co，obs^single的，从定理1可知G是强协同可测的，这表明系统在进行信息传输时，至少存在一个站点能确定系统当前状态。由于G_co，obs除初始状态{{1，2}，{1，2}，{1，2}}不属于Y_co，obs^single，其余状态都属于Y_co，obs^single的，因此除初始状态不存在一个分站点能确定系统的状态之外，其余的状态都存在一个分站点能确定系统的状态。

假设中发生以下转移：状态{{1，2}{1，2}{1，2}}经过事件串(b，0.2)(a，0.1)(g，0.4)(e，0)到达状态{{7}{7}{7}}，结合自动机可知，发生转移的节点依次是节点2、节点5、节点6、节点7；假设该无线传感网络系统各节点的电量在发生上述转移前仍为100；而节点2、节点5、节点6的电量损耗分别为0.2、0.1和0.4，则上述节点发生转移后的电量分别为99.8、99.9、99.6。因此通过记录加权事件串可知转移发生时节点电量的变化。

6 总结

本文在分布式框架下对加权DES的可测性问题进行了研究，基于各分站点的观察器构造了DWDES的协同观察器，并由此得到DWDES协同可测性的充要条件，并以无线传感器网络系统为实例，对DWDES的协同可测性进行分析。在本文的基础上，还可以进一步考虑DWDES的周期协同可测性、I-协同可测性等，将在后续研究中探讨这些问题。