基于層次狀態(tài)機(jī)的服務(wù)組合

張 颯，朱雪峰

(中國石油大學(xué)(北京) 石油數(shù)據(jù)挖掘北京市重點(diǎn)實(shí)驗(yàn)室，北京 102249)

0 引 言

Web服務(wù)組合方案設(shè)計(jì)分為組合方案設(shè)計(jì)和組合方案優(yōu)化兩個階段。如何將不同的服務(wù)有效地組合在一起，實(shí)現(xiàn)功能需求，繼而在優(yōu)化階段，針對非功能性屬性對候選服務(wù)進(jìn)行篩選，是web服務(wù)組合研究的重點(diǎn)。

文獻(xiàn)[1]采用擴(kuò)展工作流模型，將抽象服務(wù)替換為實(shí)際的wsc(web service composition)方案?；诠ぷ髁髂Ｐ脱芯康闹攸c(diǎn)之一在于如何克服動態(tài)環(huán)境的影響。文獻(xiàn)[2]利用petri網(wǎng)建模，建立了服務(wù)組合描述與狀態(tài)圖的一一映射關(guān)系。但是petri不易理解，不能在網(wǎng)中體現(xiàn)數(shù)據(jù)流。文獻(xiàn)[3]的研究基于π演算是進(jìn)程代數(shù)在wsc研究中應(yīng)用的代表。根據(jù)文獻(xiàn)[4]，局部優(yōu)化方法從所有候選服務(wù)中，可以找到局部較優(yōu)的服務(wù)方案，但是會忽略非功能屬性的需求；全局優(yōu)化方法可以找到最優(yōu)方案，但這個方法的時間花銷隨規(guī)模增大；運(yùn)用啟發(fā)式算法的優(yōu)化方法，可以以較小的開銷找到較優(yōu)的結(jié)果，但沒有考慮到服務(wù)之間的邏輯關(guān)系。

通過對比web組合方案的研究現(xiàn)狀可以發(fā)現(xiàn)，對web服務(wù)組合設(shè)計(jì)建模，進(jìn)行服務(wù)組合優(yōu)化的研究存在以下問題：①已有的服務(wù)自動組合的研究工作主要集中在通過形式化描述、圖例方法得到服務(wù)的組合和執(zhí)行順序，在這種情形下，由于空間有限和狀態(tài)過多就有可能造成狀態(tài)爆炸；②關(guān)于組合優(yōu)化的研究，上述方法并沒有考慮到用戶對于服務(wù)提出的約束條件，忽略了服務(wù)之間的邏輯關(guān)系。

1 Web服務(wù)組合及相關(guān)技術(shù)

單一的web服務(wù)可以實(shí)現(xiàn)一定的功能，但是單一的服務(wù)所能起到的作用相對而言還是有限的。通過服務(wù)組合，可以構(gòu)建出應(yīng)用場景更加多樣，功能更加強(qiáng)大的服務(wù)系統(tǒng)。web服務(wù)組合方案設(shè)計(jì)分為組合方案設(shè)計(jì)和組合方案優(yōu)化兩個階段。組合方案設(shè)計(jì)階段主要為業(yè)務(wù)流程建模，優(yōu)化階段主要是基于QoS或者是用戶的其它非功能性需求進(jìn)行研究分析。

組合優(yōu)化階段，設(shè)計(jì)者主要針對用戶的非功能性需求進(jìn)行優(yōu)化，在衡量用戶的滿意程度上，除了主觀因素，QoS作為一種非功能性的標(biāo)準(zhǔn)，可以客觀的、量化的衡量滿意程度。QoS的屬性指標(biāo)有各種各樣的，其中的內(nèi)容也是多種多樣的。常用的QoS屬性可以分為兩類，一類是優(yōu)勢屬性，另外一類是劣勢屬性。其中服務(wù)花費(fèi)、響應(yīng)時間等屬于劣勢屬性，它們的值越小越好；而服務(wù)安全、可靠性等屬于優(yōu)勢屬性，它們的值越大越好。

用QoS對web服務(wù)組合模型進(jìn)行評定時，可以選取的備選方案往往有多個。但是各個QoS屬性的取值單位和范圍是不統(tǒng)一的，舉例來說，服務(wù)花費(fèi)的取值范圍是服務(wù)提供者提出的，取值單位是數(shù)值類型的；而可靠性的取值單位是比率類型的，取值范圍在[0,1]之間。因此如果想要進(jìn)行web服務(wù)組合中QoS屬性的比較，首先要對各個QoS屬性進(jìn)行歸一化處理，避免取值單位和取值范圍造成的影響。優(yōu)勢屬性采用式(1)來計(jì)算

(1)

劣勢屬性采用式(2)計(jì)算

(2)

式(1)和式(2)中的m表示web服務(wù)未經(jīng)處理的QoS屬性值，而m′代表著經(jīng)過歸一化處理的QoS屬性值。經(jīng)過歸一化處理后，原來的QoS屬性值的值域會一一映射到范圍[0,1]中去。

在web服務(wù)組合之中存在4種服務(wù)運(yùn)行邏輯。在計(jì)算web服務(wù)組合的QoS屬性值時，要用不同的方法對4種運(yùn)行邏輯的web服務(wù)組合進(jìn)行不同的聚合。順序、循環(huán)、選擇和并行，這4種運(yùn)行邏輯的計(jì)算公式見表1。

表1 服務(wù)組合QoS計(jì)算模型

2 狀態(tài)機(jī)與服務(wù)組合建模

2.1 服務(wù)狀態(tài)機(jī)

用簡單的服務(wù)狀態(tài)機(jī)互相組合最終形成的狀態(tài)圖可能存在狀態(tài)爆炸的情況，因此引入層次狀態(tài)機(jī)對服務(wù)進(jìn)行組合。假設(shè)用戶的需求為輸入 {1,2,3}， 輸出為 {7,8,9,10}。 那么層次狀態(tài)機(jī)中的超狀態(tài)如圖1所示。其中矩形為層次狀態(tài)機(jī)中的超狀態(tài)， {A,B,C}、 {D,E} 是分別屬于兩個超狀態(tài)的服務(wù)。

2.2 基于狀態(tài)機(jī)的服務(wù)社區(qū)

存在很多接口參數(shù)相似、功能相似的服務(wù)，將他們組成一個服務(wù)社區(qū)。基于狀態(tài)機(jī)的服務(wù)社區(qū)為一個四元組 (ID,S,I,O) 其中：ID為服務(wù)社區(qū)的唯一標(biāo)示，S為服務(wù)的集合，I=(Ipub,Ipri) 為輸入?yún)?shù)的結(jié)合，Ipub為公共參數(shù)即所有服務(wù)輸入?yún)?shù)的交集、Ipri為非公共參數(shù)即所有服務(wù)除公共參數(shù)的輸入?yún)?shù)。O=(Opub,Opri) 為輸出參數(shù)的結(jié)合，Opub為公共參數(shù)即所有服務(wù)輸出參數(shù)的交集、Opri為非公共參數(shù)即所有服務(wù)除公共參數(shù)的輸出參數(shù)。

3 基于層次狀態(tài)機(jī)的服務(wù)組合過程

通過用戶的輸入?yún)?shù)發(fā)現(xiàn)服務(wù)，得到的服務(wù)暫時作為層次狀態(tài)機(jī)的H0層。將H0層的輸出作為下一層的輸入?yún)?shù)，找到下一層的服務(wù)，有則選擇該服務(wù)，無則不能選擇。直到所有層的輸出參數(shù)的并集與用戶需求的輸出參數(shù)相吻合。

基于層次狀態(tài)機(jī)的服務(wù)組合定義如下

3.1 基于層次狀態(tài)機(jī)的服務(wù)發(fā)現(xiàn)

由于公共參數(shù)是一個服務(wù)社區(qū)所有服務(wù)都需要的輸入?yún)?shù)，所以先匹配每個服務(wù)社區(qū)的服務(wù)參數(shù)，再匹配非公共參數(shù)可以提高效率。

劃分超狀態(tài)的服務(wù)步驟如下：

步驟1 查找服務(wù)社區(qū)，如果輸入滿足服務(wù)社區(qū)的公共參數(shù)，下一步。

步驟2 進(jìn)入這些服務(wù)社區(qū)，找到輸入滿足的服務(wù)集，獲得它們的輸出參數(shù)，如果滿足用戶需求，返回組合方案；不滿足，將該層的輸出與輸入并集作為下一次的輸入集。

步驟3 獲取已經(jīng)匹配的服務(wù)社區(qū)的后續(xù)服務(wù)社區(qū)，循環(huán)步驟1～步驟2，直到滿足用戶需求，或者達(dá)到停止條件。

3.2 服務(wù)狀態(tài)機(jī)的組合

(1)QP(A,B)=QA∪QB∪s0P(A,B)；

(2)EP(A,B)=EA∪EB∪ε；

(4)s0P(A,B)=s0P(A,B)；

(5)FP(A,B)=FA∪FB；

3.3 服務(wù)組合的驗(yàn)證

所有服務(wù)是否能正確且高效地組合成目標(biāo)服務(wù)，需要對服務(wù)組合的存在性及等價性進(jìn)行驗(yàn)證。其中，存在性驗(yàn)證實(shí)質(zhì)上就是對服務(wù)的可達(dá)性進(jìn)行驗(yàn)證。

3.3.1 服務(wù)存在性驗(yàn)證

由定義2可知，從最終狀態(tài)開始尋找前繼節(jié)點(diǎn)，再繼續(xù)尋找前繼節(jié)點(diǎn)的前繼節(jié)點(diǎn)，直到找到起始節(jié)點(diǎn)q0， 每個在路徑上的節(jié)點(diǎn)都是可達(dá)的。第4節(jié)中通過反向搜索保證了狀態(tài)圖的可達(dá)性。

3.3.2 服務(wù)等價性驗(yàn)證

(1)q0=s0；

(3)qn∈F；

則服務(wù)狀態(tài)機(jī)接受t。如果L={t|m接受t}， 則稱服務(wù)狀態(tài)機(jī)m識別語言L，記為：L(F)。

由以上的定義，可以得到如下性質(zhì)：

性質(zhì)1 對于狀態(tài)節(jié)點(diǎn)，當(dāng)且僅當(dāng)q0*t→qi+1～q2*t→qi+1時，q1～q2。

性質(zhì)2 終止?fàn)顟B(tài)一定不等價于非終止?fàn)顟B(tài)。

根據(jù)以上內(nèi)容，結(jié)合第4節(jié)的構(gòu)建過程，如果層次狀態(tài)機(jī)的所有終止?fàn)顟B(tài)都可以在服務(wù)社區(qū)中找到對應(yīng)的終止?fàn)顟B(tài)，那么驗(yàn)證目標(biāo)服務(wù)與原服務(wù)是等價的。

4 服務(wù)優(yōu)化過程

4.1 基于最優(yōu)QoS優(yōu)化過程

以時間花費(fèi)屬性為例，采用正向執(zhí)行順序，起始狀態(tài)看作一個只有輸出的虛擬服務(wù)，其QoS為0。對每一層的輸入?yún)?shù)I循環(huán)。在候選服務(wù)中選出QoS最小的服務(wù)s。根據(jù)2.1節(jié)的內(nèi)容，由于服務(wù)都是并行的，s的前序服務(wù)的QoS為上一層所有輸入?yún)?shù)最小值中選出的最大值。將最大值與s的QoS相加，即得到選擇s服務(wù)的服務(wù)組合QoS最小值。直到最后的終止?fàn)顟B(tài)。終止?fàn)顟B(tài)可以看作是一個只有輸入的虛擬服務(wù)。虛擬服務(wù)的QoS即為服務(wù)組合的最終值。基于最優(yōu)QoS優(yōu)化過程如算法1所示。

算法1

輸入：候選服務(wù)s

輸出：候選服務(wù)的組合最優(yōu)QoS表

(1)創(chuàng)建變量qosmax=0， 變量qosmin=極大值， map結(jié)構(gòu)的QoS最優(yōu)表map。

(2)循環(huán)s.I:

(3)創(chuàng)建隊(duì)列sersrc；

(4)sersrc.push(能輸出該參數(shù)的服務(wù))；

(5)循環(huán)sersrc{

(6)查QoS最優(yōu)表中該元素的值， 若值為null或者值比qosmin小， 將值賦給qosmin；

}

(7)if (qosmax

(8)取s.qos中時間花費(fèi)的屬性值與qosmax相加， 得到的值存入QoS最優(yōu)表s鍵值對應(yīng)的位置。

層次狀態(tài)機(jī)的終止?fàn)顟B(tài)可以看作是一個只有輸入的虛擬服務(wù)，它的最優(yōu)QoS值即為服務(wù)組合的最終QoS值。算法1不僅得到了服務(wù)組合的最終QoS值，選擇每個服務(wù)時的最優(yōu)QoS值也在組合過程中記錄下來。

4.2 基于約束條件的去冗余服務(wù)過程

采用第3節(jié)中的超狀態(tài)構(gòu)建過程，會導(dǎo)致組合服務(wù)中存在冗余服務(wù)。3種情況下會存在冗余服務(wù)：①k層的服務(wù)s，其輸出并沒有被后續(xù)服務(wù)利用；②k層存在被重復(fù)計(jì)入的服務(wù)；③k層的多個服務(wù)互相組合，輸出的參數(shù)對于后續(xù)服務(wù)的作用是相同的。

針對情況①，最終采取反向搜索排除無用服務(wù)。針對情況②、情況③采用算法2去除冗余服務(wù)。

為了減小運(yùn)算規(guī)模，應(yīng)對組合按照約束條件去除冗余服務(wù)。結(jié)合算法2，得到符合約束條件的服務(wù)組合最簡集。由于最終采取反向搜索，輸入應(yīng)包含上一層的服務(wù)，算法開始時輸入的即為終止?fàn)顟B(tài)的虛擬服務(wù)。

算法2

輸入：輸出一層參數(shù)的服務(wù)集集合sersrclist，上一層的服務(wù)組合方案slast

輸出：基于約束條件的去冗余服務(wù)方案集合

(1)循環(huán)sersrclist：

(2)將服務(wù)集集合的元素兩兩對比{

(3)檢查是否存在元素A是元素B的子集；

(4)若存在， 刪除規(guī)模大的集合；

}

(5)取sersrclist的隊(duì)頭元素s， 把s中的每個服務(wù)作為集合存入res；

(6)forj=1循環(huán)sersrclist：

(7)比較res中的每個元素和sersrclist[j], 存在交集的每一項(xiàng)移入resR并在res中刪除, 并把交集元素存入serU；

(8)對serU的每個元素{

(9)if(map無這個元素)存入map，key值為serU[i]，value為res中每一項(xiàng)與serU[i]組合的服務(wù)。

(10)elsevalue追加res中每一項(xiàng)與serU[i]組合的服務(wù)}

(11)res中剩余沒有交集的元素sres：

(12)判斷sersrclist[j]中的每個服務(wù)s：

(13)從map中取key為s的值， 檢查其中的元素， 如果不存在sres的子集， 將sres與組合作為一個元素進(jìn)入到resR中；

(14)將resR的值賦給res；

(15)循環(huán)res{

(16)取上一層服務(wù)的約束服務(wù)的集合slast.s.?；

(17)對比元素留下符合約束要求的組合方案。}

4.3 服務(wù)方案選擇

將上述過程結(jié)合可得到基于層次狀態(tài)機(jī)的服務(wù)組合優(yōu)化算法。算法1得到了各個服務(wù)在組合中的最優(yōu)QoS值，取服務(wù)狀態(tài)機(jī)本身QoS的時間維度的值，用服務(wù)的最優(yōu)QoS減去服務(wù)本身的值，得到前序服務(wù)組合的最優(yōu)QoS值，來對所有前序候選服務(wù)進(jìn)行篩選。

采用反向搜索，排除輸出參數(shù)無用的服務(wù)，也使層次狀態(tài)機(jī)是可達(dá)的。首選對終止?fàn)顟B(tài)進(jìn)行處理。把終止?fàn)顟B(tài)看作是一個只有輸入?yún)?shù)的虛擬服務(wù)，輸入?yún)?shù)為用戶的目標(biāo)輸出參數(shù)。將輸出這些參數(shù)的服務(wù)存入變量sersrc，利用算法1得到的最優(yōu)QoS篩選服務(wù)。得到的參數(shù)服務(wù)候選集經(jīng)過算法2，得到去冗余符合約束的服務(wù)組合方案存入listLeaf。循環(huán)服務(wù)組合方案集合：創(chuàng)建listTree隊(duì)列；list-Tree.push(服務(wù)方案)；創(chuàng)建樹集合listTrees；listTrees.push(listTree)。以上流程如算法3所示。

算法3

輸入：listLeaf,listTrees,result

輸出：result

(1)檢查listLeaf是不是只包含一個方案且方案中只有一個起始狀態(tài)的虛擬服務(wù)；

(2)是的話將listTrees[0]加入result終止遞歸， 返回結(jié)果， 不是的話繼續(xù)；

(3)循環(huán)listLeaf中的元素；

(4)分別找到元素的輸入?yún)?shù)對應(yīng)的前服務(wù)， 存入；

(5)利用算法1得到的QoS篩選符合最優(yōu)QoS的服務(wù)；

(6)利用算法2對篩選后的各個參數(shù)的服務(wù)集去冗余組合， 得到元素的前序服務(wù)組合方案集合存入listTreenew；

(7)循環(huán)listTreenew： {

(8)創(chuàng)建listTree數(shù)組；

(9)listTree.push(listTreenew元素)；

(10)listTree.push(listTrees[0])；

(11)listTrees.push(listTree)；

(12)listLeaf.push(listTreenew元素)；

}

(13)listLeaf隊(duì)頭元素出隊(duì)；

(14)listTrees隊(duì)頭元素出隊(duì)；

(15)繼續(xù)用新的listLeaf,listTrees,result調(diào)用本程序；

算法3是由終止?fàn)顟B(tài)出發(fā)，以其為根結(jié)點(diǎn)，找到它的前序服務(wù)組合方案，然后再以前序服務(wù)為結(jié)點(diǎn)，不斷添加葉子結(jié)點(diǎn)，樹的每條路徑就是一個組合方案。算法3采用廣度優(yōu)先，算法第(1)行～第(2)行是終止條件，即組合方案到達(dá)了起始狀態(tài)，滿足了用戶的輸入?yún)?shù)需求。算法第(3)行～第(6)行獲得它們符合約束的前序服務(wù)組合方案存入listTreenew。算法第(7)行～第(12)行把前序服務(wù)掛在相應(yīng)的父節(jié)點(diǎn)下，將這條路徑保留在listTrees中，將新的需要找前序服務(wù)的服務(wù)進(jìn)入隊(duì)列l(wèi)istLeaf。第(13)行～第(15)行將已有葉子節(jié)點(diǎn)的父節(jié)點(diǎn)出隊(duì)，繼續(xù)遞歸。

4.4 仿真實(shí)驗(yàn)與結(jié)果分析

實(shí)驗(yàn)主要驗(yàn)證上述算法在尋找組合方案時的有效性，將其與傳統(tǒng)的枚舉組合樹法進(jìn)行對比。采用選擇不同的服務(wù)社區(qū)數(shù)量和候選服務(wù)數(shù)量，比較兩種算法在此情況下運(yùn)行時間的變化。本實(shí)驗(yàn)采取的服務(wù)數(shù)據(jù)來自QWS數(shù)據(jù)集，但由于QWS數(shù)據(jù)集不存在約束條件以及服務(wù)參數(shù)的信息，因此采取隨機(jī)生成法為這些服務(wù)生成約束條件和服務(wù)參數(shù)。初始化服務(wù)數(shù)據(jù)的過程如下：首先設(shè)置模擬參數(shù)數(shù)據(jù)建立服務(wù)社區(qū)之間的參數(shù)依賴關(guān)系，再根據(jù)每個服務(wù)社區(qū)參數(shù)構(gòu)造一批參數(shù)類似的服務(wù)，其中候選服務(wù)來自QWS數(shù)據(jù)集，每個服務(wù)的參數(shù)參考服務(wù)社區(qū)的參數(shù)隨機(jī)生成。為了模擬在組合過程中各個服務(wù)之間的約束邏輯，同樣采用隨機(jī)生成法，為這些服務(wù)生成一些隨機(jī)的約束邏輯和用戶請求。

表2、表3分別是兩種算法在候選服務(wù)保持10、20、30的狀態(tài)下，服務(wù)社區(qū)分別為3時、4時的時間花費(fèi)情況。針對每種實(shí)驗(yàn)參數(shù)設(shè)置，隨機(jī)生成不同的約束條件實(shí)驗(yàn)50次，以50次實(shí)驗(yàn)的平均運(yùn)行時間作為結(jié)果進(jìn)行對比。

由表2、表3可以看出，層次篩選法明顯優(yōu)于傳統(tǒng)組合樹法，根據(jù)任務(wù)的增多，在表3中，20個任務(wù)時傳統(tǒng)方法已經(jīng)達(dá)到秒級單位，層次篩選法時間增長的趨勢明顯低于傳統(tǒng)方法。

表2 3個服務(wù)社區(qū)下算法的時間花費(fèi)/ms

表3 4個服務(wù)社區(qū)下算法的時間花費(fèi)

5 結(jié)束語

選擇狀態(tài)機(jī)進(jìn)行服務(wù)組合的情況下，當(dāng)轉(zhuǎn)移過多、狀態(tài)爆炸時，可以進(jìn)一步選用層次狀態(tài)機(jī)。提出描述服務(wù)狀態(tài)機(jī)和服務(wù)社區(qū)的概念，根據(jù)用戶的輸入以及目標(biāo)輸出，提出方法不斷劃分超狀態(tài)，直至最后超狀態(tài)輸出的參數(shù)并集符合用戶的要求。在這個過程中，會產(chǎn)生冗余服務(wù)，而且也沒有考慮用戶的非功能性需求。與此同時考慮到服務(wù)之間的約束邏輯，基于這三方面對服務(wù)組合方法進(jìn)行優(yōu)化，構(gòu)建過程中篩選符合要求的候選服務(wù)，最終得到符合約束條件的最優(yōu)QoS組合方案。經(jīng)過仿真實(shí)驗(yàn)的對比，驗(yàn)證該方法是行之有效的。

研究取得了一定的成果，但是工作仍然有待完善。研究主要在模擬好的服務(wù)社區(qū)數(shù)據(jù)的基礎(chǔ)上，基于層次狀態(tài)機(jī)對服務(wù)進(jìn)行組合和優(yōu)化，并沒有考慮到如何對相似的服務(wù)進(jìn)行聚合形成服務(wù)社區(qū)。未來的研究工作中，應(yīng)完善服務(wù)聚合的方法。