1.   引　言

当今信息时代, 网络无处不在, 我们的日常生活与网络息息相关. 随着日益增长的用户数量及指数级增长的数据量, 网络因数据量过载而发生拥塞的现象时有发生, 给人们带来许多不便甚至经济损失^[1-3]. 在这种大数据环境的驱动下, 对复杂网络的承载能力和传输容量提出了越来越高的要求^[4-6]. 以前关于复杂网络传输容量的研究, 大多关注于单层网络上的传输动力学特性^[7-10]. 现实中的许多网络, 比如信息网络、交通网络、电力网络等都具有双层或多层的结构, 并且网络的不同层不是独立存在的, 而是相互影响和依赖的^[11-14]. 例如Internet, World Wide Web (WWW)和Peer to Peer (P2P)网络, 应用层是由虚拟链路组成的逻辑层网络, 而实际上承担网络传输任务的是由IP层构成的物理层网络, 也就是说, 每个应用都映射在物理IP网络上, 由应用层(逻辑层)和IP层(物理层)共同决定了整个网络系统的传输容量. 与此类似, 在铁路交通网络中, 列车的起点、终点和经过的车站构成了一个逻辑层, 其运输任务映射在具体物理的铁路网络上^[15]. 由于双层结构或者多层结构更能反映实际网络的拓扑特征, 所以研究多层耦合网络的动力学行为具有十分重要的现实意义. 围绕着多层耦合网络传输容量的分析与优化, 降低网络拥塞的问题, Kurant 和Thiran^[15]将实际物理层结构与公共传输系统上的流量信息抽象成一个双层网络模型, 把上层看作一个交通流的逻辑层, 下层看作一个实际拓扑结构的物理层. Morris和Barthelemy^[16]研究了双层网络上的信息负载问题, 随着双层网络耦合紧密, 数据包的平均传输数量逐渐下降. 传统的最短路径路由(shortest path routing, SPR)策略的优点是数据包可以最快地到达目的地, 但是容易发生拥塞, 数据包会很快拥堵在中心节点上^[17,18]. Zhuo等^[19]提出了一种基于静态权重的全局感知路由(global awareness routing, GAR)策略, 该策略依据物理层节点的度值来设置逻辑层边上的权重, 选择逻辑层边权重之和最小的路径传输数据包, 由于考虑了物理层的静态拓扑的中心节点信息对逻辑层路由的影响, 提高了整个网络系统的传输容量. 卓越^[20]考虑物理层的队列长度对网络传输特性的影响, 把逻辑层链路的权重与其映射的物理层节点队列长度进行关联, 并按照队列长度的变化, 动态地更新链路权重, 与传统的最短路径路由策略和静态权重的全局意识路由策略相比, 进一步提高了网络的传输容量. Zhang等^[21]提出了一种删除逻辑层链路策略, 通过删除节点介数大的链路重构逻辑层拓扑, 在最短路由及有效路由策略下, 传输容量都有显著提高. Zhang等^[22]在静态权重路由策略的基础上做了一些改进, 根据两层的静态拓扑信息和控制参数给路由路径分配合适的权重, 与最短路由和静态权重路由算法相比, 提高了网络传输容量. Ma等^[23]提出了一种基于两层节点介数的全局感知路由(improved global awareness routing, IGAR)策略, 按照介数给双层的链路赋予合适的权重, 与SPR策略和GAR策略相比, IGAR策略更能提高网络传输容量. Pu等^[24]研究多层网络中的信息传输, 通过仿真得到了最优参数α对应于最大网络寿命和到达分组的最大数量, 发现分类耦合优于随机耦合和分离耦合, 实现了更好的传输性能. 对于多层耦合网络来说, 传输容量除与网络结构、路由策略和资源分配有关外, 层与层之间的耦合方式对传输容量也有很大影响. 本文将基于双层网络模型, 探究双层网络之间的耦合方式对整个网络系统传输容量的影响, 通过优化网络之间的耦合率使得网络负载分布更均匀, 以此来减少网络拥塞的发生.

2.   耦合网络模型分析

2.1   网络模型

双层耦合网络依据功能的不同分为两层, 下层基础的网络叫做物理层, 上层直接对接承载业务的网络为逻辑层. 逻辑层与物理层保持相对独立, 层内节点依据网络模型的增长特性与优先连接特性进行相互连接, 两层间的节点一一对应. 上下两层按照各自的路由传输协议传送数据. 上层逻辑层数据包按照给定的路由表进行传输, 每一条逻辑边映射到物理层对应一条物理层的路由路径. 物理层为逻辑层提供稳定的网络连接, 不关心逻辑层的具体路由策略, 只根据物理层的路由表负责把数据包从对应的源节点传送到目的节点(由逻辑层映射). 如图1所示, 设定双层网络都是在既定的路由策略下传输数据. 逻辑层中节点$a^{\rm l}$和$d^{\rm l}$之间的传输路由路径为$RP_{a^{\rm{l}}, d^{\rm{l}}} = {\{a^{\rm{l}}, b^{\rm{l}}, d^{\rm{l}}}\}$, 对应的逻辑边为$l_{a^{\rm{l}}, b^{\rm{l}}}$ 和$l_{b^{\rm{l}}, d^{\rm{l}}}$. 这条逻辑边映射到物理层对应的路径为${\{a^{\rm{p}}, e^{\rm{p}}, b^{\rm{p}}}\}$和${\{b^{\rm{p}}, f^{\rm{p}}, d^{\rm{p}}}\}$. 物理层数据包从源节点到目的节点整个传输路径为$RP'_{a^{\rm{p}}, d^{\rm{p}}} = {\{}a^{\rm{p}},\; e^{\rm{p}},\; b^{\rm{p}}, f^{\rm{p}},\; d^{\rm{p}}{\}}$.

图 1  双层网络模型示意图

Fig. 1.  Legend of the two-layer networks model

下载: 全尺寸图片 幻灯片

双层耦合网络的拓扑结构对传输动力学过程起着至关重要的作用, 对于一个给定的基本网络模型, 耦合网络拓扑结构主要取决于两层网络之间连接方式的差异^[25,26]. 根据层间度度相关性, 各层之间的耦合强度可以通过斯皮尔曼等级相关系数(Spearman rank correlation coefficient)^[27,28]来量化, 该系数定义为

其中N表示网络规模的大小, $\varDelta_i^2$表示上下两层间节点度的差异性, $P_{\rm r}$系数表示网络耦合强度, $P_{\rm r}$ 的范围是[–1, 1]. 当$P_{\rm r}\approx-1$时, 在这种情况下, 存在网络的最大负相关性, 即网络间异配耦合连接. 当所有节点被随机匹配时, 网络中的层是完全不相关的, 此时$P_{\rm r}\approx0$, 在这种情况下

在具有最大正相关性的双层网络中, 在各个层中具有相同等级的任何节点对都是匹配的, 即$\varDelta_i^2 = 0$, 表示任意一对匹配节点差异性最小, 因此$P_{\rm r}\thickapprox1$. 根据(1)式, 在随机重新匹配后, 一对节点$\varDelta_i^2 = 0$, 那么有可能$1-q$ 和匹配后的差异$\varDelta'_i$都有可能为$q$, 那么(1)式可以改写为

结合(2)式和(3)式可以得到重新匹配后的耦合强度系数:

1)同配耦合(assortative coupling, AC), 即正相关连接. 上层逻辑层与下层物理层中节点按照度值大小连接, 如果存在度相同的点则随机排序, 按照$L_{i} \rightarrow P_{i}$依次建立双层耦合网络之间内部一对一的耦合连接, 逻辑层和物理层中度值从大到小排序, 逻辑层中度大的节点连接物理层中度大的节点, 度小的节点连接度小的节点, 构成两个网络节点一对一的对应方式.

2)异配耦合(disassortative coupling, DC), 即负相关连接. 与AC方式相反, DC方式中逻辑层按照度值从大到小排序, 物理层按照度值从小到大排序, 如果存在度值相同的节点, 则对它们随机排序. 按$L_{i}{\rightarrow}P_{j}\;(j = N-i+1)$的方式建立耦合网络层间一对一的连接, 即逻辑层中度大的节点与物理层中度小的节点相连接, 并构成两个网络节点间一对一的对应方式.

3)随机耦合(random coupling, RC), 即不相关连接. 逻辑层与物理层中节点间随机连接, 并构成两个网络节点间一对一的对应方式.

2.2   双层耦合网络流量模型

在双层网络模型中, 上下两层网络中的每个节点都具有主机和路由器的功能, 也就是说每个节点都可以产生、接收和转发数据包^[29]. 整个网络每个时间步随机生成$R$个数据包(数据包生成率为$R$), 每个数据包的源地址与目的地址都是随机选取的, 且每个数据包的源地址与目的地址不同. 设定网络中每个节点的数据包处理能力为$C$, 即在每个时间步每个节点最多可以处理$C$个数据包^[30-32]. 当数据包生成时, 会被放置到节点队列的队尾, 采用先进先出(first-in-first-out)规则传送^[33]. 物理层和逻辑层上生成的数据包都会按照既定的路由策略, 寻找一条相应的路径进行传输, 如果存在多条传输路径则随机选一条, 到达目的节点时, 则被移除^[34,35]. 如果下一个不是目的节点, 数据包将会保存在下一个节点的缓存队列中等待传输.

不同的数据包生成率$R$代表网络不同的负载能力. Zhao 等^[36]在不同结构的网络上研究信息流从自由态到拥塞态的相变过程, 发现有序参数都会存在一个连续相变点. 可依据相变点处$H(R)$ 值来看出网络中信息流的状态变化. 网络处于自由流通状态时, 网络里几乎没有数据包拥塞. 随着数据包产生率$R$的增长, 网络将从自由态进入到拥塞状态, 存在一个临界值$R_{\rm{c}}$. 当数据包产生率$R < R_{\rm{c}}$时, 生成的数据包与被移除的数据包处于平衡状态, 因此网络处于自由流通状态. 当$R = R_{\rm{c}}$时网络处在一个从自由态转换到拥塞态的转换状态. 当$R > R_{\rm{c}}$时, 数据包随着时间不断地增加, 滞留在网络里的数据包量大于移除的数据包量, 网络进入了拥塞状态. 通常用一个有序参数$H(R)$ 来描述^[37-39]:

其中$C$表示节点的处理能力, $\Delta{W}$表示从时间$t$到$t+\Delta{t}$网络中总数据包的增长量. 有序参数$H(R)$表示数据包产生率为$R$时, 网络中每个时间步数据包总量的增长速率. 当$H(R) = 0$时, 此时网络处于自由流通状态, 当$H(R) > 0$时, 网络处于拥塞状态, 因此$R_{\rm{c}}$是网络中维持自由流通状态下最大的数据包生成率.

2.3   路由策略分析

本文采用SPR策略和基于度的静态权重路由(degree weighted routing, DWR)策略作为参照, 对比双层网络之间的耦合强度对传输容量的影响. 采用传统的SPR策略, 节点的度值与节点中心程度成正比关系, 度值大的节点中心性越强, 易拥塞. 采用DWR策略将节点的度值作为连接边的权重考虑在传输路径中, 使得信息流更加均匀.

双层耦合网络中上下两层都采用SPR策略时, 数据包在源节点与目的节点间的最短路径上传输, 易造成中心节点拥塞^[17,18,40]. DWR策略^[23,24]应用在物理层上时, 物理层任意两节点$i^{\rm p}$和$j^{\rm p}$的路径可以表示为$P(i^{\rm p}): = i^{\rm p}\equiv{x_0^{\rm p}}, {x_1^{\rm p}}, ..., {x_n^{\rm p}}, {x_{n-1}^{\rm p}}\equiv {j^{\rm p}}$, 在节点$i^{\rm p}$与$j^{\rm p}$之间的边权重为

其中$k{_{i^{\rm p}}}$是节点$i^{\rm p}$的度, $\alpha$是一个控制参数. 对于物理层节点$i^{\rm p}$和$j^{\rm p}$之间的任意路径, 其权重可以表示为

其中$n$是路径长度. 权重$\varOmega$最小的路径就是数据包传输的最佳路径, 如果存在多条传输路径, 则随机选择一条路径. 在逻辑层上权重的设置跟物理层是类似的, 节点$i^{\rm l}$与$j^{\rm l}$ 的边权重为

那么逻辑层任意两节点$i^{\rm l}$和$j^{\rm l}$间的路径权重定义为

首先计算两层中每个节点的度, 然后分别设置两层边的权重, 物理层任意两节点边的权重为$\omega_{{i^{\rm p}}{j^{\rm p}}}$, 逻辑层任意两节点边的权重依据物理层设置为$\omega_{{i^{\rm l}}{j^{\rm l}}}$.

本文在SPR和DWR两种路由策略的基础上研究双层网络之间的耦合强度对传输容量的影响, 通过分析数据包在网络中的传输过程, 来研究双层耦合网络间的交互机理, 优化网络之间的耦合方式, 提高网络的传输容量, 由此可分析出, 根据网络之间的耦合方式特点确定适合的路由策略能更有效地避免网络拥塞的发生.

3.   仿真实验结果与分析

为了研究双层网络之间的耦合强度对整个网络系统传输容量的影响, 采用BA, SF无标度网络, ER随机网络作为基础网络模型, 在SPR 和DWR 两种路由策略基础上进行仿真实验. 基于六种网络模型搭配, 设置网络规模$N = 400$, 平均度$\left\langle k \right\rangle = 8$, 可看出采用SPR和DWR策略在AC, DC与RC这三种耦合方式条件下影响数据包产生率$R$的因素.

分析SPR与DWR这两种路由策略和AC, DC与RC这三种耦合方式有序参数$\eta$与数据包产生率$R$的关系, 可以关注$R$的相变点, 相变点即为最大的传输容量$R_{\rm c}$. 如图2所示, 这六种网络模型在相同变量的条件下, 采用SPR策略时DC方式同AC, RC方式作比较, 相变点处于最大值, 即此时的数据包产生率$R$是最大的, 网络传输性能达到最佳, 说明采用SPR策略时, DC方式为最佳耦合方式.

图 2  采用SPR策略AC, DC, RC 这三种耦合方式有序参数$\eta$与数据包产生率$R$的关系　(a) BA-BA模型; (b) ER-ER模型; (c) SF-SF模型; (d) BA-ER模型; (e) BA-SF模型; (f) ER-SF模型

Fig. 2.  Used the SPR strategy, the relationship between ordered parameters $\eta$ and packet generation rate $R$ under the three coupling modes of AC, DC and RC: (a) BA-BA model; (b) ER-ER model; (c) SF-SF model; (d) BA-ER model; (e) BA-SF model; (f) ER-SF model

下载: 全尺寸图片 幻灯片

从图3可以看出, 这六种网络模型采用DWR策略, 在采用AC, DC与RC 这三种耦合方式条件下数据包产生率$R$随着控制参数$\alpha$变化的趋势, 会出现一个峰值. 在图3(b) ER-ER模型、图3(c) SF-SF模型、图3(e) BA-SF模型和图3(f) ER-SF模型中, AC, DC, RC这三种耦合方式在最优参数$\alpha = 0.4$时, 数据包产生率$R$出现最大值, 即此时的传输容量达到最大值, 此条件下的AC方式为最佳耦合方式. 在图3(a) BA-BA中, 可看出AC, DC与RC这三种耦合方式在最优参数$\alpha = 0.8$时, 数据包产生率$R$出现最大值, 此时AC方式为最佳耦合方式. 在图3(d) BA-ER模型中, 可看出AC, DC与RC这三种耦合方式在最优参数$\alpha = 0.6$时, 数据包产生率$R$出现最大值, 此时AC方式为最佳耦合方式. 由此可知在上述实验模型中采用DWR策略, 存在一个最优控制参数$\alpha$, 使得传输容量达到最大值, AC方式为最佳耦合方式.

图 3  采用DWR策略AC, DC, RC 这三种耦合方式$R$与控制参数$\alpha$的关系　(a) BA-BA模型; (b) ER-ER模型; (c) SF-SF模型; (d) BA-ER模型; (e) BA-SF模型; (f) ER-SF模型

Fig. 3.  Used the SPR strategy, the relationship between $R$ and control parameter $\alpha$ under the three coupling modes of AC, DC and RC: (a) BA-BA model; (b) ER-ER model; (c) SF-SF model; (d) BA-ER model; (e) BA-SF model; (f) ER-SF model

下载: 全尺寸图片 幻灯片

为了分析采用DWR策略在AC, DC与RC这三种耦合方式下有序参数$\eta$与数据包产生率$R$的关系, 在这六种模型中取最优控制参数进行仿真实验, 结果如图4所示. 可以看出, AC, DC与RC这三种耦合方式都是在规模、平均度一致的条件下作实验对比, 在每一组实验中AC方式与DC, RC作比较$R$相变值最大, 即传输容量最大, 可知在上述六种双层网络模型中, AC方式为采用DWR策略时的最佳耦合方式.

图 4  采用DWR策略AC, DC, RC 这三种耦合方式序参数$\eta$与数据包产生率$R$的关系　(a) BA-BA模型; (b) ER-ER模型; (c) SF-SF模型; (d) BA-ER模型; (e) BA-SF模型; (f) ER-SF模型

Fig. 4.  Used the DWR strategy, the relationship between ordered parameters $\eta$ and generation rate $R$ under the three coupling modes of AC, DC and RC: (a) BA-BA model; (b) ER-ER model; (c) SF-SF model; (d) BA-ER model; (e) BA-SF model; (f) ER-SF model

下载: 全尺寸图片 幻灯片

考虑到实际网络的特性, 设定逻辑层和物理层都为无标度网络, 采用BA-BA基础网络模型, 设定仿真实验规模N = 200, 400, 600, 800, 1000, 1800 和2400, 平均度$\left\langle k \right\rangle \!= 8$, 节点处理能力$C \!= 2$, 节点处的缓存长度无限长. 为保证实验数据的精准性, 在仿真实验中平均度、节点处理能力都保持一致. 首先对耦合强度系数$P_{\rm r}$随数据包产生率临界值$R_{\rm c}$变化的趋势进行仿真. 在之后的仿真分析中统一用规模为$N = 400$的网络进行分析, 涉及不同规模的实验除外. 如图5所示, 网络规模$N = 400$, 平均度$\left\langle k \right\rangle = 8$, 改变$P_{\rm r}$数值, $P_{\rm r}$从–1到1连续变化, 研究在此过程中网络传输容量$R_{\rm c}$的变化趋势. 分别采用SPR和DWR两种路由策略进行实验仿真, 可看出采用SPR策略, 当$P_{\rm r}= -1$ 时与其他$P_{\rm r}$系数下的$R_{\rm c}$值对比, 传输容量$R_{\rm c} = 9$是最大的, 此时DC方式使得整个网络系统的传输容量达到最大值. 在采用DWR路由策略, 当$P_{\rm r} = 1$时与其他$P_{\rm r}$系数下的$R_{\rm c}$值作对比, $R_{\rm c} = 35$, 传输容量达到了最大值, 这时AC方式是最佳的耦合方式.

图 5  耦合强度系数$P_{\rm r}$与$R_{\rm c}$的关系

Fig. 5.  Relationship between coupling correlation coefficient $P_r$ and $R_{\rm c}$

下载: 全尺寸图片 幻灯片

分别在RC, DC和AC这三种耦合方式下, 采用DWR策略, 研究不同网络规模的数据包产生率临界值$R_{\rm c}$与控制参数$\alpha$之间的关系. 如图6所示, $\alpha$取值范围为$-0.2—1.4$, 平均度$\left\langle k \right\rangle = 8$, 分别在RC, DC和AC耦合方式条件下用网络规模$N$ = 400, 600, 800, 1800和2400来作对比, 可看出RC, DC和AC这三种耦合方式在采用DWR策略时控制参数$\alpha$的最优值为$0.8$, 在之后的仿真中DWR策略的控制参数$\alpha$取值默认为0.8. 在图6(a)—图6(c)三幅图中可看出RC, DC和AC这三种耦合方式随着网络规模的增加, 传输容量临界值$R_{\rm c}$都在不断地增大, 到达一个峰值后不再增加, 随后逐渐减小. 例如图6(c)中规模为$N = 800$的曲线, 在采用RC, DC和AC这三种耦合方式时, RC方式的$R_{\rm c} = 26$, DC方式的$R_{\rm c} = 30$, AC方式的$R_{\rm c} = 48$, 由此可得在DWR策略时, 采用AC方式时, 网络的传输容量最大, 效果最佳, AC方式为此条件下的最佳耦合方式.

图 6  DWR策略不同网络规模$R_{\rm c}$与控制参数$\alpha$的关系　(a) RC耦合方式; (b) DC 耦合方式; (c) AC耦合方式

Fig. 6.  Relationship between $R_{\rm c}$ and control parameter $\alpha$ under different network scales of DWR strategy: (a) RC Coupling; (b) DC Coupling; (c) AC Coupling

下载: 全尺寸图片 幻灯片

为了进一步分析双层无标度网络中耦合方式和路由策略对传输容量的影响因素, 下面采用BA-SF基础网络模型进行仿真实验. BA和SF网络都为无标度网络, 幂率指数不同, BA网络幂指数为3, SF网络幂指数设置为4, 平均度$\left\langle k \right\rangle = 8$. 如图7所示, 在BA-SF模型中采用了DWR策略, 分析AC, DC 与RC这三种耦合方式下数据包产生率$R$与$\alpha$的变化趋势. 仿真实验规模设置为$N$ = 400, 600, 800, 1000 和1600, 控制参数$\alpha$的取值范围从$-0.2—1.4$. 在不同规模下, 比较$\alpha$取最优控制参数0.4 时所对应的$R$值, 从图7(a)—图7(c)可以看出$R$值随着规模的增加而增大. 取$N = 1600$的规模作比较, 图7(a) 中AC 方式下控制参数取最优值时对应的$R = 85$, 图7(b)中DC方式下控制参数取最优值对应的$R = 53$, 图7(c)中RC方式下控制参数取最优值对应的$R = 48$, 对比可知AC 方式对应的$R$值是最大的, 传输效果是最好的. 采用DWR策略时在双层BA-SF 网络中AC方式为最佳耦合方式.

图 7  DWR策略不同网络规模$R$与控制参数$\alpha$的关系　(a) AC耦合方式; (b) DC 耦合方式; (c) RC耦合方式

Fig. 7.  Relationship between $R$ and control parameter $\alpha$ under different network scales of DWR strategy: (a) AC Coupling; (b) DC Coupling; (c) RC Coupling

下载: 全尺寸图片 幻灯片

研究双层耦合网络之间的耦合特性对传输容量的影响, 采用六种基础网络模型进行对比实验, 在上述对比实验中可看出, BA-BA和BA-SF的对比效果比较明显, 基于实验设置平均度$\left\langle k \right\rangle = 8$, BA-SF在取较大规模时, 传输路径受到限制, 而BA-BA模型是正常传输的, 因此性能参数的实验在基于BA-BA 网络模型上完成.

为了获得更好的网络传输性能, 通常情况下可以相应地减少数据包在网络中的平均传输时间$\left\langle T \right\rangle$, 并增加网络的平均吞吐量$\left\langle N_t \right\rangle$, 可以使用$\left\langle T \right\rangle$和$\left\langle N_t \right\rangle$来衡量网络传输性能. 网络的平均吞吐量$\left\langle N_t \right\rangle$为单位时间内, 网络中的数据包达到目的节点的平均数量. 表达式如下:

其中t是在指定时刻, $\Delta t$是时间窗口, N是网络节点的数量, $m_{i}(t)$是在t时刻到达目的节点$i$的数据包个数. 刚开始网络处于自由态, $\left\langle N_t \right\rangle$随着数据包产生率$R$的增大呈线性增长趋势; 网络进入拥塞态后, $\left\langle N_t \right\rangle$增长的趋势变得缓慢, 两者呈现出非线性关系; 最终网络达到饱和状态, $\left\langle N_t \right\rangle$不再随着数据包产生率$R$的增加而变化, 达到平缓的趋势. 研究在不同耦合方式和不同路由策略条件下, 双层耦合网络的吞吐量$\left\langle N_t \right\rangle$随数据包产生率$R$的变化趋势. 如图8所示, 设置网络规模$N = 400$, 平均度$\left\langle k \right\rangle = 8$, 从图8(a)可以看出, 在采用SPR策略, 网络中DC方式与AC, RC两种方式对比可得, DC方式下的平均吞吐量$\left\langle N_t \right\rangle$的值最大, DC方式最佳. 从图8(b)可以看出, 采用DWR策略, 最佳参数$\alpha_{\rm c} = 0.8$, AC耦合方式下的吞吐量$\left\langle N_t \right\rangle$与RC, DC方式作对比可得, $\left\langle N_t \right\rangle$的值为最大, AC方式最佳.

图 8  两种路由策略不同耦合方式平均吞吐量$\left\langle N_t \right\rangle$ 与$R$的关系　(a) SPR策略; (b) DWR策略

Fig. 8.  Relationship between average information flow $\left\langle N_t \right\rangle$ and $R$ under two routing strategies with different coupling: (a) SPR; (b) DWR

下载: 全尺寸图片 幻灯片

衡量网络传输性能的另外一个重要参数是平均传输时间$\left\langle T \right\rangle$, 通常情况下应该尽可能缩短数据包的传输时间, 定义数据包的传输时间$\left\langle T\right\rangle$为网络中所有数据包从源节点到目的地点传输所消耗的传输时间, 表达式如下:

其中$n$是在指定时间内到达目的节点的数据包个数; $\left\langle T_i \right\rangle$是数据包$i$的传输时间, 包括数据包网络中的传送时间和在拥塞节点处的等待时间. 当$R < R_{\rm c}$时, 网络处于没有发生拥塞的自由态, 数据包的传输时间只依赖于在网络中的传递时间, 而等待时间几乎为零. 由于数据包的传递时间相对较小, 所以此时$\left\langle T \right\rangle$数值较小. 当$R > R_{\rm c}$时, 系统开始进入拥塞状态, 数据包的传输时间主要由传递时间和等待时间之和决定, 其中传递时间较小, 主要由等待时间决定, 所以进入拥塞状态时$\left\langle T \right\rangle$数值会突然增大, 发生相变. 如图9所示, 分别采用SPR 策略和DWR策略, 网络规模$N = 400$, 平均度$\left\langle k \right\rangle = 8$, 研究在RC, DC 和AC耦合方式时$\left\langle T \right\rangle$ 随数据包产生率$R$增长的变化趋势. 从图9(a)可以看出, 采用SPR策略, 比较RC, DC和AC这三种耦合方式下的$\left\langle T \right\rangle$的数值大小, 在DC方式下, $\left\langle T \right\rangle$发生的相变值最大, 网络对数据包的处理能力相对较强, DC 方式为最佳耦合方式. 从图9(b) 可以看出, 采用DWR策略, 对比RC, DC和AC方式下的变换曲线, 可得AC方式下的$\left\langle T \right\rangle$的相变点数值最大, 在一定程度上提高了传输容量, AC方式为最佳耦合方式.

图 9  采用两种路由策略不同耦合方式平均传输时间$\left\langle T \right\rangle$与$R$的关系　(a) SPR策略; (b) DWR策略,

Fig. 9.  Relationship between average transmission time $\left\langle T \right\rangle$ and $R$ under two routing strategies with different coupling: (a) SPR; (b) DWR

下载: 全尺寸图片 幻灯片

为了分析RC, DC和AC这三种耦合方式对不同网络规模传输效率的影响, 研究了数据包产生率临界值$R_{\rm c}$随网络规模$N$变化的趋势, 如图10所示. 图10(a)是采用SPR策略, 比较RC, DC和AC三种耦合方式$R_{\rm c}$随网络规模N从200增加到2400变化的趋势, 其中网络平均度$\left\langle k \right\rangle = 8$. 可看出采用SPR策略AC方式的$R_{\rm c}$值显示的数据包产生率十分稳定, 不随网络规模变化而变化. 采用DC方式的$R_{\rm c}$值随着网络规模而变化, 变化幅度较大, 最终趋于稳定, 采用RC方式的$R_{\rm c}$值随着网络规模变换较小. 可见, 随着网络规模变换DC方式很大程度上提高了网络的传输容量, 效果最佳. 图10(b)是采用DWR策略, 可看出RC, DC和AC三种耦合方式的$R_{\rm c}$都随着网络规模的增加而变大, 但是采用AC方式的$R_{\rm c}$值比DC和RC两种耦合方式的$R_{\rm c}$值变化幅度更大, 效果更加明显, 能够更好地改善网络性能, 提高传输容量.

图 10  两种路由策略三种耦合方式$R_{\rm c}$随网络规模N的变化　(a) SPR策略; (b) DWR策略

Fig. 10.  Relationship between network size N and $R_{\rm c}$ under two routing strategies with different coupling: (a) SPR; (b) DWR

下载: 全尺寸图片 幻灯片

衡量网络传输性能的参数还有平均路径长度$\left\langle L \right\rangle$, 其定义为

其中N为网络规模大小, $d_{ij}$为节点i与节点j之间的最短路径长度. 如图11所示, 仿真实验设置网络规模N = 200, 400, 600, 800, 1000, 1800和2400, 平均度$\left\langle k \right\rangle = 8$, 实验仿真了平均路径长度$\left\langle L \right\rangle$随网络规模N的变化趋势, SPR, DWR策略下AC, DC 和RC三种耦合方式的平均路径长度$\left\langle L \right\rangle$随网络规模N增加而增大. 图11(a)是采用SPR 策略, 从规模为200到2400的变化趋势来看平均路径长度$\left\langle L \right\rangle$都是呈增长趋势, AC, DC和RC三种耦合方式相比较, 采用AC方式的平均路径长度较小, 更有效的提高网络传输效率. 图11(b)是采用DWR策略, 从规模为200到2400的变化趋势来看平均路径长度$\left\langle L \right\rangle$也都是呈增长趋势, AC方式同DC与RC两种耦合方式做对比, AC方式下的平均路径长度较小, 更有益于提升网络性能.

图 11  两种路由策略三种耦合方式平均路径长度$\left\langle L \right\rangle$与网络规模N的关系　(a) SPR策略; (b) DWR 策略

Fig. 11.  Relationship between average path length $\left\langle L \right\rangle$ and network size N under two routing strategies with different coupling: (a) SPR; (b) DWR

下载: 全尺寸图片 幻灯片

4.   结　论

目前对复杂网络传输容量的研究大多以单层网络为研究对象, 实际网络不是独立存在的, 而是具有分层结构并且网络之间是相互依存相互影响的. 针对这种分层和依存关系研究双层耦合网络的交互机理和耦合强度, 在采用SPR和DWR策略的情况下探讨数据包的传输机理. 本文提出双层网络之间的耦合连接方式能够有效地提高网络传输容量, 分析了RC, DC和AC这三种网络之间的耦合方式, 依据网络之间耦合连接的特点, 可找出适合每一种耦合方式的路由传输策略. 通过六种基础网络仿真实验发现在双层耦合网络上, 分别采用SPR和DWR策略可得到相对应的最佳耦合方式. 在采用SPR策略时DC方式为最佳耦合方式, 相应地提升了网络传输容量. 在采用DWR策略时AC方式使得网络中的信息流更加均匀, 有利于信息的传输, 相应地提升了网络性能, 此条件下AC为最佳耦合方式. 现实世界呈现出双层甚至多层的复杂结构, 可依据网络之间的耦合连接特点, 采用适合的路由传输策略, 在一定程度上能更好地提升网络性能. 双层耦合网络交互机理的研究为实际网络设计和优化提供了理论基础.