苗冬云

（安徽財經(jīng)大學(xué)管理科學(xué)與工程學(xué)院 安徽蚌埠 233030）

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

苗冬云

（安徽財經(jīng)大學(xué)管理科學(xué)與工程學(xué)院 安徽蚌埠 233030）

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

云服務(wù)；服務(wù)質(zhì)量；服務(wù)組合；多目標(biāo)優(yōu)化；粒子群算法

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

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

一、云服務(wù)的QoS屬性描述

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

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

表1 云服務(wù)的QoS屬性及其說明

（續(xù)上表）

云服務(wù)的QoS屬性具有以下的特點：

（一）綜合性。云服務(wù)的QoS屬性是由多個指標(biāo)構(gòu)成的，這些指標(biāo)具有不同的量綱描述，沒有一個統(tǒng)一的標(biāo)準(zhǔn)對其進(jìn)行度量，并且各目標(biāo)的單位不統(tǒng)一。

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

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

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

二、云服務(wù)組合模型

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

圖1 云服務(wù)組合模型

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

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

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

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

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

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

四、云服務(wù)組合中基于服務(wù)質(zhì)量的粒子群算法

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

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

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

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

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

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

其中Uij1，Uij2，…，Uijn是用戶為各個QoS指標(biāo)所對應(yīng)的權(quán)值，并滿足Uij1+Uij2+…+Uijn=1，0≤Uijk≤1，其中，i=（1，2，…，m）表示第i個子任務(wù)，j=（1，2，…，n）表示某子任務(wù)中的某個服務(wù)。

假設(shè)用戶提出的全局約束為Qc，則帶有全局QoS約束的多目標(biāo)云服務(wù)組合優(yōu)化問題的數(shù)學(xué)模型定義為：

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

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

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

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

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

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

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

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

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個粒子的適應(yīng)度向量，初始化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//進(jìn)入循環(huán)階段，按照公式進(jì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

五、結(jié)束語

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

［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］張玉超，彭甫陽，鄧波.服務(wù)質(zhì)量驅(qū)動的云計算研究［J］.計算機科學(xué)，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感知的云服務(wù)優(yōu)化組合研究［J］.計算機應(yīng)用研究，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］.電腦知識與技術(shù)，2010（31）.

［8］郭力爭，耿永軍，姜長源，等.云計算環(huán)境下基于粒子群算法的多目標(biāo)優(yōu)化［J］.計算機工程與設(shè)計，2013（7）.

［9］王娜，衛(wèi)波，王晉東，等.基于混合多目標(biāo)粒子群優(yōu)化算法的云服務(wù)選擇［J］.計算機工程，2014（3）.

［責(zé)任編輯 鄭麗娟］

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-），女，江蘇揚州人，安徽財經(jīng)大學(xué)管理科學(xué)與工程學(xué)院2013級研究生，研究方向：云計算的資源調(diào)度。