基于分布式拓撲的P2P矢量地理數據表示模型的研究

摘 要:目前對矢量數據分布式拓撲關系的研究較少，且矢量拓撲表示方法不利于P2P矢量數據的共享和傳輸。提出一種基于分布式拓撲的P2P矢量地理數據表示模型。該模型結合矢量分片合并的思想，通過擴展WKT(wellknown text)格式來維持矢量數據的拓撲關系。進一步，對該模型的性能進行了數學分析，并基于JTS(Java topology suite)實現了相應的原型系統。理論分析和實驗測試結果表明，該模型在選擇適當的分片粒度情況下，能使數據傳輸比率最小化，從而驗證了該模型提高數據傳輸效率和加快矢量數據分片、合并的有效性。

關鍵詞:對等計算技術; 矢量地理數據; 拓撲; 分片; 表示模型

中圖分類號:TP393文獻標志碼:A

文章編號:1001-3695(2010)06-2170-03

doi:10.3969/j.issn.1001-3695.2010.06.050

Study of distributed topology based representation model of

P2P vector geography data

WU Jiagao1， HUANG Lin1， ZOU Zhiqiang1， FENG Jiali2， HU Bin3

(1.Institute of Computer Technology， College of Computer， Nanjing University of Posts Telecommunications， Nanjing 210003， China; 

2. School of Geographic Oceanographic Sciences， Nanjing University， Nanjing 210093， China; 3. Ministry of Education Key Laboratory of Virtual Geographic Environment， Nanjing Normal University， Nanjing 210046， China)

Abstract:Recently， studies of distributed topologic relationship of vector data are few， and vector topological representation is not propitious to sharing and transmission of P2P vector data. This paper proposed a distributed topology based representation model of P2P vector geography data. Combined the model with vector division and union ideas， which extended WKT (wellknown text) format to maintain the topological relationship of vector data. In addition， analyzed performance of the model by mathematical method， and implemented a prototype system of the model based on the JTS (Java topology suite).The theoretical analysis and experimental test results show that the model can minimize ratio of data transmission with appropriate size of tile. Hence， the validity of the model， which can improve the efficiency data transmission and increase the speed of data division and union， is approved.

Key words:peertopeer(P2P) technology; vector geography data; topology; tile; representation model

0 引言

P2PGIS是對等計算(P2P)技術應用于地理信息系統(GIS)的產物，利用P2P技術在Web上發布地理信息，用戶能從網絡上下載地圖并進行各種信息檢索和處理，它的開放性和共享性大大方便了人們的使用。P2PGIS的出現主要是讓地理空間數據真正服務于公眾，它應盡量達到以下兩個目標:a)提供更人性化的功能強大的空間查詢;b)提高服務質量(QoS)，快速地響應用戶查詢。P2PGIS的一個主要特點是數據傳輸量大，而使用瀏覽器獲取地理服務的用戶又希望在使用系統的過程中有較高的響應率。因此，如何充分利用網絡帶寬，快速地發布和獲取用戶所需要的數據已經成為眾多學者研究的主要課題之一。

如今，P2PGIS方面的研究得到重視，研究的角度也是多層次的，如文獻[1]采用分層結構利用分布式對象技術構造GIS;文獻[2]對P2PGIS空間數據的管理問題開展了研究，但這些研究主要局限在服務器及系統結構的范圍之內。而矢量地理數據作為P2PGIS中的一個重要組成對象，它的組織管理機制對P2PGIS的系統性能具有不可忽視的影響。有關這方面的研究主要集中在矢量數據分布式索引和查找方面，一般是采用分布式的R樹[3]或四叉樹索引方案[4]。由于矢量數據通常包含有復雜的拓撲關系，與柵格數據在P2P環境下容易實現分片組織和傳輸不同[5]，在現有的P2PGIS系統中，一般都不對矢量數據對象進行分片或者在強行破壞拓撲關系的情況下進行分片，從而降低P2P矢量數據的傳輸效率，并導致一些矢量拓撲分析服務難以在P2P環境下展開。雖然已提出有基于GML的矢量數據模型[6，7]，并運用壓縮和簡化的方法提高數據傳輸的效率[8]，但矢量數據的傳輸仍然基于整個文件。有關P2PGIS環境下保持拓撲關系的矢量地理數據分片組織模型目前還鮮見報道。

本文在分布式拓撲環境下，從分布式矢量地理數據入手，對矢量數據進行處理。整個研究的核心是建立具有分布式拓撲關系的矢量數據表示模型。模型的功能主要有兩個:a)矢量地圖的分片，盡量簡化矢量拓撲的描述，減少分布式網絡上數據的傳輸量;b)保持拓撲描述的準確性和完整性，使矢量分片快速地合并成原圖。以此出發，本文提出了一種基于分布式拓撲的P2P矢量地理數據表示模型，該模型采用矢量分片合并的思想，通過擴展WKT格式來維持矢量數據的拓撲關系，并基于JTS[9]實現了該表示模型的原型系統。分析和測試結果表明，在適當的分片粒度下，該模型能提高數據的傳輸效率，加快矢量數據的分片和合并。

1 表示模型的建立

在分布式拓撲環境下建立模型，源于矢量數據分片和合并的思想，并受WKT格式的啟發。矢量數據的表示方法很重要，它是分布式數據組織、管理的前提。所謂表示也就是對矢量數據的描述，它必須是客觀的、準確的、可行的。

1.1 數據分片與合并的思想

傳統的矢量數據是基于整個矢量地圖文件的形式，如果用戶要查詢其中一部分范圍，必須把整個文件都下載下來，網絡不得不傳輸許多無用的數據。根據用戶訪問數據的局部性原理，如果把整個矢量地圖文件分成若干塊，每次只傳輸用戶所需的部分數據分片，而數據傳輸效率相應地提高。

但是，一個完整的矢量數據被分成塊狀后破壞了原來數據的完整性。為了保持數據的完整性，在分片中必須記錄矢量拓撲信息。矢量拓撲的描述有很多種方法，如被廣泛運用的地理標志語言(geography markup language， GML)。GML對地理數據的拓撲描述很全面，但是它的語義描述比較復雜，隨著分片的粒度增大，網絡的傳輸量反而增加得更多，并不能加快合并的速度，所以本文采用更簡潔的WKT格式來描述分布式矢量數據的拓撲信息。WKT是由OGC(open geospatial consortium)提出的一種用來表示地理矢量圖形的文本標記語言，它語法簡單、可讀性好、通用性強，已被PostGIS、Oracle、SpatiaLite 等許多數據庫系統所支持，并在JTS里得到應用。

1.2 WKT格式的定義

分布式P2P矢量數據表示模型的關鍵作用是記錄被分割矢量圖形的拓撲關系。這些拓撲信息必須明確地記錄幾何圖形中坐標點的構造順序，以及哪些是原坐標點、哪些是新產生的坐標點，因為它們是矢量數據合并的依據。本文將分片時產生的新坐標點記為〈newNode〉類型，并為其分配一個惟一的ID號——linkingID。合并時則根據幾何圖形的構造順序以及分片中的linkingID來組織坐標點，復原圖形。因此，擴展的分布式P2P矢量數據表示模型的WKT格式定義如下:

〈left angle bracket〉〈tile tagged text〉〈right angle bracket〉

{〈left angle bracket〉

〈geometry tagged text〉;

〈gmlID tagged text〉;

〈newNodeList tagged text〉;

〈right angle bracket〉}*

〈tile tagged text〉: =〈tileID tagged text〉;

〈envelope tagged text〉;

〈tileID tagged text〉:= tileID=〈tid〉

〈envelope tagged text〉:= env(〈point〉，〈point〉 )

〈gmlID tagged text〉:= gmlID=〈gid〉

〈newNodeList tagged text〉:= newNodeList= 1 |

〈newNode〉 {， 〈newNode〉 }*

〈newNode〉:= (〈linkingID〉，〈newNodeID〉，

〈description text〉)

〈linkingID〉:= integer literal

〈newNodeID〉:= integer literal

〈description text〉:= true | flase

〈left angle bracket〉:=‘<‘

〈right angle bracket〉:=‘>‘

〈point〉:=〈x〉〈y〉

〈tid〉:=tile id string literal

〈gid〉:=geometry id string literal

〈x〉:=double precision literal

〈y〉:=double precision literal

〈tile tagged text〉是分片中不可少的標簽。網絡上的查詢，主要是計算請求的坐標范圍與tile標簽里面的〈envelope tagged text〉范圍是否相交，只要與查找范圍相交的tile都要傳給請求用戶?！磘id〉是每個分片的惟一標志。在合并數據時，查找到的數據可能不完整，還需再次根據tile的〈tileID tagged text〉來查找矢量分片。

〈geometry tagged text〉保留了原WKT的格式?！磄mlID tagged text〉是Geometry的惟一標志;〈newNodeList tagged text〉是格式中的重點，它用來記錄分片時產生的一系列新的坐標點〈newNode〉的列表。其中，〈linkingID〉是新節點的ID，〈newNodeID〉是該點在分片圖形中的坐標順序索引號。〈description text〉用來描述新坐標點是否等于原坐標點(相等為true，不等為1)。這是因為分割線可能會經過原坐標點，所以新坐標點有可能與原坐標點相等。分片的合并則需按幾何圖形坐標點的構造順序依次進行。當遇到一個新坐標點時，若〈description text〉為1，則新坐標點就用另一分片中具有相同〈linkingID〉坐標點的下一跳坐標點代替;若〈description text〉為true，則該新坐標點仍然保留。

具體看實例，圖1中的幾何圖形C的坐標點構造順序是(a， e， d， c， b， a)。C被線段L分成A、B兩塊。則原圖形C以及分片圖形A、B的WKT表示格式如下所示。

幾何圖形C的tile格式:

#tile C

〈tiletileID=t0001; env(10 0， 87 95); 〉

〈

POLYGON (47 95， 87 58， 72 0， 23 0， 8 58， 47 95);

gmlID=g0001;

newNodeList=1;

〉

幾何圖形A、B的tile格式:

#tile A

〈tiletileID=t0002; env(8 50， 87 95);〉

〈

POLYGON(47 95， 87 58， 85 50， 10 50， 8 58， 47 95 );

gmlID=g0001;

newNodeList=(0，3，1)，(1，4，1);

〉

#tile B

〈tiletileID=t0003; env(10 0， 85 50);〉

〈

POLYGON(85 50， 72 0， 23 0， 10 50， 85 50 );

gmlID=g0001;

newNodeList=(0，1，1)， (1，4， 1);

〉

由圖1和tile格式可見，對于C來說，點f(85 50)、g(10 50)是因分片生成的新坐標點，它們屬于newNode類型，在A、B的NewNodeList中同時添加點f和g。分片合并從A中的點a(47 95)開始，接著是e(87 58)。當遇到新坐標點f(85 50)，則用B中f的下一跳d(72 0)來替換它，因為f與原坐標不相等。同理，接著構造點c(72 0)、b(8 58)和a(47 95)，成功復原分片前的圖形。

2 原型系統的實現

為了驗證上述表示模型的正確性，本文基于JTS設計實現該模型的原型系統。圖2是一個該原型系統的體系結構圖。該系統結構中的數據分片和合并算法集成到JTS轉換器中，轉換器的兩頭是待轉換和已轉換的矢量數據。

系統工作過程為:給定一幅Shape格式的地圖，經過WKT轉換器得到一個用WKT描述的矢量地圖文件。矢量數據的分片和合并算法集成到JTS轉換器中。在JTS轉換器中，首先對矢量地圖進行初始化，即矢量數據分片、劃分以四叉樹的形式進行。從根節點開始，將原矢量地圖一分為四，這四個地圖分片再分為十六個小分片，直到四叉樹的f層為止(f從0開始計算)。定義f為分片的粒度，則原矢量地圖被分為4f個tile文件。每一次劃分都要更新newNodeList列表，記錄被分割的圖形，保持它們之間的拓撲關系。這些文件在系統初始化后，被發布到網絡中。Tile的合并也由JTS轉換器完成，當找到用戶所需的tile文件時，被輸入到JTS中，JTS把包含矢量數據的tile文件讀入轉換器中進行合并顯示繪出。具體的數據分片和合并算法可采用不同方法實現，但這非本文研究的重點，故不再贅述。

3 模型的分析

本文用數學方式進一步分析矢量數據表示模型，以驗證其在分布式拓撲環境下是否提高了數據的傳輸效率。

設服務器提供的初始矢量地圖面積為S0，用戶請求的矢量地圖面積為Sq，分片之前的初始數據量為D0;令f為分片的粒度，則總的tile分片數為4f，每個tile的面積為St=S/4f，每個tile的數據量為Dt=D0/4f+Δ(f)，Δ(f)是分片時加入〈newNodeList〉等信息使每個tile分片增加的數據量。用戶請求的tile數n=「Sq/St，此時網絡上數據的傳輸量為Dq=n×Dt，則

Dq=「Sq×4f/S×(D0/4f+Δ(f))(1)

設請求的矢量地圖面積比例α=Sq/S0，則可定義數據傳輸比率:

γ=實際傳輸數據量理想傳輸數據量(2)

其中:實際傳輸數據量即Dq，理想傳輸數據量為用戶所請求的有效數據量α#8226;D0，則:

γ=Dqα#8226;D0=「4fα4fα#8226;1+Δ(f)D0/4f(3)

由式(3)可見，γ≥1，即通常情況實際傳輸數據量要比用戶所需的有效數據量大。設A(f)=「4fα4fα，B(f)=Δ(f)D0/4f。容易驗證A(f)/A(f+1)≥1。所以隨著分片粒度f的增加，γ有遞減的趨勢，但同時分片粒度的提高將增加Δ(f)在原分片數據中的比例，即數據增加率B(f)隨著f的增大而增大。因此，對一個特定的地圖來說，可能存在一個適當的值f使γ最小化。

4 模型的測試

對模型分析之后，需要真實的數據來進一步說明模型的特性。選一個特定的矢量數據集D0=2 490 KB，對其進行分片處理并測試各數據參數，如表1所示。

表1 矢量數據表

f

參數

D0/4f/KBDt/KBΔ(f)/KBB(f)

1622.50632.5010.000.016 1

2155.63160.004.370.028 1

338.9140.561.650.042 6

49.7311.331.600.164 7

由表1可驗證，B(f)隨著f的增加而增加。假設所有分片文件大小相同，由表1和式(3)可計算α與γ的相關曲線，如圖3所示。

從圖3可以看出，分片后的數據傳輸量與分片之前的數據量(f=0)相比有明顯的減少，說明矢量分片要比不分片的優越。當用戶的請求面積比較小時，分片粒度越大傳輸量越小;但隨著請求面積的增大，分片粒度越大傳輸量反而越大，所以f的取值要適當。為了更清楚說明這一點，本文給出f與γ的相關曲線，如圖4所示。圖4中四條曲線對應不同的面積比例，從圖中可以看出，當分片粒度f=3時傳輸比率最小，這與理論分析的結果一致。

因此，最佳分片粒度的選擇可根據式(3)，取f使γ為最小值。由于從數學上直接求γ的最小值比較困難，建議按以下方法選擇最佳分片粒度:a)基于本文的矢量地理數據表示模型，對給定的矢量數據集，按不同分片粒度進行分片，得到D0和Δ(f)等參數;b)設定一個合適的α(如根據數據請求范圍的分布，取其平均值)，將前面獲得的參數帶入式(3)，計算γ;c)選擇使γ取最小值的分片粒度f即可。另外，還注意到式(3)本身也是通過理論抽象和假設得到的，與實際情況會有一定誤差，但這并不影響理論模型的有效性。事實上，可以先根據由式(3)得到的最佳分片粒度建立原型系統，再通過實際運行和測試，對理論最佳分片粒度進行微調，從而實現系統性能的優化。

由以上測試和分析結果表明，采用擴展的WKT格式的矢量地理數據表示模型是可行的，能夠很好地利用P2P網絡的共享機制，減少數據傳輸量，實現數據的快速分片與合并。

5 結束語

P2P網絡為各領域的研究帶來了廣闊的前景， P2PGIS更是P2P網絡中一個很好的例子。在此基礎上，本文著重研究了矢量地圖的分片技術，并分析P2P網絡的特性，結合用戶對數據請求的快速響應需求，最終構造了一個基于分布式拓撲的P2P矢量地理數據的表示模型。這種表示模型能夠根據請求數據的大小，動態地調整網絡中的數據量，盡可能地減少網絡負載，提高傳輸效率，保證數據合并的正確性。該模型比較簡單，可以進一步在此基礎上改進分片和合并算法，提高原型系統的性能。

參考文獻:

[1]劉興權，嚴米.基于J2EE和XML的分布式GIS研究[J].地理空間信息，2007，5(3):12-14.

[2]劉德剛，向金海，周剛.基于P2P的Web GIS系統架構設計[J] .計算機與現代化，2007(11):129-131.

[3]MONDAL A， YI Lifu， KITSUREGAWA M. P2PRtree: an Rtree based spatial index for peertopeer environments[C]//Proc of International Workshop on PeertoPeer Computing and Databases， 2004. Greece: Heraklion， 2004:516 -525.

[4]TANIN E， HARWOOD A， SAMET H. Using a distributed quad tree index in peertopeer networks[J]. The VLDB Journal， 2007， 16(2): 165- 178.

[5]BERGAMINI J A， Dr HAUNGS M. Enabling P2P cooperative WMS proxy caching and prefetching in an educational environment[C]//Lecture Notes in Geoinformation and Cartography.Berlin: Springer，2007:1-14.

[6]高波，郭朝珍，丁善鏡.基于GML矢量圖層分割的空間數據分布式協同處理[J].計算機應用，2009，29(1):297-300，303.

[7]駱炎民，涂超.基于GML的WebGIS地理信息建模[J].計算機工程與應用，2004，40(15):218-221.

[8]楊建宗，楊崇俊，明冬萍，等.WebGIS系統中矢量數據的壓縮與化簡方法綜述[J]. 計算機工程與應用，2004，40(32):36-38，92.

[9]VIVID Solutions. JTS Topology Suite Technical Specifica tions v1.4 [EB/OL]. (2003-10-17) [2009-11-8]. http://www. vividsolutions. com/jts/jtshome.htm.