基于激勵的P2P非結(jié)構(gòu)化自我優(yōu)化搜索算法研究.pdf

1、隨著P2P的廣泛應用，基于P2P的應用研究日新月異，搜索技術(shù)就是其中之一。研究發(fā)現(xiàn)，在P2P網(wǎng)絡中，即使每個節(jié)點共享少量文件，整個網(wǎng)絡所共享的文件數(shù)量也是非常龐大，要想充分的利用這些分散的資源，就必須能夠迅速準確的找到它們，因此，P2P網(wǎng)絡搜索算法研究就成為了一個重要的研究課題。
　　 目前，在P2P搜索算法方面的研究主要有基于現(xiàn)有的非結(jié)構(gòu)化搜索算法的改進研究以及以DHT為主的結(jié)構(gòu)化搜索算法的研究。本文主要針對非結(jié)構(gòu)化P2P搜索

2、技術(shù)進行了分析和研究，詳細分析了泛洪和隨機漫步算法存在的問題，并在隨機漫步搜索的基礎(chǔ)上提出了自己的改進方案。
　　 在非結(jié)構(gòu)化P2P網(wǎng)絡搜索算法中，以Gnutella協(xié)議為基礎(chǔ)的泛洪方式的查詢以其獨立性和易于部署，成為占絕對優(yōu)勢的查詢。不過對TTL設(shè)置過高將產(chǎn)生大量的流量，而克服這種問題的隨機漫步盡管可以將網(wǎng)絡開銷降低，但是多個漫步者之間無法聯(lián)系通信同樣會造成冗余的查詢，而串行化的隨機漫步又導致了較大時延。泛洪和隨機漫步共同的問

3、題是它們在面對自私用戶的時候性能會急劇下降，對所有的用戶使用統(tǒng)一的TTL控制搜索并不能在用戶利益方面有所區(qū)分，對合作和貢獻都沒有激勵。很遺憾的是，搜索的性能極大的依賴于節(jié)點合作轉(zhuǎn)發(fā)和共享，然而，大多數(shù)P2P用戶天性是自私的。轉(zhuǎn)發(fā)和響應其他用戶的查詢將會耗費他們自己的資源，因此他們只下載文件從不向P2P網(wǎng)絡貢獻任何資源，這就是所謂的“搭便車”問題。因此，大部分的文件下載請求都是被定向到小部分的無私節(jié)點，這些小部分愿意共享的節(jié)點很容易過載,

4、這就造成所謂的“公共的悲劇”問題。另外，自私用戶也許會在等待搜索結(jié)果的時候重復發(fā)布同樣的查詢請求，如此多的搜索請求導致網(wǎng)絡擁塞。這些自私節(jié)點具有自私性，加入網(wǎng)絡目的明確，下載資源，一旦獲得即脫離網(wǎng)絡；非惡意性，按照協(xié)議轉(zhuǎn)發(fā)消息，不會惡意丟包和丟棄消息；以及理性，一切行為選擇都是為了自身利益最大化。以上這些行為極大的破壞了泛洪和隨機漫步的搜索性能。
　　 針對非結(jié)構(gòu)化P2P系統(tǒng)中主要的搜索方案都存在的共同問題：即大量自私節(jié)點的存在

5、，導致泛洪算法產(chǎn)生大量的網(wǎng)絡開銷以及隨機漫步產(chǎn)生查詢時延，統(tǒng)一的TTL控制使節(jié)點很容易受到自私用戶的攻擊，導致查詢性能下降。本文提出了基于激勵的自我優(yōu)化搜索算法ISS，該算法是建立在隨機漫步之上，通過建立一個激勵模型，引入激勵措施，給自私用戶提供有區(qū)分的查詢服務，把用戶的貢獻度和所享受的服務水平聯(lián)系起來，動態(tài)的調(diào)整隨機漫步的TTL值以及Walker的數(shù)量，讓其根據(jù)自身的條件和當前的網(wǎng)絡狀態(tài)進行自我優(yōu)化來調(diào)整搜索性能和網(wǎng)絡開銷，全面的約束