第２８卷第３期 ２０１１年３月 计算机应用研究 Ａｐｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍｐｕｔｅｒｓ Ｖｏ１．２８ Ｎｏ．３ Ｍａｒ．２０ｌ１
基于目标约束的分层动态负载均衡算法木
胡志刚，张艳平
（中南大学信息科学与工程学院，长沙４１００８３）
摘要：针对网格环境下的负载不均问题，提出了一种分层动态负载均衡机制，该机制采用随机服务模型描述
网格任务流特性及其资源上的动态负载状态，将站点内负载平衡问题归结为目标约束规划问题。理论分析了分
层负载均衡机制的有效性，证明并设计了优化方案的求解算法。仿真实验结果显示，该分层负载均衡算法在平
均响应时间、系统吞吐量方面优于以往的ＲＢＡ和ＤＢＡ。
关键词：网格计算；负载均衡；响应时间；约束优化
中图分类号：ＴＰ３９３ 文献标志码：Ａ 文章编号：１００１—３６９５（２０１１）０３—１１０５—０３
ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１—３６９５．２０１ １．０３．０８８
Ｏｂｊｅｃｔｉｖｅ—ｃｏｎｓｔｒａｉｎｅｄ ｈｉｅｒａｒｃｈｉｃａｌ ｄｙｎａｍｉｃ ｌｏａｄ ｂａｌａｎｃｉｎｇ ａｌｇｏｒｉｔｈｍ
ＨＵ Ｚｈｉ—ｇａｎｇ，ＺＨＡＮＧ Ｙａｎ—ｐｉｎｇ
（Ｓｃｈｏｏｌ ｏｆｂ￣ｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ＆Ｅｎｇｉｎｅｅｒｉｎｇ，Ｃｅｎｔｒａｌ Ｓｏｕｔｈ Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｓｈａ ４１００８３．Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｔｏ ｄｅａｌ ｗｉｔｈ ｔｈｅ ｐｒｏｂｌｅｍ ｏｆ ｕｎｂａｌａｎｃｅｄ ｌｏａｄ ｉｎ ｇｒｉｄ ｅｎｖｉｒｏｎｍｅｎｔ．ｐｒｅｓｅｎｔｅｄ ａ ｌａｙｅｒｅｄ ｄｙｎａｍｉｃ ｌｏａｄ ｂａｌａｎｃｉｎｇ ｍｅｃｈａｎｉｓｍ．Ｉｔ ｉｎｔｒｏｄｕｃｅｄ ｒａｎｄｏｍ ｓｅｒｖｉｃｅ ｍｏｄｅｌ ｔｏ ｄｅｓｃｒｉｂｅ ｔｈｅ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｏｆ ｇｒｉｄ ｔａｓｋ ｆｌｏｗ ａｎｄ ｌｏａｄ ｓｔａｔｅ ｏｆ ｒｅｓｏｕｒｃｅｓ． Ｆｈｅｎ，ｔｈｅ ｐｒｏｂｌｅｍ ｏｆ ｌｏａｄ ｂａｌａｎｃｉｎｇ ｉｎ ｇｒｏｕｐ ｃｏｕｌｄ ｂｅ ｒｅｄｕｃｅｄ ｔｏ ｔｈｅ ｐｒｏｂｌｅｍ ｏｆ ｏｂｊｅｃｔｉｖｅ ｃｏｎｓｔｒａｉｎｔ ｐｒｏｇｒａｍｍｉｎｇ．Ｔｈｅｏｒｅｔｉｃａｌ ａｎａｌｙｓｉｓ ｓｈｏｗｓ ｔｈｅ ｅｆｆｅｃｔｉｖｅｎｅｓｓ ｏｆ ｈｉｅｒａｒｃｈｉｃａｌ ｌｏａｄ ｂａｌａｎｃｉｎｇ ｍｅｃｈａｎｉｓｍ ａｎｄ ｔｈｅ ｃｏｒｒｅｓｐｏｎｄｉｎｇ ｏｐｔｉｍａｌ ａｌｇｏｒｉｔｈｍｓ．Ｔｈｅ ｓｉｍｕ— ｌａｔｅｄ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍｓ ｏｕｔｐｅｒｆｏｒｍ ｔｈｅ ｅｘｉｓｔｉｎｇ ｏｎｅｓ ｓｕｃｈ ａｓ ＲＢＡ，ＤＢＡ ｏｎ ｔｈｅ ａｓｐｅｃｔｓ ｏｆ ｍｅａｎ ｒｅ— ｓｐｏｎｓｅ ｔｉｍｅ ａｎｄ ｓｙｓｔｅｍ ｔｈｒｏｕｇｈｏｕｔ． Ｋｅｙ ｗｏｒｄｓ：ｇｒｉｄ ｃｏｍｐｕｔｉｎｇ；ｌｏａｄ ｂａｌａｎｃｉｎｇ；ｒｅｓｐｏｎｓｅ ｔｉｍｅ；ｃｏｎｓｔｒａｉｎｅｄ ｏｐｔｉｍｉｚａｔｉｏｎ
１ 问题的提出
网格计算是在分布、异构、自治的网格环境下构建虚拟组
织，通过其内部跨自治域的资源共享和协作，达到复杂应用中
对大规模计算能力的需求。网格各站点的处理能力和容量不
均衡及网格环境具有资源可用性不确定、服务能力异构性、高
通信延迟等特点，这些容易导致自治节点的负载不均衡，大量
性能分析报告显示，负载不均是制约网格性能的关键瓶颈之
一 ，因此负载均衡一直是网格领域的一个研究热点。
负载均衡机制一般分为集中式和分布式两种。集中式机
制 的优点是管理和部署方便，可以有效地实现全局最优策
略。缺点是可靠性和可扩展性较差，且策略的算法复杂度往往
很高；分布式机制 则刚好能有效克服集中式机制的缺点，不
受单点失效的影响且具有较好的扩展性，其缺点是很难达到全
局最优。从负载均衡算法的实现而言，可以分为静态均衡算
法 和动态均衡算法 Ｊ。静态负载均衡算法不考虑当前系统
的实际运行状态，而动态负载均衡算法则会根据当前系统的状
态（如任务到达率、可用资源数目、网络负载情况等）来决定。
在已有研究中，Ｇｒｏｓｕ等人 提出的静态负载均衡算法一
般作为基准性能测试方法，该算法以轮转方式（ｒｏｕｎｄ—ｒｏｂｉｎ）将
负载平均分配到各个资源节点，其资源的已有负载信息由一个
全局状态服务器记录和更新。Ｐｅｎｍａｔｓａ等人 假设所有任务
具有相同的执行时问，然后采用随机过程模型来预测资源上动 态负载变化的情况，并依据其预测结果来规划负载分配方案。
虽然该负载均衡算法具有很好的理论分析模型，但其前提条件
（所有任务具有相同的执行时间）过于严苛，难以在实际系统
中得到应用。为此，Ｄｈａｋａｌ等人 提出了一个改进的随机过 程模型，取消了文献［７］的假设前提，并同时解决了随机延迟 问题。针对不同的任务负载特性，Ｓｈａｈ等人 提出了一种能
适应各种负载特性的动态自适应负载均衡算法，通过分析已有
任务到达时问间隔的分布特征来调整均衡算法的相关参数，从
而实现具有自适应能力的负载均衡机制。其不足之处是，在跨
虚拟组织域之间进行负载分配（包括重分配）时，由于考虑到
时问复杂度和效率问题，算法的最优化策略实际上被取消了。
本文提出的ＡＩｇＭｉｎＴ—Ｈ负载均衡算法采用两层集中式结
构。其中，第一层由多个自治站点构成，自治站点之问的负载
均衡算法由全局均衡器实现，而各个自治站点内部的负载均衡
由局部均衡器实现 依据当前负载的状态，不同的站点被赋予 不同的权值，用于计算最优均衡策略的负载分配方案。当任务
负载到达时，每个站点的本地调度器执行最优化负载均衡策
略，基于任务的最小响应时间或计算费用提出相应的负载均衡
算法，算法描述了均衡站点内计算节点的负载过程，站点问的
均衡策略则是当全局均衡器检测到组问发生不平衡时被触发。
２ 系统模型与分析
２．１ 系统模型
设网格系统是由多个计算机节点组成，这些计算节点可以
收稿日期：２０１０—０８—０３；修回日期：２０１０—０９—２３ 基金项目：国家自然科学基金资助项目（６０６７３１６５，６０９７００３８）
作者简介：胡志刚（１９６３一），男，教授，博导，主要研究方向为并行与分布式系统、网格计算、嵌入式系统；张艳平（１９８５．），女，硕士研究生，主要
研究方向为网格计算、分布式实时系统、可信计算（ｃｒｙｓｔａｌｐｉｎｇ＠１２６．ｔｏｎｉ）．
计算机应用研究 第２８卷
足个人主机、工作站、超级计算机等，它们的体系结构、操作系
统、处理能力可能各不相同。图１为网格系统结构。
图１网格系统结构
该结构分为两层，分别是ｇｌｏｂａｌ ｌｏａｄ ｂａｌａｎｃｅｒ（ＧＬＢ）控制
的站点层，以及ｄｅｓｉｇｎａｔｅｄ ｒｅｐｒｅｓｅｎｔａｔｉｖｅ（ＤＲ）控制的节点层。
每个站点有ｎ，个计算节点，且每个站点中有一个ｄｅｓｉｇｎａｔｅｄ
ｒｅｐｒｅｓｅｎｔａｔｉｖｅ（ＤＲ）计算机，用于负责站点内负载均衡且与
ＧＬＢ通信。每个站点的其他节点只与ＤＲ节点相连。在本文
中，假设被分配到站点Ｇ 的任务只能在站点Ｇ 里执行，不能迁
移到其他的站点，且假设任务可以拆分，负载均衡机制在此两
层都属于集中式。
２．２ 问题定义
为便于分析和描述，表１给出了相关符号及其含义说明。
表１符号及其说明
符号 说明 “Ｅ
ｉ
Ｐｉ 节点ｉ的平均服务率 当前的工作负载量 分配给节点ｉ的负载量 分配给站点Ｇ 的总负载 节点ｉ的处理费用
ＧＬＢ决定各个站点的权值，每个权值记做 ， 是根据
各个站点的当前负载状态确定的。ＤＲ则根据其所在站点的
节点当前负载来均衡负载。每个节点在状态检测时间时刻发
送其当前的负载状态给其站点的ＤＲ节点，每个组的ＤＲ节点
计算其所在组的全局状态，发送给ＧＬＢ。
设网格系统由Ｇ 个站点组成，每个站点有ｎ，个节点，每个
节点是一个Ｍ／Ｍ／１排队系统（泊松分布输入和指数分布处理
时间）。因为每个节点是一个Ｍ／Ｍ／Ｉ排队系统，则节点ｉ的平
均响应时间为
（ ） ‘ ）
设任务分配给站点Ｇ』的平均响应时问为 （ ），
（ ） 古 Ｆ （ ） （２）
因此，从站点 的本地调度器出发，只需找到一个负载分
布 满足（Ｔｊ（ ））最小，即
ｒａｉｎ （ ）
Ｓ．ｔ． ≥０，ｉ＝ｌ，…，一
＝
＜“ ，ｉ＝１，‘一，
２．３ ｍｉｎ Ｔ （ Ｊ的求解
定理１若目标函数 （ ）最小时当且仅当下面的等式
成立：
㈩
证明 将式（２）中的 （ ）（ｉ＝１，…，ｒｔｊ）分别求一阶偏导
和二阶偏导，即 ＝ ＩＩｉ ㈩ 嚷 —Ｘ ）
Ｏ（ｘ ＝芒 ㈩ ） （１ 一 ）
故 ＞０Ｉ 学 Ｎ￣ｃ Ｐ（ｘ）函数是关 的
一个凸函数。同时 （ ）在其定义域上连续，故 （ ）存在最
小值。
在一定的限制条件下，求取任务分配给站点Ｇ 的最小响
应时问 （ ）达到最小时的分配策略（ ，…， ），设 ＞１０，
叼 ≥０（ｉ＝１，…，ｎ，）， ≥０（ｉ＝１，…，ｎ，），可以用一阶Ｋｕｈｎ—
Ｔｕｃｋｅｒ条件 求之。
令拉格朗日函数
Ｌ（ＸＩ，… ， ，＂ｑｌ，…，叩 ． ｌ，…， ，）＝
（ ）一 （ 一 ）一 ？７ Ｕｉ（ 一Ｕｉ） （ ）
根据一阶Ｋｕｈｎ—Ｔｕｃｋｅｒ 条件可知 （ｉ＝１，…，ｎ，）是最优
解当且仅当存在 ≥０，叩 ＞１０（ｉ＝１，…，ｎ，）， ≥０（ｉ＝１，…，
ｎｊ），使得Ｆ面的等式成立：
ｏＬ：０ （７） （ ０ Ｌ：０ （８）
叩 ＝ｏ， （ 一ｎ ）＝ｏ ≥０ ＜“ （ｉ＝ｌ，…，ｎ ） （９）
因此可以得到：
‘ ）
∑ ： （１１）
叩 ＝０， ＝０ ｔ＞０ ＜ （ｉ＝１，…，ｎ，） （１２）
简化得到：
“ 。， ≤ ≤
“ ’ （１３）
（１４）
． ：西 ≥ｏ（ｉ：１，…， ） （１５）
＜“ （ｉ＝１，…，， ，） （１６）
因为 ＞０，将式（１５）代人式（１３）得到式（３），即
ｒ∑ １“ 一 ￡一ｖ，
式（３）满足式（１６）。证毕。
根据定理１可知 不能保证为非负，当下面的不等式成立
时 ＜０。
｜ 娶 （１Ｉ７￣／ｕ ＜— 一 （，）
当 为负时，直观可行的方法是重设 为０，然后根据定理
１重新分配负载给其他的节点。为了确定不能被分配负载的
节点集合，本文提出了基于定理２的分配算法。
定理２设节点根据Ｕｉ值非递减排序（“ ≤ ：≤…≤‰），
∑“，一 存在整数ｍ（１≤ｍ＜ｎ，）使得公式 ＜ ｝成立，则当
至