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

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

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

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

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

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

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

   針對目前P2P網(wǎng)絡中比較盛行的搭便車現(xiàn)象，本文引入了混合策略博弈的方法，有效地激勵了P2P網(wǎng)絡中的節(jié)點積極響應其他節(jié)點的服務請求。通過仿真實驗發(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.