基于議題分類的Web服務協商機制

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

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

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

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

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

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

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

2 協商議題分類與效益函數

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

2.1 協商議題分類

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

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

圖1 協商議題分類示意圖

2.2 獨立議題的效益函數

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

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

2.3 關聯議題子集的效益函數

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

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

2.4 總效益函數

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

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

3 Web服務協商機制

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

3.1 協商協議

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

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

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

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

3.2 獨立議題協商中的綜合協商策略

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

3.2.1 基于時間的策略

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

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

3.2.2 基于對手提議的策略

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

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

3.2.3 基于MA建議的策略

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

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

3.2.4 綜合協商策略

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

3.3 Web服務協商過程

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

算法1 Web服務協商過程

輸入:QoS集合

輸出:最終協商結果result

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

4 實驗分析

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

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

4.1 獨立議題的協商實驗

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

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

4.2 關聯議題的協商實驗

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

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

圖3 關聯議題協商結果比較

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

表1 2種算法的協商時間平均值 ms

5 結語

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

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，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］//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，Faratin 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.