服务组合中保障公平性的信誉传播算法

张 涛,马建峰,莫 若,李 琦,习 宁

(西安电子科技大学计算机学院,陕西西安 710071)



服务组合中保障公平性的信誉传播算法

张 涛,马建峰,莫 若,李 琦,习 宁

(西安电子科技大学计算机学院,陕西西安 710071)

摘要:在面向服务的环境中,服务的不透明性、组合结构的复杂性以及用户评价的主观性使得用户难以对组件服务进行有效的信誉评估.针对此问题,提出适用于服务组合的信誉传播算法,将复合服务的信誉评估值公平地传播到各个组件服务.首先,将复合服务建模为Beta混合模型,通过最大期望算法学习复合服务中各个组件的责任及信誉度.其次,基于Shapley值的合作博弈模型计算各个组件服务对复合服务的贡献度,确保所组合的各个服务不会受到额外的奖励或惩罚.最后,理论分析与实验结果表明该算法在保证公平性的前提下,能够正确地将用户提交的信誉评估层次化传播到各个组件服务.

关键词:面向服务的架构;服务组合;Web服务;信誉传播;公平性

在面向服务架构(Service-Oriented Architecture,SOA)中,服务表现为自治、平台独立的可重用计算实体,能够以统一的标准进行描述、发布、发现和组合,为多机构跨平台软件开发提供基础.面向服务架构的主要目标是在开放的网络环境中利用Web服务自动化构造满足业务逻辑的复杂应用[1].然而,开放网络内在的不确定性使用户需要承担未知服务交互的风险.基于信誉的信任机制能够对存在利益交互一方的服务质量(Quality of Service,QoS)进行度量,激励合法的服务行为,为用户提供参考信息以降低与恶意服务交互的几率,从而降低开放网络中的交互风险[2-3].

然而,在服务组合中对组件服务的信誉评估十分困难.首先,由于服务的不透明性[4],用户无法得知评价对象是原子服务或是复合服务,从而无法全面进行各个组件的信誉评估[5].其次,服务组合结构的复杂性导致组合结构服务质量的多样性,需要针对不同服务质量特性建立不同的信誉计算规则[6].最后,即便用户能够掌握复合服务组合结构及其服务质量特性,其对各个服务组件评价的主观性也导致难以实现组件服务信誉分配的公平性.因此,在服务组合中需要将用户对复合服务的评估值公平传播到所构成该服务的各个组件.

目前对服务组合的信誉传播问题已有了初步研究.文献[7]最先定义服务组合中公平信誉传播需满足如下两规则:组件服务不应由于其他组件较差的信誉而受到惩罚;组件服务不应由于其他组件较好的信誉而受到奖励.并提出服务组件重要性与服务质量一致性相结合的信誉分配算法.文献[8]依据服务组件历史信誉值和服务质量,建立补偿函数实现用户评价值分解.文献[9]结合信任趋势与信誉评估值,建立层次结构与水平结构的信誉传播方法.然而,上述工作均在服务组合结构可观测的前提下进行组件信誉度量,缺少对所提方案信誉传播公平性的理论证明.此外,文献[10]基于Shapley值的数学特性,提出公平保障的信誉传播方法.其工作虽然在理论上保证了公平性,然而该方法假设服务组件服务质量完全可观察,并需要用户提供对各个组件服务质量的最佳值和最差值的数学期望,仍未解决服务不透明性所造成的信誉评估问题.

针对上述问题,笔者从服务组合的特征出发,提出适应于Web服务组合的公平信誉传播算法(FGRP).首先针对服务不透明性及组合结构特点,将复合服务建模为Beta混合模型,利用最大期望算法学习出各个服务组件责任和信誉度.其次,基于Shapley值的合作博弈模型计算组件贡献度,并依据该贡献度将用户对复合服务的主观评价层次化分配到各个服务组件,保障信誉传播的公平性.

1 FGRP信誉传播算法

1.1 服务信誉表示

面向服务架构的主要特性是利用平台独立的服务,通过组合的方式为用户提供增值的服务.复合服务通常作为整体与用户交互.在特定情况下(如遗产系统),服务以黑盒的方式提供给用户,用户难以分析其组合逻辑的依赖关系.为了评估各个组件服务对复合服务信誉的贡献度,算法用Beta概率模型[11]建模所交互服务的信誉记录.

Beta概率模型将信誉表示为二元证据模型θ=〈α,β〉(α≥0,β≥0),其中α和β分别表示满意和未满意的交互次数.其概率密度函数表示为

服务si的信誉表示为Beta概率模型的数学期望,即

1.2 组件服务责任及信誉的统计学习

不透明性表示用户无法区分所交互的服务是原子服务,或是多个服务所组成的复合服务,从而无法对组件服务直接进行信誉评估.为了将复合服务的评价值公平地分配到各个组件服务,在获得复合服务信誉的观察之后,利用有限混合模型统计学习出各个组件的责任和信任度,从而解决服务的不透明性.

有限混合模型将每个数据对象建模为混合分支,合并不同混合分支为描述整个数据特征的混合分布,通过统计实现数据识别.笔者用Beta混合模型建模复合服务的信誉混合.在由K个组件服务构成的服务组合中,组件服务si建模为参数θi=〈αi,βi〉的Beta概率模型,则复合服务的Beta混合表示为

最大期望算法通过期望步(E-step,E步)和极大化步(M-Step,M步)两过程的不断迭代,最终收敛到似然函数的最优解,其执行流程如下.

重复E步和M步,直至参数θnew下对数似然函数收敛.此时,参数πn ew i和θnew i分别表示当前复合服务中组件服务si的责任和信誉度的统计值.

1.3 基于Shapley值的贡献度计算

算法FGRP引入符号ωi,ωi∈(0,1],表示组件服务si在服务组合中执行的概率.服务组合结构主要包括确定组合模式(包括顺序、循环、并发等)和概率组合模式两类[4,6].在确定组合模式中,各个组件按照组合顺序依次执行,其ωi=1.在概率组合模式中,组件执行概率表示为责任值归一化后的比率.例如,假设服务集si,j∈{si,1,…,si,m},构成概率模型,其责任值πi,j∈{πi,1,…,πi,m},则概率ωi,j∈{ωi,1,…,ωi,m}=πi,j/ (πi,1+…+πi,m).在得到组件服务执行概率及证据模型后,服务组件的组合信誉值根据文献[12]提出的聚合规则进行计算.

算法FGRP依据组件服务si对复合服务的贡献度Δi(c)进行信誉传播.为了保证公平性,算法利用合作博弈理论的Shapley值[13]计算各个组件服务si的贡献Δi(c),表示为

1.4 信誉传播

根据上述分析,算法FGRP在保障公平性的基础上,能够有效地解决由服务不透明性、组合结构复杂性和用户评价主观性所造成的信誉传播问题,其算法流程如下:

步骤1(服务不透明性) 通过观察值学习各个组件的责任及信誉度,见1.2节.

步骤2(组合结构复杂性) 根据Shapley值计算组件服务在组合结构下对复合服务的贡献度,见1.3节.

步骤3(用户评价主观性) 将用户的主观评价根据贡献度传播到组件服务之上,见本节前段.若该组件仍是复合服务,则转至步骤1.

2 FGRP分析

2.1 FGRP特性分析

算法FGRP基于Shapley值进行组件服务的信誉分配,将用户对复合服务的主观信誉评估公平传播于所组成的各个服务组件.因此,算法FGRP能够继承Shapley值的特性.

对称性(Symmetry) 对于∀T∈c{si,sj},若R( c|T∪{si} )=R ( c|T∪{sj} ) ,则Δi(c)=Δj(c).

贡献平衡性(Balanced Contribution) 对于∀si,sj∈c,Δi(c)-Δi( c|c{sj} )=Δj(c)-Δj( c|c{si} ),其中Δi(c|T)表示在复合服务c的组合结构中,组件服务si对给定子集T的贡献度.平衡性确保各个组件的贡献度在各个组件中能够平均分配,从而保证服务组件的信誉传播的公平性.

2.2 FGRP公平性分析

通过组件信任度的变化证明算法FGRP的公平性.在证明中,令Rt(s)、Rt′(s)和et(s)、et′(s)分别表示在连续等长时间t、t′时组件服务s的信誉值和证据数,则信誉差和证据差分别表示为ΔR(s)=Rt(s)-Rt′(s)和Δe(s)=et(s)-et′(s).首先考虑当Δe(s)=0,ΔR(s)＞0时的信誉变化情况.对于任意的组合结构,当单个组件信誉提升时,以下命题始终成立.

命题1 组件服务si信誉值的提升不会导致复合服务c信誉值的下降[8],即

同时,对于∀sj∈c,sj≠si,ΔR(sj)=0时,由式(7)可得对称性表示若不同组件与其他组件组合时信誉度相同,则其贡献度相同.

其中,ΔR(c|si)=0,表示组件服务si的信誉提升并未导致复合服务c的信誉提升.例如,组件服务sA和sB以概率模式组成复合服务c,并且ΔR(sA)＞0.若复合服务中sA的执行概率较低,则存在特定时间t中未提升复合服务信誉的可能性,从而ΔR(c|sA)=0.为了表示复合服务信誉值改变,提出有效信誉提升的定义,当信誉下降时能够得出类似结论.

定义1(有效信誉提升) 组件服务si的有效信誉提升表示其信誉提升导致复合服务c的信誉提升,即

根据定义1,可得如下推论.

推论1 给定复合服务c={s1,…,sK}以及T∈c{si},若R(si)＞R(c),则

下面,考虑组件服务信誉的改变对信誉传播配额的影响,并证明算法FGRP的公平性.

引理1 若组件服务si具有的有效信誉提升,则v(si)＞Ru.

证明 令T∈c{si},考虑如下两种情况:

情况1 若T=Ø,则ΔR( c|T∪{si} )-ΔR(c|T)=ΔR( c|{si} )-ΔR(c|Ø)=ΔR( c|{si} )＞0;

情况2 若T≠Ø,根据推论1,可得ΔR( c|T∪{si} )-ΔR(c|T)≥0.

根据式(5),可得Δi(c)＞0.因此,由式(6),可得v(si)＞Ru.证毕.

引理2 对于∀sj∈c,sj≠si,若Rt(si)＜Rt′(si),且Rt(sj)=Rt′(sj),则vt(si)＜vt′(si).

证明 令T∈c{si},已知∀sk∈c,Δe(sk)=0,则ΔR(c|si)＜0且ΔR(c|sj)=0.考虑如下两种情况:

情况1 若T=Ø,则Rt( c|T∪{si} )-Rt′(c|T∪{si} )=Rt(c|si)-Rt′(c|si)＜0;

情况2 若T≠Ø,根据命题1,可得Rt( c|T∪{si} )-Rt′(c|T∪{si} )≤0.

此外,对于∀sj∈c,sj≠si,已知Rt(sj)=Rt′(sj),则对于∀T,可得Rt(c|T)=Rt′(c|T).由

引理3 ∀sj∈c,sj≠si,若Rt(si)＞Rt′(si),且Rt(sj)=Rt′(sj),则vt(si)＞vt′(si).

引理4 ∀sj∈c,sj≠si,若Rt(si)=Rt′(si),且Rt(sj)=Rt′(sj),则vt(si)=vt′(si).

引理3和引理4的证明与引理2的证明类似,在此省略.

上述引理证明了在证据数目不变(Δe(s)=0)的条件下信誉传播的公平性.当证据数Δe(s)≠0时,首先假设单个组件的证据数增加或减少时信誉传播配额的变化下的公平性,之后利用归纳法证明当多个组件证据数的信誉传播的配额变化.其证明与引理2的证明类似,在此省略.

定理1 在服务组合中,所提出算法能够公平地将信誉传播到组件服务之中.

证明 根据上述引理,定理1成立.

3 仿真评估

3.1 实验环境

以图1为例对不同结构下算法FGRP信誉传播的公平性进行实验评估(实验以顺序结构为例说明确定结构下的信誉传播结果).在图1中,假设用户希望将汉语翻译至卢森堡语,但网络中并不存在直接的翻译器.服务提供商通过组合汉语至英语(Chi-to-Eng)、英语至德语(Eng-to-Deu)、德语至卢森堡语(Deu-to-Lux)的组件服务实现翻译功能.同时,存在3个不同服务商GOG、MIC和BAI来提供英语至德语的翻译服务,其调用概率分别为60%、20%和20%.

图1 汉语至卢森堡语翻译服务

两组实验分别对不同组合结构进行独立实验评估.每组实验生成100组观察值,并利用文献[14]方法对最大期望算法进行初值选取以减少组件责任及信誉度计算的误差.同时,实验与特征类似的文献[7]方案进行对比.对比中令用户评价值Ru=0.7,Shapley值计算常数L= R(c).其他参数与实验结果如表1和表2所示.

表1 确定组合模式的信誉传播

表2 概率组合模式的信誉传播

3.2 评估结果

表1描述图1中顺序模式服务s1、s2和s3信誉传播实验结果,其包含信誉评估较好的服务s1和较差的服务s3以及中性服务s2.如表1所示,在算法FGRP中s1始终获得正向贡献度,而s3获得负向贡献度.此外,当中性服务证据值改变时(第2行数据),复合服务信誉度向其逼近,其他服务的贡献度因此减少,而算法FGRP能够有效地反映出贡献改变的情况并计算正确的传播值.最后,当特定组件信誉改变时(第3行数据),其余组件的贡献度也会相应改变,而在文献[7]提出的算法中,在各个组件的信誉度不变而证据值变化时,其传播值不变,从而无法正确表征组件的贡献度.

对于确定模式组合结构,实验中各算法统计学习的最大误差为22%.这是由于在确定性模式中,Beta混合模型的概率分布叠加在特定观察值下呈现单峰分布,从而无法很好地进行统计学习.由于算法引入一致性因子μ,μ∈(0,1),在一定程度上能够减少误差带来的影响,实现公平的信誉传播.此外,表1还能够证明Shapley值的有效性,即正向贡献和与负向贡献和始终相等.

表2描述了图1中概率模式服务s4、s5和s6信誉传播的实验结果.由于概率组合模式特性与最大期望算法的乘法叠加特性类似,在算法中统计学习的最大误差仅为4.6%.表2结果与表1结果类似,均能够很好地反映各个组件贡献度及信誉传播的公平性.而文献[7]所提出算法由于不支持概率组合模式,其传播值无法表征信誉传播的公平性以及组件证据数变化时传播值变化的正确性.

3.3 方案对比

算法FGRP与相关信誉传播算法的对比如表3所示.首先,FGRP通过统计学习方法对组件的责任及信誉度进行学习,不依赖已有算法对服务组件信誉或服务质量值可观察性的假设,从而解决了不透明性问题.其次,算法FGRP不仅考虑文献中的确定性模型,而且支持对部分工作[7-9]中缺少的概率模式的信誉传播,从而全面解决了服务组合结构的复杂性问题.再次,FGRP无须用户对最优和最差情况组件的服务质量值进行估计[10],将用户对复合服务的评价值公平传播到各个组件,从而解决了用户评价的主观性问题.最后,笔者基于Shapley值特性对算法FGRP进行证明,确保所提算法的公平性.

表3 信誉传播方案对比

4 结束语

针对服务的不透明性、组合结构的复杂性以及用户评价的主观性所造成的信誉传播问题,笔者提出一种适用于服务组合的公平信誉传播算法,即FGRP.该算法具有如下特征:基于Beta混合模型对组件责任及信誉度学习,解决服务的不透明性;对确定组合模式与概率组合模式分别建模,解决服务结构组合的复杂性;基于合作博弈Shapley值进行服务贡献计算,消除用户评价的主观性.算法FGRP在无须用户提供服务质量估计值的基础上,实现了复合服务到组件服务信誉的层次化公平传播.理论分析与实验结果均能够证明所提方法的合理性和有效性.

下一步研究工作的重点首先在于提高信誉传播的精确性,其主要来源于两个方面:减少由于概率叠加所造成的统计误差;服务信誉变化的动态性对信誉传播变化的影响.其次,对于海量服务的贡献度计算,Shapley值在计算时需要考虑所有组合情况,因而存在开销过大的问题.所以,提高计算性能也是将来研究需要考虑的问题之一.

参考文献:

[1]PAPAZOGLOU M P,TRAVERSO P,DUSTDAR S,et al.Service-oriented Computing:a Research Roadmap[J].International Journal of Cooperative Information Systems,2008,17(2):223-255.

[2]JØSANG A,ISMAIL R,BOYD C.A Survey Of Trust And Reputation Systems For Online Service Provision[J].Decision Support Systems,2007,43(2):618-644.

[3]孟宪佳,马建峰,卢笛,等.面向可信和行为模式匹配的两层服务选择方法[J].西安电子科技大学学报,2014,41(4): 198-204.MENG Xianjia,MA Jianfeng,LU Di,et al.Trust and Behavioral Modeling Based Two Layer Service Selection[J].Journal of Xidian University,2014,41(4):198-204.

[4]ZHANG T,MA J F,SUN C,et al.Service Composition in Multi-domain Environment under Time Constraint[C]// Proceedings of the IEEE 20th International Conference on Web Services.Piscataway:IEEE Computer Society,2013: 227-234.

[5]ZHANG T,MA J F,XI N,et al.Trustworthy Service Composition in Service-oriented Mobile Social Networks[C]// Proceedings of the IEEE 21th International Conference on Web Services.Piscataway:IEEE Computer Society,2014: 684-687

[6]ZHANG T,MA J F,LI Q,et al.Trust-based Service Composition in Multi-domain Environments under Time Constraint[J].Science China Information Sciences,2014,57(9):092109(16).

[7]NEPAL S,MALIK Z,BOUGUETTAYA A.Reputation Propagation in Composite Services[C]//Proceedings of the IEEE International Conference on Web Services.Piscataway:IEEE,2009:295-302.

[8]Da SILVA I,ZISMAN A.Decomposing Ratings in Service Compositions[C]//Lecture Notes in Computer Science:8274 LNCS.Heidelberg:Springer Verlag,2013:474-482.

[9]SADEGHI R,AZGOMI M A.A Method for Fair Propagation of User Perceptions for Trust Management in Composite Services[J].Service Oriented Computing and Applications,2015,9(2):157-176.

[10]LIU A,LI Q,ZHOU X F,et al.Rating Propagation in Web Services Reputation Systems:A Fast Shapley Value Approach[C]//Lecture Notes in Computer Science:8421 LNCS.Heidelberg:Springer Verlag,2014:466-480.

[11]HANG C W,SINGH M P.Trustworthy Service Selection and Composition[J].ACM Transactions on Autonomous and Adaptive Systems,2011,6(1):5-22.

[12]LI L,WANG Y.Trust Evaluation in Composite Services Selection and Discovery[C]//Proceedings of the IEEE International Conference on Services Computing.Piscataway:IEEE Computer Society,2009:482-485.

[13]SHAPLEY L S.Theory of GamesⅡ[M].Princeton:Princeton University Press,1953:307-317.

[14]BOUGUILA N,ZIOU D,MONGA E.Practical Bayesian Estimation of a Finite Beta Mixture through Gibbs Sampling and Its Applications[J].Statistics and Computing,2006,16(2):215-225.

(编辑:郭 华)

Fairness-guaranteed reputation propagation in Web service composition

ZHANG Tao,MA Jianfeng,MO Ruo,LI Qi,XI Ning
(School of Computer Science and Technology,Xidian Univ.,Xi’an 710071,China)

Abstract:In service-oriented environment,it is difficult to evaluate component services because of the opaque characteristic of composite services,the complex invocation structures and the subjective reputation rating of service consumers.To address these issues,this paper proposes a reputation propagation algorithm for service composition,in which the subjective ratings can be fairly propagated to each component service.The algorithm first models service composition as the Beta-mixture,and learns the reputation and responsibility of each component by the EM algorithm.Then,based on the characteristics of Shapley values in cooperative gaming theory,the algorithm computes the contribution of each component to its composition,ensuring that no component would obtain extra rewards or punishments.Finally,theoretical analysis and experimental results demonstrate the fairness of the algorithm to hieratically propagate the consumer’s rating to each component service.

Key Words:service-oriented architecture;service composition;Web services;reputation propagation; fairness

作者简介:张 涛(1986-),男,西安电子科技大学博士研究生,E-mail:tzhang@stu.xidian.edu.cn.

基金项目:长江学者和创新团队发展计划资助项目(IRT1078);国家自然科学基金委员会-广东联合基金重点基金资助项目(U1135002);国家科技部重大专项资助项目(2011ZX03005-002);国家自然科学基金资助项目(61370078)

收稿日期:2014-10-17 网络出版时间:2015-05-21

doi:10.3969/j.issn.1001-2400.2016.02.013

中图分类号:TP309

文献标识码:A

文章编号:1001-2400(2016)02-0070-07

网络出版地址:http://www.cnki.net/kcms/detail/61.1076.TN.20150521.0902.010.html