融合遗传聚类的可靠Web服务组合优化方法

张苑蕾，邵 清，李刘静，鲁建斌，张程斌

(上海理工大学 光电信息与计算机工程学院，上海 200093)

E-mail：sq_usst@126.com

1 引 言

近年来，随着科学技术的不断进步，互联网早已成为人们日常工作生活中不可缺少的一部分.为了能够更好地解决网络应用之间的互操作，提高数据的共享和存储效率，Web服务组合技术应运而生.由于单个Web服务提供的功能有限，人们开始将现存的多个平台独立的Web服务进行灵活、快速组合，实现数据的相互交换或集成，满足不同用户的需求.而在大数据环境下，随着用户需求越来越复杂，单个Web服务的不确定性增加，导致服务组合的难度也越来越大，对Web服务组合技术的要求也越来越高.

现有的Web服务组合优化方法主要分为两类：传统优化方法和智能优化方法.传统的优化方法由于存在可扩展性差、灵活性低等弊端，已经渐渐被智能优化算法所代替.智能优化算法主要融入了遗传算法、蚁群算法、模拟退火算法、混沌算法、烟花算法、聚类算法等[1-13]，这些算法能够较好地利用任务资源寻求服务组合的最优解，从而提高算法的综合性能和资源利用率.例如，文献[5,6]将混沌思想和遗传算法结合，实现种群的选择优化，提高了服务组合的效率，但服务组合的可靠性没有明显改善；文献[7]针对融合网络环境中出现的两类故障(临时性故障和永久性故障)，将模糊逻辑、多属性决策理论和改进的粒子群算法应用其中，三个主要模块之间相互作用，能够有效降低故障处理时间、故障排除率和组合最优度，但是针对临时性故障，所提方法中设置的固定重试频率在实际应用中不能完全适用；文献[8]将改进的烟花算法首次应用于离散服务的组合优化问题，并在建模过程中引入高斯变异概率和精英选择策略，有效降低算法的时间开销，但服务组合的可靠性没有得到验证；文献[13]通过利用Mashup服务相似性的K-means算法进行服务聚类，大大提高了Web服务搜索引擎检索相关服务的能力，但没有改善服务组合的可靠性.除上述研究算法之外，还有一些智能优化方法[14-16]将容错思想应用其中，以提高可靠性.例如，文献[14]采用一种面向事务性Web服务组合的FT模式推荐方法，在模式选择过程中引入4个组合级QoS因子进行优化，同时采用多目标优化算法，提高复合服务中的可靠性，但该方法在实际应用中的成功与否，很大程度上取决于服务所选QoS值的可用性和精确性；为了构建可靠的面向服务的体系结构/应用程序SOA，文献[15]利用服务复制策略进行容错，同时建立分布式的评估与选择框架，但由于缺乏用于研究Web服务性能和各种复制策略的实际数据，该模型框架只能在无状态Web服务上工作；文献[16]针对具有事务性特性的组合服务，建立了容错组合框架FACTS，能有效提高组合服务的容错性，但在动态网络环境中服务组合的可靠性无法验证.

综上分析，为了提高候选Web服务集的可靠性，改善组合优化性能，本文提出一种基于混合遗传聚类的可靠Web服务组合优化模型(IHGCA).该模型首先通过混沌映射产生初始组合服务集，并借助置信度表对服务集进行一次筛选，以提高组合可靠性.在此基础上利用遗传算法优化服务集，并以二次聚类为基础建立服务组合优化模型，最终收敛于全局最优解.实验结果表明，与传统优化方法相比，所提模型在提高可靠性指标的同时改善了组合优化度.

2 问题描述

假设一个Web服务组合SC=(W1，W2，…，Wm)由m个抽象服务组成，每个抽象服务都有一个候选服务集合Wi=(wi1，wi2，…，wij)，j个具体服务的功能属性相同，非功能属性不同，每个具体服务wij有s个QoS属性(q1，q2，…，qs).根据用户所提交的任务信息，从每个候选服务集合Wi中选择一个具体服务wij即可组成一个Web服务组合SC.

Web服务组合包括4种类型结构：顺序、选择、循环和并列，由于后3种类型均可转为顺序类型，因此本文只讨论顺序类型.

本文选用一个6元组表示QoS=(rt，pr，cr，re，av，th).其中，rt代表响应时间，pr代表价格，cr代表信誉度，re代表可靠性，av代表可用性，th代表吞吐量.根据属性对任务的影响效果，可将属性分为两类：一类是积极属性(正向指标)，如信誉度cr、可靠性re、可用性av、吞吐量th；另一类是消级属性(反向指标)，如响应时间rt、价格pr.

同时，为了能够更好地对Web服务组合进行评估，本文设置了一个适应度函数fitness，通过将单个Web服务组合的QoS属性按照下列公式进行计算，最终得出整体Web服务组合的QoS指标.适应度函数的计算如公式(1)所示：

(1)

3 可靠Web服务组合优化模型

3.1 样本数据预处理

在建立服务组合优化模型之前，需要先对Web服务组合集合、参数以及QoS属性指标进行归一化预处理，以消除不同指标之间的量纲影响，减少不必要的分析误差，确定统一的标准.

数据预处理主要包括初始化控制参数、初始化QoS属性指标以及初始化组合服务集三部分.

3.1.1 初始化控制参数

进行初始化的控制参数符号意义详见表1.

表1 控制参数符号代表的意义

3.1.2 初始化QoS属性指标

针对Web服务组合的非功能属性QoS=(rt，pr，cr，re，av，th)，根据“同一指标内部相对差距不同，不同指标之间归一化后极大值相等”的原则对其进行归一化预处理，即正向指标和反向指标分别采用公式(2)进行归一化：

(2)

需要注意的是，对于积极属性(正向指标)来说，数值越大，服务质量越好；对于消极属性(反向指标)来说，数值越小，服务质量越好.

3.1.3 初始化组合服务集

在遗传算法优化初始聚类中心之前，考虑到标准遗传算法GA本身具有反馈信息少、收敛速度慢、对初始组合服务集的选择有一定的依赖性以及容易陷入局部最优等缺点，本文首先通过混沌映射对Web服务组合集合Pw进行归一化预处理，并将其按照一定的规则或者潜在内在规律进行随机遍历搜索，获得全局最优解，从而产生初始组合服务集P(0).

混沌映射的计算如公式(3)所示：

(3)

3.2 基于置信度的初始组合服务集筛选

为了提高Web服务组合的可靠性，对初始组合服务集P(0)作进一步的筛选，本文选用置信度描述Web服务组合的可靠性.置信度定义为服务组合成功次数c在所有服务组合执行次数sum中所占的比例，用R表示，如公式(4)所示：

(4)

由公式可知，置信度越大，Web服务组合的可靠性越高.

由于不同的Web服务有着不同的置信度，将各Web服务的引用地址按照置信度进行排序，形成一张置信度表.根据置信度表对初始组合服务集P(0)进行一次筛选，得到t代规模为N的Web服务组合集P(t)={a1(t)，a2(t)，…aN(t)}，以提高服务组合的可靠性.置信度表的定义如下：

Typedef struct WebServiceNode{

Struct WebServiceNode *nextwsn；

//指向下一个服务的指针

Agent *info；

//该服务相关信息的指针

}WebServiceNode，AdjList[MAX]；

其中，服务Agent的属性用来描述Web服务的执行状态，WebServiceNode代表中间变量指针，AdjList则为置信度表的生成和更新过程中所采用的链表结构.在置信度表的生成过程中，对于一个已经存在的Web服务，根据其置信度，通过一个中间的WebServiceNode完成其插入操作.随着置信度的变化，Web服务在置信度表中的位置会及时更新.

算法1.置信度表的生成算法

CreateCreditTable(WebServiceNode Node，AdjList &adjList){

if adjList.length==0 then{//置信表为空

adjList[0]=Node；}

else{//置信表不为空

if Node.Agent.WSDL=adjList[i].Agent.WSDL then

{//置信表中有该服务，插入到对应的位置

WebServiceNode current；

Current=adjList[i]；

if current.next=null then{

Current.nextwsn=Node；}

else{

WebServiceNode temp；

Temp=current；

Current=Node；

Temp.nextwsn=Node.nextwsn；

Node.nextwsn=temp；}}

else{//置信表中没有该服务

Length++；

adjList[length]=Node；}}}

算法2.置信度表的更新算法

UpdateCreditTable(WebServiceNode Node，AdjList &adjList){

WebServiceNode current；

for(i=0；i

if(adjList[i].Agent.WSDL==Node.Agent.WSDL){

Node.Agent.R=Node.Agent.credit/

(adjList[i].Agent.credit/adjList[i].Agent.R+1)；

Break；}}

Current1=adjList[i]；

Current2=adjList[i]；

while(current1.nextwsn.Agent.key!=Node.Agent.key&¤t.nextwsn!=null){

Current1=current1.nextwsn；

Current2=current2.nextwsn；}

while(Node.Agent.R

{Current2=current2.nextwsn；}

Node.nextwsn=current2.nextwsn；

Current2.nextwsn=Node；}

3.3 可靠Web服务组合优化模型的建立

在对初始组合服务集P(0)进行一次筛选的基础上，建立满足用户需求的可靠Web服务组合优化模型.首先采用遗传算法优化初始聚类中心，再根据K-means算法对组合服务集进行粗略划分，最后利用AGNES层次聚类实现精确划分.

3.3.1 基于遗传算法的初始聚类

Web服务组合集初始聚类中心的选择对聚类结果影响较大.一旦初始值选择不好，可能导致其过早收敛于次优解，无法得到有效的聚类结果.因此在聚类之前首先通过遗传算法优化初始聚类中心，具体步骤如下：

Step1.选择操作.对于经过一次筛选后的Web服务组合集P(t)，采用如下操作进行选择：

fmax(t)=max{f(a1(t))，f(a2(t))，…，f(aN(t))}

fmax(t+1)=max{f(a1(t+1))，f(a2(t+1))，…，f(aN(t+1))}

iffmax(t)>fmax(t+1)then

(k=1，ork=1，2，…，K)

(j=1，orj=1，2，…，K)

endif

Step2.交叉、变异操作.本文采用一种自适应的交叉变异操作，以提高进化的稳定性.其中，自适应交叉、变异概率计算分别如公式(5)、公式(6)所示：

(5)

(6)

式中，fmax为组合服务集中最优Web服务的适应度；favg为集合的平均适应度；f′为要交叉的两个Web服务中较大的适应度；f″为要变异的Web服务的适应度.

Step3.上述组合服务集经过选择、交叉、变异运算后得到含p个Web服务的组合服务集Xi(i=1，2，3，…，p).经过实验验证，p取值一般为[30，150]，同时将进化最为活跃且交叉概率Pc和变异概率Pm分别在[0.6，0.9]和[0.001，0.05]范围内的q个组合服务集Yi(i=1，2，3，…，q)作为遗传优化后的初始聚类中心.

3.3.2 基于K-means的一次聚类

将组合服务集Yi(i=1，2，3，…，q)划分成k个互补相交的Web服务组合子集Si(i=1，2，3，…，k).

将选取类内距极小化而类间距极大化的组合服务集Ti(i=1，2，3，…，z)作为一次聚类的结果.

算法3.一次聚类的实现步骤

将选出的k个点作为初始质心

Repeat

将每个点分配到最近的质心，形成k个组合服务集；

计算测度函数f(k)；

重新计算每个组合服务集的质心

Until组合服务集不发生变化或达到最大迭代次数

算法采用的测度函数f(k)用来描述在类别数尽可能小的情况下所得数据的紧凑度和分离度，具体定义如公式(7)所示：

(7)

式中，Dk为类间距，Ek为类内距.

3.3.3 基于AGNES的二次聚类

在一次聚类的基础利用AGNES层次聚类对服务集Ti(i=1，2，3，…，z)进行精确的划分.

算法4.二次聚类的算法描述

输入：将K-means一次聚类的结果作为输入，终止条件组合服务集的数目设为K

输出：K个组合服务集Zi(i=1，2，3，…，K)

过程：

将每个对象当成一个初始组合服务集

Repeat

根据两个组合服务集中最近的数据点找到最近的两个组合服务集；

合并两个组合服务集，生成新的Web服务组合集合

Until达到定义的组合服务集的数目

综上，IHGCA模型整体结构如图1所示.

图1 服务组合优化模型

4 仿真实验

4.1 实验数据

为验证IHGCA模型能有效提高候选组合服务集的可靠性，本文以模拟用户设定的旅游计划的Web服务组合为例，进行仿真实验分析.实验采用11个原子服务组成的模拟旅游查询组合服务.具体解释如下：

w1：用户注册

w2：登录

w3：出发地和目的地信息确认

w4，1：目的地天气信息查询

w4，2：出发地到目的地车票信息查询

w4，3：目的地旅馆信息查询

w5：旅行社信息查询服务

w5，1：跟团游线路推荐

w5，2：半自助游线路推荐

w6：自由行线路推荐

w7：支付确认

该旅游查询系统的服务关系图如图2所示.由图2可知，首先将各个旅游地点的相关信息进行混沌初始化；然后根据用户的个人基本信息及旅游喜好进行初始组合服务集的一次筛选，确定出发地和目的地；接着根据用户的个人旅游习惯进行遗传优化，选择合适的出行方式；最后通过成功订单信息及用户反馈评价进行一次聚类，筛选出用户出行最高的旅游地点和好评最佳的旅游信息服务，通过未完成支付订单和差评订单进行二次聚类，筛选出仍有待改进的旅游信息服务，进一步完善旅游查询系统的功能.

图2 旅游查询系统服务关系图

服务组合包含的任务数目设置为10-50，候选服务的数量设置为50.实验一共进行50次，每类实验分别按照任务数量从5开始，以5递增的规律进行，最终结果是以实验数据在50次仿真实验所得结果的基础上取平均值.实验相关参数及QoS属性取值范围详见表 2、表3.

表2 实验参数设置表

表3 QoS属性的取值范围

4.2 评价指标

1)平均故障间隔时间MTBF：在服务组合的执行过程中，相邻两次故障之间的平均工作时间.它反映Web服务组合产品在规定时间内保持功能的能力.

设有一个可修复的Web服务组合产品在使用过程中，共发生N0次故障，并且每次故障经过修复后又和新产品一样继续投入使用，其工作时间为T1、T2、T3、T4、T5、T6……T0.那么，平均故障间隔时间的计算如公式(8)所示：

(8)

由公式可知，MTBF的值越大，可靠性越高，正确工作能力越强.

2)故障排除率FRR：能被排除的Web服务组合故障次数和在服务组合的执行过程中出现的总故障次数之比.设NT为组合服务执行过程中出现的总故障次数，NP为能被排除的Web服务组合故障次数，故障排除率的计算如公式(9)所示：

(9)

由公式可知，FRR的值越大，故障排除能力越高，可靠性越高.

3)组合最优度CO：组合服务的效用函数值.其值的大小可以代表组合服务的QoS属性的优劣.为了简化效用函数的计算，本文只考虑原子服务的响应时间和吞吐率这两个QoS属性，并将它们的权重均设定为0.5.组合最优度的计算如公式(10)所示：

(10)

其中，Nε为组合服务包含的原子服务个数，rε和thε分别为进行归一化后的服务ε的响应时间和吞吐率.

由公式可知，CO的值越大，代表QoS属性越优.

4)响应时间RT：从用户发出请求或指令到Web服务组合系统做出反应的时间.响应时间的计算如公式(11)所示：

(11)

其中，wi为单个Web服务执行的响应时间，n为系统中Web服务组合的数量.

由公式可知，RT的值越大，系统响应时间越长.

4.3 仿真结果及分析

为了验证模型的有效性，本文选取ChaosGA[5]、FCluster[13]、RS[15]、FACTS[16]四种方法进行对比实验.实验采用java语言进行仿真模拟，具体运行环境为JDK1.8，Win10操作系统，i5-7300U处理器.实验结果如图3-图6和表4所示.

图3 平均故障间隔时间对比图

从图3可以看出，当任务数量较小(小于25)时，IHGCA模型虽然较其他4种方法的MTBF值高，但整体优势不明显，这是由于建模过程中对组合服务集进行多次筛选和划分所导致的时间资源浪费.而当任务数量增大(大于25)时，IHGCA模型在MTBF上的优势开始凸显，其原因是建模前期对服务组合集的多次筛选减少了故障次数，可靠性得到增强.

图4 故障排除率对比图

从图4可以看出，随着任务数量的增加，IHGCA模型计算的FRR值逐渐增大.当任务数量小于20时，FRR值并不高，当任务数量大于20时，所提方法的FRR值开始高于其他4种方法.原因在于IHGCA模型在建模过程中，不仅借助置信度表对初始组合服务集进行一次筛选，而且还利用遗传算法优化初始聚类中心，以上两种举措均提高了服务组合的故障排除能力.

图5 组合最优度对比图

从图5可以看出，随着任务数量的增加，本文所提方法的组合最优度逐渐增大，并且高于其他4种方法.这是因为IHGCA模型引入混沌理论，弥补了遗传算法收敛速度慢、易陷入局部最优的缺点，同时加快了搜索速度，也易于实现全局渐进收敛，从而获得全局最优解.此外通过二次聚类减少了对初始值的选择依赖，提高整体聚类效果.

图6 响应时间对比图

从图6可以看出，随着任务数量的增加，5种方法的响应时间均逐渐增大.其中ChaosGA的平均响应时间最短，FACTS则最长.而IHGCA模型的优势不明显，这是由于建模过程中对组合服务集进行多次筛选和划分所导致的时间资源浪费.

表4 主要评价指标对比结果(任务数量=50)

5 结束语

为了提高Web服务组合可靠性和组合效率，本文提出一种基于混合遗传聚类的可靠Web服务组合优化方法.该方法在混合聚类算法的基础上建立可靠服务组合优化模型，并获取全局最优解.该模型在最初设计时，充分考虑了遗传算法GA易于陷入“早熟”和K-means算法比较依赖于初始聚类中心的弱点，并且在实施阶段，分别引入混沌思想和遗传算法进行优化，同时利用置信度表和二次聚类的方法对组合服务集进行多次筛选和划分.仿真实验充分验证了本文所提出的Web服务组合优化模型在可靠性方面具有一定的优势.

但是，由于互联网环境的多变性和Web服务组合的不确定性，导致组合服务的非功能特性QoS也在不断发生变化.设计一个面向动态的组合Web服务的自适应算法，并以此来适应用户多变的需求条件，将是我们未来需要进行研究的工作.