基于P2P的分布式矢量地理数据在线服务研究

冯 佳 丽,江 南,＊,胡 斌,吴 家 皋,邹 志 强

(1.南京大学地理与海洋科学学院,江苏南京 210093;2.南京师范大学虚拟地理环境教育部重点实验室,江苏南京 210046;3.南京邮电大学计算机学院计算机技术研究所,江苏南京 210003）

基于P2P的分布式矢量地理数据在线服务研究

冯 佳 丽1,江 南1,2＊,胡 斌2,吴 家 皋3,邹 志 强3

(1.南京大学地理与海洋科学学院,江苏南京 210093;2.南京师范大学虚拟地理环境教育部重点实验室,江苏南京 210046;3.南京邮电大学计算机学院计算机技术研究所,江苏南京 210003）

研究P2P环境下矢量地理数据在线服务的关键技术,提出了一种基于Linking机制的矢量地理数据组织、分割及无损拓扑重建方法。通过将矢量要素各个层次的链接关系记录在Linking信息中,形成一种松散的分布式拓扑关系,并支持矢量数据无损重建。实验证明了该组织方式和相关算法的健壮性、高效性及完备性。

分布式 GIS;矢量地理数据服务;Linking机制;拓扑;无损重建

0 引言

地理信息系统的发展已进入社会化和大众化阶段,越来越多的用户希望在线获取空间数据和服务,而传统集中式空间信息在线服务系统存在难以解决的“单点故障”和“热点瓶颈”问题。P2P(Peer-to-Peer）技术的出现为空间信息在线服务提供了新的解决方案[1,2]。基于P2P的栅格地理数据服务已得到广泛应用[3-5],通过P2P的“多点传输”和“多点计算”大幅提高了服务效率[6,7]。由于矢量地理数据的复杂性,分布式矢量地理数据在线服务在数据组织、服务模型等方面尚缺乏有效的解决方案。

当前,基于P2P的地理数据在线服务模型主要采取Chord网作为底层网络结构,通过把空间范围内的控制点完全映射到Cho rd网,实现了负载均衡[8]。但这种纯Chord网将所有结点映射到Chord上,查询时存在网络跳数多的问题,导致效率不高及维护困难。对于分布式矢量地理数据目前主要采取两种组织方式:一种基于离散对象,该方式为保证对象的完整性,不对数据分割,但这带来索引冗余及管理复杂等问题[9];另一种基于数据瓦片(Tile）,按空间范围对数据分割形成矢量分块,该方式虽然提高了数据的传输和查询效率,却破坏了矢量对象的拓扑信息完整性[10-12],导致一些矢量拓扑算法难以在分布式环境下展开。

因此,本文研究提出新的基于P2P的分布式矢量地理数据在线服务模型,设计了一种支持空间拓扑算法的分布式矢量地理数据组织方式,利用Linking机制构建了一种松散的分布式拓扑关系,在此基础上设计并实现了矢量地理数据的分割与快速无损重建算法。

1 分布式矢量地理数据在线服务模型设计

本文提出的分布式矢量地理数据在线服务模型由3个模块协作完成(图1）:1）预处理模块,分割矢量数据,建立数据块文件,发布索引;2）P2P网络模块,采用基于DH T(Distributed Hash Table,分布式哈希表）的Cho rd+Quadtree混合索引网络对peer进行管理;3）无损重建模块,在客户端修复数据块,得到请求范围内的无损矢量数据。

该服务模型中,分布式矢量数据的组织方式、数据分块及重建算法是研究的重点。本文采用一种Chord+Quad的 P2P混合索引网络,首先在 Chord网中形成分层cache,即采用M X-CIF四叉树算法对初始数据进行一定粒度的分块,然后将fmin层数据块索引映射到Cho rd环,在每个fmin结点下存储level层(fmin≤level≤fmax）数据块的索引。这种方式能很好地发挥Cho rd网的负载均衡优势及层次网络的高效特性,提高查询效率。网络中的客户端peer对数据发出请求时,同样采用M X-CIF算法得到数据块索引,向 P2P网络发送请求消息。这种分层cache与四叉树查询算法的结合,能同时提高查询速度、减小网络传输量及数据块重建次数。

2 面向P2P的分布式矢量地理数据组织方式

2.1 Linking机制

本文提出Linking机制,通过记录少量Linking信息链接对偶实体,构建一种松散的分布式拓扑,以实现矢量地理数据的表示模型及快速无损重建。记录的Linking信息可分为3个层次:1）Tile间的Linking。Tile按照 M X-CIF编码规则编码,明确描述Tile间的邻接关系,也可通过简单计算得到 Tile的层次及父子关系。2）Geometry间的Linking。在矢量数据分块过程中,被切割的矢量对象(Geometry）形成若干个衍生子对象,存储在不同的 Tile中。将父 Geometry的标识ID传递给其所有子 Geometry,构建 Geometry间的父子、兄弟关系。数据重建时,具有相同标识ID的 Geometry需要合并重建。3）弧段间的Linking。被切割的 Geometry实际上是被分割成若干首尾相接的弧段,把切割过程中产生的弧段分割点称为LinkingNode。记录LinkingNode的相关信息,以描述结点匹配关系、弧段间的连接关系,分割点相对于父 Geometry的关系。

图1 面向P2P环境的分布式矢量数据服务流程Fig.1 Service process of distributed vector data in P2P-oriented

2.2 基于Linking机制的 Tile表示模型

在P2P网络中,数据均以 Tile为单位进行存储与传输。Tile文件的表示模型按照 Tile-Geometry-LinkingNode的层次进行组织(图2）。递归分块时,须将本层的Linking信息传递到下一层相应的子对象中,实时更新已有信息,使得叶子结点上的子对象始终拥有正确的、足够的信息,为自底向上的无损重建提供条件。

图2 Tile表示模型Fig.2 Representation model of Tile

2.3 基于Linking机制的矢量数据快速无损重建

基于Linking机制,本文设计了矢量数据快速无损重建算法,算法思想如下:

以两个数据块合并为例(图3）,描述基于Linking机制的矢量数据快速无损重建步骤。

(1）读入 Tile文件,进行编码排序,识别相邻的Tile,转步骤 2。

(2）遍历两个相邻 Tile中的 Geometry,识别需要合并的子 Geometry,转步骤 3;将无匹配对象的Geometry直接加入结果 Tile中。

图3 基于Linking机制的无损重建Fig.3 Lossless reconstruction based on Linkingmechanism

(3）矢量对象重建:1）根据Linking ID进行匹配,得到此次重建所需的LinkingNode信息(表1）;2）将两个子 Geometry分别从匹配的LinkingNode处断开,并将反向相等的弧段剔除,得到 G1-C-B-AF1和 F0-E-D-G 0;3）根据 LinkingNode信息,得知F0、F1既是分块时产生的分割点,也是父 Geometry的结点,因此合并为结点F,且保留。而 G0、G1仅为分块时产生的分割点,用其对偶结点C(或D）替换弧段中的 G0、G1。最终得到的结果弧段为 C-B-A-F和 F-E-D-C(或D-C-B-A-F 和 F-E-D）。

表1 LinkingNode信息匹配Table 1 Matching of L inkingNode

(4）由结果弧段(或点）构造 Geometry,得到无损的 Geom1(F-E-D-C-B-A-F）;将步骤3中匹配的LinkingNode信息删除,避免信息冗余。

(5）转步骤2,直到遍历参与合并的两个 Tile中所有矢量对象;将重建结果组织成 Tile并输出。

2.4 几种特殊情况的处理

由于空间矢量数据的多样性与复杂性,本文的无损拓扑重建方法考虑了对不同情况的处理(图4）。

图4 几种特殊情况Fig.4 Several special situation

(1）带岛的多边形:带岛的多边形(图4a）是地理数据中常见的图形,对此类对象往往需要单独处理。在本文的分割与无损重建算法中,对于带岛的多边形,由Linking机制修复后的弧段依次构建外轮廓与岛,再由这些环构建合并结果。

(2）凹多边形:对凹多边形进行切割,可能产生如图4b所示的情况,其子 Geometry不是一个简单的 Polygon,而是 M ultiPolygon。采用本文提出的Linking机制,也可由链接弧段得到无损重建结果。

(3）多段线:如图4c中的LineString被切割成两个子对象,且两个子对象均为M ultiLineString类型。而LineString的构造缺乏像PolygonBuilder中连接弧段的机制。若经过重建后,弧段数大于1,则以M ultiLineString类型的结果返回。对此,在线性对象的重建过程中加入LineMerger加以处理,连接邻接的子线段,使得结果无损。

经过各种特殊情况的验证及对算法的完善,本文提出的“基于Linking机制的矢量数据快速无损重建算法”不失一般性,适用于各种符合OGC规范的矢量对象。

3 实验及结果分析

开源项目JTS(Java Topology Suite）遵守由OGC(开放地理信息系统协会）发布的Simp le Feature Access规范,实现了拓扑矢量图形的九交叠置运算,但没有记忆衍生子对象之间的潜在联系,在空间计算方面属于常见的有损计算。对于大型矢量数据,也缺乏高效的处理算法。本研究以JTS为二维矢量数据基本计算的支撑环境,编程实现了基于Linking机制的实例地理数据分块与无损重建算法原型系统,并与现有JTS方法进行了对比分析(表 2）。

表2 基于JTS的分块算法与基于Linking机制的分块算法对比Table 2 Comparison of JTSMethod and L inking Mechanism

基于两种分块方法的信息增量对比显示,基于Linking机制的数据分块方法需同时记录几何信息及分块过程中产生的少量Linking信息,因此文件信息量增幅略大,但这种极小幅度的数据量增加并不影响网络传输。基于两种方法的数据重建时间对比显示,当数据块增多时,原有的JTS重建算法所需时间已远远超出接受范围。重建结果的数据增量对比显示,基于Linking机制的重建结果信息量没有任何增加。

为了更直观地反映基于Linking机制的数据分块与重建算法的优势,本文根据以上实验生成两种算法的数据比值图(图5）,可见,基于Linking机制的方法用少量的Linking信息,实现了数据重建效率的快速提升。在分块数为256块时,数据重建时间仅为原算法的3.8%,效率提升了将近两个数量级。与此同时,基于Linking机制的方法将数据块中附加的Linking信息用于恢复数据,所有子对象经过重建逐步剔除了Linking信息,数据重建结果与原始数据严格一致,达到无损重建。

图5 实验数据比值Fig.5 Ratio of experimental data

4 结论

本文针对分布式矢量地理数据在线服务的难点,设计了矢量地理数据在线服务模型,提出了一种面向分布式P2P网络的矢量数据组织模式及快速无损重建算法。经过多种类型矢量数据的检验及与现有方法的对比分析,证明该方法利用少量Linking信息可以实现分布式矢量地理数据的无损重建,并大幅提高了重建效率,具有无损性、健壮性、高效性、完备性,较好地解决了分布式环境中 GIS矢量地理数据网络管理困难的问题,为分布式矢量地理数据快速在线服务提供了关键技术支持。

[1] L IU Y,GONGJ Y,WU H Y.P2Pbased efficient on-line spatial images delivery[J].Geoinformatics,2007,6754(20）:1-9.

[2] CASTRO M,DRUSCHEL P,HU Y,et al.Exploiting network proximity in distributed hash tables[A].Proceedingsof the Fu-DiCo 2002[C].Bertinoro,Italy,2002.52-55.

[3] STOICA I,MORRISR,KARGERD.Chord:A scalable peer-topeer lookup service for internet applications[A].Proceedingsof the ACM SIGCOMM[C].2001.149-160.

[4] TAN IN E,HARWOOD A,SAM ET H.基于节点分组的 P2P海量地形数据共享机制[J].武汉大学学报,2009,34(6）:650-653.

[5] TAN IN E,HARWOOD A,SAMET H.Building and querying a P2P virtual world[J].Geoinformatics,2006,10(1）:91-116.

[6] 喻占武,郑胜,李忠民.一种混合式P2P下的大规模地形数据传输机制[J].测绘学报,2008,37(2）:243-249.

[7] 潘少明,喻占武,王浩.P2P环境中的全局空间数据目录研究[J].地理与地理信息科学,2006,22(5）:22-25.

[8] TAN IN E,HARWOOD A,SAM ET H.Using a distributed Quad Tree index in peer-to-peer networks[J].VLDB Journal,2007,16(2）:165-178.

[9] 刘荣高,庄大方,刘纪远.分布式海量矢量地理数据共享研究[J].中国图象图形学报,2001,6(9）:267-276.

[10] 魏祖宽,裴海英.Internet GIS上矢量型空间数据传送的最优化策略[J].遥感学报,2000,5(4）:865-872.

[11] 戴海滨,秦勇,于剑.铁路地理信息系统中海量空间数据组织及分布式解决方案[J].中国铁道科学,2004,25(5）:118-120.

[12] 高波,郭朝珍,丁善镜.基于 GML矢量图层分割的空间分布式协同处理的研究[J].计算机应用,2009,29(1）:297-301.

Study on P2P-Based D istr ibuted Vector Geo-Data On line Service

FENGJia-li1,JIANG Nan1,2,HU Bin2,WU Jia-gao3,ZOU Zhi-qiang3
(1.SchoolofGeographicandOceanographicScience,NanjingUniversity,Nanjing 210093;2.KeyLaboratoryofVirtual GeographicalEnvironment,NanjingNormalUniversity,MinistryofEducation,Nanjing 210046;3.InstituteofComputer Technology,CollegeofComputer,NanjingUniversityofPosts&Telecommunications,Nanjing210003,China）

P2P technology offered a novel solution to spatial info rmation online service and a good p latfo rm fo r sharing mass spatial data,it can avoid"single point of failure"and"hot spots bottleneck"p roblem,w hich exist in traditional centralized system of spatial information.P2Po riented raster geo-data online service has been widely app lied,w hereas vecto r geo-data online service still hasmany issues can′t be handled,such as vector geo-data organization pattern,segmentation,lossless reconstruction,etc.In this paper,the data organization of vecto r geo-data and distributed topology was especially researched deep ly.The Hybrid Cho rd+Quadtree Indexing netwo rk wasadop ted to manage peers to imp rove query efficiency and realize load balancing.Key technology of P2P-oriented distributed vector geo-data online service was researched,and the pattern of vector geo-data organization based on Linking Mechanism,segmentation and lossless reconstruction were p roposed in this research.This novel organization pattern reco rded link relationship between all levels in the Linking info rmation in tile in order to form a loosely distributed topology,and suppo rt lossless reconstruction.Tile was designed to be o rganized by"Tile-Geometry-LinkingNode"hierarchical model to fo rm a distributed topology.Segmentation and lossless reconstructionmethod took advantageof linking information,to reconstruct the damaged Geometries.Comparative experiment show s that the organization and the associated algorithms to be robust,efficient and complete.

distributed GIS;vecto r geo-data services;Linking M echanism;topology;lossless reconstruction

P208

A

1672-0504(2010）05-0029-04

2010-03- 29;

2010-06-09

国家高技术研究发展计划(863计划）项目(2009AA 12Z219、2007AA 12Z207）;国家自然科学基金项目(40801149）;江苏省测绘科研项目(JSCHKY200810）

冯佳丽(1987-）,女,硕士研究生,主要从事 GIS设计、开发与应用等方面研究。＊通讯作者E-mail:njiang@njnu.edu.cn