摘 要

传统的对等（P2P）网络不能为用户提供服务差异化和激励。因此，用户可以轻松访问信息，而不向P2P社区贡献任何信息或服务。这导致了“搭便车”问题，因此，大多数信息请求都针对少数P2P节点，它们愿意分享信息或提供服务，因此导致“公共悲剧”。这项工作的目的是根据每个节点提供给P2P社区的服务量来提供服务差异化。由于是基于贡献的数量进行区分，所以这鼓励所有节点在P2P网络中共享信息/服务。我们首先介绍所有信息共享节点的资源分配机制。这种机制是一种具有线性时间复杂度的分布式算法，保证了“帕累托优化”资源分配。其次，我们将整个资源请求和分发过程建模为所有竞争节点之间的竞争游戏。我们显示这个游戏具有纳什均衡，并具有串通防御功能。为了实现这个游戏，我们提出了一个协议，使得所有的竞争节点都可以与信息提供节点进行交互，从而可以有效和动态地达到纳什均衡。进行实验以说明协议提供服务差异化并且为节点共享信息或提供服务的诱导。最后，我们表明我们的协议适应不同的节点到达和离开事件，以及不同形式的网络拥塞。

关键词 - 基于贡献的服务差异化，游戏理论，激励协议，对等网络。

目录

摘 要 II

目录 III

第一章 绪论 4

1.1课题研究背景 4

1.2 研究的目的与意义 5

第二章 开发工具及技术 6

2.1开发工具 6

2.1.1 IntelliJ IDEA15 6

2.2开发技术 6

2.2.1 Java语言 6

第三章 基于博弈论的激励模型的算法分析 7

3.1 资源管理机制 7

3.1.1 资源招标机制（RBM） 8

3.1.2激励资源招标机制（RBM-I） 9

3.1.3具有效用特征的资源招标机制（RBM-U） 10

3.1.4具有激励和效用特征的资源招标机制（RBM-IU） 11

3.2 逐步填充算法在模拟程序中的实现 13

第四章 游戏竞赛协议 15

4.1 理论竞赛 15

4.2 实现游戏竞赛协议 16

第五章 实验 18

5.1 实验 18

5.1.1实验A（激励资源分配） 18

5.1.2实验B（适应于竞争节点的动态加入和离开） 21

5.1.3实验C（自适应网络拥塞） 23

5.2模拟程序 24

5.2.1类图 24

5.2.2程序运行图 25

5.2.3流程图 25

第六章 结论 27

参考文献 28

致谢 30

第一章 绪论

1.1课题研究背景

近来很多人对P2P网络感兴趣。 如ISP的流量测量所证明的，大量的现有网络流量是由于P2P应用。 这些应用程序旨在利用信息交换的协作范例，大大增加信息对大量网络用户的可访问性。 与传统的客户端 - 服务器网络不同，P2P范例允许单个用户（或节点）同时扮演服务器和客户端的角色。因此，P2P网络中的节点可以在文件搜索，文件查找和文件传输以匿名方式互相帮助。 对于文件搜索，P2P网络已经从集中文件/目录查找方法（例如，Napster）演变为分布式对象查询方法（例如，Gnutella）。 分布式对象查询可以通过受控流程的一种形式来实现，然而P2P网络（例如Chord和CAN）的新生使用一致性散列的方法来提高文件查找的效率。

虽然当前的许多研究集中在提高P2P网络中文件搜索/查找的性能，但一些信息交换的基本合作范式的和具有挑战性的问题仍然没有得到解决。免费骑马和公共悲剧是两个这样的问题。近70％的P2P用户不在P2P社区中共享任何文件。 相反，这些用户只是免费使用其他共享信息的用户。由于很少有用户愿意共享信息或向他人提供服务，所有文件搜索响应中有近50％来自信息共享节点的前1％。 因此，共享信息和资源的节点容易拥塞，这导致公共问题的悲剧——即每个人都都倾向于过度使用。总之，现有的P2P网络不提供服务区分，因此，没有激励用户共享信息或提供文件传输服务。

最近，在P2P软件中实现了一些初步机制，鼓励人们共享信息。例如，Kazaa考虑每个同伴的“参与程度”。参与级别被计算为对等体的最近上载和下载之间的比率。然而，该比率不随时间累积，并且仅提供对查询请求的区分。 另一个P2P系统eMule建立了一种信用系统，其中在任何两个特定节点之间交换信用。在将其上传资源分配给竞争请求对等体时，信息提供节点给先前已经提供更多上传信息提供节点的对等体提供较小的排队延迟。但没有为Kazaa和eMule提供其机制的正式分析，包括竞争节点的公平性。

1.2 研究的目的与意义

在本文中，我们提出了一种基于个体节点贡献度提供服务差异化协议。大致来说，分享流行文件并通过文件上传向P2P社区提供更多服务的节点将具有更高的贡献水平。作为回报，当该节点要求文件传输服务时，它将比其他具有较低贡献级别的竞争节点获得更高的效用。我们提出的激励协议集中于文件传输过程，因为每单位时间的数据传输量远远高于对象查询/查询的数据传输量。我们讨论了将激励兼容的分配机制纳入P2P协议的重要性。资源分配机制的目标是（i）

提供服务差异化，（ii）鼓励节点共享信息或服务，（iii）最大化社会福利[16]或个人用户的综合效用。重要的是要指出，我们的激励协议可以由使用分布式查询（例如，Gnutella）或一致的散列方法（例如Chord或CAN）的各种P2P系统采用。

我们的激励兼容资源分配机制具有以下特点：

1.公平性：对P2P网络贡献更多的节点应该获得更多的资源或更高的效用。

2.避免资源浪费：机制不会为不能消耗的节点分配更多的资源。 如果通信路径之间存在拥塞，则该机制可以适应拥塞水平并分配适当的资源量。

3.适应性和可扩展性：机制可以适应网络拥塞和动态节点加入或离开等条件。这中机制安装在每个节点，随着P2P网络的规模越来越大，可扩展。

4.社会效用最大化：在某些情况下，我们的机制不仅仅是最大限度地利用个人利益，而且为用户实现了高度的综合效用。

正如我们将要展示的，所提出的机制是不同需求的用户投标资源，从而创造一个动态的竞争游戏。为了保证P2P网络中的每个节点都要诚实地遵循机制，创建的动态游戏应该是具有战略意义和串通的。第一个属性意味着，提出的机制之后是P2P网络中每个用户的最佳策略。第二个属性意味着用户无法通过合作欺骗系统获得额外的资源。

第二章 开发工具及技术

2.1开发工具

2.1.1 IntelliJ IDEA15

IntelliJ IDEA是一款综合的Java 编程环境，被许多业内推崇为市场上最好的IDE。它尽可能的增快了程序员的编程速度，它同时包括了很多辅助功能。这套软件就是以其聪明的即时分析和方便的 refactoring功能深获大家所喜爱。缺点是较复杂，对初学者来说，理解起来比较困难。在代码自动提示、代码分析等方面的具有很好的功能。

2.2开发技术

2.2.1 Java语言

Java是一门面向对象编程语言，吸收了c 语言各种优点。Java作为静态面向对象编程语言的代表，极好的实现了面向对象理论。对程序员来说，这意味着要注意应中的数据和操纵数据的方法(method)，而不是严格地用过程来思考。在一个面向对象的系统中，类是(class)数据和操作数据的方法的集合。数据和方法一起描述对象(object)的状态和行为。每一对象是其状态和行为的封装。类是按一定体系和层次安排的，使得子类可以从超类继承行为。在这个类层次体系中有一个根类，它是具有一般行为的类。Java程序是用类来组织的。

Swing是Java基础类的一部分，是一个为Java设计的GUI工具包。Swing提供了捕捉用户输入的方法，提供改变在屏幕上看到的颜色的方法，提供了文本组件，处理所有普通任务。此次模拟程序的GUI界面便是由Swing组成。

第三章 基于博弈论的激励模型的算法分析

本章是论文的核心之一，针对网络中存在的搭便车现象，提出一种基于纳什均衡理论的激励机制。首先通过分析资源招标机制（RBM）分析了在网络中存在的纳什均衡，确定了结点贡献值、效用函数以及激励值的算法，给出了分配算法——逐步填充算法（implementation of the Progressive Filling (PF) algorithm）。

3.1 资源管理机制

类似于其他P2P系统，我们的P2P激励网络中的每个节点也同时播放服务器和客户端。 在文件传输过程中，执行文件共享服务的节点（例如将文件上传到其他节点）称为“源节点”，以N_s表示。 节点请求文 件N_s的负载称为“竞争节点”，表示为N₁ ... N_N，其中N是竞争节点的数量。 激励P2P网络中的每个节点具有贡献值，表示节点向整个P2P社区提供了多少服务。

相关图片展示：