高 新，方贤文，许志才，2

（1.安徽理工大学 信息与计算科学系，安徽 淮南232001；2滁州学院 数学系，安徽 滁州239012）

0 引 言

实际应用中Web服务组合的正确性不仅受到其他Web服务的约束，也受到Web环境的约束。由于Web环境的特殊性，很难用传统的方法进行建模和分析，因此研究Web环境约束下Web服务组合的正确性需要采用新的建模工具和分析方法。

传统的Web服务组合研究一般情况下只注重服务组件之间的约束和组合关系，而忽略了服务组件和Web环境之间的约束和组合关系。而实际情况是Web服务组合的正确合理与否和Web环境关系巨大，例如，多个Web服务组件组成了视频流媒体的Web服务，这个服务要想成功运行就必须依靠高带宽的Web环境约束。因此对Web服务和Web环境组合后的正确性的判定就显得愈发重要，也成为新的研究重点。

文献 ［1－2］对电磁、带宽环境对移动网络服务发现的影响做了相关研究并提出了环境影响服务正确性的观点，但是缺乏严格的形式化模型；文献 ［3］通过服务树等理论服务的组合建立了形式化的模型并对其合理性进行了判定，但是忽略了环境因素。

为解决上述不足，提出了Web服务域和Web环境域的概念，并采用open Petri net（OPN）对Web服务域和Web环境域进行建模。然后通过OPN给出Web服务域和Web环境域组合的充分条件以及组合后保持正确性的若干判定算法，最后通过实例验证这些判定算法的正确性和有效性。

1 基本概念

目前，研究人员从不同的角度对Web服务组合进行了定义。在Web服务组合技术研究方面，目前主要的服务组合技术包括工作流、AI规划、规则推理、定理证明等。本文中采用的Web服务组合是通过把一些单个的功能单一的Web服务联合起来以增值服务为目的的过程。

Web环境主要包括3部分：用户环境、计算环境、物理环境。Web环境不能提供真实的服务，但是Web环境对Web服务的组合、运行、正确性都会产生影响，把Web环境对Web服务的这种影响称为环境约束。

定义1 Web服务域 （service domain）是一个四元组SD＝ （SI，SO，SC，CI），其中SI是服务输入端，SO是服务输出端，SC是服务组件，CI是通信接口。

定义2 Web环境域 （environment domain）是一个四元组ED＝ （EI，EO，EC，CI），其中EI是环境输入端，EO是环境输出端，EC是环境组件，CI是通信接口。

定义3［4－5］满足下列条件的三元组N＝ （S，T；F）称作一个Petri网：

（1）S∪T≠

（2）S∩T＝

（3）F（（S×T）∪ （T×S））

（4）dom（F）∪cod（F）＝S∪T

dom（F）＝ ｛x∈S∪T｜-y∈S∪T：（x，y）∈F｝

cod（F）＝ ｛x∈S∪T｜-y∈S∪T：（y，x）∈F｝

定义4［6－8］满足下列条件的七元组OPN＝ （P，I，O，T，F，i，f）称作一个open petri net：

（1）（P∪I∪O，T，F）是一个petri网；

（2）P是内部库所的集合，T是变迁的集合，F是库所和变迁之间弧线的集合；

（3）I是输入库所的集合，且·I＝；O是输出库所的集合，且·O＝；

（4）i是初始标识；f是终止标识。

I∪O称作OPN的接口库所；两个OPN分别为M和N，如果PM，PN，IM，IN，OM，ON，TM，TN两两不相连，则网M和网N不相连。

定义5 设 Web服务域SD＝ （SI，SO，SC，CI），环境域ED＝ （EI，EO，EC，CI）和OPN＝ （P，I，O，T，F，i，f），如果SIi，SOf，SCP，CII∪O，SI则称SD能映射到OPN上。如果EIi，EOf，ECP，EII∪O，则称ED能映射到OPN上。

Web环境和Web服务通过接口库所进行通信，从而形成了一个结构和行为上都相互关联的整体。由于Web服务和Web环境进行了通信，那么Web环境必然会对Web服务的行为产生约束，这种约束主要通过组合后服务的正确性来反映。

2 基于OPN的Web环境约束下的Web服务组合正确性分析

Web环境约束下的Web服务组合正确性分析主要有两方式：①单个Web环境／Web服务均满足合理性，可通过组合后整体的合理性来确定正确性。②单个Web环境／Web服务不满足或不考虑合理性，则可通过组合后整体有无死锁来确定正确性。

Web环境对Web服务产生约束的前提是Web环境和Web服务进行了组合，因此先要判定Web环境和Web服务能否组合。

定义6［9－11］：设A和B是两个OPN，A⊕B表示A和B的组合，A⊕B也是一个OPN，其中：

（1）P＝PA∪PB∪ （IA∩OB）∪ （IB∩OA）

（2）I＝ （IA＼OB）∪ （IB＼OA）

（3）O＝ （OA＼IB）∪ （OB＼IA）

（4）T＝TA∪TB

（5）F＝FA∪FB

（6）i＝iA∪iB

（7）f＝fA∪fB

A和B是两个OPN，若 （PA∪IA∪OA∪TA）∩ （PB∪IB∪OB∪TB）＝ （IA∩OB）∪ （OA∩IB）成立；则A、B能够组合。

2.1 Web服务域／Web环境域组合后整体满足

合理性的判定

定义7［12－15］OPN的合理性：N是个OPN，若一个petri网S（N）＝ （PN，TN，F），其中F＝FN∩ （（PN×TN）∪（TN×PN））。则称S（N）为N的一个核心网，若任意一个M∈R（N），都有则N满足合理性。

很多情况下，多个Web服务域要共用一个Web环境域。在图1中服务域A和服务域C共用环境域B。服务域A和环境域B组合后，满足合理性；服务域C和环境域B组合后，也满足合理性；但服务域A、环境域B以及服务域C组合后，则不满足合理性。

图1 A⊕B、B⊕C合理，A⊕B⊕C不合理

定义8［7－8］ΩA，B，A和B是两个能够组合的OPN，当且仅当m∈R（A⊕B）σ成立，则称ΩA，B成立。A和B是两个能够组合的OPN如果A满足合理性且满足条件ΩA，B，则A⊕B也满足合理性。A，B，C是3个两两相连的OPN，即A和C没有直接相连的接口库所，如果A⊕B满足合理性，且ΩB，C成立。那么A⊕B⊕C也满足合理性。

算法1：3个Web服务域／Web环境域组合后整体满足合理性的判定

输入：Web服务域SD1＝ （SI，SO，SC，CI），Web环境域ED＝ （EI，EO，EC，CI），Web服务域SD2＝ （SI，SO，SC，CI）。

输出：判定结果

（1）根据定义5，把SD1＝ （SI，SO，SC，CI），ED＝（EI，EO，EC，CI），SD2＝ （SI，SO，SC，CI）映射到 OPN：WebopnA，WebEnviropnB和WebopnC；然后执行步骤 （2）。

（2）根据定义6，若 （PA∪IA∪OA∪TA）∩ （PB∪IB∪OB∪TB）＝ （IA∩OB）∪ （OA∩IB）和 （PB∪IB∪OB∪TB）∩ （PC∪IC∪OC∪TC）＝ （IB∩OC）∪ （OB∩IC）都成立，则A、B、C能够组合，且A、B、C组合后的OPN是A⊕B⊕C，然后执行步骤 （3）；否则算法终止，返回不满足合理性。

（3）若A⊕B满足合理性的要求则执行步骤 （4）；否则算法终止，返回不满足合理性。

（4）根据定义9，如果ΩB，C成立则执行步骤 （5）；否则算法终止，返回不满足合理性。

（5）A、B、C组合后的A⊕B⊕C满足合理性的要求，判定算法结束，返回满足合理性。

实际应用中，Web服务域／Web环境域的组合的数量很大、方式也很复杂，因此对多个Web环境域／Web服务域组合后的合理性进行判定十分必要。

算法2：多个Web服务域／Web环境域组合后合理性的判定

输入：D1，……Dn是Web环境域／Web服务域

输出：判定结果

（1）根据定义5，把D1，……Dn映射到对应的OPN：A1，……An上。执行步骤 （2）。

（2）根据定义6，如果 （Pi∪Ii∪Oi∪Ti）∩ （Pi（c）∪Ii（c）∪Oi（c）∪Ti（c））＝ （Ii∩Oi（c））∪ （Oi∩Ii（c））都成立，则A1，……An能够组合，然后执行步骤 （3）；否则算法终止，返回不满足合理性。

（3）把A1，……An构造成以A1为父节点的域林，其中c：｛2，……n｝→ ｛1，……n－1｝，i∈｛2，……n｝：c（i）＜i； 1≤i＜j≤n：i＝c（j）IAi∩OAj≠θ∨OAi∩IAj≠θ。执行步骤 （4）。

（4）A1，……An是以A1为父节点的域林，如果A1满足合理性且ΩAi，Ai（c）成立；则A1⊕……⊕An也满足合理性的要求，执行步骤 （5）；否则算法终止，返回不满足合理性。

（5）A1，……An组合后满足合理性的要求，判定算法结束，返回满足合理性。

2.2 多个Web服务域／Web环境域组合后整体

无死锁的判定

当单个Web服务域／Web环境域不能够满足或不需要满足合理性时，则可以用服务组合后整体无死锁的方式来判定组合后的正确性。

算法3：Web服务域／Web环境域组合后整体无死锁的判定

输入：Web服务域SD＝ （SI，SO，SC，CI），Web环境域ED＝ （EI，EO，EC，CI）。

输出：判定结果

（1）根据定义5，把SD＝ （SI，SO，SC，CI），ED＝（EI，EO，EC，CI）映射到成对应的 OPN：WebopnA和WebEnviropnB上；然后执行步骤2。

（2）根据定义6，如果 （PA∪IA∪OA∪TA）∩ （PB∪IB∪OB∪TB）＝ （IA∩OB）∪ （OA∩IB）成立，则 A、B能够组合且A和B组合后的OPN是A⊕B，然后执行步骤 （3）；否则算法终止，返回不满足正确性。

（3）求出A⊕B的关联矩阵：A（A⊕B），A⊕B的初始状态为M0。

（4）MX是要求能够达到的一个运行状态，MX∈R（M0），若求得存在非负向量 X，使得MX＝M0＋（A（A⊕B））TX成立，则执行步骤 （5）；否则算法终止，返回不满足正确性。

（5）如果存在变迁序列使得M0到MX可达，执行步骤（6）；否则算法终止，返回不满足正确性。

（6）WebopnA和WebEnviropnB组合后含有MX标识的库所不是死锁。判定算法结束，返回满足正确性。

3 实例分析

前面主要对Web环境域／Web服务域组合后的合理性和无死锁进行判定。这章通过实例对上述判定算法进行验证和分析。

Web提供高清视频点播服务 （由节目频道、节目内容、节目集数的服务组件组合而成），高清视频需要占用大量的带宽资源，所以需要带宽这个物理环境对高清视频点播服务进行约束，才能得到合理的高清视频点播服务。同时，Web还提供新闻语音直播服务 （由频道、语种等服务组件组成），直播具有实时性的特点，所以需要时间这个逻辑环境对新闻语音直播服务进行约束，才能得到合理的新闻语音直播服务，如图2所示。

图2 Web环境约束下的Web服务的组合

为了验证高清视频点播服务、新闻语音直播服务在环境域的约束下能够都实现合理的服务行为，首先通过OPN进行建模。把高清视频点播服务域、Web环境域和新闻语音直播服务域分别映射到OPN：N1，N2，N3上。其中i1、i2、i3分别为初始库所，均有一个初始标识；f1、f2、f3分别为终止库所；p1、p2、p3、p4、p5、p6分别为内部库所；o1、o2、o3分别为输出接口库所；i1、i2、i3分别为输入接口库所。需要说明的是N1中的o1在N2中等价于i2，N1中的i1在N2中等价于o2，N2中的o2在N3中等价于i3，N2中的i2在N3中等价于o3，如图3所示。

图3 服务域N1、环境域N2和服务域N3

然后把N1和N2进行组合，因为满足 （PA∪IA∪OA∪TA）∩ （PB∪IB∪OB∪TB）＝ （IA∩OB）∪ （OA∩IB）条件，所以N1、N2能够组合。N1满足合理性且N1、N2满足ΩN1，N2所以N1⊕N2满足合理性。再把N3跟N1⊕N2进行组合，由于N1⊕N2满足合理性且ΩN2，N3成立，根据判定算法1得出N1⊕N2⊕N3也满足合理性，如图4所示。

最后用可达标识来对N1⊕N2⊕N3的合理性进行验证：

M： （i1，i2，i3，p1，p2，p3，p4，p5，p6，p7，p8，p9，p10，f1，f2，f3）

M0：（1，1，1，0，0，0，0，0，0，0，0，0，0，0，0，0）

M1：（0，1，1，1，1，1，0，0，0，1，0，0，0，0，0，0）

M2：（0，0，1，1，1，1，1，0，0，0，1，0，0，0，0，0）

图4 N1⊕N2⊕N3

M3：（0，0，0，1，1，1，1，1，1，0，0，0，0，0，0，0）

M4：（0，0，0，1，1，1，1，0，0，0，0，0，1，0，0，1）

M5：（0，0，0，1，1，1，0，0，0，0，0，1，0，0，1，1）

M6：（0，0，0，0，0，0，0，0，0，0，0，0，0，1，1，1）

通过可达序列可知N1⊕N2⊕N3中的初始库所i1、i2、i3中的标识都能通过网的运行到达终止库所f1、f2、f3且N1⊕N2⊕N3没有其他的剩余标识，所以N1⊕N2⊕N3满足合理性。最后，根据判定算法3求得有非负向量且可达序列存在，所以N1⊕N2⊕N3中 ｛f1，f2，f3｝不是死锁。因此正确性的两种情况N1⊕N2⊕N3均满足。

4 结束语

通过OPN对Web服务域／Web环境域进行形式化的结构建模和动态运行分析。然后在OPN模型基础对Web环境约束下Web服务组合正确性的两种情况：单个满足合理性的Web服务域／Web环境域组合后整体满足合理性，Web服务域／Web环境域组后整体的特定库所无死锁进行了研究并给出了若干判定算法，最后通过实例验证了这些算法的正确性。下一步的研究重点是将这些判定算法移植到商用Web协议和语言上。

［1］Ahlem Ben Hassine，Joshi Finin A，Van Hee K M，et al.A constraint－based approach to horizontal web service composition［G］.LNCS 4273：The Semantic Web.Munich：Springer，2006：130－143.

［2］Ratsimor O，Korolev V，Joshi A，et al.Agents2Go：An infrastructure for location－dependent service discovery in the mobile electronic commerce environment［C］.New York：ACM Mobile Commerce Workshop，2007：163－165.

［3］Vander Aalst W M P，Hee K M，Weske T M.Service trees［R］.Eindhoven：Echnische Universiteit Eindhoven，2009：324－327.

［4］WU Zhehui.Petri net theroy ［M］.Beijing：China Machine Press，2006：19－23 （in Chinese）. ［吴哲辉.Petri网导论 ［M］.北京：机械工业出版社，2006：19－23.］

［5］YUAN Chongyi.Petri net principle and application.Beijing：Electronic Industry Press，2005：12－14 （in Chinese）. ［袁崇义.Petri网原理与应用 ［M］.北京：电子工业出版社，2006：12－14.］

［6］Lohmann N，Ratsimor O，Korolev V，et al.From public views to private views：correctness－by－design for services ［C］.Munich：Springer，2007：139－153.

［7］Kees M，Van Hee，Ahlem Ben Hassine，et al.Compositional service trees［C］.Munich：Springer，2009：287－289.

［8］Van Hee K M，Vander Aalst W M P，Van Hee K M，et al.A framework for linking and pricing nocurenopay services ［C］.Munich：Springer，2009：176－179.

［9］Beisiegel M，Lohmann N，Ratsimor O，et al.An SOA－based architecture framework ［J］.International Journal of Business Process Integration and Management，2007：2 （2）：91－101.

［10］Massuthe P，Vander Aalst W M P，Hee K M，et al.Compositional service trees ［R］.Eindhoven：Technische Universiteit Eindhoven，2009：23－25.

［11］Vander Aalst W M P，Van Hee K M，Beisiegel M，et al.From public correctness of services［C］.New York：Computer Science，2008：193－195.

［12］Vander Aalst W M P，Beisiegel M，Lohmann N，et al.Multi－party contracts：Agreeing and implementing interorganizational processes［J］.The Computer Journal，2010，53 （1）：90－106.

［13］Casati F，Kuno H，Machiraju V，et al.Web services concepts，architectures and applications［M］.Munich：Springer，2007：342－345.

［14］Decker G，Weske M.Local enforceability in interaction petri nets［C］.Proceedings of the 5th International Conference on Business Process Management，2007：305－319.

［15］GAO Xin，FANG Xianwen，XU Zhicai.Constraint－aware correctness analyzing of composite web service based on open petri net［C］.Tenth International Symposium on Distributed Computing and Applications to Business，Engineering and Science，2011：373－377.

［16］Vogler W，Ratsimor O，Korolev V，et al.Asynchronous communication of petri nets and the refinement of transitions［C］.Proceedings of the 19th International Colloquium on Automata Languages and Programming，1992：605－616.

［17］Lohmann N，Massuthe P，Stahl C，et al.Analyzing interacting BPEL processes［G］.LNCS 4102：Vienna，Austria：4th International Conference on Business Process Management，2006：17－32.

［18］Lohmann N，Massuthe P，Wolf K.Operating guidelines for finite－state services ［C］.Proceedings of the 28th International Conference on Applications and Theory of Petri nets and Other Models of Concurrency，2007：321－341.