服务因其具有松耦合、与平台无关等特性,在当今开放的网络环境中得以快速发展,各种面向服务的应用大量涌现.随着服务应用规模的日益扩大,单个服务已经难以满足用户的需求.在众多功能相同但具有不同非功能属性(如QoS属性)的服务中选择满足用户需求的优质服务参与服务组合,已经成为研究的热点.

然而,组合服务的执行通常处于面向多个并发用户的动态环境之中,这种环境常常会导致服务质量的降级或服务组合的失败^{[1, 2]}.在这种动态环境中进行基于QoS的服务选择与组合需要面临诸多挑战,而动态的服务负载就是其中之一^{[3, 4]}.当前的服务选择方法大多面向单个用户需求,以优化基于QoS的组合服务效用为目标.因而,当短期内有大量的用户请求到达时,优质的服务常常会频繁地被选择,以至于发生过载或导致短时间内的服务质量降级(如响应时间延长等),甚至拒绝用户的请求.例如,基于skyline的服务选择方法^[5]认为:选择具有较优QoS的 服务参与组合,一定优于具有较劣QoS的服务.而事实上,这些优质服务可能因为被较多用户选择而使其短期内的实际性能表现并不优于具有较劣QoS的服务.因此,为了达成满足用户QoS需求的服务组合目标,在构建一个组合服务时,服务选择必须要考虑到其他用户的服务选择行为对自身服务选择造成的影响,即动态负载因素对服务选择的影响.更进一步讲,服务选择方法应该具备应对这种变化的能力.因此,在开放的、面向多用户的动态服务负载环境下,研究满足用户QoS需求的组合服务动态选择优化问题将更具有现实意义.

具体地讲,当前的研究存在两个方面的不足:

· 一方面,针对多个用户需求的服务选择与组合研究较少^[6].大多工作是针对单个用户需求的研究,而服务运行的实际环境通常是开放的、面向多用户和多业务的(即多个组合服务),这种实际的运行环境会导致服务负载发生动态变化;

· 另一方面,已有的相关服务选择方法难以适应动态变化的服务负载.大多数服务选择方法^[1,5,7-14]在组合服务设计规划阶段就确定服务选择方案.事实上,在组合服务设计规划阶段的服务状态(例如负载),可能不同于该服务被执行时的状态.对于单个用户请求(或需求)而言,这类方法生成的服务组合方案难以根据组合服务执行阶段动态变化的服务负载进行动态调整,容易造成服务过载或组合服务性能下降,缺乏实时感知负载的应变能力.

为弥补上述不足,本文将服务选择过程划分为两个阶段(即:组合服务选择设计阶段和组合服务选择执行阶段),并提出了一种负载感知的动态服务选择模型(load-aware dynamic service selection model,简称LADSSM).该模型在组合服务规划阶段实现候选服务队列的生成;在组合服务执行阶段,依据当前负载实现服务的动态选择.该模型在满足用户端到端QoS的前提下,能够实时感知服务负载并进行服务的动态选择,最终实现优化的服务组合,从而弥补了当前服务选择方法的不足.

本文主要贡献可以归纳为3点:

(1) 提出了一种基于负载等级的多维QoS模型(load level based multidimensional QoS,简称LLBMQoS);

(2) 在此基础上,提出了一种负载感知的动态服务选择模型;

(3) 提出了实现该模型优化的关键算法.

本文第1节介绍相关工作.第2节提出基本问题的场景.第3节提出一种基于负载等级的多维QoS模型.第4节详细阐述负载感知的动态服务选择模型,包括模型的基本组成结构、数学模型和关键算法.第5节进行仿真实验,并分析比较实验结果.第6节做出总结并提出下一步研究方向.

1 相关工作

文献^[1]采用全局优化方法发现全局最优的组合服务,该方法对服务组合问题建立整数规划模型,实现了服务的优化选择;文献^[5]对具有不同QoS的候选服务进行筛选,选出skyline service参与组合服务选择,这样极大地减少了候选服务的数量,提高了选择方法的效率;文献^[7]针对工作流下的服务选择问题,构建了MMKP (multidimensional multiple-choice knapsack)模型和MCOP(multi-constrained optimal path)模型,并提出了启发式算法,从而实现了基于全局的服务优化选择;文献^[8]综合了全局和局部选择的优势实现了一种混合选择方法,将全 局QoS约束分解为局部约束,在局部选择中考虑全局因素,在实现服务优化选择的同时,显著降低了服务选择的开销;文献^[9]在文献^[5]的基础上,研究了动态服务环境下基于skyline service的服务选择问题,提出了动态环境下skyline service的筛选算法;文献^[10]分析了多种工作流模式下的QoS聚合,提出了一种优化的服务选择算法,该算法主要分为两个阶段:第1阶段在局部根据设定的阈值排除一些候选服务,第2阶段根据分支定界法生成全局优化的结果;文献^[11]提出了一种基于全局QoS约束分解的动态服务选择方法,该方法基于模糊逻辑的自适应调整方法和自适应粒子群优化算法,将全局QoS约束自适应地分解为满足用户偏好的局部约束,然后再进行局部优化选择;文献^[12]将服务选择全局优化问题转化为一个带约束条件的多目标服务组合优化问题,提出一种基于多目标遗传算法的QoS全局优化选择方法,最终产生一组满足约束条件的非劣服务聚合流程集;文献^[13]将服务组合模型建立在线性规划的基础上,引入QoS协商机制发现可行路径,并进一步优化了服务选择;文献^[14]对候选服务事先按照一定规则进行筛选,通过预先筛选,减少了可供选择的服务数量,再采用基于全局优化的线性规划方法生成最终的组合方案.在上述研究中,各服务组合过程独立地进行选择优化,< s pan="" style='font-family:宋体'>优质的服务会被多个组合服务选中,从而在这些服务节点可能出现过载,导致服务组合性能降级或失败.而失败后,无论采用重规划的方法还是使用备份服务的方法,都无法保证新生成的组合服务不会发生上面提到的问题.因而,以上的方法无法适用于多用户的动态负载环境.

文献^[15]在服务选择中引入信任,提出了基于蚁群算法的服务动态选择算法,在组合规划中避免所有组合服务的执行都经过同一条路径.但该研究未考虑单个服务节点上的负载变化,因而难以保证单个节点上不发生过载和性能的下降;文献^[16]研究了基于per-flow的优化组合问题,在预测用户任务到达速率的基础上,对多个组合服务选择方案统一进行规划,但对于同一个流中的用户请求该文献仅考虑固定统一的全局QoS约束,未考虑用户QoS需求的多样性;文献^[6]研究了满足多个用户需求的服务组合问题,对多个用户需求进行可满足性折中优化;文献^[17]针对多个用户请求提出了基于整数规划的服务选择优化方法;文献^[18]以非合作博弈的方法来解 决多用户的服务选择优化问题.以上研究的不足之处在于:一是采用离线方式进行优化,假设事先就能够获取所有用户请求信息,而在某些实际应用中用户请求的到达具有随机性和突发性,难以提前获得,因而需要采用在线优化的方式加以解决;二是在服务组合的规划阶段就生成确定不变的服务选择方案,这种方式难以适应在开放的、多用户、多业务环境下组合服务执行时的负载动态变化.

此外,在服务负载均衡方面,文献^[19]按照不同的概率在多个服务中选择一个服务来执行请求,以实现系统的总体平均响应时间最小;文献^[20]针对服务覆盖网络中服务选择和负载均衡问题,通过对候选服务的负载状况进行测算,从而建立一条适当的组合服务路径,实现了多个服务副本之间的负载均衡.然而,以上研究均未考虑用户端到端的多维QoS需求.

2 基本问题场景

一个用户需求通常可划分为多个任务,例如,一个旅游规划需求包括了天气查询、预订机票等任务.假设一个用户需求由一组任务T₁,…,T_n组成,并且一个任务T_j(1≤j≤n)存在一组服务可以完成,这些服务具有相同功能属性和不同的QoS.它们组成的集合表示为服务类S_j,S_j={s_1j,…,s_mj}.可见,实体服务s_ij(1≤i≤m)是服务类S_j的一个成员,表示一个具体服务或服务类S_j的实例.

定义1(虚拟组合服务流程VCSF(virtual composite service flow)). 是由一组服务类构成并且各服务类之间具有明确拓扑关系的组合流程模板.VCSF可以用DAG(directed acyclic graph)图来表示,通过组合不同的服务类,可以实现更加复杂的业务功能.

定义2(服务负载l_ij). 表示服务s_ij当前并发处理的用户请求数量.一个服务可以承受的最大并发请求数量(即最大负载)表示为.当并发请求数量超过最大负载时,服务将无法工作或者拒绝部分请求.

一个用户请求(或需求)由两部分组成:一是虚拟组合服务流程VCSF(即功能性需求);另一个是用户端到端的QoS需求(即非功能性需求).在多用户的应用环境中,用户的需求是多样的,这表现在两个方面:一是功能需求的多样化,这意味着开放的服务运行环境存在着多个VCSF,并且这些VCSF在某些任务节点可能相交;二是QoS需求的多样化,这意味着不同的用户有着不同的QoS需求.图 1描述了这样一个应用场景,存在两类有不同功能需求的用户:一类需求是旅游规划,对应于VCSF:S₁®S₃®S₄;另一类是会议规划,对应于VCSF:S₂®S₃®S₅.两类VCSF存在一个交集S₃.以往的服务选择大多不考虑多个用户需求,而在图 1所示的多VCSF场景中,由于存在交集& lt; /span>S₃,考虑到服务的负载因素,对一个VCSF的服务选择可能会影响到另一个VCSF的服务选择;并且在同一个VCSF中,针对一个用户请求的服务选择也会影响另一个用户请求的服务选择结果.此外,在开放的、多用户的服务环境中,用户请求到达难以提前预知,因此需要以在线的方式加以优化处理.

本文所讨论的问题可以描述为:根据依次到达的在线用户请求(即多种VCSF和端到端的QoS约束),在感知服务负载的基础上实现在线优化服务选择.为了便于描述和理解,本文给出如下假设:

假设1. 在一个虚拟组合服务流程VCSF中,共有n个服务类S_j(1≤j≤n),并且每个S_j中有m个实体服务s_ij (1≤i≤m).QoS向量的维度为r,由于QoS通常是多维的,故本文设r≥2.

假设2. 用户请求按一定平均速率到达,请求的内容(即功能需求和非功能需求)事先不可知;并且各用户请求的优先级相同,依据先来先服务的原则进行服务选择与执行.

3 基于负载等级的QoS模型

服务QoS是选择服务的主要依据,优质的服务常常会频繁地被选择.然而,一个支撑服务运行的硬件设备不可能具有无限多的资源和无限大计算能力,这造成了两个方面的影响:一是服务受到本地资源能力的限制,因而需要限制服务的最大负载,以防止服务过载;二是在不同的负载状态下,服务性能或QoS会发生变化,因而需要对服务在不同负载状态下的QoS进行表示和评估.本文提出了一种基于负载等级的多维QoS模型(LLBMQoS).

3.1 基本定义

服务s_ij的负载区间由一个负载上界和负载下界组成,其中,d为一个服务负载区间标识,表示该区间的负载等级,其值为大于0的整数,它反映了服务繁忙的状态与程度,如轻负载、中等负载和重负载,其等级越高(即d值越大),说明服务当前负载越大.显然,最大负载等级的负载上界为

定义3. 当一个服务s_ij具有z个负载等级时,基于负载等级的多维QoS模型LLBMQoS可表示为

áQ⁽¹⁾(s_ij),…,Q^(z)(s_ij)ñ,

其中,Q^(d)(s_ij)是服务s_ij在负载等级d(1≤d≤z)下的r维QoS向量,,其中,表示服务s_ij在负载等级d下第k(1≤k≤r)个QoS属性的值.

典型的服务QoS属性有响应时间、可靠性、可用性、成本等,其具体定义见文献^{[1, 10]}.

QoS属性根据其方向特征包括积极度量和消极度量两类:积极度量的QoS属性是指其值越大,其反映的质量属性越高,反之越差,如可靠性、可用性等;消极度量的QoS属性是指其值越大,其反映的质量属性越差,反之越高,如响应时间、服务成本等.

事实上,属于积极度量类的QoS属性值可以通过乘以-1而转化成消极度量类的属性^[8].

本文假设所有的QoS属性是消极度量类的或者已经转化为消极度量类.为描述简洁,本文后面的叙述如非特殊说明,都将采用这一假设.

服务通常运行在不同的负载等级下,其QoS表现也各不相同.常用的QoS属性如响应时间、可用性、可靠性、价格等,它们与负载等级之间的关系可以分为相关和不相关两类:

· 与负载等级相关的属性有响应时间、可用性和可靠性等,随着负载等级的增加,这些QoS值可能会发生变化.这种变化大致可以分为两类,即正相关变化和负相关变化:

¨ 正相关变化即随着负载增加,QoS值可能会逐步增加.例如,响应时间在重负载环境下的值要高于低负载状态下的值^[4];

¨ 负相关变化即随着负载增加,QoS值可能会逐步减小.例如,可靠性和可用性会随负载增加而出现下降的趋势^[3],这是由于随着负载的增加,部分请求的响应时间超过最大限度,从而导致响应失败而降低了服务可靠性;另一方面,由于负载的增加导致了服务过载概率的增加,从而降低了服务的可用性;

· 与负载等级不相关的属性主要是服务价格等.

本文主要考虑与负载等级相关的QoS属性,因此,采用基于负载等级的多维QoS模型可以以较细的粒度展现不同负载环境下的服务QoS,为服务选择提供符合实际环境的决策依据.

为了定量地描述负载与QoS之间的关系,需要构建基于负载等级的多维QoS模型.通常可以采用两种方法:一种是由服务提供商在服务正式发布前对服务进行不同等级的压力测试,获取不同负载等级下的QoS值,并与其他服务注册信息一同发布;另一种是在服务运营过程中,通过服务监测获取不同负载等级下的QoS值.本文不研究服务QoS的测试与监测获取问题,并假设这些数据已知.

3.2 基于QoS的效用

在VCSF已知的前提下,为了实现服务的优选和组合服务的优化评估,需要计算基于QoS的效用,本文采用文献^[1]的方法对QoS进行归一化处理,并计算效用值.

定义4. 表示经过归一化处理的,其计算方法如下:

(1)

其中,表示服务类S_j中在各负载等级下所有服务的第k维QoS属性的最大值,表示服务类S_j

在各负载等级下所有服务的第k维QoS属性的最小值,AQmax^(k)表示在当前VCSF中第k维聚合QoS属性的最大值,AQmin^(k)表示在当前VCSF中第k维聚合QoS属性的最小值.具体计算如下:

(2)

(3)

(4)

(5)

其中,G_k(×)表示在当前VCSF中,关于n个服务的第k维聚合QoS函数.本文考虑4种基本的虚拟组合服务流程结构:顺序、并发、选择和循环,这4种基本结构还可以通过组合形成更复杂的流程结构,其聚合QoS的计算方法在文献^[21]有详细的讨论,本文不再赘述.

定义5. 表示实体服务s_ij(1≤i≤n,1≤j≤m)在负载等级d下的效用,计算如下:

(6)

其中,w_k为各QoS属性的权重,且.

定义6. u_ij表示实体服务s_ij(1≤i≤n,1≤j≤m)的期望效用,计算如下:

(7)

其中,表示服务s_ij处于负载等级d的概率.

以上考虑的仅仅是局部QoS的归一化处理以及单个服务效用的计算,然而,用户QoS需求表现为组合服务的QoS需求.用户能够感知到的是组合服务的聚合QoS,而非单个实体服务的QoS及其效用.因此,需要获取实际执行时的服务QoS并对组合服务的聚合QoS进行归一化处理,以便进一步计算组合服务的实际效用.

定义7. U表示由实体服务构成的组合服务在实际负载环境下的执行效用.假设组合服务CS由n个原子服

务构成,可表示为,并且在该组合服务的执行过程中,各原子服务执行时的负载等级分别对应为ád₁,

d₂,…,d_nñ,则执行效用按式(8)计算:

(8)

其中,V_k表示表示经过归一化处理的第k维聚合QoS值,其计算方法如下:

(9)

4 负载感知的动态服务选择模型 4.1 基本模型

组合服务的生命周期可以大致分为两个部分:一是设计阶段,在这一阶段生成服务组合方案;二是组合服务执行阶段,在这一阶段依据前面的方案执行组合服务.

传统的服务选择只涉及第1阶段,而忽略了组合服务执行阶段的服务状态变化,从而造成了服务选择(或组合)方案难以适应动态变化的环境(如服务负载).本节将服务选择方法拓展到了组合服务的整个生命周期,提出了一种两阶段服务选择模型.这两个阶段分别为:

· 在服务组合规划阶段(即第1阶段)进行服务选择预规划,生成候选服务队列CSQ(candidate service queue);

· 在组合服务执行阶段(即第2阶段),依据CSQ以及相关服务的当前负载状态进行运行时的动态选择.

具体过程是(如图 2所示):

1) 当用户请求到达时,服务选择预规划模块根据用户的功能性需求(即VCSF)选择相关的虚拟服务池,也就是对应的服务类;

2) 从中获取候选服务的QoS信息;

3) 在每个相关的服务类中按一定策略选取若干个候选服务,生成候选服务队列CSQ,并发送给对应的动态选择代理;

4) 当组合服务执行到某个任务(或服务类)节点时,相应的动态选择代理根据候选服务队列中候选服务的当前负载状态,选择局部效用优化的实体服务参与组合.

其中,步骤1)~步骤3)属于服务选择的第1阶段;步骤4)属于服务选择的第2阶段.

值得一提的是,在本模型中,可以同时设置多个服务选择预规划模块来为不同的用户或业务服务,以防止单个模块带来的性能瓶颈问题.

模型主要由3个部分组成:虚拟服务池集合、服务选择预规划模块和动态选择代理集合,如图 2所示.

· 虚拟服务池集合由若干个虚拟服务池组成,每个虚拟服务池聚集了功能相同但非功能属性(如QoS)不同的一组实体服务集合,一个虚拟服务池对应一个服务类S_j;

· 服务选择预规划模块通过对服务选择进行预处理,在各服务类S_j的原始候选服务中,筛选出满足一定条件的候选服务生成候选服务队列CSQ_j,并分发给对应的动态选择代理.具体的算法将在后面讨论;

· 动态选择代理集合由多个动态选择代理组成,每个动态选择代理与服务类和虚拟服务池一一对应.当组合服务执行到该服务类时,对应的动态选择代理从该组合服务的CSQ_j中按一定的算法选择实体服务参与组合服务的执行.具体的算法将在后面讨论.

动态选择代理主要由3个部分组成:负载统计模块、动态选择模块和候选服务队列集合.图 3显示了各部分之间的关系:

1) 当任务到达时,触发服务选择;

2) 动态选择模块从候选服务队列集合中选取属于该服务类CSQ_j;

3) 动态选择模块从负载统计模块获取有关实体服务的当前负载等级;

4) 输出服务选择结果;

5) 如果结果不为Æ,负载统计模块需要根据服务被调用的情况更新该服务的负载状态.

具体方法是:当调用该服务时,该服务的并发任务数量加1;当该服务的一个任务结束(即动态选择代理收到请求的响应)时,其并发任务数量减1.值得一提的是,本模型假设了虚拟服务池中的实体服务只能由动态选择代理来选择调用,而不能由其他用户直接选择调用,如此才能保证统计负载的真实性.

图 4显示了两阶段动态服务选择过程的一个实例(为保持过程的简洁,该图删除了从虚拟服务池获取QoS数据的过程).在该实例中共有5个服务类(对应的有5个虚拟服务池和5个动态选择代理),每个服务类有若干个实体服务.这些服务类共形成了2个VCSF(见表 1),即代表了两种不同的组合服务功能(或者业务功能).同时,在该实例中为每个VCSF分别设置了一个服务选择预处理模块,用来服务于使用该VCSF的用户.在任意一个服务(或任务)节点S_j的执行过程中,选择代理依据一定策略从对应的服务候选队列中选择一个服务绑定执行.

在动态的运行环境中,为了实现负载敏感的服务优化选择,本文提出了一种基本的动态服务选择优化数学模型.该模型可以表示为公式(10):

(10)

其中:

· AQ_k(s_ij)为执行第j个任务(即服务类S_j)时的第k个QoS属性值,该值与服务执行时其所处的负载状态有关;

· 是二元变量,取值为0或1:当值为1时表示s_ij被选中,并且该服务被执行时,其负载等级为d;否则,其值为0;

· 表示第k个QoS属性的全局约束或最大值(假设所有属性均为消极度量的).

在上面的模型中,目标为最大化组合服务的执行效用U.约束条件为组合服务的各QoS属性需满足全局QoS约束,并且每个任务只能由一个服务来完成.同时,在一次服务执行过程中,一个服务只能处于一种负载等级.显然,该模型属于经典的NP-难问题.然而,服务负载在运行阶段常常发生不可预知的动态变化,在组合服务的设计阶段难以直接对服务选择进行优化.因而,本文在两阶段服务选择模型下提出了相应的优化关键算法.

4.2 模型的关键算法与分析

本模型涉及到的关键算法有候选服务队列生成算法和动态选择算法,其中,候选服务队列生成算法部署在服务选择预规划模块,动态选择算法部署在动态选择代理中.

4.2.1 候选服务队列生成算法

该算法将全局端到端的QoS约束分解为局部QoS约束LQ_j(即每个参与组合的服务类S_j的QoS约束),在各服务类节点S_j挑选出可能满足局部QoS约束的候选服务,生成候选服务队列CSQ_j.

该算法的核心是解决如何将全局端到端的QoS约束分解为对每个服务类的局部约束.本文将该问题定义为一个多维约束下的极大极小优化问题,其数学模型如下:

(11)

其中,

· 表示在服务类S_j的第k(1≤k≤r)维局部QoS约束,并且

;

· 表示第k维的全局QoS约束;

· G_k(×)表示第k维的聚合QoS函数.

约束条件保证了满足局部约束的服务组合后,其聚合QoS仍然满足用户的QoS需求(假设所有QoS属性都是消极度量类的).

F(LQ_j)表示关于局部QoS约束的目标函数,计算如下:

(12)

其中,P_ij(LQ_j)为服务s_ij在所有负载等级下满足局部约束LQ_j的概率,计算公式如下:

(13)

其中,为指示函数,当值为1时表示服务s_ij的Q^(d)(s_ij)满足局部约束LQ_i;当值为0时表示不满足局部约束:

(14)

以上数学模型可以描述为:将一个全局QoS约束分解为对多个服务类(即虚拟服务池)的局部QoS约束LQ_j (1≤j≤n),使得目标函数F(LQ_j)的最小值最大化.这种分解方法的好处在于,考虑到了参与组合的服务有可能因负载原因而使服务组合性能降级或过载.不同于以往只考虑全局求和的情况,本文提出的分解方法着重考虑优化某些可能会形成瓶颈的服务类节点,以有效地应对可能出现的性能降级或过载的情况,最终使得在这些服务类节点能够提供更多的服务选择,而并非生成单一的基于全局优化的服务选择结果.

根据假设1和文献^[22]可知,公式(11)的模型可以表示为一个多约束路径优化问题(multi-constrained optimal path,简称MCOP),至少属于NP难问题.本文设计了一种启发式算法(CSQGen),实现对这一模型的求解.在介绍本算法之前,本文首先引入与算法相关的定义.

定义8(QoS递增量). 由Drs_j表示,是对更新前和更新后的服务类S_j局部约束向量增加程度的度量,其定义如下:

(15)

其中,和LQ_j分别表示服务类S_j更新后和更新前的局部约束向量,为更新前已聚合的QoS约束向量,有:

(16)

值得一提的是,为了提高算法的效率,使其能够适应较大的服务规模,减少计算时间成本以及分发时的数据量,本模型对生成的候选服务队列CSQ的最大长度做了限制.本文用h表示候选服务队列的最大长度,即CSQ最多能够容纳的实体服务数量.显然,h≤m.

在算法1的Step 1中,需要遍历每个服务类中m个候选服务;又因为共有n个服务类,故其时间复杂度为O(nmzr).同理,Step 2的时间复杂度也为O(nmzr).Step 3~Step 7每次循环的结果是增加了一个满足局部约束的QoS,故对于n个服务类,总共需要循环次数的上界为nzh;单次循环的时间复杂度为O(nr+mzr),故Step 3~Step 7的时间复杂度为O(nhmrz²+rzhn²).Step 8的时间复杂度O(nhlogh).

综上所述,其总体的时间复杂度为O(nmrhz²+rzhn²+nhlogh).由于h≤m,当m较大时,需要恰当地选择h值,确保维持较短的计算时间.

算法1. 候选服务队列生成算法(CSQGen).

输入:全局QoS约束Q^max,S₁,…,S_n,h;

输出:CSQ₁,…,CSQ_n或者为null.

Step 1. 对每个S_j和QoS属性k,令(1≤i≤m;1≤d≤z),检查初始向量组LQ₁,…,LQ_n是否满足全局约束Q^max;若满足,则进入Step 2;否则,候选服务队列生成失败,输出null,退出算法;

Step 2. 对每个服务类S_j,将S_j中在各负载等级下都满足当前LQ_j约束的实体服务加入到CSQ_j,其他的实体服务加入集合F_j,并计算其目标函数值F(LQ_j);

Step 3. 选择目标函数值最小的服务类S_c;

Step 4. 如果CSQ_c队列长度≥h或者F_c为Æ,执行Step 8;

Step 5. 对F_c中各实体服务s_ic的所有QoS属性k(1≤k≤r),令:

(1≤d≤z) (17)

其中,,表示候选的新局部QoS约束,它是根据S_c中第i个实体服务s_ic的QoS属性所生成的;

Step 6. 将替换后仍然满足全局约束的组成局部约束候选集合y_c,如果y_c为Æ,执行Step 8;

Step 7. 在y_c中选择具有最小Drs_c的;更新局部约束,计算新的目标函数值;如果s_ic在各负载等级下的QoS均满足LQ_c,则将s_ic加入CSQ_c,并从F_c中删除s_ic;返回Step 3;

Step 8. 遍历每个CSQ_j,如果CSQ_j的长度等于h,直接输出CSQ_j,算法结束;否则,对于服务类S_j中每一服务,按其P_ij(LQ_j)的值(即满足局部约束LQ_j的概率)进行非递增排序,对于P_ij(LQ_j)函数值相同的服务,按其u_ij值非递增排序(可采用快速排序算法),并获取排在前面的h个服务组成CSQ_j,输出CSQ_j,算法结束.

4.2.2 动态选择算法

组合服务执行过程中,当需要执行某个任务时,在该任务所对应服务类S_j中触发动态选择算法.该算法的主要思想是:根据服务的当前负载等级d,从CSQ_j中选出满足局部QoS约束(即LQ_j)且效用最大的服务执行该任务,即在满足局部约束的前提下,尽量选择当前负载等级下效用值最高的服务参与组合.

从算法2中可以看出:由于候选服务队列CSQ_j最大长度为h(h≤m),故其时间复杂度为O(h).可见,时间复杂度与n和m都无关,能够满足动态服务选择在服务执行阶段对处理时间的苛刻要求.

算法2. 动态选择算法(DS).

输入:CSQj;   
    输出:s* or Æ.   
		Wi=null; 			/*初始化*/   
    For each sij in CSQj   
    {   
		get sij’s current workload dij; 	/*获取服务sij的当前负载等级dij*/   
		if sij is not overloaded 	/*判断服务sij是否发生过载,即并发任务数量是否超过*/   
			if Wj¬sij 	  /*当服务sij未过载时,如果服务在当前负载等级下可以满足局部QoS约束,
						则加入集合Wj*/   
    }   
    If Wj=null Return Æ; 			/*选择失败,没有合适的服务*/   
		Else ; 		/*获取集合中具有最大效用值的服务sij */   
    Return s.   

5 实验分析 5.1 实验环境配置

本文通过仿真实验来模拟服务选择环境并验证了本模型的有效性.实验环境为一台HP Intel P4 CPU/4G RAM/Windows 2003/C#.采用混合整数规划MIP(mixed integer programming)工具Lpsolver version 5.5实现线性规划求解;采用C#实现本文所提出的选择方法.

仿真实验采用3个QoS属性(响应时间、可靠性和可用性)和3个负载等级,并分别使用两种不同的数据:

一是采用随机生成的服务QoS数据(响应时间在1ms~800ms之间,可靠性和可用性在0.5~1.0之间)作为生成QoS模型的参考数据;

二是采用QWS数据集^[23]的响应时间、可靠性和可用性数据作为生成QoS模型的参考数据.

生成基于负载等级QoS模型的具体方法为:分别以随机数据集和QWS数据集中的数据为负载等级2时的QoS值,由于各服务在不同负载等级下表现出的QoS特性各不相同,故对于响应时间,其负载等级1和负载等级3时的值分别为负载等级2时的值乘以随机因子a₁(0.8<a₁<1)和a₂(1<a₂<1.2);而对于可靠性和可用性,其负载等级1和负载等级3时的值分别为负载等级2时的值乘以随机因子b₁(1<b₁<1.1)和b₂(0.9<b₂<1).并且,当所计算出的可靠性或可用性的值大于等于1时,则对应的属性值仍采用原来数据集中的值.如此,可以保证各QoS属性值满足不同负载等级下的依赖关系.

同时,在随机数据集中随机生成各服务的最大负载;在QWS数据集中采用最大吞吐量数据作为服务的最大负载,并根据设定的负载等级数量平均划分为3个负载区间.

表 2显示了不同数据集下的实验环境配置.

实验中的服务类数量为n(n≥10),并假设每个服务类节点都拥有相同数量的实体服务.组合服务一般包含顺序、并发、选择和循环这4种基本结构,而选择和循环结构又可以转化为顺序和并发结构^[13],故本实验的服务流程只考虑这两种结构.实验采用图 5所示的由n个服务类构成的两种虚拟组合服务流程VCSF:一个为顺序结构;另一个为顺序和并发的混合结构.

5.2 实验结果与分析

在前面的相关工作中,本文已经分析了文献^{[6, 17, 18]}等针对多个用户需求的服务选择与组合的研究情况,指出了这些研究都基于这样一个假设,即所有用户需求信息可以事先获得.而这一假设并不适用于开放的、动态的服务选择与组合环境.本文研究主要针对的是用户需求信息无法事先获得、用户请求离散随机到达的情况,故本文模型需要实时地响应用户的服务组合请求.通过前面与相关研究的比较,已经定性地分析了本文模型LADSSM的优势,为了进一步验证LADSSM的有效性,本实验将该模型与经典的、具有代表性的全局优化服务选择方法^[1](以下用Global表示)以及近年提出的混合优化法^[8](以下用Hybrid表示)进行定量的实验比较.为了方便分析,本文提出3个评价指标:执行成功率(ESR)、平均执行效用(AU)和计算时间(CT).

定义9(执行成功率(ESR)). 指成功响应的用户请求数量占用户请求总数量的比例,表示为

ESR=num_s/num (18)

其中,num_s为成功响应的用户请求数量,num为用户请求总数量.请求被成功响应的判定标准有两个:一个是组合服务要满足端到端的QoS约束;另一个是各服务节点不发生过载.该指标反映了服务选择方法在多用户的动态负载环境下的应变能力.

定义10(平均执行效用(AU)). 指对成功响应的用户请求而言,所有组合服务执行效用U(见定义7)的均值.该指标反映了本文模型的优化能力.

定义11(计算时间(CT)). 指算法生成组合服务所需的平均计算时间.该指标反映了算法的效率以及适应大规模环境的能力.值得一提的是,由于本模型动态选择算法的运行时间极短,可以忽略,故本实验将候选服务队列生成算法(CSQGen)的计算时间和全局优化方法Global的计算时间进行了比较.

5.2.1 执行成功率

第1组实验分别采用随机数据集和QWS数据集,测试了本文模型LADSSM与Global方法和Hybrid方法在不同用户请求速率l下执行成功率ESR的变化.

从图 6中可以看出:随着l从10reqs/s增加到100reqs/s时(即组合服务的负载增加),执行成功率逐步下降.其中,Global方法的执行成功率下降得较快;而本文方法的执行成功率下降得相对较慢,特别是h较大时,执行成功率下降得更慢.如:当l=90reqs/s,使用随机数据集的Global和Hybrid方法的ESR为20%左右,而本文模 型的ESR分别约为60%(h=2)和90%(h=5);使用QWS数据集时也有类似结果.可见,无论是随机数据集还是QWS数据集的实验结果都表明,本文模型的执行成功率ESR要极大地高于Global方法和Hybrid方法.

第2组实验分别采用随机数据集和QWS数据集,测试了本文模型在不同h下执行成功率的变化.

从图 7中可以看出,执行成功率随h的增加而增长.在h相同的情况下,当l较低(即组合服务的负载较小)时,执行成功率ESR相对较大;反之,ESR相对较小.在随机数据集中,当h增加到6时,执行成功率ESR就已达到了85%以上;而在QWS数据集中, 当h增加到12时,执行成功率ESR达到了85%以上.

通过比较可以看出:本文方法可以有效地提高动态环境下服务的执行成功率;当组合服务的负载较大时,可以通过适当提高h来维持较高的执行成功率.

5.2.2 平均执行效用

第3组实验分别采用随机数据集和QWS数据集,测试本文模型(LADSSM)的平均执行效用AU随候选实体服务数量m和服务类数量n的变化.

从图 8和图 9可以看出:本文模型在不同的服务规模(m和n)下都可以取得一个较好的平均执行效用AU;在相同的用户请求速率(l,单位:reqs/s)下,本文模型所获得的平均执行效用要高于采用Global方法和Hybrid方法所获得的平均执行效用.显然,LADSSM考虑了服务的负载以及在不同负载下的QoS,因而提高了组合服务运行时的执行效用.此外,当用户请求速率l较大时,平均执行效用会有所降低.这说明,当组合服务的负载较大时,本模型会在保证用户端到端的QoS需求不被违背的前提下,选择效用次优的服务,以防止优质服务的过载或性能降级,从而实现了负载感知的自适应服务优化选择.

5.2.3 计算时间

第4组实验测试了本文算法(CSQGen)与全局优化方法(Global)和混合优化方法(Hybrid)的计算时间.

从图 10和图 11可以看出,全局优化方法(Global)的计算时间随m和n增加而增长较快.混合优化方法(Hybrid)的计算时间随m和n增加而增长相对较慢;本文算法的计算时间随m和n增加也增长相对较慢.从总体上讲,本文算法在计算开销上优于上述两种算法,因而可以有效应对较大规模的服务场景.由此可见,本文算法具有较低的计算开销.此外,从结果还可以看出,h对计算时间有影响:当h增长时,计算时间相对较大.所以,为维持较短的计算时间和较高的执行成功率,需要选择一个合适的h值.可见,本模型能够通过调节h来适应不同的组合服务环境以及服务组合性能要求.

6 结束语

本文提出了一种面向多用户的负载感知的动态服务选择模型LADSSM,该模型能够在多用户、多业务的环境下较好地适应服务负载的变化,及时、动态地生成组合服务.仿真实验测试和比较了本文模型的执行成功率、平均执行效用和计算时间.结果表明:本文模型能够较好地感知服务负载变化,并及时有效地提供效用优化的服务选择方案.与以往相关研究对比,本文模型具有3个特点:① 构成组合服务的各实体服务是在执行过程中被动态选择并绑定执行的;② 支持开放的多用户、多业务环境,服务选择无需事先获得所有用户请求信息;③ 在满足不同用户QoS约束的前提下,感知服务节点的负载,实现适应负载变化的组合服务动态优化选择.

在实际应用中,当用户请求数量较大时,对多个服务实体的“负载等级”等数据的获取会造成一定的开销.因此,当用户请求数量较大时,需要减少候选服务队列最大长度h(即将h设为较小的值),如此可以减少运行时备选服务的数量,从而减少获取服务实体相关动态数据的开销.而如何有效地设定h,则需要根据实际运行环境在测量实验的基础上通过权衡效用、成功率和开销来实现.本文研究所适用的场景主要是用户实时请求离散、随机到达的情形,因而是一种在线式的动态服务选择方法;而对于大量成批连续到达的用户请求,则适用于离线式的服务选择方法,这是本文下一步的研究方向.