（计算机软件与理论专业论文）基于期望效益的网格作业调度算法研究.pdf

摘要 网格计算( g - r i d ) 技术是近年来国际上兴起的重要信息技术，其目标是实现对 地理上广泛分布的大量网上资源进行共享。其中，任务调度是网格技术的重要组成 部分，主要包括资源发现、资源匹配和任务执行3 个部分。它要根据任务需求采用 适当策略把不同的任务分配到相应的资源结点上。由于网格系统的异构性，以及应 用程序对于网格系统资源的不同需求，使得任务调度变得尤其复杂。又由于用户资 源可动态进入网格系统，使网格资源调度成为一大难题。其中，利用信任控制技术 是一个有效的方法。 为此，本文在对网格计算和网格任务调度的知识背景以及该领域研究现状进行 分析的基础上，研究了当前信任管理在网格资源调度方面的应用。本文主要运用 d c m p s t c r - s h a t e r ( d s ) 理论描述网格节点信度函数、似然函数的表示方法与更新策略。 利用次序时间影响因子来计算历史交易数据对信任度的影响，并初步证明了次序影 响因子的取值范罔。同时，本文将网格节点为获得信任所付出的代价作为检测网格 节点的可信度的依据，提出了一种基于期望效益的m i n r a i n 调度算法。期望信任效 益函数是某个作业在网格节点执行的预期效益，依此来预测作业的执行情况。 仿真实验表明，采用历史交易数据能比较准确的判断网格节点的可信状况，而 且本文提出的期望信任效益驱动算法在效益方面优于传统m i n - i n i n 算法，能提高网 格系统的资源利用率。 硕士研究生郝永生( 计算机软件与理论) 指导教师许日滨教授 关键字：信任；服务：资源发现：任务调度 a b s t r a c t g r i di sa ni m p o r t a n ti n f o r m a t i o nt e c h n o l o g yi nw o r l di nr e c e n ty e a r s i tm a k e su s e r s c a ns h a r em a n yd i f f e r e n tr e s o u r c e si nd i f f e r e n ta r e a s t a s ks c h e d u l ei sa l li m p o r t a n tp a r t o ft h i sf i e l d a c c o r d i n gt ot h et a s kc o n d i t i o n , s c h e d u l ea l l o c a t e sa p p r o p r i a t er e s o u r c e st o d i f f e r e n tt a s k sb yr a t i o n a ls t r a t e g i e s t h ed i f f e r e n tc o n s t r u c t sa n dd y n a m i co ft h e 酊d s y s t e ma n da p p l i c a t i o n si nt h eg r i dr e q u i r ev a r i e so fr e s o u r c e sb r i n gt a s ks c h e d u l em o r e c o m p l e x t h e r e f o r e ，i nt h i sp a p e r , b a s e so nt h ea n a l y s i so fg r i ds c h e d u l i n g ，i ti n t r o d u c e st h e a p p l i c a t i o no ft h et r u s tm a n a g e m e n to ng r i d t h e n , w eu s ed e m p s t e r - s h a t e rt h e o r y d e s c r i b e rt h et r u s tf u n c t i o n , t h el i k e l i h o o df u n c t i o no fg r i d m a i ni n n o v a t i o np r o j e c ti s t h eb a s e de x p e c tc r e d i tp r o f i td r i v et a s ks c h e d u l em e t h o d t h ee x p e c tp r o f i tf u n c t i o ni st h e f o r e c a s tg a i no fo n et a s ke x e c u t e so ng r i dn o d e t h i sp a p e rp r o p o s e st h ee x p e c t a t i o nt r u s t b e n e f i td r i v e ng r i dj o bs c h e d u l ea r i t h m e t i c t h ev a l u eo ft h ee x p e c t a t i o ni r u s tb e n e f i tf u n c t i o ni s p r e d i c t i o nb e n e f i to fac e r t a i nj o bw h i c he x e c u t e si ng r i d s i m u l a t i o ns h o w st h a te x p e c t a t i o nb e n e f i td r i v e na r i t h m e t i ci sb e t t e rt h a nt r a d i t i o n a l m i n r a i na r i t h m e t i ci nb e n e f i ta n di ta l s oh a sg o o dp e r f o r m a n c ei nb e n e f i t p o s t g r a d u a t es t u d e n t ：y o n g s h e n gh a o ( c o m p u t e rs o f t w a r e & t h e o r y ) d i r e c t e db yp r o f e s s o r ：y u e b i nx u k e y w o r d s ：t r u s tr e l a t i o n s h i p ；s e r v i c e ；j o bs c h e d u l e ；r e s o u r c ea l l o c a t i o n 攻读学位期间的研究成果 学位论文独创性声明 本人声明，所呈交的学位论文系本人在导师指导下独立完成的研究成果。 文中依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法律意 义上已属于他人的任何形式的研究成果，也不包含本人已用于其他学位申请的论文 或成果。 本人如违反上述声明，愿意承担由此引发的一切责任和后果。 论文作者签名： 哳孓v日期：彦口彬年珈蛔 学位论文知识产权权属声明 本人在导师指导下所完成的学位论文及相关的职务作品，知识产权归属学 校。学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权利。本人 离校后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍 然为青岛大学。 本学位论文属于： 保密口，在 年解密后适用于本声明。 不保密闼 ( 请在以上方框内打“4 ”) 用) 论文作者签名： 导师签名： 胁l 锄争扩沁 1 百军隧 日期：妇年妨f 泊 日期弘诱年r 月i ( 本声明的版权归青岛大学所有，未经许可，任何单位及任何个人不得擅自使 4 7 第一章绪论 第一章绪论 通过使用网格技术，人们希望能够实现廉价计算，合作存取各种数据信息， 提供广域多媒体应用等等。然而，由于网格计算环境相对于网络计算环境有着更为 复杂的特征，实现有效的网格计算还有很多需要解决的问题。其中，在网格环境里 如何有效地管理资源的可靠性是影响网格计算最重要因素之一。又由于资源的广域 性、自治性、动态性，传统的集中资源分配方式既难以实现也不能满足不同应用对 资源需求的差异性。其中，信任度管理是解决这些问题的有效方法之一。 1 1 网格的概念 网格是构筑在互联网上将地理上广泛分布的大量计算资源( 包括高速互联网、高 性能计算机、大型数据库、传感器、远程设备、p c 等) 融为一体，让资源共享和协 同问题求解能在一个动态的、多结构的虚拟组织中进行，为人们提供更多的资源、 功能和交互性。网格系统包括网格的物理资源及其逻辑上的抽象，它充分吸收各种 资源，并将它们转化为一种随处可见的、可靠的、标准且经济的计算能力。 人们常常会问，传统分布式系统与网格有什么区别? 从学术角度讲，网格是分布 式系统的一种形态，但网格不同于传统的分布式系统。它是松耦合的环境，有异构 性和动态性，有跨多个管理域多样和动态的资源共享关系，传统分布式系统大多是 基于同构平台的相对封闭的系统，对资源的定义局限于某些特定的数据和软、硬件。 而网格是一个开放的系统，为异构资源建立了一个共享平台，网络上任何资源都可 以共享和利用。简言之，它是一个广域网的分布系统，支持分布式应用，这些应用 可共享网格中的所有资源，能提供满足要求的服务质量。传统互联网实现了计算机 硬件的连通，w e b 实现了网页的连通，而网格则要实现互联网上分散在不同地理位 置资源的全面连通，目的为把整个互联网整合成一台“虚拟的超级计算机”，实现 计算资源、存储资源、通信资源、软件资源、信息资源、知识资源的全面共享。由 于技术和方法学革命性的变化，使科学界开此应用网格技术。计算技术的进步促使 应用和数据的空前集成。网格将与i p v 6 技术一同引领“第三代互联网浪潮”。全 球应用最广、最成熟的网格操作系统o l o b u s 源于美国，它对全世界的网格研发工作 起到了巨大的推动作用。该项目要开发一个面向科学计算的基本软件基础设施，利 用这一设施，把不同地理位置上的计算资源和信息资源集成起来。该项目还研究网 格计算的关键理论，具体包括资源管理、网格安全、信息服务、数据管理等：开发支 持网格计算的工具软件和网格应用程序：帮助规划和组建大型的网格试验平台，前 一阶段的研究成果显著。图1 1 为未来用户的逻辑视图，他体现了通过“信息插座” 获得网格服务的一种前景。 青岛大学硕士学化论文 ii 一匦弧逦； 爹：”9 ”信息插座” 绥 么玉 互 连 网 络 u lu l uiu i q 一 - - i 。一一llll 、。_ - _ ， 图：1 1 网格系统的用户逻辑视图 1 2 网格的特性 网格的技术特征包括：资源共享、协同工作，这两项是网格的基本技术要求：通 用开放标准、非集中控制、非平凡服务，这三项是l a nf o s t e r l 2 】出的网格检验标准。 分布性：这是网格的最主要的特点。组成网格的各种资源是分布在地理位置不同 的地方，而不是集中在一起的，跨越的地理范围较广。 自治性：网格的资源有自己的本地管理机构或处在本地管理机构的管理之下，网 格资源或强或弱的具有本地自治能力。网格管理系统必须尊重本地管理者，迁 就本地管理策略，不能把网格的意愿强加到资源上，更不能替换本地管理系统。 网格只能根据资源加入网格时与网格系统签署的谅解备忘录合理地使用资源， 在尊重谅解备忘录的基础上，网格系统可以把某个资源强制授权给请求用户使 用。 异构性：网格涉及的资源类型多样，规模较大，分布在不同的地理位置上。表现 在异地的地理位置，异构的管理域，异构的操作系统等等。 扩展性：网格的扩展性要求体现在规模、能力、兼容性等几个方面。网格的设计 和实现必须考虑到新的资源能否很自然地加入到网格中，并与原来的资源联合， 共同发挥作用，不降低网格计算的性能。为了建造9 d 9 格，必须部署一系列相关 2 第一章绪论 服务。这其中包括一些底层的服务，如安全性管理、信息服务、目录服务、资 源交易、资源分配和服务质量。 动态性：网格中的资源可以自由地随时加入和离开网格系统，网格资源的可获得 性是随时间的变化而动态变化的，一个网格资源贡献给网格用户使用的潜力是 随时间的变化而动态变化，并且网格资源的负载也是动态变化的。例如，一台 超级计算机，在资源所在地的白天工作时问段，它可能只提供1 0 的计算能力给 网格用户使用，甚至可能希望能从网格之中获得资源。但晚上，则可能提供9 0 的计算能力给网格用户使用。在特殊情况下( 周日) ，可能把所有的资源给其他 网格用户使用。 1 3 本文研究背景 近年来，网格计算得到了许多政府机构、学术界和产业界的共同关注，美国自 然科学基金会自1 9 9 7 年起先后启动了先进计算伙伴计划p a c i 、分布式万亿级计算设 施d t f 和增强的分布式万亿级计算设施e d t f 计划计划，美国能源部2 0 0 1 年启动了 s c i e n c eg r i d 计划，美国国防部2 0 世纪9 0 年代末启动了规模宏大的全球信息网格g i g 计划，拟于2 0 2 0 年完成；欧盟于2 0 0 0 年和2 0 0 1 年先后开展了包括欧洲网格计划 ( e u r o g r i d ) 、数据网格计划( d a t a g r i d ) ，以及e g e e ，c o m g r i d 等在内的数十个网格 重大项目；英国2 0 0 1 年启动了e s c i e n c e 计划。目前美欧的主要大学和科研机构都已 基本形成了基于网格进行资源共享与协作的实验环境，开展了许多典型应用。自2 0 世纪末，我国也实施了多项网格研究计划和重大项目，如c n g r i d ，c h i n a g f i d 和 n s f c g r i d 等，投入力度和应用领域不断加强，取得了显著的结果。 以前的i n t e m e t 只是给一定的用户主要是学者和科学家提供有限的服务。现在， 它已经发展成为一个流行的工具，用来提供大范围的服务。将来，它可以被任何人 用来在任何地方进行商业交易，这也将带来越来越多的不确定性和安全隐患( 比如恶 意攻击或者由于在线实体的疏忽而引发的安全问题) 。现有的一些安全问题有：病毒、 特洛伊木马、嵌入到文档中破坏含有敏感财政信息的数据库等等。普通的用户不具 有专门的技术和经验来识别在线交易中潜在的安全隐患。这就需要给用户提供一种 信任评估机制，使得用户能够评估一个实体的可信度。在网格环境中，由于网格节 点的自治性，动态性，这使问题更加复杂。其中，信任度管理是其中的一个有效解 决方法。 目前，基于信任机制的作业调度算法已经取得了很大进展。m b l a z e 3 】等人首次 提出信任管理的概念，并在此基础上发展出了相应的信任管理信息系统 p o l i c y m a k e r l 4 1 。a l f a r e za b d u l 5 】提出了基于信任域的信任模型，将网格划分成若干自 治域，将节点问信任关系分为域内信任关系和域间信任关系，处理这两种不同的信 青岛大学硕士学位论文 任关系。d o g a n t t 6 l 和s h a n s h a ns o n g t7 提出了最小化失效率的网格信任调度框架和调度 算法。2 0 0 2 年a z z e d i n 与m a h e s w a m n 【8 】等人将“信任”融入网格资源管理，提出了基 于信任因素的负载最小化算法。袁禄烈9 等提出了基于信任推荐模型，在参考人际 关系信任模型的基础上，提出直接信任，间接信任和综合信任，利用d s 理论将推荐 证据组合为间接信任，进一步将直接信任与间接信任组合为综合信任。李景涛等【l o 】 提出了基于相似度加权推荐的p 2 p 环境下的信任模型。 1 4 存在的问题 尽管众多的研究者对计算网格做出了大量的研究工作，并且其中也不乏开创 性，但是仍然存在以下问题，制约了计算网格的发展： ( 1 ) 每个网格结点资源数量难以预测【1 1 】。网格结点可以自主参与网格计算， 而这取决于网格结点的资源。所以网格结点不但有决定是否参与网格计算的权力， 也有决定提供多少资源的权力。要实现网格结点资源合理利用，必须有一套机制来 合理调度资源。由于可能存在恶意结点，更增加了网格资源调度的难度。 ( 2 ) 由于网格恶意结点的存在，必须提供机制，来制约恶意网格的行为1 1 2 , 1 3 。 现行的基于信任推荐及其他方式，从某一方面解决了问题，本文试图从获得信任的 过程来实现网格结点可信度的监督。 ( 3 ) 调度机制与作业类型分离 1 3 , 1 4 。由于网格中有多种类型作业，本文根据 相关文献【4 3 】，分为强信任度型作业，弱信任型作业，和无信任型作业。由于这种分 离机制，可能导致调度效益损失。 1 5 本文主要工作和结构 本文在d s 推理理论的基础上，提出了期望效益驱动的m i n r a i n 算法能够较好的 提高整个网格系统的资源利用率。通过对网格节点可靠性的估测，能够部分的避免 作业效益损失，并可以避免浪费可靠性服务。随着作业数的增加，推测可信度就能 更好的预测网格节点所提供的资源数量，从而能更好的提高整个网格系统的效益。 仿真实验表明期望信任效益驱动算法在效益方面优于传统m i n m i n 算法，提高了网格 系统的资源利用率。本文结构如下： 第一章首先简单介绍了网格计算的应用和研究背景；讨论了当前的研究现状和 存在的问题：接着阐述了本文要研究和解决的问题以及采用的研究策略。 第二章描述了几种典型的网格系统。包括五层沙漏模型，计算经济的网格体系 结构g r a c e ( g r i da r c h i t e c t u r ef o rc o m p u t a t i o n a le c o n o m y ) ，开放式网格服务体系 结构o g s a ( o p e n g r i ds e r v i c ea r c h i t e c t u r e ) 。 第三章对信任机制进行了描述，及其在相关领域的应用与发展，并且对于网格 环境下的信任机制进行行了分类。 4 第一章绪论 第四章探讨信任模型及其分类。 第五章利用推理理论对网格调度的可信度进行分析，通过期望信任效益来估计 网格资源的调度效益。在此基础上提出基于期望效益的网格资源调度算法，并完成 其模型设置。 i 第六章仿真实验。主要用于测试网格的影响因子的敏感度，在此基础上，将基 于信任效益的调度算法与传统m i n - m i n 算法进行比较，说明这种算法具有一定的优 越性。 第七章对整篇论文进行总结，并对未来工作进行展望。 青岛大学硕士学位论文 第二章网格体系结构 当前网格发展面临的主要问题是统一标准，网格体系结构的主要功能是划分系 统基本组件，指定组件的目的与功能，刻画组件之间的相互作用，整合各部分组件。 当前已经提出并实现了若干种合理的网格体系结构。下面介绍目前影响比较广泛的 几种网格体系结构：网格协议体系结构( g r i dp r o t o c o la r c h i t e c t u r e ) 和计算经济的网格 体系结构g r a c e 模型，前者以g l o b u s 和开放网格服务结构o g s a 为代表。 2 1 五层沙漏模型 l a nf o s t e r i 2 】于2 0 0 1 年提出了网格协议体系结构g l o b u s ，当时被认为是网格建 设的核心，是标准化的协议与服务，并可与i n t e r n e t 网络协议进行类比。该协议建立 在互联网协议之上，以互联网协议中的通信、路由、名字解析等功能为基础。计算 网格的协议分为构造层、连接层、资源层、汇集层和应用层共五层结构。 构造层是网格中可以被共享的资源所在层，该层包括计算设备、存储设备、目 录、分布式文件系统、分布式计算机池、计算机集群、网络、传感器、贵重仪器以 及其他设备。该层的功能是向上提供网格中可共享使用的资源接口，网格通过支持 设备共享的协议来访问本地设备。 连接层是网格中处理通信与授权控制的核心协议层。构造层的各种资源间的数 据交换都在这一层的控制下实现。各种资源间的授权验证、安全控制也在这里实现。 在此协议中提供一次登录、委托授权、局域安全方案整合、基于用户的信任关系等 功能。 资源层的作用是网格中对单个资源实施控制，与可用资源进行安全握手，对资 源进行初始化，监测资源运行状况，统计与付费有关的资源使用数据。该层使用连 接层的通信和安全协议，实现资源共享的安全协商、启动、控制、监控、记账、付 款等。资源层协议有信息协议和管理协议两种。信息协议用来获得关于资源结构和 状态的信息，管理协议用来协商访问和共享资源。 汇集层的作用是将资源层提交的受控资源汇集在一起，供应用程序共享使用。 汇集层提供目录服务、资源分配、日程安排、资源代理、资源监测诊断、网格启动、 负载控制、账户管理等功能，协调多个资源之间的工作，有跨资源集合的交互协议 和服务。 网格的最上面一层是应用层，网格应用层包括代码和网格调用两部分。网格应 用可以调用网格各低层提供的有用服务，如资源管理服务、数据访问服务、资源发 现服务等。为便于网格应用程序开发，需要构建支持网格计算的库函数。应用程序 通过服务调用网格上的资源来完成任务。其结构如下图所示： 6 第二亭叫格体系结构 应用层 连接层 j i _ | 构造层 汇聚层 资源层 图2 1 五层沙漏模型 2 2 计算经济的网格体系结构g r a c e 澳大利l l ( m o n a s h 大学的b u y y a f ”】教授基于早期对巾场机制在分布式系统中应用 的研究成果，促进了经济学理论在网格中的运h j 并开发了g r i d b u s e c o g r i d ，深入探 讨j ，网格环境中的犟于经济学的分布式资源管理和调度问题，基于。系列应用组件 构造了一个计算经济的网格体系结构g r a c e 。下图是一个融入了价格浮动机制的 g r a c e 模型州。 图2 2g r a c e 模型 g r a c e 是一个基于多种经济。学模型之上的分布的、町计算的经济! 学体系框架， 用于存网格环境中进行资源交易。由1 ：日前的些网格系统，女h g l o b u s 等已经提供 了大量的成熟的可重用的中i tt j f l ：，例如资源协同分配服务d u r o c 、认证和安全服务 g s i 等等，所以g r a c e 并没有重新搭建一个网格平台，而是在g l o b u s 之上j - f j 了扩 展，补充丁一些负责资源交易的中问件，例如网格市场目录g m d ，网格交易服务器 青岛大学硕士学位论文 g t s 和用于电子交付的g b a n k 等等。g r a c e 侧重于研究网格资源的分配方式，主要 包括以下四部分： 网格服务供应商g s p ( g r i ds e r v i c ep r o v i d e 0 ：包括地理上分布的所有互联资源 和网格中本地资源管理系统，主要是拥有资源的服务供应商( 相当于网格节点) 对资 源进行合理的分配，以满足交易服务器和资源预约的要求。同时服务供应商按照经 济模型制定价格策略和交易原则，以求获得最大利益。交易服务器是服务供应商本 身的代理程序，遵循价格策略与用户协商资源使用价格，指导结账系统记录资源使 用情况。网格服务供应商和网格用户通过网格银行和网格市场服务器进行结算。 网格中间件服务层g m s ( g r i dm i d d l e s o f is e r v i c e ) ：利用网格中间件实现了构造经 济网格模型所需的各种服务，其中包括登录、安全和服务质量控制，提供必要的网 格信息供网格浏览器查找所需资源，通过交易中间件连接交易服务器和交易管理器， 执行任务模块完成资源的正确分配，存储中间件存储各种必要信息。可以直接使用 g l o b u s 或其他网格系统的相关中间件来提供这些功能。网格市场目录g m d ( g r i d m a r k e td i r e c t o r y ) 类似于公告板，网格资源提供者可在其上发布自己的资源相关信息， 使得网格资源代理g r b 可以进行资源查找和选择。q b a n k 贝j j 是电子支付手段的一个范 例，这方面研究还有n e t c a s h ，n e t c h e c k 等。 网格资源代理层g r b ( g r i dr e s o u r c eb r o k e r ) ：负责资源发现、资源选择、资源绑定 等关键任务和计算初始化、单一资源映像等功能。资源代理层由作业控制代理、调 度顾问、网格浏览器、交易管理器和部署代理五部分组成。作业控制代理负责接收 用户作业并规范化，它作为总控负责监督程序的执行。调度顾问负责资源发现和资 源选择。交易管理器是负责与每个网格服务提供者的交易服务器进行资源价格协商， 在调度顾问的资源选择算法指导下，评估资源的访问开销，为调度顾问提供资源选 择依据。部署代理，代理负责将作业与实际资源进行绑定，在选定的资源上激活任务， 并周期性地向作业控制代理更新任务执行状态。网格浏览器和资源调度器用于资源 发现和选择。 网格用户层g c ( g r i dc l i e n t ) ：用户对网格系统提出自己的要求，包括所需资源和 交易所必须的信息，如价格、时间限制、偏好等。用户可使用网格应用程序，直接 向网格经纪层提出要求，或者用户利用网格语言编程环境，编写自己的网格程序提 交给网格经纪层。用户可以通过w e b 在远程资源节点提交数据和收集结果。在 g r a c e 架构中交易管理器居于核心地位，g r b 完成资源选择后，其内部的交易管理 器就会与刘应的资源提供者g s p 的交易管理器进行通信，讨论对资源的使用问题， 最主要的也就是价格问题。g r a c e 架构中提出了如固定价格、拍卖、垄断等多种经 济学模型，提供了多种可选择的价格协商机制。 计算经济网格体系结构的特点如下： 8 第二章网格体系结构 ( 1 ) 供求原则的投资回报机制也促进了计算服务质量的提高和资源的升级，经济 学原理是调节供求关系的最重要的机制： ( 2 ) 为访问网格资源的用户提供公平的价格机制，并允许对一切资源进行交易： ( 3 ) 建立以用户为中心，而不是系统为中心的调度政策，提供了资源分配和管理 的有效机制： ( 4 ) 综合了分层模型和抽象所有者模型的实质。该模犁更能体现网格动态、协同、 广域的特点。 2 3 开放式网格服务体系结构( o g s a ) o g s a 网格技术是基于面向服务体系结构的。一大批异构的资源组成了一个网 格，重要的是，这些资源以众所周知并且一致的方式进行交互和运转。正是这种交 互以及不同资源所提供的组件之间的互操作性，才是开放标准的需要，并因此促进 了开放网格服务架构o g s a 的出现。o g s a 是由g g f ( g l o b a lg r i df o r u m ) 的o p e ng r i d s e r v i c e sl n f r a s t r u c t u r e ( o g s i ) i 作小组于2 0 0 2 年6 月制定的。 2 3 1o g s a 的目的 提出o g s a 的目标是实现跨组织的分布式异构平台，实现跨管理域的异构资源 管理。具体目标包括如下四个方面。 1 - 提供优质的服务质量 网格的拓扑结构通常十分复杂，而且网格资源的交互往往是动态的。有一点很 重要，即网格可以提供健壮的后台服务，比如说授权，访问控制和委托，在这里， 优质的o o s 是必不可少的。 2 在多个自治管理域间实现网格自治 网格可以包含许多资源，还有大量的配置组合，交互以及状态与故障模式的改 变。对于这些资源来说，一些智能自动调节与自治管理方式是必不可少的。 3 定义开放的和公共的接口 o g s a 是一种由g g f 标准团体进行管理的开放式标准。为了不同资源的互操作 性，网格必须构建在标准接口以及协议上，通过定义一些开放式，公共的接口，为 不同用户提供统一服务。 4 充分利用行业标准的集成技术 o g s a 的创建者远见的利用了现有信息集成解决方案，并将w e bs e r v i c e 作为 o g s a 的基础组件。 2 3 2o g s a 主要架构 o g s a 架构由四个主要的层构成，从下到上依次为：物理资源和逻辑资源层； o 青岛大学硕士学位论文 w e b 服务以及定义网格服务的o g s i 扩展；基于o g s a 架构的服务；网格应用程序。 ( 1 ) 物理和逻辑资源层 资源的概念是o g s a 以及通常意义上的网格计算的中心部分。构成网格能力的 资源并不仅限于处理器。物理资源包括服务器、存储器和网络。物理资源之上是逻 辑资源。它们通过虚拟化和聚合物理层的资源来提供额外的功能。通用的中间件， 比如文件系统、数据库管理员、目录和工作流管理人员，在物理网格之上提供这些 抽象服务。 ( 2 ) w e b 服务层 o g s a 架构中的第2 层是w e b 务。这里有一条重要的o g s a 原则：所有网格资源 ( 逻辑的与物理的) 都被建模为服务。o g s i 规范定义了网格服务并建立在标准w e b 服 务技术之上。o g s i 进一步扩展了w e b 服务的定义，提供了动态的、有状态的和可管 理的w e b h 艮务的能力，这在对网格资源进行建模时都是必需的。 ( 3 ) 基于o g s a 架构的网格服务层 w e b 艮务层及其o g s i 扩展为下一层提供了基础设施：基于架构的网格服务。g g f 目前正在致力于在诸如程序执行、数据服务和核心服务等领域中定义基于网格架构 的服务。随着这些新架构的服务开始出现，o g s a 将变成更加有用的面向服务的架 构( s o a ) 。 ( 4 ) 网格应用程序层 随着时间的推移，一组丰富的基于网格架构的服务不断被开发出来，使用一个 或多个基于网格架构的服务的新网格应用程序亦将出现。这些应用程序构成了 o g s a 架构的第4 个主要的层。其结构层次如下 网格应用层 基于o g s a 的网格服务层 w e b 服务层层 物理和逻辑资源层 图2 3 基于w e bs e r v i c e s 的0 f i s a 的四个抽象层 2 3 3o g s a 的两大支撑技术 g l o b u st o o l k i t ( g t k ) 软件包和w e bs e r v i c e 是构造o g s a 的两大支撑技术，前 者相当于网格操作系统已成为广泛接受的网格技术解决方案；后者是访问网络应用 时普遍采用的标准框架。 l o 第二章网格体系结构 1 g l o b u st o o l k i t g l o b u st o o l k i t 是一种给予社团的、开放结构、开放源代码的服务的集合，也是 支持网络及其应用的软件库，它解决了安全、信息发现、资源管理、数据管理、通 信、错误检测以及可移植等问题。该软件包被射界的许多网格项目，包括几百个网 格节点采用。 2 w e bs e r v i c e s w e bs e r v i c e s 中普遍采用x m l 进行信息交换。s o a p 是基于x m l 的r p c ( r e m o t e p r o c e s sc a l l ) 协议：w s d l 用于描述服务，包括接口和访问方法，是w e bs e r v i c e s 的 接口定义语言。下图定义每一层存在的协议，服务和接口： c o n n e c t i v ep r o t o c o l s l o c a la c c e s s 姆i sa n dp r o t o c o l s 图2 4o g s a 每一层定义的协议、服务和接口 。一 w e bs e r v i c e s 提供了一种基于服务的框架结构，但是，w e bs e r v i c e s - - 般面对的 都是永久服务，而在网格应用环境中，大量的是临时性的短暂服务，比如一个计算 任务的执行的。考虑到网格环境的具体特点，o g s a 在原有w e bs e r v i c e s 概念基础上， 提出了“网格服务 的概念，该技术支持i 临时服务，并能实现其动态创建和删除。 青岛大学硕士学位论文 基丁二w e bs e r v i c e s 的0 g s a 架构如图2 5 。 应用( a p p l i c a t i o n ) o g s a 体系结构的服务( o g s a a r c h i t e c t u r a ls e r v i c e s ) o g s l w b bs e r v i c 楣 i o g s ao g s ao g s ao g s ao g s ao g s a 目录安全工作流数据文件系统消息 o g s ao g s ao g s a 存储网络服务 图2 5 基于w e bs e r v i c e s 的o g s a 架构 1 2 第三章信任机制 第三章信任机制 在这一章将介绍什么是信任、信任的分类和性质、信任效益函数。 3 1 相关定义 信任是一个非常复杂的主观概念，目前没有一致的定义。综合各种不同的文献， 首先给出与信任相关的一些描述性定义i l 引。 定义1 信任就是相信对方，是一种建立在自身知识和经验基础上的判断，是一 种实体与实体之间的主观行为。信任不同于人们对客观事物的相信( b e l i e v e ) ，而是一 种主观判断，所有的信任本质上都是主观的，信任本身并不是事实或者证据，而是关 于所观察到的事实的知识。 一定义2 信任度( t r u s td e g r e e ) 就是信任的定量表示，也可以称为信任程度、信任 值、信任级别、可信度等。 定义3 直接信任度( d i r e c tt r u s td e g r e e ) 表示在给定的上下文中，一个实体根据 直接接触行为的历史记录而得出的对另外一个实体的信任程度。 定义4 间接信任度( i n d i r e c tt r u s td e g r e e ) ，表示实体间通过第三者的间接推荐形 成的信任度，也叫声誉( r e p u t a t i o n ) 、推荐信任度、反馈信任度等。 定义5 总体信任度( o v e r a l lt r u s td e g r e e ) 是直接信任度和间接信任度的加权平 均。 有非常多的文献采用不同的方法研究信任关系和信任关系的建模，这些研究主 要分为4 个方向：( 1 ) 基于策略和凭证的信任关系( c r e d e n t i a l b a s e dt r u s t ) ；( 2 ) 通用 模型的研究( g e n e r a lm o d e l so ft r u s t ) ；( 3 ) 基于声誉的信任关系( r e p u t a t i o n b a s e d t r u s t ) ：( 4 ) w e b 和信息资源中的信任关系( t r u s ti nw e b s i t e sa n di n f o r m a t i o ns o u r c e s ) 。 定义6 ：信任关系】。根据调度过程中服务请求者对服务提供者信任值的要求， 两者问的信任关系可以分为强( s t r o n g ) 信任关系、弱( w e a k ) 信任关系与无信任关系。 ( 1 ) 强信任关系是指调度时用户请求的信任需求级别必须高于所分配服务的固 有属性值。如果不存在满足条件的服务，则此请求将被放弃。其最终效益值或者为 最大，或者为零。 ( 2 ) 弱信任关系指调度算法尽量保证请求者信任属性值高于提供者的信任属信 值，此时作业可获得最大效益；否则可降低请求者的信任需求，但其信任效益值随 之下降。 ( 3 ) 无信任关系指调度算法在调度过程中不考虑服务请求与提供者间的信任关 系，仅以性能q o s 为目标。 定义7 ： 信任q o s 效益函数【1 7 1 。服务请求对服务提供者信任q o s 满意度的评价。 13 青岛大学硕士学位论文 信任是一个很难表述的问题，一般把它当作一个隶属度问题【1 引，仅表述为信任 或者不信任显然是不可取的。 3 2 信任的性质 在不同模型中定义的信任可能会有不同性质。大致上，信任有如下性质【1 6 】： 主观的：不同的实体对同一个实体的可信度可能不同，我们对一个实体 的信任可能超过对另一个实体的信任，这表明了对不同的网格节点有不同的信 任等级。 上下文相关的：也就是说实体之间的信任是有一定的上下文的。例如我 们信任某个网格节点的安全属性，但不能信任这个网格节点的可靠性要求。我 们可以使用信任种类来表示信任的上下文，用信任值来表示每个信任种类的不 同信任等级。 在同一时刻信任关系并不是双向的，也就是非对称的，或者单向的 ( u n i d i r e c t i o n a l ) 。 最终的对称性：经过不断的交互，实体之间最终趋近于相互不信任或者 相互任。 信任总是存在于两个实体之间的。 存在信任关系的实体将会合作下去，一直信任。反之，不信任的实体将 不合作。 动态性：信任是不断变化的。我们设计一定的更新方式来更新信任度。 根据网格实体不同的行为，实体之间的信任关系动态更新。 3 3 信任函数分类方法 信任函数的分类方法，有很多种，根据文献我们可以按照以下四种方式分类： 3 3 1 主观信任函数与客观信任函数 一个网格实体的可信度取决于它对其它实体提供的服务的质量。如果这些服务 的质量能够客观测量，那么这个网格节点的信度函数就称为客观信任函数2 0 】。而对 于其它的服务，这些服务的质量很难被评测，比如说网络电视，不同人对它的质量 可能给出不同档次的评价，它取决于不同人的自我感受与其它一些主观因素。在这 种状况下，只有从某一个特定的角度去评价才有意义。我们称此信度函数为主观信 度函到19 1 。 直观的，如果网格提供的服务能够被客观评价，那么网格节点的服务信度函数 反应了网格节点的本质属性，而与其它网格节点的评价无关。而对于主观信任函数， 1 4 第三章信任机制 与其他网格节点的评价相关，不同的网格节点可能对网格提供的服务给出不同评价。 总的来说，客观信任函数与主观信任函数不可比，他们适合于不同情况。 3 3 2 基于交易与基于评估信任函数 有些信任模型通过历史交易来评估网格实体的信誉，而其它的则通过网格节 点的评价进行评估。 基于交易的信任函数是对交易的质量进行评估得到的。实际来，这种方法并不 需要交易的详细信息，我们只需要一些统计信息，比如说，交易总数，成功地交易 数等等。但总的来说，它必基于评估的信任函数需要更多信息，所以要付出通讯代 价。 当采用基于评价的信任函数，每个网格节点可以从自己的角度对其它网格节点 的可信度做出评价，所以它减少了通讯开销，同时评价可能有自私性。由于这个原 因，这种信任函数可能受不公正的网格节点评价所影响【1 7 】。 3 3 3 全局信任函数与局部信任函数 信度函数也可以根据收集信息的方式进行分类。有些信度函数假设网格节点可 以知道所有其它节点的交易信息，我们称此信度函数为全局信任函数。 另一种途径是采取局部搜索的方法。每个网格节点有若干邻节点，如果某个网 格节点需要知道与之交易节点的信任函数，则通过询问相邻网格节点的评价来计算 出信度函数。由于不同网格节点可以有不同相邻节点，所以所给出的评价也可能不 同。所以我们称之为局部信度函数。 总的来说，局部信任函数更适应于分布式计算环境。但全局函数也可以避免个 别网格节点的恶意评估。 3 3 4 基于分级与基于与门阀值函数 当通过一定方式，计算出网格节点的信度函数，那么该怎么利用信度函数做出 决策方法有两种： 对于大多数信任函数，它返回的信誉值可以解释为网格服务提供的特性。对于 有些网格节点所要求的网格服务，只要其它网格节点提供的服务信誉值高于某一阀 值即可。 而其它一些信度函数，它计算出的信誉值只有通过对其它节点的信誉值对比才 有意义。某种意义上，这种信誉函数反映了信任等级。因此，我们称此信任函数为 基于门阀值的信任函数。 | 一 这两种信任函数适用于不同的情况与应用要求。如果我们要求一定的质来担保， 那么基于门阀值信任函数是一个比较好的选择。：对于基于等级的信任函数，一个网 1 5 青岛大学硕士学位论文 格节点具有高的等级，并不代表这个网格节点提供高质量的网格服务。另一方面， 如果我们只要求知道前1 0 提供可靠服务的网格节点，那么基于等级的信任函数是一 个比较好的选择。当然，我们可以通过门阀值来获得网格节点的信誉等级，但对于 大规模的网格系统开销很大。 上文中我们给出了信任函数的四种分类方法，实际上，这些分类方法区别并不 明显，并且可能互相交叉。具体采用哪种方法，取决于具体应用。 3 4 信任函数的更新策略 正如人们在实际生活中一样，网格节点的信任度也不是一样的，它随时间而改 变。同时，在推荐系统中，我们不但考虑网格节点本身的交易情况，而且也考察网 格节点的推荐节点可信度问题。具体来说，可以归纳为以下两个策略： 按时间更新。在这种方式下，某一段时间内的交易，具有的同等的影响凶子。 时间越久远，影响因子越小。 按交易或者推荐的序号更新。网格节点的交易或推荐按照时问顺序进行排列， 根据此次交易或者推荐的评估，更新信任度函数。 3 5 防止串谋与诋毁 网格中可能存在欺诈行为以及不可靠的服务质量【2 2 1 。同时，由于网格中的节点 更多地表现出理性和自私性，节点的目标往往是最大化自身的网络效用( n e t w o r k u t i l i t y ) ，从而导致了节点只想索取资源而不愿贡献资源的行为，即可能存在串谋和 诋毁的攻击行为。例如，一组节点可能会协同合作，互相提供不真实的较高的交易 回馈评分，即“串谋”( c o l l u s i o n ) ；或者向网格中的其他节点提供不真实的较低的回 馈信息，从而影响对该节点的可信度判断，该攻击行为称为“诋毁”( b a d - m o u t h i n g ) 。 为了消除这些不诚实推荐行为对信任评估准确性的影响，推荐节点的推荐可信度可