基于深度強化學習的QoS感知Web服務組合

高文斌，王 睿，王田豐，祖家琛，胡谷雨

(陸軍工程大學 指揮控制工程學院，江蘇 南京 210007)

0 引 言

面向服務的計算(service-oriented computing，SOC)和面向服務的架構(service-oriented architecture，SOA)的出現，為如何實現軟件模塊的解耦提供了新的思路[1]。Web服務具有獨立運行、可互操作的特性[2]。步入云計算時代以后，相當一部分企業以服務的形式在互聯網上發布產品供用戶使用，致使Web服務的數量迅速增長。截至2020年12月，僅ProgrammableWeb網站上所提供的可用Web服務數量已經達到了22 200個。這些Web服務根據功能不同進行分類，如：支付類、查詢類、天氣類等。在功能相似的情況下，服務質量(quality of service，QoS)成為衡量Web服務優劣的重要指標。用于衡量服務的QoS的指標主要包括：響應時間、可用性、可靠性、吞吐量、價格以及調用成功率等[3]。Web服務組合不需要完全重新開發滿足用戶需求的新軟件，僅根據用戶的功能性需求，完成符合一定邏輯規律的現有服務組合。這種方法在有效降低開發成本的同時，縮短開發周期，進而滿足用戶時效性要求。但是，如何在規模日趨龐大的服務組合場景下，提高組合服務的QoS，是服務組合問題的研究熱點。

學術界對QoS感知的服務組合問題已經做了很多深入研究[4-10]，求解方法主要以進化計算算法為主，包括改進的遺傳算法及粒子群算法等。

郭星等人[11]提出了一種基于粒子群算法的動態服務組合方法FWPSO。通過增加種群多樣性來提高搜索性能，并在此基礎上進行了防止早熟收斂處理，實驗證明該方法相比于傳統粒子群算法在搜索效率上有顯著提升；張以文等人[4]提出了一種融合Skyline技術的遺傳粒子群算法。通過Skyline技術降低問題的求解空間。應用種群相似性和遺傳操作避免早熟收斂，實驗表明，該算法的收斂速度快于傳統粒子群算法；魯城華等[5]提出了一種基于遺傳算法的服務組合方法MADMAGA，通過局部搜索策略提高算法收斂速度，實驗表明，該算法在應對小規模服務組合場景時搜索效率高，模型收斂速度快；Sun等人[6]提出了基于時間序列預測和遺傳算法結合的模型ARIMA+GA解決服務組合問題，通過對服務QoS記錄做預測來提升服務QoS的準確性，并通過遺傳算法來求解模型。實驗結果表明，組合服務的QoS優于傳統遺傳算法；Rodrigo等人[9]考慮了服務QoS動態性，提出一種基于自回歸積分移動平均(ARIMA)的方法預測服務的QoS,然而ARIMA方法要求數據具有平穩性[10]。當QoS趨于高度動態化后，該方法的預測能力可靠性有待驗證。Wang等人[12]提出將強化學習應用到服務組合場景中，將skyline技術與Q-learning算法結合，建立了一種強化學習服務組合模型以解決大規模服務組合問題，但是該方法忽略了服務QoS的動態性。

基于進化計算算法的服務組合算法在應對小規模服務組合問題時，算法效率相對較高，但是面對大規模服務組合問題時，仍然存在模型過早收斂、算法尋優能力差的問題，導致輸出的組合服務QoS性能低下。在歷史QoS數據利用方面，由于服務調用頻率不固定，歷史QoS數據在時序上不平穩，現有基于預測的方法對于歷史數據的利用準確性不高。該文針對大規模服務組合問題提出一種基于深度強化學習的模型，同時，考慮到服務歷史QoS數據的利用問題，提出一種基于卷積網絡的方法，將服務歷史QoS數據充分利用，以保證QoS數據的準確性。

1 Web服務組合模型

1.1 服務組合的形式化表示

服務組合的目標是對用戶需求進行拆分，而后在服務庫中尋找合適的服務組件，并按照一定的邏輯順序組合成相應的組合服務。用戶的輸入包括兩方面：功能性需求、非功能性需求。如：“功能需求：旅行計劃制定”，“非功能性需求：費用低于5 000元”。拆分后的功能性需求被描述為一個工作流，工作流有多種結構。如：順序、并行、循環、選擇等。圖1所示的是包含順序及并行兩種結構的工作流，以及根據該工作流進行服務組合的過程。

圖1 服務組合場景

定義1：Web服務。

Web服務定義為一個四元組：

ws=

其中，ID為Web服務的在互聯網上的唯一標識。Inp,Outp分別表示服務的輸入規范和輸出結果。QoS=為一個五元組，其中rt(response time)為響應時間，表示用戶發出調用請求至收到服務響應所消耗的時間，單位為“s”；rl(reliability)表示服務可靠性，文中將可靠性定義為：{“1”，“2”，“3”，“4”},分別對應{“好”，“較好”，“一般”，“差”}四個級別。t(throughout)表示服務吞吐量，單位為“MB”。p(price)表示服務調用的價格，單位為“元”。av(availability)={“0”，“1”}，表示服務可用性，“1”表示服務可用，“0”表示不可用。

定義2：組合Web服務。

組合Web服務定義為一個四元組：

WSCS=

Web服務分布式部署在各個服務提供商的服務器上，用戶通過網絡訪問部署在各個服務器上的服務。這樣的“部署-使用”方式帶來的問題是部分QoS指標會受到服務器負載、通信鏈路狀態的影響[12]。例如：當服務器負載過大或者通信鏈路擁塞時，Web服務的響應時間便會增加。因此，該文將服務組合問題建模為一個不確定環境下的多階段決策優化問題。

表1 不同工作流順序組合服務QoS屬性計算方法

1.2 馬爾可夫決策過程

馬爾可夫決策過程(Markov decision process，MDP)是一種通過交互式學習來實現目標的理論框架，也是強化學習(reinforcement learning，RL)問題在數學上的理想化形式[13]。在一個馬爾可夫決策過程中，進行學習及實施決策的對象稱為智能體(agent)；智能體之外，所有與其相互作用的事物都被稱為環境(environment)。智能體與環境持續進行交互，根據從環境中獲得的反饋來不斷調整自身行動策略，以此最大化長期收益。一個馬爾可夫決策過程可以用圖2表示。

圖2 馬爾可夫決策過程抽象

定義3：馬爾可夫決策過程。

馬爾可夫決策過程可以形式化定義為一個五元組：

MDP=

(1)S={s1,s2,…,sn}表示狀態集，表示環境中智能體所能觀察到的所有狀態，n為狀態的總數。

(3)P為狀態轉移函數，P(s'|s,a)表示智能體在狀態s下執行動作a(a∈A)后，狀態轉移到s'的概率值；s表示智能體當前狀態，s'表示智能體在執行動作后，跳轉到的下一個狀態。

(4)R為獎勵函數，當動作a(a∈A)被執行后，環境從狀態s轉移到后繼狀態s'，智能體所獲得的獎勵值R=r(s'|s,a)。

(5)G表示回報，是智能體所能獲得的獎勵的總和。

定義4：策略(policy)與值函數(value function)。

策略π是狀態S到動作A的映射(S→A)。π(s)=a表示環境狀態為s條件下，智能體依據策略π進行決策，執行動作a。

值函數表示在一個確定的策略π及給定獎勵函數R的情況下，當前狀態的獎勵以及未來根據策略的決策所能得到的總獎勵的期望。數學表達見公式(1)：

Vπ(s|R)=R(s)+γVπ(s')

(1)

其中，參數γ∈[0,1]被稱為折扣率，用來權衡未來獎勵對累積獎勵的影響。

馬爾可夫決策過程中，智能體的目標就是在所有的策略中尋找出最優策略以在每個狀態獲得最大的值函數值。形式化表達如公式(2)：

(2)

1.3 基于馬爾可夫決策的服務組合模型MDPWSC

基于馬爾可夫決策模型，服務組合可以抽象為一個五元組MDPWSC=。各參數定義如下：

T={t1,t2,…,tn}為工作流，是智能體的狀態集合。工作流是對用戶功能性需求拆分成n個子功能后的抽象描述，其中ti表示第i個子功能，n表示用戶功能性需求所拆分成的子功能的總數。例如：用戶功能性需求為“旅行計劃制定”。可將其拆分為：t1=“訂車票”、t2=“訂酒店”、“t3=景點購票”、t4=“訂車票”四個流程。

P(t'|ws,t)表示狀態轉移概率，表示智能體在狀態t下，選擇動作ws，狀態轉移到t'的概率。t'表示智能體在執行完任意動作后跳轉到的后續狀態。

R=r(t'|ws,t)表示獎勵函數，表示智能體在狀態t下，選擇動作ws，狀態轉移到t'，環境給予智能體的獎勵。

G表示組合服務的QoS，也是服務組合問題的優化目標。

2 算法描述

在動態網絡環境中，服務的QoS指標將隨著網絡的動態性改變[14]。如何通過現有的調用記錄發掘服務最真實的QoS值是決定能否完成最符合用戶QoS需求的服務組合的關鍵。同時，隨著應用場景越來越復雜，如何應對大規模服務組合也是急需解決的問題。

2.1 基于CNN的獎勵函數設計

獎勵函數是強化學習中非常重要的變量之一，獎勵函數的設定對最終優化的目標起重要作用。在基于強化學習QoS感知的服務組合問題中，為了最終得到最優的組合服務QoS,常把獎勵函數設定為先對子服務的QoS值歸一化，而后對歸一化后的QoS值加權求和[10]。由于不同的QoS屬性有不同的取值范圍，現有方法都是首先利用公式(3)對各個屬性值做歸一化處理，而后采用公式(4)對多個QoS屬性加權求和得到結果作為獎勵值。

(3)

(a)：當QoS和R成正相關；(b)當QoS和R成負相關。

(4)

其中，ri為QoS指標對應的獎勵值，ωi為指標對應的權值，k為QoS指標總數。

這種方法存在的問題是需要人為設定各個指標之間的權重關系ωi，準確性不高，不能反映各QoS之間的真實聯系。同時，Web服務的每次調用都會產生相應的QoS記錄，傳統的方法只選取最近一條調用記錄作為計算獎勵值的依據，對于服務歷史QoS數據的利用過于粗糙。以上兩點原因將導致計算出的獎勵值可靠性不足，并最終導致組合服務的QoS可靠性差。

深度學習(deep learning，DL)和神經網絡(neural network)是當下學術研究的熱點，并且在多個領域取得了顯著的成果。深度學習算法通過多個神經元組成神經層，再由多個神經層組成復雜的神經網絡，進而解決復雜的問題。從數據集[15]中可以獲得單個服務關于多個QoS指標的歷史數據。該文利用卷積神經網絡(convolutional neural network，CNN)在特征提取上的突出優勢[16]，將單個服務的多次調用記錄以及相應QoS指標組合成二維矩陣輸入網絡，通過卷積網絡提取服務多條調用記錄之間的相互聯系特征，以及各個QoS指標之間的相互關系特征，進而輸出服務對應的真實QoS值。

網絡結構如圖3所示。

圖3 CNN網絡結構

輸入層為在狀態t'下被選中的服務的多次調用記錄與QoS指標組成的二維矩陣，實驗中選擇30條服務調用記錄中五個QoS指標的值組成30*5的輸入矩陣，經過一層卷積核大小為9*1*1的卷積層提取多條記錄之間的特征和一層卷積核大小為5*3*1的卷積層進一步提取多條記錄之間的特征以及提取各個QoS指標之間的特征，而后經過全連接層，最終輸出t'狀態下，被選中服務對應的獎勵值R。相比起傳統的利用某一條QoS記錄計算獎勵值的方法，基于CNN的方法可以將多條QoS屬性信息利用起來，更加能反映服務的真實QoS情況。

2.2 基于深度強化學習的服務組合算法ADR-WSC

Q-Learning算法[12]是求解強化學習問題的基本方法之一，其基本思想是通過一張Q表來存儲“動作-值”函數Q(t,ws)的值。對應的Q值是對真實獎勵的評估。算法通過比較Q值的估計值和實際值，不斷更新Q表，直至估計值接近真實值。在服務組合問題中，其迭代公式如下：

Q(t,ws)=Q(t,ws)+α(r(t'|t,ws)+γmaxQ(t',ws')-Q(t,ws))

(5)

其中，α為學習率，ws'為t'狀態下選擇的動作。

當面臨解決大規模離散空間或連續狀態空間的問題時，例如：待解決問題的狀態空間大小為5，每個狀態對應的動作空間大小為10時，這時的Q表是一個5*10的矩陣，計算和更新開銷相對較小，訓練和后續查表開銷不大。但應用到實際生產領域當中，一個子功能對應的可選服務往往成百上千個,工作流的長度也數以十甚至百計。對于一個工作流長度為30，即狀態空間大小為30，每個狀態空間對應的動作空間大小為500時，將會形成50030種組合方案，這是個巨大的搜索空間。并且，一次訓練過程就需要經過50030次計算。在網絡波動的情況下，光是計算開銷就足以導致計算結果失效。因此，在Q-Learning的基礎上，加入了深度網絡(deep neural network，DNN)替代Q表，以解決Q-Learning在面對大規模問題時的瓶頸[17]。

基于強化學習良好的決策能力和卷積網絡的特征提取能力以及神經網絡本身強大的表征能力，該文提出了一種基于深度強化學習的QoS自適應服務感知算法：“Adaptive Deep Reinforcement Learning-Web Service Composition(ADR-WSC)”。為了解決獎勵值R的可靠性問題，采用了卷積神經網絡代替傳統的直接對QoS記錄加權求和的方式；為了解決大規模“狀態-動作”值存儲于Q表中導致算法性能低下的問題，采用了深度神經網絡替代傳統的Q表。綜合上述兩點改進，傳統的Q-Learning中Q值的迭代更新公式應轉化為：

Q(t,ws)=Q(t,ws)+α(CNN(t'|t,ws)+

γmaxDNN(t',ws')-Q(t,ws))

(6)

算法具體過程如下：

算法：服務組合算法ADR-WSC。

(1)初始化“動作-值”函數Q(T,ws,ω)的參數ω、加載CNN(T,ws)網絡已保存的訓練參數。加載隨機探索率ε、學習率α、工作流長度T、初始化經驗回放區域D,確定訓練輪數MAX_EPISODE，以及網絡訓練的BATCH_SIZE

(2)For each episode in MAX_EPISODE：

(3)FortiinT：

(4)在工作流ti對應的可用服務集A(ti)中根據ε-greedy策略選取出相應的服務ws

(5)綁定服務，獲得下一個狀態t'，并根據CNN(ti,ws)網絡計算出對應的獎勵r(t'|ws,t)

(6)ti=t'，根據ti,ws計算Q值，公式如下:

y(ti,ws)=

(7)將[ti,ws,y(ti,ws)]存入經驗回放區

(8)判斷緩沖區長度是否達到BATCH_SIZE，若達到，則將經驗區中的數據喂入網絡訓練，利用梯度下降算法更新Q(T,ws,ω)中的所有參數。后清空緩沖區。否則，結束此次循環

(9)End for

(10)End for

3 實驗與分析

3.1 實驗設置

實驗數據集的基礎為公共有效數據集QWS[15]，QWS數據集中的所有數據均為真實網絡中可用Web服務被調用后獲得的統計數據。包含2 500個Web服務及其對應的11個QoS屬性值，實驗中選用了數據集中的四個QoS屬性：響應時間、可用性、可靠性、吞吐量，并擴充了服務的價格屬性。網絡使用深度學習框架Tensorflow搭建，實驗在一臺操作系統為Win10，CPU為E3-1226，內存為16G，GPU為NVDIA GT-1030的機器上運行。

3.2 結果分析

(1)初始探索率對總收益的影響。

用于預測獎勵R的CNN網絡是在ADR-WSC算法運行之前就已經完成訓練的，因此算法迭代過程中，不需要再對其做額外的訓練。而用于擬合‘動作-價值’函數的DNN網絡則是在線訓練的，經驗回放區域的容量大小、智能體的隨機探索率等超參數會很大程度上影響實驗結果，因此，實驗中先驗證了初始探索率ε的大小對總收益(即組合模型的整體QoS)的影響。

圖4 探索率對總收益值的影響

圖4顯示的是服務組合模型中流程數為10，每個流程對應有300個備選服務時，探索率ε=0.3、ε=0.5以及ε=0.8時，算法收斂時最大收益的對比。實驗中固定了學習率α=0.9。經驗區容量為150。為了模型更快的收斂，實驗中還采用了探索率遞減的方法。算法迭代的過程中，探索率會隨著迭代輪數逐漸降低，實驗中設置的探索率值僅僅是算法開始迭代時的探索率。結果表明，當模型收斂時，在ε=0.3和ε=0.5情況下，智能體獲得的總的收益值只有不到17，而ε=0.8時，收益值達到18.5以上。筆者認為，讓智能體前期更多地探索環境知識，積攢更多的訓練數據，更加有利于模型的準確性。因此，后續實驗將采取探索率ε=0.8。

(2)經驗區容量對算法收斂速度的影響。

經驗區容量直接決定了喂入網絡的訓練數據量，對算法收斂起了重要作用，因此，文中接著驗證了經驗區容量大小對于模型收斂的影響。圖5顯示的是服務組合模型中流程數為10，每個流程對應有300個備選服務時，不同經驗區容量對算法收斂過程的影響。實驗中固定了探索率ε=0.8，學習率α=0.9。結果表明，在探索率為0.8的情況下，經驗區容量取150、200、250、300均可以保證算法收斂到最優解。從節省資源的角度上來說，選擇150更合適。因此，后續實驗中，選擇經驗區容量為150。

圖5 經驗區容量對總收益的影響

(3)組合服務QoS對比。

在確定超參數以后，還對模型的整體性能做了驗證。首先是算法收斂后的QoS值對比。算法的核心目的是提供QoS更優的組合服務，因此組合服務的QoS是模型最重要的指標。實驗中選取了基于粒子群算法的FWPSO算法[11]、基于時間序列預測和遺傳算法的ARIMA+GA算法[6]做對比。同時，為了獲取實際最優組合服務QoS，實驗中還使用了窮舉法求解作為參照。

圖6 各算法在不同規模服務組合場景中 QoS值對比

圖6顯示的是ARIMA+GA、FWPSO、ADR-WSC以及窮舉算法在求解服務組合問題模型后，輸出的組合服務QoS值。需要說明的是：實驗中對每種算法運行了多次，取收斂后最低的QoS值作為對比數據，這樣做的好處是：可以明確獲知算法在最壞的情況下輸出的結果。從圖中可以看出，當單個流程的候選服務數小于等于250時，ARIMA+GA、FWPSO、ADR-WSC均可以求得最優解。當備選服務大于250時，ARIMA+GA、FWPSO出現提前收斂至局部最優的情況，無法找到全局最優解。而ADR-WSC算法迭代的過程中，不斷更新網絡，即使問題規模擴大，也可以找出最優解。

(4)算法時間開銷對比。

由于每個算法收斂時迭代輪數不同，實驗中對比的是當模型收斂時，所需要的最小時間開銷。實驗中沒有將窮舉法的運行時間繪制在圖上，因為其時間開銷跟其他三種算法不在一個量級上。從圖7中可以看出，當單個流程的備選服務數量越來越多的時候，三種算法的時間開銷都是隨著問題規模遞增的，但是ADR-WSC算法的時間開銷均低于其他兩種算法，ADR-WSC算法運行速度快可能的原因是：當完成網絡訓練以后，算法執行過程中，只需要通過網絡完成特定數據的運算即可，是針對固定數據的運算，而不像其他兩種算法每次運行都必須迭代所有數據。

圖7 GA,PSO,ADR-WSC運行時間對比

4 結束語

提出了一種基于深度強化學習的自適應優化方法ADR-WSC來解決大規模QoS感知的Web服務組合優化問題，考慮了多個QoS屬性之間的相互關系以及如何利用Web服務多條歷史調用記錄分析Web服務QoS可靠性，并改進了基于傳統Q-Learning的算法，以解決大規模服務組合問題。實驗結果表明，該方法在組合服務QoS上優于傳統尋優方法，并且在遇到大規模服務組合場景時，具有更高的可擴展性，能夠有效地處理大規模服務組合問題。

云計算發展速度越來越快，Web服務的數量在迅猛增長，對于服務組合問題來說，每個子流程的候選服務數量越多，完成組合的難度越大，算法運行開銷也越久。如果用戶對于時效要求進一步提高，比如：當應用場景為高速智能駕駛時，對于算法的時效要求更為嚴格。今后將進一步研究如何提高超大規模服務組合低時耗的問題。