亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        基于最優(yōu)路徑選擇的網(wǎng)絡(luò)感知服務(wù)組合算法*

        2022-05-26 08:17:46林志興余高鋒肖香梅劉孫發(fā)
        電訊技術(shù) 2022年5期
        關(guān)鍵詞:滿足用戶網(wǎng)絡(luò)服務(wù)關(guān)聯(lián)

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

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

        0 引 言

        隨著云計(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ù)組合方案。

        1 相關(guān)工作

        1.1 QoS感知服務(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ù)組合方案。

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

        服務(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)

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

        一個(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ù)組合模型

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

        在本文案例中,出行者打車平臺(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)失敗。

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

        2.1 算法設(shè)計(jì)

        在實(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可行路徑提示,程序終止。

        2.2 算法分析

        證畢。

        證明:對于最優(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)

        證畢。

        3 仿真測試與分析

        3.1 測試準(zhǔn)備

        仿真采用兩組有向無環(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ī)取值。

        3.2 測試指標(biāo)

        為了評價(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ì)量越好。

        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ù)組合路徑的平均時(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值

        3.4 與ADAPT的對比

        由于云計(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對比值

        4 結(jié) 論

        本文針對網(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ù)組合要求。

        猜你喜歡
        滿足用戶網(wǎng)絡(luò)服務(wù)關(guān)聯(lián)
        《壓縮機(jī)技術(shù)》網(wǎng)絡(luò)服務(wù)
        《壓縮機(jī)技術(shù)》網(wǎng)絡(luò)服務(wù)
        網(wǎng)絡(luò)服務(wù)合同的法律問題研究
        法制博覽(2021年18期)2021-11-24 20:45:30
        長城火炮
        汽車觀察(2021年11期)2021-04-24 22:04:12
        “一帶一路”遞進(jìn),關(guān)聯(lián)民生更緊
        快圖瀏覽
        奇趣搭配
        智趣
        讀者(2017年5期)2017-02-15 18:04:18
        云計(jì)算趨勢下的藍(lán)汛內(nèi)容感知網(wǎng)絡(luò)服務(wù)
        中國重汽干攪拌輕量化攪拌車成功研發(fā)
        專用汽車(2012年5期)2012-12-18 11:20:59
        久久aⅴ无码一区二区三区| 无码国产成人午夜电影在线观看| 欧美人与禽2o2o性论交| 在线播放无码高潮的视频| 国产亚洲精品福利在线| 日本高清色一区二区三区| 亚洲一区二区在线观看网址| 消息称老熟妇乱视频一区二区| 日韩毛片在线| 日本一区二区三区资源视频| 国产精品精品国产色婷婷| 中文字幕av一区二区三区人妻少妇 | 亚洲一区二区三区18| 久久亚洲av成人无码电影| 8av国产精品爽爽ⅴa在线观看| 国产国拍亚洲精品永久不卡| 少妇特殊按摩高潮对白| 精品午夜福利在线观看| 少妇无码一区二区三区| 无码av一区在线观看| 中文字幕日韩精品永久在线| 四虎成人精品国产永久免费无码 | 无遮无挡三级动态图| 亚洲啊啊啊一区二区三区 | 又粗又黑又大的吊av| 国产在线无码一区二区三区| 香蕉久久夜色精品国产| 亚洲av老熟女一区二区三区| 亚洲精品久久久久中文字幕| 亚洲视频天堂| 亚洲男人在线天堂av| 一本色道久久hezyo无码 | 欧美亚洲高清日韩成人| 亚洲中文字幕乱码在线视频| 人妻少妇被粗大爽.9797pw| 最新国产av无码专区亚洲| 久久久久久国产福利网站| 中文字幕日韩有码国产| 久久99精品国产麻豆不卡| 动漫在线无码一区| 日本女优免费一区二区三区|