肖文娟，段玉聰

(海南大學(xué)信息科學(xué)技術(shù)學(xué)院，海南 ?？?570228)

基于時(shí)間序列的感知QoS的云服務(wù)組合*

肖文娟，段玉聰

(海南大學(xué)信息科學(xué)技術(shù)學(xué)院，海南 ?？?570228)

研究基于時(shí)間序列的感知QoS的云服務(wù)組合，將服務(wù)的QoS偏好隨時(shí)間不斷變化的過(guò)程納入云服務(wù)組合的研究范圍，將云服務(wù)組合建模成時(shí)間序列的相似度對(duì)比問(wèn)題。分別用歐幾里得距離和擴(kuò)展Frobenius范數(shù)距離度量二維時(shí)間序列的相似度，繼而用基于主成分分析的擴(kuò)展Frobenius范數(shù)距離和歐幾里得距離、Brute-Force等方法度量多維時(shí)間序列的相似度，通過(guò)實(shí)驗(yàn)對(duì)比驗(yàn)證擴(kuò)展Frobenius范數(shù)距離度量相似度在時(shí)間和準(zhǔn)確性上的優(yōu)越性。

時(shí)間序列;QoS;云服務(wù)組合;相似度對(duì)比

1 引言

云計(jì)算(Cloud Computing)由分布式計(jì)算(Distributed Computing)、并行計(jì)算(Parallel Computing)、效用計(jì)算(Utility Computing)、網(wǎng)絡(luò)存儲(chǔ)技術(shù)(Network Storage Technologies)、虛擬化(Virtualization)、負(fù)載均衡(Load Balance)等傳統(tǒng)計(jì)算技術(shù)和網(wǎng)絡(luò)技術(shù)發(fā)展融合形成，是基于互聯(lián)網(wǎng)的相關(guān)服務(wù)的增加、使用和交互模式。

云計(jì)算包括的服務(wù)類型有：基礎(chǔ)設(shè)施即服務(wù)(IaaS)、平臺(tái)即服務(wù)(PaaS)和軟件即服務(wù)(SaaS)。IaaS是指消費(fèi)者通過(guò)Internet可以從完善的計(jì)算機(jī)基礎(chǔ)設(shè)施獲得服務(wù)。PaaS是指將軟件研發(fā)的平臺(tái)作為一種服務(wù)，以SaaS的模式提交給用戶，因此也是SaaS模式的一種應(yīng)用。SaaS是一種通過(guò)Internet提供軟件的模式，用戶無(wú)需購(gòu)買軟件，而是向提供商租用基于Web的軟件來(lái)管理企業(yè)經(jīng)營(yíng)活動(dòng)。

隨著云計(jì)算環(huán)境的廣泛應(yīng)用，公有、私有及混合云提供了大量具有相同功能和不同服務(wù)質(zhì)量的云服務(wù)。同時(shí)，單個(gè)服務(wù)往往不能滿足任務(wù)需求,而多個(gè)服務(wù)的組合卻可以派生出新的服務(wù)從而滿足需求。因此，如何構(gòu)建能夠滿足用戶QoS需求的組合云服務(wù)是云服務(wù)應(yīng)用領(lǐng)域亟待解決的難題。

本文的主要研究?jī)?nèi)容是：(1)通過(guò)時(shí)間序列建模將云服務(wù)組合轉(zhuǎn)化成時(shí)間序列的相似度對(duì)比問(wèn)題；(2)采用基于主成分分析的擴(kuò)展Frobenius范數(shù)距離/歐幾里得距離、Brute-Force等方法等度量方法進(jìn)行求解；(3)通過(guò)對(duì)比實(shí)驗(yàn)說(shuō)明基于主成分分析的擴(kuò)展Frobenius范數(shù)距離度量方法在時(shí)間和準(zhǔn)確性上的優(yōu)越性。

2 國(guó)內(nèi)外研究現(xiàn)狀

隨著對(duì)QoS感知的云服務(wù)組合問(wèn)題的研究日益深入，已經(jīng)提出了大量相關(guān)算法[1]。QoS感知的云服務(wù)組合問(wèn)題分為兩類：一是在同一時(shí)刻的服務(wù)組合，二是不同時(shí)刻的服務(wù)組合。對(duì)于同一時(shí)刻能夠提供的多種服務(wù)組合研究成果有很多，如Canfora G等人[2]提出了基于遺傳算法的云服務(wù)組合方法，將組合服務(wù)編碼成染色體，適應(yīng)度值是服務(wù)的綜合QoS?；谶z傳算法的QoS感知的云服務(wù)組合算法在文獻(xiàn)[3～6]中進(jìn)行了許多改進(jìn)。文獻(xiàn)[3]提出了可用于QoS感知服務(wù)組合的樹(shù)編碼遺傳算法(TGA)，對(duì)染色體進(jìn)行樹(shù)形編碼。實(shí)驗(yàn)結(jié)果表明，TGA的運(yùn)行速度與一維編碼GA的最佳結(jié)果是一樣的，并且樹(shù)編碼算法在運(yùn)行時(shí)支持服務(wù)組合進(jìn)行重新規(guī)劃。文獻(xiàn)[4]提出了基于種群的多樣性和關(guān)系矩陣編碼方案的遺傳算法(CoDiGA)，該算法有效克服了早熟,并大大提高了遺傳算法的收斂性和穩(wěn)定性、服務(wù)選擇組合的有效性。文獻(xiàn)[5]提出的混合遺傳算法可以有效解決大規(guī)模服務(wù)和限制下的服務(wù)組合優(yōu)化問(wèn)題。文獻(xiàn)[6]提出的基于處罰的遺傳算法，可以將組合服務(wù)分解為多個(gè)服務(wù)組件，便于組合服務(wù)的分散執(zhí)行，以提高服務(wù)組合的效率。文獻(xiàn)[7]提出可用于現(xiàn)有服務(wù)組合算法的緩存機(jī)制，以減少各服務(wù)組合算法的計(jì)算時(shí)間，提高服務(wù)組合的時(shí)間性能。文獻(xiàn)[8]中基于免疫遺傳算法的服務(wù)組合方法，將免疫原理引入遺傳算法(GA)中，免疫選擇可有效地防止早熟，基于免疫記憶的子群體信息交換策略可加速收斂，從而提高服務(wù)組合的質(zhì)量和收斂速度。文獻(xiàn)[9]中遵循精英螞蟻保留策略的蟻群系統(tǒng)被應(yīng)用于組合問(wèn)題求解。文獻(xiàn)[10]提出了一種基于移動(dòng)代理的蟻群優(yōu)化算法以提高組合的效率。文獻(xiàn)[11,12]中用蟻群算法自動(dòng)進(jìn)行服務(wù)組合。文獻(xiàn)[13]提出一種基于QoS 的啟發(fā)式算法，可以動(dòng)態(tài)調(diào)用Web Service來(lái)自動(dòng)生成滿足用戶所需目標(biāo)的Web Service組合。文獻(xiàn)[14]基于模擬退火算法求解QoS約束Web服務(wù)組合。文獻(xiàn)[15]提出了混合QoS模型感知的語(yǔ)義Web服務(wù)組合決策算法。文獻(xiàn)[16]用改進(jìn)的社會(huì)認(rèn)知算法對(duì)QoS感知的云服務(wù)優(yōu)化組合問(wèn)題進(jìn)行求解。文獻(xiàn)[17]提出的基于擴(kuò)展圖規(guī)劃的Top-K服務(wù)組合方法,通過(guò)服務(wù)索引和增加圖規(guī)劃中的輔助節(jié)點(diǎn), 使得經(jīng)過(guò)一次規(guī)劃搜索即可找到Top-K個(gè)滿足用戶QoS要求的組合服務(wù)。

以上提出的算法都沒(méi)有考慮組合的長(zhǎng)期性目標(biāo)問(wèn)題而僅僅是滿足當(dāng)前目標(biāo)，忽略了云服務(wù)組合的時(shí)間因素[18,19]，這是第二類云服務(wù)組合問(wèn)題—不同時(shí)刻的云服務(wù)組合的重點(diǎn)。事實(shí)上某些組合服務(wù)的性能在當(dāng)前并非是最好的，但在幾年后會(huì)表現(xiàn)良好。文獻(xiàn)[18]利用貝葉斯網(wǎng)絡(luò)構(gòu)建終端用戶的經(jīng)濟(jì)模型，將云服務(wù)組合轉(zhuǎn)化成影響圖問(wèn)題求解；時(shí)間序列可以描述各個(gè)因素隨時(shí)間變化的過(guò)程，非常利于感知QoS的云服務(wù)組合問(wèn)題的求解；文獻(xiàn)[19]用歐幾里得距離度量隨時(shí)間變化的QoS因素及其因素間聯(lián)系。本文研究基于時(shí)間序列的感知QoS的云服務(wù)組合，將服務(wù)的QoS偏好隨時(shí)間不斷變化的過(guò)程納入云服務(wù)組合的研究范圍，將云服務(wù)組合建模成時(shí)間序列的相似度對(duì)比問(wèn)題，并通過(guò)實(shí)驗(yàn)驗(yàn)證擴(kuò)展Frobenius范數(shù)距離度量相似度[20]在時(shí)間和準(zhǔn)確性上的優(yōu)越性。

3 云服務(wù)組合架構(gòu)

考慮云服務(wù)組合的四種重要因素：服務(wù)的使用者、服務(wù)組合、SaaS提供者和IaaS(包含PaaS平臺(tái)即服務(wù))提供者，構(gòu)建四層云服務(wù)組合架構(gòu)，如圖1所示。其中，服務(wù)使用者通常是大的公司或組織機(jī)構(gòu),如學(xué)校、政府等。服務(wù)組合層包含多種服務(wù)組合框架。SaaS和IaaS提供者分別為使用者軟件及基礎(chǔ)設(shè)施服務(wù)，基礎(chǔ)設(shè)施服務(wù)通常包括CPU、存儲(chǔ)空間和網(wǎng)絡(luò)等服務(wù)。服務(wù)組合為使用者提供組合服務(wù)，組合服務(wù)是指由不同SaaS和IaaS提供方提供的多種服務(wù)的組合。服務(wù)組合層直接作用于SaaS層，并通過(guò)SaaS層間接作用于IaaS層，因?yàn)槿粢褂肅PU、存儲(chǔ)空間和網(wǎng)絡(luò)等服務(wù)資源，必須通過(guò)相應(yīng)的軟件接口。

Figure 1 Architecture of cloud service composition圖1 云服務(wù)組合架構(gòu)

4 問(wèn)題描述

單個(gè)服務(wù)無(wú)法滿足復(fù)雜應(yīng)用需求，故需要通過(guò)上述云服務(wù)組合架構(gòu)為用戶提供組合應(yīng)用。如圖2所示，該應(yīng)用包含對(duì)應(yīng)于各個(gè)任務(wù)的抽象SaaS，同時(shí)需要由IaaS提供方提供CPU、網(wǎng)絡(luò)和存儲(chǔ)等服務(wù)資源。CPU服務(wù)主要用于數(shù)據(jù)計(jì)算，存儲(chǔ)服務(wù)用于保存中間數(shù)據(jù)結(jié)果，網(wǎng)絡(luò)服務(wù)用于傳輸數(shù)據(jù)。

對(duì)于任務(wù)Tk所需的軟件服務(wù)有眾多候選SaaS提供者Sk={Sk1，Sk2,…}，還有候選IaaS提供者S={S1,S2,…}可以提供基礎(chǔ)設(shè)施服務(wù)，因此可以形成多個(gè)組合方案。例如，一種備選組合方案Plan={Si,S1i,S2i,S3i,…}，由Si提供IaaS，各任務(wù)所需的SaaS服務(wù)分別由S1i、S2i、S3i、……提供。

考慮到用戶對(duì)應(yīng)用的QoS需求是隨時(shí)變化的，服務(wù)提供方所提供的服務(wù)所滿足的QoS約束也是隨時(shí)變化的，因此，需將該系統(tǒng)提供的QoS服務(wù)轉(zhuǎn)化為基于時(shí)間的服務(wù)序列并存儲(chǔ)，然后將用戶的QoS需求也轉(zhuǎn)化為基于時(shí)間的請(qǐng)求序列。將上述兩種序列進(jìn)行對(duì)比，相似度最大的時(shí)間序列所對(duì)應(yīng)的組合服務(wù)就是問(wèn)題的最優(yōu)解。

Figure 2 Application on the cloud service composition architecture圖2 云服務(wù)組合架構(gòu)上的應(yīng)用

5 時(shí)間序列建模

時(shí)間序列是按照時(shí)間順序取得的一系列觀測(cè)值，能夠體現(xiàn)觀測(cè)值不斷隨時(shí)間變化的過(guò)程，表示為Xi(t)=[i=1,2,…,n;t=1,2,…,m]，當(dāng)n=1時(shí)稱為一元時(shí)間序列，當(dāng)n≥2時(shí)表示多元時(shí)間序列MTS(Multiple Time Series)。用戶QoS需求是時(shí)時(shí)變化的，服務(wù)提供方提供的服務(wù)所滿足的QoS約束也是隨時(shí)間而變化的。因此，需將提供的QoS服務(wù)轉(zhuǎn)化為基于時(shí)間的服務(wù)序列并存儲(chǔ)，然后將用戶的QoS需求也轉(zhuǎn)化為基于時(shí)間的請(qǐng)求序列。

QoS偏好因素建模成時(shí)間序列MTS={Q1,Q2,Q3,…,Qm}。該序列的一元Qi={Vi1，Vi2，…,Vin}對(duì)應(yīng)一種QoS因素，m是因素個(gè)數(shù)，Vij代表因素i在時(shí)刻tj的值，n是時(shí)間序列長(zhǎng)度。組合型服務(wù)的QoS偏好所對(duì)應(yīng)的時(shí)間序列中，Vij由各個(gè)服務(wù)的相應(yīng)值聚合形成。將QoS偏好建模成時(shí)間序列的基本步驟如下：

(1)設(shè)定QoS偏好因素的類型，如流通量(Throughput)、信譽(yù)度(Reputation)、價(jià)格(Cost)等等；

(2)設(shè)定QoS偏好因素變化的一系列時(shí)間點(diǎn)(t=t1,t2,t3,t4,…)；

(3)獲取QoS偏好在不同時(shí)間點(diǎn)的值，并按照時(shí)間順序表示成一元/多元時(shí)間序列。

建模完成后，服務(wù)組合問(wèn)題就轉(zhuǎn)化成了時(shí)間序列的相似度比較，目標(biāo)是找到與用戶請(qǐng)求序列最為相似的服務(wù)時(shí)間序列。

6 時(shí)間序列相似度對(duì)比

6.1 歐幾里得距離

歐幾里得距離即歐幾里得度量。歐幾里得度量(Euclidean Metric)是一個(gè)常用的距離定義，指在m維空間中兩個(gè)點(diǎn)之間的真實(shí)距離，或者向量的自然長(zhǎng)度(即該點(diǎn)到原點(diǎn)的距離)。在二維和三維空間中的歐幾里得距離就是兩點(diǎn)之間的實(shí)際距離。

二維空間的歐幾里得距離計(jì)算公式為：

(1)

三維空間的歐幾里得距離計(jì)算公式為:

(2)

以此類推，序列長(zhǎng)度為n、包含m個(gè)QoS指標(biāo)的兩個(gè)多元時(shí)間序列MTS1={a11,a12,…,a1m;a21,a22,…,a2m;…；an1,an2,…,anm}和MTS2={b11,b12,…,b1m;b21,b22,…,b2m;…；bn1,bn2,…,bnm}相似度對(duì)比的歐幾里得距離計(jì)算公式為：

(3)

6.2 擴(kuò)展Frobenius范數(shù)距離

m×n維度矩陣A的Frobenius范數(shù)為：

(4)

矩陣A的擴(kuò)展Frobenius范數(shù)為：

(5)

其中，wij表示第i列對(duì)應(yīng)權(quán)重。

兩個(gè)矩陣A=[a1,a2,…,an]，B=[b1,b2,…,bn]，ai和bi分別表示A和B的單位正交向量，θi是向量ai和bi間的夾角，則矩陣C=A-B的擴(kuò)展Frobenius范數(shù)是：

(6)

假定兩個(gè)多元時(shí)間序列MA和MB均為m×n維矩陣。求得其對(duì)應(yīng)的協(xié)方差矩陣是A′和B′，再通過(guò)奇異值分解(SVD)得到相應(yīng)的特征向量矩陣VA′=[a1,a2,…,an]和VB′=[b1,b2,…,bn]，則這兩個(gè)MTS間的擴(kuò)展Frobenius范數(shù)距離為：

(7)

為了方便計(jì)算，擴(kuò)展Frobenius范數(shù)(相似度)也可以定義為：

(8)

因此，兩個(gè)MTS具有較大DEros(MA′,MB′,W)就有較小的Eros，代表它們的相似度低；否則，這兩個(gè)MTS越相似。

假定已對(duì)所有的MTS進(jìn)行了主成分分析，抽取出了前K個(gè)主成分，對(duì)應(yīng)的權(quán)重系數(shù)向量wii也已獲得，則兩個(gè)MTS間的擴(kuò)展Frobenius范數(shù)距離為：

(9)

6.3 主成分分析

QoS因素及其聯(lián)系是復(fù)雜的，窮舉性的對(duì)比是非常耗時(shí)的過(guò)程，故用主程序分析進(jìn)行序列的降維操作，以此提取出互不相干的若干維數(shù)據(jù)成分替代原序列。

主成分分析過(guò)程：

(1)標(biāo)準(zhǔn)化：不同QoS指標(biāo)有不同量綱，標(biāo)準(zhǔn)化可消除量綱差異；

(2)求協(xié)方差矩陣；

(3)奇異值分解，獲取特征值和特征向量；

(4)計(jì)算權(quán)向量，并保留K個(gè)主成分及其特征值和特征向量。

7 實(shí)驗(yàn)結(jié)果與分析

本文在VS及Matlab環(huán)境下進(jìn)行了一系列實(shí)驗(yàn)，以此評(píng)估二維和多維時(shí)間序列相似度對(duì)比方法的時(shí)間性能及準(zhǔn)確性。

(1)二維時(shí)間序列相似度對(duì)比。

用歐幾里得距離和擴(kuò)展Frobenius范數(shù)距離度量二維時(shí)間序列的相似度，并進(jìn)行準(zhǔn)確性對(duì)比。為保證實(shí)驗(yàn)結(jié)果的真實(shí)可靠性，選取的數(shù)據(jù)來(lái)源于ZhengZi-bin等多位學(xué)者專家研究提供的開(kāi)放WebService數(shù)據(jù)集。 實(shí)驗(yàn)過(guò)程如下：

第1步數(shù)據(jù)抽取。從數(shù)據(jù)源中按序抽取格式為IntervalIDWebServiceID esponse-time hroughput、時(shí)間序列長(zhǎng)度為142，分別包含五種服務(wù)類型及其QoS指標(biāo)的請(qǐng)求數(shù)據(jù)集query和包含30種服務(wù)及其QoS指標(biāo)的數(shù)據(jù)集link。

第2步數(shù)據(jù)處理和變換。將兩個(gè)數(shù)據(jù)集中的數(shù)據(jù)按照WebServiceID提取出對(duì)應(yīng)的QoS時(shí)間序列，格式為WebServiceIDIntervalID esponse-time hrougput，并將link數(shù)據(jù)集的服務(wù)分為五組，每組中的六個(gè)服務(wù)可提供相同功能，例如，0～5號(hào)服務(wù)可以滿足請(qǐng)求服務(wù)類型0,6～11號(hào)服務(wù)可以滿足請(qǐng)求服務(wù)類型1，以此類推。

第3步用歐幾里得距離度量時(shí)間序列相似度，以選取最接近請(qǐng)求序列的服務(wù)組合。

第4步用擴(kuò)展Frobenius范數(shù)距離度量時(shí)間序列相似度。可以改變兩個(gè)QoS指標(biāo)的權(quán)重，以選取最接近請(qǐng)求序列的服務(wù)組合。

實(shí)驗(yàn)結(jié)果如表1所示，結(jié)果的格式為服務(wù)編號(hào)/距離,而0.1/0.9表示response-time/througput的權(quán)重比率。

由實(shí)驗(yàn)結(jié)果可知，采用擴(kuò)展Frobenius范數(shù)距離度量相似度在準(zhǔn)確性上更有優(yōu)勢(shì)，原因有以下兩點(diǎn)：①Q(mào)oS權(quán)重比率會(huì)影響實(shí)驗(yàn)結(jié)果，采用不同QoS權(quán)重比率可以獲得不同的實(shí)驗(yàn)結(jié)果，通過(guò)改變QoS權(quán)重比率、多次測(cè)試取得最頻繁出現(xiàn)的結(jié)果會(huì)更準(zhǔn)確。②擴(kuò)展Frobenius范數(shù)距離度量相似度會(huì)考慮不同QoS向量的夾角，使計(jì)算結(jié)果更精準(zhǔn)。

(2)多維時(shí)間序列相似度對(duì)比。

用基于主成分分析的擴(kuò)展Frobenius范數(shù)距離(MTS算法)和歐幾里得距離(TSG算法)、Brute-Force等方法度量多維時(shí)間序列的相似度，并進(jìn)行了時(shí)間性能的比較。其中，Brute-Force算法通過(guò)窮舉計(jì)算所有QoS因素對(duì)的距離進(jìn)行相似度對(duì)比。

多維時(shí)間序列的相似度對(duì)比的目的是進(jìn)行時(shí)間性能的對(duì)比，故數(shù)據(jù)集采用隨機(jī)生成方式，并將每一類QoS指標(biāo)的測(cè)量結(jié)果值限定在一定范圍內(nèi)。首先隨機(jī)生成較大的用于比較的數(shù)據(jù)集表示服務(wù)提供方的服務(wù)所滿足的QoS，然后生成較小的MTS數(shù)據(jù)集用以代表用戶的QoS偏好請(qǐng)求，建模的MTS范例如表2所示。

Table 2 MTS sample(part)表2 MTS范例(部分)

用平均時(shí)間消耗進(jìn)行算法比較，通過(guò)不斷改變數(shù)據(jù)集的大小計(jì)算各算法平均時(shí)間消耗(單位s)，對(duì)比結(jié)果如表3所示。由表3可知，基于主成分分析的擴(kuò)展Frobenius范數(shù)距離(MTS算法)的時(shí)間性能明顯優(yōu)于基于主成分分析的歐幾里得距離(TSG算法)和Brute-Force(BF)算法，也即說(shuō)明了基于

主成分分析的擴(kuò)展Frobenius范數(shù)距離度量相似度的時(shí)間優(yōu)越性。

Table 3 Comparison of algorithms’ time performance表3 算法的時(shí)間性能對(duì)比

8 結(jié)束語(yǔ)

本文研究基于時(shí)間序列的感知QoS的云服務(wù)組合，將服務(wù)的QoS偏好隨時(shí)間不斷變化的過(guò)程納入云服務(wù)組合的研究范圍，將云服務(wù)組合建模成時(shí)間序列的相似度對(duì)比問(wèn)題，繼而通過(guò)時(shí)間序列相似度的比較找尋符合用戶需求的組合型云服務(wù)。一系列實(shí)驗(yàn)結(jié)果驗(yàn)證了擴(kuò)展Frobenius范數(shù)距離度量相似度在時(shí)間和準(zhǔn)確性上的優(yōu)越性。以后的研究工作可從以下幾點(diǎn)進(jìn)行：(1)本文建立了時(shí)間序列模型，但進(jìn)行相信度對(duì)比的兩個(gè)時(shí)間序列的維度和時(shí)間間隔均一致，故略顯簡(jiǎn)單和粗糙，可以考慮建立更為復(fù)雜且貼切的時(shí)間序列模型；(2)時(shí)間序列的比較可以包含時(shí)間序列的預(yù)測(cè)，進(jìn)而篩選出更適合的組合服務(wù)以滿足用戶的未來(lái)需求；(3)本文所研究的云服務(wù)組合僅考慮服務(wù)的QoS需求，可以進(jìn)一步將服務(wù)的功能性及事務(wù)性需求納入服務(wù)組合的因素范圍。

[1] Strunk A. QoS-aware service composition:A survey[C]∥Proc of the 2010 8th IEEE European Conference on Web Services(ECOWS’10), 2010:67-74.

[2] Canfora G, Di Penta M, Esposito R, et al. An approach for QoS-aware service composition based on genetic algorithms[C]∥ Proc of the 2005 ACM Conference on Genetic and Evolutionary Computation(GECCO’05), 2005:1069-1075.

[3] Gao C,Cai M,Chen H.QoS-aware service composition based on tree-coded genetic algorithm [C]∥Proc of the 31st IEEE Annual International Computer Software and Applications Conference(COMPSAC),2007:361-367.

Table 1 Comparison of similarity on two-dimensional time series表1 二維時(shí)間序列相似度對(duì)比結(jié)果

[4] Ma Y,Zhang C.Quick convergence of genetic algorithm for QoS-driven web service selection [J]. Computer Networks, 2008,52 (5):1093-1104.

[5] Tang M,Ai L.A hybrid genetic algorithm for the optimal constrained web service selection problem in web service composition[C]∥ Proc of IEEE Congress on Evolutionary Computation, 2010:1-8.

[6] Ai L, Tang M, Fidge C. Partitioning composite web services for decentralized execution using a genetic algorithm [J]. Future Generation Computer Systems, 2011, 27 (2):157-172.

[7] Wu Q, Zhu Q, Li P. A caching mechanism for QoS-aware service composition [J]. Journal of Web Engineering ,2012,11 (2):119-130.

[8] Chen Liang,Sun Min.Web services composition method based on immune genetic algorithm[J]. Computer Engineering, 2010, 36(10):226-230.(in Chinese)

[9] Zheng X,Luo J,Song A.Ant colony system based algorithm for QoS-aware web service selection[C]∥ Proc of the 4th International Conference on Grid Service Engineering and Management( GSEM), 2007:39-50.

[10] Dhore S R, Kharat M. QoS based web services composition using ant colony optimization:Mobile agent approach [J]. International Journal of Advanced Research in Computer and Communication Engineering, 2012, 1(7):519-527.

[11] Zhou Xian-zhong,Wu Kui,Xiao Yi-hong.Automatic web service composition based on any colony algorithm[C]∥Proc of Decision Evaluation and Science, 2009:228-236.(in Chinese)

[12] Shen Ji-quan, Zheng Xue-feng, Tu Xu-yan. An approach to service composition based on ant colony algorithm[J].Journal of Wuhan University of Technology (Transportation Science & Engineering), 2009, 33(6):1179-1182.(in Chinese)

[13] Yin Rong-wang,Mao Zhi-jian.A QoS-guaranteed web service composition[J]. Computer Knowledge and Technology (Network Communication and Security), 2007(11):1276-1278.(in Chinese)

[14] Liu Qing, Zhang Shi-long, Yang Rui, et al. Web service composition with QoS bound based on simulated annealing algorithm[J]. Journal of Southeast University(English Edition),2008,24(3):308-311.

[15] Li Zhen. Research on hybrid QoS-aware semantic web service composition decision making algorithm [D]. Beijing:Beijing University of Posts and Telecommunications, 2008.(in Chinese)

[16] Liu Zhi-zhong, Lei Guan-jun, Xue Xiao, et al. Research on QoS-aware cloud service optimal composition [J]. Application Research of Computers, 2012, 29(10):3919-3921.(in Chinese)

[17] Xu Meng, Cui Li-zhen, Li Qing-zhong. An extend graph-planning based ontop-Kservice composition method[J]. Acta Electronica Sinica, 2012, 40(7):1404-1409.(in Chinese)

[18] Zhen Ye,Bouguettaya A,Zhou Xiao-fang.QoS-aware cloud service composition based on economic models[C]∥Proc of the 10th International Conference on Service-Oriented Computing (ICSOC),2012:111-126.

[19] Zhen Ye,Bouguettaya A,Zhou Xiao-fang.QoS-aware cloud service composition using time series[C]∥Proc of the 11th International Conference on Service-Oriented Computing (ICSOC), 2013:9-22.

[20] Guo Xiao-fang, Li Feng. Analysis on similarity of multivariate time series based on Eros [J]. Computer Engineering and Applications, 2012, 48(23):111-114.(in Chinese)

附中文參考文獻(xiàn)：

[8] 陳亮,孫敏.基于免疫遺傳算法的Web 服務(wù)組合方法[J].計(jì)算機(jī)工程,2010,36(10):226-230.

[11] 周獻(xiàn)中,吳奎,蕭毅鴻.基于蟻群算法的Web服務(wù)自動(dòng)組合[C]∥決策科學(xué)與評(píng)價(jià),2009:228-236.

[12] 沈記全,鄭雪峰,涂序彥.一種基于蟻群算法的服務(wù)組合方法[J].武漢理工大學(xué)學(xué)報(bào)(交通科學(xué)與工程版),2009,33(6):1179-1182.

[13] 殷榮網(wǎng),冒志建.一種有QoS保障的服務(wù)組合方法[J].電腦知識(shí)與技術(shù)(網(wǎng)絡(luò)通訊與安全),2007(11):1276-1278.

[15] 李禎.混合QoS模型感知的語(yǔ)義Web服務(wù)組合決策算法研究[D].北京：北京郵電大學(xué),2008.

[16] 劉志中,雷冠軍,薛霄,等.QoS感知的云服務(wù)優(yōu)化組合研究[J].計(jì)算機(jī)應(yīng)用研究,2012, 29(10):3919-3921.

[17] 徐猛,崔立真,李慶忠.基于擴(kuò)展圖規(guī)劃的top-K服務(wù)組合方法研究[J].電子學(xué)報(bào),2012,40(7):1404-1409.

[20] 郭小芳,李鋒.基于Eros的多元時(shí)間序列相似度分析[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(23):111-114.

XIAOWen-juan,born in 1991,MS candidate,her research interest includes service computing.

段玉聰(1977),男，河南南陽(yáng)人，博士后，教授，CCF會(huì)員(E200033712M)，研究方向?yàn)榉?wù)計(jì)算。E-mail:duanyucong@hotmail.com

DUANYu-cong,born in 1977,post doctor,professor,CCF member(E200033712M)，his research interest includes service computing.

QoS-awarecloudservicecompositionbasedontimeseries

XIAO Wen-juan，DUAN Yu-cong

(College of Information Science and Technology,Hainan University,Haikou 570228,China)

In this paper, we study QoS-aware cloud service composition based on time series, taking the sustaining change process of service QoS preference into research scope of cloud service composition,and transform the composition of cloud services into similarity comparison problems between time series.Euclidean distance and the extend Frobenius norm distance are used to measure similarity between two-dimensional time series respectively. In the next,the extend Frobenius norm distance or Euclidean distance based on principal component analysis and Brute-Force method are adopted to measure the similarity between multidimensional time series. Experiments show that the extend Frobenius norm distance has better performance on similarity measurement in time and accuracy.

time series;QoS;cloud service composition;similarity comparison

1007-130X(2014)11-2061-06

2014-06-09;

：2014-08-19

國(guó)家自然科學(xué)基金資助項(xiàng)目(61363007);海南大學(xué)資助項(xiàng)目(HDSF201310,kyqd1242)

TP393.027

：A

10.3969/j.issn.1007-130X.2014.11.003

肖文娟(1991),女，湖南祁陽(yáng)人，碩士生，研究方向?yàn)榉?wù)計(jì)算。E-mail:xwj625@sina.cn

通信地址：570228 海南省海口市海南大學(xué)信息科學(xué)技術(shù)學(xué)院

Address:College of Information Science and Technology,Hainan University,Haikou 570228,Hainan,P.R.China