基于重復博弈的P2P網絡節點行為策略模型＊

王春枝 陳 莉 陳宏偉 周 可

（武漢理工大學計算機學院1） 武漢 430070） （湖北工業大學計算機學院2） 武漢 430068）

0 引 言

P2P（peer－to－peer）即對等計算或對等網絡，可以簡單地理解成通過計算機之間的直接交換來共享計算機資源和服務.P2P應用發展到了引人關注的程度，信任和安全問題也越來越值得關注.大多數節點對整個網絡的貢獻很少，只有少數節點支撐整個網絡資源，這種模式和傳統的C／S模式沒有多大區別，網絡中的用戶相互間缺乏信任，資源沒有得到充分使用.例如：在Napster，Gnutella［1］中，有66%的節點對整個系統沒有任何貢獻，10%的節點提供了87%的文件資源，20%的節點提供了98%的共享文件.這說明P2P網絡中存在大量的自私節點，容易出現以下問題：（1）搭便車（free－riding）問題［2］；（2）“公共物品的悲哀”（the tragedy of the commons）問題［3］；（3）不可靠服務和欺詐問題.所以提高網絡節點之間的信任和安全是非常必要的，這樣才能體現P2P網絡的優勢，最大化地利用資源優勢.

基于重復博弈［4－5］的P2P網絡節點行為策略模型的研究為設計更有效地激勵機制奠定了理論基礎.本文針對這些問題，深入分析節點類型的行為特征和重復博弈的特征，提出了一種基于重復博弈的P2P網絡節點行為策略模型，利用重復博弈的貼現率來分析博弈雙方采取何種策略才能使自己獲得最大收益，最后通過仿真實驗驗證了該博弈模型的可行性.

1 重復博弈

定義 設G是一個基本博弈，重復進行T次，T可以是有限的，也可以是無限的.這樣的博弈稱為重復博弈，并記為G（T）.G稱為G（T）的一個原博弈，每次博弈稱為一個階段博弈.當T是有限時稱為有限重復博弈，當T是無限時，稱為無限重復博弈.

在重復博弈G（T）中，在t階段局中人選取行動記為sit，sit∈Sit，則第t期行動組合記為st＝（s1t，s2t，…，snt），則第i個局中人在T期的總收益為

重復博弈中，局中人可根據先前雙方的博弈行為，決定自己下一階段要采取的策略.在博弈論上被稱為依存策略，依存策略又可看作為觸發策略（trigger strategies），2個有名的觸發策略：冷酷策略（grim strategy）和禮尚往來策略（tit for tat strategy）［6］.

2 P2P節點策略模型

根據網絡中節點的推薦信任值［7］，即：一些曾經和服務節點有過交互經驗的節點所給出的信任評價；還有我們自身對服務節點的信任，即自身和服務節點有過的歷史交互經驗所給出的評價.把P2P網絡中的節點分為：善意節點G（good node）和惡意節點B（bad node），各類型節點都有各自的行為策略集合.

2.1 善意節點策略模型

P2P網絡中善意節點的策略集合包括合作策略C（cooperation）和不合作策略N（non－cooperation），策略集S＝｛合作，不合作｝，記作｛C，N｝.合作策略是指其對所有鄰節點的服務請求或轉發請求都予以回應；不合作策略是指其不參與網絡中的響應，也就是所謂的退出網絡.表1顯示的是2個善意節點博弈的收益矩陣，其中α為2節點合作的收益，β為2節點合作時的支付.

表1 節點G間博弈的收益矩陣

若只進行一次博弈，有惟一的納什均衡點（合作，合作），其收益即均衡結果為（α－β，α－β）.若進行重復博弈，假設節點1先選擇“合作”行為，但當對方采取的是“不合作”行為后，節點1立即在下一期也選擇“不合作”行為，并永不改變.節點2也可以選擇和節點1同樣的策略.在此基礎上，分析節點是否愿意單獨違背自己的策略.

若節點1不改變自己的策略行為，則它的總收益，由式（1）得

當節點1在第t期改變策略時，節點2具有前期信息反饋，則在t＋1期，節點2也改變策略選擇“不合作”策略.節點1也能覺察節點2的選擇，因此在t＋1期，節點1也會選擇“不合作”策略.這樣節點1的總收益為

比較式（2）和（3）的大小.π1＞π′1，與下面表達式等價

因為δt－1＞0即當α＞β時，節點1不愿單獨改變自己的策略；同樣節點2也不愿意單獨改變自己的策略.在P2P網絡中，α＞β是一個網絡能夠維持的一個默認前提，所以當網絡中的節點都是善意節點時，節點之間選擇“合作”行為是一個均衡點.

2.2 惡意節點策略模型

P2P網絡中惡意節點的策略集合包括攻擊策略，共謀策略和搭便車策略.這里把惡意節點間博弈的策略也歸納為合作策略C和不合作策略N.其中，合作策略C包括惡意節點的共謀策略；不合作策略N包括搭便車策略.在P2P文件共享網絡中，攻擊策略是指惡意節點響應善意節點的服務請求并發送偽造文件或者病毒；共謀行為指的是當收到轉發請求時，惡意節點將請求轉發給其他惡意節點響應，還包括惡意節點間相互轉發對方惡意節點所需的文件；搭便車行為指惡意節點只向周圍節點發送服務請求來獲取服務，而對所有的服務請求和轉發請求都不予理睬.表2列出的是兩個惡意節點博弈的收益矩陣，其中i代表兩節點合作的收益，j代表兩節點合作時的支付，這里考慮i＞j.

表2 節點B間博弈的收益矩陣

若只進行一次博弈，有惟一的納什均衡點（合作，合作），其收益即均衡結果為（i－j，i－j）.若進行重復博弈，假設節點3選擇的策略是：先選擇“合作”行為，但當對方采取的是“不合作”行為后，節點3立即在下一期也選擇“不合作”行為，并永不改變.節點4也可以選擇和節點3同樣的策略.這種情況下，來分析節點是否愿意單獨違背自己的策略.

若節點3不改變自己的策略行為，則它的總收益，由式（1）得

當節點3在第t期改變策略時，節點4具有前期信息反饋，則在t＋1期，節點4也改變策略選擇“不合作”策略.節點3也能覺察節點4的選擇，因此在t＋1期，節點3也會選擇“不合作”策略.這樣節點3的總收益為

綜述之，根據節點的推薦信任值來大致分析節點的類型，當善意節點自身周圍的善意節點越多時，調整收支參數：α越大、β越小（α＞β），網絡中的節點更傾向于采取合作策略，那么P2P網絡就可以得到健康有序的發展，更加體現它對等網的優勢；當惡意節點自身周圍的惡意節點越多時，調整收支參數：i越小，j越大（i＞j），這時網絡中的惡意節點就更傾向于搭便車行為，這可以有效地減少P2P網絡中病毒和惡意軟件的傳播，減少共謀策略.這樣做可以控制不良情況的發生，從而找到合適方法發展健康的P2P網絡.

3 仿真結果分析

運用博弈分析軟件gambit來進行試驗仿真.設定兩個博弈參與者參加博弈，根據節點的收益、支出的參數變化來調整節點的策略.結合上面文章中提到的參數變化分析驗證模型的有效性，利用具有典型代表性的參數來驗證分析.

分析善意節點之間的博弈，不妨先設α＝4，β＝3，再把收益調整為α＝9，β＝1.由圖1和圖2可知，圖中上面一條曲線代表著兩個參與者都選擇合作策略，在α越大、β越小時，即收益調整后（圖2）所示，網絡中的節點更傾向于采取合作策略，而且愿意一直采取合作策略，從而保證了P2P網絡的健康發展.

圖1 善意節點博弈收益調整前變化

圖2 善意節點博弈收益調整后變化

圖3 惡意節點博弈收益調整前變化

圖4 惡意節點博弈收益調整后變化

分析惡意節點之間的博弈，不妨先設i＝9，j＝1，再把收益調整為i＝4，j＝3.由圖3和圖4可知，圖中上面一條曲線代表著兩個參與者都選擇不合作策略，即搭便車行為.在i越小，j越大（i＞j）時，網絡中的惡意節點就更傾向于搭便車行為，這可以有效地減少P2P網絡中病毒和惡意軟件的傳播，減少共謀策略.

4 結 論

本文針對P2P網絡中節點的類型不同和所采取的行為策略不同，進行了分類討論，分析了在何種情況下采取相應的策略能獲得較大的收益，并且結合重復博弈中的貼現率來討論在P2P網絡中節點之間的交互行為的短期和長期收益，以及節點策略調整的約束性條件.本文還用博弈論仿真工具gambit驗證了該模型.在今后的研究工作中，還需要深入研究P2P網絡中的節點類型未知情況下，節點所采取的策略組合博弈模型.

［1］Saroiu S，Gummadi K P，Gribble S D.Measuring and analyzing the characteristics of napster and gnutella hosts［J］.Multimedia Systems，2003，9（2）：170－184.

［2］Feldman M，Papadimitriou C，Chuang J.Free－riding and whitewashing in peer－to－peer systems［J］.IEEE Journal on Selected Areas in Communications，2006，24（5）：1010－1019.

［3］Tang Yangbin，Wang Huaimin，Dou Wen.Trust based incentive in P2Pnetwork［C］／／IEEE International Conference on E－Commerce Technology for Dynamic E－Business，2004：302－305.

［4］Feldman M，Lai K，Stoica L.Robust incentive techniques for peer－to－peer networks［C］／／The 5th ACM conference on Electronic commerce，2004，4：102－111.

［5］Xue Kaiping，Wang Qi，Hong Peilin.A conceptual incentive mechanism of P2Pfile sharing systems based on game theory［J］.Network and Parallel Computing Workshops，2007：77－82.

［6］Martin Nowak，Karl Sigmund.The evolution of stochastic strategies in the Prisoner＇s Dilemma［J］.Acta Applicandae Mathematicae，1990，20（3）：247－265.

［7］Sun Y L，Wei Yu，Zhu Han.Information theoretic framework of trust modeling and evaluation for ad hoc networks［J］.IEEE Journal，2006，24（2）：305－317.