王麗麗，方賢文，方 歡，蔡瑞文

安徽理工大學(xué) 理學(xué)院，安徽 淮南 232001

P/T_網(wǎng)中的同步距離

王麗麗，方賢文，方 歡，蔡瑞文

安徽理工大學(xué) 理學(xué)院，安徽 淮南 232001

1 引言

Petri網(wǎng)作為描述異步并發(fā)現(xiàn)象的系統(tǒng)模型在許多領(lǐng)域得到廣泛應(yīng)用[1-4]，尤其在并發(fā)系統(tǒng)中顯示出獨特的優(yōu)越性。然而有些系統(tǒng)中經(jīng)常會遇到一些信息的同步問題，為了對這些同步問題進(jìn)行定量的分析，C.A.Petri最先在文獻(xiàn)[5]中將“同步距離”的概念引入到Petri網(wǎng)中。同步距離不僅可以對實際系統(tǒng)中任意兩組事件之間的同步程度進(jìn)行定量的描述，還可以作為刻畫系統(tǒng)行為的工具，大量文獻(xiàn)已經(jīng)證明其對系統(tǒng)的分析、建模和優(yōu)化提供一定的幫助，尤其在工作流領(lǐng)域應(yīng)用最廣泛[6-12]。

由于同步距離求解不僅和網(wǎng)的結(jié)構(gòu)特征有聯(lián)系而且和網(wǎng)的初始標(biāo)識也存在聯(lián)系，這無疑給同步距離的計算帶來了一定的難度。目前只有一些Petri網(wǎng)子類如出現(xiàn)網(wǎng)[13]、標(biāo)識 T-圖[14]、標(biāo)識 S-圖[15]和標(biāo)識 T-網(wǎng)[16]中同步距離求解已經(jīng)有了較簡潔的計算方法，而對于Petri網(wǎng)中同步距離的計算仍是一個難題。文獻(xiàn)[17]采用觀察庫所來求解Petri網(wǎng)中同步距離，但是它只適用于那種不包含變遷出現(xiàn)次數(shù)不等的循環(huán)進(jìn)程段。

本文討論了P/T_網(wǎng)中任意兩個變遷子集之間的同步距離計算，對于處于同一個公平分支的變遷子集通過采用文獻(xiàn)[18]中帶權(quán)觀察庫所的原理來求解它們之間的同步距離值，在此基礎(chǔ)上進(jìn)一步討論了如何給P/T_網(wǎng)中連接變遷和帶權(quán)觀察庫所之間的弧配置一個確定的權(quán)值，從而得到一個帶權(quán)的同步觀察P/T_系統(tǒng)；為了保證原網(wǎng)系統(tǒng)的動態(tài)行為不變，假定觀察庫所中已經(jīng)配置了足夠多的tokens數(shù)，通過模擬原網(wǎng)系統(tǒng)的可覆蓋樹可以得到觀察庫所擁有的最大tokens數(shù)和最小tokens數(shù)，然后通過計算其差值得到變遷之間的同步距離值，并給出相應(yīng)的求解算法。

2 基本概念

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

關(guān)于帶權(quán)觀察庫所的求解原理請參見文獻(xiàn)[18]，這里不再贅述。

定義1[19]設(shè) Σ=(S，T;F，M0)和 Σ′(S′，T;F′，M′0)為兩個Petri網(wǎng)，如果存在滿射 f: R(M′0)→R(M0)使得：

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

（2）若 f(M′)=M 則對 ?σ∈T*:在 Σ′中有 M′[σ＞當(dāng)且僅當(dāng)在Σ中有M[σ＞，則稱Σ′和Σ是行為等價的。

為了避免觀察庫所中擁有的標(biāo)識數(shù)隨著循環(huán)進(jìn)程段循環(huán)次數(shù)的增加而無限制增加，從而導(dǎo)致不能精確地求解同步距離值，本文采用加權(quán)同步距離的概念，通過給帶權(quán)觀察庫所和變遷之間的弧引入權(quán)值來解決此問題。

定義2[19]設(shè) Σ=(S，T;F，M0)為一個Petri網(wǎng)，t1，t2∈T，那么t1和t2之間的加權(quán)同步距離 sd12由下面公式給出：

其中r是Σ的一個本原可重復(fù)向量，且r(t1)≠0，r(t2)≠0。

關(guān)于一個網(wǎng)N的本原可重復(fù)向量的定義和求解算法詳見文獻(xiàn)[20]，此文不再贅述。

定義3設(shè)N=(S，T;F)為一個網(wǎng)，記N的本原可重復(fù)向量集合為 SPRVN，若 ?X∈SPRVN都有 X(ti)＞0，X(tj)＞0或 X(ti)=0，X(tj)=0 （X(ti)表示變遷ti在向量X中對應(yīng)的分量），那么稱滿足 X(ti)＞0，X(tj)＞0 的本原可重復(fù)向量 X為覆蓋變遷ti和tj本原可重復(fù)向量，所有覆蓋ti和tj本原可重復(fù)向量組成的集合記為SPRVij。

從定義3可知若T1是網(wǎng)N的變遷子集，且T1中變遷屬于同一個公平分支，?X∈SPRVN對于?t∈T1要么都滿足 X(t)＞0，要么都滿足 X(t)=0，稱滿足 X(t)＞0的本原可重復(fù)向量X為覆蓋變遷子集T1的本原可重復(fù)向量，所有覆蓋變遷子集T1本原可重復(fù)向量組成的集合記為 SPRVT1。

從上述的定理1中可知：若兩個變遷處于公平關(guān)系，那么覆蓋它們的本原可重復(fù)向量對應(yīng)的分量一定成比例。

從定理1易求出網(wǎng)系統(tǒng)的公平分支，具體方法文獻(xiàn)[22]也有提及，這里不再敘述。

定義4設(shè) N=(S，T;F)為一個網(wǎng)，T1，T2是網(wǎng) N 的兩個變遷子集，T1≠?，T2≠?，T1∩T2=? 且T1與 T2處于同一個公平分支，帶權(quán)觀察庫所 p滿足·p=T1，p·=T2，稱滿足下列條件的權(quán)函數(shù)為本原權(quán)函數(shù)：

（1）若 T1，T2中均只含有一個變遷，設(shè) T1=ti，T2=tj

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

（2）若T1，T2中含有兩個及以上變遷

①若存在本原可重復(fù)向量 X 使得?ti∈T1，?tj∈T2，有 X(ti)≠0，X(tj)≠0，記覆蓋 T1和T2本原可重復(fù)向量集合為SPRVT1T2，X∈SPRVT1T2，設(shè)T1中變遷對應(yīng) X向量中分量的最小公倍數(shù)為k1，T2中變遷對應(yīng) X向量中分量的最小公倍數(shù)為 k2，對于 ?ti∈ T1，?tj∈ T2，有 w(ti，p)=k2，w(p，tj)=k1。

②若不存在本原可重復(fù)向量X使得?ti∈T1，?tj∈T2，有 X(ti)≠0，X(tj)≠0，對于 ?ti∈T1，?tj∈T2，則 w(ti，p)= w(p，tj)=1。

由于處于不同公平分支中變遷子集之間的同步距離為∞，所以定義4只討論處于同一個公平分支中變遷子集和帶權(quán)觀察庫所之間連接弧的權(quán)值配置。為了使得帶權(quán)觀察庫所中擁有的tokens數(shù)不受存在發(fā)生次數(shù)不等的循環(huán)進(jìn)程段的循環(huán)次數(shù)的影響，需要給帶權(quán)觀察庫所與變遷之間的弧配置一個權(quán)值w，且其滿足本原權(quán)函數(shù)的兩個條件。

定義5設(shè) Σ=(S，T;F，M0)是一個Petri網(wǎng)，R(M0)是網(wǎng)Σ的可達(dá)標(biāo)識集，T1，T2是網(wǎng)N的兩個變遷子集，T1≠?，T2≠?，T1∩T2=?且T1與T2處于同一個公平分支，p為變遷子集T1和T2之間的帶權(quán)觀察庫所，稱 Σs= (S∪p，T;F∪F′，K，W，Ms0)是 Σ 的帶權(quán)同步觀察P/T_系統(tǒng)，若滿足：

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

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

（3）W:F′→{1，2，3，…}且W是本原權(quán)函數(shù)且K(p)=∞。

（4）Ms0=M0?M0(p)，其中 M0(p)=h（h 是足夠大的正整數(shù)）是 s12的初始標(biāo)識，滿足 ?σ∈T*:M0[σ＞→Ms0[σ＞ 。

定理2[18]設(shè) Σ=(S，T;F，M0)是一個 P/T_網(wǎng)，Σs= (S∪p，T;F∪F′，K，W，Ms0)是 Σ 的帶權(quán)同步觀察P/T_系統(tǒng)，R(Ms0)是 Σs的可達(dá)標(biāo)識集，T1，T2是網(wǎng) N的兩個變遷子集，T1≠?，T2≠?，T1∩T2=? 且T1與 T2處于同一個公平分支，T1和T2之間的同步距離sd(T1，T2)可以通過下式計算：

3 處于同一個公平分支中變遷子集T1和T2之間同步距離求解

下面討論如何利用觀察庫所來求解處于同一個公平分支中變遷子集T1和T2之間同步距離求解。

由于帶權(quán)觀察庫所不屬于網(wǎng)系統(tǒng)的一部分，只起到計數(shù)的作用，為了不影響原網(wǎng)系統(tǒng)的動態(tài)行為，假定帶權(quán)觀察庫所 p的初始標(biāo)識為h（其中h是足夠大的正整數(shù)）。

采用帶權(quán)觀察庫所的原理來求解P/T_網(wǎng)中處于同一個公平分支中兩個變遷子集T1和T2同步距離時，由于帶權(quán)觀察庫所中擁有的最大或最小tokens數(shù)和T1和T2中變遷的發(fā)生次數(shù)存在直接的關(guān)系，又因為網(wǎng)系統(tǒng)的可覆蓋樹能夠很直觀地顯示每個變遷的可能發(fā)生次數(shù)，所以本文通過模擬可覆蓋樹的動態(tài)行為來計算變遷子集之間的同步距離值。

算法1變遷子集T1和T2之間的同步距離計算算法

輸入擁有初始標(biāo)識的帶權(quán)同步觀察P/T_系統(tǒng)Σs= (S∪p，T;F∪F′，K，W，Ms0)

輸出變遷子集T1和T2的同步距離值sd(T1，T2)

步驟1Max(p)=Min(p)=h（h是帶權(quán)觀察庫所 p初始tokens數(shù)）

步驟2R(Ms0)={Ms0}且Ms0作為根結(jié)點，標(biāo)記為“新”

步驟3WhileR(Ms0)存在標(biāo)記為“新”的標(biāo)識 do任選一個標(biāo)記為“新”的標(biāo)識，設(shè)為Ms

步驟4If從 Ms0到 Ms的路上存在一個標(biāo)識 M′s滿足 ?s∈S且s≠p，M′s(s)=Ms(s)then將Ms的標(biāo)記改為“舊”，返回到步驟3

步驟5If ?t∈T:﹁Ms[t＞ then將Ms的標(biāo)注改為“舊”，返回到步驟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為原網(wǎng)系統(tǒng)中庫所總個數(shù)，將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畫一條有向弧，并把此弧旁標(biāo)以ti，擦去結(jié)點Ms的“新”標(biāo)注，并將結(jié)點 M′s添加“新”標(biāo)注，返回到步驟3

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

4 P/T_網(wǎng)中任意兩個變遷之間同步距離的求解

算法思想：當(dāng)網(wǎng)系統(tǒng)Σ不存在本原可重復(fù)向量時，顯然任意兩個變遷子集T1和T2都處于公平關(guān)系，此時利用算法1來求解同步距離。當(dāng)網(wǎng)系統(tǒng)Σ存在本原可重復(fù)向量時，要分類考察變遷子集T1和T2之間的關(guān)系，根據(jù)它們處于同一個公平分支還是處于不同的公平分支分別求解它們之間的同步距離。只有處于同一個公平分支的變遷子集，才需利用算法1進(jìn)行求解。具體算法描述如下所示。

算法2求解P/T_網(wǎng)中任意兩個變遷子集之間的同步距離算法

輸入P/T_網(wǎng) Σ=(S，T;F，M0)以及 T1，T2為網(wǎng)系統(tǒng)的變遷子集

輸出T1和T2之間的同步距離sd(T1，T2)

步驟1求網(wǎng)Σ=(S，T;F)的所有本原可重復(fù)向量

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

步驟3If存在本原可重復(fù)向量，記為SPRVN={X1，X2，…，Xk}，then

步驟4If ?Xi∈SPRVN，T1，T2?‖Xi‖（說明 T1，T2均不屬于部分可重復(fù)網(wǎng)）then采用算法1求sd(T1，T2)

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

步驟6else求出覆蓋T1和T2的本原可重復(fù)向量SPRVT1T2

步驟 7If ?Xi，Xj∈ SPRVT1T2滿足?ti∈ T1，?tj∈ T2使得

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

下面通過一個實例來演示算法1和算法2步驟。

例1圖1為一個P/T_網(wǎng)，此網(wǎng)存在三個公平分支為{t1}，{t2}，{t3，t4}下面分別來求 sd(t1，t2)，sd(t1，t3)，sd(t3，t4)。

圖1 P/T_網(wǎng) Σ1

易知此網(wǎng)存在兩個本原可重復(fù)向量X(1)=[1 1 0 0]，X(2)=[1 2 1 1]，由算法2中的步驟5可知，sd(t1，t3)=∞，又由算法2中的步驟7可知，t1與t2處于非公平關(guān)系，所以 sd(t1，t2)=∞。從算法2中的步驟8可知，t3與t4處于公平關(guān)系，接下來著重討論如何利用算法1來求t3和t4之間的同步距離。

根據(jù)帶權(quán)同步觀察P/T_系統(tǒng)的構(gòu)造定義可知ω(t3，s34)=ω(s34，t4)=1，利用算法1構(gòu)造出帶權(quán)的同步觀察P/T_系統(tǒng)的可覆蓋樹如圖2所示，在構(gòu)造過程中可以得到Max(s34)=h+1，Min(s34)=h，故變遷t3和t4之間的同步距離為 sd(t3，t4)=Max(s34)-Min(s34)=1。

5 結(jié)束語

圖2 帶權(quán)同步觀察P/T_系統(tǒng)的可覆蓋樹

文中討論了如何利用觀察庫所來求解P/T_網(wǎng)中任意兩個變遷子集之間的同步距離，并給出相應(yīng)的計算算法。算法首先根據(jù)本原可重復(fù)向量來判斷某兩個變遷子集是否處于同一個公平關(guān)系，對于處于兩個不同的公平分支中的變遷子集無需給它們配置加權(quán)觀察庫所就可直接得出它們的同步距離值為無窮大，對于處于同一個公平分支的變遷變遷子集，為了使得同步距離不因變遷在循環(huán)進(jìn)程段中出現(xiàn)次數(shù)不等而導(dǎo)致觀察庫所中擁有的標(biāo)識數(shù)隨著循環(huán)次數(shù)無限制的增加，需要給帶權(quán)觀察庫所和變遷之間引入本原權(quán)函數(shù)，從而得到一個帶權(quán)同步觀察P/T_系統(tǒng)。通過模擬原網(wǎng)系統(tǒng)的可覆蓋樹可以得到帶權(quán)觀察庫所在系統(tǒng)運行過程中擁有的最大和最小tokens數(shù)，從而得到變遷之間的同步距離值，并給出了相應(yīng)算法。

本文的同步距離計算算法采用模擬可覆蓋樹來求處于同一個公平分支變遷子集之間的同步距離值，所以此算法的復(fù)雜度和可覆蓋樹的復(fù)雜度是同級別，考慮如何降低算法的復(fù)雜度是下一步有待研究的問題。

[1]何炎祥，沈華.一種基于隨機(jī)Petri網(wǎng)的Web服務(wù)組合性能瓶頸定位策略[J].計算機(jī)學(xué)報，2013，36（10）：1953-1966.

[2]黃翔，陳志剛.資源敏感的分布式系統(tǒng)性能建模方法[J].計算機(jī)科學(xué)，2013，40（9）：174-180.

[3]劉永磊，金志剛.無限局域網(wǎng)WPS安全性分析[J].計算機(jī)工程與應(yīng)用，2013，49（21）：87-89.

[4]林闖，楊宏坤，單志廣.Petri網(wǎng)在生物信息學(xué)中的應(yīng)用[J].計算機(jī)學(xué)報，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網(wǎng)原理與應(yīng)用[M].北京：電子工業(yè)出版社，2005. [8]閆哲，趙文，袁崇義，等.基于同步網(wǎng)的工作流過程變動問題研究[J].電子學(xué)報，2006，34（2）：226-231.

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

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

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

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

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

[17]張金泉，倪麗娜，蔣昌俊.Petri網(wǎng)的同步距離計算[J].計算機(jī)科學(xué)，2005，32（12）：138-141.

[18]袁崇義.Petri網(wǎng)應(yīng)用[M].北京：科學(xué)出版社，2013.

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

[20]岳昊，吳哲輝，劉關(guān)俊.Petri網(wǎng)本原可重復(fù)向量的求解算法及實現(xiàn)[J].小型微型計算機(jī)系統(tǒng)，2009，30（9）：1815-1818.

[21]王麗麗，吳哲輝，方賢文，等.關(guān)于Petri網(wǎng)中同步距離定義的研究[J].合肥工業(yè)大學(xué)學(xué)報：自然科學(xué)版，2013，36（3）：303-308.

[22]吳哲輝，郭玉彬.Petri網(wǎng)中亞公平關(guān)系與亞公平網(wǎng)[J].山東科學(xué)技術(shù)大學(xué)學(xué)報：自然科學(xué)版，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

同步距離既可以對兩組事件之間同步程度進(jìn)行定量分析，也可以刻畫系統(tǒng)動態(tài)行為，然而Petri中同步距離計算一直存在難題。采用加權(quán)觀察庫所的原理討論了P/T_網(wǎng)中任意兩個變遷子集之間同步距離的計算，并通過本原權(quán)函數(shù)的定義指出了如何給連接變遷和加權(quán)觀察庫所之間的弧配置一個唯一的權(quán)值。為了得到處于同一個公平分支變遷子集之間的同步距離值，需構(gòu)造一個帶權(quán)同步觀察P/T_系統(tǒng)，通過模擬原網(wǎng)系統(tǒng)的可覆蓋樹得到帶權(quán)觀察庫所的最大和最小tokens，從而求得變遷子集之間的同步距離值，并給出相應(yīng)算法，給出了求解P/T_網(wǎng)中任意兩個變遷子集之間同步距離計算算法。

P/T_網(wǎng)；公平分支；帶權(quán)觀察庫所；帶權(quán)同步觀察P/T_系統(tǒng)；本原權(quán)函數(shù)；同步距離

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.

國家自然科學(xué)基金（No.61272153，No.61170059，No.61340003）；安徽省高校自然科學(xué)基金重點項目（No.KJ2011A086）；安徽省自然科學(xué)基金（No.1208085MF105）；安徽省軟科學(xué)研究計劃項目（No.12020503031）；安徽理工大學(xué)青年教師科學(xué)研究基金（No.2012QNY36）。

王麗麗（1983—），女，講師，研究領(lǐng)域為Petri網(wǎng)理論與應(yīng)用、算法設(shè)計與研究；方賢文（1974—），男，博士，教授，研究領(lǐng)域為Petri網(wǎng)理論與應(yīng)用、可信軟件以及Web服務(wù)等。E-mail：wanglili198301@163.com

2014-02-17

2014-05-07

1002-8331（2014）23-0047-04

CNKI網(wǎng)絡(luò)優(yōu)先出版：2014-07-11,http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1402-0115.html