（计算机应用技术专业论文）基于移动agent的分布式路由算法研究.pdf

坝i ：i 2 丈基于移动a g e n t 的分布式路由算法研究 摘要 6 24 1 8 0 移动a g e n t 技术是随着i n t e m e t 的发展而出现的一种新兴的分白式计算技术， 能够较好地适应i n t e r n e t 分布式的特点，有效地简化分布式系统的设计、实现与 维护。这些优越性使得基于移动a g e n t 的应用迅速成为当前计算机领域研究的热 点，从电子商务、分布信息查询、并行处理、个人助理、信息发布、监视与通知、 安全巾介到远程通信网络服务、工作流应用与群体，无所不在。1 9 9 8 年，g i a n n i d ic a r o 与m a r c od o r i g o 将移动a g e n t 思想引入网络分布式路由计算领域，提出 了一种全新的路由算法a n t n e t ，是对i n t e m e t 路由系统的一次革新，主要借助于 一群具有协同工作能力的移动a g e n t ，探索并记录网络资源状态信息，然后用这 些信息按照某种规则刷新节点路由表，从而维护整个网络路由信息的一致性。 本文首先介绍了基于移动a g e n t 的分布式路由算法的研究意义和国内外研究 现状，论述了移动a g e n t 的基本理论及与路由算法的相关性。分析了传统路由算 法和a n t n e t 算法存在的问题。在此基础上，就路由表的初始化、通信网络中移 动a g e n t s 的数罱控制、网络链路出现故障后路由表的更新等几个方面提出了改进 意见，并进行了实验和性能分析。最后，总结论文所做工作，并对今后进一步探 讨基于移动a g e n t 的分布式路出算法问题提出了一点设想。 关键词：移动a g e n t ，a n t n e t 算法，分靠式路由算法，网络模型 第i 贝 坝i ：论文 皋十移动a g e n t 的分布式路由算法研究 a b s t r a c t a n t n e ti san o v e la l g o r i t h mi nc o m m u n i c a t i o nn e t w o r k s i na n t n e t ，ag r o u po f m o b i l ea g e n t sb u i l dp a t h sb e t w e e np a i ro fn o d e s ，e x p l o r i n gt h en e t w o r ka n d e x c h a n g i n go b m i n e di n f o r m a t i o nt ou p d a t et h er o u t i n gt a b l e s t h i sp a p e ra n a l y z e s a n t n e ta n dp r o p o s e si m p r o v e m e n t ss u c ha si n i t i a l i z a t i o no fr o u t i n gt a b l e s ，c o n t r o lo f t h en u m b e ro fa g e n t si nt h en e t w o r k ，u p d a t i n go fr o u t i n gt a b l e sa f t e rn e t w o r k r e s o u r c e sf a i l u r e s ，c o m p a r i n gt h e i rp e r f o r m a n c ew i t hr e s p e c tt ot h eo r i g i n a la n t n e t a tt h ee n do ft h i sp a p e r ，ab r i e fs u m m a r ya n ds o m ec o n c e i v e sa b o u tt h ef u r t h e r r e s e a r c ha r ei n t r o d u c e d k e y w o r d s m o b i l ea g e n t ，a n t n e t ，d i s t r i b u t e dr o u t i n ga l g o r i t h m ，n e t w o r km o d e 筘i i 畎 顺i + 论文 基于移动a g e n t 的分布式路由算法研究 1 绪论 1 1 研究意义 智能软件a g e n t 技术的诞生和发展是人工智能技术( a r t i f i c i a li n t e l l i g e n c e ， a i ) 和网络技术发展的必然结果。从2 0 世纪6 0 年代起，传统的a i 技术开始致力 丁知识的表达、推理、机器学习等技术的研究，其主要成果是专家系统。专家系 统把专q k 领域知识与推力有机地结合在一起，为应用程序的智能化提供了一个实 j j 的解决办法。作为人工智能的一个分支，a i 计划理论的研究成果使应用程序 有了切步的面向对象目标和特征，即应用程序具有了某种程度上的主动性：而人 工智能的另一个分支决策理论和方法则使应用程序具有了自主判断和选择 行为的能力。人【：智能围绕着知识所进行的广泛研究和应用工f 逐步形成- f l 新的 学科，这就是知识工程，它涉及知识的获取、存储和管理等许多课题。所有这些 技术的发展加快了应用程序智能化的进程。 网络技术的发展使多个应用程序间相互作用的模式正从单一的集成式系统 向分斫i 式系统演化。一个在地理上和物理上分布的应用程序之间通信与合作的网 络底层基础结构正逐步建立起来。分布式对象技术则进一步使分布且异构的应用 程序之间能以一种共同的方式提供和获得服务，实现了在分稚式状态下的“软” 集成。 智能化和网络化的发展促成了软件a g e n t 技术的发展，软件a g e n t 技术正是 为解决复杂、动态、分和式智能应用而提供的一种新的计算手段。其中移动a g e n t 作为软件 a g e n t 的一个分支它是一个可以在异构网络上的主机之间自主迁移和 独立运行的计算机程序，它寻找合适的计算资源、信息资源或软件资源，利用与 这些资源同处一台主机或子网的优势，处理或使用这些资源，代表用户完成特定 的任务。同传统的r p c 方式相比，移动a g e n t 具有降低网络负载、克服网络延 迟、支持异步及自主交互、易于协议封装、可动态自适应、自然的异构性等优点 i q 。 随着网络技术的发展和计算机应用水平的提高，计算机通讯网络广泛应用与 科研、教育、管理、生产及商业等各个领域。在计算机通信网络的设计、建设过 程中，路由选择是一个十分重要但又非常复杂的因素。理想的路由选择策略，能 够大大降低网络的传输时延，提高实时性，在一定程度上降低网络的营运费用， 从而提高网络的性能价格比。当前的因特网只能提供尽力而为( b e s t e f f o r t ) 的 服务，即它只是尽其所能的转发用户报文，不能保证用户数据传输的服务质量， 帮1 负 伸! i 。论义璀十移动a g e n t 的分布式路由算法研究 如带宽、延时、延时抖动和报文丢失率等。这种服务模式适合于传统的应用，如 f t p 和电子邮件等。但是，如今出现了大量新型服务，如i p 电话、视频会议、 远程教学、视频点播，这些新应用有一个共同的特点强实时性。他们要求网 络提供比“尽力而为”更好的传输服务。这样，在因特网上就存在传统的数据应 用和多媒体实时应用两种类型的应用，这两种应用对实时性的要求刁i 同，因此， 网络需要根据用户的需求提供不同的传输服务，为此在网络中增加服务质量 ( q u a l i t y o f - s e r v i c e ，q o s ) 机制1 2 】。但是，目前在网络中得到广泛使用的传统算 法存在效率低、不能充分利用网络资源、无法快速响应网络状态的变化等缺点， 其1 1 1 无法快速响应网络状态的变化对q o s 路由影响尤其大，因为，如果网络拓 扑编构和状态变化很频繁，将导致路由失败率的大幅提高。一般而言，集中式管 理机制把重要的决策局限于某几个节点，这种机制存在几点明显的不足：首先， 随着不同用户群体涌入i n t e m e t ，其服务规模r 益扩大，这些节点便会成为系统 性能的瓶颈；另一方面，如果这些控制节点出现故障不能够与其它节点通信，整 个网络将会面临瘫痪；其次，集中式体系结构不能够迅速适应网络拓扑结构的各 种变化；最后，集中式的管理体系结构与现实网络固有的分布式之问存在明显的 不兼容性。面对网络规模同趋扩大的状况，现今i n t e m e t 固有的集中式控制系统 已显得无能为力。f 1 趋庞大、复杂的网络亟需一种分散化的管理机制。因而提出 基于移动a g e n t 的路山算法，如果能将该算法付诸实现，必将给网络路由的发展 带来新的契机。 1 2 国内外现状和研究内容 计算机网络技术同益成为计算机应用的核心技术之一它是分布式计算、通信 技术、信息工程技术的基础。而路由选择策略作为计算机网络的关键技术之一， 其优劣直接影响计算机通信的效率和质量。因此，多年来人们对路出选择策略的 研究使用了不同的方法，而且为了适应网络上层出不穷的新型服务( 他们要求强 实时性和高的传输质量) q o s 路由逐渐受到研究者的关注并提出许多启发式算 法。国内外学术界的许多学者在这方面产生了浓厚的兴趣，研究了多种路出选择 策略，发表了多篇影响颇大的论文和专著。 a g e n t 的理论与技术研究可以追溯到7 0 年代前期m i t 关于分梅式人工智能 的研究。从8 0 年代术开始，a g e n t 理论、技术与其他的领域结合得到广泛应用。 移动a g e n t ( m o b i l ea g e n t ) 作为a g e n t 的研究方向之一，倍受关注和深入研究。 移动a g e n t 计算模式拓展了传统的计算模式，它不仅结合了a g e n t 的自治、智能 等特性，而且引入了移动的概念，极大的延伸了分布式计算的概念。这种计算方 式在如何充分利用网络资源，如何给移动用户提供高效的服务等诸多问题上提供 笫2 呱 顺i ：论文 娃十移动a g e n t 的分布式路由算法研究 了新的思路，目f j 移动a g e n t 技术的研究热点包括将移动a g e n t 技术和已有实现 系统进行集成的集成框架研究、移动a g e n t 的编程模型的研究、移动a g e n t 的应 用系统丌发方法的研究等。在分布式网络管理、网络监控、动念信息获取、智能 网、电子商务、工作流管理、主动网和移动通信网等方面，移动a g e n t 技术有广 阔的应用前景。 群体智能1 3 4 i 是近年来学术界兴起的又一热门研究课题，研究者们从生物进化 的机理受到启发，提出了许多用以解决复杂优化问题的新方法，如遗传算法、进 化规划、进化策略等。蚁群算法是最近几年来才提出的一种新型的模拟进化算法， 山意大利学者m d o r i g o 等人提出来，他们称之为蚁群系统，并用该方法求解了 旅行商m 题( t s p ) f5 1 、指派问题( a s s i g n m e n tp r o b l e m ) 1 6 1 、j o b s h o p 问题【7 i ，取 得了一系列较好的实验结果。受其影响，蚁群系统模型逐渐引起了其他研究者的 注意，他们，1 ：始用该算法解决一些实际问题i s 9 】，充分显示出算法在求解复杂优化 问题( 特别是离散优化问题) 方面的优越性。人工蚁群算法是受到人们对自然界 巾真实的蚁群集体行为的研究成果的启发而提出的一种基于群体智能的模拟进 化算法，属于随机搜索算法，由意大利学者g i a n n id ic a r o 与m a r c od o r i g o 等人 t i - 先提出。m d o r i g o 等人首次提出该方法时，充分利用了蚁群搜索食物的过程 与著名的旅行商问题( t s p ) 之间的相似性，通过人工模拟蚂蚁搜索食物的过程 ( 即通过个体之间的信息交流与相互协作最终找到从蚁穴到食物源的最短路径) 柬求解t s p ，为了区别真实蚁群系统，这种算法称为“人工蚁群算法”。它是一 种很有发展f j i f 景的方法。人工蚁群算法的实质是将问题的表示抽象为一个图，一 群假想的蚂蚁在图上移动，移动的过程中建立解决方案并通过增加随时收集的信 息不断改变问题的表示。1 9 9 8 年，麻省理工的学者利用这种算法的思想解决了 电路交换无线通信网络的路由问题【10 1 1 1 1 。后来g i a n n id ic a r o 与m a r c od o r i g o 提出了一种新的数据报交换网络的路由算法a n t n e t 算法【l “，一种基于移动 a g e n t 的分厕i 式自适应路由算法，将蚁群算法思想应用于具有规则拓扑结构的i p 数据报网络路由问题，实验显示其性能优于传统的i n t e r n e t 路由算法d v 与 链路状态最短路径，证明了将移动a g e n t 引入路由计算领域借助移动a g e n t 的思想采用一种群体智能进行路径的分布式计算，是i p 网络路出计算领域的新 尝试。 1 3 论文所做工作及论文结构 本论文的主要工作是围绕移动a g e n t 、a n t n e t 算法及传统算法存在的问题及 对a n t n e t 算法的改进和性能分析这几个方面进行。其中对a n t n e t 算法和改进 a n t n e t 算法进行了探讨，以便尽可能地提高和改进传统路由算法的工作效率和 第3 炎 倾i + 论义雉于移动a g e n t 的分布式路由算法研究 系统性能，同时发挥移动a g e n t 自身的最大效用。论文首先介绍基于移动a g e n t 的分砷j 式自适应路由算法的研究意义和状况，对移动a g e n t 的基本理论、移动 a g e n t 与路山算法的相关性以及a n t n e t 算法等基本内容作了陈述，接着论述了 改进的a n t n e t 算法，并进行了性能分析。论文最后是对所做工作的总结和对将 来工作的展望。 本论文第一章是绪论；第二章是对移动a g e n t 基本理论及与路由算法的相关 性的介绍；第三章论述了经典路由算法存在的问题；第四章提出了改进a n t n e t 算法及性能分析；最后第五章是工作总结与展望。 第4 负 坝i ：沦丘=苯十移动a g e n t 的分布武路由算法柑f 宄 2 a g e n t 基本理论 2 1 软件a g e n t 概述 2 1 1 软件a g e n t 的定义 软件a g e n t 的研究起源于多a g e n t 系统( m a s ) ，而m a s 是分自i 式人工智 能( d a i ) f j i t 0 究的三个问题之一，另外两个是分靠式问题求解( d p s ) 和并行 人j j j 智能( p a l ) 。目时，人们对a g e n t 的概念阐述还有争议，a g e n t 直译为“代 川一广义上它足指具有智能的任何实体，包括人类、智能硬件( 如机器人) 和 钳能软什。 到f l 时为i l 二r i ：多研究者提山了各自对a g e n t 的定义没有一个被大多数人 队町的统一的a g e n t 定义。在a g e n t 的不同应用系统中，不同研究领域的学者根 掘a g e n t 的特性表现并考虑各自领域的技术特点给出各自的定义。但是总体来 讲，对a g e n t 给出的较为典型的定义一般有两种：其一，a g e n t 是驻留于环境中 的实体，它可以解释从环境中获得的反映环境中所发生事件的数据，并执行对环 境产生影响的行为。该定义山f i p a ( f o u n d a t i o nf o ri n t e l l i g e n c ep h y s i c a la g e n t ) 给 b f i 队是一个致力于a g e n t 技术标准化的组织。在这个定义中m i ，a g e n t 被看 作足一种在环境巾“生存”的实体，它既可以是硬件( 如机器人) ，也可以是软件。 e 二，足软件a g e n t 的研究者对a g e n t 进行的定义：智能软件a g e n t 是能为用户 执i ? 特定任务，具有一定程度的智能从而允许自主执行部分任务弗以一种合适的 力式1 j 环境棚互作用的软件程序。 2 1 2 软件a g e n t 的特性 虽然，日i 衍人们对于a g e n t 的确切定义还没有达成共识，但是对于a g e n t 应 该具有的特性却有一个较为普遍的认同：a g e n t 首先是智能的，它应对环境有响 应性、自主性和主动性等；同时。a g e n t 又要具备社会性。通常认为一个主体部 分或全部拥有以下的特性i 】： 自主性( a u t o n o m y ) ：a g e n t 可以控制它自身的行为，它有自己的目标或意 阁，运行埘刁；组接山人或者其它实体控制，即它能在没有与环境的榴互作用或来 臼王f 境的命令的情况下自主执行任务。这是a g e n t 区别于普通软件程序的基本特 性。 笫5 ) i 倾i ：论文摧十移动a g e n t 的分布式路由算法研究 响应性( r e a c t i v i f y ) ：a g e n t 应该可以感知所处的环境，并通过行为对来自 环境的影响和信息做出适当的响应。 主动性面向目标( p r o - - a c t i v i t y g o a i - o r i e n t e d ) a g e n t 的行为应是主动的 或说自发的。它感知周围的环境；并采取基于目标的主动行为。 长寿性( l o n g e v i t y ) ：传统程序由用户在需要时激活，不需要时或者运算结束 后停止。a g e n t 与之不同，它应该至少在“相当长”的时间内连续地运行。 可移动性( m o b i l i t y ) ：a g e n t 可以携带数据和能够在远处执行智能指令，可以从 一个地方移动到另一个地方而保持其内部状态不变。 推理学习自适应能力( r e a s o n i r g l e a m i n g a 6 a p t i o n ) a g e n t 的智能由三个主 要部件来完成即内部知识库、学习或自适应能力以及基于知识库内容的推力能 力。它可以根据其当前的知识和经验，以理性的、可再生的方式推理或推测并且 修改其行为以适应新的环境。 规划能力( p l a n n i n g ) ：根据目标、环境等的要求，a g e n t 应该至少对自己的短 期行为作出规划。 角色( c h a r a c t e r ) ：a g e n t 在社会活动中对安全性、风险、信任、诚实等因素 的考虑。 通信合作协调( c o m m u n i c a t i o n c o o p e r a t i o n c o o r d i n a t i o n ) ：通常主体不是 单独的存在，而是生存在一个有很多主体组成的世界中。主体之间良好有效的协 作、通信，可以大大提高整个系统的性能。这是在a g e n t 群体中应具有的社会特 性。 2 1 3 软件a g e n t 的分类 由于a g e n t 的定义不统一，各个领域的研究者都把具有某些a g e n t 特性的研 究对象称为某类a g e n t 。因此，为明确这些a g e n t 的具体含义，必须根据a g e n t 的不同功能和特性对a g e n t 进行分类。一般软件a g e m 分为如下类： ( i ) 按功能分类。 信息a g e n t ( i n f o r m a t i o na g e n t ) ：它支持用户在分布是系统或i n t e m e t 网络 中智能搜索信息或智能管理网络资源。 界面a g e n t ( i n t e r f a c ea g e n t ) 或个人助手：它的主要任务是协助用户完成 乏味而重复性的工作。a g e n t 将观察并监督用户怎样执行特定的任务，当这些 a g e n t 能确定用户在特定情况下将如何反映时，它就开始替代或帮助用户完成任 务。这些a g e n t 已针对某一用户进行了个性化处理，适应于特定用户的行为。这 些问题与人机接e l ( h c i ) 、用户建模和模式匹配密切相关。 任务a 胛n t ( t a s ka g e n t ：它是帮助人类进行复杂决策和其他知谚 处理的软 第6 负 碳i ：沦殳 基于移动a g e n t 的分布式路由算法研究 件a g e n t 。这类a g e n t 以a i 领域的机器学习、计划、资源受限的推理、知识表 达等为基础在一实用框架中应用。 ( 2 ) 按属性分类。 反映a g e n t ( r e a c t i v e a g e n t ) ：具备对当时处境的实时反映能力的a g e n t 审慎a g e n t ( d e l i b e r a t i v e a g e n t ) ：在目标指导下具备自主行动及合作等综合 能力的a g e n t 。 合作a g e n t ( i n t e r a c t i v e a g e n t ) ：具备社会合作能力的a g e n t 。 混合a g e n t ( h y b r i d a g e n t ) ：具有实时反映、目标指导下自主行动及合作等 综合能力的a g e n t 。 ( 3 ) 按行为方式分类。 自主a g e n t ( a u t o n o m o u sa g e n t ) ：在复杂动念环境中自主感知和行动。 多重a g e n t ( m u l t i a g e n t ) ：一个a g e n t 能利用关于其它a g e n t 的知识来协调 它与其它a g e n t 的行动或合作完成目标。 助手a g e n t ( a s s i s t a n ta g e n t ) ：只与人类a g e n t 相互作用。 ( 4 ) 特殊类型。 移动a g e n t ( m o b i la g e n t ) ：位子网络中并通过迁移或服务接口能与网络中 其他程序进行通信的a g e n t 。它能够根据自己的选择不断地从一个网络位置移动 一个位置。 可信a 窟e n t ( b e l i e v a b l ea g e n t ) ：它是在与人的相互作用中以“令人信任”的 特征来执行，它需要处理与人的相互作用中发生的各种情况，而不是局限于把少 量事情做的特别好。 2 2 移动a g e n t 2 2 1 移动a g e n t 概念 移动a g e n t 是在网络上可迁移的软件a g e n t ，具有自治性、移动性、智能性。 移动a g e n t 首先是一个软件a g e n t ，满足a g e n t 的目标驱动特征，具有智能性和 自治性。其次移动a g e n t 是代码、数据以及执行语境的软件包，它可以在执行过 程中，有目的地、自治地在网络中移动f 1 5 ，j 6 】，利用与分布资源的局部交互而完成 分布任务的软件实体。在转移过程中它的执行状态被保持，转移到目标后的执行 是持续的。扶实现技术的凫度看移动a g e n t 系统主要有移动a g e n t 平台和移动 a g e n t 组成。移动a g e n t 平台是一个虚拟机，通常被称为移动a g e n t 服务器，为 移动a g e n t 的移动和执行提供执行环境，为移动a g e n t 的发射、接受、恢复、安 全管理和服务调用等提供基础服务设施。移动a g e n t 携带完成计算任务所需的代 第7 负 坝i ：论文摧f 移动a g e n l 的分布式路由算法研究 码和数据以及a g e n t 的运行状态，在网络上不同主机之间迁移并完成相应的操 作。 2 2 2 移动a g e n t 计算模型 2 2 2 1 移动a g e n t 计算模型的优点 和传统的分布式计算模型相比，移动a g e n t 具有如下优点： 1 降低网络负载：移动a g e n t 到达目标主机直接和当地环境进行交互，无 需在主机问传递大量的交互信息，从而减少网上原始数据的流量。 2 提供实时的远程交互：移动a g e n t 具有自治性，到达目的地后可自主的 执行任务并与环境进行交互，克服了网络的延迟。 3 异步执行计算：在传统的分布式计算模型中，单个的异步操作可以通过 消息传递实现，但整个任务在收到前一个异步操作的结果之前是不能继续的。移 动a g e n t 可以将一组操作成批的发送至目的地，等整个任务完成后将最终结果返 回，实现整个任务的异步执行。 4 包装不同协议：移动a g e n t 可以移到远程主机上，通过专用协议建立私 有数据交换通道。 5 动态适应环境：具有感知运行环境和对其变化做出自主反映的能力。 6 自然的异构性：移动a g e n t 一般独立于特定的主机和传输层协议，仅仅 依赖于它们的执行环境。 2 2 2 2 移动a g e n t 计算模型 移动a g e n t 的结构包括相互关联的安全服务模块、环境交互模块、任务求解 模块、知识库、内部状态集、约束条件和路由策略，如图2 2 1 所示。结构模型 的最外层为安全服务模块，它是a g e n t 与外界环境通信的中介。a g e n t 通过环境 交互模块感知外部环境并作用与外部环境。a g e n t 的任务求解模块包括a g e n t 的 运行模块及a g e n t 任务相关的推理方法和规则。知识库是a g e n t 所感知的世界和 自身模型，并保存在移动过程中获取的知识和任务求解结构。内部状态集是a g e n t 执行过程中的当前状态，它影响a g e n t 的任务求解过程，同时a g e n t 的任务求解 又作用于内部状念。约束条件是a g e n t 的创建者为保证a g e n t 的行为和性能而做 出的约束。路由策略决定a g e n t 的移动路径，路由策略可能是静态的服务设施列 表，或者是基于规则的动念路出以满足复杂和非确定性任务的求解。 第8 负 外部环境( 服务设施或其他a g e n t ) r 环境交互模块卜一叫 安全服务模块 士 任务求解模块+ + i约束条件 移 动 运行模块 喀 l 暑 方法及推理规则h i 路由策略 士 知识库 7 内部状态集 图2 2 1 移动a g e n t 的结构模型 2 3 移动a g e n t 与路由算法的相关性 一般而苦，集中式管理机制把重要的决策局限于某几个节点，这种机制存在 几点明显的不足：首先，随着不同用户群体涌入i n t e m e t ，其服务规模r 益扩大， 这些节点便会成为系统性能的瓶颈；另一方面，如果这些控制节点出现故障不能 够与其它节点通信，整个网络将会面临瘫痪；其次，集中式体系结构不能够迅速 适应网络拓扑结构的各种变化；最后，集中式的管理体系结构与现实网络固有的 分柑式之州存在明显的不兼容性。面对网络规模日趋扩大的状况，现今i n t e m e t 固有的集中式控制系统已显得无能为力。日趋庞大、复杂的网络亟需一种分散化 的管理机制。因此引入移动a g e n t 来解决网络路出问题。 2 3 1 移动a g e n t 解决网络问题的研究现状 移动a g e n t 作为一种未来的分布计算模式逐渐成为当今计算机技术的研究热 点。随着这种分稚式计算技术的逐步成熟，移动a g e n t 开始进入网络管理领域与 路山计算领域利用移动a g e n t 的网管机制取代集中式的网络管理，利用移 动代理计算组播路径树的算法【博i 相继被提出。1 9 9 8 年麻省理工学者n e l s o n 致力 第9 页 坝：论文基十移动a g e n t 的分布式路由算法研究 于“基于a g e n t 的路由算法”的研究，提出了无线网络中解决路由问题的新方案 基本思想是借助于小的a g e n t 探索网络更新路由表【1o 】。近年来，不断有研究 者尝试利用移动a g e n t 的自适应学习策略解决i n t e m e t 数据报网络的路由问题， 1 9 9 9 年意大利学者d i c a r g o 提出了著名的a n t n e t 算法【l “。a n t n e t 算法对i p 网 络路由计算模式进行了一次全新改进，本篇论文就是在其基础上进行改进，借助 于一组相互协作的移动软件a g e n t 探索网络资源，计算满足需求的路径，将传统 的集巾手少数中心控制节点的智能决策扩展到整个网络各个中间节点。 2 3 2 移动a g e n t 用于路由问题的思想 人们在对诸如蚁群等社会性动物行为的研究中发现，蚁群不可能象人类社会 那样，根据一个统一的计划来协调行动，达到一个共同的目的。它们的交互是通 过对环境的影响白j 接实现的。蚂蚁的行为源自环境的刺激，如果一只蚂蚁感受到 它周阿环境的变化，那麽它将响应这种刺激，做出相应的行动，这种行为的结果 又改变了它周围的环境，影响到其它蚂蚁。这个过程不断迭加，使整个蚁群保持 协调一致，共同完成某项任务。蚁群中最常见的工作是寻找蚁巢与食物源之问的 屉短路径，它是利用蚂蚁的道路标记和道路跟踪行为来实现的。蚂蚁在爬行过的 道路上会留下一种称为p h e r o m o n e 的特殊挥发物质，这种物质能吸引其它的蚂 蚁，p h e r o m o n e 越集中，吸引的蚂蚁就越多。在此我们给出两种假设：一种假设 是在蚁巢和食物源之间存在n 条路径r o u t e i 、r o u t e 2 、r o u t e n ，其中r o u t e l 最 短而r o u t e n 最长；另种假设是蚁群最初没有发现蚁巢和食物源之间的最短路 径。这时，蚂蚁先随机的选择一条路径，并在沿途留下p h e r o m o n e 。因为蚂蚁在 蚁巢和食物源之刚的最短路径上花费时间最短，所以，在这条道路上的p h e r o m o n e 也就最多，更多的蚂蚁也会被吸引到最短路径上来，同时这些蚂蚁又会在这条路 径上留下更多的p h e r o m o n e ，这样一来恰好形成了正反馈，蚁群很快就找到了蚁 巢和食物源之间的最短路径。 受到蚁群简单有效的寻找最短路径方法的启发，我们可以在网络的各个节点 上保存一张路山表，该表的元素值可以仿效蚂蚁的挥发物质p h e r o m o n e ，我们把 它设为选择某一相邻节点的概率值。每个a g e n t 模拟蚂蚁在网络中寻路，它可以 根据路山表上的概率值选择路径，又可以反过来修改路山表上的概率值，从而寻 找到合适的路由。 基于a g e n t 的路山策略可以称之为一种新颖的自适应路由方法，最初用于解 决无线通信网络中的动态路由算法问题，借助于一组小的a g e n t 探索网络状态学 习路由信息，进而更新路山表【io 。挣l 。当前，基于移动a g e n t 的路由研究集中于解 决传统路山算法普遍存在的一个问题负载均衡问题【】孙，其思想核心是借助于 第10 页 颂i ：沦文摹十移动a g e n t 的分布式路由算法研究 小的a g e n t ( 路由包) 【2 0 】模仿数据包的行为遍历网络，估测所经历路径的质量， 从这个角度而者+ ，各算法的不同之处主要在于a g e n t 收集路由信息且向节点传播 信息的策略。在这种路由策略中，路由表的作用同样不可忽视，它作为a g e n t 与 路山： 护进程( r o u t i n gd e m o n ) 之间的连接，类似于传统的路出算法如距离向量 算法中的路由表的结构。唯一不同的是路由表建立及更新的策略。这将在下面的 章节巾祥述。 2 3 3 路由算法中的移动a g e n t 在我们研究的网络路由范围内，移动a g e n t 具有下面五个重要特性： 1 a g e n t 是一个封装了代码与数据的执行线程。从程序的观点而言，它是自 治的。路径的计算随着a g e n t 的移动而移动。每个a g e n t 独立于其它a g e n t 运行。 a g e n t 在由一个网络节点移动到另一个网络节点的过程中保存了自身的所有状 态。 2 任何一个a g e n t 均能够在整个网络上移动。网络节点的基本体系结构应 该提供一个语苦层的原语，a g e n t 可以调用这个原语移动自己到下一个相邻节点。 3 考虑a g e n t 的传输与执行所带来的代价，a g e n t 的尺寸必须足够的小( 一 般为几十个字节) 。一组独立而又相互协作的a g e n t 个体具有复杂的群体智能行 为。 4 一个a g e n t 能够与其它a g n e t 相互协作求解复杂的动态任务：a g e n t 能够 访问网络节点的共享存储区域，读取与写入数据，其它a g e n t 可以利用前面a g e n t 的信息指导自己的移动路线。a g e n t 之间就是利用这种特殊的所谓“黑板方式” 进行通信协作的。 5 a g e n t 探索网络，记录信息，用它移动过程中学习的“知识”更新节点 的路由信息，建立最优路径。 一般来蜕，用于路由计算的a g e n t 的内部结构包括下列信息： a g e n tm o d e - a g e n t 的状态； d e s t i n a t i o nn o d ep 目的节点，当a g e n t 被创建时，可以随机产生也可人 为指定； s o u r c en o d e 源节点， 产生a g e n t 的节点； t a b ul i s t 当前a g e n t 移动过程中所经历的节点列表或所经历的链路的 列表； c o s t 1 i s t - 当前a g e n t 移动过程中所经所的节点之间的链路代价； t a b u1 i s t 用来跟踪a g e n t 所经历的路径，它的作用体现在两个方面：其一用来 确保a g e n t 不会访问已经访问的节点从而保证a g e n t 搜索的路径不会带有环路； 第11 贝 顺f ：论文甚于移动a g e n t 的分布式路由算法研究 其二a g e n t 用其准确记录的路径信息向网络中其他节点传播，实际还要借助于保 存在c o s t - l i s t 的信息。 2 4 小结 本章在介绍软件a g e n t 、移动软件a g e n t 的概念的基础上，阐述了a g e n t 与路 冉算法的相关性，把移动a g e n t 用于路由计算，并结合路由算法与移动a g e n t 的 特性，在路由算法中定义特定的移动a g e n t 及这些移动a g e n t 之问的通信协作方 式。 f i | i 【i ：论文 燕十移动a g e a t 的分布式路由算法研究 3 经典的路由算法 3 。1 概述 计算机通信网络中的路由选择问题是网络设计和建设过程中的一个重要因 素，一叮以描述为：给定一个具体拓扑结构的网络及其节点集合( n ) 与链路集合 ( l ) ，并己知网络中的所有通信节点对以及网络相应的传输需求和候选的路由集 合，在所有链路容量均确定的情况下，对每一通信节点对，从相应的候选路由集 合中选取一条路由，使得浚网络平均端到端的时延最小。 在传统的数据网络中，路幽所需考虑的仅仅是可连接性，路出算法在寻找最 优路径时，采用单一的指标如跳数或时延。但随着信息高速网的应用，为了支持 范围广泛的服务质量的需求，确定路由需要相当复杂的模型来描述网络，即路由 的测量指标要包括时延、带宽等。这样基于服务质量的路由问题就转化为寻找一 条能同时满足各个约束条件的非线性组合优化问题，该类问题已经被证明是n p 完全问题1 2 2 , 2 7 。 通信网络中路由问题的主要特征可以归纳如下： 1 具有适时约束的固有的分布式特征 状态信息数据库与路由决策系统完全分布于整个网络的各个节点，而且对于 用户的流量模式( t r a f f i cp a t t e r n ) ，状态信息与失败信号的传输延迟是不可忽视的， 因此，获得及时而且完整的分布式状态信息( 本质上是隐藏的) 是不可能的。在 每个决策节点，路山算法只能使用本地节点保存的及时信息与来自其它节点的非 本地的延迟的状态信息计算路径。 2 随机且随时间变化的特征 一般情况下，会话到达与数据产生的过程是动态的与随机的。而且，这个随 机过程与路由算法的递归交互使得建立一个针对整个系统的工作模型是不可行 的。 3 多目标性的特征 在设计路由算法时通常要同时考虑几个互相冲突的性能度量，比较常用的度 量足吞吐量( t h r o u g h p u t ) 与平均包延迟( a v e r a g ep a c k e td e l a y ) 。前者主要用来 衡量某一个时暗j 段内网络能够接纳的服务数量，而后者则是指同一时间内产生的 服务质量。其它性能度量则考虑路出算法对网络资源比如内存、带宽、和计算等 的冲击，还有算法的简单性及灵活性。 4 多约束性的特征 颂 j 沦文 旗手移动a g e n ! 的分布妓路由算法哥f 巍 约束( c o n s t r a i n t ) 被施以基本的网络拓扑结构、提供的网络服务和被请求的用 户服务。一般而害，对于异构的静止或移动的网络，用户请求低代价的、高质量 的、可靠的分布式多媒体服务。网络建设者或服务提供商在考虑技术的或商业的 因素的同时满足这些请求，争取最大利润努力。而且，在现代高速网络中用户 会话能够对网络资源的需求表达准确的请求，因此需要高层的容错能力与可靠 性。在这种情况下，一旦会话被接受，系统应该能够保证任何可以恢复的错误事 件发生的情况下，会话都应获得它需要的资源。 上述特征表明路山问题属于一类具有隐藏状态的加强学习问题 2 1 1 ( b e r t s e k a s & t s i t s i k l i s ，1 9 9 6 ) 。如何通过一种持续的在线学习的方式来获得当前 网络状态下最好的路由表项( 同时考虑网络性能标准) 是一个分布式自适应路由 系统的关键所在。 3 2 传统路由算法的特点和存在的问题 路由包含两个基本功能：一是搜集网络的状态信息并不断进行更新：二是根 据所搜集的信息计算可行路径。这两个功能都涉及到路由表，而制定路由表的过 程就是路由算法，它由主要由四种基本类型：集中式路由、分稚式路由、静态路 j 和臼适应的路由。 集中式路山( c e n t r a l i z e dr o u t i n g ) 集中的产生和维护路由信息，然后将信 息；。播给所有的网络节点。这种算法的优点是方法筒单，但是集中的产生和维护 路l j j 信息中心位置或任何与其相连的链路的故障都会对向网络节点提供路由信 息产生f m 重影响。 分棚j 式路出( d i s t r i b u t e dr o u t i n g ) 没有中央控制，每个节点必须独立的决 定和维护自己的路【u 信息。因此，节点或链路的故障对提供准确的路由信息影响 较小，但是节点可能需要更多的时捌了解远端的路出情况。 静念路山( s t a t i cr o u t i n g ) 节点无需重复执行路由算法，不根据实测或估 计的网络的当6 f 通信量和拓扑结构来做路由选择，一个节点一旦决定了它的路由 表，将不再改变。相应的这种路由对条件变化反映迟钝，原先最佳的路径在某种 情况下可能会成为最糟糕的路径。 自适应路幽( a d a p t i v er o u t i n g ) 镱略提供网络链路的最新信息。根据实 测或估计的网络的当前通信量和拓扑结构柬做路由选择。但是丌销相对较大。节 点必须维护当i j 的信息而且传输条件变化信息加重了网络负载。 颀i ：论史摹十移动a g c n t 的分布式路由算法研究 3 2 1 自适应的距离向量路由 每个节点构造一个包含到所有其它节点的距离( 开销) 的一维数组( 一个向 量) ，并将这个向量分发给与它直接相连的所有邻节点。动态的娃离向量路出通 过相邻节点的信息交换定期的更新距离向量： d ：d ( ，) 是t 时刻从节点i 经过邻节点n 到节点d 传输一个包的估计花费，如 图3 2 1 所示，g , n 是已知的从i 到它的邻节点n 的距离。 d 1 。d 图3 2 1b e l l m a n f o r d 算法中路由信息的更新 b e l l m a n f o r d 算法【3 5 j 是广泛使用的距离向量路由算法，如过去的a r p a n e t 和现在的i n t e r n e t 等网络都使用此算法，在i n t e m e t 中最广泛使用的路由协议之 一就是路由选择信息l 办议即r i p | ”j ，它就是建立在距离向量算法基础之上的。 尽管这个算法可以动态更新路由信息，但是它可能比较慢。尤其是当链路出 现故障时【2 8 1 而且这种算法被证明是振荡的f 2 9 】。 3 2 2 自适应的链路状态路由 链路状念路由算法维护一个完整的网络映像，每个节点将它所知道的信息传 达给相邻节点，这一点与b e l l m a n - f o r d 算法娜】相似，区别在于传达的信息不同。 节点收集与每个邻节点相连的每条链路的状态信息，这些信息是决定链路费用的 因素；节点为每个连接建立一个链路状态分组，这个分组指出通过那条链路相连 的两个节点和它收集的链路信息，然后节点将分组发送给每个邻节点：收到链路 状态分组的节点将它转发给所有的邻节点；由于链路状态分组在节点间交换，每 个节点最终知道网络拓扑结构，以及网络节点间的链路状态和费用。从而，它能 一 d h， d n 扣“刚 + 一 一 d d = = ) )( ( h d，h ，n d d 倾i ：论史姥十移动a g e n t 的分布式路由算法研究 够执行一种如d i k s t r a 算法【3 i 】的最省路径算法来确定到达给定目标节点的路径， 然后根据这些信息建立路由表。 个使用最为广泛的链路状态路由协议的是开放最短路径优先协议 o s p f l 3 3 1 ，该协议也越来越多的应用到i n t e r n e t 网中。该协议存在的问题是，