Agent任务调度与迁移策略研究

殷锋社

（陕西工业职业技术学院 陕西 咸阳 712000）

为解决目前市场应用中电子商务在效率、成本和业务智能化方面的问题，文中在详细论述移动Agent技术的基础上提出了一种新的电子商务模式。

1 Multi-Agent系统

1.1 概念解析

Agent的5个概念：Agent组织、Agent平台、系统Agent、Multi-Agent系统和Agent应用系统是容易被人们混淆的，在研究移动Agent系统之前，有必要对他们进行诊释。

1）Agent组织

Agent组织可以认为是Agent的集合和移动Agent系统的分布式问题求解机制，也是多Agent系统社会性的一个重要的方面。Agent组织是MAS研究的模型、组织和交互语言3个主要问题之一，组织的形成和演化问题是基于Agent的计算和Agent合作问题求解的关键。多Agent在问题求解中表现的组织形态就是组织结构。面向结构的Agent组织形成方法与人类社会的组织产生机制相符合，是一种目标明确的组织形成方法。一个为了完成一组目标的组织结构[1]为：

其中，A_ID是组织结构标识符，Role是非空的角色集合，Relation是角色关系集合，A_Goal是非空的组织目标集合，Manager是非空的组织管理者集合。

目前，关于Agent组织的形成方法有：①基于协商的合同网协议。当一个Agent发现自己面临的问题难以独立求解或者合作求解更有效时，通过与其他Agent的协商，将其部分或全部任务委托其他Agent来完成，在他们之间形成顾客与服务员关系型组织：②基于依赖关系的社会推理。通过对Agent之间依赖关系的社会推理，发现与其目标有依赖关系的其他Agent，与他们形成不同形式的合作组织；③基于对策论的联盟形成。通过联盟效用的计算与分配，依据Agent个体、联盟和群体理性原则，在Agent之间形成不；一习的联盟：④基于价洛调控的市场机制，通过市场价格的调整，Agent形成供求平衡下的买卖关系；⑤面向结构的组织形成。

组织结构的设计过程一般由5个步骤完成[2]：

①由不同Agent的共同目标出发，确定组织目标.；

②根据组织目标进行任务分解，划分出不同的子任务；

③由子任务设计组织角色。

设一个组织中的Agent a和Agent b有部分共同求解目标，Agent a有目标集Ga，Agent b有目标集Gb

其中goalcl，goalc2是Agent a和Agent b的共同目标。在进行组织结构设计时，用户向系统发出任务请求，Agent模板创建两个Agent a和Agent b，系统Agent根据请求首先设计一个空的组织结构框架。并通知Agent a和Agent b，Agent a和Agent b收到组织结构框架设计成功的消息后，向系统发送各自的求解目标，供事务服务Agent进行任务分解，进一步完成组织目标和组织角色的设计。如果Agent a和Agent b没有共同目标，则组织结构设计失败，系统终止。

Agent组织角色的创建基于组织目标。通过把组织目标分解成各个子任务，并把相同或相似的子任务合并，由角色承担不同的子任务，完成组织角色的创建。已创建的角色统一放入角色字典中。在创建过程中如果遇到相同或相似的组织角色则进行合并，并记录组织角色的需求数量，供具体组织形成时参考使用。

在二演算中引入了一个新的操作原语new，用来表示创建一个空的组织结构，表示为new os，其中create org表示组织结构创建成功以后，启动该进程建立具体的Agent组织。Milner给出了基本演算的形式语义。组织结构设计的语义[3]可描述如下：

MAS_ORG={user.Request

task

agent template.Create

Agent a，Agent b

agent Tran.Create

an empty os_frame&inform （msg， Agent a， Agent b））

match （msg）

Agent a.Send&Agent b.Send

Ga{goalal， goala2，……，goalcl， goalc2}

Gb{goalbl，goalb2，……，goalcl， goalc2）

Result=?common goal（Ga Gb）

if result=EMPTY

return （fail）

new os （os_frame）

task decomp （os_oal， os_task， Ga，Gb）

create_roles （os_task）

create_org（roles）

}

其中，EMPTY表示空集合。

2）Agent平台

Agent平台（也称为Agent系统）是在Agent理论基础上设计出来的提供给用户开发或运行Agent应用系统的支撑环境，是MAS的重要组成部分。GeneralMagic公司的Telescript，IBM公司的Aglet和南京大学的Mogent等都是比较成熟的纯Java的Agent平台。Agent平台的作用是负责为移动Agent建立安全、正确的运行环境，为其提供最基本的服务（包括创建、传输、执行），实施针对具体 Agent的约束机制、容错策略、安全控制和通信机制等监督与控制功能。它还提供了一些用户对系统进行访问的方法，主要包括Agent和系统Agent的启动控制、状态的获取、系统的输入输出、系统资源的维护和系统的关闭等。

Agent是用户编程的主要对象，用户利用Agent平台中Agent模板创建Agent a终端用户填写Agent的属性和模板中的任务字典，在平台运行时，Agent类具体化为一个Agent实例，其属性和行为来自模板。Agent为了实现移动，发送消息等通讯功能需要调用一些系统Agent的功能，这种调用是通过对系统Agent代理的Clone上的方法调用来实现，这样的调用出于安全性考虑。

3）系统 Agent

系统Agent主要目的是为了实现移动Agent的定位、移动和发送消息等功能，它被分成几个部分，每个部分实现部分相对独立的功能。它通过注册到自身的系统助手和平台进行通讯，调用平台上的函数，同时平台可以直接对系统Agent进行访问。在一个平台上有多个系统Agent，承担不同的任务，如目录服务、事务服务、事件服务、应用服务和安全服务等，目录服务维持Agent名字和其传输地址对应的目录，提供移动Agent的定位信息，形成路由选择；事务服务实现移动Agent的创建、移动、调度和资源分配；事件服务包含Agent传输协议和Agent通信协议，实现移动Agent间的事件传递；安全服务提供安全的执行环境；应用服务提供面向特定任务的服务接口。

4）Multi-Agent系统

Multi-Agent系统[4]（Multi-Agent System， MAS 是由一些联合其知识、目标、职能和计划的协作承担任务或解决问题的不同的计算实体组成的集合，这些集合元素就是Agent，它们具有相互作用以实现到总的目标。MAS可被定义为：

其中，AP，As，Ao 分别表示 Agent平台、 系统 Agent和Agent组织。每个目标由若干Agent协作完成。由此可见，MAS是由Agent平台、系统Agen t和Agent组织组成的系统。

5）Agent应用系统

Agent应用系统是在Agent平台上开发出来的程序系统，Agent是系统中的工作实体，Agent平台是它的运行环境。实际上，Agent应用系统就是拥有一个或多个Agent组织的系统。如基于移动Agent的智能电子商务系统、智能搜索引擎等。以上五个概念之间的关系如图1所示。

图1 Agent应用系统Fig.1 Agent application system

1.2 研究现状

MAS的研究始于20世纪70年代的分布式人工智能。此后，MAS的研究内容随着年代的变化而不断深入，MAS不仅仅是DAI领域的研究问题，同时相关科学的研究成果对它也起到了重要的影响作用，如管理科学、经济学和社会学等。对经济规律如市场机制、游戏理论、平衡概念等的深入研究将用于设计Agent交互策略。MAS研究者借助于游戏理论的研究成果，将其用于Agent谈判策略的设计。管理学中的组织理论研究帮助我们认识并设计Agent组织。社会学中关于人类行为的研究则能使Agent具有人类社会某些特征，如角色分配、团队和竞争等。MAS为AI的研究提供了一个新的机器学习、知识发现和知识表达模型。

1.3 Agent管理模型

为了加快移动Agent技术[5]的发展和推动其具体应用，一些标准化组织制纷纷订了Agent规范，最有影响力的国际组织有OMG下属的Agent Working Group和FIPA的MASIF规范、FIPA的FIPA97-99规范对Agent的名称、管理、迁移、语言等进行了标准化。IBM提出了ATP （Agent Transport Protocol）框架结构，是一个Agent传输协议的最小实现。Agent管理是其应用的前提，负责Agent的的创建、注册、agent定位、通信和移植等操作。Agent管理模型如图2所示。

图2 Agent管理模型Fig.2 Agent management model

1.4 典型的Multi-Agent系统

1）General Magic公司的Telescript

Telescript是General Magic公司推出的第一个商用移动Agent系统。它是用Telescript语言（一种面向对象的解释性语言）编写的。在Telescript中，Agent被编译成为一种虚拟机的字节码，该虚拟机是每个服务器的一部分。每一个网络站点运行一个服务器来维护一个或多个虚拟的地点，地点通过检查Agent加密的信任状来识别其主人}`'1}a Agent之间的通信方式有：运行在同意地点的Agent可以相互调用对方的方法；在不同地点运行时需要建立连接，互相传递对象。Telescript是一个比较成功的移动Agent系统，其安全性、容错性较好，执行效率较高，但由于Java的流行和优势，必然导致它的失败。General Magic公司开发了基于Java的Odyssey系统。

2）IBM公司的Aglet

Aglet是agent与applet合成的，是由日本IBM公司用纯Java开发的移动Agent系统，并提供着实用的平台一Aglet Workbench，让人们开发或执行移动Agent系统。到目前为止，Aglet是非常成功和全面的系统，这主要表现在：Aglet系统首先提供一个上下文环境来管理Agent的基本行为，如创建、复制、分派、召回、唤醒以及清除等。Aglet采用消息传递的方式来传递消息对象进行通信。此外，基于安全上的考虑，Aglet并非让外界直接存取其信息，而是透过一个代理（proxy）提供相应的接口与外界沟通。Workbench是一个可视化环境，用来建立使用移动Agent的应用系统.

2 基于组织的动态资源分配

2.1 资源描述

网络结点上的资源是Agent完成任务的基础，把与网络结点配置有关的情况称为该结点的系统资源。将资源分为设计资源、系统资源和Agent资源，并给出了系统资源的描述。实际上，任务设计和Agent都属于MAS讨论的问题，其系统资源的描述也不全面。文中将Agent执行任务所需的资源归结为系统资源，包括机器硬件资源、软件资源、网络设备资源和信息资源。系统资源[6]具体描述如下：

Structure Sys Source

{

Integer NetNode 一 umber；

Structure Hard_Source；//机器硬件资源

Structure Soft_Source；//软件资源

Structure NetDevice_Source；//网络设备资源

Structure Info_Source；//信息资源

}

Structure Hard Source

{

CmpString Cmp_CPU；

CmpString Cmp_RAM；

CmpString Cmp_HD；

CmpString Cmp_Multi-Media_Dev；

CmpString Cmp_Input_Dev；

CmpString Cmp_Output_Dev；

}

Structure Soft Source

{

SoftString Soft_OS；

SoftString Softes Net；

SoftString Softes Application；

}

Structure NetDevice Source

{

NDString ND_Router；

NDString ND_Switcher；

NDString ND_Gateway；

}

Structure Info Source

{

InfoString Info_DB；

InfoString Info_KB；

InfoString Info_Files；

}

2.2 动态资源分配策略

随着移动Agent应用的发展，如何为不同服务质量要求的用户合理的分配有限的资源、提高使用效率，成为近期研究的热点。近来研究者把微观经济学的方法引入移动Agent的资源分配领域，为这一领域研究提出了崭新的思路。它们存在以下问题：1）只考虑了Agent的竞争，没有考虑Agent的协作；2）没有考虑资源的时间性；3）由于算法较复杂，导致了较大的系统开销。可以采用操作系统中关于资源分配的策略进行Agent资源分配，但由于Agent资源含义不仅局限于硬件资源及Agent的动态、移动、协作等特性，简单的操作系统资源分配策略是难以适应Agent资源分配的要求。由多个子目标组成的Agent组织执行用户提交的任务，子目标由Agent协作完成，为了实现组织的目标，组织就应成为资源分配的基本单位考虑到资源的动态性及组织任务的执行时间、紧迫性和重要性等因素，这里给出了一种基于组织的动态资源分配算法。

3 基于EP算法的Agent任务调度

3.1 调度方法概述

Agent调度问题就是如何利用有限的网络资源和时间完成指定的多个任务，属于Job-shop问题。Job-shop是一类复杂且极具代表性的生产调度问题，其复杂性超乎想象，为解决这一问题，学者们作了大量研究工作，尝试了许多方法，这些方法可分为两类：指派方法和进化计算。

3.2 EP算法原理

进化规划（Evolutionary Programming，EP）最早是由美国的L.J.Fogel，A.J.Owens等人首先提出的，EP是进化计算中的代表算法之一。文献证明了他的动态寻优机理。算法流程如图3所示。

图3 EP算法流程Fig.3 EP algorithm flow

1）将问题的解编码为数字串；

2）随机产生S个可行解构成的初始种群，S为种群规模；

3）将当前种群中的S个个体进行变异，产生新的个体：

4）计算所产生的个体适应度函数值；

5）采取父子竞争策略，从2S个体中选出S个个体作为新一代种群，返回步骤③，重复此过程直到获得满意的解或达到给定的迭代次数。

以上算法是标准的EP算法，变异算子采用的是高斯变换，终止条件采用最大进化代数或出现满意的个体。

3.3 Agent任务调度

调度任务是基于时间的序列，任务之间除了具有逻辑上的相关性外，还具有时间上的相关性，即任务必须在规定的时间内完成。调度方案S可以被描述为一个定时任务的序列集合，即

其中，Pl（t）代表第 1 个任务。

Pa（t）存在的约束如下：

1）定时

必须满足下列时间约束is（i>+t（L）ate（1）

2）资源限制

任务的合理调度以使网络负载均衡，充分发挥系统资源的效用。Agent的自治性、自适应性、协同性和可移动性等显著特点为解决分布任务处理问题提供了新途径。多Agent系统中的任务通过Agent调度器统一调度。系统任务分解Agent将求解的问题分解为若干子任务，并提出调度请求，调度器考虑到各任务的执行条件，如资源、时间、优先度等，选择一定的调度算法，确定调度方案。系统资源由资源管理器管理和调配。执行任务的各Agent根据系统资源分布和实时要求派遣到相应的目标主机进行任务处理。调度模型如图4所示。

图4 Agent调度模型Fig.4 Agent scheduling model

4 移动Agent迁移

4.1 迁移机制分析

移动Agent（Mobile Agent，MA）的迁移与分布式对象的交互及Java Applet的下载有着很大的不同。在基于CORBA或DCOM的分布式对象系统中，一个对象能够通过网络远程地调用其他对象的方法。但是，在两个对象的交互过程，没有任何一个是移动的。WWW中Applet的下载也仅是提供了一种从Web服务器把代码下载到Web浏览器的机制，并没有为相应状态信息的迁移提供任何机制。

4.2 基于Java的动态迁移机制

MA的体系结构应包括Agent代码部分、运行环境部分和Agent状态部分。代码部分是MA迁移过程中不可缺少的部分，是传送给“数据”执行“计算”的部分；为了能在异构网络环境中迁移，MA应具有与平台无关，安全性要求高等特点，而Java可以较好的满足这些要求。因为Java代码的平台无关性和Java虚拟机的广泛分布性，为MA提供了良好的运行环境，具体包括MA所需的资源，对MA代码的执行和迁移请求的响应，提供安全性认证的信息等：状态部分保存MA在移动之前的状态信息，以便当Agent迁移到另一个结点后重新获取这些状态信息，提高运行效率。

5 结束语

本章介绍了MAs的研究现状与研究内容，解析了Agent组织、Agent平台、系统 Agent，Multi-Agent系统和 Agent应用系统5个概念之间的关系，讨论了Agent组织结构的形成机制及形式化描述。在MAS中，为了使已分配资源的移动Agent迁移到指定的结点执行任务，需要解决Agent的资源分配、任务调度和迁移问题。

[1]Geun-Sik J，Chae Y M.Intelligent electronic commerce[J].Expert Systems with Applications，2003，24（2）:151-151.

[2]Ryszard K，Lee M.Artificial intelligence in electronic commerce[J].Lecture Notes in Computer Science，2001，21（12）:133-134.

[3]Turowski K.Agent-based e-commerce in case of mass customization[J].Int J Production Economics，2002（75）:69-81.

[4]Malcolm B，Brian S.E-commerce oriented software agents[J].Computer Law&Security Report，2003，19（3）:201-211.

[5]Maamar Z.Association of users with software agents in ecommerce Electronic Commerce[J].Research and Applications，2002（1）:104-112.

[6]Fingar P.A CEO's guide to e-Commerce using objectoriented intelligent agent[J].Commerce Net Research Report，1998，9（19）:18-20.