基于節(jié)點興趣的非結構化P2P網絡資源搜索算法

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

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

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

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

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

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

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

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