组合服务的重选取是指重新选取某些服务绑定受到失效影响的任务流程片段，一方面这些服务需要满足任务描述的功能和接口结构等要求，另一方面重新选取出的服务不能偏离用户设定的约束.文献^{[1, 2, 3]}在重选取的过程中假定工作流中的任务是相互独立的，每个任务绑定的服务与其他任务无关.然而在实际的执行过程中普遍存在着一个场景：考虑一个订购机票旅行的计划，中国航空与假日酒店之间具有合作伙伴关系，选择假日酒店的情况下，中国航空可以提供打折的机票.因此为了获得优惠的价格，订票任务的选取结果决定了酒店预订任务的选取结果，进而使得两个任务之间具有关联关系.以任务间互相独立的方式考虑组合服务的重选取无法获得服务间的关联QoS，进而降低了重选取的质量.文献^{[4, 5, 6, 7]}给出了服务间关联关系的具体定义及相应的处理方法，但没有给出一个清晰的服务间关联关系的描述和声明，难以将服务间的关联关系应用于组合服务的选取或重选取.

为了解决该问题，本文通过扩展OWL-S，给出了一个描述关联服务QoS的模型，使得在选取或重选取过程中能够有效地刻画服务间关联关系对QoS的影响.基于该模型，给出了一个支持服务间关联关系的重选取算法.

基于OWL-S^[8]，本文给出了一个表述不同类型QoS的模型，如图 1所示.通过扩展Profile描述了Web服务的两类QoS.Profile,Parameter与Condition是OWL-S中的初始类，QoS,DefaultQoS与CorrelatedQoS是本文扩展的类， 其中DefaultQoS表示默认的QoS，CorrelatedQoS表示关联QoS.QoS是DefaultQoS与CorrelatedQoS的超类，它具有3个数据类型的属性：hasCost,hasResponseTime与hasReliability分别描述具体的价格、响应时间与可靠性.同时添加了一个对象属性dependents，把类CorrelatedQoS与Condition联系在一起，其表示的语义为CorrelatedQoS依赖条件Condition.

图 1(Figure 1)

Fig. 1

图1 扩展OWL-S Profile得到关联QoS Fig. 1 Correlated QoS described by extension OWL-S Profile

设qⁱ表示Web服务的某一个QoS属性，当i取不同的值时，qⁱ就表示不同的QoS属性，它可以表示为价格、响应时间、可靠性等.那么具有QoS关联关系的服务定义如下.

定义1 具有QoS关联关系的服务. 给定一组服务GWS={s₁,s₂,…,s_k}，当这些服务一起使用时，存在某些服务{s_a,s_a+1,…,s_a+j}GWS，它们的质量属性qⁱ受到GWS中其他服务的影响，则称GWS包含的服务之间具有QoS关联关系.

某一个任务t对应的备选服务s的质量属性qⁱ的值可以表示为 sv(s,qⁱ)={(v₁,c₁),(v₂,c₂),…,(v_m,c_m)} 式中，(v_u,c_u)表示满足条件c_u的情况下，服务s的质量属性qⁱ的值为v_u.本文利用表达式selected(t_u)∈S_u表示选择备选服务集S_u中的服务绑定任务t_u.因此条件c_u可以形式化地表示为selected(t_u)∈S_u ∧selected(t_u+1)∈S_u+1∧…∧selected(t_u+k)∈S_u+k，其中t_u,t_u+1,…,t_u+k表示与t具有关联关系的任务，S_u,…,S_u+k表示与服务s具有关联关系的备选服务的集合，符号∧表示逻辑“与”操作.由于服务s不能为质量属性qⁱ同时提供2个不同的值，因此在选取过程中只能满足某一个条件.

进一步，令等式a_u=1表示表达式selected(t_u) ∈S_u，a_u=0表示表达式selected(t_u)∉S_u(任务t_u没有绑定服务集S_u中的服务).条件c_u的真值表如表 1所示，只有当变量a_u,a_u+1,…,a_u+k的值都为1时，c_u的值才能为“真”(逻辑“与”操作).因此条件c_u还可以表示为a_u=1∧a_u+1=1∧…∧a_u+k=1，此时服务s的质量属性qⁱ的值为v_u.

表1

Table 1

表1(Table 1)

表1 条件cu的真值表 Table 1 Truth table of condition cu 条件cu au au+1 … au+k 满足cu 1 1 … 1 不满足cu other cases

表1 条件cu的真值表 Table 1 Truth table of condition cu

在组合服务流程中包含循环控制结构，可以通过循环展开等技术^[9]将循环控制结构展开为顺序控制结构.经过处理后，组合服务流程可以建模为有向图模型.设工作流程包含P个执行路径，每个执行路径不包含分支控制结构.执行概率freq_p(p∈P)是某一个分支路径的概率.T_p表示执行路径p包含的任务集.路径p的子路径可以表示为sp，它不包含并行控制结构.组合服务的聚合函数可以表示为

在组合服务CS中，具有关联关系服务的QoS会受到其他服务的影响，因此在提取质量属性qⁿ的真实值时，需要检测当前的绑定关系是否满足服务条件.一个服务s的属性qⁿ的值可以表示为sv(s,qⁿ)={(v₁,c₁),(v₂,c₂),…,(v_m,c_m)}，且selected(t_i)∈S_i表示绑定任务t_i的服务来自于服务集S_i.同时，参数x_ij表达了服务s_j与任务t_i之间的绑定关系，若x_ij=1，则表示服务s_j绑定了任务t_i.如果s_j∈S_i，那么x_ij=1与等式a_i=1表达的意义相同.设S_i={s_j,s_j+1,… ,s_j+u}，由于任务t_i在一次选取过程中只能绑定S_i中的一个服务，所以∑_{j∈{j,…,j+u}}x_ij的值只能为1或者0，因而参数a_i = ∑_{j∈{j,…,j+u}}x_ij.

如果条件c_i为a_i=1∧a_i+1=1∧…∧a_i+d=1，意味着参数a_i,a_i+1,…,a_i+d的值全部为1的情况下才能满足条件c_i.因此c_i就可以表示为∏_{i∈{i,…,i+d}ai}，则服务s的质量属性qⁿ的值可以表示为

当质量属性qⁿ的值相对于阈值Δqⁿ发生较大变化时，会导致违反用户的约束^[2].在进行重选取前，首先需要确定执行异常的组合服务的剩余任务流程.文献^[1]给出了一个确定剩余任务流程的方法，利用该方法可以获得成功执行的服务，剔除不可能再执行的分支，并更新循环控制结构的迭代次数.本文的重点是在考虑任务间关联关系的情况下，如何对剩余任务流程进行重选取.

考虑任务间关联关系的情况下，某些已经完成的任务可能会影响未执行任务与具体服务的绑定关系.如图 2所示，任务t₁,t₂与t₃属于已经完成的任务，并且t₃,t₄,t₅是一组具体有关联关系的任务.对任务t₄和t₅选取服务时，首先需要考虑的是与服务s₃₂(绑定任务t₃的服务)具有QoS关联关系的服务.如果与s₃₂具有关联关系的服务实例无法满足用户的要求也需要重新对任务t₃进行重选取.

图 2(Figure 2)

Fig. 2

图2 尚未执行的任务与已经完成的任务间的关联关系 Fig. 2 Correlations between completed tasks and unexecuted tasks

组合服务剩余任务流程主要分为3类任务：①独立于其他任务；②具有关联关系的任务，并且不受已经完成任务的影响；③与已经完成的任务具有关联关系的任务.支持关联关系的重选取算法的步骤如下.

1) 更新服务组合模型的参数：已经完成的任务集为completed_tasks={t₁,t₂,…,t_u}，绑定这些任务的服务为executed_services= {s₁,s₂,…,s_u}，再把表示completed_tasks与executed_services之间绑定关系的参数x₁,x₂,…,x_u的值都设置为1.将集合executed_services包含的服务在实际执行过程中的价格与响应时间代入服务组合模型，并把这些服务在组合模型中对应的可靠性设置为1.

2) 确定第②类任务的备选服务集：设一组关联任务集 为correlated_tasks={t_i,t_i+1,…,t_i+d}，它对应的具有QoS关联关系的备选服务集为cs_set={cs₁,cs₂,…,cs_m}，其中，元素cs_j∈cs_set是一组具有关联关系的备选服务.任务集cc_tasks= {t_i,t_i+1,…,t_i+l}⊂correlated_tasks(l<d)是一组已经完成的任务，绑定cc_tasks的Web服务为completed_cs ={s_i,s_i+1,…,s_i+l}.然后对于任意一组关联服务cs_j∈cs_set，如果满足条件c：completed_cs⊂cs_j，则进行操作cans_k= cs_j-completed_cs.并将cans_k并入集合canss，直到不存在满足条件c的关联服务为止，那么服务集合canss则是第②类任务首先考虑的备选服务集.如果canss包含的服务无法满足要求，则需要对correlated_tasks包含的所有任务进行重选取.

3) 将以上两步得到结果代入第2节的服务组合模型，利用0-1规划算法得到重选取的结果，0-1规划算法的求解过程不再陈述.

比较考虑了关联服务的重选取方法(简称为服务关联的重选取)与认为服务间互相独立的重选取方法^[1](服务独立的重选取)的效率与效果.由于真实运行场景难以模拟，因此本文采用仿真数据生成的方法进行模拟.

本实验运行的PC硬件配置为 Intel(R) Core i5 CPU 3.3GHz，4GRAM.软件环境采用了Windows7操作系统，JDK 1.7，Eclipse.本文设定了8个任务，组成一个流程，并随机生成每个任务对应的具体服务的价格、响应时间和可靠性.

再从该任务流程中取4个子任务，并为这些任务选择一定比例的具体服务作为支持QoS关联关系的备选服务.生成关联服务QoS的方式：设定服务之间的关联因子μ∈{0.2,0.3,0.4}，μ代表每2个服务之间的QoS关联程度.如果μ的值为0.3，它表示关联服务同时调用时，它们的价格在默认发布值的基础上减少30 % ，可靠性提高30 % (且不能超过100 % )，响应时间也减少30 % ，μ的值可以通过随机的方式确定.这两组任务对应的关联服务的比例是可以调整的，初始设定为50 % .

对于考虑了关联关系的重选取方法则使用服务间的关联QoS，没有考虑任务间关联关系的方法则使用默认的QoS.本文假定第二个任务出现了异常，然后对剩余的任务进行重选取.

首先设定每个任务对应的候选服务不变，调整关联服务的比例，比较2种方式的处理效率.执行结果如图 3所示，在进行测试时重复选取6次，计算重选取的平均执行时间.

图 3(Figure 3)

Fig. 3

图3 关联比例对执行时间的影响 Fig. 3 Effect of correlation proportion on execution time

由图 3可以看出服务独立的重选取方法执行效率与关联服务的比例变化并没有关系.这是因为该方法并没有考虑任务之间的关联关系，所以它的执行效率没有较大的波动.服务关联的重选取方法执行效率开始时呈上升的趋势，随后随着关联服务比例上升开始下降.这是因为关联服务的比例比较小的情况下，关联服务的可选范围也比较少，很多情况下难以满足QoS需求.此时还要搜索整个服务空间中的备选服务，这种情况下该方法的执行时间必然较长.当关联服务的比例上升时，服务关联的重选取方法大部分情况下可以通过搜索具有关联关系的服务满足QoS需求，此时无需再搜索整个服务空间中的服务，因此它的执行时间低于服务独立的重选取方法.然而随着关联服务的比例逐步升高，服务关联重选取方法的效率也在降低，这是因为其搜索空间的范围在逐步增加.

图 4将关联比例固定为60 % ，通过增加候选服务的方式比较2种算法的执行效率.由图 4可以看出，2种方法随着备选服务个数的增加，选取的效率就越低.因为服务关联的重选取方法是以关联服务作为相关任务的备选服务集，所以减少备选服务的个数，其效率优于服务独立的重选取方法.

图 4(Figure 4)

Fig. 4

图4 候选服务数对执行时间的影响 Fig. 4 Effect of candidate services number on execution time

图 5为关联服务比例对2种算法调整结果质量的影响.固定备选服务的个数为70，然后调整备选服务中关联服务的比例，计算不同比例下组合服务的QoS.

图 5(Figure 5)

Fig. 5

图5 关联服务比例对重选取质量的影响 Fig. 5 Effect of correlation proportion on reselection quality

由图 5可知，由于备选服务固定不变，因此服务独立的重选取方法获得的QoS也没有变化，该方法不受关联服务比例的影响.随着关联服务比例的提高，关联服务的QoS范围变大，因此服务关联的重选取方法获得的QoS逐渐变大.当关联服务比例比较低时，服务关联的重选取方法利用关联服务得到的QoS优势并不明显.只有当关联服务的比例逐步提高时，服务关联的重选取方法获得的QoS也逐步提高.

图 6将关联服务比例固定为60 % ，逐步增加候选服务的个数，对比了服务关联与服务独立的重选取方法获得的QoS与候选服务个数的关系.由图 6可知，随着候选服务个数的增加，服务独立的重选取方法的QoS逐步提高.另一方面，虽然关联服务的比例固定不变，而随着候选服务数量的增加，关联服务的数量也在增加，因此考虑关联关系的方法重新选取出的组合服务的QoS也在提高.在关联服务的数量逐渐增多的情况下，关联服务的重选取方法选取出的组合服务的质量优于服务独立的重选取方法.

图 6(Figure 6)

Fig. 6

图6 候选服务个数对重选取质量的影响 Fig. 6 Effect of candidate services number on reselection quality

从上述实验可以看出，由于关联任务的备选 服务集限定为具有QoS关联关系的服务，减少了备选服务的个数，因此在执行时间上优于假定任务独立的重选取方法.同时，考虑任务间关联关系的重选取方法，以服务的关联QoS为选取基础可以获得更好的质量.

本文通过扩展OWL-S描述了服务间的关联QoS，并在此基础上，给出了一个支持任务间关联关系的组合服务重选取算法.与假定任务间独立的重选取算法相比，本文的方法可以获得较高的质量.在一定程度上减少了备选服务的范围，提高了组合服务重选取的效率.