一種時(shí)序約束下的Web服務(wù)組合兼容性的定量驗(yàn)證方法

鄭宇迪，葉恒舟

(桂林理工大學(xué)信息科學(xué)與工程學(xué)院，廣西桂林541004)

作為一種基于現(xiàn)有互聯(lián)網(wǎng)協(xié)議與公開(kāi)標(biāo)準(zhǔn)的自包含、自描述、模塊化的應(yīng)用，Web服務(wù)成為設(shè)計(jì)復(fù)雜商務(wù)應(yīng)用的主要技術(shù)之一，而服務(wù)組合是研究服務(wù)技術(shù)的關(guān)鍵之一。為了增強(qiáng)服務(wù)組合的正確性及QoS特性，在流程設(shè)計(jì)層面的時(shí)間約束下的兼容性驗(yàn)證與錯(cuò)誤檢測(cè)正受到越來(lái)越多的關(guān)注。

當(dāng)前，已經(jīng)出現(xiàn)了一些驗(yàn)證組合服務(wù)的時(shí)序約束兼容性研究成果，如徐紅霞等[1]提出了一種有限狀態(tài)機(jī)(finite state automaton，F(xiàn)SA)模型，討論了服務(wù)路徑中順序、選擇、并行和循環(huán)4種結(jié)構(gòu)的兼容性推導(dǎo)過(guò)程，并針對(duì)時(shí)序部分兼容的服務(wù)組合，提出相應(yīng)的時(shí)序兼容性修正方法。為了緩解兼容性驗(yàn)證中廣泛存在的組合爆炸問(wèn)題，文獻(xiàn)[2]將服務(wù)組合的時(shí)序約束分為兩個(gè)層面，即服務(wù)內(nèi)部的時(shí)序約束及服務(wù)之間的時(shí)序約束，并分別采用時(shí)序開(kāi)放工作流網(wǎng)絡(luò)(timed open workflow net，ToN)和協(xié)調(diào)網(wǎng)絡(luò)(mediation net)表示，最終構(gòu)建出模塊化時(shí)序狀態(tài)圖(modular timed state graph，MTSG)，進(jìn)而分析時(shí)序約束的兼容性。當(dāng)兩類約束均衡分布時(shí)優(yōu)化效果較為明顯。線性時(shí)序邏輯(linear temporal logic)[3]、活動(dòng)時(shí)序邏輯(temporal logic of actions)[4]等模型檢測(cè)方法也被用來(lái)描述服務(wù)組合中的各種時(shí)序約束，并進(jìn)行兼容性驗(yàn)證。

以上研究認(rèn)為單個(gè)活動(dòng)的執(zhí)行時(shí)間是固定值或區(qū)間，因而只能定性驗(yàn)證組合服務(wù)的時(shí)序約束兼容性(完全兼容、完全不兼容、部分兼容)。為此，文獻(xiàn)[5]提出了一種基于概率的時(shí)序兼容性檢驗(yàn)方法，以定量分析服務(wù)的兼容程度，但它通過(guò)轉(zhuǎn)化并行與選擇結(jié)構(gòu)為順序結(jié)構(gòu)的形式回避了并行與選擇結(jié)構(gòu)的影響，而這種轉(zhuǎn)換不僅容易導(dǎo)致組合爆炸問(wèn)題，也不容易自動(dòng)處理。筆者假設(shè)活動(dòng)的時(shí)序約束符合正態(tài)分布，通過(guò)討論順序、選擇及并行3種結(jié)構(gòu)的概率分布，提出了一種基于概率的定量檢驗(yàn)服務(wù)的時(shí)序兼容性的方法。本文的主要貢獻(xiàn)是提出了一種估計(jì)兩個(gè)正態(tài)分布隨機(jī)變量的最大(小)值分布的算法，進(jìn)而估算組合服務(wù)的時(shí)間分布，定量估計(jì)其時(shí)序兼容性。

1 時(shí)序工作流模型

Petri網(wǎng)[6]常用來(lái)描述服務(wù)及其組合。

定義1(工作流網(wǎng)，WFN)有向網(wǎng)PN=(P，T，F(xiàn))是WFN的充要條件為:(1)PN有一個(gè)源庫(kù)所i∈P，使·i=?;(2)PN有一個(gè)漏庫(kù)所o∈P，使=?;(3)每個(gè)節(jié)點(diǎn)x∈P∪T都屬于從i到o的一條路徑上。

T中的變遷代表工作流中的活動(dòng)，活動(dòng)之間的依賴關(guān)系F通過(guò)庫(kù)所的連接表示。多個(gè)活動(dòng)可能順序執(zhí)行、并行執(zhí)行或選擇其中一個(gè)執(zhí)行。為了討論方便，約定由兩個(gè)或以上活動(dòng)順序(并發(fā)、選擇)組成的結(jié)構(gòu)塊稱為純順序(并發(fā)、選擇)結(jié)構(gòu)塊(圖1)?？紤]到不受約束的WFN可能導(dǎo)致潛在錯(cuò)誤且不易發(fā)現(xiàn)與改正[7]，本文討論的WFN僅由有限個(gè)純順序、并發(fā)或選擇結(jié)構(gòu)塊嵌套形成，即非順序結(jié)構(gòu)塊不允許交叉。

定義2(時(shí)序工作流網(wǎng)，TWN)一個(gè)時(shí)序工作流網(wǎng)是一個(gè)五元組TWN=(P，T，F(xiàn)，X，R)。其中:

(1)(P，T，F(xiàn))是一個(gè)WFN;

(2)X={x1，x2，…，xn}，xi～N(μi，)是與ti∈T關(guān)聯(lián)的一個(gè)基于正態(tài)分布的非負(fù)實(shí)數(shù)值，代表ti的時(shí)間開(kāi)銷;

(3)R={r1，r2，…，rm}描述工作流的時(shí)序約束，rk(ti，tj)≤dk表示tj應(yīng)該在ti開(kāi)始后不超過(guò)dk個(gè)時(shí)間單元內(nèi)結(jié)束;

一條時(shí)序約束rk(ti，tj)≤dk的時(shí)序兼容性可通過(guò)rk(ti，tj)≤dk的概率來(lái)度量，為此，需要估計(jì)rk(ti，tj)的概率分布。

圖1 不同的結(jié)構(gòu)塊Fig.1 Different structures

2 時(shí)序兼容性檢查

對(duì)于給定TWN中的每一條約束rk(ti，tj)≤dk，約定包含在ti、tj的部分(包含ti與·ti，tj與t·j在內(nèi))也是一個(gè)TWN，即也是由有限個(gè)純順序(并發(fā)或選擇)結(jié)構(gòu)嵌套形成。算法1描述了一種基于概率的自動(dòng)檢驗(yàn)TWN時(shí)序兼容性的方法。

算法1:基于概率的時(shí)序兼容性檢驗(yàn)

輸入:一個(gè)TWN及置信水平1－α

輸出:時(shí)序兼容性檢驗(yàn)結(jié)果

S1:For(TWN中的每一條約束rk(ti，tj)≤dk)

{

S2:while(包含在ti，tj的部分存在純結(jié)構(gòu))

選擇一個(gè)純結(jié)構(gòu)，計(jì)算其概率分布賦給事件t，并用t代替該結(jié)構(gòu);

S3:將最后剩下的事件的分布作為rk(ti，tj)的分布，若rk(ti，tj)≤dk的概率小于1－α，輸出“不兼容”并退出;

}

S4:輸出“兼容”;

算法1的基本思想是逐條檢驗(yàn)時(shí)序約束，每條約束對(duì)應(yīng)以ti開(kāi)頭、tj結(jié)尾的一個(gè)子TWN。檢驗(yàn)時(shí)，先通過(guò)步驟S2由里及外的逐步替換該TWN中的純結(jié)構(gòu)，直到TWN中僅剩下1個(gè)事件，該事件對(duì)應(yīng)的概率分布就是該TWN的概率分布。再通過(guò)步驟S3確認(rèn)該約束是否可兼容。由于每次純結(jié)構(gòu)替換都至少減少1個(gè)事件，設(shè)TWN中包含n個(gè)事件，則S2最多執(zhí)行n次。若TWN中的約束條數(shù)為m，則算法1的時(shí)序復(fù)雜度為O(n×m)。如何計(jì)算一個(gè)純結(jié)構(gòu)的概率分布是算法的關(guān)鍵，將在下節(jié)探討。

3 3種純結(jié)構(gòu)的概率分布估算

設(shè)在TWN中出現(xiàn)的變遷ti時(shí)間開(kāi)銷對(duì)應(yīng)一個(gè)隨機(jī)變量xi，xi～N(μi，σ2i)，且xi與xj(i≠j)相互獨(dú)立。

3.1 純順序結(jié)構(gòu)的概率分布

在圖1a中，當(dāng)變遷t1、t2都依次激活后，整個(gè)結(jié)構(gòu)的變遷才算完成。其時(shí)間開(kāi)銷x12應(yīng)該為兩個(gè)變遷的時(shí)間開(kāi)銷之和，即x12=x1+x2，即x12～

3.2 純并發(fā)結(jié)構(gòu)的概率分布

考慮圖1b，當(dāng)變遷t1完成后，變遷t2、t3可同時(shí)激活，當(dāng)它們都完成后，才能激活變遷t4。設(shè)變遷t2、t3整體的時(shí)間開(kāi)銷為x23，整個(gè)結(jié)構(gòu)的開(kāi)銷為x1+x23+x4，故關(guān)鍵在于計(jì)算x23=max(x2，x3)的概率分布。

很難列出可以表示x23的概率分布的簡(jiǎn)單數(shù)學(xué)表達(dá)式，實(shí)驗(yàn)測(cè)試也表明該分布并不符合常見(jiàn)的分布類型;但可以通過(guò)采樣的方式確定x23樣本的有效(考慮置信水平)分布范圍，再構(gòu)造一個(gè)相應(yīng)的正態(tài)分布，使其具有一致的有效范圍。算法2實(shí)現(xiàn)了這一思想，其時(shí)間開(kāi)銷主要由步驟S2、S3、S4決定。其中S2的時(shí)間開(kāi)銷由采樣次數(shù)(Times)決定。測(cè)試表明，當(dāng)Times取10 000時(shí)，算法2的結(jié)果已經(jīng)很穩(wěn)定。S3、S4已經(jīng)有很成熟的算法，其時(shí)間開(kāi)銷主要由采樣密度決定，實(shí)驗(yàn)時(shí)采用了Matlab中的默認(rèn)值。因而，算法2的時(shí)空復(fù)雜度不隨問(wèn)題的規(guī)模變化。

算法2:估計(jì)2個(gè)正態(tài)分布變量的最大值的分布

輸入:X1～N(μ1，σ21)，X2～N(μ2，α22)及置信水平1－α

輸出:μ，σ

S1:定義樣本數(shù)組Examples[Times];

S2:For(i=1 to Times)

{

取X1的隨機(jī)樣本x1;

取X2的隨機(jī)樣本x2;

將min{x1，x2}存入Examples[i];

}

S3:以Examples[Times]構(gòu)成分布F(y);

S4:尋找a使F(y≤a)=α;

尋找b使F(y≥b)=α;

S5:μ=(a+b)/2;

σ=(b－a)/(2*zα);//zα為標(biāo)準(zhǔn)正態(tài)分布的上

α分位點(diǎn)

3.3 純選擇結(jié)構(gòu)的概率分布

考慮圖1c，變遷t2、t3整體的時(shí)間開(kāi)銷x23=min(x2，x3)，可以用類似算法2的方法估算其概率分布。

盡管以上討論是基于兩個(gè)變遷的情形，對(duì)于多個(gè)變遷的情形也是適用的。

4 實(shí)例分析與性能測(cè)試

4.1 實(shí)例分析

某單片機(jī)系統(tǒng)開(kāi)發(fā)流程可以用如圖2所示的TWN描述，其中變遷t1～t8分別表示“系統(tǒng)需求分析”、“主板設(shè)計(jì)”、“軟件架構(gòu)設(shè)計(jì)”、“外設(shè)設(shè)計(jì)”、“重構(gòu)已有系統(tǒng)”、“重新開(kāi)發(fā)新系統(tǒng)”、“軟件測(cè)試”、“集成測(cè)試”，對(duì)應(yīng)的時(shí)間開(kāi)銷依次服從正態(tài)分布N(16，4)、N(6，2)、N(4，1)、N(8，2)、N(4，2)、N(6，1)、N(8，2)、N(10，3)。

為了估計(jì)整個(gè)TWN的時(shí)間開(kāi)銷分布(采樣次數(shù)為10 000，α=0.01)，首先轉(zhuǎn)化由路徑p2到p5的純順序結(jié)構(gòu)，轉(zhuǎn)化的效果為圖3a，其中t24的分布為N(14，4);再轉(zhuǎn)化由路徑p3到p10的純選擇結(jié)構(gòu)，轉(zhuǎn)化后如圖3b所示，其中t37的分布為N(15.5，6.9);最后轉(zhuǎn)化由路徑p1到p11的純并發(fā)結(jié)構(gòu)，轉(zhuǎn)化的效果為圖3c，其中t18的分布為N(42.4，16.7)，即整個(gè)TWN的時(shí)間開(kāi)銷分布。

圖2 用TWN描述的某系統(tǒng)開(kāi)發(fā)流程Fig.2 System development describted by TWN

4.2 性能測(cè)試

為了測(cè)試估算的概率分布的有效性，設(shè)某TWN的時(shí)間開(kāi)銷的隨機(jī)樣本值為{x1，x2，…，xn}，其估算的概率分布服從N(μ，σ2)，統(tǒng)計(jì)樣本值位于區(qū)間[μ－zασ，μ+zασ]的個(gè)數(shù)與n的比值稱為命中率，命中率越高，表明估算值越有效。當(dāng)樣本總數(shù)為10 000時(shí)，上例的命中率約為99.5%(α=0.01)、98.5%(α=0.02)、94.0%(α=0.05)或87.4%(α=0.1)，可見(jiàn)當(dāng)置信水平較高時(shí)，具有很高的命中率。

圖3 TWN的轉(zhuǎn)化過(guò)程Fig.3 Process of TWN transformation

在估算兩個(gè)正態(tài)分布的最大值或最小值的分布函數(shù)時(shí)，這兩個(gè)正態(tài)分布的概率密度曲線重疊部分的大小影響估算的準(zhǔn)確性。為此，根據(jù)t5與t6的時(shí)間開(kāi)銷概率密度曲線重疊部分的面積差別，為t5與t6取了一組測(cè)試值。測(cè)試結(jié)果表明，不同取值時(shí)的命中率變化不大且均接近95%(表1)，驗(yàn)證了該方法的有效性與穩(wěn)定性。

表1 不同取值時(shí)的命中率Table 1 Hit rates with different values

5 結(jié)論

時(shí)序約束是支持QoS的服務(wù)組合的一個(gè)重要指標(biāo)，然而單個(gè)活動(dòng)的時(shí)間開(kāi)銷往往并不容易準(zhǔn)確指定，組合服務(wù)的時(shí)序兼容性也并不總能嚴(yán)格滿足，因而需要研究一種基于正態(tài)分布和可信度的組合服務(wù)時(shí)序約束兼容性檢驗(yàn)方法。筆者提出了一種基于概率的定量檢驗(yàn)時(shí)序兼容性方法，重點(diǎn)探討了純順序(并發(fā)及選擇)結(jié)構(gòu)的概率分布估算方法。實(shí)例分析與性能測(cè)試表明該方法是可行、有效的。下一步的工作目標(biāo)是將相關(guān)算法應(yīng)用于動(dòng)態(tài)Web服務(wù)選擇，研究高效的、支持時(shí)序約束的動(dòng)態(tài)Web服務(wù)組合方法。

[1]徐紅霞，杜彥華，董紹華.時(shí)序約束下Web服務(wù)組合的兼容性及修正研究[J].計(jì)算機(jī)集成制造系統(tǒng)，2012，18(11):2562－2572.

[2]Du Y H，Tan W，Zhou M C.Timed compatibility analysis of Web service composition:A modular approach based on Petri nets[J].IEEE Transactions on Automation Science and Engineering，2014，11(2):594－606.

[3]Hao S G，Zhang L.Dynamic web services composition based on linear temporal logic[C]//IEEE Computer Society.2010 International Conference of Information Science and Management Engineering(ISME)，2010:362－365.

[4]Wang H B，Zhou Q Z，Shi Y Q.Describing and verifying web service composition using TLA reasoning[C]//IEEE Computer Society.2010 International Conference of Services Computing(SCC)，2010:234－241.

[5]Du Y H，Wang X F，Yao J S.Probability based timed compatibility of Web service composition[M]//Practical Applications of Intelligent Systems.Berlin，Heidelberg:Springer，2012:31－39.

[6]Du Y H，Xiong P C，F(xiàn)an Y S，et al.Dynamic checking and solution to temporal violations in concurrent workflow processes[J].IEEE Transactions on Systems，Man and Cybernetics，Part A:Systems and Humans，2011，41(6):1166－1181.

[7]Son J H，Kim M H.Improving the performance of time-constrained workflow processing[J].The Journal of Systems and Software，2001，58(3):211－219.