当前位置：文江博客话题详情

计算最节能自组织网络的算法

发布于 2024-08-23 17:39:20 字数 585 浏览 8 评论 0原文

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

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

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

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

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

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

编辑#2：我对问题原文中的遗漏感到抱歉。因此，您之前的一些答案并不完全是我想要的，但我不熟悉 MST 算法，所以感谢您告诉我它们。

为了让事情变得更清楚，让我添加这一点：

所有节点每个周期都会发送一条自己的消息，包括内部节点。内部节点还负责中继它们接收到的任何消息。如果他们自己发送额外的消息，这会增加他们的电池压力。目的是在任何节点的电池耗尽之前最大限度地提高循环次数。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

梦断已成空 2024-08-30 17:39:20

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

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

回复收藏 0 原文

难如初 2024-08-30 17:39:20

在不考虑电池最小化的情况下，您正在寻找的是最短路径生成树，这有点类似于最小生成树，除了具有不同的“成本” “ 功能。（您可以运行 Dijkstra 算法来计算最短路径生成树，因为成本似乎总是积极的。）

但这并没有考虑电池最小化。在这种情况下，（我不太确定您首先要最小化的是什么）您可能需要研究最小成本最大流量。然而，这将首先优化（最大化）“流量”，然后再最小化成本。这可能是理想的，也可能不是理想的。

要创建顶点约束（每个节点只能操作 k 条消息），您只需创建第二个图 G_1，在其中添加额外的顶点 u_i 对于每个 v_i - 并且让 v_i 到 u_i 的流量不受您的约束限制，在本例中为 k+1，成本0。所以基本上如果原始图G中有一条边(a,b)，那么在G_1中也会有一条边>(u_a,v_b) 对于每条边。实际上，您正在创建第二层顶点，将流限制为 k。（根的特殊情况，除非您还想在根上设置消息约束。）

G_1 上的标准最大流解决方案应该足够了 - 一个指向每个顶点的流 的源>1，以及连接到根的接收器。如果 G_1 的最大流量为 N，则 G_1（随 k 变化）有一个解，即顶点。

回复收藏 0 原文

最美的太阳 2024-08-30 17:39:20

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

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

在您的示例中，根据您给出的衡量标准（最大消息数），尚不清楚左边的节点是否更有效，因为虽然 (1,2) 处的节点确实具有较少的能耗，但 (0, 1) 产量加倍。

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

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

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

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

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

This is not just a minimum spanning tree, because the weight of each edge is dependent on the weight of other edges. Also, you need not to minimize the sum of weights but the maximum weight on a single node, which is the weight of its output edge, multiplied by the number of incoming edges plus one.

Each node will have to transmit a number of messages, but if you route messages from outer nodes through inner nodes, the inner nodes will transmit a higher number of messages. In order to equalize the battery drain over all nodes, the inner nodes will have to use much shorter connections than the outer nodes; I suspect that this dependency on the distance from the root is exponential.

In your examples, it is not so clear whether the left one is more efficient by the measure you gave (maximum number of messages), because while the node at (1,2) does have less energy consumption, the one at (0,1) doubles its output.

I believe that you have to start with some tree (e.g. the one formed by having each node transmit directly to the root node) and then do a number of optimization steps.

The optimization might be possible deterministically or through a statistical method like simulated annealing or a genetic algorithm.

A deterministic method would perhaps try to find an improvement for the current worst node, such that the new node weights are smaller than the current maximum node weight. It is difficult to do this in such a way that the result is the global optimum.

Simulated annealing would mean to change a number of nodes' targets at each step, but this might be hampered by the fact that the "goodness" of a configuration is determined by its worst node. You would need to make sure that the worst node is sufficiently often affected in the candidate children, which might be difficult when the temperature drops.

In a genetic algorithm, you would design the "genome" as a mapping of each node to its target node. A punctual mutation would consist of changing one node's target to a random node (but only the root and nodes that are closer than the root should be considered).

回复收藏 0 原文

够钟 2024-08-30 17:39:20

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

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

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

回复收藏 0 原文

汐鸠 2024-08-30 17:39:20

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

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

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

回复收藏 0 原文

薄情伤 2024-08-30 17:39:20

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

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

Have you considered using a directed acyclic graph instead of a tree? In other words, each node has multiple "parents" that it can send messages to -- the acyclic requirement ensures that all messages eventually arrive. I ask because it sounds like you have a wireless network and because there's an efficient approach to computing the optimum solution.

The approach is linear programming. Let r be the index of the root node. For nodes i, j, let cij be the energy cost of sending a message from i to j. Let xij be a variable that will represent the number of messages sent by node i to node j in each time step. Let z be a variable that will represent the maximum rate of energy consumption at each node.

The linear program is

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

You can write a code that generates this LP in something very much like this format, whereupon it can be solved by an off-the-shelf LP solver (e.g., the free GLPK).

There are a couple of features of the LP worth mentioning. First, it may seem odd that we haven't "forced" messages to go to the root. It turns out that as long as the cij constants are positive, it just wastes energy to send messages in cycles, so there's no point. This also ensures that the directed graph we've constructed is acyclic.

Second, the xij variables are in general not integers. How do we send half a message? One possible solution is randomization: if M is the total rate of messages sent by node i, then node i sends each message to node j with probability xij/M. This ensures that the averages work out over time. Another alternative is to use some sort of weighted round-robin scheme.

回复收藏 0 原文