搜索

x

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

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

基于引力约束的复杂网络拥塞问题研究

刘刚 李永树

引用本文:
Citation:

基于引力约束的复杂网络拥塞问题研究

刘刚, 李永树

Study on the congestion phenomena in complex network based on gravity constraint

Liu Gang, Li Yong-Shu
PDF
导出引用
  • 如何在保证网络传输效率的同时提高网络的吞吐量是目前研究的主要问题. 通过研究节点对数据包传递过程的引力作用,提出了一种具有引力约束的路由算法. 为检验算法的有效性,通过引入一个状态参数H, 利用由稳态到拥塞状态的指标流量相变值来度量网络的吞吐量, 同时利用数据包的最大传输时间〈Tmax〉与平均传输时间〈Tavg〉来分析网络的传输效率. 针对算法在不同引力约束条件下的路由情况进行了仿真.仿真结果表明, 若数据传递过程只考虑路径长度最短,则会导致网络吞吐量较低且流量分布极不均匀; 若只顾及等待时间最短,会导致传输路径过度迂回且大部分节点都会陷入拥塞状态; 同时考虑路径长度和等待时间的引力作用并选取适当引力的节点进行传递, 可以显著提高网络吞吐量并缓解网络的拥塞程度.
    How to guarantee the transport efficiency of the network and how to improve the network capacity are the main subject of the study presently. We investigate the gravity of the nodes to the transfer of data packets, and propose a routing method based on gravity constraint. In order to characterize the efficiency of the method, we introduce an order parameter H to measure the throughput of the network by a critical value of phase transition from free state to jammed state, and use the maximum travel time 〈Tmax〉 and the average travel time 〈Tavg〉 to test the transmission efficiency of the network. We simulate the network capacity under three different gravity constraints. Simulation results show that when only considering the path with shortest length, the network capacity is very small and the distribution of flow is extremely uneven; when only considering minimum waiting time, the excessive circuitous transfer of data packets occurs and most of the nodes will be in congestion state; when considering the gravity of path length and waiting time simultaneously and choosing a node with reasonable gravity, the network capacity will be improved greatly and the congestion level will be relieved to some extent.
    • 基金项目: 高等学校博士学科点专项科研基金(批准号: 20100184110019)资助的课题.
    • Funds: Project supported by the Specialized Research Fund for the Doctoral Program of Higher Education of China (Grant No. 20100184110019).
    [1]

    Newman M E J 2003 SIAM Rev. 45 167

    [2]

    Boccaletti S, Latora V, Moreno Y, Chavez M, Hwang D U 2006 Phys. Rep. 424 175

    [3]

    Melanie M 2006 Artificial Intelligence 170 1194

    [4]

    Albert R, Barabási A L 2002 Rev. Mod. Phys. 74 47

    [5]

    Strogatz S H 2001 Nature 410 268

    [6]

    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]

    [7]

    Lin H, Wu C X 2007 Acta Phys. Sin. 56 4313 (in Chinese) [林海, 吴晨旭 2007 物理学报 56 4313]

    [8]

    Szabo G, Szolnoki A, Vukov J 2009 Eur. Phys. Lett. 87 18007

    [9]

    Gómez J G, Campillo M, Floríe1 L M, Moreno Y 2007 Phys. Rev. Lett. 98 1081

    [10]

    Chowdhury D 2006 Physica A 372 84

    [11]

    Koo J H, Ji D H, Won S C 2010 Appl. Math. Comput. 217 3916

    [12]

    Dobson I, Carreras B A, Newman D E 2005 Prob. Eng. Inform. Sci. 19 15

    [13]

    Hu K, Hu T, Tang Y 2010 Chin. Phys. B 19 080206

    [14]

    Simonsen I, Buzna L, Peters K 2008 Phys. Rev. Lett. 100 2187

    [15]

    Paster S R, Vespingnani A 2001 Phys. Rev. Lett. 86 3200

    [16]

    Zager L, Verghese G 2009 Complexity 14 12

    [17]

    Lancic A, Antulov F N, Sikic M 2011 Physica A 390 65

    [18]

    Toenjes R, Masuda N, Kori H 2010 Chaos 20 033108

    [19]

    Tu L L 2011 Chin. Phys. B 20 030504

    [20]

    Yang J Z, Zhang M 2005 Chin. Phys. Lett. 22 2183

    [21]

    Daniele D M, Luca D A, Ginestra B, Matteo M 2009 Phys. Rev. E 79 015101

    [22]

    Pu C L, Pei W J 2010 Acta Phys. Sin. 59 3841 (in Chinese) [濮存来, 裴文江 2010 物理学报 59 3841]

    [23]

    Yan G, Zhou T, Hu B, Fu Z Q 2006 Phys. Rev. E 73 046108

    [24]

    Noh J D 2004 Phys. Rev. Lett. 92 11

    [25]

    Yang S J 2005 Phys. Rev. E 71 016107

    [26]

    Zhao L, Al-Dubai A Y, Min G Y 2011 Simul. Model. Prac. Theory 19 1415

    [27]

    Chen H L, Liu Z X, Chen Z Q, Yuan Z Z 2009 Acta Phys. Sin. 58 6068 (in Chinese) [陈华良, 刘忠信, 陈增强, 袁著祉 2009 物理学报 58 6068]

    [28]

    Echenique P, Gomez-Gardenes J, Moreno Y 2004 Phys. Rev. E 70 056105

    [29]

    Wang D, Yu H, Jing Y W, Jiang N, Zhang S Y 2009 Acta Phys. Sin. 58 6802 (in Chinese) [王丹, 于灏, 井元伟, 姜囡, 张嗣瀛 2009 物理学报 58 6802]

    [30]

    Barabási A L, Albert R 1999 Science 286 509

    [31]

    Arenas A, Díaz-Guilera A, Guimerá R 2001 Phys. Rev. Lett. 86 3196

    [32]

    Danila B, Sun Y D, Bassler K E 2009 Phys. Rev. E 80 066116

  • [1]

    Newman M E J 2003 SIAM Rev. 45 167

    [2]

    Boccaletti S, Latora V, Moreno Y, Chavez M, Hwang D U 2006 Phys. Rep. 424 175

    [3]

    Melanie M 2006 Artificial Intelligence 170 1194

    [4]

    Albert R, Barabási A L 2002 Rev. Mod. Phys. 74 47

    [5]

    Strogatz S H 2001 Nature 410 268

    [6]

    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]

    [7]

    Lin H, Wu C X 2007 Acta Phys. Sin. 56 4313 (in Chinese) [林海, 吴晨旭 2007 物理学报 56 4313]

    [8]

    Szabo G, Szolnoki A, Vukov J 2009 Eur. Phys. Lett. 87 18007

    [9]

    Gómez J G, Campillo M, Floríe1 L M, Moreno Y 2007 Phys. Rev. Lett. 98 1081

    [10]

    Chowdhury D 2006 Physica A 372 84

    [11]

    Koo J H, Ji D H, Won S C 2010 Appl. Math. Comput. 217 3916

    [12]

    Dobson I, Carreras B A, Newman D E 2005 Prob. Eng. Inform. Sci. 19 15

    [13]

    Hu K, Hu T, Tang Y 2010 Chin. Phys. B 19 080206

    [14]

    Simonsen I, Buzna L, Peters K 2008 Phys. Rev. Lett. 100 2187

    [15]

    Paster S R, Vespingnani A 2001 Phys. Rev. Lett. 86 3200

    [16]

    Zager L, Verghese G 2009 Complexity 14 12

    [17]

    Lancic A, Antulov F N, Sikic M 2011 Physica A 390 65

    [18]

    Toenjes R, Masuda N, Kori H 2010 Chaos 20 033108

    [19]

    Tu L L 2011 Chin. Phys. B 20 030504

    [20]

    Yang J Z, Zhang M 2005 Chin. Phys. Lett. 22 2183

    [21]

    Daniele D M, Luca D A, Ginestra B, Matteo M 2009 Phys. Rev. E 79 015101

    [22]

    Pu C L, Pei W J 2010 Acta Phys. Sin. 59 3841 (in Chinese) [濮存来, 裴文江 2010 物理学报 59 3841]

    [23]

    Yan G, Zhou T, Hu B, Fu Z Q 2006 Phys. Rev. E 73 046108

    [24]

    Noh J D 2004 Phys. Rev. Lett. 92 11

    [25]

    Yang S J 2005 Phys. Rev. E 71 016107

    [26]

    Zhao L, Al-Dubai A Y, Min G Y 2011 Simul. Model. Prac. Theory 19 1415

    [27]

    Chen H L, Liu Z X, Chen Z Q, Yuan Z Z 2009 Acta Phys. Sin. 58 6068 (in Chinese) [陈华良, 刘忠信, 陈增强, 袁著祉 2009 物理学报 58 6068]

    [28]

    Echenique P, Gomez-Gardenes J, Moreno Y 2004 Phys. Rev. E 70 056105

    [29]

    Wang D, Yu H, Jing Y W, Jiang N, Zhang S Y 2009 Acta Phys. Sin. 58 6802 (in Chinese) [王丹, 于灏, 井元伟, 姜囡, 张嗣瀛 2009 物理学报 58 6802]

    [30]

    Barabási A L, Albert R 1999 Science 286 509

    [31]

    Arenas A, Díaz-Guilera A, Guimerá R 2001 Phys. Rev. Lett. 86 3196

    [32]

    Danila B, Sun Y D, Bassler K E 2009 Phys. Rev. E 80 066116

  • [1] 林泓, 夏永祥, 蒋路茸. 基于最短路径长度的空间网络路由. 物理学报, 2022, 71(6): 068901. doi: 10.7498/aps.71.20211621
    [2] 阮逸润, 老松杨, 汤俊, 白亮, 郭延明. 基于引力方法的复杂网络节点重要度评估方法. 物理学报, 2022, 71(17): 176401. doi: 10.7498/aps.71.20220565
    [3] 马金龙, 张俊峰, 张冬雯, 张红斌. 基于通信序列熵的复杂网络传输容量. 物理学报, 2021, 70(7): 078902. doi: 10.7498/aps.70.20201300
    [4] 李世宝, 娄琳琳, 陈瑞祥, 洪利. 一种复杂网络路由策略的普适优化算法. 物理学报, 2014, 63(2): 028901. doi: 10.7498/aps.63.028901
    [5] 刘伟彦, 刘斌. 基于局部路由策略的复杂网络拥塞控制. 物理学报, 2014, 63(24): 248901. doi: 10.7498/aps.63.248901
    [6] 李雨珊, 吕翎, 刘烨, 刘硕, 闫兵兵, 常欢, 周佳楠. 复杂网络时空混沌同步的Backstepping设计. 物理学报, 2013, 62(2): 020513. doi: 10.7498/aps.62.020513
    [7] 周漩, 张凤鸣, 周卫平, 邹伟, 杨帆. 利用节点效率评估复杂网络功能鲁棒性. 物理学报, 2012, 61(19): 190201. doi: 10.7498/aps.61.190201
    [8] 郝崇清, 王江, 邓斌, 魏熙乐. 基于稀疏贝叶斯学习的复杂网络拓扑估计. 物理学报, 2012, 61(14): 148901. doi: 10.7498/aps.61.148901
    [9] 吕翎, 柳爽, 张新, 朱佳博, 沈娜, 商锦玉. 节点结构互异的复杂网络的时空混沌反同步. 物理学报, 2012, 61(9): 090504. doi: 10.7498/aps.61.090504
    [10] 周漩, 张凤鸣, 李克武, 惠晓滨, 吴虎胜. 利用重要度评价矩阵确定复杂网络关键节点. 物理学报, 2012, 61(5): 050201. doi: 10.7498/aps.61.050201
    [11] 王丹, 金小峥. 可调聚类系数加权无标度网络建模及其拥塞问题研究 . 物理学报, 2012, 61(22): 228901. doi: 10.7498/aps.61.228901
    [12] 刘刚, 李永树. 基于引力场理论的复杂网络路由选择策略研究. 物理学报, 2012, 61(24): 248901. doi: 10.7498/aps.61.248901
    [13] 崔爱香, 傅彦, 尚明生, 陈端兵, 周涛. 复杂网络局部结构的涌现:共同邻居驱动网络演化. 物理学报, 2011, 60(3): 038901. doi: 10.7498/aps.60.038901
    [14] 李涛, 裴文江, 王少平. 无标度复杂网络负载传输优化策略. 物理学报, 2009, 58(9): 5903-5910. doi: 10.7498/aps.58.5903
    [15] 吕翎, 张超. 一类节点结构互异的复杂网络的混沌同步. 物理学报, 2009, 58(3): 1462-1466. doi: 10.7498/aps.58.1462
    [16] 钱江海, 韩定定. 基于预期流优化的空间网络引力模型. 物理学报, 2009, 58(5): 3028-3033. doi: 10.7498/aps.58.3028
    [17] 王丹, 于灏, 井元伟, 姜囡, 张嗣瀛. 基于感知流量算法的复杂网络拥塞问题研究. 物理学报, 2009, 58(10): 6802-6808. doi: 10.7498/aps.58.6802
    [18] 陈华良, 刘忠信, 陈增强, 袁著祉. 复杂网络的一种加权路由策略研究. 物理学报, 2009, 58(9): 6068-6073. doi: 10.7498/aps.58.6068
    [19] 许 丹, 李 翔, 汪小帆. 复杂网络病毒传播的局域控制研究. 物理学报, 2007, 56(3): 1313-1317. doi: 10.7498/aps.56.1313
    [20] 李 季, 汪秉宏, 蒋品群, 周 涛, 王文旭. 节点数加速增长的复杂网络生长模型. 物理学报, 2006, 55(8): 4051-4057. doi: 10.7498/aps.55.4051
计量
  • 文章访问数:  4738
  • PDF下载量:  628
  • 被引次数: 0
出版历程
  • 收稿日期:  2011-09-05
  • 修回日期:  2012-05-28
  • 刊出日期:  2012-05-05

基于引力约束的复杂网络拥塞问题研究

  • 1. 西南交通大学地球科学与环境工程学院, 成都 610031
    基金项目: 高等学校博士学科点专项科研基金(批准号: 20100184110019)资助的课题.

摘要: 如何在保证网络传输效率的同时提高网络的吞吐量是目前研究的主要问题. 通过研究节点对数据包传递过程的引力作用,提出了一种具有引力约束的路由算法. 为检验算法的有效性,通过引入一个状态参数H, 利用由稳态到拥塞状态的指标流量相变值来度量网络的吞吐量, 同时利用数据包的最大传输时间〈Tmax〉与平均传输时间〈Tavg〉来分析网络的传输效率. 针对算法在不同引力约束条件下的路由情况进行了仿真.仿真结果表明, 若数据传递过程只考虑路径长度最短,则会导致网络吞吐量较低且流量分布极不均匀; 若只顾及等待时间最短,会导致传输路径过度迂回且大部分节点都会陷入拥塞状态; 同时考虑路径长度和等待时间的引力作用并选取适当引力的节点进行传递, 可以显著提高网络吞吐量并缓解网络的拥塞程度.

English Abstract

参考文献 (32)

目录

    /

    返回文章
    返回