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

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

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

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

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

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

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

   針對目前P2P網(wǎng)絡(luò)中比較盛行的搭便車現(xiàn)象，本文引入了混合策略博弈的方法，有效地激勵了P2P網(wǎng)絡(luò)中的節(jié)點積極響應(yīng)其他節(jié)點的服務(wù)請求。通過仿真實驗發(fā)現(xiàn)，該機制實現(xiàn)了抑制自私節(jié)點，鼓勵節(jié)點為系統(tǒng)多貢獻資源的目的。
參考文獻
[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.