一種多云環(huán)境下的啟發(fā)式服務(wù)組合方法

盧俊文，崔建峰，鄭鷺斌

(廈門理工學(xué)院計(jì)算機(jī)與信息工程學(xué)院,福建廈門361024)

一種多云環(huán)境下的啟發(fā)式服務(wù)組合方法

盧俊文，崔建峰，鄭鷺斌

(廈門理工學(xué)院計(jì)算機(jī)與信息工程學(xué)院,福建廈門361024)

提出了一種基于云中心信息的服務(wù)組合方法 （service composition based on data center information，SCDC）.SCDC通過貪婪查找方法直到找到所有需要的云服務(wù).SCDC采用3個(gè)原則減少服務(wù)組合涉及云的數(shù)量及減少訪問云服務(wù)的個(gè)數(shù).與ALL Clouds、Smart Clouds、Base Clouds方法對(duì)比表明，SCDC在保持訪問云的數(shù)量最小的同時(shí)，減少訪問云服務(wù)的數(shù)量超過20%.

多云環(huán)境；服務(wù)組合；執(zhí)行時(shí)間；訪問服務(wù)數(shù)量

Web服務(wù)技術(shù)具有高度的互操作性、跨平臺(tái)性和松散耦合等優(yōu)點(diǎn).然而,單個(gè)Web服務(wù)提供的功能較為單一,難以滿足用戶復(fù)雜多樣的請(qǐng)求,只有通過對(duì)已有服務(wù)進(jìn)行組合,才能滿足不同用戶的多個(gè)不同需求［1－2］.Web服務(wù)組合技術(shù)將多個(gè)Web服務(wù)進(jìn)行組合,形成一個(gè)功能能滿足單個(gè)用戶的新的服務(wù),以提供更多功能復(fù)雜的服務(wù)來滿足不同用戶的復(fù)雜需求,同時(shí),也簡化了軟件的生產(chǎn)過程.Web組合技術(shù)也引起了學(xué)術(shù)界和產(chǎn)業(yè)界的廣泛關(guān)注.云平臺(tái)具有可擴(kuò)展性、能規(guī)?；峁┓?wù)等特點(diǎn).云計(jì)算與Web服務(wù)技術(shù)的結(jié)合,使Web服務(wù)于云平臺(tái)都能更大地發(fā)揮各自的作用［3－4］.單個(gè)云所能提供的服務(wù)有限,通過組合多個(gè)云的Web服務(wù),能進(jìn)一步提高云的效果［2－3］,但多云環(huán)境下,服務(wù)組合更加復(fù)雜.當(dāng)前,很多文獻(xiàn)已經(jīng)從多個(gè)方面對(duì)云環(huán)境下的服務(wù)組合相關(guān)技術(shù)進(jìn)行了研究：文獻(xiàn) ［5］通過一個(gè)實(shí)際例子,描述了如何利用全局模型選擇可行的云服務(wù)；文獻(xiàn) ［6］提出了可信云服務(wù)的定義,并從用戶信任預(yù)期、安全威脅來源和技術(shù)針對(duì)的安全目標(biāo)等角度對(duì)可信云服務(wù)研究技術(shù)的類型進(jìn)行了劃分,并在此基礎(chǔ)上,系統(tǒng)地描述了數(shù)據(jù)存儲(chǔ)外包、計(jì)算外包、虛擬機(jī)外包等典型云服務(wù)的安全可信；文獻(xiàn) ［7］以社會(huì)學(xué)中的人際關(guān)系信任模型為基礎(chǔ),提出了一種基于服務(wù)消費(fèi)者的服務(wù)滿意度評(píng)價(jià)、推薦者的服務(wù)推薦和第三方服務(wù)性能反饋的可信度量模型,并在 DLS (dynamic level scheduling)算法基礎(chǔ)之上,提出可信動(dòng)態(tài)級(jí)調(diào)度算法CTDLS(trust-aware dynamic level scheduling algorithm in cloud environment),從而在計(jì)算調(diào)度級(jí)別時(shí)考慮服務(wù)資源的可信程度；文獻(xiàn)［8］探討了利用Agent實(shí)現(xiàn)服務(wù)組合的方法,通過Agent的自我重新組織,實(shí)現(xiàn)服務(wù)組合功能；文獻(xiàn)［9］提出了一種滿足服務(wù)質(zhì)量約束的網(wǎng)絡(luò)服務(wù)組合機(jī)制DSCGOM,包括滿足服務(wù)質(zhì)量的組合路徑選擇機(jī)制設(shè)計(jì)和服務(wù)重定向機(jī)制設(shè)計(jì)；文獻(xiàn) ［10］綜合考慮集成靜態(tài)服務(wù)組合和動(dòng)態(tài)服務(wù)組合的優(yōu)點(diǎn),提出了一種在虛擬層面上基于服務(wù)簇進(jìn)行服務(wù)組合的思想,并給出了一種基于服務(wù)簇的服務(wù)組合方法,并進(jìn)行了驗(yàn)證.

多云環(huán)境下的服務(wù)組合是NP問題［1］,其服務(wù)組合主要涉及到兩方面：選擇哪些服務(wù)及選擇云中的相關(guān)服務(wù)［1－4］.針對(duì)多個(gè)云環(huán)境,一些研究人員也提出了相關(guān)的服務(wù)組合算法,如 All Clouds［1－2,4］、Base Clouds［1－2,4］、Smart Clouds［1－2,4］、COM2 Clouds［1］等.多云環(huán)境下,Web服務(wù)組合的挑戰(zhàn)主要來自兩個(gè)方面：1)多個(gè)云環(huán)境下,如果服務(wù)組合涉及的云的數(shù)量過多,可能導(dǎo)致Web服務(wù)組合的執(zhí)行時(shí)間過長,從而不能完成用戶的目標(biāo)；2)在進(jìn)行服務(wù)組合的時(shí)候,需要檢測(cè)的云服務(wù)數(shù)量太多,延長了服務(wù)組合的組合時(shí)間［2－4］.很多時(shí)候這兩個(gè)調(diào)度目標(biāo)具有沖突性,本文采用折中的方式,提出了一種基于云中心信息的服務(wù)組合方法,在以上兩個(gè)方面均得到比較好的結(jié)果.

1 系統(tǒng)調(diào)度模型

在云環(huán)境下,大多數(shù)服務(wù)組合的研究是針對(duì)一個(gè)云的情況.單個(gè)云制約了服務(wù)組合的功能,本文試圖研究在多個(gè)云環(huán)境下的服務(wù)組合方法.圖1是本文要研究的系統(tǒng)調(diào)度模型.

圖1 多云環(huán)境下的服務(wù)組合Fig.1 Service composition under multi鄄cloud

多云環(huán)境 (multiple cloud environment, MCE)由多個(gè)云組成,每個(gè)云中包括多個(gè)服務(wù)集,每個(gè)服務(wù)集中的元素有多個(gè)服務(wù)單元.如圖1,具有6個(gè)云中心(C1～C6),C1中就有4個(gè)服務(wù)集.假設(shè)S1包含3個(gè)服務(wù)單元(S1～S3),則len(S1)＝3.每個(gè)用戶通過用戶接口提交組合服務(wù)要求,而每個(gè)云通過向MCE中心(multi-cloud management center)報(bào)告服務(wù)信息.Cloud manager和Service manager共同工作完成服務(wù)組合功能.Cloud manager主要完成對(duì)云的管理工作,Service manager主要完成對(duì)服務(wù)的管理工作.云管理,服務(wù)管理,多云管理中心,三者通過互相交互,完成信息各自管理工作,并互相反饋信息.

2 調(diào)度算法

假設(shè)多云環(huán)境如下：MC＝｛C1,C2,…,CMCN｝,每個(gè)多云環(huán)境包含MCN個(gè)云；SF＝｛S1,S2,…, SSN｝,總共有SN個(gè)服務(wù)；SFN＝｛SF1,SF2,…,SFSN｝為每個(gè)服務(wù)的長度,即每個(gè)服務(wù)包含子服務(wù)的數(shù)量；R＝｛SFR1,SFR2,…,SFRSFRN｝,用戶組合服務(wù)要求,假設(shè)用戶服務(wù)要求的的服務(wù)按照子服務(wù)長度按從大到小降序排練.

多云環(huán)境下的服務(wù)組合,其目標(biāo)有2個(gè)：1)最小化訪問云的數(shù)量；2)最小化檢查的服務(wù)數(shù)量,本文采用貪婪算法完成調(diào)度目標(biāo)［1－2,4］.貪婪算法 (又稱貪心算法)是指在對(duì)問題求解時(shí),總是做出在當(dāng)前看來是最好的選擇.也就是說,不從整體最優(yōu)上加以考慮,它所做出的是在某種意義上的局部最優(yōu)解.具體到本文的調(diào)度環(huán)境,算法總試圖使當(dāng)前某個(gè)云中所有服務(wù)被分配,或者某個(gè)服務(wù)組合所需要的所有服務(wù)全部獲得.為實(shí)現(xiàn)這兩個(gè)目標(biāo),筆者提出一種啟發(fā)式算法SCDC(service composition based on data-center information)如下：

算法：SCDC()

算法SCDC主要包含3個(gè)原則：1)如果一個(gè)云中所有服務(wù)都包含在一個(gè)服務(wù)組合要求之內(nèi),那么選擇這個(gè)云中所有服務(wù),如果有多個(gè)云滿足這個(gè)要求,那么選擇包含子服務(wù)數(shù)量最多的云；2)如果一個(gè)服務(wù)組合要求中所有服務(wù)都在一個(gè)云中,那么選擇這個(gè)云,如果有多個(gè)云滿足這個(gè)要求,那么選擇包含子服務(wù)總的數(shù)量最小的云；3)如果沒有滿足條件1)和2),那么選擇包含服務(wù)組合要求最多的云,如果有多個(gè)云滿足這個(gè)要求,那么選擇包含總的子服務(wù)最小的云.三條原則用以確保系統(tǒng)完成兩大目標(biāo)：最小化擬合所涉及的云的數(shù)量ACC(average number of combined clouds)及最小化組合算法所訪問的服務(wù)數(shù)量AEC(average number of examined services).

SCDC算法描述如下：rid是服務(wù)組合要求的唯一標(biāo)志,SFRrid表示對(duì)應(yīng)的服務(wù)要求.行4計(jì)算在云中而不在SFRrid中包含子服務(wù)的數(shù)量；行5計(jì)算在SFRrid而不在云中Ccid總的子服務(wù)數(shù)量；行6計(jì)算SFRrid與Ccid相同子服務(wù)數(shù)量；行8czero(lenl)判斷數(shù)組lenl中是否有值為0的元素；行9～19是執(zhí)行第一條原則,選擇符合條件且具有最大子服務(wù)數(shù)量的云,并分配云中所有服務(wù)；行22～32是執(zhí)行第二條原則,選擇包含所有服務(wù)組合要求中服務(wù)的云,分配服務(wù)并更新服務(wù)組合需求；行36～38是執(zhí)行第三條原則,如果沒有云能滿足第一、二條原則,選擇包含SFRrid中服務(wù)最多的云,若有多個(gè)云滿足這個(gè)條件,選擇總的子服務(wù)數(shù)量最小的云.

3 模擬實(shí)驗(yàn)

模擬實(shí)驗(yàn)環(huán)境如下：每個(gè)服務(wù)文件包含子服務(wù)的數(shù)量為 ［1,10］之間隨機(jī)整數(shù),隨機(jī)產(chǎn)生5個(gè)服務(wù)組合要求,每個(gè)服務(wù)組合要求最多包含5個(gè)子服務(wù)組合；每次隨機(jī)產(chǎn)生5個(gè)MCE,每個(gè)MCE包含8個(gè)云,這些云包含的服務(wù)也有隨機(jī)數(shù)產(chǎn)生.分析結(jié)果為5個(gè)MCE中的平均值,都是采用Matlab 2014對(duì)算法進(jìn)行模擬.

本文將SCDC算法與ALL Clouds、Base Clouds、Smart Clouds進(jìn)行對(duì)比.圖2是不同服務(wù)組合要求在5個(gè)MCE中的AEC,x軸表示各個(gè)服務(wù)組合需求,y軸表示AEC.總體上,除R1外,SCDC具有最小的ACC.圖3是4種方法對(duì)不同的服務(wù)組合需求的AEC,x軸是4種方法,y軸是AEC.其中, SCDC與其他方法對(duì)比,AEC至少減少了20%.

圖4是不同服務(wù)組合要求在5個(gè)MCE中的ACC,x軸是5個(gè)服務(wù)組合需求,y軸是ACC.除R2外,SCDC基本具有最小值.圖5是4種方法的ACC,x軸是4種服務(wù)組合方法,y軸是5個(gè)MCE中的ACC.其中,SCDC具有最小值,All Clouds具有最小值,Base Clouds與Smart Clouds的ACEC值沒有太大差別.

圖2 每個(gè)MCE環(huán)境中AECFig.2 Average AEC in MCE

圖3 各個(gè)方法的AECFig.3 AEC of different methods

圖4 每個(gè)MCE環(huán)境中ACCFig.4 Average ACC in MCE

圖5 各個(gè)方法的ACCFig.5 ACC of different methods

4 結(jié)語

本文研究了服務(wù)存在于多個(gè)云環(huán)境下的服務(wù)組合問題,提出一種服務(wù)組合算法.SCDC采用貪婪算法,試圖減少訪問云和檢測(cè)云服務(wù)的數(shù)量,在此基礎(chǔ)之上,確立了3條調(diào)度原則.并與Smart Clouds,All Clouds及Base Clouds對(duì)比,模擬實(shí)驗(yàn)表明,本文提出的算法不但能減少服務(wù)組合所需的云的數(shù)量,而且能減少服務(wù)組合過程中所查找的服務(wù)數(shù)量.但是,當(dāng)前算法并未考慮服務(wù)的價(jià)格,在考慮價(jià)格的情況下,如何既滿足組合服務(wù)的性能要求,又能滿足組合服務(wù)的預(yù)算要求,是筆者下一步需要考慮的問題.

［1］HEBA K，ABEER A，CARLENE C，et al.A combinatorial optimization algorithm for multiple cloud service composition［J］.Computers＆Electrical Engineering，2015，42：107-113.

［2］YU Q，CHEN L，LI B.Ant colony optimization applied to web service compositions in cloud computing［J］.Computers＆Electrical Engineering，2015，41：18-27.

［3］ZOU G B，GAN Y L，ZHENG J X，et al.Service composition and user modeling for personalized recommendation in cloud computing［C］//International Conference on Computing，Communication and Networking Technologies.Hefei：CCV，2014：11-13.

［4］ZOU G B，CHEN Y X，XIANG Y，et al.AI planning and combinatorial optimization for Web service composition in cloud computing［C］//Proceedings of Annual International Conference on Cloud Computing and Virtualization. Singapore：CCV，2010：28-35.

［5］TANG C L，LIU J Q.Selecting a trusted cloud service provider for your SaaS program［J］.Computers＆Security，2015，50：60-73.

［6］丁滟，王懷民，史佩昌，等.可信云服務(wù) ［J］.計(jì)算機(jī)學(xué)報(bào)，2015，38（1）：178-190.

［7］曹潔，曾國蓀，姜火文，等.云環(huán)境下服務(wù)信任感知的可信動(dòng)態(tài)級(jí)調(diào)度方法 ［J］.通信學(xué)報(bào)，2014，35（11）：39-48.

［8］GUTIERREZ-GARCIA J O，SIM K M.Self-organizing agents for service composition in cloud computing［C］//2nd IEEE International Conference on Cloud Computing Technology and Science.Indianapolis：IEEE，2010：59-66.

［9］羅娟，周峰，李仁發(fā).基于分布式OSGi的動(dòng)態(tài)服務(wù)組合算法 ［J］.計(jì)算機(jī)研究與發(fā)展，2014，51（2）：420-428.

［10］吳洪越，杜玉越.一種基于邏輯petri網(wǎng)的Web服務(wù)簇組合方法 ［J］.計(jì)算機(jī)學(xué)報(bào)，2015，38（1）：204-217.

A Heuristic Service Composition under Multi－Cloud Environment

LU Jun-wen，CUI Jian-feng，ZHENG Lu-bin
（School of Computer＆Information Engineering，Xiamen University of Technology，Xiamen 361024，China）

In the paper，we propose SCDC，a service composition based on data center information under MCE.SCDC finds the service candidate by greedy search and follows three principles to reduce the number of evaluated Clouds and the number of related Cloud services.Comparing to All Clouds，Smart Clouds，Base Clouds，SCDC has a minimum in the number of evaluated Clouds，at the same time，it reduces the number of evaluated Cloud services more than 20%to other methods.

multiple cloud environment；service composition；execution time；number of examined services

TP31

A

1673－4432（2015）05－0075－05

（責(zé)任編輯 雨 松）

2015－09－07

2015－09－25

國家網(wǎng)絡(luò)化支撐軟件國際科技合作基地開放課題 (NSS1403)；福建省自然科學(xué)基金項(xiàng)目 (2013J05103)；廈門理工學(xué)院對(duì)外科技合作專項(xiàng)項(xiàng)目 (201401500)

盧俊文 (1981－),男,實(shí)驗(yàn)師,碩士,研究方向?yàn)榍度胧较到y(tǒng)、網(wǎng)格計(jì)算.E-mail：jwlu＠xmut. edu.cn