多Agent系统中考虑任务局部性的动态负载均衡机制.doc

多Agent系统中考虑任务局部性的动态负载均衡机制 //.paper.edu - 1 - 多Agent系统中考虑任务局部性的动态负载 均衡机制 费超* 作者简介：费超（1991-08-16），男，硕士，多 Agent 系统中的任务分配与负载均衡 （东南大学计算机科学与工程学院，南京 211189） 5 摘要：多 Agent 系统中的负载均衡机制主要通过调节系统内各节点的负载以最小化任务完成 时间。传统的静态以及动态负载均衡策略均未考虑任务局部特性这一实际存在的任务特性。 任务局部性是指一段时间内的任务到达序列具有平滑特性，即任务稳定、递增或递减地到 达。预测未来任务强度时考虑局部任务序列比传统动态负载均衡机制考虑的全局任务序列10 具有更精确的预测效果。因此本文提出一种基于任务局部性的动态负载均衡机制，首先采 用一个窗口机制，记录任务到达的局部信息，其次利用一个改进的指数平滑公式计算未来 任务的到达强度值，在任务分配时考虑这个因子就可以达到动态负载均衡的效果。实验结 果表明该负载均衡因子可以有效地降低任务完成时间。 关键词：人工智能；多 Agent 系统；任务分配；负载均衡；任务局部性 15 中图分类号：TP3 Dynamic Load Balancing in Multi-Agent Systems based on Task Locality FEI Chao 20 (School of Computer Science and Engineering, Southeast University, Nanjing 211189) Abstract: Load balancing in multi-agent systems is mainly to minimize the task completion time by coordinating each node#039;s load. The traditional static and dynamic load balancing algorithms both ignore the influence of task locality which is a subsistent characteristic of task flow in real systems. Task locality refers to the smooth characteristics of the task arrival sequences, namely the 25 tasks arrives stably, incrementally or degressively. Emplying the local task sequences when predicting the future task arrival strength can obtain a more accurate result than employing the global task sequences. Therefore this paper proposes a dynamic load balancing machanism based on task locality, which first adopts a window mechanism recording the local information of task arrival process and then puts forward to an improved exponential smoothing method to calculate 30 the arrival strength of future tasks. Considering this factor in the period of task allocation can achieve dynamic load balancing. Experimental results show that the load balancing factor can decrease the task completion time effectively. Key words: Artificial Intelligence; Multi-agent Systems; Task Allocation; Load Balancing; Task Locality 35 0 引言