一种基于时变Petri 网的服务组合质量检验方法∗

韩 敏, 孙国庆, 郑丹晨, 周惠巍

(大连理工大学 电子信息与电气工程学部,辽宁 大连 116023)

随着高速互联网技术发展及用户对软件需求不断增加,Web 服务组合在网络技术研究中发挥着愈来愈重要的作用.Web 服务可以视作网络系统功能的基本单元,其遵循标准Internet 协议和SOAP 协议,并具有完全开放、松散耦合、高度可集成等特性.很多情况下,单一Web 服务难以满足用户的不同实际需求,服务组合技术的出现解决了多功能分布式Web 服务的集成问题,使其组合成结构统一、功能复杂的综合服务系统.因此,如何实现服务共享和无缝集成,使单一Web 服务动态组合起来,构成服务质量(quality of service,简称QoS)达到用户需求的服务组合策略(strategy of service composition,简称SSC),是建立网络服务体系的研究重点.

目前,国内外学者在Web 服务及其组合技术领域取得了诸多研究成果.这些成果的服务组合方法通常分为两大类:基于工作流的服务组合,如语义描述法[1]和图搜索方法[2];基于系统建模的服务组合,如数据分析法[3]和人工智能法[4−6].工作流技术可以利用服务绑定、流程设计、语义描述等对服务组合进行过程化处理,但其包含较多的人为参与,系统自动化程度和可靠性不高,服务组合效率偏低;数据分析的系统建模方法可以确保理论计算的正确性,但容易忽略实际因素的综合效应,进而导致与预期结果产生偏差;人工智能方法也可以实现Web 服务的自动组合,例如通过神经网络模型、智能优化算法等方法从各角度对系统进行分析建模和优化求解,但其对应的数据预处理和建模转化等环节难度较大,因此此类方法对用户提出了很高的要求.近些年来,随着信息量和数据量的激增,用户所需要服务的数量也愈加庞大.工作流一类的方法已然不能满足服务结构多样性的要求,而数据分析和人工智能也因为各自特点的限制导致其难以有效解决服务组合的动态搜索和自适应性等问题.

Petri 网是一种针对分布式系统的分析和建模工具,具备异步并发及图形化特性,能够充分表达系统状态变化及信息交互的行为属性.因此,国内外学者[7−10]提出利用Petri 网及其扩展方法对Web 服务组合进行系统建模.文献[7]提出了基于普通Petri 网的Web 服务组合代数计算方法,以Petri 网结构表示服务系统操作符,通过形式语义将代数组合转化为网系统描述,利用Petri 网属性和基本理论验证了服务组合规则及控制流的正确性.但普通Petri 网不能精确表达服务组合过程的消息机制、功能接口等,无法构建形式化业务流程.因此,文献[8−10]基于普通Petri 网对其概念进行拓展来表达服务组合过程:文献[8]使用时间加权以分层结构描述服务操作的功能类别,简化服务触发条件,降低了服务系统的复杂性,在一定程度上提高了系统的组合效率;文献[9]利用有色Petri 网描述服务语义,保证组件服务的语义一致性,以有色标记表示组合服务的状态变迁过程,实现多组件服务数据流和控制流的语义规范;文献[10]引入了模糊Petri 网语义描述变迁规则,以模糊命题的隶属度值表示服务系统库所标记,且信任度和阈值通过映射函数对应,优化了系统稳定性度量方法,对提高系统可靠度有一定的作用.所以Petri 网能够有效地描述Web 服务及其参数,利用语义和工作流等规则整合分布式服务,在服务筛选时能节约服务资源空间,简化服务组合流程,同时也提高了系统服务的组合效率,为用户提供了一种简便、高效的Web 服务组合思路.

Petri 网的出现,解决了网络大数据下Web 服务种类多样、参数复杂及用户多元需求服务量大的问题.但组合过程中,随着服务数增多,组合系统受时间变化的影响也将不断增大,时变因素在服务组合质量评价中不可忽略.例如,服务评价指标中的服务可用性和可靠性等参数具有随时间变化而改变的特性,传统的Petri 网建模方法忽略了这些固有参数随时间变化对服务质量的影响,已不足以表达包含时间因素影响在内的服务组合策略.同时,由于服务组合时用户事先无法对各领域中众多Web 服务进行一一筛选和调研,若服务组合时出现错误,将直接造成难以估量的人力、物力损失.因此,对服务组合过程进行流程正确性验证及系统性能分析是至关重要的.为了解决时间变化因素对服务组合建模的影响,本文提出一种包含可变时间参数的Petri 网建模方法,即时变Petri 网(time-varying Petri net,简称TVPN),通过对组合过程的时变参数描述及组合服务的流程正确性和系统性能进行分析,以实现组合策略的计算.时变Petri 网是时间Petri 网[8]的高级拓展,在求解实际工程问题[11]、任务调度领域[12]都有广泛应用,适于描述与分析组合服务过程状态变化.

本文的主要贡献包括:

(1) 提出一种基于时变Petri 网的Web 服务组合过程建模方法;

(2) 基于所提建模方法计算用户反馈评价,并以实际电厂信息调度服务平台进行系统性能分析和验证.

本文第1 节介绍Web 服务及服务组合的相关概念.第2 节给出时变Petri 网的定义和性质,提出基于时变Petri 网的服务组合方法.第3 节通过算法设计对所提建模方法进行QoS 分析验证.第4 节为仿真验证和结果分析.最后给出本文总结及工作展望.

1 服务与组合策略

Web 服务可以看作一系列网络应用组件程序的数据(data)和逻辑(logic)关系的集合,将服务S定义为三元组形式,即S=(n,Da,Lc),其中,n为服务名称,Da为服务数据流,Lc为服务逻辑流.数据和逻辑关系是构成单一服务的基本要素.

通过建立不同服务之间数据和逻辑对应关系,进而完成不同服务功能之间的组合,称为组合服务.根据Web服务业务流程执行语言BPEL4WS[13]的相关描述,服务数据可以表示为一个二元组,即Da=(Sp,QS),其中,Sp为系统参数,QS为QoS 属性参数;服务逻辑可以表示为一个三元组,即Lc=(I,O,Fl),其中,I为组件服务的输入功能集,O为相应服务可用输出功能集,Fl表示服务间工作流的映射关系集.因此,构造Web 服务组合过程对应了构建一定数量组件服务的输入/输出功能的映射关系.

定义1(映射规则).设服务S的数据流Da和逻辑流Lc已知,Lc中某一输入功能i∈I及其对应的输出功能o∈O,则单一输入i和输出o以逻辑关系l∈Lc相对应,可记作l:i→o,其描述了由服务逻辑l建立了一个由输入功能i到输出功能o的映射规则.由此可知,对于一组服务的逻辑关系,将其形式化定义为三元组形式,即fl=(im,on,ls),其中,im表示组件源服务的输入功能,on表示组件目标服务的输出功能,ls表示当前服务对应的映射关系,称为建立的服务映射规则,且fl∈Fl,,表示建立一组输入/输出功能的服务映射规则集.

定义2(服务候选集).给定若干组件服务S,根据用户需求及服务功能,可在其基础上进一步得到服务候选集WS={S1,S2,…,Sn},其对应包含的组件服务可表示为,其中,规定为服务候选集包含的全部服务名称集,Da*={∪Dak}为服务候选集包含的全部服务数据集,Lc*={∪Lck}为服务候选集中包含的全部服务逻辑及工作流关系集.因此,针对服务候选集,各组件服务所包含的全部输入/输出功能中,可结合不同需求由Fl构造数据、逻辑映射关系的各种组合,进而生成得到特定功能的可执行组合服务.

定义3(服务组合策略).已知服务候选集WS中包含n个组件服务,其中第i个服务Si作为根据用户需求设定的源组件服务,则可建立服务Si到其余最多n−1 个组件服务的映射规则,将得到组合服务集记为St,即

称Sti为建立的一个服务组合策略,St也称为服务组合策略集,其中,flij表示单一组件服务的映射规则,m是为服务组合策略的个数,1≤m≤M,M为满足用户需求的最大服务组合策略数,且M≤(n−1)!.

目前,国际上针对Web 服务组合的相关研究,通常基于结构化信息标准促进组织(OASIS[13])发布的UDDI及SOAP 消息机制.根据服务功能间的异步特性,图1 为由组件服务间的映射规则集Fl构建服务组合策略的一次组合过程,根据用户偏好,两个服务间的功能组合根据映射规则的不同而实现不同组合.每两个组件服务间完成一次组合过程都包括多组输入/输出功能的转换及数据、逻辑参数的反复调用,每生成一个服务组合策略时,都对应生成一组服务映射规则集Flk,k=1,2,…,则St对应的全部映射规则集为Fl*={∪Flk}.

例1(电厂信息调度服务平台系统):本文采用研究团队针对国内某电厂调度规程设计开发的电厂信息调度服务平台系统为研究对象,描述相关Web 服务问题及组合流程的特性验证.其具体执行过程为:首先,用户发布电力信息调度服务请求,将所需服务的逻辑功能和数据参数进行处理,并转化为组件服务操作形式;然后,系统自动筛选用户需求,按调度功能,将组件服务划分为发电信息服务(S1)或输电信息服务(S2),并通过一系列数据检索、验证和报错反馈,自动提取一组电力信息调度服务(S3)数据;再根据电厂工作人员使用该服务平台系统的反馈评价,综合分析各项服务质量数据,以保证用户方案的正确性,执行一组可调用的信息评估方案组合服务(S4);最后,筛选得到的综合评估方案,利用策略选择服务(S5)获取并发布当前最满足用户需求的信息调度服务组合策略.电厂信息调度平台的服务流程优先级可用(S1∨S2)

电厂信息调度服务平台系统能提供完备的信息调度服务流程,基本服务候选集为WS={S1,S2,S3,S4,S5},其中,各基本服务以SOAP 消息机制和UDDI 协议实现功能编码和数据流、控制流交互,通过不同建模方法实现特定功能服务的发布与绑定,建立服务逻辑和映射规则二者之间的对应关系.以发电信息服务为例,其可以用S1=(n1,Da1,Lc1)进行描述.其中,n1={发电信息}表示服务名称集;Da1=(Sp1,QS1)表示数据集合,其中Sp1={发电方式,发电量,功率,…},QS1={服务执行费用,服务时间开销};Lc1=(I1,O1,Fl1)表示逻辑集合,发电信息服务属于一类系统源组件服务,可知输入功能集I1=∅,输出功能集O1={执行调度信息服务},Fl1为映射规则集,基本控制流逻辑结构包括顺序、选择、分支并发、逻辑循环这 4 种,对应了调用下一组件服务的工作流对应关系.因此,根据此电厂信息调度服务的功能顺序分别选择不同服务执行,该服务平台共可生成个服务组合策略,即St={St1,St2,St3,St4,St5,St6,St7,St8}.

Fig.1 Mapping rules to input/output functions of component services图1 组件服务输出/输入功能的映射规则

Fig.2 Services flow of the system of information dispatching platform for power plant图2 电厂信息调度服务平台系统的服务流程

2 时变Petri 网与服务描述

2.1 Petri网及其特性

Petri 网是一类状态变迁模型,可用于描述系统中各异步成分之间的关系,允许系统并发执行各个状态的变迁.Petri 网通过无孤立点的有向二分图来描述系统结构,利用标识符反映系统状态.

定义4(有向网[13]).当且仅当三元组N=(P,T,F)满足如下条件时,称N为一个有向网.

(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建立的有向弧集合,表示有向网中的工作流关系.

定义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 网[13]).当且仅当满足下列条件时,称二元组PN=(N,M)为一个Petri 网.

(1)N=(P,T,F)是一个有向网.

(2)M:P→N+是PN的标识函数,M0为初始标识,N+为正整数集.

(3) 触发规则:

①如果∀p∈′t:M(p)≥1 时,称变迁t是使能的,表示为M[t〉.

② 如果状态标识M下t是使能的,则称t可以触发,且触发后得到的后继标识为M′,记作M[t〉M′.且有:

定义7(可达标识集[13]).若Petri 网系统PN=(N,M)中存在t∈T,使得M[t〉M′,则称M′是从M可达的.则PN中从M可达的全部标识的集合称为可达标识集,记作R(M),且满足M0∈R(M);同时,对于∀t∈T,若∃M∈R(M),则必∃M′∈R(M).

定义8(关联矩阵[13]).若Petri 网PN=(N,M)中,N=(P,T,F),P={p1,p2,…,pm},T={t1,t2,…,tm},则PN中有向网N可以表示为一个n行m列的矩阵A=[aij]n×m,当且仅当A满足下列条件时,称A为PN的关联矩阵.

定义9(迁移矩阵[13]).当且仅当矩阵K=A−diag(t1,t2,…,tn)A+满足如下条件时,称K为Petri 网PN的迁移矩阵.

(1) |ti|=1,变迁触发;

(2) |ti|=0,变迁失效.

其中,ti是PN中的变迁,i=1,2,…,n.

2.2 时变Petri网及服务描述

时变Petri 网是在包含时间因素影响的时间Petri 网基础上拓展而来的,通过描述系统中可变时间函数对综合性能和逻辑层次的变迁过程,以Petri 网有向二分图的网状结构性质,在库所中用包含时间参量的标识符函数状态记录时间变化对节点结构的影响;同时,对时间并发性以及逻辑异步特性也能够进行很好地描述.

为了便于描述可变时间函数与Petri 网中库所、变迁等基本元素关系,用符号p|δ表示库所p在时间函数表达式下对变迁触发产生的作用.令p|δ=Yt,则Yt表示库所p在时间参量影响下标识符函数状态发生变化的度量;令p|δ=Nt,则Nt表示库所p在时间参数影响下不可触发变迁,即时间参量不影响系统状态.当系统某一变迁使能时,将根据时间函数中输入功能时变因子δi和输出功能时变因子δo对功能库所的状态标识函数集,及可变时间参量进行相应记录和调整,以便于确保系统下次触发的基本条件.

对一个已知建立在普通Petri 网PN 基础上的系统,将时变Petri 网给出下面的定义形式.

定义10(时变库所).对∀p∈P,若系统中存在输入/输出功能的时变因子δ可触发其状态的变迁,即满足成立,则称该库所p为库所集p中的时变库所.

定义11(时变函数表达式).对于时变库所p∈P,记fδ为库所p在状态M下的时变函数表达式,则有:

其中,M(p)=1 表示标识符函数M满足时变库所p的时变参量影响条件,M(p)=0 表示标识符函数M不满足时变库所p的时变参量影响条件.

定义12(时变Petri 网).当且仅当满足如下条件时,五元组TVPN=(P,T,F,M,)称为一个时变Petri 网.

(1)p是一个库所集合,其中包含的全部时变库所构成的集合是p的一个子集;

(2)T是一个变迁集合,满足P∪T≠∅;且对于∀t∈T的前置集′t和后置集t′,满足′t∩t′=∅;同时,变迁t的触发,与所对应的时变库所时变函数表达式fδ有关,并对应引导标识符函数的变化;

(3)F⊆{(P×T)∪(T×P)}表示一个包含时间因素的有向弧集合;

(4)M表示TVPN 中状态标识符函数集合,且满足M0∈R(M),M(p)表示库所p中包含的标识符函数值;

(5)Fδ表示TVPN 中时变函数式集合,分别包含变迁t所对应的时变输入功能函数式集合FIδ和时变输出功能函数式集合FOδ,且Fδ=FIδ∪FOδ,Fδ中函数式及其值均为时变的,即与时间因子δ有关;

(6) 变迁触发规则:对∀t∈T,令,若fIδ|M=Yt,则称变迁输入′t满足状态M

下的时间因式fIδ,也称t在M下可触发;当t在M下触发后,由时变输出fOδ引导并演变为新的标识M′:

其中,m,n∈N+为系统中组件服务对应的全部输入/输出功能数量.

在TVPN 中,当某一变迁触发时,会受到系统局部外延和时变因子δ的影响,若在表示变迁触发的有向弧上添加包含时变输入功能函数fIδ和时变输出功能函数fOδ,有利于清晰描述变迁使能条件及系统时变参数引发的输入/输出功能库所状态特性的相应变化.

本文中在对时变Petri 网及其结构进行描述时,库所利用实线圆圈进行表示,时变库所利用虚线圆圈进行表示,操作变迁利用矩形框进行表示,服务变迁利用梯形框进行表示,标识符利用圆点表示.对于TVPN 中基本元素的图形化描述,将时变输入函数表达式fIδ和时变输出表达式fOδ标注在变迁触发的有向弧上,用于表示受可变时间因素影响的状态触发及部分系统外延结构,其基本元素的功能关系如图3 所示.

Fig.3 Kinds of time-varying transitions of TVPN图3 TVPN 中的时变功能变迁类型

图3(a)为普通Petri 网的功能变迁结构,变迁触发不受时间因素影响,只与库所及标识状态有关;图3(b)表示时变Petri 网结构中,变迁由时变输入fiδ影响触发,且变迁发生后由时变输出fOδ引导指向下一时变库所;图3(c)表示时变库所的变迁只由时变输入fiδ触发,不存在时变输出fOδ影响,其指向不包含时间因素的库所;图3(d)表示变迁不受时变输入fiδ影响,只受时变输出fOδ引导,并指向当前的时变库所.

2.3 基于时变Petri网的Web服务组合模型

在Web 服务及其组合过程中,很多情况下使用到的Web 服务源自很多各类领域,因此与之相对应服务的筛选配置时间也有显著差异.如果设定的组合流程中可随机选择有限服务集,则通过组合组件服务得到的综合QoS 值和用户反馈评价指标将受到时变函数因素的较大的影响.在组件服务本身性能的约束条件下,QoS 值直接决定了组合服务是否能够执行并达到预期效果.因此,考虑利用时变Petri 网建模分析服务组合问题并对分析计算时变函数对QoS 的影响,进而可以实现在将结果发布到实际系统前,对组合服务的流程正确性和QoS 量化值进行评估.

定义13(Web 服务组合的时变Petri 网模型).称六元组SC-TVPN=(WS,Fl,St,N,M,)为一个基于时变Petri 网的服务组合模型,当且仅当满足如下条件时成立.

(1)WS为服务候选集,其包含了n个基本服务S1,S2,…,Sn;

(2)Fl为组合服务过程对应的映射规则集;

(3)St为基于服务流程算法的组合服务策略集;

(4)N表示一个有向Petri 网系统,其对应包含了时变库所集、有限变迁集和工作流关系;

(5)M表示网系统中库所和时变库所的标识符状态函数集;

(6)Fδ表示组件服务功能库所间所包含的时变函数式集合,时变输入功能函数式集用FIδ表示,时变输出功能函数式集用FOδ表示.

在SC-TVPN 中,对其基本要素包含下述几点说明.

(1) 库所集合P中包含服务的数据流库所pD和服务的逻辑流库所pL,上述两类库所对应的子集分别为PD和PL,满足,且PD∩PL=∅,pi为不包含时间因子的一般库所.前者中存在两个特殊库所——源组件服务库所(只含输出功能)和终止组件服务库所(只含输入功能),普通数据流库所用于存储服务及组合过程中的数据和功能;后者主要用于记录服务组合时的参数转换、功能执行等逻辑过程.

(2) 在变迁集合T中,对于∀t∈T,′t和t′都至少包含1 个时变函数式引导的时变库所.

(3)Fδ中包含一组时变的功能函数集,其用于表示SC-TVPN 描述服务组合过程对应的时间参数驱动Petri网系统使能.组件服务间的库所和变迁触发都需要满足Fδ的约束条件.

(4) 基于BPEL4WS 相关描述,在SC-TVPN 的服务组合逻辑流包含了顺序、并发、分支选择和逻辑循环共4 种控制结构,如图4 所示.

为了表达引入时变函数关系导致的Petri 网异构变化特性,本文采用Petri 网标记语言(Petri net markup language,简称PNML)[13]来描述时变Petri 网服务组合模型的逻辑结构.其中,PNML 是一种基于XML 的Petri网系统信息交互形式,包含可读性、通用性及相关性这3 方面设计原则,以元模型、类型定义接口、特性定义接口等形式清晰表达Petri 网及其拓展模型的结构,是Petri 网交换格式标准的一种解决方案.

本文以服务组合过程中组合流程的正确性验证,及用户反馈评价服务质量中时间属性为研究重点.可将QoS 定义为一组服务的非功能属性集合,根据用户偏好,包含一系列评价指标.根据本文服务系统构造及电厂调度信息服务的用户需求,对所做研究针对的服务质量作出如下定义.

定义14(服务质量).四元组QoS=(Ps,Ts,As,Rs)为用户反馈的服务质量,其中包含一组服务组合策略的非功能属性数据.在用户组合服务整个过程中:Ps为服务执行费用(单位:元,CNY);Ts为服务执行的时间开销(单位:s,秒);As为服务可用性,表示系统提供可用组件服务的能力;Rs为服务可靠性,即系统成功执行组合服务的概率.对服务时间开销Ts,其值为SC-TVPN 系统内,构建组合服务的全部组件服务所包含的变迁触发及外延时间变化中,所有时变输入功能函数式和时变输出功能函数式的函数值代数之和.

将服务系统中的组件服务及组合服务策略的QoS 属性记作四维列向量qj形式,则对于一组包含n个组件服务的服务候选集WS={S1,S2,…,Sn},可将其全部服务的QoS 属性记为一个n×4 阶矩阵Q=Qij,其中,i,j,n为根据用户需求设定的自然数,且1≤i≤n,1≤j≤4,表示服务组合策略中包含的组件服务属性数据.

根据基本工作流关系,将服务质量的非功能属性设置为随机变量,对其数据采用随机变量组合法进行度量和计算.表1 为SC-TVPN 服务组合系统下,用户所提偏好及约束条件的QoS 计算方法,其中,αi为分支选择结构第i个组件服务操作被调用的概率系数,i=0 时,表示跳过组件;i=1 时,表示选择该组件服务.

Fig.4 Structures of logic in SC-TVPN图4 SC-TVPN 中的逻辑结构类型

Table 1 Calculation methods of random variable data of non-functional properties on QoS表1 QoS 的非功能属性随机变量数据计算方法

由于QoS 各属性量纲不一致,无法通过4 个属性值直接衡量用户满意度及使用评价,因此需要对各维属性参数进行量化处理.对于服务执行费用和时间开销指标,随着参数值越大,QoS 越低,属于负相关性影响指标;对于服务可用性和可靠性指标,随着参数值越大,服务质量越高,属于正相关性影响指标.对正、负相关性指标分别用公式(1)和公式(2)进行量化.

其中,V(t)(Pr)为量化结果.然后,对量化数据采取误差标准化处理,其实现过程如公式(3)所示.

其中,Pr(u,i)为用户对第i个服务反馈的服务数据量化值,Si为组件服务数据的误差率,θ为误差容错限值,di为参数标准化权值.再根据用户偏好,设置服务非功能属性匹配权值ω,令ωi=di,且ωi∈[0,1],,并计算QoS 数据归一化值,用V(QoS)表示,计算过程如公式(4)所示.

最后,根据得到的归一化值V(QoS)及用户匹配权值ω,由公式(5)计算该组合服务的综合服务质量值Ψ.

其中,Ψ∈[0,1].由计算过程可知,其值越大,表示组合服务策略越能满足用户特定需求,越接近用户的期望满意度.

3 服务组合模型的性能分析

为了验证所提模型在服务质量(QoS)的时间开销属性上具有有效性和可行性,本节首先说明服务组合对语义和流程正确性检验的必要性;然后给出时变Petri 网下,随着时间参数变化导致库所的状态变迁触发条件,使服务系统满足状态可达性,即实现服务组合驱动条件;并提出一种基于服务路径回溯检验的鱼群组合算法,该算法能有效减小服务候选集的检索空间,避免服务库所的冗余利用,可实现大规模服务候选集中,高效检索组件服务,快速构建组合服务输入/输出功能匹配及用户需求QoS 度量值的服务组合策略.

3.1 组合服务性能分析的前提

服务组合模型的性能分析,主要从两方面检验[14,15].

(1) 语义规范性.服务组合的PNML 语义描述满足设定的匹配规范,即在语义上能够满足参数统一、操作协同、节点状态稳定及触发条件充分等要求;同时,通过对组合控制逻辑和QoS 属性的语义一致性检验,保证流程上能够正确执行.

(2) 流程正确性.通过对建模流程进行验证,进而保证工作流语义描述正确性、系统状态可达性、逻辑流程死锁性及系统边界性等要求.

结合服务本身特性分析,户反馈评价及服务质量主要依赖模型语义描述和功能参数,与此同时参数调配、映射规则、时变参数、变迁触发、操作条件等也都可能对性能产生一定的影响.

为了清晰地明确组合服务性能分析的相关概念,考虑对时变Petri 网服务模型进行简化.若一个给定的服务候选集WS={S1,S2,…,Sn},其对应的映射规则集合为建立的某一服务组合策略Sti以S0为起始服务.由时变Petri 网特性,令该服务模型抽象为四元组TVPN=(N,M,L,Fδ).其中,

·Fδ表示时变输入/输出函数集合;

·M表示功能标识符函数集合,Mk(S)表示对调用某服务状态的输入/输出功能标记;

·L表示时变Petri 网的有向弧集合,有向弧对应包含了服务间的控制逻辑和功能属性信息;同时,其表示为三元组l′=(oi,ij,fl),其中,oi表示此前服务的输出,ij表示与此前服务相匹配的后一服务输入,fl为其包含逻辑关系所对应的服务映射规则.

为了方便讨论服务节点使能状态与时变函数触发库所变迁的关系,首先需在组件服务的组合过程进行声明,避免组合过程中冗余服务重复调用导致系统效率降低,引入回溯网络节点定理对组件服务节点作出标记,即定理1 用于判断是否存在冗余服务操作类型,建立控制流的基本逻辑关系.

定理1(回溯网络节点定理).对于一个时变Petri 网服务组合模型SC-TVPN,若有向弧l′=(oi,ij,fl)满足M(pin∩sk)⊆M(p),且任意以is为输入功能的终止服务sn至少具备1 条最简有向路径使服务组合策略成立,其中,li,lj,ls表示被有向路径L覆盖的有向弧,li表示源组件服务输出功能指向的有向时变函数弧,ls表示终止服务所包含时变函数的输入功能有向弧,则其余非最简有向路径L′上的任一有向弧l对应的标识集满足:

其中,L′为有向弧L上以第j个服务为起始服务的回溯子弧,i,j,s,n∈N+.

为保证组合服务策略分支流程是正确的,当执行前i个服务的输出功能组合操作时,需检验此前组件服务功能路径的动作过程,将这一过程称为回溯检验.构建含n个组件服务的策略则需进行n⋅(n−1)/2 次回溯检验,且需要对每条有向弧回溯路径对应的QoS 属性进行一致性验证.

定理2(系统状态可达性定理).设时变Petri 网服务组合模型SC-TVPN 中,若时变函数集Fδ={fδ1,…,fδn}在∀ti∈T,pj∈P都满足关联矩阵Aij对应的功能映射关系,且至少存在1 条从p0到pn的有向回溯路径,使其满足状态迁移矩阵K,且∀M∈R(M),∃pk∈P,使Mk[tk.fδk.pk〉Mp.

证明:令Mp为SC-TVPN 中构建的某一服务组合策略St所包含第i个组件服务Si的起始输出功能状态或前一服务Si−1的终止输入功能状态.在时变函数作用下,只有Si−1的输出功能库所和Si的输入功能库所具有时间关联,其他服务不受时变函数fδk的影响,每发生一次状态触发,用一个标识符函数相对应,构建系统关联矩阵表示组件服务功能调用的概率,则只有当状态满足Mk[tk.fδk.pk驱动节点Mp状态使能时,系统状态满足可达性.因此,当前i−2 个组件服务组合后,Si库所可以迁移至状态Mk,并使其能够到达任意组件服务状态.

定理2 表明SC-TVPN 实现服务组合过程中,若某一服务节点状态在时变函数下使能,则与其有时间关联特性的库所周期状态将由变迁条件等待触发.

为了进一步说明服务组合的逻辑流控制过程及QoS 计算方法,假设服务候选集中,由前一组件服务S1的输出功能和后一服务S2的输入功能构造一次服务节点组合匹配.构造服务S1到S9的组合服务,可由中间路径的任意服务实现,则选取两个功能相同,组件服务不同的组合服务进行QoS 计算,相应的QoS 综合值记为Ψ1和Ψ2.则经回溯过程所求得的用户综合QoS 评价值分别为,ωk为根据用户设定权值,则系统中库所的基本控制流和数据流逻辑关系如图5 所示.

Fig.5 Logical relationship of control flow and data flow in service model图5 服务模型中的逻辑关系

组合服务过程中,后一服务S2的时变输入功能集fIδ与前一服务S1的时变输出功能fOδ以映射规则集中的服务规则fl相对应.对服务组合的回溯过程即对已组合部分的输入/输出映射关系检验的过程,这个过程可通过检测对应输入/输出功能集中的参数值获取.

依据SC-TVPN 中服务控制流逻辑结构,引入组合成功率TR[16]的概念,用于比较构建组合服务时,表示不同方法下组件服务的可用性及可靠性对组合服务可成功执行的概率大小.本文中,组合成功率TR由公式(6)计算求得.

其中,li表示满足组合服务功能的有向弧路径长度;M(s)表示标识符函数状态集;t表示可触发变迁;ω为回溯路径涵盖的组件服务中,QoS 属性的用户匹配权值,表示该组件服务在用户需求功能的作用比重.

3.2 服务流程验证及组合算法

为使服务候选集中,组件服务均能以特定服务选取概率进行调用,因此需要对候选组件服务实现全局遍历,记录服务信息和节点状态.鉴于此,本文考虑在人工鱼群算法[17]的基础上利用人工鱼个体信息对应地记录服务的输入/输出功能、QoS 数据及性能属性.感知周围环境信息的特点为基础,提出一种遍历服务库所及组合操作变迁的服务组合流程验证及策略计算算法.该算法中,人工鱼个体分别用于记录组件服务的输入/输出功能、QoS 数据及性能参数等信息,通过建立的服务映射规则,对不同服务模型下建立的服务组合策略各项指标进行选择和计算,进而实现全局服务的筛选和优化配置.

本文算法采用自顶而下的设计西路解决服务组合问题.首先,根据服务数,将一定数量的人工鱼个体置于服务候选集中,其用于记录单一服务的性能参数、时变函数式及状态信息,当系统使能,满足组合操作变迁触发条件时,根据个体记录的服务空间、时变库所及变迁状态,即可实现对遍历至当前位置状态的检验;然后,固定当前服务状态xi,根据设定的调用概率实现下一服务的调用,或对已组合的服务策略进行遍历检验,以得到与当前服务状态匹配的最优组件服务.

由于人工鱼的主要活动受限于巡视视野内的位置状态,通过与当前位置进行比较,选择最优动作作为下一时刻的活动方向.因而,考虑将寻找最优服务策略与人工鱼搜索更高浓度食物生存行为[16]建立联系,则每个人工鱼个体都将以向食物浓度更高的位置运动作为目标.

鉴于此,为了提升服务组合模型的组合效率和可靠度,并从含大量组件服务的候选集中取得满足要求的服务组合策略,需要有效提升个体的全局搜索能力,克服原始算法精度低和后期收敛速度慢等问题.因此,本文以基本鱼群算法为基础,在人工鱼个体位置更新过程中引入已知全局最优的服务信息,进而改善了个体遍历的效率,其可以利用公式(7)～公式(9)进行表示.

其中,Val表示个体的视野范围;Sp表示随机移动的步长;Ra(⋅)表示变量函数在区间[0,1]上服从随机分布,其对应服务组合时,满足回溯条件的服务调用概率;Xi(t)是人工鱼的当前状态;Xi(t+1)是个体寻优下一位置的状态;ΔXi(t+1)由当前状态和较优状态X′(t+1)的差值决定.

为保证组合策略St能反映真实系统的性能,在寻优过程中,需要结合实际情况对服务参数设置可靠性和可用性等约束条件,删除不满足最低用户需求的服务策略,进而保证服务组合的效率,即满足:

此方法用于检验时变库所的状态和变迁操作正确性,并可以用于计算不同模型下生成服务组合策略的综合QoS 值,并在此基础上依据用户偏好性能提供一种最优服务组合策略.基于服务组合的语义描述和逻辑结构,我们将算法流程验证和组合计算归纳为如下步骤.

(1) 利用PNML 惯例文档描述服务数据和逻辑功能,将服务系统转化为时变Petri 网结构框架.其中,para为组件服务性能参数,data为服务基本信息或数据;fδk(p,n)为受n个时变参数影响的第k个服务库所,e(t〉)表示操作变迁t在fδk下使能,M为时变标识符的集合.

(2) 遍历服务系统中的时变参数库所及服务变迁操作,计算Petri 网系统的状态可达图.

(3) 检验服务系统是否满足语法正确性、状态可达性及变迁死锁性[16].

(4) 检验组合策略的功能特性、执行顺序和QoS 一致性.

(5) 计算并输出全部服务组合策略,生成服务组合策略集合.

具体流程见算法1.

算法1.服务性能检验及组合分析算法.

输入:服务候选集WS,服务映射规则,服务性能参数.

输出:组合分析检验结果,服务组合策略St和对应结果.

上述过程通过服务组合性能模型和时变Petri 网的状态可达性对服务对象加以分析.基于当前状态xi及对应集合中其他状态及映射规则,进行完整地遍历搜索.因此，可以实现对描述服务数据、逻辑的元素进行正确性和一致性检验,进而保证各项性能参数满足QoS 需求.假设服务集中的服务数目表示为n,服务映射规则数目表示为m,人工鱼个体检索的最大循环次数为lmax,则所提算法对应的最大时间复杂度为O(n),空间复杂度为O(m×lmax).同时,函数Test(ServiceFlow)可以保证系统性能评价的准确性,函数Check&Calculation(St)则从QoS 属性方面检验时变Petri 网服务模型的组合一致性,函数Genaration(St)可以高效计算系统效率及组合成功率.

4 仿真实验及结果分析

本节根据时变Petri 网特性对服务组合过程进行建模.首先,在服务系统中,对功能相同的Web 服务通过不同方法进行语义绑定、参数设置、文档发布,使其作为已发布的组件服务可任意调用;然后,对多功能分布式服务进行组合,在不同方法下实现功能相似的组合服务构建过程,并获取相应服务绑定数据;对于用户,则可任意调用系统发布的组合服务,并给出相应的用户反馈评价;在大量数据提取及分析统计后,可表明时间因素对服务组合用户反馈评价的影响;同时,为了进一步证明时变Petri 网服务模型的有效性,本节通过实验数据分析,定量说明本文方法在服务组合过程中时间表达的突出特性;最后,与包含普通Petri 网建模的服务组合方法对比,说明时间因素对用户反馈评价的重要性及本文方法的可行性.

4.1 实验条件

基于算法1 及用户目标需求分析,为了充分证明本文方法的可行性和有效性,采用研究团队开发的基于开发网络环境下,松散耦合的B/S 结构服务信息调度应用系统来综合分析模型性能.在此电厂信息调度服务平台中,采用随机法获取37 640 个组件Web 服务,用于构建6 000 组电力信息组合服务,其中,组件服务包含服务数据、控制逻辑及用户评价的QoS 历史数据等基本信息,用户数据由电厂各部门289 名工作人员在6 个月内使用此平台的情况来采集.针对电厂信息调度服务平台中电力信息的5 个基本服务,通过BPEL 流程进行调用,其中的服务执行参数由调度费用、时间开销、服务可用性和可靠性组成,且各参数随时间动态变化,将电厂用户每执行一次服务的参数记录下来,以TVPN 对服务参数进行描述,由Petri 网结构对各服务节点实现参数最优化的选取和匹配,将服务组合转化为节点路径优化问题.

基于模型流程,设置系统时变函数集Fδ=FIδ∪FOδ,将自然数集N={1,…,1000}视作有限时变库所集,其每个元素对应状态表示个人在一段时间内使用组合服务的次数.时变函数式与组件服务的输入/输出功能相对应,表示服务状态变迁触发或外延.为了便于采集实验数据,设定1/4组件服务包含时变输入/输出影响,1/4只包含时变输入影响,1/4 只包含时变输出影响,其余不受时间变化参数影响.将服务平台基本流程转化为时变Petri 网模型,其逻辑执行过程如图6 所示.

Fig.6 Services workflow of the platform of power plant information based on SC-TVPN图6 电厂信息调度服务的SC-TVPN 网流程

本实验在对应的实际系统中,将时变Petri 网的时变函数表达式与特定服务条件综合进行讨论,设置部分组件服务的文档为其他建模类型,用于实验对比或测试.实验中用到的信息调度服务平台搭建在IBM X260 服务器上,实验的CPU 为Dual-Core E6500@2.93GHz,内存4GB RAM,系统软件开发环境为Visual Studio 2010,数据库采集系统利用SQL Server 2008 开发搭建,使用到的组件服务主要为涉及电厂工作流程的基本信息调度规程.

4.2 服务组合的有效性实验

为了验证本文所提时变Petri 网服务组合方法的可行性和有效性,根据采集的实验数据,通过设计的服务流程验证及组合算法,由比较调用的组合服务QoS 指标实现,并综合计算各方法下构建组合服务的组合成功率TR0,可直观得出不同方法对组合服务系统建模的作用及有效性比较.

表2 为不同服务组合方法下,在服务集S1与S2中获取服务组合策略的QoS 可描述性及组合成功率的对比情况.其中,在构建的组合服务策略集St上,先选取4 000 个组合服务作为服务测试集S1,将其余2 000 个组合服务作为服务比较集S2.对于S1和S2中的电力信息调度服务,分别划分组别,并以包含数目为10 个,20 个,50 个,100个,500 个映射规则实现综合调度信息服务的组合.组合过程采用服务编码文档绑定及在线发布形式,功能相同的服务分别由基本工作流法(BPEL[18])、基于普通Petri 网(PN[13])的BPEL、模糊理论组合法(Fuzzy[19])、基于PN/TVPN 的Fuzzy、服务功能组合法(AOWSC[20])、基于PN/TVPN 的AOWSC 等组合方法实现建模和发布.由服务实际发布的功能可知,上述方法均能表达服务的并发异步特性,可实现不同功能的服务组合过程.得到的服务组合策略中,根据功能不同,服务数为10 个～1 000 个.对于用户而言,各组合/组件服务可循环执行且优先调用QoS 中可用性较高的执行.然后依据算法1 计算St1～St10这10 组服务组合策略的时间开销属性Ts,并计算各方法下的组合成功率TR0.

Table 2 Comparison of the composition evaluation with different services composition methods表2 不同服务组合方法的组合评价比较

在使用不同组合方法构建组件服务并进行组合时,不同服务数下时间开销对QoS 影响比重V(Ts)/Ψ的计算结果.可知,使用BPEL,Fuzzy 和AOWSC 这3 种方法均可进行服务描述,但由于时变Petri 网在变迁引发操作中考虑了时变参数函数作用,对QoS 时间开销属性具有更好的描述能力,因此比普通Petri 网构建的服务组合策略具有更高的组合成功率.随着服务数增多,系统检索服务候选集的时间与服务间功能组合所存在的特定时延都会增加.通过时变Petri 网的时间参数表达式,将时间因数与本体服务建立关联,构造一个与服务本身特性相关的随机变量,并计算服务组合总时间开销.

基于SC-TVPN 方法在不同服务组合建模框架下都能较好描述服务数与时间开销的近似线性增长特性,本文采用BPEL 进行服务组合功能逻辑和数据流描述,并结合时变Petri 网描述服务异步组合过程,在电厂信息调度服务数据下,得到了比Fuzzy 和AOWSC 方法更高的组合成功率.当服务较少时,时间开销占QoS 的比重为11.37%;随着服务数增多,该比重趋于稳定到45%,说明时间开销对服务组合的质量评价具有重要作用.同时,随着服务数增多,用户对服务组合策略的满意度也有较高要求,当用户需求和候选集中可选择执行的服务输入/输出功能一定时,则可选择执行一组组合成功率高且时间开销低的服务组合策略.因此,与已有服务组合模型相比,本文组合方法在评价时间开销对用户反馈服务质量评价的影响上具有有效性.

图7 表明,构建同一个服务组合方案时,使用不同服务集构建该方案的执行时间也不同.随着方案中服务数的增多,根据回溯算法计算服务组合方案所需的执行时间也将增加.此外,当一个方案服务数较少时,构建组合方案的算法执行时间在两组服务集上无明显差异;反之,方案服务数较多时,包含服务数目较少的服务集S1在执行时间上显然效率更高.

Fig.7 Contrast of service time consumption and efficiency for different methods on the same service set图7 不同方法在相同服务候选集下的时间开销及系统效率对比

4.3 同一服务候选集下构建服务组合策略

第4.2 节的实验是针对同一个服务候选集,采用不同服务建模方法进行实验的,目的是为了通过比较得出本文方法在描述QoS 的时间开销属性上具有一定优势,同时具有较高的组合成功率.为了进一步说明在不同服务候选集下,本文方法同样具备有效性和可行性,本节在同一服务候选集下进行实验,并比较使用不同的服务映射规则构建不同服务组合策略St1和St2时得到的用户满意度来证明.表3 为设定不同服务组合策略中的服务数,通过实验获得的100 组用户反馈评价情况.

Table 3 Feedback of users for different service compositions on the service set表3 同一候选服务集下构建不同服务组合方案的用户评价

表3 反映了在时变Petri 网构建的服务组合模型中,使用包含不同服务数的同一候选服务集和服务映射集合构建不同服务组合策略的用户反馈情况.可以看出,随着服务候选集包含的服务数增多,使用本文所提模型建立的服务策略在用户反馈通过数上呈降低趋势,说明服务搜索空间越大,构建使用户满意的服务策略难度越大.

图8 为在同一个候选服务集下,用8 组服务映射规则构建两组不同服务数的服务组合策略,在用户反馈通过数与组合服务时间开销指标的对比情况.

Fig.8 Contrast of service time consumption of different service compositions under the same amount of services图8 相同服务候选集下的不同服务组合时间开销

可知,服务策略包含的服务数是影响用户反馈评价的主要因素.另外,在同一服务候选集中,构建服务数不同的服务策略时,用户反馈通过数相差不大,若用相对通过率来表示用户对组合服务满意程度的对比,则该数值可保持在1.5 以下.根据文献[21]方法可知,本文建模方法是可行的.

使用本文方法进行电厂信息调度服务应用时,应充分考虑使用最少服务数的服务候选集来满足用户的使用需求即可.当组合方案中服务数一定时,时间开销是影响用户满意度的重要参考指标.由调度平台的实际运行过程,使用本文所提建模方法,在宏观上可以有效提高电厂工作人员的信息服务满意度;同时,可以根据用户对信息调度服务的使用偏好,我们可以进一步调整该信息调度平台的服务结构,通过合理的资源配置方式,将软硬件性能与组件服务的执行效率相结合,即可实现平台的最优利用价值.

5 总结

用户反馈QoS 评价方法是反映系统提供组合服务策略是否达到用户期望值的重要衡量指标,而服务的时间开销特性对本文研究的电厂信息调度服务平台具有重要参考价值,电厂系统以省时省力的调度信息服务规程为基准,因此用户更多考虑的是如何节约服务调用的时间开销.本文根据Web 服务具有异步并发、协同操作等特点,考虑到目前仅有较少研究针对特定服务组合的时间开销特性,提出一种基于时变Petri 网的系统结构用于描述服务组合建模过程.该模型面向服务组合策略计算,根据组合服务库所回溯理论对服务策略执行正确性检验,降低系统普遍存在的服务重用问题,能有效提高服务组合效率,使系统具有较高的稳定性和组合成功率.

本文提出一种由时间Petri 网拓展得到的时变Petri 网服务组合建模方法,并在一组实际电厂信息调度服务平台提供的Web 服务下进行实验分析,给出不同服务建模方法在组合成功率上的对比情况,说明该方法能够达到较好的效果.此外,使用不同规模的服务候选集进一步通过实验数据,说明时间开销特性对服务组合策略的效率及用户满意度的影响.在日益复杂的网络环境中,使用一种简单、高效的服务组合方法是满足企业级用户需求的前提条件.今后,我们将研究影响服务组合质量的其他因素对系统性能的影响,并考虑通过建立更高效的Petri 网拓展模型结构来描述系统性能,为服务系统综合分析做进一步探索和研究.

作者注 本文是我们于2016 年6 月30 日投到《软件学报》的论文.该文是大连理工大学大学韩敏(本文第一作者)老师指导的2017 届(2017 年6 月)毕业的研究生孙国庆(本文第二作者)的硕士学位论文《基于时变Petri网的Web 服务组合研究与应用》工作成果的一部分,特此说明.