基于覆盖网高效信息定位的技术探讨

VIP免费

3.0 牛悦 2024-11-19 7 4 1.72MB 61 页 15积分

侵权投诉

摘要

在现实世界中“任何一个陌生人之间所间隔的人不会超过六个” ，这就是六

度空间理论所阐述的内容。这不仅是说人与人可以经过六个或更少个层次的中转

就能产生联系，也意味着人与周围环境是存在密切联系的，不是一个独立的存在。

与人类社会类似，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 六度空间理论

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)，利用键值来完成数据的放置与维护。这种方法不仅有效地减少了资源定位

基于覆盖网高效信息定位技术的探讨

中的消耗，也加快了数据定位的速度。结构化 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 结构固有的性能瓶颈，使位于网络边缘

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

15 积分 4人已下载

立即下载 VIP免费下载

摘要：

摘要在现实世界中“任何一个陌生人之间所间隔的人不会超过六个”，这就是六度空间理论所阐述的内容。这不仅是说人与人可以经过六个或更少个层次的中转就能产生联系，也意味着人与周围环境是存在密切联系的，不是一个独立的存在。与人类社会类似，P2P网络中的节点也不是孤立的点，它们能通过各种方式的路由进行信息交互。所不同的是，前者是利用兴趣、爱好或者共同特征聚合而成，查找过程快速而简便；后者在逻辑结构上和物理结构上往往不相匹配，而且其查找过程是按照协议进行有规律的查询，不能根据环境的不同而进行优化。考虑到两种网络的相似性，如果能把六度空间理论应用到P2P网络中，那么将有可能会改善P2P网络的性能。论文为了验证...

展开>> 收起<<

基于覆盖网高效信息定位的技术探讨.pdf

共61页,预览7页

还剩页未读，继续阅读

基于覆盖网高效信息定位的技术探讨

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: