不確定感知的自適應云計算服務組合

任麗芳 王文劍 許 行

1(山西大學計算機與信息技術學院 太原 030006)2(山西財經大學應用數學學院 太原 030006)(renlf@sxufe.edu.cn)

?

不確定感知的自適應云計算服務組合

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

1(山西大學計算機與信息技術學院 太原 030006)2(山西財經大學應用數學學院 太原 030006)(renlf@sxufe.edu.cn)

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

自適應服務組合；云計算環境；不確定感知；部分可觀測Markov決策過程；Q學習算法；服務質量

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

服務組合是1個復雜而具有挑戰性的工作，在這方面已經進行了許多的研究.按照自動化程度，服務組合的方式可以分為手動、半自動和自動服務組合3大類.隨著可用服務不斷涌現，手動方式對現有的服務進行分析和組合已經變得不可行[3].

通常自動組合方式會將服務組合任務轉化為1個經典的規劃問題求解[4-7].首先用規劃語言，如PDDL[4], TRIPS[5]或GOLOG[6]等，對服務進行形式化描述；然后用人工智能規劃算法，如分層任務網絡(hierarchical task network, HTN)規劃[7]、Estimated-regression 規劃[4]等來求解該規劃問題;最后，將規劃問題的解轉變為自動的服務調用.自動服務組合通常只是尋求滿足用戶功能需求的組合服務，而不考慮組合服務的服務質量(quality of service, QoS)，因此組合服務的性能難以保證.更重要的是經典的規劃算法一般不考慮系統的動態特性，因此自動服務組合方式一般假定服務是確定不變的，然而在實際的服務組合環境中，服務的性能會受Internet的動態性和云服務提供組織升級演化的影響，甚至變得不可用，所以自動服務組合是易于失敗的.

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

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

1 相關工作

云計算環境的動態性加之服務的自治性，使得組合服務的性能難以保證，因此構建適應這種不確定環境的服務組合成為了1個挑戰，引起國內外學者對自適應服務組合方法進行了廣泛的研究[17-21].

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

Wang等人[18]考慮了Web服務演化的不確定性，設計了基于MDP的服務組合模型，在組合服務運行時進行具體服務的選擇，有效地減少了服務選擇階段與組合服務運行階段之間服務演化所帶來的影響.然而該方法在進行服務選擇時沒有考慮服務組合系統所處的運行環境的不確定性，事實上不同的運行環境中組件服務的實際性能有很大的差異.文獻[18]的方法提升了服務組合對服務演化的適應性，但是沒有考慮服務組合對運行環境的適應性，因此該方法能保證組合服務的成功執行，但是并不能保證組合服務的性能最優.

Yang等人[19]建立了云間服務組合中相繼任務的服務對集合，并定義了服務對效用的評價函數.該方法基于MDP為服務組合建立模型，選擇效用函數值最優的服務對形成服務組合.該模型在服務對的效用值計算中，認為組件服務的QoS屬性值是確定的，而實際中組件服務的QoS屬性值波動較大，所以該服務組合方法的適應能力有很大的局限.

Ardagna等人在文獻[20]將服務組合建模為1個混合整數規劃問題，并以環剝技術加速優化過程，利用協商機制降低服務過程中由于用戶約束不滿足導致的失敗率，體現了該方法對用戶約束的自適應性，目標是尋找滿足用戶約束的可行的組合服務.然而該方法以QoS屬性的理論分布值作為實際的QoS屬性值，沒有考慮組合服務對不確定環境的適應性.

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

Klein等人在文獻[21]將QoS屬性區分為服務自身決定的屬性和與網絡相關的屬性，提出了網絡感知的方法，用2種不同的方法計算2類不同的QoS屬性值.對網絡相關的QoS屬性，根據相繼服務所在服務器的網絡距離計算QoS屬性值.在此基礎上，該文設計了網絡感知的遺傳算法，求解最優服務組合，該方法的適應性體現在根據一定的經驗概率選擇執行遺傳操作，然而該方法中服務選擇與組合服務的執行分階段進行，沒有考慮對組件服務演化的適應性，不能保證服務組合的成功執行.

不同于已有的服務組合方法，本文針對云計算環境中，服務性能受Internet的動態性以及服務自身演化隨機性的影響，且系統對組合服務運行環境狀態不完全了解，這種更一般情況的服務組合問題展開研究.同時本文考慮了組件服務之間的兼容情況，建立了基于POMDP的服務組合模型SC_POMDP，并設計了模型的求解算法，為解決在不確定的云計算環境中自適應地進行性能最優的服務組合問題提供了一種可行方法.

2 云計算服務組合

本節給出服務組合問題中的一些相關概念，并給出原子服務、組件服務以及組合服務的形式化描述.同時，為了說明云計算環境服務組合過程及其特征，本節設計了1個云計算服務組合的場景.

2.1 相關概念

定義1. 原子服務(atomic service)是1個獨立的、功能完整的可以通過網絡進行發布、定位以及訪問的最小資源單位.1個原子服務可以形式化為1個三元組(Nid,Cfun,Mqos)，其中：

Nid是原子服務的標識，通過Nid可以唯一地確定1個原子服務；

Cfun代表原子服務的功能分類號，功能相同的原子服務有相同的Cfun.能完成某個特定任務的服務具有相同的Cfun，這些服務組成1個集合，稱為該任務的候選服務集(set of candidate services)；

Mqos代表原子服務在被調用歷史中表現的服務質量，是1個矩陣，矩陣的行數是該服務被調用的次數，列數是所考察的QoS屬性(如響應時間、價格、可用性等)的個數.其中行i(mi 1，mi 2，…，mi n)代表該服務在第i次被調用時各QoS屬性的值.

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

2個或多個原子服務可以組合產生1個新的服務，這個新的服務可以執行更復雜的其中任何1個原子服務無法獨立完成的任務.這個包含多個原子服務的新服務是1個組合服務.構造組合服務的過程可以迭代進行，也就是說，組合服務可以被用作組成另1個更復雜組合服務的組件服務.圖1是原子服務、組件服務與組合服務關系的1個示例.圖1中，大虛線框內的是1個組合服務，小虛線框內的是1個組件服務，每個圓圈代表1個原子服務.

定義2. 組件服務(component service)本質上是1個較小規模的組合服務,組件服務能夠實現1個小規模的完整業務解決方案，所以經常作為1個整體.組件服務可以形式化地定義為1個四元組(Nid,Cfun,Mqos,Vmemb)，其中：

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

Vmemb是依序構成這個組件服務的所有原子服務的Nid組成的序列.

服務的強大之處就在于組件服務能動態地進行集成來執行新的更復雜的任務，這個過程就是服務組合(service composition).

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

由于具有循環、分支和并行結構的服務組合都能夠轉化為一種順序結構[22]，所以本文主要解決業務邏輯的過程模型為順序結構的服務組合問題.

2.2 云計算服務組合的1個場景

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

Fig. 2 A scenario of cloud services composition.圖2 云計算環境服務組合場景

顯然為滿足用戶的需求需要對現有的服務進行組合.用戶的需求可以分解為3個任務：圖像復原任務t1、三維重建計算任務t2、云存儲任務t3，如圖2所示.在Internet中，存在許多不同的云計算服務提供商，為簡單起見，本文在圖2所示的場景中假設所涉及的服務由圖中所示的4個云提供，每個云提供商提供許多不同的原子服務，在圖中以小實心圓表示.經過在所有的云上進行服務發現，每個任務都可以由幾個不同的服務獨立地完成，圖2中以wsi j表示可以完成任務ti的第j個候選服務，也是構成目標組合服務的可用組件服務.候選服務的次序只是區分同一候選服務集中不同的服務，這些候選服務可能分布在相同或不同的云上.

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

C1={ws11,ws12,ws13},

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

C3={ws31,ws32,ws33}.

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

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

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

考慮到用戶的滿意度，應該選擇使組合服務性能最優的服務.然而由于云計算環境的動態性以及服務演化的隨機性，服務的QoS在不斷變化，有時甚至會出現某個服務失效的情況.如何在這種動態環境中為每個任務選擇服務使當前組合服務的性能最優是本文研究的目的.自適應云計算服務組合旨在感知組合服務執行的網絡環境，選擇適應該環境的組件服務，同時若被選擇的組件服務由于演化升級等原因發生失效時，可以從候選服務集中重新選擇適應性較高的服務替換失效的組件服務.

3 自適應服務組合模型SC_POMDP

本節利用第2節定義的組件服務與組合服務，建立服務組合模型SC_POMDP，給出SC_POMDP模型中服務的選擇機制，并設計該模型求解的Q學習算法.

3.1 建立服務組合模型SC_POMDP

在POMDP模型中，決策者周期地或連續地觀察隨機動態系統，在決策時刻根據觀察到的系統所處的狀態分布以及所采取的策略從可用的行動集合中選擇1個動作.POMDP系統下一步的狀態是隨機的，并且其狀態轉移概率具有無后效性，即下一個決策只依賴于系統當前的狀態，與歷史狀態無關.決策者根據新的觀察判斷系統的狀態分布，做出新的決策，如此反復地進行[14].云計算環境的服務組合，依照業務邏輯所定義的過程模型，以組合服務性能最優為目標，根據對系統所處狀態分布的判斷，從每個任務的候選服務集中選擇當前運行狀態下性能最優的組件服務，執行該服務引起系統的狀態分布發生改變，且下一個服務的選擇只與系統的當前狀態有關，與歷史狀態無關.因此本文采用POMDP建模云計算環境的服務組合，主要步驟如下：

Step1. 根據用戶需求，建立代表服務組合業務邏輯的任務流模板；

Step2. 為模板中每個任務聚集可用候選服務集，并建立服務間的兼容關系；

Step3. 建立服務組合模型SC_POMDP；

Step4. 利用Q學習算法對每個服務的歷史運行QoS數據進行學習，得出代表每個任務的各候選服務在不同系統狀態的QoS性能的矩陣Q；

Step5. 根據系統實時運行狀態分布以及矩陣Q，并結合服務之間的兼容性，選擇在當前狀態使組合服務有最大累計回報值的可用組件服務；

Step6. 重復Step5直到每個任務都完成.

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

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

1)S為狀態集合，S={s},其中任意1個狀態s=(t,q)是1個二元組,t表示正在執行的任務的序號；q表示當前組合服務運行所處的QoS等級狀態，q的可能取值為集合Qqos={A,B,C,D}中的元素.其中A表示服務質量為優；B表示服務質量中等；C表示服務質量較差；D表示服務失敗，即服務沒有正確執行.如s=(3,B)，表示組合服務正在運行任務3，且系統所處的QoS狀態為B.

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

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

5)O(ws,s′,z)是觀測函數，表示調用服務ws后狀態轉移到s′時觀測到z的概率.本文根據服務執行歷史數據中QoS值和當前服務運行的觀測值，利用Bayes公式進行計算.

6)R(s′,s,ws)是回報函數，表示在調用服務ws后系統從狀態s轉移到狀態s′所得的回報值.r=R(s′,s,ws)是1個實值函數，當r>0時表示獎勵,r<0時表示懲罰.服務ws的執行使組合服務的運行狀態轉移到的QoS等級越高，則回報值r越大;否則回報值r越小.服務組合的目標是選擇最優組件服務使組合服務的累計回報值最高.

不同于已有的基于MDP模型的服務組合，在SC_POMDP模型中設置了觀測集合與觀測函數，根據觀測集合Z中的元素z與觀測函數O，推斷系統處于某個狀態s概率.這樣做能更真實地反映在服務組合過程中組件服務執行后組合服務所處狀態的多種可能狀況，在選擇下一組件服務時，對系統所處的狀態判斷更加準確.

3.2 SC_POMDP模型中的服務選擇

SC_POMDP中，執行服務ws，引起系統狀態s轉移，決策者根據觀察z更新信任向量b，計算回報rws，并進行下一動作的決策，如此反復，直到組合服務中的所有任務依次成功執行.

由于當前系統以概率b(q)處于狀態q，選擇服務ws向下一狀態為s′∈S轉移的概率為T(s,ws,s′)，并以O(ws,s′,z)觀察到z，所以能觀察到z的總概率為

(1)

當收到新的觀察后，就要更新信任狀態，根據Bayes定理，對下一狀態處于q′的信任為

(2)

從信任狀態b(q)調用服務ws可得回報的期望值為

(3)

POMDP模型中，策略是從信任空間到動作空間的映射.決策過程即是在策略的指導下，根據對系統所處狀態的信任函數，最大化期望回報值的過程.如果存在策略π*，對于信任狀態b(q)，采用策略π*獲得的回報值大于采用其他任何策略π所獲得的回報，則稱π*為最優策略，其對應的值函數V*為最優值函數.

考慮SC_POMDP中所有可能的信任狀態更新和觀測值，得遞歸方程：

(4)

(5)

其中，rw s為執行服務ws所得的即時回報;pz是在執行第ti個任務時觀察到z的概率;γ(0≤γ≤1)是折扣因子，體現未來的回報相對近期的回報權重要低.若γ=1，表示沒有折扣，未來的回報與當前回報權重相等；若γ=0，表示只考慮即時回報，未來回報被忽略.

SC_POMDP模型研究的目標就是在服務組合運行中，根據對系統所處狀態的判斷，從候選服務集中選擇使式(4)取最大值的組件服務，所選擇的組件服務依次組成的組合服務即為服務組合問題的最優策略.

3.3 求解SC_POMDP模型的Q學習算法

理論上，將服務組合問題建模為SC_POMDP后，系統可以動態地選擇最優策略，服務組合以實時最優的結果滿足用戶的需求.然而在實踐中，由于POMDP模型的精確求解已被證明是PSPACE完全的[15]，加之云計算環境中組件服務QoS的動態性，使其最優策略的求解非常困難.因此，我們采用學習的方法來求解最優策略.Q學習是一種增強學習方法，通過動作執行結果的回報值，強化使系統狀態更好地動作[16].該算法需要從動作的多次執行中學習，然而由于組件服務大多是商業應用，在服務組合執行過程中不可能在選擇服務前多次調用候選服務以測試其性能，因此我們保存服務調用歷史中服務執行的QoS數據，用于Q學習算法求解SC_POMDP模型時對矩陣Q的學習.SC_POMDP模型的Q學習算法如下.

算法1. 求解SC_POMDP的Q學習算法.

輸入：任務數n、候選服務集A、學習率參數α、折扣因子γ；

輸出：性能矩陣Q.

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

② whileQ沒有達到收斂 do

③ 初始化任務序號：t←1;

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

⑤ whilet≤ndo

⑥ 隨機選擇A(t)中服務ws;

⑦ 執行服務ws;

⑧ 觀測到響應時間tr和吞吐量tp;

⑨ 計算信任向量b′;

⑩ 計算回報值r;

4 仿真實驗

為檢驗所提出的服務組合方法的性能，本文的實驗分3部分：1)2.2節場景中的服務組合問題求解，以驗證模型及其求解算法的正確性；2)在真實數據集上進行測試，以驗證本文所提出的方法在實際的較大規模的服務組合問題上的性能；3)對模型適應性進行測試，分別在實例問題和實際數據集中出現服務失效的情況下對SC_POMDP模型的適應性進行驗證，并與2個有代表性的方法進行適應性比較.

4.1 正確性驗證

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

設最大可接受的響應時間為5 s，服務的最快響應時間為0.1 s，所以利用

Tnorm=(5-Treps)

(6)

對矩陣Tresp進行歸一化，得矩陣Tnorm.Tresp中元素值為-1時，表示服務失敗，不參與歸一化處理，在Tnorm矩陣中保持原值-1.對Tnorm中元素，若Tnorm(i,j)≥0.95,則對應的響應時間等級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.可得如下所示的響應時間等級矩陣Trank.

設矩陣Qrank為服務歷次運行后經計算得出的綜合QoS等級(可能由服務組合代理機構根據服務調用中各QoS屬性值進行綜合計算得出，也可能由用戶反饋給出)，代表對服務執行的QoS綜合評價.其中矩陣元素A,B,C,D分別表示服務執行的QoS等級，NaN表示無調用記錄.

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

各任務調用相應的候選集中的服務，回報值的計算可以根據代表回報函數的回報向量r=(10，8，4，-10)，以及服務執行后更新的信任b′計算.回報向量r表示當QoS等級為A時，回報值為10；當QoS等級為B時，回報值為8；當QoS等級為C時，回報值為4；QoS等級為D時，回報變為懲罰，值為-10.

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

(7)

例如：在狀態s=(1, (1,0,0,0))，這里用信任b表示系統狀態，即(1,0,0,0)表示當前狀態的QoS等級為A,B,C,D的概率分別為1,0,0,0.此時，若調用服務ws12觀測到的響應時間trs=0.305 s，換算為響應時間等級trk=2.根據式(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.

因此當觀察到響應時間0.305 s時，可以判斷組合服務的QoS等級為A的概率為0.388 9，QoS等級為B的概率為0.388 9，QoS等級為C的概率為0.222 2，QoS等級為D的概率為0，所以更新信任:

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

由式(3)，計算執行服務ws12每個狀態的回報：

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).

并更新狀態為

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

在此基礎上，繼續下一任務的組件服務選擇，直到為每個任務選擇組件服務，得到最優服務組合.照此原理，利用Q學習算法對該場景中服務組合問題求解，所得Q矩陣為

Table 1 The Belief Vectors and Selected Service for Each Task

4.2 性能驗證

為測試SC_POMDP在實際數據上的性能，本文在香港中文大學博士鄭子彬等人[23-24]的研究成果WS-DREAM中的 QoSDataset2數據集上進行實驗.該數據集包括用戶信息、服務信息、響應時間和吞吐量4個文件，本文利用其中339個用戶對5 825個服務調用的響應時間數據rtmatrix和吞吐量數據tpmatrix構造了相應的QoS等級數據.經過大量實驗，權衡收斂速度與學習效果，選擇本次實驗中Q學習的學習率為α=0.2，ε-貪心策略的貪心率為ε=0.6，折扣因子為γ=0.8.

4.2.1 候選服務集大小對性能的影響

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

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

從圖4還可以看出，當候選服務集大小c>30時，矩陣Q的最高累計回報增長緩慢，所以可以認為，一般情況下，1個組合服務系統，平均每個任務有30個以上的候選服務時，SC_POMDP性能穩定于較高水平.

4.2.2 任務數目對性能的影響

固定每個任務的候選集大小為c=30，在任務的個數分別為n為10,20,30時，實驗結果如圖5所示：

Fig. 5 The situation of different number of subtasks.圖5 不同任務數目的情形

從圖5可以看出，隨著任務數n增加，收斂速度減慢，同樣因為矩陣Q的元素增加，導致Q學習需要更長的時間；而隨著任務數n增加，矩陣Q的最高累計回報收斂于較高水平，這是因為每個任務都要對最高累計回報有貢獻，所以任務數越多矩陣Q的最高累計回報就越高.圖5也表明，在任務數較多時，SC_POMDP仍然能有效地執行.

4.2.3 組合服務性能比較

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

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

Fig. 6 The experiment results comparison of different approaches.圖6 3種方法的組合服務平均回報對比

Fig. 7 The scatter plot of the 3 approaches running 100 times.圖7 3種方法100次運行結果的散點圖

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

4.3 自適應性測試

在云計算環境中，組件服務分布在不同的云上，所以Internet的動態性和服務自身演化的隨機性對服務組合是否能成功執行有很大的影響，自適應性是服務組合成功執行的可靠保證.

4.3.1 模擬實例中自適應性驗證

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

Table2TheServiceCompositionwhenComponentServiceFailuresOccur

表2 組件服務失效時服務組合運行情況

4.3.2 實際數據上的自適應性

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

Fig. 8 The different ratio of service failures.圖8 不同比率的服務失效的實驗結果

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

4.3.3 與同類方法的自適應性對比實驗

為檢驗SC_POMDP對服務組合過程自適應性的提升，選擇2個具有代表性的自適應服務組合方法[17-18]進行對比實驗,其中文獻[17]將服務的QoS看作隨機變量，以隨機變量的均值與方差刻畫服務QoS的隨機性，本文稱之為RQoSA_SC(random QoS aware service composition);文獻[18]考慮了服務演化的隨機性，用 MDP建模服務組合過程，提出了WSC_MDP模型并用Q學習方法求解.現將RQoSA_SC與WSC_MDP的方法移植到本文的實驗環境中進行服務組合，并與SC_POMDP的服務組合結果進行對比.

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

表3中RT代表響應時間，TP代表吞吐量.實驗結果表明3種方法的服務組合成功率均為100%，表明3種方法都具有對服務失效的自適應能力.而一般情況，SC_POMDP所選的組件服務有較低的響應時間與較高的吞吐量，偶爾也出現RQoSA_SC或WSC_MDP在某個任務的組件服務的響應時間或吞吐量優于SC_POMDP的情況，這是因為仿真環境的不確定性，不能保證每次服務組合的運行環境以及組件服務運行性能都一致.

表4是3種方法所選的組件服務的平均響應時間和平均吞吐量數據，以及最優最差響應時間和吞吐量任務數的對比.

從平均水平來看SC_POMDP所選的組件服務的平均響應時間為0.090 25 s，平均吞吐量為89.349 Kbps;WSC_MDP所選的組件服務的平均響應時間為0.110 05 s，平均吞吐量為49.431 6 Kbps;RQoSA_SC所選的組件服務的平均響應時間為0.619 1，平均吞吐量為46.037 55 Kbps.可以看出SC_POMDP有最優的平均吞吐量與響應時間.比較3種方法所選的組件服務響應時間最優的任務數，SC_POMDP有12個，WSC_MDP有8個，RQoSA_SC有1個，其中SC_POMDP與WSC_MDP執行任務13時的響應時間與吞吐量相同，而所選的組件服務響應時間最差的任務數SC_POMDP少于WSC_MDP，WSC_MDP又少于RQoSA_SC.吞吐量方面的對比有相同的結論.因此整體上來看，SC_POMDP有更優的自適應性.

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 總結與展望

本文建立了一種基于POMDP的服務組合模型SC_POMDP，并應用Q學習算法對模型進行求解.大量實驗表明，SC_POMDP在任務眾多、候選服務集較大或較小的情況下，都能有效地選擇組件服務進行服務組合，與已有的方法比較，對于代表組合服務QoS性能的累計回報，SC_POMDP總是優于其他方法，這是由于SC_POMDP對系統狀態的不確定性有更真實的反映；并且在出現不同比率的服務失效的情況下，SC_POMDP仍然能成功地執行服務組合，與同類方法的比較中，SC_POMDP也表現出較高的自適應性.

本文工作的主要貢獻在于:

1) 考慮到云計算環境的動態性和組件服務自身演化的隨機性，將組件服務選擇與服務組合執行同時進行，提高了方法的自適應性；

2) 考慮到在服務組合中系統運行狀態的不確定性，利用POMDP建模組合服務，提高了服務組合的可靠性；

3) 考慮了組件服務間的兼容性，這是在實際服務組合中必須面對而在許多研究工作中被忽視的環節.

在云計算環境中，集成已有的組件服務，構建自適應的服務組合，構成新的增值的Web應用，是一種新的軟件構建模式.本文提出的SC_POMDP模型是云計算環境中系統運行狀態不確定的一般情況下，一種自適應地服務組合的方法.未來需要進一步研究的問題是針對具體的用戶需求研究滿足用戶QoS約束的服務組合.

[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)(羅娟, 周峰, 李仁發. 基于分布式OSGi的動態服務組合算法[J]. 計算機研究與發展, 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)(范小芹, 蔣昌俊, 方賢文, 等. 基于離散微粒群算法的動態Web服務選擇[J]. 計算機研究與發展, 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. 機器學習[M]. 曾華軍, 張銀奎, 等譯. 1版. 北京: 機械工業出版社, 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)(范小芹, 蔣昌俊, 王俊麗, 等. 隨機QoS感知的可靠Web服務組合[J]. 軟件學報, 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

國家自然科學基金項目(61273291，61673249)；山西省回國留學人員科研資助項目(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