基于通信序列熵的复杂网络传输容量*
2021-05-07马金龙张俊峰张冬雯张红斌
马金龙 张俊峰 张冬雯 张红斌
(河北科技大学信息科学与工程学院, 石家庄 050018)
网络的传输性能在一定程度上依赖于网络的拓扑结构.本文从结构信息的角度分析复杂网络的传输动力学行为, 寻找影响网络传输容量的信息结构测度指标.通信序列熵可以有效地量化网络的整体结构信息,为了表征网络整体传输能力, 把通信序列熵引入到复杂网络传输动力学分析中, 研究网络的通信序列熵与传输性能之间的关联特性, 分析这种相关性存在的内在机理.分别在BA 无标度和WS 小世界网络模型上进行仿真, 结果显示: 网络的通信序列熵与其传输容量存在密切关联性, 随着通信序列熵的增加, 网络拓扑结构的均匀性随之增强, 传输容量明显增加.网络的传输容量是通信序列熵的单调递增函数, 与通信序列熵成正关联关系.通信序列熵可有效评估网络的传输容量, 本结论可为设计高传输容量网络提供理论依据.
1 引 言
现实世界中有着各式各样的网络, 如通信网络[1−4]、交通网络[5,6]、社区网络[7,8]、贸易网络[9]等.这些网络大多表现出高度的复杂性, 如连接结构的复杂性、节点类型的复杂性和网络演化过程的复杂性等.复杂网络理论不仅可以帮助我们更好地理解现实网络的复杂结构特征, 还可以有效研究发生在现实网络上的动力学行为[10−14].网络的拓扑结构决定其功能, 网络上的动力学行为受到网络拓扑结构的影响.随着大数据时代的到来, 网络拥塞现象越发严重, 如何提升网络传输容量成为广大学者关注的问题.Guimerá等[15]证明了缺少高介数节点的均匀网络具有更大的网络承载能力.Zhao 等[16]基于概率统计方法对影响网络传输容量的因素进行了分析, 指出网络的传输容量与网络平均最短路径和节点最大介数值所占比重成反比关系, 提出了可用于衡量网络传输容量的数值计算公式.孙磊等[17]从网络的拓扑结构指标(最大介数、最大介数比例、平均路径长度)角度研究了网络结构对网络传输容量的影响, 研究表明网络的拓扑结构指标的变化对网络的传输容量有着显著影响.Chen 等[18]通过理论分析表明, 为缓解拥塞现象, 最佳的网络拓扑应具有两个关键特征: 流量分布均匀和传输距离短.现有一些学者通过增加或删除部分比例的边, 或者将一定比例的双向边更改为单向边的方法来优化网络的拓扑结构, 进而缓解网络拥塞的发生, 提升网络的传输容量[19−34].
如何定量地描述网络拓扑结构信息是研究网络传输性能的关键问题.当以信息的角度去描述网络的拓扑结构时, 信息论中的香农熵理论是一个有力的工具.香农熵理论本身是描述事物带有某种信息的不确定性, 在热力学与信息学理论中广泛应用[35−37].随着复杂网络研究的逐渐深入, 为了有效地量化网络结构信息, 香农熵理论被广泛地应用到复杂网络模型相关信息的度量评估上.Wang 等[38]研究了可以度量网络异质性的度分布熵.吴俊等[39]利用节点相对度值定义了网络的结构熵, 可以定量分析无标度网络拓扑结构的非均匀性.蔡萌等[40]从网络结构中的“点”差异性和“边”差异性两方面综合考虑度值大小和度分布作为结构重要性的度量, 进而提出一种新的网络结构熵定义.这种网络结构熵可以更有效地反映网络的结构特征, 能够更为合理地解释稀疏网络及星型网络的结构差异.蔡萌等[41]针对以往用以度量网络异构型不足问题引入网络流的概念, 综合考虑径向测度和中间测度,提出一种新的网络结构熵, 能够从全局刻画网络的真实结构, 但这种网络结构熵并不是单独考虑网络的静态拓扑结构, 而是从流量角度刻画网络真实结构, 复杂度较高.胡钢等[42]研究了节点与其直接相连的邻节点和一次间接相连的邻节点之间的关联关系, 提出了节点邻接信息熵算法, 并以节点的信息熵数值大小表征节点在网络中的重要性程度.陈单等[43−45]以通信能力函数矩阵为基础引入香农熵理论, 并提出通信序列熵的概念.由于网络节点间的通信能力函数考虑了节点之间的所有可能路径,所以通信序列熵能完整地体现网络的整体拓扑性质, 可以作为网络之间的差异性的衡量指标.
本文基于网络通信序列熵理论, 分析不同类型网络通信序列熵与网络承载能力的数量变化关系,以明确网络的拓扑结构的特征对传输容量的影响.系统地研究了无标度网络和小世界网络的通信序列熵和传输容量之间的关联特性.最终的研究结果表明, 对于无标度网络和小世界网络而言, 它们的通信序列熵与传输容量成正关联.这一发现对构建高效率的传输网络具有一定指导意义.
2 方 法
2.1 通信序列熵
一个无权无向网络可以用N×N的邻接矩阵A表示节点之间的连接关系.如果网络中的节点i和节点j直接相连, 则邻接矩阵A中的元素aij=1 ,否则aij=0.Estrada 等[46−48]根据网络中节点之间相互到达的所有路径与该网络的幂次邻接矩阵之间的关系, 并考虑到在节点间较短的路径对节点的通信能力影响比较大, 因此将较短的路径赋予较大的权重, 用正值表示网络中节点间的通信能力,提出了可用来表示网络节点之间的通信能力的矩阵CA:
通信能力矩阵CA的第i行第j列的元素(ca)ij代表节点i和节点j之间的通信能力,l表示两个节点之间的路径长度.当i=j时, (ca)ij是节点的子图中心性, 表示节点的自通信能力(本次研究暂不考虑).为方便计算, 首先使用矩阵论中的矩阵分解A=Q ∧Q−1, 然后求出通信能力矩阵CA=eA=Qe∧Q−1, 其中Q为标准正交基组成的正交矩阵.
通信序列熵的概念描述如下: 首先将通信能力矩阵的对角线上方的元素取出来存储到通信序列元素集合B=[(ca)12,(ca)13, ··· ,(ca)1N; (ca)23,(ca)24, ··· ,(ca)2N;···], 然后根据香农熵理论计算概率集合P=[P1,P2, ··· ,PM] ,M=N(N −1)/2 ,其中集合P中的元素为(1 ≤l≤M,1 ≤i 定义通信序列标准熵为 本文用到的通信序列熵为通信序列标准熵. 复杂网络的传输容量是衡量网络传输性能的重要指标, 衡量网络传输容量的模型为流量模型.流量模型用来描述数据包在网络的传输过程, 并可判断网络从自由态到拥塞态的相变.本文采用了复杂网络研究中经典的流量模型[49−51], 具体描述如下: 1)节点有主机和路由功能, 即节点本身同时具有产生、接收、转发数据包的功能.节点尾部设置缓存队列, 用来存储节点自身产生和来自其他节点的数据包, 此缓存队列设置为无穷大.数据包进出缓存队列时采用先进先出的规则. 2)数据包产生: 每个时间步内, 网络中会生成R个数据包, 各个数据包的源节点s和目的节点d随机确定, 并且不能为同一节点. 3)数据包传输: 每个时间步内, 网络中的所有节点都具有相同的对数据包的处理能力C, 这种处理能力是节点每个时间步能处理的数据包数量. 4)数据包接收: 如果每个时间步内超过C个数据包需要处理, 则节点先对前C个数据包进行处理, 节点的缓存队列会对剩余的数据包进行保存,等待下一时间步内处理.如果数据包到达目的节点, 则被立即从网络中移除. 通过流量模型可以知道, 当节点处理能力C为有限值时, 随着数据包的生成速率R逐渐增大, 网络中的部分节点缓存队列堆积的数据包的数量越来越多, 造成这部分节点缓存队列中的数据包无法及时处理而越积越多, 最后数据包数量超过了网络的承受能力, 网络进入拥塞状态.数据包的生成速率R存在一个关键值Rc.当R 式 中〈∆W〉=W(t+∆T)−W(t) , 其 中,W(t) 表示在t时刻, 网络中所拥有的数据包的数目,∆W表示在 ∆T窗口时间内, 网络中的数据包数量的变化.当R 介数(betweenness centrality)可以表示节点在网络中的中心程度, 其最初的定义为在最短路由算法下经过节点i的最短路径条数[52]: 其中,σsd表示源节点s到达目的节点d之间的最短路径条数,σsd(i) 表 示从源节点s到达目的节点d的最短路径中经过节点i的最短路径条数.虽然介数的定义基于最短路径路由算法, 但是有很多已经存在的路由算法并不是以最短路径为基础.研究人员将介数的定义扩充为有效介数, 用以评估实际路由策略下网络的容量情况, 有效介数一般定义为[53] 其中表示节点i的有效介数,指在某种路由算法下从节点s到节点d之间的路径条数,表示从源节点s到达目的节点d的路径中通过节点i的条数. 可以使用介数对网络的传输容量进行理论评估[50],RBi/[N(N −1)] 表示每个时间步长内, 到达网络中任何一个节点i的平均数据包个数, 其中Bi/[N(N −1)] 表 示一个数据包到达介数为Bi的节点i的概率.如果RBi/[N(N −1)]>C, 那么数据包将在节点i上逐渐堆积, 网络拥塞现象将会发生.当保证网络中节点都不发生数据包堆积时, 那么所有的节点都应满足RBi/[N(N −1)]≤C, 整理此式可以得到下式: 其中Bmax表示网络中所有节点介数的最大值.网络传输容量Rc=CN(N −1)/Bmax为使得网络不发生拥塞的最大R值, 则从该式可以看出, 要想得到网络最大的传输容量, 可通过最小化网络中节点的最大介数.因此, 可以用网络中节点介数的最大值Bmax的变化来评估网络传输容量的变化情况. 在复杂网络数据包传输动力学行为研究过程中, 网络中度值较大的核心节点具有举足轻重的地位, 数据包传输过程中产生的拥塞现象与之息息相关.因此, 有效路由策略(efficient routing)[54]将网络中节点的度作为路由选择的代价函数, 假如从节点i到节点j的路径为P(i →j):=i ≡x0, x1, ··· ,xn−1,xn ≡j, 其代价函数为其中n为路径长度,a为控制参数.此次仿真采用的为有效路由策略且策略中的可调控制参数均为通过仿真得到的最优控制参数.设定网络节点规模为N=400 , 网络中数据包生成速率R=80 , 节点的处理能力C=1.采用文献[10]中的网络生成算法生成网络平均度为〈k〉=2m, 并且网络的度分布服从指数为γ=−3 的BA 无标度网络.采用文献[11]中的网络生成算法生成WS 小世界网络, 网络中任意节点都与它左右相邻的各 2 个节点相连, 重连概率P设置为从 0.1 至 0.9. 图1(a)和图1(b)分别给出了BA 无标度网络和WS 小世界网络的通信序列熵SN和网络的度分布P(k) 之间的关系.可以看出, 两种类型网络的通信序列熵在增大的时候, 网络的度值范围增大, 但网络中节点的度分布曲线从陡峭化向平缓状态发展, 网络愈加均匀.分析如下: 网络向均匀网络发展时, 通信序列元素集合B中的元素会变得更加均匀, 进而通信序列熵值会增大.随着网络通信序列熵的增大, BA 无标度网络的度分布并没有改变整体的幂律分布形状, WS 小世界网络的度分布则更加趋近于正态分布. 图2 和图3 给出了网络的通信序列熵与传输容量的关系.可以看出, 网络传输容量随着通信序列熵的增大而增大.理论分析如下: 网络的均匀性会随着网络节点之间的连接情况的改变而改变.当网络变得越来越稠密时, 网络通信序列熵中的元素数值彼此接近且均匀, 进而导致网络的通信序列熵增大.从网络的拓扑结构角度来看, 网络中许多非邻节点随着通信序列熵的增大或减小而进行连接或断开, 这些节点的度值会因此增大或减小, 使网络中原有的核心节点的影响降低或增大.网络的核心节点比例程度极大地影响网络的均匀性.当均匀性较低时, 网络中核心节点影响力高, 网络向非均匀性网络发展, 根据传统流量模型随机选取的两个节点之间的数据包传输路径经过网络的核心节点的概率高, 数据包将会通过网络的核心节点, 核心节点的处理能力是固定的, 那么数据包在核心节点的缓存队列中需要等待更长时间, 随着时间的延长, 网络就会处于一个拥塞状态.反之, 当均匀性程度较高时, 网络中核心节点影响力低, 网络向均匀性网络发展, 根据传统流量模型随机选取的两个节点之间的数据包传输路径经过网络的核心节点的概率低, 数据包传输将会经过更多的普通节点,舒缓了核心节点上的负载压力(数据包负载数目),网络不易拥塞.且本次路由策略选取的是有效路由的策略, 合理有效地避开了部分核心节点, 再一次降低了核心节点的影响力.对以上分析我们采取负载在节点分布的方法进行验证. 图1 网络的通信序列熵SN 与网络的度分布P(k)之间的关系图 (a) BA 无标度网络; (b) WS 小世界网络Fig.1.Rrelationship between the network’s communication sequence entropy SN and the network’s degree distribution P(k): (a) BA scale-free network; (b) WS small world network. 图2 (a)不同的通信序列熵的BA 无标度网络下, 有序参数H(R)与数据包生成率R 的关系; (b) BA 无标度网络通信序列熵SN与传输容量 R c 的关系.采用的路由策略为有效路由策略Fig.2.(a) Relationship between the order parameter H(R) and the packet generation rate R under BA scale-free network with different communication sequence entropy; (b) relationship between BA scale-free network communication sequence entropy S N and traffic capacity R c.The routing strategy adopted is an effective routing strategy. 图3 (a)不同的通信序列熵的WS 小世界网络下, 有序参数H(R)与数据包生成率R 的关系; (b) WS 小世界网络通信序列熵SN与传输容量 R c 的关系.采用的路由策略为有效路由策略Fig.3.(a) Relationship between the order parameters H (R) and the packet generation rate R under the WS small world network with different communication sequence entropy; (b) relationship between WS small world network communication sequence entropy SN and traffic capacity R c.The routing strategy adopted is an effective routing strategy. 图4 (a)和图4(b)所示为两种网络的节点度值上的数据包负载 (traffic load)分布.可以看出, 随着通信序列熵的增大, 数据包负载在各个不同度值大小的节点间的分布愈加缓和及均匀.核心节点和普通节点的数据包负载数目随着通信序列熵的增大渐渐地接近于相同的数值.数据包负载在传输过程中的分布愈加均匀, 进而使网络的传输容量整体提升, 所以BA 无标度网络及WS 小世界网络的传输容量随着网络的通信序列熵的增大而增大, 成正关联关系.通信序列熵亦可成为评估同种类型但不拓扑同结构网络的传输容量的指标. 图5(a)和图5(b)给出了网络的平均路径长度随通信序列熵的变化.可以看出, 网络的平均路径长度随着通信序列熵的增大反而减小.这是因为路由策略考虑的数据包在传输时尽量是避开核心节点, 对于数据包选择的路径而言, 节点之间间隔较短的路径上有度值较大的核心节点, 节点之间间隔远的路径上有度值较小的普通节点.由于随着网络通信序列熵的增大, 网络从稀疏状态向稠密状态发展, 使节点之间间隔远的路径上的非邻节点之间进行连接, 出现了许多的度值较大的节点, 使核心节点的地位降低.源节点和目的节点之间的数据包传输会经过更多新出现的度值较大节点, 经过更少的边.从而导致节点与节点之间的传输路径长度变小, 进而导致整个网络的平均路径减小, 会使数据包到达各个目的节点的平均时间整体降低, 提高了数据包整体的传输效率. 图4 数据包负载 (traffic load) 在网络中节点度值上的分布情况 (a) BA 无标度网络; (b) WS 小世界网络Fig.4.Distribution of traffic load on degree value of nodes in the network: (a) BA scale-free network; (b) WS small world network. 图5 网络的通信序列熵 S N 与平均路径长度 〈 L〉 的关系 (a) BA 无标度网络; (b) WS 小世界网络Fig.5.Relationship between communication sequence entropy SN and average path length 〈 L〉 in the network: (a) BA scale-free network; (b) WS small world network. 图6 网络的通信序列熵 S N 与节点的最大介数 B max 的关系 (a) BA 无标度网络; (b) WS 小世界网络Fig.6.Relationship between communication sequence entropy S N and the maximum betweenness of nodes B max in the network:(a) BA scale-free network; (b) WS small world network. 根据2.3 节得知, 网络中介数值最大的节点最先发生拥塞, 与网络传输容量成反比.通过仿真实验计算网络的传输容量非常耗时, 因此可以通过计算在不同路由策略下网络中所有节点的有效介数的最大值来间接评估网络的传输容量.通过对图6(a)和图6(b)的观察可以看出, 基于有效路由算法下,同等规模的网络通信序列熵值变化较快时, 网络的最大有效介数变化随之增快, 可见网络的节点最大介数敏感于通信序列熵的变化.当通信序列熵最大时, 网络中最大介数值最小, 传输容量最大.当通信序列熵最小时, 网络中最大介数值最大, 传输容量最小. 网络传输容量与其拓扑结构密切相关.本文引入了通信序列熵这一概念, 研究了不同网络拓扑结构与其通信序列熵的对应关系, 并探究网络通信序列熵与传输容量的关联性, 研究发现复杂网络的通信序列熵和网络的传输容量之间成正关联.随着网络通信序列熵的增大, 网络拓扑结构从非均匀网络性向均匀网络发展演化, 网络的均匀拓扑结构利于数据包的传输.在网络的传输动力学中, 可以通过提高网络的通信序列熵来优化网络的拓扑结构进而提高网络的整体传输能力.这些工作表明在未来的实际网络工程中, 可以通过增大网络的通信序列熵的方法来优化网络的传输容量.这对实际网络的设计与优化具有一定的参考价值, 我们将在未来的研究中着重研究通信序列熵的应用价值.
2.2 流量模型
2.3 理论评估
3 复杂网络通信序列熵与传输容量的关系
3.1 仿真数值的设置
3.2 仿真结果分析
4 结 论
