Analisi e ottimizzazione del consumo di energia in reti

wireless tramite leader election.

Dal Bianco Palo, Fabris NicolaProf. Schenato Luca

Luglio 2007

1

.

2

4 TEORIA DEI GRAFI

1 Abstract

In questo articolo si considera il problema diottimizzare il consumo energetico in reti wireless(WSN) costituite da nodi alimentati in modo indipen-dente da batterie. La strategia che viene utilizzata equella della rotazione del nodo radice dell’albero dicomunicazione. Per determinare la scelta della radicesono state introdotte delle funzioni costo a partireda quelle piu semplici che eseguono la rotazione ran-dom di tale nodo, a quelle che valutano l’energia delnodo piu scarico per arrivare a quelle piu sofisticatepredicono il dispendio di energia dell’intera rete alpasso sucessivo. Congiuntamente un altra tecnicaper aumentare la durata della rete e quella di uti-lizzare la piu bassa energia di trasmissione possibileper trasferire i dati dai vari nodi alla radice. Il con-fronto delle presatzioni e stato eseguito simulando lediverse reti con l’utilizzo di MatLab.

2 Introduzione

La tipologia della rete di cui ci si occupera inquesto articolo e di tipo Wireless Sensor Network(WSN). Questo tipo di rete e tipicamente formatada nodi costituiti da sensori wireless alimentatitramite batterie. Questa caratteristica ha il notevolevantaggio di poter posizionare sensori in modo moltosemplice in qualsiasi luogo. Purtroppo i sensori conalimentazione autonoma hanno anche un’importantesvantaggio: l’esaurimento dell’energia contenutanelle batterie. Sebbene i sensori siano progettatiper consumare meno risorse possibili i sistemi dirilevamento in cui sono inseriti hanno la necessita didurare il piu a lungo possibile. Inoltre la rete formatada sensori wireless e in genere molto sensibile allaperdita di un nodo, se per esempio si scaricano lebatterie contenute in esso. Questo fatto molte voltee causa del collasso dell’intera rete e l’arresto dellavoro in esecuzione.Da queste considerazioni ci si e posti il problema ditrovare un modo per mantenere attiva la rete per ilperiodo piu lungo possibile. Questo obiettivo e statoperseguito sotto importanti ipotesi. La tipologia direti di sensori che si analizzera in questo articolo haun grafo la cui connettivita che dipende dal grado ditrasmissione e ricezione di ogni nodo. Su tale grafosi e pensato di far comunicare i sensori secondo unastruttura ad albero in cui l’informazione, contenentele misure effettuate, passa dai nodi foglia alla radicela quale avra il compito di trasmettere in blocco i datiricevuti a un PC per un’eventuale elaborazione. Perquest’ultima trasmissione si ipotizza che ogni nodopossa raggiungere il PC. Altre ipotesi proprie della

rete che non vengono trattate in questo articolo perl’eccessiva complessita, ci si riferisce in particolare alprotocollo di trasmissione delle informazioni il qualepuo influire pesantemente sulle prestazioni. Per talimotivi ci si e posti nell’ipotesi che la rete disponga diun protocollo affidabile. Questo permettera di nonporre particolare attenzione all’effettiva connettivitadei cammini scelti.

3 Stato dell’arte

Attualmente c’e una vasta letteratura che trattadi WSN in cui si trovano molte soluzioni sia perquanto riguarda il protocollo che per ottimizzarel’energia e il tempo di vita. Questi danno svariatesoluzioni al problema della costruzione della retetrattando anche l’affidabilita dei protocolli.La gesione dell’energia residua in reti di nodi in-dipendenti e, soprattutto, il suo riparmo attraversotecniche di leader election non riscontra moltaletteratura. Il problema e gia stato affrontato inaltri articoli e risolto in modo alquanto semplice.Gli autori propongono come soluzione di scaricareuniformemente la rete considerando il fatto che,in una data configurazione, la radice e il nodo checonsuma di piu mentre le foglie si scaricano di meno.Sotto questa ipotesi essi assegnano il ruolo di radicead ogni sensore in modo casuale.

4 Teoria dei grafi

4.1 Definizioni generali

Definizione Un grafo non orientato e una coppia(V,E) in cui V e un insieme finito ed E e unafamiglia di coppie non ordinate di elementi di V . Glielementi di V sono chiamati vertici di G, mentre glielementi E sono chiamati lati di G.

Definizione Un grafo si dice completo se contienetutti i possibili lati, cioe se E = {[i, j] : i, j ∈ V, i ≤ j}

Definizione Un grafo G′

= (V′

, E′

) di dicesottografo di G = (V,E) se V

′

⊆ V e E′

⊆ E

Definizione Un cammino di G e una sequen-za di lati consecutivi e1, e2, . . . , ek ∈ E del tipo:e1 = [v1, v2], e2 = [v2, v3], . . . , ek = [vk, vk+1].

Definizione Il vertice v si dice connesso adun altro vertice w se esiste un cammino che li

3

5 COSTRUZIONE DEL GRAFO DELLE CONNETTIVITA

collega. Per definizione ogni vertice e anche connessoa se stesso anche se [v, v] /∈ E.

Definizione Un grafo si dice connesso se i vertici ve w sono connessi per ogni possibile scelta di v, w ∈ V

Definizione Un taglio di G e un insieme dilati del tipo:

δG(S) = {[i, j] ∈ E : |S ∩ {i, j}| = 1}

ove S e il sottoinsieme dei vertici che induce iltaglio(il taglio contiene cioe tutti i lati con unestremo in S e l’altro in V \S).

Definizione Un grafo orientato e una coppiaG = (V,A) in cui V e un insieme finito di vertici edA e una famiglia di coppie ordinate di vertici, dettearchi.Gli archi sono quindi coppie del tipo (i, j) coni, j ∈ V . L’ordine in cui compaiono i vetici erilevante quindi in generale (i, j) 6= (j, i)

4.2 Rappresentazione dei grafi

I grafi, orientati e non possono essere descrittiin maniera molto comoda da opportune matricicon elementi 1, 0 che giocano un importante ruolomatematico nella formalizzazione dei problemi diottimizzazione dei grafi.

Definizione La matrice di adiacenza dei nodiQ di un grafo non orientato G = (V,E) e la matricesimmetrica |V | × |V | con elementi

dij =

{

1 se il [i, j] ∈ E0 altrimenti

Nel caso di un grafo orientato si ha la seguente:

Definizione La matrice di adiacenza Q di ungrafo orientato G = (V,A) e la matrice |V | × |V | conelementi

dij =

{

1 se il [i, j] ∈ A0 altrimenti

Definizione Un grafo parziale (G′

= (V,E′

))di G si dice foresta se e aciclico, cioe non contienecicli. Una foresta e massiamle se ogni lato di E\E

′

forma un ciclo con i lati di E′

.

Definizione Un foresta massimale connessa, seesiste e detta albero. Ogni albero risulta formato daesattamente |V | − 1 lati.

4.3 Algoritmo di Dijkstra

Questo algoritmo richiede cij per ogni (i, j) ∈ Ae permette di calcolare in tempo O(n2) i camminiminimi da un assegnato vertice s a tutti gli altrivertici del grafo. Questi cammini possono essere con-venientemente memorizzati come una alborescenzadi radice s, in cui il padre pred[i] rappresenta il padredel vertice j ∈ V . In questo modo il cammino da ungenerico nodo t alla radice s puo venire ricostruito aritroso partendo da t e passando a pred[t], da pred[t]a pred[pred[t]] e cosı via fino a giungere alla radice s.

L’algoritmo di Dijkstra si basa sulla seguenteproprieta:

Teorema Siano noti i costi Li dei camminiminimi da s ad ogni altro vertice i appartenentead un dato insieme S ⊂ V con s ∈ S. Sia inoltre(v, h) := argmin {Li + cij : (i, j) ∈ δ+(S)}. Secij ≥ 0 per ogni (i, j ∈ A) , allora Lv + cvh rappre-senta il costo del cammino minimo da s a h.

Teorema Dati un grafo G = (V,E) pesato concosti non negativi, le etichette definitive assegnatedall’algoritmo di Dijkstra ad ogni nodo v ∈ R(insieme dei nodi etichettati in maniera definitiva)rappresentano il costo di un cammino minimo da sa tale nodo. Inoltre, ad ogni iterazione intermedia,l’etichetta temporanea di ogni nodo rappresenta ilminimo costo di un cammino da s a tale nodo in cuii nodi intermedi sono tutti in R.

Teorema L’algoritmo di Dijkstra richiede alpiu O(|V |2) operazioni.

5 Costruzione del grafo delle

connettivita

Un aspetto fondamentale delle reti multi-hop e cheal contrario delle tipologie a stella, i nodi usano glialtri nodi per far arrivare i dati alla radice aumen-tando in questo modo il raggio di azione della rete.Per fare questo e necessario che ogni sensore individuiun “percorso” attraverso gli altri sensori che conducaalla radice. Questo compito e svolto appunto dall’al-goritmo di routing. Poiche le scelte ad ogni hop pos-

4

5 COSTRUZIONE DEL GRAFO DELLE CONNETTIVITA

sono essere molteplici bisogna fissare una funzione dicosto del link. L’algoritmo scelto cerchera di individ-uare il percorso che porta alla radice minimizzando ilcosto totale del percorso. Come funzione di costo si escelto di minimizzare il consumo di energia della rete,che ha come diretta conseguenza, il limitare la poten-za utilizzata nella comunicazione dai trasmettitori.Tuttavia diminuendo le potenze dei trasmettitori lecelle di comunicazione dei dispositivi diminuiscono illoro diametro causando un aumentando del numerodi hops necessari per far giungere i dati alla radice.Per quanto riguarda la disposizione dei sensori wire-less abbiamo supposto di poterli collocare su di unospazio planare di dimensioni date, disponendoli al-l’interno di esso in posizioni scelte in maniera ran-dom soddisfacenti il solo vincolo che ogni sensore siain grado di comunicare con almeno un altro sensore.Questa ipotesi che coincide con cio che avviene nellarealta ci permette di ottenere grafi sempre connes-si. Per controllare se il sensore i − esimo e in gradodi comunicare con almeno un altro sensore abbiamodefinito un raggio di comunicazione unico supponen-do che tutti i sensori in esame siano identici. Il raggiodi comunicazione corrisponde alla massima distanzaa cui un sensore puo trasmettere/ricevere utilizzandola massima potenza di trasmissione.

Figura 1: Area di connettivita

Con tale raggio supponendo che il sensore sia in gra-do di comunicare in maniera omnidirezionale e statacostruita la relativa area di comunicazione di formacircolare come mostrato in figura ??. Si viene cosı acreare un grafo delle connettivita tra i vari nodi. Ilmodo che e risultato piu comodo per gestire questografo e quello di utilizzare una matrice delle adiacenzenodo-nodo. Tenendo conto della possibilita dei sen-sori di comunicare da entrambe le parti, cioe se i duesi vedono si puo pensare che il primo possa trasmet-tere e il secondo ricevere oppure viceversa.

Il risultato che si ottiene e che la matrice delle adia-cenze risulta simmetrica per costruzione.Ovviamente

Figura 2: Grafo delle connettivita

rosso blu giallo verderosso 1 1 0 1blu 1 1 0 1

giallo 0 0 1 1verde 1 1 1 1

la diagonale risulta piene di 1 in quanto ogni sensorevede se stesso. Al fine della trasmissione lungo unalbero dei pacchetti generati al nodo i-esimo questocrea delle ambiguita nella scelta del cammino ottimo.Si e cosı deciso di porre a 0 tali elementi sulla diago-nale ottenendo come matrici di adiacenze:

rosso blu giallo verderosso 0 1 0 1blu 1 0 0 1

giallo 0 0 0 1verde 1 1 1 0

A questo punto e possibile ricavare un albero sceglien-do, secondo una data legge, per ogni vertice chi e ilsuo padre e chi sono i suoi figli rispettando ovvia-mente i vincoli che sono dati dalla matrice delle adi-acenze. Nell’esempio di figura ?? si riporta un possi-bile albero, la cui martice delle adiacenze e:

rosso blu giallo verderosso 0 1 0 0blu 1 0 0 1

giallo 0 0 0 1verde 0 1 1 0

5

5 COSTRUZIONE DEL GRAFO DELLE CONNETTIVITA

Figura 3: Grafo delle connettivita

5.1 Funzione costo

L’aspetto fodamentale per risolvere il problemaproposto e trovare una struttura della soluzione chepermetta di eseguire la scelta dell’albero usando unacerta funzione costo C. L’obiettivo della funzionecosto e quella di dare all’algoritmo di calcolo delcambio rete un parametro caratteristico per ognisingolo nodo che ne permetta il confronto e la sceltadella soluzione a minor consumo.Si e cercato di costruire una funzione che permettadi avere una visione generale sul grado di bontadi ogni soluzione adottata. Prima di dare unadescrizione quantitativa delle equazioni viste per C siidentificano le componenti che influicono il consumodi energia di un generico nodo.Un nodo consuma energia principalmente pertrasmettere le proprie informazioni (Ec), per l’at-tivita propria del dispositivo (Ep) e per effettuare lemisure (Es). In genere Ep e trascurabile rispettoa Ec ed Es. Percio Ec e l’energia spesa dal nodoper trasmettere i propri dati generati Et assiemeall’energia di forwarding Ef , ossia quella spesa pertrasmettere i dati dei nodi discendenti al padre. Sipotrebbe considerare anche il consumo per trasmet-tere tutti i dati raccolti dalla radice ad un’unitaesterna Eext tipo un PC o un’altra rete esterna main questo caso la supporremo equivalente ad unaqualsiasi altra trasmissione.

E’ evidente che una fiunzione costo, anche se moltogenerale, puo soddisfare un’ampia serie di richiestema non tutti i casi specifici di progetti reali. Nel-la pratica sara molto probabile che siano necessariedelle aggiunte di parametri che tengano conto delle

caratteristiche particolari del progetto, per esempioil grado di tolleranza alle interferenze dovute a nodivicini ma non direttamente collegati le quali portanoa un’elevato tasso di perdita di informazione.In definitiva i parametri per costruire la funzionecosto sono:

1. Il livello di batteria massimo per ogni nodo B,eventualmente normalizzato all’unita;

2. Ef varia durante la costruzione dell’albero acosto minimo.

3. Un’energia che tiene conto della generazione deidati da parte del sensore Eg = Es +Et potrebbeessere considerata per valutarne la vicinanza alnodo radice. Infatti se un nodo avesse molte op-erazioni da svolgere e da comunicare, la sua vic-inanza alla radice e fondamentale per caricare ilnumero piu piccolo possibile di nodi intermedi.Questo parametro non rientra comunque nellesimulazioni in quanto si e ipotizzato che ogninodo esegua un’unica misura senza aggiungerealtro peso alla trasmissione.

4. L’energia spesa nel cambio rete (Er) ossia ilconsumo che ogni nodo affronta per la gestionedelle trasmissioni relative al cambio della config-urazione della rete sia in termini di trasmissionedi pacchetti sia per le operzioni interne tipo ilrisettaggio della potenza di trasmissione.

Obiettivo generale dell’algoritmo di ottimizzazione eevidentemente la minimizzazione del costo.In prima analisi si e fatto uso di una funzione cos-to semplice nella quale si presuppone che l’energiaspesa da un nodo durante l’attivazione della rete siasostanziamılmente quella spesa in ricezione per ac-qusire le misure dei suoi figli, piu l’energia impiegataper trasmettere tali dati, con l’aggiunta del proprio,al nodo padre. Considerando che l’energia impiegataper ricevere un pacchetto di misura e paragonabile aquella spesa per inviarne un’altro, Etr, nell’ipotesi ditrasmettere alla massima potenza, la relazione dellafunzione costo risulta della forma:

C = Etr(2 ∗ nofigli + 1) (1)

Questa e naturalmente una versione semplificatadel costo che fornisce un modello semplice ma buonodel consumo al nodo. Infatti durante la vita del sen-sore l’energia spesa e in proporzione molto maggioreper ricevere e trasmettere informazioni piu che per lealtre funzioni del dispositivo.In una prima versione degli algoritmi e stata imple-mentata questa relazione in modo da calcolare passoper passo l’energia residua di ogni nodo per poter cosı

6

6 ALBERO FISSO

eseguire la scelta della configurazione dell’albero cheporta ad avere l’energia resiudua nel nodo piu scaricola piu alta possibile eseguendo sostanzialmente unapredizione ad un passo per le energie.

6 Albero fisso

Il primo approccio al problema e stato eseguitosu una versione semplice di rete. Si e pensatoinfatti di eseguire le prove avendo a disposizioneuna struttura ad albero, ottenuta sempre dal grafodelle connessioni, mantenendola costante nel tempo.Questa situazione potrebbe presentarsi nella realtaquando ci sono degli ostacoli, tipo dei muri, tra ivari sensori oppure se il protocollo di comunicazionee molto semplice da non permettere di cambiare lastruttura della rete.Usando un albero fisso ci sono poche possibilita per

Figura 4: Grafo a 6 nodi con una possibile scelta dialbero. Su di esso verranno poi caratterizzati i nodicome foglie o radice

migliorare la vita della rete infatti all’interno dellastruttura si riesce soltanto a modificare la posizionedella radice cercando di far consumare meno i nodigia scarichi. In ogni caso questo approccio nonpermette di sfruttare appieno l’energia a disposizionedella rete in quanto, facendo riferimento alla fig.??,i nodi 3 5 6 non potranno mai diventare nodifoglia in particolare i nodi piu “interni”, in questoesempio il nodo 6, saranno sempre sottoposti a deiconsumi maggiori visto che nel caso migliore avrannocomunque a carico un certo numero, elevato, didiscendenti.Si sono eseguite varie prove sia con un numeroesiguo di nodi (sei per la precisione) sia con una

quantita piu elevata di dispositivi piu vicina a unapresumibile applicazione reale.

Prima di tutte si e simulata la scarica della rete-albero mantenendo fisso anche il nodo radice. Questaprova naturalmente e servita soltanto per avere unpunto di riferimento da cui partire visto che essendoil nodo radice sempre lo stesso e di conseguenza quellocon il consumo massimo, il tempo di vita della rete eminimo. Per dare un’idea partendo da un’energia perogni nodo pari a 5000, con una potenza di trasmis-sione pari a Etr = 1 e usando il grafo di figura ??

in cui si e posto il nodo 4 come radice. si riesconoad eseguire 455 comunicazioni prima che la rete siacollassata per lo spegnimento del nodo 4 dati raccoltisono riportati piu avanti assieme agli altri risultati.

6.1 Modello analitico

In questa sezione si intende fomulare il problemain modo piu formale introducendone una descrizioneanalitica. Si vedra una possibile soluzione che cercadi fornire un modello dinamico del comportamento diun generico nodo.Quello che si cerca di ottenere e in particolare unmodello che descriva l’andamento della carica dellebatterie a disposizione del dispositivo.Si posso subito formulare le prime ipotesi relative algenerico nodo. Per prima cosa il sensore-nodo nonlavora in modo continuo nel tempo bensı si cerca difargli eseguire il minimo delle operazioni in intervallitemporali distaccati da periodi di ‘‘quiete”, in quan-to questa e la prima soluzione per prolungare la vitadelle batterie. Assumendo che tali intervalli abbianouna lunghezza trascurabile rispetto ai periodi in cui ilsensore e in standby e che in questi periodi il consumodi energia sia piccolo, si puo descrivere il sistema neldominio discreto. A questo punto si prende in consid-erazione cosa succede nell’intervallo di tempo in cuiil sensore e attivo. Il nodo puo eseguire varie oper-azioni tra cui eseguire le misure, ricevere e trasmet-tere informazioni. Un’importante semplificazione peri calcoli sta nel fatto di far eseguire le misure nellostesso intervallo temporale in cui vengono trasmessee poter trascurare il loro apporto al consumo rispettoa quello dovuto alla comunicazione. Questa scelta esostenuta dalle caratteristiche del dispositivo raccoltenel data-sheet(vedi tabella).

Percio indicando con x lo stato del sistema-nodointesa come la carica delle batterie contenute al suointerno all’istante k , un primo modello matematicodel nodo potrebbe essere:

x((k + 1)T ) = x(kT ) − T · b(u(kT )) k ∈ Z (2)

7

6 ALBERO FISSO

Figura 5: Consumi del sensore Tmote

dove con T si indica la lunghezza del periodo diquiete, supposto costante.

Questo modello da evidentemente una caratter-izzazione alquanto semplice del dispositivo e dellasua attivita. Per aumentare la bonta del modello sidovrebbe conoscere a fondo anche altri aspetti circail nodo. Uno fra tutti il protocollo di comunicazione.Esso infatti influisce pesantemente sulla quantita didati trasmessi e quindi di energia spesa. Questo estato un problema quando si e voluto tener contoanche di quanto costa ai nodi un cambio di rete.Questa operazione introdotta qui come soluzione peril risparmio di energia, dipende molto dal protocol-lo e in ogni caso porta a un consumo di risorse nontrascurabile.Tali considerazioni hanno portato a dover considerarenel modello un contribiuto aggiuntivo nel caso in cuisi decida di passare a un altro grafo. Si e supposto al-lora che la rete possa cambiare la sua configurazionespendendo un numero minimo di trasmissioni. Il pro-cesso e stato pensato nel modo seguente: quando econveniente cambiare albero, la radice comunica conun’unica trasmissione ai figli la struttura del grafofuturo e questi la ritraspettono ai propri fino a rag-giungere i nodi foglia che riceveranno soltanto l’in-formazione senza piu spedirla. In tale situazione laradice assieme alle foglie spendono uno mentre tuttigli altri nodi due, uno per ricevere e uno pre trasmet-tere.Il nuovo modello sara allora:

x((k + 1)T ) = x(kT ) − T · b(u(kT )) − Csw (3)

dove Csw e il costo di switch che dipende dallaposizione all’interno all’albero del nodo in consider-azione.Per dare un’idea dell’andamento temporale dellecariche di alcuni nodi durante l’evoluzione della retesi riportano i seguento grafici.

Quindi con la funzione costo si dovverbbe essere ingrado di minimizzare la quantita:

max min xi (4)

6.2 Risultati

Si presentano in questa sezione i risultati ottenuti,attraverso tabelle e grafici. Nelle tabelle sonoragruppati i valori di: numero di passi effettuati,l’energia media ancora presente all’interno dei sen-sori e l’efficienza del sistema adottato calcolata conη = 1 − Emedia

Etotale. Tutti riferiti a varie configurazioni

di rete in cui si fanno uso di 6, 15, 25, 40 nodi.Quaranta sensori e pure la quantita che consente ladensita massima al metro quadro di dispositivi[?].Per quanto riguarda i grafici si e preferito rappre-sentare solanto la configurazione finale della caricadella rete. Si e cercato di dare una rappresentazioneintuitiva della carica residua di ogni nodo in duemodi. Il primo e un plot in due dimensioni dellospazio x-y in cui vengono disegnati i nodi e l’alberoche li collega evidenziando con un cerchio blu ilnodo radice in quell’istante cosı pure per il nodopiu scarico con un cerchio rosso. La carica dei nodiinvece e visualizzata come contourf (funzione diMatlab) che pone tonalita verdi attorno ai nodicarichi sfumandole in rosso verso i nodi scarichi.Il grafico in tre dimensioni aggiunge la percezionedell’altezza del grafico in base alla carica di ognisingolo nodo. Per rendere meglio l’idea della caricagenerale della rete si e preferito usare una rappresen-tazione tipo superfice stesa tra i nodi, come si puovedere dalle figure seguenti.In questa sezione si e considerata l’energia ditrasmissione Etr unitaria mentre per quanto riguar-da il valore iniziale della carica dei nodi si eimposto su tutte le simulazini una quantita pari aEiniziale = 5000.

Si riportano qui come esempio le configurazionisemplici di soli sei nodi generate durante lesimulazioni effettuate.

8

6 ALBERO FISSO

0 2 4 6 8 100

1

2

3

4

5

6

7

8

9

10

12

3

4

5

6

x

yGrafo 6 nodi

0 2 4 6 8 100

1

2

3

4

5

6

7

8

9

10

111222

3

4

5

6

x

y

Albero 6 nodi

6.2.1 Radice fissa

Nella prima prova eseguita si e simulata la scari-ca mantenendo, nel piu semplice dei modi, la radicein posizione fissa e di conseguenza anche la configu-razione dell’albeo. Si sono cosı ottenuti i dati ripor-tati in tabella.

no

nodi

no passi E residua

media

efficienza

media

6 455 2880 0.4215 173 3610 0.2425 103 3960 0.1940 64 4160 0.17

In questa situazione e intuibile che la scarica del-l’energia all’interno della rete e la piu sbilanciata. In-fatti il nodo radice ad ogni attivazione consuma sem-pre la maggior quantita di energia. In tal modo si ri-esce ad ottenere un numero esiguo di passi prima cheil nodo radice si spenga facendo decadere la rete. Dal-la tabella si deduce anche che questo comportamentopeggiora all’aumentare del nomero di nodi

6.2.2 Radice casuale

Per ottenere un’evoluzione della scarica piu uni-forme si e passati ad analizzare un grafo in cui ilnodo radice non resta fisso ma viene scelto in modorandom.

Scarica casuale in 252 passi. Valor medio finale: 2725

11

22333

44

555

6

77

8

99

10

1111

121313

1414 1515

0 2 4 6 8 100

1

2

3

4

5

6

7

8

9

10

500

1000

1500

2000

2500

3000

3500

4000

4500

I dati ricavati da questa prova sono riportati nellatabella piu avanti.

Confrontando il numero di passi si nota gia un

no

nodi

no passi E residua

media

efficienza

media

6 750 1380 0.7115 270 2688 0.4925 162 2920 0.4140 100 3120 0.36

miglioramento sensibile rispetto al caso precedente.Inoltre cambiare configurazione ha un effetto mag-giore con un numero di nodi piu alto. Un aspettoda tenere in considerazione e l’efficienza della scar-ica la quale risulta alquanto bassa. Questo fatto enaturale in quanto su una rete ad albero fissata cisaranno sempre nodi periferici molto carichi quandoquelli nelle zone ‘‘interne” sono gia a carica esaurita.

9

6 ALBERO FISSO

Questo fatto lo si nota dalla differenza di colore nelplot in due dimensioni e dalla presenza di cuspidi egole nel grafico in tre dimensioni.

6.2.3 Con costo a energia minore

Per migliorare ulteriormente la scarica complessivadella rete si e cercato di salvaguardare il nodo piuscarico scegliendo ad ogni passo una radice che portil’evoluzione della carica con il minimo piu alto.Si ottengono i seguenti risultati.

Scarica migliore in 285 passi. Valor medio finale: 2564

11

22333

44

555

6

77

8

99

10

1111

121313

1414 1515

0 2 4 6 8 100

1

2

3

4

5

6

7

8

9

10

500

1000

1500

2000

2500

3000

3500

4000

4500

no

nodi

no passi E residua

media

efficienza

media

6 810 600 0.8615 297 2234 0.5325 182 2560 0.4940 114 3280 0.35

Anche con questa soluzione si ottengono dei miglio-ramenti. Anche se l’efficenza migliora di poco si os-serva che il numero di passi effettuato e maggiore.Fino adesso pero non si e mai tenuto in con-siderazione il fatto che per cambiare la posizionedella radice il sistema consuma una porzione nontrascurabile di energia.

6.2.4 Con il costo per il cambio rete

Se nel calcolo dell’evoluzione si valua anche il cosoper cambiare la rete, come descritto in precedenza, siottengono i seguenti risultati.

111

2233

4444

5

66

7

888

99

10

11

1212

13

14

1515

0 2 4 6 8 100

1

2

3

4

5

6

7

8

9

10

500

1000

1500

2000

2500

3000

3500

4000

4500

no

nodi

no pas-

si

E residua

media

efficienza

media

6 155 1890 0.5115 65 3370 0.3425 36 3550 0.2740 26 3420 0.26

E’ evidente che il consumo di risorse per gestirel’operazione di cambio rete influisce molto sulla vitadella rete che adesso si e ridotta a circa un quarto perquaranta nodi ed a circa un quinto per il grafo a seisensori.

6.2.5 CASI DEGENERI

Nella valutazione degli algoritmi si sono identifi-cati anche dei casi degeneri. Le due principali con-figurazioni particolari sono il grafo lineare e quellaa stella. Nel primo ogni nodo e collegato ad altridue,uno che lo precede e l’altro che lo segue. L’altraconfigurazione vede invece un nodo centrale collegatoa tutti gli altrie questi soltanto al primo(si vedano le

10

7 ALBERO VARIANTE

figure sottostanti).

0 2 4 6 8 100

1

2

3

4

5

6

7

8

9

10

1

22

33

44

55

6

Scarica migliore in 811 passi. Valor medio finale: 706

1

22

33

44

55

6

0 2 4 6 8 100

1

2

3

4

5

6

7

8

9

10

500

1000

1500

2000

2500

3000

3500

4000

4500

Casi degeneri con sei nodi: Si nota che le due parti-

tipo

rete

no pas-

si

E residua

media

efficienza

media

lineare 811 706 0.85stella 556 2781 0.44

colari situazioni danno luogo a comportamenti moltodiversi. E’ evidente che un grafo lineare riesce a com-piere molti piu passi rispetto alla configurazione astella inoltre possiede un’efficienza piu alta dovutaalla capacita di scaricare maggiormente la rete.

Casi degeneri con quaranta nodi: Anche con un

tipo

rete

no passi E residua

media

efficienza

media

lineare 125 195 0.96stella 65 4691 0.06

numero piu elevato di nodi disposti secondo gli schemilineare e a stella, si possono dare le stesse conclusioniviste nel caso a sei nodi: il modello stellato non hala capacita di eseguire un numero elevato di passi e

0 2 4 6 8 100

1

2

3

4

5

6

7

8

9

10

11111

2

3

4

5

6

Scarica migliore in 556 passi. Valor medio finale: 2781

11111

2

3

4

5

6

0 2 4 6 8 100

1

2

3

4

5

6

7

8

9

10

500

1000

1500

2000

2500

3000

3500

4000

4500

mantiene un’efficenza molto bassa. Con tanti nodipero si ottengono valori di energia residua alquantobassi per il grafo lineare.

7 Albero variante

Alla luce dei risultati fin qui ottenuti si e sceltodi valutare gli effetti della scelta del cammino otti-mo a partire dal grafo di connettivita al posto cheutilizzare un albero fisso in modo da ottenere unalbero ottimo ad ogni passo. Questo metodo pre-senta una complessita computazionale non trascur-abile gia con un basso numero di nodi. Facciamo oral’esempio di un grafo costituito da n = 10 nodi emettiamoci nella condizione di grafo completamenteconnesso. In numero di archi presenti in tale grafo12n(n − 1) = 45 e il numero di alberi che si possonocostruire e nn−1 = 109. L’assenza di alcuni lati delgrafo riduce in maniera notevole il numero delle possi-bili soluzioni ma il numero delle combinazioni rimanecomunque alto. Siamo quindi stati costretti a ricor-rere alla scelta di eliminare le soluzioni che chiara-mente non portano all’ottimo man mano che venivanoindividuate durante la costruzione dell’albero.

11

7 ALBERO VARIANTE

7.1 Scelta dell’albero

Per la costruzione dell’albero a partire dallamatrice delle adiacenze si e utilizzata la tecnica cheora verra illustrata.La soluzione che e stata trovata per ridurre sensi-bilmente i calcoli e quella di addottare un versioneadattata dell’algoritmo di Dijkstra applicandolo suogni nodo in modo da ottenere esattamente n alberiottimi e tra questi scegliere l’ottimo. La modificaapportata all’algoritmo consiste nel valutare unafunzione costo sull’albero ottenuto aggiungendo ilnodo i-esimo visto dall’insieme di taglio S. Ri-portiamo come esempio la scelta della radice comenodo 4 e la relativa sezione di taglio. In questaconfigurazione il nodo 4 e in grado di comunicarecon i nodi 3, 5. Verranno cosı costruiti 2 alberi

Figura 6: Grafo a 6 nodi con una possibile sezione ditaglio: Passo 1

temporanei ognuno ottenuto aggiungendo alla radiceuno dei due nodi candidati. L’albero che varra sceltosara quello che comportera un costo minore secondola funzione costo adottata. Supponiamo che la sceltaa piu basso costo fornisca come albero provvisorioquello che connette 4 con 5. Viene calcolata la nuovasezione di taglio e questa volta ci sono 2 possibilicandidati ma tre modi diversi con i quali connetterliall’albero precedentemente creato. Viene riapplicatala stessa tecnica di calcolo delle 3 nuove possibliconfigurazioni e ne viene scelta una in base al lorocosto.Si itera questo procedimento fino a connettere tuttii nodi.Si procede con questa tecnica per tutte le possibiliradici che non sono altro che i nodi della rete.

Figura 7: Grafo a 6 nodi con una possibile sezione ditaglio: Passo 2

Figura 8: Grafo a 6 nodi con una possibile sezione ditaglio: Passo 3

7.2 Variazione della potenza di tx

Il consumo di potenza per la trasmissione dei datirisulta essere una delle possibili soluzioni per perme-ttere ai sensori di limitare in consumo dell’energiadelle batterie di cui dispongono.A causa dell’elevata densita di posizionamento chespesso si rende necessaria, i nodi possono realizzarealgoritmi di rete multi hop per raggiungere il correttodestinatario dell’informazione, ma al contempo han-no dei problemi di mutua interferenza.Intervenedo sulla potenza dei trasmettitori, inmaniera da ridurre il raggio di comunicazione dei dis-

12

7 ALBERO VARIANTE

Figura 9: Albero 6 nodi fine costruzione

positivi al minimo indispensabile perche la rete ri-manga connessa, si ottiene anche il benficio di lim-itare le interferenze tra sensori spazialmente vicini chenon sono soggetti a trasferimento di informazioni.Per contro limitare la potenza dei sensori significalimitare la connettivita della rete e questo puo averecome conseguenza una scarica non uniforme.La scelta piu immediata e di cosrtuire un sottografo aminima potenza che risulti comunque connesso. Taleapproccio limita in maniera troppo pesante la connet-tivita e quindi l’evoluzione della rete. Per ovviare aquesto problema si e deciso di sfruttare la possibilitadi scelta della potenza di trasmissione solo in fase dicalcolo della funzione costo e nel relativo aggiorna-mento delle energie e non nella fase della costruzionedelle matrici di adicacenza.

7.2.1 Caso specifico

Per il calcolo della potenza di trasmissione si sonofatte delle ipotesi sulla sua scalabilita da parte deinodi, in base alla configurazione della rete in fasedi iniziallizzazione, scegliendo tra quattro valoripredefiniti. Il legame che esiste tra la potenzadi trasmissione e la relativa distanza massima ditrasmissione puo essere approssimata abbastanzabene con una legge esponenziale del tipo Pt = Dα

con 2 ≤ α ≤ 4. La potenza di ricezione dei varinodi e stata lasciata inalterata e pari alla massimapotenza di trasmissione.Nello specifico abbiamodeciso di ipotizzare α = 2 ottenendo la seguentetabella:

Pmax dmax

34Pmax

√

32 dmax

12Pmax

1√

2dmax

14Pmax

12dmax

7.3 Costo del cambio rete

Fino ad ora si e sempre supposto che ad ogni passosi riconfiguri la rete secondo il nuovo albero di cos-to minimo. Se si vuole tener conto del fatto che ilcambiare rete non e un operazione gratuita in termi-ni di energia e necessario considerare anche questoparametro all’interno della funzione costo. Si e sup-posto che per la riassegnazione della radice tutti inodi, a partire dalla radice, comunichino la nuovaconfigurazione della rete trasmettendo in broadcastai loro figli. Questo si traduce che ogni nodo devemettersi in fase di ascolto, riceve la comunicazioe etrasmetterla ai propri figli. Si ha cosı che il consumoper ogni nodo che non sia foglia e Etr + Erx mentre,per i nodi foglia, si riduce alla sola energia spesa perricevere Erx. Sara quindi l’algoritmo di scelta dell’al-bero ottimo al passo successivo che dovra farsi cari-co di valutare in quali situazioni e energeticamenteconveniente cambiare la rete.

7.4 Risultati

Per ogni funzione costo sono state eseguite 100simulazioni su grafi generati in maniera random inmodo da valutarne le prestazioni. Vengono qui diseguito presentati i risultati ottenuti. I risultatisono stati ottenuti partendo dalla condizione inizialedi batteria carica paria 5000 unita e considerandoil costo di ricezioe e trasmissione uguali e pari a4 unita sono quelli presentati nella tabella. Verrapresentato di funzione in funzione anche un casospecifico riportando il grafo di un possibile albero ela condizione energetica in cui si viene a trovare larelativa rete quando essa e da considerarsi scarica.

7.4.1 Funzione costo energia massima del

nodo piu scarico

Considerando come funzione costo per la scelta del-l’albero e per la sua costruzione la funzione che seglietra tutte le possibili soluzioni quella che lascia il nodopiu scarico della rete ad un energia piu alta. Possiamonotare una scarica della rete che e la migliore, in ter-mini di uniformita e di energia residua minima, che sie ottenuta in fase di simulazione rispetto all’adozionedi tutte le altre funioni costo. Il numero di passi to-tale che riesce ad effettuare la rete e alto ma non e

13

7 ALBERO VARIANTE

il massimo che siamo riusciti ad ottenere. Questo facapire che non sempre l’energia media residua bas-sa e indice della migliore prestazione. La limitazionedi questa funzione costo e quella di tener conto so-lo di massimizzare l’energia del nodo piu scarico enon l’energia che viene spesa dall’intera rete ad ognipasso.

no

nodi

no passi

medio

E resudiua

media

Efficienza

media

6 297 560 0.88815 306 162 0.96725 278 261 0.97940 256 245 0.951

Tabella 1: Funzione costo energia massima nodo piuscarico

0 2 4 6 8 100

1

2

3

4

5

6

7

8

9

10

11111111

22222222222

33333333334444444444

55555555555

6666666666

777777777788888888888

99999991010101010101010

11111111111111

1212121212121212121212121212

131313131313

141414141414

15151515151515151515151515

Figura 10: Grafo albero 15 nodi nodi nodo energiaminima

7.4.2 Funzione costo totale della rete

Considerando come funzione costo la somma deicosti di trasmissione di ogni nodo normalizzato al-la sua carica residua si e andata a scegliere la reteche al passo successivo avrebbe garantito il minorconsumo globale di energia. La funzione costo chevogliamo andare a valutare e: Funzione costo rete=

∑n

1 (nfigli(Etr + Erx) + Etr)1

E(i) dove E(i) e l’en-

ergia del nodo i-esimo al passo corrente. Tale nor-malizzazione fa si che un nodo piu scarico a parita dinumero di figli abbia un costo piu alto.Con questa funzione si ha che il numero di passimedio e aumentato. Indice del fatto che controllarela potenza spesa ad ogni passo permette di gestire larete in maniera ottima. Da notare che comunque siottengono prestazioni peggiori dal punto di vista del-l’efficienza della scarica: mediamente si ha un energiaresidua maggiore.

22

4444444444

5

8

0 2 4 6 8 100

1

2

3

4

5

6

7

8

9

10

0

500

1000

1500

2000

2500

3000

3500

4000

4500

5000

Figura 11: Plot energie residue 15 nodi nodo energiaminima

no

nodi

no passi

medio

E resudiua

media

Efficienza

media

6 369 511 0.89815 312 383 0.92325 297 261 0.94740 266 235 0.953

Tabella 2: Funzione costo totale della rete

0 2 4 6 8 100

1

2

3

4

5

6

7

8

9

10

1111111111122222222222

3333333333

444444444

55555555555

6666666666

77777777777

88888888888

9999999

10101010101010101010

111111

1212121212

1313131313131313

14

151515151515

Figura 12: Grafo albero 15 nodi costo totale dellarete

7.4.3 Funzione costo totale della rete con

potenza di trasmissione diversificata

Nell’ottica di massimizzare il risparmio energeticointeressante e l’aspetto di poter ridurre la potenza di

14

7 ALBERO VARIANTE

35

6

10101010101010

111111

12

0 2 4 6 8 100

1

2

3

4

5

6

7

8

9

10

0

500

1000

1500

2000

2500

3000

3500

4000

4500

5000

Figura 13: Plot energie residue 15 nodi

trasmissione dei sensori in base alla vicinanza del no-do a cui devono tasmettere. In questo caso il nododeve avere la conoscenza della potenza con cui devetrasmettere a ogni suo possibile vicino perche la co-municazione vada a buon fine. Riportiamo i risulatatiottenuti dalle simulazioni e si vede chiaramente dal-la colonna dell’ efficienza che il confronto con il casoprecedente porge un ampio margine di miglioramentocon un numero basso di nodi.

no

nodi

no passi

medio

E resudiua

media

Efficienza

media

6 305 235 0.95315 240 127 0.97425 229 274 094540 210 417 0.917

Tabella 3: Funzione costo totale della rete conpotenza di trasmissione diversificata

7.4.4 Funzione costo totale della rete con

potenza di trasmissione diversificata e

costo cambio rete

Introucendo un costo aggiuntivo per il cambiorete pari al costo di una ricezione e ritrasmissione amassima potenza per i nodi compresi tra l’attualeradice e i figli foglia.Si ha una notevole riduzionedel numero di passi che la rete riesce a effettuare

0 2 4 6 8 100

1

2

3

4

5

6

7

8

9

10

1111111

2222223333333

444444

555555

6666666

777777

8888888

999

101010101010

111111111111111111

121212121212

131313131313

14141414141414

151515151515151515

Figura 14: Grafo di partenza 15 nodi con potenza ditrasmissione diversificata

22223

44

555555

6

0 2 4 6 8 100

1

2

3

4

5

6

7

8

9

10

0

500

1000

1500

2000

2500

3000

3500

4000

4500

5000

Figura 15: Plot energie residue albero 15 nodi conpotenza di trasmissione diversificata

imputabile direttamente alla quantita di energiaspesa per effettuare il cambio e nel contempo lariduzione del numero di volte che la radice vienecambiata. La radice viene cambiata circa un terzodelle volte rispetto a prima. Da notare che comunqueche l’energia residua della rete si mantiene bassa.

7.4.5 Casi degeneri

Vogliamo valutare ora la scarica per alcuni casiparticolari. Utilizzeremo come funzione costo la solafunzione costo totale della rete.

15

7 ALBERO VARIANTE

no

nodi

no passi

medio

E resudiua

media

Efficienza

media

6 257 334 0.93315 234 264 0.94725 212 319 0.93640 178 422 0.915

Tabella 4: Funzione costo totale della rete conpotenza di trasmissione diversificata e costo cambiorete

7.4.6 Grafo completamente connesso

Il grafo che fornisce la presatzione migliore e ovvia-mente quello completamente connesso. In tale graficola scarica e uniforme in quanto scelta la radice tuttigli altri nodi si connettono direttamente ad essa ren-dendo allo stesso tempo minima l’energia spesa dallarete. Riportiamo quello che accade nel caso di pren-dere come funzione costo la funzione energia totaledella rete.

no passi E resudiua

media

Efficienza

424 45 0.991

Tabella 5: Grafo completamente connesso

0 2 4 6 8 100

1

2

3

4

5

6

7

8

9

10

11111111111111

22222222222222

33333333333

44444444444444

55555555555555

66666666666666

77777777777777

88888888888888

99999999999999

1010101010101010101010101010

1111111111111111111111111111

1212121212121212121212121213131313131313131313131313

1414141414141414141414141414

15151515151515151515151515

Figura 16: Grafo albero 15 nodi completamenteconnesso

7.4.7 Grafo lineare

Come caso peggiore si ha il caso di grafo linearenel quale la funzione costo totale della rete utilizza-ta si dimostra non essere la scelta ottima. Durantel’evoluzione della rete essa tende a scaricare i no-di “centrali” per primi in quanto essi realizzano larete di costo complessivo minimo. Procedendo con lascarica la radice viene spostata piu frequentementesui nodi esterni ma dato che le informazioni devono

33333333333

444

0 2 4 6 8 100

1

2

3

4

5

6

7

8

9

10

0

500

1000

1500

2000

2500

3000

3500

4000

4500

5000

Figura 17: Plot energie residue albero completamenteconnesso 15 nodi

comunque transitare per i nodi centrali si ha una pre-matura scarica di questi ultimi rispetto quanto non siriesce a fare utilizzando come funzione costo la sceltadel nodo meno scarico.

no passi E resudiua

media

Efficienza

175 2367 0.523

Tabella 6: Grafo lineare

0 2 4 6 8 100

1

2

3

4

5

6

7

8

9

10

1

22

33

44

55

6

Figura 18: Grafo lineare 6 nodi

16

RIFERIMENTI BIBLIOGRAFICI

33

4

66

0 2 4 6 8 100

1

2

3

4

5

6

7

8

9

10

0

500

1000

1500

2000

2500

3000

3500

4000

4500

5000

Figura 19: Plot energie residue albero lineare 6 nodi

8 Conclusioni

L’analisi dei risultati ottenuti in questo articoloportano a dire che la soluzione semplicistica di farruotare il nodo radice in modo casuale in una strut-tura ad albero data non porta a risultati soddisfacen-ti. La prima grossa limitazione sta propio nella strut-tura ad albero fisso. Con questa soluzione si vanno aperdere tutte le potenzialita della rete wireless legatealla sua elevata connettivita. Riportandosi pero al ca-so di albero fisso si e riusciti ad ottenere prestazionimigliori adottando la previsione ad un passo del con-sumo. In ogni caso pero si e in presenza di energieresidue a fine scarica molto diverse tra i vari nodi.In ogni caso un aspetto importante da tener presentee il costo del cambio rete che nel complesso richiedeuna grossa quantita di energia. Il suo peso effettivopero dipende molto dal protocollo usato e risulta dif-ficoltoso dare una soluzione generale.Un’applicazione in cui si potrebbe avere dei vantaggie il caso degenere di alberi fissi lineari in cui il numerodi passi effettuato nella scarica e maggiore.Per quanto riguarda i risultati ottenuti dalle simu-lazioni sul grafo-tempo variante si nota un abbon-dante incremento delle prestazioni in confronto aquanto si puo ottenere con l’albero fisso. Quandoil numero di nodi e alto e il grafo sufficientementeconnesso si ottengono processi di scarica che portanol’energia residua della rete a valori veramenrte bassi.

Proprio la connettivita e uno dei parametri che in-fluiscono sull’omogeneita della scarica. Se ci si vienea trovare nel caso in cui un gruppo di nodi sono con-nessi ad un altro gruppo di nodi tramite un unico per-corso, che chiameremo critico, possiamo dire a prioriche il tempo di vita della rete sara di gran lunga in-feriore di quello ottenuto da una rete completamenteconnessa. L’individuazione dei cammini criti e la loroinfluenza sulla scarica potrebbe essere un ulterioresviluppo al lavoro fin qui svolto.Migliori sono i risultati ottenuti considerando lepotenze di trasmissione scalabili la cui efficienzatende spesso a 1. Questa rimane comunque una situ-azione puramente teorica in quanto abbiamo suppos-to sia il cambio rete che le attivita del sensore ese-guite a costo energetico nullo. Come si puo vederegia l’introduzione del costo di cambio rete incide inmaniera significativa, non tanto sull’efficienza dellascarica quanto sul numero di passi di evoluzione chesi riescono ad ottenere.

8.1 Appendice

Riferimenti bibliografici

[1] Luca Schenato, Appunti delle lezioni del corsodi progettazione di sistemi di controllo, AnnoAccademico 2006-07

[2] Lezioni di ricerca operativa, Matteo Fischetti

[3] Cluster Aggregation Point Reassignment forLoad Balancing in Sensor Networks, AntonioG. Ruzzelli, Raja Jurdak, Gregory M.P. O’HareSchool of Computer Science and Informatics,University College Dublin, Ireland

[4] WSNlabTutorial, www.ing.UniBs.it/ wsnlab

[5] Local Leader Election, Signal Strength AwareFlooding, and Routeless Routing, Gilbert Chen,Joel W. Branch, and Boleslaw K. SzymanskiCenter for Pervasive Computing and Networking,

[6] Secure Leader Election in Wireless Ad Hoc Net-works, Sudarshan Vasudevan.. , Brian DeCleene ,Jim Kurose.. , Don Towsley

17