（计算机应用技术专业论文）无线网络下p2p的资源定位和获取模型.pdf

浙江工业大学硕士学位论文 源定位的命中率和较短时延，改善了资源获取时的稳定性，具有进一步的研究价值。 关键词：m p 2 p ，资源定位，d h t ，区域划分，超节点，节点振荡，资源获取，n s 2 平 台 浙江工业大学硕士学位论文 p e e r t o p e e rr e s o u r c el o ca t d i g i ，n d e rw i r e l e s sn e t w o r k a b s t r a c t n o w a d a y s w i t i lt h ed e v e l o p m e n to fb o t hw i r e l e s sn e t w o r ka n dp e r s o n a lm o b i l e d e v i c e ，p e o p l ea r e a c c u s t o m e dt oa c c e s si n f o r m a t i o nv i aw i r e l e s sn e t w o r kf r o ma n y w h e r e a ta n y t i m e a l s o ，p e o p l em o r ea n dm o r ew a n tt os h a r ea n dt r a n s f e rt h ed a t ab e t w e e nt h e i r m o b i l ed e v i c e s a n dm o r ea n dm o r ep e o p l ea r ei n t e r e s t e di na p p l y i n gp 2 pu n d e rw i r e l e s s n e t w o r k t h e r ec o m e so u ta n e w c o n c e p tc a l l e dm p 2 e r e s o u r c el o c a t i n gi sak e yp r o b l e mo fa ne f f i c i e n tm p 2 ps y s t e m b u tw i t l lt h e r e s t r a i n t so fw i r e l e s sn e t w o r ka n dm o b i l ed e v i c e ，s u c ha sh i g h l yd y n a m i ct o p o l o g y , l o w c o m m u n i c a t i o nb a n d w i d t ha n dl i m i t e db a t t e r yc a p a c i t yo ft h ed e v i c e ，t h es t r a t e g yo f m p 2 p sr e s o u r c el o e a t i n gi sd i f f e r e n tf r o mn o r m a lo n e s t h em a i nw o r ko f t h i sp a p e ri sa sf o l l o w s ( 1 ) w eg i v eah i g hr e s o u r c eh i t t i n gr a t ea n ds h o r td e l a ym o d e l i tu s e st h ed h t a n d r e g i o np a r t i t i o na so u rb a s i cl e s o u i l ：el o c a t i n gm e t h o df o rq u i c ks e a r c h i n g ( 2 ) w ei n t r o d u c es u p e rp e e rt oi m p r o v ee f f i c i e n c yo fr e s o u r c eh i t t i n ga n da v o i dt h e p o o rs i t u a t i o nw h e nu s i n gf l o o d i n gr e q u e s t ( 3 ) a se x i s t e dm o d e ld i d n tc o n s i d e rt h es i t u a t i o n so fi m b a l a n c e dd i s t r i b u t ev e r y m u c h ，w eg i v eas t r a t e g yt oi m p r o v et h ee f f i c i e n c yw h e nt h ep r o b l e mo c c u r s ( 4 ) w eg i v et h es o l u t i o n st od e a lw i t ht h e 。t r a s h i n g s i t u a t i o ne x i s t e di i lm o s tm o d e l s ， w h i c hm e a n s p e e r sm o 、ef r e q u e n t l yb e t w e e nt w or e g i o n s b o r d e r l i n e w h e nt h i ss i t u a t i o n o c c u r s m o s to f t h i sn e t w o r k 。sc o s tw i l lb ee x p e n d e di nd e a l i n gw i t l lt h es t a t ec h a n g e ( 5 ) w ec o n s i d e rr e s o u t c , el o c a t i n ga n dr e s e u t g er e t r i e v a lt o g e t h e r w h e nt h ec o n t e n t 浙江工业大学硕士学位论文 h a sm o r et h a no i l ep r o v i d e r , w eu s et h e p r o v i d e rs e l e c t i o na l g o r i t h m a n dw ep r o v et h a ti t i m p r o v e st h es t a b i l i t ya n df a u l t t o l e r a n c eo f d a t at r a n s f e r s ( 6 ) w ep r e s e n tt h ed e s i g na n de x p e r i m e n to ft h en e wm o d e l t h e nw es i m u l a t ea n d e v a l u a t ei to nt h en s 2 p l a t f o r m f r o mt h ec o m p a r i s o nr e s u l t so fo u re x p e r i m e m , w eh a v e p r o v e dt h a tt h ei i c wm o d e lp e r f o r m sb e t t e rt h a ns o m em o d e l s ，a n da tt h es a m et i m e ，t h e n e wm o d e le n s u r e st h eh i g hh i t t i n gr a t ea n ds h o r td e l a y a l s o ，i ti m p r o v e st h es t a b i l i t yo f t r a n s f e r s s ot h eh e wm o d e lw o r t hd e e p l yr e s e a r c h i n g k e yw o r d s ：m p 2 p ，r e s o u r c el o c a t i n g ，d h t ，r e g i o np a r t i t i o n ，s u p e rp e e r w a s h i n g ，r e s o u r p er e t r i e v a l ，n s 2p l a t f o r m 浙江工业大学硕士学位论文 图索弓 图1 1 混杂式p 2 p 。3 图2 1d y n a m i ci n d e x 1 2 图3 1 整体框架图1 9 图3 - 2 资源发布过程伪代码1 9 图3 3 资源定位过程伪代码2 0 图3 4 超节点推举2 3 图3 5 区域划分2 4 图3 - 6 节点分布不均匀2 5 图3 7 由邻居节点接管 图3 - 8 区域内移动2 6 图3 - 9 局部振荡 图4 - lk e y 的发布 图4 - 2 资源请求流程图 图4 - 3 区域k e y 表维护 图4 - 4 请求协议流程。 2 7 3 0 3 0 图4 - 5 资源发布协议流程3 6 图5 1 模拟中的网络拓扑结构示意图3 8 图5 2 有无超节点时定位时延比较图3 9 图5 3 有无超节点时命中个数比较图4 0 图5 _ 4 节点分布不均匀拓扑图 图5 5 节点分布不均匀时命中时延比较图4 2 图5 - 6 节点分布不均匀时命中个数比较图4 3 图5 7 节点传输成功率比较图 浙江工业大学硕士学位论文 表索引 表1 各模型比较表1 6 2 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工 作所取得的研究成果。除文中已经加以标注引用的内容外，本论文不包含其他个 人或集体已经发表或撰写过的研究成果，也不含为获得浙江工业大学或其他教育 机构的学位证书而使用过的材料。对本文的研究作出重要贡献的个人和集体，均 已在文中以明确方式标明。本人承担本声明的法律责任。 作者签名： 日期：2 呷年矿月习日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 本人授权浙江工业大学可以将本学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密 ( 请在以上相应方框内打“寸) 作者签名：日期：年月日 导师虢江荔秒日期砷堋7 日 浙江工业大学硕士学位论文 第一章绪论 本章首先论述本文的动机和相关的技术背景知识，然后阐述了本文的目标，最后是 本文的内容组织介绍 1 1研究动机 当前，随着科技的发展，涌现出越来越多的手持设备，包括笔记本电脑、个人数字 助理( p d a ) 、手机等等，同时，网络供应商开始提供越来越完善的无线网络服务。随之 而来的是人们对移动数据服务需求的增长。随着3 g 等新一代移动网络的建成和普及， w i f i 接入点在各个公共设施和办公场所的逐步铺开，人们开始习惯于使用移动终端接入 网络，享受无线网络提供的服务。数据分发和共享，作为如今i n t e m e t 网上一种用户普 遍有需求的业务，如何将其顺利移植到无线网络和移动终端上，成为研究者们关注的问 题。 在传统的有线网络中，人们对数据的分发和共享已经进行了较多和较深入的研究， 给出了众多不同的模型，使得在不同的应用环境下，人们能够选择方便快捷的方式进行 数据传输和共享。其中，最近兴起并逐渐成熟的一个模型就是p 2 p 模型田。该模型使得 人们能够充分发挥网络中每台机器的潜力，也拓宽了人们对传统的客户端、服务器端数 据传输的认识，让网络中大范围大规模的数据传输成为可能。 因此，p 2 p 作为一种分布式数据传输的架构，其高带宽、多资源的特点正好切合人 们对更深入更广泛的数据共享的要求。但是由于无线网络和移动终端自身的特点和局限 性，传统的基于有线网络的p 2 p 模型并不适宜直接应用在无线网络和移动终端上，需要 进行针对性的改进和创新。于是出现了m p 2 p ( m o b i l ep 2 p ) 的概念，将p 2 p 部署在包括 w i f i ，a dh o e ，3 g 等各种无线网络上进行数据共享和传输成为一种新的趋势。 在对无线网络中p 2 p 应用部署的研究中，针对部署的不同层次，有许多不同的研究 方向，包括各种路由算法的研究、资源定位的研究、p 2 p 节点的访问控制研究、数据的 交换技术研究、p 2 p 无线网络的安全性研究等等【扪。 本文着重于资源定位和获取方面的研究，提出了一种在无线环境中的p 2 p 资源定位 浙江工业大学硕士学位论文 和获取的模型，给出具体设计方案，实现核心模块，并对该模型进行验证。将p 2 p 的资 源定位和资源获取结合起来，是考虑到通常的资源定位算法，不能提前保证定位后节点 之间数据传输的稳定性，即两者无定的关联性，而本文则在资源定位时就相应考虑数 据传输的要求，这在一定程度上保证了数据传输的稳定。 1 2相关技术 1 2 1p 2 p 简介 1 p 2 p 的概念 f 2 p 是一种通信模型，在这个模型中的每一个部分都拥有相同的能力并且都能独立 的互相通信。与之相对的是c s ( c l i 朗f f s c r v c r ) 和m s ( m a s t e r s l a v e ) 模型。 相对于普通的c s 结构中只由s e r v e r 端提供下载的情况，p 2 p ( p e e r - t o - p e e r ) 网络中， 每一个节点都同时具有上传和下载的功能，因此具有更多的连接参与者并能提供更大的 带宽。现在，p 2 p 开始越来越多地应用在共享文件内容( 包括声音，视频，数据以及任 何的数字格式的数据) 和实施数据传输( 电话传输) 等方面。 最早期被广泛使用的类p 2 p 网络是u s e n e tn e w ss e r v e r 系统，系统中的节点通过在整 个u s e n e t 网络中发布文章来达到互相交流的目的。当然，早期的系统并不是纯粹的p 2 p 系统，作者阅读和发布文章时依然需要连接到本地的n e w s 服务器。后来根据其进一步 发展而来的n a p s t e r 4 ，o p e n n a p t 5 1 等p 2 p 系统依然在一定程度上依赖于网络中的服务器 来完成某些工作，比如资源的索引等。它们是一种融合了传统c s 模型和p 2 p 模型各自 特点的混杂模型。 而进一步发展的g n u t e l l a l 6 和f 嗍l e t 【7 】则是纯p 2 p 系统，在这些系统当中，每个节 点都能独立完成网络中的各项功能，不再依靠服务器节点。在纯p 2 p 系统中，没有了客 户端和服务器端的概念，每个平等的节点同时履行服务器和客户端的工作。 随着p 2 p 应用的进一步普及，p 2 p 的概念也一直在随着p 2 p 的应用扩展而发展，现 在它的概念已经扩展到用来表示分布式网络中的动态关系，这种关系已经不再是简单的 计算机对计算机的关系，而是人对人的关系【8 】。 2 p 2 p 网络的分类及特点 p 2 p 网络，是从传统的网络模型中变化而来，由于其变化的多样性等自身特点，使 其在目前并没有一种固定的区分的方法。通常的做法是可以根据网络的中心化程度、网 2 浙江工业大学硕士学位论文 络拓扑结构等不同的方面来对p 2 p 网络进行简单的区分，以便对p 2 p 网络有一个相对完 整的理解。 p 2 p 网络依据其系统的中心化程度将系统可以分为纯p 2 p 系统和混杂式p 2 p 系统 2 1 s l 唧 纯p 2 p 系统特点： ( 1 ) 每个节点都是平等的，同时扮演客户端和服务器的角色，即每个节点都同时拥有 从别的节点下载内容和向其它节点提供内容的能力。 ( 2 ) 没有中心服务器来管理整个网络。节点都具有一定的自治能力，这样的系统可以 方便地进行扩张和缩小节点规模，具有较大的自由度，但是对节点自身的能力( 计算， 存储，电力资源等) 有一定的要求。 ( 3 ) 没有中心路由，路由功能由节点自身同时兼任。当节点在网络中发送数据时，除 了邻居节点可以直接抵达外，向其它远处节点发送的数据都需要经过中间节点的中转。 因此，节点的一部分能力将被用来出来路由。 这种类型的代表是上面提到的g - n u t e l l a 和f r e e n e t 网络。 混杂式p 2 p 系统特点： 图1 - i 混杂式p 2 p ( 1 ) 拥有一个中心服务器，上面保存有所有节点的信息，并响应其它节点的请求。当 一个节点加入一个混杂式的p 2 p 网络时，该节点将首先向中心服务器注册自己的信息， 以备其它节点的查询。 ( 2 ) 节点负责发布自己的资源到中心服务器之后，当它们被其它节点请求时，中心服 浙江工业大学硕士学位论文 务器在比较搜索之后将请求的结果返回给请求节点，之后，请求节点和资源提供节点将 开始数据的传输。 ( 3 ) 在混杂式p 2 p 系统中，中心服务器具有十分重要的地位，也是系统可能的瓶颈所 在。当网络规模扩大时，中心服务器的负担将变重，不稳定的可能性也将提高，因此， 混杂式的p 2 p 网络存在节点扩展不易，瓶颈突出，稳定差的缺点。 混杂式p 2 p 网络的代表如n a p s t c r 。 按照网络拓扑结构进行划分，p 2 p 系统又可分为结构化、非结构化和松散结构化 p 2 p 2 嘲。 结构化p 2 p ： ( 1 ) 节点之间有相互的连接信息，形成特定规则的拓扑结构。 c ) 当对某资源进行请求时，若资源在拓扑结构中存在，则一定能够找到。即在结构 化网络中，文件( 数据) 的位置与网络拓扑紧密相关。网络的拓扑结构受到严格控制，文 件或者指向文件的指针位于指定位置，文件i d 与文件存储位置通过分布式路由表进行映 射。 代表如c h o r d 、c a n 。 非结构化p 2 p ： ( 1 ) 节点之间有相互的连接信息，形成无规则的拓扑结构。 ( 2 ) 当对某资源进行请求时，以广播方式寻找，通常会设1 r l ，即使资源存在拓扑中， 也不一定找得到。 代表如o n u t e l l a 。 松散结构化p 2 p ： ( 1 ) 节点之间有相互的连接信息，形成无规则的拓扑结构。 ( 2 ) 当对某资源进行请求时，根据现有信息推测查找，介于结构化p 2 p 和非结构化 p 2 p 之间。 代表如f r e e n e t 。 结构化p 2 p 网络中，由于是有规则的拓扑结构，因此进行查询时不需要发送大量的 查询包，节省带宽，查询速度快，但是当有节点加入和退出时，网络结构的适应性差， 4 浙江工业大学硕士学位论文 难以维护。 非结构化p 2 p 网络中节点的加入和退出十分的简单，不影响整个网络的拓扑，但是 进行查询时则需要发送大量数据包。 松散结构化网络在网络结构的维护和查询性能方面介于前二者之间。 3 p 2 p 网络的优势 p 2 p 网络的一个重要目的便是所有的节点都能够提供资源，包括带宽，存储空间和 计算能力随着节点的加入和对系统请求的增多，系统整体的容量也将增大。这是一个 拥有固定服务器数的c s 结构无法做到的，在c s 结构中，越多的节点加入通常意味着 用户间越慢的数据交换速度。 p 2 p 网络的分布特性也使得它可以通过各种措施来增强冗余和容错能力【l o l ，包括从 多个节点复制数据，导致高度的冗余，在很大程度上提高了信息的可用性。在纯p 2 p 网 络中，能够不依赖中心索引服务器来获得数据。这种情况使得系统不会由于单个节点的 错误导致整个网络的破坏。 i 2 2 p 2 p 的资源定位和获取 p 2 p 网络中的资源定位和获取是指在p 2 p 网络中，各个节点通过一定的策略和算法， 找到自己的所需要的资源，并将其下载下来的过程。因此资源定位和获取是p 2 p 网络面 临的一个主要问题。当前主要有三种资源定位的方式： ( 1 ) 集中索引方式：这种方式主要依靠网络中超节点的存在起作用。当有节点需要某 资源时，将首先将资源请求发送到超节点中，超节点根据保存其中的网络节点资源索引 给出拥有资源的节点并交给请求节点，最后请求节点与该资源节点间建立通信进行下载。 如此，便完成了一次资源的定位和获取。 ( 2 ) 广播方式：该方式主要存在于纯p 2 p 网络中，资源定位时依靠网络中相邻节点的 传递完成，同样，资源获取也需要各中间节点的路由才能完成。 ( 3 ) 分布式哈希表方式( d h t ) ：这是目前普遍被看好的一种资源定位方式。首先， 网络中的节点将被分配一个虚拟地址( v i d ) ，同时用关键字( k e y ) 来表示其可提供的 资源内容。d h t 方式有一个公开的h a s h 函数，可以将k e y 转换成一个h a s h 值h ( k e y ) 。 网络中节点相邻的定义是h a s h 值相邻。当发布资源时，把( 1 江y ，v i d ) 二元组发布到 和h ( k e y ) 相近的节点中去，同样，资源定位时，可以根据h ( k e y ) 到相近的节点 浙江工业大学硕士学位论文 中去查询二元组( k e y ，v i d ) ，并从v i d 中获取资源节点的信息，进行通信和下载。 上述的资源定位方式各有优势和不足，可以根据不同的p 2 p 应用环境进行选择。 1 2 3 无线网络简介 1 概述 继中国成为世界最大的手机消费国之后，笔记本电脑，特别是i n t e l 大力推崇的带无 线模块的迅驰笔记本电脑的大规模普及，使人们的生活越来越越融入到无线网络中去。 可以说，人们的日常生活已经离不开无线网络。每个人的周围都有无线信号的覆盖。 而于此同时，致力于无线网络研究，以使其更好的为人们服务的研究者也越来越多。 2 无线网络的分类1 1 2 】 我们通常所说的无线网络，依据其传播范围可以大致的分为无线局域网、无线个人 局域网、无线城域网、无线广域网四种。以下分别简单介绍四种分类。 ( 1 ) 无线局域m ( w l a n s ) ： 无线局域网使得在一个区域内的用户可以通过接入点访问i n t e m e t ，同时也可以使得 几个用户组成一个i 临时性的局域网络。无线局域网可以在包括大学、图书馆这样大致的 范围内应用。 ( 2 ) 无线个人局域网( w p a n s ) 无线个人局域网的应用范围是四者中最小的，主要针对个人设备之间的连接，因此 称之为个人局域网。目前两个主要的无线个人局域网技术包括红外【1 3 1 ( 舳a ) 和蓝牙【1 4 1 ( i e e e 8 0 2 1 5 ) 技术。它们使得用户在大约3 0 英尺的范围内与个人设备进行连接，对于红 外来说，其连接范围比蓝牙更小，而且连接时需要于使得发射和接受设备在同一直线上。 ( 3 ) 无线城域n ( w m a n s ) - 无线城域网使得城市中建筑之间可以进行无线网络的通信，它可以作为光纤网络的 替代者或备份存在。 ( 4 ) 无线广域网( w w a n s ) ： 无线广域网是四者中应用范围最广的。这种网络使得通信距离在城市与城市或国家 与国家之间。无线广域网的通信依靠卫星或者当地i s p 维护的基站进行。 3 a d h o c 网络【1 5 1 a dh o c 网络是无线局域网络的一种，它是没有有线基础设施支持的移动网络。它最 6 浙江工业大学硕士学位论文 早源于d a r p a 资助的军事项目，用于战场环境下的分组无线网络数据通信。 a dh o e 网络又称为多跳无线网络，在a dh o e 网络中，当两个移动节点之间的距离 较近时，两者可以直接进行通信，而当两节点间的距离较远，无法直接进行通信时，它 们需要位于它们直接的中间节点进行转发，因此需要多跳的路由。在这个过程中，负责 转发报文和寻找路由的中间节点还担负着路由工作。 a d h o e 网络中的节点具有自治性，它们可以迅速的依靠多个节点自身建立起一个移 动通信网络。而且由于网络分布式的特点，某个节点退出或遭到破坏时都不会影响整个 网的正常工作。 a d h o e 的这种特性使之与体现了与p 2 p 类似的思想，它们同样可以不需要固定设施 的支持，所有的节点都可以频繁的加入或退出网络，所以，如何在m a n e t s ( m o b i l e a d h o e n e t s ) & 实施p 2 p 系统，如何在m a n e t s 上提供有质量保证的p 2 p 服务成为一个吸引人 的课题【蚓。 4 8 0 2 11 家族【1 8 1 8 0 2 1 1 标准在上世纪9 0 年代由i e e e 组织提出。至今它已经发展成为无线网络中有 代表性的先进技术之一。 i e e e 8 0 2 1 l 标准定义了单一的m a c 层和多样的物理层，其物理层标准主要有 i e e e 8 0 2 1 l a ，8 0 2 1 l b ，8 0 2 1 1 9 和8 0 2 i n 等。它们之间通过使用频段、调制方式、传输 速率以及支持接口的不同来相互区分。 随着技术的进步，8 0 2 1 1 家族新成员朝着传输速率更快、可靠性更高、安全性更有 保障的方向发展壮大，有朝一日，将可能取代现有的有线局域网。 1 2 4g p 2 p 简介 m p 2 p 网络是一种特殊的p 2 p 网络，它只由一些无线环境中的的移动设备组成。与 有线网络的环境不同，无线网络缺乏固定设施的支持，比如稳定的路由等，这使得m p 2 p 具有一定的特殊性。 m p 2 p 的特点包括： 1 网络拓扑的频繁变更。由于m p 2 p 网络中，随时会有节点的移动或者加入退出， 因此网络拓扑的动态性较强。相对于有线网络相对静态的拓扑形式，m p 2 p 网络的拓扑 变化剧烈和随机。在这种不利的情况下如何较好的布置应用，使得p 2 p 能够较好的在无 线网络中应用是研究中面临的一个关键问题之一。 浙江工业大学硕士学位论文 2 在m y 2 p 网络中，节点由于传输距离的限制，无法一次将数据传送到较远处的节 点，因此同时应该具有路由转发的功能。通常所说的m p 2 p 网络中并没有类似服务器之 类的设施存在，因此与前面p 2 p 分类中的纯p 2 p 系统类似，m p 2 p 系统中的各个节点通 常具有一定的路由功能。保证m p 2 p 网络一定的自治性和完整性。 3 无线信号由于传输介质的原因，抗干扰性不强，传输距离有限，在传输过程中通 常面l f 缶各种障碍物，并且也十分容易受天气等客观因素的影响。相比普通的有线网络， m p 2 p 网络还有剧烈的拓扑变化，这些区别将可能导致移动终端之间通信的高延迟，甚 至不可达。 4 移动终端本身的运算能力、存储能力以及电池续航能力和带宽等都受到限制。移 动设备的运算处理能力通常与其电池的续航能力成反比，即较快的处理器需要较高的能 耗，因此，如何平衡这一矛盾成为移动设备开发者的重要课题。在保证了一定续航能力 的前提下，移动终端的运算能力通常是这矛盾两者妥协的产物。因此，与通常的有线网 络中的计算机相比，移动设备的能力是大大受限的，这也是考虑在无线网络中部署相关 应用的一个重要前提。 综上所述，基于m p 2 p 网络所有的这些特点，目前的许多研究通常都针对它的某一 特性展开，m p 2 p 网络中的研究热点集中在包括路由策略，资源定位，能量消耗等方面 的多个方向上。 本论文把测重点放在建立一个无线网络中的p 2 p 资源定位与获取模型上。在提出较 好的资源定位策略和模型的同时，同时将其与资源的获取模型结合起来考虑，以获得更 好的性能。 1 3研究目标 本文的目标是在对多种m p 2 p 资源定位或者资源获取模型进行比较，分析其优缺点 的基础上，提出一种新的模型，并通过模拟对其进行验证和评估，证明其有效性。 本文主要的工作目标是： 1 在m p 2 p 网络中，资源定位的命中率和时延是衡量一个系统好坏的关键指标之一。 因此本文旨在建立一个资源命中率高、命中时延短的模型。现有的很多模型，都是各有 优势和缺点，至于谁最优并没有一个定论。通常，都是于无线环境的洪泛模型进行比较。 新模型在考察现有模型的基础上，针对它们的不足和缺失的方面，进行了改进，同时保 证了新模型的高命中率和短时延。 浙江工业大学硕士学位论文 2 针对i v l p 2 p 网络中节点分布不均衡的情况，提出有效的解决方案。现有的大部分 无线环境下的p 2 p 模型都没有考虑节点分布不平衡的情况，有的如无线环境下的洪泛模 型，虽然可以在这种情况下正常工作，但是效率低下，命中率低，时延高；有的模型则 根本无法在这种情况下正常工作。因此，新模型针对这种情况，给出了策略，较好的在 分布不平衡的网络中兼顾了命中率和命中时延。 3 针对诸多模型中存在的边界振荡，即节点在临界区域反复来回的情况，提出了解 决方案。在划分区域和拥有索引表的模型中，它们有一个共同面临的情况，即节点在边 界处移动的情况。当这种情况发生时，通常会导致网络中节点发生一系列状态的改变： 区域中节点资源状况的改变、索引表索引范围的扩张和缩小。这些变化将会产生一系列 的开销，包括节点的处理开销、网络流量的开销等不一而足。当这种边界移动情况频繁 时，情况将变得更加恶劣，网络中的大量的开销和网络负载被用来处理这种状态改变的 情形，因此，我们在新模型中提出了解决这一问题的策略。 4 将资源定位与资源获取结合起来考虑：当同一内容有多个提供者时，提供了择优 选择的算法。在网络中，通常不只一个节点拥有同一个资源。这就在资源定位时带来这 样一个问题：当某一资源有不只一个资源提供者时，如何选择提供者。现有的模型有的 在资源定位时没有考虑这一问题，有的不适用于我们的新模型，因此，文中给出我们的 算法，并证明该算法的应用对提高传输的稳定性、容错性有帮助。 5 对结果进行模拟评估并作出相应的分析。在文中，我们使用n s 2 工具，对新模 型进行了模拟和验证。最后，分析了实验的结果，证明新模型在资源定位命中率和时延 以及资源传输稳定性的一定优势。 1 4内容组织 本文的组织结构为： 第一章，绪论，阐述的写作本文的动机，介绍了本文相关的一些技术背景，并给出 了本文的研究目标。 第二章，已有模型的比较分析，根据国内外研究现状，给出诸多已有模型的优缺点 比较和分析。 第三章，整体方案设计与分析，以已有模型的比较分析为基础，提出本文论述的新 模型的整体，并对其进行分析。 第四章，主要流程设计，详细论述我们提出的模型的一些出要处理流程的设计情况。 9 浙江工业大学硕士学位论文 第五章，验证与评估，通过实验获得的数据对新模型进行验证和评估。 第六章，总结和展望，指出本文的不足以及下一步的工作。 1 0 浙江工业大学硕士学位论文 第二章已有模型的比较分析 由于m p 2 p 网络自身的特点，最初应用于有线p 2 p 网络的资源定位模型并不适用与 无线环境当中。因此，许多已有的研究提出了一些新的适用于m p 2 p 网络的资源定位和 获取模型。 2 1 洪泛模型 洪泛模型1 3 1 9 是可以在纯p 2 p 网络中使用的资源定位模型，因为该模型中没有中心 服务器的存在，各个节点之间完全平等，依靠网络中各个节点间的信息交换进行资源定 位。当网络随着节点的加入和退出任意扩展和缩小以及节点动态性较强烈时，其定位策 略依旧可行，因此它能够在m p 2 p 网络中应用，成为重要的m p 2 p 资源定位的参考模型， 许多新的m p 2 p 中的资源定位模型都是根据它改进而来，同时它也是目前能够完全从有 线p 2 p 网络中移植过来的资源定位模型之一。 洪泛模型的原理十分简单。在无线网络中，当某个节点需要某个资源时，此节点将 向它的所有邻居节点发送请求信息，邻居节点受到请求后，与其自身拥有的资源进行比 对，如果没有该资源，则继续向它的所有邻居节点转发该请求，直到请求信息到达资源 所在的节点，或者请求数据报的丁r l 值减为0 。在洪泛机制具体的实现过程中，应该注 意的是要防止在转发请求时，向已经转发过该请求信息的节点再次转发，导致请求环的 产生，吞噬带宽资源，以及进一步的导致资源定位的失败。 洪泛模型的特点是简单易行，需要的数据结构简单，对无线网络中节点能力的要求 较低，适用性较好。但是由于使用广播形式的请求转发机制会占用大量的带宽，在小规 模的网络中可能比较有效，但当网络规模扩大时，则会导致网络带宽的大量消耗，性能 下降严重。而且无线网络本身可用的带宽就十分的有限，因此在一定规模的无线网络中 使用洪泛模型将会遇到性能瓶颈，因此纯粹的使用洪泛机制进行资源定位并不现实。 浙江工业大学硕士学位论文 2 2 动态索引( d y n a m i ci n d e x ) 动态索弓1c 3 1 0 9 1 机制是对传统的索引表( i n d e x t a b l e ) 机制的改进。如前- - d , 节所述， 为了避免洪泛机制带来的大量带宽消耗，无线网络中的节点通过采用i n d e x t a b l e 来保存 节点周围的资源信息，包括在一定的索引半径内所有节点拥有的所有资源的信息等。采 用索引机制是对洪泛模型的显著改进，由于索引表中能够存储节点索引半径内邻居节点 的资源信息，使得节点在进行资源请求时达到减少查询量，减轻网络负荷，提高查询命 中率，减小时延的目的。但是，由于m p 2 p 网络具有的高度动态性，索引半径固定的i n d e x t a b l e 机制使得索引的失效成为一个突出的问题。针对该问题，有相关研究者提出了经过 改进的d y n a m i c i n d e x 模型，如图2 一l 所示。 在d y n , 刮l i t i ci n d e x 模型中，网络中的节点能够根据它自身周围邻居节点的动态性( 即 节点的移动，加入和退出等) 强度，适当的改变自己的索引半径以适应周围环境的变化。 当周围节点动态性较强时，该节点将适当缩小索引半径，以减小索引失效的可能；当周 围节点动态性较弱，即较稳定时，就扩大索引半径，增加搜索的一次命中率。 图2 - 1d y n a m i ci n d e x d y n a l n i c i n d e x 模型的出现，改变了固定索引半径带来的较突出的索引失效的现状。 但是，动态索引的初始索引半径的选择也是一个值得考虑的问题。这个选择将是一个各 方面进行折中的结果。同时，当网络中节点的动态性分布不均时，即在节点的索引半径 1 2 浙江工业大学硕士学位论文 范围内，一部分区域内的节点动态性强，而另一些部分则相对稳定时，将会影响节点对 索引半径的变化作出正确的选择，这也可能导致该模型在应对这种不平衡的动态分布时 无法发挥其应有的性能，或性能的倒退。 d y n a m i ci n d e x 模型的优点是查找速度较洪泛快，带宽消耗少，同时索引表占用的存 储空间相对较少。但是当网络中节点的动态性较强时，则使得节点的索引半径不断缩小， 最终退化为洪泛模型。 2 3p r o o i n o t p r e c i n c t t 2 川( p r o x i m i t yr e g i o n sf o rc a c h i n gi nc o o p e r a t i v em p 2 pn e t w o r k s ) 是一种高 效的m p 2 p 文件共享模型。在资源定位方面，它采用了类似于结构化p 2 p 网络中的 d h t ( 分布式哈希表) 数据结构，能够十分快速高效的完成资源定位。同时，为了减少m p 2 p 网络的负载，p r e c i n c t 模型根据需要修改了普通d h t 中的一些映射( m a p p i i l g ) 方法， 以妥善解决m p 2 p 网络中节点高度动态性的问题。 通常p 2 p 网络中的d h t 具有以下的三个特点： 1 分散性。构成系统的节点没有任何中央服务器的参与，网络中的资源定位完全依 靠节点独立完成。 2 当网络规模扩大，节点大量增加时，系统仍然十分高效。 3 当节点频繁退出或加入时，系统仍然具有一定的可靠性。 由这些特点可见，目前在结构化的有线p 2 p 网络中正广泛被采用的d h t ，在某种程 度上也正符合m p 2 p 网络的一些特性，因此可以作为我们研究的一个基础，我们所做的 部分工作也正是基于这个模型展开。 p r e c i n c t 模型的工作原理可以简单的概况如下： 在p r e c i n c t 模型中，m p 2 p 网络所在区域按地理位置划分成若干个大小相同的区块。 落在每一个区块中的节点负责保存一些k e y 的集合。同时，该模型还需要两个不同的h a s h 函数进行相应的文件k e y 生成和区域位置定位。当一个节点需要在网络中发布文件时， 首先将使用第一个h a s h 函数作用于要发布的文件上，生成一个文件的k e y 值；然后，再 使用第二个h a s h 函数作用于新产生的k e y 值来确定该k e y 应该被发布到的区块；最后， 根据产生的区域位置定位信息，将文件的k e y 值传送到该发布的区块中的节点上去【2 “， 就完成了一次资源的发布过程。 当该模型中进行资源定位时，所用的步骤与上类似，在得到要定位的资源的k e y 值 浙江工业大学硕士学位论文 之后，只要到某一特定的区块中的节点间进行资源的查找即可。 值得注意的是，一个文件通过第一个h a s h 函数产生的k e y 值必须一致，即发布的文 件，或者要查询的文件在经过第一个h a s h 函数处理之后必须得出一个一致的k e y 值。这 样才能保证查询信息被正确的发送到k c y 所在的区块，否则将无法实现正常的资源发布 和定位。 这个模型的优点是在m p 2 p 网络动态性较强的情况下，仍旧能保证网络负载的均衡， 查询速度较快同时它通过采用一系列的c a c h i n g 机制，根据其相应的算法，在转储、 发送资源信息时，将满足适当条件的文件进行备份，减少了第二次查询的时延，提高了 整个模型的效率。 但是该模型由于引入了c a c h i n g 机制圆圆，因此对节点的存储能力有一定要求，同 时。当节点在2 个区块的边界处频繁来回移动时，将可能导致局部地区的节点间网络状 况的恶化，资源定位命中率的急剧下降，该模型对此并没有提出解决办法。还有文章m 】 指出，该模型没有考虑当m p 2 p 网络中某些区域内没有节点的情况，此时，一些需要在 该区域内发布的资源将无法发布出去，同时，在该区域的资源定位也将无法进行。该模 型同样并没有进一步阐述如何进行区域划分的依据。 c a d r e t ”j ( ac o l l a b o r a t i v er e p l i c aa l l o c a t i o na n dd e a l l o c a t i o na p p r o a c hf o rm o b i l e - p 2 p n e t w o r k s ) 模型采用了一系列的协作式资源副本分配和取消方式f 即c a c h i n g ) ，改善了 m p 2 p 网络中资源定位命中率差的情况。该模型对资源定位性能的改善主要是通过在节 点间部署资源副本的形式体现的，为了更好的管理这些资源副本，该模型提出了一系列 的策略，称为协作式资源副本分配和取消方式，来保证资源副本分配和取消的高效、正 确和及时性。 c a d r e 模型主要进行了如下两个方面的工作： 1 采用协作式的资源副本分配和取消方式，提高了在m p 2 p 网络中资源定位的命中 率。同时，采取相应措施来避免系统中出现t r a s h i n g 的状况。t r a s h i n g 是指当网络中有连 续的资源定位请求发生时，由于资源副本的分配和取消策略，导致资源副本的连续重新 分配和取消，引发网络中局部性能的降低，进而影响系统的整体效率。 2 在移动节点间引入公平的副本分配策略。 c a d r e 模型采用了与p r e c i n c t 模型类似的分区域方法，将网络中的节点按照物理 1 4 浙江工业大学硕士学位论文 位置分成若干个大小相等的区域，但是该模型并没有采用d h t 进行资源定位。c a d r e 模型采用了混合式的p 2 p 形式，在区域内引入超级节点负责处理该区域内所有节点的资 源副本的分配。 该模型进行资源定位的过程如下： 当一个节点发出资源定位的请求时，首先由该节点所在区域的超级节点确定该资源 是否在本区域内的节点中，若在本区域，则在本区域内广播查找；若不在，则将资源定 位请求由该超级节点向其邻居区域的超节点转发，邻居区域内的超节点同样采用前面的 方式对资源请求进行广播或查找，直到找到该资源所在的节点为止。 该模型的着眼点在于如何有效的在m p 2 p 网络中引入协作式的c a c h i n g 机制，使得 在高度动态性的m p 2 p 网络中保证一定的资源可获得性( a v a i l a b i l i t y ) 。通过本模型的一系 列机制，c a d r e 模型有效的提高了资源的命中率，缩短了查询的时延。 当然，由于需要频繁的进行资源的复制，该模型也对节点的运算和存储能力提出了 要求，同时，它也同样没有解决如上述p r 七c m t 模型面临的一些问题。 2 5v 州i p 2 p w m f 2 p 1 2 6 1 模型基于加入了i n d e xt a b l e ( 索引表) 机制的洪泛模型