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

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

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

當(dāng)前的服務(wù)協(xié)商僅從協(xié)商參與者期望值和保守值［2］的角度來衡量協(xié)商帶來的收益情況［3-4］，忽略了參與者的時(shí)間成本和其他資源成本對(duì)收益的影響.此外，已有研究大部分默認(rèn)協(xié)商議題之間沒有依賴關(guān)系［1，5］或者所有議題之間都存在依賴關(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)象，目前還沒有較好的解決方案.

針對(duì)以上問題，本文將Web服務(wù)協(xié)商問題建模為不完全信息博弈問題.在此基礎(chǔ)上，針對(duì)關(guān)聯(lián)議題協(xié)商和獨(dú)立議題的特點(diǎn)，提出了不同的協(xié)商方法.針對(duì)獨(dú)立議題，引入?yún)f(xié)商管理者來統(tǒng)籌協(xié)調(diào)協(xié)商過程，克服了傳統(tǒng)策略過于保守、協(xié)商過程過于復(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ù)協(xié)商的參與者并不知道對(duì)手的協(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ù)請(qǐng)求者 (consumer agent，CA)、服務(wù)提供者(provider agent，PA)以及協(xié)商管理者(manager agent，MA).MA負(fù)責(zé)整個(gè)協(xié)商流程的控制管理，產(chǎn)生和發(fā)送協(xié)商建議.

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

在服務(wù)協(xié)商中協(xié)商議題是需要協(xié)商的QoS屬性，每一個(gè)服務(wù)協(xié)商參與者a對(duì)協(xié)商議題i存在期望值 q(a)i，des和保守值 q(a)i，res.對(duì)于獨(dú)立議題，期望值是能夠?qū)崿F(xiàn)自身關(guān)于協(xié)商議題利益最大化的數(shù)值，而保守值是協(xié)商參與者能夠接受的使利益最小化的數(shù)值.但對(duì)于關(guān)聯(lián)議題，期望值和保守值代表可協(xié)商范圍的邊界，即參與者僅接受保守值和期望值之間的協(xié)商結(jié)果.

2.1 協(xié)商議題分類

為解決協(xié)商議題的弱關(guān)聯(lián)性，基于議題分類引入關(guān)聯(lián)議題子集，以表示協(xié)商議題間的依賴關(guān)系.如果協(xié)商參與者對(duì)于某一議題i的效益不僅依賴于該議題的值，還依賴于其他議題的值，則稱這2個(gè)議題有關(guān)聯(lián).若協(xié)商議題ia與議題ib有關(guān)聯(lián)，則定義關(guān)聯(lián)議題子集 Ia，b={ia，ib}.通過議題分類，將協(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é)商議題分類示意圖

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

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

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

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

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

式中，x(ck)為滿足約束ck所有可能的提議；v(ck)為約束ck的效益值.

2.4 總效益函數(shù)

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

式中，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é)商議題分類及效益函數(shù)，本文改進(jìn)了傳統(tǒng)的協(xié)商協(xié)議和協(xié)商策略，提出了一種基于議題分類的Web服務(wù)協(xié)商機(jī)制.

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

協(xié)商協(xié)議規(guī)范和約束主體之間的交互規(guī)則［8］，包括參與協(xié)商的主體類型、協(xié)商過程中的狀態(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)鍵問題.由于關(guān)聯(lián)議題的效益函數(shù)是非線性的，其關(guā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作為非偏見性中介指導(dǎo)CA和PA的協(xié)商過程.針對(duì)獨(dú)立議題i的協(xié)商過程如下:由PA開始協(xié)商并運(yùn)行初始協(xié)商過程，根據(jù)協(xié)商策略計(jì)算提議并發(fā)送給對(duì)方.在其他階段，當(dāng)CA或PA收到對(duì)方提議時(shí)，判斷是否接受提議，若接受提議則協(xié)商成功；若拒絕提議則根據(jù)協(xié)商策略生成反提議，并發(fā)送給對(duì)方.重復(fù)以上過程，直至協(xié)商成功或失敗.由于協(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é)商問題，本文基于議題分類，改進(jìn)了文獻(xiàn)［7］中的投標(biāo)算法，提出基于議題分類的投標(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é)商過程中，協(xié)商參與者依據(jù)協(xié)商策略決定如何生成提議和反提議［9］，主要依賴于讓步函數(shù).本文根據(jù)實(shí)際應(yīng)用，綜合考慮時(shí)間代價(jià)、對(duì)手提議、MA建議等改進(jìn)了傳統(tǒng)的協(xié)商策略.

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

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

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

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

對(duì)手提議對(duì)協(xié)商參與者的決策也起著重要作用.在正常協(xié)商過程中，對(duì)手的提議越接近自己的期望時(shí)，做出的讓步越小；反之，則會(huì)做出較大讓步，以增加協(xié)商成功概率.假設(shè)在第t次協(xié)商回合中協(xié)商參與者收到另外一個(gè)協(xié)商參與者b對(duì)議題i的提議為，協(xié)商參與者 a上一次的提議為，則基于對(duì)手提議參與者 a在第 t次協(xié)商回合中生成的反提議可表示為

式中，Di=e－v(a)(P(b)i，t)為基于對(duì)方提議的妥協(xié)度.

3.2.3 基于MA建議的策略

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

式中，hi為類似歷史交易中議題i的平均值∈(0，1)為根據(jù)私人信號(hào)相關(guān)均衡原理產(chǎn)生的隨機(jī)數(shù)，用于無偏見調(diào)整協(xié)商雙方的讓步幅度.

3.2.4 綜合協(xié)商策略

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

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

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

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

輸入:QoS集合

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

第1行對(duì)QoS即協(xié)商議題進(jìn)行分類，分為關(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)鍵問題不同.獨(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é)議中提出了基于議題分類的投標(biāo)算法.為此，本文針對(duì)獨(dú)立議題和關(guān)聯(lián)議題分別設(shè)計(jì)實(shí)驗(yàn)，在獨(dú)立議題協(xié)商中比較綜合協(xié)商策略和傳統(tǒng)協(xié)商策略，在關(guān)聯(lián)議題協(xié)商中比較基于議題分類的投標(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é)商過程見圖2.由圖可知，TPM-discount策略在協(xié)商過程中可以更快地改變協(xié)商提議傾向，達(dá)成一致意見.由此表明，折扣率和綜合策略的引入加快了協(xié)商速度，同時(shí)也保證了協(xié)商結(jié)果可以客觀描述協(xié)商參與者的實(shí)際效益.

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

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

為驗(yàn)證基于議題分類的投標(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é)果見表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é)語

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

References)

［1］Zheng X R，Patrick M，Wend Y P，et al.Applying bargaining game theory to Web services negotiation［C］//Proceedings of 2010 IEEE International Conference on Services Computing.Miami，F(xiàn)L，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］//Proceedings of 2010 IEEE International Conference on System，Man，and Cybernetics.Istanbul，Turkey，2010:3118-3124.

［3］Yao Y L，Yang F C，Su S.Flexible decision making in Web services negotiation［C］//Proceedings of 2006 Artificial Intelligence:Methodology， Systems，Applications.Berlin，Germany，2006:108-117.

［4］Yao Y K，Ma L.Automated negotiation for Web services［C］//Proceedings of the 11th IEEE Singapore InternationalConference on Communication Systems.Guangzhou，China，2008:1436-1440.

［5］Zulkernine F H，Martin P.An adaptive and intelligent SLA negotiation system for Web services［J］.IEEE Transactions on Services Computing，2011，4(1):31-43.

［6］Klein M，F(xiàn)aratin P，Sayama H，et al.Negotiation complex contracts［C］//Proceedings of 2002 Autonomous Agents＆Multiagent Systems/Agent Theories，Architectures，and Languages.Bologna，Italy，2002:58-73.

［7］Takayuki I，Hattori H，Klein M.Multi-issue negotiation protocol for agents:exploring nonlinear utility spaces［C］//Proceedings of 2007 International Joint Conference on Artificial Intelligence.Hyderabad，India，2007:1347-1352.

［8］Aydoan R.Content-oriented composite service negotiation with complex preferences［C］//Proceedings of the 7th International Conference on Autonomous Agents and Multi Agent Systems.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］.Journal of Grid Computing，2009，7(2):225-246.

［10］Faratin P，Sierra C，Jennings N.Negotiation decision functions for autonomous agents［J］.Robotics and Autonomous Systems，1998，24(3/4):159-182.