Energy and Power Engineering, 2013, 5, 763-768
doi:10.4236/epe.2013.54B147 Published Online July 2013 (http://www.scirp.org/journal/epe)
A New Algorithm for Black-start 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
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 black-start 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 New-England 39 bus
system at last.
Keywords: Black-start 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 [1-4]. After the
blackout, the black-start power needs to provide power
for the units without self-starting 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
time-consuming 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 black-start 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 black-start unit has
been determined and nodes of the path between the
black-start unit and target unit have been combined into
one node before calculation. Reference [7] proposed a
black-start 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 black-start zone partitioning algorithm
based on fuzzy clustering analysis theory is proposed
with the aim to avoid deficiencies for the current meth-
ods of black-start zone partitioning. The reliability and
timeliness of the black-start 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 black-start 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 “either-or” nature. In fact most of the
object does not have strict property and “soft clustering”
is more suitable [8]. Fuzzy Clustering Analysis is a

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 black-start 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 n-th 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, min-max 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
X
xxxxx xx
im




Meanwhile, the degree of similarity between i
x
and
j
x
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
x
xX

, if ()1
ij
r


, object i
x
and object
j
x
will be clustered into the same category at level

.
When clustering by R

with a certain

, classification
results is the equivalent classification at level

.

Y. J. LI ET AL. 765
3. Power System Black-start Zone
Partitioning Algorithm
Black-start zone partitioning is aimed at partitioning the
black-start 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
self-excitation.
c) Limiting the number of substation involved in the
black-start 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
self-starting capability should be less than the maximum
output of the black-start 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 time-consuming of restoring the
black start units, the lines and the units without
black-start capacity.
3.1. Characteristic Indexes Extracting
The essence of black-start zone partition is to divide
nodes of black-start 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 black-start 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 black-start recovery go
smoothly, there must be at least one black-start power
(including black-start unit, isolated island and tie line) in
each partition. Black-start 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 black-start pow-
er are as follows:
a) Physical distance from the black-start 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 k-th 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 i-th
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
X
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 self-starting capa-
bility.
3.2. Partitioning Algorithm Flow
The steps of black-start 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

Y. J. LI ET AL.
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 black-start 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
IEEE-39. Supposing node 32, node 36 and node 37 are
the black-start units, and there must be at least one of
them in each zone to ensure every zone has capability of
self-starting. Thus the set to cluster includes 36 other
nodes in the IEEE-39, 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 non-isolated class later for the electrical
distance from them to the black-start power is further
than to others. The reason why node 25 turned non-iso-
lated later is that the number of long line near black-start
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 black-start 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 black-start resource and nodes that have shorter
length, less voltage conversions and less passing substa-
tions to the black-start resource than others. The result
meets the principles of black-start 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 black-start
resource and larger capacity on condition that the power
needed while start is less than the capacity of black-start
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 black-start zone parti-
tioning based on fuzzy clustering analysis has been pre-
sented. Electrical distance between black-start 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 black-start zone partition,
and then transitive closure method has been used for
clustering the nodes to get a black-start zone partitioning
scheme. Simulation on the IEEE-39 has confirmed the
Figure 1. Black start zone partition schematic diagram.

Y. J. LI ET AL.
768
rationality and effectiveness of the algorithm. It is helpful
to shorten the time-consuming for restarting the grid and
to improve the reliability of restoration taking algorithm
proposed when developing black-start 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. 271-277.
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. 2093-2096.
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 26th-Causes and
Recommendations,”Automation of Electric Power
Systems, Vol. 30, No. 1, 2006, pp. 1-7.
[5] H. P. Liang, H. Y. Ma, X. P. Gu and Black-Start,
“Network Partitioning Considering Time Limits and
Subsystem Restoration Sequences,” Power and Energy
Engineering Conference (APPEEC), 2011, pp. 25-28.
[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. 12-16.
[7] Y. S. Liu, W. C. Wu, Y. Q. Feng, et al., “Black-start Zone
Partitioning Based on Ordered Binary Decision Diagram
Method,” Proceedings of the CSEE, Vol. 28, No. 10,
2008, pp. 26-31.
[8] X. B. Gao, “Fuzzy Clustering Analysis and Its
Applications,” Xi'an: Xidian University Press, 2004,
37-60.
[9] Z. Li, B. X. Zhou and N. Lin, “Classification of Daily
Load Characteristics Curve and Forecasting of Short-term
Load Based on Fuzzy Clustering and Improved BP
Algorithm,” Power System Protection and Control, Vol.
40, No. 3, 2012, pp. 56-60.
[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. 46-49.
[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. 19-22.
[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. 28-32.
[13] Power System Restoration Working Group, “Special
Considerationsin Power System Restoration,” IEEE
Transon Power Systems, Vol. 7, No. 4, 1992, pp.
1419-1427.doi:10.1109/59.207363
[14] Y. W. Gao, X. P. Gu, Y. Liu, et al. “Automatic
Derivation and Assessment of Power System Black-start
Schemes,” Automation of Electric Power Systems, Vol.
28, No. 13, 2004, pp. 50-54.