利用前景理論的不確定QoS感知Web服務(wù)選擇

嚴(yán) 華,付曉東,2,岳 昆,劉 驪,劉利軍

1(昆明理工大學(xué) 信息工程與自動化學(xué)院云南省計(jì)算機(jī)技術(shù)應(yīng)用重點(diǎn)實(shí)驗(yàn)室,昆明 650500)2(昆明理工大學(xué) 航空學(xué)院,昆明 650500)3(云南大學(xué) 信息學(xué)院,昆明 650091)

1 引 言

Web服務(wù)是具有自描述、模塊化等特點(diǎn)的Web應(yīng)用程序,目前已成為面向服務(wù)的體系結(jié)構(gòu)(Service-Oriented Architerture,SOA)的最佳支撐技術(shù).近年來,隨著Web服務(wù)技術(shù)的飛速發(fā)展,網(wǎng)絡(luò)上出現(xiàn)大量功能相同或相似的Web服務(wù),但是它們的服務(wù)質(zhì)量(Quality of Service,QoS)會出現(xiàn)不盡相同的情況.因此在服務(wù)選擇過程中,QoS成為選擇Web服務(wù)的關(guān)鍵因素.

由于網(wǎng)絡(luò)環(huán)境的開放性,Web服務(wù)的QoS屬性如響應(yīng)時間、吞吐量、可靠性等容易受到用戶的網(wǎng)絡(luò)狀況、服務(wù)負(fù)載、位置等因素的影響,導(dǎo)致Web服務(wù)的QoS屬性存在不確定情況,這就使得如何選擇滿足用戶QoS需求的服務(wù)成為一個具有挑戰(zhàn)性的問題:首先,由于QoS信息的不確定性,使得用戶面臨所獲取的服務(wù)不能滿足其需求的風(fēng)險(xiǎn),因此在進(jìn)行Web服務(wù)選擇時面對QoS不確定的情況,需要考慮用戶的風(fēng)險(xiǎn)態(tài)度如風(fēng)險(xiǎn)偏好[1]等因素.其次,由于內(nèi)部狀態(tài)和外部環(huán)境等因素的不同,同一服務(wù)內(nèi)的QoS屬性以及不同服務(wù)間的QoS屬性分布概率都不盡相同,因此在不確定QoS條件下Web服務(wù)選擇中假設(shè)QoS屬性為特定分布情況[2,3]不符合實(shí)際情況.

為解決上述問題,提出一種基于前景理論(Prospect Theory,PT)[4,5]的不確定QoS感知的Web服務(wù)選擇方法,利用前景理論作為基礎(chǔ),在QoS不確定以及QoS不符合特定分布概率的條件下根據(jù)用戶QoS需求、選擇服務(wù)時的風(fēng)險(xiǎn)態(tài)度進(jìn)行Web服務(wù)選擇的問題.

2 相關(guān)工作

QoS感知的Web服務(wù)選擇策略主要分為局部最優(yōu)[6,7,10,11-13]策略和全局最優(yōu)[8,9,14-16]策略.局部最優(yōu)策略只考慮滿足局部選擇的最優(yōu)解,而沒有考慮全局服務(wù)選擇約束;全局最優(yōu)策略考慮服務(wù)組合后的全局最優(yōu)效果,而較少關(guān)注局部服務(wù)選擇結(jié)果的優(yōu)劣.

局部最優(yōu)策略的基本思想是:在每個任務(wù)節(jié)點(diǎn)的候選服務(wù)集合中,依據(jù)QoS約束條件,選出最優(yōu)的局部服務(wù).文獻(xiàn)[10]提出將Skyline計(jì)算引入到服務(wù)選擇中,但只考慮服務(wù)QoS信息為確定值條件,并不能應(yīng)用于QoS不確定場景下的服務(wù)選擇.而針對Web服務(wù)的QoS不確定情況,文獻(xiàn)[11]提出了一種基于FAHP的多維QoS局部最優(yōu)服務(wù)選擇模型.該方法在選擇Web服務(wù)時僅考慮QoS屬性.文獻(xiàn)[12]考慮Web服務(wù)的QoS區(qū)間和用戶需求,文獻(xiàn)[13]通過使用均值標(biāo)準(zhǔn)差描述QoS指標(biāo)來體現(xiàn)QoS動態(tài)變化下服務(wù)查詢選擇的風(fēng)險(xiǎn),但該方法沒有考慮到用戶選擇服務(wù)時的風(fēng)險(xiǎn)態(tài)度.并且在選擇Web服務(wù)的過程中上述研究方法未能將這兩個因素綜合考慮,因此選擇的結(jié)果不能充分體現(xiàn)用戶需求和風(fēng)險(xiǎn)態(tài)度因素.

全局最優(yōu)策略的基本思想是:從單個服務(wù)的選擇變?yōu)檎麄€組合服務(wù)的選擇,使選出的服務(wù)能更加滿足用戶對組合服務(wù)的要求.文獻(xiàn)[14,15]研究基于SOA建立可靠性的Web服務(wù)組合方法,著重解決動態(tài)環(huán)境下的Web服務(wù)選擇.針對QoS信息不確定的情況,文獻(xiàn)[16]根據(jù)粒子群算法,提出一種PSO-GODSS算法用于解決組合服務(wù)中QoS全局最優(yōu)動態(tài)Web服務(wù)選擇問題.上述研究方法選擇的服務(wù)是滿足QoS約束條件的目標(biāo)最優(yōu)解,而不是在最大程度上滿足用戶需求的服務(wù).

考慮以上研究存在的不足,本文在QoS不確定情況下,將用戶對QoS屬性需求作為關(guān)鍵因素,通過比較用戶需求與Web服務(wù)QoS屬性關(guān)系得出風(fēng)險(xiǎn)收益矩陣和風(fēng)險(xiǎn)損失矩陣,考慮用戶的風(fēng)險(xiǎn)態(tài)度,通過前景理論來解決QoS不確定條件下的Web服務(wù)選擇問題.最后,本文通過實(shí)驗(yàn)驗(yàn)證該方法的合理性和有效性.

3 問題描述

首先對QoS不確定條件下的Web服務(wù)選擇問題描述如下:

定義1.候選服務(wù)集合為S={s1,s2,…,sm},其中si(1≤i≤m)表示第i個候選服務(wù),m表示候選服務(wù)集合中服務(wù)個數(shù).

定義2.QoS屬性為Q={q1,q2,…,qn},其中qj(1≤j≤n)表示第j個QoS屬性,n為QoS屬性的個數(shù).QC和QU分別表示成本型QoS屬性和效益型QoS屬性集合,成本型QoS屬性值越小越好,效益型QoS屬性值越大越好.例如,響應(yīng)時間是成本型QoS屬性,而吞吐量、成功率是效益型QoS屬性.

對于可表示為實(shí)數(shù)離散隨機(jī)變量形式的QoS屬性,本文將該條件形式設(shè)定為條件狀態(tài).

定義4.用戶對成本型QoS屬性的需求RC={rc1,rc2,…rcn}.對效益型QoS屬性的需求RU={ru1,ru2,…,run}.此外,本文將用戶的QoS屬性需求作為參照點(diǎn).

當(dāng)Web服務(wù)QoS的信息量充分大時,經(jīng)驗(yàn)分布函數(shù)以概率1一致收斂于分布函數(shù),所以可用經(jīng)驗(yàn)分布函數(shù)作為Web服務(wù)QoS的近似分布函數(shù).因此針對Web服務(wù)的QoS不符合特定分布情況,本文用經(jīng)驗(yàn)分布函數(shù)對每個服務(wù)的不確定QoS屬性進(jìn)行描述.具體計(jì)算公式如下所示:

(1)

(2)

因此,QoS不確定條件下的服務(wù)選擇問題描述為:給定QoS信息,比較用戶的QoS需求與Web服務(wù)QoS信息,利用經(jīng)驗(yàn)分布函數(shù)描述QoS屬性的不確定性,根據(jù)前景理論得出服務(wù)的綜合前景值,并以服務(wù)的綜合前景值選擇服務(wù).

4 基于前景理論的服務(wù)選擇模型

本文運(yùn)用前景理論建立服務(wù)選擇模型對Web服務(wù)進(jìn)行選擇.前景理論屬于心理學(xué)及行為科學(xué)范疇,為在風(fēng)險(xiǎn)和不確定情況下考慮心理因素對決策影響的問題而提出,是處理不確定性信息的重要工具.

前景理論的核心思想是:首先設(shè)定參照點(diǎn),根據(jù)與參照點(diǎn)的比較結(jié)果分為收益和損失,然后建立相應(yīng)的風(fēng)險(xiǎn)矩陣;考慮用戶的風(fēng)險(xiǎn)態(tài)度,通過價值函數(shù)和概率權(quán)重函數(shù)得出綜合前景值,然后對其進(jìn)行評估與選擇.因此,本文是將用戶選擇服務(wù)時的風(fēng)險(xiǎn)態(tài)度和服務(wù)選擇過程有機(jī)結(jié)合,提出考慮QoS不確定條件下的Web服務(wù)選擇方法,從用戶的需求和風(fēng)險(xiǎn)態(tài)度角度出發(fā),量化服務(wù)選擇過程中的不確定性.

根據(jù)前景理論思想,本文首先獲取用戶對QoS屬性的需求作為參照點(diǎn),將其與Web服務(wù)的QoS信息進(jìn)行比較,得到相較于參照點(diǎn)的收益和損失,并構(gòu)建相應(yīng)的風(fēng)險(xiǎn)矩陣(風(fēng)險(xiǎn)收益、損失矩陣);其次用經(jīng)驗(yàn)分布函數(shù)對每個服務(wù)的不確定QoS屬性進(jìn)行描述;然后考慮用戶的風(fēng)險(xiǎn)態(tài)度,根據(jù)風(fēng)險(xiǎn)矩陣和QoS屬性的分布概率,利用前景理論中的價值函數(shù)和概率權(quán)重函數(shù)計(jì)算得出Web服務(wù)的綜合前景值.最后根據(jù)Web服務(wù)的綜合前景值實(shí)現(xiàn)服務(wù)排序和選擇.

4.1 風(fēng)險(xiǎn)收益和損失計(jì)算

(3)

(4)

(5)

(6)

4.2 服務(wù)選擇排序

本文中服務(wù)選擇排序的核心思想是獲取每個候選服務(wù)的綜合前景值,根據(jù)綜合前景值的大小得出候選服務(wù)的排序次序,最終選出最優(yōu)服務(wù).因此,使用前景理論中的價值函數(shù)和概率權(quán)重函數(shù)計(jì)算每個候選服務(wù)的綜合前景值.

利用價值函數(shù)V獲得每個服務(wù)針對各QoS屬性的收益、損失價值.價值函數(shù)是用戶的主觀感受價值[17],其具有以下特征:第一,價值函數(shù)是關(guān)于決策參照點(diǎn)的變化量的函數(shù),指的是相對于某個參照點(diǎn)的收益或損失;第二,價值函數(shù)為S形曲線,即在參照點(diǎn)下方為凸函數(shù),用戶面臨收益時表現(xiàn)出風(fēng)險(xiǎn)規(guī)避態(tài)度,在參照點(diǎn)上方為凹函數(shù),用戶面臨損失時表現(xiàn)出風(fēng)險(xiǎn)偏好態(tài)度.

考慮用戶對收益、損失價值的風(fēng)險(xiǎn)態(tài)度,分別計(jì)算每個服務(wù)針對各QoS屬性的收益、損失的價值V.

(7)

(8)

式(7)-式(8)中α為風(fēng)險(xiǎn)偏好系數(shù),β為風(fēng)險(xiǎn)規(guī)避系數(shù),0<α、β<1,α和β值越大,表示用戶對價值的敏感性越弱;λ為損失規(guī)避系數(shù),λ>1,λ值越大表示用戶對損失越敏感.

利用概率權(quán)重函數(shù)π獲得每個服務(wù)針對各QoS屬性在收益、損失情況下分布概率的權(quán)重.其具有以下特性:第一,概率權(quán)重函數(shù)不是客觀概率,是將客觀概率作為自變量,主觀權(quán)重作為因變量而建立的映射關(guān)系;第二,當(dāng)分布概率p很小時高估小概率事件,賦予過大權(quán)重,有π(p)>p;當(dāng)分布概率p很大時低估大概率事件,賦予過小權(quán)重,有π(p)

考慮用戶對待收益、損失的不同風(fēng)險(xiǎn)態(tài)度,計(jì)算每個服務(wù)針對各QoS屬性的收益、損失情況下的概率權(quán)重.

(9)

(10)

式(9)-式(10)中γ為風(fēng)險(xiǎn)收益態(tài)度系數(shù),δ為風(fēng)險(xiǎn)損失態(tài)度系數(shù),0<γ、δ<1,當(dāng)γ一定時,隨著δ的減少,用戶會高估小概率事件,對損失賦予的權(quán)重更高,即是風(fēng)險(xiǎn)偏好的;當(dāng)δ一定時,隨著γ的減少,則對收益賦予的權(quán)重更高,風(fēng)險(xiǎn)態(tài)度則為風(fēng)險(xiǎn)規(guī)避.

對于參數(shù)α、β、λ、γ、δ的取值問題,相關(guān)的學(xué)者進(jìn)行了研究得出多種取值情況,本文中的實(shí)驗(yàn)?zāi)J(rèn)選用PT方法提出者提供的參數(shù)值α=0.88、β=0.88、λ=2.25、γ=0.61、δ=0.69[5].

根據(jù)已得出的收益、損失的價值V(+)和V(-),以及相應(yīng)的概率權(quán)重π(+)和π(-).通過式(11)-式(12)計(jì)算得出前景值V并規(guī)范化為V*.

(11)

(12)

最后,依據(jù)簡單加權(quán)原則以及QoS屬性權(quán)重ω,計(jì)算得出綜合前景值U,計(jì)算公式如下所示.

(13)

綜上所述,在QoS不確定條件下,基于前景理論的Web服務(wù)選擇方法步驟如下:

步驟1.根據(jù)不確定QoS信息,與參照點(diǎn)對比,根據(jù)式(3)-式(6)處理后得到風(fēng)險(xiǎn)收益矩陣G和風(fēng)險(xiǎn)損失矩陣L.

步驟2.根據(jù)經(jīng)驗(yàn)分布函數(shù)及式(1)-式(2)對不確定QoS信息進(jìn)行描述.

步驟3.根據(jù)前景理論及式(7)-式(12)計(jì)算得出前景值V并規(guī)范化為V*.

步驟4.根據(jù)式(13),計(jì)算得出綜合前景值U.

步驟5.根據(jù)步驟4得到的綜合前景值U大小并對所有的服務(wù)進(jìn)行排序,綜合前景值Ui越大,服務(wù)si為最優(yōu)選擇.

5 實(shí)驗(yàn)與分析

為驗(yàn)證本文服務(wù)選擇模型的合理性和有效性,本文實(shí)驗(yàn)使用WS-DREAM數(shù)據(jù)集[18],其包括5825個分布在73個國家的實(shí)際Web服務(wù)的1974675個事務(wù)記錄,其中包括響應(yīng)時間和吞吐量兩個QoS屬性真實(shí)數(shù)據(jù).實(shí)驗(yàn)環(huán)境是CPU為Intel Core i3-4130u,3.4GHz,內(nèi)存為8GB,操作系統(tǒng)為Windows 10,利用Matlab實(shí)現(xiàn)本文方法.

5.1 有效性分析

5.1.1 有效性驗(yàn)證

本實(shí)驗(yàn)的目的是驗(yàn)證本方法的有效性.我們選擇E-V模型(Mean-Variance Model均值-方差)[19]和TOPSIS[20](Technique for Order Preference by Similarity to an Ideal Solution,逼近理想解)方法作為對比方法,通過EMV[21](expected monetary value)、EOL[22](expected opportunity loss)和EUV[23](expected utility value)三個準(zhǔn)則進(jìn)行有效性驗(yàn)證.

我們隨機(jī)選取50～300個Web服務(wù)信息,考慮到用戶需求這一因素對服務(wù)選擇的影響以及QoS屬性的表示形式為實(shí)數(shù)離散隨機(jī)變量形的情形,在實(shí)驗(yàn)中分別以二分位數(shù)、四分位數(shù)(上四分位數(shù)、下四分位數(shù))作為參照點(diǎn),判斷由PT方法選擇的最優(yōu)服務(wù)與TOPSIS方法、E-V模型選出的服務(wù)是否滿足EMV、EOL、EUV三個準(zhǔn)則.

在本實(shí)驗(yàn)中,參考點(diǎn)變化對Web服務(wù)綜合前景值的影響如圖1所示.

圖1 參考點(diǎn)變化對Web服務(wù)綜合前景值的影響Fig.1 Impact of reference point changes on the comprehensive prospect value of Web services

由圖1(a)-圖1(c)可分別直觀地看出,當(dāng)參照點(diǎn)取值不變時,隨候選服務(wù)數(shù)量的增加,相較于TOPSIS和E-V模型選擇的服務(wù),通過PT方法選擇的服務(wù)滿足EMV、EOL、EUV三個準(zhǔn)則的百分比最高;當(dāng)變化參照點(diǎn)取值時,例如圖1(a)所示,保持候選服務(wù)數(shù)量相同時,相較于E-V模型和TOPSIS方法選擇的服務(wù),由PT方法選擇的服務(wù)滿足三個準(zhǔn)則的百分比最高.

因此,由圖1(a)-圖1(c)可以得出:在變化參照點(diǎn)取值的情況下,并隨服務(wù)數(shù)量的增加,相較于TOPSIS和E-V模型選擇的服務(wù),通過PT方法選擇的服務(wù)更滿足EMV、EOL、EUV三個準(zhǔn)則.說明針對Web服務(wù)在QoS不確定下的選擇具有風(fēng)險(xiǎn)性這一情況,并且考慮用戶需求這一因素,PT方法的選擇結(jié)果比起E-V模型和TOPSIS方法的選擇結(jié)果更加有效.

5.1.2 運(yùn)行效率

在不同樣本規(guī)模下,記錄系統(tǒng)每次進(jìn)行服務(wù)選擇的運(yùn)行時間(單位:s),運(yùn)行結(jié)果如圖2所示.

圖2 運(yùn)行時間Fig.2 Response time

當(dāng)Web服務(wù)數(shù)量少于50時,PT方法、TOPSIS方法和E-V模型的運(yùn)行時間并無太大差別.當(dāng)服務(wù)數(shù)量超過100時,PT方法與TOPSIS方法的運(yùn)行時間差距較小;與E-V模型相比,雖然本方法的運(yùn)行時間較長,但本方法是在不確定QoS條件下考慮用戶需求和風(fēng)險(xiǎn)態(tài)度兩個因素的Web服務(wù)選擇,所以本方法的選擇過程比其他兩種方法消耗時間長.

5.1.3 局部服務(wù)選擇對全局服務(wù)選擇的影響

本實(shí)驗(yàn)的目的是分析由PT方法選出的局部最優(yōu)服務(wù)對全局服務(wù)組合的影響.在相同活動數(shù)目的情況下,調(diào)整每個活動的候選服務(wù)數(shù)目對組合服務(wù)的成功率的影響.以旅游業(yè)務(wù)集成[24]為例,每一活動分別有10,20,30,40,50個候選服務(wù),每種情況進(jìn)行20次平均計(jì)算,隨著候選服務(wù)數(shù)目的變化,構(gòu)造服務(wù)組合成功率的趨勢如圖3所示.

圖3 候選服務(wù)數(shù)目對服務(wù)組合成功率的影響Fig.3 Influence of number of candidate services on success rate of service composition

圖3表明當(dāng)候選服務(wù)數(shù)在10～50之間變化時,隨著候選服務(wù)數(shù)的增多,組合成功率變化平穩(wěn).并且由PT方法選出的最優(yōu)服務(wù)與TOPSIS方法、E-V模型選出的服務(wù)相比,服務(wù)組合成功率明顯,這表明本文方法選出的局部最優(yōu)選擇對服務(wù)組合的求解與其余兩種方法相比是有效的.

5.2 參數(shù)敏感性分析

本實(shí)驗(yàn)的目的是分析風(fēng)險(xiǎn)態(tài)度參數(shù)α、β、λ、γ、δ對服務(wù)選擇的影響.在QoS不確定條件下的服務(wù)選擇過程中,若用戶需要根據(jù)自己的風(fēng)險(xiǎn)態(tài)度選取某些候選服務(wù),就可以通過調(diào)整α、β、λ、γ、δ的取值,從而改變相應(yīng)服務(wù)的綜合前景值及排序,最終選取符合用戶選擇服務(wù)時的風(fēng)險(xiǎn)態(tài)度.

依據(jù)文獻(xiàn)[4,5]和文獻(xiàn)[25]提供的參數(shù)取值,實(shí)驗(yàn)隨機(jī)選取8個候選服務(wù)信息,權(quán)重分別設(shè)定為0.5、0.5,分別計(jì)算參數(shù)α、β、λ、γ、δ在不同取值下的綜合前景值,經(jīng)過多次實(shí)驗(yàn)取其平均結(jié)果,并將結(jié)果變化列于圖4(a)-圖4(e).

圖4 參數(shù)值變化對Web服務(wù)綜合前景值的影響Fig.4 Influence of parameter value change on the comprehensive prospect value of Web services

當(dāng)參數(shù)γ、δ取值不變時,將參數(shù)α值依次取(0.25,0.54,0.88,0.91)、λ值依次取(0.25,0.54,0.88)、β值依次取(1,1.5,2,2.25,2.5,3,3.5,4,5,6,12)做對比,對比結(jié)果如圖4(a)-圖4(c)所示.

當(dāng)參數(shù)α、β、λ取值不變時,將參數(shù)γ值依次取{0.25,0.61,0.74,0.81,0.91}、δ值依次取{0.25,0.69,0.74,0.91}做對比,對比結(jié)果如圖4(d)-圖4(e)所示.

從圖4(a)-圖4(e)可以看出,隨著α、β、λ、γ、δ取值的增大,一方面,各個服務(wù)的綜合前景值產(chǎn)生明顯的變化;另一方面,α、β、γ、δ、λ的取值對候選服務(wù)排序有一定的影響,但影響微小,這種影響主要體現(xiàn)在的s1和s3的排序上.當(dāng)α、β、λ的取值變化導(dǎo)致風(fēng)險(xiǎn)偏好、風(fēng)險(xiǎn)規(guī)避程度增強(qiáng)時,s1優(yōu)于s3;反之,s3優(yōu)于s1.當(dāng)δ一定時,隨γ值的減少時,對收益賦予的權(quán)重會高估小概率事件,用戶態(tài)度是風(fēng)險(xiǎn)規(guī)避;當(dāng)γ一定時,隨δ值的減少時,對損失賦予的權(quán)重會高估小概率事件,用戶態(tài)度是風(fēng)險(xiǎn)偏好.綜上,α、β、λ、γ、δ取值的變化不會影響候選服務(wù)中最優(yōu)和最差服務(wù)的排序,但會影響中間服務(wù)的排序,其綜合前景值會隨α、β、λ、γ、δ取值的變化明顯波動,因此α、β、λ、γ、δ能夠顯著地體現(xiàn)風(fēng)險(xiǎn)態(tài)度因素對于Web服務(wù)綜合前景值的影響.

6 總 結(jié)

本文針對基于不確定QoS的Web服務(wù)選擇問題,旨在考量用戶QoS需求和選擇服務(wù)時的風(fēng)險(xiǎn)態(tài)度對最優(yōu)服務(wù)選擇的影響,提出了一種基于前景理論的不確定QoS感知的Web服務(wù)選擇方法.該方法首先根據(jù)Web服務(wù)的QoS信息得出用戶需求作為參照點(diǎn),考慮用戶風(fēng)險(xiǎn)態(tài)度,再通過前景理論得出候選服務(wù)的排序并進(jìn)行選擇,為在不確定QoS條件下的Web服務(wù)選擇提供了一種新的思路.