基于服務(wù)質(zhì)量的動態(tài)Web服務(wù)組合方法研究

吳青林　周天宏

1(鄖陽師范高等?？茖W(xué)校計算機科學(xué)系　湖北 十堰 442000)2(武漢商學(xué)院信息工程系　湖北 武漢 430056)

?

基于服務(wù)質(zhì)量的動態(tài)Web服務(wù)組合方法研究

吳青林1周天宏2

1(鄖陽師范高等?？茖W(xué)校計算機科學(xué)系湖北 十堰 442000)2(武漢商學(xué)院信息工程系湖北 武漢 430056)

摘要針對Web服務(wù)組合中權(quán)重固定、選擇不靈活、性能不佳等問題，通過改進遺傳算法提出一種基于服務(wù)質(zhì)量的變權(quán)動態(tài)Web服務(wù)組合方法(VW-DWSC-QoS)。VW-DWSC-QoS組合方法使用變權(quán)QoS參數(shù)，引入罰函數(shù)策略，并動態(tài)調(diào)整變權(quán)因子、交叉因子和變異因子，使其實現(xiàn)了在較短時間內(nèi)找到符合用戶需求的Web服務(wù)組合。理論分析和仿真實驗表明該組合方法的可行性和有效性，與傳統(tǒng)的方法相比，其最優(yōu)解具有更好的服務(wù)質(zhì)量和適應(yīng)度。

關(guān)鍵詞動態(tài)Web服務(wù)QoS遺傳算法變權(quán)

0引言

Web服務(wù)是面向服務(wù)的體系結(jié)構(gòu)的一種實現(xiàn)技術(shù)，隨著大數(shù)據(jù)、云計算以及軟件即服務(wù)等的流行，互聯(lián)網(wǎng)上的Web服務(wù)數(shù)量不斷增加。Web服務(wù)在電子商務(wù)、教育、企業(yè)應(yīng)用集成等領(lǐng)域發(fā)揮的作用越來越重要。作為一種新型的分布式計算模式，具有的跨平臺、跨標(biāo)準(zhǔn)、跨語言特點使其受到工業(yè)界和學(xué)術(shù)界的廣泛關(guān)注，同時互聯(lián)網(wǎng)上的Web服務(wù)質(zhì)量各異，單個服務(wù)功能有限，不能夠最大限度地滿足用戶的多樣化需求。在實際應(yīng)用中，為了提供更合理的Web服務(wù)資源，需要基于特定的業(yè)務(wù)流程將多個Web服務(wù)組合成更大粒度的服務(wù)。因此，如何有效組合Web服務(wù)，從符合各結(jié)點功能的Web服務(wù)中選擇出具體的Web服務(wù)，滿足用戶對服務(wù)質(zhì)量多維度及不同偏好的需求，成為當(dāng)前Web服務(wù)領(lǐng)域研究的關(guān)鍵問題。

1相關(guān)工作

Web服務(wù)組合是Web服務(wù)應(yīng)用的關(guān)鍵環(huán)節(jié)，服務(wù)質(zhì)量QoS參數(shù)是服務(wù)優(yōu)劣的重要指標(biāo)，當(dāng)前基于服務(wù)質(zhì)量的Web服務(wù)組合中主要采用QoS局部優(yōu)化方法和全局優(yōu)化方法。局部優(yōu)化方法針對組合流程的單一結(jié)點選擇服務(wù)，全局優(yōu)化方法針對整個組合流程選擇不同的服務(wù)協(xié)同工作。文獻[1-3]對一組相同功能的服務(wù)，通過每個服務(wù)QoS的參數(shù)信息進行加權(quán)和排序，并將以此為選擇依據(jù)分別為組合流程的每個節(jié)點逐一選擇加權(quán)和最大的服務(wù)來構(gòu)建目標(biāo)組合服務(wù)。這種方法中各個結(jié)點選擇服務(wù)是相互獨立的，不能從全局角度上選擇服務(wù)。文獻[4,5]把組合服務(wù)的各個QoS約束參數(shù)線性加權(quán)為單目標(biāo)函數(shù)并通過線性規(guī)劃方法解決服務(wù)。文獻[6]提出了支持QoS 的服務(wù)組合計算模型，模型中考慮了權(quán)重的風(fēng)險級別。文獻[7]把尋求滿足多QoS屬性的組合問題轉(zhuǎn)化成為有向圖搜索最優(yōu)多約束問題。文獻[8]將服務(wù)的動態(tài)選擇過程看作Markov決策過程，以尋求使服務(wù)質(zhì)量最優(yōu)的方案。文獻[9]提出了支持QoS感知的組合算法，具有支持單個Web服務(wù)和組合Web服務(wù)QoS計算的功能。

當(dāng)前主要針對基于局部服務(wù)質(zhì)量的Web服務(wù)組合，但基于局部服務(wù)質(zhì)量的Web服務(wù)組合中各個單一服務(wù)的性能達到最優(yōu)并不能保證整個服務(wù)組合的性能最優(yōu)，需要整個考慮Web服務(wù)的質(zhì)量?；谌值腤eb服務(wù)質(zhì)量的Web服務(wù)組合還不成熟，主要存在以下不足：

(1) QoS屬性的賦權(quán)靈活性不夠，主要采用固定權(quán)重，賦權(quán)不具有伸縮性和模糊性，當(dāng)存在某服務(wù)的單一QoS屬性值特別高使Web質(zhì)量提升，這樣的服務(wù)有可能其他QoS屬性特別低不滿足用戶的需求，不能有效描述Web服務(wù)的質(zhì)量。

(2) 其產(chǎn)生的解為單解，并且目標(biāo)函數(shù)和約束是線性的，用戶沒有選擇的空間。在很多情況下用戶選擇Web服務(wù)組合時不一定需要最優(yōu)的，而是需要最符合自己要求的，從而限制了算法的應(yīng)用范圍。

(3) 當(dāng)服務(wù)數(shù)量增多時，計算量迅速增加，使組合時間會增加，交易成功率也會下降，服務(wù)組合的性能受到一定影響。

本文針對以上問題，通過改進遺傳算法提出了變權(quán)QoS全局動態(tài)Web服務(wù)組合方法(在DWSC-GA),方法中引入罰函數(shù)，利用迭代次數(shù)、動態(tài)交叉動態(tài)和變異因子等策略，實現(xiàn)了在較短時間內(nèi)找到符合用戶需求的Web服務(wù)組合方案。

2QOS屬性及四種組合結(jié)構(gòu)描述

(1) 原子服務(wù)QoS描述

原子服務(wù)質(zhì)量描述是多維的, 本文定義q(s) = {q1(s),q2(s),…,qn(s)}表示服務(wù)s的n維質(zhì)量屬性值，其中qk(s)表示服務(wù)s的第k個屬性值,服務(wù)質(zhì)量屬性值可以從服務(wù)提供者、歷史交易情況或用戶等多方面獲取。本文選擇響應(yīng)時間、成本、可靠性、信譽度作為原子服務(wù)QoS屬性。

(2) 服務(wù)組合描述

服務(wù)組合是將較小的細粒度服務(wù)組合成粗粒度服務(wù)，其可以包括原子服務(wù)也可以嵌套包括其他組合服務(wù)。組合服務(wù)的服務(wù)質(zhì)量屬性通過原子服務(wù)的服務(wù)質(zhì)量聚合形成，本文定義q(cs)={q1(cs),q2(cs),…,qn(cs)}表示組合服務(wù)n維質(zhì)量屬性值，其中qk(cs)表示組合服務(wù)s的第k個屬性值。組合服務(wù)流程是一個基于Web服力的的工作流，大部分組合流程可以由串聯(lián)模型、并列模型、選擇模型和循環(huán)模型組合而成[10-12]。表1給出了四種組合模型結(jié)構(gòu)相應(yīng)用QOS模型計算表達式。

表1　組合服務(wù)QoS屬性計算方法

3服務(wù)預(yù)處理

3.1服務(wù)屬性的歸一化處理

Web服務(wù)的QoS屬性的計量單位和取值范圍不具有可比性,有些屬性取值越大,其性能就越低,屬于負(fù)屬性,例如響應(yīng)時間；另外一些屬性取值越大,表示其性能越高,例如可用性。并且其不同屬性之間數(shù)值相差巨大。因此在考慮其不同的QoS屬性進行組合時應(yīng)該對其服質(zhì)進行歸一化處理,將其轉(zhuǎn)化成無量綱的值,將其范圍都限定在[0-1]之間。為了使各種QoS屬性統(tǒng)一,本文采用式(1)和式(2)分別對增量型和減量型參數(shù)進行歸一化[13,14]。

(1)

(2)

3.2權(quán)重獲取

如果用戶能夠明確指定Web服務(wù)權(quán)重，則直接獲得權(quán)重，如果用戶對權(quán)重用自然語言描述，可以參照表2的數(shù)據(jù)，通過對應(yīng)關(guān)系將其轉(zhuǎn)化為固定權(quán)值[15,16]。

表2　自然語言描述與模糊集數(shù)據(jù)對照

3.3變權(quán)處理

針對在服務(wù)選擇過程中存在某單一屬性值很高導(dǎo)致綜合屬性變高，卻因為其他屬性很低無法滿足用戶要求的問題，本文通過變權(quán)向量解決這一問題，基本思路是影響QoS屬性的權(quán)重根據(jù)其取值范圍做一定的變化，以使每個屬性更好體現(xiàn)在組合服務(wù)中的作用。

(3)

L的取值根據(jù)應(yīng)用要求決定。通過式(3)變權(quán)向量進行加權(quán)綜合計算Web服務(wù)質(zhì)量時，可以有效降低因個別QoS屬性值相差較大的Web服務(wù)的質(zhì)量值，從而更好地反映服務(wù)的質(zhì)量屬性。容易證明，變化后的權(quán)重向量仍然滿足歸一性。

4基于服務(wù)質(zhì)量的動態(tài)Web服務(wù)組合方法(VW-DWSC-QoS)

該方法基于改進遺傳算法實現(xiàn)，遺傳算法GA (Genetic Algorithm)首先由Holland教授在上世紀(jì)七十年代提出[17]，模擬自然界生物進化過程與機制求解極值問題的一類自組織、自適應(yīng)搜索算法，具有較強的魯棒性和通用優(yōu)化能力，廣泛地應(yīng)用于求解復(fù)雜的非線性和多維空間尋優(yōu)問題。

第一步染色體編碼

本文采用關(guān)系矩陣方式對染色體編碼，該方式能夠很好地反映組合服務(wù)的相互關(guān)系。關(guān)系矩陣主對角線上的元素表示遺傳算法染色體的基因位，與Web服務(wù)組合的工作任務(wù)相對應(yīng)，非對角線元素表示組合服務(wù)任務(wù)之間的關(guān)系，染色體編碼如圖1所示。

圖1染色體矩陣編碼

染色體編碼反映了組合Web服務(wù)中包括的任務(wù)及其關(guān)系，對角線元素Bii=1表示組合服務(wù)包含該任務(wù)，Bii=0表示組合服務(wù)沒有包括該任務(wù)。非對角線元素BIJ為任務(wù)關(guān)系位，如果BIJ=1，表示在組合服務(wù)中任務(wù)i與任務(wù)j相鄰，并位于其直接前方。染色體編碼通過矩陣主對角線的元素排列實現(xiàn)，組合服務(wù)集合中選出部分編碼用為遺傳算法的初始群即為種群，各類遺傳操作針對矩陣對角線的元素實現(xiàn)。

第二步初始化群體

根據(jù)Web服務(wù)所能完成的原子處理任務(wù)分類，產(chǎn)生初始Web服務(wù)群體p=(p1,p2,…,p3)，pn為Web服務(wù)種群規(guī)模大小，根據(jù)經(jīng)驗或者是專家提供的建議得出，這里取pn=100。

第三步計算個體適應(yīng)度

Web服務(wù)用戶一般會對資源服務(wù)的選擇提出響應(yīng)時間、使用成本等方面的要求或限制。本文適應(yīng)度函數(shù)通過罰函數(shù)法將限制條件與目標(biāo)函數(shù)綜合在一起實現(xiàn)，可以通過下式實現(xiàn)：

(4)

式(1)中的Rjmax表示第j個約束條件的最大值，Rj min表示第j個約束條件的最小值,n表示用戶提出的約束條件的個數(shù)，λ是罰函數(shù)系數(shù)，屬于經(jīng)驗值。Pj表示一個Qj或者多個Qj組合的運算值，ΔPi通過下式表示：

(5)

第四步選擇

選擇方法采用精英個體優(yōu)選策略，根據(jù)適應(yīng)度函數(shù)判斷當(dāng)前適應(yīng)度最好的Web服務(wù)組合，將適應(yīng)度最好的Web服務(wù)組合篩選出不進行遺傳操作，而將該個體替換本代遺傳操作后產(chǎn)生的適應(yīng)度最低的Web服務(wù)組合，經(jīng)過精英個體優(yōu)選策略實現(xiàn)了父代中最優(yōu)的Web服務(wù)組合遺傳到下一代，而最劣的Web服務(wù)組合直接淘汰，有效地保證了遺傳Web服務(wù)組合的質(zhì)量。

第五步交叉和變異

根據(jù)其Web服務(wù)組合個體適應(yīng)度數(shù)值選擇合適的交叉概率和變異概率，在個體遺傳過程中根據(jù)適應(yīng)度數(shù)值大小的變化動態(tài)調(diào)節(jié)交叉概率和變異概率的數(shù)值，這樣每個個體能夠動態(tài)適應(yīng)遺傳環(huán)境。在染色體遺傳過程中，設(shè)群體中具有較低適應(yīng)度個體的交叉概率為Pc0,具有最高個體適應(yīng)度個體的交叉概率為Pcl(其中Pcl

(6)

(7)

第六步終止

本算法的結(jié)束條件根據(jù)最大迭代次數(shù)法則來決定，推薦Web服務(wù)組合個體適應(yīng)度最大的解作為最終解。滿足以下終止條件之一即可結(jié)束進化過程：(1) 出現(xiàn)適應(yīng)度為零的Web服務(wù)種群；(2) 出現(xiàn)適應(yīng)度值達到滿足用戶需求的個體；(3) 群體中的最優(yōu)個體已經(jīng)沒有明顯的進化效果；(4) 進化代數(shù)已經(jīng)達到算法設(shè)定的代數(shù)。

5DWSC-GA算法分析

本文提出的算法VW-DWSC-QoS算法，對部分單QoS屬性值較高的Web服務(wù)對象，使用了QoS變權(quán)處理，并在組合過程中引入罰函數(shù)策略，動態(tài)調(diào)整變權(quán)因子、交叉因子和變異因子，使其實現(xiàn)了在較短時間內(nèi)找到符合用戶需求的Web服務(wù)組合，理論分析，優(yōu)點主要體現(xiàn)在以下方面：

(1) 該模型中，首先將不同綱量的QoS參數(shù)轉(zhuǎn)化成[0 1]之間的參數(shù)，便于加權(quán)處理，并對單一QoS屬性作變權(quán)處理，其QoS屬性的權(quán)重根據(jù)其取值范圍做一定的變化，使得每個屬性更好地體現(xiàn)在組合服務(wù)中的作用。

(2) 適應(yīng)度函數(shù)通過罰函數(shù)法將限制條件與目標(biāo)函數(shù)綜合在一起實現(xiàn)，使個體適應(yīng)度動態(tài)適應(yīng)服務(wù)環(huán)境變化。

(3) 在遺傳過程中根據(jù)適應(yīng)度的變化自動調(diào)節(jié)交叉概率和變異概率的數(shù)值,這樣每個個體具有自適應(yīng)環(huán)境的能力。

(4) 關(guān)系矩陣方式對染色體編碼，該方式既能反映服務(wù)的組合并系，還能體現(xiàn)任務(wù)路徑信息的編碼方式。

6仿真實驗

仿真實驗的計算機配置是Pentium 3500 MH處理器，2 GB內(nèi)存，操作系統(tǒng)為win7系統(tǒng)，Matlab8.1軟件。由于當(dāng)前沒有成熟的Web服務(wù)合測試集，本實驗指定服務(wù)模型，根據(jù)服務(wù)模型將目標(biāo)任務(wù)分解為5個子任務(wù)，5個子任務(wù)所對應(yīng)的候選服務(wù)范圍為5到60，從每個子任務(wù)中選擇一個候選服務(wù)進行組合，以完成用戶目標(biāo)任務(wù)。設(shè)每個候選服務(wù)的QoS屬性分別為響應(yīng)時間(t)，成本(c)，可靠性(av)，信譽度(rep)，依3.2節(jié)權(quán)重獲取方式，設(shè)其權(quán)重為(0.3,0.3,0.2,0.2),群體規(guī)模取50，最大迭代次數(shù)取150。分別設(shè)Pc0=0.68 ，Pcl=0.26，Pm0=0.42，Pml=0.19，經(jīng)組合方法獲取最優(yōu)組合。將從以下兩個方面進行性能比較：

1) 整數(shù)規(guī)劃算法和本文VW-DWSC-QoS算法組合時間變化：

當(dāng)每個任務(wù)的候選服務(wù)較少時，Integer Planning Algorithm比VW-DWSC-QoS算法具有一定的優(yōu)勢，但隨著候選服務(wù)的逐漸增加，Integer Planning Algorithm花費的時間增加較快，而本文提出的VW-DWSC-QoS算法所需時間沒有太明顯的增加，表現(xiàn)出較為明顯的優(yōu)勢。如圖2所示。

圖2　任務(wù)完成時間比較

2) 本文VW-DWSC-QoS算法與固定權(quán)重算法相比

實驗中的流程結(jié)構(gòu)采用順序結(jié)構(gòu)實現(xiàn)，當(dāng)每個結(jié)點的候選服務(wù)數(shù)增加時，服務(wù)組合成功率具有下降的趨勢，將VW-DWSC-QoS算法與固定權(quán)重算法相比，VW-DWSC-QoS算法組合成功率變化比較平緩，具有更高的組合成功率。如圖3所示。

圖3　任務(wù)交易成功率比較

從以上兩次實驗對比中可以看出本文提出的VW-DWSC-QoS算法使Web服務(wù)在組合時間和組合成功率上都有一定的進步，具有一定的實用價值。

7結(jié)語

Web服務(wù)組合在面向服務(wù)體系結(jié)構(gòu)軟件中的重要問題，將現(xiàn)有的服務(wù)組合成功能更強大的服務(wù)，能夠更好地增強Web服務(wù)價值。本文在相關(guān)研究的基礎(chǔ)上，提出的QoS感知的動態(tài)適應(yīng)Web服務(wù)組合，考慮了服務(wù)的動態(tài)適應(yīng)性，使其服務(wù)組合更能真實地反映Web服務(wù)的特點，提高了組合的質(zhì)量和效率，更好地滿足了用戶對Web服務(wù)的需求。

參考文獻

[1] Benatallah B,Dumas M.Declarative composition and peer-to-peer provisioning of dynamic Web services[C]//Proc of the 18 the International Conference on Data Engineering.San Jose:IEEE Computer Society,2002:297-308.

[2] Liangzhao Zeng,Boualem Benatallah.QoS Aware Middleware for Web Services Composition[J].IEEE Transactions on Software Enginneering,2004,30(5):311-327.

[3] Grafen P,Aberer K.Cross-low:cross-organizationl workflow management in dynamic virtual ebteroruses[J].Internional Journal of Computer Systems Science & Engineering,2000,15(5):277-290.

[4] Jorge C,Amit S.Quality of service for workflows and Web service processes[J].Joumal of Web Semantics,2004,1(3):281-338.

[5] 何必壯,徐哲,吳峰.基于IHE的動態(tài)語義Web服務(wù)組合研究[J].計算機應(yīng)用與軟件,2012,29(10):156-157.

[6] Joyce EI Haddad,Maude manouvrier.Dos-driven Selection of Web Services for Transactional Composition[C]//IEEE international Conference on web services,2008:653-660.

[7] Liu Qing,Zhang ShIlong.Web services composition with QoS bound based on simulated annealing algorithm[J].Journal of Southeast University(English Edition),2008,24(3):308-311.

[8] Prashant Doshi,Richard Goodwin.Dyanmic workflow composition using Markov decision processes.International[J].Journal of Web services research.Jan-March,2005,2(1):1-17.

[9] Megha Mohabey,Narahari Y.A combinatorial procurement auction for Qos aware web swevices compositon[C]//Proceedings of the 3rd annual IEEE Confercence on automation science and engineering Scottsdale,2007:716-721.

[10] Dong yuanyuan,Ni Hong,Deng haojiang.Service selection strategy offering global optimal quality of service[J].Journal of Chinese Computer System,2011,32(3):455-459.

[11] Mohammad Alrifai,Dimitrios Skoutas,Thomas Risse.Selecting skyline services for QoS-based Web service composition[C]//Poceedings of International World Wide Web Conference.ACM,2010:11-20.

[12] 代鈺,楊雷,張斌.支持組合服務(wù)選取的QoS模型及優(yōu)化求解[J].計算機學(xué)報,2009,29(7):1167-1178.

[13] 劉華鵬,劉勝全.基于主體和QoS的語義Web服務(wù)組合方法[J].計算機工程,2013,39(10):227-231.

[14] 何炎祥,吳釗.動態(tài)Web服務(wù)組合關(guān)鍵技術(shù)與性能分析[M].清華大學(xué)出版社,2011:6-78.

[15] 武云鵬,包衛(wèi)東.服務(wù)組合系統(tǒng)研究綜述[J].計算機科學(xué),2011,38(9):1-4.

[16] 康國勝,劉建勛,唐明董.QoS全局最優(yōu)動態(tài)Web服務(wù)選擇算法[J].小型微型計算機系統(tǒng),2013(1):73-76.

[17] 楊溢龍,王偉茹.基于遺傳算法Web服務(wù)組合的一般過程[J].計算機數(shù)字與工程,2012,40(7):13-15.

RESEARCH ON QUALITY OF SERVICE-BASED DYNAMIC WEB SERVICE COMPOSITION METHOD

Wu Qinglin1Zhou Tianhong2

1(DepartmentofComputerScience,YunyangTeachers’College,Shiyan442000,Hubei,China)2(DepartmentofInformationEngineering,WuhanCommercialInstitute,Wuhan430056,Hubei,China)

AbstractFor the problems in Web service composition such as the fixed weight, inflexible choice and poor performance, etc., we put forward a quality of service-based variable weight dynamic Web service composition method (VW-DWSC-QoS) by the improved genetic algorithm. The VW-DWSC-QoS method uses the variable weight QoS parameters, introduces the penalty function strategy, and dynamic adjusts the variable weight factor, crossover and mutation factor, these makes it good in finding the Web service compositions meeting users need within a relatively short period. Theoretical analysis and simulation experiments all show the feasibility and effectiveness of this method, and compared with the traditional method, its optimal solution has better quality of service and fitness.

KeywordsDynamicWeb serviceQuality of serviceGenetic algorithmVariable weight

收稿日期：2015-01-03。湖北省教育廳重點科研項目(D201450 01)。吳青林，副教授，主研領(lǐng)域：Web服務(wù)，信息管理。周天宏，教授。

中圖分類號TP393

文獻標(biāo)識碼A

DOI:10.3969/j.issn.1000-386x.2016.05.006