基于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