Energy and Power Engineering, 2013, 5, 763768 doi:10.4236/epe.2013.54B147 Published Online July 2013 (http://www.scirp.org/journal/epe) A New Algorithm for Blackstart Zone Partitioning Based on Fuzzy Clustering Analysis Yujia Li1, Yu Zou1, Yupei Jia1, Yunxia Zheng2 1China Electric Power Researc h I n s t itute, Beij i n g, China 2Jibei Qinhuangdao Electric Power Company, Hebei, China Email: liyujia@epri.sgcc.com.cn, zhengyunxia509@sina.com Received April, 2013 ABSTRACT On the process of power system black start after an accident, it can help to optimize the resources allocation and accel erate the recovery process that decomposing the po wer system into several independent partition s for parallel recovery. On the basis of adequate consideration of fuzziness of blackstart zone partitioning, a new algorithm based on fuzzy clustering analysis is presented. Characteristic indexes are extracted fully and accurately. The raw data matrix is made up of the electrical distance between every nodes and blackstart resources. Closure transfer method is utilized to get the dynamic clustering. The availability and feasibility of the proposed algorithm are verified on the NewEngland 39 bus system at last. Keywords: Blackstart Zone Partitioning; Fuzzy Clustering Analysis; Electrical Distance; Clo s ure Transfer Method 1. Introduction Since the 1960s many power outages have occurred ar round the world, which brought great losses to both so cial production and people's livelihood [14]. After the blackout, the blackstart power needs to provide power for the units without selfstarting capability as little time as possible so that they can reconnect the grid and supply the main node, and gradually establish a preliminary re covery which lay the foundation of fully load recovery in next stage. During the recovery process, taking parti tioning recovery, by which each subsystem recovers in dependently, is not only conducive to shorten recovery timeconsuming but also help to improve the security of the entire system recovery. It is beneficial to ensure the smooth progress of parti tioning recovery that adopting a scientific partitioning algorithm. Reference [5] has discussed system partition ing based on the distribution of blackstart generators considering the startup characteristics of the unit and system status, but lack of consideration of restrictions for the security and the matching between power generation and load. In [6] a new subsystem partitioning algorithm based on theory of structure of complex network has been proposed. There is a certain degree of subjectivity for the target unit which starts after blackstart unit has been determined and nodes of the path between the blackstart unit and target unit have been combined into one node before calculation. Reference [7] proposed a blackstart zone partitioning strategy based on ordered binary decision diagram trying to obtain optimal solution mainly by topology discovery, but other influencing fac tors were concerned too less. In this paper, a blackstart zone partitioning algorithm based on fuzzy clustering analysis theory is proposed with the aim to avoid deficiencies for the current meth ods of blackstart zone partitioning. The reliability and timeliness of the blackstart recovery has been cones dered fully on the extracting of the features indicators. The electrical distance between the target unit, load bus bars, important stations and blackstart units have been defined to form the original data matrix, and the transi tive closure method for clustering has been adopted. The verification results show that the method is feasible and effective. 2. Fuzzy Clustering Analysis Cluster analysis is one of multivariate statistical analysis. It groups a set of objects in such a way that objects in the same group (called cluster) are more similar (in some sense or another) to each other than to those in other groups (clusters) Traditional cluster analysis is a kind of “hard cluster ing”. Each object is identified strictly and is divided in certain types of “eitheror” nature. In fact most of the object does not have strict property and “soft clustering” is more suitable [8]. Fuzzy Clustering Analysis is a Copyright © 2013 SciRes. EPE
Y. J. LI ET AL. 764 method of “soft clustering” which considering not only whether the relationship between objects exists but also the degree of the relationship by taking full account of the fuzziness of objects being analysed. Fuzzy clustering analysis has been widely used in many fields of power system such as load characteristics analysis [9], failure diagnosis [10], electricity prices partition [11], voltage control partition [12], except th e filed of blackstart zone partitioning. 2.1. Steps of Fuzzy Clustering Analysis Steps of fuzzy clustering analysis can be summarized as follows: a) original data matrix building; b) normalization; c) demarcating; d) clustering. 1) original data matrix build ing Assuming that set are objects need to classified, each object consists of n indicators that can describe its traits and the nth indicator is denoted as so that the original data matrix can be established as. It should be noted that indicators in the matrix need to be determined with spe cific analysis for the certain problem and that extracting characteristic indicators fully and accurately is the basis for the application of fuzzy clustering method . 2) Normalization When solving practical problems different data gener ally have different dimensions. Some characteristic indi cators with particularly large magnitude may contribute to classifying too much while those with the very small magnitude may be ignored during the calculating. In or der to make data with different dimension can be com pared with each other; we usually need to transform data in an appropriate way. In accordance with the require ments of the fuzzy matrix, data should be compressed into the interval [0,1]. Method of data normalization ap plied more frequently at present are as follows: zero mean normalization, minmax normalization, max nor malization, mean normalization, center normalization, logarithmic normalization, etc. This paper takes the min max normalization method to normalize the original data matrix, by which the expression is shown below, 1 1 1 min{ }, (1,2,,) max{}min{ } ik ik im ik ik ik im im xx ykn xx 1 (1) Obviously, , and the influence of dimen sions of each indicator has been removed after normali zation. 0 ik y 3) Demarcating Demarcating is aim to get the statistics which can measure the degree of similarity of objects being classi fied. Assuming that Interval discussed is given below: 121 2 {,,,}, (,,,) (1,2,,) mi iiin xxxxx xx im Meanwhile, the degree of similarity between i and is defined as iji j (, )(,1,2, ,rRxxij )m ， ij r . Meth ods to get ij mainly include similarity coefficient method (such as scalar product method, cosine method, exponen tial similarity coefficient method, correlation coefficient method, max and min method, min arithmetic average method, and min geometric mean method), distance me thod (such as absolute value reciprocal method, absolute value exponential method, and direct distance method), subjective evaluation methods, etc. We take absolute value exponential method to calculate which is given by: r 1 exp(), (,1,2,, ) n ijik jk k rcyy ij m (2) where c is a specific positive number range from 0 to 1(0 1 ij r ), in this case we set . 1c 4) Clustering Clustering is the process to classify the object of study based on the fuzzy matrix. Clustering method mainly include clustering based on equivalent fuzzy matrix, di rect cluster and maximal tree. Closure transfer method is adopted in this paper and the detail will be shown in next part. 2.2. Fuzzy Clustering Transitive Closure The calibration matrix obtained before is just a fuzzy similar matrix and not necessarily transitive, therefore, we should transform into fuzzy equivalent matrix . Quadratic formulation is used here to calculate tran sitive closure of so that equation can be expressed as: R R * RR* ()tR R 24 2k RR RR k (3) After a finite number of computing, there is a k which fit the equation 2kkk RRRR indicate that has been transitive already, meanwhile, is the fuzzy equivalent matrix that we need. k R *k RR Suppose () ijm m Rr is the fuzzy matrix，for any [0,1] ,  cut fuzzy matrix of can be obtained, that is R () () ijm m Rr . The element of R is defined as () 1, , (,1,2,,) 0, ij ij ij r rij r m (4) For , ij xX , if ()1 ij r , object i and object will be clustered into the same category at level . When clustering by R with a certain , classification results is the equivalent classification at level . Copyright © 2013 SciRes. EPE
Y. J. LI ET AL. 765 3. Power System Blackstart Zone Partitioning Algorithm Blackstart zone partitioning is aimed at partitioning the blackstart units, units without start capacity, important substations and loads into different areas by a reasonable way. Principles sh ould be taken into account when p arti tioning can be summarized as follows [13, 14]: a) Number of voltage conversions during the black start process should be less than limit, so as to reduce the possible of overvoltage that is caused by unloaded lines charging. b) Limiting the length of the path to decrease the ca pacitive load and then reduce the probability of generator selfexcitation. c) Limiting the number of substation involved in the blackstart process to reduce the recovery operation and then reduce the risk of recovery program and the recov ery time. d) The mi n imu m lo a d re qu i re d to start the unit without selfstarting capability should be less than the maximum output of the blackstart power. With this condition, the capacity of the unit that starts secondly should be chosen as large as possible. e) Loads that have an important impact on the national economy should recover as soon as possible, hence, gen rators supplying to important consumers should be re stored as fast as possible. When limiting the timeconsuming of restoring the black start units, the lines and the units without blackstart capacity. 3.1. Characteristic Indexes Extracting The essence of blackstart zone partition is to divide nodes of blackstart unit, other units, important substa tions and important loads into different partitions by rea sonable method so that each partition could carry out restoration at the same time. To adapt to algorithm pro posed, the following factors are simplified when extract ing the features indicators. a) All the generators, substations and load buses in the network are abstr acted as undifferentiated nodes. b) Ignore the importance level of load, the difference in starting characteristic of generators , the differences of time operating breakers in substation and the direction of power flow in line, while, each electric transmission line and transformer are abstracted as an unweighted segment with no direction. c) This paper just take power plant into consideration when choose the blackstart unit, however, isolated is land and tie line can be regarded as generator thus the algorithm proposed is also suitable for situations that system restore with power from isolated island or tie line. In order to make sure the blackstart recovery go smoothly, there must be at least one blackstart power (including blackstart unit, isolated island and tie line) in each partition. Blackstart power supplies the energy for restarting other generators or loads through several In termediate substations. Taking the reliability and timeli ness into account, several indicators to measure the strength of the electrical contact between the target unit, load bus bars, important substations and blackstart pow er are as follows: a) Physical distance from the blackstart power; b) Number of voltage conversions; c) Number of substation involved. These three indicators are cost indexs; the target of partition is to control the three indicators as small as pos sible. The electrical distance between node and node is defined as: ij () () 1(1,2, ,,1,2, ,) l ijij kij k k Lrimj n (5) where, () min () max min ij k ij k rr rrr , is the kth indicators to ()ij k r describe the strength of the electrical contact, ()ij k r is its value after normalization, , min are the maximum and minimum value of ()ij k, i max r r r is the weight of ith indictor, is the number of indictors and l = 3 at pre sent. l Taking the electrical distance between node i and node j as the characteristic indicator, original data matrix can be established as follows. (),,(1,2,,,1,2,, ) ijm nijij xxLimj n (6) where m is the number of objects of classification in cluding power plants, substations and load bus in power system, n is the number of units with selfstarting capa bility. 3.2. Partitioning Algorithm Flow The steps of blackstart partition with fuzzy clustering analysis method are as follows. a) Building the original data matrix that represents the electrical distance between each node based on formula (5) and (6); b) Normalizing every element in the original data ma trix according to formula (1); c) Forming the fuzzy similar matrix by calibrating ob jects to be classified with formula (2); d) Taking the transitive closure method when clusteri ng every object with suitable threshold [0,1] the cut fuzzy matrix of R can be formed as () () ijm m Rr by formula thus the partition schema is determined; Adjusting the result can obtain the final patition Copyright © 2013 SciRes. EPE
Y. J. LI ET AL. Copyright © 2013 SciRes. EPE 766 1,2, ,31,33,34,35,38,39X. scheme by taking the practical situation of the grid into account, such as the location of blackstart resources and the result of power flow check. Based on the electrical distance from each node to node 32, node 36 and node 37, the original data matrix is formed as 4. Simulation Example 36 3 () (1,2,,36,1,2,3) ij Xx ij A simulation example has been programmed to test if the fuzzy clustering analysis is rational and effective on the IEEE39. Supposing node 32, node 36 and node 37 are the blackstart units, and there must be at least one of them in each zone to ensure every zone has capability of selfstarting. Thus the set to cluster includes 36 other nodes in the IEEE39, that is Calculated with Matlab 7.6.0, we can get the normal ized matrix Y, the fuzzy similar matrix and the transitive closure matrix .By any differ ent value of threshold R 16 ()BtR R [0,1] ,  cut fuzzy matrix of can be got. Corresponding to each R , the equivalent classification at level is shown in Table 1. Table 1. Partition Result Corresponding to Different Threshold. No. Partition Result 1 1 2 0.9832 {28,29} 3 0.9760 {21,24}，{28,29} 4 0.9746 {20,33}，{21,24}，{28,29} 5 0.9622 {7,31}，{20,33}，{21,24}，{28,29,38} 6 0.9568 {7,31}，{20,33,34}，{21,24}，{28,29,38} 7 0.9567 {2,26}，{7,31}，{20,33,34}，{21,24}，{28,29,38} 8 0.9528 {2,26}，{7,31}，{19,20,33,34}，{21,24}，{28,29,38} 9 0.9479 {2,26,30}，{7,31}，{19,20,33,34}，{21,24}，{28,29,38} 10 0.9437 {1,2,26,30}，{7,31}，{19,20,33,34}，{21,24}，{28,29,38} 11 0.9390 {1,2,26,30}，{6,7,31}，{10,11,13}，{19,20,33,34}，{21,24}，{28,29,38} 12 0.9314 {1,2,26,30}，{6,7,8,31}，{10,11,13}，{19,20,33,34}，{21,24}，{28,29,38} 13 0.9291 {{1,2,26,30}，{6,7,8,31}，{10,11,12,13}，{19,20,33,34}，{21,24}，{22,23,35}，{28,29,38} 14 0.9277 {1,2,26,30}，{6,7,8,31}，{10,11,12,13}，{17,18,27}，{19,20,21,24,33,34}，{22,23,35}，{28,29,38} 15 0.9234 {1,2,26,30}，{5,6,7,8,10,11,12,13,31}，{17,18,27}，{19,20,21,24,33,34}，{22,23,35}，{28,29,38} 16 0.9138 {1,2,26,30}，{5,6,7,8,10,11,12,13,14,31}，{17,18,27}，{19,20,21,24,33,34}，{22,23,35}，{28,29,38} 17 0.9094 {1,2,26,30,39}，{5,6,7,8,10,11,12,13,14,31}，{16,19,20,21,24,33,34}，{17,18,27}，{22,23,35}，{28,29,38} 18 0.9059 {1,2,26,30,39}，{3,17,18,27}，{5,6,7,8,10,11,12,13,14,31}，{16,19,20,21,24,33,34}，{22,23,35}，{28,29,38} 19 0.9042 {1,2,26,28,29,30,38,39}，{3,17,18,27}，{5,6,7,8,10,11,12,13,14,31}，{15,16,19,20,21,24,33,34}，{22,23,35}, 20 0.8967 {1,2,26,28,29,30,38,39}，{3,17,18,27}，{4,5,6,7,8,10,11,12,13,14,31}，{15,16,19,20,21,22,23,24,33,34,35} 21 0.8933 {1,2,25,26,28,29,30,38,39}，{3,17,18,27}，{4,5,6,7,8,10,11,12,13,14,31}，{15,16,19,20,21,22,23,24,33,34,35} 22 0.8900 {1,2,25,26,28,29,30,38,39}，{3,15,16,17,18,19,20,21,22,23,24,27,33,34,35}，{4,5,6,7,8,10,11,12,13,14,31} 23 0.8812 {1,2,3,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,33,34,35,38,39}，{4,5,6,7,8,10,11,12,13,14,31} 24 0.8790 {1,2,3,9,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,33,34,35,38,39}，{4,5,6,7,8,10,11,12,13,14,31} 25 0.8746 {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,33,34,35,38,39}
Y. J. LI ET AL. 767 For space limitation, subsets with two nodes or more but only one node has been listed in Table 1. As is shown in Table 1, the quantity of elements with one common similarity gradually increase and the number of clustering result turn from 36 to only 1, when threshold decrease from 1 to 0.8746. Nodes in {3, 9, 15, 16} join into any nonisolated class later for the electrical distance from them to the blackstart power is further than to others. The reason why node 25 turned noniso lated later is that the number of long line near blackstart power is too much that the node is of less similarity than others. While 0.8900 , three zones centered by node 32, node 36 and node 37 are formed clearly. Partition result listed in Table 1 just means clustering result mathematicall. Powerflow verification is needed to ensure that the sum of active power should be more than sum of load in each zone by adjusting schema which failed to pass the verification. The final blackstart zone partition schema is shown as is in Figure 1, where dashed lines have marked the boundaries between each zone. As is shown in Figure 1, each of the three zones con tains a blackstart resource and nodes that have shorter length, less voltage conversions and less passing substa tions to the blackstart resource than others. The result meets the principles of blackstart zone partition. Adja cent rather than distant nodes are basically divided into the same zone. The characteristic indexes extracted in this paper are reasonable. During the restoration in each zone, units, with less electrical distance to the blackstart resource and larger capacity on condition that the power needed while start is less than the capacity of blackstart resouce, should be chosen and restart have priority. Then part of loads should be restarted gradually. In the process of recovery, system voltage and frequency stability need to be strict control, each zone should be paralleled at the right time, and all of the loads should be restarted step by step until the network is stable. 5. Conclusions In this paper, a new algorithm for blackstart zone parti tioning based on fuzzy clustering analysis has been pre sented. Electrical distance between blackstart resource and each of other nodes is chosen as the characteristic indicators to form the original data matrix by taking a full account of principles for blackstart zone partition, and then transitive closure method has been used for clustering the nodes to get a blackstart zone partitioning scheme. Simulation on the IEEE39 has confirmed the Figure 1. Black start zone partition schematic diagram. Copyright © 2013 SciRes. EPE
Y. J. LI ET AL. 768 rationality and effectiveness of the algorithm. It is helpful to shorten the timeconsuming for restarting the grid and to improve the reliability of restoration taking algorithm proposed when developing blackstart zone partitioning schema after blackouts. REFERENCES [1] M. M. Adibi, P. Clelland, L. Fink, et al., “Power System Restoration A Task Force Report,” IEEE Transactions on Power Systems, Vol. 2, No. 2, 1987, pp. 271277. doi:10.1109/TPWRS.1987.4335118 [2] A. Kurita and T. Sakurai, “The Power System on July 23, 1987 in Tokyo,” Proceedings of the 27th Conference on Decision and Control, Vol. 3, 1988, pp. 20932096. doi:10.1109/CDC.1988.194703 [3] U.S.Canada Power System Outage Task Force. Final Report on the August 14, 2003 Black out in the United States and Canada. [4] S. Q. Tang, M. Zhang, J. S. Li, et al., “Review of Blackout in Hainan on September 26thCauses and Recommendations,”Automation of Electric Power Systems, Vol. 30, No. 1, 2006, pp. 17. [5] H. P. Liang, H. Y. Ma, X. P. Gu and BlackStart, “Network Partitioning Considering Time Limits and Subsystem Restoration Sequences,” Power and Energy Engineering Conference (APPEEC), 2011, pp. 2528. [6] Z. Z. Lin, F. S. Wen and H. Zhou, “A New Algorithm for Restoration Subsystem Division Based on Community Structure of Complex Network Theory,” Automation of Electric Power Systems, Vol. 33, No. 12, 2009, pp. 1216. [7] Y. S. Liu, W. C. Wu, Y. Q. Feng, et al., “Blackstart Zone Partitioning Based on Ordered Binary Decision Diagram Method,” Proceedings of the CSEE, Vol. 28, No. 10, 2008, pp. 2631. [8] X. B. Gao, “Fuzzy Clustering Analysis and Its Applications,” Xi'an: Xidian University Press, 2004, 3760. [9] Z. Li, B. X. Zhou and N. Lin, “Classification of Daily Load Characteristics Curve and Forecasting of Shortterm Load Based on Fuzzy Clustering and Improved BP Algorithm,” Power System Protection and Control, Vol. 40, No. 3, 2012, pp. 5660. [10] H. Lan, G. G. Zheng, X. L. Sun, et al., “Research of Power Transformer Fault Diagnosis Based on Vague Clustering Analysis,” Electrical Measurement & Instrumentation, Vol. 48, No. 1, 2011, pp. 4649. [11] R. Fu, Y. S. Qiu and Y. Li, “A Fuzzy Clustering Method for Price Partition Based on the Sensitivity of Node Price,” Power Demand Side Management , Vol. 9, No. 3, 2007, pp. 1922. [12] Y. Wang, J. C. Peng, Y. Q. He, et al., “Application of Fuzzy Clustering in Sencondary Voltage Control Partitioning,” RELAY, Vol. 36, No. 11, 2008, pp. 2832. [13] Power System Restoration Working Group, “Special Considerationsin Power System Restoration,” IEEE Transon Power Systems, Vol. 7, No. 4, 1992, pp. 14191427.doi:10.1109/59.207363 [14] Y. W. Gao, X. P. Gu, Y. Liu, et al. “Automatic Derivation and Assessment of Power System Blackstart Schemes,” Automation of Electric Power Systems, Vol. 28, No. 13, 2004, pp. 5054. Copyright © 2013 SciRes. EPE
