吳青林　周天宏

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

?

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

吳青林1周天宏2

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

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

關鍵詞動態(tài)Web服務QoS遺傳算法變權

0引言

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

1相關工作

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

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

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

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

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

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

2QOS屬性及四種組合結構描述

(1) 原子服務QoS描述

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

(2) 服務組合描述

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

表1　組合服務QoS屬性計算方法

3服務預處理

3.1服務屬性的歸一化處理

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

(1)

(2)

3.2權重獲取

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

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

3.3變權處理

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

(3)

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

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

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

第一步染色體編碼

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

圖1染色體矩陣編碼

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

第二步初始化群體

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

第三步計算個體適應度

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

(4)

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

(5)

第四步選擇

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

第五步交叉和變異

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

(6)

(7)

第六步終止

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

5DWSC-GA算法分析

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

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

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

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

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

6仿真實驗

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

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

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

圖2　任務完成時間比較

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

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

圖3　任務交易成功率比較

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

7結語

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

參考文獻

[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服務組合研究[J].計算機應用與軟件,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] 代鈺,楊雷,張斌.支持組合服務選取的QoS模型及優(yōu)化求解[J].計算機學報,2009,29(7):1167-1178.

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

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

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

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

[17] 楊溢龍,王偉茹.基于遺傳算法Web服務組合的一般過程[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)。吳青林，副教授，主研領域：Web服務，信息管理。周天宏，教授。

中圖分類號TP393

文獻標識碼A

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