Algorithm to calculate the most energy efficient ad-hoc network

Question

I have a (theoretical) network with N nodes, each with their own fixed location. Each node sends one message per cycle, which needs to reach the root either directly or via other nodes.

The energy cost of sending a message from node A to node B is the distance between them, squared.

The challenge is how to link these nodes, in a tree format, to produce the most energy efficient network.

E.g. Here are 2 possible ways to link these nodes, the left one being more energy efficient.

I'm working on a Genetic algorithm to solve the problem, but I was wondering if anyone had any other ideas, or is aware of any relevant open-source code.

Edit: Another aspect of the network, which I forgot to mention, is that each node is battery powered. So if we have too many messages being routed via the same node, then that node's battery will become depleted, causing the network to fail. The network's energy efficiency is measured by how many messages can be successfully transmitted from each node to the root before any node runs out of battery.

Edit #2: I'm sorry about the ommission in the original text of the question. Becasue of it, some of your earlier answers aren't quite what I'm looking for, but I wasn't familiar with the MST algorithms, so thanks for telling me about them.

In the hope of making things clearer let me add this:

All nodes send one message of their own per cycle, including inner nodes. Inner nodes are also responsible for relaying any messages that they receive. This adds to the strain on their battery, is if they were sending an additional message of their own. The aim is to maximise the amount of cycles acheived before any node's battery dies.

Answer 1

I would think that you can construct the complete graph and then use Dijkstra's shortest path algorithm on each node to find the least cost route for that node. The union of these paths should form the minimal cost tree.

Note that with Dijkstra's algorithm it is also possible to calculate the entire tree in one pass.

Answer 2

Without taking account the batteries minimization, what you're looking for is the Shortest Path Spanning Tree, which is kind of similar to the Minimum Spanning Tree, except for with a different "cost" function. (You can just run Dijkstra's Algorithm to calculate the Shortest Path Spanning Tree, since the cost seems to always be positive.)

This does not take account the battery minimization though. In that case, (and I'm not quite sure what it is that you're trying to minimize first) you might want to look into Min-cost max flow. However, this will optimize (maximize) the "flow" first, before minimizing the cost. This might or might not be ideal.

To create the vertex constraint (each node can only operate k messages), you just need to create a second graph G_1 where you add an additional vertex u_i for each v_i - and having the flow v_i to u_i be whatever your constraint be, in this case, k+1, with the cost 0. So basically if there is an edge (a,b) in the original graph G, then in G_1, there will be an edge (u_a,v_b) for each of these edges. In effect, you're creating a second layer of vertices that constraints the flow to k. (Special case for the root, unless you also want a message constraint on the root.)

The standard max-flow solution on G_1 should suffice - a source that points to each vertex with a flow of 1, and a sink that is connected to the root. There is a solution for G_1 (varying on k) if the maxflow of G_1 is N, the number of vertices.