一種時序約束下的Web服務組合兼容性的定量驗證方法

鄭宇迪，葉恒舟

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

作為一種基于現有互聯網協議與公開標準的自包含、自描述、模塊化的應用，Web服務成為設計復雜商務應用的主要技術之一，而服務組合是研究服務技術的關鍵之一。為了增強服務組合的正確性及QoS特性，在流程設計層面的時間約束下的兼容性驗證與錯誤檢測正受到越來越多的關注。

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

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

1 時序工作流模型

Petri網[6]常用來描述服務及其組合。

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

T中的變遷代表工作流中的活動，活動之間的依賴關系F通過庫所的連接表示。多個活動可能順序執行、并行執行或選擇其中一個執行。為了討論方便，約定由兩個或以上活動順序(并發、選擇)組成的結構塊稱為純順序(并發、選擇)結構塊(圖1)。考慮到不受約束的WFN可能導致潛在錯誤且不易發現與改正[7]，本文討論的WFN僅由有限個純順序、并發或選擇結構塊嵌套形成，即非順序結構塊不允許交叉。

定義2(時序工作流網，TWN)一個時序工作流網是一個五元組TWN=(P，T，F，X，R)。其中:

(1)(P，T，F)是一個WFN;

(2)X={x1，x2，…，xn}，xi～N(μi，)是與ti∈T關聯的一個基于正態分布的非負實數值，代表ti的時間開銷;

(3)R={r1，r2，…，rm}描述工作流的時序約束，rk(ti，tj)≤dk表示tj應該在ti開始后不超過dk個時間單元內結束;

一條時序約束rk(ti，tj)≤dk的時序兼容性可通過rk(ti，tj)≤dk的概率來度量，為此，需要估計rk(ti，tj)的概率分布。

圖1 不同的結構塊Fig.1 Different structures

2 時序兼容性檢查

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

算法1:基于概率的時序兼容性檢驗

輸入:一個TWN及置信水平1－α

輸出:時序兼容性檢驗結果

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

{

S2:while(包含在ti，tj的部分存在純結構)

選擇一個純結構，計算其概率分布賦給事件t，并用t代替該結構;

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

}

S4:輸出“兼容”;

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

3 3種純結構的概率分布估算

設在TWN中出現的變遷ti時間開銷對應一個隨機變量xi，xi～N(μi，σ2i)，且xi與xj(i≠j)相互獨立。

3.1 純順序結構的概率分布

在圖1a中，當變遷t1、t2都依次激活后，整個結構的變遷才算完成。其時間開銷x12應該為兩個變遷的時間開銷之和，即x12=x1+x2，即x12～

3.2 純并發結構的概率分布

考慮圖1b，當變遷t1完成后，變遷t2、t3可同時激活，當它們都完成后，才能激活變遷t4。設變遷t2、t3整體的時間開銷為x23，整個結構的開銷為x1+x23+x4，故關鍵在于計算x23=max(x2，x3)的概率分布。

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

算法2:估計2個正態分布變量的最大值的分布

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

輸出:μ，σ

S1:定義樣本數組Examples[Times];

S2:For(i=1 to Times)

{

取X1的隨機樣本x1;

取X2的隨機樣本x2;

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

}

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

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

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

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

σ=(b－a)/(2*zα);//zα為標準正態分布的上

α分位點

3.3 純選擇結構的概率分布

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

盡管以上討論是基于兩個變遷的情形，對于多個變遷的情形也是適用的。

4 實例分析與性能測試

4.1 實例分析

某單片機系統開發流程可以用如圖2所示的TWN描述，其中變遷t1～t8分別表示“系統需求分析”、“主板設計”、“軟件架構設計”、“外設設計”、“重構已有系統”、“重新開發新系統”、“軟件測試”、“集成測試”，對應的時間開銷依次服從正態分布N(16，4)、N(6，2)、N(4，1)、N(8，2)、N(4，2)、N(6，1)、N(8，2)、N(10，3)。

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

圖2 用TWN描述的某系統開發流程Fig.2 System development describted by TWN

4.2 性能測試

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

圖3 TWN的轉化過程Fig.3 Process of TWN transformation

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

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

5 結論

時序約束是支持QoS的服務組合的一個重要指標，然而單個活動的時間開銷往往并不容易準確指定，組合服務的時序兼容性也并不總能嚴格滿足，因而需要研究一種基于正態分布和可信度的組合服務時序約束兼容性檢驗方法。筆者提出了一種基于概率的定量檢驗時序兼容性方法，重點探討了純順序(并發及選擇)結構的概率分布估算方法。實例分析與性能測試表明該方法是可行、有效的。下一步的工作目標是將相關算法應用于動態Web服務選擇，研究高效的、支持時序約束的動態Web服務組合方法。

[1]徐紅霞，杜彥華，董紹華.時序約束下Web服務組合的兼容性及修正研究[J].計算機集成制造系統，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，Fan 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.