基于覆盖网高效信息定位的技术探讨
VIP免费
摘 要
在现实世界中“任何一个陌生人之间所间隔的人不会超过六个” ，这就是六
度空间理论所阐述的内容。这不仅是说人与人可以经过六个或更少个层次的中转
就能产生联系，也意味着人与周围环境是存在密切联系的，不是一个独立的存在。
与人类社会类似，P2P 网络中的节点也不是孤立的点，它们能通过各种方式的路由
进行信息交互。所不同的是，前者是利用兴趣、爱好或者共同特征聚合而成，查
找过程快速而简便；后者在逻辑结构上和物理结构上往往不相匹配，而且其查找
过程是按照协议进行有规律的查询，不能根据环境的不同而进行优化。考虑到两
种网络的相似性，如果能把六度空间理论应用到 P2P 网络中，那么将有可能会改
善P2P 网络的性能。论文为了验证这种可能性，做了如下工作。
第一，介绍了六度空间理论在实际生活中的应用，并讨论了它的一些性质。
第二，深入分析了几种典型的 P2P 网络拓扑结构，并进一步讨论了基于这几种
结构的信息定位算法。
第三，参照六度空间特性，尝试建立了基于兴趣的 P2P 网络拓扑模型。在模型
中，不同节点之间利用计算兴趣特征向量相似度的方法来模拟人类真实社会关系
以产生关联。同时，由于系统把 IP 地址作为兴趣特征向量的一个重要特征词，因
此模型缓解了因 P2P 网络物理地址和逻辑地址不匹配导致的信息查询“舍近求远”
的问题。同时，由于兴趣特征向量的特征词是用文字进行描述的，所以模型支持
语义查询功能。
第四，提出了基于上述模型的信息查询路由算法，并通过模拟实验实践了相关
的关键算法。
论文最终说明参照六度空间特性建立的基于兴趣的 P2P 信息查询网络拓扑不
仅提高了信息定位的效率、支持语义查询，也可以帮助解决物理地址和逻辑地址
不匹配的问题。
关键词：六度空间理论 兴趣特征向量 信息定位算法 P2P 网络拓扑
ABSTRACT
In the real world, there is no more than six persons between two strangers in any
interval, what is the Six Degrees of Separation theory expounded. It not only means that
within six or fewer different links we can communicate with any people, but also means
people who live in human society are closely linked. Similar to human society, P2P
network node is not an isolated point, they are connected by exchanging information
using the network's physical route. The difference is that the former uses interest,
hobbies or a common characteristic to polymerize different interest clusters, while the
latter uses the logical structure and physical structure to locate data. The process can't be
optimized according to the environment because of their contradiction. Taking into
account the similarity of two networks, if we can apply Six Degrees of Separation
theory into P2P network, it will be possible to improve the performance of P2P
networks. In order to verify this possibility, the paper has done the following work.
First, it gave an introduction of Six Degrees of Separation theory's application in
real life, and then it discussed some of its properties.
Second, it made some in-depth analysis of some typical P2P network topologies,
and made further discussions about information localization algorithms based on the
structures been informed.
Third, according to the properties of Six Degrees of Separation theory, the paper
built a model which is basing on interest. In the model, data's association is generated
by calculating the similarity of different feature vectors. Because IP address is a
important feature of the interest vector, the model solved the collision of P2P network
physical structure and logical structure. At the same time, due to the model data was
described in words and the links were generated by calculating data similarity, the
model supported semantic query capabilities.
Fourth, the paper not only submitted several different data routing ways, but also
validated its feasibility by simulating these processes.
The Paper finally verified that the Six Degrees of Separation theory could be
applied into P2P network topology. The method not only improved the efficiency of
locating information, supporting semantic query, but also to solve the physical address
and logical address conflict issues.
Key Words: Six Degrees of Separation theory, Interested Eigenvector，
Information Localization Algorithm, P2P Network Topology
目 录
中文摘要
ABSTRACT
第一章 绪 论 ....................................................... 1
§1.1 研究的背景及意义 ........................................... 1
§1.1.1 六度空间理论 .......................................... 1
§1.1.2 P2P 网络拓扑 .......................................... 1
§1.1.3 研究的意义 ............................................ 2
§1.2 国内外研究现状 ............................................. 2
§1.2.1 P2P 网络拓扑 .......................................... 2
§1.2.2 P2P 信息定位技术 ...................................... 3
§1.3 本文的主要工作及结构 ....................................... 4
第二章 六度空间理论简介 ............................................ 5
§2.1 六度空间理论简介 ........................................... 5
§2.2 六度空间理论在社会学中的应用 ............................... 5
§2.3 六度空间理论在 P2P 网络中的应用 ............................. 6
§2.4 六度空间的特性 ............................................. 7
第三章 P2P 网络拓扑结构及其信息定位算法 .............................8
§3.1 P2P 网络拓扑结构 ............................................ 8
§3.1.1 中心化 P2P 网络拓扑 .................................... 9
§3.1.2 纯粹 P2P 网络拓扑 ..................................... 10
§3.1.3 混合 P2P 网络拓扑 ..................................... 11
§3.1.4 结构化 P2P 网络拓扑 ................................... 12
§3.2 P2P 信息定位算法 ........................................... 13
§3.2.1 非结构化 P2P 网络的信息定位算法 ....................... 13
§3.2.2 结构化 P2P 网络（DHT 网络）的信息定位算法 ............. 17
第四章 基于兴趣的 P2P 网络拓扑模型 ................................. 27
§4.1 P2P 网络拓扑模型兴趣特性的表现形式 ......................... 27
§4.2 建立基于兴趣的 P2P 网络拓扑模型的基本思路 .................. 27
§4.3 节点数据兴趣特征的描述 ..................................... 28
§4.4 基于兴趣的 P2P 网络拓扑初级模型的形成 ...................... 29
§4.4.1 使用 K-Means 方法生成兴趣簇 ........................... 29
§4.4.2 兴趣簇的节点层次结构 ................................. 30
§4.4.3 节点兴趣特征向量的修正 ............................... 31
§4.4.4 兴趣簇的维护 ......................................... 32
§4.5 基于兴趣的 P2P 网络拓扑初级模型的进化 ...................... 34
§4.5.1 兴趣组节点的功能 ..................................... 34
§4.5.2 兴趣组节点的兴趣特征向量表示 ......................... 36
§4.5.3 兴趣组节点的生成与管理 ............................... 36
§4.6 小结 ...................................................... 38
第五章 基于兴趣的 P2P 网络拓扑模型的信息定位算法 ................... 39
§5.1 查询信息定位算法 .......................................... 39
§5.1.1 拓扑模型节点层次结构 ................................. 39
§5.1.2 拓扑模型中节点的数据存储方式 ......................... 39
§5.1.3 基于模型的查询路由方式 ............................... 41
§5.1.4 算法性能分析 ......................................... 44
§5.2 拓扑模型信息定位算法的模拟实验 ............................. 45
§5.2.1 实验目的 ............................................. 45
§5.2.2 实验简介 ............................................. 45
§5.2.3 实验结果 ............................................. 47
§5.2.4 关键代码 ............................................. 49
§5.2.5 小结 ................................................. 52
第六章 结论及下一步工作 ........................................... 53
§6.1 本文研究结论 .............................................. 53
§6.2 进一步工作的展望 .......................................... 53
参考文献 ............................................................ 55
在读期间公开发表的论文和承担科研项目及取得成果 ......................57
致 谢 .............................................................. 58
第一章 绪论
1
第一章 绪 论
§1.1 研究的背景及意义
§1.1.1 六度空间理论
1967 年，哈佛大学的心理学教授 Stanley Milgram (1933～1984)创立了六度分割
理论（Six Degrees of Separation）[33]，简单地说：“你和任何一个陌生人之间所间
隔的人不会超过六个，也就是说，最多通过六个人你就能够认识任何一个陌生人。
这就是六度空间理论，也叫小世界理论。”
六度空间理论并不单纯地应用于传播交流上，其更大的价值在于其中的关系网
或者朋友圈的形成。一般来讲，每一个社会性网络（Social Networking : SN）都有
群组或者其它小群体的功能，这种圈子的形成其实也是一种人际关系密切化或者
兴趣化的一种表现。
举个例子，当你登录了某个空白的个人空间时，你首先需要做的就是去认识新
朋友。密切的关系及兴趣将不同的人聚集到一起，前者会产生差异化的交流，后
者则是差异化的聚合，说到底都是资源的整合，所以 Facebook 才推出了 Facebook
Ads 计划，即兴趣与差异化的广告投放系统。将这种人际关系转变成商业关系可以
说是任何一个 SNS 网站的梦想。这不仅需要用户的矛盾、联系、交流以及交际的
安全性和真实性形成群落效应，也需要它可以转移成为商业化效应。
§1.1.2 P2P 网络拓扑
在P2P 模型中，系统所有节点都是对等的，它们具有相同的责任，并且互相之
间协同以完成计算任务。目前，虽然基于 P2P 计算模式的 Napster，Freenet 和
Gnutella 等网络模型己被广泛地应用，但是它们也存在一些无法解决的问题[16]。集
中式(centralized)的Napster 利用中央服务器负责目录管理的服务会受限于服务器的
存在，即存在单点瓶颈和崩溃的问题；而非集中式(decentralized)系统，如 Gnutella
及Freenet，由于没有中央服务器，在搜寻数据时是以泛洪(flooding)的方式将消息
散布到网络中，这使得系统的可扩展性(scalability)无法提升。
结构化覆盖网路由协议，如 CAN，Chord，
Pastry 和Tapestry 就是在这种情况
下被提出来的。这些协议的共同点就是利用 DHT，将数据和节点映射成一个键值
(key)，利用键值来完成数据的放置与维护。这种方法不仅有效地减少了资源定位
基于覆盖网高效信息定位技术的探讨
2
中的消耗，也加快了数据定位的速度。结构化 P2P 系统成为国内外专家学者的研
究热点。
另外，由于结构化 P2P 系统在利用 DHT 构建其覆盖网络(overlay)时，没有过
多地考虑底层的物理拓扑结构，所以覆盖网络的寻径是建立在逻辑概念之上的，
即根据各节点保存的路由信息，选择一条逻辑跳数(hops)最少的路径作为最优路
径。这使得覆盖网络中逻辑最近的两个节点，在物理层往往并不是最近的，即一
条逻辑最近的路径有可能不是物理最近的路径。总之，寻径在逻辑层与物理层上
的性能差异，大大降低了结构化 P2P 系统中资源定位的效率。
§1.1.3 研究的意义
通过上两节的分析和讨论，我们可以看出，六度空间和 P2P 网络是有很多共性
的。
1）“六度空间”理论和 P2P 网络拥有相似的“软硬件”基础，即人类社会中的
人似于 P2P 网络中的节点，而人与人之间的查找过程类似于 P2P 网络中的路由过
程，因此六度空间特性可以启发我们建立基于兴趣的 P2P 查询网络拓扑结构。
2）人类社会团体主要通过“兴趣”和“共同特性”构成，而这种性质已经在
P2P 网络中得到了广泛的使用，即根据兴趣点形成的聚簇关系。
由于 P2P 网络和人类社会网络有很多的相似之处，所以如果把六度空间理论的
一些特性应用到 P2P 网络拓扑结构中，那么将有可能会改善 P2P 网络信息定位的
效率，这也是本论文的目的。
§1.2 国内外研究现状
P2P 计算已成为当今科学研究和产品开发的热点，它们可以大致的分成 4大
类，即内容共享(Content sharing)、分布式计算(Distributed computing)、通信与协作
(Communication and Collaboration) 和P2P 系统平台(Platform)的设计[4]；而六度空
间理论则主要应用于 Google、天网等集中式搜索引擎和一些社会学研究领域当中。
下面主要介绍与本题目相关技术的发展现状。
§1.2.1 P2P 网络拓扑
P2P 信息共享技术是一种用于不同 PC 用户间、不经过中继设备直接交换数据
或服务的技术,它允许网络用户直接使用对方的文件,消除了中间环节,使内容从
“中心”走向“边缘”,从而避免了 C/S 结构固有的性能瓶颈，使位于网络边缘
摘要：
展开>>
收起<<
摘要在现实世界中“任何一个陌生人之间所间隔的人不会超过六个”，这就是六度空间理论所阐述的内容。这不仅是说人与人可以经过六个或更少个层次的中转就能产生联系，也意味着人与周围环境是存在密切联系的，不是一个独立的存在。与人类社会类似，P2P网络中的节点也不是孤立的点，它们能通过各种方式的路由进行信息交互。所不同的是，前者是利用兴趣、爱好或者共同特征聚合而成，查找过程快速而简便；后者在逻辑结构上和物理结构上往往不相匹配，而且其查找过程是按照协议进行有规律的查询，不能根据环境的不同而进行优化。考虑到两种网络的相似性，如果能把六度空间理论应用到P2P网络中，那么将有可能会改善P2P网络的性能。论文为了验证...
相关推荐
-
我国基层财政困难的制度成因分析与对策研究VIP免费
2024-09-20 54 -
我国煤电产业链纵向交易合约机制研究VIP免费
2024-09-20 53 -
生产要素视角下的上海市产业结构优化研究VIP免费
2025-01-09 11 -
我国银行业结构与经济结构关系研究VIP免费
2025-01-09 22 -
大数据视角下农业供应链金融研究VIP免费
2025-01-09 18 -
跨国大型综合超市的规划研究VIP免费
2025-01-09 12 -
跨境电商农产品质量安全问题研究VIP免费
2025-01-09 13 -
世界市场的虚拟化与我国国际电子商务发展方向研究VIP免费
2025-01-09 78 -
中国政府对电力行业的价格规制问题研究VIP免费
2025-01-09 45 -
中小企业信息化系统集成技术研究VIP免费
2025-01-09 40
作者：牛悦
分类：高等教育资料
价格：15积分
属性：61 页
大小：1.72MB
格式：PDF
时间：2024-11-19
相关内容
-
跨国大型综合超市的规划研究
分类：高等教育资料
时间：2025-01-09
标签：无
格式：PDF
价格：15 积分
-
跨境电商农产品质量安全问题研究
分类：高等教育资料
时间：2025-01-09
标签：无
格式：PDF
价格：15 积分
-
世界市场的虚拟化与我国国际电子商务发展方向研究
分类：高等教育资料
时间：2025-01-09
标签：无
格式：PDF
价格：15 积分
-
中国政府对电力行业的价格规制问题研究
分类：高等教育资料
时间：2025-01-09
标签：无
格式：PDF
价格：15 积分
-
中小企业信息化系统集成技术研究
分类：高等教育资料
时间：2025-01-09
标签：无
格式：PDF
价格：15 积分
