Web服務(wù)（Web Service）是基于XML和HTTPS的一種服務(wù)，其通信協(xié)議主要基于SOAP，服務(wù)的描述通過WSDL，通過UDDI來發(fā)現(xiàn)和獲得服務(wù)的元數(shù)據(jù)。

近年來，基于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 service平臺需要一套協(xié)議來實(shí)現(xiàn)分布式應(yīng)用程序的創(chuàng)建。任何平臺都有它的數(shù)據(jù)表示方法和類型系統(tǒng)。要實(shí)現(xiàn)互操作性，Web service平臺必須提供一套標(biāo)準(zhǔn)的類型系統(tǒng)，用于溝通不同平臺、編程語言和組件模型中的不同類型系統(tǒng)。在傳統(tǒng)的分布式系統(tǒng)中，基于界面(interface)的平臺提供了一些方法來描述界面、方法和參數(shù)（譯注：如COM和COBAR中的IDL語言）。同樣的，Web service平臺也必須提供一種標(biāo)準(zhǔn)來描述Web service，讓客戶可以得到足夠的信息來調(diào)用這個Web service。，我們還必須有一種方法來對這個Web service進(jìn)行遠(yuǎn)程調(diào)用。這種方法實(shí)際是一種遠(yuǎn)程過程調(diào)用協(xié)議(RPC)。為了達(dá)到互操作性，這種RPC協(xié)議還必須與平臺和編程語言無關(guān)。下面幾個小節(jié)就簡要介紹了組成Web service平臺的這三個技術(shù)。

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ù)組合模型

Web 服務(wù)是一種新的重要的應(yīng)用程序。Web 服務(wù)是一段可以用 XML 發(fā)現(xiàn)、描述和訪問的代碼。在這一領(lǐng)域有許多活動，但有三種主要的用于 Web 服務(wù)的 XML 標(biāo)準(zhǔn)：

SOAP：初是簡單對象訪問協(xié)議（Simple Object Access Protocol），SOAP 定義一個 XML 文檔格式，該格式描述如何調(diào)用一段遠(yuǎn)程代碼的方法。我的應(yīng)用程序創(chuàng)建一個描述我希望調(diào)用的方法的 XML 文檔，并傳遞給它所有必需的參數(shù)，然后應(yīng)用程序通過網(wǎng)絡(luò)將該 XML 文檔發(fā)送給那段代碼。代碼接收 XML 文檔、解釋它、調(diào)用我請求的方法，然后發(fā)回一個描述結(jié)果的 XML 文檔。SOAP 規(guī)范版本 1.1 位于 w3.org/TR/SOAP/。請?jiān)L問 w3.org/TR/ 以了解 W3C 中 SOAP 相關(guān)的所有活動。

WSDL：Web 服務(wù)描述語言（Web Services Description Language）是一個描述 Web 服務(wù)的 XML 詞匯表。編寫一段接收 WSDL 文檔然后調(diào)用其以前從未用過的 Web 服務(wù)的代碼，這是可能的。WSDL 文件中的信息定義 Web 服務(wù)的名稱、它的方法的名稱、這些方法的參數(shù)和其它詳細(xì)信息。您可以在 w3.org/TR/wsdl（結(jié)尾沒有斜杠符號）找到的 WSDL 規(guī)范。

UDDI：統(tǒng)一描述、發(fā)現(xiàn)和集成（Universal Description, Discovery, and Integration）協(xié)議向 Web 服務(wù)注冊中心定義 SOAP 接口。如果您有一段代碼希望作為 Web 服務(wù)部署，UDDI 規(guī)范定義如何將您的服務(wù)描述添加至注冊中心。如果您在尋找一段提供某種功能的代碼，UDDI 規(guī)范定義如何查詢注冊中心以找到您想要的信息。有關(guān) UDDI 的所有資料來源都可以在 uddi.org 找到。

組合服務(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ù)，在圖中尋找的服務(wù)組合方案。

把組合Web服務(wù)問題看成在1個帶有權(quán)值的有向圖G=(V，E)中尋找路徑的問題，其中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ù)。

構(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)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)比較少的情況下可以用來尋找滿足約束條件的解決方案，但當(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é)束。

具體算法，在這個算法中，邊上的權(quán)值不能是負(fù)值，如果存在負(fù)值的話，在選取值時，就會出錯。

Dijkstra算法從圖中節(jié)點(diǎn)入手進(jìn)行尋找解決方案，另外還可以從圖中的邊入手開始尋找。

(3)Bellman-Ford算法。是求解單源點(diǎn)的短路徑問題的一種算法。單源點(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)時，就找不到路徑，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)一步研究。