（电力系统及其自动化专业论文）网格计算在大型电力系统中的应用研究.pdf

摘要 f i r s tg r e e d ya l g o r i t h m ) ，以及根据时间和花费所占比例构造效益函 数的思想。该算法以效益函数作为资源分配的目标函数，利用贪心 算法选择效益函数的最大值，最终实现网格资源分配的效益最大化。 针对传统的电力系统集中式处理的特点，提出了在电力系统中 应用网格技术的方案，并将s m m 算法及b f g 算法应用于电力网格 中。这是一个全新的课题，具有可移植性和扩展性。它可以有效缓 解那些长期制约电力系统发展的难题，成为电力系统分析和计算中 至关重要的工具和手段。 本课题的独创性在于提出了基于网格计算环境下的大型电力系 统分析和计算的概念，目的在于分析电力系统网格的任务分配与分 割、资源利用与查找；利用m a t l a b 语言进行仿真，有效实现网格任 务调度及资源分配；并将s m m 算法及b f g 算法应用于电力系统网 格，总结出电力网格在任务调度和资源分配等方面应用的具体方案。 文章最后总结了本文的主要内容、成果及结论，并为今后进一 步的研究工作指明方向和重点。 关键词：网格计算；任务调度；s m m 算法；资源分配：b f g 算法： 电力系统 i l a b s t ra c t g ridc o m p u tin gm e t h o d o l o g yinl a r g e s g a l ep o w e r s y s t e m a b s t r a c t t h ep o w e rs y s t e mi nc h i n ai sn o wu n d e rt h ew a yo fd i s t e n s i b l e s c a l ea n dc o m p l i c a t e dm o d e l s o m eb o t t l e n e c kp r o b l e m s ，s u c ha s s h o r t a g eo fm e m o r ya n ds l o w - f o o t e dc o n v e r g e n c e ，w i l lb ec o m ef o r t hi f w ea d o p tt r a d i t i o n a lm e a n st oa n a l y z et h el a r g e s c a l ep o w e rs y s t e m f u r t h e rm o r e 酊dc o m p u t i n gc a l le x e r tt h ea d v a n t a g eo fm u l t ic o m p u t e r a n da c c o m p l i s ht h ej o bw i t hl o w e rc o s ta n df a s t e rs p e e dw h i c hw o u l db e f i n i s h e db ys u p e rc o m p u t e rp r e v i o u s l y t h i sd i s s e r t a t i o nf o c u s e so nt h e s t u d yo fg r i dc o m p u t i n gm e t h o d o l o g yi nl a r g e s c a l ep o w e rs y s t e ma n d t h ei n n o v a t i o no ft a s ks c h e d u l i n ga n dr e s o u r c ed i s t r i b u t i n g m o r e o v e rw e a p p l yt h ei n n o v a t i v ea l g o r i t h mt op o w e rs y s t e ma n ds i g n i f i c a n ts t r a t e g y w i l lb ep u tf o r w a r d ： a st h e k e y , t a s ks c h e d u l i n g a n dr e s o u r c e a l l o c a t i n g a r et h e b o t t l e n e c ko f 西dw h i c hs l o w e dt h ec o m p u t i n gs p e e da n de f f i c i e n c y a n e w 鲥dt a s ks c h e d u l i n ga l g o r i t h m ( s m m ：s t a b l em a t c h i n gm e c h a n i s m ) b a s e do nm a t c h i n gp r o b l e mi sp r o p o s e da n dt h eq u a n t i f i c a t i o nm a t c h i n g m e t h o df o u n d e do ne a c hc o n d i t i o nv a l u ea n di t sp r o p o r t i o nv a l u ei sp u t f o r w a r d t h eu s e ra n dt h er e s o u r c ec a nd y n a m i c a l l yp r e s e tt h eb e n c h m a r k v a l u e so fe a c hc o n d i t i o nf o l l o wa l o n gw i t hi t sc h a r a c t e ra n do b t a i nt h e m a t c h i n gd e g r e ev i at h ec o m p a r i s o nw i t ht h ea c t u a lv a l u e s a c c o r d i n gt o t h er a n ko ft h em a t c h i n gd e g r e e ，s m mc a nc i r c u l a r l ym a t c hu n t i l 1 i i a b s t r a c t s t a b i l i z a t i o n t h ed e m a n do fb o t ht h eu s e r sa n dt h er e s o u r c ei sc o n s i d e r e d i n s ，m ma n dt h er e l e v a n ts t a b l em a t c h i n gs c h e d u l i n gs t r a t e g yc a r lb e o b t a i n e d t h es i m u l a t i o nd e m o n s t r a t e st h a ts m mc a l li m p l e m e n t 西d t a s k s c h e d u l i n ge f f e c t i v e l y a n da s t r a t e g yw i l lb ep r o v i d e dt ot h e s c h e d u l i n gc e n t r e t h eh e t e r o g e n e o u sr e s o u r c ei st h ed i f f i c u l t yo f 西d an e wg r e e d y a l g o r i t h mb a s e do nb e n e f i tf i r s to f 鲥dr e s o u r c ed i s t r i b u t i n g ( b f g ： b e n e f i tf i r s tg r e e d ya l g o r i t h m ) i sp r o p o s e da n dt h ec o n s t r u c t i o no f b e n e f i tf u n c t i o nf o u n d e do nt h ep r o p o r t i o nv a l u eo ft i m ea n dc o s ti sp u t f o r w a r d t a k i n gb e n e f i tf u n c t i o na st h eo b je c to fr e s o u r c ed i s t r i b u t i n g ， b f gc a ns e l e c tt h em a x i m u mo fb e n e f i tf u n c t i o nv i ag r e e d ya l g o r i t h mt o a c h i e v et h eb e s tb e n e f i t t oo v e r c o m et h ed i s a d v a n t a g ei nc e n t r a l i z e dp r o c e s s o ro fp o w e r s y s t e m ，as c h e m eo fg r i da p p l i c a t i o ni np o w e rs y s t e mi sb r o u g h tf o r w a r d t h es p a n n e ws u b je c th a st h ec h a r a c t e ro f t r a n s p l a n t a b l ea n dp a t u l o u s i t c a ns o l v et h ei n e x t r i c a b l ep r o b l e mi np o w e rs y s t e ma l lt h ew h i l e ，a n di s t h ei n d i s p e n s a b l yi m p o r t a n tt o o lf o ra n a l y z i n ga n dc o m p u t i n gi np o w e r s y s t e m t h eo r i g i n a la s p e c to ft h i sp a p e ri st h a ta c o n c e p to ft h ea p p l i c a t i o n o fg r i di np o w e rs y s t e mi sp u tf o r w a r d t h eo b j e c ti s s t u d yo ft a s k s c h e d u l i n ga n dr e s o u r c ed i s t r i b u t i n gi np o w e r 西d t h es i m u l a t i o ni n m a t l a bd e m o n s t r a t e st h a tt h e s ea l g o r i t h m sw i l li m p l e m e n t 酣dt a s k s c h e d u l i n ga n dr e s o u r c ed i s t r i b u t i n ge f f e c t i v e l y u l t i m a t e l yw e m a k eu s e o fs m ma n db f gi np o w e r s y s t e ma n dd e s c r i b es i g n i f i c a n tb l u ep r i n to f t h ea p p l i c a t i o ni np o w e rg r i d i v a b s t ra c t f i n a l l y , t h i sp a p e r s u m m a r i z e st h e i m p o r t a n t c o n t e n t sa n d c o n c l u s i o n s ，a n dp o i n t so u td e v e l o p m e n tr e s e a r c hi nt h ef u t u r e k e yw o r d s ：g r i d ；t a s ks c h e d u l i n g ；s m ma l g o r i t h m ；r e s o u r c e d i s t r i b u t i n g ；b f ga l g o r i t h m ；p o w e rs y s t e m v 广西大学学位论文原创性声明和学位论文使用授权说明 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下完成的，研究工作所取得的成果和 相关知识产权属广西大学所有。除已注明部分外，论文中不包含其他人已经发表过的 研究成果，也不包含本人为获得其它学位而使用过的内容。对本文的研究工作提供过 重要帮助的个人和集体，均已在论文中明确说明并致谢。 j 论文作者签名： 南砍 学位论文使用授权说明 o q 年6 旯 fe l 本人完全了解广西大学关于收集、保存、使用学位论文的规定，即： f 本人保证不以其它单位为第一署名单位发表或使用本论文的研究内容； 按照学校要求提交学位论文的印刷本和电子版本； 学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务； 学校可以采用影印、缩印、数字化或其它复制手段保存论文； 在不以赢利为目的的前提下，学校可以公布论文的部分或全部内容。 请选择发布时间： 口即时发布口解密后发布 ( 保密论文需注明，并在解密后遵守此规定) 论文作者签名：碣砍导师签名论文作者签名：) 冈磊失 导师签名 精多月2 4 - e t 第一章绪论 第一章绪论 1 1 研究背景及意义 现代电力系统的运行与控制已演变成一个涉及大量数据和大规模计算的应 用工程，电力系统正在朝着一个数据密集型、信息密集型、通信密集型和计算 密集型的大型系统转变【l 】。 电力系统具有广域分布、参数海量、模型复杂等特点，随着电力系统规模 的日益扩大和对在线监控要求的不断提高，采用传统数学分析方法计算较大规 模的电力系统会存在计算机内存不足、收敛速度慢等维数灾难问题。而并行算 法的出现可以有效发挥机群的优势，以较快的速度和较低的成本完成以前需要 大型计算机才能完成的工作。目前并行算法已经在潮流计算1 2 1 、暂态稳定分析【3 】、 静态安全评估1 4 j 等方面得到了应用。 1 9 9 9 年出现了关键电力架构防御系统【5 i s p i d ( s t r a t e g i cp o w e ri n f r a s t n l e t u r e d e f e n s es y s t e m ) ，2 0 0 0 年卢强提出了架构数字化电力系统【6 】d p s ( d i g i t a lp o w e r s y s t e m ) ，这两个系统均试图以一个集中的仿真工作站群来重建实际的互联电力 系统。它们的一个共同特点是集中控制和计算，但在一个大型的信息交换系统 中，集中控制和计算还存在很多不足之处。目前，网格计算【7 - l o 】被认为是建立超 级计算的一种较好的方法，基于网格计算的系统与传统的集中系统相比有许多 优势，它充分结合了分布式计算和集中式超级计算的优点，不但能为用户提供 可靠的服务，而且能为现代电力系统大规模计算提供理想的解决方案。 1 多年以来，电力生产管理形成了一整套“分级管理、分层控制、分布处理 的体系。传统的电力系统集中式处理的计算方式，可移植性和扩展性差。因此， 在电力系统中应用网格计算技术是一个全新的课题。它能解决电力系统中长期 无法解决的难题，成为电力系统分析和计算中不可缺少的重要工具和手段。 本课题的独创性在于提出了基于网格计算环境下的大型电力系统分析和计 算的概念，目的在于分析电力系统网格的任务分配与分割、资源利用与查找； 利用m a t l a b 语言进行仿真，有效实现网格任务调度及资源分配；并将s m m 算 法及b f g 算法应用于电力系统，实现网格计算在大型电力系统分析和计算等方 面的应用。该课题对于电力系统分析和计算的发展完善以及网格计算这种先进 第一章绪论 技术在实际中的应用都有着非常重要的意义。 1 2 国内外研究现状和发展动态 1 2 - 1 国外研究现状 美国 g l o b u s h i 项目是美国a r g o n n e 国家实验室等科研单位的研发项目，主要针 对信息安全、资源管理、信息服务、数据管理以及应用开发环境等网格计算的 核心理论和关键技术进行了深入的研究。该项目的主要成果是开发出一种通用 工具包软件，这种工具包能在多种平台上运行用以规划和组建大型的网格试验 和应用平台，并由此开发适合大型网格系统运行的大型应用程序。 ： l e g i o n t l 2 1 项目是1 9 9 3 年在弗吉尼亚大学开展的一个基于对象的元系统软件 项目，目标是为用户提供单一、一致的虚拟机器模型。 c o n d o r t l 3 】项目是由威斯康星一麦迪逊大学研发的、专用的计算密集型负载 管理系统。 欧洲 2 0 0 0 年1 2 月，欧盟提供一千万欧元资金启动欧洲数据网格e u r o p e a n d a t a g r i d ( e d g ) 【1 4 】，该项目是一个国际性大型研究和技术发展项目，预期在3 年内完成。e d g 主要应用于高能物理领域，解决大量数据的分解、存贮及处理 等问题，使得分布在世界范围的工作者可以突破地理局限，交互、共享数据和 设备，并共同开展科学研究的合作环境。 亚洲 亚洲很多国家的网格计划已经启动，并各自成立了全国网格论坛。其中， 日本和韩国的网格项目已初具规模。日本的国家网格已经连接到欧洲数据网格， 主要用于高能物理实验等方面大规模数据的分析和处理。 其他 在数据传输方面，j o es h a n g e h i e hw u 和a l a ns u s s m a n 提出了一种在并行程 2 第一章绪论 序之间允许松弛耦合的数据传输模型i l5 ，该模型能够灵活控制并行程序间数据 的输入和输出。s a t o s h is h i r a s u n a 和a l e k s a n d e rs l o m i n s k i 在p e r f o r m a n c e c o m p a r i s o no fs e c u r i t ym e c h a n i s m sf o rg r i ds e r v i c e s 1 6 1 文中介绍了不同的网格安 全机制并比较它们的性能，认为传输层安全要高于信息层安全，如果没有特殊 要求应使用传输层安全协议。 在网格系统方面，s e b a s t i e nl a c o u r 和c h r i s t i a np e r e z 等人提出一种网格应用 配置的网络拓扑模型【1 7 1 ，该模型能够有效地解决计算网格的异构性；l i g a n gh e 和s t e p h e na j a r v i s 等人提出一种具有q o s t l 8 1 。【2 2 1 需求的并行任务在集群和网格 中的动态调度模型【2 3 】，该模型以( 最终期限、时间跨度、闲置时间) 共同组成 衡量调度性能的可变分量。与传统调度模型相比，该模型能够明显提高集群之 间的调度性能，而且错误预报的提出并没有使其优越性消弱。 1 2 2 国内研究现状 在我国，从1 9 9 8 年国家科技部的国家高技术研究发展计划( 8 6 3 ) 启动中 国的“高性能计算环境项目开始至今，网格计算已在中国经历了8 个春秋。 尤其是在国家“十五”计划期间，国家各部门先后启动了很多网格项目，其中 包括国家科技部的国家高技术研究发展计划( 8 6 3 ) “中国国家网格( c n o r i d ) 、 教育部2 1 l 公共服务体系建设项目“中国教育科研网格计划( c h i n a c , d d ) 、国家 自然科学基金委的重大项目“以网络为基础的科学活动环境研究一、国家重点 基础研究发展规划( 9 7 3 ) q 日的“语义网格的基础理论、模型、方法及关键技术一 和“虚拟计算环境聚合与协同机理研究等。这些研究项目在网格的各个方面 都取得了非常重要的成果。 其中，最具代表性的项目是由中科院在2 0 0 1 年提出了织女星网格计划【硎。 该项目的目的是实现一台虚拟的、单一的网格超级计算机。织女星网格体系结 构的关键部分由网格操作系统、网格硬件及网格互联系统等组成。另外，该项 目也同时提出了资源路由器、网格浏览器、网格计算协议等重要概念。 网格技术领域 文献 2 5 】 2 7 】讨论了网格系统软件的关键技术，包括系统软件体系结构、资 源管理、用户管理、作业管理等。文献【2 8 】讨论了如何设计支持网格的机群操作 第一章绪论 系统。文献 2 9 1 【3 0 】讨论了网格监控系统的关键技术。 文献【3 1 h 4 2 】讨论了网格系统软件的关键技术，重点研究了网格资源发现及 其模型、文件系统与作业管理、服务和多数据副本定位，并有针对性的对作业 管理及元数据发布、事务处理、代理技术以及对等网络中资源共享等方面进行 讨论。 文献 4 3 1 针对网格的特点提出了网程的概念，并将其与传统操作系统中的进 程相对比，总结二者的区别，并由网程代表网格主体，访问和使用网格资源。 文献【4 4 】进一步比较了进程和生物细胞之间的区别，动物细胞所特有的发育和有 性繁殖功能，正是进程缺乏的。在此基础上，文献提出发育计算的思想以及支 持发育计算的网程结构的一些重点。 文献 4 5 1 提出内存网格的概念，内存网格是一种面向广域网上内存资源共享 的新型网格系统。深入研究在物理内存不足的情况下，如何利用内存网格来提 高内存密集型应用或i o 密集型应用的系统性能。文献【4 6 】综合考虑了经济和信 任双方面，由此提出自适应的信任一激励相容的资源分配机制，并深入讨论了 网格环境中资源激励机制和分配机制之间的依赖与制约关系。文献1 4 7 提出了网 格q o s 的层次结构模型，并对q o s 参数进行新的分类和测量。在交付无缝q o s 的前提下，深入研究如何提高资源分配性能。 文献 4 8 】提出一种基于模糊聚类的网格异构任务调度算法。该算法利用模糊 聚类方法对处理单元网络这样的目标系统进行前期处理，并对其进行任务调度。 这样可以有效缓解网格环境中任务调度规模庞大、分布异构性和动态性等特点 所带来的计算压力，保障综合性能较好的处理单元聚类在任务调度时能够优先 地被选择进行调度。从而使搜索空间缩小，极大地降低了任务调度时选择处理 单元所花费的时间。 文献 4 9 1 提出了一个采用s o a 思想、支持多应用领域数据共享的数据库网 格系统d s g r i d ，实现用户按需要地对丰富的数据资源进行透明地访问和使用。 文献 5 0 1 提出了一种基于c a c h e 的反馈调度方法，这种方法可以有效地实现网格 任务的动态调度。目前网格环境下的任务调度具有自治性、动态性、分布性等 特征，该调度方法在c a c h e 中采集最近访问过的资源信息，对负载进行性能评 估，如提交时间、任务完成时间等，优先选择负载较小或性能较优的资源来进 4 第一章绪论 行任务调度。 文献 5 1 1 提出了一种基于q o s 约束的服务发现机制，并利用该机制提高服务 发现系统的可用性等问题。文献【5 2 】针对网格软件测试方面，首次提出一种面向 服务的关键技术，该技术主要研究网格软件测试管理、网格性能测试以及网格 服务测试这三个方面，探讨了网格软件测试环境的构建。 文献 5 3 】提出网格服务的概念，在网格工作流中引入服务质量作为衡量指 标，使得网格中的资源更好地按照用户的要求进行调度和分配。文献 5 4 1 提出了 一种独立任务的调度算法，面对网络通信速度不同和网格资源计算能力差异等 环境特点，在各计算节点最优任务分配数的基础上建立整数线性规划模型，该 算法可以有效实现任务调度。文献 5 5 】提出了失效检测器的概念，针对网格的 q o s 的自适应性，该元件可以有效检测出网格失效的进程，成为构建可靠的网 格计算环境所必需的基础组件之一。文献 5 6 】提出了优化用户时间的网格资源分 配策略，该策略以著名学者纳什的博弈论为基础，有效解决多用户争抢同一资 源所带来的困扰。 应用领域 在电力领域，文献【5 7 】介绍了网格计算的基本定义、模型特点和架构，分析 了现代电力系统的大规模计算特点，在c a c t u s l 5 8 1 的基础上组建电力网格系统应 用平台，提出了一种基于计算池的网格并行潮流计算方法。 文献【5 9 】- 6 h 在电力系统分析和解决问题的过程中引入网格计算技术，详细 分析了电力网格的体系结构，确定了电力网格的服务层次。文中对网格基础设 施和电网应用服务两方面进行了有效的划分和组合，设计了一套电力网格原型 系统加以实现，并在此原型系统之上实现了基于电力网格技术的分布式潮流计 算6 2 】- 【硎，总结出研究电力网格技术的关键技术问题并提供解决方案。文献【6 5 】 设计了一套矢量图形计算系统，该系统实现了在电力系统中的基于w e b 的企业 分布式【鲫。【6 7 1 的应用。 i 文献【6 8 】讨论了在天气预报系统中应用网格计算来实现的高分辨率中尺度 数值天气预报。文献【6 9 】介绍了一种并行油藏模拟软件，该软件由中国科学院软 件研究所研制，在曙光3 0 0 0 高性能计算机上实现对大庆油田油藏模拟的应用。 5 第一章绪论 文献【7 0 】提出了一种智能网格入侵检测系统，该系统结合智能检测技术，并 采用先进的网格体系结构，可以有效分辨出对网格系统的恶意入侵。文献【7 1 】 针对网格资源得异构性，研究如何为使用者提供全局统一视图和一致的访问接 口，文章以大学数字博物馆网格为例，提出了一种网格环境下模式复用的异构 数据库访问和集成方法。文献【7 2 】讨论了利用互联网来研究社会科学。 文献 7 3 1 一 7 5 】分别分析了网格技术在上海市智能交通系统、国家地质调查应 用系统和数字灌区g i s 系统中的应用。文献【7 6 】【7 7 】介绍了网格应用实现中的关 键技术，并提出一些新方法和新模型。在此基础上，介绍了在铁路系统信息管 理网格、面向北京2 0 0 8 年奥运会的奥运综合信息服务系统中相关技术的运用。 以上文献讨论了网格技术及其相关的基础性、前瞻性、战略性的重大理论 和关键技术问题，以及网格技术与其他学科的交叉性。对于网格计算这种先进 的技术在各个领域的应用奠定了坚实的基础。 1 2 - 3 存在的问题 网格计算作为计算机网络的第三代标志，正处在蓬勃的发展中。针对目前 网格计算技术的理论研究和应用现状，总结出如下问题： 缺乏协议的标准化 网格是指在动态变化的多个虚拟组织间实现资源共享和协同解决问题7 8 1 。 网格需要标准化，就像i n t e r a c t 需要t c p i p 协议一样。一方面，目前各行各业 的网格应用并没有提供很好的标准化协议，使得网格计算很难在不同行业之间 实现互通；另一方面，在行业内部也需要根据行业特点，制定网格应用的一些 行业标准，使得网格计算在行业内部的异构环境中可以实现共享和互通。 没有深入的行业应用 由于网格技术还不成熟，很多技术仍处于萌芽期。目前国内外科研机构在 一些领域的应用正如火如荼的开展，但由于缺乏统一的标准和相对完善的技术， 并没有深入到一定的层面。国内清华大学电机系牵头的9 7 3 子课题从事电力网 格的研究，采用网格技术实现全网的一体化防真。但是在电力系统在线测量和 计算中却没有得到深入的应用。 6 第一章绪论 与计算机软件技术的融合还不成熟 豳于目前的网格应用项目都处于开始阶段，还没有很好的人机交互界面， 可操作性不强。其中，霭向对象技术嘲、g l o b u st o o 髓t i s o l i 具包、开放网格服 务体系结构o g s a t s l 】等先进技术在网格的实际应用中仍有很大的发展空间。 1 3 本论文的研究工作及主要成果 本论文提出在大型电力系统中应用网格计算技术的思想，并针对网格计算 的两个核心阀题任务调度和资源分配，分粥提供有效麴解决策略。 针对网格的任务调度，本文提出基于稳定匹配机制的网格任务调度算法 ( s m m ：s t a b l em a t t i n gm e c 枷s m ) ，以及根据各条件因素值及其所占比率进行 量化匹配的思想。用户和资源可以根据自身特点动态地设置各条件因素的基准 值，通过与实际提供的条件因素值进行比较，得到匹配度，按照匹配度的高低 顺序循环匹配最终达到稳定。该算法熊有效地实现阏格任务调度，并给鼹格调 度中心提供一种调度策略。 网格资源的异构性一直是阻碍网格计算发展的难点，本文提出了种基于 效益优先的鼹格资源贪心选择分配算法( b f g ：b e n e f i tf 趣国匆趟g o 瘛趣) ， 以及根据时间和花费所占比例构造效益函数的思想。该算法以效益函数作为资 源分配的目标函数，利用贪心算法选择效益函数豹最大值，最终实现掰格资源 分配的效益最大化。 本文的主要内容安排如下： 第l 章圭要阐述了论文的研究背景及意义。 第2 章分析网格计算的技术核心。论述了网格的定义、特点及五层体系结 构；介绍g l o b u s 项目及萁设计模块，并简单阐述g l o b u s 工具包主要实现的四方 面内容。 第3 章分析网格计算的任务模型与调度策略，提出基于稳定匹配机制的网 格任务调度算法( s m m ：s t a b l e 池t c m n gm e c 碱s m ) ，以及根据各条件霹素值及 其所占比率进行量化匹配的思想。 第4 章分析网格计算的资源管理与分配，提出了一种基于效益优先的网格 资源贪心选择分配算法( b f g ：b e n e f i tf 遮q 毋越g 确蛙激) ，以及根据时阍 7 第一章绪论 和花费所占比例构造效益函数的思想。 第5 章介绍电力网格得体系结构和特点，并以电力系统负荷等效模型的建 立为例，在网格环境下，将负荷模型的大规模计算量分配到多台计算机上进行 协同工作，实现动态资源分配和协同解决问题。为电力系统实现网格计算提供 一种有效的解决方案。 第6 章总结了本论文的主要内容、结论及研究成果，进一步指明今后的研 究方向和重点。 1 4 创新点与先进性 针对传统的电力系统集中式处理的特点，本文提出了在电力系统中应用网 格技术的方案。这是一个全新的课题，具有可移植性和扩展性。它能解决电力 系统中长期无法解决的难题，成为电力系统分析和计算中不可缺少的重要工具 和手段。 本课题的独创性在于提出了基于网格计算环境下的大型电力系统分析和计 算的概念，目的在于分析电力系统网格的任务分配与分割、资源利用与查找； 利用m a t l a b 语言进行仿真，有效实现网格任务调度及资源分配；并将s m m 算 法及b f g 算法应用于电力系统，实现网格计算在大型电力系统分析和计算等方 面的应用。 8 第二章网格计算及其技术核心 2 。网格计算 第二章网格计算及其技术核心 2 1 j l 网格计算定义 。- 网格这一概念是在2 0 世纪9 0 年代中期提出，用来定义种适用于工程的分 布式和高端科学计算体系结构。网格的概念及其楣关技术最开始是为实现科研 协作中的资源共享蕊提出来的。随着规模日益扩大，这种基础设施的建设以及 其在商业计算方面的应用都取得了很大的进展。 鼹格是建立在i n t e r a c t 、w e b 等技术之上的综合软硬僻的基础设施，采震开 放、统一、标准的协议，通过对大规模分散资源的有效共享，为动态参与的多 个机构所组成的虚拟组织协同完成某项科学、工程或工业上的应用提供可扩展 的、安全的、一致的、普及的、不同等级质量的服务。 2 1 2 发展过程 全世界科研工作者历经l o 年左右的研究和开发，网格技术开始成型，并延 续至今继续发展。如图2 1 所示，我们可以将这个发展过程明显区分为四个不 同的阶段。 自定义方案： 在2 0 世纪钧年代早麓，研究重点集中在元计算及褶关领域的王俸，针对鼹 格计算问题开发自定义方案。这些研究工作的重点集中在使系统正常运转并研 究所能存在的可能情况。网格应用是直接建立在互联网协议之上的，从安全、 可扩展性和健壮性等蕉度进行考虑。应用只有一些非常有限的典型功能，恧且 互操作功能并非它的主要核心。 g l o b u s 王具集： + 1 9 9 7 年，开放源码的g l o b u s 工具集第二版( g t 2 ) 成为了网格计算的事实 标准。相比第一版，g t 2 更侧重于实用性和互操作性，它定义并实现了一些服 务、a p i 和协议，在世界范围内很多个网格平台中实现应用。遥过提供一些共 同问题的解决方案，例如授权认证、资源发现和资源访问等，g t 2 加快了网格 构建真实化的步伐；同样通过定义和实现标准化协议和服务，g t 2 率先创建了 爹 第二章网格计算及其技术核心 可以互操作的网格系统，并使得网格编程工具得到了重要的发展。g 就协议利 用现有的i n t e m e t 协议来实现资源发现、传输及安全机制。g t 2 协议套徉的一些 基本元素被编写入了正式的技术规范中，在标准组织内部进行审核，并在多种 实现中达到实例化。 翻 益 增 强 的 功 能 以 及 标 准 化 1 9 9 0 年 1 9 9 5 年2 0 0 0 年2 0 0 5 年 翻2 1 网格技术的发展 f i g2 1d e v e l o p m e n to fg r i d 开放式网格服务体系结构： 2 0 0 2 年出现的开放式网格服务体系结构( o g s a ) ，是一个真正意义上的 国际标准。它具有多种功能，包括了2 0 0 3 年发布的基于o g s a 的g t3 0 版本。 o g s a 在g t 2 基础之上，并最大限度地发展了g t 2 的概念和技术。通过采用面向 服务的结构以及w e b , q 蔓务技术，o g s a 很好地将网格计算和工业领域的应用有机 地结合起来。o g s a 定义了一个核心服务集，该服务集包含一些标准接口和行 为，- 可以解决以前面临的许多技术挑战。此外o g s a 提供了一种框架结构，在 该框架中，可以定义范围更广的可互操作的轻量级服务。o g s a 提供了一个基 础，在这个基础之上可组建由多个资源提供者组成的丰富的网格技术系统。 受管理麓共享虚拟系统： 1 0 第二章网格计算及其技术核心 o g s a 初始技术规范的产生是网格计算技术的一大飞跃，但在网格蓝图完 全实现之前还有很多问题亟待解决。在o g s a 的面向服务基础架构之上，得到 一个扩展的互操作服务集和系统。这个系统可以处理大量的实体喝一些小的设 备描述，使得可视化的程度更加透明化，共享形式更加丰富，服务质量得到增 强。 2 1 3 网格分类 r 计算网格 按功能划分 l 存储网格 2 1 4 网格计算特点 异构性 可扩展性 可适应性 结构的不可预测性 多级管理域 按应用划分 数据网格 r 计算网格 l 服务网格 2 1 5 网格的体系结构 沙漏形状的五层结构 沙漏形状的五层结构图见图2 2 ： 五层结构描述 1 ) 构造层：本地控制的接口。 构造层向上层提供对这些资源的管理和控制界面。构造层所提供的资源， 例如：计算资源、存储系统、目录、网络资源以及传感器等。对这些资源的共 享访问需要通过网格协议来决定。一个“资源所代表的可以是一个逻辑实体， 如一个分布式文件系统、计算集群或分布式计算机池；也可能是一些虚拟的协 议和算法。在这些协议或算法中，对资源的管理会涉及到内部的协议，但网格 体系结构所研究的重点并不在此。 2 ) 连接层：支持便利安全的通信。 第二章网格计算及其技术核心 连接层定义了通信和认证的核心协议，这些协议是针对专用于网格的网络 处理定义的。通信协议使得构造层韵资源之闻能够进行数据交换。认证协议构 建在通信服务之上，通过密钥安全机制来实现用户校验和资源身份的验证。逶 信的需求包括传输、路嘲以及命名等。虽然存在其他的协议，但是通常假定这 些协议是来自他黝p 协议栈。要特别指出的是，t c p 撙协议栈包括互联鼹鬃 次协议体系结构的口层( 职，i c 御) ，传输层( t c p ，u d p ) 以及应用层( d n s ， o s p f ，r s v p ，等等) 。 图2 2 沙漏形状的五层结构 2 2g r i ds y s t e m a t i cf r a m e w o r k 3 ，资源层；共享单一资源。 资源层建立在连接层通信和认证协议之上，定义单个资源上的共事操作协 议，如初始化、控制、安全协商、记账和付费等协议。在完成用户身份认证之 后，用户能够同远端的服务和资源进行交互。通过调用基础结构层的功能来实 现这些资源层协议，访瀚和控制本地赘源。分布式数据集中的全局状态等闯题， 是由汇聚层来解决的。资源层协议只关注单个资源，因而忽略了全局状态。 1 2 第二章网格计算及其技术核心 资源层的协议可以分为两种主要的类型： a 信息协议 b 管理协议 4 ) 汇聚层：协调各种资源。 汇聚层所定义的协议和服务是用来定义资源集之间的交互关系，不是专门 应对某一特定资源的。由于汇聚层建立在沙漏模型中资源层和连接层所构成的 协议瓶颈之上，故汇聚层可以实现多种不同的共享行为，而不需要对共享资源 施加新的限制。 5 ) 应用层：完成各种服务应用。 网格体系结构的最后一层一应用层，包含了在虚拟组织环境中运行的用户 应用。这些应用是根据其他层上定义的服务进行构造的。在每一层，都定义了 相关的协议和a p i ，如资源发现、资源管理和数据访问等，用来访问一些有用的 服务。 2 2g l o b u s 工具包 2 2 1g l o b u s 项目 g l o b u s 项目是美国阿尔贡国家实验室等科研单位的研发项目，对信息安全、 资源管理、数据管理、信息服务以及应用开发环境等网格计算的关键理论和j j 5 术进行了广泛的研究。该项目的主要成果是开发出一种通用工具包软件，这科 工具包能在多种平台上运行用以规划和组建大型的网格试验和应用平台，并由 此开发适合大型网格系统运行的大型应用程序。 目前，g l o b u st o o l k i t 已经从1 9 9 9 年的最初版本升级到基于新标准的网格平 台g l o b u st o o l k i t4 0 ，该工具包已经在世界上很多大型项目中得到广泛应用 和发展。 2 2 2g l o b u s 设计模块 g l o b u s 设计模块图见图2 3 ： 1 3 第二章网格计算及其技术核心 信息管理 g r i di n f o r m a t i o ns e r v i c e 厂 ll d a pl i 。一 g r i dr e s o u r c ei n f o r m a t i o ns e r v i c e llg r i di n d e xi n f o r m a t i o ns e r v i c e 资源管理 g l o b u sr e s o u r c ea l l o c a t i o n & m a n a g e m e n t d y n a m i c a l l y u p d a t e dr e q u e s to n l i n ec o a l l o c a t o r g s i 数据管理 g l o b u s a c c e s st os e c o n d a r ys t o r a g e 图2 3g l o b u s 设计模块图 f i g 2 3g i o b u sd e s i g nm o d u l e 2 。2 3g l o b u s 主要实现四个方面的蠹容 1 ) 网格安全 2 ) 网格信息获取与分布 3 ) 圈格资源管理 4 ) 网格远程数据传输 1 4 第三章网格计算的任务分析与调度 第三章网格计算的任务分析与调度 目前，国内外科研工作者在网格计算任务调度方面提出了多种策略和算法。 但由于网格任务调度是一个n p 问题，每一种策略都有它的侧重点和不足之处， 很多问题有待深入。 在以往的网格任务调度算法中，都只考虑了用户需求的某一种因素的优化 情况，没有同时对任务或资源的各方面条件因素进行综合评估，很难实现任务 与资源双方的稳定匹配。本章提出了一种基于稳定匹配机制的网格任务调度算 法( s m m ) ，并提出根据各条件因素基准值及其所占比率进行量化匹配的思想。 用户和资源可以根据自身特点动态地设置各条件因素的基准值及其权重，通过 与实际提供的条件因素值进行比较，利用匹配度函数得到量化后的匹配度，并 按照匹配度的顺序循环匹配最终达到稳定。算法综合考虑用户和资源双方的需 求而得出相应的稳定匹配调度策略。 3 1稳定匹配机制 稳定匹配问题【8 2 1 是由d a v i dg a l e 和l l o y ds h a p l e y 两位数学经济学家在1 9 6 2 年提出，最初用于讨论人员招聘过程中应聘者与公司之间的匹配问题，并使得 整个匹配过程通过自我完善达到稳定。由于应聘者与公司之间包含很多不对称 因素，比如，一个应聘者最终只能在一家公司上班，而一家公司却不是只招聘 一个应聘者。为了更好分析问题的本质，我们可以忽略掉很多复杂的因素，只 讨论刀个应聘者到力个公司的一对一映射。 假设对于每个应聘者，都对未来的工作有一定的要求，可能包括工资待遇、 劳动时间、工作强度等；同样，每个公司也