面向成本最小化的组合服务可靠性优化分配

李昌志，付晓东，2，田 强，王 威，夏永滢

(1.昆明理工大学信息工程与自动化学院，昆明 650500;2.云南省计算机技术应用重点实验室，昆明 650500)

1 概述

Web 服务是一种基于网络环境的、模块化的应用程序［1］，具有松散耦合、平台无关、互操作性强等特点［2］。在单个Web 服务无法满足用户需求的情况下，可以将若干个Web 服务组合起来协同工作。Web 服务组合(也称为组合服务)是指将若干个已存在的Web 服务按照一定规则动态发现，并组装成一个增值的、更大粒度的服务或系统以满足用户复杂需求的过程［3-4］。

由于被组合的Web 服务是由不同组织发布、分布在Internet 上，具有自治特征的软件组件，开放、动态、难控的网络环境下实现各类Web 服务资源集成和共享的Web 服务组合，服务质量(Quality of Service，QoS)成为决定其能否成功的关键因素之一［5］。Web 服务的QoS 指服务的响应时间、价格、可用性、可靠性、信誉等非功能属性［6］，在开放和动态的网络环境下，提供具有QoS 保证的Web 服务是非常必要的，所谓QoS 保证就是在服务计算模式下，协调属于不同组织与机构的各种服务，在问题求解过程中保证服务的质量［7］。而可靠性是提供具有QoS保证服务的基础，没有可靠性保证的Web 服务，其他服务质量属性就无从谈起。为此，本文对Web 服务组合的可靠性进行分析和研究，将Web 服务组合的可靠性指标约束分配给各组件服务(组件服务是指Web 服务组合的基本构成元素)，而组件服务的可靠性又与成本(成本指的是组合服务达到一定的可靠性投入的费用)密切相关。为了实现可靠性目标且成本最小化，本文提出基于遗传算法的Web 服务组合可靠性分配方法，建立可靠性分配优化模型，模型以定量的方式将Web 服务组合的可靠性指标分配给组件服务并使得成本最低。这样在保证Web 服务组合高可靠性的前提下，对可靠性指标进行了合理分配，控制了成本，优化了资源配置。

2 相关工作

近年来，一些学者站在不同的角度对Web 服务组合的可靠性做了一系列研究，如文献［8-9］，提出了一种将全局QoS 约束分解为局部约束，通过局部约束找到全局最优或近似全局最优的Web 服务组合。文献［10］提出了一种基于Petri 网分析Web 服务组合可靠性的方法，探索了可靠性数据的采集。文献［11］针对服务组合中的可靠性和相关性能评估问题，提出了一种基于离散时间马尔可夫链(Discrete Time Markov Chain，DTMC)的评估方法，从不同运行场景的角度，利用DTMC 相关性质和公式综合估算了服务组合的可靠性，并针对具体服务组合的瓶颈进行了分析，提出了改进措施。文献［12］提出一种可靠性优化方法，利用恢复块和N 版本程序设计可以有效地增强服务组合的可靠性，该文在服务组合的可靠性预测模型的基础上，提出了2 种可靠性优化模型。文献［13］提出面向服务的基于体系结构的可靠性分析方法，给出了一种体系结构以实现可靠性预测。

以上研究只考虑了Web 服务组合的可靠性［10-11］，没有考虑组件服务的可靠性，并且对提高Web 服务组合可靠性的成本没有进行控制。再者利用Petri 网［10，12］对Web 服务组合进行建模，只能表达出Web 服务组合的逻辑及服务之间的关系，不能对Web 服务组合流程进行定量分析。文献［13］只处理了2 种结构，并未考虑到Web 服务的多种结构。针对上述问题，本文在多种组合模式下，分析每种组合模式特点及其可靠性，既能清晰表达Web 服务组合之间的逻辑关系，又能对Web 服务组合流程进行定量分析，并通过可靠性分配优化模型，将可靠性指标合理地分配给组件服务，同时把成本控制到最低。

3 Web 服务组合流程及其可靠性

在Web 服务组合中，通常在结构化流程的基础上对其进行研究［14］，即服务之间可以嵌套，不能交叉。结构化流程可以表示大多数Web 服务组合场景，并且非结构化流程可以转换为结构化流程［15］。因此，本文重点考虑结构化组合流程的可靠性分配问题。文献［16-17］总结了4 种Web 服务组合模式:顺序，循环，选择，并行。在此基础上本文也考虑这4 种组合模式，即Sequence，Loop，XOR，AND 组合模式，如图1 所示。在每种组合模式下，对其可靠性进行分析。

图1 Web 服务组合模式

Sequence 的执行语义是顺序执行包含在该结构中的组件服务(如图1 中的CP1)。假定包含的组件服务的数量为N，则Sequence 模式的可靠性为:

其中，R(si)为组件服务si的可靠性。

Loop 的执行语义是某一组件服务的重复执行(如图1 中的CP2)。假定组件服务si重复执行N 次，则Loop 模式的可靠性为:

XOR 的执行语义是多个分支的选择执行，也就是从多个执行分支中选择一个分支执行(如图1 中的CP3)。假定分支的数目为N，执行组件服务si的概率为pi，并且满足约束，则XOR 模式的可靠性为:

AND 的执行语义是所包含的多个组件服务的并行执行(如图1 中的CP4)。假定包含的组件服务数量为N，则AND 模式的可靠性为:

基于以上分析，通过一个实例来计算Web 服务组合的可靠性。假如有Web 服务组合流程如图2 所示，该Web 服务组合流程中有7 个组件服务，即S1，S2，S3，S4，S5，S6，S7。从整体来看，S1，AND 模式，S7组成一个Sequence 模式，其中AND 模式有2 个分支，即S2，XOR 模式和S3，LOOP 模式2 个分支，这2 个分支分别是一个Sequence 模式，其中，XOR 模式包含2 个分支S4，S5，LOOP 模式包含1 个组件服务S6。该组合流程的可靠性为:

图2 Web 服务组合流程

4 组合服务可靠性分配优化模型

组合服务的可靠性分配优化模型需要将可靠性指标合理分配给组件服务，同时将成本最小化。因此，模型要求组件服务的可靠性与成本之间存在一种定量关系。本节首先给出了表示这种关系的可靠性成本函数，再给出可靠性分配优化模型。

4.1 可靠性成本函数

文献［18-19］概括了表示可靠性和成本之间的定量关系函数。在此基础上，本文将可靠性成本函数归纳为2 类:线性函数和非线性函数，这2 类函数表达式分别为式(6)～式(7)，图3～图4 分别为2 类函数的示例图。这2 类函数都源于可靠性和成本之间的真实假设，即关于可靠性R(si)的成本函数是严格递减的，则且呈现凸性，则

图3 线性成本函数

图4 非线性成本函数

线性可靠性成本函数:

非线性可靠性成本函数:

4.2 可靠性分配优化模型

可靠性分配是指将Web 服务组合的可靠性指标合理地分配给组件服务，以确定该Web 服务组合各组件服务的可靠性定量要求，从而保证整个Web 服务组合的可靠性指标，合理分配各组件服务的可靠性有助于提高Web 服务组合的经济性和安全性［20］。

本文提出基于遗传算法的可靠性分配方法，先由式(5)得到Web 服务组合流程的可靠性，此可靠性大于给定的可靠性指标R*作为约束，再通过组件服务的可靠性和成本之间的关系函数，得到总成本，此总成本作为目标函数，至此就获得了Web 服务组合的可靠性分配优化模型。然后利用遗传算法求解模型，获得组件服务的可靠性，即实现了对组件服务的可靠性分配，保证了Web 服务组合的高可靠性指标，同时将成本控制到最低。可靠性分配优化模型如下:

在式(8)中，由于被选择的服务是有限的(服务选择是指从功能相同、非功能特性各异的服务中进行选择，更多服务选择知识请参考文献［21-22］)，模型假设被选择的服务中，可靠性的下限值为li，上限值为ui;C(R(si))是组件服务的成本函数;Rs为Web 服务组合的可靠性。

5 遗传算法求解模型分析与设计

Web 服务组合可靠性分配本质上是一个数学规划问题，一般来说，使用传统的优化算法可以进行求解。但是，如图5 所示函数构成的优化问题具有非线性和多极值的特点［23］，使用传统方法来寻求最优解是比较困难的，而遗传算法本身固有的全局优化能力和潜在的并行性，使得它非常适用于具有复杂约束的优化问题［23］。遗传算法的基本原理是仿效生物学中适者生存演变而来。遗传算法的做法是把问题参数编码为染色体，再利用迭代的方式进行选择、交叉以及变异等运算规则来交换种群中的染色体信息，最终生成符合优化目标的染色体。

(1)染色体编码

首先，需要针对模型设计染色体，包括基因字串的长度以及基因代表的含义，即对搜索空间的可行解以编码的形式来呈现。一般的编码方式采用二进制、格雷码、浮点数、多参数级联等编码方式。

显然，本文模型具有高精度要求，采用具有高精度和搜索空间大的浮点数编码方式［24］，对于具有n 个组件服务的Web 服务组合，定义一个n 维向量X=(x1，x2，…，xn)来对染色体进行编码，向量中每一位为相应组件服务的可靠性预留位置，并且每一位都保留到小数点后面第3 位，以便可靠性的精度精确到千分位(因为可靠性必须满足0 ＜R(si)＜1)，如X=(0.559，0.958，0.982)是具有3 个组件服务的染色体编码，其中每一位为相应组件服务的可靠性编码，即第1 个组件服务的可靠性为0.559，第2 个组件服务的可靠性为0.958，第3 个组件服务的可靠性为0.982。

(2)种群初始化

对染色体实现编码以后，必须产生一个初始种群，因此，首先需要确定初始化种群的数目。初始化种群的数目一般根据经验得到，如果初始化种群的数目太大，则可能会消耗过多的搜索时间，但是如果太小，则会导致过早收敛［25］。一般情况下种群的数量视搜索空间的大小而确定，在种群初始化时采用随机方式产生，并根据实验部分的经验将种群的大小限制在40～160 之间，因为对于本文模型，大小在这之间的种群具有良好的收敛性且时间消耗低。

(3)适应度函数的设定

适应度函数必须满足单值、连续、非负和最大化，优化模型中目标函数显然满足单值、连续、非负条件，需要将目标函数乘以-1 转化为最大化并加上一个较大的常数M 保证其非负性。因此，修正后的适应度函数为:

(4)终止条件设定

严格地讲，遗传算法迭代终止条件目前尚无定论［26］。在许多组合优化问题中，适应度最大值并不清楚，其本身就是搜索的对象，因此，终止条件很难确定。

采用式(8)的约束条件作为迭代的终止条件，发现合适的染色体解码后能够满足式(8)的约束条件时，终止迭代。如果满意解并不存在，而搜索空间又非常庞大，在这种情况下，若发现群体中个体的进化已经趋于稳定状态时，终止迭代。

(5)选择算子

选择操作是从种群中选择优胜个体，并淘汰劣质个体。选择的目的是把优化的个体直接遗传到下一代，或者通过配对交叉产生新的个体再遗传到下一代。常用的选择算子包括适应度比例法、最佳个体保留法、期望值法、排序选择法等。选择最基本和最常用的适应度比例法［27］来对种群中的个体进行选择。

(6)交叉算子

交叉算子是遗传算法中起核心作用的遗传操作。交叉是指2 个父代个体的部分结构加以替换、重组而生成新个体的操作。常用的交叉算子包括一点交叉、二点交叉、多点交叉、一致交叉等。选择工程上使用较多的二点交叉算子［24］，并选择交叉概率为0.5。

(7)变异算子

变异算子的基本内容是对群体中个体串的某些基因座的基因值作变动。对于浮点数编码，在可靠性范围［li，ui］内，变异操作就是用该范围内的一个随机数去替换原基因值;一般来说，变异算子操作的基本步骤如下:

1)在群体的所有个体的码串范围内随机确定基因座;

2)以事先确定的变异概率对这些基因座的基因值进行变异。

选用基本变异算子，并选定变异概率为0.001。

6 实验验证及分析

本文通过实例说明可靠性分配过程，通过模拟验证本文方法实现成本优化的有效性和实用性，最后是收敛性分析。实验环境为2 GB 内存、Inter Pentium T2370(1.73 GHz)、Windows XP 操作系统，实验工具采用Matlab R2009a。

6.1 实例

Web 服务组合流程如图2 所示，不失一般性，设循环次数k=3，p1=p2=0.5。

6.1.1 线性成本函数

设成本函数为f(R(si))=a×R(si)+b，组件服务s1-7对应的参数为a=［325，181，165，22，22，60，245］，b=［19，29，200，280，263，200，65］，li=0.01，ui=0.99，Web 服务组合的可靠性指标约束R*=0.930，由式(8)有:

利用遗传算法求解得到组件服务的可靠性分配结果为R(s1-7)=［0.559，0.958，0.982，0.010，0.989，0.990，0.731］，所需成本C=1 833.5。

从实验结果看，根据可靠性分配优化模型分配的可靠性，S6需要选择可靠性值最高的组件服务，而S1-5，S7选择合适的可靠性值就能够达到可靠性指标R*=0.930。

6.1.2 非线性成本函数

设成本函数为f(R(si))=-bln(1 -exp(R(si)-1))，组件服务s1-7对应的参数为b=［20，40，70，80，100，120，140］，li=0.01，ui=0.99，Web 服务组合的可靠性指标为R*=0.930，求解模型同线性成本函数，此处不再赘述。得到组件服务可靠性分配结果为R(s1-7)=［0.959，0.907，0.851，0.015，0.236，0.917，0.769］，所需成本C=924.5。

由可靠性分配优化模型分配的可靠性来看，所有组件服务都没必要选取最高可靠性值就能达到可靠性指标R*=0.930。

6.2 有效性验证

为验证本文方法的有效性，与取最高值法［28］、等分配法［20］等可靠性分配方法进行了比较。本文首先在成本函数变化，组件服务数量固定的情况下进行模拟;然后模拟真实环境下本文方法的有效性和实用性。

设成本函数变化，组件服务数量固定(7 个)，并用这7 个组件服务组合成5 种以上不同结构的Web 服务组合流程。由式(8)得到每种结构的可靠性分配优化模型，然后取成本的期望值，这样有效避免了个别流程的特殊性。实验结果如图5、图6 所示，以取最高值法为基准，记录其他方法所需成本所占百分比随成本函数变化的情况。实验结果表明，当成本函数为线性时，与取最高值法相比，本文方法最少节约成本19.56%，最多节约成本62.67%，与等分配法相比最少节约成本19.54%，最多节约成本62.61%;当成本函数为非线性时，与取最高值法相比，本文方法最少节约成本37.93%，最多节约成本37.96%，与等分配法相比，最少节约成本37.29%，最多节约成本37.40%。

图5 不同成本函数(线性)成本花费对比

图6 不同成本函数(非线性)成本花费对比

在真实环境下，组件服务的数量是不同的，且不同组件服务的成本函数不一样。所以为验证本文方法在真实环境下的有效性和实用性，做了如下实验。组件服务数不同，不同组件服务的成本函数不同，并且不同组件服务数量都组合成5 种以上不同结构的Web 服务组合流程。由式(8)得到每种结构的可靠性分配优化模型，再对成本取期望值。实验结果如图7、图8 所示，以取最高值法为基准，记录其他方法所需成本所占百分比的情况。实验结果表明，当成本函数为线性时，与取最高值法相比，本文方法最少节约成本超过8%，最多节约成本17.60%，与等分配法相比，最少节约成本7.90%，最多节约成本超过17%;当成本函数为非线性时，与取最高值法相比，本文方法最少节约成本40.20%，最多节约成本55.22%，与等分配法相比，最少节约成本39.55%，最多节约成本47.36%。

图7 线性成本花费对比

图8 非线性成本花费对比

经过模拟对比实验，结果表明本文方法始终优于取最高值法和等分配法，验证了本文方法的有效性和实用性。

6.3 收敛性分析

适应度函数的收敛情况如图9、图10 所示。其中，算法的终止条件为找到了满意解，在不超过10 代的情况下，就找到了满意解，表明遗传算法应用于本文优化模型具有很好的收敛性。图9 的最佳适应度为1 634.138，平均适应度为1 977.204。

图9 最佳及平均适应度值情况

图10 最佳、最差及平均适应度值情况

7 结束语

在开放和动态的网络环境下，提供满足可靠性要求的低成本Web 服务组合具有非常重要的意义。为此，本文研究了Web 服务组合的可靠性和成本优化问题，提出基于遗传算法的Web 服务组合可靠性分配方法，分析了Web 服务组合结构模式及其对应的可靠性函数，进一步给出组合服务的可靠性计算方法，建立可靠性分配优化模型，并利用遗传算法对模型进行求解，这样既保证了Web 服务组合的高可靠性要求，又将可靠性指标合理地分配给组件服务，同时使得所需成本最小化，具有现实的意义。最后模拟实验验证了本文方法的有效性和实用性，并验证了其收敛性。

在获得可靠的、低成本的Web 服务组合的方法后，结合QoS 的其他非功能属性信息，解决随机QoS感知的Web 服务选择和组合的问题，是下一步要开展的研究工作。

［1］邓水光，尹建伟，李 莹，等.基于二分图匹配的语义Web 服务发现方法［J］.计算机学报，2008，31(8):1364-1375.

［2］宋 巍，马晓星，吕 建.Web 服务组合动态演化的实例可迁移性［J］.计算机学报，2009，32(9):1816-1831.

［3］李喜彤，范玉顺.Web 服务流程相容性和相似性分析［J］.计算机学报，2009，32(12):2429-2437.

［4］郭玉彬，杜玉越，奚建清.Web 服务组合的有色网模型及运算性质［J］.计算机学报，2006，29(7):1067-1075.

［5］肖芳雄，黄志球，曹子宁，等.Web 服务组合功能与QoS的形式化统一建模和分析［J］.软件学报，2011，22(11):2698-2715.

［6］Hwang S Y，Wang Haojun，Tang Jian，et al.A Probabilistic Approach to Modeling and Estimating the QoS of Web-services-based Workflows［J］.Information Science，2007，177(23):5484-5503.

［7］殷宪振，蒋 静，潘振宽，等.SoC 应用系统中基于信用的QoS 保证机制［J］.计算机学报，2011，34(2):413-424.

［8］王尚广，孙其博，杨放春.基于全局QoS 约束分解的Web 服务动态选择［J］.软件学报，2011，22(7):1426-1439.

［9］Alrifai M，Risse T.Combining Global Optimization with Local Selection for Efficient QoS-aware Service Composition ［C］//Proc.of the 18th International Conference on World Wide Web.Madrid，Spain:［s.n.］，2009:881-890.

［10］郭 峰，张 萌.Web 服务组合的可靠性分析［J］.系统仿真学报，2009，20(s2):94-96.

［11］曹科强，顾 庆，任颖新，等.服务组合中基于DTMC的可靠性和性能分析［J］.计算机科学，2009，36(10):179-183.

［12］钟读杭，齐治昌.基于冗余的Web 服务组合可靠性优化方法［J］.计算机工程，2008，34(4):31-33.

［13］Grassi V，Patella S.Reliability Prediction for Service Oriented Computing Environments［J］.IEEE Internet Computing，2006，10(3):43-49.

［14］Vander Aalst W M P，Hofstede A H M，Ewski B K，et al.Workflow Patterns ［J］.Distributed and Parallel Databases，2003，14(3):5-51.

［15］Chan P P W，Lyu M R.Dynamic Web Service Composition:A New Approach in Building Reliable Web Service［C］//Proc.of the 22nd International Conference on Advanced Information Networking and Applications.Ginowan，Japan:［s.n.］，2008:20-25.

［16］Zhang Guoping，Zhang Huijuan，Wang Zhibin.A QoSbased Web Services Selection Method for Dynamic Web Service Composition［C］//Proc.of the 1st International Workshop on Education Technology and Computer Science.Wuhan，China:［s.n.］，2009:15-29.

［17］蒋哲远，韩江洪，王 钊.动态的QoS 感知Web 服务选择和组合优化模型［J］.计算机学报，2009，32(5):1014-1025.

［18］Helander M E，Zhao Ming，Ohlsson N，et al.Planning Models for Software Reliability and Cost［J］.IEEE Transactions on Software Engineering，1998，24 (6):420-434.

［19］沈雪石，陈英武.基于可靠性的软件构件费用分配最优模型［J］.系统工程与电子技术，2007，29(12):2186-2188.

［20］曾声奎，冯 强.可靠性设计与分析［M］.北京:国防工业出版社，2011.

［21］蒋哲远，韩江洪，王 钊.动态的QoS 感知Web 服务选择和组合优化模型［J］.计算机学报，2009，32(5):1014-1025.

［22］吴 健，陈 亮，邓水光，等.基于Skyline 的QoS 感知的动态服务选择［J］.计算机学报，2010，33(11):2136-2146.

［23］Tian Pei，Wang Jiancheng，Zhang Wei，et al.A Fault Tree Analysis Based Software System Reliability Allocation Using Genetic Algorithm Optimization［C］//Proc.of World Congress on Software Engineering.Xiamen，China:［s.n.］，2009:194-198.

［24］雷英杰，张善文，李续武，等.Matlab 遗传算法工具箱应用［M］.西安:西安电子科技大学出版社，2006.

［25］代桂平，王 勇，侯亚荣.基于遗传算法的TSP 问题求解算法及其系统［J］.微计算机信息，2010，2(2):15-16.

［26］王 勇，胡春明，杜宗霞.服务质量感知的网格工作流调度［J］.软件学报，2006，17(11):2341-2351.

［27］周 明，孙树栋.遗传算法原理及应用［M］.北京:国防工业出版社，1999.

［28］张仕健，许 彤，张隆兵，等.一个基于微处理器功能模型的可靠度评估系统［J］.计算机学报，2008，31(3):391-399.