基于演化博弈的P2P系統(tǒng)中Node合作機(jī)制研究與設(shè)計(jì)

摘 要：P2P是一種點(diǎn)對(duì)點(diǎn)的共享機(jī)制，針對(duì)P2P在網(wǎng)絡(luò)文件共享中由于占用帶寬問題，網(wǎng)絡(luò)上傳問題影響網(wǎng)速問題，引入經(jīng)濟(jì)學(xué)的博弈論，來提高P2P網(wǎng)絡(luò)的性能，以及如何能充分利用P2P節(jié)點(diǎn)的資源，讓網(wǎng)絡(luò)中的資源尋找更加流暢，提高網(wǎng)絡(luò)共享的效率是我們目前要解決的問題。

關(guān)鍵詞：P2P網(wǎng)絡(luò)；混合戰(zhàn)略博弈；演化博弈；合作機(jī)制

中圖分類號(hào)：TP393.02

P2P是一個(gè)點(diǎn)對(duì)點(diǎn)系統(tǒng)，從當(dāng)初一對(duì)一發(fā)展到今天的一對(duì)多，多對(duì)多等等，節(jié)點(diǎn)是服務(wù)器，但是如果網(wǎng)絡(luò)上別人的客戶端有資源的話也可以下載，進(jìn)行寬帶傳輸。據(jù)統(tǒng)計(jì)在Gnutella系統(tǒng)網(wǎng)絡(luò)統(tǒng)計(jì)中，70%的用戶從來不提供文件共享，而服務(wù)器資源占到大多數(shù)一旦下載的人數(shù)過多那么就對(duì)速度有影響。應(yīng)該P(yáng)2P網(wǎng)絡(luò)的性能。而基于信譽(yù)的激勵(lì)機(jī)制目前看來更有發(fā)展前景。本文基于經(jīng)濟(jì)學(xué)中的博弈論機(jī)制提出一種演化博弈機(jī)制來促進(jìn)P2P網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行合作，大大地提高了節(jié)點(diǎn)的積極性，也提高P2P文件共享系統(tǒng)的總體效率。

1 演化博弈模型與演化重連的提出

在分布式P2P應(yīng)用系統(tǒng)中，需要通過節(jié)點(diǎn)之間的合作來提高系統(tǒng)的效率。例如，在文件共享系統(tǒng)中，節(jié)點(diǎn)要主動(dòng)上傳自己的資源供他人使用。但是在開放的系統(tǒng)中，節(jié)點(diǎn)都是自私的，他們都希望節(jié)約自己的帶寬和存儲(chǔ)空間而使用別人的資源。那么在高度自治的P2P系統(tǒng)中，自然就產(chǎn)生了一個(gè)雪堆博弈的問題。

在經(jīng)濟(jì)學(xué)中，“雪堆”博弈又稱為“鷹鴿”博弈或者“小雞”博弈（Chicken Game），是一種兩人對(duì)稱博弈模型，描述了兩個(gè)人相遇時(shí)是彼此合作共同受益，還是彼此欺騙來相互報(bào)復(fù)，該模型揭示了個(gè)體理性和群體理性的矛盾對(duì)立。

為了提高Node的積極性，本研究采用多次連接機(jī)制來測(cè)試P2P中的節(jié)點(diǎn)聯(lián)系能力。通過Gnutella協(xié)議搜尋網(wǎng)絡(luò)中的其他節(jié)點(diǎn)，已測(cè)試節(jié)點(diǎn)的互通性和帶寬使用情況。假設(shè)每一次通過Gnutella協(xié)議都可以搜尋到網(wǎng)上的咨詢，而且通過雪堆博弈來考慮的起的經(jīng)濟(jì)效率，從而得出系統(tǒng)的性能和使用效率。

在網(wǎng)絡(luò)中，P2P最大化的搜尋節(jié)點(diǎn)，通常在系統(tǒng)中都對(duì)P2P搜尋節(jié)點(diǎn)作出限制，比如著名的P2P工具迅雷就對(duì)會(huì)員客戶和非會(huì)員客戶能搜到的節(jié)點(diǎn)數(shù)不一樣，如果搜尋到的節(jié)點(diǎn)有你想到的資源，那么就下載。

在一個(gè)大規(guī)模網(wǎng)絡(luò)系統(tǒng)中，P2P首先搜索節(jié)點(diǎn)，經(jīng)過一段時(shí)間，對(duì)于節(jié)點(diǎn)進(jìn)行計(jì)算，刪除一些沒有資源或者低資源的節(jié)點(diǎn)，使得P2P下載資源的網(wǎng)絡(luò)資源能最大的利用。

該演化重連機(jī)制將分三個(gè)階段進(jìn)行。

階段0：初始化網(wǎng)絡(luò)路由。

階段1：在網(wǎng)絡(luò)中搜索與資源的節(jié)點(diǎn)。

階段2：從網(wǎng)絡(luò)中隨機(jī)的選擇兩個(gè)節(jié)點(diǎn)比較它們之間的收益。

在仿真實(shí)驗(yàn)中，該算法計(jì)算網(wǎng)絡(luò)中的節(jié)點(diǎn)資源情況，從而刪除低資源節(jié)點(diǎn)或者已經(jīng)沒有資源的節(jié)點(diǎn)，從而高效率的利用網(wǎng)絡(luò)上面的資源，并且進(jìn)行資源計(jì)算，防止對(duì)于硬件的使用情況，而導(dǎo)致電腦死機(jī)。

2 博弈機(jī)制的具體設(shè)計(jì)

在peersimP2P軟件上，目前有2種模式，采用cycle-based和event-driven模擬方式。event-driven支持傳輸層協(xié)議可以對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行控制和效益計(jì)算，而cycle-based可以缺少對(duì)于傳輸層的支持，不能起到控制作用，但是資源占用少，在統(tǒng)一硬件環(huán)境下面，cycle-based搜尋到的節(jié)點(diǎn)更多。

EGProtocol實(shí)現(xiàn)了peersim中的CDProtocol接口，他定義了節(jié)點(diǎn)在每一輪循環(huán)中所執(zhí)行的動(dòng)作。這些操作在nextCycle（）方法中實(shí)現(xiàn)。

NextCycle（）方法包含兩個(gè)參數(shù)：node和protocolID，其中node是第一個(gè)參數(shù)。在仿真的三個(gè)階段中，每一個(gè)階段都將用到該參數(shù)。在初始化階段，網(wǎng)絡(luò)開始搜尋有資源的節(jié)點(diǎn)，代碼如下：利用NextCycle（）方法中的兩個(gè)參數(shù)開始加載：

1 Linkable linkable=（Linkable） node.getProtocol（lpid）；

2 for（int i=0；i

3 {

4 this.nList.add（linkable.getNeighbor（i））；

5 }

其中第一行的參數(shù)“l(fā)pid”是協(xié)議標(biāo)示符，他是取自運(yùn)行的節(jié)點(diǎn)；lpid指的是Newcast協(xié)議，而protocolID指的是EGProtocol協(xié)議。

一個(gè)節(jié)點(diǎn)可以看成是一個(gè)協(xié)議容器，通過協(xié)議標(biāo)示符，例如lpid或者protocolID，可以獲得協(xié)議容器中的內(nèi)容。利用函數(shù)getProtocol（lpid），我們可以從一個(gè)節(jié)點(diǎn)中獲得指定協(xié)議的所有數(shù)據(jù)內(nèi)容。

在進(jìn)行節(jié)點(diǎn)控制中我們要注意節(jié)點(diǎn)資源情況，將已經(jīng)利用完的節(jié)點(diǎn)資源刪除，一般找尋新的節(jié)點(diǎn)，并且對(duì)于P2P系統(tǒng)中的節(jié)點(diǎn)最大化連接作出合理計(jì)算，防止資源利用率過大，而導(dǎo)致電腦死機(jī)，并利用算法對(duì)于節(jié)點(diǎn)資源效益作出計(jì)算，event-driven支持傳輸層協(xié)議?？梢詫?duì)網(wǎng)絡(luò)傳輸進(jìn)行控制。

我們現(xiàn)在來分析當(dāng)節(jié)點(diǎn)i的收益高于節(jié)點(diǎn)j的收益的情況：

（1）i對(duì)于節(jié)點(diǎn)進(jìn)行收益計(jì)算；

（2）i將低于收益的節(jié)點(diǎn)刪除；

（3）將搜尋高收益的節(jié)點(diǎn)；

（4）將節(jié)點(diǎn)加入i路由表；

（5）j采用斷開策略；

（6）將節(jié)點(diǎn)加入i的路由表格；

（7）節(jié)點(diǎn)將以一個(gè)很小的概率發(fā)生策略的變異。

計(jì)算網(wǎng)絡(luò)路由表的資源情況，如果發(fā)現(xiàn)搜尋到節(jié)點(diǎn)沒有資源將斷開，利用傳輸層協(xié)議對(duì)于節(jié)點(diǎn)進(jìn)行控制，而從爭(zhēng)取網(wǎng)絡(luò)資源下載最大利益化。

如果發(fā)現(xiàn)節(jié)點(diǎn)服務(wù)器或者客戶端在網(wǎng)絡(luò)中斷開或者關(guān)閉，將斷開該節(jié)點(diǎn)，搜索另外的新節(jié)點(diǎn)，以便繼續(xù)下載咨詢，利用傳輸層協(xié)議，控制整個(gè)網(wǎng)絡(luò)中的節(jié)點(diǎn)斷開與連接。

3 實(shí)驗(yàn)結(jié)果及分析

在上千次次演化過程中，不同的網(wǎng)絡(luò)節(jié)點(diǎn)通過Gnutella協(xié)議通過在網(wǎng)上多次搜尋自語來測(cè)試網(wǎng)絡(luò)節(jié)點(diǎn)的互通性已經(jīng)帶寬使用情況。對(duì)不同網(wǎng)絡(luò)的文件，采取了不用的種子文件下載，這樣可以搜尋到網(wǎng)絡(luò)中的節(jié)點(diǎn)，以檢測(cè)節(jié)點(diǎn)之間的聯(lián)系情況。實(shí)驗(yàn)表明在初次Gnutella協(xié)議探尋時(shí)網(wǎng)絡(luò)的節(jié)點(diǎn)較多，之后不斷的增多，從而可以得出問題網(wǎng)絡(luò)節(jié)點(diǎn)之間的合作性。網(wǎng)絡(luò)P2P在線的下載工具有迅雷，電驢，快播等等，目前這些軟件后臺(tái)上傳率比較厲害，有時(shí)候會(huì)影響客戶端帶寬使用情況，從而導(dǎo)致客戶的下載出現(xiàn)問題，但是如果客戶禁用節(jié)點(diǎn)資源共享，那么又會(huì)影響P2P的性能以及效率這是個(gè)矛盾的問題也是P2P今后需要改進(jìn)的地方。

實(shí)驗(yàn)表明：在網(wǎng)絡(luò)Gnutella搜尋資源的時(shí)候，初始化節(jié)點(diǎn)較少，但是后來搜尋到的節(jié)點(diǎn)不斷增多，網(wǎng)絡(luò)節(jié)點(diǎn)區(qū)域穩(wěn)定。從而資源貢獻(xiàn)下載變得穩(wěn)定，效率增高。

參考文獻(xiàn)：

[1]M.Feldman，K.Lai，I.Stoica，et.al.Robust Incentive Techniques for Peer-to-Peer Networks[A].Presented at Proc.of the 5th ACM conference on Electronic Commerce[C]，New York，2004：102-111.

[2]Cohen E，Shenker s.Replication strategies in unstructured peer-to-peer networks[C].Proceedings of ACM SIGCOMM’02，Aug 2002.

作者單位：郴州市教育招生考試院，湖南郴州 423000