基于MDP的動態Web服務組合

摘要:在面向服務的環境下，單個Web服務往往不能滿足用戶的要求，這時就需將已有的單個Web 服務進行組合，以便產生滿足用戶需求的組合服務。已有的服務組合方法都很少考慮Web 服務的隨機性和Internet 環境的動態性，從而在服務選擇過程中產生的規劃都是靜態規劃，結果導致在服務組合時都以較大概率出現組合失敗。針對上述問題，利用馬爾可夫決策過程(MDP)，設計出利用隨機QoS作為指標的Web 服務組合算法。

關鍵詞:Web服務;服務組合;Qos;MDP

中圖分類號:TP311文獻標識碼:A文章編號:1009-3044(2009)35-10003-02

Dynamic Web Service Composition Based on MDP

ZHU Xin-Feng， LI Bin， WU Jun

(College of Information Engineering，Yangzhou University， Yangzhou 225009， China)

AbstractIn the service-oriented environment， a single Web service can hardly satisfy the given request， so the composition of multiple Web services is required to fulfill the goal. Without considering the inherent stochastic and dynamic nature of Web service， the existing composition methods mostly generate static plans. As a result， Web service composition often terminates with failure inevitably. In this paper， one reliable Web service composition algorithm is also designed based on markov decision process (MDP).

Key words: web services; service composition; Qos; MDP

Web服務技術己從基礎設施的構建與概念推廣階段向大規模商業應用階段快速發展。前者主要是在早期的研究基礎上，通過制定基于XML的SOAP、WSDL，與UDDI等標準化通信協議與數據描述方式解決了服務定義、接口、服務查找以及松散耦合異構環境下的遠程調用與通信等基礎問題;而后者主要是解決在商業應用過程中所涉及的服務重用與合成、安全、QoS以及長事物的管理與調度等更為復雜的應用問題。其中，如何重用己有的服務，并通過自動化、可管理的方式進行合成來動態生成新的應用系統以滿足企業的動態需求，則成為工業界與學術界共同關注的問題，并且已經成為推動Web服務不斷向前發展的技術動力。

但由于Internet 環境的開放性和動態性以及Web 服務的隨機性，導致組件服務的QoS 具有很強的不確定性，從而影響了服務組合成功率和組合服務的質量.所以，如何準確地度量Web 服務的QoS 以及動態地對其進行自適應管理，對服務的成功組合有著重要的意義;另一方面，已有的服務組合方法在規劃過程中都假設Web 服務具有確定行為，而這個假設往往導致服務組合過程中出現約束沖突。所以，在考慮真實環境的不確定性和動態性的情況下，研究服務的可靠組合方法有著重要的現實意義。

如何獲取Qos值是一個主要問題，已有的QoS 度量方法基本都是用歷史日志的期望值近似實際的QoS 值[1]，但是這種方法忽略了很多不確定的因素如環境等，導致估計值與真實值之間的偏差較大，從而在服務組合時組合出來的結果不符合實際需要。針對這個問題，文中將Web 服務各QoS 指標定義為一系列隨機變量，并利用隨機變量的數學期望和方差來度量各指標的取值，這樣就克服了以往僅用歷史日志期望值來衡量指標的弊端，將具有不同波動性的Web服務區分開來。

服務組合廣義上可以分為手工組合、半自動組合和自動組合[2]。由于Internet 上有大量具有不確定性的Web 服務可用，手工分析這些服務并合成服務不現實。對于自動組合，首先需要利用匹配算法生成狀態圖，然后利用回溯算法確定具體的組合規劃[3-6].這種組合方法不僅過程復雜，而且如存在一個Web 服務調用異常，整個組合過程失敗。因此，很多關于服務組合的應用和研究工作都側重于半自動方式[7-8]。半自動組合方式的實現，首先需要業務人員建立組合流程模型，然后對模型中各抽象任務自動地綁定調用實例.基于全局優化的服務綁定方法主要有兩類:以整數規劃為代表的窮盡優化方法[1]和以進化算法為代表的近似優化方法[9]。但這兩種方法存在一個共同的缺陷:產生的規劃都是靜態規劃，從而在組合過程中如果出現調用異常，則只能進行重規劃，或者為了提高組合效率而選擇一個次優規劃，或者采取協商機制[10]，這些方法將不可避免地降低組合服務的性能。實際上，Internet 環境下預定義流程的Web 服務選擇問題，是對一個隨機型離散事件系統進行動態尋找最優規劃的過程，而MDP是這類系統比較合適的動態控制方法，同時文獻[11]已經證明其復雜度是P 完全的。因此，本文利用MDP 進行服務組合，該方法可以形式化服務組合過程中的一些不確定性情況(例如:服務調用失敗)，最終產生一個平衡了“風險”和“報酬”的動態最優規劃。

1 基于MDP的動態服務組合

1.1 MDP的基本概念

MDP是動態規劃與馬爾可夫過程相結合的產物，適合于對隨機型離散事件系統進行動態控制，且在對決策問題建模時考慮其隨機性和有序性. 馬爾可夫鏈中沒有考慮不確定性的因素，僅考慮了概率因素。但實際情況中由于系統的并發以及有時無法準確的用概率模型來刻畫系統，需要同時考慮概率和不確定因素。本文采用離散決策時刻，有限狀態馬爾可夫決策模型。

定義1 (馬爾可夫決策過程). 馬爾可夫決策過程是一個五元組 M= (S， Act，P， linit，AP， L)

其中S為有限狀態的集合，Act為動作集合，

P : S ×Act×S → [0， 1]， P為變遷發生概率的函數，對于所有的s∈S， α∈Act，有，

linit : S → [0， 1] 描述了初始分布，有。

AP為原子命題的組合，L:S→2AP是標記函數，表明每個狀態中所滿足的原子命題的集合

1.2 UDDI和BPEL的擴展

盡管現有的UDDI+WSDL+WSFL試圖提供一個商業整合的基礎，但是對服務的精確描述能力有所欠缺，現在有很多研究提出利用Qos的Web服務組合的研究，Web服務的描述模型為S={Function，Qos}，Functon為服務的功能屬性集合，Qos為服務的質量屬性集合。現有的服務描述語言WSDL并沒有提供對Qos的描述機制，所以文獻[12]提出一種擴展的Web服務描述語言EWSDL，可以在其中加入Qos的描述信息，同時也擴展了BPEL，其中也加入了Qos的相關內容。同時考慮到系統的不確定性，系統也需要提供一種機制來自適應的獲取Qos值。

1.3 基于MDP的Web服務組合模型

圖1為服務組合模型。

其中將具有相同或相近Qos屬性的Web服務集中在一起，作為一個Web服務類，Agent選擇滿足規定Qos條件的的服務類進行排列(s1，s2，s)，s1∈C1 s2∈C2 s3∈C3即可得到一個所希望的服務組合。

2 算法及分析

為討論方便，假設服務類的個數為m，每個服務類中服務的個數都為n，則組合模型的解空間大小為nm，這樣一個指數級的計算量對于n，m比較小的情況都會帶來很大的系統負擔[13]，所以窮盡算法通常情況下不可用，有必要尋找更高效率的服務組合算法。文獻[12]提出了利用k臂賭博機技術得到了一種服務組合算法，以文獻[14]中EXP3算法為基礎給出了算法E(α，β)。進一步的考慮，可以考慮利用MDP中的反向迭代算法和前向搜索算法，來更好的進行服務的組合。

參考文獻:

[1] Zeng L Z， Benatallah B， Ngu AHH， et al.QoS-Aware middleware for Web services composition[J]. IEEE Trans.on Software Engineering，2004，30(5):311-327.

[2] Majithia S，Walker D W，Gray W A. A framework for automated service composition in service-oriented architectures[C]//Bussler C.Proc.of the European Semantic Web Symp.2004.Berlin: Springer-Verlag，2004:269-283.

[3] Oh SC，Lee D，Kumara SRT.Web service Planner (WsPr): An effective and scalable Web service Web composition algorithm[J].Int'lJournal of Web Services Research，2007，4(1):1-23.

[4] Ponnekanti S R，Fox A. SWORD: A developer toolkitt for Web service composition[C]//Proc.of the 11th World Wide Web.NewYork: ACM Press，2002:83-107.

[5] Rao J H，Su X M.A survey of automated Web service composition methods[C]//Cardoso J，Sheth A P.Proc.of the 1st Int'l Workshop on Semantic Web Services and Web Process Composition.LNCS 3387，Berlin，Heidelberg: Springer-Verlag，2005:43-54.

[6] Blum A L，Furst M L.Fast planning through planning graph analysis[J].Artificial Intelligence，1997(90):281-300.

[7] Benatallah B，Dumas M，Sheng QZ，Ngu AHH.Declarative composition and peer-to-peer provisioning of dynamic Web services[C]//Agrawal R，Dittrich K，Ngu A H.Proc.of the 18th Int’l Conf.on Data Engineering.San Jose: IEEE Computer Society，2002.297-308.

[8] Zeng L Z， Benatallah B， Dumas M.Quality driven Web service composition[C]//Ellis A，Hagino T.Proc.of the World Wide Web.Budapest: ACM，2003:411-421.

[9] Zhang C W，Su S，Chen J L.Genetic algorithm on Web services selection supporting QoS[J].Chinese Journal of Computers，2006，29(7):1029-1037(in Chinese with English abstract).

[10] Ardagna D，Pernici B.Adaptive service composition in flexible processesp[J].IEEE Trans.on Software Engineering，2007，33(6):369-384.

[11] Doshi P，Goodwin R，Akkiraju R，et al.Dynamic workflow composition using Markov decision processes[J].Int'l Journal of Web Services Research，2005，2(1):1-17.

[12] 陳彥萍，李增智，唐亞哲，等.一種滿足馬爾可夫性質的不完全信息下的Web服務組合方法[J].計算機學報，2006(7):1076-1082.

[13] Jin Hai，Chen Han-Wen，Lu Zhi-Peng，et al.Qos optimizing model and solving for position service in CGSP job manager[J].Chinese Journal of computers，2005，28(4):578-588

[14] Auer P， Cesa-Bianchi N， Freund Y. The adversarial multi-armed bandit problem[C]. Proceeding of the 36th Annual Symposium on Foundations of Computer Science，Los Alamitors，CA，1995:322-331.