点对点网络中信息资源分配的算法实现.docx

摘要：近年来，随着无线通信与互联网技术的高速发展，使得信息技术资源可以突破传统的行政管理界限，在互联网中广泛流通、交换与共享.信息资源的交换与共享，不仅需要点对点网络平台的搭建，更需要设计出合理、公平、有效的资源传输协议. 2007年Wu和Zhang[1]将P2P网络中的信息资源交换模型化为经济学中的纯交换经济。他们从经济学的角度考察市场均衡，并以市场均衡中的分配方式作为P2P网络中信息资源的分配协议。为此，他们提出了图的瓶颈分解思想，并根据图的瓶颈分解结构，构造出一个市场均衡。遗憾的是，[1]并没有给出瓶颈分解的具体算法。因此，本文的主要贡献是根据[1]中瓶颈分解的主要思想，设计出瓶颈分解的多项式时间算法。此外，我们将详细解释如何根据由瓶颈分解得到的图的分解结果，利用最大流算法，给出点对点网络中信息资源分配方案，并进一步分析该分配方案与交换经济中的市场均衡之间联系。

关键词：点对点网络；瓶颈分解；带宽共享；交换经济

目录

摘要

Abstract

1引言-1

2概述-2

2.1课题应用背景-2

2.2课题研究的主要内容-3

3P2P网络中信息资源交换问题-4

3.1P2P网络概述-4

3.1.1 P2P网络-4

3.1.2 P2P网络带宽共享问题-5

3.2比例反应协议-5

4瓶颈分解及其相关性质-5

4.1瓶颈分解-6

4.1.1最大瓶颈-6

4.1.2瓶颈分解的定义-6

4.2瓶颈分解的相关性质-7

5计算瓶颈分解的多项式时间算法-10

5.1算法主要思想-10

5.1.1迭代计算-10

5.1.2二分法计算-10

5.2网络-10

5.3瓶颈分解的多项式时间算法-12

5.3.1算法A：计算最小比-12

5.3.2确定最大瓶颈-13

5.3.3算法的实际应用-13

6瓶颈分解与市场均衡-16

6.1市场均衡-16

6.2瓶颈分解与市场均衡-17

7结论-20

参考文献-22

致谢-23

附录-24