語義Ｗｅｂ服務(wù)組合方法研究

摘要：該文首先對語義Web服務(wù)組合的研究內(nèi)容和現(xiàn)狀進(jìn)行了概括，緊接著對現(xiàn)有的語義服務(wù)組合方法進(jìn)行了分類，然后著重討論了這些組合方法的特點(diǎn)及其相關(guān)應(yīng)用。

關(guān)鍵詞：Web服務(wù)；語義Web服務(wù)組合；人工智能

中圖分類號：TP311文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044(2008)36-2979-03

A Research on Semantic Web Services Composition

LAN Xin-bo，YANG Shan-you

(GuangDong AIB polytechnic college，Guangzhou 510663，China)

Abstract: At first，this article has been carried on the summary to the semantic Web service composition's research content and the present situation，and then classified the existing semantic service composition's method，finally discussed the Characteristic and using of these composition’s method emphatically.

Key words: Web Service; semantic web service composition; artificial intelligence

語義Web服務(wù)的自動化組合的工作主要來自兩個領(lǐng)域：一個是人工智能領(lǐng)域，一是形式化方法和自動推理領(lǐng)域。它們之間的工作既相互交叉，又互為補(bǔ)充。來自人工智能領(lǐng)域的工作主要包括構(gòu)建用于Web服務(wù)描述的本體和提出了一系列的面向Web服務(wù)功能的Web服務(wù)組合方案。來自形式化方法和自動推理領(lǐng)域的工作主要包括面向Web服務(wù)行為的服務(wù)組合方法，當(dāng)然，也有借鑒于自動化程序綜合（program synthesis）和模型檢驗（model checking）的方法。

一般地，語義Web服務(wù)的組合方法按其關(guān)注點(diǎn)的不同可分為：面向Web服務(wù)行為的組合方法、面向Web服務(wù)功能的組合方法和基于Web服務(wù)類型的組合方法；按其實(shí)現(xiàn)方式的不同可分為：面向狀態(tài)搜索算法的組合方法、面向自動推理的組合方法和面向人工智能規(guī)劃的算法。

1 基于情景演算的人工智能規(guī)劃方法

這類方法的基本思想是使用人工智能規(guī)劃中的動作來對Web服務(wù)進(jìn)行建模，利用人工智能中的規(guī)劃算法來進(jìn)行Web服務(wù)組合。它所找到的組合服務(wù)通常比基于服務(wù)輸入、輸出參數(shù)的類型匹配的方法要來得準(zhǔn)確，但是這類方法所能適用的Web服務(wù)范圍比較有限。

我們可以把Web服務(wù)看作是AI規(guī)劃中的動作。在經(jīng)典的規(guī)劃問題中，動作由動作的前提條件和效應(yīng)所刻畫，而動作的前提條件和效應(yīng)是參與動作的個體的一組狀態(tài)構(gòu)成，動作的執(zhí)行將使得某些個體處于新的狀態(tài)之中。例如在經(jīng)典的積木世界里面，使用手臂舉起物體的動作pickup可用PDDL(Planning Domain Definition Language)描述如下：

(：action pickup

：parameters (?ob)

：precondition (and (clear ?ob) (arm-empty))

：effect(and (holding ?ob)(not(arm-empty)) (when(on-table ?ob) (not (on-table ?ob))))

)

情景演算最基本的思想就是通過把動作和情境（situation）具體化（reify）以方便進(jìn)行一階邏輯推理。所謂情景，形式上就是參與規(guī)劃的個體所處的狀態(tài)。在情景演算中，我們用流（fluent）來抽象整個個體的某一特性隨情景變化的過程，而個體的狀態(tài)則就是個體在特定情境下所具有的特性。假設(shè)初始情景S0恰好滿足動作pickup(a)的前提，也即是說S0為{clear（a，So），arm-empty(S0)，…}，那么我們只要通過一步的推理就可得出執(zhí)行動作pickup(a)后的情景是{holding(a， do (pickup(a)，So，…}，其中do(pickup(a))是情景集合上的一函詞，指定了執(zhí)行動作pickup(a)之后相應(yīng)的情景遷移。

情景演算通常包含兩類公理，一類是動作的前提公理，用于指定各個動作能夠被觸發(fā)的條件；另一類是流的后繼公理，用于指定各個狀態(tài)在每個動作執(zhí)行之后的變化情況。就上例來說，動作pickup的前提公理是Poss (pickup(ob)，S)≡?坌ob.cleat(ob)∧arm-empty。而流on-table的后繼公理是on-table(x，do(action，S)) ≡on-table(x，S) ∧action≠pickup(x)∨… 其顯得更為復(fù)雜些。

Web服務(wù)的并發(fā)行為特性和經(jīng)典規(guī)劃中的動作的行為特性是非常不一樣的，而針對經(jīng)典規(guī)劃問題提出的情景演算僅能產(chǎn)生由一組順序動作構(gòu)成的計劃，因此在處理循壞、非不確定性和并發(fā)性時的行為需要一個解釋器，而不是一個規(guī)劃產(chǎn)生器。Web服務(wù)的執(zhí)行通常會導(dǎo)致新的個體產(chǎn)生，這些個體通常作為Web服務(wù)執(zhí)行的結(jié)果返回給用戶；而經(jīng)典規(guī)劃中假定參與規(guī)劃的個體不會在規(guī)劃的過程中產(chǎn)生或消失，動作執(zhí)行只是導(dǎo)致個體的狀態(tài)發(fā)生變化。

2 基于模型檢驗的人工智能規(guī)劃方法

如果把Web服務(wù)進(jìn)一步細(xì)分為感知動作（sending action）和實(shí)效動作（effect action）兩類，則Web服務(wù)組合問題可以轉(zhuǎn)化為不確定領(lǐng)域中的條件規(guī)劃問題。下面我們將要介紹的用于服務(wù)交響自動化的規(guī)劃算法正是反映了上述思想，這個思想對服務(wù)組合的自動化來說具有極大的借鑒意義。另外，我們可以在BPEL4WS上使用不確定領(lǐng)域中的規(guī)劃算法，利用規(guī)劃中的動作來刻畫Web服務(wù)的交互信息，能夠較好地處理Web服務(wù)的非確定性，產(chǎn)生非常健壯的Web服務(wù)組合方案。雖然這種方法避免了處理Web服務(wù)產(chǎn)生的新個體，但在Web服務(wù)的交互信息的層面上進(jìn)行程序綜合并不十分適合于面向功能的語義Web服務(wù)組合。所以使用這一類方法的服務(wù)組合方案一般是兩段式的，即先使用基于輸入輸出參數(shù)的類型匹配或面向服務(wù)功能的人工智能規(guī)劃的服務(wù)組合方法尋找滿足查詢的組合服務(wù)，然后針對這個組合服務(wù)使用這類方法找出與該組合服務(wù)交互的其他Web服務(wù)。

這里的規(guī)劃算法的基本思想是先用遷移系統(tǒng)(transition system)來刻畫初始狀態(tài)在各個動作執(zhí)行后的遷移過程，然后用模型檢驗檢查目標(biāo)狀態(tài)的可達(dá)性。目標(biāo)狀態(tài)的可達(dá)性蘊(yùn)含了規(guī)劃算法處理不確定性時的健壯性。如果在其中定義了多種可達(dá)性，每種可達(dá)性的遷移過程是不一樣，但是每個遷移過程都可以通過OBDD進(jìn)行編碼。下面我們簡單的介紹一下OBDD（Ordered Binary Decision Diagram）和用于刻畫這個遷移過程的程序框架。

例如對于有三個命題變量〈P，Q，V〉的系統(tǒng)，狀態(tài)集合{〈T，T，F(xiàn)〉，〈T，T，T〉}可以用命題邏輯的表達(dá)式PQ來表示，它的一個OBDD表示如圖1所示，其中實(shí)邊表示把源節(jié)點(diǎn)的變量賦為真T，虛邊表示把源節(jié)點(diǎn)的變量賦為假F。

在規(guī)劃中，我們習(xí)慣于用一階邏輯謂詞來刻畫規(guī)劃中的動作和狀態(tài)。但注意到參與規(guī)劃的個體數(shù)量n是有限的，我們就把一階邏輯謂詞轉(zhuǎn)化為命題詞。由于任意的動作都可以看作從一組狀態(tài)集合到另一組狀態(tài)集合的遷移，我們令rn（Old）為狀態(tài)集合上的一個函數(shù)，用于計算這樣的狀態(tài)集合New，使得New中的元素不包含于狀態(tài)集合Old中但卻能遷移至狀態(tài)集合Old中的狀態(tài)。設(shè)規(guī)劃問題的初始狀態(tài)集合為I，目標(biāo)狀態(tài)集合為G，我們可以使用下面程序刻畫與這個遷移過程相對應(yīng)的遷移系統(tǒng)：

function GENERATEPLAN(I，G)

X:=G

While (rn(X)≠Ф并且I?埸X)

X:=X∪ r n(X;

If (I?哿X)

return X;

Else

return Ф;

end function.

對上面這個程序進(jìn)行模型檢驗，若GENERATEPLAN(I，G)=Ф，則不存在滿足要求的規(guī)劃。否則，存在滿足要求的規(guī)劃。

3 基于參數(shù)匹配的形式化推理方法

參數(shù)匹配的形式化推理方法（Rao）依賴于輸入輸出參數(shù)類型的上下位匹配，只不過該方法借鑒了自動化程序綜合的思想，提出了采用線性邏輯推理進(jìn)行Web服務(wù)組合，因而具備對Web服務(wù)進(jìn)行參數(shù)個數(shù)的匹配的能力。由于該方法所采用的線性邏輯具有不可判定性，這從一定程度上削弱了它能夠?qū)eb服務(wù)進(jìn)行參數(shù)個數(shù)的匹配的優(yōu)勢。

線性邏輯不同于經(jīng)典邏輯，它以資源的觀點(diǎn)來看待命題，?茚表示兩個資源都存在，?茌表示兩個資源中必有一個，表示消耗前面的資源可以產(chǎn)生后面的資源。例如，分別用D和C表示一美元和一包煙，那么“兩美元能購買一包煙”可以表示為D?茚DC。

Rao用線性邏輯來刻畫Web服務(wù)和參數(shù)類型的上下位關(guān)系。譬如一個具有I1和I2類型輸入?yún)?shù)和O類型輸出參數(shù)的Web服務(wù)可表示為I1?茚I2O；又譬如SbSp可以表示Sb是Sp的子類。

線性邏輯和并發(fā)系統(tǒng)兩個重要的計算模型——Petri網(wǎng)和進(jìn)程代數(shù)都有著深刻的聯(lián)系。圖2給出了一個用線性邏輯對Petri網(wǎng)進(jìn)行形式化的例子，其中！是模態(tài)詞，用于產(chǎn)生無限個拷貝。

組合服務(wù)的進(jìn)程構(gòu)造子實(shí)質(zhì)上就是進(jìn)程代數(shù)中的順序運(yùn)算符“.”，不確定選擇“+”和并發(fā)運(yùn)算符“|”。通過對每個推理賦予一定的操作語義（即產(chǎn)生對應(yīng)的Web服務(wù)的進(jìn)程代數(shù)表達(dá)式），我們可以從推理序列獲得組合Web服務(wù)的進(jìn)程代數(shù)表達(dá)式，這個表達(dá)式又可以直接翻譯成組合Web服務(wù)的服務(wù)模型。

例如Web服務(wù)exchange可以讓客戶用一張禮券換取一支鉛筆，即CouponExchange Pencil；Web服務(wù)buy可以讓客戶付一美元買一支鉛筆，即DolarBuy Pencil；那么我們可以得出結(jié)論；無論客戶是選擇Web服務(wù)exchange還是buy，都可以獲得一支鉛筆，即Coupon?茌DollarExchange+buy Pencil。在Rao的方案中，與這對應(yīng)的推理步驟是 ，其對應(yīng)的進(jìn)程代數(shù)表達(dá)式是exchange+buy。

4 基于搜索的方法

語義Web服務(wù)組合和語義Web服務(wù)匹配的聯(lián)系是非常密切的，這里所討論的一類服務(wù)組合算法就是建構(gòu)于服務(wù)匹配之上的。

一個Web服務(wù)S能夠滿足一個查詢Q意味著：對于查詢Q提供的所有輸入，Web服務(wù)S必須都能接受；對于查詢Q所要求的所有輸出，Web服務(wù)S必須至少滿足其中之一。根據(jù)Web服務(wù)類型之間是否存在互相包含或相交的關(guān)系，我們可以定義一個Web服務(wù)S能夠滿足一個查詢Q的程度（按從高到低的順序）：

1）Exact

type(P，Q)≡type(P，S)；

2)plugIn

type(P，Q) ?哿 type(P，S) 如果P是輸入?yún)?shù)；type(P，S) ?哿 type(P，Q) 如果P是輸出參數(shù)；

3）subsume

type(P，Q) ?哿 type(P，Q) 如果P是輸入?yún)?shù)；type(P，Q) ?哿type(P，S) 如果P是輸出參數(shù)；

4）overlap

如果P輸入?yún)?shù)； 如果P輸出參數(shù)。

在確定Web服務(wù)滿足查詢的程度時，輸入?yún)?shù)類型的上下匹配方向和輸出參數(shù)類型的上下匹配方向正好相反。例如有四個在線銷售書籍的Web服務(wù)S1，S2，S3和S4。S1接受中國銀行的和花旗銀行的人民幣信用卡，S2接受所有的人民幣信用卡，S3接受中國銀行的人民幣信用卡，S4接受花旗銀行的多幣種信用卡。如果用戶希望使用手中的中國銀行和花旗銀行的人民幣信用卡來購得一些書籍，那么從輸入的角度看，服務(wù)S1滿足用戶查詢的程度是exact；服務(wù)S2滿足用戶查詢的程度是plugIn；服務(wù)S3滿足用戶查詢的程度是subsume；服務(wù)S4滿足用戶用查詢的程度是overlap。如果進(jìn)一步考慮輸出的話，假定Web服務(wù)S1只出售科技書，那么服務(wù)S1滿足用戶查詢的程度就降為plugIn。

根據(jù)上面的定義可知，僅是在subsume或overlap程度上滿足查詢的Web服務(wù)是無法單獨(dú)滿足我們的確切需要的。為此，它必須與其他Web服務(wù)“相加”，并且這些相加的Web服務(wù)必須能夠囊括查詢提供的輸入。這正是文獻(xiàn)[1]中的服務(wù)組合算法的基本出發(fā)點(diǎn)，該算法通過一個矩陣對服務(wù)進(jìn)行初步的“相加”以得到一個在exact或pluhIn程度上滿足查詢的組合Web服務(wù)，然后再不斷的向前搜索直至獲得要求的輸出。

矩陣的維數(shù)由需要匹配的輸入?yún)?shù)的個數(shù)決定，矩陣的每個維對應(yīng)著一個輸入?yún)?shù)，矩陣中的元素是一組Web服務(wù)，它們在矩陣的各個維上的分量是對應(yīng)的輸入?yún)?shù)所能接受的類型。在上述的例子中，需要匹配的輸入?yún)?shù)只有一個，即購買書籍所使用的信用卡，我們用圖3來示意這個一維矩陣。由圖3可以看出，將S3和S4組合在一起也能夠在plugIn程度上滿足查詢。

圖3 一個Web服務(wù)矩陣的示意圖

目前大多數(shù)的語義Web服務(wù)匹配算法都局限于服務(wù)參數(shù)類型的匹配，但這不等于說不能從服務(wù)的功能上和從服務(wù)的外部行為上來進(jìn)行服務(wù)匹配。如果從服務(wù)的功能上和從服務(wù)的外部行為上來進(jìn)行服務(wù)匹配，那么多少都有計算性和復(fù)雜性方面上的詬病（最顯著的如計算的不可判定性），難以獲得普遍的適應(yīng)性，這也是目前大多的語義Web服務(wù)匹配算法仍停留于參數(shù)類型匹配的原因之一。

5 基于自動機(jī)的形式化推理方法

自動機(jī)和進(jìn)程代數(shù)都可以很自然的刻畫Web服務(wù)的行為以及相應(yīng)的狀態(tài)變化，例如一個接收search消息然后發(fā)送result消息的Web服務(wù)S可以用圖4（a）中的進(jìn)程代數(shù)公式來刻畫：

S=S0;R=R0; Q=Q0;

S0=?search.S1;R0=?filter.R1; Q0=?search.Q1;

S1=! result.S0 .. R1=! result.R0.Q0=? filterQ1;

Q1=! result.Q0.

(a)刻畫Web服務(wù)S的 （b）刻畫Web服務(wù)R的 （c）刻畫組合服務(wù)Q的

行為的進(jìn)程代數(shù)公式 行為的進(jìn)程代數(shù)公式 行為的進(jìn)程代數(shù)公式

圖4一組刻畫Web服務(wù)行為的進(jìn)程代數(shù)公式

如果不區(qū)分動作前綴“？”和“！”在意義上的不同，那么圖4(a)中的各式同時也刻畫了一個自動機(jī)。它的字母表為{?search，!result}，狀態(tài)集為{S0，S1}，并且S0既是初始狀態(tài)也是終止?fàn)顟B(tài)。

另外，圖4(b)和圖4(c)分別給出了另外一個Web服務(wù)R和我們想要獲取的組合服務(wù)Q。我們的目標(biāo)是在自動機(jī)S，R和Q的基礎(chǔ)上構(gòu)造一個“組合”自動機(jī)，并使用PDL對其進(jìn)行編碼以檢驗其可滿足性。由于“組合”自動機(jī)中所有的動作都來自于自動機(jī)S和R，我們用命題變量MovedS和MovedR分別來模擬自動機(jī)S和R在“組合”自動機(jī)中的動作。設(shè)u是由所有原子程序的并構(gòu)成的程序，即 ，我們有：

自動機(jī)S，R和Q在“組合”自動機(jī)的動作遵循圖5中的PDL公式。

(a)刻畫自動機(jī)S的各個狀態(tài)在每種輸入下的動作的PDL公式

(b)刻畫自動機(jī)R的各個狀態(tài)在每種輸入下的動作的PDL公式（下轉(zhuǎn)第2992頁）

（上接第2981頁）

(c)刻畫自動機(jī)Q的各個狀態(tài)在每種輸入下的動作的PDL公式

圖5一組服務(wù)自動機(jī)的PDL編碼

顯然，這個“組合”自動機(jī)還須滿足初始狀態(tài)和接受狀態(tài)等其他一系列的要求。具體的說，這個“組合”自動機(jī)的初始狀態(tài)必須滿足

Q0∧S0∧R0，并且“組合”自動機(jī)的接受狀態(tài)必須滿足[u](Q0→S0∧R0)。最后，我們必須指明各個自動機(jī)中的每個狀態(tài)都是不同的，即在自動機(jī)Q中有[u]（Q0→ ┐Q1）；在自動機(jī)R中有[u]R0→ ┐R1）；在自動機(jī)S中有[u]（S0→ ┐S1）。

從上面構(gòu)造“組合”自動機(jī)的過程中，我們可以看出文獻(xiàn)[2]的基本思想與模型檢驗的原理如出一轍。這不是偶然的，因為從理論上講，一個遷移系統(tǒng)與一組動態(tài)邏輯公式是對等的。所以不論這個遷移系統(tǒng)是用于刻畫動態(tài)邏輯中的Kripke語義結(jié)構(gòu)，或是用于刻畫自動機(jī)，還是用于刻畫進(jìn)程代數(shù)的操作語義，它從形式上總是與一組動態(tài)邏輯公式相對應(yīng)。

6 結(jié)束語

Web服務(wù)組合和服務(wù)描述是分不開。Web服務(wù)的輸入輸出參數(shù)類型、執(zhí)行前提和效果和消息交互序列等信息不僅是服務(wù)描述的對象，也是Web服務(wù)組合的根基。從本論文的論述可以看出，Web服務(wù)組合問題很難獲得一個統(tǒng)一的解決方案。這是因為Web服務(wù)組合所依賴的計算理論基礎(chǔ)決定了Web組合方法必須根據(jù)其關(guān)注的焦點(diǎn)在計算能力和可行性作出適當(dāng)?shù)恼壑浴?/p>

參考文獻(xiàn)：

[1] Ion Constantinescu ，Boi Faltings，Walter Binder.Large Scale，Type-Compatible Service Composition.In:Proc.IEEE Int Conf.Web Services.IEEE CS Press，2004.

[2] Daniela Berardi，Diego Calvanese，Giuseppe De Giacomo，Maurizio Lenzerini and Massimo Mecella.Automatic Service Composition Based on Behavioral Descriptions.Int.J Coop.Inf.Sys，14(4)，2005.

[3] 陳旭輝.基于規(guī)劃的語義Web服務(wù)組合技術(shù)研究[D].福州大學(xué)，2006.

[4] 馮名正.Web服務(wù)組合研究綜述[J].計算機(jī)應(yīng)用與軟件，2007:24(2):23-27.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。”