毕业答辩08250403-冀武.ppt

P2P网络激励机制的研究,班级：通信工程四班,学生：冀武,学号：08250403,指导老师：陈作汉,第三章：P2P激励机制的研究,3,第一章：P2P网络的介绍,1,第二章：P2P网络信任管理,2,第四章：仿真实验,4,6,目录,5,第五章：总结,简单的说，P2P技术是一种用于不同PC用户之间不经过中继设备而直接交换数据或服务的技术。在P2P网络中，每个结点的地位都是相同的，可以同时作为服务使用者和服务提供者，具备了客户端和服务器双重属性。,第一章：P2P网络的介绍,2010.06,1.1P2P技术,因特网最基本的TCP/IP协议并没有客户机和服务器的概念，所有的设备都是通信平等的一端，同时具有服务器和客户机的功能，因此我们说P2P技术并不是新概念。P2P技术的思想在计算机网络诞生的早期已经存在，不过受早期计算机性能、资源等因素的限制，大多数连接到因特网上的普通用户并没有能力提供网络服务，从而逐步形成了以少数具有较高处理能力但非常昂贵的服务器为中心的客户机/服务器（C/S）架构。P2P技术再次引起学术界及商界的重视，主要有以下两大因素的影响：一是用户的需求。随着因特网的逐渐普及并深入到人们的日常生活，人们需要更直接、更广泛的信息交流以实现更多的资源和服务共享；二是技术发展。首先是网络技术的发展，网络技术一方面促进Internet在全世界的普及，使越来越多的用户可以实现与Internet的连接，一方面又使Internet接入速度和骨干网的带宽得以大幅度提高，为各种网络应用的发展创造了条件。,2010.06,1.2P2P产生的背景,其次是软硬件技术（特别是芯片技术）的发展，它们使得个人PC在计算能力和存储能力上有了极大提高，计算机性能的提高使各种网络终端具备了一定的网络服务能力，为P2P的应用创造了条件。最后是集中式网络模式所造成的带宽瓶颈以及网络稳定性等方面的问题，这些都迫使人们开始寻求一些新的网络应用模式。P2P技术就是在这样的背景下产生，并一名美国大学生编写的Napster将P2P技术重新带回到了网络世界。,P2P网络主要分为以下几类：（1）混合式P2P（2）无结构P2P体系（3）结构化P2P体系,1.3P2P技术的主要应用领域,1.4P2P网络的分类,目前P2P应用主要分为以下4类：（1）P2P文件下载（2）P2P在视频直播中的应用（3）P2P在其它领域的应用,目前P2P技术还不成熟，限制其发展的因素主要有：版权问题、管理问题、安全性差、垃圾信息、带宽占用和盈利模式。但是其发展还是吸引了众多领域的高度关注。从商业应用来看，目前P2P业界存在两种趋势：扩张与合并。从计算机领域的各大会议、刊物特别是P2P专业会议发表的论文来看，P2P的研究重点已经从核心机制逐渐转向增强机制，目前的研究热点集中在以下几个方面：P2P网络中的语义模糊查询、容错性、拓扑意识与一致性问题、声誉和安全性问题。,1.5P2P技术的未来发展,第二章：P2P网络信任管理,基于如何激励节点贡献出其各自资源的前提是给予它们一个相对安全的信任环境，我们讨论了目前比较常见的几种P2P信任管理模型，并指出其各自优劣。,P2P信任管理技术的思想是模仿现实社会中的信任建立过程，根据用户之间过去发生的交易行为及其参与节点的反馈信息，对网络中的每个节点给出一个“可信程度”的评价，节点在请求服务时可以根据此评价值来选择“可信”的服务提供者。,2.1什么是信任管理,2.2信任模型分类信任模型是信任机制中比较高层的构件，它的作用是保证成员的可信性和资源的可信性，目前存在若干基于P2P环境的信任模型，可以归为以下几类：（一）基于PKI的信任模型（二）使用数据签名的信任模型（三）全局可信度信任模型（四）局部信任模型,第三章：P2P激励机制的研究,在一个典型的P2P网络中，节点不从属与网络中的任何其他实体，而是自我管理并自主决定资源贡献。然而，节点由于固有的理性都希望最大化自己的利益和效用，同时最小化自己对其他节点提供的资源。P2P网络中大量节点做出这种理性选择的结果将是一种困境：P2P网络的效率大幅度降低，绝大部分节点都无法得到正常的服务，即产生了个人利益与系统性能相冲突的搭便车问题。因此，在P2P网络中设计一种激励机制来促使节点提高对系统的资源，从而在节点之间建立一种公平的互相交易环境具有非常重要的意义。,3.1P2P激励机制的研究目标,根据激励机制的作用和功能可知，若要在P2P网络中建立一种可行和高效的激励机制，其目标应包含以下几个特征：（一）可扩展性（二）自治性（三）效率（四）健壮性。P2P网络中激励机制的研究不仅包括一整套符合上述研究目标的协议设计，还包括系统仿真或系统实现以进行机制性能的评估。具体而言，主要存在以下几个问题和挑战：（一）如何构建及量化激励机制以促进节点合作（二）如何评估搭便车行为对系统性能的影响（三）如何鼓励节点的直接和间接互惠（四）如何处理新加入节点问题。,3.2P2P网络中典型的激励机制针对搭便车问题，近年来国内外学者研究和发展了不同的激励机制：从是否需要中央服务器来看，可分为基于微支付的模型和基于互惠的模型；从激励机制的可靠性和复杂度方面而言，可以将基于互惠的模型进一步分为基于直接互惠和基于间接互惠（信誉）的模型。实际上，研究人员还提出了包括基于分数、令牌、百分数等其他一些激励机制。从核心思想上讲，这些激励机制均可归入基于微支付，直接互惠和信誉等三种模型的一种。,（1）基于微支付的机制虚拟货币是一种在P2P网络中可流通的标识，用于对网络中的服务或资源进行量化表示。基于微支付的机制核心思想是以虚拟货币作为P2P网络中服务或资源交易的媒介，服务提供节点可以通过中央服务器收取由服务请求节点支付的虚拟货币。实际上虚拟货币体现了对节点贡献的反馈，从而使得节点有积极性去参与合作。文献13首先提出了基于微支付的激励机制，并用博弈论的方法分析证明该机制对防止搭便车问题的有效性。在该机制中，每个节点的下载量、网络带宽、空间消耗和利他特性等参数来表达：通过节点博弈建模得到P2P网络的Nash均衡，在均衡状态下每个节点均采用一种最高等级上传和下载的策略，因此有效的激励节点提供上传服务。节点之间的交易过程可如图3-1所示。,微支付机制涉及的中央服务器需要负责维持所有节点的账户，发行和分配虚拟货币以及为节点交易提供安全机制，因此中央服务器负荷较大。考虑到节点同时作为服务提供者和请求者的可能性较大，于是可以从提高系统可靠性和充分利用节点资源出发对基于微支付的激励机制进行改进。,图3-1基于微支付的节点交易,基于微支付的激励机制除了可行性较差外，还存在着以下两个问题：1）隐藏信息问题：目前计算机领域的隐藏信息问题的解决方法主要是采用经济学中的机制设计17，然而如何将机制设计有效合理的应用到P2P网络中还缺乏深入的研究；2）信息不对称问题：该问题在AdHoc等其他类型网络中已有了一定的研究，目前主要采取经济学中的委托代理模型来解决18。但如何将该模型和P2P网络的特性结合起来仍然没有得到很好的解决。,（二）基于直接互惠的机制基于直接互惠的机制的基本思想是P2P网络中的服务提供节点在为其他节点提供服务后得到某种直接优惠。这种激励机制首先在文献19中得到体现，。在BitTorrent中，节点在每一次的交易过程中针对向他提供服务的节点给予同等的回报，并且这种互相之间的回报是实时的进行更新。基于直接互惠的激励机制关键在于每个节点对于其他节点历史信息的维护仅存在于一次Session中。也就是说在该次Session结束后，互相提供服务的节点对彼此的贡献情况将一无所知。该机制的简单示意可由下图3-2表示。,目前来说，基于直接互惠的激励机制应用范围较小，仅适合一些特定的场合。其原因在于：一方面，P2P网络中缺乏重复的交易即两个节点在长时间内不断进行交易的可能性较小；另一方面，P2P网络中存在着各种节点能力不对称的节点如高性能服务器、PC和PDA等，节点可能由于计算能力所限无法表达自己希望参与贡献的意愿。,图3-2直接互惠机制,（三）基于信誉的机制基于信誉的机制主要是在P2P网络中引入了一个等级的概念，即每一个节点根据自己在网络的历史行为情况获得由网络中与它邻近的其他节点所评价得出的信誉值。在以后的服务或资源交易中，其他节点均根据请求节点的信誉值给予对应等级的回应。该机制与基于直接互惠的激励机制的重要区别是在基于信誉的机制中，某一节点对其他节点的贡献分布式的存储于其他节点的历史记录中，该节点在以后的交易中凭借自己先前对网络做出的贡献获得其他节点提供的资源。基于信誉的激励机制是近年来研究较多的一个方面，最早是在P2P文件共享系统KaZaA22中提出。文献23则首次利用博弈论的思想阐述了基于信誉的激励机制的有效性，它将P2P网络建模为一种非合作的博弈过程，通过设定一个接受请求的概率函数来确定对不同信誉的节点提供不同的服务。这种机制的一个简单示例可由图3-3表示。,这种激励机制扩展性更强，适用于P2P网络规模较大，节点的动态性较强并且节点之间重复交易部频繁的应用场合。采用这种机制后，节点在邻居选择方面和拓扑组织方面可以优先选择信誉高的节点，于是参与贡献的节点形成一种集群组织，从而防止搭便车和公共悲剧问题。但该机制需要从第三方获取信息，因此存在着信息的可靠性问题和对信息提供节点的信任问题。此外，如何减少节点间共享交易记录，信誉等产生的大量开销，以及这些信息如何共享也是需要解决的关键问题。除了上述几个问题外，基于信誉的激励机制主要还存在着以下两个关键问题；,图3-3基于信誉的激励机制,（1）如何处理whitewashing问题：该问题是指节点在P2P网络中做出一些恶劣行为后，通过重新加入网络的方式来取得新的身份。目前该问题一种可行的解决办法是对新加入者进行惩罚，使得节点无法从一开始就享受较好的服务。（2）如何防止共谋问题：该问题是指如何防止节点之间不存在实际交易的情况下互相连续的给予对方高信誉，从而使双方获益。对于该问题，文献2425分别设计EigenTrust算法和maxflow算法，通过信任机制和信誉限制来防止共谋行为对P2P网络信誉机制的破坏。,（四）三种激励机制的比较,表3-4几种激励机制的比较,如上表3-4所示，在这几种P2P网络激励机制中，基于信誉的模型由于其扩展性和实用性等优势，维持了节点的匿名性和自主性，更加符合对等网络的基本思想。因此，总体来说，我们认为基于信誉的激励机制更加具有研究价值，是未来P2P网络中激励机制研究的一个重要方向。,3.3基于贡献值的激励机制模型,针对P2P系统中节点资源共享出现(Freeridding）的现象，提出一种基于贡献值的激励机制模型，节点根据请求者的贡献值分配其资源，同时增加自己的贡献值，从而能够享受更高的服务质量和下载优先级。本模型设计的效用函数包括以下自变量：节点共享资源已被下载的数量、节点从其他节点已下载资源的数量和节点在线时间内提供服务的奖励。节点i的贡献值（Contribution）用C(i)来表示，保存在组节点服务器的相应节点信息里，当节点i向其他节点提供服务，它的C(i)将会增加；当节点i享用了其他节点提供的服务后，它的C(i)将会减少。用DCount(f,i)表示节点i提供的共享资源被下载的数量，其共享资源被下载次数越多，说明它所共享的资源在对等网络中越受欢迎，越具有价值，那么节点的贡献值就越大；用Down(f,i)表示节点i使用其他节点提供的资源，节点自身收益就越大，则它的贡献值就越小。K(t,i)表示节点i在其在线时间（t)内提供服务的一种奖励，与其在线时间内被下载资源的数量成正比为其他节点提供资源下载数量，这种奖励是鼓励能够为其他节点提供资源下载服务的节点尽量长时间在线，因为在P2P网络中，节点在线时间越长，那么它为其他节点提供服务的机会就越多，这正是P2P网络的设计理念。,则节点i的贡献值C(i)可以表示为（3.1）效用函数（3.1）既考虑了节点提供的共享资源在对等网络中受欢迎程度，又考虑了鼓励节点多在线为其他节点提供服务，是一个规范化系数，是个常量。表示节点i的奖励值，是惩罚值。奖励值中包括节点i为其他节点提供下载资源的贡献值与在线时间的奖励之和，惩罚值是节点i从网络中下载资源数量之和，已下载资源越多则惩罚值越大。因此，此效用函数有利于那些提供很多的受欢迎资源以及在线时间内提供服务的节点享受服务质量，又可以有效的区分那些提供不被访问资源和只从网络中下载资源的搭便车节点。在协作学习P2P网络中，各个节点的贡献值根据节点的具体情况而发生变化，因此所获得的资源服务质量也随之发生变化。基于贡献值的资源分配原则是“多劳多得”、“先劳先得”。对于资源请求者而言，贡献值越大，及时得到满足的概率就越高，从而促使其做更多贡献；对于资源提供者而言，为了尽可能增大自己的贡献值，在做资源分配时，应把资源优先分配给贡献值大的节点，同时根据资源的受欢迎度排序，越受欢迎的资源排在最里面，节省检索时间，提高查询效率。,3.4基于博弈论的激励机制模型针对P2P系统中普遍存在的搭便车和公共悲剧问题，提出了一种基于博弈论的P2P服务质量激励机制。在分析节点在网络中的贡献和收益的基础上，通过引入激励值的概念来体现网络节点服务质量的高低，同时给出了有关节点服务质量四个方面的定义。博弈是对战略相互作用的描述，它包括参与人所能采取的行动的约束和参与人的兴趣，但不强调参与人实际采取的行动。它的解是对结果的系统描述，这种结果可能产生于一种博弈。博弈论给出各种博弈的合理解释并且考察他们的性质。文献9提出的激励模型中，给出了节点的效用函数，即节点加入系统中所需付出的代价和从系统所获得的收益之差，但它并没有体现出节点间的服务质量的差异。这里引入一个激励值的概念，它的大小表示为请求节点提供服务质量的高低，即若某个节点的激励值越高，则当其请求资源时所获得的服务质量越高；若某个节点的激励值越低，则当其请求资源时所获得的服务质量就越低。,用表示节点i在t时刻的激励值，其计算公式如式（3.2）所示（3.2）在式（3.2）中，表示为节点i在t时刻的效用函数，在文献9基础上对效用函数中节点加入系统的代价进行了改进，其计算公式如式（3。3）所示。（3.3）（3.3）在式（3.3）中，为一个差异服务概率函数，表示节点贡献的资源越多，则获得服务的概率就越大；其中m为节点个数，表示在节点j所贡献的所有资源中，对节点i有用的资源所占的比重。在式（2）中，为计算节点激励值时所用的衰减函数，引入该函数的目的是初始化刚加入网络的新节点使其有一定的激励值，同时调整那些激励值高的节点使其激励值趋近于一个稳定的阈值，其计算公式如式（3.4）所示。（3.4）（4）在式（4）中是节点i用于衰减的权值。,为了体现节点的服务质量从节点的下载速度、下载优先级、TTL跳数以及请求延时等四个方面来考虑。参加节点的激励值，依次给出了四方面的定义。（1）下载速度的定义下载速度是指网络中某个请求节点所分配到的对于某个文件的下载带宽。对于请求节点的下载速度的分配，取决于它们自身的激励值占所有请求节点的激励值的比重，用表示t时刻节点i所获得的下载速度的大小，其计算公式如式（3.5）所示（3.5）当时，该请求节点所获得的下载速度也为0，即该节点将无法下载文件。当时，则该请求节点处于阻塞状态，进入等待行列。其中值是一个阈值，表示网络中节点上传带宽的最小单位。,（2）下载优先级的定义下载优先是指当某个节点出现热点文件时，对于所有请求该节点的节点请求，将按各个请求节点的优先级顺序，从高到低依次为其提供访问服务。对于请求节点下载优先级的分配，只是针对那些处于阻塞状态的节点，即如果各个请求节点获得的下载速度都大于阈值，则它们之间的优先级没有区别。既然是在等待队列中，对各个请求节点进行优先级排序，那么就不能仅仅取决于节点之间的激励值大小，还要考虑他们的等待时间，用表示在t时刻节点i的优先度，其计算公式如式（3.6）所示（3.6）在式（3.6）中，用表示时刻t节点i已经阻塞的时间。所谓优先度是衡量节点对下载文件优先级的一个数值。等待节点的优先度越大，则表示该节点的优先级越高；反之，则表示该节点的优先级越低。,3）TTL跳数的定义额外增加TTL跳数指适当的增加请求节点在文件搜索过程中的TTL跳数，依次扩大文件搜索的范围，以及文件搜索的命中率。对于请求节点的额外TTL跳数增加，主要取决于它们一定时间内所积累的平均激励值的多少，用表示t时刻节点i所获得的TTL额外增加的跳数值，其计算公式如式（3.7）所示（3.7）在式（3.7）中，表示节点i在k个时间间隔内的平均激励值；为系统的一个常量，表示给请求节点增加额外TTL跳数所需要的最小激励值。当，时，为0，即不增加额外的TTL跳数。,4）请求延时的定义请求延时是指网络中某个请求节点发出请求到收到请求恢复的间隔时间。对于网络中节点的请求延时，不仅取决于网络的传输带宽，还取决于下载链接源节点的等待时间，用表示t时刻节点i的请求延时，其计算公式如式（3.8）所示（3.8）当时，节点的请求延时较长。,第四章：仿真实验,（一）基于贡献值的激励机模型,。,在这里我们采用了Eclipse仿真平台。Eclipse是一个开放源代码的、基于Java的可扩展开发平台。就其本身而言，它只是一个框架和一组服务，用于通过插件组件构建开发环境。幸运的是，Eclipse附带了一个标准的插件集，包括Java开发工具（JavaDevelopmentKit，JDK）。,实验规模包括1000个节点，节点分为两类；一类是贡献节点，该类节点的贡献值大于0，其贡献的资源大于占用的存储资源，另一类是搭便车节点，该类节点的贡献值小于0，其贡献的资源小于占用的存储资源。在P2P仿真系统中，应用环境是文件共享服务，文件分布满足Zipf定律，其中贡献节点占55%，搭便车节点占45%。首先对比了激励机制对贡献节点和搭便车节点享受服务能的影响。我们模拟了8个时间周期，在每个时间周期，每个节点的请求时随机产生，以规定的TTL向邻居节点进行服务搜索。图4-1是贡献节点的平均享受服务的能力变化情况，可是看出做出贡献越大的节点会使其享受服务的能力快速增加，从而能够享受更高的服务质量和下载优先级。图4-2是搭便车节点的平均享受服务的能力变化情况。由于搭便车节点为了最大化自己利益，尽可能多的从其他节点获取资源而几乎不做出贡献，享受服务的能力迅速下降，从而享有较低的服务质量和优先级。,其次，比较了基于激励机制的P2P系统和没有引入激励机制的P2P系统随着时间的变化，系统可用资源的变化情况。从图4-3中可以看出，未引入激励机制的P2P系统可用资源随时间变化并不明显，而引入激励机制的P2P系统可用资源随时间变化增加较快。这主要因为引入激励机制的P2P系统节点获取的资源和其他贡献资源的多少直接关联，节点贡献越多资源，其贡献值和享受服务的能力就大，进而能获取更多资源，而未引入激励机制的P2P系统中的节点对贡献资源没有积极性，其是否贡献资源并不影响其他获取资源。,图4-1贡献节点的享受服务能力变化,评价周期（天）,图4-2搭便车节点享受服务能力变化,针对P2P文件共享中的大量搭便车现象，提出了一种基于贡献值的新型激励机制，该机制根据节点的贡献值进行资源分配，节点共享的资源被下载次数越多，其贡献值就越大，贡献值越大的节点就能获得高的服务质量和优先级。同时引入了时间衰减机制，防止贡献值“通货膨胀”，使得节点的贡献值始终能保持平稳以及能取得更好的激励效果，使得原先贡献值低的节点在经历一段时间后能够获得更多获取资源的机会，使那些贡献值高的节点由于长时间贡献少而丧失其累计的贡献值。仿真实验表明，基于贡献值的资源分配算法能有效的实现P2P系统中资源分配的公平性和效率，鼓励了贡献节点，同时抑制了搭便车现象。,图4-3系统可用资源随时间的变化,（二）基于博弈论的激励模型,该机制主要思想是：运用博弈论原理及相关模型，分析节点与节点间的博弈行为，通过节点的贡献、节点的激励值以及节点的服务质量等方面的定义与计算，激励P2P网络中的各个节点自发的贡献拥有的资源以提高网络的服务质量。为了评价博弈论的P2P激励机制的性能，进行了仿真实验。假设网络中有1000个节点，节点分成三类：一类节点成为自私节点SN（SelfishNode)，其贡献的资源小于从其他节点获得的资源；另外一类节点成为无私节点AN（AltruismNode），其贡献的资源大于从其他节点获得的资源；第三类成为其他节点ON（OtherNode），该类节点既不贡献资源，也不从其他节点获得资源。在P2P仿真系统中，初始化SN类节点所占比例为30%，AN类节点所占比例为60%，ON类节点所占比了为10%。,1.网络总收益、节点贡献总量和网络总激励值的分析实验一模拟在引入该激励机制的P2P系统中，随着博弈次数的增加，网络总收益、节点贡献总量及网络总激励值的变化情况。图4-4为博弈次数与网络总收益的关系图，可以看出，在网络形成的初期，即节点新加入网络的时候，网络的总收益并不是很高，但随着节点与节点之间博弈次数的增加，整个网络的总收益将大幅度上升，并逐渐趋向一个稳定值，这个定值就是博弈论中所谓的纳什均衡点。图4-5为博弈次数与节点贡献总量的关系图，通过节点之间的重复博弈，网络中的节点的贡献总量不断提高，这从另一个侧面反映出每个节点对网络的贡献量在不断增大，最后，贡献总量趋向于平衡，表示节点之间的博弈已经达到了纳什均衡。图4-6为博弈次数与网络总激励值的关系图，可以看出，虽然各个节点通过相互博弈，不断使自己