基于遗传算法的网络关键节点的自相似流量生成简化方法

摘要

本发明是一种基于遗传算法的网络关键节点的自相似流量生成简化方法，将网络流量分布用流量均值、方差和自相似参数决定，同时假定网络流量由边缘节点产生，且同一边缘节点在流量生成过程中请求同一网络业务。本方法构建网络拓扑结构图，确定关键节点和边缘节点；构建边缘节点开/关模型和模型初始值；通过遗传算法，确定边缘节点开/关模型参数的最优解；依据最优个体配置在边缘节点配置最优参数，进行仿真，获取仿真流量。本发明结合当前网络仿真试验实际，考虑网络流量按照其真实使用情况加载十分繁琐和耗时，为关键节点的流量生成提供了一种简化的输入方式，利用遗传算法快速找到仿真模型参数的优化解，节约了仿真时间，提升了仿真效率。

主权项

一种基于遗传算法的网络关键节点自相似流量生成简化方法，其特征在于，包括如下步骤：步骤1：构建网络拓扑结构图，获取网络的邻接矩阵A((a_ij)_n×n)，并确定边缘节点S和关键节点K；邻接矩阵中，当节点i,j相连时，a_ij＝1，否则a_ij＝0，n为网络中节点个数；设网络中只有边缘节点产生数据流量，且每个边缘节点的用户都始终使用同一种业务；步骤2：构建边缘节点开/关模型，确定模型参数初值；首先，对每个边缘节点，以等概率随机选择一个目标节点，设边缘节点S(i)的目标节点为T(j)，S(i)将数据沿路径发送到T(j)，边缘节点均按照如下开/关模型产生流量：(1)节点严格处于开或者关状态，且开、关状态严格交替；节点处于开状态时以恒定速率v产生数据，处于关状态时不产生数据；(2)节点的开/关状态的持续时间相互独立且均服从帕雷托(k,α)重尾分布，其中，α是随机变量的最小可能值，k是正的参数；(v,k,α)构成边缘节点开/关模型的参数组；然后，根据关键节点的目标流量统计特征：流量均值流量方差以及自相似参数H^*，配置边缘节点开/关模型的参数值：(1)速率M为关键节点的介数；(2)帕雷托(k,α)分布中α＝3‑2H^*，利用所得到的(v,k,α)统一配置边缘节点的开/关模型；步骤3：通过遗传算法，确定边缘节点开/关模型参数的最优解；步骤3的实现步骤如下：步骤3.1：确定目标函数，权值参数和种群大小；设置目标函数为三个目标u₁,u₂和u₃的优化函数：其中，H^sim、和分别是关键节点的仿真流量的自相似参数、流量均值和流量方差；设置权值参数G₁和G₂，G₁表示第一个目标所用的个体数量比重，G₂表示第二个目标所用的个体数量比重；设置种群大小NIND；步骤3.2：确定种群中的个体适应度；各边缘节点产生流量，根据下式确定当代种群中的个体x与目标流量的误差函数F(x)：$F\left(x\right)=\left\{\begin{array}{c}{F}_1\left(x\right)=|H^{sim}-H^{*}|/H^{*},x\in [1,G_1\times NIND+1)\\ F_2\left(x\right)=|F_{mean}^{sim}-F_{mean}^{*}|/F_{mean}^{*},x\in [G_1\times NIND,(G_1+G_2)\times NIND+1)\\ F_3\left(x\right)=|F_{\mathrm{var}}^{sim}-F_{\mathrm{var}}^{*}|/F_{\mathrm{var}}^{*},x\in \left[\right(G_1+G_2)\times NIND+1,NIND+1)\end{array}\right.$然后，确定个体x的适应度函数FitnV(x)：对于x∈[1,G₁×NIND+1)的个体，$FitnV\left(x\right)=\frac{2}{{\min }_{i=1}^{G_1\times NIND}{F}_1\left(i\right)-{\max }_{i=1}^{G_1\times NIND}{F}_1\left(i\right)}F\left(x\right)+\frac{2{\max }_{i=1}^{G_1\times NIND}{F}_1\left(i\right)}{{\max }_{i=1}^{G_1\times NIND}{F}_1\left(i\right)-{\min }_{i=1}^{G_1\times NIND}{F}_1\left(i\right)}$对于x∈[G₁×NIND+1,(G₁+G₂)×NIND+1)的个体，$FitnV\left(x\right)=\frac{2}{{\min }_{i=G_1\times NIND+1}^{(G_1+G_2)\times NIND}{F}_1\left(i\right)-{\max }_{i=G_1\times NIND+1}^{(G_1+G_2)\times NIND}{F}_2\left(i\right)}F\left(x\right)+\frac{2{\max }_{i=G_1\times NIND\mathrm{+1}}^{G_2\times NIND}{F}_2\left(i\right)}{{\max }_{i=G_1\times NIND+1}^{(G_1+G_2)\times NIND}{F}_2\left(i\right)-{\min }_{i=G_1\times NIND+1}^{(G_1+G_2)\times NIND}{F}_2\left(i\right)}$对于x∈[(G₁+G₂)×NIND+1,NIND+1)的个体，$FitnV\left(x\right)=\frac{2}{{\min }_{i=(G_1+G_2)\times NIND+1}^{NIND}{F}_3\left(i\right)-{\max }_{i=(G_1+G_2)\times NIND+1}^{NIND}{F}_3\left(i\right)}F\left(x\right)+\frac{2{\max }_{i=G_2\times NIND+1}^{NIND}{F}_3\left(i\right)}{{\max }_{i=(G_1+G_2)\times NIND+1}^{NIND}{F}_3\left(i\right)-{\min }_{i=(G_1+G_2)\times NIND+1}^{NIND}{F}_3\left(i\right)}$并根据式min(G₁×F₁(x)+G₂×F₂(x)+(1‑G₁‑G₂)F₃(x))选出并记录当代种群中精英个体；步骤3.3：选取遗传个体，进行交叉和变异，生成子代个体；首先，根据本代种群中个体的适应度对个体进行排序，将精英个体直接遗传至子代保留，对于剩余个体x确定被选入子代的概率P(x)：然后，采用轮循法选出进入子代的个体，在进入子代的个体中通过交叉和变异生成最终的子代种群；步骤3.4：判断当前是否达到最大仿真代数，若是，比较每一代种群的精英个体的误差函数值，选出误差函数值最小的个体作为最适应个体，输出当前所记录的最适应个体，然后执行步骤四，否则，对生成的种群转步骤3.2继续执行；步骤4：依据最适应个体配置边缘节点开/关模型的参数值，进行仿真获取仿真流量。