基于功能劃分圖的Web服務組合規劃和最優選擇

吳　芳　朱尚明

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

?

基于功能劃分圖的Web服務組合規劃和最優選擇

吳芳朱尚明*

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

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

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

0　引　言

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

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

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

1　相關工作

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

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

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

2　Web服務組合方式規劃

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

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

2.1基本概念

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

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

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

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

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

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

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

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

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

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

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

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

2.2服務組合規劃

規劃服務組合分為3個階段：

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

? 匹配、分類第一級服務，產生第一級服務類型；

? 裝配第一級服務類型，產生抽象服務類型組合。

1) 構造功能劃分圖

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

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

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

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

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

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

定義9第一級服務類型：第一級服務經第一級組合的分類階段產生的抽象服務類型。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3　最優Web服務組合選擇算法

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

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

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

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

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

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

3.1帶約束上下文的局部最優選擇算法

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

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

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

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

3.2帶約束上下文的全局最優選擇算法

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

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

2) 計算當前層的局部最優解。

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

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

5) 找到開始出現變化的層數，更新服務狀態，設開始出現變化的層為當前層，進入第2)步。

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

4　實驗及性能分析

4.1實驗環境

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

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

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

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

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

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

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

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

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

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

4.3局部最優和全局最優選擇算法性能分析

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

圖3　局部最優和全局最優選擇算法的分數對比

圖4　局部最優和全局最優選擇算法的花費時間對比

5　結　語

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

[1] 劉恒，張公讓，吳曼.基于分布估計算法的Web服務組合優化[J].計算機技術與發展，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] 趙明雪，趙文棟，彭來獻，等.基于業務抽象規劃的分布式動態服務組合算法[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的模糊服務發現方法[J].計算機科學，2014，41(1)：172-177.

[11] 賀興亞，王海艷.基于Petri網的組件服務發現方法[J].計算機技術與發展，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，FerhatKhendek，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。計算機與法律復合應用型人才培養基礎案例庫建設項目(A-3101-14-17-172103)。吳芳，碩士生，主研領域：計算機網絡與應用。朱尚明，教授。

TP393

A

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