摘  要： 針對(duì)P2P系統(tǒng)中的搭便車問題，提出了一種基于混合策略博弈的激勵(lì)機(jī)制。將信譽(yù)值作為激勵(lì)節(jié)點(diǎn)貢獻(xiàn)資源和提供服務(wù)的基礎(chǔ),節(jié)點(diǎn)是否能獲得服務(wù)也是與節(jié)點(diǎn)當(dāng)前信譽(yù)值成比例的，節(jié)點(diǎn)只能通過提供服務(wù)來增加其信譽(yù)值。同時(shí)節(jié)點(diǎn)是否響應(yīng)服務(wù)請(qǐng)求是以某一概率來進(jìn)行的，通過調(diào)節(jié)該概率來有效的激勵(lì)節(jié)點(diǎn)提供服務(wù)。仿真實(shí)驗(yàn)表明，節(jié)點(diǎn)在經(jīng)過一段時(shí)間的博弈之后，其響應(yīng)次數(shù)和請(qǐng)求次數(shù)基本相等，提高了節(jié)點(diǎn)在系統(tǒng)中的參與度。
關(guān)鍵詞： 混合戰(zhàn)略博弈； P2P； 激勵(lì)； 信譽(yù)

    P2P系統(tǒng)是一個(gè)靈活的分布式系統(tǒng)，節(jié)點(diǎn)既是服務(wù)器也是客戶機(jī)，相互之間可以提供各種服務(wù)。然而傳統(tǒng)的P2P系統(tǒng)沒有設(shè)計(jì)有效的激勵(lì)機(jī)制，從而導(dǎo)致了搭便車和公地悲劇的發(fā)生。參考文獻(xiàn)[1]提出，在Gnutella中，70%的用戶從來不提供文件共享，而其中50%的文件查詢響應(yīng)來自1%的共享用戶。搭便車現(xiàn)象已經(jīng)嚴(yán)重影響了目前P2P系統(tǒng)的發(fā)展。目前已經(jīng)提出一些機(jī)制來抑制搭便車現(xiàn)象：(1)微支付機(jī)制，服務(wù)提供者從服務(wù)獲得者處收取一定的報(bào)酬，可以是現(xiàn)實(shí)貨幣，也可以是虛擬貨幣；(2)信譽(yù)機(jī)制，高信譽(yù)的節(jié)點(diǎn)可以獲得更好的服務(wù)質(zhì)量。然而從實(shí)際情況來看，微支付機(jī)制需要提供一個(gè)正規(guī)的經(jīng)濟(jì)模型，實(shí)際操作上相對(duì)比較困難，而基于信譽(yù)的激勵(lì)機(jī)制目前看來更有發(fā)展前景。本文以節(jié)點(diǎn)的信譽(yù)作為激勵(lì)節(jié)點(diǎn)行為的基礎(chǔ)，通過混合策略博弈的方法來激勵(lì)節(jié)點(diǎn)共享資源并提供服務(wù)。
1 相關(guān)工作
　對(duì)于存在自私節(jié)點(diǎn)的P2P系統(tǒng)，博弈論是一個(gè)理想的分析節(jié)點(diǎn)行為的工具。筆者模擬了一個(gè)無限重復(fù)博弈的P2P系統(tǒng)，并計(jì)算每一次博弈中所存在的納什均衡。
　假設(shè)網(wǎng)絡(luò)的生命周期是無限長的，并將其劃分成一個(gè)個(gè)小的時(shí)間段t，t=0,1，…,∞。在每一個(gè)時(shí)間段里，每個(gè)節(jié)點(diǎn)都收到一個(gè)服務(wù)請(qǐng)求，同時(shí)自己也發(fā)出服務(wù)請(qǐng)求。如果服務(wù)提供者同意提供服務(wù)，則請(qǐng)求將得到滿足。如果一個(gè)節(jié)點(diǎn)在一個(gè)時(shí)間段內(nèi)獲得了多次服務(wù)，則其收益為0。在實(shí)際應(yīng)用中，一些節(jié)點(diǎn)可能會(huì)同時(shí)收到一些服務(wù)請(qǐng)求，然而其中有些請(qǐng)求可能是來自信譽(yù)較低的節(jié)點(diǎn)，可以將其忽略。當(dāng)一個(gè)節(jié)點(diǎn)在時(shí)間段t內(nèi)響應(yīng)了一個(gè)服務(wù)請(qǐng)求，則其戰(zhàn)略為{響應(yīng)}。
　將節(jié)點(diǎn)間的交互模擬成一個(gè)無限重復(fù)博弈的模型。在每一個(gè)時(shí)間段t內(nèi)進(jìn)行一次博弈G，節(jié)點(diǎn)請(qǐng)求服務(wù)，同時(shí)決定是否響應(yīng)其他節(jié)點(diǎn)的請(qǐng)求服務(wù)。
   在此博弈中，參與者為P2P系統(tǒng)中所有的節(jié)點(diǎn)，而節(jié)點(diǎn)的戰(zhàn)略集為{響應(yīng)，不響應(yīng)}，節(jié)點(diǎn)的收益函數(shù)將在后面進(jìn)行定義。本文將無限重復(fù)的博弈G記為G′。
2 信譽(yù)模型

3 純戰(zhàn)略博弈
    下面分析無限重復(fù)博弈的納什均衡的可能性。由無名氏定理[2]可知：如果a’是博弈G的納什均衡的戰(zhàn)略集，那么當(dāng)G重復(fù)進(jìn)行無限次后，a’仍然是其納什均衡的戰(zhàn)略集。則求無限重復(fù)博弈G’的納什均衡可以簡化為求一次博弈G的納什均衡。
　首先討論純戰(zhàn)略博弈納什均衡的情況。當(dāng)所有的節(jié)點(diǎn)都選取戰(zhàn)略{不響應(yīng)}時(shí)，也是一個(gè)納什均衡的解，此時(shí)每個(gè)節(jié)點(diǎn)的收益都為0。當(dāng)某一節(jié)點(diǎn)i想改變戰(zhàn)略對(duì)服務(wù)請(qǐng)求進(jìn)行響應(yīng)時(shí)，其收益為-C，比不響應(yīng)時(shí)的收益降低了。因?yàn)楣?jié)點(diǎn)都是理性的，所以節(jié)點(diǎn)不會(huì)采取這種策略。另外戰(zhàn)略{不響應(yīng)}也是一種不理想的均衡，在P2P系統(tǒng)中，如果所有的節(jié)點(diǎn)都不提供服務(wù)，系統(tǒng)將無法運(yùn)行下去。所以這種均衡是無法達(dá)到的，而且在系統(tǒng)中總會(huì)有少數(shù)的利他主義節(jié)點(diǎn)存在。同樣如果所有節(jié)點(diǎn)都選擇{響應(yīng)}戰(zhàn)略，也不能達(dá)到納什均衡。很明顯，某一節(jié)點(diǎn)改變策略選擇{不響應(yīng)}的話，其收益明顯比選擇{響應(yīng)}高，因?yàn)樗饶茉诰W(wǎng)絡(luò)中獲得服務(wù)，同時(shí)也不會(huì)因提供服務(wù)而產(chǎn)生系統(tǒng)開銷。因此，在P2P系統(tǒng)中純戰(zhàn)略博弈是無法達(dá)到納什均衡的。
4 混合戰(zhàn)略博弈
　現(xiàn)在來分析混合戰(zhàn)略均衡的的可能性，在此，節(jié)點(diǎn)不再是確定的選擇某一戰(zhàn)略，而是以某一概率來選擇其戰(zhàn)略。

    參考文獻(xiàn)[2]給出了混合戰(zhàn)略博弈納什均衡的一個(gè)重要特點(diǎn)：在納什均衡中每個(gè)參與者的期望收益應(yīng)為其在符合正向概率時(shí)選擇任意策略時(shí)的期望收益。
    由這個(gè)混合策略納什均衡的特點(diǎn)可以得出：

   從式(5)可以看出，P不是一個(gè)定值。每一時(shí)間段的P是隨著上一次博弈結(jié)束后，節(jié)點(diǎn)的信譽(yù)值的變化而變化的。如果每一個(gè)節(jié)點(diǎn)都采取這種混合策略，那么對(duì)他們而言，該策略是最佳策略。本文認(rèn)為這個(gè)策略比都不提供服務(wù)的策略穩(wěn)定，因?yàn)槿绻疾惶峁┓?wù)，那么系統(tǒng)將失效。另外，在P2P系統(tǒng)中總會(huì)有少數(shù)的利他主義節(jié)點(diǎn)存在。所以，在該系統(tǒng)中不會(huì)有不合作的情況出現(xiàn)。
5 實(shí)驗(yàn)及結(jié)果分析
　仿真實(shí)驗(yàn)采用peersim仿真工具，該仿真工具是基于Java開發(fā)的，由很多組件構(gòu)成，適合于大規(guī)模的動(dòng)態(tài)的P2P網(wǎng)絡(luò)。在本實(shí)驗(yàn)中模擬了1 000個(gè)節(jié)點(diǎn)的P2P網(wǎng)絡(luò)，每個(gè)節(jié)點(diǎn)都采取混合策略博弈算法，在一段時(shí)間的重復(fù)博弈之后，從中隨機(jī)地取出了一些節(jié)點(diǎn)進(jìn)行觀察，發(fā)現(xiàn)他們的行為基本趨于一致。
   圖1是在納什均衡策略下節(jié)點(diǎn)可能的信譽(yù)變化的仿真結(jié)果。圖示表明,在節(jié)點(diǎn)信譽(yù)值增加的時(shí)間段表示節(jié)點(diǎn)響應(yīng)了其他節(jié)點(diǎn)的服務(wù)請(qǐng)求，而信譽(yù)值下降則表明節(jié)點(diǎn)拒絕了其他節(jié)點(diǎn)的服務(wù)請(qǐng)求?？梢钥闯?，經(jīng)過10個(gè)時(shí)間段后，混合策略納什均衡使得每個(gè)節(jié)點(diǎn)信譽(yù)值處于一個(gè)相差不大的水平，這說明節(jié)點(diǎn)都采取了該策略。在圖1中，筆者隨機(jī)地選取了3個(gè)節(jié)點(diǎn)，設(shè)定其初始信譽(yù)值分別為0.8、0.5和0.2，其中α=0.8，β=1，C/U=0.1。

　從仿真實(shí)驗(yàn)中隨機(jī)選取了一個(gè)節(jié)點(diǎn)，對(duì)其α的取值進(jìn)行了3次不同的實(shí)驗(yàn)。從圖2可以看出，節(jié)點(diǎn)的上傳和下載比在經(jīng)過一段時(shí)間后都幾乎達(dá)到了1，這說明節(jié)點(diǎn)響應(yīng)其他節(jié)點(diǎn)服務(wù)請(qǐng)求的次數(shù)和自己本身發(fā)出的得到響應(yīng)的服務(wù)請(qǐng)求次數(shù)基本相等，節(jié)點(diǎn)在獲得服務(wù)的同時(shí)也為他人提供了服務(wù)，有效地抑制了節(jié)點(diǎn)搭便車現(xiàn)象。而對(duì)于不同的α取值來看，α取值越大，節(jié)點(diǎn)的上傳和下載比趨近于1的速度越快。而從信譽(yù)模型來看，α取值越大在實(shí)際中也是比較合理的，這樣節(jié)點(diǎn)不能通過一次的服務(wù)提供來大幅度地提高節(jié)點(diǎn)的信譽(yù)度，而且節(jié)點(diǎn)也不會(huì)因?yàn)橐淮尉芙^響應(yīng)服務(wù)而大幅度降低信譽(yù)值。

    再來分析一下C/U對(duì)于響應(yīng)概率P的影響。前面已經(jīng)介紹了C是節(jié)點(diǎn)在響應(yīng)其他節(jié)點(diǎn)服務(wù)請(qǐng)求時(shí)所產(chǎn)生的系統(tǒng)開銷，例如在文件共享系統(tǒng)中網(wǎng)絡(luò)帶寬的消耗以及硬盤的磨損等等。U是節(jié)點(diǎn)獲得服務(wù)響應(yīng)后所得到的理論最大收益，但并不是實(shí)際收益。節(jié)點(diǎn)的實(shí)際收益還與其信譽(yù)值是掛鉤的。例如在文件共享系統(tǒng)中，節(jié)點(diǎn)下載一部電影獲得的理論最大收益為U，而節(jié)點(diǎn)當(dāng)前信譽(yù)值為R，則節(jié)點(diǎn)的實(shí)際收益為UR。也就是說節(jié)點(diǎn)的信譽(yù)值越高，節(jié)點(diǎn)所獲得的收益越大，比如可以獲得更好的下載帶寬以及較高的優(yōu)先級(jí)。從實(shí)際中來分析C/U肯定是一個(gè)較小的數(shù)值，因?yàn)镃要小于U在實(shí)際的系統(tǒng)中才比較合理。在仿真中取了幾個(gè)C/U的值進(jìn)行了實(shí)驗(yàn)。
　從圖3來看，C/U越大,節(jié)點(diǎn)響應(yīng)服務(wù)請(qǐng)求的概率也會(huì)增大，但是C/U如果太大的話，在實(shí)際應(yīng)用中又會(huì)降低系統(tǒng)的總體效率，因此C/U的取值應(yīng)該根據(jù)不同的系統(tǒng)應(yīng)用來設(shè)置，以求達(dá)到一個(gè)平衡。在實(shí)際應(yīng)用中，如果節(jié)點(diǎn)響應(yīng)服務(wù)請(qǐng)求的概率P的平均值能維持在50%左右的話，就基本上是滿意的。在圖3中α=0.8，β=1。

   針對(duì)目前P2P網(wǎng)絡(luò)中比較盛行的搭便車現(xiàn)象，本文引入了混合策略博弈的方法，有效地激勵(lì)了P2P網(wǎng)絡(luò)中的節(jié)點(diǎn)積極響應(yīng)其他節(jié)點(diǎn)的服務(wù)請(qǐng)求。通過仿真實(shí)驗(yàn)發(fā)現(xiàn)，該機(jī)制實(shí)現(xiàn)了抑制自私節(jié)點(diǎn)，鼓勵(lì)節(jié)點(diǎn)為系統(tǒng)多貢獻(xiàn)資源的目的。
參考文獻(xiàn)
[1]  ADAR E, HUBERMAN B, Free riding  on gnutella[J].  First Monday, 2000,5(10):42-68
[2]  OSBORNE M J. A course in game theory. Cambridge, Mass.: MIT Press, c1994.
[3]  NASH J F. Equilibrium points in N-person games, Proc. Natl. Acad. Sci. USA,1950,36:48-49.
[4]  BURAGOHAIN C, AGRAWAL D, SURI S. A game theoretic framework for incentives in P2P systems. In Proc. of the Third International Conference on Peer-to-Peer Computing(P2P’03), 2003.
[5]  GOLLE P. Incentives for sharing in peer-to-peer networks. In Proc. of 2001 ACM Conference on Electronic Commerce.