非結構化P2P網絡引導型進化博弈算法

朱國暉，魯春蘭，張瑞

(西安郵電大學通信與信息工程學院，陜西 西安 710061)

非結構化P2P網絡引導型進化博弈算法

朱國暉，魯春蘭，張瑞

(西安郵電大學通信與信息工程學院，陜西 西安 710061)

為促進動態開放性對等網絡中節點間的合作，在SLACER(selfish link-based adaptation for cooperation excluding rewiring，基于自私連接排除重構的自適應合作)算法的基礎上引入標兵節點，提出了引導型進化博弈算法G-SLACER(guided-SLACER)。通過初始化，網絡節點總數的30%為標兵節點;拓撲重構過程中，新增一條到最具優勢節點的引導型連接;為鼓勵節點相互學習，加大網絡整體收益。實驗結果表明，G-SLACER算法針對不同規模的網絡均具有良好的通用性，網絡中CCP(cooperative connected path，合作連接路徑)的穩定性增強。與其他進化博弈算法相比，G-SLACER算法形成的P2P網絡的合作狀態出現得更早、更平穩。

對等網絡;標兵節點;拓撲重構;引導型;P2P

1 引言

對等網絡由于自組織、低部署維護成本［1］，網絡中的節點行為自由，屬性自私。對等節點參與網絡活動時，注重個體利益忽略集體利益，如文件共享系統中的“free riding”現象。P2P網絡是一種分布式的動態網絡，隨著各對等節點的動態加入與退出，整個網絡的拓撲結構始終處于動態變化中［2］。

存在自私節點的對等網絡隨著時間的流逝，拓撲結構會逐漸出現分化現象，網絡性能越來越差，最后整個網絡趨于癱瘓。如何改變網絡節點的屬性，鼓勵節點積極參與網絡活動?SLAC(selfish link-based adaptation for cooperation，基于自私連接的自適應合作)算法通過每周期完全重構連接自適應地產生合作網絡，但容易在合作網絡中產生“部落”現象［3］。SLACER 算法中，節點通過參與 PD(prisoner's dilemma，囚徒困境)游戲獲取收益值，算法根據節點收益值進行有保留的隨機型拓撲重構，進而自適應地產生合作網絡［4，5］。為了激勵節點之間的協作，建立一種基于重復博弈理論和懲戒機制的P2P網絡信譽模型［6］，模擬仿真證實，該模型在促進節點間協作方面是有效的。參考文獻［7，8］基于進化博弈理論，評估了P2P文件共享系統在異構環境下的性能，討論了自私節點的不作為行為，仿真結果證實，文件共享系統使用頻率較低的文件的消失與自私節點的不作為有關系，異構環境有利于文件的可用性和系統的穩固性。基于博弈論的對等網絡節點自私性研究［9］中，提出了基于混合策略Bayes博弈的P2P文件共享機制，該機制可有效地抑制自私節點的行為，并使其更好地為其他節點提供服務。量化分析節點行為，提出共享型P2P節點策略(share strategy)［10］，在隨機 博弈矩陣的基礎上，調整參數引導P2P網絡向動態平衡的方向演化。

SLACER算法初始化所有節點為不合作節點，忽略了合作節點的引導作用;拓撲重構是隨機的，網絡中高水平合作狀態出現較慢;且缺少對不合作節點的激勵措施。針對這些不足，本文提出了G-SLACER算法。首先，初始化部分節點為合作節點，充當標兵，起引導作用，引導不合作節點轉化成合作節點，初始時網絡中的合作節點稱為標兵節點;其次，在拓撲重構過程中，新增一條到收益最高節點的引導型連接;再次，為了激勵節點之間的協作，加大對不合作節點的獎勵。

2 拓撲重構算法描述

SLACER算法是一種隨機進化算法，主要分為PD游戲過程和隨機型拓撲重構過程兩個階段。PD游戲中參與雙方有4種策略，每種策略對應不同的收益值。為了方便后面的討論，簡單介紹一下SLACER算法中的一些參數。

· 節點策略:對等網絡中的節點策略集S=｛合作，不合作｝。

·PD游戲收益矩陣:博弈雙方在游戲時采取不同的策略，獲取不同的收益值。任意 2個對等節點之間博弈的收益矩陣見表 1。

表1 博弈收益矩陣

· 合作節點比例:網絡中合作節點數目與網絡總節點數目的比值。

· CC(clustering coefficient，集聚系數):節點 i的鄰居節點之間實際的連接數與所有可能的連接數的比例。多個節點集聚系數的平均值稱為平均集聚系數。

· 節點收益值:節點通過參加PD游戲獲得的獎勵值。

·合作連接路徑(CCP):連通路徑上的連接節點對數與網絡中總節點對數的比值。連接節點對由信息傳輸路徑上的源節點和目的節點組成。

3 引導型拓撲重構算法描述

學習中有學習標兵，生活中有勞動模范，工作中有企業精英，這些都是本領域的突出角色，具有標榜引導作用。SLACER算法初始化網絡中的所有節點為不合作節點，忽視了合作節點的引導作用，雖然最后網絡中也出現了高水平的合作狀態，但高水平合作狀態出現的時延較大。

3.1 初始化標兵節點

本文先采用SLACER算法，初始化對等網絡中一部分節點為標兵節點。仿真中分別初始化2 000個總節點的0、10%、20%、30%、40%為標兵節點，實驗運行 100次，計算100個周期中網絡合作節點比例變化平均值，結果如圖1所示。

從圖1可以看出，當網絡中合作節點比例達到90%時，初始化標兵節點比例為網絡總數的0、10%、20%、30%、40%的模擬實驗，分別要到 90、70、60、50、60 個周期才能滿足要求。因此，當初始化網絡中標兵節點為網絡節點總數的30%時，標兵節點引導作用最強。

3.2 G-SLACER算法描述

G-SLACER算法在SLACER算法的基礎上引入了標兵節點，改進隨機型拓撲重構過程為引導型拓撲重構過程。下面簡單描述一下G-SLACER算法的執行過程。

(1)初始化網絡節點總數的30%為標兵節點，模擬周期數 N=0。

(2)節點i從自己的鄰居節點中隨機選擇一個節點進行PD游戲;如果節點i不存在鄰居節點，則從網絡中隨機選擇一個節點進行PD游戲。

(3)游戲結束，兩個節點分別獲取本次游戲的收益值。

(4)多次執行步驟(2)、步驟(3)，獲得節點i的平均收益(執行次數與當前節點的度數有關)。

(5)節點i進入引導型拓撲重構過程。

(6)N++;如果 N＜100，跳轉至步驟(2);如果 N=100，跳轉至步驟(7)。

(7)結束。

G-SLACER算法的引導型拓撲重構過程在SLACER算法的隨機型拓撲重構過程基礎上進行了4個方面的改進，兩種算法拓撲重構過程的比較見表2。其中，Lneighbors代表當前節點到鄰居節點的連接，Nmax代表收益值最大的節點，Nrand代表隨機選擇一個有收益值的節點，Vj代表節點j的平均收益值，假定本次模擬中節點i的收益小于節點j。

下面是G-SLACER算法中引導型拓撲重構過程實現的一段偽代碼。

其中，Ui代表節點 i的收益值，Uj代表節點j的收益值，Lnew代表當前節點新學習到的連接。

4 仿真結果及分析

4.1 仿真參數配置

PeerSim［11，12］是基于 Java 的 P2P 網絡仿真工具。本文模擬仿真采用 PeerSim中的Cycle-based模式［13］，具體參數設置如下:網絡節點數為2 000，模擬周期數N=100，重連概率W=0.9，策略改變概率M=0.001，連接改變概率MR=0.01，PD 游戲收益值 T=1.9，R=1，P=0，S=0。

仿真中設置3個控制器，控制器control.0監測網絡中合作節點比例、節點平均集聚系數、節點平均收益以及合作節點收益的變化趨勢;控制器control.1監測合作連通路徑的變化趨勢，每周期記錄一次數據;控制器control.2監測網絡節點平均度數的變化趨勢，每周期記錄一次數據。

4.2 仿真結果及分析

基于Bayes均衡博弈算法以及share strategy算法中網絡節點總數、博弈收益值、模擬周期數的配置與上述具體參數保持一致，參數配置完成，運行仿真軟件，分析3個控制器的輸出結果。

SLACER算法、G-SLACER算法、基于Bayes均衡博弈算法以及share strategy算法中合作節點比例對比如圖2所示。基于Bayes算法、share strategy算法分別設置網絡中標兵節點比例為70%和15%，運行100個周期，網絡中合作節點比例分別達75%和80%;SLACER算法初始化網絡節點全部為不合作節點，算法在第90個周期左右，網絡中合作節點比例為90%;G-SLACER算法初始化網絡中30%的節點為標兵節點，算法在第50個周期，網絡中合作節點比例為90%。算法執行100個周期，SLACER算法可以達到合作節點比例為98%的高水平合作網絡，而G-SLACER算法在70個周期左右就可以達到合作節點比例為98%的高水平合作網絡，且G-SLACER算法中合作節點比例的上升速度明顯高于其他兩種算法。G-SLACER算法在前10個周期，網絡中合作節點比例出現下滑趨勢。在算法初期，合作節點處于非合作節點的包圍中，合作節點的優勢還沒顯現出來，整個網絡中的節點信心不足，導致合作節點比例出現下滑，度過初期后，網絡中合作節點比例急速上升。G-SLACER算法的優勢主要歸因于算法在拓撲重構過程中引導型鏈接的選取。

表2 兩種算法拓撲重構過程的比較

圖2 4種算法合作節點比例對比

圖3 SLACER算法和G-SLACER算法平均集聚系數對比

SLACER算法和G-SLACER算法的平均集聚系數對比如圖3所示。SLACER算法的平均集聚系數保持在0.45左右，而G-SLACER算法的平均集聚系數保持在0.5左右。G-SLACER算法使得節點的鄰居節點之間的連接更加緊密，增強了網絡的穩定性。

SLACER算法和G-SLACER算法的節點平均收益和合作節點收益對比如圖4、圖5所示。SLACER算法的節點平均收益在80個周期后分布在1附近，G-SLACER算法的節點平均收益在40個周期后分布在1.4以上。G-SLACER算法受獎懲機制的啟發，加大了對收益較差節點的獎勵，鼓勵這些節點不斷學習以增加網絡整體收益;SLACER算法中合作節點收益在70個周期后分布在0.9左右，G-SLACER算法中合作節點收益在40個周期后分布在1.3左右。對比圖4和圖5，發現兩種算法的節點平均收益與合作節點收益的變化趨勢在整個模擬過程中大體保持一致。

圖4 SLACER算法和G-SLACER算法節點平均收益對比

圖5 SLACER算法和G-SLACER算法合作節點收益對比

圖6 SLACER算法和G-SLACER算法CCP對比

圖6是兩種算法的合作連接路徑對比。兩種算法的CCP值均收斂于1，前30個周期SLACER算法的CCP值波動較大，G-SLACER算法則波動較小。從圖5可以看出，前10個周期，兩種算法的CCP值均呈下滑趨勢，主要因為此時網絡處于合作初期，節點之間波動較大。總體來說，兩種算法都保持著穩定的CCP值，確保了網絡節點間路徑的連通性。高合作性網絡中可以存在不合作節點，只要不合作節點所在位置不影響連接路徑上其他節點的消息傳遞過程，CCP值就可以無限接近于1。

圖7是4種算法的節點平均度數對比。基于Bayes博弈網絡算法和share strategy算法考慮到P2P網絡存在“Small World”現象，節點度數分別設置為 3和7，且算法運行過程中，節點的度數均保持不變。另外兩種算法中，網絡中節點度的最大值設置為20，SLACER算法的節點平均度數為 13，G-SLACER算法的節點平均度數為14，度數增加1。G-SLACER算法中的引導型拓撲重構過程比SLACER算法多連接了一個具有高收益的節點，因此節點平均度數增加了1。度數增多，有利于節點之間的交流，促進節點相互學習。產生合作網絡初期，由G-SLACER與SLACER算法所構成的網絡中節點的度數不穩定，主要歸因于此時網絡動蕩較大，節點屬性不穩定。初期過后，兩種算法所形成的網絡中節點度數趨于穩態。

圖7 4種算法下節點平均度數變化情況

4.3 算法通用性

G-SLACER算法明顯促進了網絡高水平合作狀態的出現，改善了網絡性能參數，第4.2節的仿真是在2 000個節點的網絡上模擬的，為了驗證G-SLACER算法的通用性，分別在大小為4 000、8 000、16 000個節點的網絡上仿真標兵節點為30%時，網絡中合作節點比例的變化趨勢，結果如圖8所示。

圖8 G-SLACER算法在不同規模的網絡下合作節點比例變化趨勢

由圖8可以看出，雖然在構建合作網絡的初期，由于網絡節點間信任匱乏，而出現了短暫的合作節點比例下滑的情況，但不論網絡規模多大，模擬實驗中合作節點比例的變化趨勢幾乎是一致的。因此得出結論:G-SLACER算法適用于任意大小的網絡，通用性良好。

5 結束語

本文提出了一種引導型G-SLACER算法，引入標兵節點，優化拓撲重構過程，同時加大對收益較低節點的獎勵。仿真結果表明，G-SLACER算法促進了網絡節點之間的協作，增強了網絡連通性和穩定性。選取引導型連接時，僅考慮了收益最高的節點，下一步研究工作可從選取多樣化引導型連接入手，以達到快速形成高水平合作網絡的目的。

［1］張春紅，裘曉峰，弭偉，等.P2P技術全面解析［M］.北京:人民郵電出版社，2010:101-135.ZHANG C H，QIU X F，MI W，et al.Comprehensive Analysis of P2P Technology［M］.Beijing:Posts&Telecom Press，2010:101-135.

［2］管磊.P2P 技術揭秘［M］.北京:清華大學出社，2011:108-136.GUAN L.Reveal of P2P Technology ［M］.Beijing:Tsinghua University Press，2011:108-136.

［3］MARCOZZIA，HALESD，JESIG P，etal.Tag-based cooperation in peer-to-peer networks with newscast:technical Report UBLCS-2005-15:2015 ［S/OL］.［2015-11-20］.http://www.docin.com/p-875589728.html.

［4］HALES D，ARTECONI S.Friends for free:self-organizing artificial social networks for trust and cooperation:technical ReportUBLCS-2005-20:2005 ［S/OL］.［2015-11-20］.http://www.docin.com/p-972645743.html.

［5］HALES D，ARTECONI S.SLACER:a self-organizing protocol for coordination in peer-to-peer networks［J］.IEEE Intelligent Systems，2006，21(2):29-35.

［6］孟憲福，王動.基于重復博弈和懲戒機制的P2P協作激勵信譽模型 ［J］.計算機輔助設計與圖形學學報，2010，22(5):886-893.MENG X F，WANG D.Collaboration incenting reputation model based on repeated game theory and punishment mechanism in P2P networks［J］.Journal of Computer-Aided Design&Computer Graphics，2010，22(5):886-893.

［7］MATSUDA Y，SASABE M，TAKINE T.Evolutionary game theory-based evaluation of P2P file-sharing systems in heterogeneous environments［J］.International Journal of Digital Multimedia Broadcasting，2010(1):1-13.

［8］SASABE M，WAKAMIYA N，MURATA M.User selfishness vs file availability in P2P file-sharing systems:evolutionary game theoretic approach［J］.Peer-to-Peer Networking and Applications，2010，3(1):17-26.

［9］姚霖.基于博弈論的對等網絡節點自私性研究 ［D］.濟南:山東大學，2012:22-32.YAO L.The study on selfishness of nodes in P2P networks based on game theory ［D］. Jinan:Shandong University，2012:22-32.

［10］王楊，王汝傳，徐小龍，等.資源共享P2P網絡的進化博弈激勵模型［J］. 計算機工程，2011，37(11):19-21.WANG Y，WANG R C，XU X L，et al.Evolutionary game incentive model for resource sharing P2P network［J］.Computer Engineering，2011，37(11):19-21.

［11］PeerSim 中文教程 ［EB/OL］. ［2015-11-20］.http://wenku.baidu.com/view/83b35f104431b90d6c85c7ae.html.PeerSim Chinese course ［EB/OL］. ［2015-11-20］.http://wenku.baidu.com/view/83b35f104431b90d6c85c7ae.html.

［12］PeerSim overview ［EB/OL］. ［2015-11-20］.http://peersim.sourceforge.net/doc/index.html.

［13］JESI G P.PeerSim HOWTO:build a new protocol for the PeerSim 1.0 simulator ［EB/OL］.［2015-11-20］.http://peersim.sourceforge.net/tutorial1/tutorial1.html.

Guided evolutionary game algorithm of unstructured P2P network

ZHU Guohui，LU Chunlan，ZHANG Rui
School of Telecommunication and Information Engineering，Xi'an University of Posts&Telecommunications，Xi'an 710061，China

In order to promote the cooperation among the nodes which exist in dynamic and open peer-to-peer network，G-SLACER algorithm was provided by introducing pacesetter nodes.30%of network nodes were initialized to pacesetter nodes.In the process of topology reconstruction，a guided link to the most advantage node was added.To encourage studies between nodes，the payoff of the whole network was increased.The experimental results show that the G-SLACER algorithm has good generality for different sizes of networks，and it enhances the stability of CCP.Compared with other evolutionary game algorithms，cooperation state of P2P network formed by G-SLACER algorithm appears earlier and more stable.

peer-to-peer network，pacesetter node，topology reconstruction，guided，P2P

Education Department Foundation of Shaanxi Province(No.07JK377)

TP393

A

10.11959/j.issn.1000-0801.2016009

2015-07-22;

2015-12-15

陜西省教育廳科技計劃基金資助項目(No.07JK377)

朱國暉(1969-)，男，西安郵電大學副教授、碩士生導師，主要研究方向為對等網絡、移動互聯網、復雜網絡路由算法等。

魯春蘭(1989-)，女，西安郵電大學碩士生，主要研究方向為對等網絡、復雜網絡路由算法。

張瑞(1990-)，男，西安郵電大學碩士生，主要研究方向為對等網絡路由算法。