基于QoS多目標優(yōu)化的云服務組合方法

苗冬云

（安徽財經大學管理科學與工程學院 安徽蚌埠 233030）

基于QoS多目標優(yōu)化的云服務組合方法

苗冬云

（安徽財經大學管理科學與工程學院 安徽蚌埠 233030）

隨著云計算的商業(yè)推動，云服務的發(fā)展空間擴大。如何從服務功能相同或相似而服務質量不同的云服務中選擇既能滿足用戶的QoS需求又具有最優(yōu)全局服務質量的組合云服務是一個NP難題，也是云服務亟待解決的問題。文章提出了一種基于粒子群優(yōu)化算法的多目標優(yōu)化方法，將云服務組合全局最優(yōu)化問題作為帶約束的多目標服務組合優(yōu)化問題；算法通過同時優(yōu)化多個QoS參數(shù)，最終產生一組滿足用戶約束條件的Pareto最優(yōu)解。

云服務；服務質量；服務組合；多目標優(yōu)化；粒子群算法

云計算（Cloud Computing）是一種基于Internet的計算模式，是并行計算（ParallelComputing）、分布式計算（Distributed Computing）和網格計算（Grid Computing）發(fā)展融合的產物。云計算的核心是以網絡化的方式將計算資源（包括網絡、服務器、存儲及應用軟件等）以服務的形式組織和聚合在一起，從而形成規(guī)模龐大的虛擬資源池，方便用戶獲取和使用。云計算提供的服務形式包括三種：基礎設施即服務（Infrastructure as a Service，IaaS）、平臺即服務（Platform as a Service，PaaS）和軟件即服務（Softwareasa Service，SaaS）。

云服務（Cloud Service）是基于云計算的各項網絡服務，是隨著云計算的商業(yè)推動而得到進一步發(fā)展的新興產業(yè)。由于用戶需求的復雜性、多變性，功能單一的云服務無法滿足用戶的要求，因此，需要根據用戶的業(yè)務需求將單個云服務組織聚合成服務組合，以完成復雜的業(yè)務。當用戶在進行服務選擇時，不僅考慮服務組合問題，也要考慮服務質量問題。隨著云計算技術的成熟與發(fā)展，網絡上出現(xiàn)了大量功能相同但服務質量（Quality ofService，QoS）不同的云服務，如何從其中選擇出既能滿足用戶的QoS需求又具有最優(yōu)全局服務質量的組合云服務是一個NP難題［1］。本文采用基于多目標粒子群算法的服務選擇算法將云服務優(yōu)化組合作為帶約束的多目標優(yōu)化問題進行處理。

一、云服務的QoS屬性描述

服務質量QoS是描述網絡性能的參數(shù)，通過設定不同維度的參數(shù)來描述網絡服務的質量，同時也體現(xiàn)了用戶對服務提供者所提供服務的滿意程度［2］。

云服務的QoS指標［3］主要包括費用（cost）、響應時間（response time）、可靠性（reliability）、可用性（availability）、執(zhí)行成功率（successful rate）以及安全性（security）等，云服務的QoS屬性及其說明，如表1所示。

表1 云服務的QoS屬性及其說明

（續(xù)上表）

云服務的QoS屬性具有以下的特點：

（一）綜合性。云服務的QoS屬性是由多個指標構成的，這些指標具有不同的量綱描述，沒有一個統(tǒng)一的標準對其進行度量，并且各目標的單位不統(tǒng)一。

（二）模糊性。云服務的QoS屬性中有的可以精確量化，有的只能通過模糊值進行定義或者進行評價獲得。例如，費用、響應時間可以精確量化為時間值，但可靠性卻很難精確描述。

（三）動態(tài)性。云服務的各QoS屬性的值不是保持不變的，它可能隨著服務的狀態(tài)、服務器的請求等變化。

（四）相關性。云服務的QoS屬性通常不是相互獨立的，有可能是相互制約、相互沖突的，如某一個目標的優(yōu)化是以其他目標作為代價，例如，費用與響應時間是負相關關系，響應時間越短則產生的費用就越高。

二、云服務組合模型

一個復雜的云服務組合可以分成多個子任務，每個子任務對應一個云服務群。服務群是指擁有相同的功能和不同的服務質量的一組云服務。假設實現(xiàn)一個串行的云服務組合，如圖1所示，模型含有m個子任務，每個子任務Ti（i=1，2，…，m）對應的云服務群CSij包含n個云服務，S為任務起點，E為任務終點，從S到E的任何一條路徑所包含的云服務即為能夠完成此任務的組合服務（只考慮功能）［4］。每個云服務群的屬性Q都包含n個QoS屬性，即Qij={qij1，qij2，…，qijn}。

圖1 云服務組合模型

三、多目標組合優(yōu)化問題

組合優(yōu)化（CombinatorialOptimization）問題是指運用數(shù)學方法去尋找離散事件中的最優(yōu)編排、分組、次序或篩選等，屬于運籌學（OperationsResearch）中的一個重要分支。組合優(yōu)化問題的目標是從組合問題的可行解集中求出最優(yōu)解。服務組合是將現(xiàn)有的服務依照一定業(yè)務邏輯進行集成，從而更好地滿足用戶的需求。

多目標優(yōu)化是數(shù)學規(guī)劃的一個分支，定義一個多目標優(yōu)化問題為：（X，C，F(xiàn)），其中，X是n維決策空間，并且（x1，x2，…，xn）∈X；C是決策變量必須滿足的約束條件；目標函數(shù)為min F=min（f1（x），f2（x），……，fk（x））。

定義1（可行解）如果x∈X且滿足C中的所有約束條件，稱x為可行解。

定義2（可行解集合）所有可行解的集合成為可行解集合，記為Xf，XfX。

定義3（Pareto占優(yōu)）假設xA，xB∈Xf，那么xA對xB是Pareto占優(yōu)的充要條件是：?i=1，2，……，k，fi（xA）≤fi（xB），且?j=1，2，……，k，fj（xA）＜fj（xB），記為：xA＞xB，也稱為xA支配xB。

定義4（Pareto最優(yōu)解）如果一個可行解*滿足條件：?x∈Xf使x＞x*，則x*被稱為Pareto最優(yōu)解（或者非支配解）。

定義5（Pareto最優(yōu)解集）所有Pareto最優(yōu)解的集合成為Pareto最優(yōu)解集。

在大多數(shù)情況下多目標優(yōu)化問題很難得到問題的最優(yōu)解，而且解不是唯一的，而是存在一個最優(yōu)解集合（或非劣解集合），集合中元素稱為 Pareto最優(yōu)或非劣最優(yōu)（Non-Dominated）。得到非劣解集合，然后根據用戶的需求偏好決定各分量的效用函數(shù)。效用函數(shù)是指用戶對QoS指標的偏向，不同用戶的效用函數(shù)是不同的。

四、云服務組合中基于服務質量的粒子群算法

（一）粒子群算法。粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法是1995由Kennedy［5］博士和Eberhart［6］博士等人受人工生命研究的結果啟發(fā)，在模擬鳥群覓食活動中的遷徙和群集行為時提出的一種基于群體智能的演化計算技術，是演化計算領域中一個新的分支。PSO是一種全局優(yōu)化技術，具有參數(shù)少、計算效率高、魯棒性好、收斂速度快、所需領域知識少、簡單易實現(xiàn)等優(yōu)點［6］。

在PSO算法中，將D維的搜索空間中的每個個體當作是一個沒有體積和質量的粒子，設群體規(guī)模為N，群體中的每個粒子i（i=1，2，…，N）的位置可以表示為一個D維矢量，表示為Xi=（xi1，xi2，…，xiD）T，同時每個粒子都有一個飛翔速度來決定他們飛翔的方向和距離，用Vi=（vi1，vi2，…，viD）T表示第i個粒子的飛翔速度，之后通過適應值函數(shù)計算出每個粒子的適應度值，當作自己的最優(yōu)解，稱為局部極值Pi，之后從所有粒子的局部極值中再算出最優(yōu)的極值作為全局極值Pg。用Pi=（pi1，pi2，…，piD）表示第i個粒子自身搜索的最好點，用Pg=（pg1，pg2，…，pgD）表示群體內所有粒子所經歷到的最好點。得到局部極值和全局極值之后，通過式（1）、式（2）更新粒子i的速度和位置，使得粒子都向最優(yōu)的位置靠近，最終找到Pareto最優(yōu)解。

上式中，k為迭代次數(shù)，w為慣性因子且為非負常數(shù)，c1，c2為學習因子，r1，r2為（0，1）內相互獨立的隨機數(shù)。

（二）基于粒子群的云服務組合算法。根據第3節(jié)的描述，多目標優(yōu)化中目標函數(shù)的值越小，則結果越好。但云服務的QoS屬性指標無法統(tǒng)一為一個量綱，且目標方向也不一致，有的屬性的值越大，云服務質量就越好（正指標），如可靠性、執(zhí)行成功率、可用性和安全性；而有的屬性的值越小，云服務質量就越好（負指標），如費用、響應時間。為了進行統(tǒng)一的計算和一致的度量量綱、方向，需要對云服務QoS屬性向量進行標準化處理［7］。

設云服務的效用函數(shù)為

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約束的多目標云服務組合優(yōu)化問題的數(shù)學模型定義為：

其中，xij∈{0，1}（i=1，2，…，m；j∈Wi），若服務CSij被選中，則xij=1，否則xij=0，Qc表示服務質量約束之和。

（三）基于PSO算法的實現(xiàn)步驟。利用PSO算法對上述的目標函數(shù)式進行求解，可以得到帶有全局QoS約束的多目標云服務組合優(yōu)化問題的Pareto最優(yōu)解。根據以上分析，下面給出基于粒子群的云服務組合算法的實現(xiàn)步驟。

1.初始化粒子群規(guī)模、慣性因子、學習因子、最大迭代次數(shù)或者最小適應度值誤差要求，以及粒子的初始位置和初始速度。

2.將初始的評價值作為個體的局部極值Pi以及全局極值Pg。

3.根據式（1）和式（2）對每個粒子的位置和速度進行更新。

4.用目標函數(shù)計算出每個粒子的適應度值，從而評價每個粒子的當前位置。如果粒子的適應度值優(yōu)于局部極值Pi，則替換Pi；如果粒子的適應度值優(yōu)于全局極值Pg，則替換Pg。

5.重復步驟（3）（4），直到滿足最終條件（即適應度值誤差達到設定的最小適應度值誤差要求或者迭代次數(shù)超過最大允許迭代次數(shù)）。

（四）基于PSO算法的流程。依據PSO算法的思想，基于服務質量多目標優(yōu)化的云服務組合算法可以歸納為以下說明：

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

2）for i=1：N//N表示粒子群體規(guī)模

3）for j=1：D//D表示搜索空間維數(shù)

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//進入循環(huá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

五、結束語

在云服務的應用中，基于服務質量的服務組合優(yōu)化會逐漸成為研究關注的重大問題。本文將云服務組合全局最優(yōu)化問題轉化為帶QoS約束的多目標服務組合優(yōu)化問題，提出一種基于粒子群算法的服務全局QoS最優(yōu)算法。根據用戶建立的效用函數(shù)，通過粒子群算法對多個QoS屬性進行同時優(yōu)化，最終產生用戶滿意的一組Pareto最優(yōu)解。下一步將通過實驗仿真結果，來表示粒子群算法對求解云服務組合優(yōu)化問題具有較高的求解效率，搜索結果也能較好的滿足用戶的需求。以實際問題為背景來驗證粒子群算法的可用性，進而得到更廣泛的應用。

［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，F(xiàn)AN 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感知的云服務優(yōu)化組合研究［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］郭力爭，耿永軍，姜長源，等.云計算環(huán)境下基于粒子群算法的多目標優(yōu)化［J］.計算機工程與設計，2013（7）.

［9］王娜，衛(wèi)波，王晉東，等.基于混合多目標粒子群優(yōu)化算法的云服務選擇［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級研究生，研究方向：云計算的資源調度。