基于Petri网的服务流程结构健壮性判定
2018-11-01高强，胡强
高 强，胡 强
(1.山东省人大常委会办公厅信息中心,山东 济南 250011； 2.青岛科技大学信息科学技术学院,山东 青岛 266061)
0 引 言
随着云计算技术的发展，软件服务化成为了基于互联网的软件开发与部署表现出来的主要特征。通过互联网和云计算平台寻租符合自己需求的服务，是用户调用企业业务功能的一种流行方式[1]。其中，Web服务经过近30年的发展，已经逐渐成为当前企业通过互联网开发、封装和发布业务功能的主要模式。
在进行业务集成时，用户只需要按照指定的格式调用发布在云平台或者领域服务注册中心的Web服务，即可远程使用所绑定服务的内部业务功能，不需要了解Web服务的实现细节，进而极大地缩减了开发周期和成本[2]。为了便于用户调用，Web服务内部通常不包含复杂的业务逻辑。因此，在应对复杂服务请求时大多需要通过服务组合的方式构建服务流程[3]。
已有研究工作中提出了众多的服务组合方法[4]，通过上述成果可以构建适用不同应用场景的组合服务流程。例如，Lu等[5]提出一种基于知识约束规则推理的云服务资源组合方法；朱李楠等[6]提出基于改进差分进化算法的云制造资源优化组合方法；Ye等[7]提出基于贝叶斯网络经济模型的云服务组合，以及崔立真等[8]提出面向历史流程轨迹与个性偏好的流程动态定制方法等。
在构建了组合服务流程后，流程的结构健壮性直接影响到了组合服务流程的结构质量和执行效果。在流程健壮性方面，研究者从不同角度给出健壮性的定义和判定方法。例如，Clempner[9]提出一种基于轨迹跟踪方法检测流程健壮性的规则，Du等[10]提出一种基于流程交互行为的健壮性判定标准。Martens[11]提出了一种基于流程可用性的弱健壮性概念，Fahland等[12]将健壮性定义为流程不存在死锁和同步缺失。余阳等[13]从结构的自由同步与良构等角度研究了时态工作流过程模型的结构合理性。胡强等[14]针对组合服务流程的结构合理性提出了结构范式概念，并基于逻辑Petri网建立了不同级别结构范式的判定方法。
然而，已有的研究工作通常仅对健壮性给出定性评价，缺乏对服务流程的结构健壮性分层次定量评价，因此难以精准评价流程结构质量[15]。
本文针对组合服务流程的结构健壮性判定问题，采用Petri网作为服务流程建模的形式化工具，借鉴工作流网的健壮性判定思想，提出一种基于Petri网建模的服务流程结构健壮性分层定量判定方法。
1 服务网及相关理论
定义1Petri网[16]。
Petri网是一个四元组S=(P,T,F,M)，P为库所集合，T为变迁集合，且P∩T=；F(PT)(TP)是弧的集合，映射M:P={0,1,2,…}是Petri网的标识函数，表示了库所中的托肯数目，变迁触发后可以通过如下公式计算：
定义2服务网[17]。
服务网定义为四元组SN=(S, i, o, L)，各组成项含义如下：
1)S是组合服务流程的过程模型，其中：①P=Pc∪Pd，Pd是表示与外部进行数据交换的数据库所集合，Pc是控制库所集合；②T是服务流程对应的Web服务集合；③F是服务状态流程转换弧的集合；④M为标识函数，初始标识为M0，即M0(i)=1。
3)L:T→Θ为标记函数，Θ为操作函数名称的集合。
定义3服务进程网。
若SN=(S, i, o, L)为服务网，令SPN=(S′,i,o,L),其中P′=Pc,T′=T,F′=F-{PdT∪TPd}，则SPN称为SN的服务进程网。
图1 服务网及服务进程网示例
定义4等价服务流程。
SN1=(S1, i1, o1, L1)和SN2=(S2, i2, o2, L2)为2个服务网，SN1和SN2称为等价服务流程当且仅当存在映射使得以下条件成立：
定义5投影服务流程。
SN=(S, i, o, L)为一服务网，SN′=(S′, i′, o′, L′)称为SN的投影服务流程，当且仅当F′=F∩S′,P′=P∩(1(F′)∪2(F′)),T′=T∩(1(F′)∪2(F′)),L′=Θ(T′)，表示为SN′=S(SN)。此处，1和2定义如下:1(F)={x|y:(x,y)F},2(F)={y|x:(x,y)F}。
定理1
令SN1′=S(SN1),SN2′=(SN2),若SSN1.则
证明：
令S2=T2=P2=;
{S2=S2∪((x),(y)); T2=T2∪((x,y)(SN1′).T); P2=P2∪((x,y)(SN1′).P);}
令L2=Θ(T2),(S)=S2,SN2′=(P2,T2,S2,L2);
[证毕]
2 结构健壮性的层次划分及其判定
目前，有关流程结构健壮性的研究均是采用定性判定的方式。就组合服务流程而言，仅仅以是否健壮来评价服务流程的结构质量是不完善与不合理的。因此，本文提出将服务流程的结构健壮性划分为4个层次，并给出4个层次健壮性的判定算法。下面首先给出4个层次的结构健壮性划分准则：
1)1LS：服务流程S是第一层次健壮的，当其对应的服务网SN中i至o库所存在一条可达路径。
2)2LS：服务流程S是第二层次健壮的，当其对应的服务网SN中i至o库所的任意路径可达。
3)3LS：服务流程S是第三层次健壮的，当其对应的服务网SN是2LS，且不存在重复的并发或选择服务流程。
4)4LS：服务流程S是第四层次健壮的，当其对应的服务网SN是3LS，且不存在重复子服务流程。
在上述4个层次的健壮性划分中，第一层次是要求服务流程存在可达的连通路径，该层次可以确保服务流程存在可以对外提供服务的业务流程路径；第二层次健壮性则是保障了服务网中的所有业务流程功能路径是可以执行的；第三层次保障在并发和选择结构中不存在冗余服务流程结构；第四层次则是要求服务流程中不存在重复服务流程，对重复的服务流程应该将其抽象为子服务流程替代，从而保证结构的清晰与简洁。
在进行服务流程的健壮性判定时，首先要建立服务流程所对应的服务网模型，目前组合Web服务流程多采用WS-BPEL进行描述[18]。为了获得服务流程的服务网模型，需要对给定服务流程的WS-BPEL文件进行遍历，具体转换规则如图2所示。
图2 WS-BPEL与服务网之间的映射规则图
算法1为服务流程结构健壮性层次判定算法。在该算法执行的过程中，首先调用Petri网的活性判定算法[19]。如果服务流程对应的服务网为弱活的，则为第一层次健壮性；若对应的服务网是活的，则是第二层次健壮性。然后，对服务流程文件中所有存在的switch、if、pick以及flow结构进行检测，验证是否存在冗余的子流程结构。如不存在，则是第三层次健壮性。最后，检验是否存在重复子流程。若不存在，则是第四层次健壮性。
算法1服务流程结构健壮性判定算法
SoundnessLevel(S)
输入：WS-BPEL格式描述的服务流程S
输出：S的结构健壮性层次
{construct the service net SN of S;
Invoke the live determination algorithm of Petri net
if (SN is weaklive) then LS:=1;
if (SN is live) then LS:=2;
for each structure F in {switch, if, pick, flow}
for each substructure fi and fj in F
if (flag1=true) then LS:=3;
for all the substructure in S
if there is no repetitive one then LS:=4;
return LS;
}
3 算 例
本章以网上在线交易系统所对应的服务流程为例，说明不同服务流程的结构健壮性层次。图3给出了交易系统的业务逻辑示意图，图3左侧部分为卖家流程，右侧部分为买家流程。买家流程业务逻辑为：查询商品，如果不存在满足需求的商品则处理失败；如存在，则触发预定、购买和接收商品流程。
图3 第四层次健壮性服务网
卖家流程业务逻辑为：接收用户查询，查询库存，如果不存在对应商品则查询失败；否则，接收预定、付款，快递商品。按照算法1可知，图3所对应的服务流程的结构健壮性为第四层次。在图4中，所有的业务分支逻辑均与图3相同，但是买家和卖家使用了相同的子流程，即book-pay-delivery。因此，图4中的服务流程结构健壮性为第三层次。
图4 第三层次健壮性服务网
图5 第二层次健壮性服务网
图6 第一层次健壮性服务网
如果在卖家服务流程中增加一个子服务流程：reserve-defray-express，则reserve-defray-express与book-pay-delivery子流程并发冗余，因此图5中的服务流程结构健壮性为第二层次。
如果将子流程reserve-defray-express更换为reserve-express-defray，则该流程仍是第三层次健壮。图6中的服务流程与图3相似，但是在买家流程中将express与defray服务交换，形成死锁。因此，并不是所有路径均可达，其流程结构健壮性为第一层次。
4 结束语
服务流程的结构健壮性决定了组合产生的Web服务业务流程的结构质量，是Web服务组合研究中的一个重要问题。本文借助于Petri网将WS-BPEL描述的组合服务流程建模为服务网，根据流程的可达性与冗余性，提出了4个层次的服务流程结构健壮性，并借助服务网的结构性质进行表征。文中给出了不同层次结构健壮性的判定算法，并通过网上在线交易服务流程为背景，给出不同层次结构健壮性的算例。下一步工作主要是研究不同级别的结构健壮性在流程业务演化过程的健壮性级别保持问题。
