基于議題分類的Web服務(wù)協(xié)商機制

曹玖新 楊鵬偉 劉 波 錢玉俠 吳江林 董 丹

(東南大學(xué)計算機科學(xué)與工程學(xué)院,南京 211189)(東南大學(xué)計算機網(wǎng)絡(luò)與信息集成教育部重點實驗室,南京 211189)

Internet的開放性要求Web服務(wù)能夠以豐富、靈活的交互方式向廣大用戶提供個性化、可定制的服務(wù)[1]．通過服務(wù)發(fā)現(xiàn),服務(wù)請求者可找到滿足其所需要功能的服務(wù)提供者集合．但不同服務(wù)所具有的QoS屬性往往差別很大,并且某些屬性本身具有動態(tài)性,難以保證完全符合服務(wù)請求者要求,為此引入服務(wù)協(xié)商機制來協(xié)調(diào)雙方的利益需求．

當前的服務(wù)協(xié)商僅從協(xié)商參與者期望值和保守值[2]的角度來衡量協(xié)商帶來的收益情況[3-4],忽略了參與者的時間成本和其他資源成本對收益的影響．此外,已有研究大部分默認協(xié)商議題之間沒有依賴關(guān)系[1,5]或者所有議題之間都存在依賴關(guān)系[6-7],忽略了現(xiàn)實環(huán)境中Web服務(wù)的QoS屬性往往同時存在關(guān)聯(lián)屬性和非關(guān)聯(lián)屬性．針對這種議題間的弱關(guān)聯(lián)現(xiàn)象,目前還沒有較好的解決方案．

針對以上問題,本文將Web服務(wù)協(xié)商問題建模為不完全信息博弈問題．在此基礎(chǔ)上,針對關(guān)聯(lián)議題協(xié)商和獨立議題的特點,提出了不同的協(xié)商方法．針對獨立議題,引入?yún)f(xié)商管理者來統(tǒng)籌協(xié)調(diào)協(xié)商過程,克服了傳統(tǒng)策略過于保守、協(xié)商過程過于復(fù)雜的不足．針對關(guān)聯(lián)議題,引入關(guān)聯(lián)議題子集概念,關(guān)聯(lián)議題子集內(nèi)采用聯(lián)合協(xié)商,關(guān)聯(lián)議題子集間采用獨立協(xié)商．實驗結(jié)果表明,該機制比傳統(tǒng)協(xié)商更加高效,且獲得了更好的社會效用．

1 基于不完全信息博弈的服務(wù)協(xié)商模型

Web服務(wù)協(xié)商是最能體現(xiàn)博弈特點的基本問題之一．由于服務(wù)協(xié)商的參與者并不知道對手的協(xié)商空間和偏好,因此將Web服務(wù)協(xié)商定義為不完全信息博弈過程．將協(xié)商模型表示成(A,I,P,S),其中I={i1,i2,…,in}表示協(xié)商議題集合,代表服務(wù)協(xié)商中的QoS屬性;P表示協(xié)商協(xié)議,是協(xié)商參與者的協(xié)商規(guī)程,規(guī)定了協(xié)商參與者的交互規(guī)則;S表示協(xié)商策略,協(xié)商參與者根據(jù)協(xié)商策略決定如何生成提議和反提議;A表示協(xié)商參與者集合,包括服務(wù)請求者 (consumer agent,CA)、服務(wù)提供者 (provider agent,PA)以及協(xié)商管理者(manager agent,MA)．MA負責(zé)整個協(xié)商流程的控制管理,產(chǎn)生和發(fā)送協(xié)商建議．

2 協(xié)商議題分類與效益函數(shù)

2.1 協(xié)商議題分類

為解決協(xié)商議題的弱關(guān)聯(lián)性,基于議題分類引入關(guān)聯(lián)議題子集,以表示協(xié)商議題間的依賴關(guān)系．如果協(xié)商參與者對于某一議題i的效益不僅依賴于該議題的值,還依賴于其他議題的值,則稱這2個議題有關(guān)聯(lián)．若協(xié)商議題ia與議題ib有關(guān)聯(lián),則定義關(guān)聯(lián)議題子集Ia,b={ia,ib}．通過議題分類,將協(xié)商議題分為獨立議題子集和關(guān)聯(lián)議題子集,表示為I={i1,i2,…,ik,I1,I2,…Il}．

在服務(wù)協(xié)商中,往往同時存在關(guān)聯(lián)議題和獨立議題．本文中,采用獨立協(xié)商方法解決獨立議題和關(guān)聯(lián)議題子集之間的協(xié)商,采用聯(lián)合協(xié)商方法解決關(guān)聯(lián)子集的內(nèi)部協(xié)商，具體形式如圖1所示．

圖1 協(xié)商議題分類示意圖

2.2 獨立議題的效益函數(shù)

協(xié)商議題的結(jié)果為協(xié)商參與者帶來的利益稱為效益,用效益函數(shù)來表示協(xié)商議題結(jié)果和效益的映射關(guān)系．對于獨立議題,協(xié)商參與者從此議題中獲得的利益僅與該議題的協(xié)商結(jié)果有關(guān),故對于獨立議題i,在第t次協(xié)商回合中參與者a對提議Pi,t的效益函數(shù)可表示為

(1)

式中,δ(a)為博弈論中討價還價模型的折扣率．協(xié)商回合數(shù)越多,雙方收益均越少．

2.3 關(guān)聯(lián)議題子集的效益函數(shù)

對于關(guān)聯(lián)議題子集,協(xié)商參與者的效益函數(shù)采用約束集合C={C1,C2,…,Cm}來表示．約束定義為單維或多維的議題值區(qū)間,并賦予其效益值．關(guān)聯(lián)議題子集的效益值是協(xié)商提議滿足的所有約束對應(yīng)的效益值之和．對于關(guān)聯(lián)議題子集I′,在第t次協(xié)商回合中參與者a對提議PI′,t的效益函數(shù)定義為

(2)

式中,x(ck)為滿足約束ck所有可能的提議;v(ck)為約束ck的效益值．

2.4 總效益函數(shù)

基于以上定義,若議題分類后獲得獨立議題和關(guān)聯(lián)議題子集集合I={i1,i2,…,ik,I1,I2,…Il},定義協(xié)商提議P={P1,P2,…,Pk+l}對于協(xié)商參與者的總效益為

(3)

式中,Pj為第j個獨立議題或關(guān)聯(lián)議題子集的提議值;v(Pj)為標準化后的效益值;wj為第j個獨立議題或關(guān)聯(lián)議題子集的效益值權(quán)重．

3 Web服務(wù)協(xié)商機制

基于協(xié)商模型、協(xié)商議題分類及效益函數(shù),本文改進了傳統(tǒng)的協(xié)商協(xié)議和協(xié)商策略,提出了一種基于議題分類的Web服務(wù)協(xié)商機制．

3.1 協(xié)商協(xié)議

協(xié)商協(xié)議規(guī)范和約束主體之間的交互規(guī)則[8],包括參與協(xié)商的主體類型、協(xié)商過程中的狀態(tài)及其轉(zhuǎn)換、主體在特定狀態(tài)下的行動等．

建立協(xié)商關(guān)系后,協(xié)商參與者根據(jù)議題集合I={i1,i2,…,ik,I1,I2,…Il}對每個議題元素進行獨立并行協(xié)商．對于獨立議題,如何公平、快速地獲得協(xié)商結(jié)果是需要解決的關(guān)鍵問題．由于關(guān)聯(lián)議題的效益函數(shù)是非線性的,其關(guān)鍵問題是如何在協(xié)商雙方的接受空間內(nèi)獲得全局最優(yōu)的社會效用．因此,本文針對獨立議題和關(guān)聯(lián)議題子集分別提出了2組不同的協(xié)商協(xié)議,針對獨立議題ik采用獨立議題協(xié)商協(xié)議協(xié)商,針對關(guān)聯(lián)議題子集Il內(nèi)部的議題采用關(guān)聯(lián)議題協(xié)商協(xié)議聯(lián)合協(xié)商．

在獨立議題協(xié)商協(xié)議中,引入MA作為非偏見性中介指導(dǎo)CA和PA的協(xié)商過程．針對獨立議題i的協(xié)商過程如下:由PA開始協(xié)商并運行初始協(xié)商過程,根據(jù)協(xié)商策略計算提議并發(fā)送給對方．在其他階段,當CA或PA收到對方提議時,判斷是否接受提議,若接受提議則協(xié)商成功;若拒絕提議則根據(jù)協(xié)商策略生成反提議,并發(fā)送給對方．重復(fù)以上過程,直至協(xié)商成功或失敗．由于協(xié)商雙方生成的提議是在對方的提議和自己上一輪提議的范圍內(nèi),因此協(xié)商結(jié)果不斷收斂直至協(xié)商結(jié)束．

在關(guān)聯(lián)議題協(xié)商協(xié)議中,關(guān)聯(lián)議題子集間獨立協(xié)商,關(guān)聯(lián)議題子集內(nèi)聯(lián)合協(xié)商．為解決關(guān)聯(lián)議題子集的內(nèi)部協(xié)商問題,本文基于議題分類,改進了文獻[7]中的投標算法,提出基于議題分類的投標算法．首先,將所有關(guān)聯(lián)議題分為多個關(guān)聯(lián)議題子集．然后,在每個關(guān)聯(lián)議題子集內(nèi)部使用投標算法進行協(xié)商．完成協(xié)商后,根據(jù)所有關(guān)聯(lián)議題子集的協(xié)商結(jié)果,獲得最終結(jié)果．

3.2 獨立議題協(xié)商中的綜合協(xié)商策略

在獨立議題協(xié)商過程中,協(xié)商參與者依據(jù)協(xié)商策略決定如何生成提議和反提議[9],主要依賴于讓步函數(shù)．本文根據(jù)實際應(yīng)用,綜合考慮時間代價、對手提議、MA建議等改進了傳統(tǒng)的協(xié)商策略．

3.2.1 基于時間的策略

協(xié)商過程一般存在時間限制[10],且隨時間流逝雙方的得益將同時減少,因此協(xié)商雙方隨著時間變化調(diào)整讓步幅度以求盡快協(xié)商成功．協(xié)商參與者a基于時間讓步生成的反提議可表示為

(4)

式中,Di,t為基于時間的讓步妥協(xié)度.令Di,t=exp[(1-t/tmax)σlnλ],其中,σ為自定義的參數(shù),表示協(xié)商參與者的時間緊迫程度,λ為初始讓步妥協(xié)度,tmax為協(xié)商參與者可以接受的最大協(xié)商次數(shù)．

3.2.2 基于對手提議的策略

(5)

3.2.3 基于MA建議的策略

MA作為非偏見性中介,掌握整個協(xié)商過程中的信息以及以往的協(xié)商歷史信息,可以從全局宏觀上制定協(xié)商建議來發(fā)送給CA和PA．MA生成建議的公式如下:

(6)

3.2.4 綜合協(xié)商策略

綜合以上策略及折扣率,本文提出綜合協(xié)商策略(TPM-discount策略),其計算提議和反提議公式如下:

(7)

3.3 Web服務(wù)協(xié)商過程

在基于議題分類的Web服務(wù)協(xié)商機制中,首先對議題進行分類,然后針對獨立議題和關(guān)聯(lián)議題使用不同的協(xié)商協(xié)議,并針對獨立議題的協(xié)商提出了綜合時間、對手提議和MA建議的協(xié)商策略．算法1描述了本文的Web服務(wù)協(xié)商過程．

算法1Web服務(wù)協(xié)商過程

輸入:QoS集合

輸出:最終協(xié)商結(jié)果result

1 classify(QoS,E,D);

2 for(I′∈E){//關(guān)聯(lián)議題子集,使用投標算法

3BCA=CA.bid-generation(I′);

4BPA=PA.bid-generation(I′);

5 result[I′]=MA.search_result(BCA,BPA);

6 }

7 for (i∈D)//獨立議題

8 result[i]=negotiate(i);

9 return result;

第1行對QoS即協(xié)商議題進行分類,分為關(guān)聯(lián)議題子集集合E和獨立議題集合D．第2～6行表示利用投標算法對每個關(guān)聯(lián)議題子集進行協(xié)商．第7～8行表示對每個獨立議題進行協(xié)商．

4 實驗分析

為驗證本文提出的協(xié)商機制,設(shè)計了具體的服務(wù)協(xié)商案例進行仿真．根據(jù)實驗結(jié)果,對本文提出的協(xié)商機制以及傳統(tǒng)的協(xié)商機制進行性能比較．

獨立議題和關(guān)聯(lián)議題需要解決的關(guān)鍵問題不同．獨立議題協(xié)商希望快速獲得協(xié)商結(jié)果,而關(guān)聯(lián)議題協(xié)商希望獲得全局最優(yōu)社會效用的協(xié)商結(jié)果．和傳統(tǒng)的協(xié)商機制相比,本文在獨立議題的協(xié)商協(xié)議中對協(xié)商策略進行了改進,提出了綜合協(xié)商策略,在關(guān)聯(lián)議題的協(xié)商協(xié)議中提出了基于議題分類的投標算法．為此,本文針對獨立議題和關(guān)聯(lián)議題分別設(shè)計實驗,在獨立議題協(xié)商中比較綜合協(xié)商策略和傳統(tǒng)協(xié)商策略,在關(guān)聯(lián)議題協(xié)商中比較基于議題分類的投標算法和傳統(tǒng)的投標算法,并根據(jù)不同的評價標準對實驗結(jié)果進行分析．

4.1 獨立議題的協(xié)商實驗

為了評估獨立議題協(xié)商機制的性能,在同等條件下,將本文提出的TPM-discount策略與傳統(tǒng)的基于時間的協(xié)商策略 (T策略)進行對比,協(xié)商過程見圖2．由圖可知,TPM-discount策略在協(xié)商過程中可以更快地改變協(xié)商提議傾向,達成一致意見．由此表明,折扣率和綜合策略的引入加快了協(xié)商速度,同時也保證了協(xié)商結(jié)果可以客觀描述協(xié)商參與者的實際效益．

圖2 TPM-discount策略與T策略的對比

4.2 關(guān)聯(lián)議題的協(xié)商實驗

為驗證基于議題分類的投標算法的性能,針對不同的協(xié)商議題和關(guān)聯(lián)議題子集數(shù)量,設(shè)計并實施了10個模擬實驗,并將本文算法結(jié)果與文獻[7]中的投標算法(簡單投標算法)結(jié)果進行比較,這種簡單投標算法默認所有議題之間都存在關(guān)聯(lián)．實驗中,協(xié)商議題數(shù)量從4增加到13,議題至少可以分為2組關(guān)聯(lián)議題子集,每個關(guān)聯(lián)議題子集最多包含4個議題．針對每個實驗,分別使用簡單投標算法和本文算法進行協(xié)商,并比較協(xié)商結(jié)果的社會效用以及協(xié)商時間,以評價協(xié)商機制的效率和性能．同時,為更好地對比2種算法,引入退火算法作為參照,將協(xié)商結(jié)果的社會效用值除以基于退火算法得到的社會效用值,此比值即為最終的實驗結(jié)果．

由圖3可以看出,2種算法的協(xié)商結(jié)果與退火算法的結(jié)果之比均大于1,即簡單投標算法和本文算法的協(xié)商結(jié)果優(yōu)于退火算法．同時,本文算法的結(jié)果普遍優(yōu)于簡單投標算法,且隨著協(xié)商議題數(shù)量和關(guān)聯(lián)議題子集數(shù)量的增加,前者能獲得更精確的協(xié)商結(jié)果．

圖3 關(guān)聯(lián)議題協(xié)商結(jié)果比較

為比較2種算法的效率,對所有實驗中協(xié)商時間的平均值進行統(tǒng)計,結(jié)果見表1．由表可知,使用本文算法的協(xié)商時間遠少于使用簡單投標算法的協(xié)商時間,而且隨著議題數(shù)量的增加差別愈加明顯．同時,當協(xié)商議題數(shù)量和關(guān)聯(lián)議題子集數(shù)量同時增加時,本文算法的協(xié)商時間反而減少．而對于簡單投標算法,協(xié)商時間隨著議題數(shù)量的增加嚴格遞增．

表1 2種算法的協(xié)商時間平均值 ms

5 結(jié)語

本文分析了當前Web服務(wù)協(xié)商的局限性及不足,針對服務(wù)業(yè)務(wù)流中的單一服務(wù),探討雙邊協(xié)商機制,提出了一個完整的Web服務(wù)協(xié)商機制．將協(xié)商議題分為獨立議題和關(guān)聯(lián)議題,并基于議題分類對其提出不同的協(xié)商協(xié)議．在獨立議題協(xié)商中改進了傳統(tǒng)的協(xié)商策略,提出綜合時間、對手提議和MA建議的綜合協(xié)商策略;在關(guān)聯(lián)議題協(xié)商中改進了傳統(tǒng)的投標算法,提出基于議題分類的投標算法．實驗結(jié)果表明,與傳統(tǒng)協(xié)商機制中的協(xié)商策略和投標算法相比,本文提出的綜合協(xié)商策略和基于議題分類的投標算法的協(xié)商結(jié)果更加精確,協(xié)商時間也大幅度減少．

)

[1] Zheng X R,Patrick M,Wend Y P,et al. Applying bargaining game theory to Web services negotiation[C]//Proceedingsof2010IEEEInternationalConferenceonServicesComputing. Miami,FL,USA,2010: 218-225.

[2] Cao J X,Liu Y S,Luo J Z,et al. Efficient multi-QoS attributes negotiation for service composition in dynamically changeable environments [C]//Proceedingsof2010IEEEInternationalConferenceonSystem,Man,andCybernetics. Istanbul,Turkey,2010: 3118-3124.

[3] Yao Y L,Yang F C,Su S. Flexible decision making in Web services negotiation[C]//Proceedingsof2006ArtificialIntelligence:Methodology,Systems,Applications. Berlin,Germany,2006: 108-117.

[4] Yao Y K,Ma L. Automated negotiation for Web services [C]//Proceedingsofthe11thIEEESingaporeInternationalConferenceonCommunicationSystems. Guangzhou,China,2008: 1436-1440.

[5] Zulkernine F H,Martin P. An adaptive and intelligent SLA negotiation system for Web services[J].IEEETransactionsonServicesComputing,2011,4(1): 31-43.

[6] Klein M,Faratin P,Sayama H,et al. Negotiation complex contracts[C]//Proceedingsof2002AutonomousAgents&MultiagentSystems/AgentTheories,Architectures,andLanguages. Bologna,Italy,2002:58-73.

[7] Takayuki I,Hattori H,Klein M. Multi-issue negotiation protocol for agents: exploring nonlinear utility spaces[C]//Proceedingsof2007InternationalJointConferenceonArtificialIntelligence. Hyderabad,India,2007: 1347-1352.

[8] Aydoan R. Content-oriented composite service negotiation with complex preferences[C]//Proceedingsofthe7thInternationalConferenceonAutonomousAgentsandMultiAgentSystems. Estoril,Portugal,2008: 1725-1726.

[9] Huder S,Ludwig H,Wirtz G. Negotiating SLAs—an approach for a generic negotiation framework for WS-agreement [J].JournalofGridComputing,2009,7(2): 225-246.

[10] Faratin P,Sierra C,Jennings N. Negotiation decision functions for autonomous agents[J].RoboticsandAutonomousSystems,1998,24(3/4):159-182.