基于圖的Web服務組合的研究*

王一飛，吳素芹，王 榕

(鹽城工學院 信息工程學院，江蘇 鹽城 224051)

近年來，基于XML的Web服務技術迅速發展，為互聯網應用提供了一種共享數據的有效手段。Web服務的高效執行方式，Web服務與其他成熟技術的有機結合以及Web服務的組合是解決現實應用問題的重要技術。

Web服務是一種自包含、自描述、模塊化的程序，它吸收了分布式計算、Grid計算和XML等各種技術的優點，解決了異構分布式計算以及代碼與數據重用等問題，具有高度的互操作性、跨平臺性和松耦合性，引起了世界范圍內學術界和工業界的極大興趣[1-2]。

為滿足Web服務的技術需求，W3C等國際標準組織制定了一系列Web服務規范，如統一描述發現集成UDDI(UniversalDescription，Discovery and Integration)、簡單對象訪問協議SOAP(Simple Object Access Protocol)、Web服務描述語言WSDL(Web Service Description Language)等，都是用于描述、發布、發現和調用Web服務的，這些規范共同構成了Web服務的技術體系[3]。

Web服務所執行的功能可以是從簡單的請求到復雜的商業過程中的任何事，然而單個Web服務的功能有限，難以滿足實際應用中的多種多樣的需求，因此，為了更加充分地利用共享的Web服務，有必要將共享的Web服務組合起來，提供功能更為強大的服務。Web服務組合是個非常復雜的問題[4-7]，它涉及到Web服務的描述、Web服務的發現[8]、Web服務的選擇[9]、Web服務的匹配、Web服務的調度[10-11]、服務質量(QoS)[12-13]等一系列問題。

1 基于圖的Web服務組合模型

組合服務是通過一系列數據流和控制流聯系在一起的基本服務，研究Web服務組合問題，也就是研究如何找到一組需要調用的Web服務，以及以何種方式進行調用這些Web服務。圖論中的點可以代表基本服務，邊可以代表Web服務的調用，再把 QoS屬性參數[12-13]也加入圖中，這樣就可以用1個帶有權值的有向圖來表示服務的組合問題，可以根據圖論中的算法和服務的屬性參數，在圖中尋找最優的服務組合方案。

把組合Web服務問題看成在1個帶有權值的有向圖G=(V，E)中尋找最優路徑的問題，其中V代表Web上服務的集合，E代表Web上兩個服務之間的連接的集合。另外定義n為圖中節點的數量，e代表圖中邊的數量，也就是 n=|V|，e=|E|。

每個Web服務被表示為圖中的一個節點(node)，Web服務的 QoS參數(如響應時間、費用、可靠性、可用性等)可表示為節點的權值。然而有關圖的算法通常把權值定義在邊上，而不是在節點上，所以本研究把原來在節點上屬性的權值(響應時間T，費用C，可靠性R，可用性A等)轉移到邊上。

基于圖的Web服務組合模型構造如下：

(1)圖中的每一個節點代表一個Web服務。

(2)在圖開始處加一個開始節點，在結束時加一個結束節點。

(3)同一列的節點代表是同一個服務社區的服務。

(4)圖中邊代表該邊的前驅節點所代表的Web服務可以調用該邊后繼節點所代表的Web服務。

(5)邊上的權值代表該邊后繼節點所代表的Web服務的QoS的綜合參數。

圖1是構造的Web服務組合模型圖，它有4個服務社區：第1個服務社區有4個候選服務，第2個服務社區有2個候選服務，第3個服務社區有4個候選服務，第四個服務社區有3個候選服務，邊上的值是邊后繼節點所代表服務的QoS的綜合參數。

圖1 基于圖的Web服務組合模型

圖1中符號的含義：

(1)Si：代表一個服務社區，它是一個自治的系統，包含著多個功能相同或相似但非功能(例如價格、響應時間等)不同的的單個Web服務。

(2)Sij：是一個基本 Web服務，它在Web服務社區Si中，其中j是社區為了標識Web服務的標記。

(3)S：起始節點，代表組合服務的開始。

(4)D：目標節點，代表組合服務的結束。

2 基于圖的Web服務組合算法

要從圖中找出S到D的路徑，并能夠同時滿足多種QoS約束的可行路徑。本文主要考慮多重(k≥2)路徑約束(也稱為多約束)的情況。由于多約束的QoS是NP完全問題，為此，研究人員設計了很多啟發式算法。然而這些算法往往具有很大的局限性：(1)計算復雜度過高，無法應用到實際環境中；(2)算法性能較差，不能找到實際存在的可行路徑；(3)算法只是針對某些特殊情況而設計，不具有普遍性。

本文則將多種QoS度量轉化為單一的權值，然后用幾種算法對整個圖進行計算最短路徑。使用加權公平隊列，費用、響應時間、可用性和可靠性都可以轉化為函數中的參數，不再彼此獨立。這樣，原來多約束的NP完全問題就可以簡化為多項式的復雜度。

在此介紹幾種算法求解滿足約束條件的方案。

(1)擴散法。該算法可以找出所有可能執行組合的路徑，其思想是從源點開始，通過逐個詢問圖中的其他節點，逐步逼近并達到目標節點。首先使用廣度優先的方法，在多條路徑中尋找可行路徑，在詢問抵達目標節點之前，不能斷定可行路徑。為了避免回路和擴散重復信息，節點需要記錄大量探測數據。

擴散算法在節點比較少的情況下可以用來尋找滿足約束條件的最優解決方案，但當節點較多時，它的時間復雜度會呈指數級上升，所以在大規模問題時不為人們所接受。

(2)Dijkstra算法。在經典的圖論問題中，可以使用Dijkstra算法計算圖中任意2個節點的最短路徑[4]。本研究把該算法的思想應用在服務組合過程中，求解從S到D的路徑，并且使服務質量函數最小。具體求解步驟如下：

①首先進行初始化，用d[v]表示從服務開始到調用到服務v的質量函數值，由于剛開始，所以除了服務開始節點s外，所有的節點 d[v]都設為無窮大，d[s]=0；p[v]表示調用服務v節點的服務節點，開始時都沒有調用，所以p[v]都設置為未定義。

②設置1個集合S，表示已經找到的符合要求的服務節點，一開始設置為空集合；設置1個集合Q，表示所有的服務節點，當算法找到1個符合要求的節點時，則把該節點從Q中刪除，加入到S集合中。

③當集合Q不空時，從集合中找出參數最小的服務節點 u，并且把它加到集合S中，對于每個u服務可以調用的服務，如果 d[v]大于 d[u]與 w[u，v]的總和，則把d[u]與 w[u，v]的總和賦值給 d[v]，同時把 p[v]設置為 u。

④回到步驟3，直到Q集合為空時，算法結束。

具體算法如圖2所示，在這個算法中，邊上的權值不能是負值，如果存在負值的話，在選取最小值時，就會出錯。

圖2 Dijkstra算法偽代碼

Dijkstra算法從圖中節點入手進行尋找最優解決方案，另外還可以從圖中的邊入手開始尋找。

(3)Bellman-Ford算法。是求解單源點的最短路徑問題的一種算法[4]。單源點的最短路徑問題是指：給定一個加權有向圖G和源點s，對于圖G中的任意一點v，求從s到v的最短路徑。

Bellman-Ford算法如圖3所示，它和Dijkstra算法很相似，但Dijkstra算法中的權值不能為負，因為如果有負值，則出現負循環時，就找不到最優路徑，Bellman-Ford算法比它多了檢查的步驟(行 10－12)，這樣如果權值為負值，會返回錯誤。Bellman-Ford算法可以在偽多項式時間內完成。

圖3 Bellman-Ford算法偽代碼

Web服務能夠較好地解決異構應用之間、松散耦合環境下的互操作、集成和協作問題，成為國內外軟件技術研究的重要方向。Web服務的組合是正在興起的新技術，它將徹底改變提供電子商務和客戶軟件應用的方式，是國內外在信息集成、軟件工程等領域的關注的焦點，也是Web服務技術的主要發展方向之一。

本文主要關注Web服務的組合，將QoS參數屬性作為圖的權值，提出了基于圖的Web服務組合建模，使用擴散算法、Dijkstra算法、Bellman-Ford等算法在模型中尋找組合的路徑，并將各個算法進行比較，為Web服務的組合做好了理論準備。

Web服務是處在動態的互聯網上，在過去幾年里Web上提供的Web服務數量急劇增多，通過人工在巨大的Web服務倉庫中發現人們需要的服務是不現實的，所以服務的自動發現是服務調度的前提，我們會繼續對服務的自動發現、服務的組合模型、服務的自動組合做進一步研究。

[1]岳昆，王曉玲，周傲英.Web服務核心支撐技術：研究綜述[J].軟件學報，2004，15(3)：428-442.

[2]李曼，王大治，杜小勇，等.基于領域本體的 Web服務動態組合[J].計算機學報，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.ComposingWebserviceson thesemanticWeb [J].The VLDB， 2003，12(4)：333-351.

[6]STEFAN T， RANIAK， THOMASM.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]張智，李瑞軒.基于對等網的 Web服務發布和發現機制研究 [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]谷清范，吳介一，張颯兵.網格調度機制研究綜述[J].計算機應用研究，2006，23(5)：1-4.

[11]官荷卿，張文博，魏俊，等.一種應用敏感的 Web服務請求調度策略[J].計算機學報，2006，29(7)：1189-1198.

[12]單志廣，林闖，肖人毅，等.Web QoS控制研究綜述[J].計算機學報，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.