苗冬云

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

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

苗冬云

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

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

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

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

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

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

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

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

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

（續(xù)上表）

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

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

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

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

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

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

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

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

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

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

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

定義1（可行解）如果x∈X且滿(mǎn)足C中的所有約束條件，稱(chēng)x為可行解。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.將初始的評(píng)價(jià)值作為個(gè)體的局部極值Pi以及全局極值Pg。

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

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

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

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

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；//隨機(jī)初始化位置，隨機(jī)初始化速度

5）end

6）end

7）fori=1：N

8）P（i）=fitness（x（i，：），D）；y（i，：）；//計(jì)算第i個(gè)粒子的適應(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)行迭代，直到滿(mǎ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é)束語(yǔ)

在云服務(wù)的應(yīng)用中，基于服務(wù)質(zhì)量的服務(wù)組合優(yōu)化會(huì)逐漸成為研究關(guān)注的重大問(wèn)題。本文將云服務(wù)組合全局最優(yōu)化問(wèn)題轉(zhuǎn)化為帶QoS約束的多目標(biāo)服務(wù)組合優(yōu)化問(wèn)題，提出一種基于粒子群算法的服務(wù)全局QoS最優(yōu)算法。根據(jù)用戶(hù)建立的效用函數(shù)，通過(guò)粒子群算法對(duì)多個(gè)QoS屬性進(jìn)行同時(shí)優(yōu)化，最終產(chǎn)生用戶(hù)滿(mǎn)意的一組Pareto最優(yōu)解。下一步將通過(guò)實(shí)驗(yàn)仿真結(jié)果，來(lái)表示粒子群算法對(duì)求解云服務(wù)組合優(yōu)化問(wèn)題具有較高的求解效率，搜索結(jié)果也能較好的滿(mǎn)足用戶(hù)的需求。以實(shí)際問(wèn)題為背景來(lái)驗(yàn)證粒子群算法的可用性，進(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］張玉超，彭甫陽(yáng)，鄧波.服務(wù)質(zhì)量驅(qū)動(dòng)的云計(jì)算研究［J］.計(jì)算機(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］.計(jì)算機(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］劉家良，孫俊麗，姜利群.一種面向云計(jì)算的QoS評(píng)價(jià)模型［J］.電腦知識(shí)與技術(shù)，2010（31）.

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

［9］王娜，衛(wèi)波，王晉東，等.基于混合多目標(biāo)粒子群優(yōu)化算法的云服務(wù)選擇［J］.計(jì)算機(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-），女，江蘇揚(yáng)州人，安徽財(cái)經(jīng)大學(xué)管理科學(xué)與工程學(xué)院2013級(jí)研究生，研究方向：云計(jì)算的資源調(diào)度。