第 3 1卷 第 5期 2 0 1 0 年 5 月 东 北 大 学 学 报 ( 自 然 科 学 版 ) Journal of Northeastern University(Natural Science) Vol.31,No .5 2 0 1 0 May 一 种 基 于 蚁 群 算 法 动 态 均 衡 的 网 格 任 务 调 度 孙大为, 常桂然, 陈 东, 王兴伟 ( 东北大 学 信息 科学与 工程 学院, 辽宁 沈 阳 110004) 摘 要: 网格资源分配属于 NP - 难问题,为 了更好 地解决 该问题,首 先建立 一种性 能 QoS 优 化的作 业 级网格任务调度模 型和目 标函数,并 对资源 和任务 数进行 了分析·提出 了基 于动 态信誉 度的 改进 蚁 群算 法 RACO(reputation-based ACO)进行网格任务调度,RACO 引入空间效率和时间效率的动态调节因 子,同时 采用 局部和全局信息素更新策略·仿真实验表明,RACO 在资源 利用率、动态 均衡方 面优于 Min-min, Max-min 和 ACO 算法· 关 键 词: 网格计算;任务调度;动态均衡;蚁群算法;信誉 中图分类号: T P 393 .01 文献标志码: A 文章编号: 1005-3026(2010)05-0630-04 A Grid Task Scheduling with Dynamic Equilibrium Based on Ant Colony Algorithm SUN Da-wei, CH ANG Gu i-ran, CH EN Dong, W A NG X ing-wei (School of Correspondent: SUN Da-wei, E-mail: sundaweicn @ 163 .com) Information Science & Engineering, Northeastern University, Shenyang 110004, China . Abstract: Resource allocation in grid is an NP-hard problem . To optimize the grid system, a performance QoS optimization model is developed for grid task scheduling and objective function, resources and tasks analyzed in detail . Then, an improved ant colony with the number of algorithm named RACO(reputation-based ant colony algorithm) is presented to schedule tasks in grid, based on the dynamic reputation . Int roducing a dynamic scheduling factor involving both space and time efficiencies, a local and global pheromone updating st rategy is applied to RACO . Simulation results showed that RACO algorithm outperforms the conventional Min-min, Max- min and ACO in resource utilization rate and dynamic equilibrium . Key words: grid compution; task scheduling; dynamic equilibrium; ant colony algorithm; reputation 网格计 算 技 术 强 调 在 动 态 变 化 的 异 构 环 境 中,共享资源和协作解决问题,因此网格环境中的 任务调度问题 是网 格 计算 的一 个关 键问 题,是 一 个 NP - 难问 题 [ 1 ] ·良 好 的 任务 调 度 策 略 能 高 效 地分 配网格 资源,实 现最优 跨度、服 务质量、负 载 均衡和经济原 则 等,网格 环境 下的 任 务调 度问 题 目前是网格计算的研究热点之一[ 2 ] · 针对任务调度算法在网格环境中存在的一些 缺陷 [ 3 ]:①经典算法 不能 有效 地实 现 资源 的动 态 负载均衡;②蚁 群算 法不 能有 效满 足 用户 的性 能 QoS 和经济原则等问题·本 文 提 出了 基 于动 态 信 誉度的改 进蚁 群算 法 RACO(reputation-based ant colony algorithm)进行网格任 务调度,引入 空间 效 率和时间效率 的 动态 调节 因子,结 合 蚁群 算法 的 正反馈优点,采用局部和全局信息素更新策略,有 效地实现网格任务调度系统的动态负载均衡和用 户的性能 QoS· 1 问题建模 作业级 网 格 任 务 调 度 问 题 的 实 质[ 4 - 5 ] 就 是 收 稿日 期: 2009-10-21 基 金项 目: 国家自 然科 学基金 资助 项目 (60673159, 70671020); 国 家高技 术研 究发展 计划 项目 (2007AA041201); 教育 部科学 技术 研究发 展计 划项目 (108040); 高等学 校博 士学科 点专 项科研 基金 资助项 目(20060145012, 20070145017)· 作 者简 介: 孙大 为(1985 - ),男 , 安徽六 安人, 东 北大学 博士 研究生 ; 常桂 然(1946 - ),男 ,河 北曲周 人, 东北 大学教 授, 博士 生导 师; 王兴 伟(1968 - ),男 , 辽宁盖 州人, 东 北大学 教授 ,博 士生导 师· 

第 5 期 孙大为等: 一种基于蚁群算法动态均衡的网格任务调度 136 将这 n 个相互独立的任务 J = { J1, J2, …, Jn}分 配 到 m 个 异 构 可 用 资 源 ( 处 理 单 元, PE (processing elements)) P = { P1, P2,…, Pm },使 得 任务 总 完成 代价 最小 且资 源 得到 均衡 利用·即 s 表示问题的一个解, F 2 m 是可行解,当且仅当 s ∈ F 时, s 是可行解·解空间中的 一个适应 度函 数 f, f:2 m → R,目的为找到一 个最小 任务完 成代 价 的可行解 s * , s * ∈ F 且 f( s * )≤ f( s)·为了便 于 问题的深入分析,引入如下定义· 定义 1 原 子 任 务,即 一 次 独 立调 度 的 不 相 互关联的任务,其中不排除任务内部的依赖关系, 即子任务(subtask)的依赖性· 其中, J 是 n 个需要调 度的原子 任务集 合, Ji 表示第 i 个原 子 任务, 每个 任 务 的任 务 量大 小 用 百万指令(MI)表示,每个原子任 务只能在 一个 资 源上被执行完成· 定义 2 可 用 资 源,即 可 用 于 完成 网 格 任 务 的各种 PC、同 构 异构 机 群等, 处 理单 元 PE 是 它 们的基本单元· 其中, P 是 m 个 可用 资 源 集 合, Pj 表 示 第 j 个可用资源·每个可用资源的计算能力用 p(百 万 指令每秒(MI/ s))表示· 定义 3 ET C 矩 阵(expected time to compute mat rix),任 务 Ji 在 可用 资源 Pj 上 的期 望执 行 时 间为 ET C, ij,其中 i∈{1,…, n}, j∈{1,…, m},由 ETC , ij 构成矩阵 ( ⁝ ET C, 1 1 … ET C, 1 m ET C, n 1 … ETC , n m ), ⁝ ET C, n× m = 其中, Eij = { P + ∪ + ∞},当 资源 Pj 不 能满 足 任 务 Ji 的需求时,则 E( Ji, Pj)→ + ∞· 定 义 4 EC T 矩 阵 (earliest completion time mat rix),任 务 Ji 在 可用 资源 Pj 上 的最 早完 成 时 间为 ECT , ij, 其中, i∈{1,…, n}, j∈{1,…, m}, 由 EC T, ij 构成矩阵 ( ⁝ ECT , 1 1 … ECT , 1 m EC T, n 1 … ECT , n m ), ⁝ ECT , n× m = 其中, ECT , ij 表示任 务 Ji 在 可用 资 源 Pj 上 的期 望 执行时间为 ETC , i j加上可用资源 Pj 中队列中已 存 在的任务的总执行时间·假设任务 Ji 开始执行 时 刻为 S i,那么 EC T , ij = Si + ETC , ij· 网格任 务调 度问题 是一 个求极 小值 问题·为 了便于问题的描述,引入变量 0, 否则·{ xij = 1, 任务 Ji 分配到资源 Pj 上执行; 则网格任务调度的目标函数可以描述为 满足如下约束条件: n m )·(1) makespan( J) = min ∑ 1) 当 n≤ m 时,即任务个数和可用资源个数 ECT , i j· xij ∑ ( j = 1 i = 1 xij = 1, j ∈ {1,2,…, m}, xij ∈ {0,1}·} xij = 1, i ∈ {1,2,…, n}, xij ∈ {0,1}; n m ∑ i = 1 ∑ j = 1 (2) 第一个约 束条 件 表示 第 j 个 资源 Pj 只 能 处 理一项任务,第 二个 约束 条 件表 示 第 i 个 任 务 Ji 只能由一个资源 处 理·此 时网 格任 务 调度 问题 简 化为多约束条件下的极小值求解问题· 2) 当 n > m 时,即任务个数多于可用资源个 数,会出现几个 任务 提交 到某 一个 资 源进 行处 理 的情况,那么可以通过任 务聚 类(job cluster)以 队 列方式转化为第一种情况处理· 2 算法描述 蚁 群 算 法[ 6 - 7 ] ( ant colony optimization, ACO)是通过蚂蚁群体之间的信息素(pheromone) 的传递及更新 来实 现 收敛 于最 佳路 径,是 一种 正 反馈机制· 2 .1 动态均衡机制 在蚁群算法中引入信誉度因子来实现网格任 务的动态负载均衡,通过动态的信誉激励机制,促 进资源的合理利用,实现资源的动态均衡· 节点信誉度是对可用资源节点的历史信誉的 一种测评,信誉度越高,表明此节点在过去的服务 中越可靠、安全·采用可用资源节点实际完成网格 任务的成功率 进行 量 化,同时 根据 当 前可 用资 源 节点完成网格任务的时间效率进行动态调整,即 { Trc( t + 1) = T rc(0) = 1, t = 0; (1 + λ)· Trc ( t), t > 0 且 0 ≤ λ≤ 1· (3) 其中: Trc ( t + 1)为 可用资 源节 点 Pav ailable 在 t + 1 时刻的信誉度;λ如式(4)所示, 为信 誉 度调 节 系 数,根据可用资 源节 点对 网格 任务 的 空间 效率 和 时间效率进行动态调整,1 + λ是保证 信誉度随 着 提供的服务的增加而动态增加· JM I, j k( t)( )+ β ECT , jh( t)( )· ETC , h( t) JM I, k ( t) λ = α ∑ ∑ ∑ ∑ k = 1 size s uccess h = 1 size siz e size all m m - - ∑ j = 1 ∑ k = 1 j = 1 h = 1 (4) 

236 东北大学学报(自然科学版) 第 31 卷 其中:α+ β= 1,α和 β分 别表 示空 间 效率 和时 间 效率对信誉 度调节 系数 λ的权重; 1≤ j≤ m, 0≤ h≤ size ≤ n, 0≤ k ≤ size - success ≤ size - all ≤ + m size all - ∑ JM I, j k ( t) 为 系 统 可 用 资 源 节 点 ∞; ∑ Pav ail able 在 t 时 刻 之 前已 接 受 的 所 有任 务 工 作 总 k = 1 j = 1 siz e succe ss - JM I , k ( t) 为 可用 资 源节 点 Pava il able 在 t 量; ∑ 时 刻 之 前 所 成 功 完 成 的 任 务 工 作 总 量; k = 1 m size ∑ EC T , j h( t) 为系统 可用资 源 Pa vaila bl e在 t 时 ∑ j = 1 刻 之 前 已 接 受 的 全 部 任 务 最 早 完 成 时 间 总 量; h = 1 size ET C, h( t) 为系统可用资源 Pa vaila bl e在 t 时刻之 h = 1 ∑ 前已接受的全部任务期望执行时间· 2 .2 信息素初始化 在分配任务 到 各个 资源 之前, 需从 网格 信 息 服务(G IS,grid information service)中获取 可用 资 源的 PE 个数及 其 处理 能 力 p(MI/ s)、网络 带 宽 br(Mb/ s)、信誉 度 rc 以及 资 源价 格 cs 作为 资 源 的初始信息素,即 Tk (0) = a· T p(0) + b· T b r (0) + s c c· T r (0) + d· Tc (0)· (5) 其中: a + b + c + d = 1, a, b, c, d 分 别代 表可 用 资源处理能力信息素、网络带宽信息素、信誉度信 息素和资源价格信息素在该资源信息素中所占的 权重· 2 .3 路径选择机制 在 t 时刻,第 i 个蚂蚁选择可 用资源 Pj 的概 率 pij( t)由式(6)确 定 且随 信 息 素的 更 新而 动 态 调整· pij( t) = [τj( t)]η·[ωj( t)]ε {[τu( t)]η·[ωu( t)]ε} , j ∈ allowed; { ∑ u allow ed 0, j | allowed· (6) 其中:τj ( t)表示 可用 资 源节 点 Pj 在 t 时刻 的 信 息素浓度;ωj ( t) = τj (0 )是 启 发 因 子, 表 示 节 点 Pj 的 固 有 属 性; 参 数 η 和 ε 用 于 调 节 τj ( t) 和 ωj( t)之间的 权 重, 当 η 变 小 时,收 敛 速 度 变 快, 当 ε变 小时, 收敛 速度 变 慢;allowed 为第 i 个 蚂 蚁尚未访问的节点集合· 2 .4 局部更新机制 当任务 Ji 被分 配到 某可 用资 源 节点 Pav ailable 后,资源的信息素需要进行必要更新,减少该资源 节点的信息素,促进蚁群搜索不同的路径,增加解 的多样性和求 解最 优 解的 概率,实 现 动态 负载 均 衡,信息素浓度调整如式(7)所示: Tk ( t + 1) = ρ· T k( t) + Δ T k( t),0 < ρ≤ 1· (7) 其中:ρ为信息素的持久性(一般取 0.6);1 - ρ为 信息素的挥发性;ΔT k ( t)如式(8)所示,为信息 素 改变量· Δ T k( t) = - (μ1·JM I, i + μ2·ET C, i + μ3·Ki), 0≤μ1 ,μ2,μ3 ≤1· (8) 其中:ΔT k ( t)是任务 Ji 的任务量 JM I , i,期望执 行 时间 ETC , i 和通信量 Ki 的函数;μ1,μ2,μ3 为调节 系数且 μ1 + μ2 + μ3 = 1· 2 .5 全局更新机制 当可用资源节点 Pa vaila bl e完 成任 务并返 回时, 需进行信息素的全局更新,如式(9)所示: T k ( t + 1) = ρ· T k( t) + ∑ΔT k ( t), 0 < ρ≤ 1· (9) c ( t),当 任 务 从 资 源 节 点 其中:ΔT k ( t) = Ce· Tr Pav ail able成 功 返 回时, Ce 作为 奖 励 参 数 取 0.6; 当 任务从资 源 节 点 Pav ailable 失 败 返 回 时, Ce 作 为 惩 罚因子取 - 1.2· 2 .6 网格资源调度流程 改进后 蚁 群 算 法 网 格 任 务 调 度 包 括 8 个 步 骤: 1) 用户提交任 务,并插 入到任务队列中 等待 调度,同时为每一个任务设置优先级,按照优先级 高低进行任务分 配·优先 级与 任务 量 和期 望执 行 时间成正比,即 f: k·( JM I, i, ETC , i)→P rior i· 2) 根 据 式 (5) 初 始 化 网 格 各 可 用 资 源 节 点 Pav ail able的初始信息素 T k(0)· 3) 从 GIS 中查询可用资源当前状态、返回 价 格、机器数、PE 数及处理能力等信息,对可用资 源 进行排序· 4) 调度 器 从任 务列 表中 取优 先 级高 的任 务 p rior,根据式( 6)计 算 概 率, 将 任 务 分 配 到 概 - Jhigh 率较大且 价 格在 预 算范 围 内 的 可 用资 源 Pav ailable 上· 5) 当任务 正 常分 配 后,利 用式( 7)进行 局 部 信息素的更新· 6) 当资 源 节点 将任 务执 行完 毕 且任 务成 功 返回,利用式(3)对该 资源 节点 进行 信 誉度 更新, 并采用式(9)进行节点全局信息素更新· 7) 若任务执行 失败,则 将其重新插入任 务队 

第 5 期 孙大为等: 一种基于蚁群算法动态均衡的网格任务调度 336 列中,等待调度器重 新调 度,利 用式(3)对 该资 源 节点进行信誉度更新,并采用式(9)进行节点全局 信息素更新· 运行速度、增强收敛能力、改善网格系统性能· 参考文献: 8) 循环步骤 3)～8),直到所有任务均成功执 [ 1 ] 行· 3 仿真结果与性能分析 本文利用 GridSim 模拟器 [ 8 ] 构建网格任务 调 度模拟平台·所 选择 的 系 统结 构 为 Sun Ultra, 操 作系统为 Solaris,模拟 3 个 GIS, 200 个 网格 资 源 节点、1 000 个 任 务, 任 务 计 算 量 为 5 000 MI 到 20 000 MI,数据通信量在 10～100 Mb/ s· 如图 1 所示,在不断增加资源数量的情况下, ACO 算法 [ 9 ] 的 资 源动 态 负 载 均 衡 优 于 Max-min 算法[ 1 0 ] 和 Min-min 算 法[ 1 0 ] ;而 RACO 的 资 源 负 载均衡较 ACO 有较大 改进·其 中,平 均 资源 负 载 度提高 16.87 % ;资源负载度方差 n 1 n∑ i = 1 (εi - 珋ε)2 减少 28.68 % , 取 得了 较 好 的 资 源利 用 率 和 动 态 均衡· Fig .1 图 1 网格资源负载均衡度对比 Comparison of grid resource load balancing between different algorithms 4 结 语 本文针对网 络 资源 频繁 变化 的网 格 环境, 基 于信誉度,引入 空间 效率 和时 间效 率 动态 因子 到 网格任务调度 策略 中,综 合考 虑资 源 的各 方面 参 数来确定信息 素浓 度,改 进了 蚁群 算 法在 资源 动 态均衡方面的 性能, 最后 的实 验证 实 了该 方法 的 有 效性·下一 步的研 究重点集 中于 提高蚁 群算 法 Mcmullan P, M ccollum B . Dyn amic job sch eduling on the grid environment using the great deluge algorith m [ C ] ∥ Parallel Computing Tec hnologies: P roceedings th e 9th Intern ation al Conference . Pereslavl-Zalessky: Springer- V erlag, 2007:288 - 308 . [ 2 ] At ta nasio A, Ghia ni G, Grandin et ti L, et a l . Op era tions research me thods for resource management and sch eduling in a computa tion al grid: a survey [ J ] . A d v an ces in Paral lel Com put i ng, 2005,14:53 - 81 . [ 3 ] Li K . Job sch eduling and processor allocat ion for grid comput ing on met a-computers[J ] . Jour na l o f Pa ral lel and [ 4 ] Distribu ted Compu t i ng, 2005,65(11):1406 - 1418 . 王 兴伟 ,蔡 颖, 佟呈 呈, 等· 基于 拍 卖和 免 疫优 化 的 网格 作 业 分配 机 制 [ J ]· 东 北 大 学 学 报 : 自 然 科 学 版, 2009, 30 (3):354 - 356· (Wang Xing-w ei, Cai Ying, Tong C heng-cheng, et al . Grid job assignment scheme based on auc tion and im mune optimiza tion [ J ] . Jou rnal o f N ortheastern U ni versi ty: N a t ura l S cien ce, 2009,30(3):354 - 356 .) Leal K, Huedo E, Llorente L M . A decentralized model for [ 5 ] sche duling independent tasks in fe derated grids [ J] . F u t ure Genera tion Compu ter Syste ms, 2009,25(8):840 - 852 . [ 6 ] Dorigo M, Blum C . Ant colony optimiza tion th eory: a survey [J] . Theoret ical Com pu ter S cience, 2005, 344 (3): 243 - 278 . [ 7 ] Stutzle T, Dorigo M . A short convergen ce proof for a class of ant colony optimization algorithm s [ J ] . I EEE T ransactions on Evo lu t ionary Compu t at ion, 2002,6(4):358 - 365 . B uyya R , Murshe d M . GridSim: a toolkit for the modeling [ 8 ] a nd simulat ion of distributed resource management and sc heduling for grid comput ing [ J ] . Concu rrency and Com pu ta t ion: Pract ice and Ex perie nce, 2002, 14 (3): 1175 - 1220 . [ 9 ] M arilen a1 B, Antonella D S, Giovanni M . An ACO inspired strategy to improve jobs sc heduling in a grid environment[ C] ∥ Th e 8th International Conference on Algorithms and Processing, Archit ectures Cyprus: Springer-V erlag, 2008:30 - 41 . Parallel for ICA3 PP 2008 . [10] Etmin ani K, N aghibzad eh M . A min-min max-min selec tive algorithm for grid task sch eduling [ C ] ∥ 2007 the T hird I EE E/ I FI P Intern ational C onference in Central Asia on Internet . Tashkent: IE EE, 2007:134 - 144 .