P/T_网中的同步距离

王丽丽，方贤文，方 欢，蔡瑞文

安徽理工大学 理学院，安徽 淮南 232001

P/T_网中的同步距离

王丽丽，方贤文，方 欢，蔡瑞文

安徽理工大学 理学院，安徽 淮南 232001

1 引言

Petri网作为描述异步并发现象的系统模型在许多领域得到广泛应用[1-4]，尤其在并发系统中显示出独特的优越性。然而有些系统中经常会遇到一些信息的同步问题，为了对这些同步问题进行定量的分析，C.A.Petri最先在文献[5]中将“同步距离”的概念引入到Petri网中。同步距离不仅可以对实际系统中任意两组事件之间的同步程度进行定量的描述，还可以作为刻画系统行为的工具，大量文献已经证明其对系统的分析、建模和优化提供一定的帮助，尤其在工作流领域应用最广泛[6-12]。

由于同步距离求解不仅和网的结构特征有联系而且和网的初始标识也存在联系，这无疑给同步距离的计算带来了一定的难度。目前只有一些Petri网子类如出现网[13]、标识 T-图[14]、标识 S-图[15]和标识 T-网[16]中同步距离求解已经有了较简洁的计算方法，而对于Petri网中同步距离的计算仍是一个难题。文献[17]采用观察库所来求解Petri网中同步距离，但是它只适用于那种不包含变迁出现次数不等的循环进程段。

本文讨论了P/T_网中任意两个变迁子集之间的同步距离计算，对于处于同一个公平分支的变迁子集通过采用文献[18]中带权观察库所的原理来求解它们之间的同步距离值，在此基础上进一步讨论了如何给P/T_网中连接变迁和带权观察库所之间的弧配置一个确定的权值，从而得到一个带权的同步观察P/T_系统；为了保证原网系统的动态行为不变，假定观察库所中已经配置了足够多的tokens数，通过模拟原网系统的可覆盖树可以得到观察库所拥有的最大tokens数和最小tokens数，然后通过计算其差值得到变迁之间的同步距离值，并给出相应的求解算法。

2 基本概念

关于Petri网的基本概念和结论详细内容见文献[19]，这里只对与本文密切相关的基本概念、术语和记号做一个简述或约定，以便后面的讨论。

关于带权观察库所的求解原理请参见文献[18]，这里不再赘述。

定义1[19]设 Σ=(S，T;F，M0)和 Σ′(S′，T;F′，M′0)为两个Petri网，如果存在满射 f: R(M′0)→R(M0)使得：

（1）f(M ′0)=M0。

（2）若 f(M′)=M 则对 ∀σ∈T*:在 Σ′中有 M′[σ＞当且仅当在Σ中有M[σ＞，则称Σ′和Σ是行为等价的。

为了避免观察库所中拥有的标识数随着循环进程段循环次数的增加而无限制增加，从而导致不能精确地求解同步距离值，本文采用加权同步距离的概念，通过给带权观察库所和变迁之间的弧引入权值来解决此问题。

定义2[19]设 Σ=(S，T;F，M0)为一个Petri网，t1，t2∈T，那么t1和t2之间的加权同步距离 sd12由下面公式给出：

其中r是Σ的一个本原可重复向量，且r(t1)≠0，r(t2)≠0。

关于一个网N的本原可重复向量的定义和求解算法详见文献[20]，此文不再赘述。

定义3设N=(S，T;F)为一个网，记N的本原可重复向量集合为 SPRVN，若 ∀X∈SPRVN都有 X(ti)＞0，X(tj)＞0或 X(ti)=0，X(tj)=0 （X(ti)表示变迁ti在向量X中对应的分量），那么称满足 X(ti)＞0，X(tj)＞0 的本原可重复向量 X为覆盖变迁ti和tj本原可重复向量，所有覆盖ti和tj本原可重复向量组成的集合记为SPRVij。

从定义3可知若T1是网N的变迁子集，且T1中变迁属于同一个公平分支，∀X∈SPRVN对于∀t∈T1要么都满足 X(t)＞0，要么都满足 X(t)=0，称满足 X(t)＞0的本原可重复向量X为覆盖变迁子集T1的本原可重复向量，所有覆盖变迁子集T1本原可重复向量组成的集合记为 SPRVT1。

从上述的定理1中可知：若两个变迁处于公平关系，那么覆盖它们的本原可重复向量对应的分量一定成比例。

从定理1易求出网系统的公平分支，具体方法文献[22]也有提及，这里不再叙述。

定义4设 N=(S，T;F)为一个网，T1，T2是网 N 的两个变迁子集，T1≠∅，T2≠∅，T1∩T2=∅ 且T1与 T2处于同一个公平分支，带权观察库所 p满足·p=T1，p·=T2，称满足下列条件的权函数为本原权函数：

（1）若 T1，T2中均只含有一个变迁，设 T1=ti，T2=tj

②若不存在本原可重复向量 X使得 X(ti)≠0，X(tj)≠0，则 w(ti，p)=w(p，tj)=1。

（2）若T1，T2中含有两个及以上变迁

①若存在本原可重复向量 X 使得∀ti∈T1，∀tj∈T2，有 X(ti)≠0，X(tj)≠0，记覆盖 T1和T2本原可重复向量集合为SPRVT1T2，X∈SPRVT1T2，设T1中变迁对应 X向量中分量的最小公倍数为k1，T2中变迁对应 X向量中分量的最小公倍数为 k2，对于 ∀ti∈ T1，∀tj∈ T2，有 w(ti，p)=k2，w(p，tj)=k1。

②若不存在本原可重复向量X使得∀ti∈T1，∀tj∈T2，有 X(ti)≠0，X(tj)≠0，对于 ∀ti∈T1，∀tj∈T2，则 w(ti，p)= w(p，tj)=1。

由于处于不同公平分支中变迁子集之间的同步距离为∞，所以定义4只讨论处于同一个公平分支中变迁子集和带权观察库所之间连接弧的权值配置。为了使得带权观察库所中拥有的tokens数不受存在发生次数不等的循环进程段的循环次数的影响，需要给带权观察库所与变迁之间的弧配置一个权值w，且其满足本原权函数的两个条件。

定义5设 Σ=(S，T;F，M0)是一个Petri网，R(M0)是网Σ的可达标识集，T1，T2是网N的两个变迁子集，T1≠∅，T2≠∅，T1∩T2=∅且T1与T2处于同一个公平分支，p为变迁子集T1和T2之间的带权观察库所，称 Σs= (S∪p，T;F∪F′，K，W，Ms0)是 Σ 的带权同步观察P/T_系统，若满足：

（1）·p=T1， p·=T2。

（2）F′={(t，p)|t∈T1}∪{(p，t)|t∈T2}。

（3）W:F′→{1，2，3，…}且W是本原权函数且K(p)=∞。

（4）Ms0=M0◦M0(p)，其中 M0(p)=h（h 是足够大的正整数）是 s12的初始标识，满足 ∀σ∈T*:M0[σ＞→Ms0[σ＞ 。

定理2[18]设 Σ=(S，T;F，M0)是一个 P/T_网，Σs= (S∪p，T;F∪F′，K，W，Ms0)是 Σ 的带权同步观察P/T_系统，R(Ms0)是 Σs的可达标识集，T1，T2是网 N的两个变迁子集，T1≠∅，T2≠∅，T1∩T2=∅ 且T1与 T2处于同一个公平分支，T1和T2之间的同步距离sd(T1，T2)可以通过下式计算：

3 处于同一个公平分支中变迁子集T1和T2之间同步距离求解

下面讨论如何利用观察库所来求解处于同一个公平分支中变迁子集T1和T2之间同步距离求解。

由于带权观察库所不属于网系统的一部分，只起到计数的作用，为了不影响原网系统的动态行为，假定带权观察库所 p的初始标识为h（其中h是足够大的正整数）。

采用带权观察库所的原理来求解P/T_网中处于同一个公平分支中两个变迁子集T1和T2同步距离时，由于带权观察库所中拥有的最大或最小tokens数和T1和T2中变迁的发生次数存在直接的关系，又因为网系统的可覆盖树能够很直观地显示每个变迁的可能发生次数，所以本文通过模拟可覆盖树的动态行为来计算变迁子集之间的同步距离值。

算法1变迁子集T1和T2之间的同步距离计算算法

输入拥有初始标识的带权同步观察P/T_系统Σs= (S∪p，T;F∪F′，K，W，Ms0)

输出变迁子集T1和T2的同步距离值sd(T1，T2)

步骤1Max(p)=Min(p)=h（h是带权观察库所 p初始tokens数）

步骤2R(Ms0)={Ms0}且Ms0作为根结点，标记为“新”

步骤3WhileR(Ms0)存在标记为“新”的标识 do任选一个标记为“新”的标识，设为Ms

步骤4If从 Ms0到 Ms的路上存在一个标识 M′s满足 ∀s∈S且s≠p，M′s(s)=Ms(s)then将Ms的标记改为“旧”，返回到步骤3

步骤5If ∀t∈T:﹁Ms[t＞ then将Ms的标注改为“旧”，返回到步骤3

步骤6for 每个满足Ms[t＞的t∈T do

（1）计算 Ms[ti＞M′s中的 M′s

（2）If 从 Ms0到 M′s的有向路上存在 M″s使得∀s∈ S，M″s(s)≤M′s(s)then

（3）找出使 M″s＜M′s的分量 j，若 j≠n+1，其中 n为原网系统中库所总个数，将M′s中的第 j个分量改为ω

（4）IfM′s(s12)＞ Max(s12)then Max(s12)=M′s(s12)

（5）IfM′s(s12)＜ Min(s12)then Min(s12)=M′s(s12)

（6）R(Ms0)=R(Ms0)∪ M′s，从 Ms到 M′s画一条有向弧，并把此弧旁标以ti，擦去结点Ms的“新”标注，并将结点 M′s添加“新”标注，返回到步骤3

步骤 7sd(T1，T2)=Max(p)-Min(p)

4 P/T_网中任意两个变迁之间同步距离的求解

算法思想：当网系统Σ不存在本原可重复向量时，显然任意两个变迁子集T1和T2都处于公平关系，此时利用算法1来求解同步距离。当网系统Σ存在本原可重复向量时，要分类考察变迁子集T1和T2之间的关系，根据它们处于同一个公平分支还是处于不同的公平分支分别求解它们之间的同步距离。只有处于同一个公平分支的变迁子集，才需利用算法1进行求解。具体算法描述如下所示。

算法2求解P/T_网中任意两个变迁子集之间的同步距离算法

输入P/T_网 Σ=(S，T;F，M0)以及 T1，T2为网系统的变迁子集

输出T1和T2之间的同步距离sd(T1，T2)

步骤1求网Σ=(S，T;F)的所有本原可重复向量

步骤2If不存在本原可重复向量 then 采用算法1求sd(T1，T2)

步骤3If存在本原可重复向量，记为SPRVN={X1，X2，…，Xk}，then

步骤4If ∀Xi∈SPRVN，T1，T2∉‖Xi‖（说明 T1，T2均不属于部分可重复网）then采用算法1求sd(T1，T2)

步骤 5If ∃Xi∈ SPRVN且∃t1∈ T1，∃t2∈ T2，使得 t1∈‖Xi‖但t2∉‖Xi‖(或 t2∈‖Xi‖但t1∉‖Xi‖)then

步骤6else求出覆盖T1和T2的本原可重复向量SPRVT1T2

步骤 7If ∃Xi，Xj∈ SPRVT1T2满足∃ti∈ T1，∃tj∈ T2使得

步骤8else利用算法1求出sd(T1，T2)

下面通过一个实例来演示算法1和算法2步骤。

例1图1为一个P/T_网，此网存在三个公平分支为{t1}，{t2}，{t3，t4}下面分别来求 sd(t1，t2)，sd(t1，t3)，sd(t3，t4)。

图1 P/T_网 Σ1

易知此网存在两个本原可重复向量X(1)=[1 1 0 0]，X(2)=[1 2 1 1]，由算法2中的步骤5可知，sd(t1，t3)=∞，又由算法2中的步骤7可知，t1与t2处于非公平关系，所以 sd(t1，t2)=∞。从算法2中的步骤8可知，t3与t4处于公平关系，接下来着重讨论如何利用算法1来求t3和t4之间的同步距离。

根据带权同步观察P/T_系统的构造定义可知ω(t3，s34)=ω(s34，t4)=1，利用算法1构造出带权的同步观察P/T_系统的可覆盖树如图2所示，在构造过程中可以得到Max(s34)=h+1，Min(s34)=h，故变迁t3和t4之间的同步距离为 sd(t3，t4)=Max(s34)-Min(s34)=1。

5 结束语

图2 带权同步观察P/T_系统的可覆盖树

文中讨论了如何利用观察库所来求解P/T_网中任意两个变迁子集之间的同步距离，并给出相应的计算算法。算法首先根据本原可重复向量来判断某两个变迁子集是否处于同一个公平关系，对于处于两个不同的公平分支中的变迁子集无需给它们配置加权观察库所就可直接得出它们的同步距离值为无穷大，对于处于同一个公平分支的变迁变迁子集，为了使得同步距离不因变迁在循环进程段中出现次数不等而导致观察库所中拥有的标识数随着循环次数无限制的增加，需要给带权观察库所和变迁之间引入本原权函数，从而得到一个带权同步观察P/T_系统。通过模拟原网系统的可覆盖树可以得到带权观察库所在系统运行过程中拥有的最大和最小tokens数，从而得到变迁之间的同步距离值，并给出了相应算法。

本文的同步距离计算算法采用模拟可覆盖树来求处于同一个公平分支变迁子集之间的同步距离值，所以此算法的复杂度和可覆盖树的复杂度是同级别，考虑如何降低算法的复杂度是下一步有待研究的问题。

[1]何炎祥，沈华.一种基于随机Petri网的Web服务组合性能瓶颈定位策略[J].计算机学报，2013，36（10）：1953-1966.

[2]黄翔，陈志刚.资源敏感的分布式系统性能建模方法[J].计算机科学，2013，40（9）：174-180.

[3]刘永磊，金志刚.无限局域网WPS安全性分析[J].计算机工程与应用，2013，49（21）：87-89.

[4]林闯，杨宏坤，单志广.Petri网在生物信息学中的应用[J].计算机学报，2007，30（11）：1889-1900.

[5]Petri C A.Interpretations of net theory[M].2nd ed.St Augustin：Gesellehaft fur Mathematik und Datenverarbeitung Bonn，1976.

[6]Murata T.Petri nets：properties，analysis and applications[J]. Proceedings of the IEEE，1989，77（4）：541-568.

[7]袁崇义.Petri网原理与应用[M].北京：电子工业出版社，2005. [8]闫哲，赵文，袁崇义，等.基于同步网的工作流过程变动问题研究[J].电子学报，2006，34（2）：226-231.

[9]王斌，章云，王晓红.基于Petri网的工作流模式建模与应用[J].计算机工程与应用，2008，44（13）：238-241.

[10]Zhao Wen，Huang Yu，Yuan Chongyi.Synchronic distance based workflow logic specification[C]//Proceedings of the 2008 10th IEEE International Conference on High Performance Computing and Communications，2008：819-824.

[11]Yuan Chongyi，Huang Yu，Zhao Wen，et al.A study on fairness of place/transition systems-to make fairness fairer[J].Transactionsofthe Institute ofMeasurement and Control，2011，33（1）：50-58.

[12]方欢，陆阳.混杂Petri网系统中同步距离的确定及同步控制器的设计[J].控制理论与应用，2012，29（7）：884-892.

[13]候春龙，齐新战，卫翔.基于Petri网建模的互斥问题优化方案[J].系统仿真技术，2012，8（3）：238-243.

[14] 袁崇义.出现网的同步距离[J].应用数学学报，1984，7（4）：459-466.

[15]张军明，吴哲辉.标识S-图中同步距离的计算[C]//中国计算机学会PETRI网学术会议论文集，南京，1995：61-67.

[16]王丽丽，吴哲辉，方欢.标识T-网中同步距离的计算[J].计算机科学，2008，35（10）：100-103.

[17]张金泉，倪丽娜，蒋昌俊.Petri网的同步距离计算[J].计算机科学，2005，32（12）：138-141.

[18]袁崇义.Petri网应用[M].北京：科学出版社，2013.

[19]吴哲辉.Petri网导论[M].北京：机械工业出版社，2006.

[20]岳昊，吴哲辉，刘关俊.Petri网本原可重复向量的求解算法及实现[J].小型微型计算机系统，2009，30（9）：1815-1818.

[21]王丽丽，吴哲辉，方贤文，等.关于Petri网中同步距离定义的研究[J].合肥工业大学学报：自然科学版，2013，36（3）：303-308.

[22]吴哲辉，郭玉彬.Petri网中亚公平关系与亚公平网[J].山东科学技术大学学报：自然科学版，2001，20（1）：4-9.

WANG Lili,FANG Xianwen,FANG Huan,CAI Ruiwen

College of Science,Anhui University of Science and Technology,Huainan,Anhui 232001,China

The synchronic distance is not only an analyzing metric to describe the synchronic relationship between two events,but also a tool to represent the dynamic behavior of systems.However,it’s difficult to calculate the synchronic distance in a Petri net.The paper discusses the synchronic distance between any two subsets of transition in a P/T_net by using the principle of a weighted observe-place,and it points out that how to allocate a weight to an arc connecting a weighted observe-place and a transition by the definition of primitive weight function.In order to obtain the synchronic distance between two subsets of transition which are in the same fair-components,a synchronic observed P/T_system with weight is constructed.The maximum tokens and the minimum tokens in a weighted observe-place can be yielded during constructing the coverability tree of a original net system,therefore the synchronic distance between two subsets of transition is obtained,the corresponding algorithm is also given.The algorithm of computing the synchronic distance between any two subsets of transition in a P/T_system is given.

P/T_net;fair-components;weighted observe-place;synchronic observed P/T_system with weight;primitive weight function;synchronic distance

同步距离既可以对两组事件之间同步程度进行定量分析，也可以刻画系统动态行为，然而Petri中同步距离计算一直存在难题。采用加权观察库所的原理讨论了P/T_网中任意两个变迁子集之间同步距离的计算，并通过本原权函数的定义指出了如何给连接变迁和加权观察库所之间的弧配置一个唯一的权值。为了得到处于同一个公平分支变迁子集之间的同步距离值，需构造一个带权同步观察P/T_系统，通过模拟原网系统的可覆盖树得到带权观察库所的最大和最小tokens，从而求得变迁子集之间的同步距离值，并给出相应算法，给出了求解P/T_网中任意两个变迁子集之间同步距离计算算法。

P/T_网；公平分支；带权观察库所；带权同步观察P/T_系统；本原权函数；同步距离

A

TP391.9

10.3778/j.issn.1002-8331.1402-0115

WANG Lili,FANG Xianwen,FANG Huan,et al.Synchronic distance in P/T_net.Computer Engineering and Applications,2014,50（23）：47-50.

国家自然科学基金（No.61272153，No.61170059，No.61340003）；安徽省高校自然科学基金重点项目（No.KJ2011A086）；安徽省自然科学基金（No.1208085MF105）；安徽省软科学研究计划项目（No.12020503031）；安徽理工大学青年教师科学研究基金（No.2012QNY36）。

王丽丽（1983—），女，讲师，研究领域为Petri网理论与应用、算法设计与研究；方贤文（1974—），男，博士，教授，研究领域为Petri网理论与应用、可信软件以及Web服务等。E-mail：wanglili198301@163.com

2014-02-17

2014-05-07

1002-8331（2014）23-0047-04

CNKI网络优先出版：2014-07-11,http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1402-0115.html