摘 要: 從Web服務(wù)質(zhì)量入手,,將QoS參數(shù)屬性作為圖的權(quán)重,,提出了基于圖的Web服務(wù)組合建模,并介紹了用不同的算法分別在模型上尋找解決方案,。
關(guān)鍵詞: Web服務(wù),;服務(wù)組合;服務(wù)選擇
近年來,,基于XML的Web服務(wù)技術(shù)迅速發(fā)展,,為互聯(lián)網(wǎng)應(yīng)用提供了一種共享數(shù)據(jù)的有效手段。Web服務(wù)的高效執(zhí)行方式,,Web服務(wù)與其他成熟技術(shù)的有機(jī)結(jié)合以及Web服務(wù)的組合是解決現(xiàn)實(shí)應(yīng)用問題的重要技術(shù),。
Web服務(wù)是一種自包含、自描述,、模塊化的程序,,它吸收了分布式計(jì)算、Grid計(jì)算和XML等各種技術(shù)的優(yōu)點(diǎn),,解決了異構(gòu)分布式計(jì)算以及代碼與數(shù)據(jù)重用等問題,,具有高度的互操作性、跨平臺性和松耦合性,,引起了世界范圍內(nèi)學(xué)術(shù)界和工業(yè)界的極大興趣[1-2],。
為滿足Web服務(wù)的技術(shù)需求,W3C等國際標(biāo)準(zhǔn)組織制定了一系列Web服務(wù)規(guī)范,,如統(tǒng)一描述發(fā)現(xiàn)集成UDDI(Universal Description,,Discovery and Integration)、簡單對象訪問協(xié)議SOAP(Simple Object Access Protocol),、Web服務(wù)描述語言WSDL(Web Service Description Language)等,,都是用于描述、發(fā)布,、發(fā)現(xiàn)和調(diào)用Web服務(wù)的,,這些規(guī)范共同構(gòu)成了Web服務(wù)的技術(shù)體系[3]。
Web服務(wù)所執(zhí)行的功能可以是從簡單的請求到復(fù)雜的商業(yè)過程中的任何事,然而單個Web服務(wù)的功能有限,,難以滿足實(shí)際應(yīng)用中的多種多樣的需求,,因此,為了更加充分地利用共享的Web服務(wù),,有必要將共享的Web服務(wù)組合起來,,提供功能更為強(qiáng)大的服務(wù)。Web服務(wù)組合是個非常復(fù)雜的問題[4-7],,它涉及到Web服務(wù)的描述,、Web服務(wù)的發(fā)現(xiàn)[8]、Web服務(wù)的選擇[9],、Web服務(wù)的匹配,、Web服務(wù)的調(diào)度[10-11]、服務(wù)質(zhì)量(QoS)[12-13]等一系列問題,。
1 基于圖的Web服務(wù)組合模型
組合服務(wù)是通過一系列數(shù)據(jù)流和控制流聯(lián)系在一起的基本服務(wù),,研究Web服務(wù)組合問題,也就是研究如何找到一組需要調(diào)用的Web服務(wù),,以及以何種方式進(jìn)行調(diào)用這些Web服務(wù),。圖論中的點(diǎn)可以代表基本服務(wù),邊可以代表Web服務(wù)的調(diào)用,,再把QoS屬性參數(shù)[12-13]也加入圖中,,這樣就可以用1個帶有權(quán)值的有向圖來表示服務(wù)的組合問題,可以根據(jù)圖論中的算法和服務(wù)的屬性參數(shù),,在圖中尋找最優(yōu)的服務(wù)組合方案,。
把組合Web服務(wù)問題看成在1個帶有權(quán)值的有向圖G=(V,E)中尋找最優(yōu)路徑的問題,,其中V代表Web上服務(wù)的集合,,E代表Web上兩個服務(wù)之間的連接的集合。另外定義n為圖中節(jié)點(diǎn)的數(shù)量,,e代表圖中邊的數(shù)量,,也就是n=|V|,e=|E|,。
每個Web服務(wù)被表示為圖中的一個節(jié)點(diǎn)(node),,Web服務(wù)的QoS參數(shù)(如響應(yīng)時間、費(fèi)用,、可靠性,、可用性等)可表示為節(jié)點(diǎn)的權(quán)值。然而有關(guān)圖的算法通常把權(quán)值定義在邊上,,而不是在節(jié)點(diǎn)上,,所以本研究把原來在節(jié)點(diǎn)上屬性的權(quán)值(響應(yīng)時間T,,費(fèi)用C,可靠性R,,可用性A等)轉(zhuǎn)移到邊上,。
基于圖的Web服務(wù)組合模型構(gòu)造如下:
(1)圖中的每一個節(jié)點(diǎn)代表一個Web服務(wù),。
(2)在圖開始處加一個開始節(jié)點(diǎn),,在結(jié)束時加一個結(jié)束節(jié)點(diǎn)。
(3)同一列的節(jié)點(diǎn)代表是同一個服務(wù)社區(qū)的服務(wù),。
(4)圖中邊代表該邊的前驅(qū)節(jié)點(diǎn)所代表的Web服務(wù)可以調(diào)用該邊后繼節(jié)點(diǎn)所代表的Web服務(wù),。
(5)邊上的權(quán)值代表該邊后繼節(jié)點(diǎn)所代表的Web服務(wù)的QoS的綜合參數(shù)。
圖1是構(gòu)造的Web服務(wù)組合模型圖,,它有4個服務(wù)社區(qū):第1個服務(wù)社區(qū)有4個候選服務(wù),,第2個服務(wù)社區(qū)有2個候選服務(wù),第3個服務(wù)社區(qū)有4個候選服務(wù),,第四個服務(wù)社區(qū)有3個候選服務(wù),,邊上的值是邊后繼節(jié)點(diǎn)所代表服務(wù)的QoS的綜合參數(shù)。
圖1中符號的含義:
(1)Si:代表一個服務(wù)社區(qū),,它是一個自治的系統(tǒng),,包含著多個功能相同或相似但非功能(例如價格、響應(yīng)時間等)不同的的單個Web服務(wù),。
(2)Sij:是一個基本W(wǎng)eb服務(wù),,它在Web服務(wù)社區(qū)Si中,其中j是社區(qū)為了標(biāo)識Web服務(wù)的標(biāo)記,。
(3)S:起始節(jié)點(diǎn),,代表組合服務(wù)的開始。
(4)D:目標(biāo)節(jié)點(diǎn),,代表組合服務(wù)的結(jié)束,。
2 基于圖的Web服務(wù)組合算法
要從圖中找出S到D的路徑,并能夠同時滿足多種QoS約束的可行路徑,。本文主要考慮多重(k≥2)路徑約束(也稱為多約束)的情況,。由于多約束的QoS是NP完全問題,為此,,研究人員設(shè)計(jì)了很多啟發(fā)式算法,。然而這些算法往往具有很大的局限性:(1)計(jì)算復(fù)雜度過高,無法應(yīng)用到實(shí)際環(huán)境中,;(2)算法性能較差,,不能找到實(shí)際存在的可行路徑;(3)算法只是針對某些特殊情況而設(shè)計(jì),,不具有普遍性,。
本文則將多種QoS度量轉(zhuǎn)化為單一的權(quán)值,然后用幾種算法對整個圖進(jìn)行計(jì)算最短路徑。使用加權(quán)公平隊(duì)列,,費(fèi)用,、響應(yīng)時間、可用性和可靠性都可以轉(zhuǎn)化為函數(shù)中的參數(shù),,不再彼此獨(dú)立,。這樣,原來多約束的NP完全問題就可以簡化為多項(xiàng)式的復(fù)雜度,。
在此介紹幾種算法求解滿足約束條件的方案,。
(1)擴(kuò)散法。該算法可以找出所有可能執(zhí)行組合的路徑,,其思想是從源點(diǎn)開始,,通過逐個詢問圖中的其他節(jié)點(diǎn),逐步逼近并達(dá)到目標(biāo)節(jié)點(diǎn),。首先使用廣度優(yōu)先的方法,,在多條路徑中尋找可行路徑,在詢問抵達(dá)目標(biāo)節(jié)點(diǎn)之前,,不能斷定可行路徑,。為了避免回路和擴(kuò)散重復(fù)信息,節(jié)點(diǎn)需要記錄大量探測數(shù)據(jù),。
擴(kuò)散算法在節(jié)點(diǎn)比較少的情況下可以用來尋找滿足約束條件的最優(yōu)解決方案,,但當(dāng)節(jié)點(diǎn)較多時,它的時間復(fù)雜度會呈指數(shù)級上升,,所以在大規(guī)模問題時不為人們所接受,。
(2)Dijkstra算法。在經(jīng)典的圖論問題中,,可以使用Dijkstra算法計(jì)算圖中任意2個節(jié)點(diǎn)的最短路徑[4],。本研究把該算法的思想應(yīng)用在服務(wù)組合過程中,求解從S到D的路徑,,并且使服務(wù)質(zhì)量函數(shù)最小,。具體求解步驟如下:
①首先進(jìn)行初始化,用d[v]表示從服務(wù)開始到調(diào)用到服務(wù)v的質(zhì)量函數(shù)值,,由于剛開始,,所以除了服務(wù)開始節(jié)點(diǎn)s外,所有的節(jié)點(diǎn)d[v]都設(shè)為無窮大,,d[s]=0,;p[v]表示調(diào)用服務(wù)v節(jié)點(diǎn)的服務(wù)節(jié)點(diǎn),開始時都沒有調(diào)用,,所以p[v]都設(shè)置為未定義,。
②設(shè)置1個集合S,,表示已經(jīng)找到的符合要求的服務(wù)節(jié)點(diǎn),一開始設(shè)置為空集合,;設(shè)置1個集合Q,,表示所有的服務(wù)節(jié)點(diǎn),當(dāng)算法找到1個符合要求的節(jié)點(diǎn)時,,則把該節(jié)點(diǎn)從Q中刪除,,加入到S集合中。
③當(dāng)集合Q不空時,,從集合中找出參數(shù)最小的服務(wù)節(jié)點(diǎn)u,,并且把它加到集合S中,,對于每個u服務(wù)可以調(diào)用的服務(wù),,如果d[v]大于d[u]與w[u,v]的總和,,則把d[u]與w[u,,v]的總和賦值給d[v],同時把p[v]設(shè)置為u,。
④回到步驟3,,直到Q集合為空時,算法結(jié)束,。
具體算法如圖2所示,,在這個算法中,邊上的權(quán)值不能是負(fù)值,,如果存在負(fù)值的話,,在選取最小值時,就會出錯,。
Dijkstra算法從圖中節(jié)點(diǎn)入手進(jìn)行尋找最優(yōu)解決方案,,另外還可以從圖中的邊入手開始尋找。
(3)Bellman-Ford算法,。是求解單源點(diǎn)的最短路徑問題的一種算法[4],。單源點(diǎn)的最短路徑問題是指:給定一個加權(quán)有向圖G和源點(diǎn)s,對于圖G中的任意一點(diǎn)v,,求從s到v的最短路徑,。
Bellman-Ford算法如圖3所示,它和Dijkstra算法很相似,,但Dijkstra算法中的權(quán)值不能為負(fù),,因?yàn)槿绻胸?fù)值,則出現(xiàn)負(fù)循環(huán)時,,就找不到最優(yōu)路徑,,Bellman-Ford算法比它多了檢查的步驟(行10-12),,這樣如果權(quán)值為負(fù)值,會返回錯誤,。Bellman-Ford算法可以在偽多項(xiàng)式時間內(nèi)完成,。
Web服務(wù)能夠較好地解決異構(gòu)應(yīng)用之間、松散耦合環(huán)境下的互操作,、集成和協(xié)作問題,,成為國內(nèi)外軟件技術(shù)研究的重要方向。Web服務(wù)的組合是正在興起的新技術(shù),,它將徹底改變提供電子商務(wù)和客戶軟件應(yīng)用的方式,,是國內(nèi)外在信息集成、軟件工程等領(lǐng)域的關(guān)注的焦點(diǎn),,也是Web服務(wù)技術(shù)的主要發(fā)展方向之一,。
本文主要關(guān)注Web服務(wù)的組合,將QoS參數(shù)屬性作為圖的權(quán)值,,提出了基于圖的Web服務(wù)組合建模,,使用擴(kuò)散算法、Dijkstra算法,、Bellman-Ford等算法在模型中尋找組合的路徑,,并將各個算法進(jìn)行比較,為Web服務(wù)的組合做好了理論準(zhǔn)備,。
Web服務(wù)是處在動態(tài)的互聯(lián)網(wǎng)上,,在過去幾年里Web上提供的Web服務(wù)數(shù)量急劇增多,通過人工在巨大的Web服務(wù)倉庫中發(fā)現(xiàn)人們需要的服務(wù)是不現(xiàn)實(shí)的,,所以服務(wù)的自動發(fā)現(xiàn)是服務(wù)調(diào)度的前提,,我們會繼續(xù)對服務(wù)的自動發(fā)現(xiàn)、服務(wù)的組合模型,、服務(wù)的自動組合做進(jìn)一步研究,。
參考文獻(xiàn)
[1] 岳昆,王曉玲,,周傲英.Web服務(wù)核心支撐技術(shù):研究綜述[J].軟件學(xué)報,,2004,15(3):428-442.
[2] 李曼,,王大治,,杜小勇,等.基于領(lǐng)域本體的Web服務(wù)動態(tài)組合[J].計(jì)算機(jī)學(xué)報,,2005,,28(4):644-650.
[3] DAVIES N J, FENSEL D,, RICHARDSON M. The future of Web services[J]. BT Technology Journal,, 2004,,22(1):118-130.
[4] MILANOVIC N, MIROSLAW M. Current solutions for Web service composition[J]. IEEE Internet Computing,, 2004,,26(5):51-59.
[5] MEDHAHED B, BOUGUETTAYA A,, ELMAGARMID A K. Composing Web services on the semantic Web[J]. The VLDB,, 2003,12(4):333-351.
[6] STEFAN T,, RANIA K,, THOMAS M. Composition of coordinated Web services[C]. IFIP International Federation for Information Processing, 2004:294-310.
[7] BOUALEM B,, MARLON D,, QUAN Z. Declarative composition and peer-to-peer provisioning of dynamic Web services[C].In the Proceedings of the 18th International Conference on Data Engineering, 2002.
[8] 張智,,李瑞軒.基于對等網(wǎng)的Web服務(wù)發(fā)布和發(fā)現(xiàn)機(jī)制研究[J].計(jì)算機(jī)工程與設(shè)計(jì),,2006,,27(16):2949-2951.
[9] MASSIMO M,, ALESSANDRA M, ALESSANDRO P. Declarative policies for Web service selection[C]. In the Proceedings of the Sixth IEEE International Workshop on Policies for Distributed Systems and Networks,, 2005.
[10] 谷清范,,吳介一,張颯兵.網(wǎng)格調(diào)度機(jī)制研究綜述[J].計(jì)算機(jī)應(yīng)用研究,,2006,,23(5):1-4.
[11] 官荷卿,張文博,,魏俊,,等.一種應(yīng)用敏感的Web服務(wù)請求調(diào)度策略[J].計(jì)算機(jī)學(xué)報,2006,,29(7):1189-1198.
[12] 單志廣,,林闖,肖人毅,,等.Web QoS控制研究綜述[J].計(jì)算機(jī)學(xué)報,,2003,27(2):145-156.
[13] ZENG Lang Zhao,,BENATALLAH B,,DUMAS M. Quality driven Web services composition[J]. IEEE Transaction on Software Engineering, 2004,,30(5):311-327.