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