子网行为等价的特殊网系统的同步距离

王丽丽　方贤文　张苗苗��

摘要：同步距离是刻画事件之间同步关系的一个重要的定量分析手段，已经有相关文献表明它对系统的设计和分析提供了很大的帮助，尤其在工作流和工业生产控制系统的协调结构设计方面有着显著的优势。然而目前只有一些特殊的子网中变迁之间的同步距离计算有较简洁的算法，为了使得更多的网系统其同步距离计算也能够有简洁的算法，证明了若一个网系统的行为等价与某个特殊的子网，那么此网系统中变迁之间的同步距离的求解就可以转化为其行为等价的特殊子网的同步距离的求解问题，并且给出了寻找其行为等价的特殊子网的算法， 最后进行了相应的实验验证。

关键词：Petri网；同步距离；行为等价；特殊子网

中图分类号：TP3919 文献标志码：A

文章编号：1672-1098（2014）01-0019-05

Petri网的概念是1962年由德国科学家C.A.Petri首先提出来的，它是分布式系统的描述和分析工具[1]541，特别便于描述系统中进度和部件的顺序、并发、冲突及同步等关系，广泛的应用于很多实际的系统，如离散事件系统[2]，柔性制造系统[3]，软件工程[4]，通信协议[5]和生物信息学[6]等系统。

文献[7]中最先将“同步距离”的概念引入Petri网，它是描述两个事件（或事件集）之间同步的一个重要的系统恒定性质，反映出两个变迁（变迁集）之间相对独立程度，不仅可以对两个（组）事件同步程度给出定量描述，而且也是刻画系统动态行为的工具。已经有大量的文献验证了同步距离对系统设计和分析提供了很大的帮助，譬如在工作流模型中，可以利用同步距离对工作流模型进行分析，从而检验和控制工作流程[8-14]。

由于同步距离的求解不仅和网的结构特征有关系而且和网的初始标识也存在关系，所以到目前为止还没有一个很简洁易行的算法来求解一般Petri网的同步距离，然而一些特殊的Petri网子类如出现网[15]、标识T-图[1]560、标识S-图[16]和标识T-网[17]的同步距离的计算已经有了较简洁的求解方法。本文基于此出发证明了若一个网系统的行为等价于某个特殊的子网，那么此网系统中变迁之间的同步距离的求解就可以转化为其行为等价的特殊子网的同步距离的求解问题，同时给出了相应的寻找行为等价特殊子网的算法。

2基本概念

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

说明：① 算法1中的step3表明如果库所s1能得到标识时，则s2一定也能够得到标识；但是s2得到标识时，s1不一定能够得到标识，又由于M0（s1）≤M0（s2），所以此时当s1，s2同时作为变迁t的前集时，t的引发其实主要受到s1中拥有的标志数的影响（M0（s2）-M0（s1）个标志对t的引发不起作用），故在step4中可以将弧（s2，t）从网中删去。

② 算法1中的step5表明si对网中各个变迁的行为不产生影响，可视si为冗余库所，因此在step6中可以将si及其关联的弧从网中删去

不难发现，上述算法中每个步骤均在保持原网行为不变的前提下进行的，通过对网按照算法1步骤进行化简我们可以得到另一个结构更加简单且行为等价的网′。此时若′为一个特殊的子网，我们则可以将求解网系统中变迁之间的同步距离转化为求解′中变迁之间的同步距离。

下面通过一个具体的例子来说明如何利用算法1对已知的网系统进行化简，然后通过判断化简以后的网系统是否等价于某一特殊子网来求其变迁之间的同步距离。

通过对比可知我们求得的同步距离值和采用文献[18]中方法得到的结果相同。

推论：设=（S，T；F，M0）和′=（S′，T；F′，M′0）为两个Petri网，如果这两个网系统是行为等价的，则网系统和网系统′中变迁之间的同步距离值是相等的。

证明：由于网和网′是行为等价的，故满足定理1中的（1）（2）条件，又从定理1可知若两个网系统和′满足（1）（2）条件，那么对网Σ中ti，tj∈T

有sd（ti，tj）等于网1中sd（ti，tj）。

故网系统和网系统′中变迁之间的同步距离值是相等的。证毕。

5结束语

本文证明了一些与某个特殊子网行为等价的网系统的同步距离的求解可以转化为与其行为等价的特殊子网的同步距离的求解。同时给出了如何寻找到一个与原网系系统行为等价且结构更加简洁的另一个网系统的求解算法，然后通过判断与其行为等价的网系统是否属于某个特殊的子网，若是，就将此网的同步距离求解变换为与其行为等价的特殊子网同步距离的求解，最后结合实例对算法进行了阐述。

参考文献：

[1]MURATA T. Petri Nets： Properties， analysis and applications[J].Proceedings of the IEEE， 1989， 77（4）： 541-568.

[2]HOLLAY L E， KROGH B H， GIUA A.A survey of Petri net methods for controlled discrete event systems[J]. Discrete Event Systems： Theory and Applicaitons， 1997， 7（2）： 151-190.

[3]LI ZHI-WU， ZHOU MENG-CHU， WU NAI-QI.A survey and comparison of Petri net-based deadlock prevention policies for flexible manufacturing systems[J]. IEEE Transcations on Systems，Man， and Cybernetics， Part C： Applications and Reviews， 2008， 38（2）： 173-188.

[4]HONG JANG-EUI， BAE DOO-HWAN.Software modeling and analysis using a hierarchical object-oriented Petri net[J]. Information Sciences， 2000， 130（1-4）： 133-164.

[5]OSAMA S YOUNESS， WAIL S EI-KILANI， WAIEL F ABD EI-WAHEDA.A behavior and delay equivalent petri net model for performance elvaluation of communication[J]. Computer Communications， 2008， 31（10）： 2 210-2 230.

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

[7]PETRI CA. Interpretations of Net Theory[M]. Second Edition， St Augustin：Gesellehaft fur Mathematik und Datenverarbeitung Bonn，1976：8-20.

[8]袁崇义. Petri网原理与应用[M]. 北京：电子工业出版社，2005：1-15.

[9]闫哲，赵文，袁崇义，等. 基于同步网的工作流过程变动问题研究[J].电子学报，2006，34（2）：226-231.

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

[11]ZHAO WEN， HUANG YU， YUAN CHONG YI. Synchronic Distance Based Workflow Logic Specification[C]// Proceedings of the 2008 10th IEEE International Conference on High Performance Computing and Communications. Dalian： Inst. of Elec. and Elec. Eng. Computer Society， 2008： 819-824.

[12]YUAN CHONG-YI， HUANG YU， ZHAO WEN，et al. A study on fairness of place/transition systems-to make fairness fairer[J]. Transactions of the institute of measurement and control， 2011， 33（1）： 50-58.

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

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

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

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

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

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

（责任编辑：李丽）

[4]HONG JANG-EUI， BAE DOO-HWAN.Software modeling and analysis using a hierarchical object-oriented Petri net[J]. Information Sciences， 2000， 130（1-4）： 133-164.

[5]OSAMA S YOUNESS， WAIL S EI-KILANI， WAIEL F ABD EI-WAHEDA.A behavior and delay equivalent petri net model for performance elvaluation of communication[J]. Computer Communications， 2008， 31（10）： 2 210-2 230.

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

[7]PETRI CA. Interpretations of Net Theory[M]. Second Edition， St Augustin：Gesellehaft fur Mathematik und Datenverarbeitung Bonn，1976：8-20.

[8]袁崇义. Petri网原理与应用[M]. 北京：电子工业出版社，2005：1-15.

[9]闫哲，赵文，袁崇义，等. 基于同步网的工作流过程变动问题研究[J].电子学报，2006，34（2）：226-231.

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

[11]ZHAO WEN， HUANG YU， YUAN CHONG YI. Synchronic Distance Based Workflow Logic Specification[C]// Proceedings of the 2008 10th IEEE International Conference on High Performance Computing and Communications. Dalian： Inst. of Elec. and Elec. Eng. Computer Society， 2008： 819-824.

[12]YUAN CHONG-YI， HUANG YU， ZHAO WEN，et al. A study on fairness of place/transition systems-to make fairness fairer[J]. Transactions of the institute of measurement and control， 2011， 33（1）： 50-58.

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

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

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

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

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

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

（责任编辑：李丽）

[4]HONG JANG-EUI， BAE DOO-HWAN.Software modeling and analysis using a hierarchical object-oriented Petri net[J]. Information Sciences， 2000， 130（1-4）： 133-164.

[5]OSAMA S YOUNESS， WAIL S EI-KILANI， WAIEL F ABD EI-WAHEDA.A behavior and delay equivalent petri net model for performance elvaluation of communication[J]. Computer Communications， 2008， 31（10）： 2 210-2 230.

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

[7]PETRI CA. Interpretations of Net Theory[M]. Second Edition， St Augustin：Gesellehaft fur Mathematik und Datenverarbeitung Bonn，1976：8-20.

[8]袁崇义. Petri网原理与应用[M]. 北京：电子工业出版社，2005：1-15.

[9]闫哲，赵文，袁崇义，等. 基于同步网的工作流过程变动问题研究[J].电子学报，2006，34（2）：226-231.

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

[11]ZHAO WEN， HUANG YU， YUAN CHONG YI. Synchronic Distance Based Workflow Logic Specification[C]// Proceedings of the 2008 10th IEEE International Conference on High Performance Computing and Communications. Dalian： Inst. of Elec. and Elec. Eng. Computer Society， 2008： 819-824.

[12]YUAN CHONG-YI， HUANG YU， ZHAO WEN，et al. A study on fairness of place/transition systems-to make fairness fairer[J]. Transactions of the institute of measurement and control， 2011， 33（1）： 50-58.

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

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

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

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

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

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

（责任编辑：李丽）