作者：张毅
1 引言
对等网络由于自组织、低部署维护成本，网络中的节点行为自由，属性自私。对等节点参与网络活动时，注重个体利益忽略集体利益，如文件共享系统中的“free riding”现象。P2P网络是一种分布式的动态网络，随着各对等节点的动态加入与退出，整个网络的拓扑结构始终处于动态变化中。
存在自私节点的对等网络随着时间的流逝，拓扑结构会逐渐出现分化现象，网络性能越来越差，最后整个网络趋于瘫痪。如何改变网络节点的属性，鼓励节点积极参与网络活动？SLAC(selfish link-based adaptation for cooperation,基于自私连接的自适应合作)算法通过每周期完全重构连接自适应地产生合作网络，但容易在合作网络中产生“部落”现象。SLACER算法中，节点通过参与PD (prisoner's dilemma，囚徒困境)游戏获取收益值，算法根据节点收益值进行有保留的随机型拓扑重构，进而自适应地产生合作网络。为了激励节点之间的协作，建立一种基于重复博弈理论和惩戒机制的P2P网络信誉模型，模拟仿真证实，该模型在促进节点间协作方面是有效的。基于进化博弈理论，评估了P2P文件共享系统在异构环境下的
性能，讨论了自私节点的不作为行为，仿真结果证实，文件共享系统使用频率较低的文件的消失与自私节点的不作为有关系，异构环境有利于文件的可用性和系统的稳固性。基于博弈论的对等网络节点自私性研究，提出了基于混合策略Bayes博弈的P2P文件共享机制，该机制可有效地抑制自私节点的行为，并使其更好地为其他节点提供服务。量化分析节点行为，提出共享型P2P节点策略( share strategy)，在随机博弈矩阵的基础上，调整参数引导P2P网络向动态平衡的方向演化。
SLACER算法初始化所有节点为不合作节点，忽略了合作节点的引导作用；拓扑重构是随机的，网络中高水平合作状态出现较慢；且缺少对不合作节点的激励措施。针对这些不足，本文提出了G-SLACER算法。首先，初始化部分节点为合作节点，充当标兵，起引导作用，引导不合作节点转化成合作节点，初始时网络中的合作节点称为标兵节点；其次，在拓扑重构过程中，新增一条到收益最高节点的引导型连接；再次，为了激励节点之间的协作，加大对不合作节点的奖励。
2拓扑重构算法描述
SLACER算法是一种随机进化算法，主要分为PD游戏过程和随机型拓扑重构过程两个阶段。PD游戏中参与双方有4种策略，每种策略对应不同的收益值。为了方便后面的讨论，简单介绍一下SLACER算法中的一些参数。
·节点策略：对等网络中的节点策略集S=f合作，不
合作l。
·PD游戏收益矩阵：博弈双方在游戏时采取不同的策略，获取不同的收益值。任意2个对等节点之间博弈的收益矩阵见表1。
·合作节点比例：网络中合作节点数目与网络总节点
数目的比值。
·CC（clustering coefficient，集聚系数）：节点i的邻居
节点之间实际的连接数与所有可能的连接数的比
例。多个节点集聚系数的平均值称为平均集聚系数。
·节点收益值：节点通过参加PD游戏获得的奖励值。
·合作连接路径(CCP)：连通路径上的连接节点对数
与网络中总节点对数的比值。连接节点对由信息传
输路径上的源节点和目的节点组成。
3 引导型拓扑重构算法描述
学习中有学习标兵，生活中有劳动模范，工作中有企业精英，这些都是本领域的突出角色，具有标榜引导作用。SLACER算法初始化网络中的所有节点为不合作节点，忽视了合作节点的引导作用，虽然最后网络中也出现了高水平的合作状态，但高水平合作状态出现的时延较大。
3.1 初始化标兵节点
本文先采用SJACER算法，初始化对等网络中一部分节点为标兵节点。仿真中分别初始化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算法的基础上引入了标兵节点，改进随机型拓扑重构过程为引导型拓扑重构过程。下面简单描述一下C-SLACER算法的执行过程。
(1)初始化网络节点总数的300/0为标兵节点，模拟周期数N=O。
(2)节点i从自己的邻居节点中随机选择一个节点进行PD游戏：如果节点i不存在邻居节点，则从网络中随机选择一个节点进行PD游戏。
(3)游戏结束，两个节点分别获取本次游戏的收益值。
(4)多次执行步骤(2)、步骤(3)，获得节点i的平均收益（执行次数与当前节点的度数有关）。
(5)节点i进入引导型拓扑重构过程。
(6)N++；如果N<100，跳转至步骤(2)；如果N=100，跳转至步骤(7)。
(7)结束。
C-SLACER算法的引导型拓扑重构过程在SLACER算法的随机型拓扑重构过程基础上进行了4个方面的改进，两种算法拓扑重构过程的比较见表2。其中，Lncigbons代表当前节点到邻居节点的连接，Nmax代表收益值最大的节点，nrand代表随机选择一个有收益值的节点，vj代表节点j的平均收益值，假定本次模拟中节点i的收益小于节点j。
下面是G-SIACER算法中引导型拓扑重构过程实现的一段伪代码。
for节点i
随机选择节点j；
ifUi< Uj
／／主动学习过程
i复制j的策略Si；
i以概率W断开自己的Lncigbons；
i动态有选择地复制节点j的Lncigbons；
／／拓扑重构过程
i连接到j；
i以概率M改变策略Si；
i以概率MR丢弃Lnew连接到Nrand和Nmax哪；
／／复位过程
设置i收益值为vj;
else if Uj<Ui
执行与上述相反的过程；
／／若两个节点收益相等
else UFUj且i、j同时为合作节点
节点二选一，执行引导型拓扑重构过程；
end if
end for
其中，Ui代表节点i的收益值，Uj代表节点j的收益值，Lnew代表当前节点新学习到的连接。
4仿真结果及分析
4.1 仿真参数配置
PeerSjm是基于Java的P2P网络仿真工具。本文模拟仿真采用PeerSim中的Cycle_based模式，具体参数设置如下：网络节点数力2 000，模拟周期数N=100，重连概率W=0.9，策略改变概率M=O.OOl，连接改变概率MR=0.01，PD游戏收益值T=1.9，R=l，P=O，S=O。
仿真中设置3个控制器，控制器control.0监测网络中合作节点比例、节点平均集聚系数、节点平均收益以及合作节点收益的变化趋势；控制器control.l监测合作连通路径的变化趋势，每周期记录一次数据；控制器contr01.2监测网络节点平均度数的变化趋势，每周期记录一次数据。
4.2仿真结果及分析
基于Bayes均衡博弈算法以及share strategy算法中网络节点总数、博弈收益值、模拟周期数的配置与上述具体参数保持一致，参数配置完成，运行仿真软件，分析3个控制器的输出结果。
SLACER算法、G-SLACER算法、基于Bayes均衡博弈算法以及share strategy算法中合作节点比例对比如图2所示。基于Bayes算法、share strategy算法分别设置网络中标兵节点比例为70%和15 %,运行100个周期，网络中合作节点比例分别达75%和80%：SLACER算法初始化网络节点全部为不合作节点，算法在第90个周期左右，网络中合作节点比例为900/0；G-SLACER算法初始化网络中30%的节点为标兵节点，算法在第50个周期，网络中合作节点
比例为900/0。算法执行100个周期，SLACER算法可以达到合作节点比例为98010的高水平合作网络，而G-SLACER算法在70个周期左右就可以达到合作节点比例为98%的高水平合作网络，且G-SLACER算法中合作节点比例的上升速度明显高于其他两种算法。G-SLACER算法在前10个周期，网络中合作节点比例出现下滑趋势。在算法初期，合作节点处于非合作节点的包围中，合作节点的优势还没显现出来，整个网络中的节点信心不足，导致合作节点比例出现下滑，度过初期后，网络中合作节点比例急速上升。G-SLACER算法的优势主要归因于算法在拓扑重构过程中引导型链接的选取。
SLACER算法和G-SLACER算法的平均集聚系数对比如图3所示。SLACER算法的平均集聚系数保持在0.45左右，而G-SLACER算法的平均集聚系数保持在0.5左右。C-SLACER算法使得节点的邻居节点之间的连接更加紧密，增强了网络的稳定性。
SLACER算法和G-SLACER算法的节点平均收益和合作节点收益对比如图4、图5所示。SLACER算法的节点平均收益在80个周期后分布在l附近，G-SLACER算法的节点平均收益在40个周期后分布在1.4以上。C-SLACER算法受奖惩机制的启发，加大了对收益较差节点的奖励，鼓励这些节点不断学习以增加网络整体收益：SLACER算法中合作节点收益在70个周期后分布在0.9左右,C-SLACER算法中合作节点收益在40个周期后分布在1.3左右。对比图4和图5．发现两种算法的节点平均收益与合作节点收益的变化趋势在整个模拟过程中大体保持一致。
图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,C-SJACER算法的节点平均度数为14，度数增加1。G-SLACER算法中的引导型拓扑重构过程比SLACER算法多连接了一个具有高收益的节点，因此节点平均度数增加了1。度数增多，有利于节点之间的交流，促进节点相互学习。产生合作网络初期，由G-SLACER与SLACER算法所构成的网络中节点的度数不稳定，主要归因于此时网络动荡较大，节点属性不稳定。初期过后，两种算法所形成的网络中节点度数趋于稳态。
4.3算法通用性
C-SLACER算法明显促进了网络高水平合作状态的出现，改善了网络性能参数，第4.2节的仿真是在2 000个节点的网络上模拟的，为了验证G-SLACER算法的通用性，分别在大小为4 000、8 000、16 000个节点的网络上仿真标兵节点为30%时，网络中合作节点比例的变化趋势，结果如图8所示。
由图8可以看出，虽然在构建合作网络的初期，由于网络节点间信任匮乏，而出现了短暂的合作节点比例下滑的情况，但不论网络规模多大，模拟实验中合作节点比例的变化趋势几乎是一致的。因此得出结论：G-SLACER算法适用于任意大小的网络，通用性良好。
5结束语
本文提出了一种引导型C-SLACER算法，引入标兵节点，优化拓扑重构过程，同时加大对收益较低节点的奖励。仿真结果表明，G-SLACER算法促进了网络节点之间的协作，增强了网络连通性和稳定性。选取引导型连接时，仅考虑了收益最高的节点，下一步研究工作可从选取多样化引导型连接人手，以达到快速形成高水平合作网络的目的。
6摘 要：为促进动态开放性对等网络中节点间的合作，在SLACER (selfish link-based adaptation for cooperationexcluding rewiring，基于自私连接排除重构的自适应合作)算法的基础上引入标兵节点，提出了引导型进化博弈算法G-SLACER(guided-SLACER)。通过初始化，网络节点总数的30%为标兵节点：拓扑重构过程中，新增一条到最具优势节点的引导型连接；为鼓励节点相互学习，加大网络整体收益。实验结果表明，C-SLACER算法针对不同规模的网络均具有良好的通用性，网络中CCP(cooperative connected path，合作连接路径)的稳定性增强。与其他进化博弈算法相比，G-SLACER算法形成的P2P网络的合作状态出现得更早、更平稳。
下一篇:返回列表
