Minimizzazione della energia spesa tramite assegnazione opportuna del ruolo di radice.

TIPOLOGIA DELLA RETE

1. Uguali potenzialità di calcolo

2. Uguali livelli energetici iniziali

3. Comunicazione bidirezionale

4. Assenza di perdite di messaggi

5. Architettura di comunicazione priva di ritardi

6. Struttura connessa della rete

7. Invio dei messaggi verso la radice

TECNICHE DI INVIO DEI MESSAGGI

1. Distinzione tra “Messaggi di misura” e “Messaggi di trasmissione”

2. Tra gli istanti di evoluzione discreti A e B ogni nodo riceve il proprio messaggio di misura ed i messaggi che provengono dai propri nodi figli.

3. Prima che arrivi B i vari nodi possono compiere una elaborazione parziale dei dati e devono inviare i messaggi preparati

4. Possibilità di “Reinvio totale dei messaggi” oppure di invio tramite “Sensor-Fusion”

Valutazione diversa dell’energia spesa nelle due tecniche di invio dei messaggi

Numero di messaggi ricevuti ad ogni istante discreto dai vari nodi. Caso con radice fissa e radice mobile . Negli esempi viene usato il reinvio totale dei messaggi

Il grafo rappresentativo della rete viene sostituito dalla matrice Mg. Tale matrice ha elementi che valgono zero oppure uno. L’ elemento generico in posizione ( i , j ) vale uno se e solo se il nodo i può mandare messaggi a j

Mg =

0 1 1 0 0

1 0 1 0 0

1 1 0 1 0

0 0 1 0 1

0 0 0 1 0

Mg ha la diagonale principale sempre nulla, e’ simmetrica ed in generale non è definita.

Anche l’ albero estratto dal grafo viene sostituito da una matrice Ma.Ma presenta in posizione ( i , j ) un elemento pari ad uno se e solo se nella particolare configurazione il nodo i può ricevere messaggi da j .

Ma =

0 0 0 0 0

0 0 0 0 0

1 1 0 0 0

0 0 1 0 1

0 0 0 0 0

Matrice di connessione

Forme di stato rispettive per reti con reinvio totale dei messaggi e reti con reinvio di tipo Sensor-Fusion:

Notiamo che Ma e’ una funzione NON LINEARE della funzione Φ( • ) la quale a sua volta è NON LINEARE nel suo argomento Xr.

Se prendiamo come ingresso del sistema la posizione della radice nel generico istante di evoluzione allora il sistema è NON LINEARE. Notiamo che se la radice non viene mai spostata allora siamo in presenza di un sistema lineare con ingresso pari ad un vettore con elementi pari ad uno.

Si vuole trovare tra tutte le possibili leggi di controllo quella che faccia evolvere la rete in modo che essa presenti tutti i nodi non scarichi per il maggior tempo possibile.

COME SI RAGGIUNGE LO SCOPO?

Si cerca di minimizzare un funzionale opportuno che tiene conto della energia spesa dalla rete e dello scarto quadratico medio dei livelli energetici dei vari nodi.

Si cerca infatti di far scaricare i vari nodi il più lentamente possibile in modo uniforme.

Introduciamo il vettore la cui componente j-esima rappresenta la energia spesa dal nodo j-esimo a partire dall’ istante iniziale di evoluzione della rete.

Il funzionale di costo J( T ) dipende dall’ istante T. Esso è una funzione del tempo se si fissa la legge di controllo.

• Si vuole trovare la legge di controllo ottima Xr ( K ) con 0 ≤ K ≤ T che minimizza J( T ) qualsiasi T. Si suppone che la legge di controllo ottima esista ( Tale ipotesi NON è garantita ) • Notiamo che se esistono XA r ( K ) con 0 ≤ K ≤ T che minimizza J( T ) e XB r ( K ) con 0 ≤ K ≤ ( T + 1 ) che minimizza J( T + 1 ) XA r ( K ) = XB r ( K ) per 0

≤ K ≤ T • I calcoli per decidere chi sarà radice all’ istante ( T + 1 ) vengono eseguiti all’ istante T . Quindi si vuole trovare tra tutti i possibili Xr il seguente :

• Si procede per via algoritmica con un calcolo di complessità computazionale O( n ) dove n è il numero di nodi della rete.

Il problema da risolvere è difficile.

Si vuole minimizzare un funzionale quadratico definito su un sistema non lineare il quale ammette un ingresso che può assumere solamente un numero finito di valori.

NON risulta lecito l’ utilizzo di gradienti o “strumenti simili” per minimizzare J ( T )

• L’ algoritmo di minimizzazione di J ( T ) potrebbe spostare la radice anche ad ogni istante di evoluzione della rete.

• Alcuni messaggi potrebbero dover fare “tanta strada” prima di trovare una radice.

• Si sposta la radice e si calcola il numero di livelli dell’ albero ( N ).

• Si ripete il passo di minimizzazione di J ( T ) solamente dopo che siano trascorsi N istanti.

• Si garantisce che ogni messaggio viene reinviato NON più di N volte, dove N è il numero di nodi della rete.

Ci sono due gruppi di nodi. Il generico nodo di un gruppo comunica solo con tutti i nodi del secondo gruppo.

NON ESISTE LA LEGGE DI CONTROLLO OTTIMA

• In prossimità della radice si ha il più alto dispendio energetico.

• Negli istanti in cui si sposta la radice invece di minimizzare il funzionale J ( T ) si va a trovare il nodo meno scarico.

• Il ruolo di radice viene attribuito al nodo meno scarico.

Evoluzione J ( T )

Evoluzione temporale della energia spesa dal nodo più scarico della rete

• Le foglie dell’ albero sono i nodi che presentano il minor dispendio energetico.

• Negli istanti in cui si sposta la radice invece di minimizzare il funzionale J ( T ) si va a trovare il nodo che da la configurazione della rete che presenta come foglie i nodi più scarichi.

• Il ruolo di radice viene attribuito a tale nodo.

β > α

Forma quadratica semidefinita positiva

J ( T ) può essere annullato per qualche T

Viene usata la stessa tecnica utilizzata per

il caso di reinvio totale dei messaggi.

Ci sono due gruppi di nodi. Il generico nodo di un gruppo comunica solo con tutti i nodi del secondo gruppo.

EVOLUZIONE DI J ( T )

DRIFT

PARABOLICO

NON ESISTE LA LEGGE DI CONTROLLO OTTIMA

Invece di VT si usa il vettore VM SOLO PER MINIMIZZARE J( T )

Evoluzione nella simulazione di esempio di J ( T ) valutato su VT

È OPPORTUNO PRENDERE UN TEMPO INTERADICE MINIMO ALTRIMENTI L’ INFORMAZIONE POTREBBE TRANSITARE A LUNGO NELLA RETE

Per riuscire a proseguire nella trattazione seguente si ipotizza che l’energia spesa dalla rete al passo k-esimo sia scrivibile a meno di una costante moltiplicativa come :

APPROSSIMAZIONI INTRODOTTE :• Il costo dei messaggi ricevuti è lo stesso se il nodo è radice oppure no• Viene dato un costo dei messaggi di invio costante per tutti i nodi. In verità il nodo che sarà radice al passo successivo NON si invia un messaggio e quindi NON spende energia

• La tecnica Sensor-Fusion limita il numero di messaggi in circolo• Può NON essere necessario far scaricare tutte le batterie assieme • È importante che nell’ istante finale di evoluzione della rete tutti i nodi abbiano consumato la stessa energia

SI VUOLE TROVARE LA LEGGE DI CONTROLLO CHE ALL’ ISTANTE T ABBIA FATTO SPENDERE LA STESSA

ENERGIA A TUTTI I NODIQUALE È L’ ISTANTE FINALE DI EVOLUZIONE DELLA RETE ?

L’ istante finale di evoluzione si può determinare per via algoritmica. È sufficiente provare l’ algoritmo per vari istanti finali e scegliere come istante di evoluzione il maggiore istante che non faccia spendere più energia ai nodi di quella che essi posseggono. COMPLESSITÁ O(log n)

Scriviamo ora la formula trovata che ritorna il vettore la cui componente j – esima dice per quanti istanti lasciare il nodo j come radice.

PROG.

QUADR.

• n è un vettore a componenti positive, ma non necessariamente intere. Si fa un casting ai naturali delle componenti del vettore

• se Q-1∆ è già un vettore a componenti tutte positive allora il problema di programmazione quadratica ha risultato nullo

• se Q-1∆ NON è un vettore a componenti tutte positive allora le componenti del vettore n che è la soluzione migliore potrebbero avere una deviazione standard non trascurabile

• dalla deduzione della formula risolutiva NON discendono informazioni su quale sia l’ ordine in cui mettere come radice i vari nodi.

• al soddisfacimento del nostro scopo non importa in quale ordine vengano messi come radice i vari nodi. OGNI NODO DEVE SOLAMENTE ESSERE RADICE UN CERTO NUMERO DI VOLTE

Ci sono due gruppi di nodi. Il generico nodo di un gruppo comunica solo con tutti i nodi del secondo gruppo.

Evoluzione J ( T )

Evoluzione del livello energetico