余 建,林志興,余高鋒,肖香梅,劉孫發(fā)
(1.三明學(xué)院 a.網(wǎng)絡(luò)中心;b.信息工程學(xué)院,福建 三明365004;2.物聯(lián)網(wǎng)應(yīng)用福建省高校工程研究中心,福建 三明365004)
隨著云計(jì)算[1]、物聯(lián)網(wǎng)[2]、移動(dòng)互聯(lián)網(wǎng)[3]、大數(shù)據(jù)[4]等現(xiàn)代信息技術(shù)的不斷發(fā)展,用戶(特別是手機(jī)用戶)需求日益增多,單一的服務(wù)已經(jīng)無法滿足,而服務(wù)組合技術(shù)可將現(xiàn)有的分布式的服務(wù)集成為滿足用戶需求的組合服務(wù)[5]。在個(gè)性化需求不斷擴(kuò)大的背景下,隨著大量的手機(jī)APP軟件的推出,如何將不同的服務(wù)進(jìn)行組合而又能保障全局網(wǎng)絡(luò)的服務(wù)質(zhì)量(Quality of Service,QoS),已成為當(dāng)前亟待解決的問題。同時(shí)考慮云服務(wù)和網(wǎng)絡(luò)服務(wù)的QoS屬性,解決一體化環(huán)境下服務(wù)組合問題,給出最優(yōu)的服務(wù)組合算法,為不同需求的用戶提供點(diǎn)到點(diǎn)服務(wù)質(zhì)量保障,具有重要的理論價(jià)值和廣闊的應(yīng)用前景。
針對服務(wù)組合優(yōu)化,許多學(xué)者進(jìn)行了大量的研究。張以文等[6]提出了一種任務(wù)?;惴?Task-granular Algorithm,TgA),用于快速有效地求解大規(guī)模服務(wù)組合優(yōu)化問題。張麗娜等[7]在解決海量線上到線下(Online to Offline,O2O)服務(wù)環(huán)境中,引入社會(huì)關(guān)系理論,在線上服務(wù)組合階段考慮提高線下服務(wù)提供商之間的協(xié)作效率,同時(shí)優(yōu)化算法的執(zhí)行效率。蔡江安等[8]等針對服務(wù)組合問題,利用服務(wù)組合策略,建立了以時(shí)間、實(shí)用性、創(chuàng)新性、可靠性等為優(yōu)化目標(biāo)的服務(wù)組合優(yōu)化模型;同時(shí)通過聚類算法以及對組合服務(wù)的關(guān)聯(lián)規(guī)則對路徑搜索空間進(jìn)行預(yù)處理,大大提高了搜索空間的效率,讓知識(shí)服務(wù)資源能在服務(wù)組合中以較短的時(shí)間內(nèi)進(jìn)行精準(zhǔn)定位并與之匹配,較大程度上提高服務(wù)組合的性能。
Ergun等人[9]針對雙度量QoS選路問題提出了一種性能出色的近似算法,通過選取最優(yōu)的一個(gè)上、下界,引入一個(gè)多項(xiàng)式時(shí)間的近似測試過程,去不斷地縮小上下界之間的距離,把路徑搜索問題轉(zhuǎn)化成區(qū)間搜索問題,在不斷縮小的范圍內(nèi)快速查找最優(yōu)解。Xue等人[10]提出了一種PeseudoMCPP算法,給出了一種利用路徑跳數(shù)構(gòu)建路徑搜索空間,可以獲得在滿足第一維路徑權(quán)重約束D的情況下,其他維路徑權(quán)重也都滿足于某個(gè)約束C。由于Ergun等人提出的算法非常耗時(shí),而Xue等人的算法不能繼承已知的結(jié)果,因而都難以獲得質(zhì)量更好的求解方案。本文在綜合考慮網(wǎng)絡(luò)服務(wù)特點(diǎn)的基礎(chǔ)上,結(jié)合以上兩種算法思路,給出了一種服務(wù)最優(yōu)路徑選擇算法(Optimal Path Selection,OPS),以解決QoS感知的網(wǎng)絡(luò)服務(wù)組合問題,提升網(wǎng)絡(luò)服務(wù)質(zhì)量水平,改善用戶體驗(yàn)質(zhì)量。
在某商務(wù)出行案例中,如果每一個(gè)服務(wù)類表示為{(S1,S2,S3,…,St)},按照組合服務(wù)對應(yīng)的主體,我們可分為4個(gè)服務(wù)實(shí)例,即打車平臺(tái)服務(wù)、網(wǎng)上購票、網(wǎng)上訂餐、酒店預(yù)定,任務(wù)粒(抽象服務(wù))表示為{(S1,S2,S3,S4)}。若假設(shè)每個(gè)任務(wù)都有相關(guān)候選服務(wù)可以實(shí)現(xiàn)其所在服務(wù)類的功能,但是它們有不同的服務(wù)質(zhì)量,因此,人們會(huì)根據(jù)候選服務(wù)的服務(wù)質(zhì)量選擇最優(yōu)的服務(wù)組合方案。
服務(wù)組合能充分利用目前已有的服務(wù),具有即時(shí)、快速和靈活組建分布式松耦合的優(yōu)勢[11]。當(dāng)網(wǎng)絡(luò)用戶向服務(wù)器端請求服務(wù)時(shí),服務(wù)器端將調(diào)用服務(wù)組合過程,選擇一系列原子服務(wù)組件來構(gòu)建功能復(fù)雜的組合服務(wù),以滿足網(wǎng)絡(luò)用戶個(gè)性化的需求。本文中的服務(wù)組合路徑包括多個(gè)單個(gè)服務(wù)進(jìn)行組合[12],即組合服務(wù)(也稱多目標(biāo)服務(wù)組合、多任務(wù)組合服務(wù)或綜合性服務(wù))。
定義1 可行的服務(wù)組合方案。每個(gè)服務(wù)Si(1≤i≤H),每個(gè)服務(wù)對應(yīng)一個(gè)原子服務(wù)組件SH,假設(shè)一個(gè)服務(wù)組合方案,如在某服務(wù)網(wǎng)絡(luò)中的一條路徑p,cv和Ch代表節(jié)點(diǎn)v和h的服務(wù)能力,ωk為其路徑的最小權(quán)重,Wk代表約束條件,K為任務(wù)S執(zhí)行的任務(wù)次數(shù),如果對于?v∈p有cv≥Ch,節(jié)點(diǎn)不和ωk(p)≤Wk,其中υ∈Sh,1≤h≤H,1≤k≤K,那么路徑p是一個(gè)可行的服務(wù)組合方案。
服務(wù)組合流程包括串行、選擇、并行等結(jié)構(gòu),這些基本結(jié)構(gòu)可以構(gòu)造出很多結(jié)構(gòu)不同的復(fù)雜服務(wù)組合流程。在基于功能方面的需求為請求中的每一個(gè)功能選擇服務(wù)之后,服務(wù)目錄根據(jù)用戶的QoS要求,在大量候選的服務(wù)組合路徑流程中選出滿足用戶要求的最優(yōu)組合路徑。
當(dāng)用戶在每一個(gè)任務(wù)粒中選對一個(gè)候選服務(wù)時(shí),根據(jù)網(wǎng)絡(luò)服務(wù)中最優(yōu)組合路徑選擇原則,云服務(wù)器應(yīng)在最短時(shí)間內(nèi)響應(yīng)用戶需求。由于每個(gè)候選服務(wù)組合路徑包含多種拓?fù)浣Y(jié)構(gòu),現(xiàn)有的大多數(shù)服務(wù)選擇算法無法直接處理多種結(jié)構(gòu),因此在服務(wù)選擇之前需要對拓?fù)溥M(jìn)行結(jié)構(gòu)轉(zhuǎn)換[13],在這個(gè)轉(zhuǎn)化過程中Sa和Sb保持不變。執(zhí)行完Sa之后,就分別以p1,p2,…,pn概率執(zhí)行服務(wù)S1,S2,…,Sn,然后再執(zhí)行Sb。ti、ci、ri、thi分別代表的響應(yīng)時(shí)間、代價(jià)、可靠性和吞吐量,F(xiàn)i(x)代表概率響應(yīng)時(shí)間t的概率密度函數(shù),Pi1(x)代表代價(jià)c的密度函數(shù),Pi2(x)代表可靠性r的密度函數(shù),Pi3(x)代表吞吐量th′的密度函數(shù),P代表順序結(jié)構(gòu)轉(zhuǎn)換后的服務(wù)S1n的值,計(jì)算如下:
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
一個(gè)服務(wù)組合的流程是[14]:用戶先提出自已的業(yè)務(wù)需求,服務(wù)組合根據(jù)用戶的需求設(shè)計(jì)一個(gè)抽象服務(wù)模型,然后在每一個(gè)抽象服務(wù)所對應(yīng)的候選服務(wù)集合中選擇一個(gè)服務(wù)與之相對應(yīng),并把最后所形成的關(guān)聯(lián)服務(wù)也即組合服務(wù)反饋給用戶,該組合一定是滿足用戶約束且QoS最優(yōu)的。組合服務(wù)是一個(gè)組合服務(wù)集合,其所包含的組合服務(wù)不被其他組合服務(wù)支配,它通常被用來提高組合服務(wù)選擇的效率。
為了找到更優(yōu)的服務(wù)組合路徑,我們建立了QoS感知服務(wù)組合模型。在服務(wù)組合模型中,單一服務(wù)通常無法滿足用戶需求,而需要將多種服務(wù)按照順序組成一條工作流來完成用戶請求。在組合服務(wù)選擇過程中,某個(gè)服務(wù)通常有多個(gè)候選服務(wù)[15]提供商。在組合服務(wù)集合中,通過不同任務(wù)中的候選服務(wù)之間存在關(guān)聯(lián)性,再通過OSP算法建立最優(yōu)路徑選擇,從而找到一條花費(fèi)較小的服務(wù)組合路徑。如圖1所示,每個(gè)服務(wù)Si(1≤i≤H)中有許多原子服務(wù)組件Sij(1≤i≤H,1≤f≤F)作為服務(wù)組合的候選組件。該感知服務(wù)組合模型將網(wǎng)絡(luò)服務(wù)和云服務(wù)的QoS參數(shù)一并映射在每兩個(gè)服務(wù)之間的邊上。對于每一個(gè)服務(wù)請求,這個(gè)服務(wù)組合過程將找到一條從服務(wù)入口s到服務(wù)出口t的路徑p。如果該路徑p貫穿所有被選中的服務(wù)組件,并且滿足用戶QoS需求,那么它就將作為組合服務(wù)(或服務(wù)組合方案)返回給用戶。
圖1 感知服務(wù)服務(wù)組合模型
在本文案例中,出行者打車平臺(tái)服務(wù)、網(wǎng)上購票、網(wǎng)上訂餐、酒店預(yù)定四個(gè)任務(wù)粒為云端服務(wù)時(shí),則對應(yīng)的網(wǎng)絡(luò)質(zhì)量就可以設(shè)定為其關(guān)聯(lián)性服務(wù)。
根據(jù)文獻(xiàn)[16]中所建立關(guān)聯(lián)匹配器的過程及建立過程中所需的符號和對應(yīng)的含義給出嚴(yán)格的數(shù)學(xué)定義??紤]到任務(wù)間的關(guān)聯(lián),某些已經(jīng)完成的任務(wù)可能會(huì)影響未執(zhí)行任務(wù)與具體服務(wù)的對應(yīng)關(guān)系。在圖1中,服務(wù)S1、S2、S3、S4為候選服務(wù)中(S1f,S2f,…,Shf)已完成的任務(wù)粒,并且都為一組具體有關(guān)聯(lián)關(guān)系的任務(wù)粒。服務(wù)在選取任務(wù)時(shí),首先需要考慮的是與服務(wù)具有關(guān)聯(lián)關(guān)系的最優(yōu)服務(wù)質(zhì)量的任務(wù)粒。當(dāng)具有關(guān)聯(lián)關(guān)系的服務(wù)無法滿足用戶的需求時(shí),則重新對任務(wù)粒進(jìn)行重選取。關(guān)聯(lián)關(guān)系的重選取算法的步驟如下:
Step1 更新服務(wù)組合模型的參數(shù)。已經(jīng)完成的任務(wù)集為SHf={S1f,S2f,…,Shf},對應(yīng)完成任務(wù)的服務(wù)為E(SHf)={S1f,S2f,…,Shf},然后把Shf和E(Shf)間對應(yīng)關(guān)系的參數(shù)x1,x2,…,xu設(shè)定為1。將集合E(Shf)包含的服務(wù)在實(shí)際執(zhí)行過程中的價(jià)格與響應(yīng)時(shí)間代入服務(wù)組合模型,并把這些服務(wù)在組合模型中對應(yīng)的可靠性設(shè)置為1。
Step2 候選服務(wù)選擇。設(shè)一組關(guān)聯(lián)任務(wù)集為S1f={S11,S12,…,S1f},它對應(yīng)的具有QoS關(guān)聯(lián)關(guān)系的候選服務(wù)集為S2f={S21,S22,…,S2f}。任務(wù)集S1f∈S是一組已經(jīng)完成的任務(wù),對應(yīng)E(Stf)的服務(wù)為E(Stf)={S1f,S2f,…,Stf},然后對于任意一組關(guān)聯(lián)服務(wù),如果滿足條Stf∈E(Stf)則進(jìn)行關(guān)聯(lián)。
Step3 將以上兩步得到結(jié)果用關(guān)聯(lián)性準(zhǔn)則進(jìn)行關(guān)聯(lián),再利用服務(wù)組合模型參數(shù)進(jìn)行判斷,當(dāng)參數(shù)為1時(shí),任務(wù)關(guān)聯(lián);當(dāng)參數(shù)為0時(shí),任務(wù)關(guān)聯(lián)失敗。
在實(shí)際場景可承受的范圍內(nèi),以消耗較少的資源找到近似最優(yōu)解是完全可行的。根據(jù)近似算法[18]理論設(shè)計(jì)一種求解該問題的網(wǎng)絡(luò)服務(wù)組合近似算法是一種非??煽坑行У姆椒?。因此,結(jié)合近似算法思想,本文給出OSP算法,以獲得滿足用戶QoS需求的網(wǎng)絡(luò)服務(wù)組合方案。算法流程圖如圖2所示。
圖2 OSP算法設(shè)計(jì)流程
網(wǎng)絡(luò)感知服務(wù)組合OSP算法的偽代碼如下:
Algorithm OSP
Input:GraphG(V,E,s,t,ω,W,c,C,H,K),Parameterε;
Output:pathp:
1 To each vertexυ∈Sh,pruneυand its connected edges ifcυ 2 To eache∈EinG(V,E),compute the new weights 3 forδk=0 toΔ,2≤k≤Kdo 4dυ[δ2,…,δK]←∞; 5pυ[δ2,…,δK]←NULL,?υ∈V 6ds[δ2,…,δK]←0; 7 end for 8 for all (δ2,…,δK)∈{0,1,…,Δ}K-1in increasing lexicographic order do 10 ifdυ[δ2,…,δK]>du[λ2,…,λK]+ω1(u,υ)then 11dυ[δ2,…,δK]←du[λ2,…,λK]+ω1(u,υ) 12pυ[δ2,…,δK]←u 13 end if 14 ifdυ[δ2,…,δK]>dυ[δ2,…,δj-1,…,δK] then 15dυ[δ2,…,δK]←dυ[δ2,…,δj-1,…,δK]; 16pυ[δ2,…,δK]←pυ[δ2,…,δj-1,…,δK],2≤j≤K; 17 end if 18 end for 19 end for 20 ifdt[δ2,…,δK]≤Dthen 21 Find a source-destination pathps.t.ω1(p)≤Dandωk(p)≤δk,2≤k≤K; 22 end if 23 ifωk(p)≤Wk,2≤k≤Kthen 24 return pathp; 25 end if 26 return No feasible path,EXIT. OSP算法主要由以下四個(gè)具體步驟構(gòu)成: Step1(第1行),根據(jù)節(jié)點(diǎn)約束刪減拓?fù)浣Y(jié)構(gòu)。在服務(wù)網(wǎng)絡(luò)中,cυ Step2(第2行),計(jì)算每條邊的新權(quán)重,設(shè)置參數(shù)Δ。此時(shí),原始服務(wù)網(wǎng)絡(luò)圖就被直接轉(zhuǎn)化成一個(gè)更簡單的圖,達(dá)到方便求解QoS感知的服務(wù)組合問題可行解的目的。 Step3(第3~19行),初始化(K-1)維數(shù)組,運(yùn)行動(dòng)態(tài)規(guī)劃過程,搜索服務(wù)入口節(jié)點(diǎn)s到服務(wù)出口節(jié)點(diǎn)t之間的路徑。 Step3.1 數(shù)組dυ[δ2,…,δK]記錄從源節(jié)點(diǎn)s到任一中間節(jié)點(diǎn)υ的路徑p第一維參數(shù)最小權(quán)重(ω1)。此外,該路徑p滿足ωk(p)≤δk,2≤k≤K。 Step3.2 數(shù)組pυ[δ2,…,δK]記錄路徑p上節(jié)點(diǎn)υ的前驅(qū)節(jié)點(diǎn)。該路徑p滿足ω1(p)=dυ[δ2,…,δK],且ωk(p)≤δk,2≤k≤K。 Step3.3(第10~13行),當(dāng)u-υ為圖中一條邊時(shí),則從節(jié)點(diǎn)s到節(jié)點(diǎn)υ的第一維最小權(quán)重路徑p一定經(jīng)過某些中間節(jié)點(diǎn)u,因此本文所提出的OSP算法通過搜索所有可能中間節(jié)點(diǎn)u與節(jié)點(diǎn)υ之間的邊來獲得最小的第一維路徑權(quán)重dυ[δ2,…,δK]。 Step3.4(第14~17行),如果當(dāng)前記錄的第一維路徑權(quán)重dυ[δ2,…,δK]大于之前的記錄值dυ[δ2,…,δj-1,…,δK],則繼承以前第一維最小路徑權(quán)重,即dυ[δ2,…,δK]←dυ[δ2,…,δj-1,…,δK]。這一思路來源于文獻(xiàn)[9]中ADAPT算法的思路,可以獲得更優(yōu)的可行解。對于文獻(xiàn)[10]中PseudoMCPP算法未能考慮該情形,搜索的最優(yōu)路徑p滿足ω1(p)≤D且ωk(p)≤c,2≤k≤K,其中c為正整數(shù),c≤C。結(jié)合文獻(xiàn)[9-10]的ADAPT算法和PseudoMCPP算法的優(yōu)點(diǎn),OSP算法利用路徑跳數(shù)構(gòu)建搜索空間,在搜索最優(yōu)解的過程中不斷地繼承已知結(jié)果,最終獲得的最優(yōu)路徑p滿足ω1(p)≤D,且ωk(p)≤δk,2≤k≤K,其中δk≤c。因此,對比ADAPT算法和PseudoMCPP算法,本文所提出的OSP算法具有更好的性能,能夠快速有效地獲得滿足用戶需求的網(wǎng)絡(luò)服務(wù)組合方案。 Step4(第20~26行),查找Step 3計(jì)算結(jié)果所獲得的路徑是否可行,是否滿足用戶所提約束條件。如果路徑P滿足ωk(p)≤Wk,2≤k≤K,則算法返回可行路徑p;否則返回?zé)o可行路徑提示,程序終止。 證畢。 證明:對于最優(yōu)路徑popt,有ωk(popt)≤ηopt·Wk,2≤k≤K,即 (9) (10) 由dυ[δ2,…,δK]的定義和動(dòng)態(tài)規(guī)劃的過程可知, (11) 因此可得 (12) (13) 因?yàn)槁窂絧有H-1跳,因此 (14) 即 ωk(p)≤(1+ρ)·η·Wk。 (15) 證畢。 仿真采用兩組有向無環(huán)圖作為數(shù)據(jù)集。 第一組數(shù)據(jù)集包括10個(gè)有向無環(huán)服務(wù)網(wǎng)絡(luò),服務(wù)數(shù)規(guī)模為100~1 000,其中每個(gè)服務(wù)網(wǎng)絡(luò)有3個(gè)服務(wù)類(H=3),服務(wù)數(shù)之間的每條有向邊有兩個(gè)QoS參數(shù),即K=2。第一個(gè)QoS參數(shù)在(2,10)范圍內(nèi)隨機(jī)取值,第二個(gè)QoS參數(shù)在(10-8,10-5)范圍內(nèi)隨機(jī)取值。 第二組數(shù)據(jù)集包括5個(gè)有向無環(huán)服務(wù)網(wǎng)絡(luò),服務(wù)數(shù)規(guī)模為20~100,其中每個(gè)服務(wù)網(wǎng)絡(luò)也有3個(gè)服務(wù)類(H=3),服務(wù)數(shù)之間的每條有向邊有三個(gè)QoS參數(shù),即K=3。第一個(gè)QoS參數(shù)在(2,10)范圍內(nèi)隨機(jī)取值,第二個(gè)QoS參數(shù)在(10-8,10-5)范圍內(nèi)隨機(jī)取值,第三個(gè)QoS參數(shù)在(0,0.01)范圍內(nèi)隨機(jī)取值。 為了評價(jià)OSP的性能有效性,本文采用平均執(zhí)行時(shí)間(Average Execution Time,AET)和路徑權(quán)重距離(Path Weight Distance,PWD)兩個(gè)評價(jià)指標(biāo)來反映算法求解時(shí)間和求解質(zhì)量,以達(dá)到測試算法綜合性能的目的。 AET主要是用來評估算法在網(wǎng)絡(luò)延時(shí)方面的指標(biāo),當(dāng)網(wǎng)絡(luò)用戶花費(fèi)的組合路徑所需延時(shí)越小,則求解時(shí)間的性能越好。PWD主要是用來評估不同運(yùn)行代數(shù)下所得到的服務(wù)組合路徑權(quán)重與網(wǎng)絡(luò)用戶路徑約束之間的距離,則有 (16) 對于終端用戶來講,這個(gè)評價(jià)指標(biāo)反映了算法所獲得服務(wù)組合路徑的QoS保障水平。顯然,PWD值越大,算法所獲得服務(wù)組合路徑的質(zhì)量越好。 根據(jù)前面的分析,本文將近似度參數(shù)ε引入OSP算法中。測試中將分別設(shè)定不同的ε值來分析其對QoS的影響,ε取值分別為0.01、0.02、0.03。對于用戶端到端QoS請求,假設(shè)W1=50,W2∈[2.5×10-5,5×10-5],以保證算法可以在所有服務(wù)網(wǎng)絡(luò)中找到一條可行的服務(wù)組合。分別在ε不同取值條件下,將算法運(yùn)行1 000次迭代,取20次運(yùn)行結(jié)果的并集,將得到服務(wù)組合路徑的平均時(shí)間值。圖3給出了OSP算法在服務(wù)數(shù)規(guī)模為[100,1 000]時(shí)獲得滿足用戶需求的服務(wù)組合路徑所需平均執(zhí)行時(shí)間。當(dāng)服務(wù)數(shù)規(guī)模增加時(shí),AET值增加,即在更大規(guī)模服務(wù)網(wǎng)絡(luò)中需要花費(fèi)更多時(shí)間來尋找相同路徑的趨勢。隨著參數(shù)ε值的減少,搜索路徑的時(shí)間花費(fèi)AET值增大。這主要是由于算法參數(shù)ε取值越小,路徑搜索空間越大。因此,參數(shù)ε反映的是算法的近似度。ε取值越小,近似度越高,算法的搜索空間就越大,顯然算法就需要花費(fèi)更多的時(shí)間查找滿足用戶需求的服務(wù)組合路徑。 圖3 不同服務(wù)數(shù)AET值 圖4顯示了隨著ε取值的不同,算法的AET值變化趨勢。對于一個(gè)給定的ε取值[0.01,0.03],在服務(wù)數(shù)[100,1 000]的范圍內(nèi),OSP算法的搜索空間依賴于服務(wù)組合路徑的跳數(shù),其路徑跳數(shù)值小并且可以預(yù)先獲得,容易快速有效地構(gòu)建搜索空間。OSP算法能較快找到服務(wù)組合路徑,算法的平均執(zhí)行時(shí)間AET值較小,尤其是在更大的服務(wù)數(shù)下表現(xiàn)較為突出。 圖4 ε取值[0.01,0.03]下OSP算法的AET值 圖5(a)為在服務(wù)數(shù)為500和1 000、不同ε取值的情況下AET的值。從圖中可以看出,不同的ε取值,OSP算法可以較快地滿足用戶QoS需求的服務(wù)組合路徑。此外,隨著算法ε取值的增大,OSF算法也表現(xiàn)出更加穩(wěn)定的AET性能。也就是說,當(dāng)滿足用戶需求的服務(wù)組合路徑存在于搜索空間中的某一特定位置時(shí),AET值較為穩(wěn)定。這是因?yàn)椋琌SP算法在服務(wù)組合路徑跳數(shù)構(gòu)建搜索空間,參數(shù)ε起著微調(diào)該搜索空間的作用。圖5(b)為在服務(wù)數(shù)為500和1 000、不同約束值(W2)取值的情況下AET的值。實(shí)驗(yàn)結(jié)果表明,在不同約束情況下,OSP算法的AET值并不受用戶約束的影響,隨著用戶約束值變大,算法中的AET值趨勢穩(wěn)定,始終保持在一個(gè)穩(wěn)定的狀態(tài)。 (a)不同ε值下的AET取值 圖6給出了OSP算法在不同約束值(W2)情況下的PWD值。隨著用戶約束逐步放松,OSP算法搜索的路徑距離將減小,即PWD值減小。也就是說,如果用戶需求寬松,OSP算法將找到質(zhì)量更粗糙的路徑,只需滿足用戶的要求即可。由此可知,當(dāng)服務(wù)數(shù)增大時(shí),OSP算法可以找到更好質(zhì)量的服務(wù)組合路徑。 圖6 服務(wù)數(shù)為500和1 000的W2的PWD值 圖7給出了OSP算法在不同網(wǎng)絡(luò)服務(wù)數(shù)下PWD值。從圖中可以看出,隨著網(wǎng)絡(luò)服務(wù)數(shù)的增加,OSP算法可以找到更好質(zhì)量的服務(wù)組合路徑。這是因?yàn)樵谀骋粋€(gè)更大規(guī)模的服務(wù)網(wǎng)絡(luò)中有著更優(yōu)的服務(wù)組合選擇路徑。這表明OSP算法可以根據(jù)用戶需求,在不同服務(wù)網(wǎng)絡(luò)數(shù)下穩(wěn)定、可靠地找到滿足端對端的QoS約束服務(wù)組合路徑。 圖7 不同服務(wù)數(shù)PWD值 由于云計(jì)算所持有的服務(wù)形態(tài)、服務(wù)模式和服務(wù)規(guī)模,以及云服務(wù)和網(wǎng)絡(luò)服務(wù)的QoS參數(shù)特性,ADAPT算法優(yōu)勢在于在搜索最優(yōu)解的過程中繼承已知結(jié)果。為了證驗(yàn)ADAPT和OSP兩種算法的性能,我們將文獻(xiàn)[9]的ADAPT算法與OSP算法進(jìn)行對比。圖8(a)給出了兩個(gè)算法在不同網(wǎng)絡(luò)服務(wù)數(shù)、相用ε取值下的AET對比值。測試結(jié)果表明,對于一個(gè)給定的ε取值,OSP算法可以更快地找到與運(yùn)行ADAPT算法一樣的服務(wù)組合路徑,即OSP算法的AET值更小。隨著服務(wù)數(shù)的增大,它的優(yōu)勢更為明顯。而ADAPT算法采用的算法由于逐步壓縮路徑上下界,過程較為緩慢,并且其最終所構(gòu)建的搜索空間大于依靠跳數(shù)構(gòu)建的搜索空間。因此,與ADAPT算法對比,OSP算法的AET性能方面優(yōu)勢更為明顯。 圖8(b)、8(c)分別給出了兩個(gè)算法在相同服務(wù)數(shù)(500和1 000)、不同ε取值下和不同約束值W2時(shí)的AET對比值。對于不同的ε和W2取值,OSP算法均優(yōu)于ADAPT算法,即可更快找到滿足用戶QoS需求的服務(wù)組合路徑。隨著算法參數(shù)ε取值的增大,OSP算法的AET值較為平穩(wěn),而ADAPT算法的AET值逐漸變小。這說明,當(dāng)滿足用戶需求的服務(wù)組合路徑存在于搜索空間中的某一特定位置時(shí),ADAPT算法對參數(shù)ε取值敏感,并受W2約束,而OSP算法穩(wěn)定性強(qiáng)。 (a)不同服務(wù)數(shù)下的AET對比值 本文針對網(wǎng)絡(luò)服務(wù)組合的特點(diǎn)和用戶個(gè)性化的QOS需求,分析和定義了多融合網(wǎng)絡(luò)場景下的網(wǎng)絡(luò)感知服務(wù)組合模型,提出了一種基于最優(yōu)路徑選擇的服務(wù)組合算法,大大提升了網(wǎng)絡(luò)服務(wù)質(zhì)量。實(shí)驗(yàn)結(jié)果表明,該算法在求解時(shí)間和質(zhì)量兩個(gè)方面都表現(xiàn)出了良好的性能,而且能動(dòng)態(tài)適應(yīng)用戶復(fù)雜的需求。同時(shí),OSP算法優(yōu)于ADAPT算法。在實(shí)際應(yīng)用中,許多APP服營商(比如掌上高鐵、微信等)在對相關(guān)服務(wù)進(jìn)行整合關(guān)聯(lián)時(shí),會(huì)對相關(guān)應(yīng)用程序進(jìn)行接口對接,以達(dá)到服務(wù)的快速關(guān)聯(lián),可大大提升QoS的效益。隨著技術(shù)的不斷推進(jìn),相信本方法將滿足云環(huán)境下QoS關(guān)聯(lián)的服務(wù)組合要求。2.2 算法分析
3 仿真測試與分析
3.1 測試準(zhǔn)備
3.2 測試指標(biāo)
3.3 測試結(jié)果
3.4 與ADAPT的對比
4 結(jié) 論