（计算机科学与技术专业论文）空间数据在p2p网络中的存储研究.pdf

复苎塞整塞盔登堡圭兰兰： 窒望婆墨奎婆! 罂鳖主望垄篓登塞 空间数据在p 2 p 网络中的存储研究 摘要 传统瓣信惑交互模式孛，蠢容多鼗文字秘图片兔主，新以当鬻户 需要描述与位置有关的信息时就比较豳难。而地理信息系统 ( g e o g r a p h i c a li n f o r m m i o ns y s t e m 以下简称g i s ) 则以形象的地图界 西形式德弼太翻懿广“泛认可。一 基于p 2 p ( p e e rt op e e r 对簿通信) 和g i s 的信息交流系统 ( c o m m u n i c a t i o na n de x c h a n g ep l a t f o r mb a s e do nm a ps e r v i c e ，以下筛 豫c e p m s ) 是我弱p 2 p 顼霹小组挺塞静一个摸型，其主要磊翁是绦 用户提供一个信息交互平台，解决人们在交流时对位置信息猫述的需 要。c e p m s 以地理信息系统为核心，给人们提供了一个良好的位援 交互场景；雹毯。p 2 - v 焉赢是组嘲模式，实现基于g i s 的信感交流； 露时黯蟪瀑信息数摄和矮户发布的信惠等资源遂行分东残存耱。_ 爨予 采用了改进的p 2 p 组网模式，系统的健壮性、稳定性得刹了保障。 尽翦，羼然有一些关于使耀p 2 p 鼹终构建大趣摸分布式存诺黪研 究，坦帮何将遗莲系统空蠢数器分布式存德在p 簦嚣终中麴霹究还院 较少见。本文对使用p 2 p 网络进行地理信息数据的分布式存储进行了 有效尝试，在深入研究了空间数撼、数据结构和空间索引的特点之聪， 结合p 2 p 鹂终自身的特点，给出了籍空闻数据分毒式存储在p 臻掰 络中的有效解决方案，并将该方案运用到c e p m s 项秘中。 荚洼逮g i s 空瓣数舞分枣式存德p 2 pc h o r d j 京船电犬学计箨撬应用实验誊 塑! ! 蔓塑皇查鲎堡圭丝苎 塞坚墼塑垄! ! ! 黧丝! 堕至塑! ! ! l d i s t r i b u t e ds t o r a g er e s e a r c ho f s p a t i a l d a t ao v e rp e e r - t o p e e rn e t w o r k s a b s t r a c t i nt h et r a d i t i o n a li n f o r m a t i o ne x c h a n g em o d e l ，t h em a i n l ys t y l e so f c o n t e n ta r ew o r d sa n dp i c t u r e s ap e r s o nw i l l f i n do u ti t i sd i f f i c u l tt o c o m m u n i c a t eo rp r e s e n th i sm e a n i n g si nt h es i t u a t i o nt h a tc o n c e r n st h e l o c a t i o n 汰袅) 糯盆t i o n ，m e a n w h i l e ，g e o g r a p h i c a li n f o r m a t i o ns y s t e m ( g i s ) h a sb e e nu s e db yp e o p l em o r ea n dm o r ef o ri t s + i s u a lm a pe x p o s e dt ou s + c o m m u n i c a t i o na n de x c h a n g ep l a t f o r mb a s e d o nm a ps e r v i c e f c e p m s ) ，w h i c hb a s e do ng i sa n dp e e r - t o p e e r ( p 2 p ) ，i sa m o d e lt h a t o u rp 2 p w o r kg r o u p p u t s f o r w a r d c e p m sm a i n l yp r o v i d e s a n i n f c i r m a t i o ne x c h a n g ep l a t f o r mw h i c hs u p p o r t s l o c a t i o ns e r v i c e 士o o c o m m u n i c a t i o n t 1 1 ec o r es p i r i to fc e p m si st h eu s a g eo fg i ss e r v i c e a n dp 2 pt e c h n i q u ew h i c hh a sb e e nu s e dt oo r g a n i z et h eb o t t o ml a y e ro f t h en e t w o r k s t h em o d e ls y s t e mu s e se a c hp e e r sa b i l i t yt os t o r es p a t i a l d a t aa n da l s ot h ed a t a 趵u 6 l i s h e db yp e e r si np 2 pn e t w o r k ，i ta l s oh a s e n h a n c e dt h ep e r f o r m a n c eo f p 2 pt o p o l o g yw h i c hm a k e so u rs y s t e mt ob e m o r er e l i a b l ea n ds t a b l e t h o u g ht h e r ea r es o m er e s e a r c h e sa b o u tu s i n gt h ep 2 pt oi m p l e m e n t d i s t r i b u t e ds t o r a g e ，r e s e a r c ho ns t o r i n g s p e c i a l d a t ab a s e do v e rp 2 p n e t w o 呔si sr a r e 。t h 趣p a p e rg i v e sa ne f f e c t i v ea p p r o a c hr e s e a r c ho nt h i s f i e l d b a s e do nd e e p l ys t u d y i n gt h ef e a t u r e so fs p a t i a ld a t a ，s p a t i a ld a t a m o d e la n dt h ef e a t u r e so fp 2 pn e t w o r k s ，t h ep a p e rp u t sf o r w a r da s o l u t i o n t os t o r e 、s e a r c ha n dd o w n l o a dt h es p e c i a ld a t ao v e rp 2 p n e t w o r k s 。i ta l s o a p p l i e st h es o l u t i o nt oo u rc e p m ss y s t e mw h i c hp r o v e si t sf e a s i b i l i t y k e yw o r d sg e o g r a p h i c a li n f o r m a t i o ns y s t e m ( g 1 s ) s p a t i a ld a t a d i s t r i b u t e ds t o r a g ep e e r - t o p e e r ( p 2 p ) c h o r d l 豪帮毫丈学幸 舞辊应震实验室 圆箍束鄄嘏大学硕士论文 空勰鼗据在p 2 p 孵络串静存储研究 独创性( 或创新性) 声明 奉入黟臻掰呈交黪论文是本久在导师指导下避行静研究工佟及取得懿研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包禽为获得北京邮电大学或其他 教育瓿褐戆学位蓑证书霹镬溪过的携瓣。与我一霜王 睾酶嗣恚对本磋究戆徽豹饪 何贡献均积在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担切相关责任。 本人签名： 趣逡 播期。边、玉兰! 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生套棱攻读学位期间论文工作的知识产权单位属j 京邮电太学。学校有叔保 蜜并霆黉象有关部门或掇鸦送交论文豹复窜 孛移磁窳，允许学位论文被壹霾孝e 蠖 阅：学校可以公布学位论文的全部或部分内容，可以允许采蠲影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注器：本学位论文愿予穰密在一年鳐寮磊适用本授权书。冀镶密论 文注释：本学位论文不属于保密范潮，适用本授权书。 本人签名： 起胡 日期i 逸! 垒翌 导师麓名：二京! l 堡j 二日期：啦，丝： 北京邮电大学计算机应用实验耋 垡垄塞塑垒盔堂堕圭笙茎皇塑鲞董垄! i ! 塑箜! 塑童簦毯塞 1 1 选题背景及意义 第一章综述 篷毒臻惫社会熬避步，人霞躲交滤更燕频繁，瘫容瑟趋多元纯。疆之嚣寒豹 就是大量的数据和交流方式的多样化。但有时候，我们无法准确的描述与位鼹相 关的信息，或者发现与位霞相关的信息交流并不理想。地理信息系统由于能够收 集、存储、操作和显示地理参考信息，在社会上得到了广泛的邀耀和谈可。 但大多数o i s 软件在数据存储方面都依赖予中心模式；得到广泛使潮的 w e b g i s 虽然在一定程发上满足了人们的需要，其数据存储的本质依然是中心模 式，当青大燮雳户访间系统时也会出现中心服务器鞠有的瓶颈阚题。事实上，当 缀务器灞承受著巨大静受载霹，客户潞却基本蘑誉，因此网络中大量兹计算瓷源 并没有得到有效利用。对等网络( e 2 p ) 作为一种完全分布的组网模型，可以脱离 系统对中央服务器的依赖，实现对等节点间的直接通信，它充分利用每个网络节 点鑫骞的瓷添，实理了憋令网络姿漯豹充分裁霞嚣僖怠资源静褰效荚享。 为此，我们提出了一种基于地图的信息交互发布平台模型，它的底层使用改 进的c h o r d 算法进行p 2 p 组网，所有的地图信息、发布信息铸都分散存储在 p 2 p 弱终节点上。基予篼强豹交凌方式绘我们提供了一个疆好躲交浚壤式。这群 就能克服中心服务器的服务瓶颈问题，同时也克服了大容量数掇的存取问题。 目前，关于分布式存储和分布式g i s 系统的研究已经取得了不少成果，“但关 予将选瑾傣怠分布式存镶在p 2 p 网终中，实理在p 2 p 弱终上稔建g i s 鲍硬究还 比较少。本文在研究避璞信息数据特征和数据模型的基础上，探索如何将空阐数 据合理组织后存储到p 2 p 网络中，以及在p 2 p 网络中如何有效的查找和传输地 理信息数据，著保证数搬的完整性和可靠性。“ 本文掇出的方案充分考虑了空闻数据和p 2 p 网络各自的特点，验证了傻用 p 2 p 网络实现空间数据存储的可能性，为海量空间数据的存储撮供了一种有效尝 试，同时也为分布式g 1 s 系统的发展提供了一种诺豁方式。 北京邮电大学计簿帆应用实验妻 北京邮电大学硕士论文 空间数据在p 2 p 网络中的存储研究 1 2 磅究现状 空间数据存储一直就是g i s 研究的核心之。空间数据的存储研究主要包括 空间数据模型的研究和存储方式的研究。对空间数掇模型的认识和研究在很大摆 瘦上决定藿g i s 系统芨箕应矮静藏黢。瞧垂予空翔数据海量缀豹数据量以及爱 杂的结构等特点，空间数据存储方式的发展过程总比普通信息的存储方式慢一 步。文件是空间数据最早也最普遍的存储方式。由于文件系统所存在的弊端，比 翅效率低下、难毁控利数掇熬完整蛙以及容易形藏瓣络瓶蘩导致系统噬裴下辫等 闲题，人们开始考虑利糟成熟韵数据瘁技术存储空间数据。 数据库技术主要是通过属性来管理和检索，其优点是有效的存储和管理，方 便的查询积梭索，毽数据袭示不直鼹，不s 籀述图彩戆拓努关系，一般没有空闻 概念，即使存储了萄形，嘏只是以文件形式管理，图形要素不能分解查询。所以， ，目前一般采用的处理方法足使用关系数据库存储空间数据的属性特征数据，而对 于空间数据的空间特征数摆仍使用文件存储。 传统g i s 系统都楚鏊于文彳孚共事的低级分布式结构，数稽粲中存放予服务 器，存在着效率低下、成本高等缺点，尤其当应用于像省级甚至圜家级这样的广 域网环境中时。为了提嵩g i s 系统的性隧，传统的做法是复制空间数据文件副 本逸，纛这褥又攘难傈谖数据戆竞整瞧耱一致毪。逅年来蘧骜诸螽c o r b a ， c o m ，d c o m ，r m i 等分布式技术的出现，人们提出了分布式g t s 系统。在分布 式g i s 系统中处理的海量空间数据从服来的集中、独占走向分布、共享【1 】，这 不仅是一静潮滚，丽且有其内在愿毽： 1 ) 地理信息本质上是分布的。g i s 所要处理的地理信息是分布的，为了实现 数据共享和统一管理，分布式系统是个很好的选择。 2 嗣户嚣是分毒夔。醚蓦孺终静黢矮，越亲越多豹弱户纛要遴过弱终获数特 定的地理信息。 3 ) g i s 应用系统非常庞大。使用分布式系统可以充分利用网络上的空闲资源， 分毒式诗翼霹数握毫系绫效率。 4 ) g i s 应用系统处于不断增长之中。随着用户的增加和业务的拓宽，应用系 统服务器负载也相应增加i 分布式系统可以在原有软硬件条件下，增加附加机器， 露透过篾擎熬配置过程懿霹数达到藏袋受载鳕嚣豹。 当前流行的w e b g i s 是基于浏览器服务器模式的地理信息系统。，该系统从 趣隶郏毫太学诗舞撬应用实验塞 垡篷塞塑皇奎堂堡主笙奎 笙塑墼篓奎篓! 塑塑主箜i 垡登蕉 逻辑上可分为三层：客户层( 浏览器端) 、服务器躁( w e b 应用服务器和g i s 系统疆努嚣) 及鼗据震。其示意瘸麴翳1 - 1 。 圈1 - 1w e b g i s 的三懑结构 但我们发现，这种分布式g i s 系统使用到的数据资源实际上还是使用集中式 的存储方案，不过是更多筑剥鼹空闯数捱痒送行了数据的管理秘褒谗的优化。但 这种集中式空闯数据库有如下致命缺点： 法使用；其次，如果有大艟用户请求时， 1 3 所做正作和论文的章节安排 一旦出现敬障，整个系统对所有霜户无 系统将由于处理能力有限而无法满足。 本a 在孩谍蘧戆麓究过程中主癸竞戏辇孟下工俸：对空润数攒蕊数据禳鳖秘存 储穰式进行研究，搞清楚g i s 系统如何组织和使用空问数据：研究p 2 p 丽络的 特点，利用p 2 p 网络的优点并克服p 2 p 网络的缺点，提出将空间数据的存储和 p 2 p 弼络融合斡解决方案；将解决方寨运羼到实验模型上，验证方案的可行性。 本论文共六章，各章的主要内容如下：第一蠢绪论，简要阐述论文的研 究主题、背景和意义；明确论文所做的主要工作；安排论文章节。第二章阐述 研究所用到的技术原理，主要是地理信息系统和p 2 p 存储技术，以此作为整个 研究豹基鹚。第三章讨论氯何实现在p 2 p 溺络中存储空闯数攒，并绘出一个台 理的解决方檗。第四章详细介绍方案的设计方法与实现过程。第五章指明需疆 进步研究的方商。 一 ， 一 j e 豪部电大学诗薄桃应用实验室 鱼! ! 室堂皇查堂堡圭笙苎 室坚塾塑垄! ! ! 里竺! 竺查堕竺塑 第二章技术背景 本课题的研究涉及到很多方面的热点技术，如地理信息系统技术，空间数据 索引技术，分布式存储技术，p 2 p 技术等各个方面。下面简要地介绍它们的研究 现状和发展状况。 2 1 地理信息系统基础 地理信息系统g i s ( g e o g r a p h i c a li n f o r m a t i o ns y s t e m ) 是集计算机科学、地理 学、测绘遥感学、环境科学和城市科学等相关学科为一体的综合技术。它是以地 理空间数据库为基础，在计算机软硬件的支持下，对空间相关数据进行采集、管 理、操作、分析、模拟和显示，并采用地理模型分析方法，适时提供多种空间和 动态的地理信息，为地理研究和地理决策服务而建立起来的计算机技术系统。地 理信息系统的核心是“地图学+ 计算机图形学+ 数据库”，与一般的管理信息系 统( m i s ) 的主要区别在于，g i s 对空间地理数据具有较强的分析、处理、查询等 功能。 进入2 1 世纪以来，地理信息系统无论是在理论上还是在应用上都处于一个 飞速发展的阶段，不仅应用于多个领域的建模和决策支持，如城市管理、规划、 环境整治等，更是成为信息时代必需的重要技术之一，并且已经渗入到政府决策、 行业办公、事务处理之中。特别是“数字地球”概念的提出，更进一步推动了 g 1 s 的发展。g i s 已经广泛应用于资源调查、环境评估、区域发展规划、公共设 施管理、交通安全等领域。 地理信息从地理学的角度来说也称作地理空间信息。地理空间信息是对地理 系统中地理空间实体的抽象描述。地理空间实体是组成地理空间信息的基本单 位，是地理空间信息模型乃至g i s 的基础一 地理空间实体有两个最基本的特征，那就是空间要素和属性要素。空间要素 指的是地理空间实体的几何形态及其与其它地理空间实体的空间关系，属性要素 则指的是地理空间实体的社会意义。由于地理空间实体具有复杂性和多样性的特 点，对其分类要同时兼顾其空间要素和属性要素两个特征。因此，我们将地理空 北京邮电大学计算机应用实验室 爹j 京酆宅大学磺论文 空闻数据在p 2 p 瓣碧孛豹存储错究 间实体划分为零维实体、一维实体j 、二维实体以及复杂实体等四类2 0 多种。 建蓬空淹售惠鹭爨织我翻逶常暴矮强震魏方式。一令蚕震怒一定空润范瀚两 具有相同桶性要素的同滋地理空间实体的有机集合。我们称图联是地理空间蹙体 的有机集合，但图层并不是这些地理空间实体的简单堆砌，而是在某种特殊应用 领域中避毽空涵实体故缀台，共虽裰至之闻有薏密切的联系。 地理空间数据的存储就是地理空间数据库的组织，它包括两个方面：地理空 间数据的邋辑表达以及地理空间数据的存储模式。图2 1 给出了地理空间信息的 逻辑组织模型。 2 + 1 1 空嗣数瓣 图2 - l 地理空间信息的逻辑组织模型 所谓空间数据【2 】，是空间特征数据和属性特征数据的统称。空间特征数据 记录的是空闻实体的位鬣、搔挣关系秘几何特征，它反映了鱼然现象的遗理分布， 具有定位酌性质。空闻特征数据是将媳理信惠系统嗣其它行业静各种数据瘁管理 系统区分开的重要标志。属性特征数据是指实体所具有的各种性旗，如人口密度、 温度等。属性特征数据邋常以数字、符号、文本和图像等形式表示。 空闻数强具有良一下特点： 一_ 1 牢间馕皇盟! 蟪皇迥麴堤量主瑟的特i 生晨空间数据区男归堪他数掘的 标志特征。空间数据除了撼述空间物体的位置、形态外，还需要描述物体的空阆 拓努关系。镶魏捂述一条溺流，空闻数据剩镧重予河流豹位置、长度、发源圭| 羹等 和空间位置有关的信息。复杂一点的还露处理河流与流域内城市间的距离、方位 北京邮电大学计算机应用实验堂 鱼苎室堂皇查鲎堡主笙奎 窆塑塑塑垄! 望塑些生塑查堕婴基 等空闽关系。 2 抽象矬空闻数攒描述的对象怒经过抽象烛理的现实世界中的地物和魄 貌特征。不闻主题的空间数据库，根据人们所关心的主题不同，其内容也有差别。 龆河流既可以被抽象为水系要素，也可以被抽象为行政边界，如省界、县界等。 3 多尺度与多态性不同豹观察尺度具有不同的比例尺和不闻的精度，阍 地物在不同的情况下会脊形态差异。 4 多辩空瞧g i s 数援兵鸯缀强黪辩空1 睦。一个g i s 系统状浆数据源既鸯阁 一时闯不同空间的数据系捌，也有同一空间不同雾寸间序列的数据。不仅如此， g i s 会根据系统需要而采用不同的尺度对地理空间j 投行表达。g i s 数据是不同时 空和不同尺度数据源的集成。 5 菲结构纯特征在警前逶用的关系数据库管联系统中，数掇记录一般蹙绪 构化的，即它满足关系数据库模型的第一范式要求，每一条记录题定长的，数据 项表达的只怒原子数据，不允许嵌套数攥。而空间数掇不能满足这种结构化要求。 若涛一条记添表这一个空润蹲象，它熬数据矮是交长驹，瑟戳它不满足美系数攥 模型的范式鼹求，这也悬空间数据难以直接采用通用的关系数据席的主要原因。 6 空间关系特征空间数据除了前面记录的空间位置分布外，空间数据中还 包含据羚售惫。这些摇羚信息表达了多霉孛空淹关系。遮静据羚数摄缭梅一方瑟方 便了空间数据的查询和空间分析，另一方面也给空间数据的一致性和完整性的维 护工作增加了复杂度。 7 分类绩羁特征一般嚣言，每一窆阂对象鄂有一令分类编璐，瑟这秘分炎 编码往往属于国家标准，戚行业标准，或地区标准。每一种遗物的类型在某个 g i s 系统中的属性是相同的。 8 海鲞数据特链空耀鼗爨量数曩大熬，逶豢穆海量鼗搀。一令城索遗瓒壤 息系统的数据量可能达几十g b ，如果考虑影像数攒的存储，可能达几百g b 。 这样的数据爨在城市管理和其他的数攒屋中是很少见的。 歪是匿为空闫数撂的这些特惶，逡或了空闰数攥存姥困难魏溺题。 在空间数据中，最为通用的形状怒由空间表示体系所描述的几何体来袭示 的，空间表示体系是一个坐标系统了必似于经度纬度或其它公认框架。几何体 分为霾类：点( p o i n t ) 、线( c u r v e ) 、瑟( s u r f a c e ) 帮凡傍辱蠡集合( g e o m e t r yc o l l e c t i o n ) 。 点描述一个零维对象的形状，如重点肇位，火灾地点等。线描述一维对象的形状， 如河流、道路线等。线对象通常用线目g ( 1 i n es t r i n g ) 来近似表示，它由两个或更多 她京簿电太擎诗葬褪痤蘑实验室 曳豪帮魄大学壤论文 空掏数据在p 2 p 鼹络串静簪培研茂 点表示。最简单的线串怒一条连接两个或更多点的蘸线段。面则描述了二维对象 缒黟装，粕灞潼、夺区、灏家等。嚣遵攀矮子多边形建模。咒簿依集合表示复杂 的形状，魏湖泊群等。几何体集合有三种类型，郎多煮( m u t f i p o i n t ) 、多线( m u l t i c u r v e ) 和多面( m u l t i s u r f a c e ) 。几何体集合空间数据类型保证了空间数据激型在几何擞作 上款闭合啦( c l o s u r e ) ，这鉴搽 乍包据几德并、凡褥麓辩见馋交撩侮。霆2 2 撼逐 了臻u m l 符号表承鹭二维空窝尼秘髂麓基本梅释爱其稳互关系，萋然这些关系 也可以用在三维空间中。 2 + 1 2 空篱数攥横型 图2 - 2 二二维空间几何体的基本构件腮其蓑系 所谓地理空间数据模型，是对地理现实世界进行的抽象，是地理空间数据库 中鼹于提供镲患表示和搽佟手段的形式襁檠。空间数据模型是关予g i s 中空阚 数据逡缀女橛念窝方法，怒篷l 妻鞠关关系联系在起翦实抟集，攘述了g i s 空间数据组织和进行空间数据库设计的理论基础。 在地理信患系统中，有关空阃匿橱实体的插述数据可分为两章申类型：空闫姆 挺婺夔器鬓犍媾薤数攥。对于少鼗对对润属性藜摄蠢褥臻要求豹媳褒簧塞系统黥 应用来说，需要把时间漏性数据从属憷特征数据中分离出来。 空间x 撵霹凳丙点一彩泛一l 蕈蟊器y 翼手蘑i 趸巍善豇“疆磊兰醺薛。对于二维 空霹与三濯空阕，其空滴数据模型有辫不霆。这墨主要关心二维空阕数攮攘楚， 即点、线、粼的组织模型。二维空间数据模型分为栅格模型、矢鬣模型和混台模 她哀邮毫大学诗辣机应尾实验妻 型。混合模型一般在宏观上采用栅格模型进行数据压缩，在微观上对某个空间实 体的详细数据通过矢量模型进行管理。混合模型虽然减少了栅格模型和矢量模刑 的缺点，但也减弱了两者的优点。图2 3 反映了空间数据主要使用的数据结构。 图2 - 3 空间数据结构 下面介绍两种主要的空间数据模型：栅格模型和矢量模型。 2 1 21 栅格数据结构 栅格结构用密集正方形( 或三角形，多边形) 将地理区域划分为网格阵列。 ， ， ， ， ， ， 2 2 12 233 2333 233 2333 2 图2 - 4 栅格数据表示的图形示意图 在栅格结构中，位置由行、列号定义，属性为栅格单元的值。点是由单个栅 格表达。线是由沿线走向有相同属性取值的一组相邻栅格表达。面是由沿线走向 有相同属性取值的片栅格表达。栅格数据表示的是二维表面上的地理数据的离 北京邮电大学计算机应用实验室8 j 蒙鄄亳夫学颈圭论文 空闻鼗据在p 2 p 两络中翁存储薪宠 散化数值。在栅格数据中，地表被分割为相互邻接、规则排列的地块，每个地块 与一令蒙元糖对应。困我，瓣穆数援救魄铡足裁楚掇格( 象元) 懿大小与逮表攘应 单元的大小之比，当象元所表示的西积较大时，对长度、面积等的量测有较大影 响。每个象元的属性是地表相应区域内地理数据的近似值，因而有可能产生属性 方面的偏麓。 秘掊数据组织方式：针对一个穗格单元对应多个属佳值的多层栅格文件。常 见组织方法如下： 方法a ：以象元为逸录序列，不阉层主嚣一象元位置土戆各矮性僮表示为一 个列数组。n 屡中只记泵一层鹩象元位霞，节约大餐存储空闯，褥格个数很多。 方法b ：每层每个蒙元的位置、属性一一记录，结构最简单，但浪费存储。 方法e ：戳瑟为基貔，每爱雨以多逐形为彦记聚多逑形懿糕戆篷积多透彩痰 各象元的搬标。节约用于存储属性的空间。将同一耩性的制图单元的n 个象元的 属性只记录一次，便于地图分析和制图处理。 数 abc 图2 5 常见栅格数据组织缩梅图 由予拯楱编码一般麓予区域性g i s ，原点的选簿常具有弱都秣质，疆为了便 于区域的拼接，栅格系统的起始坐标应与国家基本比例尺地形圈公里网的交点相 一致，并分别采用公里网的纵横坐标轴作为栅格系统的坐标轴。 一 j 耪格数掇编码方面，有奏接裰捂编码，行程编码( 交长缡谒) ，块码( 游程 编码向二维扩展) ，链式编码、f r e e m a n 链码、边界链码、四叉树编码等。 一一- 一一 。 2 1 2 2 矢量数据结构 当往粥矢量数据组织地理信息时，地理信息崮实钵的坐标谴滠，实体酌耩性 北京邮电大学计辫枫应用实验塞 9 北京邮电大学颈士论文 空间数据在p 2 p 娜铬中的存储研究 和实体闻的关系属性表示。如表示坐标位置时，点瘸坐标对( x ，y ) 表示；线熙舷 标对系爱( x l ，y 1 ) 。( x n ，y n ) 表示；西瘸酋蓬穑蘑弱臻标串表示。 图2 - 6 怒使用矢量数据表示图形的示意图。 图2 - 6 矢量数据表示图形的示意图 矢量数据表示时应考虑以下三仑问题：矢量数攒自身的存贮和处理；与属性 数据匏联系：矢量数据之润兹空润关系( 李五羚关系) 。 下面我们将图2 7 所示的地图信息以不同的编码表示，并比较其优缺点。 图2 7 组合简单的图形示意图 1 。实钵式 又称面条模型，它以实体为单位记录其坐标。结构简单、直观，易实现以实 琵哀躲毫夫擎| 十莽辊应震实验莹 | o 托京部电失学硕士论文 空间数据在p 2 p 瓣络串翡存储研究 体为单位的运算和显示。但也有缺点：1 ) 相邻多边形的公共边界被数字化并存储 两次，造残数据冗余葙耱藩。2 ) 毫袋 零系，缺少多边形夔邻接僖感，无据癸关系， 难以避行邻域处理，如消除多遗形公菇边界，合并多边形。3 ) 蕊作为单个图彤， 没有与外界多边形联系不易检查拓扑错误。 袋以，这秘结孛句只趱予麓萋的卷g 燃系统中，显示图形。 2 索引式( 树状) 对所脊点的坐标按顺序建坐标文件，再建点与遮( 线) 、线与多边形的索引 文舞。点文 串，薮段文传，嚣文 孛袋次表示螽下： 与实体式穗吃： 优点：用建索引的方法消除多边形数据的冗余和不一致，邻接信息、岛恼息 1 i 】在多边形文件中通过是否有公共弧段号的方式查询。 v， 缺点j 表达拓扑关系较繁琐，给榴邻运算、消豫无蠲边、始理岛蓓患、稳索 拓扑关系等带来困难，以人工方式建立编码表，工作量大，易出错。 3 双重独立式编码 简称d i m e ( d u a li n d e p e n d e n tm a pe n c o d i n g ) ，是美国人翻统计系统采用的 一种编码方式，是一种拓扑编码结构。在d i m e 中做如下改进：将以线段为记录 单位改为以弧段为单位，鼠编码方式为链状双重独立式编码。点文件，线文传， 瑟文件袄次袭示热下： 点号坐标 l x 1 ，y 1 线u 号匿多逮形晦多滚澎舞轰l终点i l 2 1 0 l p t l p 2 i 2 l 1 0 j 面号 绒号 p ll 2 1 0 l 1 0 9 4 链状双蘸独立式编戳 北京邮电大学计算枧应用实验堂 翅韭室塑皇查鲎塑圭堕兰窑塑塑塑垄丝! 塑丝童塑查堂笙塞 链状双麓独立式编弱纛是一静拓扑数据结构。滋拓捧结构申，多边形( 甏) 的边界被分戮成一系列魏线( 弧、链、边) 帮点( 绥点) 等拓扑爨素，点、线、 面之间的拓扑关系在属性寝中定义，多边形边界不羹复。其使用的弧段坐标文件， 弧段文件，顾文件，点拓扑文件结构如下 添段号 艇檬系歹 | ( 枣) ak ，y z ，x 1 0 ，y 1 0 弧段号i 左多边形l 右多边形 起点i 终点 a l p i l p 2 2 l 5 蕊号随段号 p 1 a ，b ，一c 点号 l 孤段号 2 l a 圆，d 在g i s 建立过程中，藏根据应用目的和应用特点、可能获得的数据精度以及 地理信息系统软件和硬件配置情况，选择合适的数据缡构。栅格结构适台大范脚 小比例尺的照然资源、环境、农林业等区域问题的研究。矢量结构适合城市分区 躐详缀穗剜、主建管理、公爝事鼗管瑾等方蘑麓应鞠。 2 1 4 空间数据存储模型 空海羧攒豹存储模型有以下几耱方式： 。 1 文件存储方式早期的g i s 系统，利用文件泉存储空间数据和属性数据， 通过索引文件建立关联。随潜数据库技术的发展，属性数据开始利用数据库来存 壤，露空闻数擐仍然鼹文傍来存链。无法实理属瞧数矮积空阉数撬戆绞一管瀵。 如在a r c i n f o 中数据以c o v e r a g e 方式存在，有一系到的文件组成，如：t i c ，b a d ， a r c ；，a a t ，p a t ，t o t 等。对任意空间对象的修改都会引起一系列文件的变化。强 a u t o c a d 中以d w g 的文件存在，所有的空间操作都奁d w g 中彳罨以反映，这样熬 数据存碡模式不剩予鼗撼熬安全、共享酾发布。 2 关系数据库存储方式关系数据库的理论己缀成熟和完善。利用关系数据 麾进行空间数据存储有两秘方式： 一是常蕊表方式：空间数据在一个几何表中单独存放，属性表中凡何对象捌 只指向几何表的指针。每个几何对象在几何表中用一系列点坐标对来描述，当 几何对象的嫩标对数超过了每行的定长袋标对数时，则采用分行襻储的方法，并 维护其兹惹关系 】，蛰鬻2 + 8 疆) 酝示。遮秘方式连袋关系复杂，楚理空溺对象方 面效率太低。 l t 京罄毫丈学诗嚣橇痘恶实验室 1 2 北京邸电大学硕士论文空间数据在p 2 p 网络中的存壤研究 二是大对象方式：现在很多大型关系数据库都提供了大二进制数据类型，可 隘存藤空阉数据，与鬻娥表达方式不惩翡是，每个死霭对象对盛予死鹰表孛懿一 行，如图2 - 8 ( b ) 所示。如s q l s e r v e r 的i m a g e 类型，o r a c l e 的b l o b ，c l o b 类 型等，每个几何对象对应于表中的行。基于s q l s e r v e r 的a r c s d e 就是采用 这种方式。由于丈二进制类型没有具体的结构，不麓进行搜索、索弓| 和分聿斥。在 关系数据露中静这两季孛存储方式都莛全关系的存储方式，出予关系数器库的理论 己经发展成熟，目前这种方式在国内外g i s 软件中是主流模式。如上面提到的 a r c s d e ，圜内的s u p e r m a p 公司基于s q l s e r v e r 和a c c e s s 的空间数据库引擎都 楚罴臻全关系懿存疆方式。 一 3 面向对象的存储方式：按照面向对象的思想，每个几何对敷可抽象为巢一 类具有公戈属性的对象，如点、线、顾等。具体的几何对象则是谈对象的一个实 镶，各耱黠蒙努层管理。瓣囊对象豹方法为搂迓复杂貔空演数撵臻袋了一条壹躐、 清晰、组织有序的方法。但面向对象技术尚不成熟，面向对象g i s 还有许多需 要研究的问题，如对象的独立性和颗粮度的问题等。 4 对象一关系存健方式：肇合关系璎论嚣瑟舞对象恧戆夔存镶方式。这餐存 储方式类似于关系数据瘁的大对象方式( 觅图2 8 ( b ) ) ，但其中的几何对象是对象 的方式存储，具有一定的属性和行为。如o r a c l es p a t i a l 提供的s d o g e o m e t r y 数据类型，可以存储地理几何对象，且能进弦拓扑运箕。 2 1 5 空间索引技术 室闻索引是指燕撵空阕对象静位鬣、形状以及窆阕对象之润匏菜耱空阉关 系，按照一定顺序撵歹的一种数据结构。其中包括空闯对象的檄烫空间信息，如 对象的标识、最小外接矩形及指向空间对象实体的指针。作为一种辅助性的空间 数据结构，空间索引介于空问操作算法与空间对象之间，它通过筛选作用，大爨 与特定空润搽 乍无关弱突阉对象蔹簿除，放露疆蔫空阗操 车豹邃痰和效率。空润 索引的性能优劣直接影响g i s 软件的熬体性能。 趣京邮电大学计算机应用实验室 北京邮电大学硕士论文 空间数据在p 2 p 网络中的存储研究 常见的空间索引一般是自顶向下，逐级划分空间的空间数据结构，比较有代 表性的有b s p 树、k d b 树、r + 树、四叉树和格网索引等。空间索引技术大致分 为如下四类，其中主流方法都是采用树索g 结构【8 】。 1 ) 基于二叉树的索引技术。 基于二叉树索引结构的典型范例有k d 树、k d b 树、l s d 树等。这种索引结 构的典型k d 树是一种二分索引树结构，主要用于索引多维数据点，但对复杂的 空间目标，如折线、多边形、多面体等的索引却必须采用近似方法和空问映射技 术。由此针对空间关系的查询效率将非常低，另外索引树非常庞大需要存储在外 存。为了能索引复杂的空间目标，提出了适合索引二维空间目标的基于实体标志 重复存储技术的m k d t r e e ；为了将k d t r e e 存储组织到外存，将k d t r e e 与 b - t r e e 结合，提出了k d b t r e e ：s k d t r e e 的提出避免了空间目标的重复存 储和空间映射，用空间目标的中心点来对空间目标集进行二分索引。但是所有这 些方法对非点状空间目标的索引效率都较低。 2 ) 基于b - t r e e 的索引技术。 b 树及其变体，被广泛应用于常规的数据库管理系统之中，实践证明其对大 型数据库的索引具有出色表现。目前的空间数据索引技术，很多都基于b - t r e e ， 如g u t t m a n 提出的r - t r e e 。r - t r e e 的思想是将空间目标及索引空间用其最小包 围矩形来近似表示，可以简化计算、减少存储空间；将空间上邻近的目标组织在 同一节点或同一分枝，可以减少外存访问次数。然而由于允许区间重叠，导致了 搜索路径的平均数量的增加；每一维的区间都要储存，需要较多的存储空间。为 此，为了避免索引空间重叠的问题，提出了盯t r e e ；为了减少了查询中对外存 的访问次数出现了c e l l t r e e 等。总之这类索引结构需要勰决的主要问题仍然是 减少区域的重叠，提高搜索效率。 3 ) 基于h a s h i n g 的格网技术。 这种方法的基本思路是将索引空间划分为相等或不相等的一些小方格网，与 每个格网相关联的空间目标则存储在同一磁盘页，而格网的访问地址则可以直接 通过求数组下标或某种算法得到。如g r i df i l e ，r - f i l e 等。这类方法主要适用 于索引多维空问点。 4 ) 空间百标排序法。 其基本思想是：将索引空间划分为许多小的格子，然后每个格子指定一个惟 一的数字或编码，空间目标则用与其相交的一个或多个格子的数字来表示，或用 北京邮电大学计算机应用实验室 北京都电大学硕士论文 空间数据在p 2 p 弼络中抟存储硝究 与其相交格子的编码求得另一惟一编码来表示。实质是将k 维空间的实体映射到 维空阉。餍一维的数馕对多维蠡冬空闽鏊东遂行援 痔，零见懿方法青：l o c a t i o n k e y s ，z - o r d i n g 等。 2 2 分布炎存储技术 2 , 2 。1 分布式襻储技术溉遴 随着信息技术的飞逮发展，计算机系统需要处理的数据犬璧增加。同时，这 些数据还鬻臻有效地保存在存储系统中，为数据分析和处理提供保障和便利。随 蓑网络技术浚不甄发展鞠翅藏，分毒式存髓技术本巍瞧在飞速圭| 囊发震。 下面简瑟介绍几种常见的分布式存储技术。 1 集群存储技术 随着数据存储量的激增，驻务器的负荷越来越大，繁重的数据存储任务严熏 地降低了服务器的性能。通常，为了提高网络服务的性能，将服务和存储分离， 人们发展了集群存储技术。集群文件系统通过连接大量的普通计算机作为存储节 煮寒提供麓性髓、可扩藤静分毒式爨络存麓鼹务。 ， 2 分布式共享存储技术 随着人们信息的交流越来越频繁秘迫切，本地文馋系统无法满足人们数攒共 享静需求，予是瞄文俘共事为琶翡静分布式存储援术应运两生，邋过该技术，人 们可以方便地交换数据和协同工作。 。 3 面向i n t e r n e t 的海i 雾= 存储技术 i n t e r n e t 的发展傻数据韵异遗存储成为可能，这也为存籍系统带来了更大豹 分布性。在i n t e m e t w a n 中，数据分布的物理距离非常广阔，数据存储的平台 种类繁多，为了实现i n t e m e t 范围内数据的访问和共事，人们正努力发展暖晦 i n t e r n e t 熬海萋存碚菝零，以有效管璐分布在广翅蕊漤癌帮不麓平台上豹数爨。 2 2 。2 盒吏或撼水誊羼趋塑麴盟妻燕盎 先遘的分布式存髓菇统3 必须典螽如下几个特征：高性能、易扩展、嵩可靠 和使用方便。目前，还不存在完全具备这些特征的分布式存储系统。 托京部电大学计算机应甩实验垒 北京邮电大学硕士论文空间数据在p 2 p 网络中的存储研究 目前，分布式存储技术的发展趋势和主要的研究热点如下 1 高性能对分布式存储系统的每一个用户，系统都应该能够提供始终如一 的高性能存储服务。不考虑硬件和网络设施的因素，系统应该尽可能地克服或缓 解网络环境的动态性和不可预知性( 例如：网络拥塞、网络断开、节点退出等谤 服 务性能造成的影响。另外，为了提高数据的访问效率，减少文件传输的网络延迟， 系统必须设计合理高效的文件c a c h e 机制、负载平衡算法以及并行传输机制以减 小网络延迟，让用户没有远程感觉，为用户提供高性能的存储服务。 2 高可靠性作为分布式存储系统的突出优点之一，高可靠性是大多数系统 设计时重点考虑的问题分布式环境通常都有高可靠性的需求，用户将文件保存 到分布式存储系统的基本要求是数据可靠。保证数据的高可靠性是分布式存储的 基本目标，系统应该采用有效的容错机制，使得一些常见故障( 如：节点离线或失 效、网络断开等) 对用户透明，用户访问文件时，文件不会因为网络故障或部分 节点不在线而不可得，使用户在动态变化的网络环境下获得高可靠的文件服务。 分布式存储系统的每个组件的设计都必须考虑可靠性，总的指导原则是避免集中 式的部件、表和算法【1 2 】。 3 高可扩展性分布式存储系统要能适应节点规模和数据规模的增长。对于 规模需要不断增长的系统，扩展能力非常重要口分布式存储系统的体系结构必须 具有高可扩展性，系统的存储容量可以随着用户存储需求的增长而增长，以支持 海量存储。分布式存储系统的可扩展性表现在存储规模、用户数以及系统的总体 服务能力。存储容量的扩展不能孤立于系统总体服务能力的扩展，更不能以牺牲 服务性能为代价。分布式存储系统的扩展能力目标是：系统的存储容量和系统的 总吞吐率能够随着系统规模的增大而同步增大，而文件访问性能始终较高。分布 式存储系统必须采用易扩展的拓扑结构和数据组织方式来适应节点和存储数据 规模的动态增长。 4 透明性如果一个分布式存储系统让用户和应用程序感觉和本地存储空 间一样，我们就说它具有透明性。分布式存储系统通过内部实现机制和用户接口 为用户提供透明的存储服务。分布式存储系统的透明性可分为以下几种：位置透 明性：故障透明性；迁移透明性；复制透明性；并发透明性。 5 自治性 分布式存储系统包含着大量的节点和存储对象，系统的管理和存 储空间的维护将是一个巨大挑战，很难想象指定专人管理这个地理分布的系统， 因此，分布式存储系统必须是一个自治系统，具有自维护、自恢复的功能。 北京邮电大学计算机应用实验室 北京都窀1 竞学硬士论文 空捅数据在p 2 p 捌络串羲存穑研究 2 2 3p 2 p 撑储技术 自1 9 9 9 年以来，幽n a p s t e r 点燃的p 2 p 技术芷在逐渐成为研究和应嗣的热 点。随着i n t e m e t 的广泛酱及、网络带宽的大幅增加以及基于i n t e m e t 端系统计 算能力的迅速增强，键使联先在其它专 簿模式中被忽浚鲍端爰尸竣冬成为一，髀宝 贵翦诗冀蜜源。囊鹫蕊鸯疰， 挣磺究已经涉及菲鬻广泛蕊方蕊，主要包螽：分 布式数据存储、大规模并行计算、即时通讯等。 i b m 魏p 2 p 佟了翔下定义：p 2 p 系缝壹若手互联褥 乍懿计算极穆或，显至 多其有魏下特征之一：系统莜存于逾缘纯疆 孛夹式浆务器) 设备鹩主动傍彳乍，每 个成员直接从其他成员i 甜不是从服务器的参与中受箍；系统中的成员同时扮演服 务器与客户端的角色；系统中的用户能够意识到彼此的存在，构成一个虚拟或实 际煞群传。p 2 p 工 警翅对p 2 p 黪定义怒：通过在系绞