高 新，方賢文，許志才，2

（1.安徽理工大學(xué) 信息與計算科學(xué)系，安徽 淮南232001；2滁州學(xué)院 數(shù)學(xué)系，安徽 滁州239012）

0 引 言

實際應(yīng)用中Web服務(wù)組合的正確性不僅受到其他Web服務(wù)的約束，也受到Web環(huán)境的約束。由于Web環(huán)境的特殊性，很難用傳統(tǒng)的方法進(jìn)行建模和分析，因此研究Web環(huán)境約束下Web服務(wù)組合的正確性需要采用新的建模工具和分析方法。

傳統(tǒng)的Web服務(wù)組合研究一般情況下只注重服務(wù)組件之間的約束和組合關(guān)系，而忽略了服務(wù)組件和Web環(huán)境之間的約束和組合關(guān)系。而實際情況是Web服務(wù)組合的正確合理與否和Web環(huán)境關(guān)系巨大，例如，多個Web服務(wù)組件組成了視頻流媒體的Web服務(wù)，這個服務(wù)要想成功運行就必須依靠高帶寬的Web環(huán)境約束。因此對Web服務(wù)和Web環(huán)境組合后的正確性的判定就顯得愈發(fā)重要，也成為新的研究重點。

文獻(xiàn) ［1－2］對電磁、帶寬環(huán)境對移動網(wǎng)絡(luò)服務(wù)發(fā)現(xiàn)的影響做了相關(guān)研究并提出了環(huán)境影響服務(wù)正確性的觀點，但是缺乏嚴(yán)格的形式化模型；文獻(xiàn) ［3］通過服務(wù)樹等理論服務(wù)的組合建立了形式化的模型并對其合理性進(jìn)行了判定，但是忽略了環(huán)境因素。

為解決上述不足，提出了Web服務(wù)域和Web環(huán)境域的概念，并采用open Petri net（OPN）對Web服務(wù)域和Web環(huán)境域進(jìn)行建模。然后通過OPN給出Web服務(wù)域和Web環(huán)境域組合的充分條件以及組合后保持正確性的若干判定算法，最后通過實例驗證這些判定算法的正確性和有效性。

1 基本概念

目前，研究人員從不同的角度對Web服務(wù)組合進(jìn)行了定義。在Web服務(wù)組合技術(shù)研究方面，目前主要的服務(wù)組合技術(shù)包括工作流、AI規(guī)劃、規(guī)則推理、定理證明等。本文中采用的Web服務(wù)組合是通過把一些單個的功能單一的Web服務(wù)聯(lián)合起來以增值服務(wù)為目的的過程。

Web環(huán)境主要包括3部分：用戶環(huán)境、計算環(huán)境、物理環(huán)境。Web環(huán)境不能提供真實的服務(wù)，但是Web環(huán)境對Web服務(wù)的組合、運行、正確性都會產(chǎn)生影響，把Web環(huán)境對Web服務(wù)的這種影響稱為環(huán)境約束。

定義1 Web服務(wù)域 （service domain）是一個四元組SD＝ （SI，SO，SC，CI），其中SI是服務(wù)輸入端，SO是服務(wù)輸出端，SC是服務(wù)組件，CI是通信接口。

定義2 Web環(huán)境域 （environment domain）是一個四元組ED＝ （EI，EO，EC，CI），其中EI是環(huán)境輸入端，EO是環(huán)境輸出端，EC是環(huán)境組件，CI是通信接口。

定義3［4－5］滿足下列條件的三元組N＝ （S，T；F）稱作一個Petri網(wǎng)：

（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(xiàn)，i，f）稱作一個open petri net：

（1）（P∪I∪O，T，F(xiàn)）是一個petri網(wǎng)；

（2）P是內(nèi)部庫所的集合，T是變遷的集合，F(xiàn)是庫所和變遷之間弧線的集合；

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

（4）i是初始標(biāo)識；f是終止標(biāo)識。

I∪O稱作OPN的接口庫所；兩個OPN分別為M和N，如果PM，PN，IM，IN，OM，ON，TM，TN兩兩不相連，則網(wǎng)M和網(wǎng)N不相連。

定義5 設(shè) Web服務(wù)域SD＝ （SI，SO，SC，CI），環(huán)境域ED＝ （EI，EO，EC，CI）和OPN＝ （P，I，O，T，F(xiàn)，i，f），如果SIi，SOf，SCP，CII∪O，SI則稱SD能映射到OPN上。如果EIi，EOf，ECP，EII∪O，則稱ED能映射到OPN上。

Web環(huán)境和Web服務(wù)通過接口庫所進(jìn)行通信，從而形成了一個結(jié)構(gòu)和行為上都相互關(guān)聯(lián)的整體。由于Web服務(wù)和Web環(huán)境進(jìn)行了通信，那么Web環(huán)境必然會對Web服務(wù)的行為產(chǎn)生約束，這種約束主要通過組合后服務(wù)的正確性來反映。

2 基于OPN的Web環(huán)境約束下的Web服務(wù)組合正確性分析

Web環(huán)境約束下的Web服務(wù)組合正確性分析主要有兩方式：①單個Web環(huán)境／Web服務(wù)均滿足合理性，可通過組合后整體的合理性來確定正確性。②單個Web環(huán)境／Web服務(wù)不滿足或不考慮合理性，則可通過組合后整體有無死鎖來確定正確性。

Web環(huán)境對Web服務(wù)產(chǎn)生約束的前提是Web環(huán)境和Web服務(wù)進(jìn)行了組合，因此先要判定Web環(huán)境和Web服務(wù)能否組合。

定義6［9－11］：設(shè)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服務(wù)域／Web環(huán)境域組合后整體滿足

合理性的判定

定義7［12－15］OPN的合理性：N是個OPN，若一個petri網(wǎng)S（N）＝ （PN，TN，F(xiàn)），其中F＝FN∩ （（PN×TN）∪（TN×PN））。則稱S（N）為N的一個核心網(wǎng)，若任意一個M∈R（N），都有則N滿足合理性。

很多情況下，多個Web服務(wù)域要共用一個Web環(huán)境域。在圖1中服務(wù)域A和服務(wù)域C共用環(huán)境域B。服務(wù)域A和環(huán)境域B組合后，滿足合理性；服務(wù)域C和環(huán)境域B組合后，也滿足合理性；但服務(wù)域A、環(huán)境域B以及服務(wù)域C組合后，則不滿足合理性。

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

定義8［7－8］ΩA，B，A和B是兩個能夠組合的OPN，當(dāng)且僅當(dāng)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服務(wù)域／Web環(huán)境域組合后整體滿足合理性的判定

輸入：Web服務(wù)域SD1＝ （SI，SO，SC，CI），Web環(huán)境域ED＝ （EI，EO，EC，CI），Web服務(wù)域SD2＝ （SI，SO，SC，CI）。

輸出：判定結(jié)果

（1）根據(jù)定義5，把SD1＝ （SI，SO，SC，CI），ED＝（EI，EO，EC，CI），SD2＝ （SI，SO，SC，CI）映射到 OPN：WebopnA，WebEnviropnB和WebopnC；然后執(zhí)行步驟 （2）。

（2）根據(jù)定義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，然后執(zhí)行步驟 （3）；否則算法終止，返回不滿足合理性。

（3）若A⊕B滿足合理性的要求則執(zhí)行步驟 （4）；否則算法終止，返回不滿足合理性。

（4）根據(jù)定義9，如果ΩB，C成立則執(zhí)行步驟 （5）；否則算法終止，返回不滿足合理性。

（5）A、B、C組合后的A⊕B⊕C滿足合理性的要求，判定算法結(jié)束，返回滿足合理性。

實際應(yīng)用中，Web服務(wù)域／Web環(huán)境域的組合的數(shù)量很大、方式也很復(fù)雜，因此對多個Web環(huán)境域／Web服務(wù)域組合后的合理性進(jìn)行判定十分必要。

算法2：多個Web服務(wù)域／Web環(huán)境域組合后合理性的判定

輸入：D1，……Dn是Web環(huán)境域／Web服務(wù)域

輸出：判定結(jié)果

（1）根據(jù)定義5，把D1，……Dn映射到對應(yīng)的OPN：A1，……An上。執(zhí)行步驟 （2）。

（2）根據(jù)定義6，如果 （Pi∪Ii∪Oi∪Ti）∩ （Pi（c）∪Ii（c）∪Oi（c）∪Ti（c））＝ （Ii∩Oi（c））∪ （Oi∩Ii（c））都成立，則A1，……An能夠組合，然后執(zhí)行步驟 （3）；否則算法終止，返回不滿足合理性。

（3）把A1，……An構(gòu)造成以A1為父節(jié)點的域林，其中c：｛2，……n｝→ ｛1，……n－1｝，i∈｛2，……n｝：c（i）＜i； 1≤i＜j≤n：i＝c（j）IAi∩OAj≠θ∨OAi∩IAj≠θ。執(zhí)行步驟 （4）。

（4）A1，……An是以A1為父節(jié)點的域林，如果A1滿足合理性且ΩAi，Ai（c）成立；則A1⊕……⊕An也滿足合理性的要求，執(zhí)行步驟 （5）；否則算法終止，返回不滿足合理性。

（5）A1，……An組合后滿足合理性的要求，判定算法結(jié)束，返回滿足合理性。

2.2 多個Web服務(wù)域／Web環(huán)境域組合后整體

無死鎖的判定

當(dāng)單個Web服務(wù)域／Web環(huán)境域不能夠滿足或不需要滿足合理性時，則可以用服務(wù)組合后整體無死鎖的方式來判定組合后的正確性。

算法3：Web服務(wù)域／Web環(huán)境域組合后整體無死鎖的判定

輸入：Web服務(wù)域SD＝ （SI，SO，SC，CI），Web環(huán)境域ED＝ （EI，EO，EC，CI）。

輸出：判定結(jié)果

（1）根據(jù)定義5，把SD＝ （SI，SO，SC，CI），ED＝（EI，EO，EC，CI）映射到成對應(yīng)的 OPN：WebopnA和WebEnviropnB上；然后執(zhí)行步驟2。

（2）根據(jù)定義6，如果 （PA∪IA∪OA∪TA）∩ （PB∪IB∪OB∪TB）＝ （IA∩OB）∪ （OA∩IB）成立，則 A、B能夠組合且A和B組合后的OPN是A⊕B，然后執(zhí)行步驟 （3）；否則算法終止，返回不滿足正確性。

（3）求出A⊕B的關(guān)聯(lián)矩陣：A（A⊕B），A⊕B的初始狀態(tài)為M0。

（4）MX是要求能夠達(dá)到的一個運行狀態(tài)，MX∈R（M0），若求得存在非負(fù)向量 X，使得MX＝M0＋（A（A⊕B））TX成立，則執(zhí)行步驟 （5）；否則算法終止，返回不滿足正確性。

（5）如果存在變遷序列使得M0到MX可達(dá)，執(zhí)行步驟（6）；否則算法終止，返回不滿足正確性。

（6）WebopnA和WebEnviropnB組合后含有MX標(biāo)識的庫所不是死鎖。判定算法結(jié)束，返回滿足正確性。

3 實例分析

前面主要對Web環(huán)境域／Web服務(wù)域組合后的合理性和無死鎖進(jìn)行判定。這章通過實例對上述判定算法進(jìn)行驗證和分析。

Web提供高清視頻點播服務(wù) （由節(jié)目頻道、節(jié)目內(nèi)容、節(jié)目集數(shù)的服務(wù)組件組合而成），高清視頻需要占用大量的帶寬資源，所以需要帶寬這個物理環(huán)境對高清視頻點播服務(wù)進(jìn)行約束，才能得到合理的高清視頻點播服務(wù)。同時，Web還提供新聞?wù)Z音直播服務(wù) （由頻道、語種等服務(wù)組件組成），直播具有實時性的特點，所以需要時間這個邏輯環(huán)境對新聞?wù)Z音直播服務(wù)進(jìn)行約束，才能得到合理的新聞?wù)Z音直播服務(wù)，如圖2所示。

圖2 Web環(huán)境約束下的Web服務(wù)的組合

為了驗證高清視頻點播服務(wù)、新聞?wù)Z音直播服務(wù)在環(huán)境域的約束下能夠都實現(xiàn)合理的服務(wù)行為，首先通過OPN進(jìn)行建模。把高清視頻點播服務(wù)域、Web環(huán)境域和新聞?wù)Z音直播服務(wù)域分別映射到OPN：N1，N2，N3上。其中i1、i2、i3分別為初始庫所，均有一個初始標(biāo)識；f1、f2、f3分別為終止庫所；p1、p2、p3、p4、p5、p6分別為內(nèi)部庫所；o1、o2、o3分別為輸出接口庫所；i1、i2、i3分別為輸入接口庫所。需要說明的是N1中的o1在N2中等價于i2，N1中的i1在N2中等價于o2，N2中的o2在N3中等價于i3，N2中的i2在N3中等價于o3，如圖3所示。

圖3 服務(wù)域N1、環(huán)境域N2和服務(wù)域N3

然后把N1和N2進(jìn)行組合，因為滿足 （PA∪IA∪OA∪TA）∩ （PB∪IB∪OB∪TB）＝ （IA∩OB）∪ （OA∩IB）條件，所以N1、N2能夠組合。N1滿足合理性且N1、N2滿足ΩN1，N2所以N1⊕N2滿足合理性。再把N3跟N1⊕N2進(jìn)行組合，由于N1⊕N2滿足合理性且ΩN2，N3成立，根據(jù)判定算法1得出N1⊕N2⊕N3也滿足合理性，如圖4所示。

最后用可達(dá)標(biāo)識來對N1⊕N2⊕N3的合理性進(jìn)行驗證：

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）

通過可達(dá)序列可知N1⊕N2⊕N3中的初始庫所i1、i2、i3中的標(biāo)識都能通過網(wǎng)的運行到達(dá)終止庫所f1、f2、f3且N1⊕N2⊕N3沒有其他的剩余標(biāo)識，所以N1⊕N2⊕N3滿足合理性。最后，根據(jù)判定算法3求得有非負(fù)向量且可達(dá)序列存在，所以N1⊕N2⊕N3中 ｛f1，f2，f3｝不是死鎖。因此正確性的兩種情況N1⊕N2⊕N3均滿足。

4 結(jié)束語

通過OPN對Web服務(wù)域／Web環(huán)境域進(jìn)行形式化的結(jié)構(gòu)建模和動態(tài)運行分析。然后在OPN模型基礎(chǔ)對Web環(huán)境約束下Web服務(wù)組合正確性的兩種情況：單個滿足合理性的Web服務(wù)域／Web環(huán)境域組合后整體滿足合理性，Web服務(wù)域／Web環(huán)境域組后整體的特定庫所無死鎖進(jìn)行了研究并給出了若干判定算法，最后通過實例驗證了這些算法的正確性。下一步的研究重點是將這些判定算法移植到商用Web協(xié)議和語言上。

［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網(wǎng)導(dǎo)論 ［M］.北京：機(jī)械工業(yè)出版社，2006：19－23.］

［5］YUAN Chongyi.Petri net principle and application.Beijing：Electronic Industry Press，2005：12－14 （in Chinese）. ［袁崇義.Petri網(wǎng)原理與應(yīng)用 ［M］.北京：電子工業(yè)出版社，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，F(xiàn)ANG 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.