基于关系矩阵编码的粒子群负载均衡算法研究

基于关系矩阵编码的粒子群负载均衡算法研究秦勇1宋继光1,2蔡昭权3卢庆武3罗伟3（1.茂名学院信息与网络中心，广东茂名525000；2.太原理工大学信息工程学院，山西太原030024；3.惠州学院教育技术中心，广东惠州，516007)摘要：针对网络流量负载均衡与优化问题,提出了一种基于关系矩阵编码的粒子群负载均衡算法。提出一种采用关系矩阵作为编码方法的粒子群算法来处理网络负载均衡问题，能够使网络流量能较好的分担到不同链路上。仿真结果表明了粒子算法在处理流量优化问题上的有效性和可靠性。关键词：粒子群算法；负载均衡；关系矩阵中图分类号：TP393文献标识码：AResearchonLoadBalancingAlgorithmBasedonPSOCodingRelationshipMatrixQinYong1SongJiguang1,2CaiZhaoquan3LuQingwu3LuoWei3(1.CenterofInformation&NetworksMaomingUniversity,Maoming,Guangdong525000,China；2.DepartmentofInformationEngineering,TaiYuanUniversityofTechnology,Taiyuan030024,China；3.CenterofEducationalTechnology,HuizhouUniversity,Huizhou,Guangdong516007,China)Abstract:Aimingatloadbalanceandoptimizationproblemsinnetwork,anetworkloadbalancealgorithmisproposedthatbasedonPSOwhichisencodedwithrelationalmatrix.RelationalmatrixwasfirstintroducedastheencodingofPSOalgorithmtohandlenetworkloadbalance,sothatnetworkflowcanbebettersharedtodifferentlinks.Simulationresultsshowtheperformanceofthevalidityandreliabilityofthealgorithmonflowoptimizationpossess.KeyWords:PSO;trafficoptimization;relationalmatrix0引言流量负载均衡研究的目标是网络可用路径能够合理的分担网络流量,避免网络拥塞,提高网络的资源利用率、网络的运行效率及网络的服务质量(QoS)，其一直是网络资源管理研究中的重要内容[1]。将生物启发机制应用于网络研究已成为当前研究的一个热点[2]，其中就包括粒子群算法。粒子群优化算法(ParticleSwarmOptimization,PSO)是由JamesKennedy和RussellEberhart博士于1995年提出的一种基于群智能的随机全局优化技术,其源于鸟群扑食行为的研究[3]。粒子群算法目前在诸多领域得到应用，具有需要设置的参数较少、编码简单、容易实现等特点和具有深刻智能背景的优势。粒子群算法采用“群体”和“进化”的概念，依据个体的适应度进行操作，通过个体间的协作搜寻最优解的一种群体智能算法。有些学者已经将粒子群算法[4]应用于路由选择与负载均衡等问题。LiTaoshen[5]在将粒子群算法应用到路由优化中时设计了特殊相加算子，但是这种方法存在一个缺点即当迭代时每一个个体在更新位置时都需要运用深度优先的方法寻找路径，这样就使算法的时间花费特别巨大。潘达儒[6]在算法中引入了交换、插入、删除、增量等操作算子和操作算子序列等概念，这一方法的缺点就是操作算子会产生容易搜索和增加算法实现复杂度。本文针对以上问题，提出了将关系矩阵作为粒子群算法的编码方式，本方法可以很好的克服以上算法的缺点，采用这种编码方式无需对粒子群算法的框架结构作任何改变，只要对搜索空间作一定的限制就可以避免冗余搜索。本文将采用了关系矩阵编码的粒子群算法应用到网络的流量优化和负载均衡问题，提出了基于粒子群算法的负责均衡算法，目标为使得整个网络中的流量均衡分布在各条链路上。每个个体在数据表示上就是一个矩阵变量，它代表着对应的网络状态信息，矩阵元素的大小表示对应链路上所分担的流量大小。在粒子群算法迭代过程中，个体始终追踪全体最优个体而搜索最优值，即一种最好的网络状态解。1粒子群算法在负载均衡中的应用1.1负载均衡模型一般情况下，令有向图(,)GVE表示计算机网络的拓扑结构，12{,,,}nVvvv是网络中节点集合，{|,[1,]}ijEeijn是网络的有向边集合，其中ije为节点i到节点j的有向边，n是网络的节点数，链路ije上所能承担的最大流量为ijL。假定流量自源节点0经过网络流向目的节点n。定义：ijl表示链路ije上所分担的网络流量，则整个网络的网络流量的平均值为：,1ijijijllm，其中，m为网络链路的条数，10ijijijee若存在若不存在，,0,,ijn。将负载均衡问题的均化问题转化为异化问题，所以本文以网络的流量平均值与各个链路的流量差值的绝对值之和的最小值为目标，即为下式：,min||ijijijll（1）假定链路ije不存在即0ij，其链路流量应满足：0ijl（2）对于每条链路ije上分担的流量应满足：0ijijlL（3）对于网络中的每一个节点（除源节点0和目的节点n外），当有流量流经时都应当满足flow-conversation。因此，对于网络中的第i节点（0andiin），当与此节点相关联的每条链路上的流量流经此节点时应当满足流量守恒：(0and)ijijjijijjlliin其中，（4）对于源节点0和目的节点n，流出节点i和流入节点n流量应该是守恒的，即他们应该满足下式：00(,0)jjininjillinj其中，（5）对于每一个节点，假定不存在从自己到自己的链路，因此，应该满足如下限制：0(0,,)iili=n（6）通过以上分析，优化目标函数为：,min||ijijijll(7)s.t.00(0and)(,0)0(0,,)0(0)0(and0)ijijjijijjjjininjiiiijinijijijlliinllinjli=nllLij其中，其中，（8）1.2粒子群优化Shi为了提高算法的收敛性在1998年提出了带有惯性权重的粒子群算法[7]。在每一次的迭代过程中，每个粒子基于个体认知和社会认知在N维空间中以一定的速度在群体最好粒子周围移动。其迭代公式为下式：1122(1)()(())(())ididididgdidvtwvtcrpxtcrpxt（9）(1)()(1)idididxtxtvt（10）其中，w表示惯性权重表明微粒原先的速度能在多大程度上得到保留。一般情况下，较大w会使粒子群具有较强的全局搜索能力，相反，较小w能够使粒子群具有较强的局部搜索能力。1c,2c为学习因子，代表粒子从个体极值和全局极值的信息继承度,反映了对继承信息的程度。1r，2r为区间(0,1)上的随机数。为了使算法获得较优的性能，每当全局最优适应值发生变化时，把当前的最优粒子位置随机赋值。一般在粒子群进化后期容易陷入局部最优解，本文采用在进化一定代数后将粒子群的全体粒子的位置随机赋值。1.3基于关系矩阵编码的粒子群算法1.3.1编码用网络的关系矩阵表示问题的解，粒子的位置可以表示成：000(1)(1)0(1)(1)nnnnxxxxx，相应地，粒子的速度定义为：010(1)(1)0(1)(1)nnnnvvvvv。其中，元素ijx的下标i表示链路的起点，下标j表示链路的终点，其大小表示从节点i到节点j的链路ije上分担的流量，即是满足如下映射关系式：ijijxl。因此，可以利用后面给出的适应度函数()fx对相应的粒子所寻找到的位置计算其适应值，并进行优劣评价。粒子群算法采用了关系矩阵作为编码方法，其迭代公式中所涉及的加减乘运算也应重新定义[8]，各个运算符所涉及到的是矩阵，因此将迭代公式中运算符定义为满足矩阵运算规则的运算。1.3.2适应度函数定义本文采用惩罚函数法处理约束问题，对于约束（3）可以将其作为粒子群算法的搜索边界来处理，即0ijijxL，其中，,0,1,,1ijn；对于约束（2）和（6）的性质和采用关系矩阵的原因，可以在关系矩阵中设置对应的元素值为零而实现约束，即通过设置0ijx实现0ijl的约束。因此惩罚函数只需考虑约束（4）和（5）。根据公式（8）所设计算法的适应度函数为：0,,1()||(||)(||)ijijijjijinijijjjjifxxxxxxxm（11）其中，，分别为两项约束在适应度函数中所占的权重。其中，()z是惩罚函数，其满足：0if(0)()if(0)zzrz，其中，r为一个不为零的正实数。当约束项不为零时由r决定对约束的惩罚程度，z越大惩罚程度就越大即r越大。1.3.3算法描述关系矩阵中的每个元素表示对应链路上所分担的流量大小，而链路ije承担的能力是有限的，因此，需要首先初始化网络链路能分担的最大流量ijL，其作为粒子群算法的搜索边界条件。当个体搜索区域超出了边界条件时即个体位置满足：ijijxL，将个体的位置在搜索区域内重新初始化，即使其满足：0ijijxL；另外，将不存在的链路对应于关系矩阵中的元素值设置为零，即：0ijx，本文这样处理是为了尽可能减少冗余空间的产生和冗余搜索。一般情况下，粒子群算法在迭代早期具有较强的搜索能力，就要具有较大的惯性权重w；而在搜索后期算法应当在较小的局部进行搜索，即具有较强的局部搜索能力，此时惯性权重w应是较小值。因此，把惯性权重w设计成一个随着迭代次数递减的线性函数[9,10]，即：maxmaxminmax()t，其中，maxt为设置的最大迭代次数，t为当前迭代次数，maxw为最大惯性权重，minw为最小惯性权重。对粒子群个体初始化以后，粒子群算法就依据已经设置的好的参数进行循环迭代，按照适应度函数()fx对个体进行优劣评价并更新个体极值和全体极值，在整个迭代搜索过程中，个体始终会追寻全体最优值和个体极值在搜索区域进行搜索。在迭代结束后，粒子群算法所搜寻到的最优解就是所求的最优解，解的各个元素值就代表着对应链路上应分担的流量大小。算法的实现步骤如下：1)设置参数：包括设置算法的惯性权重、学习因子和粒子群的规模，以及网络各条链路分担的流量的最大值；2)初始化：对每个个体的随机位置和速度进行初始化；3)计算粒子群的每个个体适应值；4)更新每个个体的最好位置ip：对于每个个体，将其适应值与其所经历过的最好位置的适应值进行比较，若较优，则更新最好位置；5)更新全局最优位置gp：对于每个个体，将其适应值与全局所经历的最好位置的适应值进行比较，若较好，则将其作为当前的全局最好位置。6)根据式（9）和(10)对个体的速度和位置进行更新；7)循环条件判断：若未达到足够好的适应值或达到预设最大迭代代数maxt，则返回3）并更新权重系数w；若算法找到较优的解或达到最大的迭代次数，则终止循环并输出最优解。2仿真试验试验环境采用PC机（PentiumIV2GHzCPU,1G内存），WindowsXP，VC++2008。在仿真实验中采用的网络拓扑结构如图1所示，共有9个节点构成，对节点从0依次编号，圆圈内数字为节点编号。设置粒子群