基于節(jié)點(diǎn)興趣的非結(jié)構(gòu)化P2P網(wǎng)絡(luò)資源搜索算法

1、基于節(jié)點(diǎn)興趣的非構(gòu)造化P2P網(wǎng)絡(luò)資源搜索算法基于節(jié)點(diǎn)興趣的非構(gòu)造化P2P網(wǎng)絡(luò)資源搜索算法1 引言P2P網(wǎng)絡(luò)中最關(guān)鍵的問題是如何高效地搜索資源。當(dāng)節(jié)點(diǎn)在自身找不到想要的資源時(shí)，就會發(fā)出搜索懇求，搜索過程涉及消息形式、懇求轉(zhuǎn)發(fā)方式、轉(zhuǎn)發(fā)節(jié)點(diǎn)選擇、節(jié)點(diǎn)局部索引等方面。不同網(wǎng)絡(luò)構(gòu)造可能會采用不同的搜索方法。當(dāng)前的P2P網(wǎng)絡(luò)可以分成兩大類：構(gòu)造化和非構(gòu)造化。非構(gòu)造化網(wǎng)絡(luò)因其簡單和強(qiáng)健性獲得廣泛應(yīng)用，Gnutella是其中的典型模型。2 改進(jìn)的搜索算法一個(gè)節(jié)點(diǎn)需要的資源，更可能在 跟自己興趣相似的節(jié)點(diǎn)中搜索到。假設(shè)在某個(gè)節(jié)點(diǎn)成功搜索到需要的資源，說明兩節(jié)點(diǎn)興趣相似，下次該節(jié)點(diǎn)成功搜索的可能性會也進(jìn)步?；?/p>

2、這個(gè)思想，在Gnutella的搜索模型上，提出了基于節(jié)點(diǎn)興趣和搜索經(jīng)歷的資源搜索算法。2.1 相關(guān)概念定義1元數(shù)據(jù)：對一個(gè)資源的描繪，通常包括資源的唯一標(biāo)識通常為資源的Hash值、屬性如標(biāo)題，作者，創(chuàng)立時(shí)間，關(guān)鍵字等以及資源的存儲位置。在搜索算法中，對資源的搜索轉(zhuǎn)化為對元數(shù)據(jù)相關(guān)數(shù)據(jù)的搜索。定義3鄰居節(jié)點(diǎn)：假設(shè)一個(gè)peer Pi和另一個(gè)peer Pj直接相連，那么它們互稱為鄰居節(jié)點(diǎn)。定義4 朋友節(jié)點(diǎn)：假設(shè)一個(gè)peer Pi和另一個(gè)peer Pj有相似的興趣，那么它們互稱為朋友節(jié)點(diǎn)。定義5 興趣相似系數(shù)用來描繪節(jié)點(diǎn)間的相似性。系數(shù)越高，節(jié)點(diǎn)相似性越高。定義為：1其中l(wèi)e;12對任意節(jié)點(diǎn)Pi和Pj

3、，SPi，Pj= SPj，Pi 。定義6 捷徑節(jié)點(diǎn)：假設(shè)一個(gè)peer Pi和另一個(gè)peer Pj既是鄰居節(jié)點(diǎn)優(yōu)勢朋友節(jié)點(diǎn)，那么它們互稱為捷徑節(jié)點(diǎn)2.2 分組策略改進(jìn)的搜索算法，根據(jù)節(jié)點(diǎn)間網(wǎng)絡(luò)拓?fù)浜团d趣相似度的關(guān)系，將節(jié)點(diǎn)分組為鄰居節(jié)點(diǎn)、朋友節(jié)點(diǎn)以及捷徑節(jié)點(diǎn)。2.2 .1建立鄰居節(jié)點(diǎn)鄰居節(jié)點(diǎn)的劃分采用了底層搜索機(jī)制來發(fā)現(xiàn)鄰居節(jié)點(diǎn)。這里的鄰居節(jié)點(diǎn)直接連接并非指應(yīng)用層的路由，而是實(shí)際網(wǎng)絡(luò)層中的路由間隔 ，可以防止應(yīng)用層中路由的一跳在實(shí)際網(wǎng)絡(luò)層相距較遠(yuǎn)的情況出現(xiàn)，也更加接近實(shí)際網(wǎng)絡(luò)拓?fù)錁?gòu)造，能獲得更加有效的路由。建立鄰居節(jié)點(diǎn)步驟：2Pi根據(jù)網(wǎng)絡(luò)的規(guī)模選擇一個(gè)適宜的TTL值發(fā)出Ping命令，主動探測與自

4、己相通的節(jié)點(diǎn)；3收到該消息的節(jié)點(diǎn)Pj，PkPm將返回應(yīng)答消息。應(yīng)答消息包含返回消息經(jīng)過的跳數(shù)Hop和返回消息的節(jié)點(diǎn)IP，以及返回消息節(jié)點(diǎn)的本地資源信息表；4節(jié)點(diǎn)Pi將根據(jù)收到的應(yīng)答消息中的Hop和收到消息的時(shí)間進(jìn)展排序。Hop越小那么說明應(yīng)答節(jié)點(diǎn)與Pi越接近。根據(jù)網(wǎng)絡(luò)規(guī)模Pi選擇一定數(shù)量Hop較小一般取Hop=1的節(jié)點(diǎn)作為鄰居節(jié)點(diǎn)。5節(jié)點(diǎn)Pi向選擇的鄰居節(jié)點(diǎn)發(fā)送消息。鄰居節(jié)點(diǎn)根據(jù)收到消息的時(shí)延等因素決定是否將其作為鄰居節(jié)點(diǎn)。2.2 .2 建立朋友節(jié)點(diǎn)在保證消息的轉(zhuǎn)發(fā)是在沿著實(shí)際間隔 位置上盡可能短的間隔 上進(jìn)展的根底上，消息應(yīng)該盡可能轉(zhuǎn)發(fā)給最有可能存儲查詢資源的節(jié)點(diǎn)，因此查詢消息要轉(zhuǎn)發(fā)給興趣最

5、相似的節(jié)點(diǎn)。建立朋友節(jié)點(diǎn)的步驟：1假設(shè)節(jié)點(diǎn)Pi是新參加的節(jié)點(diǎn)，在建立鄰居節(jié)點(diǎn)時(shí)，根據(jù)其他節(jié)點(diǎn)返回的本地信息表，可以計(jì)算出其他節(jié)點(diǎn)與Pi的興趣相似度。根據(jù)興趣相似度將節(jié)點(diǎn)排序，根據(jù)網(wǎng)絡(luò)規(guī)模取一定數(shù)量的相似度較高的節(jié)點(diǎn)作為朋友節(jié)點(diǎn)。2節(jié)點(diǎn)Pi將與其他節(jié)點(diǎn)的興趣相似度發(fā)給對應(yīng)的節(jié)點(diǎn)。其他節(jié)點(diǎn)根據(jù)其相似度決定是否將Pi作為自己的朋友節(jié)點(diǎn)。3將所有的朋友節(jié)點(diǎn)按照興趣相似度和查詢歷史排序。當(dāng)有新的節(jié)點(diǎn)參加時(shí)那么將排在最后面的節(jié)點(diǎn)刪除，再參加新的朋友節(jié)點(diǎn)。2.2 .3 建立捷徑節(jié)點(diǎn)節(jié)點(diǎn)的捷徑節(jié)點(diǎn)就是那些與節(jié)點(diǎn)間隔 最近、興趣相似的節(jié)點(diǎn)，即鄰居節(jié)點(diǎn)集和朋友節(jié)點(diǎn)集的交集。2.3 搜索機(jī)制節(jié)點(diǎn)進(jìn)展資源搜索的過程就

6、是查詢消息在網(wǎng)絡(luò)中進(jìn)展路由的過程。進(jìn)展搜索的根據(jù)就是節(jié)點(diǎn)維護(hù)的路由信息和采用的路由策略。節(jié)點(diǎn)按照分組不同搜集和保存一定的路由信息，使得路由盡量選擇間隔 最近且興趣最相似的節(jié)點(diǎn)。2.3 .1 節(jié)點(diǎn)路由信息1節(jié)點(diǎn)Pi參加系統(tǒng)后，建立鄰居節(jié)點(diǎn)、朋友節(jié)點(diǎn)和捷徑節(jié)點(diǎn)，然后建立相應(yīng)的鄰居節(jié)點(diǎn)、朋友節(jié)點(diǎn)和捷徑節(jié)點(diǎn)的索引表。2在節(jié)點(diǎn)進(jìn)展查詢時(shí)和節(jié)點(diǎn)共享資源更新時(shí)動態(tài)地維護(hù)索引表。當(dāng)有節(jié)點(diǎn)Pj退出系統(tǒng)時(shí)，本地節(jié)點(diǎn)Pi假設(shè)在Pj的索引表內(nèi)，會收到Pj退出系統(tǒng)的消息，然后把Pi的索引表內(nèi)Pj相關(guān)信息刪除。假設(shè)Pi不在Pj的索引表內(nèi)，雖然不能收到退出消息，但由于此鏈接不存在經(jīng)過幾次查詢的正反響，將會從索引表中刪除。1

7、為 ；rho;為信息量的揮發(fā)率，通常0rho;1防止信息量無限累加；Delta;delta;為信息增量，是該搜索成功消息留在Pj的信息量，即表征了此次成功搜索對下次搜索的影響，計(jì)算公式為：Delta;delta;-middot;TTLDelta;delta;middot;TTL3其中n為一個(gè)常量系數(shù)；TTL為搜索成功消息到達(dá)Pi節(jié)點(diǎn)的存活時(shí)間，因此離目的越近，其信息量越大。根據(jù)當(dāng)返回一條搜索成功的消息時(shí)，需要沿途修改各節(jié)點(diǎn)的路由信息表。在Pj中找到Pi需要的資源，中間經(jīng)過Pm，PnPl等節(jié)點(diǎn)，成功消息返回Pi時(shí)也要修改Pm中相對Pj的興趣相似度、Pn中相對Pj的興趣相似度Pl中相對Pj的興趣相

8、似度。3當(dāng)節(jié)點(diǎn)分開系統(tǒng)時(shí)，給自己索引表中的節(jié)點(diǎn)發(fā)送一個(gè)分開系統(tǒng)的消息，索引表中的節(jié)點(diǎn)收到該信息，那么將發(fā)送分開消息的節(jié)點(diǎn)從自己的索引表中刪除。2.3 .2 搜索策略1當(dāng)一個(gè)節(jié)點(diǎn)發(fā)起搜索懇求后，首先判斷該節(jié)點(diǎn)是否有索引表。假設(shè)沒有，說明節(jié)點(diǎn)是新參加節(jié)點(diǎn)，采用底層搜索機(jī)制進(jìn)展搜索。2假設(shè)節(jié)點(diǎn)已經(jīng)有了索引表，那么將查詢懇求轉(zhuǎn)發(fā)給所有的捷徑節(jié)點(diǎn)。捷徑節(jié)點(diǎn)查詢本地資源表，假設(shè)查詢成功那么返回查詢結(jié)果，假設(shè)沒有獲得查詢結(jié)果那么將查詢懇求轉(zhuǎn)發(fā)給自己的捷徑節(jié)點(diǎn)。3假設(shè)通過捷徑節(jié)點(diǎn)沒有獲得查詢結(jié)果，那么將查詢懇求轉(zhuǎn)發(fā)給朋友節(jié)點(diǎn)。朋友節(jié)點(diǎn)查詢本地資源表，假設(shè)查詢成功那么返回查詢結(jié)果，假設(shè)沒有獲得查詢結(jié)果那么將查詢懇求轉(zhuǎn)發(fā)給自己的朋友節(jié)點(diǎn)。4假設(shè)通過朋友節(jié)點(diǎn)沒有獲得查詢結(jié)果，那么將查詢懇求轉(zhuǎn)發(fā)給朋友節(jié)點(diǎn)。鄰居節(jié)點(diǎn)查詢本地資源表，假設(shè)查詢成功那么返回查詢結(jié)果，假設(shè)沒有獲得查詢結(jié)果那么將查詢懇求轉(zhuǎn)發(fā)給自己的鄰居節(jié)點(diǎn)。5假設(shè)仍然沒有搜索到需要的資源，那么采用底層的搜索機(jī)制進(jìn)展搜索。3 實(shí)驗(yàn)結(jié)果分析為了評價(jià)本文的資源搜索算法是否有效，建立了仿真程序來模擬P2P環(huán)境，與泛洪算法和隨機(jī)漫步算法進(jìn)展了比較，試驗(yàn)結(jié)果充分證明了本文算法相對泛洪算法和隨機(jī)漫步算法的優(yōu)勢。本文提出一種基于興趣和搜索經(jīng)歷的搜索算法，該算法通過將