付燕寧, 趙東范, 趙 健

(1. 吉林財經(jīng)大學 信息經(jīng)濟學院, 長春 130122; 2. 吉林大學 計算機科學與技術學院, 長春 130012)

Web環(huán)境的改變可以導致過去是有效的組合服務不再有效, 過去是優(yōu)化的組合服務不再優(yōu)化, 組合服務性能可能會退化甚至無法運行. 文獻[1]根據(jù)將具體服務綁定到組合規(guī)范的時機把基于過程的服務組合分為三類： 1) 在設計時確定具體的服務并將其綁定到組合規(guī)范； 2) 在組合服務執(zhí)行前將過程模型中的任務綁定為服務, 然后引擎再執(zhí)行組合服務； 3) 按照過程模型中任務間的執(zhí)行邏輯, 逐步將過程模型中的任務綁定為服務并進行調用. 后兩類在一定程度上適應了動態(tài)的Web環(huán)境, 但當用戶再次發(fā)出同樣的服務請求時, 則會出現(xiàn)以下問題： 第二類(如文獻[2-3])將以往形成的服務組合當成最終版本, 每當用戶再次發(fā)出服務請求時, 直接利用過去形成的組合服務, 不再探索新的服務組合, 這種處理方式只有對以往組合方案的利用, 而沒有對環(huán)境的探索, 因此不能適應動態(tài)變化的Web環(huán)境； 第三類(如文獻[4-5])將每次組合服務的執(zhí)行都作為一個全新的問題, 重新探索新的環(huán)境形成新的組合服務, 這種處理方式只有對新環(huán)境的探索而缺乏對以往服務組合的利用, 導致增加系統(tǒng)開銷. 這兩類服務組合方式均缺乏對動態(tài)Web環(huán)境的可持續(xù)適應性, 因此, 將強化學習應用于基于過程的服務組合, 可使組合流程無論在何時運行, 均既可以利用以往獲得的Web服務性能數(shù)據(jù), 又能探索動態(tài)的Web環(huán)境, 在利用的基礎上進行探索并調整組合策略, 持續(xù)適應不斷變化的Web環(huán)境. 雖然文獻[5-7]將學習機制用于動態(tài)Web環(huán)境下的Web服務組合, 但文獻[5]僅考慮了組合服務每次執(zhí)行時對環(huán)境的探索, 未考慮對以往形成的Web服務性能數(shù)據(jù)的再利用, 對Web服務及其性能的探索缺乏可連續(xù)性； 而文獻[6-7]僅考慮了對以往數(shù)據(jù)的利用, 未考慮對環(huán)境的探索. 為解決對Web環(huán)境缺乏可持續(xù)適應性的問題, 本文根據(jù)解決該類服務組合的特點, 提出一種基于Markov決策模型的任務分配模型, 并為實現(xiàn)對動態(tài)變化的Web環(huán)境的可持續(xù)探索和利用, 提出了持續(xù)自適應服務組合方法.

1 任務分配模型

任務分配策略是將基于過程的任務分配視為隨機順序決策問題, 將任務分配過程分為若干個連續(xù)階段, 利用強化學習技術在每個階段嘗試選擇滿足任務需求的Web服務, 并從選擇的結果中進行學習, 在執(zhí)行過程中逐步逼近從初始階段到終止階段累計代價最小的任務分配.

1.1 過程模型

服務請求的過程模型可形式化表示為SR=(T,R,δ), 其中:T={t1≤t≤m}表示一組構成服務請求的任務集合；R?T×T表示任務之間執(zhí)行的次序; (t→t+1)∈R表示只有當t執(zhí)行成功,t+1才開始執(zhí)行；δ：T→D表示每個任務到抽象任務描述的映射,D表示抽象任務功能描述的集合, 即D={d1≤d≤m}.

抽象任務描述與任務一一對應, Web服務發(fā)現(xiàn)算法利用過程模型給出的抽象任務描述查找相應的服務.

1.2 候選服務集合

如果將發(fā)現(xiàn)服務的過程表述為函數(shù)φ：D→CS, 則任務t所對應的服務集合為CSt=φ(δ(t)), 該服務集合稱為候選服務集合. 服務集合由功能相同、 QoS屬性不同的一組服務組成.

如果將基于過程的任務分配分為若干階段, 則這種組合問題具有如下特點： 每個任務分配對應一個階段, 每個任務對應一個侯選服務集合, 即CS, 因此, 一個階段即存在多種可能的任務分配, 需要在每個階段確定出執(zhí)行任務的Web服務； 在當前階段確定了某個服務后, 則進入到下一階段的某個狀態(tài)(狀態(tài)即一個階段開始時算法所處的環(huán)境)并且Web服務的選擇只取決于當前狀態(tài), 與過去各階段的狀態(tài)無關； 如果在每個階段都根據(jù)某種標準確定出優(yōu)化的Web服務, 則由各個階段選擇出的Web服務所構成的組合服務也是優(yōu)化的. 因此, 這種服務組合問題實際上是隨機順序決策問題, Markov決策模型適合為該問題建模.

1.3 任務分配模型

基于Markov決策模型, 將任務分配問題表示為TAM=(k,s,ξ,ρ).

1)k表示任務分配階段, 1≤k≤m. 若過程模型包含m個待分配的串型任務, 則基于過程的Web服務組合過程可被劃分為m個連續(xù)階段.

2)s表示在每個階段開始時算法所處的狀態(tài). 初始階段k=1, 只包括一個狀態(tài)(即初始狀態(tài), 記為s0)； 其余各階段k≠1, 所包含的狀態(tài)數(shù)取決于前一階段可供分配的Web服務數(shù)量； 特別當k=m時, 沒有可用于分配的Web服務, 為了算法處理的需要, 需設定一個無代價的任務分配終止狀態(tài), 記為sd.

如果階段k存在n個可供選擇的Web服務, 表明階段k的某個狀態(tài)有n種可能的任務分配, 這種可能的任務分配完成后, 算法可能到達的狀態(tài)稱為可達狀態(tài). 如果階段k的可達狀態(tài)為n, 則階段k+1存在n個狀態(tài).

盡管每個階段可能有多種狀態(tài), 但在算法執(zhí)行過程中只能處于某個階段的某一種狀態(tài), 即在算法執(zhí)行過程中, 狀態(tài)和階段是相對應的, 因此, 如果將某階段k的某個狀態(tài)記為s(k), 則s(k)也可以記為s； 同理,CS(k)也可記為CS(s).

3)ξ:πs(w)→w是Web服務選擇函數(shù), 表示在狀態(tài)s(k)根據(jù)概率分布πs(w)為該狀態(tài)所對應的任務選擇Web服務.πs(w)是在狀態(tài)s上關于Web服務的概率分布(簡稱為狀態(tài)s的概率分布). 如果狀態(tài)s的候選服務集為CS(s)={w1,w2,w3}, 則其概率分布πs(w)是πs(w1),πs(w2),πs(w3). 概率分布實質是關于代價rk(w)的多項式函數(shù),rk(w)是關于Web服務某種性能的實際觀察值函數(shù).

4)ρ: (s(k),ξ)→s(k+1)是狀態(tài)轉移函數(shù), 表示在當前狀態(tài)s(k), 由函數(shù)ξ(πs(w))做出了某種任務分配, 下一個階段的某個狀態(tài)s(k+1)也就完全確定了, 即表示在狀態(tài)s(k)完成任務分配后轉換到下一個狀態(tài)s(k+1).

因此, 任務分配模型具有如下特點： 一旦在某個狀態(tài)選定了一個服務, 則下一個階段的某個狀態(tài)也就確定了, 即s′=ρ(s,w); 并且不同的服務選擇可導致不同的狀態(tài), 即ρ(s,w1)≠ρ(s,w2).

1.4 策略Π

策略Π由各階段(或狀態(tài))上的服務選擇函數(shù)ξ組成, 即Π={ξkk=1,2,…,m}. 由于ξ由各階段上的概率分布決定, 因此, 策略Π也可定義為是由各階段上的概率分布組成的, 即Π={πs(w)s=1,2,…,m}.m個階段的任務分配過程包括m個狀態(tài)轉換, 與任務分配模型相對應的任務分配狀態(tài)轉移如圖1所示, 表示了各階段的狀態(tài)及狀態(tài)轉移.

圖1 任務分配狀態(tài)轉移Fig.1 Task allocation transition

假設服務請求模型包括4個任務, 存在13個可供分配的Web服務, 其中,CS(1),CS(2),CS(3),CS(4)分別為4,4,3,2, 階段1～階段5的狀態(tài)數(shù)分別為1,4,4,3,2. 圖1中節(jié)點表示任務分配狀態(tài), 邊表示狀態(tài)轉移； 實線邊表示實際轉移, 虛線邊表示可能的狀態(tài)轉移； 實心節(jié)點表示實際到達的狀態(tài), 空心節(jié)點表示可能達到的狀態(tài).

算法從初始狀態(tài)出發(fā)直到終止狀態(tài)通過學習機制逐步逼近一條累計代價的優(yōu)化路徑. 在初始狀態(tài), 有4個可供分配的Web服務, 算法根據(jù)函數(shù)ξ為任務1選擇某個Web服務后, 到達下一個狀態(tài)2(圖1中實心節(jié)點所示)； 通過服務的執(zhí)行獲得其實際執(zhí)行代價, 計算該狀態(tài)的概率分布πs(w), 對于其他狀態(tài)算法重復上述過程, 直至終止狀態(tài). 通過學習算法不斷地執(zhí)行, 不斷更新服務組合策略, 逐步逼近從初始狀態(tài)到終止狀態(tài)的優(yōu)化任務分配策略.

2 主要方法

2.1 選擇Web服務的依據(jù)

當將QoS作為選擇服務的依據(jù)時, 要注意服務提供者所給出的性能發(fā)布值是否能準確反映Web服務的實際性能, 否則會將不是真實性能的Web服務加入到組合中而影響組合服務的性能, 因此在選擇Web服務時要根據(jù)Web服務執(zhí)行的實際性能, 而不是根據(jù)服務提供者所發(fā)布的性能. 文獻[8-10]使用“信任”從一組執(zhí)行同樣任務的服務中選擇優(yōu)化的Web服務, 利用Web服務使用者給出的評價計算信譽. 這種計算信譽度的弊端是采用了使用者的主觀評價, 而不同使用者的評價標準不同, 因此, 人為的評價不一定能反映Web服務的真實性能. 本文選擇某種QoS性能參數(shù)的信譽度作為選擇Web服務的依據(jù), 通過比較所觀察到的Web服務實際性能和Web服務提供者所發(fā)布的性能計算信譽度.

對于服務, 其參數(shù)k的信譽度函數(shù)為

(1)

2.2 選擇Web服務的技術

根據(jù)任務分配模型可知, 該結構恰好對應確定性最短路徑, 可考慮采用動態(tài)規(guī)劃或強化學習解決這種優(yōu)化問題. 由于將Web服務的實際性能參數(shù)作為選擇Web服務的依據(jù), 因此, 在Web服務執(zhí)行前, 算法并不能獲得Web服務的實際性能, 這樣每個狀態(tài)的概率分布事先并不可知. 如果在概率分布未知的情況下, 優(yōu)化問題則轉化為強化學習問題, 通過值迭代或策略迭代的方式逼近MDP中的最優(yōu)策略. 根據(jù)Bellman最優(yōu)定理, 對于狀態(tài)空間有限的單鏈MPD問題, 必然存在一個最優(yōu)策略[11]； 同理, 對于服務選擇問題也必然存在一個最優(yōu)的任務分配策略Π={πs(w)s=1,2,…,m}.

因此, 采用如下在線概率分布模型[12]:

(2)

(3)

綜上可知, 概率分布取決于服務執(zhí)行的實際代價, 同時也受θs(即熵)的制約, 可通過事先指定各狀態(tài)的熵值, 確定各狀態(tài)的探索級別.

2.3 控制隨機選擇

探索是嘗試解決新問題的方法, 而利用是重用曾經(jīng)成熟的解決方案. 因此, 既要使算法保持一定程度上的探索, 還要使其利用以往獲得的Web服務性能數(shù)據(jù). 探索和利用間的平衡問題是學習算法要解決的問題之一, 強化學習是以集成方式確切地處理探索和利用之間的平衡問題及概率分布的在線估計問題[12], 為了量化探索, 利用候選服務集概率分布的熵定義各狀態(tài)的探索度.

3 算法與分析

3.1 學習算法

該算法的主要步驟是從初始狀態(tài)s0出發(fā), 在每個狀態(tài)s根據(jù)概率分布πs(w)選擇一個服務w并執(zhí)行該服務, 根據(jù)服務執(zhí)行產(chǎn)生的實際代價, 更新c(s,w),πs(w)和U(s), 然后轉移到新的狀態(tài)s′. 重復這個過程直至終止狀態(tài). 由于sd是終止狀態(tài), 因此sd的代價為0. 其中,c(s,w),πs(w),U(s)需要預先給定初始值, 一般情況下, 令πs(w),U(s)的初始值為1/ns和0, 當πs(w)=1/ns時,c(s,w)的初始值已經(jīng)不再重要. 算法步驟如下:

WSCompositionPolicy(entropyπ)

1) begin

2)t← identifyTask(SR)

3)CSt=φ(δ(t))

4) if (s≠sd)

5)w←ξ(πs(w))

6) execution(w)

7)c(s,w)=rk(w)

8)θs← computeTeta(πs(w))

10) goto 2)

11) endif

12) end

該算法在不同狀態(tài)與不同的環(huán)境交互, 通過步驟3)感知Web環(huán)境中服務的變化. 在步驟5)和步驟6)嘗試選擇執(zhí)行任務的Web服務, 如何嘗試取決于該狀態(tài)的概率分布. 步驟7)表明算法根據(jù)Web服務的執(zhí)行而觀察到該服務實際執(zhí)行性能(在動態(tài)環(huán)境下隨時間的改變而改變), 并由此計算出rk(w). 步驟9)更新該狀態(tài)的概率分布, 之后學習算法進入下一個任務分配狀態(tài)s+1, 直至終止狀態(tài)sd. 注意算法第一次執(zhí)行時, 根據(jù)初始概率分布選擇執(zhí)行任務的Web服務.

該算法每次執(zhí)行都是自學習、 自適應過程, 通過算法的不斷執(zhí)行, 算法不斷地獲得所選中Web服務的執(zhí)行代價, 根據(jù)該代價不斷更新各狀態(tài)的概率分布, 逐漸逼近一個優(yōu)化的任務分配策略, 即Π={πs(w)s=1,2,…,m}.

3.2 算法分析

當θs=0時, 概率分布退化為πs(w)=1/ns, 熵值Es=logns, 所有狀態(tài)的探索度達到最大值, 此時算法總是處于隨機探索狀態(tài), 不計代價隨機地選取一個Web服務進行任務分配, 不再利用以往學習到的策略. 因此, 當0

通過上述分析可知, 合理地給定熵值Es, 該算法即可逐步逼近一個優(yōu)化的服務選擇策略. 每當Web環(huán)境發(fā)生變化時, 該算法都能動態(tài)地調整服務組合策略； 如果Web環(huán)境未發(fā)生變化, 則可利用由Web服務以往性能參數(shù)所學習到的組合策略.

4 實驗結果與分析

為了驗證算法對環(huán)境變化的適應性, 本文通過給定不同的探索率, 考察算法在靜態(tài)和動態(tài)兩種環(huán)境下對環(huán)境的探索程度. 每次模擬實驗開始, 令U(s)和πs(w)的初始值為0和1/ns, 且每個狀態(tài)的探索率都相同；根據(jù)方程(3)和(4)在每一步更新平均代價和轉換概率.

4.1 靜態(tài)環(huán)境

當探索率分別為0,30%,60%和90%時, 通過算法探索的路徑, 考察算法對探索率的變化規(guī)律. 路徑[1,2,6,10,13]上邊的代價初始值為1, [1,5,9,12,14]上邊的代價為2, 而其他邊的代價初始值為3, 由于15是終止狀態(tài), 因此[13,15], [14,15]的代價始終為0. 圖2給出了算法運行10 000次(一次運行表示一次完整的任務分配)探索的路徑. 圖2中粗線邊表示高訪問率, 細線邊表示較高訪問率, 長虛線表示中訪問率, 短虛線表示低訪問率.

圖2 算法在4種不同探索率下的探索路徑Fig.2 Paths from source to destination for four exploration rates

當探索率為0時, 一旦找到從節(jié)點1到節(jié)點15的最短路徑, 即[1,2,6,10,13,15](圖2粗線邊所示路徑), 則算法不再進行探索, [1,2,6,10,13,15]是唯一的遍歷路徑； 當探索率為30%時, 盡管探索到了其他邊, 但最短路徑仍然是[1,2,6,10,13,15], 表明對原有組合的利用大于探索； 當探索率為60%時, 算法探索了更多的邊, 但仍然采用[1,2,6,10,13,15]作為最短路徑, 雖然增加了探索, 但探索仍然低于利用； 當探索率為90%時, 不再利用原來的最短路徑, 探索明顯大于利用. 因此, 隨著探索率的提高, 算法的探索程度逐漸加大.

4.2 動態(tài)環(huán)境

當探索率分別為0,30%,60%和90%時, 通過執(zhí)行代價變化趨勢, 考察算法在不同探索率下對環(huán)境變化的適應性. 圖3給出了隨著算法運行次數(shù)的增加, 算法執(zhí)行代價的變化規(guī)律.

圖3 4種探索率的算法執(zhí)行代價Fig.3 Cost trends for four exploration rates

初始時, 路徑[1,2,6,10,13]上邊的代價為3, [1,5,9,12,14,]上邊的代價為4, 其他邊的代價為6, 邊[13,15],[14,15]的代價仍然為0. 此時最短路徑為[1,2,6,10,13,15], 該路徑的總代價是12. 對不同探索率算法分別執(zhí)行13 000次, 當算法執(zhí)行到7 501次時, 將所有內部邊的代價置為1, 此時觀察算法對不同探索率的變化規(guī)律. 由圖3可見, 雖然內部邊的代價發(fā)生了變化, 在整個模擬實驗過程中算法執(zhí)行代價始終為12, 原因是在探索率為0時, 盡管某些邊代價發(fā)生了改變, 產(chǎn)生了新的最短路徑, 但算法不再進行探索； 當探索率不為0時, 算法可以在環(huán)境發(fā)生變化的情況下找到新的優(yōu)化路徑(所有經(jīng)過內部節(jié)點3,4,7,8,11經(jīng)過13到達15的路徑是最短路徑), 代價由12變?yōu)?且探索率越高, 找到新優(yōu)化路徑的速度越快, 其原因是當探索率不為0時, 算法可對環(huán)境進行探索發(fā)現(xiàn)性能更好的Web服務, 對原來形成的組合策略進行調整.

[1] Stephan Leutenmayr. Selected Languages for Web Services Composition: Survey, Challenges, Outlook [D]: [Ph D Thesis]. Munich: University of Munich, 2007.

[2] CHEN Yan-ping, LI Zeng-zhi, TANG Ya-zhe, et al. A Method Satisfying Markov Process of Web Service Composition under Incomplete Constrains [J]. Chinese Journal of Computers, 2006, 29(7): 1076-1083. (陳彥萍, 李增智, 唐亞哲, 等. 一種滿足馬爾可夫性質的不完全信息下的Web服務組合方法 [J]. 計算機學報, 2006, 29(7): 1076-1083.)

[3] LIU Shu-lei, LIU Yun-xiang, ZHANG Fan, et al. A Dynamic Web Services Selection Algorithm with QoS Global Optimal in Web Services Composition [J]. Journal of Software, 2007, 18(3): 646-656. (劉書雷, 劉云翔, 張帆, 等. 一種服務聚合中QoS全局最優(yōu)服務動態(tài)選擇算法 [J]. 軟件學報, 2007, 18(3): 646-656.)

[4] ZENG Liang-zhao, Benatallah B, Dumas M, et al. Quality Driven Web Service Composition [C]//Proceedings of the 12th International Conference on World Wide Web. New York: ACM, 2003: 411-421.

[5] FAN Xiao-qin, JIANG Chang-jun, WANG Jun-li, et al. Random-QoS-Aware Reliable Web Service Composition [J]. Journal of Software, 2009, 20(3): 546-556. (范小芹, 蔣昌俊, 王俊麗, 等. 隨機QoS感知的可靠Web服務組合 [J]. 軟件學報, 2009, 20(3): 546-556.)

[6] Abdallah S, Lesser V. Modeling Task Allocation Using a Decision Theoretic Model [C]//Proceedings of the Fourth International Joint Conference on Autonomous Agents and Multiagent System. New York: ACM, 2005: 719-726.

[7] Hannah H, Mouaddib A I. Task Selection Problem under Uncertainty as Decision-Making [C]//Proceedings of the First International Joint Conference on Autonomous Agents and Multiagent System. New York: ACM, 2002: 1303-1308.

[8] Maximilien E M, Singh M P. Multiagent System for Dynamic Web Services Selection [C]//Proceedings of 1st Workshop on Service-Oriented Computing and Agent-Based Engineering. Netherlands: [s.n.], 2005: 25-29.

[9] ZHAI Hong-yi. Management Tool Design for IP QoS Policy [J]. Journal of Jilin University: Information Science Edition, 2011, 29(3): 225-230. (翟紅藝. IP網(wǎng)絡QoS策略管理工具設計 [J]. 吉林大學學報: 信息科學版, 2011, 29(3): 225-230.)

[10] ZHU Mei-ling, ZHAO Xiao-hui, GU Hai-jun, et al. Adaptive Resource Allocation Algorithm for Multiuser OFDM System Based on QoS [J]. Journal of Jilin University: Engineering and Technology Edition, 2009, 39(5): 1347-1352. (朱美玲, 趙曉暉, 顧海軍, 等. 基于QoS的多用戶OFDM系統(tǒng)自適應資源分配算法 [J]. 吉林大學學報: 工學版, 2009, 39(5): 1347-1352.)

[11] GAO Yang, ZHOU Ru-yi, WANG Hao, et al. Study on an Average Reward Reinforcement Learning Algorithm [J]. Chinese Journal of Computers, 2007, 30(8): 1372-1378. (高陽, 周如益, 王皓, 等. 平均獎賞強化學習算法研究 [J]. 計算機學報, 2007, 30(8): 1372-1378.)

[12] Achbany Y, Fouss F, Yen L, et al. Optimal Tuning of Continual Online Exploration in Reinforcement Learning [C]//Proceedings of the International Conferrence on Artificial Neural Networks. Berlin: Springer, 2007: 790-800.