基于改进蚁群算法的负载均衡机制的研究*

于 爽刘从军，2

（1.江苏科技大学计算机学院 镇江 212003）（2.江苏科大汇峰科技有限公司 镇江 212003）

1 引言

网络负载均衡是保证网络系统正常运行的的重要技术手段，随着互联网和大数据的不断增长，用户对网络的访问量急剧上升［1］，面对大用户、高并发和海量数据请求，网络负载能力亟待提升，设计一个灵活的动态负载均衡机制去解决任务分配问题，可大大提高系统业务执行效率［2］，解决大量并发访问服务请求，为用户提供更好的访问质量。

负载均衡技术的核心是负载均衡算法，目前对负载均衡算法优化的研究是其主流方向，负载均衡算法可分为静态和动态两类［3］。其中前者包括优先权、轮询等，主要是基于服务器容量进行分配，该算法实现简单，复杂度低，不需考虑节点状态和网络状况，可靠性好，但缺点是不能很好的均衡不同节点的处理性能和适应网络的变化，易导致高性能设备空闲而底性能设备拥塞的情况，因此其灵活性较差。而动态负载均衡算法可通过定期收集系统参数实现对调度策略的动态调整［4］，从而实现较好的负载均衡质量。常见的有一致性哈希算法、预测法等。目前也有学者将生物优化算法如蚁群算法、遗传算法等加入到负载均衡计算中，并取得了不错的效果。本文通过对基本蚁群算法进行改进，克服其自身的不足实现负载均衡性能的提高。

2 传统蚁群算法

蚁群算法（AOC）是一种通过模仿蚂蚁觅食行为而提出的生物组合优化算法。在寻找食物的过程中蚂蚁之间会通过一种叫做信息素的化学物质传递食物信息，路径越短，释放的信息素浓度越高，该路径便会吸引更多的蚂蚁聚集，由此而找到觅食的最优路径［5］。ACO算法具并发性、正反馈性、可与其他算法结合等优点，因而常用来解决多种目标下的寻优问题［6］。

其基本求解过程如下：

1）算法初始化：对蚁群的启发信息、迭代次数、蚂蚁数、节点数和信息素、进行初始化设置。信息素浓度用τij(t)来表示，初始时为固定值，启发信息用ηij表示，他与dij的关系为：，其中dij表示节点i到j的路径长度。

2）转移概率的计算：蚂蚁在节点间移动时，会根据节点的转移概率来决定下一步的移动位置，转移概率公式为

式中，α代表信息素因子，β代表启发期望因子，allowedk表示允许访问的节点。

3）信息素更新：为了对路径信息进行不断的筛选，蚁群算法中引入了信息素挥发因子ρ（0＜ρ＜1），当蚂蚁完成一次循环后，需要对路径上的信息素按照如下公式进行更新［7］：

4）终止条件：循环次数达到预设值，则停止，输出最优解。

3 蚁群算法求解负载均衡问题

服务端的负载均衡实质是一个任务调度问题，指在用户QoS约束条件下，将请求任务合理地分配给服务器去执行，并达到最短化任务完成时间和最优化系统性能。可用如下调度模型表示。

图1 任务调度过程

将M个任务分配到N个服务器上去执行获得最佳分配方案。则基于蚁群算法的任务调度实质是找到M×N个节点的最短路径，这个最短路径基于任务完成时间和负载均衡度。

为衡量路径是否最短，需设定一个目标函数来计算路径目标值，为信息素更新做铺垫。将m个任务分配给n个服务器，因每个服务器资源参数不同，任务需求也不同，为形成目标函数，以Cij作为任务Ti在服务器Sj上的完成时间，可使用式（3）计算所有任务的完成时间：

其中，Eij为Mj上完成第i个人物的预期时间，Wj为服务器Sj的任务等待时间。

服务集群中所有任务的最大完工时间可表示为

其中，k为分配给服务器j的任务量。

负载的目标是在最小响应时间下实现最大资源利用率，基于此，将目标函数定义为［8～9］

4 改进蚁群算法

传统蚁群算法在求解过程中也具有一定的局限性，一是算法初期，由于信息素初始值相同，选择下一个节点时倾向于随机选择。虽然随机选择能探索更大的任务空间，有助于找到潜在的全局最优解，但是需要较长时间才能发挥正反馈的作用，因而开始时算法的进化能力较低。二是到了算法后期，由于ACO算法的正反馈作用的增强，蚂蚁选择方式的随机性减小，虽然加快了收敛进程，但容易使算法产生局部最优解。针对以上缺点，本文采用如下方法对算法进行改进。

4.1 信息素初始化方式的改进

传统蚁群算法中信息素采用均匀化方式初始，操作简单但易导致算法初期陷入盲目搜索，进化效率不高，为提高算法前期进化率，许多学者对信息素初始化方式进行了改进。研究发现遗传算法（GA）具有较强的搜索能力，算法初期将遗传算法加入到蚁群算法中，可有效的提高ACO算法的进化速率。图2为两种算法的进化率随时间的变化曲线。

图2 遗传算法与蚁群算法的进化率-时间曲线

从图中可以看出，蚁群算法初期进化率较低，但随着时间的推移，其正反馈作用发挥后，其进化率急剧上升，并且上升到一定水平后保持相对稳定。GA算法在前期搜索能力较高，其进化率也较高，但随着时间的推移，相较于蚁群算法，其没有一种有效的反馈机制，后期收敛速度变慢，进化率也随之降低，并降低到一定水平后趋于相对稳定。因而，本文将遗传算法引入到蚁群算法，将遗传算法进化得到的较优解作为蚁群算法的初始信息素以加快算法初期的进化速率［10］。

4.2 转移概率的确定

前面我们解决了传统蚁群算法初期收敛速度慢的问题，当算法进行到一定程度后随着正反馈机制发挥作用，或者当问题规模较大时，按照概率选择公式访问节点的方式，使得蚂蚁选择节点的随机性减小，算法易产生局部最优解。因此，要对概率选择公式进行优化，本文采取伪随机比例规则增加转移概率公式的随机性［11］。具体如下：

4.3 启发信息的改进

求解过程中为防止出现负载不均衡的现象，造成资源浪费，加入一个负载均衡因子去调节任务分配。其计算公式为

其中，Ej代表服务器Sj的总完工时间，Eavg代表n台服务器的平均完工时间。由公式可以看出，Loadj与Ej成反比，随着Ej的增加而减小。

由蚂蚁的概率转移公式可知，蚂蚁在选择下一个节点时受启发信息和信息素浓度的影响，传统ACO算法中，启发函数ηij与路径间距dij成反比，但在求解负载均衡问题时，启发信息通常与服务器预计执行时间Eij成反比［12］。将负载因子加入到启发信息中，实现对启发信息的进一步优化，平衡服务器负载，计算公式为

4.4 改进后的算法流程

遗传算法：

1）编码：实数编码，以提高GA算法的求解精度。

2）计算个体适应度函数：适应度函数的设计直接影响GA算法的求解质量，马克沃茨均值-方差组合模型是用于解决金融投资的合理配置，平衡收益和风险的一种预测模型［13］，其公式为

图3 改进遗传-蚁群算法的流程图

其中，负载均衡中对任务的调度分配与上述模型类似，即在均衡任务分配时达到服务器响应时间最小而资源利用率最大。因而利用此模型作为适应度函数，可在约束范围内进行计算，实现负载目标。

3）终止条件判断：终止条件判断有三个，满足其中任意一个即可停止进化，输出最优解。（1）达到最大进化次数；（2）个体或种群的适应度相对稳定；（3）个体适应度值达到设定阈值。

4）遗传操作：对未达到终止条件的种群，按照预设值执行选择、交叉、变异操作［14～15］。

蚁群算法：

1）初始化信息素：用遗传算法求得的解去初始蚁群算法的信息素。

2）计算转移概率：采用伪随机比例规则结合公式（1）选择下一节点。

3）计算每只蚂蚁完成一次搜索任务的路径长度。

4）更新信息素浓度：根据式（2）对信息素浓度进行更新。

5）完成迭代，输出最优解［16］。

5 实验及结果分析

为验证本文算法的优越性，选用OPNET仿真平台，分别对轮询法（RR）、传统蚁群算法（AOC）和本文算法三种算法的负载性能进行了实验对比，相应的算法参数设置如下表所示。

表1 遗传算法参数

表2 蚁群算法参数

本实验主要对集群平均响应时间和节点利用率进行了对比测试，实验结果如图所示。

图4显示了在任务数不同的情况下，三种算法对应的服务器平均响应时间，如图，当任务数增加时，平均响应时间也相应的增加，其中轮询算法的响应时间最长，改进的蚁群算法响应时间最短。因此，本文中改进的蚁群算法在负载均衡方面有效缩短了服务器处理请求的平均响应时间。

图4 平均响应时间对比

根据图5所示，随着任务数的增加，本文算法的节点利用率也随之上升，且总体节点利用率高于其它两种算法，说明本文设计的蚁群优化算法提高了并发任务的调度效率。

图5 平均节点利用率对比

6 结语

本文通过对传统蚁群算法进行改进，提出了一种改进的蚁群算法来实现网络负载均衡，首先采用遗传算法解决蚁群算法前期收敛慢的问题，然后在算法后期加入伪随机序列防止算法早熟，并对启发信息进行了优化。通过仿真软件，分别采用GA、ACO、本文算法进行实验仿真，结果表明本文算法有效的缩短了响应时间提高了节点利用率，使得整个集群负载更加平衡。