我有一个（理论上）网络，有N个节点，每个节点都有自己的固定位置。每个节点每个周期发送一条消息，需要直接或通过其他节点到达根节点。
从节点A向节点B发送消息的能量成本是它们之间的距离，平方。
挑战在于如何以树格式链接这些节点以产生最节能的网络。
例如。以下是链接这些节点的两种可能方式，左侧节点更节能。
我正在研究遗传算法来解决这个问题，但我想知道是否有人有任何其他想法，或者知道任何相关的开源代码。
编辑：网络的另一个方面，我忘了提到，每个节点都是电池供电的。因此，如果我们通过同一节点路由太多消息，那么该节点的电池将耗尽，导致网络出现故障。网络的能效是通过在任何节点电池耗尽之前可以从每个节点成功传输到根节点的消息来衡量的。
编辑＃2：对于问题原始文本中的遗漏，我感到很遗憾。不管怎么说，你之前的一些答案并不是我想要的，但我不熟悉MST算法，所以感谢你告诉我它们。
为了让事情更清楚，让我补充一点：
所有节点每个周期发送一个自己的消息，包括内部节点。内部节点还负责中继它们收到的任何消息。这增加了他们电池的压力，如果他们发送了他们自己的附加信息。目标是在任何节点电池耗尽之前最大化循环次数。
如果不考虑电池的最小化，你需要的是什么 最短路径生成树，有点类似于 最小生成树，除了具有不同的“成本”功能。 （你可以跑 Dijkstra的算法 计算最短路径生成树，因为成本似乎总是积极的。）
但这并未考虑电池最小化。在那种情况下，（我不太确定你试图最小化的是什么）你可能想要调查一下 最低成本最大流量。然而，这将在最小化成本之前首先优化（最大化）“流量”。这可能是也可能不是理想的。
创建顶点约束（每个节点只能运行 k 消息），你只需要创建第二个图 G_1 在哪里添加一个额外的顶点 u_i 为每个人 v_i - 并有流量 v_i 至 u_i 无论你的约束是什么，在这种情况下， k+1，与成本 0。所以基本上如果有优势的话 (a,b) 在原始图表中 G然后在 G_1，会有优势 (u_a,v_b)对于这些边缘中的每一个。实际上，您正在创建第二层顶点，将流量限制为 k。 （root的特殊情况，除非您还希望在根上有消息约束。）
标准的最大流量解决方案 G_1 应该足够了 - 一个用流量指向每个顶点的源 1，以及连接到根的接收器。有一个解决方案 G_1 （改变 k）如果最大流量 G_1 是 N，顶点数。
我认为你可以构建完整的图表然后使用 Dijkstra的最短路径算法 在每个节点上查找该节点的最低成本路由。这些路径的联合应该构成最小成本树。
请注意，使用Dijkstra算法，也可以一次计算整个树。
这不仅仅是最小生成树，因为每条边的权重取决于其他边的权重。此外，您不需要最小化权重之和，而是最小化单个节点上的最大权重，即其输出边缘的权重，乘以传入边缘的数量加1。
每个节点都必须传输大量消息，但如果您通过内部节点从外部节点路由消息，则内部节点将传输更多数量的消息。为了均衡所有节点上的电池消耗，内部节点必须使用比外部节点短得多的连接;我怀疑这种与根距离的依赖性是指数级的。
在您的示例中，通过您给出的度量（最大消息数）是否更有效率并不是很清楚，因为虽然（1,2）处的节点确实具有较少的能量消耗，但是（0， 1）使其输出加倍。
我相信你必须从一些树开始（例如，通过让每个节点直接传输到根节点而形成的树）然后进行许多优化步骤。
可以通过确定性地或通过诸如模拟退火或遗传算法的统计方法来进行优化。
确定性方法可能试图找到当前最差节点的改进，使得新节点权重小于当前最大节点权重。以这样的方式很难做到这一点，即结果是全局最优的。
模拟退火意味着在每一步改变节点的目标数量，但这可能受到配置的“良好性”由其最差节点决定的事实的阻碍。您需要确保候选孩子中最差的节点经常受到影响，这在温度下降时可能很难。
在遗传算法中，您可以将“基因组”设计为每个节点到其目标节点的映射。准点突变包括将一个节点的目标更改为随机节点（但只应考虑根和比根更近的节点）。
您可以尝试将问题公式化为最小成本最大流量问题。只是一些想法：
创建一个额外的虚节点作为源，并将零成本和容量1的边从此节点连接到每个非根节点。然后在水槽处设置根，并根据需要设置所有边缘成本（在这种情况下，欧几里德距离的平方）。
如果您还想考虑能源效率，可以尝试将其加权计入每个节点的边际成本。我不确定你能做到这一点，因为你正试图同时优化两个目标（消息发送成本和能源效率）。
我想知道您是否使用动态无线传感器网络（例如，由Telos传感器组成）？如果是这种情况，那么您将需要开发分布式最小距离协议，而不是像Dijkstra那样更像单片的协议。
我相信你可以使用AHODV的一些原则（http://moment.cs.ucsb.edu/AODV/aodv.html）协议，但请记住，您需要以某种方式增加指标。跳数与能耗有很大关系，但与此同时，您需要记住用于传输消息的功率。也许度量的开始可能是给定路径上每个节点的所有功率使用的总和。当您的代码正在设置您的网络时，您只需跟踪路由的给定“方向”的路径成本，并让您的分布式协议在每个节点处完成剩下的工作。
这使您可以灵活地将大量传感器投射到空中，无论它们落在何处，网络都将汇聚在最佳的能量配置上，以便传递信息。
您是否考虑使用有向无环图而不是树？换句话说，每个节点都有多个可以发送消息的“父节点” - 非循环要求确保所有消息最终到达。我问，因为听起来你有一个无线网络，因为有一种有效的方法来计算最佳解决方案。
该方法是线性编程。令r为根节点的索引。对于节点i，j，令cij是从i发送消息到j的能量成本。令xij是一个变量，它表示每个时间步长中节点i发送给节点j的消息数。设z是一个变量，表示每个节点的最大能耗率。
线性程序是
minimize z
subject to
# the right hand side is the rate of energy consumption by i
(for all i) z >= sum over all j of cij * xij
# every node other than the root sends one more message than it receives
(for all i != r) sum over all j of xij == 1 + sum over all j of xji
# every link has nonnegative utilization
(for all i, j) xij >= 0
您可以编写一个生成此LP的代码，其格式与此格式非常相似，因此可以通过现成的LP解算器（例如，免费的GLPK）来解决。
LP的一些功能值得一提。首先，我们没有“强制”消息转到根目录，这似乎很奇怪。事实证明，只要cij常数是正数，它就会浪费能量来循环发送消息，所以没有意义。这也确保了我们构建的有向图是非循环的。
其次，xij变量通常不是整数。我们如何发送半条信息？一种可能的解决方案是随机化：如果M是节点i发送的消息的总速率，则节点i以概率xij / M将每个消息发送到节点j。这可以确保平均值随着时间的推移而变化。另一种选择是使用某种加权循环方案。
我研究过类似的问题，但是使用无线传感器。我们使用PEGASIS（传感器信息系统中的节能聚集），这是一种节能协议。 http://www.mast.queensu.ca/~math484/projects/pastprojects/2005/presentation05_Yi_Wei.ppt [http://www.technion.ac.il/~es/Professional/Routing_Protocols_for_Sensor_Networks.ppt][2]