服務計算環境中收益優化的客戶選擇策略

劉蓉，李紅艷，楊長興

(1. 長沙醫學院 計算機系，湖南 長沙，410219；2. 中南大學 信息科學與工程學院，湖南 長沙，410083)

在服務計算環境中(或者云計算中)服務提供者將自身業務功能包裝為服務并對外發布，通常是服務代理(Service broker)將現有服務進行組合，并將組合后的整體提供服務給客戶(或稱服務消費者，Services consumption)，以實現服務價值的增值[1-3]。服務代理的一個最重要目標是如何實現效益的最大化，即通過提供增值服務來獲得最大的經濟效益。人們對服務選擇問題[4-10]進行了大量研究。早期的研究主要關注如何從可選的服務集合中選取QoS高的服務，其思想是：若選擇的服務QoS高，則服務組合后整體的QoS也較高[11-13]。Zeng等[14-15]通過把可選擇服務的QoS束參數線性加權轉化為1個單目標函數，轉化為1個值，從而避免了多維QoS間的比較問題。劉書雷等[6]提出了一種基于多目標遺傳算法的QoS全局最優服務動態選擇(Global optimal of dynamic Web services selection,GODSS)算法[6]。相關的研究工作還有動態規則算法、線性規則的方法[9]、基因算法[7]、PSO 算法、啟發式算法[8-10]等。在最近的研究中，可信服務組合的研究工作較多[3-7]。在對服務可信性的基礎上，對服務的QoS進行重新計算是一種較好的方法。為此，李研等[5]提出了一種考慮QoS數據可信性的服務選擇方法。劉書雷等[6]采用模擬退火算法實現了如何從多個客戶中選擇使得系統收益最大的客戶提供服務。但是，這些研究往往是采用某一種優化方法從當前的服務中選取一些能夠當前收益最大化的客戶來提供服務。但是，這種方法存在的關鍵問題是：

(1) 由于服務能力的限制，服務代理難以對所有服務提供服務，因而只能選擇對服務代理來說能夠創造收益最大的客戶。但是，如果一味地選擇對當前來說能夠帶來最大收益的客戶并不一定是一種“好”的策略。因為這可能引起潛在的有價值的客戶得不到應有的接納率，導致這些潛在的有價值的客戶流失。

(2) 由于網絡的復雜性，客戶往往只需要匿名就可以，因而，虛假的甚至惡意的客戶也很多，若不加以區別，往往會陷入對手或者攻擊者設計的圈套，從而不但不能得到較好的收益，反而會受到攻擊與損害。

為此，本文作者提出一種新的使收益最大化的客戶選擇策略。策略的目標是使得服務代理能夠獲得長期的收益最大化，而不僅僅使當前的收益最大化。其基本思想是：首先建立服務代理與客戶之間的交互行為模型，依據交互的歷史情況來描述與判斷客戶的潛在價值，從更長遠的角度來考察客戶是否能夠帶來長遠的價值。如何判斷客戶的長久價值是一個重要的問題。為此，采用一種新穎的方法，即：依據客戶的交互記錄來判斷客戶的潛在價值。客戶的潛在價值的判斷是依據客戶在過去一段時間內交互行為產生的價值來判斷的，然后，在很長一段時間內，來判斷接納此服務能夠帶來的效益，以及失去此客戶而減少的收益，從而綜合評價與選擇真正能夠帶來長遠收益的客戶。

此外，服務的可信性是服務代理能夠獲得穩定收益的重要前提，為此，對每一個客戶依據交互情況給出1個風險評估值，依據風險評估值對客戶的價值進行修正。修正的原則是；對于可信度高的客戶，風險評估的修正值與1接近；對于可信度低的客戶，風險評估的修正值與0接近。客戶修正后的價值為風險評估修正值與服務協商中標定的收益的乘積。

1 系統模型與問題描述

1.1 服務模型

本文所采用的服務體系結構與文獻[6]中所采用的服務體系結構相同。在這樣的服務架構中，來自互聯網中的客戶向服務代理申請服務組合，服務代理收到客戶的請求后，依據自己的資源情況，從互聯網中選擇合適的服務進行服務組合后提供給客戶，并以此來獲得收益，如圖1所示。

圖1 服務體系結構Fig.1 Services architecture

在服務代理對客戶提供服務時，服務代理需要與客戶進行服務級別協商(Service level agreements,SLA)。將SLA具體化為一系列的服務級別, 每個級別規定服務質量、價格等方面的參數[7,9]，并給出其收益規則(包括定價與罰金規則)，以支持基于SLA的服務組合。設服務代理A共有k個服務級別，定義為：

其中，第i個服務級別表示為：

與文獻[26]中的研究類似，服務代理記錄與每一個客戶交互過程中的信息如表1所示。在表1中，服務交互的結果共有n行代表n個客戶，m列代表最近的m次服務交互過程的行為。

表1 服務代理記錄的交互信息Table 1 Interaction information of broker

在表1中，設服務代理A在時間ti時對客戶w進行服務交互后的信息為記錄的交互信息實際上包括如下幾方面內容：(1) 交互前的服務協商的服務級別交互后實際的服務級別其他信息記錄其他對客戶的一些評價信息。

1.2 問題描述

在服務計算環境中，客戶不斷地向服務代理提交服務請求。服務請求信息包含的內容為某一服務級別SLAi。因為在較短時間內，可能有多個客戶的請求同時到達，由于資源有限，服務代理可能可以同時滿足有多個服務級別的多個需求，但是，可能難以在此段時間內滿足所有客戶的需求。因此，在這種情況下，服務代理就需要對多個客戶進行擇優選擇，選擇的目標是使 broker在較長時期內獲取盡可能多的服務收益。這樣，問題就轉化為1個多目標優化問題，即在有限的服務資源下, 組合服務的收益優化問題轉化為基于SLA 的以收益最大化為目標的客戶動態選擇。

綜上所述，收益優化的問題即對于網絡中任意服務代理A滿足下式：

要使服務收益最大化就是使服務代理在一段時期內獲得的收益最大，其中一段時間在式(3)中用T表示。T越大，表示服務代理在長時間內獲得的收益最大，而當前的大多數研究沒有考慮較長時期有收益情況。從長遠的角度來看，服務代理獲得長期的收益才是其根本目標，僅獲得當前的收益最大化往往不具有現實意義。收益的計算是提供服務收取的獲利與提供服務失敗時罰款的差值。式(3)中的限定條件是服務代理的資源有限，因此，服務代理接納的客戶對服務代理的QoS需求的量不能大于服務代理擁有的量。

2 服務選擇函數構造方法

2.1 總體概略

服務級別協議(SLA)作為服務雙方關于服務內容、質量等方面的約定，是服務計算中保障服務質量和顧客滿意度的有效途徑[2]。但是，一般來說，由服務代理提供的SLA僅是作為一種競爭依據，客戶一般是根據服務代理提供的協議挑選服務，而很難要求服務代理提供商協商SLA的細節[3]。因此，在服務組合時，服務代理需要“智能”地選擇客戶以求達到收益最大化的目標。針對以往研究中僅僅依據客戶當前的收益情況來決定是否接納客戶的不足，本文提出以下幾點：(1) 判斷客戶的價值不僅僅依據客戶的當前收益報價，而要考慮客戶長期表現出來的收益。而長期收益在本文中是依據客戶在較長時間內表現出來的收益來確定的。同時，由于不同的客戶活路程度不相同，對于價值較大而活躍程度不高的客戶，若服務代理接收到其服務請求，則代表這次請求具有更重要的意義，應該接納其請求。因而，在本文中，給出了依據客戶活躍程度的長期價值計算方法。(2) 對于客戶即時提交的請求，不能完全相信其請求所能夠帶來的收益，在本文中依據其信任度對其進行修正，以使其更符合實際。最后，依據長期與當前收益給出公正的收益判斷再進行優化選擇。

2.2 客戶長期價值量的估算

客戶能夠給服務提供者帶來的收益實際上包括 2部分：第1部分是客戶的服務請求到達后，當次服務請求能夠帶來的收益；第2部分是客戶在未來一段時間內預期能夠給服務代理帶來的收益。在以往的研究中，往往只考察了第1部分能夠給服務代理帶來的即時收益，因而可能會拒絕某次重要的有價值的客戶帶來小額收益的服務請求，從而失去一些重要的客戶。而客戶請求的即時收益是在服務級別協商中被標明，因此，現在的關鍵問題是如何計算客戶的長期價值。

客戶的長期價值是指從服務代理的角度出發計算的客戶在未來一段時間內可能帶來的收益，作為是否接納此客戶的重要依據。

設服務代理A與客戶B在時間ti進行了1次服務交互，此次產生的收益為：

若服務代理A與客戶B進行了多次服務交互，則服務代理A對客戶B下一次交互的預期收益UA,B為：

式中：]1,0[)(∈k?為衰減函數，用于對發生在不同時刻的收益進行合理加權，根據實際的社會交互行為習慣，對于新發生的交互行為應該給予更多的權重[4]。衰減函數定義為:

式(5)給出了客戶在下一次交互中的預期收益計算。服務代理是否接納客戶的請求在很大程度上取決于客戶是否能夠為服務代理帶來長期的收益，換句話說，若客戶不能夠為服務帶來長期的收益，則僅僅本次收益高而接納此客戶會造成長期價值高的客戶流失；反之，若客戶的未來長期收益大，則服務代理也不應該僅因為當前的收益小而拒絕提供服務。

客戶的長期價值的計算思想是依據客戶在時間維度上的表現來刻畫的，其思想是：若需要預測未來時間長度為T的潛在價值，則依據客戶的歷史反映未來的思想，依據從當前時間起反向T時間內交互情況的收益來反映，計算式如下：

式中：t表示從當前時刻向后推T的時間內服務代理得到的收益，若向后推的時間小于 T，則包括所有的交互行為；本身的意義是客戶在未來的時間T內的潛在收益(價值)，它實際上也包括了若不接納此客戶，則在未來的時間T內，服務代理從客戶B中損失的收益。

前面給出了客戶的潛在價值的計算方法，但還存在1個問題：對于B與C 2個客戶，在時間T內的收益相同，，但是，若交互的次數不相同，其中客戶B的交互次數遠大于客戶C的交互次數，則同時有客戶B與客戶C的服務請求到達，由于資源的有限性，只能提供1個客戶的服務。此時存在選擇哪個客戶對服務代理更有利的問題。顯然，客戶B與服務代理A交互次數非常多，但是，其產生的收益與客戶C的相等，這說明客戶B每次的收益遠小于客戶C每次的收益。因而，在這種情況下，應該選擇C才能帶來更大的收益。而客戶B由于交互次數多，也不會因為偶然的1次拒絕而使其流失。但對客戶C來說，交互次數較小，每次的收益大，可能因僅有的1次拒絕便會使其流失。這說明：即使按前面論述的方法考慮客戶的潛在價值，也要考慮客戶的活躍度，若客戶越活躍(交互次數越多)，則反映其每次收益小。為此，采取如下方法。

客戶活躍度反映了客戶在網絡中的活躍程度與穩定程度，若客戶交互的次數越多，則表示客戶會在較小的時間內有多次的服務請求，因而，在總收益相同的情況下應該降低其重要程度，而接納活躍度小的重要客戶，從而能夠帶來更多的收益。定義活躍因子為：

客戶的潛在價值(收益)為：

2.3 服務代理對客戶信任值的度量方法

前面論述了客戶的潛在價值，但是，在很多種情況下，單以客戶帶來的收益來進行客戶選擇會帶來一些問題，其中客戶的可信度是一個重要的因素。這里給出對客戶可信度的計算方法。設每次服務代理與交互的記錄如下：

則服務代理A依據信任判斷函數可得到對客戶B的信任度，即

式中：f1函數為抽象化的函數，是服務代理依據服務協商的結果對客戶的信任評價值。例如：對于服務價格這個指標，當業務代理A與客戶B在達成SLA后，若客戶嚴格按照約定的服務級別使用服務資源，則其可信度較高，f1函數則給出較高值；反之，若客戶濫用服務資源，不遵守服務級別約定，則服務代理給出的可信度就低。f2是服務代理在考察其他指標上制定的信任轉換函數。例如，服務代理A規定若客戶B對服務代理A進行攻擊或者濫用服務，則直接給出其信任度為最差級。需要指出的是：每個服務代理A制定的轉換函數可以不同，但每個服務代理A依據自己的f1和 f2函數進行信任度的評測，這樣，每個服務代理都能夠依據自己的信任轉化函數建立自己的信任空間，這樣，既符合社會網絡，也符合實際分布式網絡。在這樣的網絡中，不可能存在一個統一的信任度評價標準，每個實體都是唯一的和個性化的，都依據自己的信任評價函數在互聯網絡上進行信任演化與交互，以使自己能夠獲得較大的利益。

因此，在1次評價結果上，對多次相互交互的客戶信任評價計算如下：設是服務代理A對客戶B的所有交互行為的可信評價，

其中：TA,B表示服務代理A對客戶B的信任度。

2.4 基于信任度對收益的校正

潛在價值實際上是對未來的一種預值，是一種長期的走勢。因此，當1個客戶有具體的服務請求到達時，這個客戶的請求會提出1個具體的服務級別，其中服務級別包括了收益情況。而當前的收益情況是本次交互行為的重要體現。但服務協商的收益并不一定能夠實現，還需要進行適當修正。其原因如下。

如與服務代理A長期交互的某客戶B在原來的交互歷史中每次的交易量較小，產生的收益是1個較小的值如 ζ。但是，也不能排除在當前的交互中客戶 B申請較高級別的服務，并給出較大的遠大于ζ的收益。顯然，因為客戶B是可信的，因而，有理由相信客戶B承諾的收益遠大于收益ζ是可能的。

但是，對于另一個客戶C，若在前期的交互過程中存在很小的信用度，則由前期計算得到的預期收益也非常低，在這種情況下，若客戶在當前的申請中提出很高的收益，顯然這難以讓人相信，其收益也難以得到實現。因此，僅依據當前的收益接納這樣的客戶有可能會不但得不到較好的收益，反而會使其收益最小。

為此，這里采用服務的可信度對當前服務協商定的收益進行修正的結果，其計算方法如下：

2.5 收益優化的客戶選擇方法

對于服務代理 A，有眾多客戶的服務請求到達，服務代理從中選擇那些客戶以使得系統的收益最大。下面給出收益優化的客戶選擇方法。

與以往研究不同的是，本文的策略不僅僅以當前客戶的服務協商級別下的收益為標準，還綜合考慮了如下 3個方面的情況：(1) 客戶的潛在收益情況；(2) 客戶的當前收益情況；(3) 客戶的信任度。然后，綜合這3個方面，綜合客戶當前收益與潛在收益情況，采用線性轉化函數，將其轉化為1個較高的綜合收益。然后，依據綜合收益情況來選擇綜合收益最大的客戶，從而給出一種較為適合實際的客戶選擇方法。詳細分析如下。

對于1個到達的客戶B，其綜合收益計算表達式為：

式(15)的計算綜合了客戶的信任度、潛在收益和當前的收益，因而客戶選擇算法很容易給出。算法如下：

//多個客戶的服務請求到達時，確定選擇哪些客戶以使得系//統的收益最化。

輸入：服務代理A所有與客戶的交互記錄,客戶的請示

輸出：被選擇的客戶

Step 1:讀入服務代理記錄的客戶交互信息

Step 2:對每一個提出請求的客戶例如B進行如下計算：

Step 2.1: 依據式(5)計算出tk時的收益

Step 2.3: 據式(8)計算出 T時間段的潛在收益

Step 2.4: 據式(11)計算對客戶 B ti時的信任值

Step 2.7: 據式(14)計算對客戶 B當前的收益值

Step 2.8: 據式(15)計算對客戶 B的綜合收益值

Step 3: 對所有客戶計算的綜合收益 UA,B進行排序，選擇出前m個客戶，使其對資源的需求不能再滿足任何一個客戶。

Step 4:接納選中的客戶，提供服務。

Step 5: end.

3 實驗結果分析

下面通過模擬實驗來驗證。實驗的硬件環境如下：CPU 為Intel Pentium IV2.56GHz，內存為4G，操作系統為Windows XP；算法實現語言為JAVA。

設置服務代理的QoS資源維數為5，每個QoS的容量為1 000元；服務級別(SLA)共10級，最低的服務價格為200元，每個服務級別級差價格為80元。共產生客戶數量為500個，其中：

(1) 20%的客戶為惡意的客戶。這些惡意的客戶分為2種：第1種為純粹的惡意攻擊者，每次都只對服務代理產生攻擊，在實驗中簡稱為A(1)類客戶；第2種為善于偽裝的攻擊者，這種攻擊者可能在前期的活動中積累一定的信任值后，再進行攻擊。如在前進行多次小額度的服務請求，并嚴格按服務協商的結果執行，以取得服務代理的一定信任。然后，提出較大額的服務請求，但在這次大額請求中僅占用資源，而不付出相應的費用，從而達到欺騙的目的，在實驗中簡稱為A(2)類客戶。

(2) 有 20%的為小客戶，信任度較高，但是，每次交互的收益不大，收益在最低的幾級中選擇，在實驗中簡稱為B類客戶。

(3) 有40%的客戶為中等的客戶，信任度也較高，每次交互的服務級別為5左右，處于中等的級別，在實驗中簡稱為C類客戶。

(4) 20%的客戶是大客戶，信任度較高，其服務協商級別通常大于8 級，在實驗中簡稱為D類客戶。

采用本文提出的策略，讓各類客戶不斷按前述所給的比例向服務代理提交服務請求，服務代理接納不同類客戶的比例如圖2所示。從圖2可以看出：A類(惡意客戶)隨著交互行為的進行其被服務代理接納的比例逐步下降，而可信的客戶B，C和D類的比例逐漸上升。這說明本文的策略能夠較好地維護可信客戶的交互，而將不可信客戶排除，有利于服務代理獲得較好的收益。而且價值大的客戶接納率越高。

圖2 隨時間變化接納不同類型客戶的比例Fig.2 Relationship between accepted ratio of different type clients and time

圖3所示為不同策略下服務代理的收益。圖3中，以當前收益最大化的策略標記為策略Ⅰ(Policy Ⅰ)，本文的以長期收益最大化的策略標記為策略Ⅱ(PolicyⅡ)。從圖3可以看出：本文的策略隨著時間的推移，其收益越來越大，而僅以當前收益最大化為目標的策略由于對潛在的客戶接納率不高，因而流失(在實驗設置中，設置了1個與價值成反比的容忍拒絕率，價值越高，則容忍拒絕的次數越少，反之，容忍拒絕的次數越多)，從而造成高價值的客戶減少而使收益減少。這說明本文的策略具有較好的作用。

圖4所示為本文策略下不同類型的客戶信任度隨時間的變化情況。從圖 4可以看出：在開始階段，A類的不可信客戶可信度較低，而且隨著交互的進行，其可信度下降很快；而可信的客戶隨著交互的進行，其可信度一直上升。

圖5所示為不同類客戶自己宣稱的收益與系統評價的收益。從圖5可以看出：對于不可信的客戶，其宣稱的收益遠遠大于其實際收益，因而系統的評價值遠小于它自己宣稱的值。而對于可信的客戶，其宣稱值與系統評價值基本一致，說明本文的策略對不可信客戶，具有較好的效果。

圖3 不同策略下隨時間變化的收益對比Fig.3 Relationship between gains in different policies and time

圖4 本文策略下隨時間變化各類客戶的信任度變化情況Fig.4 Relationship between trust of different type clients and time

圖5 客戶宣稱的值與系統平價的值的對比Fig.5 Comparison of client declared value and system evaluating value

4 結論

(1) 提出了 1種基于長期收益的客戶選擇策略。該策略既考慮了客戶的可信度，又合理地依據客戶的可信度對客戶提出的收益進行修正，并依據客戶的歷史交互情況判斷其潛在的價值，從而做出收益優化的服務選擇。

(2) 依據策略的思想提出了相應的服務選擇算法。

(3) 與傳統的僅以當前收益最大化的優化方法相比，本文策略在長期收益方面要高30%以上，而且考察的時間越長，策略的效果越明顯，說明了本文策略的優越性。

[1] Armbrust M, Fox A. A view of cloud computing[J]. Magazine Communications of the ACM, 2010, 53(4): 50-58.

[2] Zulkernine F, Martin P, Craddock C. A policy-based middleware for Web services SLA negotiation[C]//Proceedings of the IEEE International Conference on Web Services (ICWS/09). Los Angeles, CA, 2009: 1043-1050.

[3] Jameel H, Hung L X,Kalim U. A trust model for ubiquitous systems based on vectors of trust values[C]//Proceedings of the7th IEEE Int’1Sympon Multimedia.Washington:IEEE Computer Society Press, 2005: 674-679.

[4] 王顯志, 徐曉飛, 王忠杰. 面向組合服務收益優化的動態服務選擇方法[J]. 計算機學報, 2010, 33(11): 2104-2115.WANG Xian-zhi, XU Xiao-fei, WANG Zhong-jie. A profit optimization oriented service selection method for dynamic service composition[J]. Chinese Journal of Computers, 2010,33(11): 2104-2115.

[5] 李研, 周明輝, 李瑞超, 等. 一種考慮 QoS 數據可信性的服務選擇方法[J]. 軟件學報, 2008, 19(10): 2620-2627.LI Yan, ZHOU Ming-hui, LI Rui-chao, et al. Service selection approach considering the trustworthiness of QoS data[J]. Journal of Software, 2008, 19(10): 2620-2627.

[6] 劉書雷, 劉云翔, 張帆, 等.一種服務聚合中 QoS 全局最優服務動態選擇算法[J]. 軟件學報, 2007, 18(3): 646-656.LIU Shu-lei, LIU Yun-xiang, ZHANG Fan, et al. A dynamic Web services selection algorithm with QoS global optimal in Web services composition[J].Journal of Software, 2007, 18(3):646-656.

[7] Wang X, Huang S, Zhou A. QoS-aware composite services retrieval[J]. Journal of Computer Science and Technology, 2006,21(4): 547-558.

[8] 代鈺, 楊雷, 張斌, 等.支持組合服務選取的 QoS 模型及優化求解[J]. 計算機學報, 2006, 29(7): 1167-1178.DAI Yu, YANG Lei, ZHANG Bin. QoS for composite Web services and optimization[J]. Chinese Journal of Computers,2006, 29(7): 1167-1178.

[9] 岳昆, 劉惟一, 王曉玲, 等. 一種基于不確定性因素疊加的Web 服務質量度量方法[J]. 計算機研究與發展, 2009, 46(5):841-849.YUE Kun, LIU Wei-yi, WANG Xiao-ling, et al. An approach for measuring quality of Web services based on the superposition of uncertain factors[J]. Journal of Computer Research and Development, 2009, 46(5): 841-849.

[10] 蔣哲遠, 韓江洪, 王釗. 動態的QoS感知Web服務選擇和組合優化模型[J]. 計算機學報, 2009, 32(5): 1014-1025.JIANG Zhe-yuan, HAN Jiang-hong, WANG Zhao. An optimization model for dynamic QoS-aware web services selection and composition[J]. Chinese Journal of Computers,2009, 32(5): 1014-1025.

[11] Benatallah B, Dumas M, Sheng Q Z, et al. Declarative composition and peer-to-peer provisioning of dynamic Web services[C]//Proc of the 18th Intel Conf on Data Engineering.San Jose: IEEE Computer Society, 2002: 297-308.

[12] Casati F, Ilnicki S, Jin L J. eFlow: A platform for developing and managing composition e-services[R]. Palo Alto: HP Laboratories,2000: 1-20.

[13] Liu Y T, Anne H H, Zeng L Z. QoS computation and policing in dynamic Web service selection[C]//Proc of the WWW 2004.New York: ACM, 2004: 66-73.

[14] Zeng L Z, Benatallah B, Dumas M. Quality driven Web service composition[C]//Proc of the WWW 2003. Budapest: ACM, 2003:411-421.

[15] 趙俊峰, 謝兵, 張路, 等. 一種支持領域特性的 Web 服務組裝方法[J]. 計算機學報, 2005, 28(4): 731-738.ZHAO Jun-feng, XIE Bing, ZHANG Lu et al. A Web services composition method supporting domain feature[J]. Chinese Journal of Computers, 2005, 28(4): 731-738.