Algoritmo per calcolare la rete ad-hoc più efficiente dal punto di vista energetico

Question

Ho una rete (teorica) con N nodi, ciascuno con la propria posizione fissa. Ogni nodo invia un messaggio per ciclo, che deve raggiungere la radice direttamente o tramite altri nodi.

Il costo energetico di invio di un messaggio dal nodo A al nodo B è la distanza tra loro, al quadrato.

La sfida è come collegare questi nodi, in un formato ad albero, per produrre la rete più efficiente dal punto di vista energetico.

E.g. Qui ci sono 2 possibili modi per collegare questi nodi, quello di sinistra è più efficiente dal punto di vista energetico.

Sto lavorando a un algoritmo genetico per risolvere il problema, ma mi chiedevo se qualcuno avesse altre idee o fosse a conoscenza di qualsiasi codice open source pertinente.

Modifica: Un altro aspetto della rete, che ho dimenticato di menzionare, è che ciascun nodo è alimentato a batteria. Quindi, se abbiamo troppi messaggi in routing tramite lo stesso nodo, la batteria di quel nodo si esaurirà, causando il fallimento della rete. L'efficienza energetica della rete è misurata dal numero di messaggi che possono essere trasmessi con successo da ciascun nodo alla radice prima che qualsiasi nodo esaurisca la batteria.

Modifica n. 2: Mi dispiace per l'omissione nel testo originale della domanda. Per questo motivo, alcune delle vostre risposte precedenti non sono proprio quello che sto cercando, ma non avevo familiarità con gli algoritmi MST, quindi grazie per avermi parlato di loro.

Nella speranza di rendere le cose più chiare lasciatemi aggiungi a:

Tutti i nodi inviare un messaggio di loro per ciclo, compresi i nodi interni. I nodi interni sono anche responsabili di inoltrare tutti i messaggi che ricevono. Ciò aumenta la tensione della batteria, è se inviavano un messaggio aggiuntivo. L'obiettivo è di massimizzare la quantità di cicli raggiunti prima che la batteria di qualsiasi nodo muoia.

Answer 1

Senza prendere in considerazione la riduzione delle batterie, quello che stai cercando è il Shortest Path Spanning Tree, che è simile al Minimum Spanning Tree, tranne che con una diversa funzione "costo". (Puoi semplicemente eseguire Dijkstra's Algorithm per calcolare l'albero di copertura del percorso più breve, poiché il costo sembra essere sempre positivo.)

Questo non tiene conto della minimizzazione della batteria. In tal caso, (e non sono abbastanza sicuro di cosa si stia tentando di minimizzare prima) si potrebbe voler esaminare Min-cost max flow. Tuttavia, ciò ottimizzerà (massimizza) il "flusso" prima, riducendo al minimo il costo. Questo potrebbe o potrebbe non essere l'ideale.

per creare il vincolo vertice (ogni nodo può operare solo k messaggi), è sufficiente creare un secondo grafico G_1 cui si aggiunge un vertice addizionale u_i per ogni v_i - e avendo il flusso v_i-u_i essere qualunque sia il vostro vincolo essere, in questo caso, k+1, con il costo 0. Quindi, in sostanza se c'è un bordo (a,b) nel grafico originale G, quindi in G_1, ci sarà un bordo (u_a,v_b) per ciascuno di questi bordi. In effetti, stai creando un secondo livello di vertici che vincola il flusso a . (Caso speciale per la radice, a meno che non si vuole anche un vincolo messaggio sulla radice.)

La soluzione max-flow di serie su G_1 dovrebbe essere sufficiente - una fonte che punta a ogni vertice, con un flusso di 1, e un lavandino che è connesso alla radice.Esiste una soluzione per G_1 (variabile su k) se il flusso massimo di G_1 è N, il numero di vertici.

Answer 2

Penso che sia possibile costruire il grafico completo e quindi utilizzare Dijkstra's shortest path algorithm su ciascun nodo per trovare il percorso meno costoso per quel nodo. L'unione di questi percorsi dovrebbe costituire l'albero dei costi minimi.

Si noti che con l'algoritmo di Dijkstra è anche possibile calcolare l'intero albero in un'unica passata.

Answer 3

albero di copertura minimo? http://en.wikipedia.org/wiki/Minimum_spanning_tree

Answer 4

Si può provare a formulare il problema come un problema di massimo flusso a costo minimo. Solo alcune idee:

Creare un nodo fittizio aggiuntivo come origine e collegare i bordi di costo zero e capacità 1 da questo nodo a ogni nodo non root. Quindi imposta la radice sul lavandino e imposta tutti i costi del bordo come desideri (il quadrato della distanza euclidea, in questo caso).

Se si desidera anche tenere conto dell'efficienza energetica, è possibile provare ad aggiungere un peso per i costi di bordo in ogni nodo. Non so in quale altro modo puoi farlo, dal momento che stai cercando di ottimizzare due obiettivi (costo dell'invio dei messaggi e dell'efficienza energetica) allo stesso tempo.

Answer 5

Questo non è solo uno spanning tree minimo, perché il peso di ogni spigolo dipende dal peso degli altri spigoli. Inoltre, non è necessario minimizzare la somma dei pesi ma il peso massimo su un singolo nodo, che è il peso del suo margine di uscita, moltiplicato per il numero di bordi in entrata più uno.

Ogni nodo dovrà trasmettere un numero di messaggi, ma se si instradano messaggi da nodi esterni attraverso nodi interni, i nodi interni trasmetteranno un numero maggiore di messaggi. Per equalizzare il consumo della batteria su tutti i nodi, i nodi interni dovranno utilizzare connessioni molto più brevi rispetto ai nodi esterni; Sospetto che questa dipendenza dalla distanza dalla radice sia esponenziale.

Nei tuoi esempi, non è chiaro se quello di sinistra sia più efficiente con la misura che hai dato (numero massimo di messaggi), perché mentre il nodo a (1,2) ha meno consumo di energia, quello a (0,1) raddoppia la sua produzione.

Credo che sia necessario iniziare con un albero (ad esempio quello formato dall'avere che ciascun nodo trasmette direttamente al nodo radice) e quindi eseguire una serie di passaggi di ottimizzazione.

L'ottimizzazione potrebbe essere possibile deterministicamente o tramite un metodo statistico come la ricottura simulata o un algoritmo genetico.

Un metodo deterministico cercherebbe probabilmente di trovare un miglioramento per il nodo corrente peggiore, in modo tale che i pesi del nuovo nodo siano inferiori al peso del nodo massimo corrente. È difficile farlo in modo tale che il risultato sia l'optimum globale.

La ricottura simulata significherebbe modificare un numero di obiettivi di nodi in ogni fase, ma ciò potrebbe essere ostacolato dal fatto che la "bontà" di una configurazione è determinata dal suo nodo peggiore. Dovresti assicurarti che il nodo peggiore sia sufficientemente spesso colpito nei bambini candidati, il che potrebbe essere difficile quando la temperatura diminuisce.

In un algoritmo genetico, si progetterebbe il "genoma" come una mappatura di ciascun nodo sul nodo di destinazione. Una mutazione puntuale consisterebbe nel cambiare la destinazione di un nodo in un nodo casuale (ma solo la radice ei nodi più vicini della radice dovrebbero essere considerati).

Answer 6

Mi chiedo se si sta utilizzando una rete di sensori wireless dinamica (composta da sensori Telos, ad esempio)? Se questo è il caso, vorrai sviluppare un protocollo a distanza ridotta piuttosto che qualcosa di più monolitico come Dijkstra.

Credo che sia possibile utilizzare alcuni principi da un protocollo AHODV (http://moment.cs.ucsb.edu/AODV/aodv.html), ma tenere presente che in qualche modo sarà necessario aumentare la metrica. Il numero di hop ha molto a che fare con il consumo di energia, ma allo stesso tempo, è necessario tenere presente quanta energia viene utilizzata per trasmettere un messaggio. Forse un inizio di una metrica potrebbe essere la somma di tutti gli usi di potenza in ogni nodo su un dato percorso. Quando il tuo codice imposta la tua rete allora, tieni semplicemente traccia del costo del percorso per una determinata "direzione" del routing e lascia che il tuo protocollo distribuito faccia il resto su ciascun nodo.

Questo ti dà la flessibilità di lanciare una serie di sensori nell'aria e ovunque si trovino la rete convergerà sulla configurazione di energia ottimale per il passaggio dei messaggi.

Answer 7

Ho lavorato su un problema simile, ma con sensori wireless. Abbiamo utilizzato PEGASIS (Power Efficient Gathering in Sensor Information System), che è un protocollo a basso consumo energetico. 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

Hai pensato di usare un grafo orientato aciclico, invece di un albero? In altre parole, ogni nodo ha più "genitori" a cui può inviare messaggi: il requisito aciclico assicura che tutti i messaggi arrivino alla fine. Chiedo perché sembra che tu abbia una rete wireless e perché c'è un approccio efficiente per calcolare la soluzione ottimale.

L'approccio è la programmazione lineare. Sia r l'indice del nodo radice. Per i nodi i, j, ci sia il costo energetico dell'invio di un messaggio da i a j. Sia xij una variabile che rappresenterà il numero di messaggi inviati dal nodo i al nodo j in ogni passo temporale. Sia z una variabile che rappresenterà il tasso massimo di consumo di energia in ciascun nodo.

Il programma lineare è

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 

è possibile scrivere un codice che genera questo LP in qualcosa di molto simile a questo formato, dopo di che può essere risolto da un LP solver off-the-shelf (ad esempio, la GLPK gratuito).

Ci sono un paio di funzioni del LP che vale la pena menzionare. In primo luogo, può sembrare strano che non abbiamo "forzato" i messaggi per andare alla radice. Si scopre che finchè le costanti cij sono positive, semplicemente sprecano energia per inviare messaggi in cicli, quindi non ha senso. Questo assicura anche che il grafo diretto che abbiamo costruito sia aciclico.

In secondo luogo, le variabili xij non sono in generale numeri interi. Come mandiamo mezzo messaggio? Una possibile soluzione è la randomizzazione: se M è la velocità totale dei messaggi inviati dal nodo i, allora il nodo i invia ciascun messaggio al nodo j con probabilità xij/M. Ciò garantisce che le medie si adattino nel tempo. Un'altra alternativa è quella di utilizzare una sorta di schema ponderato round robin.