（计算机应用技术专业论文）具有容错能力的动态合同网研究.pdf

具有容错能力的动态合同网研究 摘要 多a g e n t 系统( m u l t i - a g e n ts y s t e m ) 作为分布式人工智能( d i s t r i b u t e d a r t i f i c i a li n t e l l i g e n c e ) 的重要组成部分，已经迅速成为人工智能研究的 活跃领域。如何分解待分配的任务、求解任务、解决各种各样的冲突，使各a g e n t 互相协作，完成复杂的任务是多a g e n t 理论的核心问题。 合同网协议( c o n t r a c tn e tp r o t o c 0 1 ) 是由r a n d a l ld a v i s 和r e i dg s m i t h 为处理a g e n t 之间的任务分发，针对任务资源分配提出的协调策略，是多a g e n t 系统协同设计思想的关键。动态合同网协议基于经典合同网协议，引入信任度， 能适应多a g e n t 系统开放性、动态性的要求，并减少系统通讯量，占用资源较 少，因此，动态合同网协议的研究成为合同网研究中最重要的问题之一。 通过对多a g e n t 系统特征、动态合同网协议及其改进算法的研究，发现动 态合同网协议及其改进算法存在以下不足：动态合同网协议及其改进算法对系 统环境要求比较严格，在系统中智能主体可能故障的情况下，不具备容错能力， 无法保证系统任务完成率，据此提出研究具有容错能力的动态合同网协议的重 要意义。 本文主要完成以下工作： 1 利用任务时限监测承包商的状态，及时发现故障承包商主体，重新定 义承包商信任度更新规则，避免故障承包商在故障期间仍然参与系统 运算，并提出一种任务二次调度策略，将故障承包商无法完成的任务 二次调度给其他承包商完成，保证系统的任务完成率。 2 引入挥发机制，利用挥发机制保证承包商的信任度与能力保持一致， 任务发布者据此基于信任度最大最小阈值选择承包商，减少系统通信 量和计算量。 3 介绍如何利用多a g e n t 仿真建模平台r e p a s t 进行仿真实验，具体实现提 出的具有容错能力的动态合同网协议，并实验验证具有容错能力的动 态合同网在任务完成率和系统效率方面比动态合同网表现更为优秀。 关键字：多智能体系统容错动态合同网协议二次转发 i i r e s e a r c ho nd y n a m icc o n t r a c tn e tp r o t o c o l wit hf a u l tt o l e r a n c e a b s t r a c t a sa ni m p o r t a n td e p a r t m e n to ft h ed 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 ) ， m a s ( m u l t i a g e n ts y s t e m ) h a sr a p i d l yd e v e l o p e di n t o a l la c t i v ef i e l do ft h e a r t i f i c i a li n t e l l i g e n c er e s e a r c h h o wt ob r e a kd o w nt h ea l l o c a t e dt a s k s ，h o wt os o l v e t h et a s k s ，a n dh o wt or e s o l v ec o n f l i c t sa n dm a k ea l lt h ea g e n t sc o o p e r a t e dt os o l v e t h ec o m p l e xt a s k si sn o to n l yt h ef i r s tp r o b l e mt ob es o l v e di nm u l t i - a g e n tt h e o r y , b u ta l s oo n eo ft h ec o r ei s s u e si nm u l t i a g e n tt h e o r y t h ec n p ( c o n t r a c tn e tp r o t o c 0 1 ) ，w h i c hp r o p o s e db yr a n d a l ld a v i sa n dr e i d g s m i t hi sac l a s s i c a ls t r a t e g ya b o u tt a s ka l l o c a t i o n ，a n db e c o m et h ek e y t e c h n o l o g yi nt h ec o l l a b o r a t i v ed e s i g no fm u l t i a g e n ts y s t e m b a s e d o nt h ec n p , d c n p ( d y n a m i cc o n t r a c tn e tp r o t o c 0 1 ) l e a dt h ec r e d i b i l i t yi n t oc n p , w h i c hc a n a d a p tt ot h eo p e na n dd y n a m i cc h a r a c t e r i s t i co f t h em a s ，a n dr e d u c et h ea m o u n to f t h es y s t e mc o m m u n i c a t i o na n dc a l c u l a t i o n s od c n ph a sb e c o m eo n eo ft h em o s t i m p o r t a n td e p a r t m e n t si nc n p r e s e a r c h a c c o r d i n gt ot h er e s e a r c ho nt h ed c n p a n di t si m p r o v e da l g o r i t h m s ，w ef i n d s o m ep r o b l e m si nd c n pa n di t si m p r o v e da l g o r i t h m s ：w h e nt h ea g e n t si nt h em a s m a yb e c o m ei n v a l i d ，d c n pa n di t si m p r o v e da l g o r i t h m sa r el a c ko ft h ef a u l t t o l e r a n c ea n dc a n ta s s u r et h et a s ka c c o m p l i s h m e n tr a t i o t h i sl e a d sd c n pc a n n o t a d a p tt oa m o r ec o m p l e xe n v i r o n m e n t ，s oi ti si m p o r t a n tt oi m p r o v ead c n pw i t h f a u l tt o l e r a n c e ( f t - d c n p ) i nt h i sp a p e r , w ed os o m ew o r k sf o rt h ef t - d c n p ： i i i 1 u s et a s kd u r a t i o nt oi n s p e c tt h ec o n t r a c t o r sa n dd i s c o v e rt h ei n v a l i d c o n t r a c t o r si nt i m e ，r e d e f i n et h ec r e d i b i l i t yu p d a t i n gr u l e st oa v o i dt h ei n v a l i d c o n t r a c t o r sr e c e i v et a s k s ，a n dp r o d u c eas t r a t e g yf o rt a s kr e a l l o c a t i o nw h i c hc a n r e a l l o c a t et h ei n v a l i dt a s k st ot h eo t h e rc o n t r a c t o r st oa s s u r et h et a s ka c c o m p l i s h r a t i o 2 l e a dt h ev o l a t i l i z a t i o ni n t ot h es y s t e mt om a k et h ec o n t r a c t o r sc r e d i b i l i t y i nd i r e c tp r o p o r t i o nt ot h er e a lc a p a b i l i t y , s om a n a g e rc h o o s ec o n t r a c t o rb a s e do n t h e c r e d i b i l i t yt h r e s h o l d ，w h i c hc a nr e d u c et h es y s t e mc o m m u n i c a t i o na n d c a l c u l a t i o n 3 i n t r o d u c eh o wt ou s ea n de x t e n dr e p a s tt os i m u l a t ea n dm o d e lm u l t i a g e n t s y s t e m ，r e a l i z et h ef t - d c n pp r o p o s e di nt h ep a p e r , a n df m a l l yp r o v et h e f t - d c n pi sm o r ea d v a n t a g ei nt a s ka c c o m p l i s h m e n tr a t i oa n ds y s t e me f f i c i e n c y a c c o r d i n gt ot h ee x p e r i m e n tr e s u l t s k e yw o r d s ： m u l t i - a g e n ts y s t e m ；f a u l tt o l e r a n c e ；d y n a m i cc o n t r a c t o rn e t p r o t o c o l ；r e a l l o c a t i o n i v 广西大学学位论文原创性声明和学位论文使用授权说明 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下完成的，研究e 作所取得的成果和相 关知识产权属广西大学所有。除已注明部分外，论文中不包含其他人已经发表过的研究 成果，也不包含本人为获得其它学位而使用过的内容。对本文的研究工作提供过重要帮 助的个人和集体，均已在论文中明确说明并致谢。 论文作者签名：霜丝翘 一引弱 学位论文使用授权说明 本人完全了解广西大学关于收集、保存、使用学位论文的规定，层j ： 本人保证不以其它单位为第一署名单位发表或使用本论文的研究内容： 按照学校要求提交学位论文的印刷本和电子版本； 学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务： 学校可以采用影印、缩印、数字化或其它复制手段保存论文； 在不以赢利为目的的前提下，学校可以公布论文的部分或全部内容。 请选择发柿时i 日j ： 口即时发命口解密后发布 ( 保密论文需注明，并在解密后遵守此规定) 论文作者签名：绺导师签名：词年l 羁 | 具有容错能力的动态合同网研究 1 1 课题的提出 第一章绪论 由于不断提高的软件服务能力要求，系统中必然需要引入人工智能，因此，作为人工 智能的重要内容，a g e n t 理论【l 】引起科学、工程界广泛重视。a g e n t 理论在上个世纪中期由斯 坦福大学的b a r b a r ah a v e s r o t h 首先提出。a g e n t 理论初期没有受到科学界过多关注，但从 8 0 年代末开始，a g e n t 的理论、技术研究与许多其他领域相互参考和吸收，在很多不同于最 初智能应用的领域得到更为广泛的应用，直到现在依然是智能研究的热门领域。 在此背景下，多a g e n t 系统( m u l t i - a g e n ts y s t e m ，m a s ) 【2 】迅速成为上世纪末智能研究 热点。多a g e n t 系统是为了将一个大的、复杂的系统分割成多个小的、相互通信协调的、容 易管理的子系统。由于复杂系统的实时性、动态性、不确定性、分布性及各个子系统中不 同的知识库、不同的求解方法等，多个子系统之间的冲突不可避免。如何分解待分配的任 务、求解任务、解决各种各样的冲突，使得各个a g e n t 合力完成复杂任务是多a g e n t 理论的 核心问题之一【3 1 。 众多的多a g e n t 协作方式中，使用最为广泛的是合同网协议，已成功应用于很多实际系 统，应用领域十分广阔。合同网协议是针对任务和资源分配的协调策略【4 】。在经典合同网 协议中，任务发布者与承包商的产生、任务的产生、分配都是动态的，灵活性好。但是合 同网协议也存在许多缺陷，例如没有解决系统冲突的识别和消解问题，任务发布者需要评 估大量的标书，系统开销和资源占有率大等等。针对以上缺陷，国内外学者改进了合同网 协议，但是现阶段研究大都是对于静态环境下的友好合作型的合同网协议的改进。而一个 复杂的、动态的环境，其开放性、动态性的特征要求合同网协议可以解决动态环境下的协 同问题，并且具有一定的容错能力来保证系统运行的稳定。因此，具有容错能力的动态合 同网协议的研究成为合同网研究中重要的问题之一。 1 2 课题研究的目的与意义 a g e n t 技术正在迅猛发展，有研究人员指出：十年之i 为a g e n t 技术将影响大多数信息技 广西，o 学硕士学位论文具有容错能力的动态合同网研究 术，很多科技产品将会含有嵌入式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 技术的热点。当前m a 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 的影响， 在系统中存在故障的情况下，能够具有容错能力来保证系统的任务完成率和较高的完成效 率，这具有重要的理论和现实意义。 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 完成， 使得改进后的动态合同网协议具有容错能力，最后利用实验数据分析算法的优越性。 具体来说，论文研究的主要工作和创新点有： 1 概括多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 g e n t ，提出一种任务二次调度策略，将故障主体a g e n t 不能完成的 任务二次调度给其他主体a g e n t 完成，保证系统任务完成率。 2 广西大学硕士掌位论文具有容错能力的动态合同网研究 4 改进动态合同网协议的信任度更新准则，避免故障主体a g e n t 在故障期间仍然参 与系统运算，减少不必要的系统通讯量和系统计算量的浪费，并且能力强的主体 a g e n t 能在恢复正常后较快地重新获得任务发布者的信任，提高系统效率。 5 利用仿真模拟软件r e p a s t 进行仿真建模实验，继承和扩展r e p a s t 提供的基本函数与 接口对经典动态合同网和具有容错能力的动态合同网进行仿真建模，并进行大量 实验。通过分析实验结果，得出具有容错能力的动态合同网协议在更为复杂的环 境下，能更好地保证系统任务完成率和系统效率。 1 4 本文的组织结构 本文的章节内容安排如下： 第一章主要分为三个部分。首先，简要介绍多a g e n t 系统的发展背景。其次，介绍m a s 中任务协作协议的重要性，提出在更加复杂开放的应用环境下，研究具有容错能力的任务 协作协议的重要意义。最后给出本文研究的意义、主要工作及论文的组织结构。 第二章介绍论文的相关知识，主要分为三个部分介绍。首先，介绍多a g e n t 系统的基本 定义与性质，然后简要介绍多a g e n t 系统的协作类型和几种主要的协作方法，最后介绍实时 调度的相关知识。 第三章分为三个部分具体介绍具有容错能力的动态合同网。首先介绍动态合同网协议 的相关知识及其改进算法，通过分析得出动态合同网协议及其改进算法存在的缺陷。然后， 总结提出具有容错能力的动态合同网协议需要解决的问题，并具体介绍算法相应的解决策 略，最后给出算法的具体流程。 第四章实验与分析分为三个部分。首先简要介绍选择仿真工具r e p a s t 的原因。然后介 绍r e p a s t 平台的主要功能模块和建模流程，据此给出利用r e p a s t 实现本模型的详细设计，最 后进行实验和分析。通过对实验数据的研究分析进一步说明本文提出的具有容错能力的动 态合同网协议能更好地适应更加复杂的动态环境。 第五章对全文工作进行总结并对进一步的研究工作进行展望。 3 广西大学硕士学位戳汶具有容错能力的动态合同网研究 第二章相关理论概叙 2 1 a g e n t 的定义与特性 a g e n t 理论【5 加】是一个新兴的领域，所以当前学术界对a g e n t 没有确切的定义。通常我们 认为a g e n t 是一个拥有高度自治能力的实体( e n t i t y ) ，不同于一般的程序中的类、方法，a g e n t 可以根据自身的相关信息和能力( 资源、状态等) 对外界动态环境做出自主反应，通过各 种手段( 规划、推理、决策等) 解决问题并取得预期结果。一般来说，a g e n t 具有以下特性 f l l 】【1 2 】： 1 自主性( a u t o n o m y ) ：a g e n t f l 邕在没有用户或其它a g e n t 的直接影响和指导的情况下持 续运行，具有属于其自身的有限计算资源和局部于自身的行为控制机制。自主性 是将a g e n t 与其它抽象概念区分的重要特征。 2 反应性( r e a c t i v i t y ) ：a g e n t 能, 够感知所处的环境( 可能是物理世界与它进行交互的其 它a g e n t 等) ，并能对环境中发生的相关事件( j t i i a g e n t 间的交互和通讯) 做出适时反 应。 3 社会性( s o c i a l a b i l i t y ) ：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 完成相关的活动。 4 自发性( p r o a c t i v e n e s s ) - a g e n t 并不是简单地对环境中的事件做出反应，而是表现 出某种目标指导的行为。也就是说，为了实现其某种预期的目标，在一定的情况 下，a g e n t 能够根据外界环境的动态变化，做出基于该目标的判断和行为。 这些特性是学术界公认的a g e n t , g , 须拥有的基本特征，学术界将具备这些基本特性的 a g e n t 称为弱a g e n t 。但是随着a g e n t 理论的研究与发展，人们认为a g e n t 应该体现更多的人 类的特有性质，比如目的、信念和期望等心理特征，甚至情感特征【1 3 1 ，因此，认为a g e n t 还应具有友好性、合理性、交互性、协作性等特性，也将这类a g e n t 称为强a g e n t 。本文为 4 广西大学硕士掌位论文具有容错能力的动态合同网研究 了使m a s 能适应更为复杂的应用环境，假定研究的主体a g e n t j 丕具有诚实性的特性，即主体 a g e n t 为了自身的利益，可能隐瞒对自己不利的事实。 2 2m a s 的定义与特性 实质上，多a g e n t 系统【1 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 系统可以这 样表示： m a s - ：- - - ， 其中a g e n t s 是系统中的a g e n t 的集合，e n v i r o n m e n t 是系统环境。当处于网络环境时，多 a g e n t 系统具有开放性，a g e n t 具有动态特性。 从问题求解的角度上说，通过a g e n t 交互协调形成的m a s 整体，其总体问题求解能力可 以大于各个a g e n t 个体所具有的问题求解能力的简单相加。由于认知、资源等的局限，处于 其中的a g e n t 个体智能具有有限理性，因此，交互合作，互相依靠或牵制，是a g e n t 个体完 成自身目标，实现生存和发展的必然选择1 5 h 1 7 1 。 多a g e n t 系统除了就有单个a g e n t 特性以外，还具有以下特性【1 8 】【1 9 1 ： 1 自治性( a u t o n o m y ) ：一个a g e n t 不能基于自身利益和兴趣来强迫另一个a g e n t 提供某 项服务。 2 协作性( c o o p e r a t i o n ) ：在m a s 中，各个不同的a g e n t 有各自不同的动机，这些a g e n t 必须互相通信、相互合作来解决问题。 2 3m a s 协作方法的分析 2 3 1 协作的涵义 协作【2 0 1 1 2 1 1 是m a s 的一项重要的特征，是m a s 中的a g e n t 间互相通信、使得m a s 的各个 a g e n t 作为一个整体运行求解的进程。当系统中的a g e n t 接到外界服务请求时，首先尝试自 身独立解决问题，如果自身能力、资源不足以解决问题，则与m a s 中的其他a g e n t 进行协作， 选择恰当的a g e n t 并将自身无法完成的部分交给该a g e n t 完成。 5 具有容错能力的动态合同网研究 2 3 2 协作的必要性 协作在m a s 中具有中心地位，有效的协作对m a s 的运行以及系统设计意图的实现产生 积极的影响1 2 2 】【2 3 1 。 1 可以防止系统中a g e n t 不至于发生混乱：由于自身条件和能力的限制，a g e n t 对整个 系统只有局部视图，并且拥有各自的目标和知识，这些局部的东西可能影响其它 a g e n t 的行为和系统效率； 2 避免死锁和活锁； 3 提高系统的运行效能。 2 3 3m a s 协作类型 由于l v i a s 的设计理念、完成任务的方式、需要求解的任务以及a g e n t 的多样性，在m _ a s 中，a g e n t 之间进行的协作类型很多，大致可以分为以下5 类2 3 1 ，见表2 1 。 表2 - 1m a s 协作分类表 t a b l e2 - 1t y p eo fc o l l a b o r a t i o ni nm a 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 也可能还具有与 全局目标无直接联系的局部目标。 自私型 系统中的智f l 邕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 3 4m a s 的协作方法分析 常见协作方、法【矧有：基于承诺和约定的协作、组织架构协作、结果共享、合同网等。 1 基于承诺约定的协作方法 承诺指系统中的a g e n t 对完成某类任务或行为的保证；约定是在动态环境中监控a g e n t 6 广西大掌硕士学位论文 具有容错能力的动态合同网研究 说作承诺的状况的方法。前者使a g e n t , s , 够在做出自身行为决定前预先估计其它a g e n t 的行 为，后者使得m a s 中的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 将执行结果逐级向上报告。 3 结果共享模型 系统中的各个a g e n t 都无法靠自身独立完成任务，通过交换各自求解的阶段性结果求解 问题，逐步获得最终的结果，如图2 1 所示。 a g e 刚七絮果) a g e n t 2 结果2结果3 a g e n t 5 j 天i 泓 ， 结果2 f a g e n t3 f a g e n t4 1 llj 图2 1 结果共享协作方法 f i g 2 1s h a r i n gt h er e s u l t so f t h ec o l l a b o r a t i o n 5 合同网 合同网协议( c o n t r a c tn e tp r o t o c o l ，c n p ) 2 5 1 2 6 】是i 扫r a n d a l ld a v i s 和r e i dg s m i t h 提出的经典协调策略，工作方式是采取“招标投标中标”的形式，由任务发布者向系统中 的所有承包商发布任务，进行招标，各个承包商根据自身能力和资源进行投标，任务发布 者在所有标书中进行选择，最后与选定的承包商签订合同，将任务发布给该承包商来完成。 承包商完成任务后，将结果返回给任务发布者，标志着任务结束。合同网中的a g e n t 分为两 类：负责发布任务，评估标书的任务发布者a g e n t ( d i s t r i b u t o r ) 和负责对任务进行投标，并 在中标之后负责完成任务将结果返回给任务发布者的承包商a g e n t ( e m p l o y e e ) 。其协议流程 7 具有容错能力的动态合同网研究 如图2 2 所示 招标准 备 一律锌馆 获得标 布 书 、 1 任务评 估 接收标 投标r 书 ( 3 ) l 评估标 书 授予任接受任 、 务务 0 执行任 务 图2 - 2c n p 工作原理 f i g 2 - 2t h ep r i n c i p l eo fc n p 步骤l 任务发布：任务发布者获得新的需要发布的任务，宣布招标开始，向系统内所 有的承包商进行招标； 步骤2 投标：接收到任务发布者发出的招标信息后，各个承包商根据自身能力和资源 对任务进行评估，生成各自的标书，将标书返回给任务发布者进行评估； 步骤3 评估标书：收到承包商返回的标书后，任务发布者按照规则对承包商的标书进 行评估，选出最优的标书，与发出该标书的承包商签订合同； 步骤4 中标：承包商收到任务发布者发出的合同后，表示合同成立，承包商开始执行 任务，最后将任务结果返回给任务发布者。 合同网协议自从提出以来，得到广泛应用，但经过对现有各种资料研究发现，经典合 同网协议还存在以下不足： ( 1 )任务发布者向系统内所有的承包商进行招标，需要评估的标书过多，任务发布 者负载较大，容易导致瓶颈问题； 8 具有客错能力的动态合同网研究 ( 2 )承包商可以对所有任务发布者发起的招标进行投标，可能导致承包商资源的浪 费； ( 3 )任务发布者不会通知某个任务是否已经发布给承包商完成，其他承包商可能仍 然对已经中标的任务进行投标；承包商可能在无法接收新任务的情况下仍然对任务 进行恶意投标，导致任务发布者需要评估大量无意义的标书，浪费资源和时间； ( 4 ) 对于非友好型多a g e n t 系统，合同网协议效率差。 针对以上不足，国内外学者对合同网协议进行研究改进，目的是改进算法表现，提高 算法效率，比较成功的改进算法包括：接收者限制( a u d i e n c er e s t r i c t i o n s ) 、集中选择( f o c u s e d a d d r e s s i n g ) 2 7 、基于范例的推理( c a s e b a s e dr e a s o n i n g ) 2 8 1 、可信度模型( c r e d i b i l i t ym o d e l ) 1 5 l 和动态合同网协议( d y n a m i cc o n t r a c tn e tp r o t o c 0 1 ) 1 2 9 等。 上述几种对经典合同网的改进算法中，在实际应用中很多前提假设下都无法实现【2 9 】。 另外，这些研究大都集中在静态环境下合同网协议的改进，无法适应动态的环境变化。 张海俊、史忠植等在动态合同网协议【2 9 】一文中，参考人工智能领域里的响应阈 值模型【3 0 1 ，引入信任度的概念，提出一种动态合同网模型( d y n a m i cc o n t r a c tn e tp r o t o c o l ， d c n p ) 。该模型利用任务发布者对于承包商的信任度的大小来选择承包商，并根据任务完 成情况动态更新信任度，能很好地适应动态环境，具有重要的研究价值，将在第三章详细 介绍其算法思想和算法流程。 2 4 实时调度策略简介 2 4 1 实时调度策略的简单分类 实时调度策略是为了解决计算资源冲突，将资源进行合理调度以满足对任务完成时间 上的限制。图2 3 给出实时调度算法的分类。 9 广西大学硕士掌位论文 具有容错能力的动态合同网研究 软实时调度算法硬实时调度算法 静态调度算法 抢占式实时调 度算法 非抢占式实时 调度算法 抢占式实时调 度算法 非抢占式实时 调度算法 图2 3 实时调度算法分类图 f i g 2 - 3t h et y p e so ft h er e a l - t i m es c h e d u l ea l g o r i t h m 2 4 2 几种常用的调度算法 1 单调速率算法( r a t em o n o t o n i ca l g o r i t h m ，r m ) 3 6 1 单调速率算法是一种基于静态优先级的抢先调度算法。它按照等待调配的任务执行周 期划分固定的优先级，任务执行周期较短的任务给予较高的优先级。优先级一旦确定，则 在运行时不能被更改。调度器总是选择具有最高优先级的任务首先执行。但是r m 算法无法 适应优先级动态变化的情况。 2 最早时限优先算法( e a r l i e s t d e a d l i n e f i r s ts c h e d u l i n ga l g o r i t h m ，m d f ) 最早时限优先算法是基于动态优先级的最优动态抢先算法，它用任务时限作为优先级。 拥有最早时限的任务给予最高优先级。运行时，调度器从等待执行的任务集中选择具有最 高优先级的任务优先执行。最早时限优先算法优势在于是其优先级动态生成，因此任务执 行顺序可能随时发生改变。 3 最小时间宽限优先算法( m l f ，m i n i m u m - l a x i t y f i r s ts c h e d u l i n g a l g o r i t h m ) 最小时间宽限优先算法为任务集的每一个任务分配一个时间宽限( l a x i t y ) ，时间宽限是 对任务调度可延迟时间的度量参数。时间宽限s 表示任务可以延迟s 时间单位而不影响任务 的执行结果；时间宽限为零则表示此任务必须立即被调度执行，否则将导致任务失败。拥 1 0 广西大学硕士学位论文 具有容错能力的动态合同网研3 宅 有最小时间宽限的任务获得的优先级最高，反之则得到最低优先级。每一次调度完成后， 调度器重新计算所有待完成任务的时间宽限。 最小时间宽限优先算法和最早时限优先算法的区别在于最小时间宽限优先算法将任务 所能延迟等待的时间计算在内。 2 5本章小结 本章首先简单介绍a g e n t 和m a s 的有关知识和理论，然后对m a s 的协作方法进行具体 分析，介绍几种常见的协作方法，并重点论述合同网的基本思想及其相关的改进算法，最 后简单介绍实时调度策略的相关知识。 广西大掌硕士学位论文具有容错能力的动态合同网研究 第三章一种具有容错能力的动态合同网 3 1 动态合同网概述 3 1 1 动态合同网的理论 在上一章介绍的几种对合同网协议改进方案中，张海俊、史忠植所提出的动态合同网 协议【2 9 1 ( d y n a m i cc o n t r a c tn e tp r o t o c o l ，d c n p ) 利用信任度对承包商进行选择，能很好地 适应动态环境的应用，是一种高效的改进算法。 动态合同网协议参考人工智能领域中的响应阈值模型，引入信任度的概念。信任度是 指任务发布者发布任务时对各个承包商能够完成某类任务的能力的信任程度。承包商的信 任度越大，则其响应阈值越低，获得任务的几率越大，；反之则获得任务的几率越小。发布 任务时，任务发布者根据承包商的信任度以一定的概率确定承包商，避免接收所有承包商 的标书，减小系统通信量。承包商的信任度大小与其完成任务情况动态相关，承包商完成 某类任务，则任务发布者增加其信任度；反之降低信任度。 由此可见，动态合同网协议通过对系统中a g e n t 信任度的更新选择，可以适应a g e n t 能 力及外部环境的动态变化，减少系统通信量。 动态合同网协议有几个潜在约定： 1 任务发布者具有系统中的a g e n t 的相关信息，并能与a g e n t 进行交瓦。 2 对于同一种任务，系统中不同的a g e n t 完成任务所需的时间不同( 能力有大小之 分) 。 3 发布的任务具有原子性，不可再分。 3 1 2 动态合同网的具体算法 动态合同网协议的算法具体流程如下： 输入：主体集a ( a l ，a 2 ，a m ) ，任务集t ( t l ，t 2 ，t n ) ； 1 2 广西大学硕士学位论文具有容错能力的动态合同网研究 输出：任务完成记录。 初始化：信任度c = c o = o l i = l m ，j = 卜n ) ( 1 ) 若( t 为空) ，输出任务完成记录，程序结束； ( 2 ) 任务发布者从t 中选择任务1 ；i ，属于第t j 类任务； ( 3 ) 若c f ，= 0 ，转( 5 ) ；否则，按概率p ；选中承包商a g e n t ； 鼽毋：巨2 l 。 ( 1 0 ) 任务发布者更新承包商的信任度：若完成任务，c o - c ，+ 耐；否则，勺一 q 一 孝严。砂 。转( 1 ) ( 其中，耐与是常量，表示承包商信任度的增减。通常磊删 q m a x 且此承包商还可以接收新的任务，则任务发布者直接与该承 包商签订合同；若所有c i i q m 舣的承包商无法接收新的任务，则任务发布者根据公式3 1 概 率p 选择承包商签订合同；若对于系统中所有空闲的承包商( 缓冲池未满) ，都有c i j q m i n ， 则任务发布者根据公式3 2 向所有承包商招标。 1 6 具有容错能力的动态合同网研究 其中， c ；专 尸，：旦l c 0 ；l ( 3 1 ) 万干磊弦瓦西n i 灭互丽c t l + 6 ， q m i n c i j q 。，且缓冲池未满 o 否则 ( n 为该a g e n t 完成任务的数目，i n v a l i d n u m ( a g e n t j ) 为该a g e n t 出错无法完成任务的 数目，b i 为承包商对于完成此任务的预测代价) 只= 若c 盯 o m i n 且口f 空闲 否则 ( 3 2 ) 为了使得研究应用更为广泛，假定m a 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 都是不诚实的，在发生故障后选择隐瞒 事实，需要任务发布者主动识别是否属于故障主体a g e n t 。 在f t - d c n p q b ，参考实时系统的实时调度策略，引入时限【3