基于延迟时间Petri网的工作流相似性度量方法
2019-07-15冯复剑
冯 复 剑
(江苏第二师范学院 江苏 南京 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提出一种新的时间约束工作流相似性度量方法。首先找出整个工作流的调度序列，并依此计算出流程的时间约束路由关系集；其次给出了时间约束路由关系的距离以及相似性定义，进而通过计算两个关系集的相似度来衡量两个流程之间的接近程度；最后通过实例对上述的方法进行了说明和应用。本文方法既考虑路由结构又考虑了时间约束，大大提高了相似性判定的准确度和合理性。
由于本文考虑的工作流拓扑结构为单触发调度，实际过程中可能存在多个触发调度的情况。下一步工作将研究当工作流存在多个触发调度时，如何判定它们的相似性。
