基于Ｐ２Ｐ的海量地形漫游搜索模型

（武漢大學(xué) a.測(cè)繪遙感信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室; b.電子信息學(xué)院 武漢 430079）

摘 要：隨著用戶的增加，在傳統(tǒng)的C/S模式下，中心服務(wù)器面臨著負(fù)載過(guò)大、性能下降等諸多問(wèn)題。基于對(duì)等網(wǎng)結(jié)構(gòu)，利用P2P技術(shù)解決大規(guī)模海量地形漫游中服務(wù)器帶寬和性能瓶頸問(wèn)題得到了快速發(fā)展，但由于網(wǎng)絡(luò)節(jié)點(diǎn)的動(dòng)態(tài)性，通過(guò)P2P進(jìn)行瓦片數(shù)據(jù)共享時(shí)如何解決節(jié)點(diǎn)搜索問(wèn)題成為關(guān)鍵。針對(duì)上述問(wèn)題，提出了一種基于分組洪泛式的節(jié)點(diǎn)搜索模型GFLOODING，通過(guò)組內(nèi)緩存映射、組外鄰居組映射的洪泛模式查詢服務(wù)節(jié)點(diǎn)；通過(guò)實(shí)驗(yàn)原型系統(tǒng)的比較測(cè)試表明，該算法滿足大規(guī)模節(jié)點(diǎn)模式下的動(dòng)態(tài)性要求，且查詢效率高。

關(guān)鍵詞：搜索模型； 地形漫游； 分組； 洪泛； 對(duì)等網(wǎng)

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

文章編號(hào)：1001-3695(2009)05-1659-04

Massive terrain navigation search model based on P2P

PAN Shaoming YU Zhanwu WANG Haob LI Ruia

(a.State Key Laboratory of Information Engineering in Surveying Mapping Remote Sensing b.School of Electronic Information Wuhan University Wuhan 430079 China)

Abstract:As the number of clients increases the server performance will drop too rapidly to satisfy the client realtime rending requirement because the server loads are increasing linearly for the kind of client/server architecture. The method through peertopeer (P2P) to address the server bandwidth and performance bottleneck in large scale massive terrain navigation has attracted much effort based on P2P networks. Due to peers’ dynamics how to find the server peers quickly is the key problem on sharing the tiles based on P2P. A searching model called GFLOODING was proposed for the system which was based on the buffer map (BM) info and group peer map (GPM) info when deciding from which peers to get the tiles. Compared test result in prototype system indicates that the proposed module can satisfy the large scale massive terrain navigation system and has higher efficiency than traditional module.

Key words：search model; terrain navigation; group; flooding; P2P(peertopeer)

0 引言

P2P網(wǎng)絡(luò)是近年來(lái)計(jì)算機(jī)網(wǎng)絡(luò)領(lǐng)域研究的熱點(diǎn)。利用P2P技術(shù)解決大規(guī)模海量地形漫游中服務(wù)器帶寬和性能瓶頸問(wèn)題得到了快速的發(fā)展，有相關(guān)文獻(xiàn)加以研究^[1~4]。如何快速選擇服務(wù)節(jié)點(diǎn)進(jìn)行瓦片數(shù)據(jù)下載，是影響地形漫游服務(wù)質(zhì)量的關(guān)鍵問(wèn)題之一，對(duì)此相關(guān)文獻(xiàn)很少。由于GIS地形系統(tǒng)中瓦片數(shù)據(jù)的海量性和本地?cái)?shù)據(jù)緩存的有限性，導(dǎo)致所有節(jié)點(diǎn)都只能緩存部分瓦片；同時(shí)P2P網(wǎng)絡(luò)具有動(dòng)態(tài)和自治特性，節(jié)點(diǎn)的緩存映射信息的傳遞將消耗大量的網(wǎng)絡(luò)帶寬資源。針對(duì)上述問(wèn)題，提出了一種基于分組的洪泛節(jié)點(diǎn)搜索共享模型GFLOODING。

1 相關(guān)工作

地形漫游服務(wù)中，基于對(duì)等網(wǎng)絡(luò)的傳輸模式解決了傳統(tǒng)C/S模式下中心服務(wù)節(jié)點(diǎn)帶寬和性能瓶頸，集中式或混合式的P2P海量地形漫游系統(tǒng)成為研究熱點(diǎn)。在進(jìn)行P2P共享時(shí)，其核心思想是通過(guò)查詢中心服務(wù)器或者本地緩存信息獲取鄰居節(jié)點(diǎn)信息，并選擇鄰居節(jié)點(diǎn)下載瓦片數(shù)據(jù)。文獻(xiàn)[1]提出了一種混合式的P2P模型，每個(gè)節(jié)點(diǎn)依據(jù)一定的規(guī)則加入組，節(jié)點(diǎn)都有自己組內(nèi)的鄰居節(jié)點(diǎn)列表，鄰居節(jié)點(diǎn)之間相互交換本地瓦片信息，這種信息稱為緩存映射（buffer map，BM），通過(guò)緩存映射，組內(nèi)所有節(jié)點(diǎn)都能了解鄰居已有數(shù)據(jù)的分布情況，從而選擇服務(wù)節(jié)點(diǎn)下載瓦片。以全球SRTM90地形數(shù)據(jù)為例，表1列出了節(jié)點(diǎn)頻繁上下線時(shí)交換緩存映射信息消耗的網(wǎng)絡(luò)帶寬。表中動(dòng)態(tài)性是指每秒時(shí)間內(nèi)加入或離開(kāi)的節(jié)點(diǎn)占組內(nèi)總節(jié)點(diǎn)的比率。顯然，一定動(dòng)態(tài)性下，節(jié)點(diǎn)總數(shù)越多，單位時(shí)間加入或離開(kāi)的節(jié)點(diǎn)就越多。從表1可以看出，這種選擇模式雖然快速但難以滿足大規(guī)模節(jié)點(diǎn)的動(dòng)態(tài)性要求。文獻(xiàn)[3~5]利用集中式P2P，在節(jié)點(diǎn)需要下載數(shù)據(jù)時(shí)，通過(guò)查詢中心節(jié)點(diǎn)，獲取正在下載同一數(shù)據(jù)的其他節(jié)點(diǎn)信息，并通過(guò)該節(jié)點(diǎn)下載瓦片。這種模式選擇節(jié)點(diǎn)只需一次查詢，但中心服務(wù)器需要存儲(chǔ)大量節(jié)點(diǎn)緩存信息，而且也同樣存在與文獻(xiàn)[1]一樣的額外消耗大量帶寬問(wèn)題。

本文針對(duì)已有對(duì)等網(wǎng)絡(luò)模式下存在的問(wèn)題，提出了一種新的基于節(jié)點(diǎn)有限分組，組內(nèi)通過(guò)緩存映射信息查詢，組外通過(guò)洪泛搜索的模型，并給出了相關(guān)分析和算法流程。最后對(duì)模型開(kāi)發(fā)了原型系統(tǒng)進(jìn)行了檢驗(yàn)。

2 節(jié)點(diǎn)搜索模型

2.1 節(jié)點(diǎn)搜索模型設(shè)計(jì)

如圖1所示是一種基于混合式的P2P海量地形漫游共享模型^[1]，每個(gè)節(jié)點(diǎn)依據(jù)其當(dāng)前漫游的區(qū)域加入組（中心服務(wù)節(jié)點(diǎn)屬于特殊組成員，屬于所有組），節(jié)點(diǎn)通過(guò)互相交換緩存映射獲取組內(nèi)鄰居節(jié)點(diǎn)的信息。

為了降低組內(nèi)節(jié)點(diǎn)間的緩存映射信息流量，同時(shí)保持一定的節(jié)點(diǎn)搜索發(fā)現(xiàn)速度，主要從以下幾個(gè)方面加以考慮：

a）依據(jù)節(jié)點(diǎn)漫游的興趣區(qū)域不同，節(jié)點(diǎn)加入不同的組。考慮地形漫游的特點(diǎn)，根據(jù)如圖2所示的GIS地形數(shù)據(jù)瓦片分層規(guī)則，設(shè)某層l中某瓦片pi的坐標(biāo)值為(xi，yi)，按照金字塔模型對(duì)應(yīng)的最低分辨率（定義為0層）瓦片的坐標(biāo)為(x0，y0)，則有

x0=xi/2ly0=yi/2l（1）

依據(jù)式（1）可以確定節(jié)點(diǎn)的興趣區(qū)域。一個(gè)組具有相同的興趣區(qū)域，組內(nèi)成員之間的緩存映射只需要包含對(duì)應(yīng)的興趣區(qū)域信息即可。

b）組內(nèi)節(jié)點(diǎn)緩存映射信息的交換分全局與局部交換：節(jié)點(diǎn)在地形漫游時(shí)，本地信息發(fā)生變化，通過(guò)只交換變化部分的規(guī)則，降低緩存映射信息流量，稱為局部交換；在有新節(jié)點(diǎn)上線時(shí)，新節(jié)點(diǎn)與老節(jié)點(diǎn)之間互相交換全部興趣區(qū)域內(nèi)的瓦片信息，稱為全局交換。

c）從表1可以看出，在一定的節(jié)點(diǎn)動(dòng)態(tài)率下，全局信息流量的大小與組內(nèi)節(jié)點(diǎn)個(gè)數(shù)成正比。為了減少全局信息交換數(shù)量，限制組內(nèi)成員個(gè)數(shù)。

d）為了擴(kuò)大P2P共享搜索范圍，引入鄰居組節(jié)點(diǎn)信息，鄰居組信息包含了部分鄰居組成員節(jié)點(diǎn)的地址信息，這種信息稱為鄰居組節(jié)點(diǎn)映射(group peer map，GPM)。GPM包含了同一個(gè)興趣域內(nèi)其他組成員的地址、端口等信息，通過(guò)這些信息，節(jié)點(diǎn)可以與鄰居組節(jié)點(diǎn)建立連接并發(fā)送請(qǐng)求，獲取瓦片信息。設(shè)某興趣區(qū)域Mx，y內(nèi)有組Gk、Gm，其中k，m=1，2，…，k≠m，對(duì)任意鄰居組節(jié)點(diǎn)pi、pj滿足式（2）的限制：

piGmpi∈GkpjGkGm，Gk∈Mx，y(2)

式（2）表明，GPM成員不是本組成員，且屬于不同的組，所有的組都屬于同一個(gè)興趣區(qū)域，被選中的其他組的節(jié)點(diǎn)稱為本組的代理節(jié)點(diǎn)，一個(gè)組內(nèi)各個(gè)成員之間具有相同的GPM映射信息。

e）服務(wù)帶寬和響應(yīng)延時(shí)表示一個(gè)節(jié)點(diǎn)的服務(wù)質(zhì)量，每個(gè)組依據(jù)服務(wù)質(zhì)量最大的原則選擇一個(gè)組領(lǐng)導(dǎo)，組領(lǐng)導(dǎo)負(fù)責(zé)從中心服務(wù)器節(jié)點(diǎn)p0獲取和刷新鄰居組節(jié)點(diǎn)映射，并將最新的鄰居組節(jié)點(diǎn)映射信息通知組內(nèi)其他節(jié)點(diǎn)。為了減少傳輸數(shù)據(jù)量，采取更新刷新的原則，即每次只傳輸更新的部分。一個(gè)組領(lǐng)導(dǎo)下線時(shí)，依據(jù)同樣的原則在組內(nèi)節(jié)點(diǎn)間產(chǎn)生新的領(lǐng)導(dǎo)。

根據(jù)以上定義的規(guī)則，可以給出模型中的緩存映射BM和鄰居組節(jié)點(diǎn)映射GPM的消息結(jié)構(gòu)：

不失一般性，設(shè)區(qū)域Mx，y內(nèi)某組Gk的節(jié)點(diǎn)總個(gè)數(shù)為M，該區(qū)域內(nèi)地形數(shù)據(jù)瓦片總塊數(shù)為S，節(jié)點(diǎn)i稱為mi，瓦片i稱為pi，節(jié)點(diǎn)i由一個(gè)三元組〈IDi，bi，ui〉描述。其中IDi是節(jié)點(diǎn)標(biāo)志，全局惟一（可以通過(guò)MAC地址生成）；bi是帶寬，由各個(gè)節(jié)點(diǎn)自行估計(jì)^[6，7]；ui是數(shù)組（指針），用于存放節(jié)點(diǎn)是否擁有某塊瓦片，即uki表示節(jié)點(diǎn)i是否擁有瓦片k，uki=1表示擁有，為0則不擁有。緩存映射則是由不同節(jié)點(diǎn)的三元組組成的內(nèi)存塊，按照〈〈IDi，bi，ui〉，〈IDj，bj，uj〉，…〉的形式組織。

鄰居組節(jié)點(diǎn)信息則由一個(gè)四元組〈Gi，IDi，ipi，porti〉描述。其中：Gi是鄰居組號(hào)；IDi是從鄰居組內(nèi)選擇的代理節(jié)點(diǎn)的標(biāo)志；ipi和porti分別為代理節(jié)點(diǎn)的IP地址和服務(wù)端口；鄰居組節(jié)點(diǎn)映射GPM則是由不同鄰居組節(jié)點(diǎn)的四元組組成的內(nèi)存塊，按照〈〈Gi，IDi，ipi，porti〉，〈Gj，IDj，ipj，portj〉，…〉的形式組織。

2.2 節(jié)點(diǎn)搜索模型調(diào)度算法

節(jié)點(diǎn)搜索模型的調(diào)度分為兩個(gè)方面:a）BM和GPM的交互調(diào)度;b）利用BM和GPM信息進(jìn)行節(jié)點(diǎn)搜索調(diào)度。下面分別給出調(diào)度算法。

BM和GPM映射信息交互調(diào)度偽代碼如下：

//組Gn中節(jié)點(diǎn)mj的調(diào)度流程

//1. BM映射信息局部交換

OnRecvNewTile(pk){//收到新瓦片pk

for each mi in Gn do

if(mi≠mj)

SendBM(BMk，mi，1) //局部交換

end if

end for

}

//2. BM映射信息全局交換

OnNewPeerAdd (mi){//新節(jié)點(diǎn)mi加入

SendBMTo(BM，mi)//全局交換

RecvBMFrom(BM，mi) //全局交換

}

//3. GPM信息的更新

OnSchedule(){

isGpmUpdate = 1//記錄狀

num = GetLength(GPM)//鄰居組個(gè)數(shù)

if num < NEED_NUMBER then 

GetGpmFrom(p0 NEED_NUMBERnum)

isGpmUpdate=true

end if

for each pk in GPM do 

if not isActive(pk) then //節(jié)點(diǎn)下線

GetGpmFrom(p0，1)

isGpmUpdate=true

end if

end for

if isGpmUpdate then

for each mi in Gn do

if(mi≠mj)

SendGPM(GPM，mi) //交換GPM

end if

end for

end if

}

該調(diào)度算法的基本思想是在節(jié)點(diǎn)有瓦片更新時(shí)，實(shí)時(shí)將緩存映射的更新部分發(fā)送給組內(nèi)其他節(jié)點(diǎn)，一旦有新的節(jié)點(diǎn)上線，則將全部緩存映射信息發(fā)送給新節(jié)點(diǎn)，并同時(shí)從新節(jié)點(diǎn)獲取它的全部緩存映射信息。對(duì)于本地緩存區(qū)滿的狀態(tài)，為了保持不溢出，有新瓦片下載時(shí)，必須同時(shí)刪除一塊老的瓦片，此時(shí)緩存映射信息也有改變，只需要再次調(diào)用SendBM(BMk，mi，0)通知改變部分。函數(shù)中最后一個(gè)參數(shù)為1表示添加，為０表示刪除。

如圖3所示為一個(gè)節(jié)點(diǎn)搜索調(diào)度的例子，陰影表示擁有該瓦片數(shù)據(jù)。圖3中組Ａ的節(jié)點(diǎn)m3需要瓦片p3，m3首先在自己的緩存映射中查找本組節(jié)點(diǎn)信息，發(fā)現(xiàn)節(jié)點(diǎn)m1和m2都沒(méi)有所需要的瓦片p3。如是通過(guò)本地GPM映射信息，向鄰居組代理節(jié)點(diǎn)發(fā)送請(qǐng)求（發(fā)送的請(qǐng)求信息包含所需要的瓦片和接收者地址），組B的節(jié)點(diǎn)m2和組C的節(jié)點(diǎn)m1作為代理節(jié)點(diǎn)收到請(qǐng)求后查詢本地緩存映射信息，組B的節(jié)點(diǎn)m2發(fā)現(xiàn)自己就有瓦片p3，則直接請(qǐng)求將瓦片p3發(fā)送給組A的節(jié)點(diǎn)m3，而組C的代理節(jié)點(diǎn)m1發(fā)現(xiàn)本組節(jié)點(diǎn)m2有所需瓦片，則請(qǐng)求本組節(jié)點(diǎn)m2將瓦片p3發(fā)送給組A的節(jié)點(diǎn)m3，組C節(jié)點(diǎn)m2直接請(qǐng)求將p3發(fā)送給組A的節(jié)點(diǎn)m3。組A的節(jié)點(diǎn)m3依據(jù)先到先用的原則，接收從組B發(fā)來(lái)的瓦片，而直接拒絕組C的連接請(qǐng)求，依據(jù)節(jié)點(diǎn)規(guī)模和GPM大小，在代理組沒(méi)有發(fā)現(xiàn)所需要的瓦片時(shí)，還可以通過(guò)代理組的代理繼續(xù)查詢。為了收斂和限制消息擴(kuò)散規(guī)模，可以指定最大代理跳數(shù)，每經(jīng)過(guò)一次代理，跳數(shù)減1；跳數(shù)為0時(shí)，則不再繼續(xù)查找，在GPM足夠大時(shí)，代理跳數(shù)設(shè)置為1即可。

節(jié)點(diǎn)搜索調(diào)度算法流程偽代碼如下：

//組GA中節(jié)點(diǎn)mi請(qǐng)求瓦片pj調(diào)度流程

//1. 通過(guò)BM映射信息查找

DoFindTileInBM(pj){//組內(nèi)下載瓦片

for each mk in GA do

if(mk≠mi)

is TileExist=FindTile(pj，mk)

if is TileExist then

download(mk，pj，mi)//找到則下載

exit(1)

end if

end if

end for

exit(0)

}

//2. 利用GPM映射信息查找

DoFindTileInGPM(pj，mi，TTL){

for each mk in GPM do

RequestTile(pj，mi，TTL)//從鄰居下載

end if

}

//3. 鄰居組節(jié)點(diǎn)收到請(qǐng)求后的處理

OnRecvRequest(pj，mi，TTL){

TTL=1

bFind=DoFindTileInBM(pj)

if !bFind TTL then

DoFindTileInGPM(pj，mi，TTL)

end if

if !bFind !TTL then//沒(méi)找到

download(m0，pj，mi) //從服務(wù)器下載

end if

}

節(jié)點(diǎn)搜索算法首先查詢本地組緩存映射信息，找到則直接下載；否則將請(qǐng)求發(fā)送到所有鄰居組的代理節(jié)點(diǎn)，由代理節(jié)點(diǎn)繼續(xù)查找，直到找到或者跳數(shù)為0。如果跳數(shù)為0且沒(méi)有找到，則直接請(qǐng)求從中心服務(wù)器節(jié)點(diǎn)下載。若多個(gè)代理節(jié)點(diǎn)都找到并向請(qǐng)求節(jié)點(diǎn)發(fā)送連接請(qǐng)求，則請(qǐng)求節(jié)點(diǎn)選擇最先到達(dá)的連接請(qǐng)求，并拒絕其他連接請(qǐng)求；同樣，多個(gè)代理節(jié)點(diǎn)在沒(méi)有找到且跳數(shù)為0時(shí)會(huì)向中心服務(wù)節(jié)點(diǎn)發(fā)送請(qǐng)求，此時(shí)請(qǐng)求節(jié)點(diǎn)依據(jù)同樣的原則拒絕多余的連接請(qǐng)求。該算法會(huì)造成一些多余的連接請(qǐng)求，但并不會(huì)產(chǎn)生真正的數(shù)據(jù)傳輸和導(dǎo)致過(guò)多的帶寬消耗。通過(guò)分析可知，對(duì)該算法稍加優(yōu)化，即可以消除這些多余的請(qǐng)求，如通過(guò)減少鄰居組節(jié)點(diǎn)個(gè)數(shù)、增加跳數(shù)等，顯然當(dāng)鄰居組節(jié)點(diǎn)個(gè)數(shù)為1時(shí)，就可以保證不產(chǎn)生任何多余的連接和數(shù)據(jù)傳輸。限于篇幅，在此不作過(guò)多的描述。

2.3 算法模型性能影響分析

通過(guò)兩個(gè)方面來(lái)進(jìn)行性能影響分析：沒(méi)有節(jié)點(diǎn)上下線的影響分析；在一定的節(jié)點(diǎn)動(dòng)態(tài)性下的影響分析。

以全球SRTM90地形數(shù)據(jù)為例，共3 538 890塊瓦片，每塊瓦片數(shù)據(jù)大小約為44 KB，三元組〈IDi，bi，ui〉中，按照更新交換的原則，以平均512 kbps（普通電信ADSL用戶）的終端帶寬作為計(jì)算依據(jù)，每秒最多可下載的瓦片數(shù)為1.5塊，每塊瓦片更新占用的字節(jié)數(shù)為4 Byte+1 bit（分別表示地址和數(shù)據(jù)位，數(shù)據(jù)位為1表示新?lián)碛性撏咂駝t為新刪除該瓦片），則最多產(chǎn)生49.5 bps的ui數(shù)據(jù)。按照本地緩沖區(qū)滿狀態(tài)考慮(一般定義為1 GB)，新下載一塊瓦片，則對(duì)應(yīng)地需刪除一塊瓦片，則最大產(chǎn)生的流量為99 bps。另外，一次更新中bi和IDi分別固定占用4 Byte，由于IDi不變，可以忽略，則一個(gè)節(jié)點(diǎn)產(chǎn)生的更新總數(shù)據(jù)量最大約為131 bps，按照每組節(jié)點(diǎn)成員50個(gè)計(jì)，組內(nèi)產(chǎn)生的網(wǎng)絡(luò)流量也只有6.4 kbps，這相對(duì)于海量地形漫游時(shí)產(chǎn)生的網(wǎng)絡(luò)流量，對(duì)性能的影響是有限的。考慮到有部分節(jié)點(diǎn)處于空閑狀態(tài)，不需要發(fā)送BM信息，這個(gè)估計(jì)還是趨于保守的。

同樣，可以計(jì)算GPM更新需要消耗的網(wǎng)絡(luò)流量為sizeGPM×fGPM×128 bps。其中：sizeGPM表示GPM的大小；fGPM表示GPM更新頻率；常數(shù)128表示每個(gè)GPM信息占用的數(shù)據(jù)位數(shù)（16 Byte×8 bit／Byte）。若設(shè)GPM長(zhǎng)度為100，更新頻率為每秒2%，則產(chǎn)生的網(wǎng)絡(luò)流量為256 bps。由于一個(gè)組的GPM信息相同，也就是說(shuō)一個(gè)組總共與中心服務(wù)節(jié)點(diǎn)間產(chǎn)生的流量才256 bps。

對(duì)于節(jié)點(diǎn)動(dòng)態(tài)上下線的情況，依據(jù)節(jié)點(diǎn)搜索模型設(shè)計(jì)原則，仍然以SRTM90地形數(shù)據(jù)為例，此時(shí)域內(nèi)的瓦片數(shù)為21 845塊。按照表１的計(jì)算依據(jù)，有如表2所示的計(jì)算結(jié)果。

通過(guò)表2可以看出，適當(dāng)降低組內(nèi)節(jié)點(diǎn)個(gè)數(shù)，動(dòng)態(tài)性導(dǎo)致的平均節(jié)點(diǎn)網(wǎng)絡(luò)流量顯著下降，當(dāng)組內(nèi)節(jié)點(diǎn)個(gè)數(shù)降低到10個(gè)時(shí)，流量也就只有7.7 kbps（0.007 5 Mbps≈7.7 kbps）。

顯然，將組內(nèi)節(jié)點(diǎn)個(gè)數(shù)設(shè)置為１，即不存在BM映射信息，節(jié)點(diǎn)動(dòng)態(tài)性也就基本上不產(chǎn)生額外的網(wǎng)絡(luò)流量。該模型同樣可以通過(guò)鄰居組節(jié)點(diǎn)映射GPM查找到服務(wù)節(jié)點(diǎn)。

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

考察兩個(gè)指標(biāo)：a）搜索延時(shí)t，是指節(jié)點(diǎn)發(fā)出瓦片請(qǐng)求后，找到服務(wù)節(jié)點(diǎn)消耗的時(shí)間；b）服務(wù)器網(wǎng)絡(luò)流量占比f，即通過(guò)服務(wù)器的網(wǎng)絡(luò)流量占系統(tǒng)網(wǎng)絡(luò)總流量的比率。顯然，同樣條件下，搜索延時(shí)t越小，地形漫游質(zhì)量越高；服務(wù)器流量f占比越小，對(duì)降低中心服務(wù)器的負(fù)載、提高普通節(jié)點(diǎn)之間的共享效率越好。

利用所開(kāi)發(fā)的基于GlobeSight^[8]的P2P原型系統(tǒng)，終端實(shí)現(xiàn)兩種節(jié)點(diǎn)搜索機(jī)制：a）類似BitTorrent^[9]的節(jié)點(diǎn)隨機(jī)搜索機(jī)制，在請(qǐng)求瓦片時(shí)，從服務(wù)器隨機(jī)選擇一定數(shù)量的鄰居節(jié)點(diǎn)（本文為30個(gè)），并向所選節(jié)點(diǎn)發(fā)出請(qǐng)求，找到則從擁有該瓦片的節(jié)點(diǎn)下載，否則從中心服務(wù)器下載；b）基于本文的GFLOODING搜索機(jī)制。以最高分辨率為90 m的全球SRTM90地形數(shù)據(jù)為實(shí)驗(yàn)數(shù)據(jù)（數(shù)據(jù)塊大小為128×128像素，每塊傳輸瓦片數(shù)據(jù)大小約44 KB，共3 538 890塊瓦片），在一個(gè)局域網(wǎng)絡(luò)內(nèi)，組織１臺(tái)中心服務(wù)器和200個(gè)普通終端節(jié)點(diǎn)。不失一般性，設(shè)所有節(jié)點(diǎn)處于同一個(gè)區(qū)域，則其興趣區(qū)域的瓦片總數(shù)為21 845；普通節(jié)點(diǎn)按照10個(gè)一組，組成20個(gè)組，普通節(jié)點(diǎn)帶寬相同，為256 kbps，中心服務(wù)節(jié)點(diǎn)帶寬為10 Mbps，分別利用兩種搜索機(jī)制進(jìn)行地形數(shù)據(jù)下載。

收集數(shù)據(jù)前，普通節(jié)點(diǎn)先按照0.5%的比率形成本地瓦片緩存，節(jié)點(diǎn)在進(jìn)入系統(tǒng)后隨機(jī)選擇瓦片下載，穩(wěn)定運(yùn)行10 min后開(kāi)始記錄數(shù)據(jù)，按照1 min的周期記錄各個(gè)節(jié)點(diǎn)（不包括中心服務(wù)節(jié)點(diǎn)）搜索每塊瓦片結(jié)果的延時(shí)時(shí)間和各個(gè)節(jié)點(diǎn)（包括中心服務(wù)節(jié)點(diǎn)）的發(fā)送數(shù)據(jù)流量；最后根據(jù)記錄的數(shù)據(jù)信息計(jì)算各個(gè)周期的平均搜索延時(shí)時(shí)間t和服務(wù)器網(wǎng)絡(luò)流量占比f(wàn)。其中：t=該周期內(nèi)各個(gè)節(jié)點(diǎn)的延時(shí)時(shí)間和／各節(jié)點(diǎn)搜索請(qǐng)求次數(shù)和；f=中心服務(wù)節(jié)點(diǎn)的網(wǎng)絡(luò)流量／所有節(jié)點(diǎn)網(wǎng)絡(luò)流量和，圖4給出了不同時(shí)間點(diǎn)的搜索延時(shí)時(shí)間對(duì)比測(cè)試結(jié)果。圖5給出了不同時(shí)間點(diǎn)的服務(wù)器流量占比對(duì)比測(cè)試結(jié)果。

通過(guò)對(duì)比測(cè)試，在基于GFLOODING的搜索模型下，由于節(jié)點(diǎn)部分具有緩存映射信息，同樣的條件下，GFLOODING模型可以通過(guò)緩存映射信息BM快速定位服務(wù)節(jié)點(diǎn)，平均搜索時(shí)間相對(duì)就小。隨著運(yùn)行時(shí)間的推移，BM信息越多，通過(guò)BM映射信息定位的可能性就越大，平均搜索延時(shí)也就越來(lái)越小；同樣，由于GFLOODING模型的搜索范圍更廣，能找到普通節(jié)點(diǎn)的可能性就越大，這樣，通過(guò)普通節(jié)點(diǎn)下載數(shù)據(jù)的次數(shù)就越多，對(duì)應(yīng)的中心服務(wù)器的負(fù)載就相對(duì)變小。當(dāng)系統(tǒng)運(yùn)行一段時(shí)間之后，組內(nèi)鄰居節(jié)點(diǎn)和鄰居組節(jié)點(diǎn)擁有了全部興趣區(qū)域的瓦片時(shí)，中心服務(wù)節(jié)點(diǎn)的流量占比就趨向于0。結(jié)果表明，相對(duì)于隨機(jī)模型，GFLOODING的搜索時(shí)間和服務(wù)器流量占比性能更優(yōu)。

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

利用P2P進(jìn)行海量地形數(shù)據(jù)傳輸時(shí)，如何在花費(fèi)較小代價(jià)的前提下，盡快找到服務(wù)節(jié)點(diǎn)是提高P2P共享效率、優(yōu)化地形漫游服務(wù)質(zhì)量的關(guān)鍵；利用P2P進(jìn)行海量地形漫游共享服務(wù)作為GIS領(lǐng)域的一個(gè)新興課題，與此相關(guān)的文獻(xiàn)還相對(duì)較少。針對(duì)地形漫游中瓦片數(shù)量巨大、節(jié)點(diǎn)動(dòng)態(tài)性強(qiáng)的特點(diǎn)，本文提出的基于分域分組的節(jié)點(diǎn)緩存映射與鄰居節(jié)點(diǎn)代理映射相結(jié)合的信息組織模式，與本地查找和代理洪泛查找相關(guān)聯(lián)的算法模型，能較好地解決當(dāng)前通過(guò)P2P進(jìn)行海量地形下載漫游的節(jié)點(diǎn)快速搜索問(wèn)題。實(shí)驗(yàn)原型測(cè)試結(jié)果表明，算法對(duì)提高節(jié)點(diǎn)搜索速度和降低服務(wù)器的負(fù)載流量有效，性能較優(yōu)。

參考文獻(xiàn)：

［1］喻占武 鄭勝 李忠民. 一種混合式P2P下的大規(guī)模地形數(shù)據(jù)傳輸機(jī)制[J]. 測(cè)繪學(xué)報(bào) 2008 37(1):243-250.

[2]馬修軍 李晨煜 謝昆青，等. 基于P2P的空間數(shù)據(jù)操作分布技術(shù)研究[J]. 地理與地理信息科學(xué) 2006 22(4):16-19.

[3]徐靜 李春華 陳天滋. 基于P2P技術(shù)的GIS數(shù)據(jù)傳輸方法研究[J]. 計(jì)算機(jī)工程與設(shè)計(jì) 2007 28(12):2851-2853.

[4]GUAN Jihong WANG Leichun ZHOU Shuigeng. Enabling GIS services in a P2P environment[C]//Proc of the 4th International Conference on Computer and Information Technology. 2004:776-781.

[5]劉德剛 向金海 周剛. 基于P2P的Web GIS系統(tǒng)架構(gòu)設(shè)計(jì)[J]. 計(jì)算機(jī)與現(xiàn)代化 2007 11(1): 191-193.

[6]ZHANG Meng XIONG Yongqiang ZHANG Qian et al. On the optimal scheduling for media streaming in datadriven overlay networks[C]//Proc of IEEE Global Telecommunications Conference (GLOBECOM’06). San Francisco California: IEEE Computer Society 2006:1-5.

[7]YANG Sirui JIN Hai TU Xuping. TOBAB: a trendoriented bandwidth adaptive buffering in peertopeer streaming system[C]//Proc of Autonomic and Trusted Computing (ATC’06). Wuhan: Springer 2006:113-122.

[8]喻占武 李忠民 鄭勝. 基于對(duì)象存儲(chǔ)的新型網(wǎng)絡(luò)GIS體系結(jié)構(gòu)研究[J]. 武漢大學(xué)學(xué)報(bào):信息科學(xué)版，2008 33（3）: 285-288.

[9]QIU D SRIKANT R. Modeling and performance analysis of BitTorrentlike peertopeer networks[J]. ACM SIGCOMM Computer Communication Review Archive 2004，34(4): 367-378.