分布式计算的自适应多智能体组织

© 2013 Dr.Anatoly Kalyaev博士雅科夫·科罗温出版社：Elsevier B.V.由美国应用科学研究所负责选择和/或同行评审可在www.sciencedirect.com在线获取ScienceDirectAASRI Procedia 6（2014）49 - 582013第二届AASRI计算智能与生物信息学分布式计算的自适应多智能体组织Dr. Anatoly Kalyaeva *，Dr. Iakov Korovinaa南方联邦大学多处理器计算系统科学研究所，Chekov街，2，347900，塔甘罗格，俄罗斯联邦摘要本文提出了一种新的分布式计算组织方法。所提出的方法的主要好处是可能使用许多不同的私人计算机的资源来解决连贯的任务。该方法允许在计算节点参数发生变化时对计算过程进行修正。计算系统实现这种能力是因为它由平等的主动代理组成，这些代理相互作用以创建社区来解决传入的任务。在创建社区时，agents对社区进行优化组合，以及时解决用户任务，并最大限度地减少所需的计算资源。© 2014作者。出版社：Elsevier B. V.这是CC BY-NC-ND许可下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/3.0/）。美国应用科学研究所关键词：分布式计算系统;集体决策;去中心化;社区;适应性;多智能体系统1. 介绍使用企业和个人计算资源来解决计算任务的想法出现在30多年前，但仅仅在大约10年前，由于全球和本地联网的进步，不同的组织开始使用这样的系统。这种类型的系统被称为分布式计算系统* 通讯作者。电话：+ 7-952-5666699。电子邮件地址：anatoly@kalyaev.net。2212-6716 © 2014作者出版社：Elsevier B.诉 这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/3.0/）。美国应用科学研究所科学委员会负责的同行评审doi：10.1016/j.aasri.2014.05.00850Anatoly Kalyaev和Iakov Korovin/AASRI Procedia 6（2014）49（DCS）。第一个广泛传播的分布式计算系统是由Ian Foster和Carl Kesselman提出的GRID。今天，由于网络和个人计算机的进步，这种系统的相关性越来越大。在分析一些广泛传播的DCS [3] [4] [5] [6] [7]时，我们注意到它们中的大多数只能用于基于一组类似计算节点（CN）的专用网络。这种DCS网络中的计算通常由计算节点控制，该计算节点控制计算节点网络中传入任务的分布[8]。对DCS系统的深入分析表明，专用服务器执行此类系统中的几乎所有控制功能。DCS的这种类型的组织允许在CN之间提供负载平衡。然而，现代的本地和全球网络互连了许多私人和企业计算机，并且这些计算机的很大一部分没有完全加载。在执行分析时，作者决定，使用这些空闲资源创建DCS的任务非常重要。在分布式控制系统中使用这些CN的主要问题是，如果CN的所有者执行某些操作（例如运行某些应用程序或开始下载某些文件），则CN的参数（例如计算能力、网络带宽等）随时可能发生变化。另一个问题是不同所有者的氯化萘种类繁多。在一个DCS中可能共存许多不同的CN，这使得解决任务的有效分配变得更加困难。SETI@home项目（setiathome.berkeley.edu）就是这种尝试的一个例子。该项目使用志愿者的CNs对射电望远镜的信号进行过滤，以寻找外星智慧生物。然而，分析表明，SETI@home允许使用私人计算资源，因为它的创建只是为了解决容易分解的任务，这些任务可以分为不连贯的部分。因此，非相干任务简化了负载平衡的实现，并且解决任务的时间并不关键，这意味着各个CN的特性可以动态变化。这使得像SETI@home这样的系统在使用上非常有限。这就是为什么迫切需要开发新的方法和算法，以允许在DCS中使用个人CN。基于私有CN协作的通用DCS的创建要困难得多，因为它应该允许解决由连贯子任务组成的连贯任务。这个问题的出现是因为DCS中的CN集合是混合的：一些CN具有更宽的信道，一些CN具有更高的计算性能。 此外，氯化萘的参数随其所有者的行为而动态变化。今天，在解决连贯任务的同时有效加载DCS是一个挑战。[9]当CN的参数动态变化时，解决这样的任务的任务要困难得多。然而，在DCS中执行自适应计算的新方法的开发，可以让系统根据CN参数的变化调整计算，可以解决这个问题[10]。2. 分散式DCS的组织和功能原理在建议的DCS组织方法中，我们试图避免专用服务器，并使DCS成为分散的组织[11]。这种新方法是基于多智能体系统和集体决策原则。DCS的每个核心网都安装了主动代理软件，这些代理之间的交互实现了传入任务的调度。每次DCS都可以由不同的代理组成，这就是为什么用户和系统之间会出现交互问题，因为用户不知道将任务发送到哪里。为了解决这个问题，我们使用被动的服务节点，作为“公告板”（BB）[12]，建议分散式DCS的结构图如图1所示。Anatoly Kalyaev和Iakov Korovin/AASRI Procedia 6（2014）4951Fig. 1.建议DCS正如你所看到的，主动代理在这样的DCS中执行几乎所有的服务任务[13]。我们建议在实际执行CN（图1中的ECN）的基础上实现每个代理。Agent在DCS中调度用户任务的求解过程。为了解决连贯的任务，他们需要创建独特的社区来解决所有这些任务[5]。社区的目标是在用户指定的时间内解决传入的用户任务。如果该群落中氯化萘的参数发生变化，则该群落中氯化萘的组合也会发生变化。系统可能会遇到CN的故障，CN计算能力的变化，带宽的减少，以及所有这些都可能导致任务求解时间的增加。在所有这些情况下，代理社区必须改变其组成，以便及时解决用户指定的任务。一般来说，在分散式DCS系统中解决入站任务的方法可以描述如下。系统的用户形成他想要解决的任务，设置解决任务的时间要求，并确定解决任务的虚拟支付，该虚拟支付由一些虚拟点表示（如果我们使用私人计算机，则可以是金钱，如果我们使用公司CN，则只是任务的优先级）。之后，用户将所有数据发送到BB。DCS的主动代理正在监视BB并寻找新任务。如果某个Agent发现新的任务，则利用任务的计算复杂度和虚拟点数来评估执行每个任务的收益。当智能体找到最“有益”的任务时，它加入社区来解决它：它需要解决任务所需的部分计算。每当有新的Agent加入社区时，它就对任务求解时间进行评估，在某个时刻，社区变得足够强大，可以及时解决任务，社区停止扩张。当新的Agent加入社区时，它开始求解某个子任务，在求解子任务的过程中，Agent会监控自己的CN参数。如果参数的变化导致超过用户指定的任务解决时间，社区开始接受新的代理。当社区解决任务时，产生结果的代理将其发送给用户，然后使社区自行解散[14]。为了更容易理解所提出的方法，我们决定将其分为3个阶段： 任务的形式表示 在社区中合作; 在创建的社区中分配任务。52Anatoly Kalyaev和Iakov Korovin/AASRI Procedia 6（2014）49让我们更详细地描述阶段。3. 任务的形式化表示首先，我们需要以并行形式呈现任务，让代理社区执行解决方案。在我们的工作中，我们决定在系统中的信息图（IG）的形式表示任务。任务的IG是一个图，其中顶点表示用户任务的子任务，弧表示子任务之间的数据传输。为了形成任务的IG，用户必须以一种允许将其逻辑地分解为相互连接的部分的形式创建任务。在任务的IG G（Q，X）中，每个顶点qi Q表示第i个子任务。对于每个子任务，用户指定估计的计算复杂度Yi。每个弧x（qi，qj）X指定从子任务qi到子任务qj的传输中的数据量Wij [15]。为了方便起见，我们决定以多层并行形式（MPF）呈现IG，以简化任务图的进一步并行化。要做到这一点，图的所有顶点应根据以下规则划分为子集Vi如果弧x（qm，qn）将层j连接到层k，这意味着j k。图2显示了任务IG的MPF，它包含9个顶点。图二.任务IG的MPF当任务IG在MPF中表示时，我们可以很容易地评估任务的并行计算的数量和社区中用于解决该任务的最大代理数量作为MPF IG层中的最大顶点数量。在下一个步骤中，用户必须指定最大时间来解决他的任务和优先级（虚拟点的数量）。在所有用户将任务发送到DCS的一个BB之后。4. 社区中的协作当用户任务被发送到DCS的公告板时，DCS的节点开始在社区中协作，这将允许在用户指定的时间内解决任务。[16个]Anatoly Kalyaev和Iakov Korovin/AASRI Procedia 6（2014）4953D溶胶在创建代理社区时，分散的DCS使用以下算法：1. 公告板将传入的任务标记为未完成任务;2. 代理Aj在DCS的公告板上查找未完成的任务对于每个找到的任务，座席将收到：(a) 找到的任务的IG G;(b) 任务的优先级P(c) 子任务qi（i = 1，K）状态（“就绪”/“工作”/“新”）;(d) 解决任务的最大时间Tmax;(e) 由任务M提供的代理的最大数量;3. 代理Aj评估解决所有发现的未完成任务的收益：(a) 代理Aj从最有利可图的开始对任务的盈利能力值（P/Y）进行排名(b) 代理Aj从列表中查找下一个任务。如果列表为空，则转到步骤4;(c) 代理Aj接收社区中代理的参数和代理的数量N;(d) 如果N = M，则代理转到步骤3b;(e) 代理计算社区是否有足够的CN在用户指定的时间内解决任务，使用以下公式L我是Ts1Smm1（一）其中Yi是未解决的子任务之一的复杂度，L是未解决的子任务的数量，Sj是CN j的计算能力，D是社区中呈现的CN的数量。如果Tmax Ts，则代理从未完成任务的列表中移除该任务，并前进到步骤3b;(f) 代理Aj加入社区;(g) 如果代理的性能（通过公式（1）找到）足以在指定的时间内完成用户的任务，则代理在公告板上将任务标记为完成;4. 如果代理Aj已经成功加入社区，则进行到步骤5，否则代理进入待机模式持续时间间隔T等待并进行到步骤2;5. 如果任务标记为完成，则表示社区已成功创建，座席开始解决用户任务。上述步骤让DCS的代理形成一个社区，以解决传入的连贯任务的时间。社区中的代理集取决于它们的实际性能。这种能力使社区能够适应计算过程的动态变化的CN的参数。在完成这些步骤之后，Agent需要在社区中有效地分配子任务，使任务在用户指定的时间内得到解决。5.已创建社区中的任务分配一旦DCS的代理成功创建社区，他们必须在社区节点之间执行子任务的分配[15，16]：1. 如果社区中有自由代理（没有子任务要解决），则该代理向社区中的所有代理发送关于启动自由子任务分配过程的消息。2. 要参与这个过程，每个社区代理遵循以下步骤：(a) 代理Aj寻找新的子任务qR;(b) 对于找到的子任务qR，代理Aj计算其求解时间TRj在CNj上;3. 代理Aj发送结果值RJ溶胶社区的所有代理人不54Anatoly Kalyaev和Iakov Korovin/AASRI Procedia 6（2014）494. 当社区中的所有智能体都收到所有的值时，它们选择执行时间最短的智能体As，谁能承受这个时间，采取子任务qR，标记为“工作”，并开始其解决方案;TRjSol. 的5. 代理A，从所有代理请求任务qR的解所需的数据，这些代理是通过传入弧与顶点qR连接的顶点子集的所有者;6. 如果其中一个智能体完成了某个子任务的决策，则将该子任务标记为“就绪”;7. 在解决每个子任务之后，代理使用其计算复杂度YR和决策时间Tsol来确定其CN的当前性能Sj，Sj =YR / Tsol，并将结果值发送给所有其他代理和公告板;8. Agent估计社区的特征，以确定任务是否可以在指定的时间内解决。如果社区不能解决任务，则Agent将其标记为“未完成”，社区的创建重新开始;9. 如果有任何未解决的子任务，则转到步骤1;10. 如果代理完成了用户任务中最后一个子任务的求解，它将结果数据发送到公告板，然后发送给用户。该算法的主要优点是计算过程自适应。6. 实验和结果由于分布式控制系统中的参数较多，基于专用控制网资源的分布式控制系统中的相关任务求解算法的效率很难保证。为此，我们创建了DCS的程序模型，该模型允许对包含多达1000个CN的DCS进行建模，解决多达250个任务。图3显示了创建的程序模型的界面[17]。Anatoly Kalyaev和Iakov Korovin/AASRI Procedia 6（2014）4955图三. DCS程序模型接口右边的表格显示了DCS的一组任务、它们的状态（“新”/“求解”/“就绪”）及其参数（求解的最大时间、复杂性、求解的虚拟点数量等）。这个表中的每个任务都有不同的颜色。DCS CN的视觉表示可以在中心找到（许多圆圈）。每个圆圈代表建模的CN，其颜色与CN处正在解决的任务的颜色相研究的主要目标是所提出的算法的效率的实际证明，但我们也想评估的处理器时间的相对损失CN由于分散计算的调度。这就是为什么我们必须用不同的CN参数和计算机网络进行几系列实验的原因。在研究所提出的算法时，我们使用了我们在南方联邦大学工作的一些类型的真实任务[18]。我们决定使用CN的实际负载百分比，它可以显示由于组织目的而导致的处理器时间损失，以及及时解决的任务百分比，它显示了最终用户的系统效率[19]。DCS中有许多重要的参数，这就是为什么我们决定使用实验计划：我们将参数分为三组：主要（系统参数）（P），次要（特定任务和CN的参数）（S）和第三（用户条件参数）（T）。最后，我们决定探索DCS的以下参数的影响： DCS中氯化萘的数量（P1）; 任务的频率（P2）;56Anatoly Kalyaev和Iakov Korovin/AASRI Procedia 6（2014）49 CN的计算能力（S1）; 网络带宽（S2）; 任务的计算复杂度（S3）; 在任务的子任务之间发送的数据量（S4）; 优先级（T1）; 子任务数（T2）; 解决任务的时间（T3）。对于主要参数，我们决定使用绝对值，对于次要参数，使用相对值，对于第三参数，使用有限的随机值。为了使结果更精确，由于随机值，我们进行了三次每个实验。这篇论文的卷给我们没有机会显示所有的实验结果，这就是为什么下面你可以看到表格（表1，表2）与他们的一部分。表1.实验研究结果：CN时的实际负荷。参数S1 S2 S3 S4P1=500P1=500氯化萘实际负荷百分比，%P1=500 P1 = 1000P1=1000P2=10P2=50P2=100P2=10P2=50P2=1001----8089887176742---+7987876976733--+-8189887177754--++8390887278745-+--8289877276766-+-+8188867075737-++-8489887578788-+++8388867377769+---78868672787610+--+77868572787711+-+-81888874797812+-++80878674777713++--77868671757314++-+77858572777515+++-81878673777416++++838987748078平均80,4387,6886,6872,1877,1275,43表2.实验研究结果：任务及时解决。次要参数S1 S2 S3 S4P1=500P1=500任务解决方案P1=500及时更新，%P1=1000P1=1000P1=1000P2=10P2=50P2=100P2=10P2=50P2=1001----9998979998982---+9898979998983--+-9897979998984--++9896979898975-+--9998989999996-+-+9997979998987-++-9897979898978-+++9896969898979+---99999899999810+--+99979799989711+-+-99989899989712+-++99979799989813++--99999999999914++-+99979799989815+++-99979699989816++++999898999998Anatoly Kalyaev和Iakov Korovin/AASRI Procedia 6（2014）4957平均值98，68 97，43 97，25 98，81 98，25 97，81结果表1显示，CN下的实际负载百分比良好：从72%到92%。这意味着由于组织而损失的时间占总时间的8%到28%。在相同方向的现代研究[8][9]表明，在DCS中解决连贯任务的平均有效性约为40%，这意味着所提出的方法是有效的。从表2中还可以看出，模型化DCS中的几乎所有任务都已成功地及时结论本文提出了一种新的分布式计算的自适应多智能体组织方法。所提出的方法的主要好处是可能使用许多不同的私人计算机的资源来解决连贯的任务。作者计划研究所提出的算法的下一步是创建DCS的功能原型，这将允许在科学实验室的计算机的基础上创建计算网络。引用[1] 福斯特岛Kesselman角和Tuecke，S.网格剖析：实现可扩展的虚拟组织。国际高性能计算应用杂志，15（3）。200-222. 2001年[2] 福斯特岛Kesselman，C.，Nick，J.和Tuecke，S.网格的生理学：一个用于分布式系统集成的开放网格服务体系结构。全球电网论坛。[3] 维诺格拉多夫全球资源信息数据库项目现状分析//Jet Info onlinehttp://www.jetinfo.ru/stati/? nid=0161d223cb9ed29f66470cbf7931ae22，2007。[4] 关于Globus Toolkit，http://www.globus.org/toolkit/about.html。[5] How SETI@home works，http://seticlassic.ssl.berkeley.edu/about_seti/about_seti_at_home_1.html.[6] Thain，D.，Tannenbaum，T.，和Livny，M，Distributed Computing in Practice：The CondorExperience Concurrency and Computation：Practice and Experience，Vol.17，No.2 -4，323-356，2005。[7] Berman，F.沃尔斯基河，Adaptive computing on the Grid using AppLeS，IEEE Transactions onParallel and Distributed Systems，Vol.14，369[8] Poleshaev P.N.实验研究的算法的任务规划网格系统与模拟器/材料的国际会议[9] Ivashko E.E.，Golovin A.S. BOINC-GRID /“高性能计算”HPC-UA'2012国际会议材料的计算效率[10] 吴德立，多智能体系统导论，北京，2002，366页。[11] 卡利亚耶夫A.I.全球资源信息数据库社区代理人的分散组织管理人。- SFU的程序。Technicalsciences，2008，2011，230-238.[12] Kalyaev A.I，Melnik E. V.关于网格/极端机器人技术中分散组织计算的一种方式。//2010年圣彼得堡青年科学家学校国际会议材料。- P. 73比75[13] 塔拉索夫足球俱乐部从多智能体系统到智能组织，2002年。[14] Kalyaev A.I Multiagent Approach for Building Distributed Adaptive Computing System / ProcediaComputer Science，第18卷，2013年，第2193-2202页。[15] Kalyaev A.I.分布式网格/国际青年科学家会议高性能计算和模拟2012中分布式计算的自适应组织方法和算法。一本文摘。-55-5658Anatoly Kalyaev和Iakov Korovin/AASRI Procedia 6（2014）49[16] Kalyaev A.I.在分布式GRI D /Heral d计算机和信息技术中自适应组织分布式计算的方法和算法，2012年4月4日。–28-33[17] Kalyaev A.I，Melnik E. V.《网格计算/信息通信和计算技术分散组织的一种方式：第三届国际会议材料-乌兰乌德》，2010年。- 第160 -162页[18] Hisamutdinov M.V.，科罗温公司，Kalyaev A.I.进化算法在油田设备故障预测人工神经网络训练过程中的应用/ 2013第二届计算机、通信、控制与自动化国际研讨会（3CA 2013）会议录。- 亚特兰蒂斯出版社第253-257页。[19] Gorelova G.V.，Radchenko S.A.，Melnik E.V.，Kalyaev A.I.实验计划，同时研究新的方法和分布式计算组织的算法/计算机和信息技术先驱报2010年，2007年。–49-5 6