基于全局QoS约束分解与关联感知的动态服务组合

侯占伟，翟海霞，沈记全

(河南理工大学 计算机科学与技术学院，河南 焦作 454000)

0 引 言

随着云计算、物联网等信息技术的快速发展，越来越多的Web服务共享在网络上，由于单个服务不能满足用户的复杂业务需求，将网络上可用的服务聚合成功能强大的组合服务是实现服务增值的关键技术。如何高效地从大规模功能相同而QoS不同的候选服务中选出具有全局最优服务质量的服务是服务组合过程中需解决的关键技术问题。

很多学者在基于QoS感知的Web服务组合方法上做了大量的研究，并取得一定的研究成果。基于QoS的服务组合是一个组合优化方面的NP难题[1]，主要采用群体智能算法、进化算法或数学规划方法对该优化问题进行求解，这些方法缺乏一定的灵活性，在候选服务规模增加时算法的时间复杂度也会明显增加。为了提高服务组合的灵活性，将全局QoS约束自适应地分解为局部约束，目前采用的方法有基于模糊逻辑的自适应粒子群优化算法[2]，考虑组件服务的效用、组合模式进行约束分解方法[3-4]，以预测服务的QoS阈值进行全局QoS分解方法[5]，采用改进遗传人工蜂群算法、文化遗传算法等提高服务组合性能[6-7]，结合用户特征和访问服务偏好进行服务选择[8]。但这些方法在全局QoS约束分解时没有考虑QoS之间的关联关系。在基于服务间关联的服务组合方法有通过扩展的服务建模来描述服务间的相关性[9]，构建支持服务间质量依赖关系及语义关联服务选取的QoS模型[10-11]，通过支持任务间关联关系的服务重选算法[12]、支持相关感知服务的剪枝算法[13]，基于遗传算法的相关感知服务选择[14]，结合服务间相关性，采用扩展花授粉算法获得最优服务组合[15]。但在实际服务组合过程中，这些方法没有考虑上下游组合服务之间的动态关联性。

本文通过分析上下游组合服务之间的关联性，提出一种基于全局QoS约束分解与关联感知的动态优化服务组合方法。采用改进的人工蜂群算法进行全局QoS约束分解，在服务组合过程中，动态结合上下游服务之间的QoS关联关系进行服务选择，保证了服务选择的准确性，解决了存在关联关系的服务组合问题。

1 Web服务动态组合问题描述

Web服务动态优化组合问题是指在服务组合过程中，根据用户功能需求及QoS约束，动态地选择最优候选服务进行组合，在满足用户的任务要求情况下使构建的组合服务的QoS全局最优。组合服务CWS={S1,S2,…Sn}由n个服务类组成，服务类Si包含多个功能相同但QoS不同的候选服务，其中Si={Si1,Si2,…,Sik}，表示服务类Si有k个候选服务。动态Web服务优化组合是在大量的候选服务中选择一组满足用户需求的最优候选服务进行组合。

1.1 组合服务的评价函数

设在一个顺序结构服务组合中，CS={S1,S2,…,Sn}表示该服务组合n个任务节点的候选服务集，候选服务sjt为服务类Sj中的一个候选服务，SCl={s1,s2,…,sjt,…,sut}为一个服务组合方案；那么，单个服务sjt与组合服务SCl的QoS效用函数U(sjt)和U(SCl)可以通过(1)式和(2)式计算得到。

(1)

(2)

同时，

Qmin(j,k)=min∀sj,i∈Sjqk(sji)

(3)

Qmax(j,k)=max∀sj,i∈Sjqk(sji)

(4)

(5)

(6)

1.2 全局QoS约束分解模型

全局QoS约束分解是指在服务组合过程中，按照用户的功能需求和QoS约束，将组合流程中服务类的全局QoS约束分成若干个局部取值区间，为每类服务找到满足局部取值区间要求的最优候选服务，使得满足局部QoS约束要求的候选服务组合同样满足全局QoS约束。如果仅考虑满足局部最优约束分解的方法进行服务选择，可能出现组合失败的情况；把全局约束分解为局部约束后，可以保证满足局部约束的服务组合一定满足全局约束，提高了服务组合的效率和成功率。

文献[17]将上述的离散的局部QoS取值区间定义为质量标尺(quality level)，并提出了一种基于质量标尺的QoS分解方法，如图1所示。

首先，初始化质量标尺，图1中，Qjab(1≤a≤m,1≤b≤k)为候选服务Sja的第b个属性的QoS，Ljxy(1≤x≤d,1≤y≤k)为第y个质量标尺的第x个离散数值。将每一个服务类Sj中的k个QoS属性分解为k个质量标尺，每个质量标尺的离散数值Ljdk满足关系Qmin(j,k)≤Ljd1≤…≤Ljdk≤Qmax(j,k)。

其次，构建最优Web服务的质量标尺组合评价模型，不但要保证满足要求的候选服务数量较多，同时还要保证满足组合要求的候选服务的评价值较大。服务组合质量标尺评价公式为

(7)

2 基于改进人工蜂群算法的全局QoS约束分解方法

2.1 改进的人工蜂群算法

人工蜂群算法(artificial bee colony algorithm，ABC)是由D.Karaboga在2009年提出的一种新颖的群集智能优化算法[18]，并将其原理成功地应用到函数的数值优化问题。算法模拟蜜蜂群体寻找优质蜜源的过程，把蜜蜂分为引领蜂、跟随蜂和侦察蜂3种角色[19]，其中，引领蜂负责全局搜索，跟随蜂负责局部搜索，侦察蜂则负责处理进化停滞的个体，利用3种蜜蜂间的协作分工及信息交流共享，来实现对最优蜜源的搜索，从而找到问题的最优解。

根据服务组合问题中服务之间存在有关联关系这一特性，本文提出一种改进的人工蜂群(improved artificial bee colony， I-ABC)算法来解决服务组合全局QoS约束分解问题。

1)改进的初始食物源生成方法。生成初始解。设定食物源的规模为SN，根据服务组合执行的历史记录，从每个候选服务的非功能性属性中随机选择一个常用的属性值；首先生成第一个解，产生其余解时需先查询服务关联数据集，然后从与已生成解存在有关联关系的数据集中随机选择常用的属性值，组成初始食物源S={S1,S2,…,Si,…,SN}，如图2所示。

图2 生成N个初始解Fig.2 Generate N initial solutions

2)改进的雇佣蜂阶段。进行解的邻域交叉变换，如图3所示。首选随机选择一个解Si，在服务关联数据集中查询与Si存在有关联的解并随机选择一个解Sj，0≤i,j≤n。然后将随机选择的Si，Sj2个解对应列进行交换后得到2个新解Si′和Sj′。计算并比较Si，Sj、Si′和Sj′ 4个解的评价值，保留评价值最优的解。

图3 解的交叉变换Fig.3 Cross transformation of the solution

图4 解的变异Fig.4 Variation of the solution

4)最优解保留操作。采用(3)式对当前解的集合S={S1,S2,…,Si,…,SN}依次计算其评价值，然后进行评价比较，将评价值最高的解保留在最优解BS中。

2.2 基于I-ABC的最优服务组合求解算法

在本文提出的改进人工蜂群算法求解全局QoS约束分解的方法中，我们在初始解的生成、邻域搜索变换等阶段时考虑解组合服务之间的关联关系，这样更加符合服务组合的实际情况，有利于缩短最优解的寻优时间，提高最优解的生成效率。同时，在复杂的网络环境中进行服务组合，动态的根据环境的变化可将服务的全局约束分解按照实际的服务需求进行全局优化，实现动态的服务组合。

下面给出基于I-ABC算法求服务组合最优解的过程描述。

算法1基于I-ABC的最优服务组合求解算法。

输入：组合服务类的数量；QoS全局约束；候选服务QoS值；QoS质量标尺；最大迭代次数MCN；解的数量SN；用户约束及偏好；控制参数limit。

输出：最优质量标尺组合。

步骤1确定候选服务集合。

IF(Si不属于集合QRS)//在服务关联数据集QRS中进行解的搜索；

选择候选服务Sj并判断否属于QRS；

Endif

步骤2初始化阶段。

Set parameterslimit,MCN,SN,counteri//设置循环次数、迭代次数、解的数量、更新次数；

For i=1 toSN

产生SN个食物源(解)并保留最优解；

Endfor

步骤3雇佣蜂操作过程。

For i=1 toSN//对每一个食物源

进行解的邻域搜索变换，并保留最优解；

If(当前的食物源质量没有改变)

counteri=counteri+1

Endif

Endfor

步骤4观察蜂操作过程。

For i=1 toSN//对每一个食物源

Endfor

For i=1 toSN//对每一个食物源

利用轮盘赌方式选择新解并进行解的邻域搜索变换，保留最优解；

If(当前的食物源质量没有改变)

counteri=counteri+1

Endif

Endfor

步骤5侦查蜂操作过程。

For i=1 toSN

If(limit大于给定值后，解未更新或者解的评价值降低)

进行解的变异操作，评价保留最优解。

Endif

Endfor

步骤6判断算法是否结束。

If(达到最大迭代次数MCN)

输出最优解BS并停止计算；

Else //没有到达结束的条件

迭代次数增加一次，返回步骤3。

改进的人工蜂群算法的流程如图5所示。

图5 改进的人工蜂群算法流程图Fig.5 Improved ABC flow chart

3 基于QoS关联感知的服务优化选择方法

3.1 候选服务QoS值的确定

在进行服务选择时，考虑上下游服务之间的QoS关联性，首先通过对服务历史数据的分析和挖掘来构建服务关联数据集。针对候选服务之间存在的关联服务质量变化情况，定义服务间的QoS相关性，若为负相关，相关服务的QoS值会因QoS相关性的存在而减小；若为正相关，相关服务的QoS值会因QoS相关性的存在而增大。将候选服务参与服务组合的实际QoS值与其服务本身的QoS值之间的比例关系定义为服务关联系数，该系数能够精确表达某一候选服务在服务组合中局部约束的QoS实际值，从而使全局QoS约束的分解能够与服务的实际运行情况保持一致，提高Web服务动态优化组合中服务选择的准确度和组合效率。

定义1服务关联数据集(QoS related set, QRS)，在服务组合中

(8)

(8)式中：1≤i,j≤n，(si,sj,…)为服务关联组合单元；(qsi,qsj，…)为对应该服务关联组合单元的QoS属性聚合值；n为组合服务节点个数；QRS称为服务关联数据集。

定义2服务关联关系(QoS relationship, QR)，在服务组合中

(9)

(9)式中：si,sj为服务关联数据集中的候选服务；QR(si,sj)称为服务关联关系。当QR(si,sj)的值为1时，称服务(si,sj)正相关，当QR(si,sj)的值为0时，称服务(si,sj)不相关，当QR(si,sj)的值为-1时，称服务(si,sj)负相关。

定义3服务关联系数(QoS related coefficient,QRC)，在服务组合中

(10)

(10)式中：Qsi为服务si的QoS属性值；qsi为在服务关联数据集中服务si的QoS实际值；QRC(si)称为候选服务si对应的服务关联系数，用于计算服务组合中具体服务的QoS实际值。

在执行过程中，判断已选服务si和当前候选服务sj之间的关联关系，若为负相关，则丢弃当前候选服务，若为正相关，当前候选服务QoS的值为Qsj·QRC(sj)。

在实际的商业运行中，不同领域的服务之间具有一定的关联关系，比如协约关联关系、统计关联关系等，服务之间这种关联关系是客观存在的。导致具有关联关系的服务在运行时，表现出不同的QoS值。因此，在进行服务选择时，需要考虑上下游之间的服务是否存在关联关系。支持服务关联关系的QoS评价模型能够更加客观的评价服务在不同情况下所表现出的服务质量有助于选出更加合适的服务，进而提高服务动态组合的质量。

3.2 基于关联的服务选择过程

在Web服务选择时，利用质量标尺将Web服务组合的全局QoS约束分解为局部QoS约束，局部约束给出了候选服务的服务质量上限或下限。考虑上下游服务之间的关联性，在动态的选择候选服务时，首先查找关联数据集中是否和已选服务存在关联关系，选择过程如图6所示。

图6 考虑QoS关联的服务选择过程示意图Fig.6 QoS-related service selection process

基于QoS关联的Web服务动态组合服务过程如下。

步骤1选择第一个候选服务。从候选服务集S1={S11,S12,…S1l}中随机选择满足局部约束CS1的候选服务(CSk为对应任务Ti的局部QoS约束，1≤k≤m，m为服务组合任务总数)。

步骤2选择的关联候选服务。对于候选服务Si(2≤i≤m)，首先动态查找服务关联数据集QRS，判断与已选定的候选服务Si-1是否存在有关联关系；若存在有关联，且关联关系QR(Si,Si-1)值为1，则选择当前服务质量满足约束条件为QRC(si-1)·CSi-1的候选服务。

步骤3选择最优Web服务组合。重复步骤2的过程，利用评价公式计算所选服务组合的评价值并进行比较，选择评价值最高的一组服务组合即为最优Web服务组合。

4 模拟实验

4.1 实验设计

本实验采用Java编程语言实现基于I-ABC的全局QoS约束优化分解算法以及考虑QoS关联关系的服务优化选择方法。其中，质量标尺数量设置为d=25；改进人工蜂群算法中的交叉率设为0.85，变异率设为0.05。算法运行环境为个人计算机，CPU为Intel 酷睿i5 7 500，内存为4 GByte，操作系统为Windows 7。

为验证本文方法的有效性，实验过程设计如下：服务组合由10个服务节点组成，每个服务类有n个候选服务(200≤n≤800)；设用户提出了4个全局QoS约束：①价格<120元(人民币)，②响应时间<150 s，③成功率>0.5，④信誉度>0.6。每个服务类的QoS属性质量标尺数为d，假定4个QoS属性偏好分别为0.3，0.4，0.2和0.1；10个任务节点所对应组合服务类的QoS取值如表1所示。

表1 QoS属性的取值区间

每个候选服务的QoS属性在相应的区间内随机生成。这里通过随机的方法确定具有QoS关联关系的服务，具有QoS关联关系的服务之间的关联QoS值的取值方式为：成功率与信誉度是上下游服务这2个QoS属性聚合值的1.2倍，价格与响应时间是上下游服务这2个QoS属性聚合值的2/3。

首先，利用本文所提出的改进人工蜂群算法将用户的全局QoS约束分解为满足要求的局部QoS约束；然后，在服务优化组合时，最优服务的选择是在考虑候选服务上下游之间的关联关系对组合Web服务QoS的影响的情况下，基于所构建的服务关联数据集完成的。

4.2 算法性能比较与分析

为了验证本文所提出的I-ABC算法在求解全局QoS约束分解问题时的有效性，该实验分别采用遗传算法(genetic algorithm, GA)、粒子群算法(particle swarm optimization, PSO)及I-ABC 3种方法对4.1节所设计的实验对象进行求解，其中，3种算法的初始群体规模设置为50，遗传算法的交叉概率设置为0.85，变异率设置为0.05；粒子群算法2个学习因子设置为2。实验结果如图7所示。其中，横坐标表示3种算法的迭代次数；纵坐标表示3种算法在求解全局QoS约束分解问题时获得解的评价值。从图7可以看出，改进的人工蜂群算法在求解全局QoS约束分解问题时，具有较好的性能。

图7 I-ABC算法全局QoS约束分解性能比较Fig.7 Performance comparison of I-ABC algorithm for global QoS constraint decomposition

在性能分析比较实验中设置了迭代次数为50，100，150，200，250，300，350，400情况下3种算法的性能比较，从实验结果可以看出，迭代次数越多，算法在求解全局QoS约束分解问题时获得解的评价值越高，算法执行花费的时间代价也越大。通过实验数据可以看出，问题的求解时间较短，能够满足服务动态优化组合对时效性的要求。

4.3 算法有效性验证

为进一步验证本文提出的基于QoS全局约束分解与关联感知的动态服务组合算法(该方法记为GQDQCC)的有效性，该实验首先应用本文所提出的方法对4.1节所设计的实验对象进行了求解，采用离散型人工蜂群算法在保证全局最优的情况下对同一个服务组合问题求解(该方法记为ABCSC)。在该实验中，人工蜂群算法的初始食物源规模设为100，Limit值设置为15。实验结果如图8所示，图8中的横坐标表示服务组合算法的运行时间(单位：s)，纵坐标表示服务组合算法搜索最优服务组合的评价值。

从图8可以看出，本文所提出的算法在服务组合过程中，根据服务之间的关联关系构建了服务关联关系数据库，缩小了候选服务的搜索范围，提高了搜索效率，能够在较短的时间内能够找到较优的服务组合。因此，本文所提出的基于全局QoS约束分解与QoS关联感知的服务动态优化组合方法是有效的。

图8 服务动态优化组合性能验证Fig.8 Dynamic optimization method for service performance verification

5 结束语

本文定义了一种支持服务关联关系的QoS评价模型，运用改进的人工蜂群算法求解全局QoS约束分解为局部约束的服务优化组合问题，模拟实验结果表明该方法在优化Web服务组合方面具有较高的求解效率。在后期的工作中，除了进一步优化组合服务关联模型之外，还需考虑受网络环境等因素的影响，候选服务质量的不稳定性、实时性和动态性因素，提高服务质量评价的准确度，为高效率的Web服务组合提供参考依据。