一种网络动态负载均衡的实现方法与系统

摘要

本发明实施例公开了一种网络动态负载均衡的实现方法与系统，所述方法包括：将大型分布式系统网络划分为若干个局部区域，初始化所述局部区域内的网络拓扑结构种群；在所述局部区域内根据多个约束条件构建多目标函数，根据所述多目标函数计算种群中个体的个体适应度，并选择适应度较高的个体作为父代；对所述父代执行遗传算子，形成子代；将所述子代代入所述多目标函数中计算其后悔值，并判断所述子代的后悔值是否小于所述父代的后悔值；当判断结果为是，则以所述子代替换所述父代形成新的种群；当判断结果为否，则舍弃所述子代。本发明所述系统可以用于实现所述方法。本发明技术方案采用分布式策略，算法简单，且具有良好的适应性。

主权项

一种网络动态负载均衡的实现方法，其特征在于，包括：将大型分布式系统网络划分为若干个局部区域，初始化所述局部区域内的网络拓扑结构，并随机选择偶数个所述网络拓扑结构的个体作为初始的种群；在所述局部区域内根据多个约束条件构建多目标函数，根据所述多目标函数计算种群中个体的个体适应度，并选择适应度较高的个体作为父代；对所述父代执行遗传算子，形成子代；将所述子代代入所述多目标函数中计算其后悔值，并判断所述子代的后悔值是否小于所述父代的后悔值；当判断结果为所述子代的后悔值小于所述父代的后悔值，则以所述子代替换所述父代形成新的种群，并判断是否满足终止条件，所述终止条件为在所述将大型分布式系统网络划分为若干个局部区域，初始化所述局部区域内的网络拓扑结构，并随机选择偶数个所述网络拓扑结构的个体作为初始的种群中设定的计算的循环次数，若是，则输出所述子代作为最优结果，若不是，则返回所述计算种群中个体的个体适应度，并选择适应度较高的个体作为父代的步骤；当判断结果为所述子代的后悔值不小于所述父代的后悔值，则舍弃所述子代，并判断是否满足终止条件，若是，则输出所述父代作为最优结果，若不是，则返回所述对所述父代执行遗传算子，形成子代的步骤；在所述局部区域内根据多个约束条件构建多目标函数过程如下：若令X＝(x₁,x₂,...x_m)表示G的任一生成树T的链接状态，则X的定义如下：若令S(T)表示图G中所有生成树的集合，那么对于n阶完全图，有|S(T)|＝n^n‑2；其中，G为一个二维平面内的完全图；再令f_i(X)(i＝1,2,...,q)表示目标函数，则多目标最小生成树问题如下：$\left\{\begin{array}{c}\min f_1\left(X\right)=\underset{i=1}{\overset{m}{\Sigma }}{\omega }_{i1}·x_i\\ \min f_2\left(X\right)=\underset{i=1}{\overset{m}{\Sigma }}{\omega }_{i2}·x_i\\ ......\\ \min f_q\left(X\right)=\underset{i=1}{\overset{m}{\Sigma }}{\omega }_{iq}·x_i\end{array}\right.$s.t.X∈S(T)对于任一局部区域G_i，若V_i＝{v_i1,v_i2,...,v_in}，Ei＝{e_i1,e_i2,...,e_im}，X_i＝(x_i1,x_i2,...,x_im)，其中，V＝{v₁,v₂,...,v_n}为G的顶点集合，表示系统中的网络节点，E＝{e₁,e₂,...,e_m}为G的边集合，表示网络节点之间的链路，每条边e_i与q个权重相关联，表示为Ωi＝{ω_i1,ω_i2,...,ω_iq}(i＝1,2,...,m)，X＝(x₁,x₂,...x_m)表示G的任一生成树T的链接状态，则按照目标函数f_i(X)的形式，将目标函数z₁(X_i)、z₂(X_i)、z₃(X_i)、z₄(X_i)定义如下：$\left\{\begin{array}{c}\min z_1\left(X_i\right)=\underset{j=i1}{\overset{im}{\Sigma }}{\omega }_{j1}·x_j\\ \min z_2\left(X_i\right)=\underset{j=i1}{\overset{im}{\Sigma }}{\omega }_{j2}·x_j\\ \min z_3\left(X_i\right)=\underset{j=i1}{\overset{im}{\Sigma }}{\omega }_{j3}·x_j\\ \min z_4\left(X_i\right)=\underset{j=i1}{\overset{im}{\Sigma }}{\omega }_{j4}·x_j\end{array}\right.$s.t.X_i∈S(T_i)其中，ω_j1＝deg(x_j)，表示链路e_j两端所连接节点的端系统资源耗费之和；ω_j2＝time(x_j)，表示链路e_j的通信延时；ω_j3＝jet(x_j)，表示链路e_j的网络抖动值；ω_j4＝loss(x_j)，表示数据传输的网络丢包率；在对多个目标函数进行优化时，进行多个目标之间的权衡与折中，采用后悔函数描述：$r(Z,p)=\left|\right|Z-Z^{*}|{|}_p={\left[\underset{j=1}{\overset{q}{\Sigma }}\right|z_j-z_j^{*}{|}^p]}^{1/p}$其中，q为目标个数，p为范数参数，z_j为第j个目标的取值，z_j*表示第j个目标的理想值，其表达式为z_j*＝z_j^min，参数p代表对较大后悔值的关心程度。