基于動(dòng)態(tài)信任的最優(yōu)云服務(wù)選擇算法

王宗江，楊淑慧

(1．中原工學(xué)院 計(jì)算機(jī)學(xué)院，河南 鄭州450007;2．鄭州大學(xué) 水利與環(huán)境學(xué)院，河南 鄭州450001)

0 引言

云計(jì)算是近年來的一個(gè)研究熱點(diǎn)［1］． 從云計(jì)算的權(quán)威定義可以看出［2］，服務(wù)(也是一種資源)管理是云計(jì)算的核心問題．在服務(wù)管理中，通常有兩個(gè)角色:服務(wù)提供者(Service Provider，SP)和服務(wù)消費(fèi)者(Service Consumption，SC)．

當(dāng)前，由于不同云計(jì)算商的服務(wù)質(zhì)量存在較大差異，使得用戶在服務(wù)選擇的過程中也存在著較大的矛盾．一方面由于缺乏專業(yè)知識(shí)，服務(wù)消費(fèi)者不知道有哪些滿足自己需求的服務(wù)提供者;另一方面服務(wù)提供者則不知道有哪些服務(wù)消費(fèi)者需要服務(wù)，需要什么種類的服務(wù)．此外，服務(wù)提供者和服務(wù)消費(fèi)者都存在惡意非合作(即滿足要求，卻不執(zhí)行)情形．服務(wù)提供者從本身角度考慮，只選擇能夠獲得較高收益的消費(fèi)者，這樣會(huì)大大增加其它服務(wù)消費(fèi)者的等待時(shí)間;而服務(wù)消費(fèi)者為了減少自己的等待時(shí)間，則會(huì)發(fā)出多個(gè)服務(wù)請(qǐng)求，最后只選擇一個(gè)最快到達(dá)的服務(wù)，從而影響了服務(wù)提供者的整體利用率，對(duì)社會(huì)資源造成了極大的浪費(fèi)．

現(xiàn)實(shí)社會(huì)中，常采用服務(wù)的最優(yōu)化方法來解決服務(wù)選擇問題，即利用各種優(yōu)化方法為服務(wù)消費(fèi)者自動(dòng)尋找到最優(yōu)的服務(wù)提供者． 這里的優(yōu)化目標(biāo)包括距離最近、花費(fèi)最小等［1-2］．但是對(duì)于服務(wù)提供者和服務(wù)消費(fèi)者出現(xiàn)的惡意非合作情況，當(dāng)前研究都沒有提出有效的解決方法．

筆者針對(duì)服務(wù)選擇中存在的問題，提出了基于動(dòng)態(tài)信任的最優(yōu)服務(wù)選擇算法，其核心思想為:為服務(wù)消費(fèi)者和服務(wù)提供者分別建立動(dòng)態(tài)信任評(píng)估方法;為每一個(gè)服務(wù)消費(fèi)者提出的服務(wù)請(qǐng)求，找到最優(yōu)的服務(wù)提供者;當(dāng)前服務(wù)完成后，根據(jù)完成情況，對(duì)服務(wù)提供者和服務(wù)消費(fèi)者的信任值進(jìn)行動(dòng)態(tài)更新;將更新后的最新信任值應(yīng)用到下一個(gè)服務(wù)選擇過程中．實(shí)驗(yàn)結(jié)果表明，該方法不但能夠?yàn)楸姸喾?wù)消費(fèi)者和服務(wù)提供者提供較優(yōu)的匹配，還能有效改變當(dāng)前服務(wù)消費(fèi)者和服務(wù)提供者的惡意非合作情形．

1 基于動(dòng)態(tài)信任的最優(yōu)服務(wù)選擇模型框架

根據(jù)目前關(guān)于SLA 信任的相關(guān)研究，結(jié)合現(xiàn)有技術(shù)等［3-6］，筆者設(shè)計(jì)出了基于動(dòng)態(tài)信任的最優(yōu)服務(wù)選擇模型框架，如圖1 所示．

該模型框架包括3 個(gè)對(duì)象:服務(wù)消費(fèi)者、服務(wù)提供者和軟件應(yīng)用商．

服務(wù)消費(fèi)者具有3 個(gè)功能:申請(qǐng)服務(wù)封裝，主要用來封裝以SLA 表示的服務(wù)申請(qǐng)和它自身的位置信息(x，y);信息收發(fā)，控制用于向軟件應(yīng)用商發(fā)送服務(wù)請(qǐng)求和軟件應(yīng)用商的交互信息;信息顯示，用于顯示服務(wù)消費(fèi)者和服務(wù)提供者的動(dòng)態(tài)位置信息和服務(wù)提供者所提供的服務(wù)信息．

服務(wù)提供者具有3 個(gè)功能:提供服務(wù)封裝，主要用來封裝以SLA 表示的服務(wù)申請(qǐng)和它自身的位置信息(x，y);信息收發(fā)控制，用于向軟件應(yīng)用商發(fā)送提供的各種類型的服務(wù)和和軟件應(yīng)用商的交互信息;信息顯示，用于顯示服務(wù)消費(fèi)者和服務(wù)提供者的動(dòng)態(tài)位置信息和服務(wù)消費(fèi)者所提供的服務(wù)申請(qǐng)信息．

軟件應(yīng)用商具有3 個(gè)功能:信息收發(fā)控制，用于接收服務(wù)消費(fèi)者的服務(wù)請(qǐng)求信息和服務(wù)提供者的服務(wù)信息;信息存儲(chǔ)，用于將接收信息保存下來，以供處理模塊使用;信息處理包括兩個(gè)功能，一個(gè)是利用保存的每次交易信息，計(jì)算服務(wù)消費(fèi)者和服務(wù)提供者的當(dāng)前動(dòng)態(tài)信任值． 另外一個(gè)功能是利用計(jì)算得到的動(dòng)態(tài)信任值，選擇出最優(yōu)服務(wù)．

圖1 基于動(dòng)態(tài)信任的最優(yōu)服務(wù)選擇模型框架Fig．1 Optimal service selection framework based on dynamic trust

服務(wù)消費(fèi)者通過該模型選擇服務(wù)提供者的具體流程如下(圖2)．

(1)服務(wù)提供者首先將自己的服務(wù)在軟件應(yīng)用商注冊(cè)，服務(wù)信息包括:服務(wù)提供者ID，服務(wù)ID，服務(wù)類型，服務(wù)內(nèi)容，對(duì)應(yīng)的SLA 及位置信息等．

(2)服務(wù)消費(fèi)者在軟件應(yīng)用商注冊(cè)，信息包括:服務(wù)消費(fèi)者ID，基本信息等．

(3)服務(wù)消費(fèi)者向軟件應(yīng)用商發(fā)送申請(qǐng)服務(wù)，請(qǐng)求信息包括服務(wù)類型、服務(wù)內(nèi)容等．

(4)軟件應(yīng)用商首先將請(qǐng)求信息保存下來，然后計(jì)算動(dòng)態(tài)信任值，進(jìn)行最優(yōu)服務(wù)選擇，然后向選擇的服務(wù)提供者發(fā)送服務(wù)申請(qǐng)．

(5)服務(wù)提供者得到服務(wù)請(qǐng)求，進(jìn)行服務(wù)響應(yīng)，發(fā)送信號(hào)給服務(wù)消費(fèi)者．

(6)本次服務(wù)結(jié)束，服務(wù)消費(fèi)者支付費(fèi)用給服務(wù)提供者，并對(duì)服務(wù)提供者的服務(wù)進(jìn)行評(píng)價(jià)．

(7)服務(wù)提供者獲得本次服務(wù)費(fèi)用，并對(duì)服務(wù)消費(fèi)者進(jìn)行評(píng)價(jià)．

圖2 服務(wù)選擇場(chǎng)景數(shù)據(jù)流Fig．2 Data flow of service selection

2 動(dòng)態(tài)信任值計(jì)算與基于動(dòng)態(tài)信任的最優(yōu)服務(wù)選擇算法

在本節(jié)給出了動(dòng)態(tài)信任值的計(jì)算方法［7-8］，以及利用該信任值的最優(yōu)服務(wù)選擇算法．

2．1 動(dòng)態(tài)信任值計(jì)算

2．1．1 服務(wù)提供者的動(dòng)態(tài)信任值

在每次交易結(jié)束后，計(jì)算本次交易的信任值，服務(wù)提供者的信任值由3 部分構(gòu)成:

(1)服務(wù)提供者自身評(píng)價(jià)(SPe)． SPe =QoS完成情況的歸一化，其值的范圍為［0，1］．

(2)應(yīng)用商評(píng)價(jià)(Ae)． 正常情況下:Ae = 服務(wù)單價(jià)×服務(wù)時(shí)間．

惡意非合作情況下:Ae = -服務(wù)單價(jià)×服務(wù)時(shí)間

(3)服務(wù)消費(fèi)者評(píng)價(jià)(SCe)．SCe =服務(wù)消費(fèi)者打分的歸一化，其值的范圍為［0，1］．

服務(wù)提供者動(dòng)態(tài)信任值:Ae + 100·SPe +100·SCe．

最新信任值:以往信任值+本次交易信任值．

2．1．2 服務(wù)消費(fèi)者的動(dòng)態(tài)信任值

服務(wù)消費(fèi)者的信任值由兩部分構(gòu)成．

(1)服務(wù)提供者評(píng)價(jià)(SPe)．SPe 為服務(wù)提供者打分的歸一化，其值的范圍為［0，1］．

(2)應(yīng)用商評(píng)價(jià)(Ae)． 正常情況下:Ae = 服務(wù)單價(jià)×服務(wù)時(shí)間;惡意非合作情況下:Ae= -服務(wù)單價(jià)×服務(wù)時(shí)間．

服務(wù)消費(fèi)者動(dòng)態(tài)信任值:Ae+100·SPe．

最新信任值:以往信任值+本次交易信任值．

2．2 基于動(dòng)態(tài)信任的最優(yōu)服務(wù)選擇算法

假定最優(yōu)服務(wù)是指該服務(wù)消費(fèi)者距離最近的服務(wù)提供者所提供的服務(wù)． 基于動(dòng)態(tài)信任的最優(yōu)服務(wù)選擇算法DTOS 如下．

(1)服務(wù)消費(fèi)者欲獲得某種服務(wù)，首先向軟件應(yīng)用商提出服務(wù)請(qǐng)求，其中每個(gè)服務(wù)請(qǐng)求包括用SLA 表示的服務(wù)和所在位置的坐標(biāo)(x，y)．

(2)軟件應(yīng)用商接到請(qǐng)求后，將當(dāng)前申請(qǐng)服務(wù)的所有服務(wù)消費(fèi)者放入到隊(duì)列Qsc 中．

(3)軟件應(yīng)用商將當(dāng)前注冊(cè)的服務(wù)提供者放入到隊(duì)列Qsp 中，其中每個(gè)服務(wù)提供者包括用SLA 表示的服務(wù)和所在位置的坐標(biāo)(x，y)．

(4)對(duì)隊(duì)列Qsc 進(jìn)行k-means 聚類，得到N 個(gè)Cluster，記為C1，C2，…，Cn．

(5)使用上面的N 個(gè)質(zhì)心，將Qsp 分配到N個(gè)Cluster 中．

(6)將C1中的服務(wù)請(qǐng)求按照動(dòng)態(tài)信任值進(jìn)行降序排序，根據(jù)C1中的第一個(gè)服務(wù)請(qǐng)求SR1，將C1中的服務(wù)提供者按照最優(yōu)服務(wù)降序排列Qsp1．

(7)將C1中的第一個(gè)服務(wù)請(qǐng)求SR1發(fā)送到Qsp1中的第一個(gè)服務(wù)提供者SP1，等待SP1回應(yīng)．

(8)如果SP1回應(yīng)，繼續(xù)分配下一個(gè)服務(wù)．

(9)否則，延遲時(shí)間r 秒后，將請(qǐng)求SR1發(fā)送到Qsp1中的第二個(gè)服務(wù)提供者SP2．

(10)當(dāng)C1中的第一個(gè)服務(wù)請(qǐng)求SR1分配完后，分配下一個(gè)服務(wù)請(qǐng)求SR2．

(11)當(dāng)C1中的所有服務(wù)請(qǐng)求分配完后，回到步驟6 進(jìn)行循環(huán)，繼續(xù)下一個(gè)Cluster C2，直到結(jié)束．

3 實(shí)驗(yàn)分析

筆者使用了CloudSim 框架對(duì)所提出的算法進(jìn)行實(shí)驗(yàn)和評(píng)估．CloudSim 是一個(gè)由墨爾本大學(xué)Buyya 教授領(lǐng)導(dǎo)的研究小組開發(fā)、能夠?qū)υ朴?jì)算環(huán)境進(jìn)行建模和模擬、可以擴(kuò)展的模擬工具開放源碼軟件［9］． 在實(shí)驗(yàn)中，擴(kuò)展Datacenter 類，實(shí)現(xiàn)了自定義的調(diào)度策略，完成了對(duì)調(diào)度算法的模擬，并進(jìn)行了相關(guān)測(cè)試和實(shí)驗(yàn)． 其中的服務(wù)提供者參數(shù)設(shè)置如表1 所示，服務(wù)消費(fèi)者參數(shù)設(shè)置如表2所示．

3．1 隨交易次數(shù)增加不同類型信任值的變化情況

將服務(wù)消費(fèi)者和服務(wù)提供者的信任分為3類:完全可信、可信及不可信［10］，信任值為T，Tmax≤T≤1:表示“完全可信”，完全可信服務(wù)提供者所提供的服務(wù)是真實(shí)可信服務(wù)，完全可信服務(wù)消費(fèi)者履行交易也是真實(shí)可信的，它們出現(xiàn)惡意非合作情況非常少．

表1 服務(wù)提供者參數(shù)設(shè)置Tab．1 Parameters of service providers

表2 服務(wù)消費(fèi)者參數(shù)設(shè)置Tab．2 Parameters of service consumptions

Tmin≤T≤Tmax:表示“可信”，用戶對(duì)可信服務(wù)提供者提供的服務(wù)滿意度稍差，但能夠一直提供真實(shí)可信的服務(wù)，服務(wù)消費(fèi)者履行交易也是基本可信的，它們出現(xiàn)惡意非合作情況較少．

0≤T≤Tmin:表示“不可信”，不可信服務(wù)提供者很少提供真實(shí)可信的服務(wù)，不可信服務(wù)消費(fèi)者履行交易也不是真實(shí)可信的，兩者共同的特征是會(huì)經(jīng)常出現(xiàn)惡意非合作情況．

在仿真實(shí)驗(yàn)中，假設(shè)Tmin=0．3，Tmax=0．8，即信任值在［0．8，1．0］時(shí)為完全可信，在［0．3，0．8］時(shí)為可信，在［0，0．3］時(shí)為不可信．定義3 類服務(wù)提供者的比例分別為20%，70%，10%．各類服務(wù)提供者的信任值變化如圖3 所示，其中橫坐標(biāo)表示交易次數(shù)，縱坐標(biāo)表示信任值．

從圖3 可以看出，完全可信和可信服務(wù)提供者由于一直提供真實(shí)可信的服務(wù)，信任值隨交易次數(shù)的增加而呈上升趨勢(shì)． 不可信服務(wù)提供者由于一直提供不可信服務(wù)，信任值下降很快．3 類服務(wù)消費(fèi)者的信任值變化和服務(wù)提供者信任值變化基本一致．

3．2 隨交易次數(shù)增加不同選擇策略的服務(wù)提供者的服務(wù)利用率

對(duì)3 種服務(wù)選擇策略進(jìn)行比較，隨機(jī)服務(wù)選擇策略、基于信任的服務(wù)選擇策略和基于動(dòng)態(tài)信任的最優(yōu)服務(wù)選擇策略．

圖3 3 類服務(wù)提供者的信任值隨交易次數(shù)的變化Fig．3 Changes of transaction times of three types service provider trust valur

隨機(jī)服務(wù)選擇策略:軟件應(yīng)用商在滿足服務(wù)消費(fèi)者基本功能的服務(wù)提供者列表中，隨機(jī)選擇一個(gè)服務(wù)提供者作為服務(wù)提供者．

基于信任的服務(wù)選擇策略:軟件應(yīng)用商在滿足服務(wù)消費(fèi)者基本功能的服務(wù)提供者列表中，選擇信任值最高的服務(wù)提供者作為服務(wù)提供者．

基于動(dòng)態(tài)信任的最優(yōu)服務(wù)選擇策略:軟件應(yīng)用商在滿足服務(wù)消費(fèi)者基本功能的服務(wù)提供者列表中，選擇動(dòng)態(tài)信任值高的最優(yōu)服務(wù)提供者作為服務(wù)提供者．服務(wù)提供者的服務(wù)利用率為服務(wù)使用時(shí)間和24 h 的比值．在此假定服務(wù)提供者提供的服務(wù)是全天24 h 一直可用．

3 種不同服務(wù)策略的利用率變化如圖4 所示，其中橫坐標(biāo)表示交易次數(shù)，縱坐標(biāo)表示服務(wù)利用率．從圖4 可以看出，隨機(jī)服務(wù)選擇策略的利用率非常低．其他兩種服務(wù)策略和隨機(jī)服務(wù)選擇策略相比，效率提高許多．主要是隨機(jī)服務(wù)選擇算法不考慮是否滿足服務(wù)，造成效率非常低．

3．3 隨交易次數(shù)增加不同選擇策略的服務(wù)消費(fèi)者的等待時(shí)間

服務(wù)消費(fèi)者的等待時(shí)間是指服務(wù)消費(fèi)者發(fā)出服務(wù)申請(qǐng)到確認(rèn)服務(wù)的過程所花費(fèi)的時(shí)間．3 種不同服務(wù)策略的服務(wù)消費(fèi)者等待時(shí)間變化如圖5 所示．從圖5 可以看出，隨機(jī)服務(wù)選擇策略的等待時(shí)間圍繞一個(gè)均值(10 s)波動(dòng)． 另外兩種服務(wù)策略的服務(wù)消費(fèi)者等待時(shí)間隨著交易次數(shù)的增加逐漸降低，其中基于動(dòng)態(tài)信任最優(yōu)服務(wù)選擇算法下降的更加明顯． 主要是它不但考慮了動(dòng)態(tài)信任，還考慮了最近距離，減少了服務(wù)傳輸時(shí)間．

由圖4 和圖5 可以看出，基于動(dòng)態(tài)信任的最優(yōu)服務(wù)選擇算法不但使服務(wù)提供者獲得了較高的利用率，還使服務(wù)消費(fèi)者獲得了較短的等待時(shí)間．而且，由于對(duì)兩者出現(xiàn)的惡意非合作情形進(jìn)行了懲罰．服務(wù)消費(fèi)者和服務(wù)提供者為了自己的利益，都會(huì)減少惡意非合作情形．

圖4 不同選擇策略隨交易次數(shù)增加時(shí)服務(wù)提供者服務(wù)利用率的變化情況Fig．4 Changes of transactions times with different service selection strategy of service provide utility

圖5 不同選擇策略隨交易次數(shù)增加時(shí)服務(wù)消費(fèi)者等待時(shí)間的變化情況Fig．5 Changes of transactions times with different service selection strategy of service consumption waiting time changes

4 結(jié)論

隨著云計(jì)算的快速發(fā)展，國(guó)內(nèi)外出現(xiàn)了大量的云服務(wù)提供商． 如何為每個(gè)服務(wù)消費(fèi)者快速找到合適的服務(wù)提供者是一個(gè)難題． 筆者提出了基于動(dòng)態(tài)信任的最優(yōu)服務(wù)選擇模型． 它不但能夠?yàn)榉?wù)消費(fèi)者和服務(wù)提供者提供最優(yōu)匹配，還能有效減少兩者出現(xiàn)的惡意非合作情形．如實(shí)驗(yàn)所示，本算法既為服務(wù)提供者提供了較高利用率，又使得服務(wù)消費(fèi)者獲得了較短的等待時(shí)間．

筆者的目標(biāo)是將本算法應(yīng)用到實(shí)際應(yīng)用中．其中，本算法動(dòng)態(tài)信任中使用的權(quán)重是固定值，將來考慮使用更符合實(shí)際的值．此外，將充分利用軟件應(yīng)用商存儲(chǔ)的服務(wù)消費(fèi)者和服務(wù)提供者交易信息，為兩者提供更好的服務(wù)．例如可以為服務(wù)提供者預(yù)先提示較常用的服務(wù)消費(fèi)者服務(wù)，減少不常用的服務(wù)，從而提高服務(wù)利用率．

［1］ 林偉偉，齊德昱．云計(jì)算資源調(diào)度研究綜述［J］． 計(jì)算機(jī)科學(xué)，2012，39(10):1 -10．

［2］ LIU Liang，WANG Hao，LIU Xue，et al． Green-Cloud:a new architecture for green data center［C］∥Proceedings of the 6thInternational conference Industry Session on Autonomic Computing and Communicaitons industry Session． New York:ACM，2009:29 -38．

［3］ BUYYA R，GRAG S，CALHEIROS R． SLA -oriented resource provisioning for cloud computing:challenges，architecture，and solutions［C］∥Proceedings of the 2011 IEEE International Conference on Cloud and Service Computing． Washington D C:IEEE，2009:1-10．

［4］ VAN H N，TRAN F D，MENAUD J M． Sla-aware virtual resource management for cloud infrastructures［C］∥Ninth IEEE International Conference on Computer and Information Technology． Xiamen:IEEE，2009:357 -362．

［5］ WU Lin-lin，GARG S，BUYYA R． SLA-based resource allocation for software as a service provider(SaaS)in cloud computing environments［C］∥11th IEEE/ACM International Symposium on Cluster，Cloud and Grid Computing． Newport Beach:IEEE，2011:195 -204．

［6］ BlAZE M，F(xiàn)EIGENBAUM J，Lacy J． Decentralized trust management［C］∥Proceedings of IEEE Symposium on Security and Privacy．Oakland:IEEE，1996:164-173 ．

［7］ 胡春華，羅新星，王四春，等．云計(jì)算環(huán)境下基于信任推理的服務(wù)評(píng)價(jià)方法［J］． 通信學(xué)報(bào)，2011，32(12):72 -81．

［8］ 胡春華，陳曉紅，吳敏，等．云計(jì)算中基于SLA 的服務(wù)可信協(xié)商與訪問控制策略［J］．中國(guó)科學(xué):信息科學(xué)，2012，42(3):314 -332．

［9］ CALHEIROS R，RANJAN R，ANTON B，et al．CloudSim:a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms［J］． Software:Practice and Experience，2011，41(1):23 -50．

［10］杜瑞忠，田俊峰，張煥國(guó)．基于信任和個(gè)性偏好的云服務(wù)選擇模型［J］．浙江大學(xué)學(xué)報(bào):工學(xué)版，2013，47(1):53 -61．