一类基于随机行走机理的优化路由改进策略

王开; 周思源; 张毅锋; 裴文江; 刘茜

doi:10.7498/aps.60.118903

摘要

在对随机行走过程的研究中发现:单个粒子通过某条特定路径的时间正比于该路径上所有节点度的连乘积.据此,文章提出基于随机行走机理的优化路由改进策略.该策略以节点度连乘积最小化为原则,通过调节可变参数,建立节点处理能力均匀分布的情况下最佳路由策略.通过分析比较不同路由策略条件下平均路由介数中心度,网络的临界负载量,平均路径长度以及平均搜索信息量等性能指标,研究结果表明,此改进路由策略在保证网络平均路径长度较少增加的前提下,使网络的传输能力获得最大幅度的提升.

关键词:

Abstract

In our original contributions, we found that the time which a random walker spends in finding a given path is directly proportional to the continued product of the degrees of all the nodes which pass through the given path. In this paper, with our original contributions, we give a modified routing strategy to improve the capacity of the network when all nodes have the same packet-delivery rates. We define an average routing centrality degree of the node to analyze the traffic load on the node with different degrees, and then we analyze the transportation capacity by using the critical value of Rc, the average packet travel time, the average path length and the search information. Both theoretical and experimental results show that compared with the shortest path strategy and the efficient path strategy, the new strategy can enhance the network capability.

Keywords:

作者及机构信息

1.
东南大学信息科学与工程学院,南京 210096

基金项目: 国家自然科学基金(批准号: 60672095,60972165)、国家高技术研究发展计划(批准号: 2007AA11Z210)、教育部博士点基金(批准号: 20100092120012, 20070286004)、江苏省高技术研究项目、江苏省自然科学基金(批准号: BK2010240)、国家十一五密码发展基金和国家火炬计划项目资助的课题.

Authors and contacts

1.
School of Information Science and Engineering, Southeast University, Nanjing 210096, China

参考文献

[1]	Watts D J, Strogatz S H 1998 Nature 393 440
[2]
[3]	Barabsi A L, Albert R 1999 Science 286 509
[4]	Song C, Havlin S, Makse H A 2006 Nature 433 392
[5]
[6]
[7]	Zhao L, Park K, Lai Y C 2004 Phys. Rev. E 70 035101
[8]	Zhao L, Lai Y C, Park K, Ye N 2005 Phys. Rev. E 71 026125
[9]
[10]
[11]	Wang W X, Wang B H, Yin C Y 2006 Phys. Rev. E 73 026111
[12]
[13]	Wang W X, Yin C Y, Yan G, Wang B H 2006 Phys. Rev. E 74 016101
[14]	Hu M B, Wang W X, Jiang R 2007 Phys. Rev. E 75 036102
[15]
[16]
[17]	Ling X, Hu M B, Jiang R, Wang R L, Cao X B, Wu Q S 2009 Phys. Rev. E 80 066110
[18]
[19]	Liu Z, Hu M B, Jiang R, Wang W X 2007 Phys. Rev. E 76 037101
[20]	Yan G, Zhou T, Hu B 2006 Phys. Rev. E 73 046108
[21]
[22]	Yin C Y, Wang B H, Wang W X, Yan G, Yang H J 2006 Eur. Phys. J. B 49 205
[23]
[24]	Ling X, Hu M B 2010 Phys. Rev. E 81 016113
[25]
[26]
[27]	Ling X, Hu M B 2009 Phys. Rev. E 80 066110
[28]	Wang W X, Yin C Y 2006 Phys. Rev. E 74 016101
[29]
[30]
[31]	Zhang H, Liu Z 2007 Phys. Lett. A 364 177
[32]
[33]	Shen Y, Pei W J, Wang K 2009 Chin. Phys. B 18 3783
[34]
[35]	Danila B, Yu Y 2006 Phys. Rev. E 74 046106
[36]	Ramasco J J, Lama M, Lopez E, Boettcher S arXiv:1006.0711v1
[37]
[38]
[39]	Wang S P, Pei W J 2009 Physica A 388 514
[40]	Wang S P, Pei W J arXiv:1007.1809v1, 2010
[41]
[42]
[43]	Tao L, Pei W J, Wang S P 2009 Acta Phys. Sin. 58 5903[李涛、裴文江、王少平 2009 物理学报 58 5903]
[44]
[45]	Wang K, Zhang Y F, Zhou S Y, Pei W J, Li T, Wang S P, Optimal routing strategy based on random walk on complex networks, Physica A (accecpted)
[46]
[47]	Sneppen K, Trusina A, Rosvall M, arXiv:cond-mat/040755v1 2004
[48]
[49]	Rosvall M, Trusina A, Minnhagen P, Sneppen K 2005 Phys. Rev. Lett. 94028701

施引文献

[1]	Watts D J, Strogatz S H 1998 Nature 393 440
[2]
[3]	Barabsi A L, Albert R 1999 Science 286 509
[4]	Song C, Havlin S, Makse H A 2006 Nature 433 392
[5]
[6]
[7]	Zhao L, Park K, Lai Y C 2004 Phys. Rev. E 70 035101
[8]	Zhao L, Lai Y C, Park K, Ye N 2005 Phys. Rev. E 71 026125
[9]
[10]
[11]	Wang W X, Wang B H, Yin C Y 2006 Phys. Rev. E 73 026111
[12]
[13]	Wang W X, Yin C Y, Yan G, Wang B H 2006 Phys. Rev. E 74 016101
[14]	Hu M B, Wang W X, Jiang R 2007 Phys. Rev. E 75 036102
[15]
[16]
[17]	Ling X, Hu M B, Jiang R, Wang R L, Cao X B, Wu Q S 2009 Phys. Rev. E 80 066110
[18]
[19]	Liu Z, Hu M B, Jiang R, Wang W X 2007 Phys. Rev. E 76 037101
[20]	Yan G, Zhou T, Hu B 2006 Phys. Rev. E 73 046108
[21]
[22]	Yin C Y, Wang B H, Wang W X, Yan G, Yang H J 2006 Eur. Phys. J. B 49 205
[23]
[24]	Ling X, Hu M B 2010 Phys. Rev. E 81 016113
[25]
[26]
[27]	Ling X, Hu M B 2009 Phys. Rev. E 80 066110
[28]	Wang W X, Yin C Y 2006 Phys. Rev. E 74 016101
[29]
[30]
[31]	Zhang H, Liu Z 2007 Phys. Lett. A 364 177
[32]
[33]	Shen Y, Pei W J, Wang K 2009 Chin. Phys. B 18 3783
[34]
[35]	Danila B, Yu Y 2006 Phys. Rev. E 74 046106
[36]	Ramasco J J, Lama M, Lopez E, Boettcher S arXiv:1006.0711v1
[37]
[38]
[39]	Wang S P, Pei W J 2009 Physica A 388 514
[40]	Wang S P, Pei W J arXiv:1007.1809v1, 2010
[41]
[42]
[43]	Tao L, Pei W J, Wang S P 2009 Acta Phys. Sin. 58 5903[李涛、裴文江、王少平 2009 物理学报 58 5903]
[44]
[45]	Wang K, Zhang Y F, Zhou S Y, Pei W J, Li T, Wang S P, Optimal routing strategy based on random walk on complex networks, Physica A (accecpted)
[46]
[47]	Sneppen K, Trusina A, Rosvall M, arXiv:cond-mat/040755v1 2004
[48]
[49]	Rosvall M, Trusina A, Minnhagen P, Sneppen K 2005 Phys. Rev. Lett. 94028701

[1]	林泓, 夏永祥, 蒋路茸. 基于最短路径长度的空间网络路由. 物理学报, 2022, 71(6): 068901. doi: 10.7498/aps.71.20211621
[2]	马金龙, 张俊峰, 张冬雯, 张红斌. 基于通信序列熵的复杂网络传输容量. 物理学报, 2021, 70(7): 078902. doi: 10.7498/aps.70.20201300
[3]	蒋文君, 刘润然, 范天龙, 刘霜霜, 吕琳媛. 多层网络级联失效的预防和恢复策略概述. 物理学报, 2020, 69(8): 088904. doi: 10.7498/aps.69.20192000
[4]	杨先霞, 濮存来, 许忠奇, 陈荣斌, 吴洁鑫, 李伦波. 无标度网络中基于能量的混合路由策略. 物理学报, 2016, 65(24): 248901. doi: 10.7498/aps.65.248901
[5]	段东立, 武小悦. 基于可调负载重分配的无标度网络连锁效应分析. 物理学报, 2014, 63(3): 030501. doi: 10.7498/aps.63.030501
[6]	刘伟彦, 刘斌. 基于局部路由策略的复杂网络拥塞控制. 物理学报, 2014, 63(24): 248901. doi: 10.7498/aps.63.248901
[7]	李世宝, 娄琳琳, 陈瑞祥, 洪利. 一种复杂网络路由策略的普适优化算法. 物理学报, 2014, 63(2): 028901. doi: 10.7498/aps.63.028901
[8]	李雨珊, 吕翎, 刘烨, 刘硕, 闫兵兵, 常欢, 周佳楠. 复杂网络时空混沌同步的Backstepping设计. 物理学报, 2013, 62(2): 020513. doi: 10.7498/aps.62.020513
[9]	蔡君, 余顺争. 一种有效提高无标度网络负载容量的管理策略. 物理学报, 2013, 62(5): 058901. doi: 10.7498/aps.62.058901
[10]	刘刚, 李永树. 基于引力场理论的复杂网络路由选择策略研究. 物理学报, 2012, 61(24): 248901. doi: 10.7498/aps.61.248901
[11]	崔爱香, 傅彦, 尚明生, 陈端兵, 周涛. 复杂网络局部结构的涌现:共同邻居驱动网络演化. 物理学报, 2011, 60(3): 038901. doi: 10.7498/aps.60.038901
[12]	姜志宏, 王晖, 高超. 一种基于随机行走和策略连接的网络演化模型. 物理学报, 2011, 60(5): 058903. doi: 10.7498/aps.60.058903
[13]	邵斐, 蒋国平. 基于社团结构的负载传输优化策略研究. 物理学报, 2011, 60(7): 078902. doi: 10.7498/aps.60.078902
[14]	宋玉蓉, 蒋国平. 具有非均匀传输和抗攻击差异的网络病毒传播模型. 物理学报, 2010, 59(11): 7546-7551. doi: 10.7498/aps.59.7546
[15]	王丹, 于灏, 井元伟, 姜囡, 张嗣瀛. 基于感知流量算法的复杂网络拥塞问题研究. 物理学报, 2009, 58(10): 6802-6808. doi: 10.7498/aps.58.6802
[16]	陈华良, 刘忠信, 陈增强, 袁著祉. 复杂网络的一种加权路由策略研究. 物理学报, 2009, 58(9): 6068-6073. doi: 10.7498/aps.58.6068
[17]	李涛, 裴文江, 王少平. 无标度复杂网络负载传输优化策略. 物理学报, 2009, 58(9): 5903-5910. doi: 10.7498/aps.58.5903
[18]	许丹, 李翔, 汪小帆. 复杂网络病毒传播的局域控制研究. 物理学报, 2007, 56(3): 1313-1317. doi: 10.7498/aps.56.1313
[19]	林海, 吴晨旭. 基于遗传算法的重复囚徒困境博弈策略在复杂网络中的演化. 物理学报, 2007, 56(8): 4313-4318. doi: 10.7498/aps.56.4313
[20]	李季, 汪秉宏, 蒋品群, 周涛, 王文旭. 节点数加速增长的复杂网络生长模型. 物理学报, 2006, 55(8): 4051-4057. doi: 10.7498/aps.55.4051

计量

文章访问数: 8069
PDF下载量: 647
被引次数: 0

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

搜索

留言板