（计算机科学与技术专业论文）基于多agent系统的智能路由资源分配策略.pdf

摘要 i 路由选择方法直接影响着电信网业务接通率和负荷平衡程度。我国长信网的接通 率为4 5 左右，链路的利用率也仅为3 0 - 4 0 。据估计，接通率每提高一个百分 点，收益可达1 0 亿元。71 目前的动态路由方法周期性地采样网络参数。由于呼叫到来的随机性和传输与处 理的延时，使决策的作出在整个采样间隔内落后于采样时刻，导致它们均只是准实时 的，从而影响决策的准确性和灵敏性：而被接受的呼叫是在“未来”的一段时间内保 持和占有资源。所以，良好的决策应该考虑：某个呼叫将受到的影响，以及将产生的 影响。也就是说，决策依据的网络情况应超前于采样时刻，即应进行预测。 为了提高电信网业务接通率和平衡网络负荷，本报告针对目前所使用的路由选择 方法的不足，提出全新的基于多a g e n t 系统和神经网络预测的路由选择策略，它的 总的思想是，选择路由前，预先把握网络的负荷趋势，即下一时刻可能的情况，在设 法让入呼被接通的前提下，全网的负荷要尽量平衡，并尽可能使本次入呼的成功不影 响此后的入呼被接通的可能性。电信网被映象成一个多a g e n t 系统。 网中各结点的a g e n t 以一定时间间隔根据负荷的历史数据( 时间序列) 和当前负 荷角人工神经网络方法预测下一时刻与各邻结点相连的链路方向的负荷情况。有入呼 请求的结点将a n n a 请求传给可选路由中的邻接结点，邻接结点将最新计算出的负荷情 况与设定门限值作比较，然后把是否可以接入新人呼的结果回传给本结点( 若接受， 还包含负荷值和空余中继线数) 。 若只有一条邻接链路满足要求，则该链路被选中；若没有，入呼被拒绝；若有不 止一条，则负荷值高且空余中继线数少的不选；如果负荷高、空余中继线多或负荷低、 空余中继线少，以负荷为最后比较依据，负荷高的不选。 仿真结果表明，其良好的分布特性和智能决策能力使之优于其它方法。这为解决 网络接通率低和负荷不平衡问题提供了良好途径。十 关键词：路由选择，多a g e n t 系统，窥湎，接通率，负荷平衡，神经网络 仿真，实时网络路由。 a b s t r a c t r o u t i n g i n f l u e n c e st h es w i t c h r a t e sa n dl o a d sb a l a n c i n g o f t e l e c o m m u n i c a t i o n sn e t w o r k sd i r e c t l y i nc h i n e s em a i n l a n d ，l o n gd i s t a n c e t e l e c o m m u n i c a t i o n sn e t w o r k ss w i t c ha n dl i n k su s a g er a t ei s a b o u t4 5 a n d 3 0 一4 0 r e s p e c t i v e l y i ti s e s t i m a t e dt h a tr a i s i n go n ep e r c e n to fs w i t c hr a t e o fc u r r e n tn e t w o r kw i l lr e s u l ti nr e v e n u ea l m o s to n eb i l l i o ny u a nr m b t h ec u r r e n td y n a m i cr o u t i n gs c h e m a ss a m p l ep a r a m e t e r sp e r i o d i c a l l y f o r c a l l a r r i v i n gr a n d o m l y ，t r a n s m i t t i n g a n d t r a n s a c t i n gb e i n g d e l a y e d ， d e c i s i o n m a k i n g i s l a g g e d b e h i n ds a m p l i n gi n s t a n td u r i n gt o t a ls a m p l i n g i n t e r v a lw h i c hr e s u l t si nt h e ya r eq u a s i - r e a lt i m e h e n c ed e c i s i o n sa c c u r a c y a n d f l e x i b i l i t y a r ei n f l u e n c e d m e a n w h i l e ，t h ea c c e p t e d c a l lh o l d sa n d o c c u p i e sr e s o u r c e i n t h e f u t u r e p e r i o do ft i m e t h e r e f o r e ，g o o dd e c i s i o n s h o u l dc o n s i d e rt h ei n f l u e n c et h ec a l lb e i n ge x e r t e da n dt h ec a l l t oe x e r t t h a ti st o s a y ，n e t w o r k s t a t et h ed e c i s i o nd e p e n d so ns h o u l dg ob e y o n d s a m p l i n gi n s t a n t ，i e t of o r e c a s t o nt h eb a s i co fd e m e r i t a n a l y s i so fr o u t i n gs c h e m e sb e i n gu s e d ，an e w i n t e l l i g e n tr o u t i n gs t r a t e g yb a s e d o n m u l t i a g e n ts y s t e m sa n d n e u r a ln e t w o r k f o r e c a s t i n gi sp r e s e n t e d t h er o u t i n gp r i n c i p l ei s t h a to nt h eb a s i co fp r e g r a s p i n gn e t w o r k1 0 a dt r e n d s ，i e p o s s i b l e1 0 a ds t a t eo f n e x ti n s t a n t ，1 0 a dc a n b eb a l a n c e di np a c ew i t ht h es w i t c hr a t ei n c r e a s e d t h ec a l l ss u c c e s sw i l ln o t i n f l u e n c et h es u c c e s s sp r o b a b i l i t yo fn e x tc a l l t h et e l e c o m m u n i c a t i o n sn e t w o r kb e i n gm a p p e di n t oam u l t i a g e n t ss y s t e m t h ea g e n ti ne a c hs w i t c ho ft e l e c o m m u n i c a t i o n sn e t w o r k sf o r e c a s t s1 i n k s l o a db e t w e e ni t s e l fa n di t sv i c i n i t yn o d e sa c c o r d i n gt oh i s t o r i c a ld a t a ( t i m e s e r i e s ) a n dc u r r e n t 1 0 a du s i n gt r a i n e dn e u r a ln e t w o r k t h ev i c i n i t yn o d e s s e n db a c kr e s p o n s e sa b o u tr e l a t i v el i n kw h e t h e rt h ec a l lc a nb ea c c e p t e d ( i n c l u d i n g l o a da n d s p a r e t r u n k si f a c c e p t e d ) b yc o m p a r i n g c u r r e n t f o r e c a s t e dl o a d sa n d1 0 a dt h r e s h o l d i fo n l yo n ev i c i n i t yn o d eg i v e sa c c e p t e dr e s p o n s e t h el i n ko ft h i sd i r e c t i o n w i l lb es e l e c t e d i fn oa n yv i c i n i t yn o d eg i v e sa c c e p t i n gr e s p o n s e ，t h ec a l l a t t e m p tw i l lb er e j e c t e d i fm o r et h a n o n ev i c i n i t yn o d e sg i v e a c c e p t e d r e s p o n s e s ，t h e n ： t h o s ew i t hh i g h e rl o a da n dl e s ss i c l a r et r u n k sw 订lb ei g n o r e d i ns o m ec a s e s w h e nt h e1 i n ki sh i g h l y1 0 a d e db u th a sm o r es p a r et r u n k s ，o rv i c ev e r s e ，l o w l y l o a d e db u th a sl e s ss i c i a r et r u n k s 1 0 a dw i l lb et h eo n l yr e f e r e n c e t h o s ew i t h h i g h e rl o a dw i l lb ei g n o r e d s i m u l a t i o nr e s u l t sd e m o n s t r a t e di t s o u t s t a n d i n gb yv i r t u eo fi t su p s t a n d i n g d i s t r i b u t i o na n di n t e l l i g e n c e h e n c ei tp r o v i d e se x c e l l e n ts o l u t i o nt oi m p r o v e n e t w o r ks w i t c hr a t ea n db a l a n c en e t w o r k1 0 a d k e yw o r d s ：r o u t es e l e c t i o n ，m u l t i a g e n ts y s t e m s ，f o r e c a s t i n g ，s w i t c h r a t e ，l o a db a l a n c i n g ，n e u r a ln e t w o r k ，s i m u l a t i o n ，r t n r ( r e a lt i m e n e t w o r k r o u t i n g ) 判天地之美 之理 庄子天下 人类乃万物之灵长，智能于人复杂而神秘，析其理虽如上“蜀 道”，却令人悠然神往；大地为人类怀抱，通信理念，系天地于一 体，其美当更为壮阔。 作者记 第一章电信网路由选择方法的演化 1 1 引言 第一章电信网路由选择方法的演化 路由选择是电信网将呼叫从源送达目的地的不可缺少的过程，属于网络管理的一 部分。网络管理包括性能管理和容量管理，前者要让性能指标在所有条件下得以满足 并达到最佳；后者保证网络设计性能指标以最小代价实现。性能通常具体指吞吐量和 平均延时，前者指在某一时间量下网络能提供的服务；后者涉及服务质量。吞吐量与 接通率是相关的，在任何情况下，电信网都要力图使呼叫失败的数量达到最小、接通 率最高，又尽量使负荷得以平衡。 路由选择常以路由最短、代价最低，或流量最大、拥塞最小为原则。驱动路由选 择技术发展的动力是性能质量的改善，新服务增加和技术进步 1 。性能质量的改善 来自于网络路由提高了对负荷变化和呼叫失败的自适应性和强健性。新服务增加来自 网络将动态路由和灵活的带宽分配扩展到网络的新业务中。当利用新的传输、交换和 管理技术以获得更简单、自动和有效的网络时，路由技术进化了。 目前，除层次或静态业务路由以外，动态以及无级业务路由也已逐步普及。在动 态路由方法中，分布法又以其通信和设施代价低、实时和灵活性能好而优于集中法。 在此基础上，进一步出现了基于分布式人工智能( 主要基于行为) 的新思路。 1 2 静态路由方法 过去的等级结构的通信网尤其是长信网，由路由表给出选择路由所需的信息。当 遇到宣达路由忙时，只能通过固定的迂回路由或最后通过基千路由逐级汇接，按顺序 进行选择，有可能经过多次转接。事实上，静态路由方法全依赖于由历史状况和业务 需求确定的路由表。路由表描述从源交换机到目的交换机的路由选择，服务于某种连 接需求，是路径的序列。路径是连接源和目的交换机的链路的序列。链路则连接两个 交换机。 路由表的控制以容量管理所提供的容量为前提，若需要，一周或实时调整路由表， 以改正服务问题。通常，从一个交换机到另一交换机的路径有多条。在网络结构已确 定的前提下，设计路由表是一个简单的优化问题。同时，网络路由规划与技术能力密 切相关。 a t & t 于1 9 3 0 年建立了交换中心的层次结构，它对“长途”呼叫的交换机数目 作了限制( 六个) ，路由功能由手工完成。4 0 年代后期建立了十个区域和五级层次结 构的交换系统：区域的( r e g i o n a l ) 、地区的( s e c t i o n a l ) 、基本的( p r i m a r y ) 、交换台 ( t 0 1 1 ) 和端户( e n d o f f i c e ) 。1 9 51 年，直接拨号d d d ( d i r e c td i s t a n c ed i a l i n g ) 与自动选择路由方式被引入，它使更新的需求减少。 当有级网发展时，计算机处在它的发展初期，路由设计规则也比较简单。有级业 务路由较好地为a t & t 服务了五十多年，现在还在广泛使用。事实上它是现在唯一 可以互连不同生产厂家交换机的标准。 基于多a g e n t 系统的智能路由资源分配策略 静态路由算法有最短路径路由、扩散( f l o o d i n g ) 路由( 向除入路以外的所有出路 转发) 、基于流量的路由( 既考虑拓扑结构又考虑负荷情况) 等 2 。这些方式不考虑当 前网络状态，不能适应网上业务量的变化，不能充分利用现有的网络资源，占用资源 又多，在网络结构发生变化的情况下更是无能为力。由于不能适应变化的条件，网络 要尽量设计成能适合某些过重负荷的情况，这无疑增加了物理设施的投资，又使系统 十分复杂。 于是人们开始考虑动态路由算法。1 9 8 0 年，有人开始用“马尔柯夫过程”和控 制理论研究网络忙闲状态，得出“呼损晟小与完成业务量最大等效”的结论 3 ，使 无级动态网的发展有了一个良好的开始。这里，“无级”指电信网中各交换机处于同 一等级，任意两个交换机均可组成“收发交换机对”。“动态”指路由的选择不是固定 的，而是随当时网络的情况变化。 动态路由方法与网络负荷平衡紧密相关，可通过利用网络空余能力而避免当前或 潜在的拥塞，并提高网络性能，如它的强健性和灵活性等。动态路由依赖于网络交换 机对用户业务不断测量、并不断计算网络状态和性能，它需要更多的处理资源。 1 3 基本动态路由方法 与层次结构的、时间固定的方法完全不同，动态路由通过增加呼叫在网络中可占 用的路数来提高接通的可能性，又不能影响其它呼叫的接通。动态路由的引入使网络 连接的有效性提高，同时降低了成本。动态路由可被应用到业务层( 电路交换网) 和交 叉连接层等不同层次或它们的结合，通过在失败路径附近重新选路来提高网络性能。 动态路由对非规划好和不可预见的业务情况是有效的，它根据可获得的业务条件，以 一定频率( 如一小时) 修改路由模式。研究表明，动态业务路由能降低l o 以上的成 本 4 。 有两类基本动态路由方法：时间依赖的和状态依赖的 5 7 。 时间依赖路由的基本思想是：针对每天不同时间段业务量不一样的事实，事先编 出按时间段区分的路由选择表。它可使话务量均衡，提高电路利用率。但本质上是根 据历史上的业务情况事先安排好的顺序。如a t & t 在1 9 8 4 1 9 8 7 年实现的动态无 级路由( d y n a m i cn o n h i e r a r e h i c a lr o u t i n g ，d n h r ) 。 状态依赖路由的基本思想是：根据网络当前状态信息决定选择哪条路由，它可避 开业务量大的链路，对于事先未能规划的业务变化有较好的适应性。它需要较大的管 理开销来交换信息，以更有效地优化网络资源的使用，可分为孤立的、集中的和分布 的三种，取决于当今网络状态的信息是如何获得的。 孤立法中，每个交换机仅有它自己的出路的状态信息。集中法中，一个中央网络 处理器周期地收集网络中所有链路的状态信息。分布法中，所有涉及的交换机对相互 通信以获得当今最好的可选路由。动态路由能有效响应来自时间域、季节等的负荷变 化；灵活性和有效性也得以提高。 第一章电信网路由选择方法的演化 1 3 1 孤立法 动态迂回路由( d y n a m i ca l t e r n a t i v er o u t i n g ，d a r ) 法【8 是一种孤立法，由 剑桥大学统计实验室和英国电信研究实验室联合设计于1 9 9 6 年用于英国电信网。它 的网络中每个交换机仅有它自己的出路的状态信息。d a r 首选直达路由，若遇该路 由忙，选当前可选的迂回路由：若仍不成功，本呼叫被阻塞，同时为下一呼叫选择好 新的迂回路由。该法简单，成本低，交换机间不需交换信息。但随机选择新的路由使 得盲目性大；另一不足是当前推荐可选路由的使用在发生阻塞之前并不改变。 1 3 2 集中法 动态控制路由( d y n a m i cc o n t r o l l e dr o u t i n g ，d c r ) 法是一种集中法，其概念由 c h a r l e sg r a n d j e a n 于1 9 6 7 年提出，加拿大电信和加拿大b e l l 于1 9 9 1 年将它首 先用于加拿大电信的计赞网络。它有一中央网络处理器周期地( 每1 0 秒) 收集网络中 各交换机的信息，如交换机利用率、中继线质量、空余链路、溢出和呼叫处理活动等 情况 9 。当直路被占时，根据其算法得出的负载最小的迂回路由被选中。 网络处理器对可选路由的选择取决于下式： m a x m i n x i k - k “，x k j - k k i 】) 假定最大值是正的，x ；i 是空余中继线数，k i i 的是保留的中继线门限值。它通过 扫描现有所有的两链路路由以发现最小负荷的可选路由来实现。 该法使业务在整个网络中分布，便于吸收不可预见的波动，可能减少阻塞和无益 的传输负荷，提高了系统接通率。但它需要分离的信号网络和计算中心，初始投资高， 通信开销大，负荷也相应增多。并且，目前在国际网中，集中式路由控制器的开发无 论在经济方面还是国家主权方面都是不合适的 1 0 】。 自适应控制路由( a d a p t i v ec o n t r o l i e dr o u t i n g ，a c r ) 与d c r 相似，只是时 间间隔要长：与固定路由( f i x e dr o u t i n g ，f r ) 相比，它利用当今的业务负荷而不是 历史业务负荷。 1 3 3 分布法 7 0 年代，网络技术朝程序控制方向发展。动态路由方法动态地修改路由表，如 预规划动态业务路由( p r e p l a n n e dd y n a m i ct r a f f i cr o u t i n g ，p p d t r ) ，或者是 实时动态业务路由( r e a l t i m ed y n a m i ct r a f f i cr o u t i n g ，r t d t r ) 。1 9 8 4 年a t & t 开发出了市际d n h r 。其时变路由表由网管中心预规划，每天改变十次。 典型的分布法是实时网络路由( r e a l t i m en e t w o r kr o u t i n g ，r t n r ) ，于1 9 9 1 年被引入a t t 交换网【1 1 。在没有直达路由时，它检查现有迂回路由及其负荷条 件，最小负荷路由被选择。负荷溢出级有六等：轻负荷l l l 、l l 2 、l l 3 ，重负荷 h l ，保留t r 和忙( b u s y ) 。每当“捕获”或“释放”一条链路上的中继线时，都要 计算一次负荷条件。如果链路上的中继线数超过某一门限，则被认为是轻负荷。选择 时，源交换机发消息给目的交换机，要求发回目的交换机认为具有轻负荷的链路，源 基于多a g e n t 系统的智能路由资源分配策略 交换机和目的交换机均认为是轻负荷的链路将被选中。选择时，对两端链路中的最大 负荷进行比较，找到最小的负荷等级，若超过规定的最大等级，则该呼叫被拒绝。选 择一个特定呼叫的路由时，始发交换机对具有相同负荷状态的路由位图列表进行循环 搜索，起始点紧跟着它上一次使用的到目的交换机的呼叫的交换机。这能减少呼叫建 立的延时。 这个方法的优点是减少了操作成本，因为减少了网络交换机中大量的路由表，减 少了网络设计和预测的路由表计算，减少了下载新路由信息等管理路由的操作，减少 了网络管理中自动重新选路由的开销，从而降低了阻塞程度。然而，由于信令信息交 互很多，增加了网络负荷。 此后，a t & t 于1 9 9 5 年部署了实时互联路由( r e a lt i m e i n t e r n e t w o r k r o u t i n g ，r t i r ) 。 i 3 4 集中与分布的合成 状态和时间依赖路由( s t a t ea n dt i m ed e p e n d e n c er o u t i n g ，s t d r ) 由n t t 于1 9 9 2 年引入动态路由网，以流最大为约束。其需求是最小化附加的处理需求和对 软件及操作系统的修改 1 2 。当某交换机对间出现呼叫阻塞时，该交换机对间的可选 路由要被修改。它有两级动态控制：时间依赖级和状态依赖级，分别使用集中控制和 分布控制。在无直达路由时，在路由域中以循环方式取可选路由。在基本方案中，不 成功的路由被另一可选路由替代。在此基础上的第一个改进是：有一门限，低于它的 呼叫仍被接受，但可选路由要被替换；第二个改进是从失败的可选路由开始，顺序扫 视路由域，以获得一个空的出发路由。如果发现一个空的出发路由，它将成为新的可 选路由，并为同一呼叫重试。只有在这样的情况下失败了，呼叫才最终失败，同时可 选路由被又一次替换。 这个方法自适应性较好。同集中法一样，分离的信令网和计算中心导致成本较高， 信息的管理开销很高。 除上述以外，还有法国电信在巴黎开发和测试的s t a r ( s y s t e m t ot e s t a d a p t i n gr o u t i n g ) ；贝尔研究所开发和测试的用于大城市局部交换承载网的d r 5 ； 一 a l c a t e l 在19 9 2 年提出的动态临时可选路由( d y n a m i ct e m p o r a r ya l t e r n a t i v e r o u t i n g ，d t a r ) ；若干国家于1 9 9 4 年合作而成的w i n ( w o r l d w i d e i n t e r n a t i o n a ln e t w o r k ) ，它是分布式实时周期状态依赖方法，等等。 1 3 5 计算机网 计算机网络，尤其是因特网中，路由选择方法主要涉及距离向量路由和链接 状态路由两个概念 13 】。距离向量路由方法是指，每个路由器维护一张到达目的地的 最佳距离表以及相应的路由，并通过邻结点间交互信息而不断更新。 由于距离向量路由方法未考虑带宽和收敛因素，于是有了链接状态路由，其思想 包括五部分： 发现邻结点并了解其网络地址 4 第一章电信网路由选择方法的演化 测量到达邻结点的延时和开销 构造一个包以告诉其它路由器它所掌握的内容 将包发给其它路由器 计算到其它路由器的最短路径 另外还包括用于移动主机的路由、广播路由、多址路由等。 当一个组织机构的网络只是几个相连的以太网时，选用基于距离向量的路由信息 协议( r o u t ei n f o r m a t i o np r o t o c o l ，r i p ) 或许已足够；当有多个组织机构网互联成 一个专业网或地区网时，就得选用基于链路状态的开放式最短路径优先协议( o p e n s h o r t e s tp a t h f i r s t ，o s p f ) 和内部网关路由协议( i n t e r n a lg a t e w a y r o u t e p r o t o c o l ，i g r p ：e n h a n c e di n t e r n a lg a t e w a yr o u t ep r o t o c 0 1 ，e i g r p ) ；而一 旦多个地区网互联成一个特大网时，选择一个合适的域问路由选择协议或域间路由策 略就是关键问题了 1 4 。 r i p 是“距离向量”协议族中最简单的一种，经典的有关算法由d i j k s t r a 于1 9 5 9 年提出。d i j k s t r a 的算法用图中边的权作为度量来计算最短路由。具有很少边数的 路径不一定是具有最小权的路径 i5 】。r i p 很简单，只有两种报文和一个列表，这是 其得到广泛应用的原因。然而，对于大而复杂的网络，它无法胜任，因为这时计算十 分缓慢；且在计算过程中，网络处于过渡状态，极可能产生循环并造成暂时的拥塞。 o s p f 是i e t f ( i n t e r n e te n g i n e e r i n gt a s kf o r c e ) 为因特网开发并推荐的。这里， 各个结点不必交换通往目的结点的距离，而只须维护一张网络图，在网络拓扑结构变 化时及时更新即可。由该图可计算出全部最佳路由。o s p f 比r i p 复杂得多，但效 率明显高于r i p 。 另外，i s o 在i p 上扩充制定了i s i s ( 中介系统一中介系统) 协议。因特网的发 展促使网络路由器业的诞生。著名的路由器生产商c i s c o 使用了i g r p ，它克服了 r i p 的某些缺陷，并且能在i e t f 完成其有关o s p f 工作之前就进入市场。 同时，o s p f 的组播路由扩充 1 6 动态组播路由算法 17 1 9 、域内路由 2 0 、 网络路由容错 2 1 】、路由死锁恢复 2 2 、波分复用中的路由问题 2 3 】，以及基于交换 的l a n w a n 结构中的收敛路由 2 4 等众多方面均有研究工作在进行。 1 4 基于行为的路由选择 1 4 1 基于移动a g e n t 的方法 网络可看作分布式人工智能，尤其是基于a g e n t + 的计算技术的一个自然的应用 领域。在主动网络 2 5 中，结点可以执行计算，处理可客户化到每个用户或每个应用； 网络的路由器或交换机基于经过它们的消息执行客户化的计算。携带数据的消息的概 念是传统电路和包交换的自然进步，并可使网络快速适应变化的需求。主动网络的研 究由技术“驱动”和用户“拉动”所刺激。前者来自移动代理( p r o x i e s ) 、多路由等： 在我国，a g e n t 一词尚无一致译法，有代理、实施体、主体、智能主体、智能体等，后者的使用较为广 泛。为免误解，本报告仍用原文“a g e n t ”。 基于多a g e n t 系统的智能路由资源分配策略 后者来自使我们的目标可到达的“主动”技术。 为了克服已有动态方法的不足，基于移动a g e n t 的电信网路由控制方法于1 9 9 4 年提出 2 6 ，但在实际实现方面尚不清晰。 由于路由问题依赖于集中存储的网络连接数据，动态的网络拓扑结构使其实现很 困难。用基于协同的移动a g e n t 来映象网络 2 7 ，当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 ：每次都随机移动到一个相邻结点； “负责”( c o n s c i e n t i o u s ) 的a g e n t ：每次依据第一手知识移动到从未访问或 最近最少访问的结点； 超责任性”( s u p e r c o n s c i e n t i o u s ) 的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 的行为的 差异性极为重要。 1 4 2 基于蚂蚁活动的方法研究 以往，人工智能在电信网管理中的应用，限于专家系统，如容错管理、性能管理、 配置管理、安全管理和记费管理等 2 8 。分布式人工智能中的人工生命研究可展现自 然生命系统的行为特征的人造系统，它为解决问题给出了新方向。生命的行为是动态 和不可预测的，有时甚至是混沌的，本质上是基于行为的、多层次的活动。为了解决 电信网的拥塞，基于蚂蚁取食的过程被建模和研究 2 9 31 1 ，该模型可表示结点间呼 叫的分布，又不需复杂的概率计算。 昆虫系统具有突出的强健性，并能达到适当的平衡。作为一个群体，蚂蚁设法以 极大的可靠性和灵活性执行大量复杂的任务，其行为来自大量蚂蚁间和蚂蚁与环境的 交互。典型地，蚂蚁产生特定的活动作为对特定的局部环境刺激的反应。 6 第一章电信网路由选择方法的演化 由此可得出：可能用简单的、没有或很少有记忆或计算能力的蚂蚁a g e n t ，通过 与其它a g e n t 在环境中留下的痕迹进行交互，在许多计算活动中到达平衡。 假设信网结点间的连接有无限能力，结点容量是唯一瓶颈。 人工蚂蚁在随机选择的结点对间移动，并留下某种痕迹( p h e r o m o n e ) ，这种痕迹 是它离源结点距离和途中所遇拥塞程度的函数。它们按照在每个结点所模仿的痕迹的 分布选择路由。结点间呼叫的路由是每个中间结点的痕迹分布的函数。在此基础上修 改路由表。蚂蚁存活时间和延迟因素也被考虑。另外，直接更新概率不同于“留下” 痕迹，但功能等价。 初始呼口q 概率是随机选择的，然后随机产生呼叫，使用随机的呼叫长度。系统是 动态和随机的。这里可能出现两个问题： 阻塞( b l o c k i n g ) ，即以前发现的路由不复存在； 捷径( s h o r t c u t ) ，即突然出现一条新的、较短的路由。 系统的目的是：路由表应该有效地组合网络拓扑和呼叫分布统计信息，路由经过 的结点较少，而且尽量避开拥塞的结点。 由于蚂蚁的随机活动有可能使它们经历整个环境，这同时影响了效率。为此，给 出一个概率，让蚂蚁在一个范围内作随机活动。 有三种可能的不同形式的自适应： 自适应到网络拓扑； 自适应到在给定网络拓扑内的呼叫统计： 自适应到由呼叫模式的随机性产生的暂时情形。 仿真结果显示，基于蚂蚁的控制( a n t b a s e dc o n t r o l ，a b c ) 有比其它方法好的 地方。 现在的问题是： 是否能用于实际网络； 是否能解决现有问题； 是否比现有算法好： 是否在a g e n t 失败的情况下还具有强健性； 以及，仿真中蚂蚁数量的影响； 和对特大或特小的网络的性能影响。 在基于蚂蚁王国的算法中【3 2 】，群前向人工蚂蚁在网络中移动，它们寻找解并 通过添加收集到的信息( 有关路径的时间长度，网络的负荷状态) 来修改问题表达。有 关信息被另一在相反方向上移动的蚂蚁反传并用来修改访问过的结点的路由表。 结果表明：如果蚂蚁出发率太大，蚂蚁间的交互会引起振荡并降低性能；系统对 网络资源的影响可以忽略；其路由决策仅依赖于当前和今后网络状态的局部和近似信 息是一个严重不足。 而后，在此基础上的“动态规则”算法得以提出 3 3 ，并有了相对更好的结果。 其局限性是模型网络很简单，且往往是全连接的。 近来的研究表明，白组织是大量社会昆虫的集体行为的一个主要内容。有人利用 基于蚂蚁的优化原则，解旅行商问题等经典问题，并与模拟退火方法相比较。也有人 7 基于多a g e n t 系统的智能路由资源分配策略 将其用于地图着色问题等。但基于蚂蚁的路由方法可能是唯一被充分考虑的利用昆虫 的分布式功能的优点的例子。 1 4 3 基于市场的方法 路由资源分配和业务拥塞控制问题在其它电信领域，如移动通信网无线接入的带 宽、智能网业务交换点间的负荷平衡和a t m 网的带宽资源分配 3 4 3 6 】等方面都存 在，它们对动态路由也提出了更高的要求。 随着电信的发展，如在a t m 中，电信提供者会租出一些专用资源，一个电信网 也会由多个拥有者所拥有。每一方会根据自身的利益需求采取相应的策略，从而影响 网络的全局性能。这导致网络资源使用上的非协同情景。面对这样的情况，市场经济 中的拍卖过程被借鉴 3 7 。在市场中。有呼叫a g e n t 、链路a g e n t 、路由a g e n t 和 链路市场、路由市场等，它们有不同的利益，对外部环境具有有限信息，由不同实体 拥有，代表不同的网络资源。它们一起对网络资源进行分配，但没有预定的协同机制， 即协同是得不到保证的。实验表明，与静态路由方法相比，这个思路在网络过负荷情 况下是有益的，即竞争压力和市场效率的要求有益于解决网络中的负荷不平衡问题。 这个思路可能对整个网络管理都是有启发的。只是整个工作尚处于初始阶段。 a t m 中信元的传输开销是对网络带宽要求的函数。事实上，网络必须在接受众 多服务和回绝许多请求间维持一种平衡。在a t m 这种高度动态的系统中，全局信息 很可能过时，基于这样的信息作决策也许比没有控制更坏。局部控制可以根据随时到 达的信息迅速作决策，但是这种方式缺乏全局观点。 而建立新路由的前提是不影响现有呼叫的q o s ，又保证新呼叫所要求的0 0 s 。 多a g e n t 系统可通过结合局部决策和某种程度对全局信息的共享来提高决策的有效 性。例如，平时，用户可告诉系统暂时对音频视频的带宽不太关注，直到监视带宽 的a g e n t 收到用户要求改变对音频视频的带宽要求的消息，a g e n t 就会调整相应的 带宽 3 8 。 ， 此外，为了有效管理a t m 网中可进行虚拟路径连接的路由资源( 带宽资源) ，一 种层次结构的控制系统被提出 3 9 。它分为控制平面和管理平面。前者中的a g e n t 分别负责流控制、连接管理等，后者中的a g e n t 分别负责计费、连接服务质量等。 前者不依赖于同后者的交流。 还有一种思路是，网络各结点构成一棵树，结点间链路上的权表示现有的带宽资 源。每个结点是一个a g e n t 4 0 。每个a g e n t 有独立决策能力，叉相互协作解决冲 突。若干a g e n t 组成一个“岛”。在此基础上形成父子关系。从上往下的层次上父子 分别负责不同的带宽资源，如0 ，1 9 2 k 和6 4 k 。对一定带宽资源的需求，从“子” 到“父”经过消息传递和计算，可得到一个适当的路由。 1 4 4 模糊方法 除上述借助a g e n t 概念的方法夕 ，模糊方法也被考虑 4 1 】。般的业务路由通 过跟踪和利用网络中空余容量来提供用户所需的服务质量，降低成本，并实现灵活性、 第一章电信网路由选择方法的演化 有效性、强健性，以及网络业务管理可扩展的路由控制。已有路由方法往往利用现有 的网络状态获得的概率模型，这主要源于业务特征的随机特性。因而，相应的模糊控 制方法出现了。由基于模糊逻辑的推理而链接的规则进行路由选择，规则来源于业务 工程师和网络管理员等。与r t n r 不同，不同级的界限不是精确的，而是一个范围。 此外，b i s d n 中的模糊多目标路由模型也被研究。 1 5 我国在路由选择方面的工作 国内，信息产业部电信规划研究院 4 2 和信息产业部电信科学技术研究院 4 3 分 别对已有动态无级网进行了模拟研究，目前，信息产业部电信规划研究院和中国电信 总局正在一起推动实施固定无级路由选择方法。北京邮电大学探讨在路由选择方面使 用神经网络和模糊理论【4 4 】，前者考虑优化；后者除接通率本身外，还考虑话音质量， 如杂音、响度损耗、可懂串音和衰减失真等。此外广东省电信局联合中山大学多年， 进行路由选择方面的改进工作。 事实上，除经典长途电信网外，我国智能网 4 5 】业务也在不断增加和完善，同样 对路由选择提出了要求。 智能网是在现有交换和网络传输网络结构上，为方便、经济地增加新业务和新功 能而考虑的一种附加网络层次和结构。它基于将网络中基本的交换传输功能和对业务 的控制功能分离的思想，对业务集中控制，由“叠加”的网络层实现，是开放的、分 布的、与服务无关的通信网服务控制体系结构。 智能网由上而下可分成四个平面，分别代表从不同角度对智能网的描述： 服务层：向用户表明一个智能网具有的业务能力。 。全局功能层：面向服务设计者。 分布功能层：面向系统开发人员，在此，智能网被看作由若干功能实体组成的 网络。 物理层：物理实现层，上层每个功能实体都要映射到该层。 物理层包括网络接入点、服务交换点( s e r v i c es w i t c h i n gp o i n t ) 、服务控制点 ( s e r v i c ec o n t r o lp o i n t ) 、服务数据点、智能外设，以及可能的服务交换和控制点、 附属设备和服务结点等。 s s p 提供服务交换功能、连接控制功能等，并向其它网络组件提供信令和承载接 口。它包含着检测请求网络服务的检测能力和呼叫控制代理功能。此外，一个s s p 还可包含一个专用资源功能( s r f ) 。s s p 有一套标准函数可以被s c p 激活。 智能网的资源分配策略，一方面要限制或减少向s c p 传的请求，另一方面要使 负荷在s s p 间求得一种平衡。其目的是既要防止过载，又要有最大的业务量。所以， 考虑由s s p 作决策是一个合理的思路。若某一s s p 资源不足，则可以将呼叫引向其 它可能还有资源的s s p 。它将导致接通率的提高。 1 6 问题分析 基于多a g e n t 系统的智能路由资源分配策略 考虑路由方法，根本原则是接通率以及负荷平衡情况。同时要关注降低成本，便 于管理，以及自适应性；还要考虑到网络结构和对容量的约束条件变化时的灵活性。 人们提出的、但未投入使用方法有不少，各有侧重，如高速网中几个有关低呼损的算 法 4 6 】的比较。 负荷平衡的目的是构造一种呼叫路由，它能将变化的负荷成功地分配到系统的各 相应部分，并使呼叫失败的情况减到最少。它不一定着眼于努力使每一次呼叫都成功， 但应能尽量在全局范围内和大多数情况下，获得更好的性能。它不一定要最短路由， 甚至可以容忍一定程度的局部拥塞，最终目的是要实现全网高接通率和负荷的良好分 布。强健的路由选择方法要防止交换失败、传输失败和接入失败。 在网络性能、成本、交换处理器和信令网的负荷及与其它网络级的接口等方面， 基本动态路由方法各有优劣。 动态层次路由和固定无级路由较弱。状态依赖路由可每个呼叫或每几秒更改一次 路由模式，比事件依赖r t d t r 有效。各d n h r 间的差别较小，原因在于它们的首 选和可选的二链路第一路由是一样的。 集中法的控制器需要当今系统的有关信息，每个结点都要与控制器相连使通信开 销增加；控制器坏掉，会导致整个系统不能工作；扩缩性差；系统响应决定于控制器 的负荷和有关结点与控制器间的