基于动态合同网的Agent任务分配算法

摘要：随着应急指挥网络系统规模不断增加，网络故障诊断逐渐成为应急指挥网络系统的关键。针对域间协同故障诊断中的任务分配问题，提出了基于改进合同网的Agent动态任务分配算法，建立了Agent性能库，使管理者根据所注册Agent的性能进行发标，同时，为每个执行Agent完成某项任务建立相应的信息素，实验结果表明，该算法有效地避免了网络的拥塞，提高了任务分解的效率。

关键词：协同网络故障诊断；任务分配；合同网算法；蚁群算法

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2014）05-0919-03

1 概述

随着应急指挥网络系统复杂程度不断提高，系统规模将越来越大。这就造成应急指挥系统中网络的规模越来越大，功能越来越复杂，加之网络攻击技术与计算机病毒，使得网络故障的发生是不可避免的，而且发生的概率会越来越大，网络故障诊断逐渐成为应急指挥系统的关键。目前采用的故障诊断技术及方法无法满足应急指挥系统故障测试与诊断的要求。这时就需要协同故障诊断技术为网络系统提供更完备的综合保障支持。协同故障诊断技术包括任务分解，任务分配和决策融合等环节[1]。该文重点研究了其中的任务分配，提出了基于改进合同网的Agent动态任务分配算法，有效地避免了网络的拥塞，提高了协同故障诊断效率。

2 动态合同网算法

本文将管理Agent替代合同网算法的管理者，将执行Agent替代合同网算法的承包商完成合同网算法在Multi-Agent协同故障诊断中的应用，如图1所示。

图1 合同网在MAS中的应用

传统合同网在MAS中的直接应用缺点较多，该文根据传统合同网算法的缺点提出了一下几点改进：

1） 减小管理Agent发标量。建立Agent性能库，使管理者根据所注册Agent的性能进行发标，避免了管理Agent广播标书带来的通信拥塞。

2） 与蚁群算法相结合。为每个执行Agent完成某项任务建立相应的信息素，这样就可以形成正反馈，管理Agent就可以根据前期经验进行任务分配。

3） 任务结果评估。传统合同网算法没有任务结果评估，该文将任务结果评估纳入到合同网算法中来，实现了系统的反馈。

2.1注册Agent性能库

管理者对每个注册Agent的能力都有一个数据库，例如Agent i执行任务j的能力为[Cap（i，j）]。有能力执行任务的Agent将其初始能力值设为1，没有能力执行任务的Agent将其初始能力值设为0，这样就以数据库中的表的形式建立了Agent性能库。

设置性能库的本质是为了让管理者能够将任务分配给能够胜任的承包商执行，以减少资源耗费。所以有了注册承包商性能库，就可以根据性能库分发任务，这样就避免了传统合同网算法使用广播带来的通信量大的问题，有效避免的通信拥塞。

在合同网算法里，没有绝对的管理者，也没有绝对的承包商，它们之间是相互转化的，所以每一个有注册承包商的管理者都有性能库，而且性能库分为两部分：一部分为管理部分；另一部分为执行部分（执行部分只有自己的性能），如图2所示。

2.2 Agent信息素

传统合同网算法在竞标阶段执行Agent只要发现自己符合任务要求就会向管理Agent发送竞标标书，而且管理Agent会对每一个标书进行评估，这样就会导致管理Agent的負载过大，影响整个系统的效率。该文从减小执行Agent投送竞标标书的数量的角度出发，提高了执行Agent的自主性和竞争性，引入蚁群算法的蚂蚁信息素，对可执行任务的Agent进行进一步的寻优。

当管理Agent有一个任务i要进行分配时，将会有若干个执行代理可以执行，所以就引出了最优问题。为了让任务分配趋于最佳合理状态，引入了蚂蚁的信息素，并将蚁群算法中的转移概率公式改进为所需的代理i执行任务j的效果概率公式，如下式。

[P ij（t）= [τij（t）]α×[Tij（t）]βZ? capable[τzj（t）]α×[Tzj（t）]β T（i，j） ≠N 0 Otherwise] （1）

其中[P ij（t）]表示t时刻，代理i执行完任务j后，在所有执行代理中的执行效果优劣概率；[τ（i，j）]为t时刻代理i执行任务j的信息素值；capable为能够执行任务j的代理的集合；[T（i，j）]为t时刻代理i执行任务j的执行时间的倒数，即：

[T（i，j）=1Tc+Td] （2）

其中[Tc]为任务的完成时间；[Td]为代理i到代理j的延迟时间，单位毫秒（ms）。

依据以上公式（1）算出每一个执行Agent执行任务j的完成优劣的概率，概率越大，该Agent完成任务j的效果就越好。所以本文根据[P ij（t）]的大小选择概率大的执行任务j，这样既保证了任务的完成质量和效率，又减小了系统的通信量和负载。

针对算法中信息素和参数是动态的这一特点，为了保证全局寻优，该文利用轮转赌法选择出来的Agent执行任务。轮转赌法是模仿轮盘转动进行选择[5]，如图3所示，将各Agent执行任务完成的优劣概率在赌轮上划分成扇形区域，然后转动轮盘，使其随机转动。当轮盘停止转动时，指针所指向的扇区就是所要选择执行任务的Agent。所以完成优劣概率大，被选中的几率就大。被选中的概率与完成优劣概率成正比。

图3 轮转赌法

利用上述的轮转赌法可以选择完成能力优秀的Agent来执行任务j，显著提高了任务完成的效率。如果通过轮转赌法选择的Agent没有完成任务，那么会继续通过轮转赌法选择Agent执行任务，直到任务完成为止。

当任务完成后，会执行对执行任务的Agent信息素进行更新，更新的公式为：

[τij（t+Δ t） = 1-ρ τij（t） + τij（Δ t）] （3）

[τij（Δ t）=Q（Tc+Td）] （4）

其中[τij（t+Δ t）]为[（t+Δ t）]时刻Agent i完成任务j的信息素值；[τij（Δ t）]表示完成任务的Agent信息素增量，初始时刻[τij（Δ t）=0]；[ρ（0≤ρ<1）]为信息素挥发系数，[（1-ρ）]表示信息素的残留因子；Q为常量，表示蚂蚁所释放的信息素量为Q。

根据上述公式可以将信息素更新，这样就可以将完成能力优秀的Agent找出，并且也可以根据信息素的大小来判定执行Agent执行某一任务的效率。

2.3 算法描述

1） 算法的初始化阶段，将所有数据进行初始化，包括[τ0]，ρ，Q，[Td]。

2） 定期测试网络延迟，以此来更新延迟时间[Tc]；更新注册Agent性能库的性能参数[Cap（i，j）]，管理Agent下的注册Agent会定期上报更新其性能参数[Cap（i，j）]。

3） 管理代理根据注册Agent性能库来确定能执行任务的执行Agent。

4） 利用公式（1）计算已选Agent的完成概率，然后进行排序。

5） 利用轮转赌法在可选执行Agent中选择要执行任务的Agent，并在可选执行Agent表中去除，然后向执行Agent下发标书。如果执行Agent投标则跳到6），否则重复本步骤。

6） 管理Agent接受到投标的执行Agent分发任务，然后等待执行结果。

7） 执行Agent执行完任务后，上报管理Agent，并更新完成时间[Td]，并更新信息素[τij（t） ]。

2.4 算法的效率

假设一个Multi-Agent系统由管理Agent和n个执行Agent组成。传统的合同网采用广播式发送标书，则Agent之间进行一次通信所需要的时间设为[Tm]，管理者Agent的评估时间设为[Tp]，Agent完成任务的时间设为[Tc]。则传统合同网总的时间耗费为[T1=3Tm+nTc+Tp]。而改进后的评估时间[Tj]，因为能力库的建立只对由能力完成任务的Agent进行评估，所以将会大大减少评估的时间，虽然需要计算完成优劣的概率，但是相较于评估标书减少，对评估时间的影响极小。设改进后算法参加评估的Agent的数量为[αn （0<α<1）]，则[αn Tj

3 仿真分析

本文根据协同故障诊断的需求搭建了如下的仿真环境。该仿真环境共有10台计算机。其中由1台管理Agent计算机，1台交换机，10台执行Agent计算机。其中5台安装Linux，5台安装Windows XP。参数的设置为：a=1，b=5，r=0.1，Q=1000，tij（0）=1，[Td=500]。

将仿真平台的所有电脑安装上带有专家系统的Agent，并建立为每个Agent建立能力数据库和信息素数据库。给予管理Agent 一个由20个任务（例如：链路诊断，网卡故障诊断，交换机端口诊断等）组成的复杂任务，在这20个任务中有执行Agent可以执行有的不可以，每台电脑的执行时间也不同。最后按照传统合同网算法和动态合同网算法进行任务分配，对20个任务进行30次分配，仿真结果如图4所示。

图4 仿真结果

从图中可以看出，改进后的合同网算法完成任务的总时间明显小于传统合同网算法，提高了任务分解的效率；改进后合同网算法的完成总时间波动性较小，增加了任务分解的稳定性。反观传统合同网算法完成任务总时间较大，且有较大的波动性，算法的效率较低。

4 总结

针对域间协同故障诊断中传统MAS任务分配算法的不足和传统合同网算法的缺点，提出了动态合同网算法，提高了算法的效率，仿真结果表明，该算法有效地避免了网络的拥塞，提高了协同故障诊断效率。但是，协同故障诊断中任务的决策融合研究的较少，将是下一步研究的重点。

参考文献：

[1] 王爽.远程协同故障诊断任务执行路径规划[J]. 计算机测量与控制，2011，19（8）：1814-1816.

[2] 杨件，李文立，洪春宇.基于阈值和可用度的合同网协议改进方案研究.计算机集成制造系统， 2009，15（5）：1016-1022.

[3] 龙涛，沈林成，朱华勇，等.面向协同任务的多UCAV分布式任务分配与协调技术.自动化学报，2007，33（7）：731-737.

[4] Guo Shao-sheng， Meng You-xin. An improved entropy-based ant colony optimization algorithm， 2010 International Conference on Computer Application and System Modeling， Proceedings，2010， 15：1548-1550.

[5] 刘刚，何麟书.双赌轮选择遗传算法. 北京航空航天大学学报，2005，31（8）：930-933.