Graph Theoretic Analysis of Power Networks

Graph Theoretic Analysis of Power Networks

Divya S1, Assistant Professor, Dept. of EEE, The National Institute of Engineering, Mysuru Pawan Bharadwaj2, Assistant Professor, Dept. of ECE, The National Institute of Engineering, Mysuru

ABSTRACT – The intensified interest in Graph Theory applied to the field of Power Engineering is due to its capability in predicting the behavior of electrical networks. A complex electrical network with many interconnected electrical elements and devices behaves differently to different inputs and its response which depends on various factors needs proper investigation. The use of Linear Graph Theory is significant in power system studies as it proves to be an excellent mathematical tool for deriving the representations of the electrical transmission network.

This paper presents the modelling of standard test system using graph theoretical concepts and thereby formulating network equations using different reference frames. The approach used provides an easy analytical solution if applied to bulky power networks in real time.

Keywords: Graph Theory, Power Systems, Modelling, Topology

1. INTRODUCTION

   Graph Theory is a significant offshoot of Mathematics with wide range of applications in various domains [1]. Nowadays, Power Engineering and Graph theory combination has set a stage for the solution of large power networks. With the evolution of large, high speed digital computers there is a paradigm shift in the techniques used for solving large power networks. Digital computer solutions depend upon network equations formulated using graph theory.

   The growing interest of Graph theory in Power Engineering is due to its application in the analysis and design of electrical networks for predicting its behaviour. A complex electrical network is an interconnection of various electrical elements or devices such as resistors, inductors, capacitors, power sources, diodes, transistors, power electronic switches, storage batteries, transformers, protective devices etc. The behaviour of these elements or devices depends on various factors like characteristics of each element in the network and their topology. i.e., how the elements are connected together in the network. These elements present in the network can be classified into different categories as one-port (two terminal elements) or multiport elements, passive or active elements, linear or non-linear elements, lumped or distributed elements, time variant or time invariant elements, bilateral or unilateral elements, bipolar or unipolar elements, dependent or independent sources etc. In power system studies the electric transmission network with the interconnection of transmission lines, transformers, shunt reactors, Shunt capacitors can be modelled as a network of lumped, two terminal elements. Few potential applications of graph theory in power systems [2][3] which exist in the literature proves that linear graph theory can be an excellent and useful mathematical tool in deriving the representations of the electrical transmission network.

   This paper presents the modelling of Standard Test System using graph theoretical concepts. Topological analysis of the electrical network is carried out to formulate network equations using different reference frames.

   The paper is organized as follows. Section II reviews graph theory fundamentals. Elementary concepts of power system and standard test systems for modern power system analysis are discussed in Section III. Section IV presents the proposed network model formulation for a standard test system. Finally, Section V summarizes the work.

2. GRAPH THEORY FUNDAMENTALS

   Graphs are useful in describing the topological properties of network. Network topology is a generalized approach in solving electric circuits which deals with the properties of a geometrical Figure which are unaffected when the Figure is physically distorted. The geometrical properties of a network are independent of the types of elements & their values. Each element in the network can be represented by line segments with dots at the ends, irrespective of its nature & value. The configuration thus obtained when all the elements in a network are replaced by lines with circles or dots at both ends is called the graph of the network.

   The terminologies are used in network graph are as follows:

   Branch: A line segment representing one network element or a combination of elements connected between two points is called a branch

   Node: The point of intersection of two or more branches is called a node.

   Degree of a Node: It indicates the number of branches incident to the node.

   Tree: A tree is a subgraph of a graph without loops. A network can have several trees.

   Twig: It is the branch of a tree

   Chord: It is the branch of the graph that does not belong to a particular tree. It is also called link.

   Co-Tree: The set of links removed to form a tree constitute a co-tree.

   Loop: Loop is the closed contour selected in a graph.

   Cut-Set: It is the set of elements or branches of a graph that separates two main parts of a network.

   Tie Set: Tie set is a set of branches contained in a loop. Each loop consists of a tree and a link

   Incidence Matrix: Any directed graph can be described completely in a compact matrix form. Incidence matrix gives information about which branch is connected to which node.

   If any row is deleted from a complete incident matrix the resulting matrix is called reduced incidence matrix.

   Relation Between Twigs and Links:

   The number of twigs on a tree is always one less than the number of nodes. In a graph with N nodes, the number of tree branches or twigs T is given by

   T= N-1 (1)

   The number of links L is given by

   L = B – T = B- (N-1) = B-N + 1 (2)

   where B represents total number of branches in a graph

   A sample electrical network is shown below in Fig.1 with its directed graph in Fig.2.A graph may have many different trees. On such tree is given in Fig.3 with twigs and chords represented by bold and dotted lines respectively.

   The complete incidence matrix [Ai] of Fig.4 is shown below.

   The reduced incidence matrix is obtained after deleting node (4) such that 4th row is removed from the above matrix.

   The reduced incidence matrix [A] of the Fig.4 is given below.

   Branch and Node are also called Edge and Vertex respectively in graph theory. The two terminal electrical element represented by edge (ek) is associated with two edge variables edge voltage or cross variable vk(t) and edge current or through variable ik(t). These variables are directional, so every edge i.e, branch is assigned an arbitrary direction. In general, to analyse a network using graph theoretical principles, network variables are considered on voltage basis or on current basis.

   The graph can be directed (oriented) or undirected, planar or non-planar. A graph is said to be directed when all its nodes are named, all its branches are numbered and arbitrary orientations are assigned to the branches. The arbitrary orientation in the graph indicate the direction of branch currents.

3. POWER SYSTEMS AND STANDARD TEST SYSTEMS

Power system in general is a sophisticated system with a number of power stations of various types, interconnected by a system transmission lines & distribution network to supply different loads as per the consumer interest. Todays power networks are highly complicated with several buses interconnected by means of transmission lines. Power is injected int a bus from generators while the loads are tapped from it. In a power network there may be buses with only generators and no load or vice versa.

Different test systems, IEEE and CIGRE benchmarks have been used for power system analysis. These systems are available from small to large scale at various voltage and power levels. The benchmarks can be used for analysis of power system reliability, stability, protection, power quality, marketing, planning, observability, optimization etc. [4]

An overview of available standard test systems is given in the Table.1 below [4]

TABLE 1: AN OVERVIEW OF STANDARD TEST SYSTEMS
TEST SYSTEM	VOLTAGE (KV)	AC/DC	NUMBER OF BUSES	NUMBER OF GENERATORS	LOAD (MW, MVAR)	COMMON APPLICATION	TIME OF INTEREST FOR THE MOST COMMONLY USED APPLICATION
IEEE 9	13.8,16.5,18 and 230	AC	9	3	315, 115	Stability	From milliseconds to several seconds
IEEE 14	13.8,18 and 69	AC	14	5	259, 73.5	State Estimation
IEEE 30	33,132	AC	30	6	283.4, 126.2	Planning	From a few hours to several years
IEEE 39	345	AC	39	10	6097, 1409	Stability	From milliseconds to several seconds
IEEE 57	138, 345	AC	57	7	1251, 336.4	State Estimation
IEEE 118	138, 345	AC	118	19	3668, 1438	Planning	From a few hours to several years
IEEE 300	138, 230 and 345	AC	300	69		State Estimation

IEEE RTS-24	230, 138	AC	24	32	3405, NA	Reliability	From a few minutes to several years
RBTS	230	AC	6	11	240, NA	Reliability	From several minutes to several years
CIGRE B4 DC	±400, ±200,380 and 145	DC			7500, NA	New Technologies	From milliseconds to minutes
CIGRE MV	20	AC	14	UTILITY	-43	Control	From milliseconds to seconds
CIGRE LV	0.4	AC		UTILITY		New Technologies	From milliseconds to minutes
CIGRE 32	130,220 and 400	AC/dc	74	20	11060, NA	Control	From milliseconds to seconds
CIGRE HVDC	345, 230	DC	2	TWO UTILITY	1000(BASE)	Stability/Control	From milliseconds to seconds
NA-Not Applicable

For power system studies of a real time large networks, it is essential to proceed systematically by first formulating the network model of the systems.

IV. NETWORK MODEL FORMULATION OF TEST SYSTEM

Standard IEEE 9 bus test system is considered for the application of graph theoretical concepts

. A single line diagram of the standard IEEE 9 bus test system is shown below in Fig.5. [4]

The geometrical interconnection of the elements of the network shown in Fig.5 is depicted in the Fig.6.below. Each bus is represented by a node and each element between buses i.e., transformer or transmission line is replaced by a single line segment.

Modelling of network elements:

In general, transmission lines are modelled by the nominal model with series impedance of the line as ZL= RL+ jXL and half line charging admittances as yc / 2. A transformer equivalent circuit will be a series impedance if shunt branch of the transformer is neglected. Between buses a transformer can be modelled as a line with admittance Yt =1/(Rt+ jXt ).The load at a particular ith bus can be modelled by an equivalent admittance YLi =( PLi jQLi ) / | Vi |2, where Vi is the ith bus voltage. Generators can be modelled as a voltage source or as a current source with generator admittance YG. Also any shunt element can be modelled as a line with admittance ysh.

Power networks are structured in such a way that out of m total number of nodes, one node is normally described by zero is always at ground potential and the remaining n = m -1 nodes are the buses. Considering the arbitrary directions, the oriented graph of the network shown in Fig.5 is given below with node v0 at ground potential.

The branch-node incidence matrix of the graph shown in Fig.7 is given below.

The bus incidence matrix Abi can be obtained by deleting the first row corresponding to reference node 0. The dimensions of Abi are (m-1) x e, where e =12 & n= m-1=9

The rows of matrix [Abi ] gives Kirchhoffs current law equations for example

i1 + i2 +i3 – i4 = 0 (3)

Similarly, for other rows KCL equations can be obtained. In matrix form,

[ Abi ] [ Ibr ] = 0 (4)

where [Ibr] is a vector of branch currents of the order (12×1)

The branch voltages for the above network can be written as

Ve = [Abi ]T Ebus (5)

where Ve is a vector of branch voltages of the order 12×1 Ebus is a vector of node or bus voltages of the order 9×1.

The network equations derived from the above relation gives branch voltages in terms of the node voltages. For example,

V1= E1 (6)

V4 = E4 – E1 (7)

Different frames of reference can be considered to formulate the network equations of the above graph shown in Fig.7.

In Bus Frame of Reference there are n independent equations (n = no. of buses) relating the bus vectors of currents and voltages through the bus impedance matrix and bus admittance matrix

Ebus= Zbus Ibus (8)

Ibus = Ybus Ebus (9)

In Branch Frame of Reference there are b independent equations (b = no. of branches of a selected Tree of the system Graph) relating the branch vetors of currents and voltages through the branch impedance matrix and branch admittance matrix:

Ebr= Zbr Ibr (10)

Ibr = Ybr Ebr (11)

Similarly, in Loop Frame of Reference there are loop voltages & loop currents as vectors relating the impedance and admittance matrix.

Eloop= Zloop Iloop (12)

Iloop = Yloop Eloop (13)

Thus, using the network variables in any frame of reference the matrix pair [Y] and [Z] can be determined which forms the basis network models for power system studies.[5][6]

V. CONCLUSION

In this paper the application of graph theoretical principles in the analysis of a power network has been discussed. The modelling of Standard IEEE Test System is carried out using graph theoretical concepts. Matrix representation is obtained from the graph, using which relations between various parameters of the

network are analysed. The same approach can be applied to large scale power networks in real time to obtain a simple analytical solution.

REFERENCES

[1] Xie, Baozhuo, Chao Qi, Hongqi Ben, and Weixiong Yu. "The applications of graph theory in electric network." In 2019 International Conference on Sensing, Diagnostics, Prognostics, and Control (SDPC), pp. 780-784. IEEE, 2019.

[2] Kerur, Mr Prakash, and R. L. Chakrasali. "Graph Theory Algorithm to Find Minimum Cost Power Flow Path in Deregulated Scenario under Line Outage Contingency." International Journal of Applied Engineering Research 15, no. 7 (2020): 755-761.

[3] Saharuddin, Nur Zawani, Izham Zainal Abidin, Hazlie Mokhlis, Abdul Rahim Abdullah, and Kanendra Naidu. "A power system network splitting strategy based on contingency analysis." Energies 11, no. 2 (2018): 434.

[4] Peyghami, Saeed, Pooya Davari, Mahmud Fotuhi-Firuzabad, and Frede Blaabjerg. "Standard test systems for modern power system analysis: An overview." IEEE Industrial Electronics Magazine 13, no. 4 (2019): 86-105.

[5] Sayeekumar, Nandhini, S. Prabhakar Karthikeyan, Sarat Kumar Sahoo, and I. Jacob Raglend. "Graph theory and its applications in power systems-a review." In 2015 International Conference on Control, Instrumentation, Communication and Computational Technologies (ICCICCT), pp. 154-157. IEEE, 2015.

[6] Quirós-Tortós, Jairo, and Vladimir Terzija. "A graph theory based new approach for power system restoration." In 2013 IEEE Grenoble Conference, pp. 1-6. IEEE, 2013.