吳　芳　朱尚明

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

?

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

吳芳朱尚明*

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

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

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

0　引　言

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

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

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

1　相關(guān)工作

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

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

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

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

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

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

2.1基本概念

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

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

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

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

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

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

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

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

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

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

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

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

2.2服務(wù)組合規(guī)劃

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

? 構(gòu)造請求服務(wù)的功能劃分圖；

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

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

1) 構(gòu)造功能劃分圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5) 找到開始出現(xiàn)變化的層數(shù)，更新服務(wù)狀態(tài)，設(shè)開始出現(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ā)工具。用鏈表結(jié)構(gòu)存儲請求服務(wù)功能劃分圖，用樹結(jié)構(gòu)表示第一級服務(wù)類別，并為每個服務(wù)類別添加一個唯一的標識符。建立Composition類來模擬符合請求服務(wù)的單個服務(wù)組合，在Composition類中使用一個vector容器類型的成員變量來存儲組成這個服務(wù)組合的所有服務(wù)類型的標識。

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

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

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

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

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

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

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

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

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

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

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

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

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

5　結(jié)　語

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

[1] 劉恒，張公讓，吳曼.基于分布估計算法的Web服務(wù)組合優(yōu)化[J].計算機技術(shù)與發(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è)務(wù)抽象規(guī)劃的分布式動態(tài)服務(wù)組合算法[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的模糊服務(wù)發(fā)現(xiàn)方法[J].計算機科學(xué)，2014，41(1)：172-177.

[11] 賀興亞，王海艷.基于Petri網(wǎng)的組件服務(wù)發(fā)現(xiàn)方法[J].計算機技術(shù)與發(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。計算機與法律復(fù)合應(yīng)用型人才培養(yǎng)基礎(chǔ)案例庫建設(shè)項目(A-3101-14-17-172103)。吳芳，碩士生，主研領(lǐng)域：計算機網(wǎng)絡(luò)與應(yīng)用。朱尚明，教授。

TP393

A

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