多Agent系统中基于狄利克雷分布的信任模型
计 算 机 工 程 第 37 卷 第14期
Computer Engineering V ol.37 No.14
文章编号：文章编号：1000—3428(2011)14—0128—03 ·安全技术·安全技术·
2011年7月
July 2011
文献标识码：文献标识码：A
中图分类号：中图分类号：TP309
多Agent系统中基于狄利克雷分布系统中基于狄利克雷分布的中基于狄利克雷分布的信任模型
陈广福，陈广福，蔡国永，蔡国永，林 航，王瑞丽，王瑞丽，刘国宾
(桂林电子科技大学计算机科学与工程学院，广西 桂林 541004)
摘 要：提出一种多Agent系统中基于狄利克雷分布的信任模型。该模型利用狄利克雷分布解决二元评价的局限性，使信任模型可以按等级来评价信誉。提出层次过滤算法，以解决推荐信息中存在的各类恶意Agent问题。仿真实验结果表明，该信任模型能有效抑制不诚实推荐和策略性欺骗。
关键词：关键词：狄利克雷分布；多Agent系统；信任；过滤算法
Trust Model Based on Dirichlet Distribution
in Multi-Agent System
CHEN Guang-fu, CAI Guo-yong, LIN Hang, WANG Rui-li, LIU Guo-bin
(School of Computer Science and Engineering, Guilin University of Electronic Technology, Guilin 541004, China)
【Abstract】This paper proposes a trust model based on Dirichlet distribution in Multi-Agent System(MAS). It uses the Dirichlet distribution to solve the limitations of a binary evaluation, the trust model can rate with graded levels. A level filtering algorithm is proposed to effectively filter a variety of malicious Agent in the referrals. Experimental results show that the proposed trust model is effective in inhibiting unfair recommendations and strategies deception.
【Key words】Dirichlet distribution; Multi-Agent System(MAS); trust; filtering algorithm DOI: 10.3969/j.issn.1000-3428.2011.14.042
1 概述
多Agent系统(Multi-Agent System, MAS)正朝着大规模、开放、动态和分布式结构的方向发展。在MAS中，Agent由追求不同利益的拥有者所占有，并且可以在任何时间加入或离开系统，具有自私性和不可靠性；同时没有Agent能确知环境的一切信息，也不存在一个中心控制Agent可以控制所有Agent。这些特点使Agent信任研究，特别是信任评估模型的研究成为近年来MAS研究的热点。
许多学者从不同角度提出了各类信任评估模型。文献[1]提出了Beta信誉系统(Beta Reputation System, BRS)，该模型采用基于Beta分布函数描述二项事件(binary event)后验概率的思想，同时提供了一套主观逻辑算子，用于计算信任度。其不足之处是只能用于对信誉二元评价的情形。文献[2]扩展了BRS系统，提出了迭代的过滤恶意推荐算法，该模型同样只适用于二元评价情形，并且只有在提供者提供服务是真实和准确的情况下有效。文献[3]提出了基于Agent虚拟组织的信任与信誉模型(TRAVOS)，该模型采用概率论研究信息不精确条件下个体Agent之间的信任关系，其不足之处是使用了二元来表示交互结果评估，且在过滤不准确推荐机制中，没有考虑足够多的直接交互经验，不能对付策略性欺骗行为；文献[4]提出了Dirichlet信誉系统(Dirichlet Reputation System, DRS)，给出了一种基于Dirichlet分布的信任算法，该算法主要考虑如何利用Dirichlet概率分布分布理论计算信任度，没有过多考虑抵抗多种恶意攻击。其不足之处是没有考虑如何识别恶意评价以及对恶意评价惩罚且仅仅利用直接评价结果计算信任度，没有考虑推荐信任。文献[5]提出一种可信区间方法处理虚假推荐，但该方法的不足之处是当有大量不同级别恶意节点时，算法处理恶意节点能力就会降低，这是因为
算法中也用到Beta分布。
在上述信任模型的基础上，本文提出一种基于狄利克雷分布的信任模型(Dirichlet-Based Distribution Trust Model, DBTM)。
2 基于狄利克雷分布的信任模型
关于信任，目前尚无一致认同的定义。一般认为，信任是一种主观信念，可理解成一个实体评价其他实体行为的主观可能性程度。在MAS中，接收服务称为信任者，用Agtr表示，提供服务称为被信任者，用Agte表示。根据评价依据获得方式的不同，信任评价可以分为2类：直接信任和推荐信任。用θ来表示Agtr和Agte间交互成功的概率。直接信任是通过Agtr和Agte间的直接交互经验获得的信任评价，用θdir表示。推荐信任是通过推荐Agent提供的反馈信息获得的信任评价，用θrec表示。
θdir表示直接信任度，θrec表示推荐信任度，θ来表示信
))
))
任度，它是直接信任度和推荐信任度合并成，其计算式如下：
θ=ω1θdir+ω2θrec (1)
)
)
其中，ω1和ω2是决定2种概率重要性权重，且满足ω1+ω2=1。其值由Agent的主观因素决定。
2.1 狄利克雷分布
狄利克雷分布是多项分布，可以对离散集进行评价。假
基金项目：基金项目：广西自然科学基金资助项目(0728089)；广西研究生教育创新计划基金资助项目([1**********]12M18)
作者简介：作者简介：陈广福(1979－)，男，硕士研究生，主研方向：多Agent系统，信任模型，机器学习；蔡国永，教授、博士；林 航、王瑞丽、刘国宾，硕士研究生
收稿日期：收稿日期：2011-01-14 E-mail：[email protected]
第37卷 第14期 陈广福，蔡国永，林 航，等：多 Agent 系统中基于狄利克雷分布的信任模型 129 设离散随机变量X有x1,x2,L,xk共k个可能状态，对X多重采样服从狄利克雷分布。用X表示对k个离散随机元素的评价结果。则Xi表示第i个评价值，如：Good或Average，其集合为D={X1=x1,X2=x2,L,Xk=xk}。设离散随机向量γ=
{γ1,γ2,L,γk}表示x的概率密度分布(1≤i≤k, ∑ik=1γi=1)，
例如：γ(X=xi)=γi。
p(γ|ξ)
表示给定知识背景下γ的概率密
度函数。设离散随机变量α={a1,a2,L,ak}表示x的观察值，这里称{a1,a2,L,ak}为超级参数。γ的先验概率密度为：
p(γ|ξ)=Dir(γ|aL,aΓ(∑ki=1ai)
a1,a2,i
−1k)=∏k∏ki=1γi (2)
i=1Γ(ai)
其中，ξ表示背景知识；a1,a2,L,ak都大于0；记
γ|ξ
~
Dir(a1,a2,L,ak)，可以求出狄利克雷分布期望值为：
E(p(γ|ξ))=
a
i∑k
(3)
i=1a
i
2.2 直接信任度
在MAS中，Agtr和Agte间的直接信任是对Agent历史交互经验的总结，因此直接信任度可以使用贝叶斯估计方法对θdir估计。
假设Agtr和Agte间已发生了N次交互。要评价k个离散随机元素，在这里，用N1, N2,L,Nk记录集合D中Xi=xi出现的次数，其集合为N={N1, N2,L,Nk}，集合N是集合D的充分统计量。γ的先验分布是狄利克雷分布，且狄利克雷分布是共轭分布，所以后验概率分布p(γ|D,ξ)也服从狄利克雷分布，推理如下：
p(γ|D,ξ)∝P(D|γ,ξ)P(γ|ξ)∝ ∏kγNkk
ii
∏γai
−1i∝∏γNi
+ai
−1
i(4)
i=1i=1i=1
后验分布与先验分布有相同的形式，因此，狄利克雷分布是共轭分布。则后验分布参数为：
α1+N1, α2+N2,L, αk+Nk
则有p(γ|D,ξ)=Dir(γ|a1+N1,a2+N2,L,ak+Nk)，γ的后验分布期望估计值就是要求的直接信任度。
1kaj+Nj−1γ)
=E(P(γ|D,ξ)=
∫0
γ∏j
γj
dγa+NiDir(γ|a=i
(5) 1+N1,L,ak+Nk)+N
θ)
)
dir=γ=
ai+Ni
(6)
2.3 推荐信任度
在MAS中，Agtr和Agte在交互之前不认识或只有少量的交互的情况下要发生交互，就要考虑来自第三方的推荐信息。为使推荐信任度更加精确，用最优无偏估计方法对推荐信任度进行估计。假设Agtr和推荐Agent，推荐Agent和Ag)
te之间交互是相互独立的，它们的直接交互信任度分别为)
θ1、θ2。交互次数分别为U和V次，这里设它们分别评价m个
和j个离散随机元素，用U1,U2,L,Um和V1,V2,L,Vj记录D中Xi=xi出现次数，其集合分别为U={U1,U2,L,Um}和V={V1,V2,
L,Vj}，U、V也是D1和D2的充分统计量，D1和D2是D的
子集。由于狄利克雷分布是共轭分布，因此后验概率分布
p(γ|D1,ξ)和p(γ|D2,ξ)也服从狄利克雷分布，
后验分布分别为p(γ|D1,ξ)=Dir(γ|a1+U1,a2+U2,L,am+Um)和p(γ|D2,ξ)=Dir(γ|a1+ V1,a2+V2,L,aj+Vj)，p(γ|D1,ξ)和p(γ|D2,ξ)的数学期望估
计值就是θ)、θ)
12的信任度。根据狄利克雷分布的基本性质，2个分布数学期望E(p(γ|D1,ξ))、E(p(γ|D2,ξ))为γ的最优无
偏估计量，即有：)
θ1=E(p(γ|D1,ξ))=
∫γDir(γ|a1+U1,a2+U2,L,am+Um)dγ= ai+Ui
∑kak(7)
i=1
i+∑Ui=1
i
同理可以求出θ)
2： θ)
2=E(p(γ|D2,ξ))=
ai+Vi∑k
ak
(8)
i=1
i+∑Vi=1
i
采用概率链式法则来合成推荐信任度，即： θ)
rec=
ai+Ui
k
k
.
ai+Vi
(9)
i∑ak
k
=1
i+i∑U=1
ii∑a=1
i+i∑V=1
i
3 恶意Agent的过滤机制
由于DBTM也采用了将第三方推荐作为计算信任参考量之一，因此就存在第三方推荐所推荐的信息是否可靠的问题。推荐Agent为了获得最大利益或实现自己某一个目标，就会给出虚假推荐或是策略性欺骗。推荐Agent集合中有提供好的服务Agent，也有提供一般服务Agent，更甚至有提供虚假信息的恶意Agent，混淆对Agent的信任评价。为了有效抑制不诚实推荐和策略性欺骗，提出了层次过滤算法。
假设存在一个推荐信任阈值，用η∈[0, 1]来表示，当推荐信任度小于η时，认为推荐信任不诚实的；当推荐信任度大于η时，认为推荐信任是相对可信。因为有部分有良好推荐Agent策略性提供虚假信息，为了让算法更加有效，引入时间衰退因子，用λ∈[0, 1]表示，交互了一段时间后，对各个层次上推荐信息累积和更新，用ωn表示经过n次交互后，各层累积评价值。用β∈[0,1]表示惩罚因子，h表示对累积评价中恶意Agent处罚后集合。R表示推荐信任集合，集合中任一个推荐者的信任度用T表示。层次过滤算法主要思想是，从推荐集中先过滤不诚实的推荐，然后从这些相对可信推荐中，找出偏离大多数的推荐信息。层次过滤算法如下：
1 Agtr是信任者；
2 Agte是被信任者； 3 R是推荐集合；
4 ri是R任一个推荐者； 5 T是R任一推荐任信度；
6 if(T(γ)
7 从R中删除ri ; 8 else 9 repeat
10 for( each ri in R) do
11 )θ=ω))
1θdir+ω2θrec //结合狄利克雷分布和直接经验进行整体 //评价
13 ω))
n=λ×θdir+θdir,n；//对各个层次推荐agent进行累积评价 14 h=β.ωn； //对累积评价后的诋毁和协同作弊Agent进行 //处罚
15 if(T(γ)
16 从R中删除ri ; 17 endif; 18 endfor; 19 endif;
20 until(直到R中推荐者不再变化); 21 return R;
4 仿真实验与分析
仿真基于Agent信誉和信任测试(Agent Repuation and
130 计 算 机 工 程 2011年7月20日 Trust, ART)平台，ART的目标是建立统一的信誉系统测试平台。ART有2种功能：作为实验平台，提供了配套的可视化工具及分析手段；作为竞赛平台，参与者可以编写Agent参与竞争。ART作为实验平台使用时，可以取消竞赛中的部分限制，便于对采用不同策略的Agent在同一环境中，从不同的方面进行比较。
实验目的是评估所提出的信任模型在抑制不诚实推荐和策略性欺骗性能，并与模型BRS、TRAVOS相比较。假设电子市场为模拟场景，在该市场中，每个Agent承担2种角色：(1)服务提供者Agent，它主要是提供服务。为简化复杂性，假设只有一种服务提供类型且所有的提供者Agent提供相同服务。(2)服务消费者Agent，它与服务提供者进行交互且使用这些服务。
在服务提供者Agent中根据行为表现进行分类，如表1所示。
表1 服务提供者 Agent分类
服务提供者Agent类别
行为描述
符号 善意Agent 提供好的服务且对其他Agent的评价都真实 S 简单恶意Agent 只提供不真实的服务
SE 不诚实推荐Agent 提供不真实服务，同时诋毁所有与之交互 的S类Agent，提交不诚实的评价信息 EL 策略恶意Agent
只提供不真实服务，且与S类Agent时 互采取策略性欺骗的行为，如行为摇摆
CE
仿真参数设置如下：在电子市场中，假设总的Agent数为1 000个，服务提供者Agent总数为100，消费者Agent为900个，各类恶意Agent占的比例为[0.0~0.6]，模拟的次数为20，仿真实验结果为平均值。
每轮运行后有10
个Agent离开同时也有10个Agent加入。时间衰减因子
λ=0.3，惩罚因子β=0.5。仿真基于Java实现。
每次交互后，服务消费者是通过对每类服务提供者提供的服务质量进行评价，产生的评价越精确，会拥有越多的消费者，消费者选择每类服务得到相应的效益就高。本文用收支平衡(bank balance)表示消费者最后所得到的总效益。收支平衡值越大，表明成功交易率增加，提供者提供服务质量就好。因此，本文采用收支平衡来衡量3个不同信任模型抵抗恶意攻击能力。
4.1 SE
类仿真
简单恶意Agent的收支平衡对比如图1所示。
图2 不诚实推荐Agent的收支平衡对比
可以看出，当恶意Agent占的比例较小时，三者的区别不是很大。当恶意Agent比例增大，DBTM模型的性能显示出很大的优势。这是因为本文提出层次过滤算法能有效过滤不诚实推荐和诋毁Agent对S
类Agent
发布的不公正信息，
使得
DBTM有效识别诋毁
Agent。当比例到达30%时有所下降，这是因为惩罚因子正在对诋毁Agent进行惩罚。而BRS系统直线下降，因为在BRS中没有惩罚机制，无法识别诋毁Agent。同理，TRAVOS模型恶意Agent到了20%以后，由于不诚实推荐的信息和诋毁Agent发布不公正信息增多，模型中没有惩罚机制，单依靠个人经验和第三方意见不能识别，因此收支平衡也是在下降。
4.3 CE类仿真
策略恶意Agent的收支平衡对比如图3所示。