基于P2P的分布式矢量地理數(shù)據(jù)在線服務(wù)研究

馮 佳 麗,江 南,＊,胡 斌,吳 家 皋,鄒 志 強(qiáng)

(1.南京大學(xué)地理與海洋科學(xué)學(xué)院,江蘇南京 210093;2.南京師范大學(xué)虛擬地理環(huán)境教育部重點(diǎn)實(shí)驗(yàn)室,江蘇南京 210046;3.南京郵電大學(xué)計(jì)算機(jī)學(xué)院計(jì)算機(jī)技術(shù)研究所,江蘇南京 210003）

基于P2P的分布式矢量地理數(shù)據(jù)在線服務(wù)研究

馮 佳 麗1,江 南1,2＊,胡 斌2,吳 家 皋3,鄒 志 強(qiáng)3

(1.南京大學(xué)地理與海洋科學(xué)學(xué)院,江蘇南京 210093;2.南京師范大學(xué)虛擬地理環(huán)境教育部重點(diǎn)實(shí)驗(yàn)室,江蘇南京 210046;3.南京郵電大學(xué)計(jì)算機(jī)學(xué)院計(jì)算機(jī)技術(shù)研究所,江蘇南京 210003）

研究P2P環(huán)境下矢量地理數(shù)據(jù)在線服務(wù)的關(guān)鍵技術(shù),提出了一種基于Linking機(jī)制的矢量地理數(shù)據(jù)組織、分割及無損拓?fù)渲亟ǚ椒?。通過將矢量要素各個(gè)層次的鏈接關(guān)系記錄在Linking信息中,形成一種松散的分布式拓?fù)潢P(guān)系,并支持矢量數(shù)據(jù)無損重建。實(shí)驗(yàn)證明了該組織方式和相關(guān)算法的健壯性、高效性及完備性。

分布式 GIS;矢量地理數(shù)據(jù)服務(wù);Linking機(jī)制;拓?fù)?無損重建

0 引言

地理信息系統(tǒng)的發(fā)展已進(jìn)入社會(huì)化和大眾化階段,越來越多的用戶希望在線獲取空間數(shù)據(jù)和服務(wù),而傳統(tǒng)集中式空間信息在線服務(wù)系統(tǒng)存在難以解決的“單點(diǎn)故障”和“熱點(diǎn)瓶頸”問題。P2P(Peer-to-Peer）技術(shù)的出現(xiàn)為空間信息在線服務(wù)提供了新的解決方案[1,2]?；赑2P的柵格地理數(shù)據(jù)服務(wù)已得到廣泛應(yīng)用[3-5],通過P2P的“多點(diǎn)傳輸”和“多點(diǎn)計(jì)算”大幅提高了服務(wù)效率[6,7]。由于矢量地理數(shù)據(jù)的復(fù)雜性,分布式矢量地理數(shù)據(jù)在線服務(wù)在數(shù)據(jù)組織、服務(wù)模型等方面尚缺乏有效的解決方案。

當(dāng)前,基于P2P的地理數(shù)據(jù)在線服務(wù)模型主要采取Chord網(wǎng)作為底層網(wǎng)絡(luò)結(jié)構(gòu),通過把空間范圍內(nèi)的控制點(diǎn)完全映射到Cho rd網(wǎng),實(shí)現(xiàn)了負(fù)載均衡[8]。但這種純Chord網(wǎng)將所有結(jié)點(diǎn)映射到Chord上,查詢時(shí)存在網(wǎng)絡(luò)跳數(shù)多的問題,導(dǎo)致效率不高及維護(hù)困難。對(duì)于分布式矢量地理數(shù)據(jù)目前主要采取兩種組織方式:一種基于離散對(duì)象,該方式為保證對(duì)象的完整性,不對(duì)數(shù)據(jù)分割,但這帶來索引冗余及管理復(fù)雜等問題[9];另一種基于數(shù)據(jù)瓦片(Tile）,按空間范圍對(duì)數(shù)據(jù)分割形成矢量分塊,該方式雖然提高了數(shù)據(jù)的傳輸和查詢效率,卻破壞了矢量對(duì)象的拓?fù)湫畔⑼暾訹10-12],導(dǎo)致一些矢量拓?fù)渌惴y以在分布式環(huán)境下展開。

因此,本文研究提出新的基于P2P的分布式矢量地理數(shù)據(jù)在線服務(wù)模型,設(shè)計(jì)了一種支持空間拓?fù)渌惴ǖ姆植际绞噶康乩頂?shù)據(jù)組織方式,利用Linking機(jī)制構(gòu)建了一種松散的分布式拓?fù)潢P(guān)系,在此基礎(chǔ)上設(shè)計(jì)并實(shí)現(xiàn)了矢量地理數(shù)據(jù)的分割與快速無損重建算法。

1 分布式矢量地理數(shù)據(jù)在線服務(wù)模型設(shè)計(jì)

本文提出的分布式矢量地理數(shù)據(jù)在線服務(wù)模型由3個(gè)模塊協(xié)作完成(圖1）:1）預(yù)處理模塊,分割矢量數(shù)據(jù),建立數(shù)據(jù)塊文件,發(fā)布索引;2）P2P網(wǎng)絡(luò)模塊,采用基于DH T(Distributed Hash Table,分布式哈希表）的Cho rd+Quadtree混合索引網(wǎng)絡(luò)對(duì)peer進(jìn)行管理;3）無損重建模塊,在客戶端修復(fù)數(shù)據(jù)塊,得到請(qǐng)求范圍內(nèi)的無損矢量數(shù)據(jù)。

該服務(wù)模型中,分布式矢量數(shù)據(jù)的組織方式、數(shù)據(jù)分塊及重建算法是研究的重點(diǎn)。本文采用一種Chord+Quad的 P2P混合索引網(wǎng)絡(luò),首先在 Chord網(wǎng)中形成分層cache,即采用M X-CIF四叉樹算法對(duì)初始數(shù)據(jù)進(jìn)行一定粒度的分塊,然后將fmin層數(shù)據(jù)塊索引映射到Cho rd環(huán),在每個(gè)fmin結(jié)點(diǎn)下存儲(chǔ)level層(fmin≤level≤fmax）數(shù)據(jù)塊的索引。這種方式能很好地發(fā)揮Cho rd網(wǎng)的負(fù)載均衡優(yōu)勢(shì)及層次網(wǎng)絡(luò)的高效特性,提高查詢效率。網(wǎng)絡(luò)中的客戶端peer對(duì)數(shù)據(jù)發(fā)出請(qǐng)求時(shí),同樣采用M X-CIF算法得到數(shù)據(jù)塊索引,向 P2P網(wǎng)絡(luò)發(fā)送請(qǐng)求消息。這種分層cache與四叉樹查詢算法的結(jié)合,能同時(shí)提高查詢速度、減小網(wǎng)絡(luò)傳輸量及數(shù)據(jù)塊重建次數(shù)。

2 面向P2P的分布式矢量地理數(shù)據(jù)組織方式

2.1 Linking機(jī)制

本文提出Linking機(jī)制,通過記錄少量Linking信息鏈接對(duì)偶實(shí)體,構(gòu)建一種松散的分布式拓?fù)?以實(shí)現(xiàn)矢量地理數(shù)據(jù)的表示模型及快速無損重建。記錄的Linking信息可分為3個(gè)層次:1）Tile間的Linking。Tile按照 M X-CIF編碼規(guī)則編碼,明確描述Tile間的鄰接關(guān)系,也可通過簡(jiǎn)單計(jì)算得到 Tile的層次及父子關(guān)系。2）Geometry間的Linking。在矢量數(shù)據(jù)分塊過程中,被切割的矢量對(duì)象(Geometry）形成若干個(gè)衍生子對(duì)象,存儲(chǔ)在不同的 Tile中。將父 Geometry的標(biāo)識(shí)ID傳遞給其所有子 Geometry,構(gòu)建 Geometry間的父子、兄弟關(guān)系。數(shù)據(jù)重建時(shí),具有相同標(biāo)識(shí)ID的 Geometry需要合并重建。3）弧段間的Linking。被切割的 Geometry實(shí)際上是被分割成若干首尾相接的弧段,把切割過程中產(chǎn)生的弧段分割點(diǎn)稱為L(zhǎng)inkingNode。記錄LinkingNode的相關(guān)信息,以描述結(jié)點(diǎn)匹配關(guān)系、弧段間的連接關(guān)系,分割點(diǎn)相對(duì)于父 Geometry的關(guān)系。

圖1 面向P2P環(huán)境的分布式矢量數(shù)據(jù)服務(wù)流程Fig.1 Service process of distributed vector data in P2P-oriented

2.2 基于Linking機(jī)制的 Tile表示模型

在P2P網(wǎng)絡(luò)中,數(shù)據(jù)均以 Tile為單位進(jìn)行存儲(chǔ)與傳輸。Tile文件的表示模型按照 Tile-Geometry-LinkingNode的層次進(jìn)行組織(圖2）。遞歸分塊時(shí),須將本層的Linking信息傳遞到下一層相應(yīng)的子對(duì)象中,實(shí)時(shí)更新已有信息,使得葉子結(jié)點(diǎn)上的子對(duì)象始終擁有正確的、足夠的信息,為自底向上的無損重建提供條件。

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

2.3 基于Linking機(jī)制的矢量數(shù)據(jù)快速無損重建

基于Linking機(jī)制,本文設(shè)計(jì)了矢量數(shù)據(jù)快速無損重建算法,算法思想如下:

以兩個(gè)數(shù)據(jù)塊合并為例(圖3）,描述基于Linking機(jī)制的矢量數(shù)據(jù)快速無損重建步驟。

(1）讀入 Tile文件,進(jìn)行編碼排序,識(shí)別相鄰的Tile,轉(zhuǎn)步驟 2。

(2）遍歷兩個(gè)相鄰 Tile中的 Geometry,識(shí)別需要合并的子 Geometry,轉(zhuǎn)步驟 3;將無匹配對(duì)象的Geometry直接加入結(jié)果 Tile中。

圖3 基于Linking機(jī)制的無損重建Fig.3 Lossless reconstruction based on Linkingmechanism

(3）矢量對(duì)象重建:1）根據(jù)Linking ID進(jìn)行匹配,得到此次重建所需的LinkingNode信息(表1）;2）將兩個(gè)子 Geometry分別從匹配的LinkingNode處斷開,并將反向相等的弧段剔除,得到 G1-C-B-AF1和 F0-E-D-G 0;3）根據(jù) LinkingNode信息,得知F0、F1既是分塊時(shí)產(chǎn)生的分割點(diǎn),也是父 Geometry的結(jié)點(diǎn),因此合并為結(jié)點(diǎn)F,且保留。而 G0、G1僅為分塊時(shí)產(chǎn)生的分割點(diǎn),用其對(duì)偶結(jié)點(diǎn)C(或D）替換弧段中的 G0、G1。最終得到的結(jié)果弧段為 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）由結(jié)果弧段(或點(diǎn)）構(gòu)造 Geometry,得到無損的 Geom1(F-E-D-C-B-A-F）;將步驟3中匹配的LinkingNode信息刪除,避免信息冗余。

(5）轉(zhuǎn)步驟2,直到遍歷參與合并的兩個(gè) Tile中所有矢量對(duì)象;將重建結(jié)果組織成 Tile并輸出。

2.4 幾種特殊情況的處理

由于空間矢量數(shù)據(jù)的多樣性與復(fù)雜性,本文的無損拓?fù)渲亟ǚ椒紤]了對(duì)不同情況的處理(圖4）。

圖4 幾種特殊情況Fig.4 Several special situation

(1）帶島的多邊形:帶島的多邊形(圖4a）是地理數(shù)據(jù)中常見的圖形,對(duì)此類對(duì)象往往需要單獨(dú)處理。在本文的分割與無損重建算法中,對(duì)于帶島的多邊形,由Linking機(jī)制修復(fù)后的弧段依次構(gòu)建外輪廓與島,再由這些環(huán)構(gòu)建合并結(jié)果。

(2）凹多邊形:對(duì)凹多邊形進(jìn)行切割,可能產(chǎn)生如圖4b所示的情況,其子 Geometry不是一個(gè)簡(jiǎn)單的 Polygon,而是 M ultiPolygon。采用本文提出的Linking機(jī)制,也可由鏈接弧段得到無損重建結(jié)果。

(3）多段線:如圖4c中的LineString被切割成兩個(gè)子對(duì)象,且兩個(gè)子對(duì)象均為M ultiLineString類型。而LineString的構(gòu)造缺乏像PolygonBuilder中連接弧段的機(jī)制。若經(jīng)過重建后,弧段數(shù)大于1,則以M ultiLineString類型的結(jié)果返回。對(duì)此,在線性對(duì)象的重建過程中加入LineMerger加以處理,連接鄰接的子線段,使得結(jié)果無損。

經(jīng)過各種特殊情況的驗(yàn)證及對(duì)算法的完善,本文提出的“基于Linking機(jī)制的矢量數(shù)據(jù)快速無損重建算法”不失一般性,適用于各種符合OGC規(guī)范的矢量對(duì)象。

3 實(shí)驗(yàn)及結(jié)果分析

開源項(xiàng)目JTS(Java Topology Suite）遵守由OGC(開放地理信息系統(tǒng)協(xié)會(huì)）發(fā)布的Simp le Feature Access規(guī)范,實(shí)現(xiàn)了拓?fù)涫噶繄D形的九交疊置運(yùn)算,但沒有記憶衍生子對(duì)象之間的潛在聯(lián)系,在空間計(jì)算方面屬于常見的有損計(jì)算。對(duì)于大型矢量數(shù)據(jù),也缺乏高效的處理算法。本研究以JTS為二維矢量數(shù)據(jù)基本計(jì)算的支撐環(huán)境,編程實(shí)現(xiàn)了基于Linking機(jī)制的實(shí)例地理數(shù)據(jù)分塊與無損重建算法原型系統(tǒng),并與現(xiàn)有JTS方法進(jìn)行了對(duì)比分析(表 2）。

表2 基于JTS的分塊算法與基于Linking機(jī)制的分塊算法對(duì)比Table 2 Comparison of JTSMethod and L inking Mechanism

基于兩種分塊方法的信息增量對(duì)比顯示,基于Linking機(jī)制的數(shù)據(jù)分塊方法需同時(shí)記錄幾何信息及分塊過程中產(chǎn)生的少量Linking信息,因此文件信息量增幅略大,但這種極小幅度的數(shù)據(jù)量增加并不影響網(wǎng)絡(luò)傳輸?；趦煞N方法的數(shù)據(jù)重建時(shí)間對(duì)比顯示,當(dāng)數(shù)據(jù)塊增多時(shí),原有的JTS重建算法所需時(shí)間已遠(yuǎn)遠(yuǎn)超出接受范圍。重建結(jié)果的數(shù)據(jù)增量對(duì)比顯示,基于Linking機(jī)制的重建結(jié)果信息量沒有任何增加。

為了更直觀地反映基于Linking機(jī)制的數(shù)據(jù)分塊與重建算法的優(yōu)勢(shì),本文根據(jù)以上實(shí)驗(yàn)生成兩種算法的數(shù)據(jù)比值圖(圖5）,可見,基于Linking機(jī)制的方法用少量的Linking信息,實(shí)現(xiàn)了數(shù)據(jù)重建效率的快速提升。在分塊數(shù)為256塊時(shí),數(shù)據(jù)重建時(shí)間僅為原算法的3.8%,效率提升了將近兩個(gè)數(shù)量級(jí)。與此同時(shí),基于Linking機(jī)制的方法將數(shù)據(jù)塊中附加的Linking信息用于恢復(fù)數(shù)據(jù),所有子對(duì)象經(jīng)過重建逐步剔除了Linking信息,數(shù)據(jù)重建結(jié)果與原始數(shù)據(jù)嚴(yán)格一致,達(dá)到無損重建。

圖5 實(shí)驗(yàn)數(shù)據(jù)比值Fig.5 Ratio of experimental data

4 結(jié)論

本文針對(duì)分布式矢量地理數(shù)據(jù)在線服務(wù)的難點(diǎn),設(shè)計(jì)了矢量地理數(shù)據(jù)在線服務(wù)模型,提出了一種面向分布式P2P網(wǎng)絡(luò)的矢量數(shù)據(jù)組織模式及快速無損重建算法。經(jīng)過多種類型矢量數(shù)據(jù)的檢驗(yàn)及與現(xiàn)有方法的對(duì)比分析,證明該方法利用少量Linking信息可以實(shí)現(xiàn)分布式矢量地理數(shù)據(jù)的無損重建,并大幅提高了重建效率,具有無損性、健壯性、高效性、完備性,較好地解決了分布式環(huán)境中 GIS矢量地理數(shù)據(jù)網(wǎng)絡(luò)管理困難的問題,為分布式矢量地理數(shù)據(jù)快速在線服務(wù)提供了關(guān)鍵技術(shù)支持。

[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.基于節(jié)點(diǎn)分組的 P2P海量地形數(shù)據(jù)共享機(jī)制[J].武漢大學(xué)學(xué)報(bào),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下的大規(guī)模地形數(shù)據(jù)傳輸機(jī)制[J].測(cè)繪學(xué)報(bào),2008,37(2）:243-249.

[7] 潘少明,喻占武,王浩.P2P環(huán)境中的全局空間數(shù)據(jù)目錄研究[J].地理與地理信息科學(xué),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ì)遠(yuǎn).分布式海量矢量地理數(shù)據(jù)共享研究[J].中國(guó)圖象圖形學(xué)報(bào),2001,6(9）:267-276.

[10] 魏祖寬,裴海英.Internet GIS上矢量型空間數(shù)據(jù)傳送的最優(yōu)化策略[J].遙感學(xué)報(bào),2000,5(4）:865-872.

[11] 戴海濱,秦勇,于劍.鐵路地理信息系統(tǒng)中海量空間數(shù)據(jù)組織及分布式解決方案[J].中國(guó)鐵道科學(xué),2004,25(5）:118-120.

[12] 高波,郭朝珍,丁善鏡.基于 GML矢量圖層分割的空間分布式協(xié)同處理的研究[J].計(jì)算機(jī)應(yīng)用,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

國(guó)家高技術(shù)研究發(fā)展計(jì)劃(863計(jì)劃）項(xiàng)目(2009AA 12Z219、2007AA 12Z207）;國(guó)家自然科學(xué)基金項(xiàng)目(40801149）;江蘇省測(cè)繪科研項(xiàng)目(JSCHKY200810）

馮佳麗(1987-）,女,碩士研究生,主要從事 GIS設(shè)計(jì)、開發(fā)與應(yīng)用等方面研究。＊通訊作者E-mail:njiang@njnu.edu.cn