基于QoS多目标优化的云服务组合方法

苗冬云

（安徽财经大学管理科学与工程学院 安徽蚌埠 233030）

基于QoS多目标优化的云服务组合方法

苗冬云

（安徽财经大学管理科学与工程学院 安徽蚌埠 233030）

随着云计算的商业推动，云服务的发展空间扩大。如何从服务功能相同或相似而服务质量不同的云服务中选择既能满足用户的QoS需求又具有最优全局服务质量的组合云服务是一个NP难题，也是云服务亟待解决的问题。文章提出了一种基于粒子群优化算法的多目标优化方法，将云服务组合全局最优化问题作为带约束的多目标服务组合优化问题；算法通过同时优化多个QoS参数，最终产生一组满足用户约束条件的Pareto最优解。

云服务；服务质量；服务组合；多目标优化；粒子群算法

云计算（Cloud Computing）是一种基于Internet的计算模式，是并行计算（ParallelComputing）、分布式计算（Distributed Computing）和网格计算（Grid Computing）发展融合的产物。云计算的核心是以网络化的方式将计算资源（包括网络、服务器、存储及应用软件等）以服务的形式组织和聚合在一起，从而形成规模庞大的虚拟资源池，方便用户获取和使用。云计算提供的服务形式包括三种：基础设施即服务（Infrastructure as a Service，IaaS）、平台即服务（Platform as a Service，PaaS）和软件即服务（Softwareasa Service，SaaS）。

云服务（Cloud Service）是基于云计算的各项网络服务，是随着云计算的商业推动而得到进一步发展的新兴产业。由于用户需求的复杂性、多变性，功能单一的云服务无法满足用户的要求，因此，需要根据用户的业务需求将单个云服务组织聚合成服务组合，以完成复杂的业务。当用户在进行服务选择时，不仅考虑服务组合问题，也要考虑服务质量问题。随着云计算技术的成熟与发展，网络上出现了大量功能相同但服务质量（Quality ofService，QoS）不同的云服务，如何从其中选择出既能满足用户的QoS需求又具有最优全局服务质量的组合云服务是一个NP难题［1］。本文采用基于多目标粒子群算法的服务选择算法将云服务优化组合作为带约束的多目标优化问题进行处理。

一、云服务的QoS属性描述

服务质量QoS是描述网络性能的参数，通过设定不同维度的参数来描述网络服务的质量，同时也体现了用户对服务提供者所提供服务的满意程度［2］。

云服务的QoS指标［3］主要包括费用（cost）、响应时间（response time）、可靠性（reliability）、可用性（availability）、执行成功率（successful rate）以及安全性（security）等，云服务的QoS属性及其说明，如表1所示。

表1 云服务的QoS属性及其说明

（续上表）

云服务的QoS属性具有以下的特点：

（一）综合性。云服务的QoS属性是由多个指标构成的，这些指标具有不同的量纲描述，没有一个统一的标准对其进行度量，并且各目标的单位不统一。

（二）模糊性。云服务的QoS属性中有的可以精确量化，有的只能通过模糊值进行定义或者进行评价获得。例如，费用、响应时间可以精确量化为时间值，但可靠性却很难精确描述。

（三）动态性。云服务的各QoS属性的值不是保持不变的，它可能随着服务的状态、服务器的请求等变化。

（四）相关性。云服务的QoS属性通常不是相互独立的，有可能是相互制约、相互冲突的，如某一个目标的优化是以其他目标作为代价，例如，费用与响应时间是负相关关系，响应时间越短则产生的费用就越高。

二、云服务组合模型

一个复杂的云服务组合可以分成多个子任务，每个子任务对应一个云服务群。服务群是指拥有相同的功能和不同的服务质量的一组云服务。假设实现一个串行的云服务组合，如图1所示，模型含有m个子任务，每个子任务Ti（i=1，2，…，m）对应的云服务群CSij包含n个云服务，S为任务起点，E为任务终点，从S到E的任何一条路径所包含的云服务即为能够完成此任务的组合服务（只考虑功能）［4］。每个云服务群的属性Q都包含n个QoS属性，即Qij={qij1，qij2，…，qijn}。

图1 云服务组合模型

三、多目标组合优化问题

组合优化（CombinatorialOptimization）问题是指运用数学方法去寻找离散事件中的最优编排、分组、次序或筛选等，属于运筹学（OperationsResearch）中的一个重要分支。组合优化问题的目标是从组合问题的可行解集中求出最优解。服务组合是将现有的服务依照一定业务逻辑进行集成，从而更好地满足用户的需求。

多目标优化是数学规划的一个分支，定义一个多目标优化问题为：（X，C，F），其中，X是n维决策空间，并且（x1，x2，…，xn）∈X；C是决策变量必须满足的约束条件；目标函数为min F=min（f1（x），f2（x），……，fk（x））。

定义1（可行解）如果x∈X且满足C中的所有约束条件，称x为可行解。

定义2（可行解集合）所有可行解的集合成为可行解集合，记为Xf，XfX。

定义3（Pareto占优）假设xA，xB∈Xf，那么xA对xB是Pareto占优的充要条件是：∀i=1，2，……，k，fi（xA）≤fi（xB），且∃j=1，2，……，k，fj（xA）＜fj（xB），记为：xA＞xB，也称为xA支配xB。

定义4（Pareto最优解）如果一个可行解*满足条件：∃x∈Xf使x＞x*，则x*被称为Pareto最优解（或者非支配解）。

定义5（Pareto最优解集）所有Pareto最优解的集合成为Pareto最优解集。

在大多数情况下多目标优化问题很难得到问题的最优解，而且解不是唯一的，而是存在一个最优解集合（或非劣解集合），集合中元素称为 Pareto最优或非劣最优（Non-Dominated）。得到非劣解集合，然后根据用户的需求偏好决定各分量的效用函数。效用函数是指用户对QoS指标的偏向，不同用户的效用函数是不同的。

四、云服务组合中基于服务质量的粒子群算法

（一）粒子群算法。粒子群优化（Particle Swarm Optimization，PSO）算法是1995由Kennedy［5］博士和Eberhart［6］博士等人受人工生命研究的结果启发，在模拟鸟群觅食活动中的迁徙和群集行为时提出的一种基于群体智能的演化计算技术，是演化计算领域中一个新的分支。PSO是一种全局优化技术，具有参数少、计算效率高、鲁棒性好、收敛速度快、所需领域知识少、简单易实现等优点［6］。

在PSO算法中，将D维的搜索空间中的每个个体当作是一个没有体积和质量的粒子，设群体规模为N，群体中的每个粒子i（i=1，2，…，N）的位置可以表示为一个D维矢量，表示为Xi=（xi1，xi2，…，xiD）T，同时每个粒子都有一个飞翔速度来决定他们飞翔的方向和距离，用Vi=（vi1，vi2，…，viD）T表示第i个粒子的飞翔速度，之后通过适应值函数计算出每个粒子的适应度值，当作自己的最优解，称为局部极值Pi，之后从所有粒子的局部极值中再算出最优的极值作为全局极值Pg。用Pi=（pi1，pi2，…，piD）表示第i个粒子自身搜索的最好点，用Pg=（pg1，pg2，…，pgD）表示群体内所有粒子所经历到的最好点。得到局部极值和全局极值之后，通过式（1）、式（2）更新粒子i的速度和位置，使得粒子都向最优的位置靠近，最终找到Pareto最优解。

上式中，k为迭代次数，w为惯性因子且为非负常数，c1，c2为学习因子，r1，r2为（0，1）内相互独立的随机数。

（二）基于粒子群的云服务组合算法。根据第3节的描述，多目标优化中目标函数的值越小，则结果越好。但云服务的QoS属性指标无法统一为一个量纲，且目标方向也不一致，有的属性的值越大，云服务质量就越好（正指标），如可靠性、执行成功率、可用性和安全性；而有的属性的值越小，云服务质量就越好（负指标），如费用、响应时间。为了进行统一的计算和一致的度量量纲、方向，需要对云服务QoS属性向量进行标准化处理［7］。

设云服务的效用函数为

Fij=Wij1Uij1+Wij2Uij2+…+WijnUijn（5）

其中Uij1，Uij2，…，Uijn是用户为各个QoS指标所对应的权值，并满足Uij1+Uij2+…+Uijn=1，0≤Uijk≤1，其中，i=（1，2，…，m）表示第i个子任务，j=（1，2，…，n）表示某子任务中的某个服务。

假设用户提出的全局约束为Qc，则带有全局QoS约束的多目标云服务组合优化问题的数学模型定义为：

其中，xij∈{0，1}（i=1，2，…，m；j∈Wi），若服务CSij被选中，则xij=1，否则xij=0，Qc表示服务质量约束之和。

（三）基于PSO算法的实现步骤。利用PSO算法对上述的目标函数式进行求解，可以得到带有全局QoS约束的多目标云服务组合优化问题的Pareto最优解。根据以上分析，下面给出基于粒子群的云服务组合算法的实现步骤。

1.初始化粒子群规模、惯性因子、学习因子、最大迭代次数或者最小适应度值误差要求，以及粒子的初始位置和初始速度。

2.将初始的评价值作为个体的局部极值Pi以及全局极值Pg。

3.根据式（1）和式（2）对每个粒子的位置和速度进行更新。

4.用目标函数计算出每个粒子的适应度值，从而评价每个粒子的当前位置。如果粒子的适应度值优于局部极值Pi，则替换Pi；如果粒子的适应度值优于全局极值Pg，则替换Pg。

5.重复步骤（3）（4），直到满足最终条件（即适应度值误差达到设定的最小适应度值误差要求或者迭代次数超过最大允许迭代次数）。

（四）基于PSO算法的流程。依据PSO算法的思想，基于服务质量多目标优化的云服务组合算法可以归纳为以下说明：

1）Initialize Particle Swarm//初始化粒子群

2）for i=1：N//N表示粒子群体规模

3）for j=1：D//D表示搜索空间维数

4）x（i，j）=randm；v（i，j）=randm；//随机初始化位置，随机初始化速度

5）end

6）end

7）fori=1：N

8）P（i）=fitness（x（i，：），D）；y（i，：）；//计算第i个粒子的适应度向量，初始化Pi

9）end

10）Pg=x（i，：）；//初始化Pg

11）fori=2：N

12）iffitness（x（i，：），D）〈fitness（Pg，D）

13）Pg=x（i，：）；

14）end

15）end

16）fort=1：MaxDT//MaxDT表示最大迭代次

17）fori=1：N//进入循环阶段，按照公式进行迭代，直到满足最后要求

18）v（i，：）=w*v（i，：）+c1*r*（y（i，：）-x（i，：））+c2*r*（Pg-x（i，：））；

19）x（i，：）=x（i，：）+v（i，：）；

20）iffitness（x（i，：）〈P（i））

21）P（i）=fitness（x（i，：）：D）；y（i，：）=x（i，：）；

22）end

23）ifP（i）〈fitness（Pg，D）

24）Pg=y（i，：）；

25）end

26）end

27）Pbest（t）=fitness（Pg，D）；

28）End

五、结束语

在云服务的应用中，基于服务质量的服务组合优化会逐渐成为研究关注的重大问题。本文将云服务组合全局最优化问题转化为带QoS约束的多目标服务组合优化问题，提出一种基于粒子群算法的服务全局QoS最优算法。根据用户建立的效用函数，通过粒子群算法对多个QoS属性进行同时优化，最终产生用户满意的一组Pareto最优解。下一步将通过实验仿真结果，来表示粒子群算法对求解云服务组合优化问题具有较高的求解效率，搜索结果也能较好的满足用户的需求。以实际问题为背景来验证粒子群算法的可用性，进而得到更广泛的应用。

［1］CANFORA G，Penta D，Esposito M，etal.A lightweight approach for QoS-aware service composition［C］.Proc.2nd International Conference on Services Computing（ICSOC，04）.New york，USA，2004.

［2］张玉超，彭甫阳，邓波.服务质量驱动的云计算研究［J］.计算机科学，2012（11）.

［3］WANGXiao-ying，XUEYuan-yuan，FAN Li-hua，etal. Research on adaptive QoS -aware resource reservation management in cloud service environments ［C］//Proc of International Conference on Services Computing Conference. 2011.

［4］刘志中，雷冠军，薛霄，等.QoS感知的云服务优化组合研究［J］.计算机应用研究，2012（10）.

［5］Kenedy J，Eberhart R.Particle swarm optimization［C］. IEEE Int1 Conf Neural Networks.Piscataway，N J：IEEE Service Center，1995.

［6］Eberhart R，Kenedy J.A New Optimizer Using Particle Swarm Theory［C］..In：proc of the Sixth International Symposium on Micro Machine and Human Science，Nagoya，Japan，1995.

［7］刘家良，孙俊丽，姜利群.一种面向云计算的QoS评价模型［J］.电脑知识与技术，2010（31）.

［8］郭力争，耿永军，姜长源，等.云计算环境下基于粒子群算法的多目标优化［J］.计算机工程与设计，2013（7）.

［9］王娜，卫波，王晋东，等.基于混合多目标粒子群优化算法的云服务选择［J］.计算机工程，2014（3）.

［责任编辑 郑丽娟］

Cloud Service Composition Method Based on QoS by Multiple Objective Optimization

Miao Dongyun
（Anhui University of Finance and Economics，Bengbu，Anhui233030）

With the promotion of cloud computing business，the development space of cloud service has expanded.How to select cloud service that can meet users’requirements on QoS and the global optimal in cloud service composition from cloud service which has same or similar functions and different qualities of service is a NP problem，which is a challenge problem in the cloud service.So the paper presents a global optimal algorithm based on particle swarm optimization，this method will transform a cloud service selection global optimal problem into an optimization problem，The algorithm produces a set of optimal Pareto that can satisfy the users’constraint conditions by optimizingmulti QoS parameters simultaneously.

cloud service；quality of service；service composition；multi-objective optimization；particle swarm optimization

TP301

A

2095-0438（2015）09-0144-04

2015-03-30

苗冬云（1990-），女，江苏扬州人，安徽财经大学管理科学与工程学院2013级研究生，研究方向：云计算的资源调度。