基于覆蓋網(wǎng)高效信息定位的技術(shù)

【摘 要】在現(xiàn)實世界中“任何一個陌生人之間所間隔的人不會超過六個” ，這就是六度空間理論所闡述的內(nèi)容。本文參照六度空間特性建立的基于興趣的P2P信息查詢網(wǎng)絡(luò)拓?fù)洳粌H提高了信息定位的效率、支持語義查詢，也可以幫助解決物理地址和邏輯地址不匹配的問題。

【關(guān)鍵詞】六度空間理論；興趣特征向量；信息定位算法；P2P網(wǎng)絡(luò)拓?fù)?/p>

一、引言

在P2P模型中，系統(tǒng)所有節(jié)點都是對等的，它們具有相同的責(zé)任，并且互相之間協(xié)同以完成計算任務(wù)。目前，雖然基于P2P計算模式的Napster， Freenet和Gnutella等網(wǎng)絡(luò)模型己被廣泛地應(yīng)用，但是它們也存在一些無法解決的問題[16]。集中式（centralized）的Napster利用中央服務(wù)器負(fù)責(zé)目錄管理的服務(wù)會受限于服務(wù)器的存在，即存在單點瓶頸和崩潰的問題；而非集中式（decentralized）系統(tǒng)，如Gnutella及Freenet，由于沒有中央服務(wù)器，在搜尋數(shù)據(jù)時是以泛洪（flooding）的方式將消息散布到網(wǎng)絡(luò)中，這使得系統(tǒng)的可擴展性（scalability）無法提升。

結(jié)構(gòu)化覆蓋網(wǎng)路由協(xié)議，如CAN， Chord，Pastry和Tapestry就是在這種情況下被提出來的。這些協(xié)議的共同點就是利用DHT，將數(shù)據(jù)和節(jié)點映射成一個鍵值（key），利用鍵值來完成數(shù)據(jù)的放置與維護。這種方法不僅有效地減少了資源定位中的消耗，也加快了數(shù)據(jù)定位的速度。結(jié)構(gòu)化P2P系統(tǒng)成為國內(nèi)外專家學(xué)者的研究熱點。

另外，由于結(jié)構(gòu)化P2P系統(tǒng)在利用DHT構(gòu)建其覆蓋網(wǎng)絡(luò)（overlay）時，沒有過多地考慮底層的物理拓?fù)浣Y(jié)構(gòu)，所以覆蓋網(wǎng)絡(luò)的尋徑是建立在邏輯概念之上的，即根據(jù)各節(jié)點保存的路由信息，選擇一條邏輯跳數(shù)（hops）最少的路徑作為最優(yōu)路徑。這使得覆蓋網(wǎng)絡(luò)中邏輯最近的兩個節(jié)點，在物理層往往并不是最近的，即一條邏輯最近的路徑有可能不是物理最近的路徑。總之，尋徑在邏輯層與物理層上的性能差異，大大降低了結(jié)構(gòu)化P2P系統(tǒng)中資源定位的效率。

基于興趣的P2P網(wǎng)絡(luò)拓?fù)淠Ｐ?，本文文給出了對應(yīng)的信息定位算法，并通過實驗驗證了此算法可以在常數(shù)跳內(nèi)找到對應(yīng)的數(shù)據(jù)。

二、查詢信息定位算法

（一） 拓?fù)淠Ｐ凸?jié)點層次結(jié)構(gòu)

我們知道基于興趣的P2P網(wǎng)絡(luò)拓?fù)淠Ｐ椭械墓?jié)點可以分為三個層次，即普通節(jié)點、興趣簇中心節(jié)點和興趣組節(jié)點。從圖1中我們可以看到，不同興趣（顏色）的節(jié)點形成了不同的興趣簇，在不同的興趣組內(nèi)可以包含相同的興趣。

（二） 拓?fù)淠Ｐ椭泄?jié)點的數(shù)據(jù)存儲方式

由于三類節(jié)點存儲的信息不同，因此在信息定位的過程中，從不同的節(jié)點進行訪問，效率也是不同的。下面分別給出各層節(jié)點數(shù)據(jù)的存儲方式。

（三）算法性能分析

由于基于興趣的P2P網(wǎng)絡(luò)拓?fù)淠Ｐ褪且粋€逐步進化和成熟的體系，因此在前期階段它查找數(shù)據(jù)的性能不是非常穩(wěn)定，但當(dāng)它趨于成熟時，利用多層次的節(jié)點結(jié)構(gòu)，它將擁有其它網(wǎng)絡(luò)所無法比擬的信息定位效率。與泛洪查詢不同，它在查詢過程中，只在開始節(jié)點、興趣簇中心節(jié)點和興趣組節(jié)點跳躍，因此可以實現(xiàn)在常數(shù)跳內(nèi)找到數(shù)據(jù)。

另外，與其它網(wǎng)絡(luò)相比，它還有如下優(yōu)勢：

1）減小了邏輯地址和物理地址不匹配的程度。由于采用新的路由方式和數(shù)據(jù)組織方式，從而規(guī)避了由于使用散列表而造成的節(jié)點位置信息被破壞的問題，這也有利于網(wǎng)絡(luò)性能的不斷優(yōu)化。

2）支持語義查詢功能。由于采用興趣特征向量的方法進行興趣匹配，因此模型支持語義查詢功能。

三、拓?fù)淠Ｐ托畔⒍ㄎ凰惴ǖ哪M實驗

（一）實驗?zāi)康?/p>

從理論上講，論文1節(jié)提出的信息定位算法是可以改善P2P網(wǎng)絡(luò)信息定位效率的，因此我們這里只要驗證了算法的可行性，就意味著六度空間的一些特性是可以應(yīng)用到P2P網(wǎng)絡(luò)的，即基于興趣的P2P網(wǎng)絡(luò)拓?fù)淇梢愿纳片F(xiàn)有網(wǎng)絡(luò)的性能。

由于論文第一節(jié)提出的信息定位算法是一個非常復(fù)雜的過程，因此我們這里只驗證算法的幾個關(guān)鍵部分。

第一，模型可以使用計算興趣向量關(guān)聯(lián)性的方法來組建網(wǎng)絡(luò)。這個功能不僅是網(wǎng)絡(luò)邏輯結(jié)構(gòu)連通性的保證，也是六度空間理論在模型中的具體表現(xiàn)。

第二，模型系統(tǒng)結(jié)構(gòu)的正確性。由于算法把系統(tǒng)節(jié)點分為了普通節(jié)點、興趣簇中心節(jié)點和興趣組節(jié)點三類，因此實驗必須驗證它們是否能提供對應(yīng)的功能。這不僅是對系統(tǒng)結(jié)構(gòu)正確性的驗證，也是對網(wǎng)絡(luò)是否邏輯連通性的驗證。

第三，模型路由過程的正確性。這個功能的實現(xiàn)是對信息定位算法邏輯結(jié)構(gòu)的驗證。

（二）實驗簡介

與第一種查詢過程不同，即當(dāng)本興趣組不含所需數(shù)據(jù)時，查詢請求會發(fā)送到相鄰的興趣組進行查詢。這個過程驗證了查詢可以在不同組內(nèi)的節(jié)點之間進行跳躍。

四、總結(jié)

我們從文獻[1]和文獻[2]知道，利用改進K-Means方法生成的興趣簇中心節(jié)點個數(shù)遠小于普通節(jié)點個數(shù)，而興趣組節(jié)點個數(shù)又遠小于中心節(jié)點個數(shù)，即節(jié)點數(shù)目隨著其層數(shù)的增加而銳減。在拓?fù)淠Ｐ偷男畔⒍ㄎ贿^程中，查詢只在有限的中心節(jié)點、組節(jié)點和普通節(jié)點之間路由，即基于拓?fù)淠Ｐ偷男畔⒍ㄎ凰惴梢栽诔?shù)跳內(nèi)找到所需要的數(shù)據(jù)，這不僅證明了此算法是適用于基于興趣的P2P網(wǎng)絡(luò)拓?fù)淠Ｐ偷?，也證明了利用聚簇、關(guān)聯(lián)度計算等方法可以提高現(xiàn)有數(shù)據(jù)定位的效率。

參考文獻：

[1] 譚義紅， 陳治平， 林亞平. 基于興趣挖掘的非結(jié)構(gòu)化P2P搜索機制研究與實現(xiàn)[J]. 計算機應(yīng)用，2006，26-5

[2] 吳艷文，胡學(xué)鋼.一種K-Means算法K值的優(yōu)化方法[J].計算機研究與發(fā)展.2000，37（5）：513—520.

[3]王成，王英民，陶林偉，甘甜. 多基地聲納距離信息定位算法研究及精度分析[J]. 系統(tǒng)仿真學(xué)報，2009，06：1570-1572+1586.

[4]繆霖，邱會中. Web頁面自頂向下的正文信息定位算法[J]. 計算機工程，2010，13：76-78.

[5]聶永芳，姚奕，焦吉祥. 潛艦導(dǎo)彈超視距攻擊時外部目標(biāo)信息定位分析[J]. 飛航導(dǎo)彈，2010，11：62-65.

[6]邵秀麗，劉彬，張濤. 基于Nutch的垂直搜索引擎的設(shè)計和實現(xiàn)[J]. 計算機工程與設(shè)計，2011，02：539-542+548.

[7]王汝言，何健東，吳大鵬，彭海英. AON中基于網(wǎng)絡(luò)編碼的單鏈路故障定位機制[J]. 光通信研究，2011，06：11-14.

[8]張淑娟，趙飛，王鳳花，賈愛蓮. 基于PDA/GPS/GIS的田間信息采集方法與精度分析[J]. 農(nóng)業(yè)機械學(xué)報，2007，08：202-204.