蚁群算法在服务器集群批量任务调度中的应用
小型微型计算机系统２０１０年４月第４期
ＪｏｕｒｎａｌｏｆＣｈｉｎｅｓｅＣｏｍｐｕｔｅｒＳｙｓｔｅｍｓＶｏＬ３１Ｎｏ．４２０１０
蚁群算法在服务器集群批量任务调度中的应用
王炳飞‘ｔ一，王劲林１．一，刘学２，刘磊２
１（中国科学技术大学自动化系，安徽合肥２１００００）
２（中国科学院声学研究所国家网络与新媒体技术工程研究中心，北京１００１９０）
Ｅ?ｍａｉｌ：ｗ卸ｇｂｆ＠０ｓｐ．ａｃ．ｃｎ
摘要：服务器集群中的负载均衡和作业调度是影响系统性能的重要因素．本文描述服务器集群批量任务的作业调度问题，对该问题建立了基于图的模型．由于使用一般的启发式算法或动态规划算法解决该问题具有局限性，本文引入蚁群算法进行求解，并针对该问题具体求解提出了启发式距离合适的计算方法．最后在仿真的基础上，讨论了算法的优化效果和收敛性，结果表明蚁群算法解决该问题具有优异的性能．
关键词：蚁群算法；服务器集群；批量任务；负载均衡；作业调度
中图分类号：ＴＰ３９３文献标识码：Ａ文章编号：１０００?１２２０（２０１０）０４－０６１１讲
ＡｐｐｌｉｃａｔｉｏｎｏｆＡｎｔＡｌｇｏｒｉｔｈｍｆｏｒＳｃｈｅｄｕｌｉｎｇ
Ｍｕｌｔｉ－ｔａｓｋｉｎＳｅｒｖｉｃｅＣｌｕｓｔｅｒ
ＷＡＮＧＢｉｎｇ．ｆｅｉｌＰ，ＷＡＮＧＪｉｎ．１ｉｎｌ”．ＬＩＵＸｕｅ２。ＬＩＵＬｅｉ２
１（Ａｕｔｏｍａｔｉｏｎ。ＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｌｌＴｅｃｈｎｏｌｏｇｙｏｆＣｈｉｎａ，Ｈｅｆｅｉ２１００００．Ｃｈｉｎａ）
２【ＮａｔｉｏｎａｌＮｅｔｗｏｒｋＮｅｗＭｅｄｉａＥｎｇｉｎｅｅｒｉｎｇＲｅｓｅａｒｃｈＣｅｎｔｅｒ．ＩｎｓｔｉｔｕｔｅｏｆＡｃｏｕｓｔｉｃｓ．ＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓ。Ｂｅｉｊｉｎｇ１０００８０Ｃ：ＩｌｆＪ能）
Ａｂｓｔｒａｃｔ：Ｗｈｅｎｃｏｎｓｔｒｕｃｔｓｅｒｖｉｃｅｃｌｕｓｔｅｒｓ，ｔｈｅｆａｃｔｏｆｌｏａｄｂａｌａｎｃｉｎｇａｎｄｔａｓｋｓｃｈｅｄｕｈＩｌｇｉｓｖｅｒｙｉｍｐｏｒｔａｎｔ，ｉｔｉｎｆｌｕｅｎｃｅｓｔｈｅｐｅｒｆｏｒｍ－ａ／ｉｃｅｏｆｔｈｅｗｈｏｌｅｎｅｔｗｏｒｋｓｙｓｔｅｍ．Ｓｏｍｅｔｉｍｅｓ，ｔｈｅｔａｓｋｓｃｈｅｄｕｌｉｎｇｉｎａｓｙｓｔｅｍｉｓｐｒｅｓｅｎｔｅｄｔｏｂｅＮＰｐｒｏｂｌｅｍ．Ｔｈｉｓｐａｐｅｒｒｅｐｒｅｓｅｎｔｓｔｈｅｐｒｏｂｌｅｍｏｆｓｃｈｅｄｕｌｉｎｇｍｕｌｔｉ－ｔａｓｋｓｉｎｓｅｒｖｉｃｅｃｌｕｓｔｅｒａｎｄｂｕｉｌｄｓａｇｒａｐｈｂａｓｅｄｍｏｄｅｌｔｏｄｅｓｃｒｉｂｅｉｔ．Ｄｕｅｔｏｔｈｅｄｉｆｆｉｃｕｌｔｉｅｓｏｆｒｅｓｏｌｖｉｎｇｔｈｉｓｐｒｏｂｌｅｍｕｓｉｎｇｈｅｕｒｉｓｔｉｃａｌｇｏｒｉｔｈｍａｎｄｄｙｎａｍｉｃｐｒｏｇｒａｍｍｉｎｇａｌｇｏｒｉｔｈｍ，ｔｈｅａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ，ａｌｌｅｖｏｌｕｔｉｏｎａｒｙａｌｇｏｒｉｔｈｍ，ｉｓ
ｐｒｏｐｏｓｅｄ．Ｔｈｅｎａｎｏｖｅｌａｐｐｒｏａｃｈｏｆｃａｌｃｕｌａｔｉｎｇｔｈｅｈｅｕｒｉｓｔｉｃｄｉｓｔａｎｃｅｉｓｐｒｏｐｏｓｅｄｗｈｅｎｕｓｉｎｇｔｈｅａｎｔ
ｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ．Ａｆｔｅｒａｌｌ，ｂａｓｅｄ
ｏｎｔｈｅｓｉｍｕｌａｔｉｏｎ，ｔｈｉｓｐａｐｅｒｃｏｍｐａｒｅｓｔｈｅｐｅｒｆｏｒｍａｎｃｅｂｅｔｗｅｅｎｔｈｅａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍａｎｄｔｈｅＩｘａｄｉｔｉｏｎａｌｒｏｕｎｄ?ｒｏｂｉｎａｌｇｏｒｉｔｈｍｉｎｒｅｓｏｌｖｉｎｇｔｈｉｓｐｒｏｂｌｅｍ，ｔｈｅｃｏｎｖｅｒｇｅｎｃｅｏｆｔｈｅａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍｉｓａｌｓｏ
ｄｉｓｃｕｓｓｅｄ．Ｔｈｅａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍｉｓｄｅｍｏｎｓｔｒａｔｅｄｔｏｂｅｈｉｇｈｐｅｒｆｏｒｍａｎｃｅｉｎｒｅｓｏｌｖｉｎｇｔｈｅｍｕｌｔｉ－ｔａｓｋｓｃｈｅｄｕＬｉｎｇｐｒｏｂｌｅｍｉｎｓｅｒｖｉｃｅｃｌｕｓｔｅｒ．
Ｋｅｙｗｏｒｄｓ：ａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ；ｓｅｒｖｉｃｅｃｌｕｓｔｅｒ；ｍｕｌｔｉ－ｔａｓｋ；ｔａｓｋｓｃｈｅｄｕＬｉｎｇ
ｌ引言
在使用服务器集群的大规模网络应用系统中，如何控制服务器负载状况，有效利用服务器资源，一直是系统设计和维护中需要解决的重要问题．实际工程中通常采用负载均衡技术，通过调度任务对服务器资源进行合理分配，从而提高系统整体性能．但考虑短时间处理大批量任务的情况，常用的负载均衡机制并不能使资源配置最优，特别是当网络环境，任务规模等方面存在差异时，不同任务在不同服务器上的处理，其资源利用率不尽相同，在这种情况下，如果对批量任务进行合理的作业调度，尽量缩短批量任务整体处理时间，可以达到更好的负载均衡效果，这对提高系统资源利用率和吞吐率有着重要的意义．
与ＴＳＰ等问题类似。批量任务在服务器集群中的调度，是要按照一定的算法给集群内所有服务节点安排合适的任务处理序列，这类问题属于ＮＰ问题，随着问题规模的扩大，动态规划等精确的算法无法得到实际应用，而贪心算法等启发式算法又无法得
到较好的调度效果．作为一种随机的启发式算法，蚁群算法在解决这类组合优化问题上往往能够取得很好的效果Ｈ．．ｊＪ．蚁群算法（ａｎｔｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎ，ＡＣＯ）是意大利学者Ｍｄｏｒｉｇｏ等人从生物进化和仿生学角度出发，研究蚂蚁寻找路径的自然行为，进而提出的一种路径搜索算法．使用蚁群算法在解决ＴＳＰ问题，二次分配问题和作业调度等问题上，都取得了较好的结果，并显示出它在求解这类复杂优化问题特别是离散优化问题方面的优势，是一种很有发展前景的计算智能方法ｕ鼬１．本文通过对服务器集群内批量任务调度问题进行建模，描述了蚁群算法解决该问题的步骤，并针对蚁群算法提出启发式信息的计算方法．最后通过仿真验证了算法的有效性．
２问题描述和模型建立
—般而言。—个服务器集群内服务节点的数量有限，并且每个服务节点能够并行处理的任务数量是有限的．不失一般性，本文做以下假定：每台服务器一定时问内能够用于处理任务的连接
收稿日期：２００９－０１讲收修改稿日期：２００９－０２．１７基金项目：国家“八六三”高技术研究发展计划重大项目（２００８ＡＡ０１Ａ３１７）资助；新一代业务运行管控协同支撑环境的开发项目资助．作者简介：王炳飞，男，１９８４年生，博士研究生，研究方向为网络传播与控制；王劲林。男，１９６４年生，主任研究员，博士生导师，研究方向为ＩＰ网络技术的研究和网络流媒体应用技术，宽带网络体系结构及新业务等；刘学，男，１９７９年生，助理研究员，研究方向为网络与新媒体技术；刘磊，男，１９８０年生，博士研究生，研究方向为网络与新媒体技术．
万方数据