在面向服务的应用中,面对众多具有相同功能且服务质量(QoS)不同的候选服务,如何为应用工作流的每个任务选择并绑定一个服务,以达到在满足用户对组合服务QoS约束的基础上最优化组合服务的全局QoS,依然是基于QoS的Web服务选取问题的研究热点^[1].

当前研究多假定任务间相互独立,而忽略了任务间的状态关联关系^[2].在Web服务中,状态是一些不包含在请求消息中的信息片段^[3].实际工作流中的某些任务之间往往是状态关联的,它们彼此共享某些状态信息.为实现任务间的状态共享,要求以服务包含的操作为基本选取粒度,且具有状态关联关系的任务绑定的操作必须包含于同一服务,这种允许不同操作间共享状态信息的服务称作有状态服务(stateful service)^[4].目前对面向有状态服务的Web服务选取问题研究较少.文献^[4]研究了多个用户并发访问组合服务时的服务选取,通过在运行中限制共享状态任务集中后续任务的操作绑定关系保证有状态约束;文献^[5]将服务选取问题构建为一个混合整数规划问题,并将共享状态的任务绑定到相同服务作为最优化问题的一个约束.这些研究均采用线性规划进行求解,存在计算代价大、可扩展性差等不足.为了降低计算代价,可采用启发式算法求解,其中遗传算法已被证明是一种有效的Web服务选取方法^[6],然而面对选取问题中的有状态服务,现有遗传算法无法直接应用. 针对上述问题,本文提出了一种求解面向有状态服务的Web服务选取问题的遗传算法,其中定义了新的交叉操作和变异操作,使得每一代个体均满足任务之间的绑定约束,同时在适应度函数中引入了罚函数,以适应多个约束条件产生的复杂搜索超平面的情形.为了防止过早收敛,算法在选择操作之前增加了相似性判断过程,从而增加群体多样性.与线性规划方法相比,该算法具有全局搜索最优解的能力和良好的可扩展性.实验表明,本文的服务选取算法与现有遗传算法相比可以获得质量更好的解,同时在保证解的质量的基础上,其执行效率优于当前求解有状态服务选取的线性规划算法.

如图 1所示,任务T₁,T₂,...,T₇构成一个应用的工作流,任务的功能通过绑定某个操作(如op11,op31等)来实现,这些操作包含于不同服务,如S₁,S₃等.某些任务之间存在状态共享关系,如T₃,T₄与T₂,T₅,T₇分别共享不同状态.由于状态不包含在服务的请求消息中,为了实现状态共享,具有状态关联的任务绑定的操作必 须属于同一服务.服务S₃,S₆分别包含了实现其任务功能且共享状态的操作,称为有状态服务.

图 1(Figure 1)

Fig. 1

图1 面向有状态服务的服务选取问题示例 Fig. 1 An example of stateful service oriented selection

为便于描述,给出以下定义.

定义1 抽象组合服务(abstract composite service,简称ACS).ACS表示为一个二元组<T,SR>,其中,T={T_i|1≤i≤m,i∈ N }为任务集合,m是任务数量;SR={seq,loop,and,or},表示ACS包含的结构关系,即序列结构、循环结构、并行结构和选择结构^[4].

定义2 状态关联绑定约束(state-correlate binding constraints,简称SBC).对于ACS中的任意两个任务T_i,T_j,如果在实例化ACS时,要求二者绑定的操作必须属于同一服务且共享相同的状态,则称任务T_i,T_j之间存在状态关联绑定约束.

因此,面向有状态服务的Web服务选取问题的目标是,在满足给定的抽象组合服务端到端QoS约束和任务间状态关联绑定约束的基础上,找到所有任务与操作之间的最优绑定关系.

定义3 有状态任务(stateful task).对于ACS中的任意任务T_i,如果ACS中存在与具有状态关联绑定约束的任务,则称为有状态任务.

相应地,如果ACS中不存在与T_i具有状态关联绑定约束的任务,则称T_i为无状态任务.

根据状态共享关系的不同,可将抽象组合服务ACS中的全部有状态任务T_i(1≤i≤m)划分为多个互不相交的集合O₁,O₂,…,O_h,每个集合O_e中的元素共享相同的状态rpe,称O_e为状态rpe的有状态任务组.可知,任意O_i,O_j(i≠j)共享的状态都不同,即rpi≠rpj.在实际应用中,ACS的任务间状态关联关系通常是由工作流的设计人员确定的,因此与已有研究相同,本文假定状态关联绑定约束是已知的.

为了判断不同任务与操作绑定关系的优劣,需要确定用户关注的Web服务的QoS属性^[7],为简单起见且不失一般性,仅考虑3个常用QoS 属性:响应时间(response time)、可靠性(reliability) 以及服务费用(cost).其中,响应时间t_R为服务接受请求后,处理并返回结果所消耗的时间;可靠性R为一段时间内服务成功执行的概率;服务费用C为每次调用服务所产生的费用.

根据上述QoS属性,可以采用不同方法计算组合服务的QoS属性值^[1,4,8].对于任意服务,如果其中某一操作提供不同QoS等级,则根据QoS等级将其分解为多个功能相同的操作.下面给出面向有状态服务的Web服务选取问题的优化模型.

给定一个包含m个任务的ACS,有状态任务组的集合为O={O_e|1≤e≤h},任务T_i(1≤i≤m)的候选操作集合OP_i={op_i,1,op_i,2,…,op_i,ni},其中n_i表示候选操作数量，所有任务的候选操作所属的服务构成集合CS={s₁,s₂,…,s_M},用户u对组合服务的全局QoS约束为:最大响应时间不超过t_R,max^u,最小可靠性高于R_min^u,最大服务费用低于C_max^u.服务选取的目标是同时最优化响应时间、可靠性和服务费用.以x=(op_1,j1,op_1,j2,…,op_m,jm)表示可行解,则优化模型为

式(1)中,w₁,w₂,w₃分别表示用户给出的t_R,R,C的权重,且w₁+w₂+w₃=1；f₁,f₂,f₃分别为t_R(x),R(x)和C(x)标准化后的值.式(2)~式(4)分别表示可行解x满足响应时间、可靠性和服务费用的全局约束.式(5)表示任务状态关联绑定约束,其中ω(op_i,ji),ω(op_k,jk)分别是指操作op_i,ji,op_k,jk所属的服务,其意义是,对于属于同一有状态任务组O_e的任意两个任务T_i,T_k,它们绑定的操作op_i,ji和op_k,jk所属的服务是相同的,且二者共享相同的状态rp_e.

提出了一种求解面向有状态服务选取问题的遗传算法(stateful service oriented selection genetic algorithm,简称SSOSGA).

针对任务状态关联绑定约束,SSOSGA在个体编码中要求有状态任务组中任务对应的基因位取值所属的服务相同.同时,需要在交叉操作中确定可用的交叉点,并在变异操作中要对有状态任务组的基因位同时变异,使得交叉和变异产生的新个体均属于可行解空间,进而提高求解效率.

为了降低在解空间中无对应可行解的个体的适应度,使其遗传到下一代群体中的概率减小^[9],在SSOSGA中采用包含罚函数的个体评价策略.与此同时, 采用相似性判断^[10]增加群体多样性和高适应度值个体的主导地位以防止SSOSGA 过早收敛.

1) 个体编码.SSOSGA中的个体采用符号编码方式,个体长度为ACS的任务数m.将基因位按照共享状态的类型分组,每个基因位的序号G_i与ACS中的某个任务T_j具有对应关系,T_j=Ω(G_i),且第i个基因位的取值范围是[1,m_i],其中m_i为第i个基因位对应任务的候选操作个数,而且每个有状态任务组对应的基因位取值所属的服务相同.图 2给出了个体编码示意图.

图 2(Figure 2)

Fig. 2

图2 个体编码 Fig. 2 Individual encoding

2) 交叉操作.交叉操作采用两点交叉,但限制了交叉点的取值范围以满足任务状态关联绑定约束.首先,根据交叉概率随机选择个体对.然后,确定可用交叉点,包括:①个体中不同任务组的分割点;②无状态任务基因位的分割点;③绑定操作属于同一服务的有状态任务组基因位的分割点.最后,在所有可用交叉点中随机选择两个交叉点进行交叉操作.

3) 变异操作.变异操作中所有基因位都是可变异的.对于无状态任务,基因位变异后成为新的个体;对于任意有状态任务T_i∈O_e,如果第i个基因位变异后的值op_i,k所属的服务s_l与变异前相同,则将其作为新的个体;否则,将∀T_j∈O_e(j≠i)绑定的服务替换成s_l,并将T_j的基因位的值替换成s_l中的某个功能等价的操作,当s_l中存在多个功能等价的操作能够实现T_j时,随机从这些操作中选择一个作为其基因位的值.

4) 个体评价策略.为了评价解的质量,定义适应度函数如下:

SSOSGA采用随机遍历抽样选择个体,该方法是轮盘赌选择法的一种改进,其特点是只需一次轮盘旋转,可避免早期的高适应度个体迅速占据种群.另外,以离线性能评估准则作为算法终止条件^[11].设第T次迭代的离线性能为X(T),则对于给定阈值σ,当X(T)-X(T-1)≤σ时,终止搜索.同时,为了避免搜索时间过长,设定一个最大遗传代数.

5) 算法描述.

算法1 面向有状态服务选取的遗传算法(SOSGA)

输入:ACS,有状态服务组集合及候选服务集.

输出:所有任务与候选操作的最优绑定关系.

1) 根据任务关联状态绑定约束过滤所有有状态任务的候选服务集合;

2) 随机产生包含M个个体的初始种群P(0);

3) while X(T)-X(T-1)≤σ or T≤T_max do ;

4) 计算适应度函数Fit(x);

5) 采用随机遍历抽样选择个体;

6) 通过修改的两点交叉操作生成新的个体;

7) 通过修改的变异操作生成新的个体;

8) 评价个体间相似度;

9) 计算离线性能X(T+1);

10) T++;

11) end while

12) 将最优个体解码为最优解EP^*;

13) return.

硬件环境:CPU i5 M560 2.67GHz,内存6.0GB;软件环境:Windows 7 Ultimate操作系统,JDK 1.6.7.

实验采用一定规则随机生成工作流,任务数量m取值范围为10~50, T_i的候选操作数量n_i取值范围为20~100,且所有有状态任务组的大小均为5.实验假定操作的响应时间、可靠性和费用等QoS属性权重相等,三者的值分别在一定的区间内以随机方式生成,响应时间区间为0~10s,可靠性区间为0.7~1.0,费用区间为1~10,并且根据文献^[4]中的标记树递归规则计算组合服务QoS.

根据遗传算法参数的常用取值范围^[9], SSOSGA主要参数:种群大小P=50,交叉概率P_c=0.75,变异概率P_m=0.06,阈值σ=1.0×10^-5,最大迭代数 T_max=100.

以图 1中的问题示例为实验对象,每个任务的候选操作数量为50,与未采用罚函数的适应度函数相比较得到结果如图 3所示.由图 3可知,当未在适应度函数中引入罚函数时,种群的平均适应度明显要低一些,更容易收敛到局部最优.这是因为部分不满足多个约束条件的无可行解的个体被遗传到下一代,进而影响了收敛速度.

图 3(Figure 3)

Fig. 3

图3 SSOSGA的收敛性 Fig. 3 Convergence of SSOSGA

为了验证SSOSGA的有效性和性能开销,将其与不考虑有状态服务的遗传算法和线性规划算法(MOSES)^[4]进行组合服务QoS及算法消耗时间方面的对比.这里,不考虑有状态服务的遗传算法是指在SSOSGA中采用基本遗传算法的交叉和变异操作,并且取消个体编码规则中对有状态任务组基因位取值的限制,将其称为改进的服务选取遗传算法(improved service selection genetic algorithm,简称ISSGA).

1) 组合服务的QoS.对于不同的m,n_i组合,有状态任务组的个数固定在[m/2],得到组合服务的QoS如表 1所示.由表 1可知,对于m,n_i的不同组合,SSOSGA得到的组合服务QoS略低于MOSES,这是因为线性规划算法通常能够更容易获得最优解.但与ISSGA相比,SSOSGA使得每一代个体均满足任务状态关联绑定约束,因此能够更快地得到质量更好的解.

表1

Table 1

表1(Table 1)

表1 组合服务的QoS Table 1 QoS of composite services m ni SSOSGA ISSGA MOSES 10 50 0.754 0.631 0.797 20 50 0.834 0.710 0.853 30 50 0.793 0.668 0.822 40 50 0.801 0.670 0.849 50 50 0.734 0.655 0.761 25 20 0.772 0.678 0.800 25 40 0.753 0.640 0.794 25 60 0.784 0.665 0.805 25 80 0.730 0.578 0.748 25 100 0.693 0.537 0.724

表1 组合服务的QoS Table 1 QoS of composite services

2) 服务选取消耗的时间.与1)相同,改变m和n_i时,有状态任务组的个数固定[m/2],其结果如图 4,图 5所示.

图 4(Figure 4)

Fig. 4

图4 任务数量对计算时间的影响 Fig. 4 Impact of the number of tasks on solving time

图 5(Figure 5)

Fig. 5

图5 候选操作数量对计算时间的影响 Fig. 5 Impact of the number of candidate operations on solving time

由图可知,3种算法的计算时间均随着任务数量和候选操作数量的增加而增加,当任务或候选操作较少时,SSOSGA的计算时间略高于MOSES,但当任务或候选操作较多时,MOSES的计算时间迅速增加,并超过了前者.

1) 在适应度函数中引入罚函数能够有效提高SSOSGA的收敛速度,并且更可能获得最优解;

2) SSOSGA求得的解能够在满足全局QoS约束的前提下近似线性规划得到最优解;

3) 与采用线性规划的方法相比,SSOSGA在面对较大的问题规模时, 能够在更短的时间内得到最优解;同时,解的质量明显优于现有遗传算法.

本文针对工作流中多个任务之间存在状态关联的组合服务选取问题,提出了一种考虑状态关联绑定约束的Web服务选取方法的遗传算法.对比实验表明,本文的服务选取算法能够在令人满意的时间内收敛到最优解,并且在保证解的质量的基础上,其执行效率在一定程度上优于已有算法.