Web服務描述與組合是實現(xiàn)面向服務計算的關鍵，但目前Web服務描述研究對Web服務的實時性與智能性因素考慮不多，不適合用于分布式實時系統(tǒng)中的服務描述。該文首先定義了適合實時服務描述的實時有色Petri網(wǎng)（RTCPN）與層次實時有色Petri網(wǎng)（HRTCPN），然后建立了原子實時服務到RTCPN映射描述模型（AS-RTCPN），對服務組合運算規(guī)則進行了詳細描述與建模，最后形成了服務組合HRTCPN描述模型的簡化算法，并給出了HRTCPN的可達服務圖RSG的定義及構建算法，證明了HRTCPN模型的正確性。

【關鍵詞】Web服務 Petri網(wǎng) 形式化描述 實時服務 服務描述

1 引言

面向服務計算是實現(xiàn)跨平臺、跨語言和松藕合的最新分布式計算技術，Web服務則是面向服務計算至今最好實現(xiàn)技術。目前用Petri網(wǎng)來進行Web服務描述及組合的研究很多，文獻[1]利用模糊Petri網(wǎng)作為服務描述語言的基礎，并基于模糊Petri網(wǎng)和本體給出了一個網(wǎng)格服務發(fā)現(xiàn)的多Agent框架，使用可能性和必然性來表示對一個服務Agent能為需求Agent提供相關服務的信心程度；文獻[2]基于Petri網(wǎng)構建了服務組合網(wǎng)C-Net來分析多個Web服務之間的交互，把服務行為相容性問題分析轉化為對C-net的結構死鎖問題分析，Web服務能相容等價于在C-net圖中存在非空最小Siphons。但這些基于Petri網(wǎng)的Web服務描述研究都沒有考慮Web服務的實時性與智能性因素，不適合用于分布式實時系統(tǒng)中的服務描述，為此我們運用層次實時有色Petri網(wǎng)來構建實時服務的形式化描述模型，并采用OWL-S來表示共享領域知識來保證服務的智能性。

2 層次實時有色Petri網(wǎng)

層次實時有色Petri網(wǎng)是由含時間因素的Petri網(wǎng)[3]與有色Petri網(wǎng)[4]結合發(fā)展而來，在文獻[5]中運用了層次實時有色Petri網(wǎng)對嵌入式實時硬件電路設計進行建模與分析，并對應用在這種應用情況下的層次實時有色Petri網(wǎng)進行了定義。為了能更適合描述分布式實時系統(tǒng)中的實時服務軟件設計建模與分析，根據(jù)文獻[5]中定義的層次實時有色Petri網(wǎng)，我們重新定義了層次實時有色Petri網(wǎng)。

定義1：實時有色Petri網(wǎng)（Real-Time Coloured Petri Net，RTCPN）是一個1 3元組：RTCPN=（Ω，P，T，A，N，C，G，E，DI，DT，TS，I）。其中，Ω為是顏色的非空集合（colour set）；P為庫所的非空集合（places）；T為變遷的非空集合（transitions）；A為有向弧的集合（arcs），并且滿足表達式P∩T=P∩A=T∩A=φ；N為節(jié)點，有N：A→P×T∪T×P；C為顏色函數(shù)，定義為C：P∪T→Ω，對于p∈P，C（p）是庫所p上所有可能的托肯色之集合，對于t∈T，C（t）是變遷t上所有可能的出現(xiàn)色之集合；G是變遷的警衛(wèi)函數(shù)，指定變遷觸發(fā)必須滿足的前提條件，定義為G：T→expr（expr即表達式），有t∈T：[Type（G（t））=B∧Type（Var（G（T）））Ω]，其中B是布爾型函數(shù)，Var（.）表示變量，Type（.）表示類型（Type）；E為弧表達式函數(shù)，有E：A→expr.，有x∈A：[Type（E（a））=C（P）MS∧Type（Var（E（a）））Ω]，其中P是N（a）的庫所集元素，下標MS為多重集函數(shù)；DI為關聯(lián)變遷的實數(shù)對[tmin，tmax]的集合，tmin表示變遷最早觸發(fā)時間，tmax表示變遷最晚觸發(fā)時間；DT網(wǎng)中每個變遷執(zhí)行的持續(xù)時間，當持續(xù)時間為0時，稱之為瞬時變遷，不為0時稱之為時延變遷；TS （Time Stamp）為托肯的時間戳集合，對于t∈T，TS（t）包含了托肯到達庫所p的時間信息，托肯的時間戳信息可以通過計算表達式：TS（p）=max{TS（p）+ D（p）+DT（p）|p∈p}得出，其中D為變遷觸發(fā)的延時函數(shù)；I是初始化函數(shù)，定義為從P到一個封閉表達式I（p），滿足p∈P：[Type（I（p））=C（P）MS] 。

定義2：層次實時有色Petri網(wǎng)（Hierarchical Real-Time Coloured Petri Net，HRTCPN）是一個1 4元組HRTCPN=（Ω，P，T，A，N，C，G，E， DI，DT，TS，I，S）。其中，Ω、P、T、A、N、C、G、E、DI、DT、TS、I表示的含義與實時有色Petri網(wǎng)RTCPN中對應元組的含義一樣；S是由子層次實時有色Petri網(wǎng)（Sub—HRTCPN）和實時有色Petri網(wǎng)（RTCPN）構成的集合，S={HRTCPN} U{RTCPN}。

3 HRTCPN實時服務描述模型

目前We b服務語義描述領域最成熟的語言是OWL-S，在構建實時服務描述模型時，我們以OWL-S對Web服務語義描述元素為基礎來進行構建。OWL-S把每個服務看成是一個過程，并且將服務過程分為原子過程、簡單過程及復合過程。從服務請求者角度來看，原子過程與簡單過程都是一步就可以完成，我們在此稱這兩者為原子服務；復合過程是由其它的原子或復合過程通過一些控制構造算子來組合而成[8]，我們稱其為組合服務。故在構建實時服務的描述模型時要分兩個方面進行描述模型設計，即原子服務描述模型及組合服務描述模型。原子服務描述我們用一個定義1所定義的實時有色Petri網(wǎng)來實現(xiàn)，而對組合服務描述我們用定義2中所定義的層次實時有色Petri網(wǎng)來表達。

3.1 原子實時服務到RTCPN映射描述模型（AS-RTCPN）

原子服務可直接調用，其內部執(zhí)行過程對服務請求者不可見，故我們可以將原子服務描述為有一個輸入庫所（Pin）經(jīng)過一個服務變遷（ts）處理產(chǎn)生結果到一個輸出庫所（Pout）及一個知識庫所的實時有色Petri網(wǎng)結構。原子服務到RTCPN的映射規(guī)則：

（1）將原子服務as的執(zhí)行過程映射為一個服務變遷ts，并將ts命名為原子服務的名稱，則T={service}；

（2）原子服務的輸入狀態(tài)被映射為包含token的輸入庫所Pin；

（3）原子服務的輸入前置條件被映射成服務變遷中的警衛(wèi)函數(shù)G；

（4）原子服務的輸出狀態(tài)和執(zhí)行效果映射為包含token的輸出庫所Pout；

（5）顏色集Ω=ps∪qs，ps表示原子服務的參數(shù)集，qs表示服務用戶的QoS需求集[37]；

（6）OWS-L描述的有關原子服務的知識庫映射為知識庫所Pk，知識庫內容主要包含原子服務的質量屬性、時間屬性及執(zhí)行規(guī)則等靜態(tài)語義信息；

（7）用戶的QoS需求滿足判定映射為有向邊輸入函數(shù)E，服務變遷執(zhí)行完成后對服務狀態(tài)產(chǎn)生的影響映射為有向邊輸出果函數(shù)E；

（8）根據(jù)原子服務時間屬性，對服務變遷觸發(fā)時延DI及服務變遷執(zhí)行持續(xù)時間DT賦值；

（9）通過初始化函數(shù)I（p）對輸入庫所Pin進行初始化。

定義3：原子實時服務的實時有色Petri網(wǎng)模型是一個11元組AS-RTCPN=（Ω，P，T，F(xiàn)，C，G，E，DI，DT，TS，M0），其中：

Ω= ps∪qs，ps表示原子服務的參數(shù)集，qs表示服務用戶的QoS需求集；

P={Pin， Pout， Pk}，Pin表示原子服務的輸入，Pout表示原子服務的輸出，Pk表示原子服務的知識庫；

T={ts}，ts表示原子服務的執(zhí)行；

F={（Pin， ts），（ts， Pout），（Pk， ts），（ts，Pk）}；

C={C（Pin），C（Pout），C（Pk）}；G=G（ts）；

E={E（Pin， ts），E ts， Pout），E（Pk， ts），E（ts， Pk）}；

DI=DI（ts），表示原子服務的觸發(fā)時間區(qū)間；DT=DT（ts），表示原子服務執(zhí)行持續(xù)時間；

TS=TS（Pin），顏色Token到達輸入庫所Pin的時間戳；

M0（Pin）=C（Pin），M0（Pout）=0， M0（Pk）=C（Pk）；

AS-RTCPN模型結構圖如圖1所示。

3.2 組合實時服務HRTCPN映射描述模型（CS-HRTCPN）

組合過程用于表示具有復雜業(yè)務邏輯的服務，通常由原子服務或其他組合服務通過控制構造算子組裝而成，這就形成了組合服務的層次結構。在構建基于HRTCPN的組合實時服務描述模型時，我們需要對組合服務模型中的變遷進行分類，用于表示被調用服務的變遷稱為服務變遷，用于把服務組織成組合服務的變遷稱為控制變遷。為了便于組合服務的實時性分析，我們假設所有控制變遷均為瞬時變遷。通過對OWL-S服務組合規(guī)范中的控制構造算子研究分析，根據(jù)表達語義的不同，可將它們歸為六類服務組合運算：順序組合運算、任意次序組合運算、選擇組合運算、條件組合運算、并行組合運算及迭代組合運算。下面給出實時服務迭代組合服務用HRTCPN描述的模型結構與轉換規(guī)則。

根據(jù)OWL-S規(guī)范，實際用來進行迭代運算控制的結構包括Repeate-While及Repeate-Until。其中，它們分別通過屬性whileCondition和untilCondition指定執(zhí)行的初始、結束和維持條件，實時服務迭代組合運算符記為α。圖2（a）所示為實時服務RTS1的Repeat-Until組合運算模型結構，可以表示為αRTS1。圖中變遷分為兩種類型，其中方框中標有ts的變遷表示服務變遷；方框中標有tc的變遷表示控制變遷，用于執(zhí)行組合運算；為了清晰展示模型結構，模型結構圖中省略了時間、弧表達式、警戒函數(shù)等標識，以下類同。在執(zhí)行過程中，服務變遷ts1將產(chǎn)生一個判斷條件，根據(jù)該條件值可決定是否終止循環(huán)過程。Repeat-While的語義與此類似，區(qū)別在于控制變遷tc2和tc3的警戒函數(shù)相反。迭代組合規(guī)則為：?=?1， P= Pin∪P1∪Pout，T=T1∪{tc1， tc2， tc3 }， F=F1∪{（Pin， tc1）， （tc1， Pin1）， （tc2， Pin1）， （Pout1， tc2）， （Pout1， tc3）， （tc3， Pout） }， C=C1， E=E1∪{E（Pin， tc1）， E（tc1， Pin1）， E（tc2， Pin1）， E（Pout1， tc2）， E（Pout1， tc3），E（tc3， Pout） }， G=G1∪{G（tc1）， G（tc2）， ， G（tc3）}， DI12=DI1∪{DI（tc1）=0， DI（tc2）=0， DI（tc3）=0}， DT=DT1，TS=TS1， M0=M01∪{M0（Pin）， M0 （Pout）}。

3.3 HRTCPN實時服務描述模型有效性分析

文獻[7]針對Web服務的動態(tài)時間有色Petri網(wǎng)（DTCPN）模型給出簡化算法，但只給出了順序、條件、并行及迭代等4種服務組合模型的簡化方法，沒有給出選擇組合及任意次序組合模型的簡化方法，而且沒有考慮變遷的可觸發(fā)時間區(qū)間。根據(jù)本文中給出的定義2、定義3及各種服務組合規(guī)則，參考文獻[7]中的簡化算法，我們設計了服務組合HRTCPN描述模型的簡化算法。

算法1 服務組合HRTCPN描述模型的簡化算法

輸入：HRTCPN

輸出：簡化后的HRTCPN

（1）實時服務迭代組合HRTCPN模型簡化規(guī)則：?=?1， P={Pk1， Pin， Pout}，T={ts1}， F={（Pin， ts1），（ts1， Pout）， （ts1， Pk1）， （Pk1，ts1）}， C（Pin）=C（Pin）， C（Pout）=C（Pout）， C（Pk12）=C（Pk1）+C（Pk2）， E（Pin， ts1）=E（Pin，tc1）， E（Pk1， ts1）= E（Pk1， ts1）， E（ts1，Pout）= E（tc2，Pout）， G（ts1）=G（ts1）， DI（ts1）= DI（ts1）， DT（ts1）=αDT（ts1）， TS（Pin）=TS（Pin）， TS（Pout）=TS（Pout）， M0=（C（Pin）， C（Pk1），0）。簡化后的HRTCPN模型結構如圖2（b）所示。

（2）實時服務順序組合HRTCPN模型簡化規(guī)則：?=?12， P={Pk12， Pin12， Pout12}，T={ts12}，F(xiàn)={（Pin12，ts12），（ts12，Pout2）}，C（Pin12）=C（Pin1）+C（Pin2）， C（Pout12）=C（Pout1）+C（Pout2）， C（Pk12）=C（Pk1）+C（Pk2）， E（Pin12， ts12）= E（Pin1， ts1）+ E（Pin2， ts2）， E（Pk12， ts12）=E（Pk1，ts1）+ E（Pk2，ts2）， E（ts12，Pout12）=E（ts1，Pout1）+ E（ts2，Pout2）， G（ts12）=G（ts1）∧G（ts2）， DI（ts12）=[tmin1，tmax1+ tmax2-tmin2]， DT（ts12）=DT（ts1）+DT（ts2）， TS（Pin12）=TS（Pin1）， TS（Pout12）=TS（Pout1）， M0=（C（Pin1）+C（Pin2）， C（Pk1）+C（Pk2），0）。簡化后的HRTCPN模型結構如圖3（b）所示。

理論上通過算法1可以將一個復雜的服務組合描述HRTCPN模型簡化為一個與原子服務描述RTCPN模型結構相似的簡化模型，但這樣簡化后的模型太抽象，不利于對原服務系統(tǒng)的理解與分析，所以在實際應用此算法簡化HRTCPN模型時，我們規(guī)定組合簡化層級不能超過3層。

對組合服務HRTCPN模型簡化之后，我們就可以針對簡化模型構建可達服務圖（RSG）。文獻[8]針對網(wǎng)格服務的有色動態(tài)時延Petri網(wǎng)（CDTPN）構建了RSG，在此文獻基礎之上我們給出針對HRTCPN的可達服務圖RSG的定義及構建算法。

定義4 HRTCPN的可達服務圖RSG是一個帶標識結點與帶標識有向邊的有向圖，且RSG（HRTCPN）=（V，E，F(xiàn)T，F(xiàn)M）。其中，V={R（M0）；E={（Mi，Mj）|Mi，Mj∈R（M0）}，tk∈T：Mi[tk>Mj；FT（Mi，Mj）=tk/tsk：[tmin，tmax]，tsk表示顏色Token到達庫所tk的時間戳，[tmin，tmax]是變遷tk的可能觸發(fā)時間區(qū)間；FM（Mj）=OP，OP表示服務變遷執(zhí)行輸出結果值。

根據(jù)可達服務圖RSG的定義，我們可以設計出構建RSG的算法。

算法2 HRTCPN的可達服務圖構建

輸入：簡化后的HRTCPN

輸出：RSG（HRTCPN）

（1）令V={M0}，E={φ}，并給結點M0標記”new”標簽；

（2）如果V中不存在標記為”new”的結點，則算法結束，否則轉到步驟（3）；

（3）在V中任選一個有”new”標記的結點，設為M，再做如下處理：

（3.1）if t∈T：M[t> Then把M的標記改為”end node”；

（3.2）For 每個滿足M[t>的t∈T Do

（3.2.1）計算M[t>M中的M；

（3.2.2）If MV，then V=V+{M}，同時給M標記”new”標簽；

（3.3.3）E=E+（M，M），并給邊（M，M）標注tk/tsk：[tmin，tmax]，tsk表示顏色Token到達庫所tk的時間戳，[tmin，tmax]是變遷tk的可能觸發(fā)時間區(qū)間；

（3.3.4）If tk=sk，then 給結點M標注服務變遷執(zhí)行時間及執(zhí)行輸出結果；

（3.3.5）否則給結點M標注”[0，0]”或不標注任何標簽；

（3.3）移除結點M的”new”標簽，并返回到步驟（1）。

算法2與文獻[3]中的可覆蓋性樹構造算法原理相同，故對任何組合服務HRTCPN描述模型，算法2都是可以終止的。同時，根據(jù)HRTCPN與RSG的定義，以及服務都是按照一定的業(yè)務邏輯規(guī)則進行組合的，故很容易證明算法2是正確的，在此證明從略。

命題1[3] HRTCPN是有界的當且僅當RSG（HRTCPN）中，每個結點的標識向量中都不含有無限分量（ω）。

命題2 [8] HRTCPN是組合服務的層次結構實時有色Petri網(wǎng)描述模型，則HRTCPN是無死鎖的當且僅當M∈RSG（M0），M（Pout）≠0，p≠Pout∈P，M（p）=0。

命題3 HRTCPN無死鎖、RSG（M0）是RSG（HRTCPN）的頂點集，則組合服務系統(tǒng)的總執(zhí)行時間ET=max{∑（di+dti）}，其中∑（di+dti）是Mi的標識和，Mi是從M0到終端結點M路徑上的結點，且M0，Mi，M∈RSG（M0），di是服務變遷ti的觸發(fā)實際延遲時間，dti是服務變遷ti的執(zhí)行時間。

根據(jù)命題1、RTCPN的定義及服務組合規(guī)則，HRTCPN模型是有界的Petri網(wǎng)。同時根據(jù)RSG（HRTCPN）的構造算法及命題2可知，HRTCPN模型是無死鎖的Petri網(wǎng)。

定義5 當且僅當HRTCPN模型是有界的與無死鎖的，用HRTCPN模型描述的面向服務應用系統(tǒng)是可靠的。

4 結束語

Petri網(wǎng)非常適合描述服務的動態(tài)語議，目前用Petri網(wǎng)來進行Web服務描述及組合的研究很多，但這些基于Petri網(wǎng)的Web服務描述研究都沒有考慮Web服務的實時性與智能性因素，不適合用于分布式實時系統(tǒng)中的服務描述與組合建模。本文提出的層次實時有色Petri網(wǎng)能很好地對實時服務進行形式化描述模型，采用OWL-S表示共享領域知識來保證服務的智能性，并構建了模型的簡化算法及證明了。未來工作將構建本文提出實時服務模型在一些典型實時系統(tǒng)中的原型應用，進一步優(yōu)化模型的組合算法，更好地滿足實時性與可信性要求。

參考文獻

[1]翟正利，楊楊.基于模糊Petri網(wǎng)和本體的網(wǎng)格服務發(fā)現(xiàn)[J].北京科技大學學報，2006，12（28）：p1196-1201.

[2]PengCheng Xiong，YuShun and MenChu Zhou.A Petri Net Approach to Analysis and Composition of Web Services[J].IEEE TRANSACTIONS ON SYSTEMS，MAN，AND CYBERNETICS—PART A：SYSTEMS AND HUMANS，VOL.40，NO.2，MARCH201：p376-387.

[3]吳哲輝著.Petri網(wǎng)導論[M].機械工業(yè)出版社，2006：p215-220.

[4]袁崇義著.Petri網(wǎng)原理與應用[M].電子工業(yè)出版社，2005：p95-103.

[5]劉銘，張國印等.基于層次實時有色Petri網(wǎng)的實時系統(tǒng)建模與分析方法研究[J].電子與信息學報，2011，3（33）：p580-586.

[6]王璞巍，金芝.Web服務語義描述研究綜述[J].南京大學學報（自然科學），2005，10（41）：p462-469.

[7]Yaojun Han，Xuemei Luo.Composition and Reduction of Web Service Based on Dynamic Timed Colored Petri Nets[C]//2009 IEEE International Symposium on Parallel and Distributed Processing with Applications.p659-663.

[8]Yaojun Han，Changjun Jiang and Xuemei Luo.Modeling and Analysis for Grid Service Cooperative Scheduling Based on Petri Nets[C]//Cooperative Design， Visualization，and Engineering Lecture Notes in Computer Science Volume 4674，2007：p104-112.

作者簡介

卓國鋒（1974-），男，江西省鄱陽縣人。碩士學位。講師，研究方向為件技術、信息安全。

作者單位

成都職業(yè)技術學院軟件分院 四川省成都市 610041