Abstract: In this study, an algorithm using Multilevel Kernel k-Means approach for fast islanding of large power systems is proposed. Intentional islanding using both the spectral and the Multilevel Kernel k-Means methods have been applied on several test systems to show the efficiency of the proposed approach. The results show that the proposed method is much faster than existing methods.
INTRODUCTION
Nowadays power systems are interconnected for economic benefits, increased reliability and operational advantages as reported by Senroy et al. (2006). Deregulation and restructuring have presented new challenges in power systems. Deregulation has defined new objective for power system utilities. The utilities want to maximize their profit and are thus inclined to operate the power system very close to its limits. Moreover, many other factors such as weak connections; unexpected events; hidden failures in protection system; human errors, etc., exist, which in case of a fault in a part of the interconnected power system, may lead it towards instability or complete blackout (Kezunovic et al., 2005; Vijay and Xiaoming, 2005).
Several instances of such blackout events such as the 1996 Western US events, the 2004 Northeastern disturbance and the 2004 Italian blackout have bean reported by Venkatasubramanian and Quintero (2005) and Andersson et al. (2005). Power systems in developing countries are even more unreliable and suffer from a large gap between demand and generation; inadequate transmission capacity and large distances between load centers and generation units. Thus, if any contingencies occur in these systems, they would have serious consequences such as complete blackout (Ahmed et al., 2003). Therefore, power systems must be more intelligent and flexible to survive such serious events. One of the first measures to avoid such critical events in interconnected power systems is rapid detection of contingencies followed by corrective action such as load shedding to limit the extent of the consequences and prevent islanding or a widespread blackout (Liu and Liu, 2006).
A power system might become unstable if there is any inefficiency in its protection, monitoring and control. If this occurs the protection relays may act and trip lines or generators. This might lead to a sequence of events as a result of which the interconnected power system could involuntarily break up into two or more islands, or even lead to total blackout. It may even be the case that generators belonging to a coherent group fall into different islands in which case the recovery of the islands would be more difficult. Controlled power system islanding can decrease the effects of severe disturbances and may be considered a special protection scheme used as the last defense to avoid the occurrence of catastrophic blackouts. Islands formed by power system controlled islanding schemes can be more stable than naturally formed islands following the occurrence of contingencies. Controlled islanding can improve restoration of the power system since it creates an equilibrium between load and generation (Archer and Davies, 2002). It also helps coherent groups of generators be placed in the same island (Kezunovic et al., 2005).
System islanding and load shedding concepts have a long history. For example, one can cite the Manitoba Hydro case (Archer and Davies, 2002), the India case (Rajamani and Hambarde, 1999) and the Tokyo case (Agematsu et al., 2001). Several type of controlled islanding approaches have been presented in power systems in India without which catastrophic events could have caused serious power system blackouts (Rajamani and Hambarde, 1999). The controlled islanding approach based on active and reactive power balancing control installed in Tokyo prevented a blackout in the metropolitan area in Tokyo in 1999 after an airplane ran into a 275 kV transmission tie line (Agematsu et al., 2001).
The main aspects of power system islanding are reviewed by Liu and Liu (2006) where islanding schemes are outlined according to graph partitioning and generator grouping. Intentional power system islanding can be used to reduce the amount of load shedding to close to the theoretical minimum. Controlled islanding together with generation and/or load shedding can be used to prevent blackouts in power systems (Liu and Liu, 2006).
Many methods have been proposed for this purpose such as analyzing stability based on one-machine-infinite-bus analysis using Prony function (Senroy and Heydt, 2006a, b); minimum cut sets (Wang and Vittal, 2004); graph-theoretic eigenvalue and eigenvector analysis called the spectral approach (Li et al., 2005; Yang et al., 2006). Slow coherency methods are often used for intentional power system islanding (Dola and Chowdhury, 2006; You et al., 2003). Yusof et al. (1993) presented a network partitioning method to group generators and load buses into several coherent areas. Their method uses the slow eigenbasis matrix that includes load buses. Grouping the load buses with the reference machine can be done by calculating the nearness of each row eigenvector to the reference row eigenvectors. The grouping information is useful for network decoupling applications such as intentional islanding.
In using Prony function based on one-machine-infinite-bus, islands are determined by slow coherency method. Prony function is used to determine when and where islanding must be done. To analyze dynamic stability for any coherency generator group, the generator group is considered as one machine and the rest of the power system is considered as an infinite bus. Therefore, this method is not suitable for large interconnected power systems. Another limitation of Prony functions is that they are used for analyzing linear systems whereas power systems in the face of disturbances are nonlinear systems. A self-healing strategy has been reported by You et al. (2003) to deal with catastrophic events when power system vulnerability analysis indicates that the system is approaching an extreme emergency state. In this approach, the system is adaptively divided into smaller islands for quick restoration. Then a load shedding scheme based on the rate of frequency decline is applied. Two comprehensive approaches to deal with islanding based on the grouping information and using minimal cutsets have been reported by Wang and Vittal (2004) which rely on Breadth First Search (BFS) and Depth First Search (DFS) techniques. They require a very long time to obtain the solution, particularly if the size of the power system under study is large. These methods are slow, whereas islanding must be done rapidly for it to be an effective countermeasure.
The latest approach for controlled islanding of power systems is based on the spectral method reported by Li et al. (2005). The methods mentioned so far are either based on search approach, slow coherency grouping approach, or a combination of the two which are slow compared with the spectral method. This method is later extended by Chan et al. (1994) for k-way partitioning problems. K-way partitioning spectral method is applied to the intentional islanding of power systems by Li et al. (2005). This is the fastest approach proposed so far for large scale power systems.
Dhillon et al. (2005, 2007) have presented a graph partitioning method based on a Multilevel Kernel k-Means approach with a high speed performance in partitioning graphs. They have used their method on large-scale partitioning tasks such as image segmentation; social network analysis and gene network analysis types of systems. Wang et al. (2008) presented a searching algorithm for islanding using a multilevel reduced graph partition algorithm. They only test their approach on the IEEE 118 bus system and present no evidence that their approach is faster than existing methods. In this study, an algorithm using Multilevel Kernel k-Means approach is proposed for fast islanding of large power systems, several test system are used to show the efficiency of the proposed approach and the results are compared with the results of the best existing approach presented by Li et al. (2005) using the spectral approach. The results show that the proposed method is much faster than other methods which (Wang et al., 2008) failed to show.
PARTITIONING GRAPH BASED ON SPECTRAL METHOD
Here, the background of the spectral method is presented first and then an example of its performance is presented on k-way partitioning.
Background of the spectral method: Spectral method is an approach for partioning graph. It is used in many areas such as VLSI, FPGA, multi-chip modules, integrated circuits, macro cells (Hagen et al., 1992) and real-life pattern recognition, gene network analysis, social network analysis and image segmentation and power system (Dhillon et al., 2007).
The spectral method uses eigenvalues for partitioning graphs as presented by Hagen et al. (1992). The eigenvalues of the Laplacian matrix Q are calculated for this purpose. Graphs may be partitioned into two parts using the second smallest eigenvalues. Chan et al. (1994) presented the k-way partitioning approach based on the spectral method and demonstrated that the smallest k eigenvalues can be used for partitioning a graph into k partitions.
This could be easily proved by Eq. 1 as detailed by Chan et al. (1994):
(1) |
where, P = {P1, P2, …, Pk} is a set of k partitions of the graph G, Π is the set of all k-way partitions of the graph G and Eh is the sum of the weights of the edges in G having precisely one endpoint in Ph. This approach was used by Li et al. (2005) for intentional power system islanding. An example of partitioning graphs using this approach is presented below.
An example of the partitioning graph using spectral method: An example is presented here to demonstrate the application of the spectral method for partitioning a graph into 3 partitions, using the smallest 3 eigenvalues. The weighted graph of a 14 bus power system which has been changed for the purposes of illustrating this approach is shown in Fig. 1.
The Laplacian matrix for the above graph is as follows in Eq. 2:
(2) |
where, eij is weight of the edge that connects the two vertices vi and vj (note that eii = 0). Therefore, the Laplacian matrix is as shown as follows:
| Fig. 1: | Graph with 14 vertices and 21 edges |
| Fig. 2: | Amount of the second and third eigenvectors with respect to vertices |
The eigenvalues of Q are as follow:
Figure 2 shows the second and third eigenvectors of Q with respect to the vertices. It also shows that this graph can divided to three partitions, as follow:
| • | Partition 1: {1, 2, 3, 4, 5} |
| • | Partition 2: {6, 7, 8, 9} |
| • | Partition 3: {10, 11, 12, 13, 14} |
The spectral method is a useful approach. But along with increasing number of the vertices of the graph. The time of partitioning also increases since it depends on the eigenvectors calculation.
PARTITIONING GRAPH BASED ON MULTILEVEL KERNEL k-MEANS METHODS
Spectral partitioning and Kernel k-Means are two seemingly different methods for partitioning graphs. However, they are very similar mathematically. This mathematical similarity can be used to design a fast kernel-based multilevel graph partitioning algorithm that is better in terms of speed, memory storage and quality (Dhillon et al., 2007; Filipponea et al., 2008). In this study, it is proposed to apply the Multilevel Kernel k-Means method to the intentional power system islanding problem. Since, there is no need to calculate eigenvalues and eigenvectors in the Kernel k-Means method, it is faster than the spectral method.
The basic principles of the Multilevel Kernel k-Means are presented based on the study of Dhillon et al. (2007). Multilevel Kernel k-Means algorithm partitions graphs in three phases. Figure 3 provides a graphical overview of the multilevel framework. Suppose G0 = (v0, ε0, A0) is an input graph that must be partitioned. Multilevel Kernel k-Means algorithm can be divided into three phases: aggregation, partitioning and retrieval as follows.
Aggregation: Suppose G0 is the graph that must be partitioned. In aggregation phase G0 is converted to the graph G1 with a smaller size; G1 is converted to G2; … and finally Gm–1 is converted to Gm such that |v0|>|v1|>…>|vm|. To aggregate a graph from Gi to Gi+1, sets of nodes in Gi are merged to single node in Gi+1. In merging several nodes into a single node, the edge weights out of this node are the sum of the edge weights out of the original nodes (Dhillon et al., 2007).
Partitioning: The second phase is graph partitioning. Since, the dimension of the graph has been reduced in the previous phase, partitioning the graph can be done in the least time.
Retrieval: Retrieval phase is the last phase of Multilevel Kernel k-Means method. The initial partitions in Gi–1 (i-1th level) are the final partitions of Gi (ith level). Each node in the ith level splits up into the nodes that had made it up in the level i-1th of aggregation phase. The partitions in any level i-1th in the retrieval phase are refined by the Kernel k-Means algorithm. The retrieval phase is completed after refining G0. Since in any level of the retrieval phase, a good initial partition exists, the retrieval often quickly yields a very efficient partition (Dhillon et al., 2007).
The principles of the Kernel k-Means are presented as follows:
Given a set of vertices v1,v2,…vn, that are placed into initial partitions p1,p2,…pk, the Kernel k-Means algorithm intends to improve these partitions such that the following objective function is minimized (Dhillon et al., 2007):
(3) |
where,
is the centroid of the pc and ωi is the weight of vi.
Objective function J can be rewritten as follow:
(4) |
| Fig. 3: | Process of multilevel graph partitioning |
where, φ is a function to map data point to a higher dimensional feature space and:
Thus, the nonlinear partitioning problem is converted into a linear partitioning problem and the k-Means is applied in this feature space. Note that this linear partitioning in the feature space is corresponding to a nonlinear partitioning in the input space.
Therefore, one may write:
(5) |
Indeed, the inner product φ(vi) · φ(vj) can be written as a Kernel function kij. Thus one may write:
(6) |
Multilevel algorithm uses Kernel k-Means for the retrieval steps. Depending on the graph partitioning objective to be optimized and given the adjacency matrix for the current level, the weights and the Kernel can be set up appropriately at each step of the retrieval. At all levels, the initialization for Kernel k-Means is taken to be the partitioning induced by the previous level.
PROPOSED ALGORITHM FOR INTENTIONAL ISLANDING OF POWER SYSTEM USING MULTILEVEL KERNEL K-MEANS
Since, a very high gain in speed can be achieved using the Multilevel Kernel k-Means method in graph partitioning, it is proposed to apply it to the intentional islanding of power systems in modern energy management systems that require real-time performance. To do so, the power system must first be abstracted into a graph as follows to implement intentional islanding:
| • | Compute the power flow of the power system network |
| • | Convert the power system network into a graph G |
| • | Each bus of the power network is a vertex of the graph G |
| • | Each transmission line of the online power system diagram is an edge of graph G |
| • | The weight of each edge of graph G is assigned according to the absolute value of real power flow of the corresponding transmission line |
The created graph of the power system is considered as an input for Multilevel Kernel k-Means approach. Figure 4a, b shows the proposed algorithm for intentional islanding of power systems using Multilevel Kernel k-Means adopted from an earlier method called Metis (Karypis and Kumar, 1999).
| Fig. 4a: | The first part of the flowchart of finding the optimum form
of intentional islanding of the power system by Multilevel Kernel k-Means |
| Fig. 4b: | The second part (continuation) of the flowchart of finding
the optimum form of intentional islanding of the power system by Multilevel
Kernel k-Means |
CASE STUDY
The IEEE 118 bus system (Dola and Chawdhury, 2006), IEEE 300 bus system and the 2746 bus Polish power system are used for testing the proposed intentional islanding algorithm and comparing the results with the spectral method. The Multilevel Kernel k-Means algorithm is applied for intentional islanding of the IEEE 118 bus test system. The results of comparing the performance of intentional islanding algorithms by spectral method and Multilevel Kernel k-Means applied to the IEEE 118 bus, IEEE 300 bus and the 2746 bus Polish power systems are shown.
In the IEEE 118 bus system, IEEE 300 bus system and the 2746 bus polish power system, there are 118 buses and 186 lines, 300 buses and 417 lines and 2746 buses and 3714 lines, respectively.
Intentional islanding of the IEEE 118 bus test system by Multilevel Kernel k-Means approach: The proposed intentional islanding approach is applied to the IEEE 118 bus test system. In the IEEE 118 bus test system shown in Fig. 5 (Dola and Chowdhury, 2006), there are 118 buses and 186 lines.
The system is operating in a normal state, where all the flows satisfy system operation constraints. The system has a total generation of 4374.86 MW and 795.68 M Var. It has a total load of 4242 MW and 1438 MVar.
Suppose there is a severe fault on the transmission line which is connected between bus 64 and 65 as indicated in Fig. 4. Since, the line between bus 64 and 65 supplies a large amount of the demand for buses 56, 57, 62, 66 and 67, its tripping would cause an overflow of lines 62-66, 62-67 and 66-67. After the tripping, the proposed intentional islanding approach is applied before the tripping of the overloaded transmission lines.
As a result, the proposed intentional islanding approach breaks up the power system into two islands. The following is a list of the two areas:
| Area one = {1 through 78, 81, 113 through 118} |
| Area two = {79, 80, 82 through 112} |
| Cut set = {80-81, 79-78, 80-77 and 82-77} |
The cut set provides the points of separation. Area one has 85 buses and 130 branches. Area two has 33 buses and 50 branches. The two areas are shown in Fig. 6.
A comparison of the spectral method and this approach based on Multilevel Kernel k-Means method is shown in Table 1 based on computational time for normalized cut. Table 1 shows the computational time for islanding IEEE 118 bus power system, IEEE 300 bus power system and 2746 bus polish power system by spectral method vs. Multilevel Kernel k-Means approach.
The results presented in Table 1 show that although the computational time increases as the system size increases, the computational time required using the proposed Multilevel Kernel k-Means method is much less than the spectral method. The spectral method is highly time consuming especially in large power systems since islanding requires the calculation of eigenvalues. The fractional reduction in computational time is very impressive since the proposed approach does not require the calculation of eigenvalues. Of course, not all of this indicates a gain in speed since the code used for the Multilevel Kernel k-Means approach indirectly uses C++ and is somewhat faster than the code that was written for the spectral approach in Matlab.
| Fig. 5: | The IEEE 118 bus test system adapted from Dola et al. (2006) |
| Fig. 6: | Islanding the IEEE 118 bus test system into two areas |
| Table 1: | A comparison of computational time |
CONCLUSION
Intentional power system islanding is the last line of defense for avoiding power system blackout. For it to be affective, it must be done fast. The intentional islanding methods presented previously are slow and are therefore not proper for large scale interconnected power systems. In this study, a new algorithm for intentional islanding using Multilevel Kernel k-Means has been proposed and compared with the spectral method. It is shown that the new approach requires much less time compared with earlier methods. Moreover, this time saving is improved as the system size increases. Results of simulations are presented to demonstrate this method. The simulations reported in this study have been carried out on an IBM PC computer with a 2.8 GHz Celeron processor using Matlab for the spectral approach and existing code called Graclus Software, version 1.2 for the Multilevel Kernel k-Means approach.