基于Petri 網(wǎng)的服務(wù)組合模式的提?。?/h1>
2013-11-25 10:02:10葉榮華陳志娟
葉榮華，陳志娟
(浙江師范大學(xué) 數(shù)理與信息工程學(xué)院，浙江 金華 321004)
0 引言
隨著Web 服務(wù)技術(shù)的發(fā)展，通過(guò)服務(wù)組合來(lái)滿足用戶需求已經(jīng)成為必然趨勢(shì)［1］.服務(wù)組合是指基于面向服務(wù)的體系結(jié)構(gòu)(SOA)，根據(jù)特定的業(yè)務(wù)目標(biāo)，將多個(gè)已經(jīng)存在的服務(wù)按照其功能、語(yǔ)義及它們之間的邏輯關(guān)系組裝提供聚合功能的新服務(wù)的過(guò)程，是面向服務(wù)計(jì)算(SOC)泛型中實(shí)現(xiàn)資源聚合與應(yīng)用集成的主要模式［2］.
服務(wù)組合按照組合生成方式的不同，可以分為靜態(tài)組合與動(dòng)態(tài)組合2 種模式.靜態(tài)組合［3-4］意味著請(qǐng)求者應(yīng)在組合計(jì)劃實(shí)施前先創(chuàng)建一個(gè)抽象的過(guò)程模型，包括任務(wù)的集合及任務(wù)間的數(shù)據(jù)依賴關(guān)系.動(dòng)態(tài)組合則要實(shí)現(xiàn)自動(dòng)選擇、綁定Web 服務(wù)，更重要的是自動(dòng)地創(chuàng)建過(guò)程模型［5-6］.本文從靜態(tài)組合的角度研究服務(wù)組合，也就是側(cè)重于半自動(dòng)方式［7-8］的實(shí)現(xiàn)，首先建立組合流程模型，然后對(duì)模型中各抽象任務(wù)自動(dòng)地綁定調(diào)用實(shí)例［1］.
文獻(xiàn)［9］結(jié)合環(huán)境本體和Petri 網(wǎng)，實(shí)現(xiàn)對(duì)數(shù)據(jù)語(yǔ)義、功能語(yǔ)義及執(zhí)行語(yǔ)義的描述，將需求建模成一個(gè)類Petri 網(wǎng)，但對(duì)于其中意圖間的關(guān)系定義不夠完善;另外，只對(duì)服務(wù)是否滿足需求判定，也未給出具體的服務(wù)組合模式的內(nèi)容和其他滿足需求的服務(wù)組合模式.因此，本文在此基礎(chǔ)上展開(kāi)工作，首先通過(guò)完善意圖間的互斥關(guān)系改進(jìn)需求模型，接著對(duì)建模成的服務(wù)組合需求模型進(jìn)行分析，重點(diǎn)是為求解滿足需求的所有可行的服務(wù)組合.
1 服務(wù)組合需求模型
1.1 環(huán)境本體
在基于環(huán)境本體的服務(wù)描述中，服務(wù)功能描述為服務(wù)于環(huán)境交互而引起的環(huán)境變化.環(huán)境指的是可與服務(wù)發(fā)生交互的一組環(huán)境實(shí)體的集合.環(huán)境實(shí)體可以是現(xiàn)實(shí)世界的任何實(shí)體，可以是物理的也可以是抽象的［10］.環(huán)境實(shí)體可分為3 類:自主實(shí)體、可控實(shí)體和符號(hào)實(shí)體，并通過(guò)給每一個(gè)實(shí)體加入1 個(gè)類樹(shù)層次狀態(tài)機(jī)來(lái)描述它們的動(dòng)態(tài)屬性，刻畫(huà)了這些實(shí)體的狀態(tài)和相互之間的關(guān)系［11］.
定義1 環(huán)境本體(Environment Ontology，EO):定義為一個(gè)六元組{Ent，R，rel，HSM，EXCH，res}，其中:Ent 是一個(gè)環(huán)境實(shí)體的集合，一個(gè)環(huán)境實(shí)體可以表示為〈id，Attr，Rans，values〉，id 是實(shí)體的標(biāo)識(shí)，Attr是實(shí)體的屬性向量，Rans 是一個(gè)屬性值的向量，values:Attr→Rans 是實(shí)體屬性向其值向量?jī)缂囊粋€(gè)映射;R 是一個(gè)關(guān)系的集合;rel:r→Ent ×Ent 表示環(huán)境實(shí)體之間的關(guān)系函數(shù)，如，設(shè)a1，a2∈Ent，r∈R，則rel(r)=(a1，a2)表示a1和a2具有關(guān)系r;HSM 是層次狀態(tài)機(jī)，它是一個(gè)類樹(shù)層次狀態(tài)機(jī)的有限集合;EXCH?HSM×HSM 是HSM 之間的一種消息交換關(guān)系;res:Ent←→HSM 是環(huán)境實(shí)體與層次狀態(tài)機(jī)的一一對(duì)應(yīng)關(guān)系.
1.2 意圖
在環(huán)境本體的描述下，用戶的需求可以從某一狀態(tài)到另一狀態(tài)發(fā)生改變.如果一個(gè)服務(wù)可以使一個(gè)實(shí)體從一個(gè)狀態(tài)變遷到另一狀態(tài)，那么可以說(shuō)這個(gè)服務(wù)能滿足這個(gè)實(shí)體的一個(gè)意圖.接下來(lái)將給出意圖的定義，并根據(jù)它們之間的關(guān)系，定義意圖上的二元關(guān)系.
定義2 可達(dá)狀態(tài)(Reachable State):對(duì)于狀態(tài)rx，ry∈HSM，若存在一個(gè)狀態(tài)集{ri| ri∈HSM(0≤i≤n)}，使得〈rx，r1，r2，…，rn，ry〉是HSM 的一個(gè)可能的狀態(tài)變遷序列，則稱ry是rx的可達(dá)狀態(tài).
定義3 意圖(Intention):設(shè)CE 是領(lǐng)域環(huán)境本體中的一個(gè)可控環(huán)境實(shí)體集，r∈CE，則一個(gè)r 上的意圖是一個(gè)四元組(s0，st，I，O).其中:s0∈r.HSM 為初始狀態(tài);st∈r.HSM 為目標(biāo)狀態(tài)，且st是s0的可達(dá)狀態(tài);I∈r.HSM 是輸入信息的有限集，它表示要實(shí)現(xiàn)意圖需提供的輸入;O∈r.HSM 是輸出信息的有限集，它是意圖效果的一部分.將一個(gè)可控實(shí)體r 上的意圖e 記作r:e，其中一個(gè)實(shí)體上可以有多個(gè)意圖，即r:(e1，e2，e3，…，en).
這里將用戶的需求看作是若干個(gè)意圖，這些意圖必須是初始狀態(tài)的可達(dá)狀態(tài)，否則意圖將沒(méi)有意義，而這些意圖之間又存在著某種關(guān)系，接下來(lái)對(duì)這些意圖進(jìn)行分類.
大部分意圖的發(fā)生不會(huì)影響其他意圖的發(fā)生與否，即它們是相互獨(dú)立的.但還有一些意圖之間往往存在著某種聯(lián)系，例如對(duì)于一個(gè)“訂單”實(shí)體的“付款”意圖(即根據(jù)一些輸入訂單實(shí)體從未付款狀態(tài)轉(zhuǎn)變?yōu)橐迅犊顮顟B(tài)，并得一些輸出)與一個(gè)“信用卡”實(shí)體的“支付”意圖是相關(guān)聯(lián)的.容易看出，兩者要么同時(shí)實(shí)現(xiàn)要么都不實(shí)現(xiàn)，否則會(huì)導(dǎo)致不一致.
定義4 關(guān)聯(lián)意圖(Associated Intention):設(shè)CE 是領(lǐng)域環(huán)境本體中的可控實(shí)體集，r1，r2∈CE.若存在r1:ei和r2:ej，使得ei，ej必須全部發(fā)生或全部不發(fā)生，則稱ei，ej是關(guān)聯(lián)意圖，記作A(r1:ei，r2:ej)或r1:eiAr2:ej.
不難看出，意圖之間的關(guān)聯(lián)關(guān)系滿足自反性和對(duì)稱性，但不一定滿足傳遞性.例如，在旅游安排時(shí)，“飛機(jī)票”實(shí)體的“付款”意圖與“信用卡”實(shí)體的“支付”意圖是相關(guān)聯(lián)的，類似地，“火車票”實(shí)體的“付款”意圖與“信用卡”實(shí)體的“支付”意圖也是相關(guān)聯(lián)的.如果滿足傳遞性，那么“飛機(jī)票”實(shí)體的“付款”意圖與“火車票”實(shí)體的“支付”意圖也是相關(guān)聯(lián)的.事實(shí)上，在計(jì)劃旅游時(shí)，選擇了飛機(jī)就不可能再選擇火車，兩者只可能發(fā)生其中的一個(gè).因此，意圖的關(guān)聯(lián)關(guān)系不滿足傳遞性.
定義5 將集合E 上的二元關(guān)系R 定義為E 上的相容關(guān)系［12］，并記為〈R〉，如果滿足下述條件:
1)R?E×E;2)R 滿足自反性;3)R 滿足對(duì)稱性.
由此可知，意圖集上的關(guān)聯(lián)關(guān)系滿足上述條件，從而關(guān)聯(lián)是相容的.
1.3 任務(wù)
定義6 任務(wù)(Task):設(shè)E 為意圖集合，有A?E×E 且〈A〉，記為ti=Ei，如果滿足下述條件:
1)Ei?E;2)?em∈Ei，?en∈Ei，都有A(em，en);3)?ep∈E-Ei，?em∈Ei，都沒(méi)有A(ep，em).
上述條件中，1)說(shuō)明Ei是E 的一個(gè)子集;2)說(shuō)明任務(wù)集合中的所有元素(意圖)都滿足二元關(guān)系A(chǔ);3)表示在意圖與任務(wù)的差集中，找不到一個(gè)意圖，與任務(wù)中的意圖滿足二元關(guān)系A(chǔ).
一般來(lái)說(shuō)，在約定條件下，用示意圖更為簡(jiǎn)潔而不致引起混淆.根據(jù)集合論中的自全相容類［12］有如下求解任務(wù)的方法:
1)圖中任一完全的多邊形的結(jié)點(diǎn)的集合是一個(gè)任務(wù);
2)每一個(gè)孤立的結(jié)點(diǎn)也是一個(gè)任務(wù);
3)不在完全多邊形上的任一條邊的2 個(gè)端點(diǎn)的集是一個(gè)任務(wù).
例如，設(shè)有意圖集E={e1，e2，e3，e4，e5}，在意圖集E 上的關(guān)聯(lián)關(guān)系A(chǔ)={(e1，e2)，(e1，e4)，(e2，e4)，(e2，e3)，(e2，e5)，(e2，e1)，(e3，e5)，(e3，e2)，(e4，e1)，(e4，e2)，(e4，e5)，(e5，e2)，(e5，e3)，(e5，e4)，(e1，e1)，(e2，e2)，(e3，e3)，(e5，e5)，(e4，e4)}.〈A〉?E×E 的關(guān)系示意圖如圖1 所示.
圖1 E 上關(guān)系R 的示意圖
由以上方法不難得出，E1={e1，e2，e4}，E2={e2，e3，e5}，E3={e2，e4，e5}都是E 的任務(wù)，記為E1=t1，E2=t2，E3=t3.
如此，根據(jù)意圖的關(guān)聯(lián)關(guān)系，將意圖分為若干個(gè)子集，即為若干個(gè)任務(wù)，其中每個(gè)任務(wù)中的元素(意圖)都滿足意圖的關(guān)聯(lián)關(guān)系.此時(shí)，用戶的需求由一個(gè)龐大的意圖集劃分為若干任務(wù)組成的任務(wù)集，而每個(gè)任務(wù)可能有多個(gè)意圖，也有可能只有一個(gè)意圖.將任務(wù)看成是服務(wù)組合中的一個(gè)原子單位，每個(gè)任務(wù)必須由單個(gè)服務(wù)來(lái)完成.
1.4 服務(wù)組合需求的Petri 網(wǎng)模型
定義7 組合服務(wù)需求(Composition Service Requirement，CSR)是一個(gè)帶標(biāo)識(shí)的Petri 網(wǎng)系統(tǒng)五元組(P，T;F，M0，Mt).其中:P 是一個(gè)有限的庫(kù)所集合;T 是一個(gè)有限任務(wù)的集合;F?(P ×T)∪(T ×P)是連接庫(kù)所和任務(wù)之間的有向弧集;M0是Petri 網(wǎng)的初始標(biāo)志;Mt是目標(biāo)標(biāo)識(shí).M0到Mt必須是可達(dá)的，表示這個(gè)需求在功能上是可實(shí)現(xiàn)的.其中Petri 網(wǎng)中的庫(kù)所容量為1，任務(wù)發(fā)生的權(quán)值為1，是一個(gè)基本網(wǎng)系統(tǒng)(Elementary Net System)［13］.
2 需求模型的組合模式求解
接下來(lái)對(duì)需求模型的可達(dá)性進(jìn)行分析，它是Petri 網(wǎng)的最基本的動(dòng)態(tài)性質(zhì)，其余各種性質(zhì)都要通過(guò)可達(dá)性來(lái)定義.但是，由于模型的狀態(tài)空間與系統(tǒng)的結(jié)構(gòu)大小是呈指數(shù)增長(zhǎng)的關(guān)系，這將導(dǎo)致組合的激增.為限制這種激增，現(xiàn)對(duì)Petri 網(wǎng)模型進(jìn)行簡(jiǎn)化處理.
2.1 服務(wù)組合需求模型的簡(jiǎn)化
Petri 網(wǎng)任務(wù)的發(fā)生是由令牌觸發(fā)的，當(dāng)令牌從一個(gè)輸入庫(kù)所被任務(wù)轉(zhuǎn)移到輸出庫(kù)所的時(shí)間不被考慮時(shí)，就可以對(duì)Petri 網(wǎng)進(jìn)行簡(jiǎn)化.在此基礎(chǔ)上，根據(jù)Petri 網(wǎng)的特點(diǎn)可以確定以下庫(kù)所的吸收規(guī)則［14-15］.
圖2 原始模型
凡是只有一個(gè)輸入和輸出的中間庫(kù)所都可以被吸收，并將下一級(jí)的任務(wù)合并到上一級(jí).圖2 和圖3 為這條吸收規(guī)則的簡(jiǎn)單示意圖，其中Pj滿足庫(kù)所吸收的規(guī)則，被吸收后，將下一級(jí)任務(wù)合并到上一級(jí)，得到一個(gè)新的任務(wù).
圖3 庫(kù)所吸收后的模型
定義8 線性任務(wù)(Linear Task，LT):定義為一組滿足庫(kù)所吸收規(guī)則，吸收合并后的新任務(wù)LT=〈ti，tj，…，tk〉.
經(jīng)過(guò)庫(kù)所的吸收規(guī)則對(duì)Petri 網(wǎng)進(jìn)行吸收處理后，中間庫(kù)所和變遷的數(shù)量大大減少.由于對(duì)Petri 網(wǎng)中的路徑的求解過(guò)程的復(fù)雜度與中間庫(kù)所的數(shù)量是呈指數(shù)關(guān)系的，因此，對(duì)于規(guī)模較大且滿足吸收規(guī)則的系統(tǒng)模型進(jìn)行吸收處理是很有意義的，節(jié)省了大量的計(jì)算量.
2.2 組合模式求解算法
對(duì)于Petri 網(wǎng)(P，T;F，M0，Mt)，有如下的任務(wù)發(fā)生規(guī)則［14］:
1)對(duì)于任務(wù)t∈T，若?p∈·t，M(p)≥1，則稱M 授權(quán)(enable)t 發(fā)生，或t 是使能的(enabled)，記作M［t〉;
2)若從M 發(fā)生t 得到的新標(biāo)識(shí)為M′，則對(duì)?p∈P，有
記為M［t〉M′.其中:·t 表示任務(wù)的前件;t·表示任務(wù)的后件.
定義9 設(shè)N={P，T;F，M}是一個(gè)Petri 網(wǎng).若存在t∈T，M［t〉M′，則稱M′為從M 直接可達(dá)的;若存在任務(wù)序列t1t2…tk和標(biāo)識(shí)序列M1M2M3…Mk，使得M［t1〉M1［t2〉M2…Mk-1［tk〉Mk，則稱Mk是從M可達(dá)的.從M 可達(dá)的一切標(biāo)識(shí)的集合記為R(M).若記變遷序列t1t2t3…tk為σ，則可將M［t1〉M2［t2〉M2…Mk-1［tk＞Mk記為M［σ〉Mk.
服務(wù)組合需求模型是一個(gè)動(dòng)態(tài)的有向圖，庫(kù)所中的令牌隨著任務(wù)的發(fā)生，從輸入庫(kù)所向輸出庫(kù)所流動(dòng)，從而引起標(biāo)識(shí)的變化，推動(dòng)網(wǎng)系統(tǒng)的進(jìn)化.接下來(lái)根據(jù)文獻(xiàn)［14］構(gòu)造一個(gè)以初始標(biāo)識(shí)為根結(jié)，在有發(fā)生權(quán)的任務(wù)的推動(dòng)下，產(chǎn)生以標(biāo)識(shí)為節(jié)點(diǎn)的可達(dá)樹(shù)(Reachable Tree)的算法.
算法1 Petri 網(wǎng)的可達(dá)樹(shù)的構(gòu)造算法
輸入:CSR=(P，T，F(xiàn)，M0，Mt);
輸出:RT(CSR);
Step1:根據(jù)庫(kù)所吸收規(guī)則，對(duì)原模型進(jìn)行簡(jiǎn)化;
Step2:以M0作為RT(CSR)的根結(jié)點(diǎn)，并標(biāo)之以“新”;
Step3:while 存在標(biāo)注為“新”結(jié)點(diǎn)，Do 任選一個(gè)標(biāo)注為“新”的結(jié)點(diǎn)，設(shè)為M;
Step4:If 從M0到M 的有向路上有一個(gè)結(jié)點(diǎn)的標(biāo)識(shí)等于M Then 把M 的標(biāo)注改為“舊”，轉(zhuǎn)入Step3;
Step5:If M=MtThen 把M 的標(biāo)識(shí)改為“端點(diǎn)”，轉(zhuǎn)入Step3;
step6:For 每個(gè)滿足M［t〉的t∈T Do
1)計(jì)算M［t〉M′中的M′;
2)在RT(CSR)中引入一個(gè)“新”結(jié)點(diǎn)M′，從M 到M′畫(huà)一條有向弧，并在此弧旁邊標(biāo)以t，擦去結(jié)點(diǎn)M 的“新”的標(biāo)注，轉(zhuǎn)入Step3.
算法1 從初始標(biāo)識(shí)開(kāi)始，對(duì)Petri 網(wǎng)系統(tǒng)進(jìn)行運(yùn)行，將每次發(fā)生任務(wù)產(chǎn)生的新的標(biāo)識(shí)作為子結(jié)點(diǎn)，直到運(yùn)行到葉子結(jié)點(diǎn)為目標(biāo)標(biāo)識(shí)位置為止.文獻(xiàn)［15］對(duì)這個(gè)算法的可終止性給出了證明.
由算法1 得到與Petri 網(wǎng)對(duì)應(yīng)的可達(dá)樹(shù)，其中葉子結(jié)點(diǎn)的數(shù)量就是服務(wù)組合模式的數(shù)量，每一個(gè)結(jié)點(diǎn)表示網(wǎng)系統(tǒng)可能出現(xiàn)的一個(gè)狀態(tài)，從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)表示，從當(dāng)前狀態(tài)經(jīng)過(guò)有發(fā)生權(quán)的任務(wù)將轉(zhuǎn)化為下一個(gè)狀態(tài).通過(guò)對(duì)可達(dá)樹(shù)的深度優(yōu)先遍歷得到從初始標(biāo)識(shí)到目標(biāo)標(biāo)識(shí)的每段弧上的任務(wù)組成的任務(wù)集，這樣的一個(gè)任務(wù)集即為需求服務(wù)組合的一個(gè)服務(wù)組合模式.
算法2 需求模型的組合模式提取算法
輸入:RT(CSR);
輸出:T
Step1:訪問(wèn)RT(CSR)的根結(jié)點(diǎn)，并標(biāo)之以“已訪問(wèn)”;
Step2:while 存在標(biāo)注為“已訪問(wèn)”的結(jié)點(diǎn)Do
深度遍歷其子結(jié)點(diǎn)，并標(biāo)之以“已訪問(wèn)”，同時(shí)輸出指向子結(jié)點(diǎn)弧上的任務(wù).
算法2 是一個(gè)遞歸算法，通過(guò)深度遍歷可達(dá)樹(shù)，輸出從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)弧上的任務(wù)的集合.
表1 Petri 網(wǎng)模型中的任務(wù)形式表達(dá)
3 案 例
3.1 案例說(shuō)明
利用上述算法，求解一個(gè)旅游安排的可行路徑集.一位旅客計(jì)劃利用一段時(shí)間去旅游，他的旅游安排如下:先到景點(diǎn)A，再到景點(diǎn)B.到景點(diǎn)A，可以坐飛機(jī)或者是火車，如果乘飛機(jī)，訂的飛機(jī)票要快遞到自己處，還要在景點(diǎn)A 附近訂個(gè)酒店.從景點(diǎn)A 到景點(diǎn)B，可以坐火車或者汽車，在景點(diǎn)B 附近也要訂個(gè)酒店，此處的酒店需支付押金.所有的消費(fèi)由信用卡支付.
根據(jù)以上描述，可以抽象出實(shí)體上意圖及任務(wù)的具體對(duì)應(yīng)關(guān)系，如表1 所示.
圖4 CSR_Travel Arrange 的Petri 網(wǎng)結(jié)構(gòu)
表1 給出了任務(wù)的含義，然后將這些任務(wù)根據(jù)邏輯構(gòu)建成旅游安排(CSR_Travel Arrange)的組合服務(wù)需求的Petri 網(wǎng)結(jié)構(gòu)，如圖4 所示.
由圖4 易知，由初始結(jié)點(diǎn)p1到p6的狀態(tài)變化過(guò)程完成了到達(dá)景點(diǎn)A 的任務(wù)，從p6到p11完成了到景點(diǎn)B 的任務(wù).
3.2 服務(wù)組合模式求解過(guò)程
根據(jù)算法1 第1 步對(duì)原模型進(jìn)行簡(jiǎn)化，對(duì)模型中的庫(kù)所進(jìn)行吸收處理，得到如圖5所示的需求模型.
根據(jù)簡(jiǎn)化后的需求模型構(gòu)造可達(dá)樹(shù)的過(guò)程，如圖6 所示.
圖5 簡(jiǎn)化后的需求模型
由可達(dá)樹(shù)的葉子結(jié)點(diǎn)可知，可行路徑有4 條.由算法2 可知，其中一個(gè)從根節(jié)點(diǎn)到葉子結(jié)點(diǎn)的遍歷為:(1，1，0，1，0)［{t1，t2，t3，t6}〉(0，0，1，1，0)［{t7，t8，t11，t12}〉(0，0，0，0，1)，即M0［{t1，t2，t3，t6，t7，t8，t11，t12}〉Mt，從而{t1，t2，t3，t6，t7，t8，t11，t12}為其中一條可行路徑.由此可得出，CSR_Travel Arrange 的所有服務(wù)組合模式為:{t1，t2，t3，t6，t7，t8，t11，t12}，{t1，t2，t3，t6，t9，t10，t11，t12}，{t4，t5，t6，t7，t8，t11，t12}，{t4，t5，t6，t9，t10，t11，t12}.
圖6 可達(dá)樹(shù)的構(gòu)建過(guò)程
4 結(jié)語(yǔ)
本文以環(huán)境本體作為基礎(chǔ)，結(jié)合Petri 網(wǎng)的相關(guān)理論，將服務(wù)組合需求模型建模成一個(gè)動(dòng)態(tài)網(wǎng)系統(tǒng).其中定義了意圖關(guān)聯(lián)的二元關(guān)系，給出了求解任務(wù)的方法.根據(jù)庫(kù)所吸收規(guī)則，簡(jiǎn)化了服務(wù)組合需求模型.結(jié)合模型運(yùn)行過(guò)程中標(biāo)識(shí)和任務(wù)的變遷情況，提出了構(gòu)造可達(dá)樹(shù)的算法.通過(guò)深度遍歷可達(dá)樹(shù)得出需求模型的所有服務(wù)組合模式.最后，用經(jīng)典案例說(shuō)明了算法的實(shí)用性以及簡(jiǎn)便性.
［1］范小芹，蔣昌俊，王俊麗，等.隨機(jī)Qos 感知的可靠Web 服務(wù)組合［J］.軟件學(xué)報(bào)，2009，20(3):546-555.
［2］黃藍(lán)會(huì).動(dòng)態(tài)服務(wù)組合的研究［J］.價(jià)值工程，2012(1):154.
［3］Patia W，Wil M P，Marlon D，et al.Analysis of Web services composition languages:the case of BPEL4WS［C］//Proceedings of the 22nd International Conference on Conceptual Modelling (ER).Chicago:Springer，2003:200-215.
［4］Orri?ns B，Yang Jian，Papazoglou M P.Model driven service composition［J］.Lecture Notes in Computer Science，2003，2910:75-90.
［5］Mediahed B，Atif Y.Context-based matching for Web service composition［J］.Distributed and Parallel Databases，2007，21(1):5-37.
［6］Medjahed B，Bouguettaya A，Elmagarmid A K.Composing Web services on the semantic Web［J］.The VLDB Journal，2003，12(4):333-351.
［7］Benamllah B，Dunlas M，Sheng Q Z，et al.Declarative composition and peer-to-peer provisioning of dynamic Web services［C］//Agrawal R，Dittrich K，Ngu A H.Proc of the 18th Int′ l Conf on Data Engineering.San Jose:IEEE Computer Society，2002:297-308.
［8］Zeng Liangzhao，Benatallah B，Dumas M.Quailty driven web service composition［C］//Ellis A，Hagino T.Proc of the world wide web.Budapest:ACM，2003:41l-421.
［9］葉榮華，金芝，鐘發(fā)榮.支持服務(wù)組合的需求模型及其可滿足性判定［J］.計(jì)算機(jī)科學(xué)與探索，2011，5(5):458-466.
［10］Liu T S，Chiou S B.The application of Petri nets to failure analysis［J］.Reliability Engineering and System Safety，1997，57(2):129-142.
［11］王璞巍，金芝，劉紅巖.網(wǎng)構(gòu)軟件實(shí)體的功能描述及其發(fā)現(xiàn)［J］.中國(guó)科學(xué):A 信息科學(xué)，2009，39(12):1271-1287.
［12］朱梧槚，肖奚安.集合論導(dǎo)論［M］.大連:大連理工大學(xué)出版社，2008.
［13］袁崇義.Petri 網(wǎng)原理與應(yīng)用［M］.北京:電子工業(yè)出版社，2005.
［14］吳哲輝.Petri 網(wǎng)導(dǎo)論［M］.北京:機(jī)械工業(yè)出版社，2006.
［15］Peterson J L.Petri 網(wǎng)理論與系統(tǒng)理論［M］.吳哲輝，譯.徐州:中國(guó)礦業(yè)大學(xué)出版社，1989.
猜你喜歡
一半模型童話王國(guó)·奇妙邏輯推理(2024年5期)2024-06-19 16:03:38 重要模型『一線三等角』中學(xué)生數(shù)理化·七年級(jí)數(shù)學(xué)人教版(2020年10期)2020-11-26 08:24:50 重尾非線性自回歸模型自加權(quán)M-估計(jì)的漸近分布數(shù)學(xué)物理學(xué)報(bào)(2020年2期)2020-06-02 11:29:24 服務(wù)在身邊 健康每一天今日農(nóng)業(yè)(2019年12期)2019-08-15 00:56:32 服務(wù)在身邊 健康每一天今日農(nóng)業(yè)(2019年10期)2019-01-04 04:28:15 服務(wù)在身邊 健康每一天今日農(nóng)業(yè)(2019年16期)2019-01-03 11:39:20 招行30年:從“滿意服務(wù)”到“感動(dòng)服務(wù)”商周刊(2017年9期)2017-08-22 02:57:56 3D打印中的模型分割與打包光學(xué)精密工程(2016年6期)2016-11-07 09:07:19 成功的定義山東青年(2016年1期)2016-02-28 14:25:25 修辭學(xué)的重大定義當(dāng)代修辭學(xué)(2014年3期)2014-01-21 02:30:44
葉榮華，陳志娟
(浙江師范大學(xué) 數(shù)理與信息工程學(xué)院，浙江 金華 321004)
0 引言
隨著Web 服務(wù)技術(shù)的發(fā)展，通過(guò)服務(wù)組合來(lái)滿足用戶需求已經(jīng)成為必然趨勢(shì)［1］.服務(wù)組合是指基于面向服務(wù)的體系結(jié)構(gòu)(SOA)，根據(jù)特定的業(yè)務(wù)目標(biāo)，將多個(gè)已經(jīng)存在的服務(wù)按照其功能、語(yǔ)義及它們之間的邏輯關(guān)系組裝提供聚合功能的新服務(wù)的過(guò)程，是面向服務(wù)計(jì)算(SOC)泛型中實(shí)現(xiàn)資源聚合與應(yīng)用集成的主要模式［2］.
服務(wù)組合按照組合生成方式的不同，可以分為靜態(tài)組合與動(dòng)態(tài)組合2 種模式.靜態(tài)組合［3-4］意味著請(qǐng)求者應(yīng)在組合計(jì)劃實(shí)施前先創(chuàng)建一個(gè)抽象的過(guò)程模型，包括任務(wù)的集合及任務(wù)間的數(shù)據(jù)依賴關(guān)系.動(dòng)態(tài)組合則要實(shí)現(xiàn)自動(dòng)選擇、綁定Web 服務(wù)，更重要的是自動(dòng)地創(chuàng)建過(guò)程模型［5-6］.本文從靜態(tài)組合的角度研究服務(wù)組合，也就是側(cè)重于半自動(dòng)方式［7-8］的實(shí)現(xiàn)，首先建立組合流程模型，然后對(duì)模型中各抽象任務(wù)自動(dòng)地綁定調(diào)用實(shí)例［1］.
文獻(xiàn)［9］結(jié)合環(huán)境本體和Petri 網(wǎng)，實(shí)現(xiàn)對(duì)數(shù)據(jù)語(yǔ)義、功能語(yǔ)義及執(zhí)行語(yǔ)義的描述，將需求建模成一個(gè)類Petri 網(wǎng)，但對(duì)于其中意圖間的關(guān)系定義不夠完善;另外，只對(duì)服務(wù)是否滿足需求判定，也未給出具體的服務(wù)組合模式的內(nèi)容和其他滿足需求的服務(wù)組合模式.因此，本文在此基礎(chǔ)上展開(kāi)工作，首先通過(guò)完善意圖間的互斥關(guān)系改進(jìn)需求模型，接著對(duì)建模成的服務(wù)組合需求模型進(jìn)行分析，重點(diǎn)是為求解滿足需求的所有可行的服務(wù)組合.
1 服務(wù)組合需求模型
1.1 環(huán)境本體
在基于環(huán)境本體的服務(wù)描述中，服務(wù)功能描述為服務(wù)于環(huán)境交互而引起的環(huán)境變化.環(huán)境指的是可與服務(wù)發(fā)生交互的一組環(huán)境實(shí)體的集合.環(huán)境實(shí)體可以是現(xiàn)實(shí)世界的任何實(shí)體，可以是物理的也可以是抽象的［10］.環(huán)境實(shí)體可分為3 類:自主實(shí)體、可控實(shí)體和符號(hào)實(shí)體，并通過(guò)給每一個(gè)實(shí)體加入1 個(gè)類樹(shù)層次狀態(tài)機(jī)來(lái)描述它們的動(dòng)態(tài)屬性，刻畫(huà)了這些實(shí)體的狀態(tài)和相互之間的關(guān)系［11］.
定義1 環(huán)境本體(Environment Ontology，EO):定義為一個(gè)六元組{Ent，R，rel，HSM，EXCH，res}，其中:Ent 是一個(gè)環(huán)境實(shí)體的集合，一個(gè)環(huán)境實(shí)體可以表示為〈id，Attr，Rans，values〉，id 是實(shí)體的標(biāo)識(shí)，Attr是實(shí)體的屬性向量，Rans 是一個(gè)屬性值的向量，values:Attr→Rans 是實(shí)體屬性向其值向量?jī)缂囊粋€(gè)映射;R 是一個(gè)關(guān)系的集合;rel:r→Ent ×Ent 表示環(huán)境實(shí)體之間的關(guān)系函數(shù)，如，設(shè)a1，a2∈Ent，r∈R，則rel(r)=(a1，a2)表示a1和a2具有關(guān)系r;HSM 是層次狀態(tài)機(jī)，它是一個(gè)類樹(shù)層次狀態(tài)機(jī)的有限集合;EXCH?HSM×HSM 是HSM 之間的一種消息交換關(guān)系;res:Ent←→HSM 是環(huán)境實(shí)體與層次狀態(tài)機(jī)的一一對(duì)應(yīng)關(guān)系.
1.2 意圖
在環(huán)境本體的描述下，用戶的需求可以從某一狀態(tài)到另一狀態(tài)發(fā)生改變.如果一個(gè)服務(wù)可以使一個(gè)實(shí)體從一個(gè)狀態(tài)變遷到另一狀態(tài)，那么可以說(shuō)這個(gè)服務(wù)能滿足這個(gè)實(shí)體的一個(gè)意圖.接下來(lái)將給出意圖的定義，并根據(jù)它們之間的關(guān)系，定義意圖上的二元關(guān)系.
定義2 可達(dá)狀態(tài)(Reachable State):對(duì)于狀態(tài)rx，ry∈HSM，若存在一個(gè)狀態(tài)集{ri| ri∈HSM(0≤i≤n)}，使得〈rx，r1，r2，…，rn，ry〉是HSM 的一個(gè)可能的狀態(tài)變遷序列，則稱ry是rx的可達(dá)狀態(tài).
定義3 意圖(Intention):設(shè)CE 是領(lǐng)域環(huán)境本體中的一個(gè)可控環(huán)境實(shí)體集，r∈CE，則一個(gè)r 上的意圖是一個(gè)四元組(s0，st，I，O).其中:s0∈r.HSM 為初始狀態(tài);st∈r.HSM 為目標(biāo)狀態(tài)，且st是s0的可達(dá)狀態(tài);I∈r.HSM 是輸入信息的有限集，它表示要實(shí)現(xiàn)意圖需提供的輸入;O∈r.HSM 是輸出信息的有限集，它是意圖效果的一部分.將一個(gè)可控實(shí)體r 上的意圖e 記作r:e，其中一個(gè)實(shí)體上可以有多個(gè)意圖，即r:(e1，e2，e3，…，en).
這里將用戶的需求看作是若干個(gè)意圖，這些意圖必須是初始狀態(tài)的可達(dá)狀態(tài)，否則意圖將沒(méi)有意義，而這些意圖之間又存在著某種關(guān)系，接下來(lái)對(duì)這些意圖進(jìn)行分類.
大部分意圖的發(fā)生不會(huì)影響其他意圖的發(fā)生與否，即它們是相互獨(dú)立的.但還有一些意圖之間往往存在著某種聯(lián)系，例如對(duì)于一個(gè)“訂單”實(shí)體的“付款”意圖(即根據(jù)一些輸入訂單實(shí)體從未付款狀態(tài)轉(zhuǎn)變?yōu)橐迅犊顮顟B(tài)，并得一些輸出)與一個(gè)“信用卡”實(shí)體的“支付”意圖是相關(guān)聯(lián)的.容易看出，兩者要么同時(shí)實(shí)現(xiàn)要么都不實(shí)現(xiàn)，否則會(huì)導(dǎo)致不一致.
定義4 關(guān)聯(lián)意圖(Associated Intention):設(shè)CE 是領(lǐng)域環(huán)境本體中的可控實(shí)體集，r1，r2∈CE.若存在r1:ei和r2:ej，使得ei，ej必須全部發(fā)生或全部不發(fā)生，則稱ei，ej是關(guān)聯(lián)意圖，記作A(r1:ei，r2:ej)或r1:eiAr2:ej.
不難看出，意圖之間的關(guān)聯(lián)關(guān)系滿足自反性和對(duì)稱性，但不一定滿足傳遞性.例如，在旅游安排時(shí)，“飛機(jī)票”實(shí)體的“付款”意圖與“信用卡”實(shí)體的“支付”意圖是相關(guān)聯(lián)的，類似地，“火車票”實(shí)體的“付款”意圖與“信用卡”實(shí)體的“支付”意圖也是相關(guān)聯(lián)的.如果滿足傳遞性，那么“飛機(jī)票”實(shí)體的“付款”意圖與“火車票”實(shí)體的“支付”意圖也是相關(guān)聯(lián)的.事實(shí)上，在計(jì)劃旅游時(shí)，選擇了飛機(jī)就不可能再選擇火車，兩者只可能發(fā)生其中的一個(gè).因此，意圖的關(guān)聯(lián)關(guān)系不滿足傳遞性.
定義5 將集合E 上的二元關(guān)系R 定義為E 上的相容關(guān)系［12］，并記為〈R〉，如果滿足下述條件:
1)R?E×E;2)R 滿足自反性;3)R 滿足對(duì)稱性.
由此可知，意圖集上的關(guān)聯(lián)關(guān)系滿足上述條件，從而關(guān)聯(lián)是相容的.
1.3 任務(wù)
定義6 任務(wù)(Task):設(shè)E 為意圖集合，有A?E×E 且〈A〉，記為ti=Ei，如果滿足下述條件:
1)Ei?E;2)?em∈Ei，?en∈Ei，都有A(em，en);3)?ep∈E-Ei，?em∈Ei，都沒(méi)有A(ep，em).
上述條件中，1)說(shuō)明Ei是E 的一個(gè)子集;2)說(shuō)明任務(wù)集合中的所有元素(意圖)都滿足二元關(guān)系A(chǔ);3)表示在意圖與任務(wù)的差集中，找不到一個(gè)意圖，與任務(wù)中的意圖滿足二元關(guān)系A(chǔ).
一般來(lái)說(shuō)，在約定條件下，用示意圖更為簡(jiǎn)潔而不致引起混淆.根據(jù)集合論中的自全相容類［12］有如下求解任務(wù)的方法:
1)圖中任一完全的多邊形的結(jié)點(diǎn)的集合是一個(gè)任務(wù);
2)每一個(gè)孤立的結(jié)點(diǎn)也是一個(gè)任務(wù);
3)不在完全多邊形上的任一條邊的2 個(gè)端點(diǎn)的集是一個(gè)任務(wù).
例如，設(shè)有意圖集E={e1，e2，e3，e4，e5}，在意圖集E 上的關(guān)聯(lián)關(guān)系A(chǔ)={(e1，e2)，(e1，e4)，(e2，e4)，(e2，e3)，(e2，e5)，(e2，e1)，(e3，e5)，(e3，e2)，(e4，e1)，(e4，e2)，(e4，e5)，(e5，e2)，(e5，e3)，(e5，e4)，(e1，e1)，(e2，e2)，(e3，e3)，(e5，e5)，(e4，e4)}.〈A〉?E×E 的關(guān)系示意圖如圖1 所示.
圖1 E 上關(guān)系R 的示意圖
由以上方法不難得出，E1={e1，e2，e4}，E2={e2，e3，e5}，E3={e2，e4，e5}都是E 的任務(wù)，記為E1=t1，E2=t2，E3=t3.
如此，根據(jù)意圖的關(guān)聯(lián)關(guān)系，將意圖分為若干個(gè)子集，即為若干個(gè)任務(wù)，其中每個(gè)任務(wù)中的元素(意圖)都滿足意圖的關(guān)聯(lián)關(guān)系.此時(shí)，用戶的需求由一個(gè)龐大的意圖集劃分為若干任務(wù)組成的任務(wù)集，而每個(gè)任務(wù)可能有多個(gè)意圖，也有可能只有一個(gè)意圖.將任務(wù)看成是服務(wù)組合中的一個(gè)原子單位，每個(gè)任務(wù)必須由單個(gè)服務(wù)來(lái)完成.
1.4 服務(wù)組合需求的Petri 網(wǎng)模型
定義7 組合服務(wù)需求(Composition Service Requirement，CSR)是一個(gè)帶標(biāo)識(shí)的Petri 網(wǎng)系統(tǒng)五元組(P，T;F，M0，Mt).其中:P 是一個(gè)有限的庫(kù)所集合;T 是一個(gè)有限任務(wù)的集合;F?(P ×T)∪(T ×P)是連接庫(kù)所和任務(wù)之間的有向弧集;M0是Petri 網(wǎng)的初始標(biāo)志;Mt是目標(biāo)標(biāo)識(shí).M0到Mt必須是可達(dá)的，表示這個(gè)需求在功能上是可實(shí)現(xiàn)的.其中Petri 網(wǎng)中的庫(kù)所容量為1，任務(wù)發(fā)生的權(quán)值為1，是一個(gè)基本網(wǎng)系統(tǒng)(Elementary Net System)［13］.
2 需求模型的組合模式求解
接下來(lái)對(duì)需求模型的可達(dá)性進(jìn)行分析，它是Petri 網(wǎng)的最基本的動(dòng)態(tài)性質(zhì)，其余各種性質(zhì)都要通過(guò)可達(dá)性來(lái)定義.但是，由于模型的狀態(tài)空間與系統(tǒng)的結(jié)構(gòu)大小是呈指數(shù)增長(zhǎng)的關(guān)系，這將導(dǎo)致組合的激增.為限制這種激增，現(xiàn)對(duì)Petri 網(wǎng)模型進(jìn)行簡(jiǎn)化處理.
2.1 服務(wù)組合需求模型的簡(jiǎn)化
Petri 網(wǎng)任務(wù)的發(fā)生是由令牌觸發(fā)的，當(dāng)令牌從一個(gè)輸入庫(kù)所被任務(wù)轉(zhuǎn)移到輸出庫(kù)所的時(shí)間不被考慮時(shí)，就可以對(duì)Petri 網(wǎng)進(jìn)行簡(jiǎn)化.在此基礎(chǔ)上，根據(jù)Petri 網(wǎng)的特點(diǎn)可以確定以下庫(kù)所的吸收規(guī)則［14-15］.
圖2 原始模型
凡是只有一個(gè)輸入和輸出的中間庫(kù)所都可以被吸收，并將下一級(jí)的任務(wù)合并到上一級(jí).圖2 和圖3 為這條吸收規(guī)則的簡(jiǎn)單示意圖，其中Pj滿足庫(kù)所吸收的規(guī)則，被吸收后，將下一級(jí)任務(wù)合并到上一級(jí)，得到一個(gè)新的任務(wù).
圖3 庫(kù)所吸收后的模型
定義8 線性任務(wù)(Linear Task，LT):定義為一組滿足庫(kù)所吸收規(guī)則，吸收合并后的新任務(wù)LT=〈ti，tj，…，tk〉.
經(jīng)過(guò)庫(kù)所的吸收規(guī)則對(duì)Petri 網(wǎng)進(jìn)行吸收處理后，中間庫(kù)所和變遷的數(shù)量大大減少.由于對(duì)Petri 網(wǎng)中的路徑的求解過(guò)程的復(fù)雜度與中間庫(kù)所的數(shù)量是呈指數(shù)關(guān)系的，因此，對(duì)于規(guī)模較大且滿足吸收規(guī)則的系統(tǒng)模型進(jìn)行吸收處理是很有意義的，節(jié)省了大量的計(jì)算量.
2.2 組合模式求解算法
對(duì)于Petri 網(wǎng)(P，T;F，M0，Mt)，有如下的任務(wù)發(fā)生規(guī)則［14］:
1)對(duì)于任務(wù)t∈T，若?p∈·t，M(p)≥1，則稱M 授權(quán)(enable)t 發(fā)生，或t 是使能的(enabled)，記作M［t〉;
2)若從M 發(fā)生t 得到的新標(biāo)識(shí)為M′，則對(duì)?p∈P，有
記為M［t〉M′.其中:·t 表示任務(wù)的前件;t·表示任務(wù)的后件.
定義9 設(shè)N={P，T;F，M}是一個(gè)Petri 網(wǎng).若存在t∈T，M［t〉M′，則稱M′為從M 直接可達(dá)的;若存在任務(wù)序列t1t2…tk和標(biāo)識(shí)序列M1M2M3…Mk，使得M［t1〉M1［t2〉M2…Mk-1［tk〉Mk，則稱Mk是從M可達(dá)的.從M 可達(dá)的一切標(biāo)識(shí)的集合記為R(M).若記變遷序列t1t2t3…tk為σ，則可將M［t1〉M2［t2〉M2…Mk-1［tk＞Mk記為M［σ〉Mk.
服務(wù)組合需求模型是一個(gè)動(dòng)態(tài)的有向圖，庫(kù)所中的令牌隨著任務(wù)的發(fā)生，從輸入庫(kù)所向輸出庫(kù)所流動(dòng)，從而引起標(biāo)識(shí)的變化，推動(dòng)網(wǎng)系統(tǒng)的進(jìn)化.接下來(lái)根據(jù)文獻(xiàn)［14］構(gòu)造一個(gè)以初始標(biāo)識(shí)為根結(jié)，在有發(fā)生權(quán)的任務(wù)的推動(dòng)下，產(chǎn)生以標(biāo)識(shí)為節(jié)點(diǎn)的可達(dá)樹(shù)(Reachable Tree)的算法.
算法1 Petri 網(wǎng)的可達(dá)樹(shù)的構(gòu)造算法
輸入:CSR=(P，T，F(xiàn)，M0，Mt);
輸出:RT(CSR);
Step1:根據(jù)庫(kù)所吸收規(guī)則，對(duì)原模型進(jìn)行簡(jiǎn)化;
Step2:以M0作為RT(CSR)的根結(jié)點(diǎn)，并標(biāo)之以“新”;
Step3:while 存在標(biāo)注為“新”結(jié)點(diǎn)，Do 任選一個(gè)標(biāo)注為“新”的結(jié)點(diǎn)，設(shè)為M;
Step4:If 從M0到M 的有向路上有一個(gè)結(jié)點(diǎn)的標(biāo)識(shí)等于M Then 把M 的標(biāo)注改為“舊”，轉(zhuǎn)入Step3;
Step5:If M=MtThen 把M 的標(biāo)識(shí)改為“端點(diǎn)”，轉(zhuǎn)入Step3;
step6:For 每個(gè)滿足M［t〉的t∈T Do
1)計(jì)算M［t〉M′中的M′;
2)在RT(CSR)中引入一個(gè)“新”結(jié)點(diǎn)M′，從M 到M′畫(huà)一條有向弧，并在此弧旁邊標(biāo)以t，擦去結(jié)點(diǎn)M 的“新”的標(biāo)注，轉(zhuǎn)入Step3.
算法1 從初始標(biāo)識(shí)開(kāi)始，對(duì)Petri 網(wǎng)系統(tǒng)進(jìn)行運(yùn)行，將每次發(fā)生任務(wù)產(chǎn)生的新的標(biāo)識(shí)作為子結(jié)點(diǎn)，直到運(yùn)行到葉子結(jié)點(diǎn)為目標(biāo)標(biāo)識(shí)位置為止.文獻(xiàn)［15］對(duì)這個(gè)算法的可終止性給出了證明.
由算法1 得到與Petri 網(wǎng)對(duì)應(yīng)的可達(dá)樹(shù)，其中葉子結(jié)點(diǎn)的數(shù)量就是服務(wù)組合模式的數(shù)量，每一個(gè)結(jié)點(diǎn)表示網(wǎng)系統(tǒng)可能出現(xiàn)的一個(gè)狀態(tài)，從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)表示，從當(dāng)前狀態(tài)經(jīng)過(guò)有發(fā)生權(quán)的任務(wù)將轉(zhuǎn)化為下一個(gè)狀態(tài).通過(guò)對(duì)可達(dá)樹(shù)的深度優(yōu)先遍歷得到從初始標(biāo)識(shí)到目標(biāo)標(biāo)識(shí)的每段弧上的任務(wù)組成的任務(wù)集，這樣的一個(gè)任務(wù)集即為需求服務(wù)組合的一個(gè)服務(wù)組合模式.
算法2 需求模型的組合模式提取算法
輸入:RT(CSR);
輸出:T
Step1:訪問(wèn)RT(CSR)的根結(jié)點(diǎn)，并標(biāo)之以“已訪問(wèn)”;
Step2:while 存在標(biāo)注為“已訪問(wèn)”的結(jié)點(diǎn)Do
深度遍歷其子結(jié)點(diǎn)，并標(biāo)之以“已訪問(wèn)”，同時(shí)輸出指向子結(jié)點(diǎn)弧上的任務(wù).
算法2 是一個(gè)遞歸算法，通過(guò)深度遍歷可達(dá)樹(shù)，輸出從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)弧上的任務(wù)的集合.
表1 Petri 網(wǎng)模型中的任務(wù)形式表達(dá)
3 案 例
3.1 案例說(shuō)明
利用上述算法，求解一個(gè)旅游安排的可行路徑集.一位旅客計(jì)劃利用一段時(shí)間去旅游，他的旅游安排如下:先到景點(diǎn)A，再到景點(diǎn)B.到景點(diǎn)A，可以坐飛機(jī)或者是火車，如果乘飛機(jī)，訂的飛機(jī)票要快遞到自己處，還要在景點(diǎn)A 附近訂個(gè)酒店.從景點(diǎn)A 到景點(diǎn)B，可以坐火車或者汽車，在景點(diǎn)B 附近也要訂個(gè)酒店，此處的酒店需支付押金.所有的消費(fèi)由信用卡支付.
根據(jù)以上描述，可以抽象出實(shí)體上意圖及任務(wù)的具體對(duì)應(yīng)關(guān)系，如表1 所示.
圖4 CSR_Travel Arrange 的Petri 網(wǎng)結(jié)構(gòu)
表1 給出了任務(wù)的含義，然后將這些任務(wù)根據(jù)邏輯構(gòu)建成旅游安排(CSR_Travel Arrange)的組合服務(wù)需求的Petri 網(wǎng)結(jié)構(gòu)，如圖4 所示.
由圖4 易知，由初始結(jié)點(diǎn)p1到p6的狀態(tài)變化過(guò)程完成了到達(dá)景點(diǎn)A 的任務(wù)，從p6到p11完成了到景點(diǎn)B 的任務(wù).
3.2 服務(wù)組合模式求解過(guò)程
根據(jù)算法1 第1 步對(duì)原模型進(jìn)行簡(jiǎn)化，對(duì)模型中的庫(kù)所進(jìn)行吸收處理，得到如圖5所示的需求模型.
根據(jù)簡(jiǎn)化后的需求模型構(gòu)造可達(dá)樹(shù)的過(guò)程，如圖6 所示.
圖5 簡(jiǎn)化后的需求模型
由可達(dá)樹(shù)的葉子結(jié)點(diǎn)可知，可行路徑有4 條.由算法2 可知，其中一個(gè)從根節(jié)點(diǎn)到葉子結(jié)點(diǎn)的遍歷為:(1，1，0，1，0)［{t1，t2，t3，t6}〉(0，0，1，1，0)［{t7，t8，t11，t12}〉(0，0，0，0，1)，即M0［{t1，t2，t3，t6，t7，t8，t11，t12}〉Mt，從而{t1，t2，t3，t6，t7，t8，t11，t12}為其中一條可行路徑.由此可得出，CSR_Travel Arrange 的所有服務(wù)組合模式為:{t1，t2，t3，t6，t7，t8，t11，t12}，{t1，t2，t3，t6，t9，t10，t11，t12}，{t4，t5，t6，t7，t8，t11，t12}，{t4，t5，t6，t9，t10，t11，t12}.
圖6 可達(dá)樹(shù)的構(gòu)建過(guò)程
4 結(jié)語(yǔ)
本文以環(huán)境本體作為基礎(chǔ)，結(jié)合Petri 網(wǎng)的相關(guān)理論，將服務(wù)組合需求模型建模成一個(gè)動(dòng)態(tài)網(wǎng)系統(tǒng).其中定義了意圖關(guān)聯(lián)的二元關(guān)系，給出了求解任務(wù)的方法.根據(jù)庫(kù)所吸收規(guī)則，簡(jiǎn)化了服務(wù)組合需求模型.結(jié)合模型運(yùn)行過(guò)程中標(biāo)識(shí)和任務(wù)的變遷情況，提出了構(gòu)造可達(dá)樹(shù)的算法.通過(guò)深度遍歷可達(dá)樹(shù)得出需求模型的所有服務(wù)組合模式.最后，用經(jīng)典案例說(shuō)明了算法的實(shí)用性以及簡(jiǎn)便性.
［1］范小芹，蔣昌俊，王俊麗，等.隨機(jī)Qos 感知的可靠Web 服務(wù)組合［J］.軟件學(xué)報(bào)，2009，20(3):546-555.
［2］黃藍(lán)會(huì).動(dòng)態(tài)服務(wù)組合的研究［J］.價(jià)值工程，2012(1):154.
［3］Patia W，Wil M P，Marlon D，et al.Analysis of Web services composition languages:the case of BPEL4WS［C］//Proceedings of the 22nd International Conference on Conceptual Modelling (ER).Chicago:Springer，2003:200-215.
［4］Orri?ns B，Yang Jian，Papazoglou M P.Model driven service composition［J］.Lecture Notes in Computer Science，2003，2910:75-90.
［5］Mediahed B，Atif Y.Context-based matching for Web service composition［J］.Distributed and Parallel Databases，2007，21(1):5-37.
［6］Medjahed B，Bouguettaya A，Elmagarmid A K.Composing Web services on the semantic Web［J］.The VLDB Journal，2003，12(4):333-351.
［7］Benamllah B，Dunlas M，Sheng Q Z，et al.Declarative composition and peer-to-peer provisioning of dynamic Web services［C］//Agrawal R，Dittrich K，Ngu A H.Proc of the 18th Int′ l Conf on Data Engineering.San Jose:IEEE Computer Society，2002:297-308.
［8］Zeng Liangzhao，Benatallah B，Dumas M.Quailty driven web service composition［C］//Ellis A，Hagino T.Proc of the world wide web.Budapest:ACM，2003:41l-421.
［9］葉榮華，金芝，鐘發(fā)榮.支持服務(wù)組合的需求模型及其可滿足性判定［J］.計(jì)算機(jī)科學(xué)與探索，2011，5(5):458-466.
［10］Liu T S，Chiou S B.The application of Petri nets to failure analysis［J］.Reliability Engineering and System Safety，1997，57(2):129-142.
［11］王璞巍，金芝，劉紅巖.網(wǎng)構(gòu)軟件實(shí)體的功能描述及其發(fā)現(xiàn)［J］.中國(guó)科學(xué):A 信息科學(xué)，2009，39(12):1271-1287.
［12］朱梧槚，肖奚安.集合論導(dǎo)論［M］.大連:大連理工大學(xué)出版社，2008.
［13］袁崇義.Petri 網(wǎng)原理與應(yīng)用［M］.北京:電子工業(yè)出版社，2005.
［14］吳哲輝.Petri 網(wǎng)導(dǎo)論［M］.北京:機(jī)械工業(yè)出版社，2006.
［15］Peterson J L.Petri 網(wǎng)理論與系統(tǒng)理論［M］.吳哲輝，譯.徐州:中國(guó)礦業(yè)大學(xué)出版社，1989.
猜你喜歡
童話王國(guó)·奇妙邏輯推理(2024年5期)2024-06-19 16:03:38
中學(xué)生數(shù)理化·七年級(jí)數(shù)學(xué)人教版(2020年10期)2020-11-26 08:24:50
數(shù)學(xué)物理學(xué)報(bào)(2020年2期)2020-06-02 11:29:24
今日農(nóng)業(yè)(2019年12期)2019-08-15 00:56:32
今日農(nóng)業(yè)(2019年10期)2019-01-04 04:28:15
今日農(nóng)業(yè)(2019年16期)2019-01-03 11:39:20
商周刊(2017年9期)2017-08-22 02:57:56
光學(xué)精密工程(2016年6期)2016-11-07 09:07:19
山東青年(2016年1期)2016-02-28 14:25:25
當(dāng)代修辭學(xué)(2014年3期)2014-01-21 02:30:44
