基于事务和QoS组合的服务质量性能预测方法及装置

摘要

本发明涉及计算机网络技术领域，特别是基于事务和QoS组合的服务质量性能预测方法及装置。该方法包括：首先对Web服务赋予事务性，然后分析具有事务性要求服务的组合问题；其次分析具有事务属性组合服务的性能问题；最后，根据事务性组合服务的性能比较，提出基于事务和QoS组合的服务选择方法；本发明还包括一种使用上述方法的基于事务和QoS组合的服务质量性能预测装置，该装置还包括提取模块、处理模块、提取模块、确定模块。

说明书

技术领域

本发明涉及计算机网络技术领域，特别是基于事务和QoS组合的服务质量性能预测方法及装置。

背景技术

Web服务是一项业务之间自动交互的技术，企业能够发布它们的内部业务流程作为一个服务，然后在Web上提供它们的服务。随着应用的深入，业务流程可能包含一个或多个业务功能，由于这些业务可能调用来自不同组织的Web服务，所以需要按照一定方式组合来协同工作，并保证其运行的可靠性和结果的一致性。在复杂的网络环境中，由于面临以下问题，服务组合可能变得十分复杂：组件服务可能长时间运行，服务环境是松散匹配的和自身的异步性，由于机器失败导致的组合过程可能被取消，服务可能被移去或撤销，处理潜在的失败是必须的等等。因此，Web服务需要事务机制来保证输出的一致性及正确和可靠的执行。

在传统的组合服务选择方法分析中，研究者通常基于工作流的不同结构进行组合服务整合QoS(Quality of Service)分析，然后根据QoS进行组件的选择。但是，这些研究都没能考虑事务的要求。虽然事务的引入确保了组合服务的正确和可靠的执行，但它影响了组合服务的QoS属性。所以，需要提出一种方法来对基于事务和QoS组合的服务进行选择。

发明内容

针对现有技术的问题，本发明提出基于事务和QoS组合的服务质量性能预测方法及装置。

基于事务和QoS组合的服务质量性能预测方法，该方法包括：

首先对Web服务赋予事务性，然后分析具有事务性要求服务的组合问题；

其次分析具有事务属性组合服务的性能问题；

最后，根据事务性组合服务的性能比较，提出基于事务和QoS组合的服务选择方法；该方法具体包括以下步骤：

第一步、在进行当前组件服务的选择时，根据前面已经选择合适组件服务的事务特点，并按照事务组合服务的规则要求，获得满足事务性要求的候选组件服务；

第二步、对每个候选组件服务进行性能评估，评估考虑Web服务的QoS和事务性要求；

第三步、重复以上过程，直到获得一个满足要求的组合服务。

所述第一步、第二步的具体内容如下：

在通常的服务选择方法，性能评估都是基于所有组件服务的QoS进行分析，本方法基于事务性和QoS，把两者相结合获取到基于事务的组合服务选择方法；

在基于事务的组合服务选择过程中，当一些功能性相似的候选组件服务可以被获得时，它们的非功能性要求QoS能够反映用户的需求，本方法提出Web服务ws下面三个QoS指标：

(1)执行价格(Execution price，EP)：请求者调用服务ws所需要的花费，表示为q_ep(ws)；

(2)执行时间(Execution time，ET)：服务ws执行一次所需要的时间，表示为q_et(ws)；本方法认为服务执行一次的时间是相同的，并且在相同的时间内，服务执行一次可能失败，也可能成功完成；

(3)成功完成概率(Probability of Success，PS)：服务ws成功完成用户请求的概率，表示为q_ps(ws)；

其中，执行时间需要考虑组合服务的事务性带来的变化，分析过程如下：

(1)一个服务具有可补偿性，那么它能提供补偿策略来撤销该服务的影响，用符号“c”表示；

(2)一个服务具有可不断重试性，那么它能被重试，并且通过足够次数的重试达到最终成功，用符号“r”表示；

(3)一个服务具有中心点特性，那么它一旦执行成功，它的影响永远存在，而且不能被撤销，如果它执行失败，没有任何影响，用符号“p”表示；

由于网络环境的动态性、不确定性和开放性，来自不同组织的组件服务往往会调用失败，假设一个Web服务成功执行的概率为ps，服务执行一次的时间为t，那么在时间t内一个Web服务或者成功执行，或者执行失败，服务在前n-1次执行都失败，第n次执行成功的概率符合几何分布，概率函数为：

P(X＝n)＝(1-ps)^n-1ps

Χ表示服务第几次执行，那么数学期望值为：

几何分布的数学期望反应的就是成功的平均执行次数，即成功执行的平均次数为1/ps，服务执行一次的时间为t，那么，成功执行的平均时间st为：

st＝t/ps。

组合服务由基本组合模式构成，为分析事务组合服务的时间性能，现提出基本组合模式的时间性能分析方法；四种基本的组合模式分别是：序列模式、并行模式、选择模式和循环模式；并且服务组合由工作流模型来描述，TP表示事务性，TO表示一次执行时间，ST表示成功执行时间，PS表示成功执行概率；tp、to、st和ps表示组合服务相应概念的具体值；模式中每次只有一个组件服务执行失败。

所述第三步的具体内容如下：

本方法基于事务和QoS的服务选择方法，提出两个QoS指标：成功完成时间和执行价格，成功完成时间根据时间性能分析方法获得，执行价格根据组合服务每个组件服务的执行价格之和获得；然后对成功完成时间和执行价格进行加权处理，以获得事务组合服务的QoS分数值，并作为对事务组合服务进行选择的标准。

所述QoS指标还包括信誉、可获得性。

该方法还包括(1)选择模型的方法；

在Web环境中，组合服务一般由其它服务或组合服务构成；包括三种组合模式：序列，并行，选择；随着越来越多功能性相似的服务被获得，从中选择最优的服务实例；为了确保组合服务可靠和正确的执行，服务组合需要事务的支持；本方法提出两种基于事务和QoS的服务选择模型；

第一种事务组合服务选择模型为事务性确定服务选择模型；组合服务由工作流描述，合适的事务性已经被赋值给工作流中的所有活动；因此，候选服务已经由功能性和事务性要求确定；

第二种事务组合服务选择模型为事务性未知选择模型；组合服务仍然由工作流描述；但是，工作流中活动的事务性是未知的，活动的事务性由被选择来执行该活动的候选服务的事务性决定；基于这两个选择模型，并结合基于QoS的选择方法，本方法还提出了相应的全局最优选择算法。

该方法还包括(2)全局最优选择算法；

在基于事务和QoS的组合服务选择模型中，事务的引入对组合服务的QoS时间性能产生了影响；因此，根据本地最优的时间指标选择最优的候选服务并没有考虑到事务对时间性能的影响；所以，本方法使用全局最优方法来对服务进行选择；

首先，基于所选择模型，工作流的事务性已经确定，即工作流的每个活动事务性为已知的，这里把事务性已知的工作流称之为事务工作流(Transactional Workflow，TWF)；假设事务工作流TWF中活动个数为n，TWF＝{a₁,a₂,…,a_n}；对事务工作流中的每个活动a_j，j＝1,2,…,n，有q_j个候选事务服务能执行活动a_j，该候选服务集合满足活动a_j的功能性和事务性要求；赋给每一个活动一个候选服务可以获得一个可执行的事务组合服务；那么，根据所有候选服务可以获得一个集合可执行的候选事务组合服务TCWS(Transactional>1,tcws₂,…,tcws_m}，m＝Πq_j，这里，j＝1,2,…,n；然后，使用全局选择算法从集合TCWS中选择最优的可执行事务组合服务；这里，目标函数为Score(tcws_i)，为每个可执行的事务组合服务使用简单的加权方法来计算整个可执行事务组合服务的QoS分数值；Score(tcws_i)＝∑_jw_jq_ij，其中w_j∈[0,1]，∑_jw_j＝1，i＝1,2,…,m，q_ij表示每个候选服务的两个QoS属性；具有最小Score值的可执行事务组合服务作为最优的选择，如果有几个可执行事务组合服务具有最小的Score值，那么随机选择一条来执行事务组合服务；基于事务工作流的全局最优选择算法(GlobalSelection>

第一步：根据每个活动的候选服务集合，获得所有满足组合服务要求的可执行事务组合服务集合，

第二步，根据时间性能分析算法，获得每条可执行事务组合服务的成功完成时间，赋值给ST[i]，同时获得执行价格，赋值给EP[i]，根据加权处理，获得tcws[i]的Score值；

第三步，对比所有可执行事务组合服务的Score值，选择Score最小的执行事务组合服务赋值给BestTCWS；Score[i]为可执行事务组合的Score值；

算法GST伪代码如下：

输入：事务工作流TWF

输出：具有全局最小Score值的事务组合服务tcws

开始

结束

本方法还提供另外一种选择算法；根据工作流事务性赋值方法，首先，对工作流模型进行事务性赋值，即只给工作流活动赋予合适的事务性，而暂时不选择合适的服务实例来执行活动；那么，可以获得一个集合的事务工作流TWF＝{twf₁,twf₂,…,twf_m}，既满足组合服务的功能性要求，又满足事务性要求；对每个事务工作流，可以使用GST算法来获得全局最优的可执行事务组合服务，然后从这些最优的可执行事务组合服务集合中，再选择一个最优的事务组合服务来满足用户需求；基于工作流的全局最优选择算法(GlobalSelection>

第一步，根据事务性赋值方法，活动所有可行的事务工作流，然后把它们赋值给集合twf；

第二步，对twf中每个事务工作流使用算法GST选择最优的事务组合服务，同时获得它们的Score值，并分别赋值给BestTcws和MiniScore；最后，从集合BestTcws中选择出最优的事务组合服务BestTCWS；TempMiniScore是一个暂存事务组合服务Score值的变量；

算法伪代码如下：

输入：工作流WF

输出：具有全局最小QoS的事务组合服务TCWS

开始

结束。

该方法还包括(3)启发式选择算法；在全局最优选择算法GSW中，当工作流活动个数变得很大时，算法需要花费的时间可能变得难以接受；所以，我们需要在可接受的算法时间内，获得一个近似最优的事务组合服务来满足用户需求；算法GSW时间主要耗费在两个方面：第一，对工作流进行事务性赋值，获得所有可行的事务工作流；第二，对每个事务工作流通过算法GST获得最优可执行事务组合服务；所以，从这两方面减少算法选择时间，提出了一个启发式选择算法；

启发式评估函数用来评估并找到从当前结点到目标结点的合适路径；在启发式算法中，启发式评估函数用来评估包含当前结点不同事务性的整个事务组合服务的Score值；基于启发式评估函数，首先选择当前活动的事务性，然后，从满足该事务性的候选服务中选择最优的服务来执行当前活动；

在序列和并行模式中，如果当前活动的事务性赋值为p或pr，那么后面所有活动的事务性都必须为pr或cr；在并行模式中，如果当前活动的事务性赋值为c，那么，包含当前活动的并行模式其他所有分支的活动只能为c或cr；在选择模式中，分支活动的事务性和该模式中其他分支的事务性相同；这样就减少了工作流事务性赋值的时间；然后把确定了事务性的活动的所有候选服务的QoS平均值作为参考信息，获得包含当前活动确定事务性的事务组合服务的成功执行时间和执行价格，并加权处理获得Score值作为启发式评估函数的值；这样我们就减少了GST选择算法的时间；

这里，把启发式评估函数HEF分成三个部分，定义如下；

定义1：启发式评估函数并且：

(1)G₁(x)为当前活动的信息；

(2)G₂(x)为历史活动和根据当前活动事务性获知必须进入事务组合服务的候选服务信息；

(3)G₃(x)为未知事务性活动信息；

为了获得启发式评估函数，须知道包含当前活动确定事务性的事务组合服务的成功完成时间和执行价格；这里，我们把工作流的所有活动分成四个部分：

第一部分为已经选择了合适事务服务的活动，被称之为历史信息；那么，这部分活动的成功完成时间和执行价格就作为G₂(x)中的部分信息；

第二部分为当前活动；如果当前活动确定了事务性，那么满足该事务性要求的所有候选服务的平均QoS值作为G₁(x)信息；

第三部分为根据当前活动事务性确定了事务性的后续活动；根据这些活动的事务性，那么满足该事务性要求的所有候选服务的平均QoS值作为G₂(x)的另一部分信息；

第四部分为事务性未知的活动；首先，枚举出所有可能的事务性赋值，再同样活动所有候选服务的平均QoS值；作为G₃(x)信息的包含的信息；

根据这四部分信息，我们可以通过获得包含当前活动的事务组合服务路径的成功执行时间和执行价格，然后加权处理得到启发式评估函数HEF；

启发式选择算法HSW(Heuristic Selection based on WF)过程为：考虑当前的活动，根据前面已经选择合适服务的事务特点，可以获得满足当前活动要求的事务特点集合tpset；如果当前活动选择事务性为p或pr的服务时，满足该事务要求的候选服务为G₁(x)信息；如果活动为选择模式的分支，该选择模式其余分支活动事务性也为p或pr，其余活动事务性为pr或cr；以上活动候选服务为G₂(x)信息，且没有G₃(x)信息；当前活动选择事务性为c的服务时，满足该事务要求的候选服务为G₁(x)信息；如果为选择模式的分支，该选择模式其余分支活动事务性也为c，如果在并行结构中，该并行模式其余分支活动事务性为c或cr，以上活动候选服务为G₂(x)信息；其余事务性未知的活动为G₃(x)信息；当前活动选择事务性为cr的服务时，满足该事务要求的候选服务为G₁(x)信息；如果为选择模式的分支，该选择模式其余分支活动事务性也为cr，为G₂(x)信息；否则后面活动都为未知，为G₃(x)的信息；比较每个事务特点的HEF，为当前活动选择一个事务性，并从满足该事务性的候选服务中选择最优的服务来执行当前活动；在下面的启发式算法中，TP表示前面已经选择合适服务的事务特点，TCWS表示选择的事务组合服务；

算法HSW伪代码如下：

算法HSW

输入：包含n个元素的工作流WF

输出：具有全局最小QoS的可执行事务组合服务TCWS

开始

结束。

一种使用上述方法的基于事务和QoS组合的服务质量性能预测装置，该装置还包括：

提取模块，用于按照组合服务的工作流顺序遍历所述组合服务，提取所述组合服务中的组件服务；

处理模块，用于判断所述组件服务是否为原子服务，若是，则计算得出所述原子服务的性能参数，并为所述原子服务赋予对应的事务性；否则，调用设定算法将所述组件服务整合成原子服务，并计算得出所述原子服务性能参数，并为所述原子服务赋予对应的事务性；

所述提取模块，还用于提取所述组合服务中的下一个组件服务，并返回继续判断所述下一个组件服务是否为原子服务，直至所述组合服务中所有组件服务均遍历到为止；

确定模块，用于根据计算得出的各原子服务的性能参数以及各自被赋予的事务性，确定所述组合服务的服务质量性能。

本发明提供的技术方案预测准确度好，且具有较高的可行性和有效性。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作一简单地介绍，显而易见地，下面描述中的附图是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。

图1为本发明组合模式为序列模式的示意图；

图2为本发明组合模式为并列模式的示意图；

图3为本发明组合模式为选择模式的示意图；

图4为本发明实施例中的事务性确定选择模型；

图5为本发明实施例中的事务性未知选择模型。

具体实施方式

实现本发明的技术方案为：首先对Web服务赋予事务性，然后分析具有事务性要求服务的组合问题，其次分析具有事务属性组合服务的性能问题，最后，根据事务性组合服务的性能比较，提出基于事务和QoS组合的服务选择方法。具体包括以下步骤：

第一步、在进行当前组件服务的选择时，根据前面已经选择合适组件服务的事务特点，并按照事务组合服务的规则要求，获得满足事务性要求的候选组件服务。

第二步、对每个候选组件服务进行性能评估，评估考虑Web服务的QoS和事务性要求。

第三步、重复以上过程，直到获得一个满足要求的组合服务。

第一步和第二步中事务组合服务方法及性能评估的具体内容如下：

在通常的服务选择方法，性能评估都是基于所有组件服务的QoS进行分析，而本发明基于事务性和QoS，把两者相结合获取到基于事务的组合服务选择方法。

在基于事务的组合服务选择过程中，当一些功能性相似的候选组件服务可以被获得时，它们的非功能性要求QoS就变得非常重要。由于QoS能够很好地反映用户的需求，所以它是目前最常用的非功能性指标，本发明考虑Web服务ws下面三个QoS指标：

(1)执行价格(Execution price，EP)：请求者调用服务ws所需要的花费，表示为q_ep(ws)。

(2)执行时间(Execution time，ET)：服务ws执行一次所需要的时间，表示为q_et(ws)。本文认为服务执行一次的时间是相同的，并且在相同的时间内，服务执行一次可能失败，也可能成功完成。

(3)成功完成概率(Probability of Success，PS)：服务ws成功完成用户请求的概率，表示为q_ps(ws)。

其中，执行时间需要考虑组合服务的事务性带来的变化，分析过程如下：

(1)一个服务具有可补偿性，那么它能提供补偿策略来撤销该服务的影响，用符号“c”表示。

(2)一个服务具有可不断重试性，那么它能被重试，并且通过足够次数的重试达到最终成功，用符号“r”表示。

(3)一个服务具有中心点特性，那么它一旦执行成功，它的影响永远存在，而且不能被撤销，如果它执行失败，没有任何影响，用符号“p”表示。

由于网络环境的动态性，不确定性和开放性，来自不同组织的组件服务往往会调用失败，假设一个Web服务成功执行的概率为ps。服务执行一次的时间为t，那么在时间t内一个Web服务或者成功执行，或者执行失败。服务在前n-1次执行都失败，第n次执行成功的概率符合几何分布，概率函数为：

P(X＝n)＝(1-ps)^n-1ps

Χ表示服务第几次执行，那么数学期望值为：

几何分布的数学期望反应的就是成功的平均执行次数，即成功执行的平均次数为1/ps，服务执行一次的时间为t，那么，成功执行的平均时间st为：

st＝t/ps

通常，组合服务由基本组合模式构成，因此为了考虑事务组合服务的时间性能，我们需要分析基本组合模式的时间性能。这里，我们讨论四种基本的组合模式，分别是：序列，并行，选择和循环模式。并且服务组合由工作流模型来描述。TP表示事务性，TO表示一次执行时间，ST表示成功执行时间，PS表示成功执行概率。tp、to、st和ps表示组合服务相应概念的具体值。为了简单考虑，模式中每次只有一个组件服务执行失败。

(1)序列模式时间性能分析

序列模式用来定义组合服务由一系列按固定顺序执行的组件服，由n个组件服务组成的序列模式如图1所示。在序列模式中，组件服务从左到右执行，当且仅当前面的组件服务成功执行完成后，后面的组件服务才能开始执行。如果有组件服务执行失败，将利用事务机制处理失败。前i个组件服务成功执行时间为st_i，组件服务WS_i执行一次的时间为t_i，服务WS_i成功执行的概率为ps_i。

首先考虑两个服务组成的组合序列模式，n个服务组成的组合模式可以看作前n-1服务的组合服务和第n个服务的组合。

在序列模式中，如果第一个服务WS₁被赋予的事务特性为p或pr，根据定义4.3和4.6，WS₁一旦成功完成，就不能被撤销，因此第二个服务WS₂必须保证一定成功完成，即WS₂必须包括r的事务性，所以WS₂赋予事务性为pr或cr。{tp₁,tp₂}表示模式中从左到右或者从上到下的两个服务的事务性。

如果序列模式为{p,pr}或{p,cr}，执行一次该模式，如果WS₁执行失败，那么模式执行失败，时间为t₁。如果WS₁成功执行完成，由于WS₂经过有限次数重试必定成功完成，所以模式成功执行完成，时间为t₁+t₂/ps₂。那么在t₁+t₂/ps₂时间内，我们可以判断该模式是否成功执行完成，故to＝t₁+t₂/ps₂。WS₁成功执行完成概率为ps₁，由于WS₂经过有限次数重试必定成功完成，在模式执行过程中，我们认为事务性包含r的服务执行完成概率为1，即WS₂成功执行完成概率为1。所以该组合服务的成功执行概率为ps＝ps₁，组合服务的事务性为p。

如果WS₁执行失败,那么模式执行失败，为了分析该模式的成功完成时间，WS₁将重复执行，直到WS₁成功执行完成，那么模式成功完成。假设WS₁的成功执行完成时间为st₁(如果WS₁为原子服务，st₁＝t₁/ps₁，如果WS₁为组合服务，st₁为组合服务的成功完成时间)，由于WS₂经过有限次数重试必定成功完成，那么st＝st₁+t₂/ps₂。

如果序列模式为{pr,pr}或{pr,cr}，执行一次模式，WS₁和WS₂都经过有限次数重试必定成功完成，那么to＝t₁/ps₁+t₂/ps₂，执行一次时间也为成功执行完成时间，故st＝st₁+t₂/ps。WS₁和WS₂成功执行完成概率都为1，那么模式成功执行的概率为ps＝1，组合服务的事务性为pr。

在序列模式中，如果第一个服务WS₁赋予的事务性是c或cr，那么如果第二个服务WS₂执行失败，第一个服务执行可以被撤销，所以第二个服务WS₂可以赋予任何事务性。

在序列模式中，如果模式为{p,pr}或{p,cr}，那么，tp＝p，to＝t₁+t₂/ps₂，st＝st₁+t₂/ps₂，ps＝ps₁。如果序列模式为{pr,pr}或{pr,cr}，那么，tp＝pr，to＝t₁/ps₁+t₂/ps₂，st＝st₁+t₂/ps₂，ps＝1。

在序列模式中，如果模式为{c,p}或{c,c}，那么，tp＝p或c，to＝t₁+t₂，st＝(st₁+t₂)/ps₂，ps＝ps₁ps₂。如果序列模式为{c,pr}或{c,cr}，tp＝p或c，to＝t₁+t₂/ps₂，st＝st₁+t₂/ps₂，ps＝ps₁。如果序列模式为{cr,p}或{cr,c}，tp＝p或c，to＝t₁/ps₁+t₂，st＝(st₁+t₂)/ps₂，ps＝ps₂。如果序列模式为{cr,pr}或{cr,cr}，tp＝pr或cr，to＝t₁/ps₁+t₂/ps₂，st＝st₁+t₂/ps₂，ps＝1。

如果序列模式为{c,p}或{c,c}，执行一次该模式，如果WS₁执行失败，那么模式执行失败，时间为t₁。如果WS₁成功执行完成，WS₂执行一次，如果WS₂的执行失败，模式失败，如果WS₂的成功执行完成，模式成功执行完成，时间为t₁+t₂。所以在t₁+t₂时间内，我们可以判断模式是否成功执行完成，那么to＝t₁+t₂。

如果WS₁执行失败,那么模式执行失败，同样，重复执行WS₁，直到WS₁成功执行完成。假设WS₁的成功执行完成的时间为st₁，WS₂的执行失败会导致WS₁被补偿，并且回滚到模式的起点位置，那么也会导致模式执行失败。同样，重复执行WS₂，直到WS₂执行成功完成。WS₂每次失败都会导致WS₁和WS₂的重新执行一次，直到WS₁和WS₂都执行成功。那么服务WS₂经过k次执行后成功完成(即经过k-1次执行失败后成功)的时间为：k(st₁+t₂),概率为：

P(X＝k)＝(1-ps₂)^k-1ps₂

那么成功完成时间即数学期望为

WS₁和WS₂的成功执行完成的概率分别是ps₁和ps₂，那么模式成功执行完成概率为ps＝ps₁ps₂。如果模式为{c,p}，tp＝p。如果模式为{c,c}，tp＝c。

如果序列模式为{c,pr}或{c,cr}，那么WS₂经过有限次数重试一定能成功完成(定义4.3)，WS₁和WS₂的成功执行完成时间分别是st₁和t₂/ps₂，所以st＝st₁+t₂/ps₂。类似定理4.1中序列模式为{p,pr}和{p,cr}的证明，to＝t₁+t₂/ps₂，ps＝1。

如果序列模式为{cr,p}或{cr,c}，执行一次该模式，WS₁经过有限次重试必定成功完成(定义4.3)，WS₁的成功执行时间为st₁＝t₁/ps₁(虽然和以上讨论事务性为c的WS₁成功执行时间相同，但是原因不同)。WS₂执行一次，根据WS₂的执行结果，模式或者执行失败或者成功执行完成，时间为t₁/ps₁+t₂。所以在t₁/ps₁+t₂时间内，我们可以判断模式是否成功执行完成，那么to＝t₁/ps₁+t₂。类似序列模式为{c,p}或{c,c}的证明过程，st＝(st₁+t₂)/ps₂。WS₁和WS₂的成功执行完成的概率分别是1和ps₂，那么，ps＝ps₂。如果模式为{cr,p}，tp＝p。如果模式为{cr,c}，tp＝c。

如果序列模式为{cr,pr/cr}，类似序列模式{pr,pr/cr}的说明。

表1序列模式事务性赋值和时间性能分析

(2)并行模式时间性能计算方法

并行模式用来定义组合服务中组件服务没有严格执行顺序、必须同时进行的组合服务。其模式如图2所示。只有所有并行服务都成功执行完成时，这个组合服务才能成功执行完成。如果一些服务成功执行完成，另一些服务执行失败，那么需要利用事务机制对执行失败的服务进行处理。这里，max{x,y}表示x和y两者的最大值。min{x,y}表示x和y两者的最小值。假设在执行并行模式服务时，优先级为从上往下执行。我们首先考虑两个服务组成的并行模式。

在并行模式中，如果服务WS₁的事务性为p，一旦WS₁成功执行完成，它产生的影响不能被撤销，因此服务WS₂必须确保一定成功执行完成，即WS₂包含r的事务性。另一方面，一旦WS₁执行失败，WS₂必须能提供补偿策略，所以WS₂包含c的事务性，那么WS₂的事务性只能为cr。

当WS₁和WS₂同时执行时，由于WS₂的事务性为cr，WS₂能经过有限次数的调用确保成功执行完成，时间为t₂/ps₂。WS₁执行一次的时间为t₁。那么在时间max{t₁,t₂/ps₂}内，并行模式可以确定是否成功执行完成。所以，to＝max{t₁,t₂/ps₂}。WS₁的失败会导致WS₂被补偿，使得并行模式执行失败，所以我们重复执行该模式直到成功执行完成。WS₁经过k次执行后成功完成的概率为：

P(X＝k)＝(1-ps₁)^k-1ps₁

那么，成功执行时间为：

并行模式的执行成功完成的概率为WS₁和WS₂执行成功完成概率乘积，而WS₂的执行成功完成概率为1，那么，ps＝ps₁，tp＝p。

在并行模式中，如果一个服务WS₁的事务性为pr，WS₁经过有限次数的调用，一定能成功执行完成，而且成功完成后，其影响就不能被撤销(定义4.3)。所以另一个服务WS₂必须确保成功执行完成，即事务性必须包含r，那么服务WS₂的事务性为pr或cr。

在并行模式中，如果模式为{pr,pr}或{pr,cr}，那么，tp＝pr，to＝max{t₁/ps₁,t₂/ps₂}，st＝max{t₁/ps₁,t₂/ps₂}，ps＝1。

由于WS₁和WS₂的事务性都包含r，所以它们都能经过有限次重试确保成功执行完成，且执行一次的时间分别为t₁/ps₁和t₂/ps₂，而且执行一次的时间就是成功执行完成的时间，成功执行完成的概率都为1。所以在并行模式中，to＝max{t₁/ps₁,t₂/ps₂}，st＝max{t₁/ps₁,t₂/ps₂}，ps＝1，tp＝pr。

在并行模式中，如果一个服务WS₁的事务性为c，那么WS₁可能失败。所以另一个服务WS₂必须是可补偿的。即WS₂的是事务性包含c，那么，WS₂的事务性可以为c或cr^[64]。

在并行模式中，如果模式为为{c,cr}，tp＝c，to＝max{t₁,t₂/ps₂}，st＝max{t₁,t₂/ps₂}/ps₁，ps＝ps₁。如果并行模式为{c,c}，tp＝c，to＝max{t₁,t₂}，st＝max{t₁,t₂}/min{ps₁,ps₂}，ps＝ps₁ps₂。

如果并行模式为{c,cr}，证明类似，这里不再重述。如果并行模式为{c,c}，由于WS₁和WS₂分别执行一次的时间为t₁和t₂，故to＝max{t₁,t₂}，由于WS₁和WS₂都能提供补偿策略，当为某一个服务(该服务执行失败)提供补偿策略后，每次重新执行一次并行模式，实际上两个服务都被补偿了一次。那么补偿次数取决于需要被补偿次数更多的服务，也就是成功执行完成概率更小的服务。故st＝max{t₁,t₂}/min{ps₁,ps₂}。WS₁和WS₂成功执行完成的概率分别为ps₁和ps₂，故ps＝ps₁ps₂。根据定义4.4，tp＝c。

在并行模式中，如果一个服务WS₁的事务性为cr，根据定义4.2，经过有限调用WS₁能够确保成功完成。并且，当WS₂执行失败，WS₁是可补偿的。所以另一个服务的WS₂可以是任何事务性的服务。

如果并行模式为{cr,cr}，那么，tp＝cr，to＝max{t₁/ps₁,t₂/ps₂}，st＝max{t₁/ps₁,t₂/ps₂}，ps＝1。

由于并行模式中服务为对称的，并行模式{cr,p}，{cr,c}和{cr,pr}的公式可以参考定理4.3，4.4，4.5中给出的相应公式，这里不再复述。并行模式{cr,cr}的公式可以参考定理4.3中的模式{pr,pr}的证明。

基于两个服务的并行模式的事务性赋值和时间性能分析如表所示。

表2并行模式事务性赋值和时间性能分析

(3)选择模式时间性能分析

在本节中，我们考虑两种选择模式：一种是用来定义彼此之间相互制约与排斥关系的分支服务，这类分支服务往往根据具体的执行情况从多个分支选择一个分支执行，选择模式只有一个服务可以被执行。所以可以归结为序列模式的讨论。另外一种选择模式为任选其一的选择模式，分支服务是可以替代的，当某个分支执行失败后，选择另外一个分支替代，直到获得成功的分支，或者所有分支都失败，然后进行补偿，如图3所示。我们主要考虑第二种选择模式的时间性能分析。

假设在执行选择模式服务时，优先级为从上往下执行。我们首先考虑两个服务组成的选择模式。

在选择模式中，两个服务都赋予相同事务特性的服务，那么模式的事务性为组件服务相应的事务性，to＝(t₁+t₂)，st＝(t₁+t₂)/(ps₁+ps₂-2ps₁ps₂)，ps＝ps₁+ps₂-2ps₁ps₂。

在选择模式中，由于被选择服务都是完成同样功能的服务，所以，在本文中，为了简单起见，我们认为选择模式中服务赋予服务的事务性是对等的，也就是说，在选择模式中，服务只能赋予相同事务性的服务才能满足选择模式的物理含义。所以，两个服务赋予相同事务性的服务。在选择模式中，如果组件服务的事务性为p或c，那么如果WS₁成功执行完成，时间为t₁，如果WS₁执行失败，WS₂成功执行完成，时间为t₁+t₂，如果WS₁和WS₂都失败，并行模式失败，时间为t₁+t₂。那么在t₁+t₂，内可以判断并行模式是否成功执行完成，故to＝(t₁+t₂)。由于选择模式只有一个服务进入事务组合服务中，故不考虑单独服务的ST。第一个服务成功，模式成功，概率为，第一个服务失败，第二个服务成功的概率为(1-ps₁)ps₂，事务组合服务成功的概率为ps₁+(1-ps₁)p_s2＝ps₁+ps₂-ps₁ps₂，TCWS的事务性为p或c。组合服务选择模式的事务性赋值和时间性能分析如表3所示。如在选择模式中，如果组件服务的事务性为pr或cr，模式只需要执行第一个组件服务就可以使得模式成功执行完成，st＝to＝t₁/ps₁，ps＝1。

表3选择模式事务性赋值和时间性能分析

第三步中事务组合服务选择方法的具体内容如下：

本节主要研究基于事务和QoS的服务选择方法，并且考虑两个QoS指标：成功完成时间和执行价格，前者可以根据前面的时间性能分析算法获得，后者可以根据组合服务每个组件服务的执行价格之和获得。然后对两者进行加权处理，以获得事务组合服务的QoS分数值，并作为对事务组合服务进行选择的标准。由于本文使用的是标准的QoS属性，所以其它的QoS指标，比如：信誉，可获得性等，可以通过同样的方式扩展考虑。

(1)选择模型

在Web环境中，组合服务一般由其它服务或组合服务构成，包括三种组合模式：序列，并行，选择。随着越来越多功能性相似的服务被获得，最优的服务实例应该从中选择出来。目前，大部分工作都是基于QoS对服务进行选择。但是，为了确保组合服务可靠和正确的执行，服务组合需要事务的支持。于是，我们提出两种基于事务和QoS的服务选择模型。

第一种事务组合服务选择模型如图4所示，称为事务性确定服务选择模型。组合服务由工作流描述，合适的事务性已经被赋值给工作流中的所有活动。因此，候选服务已经由功能性和事务性要求确定。比如，根据功能性要求，活动A1有三个候选事务服务S11，S12和S13。根据事务性要求，只有S12和S13的事务性为c。因此，满足功能性和事务性两者要求的候选服务为S12和S13，然后根据QoS要求从两者中选择出最优的服务来执行活动A1。

然而，在基于事务的服务组合中，提供相似功能的候选服务可能具有不同的事务性。所以，第二种事务组合服务选择模型如图5所示，称为事务性未知选择模型。组合服务仍然由工作流描述。但是，工作流中活动的事务性是未知的，活动的事务性由被选择来执行该活动的候选服务的事务性决定。比如，根据功能性要求，活动A₁有三个候选事务服务S₁₁，S₁₂和S₁₃。如果活动A₁选择了候选服务S₁₁，那么活动的事务性为p，如果活动A₁选择了候选服务S₁₂或S₁₃，那么活动的事务性为c。根据功事务性和QoS要求，从三者中选择出最优的服务来执行活动A₁。

基于这两个选择模型，并结合目前较为常用的基于QoS的选择方法，本文提出了相应的全局最优选择算法。

(2)全局最优选择算法

在基于事务和QoS的组合服务选择模型中，事务的引入对组合服务的QoS时间性能产生了影响。因此，根据本地最优的时间指标选择最优的候选服务并没有考虑到事务对时间性能的影响。所以，本文使用全局最优方法来对服务进行选择。

首先，基于图4中的选择模型，工作流的事务性已经确定，即工作流的每个活动事务性为已知的，这里把事务性已知的工作流称之为事务工作流(Transactional Workflow，TWF)。假设事务工作流TWF中活动个数为n，TWF＝{a₁,a₂,…,a_n}。对事务工作流中的每个活动a_j，j＝1,2,…,n，有q_j个候选事务服务能执行活动a_j，该候选服务集合满足活动a_j的功能性和事务性要求。赋给每一个活动一个候选服务可以获得一个可执行的事务组合服务。那么，根据所有候选服务可以获得一个集合可执行的候选事务组合服务TCWS(Transactional>1,tcws₂,…,tcws_m}，m＝∏q_j，这里，j＝1,2,…,n。然后，使用全局选择算法从集合TCWS中选择最优的可执行事务组合服务。这里，目标函数为Score(tcws_i)，为每个可执行的事务组合服务使用简单的加权方法来计算整个可执行事务组合服务的QoS分数值。Score(tcws_i)＝∑_jw_jq_ij，其中w_j∈[0,1]，∑_jw_j＝1，i＝1,2,…,m，q_ij表示每个候选服务的两个QoS属性。具有最小Score值的可执行事务组合服务作为最优的选择，如果有几个可执行事务组合服务具有最小的Score值，那么随机选择一条来执行事务组合服务。基于事务工作流的全局最优选择算法(GlobalSelection>

第一步：根据每个活动的候选服务集合，获得所有满足组合服务要求的可执行事务组合服务集合(见行2到3)，

第二步，根据时间性能分析算法，获得每条可执行事务组合服务的成功完成时间，赋值给ST[i](见行5)，同时获得执行价格，赋值给EP[i](见行6)，根据加权处理，获得tcws[i]的Score值(见伪代码行7)。

第三步，对比所有可执行事务组合服务的Score值，选择Score最小的执行事务组合服务赋值给BestTCWS(见伪代码行9-11)。Score[i]为可执行事务组合的Score值。

在实际的事务组合服务选择过程中，图5中的选择模型更能满足服务提供者和服务使用者的需求。下面考虑基于图5中模型的选择算法。

基于图5的选择模型，有研究提出了一个基于本地的事务和QoS选择算法，由于对活动进行事务服务选择依赖于前面已经选择合适事务服务的事务特点，所以，全局选择方法不能被使用，只有本地最优的选择算法被给出。和前面讨论的一样，事务对QoS的影响并未被考虑。并且，本地最优选择是通过不考虑其他活动影响下，对单个服务进行选择，这个样选择的本地最优服务在全局上可能是次优。因此，为了考虑事务的影响，以及克服本地选择的局限性，基于图5中的选择模型给出全局选择算法。

根据前面给出的工作流事务性赋值方法，首先，我们可以对工作流模型进行事务性赋值，即只给工作流活动赋予合适的事务性，而暂时不选择合适的服务实例来执行活动。那么，我们可以获得一个集合的事务工作流TWF＝{twf₁,twf₂,…,twf_m}，既满足组合服务的功能性要求，又满足事务性要求。对每个事务工作流，可以使用上面给出的GST算法来获得全局最优的可执行事务组合服务，然后从这些最优的可执行事务组合服务集合中，再选择一个最优的事务组合服务来满足用户需求。基于工作流的全局最优选择算法(GlobalSelection>

第一步，根据事务性赋值方法，活动所有可行的事务工作流，然后把它们赋值给集合twf(见行1-3)。

第二步，对twf中每个事务工作流使用算法GST选择最优的事务组合服务，同时获得它们的Score值，并分别赋值给BestTcws和MiniScore。最后，从集合BestTcws中选择出最优的事务组合服务BestTCWS(见行6-13)。TempMiniScore是一个暂存事务组合服务Score值的变量。

(3)启发式选择算法

在全局最优选择算法GSW中，当工作流活动个数变得很大时，算法需要花费的时间可能变得难以接受。所以，我们需要在可接受的算法时间内，获得一个近似最优的事务组合服务来满足用户需求。算法GSW时间主要耗费在两个方面：第一，对工作流进行事务性赋值，获得所有可行的事务工作流。第二，对每个事务工作流通过算法GST获得最优可执行事务组合服务。所以，我们考虑从这两方面减少算法选择时间，提出了一个启发式选择算法。

通常，启发式评估函数用来评估并找到从当前结点到目标结点的合适路径。在我们的启发式算法中，启发式评估函数用来评估包含当前结点不同事务性的整个事务组合服务的Score值。基于启发式评估函数，我们首先选择当前活动的事务性，然后，从满足该事务性的候选服务中选择最优的服务来执行当前活动。

为了设计更好的启发式评估函数，我们必须尽可能地获得已知信息。根据前面工作流事务性赋值过程我们可知，在序列和并行模式中，如果当前活动的事务性赋值为p或pr，那么后面所有活动的事务性都必须为pr或cr。在并行模式中，如果当前活动的事务性赋值为c，那么，包含当前活动的并行模式其他所有分支的活动只能为c或cr。在选择模式中，分支活动的事务性和该模式中其他分支的事务性相同。这样我们就减少了工作流事务性赋值的时间。然后把确定了事务性的活动的所有候选服务的QoS平均值作为参考信息，获得包含当前活动确定事务性的事务组合服务的成功执行时间和执行价格，并加权处理获得Score值作为启发式评估函数的值。这样我们就减少了GST选择算法的时间。

这里，我们把启发式评估函数HEF分成三个部分，定义如下。

定义1：启发式评估函数并且：

(1)G₁(x)为当前活动的信息。

(2)G₂(x)为历史活动和根据当前活动事务性获知必须进入事务组合服务的候选服务信息。

(3)G₃(x)为未知事务性活动信息。

为了获得启发式评估函数，我们必须知道包含当前活动确定事务性的事务组合服务的成功完成时间和执行价格。这里，我们把工作流的所有活动分成四个部分：

第一部分为已经选择了合适事务服务的活动，被称之为历史信息。那么，这部分活动的成功完成时间和执行价格就作为G₂(x)中的部分信息。

第二部分为当前活动。如果当前活动确定了事务性，那么满足该事务性要求的所有候选服务的平均QoS值作为G₁(x)信息。

第三部分为根据当前活动事务性确定了事务性的后续活动。根据这些活动的事务性，那么满足该事务性要求的所有候选服务的平均QoS值作为G₂(x)的另一部分信息。

第四部分为事务性未知的活动。首先，枚举出所有可能的事务性赋值，再同样活动所有候选服务的平均QoS值。作为G₃(x)信息的包含的信息。

根据这四部分信息，我们可以通过获得包含当前活动的事务组合服务路径的成功执行时间和执行价格，然后加权处理得到启发式评估函数HEF。

启发式选择算法HSW(Heuristic Selection based on WF)过程为：考虑当前的活动，根据前面已经选择合适服务的事务特点，可以获得满足当前活动要求的事务特点集合tpset。如果当前活动选择事务性为p或pr的服务时，满足该事务要求的候选服务为G₁(x)信息。如果活动为选择模式的分支，该选择模式其余分支活动事务性也为p或pr，其余活动事务性为pr或cr。以上活动候选服务为G₂(x)信息，且没有G₃(x)信息。当前活动选择事务性为c的服务时，满足该事务要求的候选服务为G₁(x)信息。如果为选择模式的分支，该选择模式其余分支活动事务性也为c，如果在并行结构中，该并行模式其余分支活动事务性为c或cr，以上活动候选服务为G₂(x)信息。其余事务性未知的活动为G₃(x)信息。当前活动选择事务性为cr的服务时，满足该事务要求的候选服务为G₁(x)信息。如果为选择模式的分支，该选择模式其余分支活动事务性也为cr，为G₂(x)信息。否则后面活动都为未知，为G₃(x)的信息。比较每个事务特点的HEF，为当前活动选择一个事务性，并从满足该事务性的候选服务中选择最优的服务来执行当前活动。在下面的启发式算法中，TP表示前面已经选择合适服务的事务特点，TCWS表示选择的事务组合服务。