基于對(duì)等網(wǎng)絡(luò)的資源搜索策略的研究.pdf

1、近年來，隨著Internet的飛速發(fā)展、網(wǎng)絡(luò)帶寬的成倍增加以及計(jì)算機(jī)計(jì)算能力的大大提高，對(duì)等網(wǎng)絡(luò)逐漸引起了來自工業(yè)界和學(xué)術(shù)界越來越多的關(guān)注。對(duì)等網(wǎng)絡(luò)通過對(duì)等和分布式的方式，在網(wǎng)絡(luò)中不同節(jié)點(diǎn)間提供空閑的CPU處理能力，磁盤空間以及網(wǎng)絡(luò)帶寬。除了采用中央索引服務(wù)器的集中式對(duì)等網(wǎng)絡(luò)之外，從網(wǎng)絡(luò)拓?fù)渖希瑢?duì)等網(wǎng)絡(luò)還可以分為無結(jié)構(gòu)對(duì)等網(wǎng)絡(luò)和基于分布式哈希表的結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)。與任何大規(guī)模的分布式系統(tǒng)一樣，對(duì)等網(wǎng)絡(luò)系統(tǒng)成功與否不僅在于其網(wǎng)絡(luò)結(jié)構(gòu)的合理和

2、有效，而且在很大程度上還取決于其資源搜索策略的靈活性和可擴(kuò)展性。
　　 對(duì)等網(wǎng)絡(luò)的資源搜索策略可以分為兩種類型：基于關(guān)鍵字的搜索和基于全文的搜索。無結(jié)構(gòu)對(duì)等網(wǎng)絡(luò)采用類似泛洪的盲目搜索機(jī)制，雖然可以支持上面兩種類型的查詢，但搜索的效率和可擴(kuò)展性都較低；結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)依據(jù)文檔標(biāo)識(shí)符進(jìn)行查找，可擴(kuò)展性和查找效率都較高，但是采用內(nèi)容的哈希(Hash)值作為索引，其索引和內(nèi)容語義無關(guān)，無法真正做到全文檢索。
　　 對(duì)等網(wǎng)絡(luò)的資源搜

3、索的研究中，邏輯拓?fù)浣Y(jié)構(gòu)的組織方式和數(shù)據(jù)索引的放置方式是兩個(gè)很重要的研究內(nèi)容。
　　 在基于關(guān)鍵字檢索的對(duì)等網(wǎng)絡(luò)平臺(tái)的設(shè)計(jì)中，首先充分考慮節(jié)點(diǎn)網(wǎng)絡(luò)鄰近性特征，通過節(jié)點(diǎn)類劃分的方法將物理距離較近的節(jié)點(diǎn)歸為一組，以確保網(wǎng)絡(luò)中鄰近節(jié)點(diǎn)間的路由過程大部分能在組內(nèi)部完成，從而避免了Chord 等網(wǎng)絡(luò)存在的繞路問題，并能夠降低系統(tǒng)路由時(shí)間開銷，減少發(fā)送消息的數(shù)量，據(jù)此提出了使用Landmark 策略進(jìn)行節(jié)點(diǎn)類劃分的方法；然后，由于網(wǎng)絡(luò)中的工

4、作負(fù)載都是有空間和時(shí)間的局部性，而且用戶總是趨向于查找自己感興趣的資源，這些資源通常屬于同一個(gè)類別，因此根據(jù)數(shù)據(jù)的類別進(jìn)行數(shù)據(jù)索引的存放，使得同一類數(shù)據(jù)索引放在相近的節(jié)點(diǎn)上，然后根據(jù)類檢索表，可以快速的找到同一類別的數(shù)據(jù)；另外，小世界現(xiàn)象在網(wǎng)絡(luò)中廣泛存在的，將非確定性緩存策略應(yīng)用于路由表，然后采用SW (Small World)緩存置換策略，使得對(duì)等網(wǎng)絡(luò)能夠逐漸收斂于小世界模型；在最后的理論分析和性能測評(píng)中，表明了這種策略能夠提高系統(tǒng)的

5、查找性能并且可以減少系統(tǒng)的維護(hù)開銷。
　　 在基于全文檢索的對(duì)等網(wǎng)絡(luò)平臺(tái)的設(shè)計(jì)中，首先考慮了數(shù)據(jù)索引的放置和定位策略。使用一個(gè)平衡樹(文檔聚類樹)來組織對(duì)等網(wǎng)絡(luò)環(huán)境中的共享數(shù)據(jù)，通過調(diào)節(jié)平衡因子的大小，可以控制和減小文檔搜索的時(shí)間復(fù)雜度；然后，給出一個(gè)簡單的樹節(jié)點(diǎn)放置策略，從而保證了系統(tǒng)的負(fù)載均衡以及保證了系統(tǒng)的容錯(cuò)性；隨后，提出TRES-CORE 查詢策略，使得每個(gè)查詢對(duì)每個(gè)節(jié)點(diǎn)只操作一次，降低了分布式環(huán)境下的查詢時(shí)間，避免了

6、查詢中的路由繞路問題。另外，使用向量空間模型(VectorSpace Model，簡稱VSM)技術(shù)提取全文的數(shù)據(jù)索引，通常會(huì)有成千上萬個(gè)關(guān)鍵字，對(duì)應(yīng)了成千上萬維的特征空間。這些高維的特征集對(duì)資源索引的建立是非常有害的。
　　 進(jìn)而，提出了基于粗糙集的文檔空間降維技術(shù)來提高資源的搜索性能。
　　 邏輯拓?fù)浣Y(jié)構(gòu)的組織方式，是基于全文檢索的對(duì)等網(wǎng)絡(luò)平臺(tái)設(shè)計(jì)中的另外一個(gè)重要研究內(nèi)容。首先，采用分層的方式給出了一個(gè)對(duì)等網(wǎng)絡(luò)資源檢索

7、的通用模型，并設(shè)計(jì)了每層之間的接口。采用分層的結(jié)構(gòu)，可以使得模型具有較強(qiáng)的適應(yīng)性，當(dāng)某層策略發(fā)生改變時(shí)，其它層次的策略可以不變。隨后，基于擴(kuò)展性好、查詢效果好、不存在系統(tǒng)瓶頸以及能夠支持全文檢索的目標(biāo)，提出了一個(gè)半結(jié)構(gòu)化混合模型。
　　 在半結(jié)構(gòu)化混合模型中，所有節(jié)點(diǎn)根據(jù)物理位置分成若干個(gè)節(jié)點(diǎn)類。每個(gè)節(jié)點(diǎn)類中存在一個(gè)超級(jí)節(jié)點(diǎn)(Super Peer，簡稱SP)和若干個(gè)普通節(jié)點(diǎn)(Ordinary Peer，簡稱OP)。超級(jí)節(jié)點(diǎn)采用分

8、布式哈希表(Distribute Hash Table，簡稱DHT)的方式進(jìn)行組織，每個(gè)節(jié)點(diǎn)類中所有的節(jié)點(diǎn)以非結(jié)構(gòu)化的方式組織。在這里，半結(jié)構(gòu)是指在系統(tǒng)的構(gòu)造中同時(shí)存在結(jié)構(gòu)化和非結(jié)構(gòu)化的組織方式；混合是指在系統(tǒng)中仍然存在超級(jí)節(jié)點(diǎn)SP，但此時(shí)SP 記載用于節(jié)點(diǎn)和文檔的分類信息，并不維護(hù)整個(gè)節(jié)點(diǎn)類中所有共享文檔的索引信息，從而部分解決了SP是系統(tǒng)瓶頸的問題。在最后的實(shí)驗(yàn)測試中，可以獲知這個(gè)設(shè)計(jì)在能夠完成全文搜索的前提下，在資源搜索效率上也有