馬治杰 臺(tái)憲青 劉晶花 陳大鵬

1(中國科學(xué)院微電子研究所 北京 100000) 2(江蘇物聯(lián)網(wǎng)研究發(fā)展中心 江蘇 無錫 214000) 3(中國科學(xué)院空天信息創(chuàng)新研究院蘇州研究院 江蘇 蘇州215121) 4(中國科學(xué)院空天信息創(chuàng)新研究院 北京 101407)

0 引 言

近年來，隨著Internet和云計(jì)算技術(shù)的飛速發(fā)展和廣泛應(yīng)用，越來越多功能相似而性能不同的軟件服務(wù)被部署于云平臺(tái)中，使得服務(wù)組合數(shù)量成指數(shù)增長。面對(duì)如此大量性能各異的服務(wù)，用戶無法有效地選擇其所需要的云服務(wù)。在這種情況下，根據(jù)服務(wù)的性能差異對(duì)其進(jìn)行評(píng)估和排序是一個(gè)很好的解決思路。

為了評(píng)估服務(wù)的價(jià)值，需要建立一個(gè)既包含評(píng)價(jià)指標(biāo)又包含指標(biāo)權(quán)重的評(píng)估模型，其中如何確定權(quán)重是建立模型的關(guān)鍵。當(dāng)前研究中計(jì)算各指標(biāo)權(quán)重的方法可分為三類：主觀權(quán)重法、客觀權(quán)重法和混合權(quán)重法[1]。主觀權(quán)重法簡單、直接，主要依據(jù)決策者和專家的知識(shí)經(jīng)驗(yàn)或偏好。例如，文獻(xiàn)[2]通過調(diào)查、收集數(shù)據(jù)，采用模糊邏輯法和層次分析法對(duì)不同的云服務(wù)提供商進(jìn)行排名。文獻(xiàn)[3]提出將AHP(Analytic Hierarchy Process)與TOPSIS(Technique for Order Preference by Similarity to Ideal Solution)相結(jié)合的方法解決多屬性決策問題。然而，此類方法具有很大程度的主觀隨意性，計(jì)算出的權(quán)重值可能并不準(zhǔn)確?？陀^權(quán)重法是依據(jù)一定的數(shù)學(xué)方法，對(duì)采集得到的樣本數(shù)據(jù)進(jìn)行分析計(jì)算，最終得到各指標(biāo)權(quán)重。其反映了決策問題本身潛在的性能和規(guī)律，與決策者的主觀偏好無關(guān)。例如，文獻(xiàn)[4]提出了一種基于各指標(biāo)之間依賴關(guān)系的模糊排序算法，每個(gè)指標(biāo)的權(quán)重值僅根據(jù)指標(biāo)之間的距離相關(guān)性確定，即各指標(biāo)的重要性體現(xiàn)為指標(biāo)的獨(dú)立性。文獻(xiàn)[5]基于變異系數(shù)(Coefficient of Variation，CV)法計(jì)算服務(wù)的客觀權(quán)重，但在服務(wù)評(píng)估領(lǐng)域，表示指標(biāo)離散程度的變異系數(shù)并不一定能夠真實(shí)反映指標(biāo)的重要性?；旌蠙?quán)重法可以看作是主觀方法和客觀方法的綜合。例如，文獻(xiàn)[6]提出一種基于TOPSIS的Web服務(wù)排序方法，通過使用熵權(quán)法并結(jié)合主觀權(quán)重得到綜合權(quán)重。文獻(xiàn)[7]融合了熵權(quán)法、模糊層次法、Skyline,以及PROMETHEE方法對(duì)服務(wù)進(jìn)行排序。

通過對(duì)已有方法的研究和分析，提出了一種新的客觀權(quán)重方法用于評(píng)估云環(huán)境下不同服務(wù)的價(jià)值，稱為基于逆變異系數(shù)的服務(wù)價(jià)值評(píng)估方法，簡稱Inv-CV(Inverse Coefficient of Variation)方法。該方法的思想原理是越重要的指標(biāo)往往在較優(yōu)的服務(wù)樣本中表現(xiàn)得更為穩(wěn)定，即在較優(yōu)的服務(wù)樣本中，指標(biāo)內(nèi)部數(shù)據(jù)差異越小，其權(quán)重分配值應(yīng)越大。該方法對(duì)今后的云服務(wù)選擇和個(gè)人服務(wù)推薦有一定的參考價(jià)值。

1 傳統(tǒng)CV方法介紹

1.1 CV方法

CV評(píng)估方法是一種典型的客觀權(quán)重方法，其可以在不考慮人為因素的情況下確定各個(gè)評(píng)價(jià)指標(biāo)的權(quán)重。CV方法通過計(jì)算各個(gè)指標(biāo)的平均值和標(biāo)準(zhǔn)差，可以得到相應(yīng)指標(biāo)的變異系數(shù)值。一般來說，系數(shù)值越大，指標(biāo)權(quán)重越大，反之亦然。

下面通過表1中的示例來說明CV方法如何計(jì)算每個(gè)指標(biāo)的權(quán)重。在表1中，假設(shè)存在n個(gè)具有相似功能、不同性能的服務(wù)樣本Si(1≤i≤n)，每個(gè)樣本包含m個(gè)評(píng)價(jià)指標(biāo)Qj(1≤j≤m)，也稱服務(wù)質(zhì)量(Quality of Service，QoS)指標(biāo)，其中dij表示服務(wù)Si關(guān)于指標(biāo)Qj的具體QoS數(shù)值。用ωj表示指標(biāo)Qj的權(quán)重，則ωj可通過以下四個(gè)步驟計(jì)算獲得。

表1 n個(gè)服務(wù)，m個(gè)評(píng)價(jià)指標(biāo)

(1)

步驟2計(jì)算各個(gè)評(píng)價(jià)指標(biāo)的標(biāo)準(zhǔn)差。用σj(1≤j≤m)表示指標(biāo)Qj的QoS值的標(biāo)準(zhǔn)差，則有：

(2)

步驟3計(jì)算各個(gè)評(píng)價(jià)指標(biāo)的變異系數(shù)。用xj(1≤j≤m)表示指標(biāo)Qj的變異系數(shù)，則有：

(3)

步驟4計(jì)算各個(gè)指標(biāo)的權(quán)重。用ωj(1≤j≤m)表示指標(biāo)Qj的權(quán)重，則有：

(4)

最后，根據(jù)每個(gè)服務(wù)的實(shí)際QoS值dij與對(duì)應(yīng)QoS評(píng)價(jià)指標(biāo)權(quán)重ωj，CV評(píng)估方法可以使用加權(quán)法來計(jì)算評(píng)估每個(gè)服務(wù)的價(jià)值。

1.2 CV方法的缺點(diǎn)

與主觀權(quán)重方法相比，盡管CV方法繼承了客觀權(quán)重方法的許多優(yōu)點(diǎn)，例如，減少人為干擾、權(quán)重計(jì)算簡單等，但在服務(wù)價(jià)值評(píng)估領(lǐng)域，依然存在以下兩個(gè)缺點(diǎn)。

(1) 權(quán)重計(jì)算存在誤差。在CV方法中，權(quán)重計(jì)算依賴于全部的樣本，所以其對(duì)樣本數(shù)據(jù)的可靠性、準(zhǔn)確性等的要求會(huì)很高。此外，變異系數(shù)法作為常用的多指標(biāo)評(píng)價(jià)方法，其原理更多的是強(qiáng)調(diào)指標(biāo)對(duì)評(píng)價(jià)對(duì)象的區(qū)分作用，即內(nèi)部數(shù)據(jù)的差異性越大，該指標(biāo)對(duì)評(píng)價(jià)對(duì)象的區(qū)分作用越大，權(quán)重的分配值也就越大。但在軟件服務(wù)價(jià)值評(píng)價(jià)領(lǐng)域，每個(gè)服務(wù)QoS指標(biāo)的離散程度并不一定能夠真實(shí)反映指標(biāo)的重要性。因此，直接將CV方法部署到服務(wù)價(jià)值評(píng)估中，其評(píng)估結(jié)果并不一定合理、可靠。

(2) 計(jì)算開銷大。在CV方法中，所有的樣本值，即所有服務(wù)的QoS指標(biāo)數(shù)據(jù)，都被用來計(jì)算權(quán)重值；且在樣本庫動(dòng)態(tài)變化時(shí)，必須重新計(jì)算權(quán)重和樣本分?jǐn)?shù)，這將帶來很大的計(jì)算開銷，同時(shí)降低了效率。

2 Inv-CV方法介紹

Inv-CV方法首先基于Pareto支配概念，使用快速非支配排序算法對(duì)所有樣本進(jìn)行分層，再按用戶指定比例確定較優(yōu)的樣本集——Pareto集。然后，為了合理、精確地計(jì)算指標(biāo)權(quán)重值，Inv-CV方法僅依據(jù)Pareto集中的樣本計(jì)算指標(biāo)的變異系數(shù)值，并最終得到權(quán)重值。與傳統(tǒng)CV方法不同，在Inv-CV中，每個(gè)指標(biāo)的變異系數(shù)值越小，其權(quán)重值越大。最后，Inv-CV采用加權(quán)法對(duì)所有服務(wù)進(jìn)行價(jià)值評(píng)估。下面以表1為例詳細(xì)介紹Inv-CV方法的評(píng)估過程。

Inv-CV方法的評(píng)估過程包括以下四個(gè)步驟：

步驟1利用以Pareto支配為基礎(chǔ)的快速非支配排序算法，對(duì)所有樣本進(jìn)行分層得到Pareto集。

如表1所示，由于每個(gè)服務(wù)樣本包含多個(gè)QoS指標(biāo)，為了從大量樣本中選擇較優(yōu)的樣本，Inv-CV方法首先根據(jù)每個(gè)QoS指標(biāo)的屬性性質(zhì)進(jìn)行區(qū)分。由文獻(xiàn)[10]可知，QoS指標(biāo)可分為兩類：積極型指標(biāo)和消極型指標(biāo)，前者表示對(duì)應(yīng)指標(biāo)的QoS值越大越好(例如，可靠性、安全性等)，而后者表示對(duì)應(yīng)指標(biāo)的QoS值越小越好(例如，響應(yīng)時(shí)間、CPU利用率等)。

基于以上定義分類，Inv-CV方法將采用以Pareto支配[8]概念為基礎(chǔ)的快速非支配排序算法對(duì)樣本進(jìn)行分層，并從所有樣本中根據(jù)用戶指定比例選取較優(yōu)的服務(wù)樣本，最終組成Pareto集。下面以表1中的任意兩個(gè)服務(wù)樣本Si和Sj為例，介紹Pareto支配關(guān)系。用QP和QN分別表示積極型和消極型屬性集合，Si若滿足以下三個(gè)條件，將被視為Si支配Sj：

條件1：對(duì)于積極型QoS屬性，如Qp∈QP，服務(wù)Si的QoS值dip不小于服務(wù)Sj的QoS值djp。即dip≥djp。

條件2：對(duì)于消極型QoS屬性，如Qn∈QN，服務(wù)Si的QoS值din不大于服務(wù)Sj的QoS值djn。即din≥djn。

條件3：對(duì)于所有的QoS屬性，至少存在一個(gè)屬性，使得Si的值優(yōu)于Sj的值，即dip>djp或din

當(dāng)滿足上述三個(gè)條件時(shí)，則可認(rèn)為Si支配Sj。最后，所有不被任何其他服務(wù)支配的服務(wù)樣本，組成Pareto最優(yōu)集。

快速非支配排序算法[9]對(duì)所有樣本按照支配關(guān)系進(jìn)行分層，其通過保存兩個(gè)量：支配個(gè)數(shù)np(支配個(gè)體p的所有個(gè)體的數(shù)量)、被支配個(gè)體集合Sp(所有被個(gè)體p支配的個(gè)體組成的集合)，降低時(shí)間復(fù)雜度，提高效率。

Inv-CV方法中由用戶參考總服務(wù)樣本數(shù)，指定Pareto集比例。以第一非支配層中服務(wù)為先，其次為第二非支配層，以此類推，按指定比例選取服務(wù)確定Pareto集。本文暫且對(duì)同一非支配層的服務(wù)樣本不作區(qū)分，隨機(jī)選取。

步驟2計(jì)算每個(gè)QoS指標(biāo)的權(quán)重值。

在傳統(tǒng)的CV方法中，每個(gè)QoS指標(biāo)的變異系數(shù)值和權(quán)值都是通過所有樣本來計(jì)算的。如式(4)所示，QoS指標(biāo)的變異系數(shù)值越大，對(duì)應(yīng)的權(quán)重值越大。然而，Inv-CV方法只根據(jù)Pareto集中的樣本計(jì)算每個(gè)QoS指標(biāo)的CV值和權(quán)值，且權(quán)值的計(jì)算方法不同。具體而言，QoS指標(biāo)的CV值越大，對(duì)應(yīng)的權(quán)重反而越小。主要原因是傳統(tǒng)CV方法是根據(jù)所有樣本中每個(gè)QoS評(píng)價(jià)指標(biāo)的離散情況來分配指標(biāo)的權(quán)重，QoS值離散程度越大，相應(yīng)權(quán)重的分配值也就越大；而Inv-CV方法根據(jù)Pareto集計(jì)算各指標(biāo)權(quán)重，則是考慮到越重要的指標(biāo)往往在較優(yōu)的服務(wù)樣本中表現(xiàn)得更為穩(wěn)定，其CV值越小，相應(yīng)的權(quán)值反而越大。

簡而言之，傳統(tǒng)的CV方法和本文所提出的Inv-CV方法之間的差異有以下兩點(diǎn)。一方面，每個(gè)QoS指標(biāo)的變異系數(shù)值的計(jì)算依賴于不同的樣本。另一方面，變異系數(shù)值與權(quán)重值之間的關(guān)系是完全相反的。因此，在Inv-CV方法中，為了計(jì)算每個(gè)QoS指標(biāo)的權(quán)重，首先采用傳統(tǒng)CV方法，對(duì)Pareto集中的服務(wù)樣本計(jì)算每個(gè)QoS指標(biāo)的CV值(即式(1)-式(3))。之后，每個(gè)QoS指標(biāo)的權(quán)重可以通過下式計(jì)算：

(5)

步驟3對(duì)每個(gè)QoS指標(biāo)進(jìn)行標(biāo)準(zhǔn)化處理。

由于每一個(gè)QoS評(píng)價(jià)指標(biāo)值的范圍和單位都不同，所以直接采用未經(jīng)過任何處理的原始QoS值會(huì)帶來一些不公平的因素。為解決該問題，本文將每個(gè)QoS評(píng)價(jià)指標(biāo)值進(jìn)行標(biāo)準(zhǔn)化處理。

(6)

式中：max(Qj)和min(Qj)分別表示所有樣本中評(píng)價(jià)指標(biāo)Qj的最大值和最小值。

步驟4評(píng)估服務(wù)的價(jià)值。

最后，評(píng)估每個(gè)服務(wù)的價(jià)值。用Vi表示服務(wù)Si的價(jià)值，結(jié)合式(5)和式(6)，則有：

(7)

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

本節(jié)將通過以下兩個(gè)實(shí)驗(yàn)來驗(yàn)證所提出的Inv-CV方法。

3.1 實(shí)驗(yàn)A

(1) 數(shù)據(jù)集。實(shí)驗(yàn)A選取公共可用數(shù)據(jù)集WS-DREAM[11]，該數(shù)據(jù)集包含5 825個(gè)真實(shí)Web服務(wù)，并記錄了響應(yīng)時(shí)間和吞吐量兩個(gè)評(píng)價(jià)指標(biāo)。本實(shí)驗(yàn)從WS-DREAM中選擇前200個(gè)服務(wù)，并假設(shè)這些服務(wù)具有相似的功能，但不同的性能。

(2) 實(shí)驗(yàn)結(jié)果與分析。表2和表3分別展示了當(dāng)設(shè)置Pareto集比例為5%({60,110,123,124,170,91,126,127,7,2})和比例為10%({60, 110, 123, 124, 170, 91, 126, 127, 7, 2, 89, 109, 111, 142, 147, 186, 140, 143, 146, 88})時(shí)的評(píng)價(jià)結(jié)果。根據(jù)該P(yáng)areto集，首先用式(5)確定每個(gè)QoS評(píng)價(jià)指標(biāo)(即響應(yīng)時(shí)間和吞吐量)的權(quán)重大小，然后根據(jù)式(6)-式(7)計(jì)算200個(gè)服務(wù)的評(píng)估結(jié)果。接著，將所有服務(wù)從最高分到最低分進(jìn)行排序。

表2 Pareto集的比例為5%時(shí)的評(píng)價(jià)結(jié)果

表3 Pareto集的比例為10%時(shí)的評(píng)價(jià)結(jié)果

從表2、表3中可以獲得以下三個(gè)發(fā)現(xiàn)。首先，表2和表3中的最高得分幾乎達(dá)到1分(滿分為1)。具體而言，在表2中，當(dāng)Pareto集設(shè)定比例為5%時(shí)，排名第一的得分為0.956，而在表3中，當(dāng)Pareto集設(shè)定比例為10%時(shí)，排名第一的得分為0.966。

其次，表2和表3中的服務(wù)評(píng)估結(jié)果略有差異。但這是合理的，因?yàn)椴煌腜areto集包含不同的服務(wù)，所以導(dǎo)致計(jì)算的權(quán)重也不同。因此，服務(wù)的相應(yīng)評(píng)估結(jié)果也隨之不同。這表明，Inv-CV方法的評(píng)價(jià)結(jié)果依賴于選擇的Pareto集，具有一定的合理性。

最后，定義準(zhǔn)確率為Pareto集中排名在評(píng)估結(jié)果對(duì)應(yīng)比例內(nèi)的服務(wù)的數(shù)量與Pareto集服務(wù)總數(shù)的比率。從表2和表3可以發(fā)現(xiàn)，表2中9個(gè)相同的服務(wù)編號(hào)，而表3中有18個(gè)相同的服務(wù)編號(hào)。也就是說，這兩種情況的準(zhǔn)確率都是90%。這表明Inv-CV方法是可行和準(zhǔn)確的。

3.2 實(shí)驗(yàn)B

(1) 數(shù)據(jù)集。實(shí)驗(yàn)B采用Cloud Harmony Report[12]中公開的云服務(wù)質(zhì)量數(shù)據(jù)。Cloud Harmony 公司公布的云服務(wù)質(zhì)量評(píng)估報(bào)告涵蓋了國內(nèi)外眾多云服務(wù)商實(shí)時(shí)測(cè)試的云服務(wù)質(zhì)量數(shù)據(jù)，從中選取國內(nèi)外6家云服務(wù)商的服務(wù)質(zhì)量數(shù)據(jù)對(duì)其進(jìn)行評(píng)價(jià)：Google Cloud Platform(CSP1)、Softlayer(CSP2)、Amazon Web Services(CSP3)、GoDaddy(CSP4)、Microsoft Azure(CSP5)、CloudFlare(CSP6)，并選取7個(gè)QoS指標(biāo)進(jìn)行服務(wù)評(píng)價(jià)：CPU性能(C1)、磁盤I/O的一致性(C2)、磁盤性能(C3)、內(nèi)存性能(C4)、云服務(wù)價(jià)格(C5)、云服務(wù)可用性(C6)、網(wǎng)絡(luò)性能(C7)[12]。各云服務(wù)商質(zhì)量數(shù)據(jù)如表4所示。

表4 云服務(wù)供應(yīng)商QoS數(shù)據(jù)集

(2) 實(shí)驗(yàn)結(jié)果及分析。本實(shí)驗(yàn)使用真實(shí)的云服務(wù)質(zhì)量數(shù)據(jù)進(jìn)行服務(wù)評(píng)價(jià)研究，由于數(shù)據(jù)集服務(wù)樣本數(shù)量較少，則選取Pareto最優(yōu)集代表Pareto集。本實(shí)驗(yàn)對(duì)比了Inv-CV方法、Entropy-TOPSIS評(píng)價(jià)方法[14]與PROMETHEE評(píng)價(jià)方法[15]。

表5展示了通過Inv-CV、Entropy-TOPSIS、PROMETHEE三種評(píng)價(jià)方法所計(jì)算出各指標(biāo)的權(quán)重值。其中，Inv-CV方法為本文所提出的方法，Entropy-TOPSIS采用了Entroy方法，PROMETHEE采用了FAHP方法。由各個(gè)方法的計(jì)算結(jié)果可以看出，由于C1指標(biāo)的QoS值離散程度最大，所以計(jì)算出的熵值最大，即Entropy-TOPSIS方法計(jì)算出的權(quán)重值最大，而Inv-CV方法考慮到最優(yōu)樣本中重要指標(biāo)值的穩(wěn)定性(即離散程度低)，因此計(jì)算出的權(quán)重值反而最小。相反，由于C6指標(biāo)的QoS值離散程度最小，所以對(duì)應(yīng)的熵值最小，因此Entropy-TOPSIS方法計(jì)算出的權(quán)重值最小，而Inv-CV方法計(jì)算出的權(quán)重值則最大。與此同時(shí)，由于PROMETHEE通過專家對(duì)指標(biāo)相對(duì)重要性的量化評(píng)判結(jié)果計(jì)算各個(gè)指標(biāo)的權(quán)重，所以每個(gè)指標(biāo)權(quán)重值近乎相似。

表5 不同評(píng)價(jià)方法下各評(píng)價(jià)指標(biāo)的權(quán)重值分布

圖1展示了Inv-CV方法、Entropy-TOPSIS評(píng)價(jià)方法、PROMETHEE評(píng)價(jià)方法的對(duì)比結(jié)果。根據(jù) Cloud Harmony 公司對(duì) 6 個(gè)云服務(wù)商的質(zhì)量評(píng)價(jià)等級(jí)評(píng)分分別為：CSP3(A+)、CSP6(A)、CSP2(A)、CSP1(A)、CSP5(B)、CSP4(B-)。通過圖1可以發(fā)現(xiàn)，Inv-CV方法的評(píng)價(jià)結(jié)果更加逼近Cloud Harmony的評(píng)價(jià)結(jié)果。因此，相比其他方法，Inv-CV方法會(huì)忽略掉因某指標(biāo)劣化帶來用戶體驗(yàn)變差的問題，進(jìn)而使得該指標(biāo)權(quán)重值變小，所以更適合云服務(wù)商之間的比較。該實(shí)驗(yàn)驗(yàn)證了本文提出的Inv-CV方法在云服務(wù)評(píng)價(jià)中的可行性和準(zhǔn)確性，可以為云用戶提供決策支持。

圖1 不同評(píng)價(jià)方法下云服務(wù)質(zhì)量排名

4 結(jié) 語

本文提出了一種 Inv-CV云服務(wù)價(jià)值評(píng)估方法。Inv-CV方法在充分分析服務(wù)指標(biāo)潛在規(guī)律的基礎(chǔ)上，通過計(jì)算客觀權(quán)重對(duì)服務(wù)進(jìn)行價(jià)值評(píng)價(jià)。與傳統(tǒng)CV方法不同，在Inv-CV中，只對(duì)代表較優(yōu)服務(wù)樣本的Pareto樣本集計(jì)算指標(biāo)的變異系數(shù)值，一個(gè)指標(biāo)的變異系數(shù)值越大，對(duì)應(yīng)的權(quán)重值越小，反之亦然。實(shí)驗(yàn)結(jié)果驗(yàn)證了該方法的可行性和準(zhǔn)確性。

在本文研究過程中，確定Pareto集的過程尚且粗糙，在未來的研究中，將嘗試對(duì)快速非支配排序算法中同一非支配層的服務(wù)樣本進(jìn)行區(qū)分。另外，Inv-CV方法可與主觀權(quán)重法結(jié)合，以更好地滿足用戶的偏好。