网构软件系统中基于信誉激励的协作博弈模型

印桂生，王姝音，刘杰，董宇欣

(哈尔滨工程大学计算机科学与技术学院，黑龙江哈尔滨150001)

为了解决动态的Internet环境下分散的软件实体的共享、集成和复用［1-2］，网构软件这种具有新特征的软件应运而生，它是一种具有自底向上的自主性、协同性、演化性［3］等特征的软件新形态，其运行依赖于开放、动态的网络环境［4］，当前，如何在开放、动态环境下保障网构软件的可靠性与可信性已经成为信息化社会的重大需求.

网构软件系统属于开放网络环境下的分布式系统，目前，对于分布式系统可信性的研究主要集中在可信管理与可信评估两方面.可信管理［5］的本质是一种基于认证和授权的访问控制模型与方法.信任评估模型［6］则是以实体间的推荐信任关系为基础，结合自身经验对实体可信度做出评价，然后依据可信度进行决策.信任评估模型主要可分为基于全局信任度模型与基于局部信任度模型.在基于全局信任度的信任模型中［7-9］，节点通过相邻节点间相互满意度的迭代获取其他节点全局的信任度.此类模型往往比较复杂、通信代价高.现有的分布式系统的信任模型大多是局部信任度模型［10-11］，这类模型通过采取局部广播手段，询问有限的其他节点以获取某个节点的可信度.此类模型的典型如PeerTrust模型［12-13］、DyTrust模型［14］等.上述分布式系统中的可信模型在解决网构软件系统中信任问题时稍显不足，其原因在于:网构软件系统中的实体可以根据网络环境的变化而发生动态演化，具有自组织演化特性.以上模型对于软件实体的演化性考虑较少.文献［15］对网构软件中实体的信任关系进行了形式化建模.文献［16］则提出了一种面向网构软件的信任驱动模型，使信任管理和信任关系的在线演化得以实现.以上模型的不足在于在演化过程中不能支持实体间信任关系的自主形成.实际上，网构软件系统中软件实体在协作过程中所具有的理性思维使其协作行为呈现出博弈特性.基于此思想，本文提出一种网构软件系统中实体间的协作博弈模型，利用博弈理论对网构软件系统中实体节点的协作过程进行分析，建立节点间协作的博弈模型，并在模型中引入实体节点的信誉值，用以建立实体间有效的激励合作机制，促进实体节点自主进行协作.

1 基于信誉激励的协作博弈模型

网构软件的概念最早由我国北京大学的杨芙清教授、梅宏教授所提出.它指的是一种具有柔性、多目标、连续反应式的新系统形态［3］，它能够根据外部环境变化来动态调节自身参数与指标进而进行演化.网构软件的基本元素是具有主体化特征的软件实体，这种软件实体可以是构件实体、Web服务、软件Agent等，这种软件实体以开放、自主的方式存在于Internet的各个节点之上，任何一个软件实体可在开放的环境下通过某种方式加以发布，并以各种协同方式与其他软件实体进行跨网络的互连、互通、协作和联盟，从而形成一种与当前的信息Web相类似的Software Web.在交互过程中，软件实体需考虑自身与他人的损失与得益，使得整个交互过程成为一种博弈过程，因此可以用博弈论对网构软件系统中实体的协作过程进行建模.

1.1 单阶段博弈模型(GBM)

在利用博弈理论分析网构软件系统时，将网络中的实体看成具有有限理性的博弈参与者，将演化过程中实体协作策略的选择看成一个复杂的博弈过程，博弈者的策略就是实体节点采取的行动，而参与者的收益函数则是实体节点根据所采取行动而能获得的收益.根据此思想，首先给出网构软件系统中实体节点单阶段协作博弈的基本式.

定义1 在每个博弈阶段，实体节点间的单阶段信任博弈可定义为三元组D=(G，S，u).G表示系统中的实体节点集合，也是博弈的参与者:Gi={i，N-i}.其中N-i表示除实体节点i外的其他博弈参与者.S表示参与博弈的实体节点的策略集合S={Si，S-i}，Si={协作，不协作}为实体节点 i所有策略的集合，s={si，s-i}为博弈者的策略组合;u为参与者的收益函数，为在某一时隙t内，博弈者在策略组合下所获得的收益.

定义2 在某一时隙t内，实体节点i所采取的一系列行动策略表示为表示除i外的其他博弈者的行动策略组合.这种策略的组合关系如表1所示.

表1 博弈实体策略组合关系表Table 1 The strategy combination relation of the game players

在表1中，a、b、c、d等用来表示除节点 i以外的其他实体节点(统一定义为N-i)，在每个时隙t中，节点i与其他节点分别进行交互，co表示协作(cooperate)，dis表示不协作(dis-cooperate).表1中可以看出，在时隙t1内，节点i的策略组合为{协作，协作，不协作，协作}，与i进行协作的其他节点的策略组合为{不协作，协作，协作，协作}.这里用sti表示由节点i的行动策略组合到实数集的一个映射，即→R，它可以反映出节点i在某一时间段t内采取协作策略的几率，的取值范围为［0，1］.值越大，代表实体节点选择合作的几率越大.

网构软件系统中实体节点协作的博弈过程可以描述如下:实体节点在协作的过程中，既可以是协作的发起者，也可以是协作的响应者，例如，实体节点i需要实体节点a提供a的某种服务以完成协作时，i就为协作的发起者，而a为协作的响应者.同时，实体节点a需要节点i的数据以完成该次协作，实体节点a变成协作的发起者，而i变为协作的响应者.这种协作关系类似于P2P关系，即实体节点同时作为客户端和服务器端进行协作.当实体节点i作为协作的发起者提出协作请求，并得到节点a的协作响应后，由于成功完成一次协作，实体节点i可获得一定的收益λ，而节点a由于响应实体i的请求，牺牲了一定的资源，并且承担了i是恶意节点的风险，因此要用掉开销 ，这里λ＞ρ＞0，λ和ρ均为常量参数.可以看出，如果实体节点i和a在对方提出协作请求时能互相响应对方，则均可获得收益λ-ρ，如果节点i只获得其他节点的协作响应，而不去响应其他节点的协作请求时，可以获得收益λ.同理，如果节点i只响应其他节点的协作请求，而不能获得其他节点的协作响应时，要付出收益ρ，如果实体节点间互不响应时，其收益均为0.因此，网构软件系统中实体节点间博弈的收益矩阵可以表示为图1.

图1 协作博弈模型的收益矩阵Fig.1 The payoffmatrix of the cooperative game

1.2 博弈模型的Nash均衡

由定义2可知，在时隙t内，除i以外的实体节点选择协作策略的概率为st-i，选择不协作策略的概率为1-st-i，因此节点i选择协作策略的收益为

节点i选择不协作策略的收益为

节点i选择协作策略的概率sti，节点 i选择不协作策略的概率1-sti，因此实体节点i的期望效用函数可表示为

博弈D的Nash均衡为:在给定其他参与者的最优策略st*-i下，能最大化其效用函数的协作博弈策略st*i，即

由式(2)可以看出，在博弈的过程中，实体节点的策略选择可以相互影响和制约.由于实体节点具有自私特性，为追求自身收益最大化，每个节点都会选取较小的sti值，使 ρst

i尽量小，即节点在被请求协作的情况下趋向于选择“不协作”策略，这时采取“不协作”策略将成为系统中节点的纳什均衡策略，而此时系统的整体收益却接近于零，网构软件系统的整体性能会受到严重的影响，这是一个典型的囚徒困境博弈模型，为了解决该问题，需要通过建立有效的激励机制来刺激实体节点采取合作行为.

1.3 修正的进化博弈模型(GBDTM)

为了在网构软件系统中运用博弈理论建立节点间的激励机制，需要找到一种对所有实体节点都有利的策略，以使实体节点在博弈的过程中最终达成共识，都能获得较高的收益，从而使整个网络能够达到一种Nash均衡状态［17］，而且保证帕累托有效.

实际上，网构软件系统还具有下述性质:1)节点的协作行为在时间上具有随机性及不确定性，即节点可能在任意时刻向其他节点发起或接受到其他节点的协作请求.实体节点之间将重复进行博弈，但各节点并不能确定博弈将在哪一阶段结束;2)实体节点对每次协作的结果都有记录，即实体节点可以掌握博弈的历史信息.因此，网构软件系统中实体节点的协作博弈可用进化博弈的思想进行建模.

进化博弈理论中，具有有限理性的参与者在重复博弈的过程中，可以不断的进行学习并调整策略，以使博弈中参与者最终达成共识，使系统整体的效用最大化.进化博弈的学习过程［18］可以做如下描述:在每一阶段的博弈g中，每一个参与者i=1，2，…，N选择行动ai∈A，每阶段博弈产生该阶段的收益xi，参与者i可以观察到一些信息ω∈Ω，而这些信息并没有被完全预期到，于是参与者通过更新信念规则β:B←Ω来修正自己的信念β°i∈B，最后按照更新后的决策规则f:A←B根据目前的信念再次选择行动.

为了建立网构软件系统中实体节点的激励合作机制，需借鉴进化博弈的思想，即:使参与博弈的实体节点在不断的重复博弈中总结经验，动态的学习并调整策略.为了实现实体节点这种动态学习改变策略的博弈过程，并且对实体节点的策略选择进行激励，使不合作的节点只能在短期获得较高的收益值，长期的不合作行为会导致节点收益值减少，这里在原有的网构软件博弈模型中加入新的要素T，即实体节点综合信誉值Tt-ii，将该信誉值作为决策者在时刻t观察到的信息，反馈给博弈实体的收益函数.博弈者在每进行一次博弈后，其综合信誉值都在发生变化，收益函数受该信誉值影响而改变，因此决定了博弈者行动策略的动态调整.而策略的调整又会使博弈者的信誉值发生变化，该变化作为博弈者新观察到的信息，来决定下一次的行动.这种通过观察信誉值变化动态学习调整策略的过程如图2所示.

图2 基于信誉激励的进化博弈过程Fig.2 The process of evolutionary game based on trust

定义4 在每个博弈阶段，基于信誉激励的进化博弈可定义为四元组 D=(G，S，u，q(·)).G 表示系统中的实体节点集合，也是博弈的参与者:Gi={i，N-i}.其中 N-i表示除实体节点 i外的其他博弈参与者.S表示参与博弈的实体节点的策略集合S={Si，S-i}，Si={sij}为实体节点 i所有策略的集合.s={si，s-i}为博弈者的策略组合;u为参与者的收益函数，ui(si，s-i为博弈者策略组合下所获得的收益.q(·)为激励惩罚因子，T为实体节点i的信誉值，T值越大，表示节点i的信誉度越高，T∈［0，1］.

在引入信誉值作为激励惩罚因子后，网构软件系统中实体节点协作时的博弈过程可以重新描述为:当实体节点i提出协作请求并得到实体节点a的协作响应后，实体节点i可获得一定的收益 ，而节点i响应实体节点a的请求，要用掉开销ρ，同时，实体节点i具有信誉值T，该信誉值作为激励惩罚因子可动态调节响应协作请求所用的开销ρ.信誉值高的实体节点更容易获得其他实体节点提供的服务，因此使其开销减小，这可以看作是对行为良好的实体节点的奖励.而信誉值低的节点由于难以获得其他节点的协作而使其开销增大，作为对具有不良行为节点的惩罚.因此，网构软件系统中实体节点间基于信誉激励的收益矩阵可以表示为图3.

图3 基于信誉激励的协作博弈模型的收益矩阵Fig.3 The payoffmatrix of the trust-based cooperative game

定义5 博弈者i在某时隙t内的期望效用函数的修正表达式为

用实体节点的信誉值对节点的收益函数进行修正，可以有效限制节点的自私行为.假若节点i减小选择协作策略的概率，节点的信誉会降低，反而会增大，根据不同的信誉值评估模型来选定合适的ε值后，节点i单方面减小时，节点 i的最终收益值u也会减小.这样通过运用信誉值来修正博弈过程中的收益函数，可以有效的激励实体节点合作.收益函数修正后，如果节点信誉值增加，收益值也会随之增加，而信誉值较低的节点随着时间的推移，收益函数值将会不断降低.

引入激励惩罚机制对效用函数进行修正后，博弈D的Nash均衡可表示为

采用激励机制后，大多数实体节点最终将趋于选择策略“合作”，网络将会达到Nash均衡状态，形成一种节点之间互相合作的网络系统.

2 信誉值评估模型DyTrust

本文的进化博弈模型中采用DyTrust模型作为信誉值的评估模型，该模型中运用近期信任、长期信任、反馈信任等信任度量的相关参数，增强了节点行为改变的动态适应能力以及对反馈信息的聚合能力.

在时间帧t内，节点j对节点i的信任度量可分为直接信任和间接信任2部分，节点j对节点i的信任度量记为Rtji;则Rt

ji可表示为式中:Dtji表示在时间帧t中，节点j对节点i的直接信任;Crjr表示节点j对提供间接信任值的节点r的反馈可信度;I(i)表示时间帧t中，所有和节点i进行过交互的节点集合(不包括节点j);α表示信任评价的信心因子，取值满足0≤α≤1.

直接信任值可定义为式中:eji为节点j对节点i的交互满意度的评价，0≤eji≤1;m表示在时间帧t中，节点i和节点j之间交互的总次数.

在经过连续多个时间帧后，节点j对节点i的信任度量可以用节点j对节点i的2个信任度量参数:近期信任、长期信任来表示.

设节点j对节点i的近期信任值STji，该值可定义为

式中:β为信任学习因子，β越大，先前的经验就越容易被遗忘.

设节点j对节点i的长期信任值LTji，可以利用式(8)进行计算:

设在时间帧t，节点j和节点r的公共交互节点集合用Cset(j，r)表示，节点j和节点r对公共节点度量的差异dt

ji可以定义为

设节点j所能容忍节点r的最大偏差为θ，则反馈可信度的计算公式为

节点r如果提供诚实反馈，会提高其反馈可信度;提供不诚实反馈，则会降低其反馈可信度.

节点j对节点i的信任值Ttji取近期信任值与长期信任值中的较小值，即

最终，节点i的综合信誉值是在某一时间段里，与i有过交互历史的节点对节点i做出的综合评价.可表示为式中:Cset(-i)表示时间帧t内，与节点i有过交互的节点的集合.

利用DyTrust信任评估模型得出节点i的综合信誉值T，作为进化博弈模型中的参数，有效的将DyTrust信任模型的反馈控制机制与进化博弈论中的节点激励机制相结合，不但可以增强信任模型的动态适应能力，还可以促进网构系统中的构件节点自主的进行协作.这是单纯使用DyTrust信任模型所不能解决的.

3 实验验证

本文对上述GBDTM模型进行了试验仿真.模拟实验初步验证了该修正模型的合理性.模拟实验初始场景中，在局域网上，设置了500个节点，要求每一个节点都分别通过无激励的博弈方法、基于DyTrust信任评估方法、以及GBDTM方法进行协作交互.

设效用函数中参数 ε=3，λ=120，ρ=80，α=0.5，β =0.5，博弈交互重复100 次.图4 为3 种方法成功交互次数数目对比图，其中，DyTrust表示用无激励的博弈方法进行交互;GBDTM表示用GBDTM方法进行交互.从图中可以看出，利用无激励博弈方式进行交互时，随着交互总次数的增加，成功交互次数反而下降，这充分证明了非合作博弈中节点存在“自私”行为.在利用DyTrust模型进行交互时，随着交互次数的增加，节点的交互成功次数不断波动，DyTrust模型能有效反应网络节点的信任值，使网络节点在进行交互前对潜合作对象做出有效判断，但是，并不能促进网络中各节点进行成功交互.在利用GBDTM方法进行交互时，随着交互次数的增加，成功交互次数呈现出上升态势，并最终趋于稳定.可见，建立节点间激励机制，能够促使节点选择信任策略来进行博弈，从而达到节点间的有效合作，使网络趋向稳定，提高网络的安全性.

图4 成功交互次数数目对比Fig.4 The comparison diagramof successful interaction times

图5反映了随着博弈次数的增加，在无激励博弈模型与GBDTM模型中，选择合作策略的节点在数量上的变化.从图中可以看出采用不同的信任模型，实体节点策略的调整有着明显的变化，GBDTM模型中选择合作策略的节点数目不断增长，并在博弈的后期趋于一个稳定的数目，达到Nash均衡状态.而无激励博弈模型却使选择合作策略的实体节点数目不断减少，最终下降到一个很低的水平.

图5 成功交互节点数目对比Fig.5 The comparison diagramof successful interaction nodes

图6可以看出随着成功交互次数的增加，在无激励博弈模型与GBDTM模型中，实体节点分别得到的收益值的变化.实体节点在无激励的博弈过程中，能成功交互的次数很少，即使成功交互，也不能获得很好的收益值.GBDTM模型中，随着成功交互次数的增多，节点的信誉值不断提高，因此节点收益值也随之上升.同时促使实体节点在下一次策略选择时更容易选择合作行为，在这种信誉值与效用值互相促进的情况下，形成一种“良性循环”.

图6 收益值对比Fig.6 The comparison diagramof utility

4 结束语

在实体节点交互过程中建立激励合作机制，可防止及克服节点自私行为的不断发生，以保证网构软件系统基本功能的正常运行.本文结合当前对于博弈论中激励合作机制的研究，提出了一种新的博弈理论与DyTrust信任模型相结合的GBDTM模型，该模型通过对效用函数的修正，可有效的促进实体节点之间通过博弈自主的形成协作关系，经理论分析证明以及实验验证，得出函数修正后的有效性，说明了该方法性能的优劣，为提高网构软件系统的整体安全性奠定了基础.

［1］SHAwM.Self-healing:softening precision to avoid brittleness［C］//Proceeding of the 1st ACmSIGSOFTWorkshopon Self-Healing Systems.Charleston，USA，2002:111-113.

［2］MEIH，HUANG K，ZHAO H Y，et al.A software architecture centric engineering approach for internetware［J］.Science in China:Series E，2006，36(10):1100-1126.

［3］杨芙清.软件工程技术发展思索［J］.软件学报，2005，16(1):1-7.YANG Fuqing.The speculation of software technology de-velopment［J］.Journal of Software，2005，16(1):1-7.

［4］吕建，马晓星，陶先平，等.网构软件的研究与进展［J］.中国科学:E辑，2006，36(10):1037-1080.LÜ Jian，MA Xiaoxing，TAO Xianping，et al.The research and development of Internetware［J］.Science in China:Series E，2006，36(10):1037-1080.

［5］BLAZE M，FEIGENBAUmJ，LACY J.Decentralized trust management［C］//Proceedings of the 1996 IEEE Sympon Security and Privacy. Washington DC， USA， 1996:164-173.

［6］ABDUL-RAHMAN A，HAILESS.A distributed trustmodel［C］//Proceedings of the 1997 NewSecurity Paradigms Workshop.Cambria，United kingdom，1998:48-60.

［7］KAMVAR SD，SCHLOSSER mT，GARCIA-MOLINA H.The eigen trust algorithmfor reputation management in P2pnetworks［C］//Proceedings of the 12th International Conference on World Wide Web.Budapest，Hungary，2003:640-651.

［8］窦文，王怀民，贾焰，等.构造基于推荐的peer-to-peer环境下的 Trust模型［J］.软件学报，2004，15(4):571-583.DOUWen，WANG Huaimin，JIA Yan，etal.A Trustmodel based on reputation in P2pnetworks［J］.Journal of Software，2004，15(4):571-583.

［9］YAMAMOTO A，ASAHARA D，ITAO T.Distributed pagerank:a distributed reputationmodel for open P2pnetworks［C］//Proceedings of International Symposiumon Applications and the Internet Workshops.Tokyo，Japan，2004:389-396.

［10］MARTIS，GARCIA-MOLINA H.Limited reputation sharing in P2psystems［C］//Proceedings of the 5th ACmConference Electronic Commerce. NewYork， USA，2004:91.

［11］LEE S，SHERWOOD R，BHATTACHARJEE B.Cooperative peer groups in NICE［J］.Computing Networks，2006，50(4):523.

［12］XIONG L，LIU L.PeerTrust:supporting reputation based trust for peer to peer electronic communities［J］.IEEE Transactions on Data and Knowledge Engineering，Special Issue on Peer to Peer based Data Management，2004，16(7):843-857.

［13］SRIVATSA M，XIONG L，LIU L.TrustGuard:countering vulnerabilitles in reputation management for decentralized overlay networks［C］//Proceedings of the 14th World Wide Web Conference(WWw2005).Chiba，Japan，2005:422-431.

［14］常俊胜，王怀民，尹刚.Dytrust:一种P2P系统中基于时间帧的动态信任模型［J］.计算机学报，2006，8(29):1301-1307.CHANG Junsheng，WANG Huaiming，YIN Gang.DyTrust:a time-frame based dynamic trust model for P2psystems［J］.Journal of Computers，2006，8(29):1301-1307.

［15］董宇欣，印桂生，谢新强.网构软件信任机制的形式化研究［J］.哈尔滨工程大学学报，2011，6(32):800-806.DONG Yuxin，YIN Guisheng，XIE Xinqiang.Study on formalization of trustmechanismfor Internetware［J］.Journal of Harbin Engineering University，2011，6(32):800-806.

［16］马志强，印桂生.面向网构软件的信任驱动及演化模型［J］.哈尔滨工程大学学报，2010，8(31):1054-1060.MA Zhiqiang，YIN Guisheng.A trust-driven evolutionary model for Internetware［J］.Journal of Harbin Engineering University，2010，8(31):1054-1060.

［17］VON NEUMANN J，MORGENSTERN O.Theory of games and economic behavior［M］.Princeton:Princeton University Press，1994，328:36-39.

［18］FUDENBERG D，LEVINE D K.The theory of learning in games［M］.［S.l.］:MIT Press，1998，78:167-169.