一种基于效益折扣和议题关联的Web服务协商方法

摘要

本发明涉及服务计算领域，提出了一种基于效益折扣和议题关联的Web服务双边协商模型,引入讨价还价模型中的折扣率，提出协商参与者效益的计算方法，动态描述了协商参与者的得益情况；利用讨价还价模型改进传统协商中的协商协议和协商过程，综合时间代价、对手提议、协商管理者MA建议这几个方面计算和实现协商策略；引入协商管理者参与协商过程，从全局协调和监管协商流程；提出了协商议题关联度的概念，将大部分协商议题转化为简单的易于实现的线性求解方式，降低多维协商的维数和协商复杂度，同时采用联合协商方式求解有关联的协商议题，保证了协商结果的准确度。

说明书

技术领域

本发明是一种利用了效益折扣和议题关联的Web服务协商技术，设计服务计算领域特别是服务 协商领域。

背景技术

随着Internet的发展，以Web服务及面向服务架构SOA(Service-Oriented Architecture)为代表的 新兴分布式计算技术得到了迅猛的发展。通过动态组合多个原子服务形成复杂的大Internet的开放性 要求Web服务能够以丰富、灵活的交互方式向广大用户提供个性化的、可定制的服务。通过服务发 现，服务请求者找到服务提供者集合，通常情况下，这些服务提供者的服务都具有服务请求者所需要 的功能；但不同服务所具有的属性往往差别很大并且某些属性本身具有动态性，因而难以保证服务完 全符合服务请求者要求，为此引入服务协商(Negotiation)使服务的各项属性达成一致，并确保服务对 服务请求者可用且使得双方利益最大化。

当前对服务协商的研究，仅仅从协商参与者期望值和保守值来衡量协商带来的收益情况，忽略了 参与者的时间成本和其他资源成本对收益的影响，这就可能导致协商结果与实际需求(一般协商得到 的收益大于实际收益)未必相同；同时现有研究中协商参与者让步策略主要从时间方面考虑，不能兼 顾全局效益，同时也不能充分利用先前协商经验。此外如何处理多议题是一个难题，传统协商通常有 两种处理多议题的过程类型：独立的和联合的。独立是指双方同时发起多个单议题协商，每个单议题 协商处理一个协商议题，所有协商议题是相互孤立的，没有依赖关系。联合是指双方同时就多个议题 进行协商，所有的协商议题被看作一个整体，协商议题之间存在依赖关系。传统研究忽略了协商议题 间存在的关联，或意识到关联性却没有给出实际解决办法，但是在实际Web服务协商应用中，协商 议题间的关联情况很复杂，往往同时包含有关联的协商议题和没有关联的协商议题。

针对以上问题，本发明基于不完全信息动态博弈理论提出一种新型的服务协商机制。

发明内容

发明目的：本发明针对以上问题，基于不完全信息动态博弈理论提出一种新型的Web服务双边 协商机制，重点研究一个服务提供者和一个服务请求者参与的针对单个服务的双边协商。该机制引入 讨价还价模型中的折扣率，改进效益函数；引入协商管理者参与协商过程，从全局协调和监管协商流 程，通过建议方式综合时间代价、对手提议等，计算和实现让步策略；提出协商议题关联度的概念， 在降低多维协商的维数和协商复杂度的同时保证协商结果的准确度。

技术方案：本发明的Web服务协商技术具体如下：

一种基于效益折扣和遗体关联的Web服务协商方法，针对动态Internet环境下用户要求多变性要 求以及Web服务提供者所提供服务质量的非固定性因素，进行Web服务协商过程。

令表示在时间t，协商参与者a收到另外一个协商参与者a’对议题i的提议，表示在时间 t，协商参与者a收到另外一个协商参与者a’的所有提议，其中t＝0表示初始提议；I＝{i₁，i₂，L i_n}表 示协商议题集合，每一个协商参与者a对协商议题i都有期望值(Desired Value)和保守值(Reserve Value)，分别为每一个协商议题i，在时间t参与者a对提议P_i，t的单议题子效用函数 表示为v^a(P_i，t)。

第一步，服务请求者CA以广播的形式发布协商请求(包括对协商对象的要求、协商内容、协商 议题等)；

第二步，某个服务提供者PA收到广播并给CA发送消息表示愿意参与协商，如果有多个PA回复 协商请求参与协商则形成一对多协商，如果没有PA回复协商请求，则CA重新发送协商请求或者终止 协商；

第三步，PA根据现有的关于议题的知识产生协商议题集的初始提议并发 送给CA；

第四步，CA分析接收到的在时间t-1时的提议消息并通过效益函数计算自己的效益值 并根据使用在要求5中描述的协商策略生成自己的提议 $P_t^{\mathrm{CA}}=\{P_{1,t}^{\mathrm{CA}},P_{2,t}^{\mathrm{CA}},L,P_{n,t}^{\mathrm{CA}}\},$计算己方提议效益值$V_t^{\mathrm{CA}}\left(P_t^{\mathrm{CA}}\right)=\underset{i=1}{\overset{n}{\Sigma }}{w}_i^{\mathrm{CA}}{v}^{\mathrm{CA}}\left(P_{i,t}^{\mathrm{CA}}\right).$为了达到效益最大化，如 果且即本轮PA的提议效益值大于CA提议效益值，或者 对方提议比自己在时间t-1之前的所有提议中的最坏提议(即最远离期望值接近保守值的提议) 要好，则接受提议协商成功；否则，将己方提议发给PA；

第五步，PA分析接收到的提议消息并通过效益函数计算自己的效益值 $V_t^{\mathrm{PA}}\left(P_t^{\mathrm{CA}}\right)=\underset{i=1}{\overset{n}{\Sigma }}{w}_i^{\mathrm{PA}}{v}^{\mathrm{PA}}\left(P_{i,t}^{\mathrm{CA}}\right),$并根据生成自己的提议(t’是t的下一时刻)，计 算己方提议效益值$V_{t^{\prime }}^{\mathrm{PA}}\left(P_{t^{\prime }}^{\mathrm{PA}}\right)=\underset{i=1}{\overset{n}{\Sigma }}{w}_i^{\mathrm{PA}}{v}^{\mathrm{PA}}\left(P_{i,t^{\prime }}^{\mathrm{PA}}\right).$如果对于$\forall P_{i,t}^{\mathrm{CA}},P_{i,t}^{\mathrm{CA}}\ge q_{i,\mathrm{res}}^{\mathrm{PA}}$且$V_t^{\mathrm{PA}}\left(P_t^{\mathrm{CA}}\right)\ge V_{t^{\prime }}^{\mathrm{PA}}\left(P_{t^{\prime }}^{\mathrm{PA}}\right),$即 本轮CA的提议效益值大于PA提议效益值，或者对方提议比自己之前所有提议中的最坏提议要 好，则接受提议协商成功；否则，将己方提议发给CA；

第六步，重复四、五步骤直到协商成功；或者时间用完t＞t_max，协商失败。

前述协商中效益函数的计算方法为：

协商议题集合I＝{i₁，i₂，L i_n}中的每一个协商议题i，在时间t参与者a对提议P_i，t的单议题子效用 函数为v^a(P_i，t)，具体如下：

$v^a\left(P_{i,t}\right)=\frac{P_{i,t}-q_{i,\mathrm{res}}^a}{q_{i,\mathrm{des}}^a-q_{i,\mathrm{res}}^a}{\delta }_t^a$

其中a代表一个协商参与者，利用讨价还价模型中的折扣率表示随着协商时间的增加效益逐 渐减小，通过折扣率可以更贴切有效的描述协商参与者的动态效益。所有议题总的效用函数V是子效 用函数v^a(P_i，t)的加权和：

$V_t^a=\underset{i=1}{\overset{n}{\Sigma }}{w}_i^a{v}^a\left(P_{i,t}\right)$

其中w为协商项在效用函数中的权重，

前述的协商过程协商策略计算方法为：1)基于时间的策略，假定协商允许的最大时间是t_max， 基于时间的让步如下：

$P_{i,t}^a\left(T\right)=q_{i,\mathrm{des}}^a+D_{i,t}^a(q_{i,\mathrm{res}}^a-q_{i,\mathrm{des}}^a)$

其中是基于时间的让步妥协度，其中k^a为a的初始让步妥协度，表示协商 参与者初始提议和期望值相比做出的让步幅度，α为协商参与者自定义的参数，可以反应协商参与者 时间紧迫程度。

2)基于对手提议的策略，只考虑对手提议的影响，a在回合t的让步为

$P_{i,t}^a\left(P\right)=P_{i,t-1}^a+D_{i,P}^a(P_{i,t}^{a^{\prime }}-P_{i,t-1}^a)$

其中为上一轮a的提议，为最新接收的对方提议，表示基于对方提议的 妥协度。

3)基于不完全信息动态博弈的MA建议策略，用MA建议的方式实现不完全信息动态博弈原理， 在此给出MA生成建议的公式如下：

其中，h_i为类似的历史交易中议题i的平均值，为一个随机数，主要根据贝叶斯均衡原 理以随机概率形式产生，同时MA根据相关均衡原理以私人信号的方式将该提议发送给协商中的当前 决策方，用来在宏观上无偏见调整协商双方的让步幅度。

4)综合策略，综合以上的单个让步函数计算协商参与者的实际让步，综合让步函数用TPM表示， 其计算公式如下：

其中在[0，1]区间内，分别表示时间、对手提议、MA建议这三个因素在决定协 商让步幅度时所起作用的比重，同时满足这三个参数的具体大小由协商参与者根 据自身对于不同因素要求的不同自行定义和调整，以满足具体协商需求。

有益效果：本专利提出的基于效益折扣和议题关联的Web服务协商技术，主要从以下几个方面改 进现有协商模型：

1.本模型引入讨价还价模型中的折扣率，改进效益函数，更贴切的描述协商过程中服务提供者和 服务请求者在该过程中收益变化情况；

2.引入协商管理者参与协商过程，从全局协调和监管协商流程，通过建议方式综合时间代价、对 手提议等，计算和实现让步策略，缩短了协商时间；

3.提出了协商议题关联度的概念，通过关联度对协商议题进行分类处理，在降低多维协商的维数 和协商复杂度的同时保证协商结果的准确度。

附图说明

图1为本发明所述的协商模型图；

图2为本发明所述的协商协议图；

图3为本发明所述的整个系统架构图。

具体实施方式

如图3所示，为本发明所述的整个系统架构图。本发明所述的方法进一步描述为：

a由于服务提供者和服务请求者的选择范围存在交集且双方都力争己方利益最大化，因此发起协 商；

b服务提供者PA产生并向提供者CA发送给出初始提议；

c CA收到对方提议后计算该提议的效益值并与己方提议进行对比，如果对方提议产生的效益值 大于己方提议产生的效益值则接受对方提议，协商成功；否则将己方提议发给对方；

d PA收到对方提议后计算该提议的效益值并与己方提议进行对比，如果对方提议产生的效益值大 于己方提议产生的效益值则接受对方提议，协商成功；否则将己方提议发给对方；

e重复c和d步骤知道协商成功或者时间用完。

如图1所示，本发明一种基于效益折扣和议题关联的Web服务协商方法，针对动态Internet环境 下用户多变性要求以及Web服务提供者所提供服务质量的非固定性因素，进行Web服务协商过程：

第一步，由于服务提供者和服务请求者的选择范围存在交集且双方都力争己方利益最大化，因此 发起协商；

第二步，服务提供者PA产生并向提供者CA发送给出初始提议；

第三步，CA收到对方提议后计算该提议的效益值并与己方提议进行对比，如果对方提议产生的 效益值大于己方提议产生的效益值则接受对方提议，协商成功；否则将己方提议发给对方；

第四步，PA收到对方提议后计算该提议的效益值并与己方提议进行对比，如果对方提议产生的 效益值大于己方提议产生的效益值则接受对方提议，协商成功；否则将己方提议发给对方；

第五步，重复c和d步骤知道协商成功或者时间用完；

这里我们采用Agent技术来表示和实现协商参与者，CA(Consumer Agent)代理服务请求者， PA(Provider Agent)代理服务提供者，CA和PA负责和执行自动协商中本方的各种活动；MA(Manager Agent)代理协商管理者，负责整个协商流程的控制、管理并产生和发送信号。

本发明的主要特征在于效益函数的改进、关联度和协商过程中协商策略。其中加入协商议题关联 度，是为了在降低多维协商的维数和协商复杂度的同时保证协商结果的准确度。

如图2所示，所述协商协议具体交互过程为：

1)服务请求者CA以广播的形式发布协商请求(包括对协商对象的要求、协商内容、协商议题等)；

2)某个服务提供者PA收到广播并给CA发送消息表示愿意参与协商，如果有多个PA回复协商请 求参与协商则形成一对多协商，如果没有PA回复协商请求，则CA重新发送协商请求或者终止协商；

3)PA根据自身的情况产生协商议题集的初始提议并发送给CA；

4)CA分析接收到的提议消息并通过效益函数计算自己的效益值并根据生成自己的提议计算己方提议效益值 $V_t^{\mathrm{CA}}\left(P_t^{\mathrm{CA}}\right)=\underset{i=1}{\overset{n}{\Sigma }}{w}_i^{\mathrm{CA}}{v}^{\mathrm{CA}}\left(P_{i,t}^{\mathrm{CA}}\right);$如果$\forall P_{i,t-1}^{\mathrm{PA}},P_{i,t-1}^{\mathrm{PA}}\ge q_{i,\mathrm{res}}^{\mathrm{CA}}$且$V_{t-1}^{\mathrm{CA}}\left(P_{t-1}^{\mathrm{PA}}\right)\ge V_t^{\mathrm{CA}}\left(P_t^{\mathrm{CA}}\right),$即本轮PA的提议效 益值大于CA提议效益值，或者对方提议比自己之前所有提议中的最坏提议(即最远离期望值接 近保守值的提议)要好，则接受提议协商成功；否则，将己方提议发给PA；

5)PA分析接收到的提议消息并通过效益函数计算自己的效益值并根据生成自己的提议(t’是t的下一时刻)，计算己方提议效益值 $V_{t^{\prime }}^{\mathrm{PA}}\left(P_{t^{\prime }}^{\mathrm{PA}}\right)=\underset{i=1}{\overset{n}{\Sigma }}{w}_i^{\mathrm{PA}}{v}^{\mathrm{PA}}\left(P_{i,t^{\prime }}^{\mathrm{PA}}\right);$如果对于$\forall P_{i,t}^{\mathrm{CA}},P_{i,t}^{\mathrm{CA}}\ge q_{i,\mathrm{res}}^{\mathrm{PA}}$且$V_t^{\mathrm{PA}}\left(P_t^{\mathrm{CA}}\right)\ge V_{t^{\prime }}^{\mathrm{PA}}\left(P_{t^{\prime }}^{\mathrm{PA}}\right),$即本轮CA的提议效 益值大于PA提议效益值，或者对方提议比自己之前所有提议中的最坏提议要好，则接受提议 协商成功；否则，将己方提议发给CA；

6)重复4、5步骤直到协商成功；或者时间用完t＞t_max，协商失败。

所述协商中效益函数动态变化，协商议题集合I＝{i₁，i₂，L i_n}中的每一个协商议题i，在时间t参 与者a对提议P_i，t的单议题子效用函数为v^a(P_i，t)，具体如下：

$v^a\left(P_{i,t}\right)=\frac{P_{i,t}-q_{i,\mathrm{res}}^a}{q_{i,\mathrm{des}}^a-q_{i,\mathrm{res}}^a}{\delta }_t^a$

其中a代表协商参与者，是利用讨价还价模型中的折扣率，表示随着协商时间的增加效益逐渐 减小，通过折扣率可以更贴切有效的描述协商参与者的动态效益。所有议题总的效用函数V是子效用 函数v^a(P_i，t)的加权和：

$V_t^a=\underset{i=1}{\overset{n}{\Sigma }}{w}_i^a{v}^a\left(P_{i,t}\right)$

其中w为协商项在效用函数中的权重，

议题间关联度的定义并用于区分不同议题种类；议题i_a与议题i_b之间如果存在一方变化影响另 一方或二者效益值之间互相影响的关系，则定义二者之间存在关联；如果协商议题i_a与议题i_b有关 联，将i_a和i_b定义为关联议题子集I_a，b＝{i_a，i_b}，关联议题子集中子议题的关联度为rd＝关联议题子 集中议题个数-1；若关联议题子集I_a，b，K＝{i_a，i_b，K}中议题i_j与子集外议题i_k之有关联，则将i_k加入 I_a，b，K中，关联度rd＝rd+1；无关联议题关联度为0；

议题间可能存在关联关系，指出独立协商各议题可能造成信息缺失，因此采用联合协商所有议题 的方式，重视了关联性而忽略了可能的独立性。因为议题间是否存在关联并不是确定的，有可能部分 议题之间存在关联，而其他议题则完全独立。因此本文引入协商议题关联度概念来分类处理协商议题。

独立议题可直接进行协商，而关联议题集合内部则需要进行一定的计算和处理；通过深入研究关 联议题之间存在的依赖关系，可以从中提取两种主要关联形式：顺序关联和函数关联：

1)顺序关联，协商议题之间存在一定的先后顺序，某个议题必须等待另外一个议题协商完成后 才能进行协商，具有先后顺序关系的协商议题形成一个有向无环图(Directed Acyclic Graph，简称 DAG)，采用无前驱的顶点优先的拓扑排序算法可以进行处理；

2)函数关联，协商议题之间存在函数关系，某议题的值依赖于相关议题的变化，比如议题i_a与 议题i_b之间存在关联函数i_a＝f(i_b)，这种情况下需要通过将关联函数带入效用函数的方式简化协 商变量和协商计算。

协商过程是根据时间、对手提议以及MA建议这几项因素对己方效用函数或其他方面的影响来进 行决策：

1)基于时间的策略：基于时间的让步是根据时间来调整位于期望值和保守值之间的决策点，假 定协商允许的最大时间是t_max，基于时间的让步如下：

$P_{i,t}^a\left(T\right)=q_{i,\mathrm{des}}^a+D_{i,t}^a(q_{i,\mathrm{res}}^a-q_{i,\mathrm{des}}^a)$

其中是基于时间的让步妥协度，其中k^a为a的初始让步妥协度，表示协商 参与者初始提议和期望值相比做出的让步幅度，α为协商参与者自定义的参数，可以反应协商参与者 时间紧迫程度。

如果对协商参与者a来说v^a(P_i，t)是P_i，t的减函数，即那么随着时间的增加a会逐 步增大协商议题i的值；反之，如果对协商参与者a来说v^a(P_i，t)是P_i，t的增函数，即那么随着时间的增加a会逐步减小协商议题i的值。

2)基于对手提议的策略：假设在时间t，协商参与者a收到另外一个协商参与者a’对议题i的提议 为根据计算a效用为a上一次提议为只考虑对手提议的影响，a在回合t的让 步为

$P_{i,t}^a\left(P\right)=P_{i,t-1}^a+D_{i,P}^a(P_{i,t}^{a^{\prime }}-P_{i,t-1}^a)$

其中为上一轮a的提议，为最新接收的对方提议，表示基于对方提议的 妥协度。

在正常协商过程中，如果对手的提议比较接近自己的心理期望，参与者会减小协商让步幅度，因 为对手让步到自己的期望的概率很大，自己没有必要做出太大让步，从而保证自己利益最大化；反之， 如果对手的提议和自己的期望相差较大，为了防止继续坚持自己的较大期望而导致协商失败，参与者 会做出较大让步，因为如果协商失败，自己的效益就降为0，这是协商双方都不愿意看到的最坏结果。

3)基于不完全信息动态博弈的MA建议策略：用MA建议的方式实现不完全信息动态博弈原理， 在此给出MA生成建议的公式如下：

其中，h_i为类似的历史交易中议题i的平均值，为一个随机数，主要根据贝叶斯均衡原 理以随机概率形式产生，同时MA根据相关均衡原理以私人信号的方式将该提议发送给协商中的当前 决策方，用来在宏观上无偏见调整协商双方的让步幅度。

MA作为一种非偏见性中介，可以获得整个协商过程中的信息，因此通过MA可以确定由和 构成的取值范围同时它掌握了以往协商信息，通过这些信息，它可以从全局掌握协商进度， 从宏观上制定协商建议发送给CA和PA。另外，每个回合MA给CA和PA发送的协商建议是不同的，但 都处在双方最近一次提议的中间某点，这就保证了协商朝着对方提议逐渐逼近，同时也满足了贝叶斯 均衡原理。

4)综合策略：综合以上的单个让步函数计算协商参与者的实际让步，综合让步函数用TPM表示， 其计算公式如下：

其中在[0，1]区间内，分别表示时间、对手提议、MA建议这三个因素在决定协 商让步幅度时所起作用的比重，同时满足这三个参数的具体大小由协商参与者根 据自身对于不同因素要求的不同自行定义和调整，以满足具体协商需求。