随着全球经济化的发展和企业信息化程度的不断提高, 企业的经营模式发生了重大的变化, 企业的业务活动已从企业内单目标为导向的独立发展模式发展成为跨企业多目标合作的协同模式^[1].在现代商业环境下, 没有一个企业是孤立的^{[2, 3]}.企业作为参与者参与到协作中, 在协作过程中, 它们彼此进行交互以完成特定业务功能.近年来, 随着Internet成为主流的计算平台, 尤其是面向服务计算(service-oriented computing, 简称SOC)的快速兴起, 使得不同组织业务过程间的交互成为可能, 如企业信息系统^[4]、电子商务^[5]等.为实现共同的商业目标, 每个组织的业务过程通常需要跨越组织边界, 与其他组织的业务过程进行交互和协作以形成相对稳定的过程视图.学术界和工业界称这种存在复杂交互关系的业务过程为协同业务过程^[6].

针对协同业务过程, 国内外研究者提出多种建模方法.归纳起来, 这些建模方法可分为两类:(1)自顶向下建模方法^{[7, 8]}.该方法要求首先给出协同全局契约, 然后定义映射规则并以此为基础从契约中生成每个组织的业务过程; (2)自底向上建模方法^[9].该方法允许组织独立地定义各自的业务过程, 之后以此为基础直接构建具有协同功效的协同业务过程.由于受限于映射规则集, 利用自顶向下建模方法通常仅能建立具有有限结构形态业务过程, 灵活性和普适性不足^{[7, 8]}.因此, 本文关注自底向上建模方法.

然而, 自底向上建模方法中的业务过程由不同组织开发, 无法在设计阶段就预见其潜在的所有交互可能, 因此在实际协作中, 参与协作的业务过程间可能存在不一致(如死锁等), 无法保证协同业务过程正确地实施.因此, 对协同业务过程的正确性(正确性可根据实际需要定义, 如合理性等, 在此不作区分)进行分析是当前业务过程管理(business process management, 简称BPM)领域内的研究热点.

针对协同业务过程正确性分析, 国内外学者做了大量工作^{[9, 10]}.这些研究工作主要围绕正确性检测方法开展.该方法先构建形式化的协同业务过程并定义正确性约束(如无死锁、无活锁及未指定接收等), 然后采用某种形式的验证技术(如模型检测等)在协同业务过程中检测相容性是否满足.正确性检测方法通常具有检测过程自动化, 不需要人工干预, 且在检测失败时能够给出诊断信息, 便于业务设计人员发现并修正错误.但其不足是, 若协同业务过程中存在多处不正确, 则需要经过多次检测, 且在每次检测后都需要对协同业务过程重新调整.重复地进行检测及调整使得协同业务过程正确性分析复杂且耗时.

一种替代方法是正确性修正方法.该方法关注早期设计阶段, 根据正确性约束对业务过程内部结构进行修改以自动构建满足正确性约束的业务过程^{[11, 12]}.这方面的研究工作较少, 且大多关注组织内单个业务过程, 能够用于协同业务过程正确性修正方法^[13-15]也存在如下不足:(1)修正后的协同业务过程是集中式的, 与协同业务过程的实际特征(如自治、分布及面向流程协作等)^[16]不符; (2)这些方法基于过程挖掘技术^[17]而提出, 不能够保证修正协同业务过程中含有修正前协同业务过程中的所有完整轨迹(即完整的简单路径对应活动执行序列), 还可能引入隐藏轨迹(即不属于修正前协同业务过程中的其他轨迹), 这需要进行额外确认; (3)协同业务过程实质上是由多个业务过程构成的并发交互系统, 复杂程度高^[16].直接利用这些方法对其进行修正存在修正效率低下的问题.例如, 我们课题组最近的工作^[13]即结合Petri网和过程挖掘的相关理论, 提出了一种针对协同业务过程修正方法.但是, 该方法构建的协同业务过程存在中心流程(即只能通过该中心流程协调原有业务过程执行).同时, 修正协同业务过程与修正前协同业务过程中含有的所有完整轨迹也可能不一致, 且存在执行失败的情况.这在后文的实验部分将给出详细阐述.

针对上述问题, 本文采用标号迁移系统LTS(labeled transition system)来描述业务过程, 并将其并发组合建模协同业务过程.在考虑活动同步及异步交互的情况下, 通过将协同业务过程的行为抽象为简单路径, 在此基础上, 提出了针对部分正确的协同业务过程修正方法.该修正方法能够确保修正协同业务过程与修正前的协同业务过程中含有的轨迹相一致, 且修正协同业务过程具有自治、分布及面向流程组合等特性.

本文主要贡献如下:

(1) 在考虑活动同步及异步交互的情况下, 提出了简单路径用来刻画协同业务过程的行为, 并提出将完整的简单路径合并为核的算法.本质上, 核中包含了修正前的协同业务过程中所有正确的任务执行系列(即完整轨迹).以核为基础, 提出了将其映射为修正业务过程的方法, 将所有的修正业务过程并发组合建立修正的协同业务过程;

(2) 理论上证明了修正协同业务过程与修正前协同业务过程中含有的轨迹是一致的, 从而避免了额外确认, 降低了修正代价;

(3) 通过实验分析得出:相对已有方法, 在考虑协同业务过程实际特征(如自治、分布及面向流程组合等)的情况下, 本文方法可实现更加有效的正确性修正并能够极大地提高修正效率, 缩短修正时间.

本文第1节给出方法概览.第2节给出协同业务过程定义.第3节对正确性进行分析.第4节对正确性修正方法进行讨论.第5节通过实验对本文方法的有效性及效率进行评估.第6节为相关工作.第7节为全文总结.

1 方法概述

本文正确性修正方法提出是建立在如下一种事实, 即采用自底向上建模方法在建立协同业务过程中无法预见其所有潜在的交互可能, 从而导致建立模型中可能存在异常(如死锁等), 这将严重地阻碍业务过程间的正确协作.本文提出的正确性修正方法框架如图 1所示.

具体地, 该正确性修正方法由如下两个阶段组成.

(1) 建模阶段.参与组织首先独立地采用LTS建模各自业务过程, 并将这些业务过程并发组合建立协同业务过程; 之后参与组织间经协商, 确定期望的系统正确性, 本文以弱合理^[11]定义;

(2) 分析阶段.分析阶段将协同业务过程和正确性约束输入, 自动构建具有正确性的协同业务过程.分析阶段包含如下4个具体步骤.

(a) 基于弱合理将协同业务过程行为抽象为完整的简单路径;

(b) 将抽象的完整简单路径合并以构建核, 核中包含修正前的协同业务过程中所有正确的任务执行系列;

(c) 将核隐藏、最小化后生成每个参与组织的中间业务过程;

(d) 将中间业务过程协调映射为修正业务过程, 通过将修正业务过程并发组合建立修正协同业务过程.

下面将对图 1所示的正确性修正方法进行详细的阐述.

2 协同业务过程定义

为了实现协同业务过程与需求一致性检测, 参与组织需要首先对协同业务过程及期望需求进行建模.

2.1 协同业务过程建模

对协同业务过程进行形式定义是实现协同业务过程正确性修正的基础.本节采用标号迁移系统对业务过程建模, 并将其并发组合形成协同业务过程.

业务过程由参与组织活动集和建立其上的控制流组成, 它由该组织自治管理, 是构建协同业务过程的基础.本文采用标号迁移系统建模业务过程.

定义1(业务过程).业务过程是一个迁移系统BP=(S, s₀, F, A, Δ), 其中,

(1) S为状态集合;

(2) s₀∈S为初始状态;

(3) F⊆S为终止状态集合;

(4) A=A_l∪A_i为活动集合, 其中, A_l为本地活动集合, A_i为交互活动集合;

(5) A_i=A_si∪A_ai, 其中, A_si为同步交互活动集合, A_ai为异步交互活动集合;

(6) A_ai=A_as∪A_ar, 其中, A_as为异步发送活动集合, A_ar为异步接收活动集合;

(7) Δ⊆S×A×S为状态迁移关系集, 用来刻画活动间执行顺序, 即控制流.对于∀(r, a, s)∈Δ, 记为迁移r$\xrightarrow{a}$s, 表示BP在执行活动a后由状态r转换为状态s.

特别地, 称BP是确定的当且仅当对于其中的任意两条迁移r$\xrightarrow{{{a_1}}}$s₁及r$\xrightarrow{{{a_2}}}$s₂, 若a₁=a₂, 则s₁=s₂.本文中所讨论的业务过程均默认是确定的.对于任意同步交互活动a∈A_si, 则协同业务过程中至少存在一个其他业务过程BP', BP'的同步交互活动集合中包含a; 而对于任意异步交互活动a∈A_ai, 若a∈A_as, 则a记为!m, 表示发送消息m的活动, “!”表示发送动作, 若a∈A_ar, 则a记为?m, 表示接收消息m的活动, “?”表示接收动作.对于业务过程BP, 其发送消息集为$M_{BP}^!$={m|!m$ \in $A_as}, 而接收消息集为$M_{BP}^?$={m|?m$ \in $A_ar}.

采用标号迁移系统建模业务过程有如下3个方面的原因:(1)标号迁移系统具有直观图形表示, 可以形式化地刻画系统的行为, 是系统行为深入分析的可靠工具^[17]; (2)迁移系统作为一种中间表示, 任意具有执行语义的过程模型(如利用Petri网或进程代数建模过程模型)都可以方便地转换为本文中以标号迁移系统描述业务过程^[17]; (3)便于后文中映射生成修正业务过程.特别需要说明的是, 由于Petri网具有直观图形化表示, 严格形式语义和丰富的形式分析技术, 被广泛地用于业务过程建模和分析中.本文没有采用Petri网进行协同业务过程修正的根本原因是在具体修正中需要首先生成协同业务过程完整简单路径, 然后合成核(本质上是标号迁移系统), 最后通过对核进行协调映射生成每个修正业务过程(也为标号迁移系统).而若采用Petri网建模协同业务过程, 则具体修正仍然需要对应到标号迁移系统上开展, 不够直观.

以业务过程为基础可建模协同业务过程.本质上, 协同业务过程可视为由多个业务过程构成的并发交互系统.进程代数能够自然地以模块的方式构建复杂的交互并发系统^[18], 借鉴其思想, 本文提出并发操作符概念.并发操作符提供了一种通过组合业务过程构建协同业务过程方法.

定义2(协同业务过程).设参与协同的业务过程为BP₁, …, BP_n, 由这n个业务过程构成的协同业务过程记为CBP=BP₁ ||…||BP_n.

特性需要说明的是, 定义2只是将多个业务过程在形式上列为并发关系, CBP中的活动执行及交互可按实际场景来定义.本文同时考虑活动间同步交互及基于消息通信的活动间异步交互, 参见定义5.

对于任意协同业务过程, 其状态用格局来表示.它由每个参与组织的运行状态及所配置的先进先出消息队列组成向量表示, 其形式定义如下.

定义3(格局).协同业务过程CBP状态表示为一个格局c=〈s₁, Q₁, …, s_n, Q_n〉, 其中, ∀i∈[1..n], s_i为业务过程BP_i的运行状态; Q_i为业务过程BP_i的先进先出消息队列, 用来存储其接收消息, 本文中Q_i的长度默认为无穷.

特别地, CBP的初始格局记为c₀=〈s₀₁, NIL, …, s_0n, NIL〉, 其中, ∀i∈[1..n], s_0i为BP_i的初始状态, 且其消息队列为空, 即为NIL; CBP的终止格局记为c_e=〈s_e1, NIL, …, s_en, NIL〉, 其中, ∀i∈[1..n], s_ei为BP_i的终止状态, 且其消息队列为空, 表示所有的消息均被接收.

可对格局中的运行状态及消息队列进行重置, 形式定义如下.

定义4(格局重置).设格局c=〈s₁, Q₁, …, s_n, Q_n〉, 将业务过程BP_i的运行状态由s_i重置为s'_i, 记为c[${s'_i}/{s_i}$], 而将BP_i的消息队列由Q_i重置为Q'_i, 记为c[${Q'_i}/{Q_i}$].

在协同业务过程中, 活动执行除了受到本地控制流的约束外, 还受到其他业务过程中活动执行情况的影响.归纳起来, 可分为如下3种情况.

1) 若a∈A_l, 则活动a执行仅受到本地控制流的影响;

2) 若a∈A_si, 则活动a执行除了受到本地控制流的影响外, 还需要所有含有同步交互活动a的业务过程同时参与完成;

3) 若a=!m, 则活动a执行除了受到本地控制流的影响外, 还受到其他需要接收消息m的业务过程的消息队列Q的影响, 即Q不满, 且存在接收消息m的业务过程BP.在发送消息m之后, 消息m被添加至BP消息队列的尾部; 而若a=?m, 则活动a执行除了受到本地控制流的影响外, 还受到自身消息队列Q的影响, 即Q不空, 且Q的第1个元素是消息m.在接收消息m之后, 消息m从Q的头部移除.

根据上述对活动执行情况的分析, 我们定义协同业务过程点火规则.

定义5(点火规则).设CBP=BP₁||BP₂||…||BP_n为一个协同业务过程, 其格局为c=〈s₁, Q₁, …, s_n, Q_n〉, 则其点火规则定义如下.

(1) 若a∈A_l, 则c$\xrightarrow{a}$c', 当且仅当s_{i$\xrightarrow{a}$}s'_i∧c'=c[${s'_i}/{s_i}$];

(2) 若a∈A_si, 则c$\xrightarrow{a}$c', 当且仅当∀a∈$A_{si}^j$(1≤j≤n):s_{j$\xrightarrow{a}$}s'_j∧c'=c[${s'_j}/{s_j}$];

(3) 若a=!m, 则c$\xrightarrow{a}$c', 当且仅当s_{i$\xrightarrow{a}$}s'_i∧Ǝi, j∈[1..n]:m∈$M_i^!$∩$M_j^?$∧|Q_j| < L_Qj(L_Qj是Q_j的长度) ∧Q'_j=Q_jm∧c'=c[${Q'_j}/{Q_j}$]∧c'=c[${s'_i}/{s_i}$];

(4) 若a=?m, 则c$\xrightarrow{a}$c', 当且仅当s_{i$\xrightarrow{a}$}s'_i∧Q_i=mQ''_i∧c'=c[${Q''_i}/{Q_i}$]∧c'=c[${s'_i}/{s_i}$].

特别需要说明的是, 给定协同业务过程CBP, 若利用点火规则可产生无穷个格局, 则称CBP具有无穷状态空间, 否则称其具有有穷状态空间.本文关注具有有穷状态空间的协同业务过程.

基于点火规则, 我们可定义协同业务过程的行为, 表示为路径.下面给出几个与路径相关的定义.

定义6(路径).给定协同业务过程CBP, 其行为表示为路径, 是CBP的格局和活动(即本地活动或交互活动)组成的有穷或无穷序列.对于任意路径σ, 其形如:c_{0$\xrightarrow{{{a_1}}}$}c₁…c_{n-1$\xrightarrow{{{a_n}}}$}c_n…, 其中, ∀i∈[1..n], 迁移c_{i-1$\xrightarrow{{{a_i}}}$}c_i符合定义5给出的点火规则, c_i为CBP的格局, c₀为初始格局.

定义7(路径的轨迹).对于任意路径r, r=c_{0$\xrightarrow{{{a_1}}}$}c₁…c_{n-1$\xrightarrow{{{a_n}}}$}c_n…, 则将r中的活动依次连接, 得到活动执行序列l=a₀∧a₁…a_n-1∧a_n∧…称为r的迹, 表示为trace(r).

特别地, 若格局c可通过执行迹l迁移至格局c', 则记为c$\xrightarrow{l}$c'.

定义8(路径一致).设r_p=c_p0$\xrightarrow{{{a_1}}}$c_p1…c_p(n-1)$\xrightarrow{{{a_n}}}$c_pn和r_q=c_q0$\xrightarrow{{{b_1}}}$c_q1…c_q(n-1)$\xrightarrow{{{b_n}}}$c_qn为两条有穷路径, 称r_p和r_q一致, 记为r_p=r_q, 当且仅当r_p的迹与r_q的迹相同.

3 正确性分析

为了对协同业务过程进行修正, 首先需要明确协同业务过程的正确性.目前, 研究者提出多种针对协同业务过程的正确性标准, 其中, 以合理性^[9]及其变体(如弱合理^[11]等)应用最为广泛.由于合理性主要用于定义组织内业务过程的正确性且较为严格^[11], 因此本文利用弱合理性定义协同业务过程的正确性.

定义9(弱合理).给定协同业务过程CBP, c₀和c_e分别为初始格局和终止格局, 称CBP是弱合理的, 当且仅当对于从c₀可达的任意格局c, 存在迹σ, 使得c$\xrightarrow{\sigma }$c_e.

从定义9可以看出, 弱合理性要求从初始格局可达的任意格局都能够到达终止格局.这可确保每个业务过程均能到达终止状态, 因此可避免协同业务过程运行中可能出现的死锁和活锁等情形.同时, 终止格局(见定义3)要求每个业务过程的消息队列均为空, 能够确保协同中产生的消息均可合理地被接收.

本文中的正确性分析是基于路径开展的.实际中的协同业务过程通常含有循环结构, 循环结构将导致路径数量和长度变为无穷, 进而导致正确性检测无法判定.为了将问题收缩至有穷范围, 同时记录下必要的循环结构, 本文定义简单路径如下.

定义10(简单路径).设σ=c₀$\xrightarrow{{{a_1}}}$c₁…c_n-1$\xrightarrow{{{a_n}}}$c_n…为协同业务过程CBP中的一条路径, 称σ是简单路径, 当且仅当对于任意格局c_i在σ中最多出现2次, 即对于∀c_i, N={c_j|c_i=c_j∧j≠i}∧|N|≤2.

特别地, 简单路径对应的轨迹称为简单轨迹.下面给出算法1用来计算一个协同业务过程中的简单路径.

Algorithm1. Generating simple routes.

Input: Collaborative business process CBP;

Output: Simple routes R;

1.  curRoute=[c₀]; //a stack storing simple routes

2.  visRoutes=[]; //a queue recording visited configurations

3.  do

4.    r=curRoute[len-1], and get all successors Su of r;

5.    if Su=Ø then

6.      save curRoute to R and add r into visRoutes;

7.      curRoute=curRoute[0..len-3]; //backtrack node

8.    else

   //for a successor in Su, it can perform iff it occurs less than 2 times in curRoute or is in visRoutes

9.       if all successor in Su cannot be executed then

10.         save curRoute to R and add r into visRoutes;

11.         curRoute=curRoute[0..len-3]; //backtrack node

12.       else

13.         get the transition r$\xrightarrow{a}$s;

14.         curRoute=curRoute∧a∧s;

15.       end if

16.    end if

17.  while curRoute=Ø

18.  return R;

本质上, 算法1是一种深度优先搜索算法.设CBP中格局数为n, 且在搜索过程中每个格局入栈次数为{c₁, …, c_n}, 则算法1的时间复杂度为$O\left( {n \times \sum\limits_{i = m} {{c_i}} } \right)$.进一步地, 对于∀i∈[1..n], 根据定义10可知, c_i最大值为2(对应算法第8行), 即c_i存在于循环结构中被记录2次.因此, 算法1在最坏情况下的时间复杂度为O(2n²).特别地, 由于本文关注具有有穷状态空间的协同业务过程, 即其中含有的格局数是有穷的.因此, 可推出算法1是可以终止的, 进而可推出其中含有的简单路径数量及长度也是有穷的.

定义11(完整的简单路径).设σ=c₀$\xrightarrow{{{a_1}}}$c₁…c_n-1$\xrightarrow{{{a_n}}}$c_n为协同业务过程CBP中的一条简单路径, 称σ为完整简单路径, 当且仅当c_n为终止格局.

特别地, 完整的简单路径所对应的轨迹称为完整轨迹.由弱合理及简单路径, 对协同业务过程进行合理性分析可转换为对简单路径的分析, 见定理1.

定理1.设R为协同业务过程CBP中所有的简单路径集合, 若对于任意简单路径r∈R, r是完整简单路径, 则CBP是弱合理的.

证明:设c_m为从c₀出发且经迹σ到达的任意一个格局, 则可推出存在路径r=c₀$\xrightarrow{{{a_1}}}$c₁…c_m-1$\xrightarrow{{{a_m}}}$c_m, 满足trace(r)=σ, 分下面两种情况加以讨论.

1) 若c_m为终止格局, 则推出存在空迹t, 使得c_m$\xrightarrow{t}$c_e, 即c₀$\xrightarrow{\sigma }$c_e.

2) 若c_m为非终止格局, 再分下面两种情况加以讨论.

(1) 若r满足∀1≤i, j≤m∧j≠i, c_i≠c_j, 则可知r为某条简单路径r_a∈R的前缀片段.由于r_s是完整路径, 则可知必定存在迹t, 使得c_m$\xrightarrow{t}$c_e, 即c_m$\xrightarrow{{\sigma ^ \wedge }t}$c_e.

(2) 若r存在片段c_i$\xrightarrow{{{a_{i + 1}}}}$c_i+1…c_j…c_k-1$\xrightarrow{{{a_k}}}$c_k(1≤i, j, k≤m), 满足c_i=c_j=c_k∧∀i < x, y < k∧x≠{i, j, k}∧y≠{i, j, k} ∧x≠y, c_x≠c_y, 可知轨迹r中存在重复次数大于2的循环结构, 则在r中使用c_i替换掉片段c_i$\xrightarrow{{{a_{i + 1}}}}$c_i+1…$\xrightarrow{{{a_j}}}$c_j.反复执行循环结构替换操作, 最终得到替换后的r'必定为简单路径, 则可知r'为某条简单路径r_s∈R的前缀片段.由于r_s是完整路径, 则可知必定存在迹t, 使得c_{m$\xrightarrow{t}$}c_e, 即c_{0$\xrightarrow{{\sigma ^ \wedge }t}$}c_e.

综合上述(1)和(2)及定义9, 结论成立.证毕.

基于定理1, 设R为协同业务过程CBP中所有的简单路径集合, R中所有的完整简单路径为R_c.若|R_c|=0, 表示R中每条简单路径均不是完整路径, 则称CBP是完全不正确的; 若|R_c|≠0∧|R_c| < |R|, 表示R中有部分简单路径是完整简单路径, 则称CBP是部分正确的; 若|R_c|=|R|, 表示R中所有的简单路径均是完整路径.根据定理1可知, CBP满足弱合理性, 称CBP是完全正确的.

只有在部分正确的情况下, 才可能且有必要对协同业务过程进行修正.以获得的所有完整简单路径为基础, 下面详细地阐述针对协同业务过程的修正方法.

4 正确性修正

针对部分正确的协同业务过程, 其修正可分3步进行:(1)将所有完整的简单路径合并为核; (2)将核映射为修正业务过程; (3)将产生的修正业务过程利用并发操作符组合, 构建修正协同业务过程.

对于部分正确的协同业务过程而言, 根据第3节中的阐述可知, 其中必定含有完整的简单路径(即能够正确地执行完成路径)和非完整的简单路径(即导致协同业务过程执行失败路径).为了捕获其中含有的所有正确路径(即完整的简单路径), 本文提出了核的概念.本质上, 对于一个部分正确的协同业务过程, 它对应的核是含有其中所有完整简单路径的一个迁移系统.

定义12(核).核是五元组c=(C, c₀, C_e, A, Δ), 其中,

(1) C为格局集合;

(2) c₀∈C为初始格局;

(3) C_e∈C为终止格局集;

(4) A为活动集合;

(5) Δ∈C×A×C为格局迁移关系集合.

特别地, 对于任意核c, 其行为也可由路径表示.对于c中任意路径r=c₀$\xrightarrow{{{a_1}}}$c₁…c_n-1$\xrightarrow{{{a_n}}}$c_n…, 满足∀i∈[1..n], c_i-1$\xrightarrow{{{a_i}}}$c_i, 当且仅当(c_i-1, a_i, c_i)∈Δ.

下面提出算法2, 用来将所有完整的简单路径合并以构建核.

Algorithm2. Generating core.

Input: All complete simple routes R;

Output: Core c;

19.  define returned core c=(C, c₀, C_e, A, Δ);

20.  for each complete simple route r in R do

21.    get the length len of complete simple route r

22.    for i∈[0..len-1] do

23.      get from=r[i], task=r[i+1], and to=r[i+1];

24.      if from is not in C then

25.        add from to C;

26.      end if

27.      if to is not in C then

28.        add to to C;

29.      end if

30.      if task is not in A then

31.        add task to A;

32.      end if

33.      if (from, task, to) is not in Δ then

34.        add (from, task, to) to Δ;

35.      end if

36.    end for

37.  end for

38.  set the srart state to c₀;

39.  for each elem e in C do

40.    if e is c_e then

41.      add e to C_e;

42.    end if

43.  end for

44.  return c;

算法2的基本思想是通过将完整的简单路径中的格局集和格局迁移集分别设置为核中的格局集和格局迁移集, 从而构建核.算法2的时间复杂度取决于完整的简单路径的条数及其长度.不妨设完整的简单路径条数为m, 每条完整的简单路径的长度为n, 则算法2的时间复杂度为O(m×n).

特别需要说明的是:由于完整的简单路径中记录了循环结构, 因此最终构建的核中循环结构不会丢失.由此可以推断, 对于部分正确的协同业务过程, 通过算法2生成的核中只含有此协同业务过程中所有完整的简单路径, 见定理2.

定理2.给定部分正确的协同业务过程CBP, CBP中含有的所有完整的简单路径记为R_c.设c是根据R_c构建的核, 则对于CBP中任意完整的简单路径r_c, c中也存在r_c, 反之亦然.

证明:充分性.设r_c=c₀$\xrightarrow{{{a_1}}}$c₁…c_n-1$\xrightarrow{{{a_n}}}$c_n为CBP中任意一条完整的简单路径r_c, 分下面两种情况讨论.

1) 若r_c满足∀1≤i, j≤n∧j≠i, c_i≠c_j, 可知r_c为完整的简单路径, 推出r_c∈R_c.由算法2可知, 由R_c构建后的c中必定存在格局迁移关系集合{(c₀, a₁, c₁), …, (c_n-1, a_n, c_n)}⊆Δ, 由此格局迁移关系可生成路径r_c.

2) 若r_c中存在路径片段c_i$\xrightarrow{{{a_{i + 1}}}}$c_i+1…c_j…c_k-1$\xrightarrow{{{a_k}}}$c_k(1≤i, j, k≤n), 满足c_i=c_j=c_k∧∀i < x, y < k∧x≠{i, j, k}∧y≠ {i, j, k}∧x≠y, c_x≠c_y, 可知r_c中存在重复次数大于2的循环结构η=c_i$\xrightarrow{{{a_{i + 1}}}}$c_i+1…$\xrightarrow{{{a_j}}}$c_j, 则在r_c中使用c_i替换掉μ.反复执行循环结构替换操作, 最终得到替换后的r'_c必定为简单路径, 推出r'_c∈R_c.由算法2可知, 由R_c构建后的c中必定存在格局迁移关系集合{(c_i, a_i+1, c_i+1), …, (c_j-1, a_j, c_i)}⊆Δ, 由此可生成任意重复次数(设为p, p≥0)的循环片段, 即μ_p.由定义9可知, 轨迹r_c的长度有穷, 可推出r'_c中的循环片段μ的重复次数是确定整数(设为q), 即μ_q.由于q≤p, 可推出μ_q可由c中格局迁移关系{(c_i, a_i+1, c_i+1), …, (c_j-1, a_j, c_i)}⊆Δ生成.同时, 对于r'_c中任意非循环结构片段, 即c_g-1$\xrightarrow{{{a_g}}}$c_g(1≤g≤n), 不存在c_u, c_v(1≤u, v≤n∧u < g-1∧v > g), 使得c_u=c_v, r'_c中存在c_g-1$\xrightarrow{{{a_g}}}$c_g, 由算法2可知, (c_g-1, a_g, c_g)∈Δ.因此, 从左至右扫描r_c, 对于非循环结构路径片段c_g-1$\xrightarrow{{{a_g}}}$c_g, r'_c中存在c_g-1$\xrightarrow{{{a_g}}}$c_g, 则可推出其可由c中(c_g-1, a_g, c_g)∈Δ生成, 而对于多次重复的循环结构μ_k(μ=c_i$\xrightarrow{{{a_{i + 1}}}}$c_i+1…$\xrightarrow{{{a_j}}}$S_i), r'_c中存在c_i$\xrightarrow{{{a_{i + 1}}}}$c_i+1…$\xrightarrow{{{a_j}}}$c_i, 则可推出其可由{(c_i, a_i+1, c_i+1), …, (c_j-1, a_j, c_i)}⊆Δ生成, 重复这一过程, 最终可由c生成r_c.

必要性.可按类似方式证明, 限于篇幅, 这里从略.

给定部分正确协同业务过程CBP=BP₁||BP₂||…||BP_n, 根据算法2生成的CBP的核为c.本文中, 对CBP进行修正目标是要保证CBP中完整简单路径对应轨迹可在修正后的协同业务过程CBP_r=BP_r1||BP_r2||…||BP_rn中重现, 且CBP_r中仅含有这些完整简单路径的轨迹, 以避免后续有效性确认, 提高修正效率.其中, BP_r1, …, BP_rn分别为业务过程BP₁, …, BP_n对应的修正业务过程.根据定理2, 这一问题可转换为保证CBP_r和核c的行为一致.

为了生成与CBP行为一致的CBP_r, 基于核c, 本文提出协调映射概念.协调映射是指在映射过程中引入协调因子(对应活动), 用于建模协调交互以实现协调逻辑, 从而确保由映射生成BP_r1, …, BP_rn并发组合形成CBP_r能够遵循cc行为.从外界视角来观察, 在忽视协调因子的情况下, 协调映射可使得CBP_r只包含CBP中所有完整简单路径的轨迹.

在实际应用中, 不是CBP中的每个活动都需要进行协调.以核为基础, 本文提出协调活动的概念.

定义13(协调活动).给定部分正确协同业务过程CBP=BP₁||BP₂||…||BP_n, CBP对应的核c=(C, c₀, C_e, A, Δ), 称活动a∈A₁∪A₂∪…∪A_n为协调活动, 当且仅当存在格局c₁∈C, 使得c₁$\xrightarrow{a}$c₂, 且c₂∉C, 其中, ∀i∈[1..n], A_i为业务过程BP_i的活动集.

由定义13可知, 协调活动是指在协同业务过程执行中若不加以控制, 则可能导致隐藏路径产生的活动, 即从初始格局c₀至c₂或由c₂引出路径.因此, 需要对这些活动进行协调, 使其执行后到达正确格局c₁, 避免达到异常格局c₂.而对于除协调活动以外的其他活动, 由于其执行后总能够到达正确状态, 因此无需协调.

以核为基础, 映射生成修正业务过程之前需先将核中不相关活动(即不属于此业务过程及不是协调活动的其他活动)隐藏, 形式定义如下.

定义14(隐藏).给定部分正确协同业务过程CBP, BP=(S, s₀, F, A, Δ)为CBP中一个业务过程, CBP对应的核c=(C, c₀, C_e, A, Δ), 协调活动集为A_c, 则根据BP及A_c对c进行隐藏后得到隐藏核为c'=(C', c'₀, C'_e, A', Δ'), 其中,

(1) C'=C;

(2) A'={τ}∪{a|∀(r, a, s)∈c.Δ∧a∈A∪A_c};

(3) 对于∀(r, a, s)∈Δ, 如果a∈A∪A_c, 则(r, a, s)∈Δ', 否则, τ格局迁移关系(r, τ, s)∈Δ'.

由定义14可知, 隐藏是将c中格局迁移关系重置.即若格局迁移关系中活动是BP中活动或是协调活动, 则在重置的格局迁移关系中保持不变, 否则将其设置为不可见活动τ.

在对c进行隐藏后, 需要将产生的隐藏核c'最小化以生成修正业务过程.当前, 研究者提出多种行为最小化技术^[19], 如轨迹最小化、分支最小化及互模拟最小化等.由于本文关注协同业务过程间的路径一致, 即路径对应轨迹相同, 因此我们采用文献[20]中提出的弱轨迹最小化算法对隐藏核进行最小化操作, 最小化后生成一个中间有穷自动机.本质上, 标号迁移系统是一类特殊有穷自动机.因此, 通过将中间有穷自动机中的状态集、开始状态、结束状态集、活动集及状态迁移关系分别对应到标号迁移系统中的状态集、初始状态、终止状态集、活动集及状态迁移关系, 则可由隐藏核生成一个中间业务过程.这种转换过程非常直观, 限于篇幅, 这里不再赘述.通过利用文献[20]中提出的最小化方法, 可确保中间业务过程与隐藏核保持弱轨迹等价, 且中间业务过程中不含有不可见活动.

基于最小化后生成的中间业务过程, 根据协调活动集, 下面给出协调映射定义, 以生成修正业务过程.

定义15(协调映射).给定部分正确协同业务过程CBP=BP₁||BP₂||…||BP_n, BP=(S, s₀, F, A, Δ)为CBP中的一个业务过程, A_c为CBP中的协调活动集, 最小化后生成中间业务过程为BP_m=(S_m, s_m0, F_m, A_m, Δ_m), 则根据BP和A_c对BP_m进行协调映射后得到修正业务过程为BP_r=(S_r, s_r0, F, A_r, Δ_r), 其中,

(1) S_r=S_m∪{s_c|∀(r, a, s)∈Δ_m∧a∉A∧a∈A_c}∪{s_c1, s_c2|∀(r, a, s)∈Δ_m∧a∈A∧a∈A_c};

(2) s_r0=s_m0;

(3) F_r=F_m;

(4) A_r={a|∀(r, a, s)∈cc.Δ_m∧a∈A∧a∉A_c}∪{SYNC_1_a, SYNC_2_a|∀(r, a, s)∈Δ_m∧a∈A∧a∈A_c}∪

{SYNC_1_a, SYNC_2_a|∀(r, a, s)∈Δ_m∧a∉A∧a∈A_c};

(5) Δ_r={(r, SYNC_1_a, s_c), (s_c, SYNC_2_a, s)|∀(r, a, s)∈Δ_m∧a∉A∧a∈A_c}∪

{(r, SYNC_1_a, s_c1), (s_c1, a, s_c2), (s_c2, SYNC_2_a, s)|∀(r, a, s)∈Δ_m∧a∈A∧a∈A_c}∪

{(r, a, s)|∀(r, a, s)∈cc.Δ_m∧a∈A∧a∉A_c}.

定义15中, 对于BP_m中的一个活动a:(1)若a不属于BP但需协调, 则引入协调因子SYNC_1_a、SYNC_2_a及协调状态s_c, 用于将BP_m中的格局迁移关系(r, a, s)设置为(r, SYNC_1_a, s_c)和(s_c, SYNC_2_a, s), 表示在状态r通过协调因子SYNC_1_a对活动a开始进行协调, 并通过协调因子SYNC_2_a对活动a结束协调; (2)若a属于BP且需协调, 则引入协调因子SYNC_1_a、SYNC_2_a及协调状态s_c1和s_c2, 用于将格局迁移关系(r, b, s)设置为3个状态迁移关系(r, SYNC_1_a, s_c1)、(s_c1, a, s_c2)和(s_c2, SYNC_2_a, s), 表示在a执行前需进行协调, 通过SYNC_1_a来实现, 执行完成后进行结束协调, 通过SYNC_2_a来实现; (3)若a属于BP且无需协调, 则格局迁移关系(r, b, s)保持不变.

本质上, 修正业务过程是一个迁移系统.特别地, 给定一个业务过程BP, 其修正业务过程BP'受BP行为(即迁移序列)和协调因子的影响.根据我们的实验可以发现(见第5.2节), BP'结构通常较BP更复杂.同时, 本文中BP'采用LTS进行描述, LTS描述模型较其他图形化方式(如BPMN、BPEL和Petri网)描述的模型复杂、难懂.这就限制了本文方法在实际中被用户接受的程度.事实上, 研究者已经提出了一些方法^[21]用于将以LTS描述模型转换为Petri网描述模型, 且能够保持转换前后行为一致(如保持强互模拟等).因此, 针对修正业务过程对于用户较难理解这个问题, 可以考虑利用工具Petrify(https://www.merriam-webster.com/dictionary/petrify)将其转换为Petri网来增强其实用性.有关Petrify介绍及使用可以参见文献[21], 限于篇幅, 这里不再阐述.

通过将修正业务过程集利用并发操作符加以组合, 得到如下定义的修正协同业务过程.

定义16(修正协同业务过程).给定部分正确协同业务过程CBP=BP₁||BP₂||…||BP_n, BP_r1, …, BP_rn分别为业务过程BP₁, …, BP_n对应的修正业务过程, 则修正协同业务过程为CBP_r=BP_r1||BP_r2||…||BP_rn.

在忽视协调因子的情况下, 修正协同业务过程中只含有修正前的协同业务过程中的所有完整轨迹, 可见定理3.

定理3.给定部分正确协同业务过程CBP=BP₁||BP₂||…||BP_n, CBP_r=BP_r1||BP_r2||…||BP_rn为CBP的修正协同业务过程, 则如下结论成立.

(1) 对于CBP中任意完整的简单路径r, CBP_r中存在一条完整的简单路径r', 满足trace(r)=trace(r')↑A_cf;

(2) 对于CBP_r中任意完整的简单路径r, CBP中存在一条完整的简单路径r', 满足trace(r')=trace(r)↑A_cf;

其中, A_cf为CBP中所有协调因子集合; trace(r)↑A_cf表示将r的任务执行序列中的协调因子移除后形成的新任务执行序列.

证明:1)设c为根据算法2生成CBP的核, r=c₀$\xrightarrow{{{a_1}}}$c₁…c_m-1$\xrightarrow{{{a_m}}}$c_m为c中任意一条完整的简单路径.由定义14可知, 对于r中任意迁移c_i-1$\xrightarrow{{{a_i}}}$c_i(1≤i≤m), 每个业务过程BP_n(1≤i≤n)对应隐藏核中存在如下迁移, 记为C1:

${c_{i - 1}}\xrightarrow{{{a_i}}}{c_i} = \left\{ \begin{gathered} {c_{i - 1}}\xrightarrow{\tau }{c_i}, {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {a_i} \notin A \cup {A_c} \\ {c_{i - 1}}\xrightarrow{{{a_i}}}{c_i}, {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \;{a_i} \in A \cup {A_c} \\ \end{gathered} \right..$

由文献[20]中提出的最小化方法可知, 所有的τ-格局迁移关系(即由τ引起的格局迁移关系)均被移除, 且满足弱轨迹等价, 则最小化隐藏核后生成的业务过程BP中有如下迁移, 记为C2:

${c_{i - 1}}\xrightarrow{{{a_i}}}{c_i} = \left\{ \begin{gathered} {s_i}{\rm{ = }}{s_{i - 1}}, {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \;\;{a_i} \notin A \cup {A_c} \\ {s_{i - 1}}\xrightarrow{{{a_i}}}{s_i}, {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \;{a_i} \in A \cup {A_c} \\ \end{gathered} \right..$

根据定义15, 每个修正业务过程BP_rj(1≤j≤n)中的迁移进行如下协调映射, 记为C3:

${c_{i - 1}}\xrightarrow{{{a_i}}}{c_i} = \left\{ \begin{array}{l} {s_i}{\rm{ = }}{s_{i - 1}}, {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\kern 1pt} \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{a_i} \notin A \wedge {a_i} \notin {A_c}{\kern 1pt} \\ {s_{i - 1}}\xrightarrow{{{a_i}}}{s_i}, {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\kern 1pt} \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{a_i} \in A \wedge {a_i} \notin {A_c} \\ {s_{i - 1}}\xrightarrow{{{\rm{SYNC}}\_1\_a}}{s_{c1}}\xrightarrow{{{a_i}}}{s_{c2}}\xrightarrow{{{\rm{SYNC}}\_2\_a}}{s_i}, \;{\kern 1pt} {\kern 1pt} {\kern 1pt} {\rm{ }}\;{a_i} \in A \wedge {a_i} \in {A_c}{\kern 1pt} \\ {s_{i - 1}}\xrightarrow{{{\rm{SYNC}}\_1\_a}}{s_c}\xrightarrow{{{\rm{SYNC}}\_2\_a}}{s_i}, {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \;{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {a_i} \notin A \wedge {a_i} \in {A_c} \\ \end{array} \right..$

从左至右依次扫描r, 根据定义5中的点火规则可生成如下路径r', 满足:

$ \begin{matrix} {r}'={{k}_{0}}\ldots {{k}_{i-1}}\xrightarrow{\text{SYN}{{\text{C}}_{-}}{{1}_{-}}{{a}_{i}}}{{k}_{\left( i-1 \right)i1}}\xrightarrow{{{a}_{i}}}{{k}_{\left( i-1 \right)i2}}\xrightarrow{\text{SYN}{{\text{C}}_{-}}{{2}_{-}}{{a}_{i}}}{{k}_{i}}\ldots {{k}_{m}}\left( {{a}_{i}}\in {{A}_{c}} \right), \\ 或{r}'={{k}_{0}}\ldots {{k}_{i-1}}\xrightarrow{{{a}_{i}}}{{k}_{i\ldots }}{{k}_{m}}\left( {{a}_{i}}\notin {{A}_{c}} \right), \\ \end{matrix} $

根据C3, 由于r为完整的简单路径, 则可推出r'中k_m也为终止格局, 故r'是完整的简单路径.进一步地, 推出trace(r)=trace(r')↑A_cf成立.根据定理2, c与CBP中完整的简单路径一致, 故结论(1)成立.

2) 采用反证法证明.设CBP_r中存在路径片段r₁=k₀$\xrightarrow{{{a_1}}}$k₁…k_k-1$\xrightarrow{{{a_k}}}$k_k, 且c中存在对应路径片段r₂, 满足trace(r₂)=trace(r₁)↑A_cf.但CBP_r中存在后续迁移k_k$\xrightarrow{a}$k_k+1使得路径片段r₃=k₀$\xrightarrow{{{a_1}}}$k₁…k_k-1$\xrightarrow{{{a_k}}}$ k_k$\xrightarrow{a}$k_k+1不为c中任意完整的简单路径的前缀.按如下两步证明后续活动a不能发生.

(1) 首先明确活动a是协调活动, 即a∈A_c.针对路径片段r₁, 由于c中存在对应路径片段r₂, 满足trace(r₂)= trace(r₁)↑A_cf.因此, 从左至右扫描r₁, 对于r₁中路径片段:k_i-1$\xrightarrow{{{\rm{SYNC}}\_1\_{a_i}}}$k_c1$\xrightarrow{{{a_i}}}$k_c2$\xrightarrow{{{\rm{SYNC\_2}}\_{a_i}}}$k_i, 或者k_i-1 $\xrightarrow{{{a_i}}}$k_i, 则用c_i-1$\xrightarrow{{{a_i}}}$c_i替换, 重复这一过程, 最终可求得k_k对应于c_k.由C3可知, 若后续迁移k_k$\xrightarrow{a}$k_k+1发生后使得r₃不为c中任意完整简单路径的前缀, 那么a∈A_c.

(2) 再证明协调活动a在CBP_r中不能发生.分下面两种情况加以讨论.

i) a不在c中出现, 即a∉c.A.由C3可知, 后续迁移k_k$\xrightarrow{a}$k_k+1不存在;

ii) a在c中出现, 即a∈c.A.设有后续有效迁移k_k$\xrightarrow{b}$k_k+1, 使得r₄=k₀$\xrightarrow{{{a_1}}}$k₁…k_k-1$\xrightarrow{{{a_k}}}$k_k$\xrightarrow{b}$k_k+1为c中某条完整简单路径的前缀.若活动a能执行, 再分如下两种情况进行讨论.

①  若a和b属于同一个修正业务过程BP_rj(1≤j≤n), 则推出a和b处于选择关系.由C3可知, 若a能够执行, 则b不能执行.但迁移k_k$\xrightarrow{b}$k_k+1是有效的, 故活动a不能执行;

②  若a和b属于不同的修正业务过程, 不妨设分别属于业务过程BP_ri和BP_rj(1≤i, j≤n).根据C3可推出, BP_rj中存在迁移s_j$\xrightarrow{b}$s_j+2, s_j$\xrightarrow{{{\rm{SYNC}}\_1\_a}}$s_c1$\xrightarrow{a}$s_c2$\xrightarrow{{{\rm{SYNC\_2}}\_a}}$s_j+1.根据定义5给出的点火规则, 若活动a能够执行, 则活动b不能执行.但迁移k_k$\xrightarrow{b}$k_k+1是有效的, 故活动a不能执行.

综合上述(1)和(2)推导可知, 结论(2)成立.

定理3中的结论(1)表明修正前的协同业务过程中所有完整的简单路径都可以在修正协同业务过程中重现; 而结论(2)则表明未引入隐藏轨迹.这将避免修正后进行有效性确认, 从而提高了修正效率.

特别需要明确的是, 本文方法可支持带有一般循环结构的过程模型, 其原因在于修正是基于完整简单路径开展.完整简单路径能够记录循环结构(即自循环和一般循环结构^[17]), 故通过算法2构建的核中循环结构也不会丢失.最终, 通过对核进行协调映射产生修正业务过程也含有已有环结构.

5 实验评价

本文提出一种协同业务过程正确性修正方法.为了评估该方法的有效性, 本节使用具有实际意义的协同业务过程集, 通过与相关正确性修正方法进行实验对比, 从修正协同业务过程具有协同业务过程实际特征、重现完整轨迹及未引入隐藏轨迹等方面来分析不同正确性修正方法之间的有效性差异.

5.1 实验准备

当前针对协同业务过程没有公开的数据集可供实验^[22], 而为了评价本文提出方法的有效性, 我们从已有的研究论文^{[23, 24]}及BPMN案例库(http://www.bpmn.org/)中选取6个较为典型的协同业务过程进行实验.其中, Order Product(记为OP)、Purchase Order(记为PO)及Travel Booking System(记为TBS)分别作为文献[23, 24]中的启发案例, 用来阐述跨组织业务过程建模并分析方法的有效性, 代表性较强; Amazon Online Purchase(记为AOP)、The Nobel Prize(记为TNP)和Incident Management(记为IM)则来自BPMN案例库, 能够反映实际的协同业务过程场景.

选取的6个协同业务过程具有的属性见表 1, 其中, No. of peers表示协同业务过程中含有参与组织的个数, “No. of peer states, trans”表示协同业务过程中含有的状态数及迁移数.采用标号迁移系统表示过程模型中的结构有顺序、选择和循环3类.为了表明选取过程模型的普遍性, 选取的6个协同业务过程中含有这3类结构.特别地, 循环结构包含自循环和一般意义上的循环结构这两类^[17].这两类循环结构也反映在过程模型中, 如Purchase Order中含有自循环, 而Order中则含有一般循环结构等.

特别地, 由于本文提出正确性修正方法面向部分正确协同业务过程, 因此通过项目组讨论对选取6个协同业务过程的内部结构进行修改以注入错误, 其中错误类型为死锁、活锁及消息未合理接收等.

目前, 针对协同业务过程的正确性修正方法较少.本文选择此类中的典型方法^[13-15]作为实验比较对象, 从支持协同业务过程的实际特征、重现完整轨迹及引入隐藏轨迹等方面进行对比分析.

特别地, 文献[13]中方法的处理步骤是:先将每个业务过程采用Petri网进行建模, 利用文献[9]中提到的库所熔合和变迁熔合技术构建全局模型, 并获得其所有完备轨迹^[17].这里的完备是指在全局模型中, 若活动b能够在活动a执行后立即执行, 则存在一条轨迹σ, σ中存在位置i, 满足σ(i)=a, 且σ(i+1)=b; 然后, 将获得完备轨迹作为文献[13]中正确性修正方法输入, 则可生成中心流程; 最后, 将中心流程与每个业务过程进行变迁熔合, 则构建修正协同业务过程.而文献[14, 15]中方法的处理步骤是:先将每个业务过程采用Petri网进行建模; 然后利用文献[9]中库所熔合和变迁熔合技术构建全局模型.针对构建的全局模型, 为保持修正模型的一致性, 获得其完备轨迹; 最后, 将获得的完备轨迹作为文献[14, 15]中模型修正方法输入, 即构建出修正协同业务过程.

所有实验在一台PC上开展, 软件环境为:Windows 10及JDK 1.7, 硬件环境为:处理器为Inter(R) Core(TM) i5-8250U CPU@ 1.60GHz、内存为8GB.

5.2 实验结果及分析 5.2.1 支持个性化特征分析

通过对修正协同业务过程进行分析, 可以分析出本文方法在支持协同业务过程实际特征方面的有效性.跨组织业务过程建模研究表明^[6-10], 协同业务过程通常具有4类特征:自治性、分布性、交互性和隐私性.其中, 自治性是指每个业务过程由其所属组织管理及运行; 分布性是指协同业务过程在结构和执行上具有分布性; 交互性是指业务过程在执行中需要与其他业务过程进行交互以推动全局流程演进; 隐私性是指在跨组织环境下, 参与组织希望在建模及分析过程中避免将其内部流程信息暴露给其他参与组织.特别地, 在实际应用中, 这4类特征主要是针对构建后的协同业务过程形态(即是否表现为分布式、有无中心流程等)及构建时是否暴露流程信息给参与组织来进行体现.因此, 上文在定义协同业务过程和阐述方法时没有提及这4类特征.此外, 应用这4类特征对协同业务过程评价主要是从定性角度开展, 因此本文未在上文具体证明中及本节中应用实验数据验证这个结果.

特别需要说明的是, 实验中默认本文方法和文献[13-15]中的方法对协同业务过程进行修正均是由可信第三方TTP(trusted third party)^[25]来完成, 因此均能支持隐私性.在实际应用中, 参与组织先将各自的业务过程提交给TTP; 之后TTP对由其组合建立协同业务过程, 并对其修正; 最后TTP将每个修正业务过程返给对应参与组织.在跨组织环境下, 为保护隐私性, 这种通过TTP对协同业务过程进行分析是常见和合理的^[25].

针对选取的5个协同业务过程, 本文方法和文献[13-15]中的方法建立的修正协同业务过程对上述4类特征支持情况见表 2, 其中.A表示自治性, D表示分布性, I表示交互性, P表示隐私性.

从表 2可以看出, 经本文方法建立的修正协同业务过程能够良好地支持上述4类特征, 而经文献[13-15]中的方法建立的修正协同业务过程仅能支持隐私性.因此, 相较文献[13-15]中的方法, 本文方法能够更加有效地支持协同业务过程具有实际特征.

例如, 对于协同业务过程集中订单采购OP, OP中业务过程Customer和Vendor如图 2所示.

利用本文方法建立修正协同业务过程OP_r-o如图 3所示, 修正业务过程Customer_r和Vendor_r并发组合形成.

利用文献[13]中的方法建立的修正协同业务过程OP_r-z如图 4所示, 其中, 虚线表示任务同步关系.

利用文献[14, 15]的中方法建立的修正协同业务过程OP_r-a如图 5所示.

通过分析OP_r-o、OP_r-z和OP_r-a可知, OP_r-o由修正业务过程Customer_r和Vendor_r并发组合形成, 即OP_r-o= Customer_r||Vendor_r.由于这两个修正业务过程独立存在, 且每个修正业务过程由各自组织管理, 同时, OP_r-o按照定义5中给出的点火规则运行, 表明其具有自治、分布及交互特性.同时, 具体修正由TTP完成, 表明其具有隐私性; 而由文献[13-15]中的方法建立的修正协同业务过程OP_r-z和OP_r-a实质上均是集中式的.特别地, 业务过程Customer和Vendor中活动及活动间的交互不是并发执行的, 而是通过Center和OP_r-a中控制流的约束来执行.例如, Customer内本地活动browProduct执行需要与Center内活动browProduct执行同步; 而活动!orderA和?orderA间的交互则由Center内控制流来约束.

5.2.2 轨迹有效性分析

本小节分析修正协同业务过程中重现完整轨迹和未引入隐藏轨迹的有效性.基于简单轨迹, 本文提出精确度和泛化度这两个有效性计算指标.

精确度的计算公式如式(1)所示.

$ P\left( {M'} \right)\frac{{|acc({T_M}, {T_{M'}})|}}{{|{T_{M'}}|}} $

(1)

式(1)中, T_M'为修正协同业务过程中所有的简单轨迹; T_M为修正前协同业务过程中所有的完整简单轨迹; acc(T_M, T_M')为被T_M接受的T_M'中的轨迹子集.对于精确度而言, 计算结果值越高, 则表示修正协同业务过程中引入的隐藏轨迹越少, 修正效果越好.

泛化度的计算公式如式(2)所示.

$ G\left( {M'} \right)\frac{{|acc({T_{M'}}, {T_M})|}}{{|{T_M}|}} $

(2)

式(2)中, T_M'为修正协同业务过程中所有的简单轨迹; T_M为修正前协同业务过程中所有的完整简单轨迹; acc(T_M', T_M)为被T_M'接受的T_M中的轨迹子集.对于泛化度指标, 计算结果值越高, 则表示修正协同业务过程中重现修正前协同业务过程中的完整简单轨迹越多, 修正效果越好.

根据式(1)和式(2), 本文方法和文献[13-15]中方法的精确度和泛化度的计算结果分别如图 6(a)~图 6(b)所示.

由图 6(a)可以看出, 本文方法的精确度高于文献[13-15]中方法的精确度.同时, 本文方法的泛化度与文献[14, 15]中方法的泛化度相同, 但远高于文献[13]中的方法.由此, 我们可以得出如下结论.

(1) 由于本文方法能够事先保证修正协同业务过程中含有修正前协同业务过程中所有完整的轨迹, 且未引入隐藏轨迹, 使得本文方法的精确度和泛化度均为1.0.图 6所示实验结果也与理论分析相一致;

(2) 文献[14, 15]中的方法在精确度方面表现良好, 其均为1.0, 表明修正协同业务过程能够重现修正前的协同业务过程中所有完整的轨迹.在泛化度方面, 文献[14, 15]中方法的值介于0.5~1.0之间, 表明在修正协同业务过程中引入了隐藏轨迹.分析发现, 这些隐藏轨迹是由修正协同业务过程中存在异常(如死锁等)引起;

(3) 文献[13]中的方法在精确度和泛化度方面的表现都是最差的, 其精确度和泛化度在选取的协同业务过程中大多为0.0, 表明修正前协同业务过程中几乎所有完整轨迹在修正协同业务过程中丢失.分析发现, 这是由于修正协同业务过程中存在异常(如死锁等)和一些活动丢失(如PO_r-z中活动checkStock丢失等)所致.

5.2.3 修正时间耗费分析

通过分析建立修正协同业务过程时间耗费, 可评价本文方法的修正效率.利用本文方法和文献[13-15]中的方法对协同业务过程进行正确性修正所耗费的时间为T_cr=T_ct+T_r, 其中, T_ct为获取修正前协同业务过程中所有完整的轨迹时间, T_r为进行修正所耗费的时间; 同时, 利用文献[13-15]中的方法对协同业务过程进行修正后还需要进行有效性确认, 所耗费的时间为T_cv=T_vp+T_vg, 其中, T_vp为计算精确度时间, T_vg为计算泛化度时间.本文方法和文献[13-15]中的方法建立修正协同业务过程的时间耗费见表 3, 其中, T_total为修正总耗费时间, 即为正确性修正耗费时间和有效性确认所耗费时间之和.特别地, 为了确保结果的客观性, 每次实验重复10次, 然后取平均值作为建立修正协同业务过程的时间耗费.

从表 3可以看出:

(1) 利用本文方法修正所耗费的时间远远小于文献[13-15]中的方法.例如, 针对Travel Book System, 本文方法的修正耗费时间为3 570ms, 而文献[13]和文献[14, 15]中的方法分别耗费133 750ms和281 667ms.分析发现, 文献[13-15]中方法修正效率低下的原因是由于上述6个协同业务过程中含有较多完备轨迹(如Travel Book System中含有1 458条完备轨迹)和采用过程挖掘技术所致.可以预见, 若对更加复杂的协同业务过程进行修正, 则其时间将进一步增加.而本文方法只需获取所有的完整简单路径(如Travel Book System中只含有384条), 并对核协调映射即可生成修正协同业务过程, 避免文献[13-15]中方法使用过程模型挖掘算法(如算法等)、案例差异检测等步骤, 从而缩短了修正时间;

(2) 由于本文方法能够事先保证修正协同业务过程中含有修正前协同业务过程中所有的完整轨迹, 且未引入隐藏轨迹, 这使得本文方法无须进行有效性确认, 即有效性确认耗费时间为0ms.而文献[13-15]中方法的有效性确认所耗费的时间均较高.例如, 针对Travel Book System, 文献[13]和文献[14, 15]中方法进行有效性确认耗费的时间分别为20 900ms和59 696ms.分析发现, 这是由于选取的协同业务过程和对应修正协同业务过程中均含有较多的简单轨迹和完整轨迹所致.可以预见, 若对更加复杂的协同业务过程进行有效性确认, 则其所耗费的时间将进一步增加;

(3) 从修正耗费总时间来看, 相较文献[13]和文献[14, 15]中的方法, 本文方法的修正效率有极大的提高, 分别提高14倍和42倍.

综上分析, 可以得出如下结论:相比文献[13-15]中所提出的正确性修正方法, 在考虑协同业务过程实际特征的情况下, 由于本文方法能够事先确保修正协同业务过程中含有修正前协同业务过程中所有完整的轨迹, 且未引入隐藏轨迹, 从而使得本文方法可以对协同业务过程进行更加有效的修正, 并且能够极大地缩短修正所耗费的时间.

6 相关工作

目前, 针对协同业务过程的正确性分析方法可分为两类:正确性检测方法和正确性修正方法.下面对这两类方法中的一些典型文献进行介绍和分析.

6.1 正确性检测方法

国内外研究者针对协同业务过程的正确性检测方法开展了大量的研究.归纳起来, 这些方法可分为3类:基于Petri网的检测方法、基于进程代数的检测方法及基于自动机的检测方法.

以传统的组织内业务过程建模方法为基础, 文献[9]较早地在国际上提出了IOWF(inter-organizational workflow)用于建模跨组织业务过程.针对构建跨组织业务过程提出合理性概念用来定义其正确性, 并基于Petri网的可达图提出跨组织业务过程正确性检测方法.之后, 国内外研究者以此为基础开展了大量的研究.如文献[10]针对跨部门业务过程协同呈现出越来越复杂的特点, 对WF-net扩展资源和消息等要素以建模参与部门的业务过程, 继而使用库所熔合技术将资源库所和消息库所加以熔合从而得到跨部门协调业务过程模型.针对构建跨部门业务过程, 基于合理性定义其正确性并提出验证方法.跨组织工作流网IWF-nets(inter-organizational workflow nets)可以有效地建模协同业务过程间基于消息的协作.为了确保协同业务实施的正确性, 文献[26]引入了兼容性和弱兼容性的概念, 并针对IWF-nets的网结构提出了用于判定兼容性或弱兼容性的充要条件.针对公共管理呈现出交互的特征, 为确保其正确实施, 文献[27]首先使用BPMN(business process modeling notation)对其进行描述, 之后将其BPMN模型转换成基于Petri网的模型, 并采用Petri网的展开技术(unfolding-based technique)对相关性质(如死锁等)进行验证.为了有效地验证协同业务过程的行为正确性, 文献[28]首先利用BPMN建模协同业务过程, 然后将每个参与组织的流程转换为一类高级Petri网ECATNets(recursive ECATNets), 最后基于库所熔合技术将其组合得到以ECATNets来描述的模型.由于该模型的语义被解释为条件重写逻辑, 进而可以利用Maude LTL模型检测器对协同业务过程的行为正确性性质进行验证.

基于Pi演算, 文献[16]较早地提出一种利用进程代数建模跨组织业务过程方法.即利用Pi演算的并发算子, 将跨组织业务过程建模为一组自治且并发执行的组织内子流程的组合, 子流程建模为组织内本地流程定义和组织间控制约束的组合, 并利用工具MWB(mobile workbench)验证抽象正确性.为了检测协同业务过程能否正确地协调, 文献[29]提出了一种针对多个业务过程组合验证的概念框架.它将BPMN建模的协同业务过程转换以时间通信顺序进程CSP+T(communicating sequential processes+time)表示进程, 之后采用时序逻辑公式定义期望正确性性质, 并利用模型检测方法在工具FDR2(failures-divergences refinement)上自动验证正确性性质是否满足.为实现面向Web服务的流程无缝集成, 文献[30]提出了一种基于递归组合代数的Web服务交互流程建模和验证方法.首先利用递归组合代数建模Web服务流程交互, 并将其转换为递归组合交互图, 之后利用递归组合规约语言来描述需求, 并通过递归组合交互图自动地验证需求是否满足与否.

为了使得多个基于Web服务的业务过程的组合符合用户定义适配需求, 文献[31]提出一种描述及验证多业务过程间行为适配的方法.它采用LTS描述业务过程及适配器, 进而将业务过程与适配器组合来检测其是否相容以判断多业务过程的组合是否符合用户定义适配的需求.互操作是业务协同正确实施须具备的先决条件, 为确保每个参与组织的互操作是否符合规定的需求, 文献[32]首先使用BPMN来描述协同业务过程, 之后将其BPMN模型转换成模型检测工具UPPAAL中的时间自动机网络(timed automata network, 简称TAN), 并采用时序逻辑TCTL(time computation tree logic)描述互操作需求, 从而实现互操作自动检测.特别地, BPMN模型中每个参与组织业务过程在TAN中对应一个时间自动机(timed automata, 简称TA), 这些TA并发组合构成了TAN, 即协同业务过程.在后续工作中, 为了更加有效地存储和描述互操作需求, 文献[33]首先提出了一种领域描述语言用来描述互操作需求, 继而将描述需求自动转换为时序逻辑TCTL, 并采用TAN建模协同业务过程.通过UPPAAL实现互操作需求的自动验证.

上面提出的正确性检测方法通常具有检测过程自动化, 不需要人工干预, 且在检测失败时能够给出诊断信息, 便于业务设计人员发现并修正错误.但其不足是, 若协同业务过程中存在多处不正确, 则需要经过多次检测, 且在每次检测后都需要对协同业务过程重新调整.这种设计、验证、分析及纠错的过程使得协同业务过程的正确性分析变得复杂且耗时.

6.2 正确性修正方法

相比正确性检测方法, 针对业务过程正确性修正方法是较新的课题, 相关研究工作较少.文献[11, 12]针对以Artifact为中心的业务过程提出一种正确性保持的设计方法.它首先采用Petri网建模以Artifact为中心的业务过程, 之后以合规性和弱合理定义其正确性, 最后将业务过程与正确性合成以自动构建具有正确性的业务过程.文献[34]采用开放工作流网oWFN(open workflow nets)建模跨组织环境下的业务过程, 利用CTL公式定义期望正确性性质, 根据以CTL公式定义性质对业务过程内部结构进行修改来构建跨组织环境下具有正确性的业务过程.然而, 上面提出的正确性修正方法均面向组织内的单个业务过程.由于协同业务过程具有自治性、分布性及涉及多个业务过程间的同步或异步交互, 因此上面提出的方法不适用于跨组织环境下的协同业务过程.

近年来, 面向轨迹的业务过程修正方法引起一些学者的关注.文献[14]首次在国际上提出此类方法.首先利用已有的一致性检测来发现过程模型与轨迹间差异, 并将体现这些差异的轨迹从原轨迹中分离出来, 以子轨迹来加以表示.针对这些子轨迹, 构建其对应子结构并将其添加至原业务过程中, 从而完成业务过程的修正.随后, 文献[15]对文献[14]的工作进行了一些改进, 即针对一致性检测中发现的循环结构, 构建其对应的子过程并将其添加至修正模型中.文献[35]提出的修正方法沿用了文献[14, 15]的思路.针对工作流模型, 首先利用监控矩阵刻画实际工作流模型足迹, 通过比较工作流模型的轨迹与足迹间的差异, 提出4种用于修正的工作流模型算法.我们课题组最近的工作^[13]是结合Petri网和过程挖掘的相关理论, 提出一种针对协同业务过程的修正方法.该方法首先获取部分正确协同业务过程中所有完整的轨迹, 之后利用算法从这些完整的轨迹构建相容协同业务过程, 最后通过设置协同业务过程与业务过程间的任务执行同步关系以协调业务过程的正确运行.然而, 利用上述方法建立的修正业务过程仍是集中式的, 也存在修正前协同业务过程中完整轨迹可能会丢失和修正协同业务过程中可能会引入隐藏轨迹等问题.相较而言, 本文方法构建的协同业务过程是完全分布式的(即不存在中心流程), 它的执行能够正确终止且与修正前协同业务过程中含有的所有完整轨迹相一致.

面向Web服务流程的自动组合方法也是与协同业务过程正确性修正比较相关的工作.文献[36]首先裁剪合理性定义正确性(即相容性), 针对部分相容Web服务流程采用Petri网建模每个服务的流程, 然后将其进行组合并分析其相容性.若分析结果部分相容, 则产生适配器将来协调服务流程, 使之前部分相容的服务流程转换为完整相容, 且未改变原有服务流程的内部结构.为了应对服务流程间存在时序约束及消息匹配问题, 文献[37]首先采用Petri网建模每个服务的流程, 然后根据消息匹配情况及时序约束构建适配器, 从而使得所有服务的流程与适配器组合执行是正确的, 以避免出现时序异常.面向Web服务流程组合与通过传统业务过程组合建立协同业务过程的最大区别是服务使用者通常没有修改第三方服务的权限, 也不能要求服务提供者按照自己的需求修改提供的服务.因此, 针对Web服务流程自动组合通常利用适配器来实现, 而针对业务过程组合主要是由可信第三方在设计阶段修改业务过程的内部结构来实现^[36].

7 总结

在考虑活动同步及异步交互的情况下, 本文基于完整简单路径提出一种协同业务过程正确性修正方法.该方法将部分正确的协同业务过程中所有的完整简单路径合并以构建核, 通过协调映射来生成修正业务过程, 将修正业务过程并发组合建立修正协同业务过程.该方法一方面可确保修正协同业务过程符合其典型特征(如自治、分布等); 另一方面, 修正协同业务过程只含有修正前协同业务过程中所有完整简单路径对应的轨迹, 可避免有效性确认, 提高了修正效率.

未来工作主要针对以下3个方面的问题开展研究.

(1) 本文定义正确性关注控制流, 而数据流也是影响业务过程协作的一个重要因素.因此, 下一步将提出同时考虑控制流和数据流的协同业务过程正确性修正方法;

(2) 弱合理可归于一般意义上的正确性^[17], 而参与组织期望系统功能或特性可能多种多样.如何在考虑用户需求层面对协同业务过程进行修正是值得深入研究的课题;

(3) 本文方法在修正中需要首先生成协同业务过程完整简单路径, 然后合成核, 最后通过对核进行协调映射生成每个修正业务过程.在实际应用中, 由于受限于协同业务过程的状态空间, 本文方法也面临状态空间爆炸的问题.然而, 本文主要关注修正方法的有效性(即修正协同业务过程符合实际特征及修正前后完整简单轨迹保持一致)和效率(即修正耗费时间较短)问题.如何避免修正中出现的状态空间爆炸问题将在未来工作中着重加以讨论.