曹玖新 楊鵬偉 劉 波 錢(qián)玉俠 吳江林 董 丹

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

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

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

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

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

Web服務(wù)協(xié)商是最能體現(xiàn)博弈特點(diǎn)的基本問(wèn)題之一．由于服務(wù)協(xié)商的參與者并不知道對(duì)手的協(xié)商空間和偏好,因此將Web服務(wù)協(xié)商定義為不完全信息博弈過(guò)程．將協(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ù)請(qǐng)求者 (consumer agent,CA)、服務(wù)提供者 (provider agent,PA)以及協(xié)商管理者(manager agent,MA)．MA負(fù)責(zé)整個(gè)協(xié)商流程的控制管理,產(chǎn)生和發(fā)送協(xié)商建議．

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

2.1 協(xié)商議題分類(lèi)

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

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

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

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

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

(1)

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

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

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

(2)

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

2.4 總效益函數(shù)

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

(3)

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

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

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

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

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

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

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

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

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

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

3.2.1 基于時(shí)間的策略

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

(4)

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

3.2.2 基于對(duì)手提議的策略

(5)

3.2.3 基于MA建議的策略

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

(6)

3.2.4 綜合協(xié)商策略

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

(7)

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

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

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

輸入:QoS集合

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

1 classify(QoS,E,D);

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

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

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

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

6 }

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

8 result[i]=negotiate(i);

9 return result;

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

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

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

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

4.1 獨(dú)立議題的協(xié)商實(shí)驗(yàn)

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

圖2 TPM-discount策略與T策略的對(duì)比

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

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

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

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

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

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

5 結(jié)語(yǔ)

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

)

[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.