title: Algorithm to calculate the most energy efficient ad-hoc network
body: <p>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. </p>
  
  <p>The energy cost of sending a message from node A to node B is the distance between them, squared.</p>
  
  <p>The challenge is how to link these nodes, in a tree format, to produce the most energy efficient network.</p>
  
  <p>E.g. Here are 2 possible ways to link these nodes, the left one being more energy efficient.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>In the hope of making things clearer let me add this: </p>
  
  <p>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.</p>