ISSN 
-45-5-854-1.jpg)
-
各地的电力系统是一个庞大的网络，随着经济、社会的发展，人们对电力的依赖越来越强，电力系统所承受的压力越来越大，电力部门面对大规模停电的威胁也越来越显著，因此“黑启动”[1]方案受各国科研人员的关注度越来越高。所谓黑启动方案，是指整个系统因故障停运后，系统全部停电(不排除孤立小电网仍维持运行)，处于全“黑”状态，不依赖别的网络帮助，通过系统中具有自启动能力的发电机组启动，带动无自启动能力的发电机组，逐渐扩大系统恢复范围，最终实现整个系统的恢复。
电力系统在黑启动过程中分为3个阶段：1) 黑启动阶段；2) 系统重构阶段——主要目的是尽快给失电场站送电并建立一个骨架网络，为下一阶段全面恢复负荷(拥有发电机组的场站在网络中被标记为电源节点，除电源节点外，网络中的其他机组都可被看作是广义的负荷节点)打下基础；3) 负荷恢复阶段。大规模停电后网络重构阶段的主要任务是尽快给失电场站送电，快速恢复失电机组，并建立一个稳定的网架结构。在系统重构过程中要选择电源、负荷和线路的理想组合构成骨架网络。
为实现网络重构，一些学者根据网络中节点和连边的性质构造出了骨架网络，提出了网络恢复策略。文献[2]采用节点收缩后的网络凝聚度定义节点重要度，以网络重构效率(网络节点的平均重要度/网络的聚类系数)作为衡量重构效果的评价指标，提出了基于节点重要度评价的骨架网络重构策略，但未考虑到不同线路的相对重要性。随后，文献[3]在此基础上考虑线路介数，以节点重要度和线路介数作为重构指标，优先将重要节点和关键线路选入重构目标骨架网，从而为整个电网的全面、快速恢复奠定基础。文献[4]基于节点的恢复可靠性确定节点恢复序列，然后优先恢复待恢复节点中可靠性最高的节点，以此来提高系统恢复的成功率。文献[5]研究了节点间的供电关系，提出了一种基于后悔思想的节点重要度评价方法，但该方法在优化恢复路径时仅考虑了对重要节点的恢复。
考虑到实际网络中一些重要节点和连边的优先恢复，本文以链路预测算法为背景，考虑在网络中起重要作用的异常边，提出了基于异常链路分析的骨架网络重构方案。
HTML
-
每个网络都可以抽象成一个由节点集和边集组成的图，在记录网络的过程中，由于信息的不完全性，观测网络中会有链路的缺失问题，如信息的丢失及信息的刻意隐藏问题。
网络中的链路预测就是通过已知的网络节点以及网络结构等信息来预测网络中尚未产生连边的两个节点之间产生连接的可能性。这种预测既包含对未知链接(实际存在但未被探测到的链路)的预测，也包含对未来链接(目前不存在但应该存在或未来很可能存在的链路)的预测。链路预测将网络与信息科学联系起来，处理信息科学中缺失信息的还原和预测。学者们将节点间的相似性，即两节点间存在链接的可能性大小，直接用来进行链路预测。基于局部结构信息的相似性指标有典型的CN[6]、AA[7]、RA[8]等，基于路径的相似性指标有典型的Katz[9]、LP[8, 10]等。衡量链路预测算法精确度的指标[11]主要有AUC、精确度(precision)和排序分(ranking score)，其中AUC[12]是最常用的评价指标，可以从整体上衡量算法的精确度；而排序分[13]更多考虑了所预测边的排序。
上述5种相似性指标的具体定义方法如下：
1) CN指标(common neighbors)：
式中，$\Gamma $表示节点的邻居集。该指标定义网络中两节点间共同邻居的个数为它们之间的相似性。
2) AA指标(adamic-adar)：
式中，${d_z}$表示节点$z$的度。该指标考虑网络中两节点间共同邻居的度的信息，为每个节点赋予一个权重值，思想是度小的共同邻居节点的贡献反而要大于度大的共同邻居节点。
3) RA指标(resource allocation)：
这是文献[8]中提出的资源分配指标，该指标考虑的是未直接相连的两个节点${v_x}$和${v_y}$之间的资源传递过程，其思路是将两节点间的共同邻居作为资源传递的媒介且这个媒介的单位资源平均传送给它的邻居，然后将节点${v_y}$可以接受到的${v_x}$传递的资源数定义为两节点间的相似性。
4) LP指标(local path)：
这是文献[10]在共同邻居基础上考虑三阶路径的因素提出的局部路径相似性指标，其中$\alpha $为可调参数，${\bf{A}}$为网络的邻接矩阵，${({{\bf{A}}^3})_{xy}}$表示节点${v_x}$和${v_y}$之间长度为3的路径数目。
5) Katz指标
将局部路径指标扩展到无穷阶路径就得到全局路径指标：
该指标考虑了网络中的所有路径，$\left| {{\rm{paths}}_{x,y}^{\left\langle l \right\rangle }} \right|$表示连接节点${v_x}$和${v_y}$的路径中长度为$l$的路径数。
-
针对网络中还未连接的节点对，上述链路预测算法(相似性指标)可以用来预测两节点间存在连边的可能性；针对网络中已经存在链接的节点对，如果通过相似性算法计算出这条边的相似度较低，说明它的存在在该网络中起到一定的重要作用。从这个角度上讲，链路预测算法可以用来评价链接存在的可信度或重要性。
所谓异常边[13]就是指网络中真实存在但是通过链路预测方法认为其存在概率很低的边。文献[13]中已有实验证明，异常链路对保持网络的连通性有特别重要的贡献，通过异常链路分析的方法能够有效地识别对网络连通性起重要作用的边。因此可以相信，优先恢复网络中的异常边对网络的恢复过程有重要指导意义。
对于给定网络$G = (V,E)$和一种链路预测算法，通过逐项遍历[13]的方法对网络数据集(边集)进行划分：遍历网络中的每条边构成测试集。对$\forall e \in E$，通过算法可得到该边的相似性${s_e}$在未知边集$H$中的排名，记为${r_e}$，边$e$的排序分[13]定义为：
式中，$H$表示所有未知边的集合，即测试集与不存在边的集合的并集。记$|V| = n$，$|H|$的值可由式(7)求得：
对于异常边，排序分${\rm{R}}{{\rm{S}}_e}$越大表示边越异常，所以可以通过边的排序分来表示它的异常度。对网络$G$，遍历所有在测试集中的边，得到系统的排序分[13]为：
对于某节点$x$，与其相关联的边和它本身构成的系统${G_0}({V_x},{E_x})$的排序分为：
把节点$x$的异常度定义为：
式中，$d$表示节点的度；$\Gamma $表示节点的邻居集合；$(x,z)$表示连接节点$x$和$z$的边，$|H|$由式(7)求得。
对于链路预测算法，系统排序分值越小说明算法的预测效果越好；而对于异常边，排序分值越大说明链路越异常。
1.1. 链路预测
1.2. 异常边
-
电力网络重构的目标是在网络大规模瘫痪的状态下，带电的发电机组以最短的路径对待恢复机组按其异常度确定优先次序进行供电，从而重建系统网架，加速系统恢复进程；然后以链路异常度作为标准依次恢复已恢复机组周围的待恢复线路。
电网具有复杂网络的某些共性，因此可以应用复杂网络中的链路预测方法作为筛选重要节点和关键线路的重构指标，为确定重构网络提供指导。将链路预测算法应用到电力系统的骨架网络重构上，实质是要在大规模停电后通过某种链路预测方法计算实际发电机电源节点的恢复次序并实现网络中所有失电机组的供电，为下一步的路径恢复奠定基础。文献[13]讨论了异常边对网络连通性的影响，指出异常链接分析的方法比边介数的方法更能够有效识别对网络连通性起重要作用的边。因此，通过预测精度较高的链路预测算法得到每条边e的排序分${\rm{R}}{{\rm{S}}_e}$，即异常度，然后计算所有待恢复电源节点的异常度${\rm{R}}{{\rm{S}}_x}$，优先恢复图中异常度较高的电源节点。在电源节点的恢复顺序被确定后，采用改进的Dijkstra算法计算待恢复电源节点到其他带电电源节点的最短路径，由此可得到连通的电源节点骨架图；骨架网络重构完成后，按边的异常度从高到低依次恢复发电机电源周围的路径，从而实现整个网络的恢复。
由于重构过程中涉及诸多的技术性因素以及不确定性因素，在满足运行质量的前提下，依据网络结构进行网络的重构指导。考虑异常边及异常节点对网络的重要性，重构网络中所含异常边及异常节点越多说明重构方法越有效，因此本文定义重构网络效率$\eta $为：
式中，$\eta $越大，重构效率越高；$\bar r$表示重构网络中所有负荷节点的平均异常度；$\bar c$表示重构网络的聚类系数：
式中，$k$为重构网络中包含的负荷节点的数目；$m$为重构网络中的节点数目；${d_j}$为节点$j$在原始网络中的度；${d'_j}$为节点$j$在重构网络中的度。
为达到高效的重构策略，需要以相对较少的线路将所有电源节点和异常度较高的负荷节点联系起来组成骨架网络，进而更好地指导整个网络的恢复过程。
-
1) $G = (V,E)$，$x \in V,e \in E$；
2) 选取预测精度值(排序分)最高的链路预测算法 (LPA)，计算每条边的异常度，进而确定电源节点的优先恢复次序：
BEGIN
FOR i = 1 : 5
计算 RSi ；
END FOR
LPA = LPAi s.t. RSi=min{RS}；
RSe = LPA[train,e]；
计算 RSx；
Ranking(descend) { RS
x }； END
//得到排序后的电源节点
3) 用改进的Dijkstra算法计算最短路径，保证优先、快速地恢复重要节点，得到电源节点构成的重构骨架网络：
BEGIN
FOR i =1 : k (排序后的电源节点标号)
j = 1 : k
path(i,j) = dijkstra(A,i,j);
IF${\rm{path}}(i - 1,i) \le {\rm{path}}(j,i)(i \ge 2,1 \le j \le i - 1)$
THEN ${\rm{pat}}{{\rm{h}}_i} = {\rm{path}}(i - 1,i)$;
END IF
END FOR
END
//得到按依序恢复电源节点的最短路径
4) 将已恢复机组周围的未恢复路线按其异常度从高到低进行恢复。
2.1. 重构思想
2.2. 算法描述
-
为验证本文方法的有效性及具体实现过程，选择IEEE30节点系统(30个节点，41条边)进行测试。排序分作为衡量链路预测算法精确度的指标，系统的排序分值越小说明算法的预测精度越高。而节点和边的排序分，即异常度，揭示了它们的重要性，排序分值越大则表示该节点和连边越异常，说明它们的重要性越大。通过上述理论，本文以IEEE30节点系统图(图 1所示)为例，选取预测精度较高的链路预测算法来实现该系统的骨架重构。其中，衡量链路预测算法精确度的指标为排序分(ranking score)。
-45-5-854-1_mini.jpg)
1) 逐项遍历IEEE30节点系统图中所有连边，将不同链路预测算法在该系统网络中的预测精度值记录在表 1中。
指标 CN AA RA Katz LP 排序分 0.1427 0.1362 0.1352 0.5133 0.2774 由上述表格可知，RA指标得到的系统排序分最小，说明该指标对该系统网络的预测效果较好。
2) 通过RA指标来计算网络中连边的异常度，即排序分值，如表 2所示。然后通过式(10)求得电源节点的异常度，确定所有发电机组的恢复次序。
e RSe e RSe e RSe (1,2) 0.195 (8,28) 0.154 (16,17) 0.195 (1,3) 0.200 (9,10) 0.144 (18,19) 0.195 (2,4) 0.152 (9,11) 0.195 (19,20) 0.195 (2,5) 0.195 (10,17) 0.185 (21,22) 0.122 (2,6) 0.063 (10,20) 0.185 (22,24) 0.190 (3,4) 0.195 (10,21) 0.028 (23,24) 0.192 (4,6) 0.063 (10,22) 0.013 (24,25) 0.190 (4,12) 0.182 (12,13) 0.190 (25,26) 0.195 (5,7) 0.200 (12,14) 0.058 (25,27) 0.187 (6,7) 0.187 (12,15) 0.013 (27,28) 0.187 (6,8) 0.028 (12,16) 0.187 (27,29) 0.013 (6,9) 0.122 (14,15) 0.058 (27,30) 0.013 (6,10) 0.028 (15,18) 0.190 (29,30) 0.058 (6,28) 0.013 (15,23) 0.190 在图 1中，方形节点代表发电机组(即电源节点)，其中节点1为可自启动发电机组，在系统瘫痪状态下可以自行启动，带动其他发电机组进行供电。由于发电机2与自启动发电机相关联，所以可以直接恢复；这5个发电机机组的恢复次序可通过表 3中的异常度排名得到：2-23-13-22-27。
电源节点 异常度 2 0.1513 13 0.1900 22 0.1080 23 0.1910 27 0.1000 3) 根据确定的发电机组(电源节点)的恢复顺序，通过改进的Dijkstra算法得到最短恢复路径，包含11个节点和10条线路，如表 4所示，也就是系统的骨架网络，如图 1中虚线路径所示。
序号 节点恢复顺序 线路恢复顺序 1 2 (1,2) 2 23 (2,4)—(4,12)—(12,15)—(15,23) 3 13 (12,13) 4 22 (23,24)—(24,22) 5 27 (24,25)—(25,27) 根据重构效率的定义，可计算得到该重构策略的效率值为：
$\eta = \frac{{({r_4} + {r_{12}} + {r_{15}} + {r_{24}} + {r_{25}})/\max (r)/5}}{{\sum\limits_{j = 1}^{11} {{c_j}} /\max ({c_j})/11}} = 1.178{\rm{ }}6$
对同一系统，文献[2]中得到的含6个负荷节点、13条线路的骨架网络效率值为1.1724，文献[4]中得到的含6个负荷节点、11条线路的骨架网络效率值为1.1178，由此可见本文方法可得到目前为止含最少路径数且重构效率较高的系统骨架。在现实生活中，快速得到骨架网络对指导整个网络的恢复工作有很大的实际意义。
4) 图 1中各线路的权重值是其得分排名，骨架网络构造后，各发电机组(即电源节点)均已连通，可单独向未恢复的邻居机组进行供电。在各已恢复机组周围的未恢复线路中工作人员可依据其得分排名从高到低进行恢复。由于各电源节点均可独立工作，以节点22为例，当其恢复发电后，工作人员首先恢复线路(22,21)，而与节点27相关联的线路中(27,28)会被首先恢复；以此扩展，直到整个网络中的线路均恢复正常工作。
-
为进一步验证该算法在大规模真实网络中的有效性，本文以华中500kV电网[14]为研究系统，计算该网络在大规模崩溃后指导重构的骨架网络。经过网络等值后，该网络共有136个节点(包含1个自启动电源节点，42个带有发电机组的电源节点)和175条连边。
首先通过各链路预测方法的预测精确度比较，选择在该网络中表现力较好的RA算法。通过该算法可得到各电源节点的异常度，并可根据其异常度得到重构网络中电源节点的恢复次序。
其中假设64号节点为自启动电源节点，所以无需恢复，而系统中也无与该节点直接相连的电源节点，所以可直接根据表 5中电源节点的顺序进行恢复，对于异常度相同的节点按其编号进行排序，从而得到了电源节点的恢复次序，将这些节点按其排名顺序进行标号，然后通过2.2节中改进的Dijkstra算法计算骨架网络中的最短路径，可得到包含43个电源节点、56个负荷节点以及连接这些节点的102条路径的骨架网络系统，经过计算可得到该重构网络效率值为2.1284。通过重构网络效率值的对比发现，基于异常度的重构策略在较大规模网络中同样有效。
节点 异常度 节点 异常度 节点 异常度 57 0.3675 7 0.3656 15 0.3645 67 0.3674 10 0.3656 81 0.3645 104 0.3674 12 0.3654 132 0.3644 120 0.3669 13 0.3653 134 0.3641 2 0.3665 32 0.3653 82 0.3637 17 0.3665 38 0.3653 105 0.3635 34 0.3664 66 0.3651 29 0.3631 55 0.3663 69 0.3651 124 0.2602 68 0.3663 72 0.3651 16 0.2370 92 0.3663 79 0.3651 129 0.2144 126 0.3663 96 0.3650 118 0.1740 131 0.3663 108 0.3647 26 0.0805 135 0.3662 5 0.3646 60 0.0614 127 0.3658 8 0.3646 114 0.0420
3.1. 标准测试网试验
3.2. 大规模网络试验
-
本文在链路预测算法的基础上，通过异常链路分析的手段提出了一种电力骨架网络恢复策略，主要依据是链路预测得到的异常边刻画了这条边在该网络中的重要性。通过异常度确定电源节点优先恢复顺序，然后用最短路径算法快速构成骨架网络，为恢复整个网络奠定基础。在此基础上，再将网络中的重要链路及时修复，加快整个网络的连通，在实际应用中有重要意义。
DownLoad: