基于節(jié)點(diǎn)流行度的gnutella路由查詢策略

1、基于節(jié)點(diǎn)流行度的基于節(jié)點(diǎn)流行度的Gnutella路由查詢策略路由查詢策略Gnutella網(wǎng)絡(luò)因?yàn)闆](méi)有中心服務(wù)器，對(duì)等節(jié)點(diǎn)查詢消息完全由加入系統(tǒng)的對(duì)等節(jié)點(diǎn)轉(zhuǎn)發(fā)，所以被認(rèn)為是純分布式P2P系統(tǒng)。傳統(tǒng)的Gnutella網(wǎng)絡(luò)搜索算法[8]利用廣播方法來(lái)進(jìn)行查詢。這種方法會(huì)造成網(wǎng)絡(luò)中查詢消息以指數(shù)級(jí)增長(zhǎng)，在網(wǎng)絡(luò)中產(chǎn)生大量冗余查詢消息，造成局部網(wǎng)絡(luò)擁塞，出現(xiàn)分片現(xiàn)象。研究表明[1]，Gnutella網(wǎng)絡(luò)中文件被訪問(wèn)的頻率呈冪律特征，即少數(shù)文件流行度

2、很高被頻繁請(qǐng)求查詢，而多數(shù)文件則很少被訪問(wèn)?？萍颊撐摹＞W(wǎng)絡(luò)中流行度較高的文件會(huì)在網(wǎng)絡(luò)中留下較多副本，因此，流行度較高的文件更容易查詢成功。Gnutella網(wǎng)絡(luò)呈現(xiàn)典型的冪規(guī)律（powerlow）和明顯的小世界(smallwld)特征[2]。研究表明，Gnutella網(wǎng)絡(luò)節(jié)點(diǎn)的拓?fù)涮卣骶哂袃缫?guī)律（Powerlower）[2]特性和小世界特征[2]。1)冪規(guī)律(PowerLaw)特征即度為k的節(jié)點(diǎn)的分布概率滿足以下公式：2)小世界(Smal

3、lWld)特征的意思是網(wǎng)絡(luò)拓?fù)渚哂懈呔奂鹊吞卣髀窂介L(zhǎng)特征?？萍颊撐摹＞W(wǎng)絡(luò)聚集度和特征路徑長(zhǎng)的定義簡(jiǎn)述如下。在符合小世界特征的網(wǎng)絡(luò)模型中，可以根據(jù)節(jié)點(diǎn)的聚集度將節(jié)點(diǎn)劃分為一個(gè)個(gè)的Clusters具有強(qiáng)聚集性的節(jié)點(diǎn)具有很高的連通度。如何提高Gnutella網(wǎng)絡(luò)查詢效率近年來(lái)一直是研究熱點(diǎn)，傳統(tǒng)的Flooding算法雖然可以獲得較高的查詢效率，但是會(huì)造成大量本算法的主要思想是查詢時(shí)充分利用Gnutella網(wǎng)絡(luò)拓?fù)涮卣骱土餍卸鹊难芯砍晒?。查?/p>

4、充分利用節(jié)點(diǎn)流行度和Gnutella網(wǎng)絡(luò)拓?fù)涮卣?，采用類似隨機(jī)漫步的思想，轉(zhuǎn)發(fā)查詢消息給節(jié)點(diǎn)度和流行度大的節(jié)點(diǎn)。在介紹本文算法前，先給出以下定義：3.2.1節(jié)點(diǎn)要保存的數(shù)據(jù)結(jié)構(gòu)節(jié)點(diǎn)中除了要保存鄰居節(jié)點(diǎn)的信息之外，還要保存每個(gè)鄰居節(jié)點(diǎn)的查詢度信息。查詢消息到達(dá)時(shí)，節(jié)點(diǎn)根據(jù)每個(gè)鄰居節(jié)點(diǎn)的查詢度信息來(lái)確定查詢消息轉(zhuǎn)發(fā)對(duì)象。該數(shù)據(jù)結(jié)構(gòu)通過(guò)定期的心跳機(jī)制來(lái)更新。節(jié)點(diǎn)要保存的數(shù)據(jù)結(jié)構(gòu)節(jié)點(diǎn)將每個(gè)鄰居節(jié)點(diǎn)按查詢度排序，由高到低。查詢時(shí)，在鄰居節(jié)點(diǎn)中選擇

5、一定數(shù)量的鄰居節(jié)點(diǎn)發(fā)出查詢消息。選擇的策略將在下文詳細(xì)介紹。3.2.2基于流行度的Gnutella無(wú)結(jié)構(gòu)化網(wǎng)絡(luò)路由查詢策略本文提出的搜索方法利用節(jié)點(diǎn)的流行度和Gnutella網(wǎng)絡(luò)特征，節(jié)點(diǎn)加入網(wǎng)絡(luò)后，通過(guò)和鄰居節(jié)點(diǎn)交換信息從而得到每個(gè)鄰居節(jié)點(diǎn)的查詢度信息。查詢度信息是綜合節(jié)點(diǎn)的流行度和節(jié)點(diǎn)的聚集度的一個(gè)參數(shù)。查詢時(shí)，節(jié)點(diǎn)選擇鄰居節(jié)點(diǎn)中查詢度較高的作為路由查詢消息轉(zhuǎn)發(fā)對(duì)象。節(jié)點(diǎn)的流行度和聚集度越高，查詢成功的概率越大，因?yàn)橛晌墨I(xiàn)[1]中的