基于離散粒子群優(yōu)化的魯棒Web服務(wù)組合

葉恒舟，陸湘鵬

(桂林理工大學(xué)嵌入式技術(shù)與智能信息處理廣西高校重點(diǎn)實(shí)驗(yàn)室 廣西 桂林 541006)

Web服務(wù)已深入應(yīng)用于實(shí)現(xiàn)面向服務(wù)的計(jì)算(service-oriented computing, SOC)和面向服務(wù)的構(gòu)架(service-oriented architecture, SOA)[1]。隨著Web服務(wù)技術(shù)的發(fā)展，單個(gè)Web服務(wù)往往難以滿足人們?nèi)找嬖鲩L(zhǎng)的需要。Web服務(wù)組合將多個(gè)Web服務(wù)組合成滿足用戶需求的復(fù)合服務(wù)，使其具有更強(qiáng)大的功能。服務(wù)質(zhì)量(quality of service, QoS)用于區(qū)別功能相同的Web服務(wù)的非功能屬性，如何從眾多服務(wù)中選擇滿足用戶需求，且具有最優(yōu)QoS的組合服務(wù)，即QoS感知的Web服務(wù)組合(QSC)問題，是當(dāng)前的研究熱點(diǎn)。

目前已經(jīng)有很多求解QSC問題的方法[2-3]，它們均假定了服務(wù)的QoS不隨時(shí)間變化，即取某個(gè)確定值。然而，由于Web服務(wù)環(huán)境的動(dòng)態(tài)性，服務(wù)的QoS屬性具有內(nèi)在的不確定性[4-5]，因而有必要研究QoS不確定時(shí)的服務(wù)組合問題。文獻(xiàn)[6]采用云模型計(jì)算QoS的不確定性，剔除冗余服務(wù)。文獻(xiàn)[7]提出一種p-R-tree索引結(jié)構(gòu)和一種雙重剪枝方案計(jì)算p-dominant skyline，從而降低候選服務(wù)及其組合的數(shù)量。文獻(xiàn)[8]提出了一種發(fā)現(xiàn)可行Web服務(wù)的方法，該方法運(yùn)用了隨機(jī)優(yōu)勢(shì)理論，不關(guān)心QoS的分布情況。文獻(xiàn)[9]也采用了隨機(jī)優(yōu)勢(shì)理論剔除不滿足約束的解，準(zhǔn)確性更好。這些研究只是淘汰了部分候選服務(wù)，并不能直接獲得最優(yōu)組合服務(wù)，且僅考慮了順序結(jié)構(gòu)的工作流。

為了增強(qiáng)服務(wù)組合時(shí)，對(duì)動(dòng)態(tài)環(huán)境的適應(yīng)性，一些文獻(xiàn)采用云模型[10]或歷史事務(wù)信息[11]等方式更精確地估計(jì)QoS屬性值，或者采用了即時(shí)推薦策略[12]或約束分解策略[13]。少量文獻(xiàn)則在服務(wù)組合時(shí)，考慮了其魯棒性能。文獻(xiàn)[14]考慮了傳感網(wǎng)絡(luò)具有的不可靠性和不穩(wěn)定性，提出了一種新的服務(wù)模型和動(dòng)態(tài)選擇方法，但不適用于基于因特網(wǎng)的服務(wù)組合場(chǎng)景。文獻(xiàn)[15]所提出的魯棒服務(wù)組合方法，目標(biāo)是擴(kuò)大所選擇的服務(wù)簇在網(wǎng)絡(luò)空間上的覆蓋范圍，以降低局部網(wǎng)絡(luò)異常帶來(lái)的影響。文獻(xiàn)[16]僅考慮了響應(yīng)時(shí)間的不確定性，而文獻(xiàn)[17]僅考慮了執(zhí)行價(jià)格的不確定性。

本文假設(shè)候選服務(wù)的QoS屬性值及其聚合服從正態(tài)分布，通過估計(jì)兩個(gè)正態(tài)分布的和、積、最大、最小、平均值的期望與方差，建立了一種魯棒服務(wù)組合優(yōu)化模型。與上述研究工作不同，該模型可以支持執(zhí)行價(jià)格、響應(yīng)時(shí)間、可靠性、成功率等QoS屬性的不確定性，也可以支持由順序、選擇與并發(fā)模式經(jīng)過有限次嵌套而生成的任意工作流。

1 魯棒Web服務(wù)組合模型

Web服務(wù)組合的一個(gè)研究熱點(diǎn)是，對(duì)于給定的工作流，為該工作流中的每個(gè)任務(wù)挑選一個(gè)合適的候選服務(wù)，使最終的組合服務(wù)在滿足用戶給定的某些QoS屬性約束的同時(shí)，優(yōu)化由用戶所關(guān)注的另外一些QoS屬性所確定的綜合效用。本文所考慮的魯棒Web服務(wù)組合問題是在此基礎(chǔ)上，考慮候選服務(wù)QoS屬性值的不確定性，并使最終的組合服務(wù)具備較好的魯棒性。

設(shè)工作流F包含N個(gè)任務(wù)，任務(wù)有Mi個(gè)候選服務(wù)，為F的解域。候選服務(wù)涉及K個(gè)QoS屬性。服務(wù)的QoS屬性往往既有增益性的，也有減益性的，但兩者很容易相互轉(zhuǎn)換，本文假設(shè)qij涉及的QoS屬性都是增益性的。在考慮QoS屬性值的不確定性時(shí)，比較常見的是認(rèn)為QoS屬性值服從正態(tài)分布，設(shè)服從正態(tài)分布

不失一般性，設(shè)k= 1, 2,…,r- 1(1≤r≤K)是用戶所關(guān)心的效用屬性，k=r,r+ 1,…,K是用戶所關(guān)心的約束屬性；對(duì)于某個(gè)組合服務(wù)s∈D(F)，qk(s)表示其第k(k= 1, 2,…,K)個(gè)QoS屬性的聚合值。魯棒Web服務(wù)組合問題(RWSC)模型可以表示為：

目標(biāo)：

約束條件：

式(1)給出了優(yōu)化目標(biāo)，即選擇使用戶所關(guān)心的效用QoS屬性的聚合值的加權(quán)平均的期望最大化，方差最小化的組合服務(wù)，其中E(X)、D(X)表示X的期望與均方差，γ≥0為可調(diào)參數(shù)，wk為第k個(gè)QoS屬性的權(quán)值，滿足0 ≤wk≤ 1 (k=1, 2,…,r-1)且；式(2)限制了s的取值范圍；式(3)描述了用戶所關(guān)心的約束條件，P(X)表示事件X發(fā)生的概率，cqk(k=r,r+1,…,K)為用戶給定的約束限，pk為用戶給定的概率約束值或者取經(jīng)驗(yàn)值，如根據(jù)“3σ”法則，并假設(shè)qk(s)服從正態(tài)分布，可取pk=99.74%，此時(shí)，式(3)等價(jià)于式(4)。

式中，μk(s)、σk(s)分別為qk(s)的期望與均方差。

2 組合服務(wù)的QoS聚合

具體化RWSC模型的關(guān)鍵是確定組合服務(wù)的QoS屬性的聚合值，即的計(jì)算方法。很多文獻(xiàn)[2,18-20]針對(duì)QoS屬性為確定數(shù)值的情況進(jìn)行了研究，核心是確定工作流F中常見順序、選擇及并發(fā)等模式的QoS聚合規(guī)則。當(dāng)QoS屬性服從正態(tài)分布時(shí)，這些規(guī)則仍然是可以借鑒的，即可根據(jù)表1計(jì)算各種模式下的QoS屬性聚合值，其中Xi(i=1, 2,…,n)表示第i個(gè)服務(wù)的某個(gè)QoS屬性所對(duì)應(yīng)的隨機(jī)變量。

從表1可以看出，計(jì)算涉及到n個(gè)隨機(jī)變量的累加、最大值、最小值及累積等運(yùn)算?？紤]到這幾種運(yùn)算都具備交換律與結(jié)合律，且各個(gè)候選服務(wù)都具備獨(dú)立性，并認(rèn)為兩個(gè)正態(tài)分布的上述運(yùn)算結(jié)果近似符合正態(tài)分布，可以僅考慮兩個(gè)相互獨(dú)立的正態(tài)隨機(jī)變量的和、最大值、最小值及積的計(jì)算方法。

2.1 兩個(gè)正態(tài)分布的和

設(shè)X1、X2是兩個(gè)正態(tài)分布隨機(jī)變量，

表1 不同模式下各QoS屬性的聚合規(guī)則

2.2 兩個(gè)正態(tài)分布的最大值

記Y= max(X1,X2)，設(shè)μ1≤μ2，根據(jù)“3σ”法則，Y的分布存在圖1所示的3種可能，其中d1=(μ1-μ2) - 3 (σ1-σ2)，d2= (μ1-μ2) + 3 (σ1-σ2)。

對(duì)于圖1a，Y主要分布在區(qū)域 [μ1-3σ1，μ2+3σ2]上；對(duì)于圖1b，Y主要分布在區(qū)域[μ2- 3σ2,μ1+ 3σ1]上；對(duì)于圖1c，Y主要分布在區(qū)域[μ2- 3σ2,μ2+ 3σ2]上。若認(rèn)為Y近似于服從正態(tài)分布，可得式(5)和式(6)。

圖1Y的3種可能分布

2.3 兩個(gè)正態(tài)分布的最小值

記Y= min(X1,X2)，設(shè)μ1≤μ2，類似2.2節(jié)的分析可得，Y近似于服從正態(tài)分布N(μ,σ2) ，可得式(7)和式(8)。

2.4 兩個(gè)正態(tài)分布的積

記Y=X1×X2，則Y的期望E(Y)及方差D(Y)可以分別由式(9)、(10)計(jì)算，因此可以認(rèn)為Y近似服從正態(tài)分布N(E(Y),D(Y))。

3 求解RWSC的DPSO算法

3.1 粒子的位置與速度

設(shè)第i個(gè)粒子的位置Xi= ＜xi1,xi2,…,xiN＞，其中xij(j= 1, 2,…,N)為一個(gè)正整數(shù)，表示為任務(wù)tj選擇的候選服務(wù)的編號(hào)(從1開始編號(hào))。顯然，Xi對(duì)應(yīng)于某個(gè)服務(wù)s∈D(F)。第i個(gè)粒子的速度記為Vi=＜Vi1,Vi2,…,ViN＞，vij(j= 1, 2,…,N)表示服務(wù)sjxkj的綜合效用；服務(wù)sij的綜合效用f(sij)，由式(11)確定。

式中，r、wk、E(?)、D(?)、γ與式(1)一致；qk(s)表ij示服務(wù)sij的第k個(gè)QoS屬性值。

3.2 粒子的速度與位置更新公式

參照PSO算法中對(duì)粒子的速度與位置的定義，可得粒子的速度和位置的離散迭代如下：

式中，w為慣性權(quán)重，在[0，1]區(qū)間取值；c1和c2是學(xué)習(xí)因子，可取值為2；r1和r2是在區(qū)間[0, 1]上取值的隨機(jī)數(shù)；k表示當(dāng)前的迭代次數(shù)。算子?和⊕分別由式(14)、式(15)定義。?度量?jī)蓚€(gè)粒子各個(gè)維度上的效用差，而⊕為粒子的各個(gè)維度選擇一個(gè)新的位置，使該位置所代表的候選服務(wù)的綜合效用與原位置的效用加上速度后的值最為接近。

3.3 粒子的適應(yīng)度函數(shù)

設(shè)粒子Xi對(duì)應(yīng)服務(wù)s，粒子Xi的適應(yīng)度U(s)可由式(16)計(jì)算，其中 ()k gs用于判斷s對(duì)于第k個(gè)QoS屬性的違約情形，由式(17)度量。式(16)表明，當(dāng)s滿足約束條件時(shí)，Xi適應(yīng)度為f(s)；當(dāng)s不滿足約束條件時(shí)，Xi適應(yīng)度會(huì)在f(s)基礎(chǔ)上有所降低，降低的幅度與違反約束條件的個(gè)數(shù)與程度有關(guān)，個(gè)數(shù)越多，程度越強(qiáng)，降低幅度越大。β＞0為可調(diào)系數(shù)。

3.4 DPSO算法步驟

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)場(chǎng)景

實(shí)驗(yàn)時(shí)選取了4種規(guī)模的服務(wù)組合問題，其任務(wù)個(gè)數(shù)N與候選服務(wù)個(gè)數(shù)M分別為(20, 100)、(20, 400)、(200, 100)、(200, 400)，每種規(guī)模的相關(guān)實(shí)驗(yàn)測(cè)試40次取平均值。實(shí)驗(yàn)所用工作流依問題規(guī)模隨機(jī)產(chǎn)生，其中順序、選擇、并發(fā)模式的占比分別為1/2、1/4、1/4?？紤]執(zhí)行價(jià)格、響應(yīng)時(shí)間、可靠性、成功率4種QoS屬性，其中執(zhí)行價(jià)格為優(yōu)化目標(biāo)，響應(yīng)時(shí)間、可靠性、成功率為約束條件。執(zhí)行價(jià)格的期望在[100,1 000]上隨機(jī)取值，其他QoS屬性的期望從QWS Dataset V2開放數(shù)據(jù)集[21-22]中取值；各QoS屬性的均方差為其期望的a倍，a分別在區(qū)間[0.1, 0.2]、[0.1,0.2]、[0.001, 0.005]和[0.05, 0.1]上取隨機(jī)值。相關(guān)差數(shù)取值為：γ= 0；β= 2；w= 0.6 - 0.4t/T(t和T分別為當(dāng)前迭代次數(shù)和總迭代次數(shù))。編程語(yǔ)言為Java 1.6。

4.2 魯棒性測(cè)試

采用類似文獻(xiàn)[23]所定義的魯棒概率(robustness probability)評(píng)價(jià)所求得的組合服務(wù)的魯棒性。魯棒概率Rp，表征組合服務(wù)滿足用戶約束的概率，可由式(18)計(jì)算，其中TotalTimes、failedTimes分別表示測(cè)試的總次數(shù)、違反用戶約束的次數(shù)。

表2顯示了不同問題規(guī)模時(shí)，依據(jù)所建立的優(yōu)化模型，采用DPSO所選擇的組合服務(wù)的平均魯棒概率(TotalTimes取值為10 000)。測(cè)試結(jié)果表明，所選擇的組合服務(wù)具有很好的魯棒性，且基本不受問題規(guī)模的影響。

表2 組合服務(wù)的平均魯棒概率

4.3 模型精度測(cè)試

所建立的優(yōu)化模型中，組合服務(wù)的QoS屬性聚合值的期望與均方差有些是近似計(jì)算的，有必要測(cè)試其粒度。測(cè)試時(shí)，針對(duì)某個(gè)組合服務(wù)問題，隨機(jī)生成一個(gè)組合服務(wù)，分別為優(yōu)化模型的計(jì)算方法及采樣(樣本總數(shù)為10 000)計(jì)算方式獲取該組合服務(wù)的響應(yīng)時(shí)間、可靠性及成功率的期望與均方差，比較兩者的相對(duì)偏差，即模型計(jì)算值與采樣計(jì)算值之差與采樣計(jì)算值的比值。

表3給出了不同問題規(guī)模時(shí)，組合服務(wù)各QoS屬性聚合值的期望與均方差的相對(duì)偏差值。分析這些數(shù)據(jù)，可以發(fā)現(xiàn)：1) 各QoS屬性的聚合值的期望的偏差不超過0.2%，精度相當(dāng)高；2) 響應(yīng)時(shí)間與可靠性的均方差的偏差約2%，與問題規(guī)模無(wú)明顯關(guān)聯(lián)；3) 成功率的均方差的偏差較高，且隨任務(wù)個(gè)數(shù)增加，這在一定程度上是因?yàn)槌晒β实膶傩灾档钠谕抵杏幸恍┤≈禐?或很接近1，加上波動(dòng)后往往大于1，而測(cè)試時(shí)約定成功率不能大于1?？偟膩?lái)看，由模型計(jì)算的組合服務(wù)的各QoS屬性的聚合值的期望與方差與真實(shí)值的偏差不大，精度較好。

表3 組合服務(wù)各QoS屬性期望與均方差的相對(duì)偏差 %

5 結(jié)束語(yǔ)

應(yīng)用于互聯(lián)網(wǎng)的Web服務(wù)的QoS受到很多因素的影響，很難準(zhǔn)確估計(jì)其屬性值。魯棒Web服務(wù)組合方法，意在當(dāng)服務(wù)的QoS在一定范圍內(nèi)波動(dòng)時(shí)，所選擇的組合服務(wù)仍能在很大程度上滿足用戶的約束條件。通過給出各種QoS聚合計(jì)算方法，提出了一種魯棒Web服務(wù)組合優(yōu)化模型，并采用了一種支持約束條件的離散粒子群優(yōu)化算法求解該模型。模型僅考慮了服務(wù)的QoS服從正態(tài)分布的情形，模型的精度，特別是均方差的計(jì)算精度還有待改進(jìn)。

[1]WANG Peng-wei, DING Zhi-jun, JIANG Chang-jun, et al.Automatic web service composition based on uncertainty execution effects[J]. IEEE Transactions on Services Computing, 2016, 9(4)： 551-565.

[2]LIU Zhi-zhong, CHU Dian-hui, SONG Cheng, et al. Social learning optimization (SLO) algorithm paradigm and its application in QoS-aware cloud service composition[J].Information Sciences, 2016, 326： 315-333.

[3]CHEN Ying, HUANG Ji-wei, LIN Chuang, et al. A partial selection methodology for efficient QoS-aware service composition[J]. IEEE Transactions on Services Computing,2015, 8(3)： 384-397.

[4]ZHENG Zi-bin, ZHANG Yi-lei, LYU M R. Investigating QoS of real-world web services[J]. IEEE Transactions on Services Computing, 2014, 7(1)： 32-39.

[5]ROSARIO S, BENVENISTE A, HAAR S, et al.Probabilistic qos and soft contracts for transaction-based web services orchestrations[J]. IEEE Transactions on Services Computing, 2008, 1(4)： 187-200.

[6]王尚廣, 孫其博, 張光衛(wèi), 等. 基于云模型的不確定性QoS感知的Skyline服務(wù)選擇[J]. 軟件學(xué)報(bào), 2012, 23(6)：1397-1412.WANG Shang-guang, SUN Qi-bo, ZHANG Guang-wei, et al. QoS-aware skyline service selection based on cloud model[J]. Journal of Software, 2012, 23(6)：1397-1412.

[7]YU Q, BOUGUETTAYA A. Computing service skyline from uncertain QoWS[J]. IEEE Transactions on Services Computing, 2010, 3(1)： 16-29.

[8]FU Xiao-dong, YUE Kun, LIU Li, et al. Discovering admissible Web services with uncertain QoS[J]. Frontiers of Computer Science, 2015, 9(2)： 265-279.

[9]付曉東, 岳昆, 劉驪, 等. 不確定服務(wù)質(zhì)量感知的Web服務(wù)可行組合方案計(jì)算[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2016,22(1)： 122-132.FU Xiao-dong, YUE Kun, LIU Li, et al. Admissible composition plans of Web services with uncertain QoS[J].Computer Integrated Manufacturing Systems, 2016, 22(1)：122-132.

[10]申利民, 陳真, 李峰. 一種考慮QoS數(shù)據(jù)不確定性的服務(wù)選取方法[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2013, 19(10)：2652-2663.SHEN Li-min, CHEN Zhen, LI Feng. Service selection approach considering the uncertainty of QoS data[J].Computer Integrated Manufacturing Systems, 2013, 19(10)： 2652-2663.

[11]KIL H, CHA R, NAM W. Transaction history-based web service composition for uncertain QoS[J]. International Journal Of Web And Grid Services, 2016, 12(1)： 42-62.

[12]CHELLAMMAL S, GOPINATH G, MANIKANDAN S R.An approach for selecting best available services through a new method of decomposing QoS constraints[J]. Service Oriented Computing and Applications, 2015, 9(2)：107-138.

[13]CHEN Liang, WU Jian, JIAN Heng-yi, et al. Instant recommendation for web services composition[J]. IEEE Transactions on Services Computing, 2014, 7(4)： 586-598.

[14]GEYIK S C, SZYMANSKI B K, ZERFOS P. Robust dynamic service composition in sensor networks[J]. IEEE Transactions on Services Computing, 2013, 6(4)： 560-572.

[15]WAGNER F, ISHIKAWA F, HONIDEN S. Robust service compositions with functional and location diversity[J].IEEE Transactions on Services Computing, 2016, 9(2)：277-290.

[16]DU Yan-hua, TAN Wei, ZHOU Meng-chu. 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.

[17]MARKOU G, REFANIDIS I. Cost-sensitive probabilistic contingent planning for web service composition[J].International Journal on Artificial Intelligence Tools, 2016,25(1)： 21.

[18]馬文龍, 王錚, 趙燕偉. 基于改進(jìn)蟻群算法的制造云服務(wù)組合優(yōu)化[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2016, 22(1)： 113-121.MA Wen-long, WANG Zheng, ZHAO Yan-wei. Optimizing services composition in cloud manufacturing based on improved ant colony algorithm[J]. Computer Integrated Manufacturing Systems, 2016, 22(1)： 113-121.

[19]張以文, 吳金濤, 趙姝, 等. 基于改進(jìn)煙花算法的Web服務(wù)組合優(yōu)化[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2016, 22(2)： 422-432.ZHANG Yi-wen, WU Jin-tao, ZHAO Shu, et al.Optimization service composition based on improved firework algorithm[J]. Computer Integrated Manufacturing Systems, 2016, 22(2)： 422-432.

[20]張燕平, 荊紫慧, 張以文, 等. 基于離散粒子群算法的動(dòng)態(tài)Web服務(wù)組合[J]. 計(jì)算機(jī)科學(xué), 2015, 42(6)： 71-75.ZHANG Yan-ping, JING Zi-hui, ZHANG Yi-wen, et al.Dynamic web service composition based on discrete particle swarm optimization[J]. Computer Science, 2015,42(6)： 71-75.

[21]AL-MASRI E, MAHMOUD Q H. Discovering the best web service[C]//Proceedings of the 16th International Conference on World Wide Web (WWW). New York,USA： ACM, 2007： 1257-1258.

[22]AL-MASRI E, MAHMOUD Q H. QoS-based discovery and ranking of web services[C]//Proceedings of 16th International Conference on Computer Communications and Networks, (ICCCN). Honolulu, HI： IEEE Computer Society, 2007： 529-534.

[23]RAMACHER R, MONCH L. Robust multi-criteria service composition in information systems[J]. Business &Information Systems Engineering, 2014, 6(3)： 141-151.