（计算机软件与理论专业论文）基于信任的自适应p2p拓扑构造研究.pdf

摘要 摘要 目前主流的全分布式非结构化p 2 p 网络在构造拓扑时都没有考虑节点的自 主行为特征，节点在拓扑上的地位是相同的，对等网络缺乏有效的机制保证网 络的良性发展，这降低了节点获得服务的有效性。p 2 p 网络是基于节点愿意共 享资源这一基本假设的，但实际情况是网络中存在大量的f f e 圮- r i d e r 节点，这些 节点只消费其他节点贡献的资源，而不共享自己的资源。此外，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 网络拓扑；信任机制；信誉机制；自适应 a b s t r a c t a b s t r a c t t h ep u r ep 2 pn e t w o r k sd o n tt a k et h ei s s u eo f t h ef r e e - r i d e r sa n dm a l i c i o u sp e e r s a st h ei n h e r e n tp a r to ft h et o p o l o g yd e s i g n , a n da l lt h ep e e r sa r ；es y m m e t r yi nt h e t o p o l o g y t h er e a l i t yi st h a tt h e r ea r eal o to ff r e e - r i d e rp e e r sa n dal a r g en u m b e ro f u n r e l i a b l es e r v i c e s ，a sw e l la sf r a u di np 2 pn e t w o r k s w h i l et h e s ei s s u e sa l el a r g e l y d u et op e e r s a u t o n o m o u sb e h a v i o r , t h en o n - c o o p e r a t i o no ft h ep e e r sc a u s e db yt h e a u t o n o m o u sb e h a v i o rs e r i o u s l yi n f l u e n c e dt h ep 2 pn e t w o r ks e r v i c ea v a i l a b i l i t y i no r d e rt oi m p r o v et h ep 2 pn e t w o r k 财 v i c ea v a i l a b i l i t y , m u s tt a k ef u l la c c o u n t o f t h ea u t o n o m yo f p e e r s p 2 ps e r v i c e su s a b i l i t ya n dp 2 pt o p o l o g ya r ec l o s e l yr e l a t e d ， p 2 pt o p o l o g yd e t e r m i n e st h ee f f e c t i v e n e s so f p e e r sa n dn e t w o r k t h i sp a p e ru s e dt h et r u s ta n dr e p u t a t i o nm e c h a n i s mt om e a s u r et h ep a r t i c i p a t i o n b e h a v i o ra n ds e | v i c ep r o v i d i n ga b i l i t yo ft h ep e e r s ，t h u sd y n a m i c a l l ya d j u s t st h e c o n n e c t i o n sb e t w e e np e e r s ，m a k i n gg o o dp e e rg r a d u a l l yo c c u p yaf a v o r a b l ep o s i t i o n o f t h et o p o l o g y , b u tt h el o wc r e d i b l ep e e r sa r ee x c l u d e dt ot h eb r i n ko f n e t w o r k b a s eo nt h ea n a l y s i so f r e l e v a n tw o r k , t h i sp a p e rp r o p o s eat r u s tm o d e lw h i c hi s b a s e do i lt h er e p u t a t i o ni n f o r m a t i o nt h a tp r o v i d e db yp a r to fc r e d i b l ep e e r s ，t h e n p r o p o s ea na d a p t i v ep 2 pt o p o l o g ya l g o r i t h mw h i c hb a s e do nt h et n l s tm o d e lt h i s p a p e rp r o p o s e d t h e t r u s tm o d e li sm o r es i m p l et h a no t h e r sa n di sh i g h l yf e a s i b l e ，a n d h a sg r e a t e ri m p r o v e m e n ti nt h ec o m m u n i c a t i o no v e r h e a da n dc r e d i b i l i t yo ft h e r e c o m m e n d a t i o no ft r u s ti n f o r m a t i o n t h ea d a p t i v ep 2 pt o p o l o g ya l g o r i t h mt a k ef u l l a c c o u n to ft h ep c c l t sr a t i o n a lb e l i e fa n di m p r o v e dd e f i c i e n c i e si ne x i s t i n gt r u s tb a s e d a d a p t i v ep 2 pt o p o l o g ya l g o r i t h m t h i sa d a p t i v ep 2 pt o p o l o g ya l g o r i t h mi sb a s e do n p e e e sc o m p r e h e n s i v ea b i l i t y ( s e r v i c ep r o v i d e sc a p a b i l i t i e sa n dt h ea b i l i t yt op r o v i d e c r e d i b l er e p u t a t i o ni n f o r m a t i o n ) ，b u tt h ee x i s t i n ga l g o r i t h mi so n l yc o n s i d e rp e e r s i v i c ep r o v i d i n gc a p a b i l i t i e s f i n a l l y , t h es i m u l a t i o ne x p e r i m e n ts h o w st h em e t h o d p r o p o s e di nt h i sp a p e ri sc o r r e c ta n de f f e c t i v e k e yw o r d s ：p 2 pt o p o l o g y ；t r u s t ；r e p u t a t i o n ；a d a p t i v e 学位论文独创性声明 学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除，文中特另t l d n 以标注和致谢的地 方外，沦文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得直昌盍堂或其他教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作r 明确 的说明并表示谢意。 学位论文作者签名( 手写) ：劫及签字口期：四年，月“日 学位论文版权使用授权书 本学位沦文作者完全了解直昌太堂有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权直昌太堂町以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制于段保存、汇编本学位论文。同时授权中国科学技术信息研究 所将本学位论文收录到中国学位论文全文数据库，并通过网络向 社会公众提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：粕教 签字日期：如毋年，2 ，月汰日 导师签名么弩巧 签字日期：年月口 第1 章引言 1 1 研究背景 第1 章引言 自1 9 9 9 年以来，p e e r - t o - p e e r ( p 2 p ) 重叠网络( o v e r l a y ) 模式t l l 已经成为研究 和应用的热点，p 2 p 网络应用模式的兴起得益于l n t a r n e t 的广泛普及、网络带宽 的大幅增加以及基于i n t e m e t 的端系统计算能力的迅速增强。传统的c l i e n t s e r v e r 网络应用模式中服务器的性能瓶颈以及单点失效的问题不仅限制了端系统资源 的充分利用，同时越来越无法满足新的分布式应用的需求。p 2 p 网络使原先在其 它网络计算模式中通常被忽视且广泛存在的端用户设备成为一种宝贵的计算资 源。与传统的c l i e n t s a v e r ( c s ) 模式相比，p 2 p 技术在有效利用网络上大量闲置 的信息资源、存储空间、处理器周期等资源，避免服务器带来的瓶颈问题，降 低服务器成本等方面有明显的优势。 p 2 p 技术并不是最近几年才诞生的新技术，它是i n t e r n e t 的本质特征之_ _ 。 最初的i n t c m e t 就是通过建立网页以及在网页中引入链接来实现网页之白j 的互 访，这些网页在功能和地位上都是相同的。惠普实验室将p 2 p 定义为利用分布 式资源以非集中的方式完成特定功能的一类系统或应用【2 1 。该定义强调了p 2 p 网 络的分布式特点。其中分布式资源指计算能力、存储资源、数据、网络带宽、 其他计算机及人力等资源。而特定的功能包括分布式计算、数据或内容共享、 交流和协作或者平台服务。非集中的方式可能应用于算法、数据、原数据或所 有这些。这并不排除在需要的时候在系统或应用的某些部分保存集中的方式。 p 2 p 系统的初衷是整合i n t e m e t 终端闲置的各种资源来提供服务，它所强调的非 集中的工作方式吸引了许多家用计算机用户的加入，因为这些用户可以独立的 选择并改变策略、角色和职责。任何具有网络连接功能及服务功能的网络可寻 址的计算单元都可以作为节点加入系统。p 2 p 技术成功地使网络资源从集中走向 分散，使个人用户真正参与到网络应用和计算中来。p 2 p 技术的发展以及p 2 p 与网格技术的结合，将影响整个计算机网络的概念和人们的信息获取模式，真 正实现“网络就是计算机，计算机就是网络”的梦想。 如今，对p 2 p 技术的研究已经涉及非常广泛的方面，主要包括：网络拓扑 第1 章引言 构造1 2 1 、安全与可靠性p l 、文件和数据共享4 1 等。p 2 p 的应用更是涵盖诸多领域， 如：文件共享、即时通讯、流媒体等，并出现了一些成果和产品，特别是在文 件共享和流媒体中的应用极大地推动了p 2 p 技术的研究与发展，体现出巨大的 商业和技术上的发展潜力。 1 2 问题的提出 p 2 p 网络是构建于i n t e m e t 之上的重叠网络( o v e r l a y ) ，重叠网络代表了节点 之间逻辑上的网络拓扑。p 2 p 网络的拓扑代表了节点间的交互关系，节点间的直 接连接( l i n k ) 是节点同网络的消息通道，代表了节点的邻居关系，节点通常在拓 扑上邻近的节点上进行信息检索，因此，网络拓扑决定了节点和网络的效用1 5 1 。 p 2 p 网络是基于节点愿意共享资源这一基本假设的，但实际研究表i l j 4 , 6 】， p 2 p 网络中7 0 的节点是f i e e - r i d e ! r 节点，这些节点只消费其他节点贡献的资源， 而不共享自己的资源。此外，p 2 p 网络中存在着大量不可靠的服务以及欺诈行为。 以众多的文件共享应用为例，2 5 的文件是伪造文件( f a k e df i l e s ) 7 , g l ，而且出现了 传播蠕虫病毒等恶意代码的文件【9 】恶意节点通过在p 2 p 网络中共享、传播恶意 文件来实施破坏行为。这些节点的这种自主性造成的不合作性严重影响了p 2 p 网络服务的可用性。因此，要提高p 2 p 服务可用性，必须充分考虑节点的自主 行为。 目前的非结构化p 2 p 网络【1 0 1 在构造拓扑时都没有考虑节点的自主行为特征， 节点在拓扑中的位置没有优劣之分，具有完全对等的功能和地位，从而难以促 进网络的良性发展。因此，必须充分考虑节点的自主行为特征，建立有效识别 节点的机制，从而构造能有效提高p 2 p 服务的整体可用性的自适应拓扑。 由于p 2 p 环境下节点的高度自主性，把握节点真实的客观能力差异和网络 动态性很难通过直接的方法，例如测量和询问，因而引入一种问接的衡量尺度 是十分必须的。在p 2 p 网络中，体现节点自主参与行为的一个合理尺度是其在 p 2 p 网络中与其它节点的交互史所表现出的可信度1 1 1 1 。因此，建立良好的信任机 制是自适应p 2 p 拓扑构造的基础。由于p 2 p 网络没有集中的中心点来管理整个 网络，且节点间的状态具有动态性和不确定性，因此，构建p 2 p 环境下的信任 机制还有不少问题需要研究。虽然目前已经存在一些基于节点可信度的p 2 p 拓 扑构造方法1 5 , 1 t 2 0 l ，然而这些方法在信任机制的构建和拓扑构造算法上存在一定 2 第1 章引言 的不足。 1 3 研究现状 p 2 p 网络拓扑构造的发展经历了第一代中心化拓扑、第二代全分布式非结构 化拓扑和混合式拓扑、第三代全分布式结构化拓扑，研究界对结构化和非结构 化拓扑的优劣尚无定论【1 l 】，两者各有所长，具有互补性。目前的研究集中在第 二代和第三代p 2 p 网络中。 较早的研究已经表明优化p 2 p 网络拓扑优化可以有效的改进系统的性能【1 2 1 。 新的研究在构造p 2 p 拓扑时多考虑了以下某个或某几个因素来提高p 2 p 网络的 性能：a ) 考虑节点能力的异构性，包括节点的计算能力、存储能力、网络带宽等； ”考虑节点地理位置的相似性；c ) 考虑节点“兴趣”的相似性；d ) 考虑节点的可 信度。 在全分布式非结构化p 2 p 网络中对网络拓扑进行优化，从每个p e e r 的角度 来看，可以更迅速、更充分的响应p e e r 的请求，提高p e e r 获得的服务质量；从 整个系统运作的角度来讲，可以降低系统运行的开销，在同等条件下，支持更 大规模的p 2 p 应用。针对非结构化p 2 p 网络的缺陷，研究者们提出的优化方案 主要有以下几个方面： 基于节点物理位置的对等网络拓扑优化【”以6 】，这一类对等网络优化方法的 基础是节点间通信代价的获取，通信代价表的构建是一个关键的问题。特别是 在网络动态变化的时候，很难在通信代价信息的及时性和获取通信代价所需开 销之间作出很好的平衡。并且，这一类方法仍然需要通过复杂的操作，在对等 网络中维护特定的拓扑结构。这给系统带来不少通信负载。 基于节点处理能力的p 2 p 网络拓扑优化 1 7 , 18 】，这一类对等网络优化方法通 过考虑系统中节点之间的差异来优化o v e r l a y 网络，但是该类方法通过对某些 s u p e r - p e e r 角色的提升，使系统中局部地出现了c l i e n t s e r v e r 通信模式。因而这 些方法也具有c l i e n t s e r v e r 模式共有的缺点。该类方法增强了系统对这些 s u p e r - p e e r 的依赖，削弱了传统的非结构化p 2 p 系统优越的容错性，增加了系统 中发生单点失败的概率。同时，该类方法并没有考虑节点能力异构性的背后隐 藏的节点自治、自私性的问题。 基于兴趣聚类的对等网络拓扑优化1 1 9 1 ，这类方案基于这样的假设：具有相 3 第1 章引言 近兴趣的节点更能提供所需的服务。这类方案存在的主要问题是，其需要依赖 清晰的语义分类来判断节点兴趣的相似性，而且方案没有考虑节点实际提供服 务的能力，即使一个节点具有相同的兴趣并不意味着其可以提供较好的服务质 量。 上面三种方法都没有关注p 2 p 网络中由于节点的自治、自私性造成的 f l e e r i d e r s 问题和恶意节点的问题。 基于节点可信度的对等网络拓扑优化 5 , 1 1 她加j ，该类方法根据节点在交互中 建立起来的信任关系，进行对等网络拓扑的优化，根据节点的可信度来选择邻 居节点，使节点靠近自己更信任的节点，从而将恶意节点驱逐到网络的边缘。 此类方法从考虑节点的自主性和自私性出发，采用信任度来刻画节点的行为表 现，同时信任度也体现了节点提供服务的能力。 c o n d i et 提出的自适应拓扑构造协议【习f t h ea d a p t i v ep e c r 4 0 - p e e rt o p o l o g i e s p r o t o c o l ，简写a p t p ) 将f r e e r i d e r 和恶意节点作为拓扑设计的本质问题。a p t p 的基本思想是节点选择可能为其提供可信文件的节点建立连接。在a p t p 中，节 点基于本地可信度和连接可信度选择连接某个节点或断连某个邻居。但是，a p t p 没有考虑节点本地可信度和连接可信度之间的差别。一旦节点i 为其邻居转发请 求使其收到恶意节点的响应并下载了不可信文件，且被该邻居断开连接，那么 尽管节点i 自身可能为该邻居提供了很多可信文件，但它将再没有机会与该邻居 建立连接，这妨碍了共享兴趣的节点之间的充分连接。 文献【1 1 】提出了基于节点全局可信度的拓扑进化方法，采用h a s h 函数来计 算信任度的存放地址，但是信任度的异地存放会引发出诸多问题。首先是安全， 该模型不能保证信任度的不可篡改性。另外一个问题也是主要的问题，档案点 的临时失效，节点的全局可信度就不可能得到，这将严重影响到网络的稳定性。 再者，档案点的计算繁杂，计算量大。根据全局信任度的公式和档案点的数据 结构，档案点每次接受到一个新的评价时，它必须更新记录中的其他节点的全 局信任度，这将是一个繁琐的过程，由此也造成了大量的不必要的通信，这将 极大的损坏档案点的积极性。而且在大规模对等网络中，为每个节点建立全局 可信度是否必要和可行仍有待进一步研究。该文提出的p 2 p 拓扑构造算法中， 规定了协商行为由高可信节点发起，协商成功与否由低可信节点决定，而这是 不合理的。 文献【2 0 】给出了一个基于信任的对等网络拓扑构造机制，使节点可以通过交 4 第1 章引言 互经验和其它服务推荐节点的反馈来建立对目标节点的信任，并相应地更新同 目标节点的链接关系，以便利之后的交互。但该文所采用的信任机制没有考虑 推荐者可信度的问题，并且提出的拓扑连接更新算法只考虑了连接发起方的理 性，而没有考虑连接请求接收方的理性，即连接请求接收节点也希望与高可信 节点进行连接，该算法默认为连接请求接收方会接受任何节点( 包括低可信节 点或恶意节点) 发出的连接请求。 文献 2 1 1 通过借鉴人际关系信任模型，利用b a y e s i a n 方法对a g e n t 的可信度 进行评估，提出了一种基于信任机制的多a g e n t 协作系统的形成方案。通过a g e n t 间基于信任关系的链接更新形成稳定的多a g e n t 协作系统，并通过随机图模型分 析了提出的协作系统的演化特征。 1 4 本文的主要工作 本文研究的出发点是为p 2 p 网络提供拓扑公平性、激励性，提高p 2 p 网络 的效用，相应地抑制恶意文件的传播。 由于p 2 p 网络所具有的动态性和开放性，以及节点的自主性使节点间的信 任关系相似于人际网络的信任关系，这些特点决定了在p 2 p 网络中可以采用模 拟人际网络的信任机制来建立节点问的信任关系，并用其来保障节点间的交互。 本文通过信任度来刻画节点提供服务的能力，用信任度来度量节点的主观 参与行为，从而动态地调整节点之间的连接关系，使得高可信节点逐渐占据拓 扑中有利位置、获得更可靠的服务，同时为其它节点提供可靠的服务，而低可 信节点被边缘化、获得更差的服务质量，使网络的性能得到提高，同时达到有 效激励、拓扑公平。低可信节点的边缘化也能在一定程度上抑制恶意文件的传 播，增强系统的安全性。 本文的主要工作包括以下部分： ( 1 ) 分析各种p 2 p 网络拓扑结构的特点，并比较了它们之间的差异。总结 p 2 p 拓扑优化相关研究现状。分析p 2 p 网络应用的核心安全需求，阐述信任机制 的研究目的和意义。总结p 2 p 信任模型的研究现状，并分析现有信任模型存在 的问题。 ( 2 ) 提出基于可信局部推荐的p 2 p 信任模型，阐述模型的基本思想，定义 了相关概念和模型中的数据结构，讨论了信任计算及更新的问题，对本模型的 5 第1 章引言 信任查询及初始化问题作了分析，并分析模型的安全性。 ( 3 ) 提出基于信任的自适应p 2 p 拓扑构造算法，该算法是基于节点的综合 能力( 服务提供能力和提供可信推荐的能力) 来动态调整邻居节点，并且考虑 交易节点双方的理性。 ( 4 ) 设计仿真实验来验证本文提出的方法的正确性和有效性。 1 5 本文的组织结构 本文主要是研究p 2 p 信任机制和基于信任机制的p 2 p 网络拓扑构造。全文 共分为六章： 第l 章，引言，介绍了本文的研究背景、问题的提出、相关研究的现状及 本文研究的重点内容。 第2 章，p 2 p 网络拓扑及特点，介绍了p 2 p 网络拓扑的类型，p 2 p 网络拓扑 的特点，并对每种类型作了比较。 第3 章，p 2 p 网络信任模型研究，阐述了p 2 p 信任机制的研究目的和意义， 给出了信任的定义，总结了信任的特点，概括了信任模型的设计要求，总结了 信任模型的研究现状，并分析了现有信任系统存在的问题。 第4 章，基于信任的自适应p 2 p 拓扑构造，提出了基于可信局部推荐的p 2 p 信任模型，并提出了基于该信任模型的p 2 p 拓扑构造算法。论述了基于可信局 部推荐的的p 2 p 信任模型的基本思想，定义了相关概念和模型中的数据结构， 讨论了信任计算及更新的问题，对本模型的信任查询及初始化问题作了分析， 并分析了模型的安全性。定义了拓扑构造的相关参数，拓扑构造算法充分考虑 了节点的理性。 第5 章，仿真实验分析，以文件共享应用为仿真实验背景，在网络中设置 三类节点，对进行本文提出的拓扑构造算法进行正确性和有效性验证。 第6 章，总结与展望，总结了本文的工作，指出了本文工作中的不足，并 提出了下一步研究工作的设想。 6 第2 章p 2 p 网络拓扑及特点 第2 章p 2 p 网络拓扑及特点 2 1p 2 p 网络拓扑结构 拓扑结构是指分布式系统中各个计算单元之间的物理或逻辑的互联关系， 节点之间的拓扑结构一直是确定系统类型的重要依据。一般地，研究界关于p 2 p 的拓扑结构有多种分类方法，如根据拓扑的可扩展性将其分为可扩展( s c a l a b l e ) 拓扑和非可扩展( s c a l e f r e e ) 拓扑：根据拓扑维护对中心节点的依赖程度将其分为 基于中- i , ( c e n t r a l i z e d ) 、全分布式( d e c e n t r a l i z e d ) 或混合式的拓扑；根据拓扑结构 的可确定性将p 2 p 拓扑结构分为结构化拓( s t r u c t u r e dt o p o l o g y ) 扑和非结构化拓 b ( u n s t r u c m r e dt o p o l o g y ) ；综合考虑网络中心化和结构化的程度，p 2 p 拓扑结构 可分为中心化拓扑、全分布式非结构化拓扑、全分布式结构化拓扑和部分分布 式拓扑。根据需要，本文采用了后一种分类法，在不引起二义性的情况下，我 们也称结构化拓扑和非结构化拓扑为结构化或非结构化网络。 结构化的拓扑构造也称为确定性的拓扑构造，按结构化拓扑构造的p 2 p 系 统其网络结构是预先确定的，如c h o r d 的环状结构，c a n 的d 维笛卡儿空间等。 非结构化拓扑在拓扑构造上具有随意性，因而被认为是非确定的，基于非结构 化p 2 p 网络的应用包括为数众多的文件共享应用。典型的如g n u t e l l a 和k a z a a 等。非结构化拓扑的优势在于实现相对简单和便于维护。结构化拓扑的优势在 于其对象定位机制较小的网络开销和确定性的定位上界，然而，由于其确定性 的结构造成维护上较非结构化拓扑更为困难。基于非结构化拓扑的p 2 p 应用往 往基于广播搜索机制，广播搜索机制的优势在于由于支持模糊匹配所带来的可 选择性。但是广播搜索机制造成的消息开销成了影响非结构化拓扑扩展性的一 个关键因素，与之相反，结构化拓扑采用的精确匹配的对象定位机制由于无法 有效支持模糊匹配而在( 结果的) 可选择性上有所欠缺。 研究界对结构化和非结构化拓扑的优劣尚无定论，两者各有所长，具有互 补性。有研究指出，通过对广播搜索机制的适当优化，可以有效减少其带来的 消息开销1 2 2 。同时，通过为结构化拓扑的确定性定位机制增加语义转换中间层 和多播机制，也可以带来一定的可选择性 2 3 1 。由于非结构化拓扑已成功应用在 7 第2 章p 2 p 网络拓扑及特点 p 2 p 文件共享系统等应用中，且全分布式非结构化p 2 p 网络具有典型代表意义， 但其在拓扑构造上有一些缺陷，因此，本文选取非结构化拓扑构造作为研究对 象。以下将从p 2 p 网络发展历程分别对以上不同特征的p 2 p 系统进行介绍。 2 1 1 中心化拓扑 以n a p s t e r 2 4 为代表的第一代p 2 p 网络采用采用中心化拓扑结构其本质上并 非纯粹的p 2 p 系统。该拓扑结构下，存在中央索引服务器，索引服务器中存储 各个资源所对应的节点的地址。每个节点通过访问索引服务器得到自己所查找 的内容的网络地址，继而发起交互。中心化拓扑最大的优点是维护简单，资源 发现效率高。由于资源的发现依赖中心化的目录系统，发现算法灵活高效并能 够实现复杂查询。但由于整个系统依赖于中心索引服务器，存在单点失效问题， 一旦服务器发生故障无法工作，整个系统将处于瘫痪状态；同时，该类系统的 可扩展性较差，无法动态适应网络规模的变化，随着网络规模的扩大，对中央 索引服务器进行维护和更新的成本也将急剧增加，因而中心化拓扑结构不适合 于大型网络应用。 节点带点 图2 i 中心化拓扑 2 1 2 全分布式非结构化拓扑 为了解决第一代中心化拓扑结构的p 2 p 网络对中央索引服务器的依赖问题， 出现了以g n u t e u a 1 0 】为代表的全分布式非结构化的第二代p 2 p 网络。全分布式非 结构化拓扑的p 2 p 网络是在重叠网络( o v e r l a yn e t w o r k ) l - 采用了随机图的组织 8 第2 章p 2 p 网络拓扑及特点 方式，网络中的节点随机建立连接，具有完全对等的功能和地位。节点使用有 限范围内的“洪泛( f l o o d i n g ) ”机制发送请求，查询的广度可以根据1 t l ( t i m e t o l i v e ) 的设置决定，其他节点收到查询请求后，给出包含匹配的内容信息和地址 信息的响应，从而使源节点能与其建立连接进行文件下载。尽管g - n u t e l l a 系统的 这种基于“洪泛”的查询技术支持语义查询，能有效定位复制率很高的内容， 且能够适应动态变化的p 2 p 网络环境。但这种查询机制无法定位网络中稀缺的 内容，且随着查询数目和网络规模的增加，每个节点的负荷也快速增加，使得 网络不具有可扩展性。由于没有确定拓扑结构的支持，非结构化网络无法保证 资源发现的效率。发现的准确性和可扩展性是非结构化网络面临的两个重要问 题。 2 1 3 半分布式拓扑结构 图2 2 全分布式非结构化拓扑 我有a 文件 半分布式拓扑结构( h y b r i ds t r u c t u r e ) ，也称混合式结构，吸取了中心化结构 和全分布式非结构化拓扑的优点，是第二代p 2 p 网络的典型应用系统。充分考 虑了节点能力的异构性，采用选择性能较高( 处理、存储、带宽等方面性能) 的节 点作为超级节点( s u p e r n o d e s ) ，在各个超级节点上存储了系统中其他部分节点的 信息，发现算法仅在超级节点之间转发，超级节点再将查询请求转发给适当的 叶子节点。半分布式结构也是一个层次式结构，超级节点之间构成一个高速转 9 第2 章p 2 p 网络拓扑及特点 发层，超级节点和所负责的普通节点构成若干层次。半分布式结构的优点是性 能、可扩展性较好，较容易管理，但对超级节点依赖性大，易于受到攻击，容 错性也受到影响。采用这种结构的典型案例就是k a z a a 2 5 和e d o n k e y 2 6 1 。 2 1 4 全分布式结构化拓扑 图2 3 半分布式拓扑 为了提高第二代全分布式非结构化p 2 p 网络的可扩展性和资源定位有效性， 研究者提出了第三代p 2 p 网络，即全分布式结构化拓扑。全分布式结构化拓扑 最经典的案例是c h o r d 2 7 和c a n t 删。全分布式结构化拓扑的p 2 p 网络主要是采 用分布式散列表( d i s t r i b u t e dh a s ht a b l e ，简写成d h t ) 技术来组织网络中的节点。 d h t 是一个由广域范围大量节点共同维护的巨大散列表二散列表被分割成不连 续的块，每个节点被分配给一个属于自己的散列块，并成为这个散列块的管理 者。通过加密散列函数，一个对象的名字或关键词被映射为1 2 8 位或1 6 0 位的 散列值。同时，每个节点需维护一个路由表，包括邻居节点的地址和标志符。 d h t 类结构能够自适应节点的动态加入腿出，有着良好的可扩展性、鲁棒性、 节点i d 分配的均匀性和自组织能力。由于重叠网络采用了确定性拓扑结构，d h t 可以提供精确的发现。只要目的节点存在于网络中d h t 总能发现它，发现的准 确性得到了保证。d h t 类结构最大的问题是d h t 的维护机制较为复杂，尤其是 1 0 第2 章p 2 p 网络拓扑及特点 节点频繁加入退出造成的网络波动会极大增加d h t 的维护代价。此外，结构化 拓扑采用的精确匹配的查询机制无法支持语义查询，限制了请求者对内容的选 择性。 图2 4 全分布式结构化p 2 p 拓扑 以上四种p 2 p 拓扑结构基本上代表了p 2 p 网络的发展，每一种拓扑结构都 在一定的时期发挥了重要的作用，表2 1 从扩展性、可靠性等五个方面比较了这 四种拓扑结构的利弊。 表2 1p 2 p 不同拓扑结构特点比较 比较标准拓扑结 中心化拓扑全分布式非结构全分布式结构化 半分布式拓扑 构 化拓扑拓扑 可扩展性 差差好好 可靠性差好好 由 可维护性最好最好好 由 发现算法效率 最高中高 由 复杂查询支持支持 不支持支持 新的研究在构造p 2 p 拓扑时多考虑了以下某个或某几个因素来提高p 2 p 网 络的性能：a ) 考虑节点能力的异构性，包括节点的计算能力、存储能力、网络带 宽等；b ) 考虑节点地理位置的相似性；c ) 考虑节点“兴趣”的相似性：d ) 考虑节 点的可信度。针对非结构化p 2 p 网络，有研究指出，根据节点的处理能力调整 邻居节点【m ，可以解决节点的过载问题；选择地理位置更近的节点作为邻居节 1 1 第2 章p 2 p 网络拓扑及特点 点【1 卅可解决p 2 p 拓扑与底层物理网络之间的匹配问题，从而提高p 2 p 网络的性 能；根据兴趣在原有c m u t e l l a 网络拓扑的基础上添加快捷邻居节点或者根据兴趣 选择邻居节点【1 8 1 可以有效减少网络中洪泛的查询请求数量，并减小查询请求到 达响应者所需的跳数：根据节点的可信度来选择邻居节点习可以将恶意节点驱逐 到网络的边缘，从而提高p 2 p 网络服务的可用性。 2 2 典型p 2 p 网络的特点 典型的p 2 p 网络由i n t e m e t 终端以自组织的方式形成，具有以下特点： 1 ) 应用层o v e r l a y 拓扑特性：p 2 p 网络是工作在应用层的重叠网络。所谓 覆盖网络，是指为了实现特定的功能而建立在一个或多个己存在的网络之上的 网络，该网络需要维护一些额外的信息，例如网络中节点的连接关系、节点的 位置信息等。以文件共享p 2 p 网络为例，其所实现的特定功能就是文件的定位， 以及文件下载的组织。p 2 p 网络的应用层o v e r l a y 拓扑特性使p 2 p 网络能够灵活 容纳处于不同物理网络域的各种i n t e m e t 终端。 2 ) 自组织性：p 2 p 网络具有自组织性，节点可以在没有仲裁者的情况下自己 维护网络的连接和性能，其网络拓扑会随着节点的加入和离去而重新组织。p 2 p 网络的自组织性使其能够适应动态变化的应用环境。 3 ) 自治性：p 2 p 网络中的节点可以依据自己的意愿选择行为模式，没有外在 的强制约束。p 2 p 网络的自治性对节点的自主行为给予了充分的尊重。 4 ) 分布式的资源聚集及协作：在p 2 p 网络中，节点贡献自己的空闲资源， 并利用p 2 p 网络提供的资源定位功能发现其他节点的可利用资源，然后进行彼 此之间的资源共享。因此，p 2 p 网络提供了将i n t e m e t 终端闲散资源聚集的能力 并促成了这些终端之间的协作。 5 ) 节点的对等性：p 2 p 网络中的节点承担相同的职责，并采用对等的通信模 式。在纯p 2 p 网络中，系统的维护开销( 路由、消息转发、维护修复等) 由节点共 同来承担。 1 2 第3 章p 2 p 网络信任模型研究 第3 章p 2 p 网络信任模型研究 3 1p 2 p 网络信任机制的研究目的及意义 3 1 1p 2 p 网络应用的核心安全需求 p 2 p 技术在协同计算，分布式存储和文件资源共享领域得到了广泛的应用， 但p 2 p 网络具有的如匿名性、动态性和开放性等为用户提供便捷的特性却成为 了恶意用户入侵、破坏网络、发动攻击行为的安全隐患。例如，对等网中每一 节点都具有路由转发的能力，不良节点可随意更改路由转发信息，丢弃信息； 或将木马程序等恶意代码伪装成热点信息供网络中的其他节点下载：或伪造大 量不存在节点标识和目的不可达信息，针对整个网络发动d i ) o s 攻击1 2 9 1 等。产 生这一系列安全隐患的主要原因是对等网技术在最初设计时并没有考虑安全因 素，p 2 p 系统中的各节点彼此陌生，节点间以匿名的方式进行通信或文件信息的 共享和互换。每个节点可随意加入或退出网络，节点的状态不确定，节点标识 不唯一，各节点基于同一兴趣自主地处理与其他节点的交互，其个人行为后果 没有任何责任可言。因此，如何实现一种机制将在p 2 p 网络中存在的一些提供 欺骗性或者恶意服务的节点进行隔离，以避免同此类节点进行交互而使用其伪 造的、错误的或误导性的信息和服务是p 2 p 网络安全面临的主要问题。 在任何一个有一定规模的分布式应用中信任关系都是重要的，在p 2 p 网络 应用中，信任关系显得更为重要。这主要表现在如下两个方面： ( 1 ) p 2 p 网络应用的特殊性使得信任关系必不可少，主要原因如下： 首先，在p 2 p 网络的各种应用中，无论是对等计算、文件共享，还是协同 工作，其应用环境都是复杂而不可控的i n t e r n e t 环境，如：s e t i h o m e 项目的 桌面用户遍布全球，在不安全的网络环境下区分可信对象和不可信对象是保证 安全的基本要求。其次，p 2 p 网络应用中，各用户往往可以扮演多重角色，具有 很大的自主性和对等性，管理员难以进行管理和控制，所以p 2 p 网络应用的顺 利进行更有赖于用户间的相互信任。 再者，部分p 2 p 应用追求匿名性、自由自主和零开销的目的，使得信任关 1 3 第3 章p 2 p 网络信任模型研究 系成为系统可用性的保证。如：文件共享系统中，相当一部分文件是伪造或无 效的，通过建立信任管理系统就可以对系统用户评定信任等级，信任等级高的 节点成为首选，从而提高了系统可用性。 ( 2 ) p 2 p 网络的特点决定了p 2 p 应用中信任关系难以建立，这主要是因为： 首先，p 2 p 网络结构是分散化的、没有集中的中心点，也没有层次化的组织 结构，这意味着难以采用类似于统一的p k i 体系的集中式信任管理。 其次，p 2 p 中网络节点是动态的，加入和退出网络的时间是动态的，从而难 以选定一个固定的节点充当可信第三方。 再者，p 2 p 网络具有可配置性，节点具有自主性，可以自定义组，并制定各 自的安全策略，使得某一种信任关系管理难以满足p 2 p 应用的要求。但如果采 用多种信任关系管理系统，又面临统一和相互兼容的问题。 因此，在p 2 p 网络应用的一般安全需求中，信任关系是最基本、最核心的 安全需求，是保证p 2 p 网络应用安全的关键。 3 1 2p 2 p 信任模型研究的意义 由于p 2 p 网络本质上是一个开放的、动态的网络，其中的节点可以动态地 加入和退出，也可以自主决定在网络中的行为，而网络中并没有权威中心对这 些节点进行管理，节点之间也没有确定的信任关系，因此对于一个节点来说无 法保证协作方的行为的可靠性。p 2 p 网络所具有的动态性和开放性，以及节点的 自主性使节点间的信任关系更相似于人际网络的信任关系，其相似性主要表现 在： 1 ) 节点可以搜集、分析关于对方的信任信息并建立信任关系： 2 ) 节点间的交互会留下零星的信任信息f 交互行为记录) ； 3 ) 节点间可以利用信任委托、推荐等传递信任； 4 ) 节点对于交互对象具有充分的自主选择权。 上述的这些特点决定了在p 2 p 网络中可以采用模拟人际网络的信任机制来 建立节点间的信任关系，并用其来保障节点间的交互。 p 2 p 网络中每个节点都具有较高的自主性，自主地评估其它节点得出信任度 可靠的节点，这和人类社会人际网络关系中由个体组成的信任网络具有相似性。 p 2 p 网络中的节点可以通过自身的经验和观察，以及其他节点的推荐来建立信任 1 4 第3 章p 2 p 网络信任模型研究 关系。通过总结节点最直接的历史交互经验，对节点未来的可能行为通过信任 积累的策略做出选择，同时，节点也可以根据其他节点的信任推荐即某一节点 的信誉值来修正对特定目标节点的信任度。而信任度修正的选择根据节点是只 相信个人的评判还是参照其他节点的推荐进行调整，这其中需要一定的信任评 估方案来综合自身的直接交互经验和其他节点的推荐，以评价对特定节点的信 任，并使信任评估结果能正确地表现节点的实际行为表现。信任评价结果也代 表了对节点未来行为的一种期望。这些都和人类社会中个体间彼此信任选择过 程类似。 由于可以使用信任来评价节点行为表现，因此，也可以使用信任来定义节 点提供特定服务的能力，节点并可以使用信任来指导对协作节点的选择，从而 获得最适合的服务，从而有效地提高节点的交易质量。相应地，节点也可以避 免同不可信节点进行交互，从而将不可信节点隔离于系统之外，有效地抑制了 不可信节点的活动，减少其对网络的危害。虽然在p 2 p 网络中交互的节点间无 法保证各自行为的可靠性，但节点间在历史交互活动中会留下零星的行为记录 或称信任信息，其他节点可以依据这些历史信任的记录来决定对方行为的可信 程度并进行自主选择。同时，各节点推荐的信任值可以彼此进行传递，当有良 好行为的节点在寻找和决定与哪个节点进行信息内容请求或向哪个节点提供服 务时，能为其提供评判依据