一種自治愈的QoS感知的Web服務(wù)組合方法

葉恒舟，李陶深，關(guān)云慧

(1. 廣西大學(xué)電氣工程學(xué)院 南寧 530004；2. 桂林理工大學(xué)信息科學(xué)與工程學(xué)院 廣西 桂林 541000；3. 廣西大學(xué)計算機與電子信息學(xué)院 南寧 530004)

一種自治愈的QoS感知的Web服務(wù)組合方法

葉恒舟1,2，李陶深3，關(guān)云慧2

(1. 廣西大學(xué)電氣工程學(xué)院 南寧 530004；2. 桂林理工大學(xué)信息科學(xué)與工程學(xué)院 廣西 桂林 541000；3. 廣西大學(xué)計算機與電子信息學(xué)院 南寧 530004)

基于工作流的服務(wù)質(zhì)量(QoS)感知的Web服務(wù)組合是Web服務(wù)領(lǐng)域的一個研究熱點，其目標(biāo)是選擇一個滿足QoS約束且QoS效用最大的組合服務(wù)。該文給出了常見工作流的一種形式化定義方法及虛擬任務(wù)的合成規(guī)則，從而提出了一種基于top-k優(yōu)選策略的Web服務(wù)組合方法，其核心思想是遞歸運用虛擬任務(wù)的合成規(guī)則將原工作流轉(zhuǎn)換成一個虛擬任務(wù)，并在每次合成虛擬任務(wù)時，僅為其保留k個優(yōu)選的服務(wù)或組合服務(wù)實例。該文還提出了一種新的尋找替換服務(wù)的方法以支持自治愈性。仿真實驗分析了k值對效用的影響、算法的效用與時間開銷以及可替代性能。

QoS感知; 自治愈; 服務(wù)組合；top-k優(yōu)選

隨著Web服務(wù)應(yīng)用領(lǐng)域的持續(xù)延伸，單個簡單的Web服務(wù)已經(jīng)無法滿足實際應(yīng)用需求，人們常常需要將多個Web服務(wù)組合起來以完成一個較復(fù)雜的任務(wù)。用戶在關(guān)注組合服務(wù)功能的同時，往往更加注重服務(wù)的QoS(響應(yīng)時間、信譽度、可靠性、價格等)是否滿足自身的需求。因此，如何為用戶提供高效且滿足QoS需求的Web服務(wù)組合是一個關(guān)鍵問題[1]。QoS感知的服務(wù)組合優(yōu)化問題(optimizing the QoS-aware service composition, O-QSC)應(yīng)運而生。

若不考慮Web語義[2-5]，O-QSC的問題可以建模為一個多維多選擇背包問題(multidimensional multiple choice knapsack problem, MMKP)[6]，這是眾所周知的NP難問題。所以，如何為用戶提供一個可信賴且可靠的服務(wù)組合是一個重大的挑戰(zhàn)。目前，基于工作流的QSC問題已經(jīng)獲得了很多的研究，大體可分為三類：局部優(yōu)化方法(local optimization, LO)[6-10]，全局優(yōu)化方法(global optimization, GO)[11-24]以及質(zhì)量約束分解方法(quality constriant decomposition, QCD)[25-28]。

當(dāng)為工作流中的每個任務(wù)選擇候選服務(wù)時，LO方法通常會對滿足組合流程的一組服務(wù)的QoS指標(biāo)進行加權(quán)排序，并以此作為選擇各個服務(wù)實例的依據(jù)。由于每個服務(wù)都是被獨立選擇的[6-7]，因此該方法表現(xiàn)出較好的性能。文獻[8]提出了一種中間件平臺，該平臺解決了如何選擇Web服務(wù)的問題，同時描述了一種基于局部選擇服務(wù)的方法。文獻[6]給出了一種啟發(fā)式算法，它從局部視角尋找接近最優(yōu)解的解決方案。雖然LO方法具有很好的時間復(fù)雜度，但不容易滿足全局約束，且不容易獲得最優(yōu)解。

GO方法是以服務(wù)組合的整體質(zhì)量滿足全局QoS約束為目標(biāo)的，因此在對各個服務(wù)進行選擇時，需要綜合考慮各服務(wù)組合后的總體質(zhì)量，從而生成一個最佳組合方案。當(dāng)該最佳服務(wù)組合服從全局約束時，能使聚合效用達到最大值。為了選擇出最合適的候選組合，文獻[11]討論了如何確定可考慮不同QoS類別的標(biāo)準，并開發(fā)出一些特定的啟發(fā)式算法來解決服務(wù)組合問題。文獻[12]提出了一種采用路徑模板編碼機制的遺傳算法來解決多路徑全局優(yōu)化問題，在算法的收斂性與復(fù)雜度方面有所提升。在文獻[13]中，O-QSC問題被建模為具有一個多項式數(shù)變量和約束的混合整數(shù)型線性規(guī)劃，但它要求目標(biāo)函數(shù)是線性的，且時間復(fù)雜度較高。GO方法適應(yīng)性強，可以獲得最優(yōu)或次優(yōu)解，容易滿足全局約束，但時間復(fù)雜度較高。

為了綜合LO方法和GO方法的優(yōu)點，文獻[25-26]采用了QCD方法。QCD過程旨在把全局約束分解為與組合服務(wù)任務(wù)相關(guān)聯(lián)的局部約束集，但其主要思想是全局約束和用戶喜好能引導(dǎo)著丟棄那些質(zhì)量比預(yù)期的最小質(zhì)量還要小的Web服務(wù)。文獻[25]僅考慮了順序模式的工作流以及和類型的QoS屬性。

可見，當(dāng)前O-QSC方法存在以下一個或多個不足：1) 算法效率不高或者效用不佳；2) 僅針對順序工作流或某個具體的工作流；3) 未考慮組合服務(wù)運行異常時的自治愈能力。為此，本文提出了一種帶有一定自治愈能力的基于Top-k優(yōu)選的服務(wù)組合方法，主要貢獻包括：1) 給出了一種正則工作流的形式定義，為自動處理工作流奠定了基礎(chǔ)；2) 給出了一種高效的QoS感知的Web服務(wù)組合方法，可以以較小的時間復(fù)雜度獲得較優(yōu)的組合方案；3) 可以為所選組合方案所涉及的每個服務(wù)尋找備用服務(wù)集，具備一定的自治愈能力。

1 工作流模型

1.1 工作流的基本模式

工作流描述了服務(wù)功能的結(jié)合方式以滿足用戶需求[29]。在工作流中，一個任務(wù)代表功能相同的一系列Web服務(wù)，一種模式代表不同任務(wù)之間的依賴關(guān)系[13]。與文獻[13]一樣，本文將考慮順序模式(SEQ)、并發(fā)模式(AND)以及選擇模式(XOR)等3種常見模式(如圖1)，其中Ai代表某個任務(wù)，AND-split、 AND-join分別表示并發(fā)模式的起點與終點，XOR-split、XOR-join分別表示選擇模式的起點與終點。

圖1 工作流基本模式

1.2 復(fù)雜工作流

常見的復(fù)雜工作流由以上3種模式(順序、并發(fā)、選擇)經(jīng)過有限次的連接嵌套而成。如果分別用⊙，⊕和?來表示SEQ、AND和XOR模式，那么常見的復(fù)雜工作流可遞歸定義為：

1) 當(dāng)A和B是任務(wù)時，(A⊙B)、(A⊕B)和(A?B)是工作流；

2) 當(dāng)P和Q是工作流時，(P⊙Q)、(P⊕Q)和(P?Q)也是工作流；

3) 當(dāng)A是一個任務(wù)，P是一個工作流時，(A⊙P)、(A⊕P)和(A?P)是工作流。

由此，一個復(fù)雜工作流可以表示為一個符號串。以圖2所描述的旅行規(guī)劃工作流[13]為例，它可以表示為(A1⊙((A2⊙(A3⊕A4))?A5?(A6⊙A7)))。

圖2 復(fù)雜工作流的例子

1.3 虛擬任務(wù)

為了描述方便，將一個任務(wù)看作一個二元組A＜ID, SG＞，ID是一個用來唯一確定A的標(biāo)識符，SG是執(zhí)行任務(wù)A的所有Web服務(wù)的集合。當(dāng)用一個符號串來表示一個工作流時，串中任何一對小括號可描述該工作流的一個子工作流，可將其看成一個虛擬任務(wù)，并描述為一個三元組VA＜ID, SG, UA＞，ID是用來唯一確定VA的標(biāo)識符，SG表示其所有實例的集合，UA表示其所涉及的任務(wù)的集合。

用Q(s)= (q1(s), q2(s), …, qr(s))表示服務(wù)s的QoS屬性，其中qi(s)決定了s的第i個屬性的值。設(shè)A1、A2為兩個任務(wù)，@表示某種模式，則(A1@A2)可合并成一個虛擬任務(wù)VA＜ID, SG, UA＞，其中VA.ID=A1.ID +A2.ID；VA.SG={cs1@cs2|cs1∈A1.SG and cs2∈A2.SG}，qi(cs1@cs2) = fk(qi(cs1), qi(cs2))，fk(x, y)是一個聚合函數(shù)(見表1)；VA.UA={A, B}。該合并過程也可以用于兩個虛擬任務(wù)或一個虛擬任務(wù)與一個任務(wù)之間。

表1 聚合函數(shù)的定義

VA.UA中的每個元素代表了可完成VA的一個虛擬任務(wù)vs，其效用函數(shù)可用式(1)定義：

式中，qmax(VA,i)、qmin(VA,i)分別為VA.UA中第i個QoS屬性的最大值與最小值。當(dāng)qmax(VA, i) = qmin(VA, i)時，sqi(vs)取值為1。

2 Top-k服務(wù)組合方法

根據(jù)工作流及虛擬任務(wù)的描述，O-QSC問題可以看成是從里到外的一系列虛擬任務(wù)的合并過程。以串((A⊙B)⊕(C?D))為例，可將(A⊙B)合并為V1，(C?D)合并為V2，再將(V1⊕V2)合并為V3，最后從V3.SG中優(yōu)選一個組合實例。若某工作流涉及n個任務(wù)，每個任務(wù)有m個候選服務(wù)，則最后生成的虛擬任務(wù)將有mn個候選服務(wù)，仍為指數(shù)形式的時空復(fù)雜度。本文采用的Top-k方法則是在每次合并虛擬任務(wù)時，僅為其保留k個最優(yōu)的實例。該過程可由算法1描述。

若用合并虛擬任務(wù)的次數(shù)來度量算法1的時間復(fù)雜度，顯然為O(n)?？紤]到每次合成虛擬任務(wù)時，需要從m2或m×k或k2個組合實例中優(yōu)選k個，若采用先排序后選擇的策略，且k ＜ m，則算法1的時間復(fù)雜度可達到O(nmlog2m)。合并過程中，算法1將產(chǎn)生的所有虛擬任務(wù)依次保存于虛擬任務(wù)列表(VAL)中，它將作為算法2的輸入之一。

算法1：Top-k服務(wù)組合

輸入：描述工作流的串OL及k值

輸出：組合實例cs及虛擬任務(wù)列表VAL

3 尋找替換服務(wù)

基于案例推理(case-based reasoning, CBR)策略，文獻[30]提出了一種自治愈框架，其中一個關(guān)鍵問題就是當(dāng)組合方案中的某個服務(wù)運行出現(xiàn)異常時，如何高效地為其尋找到一個合適的替代服務(wù)。盡管算法1實際上可以給出k組組合方案，但這些組合方案往往都涉及某些服務(wù)，當(dāng)這些服務(wù)中的某個出現(xiàn)異常時，就不能相互替換了。因此，本文通過算法2為組合方案中涉及的每個服務(wù)尋找一個替代服務(wù)，其中cs(A)表示任務(wù)A的候選服務(wù)集，UCS(cs)表示組合實例cs涉及的原子服務(wù)的集合。該算法基于如下的假設(shè)：對于一個虛擬任務(wù)的兩個優(yōu)選候選服務(wù)，如果它們所涉及的原子服務(wù)中僅有一對是不相同的，則這對原子服務(wù)是可以相互替換的。例如，對于工作流(P⊙A)，若存在優(yōu)選的組合實例(P11, A11)與(P11, A12)，則A11與A12是可替換的。

設(shè)一個虛擬任務(wù)的優(yōu)選候選服務(wù)個數(shù)為k，它們可以形成k(k?1)/2對服務(wù)組合，故算法2的時間復(fù)雜度為O(nk2)，n為工作流中涉及的任務(wù)個數(shù)。該算法并不能總為每個服務(wù)尋找到至少一個可替代服務(wù)，但當(dāng)k稍大時，能夠成功找到的概率是很大的，后面的測試將證明這一點。

算法2：尋找替換服務(wù)

輸入：組合實例cs，虛擬任務(wù)列表VAL

輸出：替換服務(wù)列表AS

4 實驗分析

為了驗證該方法的有效性，本文分別從k值對效用值的影響、算法的求解質(zhì)量、時間開銷以及可替代性能4個方面進行分析。

4.1 實驗環(huán)境

該實驗是在一臺擁有Intel(R) Core (TM) i5-2 430 M、2.4 GHz Intel Xeon雙核處理器、4 GB RAM、Win7操作系統(tǒng)的Lenovo PC機上實現(xiàn)的，實驗代碼用Java 7編寫。測試時，包含順序、選擇和并發(fā)模式的復(fù)雜工作流是隨機產(chǎn)生的，其中并發(fā)、選擇模式的數(shù)量各占1/4。分配給每個候選Web服務(wù)的QoS值來源于QWS數(shù)據(jù)集[31-32]，它包含了2 508個真實Web服務(wù)，每個服務(wù)擁有10個質(zhì)量屬性，測試時選用了具有代表性的響應(yīng)時間、吞吐量、可靠性等3個屬性。每種規(guī)模測試20次后取平均值。

4.2 實驗結(jié)果

4.2.1 k值對效用的影響

圖3為不同規(guī)模、不同k值時的效用，為了使不同情況下效用值的對比效果更明顯，突出k值對效用的影響，這里以k=1時的效用值為參考標(biāo)準(即設(shè)k=1時的效用比值為1)，其它k值時的效用比值為其實際效用值與k=1時的實際效用值之比。從圖中可以看出：1) 相同問題規(guī)模下，效用比值隨k值的增大而緩慢增大；2) 當(dāng)k=10時，已經(jīng)可以得到較為理想的優(yōu)化效果；3) 同樣的k值時，效用隨問題規(guī)模的增大而略有降低。

圖3 不同k值下的效用比值

4.2.2 算法的求解質(zhì)量

圖4對不同問題規(guī)模下Top-k優(yōu)選(k=10)、局部選擇、遺傳算法(genetic algorithm, GA)等3種方法的效用值進行了比較。該圖的縱坐標(biāo)是以Top-10方法得到的效用值為參考標(biāo)準的，即設(shè)Top-k方法的效用比值為1，而其它情況為其效用值與Top-10方法效用值之比。從圖中可以看出，Top-k優(yōu)選的效用值明顯高于局部選擇算法和GA算法。

圖4 算法求解質(zhì)量的比較

4.2.3 時間開銷分析

圖5給出了不同k值、不同規(guī)模下，Top-k方法的時間開銷情況。從中可以發(fā)現(xiàn)，該方法的時間開銷大致與n2、m2成正比，與k值關(guān)聯(lián)不大。測試代碼仍有一定優(yōu)化空間，整體時間開銷較為理想。

4.2.4 可替代性能分析

本文從能夠?qū)ふ业教娲桨傅母怕蕆/t(r表示方案中所提到的Web服務(wù)個數(shù)，t表示至少尋找到一個可替代服務(wù)的Web服務(wù)個數(shù))及替代方案的質(zhì)量兩個方面評價算法的可替代性能。

從圖6可以看出，可替代概率隨k值的增大而增大；當(dāng)k=12時，該概率可達80%。

在替代方案的質(zhì)量測試中，本文將k=10、k=20時的替代效果與M2(局部最優(yōu))、M3(QoS效用差距最小[30])、M4(隨機選擇)3種情況進行了比較(見圖7，以M2的效用值作為參考)。M2是選擇候選服務(wù)中綜合效用最高的(局部最優(yōu))，M3是選擇候選服務(wù)中與需要替換的服務(wù)的QoS差距最小的，M4是從候選服務(wù)中隨機選擇。該算法的效果略優(yōu)于其他算法。

圖5 不同k值下的時間開銷

圖6 不同k值下的可替代概率

圖7 替代效果的比較

5 結(jié) 束 語

通過將工作流描述為一個符號串，本文提出了一種由里及外逐步合并虛擬任務(wù)的Web服務(wù)組合方法；為了降低時空復(fù)雜度，在每次合并虛擬任務(wù)時采用了Top-k優(yōu)選策略。這種方法兼顧了局部優(yōu)選與全局優(yōu)選的特點，可以以較小的時間復(fù)雜度獲得較優(yōu)的組合方案。同時，本文給出了一種新的尋找可替換服務(wù)的算法，支持一定的自治愈能力。

[1] LIU Xuan-zhe, HUANG Gang, HONG Mei. Discovering homogeneous web service community in the user-centric web environment[J]. IEEE Transaction on Services Computing, 2009, 2(2): 167-181.

[2] 張佩云, 黃波, 孫亞民. 面向服務(wù)組合的服務(wù)語義匹配機制[J]. 電子科技大學(xué)學(xué)報, 2008, 37(6): 917-921.

ZHANG Pei-yun, HUANG Bo, SUN Ya-min. Service semantic matching mechanism for web services composition[J]. Journal of University of Electronic Science and Technology of China, 2008, 37(6): 917-921.

[3] ZOU Guo-bing, LU Qiang, CHEN Yi-xin, et al. QoS-Aware dynamic composition of web services using numerical temporal planning[J]. IEEE Transactions on Services Computing, 2014, 7(1): 18-31.

[4] WANG Peng-wei, DING Zhi-jun, JIANG Chang-jun, et al. Constraint-aware approach to web service composition[J]. IEEE Transactions on Systems Man & Cybernetics Systems, 2014, 44(6): 770-784.

[5] 陳文宇, 張忠全, 向濤, 等. 基于相似度的語義Web服務(wù)發(fā)現(xiàn)技術(shù)研究[J]. 電子科技大學(xué)學(xué)報, 2010, 39(6): 896-899.

CHEN Wen-yu, ZHANG Zhong-quan, XIANG Tao, et al. Research on similarity-based semantic web services discovery[J]. Journal of University of Electronic Science and Technology of China, 2010, 39(6): 896-899.

[6] YU Tao, ZHANG Yue, LIN Kwei-jay. Efficient algorithms for web services selection with end-to-end QoS constraints[J]. ACM Transactions on the Web Service, 2007, 1(1): 1-26.

[7] ARDAGNA D, PERNICI B. Adaptive service composition in flexible processes[J]. IEEE Transactions on Software Engineering, 2007, 33(6): 369-384.

[8] ZENG Liang-zhao, BENATALLAH B, DUMAS M, et al. QoS-aware middleware for web services composition[J]. IEEE Transactions Software Engineering, 2004, 30(5): 311-327.

[9] ALRIFAI M, RISSE T. Combining global optimization with local selection for efficient QoS-aware service composition[C]//Proceedings of the 18th International Conference on World Wide Web. New York: ACM, 2009: 881-890.

[10] LUO Yuan-sheng, QI Yong, HOU Di, et al. A novel heuristic algorithm for QoS-aware end-to-end service composition[J]. Computer Communications, 2011, 34(9): 1137-1144.

[11] JAEGER M C, MUHL G, GOLZE S. QoS-aware composition of web services: an evaluation of selection algorithms[C]//OTM Confederated International Conference. Berlin Heidelberg: Springer, 2005: 646-661.

[12] 馮建周, 孔立富. 基于QoS的Web服務(wù)組合中多路徑全局優(yōu)化方法的研究[J]. 小型微型計算機系統(tǒng), 2013, 34(7): 1493-1497.

FENG Jian-zhou, KONG Li-fu. Research on the method of multi-path global optimization in QoS-based Web service composition[J]. Journal of Chinese Computer Systems, 2013, 34(7): 1493-1497.

[13] GABREL V, MANOUVRIER M, MURAT C. Web services composition: Complexity and models[J]. Discrete Applied Mathematics, 2014, 196(2): 67-82.

[14] KLEIN A, ISHIKAWA F, HONIDEN S. Efficient heuristic approach with improved time complexity for QoS-aware service composition[C]//IEEE International Conference on Web Services. Washington, USA: IEEE Computer Society, 2011: 436-443.

[15] DING Zhi-jun, LIU Jun-jun, SUN You-qing, et al. A transaction and QoS-aware service selection approach based on genetic algorithm[J]. IEEE Transactions on Systems Man & Cybernetics Systems, 2015, 45(7): 1035-1046.

[16] YU Yang, MA Hui, ZHANG Meng-jie. An adaptive genetic programming approach to QoS-aware web servicescomposition[C]//IEEE Congress on Evolutionary Computation. Cancun: IEEE Computer Society, 2013: 1740-1747.

[17] 溫濤, 盛國軍, 郭權(quán), 等. 基于改進粒子群算法的Web服務(wù)組合[J]. 計算機學(xué)報, 2013, 36(5): 1031-1046.

WEN Tao, SHENG Guo-jun, GUO Quan, et al. Web service composition based on modified particle swarm optimization[J]. Chinese Journal of Computers, 2013, 36(5): 1031-1046.

[18] YU Qing, CHEN Ling, LI Bin. Ant colony optimization applied to web service compositions in cloud computing[J]. Computer and Electrical Engineering, 2015, 41(1): 18-27.

[19] YILMAZ A E, KARAGOZ P. Improved genetic algorithm based approach for QoS aware web service composition[C]//IEEE International Conference on Web Services. Anchorage: IEEE Computer Society, 2014: 463-470.

[20] 張燕平, 荊紫慧, 張以文, 等. 基于離散粒子群算法的動態(tài)Web服務(wù)組合[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] YIN Hao, ZHANG Chang-sheng, GUO Ying, et al. An improved evolutionary multiobjective service composition algorithm[C]//The International Symposium on Computational Intelligence and Design. Hangzhou, China: IEEE, 2013, 1: 269-272.

[22] 蘇凱, 馬良荔, 郭曉明, 等. 一種QoS感知的服務(wù)全局優(yōu)化選擇算法[J]. 華中科技大學(xué)學(xué)報(自然科學(xué)版), 2014, 42(4): 72-76.

SU Kai, MA Liang-li, GUO Xiao-ming, et al. QoS-aware service selection global optimization algorithm[J]. Journal of Huazhong University of Science and Technology. (Natural Science Edition), 2014, 42(4): 72-76.

[23] ZHANG Wei, CHANG C K, FENG Tai-ming, et al. QoS-based dynamic web service composition with ant colony optimization[C]//37th Annual IEEE International Computer Software and Applications Conference. Seoul: IEEE Computer Society, 2010: 493-502.

[24] 夏亞梅, 程渤, 陳俊亮, 等. 基于改進蟻群算法的服務(wù)組合優(yōu)化[J]. 計算機學(xué)報, 2012, 35(2): 270-281.

XIA Ya-mei, CHENG Bo, CHEN Jun-liang, et al. Optimizing services composition based on improved ant colony algorithm[J]. Chinese Journal of Computers, 2012, 35(2): 270-281.

[25] 王尚廣, 孫其博, 楊放春. 基于全局QoS約束分解的Web服務(wù)動態(tài)選擇[J]. 軟件學(xué)報, 2011, 22(7): 1426-1439.

WANG Shang-guang, SUN Qi-bo, YANG Fang-chun. Web service dynamic selection by the decomposition of global QoS constraints[J]. Journal of Software, 2011, 22(7): 1426-1439.

[26] MARDUKHI F, NEMATBAKHSH N, ZAMANIFAR K, et al. QoS decomposition for service composition using genetic algorithm[J]. Applied Soft Computing, 2013, 6(5): 3409-3421.

[27] SUN S X, ZHAO Jing. A decomposition-based approach for service composition with global QoS guarantees[J]. Information Sciences, 2012, 199(15): 138-153.

[28] LIU Zhi-zhong, XUE Xiao, SHEN Ji-quan, et al. Web service dynamic composition based on decomposition of global QoS constraints[J]. Int J Adv Manuf Technol, 2013, 69(9): 2247-2260.

[29] TAN Wei, ZHOU Meng-chu. Business and scientific workflow: a web service-oriented approach[M]. IEEE Press Series on Systems Science and Engineering. Wiley: IEEE, 2013.

[30] LI Guo-qiang, LIAO Le-jian, SONG Dan-dan, et al. A fault-tolerant framework for QoS-aware web service composition via case-based reasoning[J]. International Journal of Web and Grid Services, 2014, 10(1): 88-99.

[31] AL-MASRIE E, MAHMOUD Q H. Discovering the best web service[C]//Proceedings of the 16th International Conference on World Wide Web. New York: ACM, 2007: 1257-1258.

[32] AL-MASRI E, MAHMOUD Q H. QoS-based discovery and ranking of web services[C]//Proceedings of the 16th International Conference on Computer Communications and Networks. Honolulu: IEEE, 2007: 529-534.

編 輯 蔣 曉

A Self-Healing QoS-Aware Web Service Composition Method

YE Heng-zhou1,2, LI Tao-shen3, and GUAN Yun-hui2

(1. College of Electrical Engineering, Guangxi University Nanning 530004; 2. College of Information Science and Engineering, Guilin University of Technology Guilin Guangxi 541000; 3. School of Computer, Electronics and Information, Guangxi University Nanning 530004)

The quality of service (QoS)-aware web service composition problem is a research hotspot. Its objective is to select a composite service which can maximizes the QoS utility while preserving QoS constraints. By giving the definition of usual workflow and the combination rule of virtual tasks, a top-k based web service composition approach is proposed. Its core idea is to transform the original workflow into a virtual task by recursively calling the combination rule of virtual tasks. Moreover, a new scheme is presented to select suitable replaceable services to support the self-healing property. The effectiveness of the k value and the performances of algorithms are analyzed through simulation experiments.

QoS-aware; self-healing; service composition; top-k optimization

TP393

A

10.3969/j.issn.1001-0548.2017.03.023

2015 ? 02 ? 24；

2015 ? 06 ? 19

國家自然科學(xué)基金(51365010)；廣西自然科學(xué)基金(2014GXNSFBA118269)

葉恒舟(1980 ? )，男，副教授，主要從事服務(wù)組合、云計算及優(yōu)化設(shè)計方面的研究.