基于QoS的制造云服务组合优选问题研究*

唐　雨，汪永超，王　宇

(四川大学 制造科学与工程学院，成都　610065)



基于QoS的制造云服务组合优选问题研究*

唐雨，汪永超，王宇

(四川大学 制造科学与工程学院，成都610065)

摘要：基于云制造的QoS(Quality of Service)属性分析了制造云服务的组合优选问题，建立了该问题的以时间、费用、信誉和可靠性为目标的云服务组合数学模型。提出了结合层次分析法和改进的粒子群算法对该模型进行求解的优化方法。为了分析用户需求，细化了每个QoS属性，形成了云服务属性层次，采用层次分析法确定各属性的权重。改进的粒子群算法则可以快速有效地收敛到最优解。这种优化方法既弥补了以往单一优化方法的不足，同时又能深入分析用户对云服务的需求，找到满足用户需求动态变化的云服务组合方案。

关键词：云制造；云服务组合；粒子群算法；层次分析法

0引言

在我国制造业面临瓶颈的背景下,为了加快我国制造业实现“敏捷制造”、“服务型制造”、“绿色制造”的新型制造模式，李伯虎院士与其团队于2009年提出了“云制造”的理念。“云制造”是一种面向服务的、高效低耗和基于知识的网络化敏捷制造新模式，是现有云计算和现有制造业信息化中的网络化制造、ASp 平台、制造网格等概念和技术的延伸和拓展[1]。随后于2012年李伯虎院士又提出了云制造的关键技术，简述了云制造的技术难点和技术途径，包括物联化技术、虚拟化技术、服务化技术、协同化技术及智能化技术[2]。在这些关键技术中，服务化技术被讨论的很多，其需要解决的难点主要包括资源/能力服务的描述、发现、匹配、组合、调度等。从制造云的基本构造制造云服务(简称云服务)来看，大量的云服务按一定的规则聚合在一起所形成的动态云服务中心，是云制造系统构架的核心，能透明地为用户提供可靠的、廉价的、按需使用的产品全生命周期应用服务[3]。所以制造云服务的组合优选对云制造服务的质量有决定性的影响，于是出现了很多针对制造服务云选择和组合优化的方法。

目前制造云服务的组合优选大多采用单一的非线性的进化方法，如遗传算法[4]，粒子群算法[5]，蚁群算法[6]，人工神经网络[7]等。虽然这些方法都得到了优化结果但是可能存在编码误差大，易陷入局部最优、早熟收敛的问题而不能保证解的优越性。本文提出将层次分析法和改进的粒子群算法结合的方式求解该组合优选问题，即基于制造云的QoS属性，同时建立云服务QoS层次分析结构，让用户基于需求对QoS属性进行打分，结合层次分析法(Analytic Hierarchy process，AHp)得到各指标的权重，然后构造云服务组合与优选问题模型，采用改进的粒子群算法收敛到满足用户需求的最优制造云服务组合。

1云制造服务相关概念

1.1制造云服务、制造云及云服务执行路径的关系

(1)制造云服务(Cloud Service，CS)是通过采用物联网、云化技术，将分散的制造资源和和能力进行封装的产物，是云制造的基本功能构成(云滴)。CS的Qos属性就是对云服务质量描述

(2)制造云(Manufacturing Cloud，MC)则是由一组功能属性相同但非功能属性QoS不同的CS聚合形成的CS集合。

(3)云服务执行路径(Cloud Service Executing path，CSEp)，由于制造任务一般被分解为多个子任务。每个子任务与一个制造云(从中选取一个合适的云服务)相对应，所以多个云服务按一定顺序执行就构成了一条CSEp，对应一个制造任务，可以描述为CSEp=[8]。制造云服务、制造云及云服务执行路径之间的关系见图1。

图1　制造云服务、制造云及云服务执行路径关系图

1.2制造云服务的QoS

制造云服务的服务质量QoS属性包括云服务运行时间T，费用C，信誉等级Rep，可靠性R，其形象化描述为：

QoSCS=

每个云服务有QoS属性，那么有云服务组合而成的云服务执行路径pi的QoS属性可以描述为：

QoS(pi)=

2云服务QoS属性量化

在满足云服务功能匹配的基础上，云服务的选择和组合优化过程实际就是对云服务执行路径QoS属性的优化即对QoS(pi)的优化。云服务执行路径分为4种基本模型(顺序结构、并行结构、选择结构和循环结构)，设每种模型中包含n个云服务{CS1,CS2,…CSn} ，①顺序结构中n个CS串行执行；②并行结构中n个CS同时执行；③选择结构中n个CS，组合服务只选择其中m(m

表1　四种模型对应的QoS(pi)计算方法

3AHp确定云服务QoS权向量

基于云服务的QoS属性，本文选取时间T、费用C、信誉等级Rep及可靠性R四个属性，每一属性又分别包含更为详细的子属性，从而对云服务进行综合分析评价。制造云服务QoS属性层次如图2所示，一级指标由时间A1、费用A2、信誉等级A3及可靠性A4组成，二级指标由响应时间B1、执行时间B2、运输时间B3等12项指标组成。

图2　制造云服务QoS属性层次

依据AHp法的标度及含义(如表2所示)，基于客户对云服务的具体需求对各属性及其子属性的权重进行两两比较，可得到属性层和子属性层两级指标的判断矩阵，借助层次分析软件最终得到基于客户需求的云服务QoS各属性的权向量[9]：

α=(α1,α2,α3,α4)

4建模与求解方法

4.1云服务组合优选问题建模

从本文已经建立的QoS模型中的四个属性考虑，云服务的组合优选结果应该满足运行时间尽可能短、费用尽可能低、信誉尽可能好、可靠性尽可能高，所以可以建立云服务组合优选问题模型，其表达式如下：

minZ(pi)=α1T(pi)+α2C(pi)+

α3/Rep(pi)+α4/R(pi)

(1)

式(1)中的α1、α2、α3、α4分别是通过层次分析法确定的QoS各属性的权重。因为公式采用的是求目标函数最小值的方法，而信誉和可靠性越大越好，所以这里取其倒数。因此使得目标函数Z(pi)值最小的云服务组合执行路径pi就是该云服务组合优化问题的最优解。下面将采用改进的粒子群算法进行求解。

4.2模型求解方法

4.2.1改进的粒子群算法说明

(1)粒子群算法(pSO)是在1995年提出的一种进化计算算法，对pSO算法的研究已经有很多了，这里不再赘述，只是使用其标志性的迭代更新公式：

(2)

(3)

(2)改进的粒子群算法则旨在避免原算法过早陷入局部最优，引入遗传算法算法中的交叉算子，同时对pSO算法中的参数作动态调整。采用如下公式对r1、r2进行优化：

(4)

惯性因子ω是一个控制参数，一般希望在搜索前期ω足够大，使算法有很好的全局搜索能力，而在后期ω可以自动减小增强局部搜索能力，加快收敛速度，提高搜索精度，所以对ω进行动态改进，经大量实验取其初值为0.91，动态变化公式如下：

(5)

式中：t为当前进化代数；T为最大进化代数。

(6)

4.2.2算法求解过程

上文中已经阐述了改进的粒子群算法的主要公式，该算法的求解步骤如下：

①粒子群初始化，由一个制造任务分解成的n个子任务构成一条云服务执行路径pi，与pSO算法中的粒子概念相对应。在初始化时，随机组合云服务生成规模稍大的初始种群Cp以便扩大搜索范围，给定种群规模p，然后依次遍历整个初始粒子群，找出相似性小的前p个粒子，作为初始粒子群pS。输出初始粒子群pS，初始全局最优位置gBest0，初始个体最优位置pBest0。

②参数设置，按照公式(4)、(5)为r1、r2和ω设定初值和确定动态变化规律。

③适应度计算，评价粒子群中每个粒子的适应度，将最优粒子的位置作为pBesti和gBesti输出，适应度按公式(7)计算，公式中的Z(pi)见公式(1)，fitness(pi)的值越大，粒子的适应度越高，pi的质量也就越好。

(7)

④粒子群更新，是pSO算法的核心内容，是优化粒子群寻找理想解的关键。本文粒子群中的每个粒子的速度和位置按公式(2)和(3)更新。输出更新后每个粒子的位置并以此计算pBesti+1和gBesti+1。

经过多次进化更新，粒子群将逐步靠近最优解，最终获得gBest为最优的云服务组合执行路径。

5结束语

本文在分析云服务组合优选这一云制造关键问题后，基于目前云服务QoS属性，并细化成子属性建立了QoS属性层次体系，以方便用户基于需求对云服务的各个属性进行赋权，同时建立云服务组合优化问题模型，为避免pSO算法易陷入局部最优以及早熟收敛的问题，而采用引入遗传算法交叉算子的改进的粒子群算法对模型求解。这种层次分析法和改进的粒子群算法相结合的方式既弥补了以往单一优化方法的不足，同时又能深入分析用户对云服务的需求，找到满足用户需求动态变化的云服务组合方案。

[参考文献]

[1] 李伯虎,张霖,王时龙,等. 云制造——面向服务的网络化制造新模式[J].计算机集成制造系统,2010,16(1):1-7,16.

[2] 李伯虎,张霖,任磊,等. 云制造典型特征、关键技术与应用[J].计算机集成制造系统,2012,18(7):1345-1356.

[3] 张霖,罗永亮,陶飞,等.制造云构建关键技术研究[J].计算机集成制造系统2010,16(11):2510-2520.

[4] Zhang Liangjie,Li Bing.Requirements Driven Dynamic Services Composition for Web Services and Grid Solutions[J].Journal of Grid Computing,2004,2(2):121.

[5] 范小芹,蒋昌俊,方贤文,等. 基于离散微粒群算法的动态Web服务选择[J]. 计算机研究与发展,2010,47(1):147-156.

[6] 倪志伟,王会颖,吴昊. 基于MapReduce和多目标蚁群算法的制造云服务动态选择算法[J]. 中国机械工程,2014,25(20):2751-2760.

[7] 杨辉,谢庆生. 基于人工神经网络的动态联盟制造资源评估方法[J]. 贵州工业大学学报(自然科学版),2005,34(4):54-58.

[8] 张以文,张铃,钱付兰,等.云制造模式下云服务选择算法研究[J].小型微型计算机系统,2014,35(11):2390-2395.

[9] 陈浩,袁逸萍,李晓娟,等. 基于QoS的云制造制造资源组合评价方法[J]. 组合机床与自动化加工技术,2013(12):25-28,32.

[10] 李一鸣. 基于交叉变异粒子群算法的复杂多任务制造云服务组合研究[D].重庆:重庆大学,2013.

(编辑李秀敏)

Study on Optimization of Manufacturing Cloud Services Composition Based on QoS

TANG Yu，WANG Yong-chao，WANG Yu

(School of Manufacturing Science and Engineering, Sichuan University, Chengdu 610065, China)

Abstract：The optimization problem of manufacturing cloud services composition was analysed based on QoS of cloud manufacturing. A mathematical model with time, cost, reputation and reliability goals of this problem was set up. To solve the mathematical model, an optimization method which combined the Analytic Hierarchy process (AHp) with the improved particle swarm algorithm was proposed. In order to analyze user’s needs, each QoS attributes were refined to form a cloud service attribute level, and AHp was used to determine the weight of each attribute. The improved particle swarm algorithm can converge to the optimal solution quickly and efficiently. This optimization method is able to make up for the shortages of the previous method and also find cloud services composition solution meeting user’s dynamic demands.

Key words：cloud manufacturing; cloud services composition; particle swarm algorithm; AHp

中图分类号：TH166;TG506

文献标识码：A

作者简介：唐雨(1991—)，男，四川绵阳人，四川大学硕士研究生，研究方向为机械制造及其自动化，企业信息化，(E-mail)12345tangyu@163.com。

*基金项目：国家“十一五”科技支撑计划项目(2006BAC02A02)

收稿日期：2015-02-08