（计算机应用技术专业论文）适应动态拓扑网络的多agent计算关键技术研究.pdf

复旦大学博士学位论文 适应动态拓扑网络的多a g c ，a t 计算关键技术研究 y7 6 9 7 0 1 适应动态拓扑网络的多a g e n t 计算 关键技术研究 r e s e a r c ho nt h ek e yt e c h n 0 1 0 9 i e so f m u l t i a g e n tc o m p u t i n gf o rd y n a m i c t o p o l o g yn e t w o r k s 指导小组成员：张世永 曹文君 钟亦平 吴承荣 杨明 教授 教授 副教授 副教授 副教授 复旦大学博士学位论文 摘要 摘要 关键字：墨g 堕；麴查翅盐圆堑! g 觑盒往董垃逦i 地照堕篮；g 塑! 适整i g 照叠 煎；g 熊信廷；g 垡运庭拯劐： 当今，多a g e n t 计算在分布式人工智能研究中起着越来越重要的作用。在多a g e n t 系统 中，a g e n t s 之间可以协作计算从而完成工作任务。在多a g e n t 计算的研究中，有四种关键技 术需要认真解决：a g e n t 台作与协调，a g e n t 2 通信，a g e n t 3 王_ 移，a g e n t 信任与安全。 在目前的多a g e n t 系统中，网络经常动态变化，特别是网络的拓扑结构在运行中经常 改变，这就是所谓的网络拓扑结构动态性。动态拓扑网络是目前的网络的一个新的主要特 征，在现今的一些网络中都会呈现出动态拓扑的特征譬如a dh o c 网络、社会网络、通信 网络、复杂网络等等。网络拓扑结构的动态变化有许多原因，譬如为了某种目的而实行结 点的移动从而保持互联等。动态拓扑网络的主要特征就是链路或者网络组件的动态变化。 这些链路可能是物理链路也可能是不同组件间的逻辑链路。但令人遗憾的是，目前并没有 关于动态拓扑网络中的多a g e n t 计算的系统性的相关研究。 针对上述情况，为了使多a g e n t 计算适应动态拓扑网络，本论文主要研究了以下一些 关键技术：a g e n t 合作与协调、通信、迁移、容错、信任等。研究内容分为以下5 个部分： 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 协作可以获得对动态网络拓扑结构的适应性， 在论文中的事例与性能分析中也得到了验证。 2 基于图论构造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 黑板通倍结构的模型。该模型基于图 论中的“中位点方法”计算中心黑板或者分布式子黑板在当前网络拓扑中的位置，基于图 论中的“s t e i n e r 树方法”计算各个分布式子黑板之间的通信拓扑；该模型还利用图论建 立了黑板结构对动态网络拓扑的适应机制，并且实现了黑板结构的容错性。最后，论文针 4 复旦大学博士学位论文 摘要 对该模型进行了事例学习以及测试，结果证明该模型可以产生适合当前网络拓扑结构的有 效的a g e n t 黑板通信结构。 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 n t 运行的网络拓扑结构或者a g e n t s 合作通 信拓扑关系动态变化的情况，提出了a g e n t 分布式黑板通信结构的动态自适应机制。当网 络的拓扑结构或者a g e n t s 合作通信拓扑关系发生变化时，该机制可以计算当前的a g e n t s 通 信拓扑图及其支撑树，并根据新的通信拓扑图或支撑树重新调整a g e n t 分布式黑板通信结 构：各a g e n t 根据调整后的通信结构进行有效地通信，从而适应动态环境的要求。最后， 本文采用a m b i e n t 演算对该机制进行了分析验证，结果证明机制是正确可行的。 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 。但是，这两个问题在早期的相关研究中经常被忽视。针对这种情 况，本部分对其进行了深入研究，我们的研究工作主要分为三块：1 ) 首先基于蚁群算法提 出了动态拓扑网络环境中的a g e n t 单跳( s i n g l eh o p ) 迁移策略，然后根据概率论中的 m a r k o v 随机过程提出了a g e n t 多跳( m u r i - h o p s ) 迁移策略；2 ) 为了解决a g e n t 在迁移过 程中所遇到的恶意主机问题，本章提出了一种新的基于完整性检测的a g e n t 容错模型 a m f i v ，该模型可以有效地解决当前的关于a g e n t 完整性检测与容错两个方面的相关研究 工作的典型弊端；3 ) 最后。本章以动态网络安全系统为例子，提出了一种动态网络环境中 的复合型迁移容错思想c a m f s ，并通过与其他相关研究工作的比较阐述了该思想的优点。 5 基于圈论方法的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 的信任关系。测试结果证实了我们 所提出的模型要优于分布式信任机制。 5 垄兰里苎塑堂些笙兰 垫蔓 综上所述，本文提出了“动态拓扑网络环境中的多a g e n t s 计算这一新的课题，并通 过以上五个部分对该课题中的关键技术进行了深入而系统的研究，提出了一整套适用于动 态拓扑环境并且可以根据网络拓扑结构的变化而实行自适应调整的全面的多a g e n t s 计算综 合理论模型和框架。 6 复q 大学博士学位论文 a b s t r a c t a b s t r a c t t i t l e ：r e s e a r c ho nt h ek e yt e c h n o l o g i e so fm u l t i - a g e n tc o m p u t i n gf o rd y n a m i ct o p o l o g y n e t w o r k s k e y w o r d s ：m u l t i - a g e n t s ；d y n a m i ct o p o l o g yn e t w o r k s ；a g e n tc o o p e r a t i o na n dn e g o t i a t i o n ；a g e n t c o m m u n i c a t i o n ；a g e n tm i g r a t i o n ；a g e n tf a u l t - t o l e r e n c e ；a g e n tt r u s t ；a g e n ta d a p t i v em e c h a n i s m n o w a d a y s ，m u l t i a g e n tc o m p u t i n gp l a y s ac r i t i c a lr o l em o r ea n dm o r ei nt h er e s e a r c ho f d i s t r i b u t e da r t i f i c i a li n t e l l i g e n c e i nm u l t i - a g e n ts y s t e m s ，m u l t i - a g e n t sc a r lc o o p e r a t et op e r f o r mt h e a s s i g n e dt a s k i nt h er e s e a r c ho f m u l t i - a g e n tc o m p u t i n g ，t h e r ea r ef o u rt e c h n o l o g i e st h a ts h o u l db e s o l v e dw e l l ：a g e n tc o o p e r a t i o na n dc o o r d i n a t i o n ，a g e n tc o m m u n i c a t i o n ，a g e n tm i g r a t i o n ，a g e n t t r u a ta n ds e c u r i t y i nn o wm u l t i - a g e n ts y s t e m s ，t h eu n d e r l y i n gn e t w o r k sa r ea l w a y sd y n a m i ca n dt h en e t w o r k t o p o l o g i e sa r ea l w a y sc h a n g e di nt h eo p e r a t i o n w h i c hc a nb ec a l l e dn e t w o r kt o p o l o g yd y a n m i c i t y d y n a m i cn e t w o r kt o p o l o g ym o d i f i c a t i o n s8 r ee s s e n t i a lf o rm a n yr e a s o n s ，e g t om a i n t a i n a c o n n e c t i o nd u et on o d em o b i l i t y d y n a m i ct o p o l o g yn e t w o r k sa r ec h a r a c t e r i z e db yt h ed y n a m i c i t y o ft h el i n k so fd i f f e r e n tn e t w o r kc o m p o n e n t s t h el i n k sc o u l db ep h y s i c a lc o n n e c t i o n so rl o g i c a l l i n k so ft h ed i f f e r e n tc o m p o n e n t s t h e s en e t w o r k sa s eo r g a n i z e dt o g e t h e rt oa c c o m p l i s hc e r t a i n t a g k s t om a k em u l t i - a g e n tc o m p u t i n ga d a p tf o rt h ed y n a m i ct o p o l o g yn e t w o r k s ，t h i sd i s s e r t a t i o n e x p l o r e st h ek e yt e c h n o l o g i e so f m u l t i - a g e n t si nd y n a m i ct o p o l o g yn e t w o r k s u c ha sc o o p e r a t i o n c o o r d i n a t i o n , c o m m u n i c a t i o n , m i g r a t i o na n df a u l tt o l e r a n c e ，t r u s t ，e t c t h i sd i s s e r t a t i o nm a i n l y i n c l u d e st h ef o l l o w i n gf i v ep a r t s 1 t h ea g e n tc o o p e r a t i o na n dn e g o t i a t i o nm o d e lf o rt h ev a r i a t i o no fu n d e r l y i n gn e t w o r k t o p o l o g y a i m i n ga tt h ed y n a m i c so fu n d e r l y i n gn e t w o r kt o p o l o g yv a r i 抓o na n dt h ea g e n td i s t r i b u t i o n a n o v e la d a p t i v em l l l t i - a g e n t sc o o r d i n a t i o nm o d e li se x p l o r e di nt h i sp a r t i nt h i sp a r t , as e r i e so f a l g o r i t h m sf o rm u l t i - a g e n tt a s ka n dr e s o u r o en e g o t i a t i o nf b a s e do ng a m et h e o r ya n dm a t r i x ) a l e p r o v i d e d 1 1 l ep r o v i d e da l g o r i t h m sc o n s i d e rt h ef a c t o r so f n e t w o r kt o p o l o g ya n da g e n td i s t r i b u t i o n a n dc a ni m p l e m n n te f f e c t i v et a s ka l l o c a t i o na n dr e s o u r c en e g o t i a t i o nf o rc u r r e n tn e t w o 嫩t o p o l o g y t h e r e f o r e t h ea d a p t a t i o no fa g e n tc o o r d i n a t i o nf o rd y n a m i cu n d e r l y i n gn e t w o r kt o p o l o g yc a nb e a c h i e y e d w h i c hi sa l s op r o v e db yt h ec a s es t u d i e sa n dp e r f o r m a n c ea n a l y s e si nt h ed i s s e r t a t i o n 2 t h ec o n s t r u c t i o no f a g e n tc o m m u n i c a t i o na r c h r e e t u r eb a s e do ng r a p ht h e o r y b l a e k b o a r da r c h i t e c t u r ei so n eo ft h ep o p u l a ra g e n tc o m m u n i c a t i o nm e c h a n i s m s ，w h e r ea g e n t s d o n ti n t e r a c tw i t he a c ho t h e rd i r e c t l yb u tt h r o u g hb l a c k b o a r d t h eb l a c k b o a r da r c h i t e c t u r e i n c l u d e sc e n t r a if a s h i o ne n dd i s t r i b u t e do n e i nb l a c k b o a r dc o m m u n i c a t i o na r c h i t e c t u r e t h e l o c a t i o no fc e n t r a lb l a c k b o a r d ( o rd i s t r i b u t e ds u b - b l a c k b o a r d s ) a n dc o m m t m i c a t i o nt o p o l o g y a m o n gs u b b l a c k b o a r d sa r et w oi m p o r t n n ti s s u e st h a tc a l li n f l u e n c et h ea g e n tc o m m u n i c a t i o n p e r f o r m a n c ev e r ym u c h h o w e v e r , t h e r ea r ef e ww o r k sa b o u ts u c hi s s u e s ；a n di nt h ee x i s t i n ga g e n t s y s t e m s t h ec e n t r a lb l a c k b o a r d ( o rd i s t r i b u t e ds u b - b l a e k b o a r d s ) i s ( o ra r e ) u s u a l l yr a n d o m l y i o c a t e di nt h et m d e r l y i n gn a t w o r k t os o l v es u c hp r o b l e m t h i sp a p e rp r e s e n t sam o d e lf o r c o n s t r u c t i n ga g e n tb l a c k b o a r dc o n u n u n i c a t i o na r c h i t e e a a eb a s e do ng r a p ht h e o r y t h em o d e l c o m p u t e st h el o c a t i o no f c e n t r a ib l a c k b o a r do rs u b - b l a c k b o a r d sb a s e do nm e d i a nl o c a t i o nm e t h o 吐 7 复旦大学博士学位论文 a b s t r a c t a n dc o m p u t e st h ec o m m u n i c a t i o nt o p o l o g ya m o n gs u b - b l a c k b o a r d sb a s c do ns t e i n n e rt r e e m e t h o d ；t h em o d e la l s oa p p l i e sg r a p ht h e o r yt ot h ec o n s t r u c t i o no fb l a c k b o a r da r c h i t e c t u r e s a d a p t a t i o nm e c h a n i s mf o rd y n a m i ct o p o i o g ya n dt h er e a l i z a t i o no ft h eb l a c k b o a r da r c h i t e c t u r e s f a u l t t o l e r a n c ea b i l i t y a tl a s t , s e v e r a ic a s es t u d i e sa n ds i m u l a t i o ne x p e r i m e n t sa r ec o n d u c t e d w h i c hp r o v et h a tt h ep r e s e n t e dm o d e lc a nc o n s t r u c tt 1 1 ee f f e c f i v ea g e n tb l a c k b o a r dc o m m u n i c a t i o n a r c h i t e c t u r ef o rt h en e t w o r kt o p o l o g y 3 t h ea d a p t i v ea d j u s t i n gm e c h a n i s mo fa g e n tc o m m u n i c a t i o na r c h i t e c t u r ef o rt h ec h a n g e o f n e t w o r kt o p o l o g y d i s t r i b u t e db l a c k b o a r di so n eo ft h ep o p u l a ra g e n tc o m m u n i c a t i o na r c h i t e c t u r e s h o w e v e r , i n c u r r e n ta g e n ts y s t e m s t l l ed i s t r i b u t e db l a c k b o a r da r c h i t e c t m i sk e p tf i x e da f t e ri t si n i t i a ls e t t i n g , w h i c hm a yi n f l u e n c et h es y s t e mp e r f o r m a n c ew h e nn e t w o r kt o p o l o g yo ra g e n tc o o p e r a t i o n r e l a t i o n sa r ec h a n g e dd u r i n go p e r a t i o n t os o l v et h ep r o b l e m ，t h i sp a r tp r e s e n t san o v e lm e c h a n i s m f o ra d j u s t i n ga g e n tc o m m u n i c a t i o na r c h i t e c t u r e b a s e d0 ng r a p ht h e o r y , t h i sm e c h a n i s mp r o v i d e sa w a y t oa d j u s tt h ed i s t r i b u t e db l a c k b o a r da r c h i t e c t u r e n ma d j u s t m e n tm a d et ot h ea r c h i t e c t u r ek e p t i t sv a l i d i t y , a n dt h ea d j u s t e da r c h i t e c t u r eo u t p e r f o r m st h ei n i t i a lo n ei nn e wn e t w o r kt o p o l o g yo r a g e n t sc o o p e r a t i o nr e l a t i o n s w h i c h 眦p r o v e db yt h em o b i l ea m b i e n t sc a l c u l u sa n a l y s e sa n dt h e s i m u l a t i n ne x p e r i m e n t s t h e r e f o r e t h ea d j u s t i n gm e c h a n i s mp r e s e n t e dh e r ec a r la c h i e v et h e a d a p t a t i o no ft h ea g e n tc o m m u n i c a t i o na r c h i t e c t u r et ot h ec h a n g e so ft h en e t w o r kt o p o l o g ya n d a g e n tc o o p e r a t i o nr e l a t i o n s 4 t h ea g e n tm 堙r a t i o na n df a u l t - t o l e r a n t * m o d e li nd y n a m i c t o p o l o g yn e t w o r k i nt h ed y n a m i ct o p o l o g yn e t w o r k s ，t h ec h a n g eo f n e t w o r kl i n k sm a yi n f l u e n c et h ea g e n tm i g r a t i o n ； o t h e r w i s e ，t h ed y n a m i c i t yo fn e t w o r kt o p o l o g ym a yi n t r o d u c es o m em a l i c i o u sh o s t sw h i c hm a y c o n t a m i n a t et h em o b i l ea g e n t s t h e r e f o r e ，t h ea g e n tm i g r a t i o na n df a u l t - t o l e r a n c em a n a g e m e n ti sa c r i t i c a li s s u e h o w e v e r , t h ei s s u eh a sa l s oa l w a y sb e e nn e g l e c t e di ne a t l yr e l a t i v ew o r k s a i m i n ga t s u c hp r o b l e m ，t h i sp a r tm a k e sr e s e a r c ha b o u ti t , w h i c hi n c h i d e st h r e es u b - p a r t s ：f i r s t l y , t h eo n e - h o p m i g r a t i o ns t r a t e g yo f a g e n ti sp r e s e n t e db a s e do na n ta l g o r i t h m s ；a n dan o v e la g e n tf a u l t - t o l e r a n c e m i g r a t i o nm e c h a n i s mr e a l i z e db yh a t e 鲥t yv e r i f i c a t i o n ( a m f i va n dp - a m f i v ) i sp r e s e n t e d ；t h e n ac o m b i n e da g e n tm i g r a t i o n f a u l t - t o l e r a n c es t r a t e g y 化a m f s ) i sp r e s e n t e da c c o r d i n gt ot h e a g e n tc h a r a c t e r i s t i ci nd y n m n i cn e t w o r ks y s t e m a tl a s t ，t h ea d v a n t a g eo fc a m f s i sd i s c u s s e db y c o m p a r i s o nw i t ho t h e rr e l a t i v ew o r k s 5 t h ea g e n ta u t o n o m o u st r u s tm o d e lb u s e do ng r a p ht h e o r ym e t h o d o l o g y t m s tm e c h a n i s ma l w a y sh a st w op o p u l a ra r c h i t e c t u r e s ：c e n t r a l i z e df a s h i o na n dd i s t r i b u t e df a s h i o n h o w e v e r , t h o s et w oa r c h i t e c t u r e sa r en o tw e l ls u i t e df o rm u l t ia g e n ts y s t e ms i n c et h e yc a n t a c h i e v et h et r u s tm a n a g e m e n ta u t o n o m yi i lt h ed y n a m i ct o p o l o g yn e t w o r k s t oa c h i e v et h et r u s t m a n a g e m e n ta u t o n o m y , t h i sp a r tp r e s e n t s 蚰a u t o n o m o u st r u s tc o n s t r u c t i o nm o d e lb a s e do ng r a p h t h e o r ym e t h o d o l o g y n 撼p r e s e n t e dm o d e la d o p t st h eg r a p ht od e s c r i b et h et r u s ti n f o r m a t i o n ，a n d u s e st h eg r a p hc o m b i n a t i o na n dp a t hs e a r c h i n gt oc o n s t r u c tt h et r u s tr e l a t i o n e v e r ya g e n tc a n i m p l e m e n tt r u s tm a n a g e m e n ta u t o n o m o u s l y ；a g e n ts y s t e mc a l lc o n s t r u c tt h eg l o b a lt r u s tc o t l c e p t b yt h ec o m b i n a t i o no f t r u s ti n f o r m a t i o na m o n ga g e n t s ；a na g e n tc a r la c h i e v et h et r u s tr e l a t i o nw i t h o t h e ra g e n tb yt n j s tp a t hs e a r c h i n go rt r u s tn e g o t i a t i o n n ms i m u l a t i o ne x p e r i m e n tr e s u l t sp r o v e t h a tt h ea u t o n o m o u st r u s tc o n s u u c t i o nb a s e do ng r a p ht h e o r ym e t h o d o l o g yi se f f e c t i v e t h e r e f o r e ，f r o ma b o v e5p a r t s ，w ec a na c h i e v ea l li n t e g r a t e df r a m e w o r kf o rt h em u l t i a g e n t c o m p u t i n gw h i c hc a l lb ea p p l i e di nt h ed y n a m i ct o p o l o g yn e t w o r k sa n dc a l lb ea d j u s t e da c c o r d i n g t ot h ev a r i a t i o no f n e t w o r kt o p o l o g y 8 复旦大学博士学位论文第一章绪论 第一章绪论 摘要：多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 1 引言 分布式人工智能( d a i ：d i s t r i b u t e da r t i f i c i a li n t e l l i g e n c e ) 是人工智能研究领域的一个 重要分支，它是人工智能和分布式计算有效结合的结果。d a l 主要研究多a g e n t 计算中的 知识、行为、合作、通信和组织等，也就是研究在各种环境下如何协调各a g e n t 的行为， 让各个a g e n t 最有效地发挥自己的功能，从而有效地利用资源获得最终的目标。 自治a g e n t 是具有自治性、具有独立处理问题能力、可以在不需要人为干预的情况下 独立自主地完成工作任务的能力的计算实体。a g e m 技术在计算机领域的研究和应用源于 2 0 世纪7 0 年代美国m i t 研究人员开展的一系列关于分布式人工智能的研究。m i t 的研究 人员在对信息系统处理复杂问题的能力进行分析时发现，通过协作将一些简单的信息系统 组成一个大的系统可以显著提高系统处理复杂问题的能力，并且通过定义合理的协作机制 可以提高整体系统的智能水平。1 9 7 7 年，h e w i t t 提出了一个a c t o r 模型：将a c t o r 定义为一 个封装了地址和行为的计算a g e n t ，通过消息传递进行通信并且并发地执行行为动作“。 2 0 世纪9 0 年代以来，随着计算机网络和通信等技术的发展，对于多a g e n t 计算的研究 不仅成为分布式人工智能的一个热点，而且也是计算机网络通信技术领域关注的一个方 面。网络技术的日益成熟和广泛的应用，为系统高可靠性的要求及信息处理速度的日益加 快提供了广阔的系统平台，也为分布式人工智能技术在理论研究上提出了新的要求和方 向。移动a g e n t 就是多a g e n t 计算在计算机网络发展上的一个新方向。移动a g e n t 的概念是 2 0 世纪9 0 年代初由g e n e r a lm a g i c 公司在推出商业系统t e l e s e r i p t 时提出的。移动a g e n t 能 够在网络中自主地从一台主机迁移到另外一台主机，在迁移过程中可以进行数据搜集或者 执行行为动作，并可与其他a g e n t 或周围的环境资源( 譬如主机、设备、网络等) 进行交 互。 目前的各种计算机网络通信系统往往是异构的，其中存在各种类型与性质的子系统。 在这种异构性的计算机网络通信系统中，需要实现异构的软、硬件环境中进行异地资源共 享、远程相互合作通信、异步相互操作等功能。这些功能的完成需要大量的不同种类的 a g e n t s 分工合作相互协调才能实现。在计算机网络蓬勃发展的背景下，计算已经不再像以 前那样仅仅局限于菜一个网络或者某几个网络中的几台服务器上，而是要求所有计算机都 9 复旦大学博士学位论文第一章绪论 融入到分布式计算这一大环境中来，这就引发了分布式计算新一轮的研究热潮，譬如目前 的网格研究就是一个新的热点，在网格研究中多a g e n t 计算就为其提供了一种新的计算和 问题求解方法。 当前，计算机网络的发展呈现出一个新的特点，那就是网络的动态性。在动态网络 中，网络的体系结构、设备、结点之间的关系和应用是复杂多变的，随着越来越多的移动 设备和相关应用不断加入传统的网络中，网络的动态性和不可确定性大大提高。在动态网 络中，最常见的就是网络拓扑的动态变化。在网络的运行中，拓扑结构经常变化，不断有 新的结点加入或者现有的结点退出，还有结点之间的联接关系也会发生改变。结点之间的 联接的改变既包括物理的改变也包括逻辑的改变。目前所研究的a d - h o c 网络与s e n s o r 网络 其实就是一种典型的动态拓扑网络。另外，当前的传统网络的拓扑结构也是经常变化的。 由于网络拓扑的动态变化，因此运行于其上的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 g e n t 计算框架模型。 1 2 多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 s 系统是由多个可以相互交互的a g e n t 的计算单元所组成的系统。它是为了解 决单个a g e n t 不能解决的发展问题，由多个a g e n t s 协调合作形成的问题求解系统。多 a g e n t 之间可以是紧密耦合也可以是松散耦合的，多a g e n t s 系统的组成粒度也可粗可细。 为了使各个a g e n t 之间能够合理高效地进行协作，多a g e n t s 计算中一个非常重要的内容就 是合作协调，通信，这是多a g e n t s 群体中应该具有的社会属性。 多a g e n t 以一定的方式组织在一起相互共享资源相互协作，称之为a g e n t 合作与协调 ( c o o p e r a t i o na n dc o o r d i n a t i o n ) ；多a g e n t 之间需要以一定的结构和机制进行通信，从而 实现信息交流，称之为a g e n t 通信( c o m m u n i c a t i o n ) ；在网络系统中，a g e n t 需要从一个 网络结点移动到另外一个网络结点执行任务，称之为a g e n t 迁移( m i g r a t i o n ) ；在开放式 1 0 复旦大学博士学位论文第一章绪论 动态网络系统中，可能会有恶意主机的加