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

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

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

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

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

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

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

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

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

2.1 協(xié)商議題分類

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

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

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

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

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

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

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

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

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

2.4 總效益函數(shù)

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

式中，Pj為第j個獨立議題或關聯(lián)議題子集的提議值；v(Pj)為標準化后的效益值；wj為第j個獨立議題或關聯(lián)議題子集的效益值權重.

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

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

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

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

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

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

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

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

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

3.2.1 基于時間的策略

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

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

3.2.2 基于對手提議的策略

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

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

3.2.3 基于MA建議的策略

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

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

3.2.4 綜合協(xié)商策略

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

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

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

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

輸入:QoS集合

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

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

4 實驗分析

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

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

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

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

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

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

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

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

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

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

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

5 結語

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

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.