一种复杂网络路由策略的普适优化算法

李世宝; 娄琳琳; 陈瑞祥; 洪利

doi:10.7498/aps.63.028901

摘要

现有的复杂网络路由策略很多，改进算法也不断涌现，但是目前还没有一个统一的标准来衡量算法是否达到网络最佳传输效果. 针对这一问题，本文提出一种适用于现有路由策略的普适优化算法. 首先通过理论分析指出制约网络传输能力的关键因素是最大介数中心度，因而“最大介数中心度是否已经最低”成为评判路由策略是否最优的标准. 在此基础上，采用“惩罚选择法”避开网络中介数中心度值比较大的节点，使网络介数中心度值分布更均匀，均衡网络中各个节点的传输负载.仿真结果显示，该优化算法针对现有路由策略均能降低最大介数中心度值，大幅度提高网络的传输能力.

关键词:

复杂网路 /
路由策略 /
拥塞 /
标准

Abstract

There are many existing routing strategies in complex networks, but there is no uniform standard to measure whether the strategies achieve optimal transmission effect. A pervasive optimized algorithm is proposed. The key factor restricting transmission capacity is maximum betweenness centrality and minimizing it becomes the uniform standard. In order to make betweenness centrality more evenly distributed and balance the traffic load of each node, we use punishment selection method to avoid the nodes with larger betweenness centrality. The simulation results show that the new algorithm could reduce maximum betweenness centrality of existing strategies and improve the network transmittability greatly.

Keywords:

作者及机构信息

1.
中国石油大学 (华东) 计算机与通信工程学院, 青岛 266580

基金项目: 中央高校基本科研业务费专项资金（批准号：12CX04077A）资助的课题.

Authors and contacts

1.
College of Computer and Communication Engineering, China University Of Petroleum, Qingdao 266580, China

Funds: Project supported by the Fundamental Research Funds for the Central Universities of Ministry of Education of China (Grant No. 12CX04077A).

参考文献

[1]	Bai W J, Wang B H, Zhou T 2005 Compl. Syst. Compl. Sci. 2 29 (in Chinese) [柏文洁, 汪秉宏, 周涛 2005 复杂系统与复杂性科学 2 29]
[2]	Liu H K, Zhou T 2007 Acta Phys. Sin. 56 106 (in Chinese) [刘宏鲲,周涛 2007 物理学报 56 106]
[3]	Li S B, Wu J J, Gao Z Y, Lin Y, Fu B B 2011 Acta Phys. Sin. 60 050701 (in Chinese) [李树彬, 吴建军, 高自友, 林勇, 傅白白 2011 物理学报 60 050701]
[4]	Liu Z H, Ma W C, Zhang H, Sun Y, Hui P M 2006 Physica A 370 843
[5]	Wang K, Zhou S Y, Zhang Y F, Pei W J, Liu Q 2011 Acta Phys. Sin. 60 118903 (in Chinese) [王开, 周思源, 张毅锋, 裴文江, 刘茜 2011 物理学报 60 118903]
[6]	Zhou T 2008 Physica A 387 3025
[7]	Yan G, Zhou T, Hu B, Fu Z Q, Wang B H 2006 Phys. Rev. E 73 046108
[8]	Wang S P, Pei W J 2009 Physica A 388 514
[9]	Shao F, Jiang G P 2011 Acta Phys. Sin. 60 078902 (in Chinese) [邵斐, 蒋国平 2011 物理学报 60 078902]
[10]	Danila B, Yu Y, Marsh J A, Bassler K E 2006 Phys. Rev. E 74 046106
[11]	Chen L, Chen J, Guan Z H, Zhang X H, Zhang D X 2012 Physica A 391 3336
[12]	Liu G, Li Y S 2012 Acta Phys. Sin. 61 108901 (in Chinese) [刘刚, 李永树 2012 物理学报 61 108901]
[13]	Liu G, Li Y S, Zhang X P 2013 Chin. Phys. B 22 068901
[14]	Tang M, Zhou T 2011 Phys. Rev. E 84 026116
[15]	Ling X, Hu M B, Long J C, Ding J X, Shi Q 2013 Chin. Phys. B 22 018904
[16]	Hu M B, Lau H Y K, Ling X, Jiang R 2012 Chin. Phys. Lett. 29 128902
[17]	Ramasco J, Marta S, Lopez E, Boettcher S 2010 Phys. Rev. E 82 036119
[18]	Chen H L, Liu Z X, Chen Z Q, Yuan Z Z 2009 Acta Phys. Sin. 58 6068 (in Chinese) [陈华良, 刘忠信, 陈增强, 袁著祉 2009 物理学报 58 6068]
[19]	Li T, Pei W J, Wang S P 2009 Acta Phys. Sin. 58 5903 (in Chinese) [李涛, 裴文江, 王少平 2009 物理学报 58 5903]
[20]	Liu G, Li Y S 2012 Acta Phys. Sin. 61 248901 (in Chinese) [刘刚,李永树 2012 物理学报 61 248901]
[21]	Zhang G Q, Wang D, Li G J 2007 Phys. Rev. E 76 017101
[22]	Eisler Z, Kertesz J 2005 Phys. Rev. E 71 057104
[23]	Danila B, Yu Y, Marsh J A, Bassler K E 2007 Chaos 17 026102
[24]	Wang W X, Yin C Y, Yan G, Wang B H 2006 Phys. Rev. E 74 016101
[25]	Meloni S, Gomez-Gardenes J 2010 Phys. Rev. E 82 056105
[26]	Barthélemy M 2004 Eur. Phys. J. B 38 163
[27]	Barabási A L, Albert R 1999 Science 286 509

施引文献

[1]	Bai W J, Wang B H, Zhou T 2005 Compl. Syst. Compl. Sci. 2 29 (in Chinese) [柏文洁, 汪秉宏, 周涛 2005 复杂系统与复杂性科学 2 29]
[2]	Liu H K, Zhou T 2007 Acta Phys. Sin. 56 106 (in Chinese) [刘宏鲲,周涛 2007 物理学报 56 106]
[3]	Li S B, Wu J J, Gao Z Y, Lin Y, Fu B B 2011 Acta Phys. Sin. 60 050701 (in Chinese) [李树彬, 吴建军, 高自友, 林勇, 傅白白 2011 物理学报 60 050701]
[4]	Liu Z H, Ma W C, Zhang H, Sun Y, Hui P M 2006 Physica A 370 843
[5]	Wang K, Zhou S Y, Zhang Y F, Pei W J, Liu Q 2011 Acta Phys. Sin. 60 118903 (in Chinese) [王开, 周思源, 张毅锋, 裴文江, 刘茜 2011 物理学报 60 118903]
[6]	Zhou T 2008 Physica A 387 3025
[7]	Yan G, Zhou T, Hu B, Fu Z Q, Wang B H 2006 Phys. Rev. E 73 046108
[8]	Wang S P, Pei W J 2009 Physica A 388 514
[9]	Shao F, Jiang G P 2011 Acta Phys. Sin. 60 078902 (in Chinese) [邵斐, 蒋国平 2011 物理学报 60 078902]
[10]	Danila B, Yu Y, Marsh J A, Bassler K E 2006 Phys. Rev. E 74 046106
[11]	Chen L, Chen J, Guan Z H, Zhang X H, Zhang D X 2012 Physica A 391 3336
[12]	Liu G, Li Y S 2012 Acta Phys. Sin. 61 108901 (in Chinese) [刘刚, 李永树 2012 物理学报 61 108901]
[13]	Liu G, Li Y S, Zhang X P 2013 Chin. Phys. B 22 068901
[14]	Tang M, Zhou T 2011 Phys. Rev. E 84 026116
[15]	Ling X, Hu M B, Long J C, Ding J X, Shi Q 2013 Chin. Phys. B 22 018904
[16]	Hu M B, Lau H Y K, Ling X, Jiang R 2012 Chin. Phys. Lett. 29 128902
[17]	Ramasco J, Marta S, Lopez E, Boettcher S 2010 Phys. Rev. E 82 036119
[18]	Chen H L, Liu Z X, Chen Z Q, Yuan Z Z 2009 Acta Phys. Sin. 58 6068 (in Chinese) [陈华良, 刘忠信, 陈增强, 袁著祉 2009 物理学报 58 6068]
[19]	Li T, Pei W J, Wang S P 2009 Acta Phys. Sin. 58 5903 (in Chinese) [李涛, 裴文江, 王少平 2009 物理学报 58 5903]
[20]	Liu G, Li Y S 2012 Acta Phys. Sin. 61 248901 (in Chinese) [刘刚,李永树 2012 物理学报 61 248901]
[21]	Zhang G Q, Wang D, Li G J 2007 Phys. Rev. E 76 017101
[22]	Eisler Z, Kertesz J 2005 Phys. Rev. E 71 057104
[23]	Danila B, Yu Y, Marsh J A, Bassler K E 2007 Chaos 17 026102
[24]	Wang W X, Yin C Y, Yan G, Wang B H 2006 Phys. Rev. E 74 016101
[25]	Meloni S, Gomez-Gardenes J 2010 Phys. Rev. E 82 056105
[26]	Barthélemy M 2004 Eur. Phys. J. B 38 163
[27]	Barabási A L, Albert R 1999 Science 286 509

[1]	王玉坤, 李泽阳, 许康, 王子正. 制备-测量量子比特系统的自测试标准. 物理学报, 2023, 72(10): 100303. doi: 10.7498/aps.72.20222431
[2]	林泓, 夏永祥, 蒋路茸. 基于最短路径长度的空间网络路由. 物理学报, 2022, 71(6): 068901. doi: 10.7498/aps.71.20211621
[3]	马金龙, 张俊峰, 张冬雯, 张红斌. 基于通信序列熵的复杂网络传输容量. 物理学报, 2021, 70(7): 078902. doi: 10.7498/aps.70.20201300
[4]	钟青, 王雪深, 李劲劲, 鲁云峰, 李正坤, 王文新, 孙庆灵. 1 k量子霍尔阵列电阻标准器件研制. 物理学报, 2016, 65(22): 227301. doi: 10.7498/aps.65.227301
[5]	薛佳, 秦际良, 张玉驰, 李刚, 张鹏飞, 张天才, 彭堃墀. 低频标准真空涨落的测量. 物理学报, 2016, 65(4): 044211. doi: 10.7498/aps.65.044211
[6]	聂敏, 刘广腾, 杨光, 裴昌幸. 基于最少中继节点约束的量子VoIP路由优化策略. 物理学报, 2016, 65(12): 120302. doi: 10.7498/aps.65.120302
[7]	杨先霞, 濮存来, 许忠奇, 陈荣斌, 吴洁鑫, 李伦波. 无标度网络中基于能量的混合路由策略. 物理学报, 2016, 65(24): 248901. doi: 10.7498/aps.65.248901
[8]	刘伟彦, 刘斌. 基于局部路由策略的复杂网络拥塞控制. 物理学报, 2014, 63(24): 248901. doi: 10.7498/aps.63.248901
[9]	刘晓慧, 聂敏, 裴昌幸. 量子无线广域网构建与路由策略. 物理学报, 2013, 62(20): 200304. doi: 10.7498/aps.62.200304
[10]	王丹, 金小峥. 可调聚类系数加权无标度网络建模及其拥塞问题研究. 物理学报, 2012, 61(22): 228901. doi: 10.7498/aps.61.228901
[11]	刘刚, 李永树. 基于引力约束的复杂网络拥塞问题研究. 物理学报, 2012, 61(10): 108901. doi: 10.7498/aps.61.108901
[12]	刘刚, 李永树. 基于引力场理论的复杂网络路由选择策略研究. 物理学报, 2012, 61(24): 248901. doi: 10.7498/aps.61.248901
[13]	周小清, 邬云文, 赵晗. 量子隐形传态网络的互联与路由策略. 物理学报, 2011, 60(4): 040304. doi: 10.7498/aps.60.040304.2
[14]	王开, 周思源, 张毅锋, 裴文江, 刘茜. 一类基于随机行走机理的优化路由改进策略. 物理学报, 2011, 60(11): 118903. doi: 10.7498/aps.60.118903
[15]	李涛, 裴文江, 王少平. 无标度复杂网络负载传输优化策略. 物理学报, 2009, 58(9): 5903-5910. doi: 10.7498/aps.58.5903
[16]	王丹, 于灏, 井元伟, 姜囡, 张嗣瀛. 基于感知流量算法的复杂网络拥塞问题研究. 物理学报, 2009, 58(10): 6802-6808. doi: 10.7498/aps.58.6802
[17]	陈华良, 刘忠信, 陈增强, 袁著祉. 复杂网络的一种加权路由策略研究. 物理学报, 2009, 58(9): 6068-6073. doi: 10.7498/aps.58.6068
[18]	林海, 吴晨旭. 基于遗传算法的重复囚徒困境博弈策略在复杂网络中的演化. 物理学报, 2007, 56(8): 4313-4318. doi: 10.7498/aps.56.4313
[19]	水嘉鹏, 刘咏松. 低频内耗测量时标准滞弹性固体的内耗行为. 物理学报, 1999, 48(4): 692-698. doi: 10.7498/aps.48.692
[20]	刘军贤, 陈光旨, 王光瑞, 陈式刚. 标准映象的周期分岔及其向混沌的过渡. 物理学报, 1988, 37(1): 119-127. doi: 10.7498/aps.37.119

计量

文章访问数: 8992
PDF下载量: 661
被引次数: 0

姓名
邮箱
手机号码
标题
留言内容
验证码

搜索

留言板