（电力系统及其自动化专业论文）水火电力系统最优潮流问题的分布式计算研究.pdf

as t u d yo fd i s t r i b u t i n gs o l u t i o nf o rh y d r o t h e r m a lo p t i m a lp o w e rf l o wp r o b l e m s a b s t r a c t h y d r o t h e r m a lo p t i m a lp o w e rf l o w ( h t o p f ) i so n eo fl a r g es c a l ed y n a m i cn o n l i n e a r o p t i m i z ep r o b l e m ，t h ea m o u n to fc o m p u t a t i o ni sf a rg r e a t e rt h a nt h ec l a s s i c a lo p t i m a lp o w e r f l o w ( o p f ) w i t ht h es y s t e ms c a l ei se n l a r g ea n dm o d e li sd e m a n dm o r ea c c u r a t ec o n t i n u o u s l y , t h ep r o b l e mi sh a r dt ob es o l v e db yt r a d i t i o n a lc e n t r a l i z ec o m p u t i n g ，t h ec a l c u l a t i o np e r i o d so f o p e r a t i n gc y c l ei ss h o r t e ra n ds h o r t e r , c o r r e s p o n d i n gd r a m a t i ci n c r e a s ei nt h ea m o u n to f c o m p u t a t i o n ，e s p e c i a l l yw h e nc o n s i d e r e di nt h em o d e lo fc a s c a d eh y d r o p o w e rp l a n t s ，t h e a c t u a lo p e r a t i o nc h a r a c t e r i s t i c s ，t h ee n t i r eo p e r a t i o nm u s tb ec o n s i d e r e dau n i f i e dc y c l e ，w i l l b e v e r yl a r g ea m o u n to fc o m p u t a t i o n ，t h ep r o b l e mi s h a r dt ob es o l v e db yt r a d i t i o n a l c e n t r a l i z e c o m p u t i n g t h er e s e a r c ho nh i g h - p o w e r e dp a r a l l e lh t o p fa l g o r i t h ma n di t s d i s t r i b u t e di m p l e m e n t a t i o nb e c o m eaq u e s t i o nf o rd i s c u s s i o n t h i sp a p e ru s e da c c u r a t ed e c o m p o s em e t h o di np r i m a l - d u a li n t e r i o rp o i n tm e t h o d ( p d i p m ) u n d e rp e r t u r b e dk a r u s h - k u h n - t u c k e r ( k k t ) c o n d i t i o n s ，d e c o u p l e dt h el a r g e s c a l er e d u c e d c o r r e c t i o ne q u a t i o n ，t h e ng e tad i s t r i b u t e dc o m p u t i n gm e t h o d sf o rh t o p f b yd e c o u p l e dw i t h p e r i o d s a c c o r d i n gt ot h ed i s t r i b u t e da l g o r i t h m ，t h ep a p e rp r o p o s e sd i s t r i b u t e dc o m p u t i n g p r o g r a mb a s e do nap c - c l u s t e rw i t hm a t l a bd i s t r i b u t e dc o m p u t i n ge n g i n e ( m d c e ) p c - c l u s t e rh a sah i g hp e r f o r m a n c ea n dp r i c er a t i o a n dm d c ei sp o w e r f u li nn u m e r i c a l c o m p u t i n g b ys i m u l a t i o ni nm a t l a bd i s t r i b u t i n ge n v i r o n m e n tw i t hp c - c l u s t e r ，l a r g e s c a l e h t o p fp r o b l e mi ss o l v e ds u c c e s s f u l l y t h r o u g ht h ef i v et e s t s y s t e mi n f i v ed i f f e r e n t o p e r a t i n gc y c l et or u nt h es i m u l a t i o nr e s u l t s ，t h er e s u l t sv e r i f yt h a tt h ep r o p o s e dd i s t r i b u t e d a l g o r i t h mp o s s e s s e sag o o dc o n v e r g e n c ep r o p e r t yi nad i s t r i b u t e de n v i r o n m e n t ，t h er e a lm o d e l r e f l e c t st h ea c t u a lp o w e rs y s t e mi nv a r i o u st h ep o w e rp l a n to u t p u t ，a n dt h ec a s c a d e h y d r o p o w e rp l a n to p e r a t i o n ，m a n yc p ut i m e si ss a v e d ，a n dh e n c e ，t h em e t h o di sq u i t e p r o m i s i n gf o rl a r g e - s c a l ea p p l i c a t i o n s s o m ep r o b l e m sa r eh a n d l e de f f e c t i v e l y , s u c ha s c o m m u n i c a t i o nf l u x ，l o a db a l a n c e ，a n dt h eg o o da c c e l e r a t er a t ea n de f f i c i e n c yi so b t a i n e d k e yw o r d s ：d i s t r i b u t ec o m p u t i n g ；h y d r o t h e r m a lp o w e rs y s t e m ；o p t i m a lp o w e rf l o w ； d e c o u p l i n ga l g o r i t h m ；i n t e r i o rp o i n tm e t h o d “，0 ，“l l ，“f 2 6 2 ，岛，b o ， c l 七，c 2 七，c 3 七，c 4 k ，c 5 七，c 6 七 f ，醮 艺 咒 呓 ，鲸 g 口，b 4 e l ， 弓 玩 z ，r ， 丁 最 s b s 。 s g ，s r s c l ( ) ，( ) 主要符号对照表 火电厂f 的燃料费用系数 固定水头电厂f 的耗水量与所发有功关系系数 变水头水电厂后的水耗系数 节点f 的可调有功和无功电源 火电厂f 的有功输出 固定水头电厂f 的有功输出 变水头k 的有功输出 节点i 的有功和无功负荷 节点f 与节点，之间的转移阻抗 节点f 电压的实部和虚部 线路，和，之间有功功率 水电厂k 第，时段的流量； 梯级水电厂k 第f 时段的库容 梯级水电厂k 第f 时段的天然进水量 梯级水电厂k 的初始库容和最终库容 时间段 调度周期内的时间段数 系统节点集合 梯级水电厂集合 固定水头水电厂集合 有功和无功电源的集合 约束线路集合 变量的下、上限制 广西大学学位论文原创性声明和学位论文使用授权说明 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下完成的，研究工作所取得的成果和相 关知识产权属广西大学所有。除已注明部分外，论文中不包含其他人已经发表过的研究 成果，也不包含本人为获得其它学位而使用过的内容。对本文的研究工作提供过重要帮 助的个人和集体，均已在论文中明确说明并致谢。 论文作者签名：裼先磊 了一弓年；只_ 移e t 学位论文使用授权说明 本人完全了解广西大学关于收集、保存、使用学位论文的规定，即： 本人保证不以其它单位为第一署名单位发表或使用本论文的研究内容； 按照学校要求提交学位论文的印刷本和电子版本； 学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务； 学校可以采用影印、缩印、数字化或其它复制手段保存论文； 在不以赢利为目的的前提下，学校可以公布论文的部分或全部内容。 请选择发布时间： ， 留即时发布口解密后发布 ( 保密论文需注明，并在解密后遵守此规定) 论文作者签名：裼爰磊 导师签名： 嘶月7 日 广西大掌硕士掌位论文 水火电力系统最优潮流问题的分布式计算研究 第一章绪论弟一早 三石下匕 1 1 课题的意义 水火电力系统最优潮流问题( h t o p f ) 是水火电力系统在满足某些工程上和运行上 的约束条件下达到某一最优运行目标，如运行成本、系统损耗或联络线的交换功率等为 最小时的潮流分布。因其考虑了潮流方程，故比传统的水火电力系统经济调度问题更具 有实际意义【。 随着我国电力工业的发展，电力系统己进入了高电压、大机组、大区域的时代。我 国电网已由省际互联进入到了跨大区互联和全国联网的新阶段。电网规模迅速扩大，相 应的计算量与计算复杂程度急剧增加，对仿真分析提出了更高的要求。面对大规模的 h t o p f 问题，传统的单机串行计算方法已经无法满足大电网模拟、在线动态安全分析 和实时控制的要求。在这种情况下，利用多机环境下的分布式求解h t o p f 问题，就成 为解决这一问题的有效方法。 基于p c 机群( p c c l u s t e r ) 环境下实现分布式计算的工程应用，是一种性能价格比高 的方法，既满足了较高的计算要求，又能充分利用现有的计算资源。可以容易地实现从 前只能在价格昂贵的大型超级计算机上才能进行的计算。 本文使用的基于分块理论的精确解耦算法将大规模的h t o p f 问题按照时段分解为 若干个可以并行计算的子问题，大大缩减了求解规模；同时，由p c 机群进行并行计算， 可以显著提高计算速度，缩短计算时间。 综上所述，以分布式计算的方式求水火电力系统最优潮流问题是符合科学发展潮流 的，处于电力系统计算研究的前沿。与传统的单机串行计算相比，它能够有效解决计算 中遇到的计算量大、运算时间长等问题，达到更快的计算速度，适合于求解多时段大规 模的系统。 1 2 水火电力系统最优潮流研究现状 水火电力系统的最优潮流问题( h t o p f ) 早期见于1 9 8 9 年，h h a b i b o l l a h z a d e h 等人提 出了一种新的最优潮流模型，该文考虑了水压模秀! 的水电模型，求解方法是z o u t e n d i j k 用于求解非线性规划问题的可行方向法。其线性和非线性约束包括了电流和电压的平衡 约束以及有功平衡约束1 2 j 。 1 9 9 8 年，h w e i 将内点二次规划引入到水火电力系统规划问题中1 3 j ，加入了潮流方 程以及线路约束等实际的物理约束，从而使h t s 问题成为了水火电力系统最优潮流问 题( h t o p f ) ，并基于拉格朗 1 松弛法和k k t 条f ， ：，将h t o p f 解耦为火电o p f 子问题 广西大掌硕士掌位论文水火电力系统最优潮流问题的分布式计算研究 和水电计划子问题。 2 0 0 0 年，h w e i 推导出了一种求解h t o p f 问题的现代内点算法，并将该算法成功 的扩展于求解次最优的h t o p f 问题( a h t o p f ) ，使求解速度提高了l - - - 2 倍。该文还定 义了一种新的变量顺序，导出了一种由4 t x 4 t ( t 为调度周期) 块状对角子矩阵组成的新 的数据结构，使得h t o p f 问题易于编程与求解【1 1 。 2 0 0 5 年，广西大学蔡广林的硕士学位论文里，推导出了两种将h t o p f 问题按时段 解耦的算法。一种采用近似牛顿方向法，将修正方程系数矩阵用近似的分块矩阵代替， 在满足一定条件下，算法具有局部的收敛特性；另一种是精确分块法，算法直接从修正 方程出发，推导了耦合约束的拉格朗同乘子变化量的公式，并有效地避免了分解产生的 矩阵求逆部分的计算。该文基于所提出的两种解耦算法，分别利用m p i 和c o n d o rm w 开发了基于p c 网格的分布式计算程序。并通过在4 台p c 机组成的分布式环境中仿真， 成功地求解了大规模系统的h t o p f 问题，有效地处理了通信流量、负载均衡等问题， 达到了较好的加速比和效掣训。 1 3 分布式计算在电力系统中的应用现状 电力系统分布式计算的早期应用可见于2 0 世纪5 0 年代，g k r o n 为了解决大规模网 络的网损问题提出了“分割论 的概念，将一个大系统分割成许多个较小的子系统，首 先求解各个子系统，然后考虑系统的互联，对各个子系统的解进行修正和组合从而得出 原始未分割大系统的解【5 】。这种基于分块思想的并行处理技术已经广泛应用于电力系统 的短路、潮流、稳定性、无功优化和经济调度等许多问题的计算中。 1 3 1 在潮流计算问题中的应用 潮流计算要求解一组由潮流方程描述的非线性代数方程。目前的并行潮流计算方法 主要足对三角分解、前代回代计算部分的并行化。例如，对矩阵的重新组合分块以发掘 其并行性、采用多重因子分解和稀疏逆因子方法、基于电力系统运行模式及人工神经网 络的潮流并行算法等【6 】。与牛顿法相比，这些方法的收敛性比较差，而且是细粒度并行， 在分布式环境中很难达到理想的效果。较好的方法是基于传统的分块理论，将系统划分 为几个小区域并行求解，由于具有较大的划分粒度，因而能够满足分布式环境的要求。 1 3 2 在暂态稳定分析中的应用 电力系统暂念稳定分析需要求解描述旋转运动的时变微分方程和描述电网的代数 方程，这组微分代数方程的求解需要耗费大量的计算时间。随着电力需求的不断增长和 电网规模的不断扩大，所形成的微分代数方程维数也在不断增长，使得进行一次暂念稳 定计算的时i u j 急剧增加。目前，分听i 式处理技术已经在电力系统静态安全分析和在线颅 广西大学硕士掌位论文水火电力系统最优潮流问题的分布式舌1 - 算研究 决策紧急控制系统等方面得到了应用，通过将预想故障分配到多台计算机上同时计算， 能够有效地提高在线稳定分析的速度【7 1 。 1 3 3 在能量管理系统中的应用 电力系统中的能量管理系统包括了s c a d a 、a g c e d c 、电力系统静态安全分析、 电力系统动态安全分析、d t s 调度员培训仿真等板块。从2 0 世纪9 0 年代起，能量管理 系统由原来的封闭式、集中式的孤立系统向开放式、分布式的集成系统发展。系统由多 台工作站构成，将不同的功能及数据库根据需要分配到不同的工作站【8 】。这是一种粗粒 度的并行处理方式，适合电力系统的结构特点和计算要求，因此能量管理系统在分布式 平台上得到了广泛应用。 1 3 4 在电力系统规划中的应用 电力系统规划需要考虑国民经济发展计划，动力资源的合理开发和利用，发、输、 变、配电设备配套的建设和协调发展等诸多因素。各种因素、不同条件的组合将产生大 量的可选方案，通过各种方案的对比分析，提出最优的、分阶段的、具体的电源和龟阿 规划需要进行大量计算。采用基于方案的分布式处理可以大大缩短计算时间提高效率。 1 3 5 在最优潮流问题中的应用 最优潮流问题是为一个非线性规划问题，在考虑燃料最省限制、线路潮流大小限制、 安全稳定、机组启停、变压器抽头和电容器投切组数等问题后，会成为一个极其复杂的 问题。采用分布式处理能够有效地提高该问题的计算速度。目前的一个研究热点是区域 最优潮流，通过区域的划分，将各子区域的计算作为可并行部分进行分布式求解。 1 9 9 7 年，k i m 和b a l d i c k 提出了一种最优潮流问题的分布式计算模型，通过增加虚 节点，将大系统解耦，再采用增广拉格朗日法进行求解【9 j 。1 9 9 9 年，他们又将内点法用 于该模型，在p v m ( p a r a l l e lv i r t u a lm a c h i n e ) 分行式计算平台上，对一个2 5 8 7 条线路的 实际系统( e r c o t ) 进行求解，计算的加速比可达4 6 ，效率为5 7 9 1 0 j 。 1 9 9 9 年，e j n o g a l e s 等人提出了一种新的求解互联大规模电力系统最优潮流问题的 方法l 。2 0 0 2 年，他们进一步证明该方法具有局部收敛性【l2 1 。2 0 0 3 年，a n a s t a s i o s g b a k i r t z i s 等人将该方法用于d c o p f 问题的求解i l 引，并用i e e er t s 9 6 系统和5 8 3 节 点的b a l k a n 实际系统进行仿真。计算结果表明该方法算法简单、易于实现，能利用系 统本身的结构特点，通信数据量少。 1 3 6 在无功优化问题中的应用 无功优化问题在电力系统电压稳定和经济运行中占有很重要的位置，也足提高电力 广西大学硕士掌位论文水火电力系统最优潮流问题的分布式计算研究 系统电压质量的一个重要措施。2 0 0 7 年6 月，广西大学的石韦针对实际电力系统的数学 模型包含离散变量和连续变量的特点，提出了一种精确求解电力系统无功优化问题的方 法原始对偶内点法结合分支定界法。通过把离散变量连续化，采用原始对偶内点法 在可行域内进行全局寻优，并结合基于广度优先遍历的分支定界法对离散变量进行归整 处理，从而找到比传统无功优化更加合理的全局最优解【l4 1 。由于求解大规模电力系统无 功优化问题的单机运算耗时相当巨大，该文采用性能价格比高的p c 机群( p c c l u s t e r ) 、 数值计算能力强大的m a t l a b 分布式计算引擎( m d c e ) 和分布式计算工具箱( d c t ) 搭建 分布式计算平台，实现了无功优化问题的分布式计算。 近年来p c 机群作为一种分布式计算系统，由于其性能价格比高、升级和可扩展性 好，越来越受到电力研究人员的广泛关注。目前，已经在机电暂态仿真【i l 、无功优化【l6 | 、 电磁暂态仿真1 1 7 1 等多个研究领域得到应用。正因为其在性价比方面与其他分布式计算系 统相比具有无可比拟的优势，本文的研究也选择了p c 机群作为分布式计算平台。 1 4 本文的主要工作 本论文介绍了水火电力系统最优潮流、内点法、精确解耦理论、分布式计算等问题， 着重对大规模水火电力系统最优潮流的精确解耦算法的分布计算做了分析和研究。为了 快速有效的求解大规模水火电力系统的最优潮流问题，提出了一种分布式并行计算的现 代内点算法，采用分块法以时段为单元对原问题进行精确解耦，在m a t l a b 分布式计 算平台上，采用主从方式来组织局域网内的多台电脑进行并行计算。文章对分布式的算 法进行了详细的设计，并讨论了m a t l a b 分布式计算平台的特点。用2 5 个算例进行了 1 7 5 次测试的仿真结果表明：本文所提算法在保证了不影响原问题计算精度的前提下， 大大减小了h t o p f 原问题的计算规模，显著的提高了计算速度，为以后的实时在线计 算奠定了基础。 本论文结构如下：第二章，讨论分御式计算系统的定义与分类，介绍本文中使用的 分布式计算硬件和软件环境，p c 机群，通过实例介绍m a t l a b 分布式计算环境，并总结 出分布式算法设计应注意的问题；第三章，对本文使用的基本算法现代内点法的发 展、分类、原理、公式推导、算法流程和特点等作了说明，并对内点法在电力系统优化 领域的应用作了综述；第四章，从o p f 问题的一般模型丌始，介绍了水火电力系统最 优潮流问题的数学模型，并给出分向式并行计算方法的思路与程序流程；第五章，用2 5 个算例分别在单机和p c 机群环境下对水火电力系统最优潮流问题进行仿真分析，通过 串行和分布式计算的对比，证明所提出的分布式计算方法的正确性和有效性；最后，在 第六章对全文作了概括性的总结，指出存在的不足，并对未来的研究和发展进行探讨和 展望。 4 广西大掌硕士掌位论文水火电力系统最优潮流问题的分布式计算研究 第二章m a t l a b 分布式计算 2 1引言 由于大规模集成电路技术的迅速发展，使得计算机也获得了令人惊叹的发展。今天 的计算机同数十年前相比，计算速度更快，内存容量也更大了，因此计算机的联网也更 为普遍。分布式系统正是在此基础上兴起的。从六十年代末期开始，关于分布式系统的 研究就开始引起了人们的注意【l 引。 近几年来，机群网络分布式计算已经成为国内外研究的热门课题。机群系统分布式 环境在进一步完善之中，不少国外大学推出了自己的机群系统，商业机群也逐渐成熟起 来。在国内，中国科学院和国内一些大学投入了相当的力量对其应用理论和方法进行研 究，如国家智能计算机研究开发中心的有关机群的在研项目，机群系统f o 负载的收集 与分析、面向机群和网格的分布式构件平台研究和集群服务器功能软件等。 随着科学技术的进步，高性能计算机的计算速度和容量的迅速增长，以前无法实现 的大型计算问题得到了很好的解决。许多科技工作者在解释自己研究的科技领域中出现 的物理现象时提出了一些相当复杂的数学理论和计算技术问题，而这些理论和方法都要 大规模的计算来解决，最后通常归结为求解大规模方程组等，不少应用软件在求解方程 组方面耗费的实际计算时间占8 0 以上。因而，研究高效的分布式算法及其计算环境引 起了国内外许多科学家的注意1 1 9 j 。 2 2 分布式系统 2 2 1分布式系统的概念 分布式系统是指其整体不在一个物理位置上，而是在地理位置广是散布分开的，通 过通讯线路连接在一起的综合计算机网络系统。如果从其完成的工作来考虑，我们则可 以对它作进一步的解释，即一个工作任务，是出在若干个不同的位置上，但通过计算机 网络连接在一起的不同计算机系统协调地完成的；或者，在不同的位置上通过计算机网 络连接在一起的不同计算机系统所运行的不同任务，依赖通讯线路进行通讯和协调i 婚】。 分布式系统是由多个处理器或计算机系统组成的，这些计算机可以是在物理上相邻 的，使用机器内部总线或丌关连接的处理器，通过共享主存进行通信；也可以是在地理 上分开的，使用计算机网络( 远程网或局部网) 连接的计算机系统，使用信件进行通信。 这些计算机组成一个整体，对用户是透明的，即用户使用任何资源时都不必知道这些资 源在：哪罩【2 0 1 。 水火电力系统最优潮流问题的分布式计算研究 2 2 2 分布式系统的分类 从结构上分，分布式系统有两大类：紧密耦合系统和松散耦合系统。 有共享主存贮器的分布式系统称为紧密耦合系统，通常也叫做多处理器系统。这种 系统中的处理器也常常有自己的专用主存贮器，因为处理器和主存贮器之间需要有较高 的通信速度。紧密耦合系统一般限于一个局部区域，各部分相距很近，可以说是在物理 上分散的，但不是在地理上分散的。各处理器交换信息是通过共享主存进行的。 在松散耦合系统中，各处理器没有共享主存贮器，其互联通过某种输入输出机构， 它们可以共享外部设备。 松散耦合系统中由于处理器不共享主存贮器，只能用交换信件的方法进行通信。它 可用远程网络( w a n ) 组成，也可用局部网络( l a n ) 组成，一般是在地理上分散的系统。 日前绝大部分松散耦合分布系统都是由l a n 组成的。本论文采用的也正是这种系统。 根据组成松散耦合分布系统的计算机机种，可以把松散耦合分布系统分为三种模 式：小型机模式、工作站模式和处理器库模式。 在小型机模式中，系统由若干具有多用户的小型机组成，每个用户在一台机器上鸯 录，就可对其他机器进行远程访问。这种模式是集中式分时系统的简单扩充。 在工作站模式中，每个用户有自己的工作站，它通常有功能很强的处理器、主存贮 器和图形显示终端，有时还配有硬磁盘，几乎能完成所有的工作。之所以将它归为分布 式系统，是因为其系统中有一个全局的文件系统可供各个工作站访问。 处理器库模式是工作站模式的进一步发展。分时系统的中央处理器( c p u ) 数目对登 录的用户数之比通常远小于l 。这个比数在工作站模式中近于l ，而在处理器库模式中则 远大l 。随着c p u 越来越便宜，处理器库模式将越来越普遍。这种模式的主要思想是： 当一个用户需要较多的计算时，将若干个c p u 暂时分配给此用户，工作完成时再将这 些c p u 归还给处理器库，等待下一个请求。 还可将上述三种模式混合起来组成新的模式，例如一个系统中除了工作站之外还可 以有处理器库。 按照组成分布式系统的计算机种类划分，分布式系统可以分为同构型分布式系统和 异构型分布式系统。 异构型分布式系统由若干不同的硬件和软件系统互联而成；同构型分布式系统由相 同或非常相似的硬件和软件组成。 计算机的异构性主要表现在硬件和软件两个方面： ( 1 ) 硬件方面 首先是指令系统不同，也就是说一个机器上的程序模块不能在另一种不兼容的机器 上运行；其次是数据表示方法不同；还有就是机器系统配置不同，即使棚f 川的c p u 也 可能有不同大小的生存和外部设备配置。 6 水火电力系统最优潮流问题的分布式计算研究 ( 2 ) 软件方面 即使硬件完全相同，如果运行的操作系统不同，则由这些机器组成的系统仍为异构 型。软件不兼容首先体现在操作系统所提供的功能可能大不相同。其次是操作系统提供 的系统调用在语法、语义和功能方面也不同。第三，文件系统不一样。 现代的科学技术飞速发展，使得具有不同性能的计算机型号层出不穷。一个单位对 计算机性能的要求不断变化和提高，不可能满足于己获得的单一型号的计算机。这就使 得异构型分布式系统的存在是不可避免的。 本论文为了尽量避免异构性带来的麻烦，在一个小型的局域网中采用了同构型分布 式系统。 2 2 3 分布式系统的优点与不足 分布式系统主要有以下优点： ( 1 ) 增加性能 增加处理部件的数目提高并行程度，可以得到所要求的性能； ( 2 ) 可扩充性 随用户需求的增长，包括功能方面的要求和性能方面的要求，增加新节点数，不必 替换整个系统； ( 3 ) 可靠性 由于控制、数据、软件和硬件的分散性( 不存在集中环节) ，资源冗余以及结构上可 动态重组，提高了对靠性； ( 4 ) 资源共享 系统中的软件、硬件资源如外部设备、文件系统和数据库等可为多个用户共享； ( 5 ) 经济性 由于可扩充性，可以避免较大的初始投资，用多个微小型机代替一个大型主架机， 可以获得很好的性能价格比； ( 6 ) 适应性 对于很多应用场合，比如银行、铁路、商业等本来就分散而又必须相互协调的部门 很适应。 由于分布式系统具有很多优点，所以发展很快。用户的需求极大地刺激了分布系统 的发展，现代半导体技术及计算机网络通信技术的飞速发展为分布式系统的发展提供了 技术保证。 同时，由于分布式系统包含多个( 可能是不同种类的) 分散的、自治的处理资源，要 想把它们组织成一个整体最有效地完成一个共同的任务，比通常集中式的单一计算机系 统要例难得多，还存在着一些问题。 广西大学硕士掌位论文 水火电力系统最优潮流问题的分布式计算研究 首先，由于处理资源的多重性，系统可能产生的差错类型和次数都比集中式系统多。 最明显的是所谓部分失效问题：系统中某一个处理资源出故障而其他计算机尚不知道， 单一计算机任何一部分出故障时都将停止整个计算。另一个是多副本信息一致性问题， 多重性资源使得差错处理和恢复问题变得很复杂，还给系统资源管理带来了困难。 其次，系统资源在地理上的分散性带来很多问题。在松散耦合系统中，使用信件在 进程之间通信，而通信可能产生不可预测的、有时是巨大的延迟，特别是在远程网络所 组成的分布式系统中更是如此。分布式的状态信息和不可预知的信件延迟，使得系统的 控制和同步问题变得复杂。要想及时地、完整地搜集到系统各方面的信息是很困难的， 从而使处理器进行最佳调度变得困难。在分布式系统中，用户或程序常常要访问远程资 源如数据、程序或进程等，与访问本地资源相比也变得复杂了。 在异构型分布系统中，由于各种不同资源的数据表示和编码、控制方式等均不相同， 就产生了翻译、命名、保护和共享等新问题。 鉴于上述原因，分布式系统的研制，特别是软件的验证、调试、测试和维护问题都 变得很复杂。这也是分布式系统殛待解决的问题。 2 3 分布式计算环境 分布式系统环境由一组提供分布应用丌发、分布系统执行和管理的软件组成。这组 软件包括编程语言、编程工具、系统管理工具和运行时支持工具等【2 。图2 一l 从用户的 角度展示了分布式计算环境组成的层次结构。用户在终端计算机上可以访问不同规模的 应用系统和信息资源，这些应用系统建立在运行于分布计算基础结构的分布式服务上， 而分布计算的基础结构又是建立在网格计算的基础结构上的。用户可以直接访问分布式 服务，对于最终用户来说，分布式计算环境提供了一个无平台、无地理隔阂的个人化信 息处理环境；对于应用丌发人员来说，分布式环境提供了统一的框架结构和基本的服务 支持，降低了分布式应用系统开发的复杂性，提高了互操作性、可移植性和代码的可重 用性；对于采用分布计算的组织机构而言，分布式计算环境使其信息系统获得了灵活性、 可缩放性，以及对信息的实时访问和快速开发业务的途径；对系统管理者来说，分布式 计算环境意味着管理复杂性的增加1 2 2 。 用户的个人化计算环境卜_ 在线信息企业系统部j 、j 系统 分布武服务 系统管理：分布汁算基础设施 i 】c ) 络管理计算平台和数据通信基础设施 图2 1 分布式计算环境 f i g 2d i s t r i b u t e dc o m p u t i n ge n t i r o n m e n t 广西大掌硕士掌位论文水火电力系统最优潮流问题的分布式计算研究 2 3 1 分布式计算环境和网络计算环境 分布式计算环境是建立在网络计算环境的基础上的。网络计算环境包括计算平台、 数据通信基础结构和支持网络计算的基本服务。网络计算环境上的用户在共享资源、存 取信息、实现计算机之间的通信时无需关注网络的传输行为。但是网络计算环境缺乏系 统的管理，不提供一个集成运行在多个平台上的应用软件的基础结构。这些问题正是分 布式计算环境殛待解决的。支持平台无关、资源分布透明性的分布式计算基础结构和分 布式服务是分布式计算环境与网络计算环境在功能组成上的主要区别。 2 3 2 分布式计算环境与分布式计算系统 分布式计算系统通常是指一种用通信网络连接在一起用于协同完成事务处理的自 主计算机群。而分布式计算环境的概念范围要更广泛些，包括各种规模的应用系统、分 布式服务和分布计算基础结构。 2 3 3 分布式计算环境与合作计算 合作计算技术是指有关多个平台上的应用相互作用、协同工作的技术，客户端朋艮务 器( c s ) 计算技术就是一种合作计算技术。但是合作计算技术不仅仅局限于c s 模式，还 可以是对等模式的。分布式计算环境包含了合作计算技术，也是合作计算应用的开发平 台。但是分布式计算更强调异构环境中分布应用的集成，而合作计算主要关注应用之间 的协同性。 2 3 4 分布式计算环境与开放系统 分布式计算环境必然是一个开放系统。分布式计算环境的目标就是要实现在异种环 境下的应用集成，因此建立分布式计算环境必须遵循丌放系统的原则。 2 4 分布式算法 分布式算法是用于解决多个互联处理器运行问题的算法【2 3 1 ，指在那些分布在一个大 的地理区域中的多个处理器上运行的算法。分和式算法的各个部分并发地、独立地运行， 每一部分只承载有限的信息。即使处理器和通信信道以不同的速度运作，或即使某些构 件出了故障，这些算法仍然应该正常工作。 分布式算法有广泛的应用：电信、银行、分布式信息处理、科学计算以及实时进程 控制等。例如，今天的电话系统、航班订票系统、银行系统、全球信息系统、天气预报 系统以及飞机和核电站控制系统都严重依赖于分确j 式算法。很明显，确保分布式算法准 确、高效运行是非常重要的。当我们为某项应用搭建一个系统时，如何设计、实现和分 9 厂西大学硕士掌位论文水火电力系统最优潮流问题的分布式计算研究 析分布式算法将是一个重要的环节。 2 4 1分布式算法与集中式算法 分布式算法和集中式算法在设计的方法和技巧上，有着非常大的不同，原因在于分 布式系统和集中式系统在系统模型和结构上有着本质的区别，集中式算法中所具备的一 些基本特征，在分布式算法中，已经不复存在了。分布性和并发性是分布式算法的两个 最基本的特征。 相对于集中式( 单处理器) 计算机系统，分布式算法有以下不同【2 4 】： ( 1 ) 缺乏全局状态知识 在集中式算法中，是基于对系统状态的观察做出控制决策的。即使在一次单机操作 过程中不能访问整个状态，程序也可以一个接一个地检查变量，考虑所有相关的信息后 做出决策。在检查及决策的过程之间，不修改数据，从而保证了决策的完整性。 分布式系统中的节点只能访问它们自己的状态，不能访问整个系统的全局状态。因 此它们不可能基于全局状念来做控制决策。一个节点可以接收其它节点的状态信息，并 以此信息作为控制决策的基础。与集中式系统相比，所接收的陈旧信息可能导致信息失 效。因为在发送信息的过程和基于此信息做决策的过程时，其它节点的状态可能已经改 变了。 节点不能直接观察到通信子系统的状态，这个信息只能通过比较节点所发送和接收 的消息而间接推断出。 ( 2 ) 缺乏全局时间帧 构成集中式算法执行的事件，完全自然地按照事件发生的时间来定序；对于每一对 事件，或一个早于一个，或一个迟于一个。 组成分布式算法执行的时间所导致的时序关系并不是全序的，对于某些对事件，可 以决定事件的先后，但对于其它一些事件，则不能确定时序。 在集中式系统中可以实现互斥，如果进程甲对资源的访问在进程乙访问之后，那么 进程甲必须在进程乙结束之后才能丌始对资源的访问。这类事件通过时序关系就可以决 定顺序。而在分布式系统中，却不能做到这一点。进程甲和进程乙可能开始访问资源， 但是它们开始的先后次序却不能确定。 ( 3 ) 非确定性 集中式算法描述计算，是明确地从某一输入丌始的；给定程序和输入，只有一种计 算可能。 相反，由于系统各部分在执行速度上的差异，分布式系统的执行通常具有不确定性。 分布式系统的执行存在着许多不稳定性的因素。由于这些多方而的差异，导致分御 式算法的设计和分析，较之集中式算法来讲，要复杂得多，也困难得多。 1 0 广西，调粤硕士学位论文 水火电力系统最优潮流问题的分布式计算研究 2 4 2 分布式算法的分类依据 分布式算法有许多种类型，它们的分类所依据的属性包括【2 3 】： ( 1 ) 进程间通信( i p c ) 的方法 分布式算法运行在一组处理器上，而这些处理器需要以某种方式的通信。一些常规 的通信方法包括访问共享存贮器、发送点对点或广播的消息( 在广域网或局域网上) 以及 执行远程过程调用。 ( 2 ) 时序模型 关于系统中时间的时序可以作几种不同的假设，这反映了算法可能会用到不同的时 序信息类型。一种极端情况是处理器完全同步，通信和计算在完美的锁一步同步中进行。 另一种极端假设情况是它们完全异步，以任意的速度和次序进行。两者之间有大量可能 的假设，这些假设可以归纳为部分同步的，在这些情况下，处理器具有关于事件时序的 部分信息。 ( 3 ) 故障模型 算法运行的底层硬件可以被假设为是完全可靠的，或者算法需要容忍一定限度的故 障行为。这些故障行为可能包括处理器故障，即处理器可能在给出或不给出警告的情况 下停止工作；也可能暂时发出错误；或表现出严重的故障，比如一个出错的处理器可以 作出任意的动作。出错行为也包括通信机制的故障，包括消息丢失和消息重复。 ( 4 ) 需解决的问题 算法要视其要解决的问题而有所差异。一些典型问题包括资源分配、通信、分布式 处理器之间的一致性、数据库并发控制、死锁检测、全局快照、同步以及各种对象类型 的实现等。 2 5 搭建分布式系统应注意的一些问题 搭建分布式系统主要应当解决的是通信流量和负载平衡的问题。由于组成机群的硬 件环境中各个p c 机的性能都比较高，如计算机的内存易于扩充，c p u 的性能也得到了 极大的改善，相对而言单台p c 机的性能提高己不是关键问题，而负责数据通信的网络 技术却显得更为重要。这是因为分布式计算时机群系统内的各个处理器之间的数据需要 通过网络进行通信。如果网络通信延迟时i 、日j 太长，加上通信软件的时l 、h j 丌销，即使算法 的内在并行性在程序的处理上很完美，都有可能使得分布式计算效果的体现并不理想。 另外，负载平衡的程度也是分布式计算程序设计时必须要考虑的关键因素，负载的均衡 分配可以避免处理器之间大量的通信丌销，从而提高整个分布式计算系统的效率。 ( 1 ) 通信流量 分布式系统是基于高速通信网络并由结点计算机互联而成的系统1 2 5 1 。网络性能的好 水火电力系统最优潮流问题的分布式 i t 算研究 坏对分布式系统计算效率的提高、处理问题的适应范围以及系统的可扩展性都有影响。 分布式系统中各处理器间采用通用网络以松散耦合的方式互联。影响网络性能的一 个重要因素是通信迟延，它包括网络硬件的处理时问和协议软件的处理时问。为了便于 实现与移植，常采用标准网络协议- t c p i p 协议，虽然它为远程的异构网络互联提供 了很好的解决方法，但却带来了很大的时问开销。 随着网络技术的发展，影响网络通信性能的主要因素将不再是网络硬件的性能，而 是通信软件的处理丌销。对于分布式系统而言，网络系统分布的范围越小，通信链路的 可靠性也就越高。当系统内参与分布式计算的处理器之间通信可以通过同构的网络来实 现时，可以考虑设计新的精简通信协议，减少传统通信协议的层次从而缩短通信软件的 处理时间。 ( 2 ) 负载平衡 在分布式计算中，一个大的任务通常由多个子任务组成。被分配到各个处理结点上 并行执行的子任务就是所谓的负载，负载在分布式计算系统的各处理结点上分布的均衡 程度叫做负载平衡度，把各个子任务分配到各处理结点上并行执行的技术称为负载平衡 技术。 任何分布式计算都需要提高并行应用的有效性，负载平衡是必不可少的。当系统的 子任务较多时，各个结点上的负载如果产生不均衡现象，将会降低整个系统的利用率。 负载不平衡问题将直接影响整个分布式计算系统的性能。因此，负载平衡是影响分布式 计算效率的一个重要因素。 解决负载平衡问题通常有两种方案【2 6 1 ，静态负载平衡和动态负载平衡。在设计负载 平衡系统时应当考虑到网络结构、系统构造( 异构或同构) 、系统的利用情况( 用户数量、 系统的平均负载量、通信流量等) ，以及系统的可靠性因素等。 静态调度算法是根据系统的先验知识做出决策，运行时负载不能重新分配1 27 。静态 调度算法的目标是调度一个任务集合，使它们在各个目标结点上有最短的执行时间。设 计调度策略时要考虑的三个主要因素是处理器的互连、任务的划分以及任务的分配拉引。 动态负载平衡是根据计算机过程中数据项的变化情况，交换系统的状态信息来决定 系统负载的分配。它具有超过静态算法的执行潜力，能够适应系统负载的变化情况，比 静态算法更灵活、有效。动态算法可以利用系统状态的短期波动来提高性能。但它必须 收集、储存并分析状态信息，因此动念算法会产生比静态算法更多的系统丌销，但这种 丌销常常可以被抵消掉i 列j 。 采用动态负载平衡算法的目的足为了在并行计算系统的操作中，使得任务的分配执 行达到最优或接近最优p ，从而尽可能的减少整个计算任务的处理时i u j ，更大程度的提 高计算资源的利用率。因此动态负载平衡在机群分布式并行计算系统中占有十分重要的 位置。 除了通信流量和负载甲衡，还应该注意计算粒度的划分以及现有资源的重复利用 广西大掌硕士掌位论文水火电力系统最优潮流问题的分布式计算研究 等。在分布式计算中，粒度还可被定义为任务的计算量与通信量之比。粒度太大会限制 并行性，因为潜在的并行任务可能被划分给同一个任务而分配给一个处理器；粒度划分 太小，通信的开销就会增加，从而降低并行计算的性能。 2 6m a t l a b 分布式计算平台 近年来，人们针对分布式处理系统已经开发出了多种编程工具和开发环境。在以 p c c l u s