（计算机应用技术专业论文）基于贝叶斯策略的网格资源分配方法研究.pdf

摘要 网格资源的分布性、异构性、动态性等特点给网格环境下资源的 分配造成困难。资源分配负责根据用户的资源需求描述发现最佳资源 服务，在实际应用中，用户的资源需求带有很大的模糊性，导致了网 格服务质量很难满足用户的要求，因此网格资源分配已成为网格技术 研究的重点之一。 本文以网格资源分配为核心，系统地介绍了网格计算中的相关技 术、特点及国内外研究现状等，通过对当前比较流行的网格资源分配 机制的分析和研究，针对其中存在的问题提出了一种新的基于贝叶斯 策略的资源分配方法。 考虑网格应用q o s 需求，以最大化网格系统的经济收益为目标， 该方法基于价格可代表资源q o s 综合性能的思想，利用历史q o s 匹 配记录，运用朴素贝叶斯分类模型根据用户提交的价格参数来分配与 其级别相对应的符合要价范围资源，并提出两种网格o o s 分级方法， 优先考虑q o s 水平较高的任务，将当前时刻q o s 水平较高的资源预 留给下一时刻到达的q o s 水平较高的任务，而忽略当前时刻q o s 水 平较低的任务。 实验结果表明，该资源分配方法不仅能有效地保障用户q o s ，而 且能使网格系统获得较大的经济收益。 关键词网格计算，资源分配，q o s 分级，经济收益，贝叶斯分类 a bs t r a c t b e c a u s eo ft h ec h a r a c t e r i s t i e so fg r i dr e s o u r c es u c ha sd i s t r i b u t i o n ， h e t e r o g e n e i t y , d y n a m i c ，e t c ，r e s o u r c ea l l o c a t i o nu n d e rg r i de n v i r o n m e n t i s v e r y d i f f i c u l t r e s o u r c ea l l o c a t i o ni s r e s p o n s i b l e f o r p r o v i d i n g b e s t s e r v i c e sa c c o r d i n gt ou s e r sr e q u i r e m e n t h o w e v e r , u s e r sr e q u e s th a s m u c hf u z z ya c t u a l l y , s oq u a l i t yo fg r i ds e r v i c ei sh a r d l yt om e e tu s e r s n e e d s t h e r e f o r e ，r e s o u r c ea l l o c a t i o nh a sb e e no n eo ft h ek e yr e s e a r c h f i e l d so fg r i ds y s t e m s t h i st h e s i st a k e sr e s o u r c ea l l o c a t i o na sac o r e ，i n t r o d u c e ss o m e c o r r e l a t i v et e c h n o l o g i e s ，c h a r a c t e r i s t i c s ，a n dc u r r e n tr e s e a r c hs t a t u si n g r i dc o m p u t i n gs y s t e m l y a f t e ra n a l y s i s i n ga n ds t u d y in gs o m ec u r r e n t p o p u l a rm e c h a n i s m s ，ab a y e s b a s e da p p r o a c hf o rg r i dr e s o u r c ea l l o c a t i o n i sp r e s e n t e dt os o l v es o m ek e yp r o b l e m si nt h i sa r e a t om a x i m i z et h ee c o n o m i ci n c o m eo fg r i ds y s t e m ，c o n s i d e r i n g a p p l i c a t i o n s q o sr e q u i r e m e n t s ，t h ea p p r o a c hi sb a s e do nt h ei d e at h a t p r i c ec a nr e p r e s e n tr e s o u r c e sq o sc o m p r e h e n s i v ep e r f o r m a n c e b yu s i n g n a i v eb a y e sc l a s s f i c a t i o nm o d e l ，t h er e s o u r c eo fc o n g r u e n tc h a r g er a n g e i sa l l o c a t e dt ot h et a s ka c c o r d i n gt op r i c ep a r a m e t e rt h a tt h eu s e rs u b m i t s ， a n dt w oa p p r o a c h e sf o rq o sl e v e lp a r t i t i o na r ep r o v i d e d ，t h e nt a s k so f h i g h e r - l e v e lq o sa r eg i v e nap r i o r i t y , r e s o u r c e so fh i g h e r - l e v e lq o s c u r r e n t l ya r eo b l i g a t e dt ot a s k so fh i g h e m e v e lq o sl a t e r , w i t ht a s k so f l o w e r - l e v e lq o s c u r r e n t l yb e i n gi g n o r e d t h ee x p e r i m e n ts h o w st h a tt h ep r o p o s e da p p r o a c hc a nn o to n l ym e e t u s e r s q o sr e q u i r e m e n t sb u ta l s om a k eh i g h e re c o n o m i ci n c o m ef o rg r i d s y s t e m k e yw o r d sg r i dc o m p u t i n g ，r e s o u r c ea l l o c a t i o n ，q o sl e v e l p a r t i t i o n ，e c o n o m i ci n c o m e ，b a y e sc l a s s f i c a t i o n i i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：左交- = 舀一日期：哔年尘月担日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 名：姆聊签名掣嘞中日 硕十学位论文第一章绪论 1 1 研究背景 第一章绪论 网格的概念出现于2 0 世纪9 0 年代中期，当时是用于表述一种适用于高端科 技和工程的分布式计算体系结构，它最初是为了实现科研协作中的资源共享，此 后规模日益扩大。随着互联网的不断发展，将地理上广泛分布的大量计算资源( 包 括超级计算机、集群、工作站、个人p c 等) 集合起来进行大规模的问题求解变 得日益普遍，由此产生了“网格计算 【1 3 】。传统因特网实现了计算机硬件的连 通，w e b 实现了网页的连通【4 。5 】，而网格试图将分散在网络上的各种共享资源包 括计算资源、存储资源、通信资源、软件资源、信息资源、知识资源等，通过虚 拟化的方式组织起来，形成动态可扩展的虚拟有机整体，向用户提供强大的计算 能力、存储能力、设备使用能力及更有效的信息融合和共享能力，从而实现资源 的全面共享和协同工作 6 - 9 。网格的最终目标是可以把分布在各个信息孤岛上的 资源统一在一起，使大家可以极为方便的使用。 近年来，网格正逐步向商业性、服务公众化、多主干的全球网格转变，并已 成为全球信息基础设施的原型。为适应这一变化，网格管理、运营和维护逐渐转 由多家资源提供者负责，他们以不同的标准向各类用户提供连接访问、视频点播 ( v o d ) 、w e b 查询、新闻组( u s e n e t ) 、e m a i l 等多种服务，向用户收取服务 费用，这既加快了网格由学术科研性网格向商业网格的转变，为运用价格杠杆来 促进资源的合理使用，也为用户提供良好的服务质量( q u a l i t yo f s e r v i c e ，q o s ) 奠定了基础，因此资源提供者要求提供更有效的资源分配机制【1 0 0 2 1 。 如何有效地分配有限资源，从而最大限度地实现资源的潜在价值，这正是经 济学研究得比较成熟的问题，自9 0 年代末起至今，国内外学者都在网格资源分 配的研究中借鉴经济学的一些方法【l 孓1 6 】。在竞争的经济市场模型中，主要根据用 户的需求和资源的供应来决定资源价格和资源分配。因此，研究基于经济的网格 资源分配方法是建立高效、可扩展与稳定的资源分配机制的一个极有前途的方 向。计算网格的研究者已经提出了一些解决分布式资源分配问题的经济学模型与 方法，如b u y y a 探讨了基于商品市场的计算网格资源分配机制【1 7 】，s a n d h o l m 研 究指出计算、通信和安全问题同经济激励问题紧密相联【1 8 】，g h o s h 提出了一种基 于对策论的定价策略解决移动网格的任务分配问题等【1 9 】。 微观经济学中，价格是调节消费者与商品之间供求关系的有效杠杆【2 0 1 ，而在 网格应用中，网格资源提供者同用户之间的行为与市场中的商品和消费者之间的 消费行为有很多相似之处。结合经济学的理论，可以把市场机制引入网格计费管 硕士学位论文第一章绪论 理。事实上，计费本身也体现了一种资源分配机制，虽然它不是显式的为特定用 户的数据流分配网格的c p u 、内存和带宽等资源，但是价格杠杆限制了那些对 当前网格资源价格不能接受的用户使用行为，从而将网格资源分配给那些急需网 格服务而接受较高价格的用户。价格杠杆可以被看作一种用来调整用户传输行为 的激励机制。要用经济学方法研究网格资源分配问题，首先要建立用户的效用函 数模型，系统优化目标是使系统总效用最大化。目前大多数模型中，用户被视为 购买商品的消费者，网格资源提供者被看作为生产者。采用价格机制调节用户需 求，使得系统达到总需求等于资源总供给的均衡状态。微观经济学理论证明：当 系统处于均衡状态时，资源配置是最优的，系统总效用最大。该方法具有以下优 占 2 1 - 2 2 j 、 ( 1 ) 优化了整个网格系统，并大大提高了网格系统的总效用； ( 2 ) 由于价格本身可以起到类似接纳控制的作用，从而简化了相关的q o s 保 障机制； ( 3 ) 提出合理的计费机制，为商业运作提供基础； ( 4 ) 市场机制固有的分布性与网格资源的分布性相适应，可以实现有效的、 松耦合的分布式资源控制和管理，符合网格资源管理的发展方向。 本文课题是在上述背景下确立的，通过对网格环境的特点和当前网格项目的 资源分配方法进行分析，考察了已有的网格资源分配机制在目前网格资源分配中 应用的优缺点，将贝叶斯策略引入网格资源分配中，通过对其改进，提出了基于 贝叶斯策略的网格资源分配方法，并通过仿真实验证明了方法的有效性。 1 2 国内外研究现状 1 2 1 网格计算发展和现状 网格技术与许多其他技术的发展一样，在学术研究领域诞生，但迅速扩散到 金融、汽车设计、生命科学和其他领域的各种商业应用中，其实质是在动态的可 扩充的虚拟组织中可控且平等地使用和共享资源，而其中最为核心的是为各种网 络上的资源提供一种安全、高效的共享机制，使得各种异构和孤立的资源能以一 个整体为用户提供各种计算和信息服务。 国际上已经涌现出一大批知名的比较有影响的大型网格项目，其中大多数的 实现都是基于g t 3 g t 4 1 2 3 】( g l o b i u st o o l k i tv e r s i o n3 4 ) 所提供的协议及服务建设 的，例如美国有g l o b u s 2 4 、l e g i o n 2 5 1 和c o n d o r l 2 q 等，欧洲有c e r nd a t ag r i d t 2 刀、 u n i c o r e 2 8 1 、e - s c i e l l c e 【2 9 】等，澳大利亚有n i m r o d g 3 0 l 、e c o g r i d 等，日本有 n i n t i 3 、b r i c k s 3 2 】等。以下简要介绍比较有影响的软件和工具： 2 硕十学位论文第一章绪论 ( 1 ) g l o b u s 工具软件已经在世界范围内得到了一定程度的使用，对全球的网 格研究开发工作起到了巨大的推动作用，成了网格领域受世人关注的焦点。该 项目要开发一个面向科学计算的基本软件基础设施，利用该设施，把地理位置 上分布的计算资源和信息资源集成起来。该项目研究网格计算的关键理论，开 发支持网格计算的工具软件和网格应用程序，帮助规划和组建大型的网格实验 平台。关键理论包括资源管理、网格安全、信息服务、数据管理等。工具软件 是g l o b u s 最重要的成果，目标是能够在各种平台上运行。 ( 2 ) l e g i o n 是弗吉尼亚大学的一个基于对象的元系统软件项目，它的目标是 为用户提供单一且一致的虚拟机器模型。l e g i o n 是一个基于计算的元系统，支 持透明调度、数据管理、容错、站点自治和多种安全机制。在l e g i o n 内，所有 的实体都是对象，包括硬件实体和软件实体。每一个对象由它的类对象定义和 管理，类对象的作用相当于管理者，除了定义实例之外，还制定管理策略。 ( 3 ) c o n d o r 是威斯康星一麦迪逊大学的研究项目，它是一个专用的计算密集 型负载管理系统，提供队列机制、调度策略、优先级方案、资源监控、资源管 理等功能。用户向c o n d o r 提交自己的作业后，c o n d o r 把作业放在队列中，并根 据一定的策略，选择合适的时间在合适的节点上运行用户提交的作业。作业运 行过程中，它监控作业的运行过程；作业运行结束时，通知提交作业的用户。 用户提交的作业可以是串行作业，也可以是并行作业。 ( 4 ) d a t a g r i d 项目基本思想是把生成的海量数据分散到全球的计算机上进行 处理，并由全球的物理学家共同进行分析。其核心中间件系统基于g l o b u s 构造 的。d a t a g r i d 的主要功能包括：负载调度和管理，以适应数据的动态重新分配、 高并发的任务数和不同国家机构的不同管理策略等；数据管理，以支持统一的 名字空间和统一的数据格式、数据的高速移动和复制、远程数据复制实例的一 致性等；系统监控，以协助制订调度策略，调整应用程度的运行性能；构造层 管理，对数量众多的基础构件提供灵活和有弹性的管理，满足严格的时间约束 条件，保证整个系统的容错性；海量存储管理，用统一的接口屏蔽不同站点的 数据存储方式和处理方式之间的差异，无缝融合分布的存储资源。 ( 5 ) e s c i e n c e 被认为是最先进的网格结构，主要集中在科学研究类应用。每 个应用有一个p o r t a l 入口，底层资源采用g t 2 、c o n d o r 、数据库、文件、w e bs e r v i c e 等形式，p o r t a l 服务器端软件直接调用物理资源。 ( 6 ) n i m r o d g 是一个网格资源代理，由四个关键构件组成t 任务管理引擎、 调度器、分派器和智能主体。任务管理引擎支持插入用户自定义的调度器、定 制应用或问题解析环境。分派器使用g l o b u s 服务将n i m r o d g 智能主体部署到 远程资源上以管理分派任务的运行。n i m r o d g 调度器则可根据用户服务质量需 3 硕十学位论文 第一章绪论 求中说明的能力、费用和可用性等租借适合的资源和服务。n i m r o d g 支持资源 的发现、选择、调度与用户任务在远程资源中的透明运行。n i m r o d g 相关的研 究成功还包括了一个称为g r i d s i m 的工具集，提供复杂的设施以支持网格资源和 应用调度的建模和模拟，可用于评估调度算法的性能。 国内的网格计算尚处于研究阶段，目前，我国已启动了若干网格项目，如科 技部负责的中国国家网格【3 3 1 ( c n g r i d ) 、教育部负责的中国教育科研网格技术【3 4 1 ( c h i n a g r i d ) 、国家自然科学基金负责的e s c i e n c e 网格研究计划、上海信息网格、 中国空间信息网格。其中，中国国家网格( c n g r i d ) 由国家8 6 3 高技术研究发 展计划资助，旨在建立面向企业、高等院校、科研机构、政府部门的国家高性能 计算环境。中国教育科研网格项目是迄今为止由政府推出的最宏大的网格工程5 万亿次量级的教育科研网格，形成世界上最大的超级网格之一，并争取在网格计 算的基础研究和应用研究方面走在世界前列。 分析目前的研究和应用现状，网格计算应在以下几个方面重点开展工作： ( 1 ) 资源管理【3 5 1 。为了使网格的性能达到最佳，需要管理信息在网格中分配 的方式。如何分配工作、工作传输的频率、以及它分配给每一个客户机的方式都 会影响服务器的负载、网络的负载，并最终影响网格的性能。通过精心管理，如 控制工作单元分配、在代理端保持记录以及分析每一个客户机的性能，应当可以 使网格的性能达到最大化。通过管理服务器( 将作业提交给网格的工作代理) 和 客户机( 所需资源的提供者) 的带宽，应当能够使网格环境的性能达到最大化， 同时防止过度使用网络、c p u 和其他资源。 ( 2 ) 资源监控【3 6 1 。确定并监测网格资源状况，收集任务运行时的资源占用数 据。用户提交的任务要由系统来分配资源并控制其运行，包括要将其分配到哪些 主机上运行、调用哪些数据、启动何种应用程序、何时开始运行等。 ( 3 ) 网格安全【3 7 】。由于可扩展性的要求，性能和异构是任何分布式系统的奋 斗目标，但网格计算的特点导致了在分布式系统中已有的安全技术尚不能解决的 问题。网格应用所涉及的大量资料和计算内容在各组织之间是否能安全共享，内 部系统环境中一些常常被忽略掉的问题，如安全和可靠性等，在任何分布式环境 下都必须得到解决。 综上所述，网格计算方面进行研究和探索的内容是极其丰富和具有挑战性 的，资源管理是网格的核心服务层技术，包括网格资源管理和分配、网格资源信 息服务、网格资源发现与监视、网格资源需求描述等方面。 1 2 2 网格资源分配研究现状 网格计算中包含很多关键技术，其中资源分配又是重中之重，因而成为研究 4 硕士学位论文第一章绪论 热点。当前的许多网格系统都有各自的资源分配方法： ( 1 ) 在n q e 3 引，p b s 3 9 1 ，l s f l 4 0 1 以及l o a d l e v e l e r t 4 1 1 等这些系统中，资源通过 一种任务控制语言清楚地表达了自己，使用者只能把任务直接提交到具体资源的 等待队列中。这样的手动控制配置方法严重阻碍了动态发现资源的实现。 ( 2 ) l e g i o n t 4 2 】是美国v i 哂1 1 i a 大学开发的基于对象的元计算系统，l e g i o n 通 过把系统中的所有组件封装成对象来实现元计算境。在l e g i o n 中定义了一个资 源管理体系来支持资源的发现，动态资源状态监控，资源分配以及任务管理。这 种架构使资源调度更加方便。 ( 3 ) g l o b u s 资源管理是通过g l o b u s 工具包与局部系统上的所有调度器交互 来实现的。g l o b u s 资源分配管理器( g l o b u sr e s o u r c ea l l o c a t i o na n dm a n a g e m e n t ， g r a m ) 支持在一组局部资源上创建和管理进程，资源请求由一种可扩展的资源 描述语言( r e s o u r c es p e c i f i c a t i o nl a n g u a g e ，r s l ) 来表示并在组件之间传递。 g l o b u s 的资源联合分配是通过一个称为资源联合分配器的实体来实现的，它将 复合请求分割成若干部分，并把每个部分提交给相应的g r a m 处理。 ( 4 ) g c o m m e r c e 【4 3 喇】是美国田纳西大学的研究项目，它利用市场经济学方法 在网格中进行动态资源分配。在g c o m m e r c e 中，资源的相对价值是根据供需变 化而变的，给出了c p u 资源和磁盘资源的价格公式，并讨论了关于价格调整的 问题。但是g c o m m e r c e 只是给出了模拟结果，并没有具体实现。 ( 5 ) 澳大利亚m o n a s h 大学的b u y y a 基于早期对市场机制在分布式系统中的 应用研究成果，深入探讨了网格环境中基于经济学的分布式资源管理、调度问题， 构造了一个网格经济学框架( 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 , g r a c e ) 4 5 】。在g r a c e 架构中交易管理器居于核心地位，网格资源代理( g r i d r e s o u r c eb r o k e r , g r b ) 完成资源选择后，其内部的交易管理器就会与对应的网 格服务提供者( g r i ds e r v i c ep r o v i d e r , g s p ) 的交易管理器进行通信，讨论对资源 的使用问题，最主要的也就是价格问题。g r a c e 架构中提出了固定价格、拍卖、 垄断等多种经济学模型，提供了多种可供选择的价格协商机制。 ( 6 ) n i m r o d g 是分布式系统技术中心( d i s t r i b u t e ds y s t e mt e c h n o l o g yc e n t e r , d s t c ) 和m o n a s h 大学合作开发的一个工具集，主要设计目标是提供基于网格 环境的大型分布式实验平台，提供一种简单的声明式参数化建模语言。使用户可 以规范化他们所要提交的作业和需求，并使用经济学模型进行资源调度和协同分 配。n i m r o d g 还提供了优秀的图形用户界面( g r a p h i c a lu s e ri n t e r f a c e g u i ) 客 户端，方便了用户使用。目前n i m r o d g 在生物信息学、计算机辅助设计( c o m p u t e r a i d e dd e s i g n ，c a d ) 、数字化电影制作等方面都发挥了不小的作用。 经过研究与分析发现，目前的一些网格资源分配方法仍然存在一些问题： 5 硕+ 学位论文第一章绪论 ( 1 ) 要在满足用户q o s 性能需求且不超出预算经费的前提下，将任务安排到 网格的适当资源上进行计算并不容易。针对不超出预算经费的前提，可采用博弈 模型【4 6 】【4 7 】或者一般均衡理论【4 8 】求解；而针对用户层q o s 和资源层q o s 之间的差 异性【4 9 1 ，可采用模糊神经网络【5 0 】进行两者之间的映射等。但以上方法均存在效 率低下的缺点； ( 2 ) 由于资源提供者在资源能力、可用性、使用代价与安全策略上存在差异， 要想将资源分配给合适的用户以使资源的利用率和相应的收益最大同样也异常 困难。文献【5 l 】指出了当前网格任务调度模型的缺点在于：不同q o s 水平的任务 竞争资源。对于一个没有q o s 需求的任务，既可以分配高q o s 水平的资源，也 可以分配低q o s 水平的资源；而对于一个高q o s 水平的任务只能分配高q o s 水 平的资源。于是可能造成以下后果：低q o s 水平的任务长期占用高q o s 水平的 资源，高q o s 水平的任务一直得不到资源，低q o s 水平的资源一直处于闲置状 态。文献 5 2 】提出了一种基于相似度距离测量方法的网格资源匹配算法：根据用 户提交的任务q o s 参数值和资源提供者提供的资源q o s 参数值，构建用户向量 和资源向量，通过测量用户向量和所有备选资源向量之间的相似程度( 即计算两 个对象之间的欧几罩德距离) ，来为用户分配相似度最高的资源。该方法存在的 问题是，若当前时刻用户提交的任务q o s 水平较低，而所有备选资源的q o s 水 平均很高时，则只能分配其中一个相似度最高( 即距离最短) 的高q o s 水平的 资源，没有将资源分配给合适的用户，导致资源利用率和经济收益低的后果。 1 3 研究意义 资源分配在网格资源管理系统中的地位举足轻重，它对网格系统的效率、网 格资源的有效利用、任务的执行结果( 执行时间、准确性等) 以及用户的满意程 度等都产生直接而又重大的影响，因此对网格资源分配机制的研究有着更加实际 的经济价值： ( 1 ) 与网格用户的几何级数增长相比较，硬件设备的扩容和技术更新较为缓 慢，带宽、缓冲等网格资源相对匮乏，不能满足日益增长的用户需求，必须设计 高效、合理的资源分配策略以充分利用资源。 ( 2 ) 不同网格应用的q o s 要求和资源需求不同，现有的单一尽力型网格模式 不能很好地提供区分服务，这就要求网格资源提供者采取措施，提供不同质量级 别的多种服务，把稀缺的网格资源分配给对其价值评价最高的用户，并收取相应 费用，使网格资源提供者获得尽可能大的用户市场及利润。 ( 3 ) 遍布全球的且具有商业化特点的网格，迫切要求引入合理的价格机制和 体系，体现资源的价值，为市场运作提供基础。同时，计费管理也是其重要组成 6 硕十学位论文第一章绪论 部分，它为企业内部各部门或相关企业之间信息共享和传输的财务结算提供依 据。但是计费必须与资源分配相结合，才有实际意义。因此，从各个角度讲，资 源分配都应当是网格研究的核心课题。 1 4 研究内容 本文首先介绍网格技术的特点、发展过程和三大趋势，分析和总结当前关于 网格资源分配方面的研究现状。对网格q o s 参数的分类、s q n 概念及q o s 服务 价格确定模型等进行简要说明，重点对资源调度的技术特点、当前的资源分配算 法及其存在的问题进行较为详细的阐述。 接着提出网格q o s 级别的概念，并提出分别基于枚举和基于聚类的网格q o s 级别划分方法，给网格q o s 分级的目的是为本文重点提出的资源分配方法所用。 最后针对当前资源分配算法中存在的问题，运用朴素贝叶斯分类模型，文章 提出一种基于贝叶斯策略的网格资源分配方法，根据q o s 历史记录，运用朴素 贝叶斯分类模型进行资源分配，根据用户提交的价格参数来分配与其级别相对应 的符合要价范围的资源，达到不会将q o s 水平高的资源分配给q o s 水平低的用 户的目标，使用户q o s 得到保证的同时也给网格系统带来了较大的网格经济收 益，并通过仿真实验验证该方法与当前资源分配算法相比之后的优越性。 1 5 论文的结构 本文详细介绍网格相关技术以及资源分配的研究现状和发展，并对资源分配 中的关键问题提出自己的看法和观点。为了更好地诠释观点和阐述研究内容，全 文主要分为5 个章节。 第一章：绪论。简要介绍研究的背景、现状和本文的主旨。 第二章：网格计算中的q o s 和资源管理。简要介绍网格q o s 、网格服务质 量数( s e r v i c eq u a l i t y n u m b e r ，s q n ) 的基本内容及网格计算中的资源管理模块。 第三章：网格q o s 级别划分方法。主要介绍用户层q o s 级别和资源层q o s 级别的定义及其相应的两种级别划分方法，为第四章所用。 第四章：基于贝叶斯策略的网格资源分配方法。简要介绍贝叶斯定理、朴素 贝叶斯分类模型及q o s 历史记录的产生和预处理方法，并详细介绍一种基于贝 叶斯策略的网格资源分配方法，并与目前现存的资源匹配算法进行理论和实验双 向对比。 第五章：总结和展望。对本文的工作进行了总结与展望。 7 硕士学位论文第二章 网格计算中的q o s 和资源管理 第二章网格计算中的o o s 和资源管理 2 1 网格0 0 s 概述 2 1 1o o s 概念 q o s ，是网络与用户之间以及网络上互相通信的用户之间关于信息传输与共 享的质的约定，定义了连接模式( t c p ) 和无连接模式( i p ) 传输的一组参数， 它们保证传输质量和服务的可靠性。q o s 是网络的一种安全机制，是用来解决网 络延迟和阻塞等问题的一种技术。在正常情况下，如果网络只用于特定的无时间 限制的应用系统，并不需要q o s ，当网络过载或拥塞时，q o s 能确保重要业务量 不受延迟或丢弃，同时保证网络的高效运行。在网络环境中，常见的q o s 指标 包括以下内容： ( 1 ) 业务可靠性：用户与i n t e m e t 业务之间连接的可靠性。 ( 2 ) 延迟：指两个参照点之间发送和接收数据包的时间间隔。 ( 3 ) 抖动：指在同一条路由上发送的一组数据流中数据包之问的时间差异。 ( 4 ) 吞吐量：网络中发送数据包的速率，可以用平均速率或峰值速率来表示。 ( 5 ) 丢包率：在网络中传输数据包时丢弃数据包的最高比率。 基于q o s 的定义，网格中的q o s 可定义为一组服务集合的性能，该性能决 定用户对服务的满意程度【5 3 1 ，是网格区别与“基础设施”或“中间件 的一个关 键要素。网格q o s 的目标就是要为网格最终用户在使用网格系统这种共享平台 时提供一些可预测性的质量级别，以及控制超过目前本网格系统最大服务能力的 服务。同时由于网格是建立在网络的基础之上，因此网格所面临的q o s 问题包 括了网络q o s 问题。除此之外，网格q o s 是通过网格资源执行用户提交的任务 来体现的，因此，网格中q o s 参数也是丰富多样的，如响应时间、可用性、可 靠性、信任度、安全性等。但由于网格任务和网格技术自身( 通过封装底层资源 以服务形式提供给用户，用户不关心任务执行的具体细节) 特点以及网格用户所 关心的q o s 来说，主要包括任务执行的截止时间和任务执行所需的费用两种。 这也是本文重点考虑的用户q o s 要求，定义如下： 定义2 1 截止时间 截止时间是指一个用户希望网格系统执行其提交任务的最迟完成时间，表示 为j d 。 定义2 2 执行花费 执行花费是指一个用户调用某个服务时，需要向服务提供者提供的必要费 用，表示为c 。 r 硕士学位论文第二章网格计算中的q o s 和资源管理 2 1 2o o s 参数的分类 由于q o s 对不同的对象可以有不同的描述，因此，在不同层次对象的角度 可以得到不同的q o s 参数分类方案。如果从网格服务的整体性能出发对网格q o s 参数进行分类，则分类方案不足以表达网格q o s 参数的特性和需求；如果从物 理资源角度出发对网格q o s 参数进行划分，则划分方案不能表达网格用户的o o s 需求和网格环境下逻辑资源的q o s 特性。而虚拟组织是连接网格服务和物理资 源的纽带，它是网格特性得以体现的关键，因此，从虚拟组织层对网格q o s 参 数进行分类，一方面可以很详细地表达网格q o s 参数的需求，另一方面可以很 方便地将虚拟组织层的q o s 参数分别映射转换成网格服务层和物理资源的q o s 参数。根据q o s 参数所表达的q o s 特性不同，文献【5 4 将网格q o s 的参数划分 成a c c o u n t i n gq o s ，s e r v i c eq o s ，p r o v i s i o n a lq o s ，s e r v i c er e l i a b i l i t y 和s e r v i c e s e c u r i t y 5 种类型，与此同时，文献 5 5 】在虚拟组织层也将网格q o s 参数分成了逻 辑资源类、系统类、安全类、信任类和记账类等5 种类型。 ( 1 ) 逻辑资源q o s 。逻辑资源q o s 是由服务提供者提供的用来描述虚拟组织 中直接提供网格服务的逻辑资源的q o s 参数，它综合考虑了物理资源本身的整 体服务性能、资源本地任务的负载情况以及资源的共享策略等因素，是物理资源 在网格环境中服务性能的抽象。逻辑资源q o s 是网格服务q o s 的主要决定因素， 也是网格q o s 不同参数种类中最活跃的参数类型。 ( 2 ) 系统q o s 。系统q o s 是用来描述对网格服务的服务能力有一定影响的系 统环境方面的q o s 参数。主要包括网络性能和资源节点环境两个方面的q o s ， 具体参数由服务提供者提供。 ( 3 ) 安全q o s 。安全q o s 是由服务提供者提供的用来表明网格服务自身安全 级别和网格服务访问控制策略等方面的q o s 参数，其中网格服务安全级别q o s 用来满足网格用户对服务安全方面的q o s 需要，网格服务访问控制策略q o s 用 来满足服务提供者安全管理方面的需要。 ( 4 ) 信任q o s 。信任q o s 就是用来评价服务信息可信度的q o s 参数，它是由 服务提供者和虚拟组织共同提供和维护的。服务提供者可以根据那些不确定的动 态因素对信息的可能偏差做出估计，并依此向虚拟组织主动提供信任q o s 。为了 防止用户故意虚报信任q o s 的情况发生，虚拟组织需要对用户提供的信任q o s 进行评价并拥有最终的决定权和奖惩措施，从而确保信任q o s 能准确反映服务 信息的真正可信程度。当然，虚拟组织也可以根据不同管理策略的需要，主动设 置服务提供者的信任q o s ，并根据信任信息的统计情况对信任q o s 进行修改。 ( 5 ) 记账q o s 。记账q o s 就是用来描述服务代价及其管理策略方面的q o s 参 数，它由服务提供者提供。 o 硕士学位论文 第二章网格计算中的q o s 和资源管理 在这5 种类型的q o s 参数里，逻辑资源q o s 和系统q o s 对网格服务的服务 能力起着决定性的影响作用，因此，这两种类型的q o s 参数又称为功能性q o s 参数。用户在申请服务时，可以根据自己的需要，申请或选择不同的系统q o s 和逻辑资源q o s 参数，从而获得不同的q o s 等级。而安全q o s 、信任q o s 和记 账q o s 等3 种类型的q o s 参数都属于网格服务属性方面的q o s ，它们对网格服 务的服务能力没有决定性的影响作用，只是向用户提供一些必须的q o s 信息， 用户也没有办法决定这些q o s 参数的具体值，因此，将这三种类型的q o s 参数 又称为描述性q o s 参数。 2 2 网格s o n 概述 为描述网格服务的质量需求，文献 5 6 定义了网格服务的基本q o s 参数，提 出了网格s q n 概念，用于度量网格服务的整体量化特性。并在此基础上，提出 了一种网格q o s 服务的价格确定模型。 2 2 1s o n 概念 用户的服务请求指定一个q o s 参数集，和其他的服务管理参数组成服务等 级协议( s e r v i c el e v e la g r e e m e n t ，s l a e ，7 】) ，q o s 服务匹配就是比较其中的对应 的元素，例如，q o s x = 饼，q ；，q ：) 和q d 驴 q ，彤，饼) 是两个不同服务x 、 y 的q o s 集，比较对应元素饼与纠( 卢1 ，2 ，”) ，可以区分x 、y 。根据网格服 务的q o s 需求，定义以下几个基本的q o s 参数： ( 1 ) 服务的响应时间q r ：服务请求发出与该请求结果收到之间的时间延迟， 包括3 个基本部分：计算时间棚，中间件处理时间甜，传输时延。q 7 1 = m + 矿死伽。 ( 2 ) 服务的可用度必：服务能成功运行的比率。翻可以定义为成功运行次数 与总被分派次数的比率： 瓯( 墨) 级= 生l 一以 公式( 2 - 1 ) 其嘲跗吲跗= 骺翥? 蓦赫 ( 3 ) 服务的资源需求q j r ：反映了服务对各类型资源的需求，纵本身也构成集 合贮 甜，胪七r c t u , ) ，每个元素代表相应资源类型。 ( 4 ) 服务的价格q c ：使用某个网格服务需支付或收取的服务费用。q c 在服务 选择匹配中是需要单独确定的q o s 参数，供求双方均可定出自己期望的q c ，但 1 0 硕士学位论文 第二章网格计算中的q o s 和资源管理 q c 在整个网格服务市场中遵循市场的价格规律。 因此描述某个网格服务s 的q o s 属性集q o s f 饼，q j ，q ：，鹾) ，更严格的 q o s 需求，还可添加新参数到q o s 属性集。在进行q o s 服务匹配时，面对数目 众多的q o s 参数，尤其是q r 参数本身还嵌套集合，使得匹配变得困难，影响服 务选择的进行。而网格服务质量数s q n 既能反映各种q o s 参数约束，又能反映 网格服务的整体质量特性。 定义2 3 服务质量数 服务质量数( s q n ) 是服务质量特性量的表征，反映了服务本身质量的高低， 受各q o s 参数( 除q c 外) 共同约束，即网格服务& 的s q n 是其q o s 参数( 除 q c g b ) 的函数f ：( q o s ，一 q ；) ) 一s q n ，v x ，量q d 墨一 碰) ，令： s q n i = 愕鼍，勰粉 渊2 叫 由上可知：d o m f = x f q d 墨一 鳞i ) ，r a n f = s q n , - 酬+ 。设s q n ig 0 ，明，v x 薯 造成服务s 事实上不可用，则s q n i = 0 ，例如，若q r 超出用户忍耐的极限，或 鳊中的某些资源没有满足导致服务无法运行，或幽超出了服务可用度的最低极 限等等。设想s u ps q n i = d 是一个可计算的确定值，s q n i 代表了服务& 质量的 量化值，在现实应用中，服务& 不存在没有上限的服务质量，即s u ps q n f # + o o 。 s u ps q n i = d 可以参照服务市场，结合网格服务实现技术的实际得到确认，或者 由己知的最好服务确定。 有了服务质量数s q n 的度量，就能对墨的服务质量有直接简洁的认识，有 助于确定服务& 的q o s 参数o c 。假定服务提供者和使用者给出的q o s 数据都是 真实可信的，根据现实生活中人们对商品市场的认知规律，在同等条件下，质量 不同的商品应用不同的价格，质量好的商品具有较高的价格，在网格服务市场也 应该遵循同样的认知规律，因此有如下推论： 推论2 1 在同等条件下，网格服务的价格因服务质量数s q n 不同而有差异， 通常s q n 越大，则q c 越高；设单位质量数s q n 价格差异的偏差因子为t ，则有： a 缈：t s q n 专p 公式( 2 - 3 ) 其中，s q n 代表质量数的偏差，p 代表单位质量数价格的偏差，价格偏差 因子t 由网格服务市场根据价格公式确定。 然而“假定服务提供者和使用者给出的q o s 数据都是真实可信的 这一假 设在实际中往往难以保证，为此，文献 5 8 1 提出了一种考虑q o s 数据可信性的服 务选择方法，方法从q o s 数据来源的角度对质量属性进行分类和计算：对于数 据来自服务提供者的质量属性，使用以往运行数据统计，对提供者的q o s 数据 硕+ 学位论文 第二章网格计算中的q o s 和资源管理 进行修正；对于数据来自服务使用者的质量属性，通过计算用户间以往反馈的相 似程度权衡不同q o s 反馈数据的可信程度，并给出了实现框架。 根据经济学原理，基于纳什均衡的思想【5 9 1 和s q n 概念，以下提出一种q o s 服务的价格确定模型。 2 2 2 网格o o s 服务的价格确定模型 建立非合作两方博弈模型，q o s 服务的请求方和提供方进行博弈，获得对单 位质量数价格鼽的均衡。设请求者集合为r = ，1 ，r 2 ，r d ，n z + ；提供者集合 为v = v l ，耽一，) ，n 矿；参与者为= r ，1 ，) ，锹，1 ，比p 户 b p z + ) ， k = - i ，2 分别作为，和1 ，的纯策略集；肌r ，k = l ，2 是参与者各自为单位质量数s q n 所定的价格； u k k = - l , 2 分别为，和v