吳　芳　朱尚明

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

?

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

吳芳朱尚明*

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

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

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

0　引　言

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

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

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

1　相關(guān)工作

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

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

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

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

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

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

2.1基本概念

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(2) 開(kāi)始節(jié)點(diǎn)用有向邊指向所有無(wú)前驅(qū)的節(jié)點(diǎn)，所有無(wú)后繼節(jié)點(diǎn)指向終結(jié)節(jié)點(diǎn)。

2) 匹配、分類(lèi)第一級(jí)服務(wù)

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

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

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

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

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

推論2一個(gè)無(wú)輸入依賴(lài)的抽象服務(wù)功能，其前驅(qū)節(jié)點(diǎn)一定是開(kāi)始節(jié)點(diǎn)。

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

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

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

3) 第一級(jí)服務(wù)類(lèi)型裝配算法

第一級(jí)服務(wù)類(lèi)型對(duì)應(yīng)的裝配算法簡(jiǎn)稱(chēng)第一級(jí)裝配算法。其具體過(guò)程分為兩階段：分層階段和裝配階段。

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

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

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

圖1　第一級(jí)裝配算法流程圖

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

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

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

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

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

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

定義11部分依賴(lài)屬性：由Web服務(wù)組合中的部分Web服務(wù)計(jì)算得到的屬性，即服務(wù)組合在此屬性上的值是通過(guò)某種規(guī)則選出部分Web服務(wù)，由它們?cè)谶@個(gè)屬性上的值經(jīng)過(guò)運(yùn)算得到的。

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

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

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

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

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

帶約束上下文的局部最優(yōu)算法的實(shí)質(zhì)就是逐層地找出滿(mǎn)足上一層選出服務(wù)的約束條件的本層最優(yōu)服務(wù)組合。考慮到會(huì)有沒(méi)有后繼服務(wù)的服務(wù)被選中而造成“無(wú)解”的情況，這里引入失敗回退機(jī)制，具體算法過(guò)程如下：

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

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

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

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

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

2) 計(jì)算當(dāng)前層的局部最優(yōu)解。

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

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

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

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

4　實(shí)驗(yàn)及性能分析

4.1實(shí)驗(yàn)環(huán)境

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

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

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

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

表1　深度對(duì)性能指標(biāo)的影響(寬度為2)

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

表2　寬度對(duì)性能指標(biāo)的的影響(深度為2)

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

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

圖2　寬度對(duì)計(jì)算時(shí)間影響圖

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

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

圖3　局部最優(yōu)和全局最優(yōu)選擇算法的分?jǐn)?shù)對(duì)比

圖4　局部最優(yōu)和全局最優(yōu)選擇算法的花費(fèi)時(shí)間對(duì)比

5　結(jié)　語(yǔ)

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

[1] 劉恒，張公讓?zhuān)瑓锹?基于分布估計(jì)算法的Web服務(wù)組合優(yōu)化[J].計(jì)算機(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] 趙明雪，趙文棟，彭來(lái)獻(xiàn)，等.基于業(yè)務(wù)抽象規(guī)劃的分布式動(dòng)態(tài)服務(wù)組合算法[J].計(jì)算機(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] 趙文棟，田暢，彭來(lái)獻(xiàn).CBSD：一種基于Chord的模糊服務(wù)發(fā)現(xiàn)方法[J].計(jì)算機(jī)科學(xué)，2014，41(1)：172-177.

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

TP393

A

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