（计算机应用技术专业论文）移动p2p网络中的多维索引技术研究.pdf

浙江大擎硕t 学位论文 摘要 摘要 近年来，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 多维搜索系统都是针对资源相对充裕的有线p 2 p 网络设 计的，所用的查询代价模型不考虑路由路径的物理长度，所以这些系统不具有拓 扑感知属性，不适合资源匮乏的移动无线网络。而且，现存p 2 p 多维搜索系统都 是静态的，无法适应移动p 2 p 网络中节点不断移动的场景。因而，本文的研究工 作致力于设计适合移动p 2 p 网络环境的拓扑感知搜索系统。 为了在移动p 2 p 网络中高效地支持多维搜索，本文提出了创新的移动p 2 p 多 维搜索系统m i m e 。首先，考虑到移动p 2 p 网络受限的通讯环境，m l m e 采用了 新的更为精确的通讯代价模型。m i m e 的通讯代价模型以查询任务所生成的网络 层路由路径的物理长度来估算查询任务的通讯代价。其次，m i m e 引入物理空| 日j 的概念以实现搜索系统的拓扑感知。也就是说，m i m e 用一个二维空间对系统的 物理网络拓扑进行建模并且假设每个节点知道自己的物理地理位置，这样m i m e 能够利用物理网络拓扑信息对数据分配模块和覆盖网组织模块进行优化。最后， 为了适应移动p 2 p 网络的动念特性，m i m e 包含两个适应性特征：更新算法，缓 存机制。更新算法对搜索系统进行动态更新以适应节点移动性；缓存机制的作用 则是减少由更新过程引起的数据迁移通讯开销。实验结果显示相比现存的p 2 p 搜 索系统，m i m e 在点查询范围查询的执行效率上达到了显著的性能提高。 关键词p 2 p ，多维搜索，拓扑感知 浙江大学硕士学位论文 a b s t “i c i a b s t r a c t l i it h ep a s tf e wy c a 略，p 2 pt c c h n o l o g yh a sb l ；e nw i d e l ya p p l j e dj n t 0t h ca r e ao ff i l e s h a r i n g ：ai a r g en u m b c ro fp c o p l eu p 2 p f t w a r e sf o rs h a r i n gm u s i cf i l e s ，v i d e of i l e s ， e t c i ni n t e m e t t h ep o p u l a r i t yo fp 2 pf i l es h a r i n gs v s t e m si sd l i et ot l l ea d v a n t a g e so f p 2 p t e c l i l l o l o g y ，i n c l u d i n g ：s c a l a b i l i t y l o wm a i n t c n a i i c cc o s t ，a i l dr e s o u r c ca g g r e g a t i o n w i t ht h ca d v a n c ei i lm o b i l ew i f c l e s sc o m m u n i c a t i 仰t e c h n o l 0 2 va n dt h ed e v e l o p m e n t o fv a r j o u sm o b i l ed e v j c e s ，p 2 pf j l cs h a r i n 2s v s t c m sh a v eb e e ne v o l v e di nt w oa s p e d s ： t l 他i rn e 觚o r 虹n gc n v i m n m e n ti sc h a n g c df r o mw i r e dp 2 pn e t w o f ki l l t 0m o b i l ep 2 p n e “o r ka n dt h e i rt a s ki sc h a n g c df r o mp r o v i d i n gs i n l p l el o o k u pi n t os u p p o n i n 空 c o m p l e xq u c l j e s t h er c 鲫l t i n ga d v a n c c ds y s t e m sa 化f c 盯e dt o 弱m o b i l ep 2 p m u i t i d i m c n s i o n a ls e a r c hs y s t e m s c b m p a r e dt ow m 。dp 2 pn e t w o r l 【，m o b i l ep 2 p n e t w o r k p r o v j d e s am o r ec o n s t m i n e dc o m m u n i c a t i 鲫c n v i m 姗e n t ， w h i c hi s c h a r a d e r i z e db ym u c hm o r el i m i t e db a n d w i d t h ，h i g t i c rm t eo ft r 锄s m i s s i o ne r r o 塔，l e s s s t a b l ec o n n e c t i o n s 柚dd y n a m i cn e t w o r l 【t o p o l 0 譬mw b r k i n gi ns u c h 粕e n v i r o 姗e n t s e 岫s y s t e m ss h o u l db et o p o l 0 2 v - a w a r e 勰da d a p t i v e t h a ti s t h e ys h o u l dt a k e a d v a n t a g eo ft h ep h y s i c a lt o p o l o g yo ft h en e t w o r l 【t oa c h i e v es h o n e fp h y s i c a ll e n g t ho f q u e r yr o u t j n gp a l ha n da d j u s lt h e m s c l v e st ot h ct o p o l o 斟c h 如g c so ft h cu n d e r l y i n g m o b i l ep 2 pn e t w o r k d e s i g n e df o rw i r c dp 2 pn e t w o r k s ，e x i s t i n gp 2 ps e a f c hs v s t e m s a r en e i t h e rt o p o l o g y a w a r cn o ra d a p t i v c ，s ot h e yw o u l dn o tw o r ke f f i c i e n n yi nm o b i l e p 2 pn e t w o r l 【s t be f c i c i c n t l y 蛐p p o nm u l t i d i m e n s i o n a ls e a r c hi nm o b i l ep 2 pn e t w o r k s ，w e p r o p o s ean o v e ls c h e m ec a l l e dm u l t i d j m e n s j o n a li n d e xi nm o b i l ee n v i r o n m e n t ( j i m e ) f i r s t ，c o n s i d e i i n gt h ec o n s t r a i n e dc o m m u n i c a t i o nc n v i m n m e n tp r o v i d e db v m o b i l ep 2 pn e t 、帕r k s ，m i m ea d o p t san e wc o m m u n i c a t i o nc o s tm o d e l t h i sc o s t m o d e lm e 鹞u 陀st h ec o s to fe x 咖t i n gaq u e r yi l lt e m so ft h ep h v s i c a id i s t a n c co fi t s n e t w o r kl a y c rp a t h ，i n s t e a do ft h en u m b 盯o fi t so v e r l a yh o p s s e n d ，m l m ec a p t u s t h cp b y s i c a lt o p o l o g yo ft h en e l 、v o kj nat w o d i m e n s i o n a lp l a n ca n dl 【e e 口s 职日r d so f t h ep h y s i c a l l o c a t i o n so ft h en o d e si o r d e rt 0c o 璐t n l c tat o p o i o 盯a w a mp 2 p o v e r l a y t h i r d ，m i m ei i i c 0 嘲t e st w 0a d 蜀【p t i v ef c a t u r e s ：柚u p d a t ca l 譬o r i t h mt h a tm a k e s d y n a m i cu p d a t e st ot h eo v 盯l a yw h e nt i i ep h y s i c a ln e t w o r kl a y o u tc h 她g e s ，a n da c h e m e c h 姐i s mt h a tf e d u c c st h el o a do fd a t am i 罩a t i o nd u r i n gt h eu p d a t e st ot h eo v e r l a y e x p e r j m e n tr c s u l t ss h o wt h a tm l m ea c h j e v c ss i 卿j f i c 柚tp c d o 册锄c ci m p r a v e m e n t s i np o i n t 瑚g cq u c r i 鹤c o m p a r e dt ot h ec o n v e n t i o n a ls y s t e m k e y w o r d sp 2 p m u l i i d i m e n s i o n a lq u e 彤t o p o l o g y a w a 陀 浙江大学硕士学位论文 图目录 图目录 图1 1p 2 p 文件共享系统沿着两个不同维度的发展3 图2 1p 2 p 结构与客户一服务器结构的对比7 图2 2p 2 p 系统按照应用领域分类1 1 图3 1m u r k 示例2 0 图4 1 覆盖网与物理网络失配示例2 4 图垂2o 埘系统示例3 1 图4 3 二重空自】划分过程示例一3 3 图4 4 二重空间组织结构示例。3 5 图4 - 5 非拓扑感知索引与拓扑感知索引的对比示例3 5 图4 6 点查询示例。3 7 图4 7 范围查询示例4 0 图4 - 8 更新算法示例。4 4 图4 1 9 缓存机制示例 图5 1 更新算法对点查询的效果5 2 图5 2 更新算法对范围查询的效果5 2 图5 3 循环运动模型下的数据迁移量5 4 图5 4 不同节点个数的点查询性能比较5 5 图5 5 不同节点个数的范围查询性能比较5 5 图5 6 平均邻居节点物理距离5 6 浙江大学硕上学位论文 表目录 表3 1 查询操作示例 表目录 表3 2p 2 p 多维搜索系统。 1 7 1 9 表4 1 传统通讯代价模型与新通讯代价模型2 8 表5 1 实验参数的取值范围和默认取值 表5 2 更新带来的性能提高与数据迁移 5 1 。5 3 浙江大学硕士学位论文 第1 章绪论 第1 章绪论 1 1 课题背景 对等计算( p e e r t o p e e r ，简称p 2 p ) 指以分布式的方式利用分散的资源实 现某种功能的一类系统和应用程序。对等节点( p e 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 系统。按 照应用领域的不同，p 2 p 系统大致可以被分成三类：并行计算、内容和文件管理、 合作。p 2 p 并行计算系统关注的是如何把一个太的计算任务划分成为多个小的子 任务，让这些子任务能在多个独立对等节点并行地运行。这类p 2 p 系统的例子是 s e t i 鲫o m e “1 。为了寻找地球外生命，该系统利用百万台个人计算机的闲置计算能 力来分析外太空收集来的数据。内容和文件管理p 2 p 系统主要关注的是如何在网 络中的各个对等节点上进行信息存储与信息检索。这类p 2 p 系统的例子是允许用 户搜索和下载文件的g n u t e l l a ”。合作性p 2 p 应用程序允许用户进行实h 于地合作 而不需要依赖中心服务器来收集和转发信息。这类p 2 p 系统的例子是即时通讯软 件i c q 。 在上述各种p 2 p 应用领域中，内容和文件管理p 2 p 系统的一个分支p 2 p 文件共享系统是目前被应用得最广泛的一类p 2 p 系统。2 0 0 4 2 0 0 5 年的统计数据 已表示p 2 p 流量已占美国的因特网流量的7 0 9 6 以上。1 。这些p 2 p 网络流量主要是 因特网用户进行文件共享引起的。例如共享音乐文件、视频文件。考虑到p 2 p 文 件共享系统如此巨大的应用需求，对这一领域进行深入的研究和探索是十分有必 要的。 浙江大学硕士学位论文第1 章绪论 在过去几年中，p 2 p 文件共享系统沿着两个不同维度网络环境、系统任 务快速发展着。( 见图卜1 ) 在第一个维度上的发展，即p 2 p 文件共享的工作环境 从p 2 p 网络演进到移动p 2 p 网络的转变是由移动无线通信技术的发展、移动设备 的进步所驱动的。在经历了最初的速度低下、配置困难、可用性差、应用匮乏等 艰难时期之后，移动无线技术进入了快速发展期。首先，在无线技术中历史最悠 久的w i - f i 技术一直处于不断的进步之中。从8 0 2 1 1 a ，发展到8 0 2 1 1 b ，再到 今天的8 0 2 1 1 9 ，w i - f i 技术的传输速率从2 m b p s 逐步提高到了5 4 m b p s “1 。与此 同时，另外一项新兴无线宽带技术w i m a x “1 也在飞速发展。在2 0 0 7 年2 月于西班 牙举行的3 g s m 大会上，三星展示了他们在w i f a ) ( 技术上的新突破，其并i 淞x 张y e 2 使用m i m o 多通道和智能天线技术，下载速率最高可达4 0 l i b p s ，上传速度也有 1 2 m b p s 。这就意味着，使用该网络下载一部7 0 0 船的电影只需不到3 分钟。除了 w i f i 和w i m a x ，蓝牙( b 1 u e t o o t h ) 技术嗍、i r d a 技术“1 等都有新的发展。整个 无线网络技术呈现蓬勃生机。 在移动无线通信技术快速发展的同时，移动设备的功能也日趋强大。一方面 是手机功能的不断强化，另一个方面是p c 电脑的无线化。现在的手机除了原有 的语音和短信服务以外，已经集成了高分辨率镜头、多媒体播放器和p d a 等新的 功能。而p c 电脑也一改自己笨重的特点，变得越来越轻便。近年来各种p d a 、p o c k e t p c 、笔记本电脑的销售量逐年上升，人们正在进入一个移动计算的时代。 因为以上所述的移动无线通信技术的发展与各种移动设备在用户中的日益 普及，近年来无论是在学术领域还是在工业界，p 2 p 计算都开始将研究范围扩展 到与移动设备、无线网络相关的问题。移动p 2 p 这一新兴研究领域由此产生。与 有线网络相比，移动网络环境存在自己的特点，例如高度动态的连接，位簧相关 ( 1 0 c a t i o n d e p e n d e n c y ) ，能量与资源的敏感，无线网络之间的差异等等。这 些特点为移动p 2 p 研究领域提出了新的挑战。我们不能将传统的针对有线网络设 计的p 2 p 文件共享系统直接移植到移动p 2 p 网络中；而是要针对移动p 2 p 网络这 一新环境，对现存的p 2 p 文件共享系统进行适当修改或者重新设计。 在第二个维度上的发展，是p 2 p 文件共享系统从最初只需要支持简单查找 ( 1 0 0 k u p ) 操作发展到后来需要支持各种复杂查询( c o m p l e xq u e r y ) 操作。这 种系统任务的扩展，是因为随着p 2 p 网络上的数据量日益增长，为了让用户能快 速高效地获取所需的数据，在p 2 p 系统中支持复杂查询功能变得越来越有必要， 越来越多的应用程序需要调用复杂查询操作。这些应用程序涵盖数据挖掘、决策 支持、模式识别、以及信息检索等领域。因为传统的p 2 p 文件共享系统都仅支持 2 浙江大学硕士学位论文 第l 章绪论 简单查找操作，本文中称仅支持查找操作的系统为p 2 p 文件共享系统：而把支持 复杂查询操作的系统称为p 2 p 多维搜索系统。由于要提供更强大的查询功能，p 2 p 多维搜索系统比p 2 p 文件共享系统更为复杂。事实上，基本上现存的p 2 p 多维搜 索系统都采用著名的分布式哈希表( 一类p 2 p 文件共享系统) 作为网络路由设施。 图l 一1p 2 p 文件共享系统沿着两个不同维度的发展 由于移动p 2 p 多维搜索系统是p 2 p 文件共享系统沿着以上两个维度发展起来 的，移动p 2 p 多维搜索系统需要面对p 2 p 文件共享系统中不存在的新挑战：适应 移动p 2 p 网络、支持复杂查询操作。到目前为止，数个p 2 p 多维搜索系统已经被 提出，例如s c r a p 、删r k 、s k i p i n d e x 、s q u i d 、z n e t 等。这些系统能够有效地支 持范围查询、k 最近邻查询、相似性查询等复杂查询操作。不过，这些搜索系统 都是工作在有线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 多维搜索系统应该考虑和利用物理网络拓扑信 3 浙江大学硕上学位论文第1 章绪论 息以降低查询请求的路由路径的物理长度。符合这个要求的搜索系统被称为拓扑 感知( t o p 0 1 0 9 y a w a r e ) 搜索系统，拓扑感知的意思是系统没有完全忽视底层物 理网络，而是在不同程度感知和利用物理网络的拓扑信息。因而，本文的动机就 是针对移动p 2 p 网络这一新通讯环境设计与之相适应的拓扑感知多维搜索系统， 这个多维搜索系统能高效地支持复杂查询操作。 1 2 本文的目标 为了设计高效的移动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 搜 索系统设计高效的查询解答机制。 节省网络带宽。移动无线网络环境下的带宽虽然较过去有了大幅度的提高， 但是相比有线网络仍然偏低，如何节省带宽是一个必须考虑的问题。 适应网络的动态性。动态性是移动无线网络的一个重要特征。移动无线网络 的动态性一方面是由移动网络本身的不稳定引起的，另外一方面是作为节点的移 动设备总是处于移动状态引起的。所以，工作在移动p 2 p 环境中的搜索系统必须 能够适应网络环境的高度动态性。 1 3 本文的组织 本文内容按以下方式组织： 第一章，序论。本章对移动p 2 p 多维搜索系统的出现背景进行简要介绍，并 4 浙江大学硕士学位论文第1 章绪论 说明本文的动机和目标。 第二章，移动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 多维搜索系统h i u r k 、 s k i p i n d e x 。我们通过这些讨论和案例研究以掌握p 2 p 多维搜索系统的主要设计 原则，为下一章提出移动p 2 p 网络中的多维搜索系统做准备。 第四章，m i m e 系统的设计和实现。这一章首先给出了m i m e 的研究动机，即 在移动p 2 p 多维搜索系统支持拓扑感知的必要性；接着，提出了创新的移动p 2 p 多维搜索系统埘u l t i d i m e n s i o n a li n d e xi nm o b i l ee n v i r o n m e n t ( m i m e ) ， 并详细介绍了m i m e 系统的设计和实现，包括：m i m e 系统的通讯代价模型、拓扑 感知分布式索引、点查询和范围查询算法、以及对移动网络的适应性特征。 第五章，m i m e 系统的模拟和评估。这一章阐述对m i m e 系统进行的测试和评 估工作，给出m i 托与同类系统的性能比较。 第六章，总结与展望。对本文的工作进行总结，概要地分析m i m e 系统的优 缺点，指出下一步研究工作的方向。 5 浙江大学硕士学位论文第2 章移动p 2 p 研究概述 第2 章移动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 系统的特点和面临的挑战。 2 1p 2 p 技术 为了加深对p 2 p 移动技术的认识，在这一节我们简要介绍移动p 2 p 技术的前 身p 2 p 技术。首先，介绍研究圈中存在的对p 2 p 技术的几种定义；然后，分 析p 2 p 系统需要实现的目标；最后，讨论p 2 p 技术的三个应用领域：并行计算、 内容和文件管理、合作。 2 1 1p 2 p 的定义 在p 2 p 研究圈中存在多种对p 2 p 的定义。h p 实验室的d e j 龃s m i l o j i c i c 等 则认为“p 2 p ”一词指的是以分布式的方式利用分散的资源实现某种功能的一类 系统和应用程序。这里的资源包括计算能力、数据存储能力、数据本身、网络带 宽等。而被实现的功能可以是分布式计算、数据共享、通讯与合作，或者平台服 务。分布式的方式可以指所采用的算法是分布式的，所涉及的数据、原数据是分 布式，或者以上这些都是分布式的；这并不排除p 2 p 系统或应用程序的某些部分 仍然是集中式的【8 l o 英特尔p 2 p 工作组将p 2 p 定义为“通过系统之间直接的交互 共享计算机资源与服务”1 9 】。a b e r d e e n 大学的a l c xw b v t s e l 将p 2 p 定义为“以非 客户端的身份使用因特网外围的设备”l 埘。o r e i l l y 的c l a ys h i r k y 使用下面的定 义：“p 2 p 是利用在因特网边缘可得的各种资源( 存储介质、计算周期、内容、用 户参与) 的一类应用程序。因为获取这些分散的资源意味着p 2 p 节点运行在一个 6 浙江大学硕士学位论文第2 章移动p 2 p 研究概述 网络连接非稳定与口地址不可预测的环境下，所以p 2 p 节点必须独立于d n s 系 统并且具有相当程度或者完全的对中心服务器的自治性。”【1 1 】 本文所借鉴的是h p 实验室所提出的p 2 p 的定义。我们认同对等节点( p c e r ) 的含义是“所有参与节点是平等的”：p 2 p 系统中参与节点同时扮演着客户和服务 器这两种角色。与p 2 p 模式相对的计算模式是集中式和客户一服务器模式( 一台 或少数几台服务器为多个客户节点提供服务的计算模式) 。在图2 1 中，我们对 p 2 p 模式与客户一服务器模式作了简单的对比。p 2 p 概念并不是一个全新的概念。 许多早期分布式系统采用类似的模式，例如u u c p 和交换机网络。一个例子是在 电话网络中，当电话线两端的用户之间建立了连接之后，他们通过这个连接直接 进行交谈。这就是一种p 2 p 模式。 图2 _ 1p 2 p 结构与客户一服务器结构的对比 户 在p 2 p 系统中对等节点是自治的，因为在p 2 p 系统中节点之间不存在完全的 相互控制或者是节点被同一个权威节点控制。节点相互依赖以获得信息、计算资 源、转发请求等等，这种相互依赖对于整个系统的运行和每个参与节点的利益都 是至关重要的。自治性产生的一个效应是，节点不能理所当然地信任其他节点和 完全依靠其他节点的行为，所以p 2 p 系统中的扩展性和冗余问题比传统集中式系 统、其他分布式系统的同类问题显得更为紧要。 2 1 2p 2 p 系统的目标 为了实现满足用户需求的应用程序，p 2 p 系统具有下面这些目标： 7 浙江大学硕士学位论文 第2 章移动p 2 p 研究概述 开销分摊降低 在向大量客户提供服务的集中式系统中，服务器通常承担系统开销的绝大部 分。当这种主要系统开销变得异常的大，p 2 p 体系结构能够帮助系统把开销分摊 到所有对等节点上。举例来说，在文件共享领域，n a p s k r 系统就实现了存储文件 开销在节点间的分摊，n a p s t c r 系统中的中心服务器只维护实现开销分摊需要的目 录结构1 1 2 1 。开销分摊大多是通过利用和聚合一些闲置的资源来实现的( 例如 s 阴 h o m c ) ，这样做不仅降低了系统的净开销，也降低了开销最大的系统组件 的开销。因为对等节点通常是自治的，非常重要的一点是保证公平合理地进行开 销分摊。 资源聚合( 提高性能) 与互操作 分布式方式与资源聚合有一种自然的联系。p 2 p 系统中的每个节点在加入系 统的时候会将某些资源带进系统，例如计算能力或者存储空间。需要大量使用这 些资源的应用程序，例如计算密集模拟或者分布式文件系统，自然会倾向于通过 p 2 p 结构把这些资源聚集起来以解决更大的问题。s 圈 h o m e 、d i s t 曲u t e d n e t 和e n d e a v o f s 是基于p 2 p 结构实现分布式计算系统的最著名的几个例子。通过把 数千个节点的计算资源聚合起来，这些系统能够完成高度计算密集的任务。诸如 n a p s t c r 、g 肌t c l l a 这些文件共享系统也进行资源聚合。在这里，被聚合的资源是 用来存储整个社区的数据集的磁盘空间和用来移动数据的网络带宽。对于聚合分 散在各种平台上的资源，互操作是一个重要的要求。 提高可扩展性可靠性 因为在对等节点之间缺乏一个强的中心权威，提高系统的可扩展性和可靠性 成了又一个重要目标。相应地，在资源发现和搜索领域出现了许多算法上的创新。 这些创新研究工作中，一部分研究工作是为现存系统提出新算法，另外一部分研 究工作是开发新的p 2 p 平台( a n 【“，c h o r d 【埘， p a s t r y l l 5 1 和1 a p e s t f y f l 6 1 ) 。p 2 p 中可扩展性和可靠性的定义遵守传统分布式系统的术语定义。例如，网络带宽方 面的可扩展性包括一个节点能够访问到多少个系统，能够支持多少个系统， 能够支持多少个用户，有多少存储空间可用等等。可靠性则是与系统故障、网络 连接中断、资源可用性这些因素相关。 增加自治性 在很多情况下，分布式系统的用户不愿意依赖任何集中式的服务提供者。他 8 浙江大学硕学位论文第2 章移动p 2 p 研究概述 们更加希望他们所有的数据和工作都在本地被处理。p 2 p 系统支持这种自治性， 因为在p 2 p 系统中本地节点是按照本地用户的命令工作的，不受到其他节点的控 制。典型的例子是各种文件共享系统，例如n a p s t e r l l 2 1 ，g 肌t e l l a 【2 i 和f t c 蛐e t l l 7 l 。 在这些文件共享系统中，用户能够得到因为规章限制不可能出现在中心服务器的 文件。但是，自治地运行各自服务器的个人用户却会把这类文件进行共享，因为 在这样的系统中哪个用户发布了哪些文件是较难被追查到的。 匿名性隐私 与自治性相关的两点是匿名性、隐私。在某些系统中，用户可能不希望任何 人或任何服务提供者知道他的参与。如果系统中存在中心服务器，匿名性就比较 难以保证，因为服务器通常能够辨识客户，至少知道客户的妒地址。通过采用 p 2 p 结构，用户能够避免将自己的信息提供给任何其他人。f r c e n c t 是一个体现p 2 p 应用程序匿名性的著名例子。它所采用的消息转发策略能够保证最初请求服务的 用户不被追踪到。它通过采用概率算法增加匿名性，所以不能通过分析网络通讯 流轻易追踪到服务的起源节点。 动态性 p 2 p 系统假设一个高度动态的计算环境。就是说，诸如计算节点之类的资源 会持续不断地加入和离开系统。当应用程序本身是为高度动态的环境所开发的， 采用p 2 p 方式就非常适合了。即时通讯应用程序中的联系人列表功能是当用户希 望与之交流的人上线时向用户发通知。这个功能就体现了p 2 p 系统对于节点动态 性的支持。而像d i s t 曲u t c d n c t 和s 删 h o m e 这样的分布式计算应用程序也必须 适应不断改变的参与节点集合。当这些分布式计算应用程序在执行一个计算步骤 时，它们必须将计算任务重新分配到其他参与节点以保证工作不会因为一些参与 节点的退出而丢失。 即兴通讯与合作 与动态性相关的是一点是支持即兴通讯与合作。即兴的意思是参与节点基于 它们的当前物理位置或当前兴趣加入或离开某个环境。p 2 p 同样适合这类即兴应 用程序，因为p 2 p 系统本身就已经把参与节点集合的动态变化纳入考虑了。p 2 p 系统通常不依赖已经建立的基础设施，它们会自己构建自己的通讯设施，例如 c a n 、c h o r d 逻辑覆盖网。 9 浙江大学硕十学位论文第2 章移动p 2 p 研究概述 2 1 3 p 2 p 系统分类 p 2 p 系统按照应用领域的不同可以被分成三类：并行计算、内容和文件管理、 合作。( 见图冬2 。) 并行计算 p 2 p 并行计算系统的一个分支是计算密集应用程序，即一个大的计算密集任 务划分成为多个小的子任务，这些子任务能在多个独立对等节点并行地运行。比 较常见的情况是，各个节点并行运行着同样的计算任务，只是使用的参数是不同 的。例子有搜索地球外生命的计算任务、密码破译、投资定价、风险评估、人口 统计学分析等。p 2 p 并行计算系统的另外一个分支构件化应用程序，例如 w b r 姐o w 、j a v a b e a 璐和w 曲s e i c 鹤，目前还没有被公认为p 2 p 系统。不过，将 来可能会出现这样的应用程序：应用程序能由精细的构件组合起来并且这些构件 是能够并行运行的。与在多个对等节点运行相同计算任务的计算密集应用程序不 同，构件化的应用程序在各个节点运行不同的构件。 内容和文件管理 内容和文件管理p 2 p 系统的主要分支是文件共享应用程序，这类应用程序关 注的是如何在网络中的各个对等节点上进行信息存储与信息检索。诸如n a p s t c r 和g n u t c l l a 之类的应用程序允许对等节点搜索和下载其他对等节点发布的文件 ( 主要是音乐文件) 。很大程度上来说，当前这类系统实现并没有致力于提供很 高的可靠性，系统主要依靠用户就从哪个节点获取文件、当下载失败以后是否重 试做出明智的选择。系统重视的是让用户利用原本并没有被利用起来的存储空 间。这些应用程序必须通过采用传统的数据库技术( 例如复制) 来确保可靠性。 在p 2 p 文件系统领域，已经出现了较多的研究项目。我们将在第三章概述这些研 究工作。另一种内容和文件管理应用程序是过滤和挖掘应用程序，例如 0 p e n c o l a i “l 和j r as e a f c h l 。这些应用程序重视的不是信息共享，而是在对 等网络中构建索引的合作过滤技术。类似j 队s e a r c h 这样的技术能和g n u t e l l a 配套使用以实现大型分布式信息平台上更为实时的搜索。 合作 合作性p 2 p 应用程序允许用户进行实时地合作而不需要依赖中心服务器来收 集和转发信息。电子邮件和新闻是两个经典例子。即时通讯软件，例如1 她o o ， 1 0 塑垩查堂堡主兰垡堡奎 星! 兰竺垫! 三! 堕壅塑堕 a i m 和j a b b c r ，在大量用户中流行着阎。共享应用程序允许相隔千里的人们( 例 如商业伙伴) 在同时查看和编辑相同的信息时进行交互。这方面的例子有 b u z z p a d l 2 1 1 和分布式p o w e r p o i i i t 。游戏是另外一类合作性p 2 p 应用程序。p 2 p 游戏是挂载在参与计算机节点上的而且更新操作也是分布在参与计算机节点上 的，不需要中心服务器。例子有q u a z a l 的n e t z ，c e n t e r s p 姐的s c o u re 【c h 锄g c ， d e s c c m 和c y b i k 0 。 图2 - 2p 2 p 系统按照应用领域分类 2 2 移动p 2 p 技术 下面，我们将从三个方面来了解移动p 2 p 技术。首先，我们介绍移动p 2 p 技 术出现的动因移动无线网络的发展；接着，我们分析移动p 2 p 系统不同于有 线p 2 p 系统的特点：最后，我们讨论移动p 2 p 系统面临的各方面挑战。 2 2 。l 移动无线网络的发展 一般来讲，凡是采用无线传输媒体并允许无线节点在一定范围内移动的计算 机网络都可称为移动无线网络。有关移动无线网络的历史起源可能要追溯到很早 以前。大约5 0 年前，第二次世界大战期问，当美国陆军采用无线电波进行数据 传输的时候，军方曾经开发出一种特别的无线电信号传输技术，这种技术相对传 统无线电技术在数据加密方面有了很大的提升，这种技术在战时被美军及其盟军 广泛采用，1 9 7 1 年，部分夏威夷大学的技术人员在这种无线电加密传输技术的基 础上开发出了新的数据包形式的无线电网络数据传输协议，当时将这种技术命名 为a l o h a n e t ，这就是最早的移动无线网络通讯协议的始祖。第一代的移动无线网 络应用为七台采用双向星状拓扑架构连通的电脑搭建而成，这七台电脑分布在夏 威夷群岛中的四个岛屿上，主机站设在瓦胡岛，七台机器可以通过并不成熟的无 1 l 四商 匮蓉r 圈际乡訇磊竺 一计应一 浙江大学硕士学位论文第2 章移动p 2 p 研究概述 线网络协议进行数据传输，这就是移动无线网络的诞生。 在经历了最初的速度低下、配旨困难、可用性差、应用匮乏等艰难时期之后， 移动无线技术进入了快速发展期。首先，在无线技术中历史最悠久的w i f i 技术 一直处于不断的进步之中。从8 0 2 1 1 a ，发展到8 0 2 1 l b ，再到今天的8 0 2 1 l g ， w i f i 技术的传输速率从2 m b p s 逐步提高到了5 4 m b p s 。最新的8 0 2 1 l n 标准正 在孕育中。8 0 2 1 1 n 的数据传输速率将达到1 5 0 6 0 0 m b p s ，这个速度足以流畅地 传输视频和声音信息。除了传输速率的提高，w i f i 技术还将沿着四大趋势发展： 网络配置趋向智能化、网络结构趋向标准化、位置感知趋向精确化和网络漫游趋 向广泛化。与此同时，另外一项新兴无线宽带技术并i m a x 嘲也在飞速发展。轷i j a x 是一种基于标准的技术，可以替代现有的有线和d s l 连接方式，来提供最后一公 里的无线宽带接入。w i m a x 将提供固定、移动、便携形式的无线宽带连接，并最 终能够在不需要直接视距基站的情况下提供移动无线宽带连接。在2 0 0 7 年2 月 于西班牙举行的3 g s m 大会上，三星展示了他们在w i m a x 技术上的新突破，其w i m a x 张v e2 使用m i m o 多通道和智能天线技术，下载速率最高可达4 伽b p s ，上传速度 也有1 2 m b p s 。这就意味着，使用该网络下载一部7 0 0 m b 的电影只需不到3 分钟。 除了w i - f i 和w i m a x ，蓝牙( b 1 u e t o o t h ) 技术、i r d 技术”1 等都有新的发展。 整个无线网络技术呈现蓬勃生机。 2 2 2 移动p 2 p 系统的特点 和传统的p 2 p 系统相比，移动p 2 p 系统是分布在移动无线网络这一新环境中 的，而参与节点一般是各种移动设备。相比有线网络，移动无线网络存在自己的 特点，例如节点的高度动态性、传输带宽有限、连接的不可靠性等等。相比有线 网络的参与节点，移动节点也存在自己的特点，例如较低的计算能力、较小的存 储容量、有限的电能等。以上移动无线网络的特点与移动节点的特点使得工作在 有线网络中的传统p 2 p 系统不能不加修改地部署到移动无线网络环境中，即移动 p 2 p 系统必须包括不同于有线p 2 p 系统的特点。下面我们列举了移动p 2 p 系统的 几个主要特点：