一种复杂网络环境下的拥塞控制方法

摘要

本发明公开一种复杂网络环境下的拥塞控制方法，首先对于给定的复杂网络建立BA网络模型。接着使用节点收缩算法，简化网络模型。然后使用节点重要度算法，计算网络中的关键节点的重要度。最后，结合邻居节点的重要度和网络负载情况，提出基于局部路由策略的复杂网络环境下的拥塞控制方法，对网络数据进行处理，缓解局部负载过重引起的拥塞。

说明书

技术领域

本发明涉及复杂网络环境下的控制方法的技术领域，具体涉及一种复杂网络环境下的拥塞控制方法。

背景技术

伴随着计算机技术、通信技术的飞速发展，越来越多的通信网络具有了如下特征：在构成上表现为单个子网都是简单网络如传输网、移动网等；在结构上表现为不同时期的多种结构的网络并存，由集中式逐步向分布式发展；在应用上表现为由单一，简单的功能向多样，多层与多态发展；在服务上表现为越来越注重性能，品质与安全在技术上表现为多种技术并存，相互融合。由于这些通信网络既不同于以往构成简单，结构清晰，功能单一的简单网络，也不等同于简单网络的复合叠加，而是在网络构成，网络模型，网络技术和网络管理方面都呈现出新的特征，无法直接用传统的理论分析，这样的网络统称为复杂网络。

随着网络的发展，网络规模越来越大，网络的拥塞控制问题也日趋复杂。由于网络拥塞控制算法的分布性，网络的复杂性，对算法性能要求高等原因使得拥塞控制算法的设计具有很高的难度。

拥塞的产生主要取决于路由器对数据包采取的路由选择方式。路由策略为数据包选择传输路线，本身不会导致拥塞的发生，但当网络拥塞时，差的路由策略会进一步加剧网络拥塞，而好的路由策略能够在不改变底层基础架构的情况下提高网络信息处理效率。因此采用好的路由策略，能提高网络的吞吐量，改善网络拥塞，例如利用局部拥塞信息将发生拥塞的节点上的数据包重分布到其他节点上去阻止拥塞的加剧。

发明内容

发明目的：本发明目的在于针对现有技术的不足，提供一种复杂网络环境下的拥塞控制方法，在复杂网络环境下中，考虑节点的重要度，提出局部路由策略，对网络数据进行处理，缓解局部负载过重引起的拥塞。

为了解决上述技术问题，本发明包括以下步骤：

S1、给定一个复杂网络，输入复杂网络系统信息包括系统产生数据包个数、系统产生数据包个数临界负载量、系统拓扑关系、节点之间距离、节点的度；

S2、对于给定的复杂网络，建立BA网络模型；

S3、使用节点收缩算法，对建立的BA网络模型进行简化；

S4、使用节点重要度算法，对节点重要度进行评估；

S5、结合邻居节点的重要度和网络负载情况，提出基于局部路由策略的复杂网络环境下的拥塞控制方法。

作为本发明的进一步改进，在步骤S2中，BA网络模型的描述如下：对于给定的复杂网络，假设网络中的每个节点都具有路由，收包，发包等功能，每一段时间内系统产生的数据包个数为R，源节点和目标节点的选择是随机的，源节点和目标节点不一样；节点i在每个时间步内向邻居节点发送数据包的最大个数为v

作为本发明的进一步改进，在步骤S3中，节点收缩算法如下：通过融合，把节点与它周围的所有连接节点凝聚成一个节点，设m为图G中的一个节点，把与节点m相连的K个节点及节点m融合在一起，节点m就把它周围的K个节点通过收缩凝聚成了一个节点，节点m收缩后所得到的用图G*m表示，节点m越重要，则收缩后得到的网络凝聚程度越高，图G的凝聚程度由网络中各个节点之间的连通力f(G)决定，定义为节点数n与平均路径长度l乘积的倒数，用f(G)表示：

作为本发明的进一步改进，在步骤S4中，节点重要度算法如下：节点m的重要度用IMG(m)表示：

上式中，G表示节点m收缩前的图，G*m表示节点m收缩后所得到的图，节点m的重要度由图G和m收缩后的图G*m的凝聚度决定；将公式(2)带入公式(1)得到：

作为本发明的进一步改进，在步骤S5中，基于节点重要度的局部路由策略根据邻居节点的重要度以及网络负载情况动态调整数据包的发送概率，网络的状态通过临界负载量R

上述公式设为公式(4)，其中IMG(q)表示邻居节点的重要度；c表示m的邻居节点的总数；α是调整系数，α

有益效果：通过本发明提供的步骤，可以在复杂网络环境下中，首先对于给定的复杂网络建立BA网络模型。接着使用节点收缩算法，简化网络模型。然后使用节点重要度算法，计算网络中的关键节点的重要度。最后，结合邻居节点的重要度和网络负载情况，提出基于局部路由策略的复杂网络环境下的拥塞控制方法，对网络数据进行处理，缓解局部负载过重引起的拥塞。

附图说明

图1为本发明的流程图。

图2为本发明的具体实施例中，在没有发生拥塞时，α与拥塞相变点R

图3为本发明的具体实施例中，在发生拥塞时，α与拥塞相变点R

图4为本发明的具体实施例中，不同路由策略下的平均传输时延比较图。

图5为本发明的具体实施例中，不同路由策略下的带宽利用率的比较图。

具体实施方式

下面通过附图对本发明技术方案进行详细说明，但是本发明的保护范围不局限于所述实施例。

本发明的步骤包括：

S1、给定一个复杂网络，输入复杂网络系统信息包括系统产生数据包个数、系统产生数据包个数临界负载量、系统拓扑关系、节点之间距离、节点的度；信息系统数据包括监视功能涉及元件种类和个数、元件逻辑结构、元件可靠性概率，输入电力系统数据包括电力系统元件可靠性概率、系统潮流约束、电网节点输入输出概率、线路阻抗等。

S2、对于给定的复杂网络，建立BA网络模型；BA网络模型的描述如下：对于给定的复杂网络，假设网络中的每个节点都具有路由，收包，发包等功能，每一段时间内系统产生的数据包个数为R，源节点和目标节点的选择是随机的，源节点和目标节点不一样；节点i在每个时间步内向邻居节点发送数据包的最大个数为v

S3、使用节点收缩算法，对建立的BA网络模型进行简化；节点收缩算法如下：通过融合，把节点与它周围的所有连接节点凝聚成一个节点，设m为图G中的一个节点，把与节点m相连的K个节点及节点m融合在一起，节点m就把它周围的K个节点通过收缩凝聚成了一个节点，节点m收缩后所得到的用图G*m表示，节点m越重要，则收缩后得到的网络凝聚程度越高，图G的凝聚程度由网络中各个节点之间的连通力f(G)决定，定义为节点数n与平均路径长度l乘积的倒数，用f(G)表示：

S4、使用节点重要度算法，对节点重要度进行评估；节点重要度算法如下：节点m的重要度用IMG(m)表示：

上式中，G表示节点m收缩前的图，G*m表示节点m收缩后所得到的图，节点m的重要度由图G和m收缩后的图G*m的凝聚度决定；将公式(2)带入公式(1)得到：

节点m的重要度IMG(m)主要由节点m在网络中的位置和节点m的度k

S5、结合邻居节点的重要度和网络负载情况，提出基于局部路由策略的复杂网络环境下的拥塞控制方法。基于节点重要度的局部路由策略根据邻居节点的重要度以及网络负载情况动态调整数据包的发送概率，网络的状态通过临界负载量R

上述公式设为公式(4)，其中IMG(q)表示邻居节点的重要度；c表示m的邻居节点的总数；α是调整系数，α

具体的实施例：

本实施例给定的复杂网络结构为，节点数N＝10000，M＝5，节点的度分布p(k)具有幂律特性，p(k)～K

在没有发生拥塞时，α与拥塞相变点R

在发生拥塞时，α与拥塞相变点R

平均传输时延是反映网络路由策略效能的重要指标之一，不同路由策略下的平均传输时延比较如图4所示。由图4可以看出，当R较小时，传输时延略大于传统最短路径路由。传统最短路由策略在R较小时能够保持较低的传输时延，但是随着R的增加其平均传输时延也迅速增大。使用本方法在发生拥塞时，网络平均传输时大大小于传统控制方式。

不同路由策略下的带宽利用率的比较如图5所示，横坐标是节点数N。由图5可知，使用本方法时带宽利用率小于传统控制方式，特别是在N较大时，使用本方法时的带宽利用率大大高于传统控制方式，优势明显且能保持。

如上所述，根据实施例可以看出所提方法可以有效提升复杂网络拥塞情情况下的网络容量。

如上所述，尽管参照特定的优选实施例已经表示和表述了本发明，但其不得解释为对本发明自身的限制。在不脱离所附权利要求定义的本发明的精神和范围前提下，可对其在形式上和细节上作出各种变化。