文档介绍：该【网构软件系统中基于信誉激励的协作博弈模型】是由【史湘云】上传分享，文档一共【7】页，该文档可以免费在线阅读，需要了解更多关于【网构软件系统中基于信誉激励的协作博弈模型】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第33卷第12期哈尔滨工程大学学报 .33№.12
Vol
2012年12月 .2012
JournalofHarbinEngineeringUniversityDec
网构软件系统中基于信誉激励的协作博弈模型
印桂生,王姝音,刘杰,董宇欣
(哈尔滨工程大学计算机科学与技术学院,黑龙江哈尔滨150001)
摘要:为了促使网构软件系统中各软件服务实体在彼此交互、协作的过程中自主的形成协作关系,提出了一种网构软
件系统中将信誉评估与博弈理论相结合的协作博弈演化模型(-).该模型借鉴经济学
GBDTMgamesbasedDyTrustmodel
中博弈论的思想,对网构软件系统中实体节点的协作过程进行博弈分析与建模,并通过在博弈模型中引入节点的信誉
值,对博弈模型中的收益函数进行修正,有效地建立了节点之间的激励合作机制,促进各实体节点间的协作,提
GBDTM
高了网构软件系统的整体安全性能.
关键词:协作博弈模型;信誉评估模型;博弈论;模型;激励机制
DyTrust
doi:/..1006-
jissn
网络出版地址:://..///...
httpwwwcnkinetkcmsdetailUhtml
中图分类号:311 文献标志码: 文章编号:1006-7043(2012)12-1515-07
TPA
Researchoncooperativegamemodel
basedontrust-incentingininternetware
,,,
(YINGuishengWANGS,huyinLIUJieDONG,Yuxin150001,)
DepartmentofComputerScienceandTechnologyHarbinEngineeringUniversityHarbinChina
Abstract:
InordertomakethesoftwareentitiesintheInternetwaresystemcooperatewitheachotherautomatically
,,
duringtheprocessofinteractionandcooperationwithoneotherthispaperproposedanevolutionarygamemodel
-(),
namelytheGamesbasedDyTrustModelGBDTMwhichcombinedthetrustevaluationmodelwiththegame
.,
theoryintheInternetwaresystemReferringtotheprinciplesofgametheoryineconomicsthispaperanalyzedand
,
modelledthecollaborativeprocessofthesoftwareentitiesandcorrectedtheutilityfunctionofthegamemodelby
.
introducingthetrustvalueoftheentityTheGBDTMmodeleffectivelyestablishedtheincentivemechanismamong
.
entitiestopromotecooperationandimprovedtheoverallsecurityoftheInternetwaresystem
Keywords:;;;;;
cooperategarmemodeltrustevaluationmodelgametheoryDyTrustmodelincentivemechanism
为了解决动态的环境下分散的软件实统,目前,对于分布式系统可信性的研究主要集中在
I[n1-2te]rnet[5]
体的共享、集成和复用,
征的软件应运而生,
[3][6]
性、协同性、演化性等特征的软件新形态,其运行评估模型则是以实体间的推荐信任关系为基础,
[4]
依赖于开放、动态的网络环境,当前,如何在开结合自身经验对实体可信度做出评价,然后依据可
放、

[7-9]
网构软件系统属于开放网络环境下的分布式系任度的信任模型中,节点通过相邻节点间相互

收稿日期:2012-04-:2012-12-517:00.
基金项目:国家自然科学基金资助项目(60973075);省自然科学基金型往往比较复杂、
资助项目(200937);哈尔滨市科技局基金资助项目[10-11]
(2009F010003).信任模型大多是局部信任度模型,这类模型通
RCXK
作者简介:印桂生(1964-),男,教授,博士生导师;过采取局部广播手段,询问有限的其他节点以获取
王姝音(1983-),女,博士研究生.
通信作者:王姝音.-:******@..
EmailshuyinwangsinacomPeerTrust
·1516·哈尔滨工程大学学报第33卷
[12-13][14]
型、=(G,S,u).G表示
DyTrust
信模型在解决网构软件系统中信任问题时稍显不系统中的实体节点集合,也是博弈的参与者:Gi=
足,其原因在于:网构软件系统中的实体可以根据网{i,N-i}.其中N-i表示除实体节点i外的其他博弈
络环境的变化而发生动态演化,=
{Si,S-i},Si={协作,不协作}为实体节点i所有策
[15]
对网构软件中实体的信任关系进行了形式化略的集合,s={si,s-i}为博弈者的策略组合;u为参
[16]则提出了一种面向网构软件的信任ttt
与者的收益函数,ui(si,s-i)为在某一时隙t内,博
驱动模型,使信任管理和信任关系的在线演化得以弈者在策略组合下所获得的收益.
在某一时隙t内,实体节点i所采取的
,网构软件系统tt
一系列行动策略表示为si,s-i表示除i外的其他博

.,
作行为呈现出博弈特性基于此思想本文提出一种所示.
网构软件系统中实体间的协作博弈模型,利用博弈表1 博弈实体策略组合关系表
理论对网构软件系统中实体节点的协作过程进行分Table1 Thestrategycombinationrelationofthegame
析,建立节点间协作的博弈模型,并在模型中引入实players
体节点的信誉值,用以建立实体间有效的激励合作
N-i映射
机制,
abcd⋯sis-i
,
1 基于信誉激励的协作博弈模型codiscodis
,
it1cocococo
网构软件的概念最早由我国北京大学的杨芙清,
discodisco
、.、,
教授梅宏教授所提出它指的是一种具有柔性多cocococo
[3]i,
目标、连续反应式的新系统形态,它能够根据外discodisco
it2,
codiscodis
部环境变化来动态调节自身参数与指标进而进行演⋯⋯⋯

实体,这种软件实体可以是构件实体、服务、软
Web在表1中,a、b、、cd等用来表示除节点i以外的
件等,这种软件实体以开放、自主的方式存在
Agent其他实体节点(统一定义为N-i),在每个时隙t中,
于的各个节点之上,任何一个软件实体可
Internet节点i与其他节点分别进行交互,表示协作(-
在开放的环境下通过某种方式加以发布,并以各种coco
),表示不协作(-).表1中可
协同方式与其他软件实体进行跨网络的互连、互通、operatedisdiscooperate
以看出,在时隙t1内,节点i的策略组合为{协作,协
协作和联盟,从而形成一种与当前的信息相类
Web作,不协作,协作},与i进行协作的其他节点的策略
,软件实体需考虑
t
SoftwareWeb组合为{不协作,协作,协作,协作}.这里用si表示
自身与他人的损失与得益,使得整个交互过程成为
由节点i的行动策略组合到实数集的一个映射,即
一种博弈过程,因此可以用博弈论对网构软件系统
t
si:S→R,它可以反映出节点i在某一时间段t内采
中实体的协作过程进行建模.
,t[0,1].t
单阶段博弈模型()取协作策略的几率si的取值范围为si值越
GBM,.
在利用博弈理论分析网构软件系统时,将网络大代表实体节点选择合作的几率越大
3 :{t,t}
中的实体看成具有有限理性的博弈参与者,将演化定义收益函数u是由策略集Ssis-i到
t
过程中实体协作策略的选择看成一个复杂的博弈过实数集合R的映射,即u:S→R,当且仅当u(si)>
t′tt′
程,博弈者的策略就是实体节点采取的行动,而参与u(si)时,节点i选择策略组合si比选择策略组合si
者的收益函数则是实体节点根据所采取行动而能获获得的满意度高.
,首先给出网构软件系统中实网构软件系统中实体节点协作的博弈过程可以
:体节点在协作的过程中,既可以是协作
定义1 在每个博弈阶段,实体节点间的单阶的发起者,也可以是协作的响应者,例如,实体节点i
第12期印桂生,等:网构软件系统中基于信誉激励的协作博弈模型·1517·
需要实体节点a提供a的某种服务以完成协作时,i 博弈D的Nash均衡为:在给定其他参与者的
t倡
就为协作的发起者,,实最优策略s-i下,能最大化其效用函数的协作博弈策
,t倡
体节点a需要节点i的数据以完成该次协作实体略si,即
节点a变成协作的发起者,
si=[ui(si,s-i)]=
argmaxE
这种协作关系类似于2关系,即实体节点同时作t倡t
(λs-i-ρsi).(2)
PPt∈[0,1]

由式(2)可以看出,在博弈的过程中,实体节点
协作的发起者提出协作请求,并得到节点a的协作

响应后,由于成功完成一次协作,实体节点i可获得
有自私特性,为追求自身收益最大化,每个节点都会
一定的收益λ,而节点a由于响应实体i的请求,牺
tt
选取较小的i值,使ρi尽量小,即节点在被请求协
牲了一定的资源,并且承担了i是恶意节点的风险,ss
“”,
因此要用掉开销,这里λ>ρ>0,λ和ρ均为常量参作的情况下趋向于选择不协作策略这时采取
“不协作”策略将成为系统中节点的纳什均衡策略,
,如果实体节点i和a在对方提出协作
,
请求时能互相响应对方,则均可获得收益λ-ρ,如而此时系统的整体收益却接近于零网构软件系统
的整体性能会受到严重的影响,这是一个典型的囚
果节点i只获得其他节点的协作响应,而不去响应
,,
其他节点的协作请求时,,如徒困境博弈模型为了解决该问题需要通过建立有
效的激励机制来刺激实体节点采取合作行为.
果节点i只响应其他节点的协作请求,而不能获得
修正的进化博弈模型()
其他节点的协作响应时,要付出收益ρ,如果实体节GBDTM
点间互不响应时,,网构软件系为了在网构软件系统中运用博弈理论建立节点
,

利的策略,以使实体节点在博弈的过程中最终达成
共识,都能获得较高的收益,从而使整个网络能够达
[17]
到一种均衡状态,而且保证帕累托有效.
Nash
实际上,网构软件系统还具有下述性质:1)节
点的协作行为在时间上具有随机性及不确定性,即
节点可能在任意时刻向其他节点发起或接受到其他
,但
各节点并不能确定博弈将在哪一阶段结束;2)实体
图1 协作博弈模型的收益矩阵节点对每次协作的结果都有记录,即实体节点可以
,网构软件系统中实体节
点的协作博弈可用进化博弈的思想进行建模.
博弈模型的均衡进化博弈理论中,具有有限理性的参与者在重
Nash
由定义2可知,在时隙t内,除i以外的实体节复博弈的过程中,可以不断的进行学****并调整策略,
t
点选择协作策略的概率为s-i,选择不协作策略的概以使博弈中参与者最终达成共识,使系统整体的效
t[18]
率为1-s-i,
tttt
ui1(s-i)=s-i(λ-ρ)+λ(1-s-i).述:在每一阶段的博弈g中,每一个参与者i=1,2,

节点i选择不协作策略的收益为⋯,N选择行动ai∈A,每阶段博弈产生该阶段的收
tttt
i2(-i)=-i·(-ρ)+(1--i)·0.
usss益xi,参与者i可以观察到一些信息ω∈Ω,而这些
t
节点i选择协作策略的概率si,节点i选择不协信息并没有被完全预期到,于是参与者通过更新信
1-t,°
作策略的概率si因此实体节点i的期望效用函念规则β:B←Ω来修正自己的信念βi∈B,最后按照
数可表示为更新后的决策规则f:A←B根据目前的信念再次选
ttttttt
[ui(si,s-i)]=siui1+(1-si)ui2=择行动.
ttEttt
si[s-i(λ-ρ)+λ(1-s-i)]+(1-si)s-i(-ρ)=为了建立网构软件系统中实体节点的激励合作
tt
λs-i-ρsi.(1)机制,需借鉴进化博弈的思想,即:使参与博弈的实
·1518·哈尔滨工程大学学报第33卷
体节点在不断的重复博弈中总结经验,动态的学****实体节点i具有信誉值T,该信誉值作为激励惩罚

策略的博弈过程,并且对实体节点的策略选择进行值高的实体节点更容易获得其他实体节点提供的服
激励,使不合作的节点只能在短期获得较高的收益务,因此使其开销减小,这可以看作是对行为良好的
值,长期的不合作行为会导致节点收益值减少,
在原有的网构软件博弈模型中加入新的要素T,即其他节点的协作而使其开销增大,作为对具有不良
t
实体节点综合信誉值T-ii,,网构软件系统中实体节点间
在时刻t观察到的信息,反馈给博弈实体的收益函基于信誉激励的收益矩阵可以表示为图3.
,其综合信誉值都在q(·)为收益函数中的激励惩罚因子,q(·)=
发生变化,收益函数受该信誉值影响而改变,因此决1
ε,T-ii是节点i的综合信誉值,表示在某时隙t
-ii
会使博弈者的信誉值发生变化,该变化作为博弈者内,与节点i交互过的其他节点对节点i的综合评
t
新观察到的信息,,这个评价值与节点i在某时隙t内选择的策略si
观察信誉值变化动态学****调整策略的过程如图2有一定关系,节点选择合作策略的概率越大,其信誉
tt
--ii的取值范围均为[0,1],当si
趋近于0时,T-,
t
,T-ii也
,ε表示对实体
节点的激励程度,ε的选取与计算信誉值T-ii所用
的信誉值评估模型有关.
图2 基于信誉激励的进化博弈过程
Theprocessofevolutionarygamebasedontrust
定义4 在每个博弈阶段,基于信誉激励的进
化博弈可定义为四元组D=(G,S,u,q(·)).G表图3 基于信誉激励的协作博弈模型的收益矩阵
示系统中的实体节点集合,也是博弈的参与者: Thepayoffmatrixofthetrust-basedcooperative
Gi={i,N-i}.其中N-i表示除实体节点i外的其他game
博弈者i在某时隙t内的期望效用函
数的修正表达式为
合S={Si,S-i},Si={sij}为实体节点i所有策略的
ttttt1
={si,s-i}为博弈者的策略组合;u为参与者ui(si,s-i)=λs-i-ρsiε(3)
T-ii
的收益函数,ui(si,s-i为博弈者策略组合下所获得
用实体节点的信誉值对节点的收益函数进行修
1
(·)为激励惩罚因子,q(·)=ε,T为正,
-
Tiit
选择协作策略的概率si,节点的信誉T-ii会降低,
实体节点i的信誉值,T值越大,表示节点i的信誉
1
度越高,T∈[0,1].ε反而会增大,根据不同的信誉值评估模型来选
T-ii
在引入信誉值作为激励惩罚因子后,网构软件t
定合适的ε值后,节点i单方面减小si时,节点i的
系统中实体节点协作时的博弈过程可以重新描述

为:当实体节点i提出协作请求并得到实体节点a
正博弈过程中的收益函数,可以有效的激励实体节
的协作响应后,实体节点可获得一定的收益,而
,如果节点信誉值增加,收
,ρ,,
节点i响应实体节点a的请求要用掉开销同时益值也会随之增加,而信誉值较低的节点随着时间
第12期印桂生,等:网构软件系统中基于信誉激励的协作博弈模型·1519·
的推移,收益函数值将会不断降低. 设在时间帧t,节点j和节点r的公共交互节点
引入激励惩罚机制对效用函数进行修正后,博集合用C(j,r)表示,节点j和节点r对公共节点度
set
t倡t
弈D的均衡s-i可表示为量的差异dji可以定义为
Nash
t倡ttt倡tt
si=[ui(si,s-i)]=钞|Dji-Dri|
argmaxEtj∈C(j,r)
set
t倡t1dji=.(9)
(λs-i-ρsiε).(4)|C(j,r)|
st∈[0,1]set
argimaxT-ii
设节点j所能容忍节点r的最大偏差为θ,则反
采用激励机制后,大多数实体节点最终将趋于
馈可信度的计算公式为
选择策略“合作”,网络将会达到均衡状态,形
Nash1-t
Crjrdjrt
+|1-|,djr<θ
jr2θ
Crjr=(10)
2 信誉值评估模型Crjrθ
-|1-|,
DyTrustcrjrt
2djr
本文的进化博弈模型中采用模型作为
DyTrust 节点r如果提供诚实反馈,会提高其反馈可信
信誉值的评估模型,该模型中运用近期信任、长期信
度;提供不诚实反馈,则会降低其反馈可信度.
任、反馈信任等信任度量的相关参数,增强了节点行为t
节点j对节点i的信任值Tji取近期信任值与长
改变的动态适应能力以及对反馈信息的聚合能力.
期信任值中的较小值,即
在时间帧t内,节点j对节点i的信任度量可分ttt
Tji=(ji,ji).(11)
为直接信任和间接信任2部分,节点j对节点i的信minSTLT
tt 最终,节点i的综合信誉值是在某一时间段里,
任度量记为Rji;则Rji可表示为
.
t与i有过交互历史的节点对节点i做出的综合评价
CrDri
ttjr可表示为
Rji=αDji+(1-α)钞.(5)
r∈I(i)
钞Crjr
r∈I(i)t1t
T-ii=钞Tji.(12)
tnj∈C(-i)
式中:Dji表示在时间帧t中,节点j对节点i的直接set
式中:C(-i)表示时间帧t内,与节点i有过交互
信任;Crjr表示节点j对提供间接信任值的节点r的set
的节点的集合.
反馈可信度;I(i)表示时间帧t中,所有和节点i进
利用信任评估模型得出节点i的综合
行过交互的节点集合(不包括节点j);α表示信任DyTrust
,,
评价的信心因子,取值满足0≤α≤
t信任模型的反馈控制机制与进化博弈论中
直接信任值Dji可定义为DyTrust
的节点激励机制相结合,不但可以增强信任模型的
t1
Dji=eji.(6)
m钞动态适应能力,还可以促进网构系统中的构件节点
式中:eji为节点j对节点i的交互满意度的评价,0≤
DyTrust
eji≤1;m表示在时间帧t中,节点i和节点j之间交所不能解决的.
互的总次数.
3 实验验证
在经过连续多个时间帧后,节点j对节点i的信
任度量可以用节点j对节点i的2个信任度量参数:
GBDTM
tt.
近期信任ji、
STLT
,,500,
设节点j对节点i的近期信任值ji,该值可定始场景中在局域网上设置了个节点要求每一个
ST
义为节点都分别通过无激励的博弈方法、基于信任
DyTrust
tt-1t、.
ji=(1-β)ji+βRji.(7)评估方法以及方法进行协作交互
STSTGBDTM
式中:β为信任学****因子,β越大,先前的经验就越设效用函数中参数ε=3,λ=120,ρ=80,α=
,β=,
,,
设节点j对节点i的长期信任值ji,可以利用成功交互次数数目对比图其中表示用无
LTDyTrust
式(8)进行计算:激励的博弈方法进行交互;表示用
GBDTMGBDTM
t-,利用无激励博弈方
tji(t-1)+Rji
ji=LT.(8)
LTt式进行交互时,随着交互总次数的增加,成功交互次
·1520·哈尔滨工程大学学报第33卷
数反而下降,这充分证明了非合作博弈中节点存在图6可以看出随着成功交互次数的增加,在无
“自私”,随着激励博弈模型与模型中,实体节点分别得
DyTrustGBDTM
交互次数的增加,节点的交互成功次数不断波动,
模型能有效反应网络节点的信任值,使网络中,能成功交互的次数很少,即使成功交互,也不能
DyTrust
节点在进行交互前对潜合作对象做出有效判断,,随着成功交互
GBDTM
是,,节点的信誉值不断提高,因此节点收益
方法进行交互时,随着交互次数的增加,
GBDTM
功交互次数呈现出上升态势,,在这种信誉值与效用值
见,建立节点间激励机制,能够促使节点选择信任策互相促进的情况下,形成一种“良性循环”.
略来进行博弈,从而达到节点间的有效合作,使网络
趋向稳定,提高网络的安全性.
图6 收益值对比
Thecomparisondiagramofutility
图4 成功交互次数数目对比
Thecomparisondiagramofsuccessfulinterac-4 结束语
tiontimes
在实体节点交互过程中建立激励合作机制,可
图5反映了随着博弈次数的增加,在无激励博
防止及克服节点自私行为的不断发生,以保证网构
弈模型与模型中,选择合作策略的节点在

博弈论中激励合作机制的研究,提出了一种新的博
型,实体节点策略的调整有着明显的变化,
GBDTM弈理论与信任模型相结合的模型,
模型中选择合作策略的节点数目不断增长,并在博DyTrustGBDTM
该模型通过对效用函数的修正,可有效的促进实体
弈的后期趋于一个稳定的数目,达到均衡状
Nash节点之间通过博弈自主的形成协作关系,经理论分

析证明以及实验验证,得出函数修正后的有效性,说
点数目不断减少,最终下降到一个很低的水平.
明了该方法性能的优劣,为提高网构软件系统的整
体安全性奠定了基础.
参考文献:
[1].-:-
SHAWMSelfhealingsofteningprecisiontoavoidbrittle
[]//1
nessCProceedingofthestACMSIGSOFTWorkshop
-.,,2002:
onSelfHealingSystemsCharlestonUSA
111-113.
[2],,,.-
MEIHHUANGKZHAOHYetalAsoftwarearchi
[].
tecturecentricengineeringapproachforinternetwareJ
图5 成功交互节点数目对比:,2006,36(10):1100-1126.
ScienceinChinaSeriesE
Thecomparisondiagramofsuccessfulinterac-[3][].软件学报,2005,
J
tionnodes16(1):1-7.
第12期印桂生,等:网构软件系统中基于信誉激励的协作博弈模型·1521·
.-50(4):523.
YANGFuqingThespeculationofsoftwaretechnologyde
[].,2005,16(1):1-7.[12],.:
velopmentJJournalofSoftwareXIONGLLIULPeerTrustsupportingreputationbased
[4]吕建,马晓星,陶先平,[].[].
JtrustforpeertopeerelectroniccommunitiesJIEEE
中国科学:辑,2006,36(10):1037-1080.,
ETransactionsonDataandKnowledgeEngineeringSpecial
册,,,.,2004,16
LJianMAXiaoxingTAOXianpingetalTheresearchIssueonPeertoPeerbasedDataManagement
[].:-(7):843-857.
anddevelopmentofInternetwareJScienceinChinaSe
,2006,36(10):1037-1080.[13],,.:
riesESRIVATSAMXIONGLLIULTrustGuardcountering
[5],,.
BLAZEMFEIGENBAUMJLACYJDecentralizedtrustvulnerabilitlesinreputationmanagementfordecentralize