结合语义与事务属性的QoS感知的服务优化选择

杨万春　张晨曦　穆斌

摘要：服务级别协议（SLA）等级感知的服务选择是NP难题。针对服务选择中维度与粒度方面的问题，提出结合语义与事务属性的服务质量（QoS）感知的服务优化选择模型。该模型从语义链接匹配度、QoS与事务三个维度对服务进行优化选择， 并设计了支持多粒度的编码策略。针对服务选择中时间复杂度高的问题，提出了克隆选择与遗传算法相结合的混合优化算法。该算法首先采用动态适应度函数，逐代淘汰不满足约束的个体；其次给出了事务属性的优先级，并根据优先级设计了知识启发式的交叉与变异算子，以保证个体满足事务属性要求；最后在遗传算法中对优秀个体进行克隆选择，以增强对最优解的搜索能力。仿真实验中，该算法在服务选择的精确度和成功率方面均优于遗传算法；在时间花费上稍高于遗传算法但远低于穷举法。实验结果表明，所提算法能在较少时间花费的基础上保证服务选择的质量。

关键词：语义链接匹配度；服务质量；事务属性；克隆选择；遗传算法；服务选择

中图分类号：TP393

文献标志码：A

0引言

近年来，面向服务的计算，尤其是云计算技术得到了快速的发展。面向服务的计算模式能够把现有的服务无缝地进行整合，从而产生新的增值服务以满足用户的需求。随着网络上服务数量的爆炸性增长，功能相似的服务也越来越多，如何在满足服务级别协议（Service Level Agreement， SLA）下，从候选服务集合中选择服务是一个热点研究课题。文献[1-2]将基于服务质量（Quality of Service， QoS）的服务选择问题转换为多维背包问题，并采用整数规划方法寻找最优的组合服务。当候选服务数量较少时，整数规划方法很有效，但当服务数量增多时，其花费的时间以指数的速度增长。为提高服务选择的效率，文献[3-4]将全局约束分解为满足用户偏好的局部约束，然后根据局部约束进行服务选择，从而获得最合适的组合服务。文献[5-6]利用支配关系对候选服务进行筛选，可以减少服务选择的范围。用户只需从Skyline 服务中进行服务选择，就能得到满足全局约束的最优组合服务，从而缩小了搜索空间，但Skyline 服务筛选只能看作服务选择的预处理阶段。文献[7]针对服务的粒度问题，构建了多维QoS约束的最优路径搜索模型，给出了基于任务和规划的多粒度服务的裁剪方法，但在多粒度的服务选择效率上有待提高。

智能优化算法用于求解各种工程问题的优化解，现已被广泛地应用于服务选择中。文献[8]给出了一种基于非均衡变异的粒子群算法来解决服务选择问题。该算法设计了非均衡变异函数，并将自适应权重调整机制和局部适应优先策略应用于粒子的速度和位置更新中。文献[9]将基于贪婪搜索的逼近策略加入到蚁群算法中，给出了基于改进蚁群算法的服务优化选择方法。文献[10]在蚁群算法中加入信息素的分布策略和更新依据，并采用局部优化策略避免陷入局部最优。文献[11]将模拟退火、和声搜索与遗传算法相结合以解决服务选择问题。以上研究采用不同的方法解决了QoS感知的服务选择问题，但是它们在服务选择过程中没有考虑服务之间的语义匹配关系[12]。

由于网络的不稳定特性降低了组合服务的可靠性，因此需要在服务选择中考虑事务属性。针对组合服务的事务属性问题，文献[13]给出了满足事务约束和QoS 端对端约束的服务选择方法，该方法将局部QoS 选择嵌入到满足事务性约束的服务选择中，但在求解全局QoS 最优方面存在不足；文献[14]设计了顺序和并发服务流程的事务属性规则，并给出了基于蚁群算法的QoS感知的事务性服务选择方法；文献[15]构造了层次服务候选图模型，并提出了基于广度优先搜索的QoS感知的事务级服务选择算法；文献[16]采用遗传算法来解决事务性服务的组合问题，但该算法采用传统的交叉和变异算子，故无法保证组合服务的事务属性。

综上所述，现有的研究大多是基于QoS来进行服务选择，即从候选服务中选择恰当的服务进行组合以满足用户提出的QoS需求。但用户的需求是多维度的，除了QoS之外，用户还会对组合服务的事务属性与语义匹配度方面提出需求。组合服务是由若干个服务组件按照一定的流程结构组合而成的，而现有的研究大多考虑的是细粒度服务的组合，因此无法构建所有粒度组合的可能。在服务选择的过程中，现有的算法在精确度和成功率方面还存在不足，因此需要设计面向多维度与多粒度的服务选择算法，使其能够在时间花费和最优解之间加以折中，即在较低的时间花费下得到满足用户需求的近似最优解。 基于上述分析，本文主要作了以下工作：

1）从语义链接匹配度、QoS与事务三个维度对服务进行选择，并综合考虑了服务粒度，建立了服务优化选择模型；

2）在该服务优化选择模型基础上设计了知识启发式的交叉、变异算子，提出了基于克隆选择与遗传算法的混合优化算法；

3）通过仿真实验验证了混合优化算法能够在接近最优解的基础上有效地降低时间花费，较好地解决了服务优化选择问题。

1问题描述

SLA 等级感知的服务选择问题是寻找抽象服务与具体服务之间最优绑定的组合优化问题。SLA在三个维度上的级别协议分别表示用户对组合服务的语义链接匹配度、QoS与事务的全局约束要求。

问题描述如图1所示，包括抽象组合服务流程部分、服务优化选择部分、具体组合服务流程部分。由于服务的粒度问题，满足用户需求的抽象组合服务流程会有多条。抽象组合服务流程由多个抽象服务组成，每个抽象服务对应一个具体服务群。同一服务群中的服务有相似功能，但是QoS和事务属性不同。通过为每个抽象服务选择合适的候选服务，使得在满足SLA的情况下，达到全局最优的效果。

2服务优化选择模型

2.1概念语义相似度

领域本体是对特定领域内的概念及概念间关系的精确描述，服务的接口参数都用领域本体来表示。为了在求两个概念间的相似度时，避免对本体树的反复查找，给出概念的关联强度定义与相似度的计算公式。

2.3QoS属性

QoS 是由一些非功能属性组成，包括服务价格（price）、服务响应时间（time）、服务可用性（availability）和服务可靠性（reliability）等。QoS 属性可以分为积极属性和消极属性两类。

积极属性考虑QoS 的最大化， 即值越大表示服务质量越好，如可用性、可靠性等；消极属性考虑QoS的最小化， 即值越小表示服务质量越好，如价格、响应时间等。

每种QoS 属性的计量单位或选择范围都不相同。通过效用函数的映射，可对不同的QoS 属性在统一的标准下进行计算。积极的QoS属性的归一化公式为式（5），消极的QoS属性的归一化公式为式（6）。

2.4服务聚合

组合服务的语义链接匹配度与QoS值是基于每个组成服务与流程结构得到的。虽然服务的组合类型不同，但都可将其分解为顺序类型的聚合函数。顺序类型的组合服务CS的语义链接匹配度与QoS的聚合函数计算公式见表1。

2.5事务属性

针对网络环境下的不稳定性问题，本文使用事务处理来控制组合服务的可靠性和语义的一致性。服务的事务属性包含如下几类：可补偿的事务属性、可重试的事务属性、枢纽事务属性及可补偿+可重试事务属性。

定义2

可补偿事务属性（c）。具有可补偿事务属性的服务是能够通过特定方式返回到执行前状态的服务。

定义3

可重试事务属性（r）。具有可重试事务属性的服务是在执行失败情况下，能够经过有限多次重启直到成功的服务。

定义4

枢纽事务属性（p）。具有枢纽事务属性的服务是在执行成功情况下，其影响不能被消除的服务。

定义5

可补偿+可重试事务属性（cr）。同时具有可补偿事务属性和可重试事务属性的服务。

组合服务的事务属性由其组成部分的事务属性来决定[13]。表2给出了顺序结构的组合服务事务属性的计算规则。表格中的 “#”表示组合服务不满足事务属性要求。若当前服务的事务属性是c，其后继服务的事务属性是r，则它们构成的组合服务的事务属性就为p。

2.6服务粒度

把组合服务中的每一个原子服务称为细粒度服务。由于存在相应的服务，它在功能上是多个原子服务的组合，同时它的非功能属性可能更优，这种服务就称为粗粒度服务。图2给出了一个顺序类型的组合服务，它由5个细粒度抽象服务（AS[1]， AS[2]， AS[3]， AS[4]， AS[5]）和2个粗粒度抽象服务（AS[1，2]， AS[3，5]）构成， 每个抽象服务可由若干具体服务来实现。AS[1，2]的功能是AS[1]和AS[2]的组合，AS[3，5] 的功能是AS[3]、AS[4]和AS[5]的组合。（S[1]1， S[1]2，…， S[1]n）表示抽象服务AS[1]的n个候选服务。

3混合优化算法

本文提出的混合优化算法采用动态适应度函数，逐代淘汰不满足约束的个体；采用知识启发式的交叉与变异算子，以保证个体满足事务属性要求；将克隆选择与遗传算法相结合，增强对最优解的搜索能力。

3.1服务粒度

采用一个定长的整数数组进行编码。数组的长度为个体包含的服务数，数组中每个元素的值为对应抽象服务绑定的具体服务实例的标识。图3中的个体由5个细粒度服务和2个粗粒度服务构成。该个体可以分解为4个组合服务流程，分别为：（S[1]5，S[2]8，S[3]10，S[4]4，S[5]12）， （S[1，2]20， S[3]10， S[4]4， S[5]12）， （S[1]5，S[2]8，S[3，5]1）， （S[1，2]20， S[3，5]1）。这4个组合服务都满足事务属性。个体的适应度值是这4个组合服务中的最大值。

3.4遗传算法

遗传算法的基本思想是通过个体之间的选择、交叉、变异等进化操作，产生具有更高适应度的新个体，然后算法不断重复上述进化过程，直到满足结束条件为止，以实现在目标空间的全局搜索。

传统的遗传算法的交叉算子采用标准的两点交叉，即对两个个体随机选择一个交叉点进行交叉；变异算子是以一定概率选择基因进行变异。由于要保证组合服务的事务属性，传统的交叉与变异算子无法做到，故给出基于知识启发式的交叉与变异算子。算子将服务的事务属性设定优先级，其中属性cr的优先级最高为3，属性c和r的优先级都为2，属性p的优先级为1，并约定属性c和r的优先级不可比较。图4给出了个体1和个体2进行交叉操作的过程。首先以个体1作为主要个体，若个体1中服务的事务优先级小于等于个体2中相应服务的事务优先级，则用个体2中的服务替代个体1中的服务，从而得到孩子个体1。类似地，如果以个体2作为主要个体进行交叉，则得到孩子个体2。

个体的变异也是基于知识启发式的，以保证变异后的个体满足事务属性。若要变异的服务的事务属性是p，变异的时候要从属性优先级大于等于p的候选服务中进行随机选择。

3.5算法流程

本文提出的基于克隆选择与遗传算法的混合优化算法的实现步骤如下：

步骤1

设定种群规模数N， 最大迭代次数K，交叉与变异概率， 随机产生满足事务属性约束的个体， 设定初始迭代k=1。

步骤2

根据式（8）计算种群中个体的适应度值，求得当前最优值并记录下最优个体。

步骤3

如果迭代次数达到最大迭代次数，输出结果；否则，执行步骤4。

步骤4

对种群中的个体进行克隆，根据式（9）计算个体的亲和度，克隆规模与亲和度成正比，克隆倍数由式（10）计算，生成临时种群C。

步骤5

对种群C中的每个个体进行高频变异和选择，生成新的种群C1。在克隆选择的过程中更新最优值和最优个体。

步骤6

在C1种群中选择个体进行知识启发式的交叉、变异与选择操作，生成种群C2， 在交叉与变异的过程中更新最优值和最优个体，k=k+1， 返回步骤3。

4实验及结果分析

以下通过仿真实验分析算法的可行性和有效性。实验环境为Pentium 2.0GHz，内存2GB，操作系统Windows 7（32位），开发语言为C++。实验中的顺序类型组合服务含有7个抽象服务，如图2所示。实验中考虑了四种QoS属性：价格、响应时间、可用性和可靠性，并参考文献[1]在取值范围内生成相应的指标数据。所有生成服务的接口都用领域本体概念进行标注，每个概念都有相应的祖先向量和关联强度向量。服务的事务属性从{p， c， r， cr}中随机选择。θ用来表示全局约束的强度。对于积极属性Qi与消极属性Qj，分别用式（11）与（12）计算θ。

本文将从迭代次数、候选服务数量、全局约束强度三个方面比较混合算法、穷举法与传统的遗传算法的性能，分析各算法的优劣。算法中种群数量设置为200，交叉概率为0.8，变异概率为0.2，最大迭代次数为300。 各对比算法分别独立运行30次，从而求得平均值。

4.1迭代次数方面的性能比较

当候选服务数量为50，全局约束强度为0.1的情况下，算法性能对比如图5所示。

从图5（a）中可以看出，随着迭代次数的增加，混合算法求得的最优值稳步增长。混合算法通过采用知识启发式的交叉、变异和克隆选择操作，进一步提高了搜索效率，求得的最优值高于传统遗传算法的最优值。在300次迭代时，混合算法求得的最优值近96%，而遗传算法的最优值在90%左右。图5（b）中，随着迭代次数的增加，混合算法的执行时间相应增长，但相比穷举法，其时间花费较低，能够在满足精度的情况下有较好的时间效率。

4.2候选服务数量方面的性能比较

设定迭代次数为300，全局约束强度为0.1，候选服务的数目分别为50，60，…，100。图6给出了最优值的比较，随着候选服务数目的增长，混合算法与遗传算法搜索到的最优值都有所降低，但混合算法的最优值明显高于遗传算法的最优值。当候选服务数量为100时，混合算法的最优值近91%，而遗传算法只有85%左右。本文的算法在不同的问题规模情况下均能够得到较好的解，由此可以验证混合算法解决大规模组合服务选择问题的可行性和有效性。

4.3约束强度方面的性能比较

设定迭代次数为300，候选服务的数目为50，约束强度分别为0.1，0.2，…，0.6。模拟100次用户请求，分析本文算法在成功率与搜索最优解上的性能，其中成功率指100次请求中找到可行解的概率。图7（a）中，随着约束强度的增加，算法的成功率都有所降低，这是因为满足强约束条件的可行解的概率降低，但混合算法仍有较高的成功率。图7（b）给出了最优值的比较。混合算法求得的最优值接近于穷举法的最优值。由此可见本文算法有较好的全局寻优搜索能力，能高效地搜索出满足用户约束的组合服务，同时解的质量有显著提高。

以上的实验结果验证了本文的混合优化算法在降低服务选择时间的同时，保证了组合服务的质量，能够满足用户多方面的需求，从而较好地应对了目前候选服务数量爆炸式增长对服务选择带来的挑战。

5结语

现有的QoS感知的服务选择中很少考虑语义链接匹配度和事务属性，而QoS值仅仅反映出组合服务的一部分非功能属性，无法满足用户多维度的需求。在服务选择过程中，若只考虑细粒度，则会导致无法求得最优组合服务。针对以上问题，本文研究并提出了面向多维度和多粒度的服务选择模型，并基于该模型设计了混合优化算法。该混合优化算法采用动态的适应度函数，将启发式的交叉、变异算子与克隆选择相结合，以增强全局搜索能力。实验结果表明，该混合优化算法增强了种群的多样性，收敛性好，在全局约束下的大规模服务选择方面有较好性能。下一步将在并发需求模式下研究服务选择问题，并进一步改进算法的性能。

参考文献：

[1]ZENG L， BENATALLAH B， NGU A H H， et al. QoS-aware middleware for Web services composition [J]. IEEE Transactions on Software Engineering， 2004， 30（5）： 311-327.

[2]ARDAGNA D， PERNICI B. Adaptive service composition in flexible processes [J]. IEEE Transactions on Software Engineering， 2007， 33（6）： 369-384.

[3]ALRIFAI M， RISSE T. Combining global optimization with local selection for efficient QoS-aware service composition [C]// WWW09： Proceedings of the 18th International Conference on World Wide Web. New York： ACM， 2009： 881-890.

[4]王尚广，孙其博，杨放春.基于全局QoS约束分解的Web服务动态选择[J].软件学报，2011，22（7）：1426-1439. （WANG S G， SUN Q B， YANG F C. Web service dynamic selection by the decomposition of global QoS constraints [J]. Journal of Software， 2011， 22（7）： 1426-1439.）

[5]ALRIFAI M， SKOUTAS D， RISSE T. Selecting skyline services for QoS-based Web service composition [C]// WWW10： Proceedings of the 19th International Conference on World Wide Web. New York： ACM， 2010： 11-20.

[6]YU Q， BOUGUETTAYA A. Efficient service skyline computation for composite service selection [J]. IEEE Transactions on Knowledge and Data Engineering， 2013， 25（4）： 776-789.

[7]BARAKAT L， MILES S， POERNOMO I， et al. Efficient multi-granularity service composition [C]// ICWS11： Proceedings of the 2011 IEEE International Conference on Web Services. Washington， DC： IEEE Computer Society， 2011： 227-234.

[8]王文彬，孙其博，赵新超，等.基于非均衡变异离散粒子群算法的QoS全局最优Web服务选择方法[J].电子学报，2010，38（12）：1426-1439. （WANG W B， SUN Q B， ZHAO X C， et al. Web services selection approach with QoS global optimal based on discrete particle swarm optimization with non-uniform mutation algorithm [J]. Acta Electronica Sinica， 2010， 38（12）： 1426-1439.）

[9]WANG X， WANG Z， XU X. An improved artificial bee colony approach to QoS-aware service selection [C]// ICWS13： Proceedings of the 2013 IEEE 20th International Conference on Web Services. Washington， DC： IEEE Computer Society， 2013： 395-402.

[10]YILMAZ A， KARAGOZ P. Improved genetic algorithm based approach for QoS aware Web service composition [C]// ICWS14： Proceedings of the 2014 IEEE 21th International Conference on Web Services. Washington， DC： IEEE Computer Society， 2014： 463-470.

[11]倪志伟，方清华，李蓉蓉，等.改进蚁群算法在基于服务质量的Web服务组合优化中的应用[J].计算机应用，2015，35（8）：2238-2243. （NI Z W， FANG Q H， LI R R， et al. Improved ant colony optimization for QoS-based Web service composition optimization [J]. Journal of Computer Applications， 2015， 35（8）： 2238-2243.）

[12]NGU A H H， CARLSON M P， SHENG Q-Y， et al. Semantic-based mashup of composite applications [J]. IEEE Transactions on Service Computing， 2010， 3（1）： 2-15.

[13]HADDAD J E， MANOUVRIER M， RUKOZ M. TQoS： transactional and QoS-aware selection algorithm for automatic Web service composition [J]. IEEE Transactions on Service Computing， 2010， 3（1）： 73-85.

[14]CAO J， ZHU G， ZHENG X， et al. TASS： transaction assurance in service selection [C]// ICWS12： Proceedings of the 2012 IEEE 19th International Conference on Web Services. Washington， DC： IEEE Computer Society， 2012： 472-479.

[15]刘海，张卫民，张瞩熹，等.满足原子事务与QoS端对端约束的服务优化选择方法[J].通信学报，2011，32（7）：80-92. （LIU H， ZHANG W M， ZHANG Z X， et al. Optimal service selection approach considering both atomic transaction and end-to-end QoS constraints [J]. Journal on Communications， 2011， 32（7）： 80-92.）

[16]DING Z， LIU J， SUN Y， et al. A transaction and QoS-aware service selection approach based on genetic algorithm [J]. IEEE Transactions on Systems， Man， and Cybernetics： Systems， 2015， 45（7）： 1035-1046.