61 电信科学 2016 年第 1 期 [2] 态加入与退出, 整个网络的拓扑结构始终处于动态变化中存在自私节点的对等网络随着时间的流逝, 拓扑结构会逐渐出现分化现象, 网络性能越来越差, 最后整个网络趋于瘫痪如何改变网络节点的属性, 鼓励节点积极参与网络活动? SLAC(selfish lin

Size: px

Start display at page:

Download "61 电信科学 2016 年第 1 期 [2] 态加入与退出, 整个网络的拓扑结构始终处于动态变化中存在自私节点的对等网络随着时间的流逝, 拓扑结构会逐渐出现分化现象, 网络性能越来越差, 最后整个网络趋于瘫痪如何改变网络节点的属性, 鼓励节点积极参与网络活动? SLAC(selfish lin"

妆浦
5 years ago
Views:

1 研究与开发研究与开发非结构化 P2P 网络引导型进化博弈算法朱国晖, 鲁春兰, 张瑞 ( 西安邮电大学通信与信息工程学院, 陕西西安 ) 摘要 : 为促进动态开放性对等网络中节点间的合作, 在 SLACER(selfish link-based adaptation for cooperation excluding rewiring, 基于自私连接排除重构的自适应合作 ) 算法的基础上引入标兵节点, 提出了引导型进化博弈算法 G-SLACER(guided-SLACER) 通过初始化, 网络节点总数的 30% 为标兵节点 ; 拓扑重构过程中, 新增一条到最具优势节点的引导型连接 ; 为鼓励节点相互学习, 加大网络整体收益实验结果表明,G-SLACER 算法针对不同规模的网络均具有良好的通用性, 网络中 CCP(cooperative connected path, 合作连接路径 ) 的稳定性增强与其他进化博弈算法相比,G-SLACER 算法形成的 P2P 网络的合作状态出现得更早更平稳关键词 : 对等网络 ; 标兵节点 ; 拓扑重构 ; 引导型 ;P2P 中图分类号 :TP393 文献标识码 :A doi: /j.issn 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 , China Abstract: 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. Key words: peer-to-peer network, pacesetter node, topology reconstruction, guided, P2P 1 引言对等网络由于自组织低部署维护成本 [1], 网络中的节点行为自由, 属性自私对等节点参与网络活动时, 注重个体利益忽略集体利益, 如文件共享系统中的 free riding 现象 P2P 网络是一种分布式的动态网络, 随着各对等节点的动收稿日期 : ; 修回日期 : 基金项目 : 陕西省教育厅科技计划基金资助项目 (No.07JK377) Foundation Item: Education Department Foundation of Shaanxi Province(No.07JK377)

2 61 电信科学 2016 年第 1 期 [2] 态加入与退出, 整个网络的拓扑结构始终处于动态变化中存在自私节点的对等网络随着时间的流逝, 拓扑结构会逐渐出现分化现象, 网络性能越来越差, 最后整个网络趋于瘫痪如何改变网络节点的属性, 鼓励节点积极参与网络活动? SLAC(selfish link-based adaptation for cooperation, 基于自私连接的自适应合作 ) 算法通过每周期完全重构连接自适应地产生合作网络, 但容易在合作网络中产生部 [3] 落现象 SLACER 算法中, 节点通过参与 PD(prisoner s dilemma, 囚徒困境 ) 游戏获取收益值, 算法根据节点收益值进行有保留的随机型拓扑重构, 进而自适应地产生合作网 [4,5] 络为了激励节点之间的协作, 建立一种基于重复博弈 [6] 理论和惩戒机制的 P2P 网络信誉模型, 模拟仿真证实, 该模型在促进节点间协作方面是有效的参考文献 [7,8] 基于进化博弈理论, 评估了 P2P 文件共享系统在异构环境下的性能, 讨论了自私节点的不作为行为, 仿真结果证实, 文件共享系统使用频率较低的文件的消失与自私节点的不作为有关系, 异构环境有利于文件的可用性和系统的稳固 [9] 性基于博弈论的对等网络节点自私性研究中, 提出了基于混合策略 Bayes 博弈的 P2P 文件共享机制, 该机制可有效地抑制自私节点的行为, 并使其更好地为其他节点提供服务量化分析节点行为, 提出共享型 P2P 节点策略 (share strategy) [10], 在随机博弈矩阵的基础上, 调整参数引导 P2P 网络向动态平衡的方向演化 SLACER 算法初始化所有节点为不合作节点, 忽略了合作节点的引导作用 ; 拓扑重构是随机的, 网络中高水平合作状态出现较慢 ; 且缺少对不合作节点的激励措施针对这些不足, 本文提出了 G-SLACER 算法首先, 初始化部分节点为合作节点, 充当标兵, 起引导作用, 引导不合作节点转化成合作节点, 初始时网络中的合作节点称为标兵节点 ; 其次, 在拓扑重构过程中, 新增一条到收益最高节点的引导型连接 ; 再次, 为了激励节点之间的协作, 加大对不合作节点的奖励 PD 游戏收益矩阵 : 博弈双方在游戏时采取不同的策略, 获取不同的收益值任意 2 个对等节点之间博弈的收益矩阵见表 1 表 1 博弈收益矩阵 peer1/peer2 合作不合作合作 (R,R) (S,T) 不合作 (T,S) (P,P) 合作节点比例 : 网络中合作节点数目与网络总节点数目的比值 CC(clustering coefficient, 集聚系数 ): 节点 i 的邻居节点之间实际的连接数与所有可能的连接数的比例多个节点集聚系数的平均值称为平均集聚系数节点收益值 : 节点通过参加 PD 游戏获得的奖励值合作连接路径 (CCP): 连通路径上的连接节点对数与网络中总节点对数的比值连接节点对由信息传输路径上的源节点和目的节点组成 3 引导型拓扑重构算法描述学习中有学习标兵, 生活中有劳动模范, 工作中有企业精英, 这些都是本领域的突出角色, 具有标榜引导作用 SLACER 算法初始化网络中的所有节点为不合作节点, 忽视了合作节点的引导作用, 虽然最后网络中也出现了高水平的合作状态, 但高水平合作状态出现的时延较大 3.1 初始化标兵节点本文先采用 SLACER 算法, 初始化对等网络中一部分节点为标兵节点仿真中分别初始化个总节点的 0 10% 20% 30% 40% 为标兵节点, 实验运行 100 次, 计算 100 个周期中网络合作节点比例变化平均值, 结果如图 1 所示 2 拓扑重构算法描述 SLACER 算法是一种随机进化算法, 主要分为 PD 游戏过程和随机型拓扑重构过程两个阶段 PD 游戏中参与双方有 4 种策略, 每种策略对应不同的收益值为了方便后面的讨论, 简单介绍一下 SLACER 算法中的一些参数节点策略 : 对等网络中的节点策略集 S={ 合作, 不合作 } 图 1 初始化不同比例标兵节点时网络合作节点的变化趋势

3 研究与开发从图 1 可以看出, 当网络中合作节点比例达到 90% 时, 初始化标兵节点比例为网络总数的 0 10% 20% 30% 40% 的模拟实验, 分别要到个周期才能满足要求因此, 当初始化网络中标兵节点为网络节点总数的 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 其中,L neighbors 代表当前节点到邻居节点的连接,N max 代表收益值最大的节点, N rand 代表随机选择一个有收益值的节点,V j 代表节点 j 的平均收益值, 假定本次模拟中节点 i 的收益小于节点 j 下面是 G-SLACER 算法中引导型拓扑重构过程实现的一段伪代码 for 节点 i 随机选择节点 j; if U i < U j // 主动学习过程 i 复制 j 的策略 S j ; i 以概率 W 断开自己的 L neighbors ; i 动态有选择地复制节点 j 的 L neighbors ; // 拓扑重构过程 i 连接到 j; i 以概率 M 改变策略 S j ; i 以概率 MR 丢弃 L new, 连接到 N rand 和 N max ; // 复位过程设置 i 收益值为 V j ; else if U j < U i 执行与上述相反的过程 ; // 若两个节点收益相等 else U i =U j 且 i j 同时为合作节点节点二选一, 执行引导型拓扑重构过程 ; end if end for 其中,U i 代表节点 i 的收益值,U j 代表节点 j 的收益值,L new 代表当前节点新学习到的连接 4 仿真结果及分析 4.1 仿真参数配置 PeerSim [11,12] 是基于 Java 的 P2P 网络仿真工具本文模 [13] 拟仿真采用 PeerSim 中的 Cycle_based 模式, 具体参数设置如下 : 网络节点数为 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 仿真结果及分析 62 基于 Bayes 均衡博弈算法以及 share strategy 算法中网络节点总数博弈收益值模拟周期数的配置与上述具体参数保持一致, 参数配置完成, 运行仿真软件, 分析 3 个控制器的输出结果 SLACER 算法 G-SLACER 算法基于 Bayes 均衡博弈算法以及 share strategy 算法中合作节点比例对比如图 2 所示基于 Bayes 算法 share strategy 算法分别设置网络中表 2 两种算法拓扑重构过程的比较算法主动学习过程拓扑重构过程复位过程两个节点收益相等 SLACER i 连接到 j 的 L neighbors i 连接 N rand 设置 i 收益为 0 随机选择一个节点 G-SLACER 根据收益差 i 连接到 j 的 L neighbors i 连接 N rand 和 N max 设置 i 收益为 V j S i S j 均为合作策略, 随机选择一个节点

4 63 电信科学 2016 年第 1 期图 2 4 种算法合作节点比例对比标兵节点比例为 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 算法的优势主要归因于算法在拓扑重构过程中引导型链接的选取 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 算法合作节点收益对比图 3 SLACER 算法和 G-SLACER 算法平均集聚系数对比图 6 是两种算法的合作连接路径对比两种算法的 CCP 值均收敛于 1, 前 30 个周期 SLACER 算法的 CCP 值波动较大,G-SLACER 算法则波动较小从图 5 可以看出, 前 10 个周期, 两种算法的 CCP 值均呈下滑趋势, 主要因为

5 研究与开发 64 的网络中节点度数趋于稳态 4.3 算法通用性 G-SLACER 算法明显促进了网络高水平合作状态的出现, 改善了网络性能参数, 第 4.2 节的仿真是在个节点的网络上模拟的, 为了验证 G-SLACER 算法的通用性, 分别在大小为个节点的网络上仿真标兵节点为 30% 时, 网络中合作节点比例的变化趋势, 结果如图 8 所示图 6 SLACER 算法和 G-SLACER 算法 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 算法所构成的网络中节点的度数不稳定, 主要归因于此时网络动荡较大, 节点属性不稳定初期过后, 两种算法所形成图 8 G-SLACER 算法在不同规模的网络下合作节点比例变化趋势由图 8 可以看出, 虽然在构建合作网络的初期, 由于网络节点间信任匮乏, 而出现了短暂的合作节点比例下滑的情况, 但不论网络规模多大, 模拟实验中合作节点比例的变化趋势几乎是一致的因此得出结论 :G-SLACER 算法适用于任意大小的网络, 通用性良好 5 结束语本文提出了一种引导型 G-SLACER 算法, 引入标兵节点, 优化拓扑重构过程, 同时加大对收益较低节点的奖励仿真结果表明,G-SLACER 算法促进了网络节点之间的协作, 增强了网络连通性和稳定性选取引导型连接时, 仅考虑了收益最高的节点, 下一步研究工作可从选取多样化引导型连接入手, 以达到快速形成高水平合作网络的目的参考文献 : 图 7 4 种算法下节点平均度数变化情况 [1] 张春红, 裘晓峰, 弭伟, 等. P2P 技术全面解析 [M]. 北京 : 人民邮电出版社,2010: ZHANG C H, QIU X F, MI W, et al. Comprehensive Analysis of P2P Technology[M]. Beijing: Posts & Telecom Press, 2010:

65 电信科学 2016 年第 1 期 [2] 管磊. P2P 技术揭秘 [M]. 北京 : 清华大学出社,2011:108-136. GUAN L. Reveal of P2P Technology [M]. Beijing: Tsinghua University Press, 2011:108-136. [3] MARCOZZI A, HALES D, JESI G P, et al.

Friends for free: self-organizing artificial social networks for trust and cooperation: technical Report UBLCS-2005-20 : 2005 [S/OL]. [2015-11-20]. http:/ / www. docin.com/p-972645743.html.

计算机辅助设计与图形学学报, 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].

6 65 电信科学 2016 年第 1 期 [2] 管磊. P2P 技术揭秘 [M]. 北京 : 清华大学出社,2011: GUAN L. Reveal of P2P Technology [M]. Beijing: Tsinghua University Press, 2011: [3] MARCOZZI A, HALES D, JESI G P, et al. Tag-based cooperation in peer-to-peer networks with newscast: technical Report UBLCS :2015 [S/OL].[ ]. com/p html. [4] HALES D, ARTECONI S. Friends for free: self-organizing artificial social networks for trust and cooperation: technical Report UBLCS : 2005 [S/OL]. [ ]. / www. docin.com/p 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): [6] 孟宪福, 王动. 基于重复博弈和惩戒机制的 P2P 协作激励信誉模型 [J]. 计算机辅助设计与图形学学报, 2010, 22 (5): 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): [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): [9] 姚霖. 基于博弈论的对等网络节点自私性研究 [D]. 济南 : 山东大学,2012: YAO L. The study on selfishness of nodes in P2P networks based on game theory [D]. Jinan: Shandong University, 2012: [10] 王杨, 王汝传, 徐小龙, 等. 资源共享 P2P 网络的进化博弈激励模型 [J]. 计算机工程,2011,37(11): 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): [11] PeerSim 中文教程 [EB/OL]. [ ]. com/view/83b35f104431b90d6c85c7ae.html. PeerSim Chinese course [EB/OL]. [ ]. baidu.com/view/83b35f104431b90d6c85c7ae.html. [12] PeerSim overview [EB/OL]. [ ]. sourceforge.net/doc/index.html. [13] JESI G P. PeerSim HOWTO: build a new protocol for the PeerSim 1.0 simulator [EB/OL]. [ ]. sourceforge.net/tutorial1/tutorial1.html. [ 作者简介 ] 朱国晖 (1969- ), 男, 西安邮电大学副教授硕士生导师, 主要研究方向为对等网络移动互联网复杂网络路由算法等鲁春兰 (1989- ), 女, 西安邮电大学硕士生, 主要研究方向为对等网络复杂网络路由算法张瑞 (1990-), 男, 西安邮电大学硕士生, 主要研究方向为对等网络路由算法

Microsoft Word - 793-797 tb20150504赵宏宇s-高校教改纵横.doc

Microsoft Word - 793-797 tb20150504赵宏宇s-高校教改纵横.doc 微生物学通报 Microbiology China tongbao@im.ac.cn Apr. 20, 2016, 43(4): 793 797 http://journals.im.ac.cn/wswxtbcn DOI: 10.13344/j.microbiol.china.150504 高校教改纵横生物工程专业发酵课程群建设探索 * 赵宏宇