沈夢(mèng)婷　劉方方

(上海大學(xué)計(jì)算機(jī)工程與科學(xué)學(xué)院　上海 200444)

?

基于不確定QoS的Web服務(wù)選擇

沈夢(mèng)婷劉方方

(上海大學(xué)計(jì)算機(jī)工程與科學(xué)學(xué)院上海 200444)

摘要服務(wù)質(zhì)量(QoS)是Web服務(wù)選擇的一個(gè)重要考慮因素。目前基于QoS的Web服務(wù)選擇研究多針對(duì)確定的QoS數(shù)據(jù)，此類方法不適合處理不確定的QoS屬性。而已有的針對(duì)不確定QoS屬性的研究方法基于離散的QoS屬性，無(wú)法處理QoS屬性連續(xù)時(shí)的情形。因此，提出針對(duì)不確定的連續(xù)QoS屬性的查詢方法，并提出QoS屬性值在一定分布下的優(yōu)化方法。實(shí)驗(yàn)表明，該方法能有效解決Web服務(wù)QoS屬性連續(xù)條件下的查詢，具備一定的可行性。

關(guān)鍵詞Web服務(wù)不確定性QoS

0引言

Internet環(huán)境下Web服務(wù)通過(guò)WSDL、SOAP和UDDI等一組技術(shù)標(biāo)準(zhǔn)進(jìn)行通信。隨著Web服務(wù)技術(shù)的廣泛應(yīng)用，Internet上不同的服務(wù)商提供了功能相似的Web服務(wù)。如何利用不同的QoS屬性值，從功能相似的Web服務(wù)中查找選擇高質(zhì)量、滿足用戶需求的服務(wù)，已成為熱點(diǎn)研究問(wèn)題之一。例如，通過(guò)公寓查詢服務(wù)從不同的代理上獲得一系列的價(jià)格、信譽(yù)、響應(yīng)時(shí)間等租房信息，利用這些服務(wù)的QoS信息，選擇一個(gè)最能滿足用戶需求的Web服務(wù)，或通過(guò)服務(wù)排序得到最好的幾個(gè)服務(wù)。

目前對(duì)基于QoS的Web服務(wù)的研究多數(shù)是假定QoS屬性是確定的，固定不變的。例如，查詢公寓是一個(gè)單間需要998美元，這是一個(gè)固定不變的數(shù)。然而，有時(shí)價(jià)格并非是一個(gè)固定的值，可能是在一個(gè)區(qū)間里浮動(dòng)，如表1所示，價(jià)格可在區(qū)間[＄990,＄1200]浮動(dòng)。除了價(jià)格外，其他屬性也會(huì)在區(qū)間里浮動(dòng)，比如等候申請(qǐng)公寓的人數(shù)較多，導(dǎo)致批準(zhǔn)時(shí)間可能在1到2個(gè)月內(nèi)，公寓的聲譽(yù)可能處在中等和高等之間等。以此可見，這些屬性更適合用區(qū)間表示。

在實(shí)際應(yīng)用中，用確定性的方法研究Web服務(wù)往往不適用于處理不確定QoS。例如，用戶想根據(jù)價(jià)格對(duì)Web服務(wù)進(jìn)行排序，而價(jià)格并非是一個(gè)確定離散的值。如表1所示，“pleasant view”的價(jià)格下界低于“sg.Court”的下界，它的上界高于后者的上界。此時(shí)QoS屬性不是離散的，因而無(wú)法用加權(quán)平均值這種計(jì)算確定QoS的方法來(lái)解決Web服務(wù)排序問(wèn)題。

表1　租借服務(wù)

目前提出了不少針對(duì)不確定QoS的Web服務(wù)選擇的方法，而這些方法主要是在QoS屬性離散的情況下，即每個(gè)QoS值有一個(gè)存在概率。例如，響應(yīng)時(shí)間1000 ms，它的存在概率是0.7。為了處理這類不確定數(shù)據(jù)，文獻(xiàn)[1]提出了用屬性的歷史值來(lái)統(tǒng)計(jì)算不確定QoS值和存在概率的方法。而文獻(xiàn)[2,14-17]利用skyline的方法查詢相似服務(wù)之間QoS屬性的支配關(guān)系，從而避免給QoS屬性分配權(quán)重。這些方法只考慮了QoS屬性是離散的，并沒有考慮到QoS屬性是區(qū)間值或連續(xù)的情況。

本文提出基于不確定連續(xù)QoS屬性值的Web服務(wù)選擇方法。目前，概率數(shù)據(jù)已經(jīng)在數(shù)據(jù)庫(kù)領(lǐng)域廣泛地被研究[3-9]。對(duì)于連續(xù)性的不確定數(shù)據(jù)的研究則更具有挑戰(zhàn)性。其中有兩個(gè)原因:(1) 不確定數(shù)據(jù)的查詢語(yǔ)義并沒有統(tǒng)一的定義。比如，租借服務(wù)的某些提供者暫無(wú)房源時(shí)，查詢結(jié)果是否還需要選擇考慮這些服務(wù)。而在不確定數(shù)據(jù)研究中[3-9]，這些服務(wù)雖然不可用，但服務(wù)本身仍然存在，也是記錄中的一部分。由此可見，語(yǔ)義不同，查詢結(jié)果也會(huì)不同。(2) 對(duì)不確定數(shù)據(jù)的排序?qū)⑸婕暗礁呔S概率計(jì)算，導(dǎo)致算法的時(shí)間消耗大。

本文針對(duì)實(shí)際應(yīng)用場(chǎng)景，提出解決不確定QoS的Web服務(wù)查詢方法，它將不確定數(shù)據(jù)的查詢語(yǔ)義應(yīng)用到服務(wù)查詢中。本文給出兩種查詢定義：top-uncertain 和uncertain score rank。前一種方法和U-topk[5]類似，但是U-topk只考慮離散數(shù)據(jù)，而top-uncertain是基于連續(xù)數(shù)據(jù)。后一種方法類似U-kRank的連續(xù)分布的擴(kuò)展[3,4]。最后，通過(guò)實(shí)驗(yàn)表明，本文提出的兩種方法能有效解決Web服務(wù)QoS屬性連續(xù)條件下的查詢，具備一定的可行性。

1查詢定義

由于Web服務(wù)處在開放的互聯(lián)網(wǎng)環(huán)境中， QoS受多方面影響產(chǎn)生不確定性。目前處理這種不確定性主要幾種在QoS離散的情況下，即計(jì)算每條記錄的存在概率，并沒考慮到QoS屬性是區(qū)間值或連續(xù)的情況。至此，本節(jié)介紹Web服務(wù)中不確定連續(xù)QoS的表示，同時(shí)介紹兩種針對(duì)QoS連續(xù)的情況下的查詢定義。

本文定義的兩種算法分別針對(duì)不同的應(yīng)用場(chǎng)景，前者假定QoS記錄存在概率為1，即不考慮服務(wù)的可信程度；后者則假設(shè)QoS記錄有一個(gè)存在概率，主要適用于對(duì)可信度要求較高的應(yīng)用場(chǎng)景。

(1)其中pr(sj)表示W(wǎng)eb服務(wù)sj的存在概率。式中，它由各個(gè)屬性的存在概率決定。例如，由于受網(wǎng)絡(luò)的影響，Web服務(wù)的響應(yīng)時(shí)間會(huì)出現(xiàn)波動(dòng)，同時(shí)服務(wù)被客戶正確使用的概率，即可用性也會(huì)隨著時(shí)間的變化不斷改變。區(qū)間表示集中出現(xiàn)的波動(dòng)范圍，每個(gè)屬性的浮動(dòng)區(qū)間存在一個(gè)概率密度函數(shù)。一個(gè)Web服務(wù)的可信概率，也即存在概率，即所有屬性存在概率累乘。式(1)可解決在不確定連續(xù)QoS屬性下Web服務(wù)存在概率的計(jì)算。

多數(shù)情況下，用戶喜歡通過(guò)計(jì)算QoS整體分值的方法找出滿足他們要求的Web服務(wù)。因此，本文定義了score(sj;q1,…,qn)來(lái)描述QoS的整體分值，記為score(sj)。QoS值是由聚合函數(shù)得到的，假設(shè)聚合函數(shù)是線性函數(shù)，QoS的權(quán)重已經(jīng)被分配(默認(rèn)的或者用戶定義)。這樣，score(sj)計(jì)算如下：

(2)

式(2)是一個(gè)聚合函數(shù)，通過(guò)聚合函數(shù)，將多個(gè)屬性聚合按照一定規(guī)則聚合成一個(gè)QoS值，用這種化多為少的方法可解決多目標(biāo)決策問(wèn)題。同時(shí)，計(jì)算中融入用戶需求和偏好計(jì)算的QoS值，更能準(zhǔn)確地選擇滿足用戶需求的服務(wù)。

在文獻(xiàn)[4]中，為了計(jì)算的簡(jiǎn)化，認(rèn)為sj的存在概率為1，即sj的存在和它的屬性存在不相關(guān)；而另一種情況， 假定sj的存在概率是QoS值的存在概率。對(duì)于由連續(xù)不確定QoS屬性值計(jì)算得到的QoS值來(lái)說(shuō)，每個(gè)記錄的QoS值也是連續(xù)不確定的，把它作為服務(wù)的一個(gè)特殊屬性值。此時(shí)，pr(sj)用pr(score(sj))表示。

在Web服務(wù)的中，以上兩種情況都有可能發(fā)生。所以，本文定義這兩種情況下的查詢語(yǔ)義。

例1假設(shè)表1中的QoS屬性的線性聚合函數(shù)為score(sj)=0.3·mprice+0.4·mw_l+0.3·mreputation。用戶想根據(jù)QoS值排名得到前二個(gè)的服務(wù)。由于 “sg.Court” 暫無(wú)房源，針對(duì)不同的查詢語(yǔ)義將得到不同的結(jié)果。例如，如果考慮所有服務(wù)都存在，返回的結(jié)果為{s1,s3}，而只考慮有房源的服務(wù)，則返回的結(jié)果為{s1,s2}。

針對(duì)第一種情況，以QoS記錄的存在概率為1為前提，這樣，返回結(jié)果排名只取決于QoS值的分布。本文對(duì)其做如下定義：

定義1Top-uncertain QoS:S={sj}是一組服務(wù)集，T={T1,…,Tm}， 是一組長(zhǎng)度為k的服務(wù)向量集，每個(gè)Ti集中的服務(wù)都是根據(jù)QoS值進(jìn)行排序。Top-uncertain QoS的返回結(jié)果記為T*，其中T*=argmaxT*∈T (∑sj∈T*pr(score(sj)))。

定義1和u-topk[5]相似，都是返回元組集中概率最大的K個(gè)服務(wù)。不同的是，u-topk所返回的是所有可能世界中發(fā)生概率最大的。而本文以服務(wù)的存在概率為1為前提，針對(duì)不確定的連續(xù)QoS屬性提出的一種查詢方法。

第二種情況，服務(wù)記錄是否存在由QoS值的存在概率決定。其中，QoS值的概率分布即是存在概率分布。在這種情況下，和Top-uncertain QoS的返回結(jié)果不同，因?yàn)閷?duì)服務(wù)的排序不僅由QoS值也由它存在概率決定。例如，表1中有三個(gè)service，假設(shè)它們的存在概率不是1，由這三個(gè)服務(wù)組成的可能世界[5-7]有{s1},{s2},{s3},{s1,s2},{s2,s3},{s1,s3},{s1,s2,s3}。以服務(wù)s3為例，在不同的可能世界實(shí)例中，它的排序位置不同。

pr(PWl)是PWl的存在概率。它為其包含服務(wù)S的存在概率的累積。

此方法根據(jù)計(jì)算的位置函數(shù)值返回最優(yōu)的K個(gè)服務(wù)。定義2類似于U-kRank[3,8,9]，都是通過(guò)計(jì)算可能世界中的位置排名返回最優(yōu)的K個(gè)服務(wù)，不同之處定義2所計(jì)算的QoS值的概率作為記錄的存在的概率。

2查詢算法

對(duì)不確定數(shù)據(jù)進(jìn)行排序和查詢選擇時(shí)需要考慮其概率和各屬性值之間組成的語(yǔ)義，文獻(xiàn)[5]提出了結(jié)合可信值和數(shù)據(jù)值的查詢算法U-topk和U-kRank。這兩種算法都是在數(shù)據(jù)概率離散情況下的處理方式，而對(duì)數(shù)據(jù)連續(xù)分布的情況未作出處理。本節(jié)提出的兩種查詢算法top-uncertain QoS和uncertain score rank，旨在解決不確定連續(xù)QoS的Web服務(wù)選擇。

不同的查詢語(yǔ)義所強(qiáng)調(diào)的是其所滿足的性質(zhì)和應(yīng)用環(huán)境。本文提出的兩種適用不同的應(yīng)用環(huán)境的查詢語(yǔ)義算法。

2.1top-uncertain QoS計(jì)算

本方法中，假設(shè)QoS記錄存在概率為1。本文重點(diǎn)是通過(guò)QoS值的概率密度分布進(jìn)行比較。QoS屬性值是不確定連續(xù)，而對(duì)于QoS值來(lái)說(shuō)，每個(gè)記錄的QoS值也是連續(xù)不確定的，此時(shí)，服務(wù)的排序是由區(qū)間和概率密度分布決定的。當(dāng)記錄相互獨(dú)立，QoS值具有相同概率密度分布時(shí)，通過(guò)比較積分面積[4]去比較哪個(gè)服務(wù)具有更高的服務(wù)質(zhì)量的概率。具體如下：

首先，比較si和sj。si和sj的區(qū)間分別由[li,ui]和[lj,uj]表示。QoS值也有相同的概率分布。設(shè)概率密度函數(shù)為ρ。這樣得到：

假設(shè)sj也有相同的概率分布，當(dāng)si和sj都是連續(xù)區(qū)間上的變量時(shí)，si的QoS值大于sj的概率為：

式中，ρi,j為si和sj的QoS值變量的聯(lián)合概率密度函數(shù)。Di,j表示u>v的積分域,即score(si)>score(sj)。

如圖1所示，x坐標(biāo)和y坐標(biāo)分別表示si和sj的區(qū)間。si和sj區(qū)間組成的面積被直線y=x分割成ai和aj兩個(gè)部分。如果ai>aj,則si的QoS值大于sj的QoS值可能性高，即pr(score(si)>score(sj))>pr(score(si)≤score(sj))。

圖1　積分面積不同的情況

當(dāng)記錄存在概率為1，QoS值符合相同密度分布時(shí)，top-uncertain QoS通過(guò)比較積分面積[4]計(jì)算兩服務(wù)之間具有更高的服務(wù)質(zhì)量的概率，從而避免多重積分的計(jì)算，降低時(shí)間消耗。它不考慮記錄可信度，即假設(shè)記錄的存在概率為1。例如，在公寓查詢時(shí)，它沒有考慮無(wú)房源的情況。

下面是top-uncertain QoS的算法：

其中，comp(si,sj)表示比較哪個(gè)服務(wù)具有更高的服務(wù)質(zhì)量，如果si>sj，則comp(si,sj)=1；否則為0。DS表示服務(wù)集；ret_serk代表服務(wù)返回的k個(gè)結(jié)果，當(dāng)DS為空時(shí)算法終止。Queue存儲(chǔ)被訪問(wèn)的、不在ret_serk里的服務(wù)集。

算法1top-uncertain QoS算法

1:初始化：Queue←φ，ret_ser0←φ

d←0表示查詢深度

2:ret_serk←DS中最先出棧k個(gè)

3:high,low←ret_serk中最大最小的代表值

4:while (DS≠φ) do

5:sd←DS中當(dāng)前出棧的服務(wù)

6:if comp(high,sd)=0

7:if comp(sd,low)=1

8:ret_serk←sd

9:low←ret_serk中最小的代表值

10:else

11:Queue←sd

12:else

13:ret_serk←sd

14:high←sd

15:endif

16:endwhile

17:return ret_serk

2.2uncertain score rank計(jì)算

在計(jì)算top-uncertain QoS時(shí)，如果QoS記錄存在概率不等于1。根據(jù)該定義，需要掃描所有的可能世界。例如表1,3個(gè)服務(wù)產(chǎn)生7個(gè)可能世界。通常情況下，n個(gè)服務(wù)將產(chǎn)生2n個(gè)可能世界。由此可見，隨著服務(wù)數(shù)量的增加，可能世界會(huì)成指數(shù)級(jí)增加，這樣大大增加了計(jì)算的時(shí)間復(fù)雜度。

文獻(xiàn)[3]提出了一種剪枝的算法以減少運(yùn)算代價(jià)。這種PRF方法基于離散不確定數(shù)據(jù)，當(dāng)QoS值是離散的時(shí)候，遞減排序。對(duì)于服務(wù)si，{sj}i集表示QoS值高于si的集合。由于低于si的QoS值的服務(wù)不會(huì)對(duì)si的排名結(jié)果造成影響，所以{sj}i只考慮QoS值高于si的集合。文獻(xiàn)[8,9]提出了多項(xiàng)式系數(shù)的方法求解si排名k的所有可能世界的概率累和。其多項(xiàng)式公式如下：

(3)

將多項(xiàng)式展開如下：

式(3)只考慮離散的不確定數(shù)據(jù)條件下，本文將它擴(kuò)展應(yīng)用到不確定的連續(xù)數(shù)據(jù)，uncertain score rank是利用PRF多項(xiàng)式系數(shù)得到服務(wù)排名位置的概率。然后計(jì)算返回pos(si)值最好的前K個(gè)。

綜上，當(dāng)pr(sj)為pr(score(sj))時(shí)式(3)轉(zhuǎn)換為：

pr(score(sj)>score(si))x)

(1-pr(score(sj)≤score(si))x)

(4)

用變量v替換score(si)式(4)變?yōu)槿缦拢?/p>

pr(score(sj)

整理得：

(5)

其中，ρi,j(u,v)是si和sj的QoS值的聯(lián)合概率密度函數(shù)。

得出：

化簡(jiǎn)得：

(6)

其中，n是服務(wù)的總數(shù)。

用式(6)，可計(jì)算每個(gè)服務(wù)的pos(si)。最后返回pos值高的前k個(gè)。

Uncertain score rank算法考慮了記錄可信度。假定記錄的存在概率為QoS值的存在概率，對(duì)于由連續(xù)不確定QoS屬性計(jì)算得到的QoS值來(lái)說(shuō)，每個(gè)記錄的QoS值也是連續(xù)不確定的，這種算法適用于對(duì)可信度要求較高的服務(wù)選擇情況。例如，在公寓查詢時(shí)，將無(wú)房源的情況考慮進(jìn)去。

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

目前互聯(lián)網(wǎng)的Web服務(wù)數(shù)量不超過(guò)10 000個(gè)，功能相同的服務(wù)也不超過(guò)300個(gè)，因此我們選擇Web服務(wù)數(shù)量的范圍在50到500之間。為驗(yàn)證uncertain score rank和 top-uncertain ranking of QoS這兩種算法的可行性。本文模擬一個(gè)數(shù)據(jù)集，每個(gè)數(shù)據(jù)集有500條數(shù)據(jù)。每條記錄的上下界在[0,10]中間浮動(dòng)，記錄的區(qū)間大小從0到10不等。本文假設(shè)概率分布分別符合均勻分布、標(biāo)準(zhǔn)正態(tài)分布和自定義正態(tài)分布的三種情況出發(fā)分析兩種方法的執(zhí)行時(shí)間。

在Web服務(wù)中，受到開放性網(wǎng)絡(luò)的影響，其服務(wù)的響應(yīng)時(shí)間集中在一定范圍內(nèi)浮動(dòng)，離散的數(shù)據(jù)未能正確反映原有數(shù)據(jù)的分布。同時(shí)如按照離散型QoS屬性值處理，當(dāng)樣本數(shù)據(jù)量龐大，很難準(zhǔn)確計(jì)算每條記錄的概率，如用簡(jiǎn)單的概率分布函數(shù)表示存在概率，可避免每條記錄的概率計(jì)算。通過(guò)本實(shí)驗(yàn)分析表明，該方法能有效解決Web服務(wù)QoS屬性連續(xù)條件下的查詢，具備一定的可行性。

3.1基于均勻分布和正態(tài)分布的uncertain score rank

利用式(6)，通過(guò)計(jì)算每個(gè)sj的prj,i來(lái)計(jì)算si的位置QoS值，si和sj無(wú)論屬于哪種概率分布。當(dāng)ui

圖2　服務(wù)QoS屬性值區(qū)間

根據(jù)上述的4中情況，prj,i的計(jì)算如下：

(7)

根據(jù)式(6)、式(7)，可計(jì)算服務(wù)的位置QoS值。

在服務(wù)數(shù)量不同，返回服務(wù)個(gè)數(shù)不同的情況下，圖3分別表示均勻分布和正態(tài)分布條件下uncertain score rank的運(yùn)行時(shí)間。

圖3　uncertain score rank運(yùn)行時(shí)間

在正態(tài)分布的情況下，si的概率密度函數(shù)為：

圖3(b)和圖3(c)分別是標(biāo)準(zhǔn)正態(tài)分布和μ=7,σ=4的正態(tài)分布圖。運(yùn)行時(shí)間隨著服務(wù)數(shù)量的增加而增加，而k值的變化對(duì)運(yùn)行時(shí)間的影響并不大。

從圖3得出，對(duì)于不同的分布，時(shí)間消耗主要在可能性pr的計(jì)算上。

3.2基于均勻分布和正態(tài)分布的Top-uncertain ranking of QoS

這種方法，我們不需要計(jì)算位置的多重積分值，只需要比較服務(wù)si和sj的QoS屬性值區(qū)間所圍成的面積大小。而且不需知道其服務(wù)屬于哪種分布，即不同分布對(duì)此方法的時(shí)間消耗沒有影響。

圖4是不同的服務(wù)數(shù)量在兩種不同分布下的運(yùn)行時(shí)間。

圖4　Top-uncertain ranking of QoS運(yùn)行時(shí)間

4相關(guān)工作

隨著功能相似的Web服務(wù)的逐漸增多，基于QoS的Web服務(wù)選擇已經(jīng)成為目前的一個(gè)研究熱點(diǎn)。

文獻(xiàn)[8]提出了一種可擴(kuò)展的QoS計(jì)算模型，它是根據(jù)用戶反饋信息建立QoS信息的計(jì)算模型。文獻(xiàn)[9,10]提出了利用線性規(guī)劃的方法找到最佳服務(wù)。類似于這個(gè)方法，文獻(xiàn)[11]提出了帶有本地約束的線性編程模型。文獻(xiàn)[12]研究了在多個(gè)QoS約束條件下的服務(wù)選擇問(wèn)題,它提出了兩種QoS組合中的融入啟發(fā)式算法的模型：(1) 組合模型；(2) 圖模型。文獻(xiàn)[13]介紹了一種用于評(píng)估多維屬性的QoS的選擇算法。以上的這些方法都是基于確定的QoS。

目前，也有不少針對(duì)不確定的QoS研究，文獻(xiàn)[1]介紹了離散的不確定QoS屬性，提出了一種對(duì)不確定QoS的描述方法，并給每個(gè)QoS屬性設(shè)立一個(gè)權(quán)值，計(jì)算出Web服務(wù)中每條記錄的加權(quán)QoS值之和進(jìn)行排序。利用U檢驗(yàn)或者峰度和偏態(tài)返回?cái)?shù)值較小的Web服務(wù)。文獻(xiàn)[2,14-17]提出了Skyline的QoS查詢方法，這種方法不需要用戶給出QoS的權(quán)重。文獻(xiàn)[2,17]將Skyline的查詢方法應(yīng)用到了不確定QoS中，并提出了一種提高Skyline查詢的效率方法。然而這些方法都是基于離散的不確定QoS。

連續(xù)的不確定性在文獻(xiàn)[3,4]中被提出來(lái)，它比離散的不確定性更加復(fù)雜。對(duì)于連續(xù)的不確定數(shù)據(jù)的查詢方法主要難點(diǎn)還是在查詢語(yǔ)義的定義[4]和不確定數(shù)據(jù)的表示[3]。

針對(duì)不確定數(shù)據(jù)查詢有不同的查詢語(yǔ)義[5]，這些方法都是基于離散的數(shù)據(jù)。本文在現(xiàn)有的基礎(chǔ)上，提出了基于連續(xù)不確定QoS的Web服務(wù)查詢方法。最后通過(guò)實(shí)驗(yàn)驗(yàn)證了本文方法的可行性。

5結(jié)語(yǔ)

本文根據(jù)不同的查詢語(yǔ)義，提出針對(duì)不確定的連續(xù)QoS屬性的查詢方法，并提出了QoS屬性值在一定分布下的優(yōu)化方法。實(shí)驗(yàn)表明，該方法能有效解決Web服務(wù)QoS屬性連續(xù)條件下的查詢，具備一定的可行性。接下去的工作主要集中以下兩點(diǎn)：(1) 討論涵蓋更多應(yīng)用場(chǎng)景的查詢語(yǔ)義和研究相應(yīng)的算法；(2) 研究如何優(yōu)化技術(shù)，降低算法的復(fù)雜性，減少時(shí)間消耗。

參考文獻(xiàn)

[1] Cheng Wan,Hongbing Wang.Uncertainty-aware QoS Description and Selection Model for Web Services[C]//IEEE International Conference on Services Computing,Salt Lake City,UT:IEEE,2007.

[2] Karim Benouare,Djamal Benslimane,Allel Hadjali.Selecting Skyline Web Services from Uncertain QoS[C]//IEEE International Conference on Services Computing, HI:IEEE,2012.

[3] Jian Li,Amol Deshpande.Ranking Continuous Probabilistic Datasets[J].Proceedings of the VLDB Endowment,2010,3(1):638-649.

[4] Chonghai Wang,Liyan Yuan,Jiahuai You.On the semantics of top-k ranking for objects with uncertain data[J].Computers and Mathematics with Applications,2011,62(7):2812-2823.

[5] Soliman M,Ilyas I,Chang K C.Top-k query processing in uncertain databases[C]//IEEE 23rdInternational Conference on Data Engineering,Istanbul:IEEE,2007.

[6] Chonghai Wang,Li Yan Yuan,Jia Huai You,et al.On Pruning for Top K Ranking in Uncertain Databases[J].PVLDB,2011,4(10):598-609.

[7] Gupta R,Sarawagi S.Creating Probabilistic Databases from Informaiton Extraction Model[C]//Proceedings of the 32nd international conference on Very large data bases,2006.

[8] Jian Li,Barna Saha,Amol Deshpande.A Unified Approach to Raning in Probabilistic Databases[J].The VLDB Journal,2009,20(2):249-275.

[9] Jian Li,Amol Deshpande.Consensus answers for queries over probabilistic databases[C]//Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems,New York:ACM,2009.

[10] Liu Y,Ngu A H H,Zeng L.Qos computation and policing in dynamic web service selection[C]//Proceedings of the 13th international World Wide Web conference on Alternate track papers & posters,New York:ACM,2004.

[11] Zeng L,Benatallah B,Dumas M,et al.Quality driven web services composition[C]//Quality driven web services composition,New York:ACM,2003.

[12] Zeng L,Benatallah B,Ngu A H H,et al.Qos-aware middleware for web services composition[J].IEEE Trans. Software Eng,2004,30(5):311-327.

[13] Ardagna D,Pernici B.Adaptive service composition in flexible processes[J].IEEE Trans.Software Eng,2007,33(6):369-384.

[14] Yu T,Zhang Y,Lin K J.Efficient algorithms for web services selection with end-to-end qos constraints[J].ACM Transactions on the Web (TWEB),2007,1(1):1-26.

[15] Wang X,Vitvar T,Kerrigan M,et al.A qos-aware selection model for semantic web services[C]//Proceedings of the 4th international conference on Service-Oriented Computing,Berlin,Springer-Verlag,2006.

[16] Alrifai M,Skoutas D,Risse T.Selecting skyline services for qos-based web service composition[C]//Proceedings of the 19th international conference on World wide web,New York:ACM,2010.

[17] Yu Q,Bouguettaya A.Computing service skylines over sets of services[C]//2010 IEEE International Conference on Web Services,Miami,FL:IEEE,2010.

[18] Benouaret K,Benslimane B,HadjAli A.On the use of fuzzy dominance for computing service skyline based on qos[C]//2010 IEEE International Conference on Web Services, Washington,DC:IEEE,2011.

[19] Yu Q,Bouguettaya A.Computing service skyline from uncertain qows[J].IEEE T. Services Computing,2010,3(1):16-29.

收稿日期：2014-12-28。上海市自然科學(xué)基金項(xiàng)目(12ZR14110 00)；2015年度上海大學(xué)電影高峰學(xué)科成果。沈夢(mèng)婷，碩士生，主研領(lǐng)域：Web service。劉方方，副教授。

中圖分類號(hào)TP3

文獻(xiàn)標(biāo)識(shí)碼A

DOI:10.3969/j.issn.1000-386x.2016.07.006

UNCERTAIN QOS-BASED WEB SERVICES SELECTION

Shen MengtingLiu Fangfang

(SchoolofComputerEngineeringandScience,ShanghaiUniversity,Shanghai200444,China)

AbstractQuality of service (QoS) is considered as a significant criterion for Web services selection. Most of researches in regard to QoS-based Web services selection focus on the determined QoS data, such kind of means are not suitable for processing uncertain QoS attributes. However existing research means for uncertain QoS attributes are based on discrete QoS attributes and cannot deal with the situation when the QoS attributes are in continuity. Therefore in this paper, we present the query method for continuous QoS attributes with uncertainty, and propose the optimisation approach for QoS attributes under certain distribution. It is indicated by experiment that the method is able to effectively solve the query of Web services under the condition of QoS attributes in continuity, and it possesses certain feasibility as well.

KeywordsWeb serviceUncertaintyQoS