搜索

x

留言板

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

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

基于引力场理论的复杂网络路由选择策略研究

刘刚 李永树

引用本文:
Citation:

基于引力场理论的复杂网络路由选择策略研究

刘刚, 李永树

Routing strategy for complex networks based on gravitation field theory

Liu Gang, Li Yong-Shu
PDF
导出引用
  • 利用引力场理论对网络传输过程中节点激发的引力场进行了描述, 建立了节点的引力场方程, 引入α 和γ 两个参数, 用于调节数据传输对节点畅通程度、节点传输能力和路径长度的依赖程度. 基于节点的引力场, 提出了一种高效的路由选择算法, 该算法下数据包将沿着所受路径引力最大的方向进行传递. 为检验算法的有效性, 引入有序状态参数η, 利用其由自由流到拥塞态的指标流量相变值度量网络的吞吐量, 并通过节点的介中心值B分析网络的传输性能和拥塞分布. 针对算法在不同 α, γ取值条件下的路由情况进行了仿真. 仿真结果显示, 与传统最短路由算法相比, 本文算法将网络传输能力提高了数倍, 有效地均衡了节点的介中心值分布, 传输路径平均长度Lavg> 随负载量R的增加表现出先增后减的变化趋势, 而参数α与γ 值的变化对网络传输能力几乎没有影响, 说明本文路由算法的性能不依赖于α与γ, 对于可行域内任意的α 与γ, 算法都能保证网络传输能力近似相等.
    Using the theory of gravitational field, we study the gravitational field induced by the node in the process of the network transmission, establish the gravitational filed equation, and define two parameters α and γ for adjusting the dependencs of transmission data on the unblocked degree of node, the transmission capacity of node and the path length. Based on the gravitational field of node, an efficient routing strategy is proposed, and the package will be transferred along the route with maximum gravitation. In order to characterize the efficiency of the method, we introduce an order parameter η to measure the throughput of the network by the critical value of phase transition from free state to jammed state, and use the node betweenness centrality B to test the transmission efficiency of network and the congestion distribution. We simulate the network transmission efficiencies under different values of α and γ. Simulation results show that compared with the traditional shortest routing strategy, our routing strategy improves the network capacity several times, and effectively balances the distribution of the betweenness centrality of nodes, and the average path length Lavg> shows a trend from ascent to descent with the increase of load amount R, and the change of the parameters α and γ nearly have no effect on the network transmission capacity, which suggests the efficiency of our routing strategy is independent of α and γ, the network capacities are approximately equal for any values of α and γ in the feasible region.
    • 基金项目: 高等学校博士学科点专项科研基金(批准号: 20100184110019)、2013年西南交通大学博士研究生创新基金和中央高校基本科研业务费专项资金资助的课题.
    • Funds: Project supported by the Specialized Research Fund for the Doctoral Program of Higher Education of China (Grant No. 20100184110019), the 2013 Doctoral Innovation Funds of Southwest Jiaotong University and the Fundamental Research Funds for the Central Universities.
    [1]

    Newman M E J 2003 SIAM Review 45 167

    [2]

    Boccaletti S, Latora V, Moreno Y, Chavez M, Hwang D U 2006 Physics Reports 424 175

    [3]

    Mitchell M 2006 Artificial Intelligence 170 1194

    [4]

    Newman M E J 2010 Networks: An Introduction (Volume 1) (Oxford: Oxford University Press) p11-20

    [5]

    Wu J, Barahona M, Tan Y J, Deng H Z 2010 Chine. Phys. Lett. 27 078902

    [6]

    Shao Z G 2010 Appl. Phys. Lett. 96 073703

    [7]

    Toda A A 2011 Phys. Rev. E 83 046122

    [8]

    Zager L, Verghese G 2008 Complexity 14 12

    [9]

    Töenjes R, Masuda N, Kori H 2010 Chaos 20 033108

    [10]

    Leyva I, Navas A, Nadal I S, Buldú J M, Almendral J A, Boccaletti S 2011 Phys. Rev. E 84 065101

    [11]

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

    [12]

    Noh J D, Rieger H 2004 Phys. Rev. Lett. 92 118701

    [13]

    Ramascc J J, Lama M S L, Eduardo L, Boettcher S 2010 Phys. Rev. E 82 036119

    [14]

    Guimerá R, Díaz-Guilera A, Vega-Redondo F, Cabrales A, Arenas A 2002 Phys. Rev. Lett. 89 248701

    [15]

    Danila B, Yu Y, Marsh J A, Bassler K E 2007 Chaos 17 026102

    [16]

    Kawamoto H, Igarashi A 2012 Physica A 391 895

    [17]

    Qian J H, Han D D 2009 Acta Phys. Sin. 58 3028 (in Chinese) [钱江海, 韩定定 2009 物流学报 58 3028]

    [18]

    Liu G, Li Y S 2012 Acta Phys. Sin. 61 108901 (in Chinese) [刘刚, 李永树 2012 物理学报 61 108901]

    [19]

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

    [20]

    Crucitti P, Latora V, Porta S 2006 Chaos 16 015113

    [21]

    Freeman L G 1977 Sociometry 40 35

    [22]

    Li Q Q, Zeng Z, Yang B S, Li B J 2010 Geomatics and Information Science of Wuhan University 35 37 (in Chinese) [李清泉, 曾喆, 杨必胜, 李必军 2010 武汉大学学报(信息科学版) 35 37]

    [23]

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

    [24]

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

    [25]

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

  • [1]

    Newman M E J 2003 SIAM Review 45 167

    [2]

    Boccaletti S, Latora V, Moreno Y, Chavez M, Hwang D U 2006 Physics Reports 424 175

    [3]

    Mitchell M 2006 Artificial Intelligence 170 1194

    [4]

    Newman M E J 2010 Networks: An Introduction (Volume 1) (Oxford: Oxford University Press) p11-20

    [5]

    Wu J, Barahona M, Tan Y J, Deng H Z 2010 Chine. Phys. Lett. 27 078902

    [6]

    Shao Z G 2010 Appl. Phys. Lett. 96 073703

    [7]

    Toda A A 2011 Phys. Rev. E 83 046122

    [8]

    Zager L, Verghese G 2008 Complexity 14 12

    [9]

    Töenjes R, Masuda N, Kori H 2010 Chaos 20 033108

    [10]

    Leyva I, Navas A, Nadal I S, Buldú J M, Almendral J A, Boccaletti S 2011 Phys. Rev. E 84 065101

    [11]

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

    [12]

    Noh J D, Rieger H 2004 Phys. Rev. Lett. 92 118701

    [13]

    Ramascc J J, Lama M S L, Eduardo L, Boettcher S 2010 Phys. Rev. E 82 036119

    [14]

    Guimerá R, Díaz-Guilera A, Vega-Redondo F, Cabrales A, Arenas A 2002 Phys. Rev. Lett. 89 248701

    [15]

    Danila B, Yu Y, Marsh J A, Bassler K E 2007 Chaos 17 026102

    [16]

    Kawamoto H, Igarashi A 2012 Physica A 391 895

    [17]

    Qian J H, Han D D 2009 Acta Phys. Sin. 58 3028 (in Chinese) [钱江海, 韩定定 2009 物流学报 58 3028]

    [18]

    Liu G, Li Y S 2012 Acta Phys. Sin. 61 108901 (in Chinese) [刘刚, 李永树 2012 物理学报 61 108901]

    [19]

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

    [20]

    Crucitti P, Latora V, Porta S 2006 Chaos 16 015113

    [21]

    Freeman L G 1977 Sociometry 40 35

    [22]

    Li Q Q, Zeng Z, Yang B S, Li B J 2010 Geomatics and Information Science of Wuhan University 35 37 (in Chinese) [李清泉, 曾喆, 杨必胜, 李必军 2010 武汉大学学报(信息科学版) 35 37]

    [23]

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

    [24]

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

    [25]

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

  • [1] 阮逸润, 老松杨, 汤俊, 白亮, 郭延明. 基于引力方法的复杂网络节点重要度评估方法. 物理学报, 2022, 71(17): 176401. doi: 10.7498/aps.71.20220565
    [2] 林泓, 夏永祥, 蒋路茸. 基于最短路径长度的空间网络路由. 物理学报, 2022, 71(6): 068901. doi: 10.7498/aps.71.20211621
    [3] 马金龙, 张俊峰, 张冬雯, 张红斌. 基于通信序列熵的复杂网络传输容量. 物理学报, 2021, 70(7): 078902. doi: 10.7498/aps.70.20201300
    [4] 蒋文君, 刘润然, 范天龙, 刘霜霜, 吕琳媛. 多层网络级联失效的预防和恢复策略概述. 物理学报, 2020, 69(8): 088904. doi: 10.7498/aps.69.20192000
    [5] 杨先霞, 濮存来, 许忠奇, 陈荣斌, 吴洁鑫, 李伦波. 无标度网络中基于能量的混合路由策略. 物理学报, 2016, 65(24): 248901. doi: 10.7498/aps.65.248901
    [6] 刘伟彦, 刘斌. 基于局部路由策略的复杂网络拥塞控制. 物理学报, 2014, 63(24): 248901. doi: 10.7498/aps.63.248901
    [7] 李世宝, 娄琳琳, 陈瑞祥, 洪利. 一种复杂网络路由策略的普适优化算法. 物理学报, 2014, 63(2): 028901. doi: 10.7498/aps.63.028901
    [8] 蔡君, 余顺争. 一种有效提高无标度网络负载容量的管理策略. 物理学报, 2013, 62(5): 058901. doi: 10.7498/aps.62.058901
    [9] 王丹, 金小峥. 可调聚类系数加权无标度网络建模及其拥塞问题研究 . 物理学报, 2012, 61(22): 228901. doi: 10.7498/aps.61.228901
    [10] 刘刚, 李永树. 基于引力约束的复杂网络拥塞问题研究. 物理学报, 2012, 61(10): 108901. doi: 10.7498/aps.61.108901
    [11] 姜志宏, 王晖, 高超. 一种基于随机行走和策略连接的网络演化模型. 物理学报, 2011, 60(5): 058903. doi: 10.7498/aps.60.058903
    [12] 王开, 周思源, 张毅锋, 裴文江, 刘茜. 一类基于随机行走机理的优化路由改进策略. 物理学报, 2011, 60(11): 118903. doi: 10.7498/aps.60.118903
    [13] 李涛, 裴文江, 王少平. 无标度复杂网络负载传输优化策略. 物理学报, 2009, 58(9): 5903-5910. doi: 10.7498/aps.58.5903
    [14] 任继荣, 朱辉. 计算光在引力场中偏折的新方法. 物理学报, 2009, 58(1): 690-694. doi: 10.7498/aps.58.690
    [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] 许 丹, 李 翔, 汪小帆. 复杂网络病毒传播的局域控制研究. 物理学报, 2007, 56(3): 1313-1317. doi: 10.7498/aps.56.1313
    [18] 林 海, 吴晨旭. 基于遗传算法的重复囚徒困境博弈策略在复杂网络中的演化. 物理学报, 2007, 56(8): 4313-4318. doi: 10.7498/aps.56.4313
    [19] 孙鸣超. 起源于引力场的Vaidya-Bonner-de Sitter黑洞的量子熵. 物理学报, 2003, 52(6): 1350-1353. doi: 10.7498/aps.52.1350
    [20] 苏成悦. 均匀弱磁场中的Kasuya双荷外部引力场. 物理学报, 2001, 50(11): 2089-2091. doi: 10.7498/aps.50.2089
计量
  • 文章访问数:  6288
  • PDF下载量:  960
  • 被引次数: 0
出版历程
  • 收稿日期:  2012-05-23
  • 修回日期:  2012-06-20
  • 刊出日期:  2012-12-05

基于引力场理论的复杂网络路由选择策略研究

  • 1. 西南交通大学地球科学与环境工程学院, 成都 610031
    基金项目: 高等学校博士学科点专项科研基金(批准号: 20100184110019)、2013年西南交通大学博士研究生创新基金和中央高校基本科研业务费专项资金资助的课题.

摘要: 利用引力场理论对网络传输过程中节点激发的引力场进行了描述, 建立了节点的引力场方程, 引入α 和γ 两个参数, 用于调节数据传输对节点畅通程度、节点传输能力和路径长度的依赖程度. 基于节点的引力场, 提出了一种高效的路由选择算法, 该算法下数据包将沿着所受路径引力最大的方向进行传递. 为检验算法的有效性, 引入有序状态参数η, 利用其由自由流到拥塞态的指标流量相变值度量网络的吞吐量, 并通过节点的介中心值B分析网络的传输性能和拥塞分布. 针对算法在不同 α, γ取值条件下的路由情况进行了仿真. 仿真结果显示, 与传统最短路由算法相比, 本文算法将网络传输能力提高了数倍, 有效地均衡了节点的介中心值分布, 传输路径平均长度Lavg> 随负载量R的增加表现出先增后减的变化趋势, 而参数α与γ 值的变化对网络传输能力几乎没有影响, 说明本文路由算法的性能不依赖于α与γ, 对于可行域内任意的α 与γ, 算法都能保证网络传输能力近似相等.

English Abstract

参考文献 (25)

目录

    /

    返回文章
    返回