[發(fā)明專利]一種基于層次化可導(dǎo)航網(wǎng)絡(luò)的P2P協(xié)議

無效

• 申請?zhí)枺?/td>: 201110120740.5
• 申請日: 2011-05-10
• 公開（公告）號: CN102148877A
• 公開（公告）日: 2011-08-10
• 發(fā)明（設(shè)計(jì)）人: 馮文峰;張治斌;陳慧琴;安吉宇;閆俊豪
• 申請（專利權(quán)）人: 河南理工大學(xué)
• 主分類號: H04L29/08
• 分類號: H04L29/08;H04L12/56
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術(shù)領(lǐng)域

本發(fā)明涉及一種P2P協(xié)議，特別涉及一種基于層次化可導(dǎo)航網(wǎng)絡(luò)的P2P協(xié)議。

背景技術(shù)

目前，P2P網(wǎng)絡(luò)主要性能指標(biāo)的復(fù)雜度無法完全達(dá)到對數(shù)級別，P2P技術(shù)已經(jīng)成為互聯(lián)網(wǎng)的重要組成部分，甚至很多人已經(jīng)認(rèn)為P2P技術(shù)將成為未來互聯(lián)網(wǎng)的發(fā)展方向；P2P應(yīng)用的流行源于P2P技術(shù)所提供的無限服務(wù)能力、低廉的成本和良好的服務(wù)穩(wěn)定性；在P2P文件共享系統(tǒng)中，內(nèi)容發(fā)布功能被開放給每一個peer端，極大地豐富了系統(tǒng)的內(nèi)容，從而吸引了大量新用戶；隨著P2P技術(shù)的快速發(fā)展，P2P技術(shù)進(jìn)一步得到發(fā)展，但P2P技術(shù)的普及破壞了傳統(tǒng)的網(wǎng)絡(luò)業(yè)務(wù)訪問模型，對P2P技術(shù)的繼續(xù)發(fā)展設(shè)置了障礙。

發(fā)明內(nèi)容

為了克服上述現(xiàn)有技術(shù)存在的缺陷，本發(fā)明提供一種基于層次化可導(dǎo)航網(wǎng)絡(luò)的P2P協(xié)議。

為實(shí)現(xiàn)上述目的，本發(fā)明的具體方案為：

一種基于層次化可導(dǎo)航網(wǎng)絡(luò)的P2P協(xié)議，包括節(jié)點(diǎn)加入、節(jié)點(diǎn)退出以及路由。

每個節(jié)點(diǎn)具有一個在[0，2H)之間均勻分布的H個比特位的標(biāo)識符；節(jié)點(diǎn)的所述標(biāo)識符代表著該節(jié)點(diǎn)在樹T(H)的葉子節(jié)點(diǎn)集中的位置；每個節(jié)點(diǎn)維護(hù)H-1個鄰居節(jié)點(diǎn)列表，其中第h(1＜＝h＜＝H-1)個列表中的鄰居節(jié)點(diǎn)和該節(jié)點(diǎn)的距離為h，該列表被稱為h-距離鄰居節(jié)點(diǎn)列表。

所述的節(jié)點(diǎn)加入為：加入節(jié)點(diǎn)j首先通過引導(dǎo)機(jī)制獲得P2P協(xié)議中的一個隨機(jī)引導(dǎo)節(jié)點(diǎn)s；然后，從節(jié)點(diǎn)s到節(jié)點(diǎn)j執(zhí)行路由操作。

所述的路由為：步驟一：加入節(jié)點(diǎn)j被加入到所有路由中繼節(jié)點(diǎn)r或節(jié)點(diǎn)s的h-距離鄰居節(jié)點(diǎn)列表，中繼節(jié)點(diǎn)r被加入節(jié)點(diǎn)j的h-距離鄰居節(jié)點(diǎn)列表；步驟二：每個中繼節(jié)點(diǎn)r的所有鄰居節(jié)點(diǎn)被加入到節(jié)點(diǎn)j的相應(yīng)距離鄰居節(jié)點(diǎn)列表；步驟三：如果前兩個動作執(zhí)行之前，中繼節(jié)點(diǎn)r的h-距離鄰居節(jié)點(diǎn)列表為空，則節(jié)點(diǎn)j被加入到節(jié)點(diǎn)r的距離小于h的所有鄰居節(jié)點(diǎn)的h-距離鄰居節(jié)點(diǎn)列表中；節(jié)點(diǎn)j的所有h距離節(jié)點(diǎn)知道節(jié)點(diǎn)j。

本發(fā)明中，所述路由的算法為：

算法1：引導(dǎo)節(jié)點(diǎn)s開始以加入節(jié)點(diǎn)j為目標(biāo)節(jié)點(diǎn)進(jìn)行路由；

步驟：

將引導(dǎo)節(jié)點(diǎn)s作為中繼節(jié)點(diǎn)r

while(中繼節(jié)點(diǎn)r！＝目標(biāo)節(jié)點(diǎn)j){

h＝節(jié)點(diǎn)r和節(jié)點(diǎn)j之間的距離

if(03and節(jié)點(diǎn)r的h-距離鄰居節(jié)點(diǎn)列表為空)

將節(jié)點(diǎn)j加入所有和節(jié)點(diǎn)r距離小于h的節(jié)點(diǎn)的h-距離鄰居節(jié)點(diǎn)列表，

將節(jié)點(diǎn)j加入節(jié)點(diǎn)r的h-距離鄰居節(jié)點(diǎn)列表；

if

將節(jié)點(diǎn)r加入節(jié)點(diǎn)j的h-距離鄰居節(jié)點(diǎn)列表

else

將節(jié)點(diǎn)r及其所有鄰居節(jié)點(diǎn)加入節(jié)點(diǎn)j的相應(yīng)鄰居節(jié)點(diǎn)列表，

從節(jié)點(diǎn)r的h-距離鄰居節(jié)點(diǎn)列表中選擇和節(jié)點(diǎn)j的距離最近的節(jié)點(diǎn)作為下一跳中繼節(jié)點(diǎn)r

}。

本發(fā)明中，所述h為節(jié)點(diǎn)j和中繼節(jié)點(diǎn)r的距離。

本發(fā)明的有益效果是：本發(fā)明中的所有節(jié)點(diǎn)被認(rèn)為是一顆完全二叉樹上均勻分布的葉子節(jié)點(diǎn)，任意兩個節(jié)點(diǎn)之間的距離定義為這兩個節(jié)點(diǎn)在二叉樹中的最低共同祖先節(jié)點(diǎn)的高度；對于該P(yáng)2P協(xié)議中的每個節(jié)點(diǎn)，如果存在和它距離為h的節(jié)點(diǎn)，則至少保證其中的一個節(jié)點(diǎn)作為該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)，該P(yáng)2P協(xié)議的平均路由路徑長度為(log2N)/2，路由成功率為100％，節(jié)點(diǎn)平均度數(shù)為(log2N)，節(jié)點(diǎn)加入P2P協(xié)議時(shí)所需發(fā)送的消息個數(shù)是(log2N)/2；與之前的主要P2P網(wǎng)絡(luò)相比，該P(yáng)2P協(xié)議的優(yōu)點(diǎn)是性能指標(biāo)的復(fù)雜度都是對數(shù)量級，穩(wěn)定性好。

附圖說明

圖1為樹T(H)的等腰三角特性示意圖。

具體實(shí)施方式：

為了使本發(fā)明的技術(shù)手段、創(chuàng)作特征與達(dá)成目的易于明白理解，以下結(jié)合具體實(shí)施例進(jìn)一步闡述本發(fā)明

本發(fā)明的一種基于層次化可導(dǎo)航網(wǎng)絡(luò)的P2P協(xié)議，包括節(jié)點(diǎn)加入、節(jié)點(diǎn)退出以及路由。

本發(fā)明中，層次化可導(dǎo)航網(wǎng)絡(luò)模型；

首先，定義一個完全二叉樹T(H)，該樹具有2H個葉子節(jié)點(diǎn)，高度為H，其中葉子節(jié)點(diǎn)的高度為0，根節(jié)點(diǎn)的高度為H-1；對于任意兩個葉子節(jié)點(diǎn)u和v，定義它們之間的距離h(u，v)為它們在樹T(H)中的最低共同祖先節(jié)點(diǎn)的高度；在這樣的距離定義下，樹T(H)具有等腰三角特性：如圖1所示，對于任何葉子節(jié)點(diǎn)u，所有和u的距離為h的葉子節(jié)點(diǎn)集內(nèi)的節(jié)點(diǎn)之間的距離都小于h。

其次，定義層次化可導(dǎo)航網(wǎng)絡(luò)模型G(N，H，k)，該網(wǎng)絡(luò)模型G(N，H，k)為：

圖G具有N個節(jié)點(diǎn)，這些節(jié)點(diǎn)均勻分布在樹T(H)的葉子節(jié)點(diǎn)集合中。