Алгоритм расчета самой энергоэффективной одноранговой сети

Question

У меня есть (теоретическая) сеть с N узлами, каждый со своим фиксированным местоположением. Каждый узел отправляет одно сообщение за цикл, который должен достичь корня напрямую или через другие узлы.

Стоимость энергии отправки сообщения от узла A к узлу B - это расстояние между ними в квадрате.

Задача состоит в том, чтобы связать эти узлы в древовидном формате для создания наиболее энергоэффективной сети.

например. Вот два возможных способа связать эти узлы, левый более энергоэффективен.

Я работаю над Генетическим алгоритмом, чтобы решить эту проблему, но мне было интересно, есть ли у кого-нибудь какие-либо другие идеи или знает какой-нибудь соответствующий открытый исходный код.

Редактировать: еще один аспект сети, о котором я забыл упомянуть, это то, что каждый узел питается от батареи. Поэтому, если у нас слишком много сообщений, маршрутизируемых через один и тот же узел, батарея этого узла будет разряжена, что приведет к сбою сети. Энергоэффективность сети измеряется тем, сколько сообщений может быть успешно передано от каждого узла к корню до того, как у любого узла разрядится батарея.

Редактировать # 2: Я сожалею об упущении в исходном тексте вопроса. Из-за этого некоторые из ваших ранних ответов не совсем то, что я ищу, но я не был знаком с алгоритмами MST, поэтому спасибо, что рассказали мне о них.

В надежде прояснить ситуацию позвольте мне добавить следующее:

Все узлы отправляют одно собственное сообщение за цикл, включая внутренние узлы. Внутренние узлы также отвечают за передачу любых сообщений, которые они получают. Это увеличивает нагрузку на батарею, если они отправляют дополнительное собственное сообщение. Цель состоит в том, чтобы максимизировать количество циклов, достигаемых до того, как разрядится батарея любого узла.

Answer 1

Я думаю, что вы можете построить полный граф и затем использовать алгоритм кратчайшего пути Дейкстры на каждом узле, чтобы найти маршрут с наименьшей стоимостью для этого узла. Объединение этих путей должно сформировать дерево минимальной стоимости.

Обратите внимание, что с помощью алгоритма Дейкстры также можно рассчитать все дерево за один проход.

Answer 2

Без учета минимизации количества батарей вам нужно найти связующее дерево кратчайшего пути , которое похоже на минимальное остовное дерево , за исключением другая функция "стоимость". (Вы можете просто запустить Алгоритм Дейкстры , чтобы вычислить остовное дерево кратчайшего пути, так как стоимость кажется всегда положительной.)

Это не учитывает минимизацию батареи, хотя. В этом случае (и я не совсем уверен, что именно вы пытаетесь минимизировать в первую очередь), вы можете захотеть взглянуть на минимальный максимальный поток . Однако это оптимизирует (максимизирует) «поток» в первую очередь, прежде чем минимизировать стоимость. Это может или не может быть идеальным.

Чтобы создать ограничение вершины (каждый узел может обрабатывать только 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 (в зависимости от k), если максимальный поток G_1 равен N, числу вершин.

Answer 3

Это не просто минимальное связующее дерево, потому что вес каждого ребра зависит от веса других ребер. Кроме того, вам нужно не минимизировать сумму весов, а максимальный вес одного узла, который представляет собой вес его выходного фронта, умноженный на количество входящих ребер плюс один.

Каждый узел должен будет передать несколько сообщений, но если вы направите сообщения от внешних узлов через внутренние узлы, внутренние узлы будут передавать большее количество сообщений. Чтобы выровнять расход батареи по всем узлам, внутренние узлы должны будут использовать гораздо более короткие соединения, чем внешние узлы; Я подозреваю, что эта зависимость от расстояния от корня является экспоненциальной.

В ваших примерах не очень понятно, является ли левый более эффективным по меру, которую вы дали (максимальное количество сообщений), потому что, хотя у узла в (1,2) энергопотребление меньше, (0,1) удваивает свой вывод.

Я полагаю, что вы должны начать с некоторого дерева (например, сформированного путем передачи каждого узла непосредственно на корневой узел), а затем выполнить ряд шагов оптимизации.

Оптимизация может быть возможна детерминистически или с помощью статистического метода, такого как моделируемый отжиг или генетический алгоритм.

Детерминистский метод, возможно, попытался бы найти улучшение для текущего наихудшего узла, так чтобы веса новых узлов были меньше, чем текущий максимальный вес узлов. Это трудно сделать таким образом, чтобы результатом был глобальный оптимум.

Имитация отжига будет означать изменение целевого числа узлов на каждом шаге, но это может быть затруднено тем фактом, что «качество» конфигурации определяется ее худшим узлом. Вам необходимо убедиться, что худший узел достаточно часто поражается у детей-кандидатов, что может быть затруднительно при падении температуры.

В генетическом алгоритме вы бы спроектировали «геном» как отображение каждого узла на его целевой узел. Пунктуальная мутация будет состоять в изменении цели одного узла на случайный узел (но следует учитывать только корень и узлы, которые находятся ближе, чем корень).

Answer 4

Рассматривали ли вы использование направленного ациклического графа вместо дерева? Другими словами, у каждого узла есть несколько «родителей», которым он может отправлять сообщения - ациклическое требование гарантирует, что все сообщения в конечном итоге поступят. Я спрашиваю, потому что это звучит так, как будто у вас есть беспроводная сеть, и потому что есть эффективный подход к вычислению оптимального решения.

Подход - линейное программирование. Пусть 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 отправляет каждое сообщение узлу j с вероятностью xij / M. Это гарантирует, что средние значения со временем получатся. Другой альтернативой является использование некоторой взвешенной схемы кругового выбора.

Answer 5

Мне интересно, используете ли вы динамическую беспроводную сенсорную сеть (например, состоящую из сенсоров Telos)? Если это так, вы захотите разработать распределенный протокол минимального расстояния, а не что-то более монолитное, как Дейкстра.

Я полагаю, что вы можете использовать некоторые принципы из протокола AHODV (http://moment.cs.ucsb.edu/AODV/aodv.html)), но имейте в виду, что вам нужно каким-то образом увеличить показатель. Счет прыжков во многом зависит от потребления энергии, но при в то же время вам нужно помнить, сколько энергии используется для передачи сообщения. Возможно, начало метрики может быть суммой всех энергопотреблений в каждом узле на заданном пути. Когда ваш код настраивает вашу сеть Затем вы просто отслеживаете стоимость пути для данного «направления» маршрутизации и позволяете вашему распределенному протоколу делать все остальное на каждом узле.

Это дает вам гибкость в подбрасывании нескольких датчиков в воздух, и, где бы они ни приземлялись, сеть сходится в оптимальной конфигурации энергии для передачи сообщений.

Answer 6

Вы можете попытаться сформулировать проблему как задачу с минимальным расходом и максимальным потоком. Просто несколько идей:

Создайте дополнительный фиктивный узел в качестве источника и подключите ребра нулевой стоимости и емкости 1 от этого узла к каждому некорневому узлу. Затем установите корень в приемнике и установите все необходимые ребра (в данном случае это квадрат евклидова расстояния).

Если вы также хотите учесть энергоэффективность, вы можете попытаться добавить вес для этого к граничным затратам, приходящимся на каждый узел. Я не уверен, как еще вы можете это сделать, поскольку вы пытаетесь оптимизировать две цели (стоимость отправки сообщений и энергоэффективность) одновременно.

Answer 7

Я работал над аналогичной проблемой, но с беспроводными датчиками. Мы использовали 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]

Answer 8

минимальное остовное дерево? http://en.wikipedia.org/wiki/Minimum_spanning_tree