韓 敏, 孫國慶, 鄭丹晨, 周惠巍

(大連理工大學(xué) 電子信息與電氣工程學(xué)部,遼寧 大連 116023)

隨著高速互聯(lián)網(wǎng)技術(shù)發(fā)展及用戶對軟件需求不斷增加,Web 服務(wù)組合在網(wǎng)絡(luò)技術(shù)研究中發(fā)揮著愈來愈重要的作用.Web 服務(wù)可以視作網(wǎng)絡(luò)系統(tǒng)功能的基本單元,其遵循標(biāo)準(zhǔn)Internet 協(xié)議和SOAP 協(xié)議,并具有完全開放、松散耦合、高度可集成等特性.很多情況下,單一Web 服務(wù)難以滿足用戶的不同實際需求,服務(wù)組合技術(shù)的出現(xiàn)解決了多功能分布式Web 服務(wù)的集成問題,使其組合成結(jié)構(gòu)統(tǒng)一、功能復(fù)雜的綜合服務(wù)系統(tǒng).因此,如何實現(xiàn)服務(wù)共享和無縫集成,使單一Web 服務(wù)動態(tài)組合起來,構(gòu)成服務(wù)質(zhì)量(quality of service,簡稱QoS)達(dá)到用戶需求的服務(wù)組合策略(strategy of service composition,簡稱SSC),是建立網(wǎng)絡(luò)服務(wù)體系的研究重點.

目前,國內(nèi)外學(xué)者在Web 服務(wù)及其組合技術(shù)領(lǐng)域取得了諸多研究成果.這些成果的服務(wù)組合方法通常分為兩大類:基于工作流的服務(wù)組合,如語義描述法[1]和圖搜索方法[2];基于系統(tǒng)建模的服務(wù)組合,如數(shù)據(jù)分析法[3]和人工智能法[4?6].工作流技術(shù)可以利用服務(wù)綁定、流程設(shè)計、語義描述等對服務(wù)組合進(jìn)行過程化處理,但其包含較多的人為參與,系統(tǒng)自動化程度和可靠性不高,服務(wù)組合效率偏低;數(shù)據(jù)分析的系統(tǒng)建模方法可以確保理論計算的正確性,但容易忽略實際因素的綜合效應(yīng),進(jìn)而導(dǎo)致與預(yù)期結(jié)果產(chǎn)生偏差;人工智能方法也可以實現(xiàn)Web 服務(wù)的自動組合,例如通過神經(jīng)網(wǎng)絡(luò)模型、智能優(yōu)化算法等方法從各角度對系統(tǒng)進(jìn)行分析建模和優(yōu)化求解,但其對應(yīng)的數(shù)據(jù)預(yù)處理和建模轉(zhuǎn)化等環(huán)節(jié)難度較大,因此此類方法對用戶提出了很高的要求.近些年來,隨著信息量和數(shù)據(jù)量的激增,用戶所需要服務(wù)的數(shù)量也愈加龐大.工作流一類的方法已然不能滿足服務(wù)結(jié)構(gòu)多樣性的要求,而數(shù)據(jù)分析和人工智能也因為各自特點的限制導(dǎo)致其難以有效解決服務(wù)組合的動態(tài)搜索和自適應(yīng)性等問題.

Petri 網(wǎng)是一種針對分布式系統(tǒng)的分析和建模工具,具備異步并發(fā)及圖形化特性,能夠充分表達(dá)系統(tǒng)狀態(tài)變化及信息交互的行為屬性.因此,國內(nèi)外學(xué)者[7?10]提出利用Petri 網(wǎng)及其擴(kuò)展方法對Web 服務(wù)組合進(jìn)行系統(tǒng)建模.文獻(xiàn)[7]提出了基于普通Petri 網(wǎng)的Web 服務(wù)組合代數(shù)計算方法,以Petri 網(wǎng)結(jié)構(gòu)表示服務(wù)系統(tǒng)操作符,通過形式語義將代數(shù)組合轉(zhuǎn)化為網(wǎng)系統(tǒng)描述,利用Petri 網(wǎng)屬性和基本理論驗證了服務(wù)組合規(guī)則及控制流的正確性.但普通Petri 網(wǎng)不能精確表達(dá)服務(wù)組合過程的消息機(jī)制、功能接口等,無法構(gòu)建形式化業(yè)務(wù)流程.因此,文獻(xiàn)[8?10]基于普通Petri 網(wǎng)對其概念進(jìn)行拓展來表達(dá)服務(wù)組合過程:文獻(xiàn)[8]使用時間加權(quán)以分層結(jié)構(gòu)描述服務(wù)操作的功能類別,簡化服務(wù)觸發(fā)條件,降低了服務(wù)系統(tǒng)的復(fù)雜性,在一定程度上提高了系統(tǒng)的組合效率;文獻(xiàn)[9]利用有色Petri 網(wǎng)描述服務(wù)語義,保證組件服務(wù)的語義一致性,以有色標(biāo)記表示組合服務(wù)的狀態(tài)變遷過程,實現(xiàn)多組件服務(wù)數(shù)據(jù)流和控制流的語義規(guī)范;文獻(xiàn)[10]引入了模糊Petri 網(wǎng)語義描述變遷規(guī)則,以模糊命題的隸屬度值表示服務(wù)系統(tǒng)庫所標(biāo)記,且信任度和閾值通過映射函數(shù)對應(yīng),優(yōu)化了系統(tǒng)穩(wěn)定性度量方法,對提高系統(tǒng)可靠度有一定的作用.所以Petri 網(wǎng)能夠有效地描述Web 服務(wù)及其參數(shù),利用語義和工作流等規(guī)則整合分布式服務(wù),在服務(wù)篩選時能節(jié)約服務(wù)資源空間,簡化服務(wù)組合流程,同時也提高了系統(tǒng)服務(wù)的組合效率,為用戶提供了一種簡便、高效的Web 服務(wù)組合思路.

Petri 網(wǎng)的出現(xiàn),解決了網(wǎng)絡(luò)大數(shù)據(jù)下Web 服務(wù)種類多樣、參數(shù)復(fù)雜及用戶多元需求服務(wù)量大的問題.但組合過程中,隨著服務(wù)數(shù)增多,組合系統(tǒng)受時間變化的影響也將不斷增大,時變因素在服務(wù)組合質(zhì)量評價中不可忽略.例如,服務(wù)評價指標(biāo)中的服務(wù)可用性和可靠性等參數(shù)具有隨時間變化而改變的特性,傳統(tǒng)的Petri 網(wǎng)建模方法忽略了這些固有參數(shù)隨時間變化對服務(wù)質(zhì)量的影響,已不足以表達(dá)包含時間因素影響在內(nèi)的服務(wù)組合策略.同時,由于服務(wù)組合時用戶事先無法對各領(lǐng)域中眾多Web 服務(wù)進(jìn)行一一篩選和調(diào)研,若服務(wù)組合時出現(xiàn)錯誤,將直接造成難以估量的人力、物力損失.因此,對服務(wù)組合過程進(jìn)行流程正確性驗證及系統(tǒng)性能分析是至關(guān)重要的.為了解決時間變化因素對服務(wù)組合建模的影響,本文提出一種包含可變時間參數(shù)的Petri 網(wǎng)建模方法,即時變Petri 網(wǎng)(time-varying Petri net,簡稱TVPN),通過對組合過程的時變參數(shù)描述及組合服務(wù)的流程正確性和系統(tǒng)性能進(jìn)行分析,以實現(xiàn)組合策略的計算.時變Petri 網(wǎng)是時間Petri 網(wǎng)[8]的高級拓展,在求解實際工程問題[11]、任務(wù)調(diào)度領(lǐng)域[12]都有廣泛應(yīng)用,適于描述與分析組合服務(wù)過程狀態(tài)變化.

本文的主要貢獻(xiàn)包括:

(1) 提出一種基于時變Petri 網(wǎng)的Web 服務(wù)組合過程建模方法;

(2) 基于所提建模方法計算用戶反饋評價,并以實際電廠信息調(diào)度服務(wù)平臺進(jìn)行系統(tǒng)性能分析和驗證.

本文第1 節(jié)介紹Web 服務(wù)及服務(wù)組合的相關(guān)概念.第2 節(jié)給出時變Petri 網(wǎng)的定義和性質(zhì),提出基于時變Petri 網(wǎng)的服務(wù)組合方法.第3 節(jié)通過算法設(shè)計對所提建模方法進(jìn)行QoS 分析驗證.第4 節(jié)為仿真驗證和結(jié)果分析.最后給出本文總結(jié)及工作展望.

1 服務(wù)與組合策略

Web 服務(wù)可以看作一系列網(wǎng)絡(luò)應(yīng)用組件程序的數(shù)據(jù)(data)和邏輯(logic)關(guān)系的集合,將服務(wù)S定義為三元組形式,即S=(n,Da,Lc),其中,n為服務(wù)名稱,Da為服務(wù)數(shù)據(jù)流,Lc為服務(wù)邏輯流.數(shù)據(jù)和邏輯關(guān)系是構(gòu)成單一服務(wù)的基本要素.

通過建立不同服務(wù)之間數(shù)據(jù)和邏輯對應(yīng)關(guān)系,進(jìn)而完成不同服務(wù)功能之間的組合,稱為組合服務(wù).根據(jù)Web服務(wù)業(yè)務(wù)流程執(zhí)行語言BPEL4WS[13]的相關(guān)描述,服務(wù)數(shù)據(jù)可以表示為一個二元組,即Da=(Sp,QS),其中,Sp為系統(tǒng)參數(shù),QS為QoS 屬性參數(shù);服務(wù)邏輯可以表示為一個三元組,即Lc=(I,O,Fl),其中,I為組件服務(wù)的輸入功能集,O為相應(yīng)服務(wù)可用輸出功能集,Fl表示服務(wù)間工作流的映射關(guān)系集.因此,構(gòu)造Web 服務(wù)組合過程對應(yīng)了構(gòu)建一定數(shù)量組件服務(wù)的輸入/輸出功能的映射關(guān)系.

定義1(映射規(guī)則).設(shè)服務(wù)S的數(shù)據(jù)流Da和邏輯流Lc已知,Lc中某一輸入功能i∈I及其對應(yīng)的輸出功能o∈O,則單一輸入i和輸出o以邏輯關(guān)系l∈Lc相對應(yīng),可記作l:i→o,其描述了由服務(wù)邏輯l建立了一個由輸入功能i到輸出功能o的映射規(guī)則.由此可知,對于一組服務(wù)的邏輯關(guān)系,將其形式化定義為三元組形式,即fl=(im,on,ls),其中,im表示組件源服務(wù)的輸入功能,on表示組件目標(biāo)服務(wù)的輸出功能,ls表示當(dāng)前服務(wù)對應(yīng)的映射關(guān)系,稱為建立的服務(wù)映射規(guī)則,且fl∈Fl,,表示建立一組輸入/輸出功能的服務(wù)映射規(guī)則集.

定義2(服務(wù)候選集).給定若干組件服務(wù)S,根據(jù)用戶需求及服務(wù)功能,可在其基礎(chǔ)上進(jìn)一步得到服務(wù)候選集WS={S1,S2,…,Sn},其對應(yīng)包含的組件服務(wù)可表示為,其中,規(guī)定為服務(wù)候選集包含的全部服務(wù)名稱集,Da*={∪Dak}為服務(wù)候選集包含的全部服務(wù)數(shù)據(jù)集,Lc*={∪Lck}為服務(wù)候選集中包含的全部服務(wù)邏輯及工作流關(guān)系集.因此,針對服務(wù)候選集,各組件服務(wù)所包含的全部輸入/輸出功能中,可結(jié)合不同需求由Fl構(gòu)造數(shù)據(jù)、邏輯映射關(guān)系的各種組合,進(jìn)而生成得到特定功能的可執(zhí)行組合服務(wù).

定義3(服務(wù)組合策略).已知服務(wù)候選集WS中包含n個組件服務(wù),其中第i個服務(wù)Si作為根據(jù)用戶需求設(shè)定的源組件服務(wù),則可建立服務(wù)Si到其余最多n?1 個組件服務(wù)的映射規(guī)則,將得到組合服務(wù)集記為St,即

稱Sti為建立的一個服務(wù)組合策略,St也稱為服務(wù)組合策略集,其中,flij表示單一組件服務(wù)的映射規(guī)則,m是為服務(wù)組合策略的個數(shù),1≤m≤M,M為滿足用戶需求的最大服務(wù)組合策略數(shù),且M≤(n?1)!.

目前,國際上針對Web 服務(wù)組合的相關(guān)研究,通?；诮Y(jié)構(gòu)化信息標(biāo)準(zhǔn)促進(jìn)組織(OASIS[13])發(fā)布的UDDI及SOAP 消息機(jī)制.根據(jù)服務(wù)功能間的異步特性,圖1 為由組件服務(wù)間的映射規(guī)則集Fl構(gòu)建服務(wù)組合策略的一次組合過程,根據(jù)用戶偏好,兩個服務(wù)間的功能組合根據(jù)映射規(guī)則的不同而實現(xiàn)不同組合.每兩個組件服務(wù)間完成一次組合過程都包括多組輸入/輸出功能的轉(zhuǎn)換及數(shù)據(jù)、邏輯參數(shù)的反復(fù)調(diào)用,每生成一個服務(wù)組合策略時,都對應(yīng)生成一組服務(wù)映射規(guī)則集Flk,k=1,2,…,則St對應(yīng)的全部映射規(guī)則集為Fl*={∪Flk}.

例1(電廠信息調(diào)度服務(wù)平臺系統(tǒng)):本文采用研究團(tuán)隊針對國內(nèi)某電廠調(diào)度規(guī)程設(shè)計開發(fā)的電廠信息調(diào)度服務(wù)平臺系統(tǒng)為研究對象,描述相關(guān)Web 服務(wù)問題及組合流程的特性驗證.其具體執(zhí)行過程為:首先,用戶發(fā)布電力信息調(diào)度服務(wù)請求,將所需服務(wù)的邏輯功能和數(shù)據(jù)參數(shù)進(jìn)行處理,并轉(zhuǎn)化為組件服務(wù)操作形式;然后,系統(tǒng)自動篩選用戶需求,按調(diào)度功能,將組件服務(wù)劃分為發(fā)電信息服務(wù)(S1)或輸電信息服務(wù)(S2),并通過一系列數(shù)據(jù)檢索、驗證和報錯反饋,自動提取一組電力信息調(diào)度服務(wù)(S3)數(shù)據(jù);再根據(jù)電廠工作人員使用該服務(wù)平臺系統(tǒng)的反饋評價,綜合分析各項服務(wù)質(zhì)量數(shù)據(jù),以保證用戶方案的正確性,執(zhí)行一組可調(diào)用的信息評估方案組合服務(wù)(S4);最后,篩選得到的綜合評估方案,利用策略選擇服務(wù)(S5)獲取并發(fā)布當(dāng)前最滿足用戶需求的信息調(diào)度服務(wù)組合策略.電廠信息調(diào)度平臺的服務(wù)流程優(yōu)先級可用(S1∨S2)

電廠信息調(diào)度服務(wù)平臺系統(tǒng)能提供完備的信息調(diào)度服務(wù)流程,基本服務(wù)候選集為WS={S1,S2,S3,S4,S5},其中,各基本服務(wù)以SOAP 消息機(jī)制和UDDI 協(xié)議實現(xiàn)功能編碼和數(shù)據(jù)流、控制流交互,通過不同建模方法實現(xiàn)特定功能服務(wù)的發(fā)布與綁定,建立服務(wù)邏輯和映射規(guī)則二者之間的對應(yīng)關(guān)系.以發(fā)電信息服務(wù)為例,其可以用S1=(n1,Da1,Lc1)進(jìn)行描述.其中,n1={發(fā)電信息}表示服務(wù)名稱集;Da1=(Sp1,QS1)表示數(shù)據(jù)集合,其中Sp1={發(fā)電方式,發(fā)電量,功率,…},QS1={服務(wù)執(zhí)行費用,服務(wù)時間開銷};Lc1=(I1,O1,Fl1)表示邏輯集合,發(fā)電信息服務(wù)屬于一類系統(tǒng)源組件服務(wù),可知輸入功能集I1=?,輸出功能集O1={執(zhí)行調(diào)度信息服務(wù)},Fl1為映射規(guī)則集,基本控制流邏輯結(jié)構(gòu)包括順序、選擇、分支并發(fā)、邏輯循環(huán)這 4 種,對應(yīng)了調(diào)用下一組件服務(wù)的工作流對應(yīng)關(guān)系.因此,根據(jù)此電廠信息調(diào)度服務(wù)的功能順序分別選擇不同服務(wù)執(zhí)行,該服務(wù)平臺共可生成個服務(wù)組合策略,即St={St1,St2,St3,St4,St5,St6,St7,St8}.

Fig.1 Mapping rules to input/output functions of component services圖1 組件服務(wù)輸出/輸入功能的映射規(guī)則

Fig.2 Services flow of the system of information dispatching platform for power plant圖2 電廠信息調(diào)度服務(wù)平臺系統(tǒng)的服務(wù)流程

2 時變Petri 網(wǎng)與服務(wù)描述

2.1 Petri網(wǎng)及其特性

Petri 網(wǎng)是一類狀態(tài)變遷模型,可用于描述系統(tǒng)中各異步成分之間的關(guān)系,允許系統(tǒng)并發(fā)執(zhí)行各個狀態(tài)的變遷.Petri 網(wǎng)通過無孤立點的有向二分圖來描述系統(tǒng)結(jié)構(gòu),利用標(biāo)識符反映系統(tǒng)狀態(tài).

定義4(有向網(wǎng)[13]).當(dāng)且僅當(dāng)三元組N=(P,T,F)滿足如下條件時,稱N為一個有向網(wǎng).

(1)P∪T≠?,P∩T=?;

(2)F?{(P×T)∪(T×P)};

(3)P∪T={x|?y:(x,y)∈F}∪{y|?x:(x,y)∈F}.其中,P為有限庫所(place)集,T為有限變遷(transition)集,F為基于P和T建立的有向弧集合,表示有向網(wǎng)中的工作流關(guān)系.

定義5(輸入集和輸出集[13]).對于?x∈P∪T,稱′x={y|(y∈P∪T)∧((y,x)∈F)}為x的輸入集;稱x′={y|(y∈P∪T)∧((x,y)∈F)}為x的輸出集.

定義6(Petri 網(wǎng)[13]).當(dāng)且僅當(dāng)滿足下列條件時,稱二元組PN=(N,M)為一個Petri 網(wǎng).

(1)N=(P,T,F)是一個有向網(wǎng).

(2)M:P→N+是PN的標(biāo)識函數(shù),M0為初始標(biāo)識,N+為正整數(shù)集.

(3) 觸發(fā)規(guī)則:

①如果?p∈′t:M(p)≥1 時,稱變遷t是使能的,表示為M[t〉.

② 如果狀態(tài)標(biāo)識M下t是使能的,則稱t可以觸發(fā),且觸發(fā)后得到的后繼標(biāo)識為M′,記作M[t〉M′.且有:

定義7(可達(dá)標(biāo)識集[13]).若Petri 網(wǎng)系統(tǒng)PN=(N,M)中存在t∈T,使得M[t〉M′,則稱M′是從M可達(dá)的.則PN中從M可達(dá)的全部標(biāo)識的集合稱為可達(dá)標(biāo)識集,記作R(M),且滿足M0∈R(M);同時,對于?t∈T,若?M∈R(M),則必?M′∈R(M).

定義8(關(guān)聯(lián)矩陣[13]).若Petri 網(wǎng)PN=(N,M)中,N=(P,T,F),P={p1,p2,…,pm},T={t1,t2,…,tm},則PN中有向網(wǎng)N可以表示為一個n行m列的矩陣A=[aij]n×m,當(dāng)且僅當(dāng)A滿足下列條件時,稱A為PN的關(guān)聯(lián)矩陣.

定義9(遷移矩陣[13]).當(dāng)且僅當(dāng)矩陣K=A?diag(t1,t2,…,tn)A+滿足如下條件時,稱K為Petri 網(wǎng)PN的遷移矩陣.

(1) |ti|=1,變遷觸發(fā);

(2) |ti|=0,變遷失效.

其中,ti是PN中的變遷,i=1,2,…,n.

2.2 時變Petri網(wǎng)及服務(wù)描述

時變Petri 網(wǎng)是在包含時間因素影響的時間Petri 網(wǎng)基礎(chǔ)上拓展而來的,通過描述系統(tǒng)中可變時間函數(shù)對綜合性能和邏輯層次的變遷過程,以Petri 網(wǎng)有向二分圖的網(wǎng)狀結(jié)構(gòu)性質(zhì),在庫所中用包含時間參量的標(biāo)識符函數(shù)狀態(tài)記錄時間變化對節(jié)點結(jié)構(gòu)的影響;同時,對時間并發(fā)性以及邏輯異步特性也能夠進(jìn)行很好地描述.

為了便于描述可變時間函數(shù)與Petri 網(wǎng)中庫所、變遷等基本元素關(guān)系,用符號p|δ表示庫所p在時間函數(shù)表達(dá)式下對變遷觸發(fā)產(chǎn)生的作用.令p|δ=Yt,則Yt表示庫所p在時間參量影響下標(biāo)識符函數(shù)狀態(tài)發(fā)生變化的度量;令p|δ=Nt,則Nt表示庫所p在時間參數(shù)影響下不可觸發(fā)變遷,即時間參量不影響系統(tǒng)狀態(tài).當(dāng)系統(tǒng)某一變遷使能時,將根據(jù)時間函數(shù)中輸入功能時變因子δi和輸出功能時變因子δo對功能庫所的狀態(tài)標(biāo)識函數(shù)集,及可變時間參量進(jìn)行相應(yīng)記錄和調(diào)整,以便于確保系統(tǒng)下次觸發(fā)的基本條件.

對一個已知建立在普通Petri 網(wǎng)PN 基礎(chǔ)上的系統(tǒng),將時變Petri 網(wǎng)給出下面的定義形式.

定義10(時變庫所).對?p∈P,若系統(tǒng)中存在輸入/輸出功能的時變因子δ可觸發(fā)其狀態(tài)的變遷,即滿足成立,則稱該庫所p為庫所集p中的時變庫所.

定義11(時變函數(shù)表達(dá)式).對于時變庫所p∈P,記fδ為庫所p在狀態(tài)M下的時變函數(shù)表達(dá)式,則有:

其中,M(p)=1 表示標(biāo)識符函數(shù)M滿足時變庫所p的時變參量影響條件,M(p)=0 表示標(biāo)識符函數(shù)M不滿足時變庫所p的時變參量影響條件.

定義12(時變Petri 網(wǎng)).當(dāng)且僅當(dāng)滿足如下條件時,五元組TVPN=(P,T,F,M,)稱為一個時變Petri 網(wǎng).

(1)p是一個庫所集合,其中包含的全部時變庫所構(gòu)成的集合是p的一個子集;

(2)T是一個變遷集合,滿足P∪T≠?;且對于?t∈T的前置集′t和后置集t′,滿足′t∩t′=?;同時,變遷t的觸發(fā),與所對應(yīng)的時變庫所時變函數(shù)表達(dá)式fδ有關(guān),并對應(yīng)引導(dǎo)標(biāo)識符函數(shù)的變化;

(3)F?{(P×T)∪(T×P)}表示一個包含時間因素的有向弧集合;

(4)M表示TVPN 中狀態(tài)標(biāo)識符函數(shù)集合,且滿足M0∈R(M),M(p)表示庫所p中包含的標(biāo)識符函數(shù)值;

(5)Fδ表示TVPN 中時變函數(shù)式集合,分別包含變遷t所對應(yīng)的時變輸入功能函數(shù)式集合FIδ和時變輸出功能函數(shù)式集合FOδ,且Fδ=FIδ∪FOδ,Fδ中函數(shù)式及其值均為時變的,即與時間因子δ有關(guān);

(6) 變遷觸發(fā)規(guī)則:對?t∈T,令,若fIδ|M=Yt,則稱變遷輸入′t滿足狀態(tài)M

下的時間因式fIδ,也稱t在M下可觸發(fā);當(dāng)t在M下觸發(fā)后,由時變輸出fOδ引導(dǎo)并演變?yōu)樾碌臉?biāo)識M′:

其中,m,n∈N+為系統(tǒng)中組件服務(wù)對應(yīng)的全部輸入/輸出功能數(shù)量.

在TVPN 中,當(dāng)某一變遷觸發(fā)時,會受到系統(tǒng)局部外延和時變因子δ的影響,若在表示變遷觸發(fā)的有向弧上添加包含時變輸入功能函數(shù)fIδ和時變輸出功能函數(shù)fOδ,有利于清晰描述變遷使能條件及系統(tǒng)時變參數(shù)引發(fā)的輸入/輸出功能庫所狀態(tài)特性的相應(yīng)變化.

本文中在對時變Petri 網(wǎng)及其結(jié)構(gòu)進(jìn)行描述時,庫所利用實線圓圈進(jìn)行表示,時變庫所利用虛線圓圈進(jìn)行表示,操作變遷利用矩形框進(jìn)行表示,服務(wù)變遷利用梯形框進(jìn)行表示,標(biāo)識符利用圓點表示.對于TVPN 中基本元素的圖形化描述,將時變輸入函數(shù)表達(dá)式fIδ和時變輸出表達(dá)式fOδ標(biāo)注在變遷觸發(fā)的有向弧上,用于表示受可變時間因素影響的狀態(tài)觸發(fā)及部分系統(tǒng)外延結(jié)構(gòu),其基本元素的功能關(guān)系如圖3 所示.

Fig.3 Kinds of time-varying transitions of TVPN圖3 TVPN 中的時變功能變遷類型

圖3(a)為普通Petri 網(wǎng)的功能變遷結(jié)構(gòu),變遷觸發(fā)不受時間因素影響,只與庫所及標(biāo)識狀態(tài)有關(guān);圖3(b)表示時變Petri 網(wǎng)結(jié)構(gòu)中,變遷由時變輸入fiδ影響觸發(fā),且變遷發(fā)生后由時變輸出fOδ引導(dǎo)指向下一時變庫所;圖3(c)表示時變庫所的變遷只由時變輸入fiδ觸發(fā),不存在時變輸出fOδ影響,其指向不包含時間因素的庫所;圖3(d)表示變遷不受時變輸入fiδ影響,只受時變輸出fOδ引導(dǎo),并指向當(dāng)前的時變庫所.

2.3 基于時變Petri網(wǎng)的Web服務(wù)組合模型

在Web 服務(wù)及其組合過程中,很多情況下使用到的Web 服務(wù)源自很多各類領(lǐng)域,因此與之相對應(yīng)服務(wù)的篩選配置時間也有顯著差異.如果設(shè)定的組合流程中可隨機(jī)選擇有限服務(wù)集,則通過組合組件服務(wù)得到的綜合QoS 值和用戶反饋評價指標(biāo)將受到時變函數(shù)因素的較大的影響.在組件服務(wù)本身性能的約束條件下,QoS 值直接決定了組合服務(wù)是否能夠執(zhí)行并達(dá)到預(yù)期效果.因此,考慮利用時變Petri 網(wǎng)建模分析服務(wù)組合問題并對分析計算時變函數(shù)對QoS 的影響,進(jìn)而可以實現(xiàn)在將結(jié)果發(fā)布到實際系統(tǒng)前,對組合服務(wù)的流程正確性和QoS 量化值進(jìn)行評估.

定義13(Web 服務(wù)組合的時變Petri 網(wǎng)模型).稱六元組SC-TVPN=(WS,Fl,St,N,M,)為一個基于時變Petri 網(wǎng)的服務(wù)組合模型,當(dāng)且僅當(dāng)滿足如下條件時成立.

(1)WS為服務(wù)候選集,其包含了n個基本服務(wù)S1,S2,…,Sn;

(2)Fl為組合服務(wù)過程對應(yīng)的映射規(guī)則集;

(3)St為基于服務(wù)流程算法的組合服務(wù)策略集;

(4)N表示一個有向Petri 網(wǎng)系統(tǒng),其對應(yīng)包含了時變庫所集、有限變遷集和工作流關(guān)系;

(5)M表示網(wǎng)系統(tǒng)中庫所和時變庫所的標(biāo)識符狀態(tài)函數(shù)集;

(6)Fδ表示組件服務(wù)功能庫所間所包含的時變函數(shù)式集合,時變輸入功能函數(shù)式集用FIδ表示,時變輸出功能函數(shù)式集用FOδ表示.

在SC-TVPN 中,對其基本要素包含下述幾點說明.

(1) 庫所集合P中包含服務(wù)的數(shù)據(jù)流庫所pD和服務(wù)的邏輯流庫所pL,上述兩類庫所對應(yīng)的子集分別為PD和PL,滿足,且PD∩PL=?,pi為不包含時間因子的一般庫所.前者中存在兩個特殊庫所——源組件服務(wù)庫所(只含輸出功能)和終止組件服務(wù)庫所(只含輸入功能),普通數(shù)據(jù)流庫所用于存儲服務(wù)及組合過程中的數(shù)據(jù)和功能;后者主要用于記錄服務(wù)組合時的參數(shù)轉(zhuǎn)換、功能執(zhí)行等邏輯過程.

(2) 在變遷集合T中,對于?t∈T,′t和t′都至少包含1 個時變函數(shù)式引導(dǎo)的時變庫所.

(3)Fδ中包含一組時變的功能函數(shù)集,其用于表示SC-TVPN 描述服務(wù)組合過程對應(yīng)的時間參數(shù)驅(qū)動Petri網(wǎng)系統(tǒng)使能.組件服務(wù)間的庫所和變遷觸發(fā)都需要滿足Fδ的約束條件.

(4) 基于BPEL4WS 相關(guān)描述,在SC-TVPN 的服務(wù)組合邏輯流包含了順序、并發(fā)、分支選擇和邏輯循環(huán)共4 種控制結(jié)構(gòu),如圖4 所示.

為了表達(dá)引入時變函數(shù)關(guān)系導(dǎo)致的Petri 網(wǎng)異構(gòu)變化特性,本文采用Petri 網(wǎng)標(biāo)記語言(Petri net markup language,簡稱PNML)[13]來描述時變Petri 網(wǎng)服務(wù)組合模型的邏輯結(jié)構(gòu).其中,PNML 是一種基于XML 的Petri網(wǎng)系統(tǒng)信息交互形式,包含可讀性、通用性及相關(guān)性這3 方面設(shè)計原則,以元模型、類型定義接口、特性定義接口等形式清晰表達(dá)Petri 網(wǎng)及其拓展模型的結(jié)構(gòu),是Petri 網(wǎng)交換格式標(biāo)準(zhǔn)的一種解決方案.

本文以服務(wù)組合過程中組合流程的正確性驗證,及用戶反饋評價服務(wù)質(zhì)量中時間屬性為研究重點.可將QoS 定義為一組服務(wù)的非功能屬性集合,根據(jù)用戶偏好,包含一系列評價指標(biāo).根據(jù)本文服務(wù)系統(tǒng)構(gòu)造及電廠調(diào)度信息服務(wù)的用戶需求,對所做研究針對的服務(wù)質(zhì)量作出如下定義.

定義14(服務(wù)質(zhì)量).四元組QoS=(Ps,Ts,As,Rs)為用戶反饋的服務(wù)質(zhì)量,其中包含一組服務(wù)組合策略的非功能屬性數(shù)據(jù).在用戶組合服務(wù)整個過程中:Ps為服務(wù)執(zhí)行費用(單位:元,CNY);Ts為服務(wù)執(zhí)行的時間開銷(單位:s,秒);As為服務(wù)可用性,表示系統(tǒng)提供可用組件服務(wù)的能力;Rs為服務(wù)可靠性,即系統(tǒng)成功執(zhí)行組合服務(wù)的概率.對服務(wù)時間開銷Ts,其值為SC-TVPN 系統(tǒng)內(nèi),構(gòu)建組合服務(wù)的全部組件服務(wù)所包含的變遷觸發(fā)及外延時間變化中,所有時變輸入功能函數(shù)式和時變輸出功能函數(shù)式的函數(shù)值代數(shù)之和.

將服務(wù)系統(tǒng)中的組件服務(wù)及組合服務(wù)策略的QoS 屬性記作四維列向量qj形式,則對于一組包含n個組件服務(wù)的服務(wù)候選集WS={S1,S2,…,Sn},可將其全部服務(wù)的QoS 屬性記為一個n×4 階矩陣Q=Qij,其中,i,j,n為根據(jù)用戶需求設(shè)定的自然數(shù),且1≤i≤n,1≤j≤4,表示服務(wù)組合策略中包含的組件服務(wù)屬性數(shù)據(jù).

根據(jù)基本工作流關(guān)系,將服務(wù)質(zhì)量的非功能屬性設(shè)置為隨機(jī)變量,對其數(shù)據(jù)采用隨機(jī)變量組合法進(jìn)行度量和計算.表1 為SC-TVPN 服務(wù)組合系統(tǒng)下,用戶所提偏好及約束條件的QoS 計算方法,其中,αi為分支選擇結(jié)構(gòu)第i個組件服務(wù)操作被調(diào)用的概率系數(shù),i=0 時,表示跳過組件;i=1 時,表示選擇該組件服務(wù).

Fig.4 Structures of logic in SC-TVPN圖4 SC-TVPN 中的邏輯結(jié)構(gòu)類型

Table 1 Calculation methods of random variable data of non-functional properties on QoS表1 QoS 的非功能屬性隨機(jī)變量數(shù)據(jù)計算方法

由于QoS 各屬性量綱不一致,無法通過4 個屬性值直接衡量用戶滿意度及使用評價,因此需要對各維屬性參數(shù)進(jìn)行量化處理.對于服務(wù)執(zhí)行費用和時間開銷指標(biāo),隨著參數(shù)值越大,QoS 越低,屬于負(fù)相關(guān)性影響指標(biāo);對于服務(wù)可用性和可靠性指標(biāo),隨著參數(shù)值越大,服務(wù)質(zhì)量越高,屬于正相關(guān)性影響指標(biāo).對正、負(fù)相關(guān)性指標(biāo)分別用公式(1)和公式(2)進(jìn)行量化.

其中,V(t)(Pr)為量化結(jié)果.然后,對量化數(shù)據(jù)采取誤差標(biāo)準(zhǔn)化處理,其實現(xiàn)過程如公式(3)所示.

其中,Pr(u,i)為用戶對第i個服務(wù)反饋的服務(wù)數(shù)據(jù)量化值,Si為組件服務(wù)數(shù)據(jù)的誤差率,θ為誤差容錯限值,di為參數(shù)標(biāo)準(zhǔn)化權(quán)值.再根據(jù)用戶偏好,設(shè)置服務(wù)非功能屬性匹配權(quán)值ω,令ωi=di,且ωi∈[0,1],,并計算QoS 數(shù)據(jù)歸一化值,用V(QoS)表示,計算過程如公式(4)所示.

最后,根據(jù)得到的歸一化值V(QoS)及用戶匹配權(quán)值ω,由公式(5)計算該組合服務(wù)的綜合服務(wù)質(zhì)量值Ψ.

其中,Ψ∈[0,1].由計算過程可知,其值越大,表示組合服務(wù)策略越能滿足用戶特定需求,越接近用戶的期望滿意度.

3 服務(wù)組合模型的性能分析

為了驗證所提模型在服務(wù)質(zhì)量(QoS)的時間開銷屬性上具有有效性和可行性,本節(jié)首先說明服務(wù)組合對語義和流程正確性檢驗的必要性;然后給出時變Petri 網(wǎng)下,隨著時間參數(shù)變化導(dǎo)致庫所的狀態(tài)變遷觸發(fā)條件,使服務(wù)系統(tǒng)滿足狀態(tài)可達(dá)性,即實現(xiàn)服務(wù)組合驅(qū)動條件;并提出一種基于服務(wù)路徑回溯檢驗的魚群組合算法,該算法能有效減小服務(wù)候選集的檢索空間,避免服務(wù)庫所的冗余利用,可實現(xiàn)大規(guī)模服務(wù)候選集中,高效檢索組件服務(wù),快速構(gòu)建組合服務(wù)輸入/輸出功能匹配及用戶需求QoS 度量值的服務(wù)組合策略.

3.1 組合服務(wù)性能分析的前提

服務(wù)組合模型的性能分析,主要從兩方面檢驗[14,15].

(1) 語義規(guī)范性.服務(wù)組合的PNML 語義描述滿足設(shè)定的匹配規(guī)范,即在語義上能夠滿足參數(shù)統(tǒng)一、操作協(xié)同、節(jié)點狀態(tài)穩(wěn)定及觸發(fā)條件充分等要求;同時,通過對組合控制邏輯和QoS 屬性的語義一致性檢驗,保證流程上能夠正確執(zhí)行.

(2) 流程正確性.通過對建模流程進(jìn)行驗證,進(jìn)而保證工作流語義描述正確性、系統(tǒng)狀態(tài)可達(dá)性、邏輯流程死鎖性及系統(tǒng)邊界性等要求.

結(jié)合服務(wù)本身特性分析,戶反饋評價及服務(wù)質(zhì)量主要依賴模型語義描述和功能參數(shù),與此同時參數(shù)調(diào)配、映射規(guī)則、時變參數(shù)、變遷觸發(fā)、操作條件等也都可能對性能產(chǎn)生一定的影響.

為了清晰地明確組合服務(wù)性能分析的相關(guān)概念,考慮對時變Petri 網(wǎng)服務(wù)模型進(jìn)行簡化.若一個給定的服務(wù)候選集WS={S1,S2,…,Sn},其對應(yīng)的映射規(guī)則集合為建立的某一服務(wù)組合策略Sti以S0為起始服務(wù).由時變Petri 網(wǎng)特性,令該服務(wù)模型抽象為四元組TVPN=(N,M,L,Fδ).其中,

·Fδ表示時變輸入/輸出函數(shù)集合;

·M表示功能標(biāo)識符函數(shù)集合,Mk(S)表示對調(diào)用某服務(wù)狀態(tài)的輸入/輸出功能標(biāo)記;

·L表示時變Petri 網(wǎng)的有向弧集合,有向弧對應(yīng)包含了服務(wù)間的控制邏輯和功能屬性信息;同時,其表示為三元組l′=(oi,ij,fl),其中,oi表示此前服務(wù)的輸出,ij表示與此前服務(wù)相匹配的后一服務(wù)輸入,fl為其包含邏輯關(guān)系所對應(yīng)的服務(wù)映射規(guī)則.

為了方便討論服務(wù)節(jié)點使能狀態(tài)與時變函數(shù)觸發(fā)庫所變遷的關(guān)系,首先需在組件服務(wù)的組合過程進(jìn)行聲明,避免組合過程中冗余服務(wù)重復(fù)調(diào)用導(dǎo)致系統(tǒng)效率降低,引入回溯網(wǎng)絡(luò)節(jié)點定理對組件服務(wù)節(jié)點作出標(biāo)記,即定理1 用于判斷是否存在冗余服務(wù)操作類型,建立控制流的基本邏輯關(guān)系.

定理1(回溯網(wǎng)絡(luò)節(jié)點定理).對于一個時變Petri 網(wǎng)服務(wù)組合模型SC-TVPN,若有向弧l′=(oi,ij,fl)滿足M(pin∩sk)?M(p),且任意以is為輸入功能的終止服務(wù)sn至少具備1 條最簡有向路徑使服務(wù)組合策略成立,其中,li,lj,ls表示被有向路徑L覆蓋的有向弧,li表示源組件服務(wù)輸出功能指向的有向時變函數(shù)弧,ls表示終止服務(wù)所包含時變函數(shù)的輸入功能有向弧,則其余非最簡有向路徑L′上的任一有向弧l對應(yīng)的標(biāo)識集滿足:

其中,L′為有向弧L上以第j個服務(wù)為起始服務(wù)的回溯子弧,i,j,s,n∈N+.

為保證組合服務(wù)策略分支流程是正確的,當(dāng)執(zhí)行前i個服務(wù)的輸出功能組合操作時,需檢驗此前組件服務(wù)功能路徑的動作過程,將這一過程稱為回溯檢驗.構(gòu)建含n個組件服務(wù)的策略則需進(jìn)行n?(n?1)/2 次回溯檢驗,且需要對每條有向弧回溯路徑對應(yīng)的QoS 屬性進(jìn)行一致性驗證.

定理2(系統(tǒng)狀態(tài)可達(dá)性定理).設(shè)時變Petri 網(wǎng)服務(wù)組合模型SC-TVPN 中,若時變函數(shù)集Fδ={fδ1,…,fδn}在?ti∈T,pj∈P都滿足關(guān)聯(lián)矩陣Aij對應(yīng)的功能映射關(guān)系,且至少存在1 條從p0到pn的有向回溯路徑,使其滿足狀態(tài)遷移矩陣K,且?M∈R(M),?pk∈P,使Mk[tk.fδk.pk〉Mp.

證明:令Mp為SC-TVPN 中構(gòu)建的某一服務(wù)組合策略St所包含第i個組件服務(wù)Si的起始輸出功能狀態(tài)或前一服務(wù)Si?1的終止輸入功能狀態(tài).在時變函數(shù)作用下,只有Si?1的輸出功能庫所和Si的輸入功能庫所具有時間關(guān)聯(lián),其他服務(wù)不受時變函數(shù)fδk的影響,每發(fā)生一次狀態(tài)觸發(fā),用一個標(biāo)識符函數(shù)相對應(yīng),構(gòu)建系統(tǒng)關(guān)聯(lián)矩陣表示組件服務(wù)功能調(diào)用的概率,則只有當(dāng)狀態(tài)滿足Mk[tk.fδk.pk驅(qū)動節(jié)點Mp狀態(tài)使能時,系統(tǒng)狀態(tài)滿足可達(dá)性.因此,當(dāng)前i?2 個組件服務(wù)組合后,Si庫所可以遷移至狀態(tài)Mk,并使其能夠到達(dá)任意組件服務(wù)狀態(tài).

定理2 表明SC-TVPN 實現(xiàn)服務(wù)組合過程中,若某一服務(wù)節(jié)點狀態(tài)在時變函數(shù)下使能,則與其有時間關(guān)聯(lián)特性的庫所周期狀態(tài)將由變遷條件等待觸發(fā).

為了進(jìn)一步說明服務(wù)組合的邏輯流控制過程及QoS 計算方法,假設(shè)服務(wù)候選集中,由前一組件服務(wù)S1的輸出功能和后一服務(wù)S2的輸入功能構(gòu)造一次服務(wù)節(jié)點組合匹配.構(gòu)造服務(wù)S1到S9的組合服務(wù),可由中間路徑的任意服務(wù)實現(xiàn),則選取兩個功能相同,組件服務(wù)不同的組合服務(wù)進(jìn)行QoS 計算,相應(yīng)的QoS 綜合值記為Ψ1和Ψ2.則經(jīng)回溯過程所求得的用戶綜合QoS 評價值分別為,ωk為根據(jù)用戶設(shè)定權(quán)值,則系統(tǒng)中庫所的基本控制流和數(shù)據(jù)流邏輯關(guān)系如圖5 所示.

Fig.5 Logical relationship of control flow and data flow in service model圖5 服務(wù)模型中的邏輯關(guān)系

組合服務(wù)過程中,后一服務(wù)S2的時變輸入功能集fIδ與前一服務(wù)S1的時變輸出功能fOδ以映射規(guī)則集中的服務(wù)規(guī)則fl相對應(yīng).對服務(wù)組合的回溯過程即對已組合部分的輸入/輸出映射關(guān)系檢驗的過程,這個過程可通過檢測對應(yīng)輸入/輸出功能集中的參數(shù)值獲取.

依據(jù)SC-TVPN 中服務(wù)控制流邏輯結(jié)構(gòu),引入組合成功率TR[16]的概念,用于比較構(gòu)建組合服務(wù)時,表示不同方法下組件服務(wù)的可用性及可靠性對組合服務(wù)可成功執(zhí)行的概率大小.本文中,組合成功率TR由公式(6)計算求得.

其中,li表示滿足組合服務(wù)功能的有向弧路徑長度;M(s)表示標(biāo)識符函數(shù)狀態(tài)集;t表示可觸發(fā)變遷;ω為回溯路徑涵蓋的組件服務(wù)中,QoS 屬性的用戶匹配權(quán)值,表示該組件服務(wù)在用戶需求功能的作用比重.

3.2 服務(wù)流程驗證及組合算法

為使服務(wù)候選集中,組件服務(wù)均能以特定服務(wù)選取概率進(jìn)行調(diào)用,因此需要對候選組件服務(wù)實現(xiàn)全局遍歷,記錄服務(wù)信息和節(jié)點狀態(tài).鑒于此,本文考慮在人工魚群算法[17]的基礎(chǔ)上利用人工魚個體信息對應(yīng)地記錄服務(wù)的輸入/輸出功能、QoS 數(shù)據(jù)及性能屬性.感知周圍環(huán)境信息的特點為基礎(chǔ),提出一種遍歷服務(wù)庫所及組合操作變遷的服務(wù)組合流程驗證及策略計算算法.該算法中,人工魚個體分別用于記錄組件服務(wù)的輸入/輸出功能、QoS 數(shù)據(jù)及性能參數(shù)等信息,通過建立的服務(wù)映射規(guī)則,對不同服務(wù)模型下建立的服務(wù)組合策略各項指標(biāo)進(jìn)行選擇和計算,進(jìn)而實現(xiàn)全局服務(wù)的篩選和優(yōu)化配置.

本文算法采用自頂而下的設(shè)計西路解決服務(wù)組合問題.首先,根據(jù)服務(wù)數(shù),將一定數(shù)量的人工魚個體置于服務(wù)候選集中,其用于記錄單一服務(wù)的性能參數(shù)、時變函數(shù)式及狀態(tài)信息,當(dāng)系統(tǒng)使能,滿足組合操作變遷觸發(fā)條件時,根據(jù)個體記錄的服務(wù)空間、時變庫所及變遷狀態(tài),即可實現(xiàn)對遍歷至當(dāng)前位置狀態(tài)的檢驗;然后,固定當(dāng)前服務(wù)狀態(tài)xi,根據(jù)設(shè)定的調(diào)用概率實現(xiàn)下一服務(wù)的調(diào)用,或?qū)σ呀M合的服務(wù)策略進(jìn)行遍歷檢驗,以得到與當(dāng)前服務(wù)狀態(tài)匹配的最優(yōu)組件服務(wù).

由于人工魚的主要活動受限于巡視視野內(nèi)的位置狀態(tài),通過與當(dāng)前位置進(jìn)行比較,選擇最優(yōu)動作作為下一時刻的活動方向.因而,考慮將尋找最優(yōu)服務(wù)策略與人工魚搜索更高濃度食物生存行為[16]建立聯(lián)系,則每個人工魚個體都將以向食物濃度更高的位置運(yùn)動作為目標(biāo).

鑒于此,為了提升服務(wù)組合模型的組合效率和可靠度,并從含大量組件服務(wù)的候選集中取得滿足要求的服務(wù)組合策略,需要有效提升個體的全局搜索能力,克服原始算法精度低和后期收斂速度慢等問題.因此,本文以基本魚群算法為基礎(chǔ),在人工魚個體位置更新過程中引入已知全局最優(yōu)的服務(wù)信息,進(jìn)而改善了個體遍歷的效率,其可以利用公式(7)～公式(9)進(jìn)行表示.

其中,Val表示個體的視野范圍;Sp表示隨機(jī)移動的步長;Ra(?)表示變量函數(shù)在區(qū)間[0,1]上服從隨機(jī)分布,其對應(yīng)服務(wù)組合時,滿足回溯條件的服務(wù)調(diào)用概率;Xi(t)是人工魚的當(dāng)前狀態(tài);Xi(t+1)是個體尋優(yōu)下一位置的狀態(tài);ΔXi(t+1)由當(dāng)前狀態(tài)和較優(yōu)狀態(tài)X′(t+1)的差值決定.

為保證組合策略St能反映真實系統(tǒng)的性能,在尋優(yōu)過程中,需要結(jié)合實際情況對服務(wù)參數(shù)設(shè)置可靠性和可用性等約束條件,刪除不滿足最低用戶需求的服務(wù)策略,進(jìn)而保證服務(wù)組合的效率,即滿足:

此方法用于檢驗時變庫所的狀態(tài)和變遷操作正確性,并可以用于計算不同模型下生成服務(wù)組合策略的綜合QoS 值,并在此基礎(chǔ)上依據(jù)用戶偏好性能提供一種最優(yōu)服務(wù)組合策略.基于服務(wù)組合的語義描述和邏輯結(jié)構(gòu),我們將算法流程驗證和組合計算歸納為如下步驟.

(1) 利用PNML 慣例文檔描述服務(wù)數(shù)據(jù)和邏輯功能,將服務(wù)系統(tǒng)轉(zhuǎn)化為時變Petri 網(wǎng)結(jié)構(gòu)框架.其中,para為組件服務(wù)性能參數(shù),data為服務(wù)基本信息或數(shù)據(jù);fδk(p,n)為受n個時變參數(shù)影響的第k個服務(wù)庫所,e(t〉)表示操作變遷t在fδk下使能,M為時變標(biāo)識符的集合.

(2) 遍歷服務(wù)系統(tǒng)中的時變參數(shù)庫所及服務(wù)變遷操作,計算Petri 網(wǎng)系統(tǒng)的狀態(tài)可達(dá)圖.

(3) 檢驗服務(wù)系統(tǒng)是否滿足語法正確性、狀態(tài)可達(dá)性及變遷死鎖性[16].

(4) 檢驗組合策略的功能特性、執(zhí)行順序和QoS 一致性.

(5) 計算并輸出全部服務(wù)組合策略,生成服務(wù)組合策略集合.

具體流程見算法1.

算法1.服務(wù)性能檢驗及組合分析算法.

輸入:服務(wù)候選集WS,服務(wù)映射規(guī)則,服務(wù)性能參數(shù).

輸出:組合分析檢驗結(jié)果,服務(wù)組合策略St和對應(yīng)結(jié)果.

上述過程通過服務(wù)組合性能模型和時變Petri 網(wǎng)的狀態(tài)可達(dá)性對服務(wù)對象加以分析.基于當(dāng)前狀態(tài)xi及對應(yīng)集合中其他狀態(tài)及映射規(guī)則,進(jìn)行完整地遍歷搜索.因此，可以實現(xiàn)對描述服務(wù)數(shù)據(jù)、邏輯的元素進(jìn)行正確性和一致性檢驗,進(jìn)而保證各項性能參數(shù)滿足QoS 需求.假設(shè)服務(wù)集中的服務(wù)數(shù)目表示為n,服務(wù)映射規(guī)則數(shù)目表示為m,人工魚個體檢索的最大循環(huán)次數(shù)為lmax,則所提算法對應(yīng)的最大時間復(fù)雜度為O(n),空間復(fù)雜度為O(m×lmax).同時,函數(shù)Test(ServiceFlow)可以保證系統(tǒng)性能評價的準(zhǔn)確性,函數(shù)Check&Calculation(St)則從QoS 屬性方面檢驗時變Petri 網(wǎng)服務(wù)模型的組合一致性,函數(shù)Genaration(St)可以高效計算系統(tǒng)效率及組合成功率.

4 仿真實驗及結(jié)果分析

本節(jié)根據(jù)時變Petri 網(wǎng)特性對服務(wù)組合過程進(jìn)行建模.首先,在服務(wù)系統(tǒng)中,對功能相同的Web 服務(wù)通過不同方法進(jìn)行語義綁定、參數(shù)設(shè)置、文檔發(fā)布,使其作為已發(fā)布的組件服務(wù)可任意調(diào)用;然后,對多功能分布式服務(wù)進(jìn)行組合,在不同方法下實現(xiàn)功能相似的組合服務(wù)構(gòu)建過程,并獲取相應(yīng)服務(wù)綁定數(shù)據(jù);對于用戶,則可任意調(diào)用系統(tǒng)發(fā)布的組合服務(wù),并給出相應(yīng)的用戶反饋評價;在大量數(shù)據(jù)提取及分析統(tǒng)計后,可表明時間因素對服務(wù)組合用戶反饋評價的影響;同時,為了進(jìn)一步證明時變Petri 網(wǎng)服務(wù)模型的有效性,本節(jié)通過實驗數(shù)據(jù)分析,定量說明本文方法在服務(wù)組合過程中時間表達(dá)的突出特性;最后,與包含普通Petri 網(wǎng)建模的服務(wù)組合方法對比,說明時間因素對用戶反饋評價的重要性及本文方法的可行性.

4.1 實驗條件

基于算法1 及用戶目標(biāo)需求分析,為了充分證明本文方法的可行性和有效性,采用研究團(tuán)隊開發(fā)的基于開發(fā)網(wǎng)絡(luò)環(huán)境下,松散耦合的B/S 結(jié)構(gòu)服務(wù)信息調(diào)度應(yīng)用系統(tǒng)來綜合分析模型性能.在此電廠信息調(diào)度服務(wù)平臺中,采用隨機(jī)法獲取37 640 個組件Web 服務(wù),用于構(gòu)建6 000 組電力信息組合服務(wù),其中,組件服務(wù)包含服務(wù)數(shù)據(jù)、控制邏輯及用戶評價的QoS 歷史數(shù)據(jù)等基本信息,用戶數(shù)據(jù)由電廠各部門289 名工作人員在6 個月內(nèi)使用此平臺的情況來采集.針對電廠信息調(diào)度服務(wù)平臺中電力信息的5 個基本服務(wù),通過BPEL 流程進(jìn)行調(diào)用,其中的服務(wù)執(zhí)行參數(shù)由調(diào)度費用、時間開銷、服務(wù)可用性和可靠性組成,且各參數(shù)隨時間動態(tài)變化,將電廠用戶每執(zhí)行一次服務(wù)的參數(shù)記錄下來,以TVPN 對服務(wù)參數(shù)進(jìn)行描述,由Petri 網(wǎng)結(jié)構(gòu)對各服務(wù)節(jié)點實現(xiàn)參數(shù)最優(yōu)化的選取和匹配,將服務(wù)組合轉(zhuǎn)化為節(jié)點路徑優(yōu)化問題.

基于模型流程,設(shè)置系統(tǒng)時變函數(shù)集Fδ=FIδ∪FOδ,將自然數(shù)集N={1,…,1000}視作有限時變庫所集,其每個元素對應(yīng)狀態(tài)表示個人在一段時間內(nèi)使用組合服務(wù)的次數(shù).時變函數(shù)式與組件服務(wù)的輸入/輸出功能相對應(yīng),表示服務(wù)狀態(tài)變遷觸發(fā)或外延.為了便于采集實驗數(shù)據(jù),設(shè)定1/4組件服務(wù)包含時變輸入/輸出影響,1/4只包含時變輸入影響,1/4 只包含時變輸出影響,其余不受時間變化參數(shù)影響.將服務(wù)平臺基本流程轉(zhuǎn)化為時變Petri 網(wǎng)模型,其邏輯執(zhí)行過程如圖6 所示.

Fig.6 Services workflow of the platform of power plant information based on SC-TVPN圖6 電廠信息調(diào)度服務(wù)的SC-TVPN 網(wǎng)流程

本實驗在對應(yīng)的實際系統(tǒng)中,將時變Petri 網(wǎng)的時變函數(shù)表達(dá)式與特定服務(wù)條件綜合進(jìn)行討論,設(shè)置部分組件服務(wù)的文檔為其他建模類型,用于實驗對比或測試.實驗中用到的信息調(diào)度服務(wù)平臺搭建在IBM X260 服務(wù)器上,實驗的CPU 為Dual-Core E6500@2.93GHz,內(nèi)存4GB RAM,系統(tǒng)軟件開發(fā)環(huán)境為Visual Studio 2010,數(shù)據(jù)庫采集系統(tǒng)利用SQL Server 2008 開發(fā)搭建,使用到的組件服務(wù)主要為涉及電廠工作流程的基本信息調(diào)度規(guī)程.

4.2 服務(wù)組合的有效性實驗

為了驗證本文所提時變Petri 網(wǎng)服務(wù)組合方法的可行性和有效性,根據(jù)采集的實驗數(shù)據(jù),通過設(shè)計的服務(wù)流程驗證及組合算法,由比較調(diào)用的組合服務(wù)QoS 指標(biāo)實現(xiàn),并綜合計算各方法下構(gòu)建組合服務(wù)的組合成功率TR0,可直觀得出不同方法對組合服務(wù)系統(tǒng)建模的作用及有效性比較.

表2 為不同服務(wù)組合方法下,在服務(wù)集S1與S2中獲取服務(wù)組合策略的QoS 可描述性及組合成功率的對比情況.其中,在構(gòu)建的組合服務(wù)策略集St上,先選取4 000 個組合服務(wù)作為服務(wù)測試集S1,將其余2 000 個組合服務(wù)作為服務(wù)比較集S2.對于S1和S2中的電力信息調(diào)度服務(wù),分別劃分組別,并以包含數(shù)目為10 個,20 個,50 個,100個,500 個映射規(guī)則實現(xiàn)綜合調(diào)度信息服務(wù)的組合.組合過程采用服務(wù)編碼文檔綁定及在線發(fā)布形式,功能相同的服務(wù)分別由基本工作流法(BPEL[18])、基于普通Petri 網(wǎng)(PN[13])的BPEL、模糊理論組合法(Fuzzy[19])、基于PN/TVPN 的Fuzzy、服務(wù)功能組合法(AOWSC[20])、基于PN/TVPN 的AOWSC 等組合方法實現(xiàn)建模和發(fā)布.由服務(wù)實際發(fā)布的功能可知,上述方法均能表達(dá)服務(wù)的并發(fā)異步特性,可實現(xiàn)不同功能的服務(wù)組合過程.得到的服務(wù)組合策略中,根據(jù)功能不同,服務(wù)數(shù)為10 個～1 000 個.對于用戶而言,各組合/組件服務(wù)可循環(huán)執(zhí)行且優(yōu)先調(diào)用QoS 中可用性較高的執(zhí)行.然后依據(jù)算法1 計算St1～St10這10 組服務(wù)組合策略的時間開銷屬性Ts,并計算各方法下的組合成功率TR0.

Table 2 Comparison of the composition evaluation with different services composition methods表2 不同服務(wù)組合方法的組合評價比較

在使用不同組合方法構(gòu)建組件服務(wù)并進(jìn)行組合時,不同服務(wù)數(shù)下時間開銷對QoS 影響比重V(Ts)/Ψ的計算結(jié)果.可知,使用BPEL,Fuzzy 和AOWSC 這3 種方法均可進(jìn)行服務(wù)描述,但由于時變Petri 網(wǎng)在變遷引發(fā)操作中考慮了時變參數(shù)函數(shù)作用,對QoS 時間開銷屬性具有更好的描述能力,因此比普通Petri 網(wǎng)構(gòu)建的服務(wù)組合策略具有更高的組合成功率.隨著服務(wù)數(shù)增多,系統(tǒng)檢索服務(wù)候選集的時間與服務(wù)間功能組合所存在的特定時延都會增加.通過時變Petri 網(wǎng)的時間參數(shù)表達(dá)式,將時間因數(shù)與本體服務(wù)建立關(guān)聯(lián),構(gòu)造一個與服務(wù)本身特性相關(guān)的隨機(jī)變量,并計算服務(wù)組合總時間開銷.

基于SC-TVPN 方法在不同服務(wù)組合建?？蚣芟露寄茌^好描述服務(wù)數(shù)與時間開銷的近似線性增長特性,本文采用BPEL 進(jìn)行服務(wù)組合功能邏輯和數(shù)據(jù)流描述,并結(jié)合時變Petri 網(wǎng)描述服務(wù)異步組合過程,在電廠信息調(diào)度服務(wù)數(shù)據(jù)下,得到了比Fuzzy 和AOWSC 方法更高的組合成功率.當(dāng)服務(wù)較少時,時間開銷占QoS 的比重為11.37%;隨著服務(wù)數(shù)增多,該比重趨于穩(wěn)定到45%,說明時間開銷對服務(wù)組合的質(zhì)量評價具有重要作用.同時,隨著服務(wù)數(shù)增多,用戶對服務(wù)組合策略的滿意度也有較高要求,當(dāng)用戶需求和候選集中可選擇執(zhí)行的服務(wù)輸入/輸出功能一定時,則可選擇執(zhí)行一組組合成功率高且時間開銷低的服務(wù)組合策略.因此,與已有服務(wù)組合模型相比,本文組合方法在評價時間開銷對用戶反饋服務(wù)質(zhì)量評價的影響上具有有效性.

圖7 表明,構(gòu)建同一個服務(wù)組合方案時,使用不同服務(wù)集構(gòu)建該方案的執(zhí)行時間也不同.隨著方案中服務(wù)數(shù)的增多,根據(jù)回溯算法計算服務(wù)組合方案所需的執(zhí)行時間也將增加.此外,當(dāng)一個方案服務(wù)數(shù)較少時,構(gòu)建組合方案的算法執(zhí)行時間在兩組服務(wù)集上無明顯差異;反之,方案服務(wù)數(shù)較多時,包含服務(wù)數(shù)目較少的服務(wù)集S1在執(zhí)行時間上顯然效率更高.

Fig.7 Contrast of service time consumption and efficiency for different methods on the same service set圖7 不同方法在相同服務(wù)候選集下的時間開銷及系統(tǒng)效率對比

4.3 同一服務(wù)候選集下構(gòu)建服務(wù)組合策略

第4.2 節(jié)的實驗是針對同一個服務(wù)候選集,采用不同服務(wù)建模方法進(jìn)行實驗的,目的是為了通過比較得出本文方法在描述QoS 的時間開銷屬性上具有一定優(yōu)勢,同時具有較高的組合成功率.為了進(jìn)一步說明在不同服務(wù)候選集下,本文方法同樣具備有效性和可行性,本節(jié)在同一服務(wù)候選集下進(jìn)行實驗,并比較使用不同的服務(wù)映射規(guī)則構(gòu)建不同服務(wù)組合策略St1和St2時得到的用戶滿意度來證明.表3 為設(shè)定不同服務(wù)組合策略中的服務(wù)數(shù),通過實驗獲得的100 組用戶反饋評價情況.

Table 3 Feedback of users for different service compositions on the service set表3 同一候選服務(wù)集下構(gòu)建不同服務(wù)組合方案的用戶評價

表3 反映了在時變Petri 網(wǎng)構(gòu)建的服務(wù)組合模型中,使用包含不同服務(wù)數(shù)的同一候選服務(wù)集和服務(wù)映射集合構(gòu)建不同服務(wù)組合策略的用戶反饋情況.可以看出,隨著服務(wù)候選集包含的服務(wù)數(shù)增多,使用本文所提模型建立的服務(wù)策略在用戶反饋通過數(shù)上呈降低趨勢,說明服務(wù)搜索空間越大,構(gòu)建使用戶滿意的服務(wù)策略難度越大.

圖8 為在同一個候選服務(wù)集下,用8 組服務(wù)映射規(guī)則構(gòu)建兩組不同服務(wù)數(shù)的服務(wù)組合策略,在用戶反饋通過數(shù)與組合服務(wù)時間開銷指標(biāo)的對比情況.

Fig.8 Contrast of service time consumption of different service compositions under the same amount of services圖8 相同服務(wù)候選集下的不同服務(wù)組合時間開銷

可知,服務(wù)策略包含的服務(wù)數(shù)是影響用戶反饋評價的主要因素.另外,在同一服務(wù)候選集中,構(gòu)建服務(wù)數(shù)不同的服務(wù)策略時,用戶反饋通過數(shù)相差不大,若用相對通過率來表示用戶對組合服務(wù)滿意程度的對比,則該數(shù)值可保持在1.5 以下.根據(jù)文獻(xiàn)[21]方法可知,本文建模方法是可行的.

使用本文方法進(jìn)行電廠信息調(diào)度服務(wù)應(yīng)用時,應(yīng)充分考慮使用最少服務(wù)數(shù)的服務(wù)候選集來滿足用戶的使用需求即可.當(dāng)組合方案中服務(wù)數(shù)一定時,時間開銷是影響用戶滿意度的重要參考指標(biāo).由調(diào)度平臺的實際運(yùn)行過程,使用本文所提建模方法,在宏觀上可以有效提高電廠工作人員的信息服務(wù)滿意度;同時,可以根據(jù)用戶對信息調(diào)度服務(wù)的使用偏好,我們可以進(jìn)一步調(diào)整該信息調(diào)度平臺的服務(wù)結(jié)構(gòu),通過合理的資源配置方式,將軟硬件性能與組件服務(wù)的執(zhí)行效率相結(jié)合,即可實現(xiàn)平臺的最優(yōu)利用價值.

5 總結(jié)

用戶反饋QoS 評價方法是反映系統(tǒng)提供組合服務(wù)策略是否達(dá)到用戶期望值的重要衡量指標(biāo),而服務(wù)的時間開銷特性對本文研究的電廠信息調(diào)度服務(wù)平臺具有重要參考價值,電廠系統(tǒng)以省時省力的調(diào)度信息服務(wù)規(guī)程為基準(zhǔn),因此用戶更多考慮的是如何節(jié)約服務(wù)調(diào)用的時間開銷.本文根據(jù)Web 服務(wù)具有異步并發(fā)、協(xié)同操作等特點,考慮到目前僅有較少研究針對特定服務(wù)組合的時間開銷特性,提出一種基于時變Petri 網(wǎng)的系統(tǒng)結(jié)構(gòu)用于描述服務(wù)組合建模過程.該模型面向服務(wù)組合策略計算,根據(jù)組合服務(wù)庫所回溯理論對服務(wù)策略執(zhí)行正確性檢驗,降低系統(tǒng)普遍存在的服務(wù)重用問題,能有效提高服務(wù)組合效率,使系統(tǒng)具有較高的穩(wěn)定性和組合成功率.

本文提出一種由時間Petri 網(wǎng)拓展得到的時變Petri 網(wǎng)服務(wù)組合建模方法,并在一組實際電廠信息調(diào)度服務(wù)平臺提供的Web 服務(wù)下進(jìn)行實驗分析,給出不同服務(wù)建模方法在組合成功率上的對比情況,說明該方法能夠達(dá)到較好的效果.此外,使用不同規(guī)模的服務(wù)候選集進(jìn)一步通過實驗數(shù)據(jù),說明時間開銷特性對服務(wù)組合策略的效率及用戶滿意度的影響.在日益復(fù)雜的網(wǎng)絡(luò)環(huán)境中,使用一種簡單、高效的服務(wù)組合方法是滿足企業(yè)級用戶需求的前提條件.今后,我們將研究影響服務(wù)組合質(zhì)量的其他因素對系統(tǒng)性能的影響,并考慮通過建立更高效的Petri 網(wǎng)拓展模型結(jié)構(gòu)來描述系統(tǒng)性能,為服務(wù)系統(tǒng)綜合分析做進(jìn)一步探索和研究.

作者注 本文是我們于2016 年6 月30 日投到《軟件學(xué)報》的論文.該文是大連理工大學(xué)大學(xué)韓敏(本文第一作者)老師指導(dǎo)的2017 屆(2017 年6 月)畢業(yè)的研究生孫國慶(本文第二作者)的碩士學(xué)位論文《基于時變Petri網(wǎng)的Web 服務(wù)組合研究與應(yīng)用》工作成果的一部分,特此說明.