王麗麗　方賢文　張苗苗??

摘要：同步距離是刻畫(huà)事件之間同步關(guān)系的一個(gè)重要的定量分析手段，已經(jīng)有相關(guān)文獻(xiàn)表明它對(duì)系統(tǒng)的設(shè)計(jì)和分析提供了很大的幫助，尤其在工作流和工業(yè)生產(chǎn)控制系統(tǒng)的協(xié)調(diào)結(jié)構(gòu)設(shè)計(jì)方面有著顯著的優(yōu)勢(shì)。然而目前只有一些特殊的子網(wǎng)中變遷之間的同步距離計(jì)算有較簡(jiǎn)潔的算法，為了使得更多的網(wǎng)系統(tǒng)其同步距離計(jì)算也能夠有簡(jiǎn)潔的算法，證明了若一個(gè)網(wǎng)系統(tǒng)的行為等價(jià)與某個(gè)特殊的子網(wǎng)，那么此網(wǎng)系統(tǒng)中變遷之間的同步距離的求解就可以轉(zhuǎn)化為其行為等價(jià)的特殊子網(wǎng)的同步距離的求解問(wèn)題，并且給出了尋找其行為等價(jià)的特殊子網(wǎng)的算法， 最后進(jìn)行了相應(yīng)的實(shí)驗(yàn)驗(yàn)證。

關(guān)鍵詞：Petri網(wǎng)；同步距離；行為等價(jià)；特殊子網(wǎng)

中圖分類(lèi)號(hào)：TP3919 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1672-1098（2014）01-0019-05

Petri網(wǎng)的概念是1962年由德國(guó)科學(xué)家C.A.Petri首先提出來(lái)的，它是分布式系統(tǒng)的描述和分析工具[1]541，特別便于描述系統(tǒng)中進(jìn)度和部件的順序、并發(fā)、沖突及同步等關(guān)系，廣泛的應(yīng)用于很多實(shí)際的系統(tǒng)，如離散事件系統(tǒng)[2]，柔性制造系統(tǒng)[3]，軟件工程[4]，通信協(xié)議[5]和生物信息學(xué)[6]等系統(tǒng)。

文獻(xiàn)[7]中最先將“同步距離”的概念引入Petri網(wǎng)，它是描述兩個(gè)事件（或事件集）之間同步的一個(gè)重要的系統(tǒng)恒定性質(zhì)，反映出兩個(gè)變遷（變遷集）之間相對(duì)獨(dú)立程度，不僅可以對(duì)兩個(gè)（組）事件同步程度給出定量描述，而且也是刻畫(huà)系統(tǒng)動(dòng)態(tài)行為的工具。已經(jīng)有大量的文獻(xiàn)驗(yàn)證了同步距離對(duì)系統(tǒng)設(shè)計(jì)和分析提供了很大的幫助，譬如在工作流模型中，可以利用同步距離對(duì)工作流模型進(jìn)行分析，從而檢驗(yàn)和控制工作流程[8-14]。

由于同步距離的求解不僅和網(wǎng)的結(jié)構(gòu)特征有關(guān)系而且和網(wǎng)的初始標(biāo)識(shí)也存在關(guān)系，所以到目前為止還沒(méi)有一個(gè)很簡(jiǎn)潔易行的算法來(lái)求解一般Petri網(wǎng)的同步距離，然而一些特殊的Petri網(wǎng)子類(lèi)如出現(xiàn)網(wǎng)[15]、標(biāo)識(shí)T-圖[1]560、標(biāo)識(shí)S-圖[16]和標(biāo)識(shí)T-網(wǎng)[17]的同步距離的計(jì)算已經(jīng)有了較簡(jiǎn)潔的求解方法。本文基于此出發(fā)證明了若一個(gè)網(wǎng)系統(tǒng)的行為等價(jià)于某個(gè)特殊的子網(wǎng)，那么此網(wǎng)系統(tǒng)中變遷之間的同步距離的求解就可以轉(zhuǎn)化為其行為等價(jià)的特殊子網(wǎng)的同步距離的求解問(wèn)題，同時(shí)給出了相應(yīng)的尋找行為等價(jià)特殊子網(wǎng)的算法。

2基本概念

關(guān)于Petri網(wǎng)的基本概念和結(jié)論詳細(xì)內(nèi)容見(jiàn)文[18]，這里只對(duì)與本文有關(guān)的基本概念、結(jié)論、術(shù)語(yǔ)和記號(hào)做個(gè)簡(jiǎn)述或約定，以便后面的討論。

說(shuō)明：① 算法1中的step3表明如果庫(kù)所s1能得到標(biāo)識(shí)時(shí)，則s2一定也能夠得到標(biāo)識(shí)；但是s2得到標(biāo)識(shí)時(shí)，s1不一定能夠得到標(biāo)識(shí)，又由于M0（s1）≤M0（s2），所以此時(shí)當(dāng)s1，s2同時(shí)作為變遷t的前集時(shí)，t的引發(fā)其實(shí)主要受到s1中擁有的標(biāo)志數(shù)的影響（M0（s2）-M0（s1）個(gè)標(biāo)志對(duì)t的引發(fā)不起作用），故在step4中可以將?。╯2，t）從網(wǎng)中刪去。

② 算法1中的step5表明si對(duì)網(wǎng)中各個(gè)變遷的行為不產(chǎn)生影響，可視si為冗余庫(kù)所，因此在step6中可以將si及其關(guān)聯(lián)的弧從網(wǎng)中刪去

不難發(fā)現(xiàn)，上述算法中每個(gè)步驟均在保持原網(wǎng)行為不變的前提下進(jìn)行的，通過(guò)對(duì)網(wǎng)按照算法1步驟進(jìn)行化簡(jiǎn)我們可以得到另一個(gè)結(jié)構(gòu)更加簡(jiǎn)單且行為等價(jià)的網(wǎng)′。此時(shí)若′為一個(gè)特殊的子網(wǎng)，我們則可以將求解網(wǎng)系統(tǒng)中變遷之間的同步距離轉(zhuǎn)化為求解′中變遷之間的同步距離。

下面通過(guò)一個(gè)具體的例子來(lái)說(shuō)明如何利用算法1對(duì)已知的網(wǎng)系統(tǒng)進(jìn)行化簡(jiǎn)，然后通過(guò)判斷化簡(jiǎn)以后的網(wǎng)系統(tǒng)是否等價(jià)于某一特殊子網(wǎng)來(lái)求其變遷之間的同步距離。

通過(guò)對(duì)比可知我們求得的同步距離值和采用文獻(xiàn)[18]中方法得到的結(jié)果相同。

推論：設(shè)=（S，T；F，M0）和′=（S′，T；F′，M′0）為兩個(gè)Petri網(wǎng)，如果這兩個(gè)網(wǎng)系統(tǒng)是行為等價(jià)的，則網(wǎng)系統(tǒng)和網(wǎng)系統(tǒng)′中變遷之間的同步距離值是相等的。

證明：由于網(wǎng)和網(wǎng)′是行為等價(jià)的，故滿(mǎn)足定理1中的（1）（2）條件，又從定理1可知若兩個(gè)網(wǎng)系統(tǒng)和′滿(mǎn)足（1）（2）條件，那么對(duì)網(wǎng)Σ中ti，tj∈T

有sd（ti，tj）等于網(wǎng)1中sd（ti，tj）。

故網(wǎng)系統(tǒng)和網(wǎng)系統(tǒng)′中變遷之間的同步距離值是相等的。證畢。

5結(jié)束語(yǔ)

本文證明了一些與某個(gè)特殊子網(wǎng)行為等價(jià)的網(wǎng)系統(tǒng)的同步距離的求解可以轉(zhuǎn)化為與其行為等價(jià)的特殊子網(wǎng)的同步距離的求解。同時(shí)給出了如何尋找到一個(gè)與原網(wǎng)系系統(tǒng)行為等價(jià)且結(jié)構(gòu)更加簡(jiǎn)潔的另一個(gè)網(wǎng)系統(tǒng)的求解算法，然后通過(guò)判斷與其行為等價(jià)的網(wǎng)系統(tǒng)是否屬于某個(gè)特殊的子網(wǎng)，若是，就將此網(wǎng)的同步距離求解變換為與其行為等價(jià)的特殊子網(wǎng)同步距離的求解，最后結(jié)合實(shí)例對(duì)算法進(jìn)行了闡述。

參考文獻(xiàn)：

[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 網(wǎng)在生物信息學(xué)中的應(yīng)用[J].計(jì)算機(jī)學(xué)報(bào)，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網(wǎng)原理與應(yīng)用[M]. 北京：電子工業(yè)出版社，2005：1-15.

[9]閆哲，趙文，袁崇義，等. 基于同步網(wǎng)的工作流過(guò)程變動(dòng)問(wèn)題研究[J].電子學(xué)報(bào)，2006，34（2）：226-231.

[10]王斌， 章云， 王曉紅. 基于Petri網(wǎng)的工作流模式建模與應(yīng)用[J]. 計(jì)算機(jī)工程與應(yīng)用， 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]方歡， 陸陽(yáng)等. 混雜Petri網(wǎng)系統(tǒng)中同步距離的確定及同步控制器的設(shè)計(jì)[J]. 控制理論與應(yīng)用， 2012，29（7）： 884-892.

[14]候春龍，齊新戰(zhàn)，衛(wèi)翔.基于Petri網(wǎng)建模的互斥問(wèn)題優(yōu)化方案[J]. 系統(tǒng)仿真技術(shù)， 2012， 8（3）： 238-243.

[15]袁崇義.出現(xiàn)網(wǎng)的同步距離[J]. 應(yīng)用數(shù)學(xué)學(xué)報(bào)， 1984，7（4）：459-466.

[16]張軍明，吳哲輝. 標(biāo)識(shí)S-圖中同步距離的計(jì)算[C]//中國(guó)計(jì)算機(jī)學(xué)會(huì)PETRI網(wǎng)學(xué)術(shù)會(huì)議論文集.南京，1995：61-67.

[17]王麗麗，吳哲輝，方歡. 標(biāo)識(shí)T-網(wǎng)中同步距離的計(jì)算[J]. 計(jì)算機(jī)科學(xué)，2008，35（10）： 100-103.

[18]吳哲輝. Petri網(wǎng)導(dǎo)論[M]. 北京：機(jī)械工業(yè)出版社， 2006：285-301.

（責(zé)任編輯：李麗）

[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 網(wǎng)在生物信息學(xué)中的應(yīng)用[J].計(jì)算機(jī)學(xué)報(bào)，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網(wǎng)原理與應(yīng)用[M]. 北京：電子工業(yè)出版社，2005：1-15.

[9]閆哲，趙文，袁崇義，等. 基于同步網(wǎng)的工作流過(guò)程變動(dòng)問(wèn)題研究[J].電子學(xué)報(bào)，2006，34（2）：226-231.

[10]王斌， 章云， 王曉紅. 基于Petri網(wǎng)的工作流模式建模與應(yīng)用[J]. 計(jì)算機(jī)工程與應(yīng)用， 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]方歡， 陸陽(yáng)等. 混雜Petri網(wǎng)系統(tǒng)中同步距離的確定及同步控制器的設(shè)計(jì)[J]. 控制理論與應(yīng)用， 2012，29（7）： 884-892.

[14]候春龍，齊新戰(zhàn)，衛(wèi)翔.基于Petri網(wǎng)建模的互斥問(wèn)題優(yōu)化方案[J]. 系統(tǒng)仿真技術(shù)， 2012， 8（3）： 238-243.

[15]袁崇義.出現(xiàn)網(wǎng)的同步距離[J]. 應(yīng)用數(shù)學(xué)學(xué)報(bào)， 1984，7（4）：459-466.

[16]張軍明，吳哲輝. 標(biāo)識(shí)S-圖中同步距離的計(jì)算[C]//中國(guó)計(jì)算機(jī)學(xué)會(huì)PETRI網(wǎng)學(xué)術(shù)會(huì)議論文集.南京，1995：61-67.

[17]王麗麗，吳哲輝，方歡. 標(biāo)識(shí)T-網(wǎng)中同步距離的計(jì)算[J]. 計(jì)算機(jī)科學(xué)，2008，35（10）： 100-103.

[18]吳哲輝. Petri網(wǎng)導(dǎo)論[M]. 北京：機(jī)械工業(yè)出版社， 2006：285-301.

（責(zé)任編輯：李麗）

[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 網(wǎng)在生物信息學(xué)中的應(yīng)用[J].計(jì)算機(jī)學(xué)報(bào)，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網(wǎng)原理與應(yīng)用[M]. 北京：電子工業(yè)出版社，2005：1-15.

[9]閆哲，趙文，袁崇義，等. 基于同步網(wǎng)的工作流過(guò)程變動(dòng)問(wèn)題研究[J].電子學(xué)報(bào)，2006，34（2）：226-231.

[10]王斌， 章云， 王曉紅. 基于Petri網(wǎng)的工作流模式建模與應(yīng)用[J]. 計(jì)算機(jī)工程與應(yīng)用， 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]方歡， 陸陽(yáng)等. 混雜Petri網(wǎng)系統(tǒng)中同步距離的確定及同步控制器的設(shè)計(jì)[J]. 控制理論與應(yīng)用， 2012，29（7）： 884-892.

[14]候春龍，齊新戰(zhàn)，衛(wèi)翔.基于Petri網(wǎng)建模的互斥問(wèn)題優(yōu)化方案[J]. 系統(tǒng)仿真技術(shù)， 2012， 8（3）： 238-243.

[15]袁崇義.出現(xiàn)網(wǎng)的同步距離[J]. 應(yīng)用數(shù)學(xué)學(xué)報(bào)， 1984，7（4）：459-466.

[16]張軍明，吳哲輝. 標(biāo)識(shí)S-圖中同步距離的計(jì)算[C]//中國(guó)計(jì)算機(jī)學(xué)會(huì)PETRI網(wǎng)學(xué)術(shù)會(huì)議論文集.南京，1995：61-67.

[17]王麗麗，吳哲輝，方歡. 標(biāo)識(shí)T-網(wǎng)中同步距離的計(jì)算[J]. 計(jì)算機(jī)科學(xué)，2008，35（10）： 100-103.

[18]吳哲輝. Petri網(wǎng)導(dǎo)論[M]. 北京：機(jī)械工業(yè)出版社， 2006：285-301.

（責(zé)任編輯：李麗）