（计算机科学与技术专业论文）虚拟组织上的有限状态mobile+agent系统的建模与性能评估.pdf

虚拟组织上的有限状态；。渖。系统的建模与性能评估 y 8 7 7 2 乏2 摘要 b i | e g 卸t 是一种能够自主控制通过网络进行迁移，有选择地在网络中不 同的节点上独自运行以完成多种任务的程序。通常，_ 0 b i e a g e n t 需要寻找恰当 的计算资源、信息资源和网络资源，并且在网络中的某一个节点上将这些资源组 合起来完成哪b _ | ea g e n t 具体负责的计算任务。粕b i e g e n t 技术是下一代网络 应用程序发展的方向，该项技术为分布式程序的部署提供了一种十分有效的模 式，它特别适合在网络环境不稳定，需要使用特殊的设备和计算资源的情况下使 用 1 6 】。目前m 0 b - i ea g e n t 技术已经得到了广泛的研究和应用，涌现出了非常多 的原型系统，但是在实际部署前，往往需要对m o b i ea g e n t 系统在实际大型网络 ( 如i n t e r n e t 环境) 中运行的性能指标情况进行测量但是由于网络本身的对称 性、复杂性、多样性及u o b i e g e n t 技术本身的特点，在实际的复杂网络环境下 测量是非常困难的，因而就必须对该类系统进行大规模网络环境下的建模仿真和 性能评估。 m o b | e g e n t 技术作为未来分布式系统中的主要计算模式，得到了广泛的应 用。为了更有效的在大规模的网络环境中部署o b 1 e g e n t 应用系统，往往需要 对b i e g e n t 系统进行定量的性能参数评测和模拟。 本文介绍了一种建立在虚拟组织网络拓扑管理技术之上的有限状态精o b _ | e a g e n t 系统，该系统采用虚拟群组的节点管理协议实现节点间资源和服务的快速 查找，并且在资源的驱动下实现a g e n t 的部署、迁移和服务等功能。 本文中还给出了有限状态b i | ea g e n t 系统定量的性能评估建模过程，对有 限状态m o b i l ea g e n t 系统执行中的a g e n t 的子状态的执行过程进行分析，从而给出 其执行参数计算过程，并且根据给出的模型通过仿真实验获得系统在大规模网络 环境下执行时的性能参数指标，实验结果表明，该系统具有良好的可扩展性和较 高的网络服务效率。 关键词虚拟组织，有限状态如b i i ea g e n t ，性能评估，评估模型 虚拟组织上的有限状态m o b a g e n t 系统的建模与性能评怙 a b s t r a c t am o b i l ea g e n ti sap r o g r 帅t h a tc a nm o v em r o u 曲an e t w o r ku n d e ri t so w nc o n 们l ，c 印a b l e o fn a v 逸a 毒i n gt h f o u 曲l h eu n d e f l y 抽gn e 细o r k 糊dp e 哟艄讥gv 甜i o u $ t a s k sa le a 穗n 吲e 融崛 e n d e n t l y m 。b 订ea 彗e n t sp r o v m 粕e & c t i wp a 豫d i g l l lf o rd i s 曲嘞d8 p p l i c 砒i o n s ，d 雠嘶c u i a r l y 缸口a c t i v ei n8d y r m kn e t w o r ke n v 证o n m e n ti n v o 汛gp a m a l l yc o n n e c t e dc o r 叩u t 砸g e l e 啦e n 括鼍 h 。yl o e a t ef 馥t h e 诤p 争靠a 坶e 。礅p 娃攮瘃啦 夥o h 羚。s ，i n m 赫。n 糟s o h 瓣髓鞠d n e t 、v o r kr e s o u r c e s ，c o m b i n i n gt h e s er e s o u r c e si n4c e r t a i nh o s t ，t oa c c o m p l i s ht h ec 讲n p u t i n gt a s k s ni sad e s i r a b l et e c l l l l o j o g yf o r 也en e x tg e n e r a 廿o nn e t 、v o r ka p p l i c a t i o n s w 囊i l em o 鲢l e8 窖嘲括囊a v eg e 矗髓褒圭e de o n s i d e 持瓣搴镪e i 耙m e 蛀l 遮氇er 嚣# 8 托he 锄m 鞴鞋孔强垂 a l s oh a v em a n yp r o t o q ，p es y s t e m s ，协e yh a v en o tb e e na p p l i e di n t 0as i g n i f i c a n tn u m b e ro f r e a 卜w o r i da p p l i c a t i o n s o n eo ft h em a i nr e a s 呻sf o rt h i si st h el a c ko fq u a n t i 协t i v ep e r f o 玎| 1 a n c e e v a l u a o h s n l i sp a p e ra n a l y z e st h ep e r f o m a n c eo ff i l l i t os t a t em o b i i e 鸭e n t t h e 舶i t es t a t e sr e f e rl o 峨em i g r a t i o n ，e x e c m i o n ，a n ds e a r c h 抵go f 壤em o b 娃ea g e n l s 1 nt h 娃p a p e nw ep r o p o s e od e p l o y 娃豫磊n 拜es 诹t em 。糙ka g e n 拓o n 斑ev i m 越珊g 黼i 猫舡o np l a t 稻糯b a s e do n 氆i s 矗薯m e w o 血，w e i i l 廿o d u c e dan o v e lc o 丌e s p o n d i n gs e a ha 1 9 0 啪1 1 1 nt o g e t l l e rw 胁a ne v a l u a t i o nm o d e if 叶i h e 最n i t e 妇瞳em 曲i l ea 鐾e n t 。t h ee x p e 瞳n e n tf e s 毽虹b 鹅e do 矬峨i se v a l u 越 傩m o d e l 鼎o wt h e 蠡n t e 蝌) b l e a g c n 铝c a na 幽话v e 懿l j y i n gp e r f o m 、蝴c eu n 赫讯es i n g l ea g e n tc o n d i t i o n 矗n d t h em u l t i p l e 矗g e m c o n d i t i o n k e yw o r d s ：v i r t u a io r g a n i 糊t i o n ，f i n i t es 扭t em o b i i ea g e n h r f o r m a n c ea n a i y s s ， 嚣v 矗l h a 蛀o # m 8 d e l i 寝掇组绞| ：辩露鞭撬鑫磁o b i e a 铲嗽糸统赫建模知挂艟弹嵇 第一章绪论 嘻。1 课题磅究懿背景移意义 自1 9 9 9 年起，教育部先后在我国近百所著名高校的一流专业或实验窜( 主要 是圈容重点学科或重点实验室) 中建立了网上台作研究中心( 以下简称中心) 或 分中心，使褥嚣中心或分中心之闻能充分利用瓣络资源开展计算枫支持的协同磅 究( e o l l p h t e rs “p p o r t 嬲e 弦r a t i 鞠r e s e a r c h ，麓称e s c r ) 。其中，隧上台 作研究的重点和难点问题之一是如何为所有中心或分中心提供一个灵活、高效、 稳定、可靠的网上合作研究支撑平台。本文的研究内容就是在此背景下展玎的。 在实际应用过程中，需爨将分布在全国大学中的1 9 个不同领域的研究中心通过 c 鞭l 显耀连接，利用公共戆凌终平台实现备令中心之闻豹赘嗣磷究工嚣。磅究 中心凝据箕研究领域的不同丽各自形成穗对鬃中的树状组织结构，黼此如何管理 和组织这些合作中心，掇供一个合理可靠的资源共享和使用平台魑1 _ 作的重点。 在我们的解决方案中使用了一个虚拟组织的网络拓扑管理技术，同时引入m o b i i e a g e 雌技术作为资源共事耪使用的解决技术。 瓣两il ea g e n t 是一耱黢够鑫主控爨逶邈嗣终逡器迂移，毒选撵羹魏在网络中不 嗣的节点上独自运行以究成多种任务的程序c 1 5 】。通常，m o b i ea q e n t 需要寻 找恰当的计算资源、信息资源和网络资源，并且在网络中的某个节点上将这些 资渊缀台起来完成m o b i i ea g e n t 具体负责的计簿任务。b i i ea g e n t 技术是下 一代网络应曩程序发展鲶方囱，该瑗技本为分露式程序的部署提供了一耱十分毒 效静模式，它特嗣适合程网络强壤不稳定，需要使翊特殊豹设备魏计算资源豹猿 况下使用【16 】。目前抽o b i l ea g e n t 技术已经得到了广泛的研究和麻用，涌现出 了a # 常多的原型系统，如i 阴的a g l e t 系统【1 3 】、o a r t i i l o u t h 大学的d a g e n t 系统c 1 0 ，1 1 ，掩】、t r a c y a g e n t 系统【1 7 】、g e n t f l 9 】系统等等。虽然这些酗h li e a g e n 系统广泛痰蠲予谗多实舔系统中，餐是凌褰嚣部署蘸，往臻鬟蓑对麴b ll e a g e n t 系统在实际大型溺络( 翻i n t e r n e t 环境) 中运行的性能揩标情况进行测 量，但是由于网络本身的对称性、复杂性、多样性及m 曲i i ea g e n t 技术本身的 特点，在实际的复杂网络环境下测量是非常困难的，因而就必须对该炭系统进行 蕴糕懿纸 壤亩澈毓惫m 。b 涤a 錾砒蘸统鞠斑模与性能评旗 大瓶模疆络环境下静建模仿真鞫性髓评话，嗣靖壶予轴b il ea 擎盹系统往往部 署猩特定的应用场景中，因两需蹑对特定的成用场景和应用过程进行针对性的建 模和性能评估。 近年来淹着耩曲ll ea g e n t 在飕终中的应瓣摆广，晒b ll ea g e n t 系绞豹牲麓 建横和评 苡1 ：作涧题引发了研究人员的越来越多的荚注。在对豫o b ii e8 q e n t 性 能评估的褶关研究中，目前主要有两种比较通用的研究恿路：一种是从b 1 e a 掌n t 实瑗的具体技本出发建立逶震戆黼ll e8 9 e 赋系绞工痒模型，热 j o h a n s e n 【5 】，并且与对应的实现技术进行对比如远程调用、客户服务器技 术等等。程这方瑟主要的代表工作有s t r a s s e r 和s c h e h i i l 【2 】提出的赫o b i l e a g e 聃t 与r p c 性g & 对比模型，阳li a f l t o 等人【4 】提爨麴b l ea g e 畦、远程瀵 用及客户服务器模型对比实验等：另外一种比较普遍的研究思路是从m o b ii e a g e n t 赢潮的其体场景离发针对特定的应用领域中采用的i | | o b il ea g e n t 实现技 术，建立其性能模型并且评售其性能水平，遮方薅的工作主要鸯，k u p p e ra 删 p a r k 3 针对一个分等级的发信号网络的队列，给出的基于m o b t i ea g e n t 实现方 式静往麓谱储模羹，懿获耗v i dk o t ：等人【】针对羡国海军怒飘作战遵讯弼中 的卫星无线网络僚怠过滤系统，给出的应用了聃曲il ea g e n t 技术的系统性能谔 估模型和实验等等。 1 2 课题研究的内容及主要工作 本文介绍了一个在虚拟组织( v i r t u a l0 r g a n i z a t i o n ) c 7 ，8 ，9 】之上的基 于有限状态机的m 油- i ea g e n t 系统( f j n i t es t a t em o b 1 ea g e n ts y s t e m f s 一瓢s ) 。通过虚拟组织按术采实理对鼹上中心溺的繁点拓羚进行管理，裂用 f s m s 系统实现在in t e r n e t 的环境下远程的多个节点间的资源共事和计算功能。 并针对f s - 赫a s 系统的一个典型成用给幽其性能评估横型，该模型定照地对f s 一朔a s 系统述行建模，然磊遥_ 过鼹络环壤斡傍宾，季譬蹬大爨釉b ll ea g 朝t 嗣薅撬行媾嚣 下系统及网络的性能指标状况，并且从运行的结果中计算得到系统的性能基准。 实验缩采表明砖一黼矗s 系统具有较好豹可扩展径，能够支持大量晒b i l ea g e n t 同时 执行，且保持系统攫体。睦能不会明显鲍下降。 首先对对有限状态m o b | l ea g e n t 建模并给出了m o b | ea g e n t 计算模型，并且 虚拟组织上的有限状态m o b i l ea g e n t 系统的建模与性能评估 在实验室局域网环境下实现了有限状态h o b i i ea g e n t 系统原型，并且测量了基本 通信参数。进一步给出了基于虚拟组织的有限状态h o b _ i ea q e n t 系统的性能评估 模型，对关键测评参数进行了推导，最后实现了整个模拟实验平台，并对实验结 果作出分析。 1 3 文章结构 本文内容共分六章，包括：第一章“绪论”，第二至五章为主要内容，最后 一章足“总结与展望”。 第一章绪论 介绍了本论文的研究背景、意义以及研究内容，同时对课题研究内容做了简 单的介绍。 第二章基于虚拟组织的有限状态m o b 1 ea g e n t 系统 本章中首先对有限状态m o b i ea g e n t 的底层一虚拟组织做了简要介绍，并洋 细介绍了有限状奄雠0 b i l ea g e n t 的理论模型。 第三章有限状态m o b ea g e n t 系统的性能评估模型 本章中首先对有限状态睢o b i l ea 9 e n t 的工作场景和资源搜索作出简单描述， 最后详细介绍了性能评估模型和参数的选取与计算。 第四章模拟实验平台的设计与实现 本章实现了有限状态m o b i ea g e n t 性能评估模型实验平台，并对实验平台的 两大模块虚拟组织和b i l ea 9 e n t 系统做出详细介绍。 第五章实验设计与结果分析 本章介给出模拟实验的设计和结果，对单a g e n t 和多a g e n t 运行情况作出详细 分析。 第六章总结与展望 对论文的工作进行了回顾、总结，并对后续工作进行了展望。 1 4 本章小结 本章是综述性的章节，力求使读者对论文选题背景、研究意义和研究内容有 个大致的了解。研究内容和主要工作： 虚拟组织l 的有限状态m o b i i ea g e m 系统的建模与性能评估 对有限状态m o b _ | ea g e n t 建模并给出了b _ | ea g e n t 计算模型； 局域网环境下实现了有限状态u o b i ea g e n t 系统原型，并且测量了基 本通信参数； 基丁虚拟组织的有限状态m 曲i ea g e n t 系统的性能评估模型； 实现了整个模拟实验平台，并对实验结果作出分析。 虚拟组织卜的限状态m o b i l e a g e n t 系统的建模与性能p f 估 第二章基于虚拟组织的有限状态m o b i l e a g e n t 系统 2 1f s m a s 系统的底层结构一一虚拟组织 f s 一帆s 系统是建立在虚拟组织之上的，同时f s m s 中a q e n t 间的通讯和资 源发现以及a 9 e n t 的迁移等子功能都是由虚拟组移 介入辅助完成的，冈而虚拟组 织的底层结构是f s 一叭s 系统执行和部署的基础。这里在详细介绍f s m a s 系统之 前有必要介绍一下虚拟组织的构成和定义。 虚拟组织的基本构成单位是节点，如网络中p c 、p 队、便携机或者其它与网 络相连的设备等，如图2 - 1 。虚拟组织中的节点实行分组( 群组) 管理，节点可 以动态的加入或者退出群组。群组与群组之间按照一个树状的等级层次结构管 理，这样群组就可以被分为r o o t 层、中间层和l e a f 层等虚拟屡。 2 1 1 虚拟组织结构中的相关概念 本文中的虚拟组织结构足中类似丁文献 7 ，8 】的网络拓扑组纵结构，具体的 定义给出如下。 黟席m 如j ，能够装载和执行移动主体的网络上的最小设备，记为r i 。 这里所说的最小设备包括各种终端、服务器，以及具有自己的管理软件系统的仪 器设备等。这里每一个节点即可提供服务，同时又可以消费服务。 兴鳝秽篇隰砂 ，d 如j ，关键节点是在虚拟组织中能够处理远程通讯的节点， 每一个群组中必须包含有至少一个关键节点。 群级佑切印) ，群组由一个或多个节点构成的集合，记为g a i = tr 0 a ，r 1 a r 2 a ，r n a ) 。a 是群组的名称标识，同时每一个群组都有一个层标识i ，表明当 前的群组是位于整个虚拟组织的第i 层。同时节点可以同时加入一个或者多个群 组，这样就意味着包括关键节点在内的每一个节点都可以同时属丁| 多个群组。 群组是一个相对稳定的组织结构，属丁某一个群组的节点可以动态的加入或 者离开该群组，节点的登陆和注销操作使用一个类似于i g 忡的g g 肿( g r i dg r o u d 5 虚拟组织 j 的有限状畚m o b i l e a g e n t 系统的建模与十牛能评估 m a 响g 鲫e n tp r o t o c o i ) 7 协议来规范实现。 图2 - l虚拟组织结构中节点、关键节点、群组刚关系示意 在以上定义的基础上，我们可以得出虚拟组织的定义 瘟拟级钾f 啪肼，0 噌m 妇f f d 月) 一种由网络中的节点构成的、通过一定 的协议来维护其群组关系的组纵形式。虚拟组织中的群组之间的层次结构晕树 状，如图2 2 所示，包括r 1 r o o t 群组，标识为r gm o t 群组是树状结构的第一层； 2 中间层群组，标识为吲，f 标识群组位于虚拟组织的第f 层： 3 l e a f 群组，位于虚拟组织的树状结构的最底层。 一般地，每个群组中包含一组属性相似、距离接近的节点。在每个群组中部有一 个关键节点( k e yn o d e ) ，用r 0 i 表示群组g i 中的关键节点，关键节点在群组 中的作用相当于局域网中的网关，它负责该群组中的节点与其他群组中的节点之 间的通信。在群组中通过g n s p ( 6 a t 蝴yn o d es e i e c t i v ep r o t o c o i ) 7 协议来 选择关键节点。在整个节点和群组中，所有的关键节点之间又构成了一个特殊的 互联群组，我们称之为核心群组( k e r n e ig r o u p ) ，记为g k 。核心群组足整个 网络拓扑结构中最重要的组成部分，为所有节点提供服务，处理节点之间的通讯、 虚拟组织上的有限状态m o b a g e 呲系统的建模与性能评估 寻址等操作。 r o o t1 a v e r ( f i 圩” j d、奄 面6 o ， l一 t 卣审七西! 曲 图2 2 树状的虚拟组织层次结构关键节点连接了r 0 0 t 崖群组和其子层的群组群组 g 中的关键节点将群组g 和g 连接起来 2 1 2 虚拟组织中的资源搜索策略 由丁采用了树状的管理结构，在虚拟组纵中查找资源服务的效率得到了非常 显著的提高。虚拟组织中采用了两种资源查找策略，分别是无关键字的全树搜索 策略和基于关键字的领域搜索策略 1 4 】。无关键字的全树搜索策略从树状结构的 最顶层群组开始查找，并行的向下面的子群组发送搜索消息，直到具有需请求资 源的节点回复为止。区别于无关键字搜索策略，基于关键字的领域搜索策略采用 的方法是，先比对每一个层的虚拟群组所具有的关键字，如果关键字不匹配则直 接跳过，只有那些关键字与所搜索的内容关键字匹配的群组才会被进一步的搜 索。 在虚拟结构中由于对群组进行了树状结构的表示和管理，然后再通过具体 的群组对若干的节点进行管理，类似于进行了二次的索引操作，冈而采用全树搜 索的策略其效率还是非常的高的。然而，无关键字全树搜索策略在进行查找过程 中需要并行的向其子层发送消息( 最坏的情况下，消息发送甚至需要覆盖整个虚 拟组织树结构) ，因而该策略容易导致消息通讯量过多，占用比较多的带宽。 虚拟组织卜的订限状态m o b i i c a 香e m 系统的建模与性能许估 为了解决全树搜索策略中的消息通讯量开销较大的问题，我们给出了基于关 键字索引的搜索策略，在此策略中，请求资源的消息不会转发给每一个子群组及 其节点。只有在群组的标识关键字与需搜索资源的关键字匹配对应的情况下，查 询消息才会转发给对应的群组，这样就可以避免消息广播的情况出现。但是采用 基于关键字的领域搜索策略，在使用之前要求预先建立虚拟组织结构的领域关键 字索引目录，且随着群组中节点的变更，还需要不断的对索引目录进行维护和修 改。基于关键字的领域搜索策略虽然能够有效的减少资源查找过程中的消息通讯 耗费，但是需要对虚拟组织进行额外的索引目录建立和维护，可以看作是通过牺 牲一定的预处理代价来减少搜索过程中通讯耗费。 在接下来的f s m a s 的性能建模和评估中，由于无关键字搜索策略不需要事 先建立对应的关键字目录和索引，我们采用该策略作为b i ea g e n t 系统的缺 省资源发现方法。在有限状态m o b - i ea g e n t 系统中如何具体的实现无关键字搜 索策略将在后面的章节中予以详细介绍。 2 2 有限状态a g e n t 有限状态 g e n t 是一种基于资源驱动的介于强移动模式与弱移动模式之间 的m 0 b i ea g e n t 系统。它实质上足一种在外部资源或数据变化的影响下自动进 入对应执行状态的有限状态机。 数据与m o b - i ea g e n t 自身状态转换有关却与执行节点无关的所有局部数 据。 资源分布在o b i | ea g e n t 的执行节点上的所有数据、设备、软件环境的 统称。 本文将位丁节点上的所有运行时参数和设备都统称为资源，以区别于影响 m 0 b | e a g e n t 自身发生状态转移的数据。这样就可暂时不考虑网络拓扑对m 0 b i i e a g e n t 执行状态的影响，故可直接从m o b i ea g e n t 的执行状态转移角度描述其 具体执行过程。实际上t 在有限状态a g e n t 中，我们不必关心当前已经执行到了 具体哪一个节点上，而只需了解m 曲| e g e n t 当前已执行到什么状念。 有限状态a g e n t 由有限状念集、外部输入条件集和状态转移关系组成。记作 f s - a g e n t = a n s 。u nf 毒 虚拟组织l 二的有限状态m o b i i ea 薛n t 系统的建模与性能评估 其中，彳，表示耶刊雕 f 的标识，它在整个系统运行过程中保持不变，其作 用是用以区分不同的m o b i l ea g e n t 。在有限状态m o b i l ea g e n t 体系中，所有的 m o b i l ea g e n t 都采用通用的状态集合及通用的状态转换关系，个体之间通过爿， 来区分，在服务状态运行相应的服务内容。墨是有限状态集合，包括请求( r e q u e s t ) 状态、服务暂停( s u s p e n d ) 状态、服务阻塞( b l o c k ) 状态、迁移状态( m i g r a t i o n ) 和服务( s e r v e ) 状态。昕包含两种条件：一种是服务状态对应的资源( r c s o u r c c ) ； 另一种是服务状态对应的服务的执行时间( t i m e ) ；f r 是状态转移关系，状态转 换关系如图4 所示。 由图2 3 可知，有限状态a g e n t 是在资源与服务时间共同驱动下的一个状态 机。在此状态机中，从b l o c k 状态到s e r v e 状态间加入了m i g r a t i o n 状态，实际 上能起到如下作用：当m o b i l ea g e n t 发现本地资源不足时，就开始查找远程资源， 并迁移到具有足够下一阶段服务执行所需的资源的节点上。 图2 3 有限状态a g e n t 状态转移关系图 2 3m o b i i e a g e n t 计算模型( m a c m ) 在实际的网络执行状况下，随着网络拓扑的变化，以及网络节点上资源的消 耗与生成，同种m o b i l ea g e n t 执行的具体路径是不同的，为了能够描述和规范在 虚拟组织之上的m o b i l ea g e n t 的执行过程，本文提出了一个服务计算状态机，也 称之为基于有限状态机的m o b i l ea g e n t 计算模型。 在已有虚拟组织【7 的基础上，本文给出分布式系统中的基1 ：有限状态机的 m o b i l ea g e n t 计算模型，其定义如下： 9 虚拟组织l ：的竹限状态m o b i l e a g e n t 系统的建模与性能评估 脱4 c 杯e ，= 俾，s 肘j 巾，h 曰，a ，g j 其中，r 是节点集合；s 是m o b i i e a g e n t 的有限状态集合，在实际的网络服务中s 就代表着每段服务执行代码； m c s 是m o b i l e a g e n t 中所有处理消息状态的集合，m = 腿a 彩，坛是发送消 息的状态，是接收消息的状态；v _ r 是m o b i l e a g e n t 初次产生的节点，m o b i l e a g e n t 在节点v 被发布，进入其状态转换周期；e c 月是m o b i l e a g e n t 注销的节 点，m o b i l ea g e n t 移动到e 中的节点后注销并结束其生命周期；a 为m o b i l e a g e n t 的迁移状态，表示m o b i l e a g e n t 处在开始移动到另一个节点上将要进入新 的执行过程的状态：s 为空状态，表示m 0 b i l ea g e n t 不执行任何运行状态或迁移 状态；巾是从尺x 心u a ，s j 到r 的转换函数，即 中? 置x f su a ，s ) j 一置 使得 ( 1 ) 对所有r 。玛r ，若m c r bs ) = 如则r l = 马： ( 2 ) 对所有风弓r ，若中( 风a ) = 弓，则风弓； ( 3 ) 对所有月。弓尺，研墨若中( 月，s k ) = 吩则r = 弓； ( 4 ) 对所有扁r ，若中俾“舰j = r 。则下一状态转换关系为面俾。 m 0 = r j 。 m o b i l ea g e n t 计算模型中的转移状态a 是建立在虚拟节点组织结构中的节点 间的通信基础上的，利用基丁消息的通信算法 1 0 】，将m o b i l e a g e n t 从源节点迁 移到目的节点。在虚拟节点的底层结构的支撑下，m o b i i e a g e n t 的计算模型可实 现高效的状态转换、位置迁移和消息通信等功能。 2 4 有限状态m o b i i ea g e n t 原型系统 在实际的有限状态m o b i l ea g e n t 系统中，有限状态香n t 都是执行在一个称 之为a g e n t h o m e 的容器上。a g e n t h o m e ，如图2 4 所示，包括了两个主要功能：管 理虚拟群组和m o b i l ea g e n t 的调度。出丁对系统的跨平台性及可移植性的考虑， a g e n th o m e 采用j a v a 和x m l 技术实现丌发，利用x m l 的可扩展性对a g e n t 的 虚拟组织卜的有限状态m o b i l e a 辨n l 系统的建模与性能评仙 输入以及资源等进行描述。部辫在每一个可以允许m o b i l ea g e n t 执行的节点上的 a g e n th o m e 提供了如下的服务和功能： 一所有的a g e n t 执行的服务功能都是邋过a g e n th o m e 来间接调阕的，这样 a g e n t 不能直接的访问本地节点上的资源，而改为必须由a g e n t h o m e 代理， 韪够辍证毒限凝态麓曲 l ea g e l l t 系统熬安全注裁，有效兹避受恶意豹找鹃翔 题。此外由j 二a g o n t 的服务是通过a g e n th o m e 来代理的，这样可以比较灵 活方馁的在a g e n th o m e 上应用一些增强系统安全瓣全弱媛者本遗鲍策略， 提高脊限状态m o b i l ea g e n t 系统的适应性能。 _ a g e n t 执行和阻塞队列的调度和管理服务，在a g e n th o m e 中维护了三个 m o b i l e8 9 e n t 酌运行酞到：阻塞队列、挂起酞劐和等待执行队列，分剐对应 于有限状态a g e n t 的阻塞、挂起和执行三个状撩。这样a g e n th o m e 就可以 按照鸯陵鼗态a g c n t 熬凝恣转移关系，围4 ，裰据当蘩节赢豹姿潺熬使瘸戆 况对请求资源的a g e n t 进行调度和管理，从而维护和保证a g e n t 的正常执行。 资源攘索服务，褒毒限状态m o b i l e8 9 0 n 系统中分毒在各个节点上的艨奏资 源都魑使用r d f 【1 8 来描述定义的，a g e n th o m # 中提供了对远程资源的搜集 和查找功能，即肖阻塞的a g e n t 发送资源寻找溥求时，不足直接通过a g e n t 本身曩乏发送的，褥是通过本地的a g c n th o n l e 来代理完成的。在我们的a g e n t h o m e 原型系统中，资源搜索服务是绑定在3 1 3 端口上的。 撬牙a g e 嫩骚务，a g e n t h o m e 捷珙了镪始纯a g 鞠t 撬幸亍环凌及箕资淄鹣功麓， 并且可以启动a g e n t 的执行过程，在有限状态m o b i i ea g e n t 系统中a g e n t 的 执行功施被分勰为若干段霹阻独立撬行蕊j a v 8 程序段，只鬟袋褒了埝尚豹赣 入资源和参数的情况下就可以唤起执行，我们使用x m l 格式的文件描述出 这些j a v 8 程序段a 罾e n t 的执行流程。出于a g e n t 执行的流程控制是通过x m l 格式采擒述弱，可以非常容易的与r d f 格式的资源描述兼容。 虚拟蛆织上的有限状态m 0 b i i e a g e n t 系统的建模与性能评估 2 5 本章小结 阁2 4 a g 蝴t h o m e 的主羿商 本拳必_ 鑫文粒主体理论牵碧，奔绥了纂予囊羧缀缓戆毒嫩获悉辍玲ll e 纛鬈e 畦 系统的相关基础理论概念以及系统原型，对虚拟组织和有限状态捌o b i e g e n t 以及其计算模型作出详细贪绍。涉及的关键内容毒： 虚拟组织 有限状态a g e n t 基于有隈状态税的m o b i l ea g e n t 计算模登 滋搬组织上钓有碾状态m o 桃l e a 醇m 系统的建横与性能评估 第三章有限状态m o b i l ea g e 疆l 系统的性能 评估模型 3 1m o b i i ea g e n t 的工作场景和过程 在有限状态m o b i l ea g e n t 的执行过程中，a g o n t 需甓在网络上寻找到具宵足够 夔资源，嗣簿g l 够保涯8 9 。n t 鼹。f 一步l 琵务状态g 够被撬杼熬网络节点。在这一 过程中，m o b i l ea g e n t 仅需要与本地的节点进行通讯，所有远程的i 随讯操作都是 由本魄节点来实现的。 图3 一l 中寿鼹状态稻b i l ea 鬈c n t 系绫戆典型窟雳场景是建立在其体弱癍震基 础上的，在实现上可以分解成为图3 1 所示的有限状态转换过程。图3 1 中的 s 钯t e o 和s t a l c 1 分潮表示鹰用场景中的获得挖掘算法的服务和对生物文献数据库 进行检索挖掘处理的服务，秘r 1 分剐表承运舞上莲静鼹个驻务鼹震蘩故资 源，这里具体指a i 中心提供的数据挖掘算法模块和生物中心的文献数据库资源。 8 鼬晦# j # 镣l o 粥d 翱l 静滟x 一 。“ t k 椎缸辩， 一1 卜 e 桐抽y b a g l k ；_ i 一 j 旷j d a 躯t “榭谢轩t 。v 一一 e 矗辩融鬏l 戳赣a 轴# _ _ ，“ 举n l 融冁辍# t 謦l _ 。f - ”n or e 粕l 撼嚣 、誓s 酶镣# 骤瓣酶 l 、一r 脚 强3 。lf s ，酣a 撬行滚鞣 图3 - 1 中给出的有# 建状态m 0 b i l ea g e n t 的执行过程可以着俸是一个服务状态 在资源驱动下依次执行的j 遘程。圈中鲍a g e n t “e x 8 m ”由薅个鼹务状态组成，其 虚拟组织卜的商限状态m o b i i e a g e n t 系统的建模与性能评仙 执行过程如下： a ) 最耦a 窨e 墩是都署在畿叛缝织上的节点x 上，群始准备执行s t a 豫o 豹缀务， 但是发现本地的节点。b 没有足够的资源 ( b ) e x a m 需要资源r 。才髓执行s t a t e 0 的辙务，闲j 玩e x a m 阿虚叛缎织发送请 求资源的消息，这里e x a m 不镶要关心资源搜索的具体过程，完全交给虚 拟组织来处理 ( c ) 当发现虚拟组织中的巢一个节点上具有资源。则向节点x 返回发现资 源的消息 ( d ) 节点x 收到消息，节点y 上育溅足s t a l e o 执行的资源，然后节点x 将e x a m 迁移别节点y 上 ( e ) e x a m 迂穆到节点y 上层，一鲢获褥瓷源鸵使嗣权，就嚣媲撬程s t 8 t e 0 以上绘爨熬是筑8 妊0 执纷戆详缨过程，s 纽t e l 戆撬雩亍过程测蹙重复上l 垂静避 程。这里需臻说明的是，搜索过程中的节点x 在等待了一个同定的题时之后没 有褥爨发璃瓷澡豹豳 囊信惠，翻诫为在挠行邋疆中当籍的虚瓠缀缓上没有茇瑷蹩 够的满足服务状态执行的资源，此时节点x 会返回l n 师i n d 的标识，告诉a g e m 当蘸没有可辩i 静资源，箢对烀n t 将转入阻塞状态，等待一段时间后释重新查拽 资源。 l 注e c u t eb 】o e k 。d e y t lt 2翳瓢 强 辐 图3 - 2 ，a g e n t 执行的时序过程圈 虚撤组织上盼霄限状态m o b i l ea g e n t 系缝的建攫与性能评馈 图3 - 2 给出了a g e n t 执行的时序过程，从图中可以看出，a g e n t 的执行过程 飙时间先瑶t 可以划分为几个相对阍定酌片断，分剐是a g e n t 查找资源耗时 t 。m t a g c n t 迁移耗时己 。，a g e n t 在远程节点上执行耗时z k 。，以及8 9 e n t 阻塞过程耗时。从图7 中可得，巧 正 墨 瓦 i 瓦，这里我们忽略网络 接送过程中的信号懿时，予怒可茨褥翻下面瀚计葬公式： 3 2 资源獯索算法 霉甜。互一霉 婚删坤霉一瓦 瓦。“五一墨 不撕。磊一霉 ( 1 ) ( 2 ) ( 3 ) ( 4 ) 为了避免索弓i 建立方法的不同而对有限状态bw | ea g e n t 系统性能造成的 干扰和影响，在我们的性能评估模型巾采用的是无关镳字的垒树搜索燕略，其策 略在在虚拟组织上的实现过程如图3 3 所示。虚拟组织中的某一源节点开始发送 资渊请求消息，在发现本节点所属鲍群缀中没有找到资源之盛，于是邋过该璐缝 的关键节点向根节点发送资源请求消息，根节点收到消息后，稃并行的依次向其 子鼗篷发送瓷源请裳涟惑，遂群在痘熬缝缀中食毒爨诲隶资源豹嚣麴节点牧到遮 求消息后，目的节点再向源节点回复资源请求消息。 有限袋套蘩o b ll ea 弘n t 中豹搜索算法楚蒺，消惑传递模式亲实毯豹，渍惑 通过虚拟群组中的关键节点转发给不同的群缎。消息传递的通讯方式中由于不怒 采掰“发送一确试”豹霹靠遴谖方法，容荔出糯消意兹失静情况，淆惑丢失豹赢 接结果就有可能造成等待资源搜索回复的 g e n t 一直处于等待状态中，这就要求 在a g e n t 搜索过程必须有一个最大的援索等待延时，一壁a g e n t 在资源搜索过穰 中等待的时间超过了摄大搜索等待延时，a g e n t 就认为消息已经丢失或黄是资源 没有找至9 ，a g e n t 转入阻塞献列。 虚拟组织上盼谢跟状态m o b i l ea g e 拜t 系统蛉建模与性自评旗 当a g e n t 进入阻塞队列之后，同步的将启动一个计时器，计算a g e n t 被阻塞 的时间，这辍给酞捌设篝了一个酲塞酞列查询延时，当a 9 e n t 被阻塞的时问累计 到达阻塞队列查询延时，a g e n t 会被霪新唤起，然后继续发送溃源请求消息。 通常，鼹大援索等待延时和阻塞队列查询延时都怒由虚拟组够l 根搬肖前嘲络 的状况，振扑的结构，虚拟缀纵群维树的层数等因素来设定魄。但是在有限状态 赫o b _ i ea g e n t 系统中，也允许本地的节点和a g e n t 本身来单独指定遂两个延时 的疑体值。 _ 。，。， 一。、f i i $ h it ，r u 。似 。 l ” 一 ll 。一。 l 一“_ i _ m 、r i i li ll 3 3 参数和评估模型 3 3 1 参数 翻3 3 盘撼缝缀土熬炎深搜索过程 为了更好的给出有限状态m o b j l ea g c n t 系统的性能模型，下面我们给出评估 模型中需要用到的一些参数帮术语的定义： 只，a g e n t 平均字节数大小( b i t s ) 蜕，都瓣在虚拟组织上的a g e f l t 数量 ，粥难运行避程孛爨要攮行瓣子状态数 f ，a g e n t 子状态数的编号标识，l 基，s c 1 6 虚拟组织1 的仃限状志m o b i i ea g c n t 系统的建模与性能评仙 j ，部署在虚拟组织上的a g e n t 编号标识 ，查询消息的字节数大小( b i t s ) 乙。，最大搜索等待延时( s ) 曰，虚拟组织中的带宽( b i t s s ) 成，a g e n t 迁移过程中的有效带宽比率( 尾 1 ) 风，a g e n t 消息通讯过程中的有效带宽比率( 几 1 ) 吃，a g e n t 迁移过程中的有效带宽( b i t “s ) ，吃= 成b ，a g e n t 通讯过程中的有效带宽( b i t “s ) ，既= 风口 k ，节点x 和节点y 之间的最小跳跃( h o p ) 数 瓦，阻塞队列查询延时( s ) “”t ，a g e n t 在执行第i 个子状态过程中被阻塞的次数 毛，a g e n t 第i 个子状态服务执行耗费时间，1 f e ( s ) 。，节点y 上等待资源执行的a g e n t 队列数目 巧，节点x 执行a g e n t 子状态服务的能力( s u b s 诅t e s s ) ，节点x 执行能力效率( 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 的子状态数e 都是相等的。 b 是虚拟组织网络中的理论带宽值，但是在实际中的网络传输是无法达到该 值的，因此我们分别给出了有限状态m o b i l ea g e 眦系统中在考虑了网络协议及其 设备等影响因素作用后的消息传递过程中实际获得的带宽和a g e n t 进行迁移 过程中实际获得的带宽鼠。 虚拟组织上的有限状态m 0 b i l ea g e n t 系统的建模与性能评估 由丁a g e n t 请求资源的过程中可能会失败多次t 冈此我们引入了参数m f ， 作为a g e n t 在执行其第i 个子状态过程中发生阻塞情况的计数。这里即使在不同 的节点上执行的是相同的子状态过程。但是由于节点的处理速度，等待队列的长 短等因素的影响，从而造成a g e n t 的予状态执行时间瓦是不同的。因此我们采 用巧表示节点x 的a g e n t 状态服务处理性能，用来表示考虑硬件和软件等作 用因素后的节点处理能力，除了以上两个参数之外，l 的大小还依赖于当前节 点中等待资源执行的a g e n t 队列数目，这里我们对等待资源执行a g e n t 的 队列采用先进先出的调度策略，这样当前的a g e n t 必须等待队列中没有比它更前 的a g e n t 时才能进入执行服务状态。 在给出有限状念m o b i i ea g e n t 性能建模中