基于重復博弈的P2P網(wǎng)絡節(jié)點行為策略模型＊

王春枝 陳 莉 陳宏偉 周 可

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

0 引 言

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

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

1 重復博弈

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

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

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

2 P2P節(jié)點策略模型

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

2.1 善意節(jié)點策略模型

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

表1 節(jié)點G間博弈的收益矩陣

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

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

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

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

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

2.2 惡意節(jié)點策略模型

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

表2 節(jié)點B間博弈的收益矩陣

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

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

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

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

3 仿真結(jié)果分析

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

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

圖1 善意節(jié)點博弈收益調(diào)整前變化

圖2 善意節(jié)點博弈收益調(diào)整后變化

圖3 惡意節(jié)點博弈收益調(diào)整前變化

圖4 惡意節(jié)點博弈收益調(diào)整后變化

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

4 結(jié) 論

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

［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.