基于功能劃分圖的Web服務組合規(guī)劃和最優(yōu)選擇

吳　芳　朱尚明

(華東理工大學計算機科學與工程系　上海 200237)

?

基于功能劃分圖的Web服務組合規(guī)劃和最優(yōu)選擇

吳芳朱尚明*

(華東理工大學計算機科學與工程系上海 200237)

擴展Web服務類型的組合方式、實現(xiàn)服務的無縫組合和提高服務組合的可靠性是當今Web服務組合的研究熱點。針對Web服務類型組合方式多樣性和無縫服務組合問題，根據(jù)請求服務的功能劃分圖來計算可用于服務組合的候選服務類型，動態(tài)規(guī)劃各種服務類型的組合方式，并提出第一級服務類型的裝配算法。針對服務組合的可靠性問題，將Web服務自身對運行環(huán)境的要求和自身的優(yōu)先條件表示為上下文，并提出相應的局部最優(yōu)選擇算法和全局最優(yōu)選擇算法，以找到真實的、具有高可靠性的服務組合。最后，通過仿真實驗驗證了第一級服務類型裝配算法、局部最優(yōu)和全局最優(yōu)選擇算法的性能。

Web服務組合功能劃分圖第一級服務裝配算法局部最優(yōu)選擇算法全局最優(yōu)選擇算法

0　引　言

隨著互聯(lián)網(wǎng)以及云計算技術的發(fā)展，越來越多的Web服務出現(xiàn)在互聯(lián)網(wǎng)以及云計算平臺上。Web服務是可以跨越整個Web被發(fā)布、定位以及調(diào)用的自包含、自描述的模塊化應用。如何有效地組合分布于Internet中的各類Web服務，實現(xiàn)服務之間的無縫集成，形成功能豐富的企業(yè)級服務流程，已經(jīng)成為Web服務發(fā)展過程中的一個重要步驟。Web服務組合的研究正是在這種背景下被提出來，并吸引了學術界和工業(yè)界的廣泛關注。Web服務組合作為一種應用模式，可以在保證Web服務的質量和服務獨立性以及滿足用戶約束的前提下，發(fā)現(xiàn)一組服務并將其組合成一個新的、功能更加復雜的服務[1]。

Web服務組合是針對Web服務進行資源管理與整合的重要技術和手段。然而，隨著Web服務的迅速增長，通過逐一匹配請求服務的單個抽象功能來進行服務組合的方式對Web服務的利用率變得越來越低?；ヂ?lián)網(wǎng)環(huán)境千差萬別，不同的Web服務正常運行的環(huán)境也不一樣，在服務選擇階段，僅僅通過運行成功率這一統(tǒng)計性標量已不足以選擇到真實環(huán)境下高可靠性的服務。實現(xiàn)Web服務的無縫組合和提高服務的可靠性、擴展性已成為當今Web服務組合研究領域的熱點問題[2,3]。

本文在Web服務組合方式規(guī)劃上將針對組合方式的多樣性和無縫性問題，提出一種基于請求服務功能劃分圖的動態(tài)Web服務組合方法。在組合服務的選擇上將針對服務的可靠性問題，提出帶約束上下文的局部最優(yōu)選擇算法和全局最優(yōu)選擇算法。目前云平臺上的Web服務既有獨立的集成軟件，也有適用于工業(yè)流程的組件，本文提出的算法對這兩類應用場景都適用。

1　相關工作

目前對Web服務組合技術的研究可以分為兩類：基于工作流的服務組合和基于人工智能規(guī)劃的服務組合[4]。例如，文獻[5-9]介紹了基于工作流圖的動態(tài)服務組合和選擇算法，其思想是根據(jù)流程圖逐步選擇最優(yōu)的服務，將最優(yōu)服務組合和選擇問題轉換為求最優(yōu)路徑問題。文獻[1]介紹了基于人工智能的服務組合優(yōu)化方法，通過統(tǒng)計特征來把握候選服務的全局特性，使用遺傳算法求出最優(yōu)解。隨著互聯(lián)網(wǎng)以及云計算技術的發(fā)展，越來越多的Web 服務出現(xiàn)在互聯(lián)網(wǎng)上，只逐個匹配請求服務的各個抽象功能來確定候選服務，并從中選擇和組合出Web服務已經(jīng)不能滿足當前的需要了。為擴展Web服務組合的方式，很多學者都把目標放在擴大候選服務類型集上，文獻[2]提出了服務內(nèi)擴展和服務外擴展方法，文獻[10]采用聚類技術和結構化服務發(fā)現(xiàn)相結合的方法來為Web服務歸類，文獻[11]采用計算流程相似度來查找所需候選服務。服務類型集的擴大必然引起組合方式的多樣性，在最優(yōu)服務組合選取上，文獻[3]采用嵌套組合的方法，文獻[12]則提出了基于相似度的模糊預測的方法，文獻[13]和文獻[14]也各提出一種模型來力求最大限度找到能組合出滿足用戶需求的候選服務并將它們裝配起來。但是，這些方法都不能完整表現(xiàn)出服務間的關系。因此，對于包含多個請求服務的抽象功能的候選服務，其服務組合方式也就不確定，從而產(chǎn)生了無縫組合問題。Web服務的無縫組合就是如何完整和正確地將候選服務裝配成滿足請求服務要求的服務組合。

Web服務千差萬別，其對運行環(huán)境的要求也各有不同，Web服務組合面臨多樣性的問題。文獻[2]提出了服務約束-感知機制來確保Web服務在正確的環(huán)境中運行，但是文獻[2]在初始化及預包裝上沒有提出相應的算法，而且深度優(yōu)先的圖算法的復雜度很高。文獻[15]提出了用上下文來表述服務特殊要求的方法，其思想是后退一步來查驗當前選擇的服務是否是最優(yōu)的，是則繼續(xù)到下一步，否則在退后一步的前提下選擇最優(yōu)。然而這個算法只適用于功能呈順序關系，不能滿足請求服務的功能間呈非順序關系的情況。

本文提出的Web服務組合和選擇方法分為兩個階段：(1)基于請求服務的功能劃分圖來計算出所有可用于服務組合的候選服務類型，同時通過精確匹配來確定出各個類型的候選服務集，并規(guī)劃出各種服務類型組合方式；(2)查找各個組合方式下的最優(yōu)服務組合，比較產(chǎn)生最優(yōu)的服務組合?？紤]到各個Web服務會受環(huán)境的影響，本文采用上下文結構來表述每個具體Web服務或服務組合自身對運行環(huán)境的要求和自身具有的優(yōu)先條件，并提出基于這種上下文的局部最優(yōu)選擇算法和全局最優(yōu)選擇算法來找出高可執(zhí)行性的最優(yōu)服務組合。

2　Web服務組合方式規(guī)劃

目前，在Web服務的識別上有基于輸入和輸出參數(shù)的[4]，還有基于功能語義描述的[2]，本文采用解析請求服務的輸入和輸出參數(shù)來確定單個服務的類別。對于用戶的請求服務，如何抽象出其包含的各個功能和它們之間的關系，以及每個功能對應的參數(shù)，目前已有很多研究。本文將在確定出請求服務的各個抽象功能、各個抽象功能的輸入和輸出參數(shù)以及請求服務的功能劃分圖的基礎上，進行Web服務組合的研究。

服務不僅具有功能特性，還有輸入、輸出參數(shù)的差別[9]。本文采用分級思想，對于在功能及相應功能的輸入、輸出參數(shù)上都完全或部分符合請求的服務采用第一級服務組合；對于在功能上滿足請求服務的某個功能，但是在輸入、輸出參數(shù)上卻不滿足相應要求的服務采用第二級服務組合。本文重點研究第一級服務組合。

2.1基本概念

為便于理解Web服務的組合方式，首先介紹本文定義的幾個基本概念。

定義1請求服務的功能關系：指請求服務的各個功能間的行為關系和數(shù)據(jù)關系。

一般，功能間的行為關系分為順序關系和并行關系兩種，且呈順序關系的兩個功能才可能有數(shù)據(jù)關系。本文通過匹配輸入?yún)?shù)和輸出參數(shù)來抽象各個功能，而各個參數(shù)又反映了功能間的數(shù)據(jù)關系。因此，也可以通過匹配輸入和輸出參數(shù)來確定出整個功能間的關系。

定義2請求服務的功能劃分圖：指反映請求服務的各個抽象功能及各個抽象功能間關系的圖，圖有兩個虛擬節(jié)點表示開始與結束，其他節(jié)點表示請求服務的抽象功能，抽象功能節(jié)點間的邊表示抽象功能間的功能關系。

定義3第一級服務：指一個Web服務能滿足一個或多個Web請求服務的抽象功能，這些抽象功能間的關系必須與請求服務的功能關系一致。同時其輸入?yún)?shù)和輸出參數(shù)也滿足請求服務在這些功能上的參數(shù)約束。

定義4第二級服務：指一個Web服務能滿足某一個請求服務的抽象功能，但其輸入?yún)?shù)和輸出參數(shù)無法滿足請求服務在這個功能上的參數(shù)約束。第二級服務只涉及一個請求服務的抽象功能，所以沒有功能關系的限制。

匹配技術、分類技術和裝配技術是形成Web服務組合的三項關鍵技術[16]。匹配Web服務的過程也是搜索候選Web服務的過程，為了匹配出上述所提到的第一級服務，可以在匹配Web服務的過程中，將Web服務分為完全匹配服務、部分匹配服務、約束不匹配服務和完全不匹配服務。

定義5完全匹配服務：指一個服務的輸入?yún)?shù)類型滿足請求服務的所有輸入?yún)?shù)類型，且服務的輸出參數(shù)類型也滿足請求服務的所有輸出參數(shù)類型。同時，這個服務的輸入?yún)?shù)和輸出參數(shù)在取值上滿足請求服務的約束。

定義6部分匹配服務：指一個服務的輸入?yún)?shù)和輸出參數(shù)在類型上分別部分匹配請求服務的輸入?yún)?shù)和輸出參數(shù)，且這些匹配的輸入?yún)?shù)與輸出參數(shù)在取值上也與請求服務的相應參數(shù)一致。

定義7約束不匹配服務：指一個服務的輸入?yún)?shù)類型和輸出參數(shù)類型都完全或部分出現(xiàn)在請求服務的輸入?yún)?shù)和輸出參數(shù)中，但是它們不都滿足其對應的參數(shù)約束。

定義8完全不匹配服務：指不滿足上述三類中任意一類的服務。

完全匹配服務和部分匹配服務歸為第一級服務，用于后續(xù)的服務組合和選擇技術，至于完全不匹配服務則直接舍棄。

2.2服務組合規(guī)劃

規(guī)劃服務組合分為3個階段：

? 構造請求服務的功能劃分圖；

? 匹配、分類第一級服務，產(chǎn)生第一級服務類型；

? 裝配第一級服務類型，產(chǎn)生抽象服務類型組合。

1) 構造功能劃分圖

將整個請求服務中的各個功能看作一個節(jié)點，先設定兩個虛擬節(jié)點，即開始節(jié)點和終結節(jié)點，之后將這些節(jié)點初始化為一個有向圖，這里稱其為請求服務的功能劃分圖。

定義深度為功能劃分圖的最大路徑長度，寬度為功能劃分圖中所有功能節(jié)點的最大直接后繼服務節(jié)點數(shù)量。功能劃分圖的構造方法如下：

(1) 功能節(jié)點依照功能間的行為關系進行連接，若兩個功能之間的行為關系是并行或不相鄰的先后關系，則它們不需要連接；若它們的行為關系為順序且相鄰，則依照它們的先后順序用有向邊連接。

(2) 開始節(jié)點用有向邊指向所有無前驅的節(jié)點，所有無后繼節(jié)點指向終結節(jié)點。

2) 匹配、分類第一級服務

這一階段的目的是搜索符合要求的第一級服務并將它們分類，由此產(chǎn)生各個第一級服務類型。為便于理解，對第一級服務類型作如下定義：

定義9第一級服務類型：第一級服務經(jīng)第一級組合的分類階段產(chǎn)生的抽象服務類型。

根據(jù)初始化后的功能劃分圖，標記圖中的各分支和各抽象服務相對于各個分支所在的位置，并確定各分支間的隸屬關系。之后，通過將各個服務與這個有向圖對比來對服務進行分類。

已知第一級服務都能部分產(chǎn)生目標輸出，且它們對應的節(jié)點之間有關聯(lián)表示后者節(jié)點的輸入依賴前者節(jié)點的輸出，可得出以下推論：

推論1對于一個抽象服務功能，當其輸入不能完全由一個第三方提供的服務決定時，則這個第三方提供的服務一定不包括這個抽象服務功能。

推論2一個無輸入依賴的抽象服務功能，其前驅節(jié)點一定是開始節(jié)點。

推論3一個第三方提供的服務如果包含兩個或多個在不同分支但它們的分支卻隸屬于同一分支A的抽象服務功能，記這兩個或多個抽象服務功能所在的分支為B類分支，則這個第三方提供的服務必然包含分支A上的服務功能及其在B類分支上的直接后繼抽象服務功能。

推論4一個第三方提供的服務所涉及到的抽象服務功能中，如果有其所在分支隸屬于同一個分支的，則它們在請求服務功能劃分圖中的位置必是連續(xù)的。

將請求服務的功能劃分圖的開始節(jié)點留下，終結節(jié)點刪去。根據(jù)上述4個推論可知，每個第一級服務類型對應到請求服務功能劃分圖中就是一個樹，因此，每個第一級服務類型都可以由一個樹結構來表示。

3) 第一級服務類型裝配算法

第一級服務類型對應的裝配算法簡稱第一級裝配算法。其具體過程分為兩階段：分層階段和裝配階段。

已知第一級服務類型的表示是一個樹結構，本文根據(jù)各個第一級服務類型表示樹的根節(jié)點來分層，即第一級服務類型所屬的層數(shù)就是其表示樹的根節(jié)點在請求服務功能劃分圖中的層數(shù)。

計算請求服務功能劃分圖中，求各個抽象服務節(jié)點的層數(shù)的方法如下：先求出請求服務功能劃分圖中從開始節(jié)點到終結節(jié)點的所有路徑；接著，計算各個路徑上的抽象服務在這個路徑上的位置，設定開始節(jié)點的位置為0，其直接后繼節(jié)點的位置為1，就這樣依次加1得到各個路徑上的各個抽象服務的位置；最后，對于每個抽象服務，取在經(jīng)過自己的所有路徑上的最大位置數(shù)作為自己的層數(shù)。

裝配階段就是依次對第0層的各個服務類型進行裝配來得到它們的所有服務類型組合方式，進而得到請求服務所對應的所有服務類型組合方式，具體算法流程見圖1所示。

圖1　第一級裝配算法流程圖

(1) 初始化隊列Queue：設Queue為一個先進先出隊列，將屬于0層的所有Web服務類型都封裝為Web服務類型組合并依次放入Queue中。

(2) 裝配一個缺少的服務類型：按層次數(shù)從小到大來找到服務類型組合A所需的第一個服務類型，并將這個服務類型裝配到A上。

毛澤東作為一位出色的政治家詩人，其詩詞作品始終洋溢著樂觀的革命精神，飽含著深厚的人民情懷，蘊藏著巨大的精神力量。在他的眾多詩詞作品中，《菩薩蠻·大柏地》一詞尤其引起筆者關注。一是因為這首詞在一定的程度上反映了毛澤東領導工農(nóng)紅軍開辟、創(chuàng)建和鞏固中央紅色政權的歷史過程；二是因為筆者好奇，是什么樣的力量能讓毛澤東在逆境中始終昂揚著樂觀豪邁的革命精神，從而抒寫出恢弘大氣的壯麗詩篇？古人云：詩言志。意謂詩詞的創(chuàng)作是詩人理想抱負、感情意志的自然流露，最能反映詩人的內(nèi)心世界。下面，筆者試著聯(lián)系這首詞背后的歷史細節(jié)來探究毛澤東的革命情懷。

3　最優(yōu)Web服務組合選擇算法

Web服務組合選擇階段則是根據(jù)請求服務的服務質量、客戶偏好等非功能屬性，選擇出最優(yōu)的、真實的服務組合。文獻[17] 提出了服務質量標準和相應的計算公式，探討了對于確定的Web服務類型組合方式，求其最優(yōu)服務組合解的方法。本文將Web服務組合的非功能屬性分為完全依賴屬性和部分依賴屬性，用多領域決策來產(chǎn)生集成函數(shù)，通過集成函數(shù)的權值來表現(xiàn)請求服務的非功能性屬性。最優(yōu)Web服務組合選擇算法就是選擇出分數(shù)最高的服務組合的算法。

定義10完全依賴屬性：由Web服務組合中的所有Web服務計算得到的屬性，即服務組合在此屬性上的值是所有Web服務在此屬性上的值運算得到的。

定義11部分依賴屬性：由Web服務組合中的部分Web服務計算得到的屬性，即服務組合在此屬性上的值是通過某種規(guī)則選出部分Web服務，由它們在這個屬性上的值經(jīng)過運算得到的。

從定義10和定義11可知，例如花費就是完全依賴屬性，消耗的時間就為部分依賴屬性。本文采用整數(shù)規(guī)劃的思想，將所有非功能性屬性的計算公式都轉化為和的形式。這樣，整個服務組合的分數(shù)就是整個服務組合在各個非功能屬性項上的值乘以相應的權值之后將這些項進行累加。當Web服務或Web服務組合在這些屬性上的值是相互獨立時，對于完全依賴屬性，其在整個Web服務組合上的值為這個Web服務組合所包含的所有Web服務在這個屬性上的值的和；對于部分依賴屬性，求解其在整個Web服務組合上的值實質上是一個關鍵路徑問題，只不過具體問題依屬性而不同。

由定義10、定義11知，完全依賴屬性和部分依賴屬性是沒有邏輯聯(lián)系的，而在部分依賴屬性上選擇出最優(yōu)服務須得形成所有服務組合，這樣問題就轉換成圖的最優(yōu)路徑選擇問題。由文獻[5]知，這是一個NP-hard問題，因此本文采取只根據(jù)完全依賴屬性選擇最優(yōu)服務組合，在計算分數(shù)時會考慮整體的屬性分數(shù)。

對于完全依賴屬性，求解其在整個Web服務組合上的最優(yōu)解問題實際上是個貪心問題，用貪心算法得到的最優(yōu)完全依賴屬性解在現(xiàn)實環(huán)境中并不保證一定能運行。另外，不是所有Web服務或服務組合在這些屬性上的取值都是獨立的，Web服務或服務組合間可能有優(yōu)先條件，所以本文采用上下文來表示W(wǎng)eb服務或服務組合在這些屬性上的關聯(lián)和它們自身對運行環(huán)境的要求。在3.1節(jié)和3.2節(jié)將介紹結合上下文來求解最優(yōu)完全依賴屬性服務組合的局部最優(yōu)算法和全局最優(yōu)算法。

3.1帶約束上下文的局部最優(yōu)選擇算法

一般來說，一個Web服務的自身運行限制是與其前驅服務相關的，而其與其相鄰服務的優(yōu)先條件也可以表示為受其前驅服務的限制。因此，每個Web服務的約束上下文都可以表示為對其后繼服務有限制。

帶約束上下文的局部最優(yōu)算法的實質就是逐層地找出滿足上一層選出服務的約束條件的本層最優(yōu)服務組合?？紤]到會有沒有后繼服務的服務被選中而造成“無解”的情況，這里引入失敗回退機制，具體算法過程如下：

2) 選擇出滿足前驅層的當前層最優(yōu)服務組合，如果沒有，則更新服務狀態(tài)并回退至前驅層；如果存在則進入第3)步。

3) 判斷當前層是否為最后一層，是則退出算法；否則設下一層為當前層，接著執(zhí)行第2)步。

3.2帶約束上下文的全局最優(yōu)選擇算法

帶約束上下文的全局最優(yōu)算法結合了動態(tài)規(guī)劃思想和上述的局部最優(yōu)算法，因此也帶有失敗回退的機制，具體算法過程如下：

1) 初始化：與局部最優(yōu)算法的初始化過程一樣。

2) 計算當前層的局部最優(yōu)解。

3) 將上步得出的結果與第0層到當前層的前驅層篩選出的全局最優(yōu)服務作對比，若完全一樣則進入第4)步，否則進入第5)步。

4) 篩選出只在當前層上，比第2)步選出的當前層服務組合更優(yōu)秀的服務組合，并依次找出包含這些服務組合的從0層到當前層的最優(yōu)子結構；之后通過對比這些解找出0層到當前層的最優(yōu)子結構，接著進入第6)步。

5) 找到開始出現(xiàn)變化的層數(shù)，更新服務狀態(tài)，設開始出現(xiàn)變化的層為當前層，進入第2)步。

6) 判斷當前層是否為最后一層，是則退出算法；否則記下一層為當前層，重新進入第2)步。

4　實驗及性能分析

4.1實驗環(huán)境

為驗證上述算法的性能，本文進行了仿真實驗。仿真實驗采用的開發(fā)環(huán)境如下：操作系統(tǒng)為Windows7 32位操作系統(tǒng)，算法開發(fā)語言為C++，采用Microsoft Visual C++6.0為開發(fā)工具。用鏈表結構存儲請求服務功能劃分圖，用樹結構表示第一級服務類別，并為每個服務類別添加一個唯一的標識符。建立Composition類來模擬符合請求服務的單個服務組合，在Composition類中使用一個vector容器類型的成員變量來存儲組成這個服務組合的所有服務類型的標識。

對第一級裝配算法，分別采用單線程和多線程兩種計算方式，以功能劃分圖的深度和寬度作為標量，以功能數(shù)、服務類型數(shù)、組合方式數(shù)、裝配時間等作為服務類型裝配算法的性能指標，進行了仿真試驗。對選擇算法，以最優(yōu)服務組合的分數(shù)和花費時間作為服務組合選擇算法的性能指標，進行了仿真實驗。

4.2第一級服務類型裝配算法性能分析

為驗證第一級裝配技術受請求服務功能劃分圖的影響，深度和寬度是反映請求服務功能劃分圖的復雜度的兩個重要標量。表1給出了寬度為2時功能數(shù)、第一級服務類型數(shù)、組合方式數(shù)、裝配時間等指標隨深度的變化情況。從表1中可以看出，當深度從1增加到3時，第一級服務類型數(shù)量的變化比第一級服務類型組合方式數(shù)量的變化明顯要大，采用多線程計算方式比單線程計算方式耗費的時間明顯要少。

表1　深度對性能指標的影響(寬度為2)

表2給出了深度為2時功能數(shù)、第一級服務類型數(shù)、組合方式數(shù)、裝配時間等指標隨寬度的變化情況。從表2中可以看出，當寬度從1增加到3時，第一級服務類型數(shù)量的變化比第一級服務類型組合方式的數(shù)量變化要小，采用多線程計算方式比單線程計算方式耗費的時間要少，但差值不大。

表2　寬度對性能指標的的影響(深度為2)

對比表1和表2可以得出，服務類型數(shù)量更易受寬度的影響，而服務類型組合方式數(shù)量更易受深度的影響。另外，多線程計算方式更適合裝配深度較大的請求服務。

圖2是深度為1，寬度從1到10變化時，分別用單線程和多線程計算方式所得的處理時間對比圖。從圖2中可以看出，寬度達到一定值時，用多線程產(chǎn)生的開銷已經(jīng)遠大于裝配的開銷，使得多線程計算方式在處理效果上還不如單線程。

圖2　寬度對計算時間影響圖

4.3局部最優(yōu)和全局最優(yōu)選擇算法性能分析

這部分實驗采用單線程、單機計算方式。為驗證Web服務組合選擇算法在約束上下文條件下的性能，實驗用后繼匹配率來表示滿足服務約束的后繼服務占有情況，即后繼匹配率=滿足服務的后繼服務數(shù)量/后繼服務的整體數(shù)量。設定整個服務組合的滿分為100，選擇算法負責選擇分數(shù)最高的服務組合。由表1知，當請求服務功能劃分圖的深度(路徑長度)為2(不包含初始節(jié)點)、寬度為2時，最大請求服務的功能數(shù)為6，服務類型數(shù)為28，服務類型組合方式數(shù)為32。圖3給出了這種情況下后繼匹配率為0.5，每種服務類型的候選服務數(shù)量取10～100間的10倍數(shù)離散點時，分別用局部最優(yōu)選擇算法和全局最優(yōu)選擇算法所得的服務組合的分數(shù)情況。圖4給出了對應的局部最優(yōu)選擇算法和全局最優(yōu)算法所花費的時間情況。從圖3和圖4可以看出，全局最優(yōu)算法在效果上略優(yōu)于局部最優(yōu)算法，但是其花費的時間要比局部最優(yōu)選擇算法大得多，而且易受候選服務數(shù)量的影響。

圖3　局部最優(yōu)和全局最優(yōu)選擇算法的分數(shù)對比

圖4　局部最優(yōu)和全局最優(yōu)選擇算法的花費時間對比

5　結　語

本文通過構造請求服務的功能劃分圖，來計算用于Web服務組合的服務類型并規(guī)劃出相應的服務類型組合方式。結合后退一步上下文算法以及動態(tài)規(guī)劃思想，將非功能屬性分類求解，并通過計算局部最優(yōu)來縮小計算范圍的方法，來簡化局部最優(yōu)和全局最優(yōu)選擇問題的復雜度。最后通過仿真實驗，分析了功能劃分圖對第一級裝配算法的影響，以及局部最優(yōu)選擇算法和全局最優(yōu)選擇算法的性能。

[1] 劉恒，張公讓，吳曼.基于分布估計算法的Web服務組合優(yōu)化[J].計算機技術與發(fā)展，2014，24(6)：10-14.

[2] PengWei Wang，ZhiJun Ding，ChangJun Jiang，et al.Constraint-Aware Approach to Web Service Composition[J].IEEE Transactions on Systems,Man,and Cybernetics:Systems，2014，44(6)：770-784.

[3] Incheon Park，Wuhui Chen，Michael N.Huhns.A Scalable Architecture for Automatic Service Composition[J].IEEE Transactions on Services Computing，2014，7(1)：82-95.

[4] 趙明雪，趙文棟，彭來獻，等.基于業(yè)務抽象規(guī)劃的分布式動態(tài)服務組合算法[J].計算機工程，2014，40(4)：37-41,47.

[5] Liangzhao Zeng，Boualam Benatallah，Anne H H Ngu，et al.QoS-Aware Middleware for Web Services Composition[J].IEEE Transactions on Software Engineering，2004，30(5)：311-327.

[6] Dongnei Liu，Zhiqing Shao，Caizhu Yu，et al.A Heuristic QoS-Aware Service Selection Approach to Web Service Composition[C]//Eighth IEEE/ACIS International Conference on Computer and Information Science：IEEE Computer Society，2009:1184-1189.

[8] Shuiguang Deng，Longtao Huang，Wei Tan，et al.Top-k Automatic Service Composition:A Parallel Framework for Large-Scale Service Sets[J].IEEE Transactions on Automation Science and Engineering，2014，11(3)：891-905.

[9] Cristima Bianca Pop，Viorica Rozina Chifu，Ioan Salomie，et al.Ant-inspired Technique for Automatic Web Service Composition and Selection[C]//2011 13th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (2010)：IEEE Computer Society ，2010:449-455.

[10] 趙文棟，田暢，彭來獻.CBSD：一種基于Chord的模糊服務發(fā)現(xiàn)方法[J].計算機科學，2014，41(1)：172-177.

[11] 賀興亞，王海艷.基于Petri網(wǎng)的組件服務發(fā)現(xiàn)方法[J].計算機技術與發(fā)展，2014，24(7)：136-140.

[12] Jinjun Cheng，Cong Liu，MengChu Zhou，et al.Automatic Composition of Semantic Web Services Based on Fuzzy Predicate Petri Nets[J].Automation Science and Engineering，2015，12(2)：680-689.

[13] Yang Jie，Zhou Xianzhong，Wang Jiacun，et al.A Novel Method for Web Service Composition Based on Extended BDI[C]//2014 IEEE 11th International Conference on Networking,Sensing and Control，2014：310-315.

[14] Xuanzhe Liu，Gang Huang，Junfeng Zhao，et al.Data-Driven Composition for Service-Oriented Situational Web Applications[J].IEEE Transactions on Services Computing，2014，8(1)：2-16.[15] Hong Qing Yu，Stephan Reiff-Marganiec.A Backwards Composition Context Based Service Selection Approach for Service Composition[C]//2009 IEEE International Conference on Services Computing (SCC)：IEEE Computer Society，2009:419-426.

[16] Rajesh Karunamurthy，F(xiàn)erhatKhendek，Roch H Glitho.A Novel Architecture for Web Service Composition[J].Journal of Network and Computer Applications，2012，35(2)：787-802.

[17] Rajeswari M，Sambasivam G，Balaji N，et al.Appraisal and Analysis on Various Web Service Composition Approaches Based on QoS Factors[J].Journal of King Saud University-Computer and Information Sciences，2014，26(1)：143-152.

WEB SERVICE COMPOSITION PLANNING AND OPTIMAL SELECTION BASED ON FUNCTION PARTITION MAP

Wu FangZhu Shangming*

(Department of Computer Science and Engineering,East China University of Science and Technology,Shanghai 200237,China)

To expand the composition mode of Web service types,implement seamless Web service composition and improve the reliability of service composition are the focuses of current Web service composition research.Considering the diversity of Web service composition modes and the seamless service composition issue,we calculate the candidate service types applicable to the service composition based on the function partition map of service,dynamically plan the composition mode of various service types,and propose an assembly algorithm of the first stage service type.Aiming at the reliability issue of service composition,we express the operating environment required by Web service itself and the preferential conditions of its own as the context,and propose the correlated local optimum and global optimum selection algorithms to find the real service composition with high reliability.Finally,we verify the performances of the assembly algorithm of first stage service type,the local optimum and the global optimum selection algorithms through simulation experiments.

Web service compositionFunction partition mapAssembly algorithm of first stage service typeLocal optimum selection algorithmGlobal optimum selection algorithm

2015-05-22。計算機與法律復合應用型人才培養(yǎng)基礎案例庫建設項目(A-3101-14-17-172103)。吳芳，碩士生，主研領域：計算機網(wǎng)絡與應用。朱尚明，教授。

TP393

A

10.3969/j.issn.1000-386x.2016.09.003