一种基于负载均衡的多Agent路径规划算法

《一种基于负载均衡的多Agent路径规划算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第42卷第2期2010年4月南Journalof京航Nanjing空航天大学UniversityofAeronautics一种基于负载均衡的多A朱广蔚秦小麟gent许学报＆Astronautics路径规划算法峰(南京航空航天大学信息科学与技术学院，南京，210016)V01．42No．2Apr．2010摘要：在分布式信息查询系统中，使用多个Agent协作完成查询任务是一种有效的方法，所有Agent的总行程影响网络的通信流量，单个Agent的最大负栽决定了查询任务的完成时间。现有方法大多研究如何减少Age

2、nt的总行程，未考虑Agent的负载均衡问题。本文提出一种基于负载均衡的多Agent迁移路线规剐(Loadbalancedmulti—agentplanning，LBMAP)算法首先寻找图中一条包含所有节点的TSP曰路，然后使用动态规划算法将该回路分为多段，每个Agent访同其中一段，算法兼顾了两个优化目标：最小化Agent的总行程、最小化Agent的关键负裁。仿真实验表明：随着Agent平均访问节点数的增大，LBMAP算法的性能趋近于理论最优值。关键词：移动代理；负载均衡；旅行商问题中图分类号：TP3

3、1文献标识码；A文章编号：1005—2615(2010)02—0198—06LoadBalancingAlogrithmforMulti—AgentItineraryPlanningZhuGuangwei，QinXiaolin，XuFeng(CollegeofInformationScienceandTechnology，NanjingUniversityofAeronautics&Astronautics，Nanjing，210016，China)Abstract：Intheagent—baseddi

4、stributedinformationsystems，itisordinarytousemultipleagentstocompletethetask．Thetotaltripimpactonthenetworkcommunicationstraffic，andthelargestsingleworkloaddeterminesthetimetocompletethetaskofinquiry．Existingmethodsfocusprimarilyonre—ducingmobileAgent7St

5、otaltrip，whiledoesnotconsideringtheloadbalancingproblem．Inthispaper，aloadbalancingalogrithmformulti—agentitineraryplanningisproposed．Firstly，thealgorithmfindsaTSPcircuit，andthendividethecircuitintosegments，eachAgentvisitsasegmentseparately．Theal—gorithmc

6、onsiderstwoobjectiveswhenplanningtheAgent’Stravelpath：minimizingthetotaltripandm’in‘im’iz‘ingthecriticalworkload．SimulationresultsshowthatLBMAPalogrithmproducesnear-optimalperformancewithincreasingaveragenumberofvisitingnodes．Keywords：mobileagent；loadbal

7、ancing；travellingsalesmanproblemAgent技术是一种新型分布式计算技术，基于Agent的分布式查询系统改变了传统的客户端／服务器查询方法[1】，Agent携带查询命令移动到服务器上执行相应的查询操作，然后将查询结果返回给用户，采用Agent技术实现分布式查询的方法有两种【2d】：(1)设计一个专门的Agent，它通过网络分别移动到各个节点，执行数据访问任务。(2)将一个任务分解成多个子任务，由不同的Agent来分别完成。在方法(1)中只存在一个Agent执行查询任务，它要

8、串行访问所有的节点后才能统计出结果。为了有效地利用网格并行计算的特点，通常采用的是方法(2)中的多个Agent协作技术，通过创建多基金项目：国家自然科学基金(60673127)资助项目；国家高技术研究发展计划(。八六三”计划)(2007AA012404)资助项目；航空科学基金(20085552021)资助项目。收稿日期：2009·04—02；修订日期：2009-11—26作者简介：朱广蔚，男，博士研究生，1978年6月生；秦小麟(联系人)，