11

我有一个包含 N 个节点的（理论上的）网络，每个节点都有自己的固定位置。每个节点每个周期发送一条消息，该消息需要直接或通过其他节点到达根。

从节点 A 向节点 B 发送消息的能量成本是它们之间的距离的平方。

挑战在于如何以树的形式链接这些节点，以产生最节能的网络。

例如，这里有 2 种可能的方式来链接这些节点，左边的一种更节能。

我正在研究一种遗传算法来解决这个问题，但我想知道是否有人有任何其他想法，或者是否知道任何相关的开源代码。

编辑：我忘了提到的网络的另一个方面是每个节点都是电池供电的。因此，如果我们有太多的消息通过同一个节点进行路由，那么该节点的电池就会耗尽，导致网络出现故障。网络的能源效率是通过在任何节点耗尽电池之前可以从每个节点成功传输到根节点的消息数来衡量的。

编辑#2：对于问题原文中的遗漏，我深表歉意。因此，您之前的一些答案并不是我想要的，但我对 MST 算法并不熟悉，所以感谢您告诉我有关它们的信息。

为了让事情更清楚，让我补充一下：

所有节点每个周期都发送一条自己的消息，包括内部节点。内部节点还负责中继他们收到的任何消息。这增加了他们电池的压力，如果他们要发送自己的额外信息。目的是最大化在任何节点的电池耗尽之前实现的循环数量。

4

8 回答 8

6

我认为您可以构建完整的图，然后在每个节点上使用Dijkstra 的最短路径算法来找到该节点的成本最低的路线。这些路径的联合应该形成最小成本树。

请注意，使用 Dijkstra 算法也可以一次计算整个树。

于 2010-03-04T10:44:35.347 回答
3

在不考虑电池最小化的情况下，您正在寻找的是Shortest Path Spanning Tree，它类似于Minimum Spanning Tree，除了具有不同的“成本”函数。（您可以运行Dijkstra 算法来计算最短路径生成树，因为成本似乎总是正数。）

不过，这并没有考虑到电池的最小化。在这种情况下，（我不太确定您首先尝试最小化的是什么）您可能需要查看Min-cost max flow。但是，这将首先优化（最大化）“流量”，然后再最小化成本。这可能是理想的，也可能不是理想的。

要创建顶点约束（每个节点只能操作k消息），您只需要创建第二个图，在其中为每个G_1顶点添加一个额外的顶点- 并让流成为您的约束，在这种情况下，成本. 所以基本上如果原始图中有一条边，那么在 中，这些边中的每一条都会有一条边。实际上，您正在创建将流限制为的第二层顶点。（根的特殊情况，除非您还想要根上的消息约束。）u_iv_iv_iu_ik+10(a,b)GG_1(u_a,v_b)k

上的标准最大流解决方案就G_1足够了 - 一个指向每个顶点的流为 的源1，以及一个连接到根的接收器。如果 maxflow为，则有一个解决方案G_1（在 上变化） ，即顶点数。kG_1N

于 2010-03-04T13:35:11.813 回答
2

这不仅仅是最小生成树，因为每条边的权重取决于其他边的权重。此外，您不需要最小化权重总和，而是单个节点上的最大权重，即其输出边的权重乘以传入边的数量加一。

每个节点都必须传输许多消息，但是如果您从外部节点通过内部节点路由消息，则内部节点将传输更多的消息。为了均衡所有节点的电池消耗，内部节点必须使用比外部节点短得多的连接；我怀疑这种对与根的距离的依赖性是指数的。

在您的示例中，通过您给出的度量（最大消息数），左边的节点是否更有效并不清楚，因为虽然 (1,2) 处的节点确实具有较少的能量消耗，但位于 (0, 1) 产量翻倍。

我相信你必须从一些树开始（例如，通过让每个节点直接传输到根节点形成的树），然后执行一些优化步骤。

优化可能是确定性的，也可能是通过模拟退火或遗传算法等统计方法进行的。

确定性方法可能会尝试为当前最差节点找到改进，使得新节点权重小于当前最大节点权重。很难以这样一种方式做到这一点，即结果是全局最优的。

模拟退火意味着在每个步骤中更改多个节点的目标，但这可能会受到以下事实的阻碍：配置的“优点”是由其最差的节点决定的。您需要确保最坏的节点在候选子节点中经常受到影响，这在温度下降时可能会很困难。

在遗传算法中，您可以将“基因组”设计为每个节点到其目标节点的映射。准时突变包括将一个节点的目标更改为随机节点（但只应考虑根和比根更近的节点）。

于 2010-03-04T13:19:26.407 回答
1

您是否考虑过使用有向无环图而不是树？换句话说，每个节点都有多个可以向其发送消息的“父节点”——非循环要求确保所有消息最终都到达。我问是因为听起来你有一个无线网络，并且因为有一种有效的方法来计算最佳解决方案。

方法是线性规划。设 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。这确保了平均值随着时间的推移而计算出来。另一种选择是使用某种加权循环方案。

于 2010-03-06T16:19:28.517 回答
1

我想知道您是否正在使用动态无线传感器网络（例如，由 Telos 传感器组成）？如果是这种情况，您将想要开发一个分布式最小距离协议，而不是像 Dijkstra 这样更单一的东西。

我相信您可以使用 AHODV ( http://moment.cs.ucsb.edu/AODV/aodv.html ) 协议中的一些原则，但请记住，您需要以某种方式增加指标。跳数与能量消耗有很大关系，但同时，您需要记住传输消息使用了多少功率。也许一个度量的开始可能是给定路径上每个节点的所有电源使用的总和。当您的代码设置您的网络时，您只需跟踪给定路由“方向”的路径成本，并让您的分布式协议在每个节点上完成其余的工作。

这使您可以灵活地将一堆传感器抛向空中，无论它们降落在哪里，网络都会汇聚在消息传递的最佳能量配置上。

于 2010-03-04T13:44:09.763 回答
1

您可以尝试将问题表述为最小成本最大流量问题。只是一些想法：

创建一个额外的虚拟节点作为源，并将零成本和容量 1 的边从该节点连接到每个非根节点。然后将根设置在汇点，并根据需要设置所有边成本（在本例中为欧几里得距离的平方）。

如果您还想考虑能源效率，您可以尝试将权重添加到进入每个节点的边缘成本中。我不确定您还能如何做到这一点，因为您正在尝试同时优化两个目标（消息发送成本和能源效率）。

于 2010-03-04T11:54:20.713 回答
0

我曾处理过类似的问题，但使用的是无线传感器。我们使用了 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]

于 2010-03-05T01:27:20.543 回答
0

最小生成树？http://en.wikipedia.org/wiki/Minimum_spanning_tree

于 2010-03-04T10:46:11.863 回答