摘 要：由于缺少合適的服務(wù)描述模型，基于BPEL服務(wù)組合方法無(wú)法實(shí)現(xiàn)自動(dòng)服務(wù)組合。提出一個(gè)基于STRIPS的服務(wù)描述模型實(shí)現(xiàn)服務(wù)自動(dòng)組合。當(dāng)存在不同的服務(wù)前提對(duì)應(yīng)不同服務(wù)結(jié)果時(shí)，STRIPS模型變成了一個(gè)NFA，擴(kuò)展POPLAN算法，將NFA變成DFA，實(shí)現(xiàn)了不確定狀態(tài)服務(wù)的自動(dòng)組合。

關(guān)鍵詞：自動(dòng)服務(wù)組合；STRIPS；DFA；NFA；Extended POPLAN

1 引言

近年來(lái)，軟件服務(wù)作為網(wǎng)絡(luò)上信息處理能力的一種抽象形式得到了廣泛關(guān)注。面向服務(wù)的計(jì)算（SOC）技術(shù)已成為標(biāo)識(shí)分布式系統(tǒng)和軟件集成等方向技術(shù)進(jìn)步的一個(gè)新的里程碑[1]。SOC倡導(dǎo)以服務(wù)及其組合為基礎(chǔ)構(gòu)造應(yīng)用的開(kāi)發(fā)模式，使能標(biāo)準(zhǔn)化、松耦合和透明的應(yīng)用集成方式，有助于提高應(yīng)用系統(tǒng)的互操作能力、敏捷性和集成能力[2]。

本文提出了基于STRIPS（Stanford Research Institute Problem Solver）[3]的服務(wù)組合描述模型，擴(kuò)展POPLAN算法，通過(guò)一階邏輯計(jì)算確定狀態(tài)服務(wù)組合，實(shí)現(xiàn)自動(dòng)服務(wù)組合。

2 基于STRIPS的服務(wù)組合描述模型

STRIPS是R.Fikes和N.Nilsson在1971年提出的一個(gè)自動(dòng)規(guī)劃問(wèn)題分析器，后來(lái)發(fā)展成為一種形式化的規(guī)劃輸入語(yǔ)言?；赟TRIPS來(lái)做服務(wù)組合模型，包括領(lǐng)域描述的一階謂詞邏輯和包含條件和結(jié)果的服務(wù)行為。

服務(wù)（Service）：服務(wù)S是一個(gè)操作符集合，S=。

服務(wù)狀態(tài)State（S）：是領(lǐng)域中的一個(gè)命題子集合組成，對(duì)于集合中的每個(gè)命題，值均為“真”，非值均為“假”，而且集合外的命題不確定。

目標(biāo)狀態(tài)Goal（S）：是一個(gè)領(lǐng)域命題子集合，集合中元素為“真”，集合外命題不確定。

可執(zhí)行服務(wù)組合規(guī)劃（Executable Service Composition Plan）： 可執(zhí)行服務(wù)組合規(guī)劃對(duì)應(yīng)于可執(zhí)行業(yè)務(wù)流程語(yǔ)言應(yīng)用（Executable BPEL或者BPEL）。

松鏈接（Casual-Link）： 。

抽象服務(wù)組合規(guī)劃（Abstract Service Composition Plan）：一個(gè)服務(wù)行為序列，滿(mǎn)足從初始狀態(tài)到目標(biāo)狀態(tài)轉(zhuǎn)移， Π=。DFA和NFA的E-traveling服務(wù)組合分析。

某旅游系統(tǒng)是實(shí)現(xiàn)了的一個(gè)包含旅游代理、飛機(jī)票代理、火車(chē)票代理、賓館服務(wù)和信用卡交費(fèi)服務(wù)等的旅游服務(wù)組合原型系統(tǒng)，如圖1和2。

圖1是一個(gè)DFA的旅游領(lǐng)域業(yè)務(wù)流程圖。目前Web服務(wù)組合相關(guān)標(biāo)準(zhǔn)不支持相似能力優(yōu)先級(jí)的選擇，而DFA也不能在一個(gè)狀態(tài)連接多個(gè)后繼狀態(tài)，因此在規(guī)劃選擇飛機(jī)還是火車(chē)時(shí)實(shí)際是不可能同時(shí)出現(xiàn)在一個(gè)狀態(tài)的轉(zhuǎn)移圖中。而把每一個(gè)步驟映射成一個(gè)服務(wù)行為，即可以得到服務(wù)組合結(jié)果。

圖2是一個(gè)非確定有限狀態(tài)機(jī)圖。當(dāng)查詢(xún)到賓館價(jià)格時(shí)，旅游代理可以判斷是否滿(mǎn)足用戶(hù)要求，如果不滿(mǎn)足可以通過(guò)重新查詢(xún)賓館架構(gòu)，否則調(diào)用賓館預(yù)定服務(wù)。同樣的情況包括火車(chē)或者飛機(jī)票價(jià)查詢(xún)和預(yù)定。用戶(hù)甚至可以因?yàn)閷?duì)行程不滿(mǎn)意而更新需求（A16：revision required），更換滿(mǎn)意的房間價(jià)格，類(lèi)型、飛機(jī)票價(jià)格，出行時(shí)間等等。

3 基于STRIPS的自動(dòng)服務(wù)組合算法

3.1 面向DFA的POPLAN服務(wù)規(guī)劃算法

DFA的服務(wù)組合問(wèn)題，因?yàn)榉?wù)行為及其對(duì)應(yīng)的輸入輸出確定，為了實(shí)現(xiàn)自動(dòng)服務(wù)組合，需要解決兩個(gè)問(wèn)題。第一，服務(wù)選擇，第二，服務(wù)編排，及確定服務(wù)組合邏輯及其順序。

3.1.1 服務(wù)選擇

借鑒SHOP2[10]分析含輸入輸出的服務(wù)描述生成服務(wù)行為前提和結(jié)果。

算法 Service Predictions Effects Creation

Input：a WSDL definition of Service S

Output： precondition，

effect set of the form（S，Pre，Eff，Cost，Role， Provider）

Insert Operator o in table as service operator

Pre=a conjunct of all input of A，as defined in table，

plus one more precondition —0

Eff=a conjunct of all output， plus one more effect as o，

and delete other conflict with Eff

For service request，the cost is 1，else for service

response the cost is 0.5

Give related role and provider value

DFA的旅游服務(wù)場(chǎng)景中服務(wù)行為

3.1.2 服務(wù)編排

基于BPEL規(guī)范，將服務(wù)之間的結(jié)構(gòu)關(guān)系主要分解為順序、并發(fā)、選擇和循環(huán)來(lái)處理。

算法Service Structure Determination（π）

Input： a partial-order plan with steps，

step order and casual links

Output： Structure（π）

For each operator o in （π））

If o is partial-ordered step

Structure （π）=Sequence or Parallel

Else If o has similar precondition and different effect

Structure （π）=Select

Else

Structure （π）=Sequence

而服務(wù)消息和服務(wù)提供商的確定，可以基于UDDI和WSDL直接查找實(shí)現(xiàn)，不需要復(fù)雜算法。

3.2 面向NFA的Extended POPLAN服務(wù)規(guī)劃

3.2.1 不確定服務(wù)狀態(tài)分類(lèi)

相對(duì)于圖1，圖2更合適的描述用戶(hù)旅游服務(wù)組合場(chǎng)景。圖2包括三個(gè)方面的擴(kuò)展：（1）用戶(hù)可以根據(jù)需求返回以前狀態(tài)。 （2）服務(wù)響應(yīng)可能因?yàn)椴煌慕Y(jié)果存在多個(gè)后續(xù)狀態(tài)。（3）有些相似功能的服務(wù)，需要用戶(hù)指定前提來(lái)選擇服務(wù)A還是服務(wù)B，甚至是服務(wù)C。

從服務(wù)請(qǐng)求和服務(wù)響應(yīng)的角度對(duì)以上情況進(jìn)行分類(lèi)。如果狀態(tài)后續(xù)狀態(tài)有多個(gè)請(qǐng)求分支，為不確定請(qǐng)求。如果狀態(tài)的后續(xù)情況有多個(gè)響應(yīng)分支，稱(chēng)之為不確定響應(yīng)。針對(duì)不確定請(qǐng)求是用不同的行為名定義，因?yàn)獒槍?duì)不同請(qǐng)求，而針對(duì)相應(yīng)則是采用同一個(gè)行為名的不同分支實(shí)現(xiàn)。

3.2.2 增加服務(wù)前提解決不確定服務(wù)請(qǐng)求

增加服務(wù)前提的算法主要是輸入一個(gè)有序規(guī)劃，包括起始狀態(tài)，目標(biāo)狀態(tài)和一系列中間服務(wù)行為，輸出為增加一些新的服務(wù)行為、前后關(guān)系和松鏈接，保證服務(wù)組合狀態(tài)確定。對(duì)應(yīng)圖2中的不確定請(qǐng)求，結(jié)合New Establish-Precondition（π）算法解決，當(dāng)用戶(hù)需求缺乏一定參數(shù)時(shí)，要求用戶(hù)提供新的前提參數(shù)。

算法 New Establish-Precondition （π）

Input：a partial-order plan πwith initial step，

final step and maybe inside steps

Output：some new step，step order，and casual links added to （π）

For （p） applied to （π） and Se，by adding new constraints θ

For ……，if some of Se are new steps，add new steps to Steps （π）Add ordering constraints

……and to …… rder （π）

Add casual

link <…… > to C-links （π）

3.2.3 動(dòng)態(tài)選擇服務(wù)商解決不確定服務(wù)響應(yīng)

因是否有票等線(xiàn)性約束，可以通過(guò)Abstract BPEL/UDDI交互回溯來(lái)查找合理的服務(wù)商，ChooseProvider算法的基本思路即根據(jù)量化條件選擇起始服務(wù)供應(yīng)商，分析其響應(yīng)是否滿(mǎn)足，滿(mǎn)足則繼續(xù)選擇下一服務(wù)提供商，如果不滿(mǎn)足，返回上一步，換服務(wù)商，直到所有服務(wù)商均確定并滿(mǎn)足要求，返回服務(wù)商列表，如果所有服務(wù)商遍歷均不滿(mǎn)足條件，返回空，即無(wú)滿(mǎn)足條件的服務(wù)商。

算法 ChooseProvider（ ， UDDI， QCList）

Input： a partial-order planπ ，uddi， qclist

Output： determined provider for each action/role and concrete

partial-order plan

Repeat

a=firstAction （π）

π=π-3

qc = getPolicy（QCList，a）

if（webServiceAction（a）） then

role=Role（a）

provider = contactUDDI（role）

If（provider ！= 1）

message = invoke（a， provider）

if（！match（qc， message）） goto 7 for another provider

else throw exception for no acceptable provider for a

until π=0

return （（a， provider） list）

4 總結(jié)

基于STRIPS的服務(wù)描述模型將服務(wù)組合轉(zhuǎn)化成了一個(gè)確定狀態(tài)的自動(dòng)機(jī)，通過(guò)POPLAN找到一條連接起始狀態(tài)和目標(biāo)狀態(tài)有向無(wú)環(huán)圖，從而實(shí)現(xiàn)了目標(biāo)服務(wù)的自動(dòng)組合。而不確定狀態(tài)的服務(wù)組合可以通過(guò)增加服務(wù)前提和動(dòng)態(tài)選擇服務(wù)提供商，將不確定狀態(tài)的服務(wù)組合轉(zhuǎn)化成為確定狀態(tài)的服務(wù)組合，通過(guò)服務(wù)規(guī)劃算法進(jìn)行服務(wù)組合。

[參考文獻(xiàn)]

[1]M.Papazoglou，D.G.，Service-Oriented Computing。 Communications of the ACM， 2003.46（10）：p.25-28.

[2]D.Berardi，D.C.，G.De Giacomo，Reasoning about Actions for e-Service Composition，in ICAPS'03 Workshop on Planning for Web Services.2003：Trento，Italy.

[3]M.Castilho，L.A.K，E.Lecheta，F(xiàn).Silva An Investigation on Genetic Algorithms for Generic STRIPS Planning.LECTURE NOTES IN COMPUTER SCIENCE，2004： p.185--194.

[4]A.Lazovik，M.Aielloand M.Papazoglou，Planning and monitoring the execution of web service requests International Journal on Digital Libraries，2006.6（3）：p.235-246.

[5]A.Lazovik，M.A，M Papazoglou，Planning and monitoring the execution of web service requests，in Service Oriented Computing.2003.p 335-350.

[6]McIlraith，S.and T.C.Son Adapting Golog for Programming the Semantic Web.

[7]張文濤，彭泳，陳俊亮.會(huì)話(huà)類(lèi)E-Service的接口兼容和服務(wù)組合分析. 計(jì)算機(jī)學(xué)報(bào)，2006.7：p.15-25.