下载:
-
20世纪50年代末, Erdös与Rényi[1]提出的ER随机图模型开辟了复杂网络领域研究的先河. 直至20世纪末, 小世界网络[2]的提出与无标度特性[3]的发现, 吸引了一大批科学家参与到复杂网络结构与动力学的研究之中. 近十年来, 复杂网络成为生物技术、移动通信、交通运输、社会关系等多个不同领域的研究热点[4-8], 受到物理、数学、计算机、通信、社会学等领域学者的广泛关注. 实际生活中的Internet、移动通信网络、交通运输网络、电力网等都可以被抽象成复杂网络进行研究分析, 而这类网络的传输性能与人们的生活息息相关. 如何提升网络的传输性能已经成为复杂网络领域研究的热门课题之一. 网络传输能力主要取决于网络的拓扑结构与路由方式, 针对这两方面的影响因素, 一般有“硬策略”和“软策略”两种优化方式[9], 即优化网络拓扑结构与优化路由方式. 而在实际生活中, 不少网络的结构已经固定, 修改其结构需要承担高昂的成本. 因此, 采用更加高效的路由策略来提升网络传输性能更具有可行性.
传统意义上的最短路径的策略是目前应用较为广泛的一种路由方式, 即负载从节点A通过最少的边数传输到节点B, 但是这种方式很容易在一些度值较大的节点处造成拥塞现象[10]. 因此, 不少研究人员提出了更加高效的路由策略[10-20]. Yan等[18]提出了一种“the efficient path”的路由策略, 定义任意两点i和j之间的路径为
$L(P(i\to j):\beta )= $ $ \displaystyle \sum\nolimits _{i=0}^{n-1}k{({x}_{i})}^{\beta }$ , 以$ {\rm{m}\rm{i}\rm{n}}\left(L\right) $ 为目标选择路径, 通过绕开度值较大的节点来减少发生拥塞的可能, 大大提升网络的传输性能. Huang和Chow[19]提出了一种带记忆信息的路由策略, 节点记录负载的传输来源, 避免出现回溯现象, 使得负载在两个不同节点之间来回传输的机会大大减少, 有效地提高网络吞吐量. Wang等[20]提出了一种流量模型, 负载从节点a传输到节点b, 若节点a与b之间有边连接, 则负载可直接传输至目标节点b; 否则, 将以${\varPi }_{i}= $ $ \displaystyle {{k}_{i}^{\alpha }}\Big/{\displaystyle\sum\nolimits _{j}{k}_{j}^{\alpha }}$ 的概率传输至a的某个邻居节点i.之前提出的各种路由策略主要是基于复杂网络的拓扑, 很少有研究考虑节点的空间位置. 而事实上, 由于空间网络中的节点与节点之间的连接受到实际位置的约束, 与一般的复杂网络在拓扑结构和鲁棒性[21]等方面具有一定的差异性. 在实际生活中, 如航空网络[22]、交通网络[23]、无线传感器网络[24]、无人机网络[25]等都受到空间位置的限制. 由于这类空间网络的特殊性, 对其路由策略的研究具有很强的理论价值和现实意义.
本文提出一种基于最短路径长度的空间路由方式, 即负载从源节点沿着最短路径长度的方向传输到目标节点. Zhao等[26]在2005年发表的文章中指出, 不同结构的网络出现拥塞现象的性能不相同. 因此, 本文考虑了空间匀质网络和异质网络两种情况, 在随机几何图[27]和LAEE (local-area and energy-efficient evolution)模型[28]上进行了仿真模拟. 仿真结果表明, 本文提出的路由策略能够有效提升网络的传输性能, 减少拥塞现象的发生.
-
研究发现, 很多实际网络都遵循节点的度值呈幂律分布的无标度特性, 即
$ P\left(k\right)\propto {k}^{-\gamma } $ , 其中k表示节点的度, γ为常数. 为了探究本文提出的路由算法在异质网络上的适用性, 采用Jiang等[28]提出的具有无标度特性的空间LAEE演化模型.该网络的拓扑演化主要分为两个阶段. 在第1阶段, 将N个节点随机分布在1 × 1的区域S内, 每个节点传输和处理负载的能力都是相同的. 此时所有节点都是孤立的, 假设以节点i为圆心、r为半径的连通区域内所有节点为节点i的潜在邻居, 并定义最靠近原点O的节点为汇聚节点.
在第2阶段, 从汇聚节点开始进行网络的拓扑演化.
步骤1 令汇聚节点与其通信半径r内的
$ {a}_{0} $ 个潜在邻居节点进行连接, 形成初始网络$ {T}_{0} $ .步骤 2 在时间步i, 定义网络
$ {T}_{i} $ 中具有最多孤立的潜在邻居的节点为v, 在其潜在邻居中挑选一个节点$ {n}_{i} $ 加入到网络$ {T}_{i} $ 中.步骤 3 如图1所示, 基于优先连接的原则下, 以
${\varPi}_{i}$ 的连接概率选取网络$ {T}_{i} $ 中a个节点与节点$ {n}_{i} $ 进行连接, 并满足a个节点均在节点$ {n}_{i} $ 的连通范围内; 若可选取的节点数小于a, 则全部连接. 连接概率${\varPi}_{i}$ 可通过下式求得:$ {\varPi }_{i}={\varPi}_{i}'\left(i\in {\rm{local}}\text{-}{\rm{area}}\right)\displaystyle\frac{f\left({E}_{i}\right){k}_{i}}{\displaystyle\sum _{{\rm{local}}\text{-}{\rm{area}}}f\left({E}_{j}\right){k}_{j}-q{k}_{\rm{max}}}, $ 其中, 局部区域指以节点
$ {n}_{i} $ 为圆心; r为半径的连通范围;$ {k}_{\rm{max}} $ 是默认节点最大的度值;$ q $ 是已经达到$ {k}_{\rm{max}} $ 的节点的个数;$ f\left({E}_{i}\right) $ 是功能函数, 为了方便处理, 这里取$ f\left({E}_{i}\right)=1 $ .
图 1 LAEE演化模型
Figure 1. LAEE evolution model.
步骤 4 重复步骤2和步骤 3, 直至区域S内的所有节点都被加入到网络中.
从上述过程可以看出, 在此模型中, 虽然N个节点的位置开始就已经确定了, 但它们是一个一个加入到网络中的, 且它们的连边是基于优先连接的原则建立的, 因此有少部分节点拥有大量的连接, 而大多数节点的度则比较小. LAEE网络的度分布如图2所示. 可以发现其度分布呈现幂律分布的特点, 是典型的异质网络.
图 2 N = 1500,
$ \left\langle{k}\right\rangle $ = 8时的LAEE网络的度分布Figure 2. Degree distribution of the LAEE network. N = 1500,
$ \left\langle{k}\right\rangle $ = 8. -
最简单的空间网络是随机几何图模型[24]. 该模型主要分为以下3个阶段:
步骤1 将N个节点随机地分布在1 × 1的区域S内.
步骤2 随机选取一个节点i, 以它为圆心, r为连通半径, 构成一个圆形的连通区域. 如图3所示, 节点i与其连通区域内的全部节点建立连接.
图 3 节点i与其连通区域内的全部节点建立连接
Figure 3. Node i connects all nodes in its connection area.
步骤3 重复步骤2, 直至所有节点都与其连通半径内的所有节点建立连接.
-
在节点数N与平均度
$ \left\langle{k}\right\rangle $ 相同的情况下, 随机几何图模型的连通半径要小于LAEE演化模型. 为了更公平地比较匀质与异质网络, 我们希望两个网络模型中的连通半径r相同. 对此, 本文在经典的随机几何图模型基础上, 提出一种改进的随机几何图模型.网络的生成如下所示:
步骤1 将N个节点随机的分布在
$ 1\times 1 $ 的区域S内.步骤2 随机选取一个节点i, 以节点i为圆心, r为连通半径, 构成一个圆形的连通区域. 如图4所示, 定义连接概率p, 节点i与其连通区域内的节点以p概率建立连接.
图 4 节点i与其连通范围内的节点以p概率进行连接
Figure 4. Node i connects nodes within its connection range with probability p.
步骤3 重复步骤2, 直至所有节点都被遍历到.
从上述过程可以看出, 在改进的随机几何图模型中, 每个节点的连接概率相同, 不同节点之间不存在明显的差异. 该模型的度分布情况如图5所示. 与LAEE网络相比, 改进的随机几何图更接近匀质网络.
图 5 N = 1500,
$ \left\langle{k}\right\rangle $ = 8时改进的随机几何图的度分布Figure 5. Degree distribution of the improved random geometric graph. N = 1500,
$ \left\langle{k}\right\rangle $ = 8. -
假设每个节点都具有相同的传输负载的能力. 负载在网络上的传输过程描述如下: 在每一个时间步, 网络产生R个单位的负载, 它们的源节点与目标节点均随机确定, 根据路由策略由源节点向目的节点传输. 每个节点在每个时间步中所能处理的最大负载量为C个单位的负载, 为了便于问题的分析, 假设
$ C=1 $ . 在每个时间步, 负载只能向前传输一步, 即从一个节点抵达至其邻居节点. 当负载到达目标节点时, 自动从网络中删除. 用参数$ H\left(R\right) $ 表示网络的序参量[18]:$ H\left(R\right)={\lim\limits _{t \to \infty }}\frac{C}{R}\frac{ \left\langle \Delta W \right\rangle }{\Delta t}, $ 其中,
$\Delta W=W (t+\Delta t ) - W (t)$ ,$ \Delta t $ 表示一个时间步的长度,$W(t)$ 表示t时刻网络中负载的总量. 当R较小时, 所有的负载都能被及时处理, 因此$H(R)=0$ , 这种状态称为自由流状态. 如果R逐渐增大, 使得在某个节点处每个时间步需要处理的负载量超过C, 那么必然会有一部分负载无法被及时处理, 此时$ H\left(R\right) > 0 $ , 即网络出现拥塞现象. 我们关心网络从自由流状态到拥塞状态的相变点处的R值, 称为$ {R}_{\rm{c}} $ , 它表示网络在不出现拥塞现象时最多能处理的负载量, 即网络的最大吞吐量.$ {R}_{\rm{c}} $ 的值一方面取决于网络的拓扑结构, 不同拓扑结构的网络具有不同的$ {R}_{\rm{c}} $ ; 另一方面,$ {R}_{\rm{c}} $ 的值取决于所采用的路由方式. 因此, 本文将在具有不同拓扑结构的空间网络模型下进行仿真, 并对比本文提出的路由方式与传统的最少跳数路由方式. -
在考虑负载传输时, 经常采用所谓的最短路径路由. 在一般的复杂网络中, 两点之间的最短路径通常指它们之间经过最少连边的路径, 即最少跳数路由. 但是, 在空间网络中, 所谓最短路径可能有多种含义, 例如跳数最少或者长度最短. 为了不引起混淆, 本文将通常意义下的最短路径路由称为“最少跳数路由”.
在采用最少跳数路由的情况下, 可以用介数来描述各个节点的负载情况, 任意一个节点v的介数表示如下[18]:
$ g\left(v\right)=\sum \limits_{s\ne t}\frac{{\sigma }_{st}\left(v\right)}{{\sigma }_{st}}, $ 其中
$ {\sigma }_{st} $ 表示节点s到节点t的最少跳数路径的数量,$ {\sigma }_{st}\left(v\right) $ 表示节点s到节点t的最少跳数路径中经过节点v的数量. 当$ R < {R}_{\rm{c}} $ 时, 网络处于自由流状态, 不会出现拥塞现象, 单位时间到达节点v的负载为$ Rg\left(v\right)/\left[N\left(N-1\right)\right] $ ; 当$ R > {R}_{\rm{c}} $ 时, 网络出现拥塞现象, 假设在节点v处出现拥塞, 此时$ Rg\left(v\right)/\left[N\left(N-1\right)\right] > C $ . 研究表明, 拥塞最先发生在介数值最大的节点处. 因此,$ {R}_{\rm{c}} $ 可表示为[18]$ {R}_{\rm{c}}= {CN\left(N-1\right)}/{{g}_{\rm{max}}} . $ -
在空间网络中, 由于每个节点都有一个空间位置, 因此每条连边都有长度. 简单起见, 考虑二维平面上的网络, 那么对于连接节点i和j的连边, 其长度为
$ d\left(ij\right)=\sqrt{{\left({x}_{i}-{x}_{j}\right)}^{2}+{\left({y}_{i}-{y}_{j}\right)}^{2}}, $ 其中
$ ({x}_{i}, {y}_{i}) $ 与$ ({x}_{j}, {y}_{j}) $ 分别为节点i和j的二维坐标. 这样, 对于任意节点对$ (s, t) $ , 可以定义它们之间的一条路径的长度为这条路径所经过的所有连边长度之和. 即路径$ P\left(s\to t\right)=\left(s\equiv x\left(0\right),x\left(1\right)\cdots,x\left(n\right)\equiv t\right) $ 的长度为
$ L\left(s\to t\right)=\sum \limits_{i=0}^{n-1}d\left(x\left(i\right)x\left(i+1\right)\right) . $ 在这些路径中, 长度最小的路径被称为最短长度路径, 而其长度被称为最短路径长度, 采用最短长度路径的路由策略称为最短路径长度路由. 可以看到, 这种路由策略只可能出现在空间网络中, 因为连边长度乃至路径长度的概念是建立在节点的空间坐标基础上的.
需要说明的是, 采用最短路径长度路由策略时, 节点的介数仍可以采用类似(3)式的方法计算, 但是式中的变量含义有所变化. 具体地,
$ {\sigma }_{st} $ 表示节点s到节点t的具有最短长度的路径的数量,$ {\sigma }_{st}\left(v\right) $ 表示节点s到节点t的具有最短长度的路径中经过节点v的数量. -
为了检验两种路由策略的性能, 采用前文提到的LAEE演化模型和改进的随机几何图模型两种空间网络进行仿真实验. 其中, LAEE演化模型产生具有无标度特性的空间网络, 是典型的异质网络; 而改进的随机几何图模型继承了经典随机几何图模型的特点, 是典型的匀质网络.
先将N个节点随机地分布在1 × 1的区域S内, 由于空间位置的限制, 节点i只能与以节点i为圆心, r为半径的区域内的潜在邻居节点进行连接. 根据(5)式, 可以计算出任意两点之间的距离, 找到节点i的所有潜在邻居节点, 再根据LAEE与改进的随机几何图模型的生成规则, 将节点i与其部分潜在邻居节点连接, 分别生成具有异质与匀质特性的空间网络.
对于网络的任意节点对, 其路径可由(6)式来表示. 在空间网络的背景下, 连边被赋予了长度的属性, 通过(7)式可以得到任意节点对之间的路径的长度, 本文提出的最短路径长度的路由正是基于(5)式—(7)式去寻找任意节点对
$ (s, t) $ 之间的最短长度的路径, 即$ {\rm{min}}L(s\to t ) $ . 传统的最少跳数路由和最短路径长度路由从不同角度刻画了节点之间的“最短路径”. 接下来将通过仿真分析来比较两种路由的性能, 进而确定那种路由效果更好.首先对两种路由策略下的拓扑指标进行分析. 不同路由策略下平均路径长度、平均跳数与节点数N的关系如图6和图7所示. 可以看到, 正如它们的名称所示, 最少跳数路由具有更小的平均跳数, 而最短路径长度路由具有更小的平均路径长度. 比较两种网络可以发现, 结构上异质的LAEE网络具有更短的平均路径长度和更小的平均跳数. 这是因为LAEE网络中具有少量大度节点, 它们提供了传输的捷径. 但是, 在同一种网络中, 随着节点数的增加, 平均路径长度略有减少, 而平均跳数却有所增加. 这是因为在保证平均度不变的前提下, 随着节点数的增加, 连通半径r是不断减小的. 这样, 平均来讲, 从源节点到目的节点所经过的连边数会增加.
图 6 平均度
$ \left\langle{k}\right\rangle=4 $ 时, 不同节点规模下两种路由方式平均路径长度的比较 (a) LAEE演化模型; (b)改进的随机几何图模型. 图中每个点是10次仿真的平均值Figure 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次仿真的平均值Figure 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.网络最大吞吐量
$ {R}_{\rm{c}} $ 与节点数N的关系如图8所示. 可以看出, 无论在哪种网络中, 最短路径长度路由都具有更大的$ {R}_{\rm{c}} $ 值, 这说明采用最短路径长度路由会有效提高空间网络的吞吐量. 当然, 如图7所示, 最短路径长度路由增加了平均跳数, 这将导致平均传输延时变长. 也就是说, 最短路径长度路由提高空间网络吞吐量是以增加传输延时为代价的. 而比较两种网络发现, 结构上异质的LAEE网络具有更小的$ {R}_{\rm{c}} $ 值, 这是因为异质网络中的大度节点在提供传输捷径的同时, 不可避免地成为传输的瓶颈, 制约了网络的吞吐量. 此外, 网络吞吐量随着网络规模增加而增大.
图 8 平均度
$ \left\langle{k}\right\rangle=4 $ 时, 不同节点规模下两种路由方式的网络最大吞吐量$ {R}_{\rm{c}} $ 的比较 (a) LAEE演化模型; (b)改进的随机几何图模型. 图中每个点是10次仿真的平均值Figure 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.不同路由策略下平均路径长度、平均跳数与平均度
$ \left\langle{k}\right\rangle $ 的关系如图9和图10所示. 与改变网络规模类似, 这里也可以看到, 无论平均度如何变化, 最少跳数路由总是具有更小的平均跳数, 而最短路径长度路由总是具有更小的平均路径长度. 另一方面, 随着$ \left\langle{k}\right\rangle $ 的增加, 网络中的连边数逐渐增加, 各节点间路径有了更多的选择, 因此传输的路径长度变短, 平均跳数减小.
图 9 节点数
$ N=1000 $ 时, 不同平均度下两种路由方式平均路径长度的比较 (a) LAEE演化模型; (b)改进的随机几何图模型. 图中每个点是10次仿真的平均值Figure 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次仿真的平均值Figure 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给出了网络最大吞吐量
$ {R}_{\rm{c}} $ 随平均度$ \left\langle{k}\right\rangle $ 的变化情况. 总体来看, 最短路径长度路由总是具有更大的$ {R}_{\rm{c}} $ 值. 而随着平均度的不断增大, 网络连接越来越稠密, 负载传输的路径越来越均匀地分布在网络中, 结果是导致$ {R}_{\rm{c}} $ 值的迅速增加, 即网络吞吐量迅速变大.
图 11 节点数
$ N=1000 $ 时, 不同平均度下两种路由方式的网络最大吞吐量$ {R}_{\rm{c}} $ 的比较 (a) LAEE演化模型; (b)改进的随机几何图模型. 图中每个点是10次仿真的平均值Figure 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和图13分别给出了两种网络在采用两种路由策略时的介数分布. 可以看出, 无论哪种网络, 采用最短路径长度路由时的最大介数值都比采用最少跳数路由时的最大介数小. 正是这个更小的最大介数, 导致最短路径长度路由具有更大的
$ {R}_{\rm{c}} $ . 那么, 为什么最短路径长度路由会导致更小的最大介数呢? 这是因为采用最短路径长度路由时, 为了保证路径长度尽可能短, 所遵循的路径更接近于直线, 所以所谓网络关键节点的作用并不突出. 相比之下, 最少跳数路由追求更少的跳数, 网络中少量关键节点往往起到中介的作用, 汇聚了大量的路径, 导致最大介数更大. 综上所述, 最短路径长度路由能使网络传输的负载得到更加合理的分布, 从而使网络具有更大的吞吐量, 是一种更加有效的路由策略.
图 12 LAEE演化模型中, 节点数N = 1000,
$ \left\langle{k}\right\rangle $ = 4时的介数分布 (a)最少跳数路由; (b)最短路径长度路由Figure 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)最短路径长度路由Figure 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. -
在空间网络中, “最短路径”可以有不同的解读, 传统的最短路径等效于跳数最少的路径. 而空间网络中由于连边具有长度属性, 最短路径也可以理解为从源节点到目的节点所经过的所有连边的长度之和(即路径长度)最短. 本文提出的最短路径长度路由策略就是基于后者. 通过在匀质和异质空间网络上的仿真发现, 这种新路由策略能够有效提升网络最大吞吐量. 本文提出的路由策略对现实生活中交通运输、无线通信网络等都具有很好的借鉴意义.
-
以通信网、电力网、交通网为代表的很多复杂网络以传输负载为基本功能. 在这些网络中, 网络的吞吐量是衡量网络传输性能的重要指标, 如何提升网络的吞吐量是研究热点之一. 不少研究人员提出了不同的路由算法, 通过调节传输路径来提高网络吞吐量. 但之前的研究很少考虑网络中节点的空间位置. 本文针对空间网络提出了一种高效的路由策略, 通过节点位置得到路径长度; 采用该算法, 负载从源节点沿着最短长度的路径传输到目标节点. 为了检验算法的有效性, 采用网络从自由流状态转变成拥塞状态的相变点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.-
Keywords:
- routing strategy /
- spatial network /
- congestion
[1] Erdös P, Rényi A 1959 Publ. Math. 6 290
[2] Barabási A L, Albert R 1999 Science 286 509
Google Scholar
[3] Watts D J, Strogatz S H 1998 Nature 393 440
Google Scholar
[4] 陈关荣 2008 力学进展 38 653
Google Scholar
Chen G R 2008 Adv. Mech. 38 653
Google Scholar
[5] 马金龙, 张俊峰, 张冬雯, 张红斌 2021 物理学报 70 078902
Google Scholar
Ma J L, Zhang J F, Zhang D W, Zhang H B 2021 Acta Phys. Sin. 70 078902
Google Scholar
[6] 于晓 2020 软件工程 23 1
Google Scholar
Yu X 2020 Software Engineering 23 1
Google Scholar
[7] 任卓明 2020 物理学报 69 048901
Google Scholar
Ren Z M 2020 Acta Phys. Sin. 69 048901
Google Scholar
[8] Hearnshaw E J S, Wilson M M J 2013 Int. J. Operat. Product. Manage. 33 442
Google Scholar
[9] Chen S Y, Huang W, Cattani C, Altieri G 2012 Math. Probl. Eng. 2012 732698
Google Scholar
[10] Tan F, Wu J J, Xia Y X, Tse C K 2014 Phys. Rev. E 89 062813
Google Scholar
[11] 陈华良, 刘忠信, 陈增强, 袁著祉 2009 物理学报 58 6068
Google Scholar
Chen H L, Liu Z X, Chen Z Q, Yuan Z Z 2009 Acta Phys. Sin. 58 6068
Google Scholar
[12] 刘伟彦, 刘斌 2014 物理学报 63 248901
Google Scholar
Liu W Y, Liu B 2014 Acta Phys. Sin. 63 248901
Google Scholar
[13] 赵磊, 周金和 2019 计算机科学 46 137
Google Scholar
Zhao L, Zhou J H 2019 Computer Science 46 137
Google Scholar
[14] 刘金良 2013 物理学报 62 040503
Google Scholar
Liu J L 2013 Acta Phys. Sin. 62 040503
Google Scholar
[15] 赵宇红 2019 博士学位论文 (北京: 北京科技大学)
Zhao Y H 2019 Ph. D. Dissertation (Beijing: University of Science and Technology Beijing) (in Chinese)
[16] 李世宝, 娄琳琳, 陈瑞祥, 洪利 2014 物理学报 63 028901
Google Scholar
Li S B, Lou L L, Chen R X, Hong L 2014 Acta Phys. Sin. 63 028901
Google Scholar
[17] 邵斐, 蒋国平 2011 物理学报 60 078902
Google Scholar
Shao F, Jiang G P 2011 Acta Phys. Sin. 60 078902
Google Scholar
[18] Yan G, Zhou T, Hu B, Fu Z Q, Wang B H 2005 Phys. Rev. E 73 046108
Google Scholar
[19] Huang W, Chow T W S 2009 Chaos 19 043124
Google Scholar
[20] Wang W X, Wang B H, Yin C Y, Xie Y B, Zhou T 2006 Phys. Rev. E 73 026111
Google Scholar
[21] Xia Y X, Wang C, Shen H L, Song H N 2020 Physica A 559 125071
Google Scholar
[22] Zhang M, Chen S, Sun L, Du W, Cao X 2021 Engineering 7 465
Google Scholar
[23] Du W B, Zhou X L, Jusup M, Wang Z 2016 Sci. Rep. 6 19059
Google Scholar
[24] Jiang L, Xu Q, Pan H, Dai Y, Tong J 2020 Secur. Commun. Netw. 2020 6513920
Google Scholar
[25] Bai G H, Li Y J, Fang Y N, Zhang Y A, Tao J Y 2020 Reliab. Eng. Syst. Saf. 193 106602
Google Scholar
[26] Zhao L, Lai Y C, Park K, Ye N 2005 Phys. Rev. E 71 026125
Google Scholar
[27] Dall J, Christensen M 2002 Phys. Rev. E 66 016121
Google 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 764698
Google Scholar
-
图 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.
图 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 509
Google Scholar
[3] Watts D J, Strogatz S H 1998 Nature 393 440
Google Scholar
[4] 陈关荣 2008 力学进展 38 653
Google Scholar
Chen G R 2008 Adv. Mech. 38 653
Google Scholar
[5] 马金龙, 张俊峰, 张冬雯, 张红斌 2021 物理学报 70 078902
Google Scholar
Ma J L, Zhang J F, Zhang D W, Zhang H B 2021 Acta Phys. Sin. 70 078902
Google Scholar
[6] 于晓 2020 软件工程 23 1
Google Scholar
Yu X 2020 Software Engineering 23 1
Google Scholar
[7] 任卓明 2020 物理学报 69 048901
Google Scholar
Ren Z M 2020 Acta Phys. Sin. 69 048901
Google Scholar
[8] Hearnshaw E J S, Wilson M M J 2013 Int. J. Operat. Product. Manage. 33 442
Google Scholar
[9] Chen S Y, Huang W, Cattani C, Altieri G 2012 Math. Probl. Eng. 2012 732698
Google Scholar
[10] Tan F, Wu J J, Xia Y X, Tse C K 2014 Phys. Rev. E 89 062813
Google Scholar
[11] 陈华良, 刘忠信, 陈增强, 袁著祉 2009 物理学报 58 6068
Google Scholar
Chen H L, Liu Z X, Chen Z Q, Yuan Z Z 2009 Acta Phys. Sin. 58 6068
Google Scholar
[12] 刘伟彦, 刘斌 2014 物理学报 63 248901
Google Scholar
Liu W Y, Liu B 2014 Acta Phys. Sin. 63 248901
Google Scholar
[13] 赵磊, 周金和 2019 计算机科学 46 137
Google Scholar
Zhao L, Zhou J H 2019 Computer Science 46 137
Google Scholar
[14] 刘金良 2013 物理学报 62 040503
Google Scholar
Liu J L 2013 Acta Phys. Sin. 62 040503
Google Scholar
[15] 赵宇红 2019 博士学位论文 (北京: 北京科技大学)
Zhao Y H 2019 Ph. D. Dissertation (Beijing: University of Science and Technology Beijing) (in Chinese)
[16] 李世宝, 娄琳琳, 陈瑞祥, 洪利 2014 物理学报 63 028901
Google Scholar
Li S B, Lou L L, Chen R X, Hong L 2014 Acta Phys. Sin. 63 028901
Google Scholar
[17] 邵斐, 蒋国平 2011 物理学报 60 078902
Google Scholar
Shao F, Jiang G P 2011 Acta Phys. Sin. 60 078902
Google Scholar
[18] Yan G, Zhou T, Hu B, Fu Z Q, Wang B H 2005 Phys. Rev. E 73 046108
Google Scholar
[19] Huang W, Chow T W S 2009 Chaos 19 043124
Google Scholar
[20] Wang W X, Wang B H, Yin C Y, Xie Y B, Zhou T 2006 Phys. Rev. E 73 026111
Google Scholar
[21] Xia Y X, Wang C, Shen H L, Song H N 2020 Physica A 559 125071
Google Scholar
[22] Zhang M, Chen S, Sun L, Du W, Cao X 2021 Engineering 7 465
Google Scholar
[23] Du W B, Zhou X L, Jusup M, Wang Z 2016 Sci. Rep. 6 19059
Google Scholar
[24] Jiang L, Xu Q, Pan H, Dai Y, Tong J 2020 Secur. Commun. Netw. 2020 6513920
Google Scholar
[25] Bai G H, Li Y J, Fang Y N, Zhang Y A, Tao J Y 2020 Reliab. Eng. Syst. Saf. 193 106602
Google Scholar
[26] Zhao L, Lai Y C, Park K, Ye N 2005 Phys. Rev. E 71 026125
Google Scholar
[27] Dall J, Christensen M 2002 Phys. Rev. E 66 016121
Google 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 764698
Google Scholar
计量
- 文章访问数: 1253
- PDF下载量: 63
- 被引次数: 0
