Tree based power flow

Read Kho J, Tran-Thanh L, Rogers A, Jennings NR. An Agent-Based Distributed Coordination Mechanism for Wireless Visual Sensor Nodes Using Dynamic Programming. The Computer Journal. 2010;53(8):1277.

Contains an algorithm that calculates the sampling, forwarding and routing actions of each node within a network such that maximum information of data is collected. Two algorithms are presented, one which assumes fixed path for data from a node to the base station (i.e underlying tree structure) and one which has flexible routing.

In both cases dynamic programming is used to propagate message from the nodes in the network to the base station. In the tree algorithm messages are propagated from the root (base station) to the leaves and then back to the root again:

1. Starting from the root, node sends to all its children the energy it uses to forward data and its own energy budget (i.e. how much energy it can use). When a node receives this information from its parent it sends its own information to all of its children.

2. Each node sends its D message to its parent, expressing it utility calculated based on its own ability to send data and in conjunction with its children.

3. base station calculates the optimal coordination for the sensors based on whether they forward some of their data or their childrens data. Corrdination message propagates through the network.

Using this as a starting point for calculating flow within the network. I am going to start with a simple tree network of 4 nodes and assume there are no transmission line limits. Need to express a nodes ability to either use power from elsewhere or use its own power to satisfy a load. 

One step forward, two steps back

Today I had a supervisor meeting with Alex and Gopal. In it I explained my simple decentralised message passing algorithm for determining which generators need to ramp up in order to reduce an overloaded line. As in the scenario I described in my previous blog post. However Alex pointed out that the way in which I allocate power does not take into account when a load overloads a line but the load is not directly connected to the line that gets overloaded. In this case a node nearer the load may be able to satisfy it however in my model I had assumed that load was situated at the root of the tree.

Therefore I have turned my attention to solving the decentralised power flow in a tree using dynamic programming. Is there an allocation of generator outputs that satisfy the thermal limits of the transmission lines and satisfy the loads within the tree using a decentralised dynamic programming algorithm. As a starting point I am going to read the following paper which does a similar thing for sending information around a tree using sensors:

Kho J, Tran-Thanh L, Rogers A, Jennings NR. An Agent-Based Distributed Coordination Mechanism for Wireless Visual Sensor Nodes Using Dynamic Programming. The Computer Journal. 2010;53(8):1277.

Initially from the dynamic programming explanations I think each generator will represent a stage and the state of each stage will be a continuous variable representing the generators output. The decision variable for each stage will represent the optimal output for each generator such that carbon emissions are minimised, the flow within the network is satisfied and the transmission lines are not overloaded.

Decentralised

I have come up with a simple strategy that coordinates generators in a decentralised way. The strategy will be applied to trees and works as follows:

Line A agent detects that it is overloaded, therefore it sends a message to the node receiving its flow that they need to increase their power output by x, and sends a message to the node sending their flow that they need to decrease their generation by x amount. In doing this the amount of power flowing down line A will be reduced by x and thus the line will no longer be overloaded.

Each subsequent node simply forwards the amount of power that is asked of them from a transmission line to all children.

A transmission line agent checks that the power required by one node from the other will not actually overload its transmission line, if it will then the transmission line changes the required power to be capped at the (maximumCapacity - currentFlow)

(i.e. Node 1 sends a message to Node 2 that it requires an extra 300kW, however the transmission line in between can only handle an extra 200kW therefore Node 2 will recieve a request for 200kW instead. )

Once the required power has been propagated down to the leaf nodes the nodes then send messages back to the root saying how much power they can produce and at what carbon intensity.

Finally messages are propagated back down to the leaf nodes starting from the root. At the root node it calculates how much power it needs to ask from each of its neighbours nodes in order to minimise carbon emissions, it only asks for the required power and doesn't care how it is broken down further between generators. Subsequent nodes repeat the process until all leaf nodes have received a message saying how much power is required from them. They all increase by the required amount.

Similarly the subtree that is required to decrease its power output by x amount perform the same steps however the transmission lines do not need to intervene in changing the required decrease in power.

This Week

This week I will be focusing on researching ways to implement a decentralised approach to the problem of generator coordination within a network. I will also be polishing my demo so that it can be displayed at the next energy meeting where I will be giving a presentation on my work so far.

Demo

I have now created a demo which visualises an electricity network with a number of generators and loads. When the demo is run, a load increases on the network, which is then satisfied by a generator ramping up to compensate. However doing this overloads two of the lines on the network. It then attempts to coordinate generators so that the lines are no longer overloaded. The objective function in use is a combination of minimising  the sum of carbon emissions and minimising the change of generators output.

Java implementation of CPLEX

I have written some code in Java which uses CPLEX to solve the same problem that I specified in my last post. The reason for using Java and CPLEX to specify the problem is that an actual simulation can be conducted that uses multiple CPLEX models to demonstrate the centralised approach to generator coordination. The simulation scenario is as follows:

1. Network is balanced, all thermal limits are satisfied. Carbon emissions are minimised. One generator/Node is nominated to follow loads within the network.

2. Load at a substation increases/line failure

3. This causes nominated generator to balance the demand

4. However in doing so this overloads a line.

5. Run the CPLEX code to optimise the thermal constraints within the network and also reduce the distance between the new power output of a generator and its previous power output when the network was overloaded.

6. network solution is achieved, network is restored back to fully working order.

This benchmark will be used to test the centralised, and eventually, decentralised approach.