网络结构化多Agent系统中基于动态综合关系网的任务分配
2018-07-04武丹凤于思淼曾广平张锐文王乙晴
武丹凤,于思淼,曾广平,张锐文,王乙晴,陈 强
1(辽宁工程技术大学 软件学院,辽宁 葫芦岛 125105)2(北京科技大学 计算机与通信工程学院,北京 100083)
1 引 言
分布式系统[1]通常包含大量具有一定独立自主性并又相互作用的个体,因此人们提出基于多Agent[2,3]模型来对多领域分布式系统进行建模和分析,这就是多Agent系统(Multi-Agent System,MAS)[4-7].当MAS要执行任务时,首先就是将该任务分配给合适的Agent,然后由这些Agent来负责执行,这就是任务分配[7,8].
随着大规模复杂多 Agent 系统的发展,人们提出网络结构化多Agent系统(Networked Multiagent Systems,NMAS)的概念[9-11].NMAS中存在着两种网络:系统所运行的底层物理网络和Agent之间的交互虚拟网络.以云平台为例,其是由搭载了云平台服务器端软件的云服务器、搭载了云平台客户端软件的云电脑以及网络组件所构成的,可抽象为一个大型的多Agent系统.云电脑可看作产生任务的用户,任务可以是通讯、邮箱、数据库存储、文件存储、办公协同等多种应用.云服务器可抽象为执行任务的Agent,其是一种虚拟主机,而部署在一个硬件计算服务器上的虚拟主机群可看作同属一个物理子系统.位于一个机房的多个物理子系统通过交换机等设备相连,形成一个物理网络.不同位置机房的物理网络通过路由器等设备相连,形成更大的物理网络.如机房X内物理子系统A中的云服务器A1与机房Y内物理子系统B中的云服务器B2存在直接的交互关系(如进行文件共享等),则A1与B2之间存在社会关系,而整个云平台这种 Agent 之间的社会关系所形成的网络称为交互虚拟网络.具有社会关系的Agent间是通过实际的通信链路进行交互的,它们之间的物理距离并不一定相同.
由于复杂的网络结构构成,NMAS的任务分配实现难度较大.近几年,东南大学的蒋嶷川等基于NAMS的网络结构,研究了基于Agent物理情境资源和社会情境资源的任务分配模型[7,12].他们指出,在实际的NMAS中,每个Agent会由于其所处的物理位置和社会位置而位于一定的情境之中.物理情境主要指Agent在底层物理网络环境中的周围Agent,而社会情境主要是指Agent在交互网络中的交互对象所组成的情境[7].其所提出的相应的任务分配模型[12]基于Agent物理情境中的资源和物理通信距离,计算出物理情境富集因子,基于Agent社会情境(即交互网络中的周围环境)中的资源和交互距离计算出其社会情境富集因子,两者的加权和为该Agent的综合情境富集因子.对任务所需资源的富集因子最高的Agent优先获得任务,负责该任务的执行.但是,所提出的基于综合情境资源的分配模型没有考虑Agent分配的智能性,也不适用于具有不诚信节点的NMAS,且模型是基于固定网络结构的,在计算社会资源富集因子的过程中需要网络全局信息,并不适合动态的、大型的NMAS.
此外,在分布式NMAS中进行任务分配需要Agent间的横向交互,且在系统的实际应用中,往往需要尽可能快的分配并完成任务,满足用户的需求.但是,已有的任务分配模型对NMAS的任务分配协商过程缺乏深入研究,没有有效考虑底层物理网络拓扑结构和社会组织结构在分配协商过程中的作用,也没有充分利用Agent的社会关系资源,系统中横向通信密集.因此,本文将以最小化任务执行总时间和通信次数为模型优化目标,根据Agent的物理网络关系资源和交互网络关系资源,以及运行过程中形成的熟人[13-17]关系资源,借鉴合同网协议[17-20]的协商过程,研究分布式的基于动态综合关系网的任务分配模型(Dynamic Integrated Relationship Network Model,DIRNM).本文的主要贡献如下:
1)提出了基于物理能力和社会关系资源提供力的任务承包方选择策略.该策略结合直接信任度,尽量保证任务分配的可靠性;充分利用了Agent的社会关系资源,在任务分配时,除细粒度的考虑Agent的物理能力外,将Agent的社会关系资源提供力也纳入考量范围,为任务的再分配做准备,以优化任务再分配性能.
2)设计了基于熟人、物理邻居和社会邻居所构成的动态综合关系网的任务分配协商过程.该算法充分考虑了物理网络组织和交互网络组织的特点和作用,适合大型的NMAS实际应用,在保证分配质量的基础上尽量控制协商范围,提高协商效率,降低任务分配通信开销.
3)提出了基于直接社会关系资源的再分配策略.当任务承包Agent执行任务失败时,可求助自己的直接社会关系资源,以有效减少任务管理Agent重新分配任务的次数,降低再分配的通信开销.
2 相关工作
NMAS已有的任务分配相关工作可分为三类:基于底层网络拓扑的任务分配、基于 Agent 交互网络的任务分配、基于综合网络情境的任务分配.
基于底层网络拓扑分配任务时,不但考虑Agent 自身能力情况,还要考虑Agent在底层物理网络中的实际通信耗费.Agent 获得任务执行权的概率不但与其能力有关,还与其在底层物理网络中的位置有关.此方式能较好地适应底层物理网络拓扑结构的动态改变,有效降低实际的物理通信耗费,但没有考虑到NMAS的社会组织性的作用.基于Agent 交互网络分配任务时,不但考虑Agent 自身能力情况,还要考虑Agent在交互网络中的位置和彼此之间的交互距离,Agent 获得任务执行权的概率不但与其能力有关,还与其在交互网络中的位置有关.此方式有效考虑到多Agent 系统的社会组织性,特别是网络结构组织的作用,可有效降低 Agent 之间交互的代价,但没有考虑多Agent 系统运行时的底层物理网络的情况.基于综合网络情境分配任务时,主要考虑三种因素:Agent自身能力情况、Agent在底层物理网络中的位置和彼此之间的实际通信耗费、Agent 在交互网络中的位置和彼此之间的交互距离.此方式既有效考虑到多 Agent系统的底层物理网络拓扑结构的作用,也有效考虑到多Agent系统的社会组织结构,因此能较好地适应大规模网络结构化多Agent系统的任务分配,但实现难度相对较大,研究成果较少[7].
下面,将对近几年提出的具有代表性的NMAS任务分配模型从模型的控制方式、对目标对象的评估粒度、评估指标选取、是否考虑底层物理网络和交互网络两种网络结构的作用以及是否进行Agent执行任务失败后的再分配机制研究等方面作一特征总结,如表1所示.
针对表1,我们将进行以下分析,以指导本文所所进行的任务分配模型研究工作.
1)评估粒度粗糙.现实情况下,每个对象一般都有自己擅长执行的任务功能类型,且拥有多种资源.如果基于全部功能或资源类型对目标对象进行评估,有可能得出的评估值很高,但是其并不适合执行某类任务,或在需求的某类资源总量上并不占优.在本文所研究的任务分配模型中,将基于任务所需功能类型细化评估粒度,得出Agent执行不同功能类型任务的能力评估值.
2)能力评估指标选取较少.信任度一般用来衡量目标对象的诚信程度,而能力评估用来衡量其实时的任务执行能力.在大多数任务分配模型中,只是基于资源对对象进行能力评估,只有文献[23]和[24]结合了资源外的可靠性或声誉等指标.在本文中,我们拟将预计执行时间、执行不同类型任务的成功率和任务需求的资源作为投标方的物理能力衡量指标,将投标方的直接社会关系资源转换为社会关系资源提供力,并结合直接信任度,对Agent的能力进行较全面地评估.
表1 近年具有代表性的NMAS任务分配模型总结Table 1 Summary of typical task allocation models of NMAS
3)在任务分配模型设计时,考虑节点在物理网络和交互网络中的关系及属性,可提高通信可靠性,降低协商时间,节省通信开销.但是,由于NMAS复杂的结构化综合网络情境,任务分配协商过程的规划复杂,进而导致相关任务分配模型对任务分配协商过程的研究成果较少.表1所列文献中,只有[26]较深入地考虑了两种网络结构的积极作用,但其没有考虑系统中实体分配的智能性、网络拓扑结构的动态变化性,也没有从充分利用社会关系资源的角度出发、基于不同类型邻居节点的关系属性进行分配协商过程的设计.
4)缺乏对任务承包方执行任务失败后再分配机制的研究.表1所列代表性文献中,只有[24]中提到了执行任务失败后的再分配,即如管理者出现故障,则任务执行失败,任务以其它Agent为入口进行新一轮的分配,如任务辅助协作方执行失败,则管理者重新寻找新的协助者.此种任务再分配机制并不能有效利用系统节点社会交互资源,因此,本文在研究NMAS的任务分配模型时,拟基于Agent的社会关系资源,设计任务再分配机制.
3 相关描述与任务分配目标
在本节中,我们将描述动态综合关系网的构成,并定义NMAS中的任务与任务分配.
3.1 动态综合关系网
引言中提到,NMAS既包括系统运行的底层物理网络,还包括Agent之间的社会交互网络.我们将继续以云平台为例,定义NMAS中综合关系网的构成.部署在一个硬件计算服务器上的虚拟服务器Agent群同属一个物理子系统,则本文定义同一物理子系统内的Agent互为物理邻居;机房X内物理子系统A中的云服务器A1与机房Y内物理子系统B中的云服务器B2具有社会关系,可以借助实际的通信链路进行直接交互(如文件共享),则本文定义不属同一物理子系统但可直接进行交互(不需其它Agent引荐)的Agent互为社会邻居.云服务器上的资源(关键是CPU和内存)是有限的,但可将其上的相应耗费计算单元资源的软件重新部署在具有对应云服务的物理邻居或社会邻居之上,即进行多地域跨集群的存储,此时可将此类操作看作是在云平台MAS中的资源协调分配,而针对数据库、文件等不同类型存储的共享可看成是具有不同社会功能需求类型(function identifier,fid)的资源访问任务.此时,每一类型共享任务需相应的具有该fid功能(提供该类型存储)的Agent执行.如某一Agent不具备执行某一类型任务的能力,则其接收到此类型任务请求时,需求助其它Agent执行,传回相关数据.随着合作过程的积累,请求Agent可以和接触频繁、物理距离较近、任务执行成功率较高、质量较好的Agent形成更加亲密的基于某一fid功能类型任务的社会关系,我们称之为Agent基于fid的熟人集.基于fid的熟人集中的成员可以是其物理邻居或社会邻居,也可以是通过物理邻居和社会邻居作为中介结识的平台中的其它Agent.那么围绕任务分配问题的所有这些物理邻居、社会邻居和熟人便形成了Agent的综合关系网.
此外,在人类社会关系中,也存在这样的综合关系网络.如一个软件系统的开发任务,可按开发过程分解为需求调研、需求分析、系统设计、编程、测试等子任务,每一类型的子任务对应一种fid.一个软件项目组内的成员互为物理邻居,不同项目组内的人员可具有社会交互关系,彼此间互为社会邻居.如果一个工程师A执行某一fid类子任务质量高,且花费时间少,则当本项目组或其它项目组一些工程师接收到该类fid任务时,如超出自己能力或时间不允许,会求助该工程师协作完成.随着任务分配协作经验的积累,他们与A会按照任务的社会功能需求fid形成基于特定功能fid的熟人关系.
在综合关系网中,Agent与其基于fid的熟人之间的合作关系是单向的,而与物理邻居和社会邻居之间的合作关系是双向的.图1展示了一个简单的NMAS,在此NMAS中,共有4个物理子系统,分别用SS1、SS2、SS3和SS4表示.子系统中的Agent节点用a表示,节点之间的实线边表示Agent之间存在直接交互关系;带箭头的有向虚线边表示Agent之间基于功能类型fidx的熟人合作关系,箭头指向的是基于fidx的合作提供方,反之并不成立.
图1 NMAS示意图Fig.1 Schematic diagram of NMAS
在NMAS运行过程中,经常会有些Agent节点加入或离开,节点之间的链接也会经常改变,因此,邻居关系及关系属性是动态变化的;而随着Agent任务分配经验的积累,以及Agent诚信和能力的动态变化,其熟人关系也是动态变化的.由此可见,综合关系网是动态的.
3.2 NMAS中的任务与任务分配
定义1.NMAS中的任务.NMAS中的每一个任务t可以描述为一个五元组:
t={id,fid,td,q,dl}
其中,id表示任务标识符,对任务起唯一标识作用;fid表示任务的社会功能需求代码,每个任务对应一种fid;td表示任务的文本描述;q表示任务所需的各项资源集合,q={q1,…,qr,…,qM},M表示NMAS中所有Agent的资源种类数,表示任务对第r种资源的需求量;dl表示完成任务的截止时间.
在本文中,我们设计NMAS中的每个Agent都可同时作为任务入口,且假设Agent对于以自身为入口的任务都是诚信的.入口Agent在将每一个原始任务分解后,得到若干子任务,而此些子任务的管理者即为该入口Agent,其使用任务分配模型作为任务管方进行任务分配.本文设定每一个子任务是需在具有相应任务功能需求类型的单个Agent内完成的,而执行任务的Agent即为任务的承包方.此外,我们研究的是针对NMAS综合网络结构组织与关系的任务分配问题,研究角度并非基于任务间依赖和优先级关系的任务分配,因此假设这些子任务之间是并行关系.
定义2.NMAS中的任务分配.在NMAS中,存在<{a};E>,其中,{a}表示Agent节点集合,任意的
1)t需求的资源在a中可全部满足;
2)a具备任务t的fid类型相应功能;
3)a执行t能完成任务的预定目标.
4 任务分配模型
本节将以最小化任务执行时间和通信次数为目标,基于NMAS中的物理网络和交互网络,充分利用Agent的综合关系网资源,研究基于动态综合关系网的任务分配模型DIRNM.模型主要包括基于Agent物理能力和社会关系资源提供力的任务承包方选择策略,基于动态综合关系网的任务分配协商过程设计和基于直接社会关系资源的任务再分配机制.
4.1 任务承包方选择策略
NMAS中的Agent是自治的,具体能力信息对外是不透明的,因此当其投标任务时,需提供自身的实时物理能力信息和社会关系资源提供力信息.物理能力表明投标Agent的实时状态信息,而社会关系资源提供力表明如该Agent执行任务失败后,其可直接求助的社会关系资源.在NMAS中存在不诚信的Agent,对于投标Agent所提供的此些能力信息,招标Agent必须加以衡量.因此,本节设计其可借助于直接信任度信息对投标Agent所提供的物理能力和社会关系资源提供力信息进行评估,并结合Agent间的通信距离,确定最优任务承包方.
1)物理计算能力
当任务管理Agent根据自身功能类型和资源状态决定对任务进行招标分配时,选择三个因素作为投标Agent物理能力的衡量指标.实时的任务环境和需求对于任务的等待时间和处理时间具有很高的要求,因此,将任务等待时间和处理时间合并统称为投标方的预计执行时间,以此作为第一个衡量指标,此指标也有利于Agent间的负载均衡;一个Agent往往对某类任务类型比较擅长,即Agent完成此类任务的成功率较高,因此,将Agent基于fid任务类型的执行成功率作为第二个衡量指标;当一个Agent对于任务需求的资源充余时,在其执行任务发生故障时,可在任务截止时间及系统资源允许的情况下,再次执行任务,免去了对任务的二次分配,因此,Agent拥有任务所需资源的大小将作为第三个衡量指标.在任务分配时,这三个指标数值由投标Agent汇报给招标Agent,代表了投标Agent的实时物理能力.
设ai为任务t的招标方,t的功能需求代码为fid,aj为任务t的投标方,则ai对于aj的物理能力PAj(t)的计算公式为
PAj(t)=α·RETj(t)+β·RSRj(fid)+γ·RRj(t)
(1)
公式(1)中:
0≤PAj(t)≤1;
α、β和γ为权系数,0≤α≤1,0≤β≤1,0≤γ≤1,且α+β+λ=1;
RETj(t)为相对执行时间:
EETj(t)表示aj投标时给出的预计执行时间,A(t)表示投标t的Agent集合,RETj(t)∈[0,1];
RSRj(fid)为aj执行fid功能类型任务的相对成功率:
Rj(t)表示aj拥有的t需求资源的总量,RRj(t)∈[0,1].
2)社会关系资源提供力计算
社会关系资源提供力代表了投标Agent可提供其直接社会关系资源的能力,我们引入其的目的是为了衡量投标方执行任务失败时在任务截止时间允许范围内作为新的任务管理方,在其直接社会关系中再分配任务的能力.关于任务承包方执行任务失败后基于直接社会关系资源的再分配策略及其作用将在4.3中具体介绍,本小节只是研究社会关系资源提供力的计算方法.
在计算投标方的社会关系资源提供力时,将衡量其出度和总入度,出度是投标方基于fid请求直接社会关系资源的能力指标,而总入度是衡量投标方所能直接提供社会资源或作为中介服务社会的能力指标.出度越大表示其可求助的社会关系资源越多,总入度越大表示其对外服务越繁忙.
· 基于fid的出度Oj(fid)
设aj为任务管理方ai所招标任务t的投标方,t的任务需求类型为fid,则aj的出度Oj(fid)为:
Oj(fid)=σ1·OACTj(fid)+σ2·(PNj(fid)-
|PNj(fid)∩OACTj(fid)|)+σ3·(SNj(fid)-
|SNj(fid)∩OACTj(fid)|)
(2)
其中,OACTj(fid)为aj基于fid以任务管理方身份建立的熟人集中熟人的数量;PNj(fid)为aj拥有的具备fid功能的物理邻居数量,|PNj(fid)∩OLNj(fid)|为既是aj基于fid的熟人又是物理邻居的Agent数量;SNj(fid)为aj拥有的具备fid功能的社会邻居数量,|SNj(fid)∩OACTj(fid)|为既是aj基于fid的熟人又是社会邻居的数量;0≤σ1≤1,0≤σ2≤1,0≤σ3≤1,σ1+σ2+σ3=1,且依据任务分配时选择关系Agent的顺序来说,一般σ1>σ2>σ3.
· 总入度TIj
TIj=σ1·IACTj+σ2·PNj+σ3·SNj
(3)
其中,IACTj指aj以资源提供方加入不同Agent不同fid熟人集的数量,PNj为aj拥有的物理邻居数量,SNj为aj拥有的社会邻居数量.
在公式(2)和公式(3)中,我们设计所涉及的参数设置是相同的.因为在计算出度时,用到的3个参数分别表示了投标方aj以资源请求方身份建立的熟人集中熟人的数量、拥有的具备fid功能的物理邻居数量(除去已是基于fid熟人的Agent)以及拥有的具备fid功能的社会邻居数量(除去已是基于fid熟人的Agent)的相对重要程度;在计算Agent入度时,涉及到了投标方aj以资源提供方身份加入不同Agent不同fid熟人集的数量,以资源提供方和中介服务方身份拥有的可求助aj自身的物理邻居数量和社会邻居数量.相同的社会关系角色所起到的影响作用在计算Agent出度和总入度时差别不大,因此我们统一用相同的参数权值来衡量这些项,且一般σ1>σ2>σ3.
· 基于fid的社会关系资源提供力PPSj(fid)
(4)
其中,0≤PPSj(fid)≤1,0≤μ≤1.
由公式(4)可知,μ越大,在衡量投标方aj的社会关系资源提供力时,对其基于fid的出度越重视,即对其可求助的社会关系资源越重视;在同一参数设置下,aj的总入度越小、基于fid的出度越大,表示其服务社会的繁忙程度越低,可求助的基于fid的社会资源越多,社会关系资源提供力越强.
3)基于直接信任度、物理能力和社会关系资源提供力的任务投标方综合能力评估
因物理能力和社会关系资源提供力都是投标方汇报的,所以在具有不诚信Agent的NMAS中,招标方有必要使用信任度进行进一步的能力评估.随着系统规模的扩大,完全分布式的Agent之间的横向通信密集,如再需其它Agent进行信任度推荐将不再适合.因此,在基于动态综合关系网的任务分配模型中,一个Agent在衡量其它Agent的信任度时,设定其将只依靠自己的直接信任度去判断.关于直接信任度的计算,将使用我们在论文[27]中所提出的方法,本文不再赘述.
基于直接信任度、物理能力和社会关系资源提供力的任务投标方综合能力评估计算如公式(5)所示.
Pj(t)=DTij(fid)·[ηPAj(t)+(1-η)PPSj(fid)]
(5)
其中,DTij(fid)表示任务管理方ai对任务投标方aj的直接信任度;PAj(fid)表示ai对于aj的物理能力衡量,0≤PAj(fid)≤1;PPSj(fid)表示ai对aj的基于fid的社会关系资源提供力衡量,0≤PPSj(fid)≤1;η表示ai在评估aj能力时对PAj(fid)的重视程度,η越大,说明其对投标方自身的物理能力越重视,反之,说明其对投标方的社会关系资源提供力越重视,0≤η≤1.
4)最优任务承包方选择
任务执行时或完成后,任务管理方都需与任务承包方进行通信,它们间距离越近,通信时间越少,任务完成时间越短.因此,本节将通信距离纳入任务承包方选择的衡量因素中.此时,可根据ai对aj的能力评估值,结合ai与aj之间的通信距离,计算出ai将任务t分配给aj的合作倾向因子CTFj(t):
(6)
最终,根据下式确定最优任务承包方:
综上,在设计的任务承包方选择策略中,使用了直接信任度指标,而直接信任度计算方法又主要与Agent实际执行任务的时间有关(详见文献[27]),且将Agent执行相应类型任务的成功率考虑其中,因此提高了任务分配成功率,降低了任务执行总时间以及再分配的协商时间和通信开销;每个Agent处于网络中的不同位置,在任务分配时考虑Agent间的通信距离可降低通信时间,进而降低了任务执行总时间.此外,还创新性地提出了基于出度和总入度的社会关系资源提供力的概念.其一可以用于衡量Agent服务社会的繁忙程度,从而找到较为空闲的Agent,降低任务执行总时间;其二可以借助其提出基于直接社会关系资源的任务再分配机制(4.3节),以优化任务分配模型性能.
4.2 基于动态综合关系网的任务分配协商算法设计
Agent在NMAS中像人在人类社会中一样,与生俱来具有自己的社会关系,因此我们提出假设1.
假设1.不存在既无物理邻居又无社会邻居的Agent,也不存在与外界社会无任何联系的子系统.当一个Agent的全部物理邻居和社会邻居退出社会时,其会在其它子系统的Agent中进行选择,形成新的社会邻居关系.
在NMAS中,当底层物理网络拓扑结构发生变化时,Agent之间的通信耗费必定受到影响;Agent之间的交互网络组织关系发生变化时,它们之间的协商和协调也会受到影响.因此在设计任务分配协商过程时,我们将综合考虑底层物理网络和交互网络的作用,使得模型在分配任务和Agent执行任务过程中能获得更好的性能,更加趋近于任务分配优化目标.
基于动态综合关系网的任务分配模型DIRNM并不需要掌握社会的整体网络拓扑和资源分布情况,而是当任务管理方ai将原始任务T分解后,如自身具备任务t(fid)对应的功能需求类型,且系统资源充足,则在本地执行;对于自身不能执行或执行后失败的任务,则基于自身直接社会关系进行分配.
在任务分配模型DIRNM中,我们引入了熟人资质评估策略,针对某类fid认定Agent具备资格成为其熟人集中一员的最小熟人资质评估总值,以及对直接信任度、合作频度和投标积极度各项的最低资质要求,利用任务分配过程中的历史数据,细粒度地进行每个Agent基于fid的熟人集的动态维护.由于篇幅限制,以及此部分内容较简单、易理解,因此,本文将不再进行更为详细的说明.
由上可见,熟人是执行某类型任务综合评定较优的Agent,因此当任务管理方基于自身直接社会关系进行分配时,将以熟人为第一分配选择梯队,以有效降低任务分配协商通信次数,提高任务分配成功率,降低任务执行总时间;物理邻居与任务管理方同在一个子系统中,它们交互密集且通信耗费较低,距离近且通信链路可靠性高、通信时间少,有效减少了任务执行总时间,因此将其作为第二分配选择梯队;最后,将社会邻居作为第三选择梯队.三个梯队的逐层招标,可逐步扩展任务管理Agent的协商范围,有效控制协商分配过程中的通信开销.如仍无法分配成功,则会首先借助于其物理邻居、其次为所在子系统全部Agent的社会邻居作为中介向外扩散招标范围.因此,分配协商过程将依次分为3部分.第一部分为任务入口Agent基于直接社会关系网的任务分配,采用的是先面向熟人、再面向物理邻居、最后物理邻居的三级分配协商,假设Agent的熟人数、物理邻居数和社会邻居数分别为g1、g2、g3,则逐级发送招标书操作的时间复杂度为O(g1+g2+g3);第二部分为求助物理邻居作为中介的任务分配,因为当前中介的物理邻居即为上一轮的中介Agent(入口Agent也可看成是特殊的中介Agent),已被遍历,所以实质上是先面向熟人、后面向社会邻居的二级分配协商,设当前中介Agent的数量为q,则此部分中介Agent逐级发送招标书操作的时间复杂度为O(q(g1+g3));第三部分为借助当前物理邻居所在子系统的所有社会邻居作为中介,任务管理Agent面向中介Agent的熟人、物理邻居和社会邻居的三级任务协商分配,此部分中介Agent逐级发送招标书操作的时间复杂度为O(q(g1+g2+g3)).仍未分配成功,则视当前中介Agent的物理邻居是否曾全部作为中介循环返回到第二部分或第三部分的开始处,继续求助新的中介向外扩散招标.
设循环次数为h,则任务分配协商算法的时间复杂度为:
O((g1+g2+g3)+h1q(g1+g3)+h2q(g1+g2+g3))
=O(hq(g1+g2+g3))
如模型需分配的任务个数为n,则最坏情况下模型的时间复杂度为O(nhq(g1+g2+g3)).
此三部分构成完整的分配协商过程,即使未找到任务承包Agent,但在基于假设1构建的网络中,对Agent节点已实现完全遍历.协商过程中,t的任务管理方对于收到过招标书的Agent将不再重复发送招标信息,Agent也不能重复充当中介,这也是协商算法实现的复杂之处.
关于分配模型对动态综合关系网的适应性,我们设计NMAS中的每一个Agent存储着其基于fid的熟人信息表、基于某一fid以其为熟人的Agent列表、物理邻居信息表和社会邻居信息表,且这些表在动态的NMAS运行过程中是实时更新的.其中熟人信息表是Agent自身根据熟人的表现实时计算更新,以实现对其熟人集的动态维护;熟人、物理邻居和社会邻居的加入或离开是根据其加入后或离开前发布的消息进行更新的;而Agent功能发生变化后,其会及时的汇报给自己的物理邻居、社会邻居以及基于该功能以自身为熟人的Agent.Agent对于熟人、物理邻居和社会邻居基于某类fid的直接信任度信息,是根据它们的历史表现结合当前服务质量实时计算更新的[27],而基于某类fid的的能力信息(如预计执行时间、执行任务成功率、任务所需类型资源拥有量、出度和总入度),是在任务分配时实时获取并结合信任度衡量后得出的.
4.3 基于直接社会关系资源的任务再分配机制
在NMAS中,当任务承包方aj(aj不等于任务管理方ai)执行任务失败后,可设计三种方式进行任务的再分配:1)aj将失败消息传回任务管理方ai,由ai重新对任务进行协商分配;2)aj在任务截止期内作为新的任务管理方寻找可再次执行的Agent,以此类推,直到任务分配执行成功或网络节点完全遍历;3)当aj执行任务失败后,允许其作为临时任务管理方基于所拥有的熟人、物理邻居和社会邻居这些直接社会关系资源再分配一次,如分配失败或分配后执行失败,再返回失败消息给原始任务管理方ai,由ai重新开始对任务进行新一轮分配.本文将采取第三种方式,如再分配成功,可省去原始任务管理方的任务再分配协商,避免其可能向更远Agent招标的通信消耗.因为一般情况下,如任务管理方有更好的关系Agent,也不会交由现失败Agent执行;如再分配失败,随着系统资源状态变化,原先因资源限制没有投标,或发生故障现已恢复的Agent可再次进行投标,保证了任务管理方尽量与距离较近的Agent进行合作,降低了通信消耗,也尽量保证了信息的实时性.
aj在进行任务承包方选择时将不再考虑投标方的社会关系资源提供力,这是由于本文选择的是第三种任务承包方再分配方式,因此,4.2节公式(5)中的η=1.
5 实验验证与分析
拟进行三部分实验,完成以下工作:
第一部分:基于动态综合关系网的任务分配模型的有效性验证.此部分实验将选取三个近年来具有代表性的NMAS任务分配模型与本文所提出的DIRNM进行对比实验.
第二部分:基于直接社会关系资源再分配机制的效果验证.将采用基于直接社会关系资源再分配机制的DIRNM与不采用该机制的模型进行对比,验证模型在进行任务承包方选择时,除物理能力外,引入社会关系资源提供力衡量指标,以便于任务承包方失败后采取基于其直接社会关系资源再分配机制的效果.
第三部分:模型鲁棒性验证.NMAS是开放的、动态的,随时会有Agent节点加入或离开.本文将进行Agent节点动态离开社会网络时的模型鲁棒性测试,以验证模型在网络结构发生变化时的有效性.
实验仿真平台在MyEclipse IDE下使用Java语言自主开发.所开发的仿真NMAS中包含10个子系统30个Agent.30个Agent按每个子系统2到4个的数量随机分散在10个物理局域子系统中,Agent与其它不属同一子系统的Agent形成社会邻居的数量小于等于2;每一个子系统中,至少有一个Agent拥有社会邻居;30个Agent中,诚信度为90%、80%、70%的Agent数量各占三分之一,当Agent投标时,按1减去其诚信度的概率谎报自己的能力,即预计执行时间缩短30%,成功率提高到100%;每个Agent的初始资源不同,相同功能需求类型任务的大小及所需资源相同;Agent具备的功能分属于1到6功能类型中的1到3种,单个Agent执行不同功能类型任务的成功率在50%～95%之间,处理速率随机设定为6～9个任务每秒;任务的资源需求种类包括CPU、内存、磁盘、网络四种系统资源.
当Agent自身客观能力有限,或不诚信地执行任务时,会导致任务执行失败.在仿真平台中,我们以Agent执行不同功能类型任务的成功率代表其客观能力;而当一个Agent的诚信度设置为70%时,意味着其接收的平均100个任务中,有30个任务该Agent不按约定执行以至于超出任务截止时间,最终导致任务执行失败.设置每一个任务经任务管理方分配后(可多次分配)都可在NMAS中完成.
任务分配模型的性能指标分为任务执行总时间、通信次数和任务完成步骤三种:
·任务执行总时间.任务执行总时间指任务集从不同Agent进入NMAS到任务全部执行完毕所经历的时间.执行总时间与任务分配模型的性能成反比.针对系统任务,记录不同的任务分配模型下、每一轮任务完成后与之前各轮任务的累积执行总时间.实验重复进行50次,得出累积平均执行总时间.
·任务完成步骤.任务完成步骤其实衡量的是任务分配模型在不同Agent节点间分配任务的可靠性.它的基数为任务个数,每一个任务进入本地Agent后即为一步,当本地Agent通过招投标交由其他Agent执行一次,或其它Agent执行失败,再次回到本地被本地Agent执行时,任务完成步骤累加一次.针对系统任务,观察不同的任务分配模型下、每一轮任务完成后与之前各轮任务的累积完成步骤.实验重复进行50次,得出累积平均完成步骤.
·通信次数.通信次数指的是从任务分配到任务完成整个过程中,不同Agent之间通信次数的总和.
在对比实验之前,我们将根据模型中对参数取值的约束,设计不同的参数值输入数据,经多次实验,确定参数最优取值.下面以确定公式(1)中参数α、β和γ的最优值为例进行具体说明.
当{α,β,γ}为需取值的参数集,模型中的其它参数取固定假设值,因此α、β和γ的取值过程其实是有约束性质的交叉检验[28,29].先α将取固定值,将β和γ的取值进行变化,β、γ不同取值都覆盖后,再将α取另一固定值,β、γ的值再进行变化,…,以此类推,直到α的取值也都覆盖.α、β和γ的取值间距为0.1.针对{α,β,γ}的每一组参数取值组合,将不同功能需求类型的任务投放到位于不同子系统的Agent中,经50次重复实验,得出平均任务执行总时间 (Total Execution time,TET)和平均通信次数(Communication Number,CN),并按照公式(7)计算该参数取值下的优越值SV.
(7)
其中,ζ∈[0,1].ζ的取值与用户需求有关,ζ越大,对任务执行时间越重视,反之,对通信次数越重视.
在接下来的实验中,关于所使用模型中的参数取值,我们将兼顾缩短任务执行时间和减少通信次数的分配目标,设置任务执行时间权重为0.7,通信次数权重为0.3,采用上述参数取值方法,预先设计不同的参数值组合,经多次实验后,最终通过公式(7)选出一组优越值最高的参数值进行相关实验.
5.1 模型有效性验证
此部分实验将本文所提出的DIRNM与近几年提出的Locality-sensitive model[21]、Community-aware Model[22]和HRETA[23]此三种NMAS任务分配模型进行任务完成总时间、通信次数和任务执行步骤三个衡量指标方面的性能比较,以验证本文所提出模型的有效性.用来对比的三种模型的特征分析可回见表1.
每个Agent节点都是任务入口,可同时进入需要系统执行的任务.随机产生任务3000个,任务类型fid∈{0,1,…,6},分10轮投放到位于10个子系统的30个Agent中,每轮投放300个,每个Agent10个.设置每一个任务经任务管理Agent分配后(可多次分配)都可在NMAS中完成.进行50次重复实验,计算得出每一轮任务完成后累计的平均任务执行总时间、通信次数、任务完成步骤,结果如图2所示.
由图2可见,基于动态综合关系网的任务分配模型的任务执行总时间、通信次数、任务完成步骤均最少,模型性能最优.这是由于其基于熟人——物理邻居——社会邻居网络结构化特点的三级分配过程,基于具体任务功能需求类型fid的Agent直接信任度、Agent物理能力(包含预计执行时间、成功率和资源三项衡量指标)、社会关系资源提供力和通信距离的Agent节点选择机制,以及基于直接社会资源的任务失败Agent再分配策略共同作用的结果;其它三种对比模型在选择执行任务的Agent时都考虑了物理资源量和通信距离,Locality-sensitive model还考虑了Agent的社会资源和负载均衡,HRETA考虑了Agent的可靠性和负载均衡,因此如图2(a)所示,此两模型任务完成总时间较Community-aware model少;但Community-aware model在招标时先面向距离近的Agent招标,由近及远向外扩散招标范围,即对应网络结构化特点首先面向物理邻居招标,其次为社会邻居,因此如图2(b)所示,其通信次数较Locality-sensitive model和HRETA少;Locality-sensitive model考虑了社会资源,在Agent执行任务失败时可扩展协商范围,增加接触能力较优Agent的机会,HRETA考虑了可靠性,所以如图2(c)所示,此两种模型任务完成步骤较Community-aware model少.
图2 四种任务分配模型性能对比Fig.2 Performance comparison of four kinds of models
5.2 基于直接社会关系资源再分配机制的效果验证
本部分实验将分别使用Agent节点选择时考虑社会关系资源提供力指标、采取基于直接社会关系资源再分配机制的模型,与不考虑社会关系资源提供力指标、不采取基于直接社会关系资源再分配机制的模型分配任务.随机产生3000个fid∈{0,1,…,6}的任务,分10轮投放,每轮300个,每Agent10个.实验重复进行50次,计算得出累积平均执行总时间、通信次数和完成步骤,如图3所示.
图3 采用与不采用基于直接社会关系资源再分配机制的性能对比Fig.3 Model performance comparison of using and not using the redistribution mechanism based on direct social relation resources
由图3(a)和(b)可以看出,采用基于社会资源再分配机制的模型,从第一轮任务开始,较没采用该机制的分配模型执行总时间低,通信次数少,性能表现优,验证了3.3节设计失败Agent基于直接社会关系资源再分配策略时提到的“如再分配成功,可省去原始任务管理方的任务再分配协商,避免其可能向更远Agent招标的通信消耗,因为如任务管理方有更好的Agent,也不会交由现失败Agent执行;如再分配失败,随着系统资源状态变化,原先因资源限制没有投标,或发生故障现已恢复的Agent可再次进行投标,保证了入口Agent尽量与距离较近的Agent进行合作,降低了通信消耗”的初衷.由图3(c)可以看出,该策略对提高任务分配成功率也有促进作用,这是由于任务失败Agent基于直接社会关系资源的再分配增加了其熟人等能力较优Agent执行任务的机会.
5.3 模型鲁棒性
由于NMAS的开放性,Agent节点会动态加入或离开社会网络.本部分实验将在一些Agent节点离开社会导致网络结构动态变化的情形下,验证基于动态综合关系网任务分配模型的鲁棒性.实验共分配20轮任务,第1-10轮任务分配时实验设置仍为10个子系统30个Agent,第11轮将选取两个诚信度高且能力相对优秀的Agent离开社会网络.
随机产生300个任务,在第1到10轮,此300个任务将被重复分配,每轮每个Agent固定分配10个任务.随机产生280个任务,在第11轮到20轮,此280个任务将被重复分配,每轮每个Agent固定分配10个任务.实验重复进行50次,得出每轮单任务的平均执行时间和平均通信次数消耗,实验结果如图4所示.
图4 网络结构动态变化时的实验结果Fig.4 Experimental results under the circumstance of the network structure changing dynamicly
由图4可以看出,在第1-10轮任务,随着轮次的增加,每轮单任务的平均执行时间和通信次数开销逐渐下降,最后趋于平稳,这说明每个Agent随着任务分配经验的积累,形成了较为固定的熟人社会关系以及较为准确的Agent直接信任度判断,同时也验证了模型中相关机制和策略的有效性.在第11轮,随着两个诚信度高且能力较优Agent的离开,单任务平均执行时间和通信次数开销有一个大幅度的升高,这是由于随着两个优秀Agent的离开,原先将之作为熟人的Agent只能通过诚信度和能力相对离开Agent低的熟人或物理邻居、社会邻居进行任务分配,任务执行时间增加,任务分配成功率下降引起再分配通信次数上升;而与之互为物理邻居或社会邻居的Agent在利用自身综合关系网进行任务扩散招标时,随着此两Agent的退出,招标范围将受到影响,协商效率下降.随后,随着任务轮次的增加,执行总时间和完成步骤总体为下降趋势,并慢慢趋于平稳,这说明每个Agent又重新形成了较为稳定的综合关系网络.但平稳后的平均执行总时间和通信次数仍较Agent退出社会前高,这是由于此两Agent为社会中诚信度高且能力相对优秀的Agent,且随着Agent的退出,其熟人、物理邻居和社会的任务分配协商效率受到影响.总的来说,从图4曲线走势来看,模型具有鲁棒性,且恢复性能较快.
6 总 结
近几年来,随着NMAS概念的提出,NMAS的任务分配开始被研究.本文通过深入考虑网络结构化(包括物理网络和交互网络)的作用,研究了完全分布式的、基于动态综合关系网的任务分配模型,解决了大规模分布式NMAS任务分配中横向通信密集且社会关系资源不能充分利用的问题,且适用于动态的网络结构.模型中基于直接信任度、物理能力和社会关系资源提供力的任务承包方选择策略有效评估了Agent的实时能力及其执行任务失败时可求助的社会关系资源;基于熟人、物理邻居和社会邻居形成的动态综合关系网的任务分配协商过程,降低了分配协商通信开销.此外,构建了基于Agent直接社会关系资源的任务再分配机制,充分利用了Agent节点的社会关系资源,有效规划了任务再分配协商范围,优化了模型的任务分配性能.但本文对于模型中的权重参数,实验时是通过设置多个参数组合,利用交叉检验方法经过多次实验,根据降低任务执行时间和通信次数的任务分配目标取最优设置值.但此种参数取值方法较为传统,工作量也较大.此外,当Agent诚信和能力动态变化时参数值设置也不能及时调整.因此,下一步工作我们将专门研究参数取值及其在实时分配过程中的自适应调节问题,以进一步保证动态网络环境中的模型性能.
：
[1] Coulouris G,Dollimore G,Kindberg J,et al.Distributed systems:concepts and design (5th edition)[M].Burlington:Morgan Kaufmann Publishing,2012.
[2] Wilensky U,Rand W.An introduction to agent-based modeling:modeling natural,social,and engineered complex systems with netlogo[M].Cambridge:MIT Press,2015.
[3] Liu Da-you,Yang Kun,Chen Jian-zhong.Research status and development trend of agent[J].Journal of Software,2000,11(3):315-321.
[4] Wooldridge M.An introduction to multiagent systems[M].Wiley Publishing,2009.
[5] Rousset A,Herrmann B,Lang C,et al.A survey on parallel and distributed multi-agent systems[C].Euro-Par 2014:Parallel Processing Workshops,August 25-26,Porto,Portugal,2014:371-382.
[6] Cao L,Zhang C,Zhou M C.Engineering open complex agent systems:a case study[J].IEEE Transactions on Systems Man & Cybernetics Part C Applications & Reviews,2008,38(4):483-496.
[7] Jiang Yi-chuan.Task allocation in networked multiagent systems[J].Pattern Recognition and Artificial Intelligence,2012,25(2):262-272.
[8] Jiang Y C,Jiang J C.A multi-agent coordination model for the variation of underlying network topology[J].Expert Systems with Applications,2005,29(2):372-382.
[9] Lv Jian,Tao Xian-ping,Ma Xiao-xing,et al.Research on interware model based on agents[J].Science China:Series E,2005,35(12):1233-1253.
[10] Jiang Y,Hu J,Lin D.Decision making of networked multiagent systems for interaction structures[J].IEEE Trans on Systems,Man and Cybernetics,2011,99(3):1-15.
[11] Abdallah S,Lesser V.Multiagent reinforcement learning and self-organization in a network of agents[C].Proc of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems,Honolulu,USA,2007:172-179.
[12] Jiang Y,Huang Z.The rich get richer:preferential attachment in the task allocation of cooperative networked multiagent systems with resource caching[J].IEEE Transactions on Systems Man & Cybernetics Part A Systems & Humans,2012,42(5):1040-1052.
[13] Tao Hai-jun,Wang Ya-dong,Guo Mao-zu,et al.A multi-agent negotiation model based on acquaintance coalition and extended contract net protocol[J].Journal of Computer Research and Development,2006,43(7):1155-1160.
[14] Chen Gang,Lu Ru-qian.Relation web model an organizational approach to agent cooperation based on social mechanism[J].Journal of Computer Research and Development,2003,40(1):107-114.
[15] Guo Gai-gai.Research and implementation of multi-agent aggregation model[D].Xi′an:Xidian University,2014.
[16] Val E D,Rebollo M,Vasirani M,et al.Utility-based mechanism for structural self-organization in service-oriented MAS[J].Acm Transactions on Autonomous & Adaptive Systems,2014,9(3):1-24.
[17] Gao Fei-yan.Research on the multi-agent task allocation mechanism based on extended contract net[D].Dalian:Dalian Maritime University,2009.
[18] Kinnebrew J S,Biswas G.Efficient allocation of hierarchically -decomposable tasks in a sensor web contract net[C].IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology,15-18 Sept,Milan,Italy,2009,2:225-232.
[19] Xu H,Mandal S,Pattipati K R,et al.An optimization-based distributed planning algorithm:a blackboard-based collaborative framework[J].IEEE Transactions on Systems,Man & Cybernetics Systems,2014,44(6):673-686.
[20] Qiu Hang-ping,Qin Yao,Hu Rui.Study on the task allocation based on improved contract net in multi-agent system[J].Computer Science,2012(B06):279-282.
[21] Jiang Y,Li Z.Locality-sensitive task allocation and load balancing in networked multiagent systems:talent versus centrality[J].Journal of Parallel and Distributed Computing,2011,71(6):822-836.
[22] Wang W,Jiang Y.Community-aware task allocation for social networked multiagent systems[J].IEEE Transactions on Cybernetics,2013,44(9):1529-1543.
[23] Rahimzadeh F,Khanli L M,Mahan F.High reliable and efficient task allocation in networked multi-agent systems[J].Autonomous Agents and Multi-Agent Systems,2015,29(6):1023-1040.
[24] Jiang Y,Zhou Y,Wang W.Task allocation for undependable multiagent systems in social networks[J].IEEE Transactions on Parallel & Distributed Systems,2013,24(8):1671-1681.
[25] Weerdt M M D,Zhang Y,Klos T.Multiagent task allocation in social networks[J].Autonomous Agents and Multi-Agent Systems,2012,25(1):46-86.
[26] Jiang Y,Jiang J.Contextual resource negotiation-based task allocation and load balancing in complex software systems[J].IEEE Transactions on Parallel & Distributed Systems,2009,20(5):641-653.
[27] Wu Dan-feng,Yu Si-miao,Zhang Sheng-yu,et al.Rask allocation based trust degree for social network of syncretic system[J].Journal of Software,2017,28(7):1898-1925.
[28] Zhao Y,Wang K.Fast cross validation for regularized extreme learning machine[J].Systems Engineering & Electronics Journal of,2014,25(5):895-900.
[29] Astorino A,Fuduli A.The proximal trajectory algorithm in svm cross validation[J].IEEE Transactions on Neural Networks & Learning Systems,2016,27(5):966-976.
附中文参考文献：
[3] 刘大有,杨 鲲,陈建中.Agent研究现状与发展趋势[J].软件学报,2000,11(3):315-321.
[7] 蒋嶷川.网络结构化多Agent系统的任务分配[J].模式识别与人工智能,2012,25(2):262-272.
[9] 吕 建,陶先平,马晓星,等.基于 Agent 的网构软件模型研究[J].中国科学:技术科学,2005,35(12):1233-1253.
[13] 陶海军,王亚东,郭茂祖,等.基于熟人联盟及扩充合同网协议的多智能体协商模型[J].计算机研究与发展,2006,43(7):1155-1160.
[14] 陈 刚,陆汝钤.关系网模型—基于社会合作机制的多Agent协作组织方法[J].计算机研究与发展,2003,40(1):107-114.
[15] 郭改改.多Agent聚合模型的研究与实现[D].西安:西安电子科技大学,2014.
[17] 高飞燕.基于扩展合同网的多Agent任务分配机制的研究[D].大连:大连海事大学,2009.
[20] 裘杭萍,覃 垚,胡 汭,等.多Agent系统中基于改进合同网模型的任务分配研究[J].计算机科学,2012(B06):279-282.
[27] 武丹凤,于思淼,张绳昱,等.基于信任度的合一系统社会任务分配[J].软件学报,2017,28(7):1898-1925.
