不確定狀態自動服務組合算法模型的研究

摘 要：由于缺少合適的服務描述模型，基于BPEL服務組合方法無法實現自動服務組合。提出一個基于STRIPS的服務描述模型實現服務自動組合。當存在不同的服務前提對應不同服務結果時，STRIPS模型變成了一個NFA，擴展POPLAN算法，將NFA變成DFA，實現了不確定狀態服務的自動組合。

關鍵詞：自動服務組合；STRIPS；DFA；NFA；Extended POPLAN

1 引言

近年來，軟件服務作為網絡上信息處理能力的一種抽象形式得到了廣泛關注。面向服務的計算（SOC）技術已成為標識分布式系統和軟件集成等方向技術進步的一個新的里程碑[1]。SOC倡導以服務及其組合為基礎構造應用的開發模式，使能標準化、松耦合和透明的應用集成方式，有助于提高應用系統的互操作能力、敏捷性和集成能力[2]。

本文提出了基于STRIPS（Stanford Research Institute Problem Solver）[3]的服務組合描述模型，擴展POPLAN算法，通過一階邏輯計算確定狀態服務組合，實現自動服務組合。

2 基于STRIPS的服務組合描述模型

STRIPS是R.Fikes和N.Nilsson在1971年提出的一個自動規劃問題分析器，后來發展成為一種形式化的規劃輸入語言。基于STRIPS來做服務組合模型，包括領域描述的一階謂詞邏輯和包含條件和結果的服務行為。

服務（Service）：服務S是一個操作符集合，S=。

服務狀態State（S）：是領域中的一個命題子集合組成，對于集合中的每個命題，值均為“真”，非值均為“假”，而且集合外的命題不確定。

目標狀態Goal（S）：是一個領域命題子集合，集合中元素為“真”，集合外命題不確定。

可執行服務組合規劃（Executable Service Composition Plan）： 可執行服務組合規劃對應于可執行業務流程語言應用（Executable BPEL或者BPEL）。

松鏈接（Casual-Link）： 。

抽象服務組合規劃（Abstract Service Composition Plan）：一個服務行為序列，滿足從初始狀態到目標狀態轉移， Π=。DFA和NFA的E-traveling服務組合分析。

某旅游系統是實現了的一個包含旅游代理、飛機票代理、火車票代理、賓館服務和信用卡交費服務等的旅游服務組合原型系統，如圖1和2。

圖1是一個DFA的旅游領域業務流程圖。目前Web服務組合相關標準不支持相似能力優先級的選擇，而DFA也不能在一個狀態連接多個后繼狀態，因此在規劃選擇飛機還是火車時實際是不可能同時出現在一個狀態的轉移圖中。而把每一個步驟映射成一個服務行為，即可以得到服務組合結果。

圖2是一個非確定有限狀態機圖。當查詢到賓館價格時，旅游代理可以判斷是否滿足用戶要求，如果不滿足可以通過重新查詢賓館架構，否則調用賓館預定服務。同樣的情況包括火車或者飛機票價查詢和預定。用戶甚至可以因為對行程不滿意而更新需求（A16：revision required），更換滿意的房間價格，類型、飛機票價格，出行時間等等。

3 基于STRIPS的自動服務組合算法

3.1 面向DFA的POPLAN服務規劃算法

DFA的服務組合問題，因為服務行為及其對應的輸入輸出確定，為了實現自動服務組合，需要解決兩個問題。第一，服務選擇，第二，服務編排，及確定服務組合邏輯及其順序。

3.1.1 服務選擇

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

算法 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的旅游服務場景中服務行為

3.1.2 服務編排

基于BPEL規范，將服務之間的結構關系主要分解為順序、并發、選擇和循環來處理。

算法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

而服務消息和服務提供商的確定，可以基于UDDI和WSDL直接查找實現，不需要復雜算法。

3.2 面向NFA的Extended POPLAN服務規劃

3.2.1 不確定服務狀態分類

相對于圖1，圖2更合適的描述用戶旅游服務組合場景。圖2包括三個方面的擴展：（1）用戶可以根據需求返回以前狀態。 （2）服務響應可能因為不同的結果存在多個后續狀態。（3）有些相似功能的服務，需要用戶指定前提來選擇服務A還是服務B，甚至是服務C。

從服務請求和服務響應的角度對以上情況進行分類。如果狀態后續狀態有多個請求分支，為不確定請求。如果狀態的后續情況有多個響應分支，稱之為不確定響應。針對不確定請求是用不同的行為名定義，因為針對不同請求，而針對相應則是采用同一個行為名的不同分支實現。

3.2.2 增加服務前提解決不確定服務請求

增加服務前提的算法主要是輸入一個有序規劃，包括起始狀態，目標狀態和一系列中間服務行為，輸出為增加一些新的服務行為、前后關系和松鏈接，保證服務組合狀態確定。對應圖2中的不確定請求，結合New Establish-Precondition（π）算法解決，當用戶需求缺乏一定參數時，要求用戶提供新的前提參數。

算法 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 動態選擇服務商解決不確定服務響應

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

算法 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 總結

基于STRIPS的服務描述模型將服務組合轉化成了一個確定狀態的自動機，通過POPLAN找到一條連接起始狀態和目標狀態有向無環圖，從而實現了目標服務的自動組合。而不確定狀態的服務組合可以通過增加服務前提和動態選擇服務提供商，將不確定狀態的服務組合轉化成為確定狀態的服務組合，通過服務規劃算法進行服務組合。

[參考文獻]

[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.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]張文濤，彭泳，陳俊亮.會話類E-Service的接口兼容和服務組合分析. 計算機學報，2006.7：p.15-25.