基于层次实时有色Petri网的实时服务描述研究

Web服务描述与组合是实现面向服务计算的关键，但目前Web服务描述研究对Web服务的实时性与智能性因素考虑不多，不适合用于分布式实时系统中的服务描述。该文首先定义了适合实时服务描述的实时有色Petri网（RTCPN）与层次实时有色Petri网（HRTCPN），然后建立了原子实时服务到RTCPN映射描述模型（AS-RTCPN），对服务组合运算规则进行了详细描述与建模，最后形成了服务组合HRTCPN描述模型的简化算法，并给出了HRTCPN的可达服务图RSG的定义及构建算法，证明了HRTCPN模型的正确性。

【关键词】Web服务 Petri网 形式化描述 实时服务 服务描述

1 引言

面向服务计算是实现跨平台、跨语言和松藕合的最新分布式计算技术，Web服务则是面向服务计算至今最好实现技术。目前用Petri网来进行Web服务描述及组合的研究很多，文献[1]利用模糊Petri网作为服务描述语言的基础，并基于模糊Petri网和本体给出了一个网格服务发现的多Agent框架，使用可能性和必然性来表示对一个服务Agent能为需求Agent提供相关服务的信心程度；文献[2]基于Petri网构建了服务组合网C-Net来分析多个Web服务之间的交互，把服务行为相容性问题分析转化为对C-net的结构死锁问题分析，Web服务能相容等价于在C-net图中存在非空最小Siphons。但这些基于Petri网的Web服务描述研究都没有考虑Web服务的实时性与智能性因素，不适合用于分布式实时系统中的服务描述，为此我们运用层次实时有色Petri网来构建实时服务的形式化描述模型，并采用OWL-S来表示共享领域知识来保证服务的智能性。

2 层次实时有色Petri网

层次实时有色Petri网是由含时间因素的Petri网[3]与有色Petri网[4]结合发展而来，在文献[5]中運用了层次实时有色Petri网对嵌入式实时硬件电路设计进行建模与分析，并对应用在这种应用情况下的层次实时有色Petri网进行了定义。为了能更适合描述分布式实时系统中的实时服务软件设计建模与分析，根据文献[5]中定义的层次实时有色Petri网，我们重新定义了层次实时有色Petri网。

定义1：实时有色Petri网（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为节点，有N：A→P×T∪T×P；C为颜色函数，定义为C：P∪T→Ω，对于p∈P，C（p）是库所p上所有可能的托肯色之集合，对于t∈T，C（t）是变迁t上所有可能的出现色之集合；G是变迁的警卫函数，指定变迁触发必须满足的前提条件，定义为G：T→expr（expr即表达式），有t∈T：[Type（G（t））=B∧Type（Var（G（T）））Ω]，其中B是布尔型函数，Var（.）表示变量，Type（.）表示类型（Type）；E为弧表达式函数，有E：A→expr.，有x∈A：[Type（E（a））=C（P）MS∧Type（Var（E（a）））Ω]，其中P是N（a）的库所集元素，下标MS为多重集函数；DI为关联变迁的实数对[tmin，tmax]的集合，tmin表示变迁最早触发时间，tmax表示变迁最晚触发时间；DT网中每个变迁执行的持续时间，当持续时间为0时，称之为瞬时变迁，不为0时称之为时延变迁；TS （Time Stamp）为托肯的时间戳集合，对于t∈T，TS（t）包含了托肯到达库所p的时间信息，托肯的时间戳信息可以通过计算表达式：TS（p）=max{TS（p）+ D（p）+DT（p）|p∈p}得出，其中D为变迁触发的延时函数；I是初始化函数，定义为从P到一个封闭表达式I（p），满足p∈P：[Type（I（p））=C（P）MS] 。

定义2：层次实时有色Petri网（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网RTCPN中对应元组的含义一样；S是由子层次实时有色Petri网（Sub—HRTCPN）和实时有色Petri网（RTCPN）构成的集合，S={HRTCPN} U{RTCPN}。

3 HRTCPN实时服务描述模型

目前We b服务语义描述领域最成熟的语言是OWL-S，在构建实时服务描述模型时，我们以OWL-S对Web服务语义描述元素为基础来进行构建。OWL-S把每个服务看成是一个过程，并且将服务过程分为原子过程、简单过程及复合过程。从服务请求者角度来看，原子过程与简单过程都是一步就可以完成，我们在此称这两者为原子服务；复合过程是由其它的原子或复合过程通过一些控制构造算子来组合而成[8]，我们称其为组合服务。故在构建实时服务的描述模型时要分两个方面进行描述模型设计，即原子服务描述模型及组合服务描述模型。原子服务描述我们用一个定义1所定义的实时有色Petri网来实现，而对组合服务描述我们用定义2中所定义的层次实时有色Petri网来表达。

3.1 原子实时服务到RTCPN映射描述模型（AS-RTCPN）

原子服务可直接调用，其内部执行过程对服务请求者不可见，故我们可以将原子服务描述为有一个输入库所（Pin）经过一个服务变迁（ts）处理产生结果到一个输出库所（Pout）及一个知识库所的实时有色Petri网结构。原子服务到RTCPN的映射规则：

（1）将原子服务as的执行过程映射为一个服务变迁ts，并将ts命名为原子服务的名称，则T={service}；

（2）原子服务的输入状态被映射为包含token的输入库所Pin；

（3）原子服務的输入前置条件被映射成服务变迁中的警卫函数G；

（4）原子服务的输出状态和执行效果映射为包含token的输出库所Pout；

（5）颜色集Ω=ps∪qs，ps表示原子服务的参数集，qs表示服务用户的QoS需求集[37]；

（6）OWS-L描述的有关原子服务的知识库映射为知识库所Pk，知识库内容主要包含原子服务的质量属性、时间属性及执行规则等静态语义信息；

（7）用户的QoS需求满足判定映射为有向边输入函数E，服务变迁执行完成后对服务状态产生的影响映射为有向边输出果函数E；

（8）根据原子服务时间属性，对服务变迁触发时延DI及服务变迁执行持续时间DT赋值；

（9）通过初始化函数I（p）对输入库所Pin进行初始化。

定义3：原子实时服务的实时有色Petri网模型是一个11元组AS-RTCPN=（Ω，P，T，F，C，G，E，DI，DT，TS，M0），其中：

Ω= ps∪qs，ps表示原子服务的参数集，qs表示服务用户的QoS需求集；

P={Pin， Pout， Pk}，Pin表示原子服务的输入，Pout表示原子服务的输出，Pk表示原子服务的知识库；

T={ts}，ts表示原子服务的执行；

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），表示原子服务的触发时间区间；DT=DT（ts），表示原子服务执行持续时间；

TS=TS（Pin），颜色Token到达输入库所Pin的时间戳；

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

AS-RTCPN模型结构图如图1所示。

3.2 组合实时服务HRTCPN映射描述模型（CS-HRTCPN）

组合过程用于表示具有复杂业务逻辑的服务，通常由原子服务或其他组合服务通过控制构造算子组装而成，这就形成了组合服务的层次结构。在构建基于HRTCPN的组合实时服务描述模型时，我们需要对组合服务模型中的变迁进行分类，用于表示被调用服务的变迁称为服务变迁，用于把服务组织成组合服务的变迁称为控制变迁。为了便于组合服务的实时性分析，我们假设所有控制变迁均为瞬时变迁。通过对OWL-S服务组合规范中的控制构造算子研究分析，根据表达语义的不同，可将它们归为六类服务组合运算：顺序组合运算、任意次序组合运算、选择组合运算、条件组合运算、并行组合运算及迭代组合运算。下面给出实时服务迭代组合服务用HRTCPN描述的模型结构与转换规则。

根据OWL-S规范，实际用来进行迭代运算控制的结构包括Repeate-While及Repeate-Until。其中，它们分别通过属性whileCondition和untilCondition指定执行的初始、结束和维持条件，实时服务迭代组合运算符记为α。图2（a）所示为实时服务RTS1的Repeat-Until组合运算模型结构，可以表示为αRTS1。图中变迁分为两种类型，其中方框中标有ts的变迁表示服务变迁；方框中标有tc的变迁表示控制变迁，用于执行组合运算；为了清晰展示模型结构，模型结构图中省略了时间、弧表达式、警戒函数等标识，以下类同。在执行过程中，服务变迁ts1将产生一个判断条件，根据该条件值可决定是否终止循环过程。Repeat-While的语义与此类似，区别在于控制变迁tc2和tc3的警戒函数相反。迭代组合规则为：?=?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服务的动态时间有色Petri网（DTCPN）模型给出简化算法，但只给出了顺序、条件、并行及迭代等4种服务组合模型的简化方法，没有给出选择组合及任意次序组合模型的简化方法，而且没有考虑变迁的可触发时间区间。根据本文中给出的定义2、定义3及各种服务组合规则，参考文献[7]中的简化算法，我们设计了服务组合HRTCPN描述模型的简化算法。

算法1 服务组合HRTCPN描述模型的简化算法

输入：HRTCPN

输出：简化后的HRTCPN

（1）实时服务迭代组合HRTCPN模型简化规则：?=?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模型简化规则：?=?12， P={Pk12， Pin12， Pout12}，T={ts12}，F={（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模型结构相似的简化模型，但这样简化后的模型太抽象，不利于对原服务系统的理解与分析，所以在实际应用此算法简化HRTCPN模型时，我们规定组合简化层级不能超过3层。

对组合服务HRTCPN模型简化之后，我们就可以针对简化模型构建可达服务图（RSG）。文献[8]针对网格服务的有色动态时延Petri网（CDTPN）构建了RSG，在此文献基础之上我们给出针对HRTCPN的可达服务图RSG的定义及构建算法。

定义4 HRTCPN的可达服务图RSG是一个带标识结点与带标识有向边的有向图，且RSG（HRTCPN）=（V，E，FT，FM）。其中，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的可能触发时间区间；FM（Mj）=OP，OP表示服务变迁执行输出结果值。

根据可达服务图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的可能触发时间区间；

（3.3.4）If tk=sk，then 给结点M标注服务变迁执行时间及执行输出结果；

（3.3.5）否则给结点M标注”[0，0]”或不标注任何标签；

（3.3）移除结点M的”new”标签，并返回到步骤（1）。

算法2与文献[3]中的可覆盖性树构造算法原理相同，故对任何组合服务HRTCPN描述模型，算法2都是可以终止的。同时，根据HRTCPN与RSG的定义，以及服务都是按照一定的业务逻辑规则进行组合的，故很容易证明算法2是正确的，在此证明从略。

命题1[3] HRTCPN是有界的当且仅当RSG（HRTCPN）中，每个结点的标识向量中都不含有无限分量（ω）。

命题2 [8] HRTCPN是组合服务的层次结构实时有色Petri网描述模型，则HRTCPN是无死锁的当且仅当M∈RSG（M0），M（Pout）≠0，p≠Pout∈P，M（p）=0。

命题3 HRTCPN无死锁、RSG（M0）是RSG（HRTCPN）的顶点集，则组合服务系统的总执行时间ET=max{∑（di+dti）}，其中∑（di+dti）是Mi的标识和，Mi是从M0到终端结点M路径上的结点，且M0，Mi，M∈RSG（M0），di是服务变迁ti的触发实际延迟时间，dti是服务变迁ti的执行时间。

根据命题1、RTCPN的定义及服务组合规则，HRTCPN模型是有界的Petri网。同时根据RSG（HRTCPN）的构造算法及命题2可知，HRTCPN模型是无死锁的Petri网。

定义5 当且仅当HRTCPN模型是有界的与无死锁的，用HRTCPN模型描述的面向服务应用系统是可靠的。

4 结束语

Petri网非常适合描述服务的动态语议，目前用Petri网来进行Web服务描述及组合的研究很多，但这些基于Petri网的Web服务描述研究都没有考虑Web服务的实时性与智能性因素，不适合用于分布式实时系统中的服务描述与组合建模。本文提出的层次实时有色Petri网能很好地对实时服务进行形式化描述模型，采用OWL-S表示共享领域知识来保证服务的智能性，并构建了模型的简化算法及证明了。未来工作将构建本文提出实时服务模型在一些典型实时系统中的原型应用，进一步优化模型的组合算法，更好地满足实时性与可信性要求。

参考文献

[1]翟正利，杨杨.基于模糊Petri网和本体的网格服务发现[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网导论[M].机械工业出版社，2006：p215-220.

[4]袁崇义著.Petri网原理与应用[M].电子工业出版社，2005：p95-103.

[5]刘铭，张国印等.基于层次实时有色Petri网的实时系统建模与分析方法研究[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-），男，江西省鄱阳县人。硕士学位。讲师，研究方向为件技术、信息安全。

作者单位

成都职业技术学院软件分院 四川省成都市 610041