朱国晖，鲁春兰，张瑞

(西安邮电大学通信与信息工程学院，陕西 西安 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-)，男，西安邮电大学硕士生，主要研究方向为对等网络路由算法。