（计算机应用技术专业论文）p2p技术在点云数据处理中的应用.pdf

浙江火学碳l 学位论文 摘要 摘要 p 2 p 技术是目前网络计算研究领域的热点问题之一，其中基于p 2 p 的分布式 计算也同益受到人们的关注。j x t a 技术是一套开放、通用的p 2 p 协议，独立于 编程语言和系统平台，可以作为p 2 p 应用开发的基础设施。逆向工程是一种从 模型对象表面获得的数据点云出发，人工或自动生成一个己存在模型实物替代品 的技术。在处理海量点云时需要频繁进行邻近点求取，这类计算需要耗费大量内 存和c p u 资源。由此，本文提出采用基于p 2 p 的分布式计算来实现海墨点云的 邻近点求取。 本文介绍了p 2 p 技术，对j x t a 技术及其特点作了深入分析；随后对逆向工 程和几种涉及邻近点求取的算法作了简要介绍。本文主要研究了如下两个问题： 一、研究了基于p 2 p 分布式计算平台的设计和实现，主要包括计算平台的 总体框架和组成，各个组成部分之间的关系和通信；采用任务调度器对等组而非 对等体来分发任务以提高整个平台的冗余度，此外对平台的可伸缩性也做了一定 的探讨。 二、研究了如何在上述平台上进行海量点云的邻近点分布求取。计算多个任 务中点云在内存罩的状态，另外还探讨了计算结果的存储。利用测试程序和实际 数据对分布式计算平台进行了测试，最后指出了应用到工程实际中会出现并有待 解决的问题。 关键词：p 2 p ，j x t a ，分布式计算，逆向工程，点云处理 浙江大学硕上学位论文 a b s t r t a b s t r a c t p e e r - t o p e e rt e c h n o l o g yi sc u r r e n t l yo n eo fh o ts p o t si nn e t w o r kc o m p u t i n g ，a n d p 2 p b a s e dd i s t r i b u t e dc o m p u t i n ga l s o h a s b e e nm o r ea n dm o r ep o p u l a r j x t a t e c h n o l o g yi sas e to fo p e n ，g e n e r a l i z e dp 2 pp r o t o c o l s ，c h a r a c t e r i z e da si n d e p e n d e n t o fp r o g r a m m i n gl a n g 嶝a n do p e r a t i n gs y s t e m ，c a nb ear e l i a b l ea n dw i e l d y i n f r a s t r u c t u r ef o rp 2 pa p p l i c a t i o nd e v e l o p m e n t r e v e r s ee n g i n e e r i n gi sat e c h n o l o g y w h i c hg e t sp o i n td a t af r o mt h es u r f a c eo fm o d e lo b j e c ta n dp r o d u c e sa na l t e r n a t i v eo f t h ee x i s t e dm o d e la u t o m a t i c a l l yo rm a n u a l l y a l m o s ta l la l g o r i t h m so fp o i n tc l o u d p r o c e s s i n gr e q u i r ec a r r y i n go u tn e i g h b o rp o i n t ss e e k i n g ，w h i c hi sq u i t em e m o r ya n d c p uc y c l ec o n s u m i n g s ot h ei d e ao fs e e k i n gn e i g h b o rp o i n t st h r o 甥hp 2 p - b a s e d d i s t r i b u t e dc o m p u t i n gi sb r o u g h tf o r w a r d f i r s t l yp e e r t o p e e rt e c h n o l o g yi si n t r o d u c e d ，a n dj x t at e c h n o l o g yi n c l u d i n gi t s h i g h l i g h t si st h o r o u g h l ya n a l y z e d r e v e r s ee n g i n e e r i n ga n ds e v e r a la l g o r i t h m st h a t n e i g h b o rp o i n t ss e e k i n gr e l a t e da r eb r i e f l yi n t r o d u c e d t h er f l a i ni d e ao f t h et h e s i si s ： t h ei n v e s t i g a t i o no fd e s i g na n dp r o t o t y p ei m p l e m e n t a t i o no fp 2 p - b a s e d d i s t r i b u t e d c o m p u t i n gp l a t f o r m i sc a r r i e do u t ，m a l m y i n c l u d i n gt h e o v e r a l l a r c h i t e c t u r ea n dc o m p o n e n t so ft h ep l a t f o r m ，t h er e l a t i o n sa n dc o m m u n i c a t i o n b e t w e e na l lc o m p o n e n t s t a s kd i s p a t c h e rp e e rg r o u pi su s e dt od i s p a t c ht h et a s k s r a t h e rt h a nap e e rf o rt h er e d u n d a n c y ；t h es c a l a b i l i t yo f t h ep l a t f o r mi sa l s od i s c u s s e d n e i g h b o rp o i n t ss e e k i n gi nh 1 娼ea m o u n tp o i n tc l o u dt h r o u g ht h ea b o v ep l a t f o r m i si n v e s t i g a t e d i n c l u d i n gt h a tw h e t h e rp o i n tc l o u ds h o u l ds t a yi nm e m o r yf o rm o r e t h a no n et a s k t h es t o r em e c h a n i s mo fc o m p u t i n gr e s t si sa l s od i s c u s s e d t h e nt h e d i s t r i b u t e dc o m p u t i n gp l a t f o r mi st e s t e dw i t he x a m p l ea p p l i c a t i o na n da c t u a lp o i n t c l o u d f i n a l l y ，t h ep r o b l e m st h a tw i l le n c o u n t e ri ne n g i n e e r i n ga n di m p r o v e m e n t sa r e p o i n t e do u t k e y w o r d s ：p 2 p ，j x t a ，d i s t r i b u t e dc o m p u t i n g ，r e v e r s ee n g i n e e r i n g ，p o i n tc l o u d p r o c e s s 浙江大学硕l 学位论文 第一章绪论 1 1p 2 p 技术简介 第一章绪论 当前互联网的主要技术模式是客户n 务器( c s ) 模型，它的出现旨在替代 大型机系统的传统方案。在大型机方案景，几乎每件事都由大型计算机来处理， 大型机的处理能力很快就成为瓶颈，人们被迫不断升级大型机系统以增加处理能 力。c s 模型把处理的负担转移到客户机。在这个模型里，客户机就是向其它计 算机( 也就是服务器) 请求服务的计算机，服务器则是专注为客户机提供服务的 计算机。通过工作负担的分担，在减少计算资源预算的同时，c s 模型能够提高 整体效率。自上世纪8 0 年代晚期，c s 模型开始被广泛接受。 p 2 p ( p e e r - t o p e e r l l 1 对等网络) 技术是计算机应用技术和网络普及到一定程 度的必然产物“。随着时代的发展，网络环境中的闲置资源不断增加，很多客户 机大部分时涮旱都处于空闲状态，并且拥有大量未使用的磁盘存储空间i 与此同 时，科学计算却呈现出计算密集型的趋势，需要耗费海量的存储和计算资源。人 们希望把一个国家或地区的超级计算机系统整合为一个统一的计算平台，使用户 可以像使用一台单机那样来完成计算密集型任务，2 0 世纪9 0 年代网格计算由此而 兴起，不过其基本模式仍是c s 模型。受网格计算的启发，为了充分利用互联网 边缘资源( 包括存储、c p u 、内容等) ，人们提出了全分布式通信模型为基础的 p 2 p 技术：这样一来就可以有效利用大量个人闲薰资源，并向用户提供各种网络 计算服务。从目前的应用来看，p 2 p 的优势主要体现在大范围的共事和搜索上， 并集中在以下几个方面：分布式计算、协同工作、搜索引擎和文件交换。文件共 享o n g n u t e l l a 、分布式计算女t l s e t i h o m e 等大量方兴未艾的应用充分显示了p 2 p 技术的强大生命力。 p 2 p 是一种分布式系统，如图1 1 所示，其主要特征嘲为：自组织、对称式通 讯和非中心化控制。自组织是指 p 2 p n 络能够在对等体进入、离开和失效时自动 加以调整适应 3 i 。对等体2 _ n 的通讯是对称的，它们既请求又提供服务。非中心 化控制即p 2 p 网络没有集中的目录或控制点，对等体自主进行控制。在p 2 p 系统 浙江大学倾1 1 学位论文 第一章绪论 里【，计算机能够同时扮演客户机和服务器的角色，它在某个任务里的角色取决 于其发挥的作用。该方案使服务器的工作负荷最小化，同时又能最大限度的剥用 整个网络的性能。p 2 p 分布计算允许用户使用网络中聚集起来的处理能力，完成 大量以前无法开展的超大计算量作业。此p h p 2 p 应用具有良好的性价比，系统里 的所有参与者皆可受益，成本更低处理速度更快。 对等体 纯p 2 p 模型 客户机 图1 - 1p 2 p 和c s 模型 1 2 逆向工程和点云处理 c s 模型 计算机辅助设计( c a d ) 是蠼重要的计算机应用领域之一。随着计算机技 术的不断发展，c a d 技术的发展和应用水平己成为衡量一个国家科技现代化和 工业现代化的重要标志之一i5 1 。c a d 可以有效提高设计的速度与质量，从而产生 显著的经济效益。如果使用计算枫集成处理设计、制作、工艺处理、管理等多个 步骤，则整个产品的生产效率和质量可获极大改善。c a d 技术起步予2 0 世纪5 0 年代后期，先后经历了二维绘图、线框造型、曲面造型、实体造型、参数化设计 等几个发展阶段。经过4 0 多年的发展，传统的c a d 技术已渐趋成熟，并且在制 造业和其它行业获得广泛应用1 6 j 。 逆向工程( r e ) 是近年来发展迅速的一门技术m ，是c a d 领域的重要分支 之一。它研究从已有物理实体创建其c a d 模型的方法，以提取已有零件和模型 的设计思想、或者对已有零件进行二次设计：逆向工程可以简单定义为“理解原 浙江大学硕j 。学位论文 第一章绻论 始的设计意图和机制”，包括形状、材料、工艺等诸多方面。目前有关逆向工程 的研究和应用大多数针对实物模型的几何形状的反求，在这个意义下，逆向工程 是根据已有实物模型的坐标测量数据，重新建立实物的数字化模型，而后进行分 析、加工等处理。这里的实物模型可以是机械产品、人体、动植物、艺术品、地 形地貌等等 8 母l 。通过实物模型产生其数字化模型，可以充分利用数字化的优势， 提高设计、制造、分析的质量和效率，并适应智能化、集成化、并行化、网络化 的产品设计制造过程中的信息存储与交换。逆向工程将现代坐标测量设备作为产 品设计的前置输入装置和原型或产品制造后的检测手段，与快速原型制造 ( r p m ) 、计算机辅助设计与制造( c a d c a m ) 相结合并形成产品设计制造的 闭环系统，将有效提高产品的快速响应能力，丰富几何造型方法和产品设计手段， 其关键技术可用于其他许多领域，从而拓宽计算机辅助建模的应用。 图1 - 2 逆向工程实施原理简图 逆向工程并不限于样件复制，其目标是实现一种智能化的三维扫描识别重建 系统。三维扫描识别系统不仅要获得物体的基本数据，而且要对数据进行必要的 处理，建立相应的计算机模型，允许对该模型的体积和面积等物理特性计舅避行 分析、修改等等1 0 】。据统计，各国百分之七十以上的技术源于国外，逆向工程 作为掌握技术的种手段，可使产品研制周期缩短百分之四十以上，极大提高生 产率。 浙江人学顺 j 学位论文 第一章绪论 一一 输入 输出 点云数据卜叫畜嘉攀嚣婷特征线提取卜叫三维c a d 模型i 网格数据k 1压特征面提取l| _ 1 网格数据优化少 图1 3r e 系统产品建横流程国 在逆向工程中，首先对实物样件或者由造型师用木材、油土造型的产品模型 进行数字化，然后对获得的点云数据使用专门的曲面造型和c a d 系统重构出实 物的c a d 模型，上述过程如图1 3 所示，最后利用输出的n c 加工指令驱动c n c 或 者用s t l 文件驱动快速成型机制造生产品或者原型。逆向工程的主要目的在于消 化、吸收和提高先进技术，减少产品的研发时间。在一些工业领域如汽车制造业， 许多零件的几何模型都通过逆向工程由油泥模型或实物零件获得【j “。 目前常用的点云数据测绘方法可分为接触式与非接触式数据扫描两大类。接 触式扫描方法得到的数据点精度较高，但其速度较慢，测量数据点较少，测量具 有复杂型面的自由曲面非常困难。菲接触式方法速度较快，粼量数据点多，其中 激光扫描仪每秒可产生数十万个数据点，能清楚地表达物体表面细节，非常适合 于自由曲面扫描，在工业领域己得到越来越广泛的应用【1 3 】。 随着激光扫描设备技术的不断提高，激光扫描仪的数据采集速度和密度不断 提高，需要处理的点云数据量也将随之增大。虽然激光扫描仪能够获得非常密集 的点云，但并不是所有点云数据都能用于曲面重构，过多的数据点会导致计算机 运行、存储和操作的低效率，生成曲面模型需要消耗更多的时间；并且过于密集 的点云会影响重构曲面的光顺性。为避免上述问题，就需要删除部分数据点。即 对数据点云进行精简处理。经过精简处理后点云数据萋可能仍然非常大，严重影 响曲面模型的生成速度。在上述两个步骤中，如何进行快速有效的点云数据处理 是工程实践中必须解决的问题。 浙江大学坝h 学位论立 第一章绪论 在各种点云数据处理算法中，邻近点求取是必不可少的一步，如计算曲率、 曲面法线、点云精简等都必须先求取邻近点。所谓邻近点求取，就是要在几十上 百万的点云中找出和某点距离最近的k 点。当进行大量点的邻近点求取时，通常 要耗费大量的内存和计算时间，如果耗时过长则无法付诸实际应用，那么利用现 有计算机硬件资源，在不增加硬件投资的前提下，如何提高点云尤其是海量点云 中邻近点求取的速度? 面对现在完善的网络环境和局域网内大量的闲置资源，利 用p 2 p 进行灵活的分布式计算成为一个可行的解决方案。 1 3 实现技术选择 j x t a 1 4 1 是由s u n 公司提出的一个开放、通用的p 2 p 协议，旨在成为构建p 2 p 应用的公共平台，它是一个与编程语言和系统平台无关的规范，使用易于实现和 集成p 2 p 服务和应用的协议。经过五年多的发展，j x t a 愈加稳定和高效，其j a v a 和c 语言参考实现日渐成熟。基于j x t a 的网格计算和分布式计算的项目也层出 不穷，如p 2 p 网格计算项目x e e r k “列、p 2 p 分布式计算平台j n g i 【l q 等，上述项 目都表明j x t a 可以很好的使用分布式计算。利用j x t a 可以有效实现一些关键 的p 2 p 概念： 发现：无霈借助中心服务器，p c 就能动态发现其它p c 和作业，有主机加入 或退出时不会影响计算的进行。 对等组：大量p c 可以分组成作业对等组，如图1 - 4 所示，在对等组里计算机 可以进行代码发布、作业控制，以及分布式计算时的组通信。 中继：支持穿越n a t 和防火墙的端到端通讯，并实现以消息传递模型为基础 的分布式并行处理。本文主要集中在局域网内实现p 2 p 分布式计算，因此该 功能可有可无，不过为今后的扩展性提供了可能。 此外鉴于j a v a 本身特性，如跨平台、快速开发能力等，本文选用j x t a - j s e 版本进行分布式计算平台的设计和原型系统的实现a 采用j x t a - j s e 版本时，由 于j a v a 虚拟机的存在，和j x t a - c 版本的实现相比，必然存在效率上的差距。 不过，目的就通讯层的效率而言，j x t a c 版本仍不如j x t a - j s e 版本【1 7 】，不过 浙江火学坝l 学位论文第章绪论 相信今后会得以不断的改进和完善，如果工程实际中决定采用j x t a 实现分布式 计算平台，可以考虑选择j x t a c 版本。或者采用j n i 技术以本地代码实现那些 资源耗费极大的执行程序。 图1 - 4 利用对等组进行分布计算 1 4 本文主要研究内容 逆向工程是一种从模型对象表面获得的数据点云出发，人工或自动生成一个 已存在模型实物的替代品的技术。点云处理在逆向工程中占有极其重要的地位， 而邻近点如七近邻的求取又是点云处理中不可或缺的一步。这类计算通常需要 耗费大量的内存和c p u 资源，遇到海量点云数据时情况尤其糟糕。由此本文提 出了用基于p 2 p 的分布式计算来实现海量点云的邻近点求取a 利用p 2 p 分布式计算来求取邻近点，首先必须搭建分布式计算平台a 本文 论述的重点集中于浚分布式计算平台的设计与实现，以及在该平台上邻近点求取 的实现过程。本文主要研究内容及创新如下： 浙江大学硕上学位论文第一章缝论 1 研究了基于p 2 p 分布式计算平台的设计和实现，主要包括计算平台的总 体框架和组成，各个组成部分之间的关系和通信；采用任务调度器对等 组而非对等体来分发任务以提高整个平台的冗余度，此外对平台的可伸 缩性也做了一定的探讨。 2 研究了如何在上述平台上进行海量点云的邻近点分布求取，计算多个任 务中点云在内存罩的状态，另外还探讨了计算结果的存储。利用测试程 序和实际数据对分布式计算平台进行了测试，最后指出了应用到工程实 际中会出现并有待解决的问题。 1 5 本文组织结构 本文在结构上共分五章，各章内容具体如下 第一章对p 2 p 技术和逆向工程概念作了简要介绍，还论及点云处理在逆向 工程中的重要性。提出了利用p 2 p 分布式计算来求取邻近点，并选用j x t a 作为 实现技术，最后列出了本文主要研究内容。 第二章描述了p 2 p 技术的发展和p 2 p 应用的分类，及其现状和未来，并分 析了p 2 p 的关键技术。对j x t a 基本概念和核心的六个协议做了深入探讨a 第三章论述了点云数据处理技术，包括点云的概念，点云的获取和处理，还 详细介绍了特征点云带的计算，以此说明邻近点求取在点云处理中的重要性。 羹四章，针对海量数据点云的邻近点求取，提出了一个基于p 2 p 的分布式 计算平台，重点研究了该平台的设计和原型实现，平台的组成及各组成之间的关 系。并在这个平台上进行了邻近点求取的分布式计算。 第五章对本文的工作进行了总结，并指出了存在的问题及今后工作展望。 浙江人学硕t 1 学位论立 第兰章点云数据处理技术 一- 一 第二章p 2 p 和j x t a 技术 p 2 p 被许多人视为2 1 世纪的技术热点之一。p 2 p 计算是指不同系统之间通 过直接交换，达成计算机资源和服务共事、进行信恩处理的过程，这里的资源可 以是处理器时钟、缓存和磁盘空间等。p 2 p 模式与传统c s 模式的关键区别在于 p e e r 与p e e r 之间可以完全摒弃服务器，通过直接通信获得资源或服务，实际上 这就是i m e r n e t 最初的设计目标，只是后来由于网络规模的扩大，c s 模式才逐 渐成为互联网上占统治地位的计算模型。从这个角度看，p 2 p 计算可以说是一种 “向传统的回归”。尽管p 2 p 这个术语最近刊出现，但p 2 p 并非一种全新的技术， 早在2 0 世纪7 0 年代就已出现，典型代表是u s e n e t 和f i d o n e t 这两个分散分 布的信息交换系统，p 2 p 技术真正大规模的应用肇始予文件交换软件n a p s t e r i t s 】。 目前p 2 p 还投有一个统一的定义。i n t e l 将p 2 p 计算定义为“通过系统间的 直接交换所达成的计算机资源与信息的共享”，这些资源与服务包括信息交换、 处理器时钟、缓存和磁盘空可等，称其为第三代网络革命的“点对点分散式网络 架构”。i b m 则给p 2 p 赋予更广泛的定义，把它看成是由若干互联协作的计算机 构成的系统，并具备如下若于特性之一：系统依存于边缘化( 非中央式服务器) 设备的主动协作，每个成员直接从其它成员而非服务器的参与中受益；系统中成 员同时扮演服务器和客户的凫色；系统应用的用户能够意识到彼此的存在构成一 个虚拟或实际的群体。就总体而言，p 2 p 计算系统是分布式的，有别于集中式和 基于服务器的结构，在对等网络中每个节点的地位都是相同的。纯p 2 p 计算系 统无需服务器，其中的实体一般同时扮演客户和服务器两种角色。 2 1p 2 p 系统分类 按网络拓扑结构，p 2 p 系统可分为纯p 2 p 系统和混杂型p 2 p 系统，如圈2 - 1 所示。在纯p 2 p 系统中，没有服务器的概念，每个对等体都具有同等责任和地 位，不存在中间节点的协调，f r e e n e l 、g n u t e l l a 都属此类。纯p 2 p 系统克服了 c s 模式中服务器单点夫效和瓶颈等问题，但一个节点的搜索请求要经过整个网 络或至少一个很大的范围才。能得到结果，占用大量带宽，并且可能耗时很长。混 络或至少一个很大的范围才能得到结果，占用大量带宽，并且可能耗时很长。混 一0 一 浙江火学颂f + 学位论义 第三章点云数据处理技术 第二章p 2 p 和j x t a 技术 p 2 p 被许多人视为2 1 世纪的技术热点之。p 2 p 计算是指不同系统之间通 过直接交换，达成计算机资源和服务共享、进行信息处理的过程，这里的资源可 以是处理器时钟、缓存和磁盘空间等。p 2 p 模式与传统c i s 模式的关键区别在于 p e e r 与p e e r 之l 训可以完全摒弃服务器，通过直接通信获得资源或服务，实际上 这就是i n t e m e t 最初的设计目标，只是后来由于网络规模的扩大，c i s 模式才逐 渐成为互联网上占统治地位的计算模型。从这个角度看，p 2 p 计算可以说是一种 “向传统的回归”。尽管p 2 p 这个术语最近才出现，但p 2 p 并非一种全新的技术， 早在2 0 世纪7 0 年代就已出现，典型代表是u s e n e t 和f i d o n e t 这两个分散分 布的信息交换系统，p 2 p 技术真正大规模的应用肇始于文件交换软件n a p s t e r 1 8 1 。 目前p 2 p 还没有一个统一的定义。i n t e l 将p 2 p 计算定义为“通过系统间的 壹接交换所达成的计算机资源与信息的共享”，这些资源与服务包括信息交换、 处理器时钟、缓存和磁盘空间等，称其为第三代网络革命的“点对点分散式网络 架构”。i b m 则给p 2 p 赋予更广泛的定义，把它看成是出若干互联协作的计算机 构成的系统，并具备如下若干特性之一：系统依存于边缘化( 非中央式服务器) 设备的主动协作，每个成员直接从其它成员而非服务器的参与中受益；系统中成 员同时扮演服务器和客户的角色；系统应用的用户能够意识到彼此的存在构成一 个虚拟或实际的群体。就总体而言，p 2 p 计算系统是分布式的，有别于集中式和 基于服务器的结构，在对等网络中每个节点的地位都是相同的。纯p 2 p 计算系 统无需服务器，其中的实体一般同时扮演客户和服务器两种角色。 2 1p 2 p 系统分类 按网络拓扑结构，p 2 p 系统可分为纯p 2 p 系统和混杂型p 2 p 系统，如图2 一l 所示。在纯p 2 p 系统中，没有服务器的概念，每个对等体都具有同等责任和地 位，不存在中f 刚节点的协调，f r e e n e t 、o n u t e l l a 都属此类a 纯p 2 p 系统克服了 c s 模式中服务器单点失效和瓶颈等问题，但一个节点的搜索请求要经过整个网 络或至少一个很大的范围才能得到结果，占用大量带宽，并且可能耗时很长。混 一8 一 浙江大学倾l 。学位论义 第三章点云数据处理技术 杂型p 2 p 系统将分布式系统与集中式系统相结合，由位于网络中的服务器搜集 相关信息，作为索引节点，负责记录共享信息以及回答对这些信息的查询，但该 服务器并不充当整个系统的核心，而共享资源则分布在各个节点上。对等体节点 先向服务器发出请求，获得相关对等体的地址信息，之后信息交换仍发生在两个 对等节点之间。n a p s t e r 系统就是这类系统的典型代表。 纯p 2 p 拓扑结构混杂型p 2 p 拓扑结构 图2 - ip 2 p 系统拓扑分类 n 对等体 囤脑器 。y 吣查询 、i 应替 f 载 按系统中用户的行为方式，p 2 p 系统可以分为多对多、少对少和少对多三种 结构。第一种结构的系统操作双方用户人数基本相当，基于因特网的开放式文件 共享系统多数属于此类，如g n u t e l l a 、f r e e n e t 、n a p s t e r 等；第二种结构的系统是 封闭的，即系统的发起者构建一个系统，不允许他人加入，在系统运行期间，所 有参与者地位均等：第三种系统属于典型的开放式分布计算系统，系统中存在少 量的中央服务器，为多数用户所使用。 按成员标识管理方式，p 2 p 计算系统可分为集中式和局部式。前者是最直接 又比较普通的方式，它创建一个全局的名字空间，保证所有实体的名字都是惟一 的：后者既不需要集中式授权机制，也无需求助于分层结构，很自然地采用了公 共密钥加密机制。 按实体发现方式的不同，p 2 p 系统可以分为直接和间接方式。其中直接方式 比较简单，即利用广播或多播形式发出查询请求，符合查询要求的对等节点进行 新江大学硕士学位论史 第三章点云数据处理技术 应答，然后建立直接的通信连接。这种方式只能在局域网中使用，应用范围有限， 不过结合其它方式使用可以取得良好的查询效率。间接方式又包括三种模型：服 务器模型、洪流模型和路由模型。服务器模型基于混杂型p 2 p 拓扑结构，充当 服务器的对等节点提供资源查询存在单点失败的可能。洪流模型基于纯p 2 p 拓扑结构，对等节点采用洪流法将查询请求不断转发给邻居节点，直到到达目标 节点，获得查询结果。路由模型也是基于纯p 2 p 网络结构，首先它为网络中每 个对等体赋予一个i d ，同时每个对等体存储的资源和服务也有类似i d 。对等节 点的路由表中登记一定数量的邻居节点。对等体的请求被转发给与所请求资源或 服务i d 最接近的对等体，直到发现这个资源或服务。计算系统可分为客户服务 器模型、直接模型和中介模型。第一种模型中，可访问实体的发现需求助于特定 的集中式服务器；第二种模型中，系统每个实体负责自身的标识动能，以傈证能 被其它实体发现；第三种模型最常见，核心实现方法是请求转发。 2 2p 2 p 应用领域 随着n a p s t e r 1 9 】、g n u t e l l a 2 。1 以及i c q 等p 2 p 系统的出现，p 2 p 的技术优势 及其在未来网络中的应用价值逐渐体现出来，并在工业界和学术界受蚕高度韵重 视。p 2 p 系统的每个对等体都是平等的参与者，扮演服务使用者和服务提供者两 种角色，资源的所有权和控制权被分散到网络的每个节点中。服务傻用者和嘏务 提供者之间进行直接通信，可以充分利用网络带宽减少网络的拥塞状况，使得舞 源的有效利用率大大提高。同时出于没有中央节点的集中控制，系统的伸缩性较 强，可避免单点故障，提高系统的容错性能。但由于p 2 p 网络的分散性、自治 性、动态性等特点，造成某些情况下对等体的访问结果不可预见，倒如一个请求 可能在转发过程中被丢弃从而得不到任何应答消息。p 2 p 系统的这些特点决定了 p 2 p 应用主要集中在以下几个方面： 2 , 2 1 资源共享 作为网络系统，“共享”永远是最基本的目标，包括文件、c p u 时钟、应用 服务等，箕中尤以文件共享最为常见。在传统的w e b 方式中，要实现文件交抉 浙江大学颂i ：学位论文 第三章点孟数据处理技术 需要服务器的参与，通过将文件上传到某个特定的网站，用户再至0 某个网站搜索 并下载需要的文件，而基于p 2 p ，文件共享有两种基本方式：基于目录服务的文 件共享和对等式文件共享。前者的典型例子是n a p s t e r ，用户在一个目录服务器 中注册文件条目，搜索通过查询该服务器进行，以寻找一个匹配的文件拷贝。文 件操作在成员之间直接进行，这种混杂型p 2 p 计算系统结构如图2 2 所示。在对 等式文件共享系统中，用户通过系统网络邻居来注册文件，通过网络来搜索文件 拷贝，不需要集中式目录服务器，典型例子是f r e e n e t 。 图2 - 2 混杂型p 2 p 系统结构 以c p u 时钟共享为目标的p 2 p 系统也不少，如s e t i h o m e 、d i s t r i b u t e d n e t 等。大致实现方式为：系统某个成员要运行一个计算任务，就在系统中发布该任 务，其它成员如果认为自身c p u 足够空闲就与该成员联系，下载并执行计算代 码，最后把结果返回给该成员。在这一过程中，执行任务的成员可根据自身负载 变化主动中止或迁移计算任务。基于p 2 p 技术豹分布计算可以把网络中丈量计 算机闲置的计算能力如处理器、存储器等积聚起来，完成超级计算机的任务，可 应用在天气预报、动画制作、基因组研究等领域中。p 2 p 技术使得这些需要进彳亍 海量数据处理或计算的行业受益匪浅。 2 2 2 协同工作 协同工作包括一系列p 2 p 程序，其目的是让分布在不同地点的人能够通过 互联网进行实时协作。例如在一个工作组中，协同工作包括想法和资源的共享， 而这种共享是通过交互式通信进行的。为了实现项目合作，项目组成璺彼此间可 能需要交换信息和文档资料。信息的交换可以通过e - m a i l 、电话或是即时通信软 浙江 学顺l 学位论义 第三章点云数据处理挫术 件实现。在会议中，使用一个双方可共用的虚拟白板与远程合作者进行交流是一 种非常及时有效方法。自板就相当于在通信双方面前的信息“黑板”，任何一方 在上面进行文字输入或者是图形绘制，双方都可同时看到。在此过程中，文档可 以由某一方单独起草并共享，或者是由多方联合起草，但无论采用哪种起草方式， p 2 p 技术都可以使得文档能实时进行共享，并且不依赖中央服务器的存在。 2 , 2 3 搜索引擎 基于p 2 p 技术搜索文档的深度要大于传统目录式搜索引擎的深度。以 g n u t e l l a 系统进行的搜索为例：一台p c 上的g n u t e l l a 软件可将用户的搜索请求 同时发给网络上另外1 0 台p c ，如果搜索请求末得到满足，这l o 台p c 中的每 一台都会把该搜索请求转发给另外1 0 台p c ，这样，搜索范围将在几秒钟内以几 何级数增长，几分钟内就可搜遍几百万台p c 上的信息资源。 2 , 3 p 2 p 关键技术 p 2 p 是一种基于互联网环境的新的应用型技术，主要为软件技术【2 “。p 2 p 技 术拥有许多传统c s 模型所不具备的优势，丽它们离不开p 2 p 关键技术的支撑。 1 拓扑一致性和资源定位。面对互联网上数量庞大的计算机，和其它应用 相比，p 2 p 应用需要更多考虑那些低端p c 的互联问题，它们不具备服务器那么 强大的联网能力。同时和过去相比，现在的硬件环境更为复杂，这样在通信基础 方面，p 2 p 必须提供在现有硬件逻辑和底层通信协议上的端到端定位( 寻址) 和 握手技术，建立稳定的连接。与此相关的技术包括i p 地址解析、路由以及n a t 和防火墙的穿越。p 2 p 系统需要解决的另一个重要问题是：在一个没有中央服务 器的动态环境下，备个节点怎样维持致的网络拓扑信息。p 2 p 网络中节点的加 入和离丌非常频繁，因此传统路由扩散的方法难以解决这一闯题，所以需要一个 高效的一致性信息维护机制。例如，当网络拓扑变化时快速恢复网络的稳定性问 题需要解决，但多个节点的并发加入和离开使得这一问题的解决更具挑战牲。另 外，用户从大量分散的节点中找到需要的资源和服务也是一大挑战，这涉及资源 和服务如何标识，进行资源查找时如何定位对等体。 浙江大学坝1 1 学位论文 第三章点云数据处理技术 2 安全机制。p 2 p 中的安全问题直接决定了p 2 p 能否进行大规模商用，与 安全问题有紧密关系的是p 2 p 平台具有的匿名性，如f r e e n e t 可以通过隐藏路径 和身份欺骗的方法达到服务提供者匿名的目的。p 2 p 系统所具有的匿名性等特性 可能会带来t y u 安全隐患：担绝服务攻击、恶意软件分发和信息泄漏或篡改等。 3 性能指标。p 2 p 系统的性能指标包括请求相应时间、公平性等。其中请 求相应时间与p 2 p 系统的拓扑结构有很大关系，如何快速有效的定位对等体、 查找资源的同时不浪费带宽等问题亟待解决。p 2 p 体系结构会导致“无政府主义” 行为的出现，如过量下载或有意让下载的文件中包含广告等，这些行为导致p 2 p 信息交换的不公平性。 4 互操作性。涉及数据描述和交换的协议。在应用层面上，如果两个对等 体分别代表两家不同的公司，而且它们已经通过互联网建立连接，那么一方的信 息就必须为另一方所识别，所以当| i i 关于数据描述和交换的协议，如x m l 、s o a p 和u d d i 等都是一个完整可用的p 2 p 软件所应考虑的。 5 q o s 问题。p 2 p 网络的q o s 问题包括两个方面：信息获取的q o s 问题， 用户需要的信息可能同时存放在多个节点上，如何选择一个处理能力强、负载轻、 带宽高的节点需要用户考虑。用户可能共享无用或者违法信息，造成信息垃圾 充斥网络，因此网络应该控制用户共享的信息，提高用户获得有用信息的效率。 2 4j x t a 技术分析 丌源项目j x t a 肇始于2 0 0 0 年夏天，是由s u n 公司组织开发的一个开放通 用的p 2 p 计算平台，旨在解决技术与商业上的几个难题。首先是要解决众多p 2 p 系统互不相通的问题。只有互通才能真正发挥出p 2 p 的优势，正如即时通信工 具那样，能互连的人越多则越有价值。因此s u n 公司决定开发一个通用平台。为 p 2 p 应用提供基础设施，使所有p 2 p 系统都能连接起来。其次，j x t a 试图寻找 一套数量最少、概念最简单的系统构成的“积木”使之成为今后入们构架信息系 统的基本模块i 从而帮助人们摆脱像w i n d o w s 或t c p f l p 带来的包袱。j x t a 是 j u x t a p o s e 的缩写，既表现了p 2 p 或肩并肩的意义，又表明j x t a 不局限于p 2 p e 一1 3 浙江火学硕二l 学位论文 第三章点云数据处理技术 j x t a 由系列网络协议构成的，独立于编程语言、操作系统和网络传输技术。 j x t a 技术提供了基础性的机制柬解决当前分布计算应用中面临的问题，实 现新一代统一、安全、互操作以及异构的应用。目前它已有j 2 s e 、j 2 m e 和c 语言参考实现。j x t a 通过j a v a 技术和x m l 数据表达的结合，提供了强大的功 能使得垂直应用得以交互，并且可以克服目前p 2 p 软件的限制。同时，通过小 型、简单、便于开发的构造模块，j x t a 将使开发者从建立框架的复杂工作中解 放出来，可以潜心构建各种创造性的分布式计算应用。 2 4 1j x t a 设计目标 首先，j x t a 是为了构建p 2 p 网络而制订的一组协议，关注机制而非策略， 因此应用开发人员有最大的自由度开发和编写具有竞争力的解决方案。j x t a 旨 在解决构建p 2 p 网络时所遇到的问题，j x t a 标准协议规范介绍如下：j x t a 由 六个协议组成，这些协议专为特定的、分御式的、对等的网络计算而设计。使用 这些协议，对等体可以互相合作建立自组织、自治的对等组，丽不必关一心它们在 网络中所处的位置( 在网络边缘或防火墙后面) ，并且也不需要集中的管理机构。 j x t a 的核心是六个协议，是p 2 p 应用程序开发的运行平台。x t a 有如下 几个设计目标：互操作性，可跨越不同p 2 p 系统和群落；平台独立性，独 立于各种语言、操作系统和网络协议；渗透性，渗透到所有数字化设备，为 p 2 p 应用提供服务和基础。本质上讲，j x t a 的目标是希望任何设备，从台式机 到p d a 、汽车、洗衣机等都可以支持p 2 p 。这里有几个概念上的目标，包括： 使用对等组来组织对等体并且在组内提供服务和应用的环境；组可以使用认证和 验证方式来控制组的访问权限；通过网络来发布对等体和网络资源的信息 通过 系统来发御各种请求；提供个基础平台，供对等体之间做路由和通信，以及穿 越防火墙或其它障碍；提供一种机制允许对等体之间能彼此监视状态和资源。 2 4 2j x t a 层次结构 j x t a 软件架构分为三层【2 2 1 ，分别是平台层、服务层和应用层，如图2 3 所 一j 4 一 浙江大学颂i j 学位论文 第三章点五数据处理技术 示。平台层，也称核心层，包含有服务所需要的核心功能，封装了p 2 p 网络通 用的基本原语最小集合。它实现了构建p 2 p 应用的关键机制，包括对等体、对 等组、对等体发现、对等体传输( 包括防火墙穿越) 、对等体监视以及对等体和 对等组的创建和安全相关的原语。中间的服务层提供了搜索和索引、目录、存储 系统、文件共享、资源聚集、认证等网络服务，它并非p 2 p 网络运行所必需， 但通常不可或缺。最上面的应用层，包括了使用j x t a 服务开发的完燕p 2 p 应用 程序，如p 2 p 即时通信、文档和资源共享、娱乐内容管理和分发等。 应用 服务 核心 匪亟立因e 互亟困 臣亟亟互固臣亟圃 f j 心 扩展网络上的并种对锝体 图2 - 3j x t a 软件架构 j x t a 网络由一系列互联的节点或对等体组成。对等体够自组织形成对等 组，它可以提供一套常用服务，如文档共享或交谈应用等。j x t a 对等体可以通 过x m l 格式的通告发布其服务，网络上其它对等体可以通过通告获悉如何连接 及交互对等体的服务。j x t a 对等体使用管道向其它对等体发送消息，其中管道 是一种用于服务通信的异步、无向的消息传输机制，消息只是简单的x m l 文档， 包含路由、摘要和认证信息。管道需绑定到特定的端点上，如t c p 端口和相关 i p 地址。下一节将详细描述这些基本概念。 j x t a 架构有别于其它分布式网络模型的主要特点为：使用x m l 文档( 通 告) 来描述网络资源；由于管道到对等体，对等体到端点的抽象，无需依赖集 浙江大学颂卜学位论文 第三章点云数据处理技术 中式的名字地址转换如d n s ；一致的对等体寻址机制如对等体i d 。 2 4 3j x t a 基本概念 j x t a 基本概念是从j x t a 协议中提出的一系列专有名词，描述了一些j x t a 的常用术语以及构成j x t a 的基本组件。包括对等体、对等组、消息、管道、服 务、通告和标识符等。 1 对等体 对等体是一个虚拟的通信点，它并不等同于用户或设备；在一台计算机或设 备上可以有多个对等体，在一台设备上运行多个应用程序，每个应用程序都可以 看作是一个对等体，所以对等体可以是一个已联网( 如接八互联网) 设备上的一 个应用程序。其次，个应用程序可以分布在多台设备上，但只作为一个对等体。 由此对等体可以定义成：对等体是任意一个实体，它支持j x t a 协议族中一个或 多个协议，能够执行一些有用的任务，并就操作的结果与网络上其他实体直接或 怕 】接地进行通信。每个对等体都有一个唯一的标识符，且不随时间和空闯而改变。 对等体与特定