（计算机应用技术专业论文）对等网络中的查询搜索机制与信任模型研究.pdf

中文摘要对等计算( p e e r - t 0 - p e e rc o m p u t i n g ，简称p 2 p ) 是分布式系统和计算机网络相结合的产物，打破了网络应用层过去的“客户服务器”模式，使系统中节点以自由平等的方式进行互联。p 2 p 网络从拓扑结构角度分为结构化拓扑和非结构化拓扑。结构化拓扑网络采用分布式哈希表( d h t ) 进行资源搜索，网络易扩展、查询效率高，但不支持基于内容的复杂查询。非结构化拓扑网络采用洪泛法进行资源搜索，支持多样化的查询，网络的拓扑结构简单，但查询效率低，数据无法准确定位。此外，p 2 p 网络中节点的动态性和匿名性，使得系统无法保证所有节点都提供良好的服务和可靠的资源。为了应对这些问题，本文深入研究了p 2 p系统中的拓扑构造和资源搜索机制，以及节点的信任管理机制，取得了以下成果：1 针对结构化p 2 p 网络缺乏基于内容的查询机制，提出基于语义的分组p 2 p网络。该网络采用向量空间模型( v s m ) 归纳节点共享资源的语义信息，使具有相似语义的节点形成语义分组。各个分组内采用非结构化拓扑网络，同时在分组内选择能力较强的节点成为组内超级节点，超级节点之间构成了结构化拓扑网络。仿真实验表明这种结构降低了资源的查询开销，有效的支持在动态p 2 p 系统中进行基于内容的检索。2 针对非结构化p 2 p 网络中的洪泛搜索机制，本文结合“小世界”模型，按照社会关系网络中“物以类聚，人以群分”的原理提出一种非结构化p 2 p 网络。网络中具有相似语义的节点聚类，使得网络具有较高的聚类系数和较小的平均路径长度，提高了网络的查询效率。3 由于p 2 p 系统中节点的动态性和匿名性，系统对节点的行为缺乏有效的监管，在系统内建立信任模型是解决此问题比较可行的机制。本文结合基于语义的分组p 2 p 网络提出了基于分组的信任模型。由于网络中的超级节点的在线时间长、计算能力强，因此在结构化层采用了全局信任模型，而在分组内部采用局部信任模型。仿真实验表明这种信任模型能够较好抵御网络中恶意节点的攻击，有一定的有效性和健壮性。关键词：对等计算，资源检索，聚类，小世界，信任模型a b s t r a c tp e e r - t 0 - p e e rc o m p u t i n g ( p 2 p ) i st h ec o m b i n a t i o no fd i s t r i b u t c ds y s t c m 锄dc o m p u t e rn e t w o r k s r a t h e rt h 锄t 1 1 e c l i e n t s e n ，e r ，m o d e ，n o d e si nt l l es y s t e 】【nc o r u l e c tw i t he a c ho m e ri na 毹e 柚de q u a lw a y t h i sm o d e lo fn e t 、) l ，o r ka r r a n g e m e n tb r e a k su pt t l et r a d i t i o n a l “c l i e n t s e r v e r m o d e la tn e t 、0 r k 印p l i c a t i o nl a y e r f r o m l et o p o l o g ) ，v i e w ，p 2 ps y s t e l nc a nb ec l a s s i f i e da ss t m c t u r e dt o p o l o g ya n du n s t i u c t u r e dt o p o l o g y s t m c 呲e d 白d p o l o g yp 2 pn 咖o r ka d o p t sd i s t r i b u t e dh a s ht a b l e ( d h t ) t 0l o c a t er e s o u r c e s u c hn e t 、 ，o r kc a nb ee a s i l ye x p 粕d e d 锄dt h ee f f i c i e n c yo fq u e 叫i n gr e s o u r c ei sr e l a t i v eh i g h b u tq u e 巧b a s e do nc o n t e n ti sn o ts u p p o r t u n s t r u c t u r e dt o p o l o 科p 2 pn e t 、】l ，o r ka d o p t sf 1 0 0 d i n gw a yt 0q u e 哆r e s o u r c e s u c hn e 觚o r ks u p p o r tc o m p l e xq u e r y 锄dh a sas i m p l et o p o l o g y b u te m c i e n c yo fq u e 巧i sr e l a t i v el o w 锄dd a _ t am a yn o tb el o c a t e da c c u r a t e l y b e s i d e s ，g o o ds e n ，i c e 锄dr e l i a b l cr e s o u r c ec 粕n o tb eg u a r a n t e e df o re v e 巧n o d ei i lt h es y s t e mb e c a u s eo ft h ed y n a m i c 锄d 跏o n y m i 够o fn o d e s w i u lt h e s ep r o b l e m s ，ad e e ps t u d yo fp 2 ps y s t e mt o p o l o g yc o n 鼬m c t i o n ，r c s o u r c e sq u e 拶m e c h a n i s m ，a sw e l l 嬲n o d e st 兀j s tm a n a g e m e n ti si n 臼d d u c e di nt i l i sa n i c l e ，粕dh a sy i e l d e dt h ef o l l o w i n gr e s u l t s 1 c o n s i d e r i n gt h a ts 仉l c t u r e dp 2 pn e t 、o r ki sl a c ko fc o n t e n t - b a s e dq u e t h i sp 印e rp r o p o s e sg r o u p e dp 2 pn e t w o r kb a s e do ns e m a n t i c t h i sn e 锕o r ka d o p t sv e c t o rs p a c em o d e l ( v s m ) t 0s u m m a r i z et i l es e m 锄t i ci n f o r n l a t i o no fs h a r e dr e s o u r c eb e 铆e e nn o d e s n l e nn o d e sw i t hs i m i l a rs e m a n t i cc 锄b eg r o u p e d i ne a c hg r o u p ，u n 蚰r u c t u r e dn e t w o r ki sa d o p t c d a tt h es 锄et i m ei nag r o u pn o d e sw i t h 铲e a t e ra b i l i 哆a r es e l e c t e da ss u p e rn o d e sa n ds u p e rn o d e sf o m l e ds 仃i j c t u r e dn e t w o f k t h es 肌u l a t i o ns h o w st h a ts u c hs 臼1 l c t u r eo fn e 俩o r kr e d u c e st h ec o s to fr e s o u r c eq u e 彤跏dp r o v i d e se 腩c t i v es u p p o r tf o rc o n t e n t - b a s e dq u e r y 2 c o m b i n i n gw i t ht h ef l o o d i n gs e a r c hm e c h a n i s mo fu ns t r u c t u r e dp 2 pn e t w o r kt h i sp a p e ri n t r o d u c e san o v e lu n s t m c t u r c dp 2 pn e t 、 ，o r kb a s e d0 ns m a l l - w o r l dt h e o 阱t h i su n s 仇l c m r e dp 2 ps y 咖mi sd e s i g n e di na c c o r d 粕c ew i t ht h e 两n c i p l e ”b 砌so faf e a t h e rn o c kt o g e t h e r t i ns o c i a ln e 觚o r k s ，s u c hu n s t r u c t u r e dp 2 ps y s t e mm a k e sn o d e sw i t hs i m i l a rs e m a l l t i cc l u s t e 】r e d ，s 0t h a tt h en e t w o r kh a sah i g hc l u s t e r i n gc o e 伍c i e n ta n ds m a l l e ra v e r a g ep a ml e n g m ，s i g n i f i c a n t i yi m p r 0 v i n gt i l ee m c i e n c yo fl en e t w o r kq u e 巧3 i np 2 pn e t w o 呔s y s t e m ，髓n o d e sa r ed y n 锄i c 锄d 锄o n y m o u s ，t h es y s t e ml a c l ( se 虢c t i v es u p e r v i s i n ga n dm a n a g i n gt 0n o d e s b e h a v i o r e s t a b l i s h i n gt m s tm o d e li nt h es y s t e mi saf e a s i b l es o l u t i o n i nv i e wo ft h es e m a n t i c 轳o u p e dp 2 pn e t w o f kt h i sp 印e rp r o p o s e sg r o u pb a s e d 仃u s tm o d e l i ng r o u p e dp 2 pn 咖。如s u p e rn o d e sh a v em o r eo n l i n et i m ea n dp o w e r f u lc o m p u t i n ga b i l i 吼s 0g l o b a lt r u s tm o d e li su s e di nt l l e鲫r u c t u r e dl a y e r ，a n di o c a l 仃u s tm o d e ii su s e di n s i d eg r o u p s e x p e r i m e n t ss h o wt h a tt h i s 仃u s tm o d e lc 锄r e s i s ta t t a c i ( s 舶mm a l i c i o u sn o d e sa n dh a sg o o de 仃e c t i v e n e s sa n dr o b u s t l l e s s k e yw o i m s ：p e e r - t o p e e rc o m p u t i n g ，i n f o m l a t i o nr e 仃i e v a l ，c l u s t e r i n g ，s m a l lw b r l d t l m s tm o d e l独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得丞鲞盘堂或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。一虢疆叠：m 夕年岁月夕日学位论文版权使用授权书本学位论文作者完全了解丞壅盘堂有关保留、使用学位论文的规定。特授权鑫鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。( 保密的学位论文在解密后适用本授权说明)学位论文作糍：乃踊导：签字日期：刁匙楣汨；日签字日期：凯7 年；月7 日j，l天津大学博士学位论文第一章绪论计算机网络是2 0 世纪人类最伟大的发明之一，它的出现改变了人类几千年来对信息存储、表示、处理的方式，也极大的影响了人类生活与思考的方式。随着计算机网络技术的发展，网络的计算模式也正在从客户服务器( c l i e 叫s e r v e r )模式发展到了对等计算( p e e 卜t o p e e r ，简称p 2 p ) 模式【l 】。对等计算模式的本质思想在于打破网络中传统的客户服务器模式，让一切网络成员享有自由、平等、互联的功能，不再有客户、服务器之分；网络中的每个节点既向其他节点提供服务，也享受来自其他节点的服务。p 2 p 网络中的资源存放在网络中的各个节点上，不像传统的客户服务器模式中的网络资源是集中保存在服务器上。随着p 2 p 网络规模的不断扩大，网络用户的数量激增，p 2 p 网络中的共享资源的数量也迅速增加。如何在海量的共享资源中准确的定位资源就成为影响p 2 p 网络发展的重要因素，因此研究p 2 p 网络中的资源搜索机制，提高p 2 p 网络的资源定位性能，成为p 2 p 网络的一个重要研究课题。同时，由于p 2 p 网络的匿名性，使得用户在网络中的行为很难受到控制。如何保证网络能够正常稳定的运行，减少恶意用户对网络的负面影响即建立p 2 p 网络中的信任模型问题，也成为p 2 p 网络的一个重要研究课题。本章以下的部分说明了本文的选题背景及研究意义，介绍了p 2 p 网络的一些基本概念和目前p 2 p 网络环境下资源检索机制和安全问题的研究现状，阐述了本文的主要目标以及取得的主要研究成果。1 1 选题背景1 1 1 社会经济和技术背景计算机网络自产生以来，网络中的管理和控制模式始终存在两种不同的方式：集中式和分布式。在计算机网络中因特网( i n t e m e t ) 是发展最迅猛的，成为世界上最大的广域网络，连接了地球上几乎每个角落的计算机，在因特网的发展过程中客户服务器模式是最传统、最成熟的集中式的工作模式，例如因特网中的多种应用协议h t t p 、f t p 、s m t p 等均采用了这种工作模式，这种工作模式在因特网的初期工作得非常好；然而随着计算机的性能、网络传输的设施以及其它相关资源以类似摩尔定律的方式增长，即计算速度每1 8 个月翻一番，网络速第一章绪论度每9 个月翻一番，差不多每5 年上一个数量级 2 】，使得因特网在规模上不断膨胀，网络用户数量激增，导致了网络中的服务器负载过重。这种情况下客户服务器模式的低效率和难以扩展的缺陷充分地暴露出来，这种工作模式越来越难以满足客户的服务请求，形成了网络中的服务器瓶颈。与此相反，随着网络规模的不断膨胀，网络中的个人计算机的性能也在不断提高，甚至超过了传统小型服务器的计算能力。在客户服务器模式下网络中的个人计算机只能处于客户模式，导致了大量个人计算机无法在网络中充分发挥其计算能力，造成资源浪费。这里我们做一个简单的计算，假设因特网中同时有1 千万台计算机连接在计算机网络上，每台计算机的c p u 频率为l g h z ，有1 的c p u 时间是空闲的，每台计算机上有1 0 m b 的空闲空间，则这些计算机总共可以提供1 0 4 g h z 的计算能力和1 0 0 t b 的存储空间，这相当于网络中有l 万台计算机没有工作，完全空闲，浪费了巨大的资源。在传统的客户服务器模式中远远未能充分利用计算机网络系统中的信息、带宽和计算资源【3 】，因此亟待研究出一种新型的计算模式，以高效地利用网络中所存在的各种资源，有效地满足网络用户的各种需求。由此，采用新型计算模式的对等计算系统( p e e r - t o p e e r ) 产生了。1 1 2 对等系统的定义p 2 p 并不是一个新的概念，在p 2 p 网络诞生之前，电信领域和一些游戏软件中已经有了p 2 p 的工作模式，即作为c l i e 州s e r v e r 的一种替代方式，在系统中没有中心服务器的概念，各个节点( p e e r ) 的地位是平等的，节点之间可以任意交换资源。一种高度概括的c s 与p 2 p 的结构比较如图1 1 所示 4 】。( a ) c s 结构( b ) p 2 p 结构图1 1c s 与p 2 p 结构比较天津大学博士学位论文图1 1 中的p 2 p 结构是种简单的模型。目前p 2 p 系统正处于不断发展的阶段，因而并不存在一个精确的定义。当前给出的许多定义都是试图反映p 2 p 系统发展过程中的某个阶段的新特征。下面是一些p 2 p 系统的相关研究者给出的定义。1 国际p 2 p 工作组的定义 5 】：p 2 p 就是通过在系统之间直接交换来共享计算机资源和服务。这些资源和服务包括信息交换、高速缓存、处理能力、存储空间。p 2 p 可以整合这些经济的p c 机上计算力和网络连接，从而提供企业级的计算平台。2 s c h o l l m e i e r 对p 2 p 系统的定义如下【6 】：如果一个系统的参与者共享了自己的硬件资源，这些共享的资源是系统提供服务必需的，且可以被其它参与者不用通过中介而直接访问；系统的参与者既是资源的提供者也是资源的请求者，则此系统可以认为是p 2 p 系统。3 c l a ys h i r k e y ：p 2 p 是一种利用位于i n t e n l e t 边缘的各种可用资源( 如存储空间、计算能力、媒体内容) 的应用【7 】。访问这些分散的资源，就意味着要在连接不稳定和i p 地址不可预见的环境里工作。由于网络上大量的节点工作在d i n s 系统之外，这些分散的资源具有不稳定的连通性和未知的i p 地址。因此，p 2 p 节点必须能够独立于d n s 系统且高度自治。4 a b e r e r 通过描述p 2 p 系统的特征来定义p 2 p 系统。这些特征如下 8 】：没有集中的协调中心；不存在集中的数据库；p 2 p 系统中的节点没有整个系统的全局视图；全局的行为依靠局部的相互作用；所有存在的数据和服务都是可访问的；p 2 p 节点是自治的；p 2 p 系统中的节点及其相互之间的连接都是不可靠的。由于p 2 p 系统采用了一种新型的计算模式，而且正在不断地发展变化，所以目前学术界仍然没有给出一个权威的定义，一般地说，p 2 p 是一个用于资源共享的节点的集合，其中每个节点向系统内的其它节点提供资源，同时作为回报从系统的其它节点中获取所需资源。构建这类系统的主要思想是：世界上的一切事物都是广泛分布且相互联系的，不可能通过一种集中化的方式管理如此庞大的结构。p 2 p 通过分布于世界各地的个人计算机管理大量的计算能力、存储空间和连接。p 2 p 中的每个节点自治又彼此依赖，所谓自治是指系统中的每个节点独立决定自己的行为而不受其它因素( 例如：集中式授权机构) 的控制，同时每个节点又需要相互协作获得所需的信息资源、计算资源。1 1 3 对等网络的特点对等网络的特点集中体现在以下几个方面【9 】【1 0 】：1 非中心化( d e c e n 帆l i z a t i o n ) ：网络中的资源和服务分散在所有结点上，第一章绪论信息的传输和服务的实现都直接在结点之间进行，可以无需中间环节和服务器的介入，避免了可能出现的瓶颈。p 2 p 的非中心化这个基本特点，带来了其在可扩展性、健壮性等方面的优势。2 可扩展性：在p 2 p 网络中，随着用户的加入，不仅服务的需求急剧增加，系统整体的资源和服务能力也在同步地扩充，始终能比较容易地满足用户的需要。理论上其可扩展性可以认为几乎是无限的。例如：在传统的通过f t p 的文件下载方式中，当下载用户增加之后，下载速度会变得越来越慢，然而p 2 p 网络正好相反，加入的用户越多，p 2 p 网络中提供的资源就越多，下载的速度反而越快。3 健壮性：p 2 p 架构天生具有耐攻击、高容错的优点。由于服务是分散在各个节点之间进行的，部分节点或网络遭到破坏对其他部分的影响很小。p 2 p 网络在部分节点失效时能够自动调整整体拓扑，保持节点的连通性。p 2 p 网络通常都是以自组织的方式建立起来的，并允许节点自由地加入和离开。p 2 p 网络还能够根据网络带宽、节点数、负载等变化不断地做自适应的调整。4 高性价比：性能优势是p 2 p 被广泛关注的一个重要原因。随着硬件技术的发展，个人计算机的计算能力和存储能力以及网络带宽等性能依照摩尔定律高速增长。采用p 2 p 架构可以有效地利用互联网中分布的大量普通节点，将计算任务或存储资料分布到所有节点上。利用其中闲置的计算能力或存储空间，达到高性能计算和海量存储的目的。通过利用网络中的大量空闲资源，可以用更低的成本提供更高的计算和存储能力。5 隐私保护：在p 2 p 网络中，由于信息的传输分散在各节点之间进行而不必经过某个集中环节，用户的隐私信息被窃听和泄漏的可能性会大大缩小。此外：目前解决i n t e m e t 隐私问题主要采用中继转发的技术方法，从而将通信的参与者隐藏在众多的网络实体之中。在传统的一些匿名通信系统中，实现这一机制依赖于某些中继服务器节点，而p 2 p 中所有参与者都可以提供中继转发的功能，因而大大提高了匿名通讯的灵活性和可靠性，能够为用户提供更好的隐私保护。6 负载均衡：p 2 p 网络环境下由于每个节点既是服务器又是客户机，减少了对传统c s 结构服务器计算能力、存储能力的要求；同时因为资源分布在多个节点，更好地实现了整个网络的负载均衡。1 1 4 对等网络的应用随着对等计算技术的发展，对等网络的应用范围越来越广泛，因此p 2 p 系统在文件共享、多媒体传输、实时通信、分布式计算、分布式数据存储等多个领域得到了广泛的应用和研究，开辟了互联网络应用的新时代。天津大学博士学位论文1 文件共享在基于客户服务器模式的文件共享系统中，每个需要共享文件的计算机必须先把文件上载到集中的服务器上，而需要获取文件的计算机必须到服务器上下载所需的文件，这样才能实现个人计算机之间的文件共享，例如现有互联网络中的f t p 文件传输协议，其工作模式就是这种方式。基于客户服务器的这种工作模式不仅浪费了大量的服务器资源，而且存在单点失效问题。利用p 2 p 系统进行数据文件共享，可以让个人计算机用户之间不通过中心服务器而直接共享各种文件，用户直接到共享文件的计算机上去下载文件，这样不仅节约了资源，还提高了系统的鲁棒性。出现于1 9 9 9 年的世界上的第一个应用性对等网络n 印s t e r 【ll 】就是一个文件共享系统，它提供服务允许音乐迷们交流m p 3 文件。在n a p s t c r发布后的半年内就拥有了5 0 0 0 万用户，最高时超过6 1 0 0 万用户，这在计算机网络领域是一个从未有过的奇迹。此后g n u t e l l a 【1 2 】，i m e s h 1 3 】，k a z a a 1 4 】，e d o i l l ( e y 1 5 】，f r e e n e t 1 6 】，b i t t 0 r r c n t 【1 7 】等p 2 p 文件共享系统不断涌现。用户数量的持续增长和应用的迫切需求使得文件共享成为当前p 2 p 系统中最主流的应用。2 多媒体传输自多媒体技术产生以来，多媒体文件( 音频、视频等) 就一直在寻找一个合适的网络传输载体，但由于多媒体具有传输实时性要求高、带宽资源消耗大和传输过程持续长等特点，若采用传统的客户服务器模式会导致较大的i o 负载压力、可扩展性差和系统部署成本高等问题。并且在多用户并发的服务请求条件下，基于客户服务器模式的多媒体传输系统所提供的服务质量难以得到保证。p 2 p系统真正适应了多媒体传输对网络带宽的巨量需求，因为所需要的巨大带宽被所有共享多媒体文件的用户分散承担，当用户数量增加时传输质量通常是变好而不是变坏。目前互联网络中的语音传输工具s k y p e 【l8 】就是一个多媒体传输的典型应用，s k y p e 最诱人的应用在于可以使用s k y p e o u t 实现p c 2 p h o n e 的功能( 即网上拨打座机电话) ，价格低廉而且音效很好，属于v o i p ( v o i c eo fi p ，i p 语音电话) 。s k y p e 网络电话服务的开通，对全球网络、电信领域造成很大的冲击。类似的应用还有p p l i v e 【1 9 】，t v a n t s 【2 0 】，a m y s e e 2 1 】等用于互联网上大规模视频直播的p 2 p 多媒体传输软件。3 实时通信实时通信就是即时消息传递，不同的用户通过网络( 一般是i n t e m c t ) 相互递送消息进行对话。这与同一台主机不同终端用户之间的消息传递是不同的，因为消息的传递是在两台不同的计算机之间进行的，这两台计算机甚至可能拥有不同的体系结构、运行不同的操作系统。除了简单的文字消息传递以外，这些即时消息第一章绪论传递软件一般还提供多方文字会议、文件共享、即时音频对话甚至即时图像传输功能。在著名的实时通信软件中，i c q 曾经是下载量最大的共享软件。除此之外，还包括y 曲o o ! m e s s e n g e r 、m s nm e s s e n g e r 等。目前，国内最流行的实时通信软件就是腾讯公司的q q ，自1 9 9 9 年第一个q q 测试版推出之后，q q 用户迅猛增长，最高在线人数以每年超过1 0 0 万人数的速度增长。4 分布式计算在互联网中的许多计算机的c p u 资源并不是时刻保持峰值运转的，甚至很多时候计算机处于“空闲状态，比如使用者暂时离开或正在运行简单应用程序等情况。而p 2 p 技术可以连接上百万台或更大规模的计算机，有效地利用这些计算机的空闲计算资源进行协同工作，服务于一个共同的计算。这种计算一般是计算量巨大、数据极多、耗时很长的科学计算。在每次计算过程中，任务( 包括逻辑与数据等) 被划分成多个片，被分配到参与科学计算的p 2 p 节点机器上。在不影响原有计算机使用的前提下，人们利用分散的c p u 资源完成计算任务，并将结果返回给一个或多个服务器，将众多结果进行整合，以得到最终结果。世界最著名的p 2 p 分布式科学计算系统是由美国加利福尼亚大学伯克利分校在1 9 9 9 年发起“s e t l h o m e 【2 2 】，也是至今最成功的分布式计算项目。s e t l h o m e 通过分析从射电望远镜传来的数据来搜寻地外文明，这在不少科幻迷以及普通大众眼里都是一个“很酷”的应用。s e t i 的早期版本截至2 0 0 5 年已经吸引了5 4 3 万用户，分析了大量积压数据。正如宇宙的浩瀚一般，需要计算的数据( 即存在宇宙空间的无数无线电信号) 也是海量的。可以说，这几百万台终端组成了一个目前最快的高性能计算机都望尘莫及的“超级计算机 。2 0 0 0 年斯坦福大学开发的f o l d i n g h o m e 2 3 】项目致力于研究蛋白质折叠、误折、聚合及由此引起的相关疾病，到目前己经吸引了4 0 0 ，0 0 0 个用户加入。2 0 0 3 年o l s o n 实验室主持的研究艾滋病的项目f i g h t a i d s h o m e 2 4 也吸引到了9 ，0 2 0 个用户。5 分布式数据存储p 2 p 分布式存储系统( 文件共享与下载) 是一个用于对等网络的数据存储系统，它可以提供高效率的、鲁棒的和负载平衡的文件存取功能。对于存储系统，用户关心数据的定位、搜索以及路由的效率，安全性也是重要的因素。集中方式在很多情况下不再适用这种大规模数据存储的要求，这就需要一个新的体系来管理系统中的数据。p 2 p 分布式存储系统就是解决这样的问题。伯克利大学开发的分布式海量存储系统o c e 锄s t o r e 2 5 】采用t a p e 唧 2 6 】技术，提供了全球范围内的一致性数据存储。m i t 研究的c f s 项目采用c h o r d 【2 7 】技术，提供了一致性的分布协同文件存储。砌c e 大学和微软公司联合研究的p a s t 项目采用p a s 仃y 【2 8 】技术，提供了大规模的、可扩展的、协同的分布文件存储服务。天津大学博士学位论文1 2p 2 p 网络的分类现有的p 2 p 系统种类繁多，研究人员从不同的角度对p 2 p 系统进行了分类 2 9 】 3 0 】。本文依据文献 2 9 】选取网络的拓扑结构作为p 2 p 系统的分类标准，我们认为这种分类比较好的反映了p 2 p 系统的本质特征，如图1 2 所示。根据p 2 p覆盖网络的组成方式的不同，可以将p 2 p 系统分为非结构化网络和结构化网络两类。非集中式( 肌那刎结全分布式非结构化构g n t l t e l l n 、e e n e f化p 2 p混合式僻砸删)系统结构i化| ( c j l l d 磁c 州却嚣嗍图1 2p 2 p 系统的分类1 2 1 非结构化拓扑( u n s 仃1 l c t u r e d )系统中的节点与多个节点之间存在着随机连接，形成随机网络，具有随机网络直径较小的特点。节点间的逻辑拓扑关系通常较为松散，资源( 或资源元信息)放置通常与p 2 p 系统的拓扑结构无关，一般只放置在本地。资源的搜索依靠洪泛算法来实现，使得网络的开销较大。但是，非结构化拓扑的实现和维护相对简单，可较好地支持复杂资源搜索。这些特点使得非结构化拓扑在i n t e m e t 上得到了广泛的应用。在非结构化拓扑中又分为集中式、全分布式非结构化和混合式三种类型。1 集中式p 2 p 系统：在该类系统中，存在着一个和多个目录服务器。用户将自己拥有的资源索引发布到目录服务器上，并通过目录服务器搜寻自己需要的资源，然后再由各个节点直接交换数据。该类型系统包括n a p s t e r 1 1 、b i t t 0 盯e n t 1 7 】等。该类系统的优点在于搜索的高效性和完整性，用户只需要一步第一章绪论就可以查询到自己需要的所有资源；但是该类系统也面临着单点失效、版权、系统安全等方面的挑战。2 全分布式非结构化p 2 p 系统：该类系统中，没有服务器和普通节点之分，每个节点都具有相同的权利和义务。该类型包括g n u t e l l a 【1 2 】、f r e e n e t 【1 6 】等。该类型系统体现了“人人为我，我为人人的思想，系统中的每个节点既是服务器也是客户端。该类系统的优点是系统中没有性能瓶颈，系统拥有较强的伸缩性，可以随节点规模而变化。但是该类系统在容错性、节点异构性、安全性的方面需要做大量的工作。3 混合式p 2 p 系统：在该类型系统中，存在着一些“超级节点”，例如k a z 啦【1 4 】。这些节点由p 2 p 系统按照某种规则从网络中选择出来，并充当了目录服务器的角色。这些超级节点往往拥有较强的处理能力、高带宽和较长的在线时间，使系统在查询性能、容错性、伸缩性等方面表现出较好的能力。1 2 2 结构化拓扑( c t u r e d )系统中的节点按照某种算法组织起来，形成具有某种拓扑结构的网络。节点间的逻辑拓扑关系通常由确定性的算法严格控制，资源( 或资源的元信息) 的放置也是由确定性的算法精确发布到特定的节点上。结构化拓扑p 2 p 系统通常采用分布哈希表技术( d i s 仃i b u t e dh a s ht a b l e ，d h t ) 构建，它提供了与哈希表类似的两个抽象操作：p u b l i s h ( k e y ) 和l o o k u p ( k e y ) 。p u b l i s h ( k c y ) 将资源对象根据其关键字k e y 发布到p 2 p 系统中的节点上，l o o k u p ( 1 ( e y ) 则根据关键字k e y 在p 2 p 系统中搜索资源对象。结构化拓扑的优点是资源定位准确并且可保证一定的效率，具有良好的可扩展性和性能，适用于对可用性要求高的系统。但结构化拓扑的维护相对复杂，当一个节点非正常离开系统时，需要o ( 1 0 9 n ) 步来纠正系统的错误。此外结构化p 2 p 系统通常只支持精确匹配资源定位，对复杂条件的资源定位能力较弱。1 3 问题的提出1 3 1 研究现状p 2 p 的思想起源很早，最早提及p 2 p 的文献发表于1 9 5 6 年，从那以后几乎每年都有与p 2 p 相关的文章，但一直未成为学术界的研究热点。直至1 9 9 9 年第一个应用性的对等网络n 印s t c r 【1 1 】出现，它创造了在半年时间里就拥有了超过5 0 0 0 万用户的一个奇迹，向整个世界展示了p 2 p 系统的优异性能和巨大潜力。天津大学博士学位论文自此，许多国内外著名的研究机构如：u cb e r k e i e y 、m i t 、s t a n d f o r d 、c m u 、m i c r o s o f t 、i n t e l 、s u n 、h p 等都对p 2 p 系统的研究投入了大量的精力，并且提出了很多著名的p 2 p 系统的模型，如c h o r d 2 7 】、c a n 【3 1 】、p a s t 叮【2 8 】、t a p e s t 巧 2 6 】等。在这些网络模型的基础上，开发了如文件共享、分布式数据存储等应用系统。我国对p 2 p 研究起步较晚，但近几年有很大的进展，例如北京大学网络实验室开发了m a z e 系统，主要应用于文件共享；清华大学开发的g h n a 巧【3 2 】分布式存储系统；华中理工大学开发的视频直播软件a i l y s e e 【2 1 】。虽然研究者在p 2 p 领域提出了多种模型，但文件共享系统依然是当前p 2 p系统中最主流的应用。1 9 9 9 年开发的n a p s t e r 系统，在顶峰时期达到过6 0 0 0 ，0 0 0 用户。2 0 0 5 年2 月1 9 日，k a z a a 文件共享系统软件下载累计达到3 8 4 ，1 9 1 ，3 3 4 次【3 3 】。中国互联网络信息中心( c n n l c ) 2 0 0 6 年发布的统计报告显示，互联网中2 7 8 的用户使用b t 软件。美国m u l t i m e d i ai n t e l l i g e n c e 市场调查机构于2 0 0 8 年1 0 月出具的一份调查报告显示美国互联网中的6 1 0 8 的流量为p 2 p 用户下载文件所产生的，并且估计在今后5 年中这个流量将比现在增加4 0 0 。从这些数据可以看出，在互联网络中基于p 2 p 技术的文件共享系统规模在以惊人的速度增长。因此本文选择结构化p 2 p 文件共享系统和非结构化p 2 p 文件共享系统为研究对象，重点研究p 2 p 系统中的资源搜索机制和信誉管理问题。1 3 2 资源搜索机制问题基于p 2 p 技术的文件共享系统是到目前为止是参与用户最多也是最为引人注目的p 2 p 应用。在基于p 2 p 技术的文件共享系统中，共享资源不采用集中式存放，系统内的共享资源是分布在系统中的各个节点之上的。当系统中的一个用户想要在系统内获取资源，首先必须在系统内查询资源的存放位置，找到资源的存放位置后在与存放该资源的节点联系并下载资源。因此，在p 2 p 文件共享系统中资源的搜索机制即查找资源、定位资源的效率直接影响到用户获取资源的速度和网络的利用效率。现有p 2 p 网络中进行资源搜索一般采用三种方式【3 3 】：集中方式索引、广播方式和d h t 方式。1 集中方式索引n 印s t c r 是集中方式索引的典型代表。集中方式索引用一个集中目录服务器存储系统中所有文件的索引。当用户搜索文件时，以文件名向服务器提交查询，获得存储所需要文件的主机的i p 地址，然后文件从这个主机下载给用户。2 广播方式广播方式中不存在集中的目录服务器，系统中的节点对p 2 p 网络的拓扑结构第一章绪论和资源的存放位置没有任何精准的控制，系统中的每个节点只维护自己共享的文件及其索引，g i l u t e l l a 就是这种方式的典型代表。查找文件的典型做法是以一定的半径在网络中扩散( f l o o d i n g ) 查询消息。接收到消息的结点，将其与所存储的文件进行比较，若存在正的匹配，则向提出查询的结点回答。若消息的生命期( t i m e 埝l 沁e ，1 几) 不为0 ，则将查询消息向邻居结点扩散，否则，将之丢弃。3 d h t 方式在这种方式下对资源的搜索采用分布式哈希表( d i s t r i b u t e dh a s ht a b l e ，d h t )技术，如c h o r d 2 7 】、c a n 【3 1 】、p a s n y 2 8 】和t a p e 咖 2 6 】。在d h t 方式中，文件与键( k e y ) 相关联。键为一定长度( 如1 2 8 位) 的位串，通过对文件名进行哈希而得；结点的标识符通过哈希i p 地址获得，并与键具有相同的地址空间。d h t 方式有一个基本的操作，1 0 0 k u p ( k e y ) 来进行资源搜索，给定k e y ，1 0 0 k u p ( k e ”返回存储k e y 结点的i p 地址，该操作允许结点基于键来放置和获得文件，因而支持类似于哈希表的功能。查找文件时，直接将查询消息逐步地路由到拥有所需文件的结点上。d h t 方式已经在众多的规模分布式系统中采用，如分布式文件系统 3 4 】 3 5 】 3 6 、应用层组播【3 7 】【3 8 】和事件通知服务【3 9 】【4 0 】等。p 2 p 系统中存在的这三种资源检索方式，各有优缺点：集中式索引的优点是支持多样化( 部分匹配) 的查询，支持稀少文件的查询；缺点是系统存在单点故障即当用户数量过多或恶意攻击服务器时会导致整个系统瘫痪。广播方式的优点是支持多样化查询；缺点是当前的搜索算法对网络及参与者产生很大的负载，所以为了降低网络负载而限制查询的范围，这就导致目标文件存在于系统中，仍有可能找不到。这样对稀少文件的定位非常不利。d h t 方式搜索机制的优点是查询效率高，支持稀少文件的查询；缺点是不能有效地支持多样化查询。低效的资源搜索机制严重的阻碍了p 2 p 系统规模的进一步扩大，影响了p 2 p系统的使用效果，因此如何p 2 p 系统中高效的搜索机制成为p 2 p 系统研究的重要方向。1 3 3 信任机制问题随着现有p 2 p 系统的广泛、深入地应用，研究人员发现p 2 p 系统的性能始终无法达到理论上的最佳状态。其中一个主要原因是p 2 p 系统中节点的“匿名性。节点的“匿名性 保护了系统中用户的重要信息和隐私，使得p 2 p 系统具有高度的开放性，因此众多的用户才愿意加入到p 2 p 系统中来；但这种“匿名性也使得加入系统的用户节点类型、加入系统的目的等都存在较大的差异。不同的天津大学博士学位论文用户在系统中的自主行为并不受系统制约，导致了p 2 p 系统的服务质量不稳定、存在较大的安全风险，因此影响了p 2 p 系统中用户节点之间的合作。此外，现有p 2 p 系统中缺乏有效的管理机制，来激励用户更积极地参与合作，导致系统中的用户不愿意共享资源与其它用户分享。出现这些问题的最根本原因就是用户之间缺乏信任，这种用户之间的信任缺失使p 2 p 网络性能严重受损，同时也阻碍了发展更丰富的p 2 p 网络应用。因此，在致力于节点之间合作、提高p 2 p 服务整体可用性的目标下，构造有效的信任管理模型以便用户来选择资源以及激励用户之间的合作具有非常重要的意义。1 4 论文工作为了设计高效的p 2 p 系统的资源检索机制以及建立p 2 p 系统中的信任模型，本文总结了相关领域的研究成果，并对资源检索机制和信任模型展开深入研究，主要研究工作如下：1 全面综述了p 2 p 系统中的资源检索的相关技术和现有的p 2 p 系统的信誉模型，分析了现有资源检索模型和信任模型的特点，总结了相关研究工作中存在的主要问题，阐述了未来研究工作的发展趋势。2 针对非结构化p 2 p 网络和结构化p 2 p 网络的特点，提出了在动态的、自组织的p 2 p 网络环境中构造一个基于语义的分组p 2 p 网络。该网络使用向量空间模型( v e c 白d rs p a c em o d e l ，v s m ) 对节点的共享文档进行语义分类。将系统中语义相关的节点聚集在一起形成相关的语义分组，分组内的节点采用非结构化网络，构成松散的连接。在各个语义分组中评选出能力较强的节点作为组内的超节点( s u p e rp e e r ) 。网络中各个语义分组中的超节点采用分布式哈希表d h t 技术构成一个结构化的语义网络。节点可以根据节点共享文档的语义信息自主的加入到相关的语义分组中，因此网络中的资源搜索就在相关的语义分组中进行，降低了网络负载，提高了系统的查询性能。3 研究分析了社会学问题中的“小世界理论，按照社会关系网络中“物以类聚，人以群分”的原理，在非结构化的p 2 p 网络中有着同类资源的节点更容易建立关系。因此，通过这种方式对非结构化p 2 p 网络进行重组，利用网络中各个邻居节点共享文档的语义信息将语义相近的节点进行聚类。聚类后的节点之间形成小世界网络中的“短链。在节点的邻居节点中随机选择语义相似度低的节点形成小世界网络的“长链。这样使得p 2 p 网络的搜索、维护、存储开销降低，从而提高网络的可用性以及资