激励机制下负载均衡和QoS感知服务组合方法

刘英， 焦竽鑫， 吴小竹

(福州大学 数字中国研究院(福建)， 福建 福州 350108)

近年来，随着Web服务技术的快速发展，越来越多的Web服务被发布到网络端实现共享，使具有相同功能但不同服务质量(QoS)的Web服务数量剧增[1].单个Web服务由于功能简单很难满足用户的复杂需求，QoS感知服务组合(QSC)研究应运而生[2].欧阳超等[3]结合模拟退火算法和遗传算法提出一种新的服务组合方法，加速解的收敛.马力等[4]针对传统缺乏语义信息支持的Web服务选择问题，量化QoS属性并将该问题转化为图搜索问题，利用AO*算法求解.Hwang等[5]将QoS作为具有概率质量函数的离散随机变量进行服务选择.Yuan等[6]提出基于自适应全局QoS约束分解的动态服务选择方法，采用模糊逻辑和文化遗传算法获取局部约束组合，缩小服务的搜索范围.Alayed等[7]提出改进蚁群优化算法(EACO)，该方法能有效避免局部最优，减少搜索时间.传统服务组合方法容易忽略参与者的竞争关系，部分学者引入博弈论思想.马同伟等[8]针对分配中买卖双方的利益问题，提出双向拍卖资源分配模型，保证双方在公平公正的环境中竞争和购买.Wang等[9-10]认为在服务选择过程中，参与者具有自私性且不愿完全暴露自己的信息，针对信息不完整的决策问题，考虑Web服务存在纳什均衡竞争关系，提出一种激励机制选择最优Web服务；并且基于激励合同提出一种新的激励机制，在该激励机制中，请求者向提供者提供激励合同，根据提供者对激励合同的反应获取私有信息，不断迭代直到为每个任务均选择出最优服务.激励机制是将博弈论应用到服务组合中的一次大胆且成功的创新，有效地解决了服务选择中寻找最优解的问题，并且对参与者都有着正向、积极的作用.

在服务组合过程中，请求者的主要目的是在满足其功能需求下获取具有良好质量保障的组合服务，提供者则需要优化QoS和保证负载均衡[11].传统服务选择策略倾向于选择QoS更优的Web服务，使该Web服务的负载增加.服务的负载能力往往是有限的[12]，若达到最大负载量后，其QoS可能无法保证，并且负载不均会导致服务出现过载或空闲的状态，这将影响系统的整体性能.李文中等[13]提出一种自适应分布式负载均衡(LCB)算法，使用负载容率测度衡量各服务副本的负载状况.杨石等[14]针对任务调度中的时间和通信成本问题，提出基于蜜蜂觅食行为的负载均衡(HBB-LB)算法，有效平衡虚拟机的负载和响应时间.任金霞等[15]为缩短任务完成时间和提高负载均衡，提出一种具有QoS约束的模拟退火的任务调度算法，使参与者的效用均能获得满足.Pushpavati等[16]提出一种改进最大完成时间和迁移性能的配对树算法，提高了响应时间、成本、活力和吞吐量等综合服务质量指标.Arabinda等[17]提出一种基于改进粒子群算法的负载均衡技术(LBMPSO)，能够缩短虚拟机完工时间，提高资源的利用率.施凌鹏等[18]提出微服务链感知的请求负载均衡算法，减少请求响应的延迟时间，平衡主机间的负载.Muthsamy等[19]考虑完工时间、响应时间、执行时间和任务优先级等多种QoS属性，提出人工蜜蜂觅食优化任务调度(TSABF)算法，以获得虚拟机上的最优任务调度和负载均衡.Li等[20]考虑用户偏好、服务水平协议和成本等因素，提出边缘云资源模型，能在满足负载均衡要求的同时使成本降到最低.Mohanty等[21]认为负载均衡的基本目标是最小化时间和提高系统性能，采用Jaya算法实现了云环境中的负载均衡.Asghari等[22]同时考虑负载均衡和QoS感知问题，提出反向蚁群优化(IACO)算法，以解决云服务器的负载均衡效率低下问题.

考虑QoS的负载均衡策略不仅能够合理分配资源的工作负载，实现资源的有效利用，还能够获取到满足请求的优质方案.因此，QoS感知负载均衡的研究具有必要性.基于此，本文提出一种基于激励机制的负载均衡和QoS感知服务组合(LBQSC)方法，通过动态调整QoS改变Web服务的选择概率，并权衡请求和提供者的双方需求，以解决服务组合的负载均衡QoS感知问题.

1 负载均衡和QoS感知服务组合问题

1.1 相关定义

定义1Web服务(s)是一个独立的、功能完整的可以通过网络进行发布、定位及访问的最小资源单位，包含功能属性和非功能属性，可用6元组s={id，b，f，QoS，lw，lmw}表示，其中，id为s的唯一标识；b为s的基本信息，包括提供者、名称和发布时间等；f为s的功能属性，是服务被发现的首要依据；QoS为s的非功能属性，是服务被选择的重要评判标准；lw为s的实时负载量，是Web服务当前的服务对象个数；lmw为s的最大负载量，是被服务对象个数的最大值，lw≤lmw，一旦实时工作量达到最大负载量，服务立刻停止为其他对象提供服务.

定义2服务质量指Web服务的非功能属性，包括一组QoS属性QoS={q1，…，qν}.一个QoS属性qν可用3元组qν={nν，dν，rν}表示，其中，nν为qν的名称，如响应时间、声誉、价格、可行性等，dν为qν的初始状态默认值，rν为dν的可变性，存在两种情况:1) 当rν=0时，dν不发生改变；2) 当rν≠0且rν∈(0，1)时，dν可发生改变，变化区间为[dν×(1-rν)，dν×(1+rν)].

在服务组合中，不同QoS属性的数量级往往不同，因此，需要进行归一化处理.施凌鹏等[18]将非功能属性分成积极属性和消极属性，通过简单加权(SAW)技术[19]进行归一化.对于积极属性(声誉、可行性等)，属性值越大，表示服务质量越好，按照式(1)归一化，即

(1)

对于消极属性(响应时间、价格等)，属性值越小，表示服务质量越好，按照式(2)归一化，即

(2)

定义3抽象服务(AS)代表具有相同功能、不同QoS的一组Web服务，这组服务被称为该抽象服务的候选(具体)服务集.

定义4工作流(F)可用2元组F={AS_set，str}表示，其中，AS_set={AS1，…，ASi，…，ASm}为一组抽象服务，ASi为第i个抽象服务且ASi={si，1，si，2，…，si，j，…，si，n}；str为抽象服务的组织结构.

工作流管理联盟(WFMC)提出顺序、选择、循环和并行4种结构，用以支持Web服务组合建模[1].其中，选择、循环和并行结构均可通过文献[20]中的技术转化成顺序结构.

(3)

组合服务的QoS属性值是由构成该服务的各个原子服务的QoS属性值聚合而成.不同QoS属性在不同工作流中的聚合公式不同，不同QoS属性在同一工作流中的聚合公式也不同[21].Web服务的声誉(R)、响应时间(T)和价格(P)3个QoS属性在顺序工作流下的聚合公式分别为

定义6服务负载(load)指服务资源利用率，用Web服务在某一时刻工作量与最大工作量的比值表示，即load=lw/lmw.

定义7用户请求(r)用来存放请求者的需求信息，可用2元组r={id，C}表示，其中，id表示r的唯一标识；C表示全局QoS约束，是请求者对组合服务QoS的基本要求.

定义8全局QoS约束C={c1，c2，…，cϑ}，其个数不得超过Web服务QoS个数，即ϑ≤ν.全局QoS约束是对组合服务QoS的基本约束，它要求组合服务的QoS应该优于用户请求中对应的全局QoS.

1.2 问题描述

minδ，

(4)

(5)

mint，

(6)

(7)

则SOL为最优解决方案.

式(4)～(6)是最优解决方案的评判标准，其中，式(4)表示在获得SOL后，Web服务的总体负载标准差最小；式(5)表示SOL具有最大的平均效用；式(6)表示获取SOL的执行时间最少.式(7)是SOL作为最优解决方案存在的基本条件，它要求每个组合服务CSk中QoS属性qν整合后均优于请求rk中对应的全局QoS约束qν.

图1 LBQSC的总体框架 Fig.1 Overall framework of LBQSC

2 LBQSC方法设计

2.1 LBQSC的总体框架

基于LBQSC方法求解负载均衡和QoS感知服务组合问题主要分为全局约束分解(GCD)模型求解和局部服务选择2个步骤.LBQSC的总体框架，如图1所示.

GCD模型求解被认为是组合优化问题，文化遗传算法(CGA)在处理此类问题时具有快速收敛和防止早熟等优点[9，23-24]，因此，文中采用CGA算法.在局部服务过程中，Web服务选择激励机制[5]，通过合同激励服务提供者更改自身服务QoS属性，再迭代选择QoS更高的Web服务，从而提高服务请求者的效用.但是这种机制并没有考虑服务的负载情况，因此，对合同进行改进，使其不仅能够约束服务的QoS和负载，还能提供更高报酬来激励服务提供者将本身服务的QoS根据当前负载整体水平进行动态调整，在此基础上，提出一种基于激励机制的服务选择方法.最后，组合局部选择的服务形成组合服务.

2.2 GCD模型求解

全局QoS约束分解过程的主要目的是将服务请求者的全局QoS约束合理地分解为一组局部约束，确保满足局部约束的Web服务复合而成的组合服务一定满足服务请求者的全局QoS约束.保留更多的组合方案考虑2个原则：1) 确保满足每个局部约束的候选服务个数尽量多；2) 确保满足每个局部约束的候选服务个数尽量均衡[25].其评价公式为

E=ωsum×S+ωmul×M.

(8)

GCD模型求解过程包括初始化质量等级和寻找最优局部约束组合2个步骤.

寻找最优局部约束组合是将质量等级进行组合，从而使E近似最大化的过程.采用CGA求解该过程，通过文化算法从进化种群中抽象待解决问题的知识，反馈这些知识以指导算法的搜索过程，从而保证解的收敛.CGA的实现框架，如图3所示.图3中：种群空间由个体组成；Update()函数用于更新信仰空间的知识；Accept()函数用于从种群空间选择一定数量的个体进入信仰空间以形成知识；Influence()函数主要通过信仰空间中的知识影响社会群体空间的进化方向；Generate()函数用于构造个体；Evaluate()函数用于评价个体的适应度；Select()函数用于遗传操作中选择交叉的个体.

图2 质量等级分解 图3 CGA的实现框架 Fig.2 Quality level decomposition Fig.3 CGA implementation framework of CGA

2.3 基于激励机制的服务选择

激励机制来源于激励理论，主要包括激励主体、激励客体和激励手段3部分.在激励机制中，激励主体通过各种手段引导、激发激励客体的潜能，从而实现激励主体的战略目标.在服务选择过程中，请求者、提供者和选择策略分别对应激励主体、激励客体和激励手段.于是，Wang等[9]提出一种Web服务选择激励机制，将激励机制的优势充分应用于服务选择.该机制针对不同QoS提供具有不同报酬的合同来调动服务提供者的积极性，能够帮助请求者快速获取质量更优的服务，并保证服务本身的基本利益.但是，该机制并没有考虑服务的负载能力.因此，对文献[9]的方法进行改进，使之能够解决负载均衡和QoS感知服务组合问题.通过节2.2获取近似最优局部约束组合，排除不满足约束要求的候选服务，缩小服务选择的搜索范围.此时，提供一种新的合同，通过给不同的QoS和服务负载支付不同的报酬，激励服务提供者动态调整其自身服务的QoS来积极竞争合同.同时，为了选择最适合的服务，设计一个基于合同的服务选择策略.在此基础上，构建基于激励机制的服务选择算法，具体描述如算法1.激励合同构造、QoS动态调整和Web服务选择是其中的3个关键步骤.

算法1 基于激励机制的服务选择算法

输入： csSet ∥满足局部约束的候选服务集合

输出： bos ∥最优可选服务

1. ∥M为最大迭代次数，Size为候选服

务个数

2. IF j≤ M OR Size!=0

3. ∥构造合同

4. conj=offerContract(s_set， canSet， j)

5. ∥满足当前合同的候选服务集中存放

到osSetj

7. ∥添加到osSet中

8. osSet←osSetj

9. ∥不满足的动态调整其QoS后存放到

csSet中

10. csSet=AdjustQoSValue(Unsatisfy

(conj))

11. ENDIF

12. ∥选择服务

13. bos=ServiceSelect(osSet)

带合闸电阻断路器装置示意如图3所示，其中R1为合闸电阻，D1为辅助触头，D2为主触头。合闸命令发出后，D1先合闸，合闸电阻投入并作用一段时间，而后D2合闸，合闸电阻旁路退出运行，D1再分闸。

14. Return bos∥最优可选服务

2.3.1 激励合同构造 合同(con)是请求者对负载和服务质量这2个影响因子提出的要求，并确保若服务提供者可以提供满足合同约束的Web服务，服务请求者会支付合同中所给定的报酬.一个合同用4元组conτ=(τ，QoS，τ，loadτ，rewardτ)表示，其中，τ为合同的唯一标识；QoS，τ为合同中除价格之外的QoS属性约束；loadτ为合同中的服务负载约束；rewardτ为针对当前的负载和服务质量，服务请求者支付的费用，也是服务价格的上限.

在合同中，2个影响因子的数值不同，提供的报酬也随之发生变化.就服务请求者而言，在其预算范围内，他们愿意支付更多的报酬去获取QoS更优、负载更低的Web服务.对于一个抽象服务，以其局部约束为依据，提供一组合同Con={con1，…，conτ-1，conτ}，合同conτ的负载和服务质量均优于合同conτ-1的负载和服务质量，且前者的报酬高于后者，则这组合同被称为激励合同.服务提供者若想获得更多的报酬，就需要调整服务自身的QoS来进行竞争.将满足合同约束的候选服务称作可选服务(os)，将效用值最大的服务称作最优可选Web服务(bos).

2.3.2 QoS动态调整 在不满足当前合同的情况下，候选服务若还想获得被选择的机会且获得更高的报酬，就必须改变自身的QoS属性去参与新的合同的竞争.就候选服务来说，若改变当前的响应时间、声誉等QoS属性使之较先前更优，则其价格也会随之增长.因此，给定一个服务提供策略：1) 如果候选服务的负载小于服务的总体负载均值，则优化候选服务除价格以外的QoS属性，并提高候选服务的价格；2) 如果候选服务的负载等于服务的总体负载均值，则保持候选服务的所有QoS属性不变；3) 如果候选服务的负载大于服务的总体负载均值，则劣化候选服务的除价格以外的QoS属性，并减少候选服的价格.

2.3.3 服务选择策略 激励机制运行完毕后，得到多组可选服务集，提供一个服务选择策略确定最终选择的服务，即确定可选服务os个数最多的可选服务集，选择该服务集中的最优可选服务bos.

3 实验分析

通过实验对比LBQSC，EACO[7]，IACO[22]方法，验证LBQSC方法在处理负载均衡和QoS感知服务组合问题时的优越性.

3.1 实验数据与环境

实验数据来源于综合服务数据集QWS 2.0.该数据集包含真实世界中2 507个Web服务数据，每个Web服务有9个QoS属性，包括响应时间、声誉、价格、吞吐量和可靠性等，具体信息可参考文献[21].考虑到对比实验中数据条件的分配情况，仅挑选QWS 2.0数据集中的2 000个Web服务数据，并重点关注Web服务的声誉、响应时间、价格、实时工作量和最大工作量5个QoS属性，声誉和响应时间可从数据集中获取，价格、实时工作量和最大工作量则采用随机算法构造.其中，价格取值控制在50～500；最大工作量取值控制在50～100；实时工作量取值控制在0到最大工作量之间；假设响应时间和价格均是可变的QoS属性，其变化率分别设置为rt=0.2，rp=0.2.在计算组合服务的效用时，声誉、响应时间和负载的权重分别赋值为0.3，0.3，0.4.请求数据根据服务数据特征随机构造.实验结果都是运行10次之后取平均值.

实验使用的算法开发语言是Java，实现工具为MyEclipse 2016 CI，运行环境的具体配置为Windows 7专业版操作系统，内存为4 GB，处理器为Intel(R)Core(TM) i5-2500 CPU@3.30 GHz.

3.2 实验结果与分析

采用LBQSC，EACO和IACO方法在不同的数据条件下分别进行实验，并对各指标进行评估.

3.2.1 负载标准差 为验证LBQSC，IACO和EACO在进行大规模服务组合后，服务的负载标准差较初始状态的优化程度，进行3组对比实验，具体如下.

1) 当抽象服务数(Na)范围为1～10且步长为1，具体服务数(Nc)为200，请求数(Nr)为100时，3种方法的负载标准差(δ)对比，如图4(a)所示.图4(a)中：INT为初始状态下服务总体的负载标准差.

2) 当具体服务数范围为40～400且步长为40，Na=5，Nr=100时，3种方法的负载标准差对比，如图4(b)所示.

(a) 不同抽象服务数

3) 当请求数范围为20～200且步长为20，Na=5，Nc=200时，3种方法的负载标准差对比情况，如图4(c)所示.

(b) 不同具体服务数 (c) 不同请求数图4 不同数据条件下3种方法的负载标准差对比 Fig.4 Comparison of load standard deviation in three methods under different data conditions

由图4(a)可知：在相同具体服务数和请求数情况下，随着抽象服务数的增加，3种方法的负载标准差比初始状态均有所减小，其中，LBQSC方法减小得最明显.由图4(b)可知：不论具体服务数如何变化，LBQSC方法的负载标准差始终最小，其次为IACO方法.由图4(c)可知：服务的数据条件相同，随着请求数的增加，EACO方法的负载标准差虽低于INT，但基本没有太大改变；而LBQSC和EACO方法的负载标准差都逐渐下降且很明显，LBQSC方法下降尤为迅速.

(a) 不同抽象服务数

(b) 不同具体服务数 (c) 不同请求数图5 不同数据条件下3种方法获取的解决方案的平均效用对比 Fig.5 Comparison of average utility in three methods under different data conditions

(a) 不同抽象服务数

(b) 不同具体服务数 (c) 不同请求数图6 不同数据条件下3种方法的执行时间对比 Fig.6 Comparison of execution time in three methods under different data conditions

由图5(a)可知：在具体服务数和请求数相同时，随着抽象服务数的增加，通过3种方法获取的解决方案的平均效用也随之增加，且平均效用与抽象服务数大小呈现近似线性关系.由图5(b)可知：随着具体服务数的增加，LBQSC方法的平均效用明显高于其他两种方法，但当Na<4且Nc<120时，LBQSC方法的平均效用比其他两种方法差，这是因为蚁群算法在小规模服务组合下较激励机制具有更好的收敛性.由图5(c)可知：在服务数据相同的条件下，请求数越多，3种方法的平均效用越差，其主要原因是在大量请求下，QoS较高的Web服务被选择达到最大负载量后，后续的请求只能选择一些QoS较差的Web服务代替，使组合服务效用降低，从而使解决方案的平均效用减小.

3.2.3 执行时间 为进一步验证LBQSC，IACO，EACO方法的时间开销，同样采用节3.2.1的3组数据进行对比实验.不同数据条件下，3种方法的执行时间(t)对比，如图6所示.

由图6可知:不论数据条件如何变化，所提LBQSC方法的执行时间均小于其他两种方法，能快速地获取解决方案.

结合3个指标的对比结果可知，LBQSC方法能够有效解决多请求下的负载均衡和QoS感知服务组合问题，且具有较少的时间开销.

4 结论

针对请求者的高QoS需求、提供者的负载均衡需求及QoS的动态性等问题，提出基于激励机制的负载均衡和QoS感知服务组合(LBQSC)方法.首先，利用文化遗传算法将全局QoS约束分解为一组局部约束；然后，基于激励机制，在满足局部约束且具有动态QoS的候选服务中迭代选择出最佳Web服务；最后，采用QWS 2.0数据集进行实验.实验结果表明：与EACO和IACO方法相比，LBQSC方法能够有效地处理负载均衡和QoS感知服务组合问题.

在未来的工作中，将完善LBQSC方法，使其可灵活地运用到工作流的其他3种基本结构(并行、选择、循环)；改善激励机制中的服务提供策略，使服务QoS的动态调整更加依赖于激励合同的变化，以更好地服务于服务选择过程；考虑用户请求的时序特征，研究面向多连续请求的负载均衡和QoS感知服务组合方法.