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

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

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

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

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

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

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

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