
Citation 
 Permanent Link:
 http://digital.auraria.edu/AA00000011/00001
Material Information
 Title:
 Consensus algorithm in smart grid and communication networks
 Creator:
 Alfagee, Husain Abdulaziz ( author )
 Place of Publication:
 Denver, CO
 Publisher:
 University of Colorado Denver
 Publication Date:
 2013
 Language:
 English
 Physical Description:
 1 electronic file. : ;
Thesis/Dissertation Information
 Degree:
 Master's ( Master of science)
 Degree Grantor:
 University of Colorado Denver
 Degree Divisions:
 Department of Electrical Engineering, CU Denver
 Degree Disciplines:
 Electrical engineering
Subjects
 Subjects / Keywords:
 Consensus (Social sciences) ( lcsh )
Smart power grids ( lcsh ) Consensus (Social sciences) ( fast ) Smart power grids ( fast )
 Genre:
 bibliography ( marcgt )
theses ( marcgt ) nonfiction ( marcgt )
Notes
 Review:
 On a daily basis, consensus theory attracts more and more researches from different areas of interest, to apply its techniques to solve technical problems in a way that is faster, more reliable, and even more precise than ever before. A power system network is one of those fields that consensus theory employs extensively. The use of the consensus algorithm to solve the Economic Dispatch and Load Restoration Problems is a good example. Instead of a conventional central controller, some researchers have explored an algorithm to solve the above mentioned problems, in a distribution manner, using the consensus algorithm, which is based on calculation methods, i.e., non estimation methods, for updating the information consensus matrix. Starting from this point of solving these types of problems mentioned, specifically, in a distribution fashion, using the consensus algorithm, we have implemented a new advanced consensus algorithm. It is based on the adaptive estimation techniques, such as the Gradient Algorithm and the Recursive Least Square Algorithm, to solve the same problems. This advanced work was tested on different case studies that had formerly been explored, as seen in references 5, 7, and 18. Three and five generators, or agents, with different topologies, correspond to the Economic Dispatch Problem and the IEEE 16Bus power system corresponds to the Load Restoration Problem. In all the cases we have studied, the results met our expectations with extreme accuracy, and completely matched the results of the previous researchers. There is little question that this research proves the capability and dependability of using the consensus algorithm, based on the estimation methods as the Gradient Algorithm and the Recursive Least Square Algorithm to solve such power problems.
 Thesis:
 Thesis (M.S.)University of Colorado Denver. Electrical engineering
 Bibliography:
 Includes bibliographic references.
 System Details:
 System requirements: Adobe Reader.
 General Note:
 Department of Electrical Engineering
 Statement of Responsibility:
 by Husain Abdulaziz Alfagee.
Record Information
 Source Institution:
 University of Colorado Denver
 Holding Location:
 Auraria Library
 Rights Management:
 All applicable rights reserved by the source institution and holding location.
 Resource Identifier:
 879382893 ( OCLC )
ocn879382893

Downloads 
This item has the following downloads:

Full Text 
CONSENSUS ALGORITHM IN
SMART GRID AND COMMUNICATION NETWORKS
by
HUSAIN ABDULAZIZ ALFAGEE
B.S.E.E, Higher Institute of Engineering, 1998
A thesis submitted to the
Faculty of Graduate School of the
University of Colorado in partial fulfillment
of the requirements for the degree of
Master of Science
Electrical Engineering
2013
This thesis for the Master of Science degree by
Husain Abdulaziz Alfagee
has been approved for the Electrical Engineering Program
by
Miloje Radenkovic, Chair
Mark Golkowski
Sam Welch
June 20, 2013
n
Alfagee, Husain Abdulaziz (M.S., Electrical Engineering)
Consensus Algorithm in Smart Grid and Communication Networks.
Thesis directed by Professor Miloje Radenkovic
ABSTRACT
On a daily basis, consensus theory attracts more and more researches from
different areas of interest, to apply its techniques to solve technical problems in a way
that is faster, more reliable, and even more precise than ever before. A power system
network is one of those fields that consensus theory employs extensively. The use of the
consensus algorithm to solve the Economic Dispatch and Load Restoration Problems is a
good example. Instead of a conventional central controller, some researchers have
explored an algorithm to solve the above mentioned problems, in a distribution manner,
using the consensus algorithm, which is based on calculation methods, i.e., non
estimation methods, for updating the information consensus matrix.
Starting from this point of solving these types of problems mentioned,
specifically, in a distribution fashion, using the consensus algorithm, we have
implemented a new advanced consensus algorithm. It is based on the adaptive estimation
techniques, such as the Gradient Algorithm and the Recursive Least Square Algorithm, to
solve the same problems. This advanced work was tested on different case studies that
had formerly been explored, as seen in references 5, 7, and 18. Three and five generators,
or agents, with different topologies, correspond to the Economic Dispatch Problem and
the IEEE 16Bus power system corresponds to the Load Restoration Problem.
m
In all the cases we have studied, the results met our expectations with extreme
accuracy, and completely matched the results of the previous researchers. There is little
question that this research proves the capability and dependability of using the consensus
algorithm, based on the estimation methods as the Gradient Algorithm and the Recursive
Least Square Algorithm to solve such power problems.
The form and content of this abstract are approved. I recommend its publication.
Approved: Miloje Radenkovic
IV
DEDICATION
I lovingly dedicate this thesis to my parents, who gave me an appreciation of
learning and taught me the value of perseverance and resolve. I also dedicate this thesis to
my wife for her unfaltering support and understanding while I was doing my Masters.
v
ACKNOWLEDGEMENT
My special thanks to my advisor, Prof. Miloje Radenkovic, for his contribution
and support to my research. I also wish to thank all the members of my committee for
their valuable participation and insights.
vi
CONTENTS
Figures........................................................................ x
Tables......................................................................... xii
Chapter
1. Introduction................................................................. 1
1.1 Thesis Objectives............................................................ 4
1.2 Thesis Organization.......................................................... 5
2. Graph and Consensus Theory................................................... 7
2.1 Graph Theory................................................................ 7
2.1.1 Graph Definition........................................................... 9
2.1.2 Directed and Undirected Graph............................................. 10
2.1.3 Connected and Disconnected Graph.......................................... 11
2.1.4 Incidence and Adjacency Matrices.......................................... 11
2.2 Consensus Theory........................................................... 13
2.2.1 Consensus Definition...................................................... 13
2.2.2 Consensus in Networks..................................................... 13
2.3 Consensus Algorithm Applications........................................... 16
3. Economic Dispatch and Load Restoration Problems............................. 18
3.1 Economic Dispatch Problem................................................... 18
3.2 Load Restoration Problem................................................... 20
3.3 Estimation Information Matrix in the Consensus Algorithm.................. 22
3.4.1 Gradient Algorithm Estimation Form........................................ 23
3.4.2 Recursive Least Square Algorithm Estimation Form.......................... 24
4. Study Cases and Results..................................................... 25
vii
4.1 Three Generators System for Economic Dispatch Problem....................... 25
4.1.1 Three Generators System with New Estimation Method using Gradient Algorithm
without Power Constraints................................................. 26
4.1.2 Three Generators System with New Estimation Method using Gradient Algorithm
with Power Constraints.................................................... 27
4.2 Five Generators System for Economic Dispatch Problem...................... 28
4.2.1 Five Generators System with New Estimation Method using Gradient Algorithm
........................................................................ 29
4.2.1.1 Five Generators using GA; Guessing Initial Values dy = dy =0.0......... 30
4.2.1.2 Five Generators using GA; Guessing Initial Values dy = dy A 0.0........ 31
4.2.1.3 Five Generators using GA; Guessing Initial Values dy A dy A 0.0........ 32
4.2.2 Five Generators System with New Estimation Method using Recursive Least
Square Algorithm........................................................ 33
4.2.2.1 Five Generators using RLS; Guessing Initial Values dy = dy = 0.0....... 34
4.2.2.2 Five Generators using RLS; Guessing Initial Values dy = dy A 0.0....... 35
4.2.2.3 Five Generators using RLS; Guessing Initial Values dy A dy A 0.0....... 36
4.2.3 Five Generators System with New Estimation Method using GA and RLS where
the System Topology Changes with Time................................... 37
4.2.4 Five Generators System with New Estimation Method using GA and Two Agents
4 and 5 are Become Disconnected......................................... 39
4.2.5 Five Generators System with New Estimation Method using RLS and Check the
Necessity of Reaching Consensus......................................... 42
4.3 IEEE 16Bus Test Power System for Load Restoration Problem................ 45
4.3.1 IEEE 16Bus Test Power System with New Estimation Method using GA and 01
Knapsack Value Based.................................................... 50
4.3.2 IEEE 16Bus Test Power System with New Estimation Method using GA and 01
Knapsack Density Based.................................................. 52
5. Conclusion and Future Work ................................................. 54
viii
5.1 Conclusion .............................................................. 54
5.2 Future Work ............................................................. 55
References ................................................................... 56
Appendix
A.l Derivation of Recursive Least Square Algorithm Estimation (RLS) .......... 60
A.2 Derivation of Gradient Algorithm Estimation (GA) ........................ 61
A.3 Basic Flowchart for the Estimation Algorithms (RLS and GA) ............... 62
IX
FIGURES
Figure
1.1 (a) Central control, and (b) distributed control connections.................... 3
2.1 Bridges of Konigsberg City (1736).............................................. 7
2.2 The Four regions and seven bridges in Konigsberg City.......................... 8
2.3 Eulerian Circuit................................................................ 8
2.4 Three generators (agents) system................................................ 9
2.5 Directed graph................................................................. 10
2.6 (a) Connected graph, and (b) disconnected graph................................ 11
2.7 (a) Adjacent vertices, and (b) adjacent edges.................................. 11
4.1 Three generators using GA; ICs and power (no power constraints)............ 26
4.2 Three generators using GA; ICs and power (with power constraints).......... 27
4.3 Five generators; different system topologies................................... 29
4.4 Five generators using GA; ICs and power (d;j = dji = 0.0).................... 30
4.5 Five generators using GA; ICs and power (d;j = dji ^ 0.0).................... 31
4.6 Five generators using GA; ICs and power (d;j ^ dji ^ 0.0).................... 32
4.7 Five generators using RLS; ICs and power (d;j = dji = 0.0)................... 34
4.8 Five generators using RLS; ICs and power (d;j = dji ^ 0.0)................... 35
4.9 Five generators using RLS; ICs and power (d;j ^ dji ^ 0.0)................... 36
4.10 Five generators; changing sequence of system topology.......................... 38
4.11 Five generators using GA; ICs and power (topology changes with time).......... 38
4.12 Five generators using RLS; ICs and power (topology changes with time)........ 39
4.13 Five generators; agents 4 and 5 become disconnected........................... 40
4.14 Five generators using GA; ICs and power (two agents 4 and 5 become
disconnected)............................................................... 41
x
4.15 Five generators; changing sequence of system topology........................ 42
4.16 Five generators using RLS; ICs and power (P0 = 0.01)........................ 43
4.17 Five generators; adjacency rows and columns summation (P0 = 0.01)........... 43
4.18 Five generators using RLS; ICs and power (P0 = 10).......................... 44
4.19 Five generators; adjacency rows and columns summation (P0 =10).............. 44
4.20 The 16bus test system (source ref. [18]).................................... 45
4.21 The 16bus system; post fault configuration (source ref. [18])............... 47
4.22 The 16bus system; after fault configuration (source ref. [18]).............. 49
4.23 The 16bus system; information matrixM convergence.......................... 50
4.24 The 16bus system; total net power convergence (knapsack value based)........ 50
4.25 The 16bus system; information matrixM convergence.......................... 52
4.26 The 16bus system; total net power convergence (knapsack density based)...... 52
A. 1 Flowchart of solving EDP based on new estimation algorithms................... 62
xi
TABLES
Table
4.1 Three generators; system parameters .......................................... 25
4.2 Five generators; system parameters ........................................... 28
4.3 16Bus power system; system data .............................................. 46
4.4 16Bus power system; final converged of information matrixM .................. 48
xii
1. Introduction
For more than half of a century, the existing US power grid has been providing its
electric power to a wide range of customers. In fact, this system faced substantial
magnitudes of challenges that were not taken into account at the time the design was
originated. These challenges can be summarized in accordance with the following:
lack of supporting the distributed generation.
renewable energy sources which are being added to the power grid.
lack of flexibility and adaptability.
natural disasters.
human operating errors.
For all of the above reasons, and to assure that the power grid will continue to
provide the demanded power to its consumers as needed, the power grid should be
efficient and smart enough to deal with all demeanors of ongoing and varying changes of
the system topology without losing its stability, availability, et cetera.
In order to make a power system network effective and smart enough, it should
implement a communication network and a control network that integrate and
complement the future power system, where the system is called the LargeScale
Network Control System (LSNCS) [4][5], There is no doubt that the LSNCS will be a
necessity for the next series of power networks. This refers to a specific means and
existence of a large number of subsystems. In this bulk system, the conventional control
schematic will face severe challenges that will inevitably affect its controllability. These
challenges can be summarized in the following factors [5]:
requirement of a high level of connectivity to achieve the optimal operation
1
condition.
sensitivity to failures and modeling errors.
affect of a variety of the configurations, such as PlugandPlay of the power grid
topology which will make the smart grid topology unknown or undefined.
To overcome the drawbacks of conventional control, distribution control is more
convenient for solving the identified problems. The main task for using distribution
control algorithms is to make sure all system agents, or nodes, reach what is called the
consensus. Several areas, where the consensus algorithm is applied, can be used in the
improvement of the power system. For example, the consensus algorithm of a multi
vehicle system, where a vehicle is able to communicate with other vehicles upon a
communication network system, is a good example [2], Therefore, to control this
LSNCS smart grid, a very strong algorithm has to be implemented in order to work
correctly in the existence of a lack of or unreliable communication capability; this applies
even with loss of the central control topology. Such an algorithm has to be tested in areas
that resemble LSNCS, as would the Economic Dispatch Problem and the Load
Restoration Problem.
To illustrate the idea of the central and distribution control, let us consider the
five buses power system, where each bus has its load and generated power as it is
shown in Figure 1.1 on the next page.
2
(a) (b)
Figure 1.1: (a) Central controller, and (b) Distributed controller
The communication topology could be a conventional central controller, as shown
in Figure 1.1(a), or a distributed controller as in Figure 1.1(b). In Figure 1.1(b), generator
one has been selected as the consensus leader. The local controller, in each bus, will keep
reporting its status to the leader. Based on the collected information, the leader will
decide whether to increase or decrease the group of the consensus variable, according to
the situation of a required condition [5], The entire process mentioned is manipulated by
the consensus algorithm.
The consensus algorithm is used to solve some fundamental problems of the
power system, as the Economic Dispatch problem and the Load Restoration problem.
Instead of the conventional central controller, Some researchers had explored consensus
algorithms to solve the mentioned problems in a distribution manner [5][8][18], The main
reason of using the distribution fashion is to overcome the drawbacks of the central
controller.
Staring from the point of solving the economic dispatch, and the load restoration
problems in a distribution fashion, by using the consensus algorithm, we have
implemented a new advanced consensus algorithm based on the adaptive estimation
techniques of the Gradient Algorithm and the Recursive Least Square Algorithm to solve
the same problems. This advanced work is tested on different case studies that are
3
proposed in the references [5][7][18] to ascertain the sets of comparativelysourced
results do coincide and are depicted accurately. These case studies, and their results, are
presented in details in the Chapter 4. No doubt, this research proves the capability and
dependability of using the consensus algorithm, based on the estimation methods, citing
specifically, the Gradient Algorithm and the Recursive Least Square Algorithm to solve
such power problems.
Briefly, our research objectives outlining this thesis are summarized in the
following section:
1.1 Thesis Objectives
To fulfill the goals of this research, a set of objectives was specified inclusive in this
work. These objectives are summarized in the following points:
1. Implementing a Matlab code to solve the Economic Dispatch Problem for the
previous case studies that were focused on in the reference [5] without the power
constraints and fulfilling the same results.
2. Implementing a Matlab code to solve the Economic Dispatch Problem and taking
into account the power constraints in order to fulfill the power limitations, i.e., a
condition that was mentioned in Reference [7],
3. Implementing a new Matlab code to solve the Economic Dispatch Problem in the
same case studies addressing objectives 1 and 2; but this time by applying a new
estimation method using the Gradient Algorithm and fulfilling the same results in
objectives 1 and 2.
4. Implementing a new Matlab code to solve the Economic Dispatch Problem in the
same case studies in objectives 1 and 2; but this time by applying a new
4
estimation method using the Recursive Least Square Algorithm and fulfilling the
same results in objectives 1 and 2.
5. Repeating objectives 3 and 4 to study the case where the system topology changes
with time.
6. Implementing a Matlab code to solve the Economic Dispatch Problem to study
the case if some agents are found to be disconnected.
7. Implementing a Matlab code to solve the Load Restoration Problem for the case
study that was presented in reference [18] and fulfilling the same results.
8. Implementing a new Matlab code to solve the Load Restoration Problem in the
same case in objective 7; but this time by applying the new estimation method
using the Gradient Algorithm and obtaining the same results in objective 7.
1.2 Thesis Organization
The remainder of this thesis is organized and described in methodologies as
follows:
Chapter 2: provides a very important background about the graph and consensus
theories in the networks; the consensus mathematical model is presented in this
chapter
Chapter 3: presents one of the very useful applications of the consensus theory,
which is solving the economic dispatch and the load restoration problems in a
distributed manner; the mathematical model of the new consensus estimation
method is presented in this chapter, as well
Chapter 4: presents the study cases, and their respective results, of the estimation
methods to solve the economic dispatch and the load restoration problems; also, it
5
contains notes and comments in direct reference and concern to the results
Chapter 5: thesis conclusions and recommendations for future studies are
presented in this chapter, which is the last chapter of the thesis
In the following chapter, the thesis starts with an introduction about the graph and
the consensus theory.
6
2. Graph and Consensus Theory
Before going in the details of the consensus theory, there is an important concept
which must be clearly understandable. This concept is called the Graph.
2.1 Graph Theory
If we look around us in the real world, there are many situations that can be easily
described or converted to a diagram which consists of a set of points, called vertices,
together with lines, called edges, which connect or join certain pairs of the points within
the diagrams. For instant, the subway system, where the points could represent the stop
stations, and the edges represent the rails that connect these stations. The mathematical
concept of a situation of such a case provides the idea of what is called a Graph.
The principle of the Graph was born from the idea of the Konigsberg Bridge
Problem. The Pregel River in Prussia divided the city of Konigsberg into four separate
regions which were connected by seven bridges as shown in Figure 2.1 below.
Figure 2.1: Bridges of Konigsberg city (1736)
7
A simple diagram of the bridges in the city is illustrated in Figure 2.2 below.
Figure 2.2: The Four regions and seven bridges in the Konigsberg city
The inhabitants of the city wondered if it were possible to leave home, cross each
of the seven bridges only once, and return home. The Leonhard Euler, a Swiss
mathematician, (17071783), took the puzzle and tried to apply a mathematical method to
solve the problem. He redrew each region as a vertex and each bridge as an edge
connected vertices corresponding to the regions, as shown in Figure 2.3.
Figure 2.3 shows the Graph that encodes all necessary information from Figure
2.2. It is called the Eulerian circuit. Many consider the Eulers method to be the birth of
the Graph theory [1][9][11],
8
2.1.1 Graph Definition
The Graph G is defined as a structure which consists a vertex set V(G), and an
edge set E(G), and a relation that associates with each edge whose two vertices are called
the endpoints. This graph is used to model the system topology of the network. The graph
G = (V, E) where V = {1,2, ...,n} is called the vertices or the nodes. E Q V x Vis called
the edges which is a set of unordered pairs of distinct vertices. When the two vertices 1, 2
in V(G) are endpoints of an edge, both 1 and 2 are called adjacent [1],
In the real world, Graph G can be an electric circuit where vertices represent
sources, diodes, capacitors, et cetera, and edges represent the wires that connect them. It
can be a computer network where vertices represent computers, and edges represent the
communication network that connects them together. It can be the World Wide Web,
where vertices represent the WebPages, and edges represent the hyperlinks, and so on. In
this research, the graph is an electric power grid where the vertices represent the power
generators or loads, and the edges represent the communication network that connects
them as illustrated in Figure 2.4 below, specifically, for the three generators case study. It
is an unordered, an undirected, and unweighted graph.
Figure 2.4: Three generators (agents) system
9
2.1.2 Directed and Undirected Graph
As was mentioned, Graph G is a mathematical structure consists of a set of
vertices V(G), and a set of edges E(G), which connect the vertices according to an
associated relationship. This mathematical structure can be a directed or an undirected
graph. In the undirected graph, the edges that connect the vertices are not directionally
fixed. The direction form a node n, to a node n, is represented by a line, with or without,
arrowhead in both line ends, as seen in Figure 2.4 on the previous page. On the other
hand, in the directed graph, also referred to as the digraph, the edge that connects two
vertices is directed, or ordered, to gravitate in a specific direction from a node nu or the
tail node, to a node called the head node. The edge direction can be easily recognized
by the arrowhead that always points to the head node as illustrated in Figure 2.5 below.
Figure 2.5: Directed graph
Formally; G = (V,E) where V = {1,2, and E Â£ y x V .
Assuming that u and w are end points then:
G =
(V,E) will be j
undirected
directed
if for allu,w Â£ V, i. e (it, w) Â£ E <=> (w, u) Â£ E
otherwise
10
2.1.3 A Connected and Disconnected Graph
The Graph G is a connected graph if, between every two vertices in the V(G),
there is a path linking them, otherwise the Graph G is called a disconnected graph. In
other words, the graph is disconnected if its vertex set can be divided into two nonempty
subsets where no edge connects them [10], Figure 2.6 below illustrates the two types.
(a)
Figure 2.6: (a) A connected graph, and (b) a disconnected graph
2.1.4 An Incidence and Adjacency Matrices
In the graph G, when the edge e joins or connects the two vertices 1 and 2, these
two vertices are called the adjacent. In the same time, both 1 and 2 are called the incident
to the edge e. Likewise, in the graph G, two edges are adjacent if they have a vertex in
common as it is shown in Figure 2.7 below.
3
1 e 2
(a)
Figure 2.7: (a) Adjacent vertices, and (b) adjacent edges
11
Thus, based on the previous description, a pertinent question is raised. Are the
graphs, as they are in diagram form, suitable for the computer calculations or the
mathematical models to study their properties? The answer is no. Because of this, these
two matrices are considered critical matrices. They are the incidence matrix and the
adjacency matrix. Both of them are associated with the graph.
The incidence matrix of a graph G is n m matrix Mg := (mve), where mve is the
number of times (0,1, or 2) that a vertex v and an edge e are incident.
The adjacent matrix of a graph G is n n matrix Ac, := (auv), where auv is the
number of edges that join vertices u and v.
Both the incidence and the adjacency matrices of the graph G in Figure 2.6 (a) can be
built as follows:
The incidence matrix; M7xll =
The adjacency matrix; Ajxj =
T 0 0 0 1 1 0 0 0 0 0
1 1 0 0 0 0 1 0 0 0 0
0 1 1 0 0 0 0 0 0 0 1
0 0 1 1 0 0 0 0 1 1 0
0 0 0 1 1 0 0 1 0 0 0
0 0 0 0 0 1 0 1 1 0 0
0 0 0 0 0 0 1 0 0 1 lJ
r0 1 0 0 1 1 0
1 0 1 0 0 0 1
0 1 0 1 0 0 1
0 0 1 0 1 1 1
1 0 0 1 0 1 0
1 0 0 1 1 0 0
L0 1 1 1 0 0 oJ
It is easily apparent to notice that the adjacency matrix is much smaller than the
incidence matrix because usually graphs have more edges than vertices. This causes the
adjacency matrix to require less storage computer capability which is preferred in the
computer programs where the consensus algorithm is applied [10],
12
2.2 Consensus Theory
As mentioned, the concept of the consensus is an area of interest from many
researchers in different fields of a study. To illustrate the idea of the consensus, let us
consider a system of three decisionmaking units where each unit can be known as an
agent, or a generator as shown in Figure 2.4. Each agent has two parts: first part is the
local controller and the second part is the consensus manager. The local controller
collects system data and reports its own condition, or state, to the consensus manager.
The mission of the consensus manager is to analyze this information and negotiates it
with other connected neighborhood agents via the communication system. As result, the
consensus manager will pass the decision back to the local controller. The local controller
will update its situation depending on the received information and report back its new
condition to the consensus manager again in a reciprocal, or backandforth process.
2.2.1 Consensus Definition
In a network of multiagents, a Consensus means to reach an agreement
regarding a certain quantity of an interest, depending on the state of all agents. A
Consensus Algorithm, or a protocol, is an interaction rule that specifies the
information exchange between an agent and all its neighbors in the same network [2],
2.2.2 Consensus in Networks
The topology of the system in Figure 2.4 can be represented using undirected
graph G = (V,E) where V = {1,2, and E Â£ y x V, whereas this graph can be
described as using the adjacency matrix A as mentioned prior, of a finite system of n
nodes. The adjacency matrix A is n x n matrix that depends on the number of the agents.
The offdiagonal entry atl is the number of edges from node i to node j. If a(/ ^ 0 i A j
13
then the agent ith is communicating with the agent jth. In our case of a simple finite graph,
the adjacency matrix is only a (0, l)matrix with zeros on its diagonal. The neighbors of
ith agent are denoted by: JVj = [j G V (i,j) EE}.
For our system, the ith node has xt G R that denotes the state value it possess. The
state Xj of a node can be a physical quantity, such as voltage, current, power, incremental
cost, et cetera. It can be said that the system nodes, generators, or agents, have reached
the consensus state if, and only if, the state value of ith node is equal the state value of jth
node for all i ,j [3], i.e
xt = Xj for all i ,j (2.1)
The information discovery process for agent i is presented as follows:
xk+i xk + aij(xjk xtk ) i = 1,2, ...n (2.2)
Where:
xk+1, xk : are the discovered information by agent i (like average net power)
JVj : is the neighbors that are connected to the agent i
atj : is the coefficient for information exchange between neighboring agents i and j
_ (0 < atj <1 if agent i and j are connected
lJ { 0 otherwise
The information discovery process for the whole system is formed using matrix format as
follows:
xk+i =xk + A* Xk (2.3)
Xk+1 = (/ + A)Xk (2.4)
Xk+1 = DXk (2.5)
14
Where:
yk k k1 A, Â£ ... f Aft J
ill ill al n i
hi iii % " 1 'LjENiaij Ml IH ( HI ain in
^1 dni 1 ~'LjENiaij
The D matrix is called the information discovery matrix, or sparse iteration matrix, for
the system [18],
The coefficients atj in matrix D have to be properly designed, because they play a
critical role in reaching consensus of a system. For instant, a fullyconnected system can
reach consensus in one step if atj is selected to be equal where n is the number of the
system nodes. However, most of the systems are usually not fullyconnected where they
can suffer from loss of their connection lines.
Different methods are used to compute matrix D based on computing the
coefficients a(/. Some of those methods are summarized in the following:
The Uniform Method: the weights are fixed and computed according the equation
(2.6). The drawbacks of this method are the loss of the adaptivity and the slow
convergence.
a,
(2.6)
The Metropolis Method: it is an improved method to accommodate the changes of
system configuration which guarantees the stability of the information discovery
15
process. The weights are updated according the equation (2.7) below.
a,
[max (
1Z
o
ni ,nj )+ 1]
'j max nj )+ 1]
j ejv;
i =j
otherwise
(2.7)
The Mean Metropolis Method: a new improved method that is presented in [18],
It provides the stability and the adaptivity for the information discovery process.
Their weights are updated according the equation (2.8) below.
j eiV;
Qij
[Hi +nj+ e]
1 2; ENt
[iii + tij + e]
^0
t =J
otherwise
(2.8)
Where:
e: is a very small number, and can be zero for large complex systems.
2.3 Consensus Algorithm Applications
Here are some applications where the consensus algorithm plays an important
role:
Flocking Theory: A group of moving agents that have sensing and
communicating devices in a large environment. The mission of the consensus
algorithm in here is to make every agent reach the same velocity of its neighbors.
The system of the network is a dynamic system with a dynamic topology. The
topology is an agent state dependence, and it is computed locally for each agent.
A good example for this is a group of nonpilot planes [2][12],
Rendezvous in Space: In this case, the position of the agent is very important
which makes the system an interactive position topology. This application is
easier than the Flocking Theory because it does not require an agenttoobstacle
16
clash avoidance [13],
Fast Consensus in SmallWorlds: Using semidefine convex programming, where
the weight of the network is considered, leads to a slight increase in algebraic
connectivity of the network, where the speed of the convergence of the consensus
algorithms is measured. By keeping the network weights fixed, the topology can
be designed to achieve a relatively high algebraic connectivity.
Distributed Sensor Fusion in Sensor Networks: The above applications are
considered as distributed sensor fusion. Distributed averaging problems require
implementing the Kalman filter. The average of the inputs in the sensor networks
is dynamically computed [14],
Distribution Formation Control: In multivehicle systems, the design and analysis
framework of distributed formation controllers uses vectors of relative positions
of neighboring vehicles. In order the agents, as multivehicle, to move in
formation, the agents have to cooperate, which requires consent and collaboration
of every agent in the formation. It is clearly a consensus problem [16],
Economic Dispatch and Load Restoration Problems in Power System: a
conventional centralized control problem can be solved in a distribution manner
by applying the consensus theory. Surly, this requires to choose the appropriate
measures as a consensus variables [5][8][18], More details are presented in the
next chapter.
17
3. Economic Dispatch and Load Restoration Problems
3.1 Economic Dispatch Problem
The main target here is to get perfect use of serving equipment as much as
possible with parallel to the highest financial benefits. In a power system, the Economic
Dispatch is an optimal operation point of each power generator where the demand power
is met, but the total generation cost is the lowest [6],
Several methods are used to solve the Incremental Cost equations, like setting
value of Lambda and solving for generation values, or solving the value of Lambda
directly for a specific load demand with different algorithms. Modem techniques use
linear and nonlinear programming like PiecewiseLinear fuelCost functions and
Quadratic programming of the cost function.
Usually, a cost fuel curve of any power generator is formulated by quadratic
function as follows [7]:
The fuel cost equation:
Ci(Pa) = at +PiPa + YiPci
(3.1)
The Total fuel cost equation:
Protai Hr=i Ci(Pa)
(3.2)
Under the balance condition:
(3.3)
Where:
Q : the fuel cost of the ith generator
au Pi> Yi ' the cost coefficients of the ith generator
PD: the total demanded power
18
Pa : the generated power of the ith generator
The definition of the Incremental Cost IC for each generator is the same as the
conventional economic dispatch:
ICt= dÂ£Â§^1 = At i =1,2.......n (3.4)
By using the discretetime consensus algorithm form then the Incremental Cost by using
the first order discrete consensus algorithm is as follows [5]:
At[k + 1] = Yj=i dij Aj [k] i =1,2(3.5)
Where:
dij : is the ( i ,j) entry of the rowstochastic matrix Dn depends on the Laplacian
matrix
Ai[k + 1] : updating IC of ith takes in account the connected jth generator to the ith
generator
In order to include the power balance constraints in the equation (3.3), the power balance
error AP is defined as follows:
AP = Pz, HU PGt (3.6)
Finally, the updating IC of the leader becomes as follows:
Ai[k + 1] = Aj[k\ + eAP i = 1,2, ...,n (3.7)
Where:
Â£ : is a positive scalar, and it is called the convergence coefficient that controls
the convergence speed of the leader generator or the leader agent.
In the case where the power generation constraints are applied, the following conditions
must be taken in account in the algorithm [5][7][8],
19
PGijnax > when PGi > Pdjnax
PGi .when PGijnin < PGi < P(
when PGi < PGijnin
Gijnin Gi
Gijnax
3.2 Load Restoration Problem
One of the consequences, after the protection system gives its orders to the circuit
breakers to open, in order to isolate a faulty area in the power network, some unfaulted
loads may trip and become out of service. Returning these loads back to the service as
fast as possible, is one of the important aspects in the power networks. This action takes
into account priority and capacity of each load. This procedure (retuning unfaulted loads
back to the service) is called in the power system the LoadRestoration [18][ 19].
This kind of control task has been achieved in past years by using different
computing algorithms, like genetic algorithm, particle swarm optimization, et cetera. A
major drawback of these methods appears to be their need to a powerful central controller
in order deal with a vast amount of information throughout the network. This leads to an
extra cost and suffers from a singlepoint failure besides other drawbacks of a central
controller that were mentioned earlier. In absence of question, solving the load restoration
problem in a distribution control scheme is an intelligent solution to overcome all central
controllers drawbacks.
Recently, MultiAgent System (MAS) is an area of the interest, and different
algorithms are applied to solve the load restoration problem. Some of them work with
only radial power structures; others work with ring power structure. One advanced
algorithm is presented in the reference [18], It is capable to work even with a complex
power structure, i.e., radial, ring, or mixed, because the proposed algorithm is
independent of a system configuration.
20
In this case, the total net power of each agent is required for the calculation, and
during stable normal operation the average of the total net power must be equal to zero.
Xeq = = 0, i = 1,2 ...n (3.8)
Where:
X : is discovered information which is the total net power of the agent ith
n : is the total number of the agents
The overall information updating process i.e., the total average net power for each agent,
is modeled the same as the equation (3.7) but without the balance error dimension.
X[k + 1] = DX[k\ (3.9)
Where:
D : is the sparse iteration matrix.
During a post fault period, the total net power equation (3.8) cannot be fulfilled
because of the negative power shortage from the unfaulted agents, or loads. This
requires immediate load restoration procedure. The Optimal load restoration decision can
be obtained by satisfying coming two conditions:
1. Maximizing the capacity of restored loads and assuring higher priority loads be
served first, i.e.,
max Â£f=1 Pt.PLi (3.10)
Where:
Pi : is the priority index associate with z'^load
PLi : is the amount of power for an agent ith needs to be restored
2. Sum of the total loads to be restored must not exceed the total generated power,
21
(3.11)
Where:
PGi : is the amount of generated power for an agent ith.
Identifying lost loads to be restored can be easily done by using the 01 Knapsack
Problem, which is a combinatorial optimization problem. Having a group of items where
each item has its own weight and corresponding value, and finding the number of each
item to be added in a collection with a condition of the total collection weight, is less than
or equal to a given limited amount but the total value is as large as possible. Its
mathematical model is summarized as follows [21]:
A : is the limited total weight of the collection
The 01 knapsack problem can identify restored loads based on three factors,
greedy by profit, or value, greedy by weight, or greedy by profit density. Since these
loads are identified, the consensus algorithm will be activated to achieve a power balance
again where the total net power for each systems agent should converge to zero.
3.3 Estimation Information Matrix in the Consensus Algorithm
Instead of computing the information matrix D in equations (3.5) and (3.9) based
on the calculation methods that are presented in the chapter two, the estimation adaptive
ma xf(x1,x2,...,xn) = Z?=iPiXi
I"=i WiXi< A
Xi e {0,1}
(3.12)
Where:
Pi : is the value of an agent ith
Wj : is the weight of an agent ith
22
techniques are applied to estimate it. In this thesis, Matlab codes were implemented based
on the Gradient Algorithm (GA) and the Recursive Least Square Algorithm (RLS) to
solve both the economic dispatch and the load restoration problems. The final forms of
those estimation methods are presented in the following sections. The Complete
mathematical derivation for both estimation algorithms is presented in the appendix A.
3.3.1 Gradient Algorithm Estimation Form
Ai(k + 1) = duAf,(fc) + Y,j eN; dtj [.Aj(k)  Aj(fc)] (3.13)
du I 2/ 6 Nj dy i 1.2, ,n (3.14)
Inspired by the adaptive control theory, we propose the following cost function to be
minimized [22],
+  Xt(k + !)]2 (3 15)
dtj{k + 1) = dtJ(k) At[At(fc + 1) Xt(k + 1)] (3.16)
dij(k + 1) = dtj{k) fi[At(k + 1) Xt(k + 1)] [%(Â£) Af(fc)] (3.17)
dij(k + 1) = dy(/c) /t^i(fc)[Ai(fc +1) Xt(k + 1)] (3.18)
In the equation (3.18), Xt is the average of the neighbors of a ith node, and it is computed
as follows:
Xi(k + l) = ^jeNiAj(k + l) (3.20)
The initial values: dy (0) = 0 i A j and du (0) = 1 e dy (0) 1 7= j
pL = 0.5, 0.1 or less is a scalar to increase the speed of the convergence.
23
3.3.2 Recursive Least Square Algorithm Estimation Form
dij(k + 1) = dij(k) Pi{k)(pi{k)[Xi{k + 1) At(k + 1)] (3.21)
Pi(kl)(pi(k)(pi(k)T Pj(fcl)
P,(/C) = Pf(fc 1) +
(3.23)
1+ (pi(k)T Pi(kl)(pi(k)
In the equation (3.21), A* is the average of the neighbors of a ith node, and it is computed
as follows:
+ 1) ~Xj e ^ + 1)
(3.24)
The initial values: dy (0) = 0 i =Â£ j and du (0) = 1 e dy (0) i ^ 7
Pj(0) = Pj/ Pj > 0 is a scalar matrix to increase the speed of the convergence.
24
4. Study Cases and Results
To verify our new estimation methods of computing average consensus, in both
cases, the Economic Dispatch and the Load Restoration problems, they were tested on
cases that had been studied before. We compared our results with theirs to make sure the
performance of our new estimation algorithms gave the same correct results of the
previous studies.
4.1 Three Generators System for Economic Dispatch Problem
The system contains three generators, or agents, which provide power supply to
an electric load Pd The system parameters are summarized in the table 4.1 below [7]:
Table 4.1: Three generators; system parameters
Agent Or Generator Cost Coefficients used in equation (3.1) Power initial [MW]
a r $/hr] P \ $/MWhr] Y 2 \ $/MW2hr]
1st 561 7.92 0.001562 450
2nd 310 7.85 0.001940 300
3rd 078 7.97 0.004820 100
In this case, the new estimation method is applied to solve the economic dispatch
problem. Here, instead of computing the row stochastic matrix D, based on the
Laplacian Matrix L, the gradient algorithm is used to estimate it. The communication
topology of this system is the same as Figure 1.1 (b). The algorithm will solve the
economic dispatch problem so that the Incremental Cost of each generator converges to
the same optimal value. The next sections show our results based on the estimation
method.
25
4.1.1 Three Generators System with New Estimation Method using Gradient
Algorithm without Power Constraints
In this case, there were no produced power limits for the system generators. The
situations summary is as follows:
1 The system parameters were taken from the table 4.1
2 The row stochastic matrix D was estimated by using the Gradient Algorithm
3 The required demanded power was 850 MW and 950 MW
4 The convergence gradient gain coefficient fx = 0.5
Incremental Costs
Total Power (Demand & Produced)[MW]
Produced Power per Generator [MW]
(a) (b) (c)
Figure 4.1: Three generators using GA; ICs and power (no power constraints)
As it is see in Figure 4.1 (a), all the three Incremental Costs A1,A2, and A3
converged very fast to the same optimal value A* = 9.1483 %/MWh. After 1 second, the
demanded power increased to 950 MW. We notice that the leader (agent 1), red line,
responded faster than the others after the change happened, then it raised the other agents
to a new Incremental Cost value, and after 1.4 sec they reached to the consensus again,
which is a new optimal value A* = 9.295 %/MWh. In both stages, the generated power
reached the demanded power quickly. Because there were no power constraints, we
notice that all agents produced power without any limits as it is shown in Figure 4.1 (c).
26
Also the power balance had been satisfied as it is shown in Figure 4.1 (b). Our results are
exactly the same as the results in the reference [5] where the Incremental Cost was
computed based on the calculation methods in equations (2.6), (2.7), and (2.8).
4.1.2 Three Generators System with New Estimation Method using Gradient
Algorithm with Power Constraints
In this case, there were produced power limits for the system generators. The
situations summary is as follows:
1. The system parameters were taken from the table 4.1 except y^ = 0.00128
$/MW2hr so that agent one can produce more than 600 MW
2. The row stochastic matrix D was estimated by using the Gradient Algorithm
3. The required demanded power was 850 MW and 950 MW
4. The convergence gradient gain coefficient /i = 0.5
5. The generator maximums limits were [ 600 400 200 ] MW
6. The generator minimums limits were [ 150 100 050] MW
Incremental Costs Total Power (Demand & Produced)[MWI Power Produced per Generator [MW]
Time [sec] Time [sec] Time [sec]
(a) (b) (c)
Figure 4.2 Three generators using GA; ICs and power (with power constraints)
In this case, the generators power limits were applied in solving the Incremental
Fuel Cost. As we see in Figure 4.2 (a), all the three Incremental Costs X1 ,X2 ,and X3
27
converged very fast to the same optimal value X* = 8.576 $/MWh. After 1 second, the
demanded power increased to 950 MW. We noticed that the leader (agent 1), red line,
responded faster than the others after the change happened, then it raised the other agents
to a new Incremental Cost value, and after 1.6 sec they reached to the consensus again,
which is a new optimal value X* = 8.852 $/MWh. In both stages, the generated power
reached the demanded power quickly. Because of the power constraints, we notice that
the generator one (the leader) stuck on 600 MW as a result of its power limits as shown in
Figure 4.2 (c). Also, the power balance and the power constraints had been satisfied as
shown in Figure 4.2 (b). Our results are exactly the same as the results in the reference
[7] where the Incremental Cost was computed based on the calculation methods.
4.2 Five Generators System for Economic Dispatch Problem
The system contains five generators or agents provide power supply to an electric
load Pd The system parameters are summarized in the table 4.2 below [7]:
Table 4.2: Five generators; system parameters
Agent or Generator Cost Coefficients used in equation (3.1) Power initial [MW]
a [$/hr] P [$/MWhr] Y 2 [$/MW2hr]
1st 561 7.92 0.001562 200
2nd 310 7.85 0.001940 250
3rd 078 7.97 0.004820 100
4th 561 7.92 0.001562 200
5th 078 7.80 0.004820 100
28
In this case, the gradient algorithm and the recursive least square algorithm are
used to estimate the rowstochastic matrix D. The communication network of this system
has different topologies as it is shown in Figure 4.3 below. The Incremental Cost
algorithm will solve the economic dispatch problem so that the Incremental Cost of each
generator converges to the same optimal value. The next sections show our results based
on the estimation methods.
Figure 4.3: Five generators; different system topologies
4.2.1 Five Generators with New Estimation Method using Gradient Algorithm
Three different cases for the initial values of the adjacency matrix for different
system topologies were studied. The situations summary is as follows:
1 The system parameters were taken from the table 4.2
2 The row stochastic matrix D was estimated by using the Gradient Algorithm
3 The required demanded power was 850 MW and 950 MW
4 The convergence gradient gain coefficient pL = 0.5
5 Different system topologies were used as it is shown in Figure 4.3
6 No power constraints were applied
29
$/MWh
4.2.1.1 Five Generators using GA; Guessing Initial Values djj = djj = 0.0
Ni
dy dji 0.0 dn 1
dij
)=l.Ni ,ij
rl.O 0.0 0.0 0.0 0.0
0.0 1.0 0.0 0.0 0.0
d0 0.0 0.0 1.0 0.0 0.0
0.0 0.0 0.0 1.0 0.0
Lo.o 0.0 0.0 0.0 1.0
Incremental Costs
Total Power (Demand & Produced)[MW]
(a)
(b)
Figure 4.4: Five generators using GA; ICs and power (d^ = d^ = 0.0)
30
4.2.1.2 Five Generators using GA; Guessing Initial Values djj = djj =Â£0.0
Ni
dij dji =Â£ 0.0
.0,du = l ^
j=l:Ni ,i*j
rO.10 0.30 0.20 0.25 0.15
0.30 0.05 0.10 0.10 0.05
d0 0.20 0.10 0.10 0.40 0.20
0.25 0.10 0.40 0.15 0.10
Lo.15 0.05 0.20 0.10 0.05
Incremental Costs
8.95
8.9
8.85
8.8
8.75
8.7
8.65
8.6
8.55
8.5
X = 8.7565
x = a 66 61
r
1000
950
900
% 850
800
750
Total Power (Demand & Produced)[MW]
700
0 0.5 1 1.5 2 "~0 0.5 1 1.5
Time [sec] Time [sec]
(a) (b)
Figure 4.5: Five generators using GA; ICs and power (d^ = dj, =Â£ 0.0)
PD PG
7
\
31
4.2.1.3 Five Generators using GA; Guessing Initial Values djj =Â£ djj =Â£0.0
Ni
dij =Â£ dji Â£= 0.0, dn = 1 ~ ^' dij
j=lNi ,i+j
r0.30 0.30 0.15 0.05 0.20
0.15 0.20 0.15 0.30 0.20
=> d0 0.20 0.10 0.05 0.40 0.25
0.20 0.20 0.30 0.15 0.15
Lo.15 0.05 0.20 0.10 0.50
Incremental Costs
Total Power (Demand & Produced)[MW]
(a)
(b)
Figure 4.6: Five generators using GA; ICs and power (d^ =Â£ dj, Â£= 0.0)
It can be seen in Figures 4.4 (a), 4.5 (a), and 4.6 (a) by applying the gradient
algorithm, all five Incremental Costs 7^ ,X2 ,X3, k4, and ks converged very fast to the
same optimal value X* = 8.666 $/MWh. After 1 second, the demanded power increased
to 950 MW. It is noticeable that the leader (agent 1), red line, responded faster than the
others after the change happened, then it raised the other agents to a new Incremental
Cost value, and after 1.1 sec they reached to the consensus again, which is a new optimal
32
value X* = 8.756 $/MWh. It can be easily noticed that in Figure 4.5(a) where d;j = dji ^
0.0, the agents reached the consensus faster than the other cases because of the symmetry
of the initial matrix. Figures 4.4 (b), 4.5 (b), and 4.6 (b) show the total generated power
by the agents. When the demanded power changed from 850 MW to 950 MW after 1
second of operation, all agents increased their produced power to meet the demanded
power. Therefore, the power balance had been satisfied. Our results are exactly the same
as the results in the reference [5] where the Incremental Cost was computed based on the
calculation methods.
4.2.2 Five Generators System with New Estimation Method using Recursive Least
Square Algorithm
Three different cases for the initial values of the adjacency matrix for different
system topologies were studied. The situations summary is as follows:
1 The system parameters were taken from the table 4.2
2 The row stochastic matrix D was estimated by using the Gradient Algorithm
3 The required demanded power was 850 MW and 950 MW
4 Different system topologies were used as it is shown in Figure 4.3
5 No power constraints were applied
6 The Covariance Matrixs initial p0 = 10/
33
4.2.2.1 Five Generators using RLS; Guessing Initial Values d^ = djj = 0.0
dij dji 0.0 ,
j=l:Ni ,ij
rl.O 0.0 0.0 0.0 0.0
0.0 1.0 0.0 0.0 0.0
d0 0.0 0.0 1.0 0.0 0.0
0.0 0.0 0.0 1.0 0.0
Lo.o 0.0 0.0 0.0 1.0
Incremental Costs Total Power (Demand & Produced)[MW]
(a) (b)
Figure 4.7: Five generators using RLS; ICs and power (d^ = dji = 0.0)
34
4.2.2.2 Five Generators using RLS; Guessing Initial Values d^ = djj ^0.0
Ni
dij = dji =Â£ 0.0, dn = 1 ^' dij =>
j=l:Ni ,ij
rO.10 0.30 0.20 0.25 0.15
0.30 0.05 0.10 0.10 0.05
0 = 0.20 0.10 0.10 0.40 0.20
0.25 0.10 0.40 0.15 0.10
Lo.15 0.05 0.20 0.10 0.05
Incremental Costs Total Power (Demand & Produced)[MW]
(a) (b)
Figure 4.8: Five generators using RLS; ICs and power (d^ = dj, =Â£ 0.0)
35
4.2.2.3 Five Generators using RLS; Guessing Initial Values d^ A djj A 0.0
Ni
di} A dji A 0.0, du = 1  ^ dij
j=lNi ,i+j
r0.30 0.30 0.15 0.05 0.20
0.15 0.20 0.15 0.30 0.20
=> d0 0.20 0.10 0.05 0.40 0.25
0.20 0.20 0.30 0.15 0.15
Lo.15 0.05 0.20 0.10 0.50
Incremental Costs Total Power (Demand & Produced)[MW]
(a)
(b)
Figure 4.9: Five generators using RLS; ICs and power (d^ A d^ A 0.0)
It can be seen in Figures 4.7 (a), 4.8 (a), and 4.9 (a) by applying recursive least
square algorithm, all five Incremental Costs Xx X2, X3, X4, and ks converged very fast to
the same optimal value X* = 8.666 $/MWh. After 1 second, the demanded power
increased to 950 MW. It was noticeable that the leader (agent 1), yellow line, responded
36
faster than the others after the change happened, then it raised the other agents to a new
Incremental Cost value, and after 1.05 seconds they reached the consensus again, which
is a new optimal value X* = 8.756 $/MWh. It can be easily noticed that in Figure 4.8(a)
where dy = dji ^ 0.0, the agents reached the consensus faster than the other cases because
of the symmetry of the initial matrix. Overall, the performance of RLS algorithm has
smoother convergence to the optimal value than the GA algorithm, and this can be easily
noticeable when their results are compared. Figures 4.7 (b), 4.8 (b), and 4.9 (b) show the
total produced power by all agents. When the demanded power changed from 850 MW to
950 MW after 1 second of operation, all agents increased their produced power to meet
the demanded power. So the power balance had been satisfied. Our results are exactly the
same as the results in the reference [5] where the Incremental Cost was computed based
on the calculation methods in equations (2.6), (2.7), and (2.8).
4.2.3 Five Generators with New Estimation Method using GA and RLS algorithms
where the System Topology Changes with Time
In this case, the system topology changes with time. The situations summary is
as follows:
1. The system parameters were taken from the table 4.2
2. The row stochastic matrix D was estimated by using the Gradient Algorithm and
the Recursive Least Square Algorithm with do = 0.0 for both algorithms
3. The required demanded power was 850 MW and 950 MW
4. The system topology was changing with time as it is shown in Figure 4.10 on the
next page
5. No power constraints were applied
37
J/MWh
The topology of the system changes with time as follows
Figure 4.10: Five generators; changing sequence of the system topology
Incremental Costs
Total Power (Demand & Produced)[MW]
(a) (b)
Figure 4.11: Five generators using GA; ICs and power (topology changes with time)
38
8.95
Incremental Costs
1000
Total Power (Demand & Produced)[MW]
8.9
8.85
8.8
8.75
8.7
8.65
8.6
8.55
3.5
V *3 V
Â£= 8.75
35
r~
( Â£= a 6661 I
0.5 1
Time [sec]
1.5
950
900
850
800 
750
~0 0.5 1 1.5 2
Time [sec]
(a) (b)
Figure 4.12: Five generators using RLS; ICs and power (topology changes with time)
It can be seen from Figures 4.11(a) and 4.12(a), by using the gradient algorithm
and the recursive least square algorithm, all five Incremental Costs X1, X2, X3, X4, and X5
converged very fast to the same optimal value X* = 8.666 $/MWh and X* =
8.756 $/MWh corresponding to the demanded power from 850 MW to 950 MW. Figures
4.11(b) and 4.12 (b) illustrate the total generated power. It is noticeable that the total
generated power increased to meet the demanded power. This case lead to the conclusion
the connected agents reached the consensus even though their topology changed with
time.
4.2.4 Five Generators with New Estimation Method using GA and Agents 4 and 5
are Become Disconnected
In this case, two agents became disconnected from the rest of the system. What
will happen to the system convergence and the produced power? The changing sequence
of the system topology is illustrated in Figure 4.13 on the next page. The agents 4 and 5
have been selected as the disconnected agents after 1.2 sec of operation. The situations
39
summary is as follows:
1. The system parameters were taken from the table 4.2
2. The row stochastic matrix D was estimated by using the Gradient Algorithm
3. The required demanded power was 850 MW
4. The convergence gradient gain coefficient /i = 0.5
5. No power constraints were applied.
(0.4 to 0.6) sec (0.6 to 1.2) sec (1.2 to 2) sec
Figure 4.13: Five generators; agents 4 and 5 become disconnected
40
Incremental Costs Total Power (Demand & Produced)[MW] Power Produced per Generator [MW]
Time [sec] Time [sec] Time [sec]
(a) (b) (c)
Figure 4.14: Five generators using GA; ICs and power (two agents 4 and 5 become
disconnected)
It can be seen from Figure 4.14 (a), by using the gradient algorithm, all five
Incremental Costs X1, X2,X3, X4, and X5 converged very fast to the same optimal value
X* = 8.666 $/MWh. After 1.2 sec of operation, two agents (4 & 5) became disconnected
from the rest of the system while the demanded power still at 850 MW. It can be noticed
that the other three agents (1, 2, and 3) converged to a new Incremental Cost value
X* = 9.148 $/MWh. As the system lost the connection with the disconnected agents so it
kept the last Incremental Costs of them just before they became disconnected. Because
the system lost part of the generated power from the disconnected agents, as it is seen in
Figure 4.14 (b), the other agents had to compensate the shortage in the generated power,
and this what exactly happened in a few milliseconds as it illustrated in Figure 4.14 (c).
The agents 1, 2, and 3 increased their produced power to match the demanded power of
the system. Finally, the power balance had been satisfied.
41
4.2.5 Five Generators with New Estimation Method using RLS and Check the
Necessity of the Reaching Consensus
This case is to check the necessity that said In order the agents to reach the
consensus, the sum of all columns of the adjacency matrix d must be equal to one, so the
summation of all rows (red lines) and columns (blue lines) were plotted in order to check
whether this necessity hold or not. The situations summary is as follows:
1. The system parameters were taken from the table 4.2
2. The row stochastic matrix D was estimated by using the RLS and d0 = 0.0
3. The required demanded power was 850 MW
4. No power constraints were applied.
The system topology was changing with time as it is shown in Figure 4.15 below.
(0.4 to 0.6) sec (0.6 to 2) sec
Figure 4.15: Five generators; changing sequence of system topology
42
Incremental Costs Total Power (Demand & Produced)[MW]
(a) (b)
Figure 4.16: Five generators using RLS; ICs and power (P0 = 0.01)
15
I
05
0
ot Cohmra Summation 
200
400
600
800
1000
1200
1400
1600
1800
2000
Figure 4.17: Five generators; adjacency rows and columns summation (P0 = 0.01)
43
Incremental Costs Total Power (Demand & Produced)[MW]
(a) (b)
Figure 4.18: Five generators using RLS; ICs and power (P0 = 10)
is
t 
05 
I I I M L
200
IS,
too
600
aoo
1000
1200
l0
1600
1800
11T
I 1111111)1111 I l.MI I I I ll*l II 1 I.Mlllll......
2000
05 
11 iihiiii iimm in imm
IIIIMIIIIIIIltlll
111 MIt 11'
200
I Si
1
05 
0
too
600
800
1000
1200
1tOO
1600
1800
2000
200
 ctCofcmw SuwntMn
too
600
800
1000
1200
1t00
1600
1800
2000
Figure 4.19: Five generators; adjacency rows and columns summation (P0 = 10)
44
It can be seen this necessity was accomplished when Po = 0.01 in Figure 4.17, but
it did not hold as P0 increased as in Figure 4.19. It is noticeable the system reached the
consensus even though the sum of columns of the rowstochastic matrix D did not equal
one. From this ironic result, it can be concluded that this proposed necessity has not to be
held true in order for the system to reach the consensus. Instead, the average of the
columns summation of the rowstochastic matrix D must be equal to one.
4.3 IEEE 16Bus Test Power System for the Load Restoration Problem
In this case, the system contains 16 buses compound of generation and load
agents. The system configuration is show in Figure 4.20 below:
It is a standard IEEE test power system. The arrows resemble the power loads, the
circles resemble the power generators, the red squares resemble the circuit breakers in the
close position, and the green squares resemble the circuit breakers in the open position. In
this case of study, the power loses of the transmission lines are neglected.
45
Data of the 16bus system in Figure 4.20 on the previous page can be easily summarized
in the table 4.3 below [18]:
Table 4.3: 161 3us power system; system data
Agent or Bus Neighbors Pa [MW] Pu [MW] x? [MW] Priority
r 2,5 40 0 40 
2 1,3,5,10 40 0 40 
3th 2,10 50 0 50 
4 10,11 0 25 25 P2
5m 1,2,6 0 35 35 P2
6m 5,7,9 0 20 20 PI
yEE 6,8,9 0 15 15 P2
8th 7,9 0 25 25 PI
9 6,7,8,11,15 0 5 5 PI
To 2,3,4 0 30 30 P2
11th 4,9,12 40 0 40 
12 11,13 0 45 45 P2
13 12,14 0 10 10 P2
14 13,16 0 40 40 P2
15 9 30 0 30 
16 14 50 0 50 
In the table above; PGi is the agent ith local generation, PLi is the agent ith local
load, X is the agent ith local net power, and Pi~2 is the agent ith load priority with Pi >
P2 The assumption here according to [20] is a sudden fault occurs to the generator on the
bus 11 (agent 11) which led the protection system to react immediately to isolate the fault
by opening some circuit breakers. The system configuration of the post fault period is
illustrated in Figure 4.21 on the next page.
46
Figure 4.21: The 16bus system; post fault configuration (source ref. [18])
As a result the power protection reaction, the system lost eight unfaulted loads
(outofservice) which attached to the agents 4 and 6 ~ 12 (shaded area). No doubt, these
loads should be restored, as fast as possible, based on the total net power available and
their priority. So, the load restoration process has to be activated to return back the lost
loads. For such case, very important information like the total net power, the agents
indexes, and the demanded power of the unfaulted loads are extremely required.
To solve the load restoration problem for the situation above in a distribution
fashion, the information discovery matrix M is very important. Each agent has to
converge to the same M matrix. According to the reference [18], every agent in the
system is initially created with the nx3 matrix. In this initial matrix only two nonzero
elements can be found. Mu indicates the agent index (ith) if it is working normally or (0)
if it is not. Mt2 indicates the outofservice agent index (ilh) if it is ready for restoration or
(0) if it is not. Mi3 indicates the local net power for the working agent or the demanded
power of the ready for restoration agent. Clearly in the Mj.j matrix, the i1h agent row
could be [i 0 PLi ] if it is working agent or [0 i PLi ] if it is ready for restoration agent.
47
Because every agent has to converge to the same information matrix M, the
information discovery algorithm should be applied to each element of the initial matrices.
Here, instead of apply information discovery algorithm based on the calculation methods,
which are proposed in the reference [18], a new advanced information discovery
algorithm which is based on the estimation methods like, the gradient algorithm, is
applied. The final converged matrix M contains all necessary information required for the
load restoration. The first column shows all normally working agents, the second column
shows all ready for restoration agents, and finally, the third column shows the local net
power for the agents whether they are working normally or ready for the restoration as it
is shown in the table 4.4 below.
Table 4.4: 16Bus power system; final converged of information matrixM
Final converged matrix M
1st column 2nd column 3rd column
1/16 0 40/16
2/16 0 40/16
3/16 0 50/16
0 4/16 25/16
5/16 0 35/16
0 6/16 20/16
0 7/16 15/16
0 8/16 25/16
0 9/16 5/16
0 10/16 30/16
0 0 0/16
0 12/16 45/16
13/16 0 10/16
14/16 0 40/16
15/16 0 30/16
16/16 0 50/16
Initials matrices for the agents
1 0 401 r 0 0 1 r 0 0
0 0 0 2 0 40 : :
0 0 0 0 0 0 3 0 50
0 0 0 0 0 0 4) 0 0
0 0 1 0 0 0 rO 0 0
0 4 25
5 0 35
0 6
LO 0 O JLO 0 0 JL0 O
rO 0 0 nrO 0 0 rO 0
0 7 15
LO 0
TO O
0
0
O 8 25 O 9 5
0 JLO 0
0 JLq 0
0 10 30
O O
o on
13 0 10
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
L4 0 4
0 0 0
0 0 0
0 0 0
0
0
0 12 45
r 0
15
0
O
0 On
0 30
O O
L16 0 50J
48
Using the final converged matrix M as input to the 01 knapsack problem, the
exact ready for the restoration agents with their associated power can be easily identified
to reconnect them back to the system as fast as possible. At the end, the balanced system
is achieved. The final arrangement of our example is illustrated in Figure 4.22 below for
the 0lknapsack greedy by value. The agents with red circuits were not selected by the 0
11 knapsack greedy by value for the restoration.
<
I \
1
'Q
10
11
.12
15
connected
disconnected
.13
14
.16
Figure 4.22: The 16bus system; after restore configuration (source ref. [18])
The operation sequence in the Matlab code of this case was as follows:
1 Total Number of iterations N = 800.
2 Fault occurred at N = 300
3 Load restored at N = 500
4 The convergence gradient gain coefficient /i = 0.0001
49
Average Netpower [MW] Agents Netpower M3 [MW] Agents indexes M2 Agents indexes Ml
4.3.1 IEEE 16Bus Test Power System with New Estimation Method using GA
01 knapsack Value Based
and
Converged Information Matrix M for Agent 5
0 100 200 300 400 500 600 700 800
Number of Iterations
Figure 4.23: The 16bus system; information matrixM convergence
Average Netpower Convergence
Figure 4.24: The 16bus system; total net power convergence (knapsack value based)
50
Instead of using the consensus algorithm based on the calculation methods that
were proposed in the reference [18], a new advanced estimation method using the
gradient algorithm was applied, and the 16bus system reached to the same consensus
results as that presented in the reference [18], For instant, the information discovery
matrixM was initiated with initial values corresponding to every agent as in the table 4.4,
then it converged to the final converged matrixM shown in the same table. Figure 4.23
shows the agent convergence process for each matrix column and Figure 4.24 shows the
system total average net power convergence in the three stages process; the pre fault, the
post fault, and the after fault period. In each stage, the system converged to the net power
initial values. When the system was working normally (1300 iterations in Figure 4.24)
all agents converged to zero which is clear if we take the average of the agents in the
column five of the table 4.3 on the page 46. During the post fault period (300500
iterations in Figure 4.24) and because of the outofservice agents, remains working
agents converged to a positive value which is 7.81 MW. Those working agents can be
easily identified using the first column of the final converged matrixM ((40+40+5035
1040+30+50)/16 = 7.81). Since the average total net power is positive, there is a
necessity to restore some, or all outofservice agents, depending on the system capacity,
and their priorities.
Finding such agents (their indexes) for the load restoration is very easy by
extracting the information from the second column of the final converged discovery
matrixM. Sometimes and because of power demands shortage, not all outofservice
agents can be restored. To identify agents that can be restored, the 01 knapsack is
applied to perform such selection based on the agents priorities and capacities. After
51
reconnection outofservice agents as it is shown in Figure 4.24 (500800 iterations), the
total net power converged back to zero because the 01 knapsack value based restored
100% of the demanded power available (7.81x16 = 125 MW). The 01 knapsack selected
agents was; agent 4(25), agent 8(25), agent 10(30), and agent 12(45).
4.3.2 IEEE 16Bus Test Power System with New Estimation Method using GA and
01 knapsack Density Based
Converged Information Matrix M for Agent 12
Number of Iterations
Figure 4.25: The 16bus system; information matrixM convergence
Average Netpower Convergence
Figure 4.26: The 16bus system; total net power convergence (knapsack density based)
52
This time, the 01 knapsack density based was applied for the load restoration.
By applying the 01 knapsack density based, only 96% of the demand power available
(7.81x16x96% = 124 MW) was restored. The 01 knapsack selected agents was; agent
4(25), agent 6(20), agent 7(15), agent 8(25), agent 9(5), and agent 10(30). As it is
seen in Figure 4.27 (500800 iterations), the average total net power converged to a small
positive number which is (5/16=0.3) as a result of 96% of the 01 knapsack density
based.
Both sections 4.3.1 and 4.3.2 prove the capability of using our new advanced
consensus algorithm based on the estimation methods like the gradient algorithm for
solving such power problem. Moreover, they prove that it is needless to apply traditional
calculation methods like those which are presented in the references [5] and [18],
53
5. Conclusion and Future Work
5.1 Conclusion
In this thesis, a new concept of solving the economic dispatch problem and the
load restoration problems is presented. As a part of solving both problems in a
distribution fashion, an important information matrix is required for updating system
status so a system can reach what is called the consensus. This matrix is called the
information discovery matrix, and it is computed based on specific calculation methods.
Instead of using the existing calculation methods of computing the information
discovery matrix, adaptive techniques, like the gradient algorithm and the recursive least
square algorithm, are applied to estimate above mentioned matrix. This advanced work is
extremely useful to save time consumed during the calculation process of reaching
consensus especially in the case of the bulk network systems. Our results of reaching the
consensus totally matched previous results of cases that had used calculation methods of
reaching the consensus. No doubt, this work proves the importance of the estimation
methods in the reaching consensus and their capability of solving power problems in a
distribution manner which helps to overcome the drawbacks of the central controller.
In this thesis, chapter two gives an important background about the graph and
consensus theory. The chapter three gives the theoretical analysis of applying the
consensus algorithm to solve the economic dispatch and the load restoration problems.
The estimation mathematical model is presented in this chapter. Our case studies and
their results are presented in the chapter four. The comments and notes on these results
are presented here also. Finally, the chapter five gives the conclusion and the future work
of this research.
54
5.2 Future Work
Some important steps have to be taken as further investigation to complement this
work of study in the consensus algorithm based on the estimation techniques. These
future researches can be summarized in the following points:
Study the case of a leader selection in a case if the system is a weighted, an
ordered, and a directed graph.
Study the case of taking into account the power losses in the transmission lines of
the power network.
Study deeply the case of the disconnected agents whether the disconnection
happen in the communication network only, the power lines only, or both of them.
Study the case of losing the systems leader. Dose the system able to select
another leader or not? And how?
Study the case of clastericity when the system is divided to several connected
groups and each group converges to its own consensus.
All in all, all these mentioned future researches need more of an advanced code that
can take into account many possibilities and assumptions in order get a generally flexible
algorithm. Such an algorithm can be easily applied in the real power networks.
55
REFERENCES
[1] R. Diestel, Graph theory, 3rd ed. Berlin: Springer, 2005.
[2] R. OlfatiSaber, J. A. Fax, and R. M. Murray, "Consensus and Cooperation in
Networked MultiAgent Systems," Proceedings of the IEEE, vol. 95, pp. 215233,
2007.
[3] R. Wei, R. W. Beard, and E. M. Atkins, "A survey of consensus problems in multi
agent coordination," in American Control Conference, 2005. Proceedings of the
2005, 2005, pp. 18591864 vol. 3.
[4] R. A. Gupta and C. MoYuen, "Networked Control System: Overview and Research
Trends," Industrial Electronics, IEEE Transactions on, vol. 57, pp. 25272535,
2010.
[5] Z. Ziang and C. MoYuen, "Incremental cost consensus algorithm in a smart grid
environment," in Power and Energy Society General Meeting, 2011 IEEE, 2011,
pp. 16.
[6] T. L. Baldwin and E. B. Makram, "Economic wdispatch of electric power systems
with line losses," in System Theory, 1989. Proceedings., TwentyFirst
Southeastern Symposium on, 1989, pp. 1317.
[7] A. J. Wood and B. F. Wollenberg, Power generation, operation, and control, 2nd ed.
New York: J. Wiley & Sons, 1996.
[8] Z. Ziang and C. MoYuen, "Convergence Analysis of the Incremental Cost Consensus
Algorithm Under Different Communication Network Topologies in a Smart
Grid," Power Systems, IEEE Transactions on, vol. 27, pp. 17611768, 2012.
[9] R. J. Wilson, Introduction to graph theory, 4th ed. Harlow: Longman, 1996.
[10] J. A. Bondy, U. S. R. Murty, and SpringerLink (Online service). (2008). Graph
Theory. Available: http://0dx.doi.org.skyline.ucdenver.edu/10.1007/978l
846289705
[11] D. B. West, Introduction to graph theory, 2nd ed. Upper Saddle River, NJ: Prentice
Hall, 2001.
[12] R. OlfatiSaber, "Flocking for multiagent dynamic systems: algorithms and
theory," Automatic Control, IEEE Transactions on, vol. 51, pp. 401420, 2006.
56
[13] J. Cortes, S. Martinez, and F. Bullo, "Robust rendezvous for mobile autonomous
agents via proximity graphs in arbitrary dimensions," Automatic Control, IEEE
Transactions on, vol. 51, pp. 12891298, 2006.
[14] R. OlfatiSaber and J. S. Shamma, "Consensus Filters for Sensor Networks and
Distributed Sensor Fusion," in Decision and Control, 2005 and 2005 European
Control Conference. CDCECC '05. 44th IEEE Conference on, 2005, pp. 6698
6703.
[15] V. M. Preciado and G. C. Verghese, "Synchronization in Generalized ErdosRenyi
Networks of Nonlinear Oscillators," in Decision and Control, 2005 and 2005
European Control Conference. CDCECC '05. 44th IEEE Conference on, 2005,
pp. 46284633.
[16] J. A. Fax and R. M. Murray, "Information flow and cooperative control of vehicle
formations," Automatic Control, IEEE Transactions on, vol. 49, pp. 14651476,
2004.
[17] Z. Ziang and C. MoYuen, "The leader election criterion for decentralized economic
dispatch using incremental cost consensus algorithm," in IECON2011 37th
Annual Conference on IEEE Industrial Electronics Society, 2011, pp. 27302735.
[18] X. Yinliang and L. Wenxin, "Novel Multiagent Based Load Restoration Algorithm
for Microgrids," Smart Grid, IEEE Transactions on, vol. 2, pp. 152161, 2011.
[19] J. M. Solanki, S. Khushalani, and N. N. Schulz, "A MultiAgent Solution to
Distribution Systems Restoration," Power Systems, IEEE Transactions on, vol.
22, pp. 10261034, 2007.
[20] T. Nagata, Y. Tao, and H. Fujita, "An autonomous agent for power system
restoration," in Power Engineering Society General Meeting, 2004. IEEE, 2004,
pp. 10691074 Vol. 1.
[21] Z. Jiangfei, H. TingLei, P. Fei, and L. Yuanjie, "Genetic Algorithm Based on
Greedy Strategy in the 01 Knapsack Problem," in Genetic and Evolutionary
Computing, 2009. WGEC '09. 3rd International Conference on, 2009, pp. 105
107.
[22] M. Radenkovic, Adaptive Control System Design, class notes for ELEC 5466.
Department of Electrical Engineering, University of Colorado Denver, Fall, 2011.
57
APPENDIX A
MATHEMATICAL DERIVATION OF THE ESTIMATION ALGORITHMS (RLS
and GA)
Let us consider the following linear system model [22]:
y(i + 1) + aqyCi) + I any(i + 1 n) = bxu(i) + b2u(i 1) + I bmu(i + 1
m), i = 0,1,2,.... (A.l)
Where:
u(i) : measurable system input signal
y(i) : measurable system output signal
Knowing that q'1 is unit delay operator, i.e. q_1y(0 = y(t 1) then system in equation
(A.l) becomes:
(1 + aqq1 + I anq~n)y(i + 1) = + b2q~x + I bmq~m+1)u(i)
So that:
y4(<7x) = 1 + aqq1 + I anq~n
5(q_1) = bx + b2q~x + + bmq~m+1
Biq1)
The term ^ ^ in equation (A.3) is transfer operator of the system.
(A. 2)
(A.3)
(A4)
(A.5)
Let us define system parameters and signal vectors as follows:
0q [ q,2> > cijif , brn\ (A.6)
0(Or = [y(0. , y(i + 1 n); bx,..., u(i + 1 m)] (A.7)
So the system is equation (A.l) can be written as:
y(i + 1) = 0(i)TOo (A. 8)
More general system model is:
58
y(i + 1) = 0(i)T0o + d(i) (A.9)
Where d(i) represents the cumulative effects of disturbance, measurement errors, etc.
Assuming that system parameters are unknown, an estimate of 60 is denoted by 6(i + 1)
then the following identification model can be constructed:
y(t + 1) = 6(i + l)r0(O (A. 10)
Estimating 6{i + 1) is determined so that in a certain sense model output y(i + 1)
matches the system output y(i + 1).
Let us choose 6{i + 1) so that it minimizes the sum of the square errors of the fit.
v(e) = zLo (y(k + i) 0(k)Te(i + i)f (A.ii)
A necessary condition for a local minimum is:
mk =0 which ives:
2 S=o {y(k + 1) 0(k)Te(i +1)) (0(JO) = 0 (A 12)
It follows that:
(EL o 0(k)0(k)T)0(i + 1) = ZLo 0(k)y(k + 1) (A. 13)
Hence a least square estimate of 0ois any estimate 6(i + 1) that satisfies equation (A. 13).
There may be more than one minimize of E(s).
Let define a new matrix:
R(i) =n=o0(kmk)T (A. 14)
Which is invertible, and called covariance matrix, then there is an unique least square
estimate:
0(i + 1) = K(i)12fc=o 0(k)y(k + 1) (A. 15)
59
A.l Derivation of Recursive Least Square Algorithm Estimation (RLS)
Considering the least square estimate in equation (A. 13), we wish to determine a
recursive form of this estimate that suitable for easily updating 0(i) to 0(i + 1).
Recalling equation (A. 14), we see that
R(i) = R(i 1) + 0(t)0(Or (A. 16)
Then from (A. 13)
R(i)0(i + 1) = li=o0(k)y(k + 1) (A.17)
R(i)0(i + 1)= 0(/c) y(k + 1) + 0(OyO + 1) (A.18)
R{i)6{i + 1) = R(i 1)0(0 + 0(Oy(i + 1) from (A.13) (A.19)
R(i)6(i + 1) = ( R(i) 0(O0(OT ) 0(0 + 0(0y(i + 1) from (A. 16) (A.20)
Thus:
R(i)6(i + 1) = R(i)6(i) 0(O0(Or 0(0 + 0(0y(i + 1) (A.21)
/?(O0(t + 1) = R(Q6(Q + 0(0[y0 + 1) 0(Or 0(0 ] (A.22)
Then:
0(t + 1) = 0(0 + /?(O_10(O[yO + 1) 0(Or 0(0 ] (A.23)
From stored values of 0(0 and R(i 1), and new observations y(i + 1) and 0(0, by
using equations (A.20 & A.23) we can calculate the new values 0(t + 1) and R(i).
Equations (A. 16 & A.23) are called the Recursive Least Square Estimate (RLS).
To avoid inverting matrix /?(0_1 in equation (A.23), we use what called the matrix
invariance lemma:
(A+BCD)'1 = A'1 A'^C'1 + DA^B)'1 DA'1 (A.25)
Here, all matrices inverses on the righthand side are exist.
Let define P(0 = P(01 then from (A.17)
60
(A.26)
por1 = p(i 1 r1 + 0(O0(or
By applying the mle of matrix invariance lemma, we set:
A = P(i)_1 ,B = 0(/c) C = 1, and D = 0(/c)r then the equation (A.25) becomes
P(i) = P(i 1) +
(A.27)
l+0(i)rP(il)0(fc)
Then we have obtained the following RLS estimate that requires no inversion to be
performed at each step.
0(i + 1) = 0(0 + P(O0(O[yO + 1) 0(Or0(O ] (A.28)
P(ilMk)W)T Pdl)
P(i) = P(i 1) +
l+0(i)rP(il)0(fc)
(A.29)
P(0) = P(0)r > 0
A.2 Derivation of Gradient Algorithm Estimation (GA)
Given an estimate Q, the squared prediction error is:
e(02 = ^(y(0 00 l)r0)2 (A.30)
Its gradient with respect to 6 is:
vee(02 = 00 l)[y(0 00 l)r0] (A.31)
The direction of the negative gradient 0(i l)[y(0 0(i 1)0] is the direction in
which a small change in 0 will lead to a decrease in e(i)2. Thus one motivated to
consider the algorithm
0(0 = 00 1) + P0O 1) (y(0 0(i l)r0(i 1))
(A. 3 2)
Where p > 0 is a gain to increase the speed of the convergence.
Equation (A.32) is called the Gradient Algorithm Estimate (GA) [22],
61
A.3 Basic Flowchart for the Estimation Algorithms (RLS and GA)
Figure A.l: Flowchart of solving EDP based on new estimation algorithms
62

Full Text 
PAGE 1
ENERGY HARVESTING FROM MICROBIAL FUEL CELL USING SELF SYNCHRONOUS FLYBACK CONVERTER by Muhannad, A Alaraj Bachelor of Electrical Engi neering, Qassim University, 2008 A thesis submitted to the Faculty of the Graduate School of the University of Colorado in partial fulfillment of the requirements for the degree of Master of Science Electrical Engin e ering 2013
PAGE 2
ii This thesis for the Master of Science degree by Muhannad, A Alaraj h as been approved for the Electrical Engineering Program by Jae Do Park Chair Tim C. Lei Jason Ren May 16, 2013
PAGE 3
iii Muhannad, A Alaraj (M.S., Electrical Engineering) Energy Harvesting From Microbial Fuel Cell Using Self Synchronous Flyback Converter Thesis directed by Assistant Professor Jae Do Park ABSTRACT Microbial Fuel Cells (MFCs) use biodegradable matter, such as wastewater and animal droppings to generate ele ctrical energy. To harvest the energy from MFC, power electronic converters have recently been used because of their advantages, such as the ability to store the harvested energy and the ability to control MFC voltage. Although power electronic converters have advantages to be used to harvest the energy, the diode based energy harvesters suffer from the low efficiency because of the diode losses. Replacing the diode with a MOSFET reduces the loss because MOSFET have lower conduction loss but this replaceme nt causes the sy nchronous MOSFET to be floating, which requires an isolated gate signal This study presents harvesting energy from MFC using self synchronous flyback converter, which improved the harvesting efficiency by 37.6 % compared to a diode based b oost converter. The form and content of this abstract are approved. I recommend its publication. Approved: Jae Do Park
PAGE 4
iv DEDICATION I dedicate this work to Abrar my lovely wife, who has always beli eved and supported me
PAGE 5
v ACKNOWLEDGMENTS This thesis would not have been possible w ithout the generous support of Qassim University
PAGE 6
vi TABLE OF CONTENTS CHAPTER I. MICROBIAL FUEL CELL ................................ ................................ .......................... 1 Introduction ................................ ................................ ................................ ............. 1 Electrical Characteristics of MFC ................................ ................................ ........... 1 Voltage Current Polarization Curve ................................ ................................ 1 Internal Resistance ................................ ................................ ............................ 3 Maximum Power Point ................................ ................................ ..................... 3 Advantages and Disadvantages ................................ ................................ ............... 4 II. MFC ENERGY EXTRACTION ................................ ................................ ................. 5 Intorduction ................................ ................................ ................................ ............. 5 Passive Energy Extraction ................................ ................................ ...................... 5 Resistors ................................ ................................ ................................ ............ 5 Supercapacitors ................................ ................................ ................................ 6 Charge Pumps ................................ ................................ ................................ ... 7 Active Energy Extraction ................................ ................................ ........................ 8 Power Electronics Converter s ................................ ................................ ........... 8 Boost Converter ................................ ................................ ................................ 9 III. FLYBACK CONVERTER ................................ ................................ ........................ 12 Introduction ................................ ................................ ................................ ........... 12 Basic Topology for Flyback Converter ................................ ................................ 12 Operation of the Flyback Converter ................................ ................................ ..... 13 Continuous versus Discontinuous Flux Operation ................................ ............... 14 Synchronous Flyback Converter ................................ ................................ ........... 16
PAGE 7
vii IV. PROPOSED SYSTEM ................................ ................................ .............................. 17 Introduction ................................ ................................ ................................ ........... 17 Self Synchronous Flyback Converter ................................ ................................ ... 18 Operation of the Self Synchronous Flyback Converter ................................ ........ 18 Hysteresis Controller ................................ ................................ ............................ 22 System Simulation ................................ ................................ ................................ 23 Overall System ................................ ................................ ................................ ...... 24 V. EXPERIMENTAL RESULTS ................................ ................................ .................. 26 Self Synchronous Flyback Converter ................................ ................................ ... 26 System Parameters ................................ ................................ .......................... 26 Filtering the MFC Voltage Ringing ................................ ................................ 30 Results ................................ ................................ ................................ ............. 32 Calculations ................................ ................................ ................................ ..... 34 Boost Converter ................................ ................................ ................................ .... 38 VI. COMPARISON AND CONCLUSION ................................ ................................ ..... 42 Comparison ................................ ................................ ................................ ........... 42 Conclusion ................................ ................................ ................................ ............ 46 APPENDIX ................................ ................................ ................................ ....................... 47 REFERENCES ................................ ................................ ................................ ................. 49
PAGE 8
viii LIST OF TABLES T able V.1 Table of Parameters. ................................ ................................ ................................ 29 V.2 Self Synchronous FLyback Converter Experiment Results. ................................ .... 35 V.3 Boost Converter Experiment Res ults. ................................ ................................ ....... 38
PAGE 9
ix LIST OF FIGURES Figure I.1 Polarization Curve of Two Different MFCs [5]. ................................ .......................... 2 I.2 MFC Electrical Equivalent Circuit [5]. ................................ ................................ ........ 3 II.1 Simple Charge Pump. ................................ ................................ ................................ .. 7 II.2 Schematic Diagram of Boost Converter. ................................ ................................ ... 10 III.1 Flyback Converter. ................................ ................................ ................................ ... 13 III.2 First Mode of Operation. ................................ ................................ .......................... 15 III.3 Second Mode of Operation. ................................ ................................ ..................... 15 III.4 Synchronous Flyback Converter. ................................ ................................ ............. 16 IV.1 Self Synchronous Flyback Converter. ................................ ................................ ..... 19 IV.2 Synchronous Driving Circuit Operation. ................................ ................................ 21 IV.3 Non inverting Hysteresis Controller. ................................ ................................ ....... 22 IV.4 Simulation Results. ................................ ................................ ................................ .. 24 IV.5 Overall System. ................................ ................................ ................................ ........ 25 V.1 Winding Machine. ................................ ................................ ................................ ..... 28 V.2 Ringing Waveforms. ................................ ................................ ................................ 30 V.3 Non inverting hysteresis controller with capacitor at the input. ............................... 31 V.4 Waveforms Afer Filtering. ................................ ................................ ........................ 32 V.5 Experiment Set. ................................ ................................ ................................ ......... 33 V.6 Self Synchronous FLyback Converter Experiment Waveforms. ............................. 36 V.7 Efficiency of the Self Synch ronous Flyback Converter vs. Time. ........................... 37 V.8 Boost Converter Experiment Waveforms. ................................ ................................ 39 V.9 Efficiency of the Boost Converter vs. Time. ................................ ............................ 41
PAGE 10
x VI.1 MFC Voltage for Both Experiments vs. Time. ................................ ........................ 43 VI.2 MFC Current For Both Experiments vs. Time. ................................ ....................... 43 VI.3 Switching Frequency For Both Experiment s vs. Time. ................................ ........... 44 VI.4 Output Capacitor Voltage for Both Experiments vs. Time. ................................ .... 44 VI.5 Efficiency of Both Converters vs. Time. ................................ ................................ 45
PAGE 11
1 CHAPTER I MICROBIAL FUEL CELL Introduction The main purpose of this thesis is to harve st the energy e ffi ciently from Microbial Fuel Cell (MFC). MFC uses biodegradable matter, such as wastewater and animal droppings to generate electrical energy. Employing the bacteria to generate electricity is the basic idea of the microbial fuel cell. The bacteria oxidize their food source, and electrons are produced. When closing the circuit, electrons will circulate and electric ity will b e generated. In the recent research e s the MFC was improved to produce big enough power to be c b nsidered as a power source [21, 22] MFC s can be built in the lab [5, 6] also in the ocean [1, 2] which is very useful to have a renewable source of electrical power under the ocean water. The U.S. Navy supported some researches on the MFC to be able to use it under water to power sensors [1, 2], and it might be used for other applicatio ns. One impor tant problem of MFC is that it has a low output voltage and it cannot be connected in series with other MFCs to have a higher output voltage [3, 4], b ecause of their nonlinear behavior. E lectrical Characteristics of MF C Voltage Current Polarization Curve T he polarization curve is the raltion between the voltage and the current output of the MFC. Different MFCs might have different output power but usually they have similar polirization curves. Figu re I .1 shows two different MFCs and it is clea r that they have the same shape but differernt current and voltage values.
PAGE 12
2 Figure I 1 Polarization Curve of Two Different MFCs [5]
PAGE 13
3 Figure I 2 MFC Electrical Equivalent Circuit [5] Internal Resistance The voltage of the MFC when its terminals are open is generally 0.7 V This voltag e on the terminal of the MFC decreases when an external res istance is connected to the MFC, in other words, when a current fl ows through the MFC. The internal resi stance of the MFC causes this voltage drop The equ ivalent circuit of the MFC is shown in Figure I .2 [5]. The value of the internal resistance varies depending on factors such as reactor size and environmental conditions. Maximum Power Point T here is a poi nt of operation where the maximum power can be extracted from MFC. Th e maximum power extraction f rom MFC happens when an external resistance equal to the interna l resistance is connected to MFC. The maximum power point can be seen in the polarization curves tha t are shown in Figur e I .1. T he internal resistance of the
PAGE 14
4 MFC varies depending on the environ mental conditions, but in most cases it can be assumed to be constant Using a lgorithms tha t have been devel oped to track the maximum power point, the maximum power can be extr acted using a variable resistor or using DC DC converters [6, 7]. Ad vantages and Disadvantages The MFC has many a dvantages that make it an important energy source and tho se advantages can be listed as follows: S ustainable power source. Clean power source from the environment point of view. Direct conversion of substrate energy to ele ctricity [8] Works in ambient and low temperature [8]. Operates in under water e nvironment. However, it also has some disadvantages that eff ect its operation: Low outpu t voltage Low output current, few milliamps depending on the size of the MFC. Depends on environmental conditions. Cannot b e stacked in series to get higher output voltage because of their nonlinear behaviour [3, 4].
PAGE 15
5 CHAPTER II MFC ENERGY EXTRACTION Intorduction To use the energy generated by the MFC, an electrical circuit needs to be con nected to harvest this e nergy. Diff erent harvesters have been used in the recent years' MFC research including resistors and power electronic converters This chapter will brief ly review the previous work that has been done to extract the energy from the MFC. MFC energy harvesters can be di vided into passive harvesters and active harve sters. Each type of harvesters will be brie fl y discussed. Passive Energy Extraction Resistors Extracting the energy from MFC using an external resistor is the most basic technique and has been widely used [12, 23, 24] When an exter nal resistor is connected to MFC, the current will start flowing through the resistor and the MFC voltage is given as : !"# !"# w here !"# is MFC output voltage which is the voltage across the external resistor, is the current pass ing through that resistor, and !"# is the resistance of the external resistor. When the current passes thr ough the resistor, the extracted p ower will be dissipated in the resistor. This power dissipation shows the amount of extract ed energy:
PAGE 16
6 !"#$ !"#$ !" !"! !"#$ !"# To dissipate the maximum amount of power on the external resistor, the external resistor must be equal to the internal resistance of the MFC. This can be seen in the following equations: !"# !"# !"# !"# !"# !"# !"# !"# !"# !"# !"# !"# !"# !"# !"# !"# A variable external resistance was t ested in [12] with developed perturbatio n and observation (P&O) algorithm to track the maximum power point of the MFC, and the algorithm is able to set the external resistance equal to the internal resistance even it is changing. The disadvantage of using external resistor is that the extracted energy will burned in the resistor, which will not make the energy usable. Supercapacitors Using a supercapacitor is more useful than using a resistor because the supercapacitor stores the energy instead of burning it in the resistor. Supercapacitor is a simple way to harvest and store the energy from the MFC, by connecting it in paral lel with the MFC In [1, 2, 14], a capacitor and DC DC converter are used to power wireless sensor s. Different combinations have been used but they share the idea of connect ing the
PAGE 17
7 Figure II 1 Simple Charge Pump capacitor directly to the MFC. Also, the capacitor was used in [13] to develop a MFC tester. To determine the charging and discharging frequency, and the optimum capacity of the capacitor for given charging and discharging potentials, and the optimum charging potentials when the discharge potentials and capacitor values are given. Charge Pumps Charge pumps were used to harvest the energy from the MFC. Charge pumps basically use capacitors and switches, and the operation of the charge pumps can be explained in the simple circuit shown in Figure II .1. Two modes of operation are present in the charge pumps. The first mode of operation is when the switches and are closed and the switch is opened. The capacitor is now in parallel with the supply and it will start charging to reach the supply voltage following the capacitor voltage current equation:
PAGE 18
8 !" After charging the capacitor the switches and opene and the switch close which is the second operation mode. During this mode the capacitor is in series with the supply and the output voltage is equal to: !"# !" Using charge pumps with the MFC has an advantage of being able to h arvest the energy with higher voltage. In [11], the charge pump was applied directly to the MFC and a supercapacitor was connected at the output of the charge pump to store the energy. The charge pump is not a preffered choice because of the low e fficiency at 16.6% 24.4% [11], and the limited controllability Active Energy Extraction Power Electronics Converters Passive energy extraction f rom the MFC is not useful, because r esistors burn the energy, and capacitors can lead the voltage to drop in the MFC. When a supercapacitor is connected to MFC, current flows and charges the supercapacitor, and at some point the voltage of the supercapacitor will be equal to the voltage of the MFC and the current will stop flowing, which will stop harvesting the ener gy from the MFC. The better way to extract the energy from the MFC is by active energy extraction using power electronics converters [5, 6, 15, 16, 19] The energy can be stored in a capacitor and the voltage of the MFC can be maintained within the desirab le limits when using converte rs. Inductance, duty ratio, and the switching frequency are the elements that affect the energy extraction and their effect was investigated in [15].
PAGE 19
9 Boost Converter The need to increase the voltage of the MFC made the use of the boost converter attractive [5, 16, 17, 18, 19]. The boost converter schematic is shown in Figure II .2. On the first time period when the switch is closed and the switch is open, the current will flow through the inductor The voltage a cross the inductor will start increasing and the current decreases following the basic inductance current voltage relation: !" w here is the voltage across the inductor and is th e current passing through it. During the second time period the switch should be opened and the switch should be closed to forward the current to the load During this time the current will start to flow through the switch to charge the capacitor : !" w here is the output capacitor voltage and the is the inductor voltage achieved on the first time period Switching between these two m odes in high frequency will allow the energy to be stored in the c apacitor with a boosted voltage. The switching frequenc y depend s on the time spent in the two modes: !"! The output voltage of the boost converter is: !"# !"
PAGE 20
10 Figure II 2 Schematic Diagram of Boost Converter. w here is th e duty ratio, which is related to the amount of time spent at each period and it can be calculated as follows: w here and are the times spent on the first and second period respectively. Notice that the maximum number of the duty ration is one. In [5], a simple boost converter was used with a MOSFET as and a diode as The reported efficiency was low at 43.8%. The mai n reason of this low efficiency is the diode drop because the voltage across the diode is around 0.6 and the current flows through this diode during the second time period. The diode losses can be calculated as follows: !"## !"#
PAGE 21
11 Loss of the diode is very high especially compared to the low power output of MFC which is drawback of the diode based boost converter. To av oid the high loss of the diode a synchronous boost converter was used in [16] The synchronous boost converter repla ces the diode by a MOSFET, because the MOSFET has low on resistance. The problem of using the synchronou s boost converter is that the MOSFET in place of the diode will become a floating switch, which needs to be driven by a separate or isola ted source. In [16] a transformer was used to drive the synchronous MOSFET by isolated signal, and an efficiency of 75.9% has been achieved.
PAGE 22
12 CHAPTER III FLYBACK CONVERTER Introduction The i dea of using the synchronous boost converter with a transformer based circuit to drive the synchronous floating switch makes th e flyback converter a viable alternative, because the flyback converter already has a transformer that can be used to drive the synchronous floating s witch. Hence the synchronous flyback converter will be more efficient than the diode based boost converter, by eliminating diode and using the main transformer for gating signal as well as power transfer This chapter gives a background review on the flyback converter and its operation. Basic Topology for Flyback Converter Figure III .1 shows a basic fly back converter schematic The flyback converter is derived from the boost co nverter, but with a transformer to step up the voltage. The transformer is also used to iso late the input and the output, which is required for some applications. The transformer must be designed to have a good coupling so that the primary and the secondary are linked with minimal leakage flux T he primary and the secondary of the transformer wi ndings do not carry current simultaneously. Each side of the transformer will carry current only during a part of the switching period depending on the duty ratio.
PAGE 23
13 Figure I II. 1 Flyback Converter Operation of the Flybac k Converter The operation of flyback converter is d efined by two modes: On State and Off State Each mode of operation can be described w ith a separate equivalent circuit that will help to understand the operation of the flyback converter. When the switch in Figure III .1 closes, the primary winding of the transformer is connected to t he power supply 's positive terminal During this time the diode on the secondary side will be reverse biased and open the secondary side of the transformer. Now, the input voltage will appear across the primary w inding and the current will flow throu gh the primary winding with this current voltage relation: !" w here is the voltage across the primary inductor and is the inductor cur rent passing through it. T he secondary current will not flow because the secondary circuit is open. Hence, the flux will be establishe d in the core by the primary current only Thi s is the on
PAGE 24
14 state mode and Figure III.2 shows the current carrying part of the circuit during this mode of operation. The energy will be stored in the magnetic field and it can be calculated using this relation: !"#$%& Where denotes the magnitude of the primary current at the end of the conduction p eriod. At the end of th e first time period the switch should be opened, which will cut the current path on the primary winding. By opening the current path, the voltage of the primary winding should be reversed according to the magnetic induction laws. Reversing the voltage polarity of the primary side will also reverse the polarity of the seco ndary side. This makes the diode on the secondary side forward biased, which will allow the current to pass through the secondary winding and charge the capacitor. This is the second mode of operation, and the equivalent circuit can be seen in Figure III .3. Continuous v ersus Discontinuou s Flux Operation Operating the flyback converter such that the primary switch closes before the secondary current goes to zero is known as the continuous flux operation because the magentic flux in the transformer core is never zero. In the continuous fl ux operation, the current that flows in the primary winding will not start from zero because of the existing magnetic flux. On the other hand, the discontinuous flux operation happen when the current at the secondary side of the transformer goes to zero be fore the primary switch is on. Having zero current in both sides of the transformer means zero flux in the core.
PAGE 25
15 Figure III 2 First Mode of Operation. Figure III 3 Second Mode of Operati on.
PAGE 26
16 Figure III 4 Synchronous Flyback Converter. Synchronous Flyback Converter The basic flyback converter shar es the disadvantage of the diode losses with the basic boost converter. For this reason the synchronous flyback converter is better choice to increase the efficiency since the MOSFET has much lower conduction losses. The synchronous flyback converter shown in Figure III.4 has same structure as the basic flyback converter but with a MOSFET instead of the diode. The ch allenge with replacing the diode with a MOSFET is the driving of the synchronous MOSFET since it is a floa ting switch. The gate drive circuit of the synchronous MOSFET m ust turn it on when the primary switch is o ff and must block the reverse current in case of discontinuous operation. The reverse current must be considered because the MOSFET conducts bidirectional current, and if it is not turned off when the current red uces to zero, the energy stored in the capacitor will be discharged through the synchronous MOSFET to the transformer
PAGE 27
17 CHAPTER IV PROPOSED SYSTEM I ntroduction The best way to harvest the energy is using power converters, which have many advantages over th e other harvesters. They are able to maintain the voltage of the MFC at certain levels which will be necessary to extract the maximum power fr om the MFC, and converters give the ability to store the harvested energy. However, their effciency needs to be i mproved as much as possible Since a transformer was used to drive the synchronous MOSFET of the boost converter because it is a floating switch [6] the idea of using the flyback converter was considerable. Therefore the self synchronized flyback conve rte r [20] will be a good choice because i t synchronizes the secondary MOSFET by itself, so the only thing needs to be driven is the primary MOSFET, which is easy to drive. To drive the primary MOSFET, a non inverting hysteresis c ontroller will be used. This thesis claims that using the self synchronized flyback converter will be more efficient than using the basic boo st converter with a diode because of the MOSFET at the secondary side. T he operation of the self synchronized flyback converter and the non inve rting hysteresis controller will be discussed in details in this chapter.
PAGE 28
18 Self Synchronous Flyback Converter The self synchronized flyback converter [20] is basically a synchronous flyback converter with a designed driving circuit that will drive the synchronous MOSFET using the voltage across the output capacitor. The self synchronized flyback converter is shown in Figure IV .1, and it can be seen that the synchronous MOSFET will be driven by using the output capacitor voltage Since the capacitor to s tore the energy must be big enough to store the harvested energy, it takes time to build a voltage that can drive the MOSFET. At the beginning, when the output capacitor voltage is zero, the body diode of the MOSFET will be used as a switch until the capac itor builds a voltage equal to the minimum gate threshold voltage of the MOSFET. This means that at the beginning the circuit will act like a basic flyback converter. Operation of the Self Synchronous Flyback Converter The operation is similar to the opera tion of the basic flyback converter discussed in the previous chapter. The only thing that will change is when the output capacitor builds some voltage. The synchronou s MOSFET gate drive circuit will start operating. Note that the operation of the flyback converter will not change, so the only thing that needs to be discussed is the operation of the synchronous driving circuit. The synchronous driving circuit [20] consists of two resistors: ; and three transistors: ; and a diode The transistor operates as inverter. The transistors and operates as push pull, which is needed to improve the transition of
PAGE 29
19 Figure IV 1 Self Synchronous Flyback Converter. the driving circuit. The diode is used to detect the polarity of the voltage across the MOSFET, which will be used to operate the transistor To understand the operation of the synchronous driving circuit, its operation will be discussed step by step. After opening the primary swi tch, current starts to flow in the secondary side passing through the body diode of the MOSFET. This makes the voltage !" which will make the diode forward biased with a higher voltage than the base emitter voltage !" of the transistor For this reason the diode will be forward bias ed as in Figure IV .2(b). The transistor will remain turned off, and when the transistor is off the base of the transistors will have the voltage of the collector that is high. Having the voltage connected to the base of the transistors and through the resistor will turn the transistor on and turn the transistor off. When the
PAGE 30
20 transistor is turned on, the voltage will be connected to the gate of the s ynchronous MOSFET as in Figure IV .2(c). Now, the gate source voltage of the synchronous MOSFET is equal to the capacitor voltage and the MOSFET will be turned on as in Figure IV .2(d). When !" either when the primary swi tch is closed or the current reversed its direction in case of disco ntinuous operation, the diode will b e reversed biased as in Figure IV .2(e), and the b ase emitter of the transistor will be connected to through the resistor This will t urn the transistor on, and the base of the transi stors and will be connected to a low voltage. This will turn the transistor off, and the transistor will be turned on. T he gate of the synchronous MOSFET will now be connected to a low voltag e and it w ill be turned off as in Figure IV .2(f).
PAGE 31
21 Figure IV 2 Synchronous Driving Circuit Operation.
PAGE 32
22 Figure IV 3 Non inverting Hysteresis Controller. Hysteresis Controller To be able to maintain the MFC voltage at the desirable level, the hyteresis controller can be used. The inverting hyteresis controller was used with the boost converter [5, 16]. When using the inverting hyteresis controller, a transistor must be added t o invert the output signal. This transistor can be eleminated if the non inverting hyteresis controller is used. The non inverting hyter esis controller shown in Fgure IV .3 can maintain the voltage of the MFC at the desirable level. Choosing the non inverti ng hyteresis controller will reduce the number of elements used in the controller without affecting its function. The resistors and in Figure IV .3 are chosen to be variable resistors to change the hysteresis band. Using these variable resistors t he voltage of the MFC and the
PAGE 33
23 operation frequency can be controlled. The high threshold voltage and the low threshold voltage determine the hysteresis band. To calculate the values of the and the following equations can be used: !! !! !! when the MFC voltage hits the the controller turns the MOSFET on, and when the MFC voltage hits the the controller turns the MOSFET off. System Sim ulation After choosing the self synchronized flyback converter and the hyteresis controller to harvest the energy fom the MFC, a simulation must be done to make sure that this combination will wo r k with the MFC. The MFC was simulated as a battery with a series resistance as an internal resistance. The code was used to simulat e the system is in the appendix and the results are shown in Figure IV .4. The first waveform in Figure IV .4 is the primary MOSFET gate signal, which is controlled by the hyteresis band. The second waveform is the voltage of the primary winding of the transformer and notice that it is different than the MFC voltage because the primary inductor is di sonnected from the MFC for part of the time depending on the duty ratio. The third wav eform represents the primary and the secondary currents and notice that the secon dary value depends on the turn ratio of the transformer.
PAGE 34
24 Figure IV 4 Simulation Results. Overall System The overall system schematic of the proposed MFC energy harvester is shown in Figure IV .5 To evaluate the system ef ficiency, a boost converter has be en tested under the same conditions for comparison. At the beginning the hysteresis controller will turn the primary MOSFET on, and the cu rrent will flow through the primary winding. The voltage of the MFC will decrease as the current increase, and when the MFC voltage hits the lower threshold voltage the hysteresis controller will turn the primary MOSFET off. The synchronous gate drive will turn the synchronous MOSFET on and off depending on the current dir e ction on the secondary side of the transformer.
PAGE 35
25 Figure IV 5 Overall System
PAGE 36
26 CHAPTER V EXPERIMENT AL RESULTS Self Synchronous Flyback Converter The main purpose of using the self synchronous flyback converter is to increase the efficiency of harvesting the energy from the MFC. To get high efficiency, the parameters of the self synchronous flyba ck converter must be chosen care fully so th ey consume less energy. System Parameters To build the circuit, the parameters must be chosen such that they have low power losses. For exampl e, the MOSFETs must have low on resistance and the comparator in the hyter esis controller must consume minimal power. For harvesting the energy all the resistances in the path of the current must be reduced to reduce the amount of the power loss. The flyback transformer was made using the transformer winding machine shown in Figure V.1 The primary inductance is a n important element because it affects the switchin g frequency For this experiment it was chosen to have low inductance to reduce the number of turns, which will re duc e the resistance of the wire. A 50 turn primary inductor was made using the transformer winding machine, which has an inductance of 7mH and resistance Also, the turns ratio is important because as the turns ratio increase the secondary current will decrease. Reducing the secondary current should reduce the secondary losses. This can be seen from the simple !"## equation:
PAGE 37
27 !"## If the secondary winding is doubled, the resistance will also be doubled. But the current will be reduced in half. Inserting those values in the loss equation will result in reducing the loss by h alf. So, as the turn s ratio increases the efficiency should increas e. For this experiment the turns ratio was 1:4. The MOSFETs should have low on resistance to reduce the power loss. The ON Semiconductor N channel MOSFET 4906NG was used on bo th switches, which has on resistance at !" T he PN2222A NPN & PN2907A PNP transistors were used for the transistors on the synchronous driving cir cuit. Also, the diode 1N755A was used as in the synchronous driving circuit. The resistor must b e very high to limit the c urrent that flow through it, just enough to drive the transistor The resistor should be high enough so that the current is limited when the transistor is on. The values of the parameters that were used in this experi ment are listed in table V .1
PAGE 38
28 Figure V 1 Winding Machine
PAGE 39
29 Table V 1 Table of Parameters.
PAGE 40
30 Figure V 2 Ringing Waveforms. (a) Switch State (b) MFC Voltage. Filtering the MFC Voltage Ringing The circuit was built in the lab, using the parameters chose on the previous section. When the built circuit was applied to the MFC and connected to the hysteresis controller, the voltage of th e MFC started ringing as the switch goes off, and it becomes no rmal when the switch is on This ringing is caused by the weakness of the MFC and it affected the hysteresis controller, since the voltage of the MFC exceeds the hig h and the low threshold voltages many times during the off period. This makes the hysteresis controller open and close the switch many times during the o ff period. This ringing on the MFC voltage and the hysteresis controller output w aveforms can be seen in Figure V .2
PAGE 41
31 Figure V 3 Non inverting hysteresis controller with capacitor at the input. The MFC voltage ringing starts when the switch goes off, which means when the current stops flowing through the transformer primary winding. When the switc h is off the current stops flowing and because the MFC is a weak source the voltage starts ringing. This problem increases since the hysteresis controller opens and closes the current path many times, which wi ll make the ringing worse To solve this proble m, a capacitor must be connected at the input of the hysteresis controller as shown in Figure V .3 Now when the switch is off and the path of the current is closed, the current will flow through the capacitor and charge it. When the switch is on, the capa citor will be discharged and the current will be added to the current fr om the MFC. The waveforms of the MFC voltage and the
PAGE 42
32 Figure V 4 Waveforms Af t er Filtering. (a) Switch State (b) MFC Voltage. MOSFET gate signal from the hysteresis controller after applying 0.1 !" c apacitor are shown in Figure V.4. Results The proposed system was built as shown in Figure V.5 and applied to the MFC for 25 minutes and the energy was harvested and stored in the output capacitor. The readings were taken each 5 minutes for the MFC voltage, MFC current, output capacitor voltage, switching frequency and exported to excel for the calculations an d they can be seen in Table V .2. The resultant waveforms were recorded using Tektronix TPS2012 o scilloscope as shown in Figure V .6
PAGE 43
33 Figure V 5 Experiment Set
PAGE 44
34 Calculations After getting the experiment results, t he efficiency must be calculated. To calculate the efficiency the input and the output energy must be calculated because we know that the efficiency is equal to: !"# !" where the input energy can be calculated using: !" !" !" !" Where !" !"# !" are the input voltage and input current respectively Now we have the input energy, which is the energy extracted from the MFC. The output energy in our experiment is stored in the output capacitor, and the energy stored in the capacitor can be calculated from: !"# Where is the capacitor voltage and is the capacitance of the capacitor The efficiency was calculated for every 5 minutes for this experi ment and was plotted in Figure V .7 The average efficien cy was 46.1%, and from Figu re V .7 it is clear that the efficiency at the beginning is low because at the beginning the diode conducts, and when the output capacitor voltage reached 1.27 V the synchronous driving circuit started to work and the efficiency started increasing. As the output capacitor voltage increases the gate voltage will increase, which will turn th e synchronous MOSFET on. The on resistance of the MOSFET depends on the voltage at the gate. The on resistance
PAGE 45
35 Table V 2 Self Synchronous FLyback Converter Experiment Results. decreases as the gate voltage goes high, and the MOSFET is completely turned on when the gate voltage is equal to the rated gate source voltage on the data sheet. The switching frequency is decreasing because of the capacitor across the input of the hysteresis controller. When the primary switch is off the current from MFC charges the filtering capacitor, which makes the MFC voltage need more time to hit the upper threshold of the hysteres is controller.
PAGE 46
36 Figure V 6 Self Synchronous FLyback Converter Experiment Waveforms. (a) Primary Switch State (b) MFC Voltage (c) Synchronous Switch State.
PAGE 47
37 Figure V 7 Efficiency of the Self Synchronous Flyback Converter vs. Time.
PAGE 48
38 Table V 3 Boost Converter Experiment Results. Boost Converter To compare the results of harvesting the energy from the MFC with the self synchronous flyback converter, diode based boost converter will be used. Comparing the results of the two converters will help to see the improvement of the self synchronous flyback c onverter in terms of the efficiency. To make the compariso n fair, the two converters have similar components. The inductor used with the boost converter was made in the lab using the windi ng machine. This inductor has !" inductance and resistance. Although this inductor is not efficient because of the high resistance compared to the inductor used in [5], it was used because we will use the same winding machine to make the transformer of the fl yback converter. Low on resistance 4906NG MOSFET has been chosen with the 1N755A diode to build the boost converter. The three main components for the boost converter were chosen and the circuit was built and tested in the lab.
PAGE 49
39 Figure V 8 Boost Converter Experiment Waveforms. (a ) Switch State (b) MFC Voltage The boost converter was connected to the MFC with the non inverting hysteresis controller, and the energy was harvested and stored in 1 F supercapacitor. The experiment took 25 minutes and the readings were taken every 5 minutes. The MFC voltage, the MFC current, the capacitor voltage, and the switching frequency were recorded and they can be seen in table V .3. The waveforms shown in Figure V .8 were taken using Tektronix TPS2012 oscilloscope. The voltage of the MFC can be seen controlled by the hysteresis band of the hysteresis controller. The results was exported to excel and using the same calculations for the self synchronous flyback converter, the efficiency was calculated and plotted as shown in Figure V .9 and the ove rall efficiency was calculated to be 33.5 %.
PAGE 50
40 As the output capacitor voltage increase, the switching frequency increase because of the higher resistance for injecting the power and this increase in the switching frequency can be seen in Table V.3.
PAGE 51
41 Figure V 9 Efficiency of the Boost Converter vs. Time.
PAGE 52
42 CHAPTER VI COMPARISON AND CONCLUSION Comparison The two converters were operated at the same conditions to make the comparison fair. The MFC voltage is shown in Figure VI .1 in real time for both converters. The MFC c urrent is also shown in Figure VI .2 for both converters in real time. Having the same voltage and current from the MFC means the same input power for both converters. The thing that is different between the two circuits is the switching frequency. They started at approximately the same switching frequency, but the switching frequency of the flyback converter was decreasing and was increasing for the boost converter. This switching fr equency behavior difference is shown in Figure VI .3. The self s ynchronous flyback converter charged the output capacitor faster than the boost converter and Figure VI .4 shows a comparison between them. It is clear from the e fficiency comparison in Figure V I .5 that the self synchronous flyback converter has higher efficiency than the boost converter after 10 minutes of operation, which is because the synchronous driving circuit started to drive the synchronous MOSFET at this time. Even the synchronous dr ivin g circuit started to drive the synchronous MOSFET after approximately 10 minutes, the overall efficiency was i mproved by 37.6% to reach 46.1% compared to 33.5 % for the boost converter. The self synchronous flyback converter was able to store 2.27J out of 4 .91J in the output capacitor compared to 1.665J out of 4.95J stored in the output capacitor by the boost converter.
PAGE 53
43 Figure VI 1 MFC Voltage for Both Experiments vs. Time Figure VI 2 MFC Current For Both Experiments vs. Time
PAGE 54
44 Figure VI 3 Switching Frequency For Both Experiments vs. Time Figure VI 4 Output Capacitor Voltage for Both Experiments vs. Time
PAGE 55
45 Figure VI 5 Efficiency of Both Converters vs. Time
PAGE 56
46 Conclusion The self synchronous flyback converter was d esigned and built and the energy was harvested from the MFC and stored in the capacitor in a good efficiency compared to the boost converter. The efficiency improved when the secondary diode was replaced by a MOSFET, because the diode has a high voltage drop across it (0.7 V). Replacing the diode by the MOSFET resulted in floating switch, which needs to be driven by an isolated source. The synchronous driv ing circuit [20] was used to drive the synchronous MOSFET. The main advantage of using the DC DC converters is the ability to control the voltag e of the MFC. The non inverting hysteresis controller was used for this thesis, but a capacitor was needed in the input of the hysteresis controller to filter the voltage of the MFC from the ringing caused by closing the current path each cycle, which is t he way that the flyback converter works. This thesis proved that replacing the secondary diode by a MOSFET im proved the eciency of harvesting the energy from the MFC. It also proves the advantages of using DC DC converters, which are the ability to control the MFC voltage, the ability to store the energy in the output capacitor, and the efficient way to harvest the energy from the MFC.
PAGE 57
47 APPENDIX This is the simulation code for the flyback converter: clear all ; close all ; screenSize = get(0, 'ScreenSize' ); position = [screenSize(3)/3 screenSize(4)/5 560 420]; set(0, 'DefaultFigurePosition' ,position); tMax =0.01; % time period [sec] C = 40000e 6; dt = 1e 6; % Sampling time [sec] Vint = 0.7; % Input voltage peak [V] R = 120; % Resistance [Ohm] R2= 0; t = linspace(0,tMax,tMax/dt); % time vector vs = Vint*ones(1, length(t)); % Source voltage vector vL = zeros(1, length(t)); % Inductor voltage vector initialization vR = zeros(1, length(t)); % Resistor voltage vector initialization vR2 = zeros(1, length(t)); vo = 0.6*ones(1, length(t)); i1 = zeros(1, length(t)); % Curr ent vector initialization i2 = zeros(1, length(t)); sw = ones(1, length(t)); il=0; % load current N = 4; L1= 200e 3 ; L2= L1 N ; Th_H = 3 /1000 ; Th_L = 2/N/1000 ; for n = 1:length(t) 1 if sw(n) == 1, vR(n+1) = R i1(n); vL(n+1) = vs(n) vR(n); % Inductance voltage i1(n+1) = i1(n) + (vL(n))/L1*dt; vo(n+1) = vo(n) + ( il)/C*dt; if i1(n) >= Th_H, sw(n+1)=0; i2(n+1)=i1(n+1)/N; else
PAGE 58
48 sw(n+1)=1; i2(n+1)=0; end else vR2(n+1)= R2 i2(n); vL(n+1)=(vR2(n+1) vo(n+1))/N; i2(n+1) = i2(n) (vo(n)/ L2) dt; % Integration for current vo(n+1) = vo(n) + (i2(n) il)/C*dt; vL(n+1)= ( vo(n+1))/N; if i2(n) <= Th_L, sw(n+1) = 1; i1(n+1)=i2(n)*N; else sw(n+1) = 0; i1(n+1)=0; end end end tm = t*1000; % Result plotting figure(1); subplot(3,1,1); plot(tm, sw, 'k' ); grid on ; axis([0 tMax*1000 0 1.5]); ylabel( 'Switch Status' ); subplot(3,1,2); plot(tm, vL, 'k' ); grid on ; hold on ; ylabel( 'Primary Inductor Voltage [V]' ); subplot(3,1,3); plot(tm, i1, 'k' ); grid on ; hold on ; plot(tm, i2, 'r' ); ylabel( 'Current [mA]' ); xlabel( 'Time [msec]' ); figure(2); plot(tm, vo); hold on ; grid on ;
PAGE 59
49 REFERENCES 1. Conrad Donovan, Alim Dewan, Deukhyoun Heo, and Haluk Beyenal,Batteryless, Wireless Sensor Powered by a Sediment Microbial Fuel Cell, Environmental Science & Technology 2008 42 (22), 8591 8596. 2. Shantaram, H. Beyenal, R. Raajan, A. Veluchamy and Z. Lewandowski,Wireless Sensors Powered by Microbial Fuel Cells, Envi ronmental Science & Technology 2005 39 (13), 5037 5042. 3. S. E. Oh, B.E. Logan, Voltage reversal during microbial fuel cell stack operation, Journal of Power Sources, Volume 167, Issue 1, 1 May 2007, Pages 11 17. 4. P. Aelterma n,K. Rabaey,H. The Pham,N. Boo n, and W. Ver straete,Continuous Electricity Generation at High Voltages and Currents Using Stacked Microbial Fuel Cells, Environmental Science & Technology 2006 40 (10), 3388 3394. 5. Jae Do Park; Zhiyong Ren ,"E_cient energy harvester for microbial fuel cells using DC/DC converters," En ergy Conversion Congress and Ex position (ECCE), 2011 IEEE vol., no., pp.3852 3858, 17 22 Sept. 2011. 6. Jae Do Park, Zhiyong Ren,Hysteresis controller based maximum power point tracking energy h arvesting system for microbial fuel cells, Journal of Power Sources, Volume 205, 1 May 2012, Pages 151 156. 7. Woodward, L., Perrier, M., Srinivasan, B., Pinto, R. P. and Tartakovsky, B., (2010), Comparison of real time methods for maxi mizing power output in microbial fuel cells. AIChE J., 56: 27422750. 8. Korneel Rabaey, Willy Verstraete,Microbial fuel cells: novel biotechnology for energy generation, Trends in Biotechnology 1 June 2005 (Vol. 23, Issue 6, pp. 291 298) 9. R.A. Bullen, T.C. Arnot, J.B. Lakeman F.C. Walsh, Biofuel cells and their development, Biosensors and Bioelectronics, Volume 21, Issue 11, 15 May 2006, Pages 2015 2045.47 10. Alim Dewan, Haluk Beyenal, Zbigniew Lewandowski, Scaling up microbial fuel cells, Environmental Science & Technology 20 08 42 (20), 7643 7648 11. Meehan, A.; Hongwei Gao; Lewandowski, Z.,"Energy Harvesting With Microbial Fuel Cell and Power Management System," Power Electronics, IEEE Transactions on vol.26, no.1, pp.176,181, Jan. 2011.
PAGE 60
50 12. R.P. Pinto, B. Srinivasan, S.R. Guio t, B. Tartakovsky,The e ff ect of real time external resistance optimizatio n on microbial fuel cell performance, Water Research, Volume 45, Issue 4, February 2011, Pages 1571 1578. 13. Alim Dewan, Conrad Don ovan, Deukhyoun Heo, Haluk Beye nal,em Evaluating the performance of microb ial fuel cells powering elec tronic devices, Journal of Power Sources, Volume 195, Issue 1, 1 January 2010, Pages 90 96. 14. Fei Zhang, Lei Tian, Zhen He,Powering a wireless temperature sensor using sediment microbial fuel cells with vertical arrangement of electrodes, Journal of Power Sources, Volume 196, Issue 22, 15 November 2011, Pages 9568 9573. 15. Heming Wang, Zhiyong Ren, J ae Do Park,Power electronic converters for microbial fuel cell energy extraction: Eff ects of inductance, dut y ratio, and switching frequency, Journal of Power Sources, Volume 220, 15 December 2012, Pages 89 94. 16. Jae Do Park, Zhiyong Ren,High e ffi c iency energy harvesting from microbial fuel cells using a synchronous boost converter, Journal of Power Sources, Volume 208, 15 June 2012, Pages 322 327. 17. Richelli, A.; Colalongo, L.; Tonoli, S.; Kovacs, Z.,"A 0.2V1.2V converter for power harvesting application s," Solid State Circuits Confer ence, 2008. ESSCIRC 2008. 34th European vol., no., pp.406, 409, 1 5 19 Sept. 2008. 18. Lhermet, H.; Condemine, C.; P lissonnier, M.; Salot, R.; Aude bert, P.; Rosset, M.,"Efficient Powe r Management Circuit: From Ther mal Energy Harvesting to Above IC Micr obattery Energy Storage," Solid St ate Circuits, IEEE Journal of vol.43, no.1, pp.246,255, Jan. 2008. 19. Carlson, E.J.; Strunz, K.; Otis, B.P.," A 20 mV Input Boost Con verter With Efficient Digital Control fo r Thermoelectric Energy Harvest ing," Solid State Circuits, IEEE Journal of vol.45, no.4, pp.741,750, April 2010. 20. Lee Jon g Jae; Jung Min Kwon; Kim Eung Ho; Woo Young Choi; Bong Hwan Kwon "Single Stag e Single Switch PFC Flyback Con v erter Using a Synchronous Rectifi er," Ind ustrial Electronics, IEEE Transactions on vol.55, no.3, pp.1352,1365, March 2008. 21. Liu, H. and Logan, B.E. (2004) Electricity generation using an aircathode single chamber microbial fuel cell in the presence and absence of a proton exchange membrane. Environ. Sci. Technol. 38, 4040 4046
PAGE 61
51 22. Schroder, U. et al. (2003) A generation of microbial fuel cells with current outputs boosted by more than one order of magnitude. Angew. Chem. Int. Ed. Engl. 42, 2880 2883 23. Rhoads, A., H. Beyenal, and Z. Lewandowski. 2005. Microbial fuel cell using anaerobic respiration as an anodic reaction and biomineralized mangane se as cathodic reactant. Environ. Sci. Technol.39 : 4666 4671. 24. Liu H, Cheng S, Logan BE. Production of electricity from acetate or butyrate in a single chamber microbial fuel cell. Environ Sci Technol. 2005;39 :658 662.
PAGE 1
CONSENSUS ALGORITHM IN SMART GRID AND COMMUNICATION NETWORKS by HUSAIN ABDULAZIZ ALFAGEE B.S.E.E, Higher Institute of Engineering, 1998 A thesis submitted to the Faculty of Graduate School of the University of Colorado in partial fulfillment of the requirements for the degree of Master of Science Electrical Engineering 2013
PAGE 2
ii This thesis for the Master of Science degree by Husain Abdulaziz Alfagee has been approved for the Electrical Engineering Program by Miloje Radenkovic, Chair Mark Golkowski Sam Welch June 20, 2013
PAGE 3
iii Alfagee, Husain Abdulaziz (M.S., Electrical Engineering) Consensus Algorithm in Smart Grid and Communication Networks. Thesis directed by Professor Miloje Radenkovic ABSTRACT On a daily basis, consensus theory attracts more and more researches from different areas of interest, to apply its techniques to solve technical problems in a way that is faster, more reliable, and even more precise than ever before. A power system network is one of those fields that consensus theory employs extensively. The use of the consensus algorithm to solve the Economic Dispatch and Load Restoration Problems is a good example. Instead of a conventional central controller, some researchers have explored an algorithm to solve the above mentioned problems, in a distribution manner, using the consensus algorithm, which is based on calculation methods, i.e., non estimation methods, for updating the information consensus matrix. Starting from this point of solving these types of problems mentioned, specifically, in a distribution fashion, using the consensus algorithm, we have implemented a new advanced consensus algorithm. It is based on the adaptive estimation techniques, such as the Gradient Algorithm and the Recursive Least Square Algorithm, to solve the same problems. This advanced work was tested on different case studies that had formerly been explored, as seen in references 5, 7, and 18. Three and five generators, or agents, with different topologies, correspond to the Economic Dispatch Problem and the IEEE 16Bus power system corresponds to the Load Restoration Problem.
PAGE 4
iv In all the cases we have studied, the results met our expectations with extreme accuracy, and completely matched the results of the previous researchers. There is little question that this research proves the capability and dependability of using the consensus algorithm, based on the estimation methods as the Gradient Algorithm and the Recursive Least Square Algorithm to solve such power problems. The form and content of this abstract are approved. I recommend its publication. Approved: Miloje Radenkovic
PAGE 5
v DEDICATION I lovingly dedicate this thesis to my parents, who gave me an appreciation of learning and taught me the value of perseverance and resolve. I also dedicate this thesis to my wife for her unfaltering support and understanding while I was GRLQJP\0DVWHUV.
PAGE 6
vi ACKNOWLEDGEMENT My special thanks to my advisor, Prof. Miloje Radenkovic, for his contribution and support to my research. I also wish to thank all the members of my committee for their valuable participation and insights.
PAGE 7
vii CONTENTS )LJXUHV....... x Tables ........... xii Chapter 1. Introduction .... 1 1.1 7KHVLV2EMHFWLYHV4 1.2 Thesis Organization ... 5 2. Graph and Consensus Theory .. 7 2.1 Graph Theory 7 2.1.1 *UDSK'HILQLWLRQ 9 2.1.2 'LUHFWHGDQG8QGLUHFWHG*UDSK........10 2.1.3 Connected and DisFRQQHFWHG*UDSK... 11 2.1.4 Incidence and Adjacency MDWULFHV.. 11 2.2 &RQVHQVXV7KHRU\... 13 2.2.1 &RQVHQVXV'HILQLWLRQ.. 13 2.2.2 Consensus in Networks 13 2.3 Consensus Algorithm Applications ... 16 3. Economic Dispatch and Load Restoration Problems 18 3.1 Economic Dispatch Problem ...18 3.2 Load Restoration Problem .20 3.3 Estimation Information Matrix in the Consensus Algorithm ....22 3.4.1 Gradient Algorithm Estimation )RUP..23 3.4.2 Recursive Least Square Algorithm Estimation )RUP......24 4. Study Cases and Results 25
PAGE 8
viii 4.1 Three Generators System for Economic Dispatch Problem ......25 4.1.1 Three Generators System with New Estimation Method using Gradient Algorithm without Power Constraints .....26 4.1.2 Three Generators System with New Estimation Method using Gradient Algorithm with Power Constraints ..27 4.2 Five Generators System for Economic Dispatch Problem ..... 28 4.2.1 Five Generators System with New Estimation Method using Gradient Algorithm ....29 4.2.1.1 Five Generators using GA; Guessing Initial Values @EF=@FE=0.0 . 30 4.2.1.2 Five Generators using GA; Guessing Initial Values @EF=@FErM0.0 31 4.2.1.3 Five Generators using GA; Guessing Initial Values @EFrM@FErM0.0 . 32 4.2.2 Five Generators System with New Estimation Method using Recursive Least Square Algorithm ..33 4.2.2.1 Five Generators using RLS; Guessing Initial Values @EF=@FE=0.0 ....34 4.2.2.2 Five Generators using RLS; Guessing Initial Values @EF=@FErM0.0 .... 35 4.2.2.3 Five Generators using RLS; Guessing Initial Values @EFrM@FErM0.0 ...36 4.2.3 Five Generators System with New Estimation Method using GA and RLS where the System Topology Changes with Time ...37 4.2.4 Five Generators System with New Estimation Method using GA and Two Agents 4 and 5 are Become Disconnected ....39 4.2.5 Five Generators System with New Estimation Method using RLS and Check the Necessity of Reaching Consensus ..42 4.3 IEEE 16%XV7HVW3RZHU6\VWHPIRU/RDG5HVWRUDWLRQ3UREOHP45 4.3.1 IEEE 16Bus Test Power System with New Estimation Method using GA and 01 Knapsack Value Based ..50 4.3.2 IEEE 16Bus Test Power System with New Estimation Method using GA and 01 Knapsack Density Based ..52 5. Conclusion and Future Work ..54
PAGE 9
ix 5.1 &RQFOXVLRQ..54 5.2 Future Work ..55 References ..56 Appendix A.1 'HULYDWLRQRI5HFXUVLYH/HDVW6TXDUH$OJRULWKP(VWLPDWLRQ5/660 A.2 'HULYDWLRQRI*UDGLHQW$OJRULWKP(VWLPDWLRQ*$61 A.3 Basic FORZFKDUWIRUWKH(VWLPDWLRQ$OJRULWKPV5/6DQG*$......62
PAGE 10
x FIGURES Figure 1.1 (a) Central control, and (b) distributed control connections 3 2.1 Bridges of Konigsberg City (1736) .7 2.2 The Four regions and seven bridges in Konigsberg City ......8 2.3 Eulerian Circuit ....... 8 2.4 Three generators (agents) system ... 9 2.5 Directed graph ..... 10 2.6 (a) Connected graph, and (b) disconnected graph 11 2.7 (a) Adjacent vertices, and (b) adjacent edges ..... 11 4.1 Three generators using GA; ,&VDQGpower (no power constraints) .. 26 4.2 Three generators using GA; ,&VDQGpower (with power constraints) 27 4.3 )LYHJHQHUDWRUVGLIIHUHQWV\VWHPWRSRORJLHV29 4.4 Five generators using GA; ,&VDQGpower (dij = dji = 0.0) 30 4.5 Five generators using GA; ,&VDQGpower (dij = dji Â) 31 4.6 Five generators using GA; ,&VDQGpower (dij ÂGji Â) 32 4.7 Five generators using RLS; ,&VDQGpower (dij = dji = 0.0) 34 4.8 Five generators using RLS; ,&VDQGpower (dij = dji Â) 35 4.9 Five generators using RLS; ,&VDQGpower (dij ÂGji Â) 36 4.10 Five generators; changing sequence of system topology 38 4.11 Five generators using GA; ,&VDQGpower (topology changes with time) ....... 38 4.12 Five generators using RLS; ,&VDQGpower (topology changes with time) ..... 39 4.13 Five generators; agents 4 and 5 become disconnected 40 4.14 Five generators using GA; ,&VDQGpower (two agents 4 and 5 become disconnected) ..41
PAGE 11
xi 4.15 Five generators; changing sequence of system topology 42 4.16 Five generators using RLS; ,&VDQGpower (Po = 0.01) 43 4.17 Five generators; adjacency URZVDQGFROXPQVVXPPDWLRQPo = 0.01) 43 4.18 Five generators using RLS; ,&VDQGpower (Po = 10) 44 4.19 Five generators; adjacency URZVDQGFROXPQVVXPPDWLRQPo = 10) 44 4.20 The 16bus test system (source ref. [18]) 45 4.21 The 16bus system; post fault configuration (source ref. [18]) ...47 4.22 The 16bus system; after fault configuration (source ref. [18]) 49 4.23 The 16bus system; information matrix0FRQYHUJHQFH50 4.24 The 16EXVV\VWHPWRWDOQHWSRZHUFRQYHUJHQFHNQDSVDFNYDOXHEDVHG50 4.25 The 16bus system; information matrix0FRQYHUJHQFH52 4.26 The 16EXVV\VWHPWRWDOQHWSRZHUFRQYHUJHQFHNQDSVDFNGHQVLW\EDVHG 52 A.1 Flowchart of solving EDP based on new estimation algorithms 62
PAGE 12
xii TABLES Table 4.1 Three generators; system parameters 25 4.2 Five generators; system parameters 28 4.3 16%XVSRZHUV\VWHPV\VWHPGDWD 46 4.4 16Bus power system; final converged of information matrix0. 48
PAGE 13
1 1. Introduction For more than half of a century, the existing US power grid has been providing its electric power to a wide range of customers. In fact, this system faced substantial magnitudes of challenges that were not taken into account at the time the design was originated. These challenges can be summarized in accordance with the following: x lack of supporting the distributed generation. x renewable energy sources which are being added to the power grid. x lack of flexibility and adaptability. x natural disasters. x human operating errors. For all of the above reasons, and to assure that the power grid will continue to provide the demanded power to its consumers as needed, the power grid should be efficient and smart enough to deal with all demeanors of ongoing and varying changes of the system topology without losing its stability, availability, et cetera. In order to make a power system network effective and smart enough, it should implement a communication network and a control network that integrate and complement the future power system, where the system is called the LargeScale Network Control System (LSNCS) [4][5]. There is no doubt that the LSNCS will be a necessity for the next series of power networks. This refers to a specific means and existence of a large number of subsystems. In this bulk system, the conventional control schematic will face severe challenges that will inevitably affect its controllability. These challenges can be summarized in the following factors [5]: x requirement of a high level of connectivity to achieve the optimal operation
PAGE 14
2 condition. x sensitivity to failures and modeling errors. x affect of a variety of the configurations, such as PlugandPlay of the power grid topology which will make the smart grid topology unknown or undefined. To overcome the drawbacks of conventional control, distribution control is more convenient for solving the identified problems. The main task for using distribution control algorithms is to make sure all system agents, or nodes, reach what is called the consensus. Several areas, where the consensus algorithm is applied, can be used in the improvement of the power system. For example, the consensus algorithm of a multivehicle system, where a vehicle is able to communicate with other vehicles upon a communication network system, is a good example [2]. Therefore, to control this LSNCS smart grid, a very strong algorithm has to be implemented in order to work correctly in the existence of a lack of or unreliable communication capability; this applies even with loss of the central control topology. Such an algorithm has to be tested in areas that resemble LSNCS, as would the Economic Dispatch Problem and the Load Restoration Problem. To illustrate the idea of the central and distribution control, let us consider the five buses power system where each bus has its load and generated power as it is shown in Figure 1.1 on the next page.
PAGE 15
3 (a) (b) Figure 1.1: (a) Central controller, and (b) Distributed controller The communication topology could be a conventional central controller, as shown in Figure 1.1(a), or a distributed controller as in Figure 1.1(b). In Figure 1.1(b), generator one has been selected as the consensus leader. The local controller, in each bus, will keep reporting its status to the leader. Based on the collected information, the leader will decide whether to increase or decrease the group of the consensus variable, according to the situation of a required condition [5]. The entire process mentioned is manipulated by the consensus algorithm. The consensus algorithm is used to solve some fundamental problems of the power system, as the Economic Dispatch problem and the Load Restoration problem. Instead of the conventional central controller, Some researchers had explored consensus algorithms to solve the mentioned problems in a distribution manner [5][8][18]. The main reason of using the distribution fashion is to overcome the drawbacks of the central controller. Staring from the point of solving the economic dispatch, and the load restoration problems in a distribution fashion, by using the consensus algorithm, we have implemented a new advanced consensus algorithm based on the adaptive estimation techniques of the Gradient Algorithm and the Recursive Least Square Algorithm to solve the same problems. This advanced work is tested on different case studies that are G2 G3 G1 G2 G3 G1 Control Center
PAGE 16
4 proposed in the references [5][7][18] to ascertain the sets of comparativelysourced results do coincide and are depicted accurately. These case studies, and their results, are presented in details in the Chapter 4. No doubt, this research proves the capability and dependability of using the consensus algorithm, based on the estimation methods, citing specifically, the Gradient Algorithm and the Recursive Least Square Algorithm to solve such power problems. Briefly, our research objectives outlining this thesis are summarized in the following section: 1.1 Thesis Objectives To fulfill the goals of this research, a set of objectives was specified inclusive in this work. These objectives are summarized in the following points: 1. Implementing a Matlab code to solve the Economic Dispatch Problem for the previous case studies that were focused on in the reference [5] without the power constraints and fulfilling the same results. 2. Implementing a Matlab code to solve the Economic Dispatch Problem and taking into account the power constraints in order to fulfill the power limitations, i.e., a condition that was mentioned in Reference [7]. 3. Implementing a new Matlab code to solve the Economic Dispatch Problem in the same case studies addressing objectives 1 and 2; but this time by applying a new estimation method using the Gradient Algorithm and fulfilling the same results in objectives 1 and 2. 4. Implementing a new Matlab code to solve the Economic Dispatch Problem in the same case studies in objectives 1 and 2; but this time by applying a new
PAGE 17
5 estimation method using the Recursive Least Square Algorithm and fulfilling the same results in objectives 1 and 2. 5. Repeating objectives 3 and 4 to study the case where the system topology changes with time. 6. Implementing a Matlab code to solve the Economic Dispatch Problem to study the case if some agents are found to be disconnected. 7. Implementing a Matlab code to solve the Load Restoration Problem for the case study that was presented in reference [18] and fulfilling the same results. 8. Implementing a new Matlab code to solve the Load Restoration Problem in the same case in objective 7; but this time by applying the new estimation method using the Gradient Algorithm and obtaining the same results in objective 7. 1.2 Thesis Organization The remainder of this thesis is organized and described in methodologies as follows: x Chapter 2: provides a very important background about the graph and consensus theories in the networks; the consensus mathematical model is presented in this chapter x Chapter 3: presents one of the very useful applications of the consensus theory, which is solving the economic dispatch and the load restoration problems in a distributed manner; the mathematical model of the new consensus estimation method is presented in this chapter, as well x Chapter 4: presents the study cases, and their respective results, of the estimation methods to solve the economic dispatch and the load restoration problems; also, it
PAGE 18
6 contains notes and comments in direct reference and concern to the results x Chapter 5: thesis conclusions and recommendations for future studies are presented in this chapter, which is the last chapter of the thesis In the following chapter, the thesis starts with an introduction about the graph and the consensus theory.
PAGE 19
7 2. Graph and Consensus Theory Before going in the details of the consensus theory, there is an important concept which must be clearly understandable. This concept is called the Graph. 2.1 Graph Theory If we look around us in the real world, there are many situations that can be easily described or converted to a diagram which consists of a set of points, called vertices, together with lines, called edges, which connect or join certain pairs of the points within the diagrams. For instant, the subway system, where the points could represent the stop stations, and the edges represent the rails that connect these stations. The mathematical concept of a situation of such a case provides the idea of what is called a Graph. The principle of the Graph was born from the idea of the Knigsberg Bridge Problem. The Pregel River in Prussia divided the city of Knigsberg into four separate regions which were connected by seven bridges as shown in Figure 2.1 below. Figure 2.1: Bridges of Knigsberg city (1736)
PAGE 20
8 A simple diagram of the bridges in the city is illustrated in Figure 2.2 below. Figure 2.2: The Four regions and seven bridges in the Knigsberg city The inhabitants of the city wondered if it were possible to leave home, cross each of the seven bridges only once, and return home. The Leonhard Euler, a Swiss mathematician, (17071783), took the puzzle and tried to apply a mathematical method to solve the problem. He redrew each region as a vertex and each bridge as an edge connected vertices corresponding to the regions, as shown in Figure 2.3. Figure 2.3: Eulerian Circuit Figure 2.3 shows the Graph that encodes all necessary information from Figure 2.2. It is called the Eulerian circuit. Many consider the (XOHUVPHWKRGWREHWKHELUWKRIthe Graph theory [1][9][11].
PAGE 21
9 2.1.1 Graph Definition The Graph G is defined as a structure which consists a vertex set 8()), and an edge set '()), and a relation that associates with each edge whose two vertices are called the endpoints. This graph is used to model the system topology of the network. The graph G = (V, E) where 9 ^Q` is called the vertices or the nodes. E C V V is called the edges which is a set of unordered pairs of distinct vertices. When the two vertices 1, 2 in V(G) are endpoints of an edge, both 1 and 2 are called adjacent [1]. In the real world, Graph G can be an electric circuit where vertices represent sources, diodes, capacitors, et cetera, and edges represent the wires that connect them. It can be a computer network where vertices represent computers, and edges represent the communication network that connects them together. It can be the World Wide Web, where vertices represent the WebPages, and edges represent the hyperlinks, and so on. In this research, the graph is an electric power grid where the vertices represent the power generators or loads, and the edges represent the communication network that connects them as illustrated in Figure 2.4 below, specifically, for the three generators case study. It is an unordered, an undirected, and unweighted graph. Figure 2.4: Three generators (agents) system G1 G2 G3
PAGE 22
10 2.1.2 Directed and Undirected Graph As was mentioned, Graph G is a mathematical structure consists of a set of vertices 8()), and a set of edges '()), which connect the vertices according to an associated relationship. This mathematical structure can be a directed or an undirected graph. In the undirected graph, the edges that connect the vertices are not directionally fixed. The direction form a node ni to a node nj is represented by a line, with or without, arrowhead in both line ends, as seen in Figure 2.4 on the previous page. On the other hand, in the directed graph, also referred to as the digraph, the edge that connects two vertices is directed, or ordered, to gravitate in a specific direction from a node ni, or the tail node, to a node nj, called the head node. The edge direction can be easily recognized by the arrowhead that always points to the head node as illustrated in Figure 2.5 below. Figure 2.5: Directed graph Formally; )=:8,'; SDANA 8= <1,2,,J= =J@ 'C88 Assuming that Q =J@ S =NA AJ@ LKEJPO PDAJ: )=:8,'; SEHH >A DQJ@ENA?PA@ EB BKN =HH Q,S 8 ,E.A :Q,S;' :S,Q;'@ENA?PA@ KPDANSEOA G1 G2 G3
PAGE 23
11 2.1.3 A Connected and Disconnected Graph The Graph G is a connected graph if, between every two vertices in the V(G), there is a path linking them, otherwise the Graph G is called a disconnected graph. In other words, the graph is disconnected if its vertex set can be divided into two nonempty subsets where no edge connects them [10]. Figure 2.6 below illustrates the two types. (a) (b) Figure 2.6: (a) A connected graph, and (b) a disconnected graph 2.1.4 An Incidence and Adjacency Matrices In the graph G, when the edge e joins or connects the two vertices 1 and 2, these two vertices are called the adjacent. In the same time, both 1 and 2 are called the incident to the edge e. Likewise, in the graph G, two edges are adjacent if they have a vertex in common as it is shown in Figure 2.7 below. (a) (b) Figure 2.7: (a) Adjacent vertices, and (b) adjacent edges 1 2 e f 3 1 2 e 1 2 3 4 5 6 7 2 3 4 1 5 6 7 a b c d e f g i j k h
PAGE 24
12 Thus, based on the previous description, a pertinent question is raised. Are the graphs, as they are in diagram form, suitable for the computer calculations or the mathematical models to study their properties? The answer is no. Because of this, these two matrices are considered critical matrices. They are the incidence matrix and the adjacency matrix. Both of them are associated with the graph. x The incidence matrix of a graph G is n m matrix MG := (mve), where mve is the number of times (0,1, or 2) that a vertex v and an edge e are incident. x The adjacent matrix of a graph G is n n matrix AG := (auv), where auv is the number of edges that join vertices u and v. Both the incidence and the adjacency matrices of the graph G in Figure 2.6 (a) can be built as follows: 6DA EJ?E@AJ?A I=PNET; /711= 11001100110000000001000010000000100000011000011001100100000010110000000010011 6DA =@F=?AJ?U I=PNET; #77= 0101010011010001010010110001011101010011000111000 It is easily apparent to notice that the adjacency matrix is much smaller than the incidence matrix because usually graphs have more edges than vertices. This causes the adjacency matrix to require less storage computer capability which is preferred in the computer programs where the consensus algorithm is applied [10].
PAGE 25
13 2.2 Consensus Theory As mentioned, the concept of the consensus is an area of interest from many researchers in different fields of a study. To illustrate the idea of the consensus, let us consider a system of three decisionmaking units where each unit can be known as an agent, or a generator as shown in Figure 2.4. Each agent has two parts: first part is the local controller and the second part is the consensus manager. The local controller collects system data and reports its own condition, or state, to the consensus manager. The mission of the consensus manager is to analyze this information and negotiates it with other connected neighborhood agents via the communication system. As result, the consensus manager will pass the decision back to the local controller. The local controller will update its situation depending on the received information and report back its new condition to the consensus manager again in a reciprocal, or backandforth process. 2.2.1 Consensus Definition In a network of multiagents, a ConsensusPHDQVto reach an agreement regarding a certain quantity of an interest, depending on the state of all agents. A Consensus Algorithm, or a protocol, is an interaction rule that specifies the information exchange between an agent and all its neighbors in the same network [2]. 2.2.2 Consensus in Networks The topology of the system in Figure 2.4 can be represented using undirected graph )=:8,'; SDANA 8= <1,2,,J= =J@ 'C88, whereas this graph can be described as using the adjacency matrix A as mentioned prior, of a finite system of n nodes. The adjacency matrix A is n x n matrix that depends on the number of the agents. The offdiagonal entry aij is the number of edges from node i to node j. If =EF rM0 ,ErMF
PAGE 26
14 then the agent ith is communicating with the agent jth. In our case of a simple finite graph, the adjacency matrix is only a (0, 1)matrix with zeros on its diagonal. The neighbors of ith agent are denoted by: E={ F 8:E,F; ' }. For our system, the ith node has TE 4 that denotes the state value it possess. The state TE of a node can be a physical quantity, such as voltage, current, power, incremental cost, et cetera. It can be said that the system nodes, generators, or agents, have reached the consensus state if, and only if, the state value of ith node is equal the state value of jth node for all i j [3]. i.e TE=TF BKN =HH E ,F (2.1) The information discovery process for agent i is presented as follows: TEG+1= TEG+=EFrkTFGrFTEG roFE ,E=1,2,J (2.2) Where: TEG+1,TEG : are the discovered information by agent i (like average net power) E : is the neighbors that are connected to the agent i =EF : is the coefficient for information exchange between neighboring agents i and j =EF=r\0<=EF<1 EB =CAJP E =J@ F =NA ?KJJA?PA@0 KPDANSEOA The information discovery process for the whole system is formed using matrix format as follows: :G+1=:G+ #:G (2.3) :G+1=(++ #):G (2.4) :G+1=&:G (2.5)
PAGE 27
15 Where: :G=[ T1G,,TEG,,TJG] The D matrix is called the information discovery matrix, or sparse iteration matrix, for the system [18]. The coefficients =EF in matrix D have to be properly designed, because they play a critical role in reaching consensus of a system. For instant, a fullyconnected system can reach consensus in one step if =EF is selected to be equal 1J where n is the number of the system nodes. However, most of the systems are usually not fullyconnected where they can suffer from loss of their connection lines. Different methods are used to compute matrix D based on computing the coefficients =EF. Some of those methods are summarized in the following: x The Uniform Method: the weights are fixed and computed according the equation (2.6). The drawbacks of this method are the loss of the adaptivity and the slow convergence. =EF=r^1J F E1rF1J F E E=F0 KPDANSEOA (2.6) x The Metropolis Method: it is an improved method to accommodate the changes of system configuration which guarantees the stability of the information discovery
PAGE 28
16 process. The weights are updated according the equation (2.7) below. =EF= 1[maxrkJE ,JFro+ 1] F E1rF1[maxrkJE ,JFro+ 1] F E E=F0 KPDANSEOA (2.7) x The Mean Metropolis Method: a new improved method that is presented in [18]. It provides the stability and the adaptivity for the information discovery process. Their weights are updated according the equation (2.8) below. =EF= 2[JE + JF+ ] F 0E1rF2[JE + JF+ ] F 0E E=F0 KPDANSEOA (2.8) Where: : is a very small number, and can be zero for large complex systems. 2.3 Consensus Algorithm Applications Here are some applications where the consensus algorithm plays an important role:x Flocking Theory: A group of moving agents that have sensing and communicating devices in a large environment. The mission of the consensus algorithm in here is to make every agent reach the same velocity of its neighbors. The system of the network is a dynamic system with a dynamic topology. The topology is an agent state dependence, and it is computed locally for each agent. A good example for this is a group of nonpilot planes [2][12]. x Rendezvous in Space: In this case, the position of the agent is very important which makes the system an interactive position topology. This application is easier than the Flocking Theory because it does not require an agenttoobstacle
PAGE 29
17 clash avoidance [13]. x Fast Consensus in SmallWorlds: Using semidefine convex programming, where the weight of the network is considered, leads to a slight increase in algebraic connectivity of the network, where the speed of the convergence of the consensus algorithms is measured. By keeping the network weights fixed, the topology can be designed to achieve a relatively high algebraic connectivity. x Distributed Sensor Fusion in Sensor Networks: The above applications are considered as distributed sensor fusion. Distributed averaging problems require implementing the Kalman filter. The average of the inputs in the sensor networks is dynamically computed [14]. x Distribution Formation Control: In multivehicle systems, the design and analysis framework of distributed formation controllers uses vectors of relative positions of neighboring vehicles. In order the agents, as multivehicle, to move in formation, the agents have to cooperate, which requires consent and collaboration of every agent in the formation. It is clearly a consensus problem [16]. x Economic Dispatch and Load Restoration Problems in Power System: a conventional centralized control problem can be solved in a distribution manner by applying the consensus theory. Surly, this requires to choose the appropriate measures as a consensus variables [5][8][18]. More details are presented in the next chapter.
PAGE 30
18 3. Economic Dispatch and Load Restoration Problems 3.1 Economic Dispatch Problem The main target here is to get perfect use of serving equipment as much as possible with parallel to the highest financial benefits. In a power system, the Economic Dispatch is an optimal operation point of each power generator where the demand power is met, but the total generation cost is the lowest [6]. Several methods are used to solve the Incremental Cost equations, like setting value of Lambda and solving for generation values, or solving the value of Lambda directly for a specific load demand with different algorithms. Modern techniques use linear and nonlinear programming like PiecewiseLinear fuelCost functions and Quadratic programming of the cost function. Usually, a cost fuel curve of any power generator is formulated by quadratic function as follows [7]: The fuel cost equation: %E:2)E;= E+E2)E+ E2)E2 (3.1) The Total fuel cost equation: %6KP=H= %E:2)E;JE=1 (3.2) Under the balance condition: 2& rF 2)EJE=1 = 0 (3.3) Where: %E : the fuel cost of the EPD generator E,E,E : the cost coefficients of the EPD generator 2&: the total demanded power
PAGE 31
19 2)E: the generated power of the EPD generator The definition of the Incremental Cost IC for each generator is the same as the conventional economic dispatch: +%E= %E(2)E)2)E = E E =1,2,,J (3.4) By using the discretetime consensus algorithm form then the Incremental Cost by using the first order discrete consensus algorithm is as follows [5]: E>G+1?= @EFJF=1F>G? E =1,2,,J (3.5) Where: @EF : is the ( E ,F ) entry of the rowstochastic matrix Dn depends on the Laplacian matrix E>G+1? : updating IC of EPD takes in account the connected FPD generator to the EPD generator In order to include the power balance constraints in the equation (3.3), the power balance error 2 is defined as follows: 2= 2& rF 2)EJE=1 (3.6) Finally, the updating IC of the leader becomes as follows: E>G+1?= @EFJF=1F>G? + 2 E =1,2,,J (3.7) Where: : is a positive scalar, and it is called the convergence coefficient that controls the convergence speed of the leader generator or the leader agent. In the case where the power generation constraints are applied, the following conditions must be taken in account in the algorithm [5][7][8].
PAGE 32
20 P 2)E= 2)E_I=T ,SDAJ 2)E> 2)E_I=T 2)E= 2)E ,SDAJ 2)E_IEJ rQ 2)ErQ 2)E_I=T2)E= 2)E_IEJ ,SDAJ 2)E< 2)E_IEJ 3.2 Load Restoration Problem One of the consequences, after the protection system gives its orders to the circuit breakers to open, in order to isolate a faulty area in the power network, some unfaulted loads may trip and become out of service. Returning these loads back to the service as fast as possible, is one of the important aspects in the power networks. This action takes into account priority and capacity of each load. This procedure (retuning unfaulted loads back to the service) is called in the power system the Load Restoration[18][19]. This kind of control task has been achieved in past years by using different computing algorithms, like genetic algorithm, particle swarm optimization, et cetera. A major drawback of these methods appears to be their need to a powerful central controller in order deal with a vast amount of information throughout the network. This leads to an extra cost and suffers from a singlepoint failure besides other drawbacks of a central controller that were mentioned earlier. In absence of question, solving the load restoration problem in a distribution control scheme is an intelligent solution to overcome all central FRQWUROOHUV drawbacks. Recently, MultiAgent System (MAS) is an area of the interest, and different algorithms are applied to solve the load restoration problem. Some of them work with only radial power structures; others work with ring power structure. One advanced algorithm is presented in the reference [18]. It is capable to work even with a complex power structure, i.e., radial, ring, or mixed, because the proposed algorithm is independent of a system configuration.
PAGE 33
21 In this case, the total net power of each agent is required for the calculation, and during stable normal operation the average of the total net power must be equal to zero. :AM = TEKJE=1J = 0, E=1,2J (3.8) Where: : : is discovered information which is the total net power of the agent ith J : is the total number of the agents The overall information updating process i.e., the total average net power for each agent, is modeled the same as the equation (3.7) but without the balance error dimension. :>G+1?= &:>G? (3.9) Where: & : is the sparse iteration matrix. During a post fault period, the total net power equation (3.8) cannot be fulfilled because of the negative power shortage from the unfaulted agents, or loads. This requires immediate load restoration procedure. The Optimal load restoration decision can be obtained by satisfying coming two conditions: 1. Maximizing the capacity of restored loads and assuring higher priority loads be served first, i.e., I=T 2E0E=1.2.E (3.10) Where: 2E : is the priority index associate with ith load 2.E : is the amount of power for an agent ith needs to be restored 2. Sum of the total loads to be restored must not exceed the total generated power,
PAGE 34
22 i.e., 2)E0E=1rF2.E0E=1 rR0 (3.11) Where: 2)E : is the amount of generated power for an agent ith. Identifying lost loads to be restored can be easily done by using the 01 Knapsack Problem, which is a combinatorial optimization problem. Having a group of items where each item has its own weight and corresponding value, and finding the number of each item to be added in a collection with a condition of the total collection weight, is less than or equal to a given limited amount but the total value is as large as possible. Its mathematical model is summarized as follows [21]: P maxB:T1,T2,,TJ;= LEJE=1TE SEJE=1TE<# TE {0,1} (3.12) Where: LE : is the value of an agent ith SE : is the weight of an agent ith # : is the limited total weight of the collection The 01 knapsack problem can identify restored loads based on three factors, greedy by profit, or value, greedy by weight, or greedy by profit density. Since these loads are identified, the consensus algorithm will be activated to achieve a power balance again where the WRWDOQHWSRZHUIRUHDFKV\VWHPVDJHQWVKRXOGFRQYHUJHWR]HUR 3.3 Estimation Information Matrix in the Consensus Algorithm Instead of computing the information matrix D in equations (3.5) and (3.9) based on the calculation methods that are presented in the chapter two, the estimation adaptive
PAGE 35
23 techniques are applied to estimate it. In this thesis, Matlab codes were implemented based on the Gradient Algorithm (GA) and the Recursive Least Square Algorithm (RLS) to solve both the economic dispatch and the load restoration problems. The final forms of those estimation methods are presented in the following sections. The Complete mathematical derivation for both estimation algorithms is presented in the appendix A. 3.3.1 Gradient Algorithm Estimation Form E:G+1;= @EEE:G;+ @EFF 3ErcF:G; rF E:G;rg (3.13) @EE= 1 rF @EFF 3E E =1,2,,J (3.14) Inspired by the adaptive control theory, we propose the following cost function to be minimized [22]. min@rEF12 [E(G+1) rF Â§E(G+1)]2 (3.15) @EF(G+1)= @EF(G) rF [E(G+1) rF Â§E(G+1)] E>G+1?@rEF (3.16) @EF(G+1)= @EF(G) rF [E(G+1) rF Â§E(G+1)] [F(G) rF E(G)] (3.17) @EF(G+1)= @EF(G) rF E:G;[E(G+1) rF Â§E(G+1)] (3.18) E:G;=rc F:G; rF E:G;rg F=1,2,,3E (3.19) In the equation (3.18), Â§E is the average of the neighbors of a EPD node, and it is computed as follows: Â§E(G+1)= 1JE F(G+1)F 3E (3.20) The initial values: @EF:0;=0 ErMF =J@ @EE:0;=1rF@EF:0;F 3E ErMF =0.5 ,0.1 KN HAOO is a scalar to increase the speed of the convergence.
PAGE 36
24 3.3.2 Recursive Least Square Algorithm Estimation Form @EF(G+1)= @EF(G) rF 2E:G;E:G;[E(G+1) rF Â§E(G+1)] (3.21) E:G;=rc F:G; rF E:G;rg F=1,2,,3E (3.22) 2E:G;= 2E:GrF1;+ 2E:GrF1;E:G;E:G;6 2E:GrF1;1+ E:G;62E:GrF1;E:G; (3.23) In the equation (3.21), Â§E is the average of the neighbors of a EPD node, and it is computed as follows: Â§E(G+1)= 1JE F(G+1)F 3E (3.24) The initial values: @EF:0;=0 ErMF =J@ @EE:0;=1rF@EF:0;F 3E ErMF 2E:0;=2E+ ,2E>0 is a scalar matrix to increase the speed of the convergence.
PAGE 37
25 4. Study Cases and Results To verify our new estimation methods of computing average consensus, in both cases, the Economic Dispatch and the Load Restoration problems, they were tested on cases that had been studied before. We compared our results with theirs to make sure the performance of our new estimation algorithms gave the same correct results of the previous studies. 4.1 Three Generators System for Economic Dispatch Problem The system contains three generators, or agents, which provide power supply to an electric load PD. The system parameters are summarized in the table 4.1 below [7]: Table 4.1: Three generators; system parameters Agent Or Generator Cost Coefficients used in equation (3.1) Power initial [MW] [$/hr] [$/MWhr] [$/MW2hr] 1st 561 7.92 0.001562 450 2nd 310 7.85 0.001940 300 3rd 078 7.97 0.004820 100 In this case, the new estimation method is applied to solve the economic dispatch problem. Here, instead of computing the rowstochastic matrix D, based on the Laplacian Matrix L, the gradient algorithm is used to estimate it. The communication topology of this system is the same as Figure 1.1 (b). The algorithm will solve the economic dispatch problem so that the Incremental Cost of each generator converges to the same optimal value. The next sections show our results based on the estimation method.
PAGE 38
26 4.1.1 Three Generators System with New Estimation Method using Gradient Algorithm without Power Constraints In this case, there were no produced power limits for the system generators. The situationV summary is as follows: 1The system parameters were taken from the table 4.1 2The rowstochastic matrix D was estimated by using the Gradient Algorithm 3The required demanded power was 850 MW and 950 MW 4The convergence gradient gain coefficient =0.5 (a) (b) (c) Figure 4.1: Three generators using GA; ,&VDQGpower (no power constraints) As it is see in Figure 4.1 (a), all the three Incremental Costs 1 ,2 =J@ 3 converged very fast to the same optimal value =9.1483 $//9D. After 1 second, the demanded power increased to 950 MW. We notice that the leader (agent 1), red line, responded faster than the others after the change happened, then it raised the other agents to a new Incremental Cost value, and after 1.4 sec they reached to the consensus again, which is a new optimal value =9.295 $//9D. In both stages, the generated power reached the demanded power quickly. Because there were no power constraints, we notice that all agents produced power without any limits as it is shown in Figure 4.1 (c).
PAGE 39
27 Also the power balance had been satisfied as it is shown in Figure 4.1 (b). Our results are exactly the same as the results in the reference [5] where the Incremental Cost was computed based on the calculation methods in equations (2.6), (2.7), and (2.8). 4.1.2 Three Generators System with New Estimation Method using Gradient Algorithm with Power Constraints In this case, there were produced power limits for the system generators. The sitXDWLRQVVXPPDU\LVDVIROORZV 1. The system parameters were taken from the table 4.1 except @(1)=0.00128 $/MW2hr so that agent one can produce more than 600 MW 2. The rowstochastic matrix D was estimated by using the Gradient Algorithm 3. The required demanded power was 850 MW and 950 MW 4. The convergence gradient gain coefficient =0.5 5. The generator maximumV limits were [ 600 400 200 ] MW 6. The generator minimumV limits were [ 150 100 050] MW (a) (b) (c) Figure 4.2 Three generators using GA; ,&VDQGpower (with power constraints) In this case, the generators power limits were applied in solving the Incremental Fuel Cost. As we see in Figure 4.2 (a), all the three Incremental Costs 1 ,2 ,and 3
PAGE 40
28 converged very fast to the same optimal value =8.576 $/MWh. After 1 second, the demanded power increased to 950 MW. We noticed that the leader (agent 1), red line, responded faster than the others after the change happened, then it raised the other agents to a new Incremental Cost value, and after 1.6 sec they reached to the consensus again, which is a new optimal value =8.852 $/MWh. In both stages, the generated power reached the demanded power quickly. Because of the power constraints, we notice that the generator one (the leader) stuck on 600 MW as a result of its power limits as shown in Figure 4.2 (c). Also, the power balance and the power constraints had been satisfied as shown in Figure 4.2 (b). Our results are exactly the same as the results in the reference [7] where the Incremental Cost was computed based on the calculation methods. 4.2 Five Generators System for Economic Dispatch Problem The system contains five generators or agents provide power supply to an electric load PD. The system parameters are summarized in the table 4.2 below [7]: Table 4.2: Five generators; system parameters Agent or Generator Cost Coefficients used in equation (3.1) Power initial [MW] [$/hr] [$/MWhr] [$/MW2hr] 1st 561 7.92 0.001562 200 2nd 310 7.85 0.001940 250 3rd 078 7.97 0.004820 100 4th 561 7.92 0.001562 200 5th 078 7.80 0.004820 100
PAGE 41
29 In this case, the gradient algorithm and the recursive least square algorithm are used to estimate the rowstochastic matrix D. The communication network of this system has different topologies as it is shown in Figure 4.3 below. The Incremental Cost algorithm will solve the economic dispatch problem so that the Incremental Cost of each generator converges to the same optimal value. The next sections show our results based on the estimation methods. Figure 4.3: Five generators; different system topologies 4.2.1 Five Generators with New Estimation Method using Gradient Algorithm Three different cases for the initial values of the adjacency matrix for different system topologies were studied. The situationV summary is as follows:1The system parameters were taken from the table 4.2 2The rowstochastic matrix D was estimated by using the Gradient Algorithm 3The required demanded power was 850 MW and 950 MW 4The convergence gradient gain coefficient =0.5 5Different system topologies were used as it is shown in Figure 4.3 6No power constraints were applied G1 G2 G3 G4 G5 G1 G2 G3 G4 G5 G1 G2 G3 G4 G5 G1 G2 G 3 G 4 G5
PAGE 42
30 4.2.1.1 Five Generators using GA; Guessing Initial Values ==n.n @EF=@FE=0.0 ,@EE=1rFr@EFEF=1:E ,ErMF Âœ @K= 1.00.00.00.00.00.00.00.01.00.00.00.00.00.01.00.00.00.01.00.00.00.00.00.01.0 (a) (b) Figure 4.4: Five generators using GA; ,&VDQGpower (dij=dji=0.0)
PAGE 43
31 4.2.1.2 Five Generators using GA; Guessing Initial Values =rMn.n @EF=@FErM0.0 ,@EE=1rFr@EFEF=1:E ,ErMFÂœ @K= 0.100.300.200.250.150.300.200.250.050.100.100.100.100.050.100.400.200.400.150.100.150.050.200.100.05 (a) (b) Figure 4.5: Five generators using GA; ,&VDQGpower (dij=djirM0.0)
PAGE 44
32 4.2.1.3 Five Generators using GA; Guessing Initial Values rMrMn.n @EFrM@FErM0.0,@EE=1rFr@EFEF=1:E ,ErMFÂœ @K= 0.300.300.150.050.200.150.200.200.200.100.200.150.300.200.050.400.250.300.150.150.150.050.200.100.50 (a) (b) Figure 4.6: Five generators using GA; ,&VDQGpower (dijrMdjirM0.0) It can be seen in Figures 4.4 (a), 4.5 (a), and 4.6 (a) by applying the gradient algorithm, all five Incremental Costs 1 ,2 ,3 ,4,and 5 converged very fast to the same optimal value =8.666 $/MWh. After 1 second, the demanded power increased to 950 MW. It is noticeable that the leader (agent 1), red line, responded faster than the others after the change happened, then it raised the other agents to a new Incremental Cost value, and after 1.1 sec they reached to the consensus again, which is a new optimal
PAGE 45
33 value =8.756 $/MWh. It can be easily noticed that in Figure 4.5(a) where dij GMLÂ0.0, the agents reached the consensus faster than the other cases because of the symmetry of the initial matrix. Figures 4.4 (b), 4.5 (b), and 4.6 (b) show the total generated power by the agents. When the demanded power changed from 850 MW to 950 MW after 1 second of operation, all agents increased their produced power to meet the demanded power. Therefore, the power balance had been satisfied. Our results are exactly the same as the results in the reference [5] where the Incremental Cost was computed based on the calculation methods. 4.2.2 Five Generators System with New Estimation Method using Recursive Least Square Algorithm Three different cases for the initial values of the adjacency matrix for different system topologies were studied. 7KHVLWXDWLRQVVXPPDU\LVas follows:1The system parameters were taken from the table 4.2 2The rowstochastic matrix D was estimated by using the Gradient Algorithm 3The required demanded power was 850 MW and 950 MW 4Different system topologies were used as it is shown in Figure 4.3 5No power constraints were applied 6The Covariance 0DWUL[Vinitial LK=10+
PAGE 46
34 4.2.2.1 Five Generators using RLS; Guessing Initial Values ==n.n @EF=@FE=0.0 ,@EE=1rFr@EFEF=1:E ,ErMF Âœ @K= 1.00.00.00.00.00.00.00.01.00.00.00.00.00.01.00.00.00.01.00.00.00.00.00.01.0 (a) (b) Figure 4.7: Five generators using RLS; ,&VDQGpower (dij=dji=0.0)
PAGE 47
35 4.2.2.2 Five Generators using RLS; Guessing Initial Values =rMn.n @EF=@FErM0.0 ,@EE=1rFr@EFEF=1:E ,ErMFÂœ @K= 0.100.300.200.250.150.300.200.250.050.100.100.100.100.050.100.400.200.400.150.100.150.050.200.100.05 (a) (b) Figure 4.8: Five generators using RLS; ,&VDQGpower (dij=djirM0.0)
PAGE 48
36 4.2.2.3 Five Generators using RLS; Guessing Initial Values rMrMn.n @EFrM@FErM0.0,@EE=1rFr@EFEF=1:E ,ErMFÂœ @K= 0.300.300.150.050.200.150.200.200.200.100.200.150.300.200.050.400.250.300.150.150.150.050.200.100.50 (a) (b) Figure 4.9: Five generators using RLS; ,&VDQGpower (dijrMdjirM0.0) It can be seen in Figures 4.7 (a), 4.8 (a), and 4.9 (a) by applying recursive least square algorithm, all five Incremental Costs 1 ,2 ,3 ,4,and 5 converged very fast to the same optimal value =8.666 $/MWh. After 1 second, the demanded power increased to 950 MW. It was noticeable that the leader (agent 1), yellow line, responded
PAGE 49
37 faster than the others after the change happened, then it raised the other agents to a new Incremental Cost value, and after 1.05 seconds they reached the consensus again, which is a new optimal value =8.756 $/MWh. It can be easily noticed that in Figure 4.8(a) where dij GMLÂWKHDJHQWVUHDFKHGthe consensus faster than the other cases because of the symmetry of the initial matrix. Overall, the performance of RLS algorithm has smoother convergence to the optimal value than the GA algorithm, and this can be easily noticeable when their results are compared. Figures 4.7 (b), 4.8 (b), and 4.9 (b) show the total produced power by all agents. When the demanded power changed from 850 MW to 950 MW after 1 second of operation, all agents increased their produced power to meet the demanded power. So the power balance had been satisfied. Our results are exactly the same as the results in the reference [5] where the Incremental Cost was computed based on the calculation methods in equations (2.6), (2.7), and (2.8). 4.2.3 Five Generators with New Estimation Method using GA and RLS algorithms where the System Topology Changes with Time In this case, WKHV\VWHPWRSRORJ\FKDQJHVZLWKWLPH7KHVLWXDWLRQVVXPPDU\LVas follows:1. The system parameters were taken from the table 4.2 2. The rowstochastic matrix D was estimated by using the Gradient Algorithm and the Recursive Least Square Algorithm with do = 0.0 for both algorithms 3. The required demanded power was 850 MW and 950 MW 4. The system topology was changing with time as it is shown in Figure 4.10 on the next page 5. No power constraints were applied
PAGE 50
38 The topology of the system changes with time as follows:Figure 4.10: Five generators; changing sequence of the system topology (a) (b) Figure 4.11: Five generators using GA; ,&VDQGpower (topology changes with time) G1 G2 G 3 G4 G5 G1 G2 G4 G5 G3 (0.0 to 0.2) sec (0. 2 to 0. 4 ) sec G1 G2 G3 G4 G5 G1 G2 G3 G4 G5 (0.4 to 0.6) sec (0.6 to 2.0) sec
PAGE 51
39 (a) (b) Figure 4.12: Five generators using RLS; ,&VDQGpower (topology changes with time) It can be seen from Figures 4.11(a) and 4.12(a), by using the gradient algorithm and the recursive least square algorithm, all five Incremental Costs 1 ,2 ,3 ,4,and 5 converged very fast to the same optimal value =8.666 $/MWh and =8.756 $/MWh corresponding to the demanded power from 850 MW to 950 MW. Figures 4.11(b) and 4.12 (b) illustrate the total generated power. It is noticeable that the total generated power increased to meet the demanded power. This case lead to the conclusion the connected agents reached the consensus even though their topology changed with time. 4.2.4 Five Generators with New Estimation Method using GA and Agents 4 and 5 are Become Disconnected In this case, two agents became disconnected from the rest of the system. What will happen to the system convergence and the produced power? The changing sequence of the system topology is illustrated in Figure 4.13 on the next page. The agents 4 and 5 have been selected as the disconnected agents after 1.2 sec of operation. The situationV
PAGE 52
40 summary is as follows:1. The system parameters were taken from the table 4.2 2. The rowstochastic matrix D was estimated by using the Gradient Algorithm 3. The required demanded power was 850 MW 4. The convergence gradient gain coefficient =0.5 5. No power constraints were applied. Figure 4.13: Five generators; agents 4 and 5 become disconnected
PAGE 53
41 (a) (b) (c) Figure 4.14: Five generators using GA; ,&VDQGSower (two agents 4 and 5 become disconnected) It can be seen from Figure 4.14 (a), by using the gradient algorithm, all five Incremental Costs 1 ,2 ,3 ,4,and 5 converged very fast to the same optimal value =8.666 $/MWh. After 1.2 sec of operation, two agents (4 & 5) became disconnected from the rest of the system while the demanded power still at 850 MW. It can be noticed that the other three agents (1, 2, and 3) converged to a new Incremental Cost value =9.148 $/MWh. As the system lost the connection with the disconnected agents so it kept the last Incremental Costs of them just before they became disconnected. Because the system lost part of the generated power from the disconnected agents, as it is seen in Figure 4.14 (b), the other agents had to compensate the shortage in the generated power, and this what exactly happened in a few milliseconds as it illustrated in Figure 4.14 (c). The agents 1, 2, and 3 increased their produced power to match the demanded power of the system. Finally, the power balance had been satisfied.
PAGE 54
42 4.2.5 Five Generators with New Estimation Method using RLS and Check the Necessity of the Reaching Consensus This case is to FKHFNWKHQHFHVVLW\WKDWVDLG,QRUGHUWKHDJHQWVto reach the consensus, the sum of all columns of the adjacency matrix d must be equal to RQHVRWKHsummation of all rows (red lines) and columns (blue lines) were plotted in order to check whether this necessity hold or not. The situationV summary is as follows:1. The system parameters were taken from the table 4.2 2. The rowstochastic matrix D was estimated by using the RLS and do = 0.0 3. The required demanded power was 850 MW 4. No power constraints were applied. The system topology was changing with time as it is shown in Figure 4.15 below. Figure 4.15: Five generators; changing sequence of system topology
PAGE 55
43 (a) (b) Figure 4.16: Five generators using RLS; ,&VDQGpower (Po = 0.01) Figure 4.17: Five generators; adjacency URZVDQGFROXPQVVXPPDWLRQ (Po = 0.01)
PAGE 56
44 (a) (b) Figure 4.18: Five generators using RLS; ,&VDQGpower (Po = 10) Figure 4.19: Five generators; adjacency URZVDQGFROXPQVsummation (Po = 10)
PAGE 57
45 It can be seen this necessity was accomplished when Po = 0.01 in Figure 4.17, but it did not hold as Po increased as in Figure 4.19. It is noticeable the system reached the consensus even though the sum of columns of the rowstochastic matrix D did not equal one. From this ironic result, it can be concluded that this proposed necessity has not to be held true in order for the system to reach the consensus. Instead, the average of the FROXPQVVXPPDWLRQRIthe rowstochastic matrix D must be equal to one. 4.3 IEEE 16Bus Test Power System for the Load Restoration Problem In this case, the system contains 16 buses compound of generation and load agents. The system configuration is show in Figure 4.20 below: Figure 4.20: The 16bus test power system (source ref. [18]) It is a standard IEEE test power system. The arrows resemble the power loads, the circles resemble the power generators, the red squares resemble the circuit breakers in the close position, and the green squares resemble the circuit breakers in the open position. In this case of study, the power loses of the transmission lines are neglected.
PAGE 58
46 Data of the 16bus system in Figure 4.20 on the previous page can be easily summarized in the table 4.3 below [18]: Table 4.3: 16Bus power system; system data Agent or Bus Neighbors 2)E [MW] 2.E [MW] :EK [MW] Priority 1 th 2,5 40 0 40 2 th 1,3,5,10 40 0 40 3 th 2,10 50 0 50 4 th 10,11 0 25 25 P2 5 th 1,2,6 0 35 35 P2 6 th 5,7,9 0 20 20 P1 7 th 6,8,9 0 15 15 P2 8 th 7,9 0 25 25 P1 9 th 6,7,8,11,15 0 5 5 P1 10 th 2,3,4 0 30 30 P2 11 th 4,9,12 40 0 40 12 th 11,13 0 45 45 P2 13 th 12,14 0 10 10 P2 14 th 13,16 0 40 40 P2 15 th 9 30 0 30 16 th 14 50 0 50 In the table above; 2)E is the agent ith local generation, 2.E is the agent ith local load, :EK is the agent ith local net power, and P1~2 is the agent ith load priority with P1 > P2. The assumption here according to [20] is a sudden fault occurs to the generator on the bus 11 (agent 11) which led the protection system to react immediately to isolate the fault by opening some circuit breakers. The system configuration of the post fault period is illustrated in Figure 4.21 on the next page.
PAGE 59
47 Figure 4.21: The 16bus system; post fault configuration (source ref. [18]) As a result the power protection reaction, the system lost eight unfaulted loads (outofservice) which attached to the agents 4 and 6 ~ 12 (shaded area). No doubt, these loads should be restored, as fast as possible, based on the total net power available and their priority. So, the load restoration process has to be activated to return back the lost loads. For such case, very important information like the total net power, WKHDJHQWVindexes, and the demanded power of the unfaulted loads are extremely required. To solve the load restoration problem for the situation above in a distribution fashion, the information discovery matrix M is very important. Each agent has to converge to the same M matrix. According to the reference [18], every agent in the system is initially created with the n3 matrix. In this initial matrix only two nonzero elements can be found. Mi1 indicates the agent index (ith) if it is working normally or (0) if it is not. Mi2 indicates the outofservice agent index (ith) if it is ready for restoration or (0) if it is not. Mi3 indicates the local net power for the working agent or the demanded power of the ready for restoration agent. Clearly in the Mi,1~3 matrix, the ith agent row could be [i 0 PLi ] if it is working agent or [0 i PLi ] if it is ready for restoration agent.
PAGE 60
48 Because every agent has to converge to the same information matrix M, the information discovery algorithm should be applied to each element of the initial matrices. Here, instead of apply information discovery algorithm based on the calculation methods, which are proposed in the reference [18], a new advanced information discovery algorithm which is based on the estimation methods like, the gradient algorithm, is applied. The final converged matrix M contains all necessary information required for the load restoration. The first column shows all normally working agents, the second column shows all ready for restoration agents, and finally, the third column shows the local net power for the agents whether they are working normally or ready for the restoration as it is shown in the table 4.4 below. Table 4.4: 16Bus power system; final converged of information matrixM Initials matrices for the agents Final converged matrix M 1st column 2nd column 3rd column 1/16 0 40/16 2/16 0 40/16 3/16 0 50/16 0 4/16 25/16 5/16 0 35/16 0 6/16 20/16 0 7/16 15/16 0 8/16 25/16 0 9/16 5/16 0 10/16 30/16 0 0 0/16 0 12/16 45/16 13/16 0 10/16 14/16 0 40/16 15/16 0 30/16 16/16 0 50/16
PAGE 61
49 Using the final converged matrix M as input to the 01 knapsack problem, the exact ready for the restoration agents with their associated power can be easily identified to reconnect them back to the system as fast as possible. At the end, the balanced system is achieved. The final arrangement of our example is illustrated in Figure 4.22 below for the 01knapsack greedy by value. The agents with red circuits were not selected by the 011knapsack greedy by value for the restoration. Figure 4.22: The 16bus system; after restore configuration (source ref. [18]) The operation sequence in the Matlab code of this case was as follows: 1Total Number of iterations N = 800. 2Fault occurred at N = 300 3Load restored at N = 500 4The convergence gradient gain coefficient =0.0001
PAGE 62
50 4.3.1 IEEE 16Bus Test Power System with New Estimation Method using GA and 01 knapsack Value Based Figure 4.23: The 16bus system; information matrixM convergence Figure 4.24: The 16bus system; total net power convergence (knapsack value based)
PAGE 63
51 Instead of using the consensus algorithm based on the calculation methods that were proposed in the reference [18], a new advanced estimation method using the gradient algorithm was applied, and the 16bus system reached to the same consensus results as that presented in the reference [18]. For instant, the information discovery matrixM was initiated with initial values corresponding to every agent as in the table 4.4, then it converged to the final converged matrixM shown in the same table. Figure 4.23 shows the agent convergence process for each matrix column and Figure 4.24 shows the system total average net power convergence in the three stages process; the pre fault, the post fault, and the after fault period. In each stage, the system converged to the net power initial values. When the system was working normally (1~300 iterations in Figure 4.24) all agents converged to zero which is clear if we take the average of the agents in the column five of the table 4.3 on the page 46. During the post fault period (300~500 iterations in Figure 4.24) and because of the outofservice agents, remains working agents converged to a positive value which is 7.81 MW. Those working agents can be easily identified using the first column of the final converged matrixM ((40+40+50351040+30+50)/16 = 7.81). Since the average total net power is positive, there is a necessity to restore some, or all outofservice agents, depending on the system capacity, and their priorities. Finding such agents (their indexes) for the load restoration is very easy by extracting the information from the second column of the final converged discovery matrixM. Sometimes and because of SRZHUGHPDQGVVKRUWDJH, not all outofservice agents can be restored. To identify agents that can be restored, the 01 knapsack is applied to perform such selection based on the DJHQWVSULRULWLHV and capacities. After
PAGE 64
52 reconnection outofservice agents as it is shown in Figure 4.24 (500~800 iterations), the total net power converged back to zero because the 01 knapsack value based restored 100% of the demanded power available (7.8116 = 125 MW). The 01 knapsack selected agents was; agent 4(25), agent 8(25), agent 10(30), and agent 12(45). 4.3.2 IEEE 16Bus Test Power System with New Estimation Method using GA and 01 knapsack Density Based Figure 4.25: The 16bus system; information matrixM convergence Figure 4.26: The 16bus system; total net power convergence (knapsack density based)
PAGE 65
53 This time, the 01 knapsack density based was applied for the load restoration. By applying the 01 knapsack density based, only 96% of the demand power available (7.811696% = 124 MW) was restored. The 01 knapsack selected agents was; agent 4(25), agent 6(20), agent 7(15), agent 8(25), agent 9(5), and agent 10(30). As it is seen in Figure 4.27 (500~800 iterations), the average total net power converged to a small positive number which is (5/16=0.3) as a result of 96% of the 01 knapsack density based. Both sections 4.3.1 and 4.3.2 prove the capability of using our new advanced consensus algorithm based on the estimation methods like the gradient algorithm for solving such power problem. Moreover, they prove that it is needless to apply traditional calculation methods like those which are presented in the references [5] and [18].
PAGE 66
54 5. Conclusion and Future Work 5.1 Conclusion In this thesis, a new concept of solving the economic dispatch problem and the load restoration problems is presented. As a part of solving both problems in a distribution fashion, an important information matrix is required for updating system status so a system can reach what is called the consensus. This matrix is called the information discovery matrix, and it is computed based on specific calculation methods. Instead of using the existing calculation methods of computing the information discovery matrix, adaptive techniques, like the gradient algorithm and the recursive least square algorithm, are applied to estimate above mentioned matrix. This advanced work is extremely useful to save time consumed during the calculation process of reaching consensus especially in the case of the bulk network systems. Our results of reaching the consensus totally matched previous results of cases that had used calculation methods of reaching the consensus. No doubt, this work proves the importance of the estimation methods in the reaching consensus and their capability of solving power problems in a distribution manner which helps to overcome the drawbacks of the central controller. In this thesis, chapter two gives an important background about the graph and consensus theory. The chapter three gives the theoretical analysis of applying the consensus algorithm to solve the economic dispatch and the load restoration problems. The estimation mathematical model is presented in this chapter. Our case studies and their results are presented in the chapter four. The comments and notes on these results are presented here also. Finally, the chapter five gives the conclusion and the future work of this research.
PAGE 67
55 5.2 Future Work Some important steps have to be taken as further investigation to complement this work of study in the consensus algorithm based on the estimation techniques. These future researches can be summarized in the following points: x Study the case of a leader selection in a case if the system is a weighted, an ordered, and a directed graph. x Study the case of taking into account the power losses in the transmission lines of the power network. x Study deeply the case of the disconnected agents whether the disconnection happen in the communication network only, the power lines only, or both of them. x Study the case of losing the V\VWHPVOHDGHU'RVHWKHV\VWHPDEOHWRVHOHFWanother leader or not? And how? x Study the case of clastericity when the system is divided to several connected groups and each group converges to its own consensus. All in all, all these mentioned future researches need more of an advanced code that can take into account many possibilities and assumptions in order get a generally flexible algorithm. Such an algorithm can be easily applied in the real power networks.
PAGE 68
56 REFERENCES [1] R. Diestel, Graph theory, 3rd ed. Berlin: Springer, 2005. [2] R. OlfatiSaber, J. A. Fax, and R. M. Murray, "Consensus and Cooperation in Networked MultiAgent Systems," Proceedings of the IEEE, vol. 95, pp. 215233, 2007. [3] R. Wei, R. W. Beard, and E. M. Atkins, "A survey of consensus problems in multiagent coordination," in American Control Conference, 2005. Proceedings of the 2005, 2005, pp. 18591864 vol. 3. [4] R. A. Gupta and C. MoYuen, "Networked Control System: Overview and Research Trends," Industrial Electronics, IEEE Transactions on, vol. 57, pp. 25272535, 2010. [5] Z. Ziang and C. MoYuen, "Incremental cost consensus algorithm in a smart grid environment," in Power and Energy Society General Meeting, 2011 IEEE, 2011, pp. 16. [6] T. L. Baldwin and E. B. Makram, "Economic wdispatch of electric power systems with line losses," in System Theory, 1989. Proceedings., TwentyFirst Southeastern Symposium on, 1989, pp. 1317. [7] A. J. Wood and B. F. Wollenberg, Power generation, operation, and control, 2nd ed. New York: J. Wiley & Sons, 1996. [8] Z. Ziang and C. MoYuen, "Convergence Analysis of the Incremental Cost Consensus Algorithm Under Different Communication Network Topologies in a Smart Grid," Power Systems, IEEE Transactions on, vol. 27, pp. 17611768, 2012. [9] R. J. Wilson, Introduction to graph theory, 4th ed. Harlow: Longman, 1996. [10] J. A. Bondy, U. S. R. Murty, and SpringerLink (Online service). (2008). Graph Theory. Available: http://0dx.doi.org.skyline.ucdenver.edu/10.1007/9781846289705 [11] D. B. West, Introduction to graph theory, 2nd ed. Upper Saddle River, NJ: Prentice Hall, 2001. [12] R. OlfatiSaber, "Flocking for multiagent dynamic systems: algorithms and theory," Automatic Control, IEEE Transactions on, vol. 51, pp. 401420, 2006.
PAGE 69
57 [13] J. Cortes, S. Martinez, and F. Bullo, "Robust rendezvous for mobile autonomous agents via proximity graphs in arbitrary dimensions," Automatic Control, IEEE Transactions on, vol. 51, pp. 12891298, 2006. [14] R. OlfatiSaber and J. S. Shamma, "Consensus Filters for Sensor Networks and Distributed Sensor Fusion," in Decision and Control, 2005 and 2005 European Control Conference. CDCECC '05. 44th IEEE Conference on, 2005, pp. 66986703. [15] V. M. Preciado and G. C. Verghese, "Synchronization in Generalized ErdsRnyi Networks of Nonlinear Oscillators," in Decision and Control, 2005 and 2005 European Control Conference. CDCECC '05. 44th IEEE Conference on, 2005, pp. 46284633. [16] J. A. Fax and R. M. Murray, "Information flow and cooperative control of vehicle formations," Automatic Control, IEEE Transactions on, vol. 49, pp. 14651476, 2004. [17] Z. Ziang and C. MoYuen, "The leader election criterion for decentralized economic dispatch using incremental cost consensus algorithm," in IECON 2011 37th Annual Conference on IEEE Industrial Electronics Society, 2011, pp. 27302735. [18] X. Yinliang and L. Wenxin, "Novel Multiagent Based Load Restoration Algorithm for Microgrids," Smart Grid, IEEE Transactions on, vol. 2, pp. 152161, 2011. [19] J. M. Solanki, S. Khushalani, and N. N. Schulz, "A MultiAgent Solution to Distribution Systems Restoration," Power Systems, IEEE Transactions on, vol. 22, pp. 10261034, 2007. [20] T. Nagata, Y. Tao, and H. Fujita, "An autonomous agent for power system restoration," in Power Engineering Society General Meeting, 2004. IEEE, 2004, pp. 10691074 Vol.1. [21] Z. Jiangfei, H. TingLei, P. Fei, and L. Yuanjie, "Genetic Algorithm Based on Greedy Strategy in the 01 Knapsack Problem," in Genetic and Evolutionary Computing, 2009. WGEC '09. 3rd International Conference on, 2009, pp. 105107. [22] M. Radenkovic, Adaptive Control System DesignFlass notes for ELEC 5466. Department of Electrical Engineering, University of Colorado Denver, Fall, 2011.
PAGE 70
58 APPENDIX A MATHIMATICAL DERIVATION OF THE ESTIMATION ALGORITHMS (RLS and GA) Let us consider the following linear system model [22]: U:E+1;+=1U:E;++=JU:E+1rFJ;=>1Q:E;+>2Q:ErF1;++>IQ:E+1rFI;,E=0,1,2, (A.1) Where: Q:E; : measurable system input signal U:E; : measurable system output signal Knowing that q1 is unit delay operator, i.e. MrF1U:E;=U:ErF1; then system in equation (A.1) becomes: :1+=1MrF1++=JMrFJ;U:E+1;=:>1+>2MrF1++>IMrFI+1;Q:E; (A.2) U:E+1;=$rkMrF1ro#:MrF1; Q(E) (A.3) So that: #:MrF1;=1+=1MrF1++=JMrFJ (A.4) $:MrF1;=>1+>2MrF1++>IMrFI+1 (A.5) The term $rkMrF1ro#:MrF1; in equation (A.3) is transfer operator of the system. Let us define system parameters and signal vectors as follows: K6=[rF=1,rF=2,,rF=J; Q:E;,,>I] (A.6) :E;6=[U:E;,,U:E+1rFJ;; >1,,Q:E+1rFI;] (A.7) So the system is equation (A.1) can be written as: U:E+1;=:E;6K (A.8) More general system model is:
PAGE 71
59 + 1 = + ( ) (A.9 ) W here ( ) represents the cumulative effects of disturbance, measurement errors, etc Assuming that system parameters are unknown, an estimate of is denoted by + 1 then the following identification model can be constructed: + 1 = + 1 (A.10) Estimating + 1 is determined so that in a certain sense model output + 1 matches the system output + 1 Let us choose + 1 so that it minimizes the sum of the square errors of the fit. = + 1 + 1 2 = 0 (A.11) A necessary condition for a local minimum is: + 1 = 0 which gives : 2 + 1 + 1 ( ) = 0 = 0 (A.12) I t follows that: = 0 + 1 = + 1 = 0 (A.13) Hence a least square estimate of is any estimate + 1 t hat satisfies equation ( A.13 ). There may be more than one minimize of Let define a new matrix : = 0 (A.14) W hich is invertible, and called covariance matrix. then there is an unique least square estimate: + 1 = 1 + 1 = 0 (A.15)
PAGE 72
60 A. 1 Derivation of R ecursive L east S quare Algorithm E stimation (RLS) Considering the least square estimate in equation ( A. 1 3 ), we wish to determine a recursive form of this estimate that suitable for easily updating to + 1 Recalling equation ( A. 1 4 ), we see that = 1 + (A.16) Then from ( A.13 ) ( ) + 1 = = 0 ( + 1 ) (A.17) + 1 = 1 = 0 + 1 + + 1 (A.18) + 1 = 1 + + 1 from ( A.13 ) (A.19) + 1 = ( ) + + 1 from ( A.16 ) (A.20) Thus: + 1 = + + 1 (A.21) + 1 = + [ + 1 ] (A.22) Then: + 1 = + 1 [ + 1 ] (A.23) From stored values of and 1 and new observations + 1 and by using equations (A. 20 & A. 23 ) we can calculate the new values + 1 and Equations (A.1 6 & A. 23 ) are called the Recursive Least Square Estimate (RLS). To avoid inverting matrix 1 in equation (A.2 3 ), we use what called the matrix invariance lemma : (A+BCD) 1 = A 1 A 1 B(C 1 + DA 1 B) 1 DA 1 (A.25) Here, all matrices in verses on the right hand side are exist. Let define 1 then from ( A.1 7 )
PAGE 73
61 1 = 1 1 + (A.26) By applying the rule of matrix invariance lemma, we set: = 1 = = 1 = then the equation (A.2 5 ) becomes = 1 + 1 1 1 + 1 (A.27) Then we have obtained the following RLS estimate that requires no inversion to be performed at each step. + 1 = + ( ) [ + 1 ] (A.28) = 1 + 1 1 1 + 1 (A.29) 0 = 0 > 0 A. 2 Derivation of Gradient A lgorithm E stimation (GA) Given an estimate the squared prediction error is: 2 = 1 2 ( 1 ) 2 (A.30) Its gradient with respect to is: 2 = 1 [ ( 1 ) ] (A.31) The direction of the negative gradient 1 [ ( 1 ) ] is the direction in which a small change in will lead to a decrease in 2 Thus one moti vated to consider the algorithm = 1 + ( 1 ) ( 1 ) 1 (A.32) W here > 0 is a gain to increase the speed of the convergence. Equation (A. 32 ) is called the Gradient Algorithm Estimate (GA) [22]
PAGE 74
62 A. 3 Basic Flowchart for the Estimation Algorithms (RLS and GA) Figure A .1: Flowchart of solving EDP based on new estimation algorithms

