基于Petri 網(wǎng)的服務組合模式的提?。?/h1>
2013-11-25 10:02:10葉榮華陳志娟
浙江師范大學學報(自然科學版) 2013年2期
葉榮華，陳志娟
(浙江師范大學 數(shù)理與信息工程學院，浙江 金華 321004)
0 引言
隨著Web 服務技術(shù)的發(fā)展，通過服務組合來滿足用戶需求已經(jīng)成為必然趨勢［1］.服務組合是指基于面向服務的體系結(jié)構(gòu)(SOA)，根據(jù)特定的業(yè)務目標，將多個已經(jīng)存在的服務按照其功能、語義及它們之間的邏輯關(guān)系組裝提供聚合功能的新服務的過程，是面向服務計算(SOC)泛型中實現(xiàn)資源聚合與應用集成的主要模式［2］.
服務組合按照組合生成方式的不同，可以分為靜態(tài)組合與動態(tài)組合2 種模式.靜態(tài)組合［3-4］意味著請求者應在組合計劃實施前先創(chuàng)建一個抽象的過程模型，包括任務的集合及任務間的數(shù)據(jù)依賴關(guān)系.動態(tài)組合則要實現(xiàn)自動選擇、綁定Web 服務，更重要的是自動地創(chuàng)建過程模型［5-6］.本文從靜態(tài)組合的角度研究服務組合，也就是側(cè)重于半自動方式［7-8］的實現(xiàn)，首先建立組合流程模型，然后對模型中各抽象任務自動地綁定調(diào)用實例［1］.
文獻［9］結(jié)合環(huán)境本體和Petri 網(wǎng)，實現(xiàn)對數(shù)據(jù)語義、功能語義及執(zhí)行語義的描述，將需求建模成一個類Petri 網(wǎng)，但對于其中意圖間的關(guān)系定義不夠完善;另外，只對服務是否滿足需求判定，也未給出具體的服務組合模式的內(nèi)容和其他滿足需求的服務組合模式.因此，本文在此基礎(chǔ)上展開工作，首先通過完善意圖間的互斥關(guān)系改進需求模型，接著對建模成的服務組合需求模型進行分析，重點是為求解滿足需求的所有可行的服務組合.
1 服務組合需求模型
1.1 環(huán)境本體
在基于環(huán)境本體的服務描述中，服務功能描述為服務于環(huán)境交互而引起的環(huán)境變化.環(huán)境指的是可與服務發(fā)生交互的一組環(huán)境實體的集合.環(huán)境實體可以是現(xiàn)實世界的任何實體，可以是物理的也可以是抽象的［10］.環(huán)境實體可分為3 類:自主實體、可控實體和符號實體，并通過給每一個實體加入1 個類樹層次狀態(tài)機來描述它們的動態(tài)屬性，刻畫了這些實體的狀態(tài)和相互之間的關(guān)系［11］.
定義1 環(huán)境本體(Environment Ontology，EO):定義為一個六元組{Ent，R，rel，HSM，EXCH，res}，其中:Ent 是一個環(huán)境實體的集合，一個環(huán)境實體可以表示為〈id，Attr，Rans，values〉，id 是實體的標識，Attr是實體的屬性向量，Rans 是一個屬性值的向量，values:Attr→Rans 是實體屬性向其值向量冪集的一個映射;R 是一個關(guān)系的集合;rel:r→Ent ×Ent 表示環(huán)境實體之間的關(guān)系函數(shù)，如，設(shè)a1，a2∈Ent，r∈R，則rel(r)=(a1，a2)表示a1和a2具有關(guān)系r;HSM 是層次狀態(tài)機，它是一個類樹層次狀態(tài)機的有限集合;EXCH?HSM×HSM 是HSM 之間的一種消息交換關(guān)系;res:Ent←→HSM 是環(huán)境實體與層次狀態(tài)機的一一對應關(guān)系.
1.2 意圖
在環(huán)境本體的描述下，用戶的需求可以從某一狀態(tài)到另一狀態(tài)發(fā)生改變.如果一個服務可以使一個實體從一個狀態(tài)變遷到另一狀態(tài)，那么可以說這個服務能滿足這個實體的一個意圖.接下來將給出意圖的定義，并根據(jù)它們之間的關(guān)系，定義意圖上的二元關(guān)系.
定義2 可達狀態(tài)(Reachable State):對于狀態(tài)rx，ry∈HSM，若存在一個狀態(tài)集{ri| ri∈HSM(0≤i≤n)}，使得〈rx，r1，r2，…，rn，ry〉是HSM 的一個可能的狀態(tài)變遷序列，則稱ry是rx的可達狀態(tài).
定義3 意圖(Intention):設(shè)CE 是領(lǐng)域環(huán)境本體中的一個可控環(huán)境實體集，r∈CE，則一個r 上的意圖是一個四元組(s0，st，I，O).其中:s0∈r.HSM 為初始狀態(tài);st∈r.HSM 為目標狀態(tài)，且st是s0的可達狀態(tài);I∈r.HSM 是輸入信息的有限集，它表示要實現(xiàn)意圖需提供的輸入;O∈r.HSM 是輸出信息的有限集，它是意圖效果的一部分.將一個可控實體r 上的意圖e 記作r:e，其中一個實體上可以有多個意圖，即r:(e1，e2，e3，…，en).
這里將用戶的需求看作是若干個意圖，這些意圖必須是初始狀態(tài)的可達狀態(tài)，否則意圖將沒有意義，而這些意圖之間又存在著某種關(guān)系，接下來對這些意圖進行分類.
大部分意圖的發(fā)生不會影響其他意圖的發(fā)生與否，即它們是相互獨立的.但還有一些意圖之間往往存在著某種聯(lián)系，例如對于一個“訂單”實體的“付款”意圖(即根據(jù)一些輸入訂單實體從未付款狀態(tài)轉(zhuǎn)變?yōu)橐迅犊顮顟B(tài)，并得一些輸出)與一個“信用卡”實體的“支付”意圖是相關(guān)聯(lián)的.容易看出，兩者要么同時實現(xiàn)要么都不實現(xiàn)，否則會導致不一致.
定義4 關(guān)聯(lián)意圖(Associated Intention):設(shè)CE 是領(lǐng)域環(huán)境本體中的可控實體集，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)系滿足自反性和對稱性，但不一定滿足傳遞性.例如，在旅游安排時，“飛機票”實體的“付款”意圖與“信用卡”實體的“支付”意圖是相關(guān)聯(lián)的，類似地，“火車票”實體的“付款”意圖與“信用卡”實體的“支付”意圖也是相關(guān)聯(lián)的.如果滿足傳遞性，那么“飛機票”實體的“付款”意圖與“火車票”實體的“支付”意圖也是相關(guān)聯(lián)的.事實上，在計劃旅游時，選擇了飛機就不可能再選擇火車，兩者只可能發(fā)生其中的一個.因此，意圖的關(guān)聯(lián)關(guān)系不滿足傳遞性.
定義5 將集合E 上的二元關(guān)系R 定義為E 上的相容關(guān)系［12］，并記為〈R〉，如果滿足下述條件:
1)R?E×E;2)R 滿足自反性;3)R 滿足對稱性.
由此可知，意圖集上的關(guān)聯(lián)關(guān)系滿足上述條件，從而關(guān)聯(lián)是相容的.
1.3 任務
定義6 任務(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，都沒有A(ep，em).
上述條件中，1)說明Ei是E 的一個子集;2)說明任務集合中的所有元素(意圖)都滿足二元關(guān)系A(chǔ);3)表示在意圖與任務的差集中，找不到一個意圖，與任務中的意圖滿足二元關(guān)系A(chǔ).
一般來說，在約定條件下，用示意圖更為簡潔而不致引起混淆.根據(jù)集合論中的自全相容類［12］有如下求解任務的方法:
1)圖中任一完全的多邊形的結(jié)點的集合是一個任務;
2)每一個孤立的結(jié)點也是一個任務;
3)不在完全多邊形上的任一條邊的2 個端點的集是一個任務.
例如，設(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 的任務，記為E1=t1，E2=t2，E3=t3.
如此，根據(jù)意圖的關(guān)聯(lián)關(guān)系，將意圖分為若干個子集，即為若干個任務，其中每個任務中的元素(意圖)都滿足意圖的關(guān)聯(lián)關(guān)系.此時，用戶的需求由一個龐大的意圖集劃分為若干任務組成的任務集，而每個任務可能有多個意圖，也有可能只有一個意圖.將任務看成是服務組合中的一個原子單位，每個任務必須由單個服務來完成.
1.4 服務組合需求的Petri 網(wǎng)模型
定義7 組合服務需求(Composition Service Requirement，CSR)是一個帶標識的Petri 網(wǎng)系統(tǒng)五元組(P，T;F，M0，Mt).其中:P 是一個有限的庫所集合;T 是一個有限任務的集合;F?(P ×T)∪(T ×P)是連接庫所和任務之間的有向弧集;M0是Petri 網(wǎng)的初始標志;Mt是目標標識.M0到Mt必須是可達的，表示這個需求在功能上是可實現(xiàn)的.其中Petri 網(wǎng)中的庫所容量為1，任務發(fā)生的權(quán)值為1，是一個基本網(wǎng)系統(tǒng)(Elementary Net System)［13］.
2 需求模型的組合模式求解
接下來對需求模型的可達性進行分析，它是Petri 網(wǎng)的最基本的動態(tài)性質(zhì)，其余各種性質(zhì)都要通過可達性來定義.但是，由于模型的狀態(tài)空間與系統(tǒng)的結(jié)構(gòu)大小是呈指數(shù)增長的關(guān)系，這將導致組合的激增.為限制這種激增，現(xiàn)對Petri 網(wǎng)模型進行簡化處理.
2.1 服務組合需求模型的簡化
Petri 網(wǎng)任務的發(fā)生是由令牌觸發(fā)的，當令牌從一個輸入庫所被任務轉(zhuǎn)移到輸出庫所的時間不被考慮時，就可以對Petri 網(wǎng)進行簡化.在此基礎(chǔ)上，根據(jù)Petri 網(wǎng)的特點可以確定以下庫所的吸收規(guī)則［14-15］.
圖2 原始模型
凡是只有一個輸入和輸出的中間庫所都可以被吸收，并將下一級的任務合并到上一級.圖2 和圖3 為這條吸收規(guī)則的簡單示意圖，其中Pj滿足庫所吸收的規(guī)則，被吸收后，將下一級任務合并到上一級，得到一個新的任務.
圖3 庫所吸收后的模型
定義8 線性任務(Linear Task，LT):定義為一組滿足庫所吸收規(guī)則，吸收合并后的新任務LT=〈ti，tj，…，tk〉.
經(jīng)過庫所的吸收規(guī)則對Petri 網(wǎng)進行吸收處理后，中間庫所和變遷的數(shù)量大大減少.由于對Petri 網(wǎng)中的路徑的求解過程的復雜度與中間庫所的數(shù)量是呈指數(shù)關(guān)系的，因此，對于規(guī)模較大且滿足吸收規(guī)則的系統(tǒng)模型進行吸收處理是很有意義的，節(jié)省了大量的計算量.
2.2 組合模式求解算法
對于Petri 網(wǎng)(P，T;F，M0，Mt)，有如下的任務發(fā)生規(guī)則［14］:
1)對于任務t∈T，若?p∈·t，M(p)≥1，則稱M 授權(quán)(enable)t 發(fā)生，或t 是使能的(enabled)，記作M［t〉;
2)若從M 發(fā)生t 得到的新標識為M′，則對?p∈P，有
記為M［t〉M′.其中:·t 表示任務的前件;t·表示任務的后件.
定義9 設(shè)N={P，T;F，M}是一個Petri 網(wǎng).若存在t∈T，M［t〉M′，則稱M′為從M 直接可達的;若存在任務序列t1t2…tk和標識序列M1M2M3…Mk，使得M［t1〉M1［t2〉M2…Mk-1［tk〉Mk，則稱Mk是從M可達的.從M 可達的一切標識的集合記為R(M).若記變遷序列t1t2t3…tk為σ，則可將M［t1〉M2［t2〉M2…Mk-1［tk＞Mk記為M［σ〉Mk.
服務組合需求模型是一個動態(tài)的有向圖，庫所中的令牌隨著任務的發(fā)生，從輸入庫所向輸出庫所流動，從而引起標識的變化，推動網(wǎng)系統(tǒng)的進化.接下來根據(jù)文獻［14］構(gòu)造一個以初始標識為根結(jié)，在有發(fā)生權(quán)的任務的推動下，產(chǎn)生以標識為節(jié)點的可達樹(Reachable Tree)的算法.
算法1 Petri 網(wǎng)的可達樹的構(gòu)造算法
輸入:CSR=(P，T，F(xiàn)，M0，Mt);
輸出:RT(CSR);
Step1:根據(jù)庫所吸收規(guī)則，對原模型進行簡化;
Step2:以M0作為RT(CSR)的根結(jié)點，并標之以“新”;
Step3:while 存在標注為“新”結(jié)點，Do 任選一個標注為“新”的結(jié)點，設(shè)為M;
Step4:If 從M0到M 的有向路上有一個結(jié)點的標識等于M Then 把M 的標注改為“舊”，轉(zhuǎn)入Step3;
Step5:If M=MtThen 把M 的標識改為“端點”，轉(zhuǎn)入Step3;
step6:For 每個滿足M［t〉的t∈T Do
1)計算M［t〉M′中的M′;
2)在RT(CSR)中引入一個“新”結(jié)點M′，從M 到M′畫一條有向弧，并在此弧旁邊標以t，擦去結(jié)點M 的“新”的標注，轉(zhuǎn)入Step3.
算法1 從初始標識開始，對Petri 網(wǎng)系統(tǒng)進行運行，將每次發(fā)生任務產(chǎn)生的新的標識作為子結(jié)點，直到運行到葉子結(jié)點為目標標識位置為止.文獻［15］對這個算法的可終止性給出了證明.
由算法1 得到與Petri 網(wǎng)對應的可達樹，其中葉子結(jié)點的數(shù)量就是服務組合模式的數(shù)量，每一個結(jié)點表示網(wǎng)系統(tǒng)可能出現(xiàn)的一個狀態(tài)，從一個結(jié)點到另一個結(jié)點表示，從當前狀態(tài)經(jīng)過有發(fā)生權(quán)的任務將轉(zhuǎn)化為下一個狀態(tài).通過對可達樹的深度優(yōu)先遍歷得到從初始標識到目標標識的每段弧上的任務組成的任務集，這樣的一個任務集即為需求服務組合的一個服務組合模式.
算法2 需求模型的組合模式提取算法
輸入:RT(CSR);
輸出:T
Step1:訪問RT(CSR)的根結(jié)點，并標之以“已訪問”;
Step2:while 存在標注為“已訪問”的結(jié)點Do
深度遍歷其子結(jié)點，并標之以“已訪問”，同時輸出指向子結(jié)點弧上的任務.
算法2 是一個遞歸算法，通過深度遍歷可達樹，輸出從根結(jié)點到葉子結(jié)點弧上的任務的集合.
表1 Petri 網(wǎng)模型中的任務形式表達
3 案 例
3.1 案例說明
利用上述算法，求解一個旅游安排的可行路徑集.一位旅客計劃利用一段時間去旅游，他的旅游安排如下:先到景點A，再到景點B.到景點A，可以坐飛機或者是火車，如果乘飛機，訂的飛機票要快遞到自己處，還要在景點A 附近訂個酒店.從景點A 到景點B，可以坐火車或者汽車，在景點B 附近也要訂個酒店，此處的酒店需支付押金.所有的消費由信用卡支付.
根據(jù)以上描述，可以抽象出實體上意圖及任務的具體對應關(guān)系，如表1 所示.
圖4 CSR_Travel Arrange 的Petri 網(wǎng)結(jié)構(gòu)
表1 給出了任務的含義，然后將這些任務根據(jù)邏輯構(gòu)建成旅游安排(CSR_Travel Arrange)的組合服務需求的Petri 網(wǎng)結(jié)構(gòu)，如圖4 所示.
由圖4 易知，由初始結(jié)點p1到p6的狀態(tài)變化過程完成了到達景點A 的任務，從p6到p11完成了到景點B 的任務.
3.2 服務組合模式求解過程
根據(jù)算法1 第1 步對原模型進行簡化，對模型中的庫所進行吸收處理，得到如圖5所示的需求模型.
根據(jù)簡化后的需求模型構(gòu)造可達樹的過程，如圖6 所示.
圖5 簡化后的需求模型
由可達樹的葉子結(jié)點可知，可行路徑有4 條.由算法2 可知，其中一個從根節(jié)點到葉子結(jié)點的遍歷為:(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 的所有服務組合模式為:{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 可達樹的構(gòu)建過程
4 結(jié)語
本文以環(huán)境本體作為基礎(chǔ)，結(jié)合Petri 網(wǎng)的相關(guān)理論，將服務組合需求模型建模成一個動態(tài)網(wǎng)系統(tǒng).其中定義了意圖關(guān)聯(lián)的二元關(guān)系，給出了求解任務的方法.根據(jù)庫所吸收規(guī)則，簡化了服務組合需求模型.結(jié)合模型運行過程中標識和任務的變遷情況，提出了構(gòu)造可達樹的算法.通過深度遍歷可達樹得出需求模型的所有服務組合模式.最后，用經(jīng)典案例說明了算法的實用性以及簡便性.
［1］范小芹，蔣昌俊，王俊麗，等.隨機Qos 感知的可靠Web 服務組合［J］.軟件學報，2009，20(3):546-555.
［2］黃藍會.動態(tài)服務組合的研究［J］.價值工程，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ā)榮.支持服務組合的需求模型及其可滿足性判定［J］.計算機科學與探索，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)軟件實體的功能描述及其發(fā)現(xiàn)［J］.中國科學:A 信息科學，2009，39(12):1271-1287.
［12］朱梧槚，肖奚安.集合論導論［M］.大連:大連理工大學出版社，2008.
［13］袁崇義.Petri 網(wǎng)原理與應用［M］.北京:電子工業(yè)出版社，2005.
［14］吳哲輝.Petri 網(wǎng)導論［M］.北京:機械工業(yè)出版社，2006.
［15］Peterson J L.Petri 網(wǎng)理論與系統(tǒng)理論［M］.吳哲輝，譯.徐州:中國礦業(yè)大學出版社，1989.
猜你喜歡
原始意圖、對抗主義和非解釋主義法律方法(2022年2期)2022-10-20 06:42:20 陸游詩寫意圖（國畫）福建基礎(chǔ)教育研究(2022年4期)2022-05-16 08:48:40 基于FPGA 的有色Petri 網(wǎng)仿真系統(tǒng)設(shè)計*電子器件(2021年1期)2021-03-23 09:24:02 制定法解釋與立法意圖的反事實檢驗法律方法(2021年3期)2021-03-16 05:56:58 Ladyzhenskaya流體力學方程組的確定模與確定結(jié)點個數(shù)估計數(shù)學物理學報(2018年1期)2018-03-26 08:16:42 利用Petri網(wǎng)特征結(jié)構(gòu)的故障診斷方法華僑大學學報(自然科學版)(2014年4期)2014-10-11 06:23:42 一種遞歸π演算向Petri網(wǎng)的轉(zhuǎn)換方法吉林大學學報(工學版)(2014年1期)2014-04-12 00:32:08 燕山秋意圖延河(下半月)(2014年3期)2014-02-28 21:06:46 基于Raspberry PI為結(jié)點的天氣云測量網(wǎng)絡(luò)實現(xiàn)電子設(shè)計工程(2014年12期)2014-02-27 11:58:23 基于模糊Petri網(wǎng)的數(shù)控機床主軸故障診斷*制造技術(shù)與機床(2012年3期)2012-09-26 09:31:46
葉榮華，陳志娟
(浙江師范大學 數(shù)理與信息工程學院，浙江 金華 321004)
0 引言
隨著Web 服務技術(shù)的發(fā)展，通過服務組合來滿足用戶需求已經(jīng)成為必然趨勢［1］.服務組合是指基于面向服務的體系結(jié)構(gòu)(SOA)，根據(jù)特定的業(yè)務目標，將多個已經(jīng)存在的服務按照其功能、語義及它們之間的邏輯關(guān)系組裝提供聚合功能的新服務的過程，是面向服務計算(SOC)泛型中實現(xiàn)資源聚合與應用集成的主要模式［2］.
服務組合按照組合生成方式的不同，可以分為靜態(tài)組合與動態(tài)組合2 種模式.靜態(tài)組合［3-4］意味著請求者應在組合計劃實施前先創(chuàng)建一個抽象的過程模型，包括任務的集合及任務間的數(shù)據(jù)依賴關(guān)系.動態(tài)組合則要實現(xiàn)自動選擇、綁定Web 服務，更重要的是自動地創(chuàng)建過程模型［5-6］.本文從靜態(tài)組合的角度研究服務組合，也就是側(cè)重于半自動方式［7-8］的實現(xiàn)，首先建立組合流程模型，然后對模型中各抽象任務自動地綁定調(diào)用實例［1］.
文獻［9］結(jié)合環(huán)境本體和Petri 網(wǎng)，實現(xiàn)對數(shù)據(jù)語義、功能語義及執(zhí)行語義的描述，將需求建模成一個類Petri 網(wǎng)，但對于其中意圖間的關(guān)系定義不夠完善;另外，只對服務是否滿足需求判定，也未給出具體的服務組合模式的內(nèi)容和其他滿足需求的服務組合模式.因此，本文在此基礎(chǔ)上展開工作，首先通過完善意圖間的互斥關(guān)系改進需求模型，接著對建模成的服務組合需求模型進行分析，重點是為求解滿足需求的所有可行的服務組合.
1 服務組合需求模型
1.1 環(huán)境本體
在基于環(huán)境本體的服務描述中，服務功能描述為服務于環(huán)境交互而引起的環(huán)境變化.環(huán)境指的是可與服務發(fā)生交互的一組環(huán)境實體的集合.環(huán)境實體可以是現(xiàn)實世界的任何實體，可以是物理的也可以是抽象的［10］.環(huán)境實體可分為3 類:自主實體、可控實體和符號實體，并通過給每一個實體加入1 個類樹層次狀態(tài)機來描述它們的動態(tài)屬性，刻畫了這些實體的狀態(tài)和相互之間的關(guān)系［11］.
定義1 環(huán)境本體(Environment Ontology，EO):定義為一個六元組{Ent，R，rel，HSM，EXCH，res}，其中:Ent 是一個環(huán)境實體的集合，一個環(huán)境實體可以表示為〈id，Attr，Rans，values〉，id 是實體的標識，Attr是實體的屬性向量，Rans 是一個屬性值的向量，values:Attr→Rans 是實體屬性向其值向量冪集的一個映射;R 是一個關(guān)系的集合;rel:r→Ent ×Ent 表示環(huán)境實體之間的關(guān)系函數(shù)，如，設(shè)a1，a2∈Ent，r∈R，則rel(r)=(a1，a2)表示a1和a2具有關(guān)系r;HSM 是層次狀態(tài)機，它是一個類樹層次狀態(tài)機的有限集合;EXCH?HSM×HSM 是HSM 之間的一種消息交換關(guān)系;res:Ent←→HSM 是環(huán)境實體與層次狀態(tài)機的一一對應關(guān)系.
1.2 意圖
在環(huán)境本體的描述下，用戶的需求可以從某一狀態(tài)到另一狀態(tài)發(fā)生改變.如果一個服務可以使一個實體從一個狀態(tài)變遷到另一狀態(tài)，那么可以說這個服務能滿足這個實體的一個意圖.接下來將給出意圖的定義，并根據(jù)它們之間的關(guān)系，定義意圖上的二元關(guān)系.
定義2 可達狀態(tài)(Reachable State):對于狀態(tài)rx，ry∈HSM，若存在一個狀態(tài)集{ri| ri∈HSM(0≤i≤n)}，使得〈rx，r1，r2，…，rn，ry〉是HSM 的一個可能的狀態(tài)變遷序列，則稱ry是rx的可達狀態(tài).
定義3 意圖(Intention):設(shè)CE 是領(lǐng)域環(huán)境本體中的一個可控環(huán)境實體集，r∈CE，則一個r 上的意圖是一個四元組(s0，st，I，O).其中:s0∈r.HSM 為初始狀態(tài);st∈r.HSM 為目標狀態(tài)，且st是s0的可達狀態(tài);I∈r.HSM 是輸入信息的有限集，它表示要實現(xiàn)意圖需提供的輸入;O∈r.HSM 是輸出信息的有限集，它是意圖效果的一部分.將一個可控實體r 上的意圖e 記作r:e，其中一個實體上可以有多個意圖，即r:(e1，e2，e3，…，en).
這里將用戶的需求看作是若干個意圖，這些意圖必須是初始狀態(tài)的可達狀態(tài)，否則意圖將沒有意義，而這些意圖之間又存在著某種關(guān)系，接下來對這些意圖進行分類.
大部分意圖的發(fā)生不會影響其他意圖的發(fā)生與否，即它們是相互獨立的.但還有一些意圖之間往往存在著某種聯(lián)系，例如對于一個“訂單”實體的“付款”意圖(即根據(jù)一些輸入訂單實體從未付款狀態(tài)轉(zhuǎn)變?yōu)橐迅犊顮顟B(tài)，并得一些輸出)與一個“信用卡”實體的“支付”意圖是相關(guān)聯(lián)的.容易看出，兩者要么同時實現(xiàn)要么都不實現(xiàn)，否則會導致不一致.
定義4 關(guān)聯(lián)意圖(Associated Intention):設(shè)CE 是領(lǐng)域環(huán)境本體中的可控實體集，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)系滿足自反性和對稱性，但不一定滿足傳遞性.例如，在旅游安排時，“飛機票”實體的“付款”意圖與“信用卡”實體的“支付”意圖是相關(guān)聯(lián)的，類似地，“火車票”實體的“付款”意圖與“信用卡”實體的“支付”意圖也是相關(guān)聯(lián)的.如果滿足傳遞性，那么“飛機票”實體的“付款”意圖與“火車票”實體的“支付”意圖也是相關(guān)聯(lián)的.事實上，在計劃旅游時，選擇了飛機就不可能再選擇火車，兩者只可能發(fā)生其中的一個.因此，意圖的關(guān)聯(lián)關(guān)系不滿足傳遞性.
定義5 將集合E 上的二元關(guān)系R 定義為E 上的相容關(guān)系［12］，并記為〈R〉，如果滿足下述條件:
1)R?E×E;2)R 滿足自反性;3)R 滿足對稱性.
由此可知，意圖集上的關(guān)聯(lián)關(guān)系滿足上述條件，從而關(guān)聯(lián)是相容的.
1.3 任務
定義6 任務(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，都沒有A(ep，em).
上述條件中，1)說明Ei是E 的一個子集;2)說明任務集合中的所有元素(意圖)都滿足二元關(guān)系A(chǔ);3)表示在意圖與任務的差集中，找不到一個意圖，與任務中的意圖滿足二元關(guān)系A(chǔ).
一般來說，在約定條件下，用示意圖更為簡潔而不致引起混淆.根據(jù)集合論中的自全相容類［12］有如下求解任務的方法:
1)圖中任一完全的多邊形的結(jié)點的集合是一個任務;
2)每一個孤立的結(jié)點也是一個任務;
3)不在完全多邊形上的任一條邊的2 個端點的集是一個任務.
例如，設(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 的任務，記為E1=t1，E2=t2，E3=t3.
如此，根據(jù)意圖的關(guān)聯(lián)關(guān)系，將意圖分為若干個子集，即為若干個任務，其中每個任務中的元素(意圖)都滿足意圖的關(guān)聯(lián)關(guān)系.此時，用戶的需求由一個龐大的意圖集劃分為若干任務組成的任務集，而每個任務可能有多個意圖，也有可能只有一個意圖.將任務看成是服務組合中的一個原子單位，每個任務必須由單個服務來完成.
1.4 服務組合需求的Petri 網(wǎng)模型
定義7 組合服務需求(Composition Service Requirement，CSR)是一個帶標識的Petri 網(wǎng)系統(tǒng)五元組(P，T;F，M0，Mt).其中:P 是一個有限的庫所集合;T 是一個有限任務的集合;F?(P ×T)∪(T ×P)是連接庫所和任務之間的有向弧集;M0是Petri 網(wǎng)的初始標志;Mt是目標標識.M0到Mt必須是可達的，表示這個需求在功能上是可實現(xiàn)的.其中Petri 網(wǎng)中的庫所容量為1，任務發(fā)生的權(quán)值為1，是一個基本網(wǎng)系統(tǒng)(Elementary Net System)［13］.
2 需求模型的組合模式求解
接下來對需求模型的可達性進行分析，它是Petri 網(wǎng)的最基本的動態(tài)性質(zhì)，其余各種性質(zhì)都要通過可達性來定義.但是，由于模型的狀態(tài)空間與系統(tǒng)的結(jié)構(gòu)大小是呈指數(shù)增長的關(guān)系，這將導致組合的激增.為限制這種激增，現(xiàn)對Petri 網(wǎng)模型進行簡化處理.
2.1 服務組合需求模型的簡化
Petri 網(wǎng)任務的發(fā)生是由令牌觸發(fā)的，當令牌從一個輸入庫所被任務轉(zhuǎn)移到輸出庫所的時間不被考慮時，就可以對Petri 網(wǎng)進行簡化.在此基礎(chǔ)上，根據(jù)Petri 網(wǎng)的特點可以確定以下庫所的吸收規(guī)則［14-15］.
圖2 原始模型
凡是只有一個輸入和輸出的中間庫所都可以被吸收，并將下一級的任務合并到上一級.圖2 和圖3 為這條吸收規(guī)則的簡單示意圖，其中Pj滿足庫所吸收的規(guī)則，被吸收后，將下一級任務合并到上一級，得到一個新的任務.
圖3 庫所吸收后的模型
定義8 線性任務(Linear Task，LT):定義為一組滿足庫所吸收規(guī)則，吸收合并后的新任務LT=〈ti，tj，…，tk〉.
經(jīng)過庫所的吸收規(guī)則對Petri 網(wǎng)進行吸收處理后，中間庫所和變遷的數(shù)量大大減少.由于對Petri 網(wǎng)中的路徑的求解過程的復雜度與中間庫所的數(shù)量是呈指數(shù)關(guān)系的，因此，對于規(guī)模較大且滿足吸收規(guī)則的系統(tǒng)模型進行吸收處理是很有意義的，節(jié)省了大量的計算量.
2.2 組合模式求解算法
對于Petri 網(wǎng)(P，T;F，M0，Mt)，有如下的任務發(fā)生規(guī)則［14］:
1)對于任務t∈T，若?p∈·t，M(p)≥1，則稱M 授權(quán)(enable)t 發(fā)生，或t 是使能的(enabled)，記作M［t〉;
2)若從M 發(fā)生t 得到的新標識為M′，則對?p∈P，有
記為M［t〉M′.其中:·t 表示任務的前件;t·表示任務的后件.
定義9 設(shè)N={P，T;F，M}是一個Petri 網(wǎng).若存在t∈T，M［t〉M′，則稱M′為從M 直接可達的;若存在任務序列t1t2…tk和標識序列M1M2M3…Mk，使得M［t1〉M1［t2〉M2…Mk-1［tk〉Mk，則稱Mk是從M可達的.從M 可達的一切標識的集合記為R(M).若記變遷序列t1t2t3…tk為σ，則可將M［t1〉M2［t2〉M2…Mk-1［tk＞Mk記為M［σ〉Mk.
服務組合需求模型是一個動態(tài)的有向圖，庫所中的令牌隨著任務的發(fā)生，從輸入庫所向輸出庫所流動，從而引起標識的變化，推動網(wǎng)系統(tǒng)的進化.接下來根據(jù)文獻［14］構(gòu)造一個以初始標識為根結(jié)，在有發(fā)生權(quán)的任務的推動下，產(chǎn)生以標識為節(jié)點的可達樹(Reachable Tree)的算法.
算法1 Petri 網(wǎng)的可達樹的構(gòu)造算法
輸入:CSR=(P，T，F(xiàn)，M0，Mt);
輸出:RT(CSR);
Step1:根據(jù)庫所吸收規(guī)則，對原模型進行簡化;
Step2:以M0作為RT(CSR)的根結(jié)點，并標之以“新”;
Step3:while 存在標注為“新”結(jié)點，Do 任選一個標注為“新”的結(jié)點，設(shè)為M;
Step4:If 從M0到M 的有向路上有一個結(jié)點的標識等于M Then 把M 的標注改為“舊”，轉(zhuǎn)入Step3;
Step5:If M=MtThen 把M 的標識改為“端點”，轉(zhuǎn)入Step3;
step6:For 每個滿足M［t〉的t∈T Do
1)計算M［t〉M′中的M′;
2)在RT(CSR)中引入一個“新”結(jié)點M′，從M 到M′畫一條有向弧，并在此弧旁邊標以t，擦去結(jié)點M 的“新”的標注，轉(zhuǎn)入Step3.
算法1 從初始標識開始，對Petri 網(wǎng)系統(tǒng)進行運行，將每次發(fā)生任務產(chǎn)生的新的標識作為子結(jié)點，直到運行到葉子結(jié)點為目標標識位置為止.文獻［15］對這個算法的可終止性給出了證明.
由算法1 得到與Petri 網(wǎng)對應的可達樹，其中葉子結(jié)點的數(shù)量就是服務組合模式的數(shù)量，每一個結(jié)點表示網(wǎng)系統(tǒng)可能出現(xiàn)的一個狀態(tài)，從一個結(jié)點到另一個結(jié)點表示，從當前狀態(tài)經(jīng)過有發(fā)生權(quán)的任務將轉(zhuǎn)化為下一個狀態(tài).通過對可達樹的深度優(yōu)先遍歷得到從初始標識到目標標識的每段弧上的任務組成的任務集，這樣的一個任務集即為需求服務組合的一個服務組合模式.
算法2 需求模型的組合模式提取算法
輸入:RT(CSR);
輸出:T
Step1:訪問RT(CSR)的根結(jié)點，并標之以“已訪問”;
Step2:while 存在標注為“已訪問”的結(jié)點Do
深度遍歷其子結(jié)點，并標之以“已訪問”，同時輸出指向子結(jié)點弧上的任務.
算法2 是一個遞歸算法，通過深度遍歷可達樹，輸出從根結(jié)點到葉子結(jié)點弧上的任務的集合.
表1 Petri 網(wǎng)模型中的任務形式表達
3 案 例
3.1 案例說明
利用上述算法，求解一個旅游安排的可行路徑集.一位旅客計劃利用一段時間去旅游，他的旅游安排如下:先到景點A，再到景點B.到景點A，可以坐飛機或者是火車，如果乘飛機，訂的飛機票要快遞到自己處，還要在景點A 附近訂個酒店.從景點A 到景點B，可以坐火車或者汽車，在景點B 附近也要訂個酒店，此處的酒店需支付押金.所有的消費由信用卡支付.
根據(jù)以上描述，可以抽象出實體上意圖及任務的具體對應關(guān)系，如表1 所示.
圖4 CSR_Travel Arrange 的Petri 網(wǎng)結(jié)構(gòu)
表1 給出了任務的含義，然后將這些任務根據(jù)邏輯構(gòu)建成旅游安排(CSR_Travel Arrange)的組合服務需求的Petri 網(wǎng)結(jié)構(gòu)，如圖4 所示.
由圖4 易知，由初始結(jié)點p1到p6的狀態(tài)變化過程完成了到達景點A 的任務，從p6到p11完成了到景點B 的任務.
3.2 服務組合模式求解過程
根據(jù)算法1 第1 步對原模型進行簡化，對模型中的庫所進行吸收處理，得到如圖5所示的需求模型.
根據(jù)簡化后的需求模型構(gòu)造可達樹的過程，如圖6 所示.
圖5 簡化后的需求模型
由可達樹的葉子結(jié)點可知，可行路徑有4 條.由算法2 可知，其中一個從根節(jié)點到葉子結(jié)點的遍歷為:(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 的所有服務組合模式為:{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 可達樹的構(gòu)建過程
4 結(jié)語
本文以環(huán)境本體作為基礎(chǔ)，結(jié)合Petri 網(wǎng)的相關(guān)理論，將服務組合需求模型建模成一個動態(tài)網(wǎng)系統(tǒng).其中定義了意圖關(guān)聯(lián)的二元關(guān)系，給出了求解任務的方法.根據(jù)庫所吸收規(guī)則，簡化了服務組合需求模型.結(jié)合模型運行過程中標識和任務的變遷情況，提出了構(gòu)造可達樹的算法.通過深度遍歷可達樹得出需求模型的所有服務組合模式.最后，用經(jīng)典案例說明了算法的實用性以及簡便性.
［1］范小芹，蔣昌俊，王俊麗，等.隨機Qos 感知的可靠Web 服務組合［J］.軟件學報，2009，20(3):546-555.
［2］黃藍會.動態(tài)服務組合的研究［J］.價值工程，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ā)榮.支持服務組合的需求模型及其可滿足性判定［J］.計算機科學與探索，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)軟件實體的功能描述及其發(fā)現(xiàn)［J］.中國科學:A 信息科學，2009，39(12):1271-1287.
［12］朱梧槚，肖奚安.集合論導論［M］.大連:大連理工大學出版社，2008.
［13］袁崇義.Petri 網(wǎng)原理與應用［M］.北京:電子工業(yè)出版社，2005.
［14］吳哲輝.Petri 網(wǎng)導論［M］.北京:機械工業(yè)出版社，2006.
［15］Peterson J L.Petri 網(wǎng)理論與系統(tǒng)理論［M］.吳哲輝，譯.徐州:中國礦業(yè)大學出版社，1989.
猜你喜歡
法律方法(2022年2期)2022-10-20 06:42:20
福建基礎(chǔ)教育研究(2022年4期)2022-05-16 08:48:40
電子器件(2021年1期)2021-03-23 09:24:02
法律方法(2021年3期)2021-03-16 05:56:58
數(shù)學物理學報(2018年1期)2018-03-26 08:16:42
華僑大學學報(自然科學版)(2014年4期)2014-10-11 06:23:42
吉林大學學報(工學版)(2014年1期)2014-04-12 00:32:08
延河(下半月)(2014年3期)2014-02-28 21:06:46
電子設(shè)計工程(2014年12期)2014-02-27 11:58:23
制造技術(shù)與機床(2012年3期)2012-09-26 09:31:46
