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

魯春蘭

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

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

1 進化博弈算法描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本文前面，通過模擬實驗已經(jīng)得出：背叛誘惑因子r=0.8不是所求背叛誘惑因子的上限。而當(dāng)背叛誘惑因子r=0.79時，網(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)收益進化博弈算法可以使得網(wǎng)絡(luò)中出現(xiàn)合作穩(wěn)態(tài)。

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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