分布式多Agent环境下的信任和声誉模型

理论计算机科学电子笔记244（2009）139-149www.elsevier.com/locate/entcs一种分布式多Agent环境下的Mozhgan Tavakolifard1，3挪威特隆赫姆挪威科技大学通信系统服务质量量化中心Svein J. Knapskog克纳普斯科格2，3挪威特隆赫姆挪威科技大学通信系统服务质量量化中心摘要信任在电子交易中的重要性是众所周知的。目前的大多数信任模型由一个中央实体组成，该实体使用标准化的评估方法和标准来验证是否符合信任要求。 在去中心化环境中，通信场景更加复杂，并且不存在普遍接受的客观要求或评估标准。应该指出的是，当代理人相互交互时，情况会变得更加复杂。本研究的目标是在分散的多代理系统的信任和声誉模型。为了实现这一目标，我们选择了Ntropi模型作为起点，在其他几个模型中，通过为Ntropi模型引入新的概率声誉算法，该模型在此类场景中的效率得到了显著提高。关键词：贝叶斯推断，狄利克雷分布，最大似然估计，信誉，信任。1引言互联网的快速变化的环境导致了诸如互联网上数百万活跃实体的脆弱可信度之类的问题，例如，人类和移动代理。随着越来越多的商业交易通过互联网进行，这个问题并不简单。因此，设计一种有效的方法来验证在这样复杂的环境中的可信性是必不可少的，因为信任机制在多代理系统的安全性中起着关键作用还有信任1电子邮件：mozhgan@q2s.ntnu.no2电子邮件：knapskog@q2s.ntnu.no3由挪威研究委员会任命的“通信系统服务质量量化中心，卓越中心”，由研究委员会、挪威技术大学和UNINETT资助。http://www.q2s.ntnu.no1571-0661 © 2009 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2009.07.043140M. Tavakolifard，S.J.Knapskog/Electronic Notes in Theoretical Computer Science 244（2009）139信任的建立并非微不足道，因为传统的和社会的信任手段不能直接应用于这些环境的虚拟设置，因为在许多情况下，所涉及的各方没有任何先前的交互。在这样的场景中，信誉技术可以用于刺激服务质量和可接受的用户行为在线市场和社区，并制裁可能不可接受的用户行为。 为此，Ntropi模型[1]被设计用于促进交换 信息和/或商业环境中的信任和声誉。Ntropi将信任分为直接（显式）和推荐类。 直接类基于委托代理人与受托代理人的先前个人经历。但是推荐的可信类是从口碑中派生出来的（例如，意见），这被称为声誉，并且可以被转化为直接的或定期的信任。本文提出了一个自动化和自治的信任系统，使用贝叶斯推理以及改进的Dirichlet分布。 我们的主要贡献是 最大似然法在信任/声誉模型中的应用，估计Dirichlet分布中的参数，并在所提出的声誉管理模型中引入分层贝叶斯方法。最大似然估计方法以前已在[5]中介绍过 作为反馈聚合策略。然而，在这项工作中，引导（当两个不熟悉的代理人面对对方）是主要关注的本文的其余部分组织如下：第2节涵盖相关文献。第三节介绍了Ntropi模型及其分析。第4节详细讨论了所提出的模型。第5节解释了实验结果，并介绍了评估过程。第6节提出了结论和建议未来的工作。2文献综述我们在其他几个模型中选择了Ntropi模型[1]，因为：1）这个模型 主要是为分散式多代理系统设计的，2）它比其他模型在这一领域涵盖了更多的信任方面，3）它是学术界广受欢迎的模型，4）它提出的元素已被纳入Sun JXTA是一个开源的通用P2P框架。此外，已经在各种流行的P2P平台中分析了这些实现，例如Gnutella [7]，Free Haven [12] [4]自由的根据对现有信誉算法的调查，概率算法，特别是贝叶斯推理算法似乎更受欢迎。因为这些算法有一个健全的数学基础，并被认为是适合制定人类的特点，他们是更灵活的比Ntropi的ad-hoc算法，需要较少的互动与用户。因此，主体定义的大多数基于贝叶斯的声誉算法都是二项式的（例如[2]），允许两个值的评级，要么是正面的（例如好），要么是负面的（例如坏）。 二项模型的主要缺点是它不能代表大鼠-M. Tavakolifard，S.J.Knapskog/Electronic Notes in Theoretical Computer Science 244（2009）139141具有分级水平的环，例如一般-不好-一般-好极了。 此外，二项模型原则上无法区分两极化评级（即许多非常差和许多非常好的评级）和平均评级。Ntropi的研究人员对多项评级进行了分级：例如“非常值得信任”、“值得信赖”、“中等”、“不值得信赖”和“非常不值得信赖”，这更现实。还有几个基于贝叶斯的声誉模型，分级评级似乎更合适。这些模型中的一些已经使用Dirichlet作为先验分布和多项模型作为似然分布在他们的贝叶斯推断。3Ntropi模型在本节中，Farez Abdul-Rahman [1]的Ntropi模型构成了我们提出的模型，解释和分析的模型。3.1模型描述Ntropi是一个真正去中心化的信任模型。它不依赖任何第三方，所有实体都可以自己决定如何信任。它同时使用代表性和经验性信息。将作为单一意见的推荐信任值有五个等级：在接收到来自潜在客户的推荐在那之后，他可以给他的经验一个评级，并注意到他自己的评级和推荐评级之间的差异这种差异（在该模型中称为语义距离）显示了评级标准的差异这些差异会被记录下来，以便将来信任代理可以相应地调整其信任值。根据这一分歧的历史，将形成一个翻译表，并将翻译建议。为了将“他说的话”转化为“我们认为他的意思”，我们得到了最常见的语义距离，并将其添加到推荐值中。为了组合多个推荐并计算声誉，我们需要知道每个推荐者的信任度，并对来自更值得信任的推荐者的推荐给予更多权重。在Ntropi模型中，信任关系经历了几个阶段。在任何时间点，信任关系将存在于四个阶段之一，如图所示。1.一、不同阶段的建议可以不同的方式考虑我们根据推荐者先前推荐的一致性来计算我们对推荐者的信任。如果语义距离的分布更加分散，那么一致性就更低。传播越小，推荐器被认为越一致。 在这个模型中，通过首先找到有序集的半四分位数范围（SIQR）的语义距离，四舍五入到最接近的整数。然后使用查找表将SIQR转换为可信度级别。然后，我们分配的权重，根据他们的信任值。针对每个所推荐142M. Tavakolifard，S.J.Knapskog/Electronic Notes in Theoretical Computer Science 244（2009）139图1.一、信任关系的阶段，箭头指示阶段转换的可能方向信任值将推荐者的权重相加。最终信誉值是具有最高权重和的信任值如果推荐请求者不知道推荐者，则请求者可以获得关于未知推荐者的推荐。还存在这样的场景，其中推荐请求者可以执行网络搜索，特定代理和接收到的推荐可以是通过多个中间代理转发请求的结果。在这两种情况下，当一个推荐者推荐另一个推荐者时，结果就是一个推荐链。链的头部可能包含一个以上的已知推荐器，所有这些推荐器都推荐链的同一个第一中介。寻求关于未知前景的推荐的代理将请求来自那些他已经知道并且信任的推荐者的推荐。因此，链3.2模型分析我们对Ntropi模型的分析如下：• SIQR方法只是在这个模型中找到语义距离传播的一种方法。数据中的其他分散性度量可能更适合于不同的应用，特别是不存在无界、单峰和对称分布要求（SIQR适用于此）的应用。• 然而，SIQR不包括分布中的所有数据点，这可能是在确定适当的扩散测量时的另一个考虑因素，例如，标准偏差确实包括所有数据点。• 此外，当将SIQR（或任何扩散度量）转换为信任级别时，不需要假设线性转换。然而，可以根据给予不同SIQR/散布值的权重为每个SIQR值选择不同的信任值。• 在Ntropi中，所有链头都必须是已知的，这种方法的另一个可能的缺点是，即使请求者愿意使用那些链头，M. Tavakolifard，S.J.Knapskog/Electronic Notes in Theoretical Computer Science 244（2009）139143建议.一个例子，未知的排序器可能是有用的，当替代方案是没有任何建议。这种情况类似于在街上问路，有时也会证明这一点 可以成功地使用来自陌生人的建议，即当对推荐代理一无所知时。这在拥有任何信息都比没有信息好的情况下尤其如此，同时，人们相信推荐者的仁慈以及低感知风险。• 我们将在这里观察到，加权信任级别方法提供了基于推荐者的信任级别来对推荐进行加权的定制和灵活性的可能性。然而，它也增加了用户要执行的任务列表，即他必须能够定义，并且如果需要，可以调整使用此模型的每个应用程序的权重。实际上，这不是一个非常令人满意的情况，因为它将需要来自应用本身的额外帮助，要么基于应用领域中代理的公知属性来硬连线加权，要么采用某种形式的学习算法，该算法可以基于经验动态更新权重• 由于其信誉算法导致选择具有最高权重的推荐，因此它将潜在地忽略也源自可信赖的推荐者的其他推荐，尽管这些推荐者具有较低的可比较的可信度水平。给定来自较低信任度的推荐者的推荐数量（对于相同的信任值）足够高，它们的推荐信任值仍然可以是获胜值，因为它们的权重总和将超过具有较高信任度但在本地推荐集合内具有较低群体的推荐者。 更好的算法是 新的信任值由信誉/组合算法基于从整个信任级别范围的所有可信代理接收的推荐来产生。4推荐的声誉算法本文提出的新信誉算法是基于A. Jøsang [8].本文对该算法进行了改进，利用最大似然估计方法，根据观测数据对算法的参数进行估计。JøsangP（Θ |X）P（X|P（Θ）（1）从左到右阅读，该公式被解释为：实验X的结果后的假设Θ与假设下的这种结果的可能性乘以以下概率成比例：实验前的假设。 在本上下文中，先验θ将是我们与主体p的下一次交互中每个潜在结果的概率的估计，而后验将是我们在一次这样的交互之后的修正估计。144M. Tavakolifard，S.J.Knapskog/Electronic Notes in Theoretical Computer Science 244（2009）139|与成果X进行了互动。在这里，重要的是要注意P（ΘX）在某种意义上是一个二阶概念，我们对计算任何特定θ值的P（Θ X）不感兴趣。 确实如Θ是我们问题中的未知数，我们感兴趣的是导出整个分布，以便计算其期望值，并将其用作我们对可信度的下一个估计。在Ntropi模型中，代理的可信度可以被称为“非常可信”所以评级水平是一个离散的集合。但在贝叶斯模型中，评级是介于0和1之间的实数。在贝叶斯推断中，我们应该使用多项概率分布来表示可能性那么共轭先验分布就是Dirichlet分布。定义4.1代理人A它反映了AgentA信任值用θdt表示，因为它是直接信任。定义4.2从代理人A的角度来看，代理人B它是对代理B表示值用θrt表示，因为它是推荐信任。成功合作的估计量是信任值和声誉值的组合。θ=w1θdt+w2θrt（2）其中w1和w2满足w1+w2=1。它们是分别代表这两个概率的重要性的权重，并由代理人的个人特征决定4.1陌生的阶段最大似然法估计Dirichlet分布的参数。这些参数在封闭形式中不可用。我们使用一个简单而有效的迭代方案，从过去的经验与其他代理人在这个模型中获得的参数估计。这是我们的主要贡献。狄利克雷分布捕捉了k个可能结果的观测序列，其中k个正实参数为α（θi），i= 1. k，每个对应于一个可能的结果。参数α可以从具有比例的训练集估计：D={p1，p2，...，p N}。如果A和B是完全陌生的人，B处于不熟悉阶段对于A来说，当这两个陌生人第一次见面时，A需要收集与他遇到B时相同的背景下的那些过去的经验（背景限定了信任意见，描述了信任者是训练集D。有两类广义信息，称为分类器，A在估计参数时可以用来形成集合DM. Tavakolifard，S.J.Knapskog/Electronic Notes in Theoretical Computer Science 244（2009）139145||NKΣdαkKKα：情境经验和刻板印象。表1详细介绍了这两个泛化分类器。表1首次相遇的广义信息分类器描述分类器情境体验我们在当前上下文中体验到的所有其他受托人的一般可信赖性，并将其用作此上下文中受托人刻板印象根据与潜在客户的共同贡献对过去的受托人进行分组，并总结这些受托人的一般可信度。然后，我们形成对这些受托人作为一个群体的看法，并将潜在客户包括在该群体中，从而有效地将我们对该群体的看法转变为对潜在客户的看法α的极大似然估计使p（D α）=ip（Pi α）最大化。对数似然可以写成logp（D|α）=NlogΓ（αk）−NlogΓ（αk）+N（αk−1）logp<$k（3）k k k其中logp<$k=1logpik我这个目标在α中是凸的，因为Dirichlet分布是指数分布家人这意味着可能性是单峰的，并且可以通过简单的搜索找到最大值。相对于一个αk的对数似然的梯度为g=dloggp（D|α）=N（α）−N（α）+Nlogp<$K（四）（x）=dlog Γ（x）DX（五）函数的性质与自然对数相似。与指数族一样，当梯度为零时，期望的充分统计量等于观察到的充分统计量。在这种情况下，预期的充分统计量为E[logpk] =（αk）−（αk）（6）K观察到的充分统计量是logpk。用于最大化似然的固定点迭代，可以如下导出。给定α的初始猜测，我们构造一个简单的似然下界，它在α处是紧的。最大K146M. Tavakolifard，S.J.Knapskog/Electronic Notes in Theoretical Computer Science 244（2009）139Σ∈k−1−KKK这个界限的计算是在封闭的形式，它成为新的猜测。这样的迭代保证收敛到一个平稳点的可能性。对于狄利克雷，最大值是唯一的稳定点。如[11]所示，一个关于r（αk）导致以下固定点迭代：K（αnew）=该算法需要用[11]中描述的过程来反转该函数。4.2信任和不稳定的阶段假设A是信任者代理，B是受托者代理，C是推荐者代理。设有k个不同的离散评级水平。这转化为狄利克雷分布具有基数k的状态空间（在我们的模型中k为5）。让评级水平由i索引。代理C对代理B的每个新评级采取平凡向量的形式，其中只有一个元素具有值1，并且所有其他向量元素具有值0。值为1的向量元素的索引i指的是特定评级级别。作为新评级的结果，将通过将新接收的评级向量r添加到先前存储的向量R（贝叶斯推断）来更新评级向量。代理人可能会随着时间的推移改变他们的行为，因此希望给予最近的评级相对更大的权重。这可以通过引入寿命因子λ[0， 1]来实现;该因子控制旧评级的老化率和折扣率作为时间的函数。 当λ=0时，评级在 一个单一的时间段。当λ=1时，评级永远不会被遗忘。 在遇到其他药剂后，新的α将计算如下：αnew=αold.λ+R其中0≤λ≤1（8）为了在使用每个交互（8）之后调整λ。λ新=λold+SIMn其中SIM=1−θrt−outcomen2（9）在这个公式中，首先计算我们的估计和交互结果之间的相似性值（SIM）。 如果θrt和outcome相同，则SIM将等于1，否则将小于1且大于0。它们的差异的最大值是k1，在这种情况下，SIM将等于0。 基于 根据我们的估计与相互作用结果之间的相似性，将计算λ的新值。在该公式中，n是大于或等于2的自然数，并且基于应用而决定。例如，在有风险的应用中，在主体的行为发生变化后，λ的值应该急剧下降。因此，需要更大的n值。M. Tavakolifard，S.J.Knapskog/Electronic Notes in Theoretical Computer Science 244（2009）139147ΣKRTk−1我i=1然后我们计算Dirichlet分布的期望值α（θi）E（p（θ i）|α）=ki=1（十）α（θi）信誉分数可以表示为某个预定义区间内的单个值。这可以通过将点值θt分配给每个评级水平（对于k个不同的评级水平，在范围[0，1]中均匀分布的点值），并计算归一化的加权点估计得分来完成。 然后，点估计信誉分数被计算为：θˆ =i−1E（p（θ）|α）（11）5评价为了评估该算法的性能和效率，使用了一个由美国德克萨斯大学、法国EMSE、意大利ISTC和荷兰CWI联合开发的Agent系统信任和信誉测试平台ART.。 代理信誉和信任（ART）测试床[6]该倡议已经启动，目标是为代理信誉和信任相关技术建立一个试验平台。 ART试验台有两个目的：(1)作为一个竞争论坛，研究人员可以将他们的技术与客观指标进行比较，（2）作为一套具有灵活参数的工具，允许研究人员执行可定制的、易于重复的实验。每年，关于ART应用的研讨会与自治代理和多代理系统会议（AAMAS）一起举行，该会议旨在汇集能够更好地理解信任和声誉的研究人员在代理人社会中。选择这一选择的原因是：1）作为一个多功能，通用的实验网站，ART Testbed涵盖了相关的信任研究问题，并通过统一的实验方法将研究人员团结起来解决问题2）通过客观，定义明确的指标，测试床为研究人员提供了比较和验证其科学模型的工具，以及将新模型与以前的模型进行比较的可能性，3）站在巨人的肩膀上，4）可重用性。我们com-constructed提出的模型与Ntropi，并已显示出相当大的提高效率。5.1试验台的分析方法一般来说，最成功的代理人被选为银行账户余额最高的评估人。换句话说，能够（1）最准确地估计其画作的价值和（2）最谨慎地购买信息的评估师被认为是最成功的。 测试平台还提供了计算评估人最终评估的平均准确度以及该准确度的一致性的功能148M. Tavakolifard，S.J.Knapskog/Electronic Notes in Theoretical Computer Science 244（2009）139- 是的此外，还记录了评估人员之间传递的每种类型的消息的数量[6]。5.2仿真结果代理骨架被设计为允许研究人员在其评估者代理定制的信任表示和算法内植入，同时允许与其他实体的标准化通信协议。参与ART测试床的所有评估代理都是同一抽象类Agent的后代。该类定义了一组抽象方法，由研究人员进行编码，以定义他/她的评估代理的行为，以及一组方法，以促进与其他评估代理的通信。Agent类还提供了与Simulation Engine交互的方法（用于验证银行余额等任务我们使用了与ART Testbed Competition 2007相似的游戏规则：• 平均客户端/代理=20• 客户费用=100.0• 意见-成本=10.0• 声誉成本=0.1• 每次会话的时间步数：40该游戏由12个代理商从4不同类型：• 简单：代理不使用任何模型进行信任相关决策。• Ntropi：使用Ntropi模型进行信任相关决策的代理• 改进：使用改进模型进行信任相关决策的代理• 虚拟：来自测试平台本身的三个虚拟代理，我们曾经拥有更真实的环境。图2显示了结果。 图2中的水平轴显示时间步，垂直轴是银行总计（代理 所有改进的代理在所有时间步长中都有更高的银行账户，这表明它们的性能更好。6结论本文的主要贡献是，我们已经采用了第二贝叶斯算法，以估计先验信任的参数，使用Dirich-let分布，并介绍了一个新的层次贝叶斯信誉算法。此外，我们使用最大似然估计算法来估计Dirichlet分布的参数引用[1] A. Abdul-Rahman和S.海尔斯分布式信任模型。1997年新安全范例研讨会会议记录，第48-60页M. Tavakolifard，S.J.Knapskog/Electronic Notes in Theoretical Computer Science 244（2009）139149银行资产负债70000改进_360000改善_1改善_25000040000ntropi_3ntropi_2ntropi_1300002000010000Dummy_30Dummy_2Dummy_1-1000002468 10 1214161820时间步长图二. 结果[2] S. Buchegger和J.Y. 勒·布德克一种适用于移动Ad-hoc网络的鲁棒信誉系统。P2PEcon会议记录，2004年[3] R. Chen和W.耶格尔Poblano：一个对等网络的分布式信任模型。 JXTA安全项目白皮书，第1-26页[4] I. 张 文 辉 ， 王 文 辉 ， 陈 文 辉 . Sandberg ， and B. 威 利 使 用 Freenet 保 护 在 线 言 论 自 由 。 InternetComputing，IEEE，6（1）：40[5] Z. Despotovic和K.阿伯雷尔P2P网络中节点性能的最大似然估计2004年6月在美国马萨诸塞州剑桥举行的第二次对等系统经济学讲习班[6] K.K. Fullam，T.B. 克洛斯湾 Muller，J. Sabater，A. Schlosser，Z. Topol，K.S. Barber，J.S. 罗森沙因，L. Vercouter和M.佛斯代理信誉和信任（ART）测试平台的规范：代理社会中信任的实验和竞争。2005年第四届自治代理和多代理系统国际联合会议论文集，第512-518页[7] Gnutella协议开发0.6. 方案规范。[8] A. Jøsang和J. Haller。狄利克雷信誉系统。 第二届可用性、可靠性和安全性国际会议（ARES），2007年。[9] K. Quinn和A.莱迪ebs/cd/a-04：000737 uen.技术报告，爱立信研究，2004年。[10] K. Quinn，D. OSullivan，D.刘易斯河，巴西-地 布伦南和副总统韦德。 deepTrust管理应用程序，用于发现、选择和组合可信服务。IDIP/IEEE第9届集成网络管理国际研讨会（IM 2005），法国尼斯，2005年[11] G.朗宁Dirichlet分布的极大似然估计。Journal of Statistical Computation and Simulation，32（4）：215[12] B.T.你好自由港项目中的信任经济。 麻省理工学院博士论文，2000年。银行共计