任麗芳 王文劍 許 行

1(山西大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院 太原 030006)2(山西財(cái)經(jīng)大學(xué)應(yīng)用數(shù)學(xué)學(xué)院 太原 030006)(renlf@sxufe.edu.cn)

?

不確定感知的自適應(yīng)云計(jì)算服務(wù)組合

任麗芳1,2王文劍1許 行1

1(山西大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院 太原 030006)2(山西財(cái)經(jīng)大學(xué)應(yīng)用數(shù)學(xué)學(xué)院 太原 030006)(renlf@sxufe.edu.cn)

云計(jì)算服務(wù)組合是從眾多分布在不同云計(jì)算平臺(tái)上的遠(yuǎn)程服務(wù)中選擇合適的組件服務(wù)來(lái)構(gòu)建可伸縮的松耦合的增值應(yīng)用.傳統(tǒng)的服務(wù)組合方法通常將服務(wù)選擇與服務(wù)組合分階段進(jìn)行，由于云計(jì)算環(huán)境的動(dòng)態(tài)性和服務(wù)自身演化的隨機(jī)性，不能保證選擇階段性能最優(yōu)的服務(wù)在組合服務(wù)執(zhí)行階段依然是最優(yōu)的.考慮到云計(jì)算環(huán)境服務(wù)組合的動(dòng)態(tài)性和隨機(jī)性，建立基于部分可觀測(cè)Markov決策過(guò)程(partially observable Markov decision process, POMDP)的服務(wù)組合模型SC_POMDP (service composition based on POMDP)，并設(shè)計(jì)用于模型求解的Q學(xué)習(xí)算法.SC_POMDP模型在組合服務(wù)運(yùn)行中動(dòng)態(tài)地進(jìn)行服務(wù)質(zhì)量(quality of service, QoS)最優(yōu)的組件服務(wù)選擇，且認(rèn)為組合服務(wù)運(yùn)行的環(huán)境狀態(tài)是不確定的，同時(shí)SC_POMDP考慮了組件服務(wù)間的兼容性，可保證服務(wù)組合對(duì)實(shí)際情境的適應(yīng)性.仿真實(shí)驗(yàn)表明，所提出的方法能成功地解決不同規(guī)模的服務(wù)組合問(wèn)題，在出現(xiàn)不同比率的服務(wù)失效時(shí)，SC_POMDP仍然能動(dòng)態(tài)地選擇可用的最優(yōu)組件服務(wù)，保證服務(wù)組合能成功地執(zhí)行.與已有方法相比，SC_POMDP方法所選的服務(wù)有更優(yōu)的響應(yīng)時(shí)間和吞吐量，表明SC_POMDP可有效地提高服務(wù)組合的自適應(yīng)性.

自適應(yīng)服務(wù)組合；云計(jì)算環(huán)境；不確定感知；部分可觀測(cè)Markov決策過(guò)程；Q學(xué)習(xí)算法；服務(wù)質(zhì)量

隨著云計(jì)算技術(shù)的興起，軟件的開(kāi)發(fā)、交付和維護(hù)模式正發(fā)生著巨大的變革.面向服務(wù)的計(jì)算(service oriented computing, SOC)作為一種新興的計(jì)算模式，以服務(wù)作為構(gòu)建軟件應(yīng)用的基本元素，引起學(xué)術(shù)界和工業(yè)界的普遍關(guān)注.Web服務(wù)是具有標(biāo)準(zhǔn)接口描述的可編程模塊，是一種靈活的標(biāo)準(zhǔn)的服務(wù)交付接口技術(shù)，常用于云計(jì)算平臺(tái)服務(wù)實(shí)施中提供各種已經(jīng)實(shí)現(xiàn)的功能或資源.然而單一的服務(wù)所能提供的計(jì)算資源和能力是有限的，為滿(mǎn)足用戶(hù)日益復(fù)雜的需求，需要從眾多的分布在不同的云平臺(tái)上的服務(wù)中，選擇合適的組件服務(wù)，并按照一定的業(yè)務(wù)規(guī)則進(jìn)行組合，構(gòu)建可伸縮的松耦合的組合服務(wù)[1-2].

服務(wù)組合是1個(gè)復(fù)雜而具有挑戰(zhàn)性的工作，在這方面已經(jīng)進(jìn)行了許多的研究.按照自動(dòng)化程度，服務(wù)組合的方式可以分為手動(dòng)、半自動(dòng)和自動(dòng)服務(wù)組合3大類(lèi).隨著可用服務(wù)不斷涌現(xiàn)，手動(dòng)方式對(duì)現(xiàn)有的服務(wù)進(jìn)行分析和組合已經(jīng)變得不可行[3].

通常自動(dòng)組合方式會(huì)將服務(wù)組合任務(wù)轉(zhuǎn)化為1個(gè)經(jīng)典的規(guī)劃問(wèn)題求解[4-7].首先用規(guī)劃語(yǔ)言，如PDDL[4], TRIPS[5]或GOLOG[6]等，對(duì)服務(wù)進(jìn)行形式化描述；然后用人工智能規(guī)劃算法，如分層任務(wù)網(wǎng)絡(luò)(hierarchical task network, HTN)規(guī)劃[7]、Estimated-regression 規(guī)劃[4]等來(lái)求解該規(guī)劃問(wèn)題;最后，將規(guī)劃問(wèn)題的解轉(zhuǎn)變?yōu)樽詣?dòng)的服務(wù)調(diào)用.自動(dòng)服務(wù)組合通常只是尋求滿(mǎn)足用戶(hù)功能需求的組合服務(wù)，而不考慮組合服務(wù)的服務(wù)質(zhì)量(quality of service, QoS)，因此組合服務(wù)的性能難以保證.更重要的是經(jīng)典的規(guī)劃算法一般不考慮系統(tǒng)的動(dòng)態(tài)特性，因此自動(dòng)服務(wù)組合方式一般假定服務(wù)是確定不變的，然而在實(shí)際的服務(wù)組合環(huán)境中，服務(wù)的性能會(huì)受Internet的動(dòng)態(tài)性和云服務(wù)提供組織升級(jí)演化的影響，甚至變得不可用，所以自動(dòng)服務(wù)組合是易于失敗的.

在半自動(dòng)服務(wù)組合中，首先構(gòu)建1個(gè)過(guò)程模型，然后以全局或局部最優(yōu)為目標(biāo)自動(dòng)地為每個(gè)抽象任務(wù)選擇服務(wù)實(shí)例[3].現(xiàn)有的多數(shù)服務(wù)選擇方式都是QoS感知的[8-10]，這種服務(wù)選擇方式比較容易滿(mǎn)足用戶(hù)對(duì)組合服務(wù)性能的要求.還有一些半自動(dòng)服務(wù)組合是基于信任或信譽(yù)管理[11]，或者網(wǎng)頁(yè)排名[12]等.在大多數(shù)這些方法[8-13]中組件服務(wù)的選擇和組合服務(wù)的執(zhí)行是2個(gè)獨(dú)立的階段，很難保證選擇階段具有最優(yōu)性能的服務(wù)在執(zhí)行階段其性能依然是最優(yōu)的，甚至可能出現(xiàn)組件服務(wù)在執(zhí)行階段失效，導(dǎo)致重新啟動(dòng)服務(wù)組合的選擇和執(zhí)行過(guò)程，然而重新規(guī)劃也不能保證新的組合服務(wù)一定有效.

事實(shí)上，由于作為云計(jì)算支撐環(huán)境的Internet是動(dòng)態(tài)的，導(dǎo)致服務(wù)的QoS不斷地變化，如網(wǎng)絡(luò)訪問(wèn)量的增加可能導(dǎo)致服務(wù)的響應(yīng)時(shí)間延長(zhǎng)，網(wǎng)絡(luò)連接失敗直接導(dǎo)致服務(wù)變得不可用等.此外，云計(jì)算提供組織也在不斷地演化.如會(huì)出現(xiàn)一些新的服務(wù)、會(huì)有某些服務(wù)消失、也會(huì)有某些服務(wù)發(fā)生升級(jí)等.因此這種云計(jì)算環(huán)境中具有預(yù)定義過(guò)程模型的QoS最優(yōu)的服務(wù)組合問(wèn)題，可以看作隨機(jī)環(huán)境中多階段決策過(guò)程優(yōu)化問(wèn)題.Markov決策過(guò)程(Markov decision process, MDP)是動(dòng)態(tài)規(guī)劃與Markov過(guò)程相結(jié)合的產(chǎn)物，在對(duì)決策問(wèn)題建模時(shí)考慮其隨機(jī)性和有序性，適合于對(duì)隨機(jī)環(huán)境中多階段決策過(guò)程進(jìn)行優(yōu)化控制.然而MDP模型假定對(duì)系統(tǒng)的運(yùn)行狀態(tài)是完全了解的，在實(shí)際的服務(wù)組合問(wèn)題中這個(gè)假定很難成立.部分可觀測(cè)Markov決策過(guò)程(partially observable Markov decision process, POMDP)模型是將MDP模型應(yīng)用于更一般環(huán)境中的擴(kuò)展，適用于建模不確定環(huán)境中的決策過(guò)程，模擬決策者和系統(tǒng)在信息不完全確定的情況下交互，并進(jìn)行決策的過(guò)程.POMDP在機(jī)器人導(dǎo)航、移動(dòng)目標(biāo)俘獲等領(lǐng)域已有廣泛的應(yīng)用[14].云計(jì)算服務(wù)組合研究在云計(jì)算的動(dòng)態(tài)環(huán)境中，服務(wù)組合的構(gòu)建者對(duì)服務(wù)組合所處的云計(jì)算環(huán)境以及服務(wù)組合系統(tǒng)的運(yùn)行狀態(tài)不完全了解的情況下，對(duì)最優(yōu)服務(wù)組合進(jìn)行決策.這種動(dòng)態(tài)的不確定環(huán)境中的決策問(wèn)題適合用POMDP進(jìn)行建模，因此本文基于POMDP建立服務(wù)組合模型SC_POMDP(service composition based on POMDP),該模型不僅能適應(yīng)云計(jì)算環(huán)境的動(dòng)態(tài)性和服務(wù)演化的隨機(jī)性，而且能建模服務(wù)組合運(yùn)行中系統(tǒng)狀態(tài)的不確定性，所以SC_POMDP模型是自適應(yīng)的.然而POMDP模型的復(fù)雜性使其最優(yōu)策略的求解非常困難，現(xiàn)有的求解算法只能對(duì)較小規(guī)模的問(wèn)題進(jìn)行精確求解[15].Q學(xué)習(xí)算法是一種增強(qiáng)學(xué)習(xí)技術(shù)，可以通過(guò)試錯(cuò)方法學(xué)習(xí)最優(yōu)交互策略，使系統(tǒng)從環(huán)境獲得最高回報(bào)[16]，因此本文采用Q學(xué)習(xí)算法對(duì)SC_POMDP模型進(jìn)行求解.

1 相關(guān)工作

云計(jì)算環(huán)境的動(dòng)態(tài)性加之服務(wù)的自治性，使得組合服務(wù)的性能難以保證，因此構(gòu)建適應(yīng)這種不確定環(huán)境的服務(wù)組合成為了1個(gè)挑戰(zhàn)，引起國(guó)內(nèi)外學(xué)者對(duì)自適應(yīng)服務(wù)組合方法進(jìn)行了廣泛的研究[17-21].

范小芹等人[17]考慮到組件服務(wù)QoS的不確定性對(duì)組合服務(wù)成功率的影響，用隨機(jī)變量的均值和方差來(lái)度量Web服務(wù)的QoS指標(biāo)，然后基于MDP建立服務(wù)組合模型，提高了服務(wù)組合的成功率.然而，雖然均值和方差能反映QoS指標(biāo)的平均水平及其波動(dòng)程度，但是實(shí)際中并不能保證組合服務(wù)運(yùn)行中組件服務(wù)的QoS指標(biāo)真實(shí)值和QoS指標(biāo)理論值保持一致.因此文獻(xiàn)[17]以組件服務(wù)QoS指標(biāo)的理論分布作為服務(wù)選擇的標(biāo)準(zhǔn)，在一定程度上提高了服務(wù)組合的成功率，但是該方法對(duì)服務(wù)組合運(yùn)行環(huán)境的不確定性適應(yīng)明顯不足.

Wang等人[18]考慮了Web服務(wù)演化的不確定性，設(shè)計(jì)了基于MDP的服務(wù)組合模型，在組合服務(wù)運(yùn)行時(shí)進(jìn)行具體服務(wù)的選擇，有效地減少了服務(wù)選擇階段與組合服務(wù)運(yùn)行階段之間服務(wù)演化所帶來(lái)的影響.然而該方法在進(jìn)行服務(wù)選擇時(shí)沒(méi)有考慮服務(wù)組合系統(tǒng)所處的運(yùn)行環(huán)境的不確定性，事實(shí)上不同的運(yùn)行環(huán)境中組件服務(wù)的實(shí)際性能有很大的差異.文獻(xiàn)[18]的方法提升了服務(wù)組合對(duì)服務(wù)演化的適應(yīng)性，但是沒(méi)有考慮服務(wù)組合對(duì)運(yùn)行環(huán)境的適應(yīng)性，因此該方法能保證組合服務(wù)的成功執(zhí)行，但是并不能保證組合服務(wù)的性能最優(yōu).

Yang等人[19]建立了云間服務(wù)組合中相繼任務(wù)的服務(wù)對(duì)集合，并定義了服務(wù)對(duì)效用的評(píng)價(jià)函數(shù).該方法基于MDP為服務(wù)組合建立模型，選擇效用函數(shù)值最優(yōu)的服務(wù)對(duì)形成服務(wù)組合.該模型在服務(wù)對(duì)的效用值計(jì)算中，認(rèn)為組件服務(wù)的QoS屬性值是確定的，而實(shí)際中組件服務(wù)的QoS屬性值波動(dòng)較大，所以該服務(wù)組合方法的適應(yīng)能力有很大的局限.

Ardagna等人在文獻(xiàn)[20]將服務(wù)組合建模為1個(gè)混合整數(shù)規(guī)劃問(wèn)題，并以環(huán)剝技術(shù)加速優(yōu)化過(guò)程，利用協(xié)商機(jī)制降低服務(wù)過(guò)程中由于用戶(hù)約束不滿(mǎn)足導(dǎo)致的失敗率，體現(xiàn)了該方法對(duì)用戶(hù)約束的自適應(yīng)性，目標(biāo)是尋找滿(mǎn)足用戶(hù)約束的可行的組合服務(wù).然而該方法以QoS屬性的理論分布值作為實(shí)際的QoS屬性值，沒(méi)有考慮組合服務(wù)對(duì)不確定環(huán)境的適應(yīng)性.

文獻(xiàn)[12]利用公共注冊(cè)機(jī)構(gòu)的動(dòng)態(tài)Web服務(wù)定義語(yǔ)言(Web Service Definition Language, WSDL)信息近似服務(wù)的瞬時(shí)狀態(tài)，以瞬間快照上的鏈接分析代表服務(wù)在該時(shí)刻受不同用戶(hù)歡迎的程度，體現(xiàn)該方法對(duì)組件服務(wù)信譽(yù)度的適應(yīng)性.該方法把組件服務(wù)的選擇形式化為高被引服務(wù)的選擇.由于服務(wù)QoS屬性間的不一致性，高被引服務(wù)的高訪問(wèn)量會(huì)引起響應(yīng)時(shí)間等其他QoS屬性性能的降低，所以該方法的適應(yīng)性考慮不全面.

Klein等人在文獻(xiàn)[21]將QoS屬性區(qū)分為服務(wù)自身決定的屬性和與網(wǎng)絡(luò)相關(guān)的屬性，提出了網(wǎng)絡(luò)感知的方法，用2種不同的方法計(jì)算2類(lèi)不同的QoS屬性值.對(duì)網(wǎng)絡(luò)相關(guān)的QoS屬性，根據(jù)相繼服務(wù)所在服務(wù)器的網(wǎng)絡(luò)距離計(jì)算QoS屬性值.在此基礎(chǔ)上，該文設(shè)計(jì)了網(wǎng)絡(luò)感知的遺傳算法，求解最優(yōu)服務(wù)組合，該方法的適應(yīng)性體現(xiàn)在根據(jù)一定的經(jīng)驗(yàn)概率選擇執(zhí)行遺傳操作，然而該方法中服務(wù)選擇與組合服務(wù)的執(zhí)行分階段進(jìn)行，沒(méi)有考慮對(duì)組件服務(wù)演化的適應(yīng)性，不能保證服務(wù)組合的成功執(zhí)行.

不同于已有的服務(wù)組合方法，本文針對(duì)云計(jì)算環(huán)境中，服務(wù)性能受Internet的動(dòng)態(tài)性以及服務(wù)自身演化隨機(jī)性的影響，且系統(tǒng)對(duì)組合服務(wù)運(yùn)行環(huán)境狀態(tài)不完全了解，這種更一般情況的服務(wù)組合問(wèn)題展開(kāi)研究.同時(shí)本文考慮了組件服務(wù)之間的兼容情況，建立了基于POMDP的服務(wù)組合模型SC_POMDP，并設(shè)計(jì)了模型的求解算法，為解決在不確定的云計(jì)算環(huán)境中自適應(yīng)地進(jìn)行性能最優(yōu)的服務(wù)組合問(wèn)題提供了一種可行方法.

2 云計(jì)算服務(wù)組合

本節(jié)給出服務(wù)組合問(wèn)題中的一些相關(guān)概念，并給出原子服務(wù)、組件服務(wù)以及組合服務(wù)的形式化描述.同時(shí)，為了說(shuō)明云計(jì)算環(huán)境服務(wù)組合過(guò)程及其特征，本節(jié)設(shè)計(jì)了1個(gè)云計(jì)算服務(wù)組合的場(chǎng)景.

2.1 相關(guān)概念

定義1. 原子服務(wù)(atomic service)是1個(gè)獨(dú)立的、功能完整的可以通過(guò)網(wǎng)絡(luò)進(jìn)行發(fā)布、定位以及訪問(wèn)的最小資源單位.1個(gè)原子服務(wù)可以形式化為1個(gè)三元組(Nid,Cfun,Mqos)，其中：

Nid是原子服務(wù)的標(biāo)識(shí)，通過(guò)Nid可以唯一地確定1個(gè)原子服務(wù)；

Cfun代表原子服務(wù)的功能分類(lèi)號(hào)，功能相同的原子服務(wù)有相同的Cfun.能完成某個(gè)特定任務(wù)的服務(wù)具有相同的Cfun，這些服務(wù)組成1個(gè)集合，稱(chēng)為該任務(wù)的候選服務(wù)集(set of candidate services)；

Mqos代表原子服務(wù)在被調(diào)用歷史中表現(xiàn)的服務(wù)質(zhì)量，是1個(gè)矩陣，矩陣的行數(shù)是該服務(wù)被調(diào)用的次數(shù)，列數(shù)是所考察的QoS屬性(如響應(yīng)時(shí)間、價(jià)格、可用性等)的個(gè)數(shù).其中行i(mi 1，mi 2，…，mi n)代表該服務(wù)在第i次被調(diào)用時(shí)各QoS屬性的值.

Fig. 1 An example graph of atomic service, component service and composite service.圖1 原子服務(wù)、組件服務(wù)與組合服務(wù)示例圖

2個(gè)或多個(gè)原子服務(wù)可以組合產(chǎn)生1個(gè)新的服務(wù)，這個(gè)新的服務(wù)可以執(zhí)行更復(fù)雜的其中任何1個(gè)原子服務(wù)無(wú)法獨(dú)立完成的任務(wù).這個(gè)包含多個(gè)原子服務(wù)的新服務(wù)是1個(gè)組合服務(wù).構(gòu)造組合服務(wù)的過(guò)程可以迭代進(jìn)行，也就是說(shuō)，組合服務(wù)可以被用作組成另1個(gè)更復(fù)雜組合服務(wù)的組件服務(wù).圖1是原子服務(wù)、組件服務(wù)與組合服務(wù)關(guān)系的1個(gè)示例.圖1中，大虛線框內(nèi)的是1個(gè)組合服務(wù)，小虛線框內(nèi)的是1個(gè)組件服務(wù)，每個(gè)圓圈代表1個(gè)原子服務(wù).

定義2. 組件服務(wù)(component service)本質(zhì)上是1個(gè)較小規(guī)模的組合服務(wù),組件服務(wù)能夠?qū)崿F(xiàn)1個(gè)小規(guī)模的完整業(yè)務(wù)解決方案，所以經(jīng)常作為1個(gè)整體.組件服務(wù)可以形式化地定義為1個(gè)四元組(Nid,Cfun,Mqos,Vmemb)，其中：

Nid，Cfun和Mqos的形式及含義與原子服務(wù)定義中相同；

Vmemb是依序構(gòu)成這個(gè)組件服務(wù)的所有原子服務(wù)的Nid組成的序列.

服務(wù)的強(qiáng)大之處就在于組件服務(wù)能動(dòng)態(tài)地進(jìn)行集成來(lái)執(zhí)行新的更復(fù)雜的任務(wù)，這個(gè)過(guò)程就是服務(wù)組合(service composition).

定義3. 組合服務(wù)(composite service).為滿(mǎn)足用戶(hù)需求，將已有的具有不同功能的組件服務(wù)按照一定的業(yè)務(wù)邏輯進(jìn)行集成，形成可伸縮的松耦合的增值應(yīng)用.其中的組件服務(wù)，包括由1個(gè)原子服務(wù)組成的組件服務(wù)，即原子級(jí)的組件服務(wù).這樣，組合服務(wù)可以形式化地表示為1個(gè)序列(ws1，ws2，…，wsn)，其中wsi(i=1,2,…,n)為依序組成組合服務(wù)的所有組件服務(wù)的Nid，n為組合服務(wù)中組件服務(wù)的個(gè)數(shù).

由于具有循環(huán)、分支和并行結(jié)構(gòu)的服務(wù)組合都能夠轉(zhuǎn)化為一種順序結(jié)構(gòu)[22]，所以本文主要解決業(yè)務(wù)邏輯的過(guò)程模型為順序結(jié)構(gòu)的服務(wù)組合問(wèn)題.

2.2 云計(jì)算服務(wù)組合的1個(gè)場(chǎng)景

為了說(shuō)明服務(wù)組合過(guò)程及其在云計(jì)算環(huán)境的特征，考慮如下的場(chǎng)景：某用戶(hù)捕獲1個(gè)物體在運(yùn)動(dòng)時(shí)的1組多視角照片，希望根據(jù)這組二維圖像利用用戶(hù)設(shè)計(jì)的重建算法重建該物體的三維模型，并將重建的三維模型進(jìn)行存儲(chǔ).由于拍攝時(shí)物體在運(yùn)動(dòng)，照片可能比較模糊，所以在三維重建之前需要進(jìn)行二維圖像復(fù)原，以提高二維圖像質(zhì)量.由于本地資源有限，用戶(hù)希望通過(guò)云計(jì)算環(huán)境所提供的服務(wù)來(lái)完成這個(gè)任務(wù).為此可以首先利用云計(jì)算環(huán)境中的模糊圖像復(fù)原服務(wù)將模糊的二維圖像進(jìn)行復(fù)原，然后利用云計(jì)算平臺(tái)提供的強(qiáng)大的計(jì)算能力運(yùn)行用戶(hù)設(shè)計(jì)的三維重建算法，得到重建的三維模型，最后將三維模型在云空間存儲(chǔ).圖2是對(duì)該場(chǎng)景服務(wù)組合的描述.

Fig. 2 A scenario of cloud services composition.圖2 云計(jì)算環(huán)境服務(wù)組合場(chǎng)景

顯然為滿(mǎn)足用戶(hù)的需求需要對(duì)現(xiàn)有的服務(wù)進(jìn)行組合.用戶(hù)的需求可以分解為3個(gè)任務(wù)：圖像復(fù)原任務(wù)t1、三維重建計(jì)算任務(wù)t2、云存儲(chǔ)任務(wù)t3，如圖2所示.在Internet中，存在許多不同的云計(jì)算服務(wù)提供商，為簡(jiǎn)單起見(jiàn)，本文在圖2所示的場(chǎng)景中假設(shè)所涉及的服務(wù)由圖中所示的4個(gè)云提供，每個(gè)云提供商提供許多不同的原子服務(wù)，在圖中以小實(shí)心圓表示.經(jīng)過(guò)在所有的云上進(jìn)行服務(wù)發(fā)現(xiàn)，每個(gè)任務(wù)都可以由幾個(gè)不同的服務(wù)獨(dú)立地完成，圖2中以wsi j表示可以完成任務(wù)ti的第j個(gè)候選服務(wù)，也是構(gòu)成目標(biāo)組合服務(wù)的可用組件服務(wù).候選服務(wù)的次序只是區(qū)分同一候選服務(wù)集中不同的服務(wù)，這些候選服務(wù)可能分布在相同或不同的云上.

完成相同任務(wù)的不同服務(wù)組成該任務(wù)的候選服務(wù)集.在圖2所示的場(chǎng)景中，任務(wù)t1,t2,t3的候選服務(wù)集分別為

C1={ws11,ws12,ws13},

C2={ws21,ws22,ws23,ws24,ws25},

C3={ws31,ws32,ws33}.

服務(wù)之間由于語(yǔ)法、語(yǔ)義或行為等其他原因，兼容情況(服務(wù)間的兼容性判定不在本文研究范圍，故不做過(guò)多的解釋)如圖3所示:

Fig. 3 The compatibility of candidate services.圖3 候選服務(wù)之間的兼容情況

其中C1,C2,C3分別為3個(gè)任務(wù)t1,t2,t3的候選服務(wù)集，每個(gè)箭頭所指向的是下一個(gè)任務(wù)的候選服務(wù)集中能與該服務(wù)兼容的服務(wù).本文用Rtrs(ws)表示在下一個(gè)任務(wù)的候選服務(wù)集中與服務(wù)ws兼容的候選服務(wù)子集.因此，圖3中每1條由箭頭連接的從C1集合出發(fā)，經(jīng)過(guò)C2集合，到達(dá)C3集合的路徑，即為一種可行的組合方案，如(ws11，ws21，ws31),(ws12，ws23，ws32),(ws13，ws22，ws31)等分別為一種可行的組合服務(wù).這樣，服務(wù)組合問(wèn)題就是依照一定的策略，依次從每個(gè)任務(wù)的候選服務(wù)集中選擇與前一任務(wù)所選組件服務(wù)兼容的最優(yōu)服務(wù)完成該任務(wù)，進(jìn)而完成復(fù)合任務(wù).按照這種組合方式，圖2所示的場(chǎng)景中選擇執(zhí)行的組合服務(wù)為(ws12，ws24，ws31).

考慮到用戶(hù)的滿(mǎn)意度，應(yīng)該選擇使組合服務(wù)性能最優(yōu)的服務(wù).然而由于云計(jì)算環(huán)境的動(dòng)態(tài)性以及服務(wù)演化的隨機(jī)性，服務(wù)的QoS在不斷變化，有時(shí)甚至?xí)霈F(xiàn)某個(gè)服務(wù)失效的情況.如何在這種動(dòng)態(tài)環(huán)境中為每個(gè)任務(wù)選擇服務(wù)使當(dāng)前組合服務(wù)的性能最優(yōu)是本文研究的目的.自適應(yīng)云計(jì)算服務(wù)組合旨在感知組合服務(wù)執(zhí)行的網(wǎng)絡(luò)環(huán)境，選擇適應(yīng)該環(huán)境的組件服務(wù)，同時(shí)若被選擇的組件服務(wù)由于演化升級(jí)等原因發(fā)生失效時(shí)，可以從候選服務(wù)集中重新選擇適應(yīng)性較高的服務(wù)替換失效的組件服務(wù).

3 自適應(yīng)服務(wù)組合模型SC_POMDP

本節(jié)利用第2節(jié)定義的組件服務(wù)與組合服務(wù)，建立服務(wù)組合模型SC_POMDP，給出SC_POMDP模型中服務(wù)的選擇機(jī)制，并設(shè)計(jì)該模型求解的Q學(xué)習(xí)算法.

3.1 建立服務(wù)組合模型SC_POMDP

在POMDP模型中，決策者周期地或連續(xù)地觀察隨機(jī)動(dòng)態(tài)系統(tǒng)，在決策時(shí)刻根據(jù)觀察到的系統(tǒng)所處的狀態(tài)分布以及所采取的策略從可用的行動(dòng)集合中選擇1個(gè)動(dòng)作.POMDP系統(tǒng)下一步的狀態(tài)是隨機(jī)的，并且其狀態(tài)轉(zhuǎn)移概率具有無(wú)后效性，即下一個(gè)決策只依賴(lài)于系統(tǒng)當(dāng)前的狀態(tài)，與歷史狀態(tài)無(wú)關(guān).決策者根據(jù)新的觀察判斷系統(tǒng)的狀態(tài)分布，做出新的決策，如此反復(fù)地進(jìn)行[14].云計(jì)算環(huán)境的服務(wù)組合，依照業(yè)務(wù)邏輯所定義的過(guò)程模型，以組合服務(wù)性能最優(yōu)為目標(biāo)，根據(jù)對(duì)系統(tǒng)所處狀態(tài)分布的判斷，從每個(gè)任務(wù)的候選服務(wù)集中選擇當(dāng)前運(yùn)行狀態(tài)下性能最優(yōu)的組件服務(wù)，執(zhí)行該服務(wù)引起系統(tǒng)的狀態(tài)分布發(fā)生改變，且下一個(gè)服務(wù)的選擇只與系統(tǒng)的當(dāng)前狀態(tài)有關(guān)，與歷史狀態(tài)無(wú)關(guān).因此本文采用POMDP建模云計(jì)算環(huán)境的服務(wù)組合，主要步驟如下：

Step1. 根據(jù)用戶(hù)需求，建立代表服務(wù)組合業(yè)務(wù)邏輯的任務(wù)流模板；

Step2. 為模板中每個(gè)任務(wù)聚集可用候選服務(wù)集，并建立服務(wù)間的兼容關(guān)系；

Step3. 建立服務(wù)組合模型SC_POMDP；

Step4. 利用Q學(xué)習(xí)算法對(duì)每個(gè)服務(wù)的歷史運(yùn)行QoS數(shù)據(jù)進(jìn)行學(xué)習(xí)，得出代表每個(gè)任務(wù)的各候選服務(wù)在不同系統(tǒng)狀態(tài)的QoS性能的矩陣Q；

Step5. 根據(jù)系統(tǒng)實(shí)時(shí)運(yùn)行狀態(tài)分布以及矩陣Q，并結(jié)合服務(wù)之間的兼容性，選擇在當(dāng)前狀態(tài)使組合服務(wù)有最大累計(jì)回報(bào)值的可用組件服務(wù)；

Step6. 重復(fù)Step5直到每個(gè)任務(wù)都完成.

其中，步驟Step3建立的服務(wù)組合模型定義如下：

定義4. 基于POMDP的服務(wù)組合模型SC_POMDP，該模型可以形式化為1個(gè)六元組(S,A,T,Z,O,R), 其中：

1)S為狀態(tài)集合，S={s},其中任意1個(gè)狀態(tài)s=(t,q)是1個(gè)二元組,t表示正在執(zhí)行的任務(wù)的序號(hào)；q表示當(dāng)前組合服務(wù)運(yùn)行所處的QoS等級(jí)狀態(tài)，q的可能取值為集合Qqos={A,B,C,D}中的元素.其中A表示服務(wù)質(zhì)量為優(yōu)；B表示服務(wù)質(zhì)量中等；C表示服務(wù)質(zhì)量較差；D表示服務(wù)失敗，即服務(wù)沒(méi)有正確執(zhí)行.如s=(3,B)，表示組合服務(wù)正在運(yùn)行任務(wù)3，且系統(tǒng)所處的QoS狀態(tài)為B.

3)T(s,ws,s′)是轉(zhuǎn)移概率函數(shù)，表示組合服務(wù)從狀態(tài)s調(diào)用服務(wù)ws，使組合服務(wù)的狀態(tài)轉(zhuǎn)移到s′的概率.設(shè)當(dāng)前狀態(tài)為s=(ti,q), 其中i=1,2,…,n，若選擇的組件服務(wù)ws執(zhí)行失敗，即任務(wù)ti沒(méi)有完成，則s′=(ti,D)；若組件服務(wù)ws執(zhí)行成功，則s′=(ti+1,q′)，q′為組合服務(wù)的實(shí)際運(yùn)行狀態(tài)，可能為A,B或C.

4)Z={z|z=(z1，z2，…，zm)}是觀測(cè)值集合，其中,z是1個(gè)向量，代表1次觀測(cè)，每個(gè)分量zi(i=1,2,…,m)代表組件服務(wù)1次執(zhí)行中觀測(cè)到的1個(gè)QoS屬性值，可能是服務(wù)的價(jià)格、響應(yīng)時(shí)間或吞吐量等.

5)O(ws,s′,z)是觀測(cè)函數(shù)，表示調(diào)用服務(wù)ws后狀態(tài)轉(zhuǎn)移到s′時(shí)觀測(cè)到z的概率.本文根據(jù)服務(wù)執(zhí)行歷史數(shù)據(jù)中QoS值和當(dāng)前服務(wù)運(yùn)行的觀測(cè)值，利用Bayes公式進(jìn)行計(jì)算.

6)R(s′,s,ws)是回報(bào)函數(shù)，表示在調(diào)用服務(wù)ws后系統(tǒng)從狀態(tài)s轉(zhuǎn)移到狀態(tài)s′所得的回報(bào)值.r=R(s′,s,ws)是1個(gè)實(shí)值函數(shù)，當(dāng)r>0時(shí)表示獎(jiǎng)勵(lì),r<0時(shí)表示懲罰.服務(wù)ws的執(zhí)行使組合服務(wù)的運(yùn)行狀態(tài)轉(zhuǎn)移到的QoS等級(jí)越高，則回報(bào)值r越大;否則回報(bào)值r越小.服務(wù)組合的目標(biāo)是選擇最優(yōu)組件服務(wù)使組合服務(wù)的累計(jì)回報(bào)值最高.

不同于已有的基于MDP模型的服務(wù)組合，在SC_POMDP模型中設(shè)置了觀測(cè)集合與觀測(cè)函數(shù)，根據(jù)觀測(cè)集合Z中的元素z與觀測(cè)函數(shù)O，推斷系統(tǒng)處于某個(gè)狀態(tài)s概率.這樣做能更真實(shí)地反映在服務(wù)組合過(guò)程中組件服務(wù)執(zhí)行后組合服務(wù)所處狀態(tài)的多種可能狀況，在選擇下一組件服務(wù)時(shí)，對(duì)系統(tǒng)所處的狀態(tài)判斷更加準(zhǔn)確.

3.2 SC_POMDP模型中的服務(wù)選擇

SC_POMDP中，執(zhí)行服務(wù)ws，引起系統(tǒng)狀態(tài)s轉(zhuǎn)移，決策者根據(jù)觀察z更新信任向量b，計(jì)算回報(bào)rws，并進(jìn)行下一動(dòng)作的決策，如此反復(fù)，直到組合服務(wù)中的所有任務(wù)依次成功執(zhí)行.

由于當(dāng)前系統(tǒng)以概率b(q)處于狀態(tài)q，選擇服務(wù)ws向下一狀態(tài)為s′∈S轉(zhuǎn)移的概率為T(mén)(s,ws,s′)，并以O(shè)(ws,s′,z)觀察到z，所以能觀察到z的總概率為

(1)

當(dāng)收到新的觀察后，就要更新信任狀態(tài)，根據(jù)Bayes定理，對(duì)下一狀態(tài)處于q′的信任為

(2)

從信任狀態(tài)b(q)調(diào)用服務(wù)ws可得回報(bào)的期望值為

(3)

POMDP模型中，策略是從信任空間到動(dòng)作空間的映射.決策過(guò)程即是在策略的指導(dǎo)下，根據(jù)對(duì)系統(tǒng)所處狀態(tài)的信任函數(shù)，最大化期望回報(bào)值的過(guò)程.如果存在策略π*，對(duì)于信任狀態(tài)b(q)，采用策略π*獲得的回報(bào)值大于采用其他任何策略π所獲得的回報(bào)，則稱(chēng)π*為最優(yōu)策略，其對(duì)應(yīng)的值函數(shù)V*為最優(yōu)值函數(shù).

考慮SC_POMDP中所有可能的信任狀態(tài)更新和觀測(cè)值，得遞歸方程：

(4)

(5)

其中，rw s為執(zhí)行服務(wù)ws所得的即時(shí)回報(bào);pz是在執(zhí)行第ti個(gè)任務(wù)時(shí)觀察到z的概率;γ(0≤γ≤1)是折扣因子，體現(xiàn)未來(lái)的回報(bào)相對(duì)近期的回報(bào)權(quán)重要低.若γ=1，表示沒(méi)有折扣，未來(lái)的回報(bào)與當(dāng)前回報(bào)權(quán)重相等；若γ=0，表示只考慮即時(shí)回報(bào)，未來(lái)回報(bào)被忽略.

SC_POMDP模型研究的目標(biāo)就是在服務(wù)組合運(yùn)行中，根據(jù)對(duì)系統(tǒng)所處狀態(tài)的判斷，從候選服務(wù)集中選擇使式(4)取最大值的組件服務(wù)，所選擇的組件服務(wù)依次組成的組合服務(wù)即為服務(wù)組合問(wèn)題的最優(yōu)策略.

3.3 求解SC_POMDP模型的Q學(xué)習(xí)算法

理論上，將服務(wù)組合問(wèn)題建模為SC_POMDP后，系統(tǒng)可以動(dòng)態(tài)地選擇最優(yōu)策略，服務(wù)組合以實(shí)時(shí)最優(yōu)的結(jié)果滿(mǎn)足用戶(hù)的需求.然而在實(shí)踐中，由于POMDP模型的精確求解已被證明是PSPACE完全的[15]，加之云計(jì)算環(huán)境中組件服務(wù)QoS的動(dòng)態(tài)性，使其最優(yōu)策略的求解非常困難.因此，我們采用學(xué)習(xí)的方法來(lái)求解最優(yōu)策略.Q學(xué)習(xí)是一種增強(qiáng)學(xué)習(xí)方法，通過(guò)動(dòng)作執(zhí)行結(jié)果的回報(bào)值，強(qiáng)化使系統(tǒng)狀態(tài)更好地動(dòng)作[16].該算法需要從動(dòng)作的多次執(zhí)行中學(xué)習(xí)，然而由于組件服務(wù)大多是商業(yè)應(yīng)用，在服務(wù)組合執(zhí)行過(guò)程中不可能在選擇服務(wù)前多次調(diào)用候選服務(wù)以測(cè)試其性能，因此我們保存服務(wù)調(diào)用歷史中服務(wù)執(zhí)行的QoS數(shù)據(jù)，用于Q學(xué)習(xí)算法求解SC_POMDP模型時(shí)對(duì)矩陣Q的學(xué)習(xí).SC_POMDP模型的Q學(xué)習(xí)算法如下.

算法1. 求解SC_POMDP的Q學(xué)習(xí)算法.

輸入：任務(wù)數(shù)n、候選服務(wù)集A、學(xué)習(xí)率參數(shù)α、折扣因子γ；

輸出：性能矩陣Q.

① 初始化矩陣:Q←zeros(3n,m);

② whileQ沒(méi)有達(dá)到收斂 do

③ 初始化任務(wù)序號(hào)：t←1;

④ 初始化信任向量:b←(1,0,0,0);

⑤ whilet≤ndo

⑥ 隨機(jī)選擇A(t)中服務(wù)ws;

⑦ 執(zhí)行服務(wù)ws;

⑧ 觀測(cè)到響應(yīng)時(shí)間tr和吞吐量tp;

⑨ 計(jì)算信任向量b′;

⑩ 計(jì)算回報(bào)值r;

4 仿真實(shí)驗(yàn)

為檢驗(yàn)所提出的服務(wù)組合方法的性能，本文的實(shí)驗(yàn)分3部分：1)2.2節(jié)場(chǎng)景中的服務(wù)組合問(wèn)題求解，以驗(yàn)證模型及其求解算法的正確性；2)在真實(shí)數(shù)據(jù)集上進(jìn)行測(cè)試，以驗(yàn)證本文所提出的方法在實(shí)際的較大規(guī)模的服務(wù)組合問(wèn)題上的性能；3)對(duì)模型適應(yīng)性進(jìn)行測(cè)試，分別在實(shí)例問(wèn)題和實(shí)際數(shù)據(jù)集中出現(xiàn)服務(wù)失效的情況下對(duì)SC_POMDP模型的適應(yīng)性進(jìn)行驗(yàn)證，并與2個(gè)有代表性的方法進(jìn)行適應(yīng)性比較.

4.1 正確性驗(yàn)證

首先為2.2節(jié)的場(chǎng)景建立SC_POMDP模型.為簡(jiǎn)單起見(jiàn)，設(shè)服務(wù)的可觀察信息只有響應(yīng)時(shí)間tr，各候選服務(wù)(本例共11個(gè))的歷史觀測(cè)響應(yīng)時(shí)間的數(shù)據(jù)(本例中服務(wù)的歷史數(shù)據(jù)最多有7次記錄)構(gòu)成7×11的矩陣Tresp如下所示，其中數(shù)據(jù)單位為s.Tresp中每列代表1個(gè)服務(wù)，每行代表1次調(diào)用，如Tresp(i,j)表示第j個(gè)服務(wù)在第i次調(diào)用時(shí)的響應(yīng)時(shí)間.其中，Tresp(i,j)=NaN表示第j個(gè)服務(wù)調(diào)用次數(shù)不足i次，所以Tresp(i,j)未知.

設(shè)最大可接受的響應(yīng)時(shí)間為5 s，服務(wù)的最快響應(yīng)時(shí)間為0.1 s，所以利用

Tnorm=(5-Treps)

(6)

對(duì)矩陣Tresp進(jìn)行歸一化，得矩陣Tnorm.Tresp中元素值為-1時(shí)，表示服務(wù)失敗，不參與歸一化處理，在Tnorm矩陣中保持原值-1.對(duì)Tnorm中元素，若Tnorm(i,j)≥0.95,則對(duì)應(yīng)的響應(yīng)時(shí)間等級(jí)Trank(i,j)=1；若0.90≤Tnorm(i,j)<0.95,則Trank(i,j)=2；若0.85≤Tnorm(i,j)<0.90,則Trank(i,j)=3；若Tnorm(i,j)=-1，則Trank(i,j)=4.可得如下所示的響應(yīng)時(shí)間等級(jí)矩陣Trank.

設(shè)矩陣Qrank為服務(wù)歷次運(yùn)行后經(jīng)計(jì)算得出的綜合QoS等級(jí)(可能由服務(wù)組合代理機(jī)構(gòu)根據(jù)服務(wù)調(diào)用中各QoS屬性值進(jìn)行綜合計(jì)算得出，也可能由用戶(hù)反饋給出)，代表對(duì)服務(wù)執(zhí)行的QoS綜合評(píng)價(jià).其中矩陣元素A,B,C,D分別表示服務(wù)執(zhí)行的QoS等級(jí)，NaN表示無(wú)調(diào)用記錄.

矩陣Ctrs中元素Ctrs(i,j)=1，表示第i行的服務(wù)與下一個(gè)任務(wù)的第j個(gè)候選服務(wù)兼容，否則，Ctrs(i,j)=0，表示第i行的服務(wù)與下一個(gè)任務(wù)的第j個(gè)候選服務(wù)不兼容.如第6行(0，1，1，0，0，0)表示ws23與下一任務(wù)的第2和第3個(gè)服務(wù)(ws32和ws33)兼容，與其他服務(wù)(ws31,ws34,ws35)都不兼容,即Rtrs(ws23)={ws32,ws33}.最后1個(gè)任務(wù)的候選服務(wù)集中服務(wù)不再調(diào)用其他服務(wù)，所以相應(yīng)行的元素全為0.

各任務(wù)調(diào)用相應(yīng)的候選集中的服務(wù)，回報(bào)值的計(jì)算可以根據(jù)代表回報(bào)函數(shù)的回報(bào)向量r=(10，8，4，-10)，以及服務(wù)執(zhí)行后更新的信任b′計(jì)算.回報(bào)向量r表示當(dāng)QoS等級(jí)為A時(shí)，回報(bào)值為10；當(dāng)QoS等級(jí)為B時(shí)，回報(bào)值為8；當(dāng)QoS等級(jí)為C時(shí)，回報(bào)值為4；QoS等級(jí)為D時(shí)，回報(bào)變?yōu)閼土P，值為-10.

在組合服務(wù)運(yùn)行中，觀測(cè)到服務(wù)的響應(yīng)時(shí)間，根據(jù)式(6)及等級(jí)劃分規(guī)則，可以將得到的響應(yīng)時(shí)間換算為等級(jí).由式(2)，推算出響應(yīng)時(shí)間等級(jí)trank=i時(shí)，QoS等級(jí)q=k的概率：

(7)

例如：在狀態(tài)s=(1, (1,0,0,0))，這里用信任b表示系統(tǒng)狀態(tài)，即(1,0,0,0)表示當(dāng)前狀態(tài)的QoS等級(jí)為A,B,C,D的概率分別為1,0,0,0.此時(shí)，若調(diào)用服務(wù)ws12觀測(cè)到的響應(yīng)時(shí)間trs=0.305 s，換算為響應(yīng)時(shí)間等級(jí)trk=2.根據(jù)式(7)可得：

P(q=A|trank=2)=

同理可得：

P(q=B|trank=2)=0.388 9,

P(q=C|trank=2)=0.222 2,

P(q=D|trank=2)=0.

因此當(dāng)觀察到響應(yīng)時(shí)間0.305 s時(shí)，可以判斷組合服務(wù)的QoS等級(jí)為A的概率為0.388 9，QoS等級(jí)為B的概率為0.388 9，QoS等級(jí)為C的概率為0.222 2，QoS等級(jí)為D的概率為0，所以更新信任:

b′=(0.388 9,0.388 9,0.222 2,0).

由式(3)，計(jì)算執(zhí)行服務(wù)ws12每個(gè)狀態(tài)的回報(bào)：

rws12=b·r=(0.388 9,0.388 9,0.222 2,0)·

(10,8,4,-10)=(3.889,3.111 2,0.888 8,0).

并更新?tīng)顟B(tài)為

s′=(2,(0.388 9,0.388 9,0.222 2,0)).

在此基礎(chǔ)上，繼續(xù)下一任務(wù)的組件服務(wù)選擇，直到為每個(gè)任務(wù)選擇組件服務(wù)，得到最優(yōu)服務(wù)組合.照此原理，利用Q學(xué)習(xí)算法對(duì)該場(chǎng)景中服務(wù)組合問(wèn)題求解，所得Q矩陣為

Table 1 The Belief Vectors and Selected Service for Each Task

4.2 性能驗(yàn)證

為測(cè)試SC_POMDP在實(shí)際數(shù)據(jù)上的性能，本文在香港中文大學(xué)博士鄭子彬等人[23-24]的研究成果WS-DREAM中的 QoSDataset2數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn).該數(shù)據(jù)集包括用戶(hù)信息、服務(wù)信息、響應(yīng)時(shí)間和吞吐量4個(gè)文件，本文利用其中339個(gè)用戶(hù)對(duì)5 825個(gè)服務(wù)調(diào)用的響應(yīng)時(shí)間數(shù)據(jù)rtmatrix和吞吐量數(shù)據(jù)tpmatrix構(gòu)造了相應(yīng)的QoS等級(jí)數(shù)據(jù).經(jīng)過(guò)大量實(shí)驗(yàn)，權(quán)衡收斂速度與學(xué)習(xí)效果，選擇本次實(shí)驗(yàn)中Q學(xué)習(xí)的學(xué)習(xí)率為α=0.2，ε-貪心策略的貪心率為ε=0.6，折扣因子為γ=0.8.

4.2.1 候選服務(wù)集大小對(duì)性能的影響

Fig. 4 The situation of different size of candidate sets.圖4 不同大小候選服務(wù)集的情形

固定任務(wù)數(shù)n=30，令候選服務(wù)集的大小分別為c=10,30,50，實(shí)驗(yàn)結(jié)果如圖4所示.從圖4可以看出，候選子集大小為c=10時(shí)，收斂速度較快，矩陣Q中的最高累計(jì)回報(bào)收斂到1個(gè)較小的值；隨著候選服務(wù)集增大，收斂速度減慢，但是矩陣Q中最高累計(jì)回報(bào)值增加.這與實(shí)際情況相吻合，候選集越大，矩陣Q元素越多，所以收斂速度減慢，同時(shí)由于候選集越大時(shí)較優(yōu)秀的服務(wù)會(huì)越多一些，能選到QoS較優(yōu)的組件服務(wù)的可能性就會(huì)增大，所以矩陣Q的最高累計(jì)回報(bào)收斂到更高的值.

從圖4還可以看出，當(dāng)候選服務(wù)集大小c>30時(shí)，矩陣Q的最高累計(jì)回報(bào)增長(zhǎng)緩慢，所以可以認(rèn)為，一般情況下，1個(gè)組合服務(wù)系統(tǒng)，平均每個(gè)任務(wù)有30個(gè)以上的候選服務(wù)時(shí)，SC_POMDP性能穩(wěn)定于較高水平.

4.2.2 任務(wù)數(shù)目對(duì)性能的影響

固定每個(gè)任務(wù)的候選集大小為c=30，在任務(wù)的個(gè)數(shù)分別為n為10,20,30時(shí)，實(shí)驗(yàn)結(jié)果如圖5所示：

Fig. 5 The situation of different number of subtasks.圖5 不同任務(wù)數(shù)目的情形

從圖5可以看出，隨著任務(wù)數(shù)n增加，收斂速度減慢，同樣因?yàn)榫仃嘠的元素增加，導(dǎo)致Q學(xué)習(xí)需要更長(zhǎng)的時(shí)間；而隨著任務(wù)數(shù)n增加，矩陣Q的最高累計(jì)回報(bào)收斂于較高水平，這是因?yàn)槊總€(gè)任務(wù)都要對(duì)最高累計(jì)回報(bào)有貢獻(xiàn)，所以任務(wù)數(shù)越多矩陣Q的最高累計(jì)回報(bào)就越高.圖5也表明，在任務(wù)數(shù)較多時(shí)，SC_POMDP仍然能有效地執(zhí)行.

4.2.3 組合服務(wù)性能比較

為了研究SC_POMDP建模服務(wù)組合問(wèn)題的性能，與其他方法比較服務(wù)組合的結(jié)果，即組合服務(wù)的累計(jì)回報(bào).Mean方法是從歷史數(shù)據(jù)中選擇平均性能最好的服務(wù)，不考慮當(dāng)前系統(tǒng)的運(yùn)行狀態(tài)與服務(wù)的演化情況.MDP是Wang等人在文獻(xiàn)[18]提出的服務(wù)組合模型，該模型考慮了云計(jì)算環(huán)境中服務(wù)自身的演化對(duì)服務(wù)可用性的影響，但是他們認(rèn)為對(duì)系統(tǒng)狀態(tài)是完全了解的，這是一種理想狀態(tài)，實(shí)際的組合服務(wù)運(yùn)行中對(duì)組合服務(wù)的運(yùn)行環(huán)境以及系統(tǒng)的運(yùn)行狀態(tài)，不可能有精確的了解.而本文提出的SC_POMDP用POMDP建模服務(wù)組合問(wèn)題，認(rèn)為組合服務(wù)以某概率處于某個(gè)在運(yùn)行狀態(tài).

圖6(a)(b)(c)(d)分別是在任務(wù)數(shù)n為5,10,20,30時(shí)，候選服務(wù)集大小c從5增加到10,20,30時(shí)，3種方法所計(jì)算的組合服務(wù)的平均累計(jì)回報(bào)值比較.圖6中每個(gè)取點(diǎn)都是在一種情況下重復(fù)100次實(shí)驗(yàn)的運(yùn)行結(jié)果的平均值.從圖6可以看出，隨著候選服務(wù)集增加，3種方法得到的組合服務(wù)平均回報(bào)都逐漸增加，但是基于MDP方法的平均累計(jì)回報(bào)總是優(yōu)于基于Mean方法，而SC_POMDP模型的方法平均累計(jì)回報(bào)總是優(yōu)于基于MDP的方法，從而驗(yàn)證本文所提出的SC_POMDP模型及其求解方法有較好的性能.

Fig. 6 The experiment results comparison of different approaches.圖6 3種方法的組合服務(wù)平均回報(bào)對(duì)比

Fig. 7 The scatter plot of the 3 approaches running 100 times.圖7 3種方法100次運(yùn)行結(jié)果的散點(diǎn)圖

圖7是任務(wù)數(shù)n=30、候選服務(wù)集大小c=30時(shí)，3種方法分別運(yùn)行100次的散點(diǎn)圖.從圖7可以看出，SC_POMDP模型的運(yùn)行結(jié)果都集中于值較高的區(qū)域，基于MDP的方法大部分運(yùn)行結(jié)果集中于中間值區(qū)域，也有部分較大或較小值，而基于Mean的方法運(yùn)行結(jié)果值較為分散，且分布在值較低的區(qū)域.圖7可以說(shuō)明SC_POMDP方法不僅具有較好的平均性能，而且性能比較穩(wěn)定.

4.3 自適應(yīng)性測(cè)試

在云計(jì)算環(huán)境中，組件服務(wù)分布在不同的云上，所以Internet的動(dòng)態(tài)性和服務(wù)自身演化的隨機(jī)性對(duì)服務(wù)組合是否能成功執(zhí)行有很大的影響，自適應(yīng)性是服務(wù)組合成功執(zhí)行的可靠保證.

4.3.1 模擬實(shí)例中自適應(yīng)性驗(yàn)證

為驗(yàn)證SC_POMDP的自適應(yīng)性，對(duì)1.2節(jié)的場(chǎng)景，假設(shè)組合服務(wù)(ws12，ws24，ws31)中組件服務(wù)ws24和ws31均失效，在4.1節(jié)的實(shí)驗(yàn)環(huán)境下再次運(yùn)行服務(wù)組合，SC_POMDP能選擇替代服務(wù)組合(ws12，ws25，ws32)，實(shí)驗(yàn)結(jié)果如表2所示.根據(jù)歷史觀測(cè)數(shù)據(jù)學(xué)習(xí)的結(jié)果矩陣Q，選擇到服務(wù)ws24和ws31時(shí)，由于服務(wù)失效，不能完成相應(yīng)的任務(wù)，所以在信任保持不變的情況下，從正在執(zhí)行的任務(wù)的候選集中選擇與上一個(gè)已成功執(zhí)行的組件服務(wù)相兼容的最優(yōu)服務(wù)，在選擇替換服務(wù)時(shí)不僅考慮服務(wù)的性能，而且考慮服務(wù)間的兼容性，保證服務(wù)組合能成功執(zhí)行，本例分別選擇服務(wù)ws25和ws32作為替換服務(wù).本實(shí)驗(yàn)說(shuō)明在最優(yōu)組件服務(wù)失效時(shí)，SC_POMDP能自動(dòng)選擇可用組件服務(wù)參與服務(wù)組合，說(shuō)明SC_POMDP的自適應(yīng)性.

Table2TheServiceCompositionwhenComponentServiceFailuresOccur

表2 組件服務(wù)失效時(shí)服務(wù)組合運(yùn)行情況

4.3.2 實(shí)際數(shù)據(jù)上的自適應(yīng)性

為驗(yàn)證SC_POMDP模型在較大規(guī)模實(shí)際數(shù)據(jù)上的自適應(yīng)性，在4.2節(jié)的實(shí)驗(yàn)環(huán)境下，固定任務(wù)數(shù)為n=30，令每個(gè)任務(wù)的候選服務(wù)集c大小分別為10,20,30,40,50, 在每個(gè)候選集上分別設(shè)定服務(wù)全部有效，20%的服務(wù)失效和40%的服務(wù)失效的情況,對(duì)算法進(jìn)行仿真實(shí)驗(yàn).圖8為服務(wù)組合運(yùn)行中出現(xiàn)不同比率的服務(wù)失效的實(shí)驗(yàn)結(jié)果，其中縱軸為每種情況下組合服務(wù)所得累計(jì)回報(bào)值.

Fig. 8 The different ratio of service failures.圖8 不同比率的服務(wù)失效的實(shí)驗(yàn)結(jié)果

從圖8可以看出，組合服務(wù)的回報(bào)值會(huì)受到服務(wù)失效的影響，隨著服務(wù)失效率的增長(zhǎng)組合服務(wù)的回報(bào)值降低，但是服務(wù)組合仍然能成功執(zhí)行.事實(shí)上，只要存在性能較好的可用候選服務(wù)，在失效率更高的情況下，服務(wù)組合仍然能較好地執(zhí)行，這也表明SC_POMDP的高度自適應(yīng)性.

4.3.3 與同類(lèi)方法的自適應(yīng)性對(duì)比實(shí)驗(yàn)

為檢驗(yàn)SC_POMDP對(duì)服務(wù)組合過(guò)程自適應(yīng)性的提升，選擇2個(gè)具有代表性的自適應(yīng)服務(wù)組合方法[17-18]進(jìn)行對(duì)比實(shí)驗(yàn),其中文獻(xiàn)[17]將服務(wù)的QoS看作隨機(jī)變量，以隨機(jī)變量的均值與方差刻畫(huà)服務(wù)QoS的隨機(jī)性，本文稱(chēng)之為RQoSA_SC(random QoS aware service composition);文獻(xiàn)[18]考慮了服務(wù)演化的隨機(jī)性，用 MDP建模服務(wù)組合過(guò)程，提出了WSC_MDP模型并用Q學(xué)習(xí)方法求解.現(xiàn)將RQoSA_SC與WSC_MDP的方法移植到本文的實(shí)驗(yàn)環(huán)境中進(jìn)行服務(wù)組合，并與SC_POMDP的服務(wù)組合結(jié)果進(jìn)行對(duì)比.

實(shí)驗(yàn)中固定任務(wù)數(shù)n=20，每個(gè)任務(wù)的候選服務(wù)集大小c=30，且3個(gè)方法用相同的候選服務(wù)集，設(shè)置服務(wù)失效率均為20%，分別用RQoSA_SC，WSC_MDP和SC_POMDP進(jìn)行服務(wù)組合，考察組合服務(wù)的成功率以及各組件服務(wù)的QoS(本文以響應(yīng)時(shí)間與吞吐量為代表).表3所示的是3種方法在1次實(shí)驗(yàn)中所選的組件服務(wù)的響應(yīng)時(shí)間與吞吐量對(duì)比，事實(shí)上幾乎每次的實(shí)驗(yàn)結(jié)果都和表3的情形類(lèi)似.

表3中RT代表響應(yīng)時(shí)間，TP代表吞吐量.實(shí)驗(yàn)結(jié)果表明3種方法的服務(wù)組合成功率均為100%，表明3種方法都具有對(duì)服務(wù)失效的自適應(yīng)能力.而一般情況，SC_POMDP所選的組件服務(wù)有較低的響應(yīng)時(shí)間與較高的吞吐量，偶爾也出現(xiàn)RQoSA_SC或WSC_MDP在某個(gè)任務(wù)的組件服務(wù)的響應(yīng)時(shí)間或吞吐量?jī)?yōu)于SC_POMDP的情況，這是因?yàn)榉抡姝h(huán)境的不確定性，不能保證每次服務(wù)組合的運(yùn)行環(huán)境以及組件服務(wù)運(yùn)行性能都一致.

表4是3種方法所選的組件服務(wù)的平均響應(yīng)時(shí)間和平均吞吐量數(shù)據(jù)，以及最優(yōu)最差響應(yīng)時(shí)間和吞吐量任務(wù)數(shù)的對(duì)比.

從平均水平來(lái)看SC_POMDP所選的組件服務(wù)的平均響應(yīng)時(shí)間為0.090 25 s，平均吞吐量為89.349 Kbps;WSC_MDP所選的組件服務(wù)的平均響應(yīng)時(shí)間為0.110 05 s，平均吞吐量為49.431 6 Kbps;RQoSA_SC所選的組件服務(wù)的平均響應(yīng)時(shí)間為0.619 1，平均吞吐量為46.037 55 Kbps.可以看出SC_POMDP有最優(yōu)的平均吞吐量與響應(yīng)時(shí)間.比較3種方法所選的組件服務(wù)響應(yīng)時(shí)間最優(yōu)的任務(wù)數(shù)，SC_POMDP有12個(gè)，WSC_MDP有8個(gè)，RQoSA_SC有1個(gè)，其中SC_POMDP與WSC_MDP執(zhí)行任務(wù)13時(shí)的響應(yīng)時(shí)間與吞吐量相同，而所選的組件服務(wù)響應(yīng)時(shí)間最差的任務(wù)數(shù)SC_POMDP少于WSC_MDP，WSC_MDP又少于RQoSA_SC.吞吐量方面的對(duì)比有相同的結(jié)論.因此整體上來(lái)看，SC_POMDP有更優(yōu)的自適應(yīng)性.

Table 3 The Comparison of the Component Services’ Response Time and Throughput Result from the 3 Methods

Table 4 The Statistic Data Comparison of the 3 Methods

5 總結(jié)與展望

本文建立了一種基于POMDP的服務(wù)組合模型SC_POMDP，并應(yīng)用Q學(xué)習(xí)算法對(duì)模型進(jìn)行求解.大量實(shí)驗(yàn)表明，SC_POMDP在任務(wù)眾多、候選服務(wù)集較大或較小的情況下，都能有效地選擇組件服務(wù)進(jìn)行服務(wù)組合，與已有的方法比較，對(duì)于代表組合服務(wù)QoS性能的累計(jì)回報(bào)，SC_POMDP總是優(yōu)于其他方法，這是由于SC_POMDP對(duì)系統(tǒng)狀態(tài)的不確定性有更真實(shí)的反映；并且在出現(xiàn)不同比率的服務(wù)失效的情況下，SC_POMDP仍然能成功地執(zhí)行服務(wù)組合，與同類(lèi)方法的比較中，SC_POMDP也表現(xiàn)出較高的自適應(yīng)性.

本文工作的主要貢獻(xiàn)在于:

1) 考慮到云計(jì)算環(huán)境的動(dòng)態(tài)性和組件服務(wù)自身演化的隨機(jī)性，將組件服務(wù)選擇與服務(wù)組合執(zhí)行同時(shí)進(jìn)行，提高了方法的自適應(yīng)性；

2) 考慮到在服務(wù)組合中系統(tǒng)運(yùn)行狀態(tài)的不確定性，利用POMDP建模組合服務(wù)，提高了服務(wù)組合的可靠性；

3) 考慮了組件服務(wù)間的兼容性，這是在實(shí)際服務(wù)組合中必須面對(duì)而在許多研究工作中被忽視的環(huán)節(jié).

在云計(jì)算環(huán)境中，集成已有的組件服務(wù)，構(gòu)建自適應(yīng)的服務(wù)組合，構(gòu)成新的增值的Web應(yīng)用，是一種新的軟件構(gòu)建模式.本文提出的SC_POMDP模型是云計(jì)算環(huán)境中系統(tǒng)運(yùn)行狀態(tài)不確定的一般情況下，一種自適應(yīng)地服務(wù)組合的方法.未來(lái)需要進(jìn)一步研究的問(wèn)題是針對(duì)具體的用戶(hù)需求研究滿(mǎn)足用戶(hù)QoS約束的服務(wù)組合.

[1]Ari I, Muhtaroglu N. Design and implementation of a cloud computing service for finite element analysis[J]. Advances in Engineering Software, 2013, 60: 122-135

[2]Rezaei R, Chiew T K, Lee S P, et al. A semantic interoperability framework for software as a service systems in cloud computing environments[J]. Expert Systems with Application, 2014, 41(13): 5751-5770

[3]Sheng Quan Z, Qiao Xiaoqiang, Vasilakos A V, et al. Web services composition: A decade’s overview[J]. Information Sciences, 2014, 280: 218-238

[4]McDermott D. Estimated-Regression planning for interactions with Web services[C] //Proc of the 6th Int Conf on Artificial Intelligence Planning and Scheduling. Melon Park, CA: AAAI Press, 2002: 204-211

[5]Sheshagiri M, desJardins M, Finin T. A planner for composing services described in DAML-S[J]. Web Services and Agent-based Engineering-AAMAS, 2003, 3: 1-5

[6]McIlraith S, Son T C. Adapting golog for composition of semantic Web services[C] //Proc of the 8th Int Conf on Knowledge Representation and Reasoning. Toulouse, France: CiteSeer, 2002: 482-493

[7]Sirin E, Parsia B, Wu D, et al. HTN planning for Web service composition using SHOP2[J]. Web Semantics: Science, Services and Agents on the World Wide Web, 2004, 1(4): 377-396

[8]He Qiang, Han Jun, Yang Yun, et al. QoS-driven service selection for multi-tenant SaaS[C] //Proc of the 5th IEEE Int Conf on Cloud Computing. Piscataway,NJ : IEEE, 2012: 566-573

[9]Alrifai M, Skoutas D, Risse T. Selecting skyline services for QoS-based Web service composition[C] //Proc of the 19th Int Conf on World Wide Web. New York : ACM, 2010: 11-20

[10]Luo Juan, Zhou Feng, Li Renfa. Dynamic service composition mechanism based on OSGi[J]. Journal of Computer Research and Development, 2014, 51(2): 420-428 (in Chinese)(羅娟, 周峰, 李仁發(fā). 基于分布式OSGi的動(dòng)態(tài)服務(wù)組合算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(2): 420-428)

[11]Vu L-H, Hauswirth M, Aberer K. QoS-based service selection and ranking with trust and reputation management[C] //Proc of the Cooperative Information System Conf. Berlin: Springer, 2005: 466-483

[12]Mei Lijun, Chan W K, Tse T H. An adaptive service selection approach to service composition[C] //Proc of the 20th IEEE Int Conf on Web Services. Piscataway, NJ: IEEE, 2008: 70-77

[13]Fan Xiaoqin, Jiang Changjun, Fang Xianwen, et al. Dynamic Web service selection based on discrete particle swarm optimization[J]. Journal of Computer Research and Development, 2010, 47(1): 147-156 (in Chinese)(范小芹, 蔣昌俊, 方賢文, 等. 基于離散微粒群算法的動(dòng)態(tài)Web服務(wù)選擇[J]. 計(jì)算機(jī)研究與發(fā)展, 2010: 47(1): 147-156)

[14]Littman M L. A tutorial on partially observable Markov decision processes[J]. Journal of Mathematical Psychology, 2009, 53(3): 119-125

[15]Hauskrecht M. Value-function approximations for partially observable Markov decision processes[J]. Journal of Artificial Intelligence Research, 2000, 13(1): 33-94

[16]Mitchell T M. Machine Learning[M]. New York: McGraw-Hill Science/Engineering/Math, 1997 (in Chinese)(Mitchell T M. 機(jī)器學(xué)習(xí)[M]. 曾華軍, 張銀奎, 等譯. 1版. 北京: 機(jī)械工業(yè)出版社, 1997)

[17]Fan Xiaoqin, Jiang Changjun, Wang Junli et al. Random-QoS-Aware reliable Web service composition[J]. Journal of Software, 2009, 20(3): 546-556 (in Chinese)(范小芹, 蔣昌俊, 王俊麗, 等. 隨機(jī)QoS感知的可靠Web服務(wù)組合[J]. 軟件學(xué)報(bào), 2009, 20(3): 546-556)

[18]Wang Hongbing, Zhou Xuan, Zhou Xiang, et al. Adaptive and dynamic service composition using Q-learning[C] //Proc of the 22nd IEEE Int Conf on Tools with Artificial Intelligence. Piscataway, NJ: IEEE, 2010: 145-152

[19]Yang Jun, Lin Wenming, Dou Wanchun. An adaptive service selection method for cross-cloud service composition[J]. Concurrency and Computation: Practice and Experience, 2013, 25(18): 2435-2454

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

[21]Klein A, Ishikawa F, Honiden S. SanGa: A self-adaptive network-aware approach to service composition[J]. IEEE Trans on Services Computing, 2014, 7(3): 452-464

[22]Cardoso J, Sheth A, Miller J, et al. Quality of service for workflows and Web service processes[J]. Journal of Web Semantics: Science, Services and Agents on the World Wide Web, 2004, 1(3): 281-308

[23]Zheng Zibin, Zhang Yilei, Lyu M R. Distributed QoS evaluation for real-world Web services[C] //Proc of the 8th IEEE Int Conf on Web Services. Piscataway, NJ: IEEE, 2010: 83-90

[24]Zhang Yilei. Zheng Zibin, Lyu M R. Exploring latent features for memory-based QoS prediction in cloud computing[C] //Proc of the 30th IEEE Symp on Reliable Distributed Systems. Piscataway, NJ: IEEE, 2011: 1-10

Ren Lifang, born in 1976. PhD candidate, lecturer. Her main research interests include service computing and trustworthy software.

Wang Wenjian, born in 1968. PhD, professor. Senior member of China Computer Federation. Her main research interests include data mining and machine learning theory.

Xu Hang, born in 1987. PhD candidate. Her main research interests include machine learning and service computing (xuh102@126.com).

Uncertainty-Aware Adaptive Service Composition in Cloud Computing

Ren Lifang1,2, Wang Wenjian1, and Xu Hang1

1(School of Computer and Information Technology, Shanxi University, Taiyuan 030006)2(SchoolofAppliedMathematics,ShanxiUniversityofFinance&Economics,Taiyuan030006)

Cloud computing service composition is to select appropriate component services from numerous of services distributed in different clouds to build scalable loose coupling value-added applications. Traditional service composition methods are usually divided into selection stage and composition stage. Hardly guaranteeing the services with the best performance in the selection stage are still optimal in the execution stage because of the dynamic nature of the cloud computing environment and the stochastic nature of services evolution. Focusing on these two natures of service composition in cloud computing environment, a service composition model is built based on POMDP (partially observable Markov decision process) named as SC_POMDP (service composition based on POMDP), and a Q-learning algorithm is designed to solve the model. SC_POMDP can dynamically select the component services with outstanding QoS (quality of service) during the execution of service composition, which aims to ensure the adaptability of the service composition. Different from most existing methods, the proposed SC_POMDP regards the environment of service composition as being uncertain, and the compatibility between component services is considered, hence SC_POMDP is more in line with the real situation. Simulation experiments demonstrate that the proposed method can successfully solve the problems of service composition in different sizes. Specially, when service failure occurs, SC_POMDP can still select the optimal alternative component services to ensure the successful execution of the composite service. Compared with two existing methods，the selected composite service by SC_POMDP is best in response time and throughput, which reflects the superior adaptation of SC_POMDP.

adaptive service composition; cloud computing environment; uncertainty-aware; partially observable Markov decision process (POMDP); Q-learning algorithm; quality of service (QoS)

2015-01-26；

2015-08-11

國(guó)家自然科學(xué)基金項(xiàng)目(61273291，61673249)；山西省回國(guó)留學(xué)人員科研資助項(xiàng)目(2016-004) This work was supported by the National Natural Science Foundation of China (61273291, 61673249) and the Research Project of Shanxi Scholarship Council of China (2016-004)

王文劍(wjwang@sxu.edu.cn)

TP311