基于MDP的動(dòng)態(tài)Web服務(wù)組合

摘要:在面向服務(wù)的環(huán)境下，單個(gè)Web服務(wù)往往不能滿(mǎn)足用戶(hù)的要求，這時(shí)就需將已有的單個(gè)Web 服務(wù)進(jìn)行組合，以便產(chǎn)生滿(mǎn)足用戶(hù)需求的組合服務(wù)。已有的服務(wù)組合方法都很少考慮Web 服務(wù)的隨機(jī)性和Internet 環(huán)境的動(dòng)態(tài)性，從而在服務(wù)選擇過(guò)程中產(chǎn)生的規(guī)劃都是靜態(tài)規(guī)劃，結(jié)果導(dǎo)致在服務(wù)組合時(shí)都以較大概率出現(xiàn)組合失敗。針對(duì)上述問(wèn)題，利用馬爾可夫決策過(guò)程(MDP)，設(shè)計(jì)出利用隨機(jī)QoS作為指標(biāo)的Web 服務(wù)組合算法。

關(guān)鍵詞:Web服務(wù);服務(wù)組合;Qos;MDP

中圖分類(lèi)號(hào):TP311文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):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服務(wù)技術(shù)己從基礎(chǔ)設(shè)施的構(gòu)建與概念推廣階段向大規(guī)模商業(yè)應(yīng)用階段快速發(fā)展。前者主要是在早期的研究基礎(chǔ)上，通過(guò)制定基于XML的SOAP、WSDL，與UDDI等標(biāo)準(zhǔn)化通信協(xié)議與數(shù)據(jù)描述方式解決了服務(wù)定義、接口、服務(wù)查找以及松散耦合異構(gòu)環(huán)境下的遠(yuǎn)程調(diào)用與通信等基礎(chǔ)問(wèn)題;而后者主要是解決在商業(yè)應(yīng)用過(guò)程中所涉及的服務(wù)重用與合成、安全、QoS以及長(zhǎng)事物的管理與調(diào)度等更為復(fù)雜的應(yīng)用問(wèn)題。其中，如何重用己有的服務(wù)，并通過(guò)自動(dòng)化、可管理的方式進(jìn)行合成來(lái)動(dòng)態(tài)生成新的應(yīng)用系統(tǒng)以滿(mǎn)足企業(yè)的動(dòng)態(tài)需求，則成為工業(yè)界與學(xué)術(shù)界共同關(guān)注的問(wèn)題，并且已經(jīng)成為推動(dòng)Web服務(wù)不斷向前發(fā)展的技術(shù)動(dòng)力。

但由于Internet 環(huán)境的開(kāi)放性和動(dòng)態(tài)性以及Web 服務(wù)的隨機(jī)性，導(dǎo)致組件服務(wù)的QoS 具有很強(qiáng)的不確定性，從而影響了服務(wù)組合成功率和組合服務(wù)的質(zhì)量.所以，如何準(zhǔn)確地度量Web 服務(wù)的QoS 以及動(dòng)態(tài)地對(duì)其進(jìn)行自適應(yīng)管理，對(duì)服務(wù)的成功組合有著重要的意義;另一方面，已有的服務(wù)組合方法在規(guī)劃過(guò)程中都假設(shè)Web 服務(wù)具有確定行為，而這個(gè)假設(shè)往往導(dǎo)致服務(wù)組合過(guò)程中出現(xiàn)約束沖突。所以，在考慮真實(shí)環(huán)境的不確定性和動(dòng)態(tài)性的情況下，研究服務(wù)的可靠組合方法有著重要的現(xiàn)實(shí)意義。

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

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

1 基于MDP的動(dòng)態(tài)服務(wù)組合

1.1 MDP的基本概念

MDP是動(dòng)態(tài)規(guī)劃與馬爾可夫過(guò)程相結(jié)合的產(chǎn)物，適合于對(duì)隨機(jī)型離散事件系統(tǒng)進(jìn)行動(dòng)態(tài)控制，且在對(duì)決策問(wèn)題建模時(shí)考慮其隨機(jī)性和有序性. 馬爾可夫鏈中沒(méi)有考慮不確定性的因素，僅考慮了概率因素。但實(shí)際情況中由于系統(tǒng)的并發(fā)以及有時(shí)無(wú)法準(zhǔn)確的用概率模型來(lái)刻畫(huà)系統(tǒng)，需要同時(shí)考慮概率和不確定因素。本文采用離散決策時(shí)刻，有限狀態(tài)馬爾可夫決策模型。

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

其中S為有限狀態(tài)的集合，Act為動(dòng)作集合，

P : S ×Act×S → [0， 1]， P為變遷發(fā)生概率的函數(shù)，對(duì)于所有的s∈S， α∈Act，有，

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

AP為原子命題的組合，L:S→2AP是標(biāo)記函數(shù)，表明每個(gè)狀態(tài)中所滿(mǎn)足的原子命題的集合

1.2 UDDI和BPEL的擴(kuò)展

盡管現(xiàn)有的UDDI+WSDL+WSFL試圖提供一個(gè)商業(yè)整合的基礎(chǔ)，但是對(duì)服務(wù)的精確描述能力有所欠缺，現(xiàn)在有很多研究提出利用Qos的Web服務(wù)組合的研究，Web服務(wù)的描述模型為S={Function，Qos}，F(xiàn)uncton為服務(wù)的功能屬性集合，Qos為服務(wù)的質(zhì)量屬性集合?，F(xiàn)有的服務(wù)描述語(yǔ)言WSDL并沒(méi)有提供對(duì)Qos的描述機(jī)制，所以文獻(xiàn)[12]提出一種擴(kuò)展的Web服務(wù)描述語(yǔ)言EWSDL，可以在其中加入Qos的描述信息，同時(shí)也擴(kuò)展了BPEL，其中也加入了Qos的相關(guān)內(nèi)容。同時(shí)考慮到系統(tǒng)的不確定性，系統(tǒng)也需要提供一種機(jī)制來(lái)自適應(yīng)的獲取Qos值。

1.3 基于MDP的Web服務(wù)組合模型

圖1為服務(wù)組合模型。

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

2 算法及分析

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

參考文獻(xiàn):

[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，F(xiàn)ox 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，F(xiàn)urst 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] 陳彥萍，李增智，唐亞哲，等.一種滿(mǎn)足馬爾可夫性質(zhì)的不完全信息下的Web服務(wù)組合方法[J].計(jì)算機(jī)學(xué)報(bào)，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.