基于平衡興趣樹的Ｐ２Ｐ空間數(shù)據(jù)服務(wù)調(diào)度

摘 要:構(gòu)建空間信息網(wǎng)格要求解決海量地理空間數(shù)據(jù)傳輸問題，通過分析空間數(shù)據(jù)服務(wù)特征，對(duì)空間數(shù)據(jù)設(shè)計(jì)了多級(jí)網(wǎng)格索引，利用P2P技術(shù)設(shè)計(jì)了基于平衡興趣樹的空間數(shù)據(jù)服務(wù)網(wǎng)絡(luò)模型。算法按peer興趣區(qū)對(duì)申請(qǐng)空間數(shù)據(jù)服務(wù)的peer進(jìn)行組織，將peer間路由關(guān)系動(dòng)態(tài)組織成一種新的拓?fù)浣Y(jié)構(gòu)——平衡興趣樹。算法可動(dòng)態(tài)維護(hù)網(wǎng)格熱度表中數(shù)據(jù)塊的熱度，通過熱度表可快速發(fā)現(xiàn)網(wǎng)格數(shù)據(jù)塊在P2P網(wǎng)絡(luò)中的位置并下載，從而減輕了空間數(shù)據(jù)服務(wù)器壓力，提高了服務(wù)效率。

關(guān)鍵詞:對(duì)等網(wǎng); 分布式; 平衡興趣樹; 空間數(shù)據(jù)服務(wù); 空間信息網(wǎng)格

中圖分類號(hào):TP319文獻(xiàn)標(biāo)志碼:A

文章編號(hào):1001-3695(2009)09-3414-04

doi:10.3969/j.issn.1001-3695.2009.09.060

Spatial data service scheduling algorithm of P2P networksbased on balance interest tree

HOU Zhe-wei1，2， WANG Qing-shan1， DING Lin3， REN Liu-cheng2

(1.Institute of Surveying Mapping， PLA Information Engineering University， Zhengzhou 450052， China; 2.Air Force Command College， Beijing 100097， China; 3.Institute of Remote Sensing Application， Chinese Academy of Sciences， Beijing 100101， China)

Abstract:The transport problem of vast spatial data through Internet must be solved in establishing spatial information grid (SIG). Designed the multilevel grid index of spatial data and a network model of spatial data service based on balance interest tree by analyzing the basic character of spatial data service and using P2P technology. According to the interesting region of peers， effectively organized the peers requested spatial data service by the algorithm， and transformed the routing relationship of peers to a new topology structure: dynamic balance interest tree. This algorithm can maintain the degree of heat of data grid in the heat table， and can find the location of data grid in the P2P network quickly by the heat table and download， so the pressure of spatial data service and improves the efficiency of service.

Key words:P2P(peer-to-peer); distributed; balance interest tree; spatial data service; spatial information grid

0 引言

空間數(shù)據(jù)服務(wù)(spatial data service，SDS)作為空間信息網(wǎng)格(spatial information grid，SIG)的重要服務(wù)，是網(wǎng)格GIS的數(shù)據(jù)源，其數(shù)據(jù)傳輸機(jī)制直接影響空間信息網(wǎng)格服務(wù)效率。文獻(xiàn)[1，2]認(rèn)為在數(shù)據(jù)傳輸過程中基于GML對(duì)空間數(shù)據(jù)和屬性數(shù)據(jù)進(jìn)行描述，以解決服務(wù)間的數(shù)據(jù)共享問題，但GML對(duì)于海量的地理空間數(shù)據(jù)，特別是遙感影像數(shù)據(jù)傳輸不能很好地解決。文獻(xiàn)[2]提出當(dāng)數(shù)據(jù)量變大時(shí)，通過構(gòu)建多個(gè)數(shù)據(jù)庫(kù)服務(wù)器管理數(shù)據(jù)，以分散多用戶請(qǐng)求時(shí)對(duì)服務(wù)器造成的壓力。在數(shù)據(jù)服務(wù)器端構(gòu)建空間信息的多分辨率模型[3，4]和將數(shù)據(jù)模型壓縮后生成漸進(jìn)壓縮碼流[5]可以提高網(wǎng)絡(luò)傳輸效率，這兩種方法可解決單客戶端與服務(wù)器間的數(shù)據(jù)傳輸問題;多用戶訪問數(shù)據(jù)服務(wù)器時(shí)沒有協(xié)作機(jī)制，勢(shì)必會(huì)造成服務(wù)器負(fù)擔(dān)，服務(wù)器性能和網(wǎng)絡(luò)帶寬將成為空間數(shù)據(jù)服務(wù)瓶頸。

利用peer-to-peer(P2P)技術(shù)可有效解決空間數(shù)據(jù)服務(wù)中數(shù)據(jù)傳輸問題，它充分利用peer存儲(chǔ)和計(jì)算資源，各對(duì)等實(shí)體間進(jìn)行有機(jī)、自由連接[6]，可用于大量計(jì)算和數(shù)據(jù)資源的共享[7]，系統(tǒng)伸縮性強(qiáng)，適合海量數(shù)據(jù)管理和共享[8]。在空間領(lǐng)域也提出了一些P2P環(huán)境下空間信息服務(wù)的系統(tǒng)原型[9，10]。P2P網(wǎng)絡(luò)模型結(jié)構(gòu)決定了P2P系統(tǒng)調(diào)度策略，目前主要有非結(jié)構(gòu)化和結(jié)構(gòu)化方式[11]。在非結(jié)構(gòu)化方式中，peer存儲(chǔ)自身的信息和信息的索引，peer通過泛洪式和擴(kuò)展環(huán)來進(jìn)行信息查找，效率相對(duì)不高;在結(jié)構(gòu)化方式中，peer只存儲(chǔ)特定的信息或特定信息的索引，有效地避免了非結(jié)構(gòu)化中的泛洪式查找，但關(guān)鍵節(jié)點(diǎn)的失效容易對(duì)系統(tǒng)穩(wěn)定造成影響。在Gnutella和文獻(xiàn)[12]中，對(duì)節(jié)點(diǎn)進(jìn)行了等級(jí)劃分，節(jié)點(diǎn)負(fù)責(zé)一定的域，減少了查找范圍，本文對(duì)該結(jié)構(gòu)進(jìn)行了一定優(yōu)化。

本文通過分析SDS基本特征，設(shè)計(jì)了基于平衡興趣樹(balance interest tree，BIT)的P2PSDS網(wǎng)絡(luò)模型，根據(jù)熱度表的熱度分布動(dòng)態(tài)進(jìn)行P2P SDS調(diào)度。通過性能分析，本文提出調(diào)度方法可以使申請(qǐng)SDS的peer以較快速度下載空間數(shù)據(jù)，降低服務(wù)器負(fù)擔(dān)，提高服務(wù)效能。

1 空間數(shù)據(jù)服務(wù)

SDS通過將空間數(shù)據(jù)集成存儲(chǔ)到一臺(tái)或多臺(tái)數(shù)據(jù)服務(wù)器上，實(shí)現(xiàn)地理空間數(shù)據(jù)共享和分布。為保證數(shù)據(jù)安全，通常構(gòu)建空間數(shù)據(jù)庫(kù)系統(tǒng)，根據(jù)其數(shù)據(jù)訪問組件構(gòu)建遠(yuǎn)程數(shù)據(jù)訪問中間件或開發(fā)為Web服務(wù)——空間數(shù)據(jù)服務(wù)，以提供給遠(yuǎn)程應(yīng)用或其他服務(wù)調(diào)用，這解決了一定數(shù)量用戶對(duì)空間數(shù)據(jù)的并發(fā)訪問問題。

與流媒體服務(wù)和P2P文件下載相比，空間數(shù)據(jù)服務(wù)有其自身的特點(diǎn):

a)服務(wù)內(nèi)容不同。SDS主體是地球空間數(shù)據(jù)，包括海量遙感影像及各種地理信息，有空間特征、屬性特征和時(shí)間特征，通常按照空間區(qū)域?qū)臻g數(shù)據(jù)進(jìn)行分布管理，內(nèi)部關(guān)系復(fù)雜。

b)服務(wù)方式不同。SDS提供數(shù)據(jù)下載及查詢等服務(wù)，服務(wù)器根據(jù)用戶的興趣范圍進(jìn)行響應(yīng)，通過數(shù)據(jù)檢索模塊獲得請(qǐng)求的空間數(shù)據(jù)。針對(duì)客戶請(qǐng)求可以直接返回空間數(shù)據(jù)或處理成圖像后返回，由客戶端完成拼接，顯示為二維電子地圖或三維仿真場(chǎng)景。

c)服務(wù)對(duì)象不同。SDS作為SIG的關(guān)鍵節(jié)點(diǎn)，對(duì)外公開遠(yuǎn)程訪問接口，遠(yuǎn)程應(yīng)用通過訪問該接口獲取需要的空間數(shù)據(jù)，其服務(wù)對(duì)象主要有瀏覽器GIS組件、遠(yuǎn)程客戶端GIS應(yīng)用程序和SIG服務(wù)節(jié)點(diǎn)。

基于P2P的SDS要充分考慮SDS以上特點(diǎn)，設(shè)計(jì)合理的網(wǎng)絡(luò)模型對(duì)peer任務(wù)進(jìn)行合理分配

及調(diào)度。

2 基于BIT的P2PSDS調(diào)度策略

2.1 P2P空間數(shù)據(jù)服務(wù)架構(gòu)

本文設(shè)計(jì)了P2P空間數(shù)據(jù)服務(wù)(P2PSDS)的體系結(jié)構(gòu)，如圖1所示。P2PSDS網(wǎng)絡(luò)中分為源節(jié)點(diǎn)和普通節(jié)點(diǎn)peer。節(jié)點(diǎn)間的網(wǎng)絡(luò)通信通過P2PSDS中間件實(shí)現(xiàn)，它具有空間數(shù)據(jù)下載接口、熱度表(定義見2.2節(jié))更新接口、peer資源定位接口、peer管理接口等。

本文采用在源節(jié)點(diǎn)對(duì)空間數(shù)據(jù)進(jìn)行多級(jí)網(wǎng)格劃分，不同級(jí)別的網(wǎng)格要建立統(tǒng)一編碼，網(wǎng)格內(nèi)部空間目標(biāo)具有惟一編碼，以保證P2PSDS中數(shù)據(jù)的全局性和一致性。

編碼方法要求能夠做到將不同比例尺層次的空間信息以一個(gè)一體化的數(shù)據(jù)庫(kù)進(jìn)行統(tǒng)一存儲(chǔ)與管理[13]。由于空間目標(biāo)可能跨越相鄰的多個(gè)網(wǎng)格，數(shù)據(jù)庫(kù)允許不同網(wǎng)格關(guān)聯(lián)同一個(gè)空間目標(biāo)，每一個(gè)網(wǎng)格只關(guān)聯(lián)其內(nèi)部空間目標(biāo)的惟一編碼。由于矢量數(shù)據(jù)具有跨區(qū)域性，會(huì)造成網(wǎng)格數(shù)據(jù)塊下載時(shí)不同數(shù)據(jù)塊間空間數(shù)據(jù)冗余，本文提出可以對(duì)一些數(shù)據(jù)量較大、跨網(wǎng)格較多、數(shù)據(jù)不用頻繁更新的數(shù)據(jù)，如地貌、水系等數(shù)據(jù)，結(jié)合地貌數(shù)據(jù)建立的數(shù)字高程模型，生成暈渲圖像。將高程模型、暈渲圖像、影像數(shù)據(jù)和其他矢量數(shù)據(jù)以網(wǎng)格為單位進(jìn)行管理，從而減少網(wǎng)格間數(shù)據(jù)的冗余下載。網(wǎng)格劃分示例如表1所示，網(wǎng)格數(shù)據(jù)容量限制在64～256 KB，網(wǎng)格編碼gridID 通過函數(shù)gridCode(級(jí)號(hào)、經(jīng)度、緯度)計(jì)算。P2PSDS數(shù)據(jù)傳輸以網(wǎng)格為單位傳輸。Peer以網(wǎng)格為單位建立主存區(qū)(MD)和緩存區(qū)(LD)，分別用于空間數(shù)據(jù)瀏覽和P2P網(wǎng)共享。主存與緩存為空間上連續(xù)的一個(gè)矩形區(qū)域，區(qū)域內(nèi)數(shù)據(jù)塊網(wǎng)格等級(jí)相同，大小為網(wǎng)格行列數(shù)的乘積。緩存大小與peer性能與2.4節(jié)定義2中的劃分函數(shù)Ni=f(i)有關(guān)。緩存設(shè)有中心原點(diǎn)塊，允許各peer緩存數(shù)據(jù)塊冗余出現(xiàn)在其他peer緩存中。 2.2 基于BIT的P2P網(wǎng)絡(luò)劃分方案

下面給出熱度表的基本結(jié)構(gòu)及節(jié)點(diǎn)任務(wù)區(qū)、節(jié)點(diǎn)興趣區(qū)、BIT、子樹任務(wù)區(qū)基本概念。

為反映以網(wǎng)格為單位的數(shù)據(jù)塊在P2P網(wǎng)絡(luò)中的副本數(shù)及擁有該副本的節(jié)點(diǎn)信息，本文設(shè)計(jì)了網(wǎng)格熱度表進(jìn)行副本資源快速發(fā)現(xiàn)及定位。網(wǎng)格熱度表是一個(gè)hash表，其主鍵值為hash(gridID)，具體內(nèi)容為網(wǎng)格數(shù)據(jù)塊所關(guān)聯(lián)的信息結(jié)構(gòu)，如下所示。GridID占12 Byte，前兩位為級(jí)數(shù)，后十位分別為經(jīng)度和緯度方向行列號(hào)，如XX XXXXX XXXXX。

class gridStruct

{

char gridID[12]; //數(shù)據(jù)塊編碼

list〈peer〉 peerList;//數(shù)據(jù)塊對(duì)應(yīng)peer列表

int gridHot;//數(shù)據(jù)塊熱度

}

class peer

{

int cpu_ability; //CPU能力，4 Byte

string IP;//網(wǎng)絡(luò)地址，16 Byte

int port;//端口號(hào)，4 Byte

}

節(jié)點(diǎn)任務(wù)區(qū)是指緩存區(qū)所包含的網(wǎng)格數(shù)據(jù)塊的空間經(jīng)緯度范圍;節(jié)點(diǎn)興趣區(qū)是指主存中所包含的網(wǎng)格數(shù)據(jù)塊的空間經(jīng)緯度范圍。

P2P空間數(shù)據(jù)服務(wù)要求網(wǎng)絡(luò)中有足夠網(wǎng)格數(shù)據(jù)塊副本，對(duì)高訪問的數(shù)據(jù)塊有足夠熱度。圖2為BIT網(wǎng)絡(luò)拓?fù)洹ＴO(shè)peeri任務(wù)區(qū)為Si，peeri根的子樹peer_treei任務(wù)區(qū)為Ri，peer_treej為peer_treei的子樹，則有Ri=∪Rj。圖中實(shí)線雙箭頭表示BIT父子關(guān)系，虛線部分為BIT兄弟關(guān)系。對(duì)檢測(cè)不到父節(jié)點(diǎn)的兄弟節(jié)點(diǎn)可以推選出網(wǎng)絡(luò)信譽(yù)度最高的節(jié)點(diǎn)擔(dān)任父節(jié)點(diǎn)，重新帶領(lǐng)子樹及時(shí)加入網(wǎng)絡(luò)。

Peer根據(jù)P2PSDS網(wǎng)絡(luò)peer興趣區(qū)范圍和網(wǎng)格熱度表的熱度分布，動(dòng)態(tài)加入到BIT中，然后為peer分配合理的任務(wù)區(qū)和以peer為根的子樹的任務(wù)區(qū)。Peer通過向父節(jié)點(diǎn)發(fā)送任務(wù)區(qū)和興趣區(qū)的范圍，在網(wǎng)格熱度表中查找擁有該區(qū)域的網(wǎng)格數(shù)據(jù)塊所在的節(jié)點(diǎn)信息。若查找不到，由該peer節(jié)點(diǎn)按照先父節(jié)點(diǎn)再兄弟節(jié)點(diǎn)的順序發(fā)送泛洪消息，找到后由具有該數(shù)據(jù)塊的節(jié)點(diǎn)負(fù)責(zé)與請(qǐng)求數(shù)據(jù)的節(jié)點(diǎn)建立連接并下載數(shù)據(jù)。Peer定期向父節(jié)點(diǎn)發(fā)送熱度表更新消息，更新父節(jié)點(diǎn)子樹任務(wù)區(qū)熱度表，直至更新至源節(jié)點(diǎn)。

源節(jié)點(diǎn)功能有數(shù)據(jù)管理和檢索、網(wǎng)格數(shù)據(jù)塊打包、熱度表更新與維護(hù)、網(wǎng)格數(shù)據(jù)塊資源發(fā)現(xiàn)、管理子節(jié)點(diǎn)和子節(jié)點(diǎn)任務(wù)分配。普通節(jié)點(diǎn)功能有完成任務(wù)區(qū)數(shù)據(jù)下載、管理子節(jié)點(diǎn)和子節(jié)點(diǎn)任務(wù)分配、數(shù)據(jù)塊打包、節(jié)點(diǎn)熱度表更新與維護(hù)、網(wǎng)格數(shù)據(jù)塊資源發(fā)現(xiàn)、興趣區(qū)的網(wǎng)格數(shù)據(jù)塊下載、興趣區(qū)空間數(shù)據(jù)應(yīng)用。

2.3 基于BIT的P2P網(wǎng)絡(luò)調(diào)度

Peer網(wǎng)格熱度表反映以該節(jié)點(diǎn)為樹根的子樹所包含的數(shù)據(jù)塊熱度，是新節(jié)點(diǎn)加入興趣樹的依據(jù)。設(shè)數(shù)據(jù)塊的最高熱度gridHot為R，最低熱度為1。隨著P2P網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)增加，為滿足系統(tǒng)需要，數(shù)據(jù)塊的熱度會(huì)逐步提高。

2.3.1 節(jié)點(diǎn)加入

節(jié)點(diǎn)加入P2PSDS網(wǎng)絡(luò)時(shí)任務(wù)區(qū)域和興趣區(qū)域一致，圖3為加入過程，圖中peer加入節(jié)點(diǎn)子樹過程是檢索子節(jié)點(diǎn)不足的節(jié)點(diǎn)的過程。

節(jié)點(diǎn)加入要考慮以下因素:節(jié)點(diǎn)熱度表、允許擁有子節(jié)點(diǎn)個(gè)數(shù)、節(jié)點(diǎn)子樹任務(wù)區(qū)。節(jié)點(diǎn)根據(jù)平均算法將該peer_tree任務(wù)區(qū)平均分為N組(源節(jié)點(diǎn)中不同級(jí)別數(shù)據(jù)塊統(tǒng)一參與分配，一組數(shù)據(jù)塊必須屬于相同級(jí)別)，作為新加入節(jié)點(diǎn)的子樹任務(wù)區(qū)，每組數(shù)據(jù)塊數(shù)不能小于節(jié)點(diǎn)緩存數(shù)據(jù)塊數(shù)，當(dāng)達(dá)到臨界值時(shí)系統(tǒng)不再劃分。設(shè)每個(gè)分組可最多有max個(gè)子樹將其設(shè)為任務(wù)區(qū)，則每個(gè)節(jié)點(diǎn)最多可包含子節(jié)點(diǎn)個(gè)數(shù)為max×N，多個(gè)兄弟節(jié)點(diǎn)樹任務(wù)區(qū)相同從一定程度保證了數(shù)據(jù)塊熱度。

2.3.2 建立節(jié)點(diǎn)peeri的緩存

Peeri入網(wǎng)后，按照先父節(jié)點(diǎn)再父節(jié)點(diǎn)兄弟的泛洪原則依次向上發(fā)送消息，peer收到消息后檢測(cè)子樹任務(wù)區(qū)熱度表，找到后由擁有數(shù)據(jù)的節(jié)點(diǎn)通知peeri建立連接并下載。如果沒有能夠提供的可連接節(jié)點(diǎn)，則需要連接源節(jié)點(diǎn)下載對(duì)應(yīng)數(shù)據(jù)塊的數(shù)據(jù)，在連接節(jié)點(diǎn)過程中如果遇到被連接節(jié)點(diǎn)網(wǎng)絡(luò)忙時(shí)，則進(jìn)入等待隊(duì)列，等到自己次序后方可建立連接并下載數(shù)據(jù)塊。

節(jié)點(diǎn)應(yīng)定期向父節(jié)點(diǎn)發(fā)送熱度表更新消息，在熱度表中添加數(shù)據(jù)塊對(duì)應(yīng)的節(jié)點(diǎn)信息，提高數(shù)據(jù)塊熱度。由于需要更新的信息只是數(shù)據(jù)塊編碼的hash值和節(jié)點(diǎn)的基本信息24 Byte，由于數(shù)據(jù)塊是相鄰的，只需發(fā)送一個(gè)中心數(shù)據(jù)塊，其他數(shù)據(jù)塊的編碼可以由接收信息的節(jié)點(diǎn)完成計(jì)算，則更新熱度表矩陣時(shí)的網(wǎng)絡(luò)數(shù)據(jù)量為12+24=36 Byte，不會(huì)占用太多帶寬。由于peer對(duì)不能給于服務(wù)節(jié)點(diǎn)采取排隊(duì)處理，對(duì)網(wǎng)絡(luò)上有大量節(jié)點(diǎn)同時(shí)涌入時(shí)熱度表更新情況可以得到控制。

2.3.3 更新主存

Peer首先檢測(cè)peer緩存，若緩存可滿足興趣區(qū)需求，則直接進(jìn)行數(shù)據(jù)轉(zhuǎn)存。

主存數(shù)據(jù)塊下載方法主要通過向BIT中與peer相關(guān)聯(lián)的節(jié)點(diǎn)(包括興趣區(qū)網(wǎng)格數(shù)據(jù)塊所關(guān)聯(lián)的節(jié)點(diǎn))和源節(jié)點(diǎn)發(fā)送泛洪消息，收到消息的節(jié)點(diǎn)檢測(cè)節(jié)點(diǎn)熱度表，找不到時(shí)，繼續(xù)與關(guān)聯(lián)的其他節(jié)點(diǎn)泛洪，直至找到后通知相關(guān)節(jié)點(diǎn)給peer發(fā)送連接消息，peer與最先返回消息的節(jié)點(diǎn)建立連接，并排隊(duì)等待數(shù)據(jù)塊下載。

2.3.4 節(jié)點(diǎn)退出

節(jié)點(diǎn)退出時(shí)，系統(tǒng)強(qiáng)制節(jié)點(diǎn)延長(zhǎng)一定用戶可忍受的退出時(shí)間。在退出時(shí)間內(nèi)，用戶委托一個(gè)子節(jié)點(diǎn)頂替該節(jié)點(diǎn)在P2P網(wǎng)絡(luò)中的位置，同時(shí)向父節(jié)點(diǎn)發(fā)出熱度表更新消息，刪除退出的peer緩存數(shù)據(jù)塊對(duì)應(yīng)的熱度表中該節(jié)點(diǎn)的信息。對(duì)兄弟環(huán)中的節(jié)點(diǎn)在找不到父節(jié)點(diǎn)時(shí)，兄弟環(huán)委托信譽(yù)高的節(jié)點(diǎn)擔(dān)任父節(jié)點(diǎn)，并更新該節(jié)點(diǎn)樹的任務(wù)區(qū)，按照任務(wù)區(qū)重新加入BIT。為確保熱度表可靠性，系統(tǒng)建立舉報(bào)機(jī)制，每個(gè)節(jié)點(diǎn)利用空閑時(shí)間在進(jìn)行數(shù)據(jù)塊下載過程中，如果連接的節(jié)點(diǎn)在連續(xù)兩次均連接不上時(shí)，則向其他關(guān)聯(lián)的節(jié)點(diǎn)發(fā)送舉報(bào)信息，被舉報(bào)的節(jié)點(diǎn)在熱度表中的關(guān)聯(lián)應(yīng)當(dāng)刪除，以減少對(duì)應(yīng)數(shù)據(jù)塊熱度。

2.4 P2P空間數(shù)據(jù)塊分布和熱度分析

為保證P2P空間數(shù)據(jù)服務(wù)系統(tǒng)正常運(yùn)行，每個(gè)數(shù)據(jù)塊必須有足夠的副本數(shù)，且各數(shù)據(jù)塊冗余度不應(yīng)波動(dòng)太大，整體熱度達(dá)到一定程度后保持平衡。系統(tǒng)通過設(shè)置數(shù)據(jù)塊分組的最大子節(jié)點(diǎn)數(shù)max以提高數(shù)據(jù)冗余度。由于節(jié)點(diǎn)興趣區(qū)會(huì)出現(xiàn)重合，在P2P網(wǎng)絡(luò)建立之初，高興趣區(qū)的冗余度首先提高，熱度表部分區(qū)域會(huì)提前變熱。當(dāng)高興趣區(qū)熱度達(dá)到用戶要求時(shí)，系統(tǒng)通過動(dòng)態(tài)監(jiān)測(cè)熱度表的熱度均衡狀態(tài)，對(duì)新加入的peer的任務(wù)區(qū)和peer_tree任務(wù)區(qū)進(jìn)行動(dòng)態(tài)調(diào)整分配，實(shí)現(xiàn)熱度表熱度均衡。

根據(jù)BIT的服務(wù)調(diào)度策略，本文給出以下定義計(jì)算調(diào)度策略中各參數(shù)的關(guān)系。

定義1 設(shè)空間數(shù)據(jù)大小為S，源節(jié)點(diǎn)數(shù)據(jù)塊個(gè)數(shù)為num，網(wǎng)格單元平均大小為K=S/num。

定義2 BIT各節(jié)點(diǎn)子樹按照其層次劃分等級(jí)i=(0，1，2，…，m)，源節(jié)點(diǎn)為第0級(jí)，葉節(jié)點(diǎn)為第m級(jí)。不同等級(jí)節(jié)點(diǎn)樹任務(wù)區(qū)劃分大小Ni=f(i)。設(shè)每一組數(shù)據(jù)允許有max個(gè)子節(jié)點(diǎn)將一個(gè)劃分組作為自己的子樹任務(wù)區(qū)，則對(duì)于第i級(jí)的節(jié)點(diǎn)子樹最多可有Ni×max個(gè)子節(jié)點(diǎn)。

定義3 設(shè)網(wǎng)絡(luò)peer(包括源節(jié)點(diǎn)root)總數(shù)為peerNum，第i級(jí)節(jié)點(diǎn)個(gè)數(shù)為peerNumi。Peer緩存大小為L(zhǎng)DSize，主存大小為MDSize。數(shù)據(jù)塊最低穩(wěn)定熱度為hot。

通過以上定義、分塊方案函數(shù)獲得以下公式:

(peerNum-1)×LDSize≥(hot-1)×num(1)

各級(jí)節(jié)點(diǎn)總數(shù)分別為

peerNum0=1

peerNum1=f(0)×max

peerNum2=peerNum1×f(1)×max

……

peerNumm-1=peerNumm-2×f(m-2)×max

peerNumm=peerNumm-1×f(m-1)×max

peerNumm=maxm×m-1i=1f(i)(2)

peerNum≤∑mi=0peerNumi=1+∑mi=0maxi×i-1j=0f(j)

(3)

(hot-1)×num/LDSize≤∑mi=0maxi×i-1j=0f(j)(4)

LDSize=num/m-1i=0f(i)≤num/m-1i=0f(i)(5)



根據(jù)以上定義和公式綜合得出最低穩(wěn)定熱度hot和劃分函數(shù)關(guān)系式如下:

(hot-1)×m-1i=0f(i)≤∑mi=0maxi×i-1j=0f(j)

(6)



當(dāng)hot、S和K已知，劃分函數(shù)值和max取值滿足式(6)時(shí)，該設(shè)置可以使熱度表數(shù)據(jù)塊平均熱度達(dá)到最低要求hot。

3 性能分析

模擬測(cè)試中源節(jié)點(diǎn)為Dell PowerEdge 840服務(wù)器，處理器個(gè)數(shù)為1，類型為Intel Pentium D，主頻3000 MHz，內(nèi)存1 GB，操作系統(tǒng)Windows Server 2003;網(wǎng)絡(luò)協(xié)議為TCP/IP。設(shè)源節(jié)點(diǎn)空間數(shù)據(jù)為512 MB，數(shù)據(jù)分塊平均約為64 KB，數(shù)據(jù)塊共8 192塊，劃分方案如表2所示。

表2 Peer空間數(shù)據(jù)塊劃分方案表

節(jié)點(diǎn)等級(jí)i0123

劃分函數(shù)f(i)4222

子樹任務(wù)區(qū)大小2 0481 024512256

根據(jù)以上參數(shù)，針對(duì)普通SDS和基于BIT的P2PSDS，通過測(cè)試兩種方式主存刷新頻率來比較調(diào)度效率。在局域網(wǎng)內(nèi)采用兩臺(tái)Dell Vostro200作為客戶端，CPU為Intel 奔騰雙核，主頻1 600 MHz，內(nèi)存1 GB，操作系統(tǒng)Windows XP。客戶端建立多線程，每個(gè)線程代表一個(gè)peer節(jié)點(diǎn)，緩存為256塊，主存為9塊。由于環(huán)境有限采用max=1，進(jìn)行模擬后得兩種SDS節(jié)點(diǎn)主存平均刷新頻率與peer節(jié)點(diǎn)個(gè)數(shù)關(guān)系如表3和圖4所示。

表3 普通SDS與P2PSDS主存刷新頻率和peer數(shù)關(guān)系

實(shí)驗(yàn)表明:隨著節(jié)點(diǎn)的增加，對(duì)于普通空間數(shù)據(jù)服務(wù)，源節(jié)點(diǎn)負(fù)擔(dān)加重，當(dāng)節(jié)點(diǎn)數(shù)到達(dá)一定程度后，平均刷新頻率降低不能滿足用戶需求;對(duì)于本文的調(diào)度算法，隨著peer節(jié)點(diǎn)加入，數(shù)據(jù)塊熱度變高，整個(gè)系統(tǒng)提供的連接數(shù)變多，緩減了服務(wù)器的負(fù)擔(dān)，刷新頻率仍能滿足peer節(jié)點(diǎn)需要，效果較好。

4 結(jié)束語(yǔ)

本文提出基于BIT的P2PSDS網(wǎng)絡(luò)模型具有小世界模型特點(diǎn)，子樹任務(wù)區(qū)內(nèi)peer任務(wù)具有關(guān)聯(lián)性，這迎合了空間數(shù)據(jù)請(qǐng)求連續(xù)空間變化的特點(diǎn)。本文通過網(wǎng)格熱度表來反映各網(wǎng)格的資源位置及熱度，并按照peer的興趣區(qū)動(dòng)態(tài)分配peer任務(wù)，最終形成BIT，使網(wǎng)絡(luò)中的資源副本達(dá)到一定熱度。由于節(jié)點(diǎn)在進(jìn)行興趣區(qū)任務(wù)下載時(shí)，可利用熱度表的快速資源定位，降低了網(wǎng)絡(luò)開銷。實(shí)驗(yàn)證明本文提出的調(diào)度方法可行，能夠滿足用戶請(qǐng)求服務(wù)的快速要求。

在任何P2P網(wǎng)絡(luò)中均面臨著單點(diǎn)失效問題，盡管本文采取了一些方法，但還應(yīng)建立peer激勵(lì)和安全機(jī)制，維護(hù)系統(tǒng)穩(wěn)定。空間數(shù)據(jù)海量特征決定了空間數(shù)據(jù)必須分布存儲(chǔ)在網(wǎng)絡(luò)環(huán)境中，下一步需要研究在SIG中基于P2P技術(shù)的空間數(shù)據(jù)服務(wù)資源發(fā)現(xiàn)機(jī)制，以實(shí)現(xiàn)數(shù)據(jù)整合。

參考文獻(xiàn):

[1]孫慶輝，駱劍承，趙軍喜，等.網(wǎng)格GIS數(shù)據(jù)傳輸機(jī)制與策略[J].地球信息科學(xué)，2005，7(1):65-70.

[2]張立朝，潘貞，王富強(qiáng)，等.基于網(wǎng)格的地理空間數(shù)據(jù)傳輸策略研究[J]. 測(cè)繪通報(bào)，2008(6):37-40.

[3]童曉沖，賁進(jìn)，張永生，等.全球多分辨率數(shù)據(jù)模型的構(gòu)建與快速顯示[J].測(cè)繪科學(xué)， 2006，31(1):72-74.

[4]韓猛，鐘廣軍.一種適用于網(wǎng)絡(luò)環(huán)境的三維網(wǎng)格壓縮算法[J]. 計(jì)算機(jī)技術(shù)與發(fā)展，2007，17(12):8-11.

[5]黃曉濤，鄭濤.P2P流媒體點(diǎn)播緩存機(jī)制研究[J].計(jì)算機(jī)工程與科學(xué)，2008，30(3):44-46.

[6]MAUTHE A， HUTCHISON D. Peer-to-peer computing: systems， concepts and characteristics[J]. Praxis der Informationsverarbeitung und Kommunikation， 2003，26(2):60-64.

[7]YOUNG W A. Evaluation of peer-to-peer database solutions[EB/OL].(2004). http://www.tonyyoung.ca/cs654paper.pdf.

[8]LIU C， MA X J，SUN Y F.A peer-to-peer architecture for dynamic executing GIS Web service composition[C]//Proc of IGARSS.2005.

[9]SUN Y F，MA X J，XIE K Q.A compensation mechanismin GIS Web service composition[C]//Proc of IGARSS.2005.

[10]PARAMESWEARAN M， SUSARLA A， WHINSTON A. P2P networking:an information sharing alternative [J]. Computer，2001，34(7):31-38.

[11]樂學(xué)光，郭勇，鄢卉，等.基于region多層結(jié)構(gòu)P2P計(jì)算網(wǎng)絡(luò)定位服務(wù)策略研究[J].微電子學(xué)與計(jì)算機(jī)，2005，22(3):110-113.

[12]劉德剛，陳傳波，曾文.P2P環(huán)境中空間數(shù)據(jù)索引模型和生成算法研究[J].計(jì)算機(jī)工程與應(yīng)用，2008，44(2):12-15.

[13]李德仁，朱欣焰，龔健雅.從數(shù)字地圖到空間信息網(wǎng)格——空間信息多級(jí)網(wǎng)格理論思考[J].武漢大學(xué)學(xué)報(bào):信息科學(xué)版，2003，28(6):642-650.