不同P2P網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)上進(jìn)化博弈算法的研究

魯春蘭

（西安航空職業(yè)技術(shù)學(xué)院電子工程學(xué)院，陜西西安710089）

Peer，中文意思為，伙伴，同事。由Peer組成的網(wǎng)絡(luò)被稱為對(duì)等網(wǎng)絡(luò)，即Peer-to-Peer network[1]。P2P網(wǎng)絡(luò)是建立在IP網(wǎng)絡(luò)之上的應(yīng)用層上的一種扁平化網(wǎng)絡(luò)，其憑借良好的可擴(kuò)展性、健壯性、通信匿名性、流量均衡、組網(wǎng)簡單靈活等優(yōu)勢(shì)，應(yīng)用極為廣泛。P2P網(wǎng)絡(luò)應(yīng)用極為廣泛，但仍然存在一些問題：“搭便車”現(xiàn)象[2]“洗白攻擊”[3]“公共悲劇”[4]。國內(nèi)外學(xué)者針對(duì)P2P網(wǎng)絡(luò)的缺點(diǎn)，提出不同的模型來提升P2P網(wǎng)絡(luò)中節(jié)點(diǎn)的合作性，比如：文獻(xiàn)[5]將博弈論的觀點(diǎn)引入對(duì)等網(wǎng)絡(luò)中，文獻(xiàn)[6]通過博弈論的方法研究了網(wǎng)絡(luò)中節(jié)點(diǎn)的自私性，文獻(xiàn)[7-9]研究了在不同激勵(lì)下建立信任模型，文獻(xiàn)[10]給P2P網(wǎng)絡(luò)中的節(jié)點(diǎn)賦予一定信譽(yù)，節(jié)點(diǎn)根據(jù)其自身信譽(yù)享受不同的合作服務(wù)水平，文獻(xiàn)[11-13]提出了在網(wǎng)格網(wǎng)絡(luò)以及無標(biāo)度網(wǎng)絡(luò)中，節(jié)點(diǎn)間更易于形成合作穩(wěn)態(tài)。

1 進(jìn)化博弈算法描述

網(wǎng)絡(luò)中的節(jié)點(diǎn)依次與自己的相鄰節(jié)點(diǎn)進(jìn)行囚徒困境博弈，博弈完成后，當(dāng)前節(jié)點(diǎn)從鄰居節(jié)點(diǎn)中選擇收益值最高的節(jié)點(diǎn)策略作為自己的策略，這是一種進(jìn)化型博弈模型。網(wǎng)絡(luò)通過節(jié)點(diǎn)之間的動(dòng)態(tài)演繹來激勵(lì)合作狀態(tài)的涌現(xiàn)。

文獻(xiàn)[14]中已經(jīng)證明網(wǎng)絡(luò)節(jié)點(diǎn)被賦予一定的身份認(rèn)證消息時(shí)，可以高效地遏制網(wǎng)絡(luò)中的“搭便車”行為，提高節(jié)點(diǎn)之間的合作性。該算法在P2P網(wǎng)絡(luò)里引入標(biāo)兵節(jié)點(diǎn)，引導(dǎo)網(wǎng)絡(luò)里的節(jié)點(diǎn)選擇合作策略，另外，節(jié)點(diǎn)主動(dòng)學(xué)習(xí)過程中根據(jù)收益差值選擇鄰居節(jié)點(diǎn)進(jìn)行連接。通過仿真軟件的仿真已經(jīng)證實(shí)了該算法的有效性和可靠性。

本文在文獻(xiàn)[14]的基礎(chǔ)上，將進(jìn)化博弈算法進(jìn)行了優(yōu)化，并在兩種不同的P2P網(wǎng)絡(luò)上進(jìn)行了仿真，仿真結(jié)果證明，在不同結(jié)構(gòu)的P2P網(wǎng)絡(luò)中采取不同學(xué)習(xí)策略，網(wǎng)絡(luò)中節(jié)點(diǎn)的合作性均有很大提高。

2 近似網(wǎng)格P2P網(wǎng)絡(luò)上的進(jìn)化博弈算法

為了抑制節(jié)點(diǎn)的自私性，Nowak等學(xué)者在網(wǎng)格網(wǎng)絡(luò)上運(yùn)用斑型圖對(duì)囚徒困境展開了分析，發(fā)現(xiàn)網(wǎng)格網(wǎng)絡(luò)里采取合作策略的節(jié)點(diǎn)在網(wǎng)絡(luò)博弈過程匯總成簇，越聚越大，最后網(wǎng)絡(luò)中會(huì)出現(xiàn)合作穩(wěn)態(tài)[15]。除了規(guī)則網(wǎng)格網(wǎng)絡(luò)外，還存在一種稀疏網(wǎng)格網(wǎng)絡(luò)。稀疏網(wǎng)格中有節(jié)點(diǎn)的缺失，缺失的節(jié)點(diǎn)位置可以一直保持空白，也可以連接到網(wǎng)絡(luò)中的其他節(jié)點(diǎn)上去。這樣的組網(wǎng)方式與P2P網(wǎng)絡(luò)形式十分類似，我們把這樣的稀疏網(wǎng)格網(wǎng)絡(luò)可以稱作近似網(wǎng)格P2P網(wǎng)絡(luò)。

本文的第一種進(jìn)化博弈算法將在近似網(wǎng)格P2P網(wǎng)絡(luò)上模擬，近似網(wǎng)格P2P網(wǎng)絡(luò)由于其組網(wǎng)方式具有一定的規(guī)則性，其策略更新形式采用的選擇最優(yōu)收益進(jìn)化式。

弱囚徒困境與經(jīng)典囚徒困境的區(qū)別在于收益矩陣參數(shù)設(shè)置的不同。從文獻(xiàn)[16]中可得出結(jié)論：弱囚徒困境與經(jīng)典囚徒困境的演化結(jié)論是一致的。弱囚徒困境參數(shù)設(shè)置如下：R=1,T=1+r,P=S=0。其中，R＜T=1+r＜2R即0＜r＜1。r稱為背叛誘惑因子。進(jìn)化博弈雙方的收益與收益矩陣有關(guān)，收益矩陣與背叛誘惑因子有關(guān)。因此，在計(jì)算節(jié)點(diǎn)收益，討論網(wǎng)絡(luò)中合作節(jié)點(diǎn)比例時(shí)必須從背叛誘惑因子入手。

3 改進(jìn)型隨機(jī)P2P網(wǎng)絡(luò)上進(jìn)化博弈算法

本文將構(gòu)造一個(gè)類似無標(biāo)度網(wǎng)絡(luò)的改進(jìn)型隨機(jī)P2P網(wǎng)絡(luò)，這個(gè)隨機(jī)P2P網(wǎng)絡(luò)也有優(yōu)先連接特性。雖然新構(gòu)造的改進(jìn)型隨機(jī)P2P網(wǎng)絡(luò)里每個(gè)節(jié)點(diǎn)擁有的相鄰節(jié)點(diǎn)數(shù)不一樣，但可以計(jì)算改進(jìn)型隨機(jī)P2P網(wǎng)絡(luò)里每一個(gè)節(jié)點(diǎn)的平均相鄰的節(jié)點(diǎn)數(shù)，這個(gè)計(jì)算值是個(gè)固定的值。

改進(jìn)型隨機(jī)P2P網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)代表一個(gè)參與博弈的博弈者，節(jié)點(diǎn)之間的連線代表博弈者之間的信息交互。兩個(gè)節(jié)點(diǎn)相互博弈，博弈活動(dòng)完成后計(jì)算本次博弈的收益值。接著進(jìn)行節(jié)點(diǎn)策略的更新，節(jié)點(diǎn)依次選擇鄰居節(jié)點(diǎn)計(jì)算策略轉(zhuǎn)移概率p，接著系統(tǒng)產(chǎn)生一個(gè)隨機(jī)數(shù)，如果該隨機(jī)數(shù)的值小于策略轉(zhuǎn)移概率p，則節(jié)點(diǎn)會(huì)將自己的策略更新為相鄰節(jié)點(diǎn)的策略，策略更新過程完成。

改進(jìn)型隨機(jī)P2P網(wǎng)絡(luò)由于其組網(wǎng)方式的隨機(jī)性，為了平衡組網(wǎng)方式的隨機(jī)性，在策略更新階段采取了策略轉(zhuǎn)移概率的更新方式。

策略轉(zhuǎn)移概率p的計(jì)算公式如下：

其中，Si，Sj分別表示節(jié)點(diǎn)i與節(jié)點(diǎn)j的策略，i表示當(dāng)前節(jié)點(diǎn)，j表示相鄰節(jié)點(diǎn)。

4 仿真結(jié)果及分析

4.1 近似網(wǎng)格P2P網(wǎng)絡(luò)上的進(jìn)化博弈算法參數(shù)配置

仿真實(shí)驗(yàn)是在N*N=200*200的稀疏網(wǎng)格網(wǎng)絡(luò)上完成的。初始化網(wǎng)絡(luò)中的合作節(jié)點(diǎn)為30%，不合作節(jié)點(diǎn)為70%，進(jìn)化博弈算法運(yùn)行100個(gè)周期。背叛誘惑因子的取值區(qū)間為0＜r＜1。

4.2 近似網(wǎng)格P2P網(wǎng)絡(luò)上的進(jìn)化博弈算法數(shù)據(jù)分析

實(shí)驗(yàn)中，令背叛因子的取值分別為r=0.05，0.25，0.45，0.65，0.85，討論不同背叛因子對(duì)網(wǎng)絡(luò)合作演化的作用。

圖1中（a）～（e）圖，分別表示的是當(dāng)背叛因子r=0.05，0.25，0.45，0.65，0.85時(shí)，網(wǎng)絡(luò)中合作節(jié)點(diǎn)與不合作節(jié)點(diǎn)的變化趨勢(shì)。對(duì)比可知，r=0.85不適合充當(dāng)背叛誘惑因子。

下面主要研究在近似網(wǎng)格P2P網(wǎng)絡(luò)中，背叛誘惑因子的上限值。首先適當(dāng)?shù)販p小背叛誘惑因子r的取值，定義r=0.8。圖2表示背叛誘惑因子r=0.8時(shí)，合作節(jié)點(diǎn)與不合作節(jié)點(diǎn)所占比例變化趨勢(shì)。從圖中可以看出，不合作節(jié)點(diǎn)所占比例一直高于合作節(jié)點(diǎn)所占比例，網(wǎng)絡(luò)在達(dá)到穩(wěn)態(tài)之后，一直不會(huì)出現(xiàn)合作狀態(tài)。因此，r=0.8不是所求背叛誘惑因子的上限。

實(shí)驗(yàn)中，又分別取了r=0.75，0.77，0.79來估算背叛誘惑因子的上限。圖3、圖4、圖5分別表示r=0.75，0.77，0.79時(shí)，偏向合作態(tài)度的節(jié)點(diǎn)與選擇不合作態(tài)度的節(jié)點(diǎn)所占比例變化趨勢(shì)以及模擬過程中的動(dòng)態(tài)演化過程圖。

圖1 不同背叛誘惑因子下，合作節(jié)點(diǎn)與不合作節(jié)點(diǎn)所占比例變化趨勢(shì)

圖2 背叛誘惑因子r=0.8時(shí)，合作節(jié)點(diǎn)與不合作節(jié)點(diǎn)所占比例變化趨勢(shì)

對(duì)比這3組圖，我們對(duì)出現(xiàn)合作穩(wěn)態(tài)最快的圖5進(jìn)行分析。當(dāng)背叛誘惑因子r=0.79時(shí)，從圖5中（a）可以看出，模擬進(jìn)行到第70周期時(shí)，網(wǎng)絡(luò)就已經(jīng)進(jìn)入合作的穩(wěn)定狀態(tài)。網(wǎng)絡(luò)在T0=42時(shí)，網(wǎng)絡(luò)里有數(shù)量相等的兩種節(jié)點(diǎn)。T=3時(shí)，合作節(jié)點(diǎn)處于變化曲線的波谷，對(duì)比動(dòng)態(tài)演變過程，可以看到此時(shí)網(wǎng)絡(luò)中不合作節(jié)點(diǎn)處于統(tǒng)治地位，隨著模擬的不斷進(jìn)行，網(wǎng)絡(luò)中出現(xiàn)了大量的合作節(jié)點(diǎn)形成的合作簇，逐漸擴(kuò)展到不合作節(jié)點(diǎn)區(qū)域，最后整個(gè)網(wǎng)絡(luò)處于合作穩(wěn)定狀態(tài)。

本文前面，通過模擬實(shí)驗(yàn)已經(jīng)得出：背叛誘惑因子r=0.8不是所求背叛誘惑因子的上限。而當(dāng)背叛誘惑因子r=0.79時(shí)，網(wǎng)絡(luò)處于穩(wěn)定的合作狀態(tài)。因此，定性分析背叛誘惑因子r=0.79是背叛誘惑因子的上限。背叛誘惑因子的取值范圍0＜r＜0.79。當(dāng)背叛誘惑因子的值在本文所求解的取值范圍內(nèi)，近似網(wǎng)格P2P網(wǎng)絡(luò)中就可以出現(xiàn)合作穩(wěn)態(tài)。模擬證明，在近似網(wǎng)格P2P網(wǎng)絡(luò)中采取策略更新?lián)褡顑?yōu)收益進(jìn)化博弈算法可以使得網(wǎng)絡(luò)中出現(xiàn)合作穩(wěn)態(tài)。

圖3 當(dāng)背叛誘惑因子r=0.75時(shí)，圖（a）表示合作節(jié)點(diǎn)與不合作節(jié)點(diǎn)所占比例變化趨勢(shì)。圖（b）～（f）分別表示的是模擬周期[T]為0、5、30、60、100時(shí)的動(dòng)態(tài)演化過程。其中淺色表示不合作節(jié)點(diǎn)，深色表示合作節(jié)點(diǎn)。

圖4 當(dāng)背叛誘惑因子r=0.77時(shí)，圖（a）表示合作節(jié)點(diǎn)與不合作節(jié)點(diǎn)所占比例變化趨勢(shì)。圖（b）～（d）分別表示的是模擬周期T為3、50、100時(shí)的動(dòng)態(tài)演化過程。其中淺色表示不合作節(jié)點(diǎn)，深色表示合作節(jié)點(diǎn)。

4.3 改進(jìn)型隨機(jī)P2P網(wǎng)絡(luò)上進(jìn)化博弈算法的研究

模擬實(shí)驗(yàn)運(yùn)行的環(huán)境為改進(jìn)型隨機(jī)P2P網(wǎng)絡(luò)，為了體現(xiàn)對(duì)節(jié)點(diǎn)策略的公平性，并促使網(wǎng)絡(luò)中快速出現(xiàn)合作穩(wěn)態(tài)，以下的實(shí)驗(yàn)將在初始合作節(jié)點(diǎn)為50%的環(huán)境中進(jìn)行。

當(dāng)設(shè)置背叛誘惑因子r的值為0.06時(shí)，網(wǎng)絡(luò)中并未出現(xiàn)合作穩(wěn)態(tài)。重新設(shè)置背叛誘惑因子的值，分別設(shè)置為0.99和0.1，初始化網(wǎng)絡(luò)中合作節(jié)點(diǎn)為50%。實(shí)驗(yàn)運(yùn)行100周期，結(jié)果如圖6所示。

圖5 當(dāng)背叛誘惑因子r=0.79時(shí)，圖（a）表示合作節(jié)點(diǎn)與不合作節(jié)點(diǎn)所占比例變化趨勢(shì)。圖（b）～（f）分別表示的是模擬周期T為3、50、70、80、100時(shí)的動(dòng)態(tài)演化過程。其中淺色表示不合作節(jié)點(diǎn)，深色表示合作節(jié)點(diǎn)。

圖6 初始化網(wǎng)絡(luò)中合作節(jié)點(diǎn)為50%，圖（a）是背叛誘惑因子r=0.99時(shí)，兩種節(jié)點(diǎn)所占比例變化趨勢(shì)，圖（b）是背叛誘惑因子r=0.1時(shí)，兩種節(jié)點(diǎn)所占比例變化趨勢(shì)圖。

當(dāng)背叛誘惑因子為0.99和0.1時(shí)，模擬運(yùn)行結(jié)束時(shí)兩種狀態(tài)的網(wǎng)絡(luò)均達(dá)到了合作穩(wěn)態(tài)。誘惑因子為0.99時(shí)，實(shí)驗(yàn)運(yùn)行到第5周期網(wǎng)絡(luò)已經(jīng)達(dá)到了合作穩(wěn)態(tài)，而r=0.1時(shí)的合作穩(wěn)態(tài)則出現(xiàn)的稍微晚些，但也在第30周期出現(xiàn)合作穩(wěn)態(tài)。由此可見，在隨機(jī)P2P網(wǎng)絡(luò)中，背叛誘惑因子越大，網(wǎng)絡(luò)中出現(xiàn)合作穩(wěn)態(tài)時(shí)間越短，網(wǎng)絡(luò)越穩(wěn)定。

接著，實(shí)驗(yàn)對(duì)背叛誘惑因子分別取值為0.07，0.065，0.063和0.061，模擬運(yùn)行100周期，結(jié)果如圖7所示。

由圖7可以看出，這4種不同大小的背叛誘惑因子下，合作節(jié)點(diǎn)所占比例逐漸增長，網(wǎng)絡(luò)中出現(xiàn)合作穩(wěn)態(tài)。隨著背叛誘惑因子的不斷減小，合作穩(wěn)態(tài)的穩(wěn)固程度也依次減弱。

由于改進(jìn)型隨機(jī)P2P網(wǎng)絡(luò)是一種完全隨機(jī)的網(wǎng)絡(luò)，節(jié)點(diǎn)之間博弈算法使用的收益矩陣是一種弱博弈矩陣，并且節(jié)點(diǎn)更新策略使用的是一種動(dòng)態(tài)轉(zhuǎn)移概率策略，該概率中加入了非理性選擇的噪聲，背叛誘惑因子越小，競(jìng)爭因素相對(duì)也就越少，因此，這種網(wǎng)絡(luò)情況下，網(wǎng)絡(luò)中的合作穩(wěn)態(tài)出現(xiàn)的較晚。相反，背叛誘惑因子越大，節(jié)點(diǎn)之間的競(jìng)爭越激烈，節(jié)點(diǎn)更愿意選擇合作策略，提高了網(wǎng)絡(luò)中節(jié)點(diǎn)的整體收益，良好的整體收益更深入地促進(jìn)了網(wǎng)絡(luò)中合作穩(wěn)態(tài)的出現(xiàn)。結(jié)合實(shí)驗(yàn)數(shù)據(jù)，得出背叛誘惑因子的取值范圍為0.06＜r＜1時(shí)，改進(jìn)型隨機(jī)P2P網(wǎng)絡(luò)中會(huì)出現(xiàn)合作穩(wěn)態(tài)，并且背叛誘惑因子越大，合作穩(wěn)態(tài)出現(xiàn)的越早越牢固。

圖7 圖（a）～（d）分別是背叛誘惑因子為0.07，0.065，0.063，0.061時(shí)，網(wǎng)絡(luò)中兩種節(jié)點(diǎn)所占比例變化趨勢(shì)

5 結(jié)束語

為了促進(jìn)P2P網(wǎng)絡(luò)中節(jié)點(diǎn)的合作性，本文分別在近似網(wǎng)格P2P網(wǎng)絡(luò)中模擬了選擇最優(yōu)策略的進(jìn)化博弈算法、在改進(jìn)型P2P網(wǎng)絡(luò)中模擬了選擇概率轉(zhuǎn)移策略的進(jìn)化博弈算法。仿真結(jié)果證明，在這兩種不同的拓?fù)浣Y(jié)構(gòu)中進(jìn)化博弈算法均能促進(jìn)網(wǎng)絡(luò)中合作穩(wěn)態(tài)的出現(xiàn)。