基于skyline全局qos約束下web服務(wù)選擇

《基于skyline全局qos約束下web服務(wù)選擇》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、基于skyline全局QoS約束下web服務(wù)選擇摘要隨著web2.0的普及，大量web服務(wù)被提出及應(yīng)用到開放式服務(wù)系統(tǒng)中，服務(wù)組合能滿足用戶不斷變化的需求，但是在組合服務(wù)中需要用盡可能短的時(shí)間從大量備選服務(wù)中選擇以滿足用戶需求的組合。本文提出了一種基于Skyline服務(wù)的全局QoS約束下的web服務(wù)選擇方法。通過區(qū)分出Skyline服務(wù)同時(shí)對其進(jìn)行層次聚類，使用虛擬最優(yōu)點(diǎn)定位有解的層次后，求解全局最優(yōu)解。實(shí)驗(yàn)表明，該方法有較好的有效性以及較好的性能。關(guān)鍵詞web服務(wù);skyline；服務(wù)組合中圖分類號TP39文獻(xiàn)標(biāo)識碼A文章編號1674-6708(2

2、012)81-0237-02面向服務(wù)的計(jì)算能夠無縫地把現(xiàn)存的各種商業(yè)應(yīng)用服務(wù)組合起來，形成新的增值服務(wù)滿足用戶的需求。如何能從具有不同QoS屬性的高度動(dòng)態(tài)化的web服務(wù)中，以有效的方式在較短的時(shí)間內(nèi)選擇出滿足用戶對于全局QoS需求的服務(wù)，已經(jīng)是web服務(wù)組合中一個(gè)比較重要的問題。在文獻(xiàn)［1］中提出了一種基于skyline服務(wù)的服務(wù)選擇方法。該方法通過區(qū)分出skyline服務(wù)，同時(shí)進(jìn)行層次聚類,對每一層使用混合線性規(guī)劃(MIP,mixedintegerprogram)求解最優(yōu)解。本文在該方法的基礎(chǔ)上進(jìn)行改進(jìn)，通過增加虛擬最優(yōu)點(diǎn)，定位有解的層次，進(jìn)一步縮

3、小搜索范圍，使得性能進(jìn)一步得到提升。1全局約束下的服務(wù)選擇1.1QoS效用函數(shù)QoS效用函數(shù)用來將服務(wù)類中的每個(gè)候選服務(wù)的QoS屬性向量Qs映射到一個(gè)實(shí)數(shù)值，通過該值對每一個(gè)候選服務(wù)進(jìn)行排序或分類，便于選擇到滿足QoS約束的服務(wù)組件。本文中的效用函數(shù)采用簡單加權(quán)方法計(jì)算。1.2基于skylineservice的全局QoS約束下的服務(wù)選擇基于全局QoS約束的服務(wù)選擇是一個(gè)最優(yōu)化問題，該問題的重點(diǎn)是從所有可能的服務(wù)組合中選擇一個(gè)QoS效用函數(shù)值最大且滿足全局QoS約束的組合服務(wù)。例如，如果全局QoS約束，求得的組合服務(wù)是最優(yōu)組合服務(wù)，則必須滿足以下兩個(gè)條

4、件：組合服務(wù)中所有服務(wù)類的QoS效用函數(shù)值U(CS)最大;組合服務(wù)的QoS聚合值。通過在論文［1］所提出的方法上進(jìn)行改進(jìn)，本節(jié)提出了時(shí)間復(fù)雜度較低的服務(wù)選擇方法。定義1：Dominate,在一個(gè)服務(wù)類S中，有兩個(gè)服務(wù)x,yGS.xdominatesy,記做x?y,當(dāng)且僅當(dāng)x在QoS的所有維度都不比y服務(wù)的差，并且至少有一維要優(yōu)于y。定義2：Skyline服務(wù)，在一個(gè)服務(wù)類中，所有沒有被dominate的服務(wù)都是Skyline服務(wù)。該方法的主要步驟如下：步驟1：對于抽象的組合服務(wù)S中所有的服務(wù)類Sj找出每一個(gè)服務(wù)類中的所有skyline服務(wù)。步驟2：構(gòu)

5、造QoSLeveltree。對每一個(gè)服務(wù)類的skyline服務(wù)聚類到k個(gè)集合中，其中22,4,6,K并且為每一個(gè)集合選取一個(gè)代表性的服務(wù)。這里我們選取每個(gè)集合中ut訂ity值最大的服務(wù)代表該集合，將這些具有代表性的服務(wù)構(gòu)造成一棵二叉樹。樹的葉子節(jié)點(diǎn)對應(yīng)于skyline服務(wù)的每一個(gè)服務(wù)，跟節(jié)點(diǎn)和中間結(jié)點(diǎn)對應(yīng)于聚類后產(chǎn)生的集合的代表服務(wù)。步驟3：構(gòu)建虛擬最優(yōu)點(diǎn)及定位有解的起始層次。對于每一個(gè)服務(wù)類的QoSLeveltree的每一層構(gòu)造一個(gè)虛擬最優(yōu)點(diǎn)，該虛擬最優(yōu)點(diǎn)的QoS每一維的屬性值等于該層所有服務(wù)中QoS的每一維度的最優(yōu)屬性值。然后，對于所有服務(wù)類的每

6、一層的虛擬最優(yōu)點(diǎn)進(jìn)行聚合計(jì)算。如果聚合值滿足全局QoS約束，則該層可能有解。步驟4：使用MIP進(jìn)行求解。通過上一步定位出了有解的起始層次，從該層開始使用MIP求解，直到找到最優(yōu)解為止。MIP公式如下：xij代表服務(wù)類Sj中的服務(wù)yij是否被選擇，如果yij被選擇，則xij=1否則xij=Oo約束條件：2實(shí)驗(yàn)對比為了驗(yàn)證本文所提出的方法，在不同數(shù)量的web服務(wù)的和不同的全局QoS約束下同一下幾種方法進(jìn)行比較：ExactSkyline：基于Skyline的標(biāo)準(zhǔn)的全局約束下求解最優(yōu)解的方法。SkylineRep：文獻(xiàn)［1］中所提出的方法。SkylineRe

7、p-VOP：對于文獻(xiàn)［1］中方法的改進(jìn)。備選服務(wù)的QoS使用QWSdataset,該數(shù)據(jù)集包含2500個(gè)真實(shí)web服務(wù)的9個(gè)QoS屬性。該實(shí)驗(yàn)使用備選服務(wù)包含10個(gè)備選服務(wù)類，每次實(shí)驗(yàn)的每個(gè)備選服務(wù)類中的服務(wù)數(shù)量從100變化到1000,每一次實(shí)驗(yàn)重復(fù)100次得到如下圖所不結(jié)果：在三種方法中，SkylineRep-VOP明顯優(yōu)于其他兩種方法。當(dāng)備選服務(wù)類中服務(wù)數(shù)量增加時(shí)，SkylineRep和SkylineRep-VOP所花費(fèi)的時(shí)間沒有明顯增長。這兩種的方法性能上的差別主要體現(xiàn)在處理了多少層的RepresentTree,因?yàn)樘摂M最優(yōu)點(diǎn)的加入，Skyli

8、neRep-VOP能夠排除一些不可能存在解的層次，而不是每次都從第一層開始,因此該算法在性能上要比原算法要好