Algorytm obliczania najbardziej energooszczędnej sieci ad-hoc

Question

Posiadam (teoretyczną) sieć z N węzłami, każdy z własną ustaloną lokalizacją. Każdy węzeł wysyła jedną wiadomość na cykl, który musi dotrzeć do katalogu głównego bezpośrednio lub za pośrednictwem innych węzłów.

Koszt energii wysłania wiadomości z węzła A do węzła B jest odległością między nimi, do kwadratu.

Wyzwanie polega na połączeniu tych węzłów w formacie drzewa, aby uzyskać najbardziej wydajną energetycznie sieć.

E.g. Oto 2 możliwe sposoby połączenia tych węzłów, z których jeden jest bardziej energooszczędny.

Pracuję nad algorytmem genetycznym, aby rozwiązać problem, ale zastanawiałem się, czy ktoś ma jakieś inne pomysły, czy jest świadomy jakiegokolwiek kodu open-source.

Edytuj: Kolejnym aspektem sieci, o którym zapomniałem wspomnieć, jest to, że każdy węzeł jest zasilany z baterii. Jeśli więc mamy zbyt dużo komunikatów przesyłanych przez ten sam węzeł, bateria tego węzła zostanie rozładowana, co spowoduje awarię sieci. Sprawność energetyczna sieci jest mierzona liczbą komunikatów, które mogą być z powodzeniem przesyłane z każdego węzła do katalogu głównego, zanim dowolny węzeł zabraknie baterii.

Edycja nr 2: Przykro mi z powodu braku odpowiedzi w oryginalnym tekście pytania. Po pierwsze niektóre z twoich wcześniejszych odpowiedzi nie są tym, czego szukam, ale nie znałem algorytmów MST, więc dziękuję za opowiadanie mi o nich.

W nadziei dokonywania rzeczy jaśniejsze dodam to:

Wszystkie węzły wysłać jedną wiadomość własnych na cykl, w tym wewnętrznych węzłów. Wewnętrzne węzły są również odpowiedzialne za przekazywanie otrzymywanych wiadomości. To zwiększa obciążenie ich baterii, jeśli wysyłali oni dodatkową wiadomość. Celem jest zmaksymalizowanie liczby cykli osiągniętych przed śmiercią baterii dowolnego węzła.

Answer 1

Bez uwzględnienia minimalizacji baterii potrzebna jest wersja Shortest Path Spanning Tree, która jest podobna do Minimum Spanning Tree, z wyjątkiem innej funkcji "kosztowej". (Możesz po prostu uruchomić Dijkstra's Algorithm, aby obliczyć najkrótsze drzewo rozpinające ścieżkę, ponieważ koszt wydaje się zawsze dodatni.)

Nie uwzględnia to jednak minimalizacji baterii. W takim przypadku (i nie jestem całkiem pewien, co to jest, że najpierw próbujesz zminimalizować), możesz zajrzeć do Min-cost max flow. To jednak zoptymalizuje (zmaksymalizuje) "przepływ" najpierw, zanim zminimalizuje koszt. To może, ale nie musi, być idealne.

Aby utworzyć ograniczenie wierzchołków (każdy węzeł może działać tylko k wiadomości), wystarczy utworzyć drugi wykres G_1 gdzie można dodać dodatkowy wierzchołek u_i dla każdego v_i - i mający przepływ v_i do u_i być bez względu na ograniczenia być, w tym przypadku, k+1, z kosztem 0. Zasadniczo, jeśli istnieje krawędź (a,b) na oryginalnym wykresie G, to w przypadku G_1, dla każdej z tych krawędzi pojawi się krawędź (u_a,v_b). W efekcie tworzysz drugą warstwę wierzchołków, która ogranicza przepływ do k. (Przypadek specjalny dla katalogu głównego, chyba że chcesz także ograniczyć wiązanie wiadomości do katalogu głównego).

Standardowe rozwiązanie do maksymalnego przepływu na G_1 powinno wystarczyć - źródło wskazujące każdy wierzchołek z przepływem 1 i zlewem który jest połączony z rootem.Istnieje rozwiązanie dla G_1 (zmieniające się na k), jeśli maksymalny przepływ G_1 wynosi N, liczba wierzchołków.

Answer 2

Myślę, że można zbudować kompletny wykres, a następnie użyć Dijkstra's shortest path algorithm na każdym węźle, aby znaleźć trasę o najniższym koszcie dla tego węzła. Połączenie tych ścieżek powinno tworzyć drzewo kosztów minimalnych.

Należy zauważyć, że z algorytmem Dijkstry możliwe jest również obliczenie całego drzewa w jednym przebiegu.

Answer 3

minimalne drzewo opinające? http://en.wikipedia.org/wiki/Minimum_spanning_tree

Answer 4

Możesz spróbować sformułować problem jako problem z minimalnym kosztem maksymalnego przepływu. Kilka pomysłów:

Utwórz dodatkowy węzeł typu dummy jako źródło i połącz krawędzie o zerowym koszcie i pojemności 1 z tego węzła do każdego węzła innego niż root. Następnie ustaw korzeń w zlewie i ustaw wszystkie koszty krawędzi, jak chcesz (w tym przypadku kwadrat odległości euklidesowej).

Jeśli chcesz również uwzględnić wydajność energetyczną, możesz spróbować dodać wagę do kosztów krawędzi wchodzących do każdego węzła. Nie jestem pewien, jak inaczej można to zrobić, ponieważ próbujesz zoptymalizować dwa cele (koszt wysłania wiadomości i wydajność energetyczną) w tym samym czasie.

Answer 5

To nie jest tylko minimalne drzewo opinające, ponieważ ciężar każdej krawędzi zależy od ciężaru innych krawędzi. Nie musisz też minimalizować sumy wag, ale maksymalną masę na pojedynczym węźle, która jest masą jego krawędzi wyjściowej, pomnożoną przez liczbę przychodzących krawędzi plus jeden.

Każdy węzeł będzie musiał przesłać pewną liczbę komunikatów, ale jeśli przekierowujesz komunikaty z zewnętrznych węzłów przez wewnętrzne węzły, wewnętrzne węzły będą przekazywać większą liczbę wiadomości. Aby wyrównać rozładowanie baterii na wszystkich węzłach, węzły wewnętrzne będą musiały używać znacznie krótszych połączeń niż zewnętrzne węzły; Podejrzewam, że ta zależność od odległości od korzenia jest wykładnicza.

W waszych przykładach nie jest tak jednoznaczne, czy lewy jest bardziej skuteczny dzięki podanej miarie (maksymalna liczba wiadomości), ponieważ podczas gdy węzeł w (1,2) ma mniejsze zużycie energii, ten w (0,1) podwaja swoją wydajność.

Wierzę, że musisz zacząć od jakiegoś drzewa (na przykład tego, które zostało utworzone przez przeniesienie każdego węzła bezpośrednio do węzła głównego), a następnie wykonać kilka kroków optymalizacyjnych.

Optymalizacja może być możliwa w sposób deterministyczny lub za pomocą metody statystycznej, takiej jak symulowane wyżarzanie lub algorytm genetyczny.

Metoda deterministyczna prawdopodobnie spróbuje znaleźć ulepszenie dla bieżącego najgorszego węzła, tak aby nowe wagi węzłów były mniejsze niż bieżący maksymalny ciężar węzła. Trudno to zrobić w taki sposób, aby wynik był optymalnym globalnym.

Symulowane wyżarzanie oznaczałoby zmianę liczby celów węzłów na każdym kroku, ale może to być utrudnione przez fakt, że "dobro" konfiguracji jest określone przez najgorszy węzeł. Trzeba się upewnić, że najgorszy węzeł jest wystarczająco często dotknięty u kandydujących dzieci, co może być trudne, gdy temperatura spada.

W algorytmie genetycznym zaprojektowałbyś "genom" jako mapowanie każdego węzła do jego węzła docelowego. Punktowa mutacja polegałaby na zmianie celu jednego węzła na losowy węzeł (ale należy wziąć pod uwagę tylko root i węzły znajdujące się bliżej niż root).

Answer 6

Zastanawiam się, czy korzystasz z dynamicznej sieci czujników bezprzewodowych (na przykład z czujników Telos)? W takim przypadku będziesz chciał opracować rozproszony protokół min-distance, a nie coś bardziej monolitycznego, jak Dijkstra.

Sądzę, że można zastosować pewne zasady z protokołu AHODV (http://moment.cs.ucsb.edu/AODV/aodv.html), ale należy pamiętać, że trzeba jakoś powiększyć metrykę. Licznik opadów ma wiele wspólnego z zużyciem energii, ale jednocześnie należy pamiętać, ile energii zużywa się do przesłania wiadomości. Być może początek pomiaru może być sumą wszystkich poborów mocy w każdym węźle na danej ścieżce. Kiedy twój kod ustawia twoją sieć, po prostu monitoruj koszt ścieżki dla danego "kierunku" routingu i pozwól, aby Twój rozproszony protokół wykonał resztę w każdym węźle.

Daje to elastyczność w rzucaniu wiązki czujników w powietrze i gdziekolwiek się znajdą, sieć będzie się zbliżać do optymalnej konfiguracji energii do przekazywania komunikatów.

Answer 7

Pracowałem nad podobnym problemem, ale z czujnikami bezprzewodowymi. Zastosowaliśmy PEGASIS (Power Efficient Gathering in Sensor Information System), który jest energooszczędnym protokołem. 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

Czy uważane za pomocą skierowany graf acykliczny zamiast drzewa? Innymi słowy, każdy węzeł ma wielu "rodziców", do których może wysyłać wiadomości - acykliczny wymóg zapewnia, że ​​wszystkie wiadomości w końcu dotrą. Pytam, ponieważ wygląda na to, że masz sieć bezprzewodową i że istnieje wydajne podejście do obliczania optymalnego rozwiązania.

Podejście to programowanie liniowe. Niech r będzie indeksem węzła głównego. Dla węzłów i, j, niech cij będzie kosztem energii wysłania wiadomości od i do j. Niech xij będzie zmienną, która będzie reprezentować liczbę wiadomości wysyłanych przez węzeł i do węzła j w każdym kroku czasowym. Niech z będzie zmienną, która będzie reprezentować maksymalną szybkość zużycia energii w każdym węźle.

Program liniowy jest

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 

można napisać kod, który generuje ten LP w coś bardzo podobny do tego formatu, przy czym może on być rozwiązany przez off-the-shelf LP solver (np bezpłatny GLPK).

Jest kilka cech LP wartych wspomnienia. Po pierwsze, może wydawać się dziwne, że nie musieliśmy "wymuszać" wiadomości, aby przejść do katalogu głównego. Okazuje się, że dopóki stałe cij są dodatnie, po prostu marnuje energię na wysyłanie wiadomości w cyklach, więc nie ma sensu. Zapewnia to również, że skonstruowany przez nas wykres jest acykliczny.

Po drugie, zmienne xij w ogóle nie są liczbami całkowitymi. Jak wysłać połowę wiadomości? Jednym z możliwych rozwiązań jest randomizacja: jeśli M jest całkowitą prędkością komunikatów wysyłanych przez węzeł i, to węzeł i wysyła każdą wiadomość do węzła j z prawdopodobieństwem xij/M. Zapewnia to, że średnie wypracowują się z czasem. Inną alternatywą jest zastosowanie pewnego rodzaju ważonego programu typu round-robin.