基于SMDP模型的Web服務(wù)組合優(yōu)化方法

柴雪霞， 馬學(xué)森，2， 周 雷， 唐 昊，2

（1.合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院，安徽 合肥 230009；2.合肥工業(yè)大學(xué) 安全關(guān)鍵工業(yè)測(cè)控技術(shù)教育部工程研究中心，安徽 合肥230009）

隨著網(wǎng)絡(luò)上Web服務(wù)數(shù)量的急劇增加，在動(dòng)態(tài)Web服務(wù)組合過程中，提供相同功能的 Web服務(wù)大量出現(xiàn)，對(duì)于眾多功能相同的Web服務(wù)，服務(wù)選擇的標(biāo)準(zhǔn)不僅要滿足功能需求，還要滿足非功能需求，因此QoS就成為了服務(wù)選擇的一個(gè)標(biāo)準(zhǔn)。傳統(tǒng)的Web服務(wù)架構(gòu)中因缺乏對(duì)QoS的描述而難以從功能相同的眾多服務(wù)中為用戶選擇最佳服務(wù)［1－2］，因此目前基于QoS的服務(wù)選擇成為研究的重點(diǎn)?；赒oS的Web服務(wù)組合的選擇問題的研究主要分為Web服務(wù)組合模型的建立和針對(duì)具體模型服務(wù)選擇算法的研究［3］。

在Web服務(wù)組合模型方面，文獻(xiàn)［4］提出了基于Petri網(wǎng)的Web服務(wù)組合模型，但是在服務(wù)選擇時(shí)沒有考慮服務(wù)的QoS。文獻(xiàn)［5－6］利用離散時(shí)間的馬爾可夫決策過程（Markov Decision Process，簡(jiǎn)稱MDP）對(duì)服務(wù)組合建模，把QoS各個(gè)指標(biāo)的綜合值作為即時(shí)報(bào)酬，然后用Bellman最優(yōu)方程求解最優(yōu)策略，但在求解過程中需要了解各個(gè)狀態(tài)的轉(zhuǎn)移概率，而轉(zhuǎn)移概率在實(shí)際系統(tǒng)中是很難得到的，并且不能解決連續(xù)時(shí)間的服務(wù)組合問題。在服務(wù)選擇算法方面，文獻(xiàn)［7］提出了適用于不同應(yīng)用場(chǎng)景的局部?jī)?yōu)化與全局優(yōu)化2種算法，局部?jī)?yōu)化算法只對(duì)組合中的某個(gè)任務(wù)有QoS約束，全局優(yōu)化算法對(duì)組合中的所有任務(wù)都有QoS約束，但相對(duì)于前者來講，后者計(jì)算量更大。文獻(xiàn)［8］使用遺傳算法從適應(yīng)度函數(shù)的靜態(tài)懲罰、動(dòng)態(tài)懲罰及拉伸3個(gè)方面對(duì)系統(tǒng)優(yōu)化性能進(jìn)行比較。本文在文獻(xiàn)［6］的基礎(chǔ)上，借鑒了文獻(xiàn)［7］中QoS模型的優(yōu)點(diǎn)，對(duì)服務(wù)組合模型進(jìn)一步擴(kuò)展，使用有限狀態(tài)連續(xù)時(shí)間SMDP對(duì)服務(wù)組合建模，利用模型無關(guān)的Q學(xué)習(xí)算法求解，得到最優(yōu)的服務(wù)組合。

1 Web服務(wù)組合

1.1 Web服務(wù)組合系統(tǒng)

不同標(biāo)準(zhǔn)和研究組織對(duì)Web服務(wù)組合的定義不同，文獻(xiàn)［9］給出了一個(gè)相對(duì)完整和通用的定義，即Web服務(wù)組合是利用Internet上分布的現(xiàn)有Web服務(wù)，根據(jù)用戶需求，自動(dòng)選擇用戶所需要的服務(wù)，在服務(wù)組合支撐平臺(tái)的支持下，按照一定的規(guī)則協(xié)同完成服務(wù)請(qǐng)求。

Web服務(wù)組合系統(tǒng)包含2個(gè)用戶角色（服務(wù)請(qǐng)求者和服務(wù)提供者）和5個(gè)部件（翻譯器、組合管理器、執(zhí)行引擎、服務(wù)匹配器和UDDI）。Web服務(wù)提供者把服務(wù)信息注冊(cè)發(fā)布到UDDI，當(dāng)服務(wù)請(qǐng)求者提出請(qǐng)求時(shí)，翻譯器接受用戶的請(qǐng)求，并將其請(qǐng)求轉(zhuǎn)換為機(jī)器能夠識(shí)別的語(yǔ)義表達(dá)，然后提交給組合管理器。組合管理器接受語(yǔ)義解釋后，結(jié)合UDDI中的服務(wù)描述生成抽象的組合方案，并提交給執(zhí)行引擎。執(zhí)行引擎把抽象的服務(wù)描述發(fā)送給服務(wù)匹配器，服務(wù)匹配器結(jié)合UDDI中的QoS描述，把尋找到的最適合的具體 Web服務(wù)句柄返回給執(zhí)行引擎。通過組合方案和查找到的具體 Web服務(wù)，執(zhí)行引擎去調(diào)用和監(jiān)督Web服務(wù)的執(zhí)行，最后系統(tǒng)把執(zhí)行結(jié)果返回給服務(wù)請(qǐng)求者。具體的實(shí)現(xiàn)過程如圖1所示。

圖1 Web服務(wù)組合系統(tǒng)

1.2 Web服務(wù)的QoS模型

目前學(xué)術(shù)界和工業(yè)界對(duì)QoS的認(rèn)識(shí)有一定的差別，其中國(guó)際標(biāo)準(zhǔn)ISO8402和ITUE.800對(duì)QoS的定義更準(zhǔn)確地反映了Web服務(wù)的QoS特點(diǎn)，同時(shí)也反映了用戶的實(shí)際需要。QoS由一些非功能屬性組成，為了討論方便，本文的QoS模型只采用了有限的若干指標(biāo)，以下分別給出這些指標(biāo)的定義：

（1）服務(wù)費(fèi)用C（S）指調(diào)用服務(wù)S所必須支付的費(fèi)用，它由服務(wù)提供商指定，是一個(gè)確定的值，不隨環(huán)境的動(dòng)態(tài)改變而變化。

（2）響應(yīng)時(shí)間T（S）指服務(wù)請(qǐng)求者從發(fā)送服務(wù)請(qǐng)求到收到結(jié)果的延遲時(shí)間，主要包括服務(wù)處理時(shí)間和網(wǎng)絡(luò)傳輸時(shí)間，其中網(wǎng)絡(luò)傳輸時(shí)間又可以分為發(fā)送請(qǐng)求的傳輸時(shí)間tra1和返回結(jié)果的傳輸時(shí)間tra2，服務(wù)處理時(shí)間表示為pr，因此響應(yīng)時(shí)間T（S）＝tra1＋pr＋tra2。

（3）可用性A（S）表示服務(wù)S可以被訪問，即可用的概率，可以通過服務(wù)S的平均無故障時(shí)間MTTF（S）和平均修復(fù)時(shí)間 MTTR（S）來定義，因此A（S）

（4）可靠性R（S）表示服務(wù)請(qǐng)求被成功響應(yīng)的概率，并通過以往服務(wù)被成功調(diào)用的次數(shù)Nc（S）與服務(wù)被調(diào)用的總次數(shù)Ninvoke比值來衡量，即服務(wù)S的可靠性R（S）＝Nc（S）／Ninvoke。

QoS指標(biāo)可以分為2種：① 正向質(zhì)量指標(biāo)，即指標(biāo)值越大，服務(wù)質(zhì)量越好，如可用性和可靠性；② 負(fù)向質(zhì)量指標(biāo)，即指標(biāo)值越大，服務(wù)質(zhì)量越差，如服務(wù)費(fèi)用和響應(yīng)時(shí)間。因此為了使各個(gè)指標(biāo)對(duì)其性能影響一致，要對(duì)QoS指標(biāo)歸一。正向指標(biāo)歸一為：

負(fù)向指標(biāo)歸一為：

根據(jù)歸一化后的值可以計(jì)算每個(gè)服務(wù)S的綜合評(píng)價(jià)值，于是得到其中，二維矩陣Q為一組服務(wù)的QoS指標(biāo)值；i為服務(wù)個(gè)數(shù)；j為指標(biāo)的個(gè)數(shù)為第j個(gè)指標(biāo)的最大值為第j個(gè)指標(biāo)的最小值；wj為每個(gè)指標(biāo)的權(quán)值，并有QoS（S）值越大，說明服務(wù)質(zhì)量越好。

2 Web服務(wù)組合的數(shù)學(xué)模型和優(yōu)化算法

文獻(xiàn)［6］考慮了離散時(shí)間的 MDP，而在實(shí)際的服務(wù)組合中，系統(tǒng)在各個(gè)狀態(tài)的逗留時(shí)間服從一般分布，因此Web服務(wù)組合的優(yōu)化問題可建模為連續(xù)時(shí)間SMDP來研究。

2.1 Web服務(wù)組合的SMDP模型

Web服務(wù)組合將現(xiàn)有的一組服務(wù)按照一定的邏輯進(jìn)行集成，從而更好地滿足用戶的需求。靜態(tài)服務(wù)組合在創(chuàng)建一個(gè)新服務(wù)前就了解用戶的需求，在服務(wù)提供給用戶后不再發(fā)生變化，而動(dòng)態(tài)服務(wù)組合則根據(jù)運(yùn)行時(shí)出現(xiàn)的需求自動(dòng)生成組合流程，并能夠自動(dòng)查找、組合服務(wù)。本文是在自動(dòng)生成流程結(jié)構(gòu)的基礎(chǔ)上研究服務(wù)組合的，因此屬于動(dòng)態(tài)服務(wù)組合。Web服務(wù)組合通常有4種結(jié)構(gòu)［5］：順序、并行、選擇和循環(huán)結(jié)構(gòu)。根據(jù)文獻(xiàn)［10］，這4種結(jié)構(gòu)可以轉(zhuǎn)化為如圖2所示的順序結(jié)構(gòu)。其中ti表示服務(wù)組合中的一個(gè)任務(wù)節(jié)點(diǎn)。

圖2 順序結(jié)構(gòu)

Web服務(wù)組合可以看成是從初始狀態(tài)到終止?fàn)顟B(tài)的任務(wù)流程圖，根據(jù)生成的流程結(jié)構(gòu)，系統(tǒng)分別為每一個(gè)任務(wù)節(jié)點(diǎn)選擇具體的Web服務(wù)，如果為當(dāng)前的任務(wù)節(jié)點(diǎn)選擇服務(wù)成功，則轉(zhuǎn)到下一個(gè)任務(wù)節(jié)點(diǎn)，否則繼續(xù)為當(dāng)前的任務(wù)節(jié)點(diǎn)選擇服務(wù)，直到成功為止。

設(shè)Tn表示第n個(gè)決策時(shí)刻，n＝0，1，2，…，N。系統(tǒng)狀態(tài)用各個(gè)任務(wù)節(jié)點(diǎn)的執(zhí)行情況來表示，對(duì)于包含m個(gè)任務(wù)的流程圖，系統(tǒng)狀態(tài)用m元組〈t1，t2，…，ti，…，tm〉表示，第n個(gè)決策時(shí)刻系統(tǒng)的狀態(tài)記作sn，其中ti＝1，2，…，m∈｛0，1｝，ti＝1表示已經(jīng)為節(jié)點(diǎn)ti綁定了具體的 Web服務(wù)，ti＝0表示還未為節(jié)點(diǎn)ti綁定具體服務(wù)。假設(shè)第n個(gè)決策時(shí)刻采取的行動(dòng)（即調(diào)用的服務(wù)）為an，狀態(tài)sn下的行動(dòng)集A（sn）是任務(wù)節(jié)點(diǎn)可調(diào)用的候選服務(wù)，所有狀態(tài)下的行動(dòng)集構(gòu)成了系統(tǒng)的行動(dòng)集A，其中每個(gè)任務(wù)下的候選服務(wù)功能相同而QoS不同，不同任務(wù)對(duì)應(yīng)的候選服務(wù)集是不同的。根據(jù)文獻(xiàn)［5］，把調(diào)用服務(wù)的可靠性作為轉(zhuǎn)移概率，則系統(tǒng)在當(dāng)前狀態(tài)sn以psnsn＋1（an）＝R（an）的概率轉(zhuǎn)移到下一狀態(tài)，以1－psnsn＋1（an）的概率停留在當(dāng)前狀態(tài)。若服務(wù)請(qǐng)求時(shí)間、處理服務(wù)時(shí)間和返回處理結(jié)果時(shí)間均服從指數(shù)分布，則在狀態(tài)sn的逗留時(shí)間Fsnsn＋1（t，an）服從Erlang分布［11］，根據(jù)文獻(xiàn)［12］，通過 Q（sn，sn＋1，an，t）＝psnsn＋1（an）Fsnsn＋1（t，an）可以求得半馬爾可夫核，此式表示系統(tǒng)在狀態(tài)sn采取行動(dòng)an，轉(zhuǎn)移到下一狀態(tài)sn＋1前所需時(shí)間小于或等于t的概率。

從Tn到Tn＋1共經(jīng)歷3個(gè)階段：發(fā)送服務(wù)請(qǐng)求、處理服務(wù)和返回處理結(jié)果。其中，tra1和tra2分別表示發(fā)送服務(wù)請(qǐng)求時(shí)間和返回處理結(jié)果時(shí)間，pr表示處理服務(wù)的時(shí)間，因此有Tn＋1＝Tn＋tra1＋pr＋tra2。系統(tǒng)運(yùn)行的時(shí)間軸如圖3所示。

圖3 系統(tǒng)運(yùn)行時(shí)間軸

由于服務(wù)組合包含有限個(gè)任務(wù)節(jié)點(diǎn)，因此本文采用有限時(shí)段連續(xù)時(shí)間SMDP。定義在策略v下的有限時(shí)段折扣代價(jià)準(zhǔn)則為：

其中，G（iN）為最終狀態(tài)的代價(jià)；g（sn，an，sn＋1）定義為系統(tǒng)在當(dāng)前狀態(tài)sn采取行動(dòng)an轉(zhuǎn)移到下一狀態(tài)sn＋1之前的單位時(shí)間期望代價(jià)；α為折扣因子，當(dāng)α＞0時(shí)表示狀態(tài)s的折扣代價(jià)，當(dāng)α＝0時(shí)，表示狀態(tài)s的累積代價(jià)。優(yōu)化目標(biāo)就是在策略空間中找到一個(gè)最優(yōu)策略，使得（3）式代價(jià)最小。

2.2 服務(wù)組合的Q學(xué)習(xí)算法

文獻(xiàn)［5－6］使用數(shù)值迭代的方法求解最優(yōu)策略，而當(dāng)系統(tǒng)狀態(tài)空間巨大時(shí)，數(shù)值迭代通常存在著“維數(shù)災(zāi)”問題。因此為了避免此問題的出現(xiàn)，本文采用Q學(xué)習(xí)方法，其最大的優(yōu)點(diǎn)是不依賴系統(tǒng)模型，為解決系統(tǒng)信息未知或不完全知的情況提供了便利。

假設(shè)系統(tǒng)從狀態(tài)sn轉(zhuǎn)移到狀態(tài)sn＋1，在此期間分別會(huì)產(chǎn)生發(fā)送請(qǐng)求服務(wù)代價(jià)、處理服務(wù)代價(jià)和返回處理結(jié)果代價(jià)。此外，在狀態(tài)sn調(diào)用服務(wù)后會(huì)產(chǎn)生一個(gè)立即報(bào)酬，設(shè)Can為采取行動(dòng)an所對(duì)應(yīng)的立即報(bào)酬，則累積代價(jià)的計(jì)算公式為：

其中，f′（sn，an，sn＋1）為系統(tǒng)從決策時(shí)刻 Tn到Tn＋1所獲得的累積代價(jià)；k1為處理服務(wù)單位時(shí)間代價(jià)；k2為在網(wǎng)絡(luò)上傳輸單位時(shí)間代價(jià)。由于Web服務(wù)的不確定性，在調(diào)用的過程中可能成功也可能失敗，若調(diào)用服務(wù)成功，Can＝QoS（S），否則Can＝0，QoS（S）指Web服務(wù)的綜合評(píng)價(jià)值。

在學(xué)習(xí)優(yōu)化過程中，從Web服務(wù)組合的任意狀態(tài)出發(fā)到終止?fàn)顟B(tài)作為一個(gè)仿真片段（episode），記為h。在仿真片段結(jié)束后，折扣準(zhǔn)則下差分dh的計(jì)算公式為：

其中，T0＝0為第h個(gè)仿真片段的第n步；仿真片段的長(zhǎng)度為lh＋1；Qα為第h個(gè)仿真片段的初始狀態(tài)行動(dòng)對(duì)值。

其中，γh為學(xué)習(xí)步長(zhǎng)。

在Q學(xué)習(xí)中對(duì)于行動(dòng)的選取，一般采用εgreedy方法（0≤ε＜1，取接近0的小數(shù)），即在當(dāng)前狀態(tài)s以1－ε的概率選取當(dāng)前最優(yōu)行動(dòng)a＊∈，以ε的概率隨機(jī)選擇一個(gè)行動(dòng)。

Q學(xué)習(xí)具體算法過程為：

（1）初始化參數(shù)。令h＝0，設(shè)置折扣因子α，學(xué)習(xí)步長(zhǎng)γh，學(xué)習(xí)片段數(shù)H，初始化所有狀態(tài)行動(dòng)對(duì)的Q值。

（6）h：＝h＋1，若h＝H，學(xué)習(xí)結(jié)束，否則轉(zhuǎn)步驟（2）。

3 仿真結(jié)果

鑒于目前沒有相關(guān)的標(biāo)準(zhǔn)平臺(tái)和測(cè)試數(shù)據(jù)集，本文采用隨機(jī)生成的大量數(shù)據(jù)進(jìn)行仿真，在仿真中設(shè)定k1＝40，k2＝20，tra1和tra2均服從參數(shù)為λtra1＝λtra2＝2的指數(shù)分布，pr服從參數(shù)為λpr＝1的指數(shù)分布。

在仿真中設(shè)定服務(wù)組合有10個(gè)任務(wù)，每個(gè)任務(wù)有10個(gè)候選服務(wù)。不同折扣因子下的優(yōu)化曲線如圖4所示，從圖4可以看出，使用Q學(xué)習(xí)算法，能很快收斂到最優(yōu)或次優(yōu)策略。在折扣因子α＝0時(shí)，經(jīng)過450次迭代后，性能逐漸趨于穩(wěn)定，最終策略v＊＝［10，10，1，6，3，7，4，9，3，1］，在該策略下的代價(jià)為2.019 4，其中策略v＊中的數(shù)字代表在不同的任務(wù)下所調(diào)用的具體服務(wù)。

圖4 不同折扣因子的優(yōu)化曲線

為了分析流程中不同任務(wù)數(shù)以及每個(gè)任務(wù)下不同候選服務(wù)數(shù)對(duì)系統(tǒng)計(jì)算代價(jià)的影響，本文對(duì)順序結(jié)構(gòu)分別包含10、20以及最多80個(gè)任務(wù)的流程圖進(jìn)行仿真實(shí)驗(yàn)，其中每個(gè)任務(wù)又分別有10、20以及30個(gè)候選服務(wù)，結(jié)果如圖5所示。

圖5 不同任務(wù)數(shù)和候選服務(wù)數(shù)的代價(jià)

圖5表明隨著任務(wù)數(shù)和候選服務(wù)數(shù)的增加，得到最終策略的計(jì)算代價(jià)也隨之增加。當(dāng)任務(wù)數(shù)小于30個(gè)，候選服務(wù)10～30時(shí)，對(duì)計(jì)算代價(jià)的影響不是很大，但當(dāng)任務(wù)數(shù)大于50個(gè)時(shí)，計(jì)算代價(jià)會(huì)隨著候選服務(wù)數(shù)的增多而劇烈增加。

不同任務(wù)數(shù)和候選服務(wù)數(shù)的情況下組合成功率如圖6所示。由圖6可以看出，使用Q學(xué)習(xí)算法可以得到相對(duì)高的服務(wù)組合成功率。并且服務(wù)組合時(shí)，組合成功率與任務(wù)數(shù)和候選服務(wù)數(shù)都有關(guān)系，在任務(wù)數(shù)確定的情況下，其對(duì)應(yīng)的候選服務(wù)數(shù)10～30時(shí)，對(duì)組合成功率的影響不是很大，但隨著任務(wù)數(shù)的增加，組合成功率會(huì)降低。候選服務(wù)數(shù)較多，組合成功率變化緩慢，說明候選服務(wù)數(shù)越多，系統(tǒng)的性能越穩(wěn)定，但同時(shí)系統(tǒng)的代價(jià)也會(huì)增大，這與實(shí)際是相符合的。

圖6 不同任務(wù)數(shù)和候選服務(wù)數(shù)成功率

在相同的實(shí)驗(yàn)環(huán)境下對(duì)文獻(xiàn)［7］提出的整數(shù)規(guī)劃方法和本文的優(yōu)化方法進(jìn)行比較，結(jié)果如圖7所示。從圖7可以看出，本文的方法具有較高的服務(wù)組合成功率，因?yàn)檎麛?shù)規(guī)劃是靜態(tài)的方法，如果在組合過程中出現(xiàn)服務(wù)失效或者調(diào)用異常，則只能進(jìn)行重規(guī)劃，而本文是動(dòng)態(tài)尋找最優(yōu)規(guī)劃的方法。

圖7 組合成功率的比較

4 結(jié)束語(yǔ)

本文給出了Web服務(wù)組合的實(shí)現(xiàn)過程以及QoS模型，并針對(duì)Internet環(huán)境的動(dòng)態(tài)性和Web服務(wù)的隨機(jī)性，給出了有限狀態(tài)連續(xù)時(shí)間SMDP模型的Web服務(wù)組合學(xué)習(xí)優(yōu)化方法，最后的仿真實(shí)驗(yàn)也說明了該方法的可行性和有效性。另外，可用分層強(qiáng)化學(xué)習(xí)如Option、MAXQ等研究Web服務(wù)組合，可以解決大規(guī)模系統(tǒng)的“維數(shù)災(zāi)”問題，同時(shí)可以加速策略學(xué)習(xí)。

［1］郝軒史，維 峰.基于SOA的Web服務(wù)動(dòng)態(tài)組合研究與實(shí)現(xiàn)［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2008，29（15）：3929－3932.

［2］岳 昆，王曉玲，周傲英.Web服務(wù)核心支撐技術(shù)：研究綜述［J］.軟件學(xué)報(bào)，2004，15（3）：428－442.

［3］袁小玲，李心科.基于雙向動(dòng)態(tài)規(guī)劃質(zhì)量有保障的組合服務(wù)選?。跩］.合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，32（4）：465－469，499.

［4］范貴生，劉冬梅，陳麗瓊，等.可靠服務(wù)組合的協(xié)調(diào)策略與分析［J］.計(jì)算機(jī)學(xué)報(bào)，2008，31（8）：1445－1457.

［5］Gao Aiqiang，Yang Dongqing，Tang Shiwei.Web service composition using Markov decision processes［C］／／Proc of the 6th Int Conf on Web－Age Information Management，LNCS 3739，2005：308－319.

［6］范小芹，蔣昌俊，王俊麗，等.隨機(jī)QoS感知的可靠 Web服務(wù)組合［J］.軟件學(xué)報(bào)，2009，20（3）：546－556.

［7］Zeng Liangzhao，Benatallah B.QOS－aware middleware for Web service composition［J］.IEEE Transaction on Software Engineering，2004，30（5）：311－327.

［8］蔣哲元，韓江洪，王 釗.動(dòng)態(tài)的QoS感知Web服務(wù)選擇和組合優(yōu)化模型［J］.計(jì)算機(jī)學(xué)報(bào)，2009，32（5）：1014－1025.

［9］馮明正.Web服務(wù)組合綜述［J］.計(jì)算機(jī)應(yīng)用與軟件，2007，24（2）：23－27.

［10］Cardoso J，Sheth A，Miller J，et al.Quality of service for workflow and Web service processes［J］.Web Semantics：Science，Services and Agents on the World Wide Web，2004，1（3）：281－308.

［11］胡奇英，劉建庸.馬爾可夫決策過程引論［M］.西安：西安電子科技大學(xué)出版社，2000：94－125.

［12］Tang Hao，Yin Baoqun，Xi Hongsheng.Error bound of optimization algorithms for semi－Markov decision processes［J］.International Journal of Systems Science，2007，38（9）：725－736.