山东科技大学 学 科辆 ２第３０１５４年８卷第４月 期 ＶＡＯｕｇ１．３４ ＮＯ ４ ．２０１５ 中交通枢纽站点的转运能力和容纳能力等。②网络中连接边的容量（带宽）资源的有限性。主要是指网络中 连接边在单位时间运送数据包的能力［２－４］，如通信网络的传输带宽限制、交通道路上承载车流量的能力等。 本研究主要分析网络传输过程中，网络节点资源有限条件下的网络传输负载能力。在所有复杂网络传 输研究中都会考虑节点处理能力的问题，而为了简化研究，多数研究都把节点容量假设为无限大［１＿８¨，因此， 本研究中节点资源约束主要从节点容量资源有限方面考虑。为了着重突出节点容量资源限制对复杂网络传 输的影响，暂不考虑连接边的带宽限制。 １ 节点容量资源限制下的复杂网络流量模型 为研究节点资源限制下的网络传输性能，构建带有节点容量限制的流量模型。这个模型中，网络中所有 节点被看作是主机和路由器的结合体。假设网络传输从零负载开始，每单位时间内新加入Ｒ个数据包，每 个新加入的数据包随机地在网络中选择出发节点和目的节点，到达目的节点后的数据包自动从网络上移除。 每个节点处理数据包的能力为Ｃ 。假设网络中总的节点容量为Ｌ ，节点ｉ所能容纳的数据包的最大缓冲队 列长度为Ｌ 。当某一节点中的数据包数量达到该节点的缓冲区队列长度上限时，则该节点不再产生新的数 据包，同时也不再接收其他数据包的进入，直到该节点有数据包传出，腾出缓冲队列空间。在每个节点缓冲 队列中等待发送的数据包都是按照先入先出（ｆｉｒｓｔ ｉｎ ｆｉｒｓｔ ｏｕｔ，ＦＩＦＯ）的规则按顺序进行处理。节点间连接 边的运送能力不受限制。 ２节点容量的分配方式 网络中总节点容量固定情况下，节点容量分配方式分为两类。 １）匀质化节点容量分配（平均分配），是指把具有Ｎ个节点的网络的总节点容量平均分配给每个节点， 即：任意节点ｉ的容量为 Ｔ Ｌ 一Ｌ ．ｑｒ。 （１） ２）异质化节点容量分配，即把节点容量按照下面两种方式分配。 ①根据网络中节点的度ｋ分配节点容量： 厶 Ｌ 一｝②根据网络节点的介数ｇ 。 分配节点容量： Ｌ 一］ ｊ＝１ Ｌ 。 （２） ∑ｋ， Ｌ ｑ。 （３） ∑ｇ 厶＇ ３ 仿真分析 采用不同的节点容量分配方案，对复杂网络传输问题进行研究。分别选取Ｅｒｄｂｓ—Ｒ６ｎｙｉ（ＥＲ）随机网 络 、Ｗａｔｔｓ—Ｓｔｒｏｇａｔｚ（ｗＳ）小世界网络［１ 和Ｂａｒａｂｄｓｉ—Ａｌｂｅｒｔ（ＢＡ）无标度网络ｌｌ】 作为网络仿真的拓扑平 台。网络规模都为Ｎ一１００个节点，平均度＜ｋ）一４，每个节点的处理能力Ｃ 一１０，网络总的节点容量 Ｌ 一１ ０００。仿真数据结果取５Ｏ次独立实验结果的平均值。 仿真中的具体流量模型描述如下：网络中的每个节点仍被看作具备主机和路由器的功能，具有产生、接 收和转发数据包的能力；每个节点处理数据包能力为Ｃ ；网络中总的节点容量为Ｌ ，节点ｉ的容量为Ｌ （分 别为式（１）、式（２）、式（３）），当节点达到其容量上限时，数据包在该节点既不会产生也不会流人，直到有数据 包流出，腾出缓冲区空间；数据包传递仍然遵循ＦＩＦＯ原则。路由策略分别采用最短路径路由（ｓｈｏｒｔｅｓｔ ｐａｔｈ ｒｏｕｔｉｎ，ＳＰＲ）策略和文献［４］中基于全局和局部信息（Ｇ—Ｌ）的路由策略，其中ａ＝＝＝０．７。 于灏等 Ｊｏｕｒｎａｌ ｏｆ Ｓｈａｎｄｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ 节点容量资源限制下的复杂网络传输过程分析 Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ （Ｒ）一ｌｉｍ—ＡＷ （ｔ）一网络传输过程中的流量状态变化使用状态相变参数 来描述口 ¨］： 。 （４） 一．。。』 其中，Ｗ（ ）为ｔ时刻网络中总的数据包数量。在网络流量状态由自由流状态向拥塞状态转变过程中，存在 一个数据包产生率的临界值Ｒ 。当Ｒ＜Ｒ。时，网络系统中产生的数据包和到达目标节点的数据包数量基 本相抵，此时叩值近似为零，网络传输系统处于稳定的自由流状态；当Ｒ＞Ｒ 时，网络传输系统不能及时、完 全地消化新产生的数据包，此时网络传输系统进入拥塞状态，且 值伴随着数据包产生速率Ｒ的增加而增 大，同时 值越大，显示拥塞程度越高。最终 一１时，网络传输系统处于完全堵塞状态，此时代表网络中新 产生的数据包一个都不能传出，全部滞留在网络中。网络传输性能的关键指标值仍然用流量状态相变临界 值Ｒ。来衡量。 １）节点容量资源匀质化分配时，即Ｌ 一Ｌ。／Ｎ。 图１是分别采用最短路径路由策略（ＳＰＲ）和Ｇ—Ｌ路由策略时，ＥＲ随机网络上数据包产生率反映的流 量状态变化情况。图２是分别采用ＳＰＲ和Ｇ—Ｌ路由策略时，ＷＳ小世界网络上数据包产生率反映的流量状 态变化情况。图３是分别采用ＳＰＲ和Ｇ—Ｌ路由策略时，ＢＡ无标度网络上数据包产生率反映的流量状态变 化情况。 Ｏ．ＯＯ ０．００ 图１“平均”分配方式下ＥＲ网络流量 Ｆｉｇ．１ Ｕｓｉｎｇ“ｅｑｕａｌ ｄｉｖｉｓｉｏｎ”ａｌｌｏｃａｔｉｏｎ，ｔｒａｆｆｉｃ ｉｎ ＥＲ ｎｅｔｗｏｒｋ 图２“平均”分配方式下ＷＳ网络流量 Ｆｉｇ．２ Ｕｓｉｎｇ“ｅｑｕａｌ ｄｉｖｉｓｉｏｎ”ａｌｌｏｃａｔｉｏｎ， ｔｒａｆｆｉｃ ｉｎ ＷＳ ｎｅｔｗｏｒｋ ２）节点容量资源根据节点度进行分配时，即Ｌ 一 Ｎ Ｌｑ Ｉ ７ ＝ｉ。 ｌ 图４是分别采用ＳＰＲ和Ｇ—Ｌ路由策略时，ＥＲ随 机网络上数据包产生率反映的流量状态变化情况。图 ５是分别采用ＳＰＲ和Ｇ—Ｌ路由策略时，ＷＳ小世界网 络上数据包产生率反映的流量状态变化情况。图６是 分别采用ＳＰＲ和Ｇ—Ｌ路由策略时，ＢＡ无标度网络上 数据包产生率反映的流量状态变化情况。 ３）节点容量资源根据节点度进行分配时，即Ｌ 一 Ｎ Ｏ ＯＯ ０ ２０ 尺 ４０ ６０ Ｌｑｇ ／∑ｇ 。 Ｊ＝１ 图３ “平均”分配方式下ＢＡ网络流量 Ｆｉｇ．３ Ｕｓｉｎｇ“ｅｑｕａｌ ｄｉｖｉｓｉｏｎ”ａｌｌｏｃａｔｉｏｎ，ｔｒａｆｆｉｃ ｎ ＢＡ ｎｅｔｗｏｒｋ 图７是分别采用ＳＰＲ和Ｇ—Ｌ路由策略时，ＥＲ随 学 科学版 ７０ 第３２Ｏ１５４年８卷第４月 期 ＶＡＯｕＩｇ． ３２４０ Ｎ１５Ｏ ４ 机网络上数据包产生率反映的流量状态变化情况。图８是分别采用ＳＰＲ和Ｇ—Ｌ路由策略时，ＷＳ小世界网 络上数据包产生率反映的流量状态变化情况。图９是分别采用ＳＰＲ和Ｇ—Ｌ路由策略时，ＢＡ无标度网络上 数据包产生率反映的流量状态变化情况。 ０．０４ Ｏ．Ｏ２ ０．０Ｏ Ｏ ２Ｏ ４０ ６０ ８０ １００ ＪＲ 图４“度”分配方式下ＥＲ网络流量 Ｆｉｇ．４ Ｕｓｉｎｇ“ｄｅｇｒｅｅ”ａｌｌｏｃａｔｉｏｎ， ｔｒａｆｆｉｃ ｉｎ ＥＲ ｎｅｔｗｏｒｋ ０．０４ ０．０２ Ｏ．ＯＯ ０ ２０ ４０ ６Ｏ 尺 图６“度”分配方式下，ＢＡ网络流量 Ｆｉｇ．６ Ｕｓｉｎｇ“ｄｅｇｒｅｅ”ａｌｌｏｃａｔｉｏｎ， ｔｒａｆｆｉｃ ｉｎ ＢＡ ｎｅｔｗｏｒｋ ０ ２０ ４０ ６Ｏ ８０ １００ Ｒ 图８“介数”分配方式下。ＷＳ网络流量 Ｆｉｇ．８ Ｕｓｉｎｇ“ｂｅｔｗｅｅｎｎｅｓｓ”ａｌｌｏｃａｔｉｏｎ， ｔｒａｆｆｉｃ ｉｎ ＷＳ ｎｅｔｗｏｒｋ ０．０４ ０．Ｏ２ ０ ＯＯ ０ ２０ ４０ ６０ ８０ 尺 图５“度”分配方式下ＷＳ网络流量 Ｆｉｇ．５ Ｕｓｉｎｇ“ｄｅｇｒｅｅ”ａｌｌｏｃａｔｉｏｎ， ｔｒａｆｆｉｃ ｉｎ ＷＳ ｎｅｔｗｏｒｋ Ｏ ２０ ４０ ６０ ８０ １００ ｌ２０ Ｒ 图７“介数”分配方式下ＥＲ网络流量 Ｆｉｇ．７ Ｕｓｉｎｇ“ｂｅｔｗｅｅｎｎｅｓｓ”ａｌｌｏｃａｔｉｏｎ， ｔｒａｆｆｉｃ ｉｎ ＥＲ ｎｅｔｗｏｒｋ 图９“介数”分配方式下。ＢＡ网络流量 Ｆｉｇ．９ Ｕｓｉｎｇ“ｂｅｔｗｅｅｎｎｅｓｓ”ａｌｌｏｃａｔｉｏｎ， ｔｒａｆｆｉｃ ｉｎ ＢＡ ｎｅｔｗｏｒｋ 于灏等 Ｊｏｕｒｎａｌ ｏｆ Ｓｈａｎｄｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ 节点容量资源限制下的复杂网络传输过程分析 ＮａｔｕｒａＩ Ｓｃｉｅｎｃｅ 对比三种节点容量资源分配方案可以看出，无论在哪种网络中，相同节点容量分配时采用Ｇ－Ｌ路由策 略的网络负载能力都要优于采用最短路由策略（ＳＰＲ）的网络负载能力。对比ＥＲ随机网络下分别采用三种 节点容量分配方案的网络最大负载能力（如图１、图４、图７）发现，当采用同一种路由策略时，节点容量资源 根据网络节点介数分配时网络负载能力最大，其次是根据网络节点度来分配节点容量资源，而根据网络节点 容量资源平均分配时最小。同样，在ＷＳ小世界网络和ＢＡ无标度网络中，也存在同样的情况。因此，比较 这三种节点容量资源分配方式，根据网络节点介数分配节点容量资源的方案是使得网络传输性能最优的最 佳方案。 ４ 结束语 节点容量的限制是造成传输不畅、产生网络拥塞的主要原因之一。考虑节点容量受限条件下的传输以 及合理分配节点容量，对缓解网络传输拥塞、提高网络负载能力具有重要意义。 重点研究网络节点容量资源限制下的复杂网络传输问题，构建了带有节点容量限制的复杂网络传输流 量模型。根据模拟结果，得出基于节点介数的节点容量分配方案对提高网络传输性能具有优势的结论。 在实际应用中，介数作为一种既定网络规模下的全局信息，在网络规模巨大或是动态时变网络结构的环 境中，不易精确地获取，因此，在进一步的研究工作中，选取对应实际系统的“有效介数”替代理论介数将是一 项有意义的工作。 参考文献： ［１］Ｙａｎ Ｇ。Ｚｈｏｕ Ｔ Ｂ，Ｈｕ Ｂ Ｈ．Ｅｆｆｉｃｉｅｎｔ ｒｏｕｔｉｎｇ ｏｎ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ［Ｊ］．Ｐｈｙｓｉｃａｌ Ｒｅｖｉｅｗ Ｅ，２００６，７３：０６４１０８． ［２３Ｌｉｎｇ Ｘ，Ｈｕ Ｍ Ｂ，Ｄｕ Ｗ Ｂ，ｅｔ ａ１．Ｂａｎｄｗｉｄｔｈ ａｌｌｏｃａｔｉｏｎ ｓｔｒａｔｅｇｙ ｆｏｒ ｔｒａｆｆｉｃ ｓｙｓｔｅｍｓ ｏｆ ｓｃａｌｅ—ｆｒｅｅ ｎｅｔｗｏｒｋ［Ｊ］．Ｐｈｙｓｉｃｓ Ｌｅｔｔｅｒｓ Ａ，２Ｏ１０，３７４（４８）：４８２５ ４８３０． Ｅ３３于灏，周玉成，井元伟，等．固定带宽下的无标度网络数据传输流量分析［Ｊ］．东北大学学报：自然科学版，２０１０，３１（９）：１２２６—１２２９． Ｙｕ Ｈａｏ。Ｚｈｏｕ Ｙｕ Ｃｈｅｎｇ，Ｊｉｎｇ Ｙｕａｎｗｅｉ，ｅｔ ａ１．Ｄｙｎａｍｉｃ ａｎａｌｙｓｉｓ ｏｆ ｓｃａｌｅ—ｆｒｅｅ ｎｅｔｗｏｒｋ ｔｒａｆｆｉｃ ｗｉｔｈ ｆｉｘｅｄ ｂａｎｄｗｉｄｔｈ［Ｊ］．Ｊｏｕｒ— ｈａｌ ｏｆ Ｎｏｒｔｈｅａｓｔｅｒｎ Ｕｎｉｖｅｒｓｉｔｙ：Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ，２０１０，３１（９）：１２２６—１２２９． ［４］于灏，周玉成，井元伟，等．异质化带宽分配下的复杂网络数据流负载问题研究［Ｊ］．物理学报，２０１３，６２（８）：０８０５０２． Ｙｕ Ｈａｏ，Ｚｈｏｕ Ｙｕ Ｃｈｅｎｇ，Ｊｉｎｇ Ｙｕａｎｗｅｉ，ｅｔ ａ１．Ｓｔｕｄｙ ｏｎ ｔｒａｆｆｉｃ ｄｙｎａｍｉｃｓ ｏｆ ｔｈｅ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ ｗｉｔｈ ｔｈｅ ｈｅｔｅｒｏｇｅ ｎｅｏｕｓ ｂａｎｄｗｉｄｔｈ ａｌｌｏｃａｔｉｏｎ［Ｊ］．Ａｃｔａ Ｐｈｙｓｉｃａ Ｓｉｎｉｃａ，２０１３，６２（８）：０８０５０２． ［５］于灏，马妍，王新华，等．随机带宽分配对复杂网络传输性能的影响分析［Ｊ］．复杂系统与复杂性科学，２０１５（１）：８Ｏ一８４． Ｙｕ Ｈａｏ，Ｍａ Ｙａｎ，Ｗａｎｇ Ｘｉｎｈｕａ，ｅｔ ａ１．Ｉｍｐａｃｔ ｏｆ ｒａｎｄｏｍ ｂａｎｄｗｉｄｔｈ ａｌｌｏｃａｔｉｏｎ ｏｎ ｔｒａｎｓｍｉｓｓｉｏｎ ｏｆ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ［Ｊ］． Ｃｏｍｐｌｅｘ Ｓｙｓｔｅｍ Ｃｏｍｐｌｅｘｉｔｙ Ｓｃｉｅｎｃｅ，２０１５（１）：８０—８４． ［６］ｔｈｅｎ Ｚ Ｙ，Ｗａｎｇ Ｘ Ｆ．Ａ ｃｏｎｇｅｓｔｉｏｎ ａｗａｒｅｎｅｓｓ ｒｏｕｔｉｎｇ ｓｔｒａｔｅｇｙ ｆｏｒ ｓｃａｌｅ—ｆｒｅｅ ｎｅｔｗｏｒｋｓ ｗｉｔｈ ｔｕｎａｂｌｅ ｃｌｕｓｔｅｒｉｎｇ［Ｊ］．Ｐｈｙｓｉｃａ Ａ：Ｓｔａｔｉｓｔｉｃａｌ Ｍｅｃｈａｎｉｃｓ ａｎｄ Ｉｔｓ Ａｐｐｌｉｃａｔｉｏｎｓ，２００６，３６４：５９５—６０２． ［７］王丹，于灏，井元伟，等．基于感知流量算法的复杂网络拥塞问题研究［Ｊ］．物理学报，２００９，５８（１０）：６８０２—６８０８． Ｗａｎｇ Ｄａｎ，Ｙｕ Ｈａｏ，Ｊｉｎｇ Ｙｕａｎｗｅｉ，ｅｔ ａ１．Ｓｔｕｄｙ ｏｎ ｔｈｅ ｃｏｎｇｅｓｔｉｏｎ ｉｎ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋ ｂａｓｅｄ ｏｎ ｔｒａｆｆｉｃ ａｗａｒｅｎｅｓｓ ａｌｇｏｒｉｔｈｍ ［Ｊ］．Ａｃｔａ Ｐｈｙｓｉｃａ Ｓｉｎｉｃａ，２００９，５８（１０）：６８０２—６８０８． ［８］Ｗａｎｇ Ｄ，Ｊｉｎｇ Ｙ Ｗ，Ｚｈａｎｇ Ｓ Ｙ．Ｔｒａｆｆｉｃ ｄｙｎａｍｉｃｓ ｂａｓｅｄ ｏｎ ａ ｔｒａｆｆｉｃ ａｗａｒｅｎｅｓｓ ｒｏｕｔｉｎｇ ｓｔｒａｔｅｇｙ ｏｎ ｓｃａｌｅ－ｆｒｅｅ ｎｅｔｗｏｒｋｓ［Ｊ］． Ｐｈｙｓｉｃａ Ａ：Ｓｔａｔｉｓｔｉｃａｌ Ｍｅｃｈａｎｉｃｓ ａｎｄ Ｉｔｓ Ａｐｐｌｉｃａｔｉｏｎｓ，２００８，３８７：３００１—３００７． ［９］张国清，程苏琦．，ｌ、世界网络中的删边扩容效应［Ｊ］．中国科学：信息科学，２０１２，４２（２）：１５１—１６０． Ｚｈａｎｇ Ｇｕｏｑｉｎｇ，Ｃｈｅｎｇ Ｓｕｑｉ．Ｅｎｈａｎｃｉｎｇ ｎｅｔｗｏｒｋ ｃａｐａｃｉｔｙ ｅｆｆｅｃｔｓ ｏｆ ｅｄｇｅ－ｒｅｍｏｖａｌ ｉｎ ｓｍａｌｌ—ｗｏｒｌｄ ｎｅｔｗｏｒｋｓ［Ｊ］．Ｓｃｉｅｎｃｅ Ｃｈｉｎａ： Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅｓ，２０１２，４２（２）：１５１－１６０． ［１０］Ｅｒｄ６ｓ Ｐ，Ｒ６ｎｙｉ Ａ．Ｏｎ ｒａｎｄｏｍ ｇｒａｐｈｓＥＪ］．Ｐｕｂｌｉｃａｔｉｏｎｅｓ Ｍａｔｈｅｍａｔｉｃａｅ，１９５９，６：２９０—２９７． ｒ１１］Ｗａｔｔｓ Ｄ Ｊ，Ｓｔｒｏｇａｔｚ Ｓ Ｈ．Ｃｏｌｌｅｃｔｉｖｅ ｄｙｎａｍｉｃｓ ｏｆ‘ｓｍａｌｌ—ｗｏｒｌｄ’ｎｅｔｗｏｒｋｓ［Ｊ］．Ｎａｔｕｒｅ，１９９８，３９３（６６８４）：４４０—４４２． ［１２］Ｂａｒａｂｄｓｉ Ａ Ｌ．Ａｌｂｅｒｔ Ｒ．Ｅｍｅｒｇｅｎｃｅ ｏｆ ｓｃａｌｉｎｇ ｉｎ ｒａｎｄｏｍ ｎｅｔｗｏｒｋｓ［Ｊ］．Ｓｃｉｅｎｃｅ，１９９９，２８６（５４３９）：５０９—５１２． ［１３］Ａｒｅｎａｓ Ａ，Ｃａｂｒａｌｅｓ Ａ，Ｄｉａｚ—Ｇｕｉｌｅｒａ Ａ，ｅｔ ａ１．Ｓｅａｒｃｈ ａｎｄ ｃｏｎｇｅｓｔｉｏｎ ｉｎ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ［Ｊ］．Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｐｈｙｓｉｃｓ， ２００３，６２５：１７５－１９４． ｒ１４］Ａｒｅｎａｓ Ａ，Ｄａｎｏｎ Ｌ，Ｄｉａｚ—Ｇｕｉｌｅｒａ Ａ，ｅｔ ａ１．Ｌｏｃａｌ ｓｅａｒｃｈ ｗｉｔｈ ｃｏｎｇｅｓｔｉｏｎ ｉｎ ｃｏｍｐｌｅｘ ｃｏｍｍｕｎｉｃａｔｉｏｎ ｎｅｔｗｏｒｋｓ［Ｊ］．Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，２００４，３０３８：１０７８—１０８５． （责任编辑：吕文红）
