Алгоритм для вычисления самой энергосберегающей специальной сети
У меня есть (теоретическая) сеть с узлами N, каждый с их собственным фиксированным местоположением. Каждый узел отправляет одно сообщение на цикл, который должен достигнуть корня или непосредственно или через другие узлы.
Стоимость энергии отправки сообщения от узла к узлу B является расстоянием между ними, в квадрате.
Проблема состоит в том, как связать эти узлы, в древовидном формате, для создания самой энергосберегающей сети.
Например, Вот 2 возможных способа связать эти узлы, левые один являющийся более энергосберегающим.
Я работаю над Генетическим алгоритмом для решения проблемы, но я задавался вопросом, имел ли кто-либо какие-либо другие идеи или знает о каком-либо соответствующем открытом исходном коде.
Править: Другой аспект сети, которую я забыл упоминать, то, что каждый узел c батарейным питанием. Таким образом, если у нас есть слишком много сообщений, направляемых через тот же узел, затем который батарея узла станет истощенной, заставляя сеть привести к сбою. Энергоэффективность сети измеряется тем, сколько сообщений может быть успешно передано от каждого узла до корня, прежде чем любой узел разрядит батарею.
Редактирование № 2: я сожалею о пропуске в оригинальном тексте вопроса. Becasue его, некоторые Ваши более ранние ответы не вполне, что я ищу, но я не был знаком с алгоритмами MST, поэтому благодарит говорить мне о них.
В надежде на создание более ясных вещей позволяют мне добавить это:
Все узлы отправляют одно собственное сообщение на цикл, включая внутренние узлы. Внутренние узлы также ответственны за передачу любых сообщений, что они получают. Это добавляет к деформации на их батарее, то, если они отправляли дополнительное собственное сообщение. Цель состоит в том, чтобы максимизировать количество циклов, достигнутых, прежде чем батарея любого узла перестанет работать.
8 ответов
Без учета минимизации аккумуляторов, то, что вы ищете - это Shortest Path Spanning Tree, который похож на Minimum Spanning Tree, только с другой функцией "стоимости". (Вы можете просто запустить Алгоритм Дейкстры для расчета Shortest Path Spanning Tree, поскольку стоимость всегда положительна.)
Однако это не учитывает минимизацию заряда батареи. В этом случае (и я не совсем понимаю, что именно вы пытаетесь минимизировать в первую очередь) вы можете рассмотреть Min-cost max flow. Однако в этом случае сначала будет оптимизирован (максимизирован) "поток", а затем минимизирована стоимость. Это может быть или не быть идеальным.
Чтобы создать вершинное ограничение (каждый узел может обрабатывать только k сообщений), вам просто нужно создать второй граф G_1, где вы добавите дополнительную вершину u_i для каждой v_i - и поток v_i к u_i будет любым вашим ограничением, в данном случае k+1, со стоимостью 0. Таким образом, если в исходном графе (a,b) есть ребро G, то в G_1 для каждого из этих ребер будет ребро (u_a,v_b). По сути, вы создаете второй слой вершин, который ограничивает поток на k. (Особый случай для корня, если вы также не хотите ограничения сообщения на корень.)
Стандартного решения для максимального потока на G_1 должно быть достаточно - источник, указывающий на каждую вершину с потоком 1, и сток, соединенный с корнем. Существует решение для G_1 (изменяющееся по k), если максимальный поток G_1 равен N, числу вершин.
Это не просто минимальное остовное дерево, потому что вес каждого ребра зависит от веса других ребер. Кроме того, вам нужно минимизировать не сумму весов, а максимальный вес для одного узла, который представляет собой вес его выходного ребра, умноженный на количество входящих ребер плюс один.
Каждый узел должен будет передать некоторое количество сообщений, но если вы маршрутизируете сообщения от внешних узлов через внутренние узлы, внутренние узлы будут передавать большее количество сообщений. Чтобы выровнять разряд батареи по всем узлам, внутренние узлы должны будут использовать гораздо более короткие соединения, чем внешние узлы; Я подозреваю, что эта зависимость от расстояния от корня экспоненциальна.
В ваших примерах не так ясно, является ли левый более эффективным по указанной вами мере (максимальное количество сообщений), потому что, хотя узел в (1,2) действительно потребляет меньше энергии, узел в (0,1) удваивает свой вывод.
Я считаю, что вам нужно начать с некоторого дерева (например, того, которое сформировано тем, что каждый узел передает непосредственно корневому узлу), а затем выполнить ряд шагов по оптимизации.
Оптимизация может быть возможна детерминированно или с помощью статистического метода, такого как моделирование отжига или генетический алгоритм.
Детерминированный метод, возможно, попытался бы найти улучшение для текущего наихудшего узла, так что веса нового узла меньше текущего максимального веса узла. Сделать это так, чтобы результат был глобальным оптимумом, сложно.
Имитация отжига означала бы изменение целого ряда узлов на каждом этапе, но этому может препятствовать тот факт, что «качество» конфигурации определяется ее наихудшим узлом. Вам нужно будет убедиться, что наихудший узел достаточно часто поражается у детей-кандидатов, что может быть затруднено при понижении температуры.
В генетическом алгоритме вы должны спроектировать «геном» как отображение каждого узла на его целевой узел. Точечная мутация будет состоять в изменении цели одного узла на случайный узел (но следует учитывать только корень и узлы, расположенные ближе, чем корень).
минимальное остовное дерево? http://en.wikipedia.org/wiki/Minimum_spanning_tree
Я работал над аналогичной проблемой, но с беспроводными датчиками. Мы использовали PEGASIS (Power Efficient Gathering in Sensor Information System), который является энергоэффективным протоколом. 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]
Я бы подумал, что вы можете построить полный граф, а затем использовать алгоритм кратчайшего пути Дейкстры на каждом узле, чтобы найти маршрут с наименьшей стоимостью для этого узла. Объединение этих путей должно сформировать дерево минимальных затрат.
Обратите внимание, что с помощью алгоритма Дейкстры также можно вычислить все дерево за один проход.
Вы можете попробовать сформулировать проблему как проблему минимальной стоимости максимального потока. Вот некоторые идеи:
Создайте дополнительный фиктивный узел в качестве источника, и соедините ребра с нулевой стоимостью и пропускной способностью 1 от этого узла до каждого узла, не являющегося корнем. Затем установите корень в стоке и задайте стоимость всех ребер так, как вам нужно (квадрат евклидова расстояния, в данном случае).
Если вы хотите также учесть энергоэффективность, вы можете попробовать добавить вес для нее в стоимость граней, идущих в каждый узел. Я не уверен, как еще можно это сделать, поскольку вы пытаетесь оптимизировать две цели (стоимость отправки сообщения и энергоэффективность) одновременно.
Мне интересно, используете ли вы динамическую беспроводную сенсорную сеть (состоящую, например, из сенсоров Telos)? Если это так, то вы захотите разработать распределенный протокол минимального расстояния, а не что-то более монолитное, как у Дейкстры.
Я считаю, что вы можете использовать некоторые принципы протокола 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).
Есть несколько особенностей ЛП, о которых стоит упомянуть. Во-первых, может показаться странным, что мы не "заставили" сообщения идти к корню. Оказывается, пока константы cij положительны, отправка сообщений по циклам просто тратит энергию, так что в этом нет смысла. Это также гарантирует, что построенный нами направленный граф является ациклическим.
Во-вторых, переменные xij в общем случае не являются целыми числами. Как мы отправим половину сообщения? Одним из возможных решений является рандомизация: если M - это общее количество сообщений, отправленных узлом i, то узел i отправляет каждое сообщение узлу j с вероятностью xij/M. Это гарантирует, что средние значения со временем сработают. Другая альтернатива - использовать какую-либо взвешенную схему круговой выборки.