對等網(wǎng)絡(luò)分組搜索算法研究.pdf

1、隨著Internet的發(fā)展和用戶的不斷增多，對等網(wǎng)絡(luò)作為一種新的網(wǎng)絡(luò)應(yīng)用模式受到了國際上廣泛的關(guān)注，越來越多的專家、學(xué)者投身到對等網(wǎng)絡(luò)的研究和探討當(dāng)中，取得了一系列的研究成果，但是大多研究成果都集中在有結(jié)構(gòu)對等網(wǎng)絡(luò)方面，對無結(jié)構(gòu)對等網(wǎng)絡(luò)的研究還很少。 當(dāng)前，無結(jié)構(gòu)對等網(wǎng)絡(luò)由于搜索的靈活性和對動態(tài)環(huán)境的適應(yīng)性，得到了廣泛的應(yīng)用，已經(jīng)成為對等網(wǎng)絡(luò)的主流。但無結(jié)構(gòu)對等網(wǎng)絡(luò)的資源搜索效率比較低，這就使得無結(jié)構(gòu)對等網(wǎng)絡(luò)的搜索算法一直是人們

2、研究的重點(diǎn)。 本論文詳細(xì)分析了對等網(wǎng)絡(luò)的搜索算法和應(yīng)用，研究了無結(jié)構(gòu)對等網(wǎng)絡(luò)的搜索算法，首次提出了根據(jù)節(jié)點(diǎn)之間的通信延遲來實(shí)現(xiàn)網(wǎng)絡(luò)節(jié)點(diǎn)分組的理論和概念，進(jìn)而提出了無結(jié)構(gòu)對等網(wǎng)絡(luò)的分組算法、組內(nèi)平臺搜索算法、基于查詢代理的多組同步搜索算法，并在理論和大量的仿真實(shí)驗(yàn)上驗(yàn)證了這些算法的正確和高效性。 本文通過對無結(jié)構(gòu)對等網(wǎng)絡(luò)的特性研究，提出了組內(nèi)分級的概念。組內(nèi)分級就是把通常網(wǎng)絡(luò)中的分層思想變換推廣到組內(nèi)節(jié)點(diǎn)的分級管理，突出核

3、心級的地位，并在核心級中提出管理節(jié)點(diǎn)和管理域，以便對組進(jìn)行維護(hù)。本文提出的組內(nèi)節(jié)點(diǎn)分級管理的方法極大地降低了查詢消息冗余，提高了組內(nèi)搜索速度和網(wǎng)絡(luò)中組的覆蓋率。 本文通過對網(wǎng)絡(luò)中存在網(wǎng)絡(luò)通信質(zhì)量極差的節(jié)點(diǎn)的研究，提出了附屬節(jié)點(diǎn)的概念。附屬節(jié)點(diǎn)不屬于任何一個組，它可以搜索其它節(jié)點(diǎn)，但是其它節(jié)點(diǎn)不能在此節(jié)點(diǎn)上搜索資源。 本文用NS2軟件做了大量的仿真實(shí)驗(yàn)。實(shí)驗(yàn)采用了自定義均勻隨機(jī)圖模型和自定義節(jié)點(diǎn)間通信質(zhì)量作為網(wǎng)絡(luò)拓?fù)洌謩e

4、對算法中的延遲、負(fù)載、查詢覆蓋率、查詢消息冗余率、查詢結(jié)果冗余率、可擴(kuò)展性方面作了數(shù)據(jù)統(tǒng)計，并針對實(shí)驗(yàn)數(shù)據(jù)作了有效分析，實(shí)驗(yàn)結(jié)果驗(yàn)證了算法的有效性和可行性。 本文對無結(jié)構(gòu)對等網(wǎng)絡(luò)分組搜索算法提出了優(yōu)化策略。優(yōu)化網(wǎng)絡(luò)的結(jié)構(gòu)，定義組內(nèi)級與級之間的界限，使節(jié)點(diǎn)能夠自適應(yīng)的形成組，擴(kuò)大了組內(nèi)核心級的規(guī)模，優(yōu)化了組內(nèi)搜索的速度。結(jié)合改進(jìn)的分組算法，提出了一種新的跨組搜索算法，能夠根據(jù)查詢結(jié)果選擇外組搜索，降低了查詢開銷和結(jié)果冗余。通過仿真

5、實(shí)驗(yàn)，驗(yàn)證了改進(jìn)的分組搜索算法的優(yōu)越性。 本文的主要創(chuàng)新成果如下： 1）提出了基于通信質(zhì)量的無結(jié)構(gòu)對等網(wǎng)絡(luò)的分組算法。無結(jié)構(gòu)對等網(wǎng)絡(luò)盲搜索算法的主要目的是提高搜索速度、控制查詢規(guī)模、降低冗余和開銷，但現(xiàn)有算法都存在一些不足，尤其是對對等網(wǎng)絡(luò)中窄帶寬的處理都不盡人意。本文通過對無結(jié)構(gòu)對等網(wǎng)絡(luò)體系結(jié)構(gòu)和邏輯結(jié)構(gòu)進(jìn)行了深入細(xì)致的研究與分析，提出了依據(jù)無結(jié)構(gòu)對等網(wǎng)絡(luò)節(jié)點(diǎn)間的通信延遲將網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行邏輯分組的算法。該算法的核心思想是

6、將無結(jié)構(gòu)對等網(wǎng)絡(luò)中節(jié)點(diǎn)之間通信質(zhì)量高的節(jié)點(diǎn)劃分成一個組，使得原來節(jié)點(diǎn)之間的頻繁窄帶通信變成組與組之間的單一窄帶通信，從而有效地提高查詢速度，降低網(wǎng)絡(luò)通信開銷。該算法的規(guī)則是：以網(wǎng)絡(luò)節(jié)點(diǎn)之間的通信質(zhì)量為節(jié)點(diǎn)成組的標(biāo)準(zhǔn)，使質(zhì)量高的節(jié)點(diǎn)聚集在組內(nèi)核心級中，其它節(jié)點(diǎn)處在組的外圍，依附于組內(nèi)核心繳。 2）提出了無結(jié)構(gòu)對等網(wǎng)絡(luò)中基于分組的平臺搜索算法。本文根據(jù)分組后的組內(nèi)節(jié)點(diǎn)之間通信質(zhì)量高的特點(diǎn)，在組內(nèi)分級思想的指導(dǎo)下，提出了分組后的組內(nèi)平

7、臺搜索算法。該算法兼顧了搜索的速度與深度，同時只需付出較小的開銷。 3）提出了通過查詢代理實(shí)現(xiàn)多組同步搜索的算法。該算法的核心思想是：將無結(jié)構(gòu)對等網(wǎng)絡(luò)按照本文的分組算法分組后，在每個組內(nèi)按照一定的規(guī)則設(shè)置查詢代理節(jié)點(diǎn)，查詢發(fā)起點(diǎn)通過與外組查詢代理節(jié)點(diǎn)之間的邏輯連接，根據(jù)不同的搜索要求，查詢發(fā)起點(diǎn)將查詢消息按照不同的發(fā)送策略發(fā)送給外組的查詢代理節(jié)點(diǎn)，各查詢代理節(jié)點(diǎn)在本組內(nèi)快速查詢后，將本組的查詢結(jié)果按照不同的返回策略返回給查詢發(fā)起