一种应用于含权无标度网络的全局路由算法

濮存来; 裴文江

doi:10.7498/aps.59.3841

摘要

针对含权无标度网络提出了一种全局路由算法.该算法利用网络路径上的节点强度信息构建了一种全局路由代价函数，选择使该代价函数最小的路径来传输信息包，有效避开了网络中易发生拥塞的核心节点.实验结果表明，与最短路径算法相比，该算法以较小的平均路径长度的增加为代价，将网络容量提高了十多倍.

关键词:

In this article, a global routing method is proposed for weighted scale-free networks. To bypass the central nodes and alleviate the congestion, it chooses the best route according to the minimum value of the cost function which is based on the node strength. Simulation results show that the network capacity is improved more than 10 times by our method than by the shortest path strategy at the cost of a slightly growth in the average path-length.

Keywords:

作者及机构信息

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

基金项目: 国家自然科学基金（批准号： 60672095， 60972165）、国家高技术研究发展计划（批准号：2007AA11Z210）和江苏省自然科学基金（批准号：BK2008281）资助的课题.

Authors and contacts

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

参考文献

[1]	［1］Barabsi A L, Albert R 2002 Rev. Mod. Phys. 74 47
[2]	［2］Newman M E J 2003 SIAM Rev. 45 167
[3]	［3］Boccaletti S, Latora V, Moreno Y, Chavez M, Hwang D U 2006 Phys. Rep. 424 175
[4]	［4］Li J, Wang B H, Jiang P Q, Zhou T, Wang W X 2006 Acta Phys. Sin. 55 4051 (in Chinese) ［李季、汪秉宏、蒋品群、周涛、王文旭 2006 55 4051］
[5]	［5］Zanette D H 2002 Phys. Rev. E 65 041908
[6]	［6］Moreno Y, Gómez J B, Pacheco A F 2003 Phys. Rev. E 68 035103
[7]	［7］Xu D, Li X, Wang X F 2007 Acta Phys. Sin. 56 1313 (in Chinese)［许丹、李翔、汪小帆 2007 56 1313］
[8]	［8］Huang W, Jiang R, Hu M B, Wu Q S 2009 Chin. Phys. B 18 1306
[9]	［9］Jin Z, Liu Q X, Mainul H 2007 Chin. Phys. 16 1267
[10]	］Wu Z X, Wang Y H 2007 Phys. Rev. E 75 041114
[11]	］Zhao M, Wang B H, Jiang P Q, Zhou T 2005 Prog. Phys. 25 273 (in Chinese) ［赵明、汪秉宏、蒋品群、周涛 2005 物理学进展 25 273］
[12]	］Sorrentino F, Ott E 2008 Phys. Rev. Lett. 100 114101
[13]	］Luo Q, Wu W, Li L X, Yang Y X, Peng H P 2008 Acta Phys. Sin. 57 1529 (in Chinese)［罗群、吴薇、李丽香、杨义先、彭海朋 2008 57 1529］
[14]	］Lü L, Zhang C 2009 Acta Phys. Sin. 58 1462（in Chinese）［吕翎、张超 2009 58 1462］
[15]	］Dobson I, Carreras B A, Newman D E 2005 Prob. Eng. Inform. Sci. 19 15
[16]	］Wang W X, Chen G R 2008 Phys. Rev. E 77 026101
[17]	］Ouyang M, Fei Q, Yu M H 2008 Acta Phys. Sin. 57 6763 （in Chinese）［欧阳敏、费奇、余明晖 2008 57 6763］
[18]	］Kleinberg J 2000 Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (New York: ACM) p163
[19]	］Adamic L A, Lukose R M, Puniyani A R, Huberman B A 2001 Phys. Rev. E 64 046135
[20]	］Lü Q, Cao P, Cohen E, Li K, Shenker S 2002 Proceedings of the 16th ACM International Conference on Supercomputing (New York: ACM) p84
[21]	］Noh J D 2004 Phys. Rev. Lett. 92 11
[22]	］Wang S P, Pei W J 2008 Physica A 387 4699
[23]	］Yang S J 2005 Phys. Rev. E 71 016107
[24]	］Zhou T 2008 Physica A 387 3025
[25]	］Kim B J, Yoon C N, Han S K, Jeong H 2002 Phys. Rev. E 65 027103
[26]	］Thadakamalla H P, Albert R, Kumara S R T 2005 Phys. Rev. E 72 066128
[27]	］Yan G, Zhou T, Hu B, Fu Z Q, Wang B H 2006 Phys. Rev. E 73 046108
[28]	］Wang W X, Yin C Y, Yan G, Wang B H 2006 Phys. Rev. E 74 016101
[29]	］Chen Z Y, Wang X F 2006 Phys. Rev. E 73 036107
[30]	］Zhang G Q, Wang D, Li G J 2007 Phys. Rev. E 76 017101
[31]	］Danila B, Yu Y, Marsh J A, Bassler K E 2006 Phys. Rev. E 74 046106
[32]	］Yin C Y, Wang B H, Wang W X, Yan G, Yang H J 2006 Eur. Phys. J. B 49 205
[33]	］Wang W X, Wang B H, Yin C Y, Xie Y B, Zhou T 2006 Phys. Rev. E 73 026111
[34]	］Wang W X, Wang B H, Hu B, Yan G, Ou Q 2005 Phys. Rev. Lett. 94 188702
[35]	］Arenas A, Díaz-Guilera A, Guimera′ R 2001 Phys. Rev. Lett. 86 3196
[36]	］Hu M B, Jiang R, Wu Y H, Wang W X, Wu Q S 2008 Physica A 387 4967
[37]	］Zhao L, Lai Y C, Park K, Ye N 2005 Phys. Rev. E 71 026125

施引文献

[1]	［1］Barabsi A L, Albert R 2002 Rev. Mod. Phys. 74 47
[2]	［2］Newman M E J 2003 SIAM Rev. 45 167
[3]	［3］Boccaletti S, Latora V, Moreno Y, Chavez M, Hwang D U 2006 Phys. Rep. 424 175
[4]	［4］Li J, Wang B H, Jiang P Q, Zhou T, Wang W X 2006 Acta Phys. Sin. 55 4051 (in Chinese) ［李季、汪秉宏、蒋品群、周涛、王文旭 2006 55 4051］
[5]	［5］Zanette D H 2002 Phys. Rev. E 65 041908
[6]	［6］Moreno Y, Gómez J B, Pacheco A F 2003 Phys. Rev. E 68 035103
[7]	［7］Xu D, Li X, Wang X F 2007 Acta Phys. Sin. 56 1313 (in Chinese)［许丹、李翔、汪小帆 2007 56 1313］
[8]	［8］Huang W, Jiang R, Hu M B, Wu Q S 2009 Chin. Phys. B 18 1306
[9]	［9］Jin Z, Liu Q X, Mainul H 2007 Chin. Phys. 16 1267
[10]	］Wu Z X, Wang Y H 2007 Phys. Rev. E 75 041114
[11]	］Zhao M, Wang B H, Jiang P Q, Zhou T 2005 Prog. Phys. 25 273 (in Chinese) ［赵明、汪秉宏、蒋品群、周涛 2005 物理学进展 25 273］
[12]	］Sorrentino F, Ott E 2008 Phys. Rev. Lett. 100 114101
[13]	］Luo Q, Wu W, Li L X, Yang Y X, Peng H P 2008 Acta Phys. Sin. 57 1529 (in Chinese)［罗群、吴薇、李丽香、杨义先、彭海朋 2008 57 1529］
[14]	］Lü L, Zhang C 2009 Acta Phys. Sin. 58 1462（in Chinese）［吕翎、张超 2009 58 1462］
[15]	］Dobson I, Carreras B A, Newman D E 2005 Prob. Eng. Inform. Sci. 19 15
[16]	］Wang W X, Chen G R 2008 Phys. Rev. E 77 026101
[17]	］Ouyang M, Fei Q, Yu M H 2008 Acta Phys. Sin. 57 6763 （in Chinese）［欧阳敏、费奇、余明晖 2008 57 6763］
[18]	］Kleinberg J 2000 Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (New York: ACM) p163
[19]	］Adamic L A, Lukose R M, Puniyani A R, Huberman B A 2001 Phys. Rev. E 64 046135
[20]	］Lü Q, Cao P, Cohen E, Li K, Shenker S 2002 Proceedings of the 16th ACM International Conference on Supercomputing (New York: ACM) p84
[21]	］Noh J D 2004 Phys. Rev. Lett. 92 11
[22]	］Wang S P, Pei W J 2008 Physica A 387 4699
[23]	］Yang S J 2005 Phys. Rev. E 71 016107
[24]	］Zhou T 2008 Physica A 387 3025
[25]	］Kim B J, Yoon C N, Han S K, Jeong H 2002 Phys. Rev. E 65 027103
[26]	］Thadakamalla H P, Albert R, Kumara S R T 2005 Phys. Rev. E 72 066128
[27]	］Yan G, Zhou T, Hu B, Fu Z Q, Wang B H 2006 Phys. Rev. E 73 046108
[28]	］Wang W X, Yin C Y, Yan G, Wang B H 2006 Phys. Rev. E 74 016101
[29]	］Chen Z Y, Wang X F 2006 Phys. Rev. E 73 036107
[30]	］Zhang G Q, Wang D, Li G J 2007 Phys. Rev. E 76 017101
[31]	］Danila B, Yu Y, Marsh J A, Bassler K E 2006 Phys. Rev. E 74 046106
[32]	］Yin C Y, Wang B H, Wang W X, Yan G, Yang H J 2006 Eur. Phys. J. B 49 205
[33]	］Wang W X, Wang B H, Yin C Y, Xie Y B, Zhou T 2006 Phys. Rev. E 73 026111
[34]	］Wang W X, Wang B H, Hu B, Yan G, Ou Q 2005 Phys. Rev. Lett. 94 188702
[35]	］Arenas A, Díaz-Guilera A, Guimera′ R 2001 Phys. Rev. Lett. 86 3196
[36]	］Hu M B, Jiang R, Wu Y H, Wang W X, Wu Q S 2008 Physica A 387 4967
[37]	］Zhao L, Lai Y C, Park K, Ye N 2005 Phys. Rev. E 71 026125

[1]	林泓, 夏永祥, 蒋路茸. 基于最短路径长度的空间网络路由. , 2022, 71(6): 068901. doi: 10.7498/aps.71.20211621
[2]	马金龙, 张俊峰, 张冬雯, 张红斌. 基于通信序列熵的复杂网络传输容量. , 2021, 70(7): 078902. doi: 10.7498/aps.70.20201300
[3]	孔江涛, 黄健, 龚建兴, 李尔玉. 基于复杂网络动力学模型的无向加权网络节点重要性评估. , 2018, 67(9): 098901. doi: 10.7498/aps.67.20172295
[4]	聂敏, 刘广腾, 杨光, 裴昌幸. 基于最少中继节点约束的量子VoIP路由优化策略. , 2016, 65(12): 120302. doi: 10.7498/aps.65.120302
[5]	杨先霞, 濮存来, 许忠奇, 陈荣斌, 吴洁鑫, 李伦波. 无标度网络中基于能量的混合路由策略. , 2016, 65(24): 248901. doi: 10.7498/aps.65.248901
[6]	舒盼盼, 王伟, 唐明, 尚明生. 花簇分形无标度网络中节点影响力的区分度. , 2015, 64(20): 208901. doi: 10.7498/aps.64.208901
[7]	李世宝, 娄琳琳, 陈瑞祥, 洪利. 一种复杂网络路由策略的普适优化算法. , 2014, 63(2): 028901. doi: 10.7498/aps.63.028901
[8]	刘伟彦, 刘斌. 基于局部路由策略的复杂网络拥塞控制. , 2014, 63(24): 248901. doi: 10.7498/aps.63.248901
[9]	叶纬明, 吕彬彬, 赵琛, 狄增如. 少节点基因调控网络的控制. , 2013, 62(1): 010507. doi: 10.7498/aps.62.010507
[10]	蔡君, 余顺争. 一种有效提高无标度网络负载容量的管理策略. , 2013, 62(5): 058901. doi: 10.7498/aps.62.058901
[11]	刘刚, 李永树. 基于引力场理论的复杂网络路由选择策略研究. , 2012, 61(24): 248901. doi: 10.7498/aps.61.248901
[12]	余旭涛, 徐进, 张在琛. 基于量子远程传态的无线自组织量子通信网络路由协议. , 2012, 61(22): 220303. doi: 10.7498/aps.61.220303
[13]	周小清, 邬云文, 赵晗. 量子隐形传态网络的互联与路由策略. , 2011, 60(4): 040304. doi: 10.7498/aps.60.040304.2
[14]	何敏华, 张端明, 王海艳, 李小刚, 方频捷. 基于无标度网络拓扑结构变化的舆论演化模型. , 2010, 59(8): 5175-5181. doi: 10.7498/aps.59.5175
[15]	濮存来, 裴文江, 缪瑞华, 周思源, 王开. 无标度网络上队列资源分配研究. , 2010, 59(9): 6009-6013. doi: 10.7498/aps.59.6009
[16]	李涛, 裴文江, 王少平. 无标度复杂网络负载传输优化策略. , 2009, 58(9): 5903-5910. doi: 10.7498/aps.58.5903
[17]	王延, 郑志刚. 无标度网络上的传播动力学. , 2009, 58(7): 4421-4425. doi: 10.7498/aps.58.4421
[18]	陈华良, 刘忠信, 陈增强, 袁著祉. 复杂网络的一种加权路由策略研究. , 2009, 58(9): 6068-6073. doi: 10.7498/aps.58.6068
[19]	郭进利. 新节点的边对网络无标度性影响. , 2008, 57(2): 756-761. doi: 10.7498/aps.57.756
[20]	杜海峰, 李树茁, W. F. Marcus, 悦中山, 杨绪松. 小世界网络与无标度网络的社区结构研究. , 2007, 56(12): 6886-6893. doi: 10.7498/aps.56.6886

计量

文章访问数: 9000
PDF下载量: 973
被引次数: 0

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

搜索

留言板