搜索

x

留言板

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

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

基于最短路径长度的空间网络路由

林泓 夏永祥 蒋路茸

引用本文:
Citation:

基于最短路径长度的空间网络路由

林泓, 夏永祥, 蒋路茸

Routing in spatial networks based on shortest path length

Lin Hong, Xia Yong-Xiang, Jiang Lu-Rong
PDF
HTML
导出引用
  • 以通信网、电力网、交通网为代表的很多复杂网络以传输负载为基本功能. 在这些网络中, 网络的吞吐量是衡量网络传输性能的重要指标, 如何提升网络的吞吐量是研究热点之一. 不少研究人员提出了不同的路由算法, 通过调节传输路径来提高网络吞吐量. 但之前的研究很少考虑网络中节点的空间位置. 本文针对空间网络提出了一种高效的路由策略, 通过节点位置得到路径长度; 采用该算法, 负载从源节点沿着最短长度的路径传输到目标节点. 为了检验算法的有效性, 采用网络从自由流状态转变成拥塞状态的相变点Rc来衡量网络的吞吐量. 在匀质和异质空间网络上的仿真表明, 与传统的最少跳数路由策略相比, 本文提出的基于最短路径长度的路由算法能有效提高空间网络的吞吐量.
    In many complex networks, such as communication networks, power grids, and transportation networks, the main task is load transmission from sources to destinations. Therefore, the transmission throughput is a very important indicator to measure the network performance, and improving the throughput becomes one of the hotspots in the research of these complex networks. Many researchers have proposed different routing algorithms to improve the network throughput. However, few of them considered the spatial location of nodes in the network. Indeed, many real-world networks can be modeled by spatial networks, where the spatial location of nodes plays a vital role in determining the structure and dynamic behaviors of such networks. Specifically, when the locations of nodes are considered, each link has a length. And the shortest path may have different meaning. Traditionally, the shortest path indicates the path which passes the least number of links from source to destination, or the least number of hops. However, when the length of link is taken into account, the least number of links does not mean the least summation of link lengths along the path. The latter can be called the shortest path length. To this end, we proposes an efficient routing strategy for spatial networks based on the shortest path length in this work. In order to test the effectiveness of the algorithm, the network throughput ${R}_{\rm c}$ is used, at which the network changes from a free flow state to a congestion state, to measure the performance of the network. Simulations of homogeneous and heterogeneous spatial networks show that compared with the traditional least number of hops routing strategy, the routing algorithm based on the shortest path length proposed in this paper can effectively improve the throughput of the network. The routing algorithm proposed in this paper can be applied to many real-world spatial networks for improving their performances.
      通信作者: 夏永祥, xiayx@hdu.edu.cn
    • 基金项目: 装备综合保障技术重点实验室开放基金和国家自然科学基金(批准号: 61602417)资助的课题
      Corresponding author: Xia Yong-Xiang, xiayx@hdu.edu.cn
    • Funds: Project supported by the Open Fund of Laboratory of Science and Technology on Integrated Logistic Support of China and the National Natural Science Foundation of China (Grant No. 61602417)
    [1]

    Erdös P, Rényi A 1959 Publ. Math. 6 290

    [2]

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

    [3]

    Watts D J, Strogatz S H 1998 Nature 393 440Google Scholar

    [4]

    陈关荣 2008 力学进展 38 653Google Scholar

    Chen G R 2008 Adv. Mech. 38 653Google Scholar

    [5]

    马金龙, 张俊峰, 张冬雯, 张红斌 2021 物理学报 70 078902Google Scholar

    Ma J L, Zhang J F, Zhang D W, Zhang H B 2021 Acta Phys. Sin. 70 078902Google Scholar

    [6]

    于晓 2020 软件工程 23 1Google Scholar

    Yu X 2020 Software Engineering 23 1Google Scholar

    [7]

    任卓明 2020 物理学报 69 048901Google Scholar

    Ren Z M 2020 Acta Phys. Sin. 69 048901Google Scholar

    [8]

    Hearnshaw E J S, Wilson M M J 2013 Int. J. Operat. Product. Manage. 33 442Google Scholar

    [9]

    Chen S Y, Huang W, Cattani C, Altieri G 2012 Math. Probl. Eng. 2012 732698Google Scholar

    [10]

    Tan F, Wu J J, Xia Y X, Tse C K 2014 Phys. Rev. E 89 062813Google Scholar

    [11]

    陈华良, 刘忠信, 陈增强, 袁著祉 2009 物理学报 58 6068Google Scholar

    Chen H L, Liu Z X, Chen Z Q, Yuan Z Z 2009 Acta Phys. Sin. 58 6068Google Scholar

    [12]

    刘伟彦, 刘斌 2014 物理学报 63 248901Google Scholar

    Liu W Y, Liu B 2014 Acta Phys. Sin. 63 248901Google Scholar

    [13]

    赵磊, 周金和 2019 计算机科学 46 137Google Scholar

    Zhao L, Zhou J H 2019 Computer Science 46 137Google Scholar

    [14]

    刘金良 2013 物理学报 62 040503Google Scholar

    Liu J L 2013 Acta Phys. Sin. 62 040503Google Scholar

    [15]

    赵宇红 2019 博士学位论文 (北京: 北京科技大学)

    Zhao Y H 2019 Ph. D. Dissertation (Beijing: University of Science and Technology Beijing) (in Chinese)

    [16]

    李世宝, 娄琳琳, 陈瑞祥, 洪利 2014 物理学报 63 028901Google Scholar

    Li S B, Lou L L, Chen R X, Hong L 2014 Acta Phys. Sin. 63 028901Google Scholar

    [17]

    邵斐, 蒋国平 2011 物理学报 60 078902Google Scholar

    Shao F, Jiang G P 2011 Acta Phys. Sin. 60 078902Google Scholar

    [18]

    Yan G, Zhou T, Hu B, Fu Z Q, Wang B H 2005 Phys. Rev. E 73 046108Google Scholar

    [19]

    Huang W, Chow T W S 2009 Chaos 19 043124Google Scholar

    [20]

    Wang W X, Wang B H, Yin C Y, Xie Y B, Zhou T 2006 Phys. Rev. E 73 026111Google Scholar

    [21]

    Xia Y X, Wang C, Shen H L, Song H N 2020 Physica A 559 125071Google Scholar

    [22]

    Zhang M, Chen S, Sun L, Du W, Cao X 2021 Engineering 7 465Google Scholar

    [23]

    Du W B, Zhou X L, Jusup M, Wang Z 2016 Sci. Rep. 6 19059Google Scholar

    [24]

    Jiang L, Xu Q, Pan H, Dai Y, Tong J 2020 Secur. Commun. Netw. 2020 6513920Google Scholar

    [25]

    Bai G H, Li Y J, Fang Y N, Zhang Y A, Tao J Y 2020 Reliab. Eng. Syst. Saf. 193 106602Google Scholar

    [26]

    Zhao L, Lai Y C, Park K, Ye N 2005 Phys. Rev. E 71 026125Google Scholar

    [27]

    Dall J, Christensen M 2002 Phys. Rev. E 66 016121Google Scholar

    [28]

    Jiang L R, Jin X Y, Xia Y X, Ouyang B, Wu D P, Chen X 2015 Int. J. Distrib. Sens. Netw. 2014 764698Google Scholar

  • 图 1  LAEE演化模型

    Fig. 1.  LAEE evolution model.

    图 2  N = 1500, $ \left\langle{k}\right\rangle $ = 8时的LAEE网络的度分布

    Fig. 2.  Degree distribution of the LAEE network. N = 1500, $ \left\langle{k}\right\rangle $ = 8.

    图 3  节点i与其连通区域内的全部节点建立连接

    Fig. 3.  Node i connects all nodes in its connection area.

    图 4  节点i与其连通范围内的节点以p概率进行连接

    Fig. 4.  Node i connects nodes within its connection range with probability p.

    图 5  N = 1500, $ \left\langle{k}\right\rangle $ = 8时改进的随机几何图的度分布

    Fig. 5.  Degree distribution of the improved random geometric graph. N = 1500, $ \left\langle{k}\right\rangle $= 8.

    图 6  平均度$ \left\langle{k}\right\rangle=4 $时, 不同节点规模下两种路由方式平均路径长度的比较 (a) LAEE演化模型; (b)改进的随机几何图模型. 图中每个点是10次仿真的平均值

    Fig. 6.  With the average degree $ \left\langle{k}\right\rangle=4 $, the average path length under two routing strategies with different node sizes: (a) LAEE evolution model; (b) improved random geometric graph model. Each point is the average of 10 runs.

    图 7  平均度$ \left\langle{k}\right\rangle=4 $时, 不同节点规模下两种路由方式平均跳数的比较 (a) LAEE演化模型; (b)改进的随机几何图模型. 图中每个点是10次仿真的平均值

    Fig. 7.  With the average degree $ \left\langle{k}\right\rangle=4 $, the average number of hops under two routing strategies with different node sizes: (a) LAEE evolution model; (b) improved random geometric graph model. Each point is the average of 10 runs.

    图 8  平均度$ \left\langle{k}\right\rangle=4 $时, 不同节点规模下两种路由方式的网络最大吞吐量$ {R}_{\rm{c}} $的比较 (a) LAEE演化模型; (b)改进的随机几何图模型. 图中每个点是10次仿真的平均值

    Fig. 8.  With the average degree$\left\langle{k}\right\rangle=4$, $ {R}_{\rm{c}} $ under two routing strategies with different node sizes: (a) LAEE evolution model; (b) improved random geometric graph model. Each point is the average of 10 runs.

    图 9  节点数$ N=1000 $时, 不同平均度下两种路由方式平均路径长度的比较 (a) LAEE演化模型; (b)改进的随机几何图模型. 图中每个点是10次仿真的平均值

    Fig. 9.  With N = 1000, the average path length under two routing strategies with different average degrees: (a) LAEE evolution model; (b) improved random geometric graph model. Each point is the average of 10 runs.

    图 10  节点数$ N=1000 $时, 不同平均度下两种路由方式平均跳数的比较 (a) LAEE演化模型; (b)改进的随机几何图模型. 图中每个点是10次仿真的平均值

    Fig. 10.  With N = 1000, the average number of hops under two routing strategies with different average degrees: (a) LAEE evolution model; (b) improved random geometric graph model. Each point is the average of 10 runs.

    图 11  节点数$ N=1000 $时, 不同平均度下两种路由方式的网络最大吞吐量$ {R}_{\rm{c}} $的比较 (a) LAEE演化模型; (b)改进的随机几何图模型. 图中每个点是10次仿真的平均值

    Fig. 11.  With $ N=1000 $, $ {R}_{c} $ under two routing strategies with different average degrees: (a) LAEE evolution model; (b) improved random geometric graph model. Each point is the average of 10 runs.

    图 12  LAEE演化模型中, 节点数N = 1000, $ \left\langle{k}\right\rangle $= 4时的介数分布 (a)最少跳数路由; (b)最短路径长度路由

    Fig. 12.  Betweenness distribution of the LAEE network with N = 1000, $ \left\langle{k}\right\rangle $ = 4: (a) Least number of hops routing strategy; (b) shortest path length routing strategy.

    图 13  改进的随机几何图模型中, 节点数N = 1000, $ \left\langle{k}\right\rangle $ = 4时的介数分布 (a)最少跳数路由; (b)最短路径长度路由

    Fig. 13.  Betweenness distribution of the improved random geometric graph with N = 1000, $ \left\langle{k}\right\rangle $ = 4: (a) Least number of hops routing strategy; (b) shortest path length routing strategy.

  • [1]

    Erdös P, Rényi A 1959 Publ. Math. 6 290

    [2]

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

    [3]

    Watts D J, Strogatz S H 1998 Nature 393 440Google Scholar

    [4]

    陈关荣 2008 力学进展 38 653Google Scholar

    Chen G R 2008 Adv. Mech. 38 653Google Scholar

    [5]

    马金龙, 张俊峰, 张冬雯, 张红斌 2021 物理学报 70 078902Google Scholar

    Ma J L, Zhang J F, Zhang D W, Zhang H B 2021 Acta Phys. Sin. 70 078902Google Scholar

    [6]

    于晓 2020 软件工程 23 1Google Scholar

    Yu X 2020 Software Engineering 23 1Google Scholar

    [7]

    任卓明 2020 物理学报 69 048901Google Scholar

    Ren Z M 2020 Acta Phys. Sin. 69 048901Google Scholar

    [8]

    Hearnshaw E J S, Wilson M M J 2013 Int. J. Operat. Product. Manage. 33 442Google Scholar

    [9]

    Chen S Y, Huang W, Cattani C, Altieri G 2012 Math. Probl. Eng. 2012 732698Google Scholar

    [10]

    Tan F, Wu J J, Xia Y X, Tse C K 2014 Phys. Rev. E 89 062813Google Scholar

    [11]

    陈华良, 刘忠信, 陈增强, 袁著祉 2009 物理学报 58 6068Google Scholar

    Chen H L, Liu Z X, Chen Z Q, Yuan Z Z 2009 Acta Phys. Sin. 58 6068Google Scholar

    [12]

    刘伟彦, 刘斌 2014 物理学报 63 248901Google Scholar

    Liu W Y, Liu B 2014 Acta Phys. Sin. 63 248901Google Scholar

    [13]

    赵磊, 周金和 2019 计算机科学 46 137Google Scholar

    Zhao L, Zhou J H 2019 Computer Science 46 137Google Scholar

    [14]

    刘金良 2013 物理学报 62 040503Google Scholar

    Liu J L 2013 Acta Phys. Sin. 62 040503Google Scholar

    [15]

    赵宇红 2019 博士学位论文 (北京: 北京科技大学)

    Zhao Y H 2019 Ph. D. Dissertation (Beijing: University of Science and Technology Beijing) (in Chinese)

    [16]

    李世宝, 娄琳琳, 陈瑞祥, 洪利 2014 物理学报 63 028901Google Scholar

    Li S B, Lou L L, Chen R X, Hong L 2014 Acta Phys. Sin. 63 028901Google Scholar

    [17]

    邵斐, 蒋国平 2011 物理学报 60 078902Google Scholar

    Shao F, Jiang G P 2011 Acta Phys. Sin. 60 078902Google Scholar

    [18]

    Yan G, Zhou T, Hu B, Fu Z Q, Wang B H 2005 Phys. Rev. E 73 046108Google Scholar

    [19]

    Huang W, Chow T W S 2009 Chaos 19 043124Google Scholar

    [20]

    Wang W X, Wang B H, Yin C Y, Xie Y B, Zhou T 2006 Phys. Rev. E 73 026111Google Scholar

    [21]

    Xia Y X, Wang C, Shen H L, Song H N 2020 Physica A 559 125071Google Scholar

    [22]

    Zhang M, Chen S, Sun L, Du W, Cao X 2021 Engineering 7 465Google Scholar

    [23]

    Du W B, Zhou X L, Jusup M, Wang Z 2016 Sci. Rep. 6 19059Google Scholar

    [24]

    Jiang L, Xu Q, Pan H, Dai Y, Tong J 2020 Secur. Commun. Netw. 2020 6513920Google Scholar

    [25]

    Bai G H, Li Y J, Fang Y N, Zhang Y A, Tao J Y 2020 Reliab. Eng. Syst. Saf. 193 106602Google Scholar

    [26]

    Zhao L, Lai Y C, Park K, Ye N 2005 Phys. Rev. E 71 026125Google Scholar

    [27]

    Dall J, Christensen M 2002 Phys. Rev. E 66 016121Google Scholar

    [28]

    Jiang L R, Jin X Y, Xia Y X, Ouyang B, Wu D P, Chen X 2015 Int. J. Distrib. Sens. Netw. 2014 764698Google Scholar

  • [1] 马金龙, 张俊峰, 张冬雯, 张红斌. 基于通信序列熵的复杂网络传输容量. 物理学报, 2021, 70(7): 078902. doi: 10.7498/aps.70.20201300
    [2] 蒋文君, 刘润然, 范天龙, 刘霜霜, 吕琳媛. 多层网络级联失效的预防和恢复策略概述. 物理学报, 2020, 69(8): 088904. doi: 10.7498/aps.69.20192000
    [3] 聂敏, 刘广腾, 杨光, 裴昌幸. 基于最少中继节点约束的量子VoIP路由优化策略. 物理学报, 2016, 65(12): 120302. doi: 10.7498/aps.65.120302
    [4] 杨先霞, 濮存来, 许忠奇, 陈荣斌, 吴洁鑫, 李伦波. 无标度网络中基于能量的混合路由策略. 物理学报, 2016, 65(24): 248901. doi: 10.7498/aps.65.248901
    [5] 刘伟彦, 刘斌. 基于局部路由策略的复杂网络拥塞控制. 物理学报, 2014, 63(24): 248901. doi: 10.7498/aps.63.248901
    [6] 李世宝, 娄琳琳, 陈瑞祥, 洪利. 一种复杂网络路由策略的普适优化算法. 物理学报, 2014, 63(2): 028901. doi: 10.7498/aps.63.028901
    [7] 刘晓慧, 聂敏, 裴昌幸. 量子无线广域网构建与路由策略. 物理学报, 2013, 62(20): 200304. doi: 10.7498/aps.62.200304
    [8] 余旭涛, 徐进, 张在琛. 基于量子远程传态的无线自组织量子通信网络路由协议. 物理学报, 2012, 61(22): 220303. doi: 10.7498/aps.61.220303
    [9] 黎勇, 钭斐玲, 樊瑛, 狄增如. 二维有限能量约束下最优导航问题的理论分析. 物理学报, 2012, 61(22): 228902. doi: 10.7498/aps.61.228902
    [10] 钭斐玲, 胡延庆, 黎勇, 樊瑛, 狄增如. 空间网络上的随机游走. 物理学报, 2012, 61(17): 178901. doi: 10.7498/aps.61.178901
    [11] 王丹, 金小峥. 可调聚类系数加权无标度网络建模及其拥塞问题研究. 物理学报, 2012, 61(22): 228901. doi: 10.7498/aps.61.228901
    [12] 刘刚, 李永树. 基于引力约束的复杂网络拥塞问题研究. 物理学报, 2012, 61(10): 108901. doi: 10.7498/aps.61.108901
    [13] 刘刚, 李永树. 基于引力场理论的复杂网络路由选择策略研究. 物理学报, 2012, 61(24): 248901. doi: 10.7498/aps.61.248901
    [14] 周小清, 邬云文, 赵晗. 量子隐形传态网络的互联与路由策略. 物理学报, 2011, 60(4): 040304. doi: 10.7498/aps.60.040304.2
    [15] 王开, 周思源, 张毅锋, 裴文江, 刘茜. 一类基于随机行走机理的优化路由改进策略. 物理学报, 2011, 60(11): 118903. doi: 10.7498/aps.60.118903
    [16] 濮存来, 裴文江. 一种应用于含权无标度网络的全局路由算法. 物理学报, 2010, 59(6): 3841-3845. doi: 10.7498/aps.59.3841
    [17] 李涛, 裴文江, 王少平. 无标度复杂网络负载传输优化策略. 物理学报, 2009, 58(9): 5903-5910. doi: 10.7498/aps.58.5903
    [18] 钱江海, 韩定定. 基于预期流优化的空间网络引力模型. 物理学报, 2009, 58(5): 3028-3033. doi: 10.7498/aps.58.3028
    [19] 王丹, 于灏, 井元伟, 姜囡, 张嗣瀛. 基于感知流量算法的复杂网络拥塞问题研究. 物理学报, 2009, 58(10): 6802-6808. doi: 10.7498/aps.58.6802
    [20] 陈华良, 刘忠信, 陈增强, 袁著祉. 复杂网络的一种加权路由策略研究. 物理学报, 2009, 58(9): 6068-6073. doi: 10.7498/aps.58.6068
计量
  • 文章访问数:  3057
  • PDF下载量:  86
  • 被引次数: 0
出版历程
  • 收稿日期:  2021-09-01
  • 修回日期:  2021-11-23
  • 上网日期:  2022-01-26
  • 刊出日期:  2022-03-20

/

返回文章
返回