基于延遲時間Petri網的工作流相似性度量方法

馮 復 劍

(江蘇第二師范學院 江蘇 南京 210013)

0 引 言

流程相似性度量旨在明確流程之間的接近程度，相似性越高表示流程功能越接近，反之越遠。其被廣泛應用于流程的檢索、合并、重組以及推薦等。流程相似性的研究一直是個熱點。目前，主流算法[1-14]主要基于以下三個方面[15]來衡量流程是否相似：(1) 任務、事件的標簽或其他模型元素；(2) 流程模型的拓撲結構；(3) 流程模型的執行語義。目前常用的相似性算法包括變遷緊鄰關系算法[9](Transition Adjacency Relations，TAR)、標簽無關變遷緊鄰關系算法[10](Label-free Transition Adjacency Relations，Label-free TAR)。TAR算法使用兩個模型的TAR集合Jaccard系數來表征其相似性，該算法依賴于變遷的標簽；Label-free TAR算法改善了TAR算法的不足，著重考慮流程的控制結構而忽略標簽的不同。

實時系統中，流程或者任務往往具有時間約束，其相似性的判定不僅僅需要從以上三個方面考慮，還需要將時間約束納入其中。普通工作流和時間約束工作流各自的相似性度量具有很大的不同。如圖1所示的兩個時間Petri網片段，在不考慮時間約束的情況下，使用Label-free TAR算法易知(a)、(b)是等價的。實際上，由于時間約束，(a) 中只有變遷t1將有機會被執行，而(b) 中變遷t1、t2都有機會完成觸發。因此，兩者的行為并不等價。

現有的關于時間約束工作流相似性的研究成果相對較少。文獻[16]采用Timed WF-net對云工作流進行建模，通過構建帶時間約束的任務執行次序關系索引對大規模云工作流模型庫進行過濾，進而依據執行次序關系的匹值來判斷候選集合查詢集的匹配度。該方法只適用于WF-nets，對模型的拓撲結構要求過于嚴格，且存在一些不足。以文獻[16]中例6為例進行說明。查詢模型q的關系集為：(“B”,“C”,“→”,[2,3]),(“B”,“D”,“→”,[2,4])，(“C”,“D”,“‖”)，需要從圖2所示的候選模型庫中找出相似度最高的模型。根據文獻[16]中的式(8)，可以得到：BMD(TN1,q)=BMD(TN2,q)=BMD(TN3,q)=1，可認為候選庫都是滿足查詢模型q的檢索結果。顯然，TN1、TN2、TN3并不相同，相似性匹配得到的結果不合理。造成此不合理性的原因在于滿足執行次序關系的拓撲結構以及時間約束可以有多種。文獻[17]對timed-arc Petri nets的相似性進行研究，通過簡化時間可達圖來比較流程的相似性。這種方法的主要缺點是狀態空間爆炸，因為MLTAPN通常具有大量的狀態。

圖2 候選模型庫

本文采用DTPN建模時間約束工作流，首先找出網的觸發序列，然后根據觸發調度求得其時間約束路由關系集，最后通過比較路由關系集的距離來判斷流程之間的相似性。

1 預備知識

為了更好地理解本文，下面將給出一些與本文研究相關的預備知識。

1.1 DTPN定義

DTPN中庫所和變遷之間的有向弧上添加了靜態的時間間隔。輸入庫所中的托肯到達后不能立即用于使能其輸出變遷，相應的變遷觸發后托肯也不能立刻到達其輸出庫所。

定義1[18-19]DTPN是一個七元組(P,T,F,W,M0,SIM,SIF)，其中：

?P、T、F、W、M0為普通Petri網；

?SIM：T→Q×(Q∪+∞)為變遷靜態觸發間隔映射，Q為非負有理數集合；

?P、T、F、W、M0、SIM共同組成TPN；

?SIF：F→Q×(Q∪+∞)為弧靜態延遲間隔映射，Q為非負有理數集合。

圖3為一個DTPN片段，圖中數字單位為時間單元，如天、小時等。

圖3 一個DTPN片段

1.2 DTPN觸發調度

定義2[20-21]觸發序列t1，t2，…，tn中，變遷ti的觸發時刻稱作ith觸發點；變量xi表示(i-1)th和ith兩觸發點之間所消逝的時間。

假設圖4中初始時刻為τ0=0，則x1是變遷t1的觸發時刻，(x1+x2)是變遷t2的觸發時刻，(x2+x3)為變遷t3、t1各自觸發點之間的時間距離。

圖4 觸發點

為了敘述簡單，定義網的初始時刻τ0取值為0。

考慮拓撲結構的DTPN觸發調度的計算可參考文獻[22]。

2 DTPN相似性

本節利用觸發調度來計算兩個DTPN之間的距離，進而判定它們之間的相似度。判定兩個DTPN是否相似，即以一個DTPN作為目標對象，另一個作為比較對象，衡量它們之間的接近程度。兩者越接近，則越相似。Δ(Δ′)表示目標DTPN(待比較DTPN)，?(?′)是各自網的觸發調度。

2.1 時間約束路由關系相似度

Petri網中任意兩個變遷ti和tj之間的路由關系RC(ti,tj)=(ti,tj,rc)，可以是以下三種關系中的一種：

(1) 順序路由：活動tj是可以被執行的當且僅當活動ti被完成，記作(ti,tj,?)；

(2) 并行路由：活動ti、tj需要被執行，但是執行的順序是任意的，即可以同時也可以任意順序，記作(ti,tj,&&)；

(3) 條件路由：活動ti、tj每次只有一個是可以被執行的，其依賴于工作流屬性、環境行為等因素，記作(ti,tj,‖)。

需要指出的是，以上路由關系針對的是非嵌套拓撲結構。

考慮變遷觸發時間屬性，DTPN網中兩個變遷ti和tj帶有時間約束的路由關系TCRC(ti,tj)=(ti,tj,rc,ft(i),ft(j))，rc∈(?,&&,‖)，ft(k)是變遷tk的觸發時刻。給定一個DTPN，根據其觸發調度可求得時間約束路由關系矩陣RCM，RCM中所有非空的元素組成了DTPN的時間約束路由關系集R。

(1)

(2)

定義4(時間約束路由關系距離)：假定TCRC(ti,tj)、TCRC(ti,tj)′分別是Δ、Δ′的時間約束路由關系，兩者之間的距離定義為RCDist(TCRC(ti,tj),TCRC(ti,tj)′)，其計算公式為：

RCDist(TCRC(ti,tj),TCRC(ti,tj)′)=

(3)

定義5(時間約束路由關系相似度)：給定Δ、Δ′的兩條對應時間約束路由關系TCRC(ti,tj),TCRC(ti,tj)′，兩者之間的相似程度定義為RCSim，其計算公式為：

RCSim(TCRC(ti,tj),TCRC(ti,tj)′)=

(4)

為了更好地理解時間約束路由關系相似度的描述，下面給出一個實例：

例1：圖5(a)、(b)分別為目標、待比較DTPN，判定它們之間某一對應時間約束路由關系的相似性。根據文獻[22]的內容，可求得各自的觸發調度為：?=((t1,2),(t2,6))，?′=((t1,2),(t2,6))。因此，對應的時間約束路由關系為TCRC(t1,t2)=(t1,t2,&&,2,6)，TCRC(t1,t2)′=(t1,t2,?,2,6)。代入式可以求得RCSim=0，可判定兩者無任何相似性。

圖5 DTPN模型

給定一個DTPN，可求得其時間約束路由關系集合。兩個關系集合的接近程度則衡量了兩個網的相似度。記目標、待比較時間約束路由關系集合分別為R、R′，|R|表示關系集合的大小。則Δ、Δ′之間的相似度為sim(Δ,Δ′)，其具體計算公式為：

(5)

2.2 DTPN相似性判定方法

兩個DTPN的相似性判定流程分為三步：(1) 計算觸發調度；(2) 求得時間約束路由關系集合；(3) 計算相似度。實現方法如算法1所示。

算法1 DTPN相似性判定算法

輸入：Δ、Δ′

輸出：sim(Δ,Δ′)

Begin

1. 計算Δ、Δ′的觸發調度?、?′；

2. 根據觸發調度計算Δ、Δ′的時間約束路由關系集合R、R′；

3. if(|R′|≥|R|)

4. {

5. for eachTCRC∈Rdo

6. {

7. for eachTCRC∈R′ do

8. {

10. }

11. };

12. }

13. else

14. {

15. sim(Δ,Δ′)=0;

16. }

17. return sim(Δ,Δ′)；

End

假設|R|=n,|R′|=m，則算法1的時間復雜度為O(n×m)。

3 實 驗

本節對前文所提出的方法進行實驗驗證。現需要將校園二級域名申請流程實現網上在線辦理，其業務過程如圖6(a)所示，采用DTPN建模后的模型如圖6(b)所示，時間約束單位為天。約定未標注的有向弧上的時間約束為[0,0]。通過網絡篩選，得出功能相似的待選模型庫并將其轉換成DTPN模型，如圖7所示。通過以下步驟確定待選庫中哪條流程與目標流程相似度更高。

圖6 校園二級域名申請流程

(a) (b) (c) (d)圖7 候選模型庫

(1) 觸發調度。

(2) 時間約束路由關系集。

根據觸發調度可求得時間約束路由關系集分別為：

(3) 相似性。

通過式(5)，分別計算DTPN0與DTPN1、DTPN2之間的相似度。可得到：sim(DTPN0,DTPN1)≈0.62，sim(DTPN0,DTPN2)=0.5。因此，DTPN1更接近DTPN0。

4 結 語

針對實時系統等具有時間約束屬性的業務流程相似性問題，本文基于DTPN提出一種新的時間約束工作流相似性度量方法。首先找出整個工作流的調度序列，并依此計算出流程的時間約束路由關系集；其次給出了時間約束路由關系的距離以及相似性定義，進而通過計算兩個關系集的相似度來衡量兩個流程之間的接近程度；最后通過實例對上述的方法進行了說明和應用。本文方法既考慮路由結構又考慮了時間約束，大大提高了相似性判定的準確度和合理性。

由于本文考慮的工作流拓撲結構為單觸發調度，實際過程中可能存在多個觸發調度的情況。下一步工作將研究當工作流存在多個觸發調度時，如何判定它們的相似性。