基于Petri 网的服务组合模式的提取＊

叶荣华，陈志娟

(浙江师范大学 数理与信息工程学院，浙江 金华 321004)

0 引言

随着Web 服务技术的发展，通过服务组合来满足用户需求已经成为必然趋势［1］.服务组合是指基于面向服务的体系结构(SOA)，根据特定的业务目标，将多个已经存在的服务按照其功能、语义及它们之间的逻辑关系组装提供聚合功能的新服务的过程，是面向服务计算(SOC)泛型中实现资源聚合与应用集成的主要模式［2］.

服务组合按照组合生成方式的不同，可以分为静态组合与动态组合2 种模式.静态组合［3-4］意味着请求者应在组合计划实施前先创建一个抽象的过程模型，包括任务的集合及任务间的数据依赖关系.动态组合则要实现自动选择、绑定Web 服务，更重要的是自动地创建过程模型［5-6］.本文从静态组合的角度研究服务组合，也就是侧重于半自动方式［7-8］的实现，首先建立组合流程模型，然后对模型中各抽象任务自动地绑定调用实例［1］.

文献［9］结合环境本体和Petri 网，实现对数据语义、功能语义及执行语义的描述，将需求建模成一个类Petri 网，但对于其中意图间的关系定义不够完善;另外，只对服务是否满足需求判定，也未给出具体的服务组合模式的内容和其他满足需求的服务组合模式.因此，本文在此基础上展开工作，首先通过完善意图间的互斥关系改进需求模型，接着对建模成的服务组合需求模型进行分析，重点是为求解满足需求的所有可行的服务组合.

1 服务组合需求模型

1.1 环境本体

在基于环境本体的服务描述中，服务功能描述为服务于环境交互而引起的环境变化.环境指的是可与服务发生交互的一组环境实体的集合.环境实体可以是现实世界的任何实体，可以是物理的也可以是抽象的［10］.环境实体可分为3 类:自主实体、可控实体和符号实体，并通过给每一个实体加入1 个类树层次状态机来描述它们的动态属性，刻画了这些实体的状态和相互之间的关系［11］.

定义1 环境本体(Environment Ontology，EO):定义为一个六元组{Ent，R，rel，HSM，EXCH，res}，其中:Ent 是一个环境实体的集合，一个环境实体可以表示为〈id，Attr，Rans，values〉，id 是实体的标识，Attr是实体的属性向量，Rans 是一个属性值的向量，values:Attr→Rans 是实体属性向其值向量幂集的一个映射;R 是一个关系的集合;rel:r→Ent ×Ent 表示环境实体之间的关系函数，如，设a1，a2∈Ent，r∈R，则rel(r)=(a1，a2)表示a1和a2具有关系r;HSM 是层次状态机，它是一个类树层次状态机的有限集合;EXCH⊆HSM×HSM 是HSM 之间的一种消息交换关系;res:Ent←→HSM 是环境实体与层次状态机的一一对应关系.

1.2 意图

在环境本体的描述下，用户的需求可以从某一状态到另一状态发生改变.如果一个服务可以使一个实体从一个状态变迁到另一状态，那么可以说这个服务能满足这个实体的一个意图.接下来将给出意图的定义，并根据它们之间的关系，定义意图上的二元关系.

定义2 可达状态(Reachable State):对于状态rx，ry∈HSM，若存在一个状态集{ri| ri∈HSM(0≤i≤n)}，使得〈rx，r1，r2，…，rn，ry〉是HSM 的一个可能的状态变迁序列，则称ry是rx的可达状态.

定义3 意图(Intention):设CE 是领域环境本体中的一个可控环境实体集，r∈CE，则一个r 上的意图是一个四元组(s0，st，I，O).其中:s0∈r.HSM 为初始状态;st∈r.HSM 为目标状态，且st是s0的可达状态;I∈r.HSM 是输入信息的有限集，它表示要实现意图需提供的输入;O∈r.HSM 是输出信息的有限集，它是意图效果的一部分.将一个可控实体r 上的意图e 记作r:e，其中一个实体上可以有多个意图，即r:(e1，e2，e3，…，en).

这里将用户的需求看作是若干个意图，这些意图必须是初始状态的可达状态，否则意图将没有意义，而这些意图之间又存在着某种关系，接下来对这些意图进行分类.

大部分意图的发生不会影响其他意图的发生与否，即它们是相互独立的.但还有一些意图之间往往存在着某种联系，例如对于一个“订单”实体的“付款”意图(即根据一些输入订单实体从未付款状态转变为已付款状态，并得一些输出)与一个“信用卡”实体的“支付”意图是相关联的.容易看出，两者要么同时实现要么都不实现，否则会导致不一致.

定义4 关联意图(Associated Intention):设CE 是领域环境本体中的可控实体集，r1，r2∈CE.若存在r1:ei和r2:ej，使得ei，ej必须全部发生或全部不发生，则称ei，ej是关联意图，记作A(r1:ei，r2:ej)或r1:eiAr2:ej.

不难看出，意图之间的关联关系满足自反性和对称性，但不一定满足传递性.例如，在旅游安排时，“飞机票”实体的“付款”意图与“信用卡”实体的“支付”意图是相关联的，类似地，“火车票”实体的“付款”意图与“信用卡”实体的“支付”意图也是相关联的.如果满足传递性，那么“飞机票”实体的“付款”意图与“火车票”实体的“支付”意图也是相关联的.事实上，在计划旅游时，选择了飞机就不可能再选择火车，两者只可能发生其中的一个.因此，意图的关联关系不满足传递性.

定义5 将集合E 上的二元关系R 定义为E 上的相容关系［12］，并记为〈R〉，如果满足下述条件:

1)R⊆E×E;2)R 满足自反性;3)R 满足对称性.

由此可知，意图集上的关联关系满足上述条件，从而关联是相容的.

1.3 任务

定义6 任务(Task):设E 为意图集合，有A⊆E×E 且〈A〉，记为ti=Ei，如果满足下述条件:

1)Ei⊆E;2)∀em∈Ei，∀en∈Ei，都有A(em，en);3)∀ep∈E-Ei，∀em∈Ei，都没有A(ep，em).

上述条件中，1)说明Ei是E 的一个子集;2)说明任务集合中的所有元素(意图)都满足二元关系A;3)表示在意图与任务的差集中，找不到一个意图，与任务中的意图满足二元关系A.

一般来说，在约定条件下，用示意图更为简洁而不致引起混淆.根据集合论中的自全相容类［12］有如下求解任务的方法:

1)图中任一完全的多边形的结点的集合是一个任务;

2)每一个孤立的结点也是一个任务;

3)不在完全多边形上的任一条边的2 个端点的集是一个任务.

例如，设有意图集E={e1，e2，e3，e4，e5}，在意图集E 上的关联关系A={(e1，e2)，(e1，e4)，(e2，e4)，(e2，e3)，(e2，e5)，(e2，e1)，(e3，e5)，(e3，e2)，(e4，e1)，(e4，e2)，(e4，e5)，(e5，e2)，(e5，e3)，(e5，e4)，(e1，e1)，(e2，e2)，(e3，e3)，(e5，e5)，(e4，e4)}.〈A〉⊆E×E 的关系示意图如图1 所示.

图1 E 上关系R 的示意图

由以上方法不难得出，E1={e1，e2，e4}，E2={e2，e3，e5}，E3={e2，e4，e5}都是E 的任务，记为E1=t1，E2=t2，E3=t3.

如此，根据意图的关联关系，将意图分为若干个子集，即为若干个任务，其中每个任务中的元素(意图)都满足意图的关联关系.此时，用户的需求由一个庞大的意图集划分为若干任务组成的任务集，而每个任务可能有多个意图，也有可能只有一个意图.将任务看成是服务组合中的一个原子单位，每个任务必须由单个服务来完成.

1.4 服务组合需求的Petri 网模型

定义7 组合服务需求(Composition Service Requirement，CSR)是一个带标识的Petri 网系统五元组(P，T;F，M0，Mt).其中:P 是一个有限的库所集合;T 是一个有限任务的集合;F⊆(P ×T)∪(T ×P)是连接库所和任务之间的有向弧集;M0是Petri 网的初始标志;Mt是目标标识.M0到Mt必须是可达的，表示这个需求在功能上是可实现的.其中Petri 网中的库所容量为1，任务发生的权值为1，是一个基本网系统(Elementary Net System)［13］.

2 需求模型的组合模式求解

接下来对需求模型的可达性进行分析，它是Petri 网的最基本的动态性质，其余各种性质都要通过可达性来定义.但是，由于模型的状态空间与系统的结构大小是呈指数增长的关系，这将导致组合的激增.为限制这种激增，现对Petri 网模型进行简化处理.

2.1 服务组合需求模型的简化

Petri 网任务的发生是由令牌触发的，当令牌从一个输入库所被任务转移到输出库所的时间不被考虑时，就可以对Petri 网进行简化.在此基础上，根据Petri 网的特点可以确定以下库所的吸收规则［14-15］.

图2 原始模型

凡是只有一个输入和输出的中间库所都可以被吸收，并将下一级的任务合并到上一级.图2 和图3 为这条吸收规则的简单示意图，其中Pj满足库所吸收的规则，被吸收后，将下一级任务合并到上一级，得到一个新的任务.

图3 库所吸收后的模型

定义8 线性任务(Linear Task，LT):定义为一组满足库所吸收规则，吸收合并后的新任务LT=〈ti，tj，…，tk〉.

经过库所的吸收规则对Petri 网进行吸收处理后，中间库所和变迁的数量大大减少.由于对Petri 网中的路径的求解过程的复杂度与中间库所的数量是呈指数关系的，因此，对于规模较大且满足吸收规则的系统模型进行吸收处理是很有意义的，节省了大量的计算量.

2.2 组合模式求解算法

对于Petri 网(P，T;F，M0，Mt)，有如下的任务发生规则［14］:

1)对于任务t∈T，若∀p∈·t，M(p)≥1，则称M 授权(enable)t 发生，或t 是使能的(enabled)，记作M［t〉;

2)若从M 发生t 得到的新标识为M′，则对∀p∈P，有

记为M［t〉M′.其中:·t 表示任务的前件;t·表示任务的后件.

定义9 设N={P，T;F，M}是一个Petri 网.若存在t∈T，M［t〉M′，则称M′为从M 直接可达的;若存在任务序列t1t2…tk和标识序列M1M2M3…Mk，使得M［t1〉M1［t2〉M2…Mk-1［tk〉Mk，则称Mk是从M可达的.从M 可达的一切标识的集合记为R(M).若记变迁序列t1t2t3…tk为σ，则可将M［t1〉M2［t2〉M2…Mk-1［tk＞Mk记为M［σ〉Mk.

服务组合需求模型是一个动态的有向图，库所中的令牌随着任务的发生，从输入库所向输出库所流动，从而引起标识的变化，推动网系统的进化.接下来根据文献［14］构造一个以初始标识为根结，在有发生权的任务的推动下，产生以标识为节点的可达树(Reachable Tree)的算法.

算法1 Petri 网的可达树的构造算法

输入:CSR=(P，T，F，M0，Mt);

输出:RT(CSR);

Step1:根据库所吸收规则，对原模型进行简化;

Step2:以M0作为RT(CSR)的根结点，并标之以“新”;

Step3:while 存在标注为“新”结点，Do 任选一个标注为“新”的结点，设为M;

Step4:If 从M0到M 的有向路上有一个结点的标识等于M Then 把M 的标注改为“旧”，转入Step3;

Step5:If M=MtThen 把M 的标识改为“端点”，转入Step3;

step6:For 每个满足M［t〉的t∈T Do

1)计算M［t〉M′中的M′;

2)在RT(CSR)中引入一个“新”结点M′，从M 到M′画一条有向弧，并在此弧旁边标以t，擦去结点M 的“新”的标注，转入Step3.

算法1 从初始标识开始，对Petri 网系统进行运行，将每次发生任务产生的新的标识作为子结点，直到运行到叶子结点为目标标识位置为止.文献［15］对这个算法的可终止性给出了证明.

由算法1 得到与Petri 网对应的可达树，其中叶子结点的数量就是服务组合模式的数量，每一个结点表示网系统可能出现的一个状态，从一个结点到另一个结点表示，从当前状态经过有发生权的任务将转化为下一个状态.通过对可达树的深度优先遍历得到从初始标识到目标标识的每段弧上的任务组成的任务集，这样的一个任务集即为需求服务组合的一个服务组合模式.

算法2 需求模型的组合模式提取算法

输入:RT(CSR);

输出:T

Step1:访问RT(CSR)的根结点，并标之以“已访问”;

Step2:while 存在标注为“已访问”的结点Do

深度遍历其子结点，并标之以“已访问”，同时输出指向子结点弧上的任务.

算法2 是一个递归算法，通过深度遍历可达树，输出从根结点到叶子结点弧上的任务的集合.

表1 Petri 网模型中的任务形式表达

3 案 例

3.1 案例说明

利用上述算法，求解一个旅游安排的可行路径集.一位旅客计划利用一段时间去旅游，他的旅游安排如下:先到景点A，再到景点B.到景点A，可以坐飞机或者是火车，如果乘飞机，订的飞机票要快递到自己处，还要在景点A 附近订个酒店.从景点A 到景点B，可以坐火车或者汽车，在景点B 附近也要订个酒店，此处的酒店需支付押金.所有的消费由信用卡支付.

根据以上描述，可以抽象出实体上意图及任务的具体对应关系，如表1 所示.

图4 CSR_Travel Arrange 的Petri 网结构

表1 给出了任务的含义，然后将这些任务根据逻辑构建成旅游安排(CSR_Travel Arrange)的组合服务需求的Petri 网结构，如图4 所示.

由图4 易知，由初始结点p1到p6的状态变化过程完成了到达景点A 的任务，从p6到p11完成了到景点B 的任务.

3.2 服务组合模式求解过程

根据算法1 第1 步对原模型进行简化，对模型中的库所进行吸收处理，得到如图5所示的需求模型.

根据简化后的需求模型构造可达树的过程，如图6 所示.

图5 简化后的需求模型

由可达树的叶子结点可知，可行路径有4 条.由算法2 可知，其中一个从根节点到叶子结点的遍历为:(1，1，0，1，0)［{t1，t2，t3，t6}〉(0，0，1，1，0)［{t7，t8，t11，t12}〉(0，0，0，0，1)，即M0［{t1，t2，t3，t6，t7，t8，t11，t12}〉Mt，从而{t1，t2，t3，t6，t7，t8，t11，t12}为其中一条可行路径.由此可得出，CSR_Travel Arrange 的所有服务组合模式为:{t1，t2，t3，t6，t7，t8，t11，t12}，{t1，t2，t3，t6，t9，t10，t11，t12}，{t4，t5，t6，t7，t8，t11，t12}，{t4，t5，t6，t9，t10，t11，t12}.

图6 可达树的构建过程

4 结语

本文以环境本体作为基础，结合Petri 网的相关理论，将服务组合需求模型建模成一个动态网系统.其中定义了意图关联的二元关系，给出了求解任务的方法.根据库所吸收规则，简化了服务组合需求模型.结合模型运行过程中标识和任务的变迁情况，提出了构造可达树的算法.通过深度遍历可达树得出需求模型的所有服务组合模式.最后，用经典案例说明了算法的实用性以及简便性.

［1］范小芹，蒋昌俊，王俊丽，等.随机Qos 感知的可靠Web 服务组合［J］.软件学报，2009，20(3):546-555.

［2］黄蓝会.动态服务组合的研究［J］.价值工程，2012(1):154.

［3］Patia W，Wil M P，Marlon D，et al.Analysis of Web services composition languages:the case of BPEL4WS［C］//Proceedings of the 22nd International Conference on Conceptual Modelling (ER).Chicago:Springer，2003:200-215.

［4］Orriëns B，Yang Jian，Papazoglou M P.Model driven service composition［J］.Lecture Notes in Computer Science，2003，2910:75-90.

［5］Mediahed B，Atif Y.Context-based matching for Web service composition［J］.Distributed and Parallel Databases，2007，21(1):5-37.

［6］Medjahed B，Bouguettaya A，Elmagarmid A K.Composing Web services on the semantic Web［J］.The VLDB Journal，2003，12(4):333-351.

［7］Benamllah B，Dunlas M，Sheng Q Z，et al.Declarative composition and peer-to-peer provisioning of dynamic Web services［C］//Agrawal R，Dittrich K，Ngu A H.Proc of the 18th Int′ l Conf on Data Engineering.San Jose:IEEE Computer Society，2002:297-308.

［8］Zeng Liangzhao，Benatallah B，Dumas M.Quailty driven web service composition［C］//Ellis A，Hagino T.Proc of the world wide web.Budapest:ACM，2003:41l-421.

［9］叶荣华，金芝，钟发荣.支持服务组合的需求模型及其可满足性判定［J］.计算机科学与探索，2011，5(5):458-466.

［10］Liu T S，Chiou S B.The application of Petri nets to failure analysis［J］.Reliability Engineering and System Safety，1997，57(2):129-142.

［11］王璞巍，金芝，刘红岩.网构软件实体的功能描述及其发现［J］.中国科学:A 信息科学，2009，39(12):1271-1287.

［12］朱梧槚，肖奚安.集合论导论［M］.大连:大连理工大学出版社，2008.

［13］袁崇义.Petri 网原理与应用［M］.北京:电子工业出版社，2005.

［14］吴哲辉.Petri 网导论［M］.北京:机械工业出版社，2006.

［15］Peterson J L.Petri 网理论与系统理论［M］.吴哲辉，译.徐州:中国矿业大学出版社，1989.