余 建，林志興，余高鋒，肖香梅，劉孫發(fā)

(1.三明學(xué)院 a.網(wǎng)絡(luò)中心;b.信息工程學(xué)院，福建 三明365004;2.物聯(lián)網(wǎng)應(yīng)用福建省高校工程研究中心，福建 三明365004)

0 引 言

隨著云計算[1]、物聯(lián)網(wǎng)[2]、移動互聯(lián)網(wǎng)[3]、大數(shù)據(jù)[4]等現(xiàn)代信息技術(shù)的不斷發(fā)展，用戶(特別是手機(jī)用戶)需求日益增多,單一的服務(wù)已經(jīng)無法滿足,而服務(wù)組合技術(shù)可將現(xiàn)有的分布式的服務(wù)集成為滿足用戶需求的組合服務(wù)[5]。在個性化需求不斷擴(kuò)大的背景下，隨著大量的手機(jī)APP軟件的推出，如何將不同的服務(wù)進(jìn)行組合而又能保障全局網(wǎng)絡(luò)的服務(wù)質(zhì)量(Quality of Service,QoS)，已成為當(dāng)前亟待解決的問題。同時考慮云服務(wù)和網(wǎng)絡(luò)服務(wù)的QoS屬性，解決一體化環(huán)境下服務(wù)組合問題，給出最優(yōu)的服務(wù)組合算法，為不同需求的用戶提供點到點服務(wù)質(zhì)量保障，具有重要的理論價值和廣闊的應(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)境中,引入社會關(guān)系理論，在線上服務(wù)組合階段考慮提高線下服務(wù)提供商之間的協(xié)作效率,同時優(yōu)化算法的執(zhí)行效率。蔡江安等[8]等針對服務(wù)組合問題，利用服務(wù)組合策略，建立了以時間、實用性、創(chuàng)新性、可靠性等為優(yōu)化目標(biāo)的服務(wù)組合優(yōu)化模型；同時通過聚類算法以及對組合服務(wù)的關(guān)聯(lián)規(guī)則對路徑搜索空間進(jìn)行預(yù)處理，大大提高了搜索空間的效率，讓知識服務(wù)資源能在服務(wù)組合中以較短的時間內(nèi)進(jìn)行精準(zhǔn)定位并與之匹配，較大程度上提高服務(wù)組合的性能。

Ergun等人[9]針對雙度量QoS選路問題提出了一種性能出色的近似算法，通過選取最優(yōu)的一個上、下界，引入一個多項式時間的近似測試過程，去不斷地縮小上下界之間的距離，把路徑搜索問題轉(zhuǎn)化成區(qū)間搜索問題，在不斷縮小的范圍內(nèi)快速查找最優(yōu)解。Xue等人[10]提出了一種PeseudoMCPP算法，給出了一種利用路徑跳數(shù)構(gòu)建路徑搜索空間，可以獲得在滿足第一維路徑權(quán)重約束D的情況下，其他維路徑權(quán)重也都滿足于某個約束C。由于Ergun等人提出的算法非常耗時，而Xue等人的算法不能繼承已知的結(jié)果，因而都難以獲得質(zhì)量更好的求解方案。本文在綜合考慮網(wǎng)絡(luò)服務(wù)特點的基礎(chǔ)上，結(jié)合以上兩種算法思路，給出了一種服務(wù)最優(yōu)路徑選擇算法(Optimal Path Selection，OPS)，以解決QoS感知的網(wǎng)絡(luò)服務(wù)組合問題，提升網(wǎng)絡(luò)服務(wù)質(zhì)量水平，改善用戶體驗質(zhì)量。

在某商務(wù)出行案例中，如果每一個服務(wù)類表示為{(S1,S2,S3,…,St)}，按照組合服務(wù)對應(yīng)的主體，我們可分為4個服務(wù)實例，即打車平臺服務(wù)、網(wǎng)上購票、網(wǎng)上訂餐、酒店預(yù)定，任務(wù)粒(抽象服務(wù))表示為{(S1,S2,S3,S4)}。若假設(shè)每個任務(wù)都有相關(guān)候選服務(wù)可以實現(xiàn)其所在服務(wù)類的功能，但是它們有不同的服務(wù)質(zhì)量，因此，人們會根據(jù)候選服務(wù)的服務(wù)質(zhì)量選擇最優(yōu)的服務(wù)組合方案。

1 相關(guān)工作

1.1 QoS感知服務(wù)組合定義

服務(wù)組合能充分利用目前已有的服務(wù)，具有即時、快速和靈活組建分布式松耦合的優(yōu)勢[11]。當(dāng)網(wǎng)絡(luò)用戶向服務(wù)器端請求服務(wù)時，服務(wù)器端將調(diào)用服務(wù)組合過程，選擇一系列原子服務(wù)組件來構(gòu)建功能復(fù)雜的組合服務(wù)，以滿足網(wǎng)絡(luò)用戶個性化的需求。本文中的服務(wù)組合路徑包括多個單個服務(wù)進(jìn)行組合[12]，即組合服務(wù)(也稱多目標(biāo)服務(wù)組合、多任務(wù)組合服務(wù)或綜合性服務(wù))。

定義1 可行的服務(wù)組合方案。每個服務(wù)Si(1≤i≤H)，每個服務(wù)對應(yīng)一個原子服務(wù)組件SH，假設(shè)一個服務(wù)組合方案，如在某服務(wù)網(wǎng)絡(luò)中的一條路徑p，cv和Ch代表節(jié)點v和h的服務(wù)能力，ωk為其路徑的最小權(quán)重，Wk代表約束條件，K為任務(wù)S執(zhí)行的任務(wù)次數(shù)，如果對于?v∈p有cv≥Ch，節(jié)點不和ωk(p)≤Wk，其中υ∈Sh，1≤h≤H，1≤k≤K，那么路徑p是一個可行的服務(wù)組合方案。

1.2 服務(wù)組合結(jié)構(gòu)轉(zhuǎn)化

服務(wù)組合流程包括串行、選擇、并行等結(jié)構(gòu)，這些基本結(jié)構(gòu)可以構(gòu)造出很多結(jié)構(gòu)不同的復(fù)雜服務(wù)組合流程。在基于功能方面的需求為請求中的每一個功能選擇服務(wù)之后，服務(wù)目錄根據(jù)用戶的QoS要求，在大量候選的服務(wù)組合路徑流程中選出滿足用戶要求的最優(yōu)組合路徑。

當(dāng)用戶在每一個任務(wù)粒中選對一個候選服務(wù)時，根據(jù)網(wǎng)絡(luò)服務(wù)中最優(yōu)組合路徑選擇原則，云服務(wù)器應(yīng)在最短時間內(nèi)響應(yīng)用戶需求。由于每個候選服務(wù)組合路徑包含多種拓?fù)浣Y(jié)構(gòu)，現(xiàn)有的大多數(shù)服務(wù)選擇算法無法直接處理多種結(jié)構(gòu)，因此在服務(wù)選擇之前需要對拓?fù)溥M(jìn)行結(jié)構(gòu)轉(zhuǎn)換[13]，在這個轉(zhuǎn)化過程中Sa和Sb保持不變。執(zhí)行完Sa之后，就分別以p1,p2,…,pn概率執(zhí)行服務(wù)S1,S2,…,Sn，然后再執(zhí)行Sb。ti、ci、ri、thi分別代表的響應(yīng)時間、代價、可靠性和吞吐量，F(xiàn)i(x)代表概率響應(yīng)時間t的概率密度函數(shù),Pi1(x)代表代價c的密度函數(shù)，Pi2(x)代表可靠性r的密度函數(shù)，Pi3(x)代表吞吐量th′的密度函數(shù)，P代表順序結(jié)構(gòu)轉(zhuǎn)換后的服務(wù)S1n的值，計算如下：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

1.3 QoS感知服務(wù)組合模型

一個服務(wù)組合的流程是[14]：用戶先提出自已的業(yè)務(wù)需求，服務(wù)組合根據(jù)用戶的需求設(shè)計一個抽象服務(wù)模型，然后在每一個抽象服務(wù)所對應(yīng)的候選服務(wù)集合中選擇一個服務(wù)與之相對應(yīng)，并把最后所形成的關(guān)聯(lián)服務(wù)也即組合服務(wù)反饋給用戶，該組合一定是滿足用戶約束且QoS最優(yōu)的。組合服務(wù)是一個組合服務(wù)集合，其所包含的組合服務(wù)不被其他組合服務(wù)支配，它通常被用來提高組合服務(wù)選擇的效率。

為了找到更優(yōu)的服務(wù)組合路徑，我們建立了QoS感知服務(wù)組合模型。在服務(wù)組合模型中，單一服務(wù)通常無法滿足用戶需求，而需要將多種服務(wù)按照順序組成一條工作流來完成用戶請求。在組合服務(wù)選擇過程中，某個服務(wù)通常有多個候選服務(wù)[15]提供商。在組合服務(wù)集合中，通過不同任務(wù)中的候選服務(wù)之間存在關(guān)聯(lián)性，再通過OSP算法建立最優(yōu)路徑選擇，從而找到一條花費(fèi)較小的服務(wù)組合路徑。如圖1所示，每個服務(wù)Si(1≤i≤H)中有許多原子服務(wù)組件Sij(1≤i≤H，1≤f≤F)作為服務(wù)組合的候選組件。該感知服務(wù)組合模型將網(wǎng)絡(luò)服務(wù)和云服務(wù)的QoS參數(shù)一并映射在每兩個服務(wù)之間的邊上。對于每一個服務(wù)請求，這個服務(wù)組合過程將找到一條從服務(wù)入口s到服務(wù)出口t的路徑p。如果該路徑p貫穿所有被選中的服務(wù)組件，并且滿足用戶QoS需求，那么它就將作為組合服務(wù)(或服務(wù)組合方案)返回給用戶。

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

1.4 組合服務(wù)關(guān)聯(lián)

在本文案例中，出行者打車平臺服務(wù)、網(wǎng)上購票、網(wǎng)上訂餐、酒店預(yù)定四個任務(wù)粒為云端服務(wù)時，則對應(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ù)可能會影響未執(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ù)時，首先需要考慮的是與服務(wù)具有關(guān)聯(lián)關(guān)系的最優(yōu)服務(wù)質(zhì)量的任務(wù)粒。當(dāng)具有關(guān)聯(lián)關(guān)系的服務(wù)無法滿足用戶的需求時，則重新對任務(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ù)在實際執(zhí)行過程中的價格與響應(yīng)時間代入服務(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時，任務(wù)關(guān)聯(lián)；當(dāng)參數(shù)為0時，任務(wù)關(guān)聯(lián)失敗。

2 基于QoS感知的服務(wù)組合算法

2.1 算法設(shè)計

在實際場景可承受的范圍內(nèi)，以消耗較少的資源找到近似最優(yōu)解是完全可行的。根據(jù)近似算法[18]理論設(shè)計一種求解該問題的網(wǎng)絡(luò)服務(wù)組合近似算法是一種非?？煽坑行У姆椒?。因此，結(jié)合近似算法思想，本文給出OSP算法，以獲得滿足用戶QoS需求的網(wǎng)絡(luò)服務(wù)組合方案。算法流程圖如圖2所示。

圖2 OSP算法設(shè)計流程

網(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òu)成：

Step1(第1行)，根據(jù)節(jié)點約束刪減拓?fù)浣Y(jié)構(gòu)。在服務(wù)網(wǎng)絡(luò)中，cυ

Step2(第2行)，計算每條邊的新權(quán)重，設(shè)置參數(shù)Δ。此時，原始服務(wù)網(wǎng)絡(luò)圖就被直接轉(zhuǎn)化成一個更簡單的圖，達(dá)到方便求解QoS感知的服務(wù)組合問題可行解的目的。

Step3(第3～19行)，初始化(K-1)維數(shù)組，運(yùn)行動態(tài)規(guī)劃過程，搜索服務(wù)入口節(jié)點s到服務(wù)出口節(jié)點t之間的路徑。

Step3.1 數(shù)組dυ[δ2,…,δK]記錄從源節(jié)點s到任一中間節(jié)點υ的路徑p第一維參數(shù)最小權(quán)重(ω1)。此外，該路徑p滿足ωk(p)≤δk，2≤k≤K。

Step3.2 數(shù)組pυ[δ2,…,δK]記錄路徑p上節(jié)點υ的前驅(qū)節(jié)點。該路徑p滿足ω1(p)=dυ[δ2,…,δK]，且ωk(p)≤δk，2≤k≤K。

Step3.3(第10～13行)，當(dāng)u-υ為圖中一條邊時，則從節(jié)點s到節(jié)點υ的第一維最小權(quán)重路徑p一定經(jīng)過某些中間節(jié)點u，因此本文所提出的OSP算法通過搜索所有可能中間節(jié)點u與節(jié)點υ之間的邊來獲得最小的第一維路徑權(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)點，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計算結(jié)果所獲得的路徑是否可行，是否滿足用戶所提約束條件。如果路徑P滿足ωk(p)≤Wk，2≤k≤K，則算法返回可行路徑p；否則返回?zé)o可行路徑提示，程序終止。

2.2 算法分析

證畢。

證明：對于最優(yōu)路徑popt，有ωk(popt)≤ηopt·Wk，2≤k≤K，即

(9)

(10)

由dυ[δ2,…,δK]的定義和動態(tài)規(guī)劃的過程可知，

(11)

因此可得

(12)

(13)

因為路徑p有H-1跳，因此

(14)

即

ωk(p)≤(1+ρ)·η·Wk。

(15)

證畢。

3 仿真測試與分析

3.1 測試準(zhǔn)備

仿真采用兩組有向無環(huán)圖作為數(shù)據(jù)集。

第一組數(shù)據(jù)集包括10個有向無環(huán)服務(wù)網(wǎng)絡(luò)，服務(wù)數(shù)規(guī)模為100～1 000，其中每個服務(wù)網(wǎng)絡(luò)有3個服務(wù)類(H=3)，服務(wù)數(shù)之間的每條有向邊有兩個QoS參數(shù)，即K=2。第一個QoS參數(shù)在(2，10)范圍內(nèi)隨機(jī)取值，第二個QoS參數(shù)在(10-8，10-5)范圍內(nèi)隨機(jī)取值。

第二組數(shù)據(jù)集包括5個有向無環(huán)服務(wù)網(wǎng)絡(luò)，服務(wù)數(shù)規(guī)模為20～100，其中每個服務(wù)網(wǎng)絡(luò)也有3個服務(wù)類(H=3)，服務(wù)數(shù)之間的每條有向邊有三個QoS參數(shù)，即K=3。第一個QoS參數(shù)在(2，10)范圍內(nèi)隨機(jī)取值，第二個QoS參數(shù)在(10-8，10-5)范圍內(nèi)隨機(jī)取值，第三個QoS參數(shù)在(0，0.01)范圍內(nèi)隨機(jī)取值。

3.2 測試指標(biāo)

為了評價OSP的性能有效性，本文采用平均執(zhí)行時間(Average Execution Time，AET)和路徑權(quán)重距離(Path Weight Distance，PWD)兩個評價指標(biāo)來反映算法求解時間和求解質(zhì)量，以達(dá)到測試算法綜合性能的目的。

AET主要是用來評估算法在網(wǎng)絡(luò)延時方面的指標(biāo)，當(dāng)網(wǎng)絡(luò)用戶花費(fèi)的組合路徑所需延時越小，則求解時間的性能越好。PWD主要是用來評估不同運(yùn)行代數(shù)下所得到的服務(wù)組合路徑權(quán)重與網(wǎng)絡(luò)用戶路徑約束之間的距離，則有

(16)

對于終端用戶來講，這個評價指標(biāo)反映了算法所獲得服務(wù)組合路徑的QoS保障水平。顯然，PWD值越大，算法所獲得服務(wù)組合路徑的質(zhì)量越好。

3.3 測試結(jié)果

根據(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ù)組合路徑的平均時間值。圖3給出了OSP算法在服務(wù)數(shù)規(guī)模為[100，1 000]時獲得滿足用戶需求的服務(wù)組合路徑所需平均執(zhí)行時間。當(dāng)服務(wù)數(shù)規(guī)模增加時，AET值增加，即在更大規(guī)模服務(wù)網(wǎng)絡(luò)中需要花費(fèi)更多時間來尋找相同路徑的趨勢。隨著參數(shù)ε值的減少，搜索路徑的時間花費(fèi)AET值增大。這主要是由于算法參數(shù)ε取值越小，路徑搜索空間越大。因此，參數(shù)ε反映的是算法的近似度。ε取值越小，近似度越高，算法的搜索空間就越大，顯然算法就需要花費(fèi)更多的時間查找滿足用戶需求的服務(wù)組合路徑。

圖3 不同服務(wù)數(shù)AET值

圖4顯示了隨著ε取值的不同，算法的AET值變化趨勢。對于一個給定的ε取值[0.01，0.03]，在服務(wù)數(shù)[100,1 000]的范圍內(nèi)，OSP算法的搜索空間依賴于服務(wù)組合路徑的跳數(shù)，其路徑跳數(shù)值小并且可以預(yù)先獲得，容易快速有效地構(gòu)建搜索空間。OSP算法能較快找到服務(wù)組合路徑，算法的平均執(zhí)行時間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ù)組合路徑存在于搜索空間中的某一特定位置時，AET值較為穩(wěn)定。這是因為，OSP算法在服務(wù)組合路徑跳數(shù)構(gòu)建搜索空間，參數(shù)ε起著微調(diào)該搜索空間的作用。圖5(b)為在服務(wù)數(shù)為500和1 000、不同約束值(W2)取值的情況下AET的值。實驗結(jié)果表明，在不同約束情況下，OSP算法的AET值并不受用戶約束的影響，隨著用戶約束值變大，算法中的AET值趨勢穩(wěn)定，始終保持在一個穩(wěn)定的狀態(tài)。

(a)不同ε值下的AET取值

圖6給出了OSP算法在不同約束值(W2)情況下的PWD值。隨著用戶約束逐步放松，OSP算法搜索的路徑距離將減小，即PWD值減小。也就是說，如果用戶需求寬松，OSP算法將找到質(zhì)量更粗糙的路徑，只需滿足用戶的要求即可。由此可知，當(dāng)服務(wù)數(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ù)組合路徑。這是因為在某一個更大規(guī)模的服務(wù)網(wǎng)絡(luò)中有著更優(yōu)的服務(wù)組合選擇路徑。這表明OSP算法可以根據(jù)用戶需求，在不同服務(wù)網(wǎng)絡(luò)數(shù)下穩(wěn)定、可靠地找到滿足端對端的QoS約束服務(wù)組合路徑。

圖7 不同服務(wù)數(shù)PWD值

3.4 與ADAPT的對比

由于云計算所持有的服務(wù)形態(tài)、服務(wù)模式和服務(wù)規(guī)模，以及云服務(wù)和網(wǎng)絡(luò)服務(wù)的QoS參數(shù)特性，ADAPT算法優(yōu)勢在于在搜索最優(yōu)解的過程中繼承已知結(jié)果。為了證驗ADAPT和OSP兩種算法的性能，我們將文獻(xiàn)[9]的ADAPT算法與OSP算法進(jìn)行對比。圖8(a)給出了兩個算法在不同網(wǎng)絡(luò)服務(wù)數(shù)、相用ε取值下的AET對比值。測試結(jié)果表明，對于一個給定的ε取值，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)分別給出了兩個算法在相同服務(wù)數(shù)(500和1 000)、不同ε取值下和不同約束值W2時的AET對比值。對于不同的ε和W2取值，OSP算法均優(yōu)于ADAPT算法，即可更快找到滿足用戶QoS需求的服務(wù)組合路徑。隨著算法參數(shù)ε取值的增大，OSP算法的AET值較為平穩(wěn)，而ADAPT算法的AET值逐漸變小。這說明，當(dāng)滿足用戶需求的服務(wù)組合路徑存在于搜索空間中的某一特定位置時，ADAPT算法對參數(shù)ε取值敏感，并受W2約束，而OSP算法穩(wěn)定性強(qiáng)。

(a)不同服務(wù)數(shù)下的AET對比值

4 結(jié) 論

本文針對網(wǎng)絡(luò)服務(wù)組合的特點和用戶個性化的QOS需求，分析和定義了多融合網(wǎng)絡(luò)場景下的網(wǎng)絡(luò)感知服務(wù)組合模型，提出了一種基于最優(yōu)路徑選擇的服務(wù)組合算法，大大提升了網(wǎng)絡(luò)服務(wù)質(zhì)量。實驗結(jié)果表明，該算法在求解時間和質(zhì)量兩個方面都表現(xiàn)出了良好的性能，而且能動態(tài)適應(yīng)用戶復(fù)雜的需求。同時，OSP算法優(yōu)于ADAPT算法。在實際應(yīng)用中，許多APP服營商(比如掌上高鐵、微信等)在對相關(guān)服務(wù)進(jìn)行整合關(guān)聯(lián)時，會對相關(guān)應(yīng)用程序進(jìn)行接口對接，以達(dá)到服務(wù)的快速關(guān)聯(lián)，可大大提升QoS的效益。隨著技術(shù)的不斷推進(jìn)，相信本方法將滿足云環(huán)境下QoS關(guān)聯(lián)的服務(wù)組合要求。