最优孤岛划分

最优孤岛划分（共3篇）

最优孤岛划分 篇1

0 引言

现代城市是大量重要用户的聚集地,一旦遭遇大面积停电,若不采取应急措施而等待电网修复后重新并网,经济损失和后果将十分严重[1]。移动应急电源(mobile emergency power source,MEPS)可以直接恢复配电网馈线的供电,分散地解决重要用户的停电问题,减少经济损失。从原理上讲,这是一种根本性的手段。在灾变发生时,如何有效地利用移动应急电源,最大限度地减少损失是移动应急电源运行的重要课题。移动应急电源可以接入配电网中任意馈线,通过形成一定范围的电力孤岛恢复岛内重要负荷的供电,因此,移动应急电源在配电网中的最优接入点以及最优孤岛范围的划定成为其运行的关键问题。学术界对此问题尚未深入研究,文献 [2]研究了MEPS在城市不同区域的优化配置,但其不涉及具体运行时的接入点和孤岛优化。文献 [3]研究了应急电源在城市各重要用户的配置,但仅限于固定应急电源,也不涉及运行方案的优化。本文提出了一种基于图论的精确递归的孤岛搜索方法,以孤岛内负荷的失负荷价值总和为指标评价不同接入点孤岛的优劣,并对最优孤岛内电源接入点进行多约束优化。最后提出了多台移动应急电源联合应急的接入点和孤岛搜索方案,69节点配电网的算例证明了该方法的有效性、实用性。

1 配电网图模型

1.1 配电网最小供电区域

配电网馈线开关是控制馈线带电与否的关键设备,因此定义有馈线开关或末梢节点包围的最小馈线段区域为最小供电区域。如图1所示,虚线包围的区域1,2,3都是最小供电区域。

图中:热201表示热水蒸汽厂负荷为201 MW, 其余简写见图注(下同)。在同一个供电区域内,馈线如果失电,则该区域所有负荷都将失电。移动应急电源接入配电网的方式十分灵活,可以直接通过自带的箱式变压器接入馈线,也可以通过配电变压器从负荷侧接入[4],一旦移动应急电源对该区域进行供电,该区域馈线所连接的负荷都能恢复供电。 即同一供电区域的负荷具有供电的同时性、一致性, 因此最小供电区域可以等效成一个节点。

1.2 配电网可控负荷与不可控负荷

配电网的负荷按照能否被调度直接控制并网或脱网可分为可控负荷和不可控负荷[5]。可控负荷安装有负荷控制终端,调度可以直接切除或并网。不可控负荷只要其所连接的馈线带电,就会被供电。 馈线失电,不可控负荷也失电,因此可以将最小供电区域内不可控负荷和馈线合并。而可控负荷则以开关元件与馈线关联。

1.3 配电网详细模型转化为图模型

由1.1节和1.2节可知,配电网转化为图模型的关键是:1供电区域内不可控负荷与馈线的合并; 2合并后线路等效阻抗的计算;3可控负荷的引出。 其中第2点关系到潮流计算的准确性,进而关系到应急电力孤岛的安全校验。文献[6-7]给出了双方向等效电压降落模型,这使得等效阻抗的计算有了理论基础。本文将一个供电区域内的负荷等效成一个节点,节点与节点之间以等效阻抗赋权的边连接, 等效阻抗计算及推导见附录A。

图2显示的是对图1等效后的图模型,各边等效阻抗见附录A。图2中:粗体数字表示节点编号, 其余数字表示fi/pi,其中pi为用户的有功负荷 量,fi为负荷i的重要度。由于配电网都是开环运行,因此图模型是典型的一棵树。第2节将对节点赋权形成节点 赋权树,建立孤岛 搜索算法 的图论基础。

2 基于电力失负荷价值的节点赋权

移动应急电源不但能为电力公司减少损失,同时也作为现代城市应急反应体系的一项重要资源。 然而由于移动应急电源造价高,配置数量有限,不可能在配电网发生停电时满足电网所有负荷的需求, 因此应优先恢复因失电可能造成巨大经济损失或威胁人身安全的负荷。基于投入—产出法的电力失负荷价值(VOLL)理论是分析电力对不同用户的经济价值的有效方法[8],本文采用单位失负荷价值作为各节点权值,以确定各个节点的重要性。其中由于大型医院一般都自配发电机,且人身安全无法用经济价值估计,因此在此不考虑医院负荷。

表1列出了图1配电网中所有用户的有功负荷量pi和单位失负荷 价值系数 (权值)ki。 令fi= piki为负荷i的重要度。由于系数ki的含义是损失单位电量的价值,因此重要度fi实质上表明的就是损失该负荷带来的经济损失。移动电源接入点最优目标也就是要使其恢复的负荷重要度之和∑fi达到最大,即经济损失最小。

3 接入点确定的应急孤岛搜索数学模型

移动应急电源接入供电区域后,相当于一个分布式电源(DG),可以在其供电能力范围内形成电力孤岛,以保证重要负荷的供电。当接入点确定后,孤岛的搜索或划分问题成为形成孤岛的关键问题。文献[9]对孤岛划分领域的国内外相关研究作了全面的分析。文献[10]提出了基于有根树的DG孤岛搜索方案,从树根节点开始进行深度优先搜索,依次断开支路上 的负荷,直到满足 功率平衡 为止。 文献[11]提出了基于Prim算法的策略。文献[12]利用粒子群智能算法搜索孤岛,再对粒子进行连通性检验。文献[13]利用sollin算法求得最小生成树来实现孤岛搜索。

上述文献基本上从孤岛的最优性和孤岛的联通性两个方面对孤岛搜索进行了研究,但是为了保证孤岛的连通性,往往会牺牲一定的最优性。本文提出了一种基于图论的孤岛搜索方法。

3.1 最优孤岛搜索的数学模型

如图2所示,配电网图模型是一棵树T(V,E), 设接入点已经确定,以接入点为根节点,对该树进行节点深度优先搜索,按搜索顺序给节点编号,当一辆移动应急电源车接入某个节点后,建立如下最优孤岛搜索数学模型:

式中:f(T,P)表示初始树T在移动应急电源有功容量P的约束下形成的孤岛的节点重要度之和;V为树T的节点集合,为孤岛的所有节点;E为T的所有边的集合为孤岛内所有边的集合且满足任意(vi,vj)∈E都有i<j;vi表示节点i,若节点i被选入孤岛中,则xi=1,否则xi=0。 根节点电源所接的节点,编号为1。

式(1)中最优目标是选入孤岛的负荷的失负荷价值总和最大,第1个约束表示应急电源的有功容量约束,第3个约束的含义是当某节点被选入孤岛, 其父节点必定也被选入,即连通性约束。

3.2 求解方法

式(1)所描述的单个应急电源的孤岛搜索问题, 本质上是带 祖先约束 的背包问 题 (precedenceconstrained knapsack problem,PCKP),所谓祖先 约束,即当某节点被选入背包,则其祖先节点亦必须被选入,PCKP是NP难问题,无法在多项式时间内求解。基于图论的精确递归算法是解决PCKP问题的有效方法[14],本文借鉴其求解过程,解算确定接入点情况下的最优孤岛方案和对应的失负荷价值总和,然后依次求解配电网等效图中以各节点作为接入点的情况下孤岛的失负荷价值总和,其中失负荷价值最大的孤岛接入点就是最优接入点,在该接入点形成的最优孤岛就是应急电源最优供电范围。

4 基于图论的精确递归算法

4.1 左右孩子图的关系树的生成

对于树T0(V0,E0),以接入点为树根,按照深度优先搜索顺序进行编号,在T0的任一条链上,如果编号沿着链依次递增(递减),那么编号小(大)的节点称为编号大(小)的节点的祖先(后代),并规定节点自身是自己的祖先(后代)。用符号Dv来表示节点v的所有后代组成的集合。设T(V,E)是T0的任意子图,定义其中编号最小的节点为t(T)。当|T|=1时,称T为单身图;当T=Ø时,称T为空图。对于T,可以定义 其左、右孩子图,TL:= T|V{t(T)},TR:=T|VDt(T),即左孩子图是图T去掉最小编号节点后形成的图,右孩子图是图T去掉它最小编号的所有后代所形成的图。任意T可生成TL和TR,TL又能生成TLL和TRR,直到单身图没有左右孩子图为止。因此,从T0开始,穷尽其所有左右孩子图后,可以以链表的结构描述这些子图的关系,称为关系链。理论上子图数量与T0的节点数成指数关系,但实际上,当T0是树时,将产生大量相同的子图,若只保留不同的子图,则子图数与节点数相等。

图3显示了图2的树T0(以节点1为根)生成的所有左右孩子图及关系链,圆圈中编号为各个子图的编号,圆圈1代表初始树T0。在上述编号法则下,每个孩子图的内容有一定规律,即若子图的编号为n,则该子图是由节点n至34所形成的。如子图30,其父图是29,左孩子图是31,右孩子图是34, 其包含的节点是30至34,如图2虚线所包含的节点所示。

4.2 精确递归算法原理

以图2的树为例,令其为T0,设接入点为1号节点。根据3.1节的数学模型,需要在找出一棵以节点1为根的树(孤岛),使该树在节点负荷总和在给定容量P之内的约束下,节点重要度之和最大。 从T0(子图1)的最小编号节点t(T0)开始考虑,若选择t(T0)进入孤岛,则孤岛重要度之和f*(T0, P)可以表示为ft(T0)+f*(T0L,P-pt(T0)),若不选入孤岛,则t(T0)的所有后代都不能选入孤岛,重要度之和为f*(T0R,P),T0L是T0的左孩子图,即图3中子图2,T0R是T0的右孩子图,恰为空图。选择两者中较大者,显然空图的重要度为0,因此节点1必选入。 继续计算f*(T0L,P -pt(T0))= f*(G2,P-pt(T0)),G2表示图3中的子图2。同样,f*(G2,P -pt(T0))= max{ft(G2)+f*(G2L, P-pt(T0) -pt(G2)),f*(G2R,P -pt(T0))},其中G2L=G3,G2R=G3。pt(T0)=0,pt(G2)=189,ft(G2)= 321.3,如果前者大,则t(G2)入选,否则不入选。由于无法比较321.3+f*(G3,P-0-189)和f*(G3, P-0)的大小,继而需计算f*(G3,P-0-189)和f*(G3,P)。由此,递归开始,继而需计算f*(G4, P4),f*(G5,P5),…,f*(G13,P13),…,直到单身子图34(只含节点34)对应的

结束递归,若满足P34≥p34,选入节点34,否则不选入,算法完整步骤见附录A。

以图2为例,设以节点1为接入点,容量约束P=41,依次运行上述算法的程序,可得选入孤岛节点为1,4,13,20,25,26,30;重要度总和为868.74, 恢复的负荷总 和40,留有1的裕度容 量。在图1中,粗虚线围出了该孤岛的恢复范围。此时形成的孤岛只是初始孤岛,满足工程需要的孤岛完整形成过程在第5节讨论。

5 单台移动应急车接入点的搜索策略及应 急孤岛的形成

5.1 最优孤岛的接入点搜索

孤岛最优接入点描述的是在哪些节点范围内形成最优孤岛的问题。上例中,当容量为41的移动应急车接入节点1时,可以得到重要度总和为868.74, 如果依次将电源接入图模型中的每个点,每次都能形成一个最优孤岛,枚举这些孤岛的重要度总和,总共34个数据。表2列出了其中部分数据。

由计算得出,当电源接 入节点13,15,20,25, 26,29,30,31时,重要度总和并列最高,并且形成的孤岛也相同。

5.2 孤岛内电源最优接入点搜索

为了最大限度地利用宝贵的应急电源资源,需在孤岛的节点范围内选择一个网损最小的节点,即使得min∑ri|Ii|2(i∈Eisland)的节点作为接入点,其中,Eisland为孤岛内边集合,ri为边的电阻,Ii为流过边的电流。本例中,经计算,节点25为最优接入点,其网损最小。除了网损最小这一目标外,孤岛还需满足有功和无功容量、安全、稳定等约束,以满足工程化的需要。因此,孤岛内最优接入点的搜索本质上可转化为多约束优化问题。

设移动应急 电源总形 成h个孤岛,H1,…, Hk,…,Hh是这h个孤岛的 节点集合,E1,…, Ek,…,Eh是每个孤岛的边的集合,分配给每个孤岛的移动应急电源集合分别为D1,…,Dk,…,Dh。 Hk={vk1,…,vki,…,vkt},孤岛k内各负荷有功和无功需求 分别为pk1,…,pki,…,pkt和qk1,…, qki,…,qkt。Dk= {Dk1,…,Dkj,…,Dks}。孤岛k内DG的最大有 功和无功 出力分别 为Pk1,…, Pkj,…,Pks和Qk1,…,Qkj,…,Qks。Ploss表示孤岛k内网损。

设研究对象为孤岛k,则目标函数为:

式中:rij为线路(vi,vj)的电阻;Pij,Qij分别为线路 (vi,vj)的有功和无功潮流;Vj为vj的电压。

约束具体如下。

1)功率约束

功率约束包含有功和无功功率两个部分:

式中:xij为线路(vi,vj)的电抗。

2)电压约束

式中:Vjmax,Vjmin分别为节点j的电压上、下限。

3)潮流约束

式中:Sij为通过线路(vi,vj)的潮流;Simjax为潮流上限。

4)电压稳定约束

采用文献[15]的电压稳定指标,即

式中:Ivmsjax为vj的电压稳定指标安全上限;z为线路 (vi,vj)的阻抗模值。

该优化问题完全可以用遗传算法解决[16]。对于单个电源接入问题,显然只形成一个孤岛H1,孤岛内只含一个电源DG1,该电源最大出力为P1和Q1。在潮流计算中,电源的节点类型根据不同能源形式作不同抽象:储能电池可以看做恒电流节点(I节点),燃料电池、燃气轮机可以看做PV节点,小型发电机看做PQ节点。潮流计算中对于PV节点的处理可参考文献[17]进行。

当上述优化问题无解时,表示任意接入点都不能满足所有的约束,此时采取以下措施后重新计算该优化问题:当有功功率约束、潮流约束或稳定约束不满足时,采取减负荷措施;当无功功率约束不满足时,采用在接入点接入电容器,投切无功补偿装置或减负荷的方式解决;当电压约束不满足时,通过电源调压处理电压越限,若仍不能解决,投切无功补偿装置或执行减负荷措施调节。

本节例子的孤岛经检验不满足功率约束,实行减负荷操 作,节点15的可控负 荷 (商业 )减载1.5 MW后,孤岛安全,形成应急 电力孤岛 如图4所示。

6 多台移动应急电源车联合应急接入点的 搜索策略及应急方案生成

现代城市一般配备多辆移动应急电源车,多车联合应急时,可以多电源同时供应一个孤岛,也可以单独供应各自的孤岛,也可以将两种模式混合运行, 而形成多少个孤岛由使用哪种容量组合决定,每种容量组合称之为一种运行方式。当车辆规格和数量确定后,运行方式的种类也确定了。例如,有应急电源车3台,容量分别为100,50,50kW,则有4种运行方式:1200kW供应一个 孤岛;2150kW和50kW分别供应一个孤岛;3100kW和100kW分别供应一个孤岛;4100,50,50kW分别供应一个孤岛。

多台电源车应急与单台电源车应急不同的是, 首先要确定形成多少个孤岛(运行方式)及这些孤岛的形成范围是哪些节点,其次要确定每个孤岛内多个电源(如果该孤岛有多个电源接入)接入点的优化。

本文的方法是,首先枚举所有可能的电源容量组合;然后对每种运行方式,依次按照电源容量总和从大到小排列,依次选取每个孤岛的最优接入点,并排除不同孤岛重合的情况;其次,利用5.2节的多约束优化模型,对每个孤岛进行岛内电源接入点的优化;最后,以重要度总和评价运行方式的优劣,选出最优运行方式和接入点方案。多台移动应急电源联合应急方案生成流程可参见附录A图A3。

7 算例分析

本文采用美国PG&E69节点配电网系统作为分析对象,如图5所示,该系统原始参数可参见文献[18],经本文模 型换算后 参数可参 见附录A表A1。负荷的优先级和可控类型如表3所示。由于该标准电网无用户失负荷损失参数,此处以负荷优先级代替。1,2,3类负荷权值分别取100,10,1。 全网停电后,移动应急电源进行应急供电。

设该配电网配置有3台移动应急电源车,容量分别为125,75,75kW,如第6节中分析,共有4种运行方式,下面利用附录A图A3所示流程搜索最优接入点及计算最优孤岛范围,图6绘出了4种运行方式供电组合中最优的一个,其余方式见附录A图A4至图A6。图6中:空心节点表示可控负荷断开,未选入孤岛,但馈线仍被充电。

为了比较,表4列出了4种运行方式的恢复负荷总量(指标1)、恢复重要负荷比重(指标2)和最重要的指标———应急孤岛的重要度总和(指标3)。

根据指标3的重要度排序,运行方式最优者为方式2,最差为方式1,方式2的恢复负荷总量和恢复重要负荷比重都超过了其他方式,其原因在于方式2的供电组合能同时满足以节点12和9这一类负荷为中心的 高优先级 负荷群;而方式1在给节点12的负荷群供电后,无法同时给节点9的一类负荷群进行供电。同时可以看到,重要度指标高的方案,其余指标也高,说明重要度指标确能有效反映应急方案的优劣。

8 结语

从最大程度减小失电经济损失的角度,本文提出了:1基于图论的最优孤岛搜索算法;2单台移动应急电源接入点最优搜索及岛内电源接入点多约束优化模型;3多台移动应急电源联合供电最优方案的制订。其中,第2点和第3点建立在第1点的基础上,得到满足工程要求的移动应急电源最优接入点和供电孤岛方案。算例的结果表明,接入点不同将对应急方案的优劣产生很大影响,利用本文提出的方法,可以最大程度地发挥有限的移动应急电力资源的作用,保证重要负荷的经济损失降到最低。

附录见本 刊网络版 (http://www.aeps-info. com/aeps/ch/index.aspx)。

摘要：在城市配电网发生大面积停电时,移动应急电源为重要用户提供孤岛应急电力资源。在配电网图模型的基础上,提出将孤岛划分问题转化为祖先约束背包问题,利用图论的精确递归法解决。首先深入研究了最优接入点的优化:通过在配电网每个节点形成孤岛,获得每个节点对应恢复负荷的失负荷价值总和。然后以此为目标,搜索到单台移动应急电源最优接入点,并利用多约束优化解决岛内电源接入点搜索问题。最后,在单台移动应急电源最优接入点搜索方法的基础上,给出了多台移动应急电源联合应急的方案制定方法,算例结果证明了该方法能最大程度地利用移动应急电力资源减小重要用户的经济损失。

关键词：移动应急电源,配电网恢复,孤岛划分,图论,精确递归

最优孤岛划分 篇2

关键词：配电系统,分布式电源,孤岛划分,供电可靠性

0 引言

分布式电源（distributed generator,DG）以其独有的环保性和经济性成为提高能源综合利用效率的有效途径[1,2]。同时，DG可灵活地并网或者孤岛运行，迅速恢复受故障影响的重要负荷供电，提高配电网的供电可靠性[3,4,5]。为此，IEEE编制了IEEE1547—2003标准鼓励供电方和用户通过技术手段实现孤岛运行[6]。孤岛运行是配电网在接入DG后一种新的运行方式，由DG独立地向系统的部分负荷供电。在系统发生故障时，各DG按照划分好的孤岛继续向负荷供电直至故障排除，系统恢复供电[7]。

国内外众多专家都对如何合理地划分孤岛进行了深入研究。文献[8]提出了利用DG和负荷的状态实现自适应孤岛运行的整体思路。文献[9]将以不同DG为中心划分的相邻孤岛进行融合，解决了功率圆相交的问题。文献[10]采用改进Prim算法对配电网进行孤岛划分，但该方法要求孤岛范围尽可能大，故网损较重。文献[11]建立孤岛划分的树背包问题模型，利用分支定界算法求解。文献[12]采用改进Kruskal算法对含DG的配电网进行孤岛划分。上述文献都对提高电力系统供电可靠性起到积极的作用，但仍需考虑以下几个方面。

1）文献[8,9,10,11,12]由于采用的是不完全解析性的建模方式，因此都使用了搜索的方法对配电网孤岛划分问题进行求解，得到的结果还需进一步校验和修正，如检验功率平衡是否得到满足、检验孤岛中有无线路过载、剔除孤岛中的某些支路等。因此，不同的处理方法可能会形成不同的解，得到的孤岛不一定是唯一最优的。

2）分布式发电技术多种多样，常见的有光伏发电、风力发电、生物质发电、燃料电池等。但并不是所有的DG均适合单独对某一区域进行供电，如风力发电[13]，其输出的功率有较强的随机性且很难进行调节，影响所在孤岛的可靠运行。

综上所述，本文根据DG和配电网的运行特点[14,15]，建立了不同可靠性类型DG联合供电的表达式；根据电力负荷的等级和可控性，建立了优先恢复一、二级负荷的智能配电网孤岛划分数学模型，并采用数学优化方法进行求解。

1 含不同类型DG的孤岛划分原则

DG须具备以下条件才能单独供电，称之为可靠性DG:(1)电源输出的功率稳定且大小可以调节；(2)有综合控制策略来维持该区域的电压和频率的稳定；(3)具备一定的通信能力，在其单独对某一区域进行供电时，采集点将系统实时的电压、频率和负荷变化等信息传回DG,DG根据这些信息采用相应的控制策略，维持该区域电压和频率的稳定。

可靠性DG主要包括燃料电池、微型燃气轮机、配置储能装置的风能发电及光伏发电等。

一般的风能发电及光伏发电，由于其出力波动极大且很难进行调节，为非可靠性DG，需与可靠性DG一起对一个负荷区域联合供电。

因此，含DG的配电网在进行孤岛划分时需考虑以下几个原则。

1）重要负荷优先供给原则。在系统发生故障时，重要负荷优先得到供电恢复。因此，在孤岛划分时应首先将一、二级负荷划入孤岛内。

2）最大负荷原则。在满足岛内总负荷不超过DG发电容量的前提下，为提高系统的供电可靠性，减少负荷失电量，充分发挥DG的作用，应将尽可能多的负荷并入孤岛内。

3）孤岛备用原则。当DG孤岛运行时，由于没有大网作为依托对岛内的频率和电压进行调节，因此需要部分机组具备一定的调节能力以应对可能出现的削峰填谷、平滑功率、调峰调频等情况。

4）联合供电原则。根据DG单独供电的要求，需要避免出现非可靠的DG独自供给区域负荷的情况，使划分后的每个孤岛都能安全可靠的运行。

2 配电网孤岛划分模型

孤岛运行作为一种提高供电可靠性的重要方式，得到了人们越来越多的关注。通过选取合理的孤岛范围，与重合闸等自动控制措施相结合，可以实现DG并网模式和孤岛模式间的无缝转换，从而在最大程度上提高DG的利用率，改善供电可靠性。

2.1 目标函数

本文的目标函数为在满足各类安全约束的基础上达到总供电收益最大量Pload，实现最大负荷原则；除一级负荷需要100%恢复外，二级负荷通过调整权值的大小实现优先供给，三级负荷在满足一、二级负荷优先供给的基础上尽可能多的恢复。

式中：dv1i,dv2i,dv3i,dv4i,dv5i分别为一级负荷、二级不可控负荷、二级可控负荷、三级不可控负荷以及三级可控负荷的有功负载；n,m,r,p,q分别为系统中这5种不同负荷的数量；kv2i为0-1变量，0表示该节点的二级不可控负荷不接入孤岛，1表示该节点的二级不可控负荷接入孤岛，二级负荷的供电系统应尽量做到发生故障时不致中断供电，或中断供电后能迅速恢复；wv3i的取值可在0到1之间变化，表示该二级负荷节点为可控节点，负荷接入量可控；lv4i为0-1变量，表示三级负荷节点为不可控节点，即此类负荷节点只存在两种情况，全部接入孤岛或负荷全部切除；zv5i的取值可在0到1之间变化，表示该三级负荷节点为可控节点，负荷接入量可控；α1和α2分别为二级不可控负荷和二级可控负荷的优先供给权值，通常情况下的取值均大于1，以体现二级负荷比三级负荷的优先性。

2.2 约束条件

2.2.1 节点功率平衡约束

被选入孤岛的点都应与电源点连通，即孤岛内的每个节点都满足基尔霍夫定律。

式中：Ωb为系统节点集合；Ωl为系统支路集合；f(i,j）为节点i和节点j之间的有功传输功率；gi为DG节点的有功出力，包括非可靠DG和可靠性DG;di为负荷节点i的有功负载，其中包含n个一级负荷、m+r个二级负荷以及p+q个三级负荷。

2.2.2 机组出力约束

1）非可靠性DG出力约束

由于非可靠性DG的输出功率有较强的随机性且很难进行调节，因此需要与可靠且有调节能力的DG联合供电。

式中：Ωdg为系统DG集合；ΩNSdg为非可靠性DG集合；gNSi为第i台非可靠性DG的接入功率。

2）可靠且有调节能力的DG出力约束

当DG孤岛运行时，由于没有大网作为依托对岛内的频率和电压进行调节，因此需要部分机组具备一定的调节能力以应对可能出现的削峰填谷、平滑功率、调峰调频等情况。如带有通信和控制策略的燃料电池系统、微型燃气轮机等。此时该类DG输出功率的约束为：

式中：Ωbdg为系统可靠且有调节能力的DG集合；为该类DG的最大出力。考虑到系统的安全因素系统需预留的备用，其大小可根据具体情况而定，β在0至1之间取值。

2.2.3 负荷约束

电力负荷对供电可靠性的要求及中断供电在对人身安全、经济损失上所造成的影响程度进行分级[16]。

1）一级负荷

此类负荷中断供电将造成人身伤害、经济重大损失或影响重要单位正常工作等情况，因此该类负荷在配电网发生故障时应100%恢复供电，使各项损失降低到最小。一级负荷的供电约束为：

式中：Ωv1为该配电网一级负荷的集合。

2）二级不可控负荷

此类负荷中断供电将在经济上造成较大损失或影响较重要单位正常工作等情况，虽然该类负荷重要程度不及一级负荷，但停电也会给经济和生活带来不小的影响，因此在目标函数中引入权值α1和α2，使得二级负荷的供电优先级大于三级负荷。二级不可控负荷的供电约束为：

式中：Ωv2为该配电网二级不可控负荷的集合。当DG剩余功率无法满足某个二级不可控负荷节点时，kv2i=0；当DG剩余功率能够满足某个二级不可控负荷节点时，kv2i=1。

3）二级可控负荷

该类负荷的供电要求与不可控的二级负荷一致。其供电约束为：

式中：Ωv3为该配电网二级可控负荷集合。当DG剩余功率无法满足某个二级可控负荷节点时，wv3i=0；当DG剩余功率能够满足该节点部分负荷时，wv3i取0到1之间的数；当DG剩余功率能够满足该二级可控负荷节点时，wv3i=1。

4）三级不可控负荷

不属于一级和二级负荷者为三级负荷。三级负荷的供电优先级为最低。三级不可控负荷的供电约束为：

式中：Ωv4为该配电网三级不可控负荷的集合。当DG剩余功率无法满足某个三级不可控负荷节点时，lv4i=0；当DG剩余功率能够满足某个三级不可控负荷节点时，lv4i=1。

5）三级可控负荷

三级可控负荷的供电约束为：

di=zv5idv5i,i∈Ωb∩Ωv5(9）式中：Ωv5为该配电网三级可控负荷集合。当DG剩余功率无法满足某个三级可控负荷节点时，zv5i=0；当DG剩余功率能够满足该节点部分负荷时，zv5i取0到1之间的数；当DG剩余功率能够满足该三级可控负荷节点时，zv5i=1。

2.2.4 线路功率约束

在电力系统实际运行中，若要切除某一点的负荷，通常情况下会断开该负荷点两侧的线路开关。因此，在孤岛划分中，如果某一负荷点没有接入孤岛内，应断开其两侧的连接线路：

式中：为支路（i,j）传输的最大功率。xi的取值与kv2i,wv3i,lv4i,zv5i有关，当负荷节点所有负荷均被切除时，则xi=0；当负荷节点所有负荷均接入孤岛内时，则xi=1；当可控负荷点接入部分负荷时，则xi=1。

2.2.5 非可靠机组联合供电约束

对于风电、太阳能等DG其出力不够稳定，难以独立供电，需要与具备一定调节能力的机组一起对一个负荷区域联合供电。要保证非可靠的DG与具备一定调节能力的DG联合供电，即要求包含这两类DG节点是连通。首先在式（2）的基础上叠加一个与原网络结构相同的虚拟网络，并在每个非可靠的DG处添加虚拟负荷Ki，假设该虚拟负荷是由具备一定调节能力的DG供给，其虚拟出力为Gi，如此保证每个非可靠性DG的虚拟负荷均由可靠且有调节能力的DG供给，保持这两类机组间的连通性。虚拟网络中传输的功率为kij。最后构建如式（12）所示虚拟网络功率平衡约束，每个非可靠性的DG都会与可靠的DG相连，虽然这一约束增加了变量的规模，但这些变量都是连续变量。

式中：Gi为具备一定调节能力机组的虚拟出力；kij为流过虚拟支路（i,j）的虚拟功率；Ki为虚拟负荷，若Ki=ε，则认为i节点有非可靠的DG接入，反之若Ki=0，则节点i为具备一定调节能力的DG接入点或一般负荷节点；nNSdg为系统中非可靠DG个数；ε为大于0的常数。

3 算例分析

本文对上述模型采用C++编程，调用CPLEX12.5[17]求解。CPLEX求解器能够处理线性规划、二次规划、二次约束规划、混合整数规划等四类基本问题，其在求解混合整数线性规划模型时拥有非常出色的性能，通常采用分支—割平面法，并融合了预处理技术。硬件环境：Intel(R)Core(TM)i3CPU3.2GHz,4GB RAM；软件环境：Windows 7。

3.1 算例1

1）系统参数

69节点系统是美国PG&E的配电网，其有功负荷为3 802.19kW。参照文献[11]在该系统中引入DG，线路（2,3）由于发生三相短路接地故障，其下游节点全部失电，如图1所示。DG1至DG6最大输出功率见附录A表A1，且均为可靠有调节能力的DG，在图中以绿色标示出。本算例中并没有考虑机组的备用，验证本文所提模型在设定系统条件下最大负荷恢复量。负荷的优先级和可控类型见附录A表A2和表A3。

2）结果分析

利用本文所建立的模型对系统内失电节点进行孤岛划分。当优先供给权值α1，α2≥2时，得到如图2所示的孤岛方案，DG点的实际出力如表1所示，除节点32的DG输出功率为39.5kW外，其余机组的出力均处于最大值。总的负荷恢复量为2 139.5kW，一级负荷为410.95kW，二级负荷为1 659.05kW，三级负荷为69.5kW，各类负荷恢复百分比如表2所示。可控负荷节点的恢复量如表3所示，其他未列出的可控节点负荷恢复量为0，由于权值α1，α2的存在，并没有对三级可控负荷进行恢复。

当优先供给权值α1=α2=1时，孤岛划分方案如图3所示，总的负荷恢复量为2 140kW，一级负荷为410.95kW，二级负荷为1 513.15kW，三级负荷为215.9kW，各类负荷恢复百分比如表4所示。由表1和表4对比可知，当权值α1=α2=1时，二、三级负荷间不会出现选择性，三级负荷恢复百分比增大。

文献[11]所采用的孤岛分析策略对图1系统进行孤岛划分，得到如图4所示的孤岛方案。

为比较，文献[11]还分别采用文献[9]的方法对图1系统进行孤岛划分。上述3种孤岛方案恢复负荷总量和恢复重要负荷比重如表5所示。可知，文献[11]虽然在得到初始孤岛方案后进行了校验和调节，但负荷的恢复总数仍没达到最大值。文献[9]算法恢复负荷总量和重要负荷比重都不理想，其原因在于该算法对相邻且相同优先级负荷点的选择不加比较，导致一些不可控负荷节点，无法得到供电。

3.2 算例2

1）系统参数

在算例1的系统条件下引入DG7至DG10，新的系统图如图5所示，可靠且有调节能力的DG以绿色标示出，非可靠DG以红色标示出，该系统内所有机组的类型和最大出力见附录A表A4。优先供给权值取α1，α2≥2的情况。与算例1相比，对于可靠且有调节能力的DG，如DG2,DG3,DG4,DG7，需预留30%的备用。另外，算例中还加入了非可靠机组，验证非可靠机组联合供电约束的有效性。

2）结果分析

利用本文所建立的模型对系统内失电节点进行孤岛划分，得到如图6所示的孤岛方案。

算例2的负荷恢复情况如表6所示。由表6可知，该方案总的负荷恢复量为2 126kW，其中一级负荷为410.95kW，恢复率为100.00%，二级负荷为1 521.42kW，三级负荷为193.63kW。可控负荷节点的恢复量如表7所示，其他未列出的可控节点负荷恢复量为0。

由图6可知，划分的结果形成两个孤岛：(1)DG3和DG8为一个孤岛，DG3是可靠且有调节能力的DG;(2)DG1,DG2,DG4,DG5,DG6,DG7,DG9和DG10为一个孤岛，其中DG2,DG4,DG7是可靠且有调节能力的DG，由划分的结果得到，每个孤岛内均有可靠且有调节能力的DG，避免了非可靠DG单独供电的情况，实现可靠且有调节能力的DG与非可靠机组联合供电的原则。DG实际出力如表8所示。由表8可知，可靠电源DG2,DG3,DG4和DG7均预留了30%以上的备用，提高了各个孤岛实际运行时的可靠性，实现孤岛备用原则。

4 结论

随着DG不断深入的研究和发展，使得孤岛运行在电力系统中的大规模应用成为可能。本文根据DG的供电特性和配电网孤岛运行的特点，提出了考虑多种因素的智能配电网孤岛划分模型，得出的结论如下。

1）由算例1和算例2的结果分析表明，本文提出的模型采用解析性表达是合理有效的，实现了最大程度上解的最优性。

2）在包含6台可靠有调节能力DG的IEEE 69节点系统中，在保证一级负荷100.00%恢复的前提下，系统总的负荷恢复量增加，结果合理。

3）在包含4台可靠有调节能力DG和6台非可靠性DG的IEEE 69节点系统中，可靠性DG和非可靠性DG联合对某一区域供电，此外，可靠有调节能力DG还预留了一定的备用，提高各孤岛运行的可靠性。

4）本文采用数学优化的方法求解孤岛划分问题，在改进的IEEE 69节点系统的仿真结果验证了本文提出模型的有效性。

最优孤岛划分 篇3

随着互联网以及云计算技术的发展,越来越多的Web服务出现在互联网以及云计算平台上。Web服务是可以跨越整个Web被发布、定位以及调用的自包含、自描述的模块化应用。如何有效地组合分布于Internet中的各类Web服务,实现服务之间的无缝集成,形成功能丰富的企业级服务流程,已经成为Web服务发展过程中的一个重要步骤。Web服务组合的研究正是在这种背景下被提出来,并吸引了学术界和工业界的广泛关注。Web服务组合作为一种应用模式,可以在保证Web服务的质量和服务独立性以及满足用户约束的前提下,发现一组服务并将其组合成一个新的、功能更加复杂的服务[1]。

Web服务组合是针对Web服务进行资源管理与整合的重要技术和手段。然而,随着Web服务的迅速增长,通过逐一匹配请求服务的单个抽象功能来进行服务组合的方式对Web服务的利用率变得越来越低。互联网环境千差万别,不同的Web服务正常运行的环境也不一样,在服务选择阶段,仅仅通过运行成功率这一统计性标量已不足以选择到真实环境下高可靠性的服务。实现Web服务的无缝组合和提高服务的可靠性、扩展性已成为当今Web服务组合研究领域的热点问题[2,3]。

本文在Web服务组合方式规划上将针对组合方式的多样性和无缝性问题,提出一种基于请求服务功能划分图的动态Web服务组合方法。在组合服务的选择上将针对服务的可靠性问题,提出带约束上下文的局部最优选择算法和全局最优选择算法。目前云平台上的Web服务既有独立的集成软件,也有适用于工业流程的组件,本文提出的算法对这两类应用场景都适用。

1 相关工作

目前对Web服务组合技术的研究可以分为两类:基于工作流的服务组合和基于人工智能规划的服务组合[4]。例如,文献[5-9]介绍了基于工作流图的动态服务组合和选择算法,其思想是根据流程图逐步选择最优的服务,将最优服务组合和选择问题转换为求最优路径问题。文献[1]介绍了基于人工智能的服务组合优化方法,通过统计特征来把握候选服务的全局特性,使用遗传算法求出最优解。随着互联网以及云计算技术的发展,越来越多的Web服务出现在互联网上,只逐个匹配请求服务的各个抽象功能来确定候选服务,并从中选择和组合出Web服务已经不能满足当前的需要了。为扩展Web服务组合的方式,很多学者都把目标放在扩大候选服务类型集上,文献[2]提出了服务内扩展和服务外扩展方法,文献[10]采用聚类技术和结构化服务发现相结合的方法来为Web服务归类,文献[11]采用计算流程相似度来查找所需候选服务。服务类型集的扩大必然引起组合方式的多样性,在最优服务组合选取上,文献[3]采用嵌套组合的方法,文献[12]则提出了基于相似度的模糊预测的方法,文献[13]和文献[14]也各提出一种模型来力求最大限度找到能组合出满足用户需求的候选服务并将它们装配起来。但是,这些方法都不能完整表现出服务间的关系。因此,对于包含多个请求服务的抽象功能的候选服务,其服务组合方式也就不确定,从而产生了无缝组合问题。Web服务的无缝组合就是如何完整和正确地将候选服务装配成满足请求服务要求的服务组合。

Web服务千差万别,其对运行环境的要求也各有不同,Web服务组合面临多样性的问题。文献[2]提出了服务约束-感知机制来确保Web服务在正确的环境中运行,但是文献[2]在初始化及预包装上没有提出相应的算法,而且深度优先的图算法的复杂度很高。文献[15]提出了用上下文来表述服务特殊要求的方法,其思想是后退一步来查验当前选择的服务是否是最优的,是则继续到下一步,否则在退后一步的前提下选择最优。然而这个算法只适用于功能呈顺序关系,不能满足请求服务的功能间呈非顺序关系的情况。

本文提出的Web服务组合和选择方法分为两个阶段:(1)基于请求服务的功能划分图来计算出所有可用于服务组合的候选服务类型,同时通过精确匹配来确定出各个类型的候选服务集,并规划出各种服务类型组合方式;(2)查找各个组合方式下的最优服务组合,比较产生最优的服务组合。考虑到各个Web服务会受环境的影响,本文采用上下文结构来表述每个具体Web服务或服务组合自身对运行环境的要求和自身具有的优先条件,并提出基于这种上下文的局部最优选择算法和全局最优选择算法来找出高可执行性的最优服务组合。

2 Web服务组合方式规划

目前,在Web服务的识别上有基于输入和输出参数的[4],还有基于功能语义描述的[2],本文采用解析请求服务的输入和输出参数来确定单个服务的类别。对于用户的请求服务,如何抽象出其包含的各个功能和它们之间的关系,以及每个功能对应的参数,目前已有很多研究。本文将在确定出请求服务的各个抽象功能、各个抽象功能的输入和输出参数以及请求服务的功能划分图的基础上,进行Web服务组合的研究。

服务不仅具有功能特性,还有输入、输出参数的差别[9]。本文采用分级思想,对于在功能及相应功能的输入、输出参数上都完全或部分符合请求的服务采用第一级服务组合;对于在功能上满足请求服务的某个功能,但是在输入、输出参数上却不满足相应要求的服务采用第二级服务组合。本文重点研究第一级服务组合。

2.1 基本概念

为便于理解Web服务的组合方式,首先介绍本文定义的几个基本概念。

定义1请求服务的功能关系:指请求服务的各个功能间的行为关系和数据关系。

一般,功能间的行为关系分为顺序关系和并行关系两种,且呈顺序关系的两个功能才可能有数据关系。本文通过匹配输入参数和输出参数来抽象各个功能,而各个参数又反映了功能间的数据关系。因此,也可以通过匹配输入和输出参数来确定出整个功能间的关系。

定义2请求服务的功能划分图:指反映请求服务的各个抽象功能及各个抽象功能间关系的图,图有两个虚拟节点表示开始与结束,其他节点表示请求服务的抽象功能,抽象功能节点间的边表示抽象功能间的功能关系。

定义3第一级服务:指一个Web服务能满足一个或多个Web请求服务的抽象功能,这些抽象功能间的关系必须与请求服务的功能关系一致。同时其输入参数和输出参数也满足请求服务在这些功能上的参数约束。

定义4第二级服务:指一个Web服务能满足某一个请求服务的抽象功能,但其输入参数和输出参数无法满足请求服务在这个功能上的参数约束。第二级服务只涉及一个请求服务的抽象功能,所以没有功能关系的限制。

匹配技术、分类技术和装配技术是形成Web服务组合的三项关键技术[16]。匹配Web服务的过程也是搜索候选Web服务的过程,为了匹配出上述所提到的第一级服务,可以在匹配Web服务的过程中,将Web服务分为完全匹配服务、部分匹配服务、约束不匹配服务和完全不匹配服务。

定义5完全匹配服务:指一个服务的输入参数类型满足请求服务的所有输入参数类型,且服务的输出参数类型也满足请求服务的所有输出参数类型。同时,这个服务的输入参数和输出参数在取值上满足请求服务的约束。

定义6部分匹配服务:指一个服务的输入参数和输出参数在类型上分别部分匹配请求服务的输入参数和输出参数,且这些匹配的输入参数与输出参数在取值上也与请求服务的相应参数一致。

定义7约束不匹配服务:指一个服务的输入参数类型和输出参数类型都完全或部分出现在请求服务的输入参数和输出参数中,但是它们不都满足其对应的参数约束。

定义8完全不匹配服务:指不满足上述三类中任意一类的服务。

完全匹配服务和部分匹配服务归为第一级服务,用于后续的服务组合和选择技术,至于完全不匹配服务则直接舍弃。

2.2 服务组合规划

规划服务组合分为3个阶段:

构造请求服务的功能划分图;

匹配、分类第一级服务,产生第一级服务类型;

装配第一级服务类型,产生抽象服务类型组合。

1)构造功能划分图

将整个请求服务中的各个功能看作一个节点,先设定两个虚拟节点,即开始节点和终结节点,之后将这些节点初始化为一个有向图,这里称其为请求服务的功能划分图。

定义深度为功能划分图的最大路径长度,宽度为功能划分图中所有功能节点的最大直接后继服务节点数量。功能划分图的构造方法如下:

(1)功能节点依照功能间的行为关系进行连接,若两个功能之间的行为关系是并行或不相邻的先后关系,则它们不需要连接;若它们的行为关系为顺序且相邻,则依照它们的先后顺序用有向边连接。

(2)开始节点用有向边指向所有无前驱的节点,所有无后继节点指向终结节点。

2)匹配、分类第一级服务

这一阶段的目的是搜索符合要求的第一级服务并将它们分类,由此产生各个第一级服务类型。为便于理解,对第一级服务类型作如下定义:

定义9第一级服务类型:第一级服务经第一级组合的分类阶段产生的抽象服务类型。

根据初始化后的功能划分图,标记图中的各分支和各抽象服务相对于各个分支所在的位置,并确定各分支间的隶属关系。之后,通过将各个服务与这个有向图对比来对服务进行分类。

已知第一级服务都能部分产生目标输出,且它们对应的节点之间有关联表示后者节点的输入依赖前者节点的输出,可得出以下推论:

推论1对于一个抽象服务功能,当其输入不能完全由一个第三方提供的服务决定时,则这个第三方提供的服务一定不包括这个抽象服务功能。

推论2一个无输入依赖的抽象服务功能,其前驱节点一定是开始节点。

推论3一个第三方提供的服务如果包含两个或多个在不同分支但它们的分支却隶属于同一分支A的抽象服务功能,记这两个或多个抽象服务功能所在的分支为B类分支,则这个第三方提供的服务必然包含分支A上的服务功能及其在B类分支上的直接后继抽象服务功能。

推论4一个第三方提供的服务所涉及到的抽象服务功能中,如果有其所在分支隶属于同一个分支的,则它们在请求服务功能划分图中的位置必是连续的。

将请求服务的功能划分图的开始节点留下,终结节点删去。根据上述4个推论可知,每个第一级服务类型对应到请求服务功能划分图中就是一个树,因此,每个第一级服务类型都可以由一个树结构来表示。

3)第一级服务类型装配算法

第一级服务类型对应的装配算法简称第一级装配算法。其具体过程分为两阶段:分层阶段和装配阶段。

已知第一级服务类型的表示是一个树结构,本文根据各个第一级服务类型表示树的根节点来分层,即第一级服务类型所属的层数就是其表示树的根节点在请求服务功能划分图中的层数。

计算请求服务功能划分图中,求各个抽象服务节点的层数的方法如下:先求出请求服务功能划分图中从开始节点到终结节点的所有路径;接着,计算各个路径上的抽象服务在这个路径上的位置,设定开始节点的位置为0,其直接后继节点的位置为1,就这样依次加1得到各个路径上的各个抽象服务的位置;最后,对于每个抽象服务,取在经过自己的所有路径上的最大位置数作为自己的层数。

装配阶段就是依次对第0层的各个服务类型进行装配来得到它们的所有服务类型组合方式,进而得到请求服务所对应的所有服务类型组合方式,具体算法流程见图1所示。

图1 第一级装配算法流程图

(1)初始化队列Queue:设Queue为一个先进先出队列,将属于0层的所有Web服务类型都封装为Web服务类型组合并依次放入Queue中。

(2)装配一个缺少的服务类型:按层次数从小到大来找到服务类型组合A所需的第一个服务类型,并将这个服务类型装配到A上。

3 最优Web服务组合选择算法

Web服务组合选择阶段则是根据请求服务的服务质量、客户偏好等非功能属性,选择出最优的、真实的服务组合。文献[17]提出了服务质量标准和相应的计算公式,探讨了对于确定的Web服务类型组合方式,求其最优服务组合解的方法。本文将Web服务组合的非功能属性分为完全依赖属性和部分依赖属性,用多领域决策来产生集成函数,通过集成函数的权值来表现请求服务的非功能性属性。最优Web服务组合选择算法就是选择出分数最高的服务组合的算法。

定义10完全依赖属性:由Web服务组合中的所有Web服务计算得到的属性,即服务组合在此属性上的值是所有Web服务在此属性上的值运算得到的。

定义11部分依赖属性:由Web服务组合中的部分Web服务计算得到的属性,即服务组合在此属性上的值是通过某种规则选出部分Web服务,由它们在这个属性上的值经过运算得到的。

从定义10和定义11可知,例如花费就是完全依赖属性,消耗的时间就为部分依赖属性。本文采用整数规划的思想,将所有非功能性属性的计算公式都转化为和的形式。这样,整个服务组合的分数就是整个服务组合在各个非功能属性项上的值乘以相应的权值之后将这些项进行累加。当Web服务或Web服务组合在这些属性上的值是相互独立时,对于完全依赖属性,其在整个Web服务组合上的值为这个Web服务组合所包含的所有Web服务在这个属性上的值的和;对于部分依赖属性,求解其在整个Web服务组合上的值实质上是一个关键路径问题,只不过具体问题依属性而不同。

由定义10、定义11知,完全依赖属性和部分依赖属性是没有逻辑联系的,而在部分依赖属性上选择出最优服务须得形成所有服务组合,这样问题就转换成图的最优路径选择问题。由文献[5]知,这是一个NP-hard问题,因此本文采取只根据完全依赖属性选择最优服务组合,在计算分数时会考虑整体的属性分数。

对于完全依赖属性,求解其在整个Web服务组合上的最优解问题实际上是个贪心问题,用贪心算法得到的最优完全依赖属性解在现实环境中并不保证一定能运行。另外,不是所有Web服务或服务组合在这些属性上的取值都是独立的,Web服务或服务组合间可能有优先条件,所以本文采用上下文来表示Web服务或服务组合在这些属性上的关联和它们自身对运行环境的要求。在3.1节和3.2节将介绍结合上下文来求解最优完全依赖属性服务组合的局部最优算法和全局最优算法。

3.1 带约束上下文的局部最优选择算法

一般来说,一个Web服务的自身运行限制是与其前驱服务相关的,而其与其相邻服务的优先条件也可以表示为受其前驱服务的限制。因此,每个Web服务的约束上下文都可以表示为对其后继服务有限制。

带约束上下文的局部最优算法的实质就是逐层地找出满足上一层选出服务的约束条件的本层最优服务组合。考虑到会有没有后继服务的服务被选中而造成“无解”的情况,这里引入失败回退机制,具体算法过程如下:

1)初始化:初始化这个服务类型组合方式中的各个服务类型的层次关系,设第0层的前驱层的最优子结构为null且没有对后继的约束。最后,设当前层为第1层。

2)选择出满足前驱层的当前层最优服务组合,如果没有,则更新服务状态并回退至前驱层;如果存在则进入第3)步。

3)判断当前层是否为最后一层,是则退出算法;否则设下一层为当前层,接着执行第2)步。

3.2 带约束上下文的全局最优选择算法

带约束上下文的全局最优算法结合了动态规划思想和上述的局部最优算法,因此也带有失败回退的机制,具体算法过程如下:

1)初始化:与局部最优算法的初始化过程一样。

2)计算当前层的局部最优解。

3)将上步得出的结果与第0层到当前层的前驱层筛选出的全局最优服务作对比,若完全一样则进入第4)步,否则进入第5)步。

4)筛选出只在当前层上,比第2)步选出的当前层服务组合更优秀的服务组合,并依次找出包含这些服务组合的从0层到当前层的最优子结构;之后通过对比这些解找出0层到当前层的最优子结构,接着进入第6)步。

5)找到开始出现变化的层数,更新服务状态,设开始出现变化的层为当前层,进入第2)步。

6)判断当前层是否为最后一层,是则退出算法;否则记下一层为当前层,重新进入第2)步。

4 实验及性能分析

4.1 实验环境

为验证上述算法的性能,本文进行了仿真实验。仿真实验采用的开发环境如下:操作系统为Windows7 32位操作系统,算法开发语言为C++,采用Microsoft Visual C++6.0为开发工具。用链表结构存储请求服务功能划分图,用树结构表示第一级服务类别,并为每个服务类别添加一个唯一的标识符。建立Composition类来模拟符合请求服务的单个服务组合,在Composition类中使用一个vector容器类型的成员变量来存储组成这个服务组合的所有服务类型的标识。

对第一级装配算法,分别采用单线程和多线程两种计算方式,以功能划分图的深度和宽度作为标量,以功能数、服务类型数、组合方式数、装配时间等作为服务类型装配算法的性能指标,进行了仿真试验。对选择算法,以最优服务组合的分数和花费时间作为服务组合选择算法的性能指标,进行了仿真实验。

4.2 第一级服务类型装配算法性能分析

为验证第一级装配技术受请求服务功能划分图的影响,深度和宽度是反映请求服务功能划分图的复杂度的两个重要标量。表1给出了宽度为2时功能数、第一级服务类型数、组合方式数、装配时间等指标随深度的变化情况。从表1中可以看出,当深度从1增加到3时,第一级服务类型数量的变化比第一级服务类型组合方式数量的变化明显要大,采用多线程计算方式比单线程计算方式耗费的时间明显要少。

表1 深度对性能指标的影响(宽度为2)

表2给出了深度为2时功能数、第一级服务类型数、组合方式数、装配时间等指标随宽度的变化情况。从表2中可以看出,当宽度从1增加到3时,第一级服务类型数量的变化比第一级服务类型组合方式的数量变化要小,采用多线程计算方式比单线程计算方式耗费的时间要少,但差值不大。

表2 宽度对性能指标的的影响(深度为2)

对比表1和表2可以得出,服务类型数量更易受宽度的影响,而服务类型组合方式数量更易受深度的影响。另外,多线程计算方式更适合装配深度较大的请求服务。

图2是深度为1,宽度从1到10变化时,分别用单线程和多线程计算方式所得的处理时间对比图。从图2中可以看出,宽度达到一定值时,用多线程产生的开销已经远大于装配的开销,使得多线程计算方式在处理效果上还不如单线程。

图2 宽度对计算时间影响图

4.3 局部最优和全局最优选择算法性能分析

这部分实验采用单线程、单机计算方式。为验证Web服务组合选择算法在约束上下文条件下的性能,实验用后继匹配率来表示满足服务约束的后继服务占有情况,即后继匹配率=满足服务的后继服务数量/后继服务的整体数量。设定整个服务组合的满分为100,选择算法负责选择分数最高的服务组合。由表1知,当请求服务功能划分图的深度(路径长度)为2(不包含初始节点)、宽度为2时,最大请求服务的功能数为6,服务类型数为28,服务类型组合方式数为32。图3给出了这种情况下后继匹配率为0.5,每种服务类型的候选服务数量取10~100间的10倍数离散点时,分别用局部最优选择算法和全局最优选择算法所得的服务组合的分数情况。图4给出了对应的局部最优选择算法和全局最优算法所花费的时间情况。从图3和图4可以看出,全局最优算法在效果上略优于局部最优算法,但是其花费的时间要比局部最优选择算法大得多,而且易受候选服务数量的影响。

图3局部最优和全局最优选择算法的分数对比

图4局部最优和全局最优选择算法的花费时间对比

5 结语

本文通过构造请求服务的功能划分图,来计算用于Web服务组合的服务类型并规划出相应的服务类型组合方式。结合后退一步上下文算法以及动态规划思想,将非功能属性分类求解,并通过计算局部最优来缩小计算范围的方法,来简化局部最优和全局最优选择问题的复杂度。最后通过仿真实验,分析了功能划分图对第一级装配算法的影响,以及局部最优选择算法和全局最优选择算法的性能。

摘要：扩展Web服务类型的组合方式、实现服务的无缝组合和提高服务组合的可靠性是当今Web服务组合的研究热点。针对Web服务类型组合方式多样性和无缝服务组合问题,根据请求服务的功能划分图来计算可用于服务组合的候选服务类型,动态规划各种服务类型的组合方式,并提出第一级服务类型的装配算法。针对服务组合的可靠性问题,将Web服务自身对运行环境的要求和自身的优先条件表示为上下文,并提出相应的局部最优选择算法和全局最优选择算法,以找到真实的、具有高可靠性的服务组合。最后,通过仿真实验验证了第一级服务类型装配算法、局部最优和全局最优选择算法的性能。