面向成本最小化的組合服務可靠性優化分配

李昌志，付曉東，2，田 強，王 威，夏永瀅

(1.昆明理工大學信息工程與自動化學院，昆明 650500;2.云南省計算機技術應用重點實驗室，昆明 650500)

1 概述

Web 服務是一種基于網絡環境的、模塊化的應用程序［1］，具有松散耦合、平臺無關、互操作性強等特點［2］。在單個Web 服務無法滿足用戶需求的情況下，可以將若干個Web 服務組合起來協同工作。Web 服務組合(也稱為組合服務)是指將若干個已存在的Web 服務按照一定規則動態發現，并組裝成一個增值的、更大粒度的服務或系統以滿足用戶復雜需求的過程［3-4］。

由于被組合的Web 服務是由不同組織發布、分布在Internet 上，具有自治特征的軟件組件，開放、動態、難控的網絡環境下實現各類Web 服務資源集成和共享的Web 服務組合，服務質量(Quality of Service，QoS)成為決定其能否成功的關鍵因素之一［5］。Web 服務的QoS 指服務的響應時間、價格、可用性、可靠性、信譽等非功能屬性［6］，在開放和動態的網絡環境下，提供具有QoS 保證的Web 服務是非常必要的，所謂QoS 保證就是在服務計算模式下，協調屬于不同組織與機構的各種服務，在問題求解過程中保證服務的質量［7］。而可靠性是提供具有QoS保證服務的基礎，沒有可靠性保證的Web 服務，其他服務質量屬性就無從談起。為此，本文對Web 服務組合的可靠性進行分析和研究，將Web 服務組合的可靠性指標約束分配給各組件服務(組件服務是指Web 服務組合的基本構成元素)，而組件服務的可靠性又與成本(成本指的是組合服務達到一定的可靠性投入的費用)密切相關。為了實現可靠性目標且成本最小化，本文提出基于遺傳算法的Web 服務組合可靠性分配方法，建立可靠性分配優化模型，模型以定量的方式將Web 服務組合的可靠性指標分配給組件服務并使得成本最低。這樣在保證Web 服務組合高可靠性的前提下，對可靠性指標進行了合理分配，控制了成本，優化了資源配置。

2 相關工作

近年來，一些學者站在不同的角度對Web 服務組合的可靠性做了一系列研究，如文獻［8-9］，提出了一種將全局QoS 約束分解為局部約束，通過局部約束找到全局最優或近似全局最優的Web 服務組合。文獻［10］提出了一種基于Petri 網分析Web 服務組合可靠性的方法，探索了可靠性數據的采集。文獻［11］針對服務組合中的可靠性和相關性能評估問題，提出了一種基于離散時間馬爾可夫鏈(Discrete Time Markov Chain，DTMC)的評估方法，從不同運行場景的角度，利用DTMC 相關性質和公式綜合估算了服務組合的可靠性，并針對具體服務組合的瓶頸進行了分析，提出了改進措施。文獻［12］提出一種可靠性優化方法，利用恢復塊和N 版本程序設計可以有效地增強服務組合的可靠性，該文在服務組合的可靠性預測模型的基礎上，提出了2 種可靠性優化模型。文獻［13］提出面向服務的基于體系結構的可靠性分析方法，給出了一種體系結構以實現可靠性預測。

以上研究只考慮了Web 服務組合的可靠性［10-11］，沒有考慮組件服務的可靠性，并且對提高Web 服務組合可靠性的成本沒有進行控制。再者利用Petri 網［10，12］對Web 服務組合進行建模，只能表達出Web 服務組合的邏輯及服務之間的關系，不能對Web 服務組合流程進行定量分析。文獻［13］只處理了2 種結構，并未考慮到Web 服務的多種結構。針對上述問題，本文在多種組合模式下，分析每種組合模式特點及其可靠性，既能清晰表達Web 服務組合之間的邏輯關系，又能對Web 服務組合流程進行定量分析，并通過可靠性分配優化模型，將可靠性指標合理地分配給組件服務，同時把成本控制到最低。

3 Web 服務組合流程及其可靠性

在Web 服務組合中，通常在結構化流程的基礎上對其進行研究［14］，即服務之間可以嵌套，不能交叉。結構化流程可以表示大多數Web 服務組合場景，并且非結構化流程可以轉換為結構化流程［15］。因此，本文重點考慮結構化組合流程的可靠性分配問題。文獻［16-17］總結了4 種Web 服務組合模式:順序，循環，選擇，并行。在此基礎上本文也考慮這4 種組合模式，即Sequence，Loop，XOR，AND 組合模式，如圖1 所示。在每種組合模式下，對其可靠性進行分析。

圖1 Web 服務組合模式

Sequence 的執行語義是順序執行包含在該結構中的組件服務(如圖1 中的CP1)。假定包含的組件服務的數量為N，則Sequence 模式的可靠性為:

其中，R(si)為組件服務si的可靠性。

Loop 的執行語義是某一組件服務的重復執行(如圖1 中的CP2)。假定組件服務si重復執行N 次，則Loop 模式的可靠性為:

XOR 的執行語義是多個分支的選擇執行，也就是從多個執行分支中選擇一個分支執行(如圖1 中的CP3)。假定分支的數目為N，執行組件服務si的概率為pi，并且滿足約束，則XOR 模式的可靠性為:

AND 的執行語義是所包含的多個組件服務的并行執行(如圖1 中的CP4)。假定包含的組件服務數量為N，則AND 模式的可靠性為:

基于以上分析，通過一個實例來計算Web 服務組合的可靠性。假如有Web 服務組合流程如圖2 所示，該Web 服務組合流程中有7 個組件服務，即S1，S2，S3，S4，S5，S6，S7。從整體來看，S1，AND 模式，S7組成一個Sequence 模式，其中AND 模式有2 個分支，即S2，XOR 模式和S3，LOOP 模式2 個分支，這2 個分支分別是一個Sequence 模式，其中，XOR 模式包含2 個分支S4，S5，LOOP 模式包含1 個組件服務S6。該組合流程的可靠性為:

圖2 Web 服務組合流程

4 組合服務可靠性分配優化模型

組合服務的可靠性分配優化模型需要將可靠性指標合理分配給組件服務，同時將成本最小化。因此，模型要求組件服務的可靠性與成本之間存在一種定量關系。本節首先給出了表示這種關系的可靠性成本函數，再給出可靠性分配優化模型。

4.1 可靠性成本函數

文獻［18-19］概括了表示可靠性和成本之間的定量關系函數。在此基礎上，本文將可靠性成本函數歸納為2 類:線性函數和非線性函數，這2 類函數表達式分別為式(6)～式(7)，圖3～圖4 分別為2 類函數的示例圖。這2 類函數都源于可靠性和成本之間的真實假設，即關于可靠性R(si)的成本函數是嚴格遞減的，則且呈現凸性，則

圖3 線性成本函數

圖4 非線性成本函數

線性可靠性成本函數:

非線性可靠性成本函數:

4.2 可靠性分配優化模型

可靠性分配是指將Web 服務組合的可靠性指標合理地分配給組件服務，以確定該Web 服務組合各組件服務的可靠性定量要求，從而保證整個Web 服務組合的可靠性指標，合理分配各組件服務的可靠性有助于提高Web 服務組合的經濟性和安全性［20］。

本文提出基于遺傳算法的可靠性分配方法，先由式(5)得到Web 服務組合流程的可靠性，此可靠性大于給定的可靠性指標R*作為約束，再通過組件服務的可靠性和成本之間的關系函數，得到總成本，此總成本作為目標函數，至此就獲得了Web 服務組合的可靠性分配優化模型。然后利用遺傳算法求解模型，獲得組件服務的可靠性，即實現了對組件服務的可靠性分配，保證了Web 服務組合的高可靠性指標，同時將成本控制到最低。可靠性分配優化模型如下:

在式(8)中，由于被選擇的服務是有限的(服務選擇是指從功能相同、非功能特性各異的服務中進行選擇，更多服務選擇知識請參考文獻［21-22］)，模型假設被選擇的服務中，可靠性的下限值為li，上限值為ui;C(R(si))是組件服務的成本函數;Rs為Web 服務組合的可靠性。

5 遺傳算法求解模型分析與設計

Web 服務組合可靠性分配本質上是一個數學規劃問題，一般來說，使用傳統的優化算法可以進行求解。但是，如圖5 所示函數構成的優化問題具有非線性和多極值的特點［23］，使用傳統方法來尋求最優解是比較困難的，而遺傳算法本身固有的全局優化能力和潛在的并行性，使得它非常適用于具有復雜約束的優化問題［23］。遺傳算法的基本原理是仿效生物學中適者生存演變而來。遺傳算法的做法是把問題參數編碼為染色體，再利用迭代的方式進行選擇、交叉以及變異等運算規則來交換種群中的染色體信息，最終生成符合優化目標的染色體。

(1)染色體編碼

首先，需要針對模型設計染色體，包括基因字串的長度以及基因代表的含義，即對搜索空間的可行解以編碼的形式來呈現。一般的編碼方式采用二進制、格雷碼、浮點數、多參數級聯等編碼方式。

顯然，本文模型具有高精度要求，采用具有高精度和搜索空間大的浮點數編碼方式［24］，對于具有n 個組件服務的Web 服務組合，定義一個n 維向量X=(x1，x2，…，xn)來對染色體進行編碼，向量中每一位為相應組件服務的可靠性預留位置，并且每一位都保留到小數點后面第3 位，以便可靠性的精度精確到千分位(因為可靠性必須滿足0 ＜R(si)＜1)，如X=(0.559，0.958，0.982)是具有3 個組件服務的染色體編碼，其中每一位為相應組件服務的可靠性編碼，即第1 個組件服務的可靠性為0.559，第2 個組件服務的可靠性為0.958，第3 個組件服務的可靠性為0.982。

(2)種群初始化

對染色體實現編碼以后，必須產生一個初始種群，因此，首先需要確定初始化種群的數目。初始化種群的數目一般根據經驗得到，如果初始化種群的數目太大，則可能會消耗過多的搜索時間，但是如果太小，則會導致過早收斂［25］。一般情況下種群的數量視搜索空間的大小而確定，在種群初始化時采用隨機方式產生，并根據實驗部分的經驗將種群的大小限制在40～160 之間，因為對于本文模型，大小在這之間的種群具有良好的收斂性且時間消耗低。

(3)適應度函數的設定

適應度函數必須滿足單值、連續、非負和最大化，優化模型中目標函數顯然滿足單值、連續、非負條件，需要將目標函數乘以-1 轉化為最大化并加上一個較大的常數M 保證其非負性。因此，修正后的適應度函數為:

(4)終止條件設定

嚴格地講，遺傳算法迭代終止條件目前尚無定論［26］。在許多組合優化問題中，適應度最大值并不清楚，其本身就是搜索的對象，因此，終止條件很難確定。

采用式(8)的約束條件作為迭代的終止條件，發現合適的染色體解碼后能夠滿足式(8)的約束條件時，終止迭代。如果滿意解并不存在，而搜索空間又非常龐大，在這種情況下，若發現群體中個體的進化已經趨于穩定狀態時，終止迭代。

(5)選擇算子

選擇操作是從種群中選擇優勝個體，并淘汰劣質個體。選擇的目的是把優化的個體直接遺傳到下一代，或者通過配對交叉產生新的個體再遺傳到下一代。常用的選擇算子包括適應度比例法、最佳個體保留法、期望值法、排序選擇法等。選擇最基本和最常用的適應度比例法［27］來對種群中的個體進行選擇。

(6)交叉算子

交叉算子是遺傳算法中起核心作用的遺傳操作。交叉是指2 個父代個體的部分結構加以替換、重組而生成新個體的操作。常用的交叉算子包括一點交叉、二點交叉、多點交叉、一致交叉等。選擇工程上使用較多的二點交叉算子［24］，并選擇交叉概率為0.5。

(7)變異算子

變異算子的基本內容是對群體中個體串的某些基因座的基因值作變動。對于浮點數編碼，在可靠性范圍［li，ui］內，變異操作就是用該范圍內的一個隨機數去替換原基因值;一般來說，變異算子操作的基本步驟如下:

1)在群體的所有個體的碼串范圍內隨機確定基因座;

2)以事先確定的變異概率對這些基因座的基因值進行變異。

選用基本變異算子，并選定變異概率為0.001。

6 實驗驗證及分析

本文通過實例說明可靠性分配過程，通過模擬驗證本文方法實現成本優化的有效性和實用性，最后是收斂性分析。實驗環境為2 GB 內存、Inter Pentium T2370(1.73 GHz)、Windows XP 操作系統，實驗工具采用Matlab R2009a。

6.1 實例

Web 服務組合流程如圖2 所示，不失一般性，設循環次數k=3，p1=p2=0.5。

6.1.1 線性成本函數

設成本函數為f(R(si))=a×R(si)+b，組件服務s1-7對應的參數為a=［325，181，165，22，22，60，245］，b=［19，29，200，280，263，200，65］，li=0.01，ui=0.99，Web 服務組合的可靠性指標約束R*=0.930，由式(8)有:

利用遺傳算法求解得到組件服務的可靠性分配結果為R(s1-7)=［0.559，0.958，0.982，0.010，0.989，0.990，0.731］，所需成本C=1 833.5。

從實驗結果看，根據可靠性分配優化模型分配的可靠性，S6需要選擇可靠性值最高的組件服務，而S1-5，S7選擇合適的可靠性值就能夠達到可靠性指標R*=0.930。

6.1.2 非線性成本函數

設成本函數為f(R(si))=-bln(1 -exp(R(si)-1))，組件服務s1-7對應的參數為b=［20，40，70，80，100，120，140］，li=0.01，ui=0.99，Web 服務組合的可靠性指標為R*=0.930，求解模型同線性成本函數，此處不再贅述。得到組件服務可靠性分配結果為R(s1-7)=［0.959，0.907，0.851，0.015，0.236，0.917，0.769］，所需成本C=924.5。

由可靠性分配優化模型分配的可靠性來看，所有組件服務都沒必要選取最高可靠性值就能達到可靠性指標R*=0.930。

6.2 有效性驗證

為驗證本文方法的有效性，與取最高值法［28］、等分配法［20］等可靠性分配方法進行了比較。本文首先在成本函數變化，組件服務數量固定的情況下進行模擬;然后模擬真實環境下本文方法的有效性和實用性。

設成本函數變化，組件服務數量固定(7 個)，并用這7 個組件服務組合成5 種以上不同結構的Web 服務組合流程。由式(8)得到每種結構的可靠性分配優化模型，然后取成本的期望值，這樣有效避免了個別流程的特殊性。實驗結果如圖5、圖6 所示，以取最高值法為基準，記錄其他方法所需成本所占百分比隨成本函數變化的情況。實驗結果表明，當成本函數為線性時，與取最高值法相比，本文方法最少節約成本19.56%，最多節約成本62.67%，與等分配法相比最少節約成本19.54%，最多節約成本62.61%;當成本函數為非線性時，與取最高值法相比，本文方法最少節約成本37.93%，最多節約成本37.96%，與等分配法相比，最少節約成本37.29%，最多節約成本37.40%。

圖5 不同成本函數(線性)成本花費對比

圖6 不同成本函數(非線性)成本花費對比

在真實環境下，組件服務的數量是不同的，且不同組件服務的成本函數不一樣。所以為驗證本文方法在真實環境下的有效性和實用性，做了如下實驗。組件服務數不同，不同組件服務的成本函數不同，并且不同組件服務數量都組合成5 種以上不同結構的Web 服務組合流程。由式(8)得到每種結構的可靠性分配優化模型，再對成本取期望值。實驗結果如圖7、圖8 所示，以取最高值法為基準，記錄其他方法所需成本所占百分比的情況。實驗結果表明，當成本函數為線性時，與取最高值法相比，本文方法最少節約成本超過8%，最多節約成本17.60%，與等分配法相比，最少節約成本7.90%，最多節約成本超過17%;當成本函數為非線性時，與取最高值法相比，本文方法最少節約成本40.20%，最多節約成本55.22%，與等分配法相比，最少節約成本39.55%，最多節約成本47.36%。

圖7 線性成本花費對比

圖8 非線性成本花費對比

經過模擬對比實驗，結果表明本文方法始終優于取最高值法和等分配法，驗證了本文方法的有效性和實用性。

6.3 收斂性分析

適應度函數的收斂情況如圖9、圖10 所示。其中，算法的終止條件為找到了滿意解，在不超過10 代的情況下，就找到了滿意解，表明遺傳算法應用于本文優化模型具有很好的收斂性。圖9 的最佳適應度為1 634.138，平均適應度為1 977.204。

圖9 最佳及平均適應度值情況

圖10 最佳、最差及平均適應度值情況

7 結束語

在開放和動態的網絡環境下，提供滿足可靠性要求的低成本Web 服務組合具有非常重要的意義。為此，本文研究了Web 服務組合的可靠性和成本優化問題，提出基于遺傳算法的Web 服務組合可靠性分配方法，分析了Web 服務組合結構模式及其對應的可靠性函數，進一步給出組合服務的可靠性計算方法，建立可靠性分配優化模型，并利用遺傳算法對模型進行求解，這樣既保證了Web 服務組合的高可靠性要求，又將可靠性指標合理地分配給組件服務，同時使得所需成本最小化，具有現實的意義。最后模擬實驗驗證了本文方法的有效性和實用性，并驗證了其收斂性。

在獲得可靠的、低成本的Web 服務組合的方法后，結合QoS 的其他非功能屬性信息，解決隨機QoS感知的Web 服務選擇和組合的問題，是下一步要開展的研究工作。

［1］鄧水光，尹建偉，李 瑩，等.基于二分圖匹配的語義Web 服務發現方法［J］.計算機學報，2008，31(8):1364-1375.

［2］宋 巍，馬曉星，呂 建.Web 服務組合動態演化的實例可遷移性［J］.計算機學報，2009，32(9):1816-1831.

［3］李喜彤，范玉順.Web 服務流程相容性和相似性分析［J］.計算機學報，2009，32(12):2429-2437.

［4］郭玉彬，杜玉越，奚建清.Web 服務組合的有色網模型及運算性質［J］.計算機學報，2006，29(7):1067-1075.

［5］肖芳雄，黃志球，曹子寧，等.Web 服務組合功能與QoS的形式化統一建模和分析［J］.軟件學報，2011，22(11):2698-2715.

［6］Hwang S Y，Wang Haojun，Tang Jian，et al.A Probabilistic Approach to Modeling and Estimating the QoS of Web-services-based Workflows［J］.Information Science，2007，177(23):5484-5503.

［7］殷憲振，蔣 靜，潘振寬，等.SoC 應用系統中基于信用的QoS 保證機制［J］.計算機學報，2011，34(2):413-424.

［8］王尚廣，孫其博，楊放春.基于全局QoS 約束分解的Web 服務動態選擇［J］.軟件學報，2011，22(7):1426-1439.

［9］Alrifai M，Risse T.Combining Global Optimization with Local Selection for Efficient QoS-aware Service Composition ［C］//Proc.of the 18th International Conference on World Wide Web.Madrid，Spain:［s.n.］，2009:881-890.

［10］郭 峰，張 萌.Web 服務組合的可靠性分析［J］.系統仿真學報，2009，20(s2):94-96.

［11］曹科強，顧 慶，任穎新，等.服務組合中基于DTMC的可靠性和性能分析［J］.計算機科學，2009，36(10):179-183.

［12］鐘讀杭，齊治昌.基于冗余的Web 服務組合可靠性優化方法［J］.計算機工程，2008，34(4):31-33.

［13］Grassi V，Patella S.Reliability Prediction for Service Oriented Computing Environments［J］.IEEE Internet Computing，2006，10(3):43-49.

［14］Vander Aalst W M P，Hofstede A H M，Ewski B K，et al.Workflow Patterns ［J］.Distributed and Parallel Databases，2003，14(3):5-51.

［15］Chan P P W，Lyu M R.Dynamic Web Service Composition:A New Approach in Building Reliable Web Service［C］//Proc.of the 22nd International Conference on Advanced Information Networking and Applications.Ginowan，Japan:［s.n.］，2008:20-25.

［16］Zhang Guoping，Zhang Huijuan，Wang Zhibin.A QoSbased Web Services Selection Method for Dynamic Web Service Composition［C］//Proc.of the 1st International Workshop on Education Technology and Computer Science.Wuhan，China:［s.n.］，2009:15-29.

［17］蔣哲遠，韓江洪，王 釗.動態的QoS 感知Web 服務選擇和組合優化模型［J］.計算機學報，2009，32(5):1014-1025.

［18］Helander M E，Zhao Ming，Ohlsson N，et al.Planning Models for Software Reliability and Cost［J］.IEEE Transactions on Software Engineering，1998，24 (6):420-434.

［19］沈雪石，陳英武.基于可靠性的軟件構件費用分配最優模型［J］.系統工程與電子技術，2007，29(12):2186-2188.

［20］曾聲奎，馮 強.可靠性設計與分析［M］.北京:國防工業出版社，2011.

［21］蔣哲遠，韓江洪，王 釗.動態的QoS 感知Web 服務選擇和組合優化模型［J］.計算機學報，2009，32(5):1014-1025.

［22］吳 健，陳 亮，鄧水光，等.基于Skyline 的QoS 感知的動態服務選擇［J］.計算機學報，2010，33(11):2136-2146.

［23］Tian Pei，Wang Jiancheng，Zhang Wei，et al.A Fault Tree Analysis Based Software System Reliability Allocation Using Genetic Algorithm Optimization［C］//Proc.of World Congress on Software Engineering.Xiamen，China:［s.n.］，2009:194-198.

［24］雷英杰，張善文，李續武，等.Matlab 遺傳算法工具箱應用［M］.西安:西安電子科技大學出版社，2006.

［25］代桂平，王 勇，侯亞榮.基于遺傳算法的TSP 問題求解算法及其系統［J］.微計算機信息，2010，2(2):15-16.

［26］王 勇，胡春明，杜宗霞.服務質量感知的網格工作流調度［J］.軟件學報，2006，17(11):2341-2351.

［27］周 明，孫樹棟.遺傳算法原理及應用［M］.北京:國防工業出版社，1999.

［28］張仕健，許 彤，張隆兵，等.一個基于微處理器功能模型的可靠度評估系統［J］.計算機學報，2008，31(3):391-399.