曹玖新 杨鹏伟 刘 波 钱玉侠 吴江林 董 丹

(东南大学计算机科学与工程学院,南京 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 协商议题分类与效益函数

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的效益函数可表示为

(1)

式中,δ(a)为博弈论中讨价还价模型的折扣率．协商回合数越多,双方收益均越少．

2.3 关联议题子集的效益函数

对于关联议题子集,协商参与者的效益函数采用约束集合C={C1,C2,…,Cm}来表示．约束定义为单维或多维的议题值区间,并赋予其效益值．关联议题子集的效益值是协商提议满足的所有约束对应的效益值之和．对于关联议题子集I′,在第t次协商回合中参与者a对提议PI′,t的效益函数定义为

(2)

式中,x(ck)为满足约束ck所有可能的提议;v(ck)为约束ck的效益值．

2.4 总效益函数

基于以上定义,若议题分类后获得独立议题和关联议题子集集合I={i1,i2,…,ik,I1,I2,…Il},定义协商提议P={P1,P2,…,Pk+l}对于协商参与者的总效益为

(3)

式中,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基于时间让步生成的反提议可表示为

(4)

式中,Di,t为基于时间的让步妥协度.令Di,t=exp[(1-t/tmax)σlnλ],其中,σ为自定义的参数,表示协商参与者的时间紧迫程度,λ为初始让步妥协度,tmax为协商参与者可以接受的最大协商次数．

3.2.2 基于对手提议的策略

(5)

3.2.3 基于MA建议的策略

MA作为非偏见性中介,掌握整个协商过程中的信息以及以往的协商历史信息,可以从全局宏观上制定协商建议来发送给CA和PA．MA生成建议的公式如下:

(6)

3.2.4 综合协商策略

综合以上策略及折扣率,本文提出综合协商策略(TPM-discount策略),其计算提议和反提议公式如下:

(7)

3.3 Web服务协商过程

在基于议题分类的Web服务协商机制中,首先对议题进行分类,然后针对独立议题和关联议题使用不同的协商协议,并针对独立议题的协商提出了综合时间、对手提议和MA建议的协商策略．算法1描述了本文的Web服务协商过程．

算法1Web服务协商过程

输入:QoS集合

输出:最终协商结果result

1 classify(QoS,E,D);

2 for(I′∈E){//关联议题子集,使用投标算法

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即协商议题进行分类,分为关联议题子集集合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建议的综合协商策略;在关联议题协商中改进了传统的投标算法,提出基于议题分类的投标算法．实验结果表明,与传统协商机制中的协商策略和投标算法相比,本文提出的综合协商策略和基于议题分类的投标算法的协商结果更加精确,协商时间也大幅度减少．

)

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