饶 磊，汤小春，侯增江

(西北工业大学计算机学院，陕西 西安 710129)

0 引言

集群[1](Cluster)是由一组服务器构成的一种松散耦合的计算节点集合，对客户来说就像是形成了一个单一系统对外提供服务。在服务器集群环境下，各个服务器处理能力、负载水平之间存在一定的差异。如果不能合理分配任务，会出现某个服务器负载过重导致无法完成任务或者负载过轻导致资源闲置的情况，使得系统资源利用率低下，从而限制了系统整体性能的提升。

负载均衡问题的关键在于任务调度，目前国内外已提出各种任务调度算法。常见的任务调度算法有轮循法(Round Robin，RR)[2]、Min-Min 算法[3]、Max-Min 算法[3]、遗传算法[4](Genetic Algorithm，GA)等。轮循法没有考虑服务器的实际负载和任务的大小，在实际应用中不能及时响应用户请求，且存在负载不均衡的问题。Min-Min算法优先选择完成时间最短的任务到对应的机器上执行，而Max-Min算法优先选择完成时间最长的任务到对应的机器上执行;Min-Min算法的任务调度跨度较小，但容易导致负载不均衡;Max-Min算法能在一定程度上缓解负载不均衡的问题，但是任务调度跨度相对于Min-Min算法较长。此外，文献[2]中还提及了基于负载参数的调度算法。

遗传算法[4]是模拟生物进化过程的一种启发性搜索算法。目前，遗传算法已经被广泛应用于负载均衡问题的研究中，但存在一些缺陷:遗传算法局部搜索能力较差，在优化后期会因为种群缺乏多样性而局部早熟收敛。模拟退火算法(Simulated Annealing，SA)的局部搜索能力较强，能跳出局部最优解[5]，达到全局收敛，但把握搜索过程主体的能力较差。本文结合两种算法的优点，建立遗传模拟退火算法(Genetic Simulated Annealing，GSA)，增强了遗传算法的爬山能力，有效地解决了遗传算法的早熟问题，同时提高了收敛的精度。

1 负载均衡问题建模

由于在实际的服务器集群环境下需要考虑的因素很多，为了方便问题的求解，本文假设集群系统采用集中式[6]任务调度模型;用户提交的任务可以唯一的划分为一组具有约束关系的不可再分的子任务，约束关系用来表示子任务调度的先后顺序;每个子任务在各个服务器节点上运行的时间可以预估，各个节点间的通信延迟不计。基于以上假设，任务调度问题可以描述为将具有约束关系的子任务分配到服务器节点上进行处理，以降低任务调度跨度，提高负载均衡度，使集群系统资源得到合理利用，优化系统的性能。

1.1 任务调度模型

本文将服务器集群环境描述为四元组Ω=(T，S，M，W)。其中任务集 T={t1，t2，…，tm}，服务器集S={s1，s2，…，sn}。M 是一个 m × n 阶矩阵，Mij表示子任务ti在服务器sj上的预计运行时间，若ti无法在服务器sj上执行，则Mij=-1。W是一个m×n阶稀疏矩阵，Wij=1表示子任务ti被分配到服务器sj上执行，否则 Wij=0，i∈{1，2，…，m}，j∈{1，2，…，n}。需要说明的是:在一种调度策略下，一个子任务只能在一台服务器上执行，即矩阵W的一行有且只能有一个非零值。子任务调度的先后顺序可以用DAG图表示，根据该图可以得到若干个有效的调度顺序。图中每个结点对应一个子任务，有向边(ti，tj)表示ti先于tj执行，先序关系具有传递性。对于任意一个有效的调度顺序，必须满足该先序关系。例如图1中t4和t5先于t7执行，而t4和t5没有固定的先后关系，二者的调度顺序可先可后。

图1 子任务调度的顺序图

1.2 负载均衡模型

设A为一个有效的任务调度策略，T(A)表示在调度策略A下的任务调度跨度，即任务集T在服务器集S上总的执行时间。本文的目的之一就是要降低T(A)，缩短用户的等待时间。

设 L={l1，l2，…，ln}表示在某种调度策略下，服务器的负载指标集合，lj(A)为在调度策略A下，服务器sj的负载指标。定义lj(A)如下:

式(1)中 j∈{1，2，…，n}，Mij≠ －1，由此可见，0＜lj(A)≤1。设σ(A)为负载指标的标准差，即:

由式(3)可得，0＜μ(A)≤1。负载均衡要解决的问题就是要构造一个合理的调度策略A，并根据该策略将任务调度到对应的服务器上执行，使得T(A)最小的同时μ(A)尽可能大。

2 算法原理分析

2.1 遗传算法

遗传算法[4]将问题域中的解编码为种群中的染色体或个体，传统遗传算法的早熟现象与选择操作有关。为了达到全局收敛的目的，理论上必须保持种群的多样性;而在实际应用中，为了加快算法的收敛速度，会倾向于选择适应度值较高的个体，而那些具有部分优良基因却适应度值低的个体很容易被舍弃，在迭代的过程中，种群的多样性会逐渐降低，导致早熟的概率变大。

2.2 模拟退火算法

模拟退火算法[5]来源于固体退火原理的启发式随机搜索算法。在进行选择操作时，按照Metropolis准则[7]以一定的概率选择较差的解，这样可以有效防止局部收敛现象的发生。

2.3 遗传模拟退火算法

遗传模拟退火算法一方面以遗传算法的基本操作主导寻优的方向;另一方面，在进化过程中，采用模拟退火算法选择个体。在进化初期温度较高，加大了适应度值较低的个体被选择的概率，保持了种群的多样性，增强了算法的全局收敛性。在迭代的过程中，温度逐渐降低，导致适应度值较低的个体被舍弃的概率变大，从而加快了算法的收敛速度。

3 算法设计

3.1 染色体编码

本文采用二维实数编码[4，8](矩阵编码)方式。设子任务数为n，则一种有效的任务调度方式可以用n×n阶稀疏矩阵R表示，矩阵的行依次对应任务编号，矩阵的列表示任务的调度顺序，比如任务ti的调度顺序为j，Rij的值为任务对应的服务器编号，在第i行除第j列外，其余项的值为零。例如下面的7×7阶矩阵:

由该矩阵可以得到满足图1的一种有效的任务调度顺序{t1，t3，t2，t5，t4，t7，t6}，在服务器 s1上执行的任务有{t1，t4，t7}，在服务器 s2上执行的任务有{t2，t3，t5，t6}。

3.2 初始化种群

初始参数设定:设定种群规模Z，当前种群代数K=1，终止进化代数D，交叉概率Pc，变异概率Pm;初始温度 T1，降温因子 λ=1－K/D，0＜λ＜1。

初始化种群个体:

(1)生成任务调度顺序，即子任务DAG图的拓扑排序，算法如下:

①判断DAG图中的结点集合是否为空，如果非空，则在DAG图中随机选一个没有前驱的任务结点并输出;否则算法结束。

②从图中删除该结点及由它发出的边，转①。

重复以上两步，直到输出所有结点，这样就生成了一个有效的任务排列。

(2)生成任务资源映射:采取有放回的抽取方式，从S中随机抽取一台服务器sj分配给某个任务ti，抽取时若检测到Mij=－1，则继续抽取，直到Mij≠－1，抽取完后将Eij的值置为1，当所有任务都分配完毕时才结束。

(3)将生成的任务调度顺序和任务资源映射组合拼接，得到任务调度矩阵R。

依次循环执行以上三步Z次，创建初始种群的Z个个体。至此，种群初始化结束。

3.3 适应度函数定义

定义系统在调度策略A下的适应度函数f(A)如下:

由式(4)可知T(A)越小，f(A)越大，反之亦然。

3.4 选择操作

为了防止当前种群的最优个体在下一代丢失，采用精英选择[4](Elitist Selection)策略:把当前种群中最优个体直接复制到下一代种群中，不进行交叉、变异操作。

在进行选择操作时，首先采用精英选择;然后采用轮盘赌[4](Roulette Wheel)算法和模拟退火算法结合的改良选择算法，该算法首先采用轮盘赌算法进行选择，若某个体未被选中，则继续采用模拟退火算法进行选择，算法如下:

设Xi为当前种群中的第i个个体，P[Xi]为采用轮盘赌算法时，Xi被选择的概率，根据轮盘赌算法原理有:

其中f(Xi)为Xi的适应度值。由式(5)可知Xi被选择的概率与f(Xi)的值成正比。

令△μ =max{μ(Xj)}－ μ(Xi)，j∈{1，2，…，Z]。PSA[Xi]表示模拟退火算法中的选择概率，根据Metropolis准则[7]，有:

当满足条件 PSA[Xi]＞ random[0，1]时选择 Xi。显然△μ≥0，由式(6)可知μ(Xi)越大时，Xi被选择的概率也越大。算法伪代码如下:

按照上述选择算法，每次选择两个个体X、Y，用于3.5节的交叉操作。

3.5 交叉操作

对于3.4节中选择的两个个体X、Y，以概率Pc进行交叉操作，交叉过程分为两步:

(1)任务调度顺序交叉:采用纵向交叉方法。随机选择X的任务调度矩阵中的一列作为交叉起始位置，其后的列按照Y的任务调度矩阵中的顺序进行移动;同理，Y也按照X的顺序进行移动。

(2)任务资源映射交叉:采用横向交叉方法。在上一步的基础上，随机选择X的任务调度矩阵中的一行作为交叉起始位置，其后的行中的非零值与Y互换。若互换时存在Mij=－1的情况，则该行不交换。至此，产生 X'、Y'。

3.6 变异操作

对3.5节交叉操作产生的两个个体X'、Y'，以概率Pm分别进行变异操作，变异过程分为两步:

(1)任务调度顺序变异:随机选择X'(或Y')的任务调度矩阵R中的一列作为变异列。在当前排列中找到离变异列最近的DAG图中的直接前驱任务所在的列，作为起始位置;在当前排列中找到离变异列最近的DAG图中的直接后继任务所在的列，作为结束位置;在起始位置和结束位置之间随机选择一列，将变异列移动至该列。

(2)任务资源映射变异:随机选择X'(或Y')的任务调度矩阵R中的一行作为变异行，随机抽取一台服务器分配给该任务，若Mij=－1，则继续抽取，直到Mij≠－1，并替换当前分配给该任务的服务器编号。至此，产生 X″、Y″。

循环进行选择、交叉、变异操作，并将新个体加入到下一代种群中，直到下一代种群中个体的数量达到Z为止。

3.7 算法终止条件

当种群进化代数达到D时，即K=D时输出最优解并进行解码，算法终止;否则继续迭代，在创建下一代种群的Z个个体后，按照TK+1=λ*TK进行降温，进化代数累加，K=K+1。

3.8 算法流程

综合以上各小节中的算法描述，本节采用如下伪代码描述GSA算法的总体流程:

4 实验结果与分析

本文以国外某集群作业管理系统[9]为实验平台，针对GSA算法、轮循法、Min-Min算法和Max-Min算法分别进行实验。本次实验中的参数设置如下:资源数n=10，任务数从50增加到500;种群规模Z=100，种群终止进化代数D=100，交叉概率Pc=0.95，变异概率Pm=0.05;初始温度T1=0.1。4种算法在不同任务数下的任务调度跨度如图2所示。

图2 任务调度跨度图

图2表明GSA算法的任务调度跨度总体低于另外3种算法。当任务数较少时，GSA算法的优势并不明显，这是因为GSA算法存在一定的开销，但随着任务数的增加，GSA算法在降低了任务调度跨度方面的优势逐渐得到体现。系统的负载均衡度如图3所示。

从图3可以看出GSA算法的负载均衡度大于另外3种算法，且随着任务数的增加，GSA的负载均衡度上升幅度较大，可见GSA算法合理分配了任务，有效地实现了集群系统的负载均衡。

图3 系统负载均衡度图

5 结束语

本文针对服务器集群环境下的负载均衡问题提出了一种遗传模拟退火算法，实验证明该算法有效地降低了任务调度跨度，减少了用户的等待时间，实现了集群系统的负载均衡。但是本文在建立任务调度模型时没有考虑节点之间的通信延时，此外文献[10]提出了自适应的交叉和变异概率以克服早熟缺陷，这些都是进一步需要研究的问题。

[1]Wikipedia.Computer Cluster[EB/OL].http://en.wikipedia.org/wiki/Computer_cluster，2012-06-18.

[2]李坤，王百杰.服务器集群负载均衡技术研究及算法比较[J].计算机与现代化，2009(8):7-10.

[3]王观玉.网格计算中任务调度算法的研究和改进[J].计算机工程与科学，2011，33(10):186-190.

[4]王小平，曹立明.遗传算法:理论、应用及软件实现[M].西安:西安交通大学出版社，2002.

[5]朱颢东，钟勇.一种改进的模拟退火算法[J].计算机技术与发展，2009，19(6):32-35.

[6]王文枫，帅建梅.一种云计算环境下任务调度策略[J].电子技术，2012，39(7):35-38.

[7]陈华根，吴健生，王家林，等.模拟退火算法机理研究[J].同济大学学报:自然科学版，2004，32(6):802-805.

[8]余有明，刘玉树，阎光伟.遗传算法的编码理论与应用[J].计算机工程与应用，2006，42(3):86-89.

[9]汤小春.基于集群技术的作业管理系统的研究与实现[D].西安:西北工业大学，2002.

[10]刘漳辉，王晓莉.云计算虚拟机群中带遗传算法的负载均衡算法[J].福州大学学报:自然科学版，2012，40(4):453-458.

[11]Mukul Pathak，Ajeet Kumar Bhartee，Vinay Tandon.An efficient scheduling policy for load balancing model for computational grid system[J].Computer Engineering and Intelligent Systems，2012，3(7):51-61.

[12]赵超，王晟.基于云模型的负载均衡问题研究[J].微电子学与计算机，2012，29(3):131-134.

[13]徐慧慧，石磊，陈信.网格资源调度算法研究[J].计算机技术与发展，2009，19(9):76-78.

[14]宋昕，宋欢欢.云计算环境下的流量控制和负载均衡策略[J].电子设计工程，2011，19(12):112-115.