社会系统MAS分布仿真中的Agent优化调度算法

戴华，林杰

（同济大学经济与管理学院，上海 200092）

社会系统MAS分布仿真中的Agent优化调度算法

戴华，林杰

（同济大学经济与管理学院，上海 200092）

针对分布式多Agent系统在复杂社会系统仿真应用中的运算特性，设计了一个基于分布式结构的Agent调度框架并提出了Agent的动态优化调度算法.该算法综合考虑了仿真过程中仿真节点运算负载和Agent通信结构的变化，通过优化Agent的调度和分配实现各仿真节点负载的动态均衡以及多Agent系统中跨节点全局通信量的减少.仿真实验分析表明提出的算法能够有效提高此类仿真应用的运算性能以及减少仿真执行的时间.

多Agent系统；复杂系统；分布式仿真；调度优化

1 引言

随着计算机技术的发展和广泛应用，在许多复杂社会系统（如制造系统，供应链系统等）的分析和研究中，利用计算机进行建模与仿真是广泛使用的一类分析方法和技术［1-3］.特别是当前流行的基于Agent的微观仿真建模方法，成为了研究复杂社会系统的重要方法之一［4，5］.多Agent系统（MAS）能够对复杂社会系统中的各个对象实体进行有效的定义以及功能特性上的模拟，并在计算机系统中进行仿真实验，通过实验的数据和评估指标对系统运作和性能进行直观的量化分析和评价，具有很好的可重复性、可试验性、可扩展性等优点.

为适应复杂和更大规模仿真应用的需要，分布式的仿真运行架构成为必然的选择.对于基于分布式多Agent系统的仿真应用而言，大量参与仿真的Agent由于仿真过程中运算量的可变性和不可预知性，极易会造成局部某些仿真节点的运算负载过重，从而影响整个仿真运算的效率甚至使仿真过程崩溃.同时，在分布式环境下Agent之间的动态消息通信也会带来大量冗余的网络通信量而影响仿真的执行时间和效率［6，7］.因此在有限的计算资源条件下，实施较大规模的系统仿真实验时，平衡运算节点的负载并减少节点间冗余的消息通信成为提高此类系统仿真运算效率和性能的关键.在传统分布式计算的负载均衡调度问题中，主要是针对计算任务如何在运算节点间进行合理有效地调度和分配［8，9］，而基于Agent的分布式仿真中，Agent作为运算的基本单元和载体，负载的平衡过程主要依赖于Agent在各个仿真节点之间的调度和分配.此外，在基于Agent的系统仿真中，参与仿真的Agent都是基于某个特定功能和结构进行划分，并不是同质的计算单元，在仿真过程中不能将一个Agent的计算任务简单分配给另一个Agent.同时，复杂社会系统的仿真过程往往是基于离散事件驱动，仿真Agent之间有复杂的逻辑关联，Agent的行为会受到其他某些Agent的影响，在不破坏各个事件逻辑执行序列的情况下进行Agent的动态调度也是一个复杂的过程.在已有的相关研究中.如将Agent视为独立且相互关联的计算单元，通过对Agent计算任务的进行合理调配实现任务的高效执行［10，11］.此外，基于某些设定的计分规则来对Agent的移动和调度进行判断的方法［12］被设计出来以解决局部计算资源的过载问题，文献［6，7，13，14］针对MAS中Agent的消息通信特性，提出了在相关应用中减小和优化MAS消息通信的一些方法.经济市场领域中资源分配的博弈机制也被用于解决和实现MAS负载动态均衡问题［15］.

与传统的并行与分布式计算或仿真过程相比，基于多Agent系统的社会系统仿真具有自身的一些特性.如上所述，目前提出的一些方法中，或是不完全适合基于Agent的社会系统仿真中的负载均衡与调度，如基于任务分配和调度的方式；或是在Agent的分配和迁移上没有充分考虑到Agent之间通信交互的关联性和动态性，此外，普遍采用固定的负载监测阈值来作为负载调度的依据，对仿真过程中复杂多变负载状态缺乏灵敏性而影响实施调度的效果，因此已有的一些方法不能很好地解决此类并行分布式仿真应用的负载均衡和调度问题.本文针对此类仿真的运算特性，综合考虑了Agent之间的通信结构和各仿真节点负载的动态变化，提出了实施动态负载调度的框架及相关的Agent优化调度算法来提高分布式仿真运算的效率和性能.仿真实验的结果表明，所提出的算法在总体负载均衡性和仿真运行的时间上均有较好的表现.

2 问题描述

2.1 Agent调度优化问题

在基于分布式Agent的仿真运算中，大量Agent散布在不同分布式主机节点上，Agent以消息交互的方式进行通信和协作，Agent之间的消息通信因Agent所处节点位置的不同，包括节点内部的消息通信和跨节点的消息通信，通过Agent在节点之间的迁移能够实现这两种消息通信的转换.由于跨节点的消息通信在处理时间的消耗上要远大于内部的消息通信处理，因此一个最优的Agent调度分配既要保证各个仿真节点不因为过载造成仿真失效，又要最大限度地减少Agent系统中跨节点的全局网络消息通信量，即系统通信负载.式（1）定义和描述了一个最优的Agent调度分配应满足的条件，其中σ表示所有节点运算负载的均方差，Φ表示MAS中跨节点的Agent通信总量，α是权重系数，Wk表示任意某个节点的运算负载量，表示所有节点的平均负载量，Th是设定的节点负载上限阈值，Cij是任意两个不同节点Hi，Hj之间的通信量，m表示分布式仿真节点的数量.

求解满足上述条件的Agent分布是一个典型的NP问题，同时由于仿真运行中节点负载和Agent交互是动态可变的，特别在Agent数量相对较多时，在解空间中求解一个全局最优调度方案需要消耗大量的计算时间，因此无法有效地满足系统仿真过程中动态实时调度的要求.为了在动态调度过程中能实时地做出合理的Agent调度和分配，本文通过周期性监测及调度优化的方法，利用各周期时间点相应的节点负载状态与Agent之间的通信结构来实时地给出一个局部优化的Agent调度和分配方案，实现动态的Agent通信优化和节点负载均衡，以此提高系统运算效率并加快仿真执行时间.

2.2 基于分布式MAS的社会系统仿真特性

与其他分布式计算系统类似，基于MAS的社会系统分布式仿真也是一个分布式计算过程.但由于社会系统的运作特性，其仿真运算有如下特点：1）由于社会系统自身结构和功能的复杂性，仿真运算过程中的负载和Agent之间的通信结构模式较一般运算有更高的随机性和动态性；2）社会系统仿真模型中，参与仿真运行的Agent往往是具有特定功能和角色的实体，运算任务在Agent之间不具备一般的传递性；3）在基于离散事件驱动的社会系统的仿真过程中，Agent的调度和迁移需要协调和维护整个仿真过程的时间同步和各个并发事件的逻辑顺序.

针对上述运算特性，在本文设计的Agent动态优化调度算法中，进行了以下前提条件的假设：1）仿真Agent在计算资源使用权限上是一致的且其运算不依赖于某个特定的仿真节点；2）Agent之间跨节点的消息交互时间远大于在节点内部的通信；3）Agent在不同节点之间移动的代价是相同的.

3 动态负载均衡调度算法

3.1 调度框架

本文设计了一个层次化的分布式Agent调度框架来实现对仿真Agent的动态调度和分配，图1给出了调度框架的基本结构，其中全局负载调度Agent（GLSA）是进行全局调度和控制的Agent，区域负载调度Agent（DLSA）是分布在各个仿真节点上负责对应节点区域调度操作的Agent.GLSA与各DLSA共同构成了层次化的调度控制结构，分散在各节点的DLSA执行与所在节点相关的Agent调度与分配操作，GLSA则在更高的层面对全局调度进行协调，该结构模式有效地分解了实施调度控制操作的运算任务，充分发挥了分布式计算的优点.在系统运行过程中，GLSA以及分散的DLSA均常驻于对应的仿真节点上，其他参与仿真的Agent则根据设计的调度分配算法在各仿真节点之间进行动态地调度.

图1 Agent层次调度框架Fig.1The level scheduling framework for agent

在需要进行Agent调度操作时，提出的算法通过选择一个最佳Agent组的方式来实施Agent在相应节点的调度迁移，算法定义的Agent组是包含若干Agent的一个集合，组中Agent的选取充分考虑了当前Agent之间的通信关联和聚集性.相比于提出的对Agent进行逐个单独选取并迁移的调度方式，基于选取最佳Agent组的调度方式不仅能快速有效地降低过载节点的负载，还能避免逐个调度方法中由于未充分考虑Agent之间的通信结构和关联性而增加额外的跨节点通信量的情况，从而利用Agent的优化调度最大限度地减少MAS中的全局网络通信量.框架中动态调度的实现主要包括两个过程，一个是在仿真过程中对节点负载进行周期性监测与控制；另一个是发生节点运算过载后进行Agent的优化分配和调度，该过程包括对过载节点中最佳迁移Agent组的选取及Agent组向目标节点的迁移. 3.2负载动态监测和调度控制

负载动态监测过程通过设定的某个周期时间对节点的负载状态进行监控，当某个周期监测点发生节点负载超过特定阈值时，将执行相应的Agent优化调度操作，此时仿真的逻辑时间推进将暂停，直至整个调度过程完成；反之仿真过程将不会停止.为了能更好的实现各个节点负载的均衡调度以提高节点的计算效率，本文运用了可变阈值的监测方法，并利用式（2）给出了可变阈值的定义.其中Th（t）表示在监测周期时间点t的负载阈值，（t）表示所有节点在t时间点的平均负载值，λ是时序相关的负载平均值的比重系数，γ是负载阈值的调节系数，主要是控制可承受的负载扰动范围.

下面的算法给出了GLSA和各DLSA共同实施负载监测和控制操作的描述.

步骤1在监测时间周期时间点t，GLSA接收来自各个DLSA发送来的节点负载值Wi（t）；

步骤3将各个仿真节点按当前负载量的从大到小排列得到负载状态队列Q，判断Q中是否有节点负载值大于当前的Th（t），如果成立转入步骤4，否则转入步骤7；

步骤4挂起当前的仿真推进进程，并向超过当前负载阈值的仿真节点的DLSA发送负载调度信息和当前负载状态队列Q；

步骤5结合当前负载状态队列Q，过载节点的DLSA选择相应的迁移Agent组和迁移目标节点，并将组中的Agent迁移进行迁移，实现负载的均衡调度；

步骤6继续当前仿真运算进程；

步骤7在下一个监测周期返回步骤1.

3.3 Agent优化分配与调度

如上所述，提出的算法在实施Agent优化调度时，采用了基于Agent组的分配和调度方式.Agent组的选择则由Agent之间的通信关联度来确定.Agent之间的消息交互是MAS运行的基础和引起系统通信量变化的因素，因此本文中通过Agent之间的消息交互数量来度量Agent之间的关联程度和Agent内部及外部的通信量大小.在式（3）中利用Agent的消息量定义并量化了在两个节点之间迁移某个Agent组引起的全局通信量变化指标，其中mij表示任意两个Agent，ai,aj之间的消息通信量，G表示某个包含若干Agent的备选Agent组，Ai和Aj分别表示对应节点当前包含的Agent集合.

由式（3）的定义可知，为尽量减少跨节点的Agent通信量，在选择要迁移的Agent组时，其Δ（G）数值越大，则表明该组越适合作为实施调度迁移的Agent组.因此式（3）可以作为选定最佳迁移Agent组的判定指标.在下面的算法中给出了当需要进行负载调度操作时，在对应过载节点中DLSA进行目标迁移节点和最佳迁移Agent组选择的算法步骤：

步骤1利用过载节点（Hi）当前的负载量（Wi），通过公式OutNum=「（Wi-Th）Ni/Wi」来量化需迁移的Agent数量；

步骤2在当前节点负载状态队列Q中，选取队尾负载最小且未被选择过的节点（Hj）作为调度迁移的目标节点，并结合Hj当前的负载量Wj用公式InNum=「（Th-Wj）Nj/Wj」计算Hj可容纳的Agent数量；

步骤3从当前过载节点Hi中选取某个未被遍历过的Agent（ai），并将ai放入备选迁移Agent组G′中；

步骤4将与ai关联的所有Agent放入一个临时Agent集合T中；

步骤6将ak从S中取出，并加入G′中，同时将与ak存在通信关联的且不在G′中的Agent放入临时集合T中；

步骤7判断G′中的Agent数量是否小于min（InNum,OutNum），若是则转入步骤5，否则将本次得到的备选组G′放入一个备选组的集合S中；

步骤8如果Hi中的Agent遍历未完成，则转入步骤3；

步骤9在备选组集合S中查找具有最大Δ（G）值的备选组，并将该组选定为迁移到Hj的Agent组G，并得到本次优化调度的Agent组与目标节点的组合〈G,Hj〉；

步骤10若迁移组G中累计的Agent的数量小于OutNum，则返回步骤2.

算法在Agent组中成员Agent的选取上利用了Agent之间的通信关联性以及动态交互结构，通过当前的负载状态队列信息，并结合定义的InNum和OutNum来量化平衡各节点负载时所需调度的Agent数量，将队首过载节点中的Agent以优化分组的形式向负载相对较轻的队尾节点进行调度迁移.

3.4 算法性能分析

在上述算法实现中，对目标迁移节点的选择主要根据负载状态队列来实现，求解并实现队列的排序计算时间主要取决于主机的数量，其时间复杂度为O（m2）.在最佳Agent组的生成和选择上，设ρ=n/m表示节点的Agent平均密度，其中n,m分别是Agent总数和节点数.可知过载节点中选取Agent组的大小为（1-Th/Wi）ρ，确定最佳Agent组需要对该节点的所有Agent（数量为ρ）进行遍历，所以组选择过程的时间复杂度为O（ρ2）.

4 实验分析

4.1 实验平台

为了验证所提出算法在基于MAS的社会系统分布式仿真应用中的有效性，本文利用面向Agent的编程工具组件JADE开发了一个实验平台，该平台用于实施基于多Agent的供应链场景模型的运作过程仿真，同时实验平台利用设计的GLSA及DLSA来实现层次化的动态调度算法，其中实现算法所涉及的Agent基本功能属性如消息交互以及迁移等都继承JADE组件提供的底层功能接口.在平台中有五种类型的仿真Agent来构建供应链仿真模型，其中包括生产制造Agent，生产计划Agent，库存Agent，运输Agent以及运输计划Agent.在实验分析中，用于实施仿真实验的不同规模和结构的供应链场景MAS模型都由继承这五种Agent类型的若干仿真Agent构成.

在供应链场景的MAS模型中包括了由仿真Agent组成的若干供应商、生产商以及分销商，模型的仿真过程是基于离散事件驱动，模拟供应链场景模型完成一定数量的产品订单的过程.在仿真时各分销商给出一定数量的订货量需求，模型在订单驱动下开始运作，各生产商利用供应商提供的原材料根据自身的生产线进行产品生产，原材料及产品在供应商、生产商及分销商之间运输，当各个分销商的订货量满足后仿真过程结束.仿真过程中参与仿真的Agent根据各自的角色功能自适应地交互和协作，各仿真Agent的事件活动运用保守时间管理机制来推进，直至完成设定的模型场景任务.在这个过程中，由于仿真逻辑时间的推进以及仿真Agent各自运行状态，Agent之间的相互通信关系和运算负载都会动态地变化.

4.2 仿真实验的环境和参数设定

在仿真实验中利用十台互联的主机组成分布式仿真节点实施仿真分析实验，其中一台机器作为中心控制节点，其他主机作为仿真运行节点.在仿真监测中，节点的负载状态利用公式Wi=βUc+（1-β）Um,0＜β＜1度量，其中Uc和Um分别是主机的CPU和内存的使用率，β为两者之间的权重系数.根据仿真实验环境和不同仿真模型，在表1中给出了实验中实施调度算法所设定的各个参数值，其中监测间隔周期根据仿真规模在30～60s之间进行调整.

表1 实验参数设定Table 1Parameters in experiments

4.3 实验对比分析

实验分析主要从负载均衡性能和仿真执行时间的消耗两个方面，对所提出的优化调度算法进行检验.实验中引入了静态Agent均匀分布方法作为参照方法与所提出算法进行对比分析.参照方法在仿真执行前将所有仿真Agent随机地平均分配到不同节点上，且仿真过程中不进行Agent的动态调度.由式（2）中对负载均方差的定义可知，负载值均方差σ的数值越小，说明在仿真过程中各节点的计算负载具有较好的均衡性和较小的波动，计算资源的综合利用率就越高，同时节点的过载风险也相应降低，因此σ值可作为分布式节点综合运算性能的一个有效指标.在图2中将本文提出的算法（PA）和引入的参照方法（RA）在负载均衡性能方面进行了对比.

图2（a）给出了在上述两种情形下，同一仿真模型的仿真运行过程中各节点的负载值均方差σ随监测周期时间点变化的σ值.从图中可以看到，在整个仿真运行过程中使用提出的动态调度算法后得到的σ值总体上要低于作为对比的参照方法，且该数值的波动也相对较小.此外，在图2（b）中给出了在两种情形下，针对不同Agent规模（NAgent）的仿真模型，对应的整个仿真过程中得到所有σ值的平均值（σav）变化.图中σav的变化趋势表明，随着仿真Agent规模的增加，在整个仿真过程中两种情况下的σav都呈逐步下降趋势，但在PA情形下的σav总体上低于RA情形下的数值，这说明实施了提出的优化调度算法有更好的全局负载均衡性.

图2 负载均衡性能分析Fig.2 The analysis of load balancing performance

图3对上述两种情况下的仿真运行时间进行了对比分析，图中给出了在不同Agent仿真规模NAgent下提出算法（PA）与参照方法（RA）的仿真执行时间的比值η（η=TPA：TRA）变化趋势.在Agent规模较小时，两者的执行时间比值接近且约大于1，表明此时两者的仿真时间消耗比较接近，但PA情形下的时间消耗稍多，这是由于在动态调度算法中对Agent组选取和迁移操作会产生额外的时间消耗，执行优化调度后减少的时间消耗无法从总体上抵消算法产生的时间消耗.但随着仿真Agent规模的增大及相互通信增多，所提出算法在仿真执行时间上的占比开始逐渐减少，图中可以看到PA与RA的仿真执行时间比值η呈逐步下降趋势.这表明在相对较大的Agent规模下，优化调度后减少的时间消耗逐渐弥补了调度过程本身产生的时间消耗，并使总的仿真时间得到有效降低.因此运用提出的动态优化调度算法在总的执行时间上也有明显的改善.

图3 仿真时间比值η（η=TPA：TRA）与Agent规模NAgent的关系Fig.3The relationship between simulation time-ratio η（η=TPA：TRA）and Agent scale NAgent

5 结束语

基于多Agent系统的计算机仿真方法在社会系统分析和研究中越来越普遍，提高此类仿真应用的分析能力和运算效率变得十分重要.本文针对基于多Agent系统的分布式仿真运算特性，提出了一个优化Agent分配的动态调度算法实现各仿真节点的负载均衡以及全局通信结构的优化.该算法综合考虑了仿真过程中仿真节点的负载状态和MAS通信结构的动态变化，设计了相应的可变负载阈值监测和基于Agent组选择和迁移的优化调度方法.通过仿真实验对比分析，提出的方法在仿真运行时间和负载均衡性能上均要优于作为实验对比的静态Agent随机均匀分配的方法.文中提出的方法对于相关的基于分布式多Agent的仿真和运算系统也有一定的借鉴性.此外，当前算法设计中对一些相关前提条件进了简化和限定，如Agent运算依附性、Agent迁移代价以及异质跨网段环境等，同时，Agent迁移机制设计与优化对于提升MAS运算的执行性能也有着一定影响，在今后的研究工作中，将会进一步考虑这些相关因素对算法进行改进和完善.

［1］盛昭瀚，张维.管理科学研究中的计算实验方法［J］.管理科学学报，2011，14（5）：1-10.

Sheng Zhaohan，Zhang Wei.Computational experiments in management science and research［J］.Journal of Management Sciences in China，2011，14（5）：1-10.（in Chinese）

［2］刘晓平，唐益明，郑利平.复杂系统与复杂系统仿真研究综述［J］.系统仿真学报，2008，20（23）：6303-6315.

Liu Xiaoping，Tang Yiming，Zheng Liping.Survey of complex system and complex system simulation［J］.Journal of System Simulation，2008，20（23）：6303-6315.（in Chinese）

［3］Lee J H，Kim C O.Multi-agent systems applications in manufacturing systems and supply chain management：A review paper［J］. International Journal of Production Research，2008，46（1）：233-265.

［4］李英，马寿峰.基于Agent的仿真系统建模［J］.系统工程学报，2006，21（3）：225-231.

Li Ying，Ma Shoufeng.Modeling of agent-based simulation system［J］.Journal of Systems Engineering，2006，21（3）：225-231.（inChinese）

［5］张少苹，戴锋，王成志，等.多Agent系统研究综述［J］.复杂系统与复杂性科学，2011，8（4）：1-8.

Zhang Shaoping，Dai Feng，WangChengzhi，et al.Summary on research ofmulti-agentsystem［J］.ComplexSyatemsand Complexity Science，2011，8（4）：1-8.（in Chinese）

［6］Boukerche A，Das S K.Reducing null messages overhead through load balancing in conservative distributed simulation systems［J］. Journal of Parallel and Distributed Computing，2004，64（3）：330-344.

［7］Jang M W，Agha G.Adaptive agent allocation for massively multi-agent applications［C］//Ishida T，Gasser L，Nakashima H.Massively Multi-Agent Systems I.Berlin，Heidelberg：Springer，2005：25-39.

［8］GrosuD，ChronopoulosAT.Noncooperativeloadbalancingindistributedsystems［J］.JournalofParallelandDistributedComputing，2005，65（9）：1022-1034.

［9］Zhang Z，Fan W.Web server load balancing：A queueing analysis［J］.European Journal of Operational Research，2008，186（2）：681-693.

［10］Oguara T，Chen D，Theodoropoulos G K，et al.An adaptive load management mechanism for distributed simulation of multiagent systems［C］//Proceedings of the 9th IEEE International Symposium on Distributed Simulation and Real-Time Applications，Montreal.Canada，2005：179-186.

［11］Ha B H，Bae J，Park Y T，et al.Development of process execution rules for workload balancing on agents［J］.Data&Knowledge Engineering，2006，56（1）：64-84.

［12］Chow K P，Kwok Y K.On load balancing for distributed multi-agent computing［J］.IEEE Transactions on Parallel and Distributed Systems，2002，13（8）：787-801.

［13］De Grande R E，Boukerche A.Dynamic partitioning of distributed virtual simulations for reducing communication load［C］//Haptic Audio visual Environments and Games，2009（HAVE 2009）.IEEE International Workshop on，IEEE，2009：176-181.

［14］Gonzalez-Pardo A，Varona P，Camacho D.Optimal message interchange in a self-organizing multi-agent system［C］//Proceedings of the 4th International Symposium on Intelligent Distributed Computing.Tangier，Morocco，2010，315：131-141.

［15］Ham M J，Agha G.Market-based coordination strategies for large-scale multi-agent systems［J］.System and Information Sciences Notes，2007，2（1）：126-131.

Algorithm for Agent optimal dispatching in MAS distributed simulations of social system

Dai Hua，Lin Jie

（School of Economy&Management，Tongji University，Shanghai 200092，China）

Accordingtothespecificcomputationalcharacteristicsofagent-basedapplicationsincomplexsocial systems，a distributed agent scheduling architecture is designed and algorithms for dynamic agent scheduling optimization are proposed.The algorithm takes into account the variation of both computation and communication during the simulation process，which implements the dynamic load balancing of each simulation node and the decrease of the overall agent communication that crosses nodes by means of optimizing the agent distribution and scheduling.The experimental results indicate that the proposed algorithms can effectively improve the computational performance and shorten the run-time of such simulation applications.

multi-Agent system（MAS）；complex system；distributed simulation；scheduling optimization

TP391.9

A

1000-5781（2015）06-0844-08

10.13383/j.cnki.jse.2015.06.012

戴华（1981-），男，湖南澧县人，博士生，研究方向：分布式多Agent系统，系统仿真与建模等，Email：dh_myemail@126.com；

2013-11-14；

2014-09-04.

国家自然科学基金资助项目（71071114）；教育部社科支撑资助项目（11YJC630216）；上海市重点学科建设资助项目（B310）.

林杰（1967-），男，四川渠县人，教授，博士生导师，研究方向：信息管理与信息系统，供应链管理，决策支持系统等，Email：linjie@tongji.edu.cn.