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

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

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

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

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

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