非結(jié)構(gòu)對(duì)等網(wǎng)絡(luò)中一種有效的資源搜索策略

1、非結(jié)構(gòu)對(duì)等網(wǎng)絡(luò)中一種有效的資源搜索策略摘要 :針對(duì)非結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)中資源搜索算法效率不高、 搜索過(guò)程中產(chǎn)生的冗余消息數(shù)過(guò)大而造成的網(wǎng)絡(luò)帶寬消耗 及網(wǎng)絡(luò)擁塞等狀況 ,提出一種基于路由搜索機(jī)制的改進(jìn)算法。 該算法利用鄰節(jié)點(diǎn)之間的關(guān)系 ,生成鄰節(jié)點(diǎn)的轉(zhuǎn)發(fā)路由表。 實(shí) 驗(yàn)證明 ,該算法有效抑制了網(wǎng)絡(luò)中冗余搜索消息數(shù)量,減小了網(wǎng)絡(luò)帶寬的消耗 ,有效避開(kāi)了搭便車節(jié)點(diǎn) ,從而提高了搜索效 率。關(guān)鍵詞 :對(duì)等網(wǎng) ;資源搜索 ;路由表 ;鄰接關(guān)系中圖分類號(hào) :TP301.5文獻(xiàn)標(biāo)志碼 :A 0 引言對(duì)等網(wǎng)絡(luò)(PeertoPeer,P2P中每個(gè)節(jié)點(diǎn)地位對(duì)等，既充當(dāng) 服務(wù)器 ,為其他節(jié)點(diǎn)提供服務(wù) ,同時(shí)也為客戶機(jī)

2、,享用其他節(jié)點(diǎn) 提供的服務(wù)。P2P網(wǎng)絡(luò)從結(jié)構(gòu)上分為無(wú)結(jié)構(gòu)化P2P和結(jié)構(gòu)化P2P。結(jié)構(gòu)化P2P網(wǎng)絡(luò)建立在分布式哈希表 (DistributedHashTableQHT)上，在給定資源索引下的情況下，能 夠在O(logN)跳之內(nèi)定位到目的節(jié)點(diǎn)，資源定位快，但需要以很高的代價(jià)維護(hù)既定拓?fù)?,而且節(jié)點(diǎn)的加入和退出所引起的網(wǎng) 絡(luò)波動(dòng)較大 ,不能很好地適應(yīng)高度動(dòng)態(tài)的P2P 環(huán)境。無(wú)結(jié)構(gòu)化P2P資源的搜索和定位通過(guò)消息擴(kuò)散來(lái)實(shí)現(xiàn)，容錯(cuò)性好，支持 復(fù)雜查詢 ,受節(jié)點(diǎn)頻繁加入和退出的影響小,但搜索數(shù)據(jù)幾乎是隨機(jī)搜索 ,容易造成網(wǎng)絡(luò)流量急劇增加 ,導(dǎo)致網(wǎng)絡(luò)擁塞。因 此，無(wú)結(jié)構(gòu)化P2P的一個(gè)核心問(wèn)題就是如何進(jìn)行資源

3、的快速 搜索 ,同時(shí)降低網(wǎng)絡(luò)帶寬消耗 ,保證系統(tǒng)可擴(kuò)展性和穩(wěn)定性。 本文主要討論無(wú)結(jié)構(gòu) P2P網(wǎng)絡(luò)環(huán)境下的搜索策略。1 問(wèn)題的描述及研究現(xiàn)狀Gnutella 是非結(jié)構(gòu)化網(wǎng)絡(luò)的典型代表 ,其設(shè)計(jì)思想簡(jiǎn)單 , 資源搜索采用洪泛搜索機(jī)制 ,每個(gè)節(jié)點(diǎn)在查找過(guò)程中將接收 到的搜索請(qǐng)求信息轉(zhuǎn)發(fā)給所有的鄰居節(jié)點(diǎn)。隨著對(duì)等網(wǎng)絡(luò)規(guī) 模的不斷增大 ,洪泛機(jī)制的弊端越來(lái)越明顯 :搜索過(guò)程中產(chǎn)生 大量冗余的消息 ,嚴(yán)重吞噬帶寬而使得系統(tǒng)極不可擴(kuò)展。 文獻(xiàn) 1中提出的隨機(jī)漫步(RandomWalk,RW)算法的基本思想是： 查詢節(jié)點(diǎn)將K個(gè)查詢請(qǐng)求轉(zhuǎn)發(fā)給在其相鄰節(jié)點(diǎn)中隨機(jī)選取的 K個(gè)節(jié)點(diǎn)，然后這K個(gè)節(jié)點(diǎn)將查詢請(qǐng)求隨機(jī)地向

4、它的一個(gè)相鄰 節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā) ,以此類推。這些請(qǐng)求消息叫作漫步者 ,漫步者 在搜索成功或者生存時(shí)間 (TimeToLive,TTL)tTTL為0時(shí)結(jié)束。相比洪泛方法 ,隨機(jī)漫步算法能大量減少消息冗余 ,最壞的情況下所產(chǎn)生的最大消息數(shù)為K•tTTL,但其搜索成功率隨著網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和K的選取有很大的變化。文獻(xiàn)2中指出Gnutella 具有 Powerlaw 特性 ,并依據(jù)這種特性提出了將搜索 請(qǐng)求轉(zhuǎn)發(fā)到度數(shù)較高的節(jié)點(diǎn) ,度數(shù)較高的節(jié)點(diǎn)指向更多的節(jié) 點(diǎn),包含了較多的信息。 文獻(xiàn) 3中給出了一種前向?qū)W習(xí)的方法 在這種方法中建議每個(gè)節(jié)點(diǎn)包含的元數(shù)據(jù)可以給出哪些節(jié) 點(diǎn)可能含有應(yīng)答信息的隱

5、含信息,依據(jù)此隱含信息可以選擇節(jié)點(diǎn)轉(zhuǎn)發(fā)請(qǐng)求信息。文獻(xiàn)4中的研究結(jié)果表明，在Gnutella中, 有 42%的節(jié)點(diǎn)不共享任何資源 ,而 10%的節(jié)點(diǎn)提供了大部分 的資源。文獻(xiàn) 5中提出的基于擴(kuò)散路由機(jī)制的改進(jìn)算法 (lmprovedalgorithmBasedSpreadRouting,ISR)在一定程度上控 制了節(jié)點(diǎn)轉(zhuǎn)發(fā)的搜索消息數(shù)量 ,但其未考慮到對(duì)等網(wǎng)絡(luò)中大 量存在的搭便車的自私節(jié)點(diǎn)及節(jié)點(diǎn)負(fù)載情況,使搜索的效率和可靠性大打折扣。由分析得 ,為提高無(wú)結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)中資源搜索效率 ,在 保持節(jié)點(diǎn)負(fù)載平衡的情況下 ,要使搜索消息盡量流向度數(shù)較 高的節(jié)點(diǎn) ,避開(kāi)自私節(jié)點(diǎn) ,同時(shí)降低搜索消息的冗余度

6、和減小 消息數(shù)據(jù)包的大小。 因此 ,本文提出了一種基于路由搜索機(jī)制 的改進(jìn)算法 ,較之洪泛算法和隨機(jī)漫步算法在搜索消息控制 及搜索效率方面均有較大的改進(jìn)。1 算法描述1.1 轉(zhuǎn)發(fā)路由表的引入通過(guò)研究 Gnutella 網(wǎng)絡(luò)中節(jié)點(diǎn)的聚集性和冪率特性,分析節(jié)點(diǎn)的鄰接關(guān)系 ,發(fā)現(xiàn)一個(gè)節(jié)點(diǎn)的直接前驅(qū)節(jié)點(diǎn)利用其鄰節(jié) 點(diǎn)集合能夠得知該節(jié)點(diǎn)的消息轉(zhuǎn)發(fā)路由。節(jié)點(diǎn) n 的搜索消息 轉(zhuǎn)發(fā)路由表由它的前驅(qū)節(jié)點(diǎn)生成,通過(guò)附加在搜索消息數(shù)據(jù)包中傳遞給節(jié)點(diǎn)n。網(wǎng)絡(luò)中各節(jié)點(diǎn)存儲(chǔ)各自的鄰居節(jié)點(diǎn)集合 Neighbor(n) 以及每個(gè)鄰節(jié)點(diǎn)的鄰節(jié)點(diǎn)集合 Connection(n,i)6, 即每個(gè)節(jié)點(diǎn)必須了解其鄰居節(jié)點(diǎn)的鄰接關(guān)系信

7、息,即每個(gè)節(jié)點(diǎn)都知道誰(shuí)與它的鄰居節(jié)點(diǎn)直接相連。這些信息相對(duì)比較穩(wěn) 定,只有當(dāng)網(wǎng)絡(luò)中有新的節(jié)點(diǎn)加入或者有節(jié)點(diǎn)離開(kāi)時(shí)才需要 更新 ,而這種更新可以通過(guò)在相鄰節(jié)點(diǎn)之間周期性交換鄰居 連接關(guān)系查詢包來(lái)觸發(fā)。有關(guān)定義如下。定義 1 集合 Neighbor(n) 表示節(jié)點(diǎn) n 的所有鄰接點(diǎn)集合。定義2設(shè)當(dāng)前節(jié)點(diǎn)為n,節(jié)點(diǎn)i是節(jié)點(diǎn)n的一個(gè)鄰節(jié)點(diǎn)，集 合 Connection(n,i) 表示節(jié)點(diǎn) n 的鄰節(jié)點(diǎn) i 的所有鄰節(jié)點(diǎn)的集合。定義 3 如果節(jié)點(diǎn) j 從節(jié)點(diǎn) i 接收到搜索消息數(shù)據(jù)包 ,節(jié)點(diǎn) k是節(jié)點(diǎn)j的待轉(zhuǎn)發(fā)節(jié)點(diǎn)，則稱節(jié)點(diǎn)i是節(jié)點(diǎn)j的直接前驅(qū)節(jié)點(diǎn), 節(jié)點(diǎn) k 是節(jié)點(diǎn) j 的直接后繼節(jié)點(diǎn)。設(shè)當(dāng)前節(jié)點(diǎn)為

8、n,節(jié)點(diǎn)i是節(jié)點(diǎn) n的直接后繼節(jié)點(diǎn)，節(jié)點(diǎn)i 的搜索消息轉(zhuǎn)發(fā)路由表Forward(i)=Connection(n,i)-(Neighbor(n) Q Neighbor(i)-n,即節(jié)點(diǎn) i 的轉(zhuǎn)發(fā)路由表為從其所有鄰節(jié)點(diǎn)中去掉與直接 前驅(qū)節(jié)點(diǎn) n 的共同鄰節(jié)點(diǎn)的剩余鄰節(jié)點(diǎn)集合,另外還要去掉節(jié)點(diǎn)n。這樣處理的目的是防止搜索消息回流和側(cè)向流動(dòng)，使得消息始終向外擴(kuò)散。 若將搜索起始點(diǎn)看作制高點(diǎn) ,則這種搜 索消息擴(kuò)散機(jī)制有類似于水流的特性。1.2 對(duì)節(jié)點(diǎn)負(fù)載及自私節(jié)點(diǎn)的控制研究表明 ,Gnutella 網(wǎng)絡(luò)具有很強(qiáng)的聚集性。所謂聚集性 是指網(wǎng)絡(luò)中的一些節(jié)點(diǎn)互相連接聚集在一起。具有聚集性的 節(jié)點(diǎn)具有很高的

9、連通度 ,又由于高連通度的節(jié)點(diǎn)與其他節(jié)點(diǎn) 聯(lián)系更為頻繁而顯示出更高的穩(wěn)定性和更豐富的資源 ,通過(guò) 它查找到待查資源概率較高。因此 ,若控制搜索消息流向高連通度的節(jié)點(diǎn) ,搜索效率和系統(tǒng)的穩(wěn)定性將會(huì)大大提高。在 P2P 這樣一個(gè)高度動(dòng)態(tài)和異構(gòu)的網(wǎng)絡(luò)中 ,各個(gè)節(jié)點(diǎn)都有計(jì)算和帶 寬的限制。節(jié)點(diǎn)接受查詢請(qǐng)求 ,執(zhí)行查詢處理 ,返回查詢結(jié)果 需要消耗一定的計(jì)算資源和網(wǎng)絡(luò)帶寬資源。本文引入節(jié)點(diǎn)負(fù) 載7和節(jié)點(diǎn)負(fù)載率的概念。定義 4 節(jié)點(diǎn)負(fù)載。節(jié)點(diǎn)在單位時(shí)間內(nèi)接受的查詢請(qǐng)求數(shù) 量,稱之為節(jié)點(diǎn)負(fù)載。定義5節(jié)點(diǎn)負(fù)載率。令節(jié)點(diǎn) n的能力為cn,負(fù)載為In,那 么n的負(fù)載率為un=ln/cn。令節(jié)點(diǎn)n的負(fù)載率閾值為tn,當(dāng) un > tn時(shí),稱節(jié)點(diǎn)n過(guò)載，否則稱節(jié)點(diǎn)n欠載。1.3 算法分析在算法中 ,每個(gè)節(jié)點(diǎn)維護(hù)著一個(gè)如表 1 所示的路由信息 表,表中存儲(chǔ)鄰節(jié)點(diǎn)的相關(guān)信息 ,表中各項(xiàng)按照節(jié)點(diǎn)連通度從 大到小順序排列。 搜索過(guò)程中 ,控制搜索消息流向連通度高