CAPITOLO VIII SIMULAZIONE PROTOCOLLO DI ROUTING

(1)

CAPITOLO VIII

SIMULAZIONE PROTOCOLLO

DI ROUTING

Per valutare le prestazioni dell’algoritmo per la costruzione ed il manteni-mento dell’albero di Routing tra i nodi di Rete di Sensori è stato implemen-tato un simulatore. È simplemen-tato usato il linguaggio di programmazione C++ ed il modello adottato è quello della Simulazione ad eventi.

Sono state effettuate le seguenti ipotesi esemplificative: • I nodi Sensore sono disposti in una struttura a griglia

• Ogni nodo è capace di inviare e di ricevere messaggi da tutti i nodi distanti un hop dal nodo stesso. Come mostrato in Figura 8.1, cia-scun nodo può comunicare al massimo con otto nodi vicini.

• Il protocollo MAC utilizzato è l’ 802.11 considerando il caso peggio-re riguardo le possibili interfepeggio-renze e le possibili ritrasmissioni effet-tuate da ciascun Nodo Sensore. Sono stati presi in considerazione tutti i nodi vicini che potrebbero disturbare la trasmissione di un messaggio.

• La scarica delle batterie installate nei Nodi Sensore è stata assunta lineare.

Il raggio di trasmissione di ciascun nodo è stato assunto pari a 55 metri e per quanto riguarda i consumi energetici sono state prese come riferimen-to alcune misurazioni sperimentali [Falchi] effettuate sui MICA2 motes in dotazione al nostro dipartimento. Infatti, in [Falchi] è stato rilevato che in

(2)

ambiente open-space la percentuale di pacchetti persi tra due Mica2 mo-tes disposti ad una distanza di 55 metri è inferiore al 15%.

Figura 8.1 Raggio Di Comunicazione di un Nodo Sensore

Per le simulazioni abbiamo supposto che su tutti i nodi sensore sia già sta-ta inssta-tallasta-ta una interrogazione di tipo non aggregato con un Communica-tion Period pari a 3 minuti. Un esempio di interrogazione di tale tipo è la seguente:

SELECT light FROM sensors

EPOCH DURATION 180s RELIABILITY 1

Per quanto riguarda il protocollo di Routing abbiamo stabilito che il refresh

periodico avvenga ogni due giorni.

Nella simulazione è stato considerato anche il protocollo di scheduling tra i nodi della rete (Capitolo 6) con l’ipotesi esemplificativa che non ci siano variazioni nella durata dei Talk Interval e dei Communication Period. I nodi Sensore stanno quindi accesi solo nel periodo di tempo in cui devono co-municare con il nodo padre e con i figli e dopo vengono messi nello stato di sleep fino al Comunication Period successivo.

(3)

8.1 Indici di Prestazione

Per tutte le simulazioni effettuate è stata presa in considerazione una rete quadrata di 11x11 nodi Sensore con distanza tra i sensori pari a 55 metri (cioè equivalente al raggio di trasmissione dei nodi). Il nodo Sink è stato posto al centro della rete. Data la simmetria della rete anche gli indici di prestazione sono stati calcolati tenendo conto di ciò. In particolare la rete è stata suddivisa in zone in base al numero minimo di hop con cui ogni nodo può raggiungere il nodo Sink. Con questo criterio sono state indivi-duate sei zona significative e mostrate nella Figura 8.2. Al centro è presente il nodo Sink, gli otto nodi Sensore intorno fanno parte della Zona1. Procedendo in questo modo si incontrano rispettivamente i sedici nodi della Zona2, i ventiquattro della Zona3, i trentadue della Zona4 ed infine i quaranta della Zona5. La motivazione di tale suddivisione è che i nodi appartenenti alla stessa zona svolgono, a parità di condizioni energetiche, gli stessi ruoli nella rete. Infatti, tramite il protocollo mostrato nel capitolo precedente l’albero di Routing viene costruito a partire del nodo Sink procedendo verso la periferia della rete.

Gli indici di prestazione che sono stati presi in considerazione possono essere divisi in due categorie. Tali indici sono calcolati per ogni zona della rete.

La prima categoria riguarda gli indici Energetici e comprende:

• Energia: cioè l’evoluzione dell’energia di ogni nodo al trascorrere del tempo di vita della rete;

• Delta-Energia: ad un dato istante t di vita della rete la grandezza Delta-energia relativa alla Zona i è così definita:

Delta-Energia (t)= E_i

( )

_r _MAX - E

( )

_s _MIN t.c. r,s nodi Sensore Zona-i

{

∈

}

Una seconda categoria di indici prestazionali riguardano le caratteristiche

(4)

• Livelli Albero : numero di livelli che compongono l’albero di Rou-ting;

• Livello: Livello medio occupato nell’albero di Routing dai nodi ap-partenenti alla stessa Zona della rete;

• Figli: numero medio di Figli relativi ai nodi appartenenti alla stessa Zona dell’albero di Routing;

• Discendenti: numero medio di discendenti relativi ai nodi apparte-nenti alla stessa Zona dell’albero di Routing.

In seguito sono riportate le descrizioni ed i risultati ottenuti dalle simula-zioni effettuate. Ogni risultato mostrato è la conseguenza della media dei risultati ottenuti da otto Simulazioni effettuate con le stesse condizioni ini-ziali.

Figura 8.2 Rete usata per le Simulazioni e relativa divisione in Zone

SINK ZONA 1 ZONA 2

ZONA 3 ZONA 4 ZONA 5

(5)

8.2 Risultati delle Simulazioni

Sono stati presi in considerazione due tipi di configurazione di rete. I primi tipi di test sono stati effettuati partendo dalla condizione iniziale in cui tutti i nodi hanno la stessa carica energetica (tutti i nodi con energia iniziale pari al 100%). In seguito la rete è stata sbilanciata dal punto di vista energeti-co.

8.2.1 SIMULAZIONI CON RETE OMOGENEA DAL PUNTO DI VISTA ENERGETICO

Densità Rete=1

La prima situazione esaminata è quella in cui la rete è composta da 121 nodi e tutti i nodi hanno inizialmente una energia pari al 100%.

L’evoluzione della rete dal punto di vista energetico è riportato in Figura8.3. Da questo grafico è facilmente evidenziabile come per un nodo sensore l’attività di Routing risulti energeticamente più costosa rispetto all’attività di sensing. Infatti la rete cessa di funzionare perché i nodi della Zona1 sono scarichi e quindi al nodo Sink non vengono recapitati i risultati degli altri nodi della rete. Tutto il resto della rete potrebbe comunque con-tinuare a operare per molti altri giorni. Questo è dovuto al fatto che i nodi distanti un hop dal Sink devono recapitare al nodo Sink tutti i rilevamenti effettuati dagli altri nodi della rete. Tale aspetto risulta meno accentuato man mano che ci spostiamo verso le zone periferiche della rete. I nodi del-la zona 5 svolgono quasi esclusivamente il ruolo di foglia ed è per questo che alla fine la loro energia media risulta superiore al 90% dell’energia ini-ziale.

Un ulteriore miglioramento che può essere apportato al protocollo potreb-be essere quello di studiare una tecnica per spostare nel tempo la posi-zione del nodo Sink (applicazione permettendo) in modo da uniformare il consumo energetico su tutti i nodi della rete.

(6)

Comunque il protocollo presentato riesce ad uniformare il consumo ener-getico tra i nodi appartenenti alla stessa zona della rete.

Questa caratteristica risalta particolarmente dal grafico in Figura 8.4 in cui viene riportato il valore della quantità Delta-Energia descritta in preceden-za. In tutte le zone della rete questa grandezza rimane contenuta per tutta la durata della rete (il valore massimo è di 3,44 e viene raggiunto dai nodi della zona1).

Passando ora agli aspetti strutturali dalla Figura 8.5 vediamo come l’albero di Routing risulti sempre compatto (tranne qualche lieve e regolare

perturbazione) fino agli ultimi istanti di vita della rete. Negli ultimi giorni di vita della rete alcuni nodi della zona 1 cadono in quanto scarichi energeti-camente e di conseguenza si ha un allungamento dell’albero. L’allungamento è dovuto al fatto che alcuni nodi della zona2 non possono più comunicare direttamente con i nodi della zona1 in quanto caduti ma devono scegliere come padre un nodo della stessa zona.

Tale aspetto risulta evidenziato anche nell’andamento del livello medio occupato dai nodi di ogni zona della rete e riportato in Figura 8.6 ed anche nella Figura 8.7 dove sono riportati il numero di figli per i nodi di ogni zona della rete. ENERGIA 0 20 40 60 80 100 120 1 ₁₃ ₂₅ ₃₇ ₄₉ ₆₁ ₇₃ ₈₅ 97 109 121 133 145 157 169 181 193 205 217 229 241 TEMPO (giorni)

ZONA1 ZONA2 ZONA3 ZONA4 ZONA5

(7)

DELTA ENERGIA 0 0,5 1 1,5 2 2,5 3 3,5 4 1 ₁₂ ₂₃ ₃₄ ₄₅ ₅₆ ₆₇ ₇₈ ₈₉ 100 111 122 133 144 155 166 177 188 199 210 221 232 243 TEMPO (giorni)

Figura 8.4 Rete Energia Iniziale=100% Densità=1:Delta Energia

LIVELLI ALBERO 3 4 5 6 7 8 9 10 0 ₁₂ ₂₄ ₃₆ ₄₈ ₆₀ ₇₂ ₈₄ ₉₆ 108 120 132 144 156 168 180 192 204 216 228 240 TEMPO (giorni)

(8)

LIVELLO 0 1 2 3 4 5 6 7 0 ₁₂ ₂₄ ₃₆ ₄₈ ₆₀ ₇₂ ₈₄ ₉₆ 108 120 132 144 156 168 180 192 204 216 228 240 TEMPO (giorni)

Figura 8.6 Rete Energia Iniziale=100% Densità=1:Livello

FIGLI -1 0 1 2 3 4 5 6 7 8 9 0 ₁₂ ₂₄ ₃₆ ₄₈ ₆₀ ₇₂ ₈₄ ₉₆ 108 120 132 144 156 168 180 192 204 216 228 240 252 TEMPO (giorni)

ZONA1 ZONA2 ZONA3 ZONA4 ZONA5 SINK

(9)

Densità Rete=0,9

Una seconda serie di simulazioni è stata effettuata prendendo in conside-razione una rete in cui la densità dei nodi non fosse pari ad 1 (come nel caso precedente), ma pari a 0,9.

Sotto queste ipotesi sono state prese in considerazioni due configurazioni di rete. La prima, mostrata in Figura 8.8, in cui la distribuzione dei “buchi” risulta abbastanza uniforme mentre nella seconda (Figura 8.9) in cui i “bu-chi” risultano addensati in particolari zone della rete. Mentre le simulazioni per la rete di Figura 8.8 hanno dato esiti molto simili a quelli esaminati in precedenza per una rete con densità 1, le simulazioni per l’altro tipo di rete hanno evidenziato, come risalta dall’andamento della grandezza Delta-Energia nella Figura 8.10, come il bilanciamento del consumo energetico tra i nodi della rete non sia sempre possibile. Naturalmente questo è lega-to alla particolare configurazione di rete in cui alcuni nodi sono sempre co-stretti a consumare più energia rispetto ad altri nodi appartenenti alla stes-sa zona (in particolare questo accade per i nodi della zona2).

(10)

Figura 8.9 Schema Rete Energia Iniziale=100% Densità=0,9-Test2 DELTA ENERGIA 0 5 10 15 20 25 30 1 11 21 31 41 51 61 71 81 91 101 111 121 131 141 151 161 171 181 191 201 211 221 TEMPO (giorni)

(11)

8.2.1 SIMULAZIONI CON RETE NON OMOGENEA DAL PUNTO DI VISTA ENERGETICO

Una seconda tipologia di esperimenti sono stati effettuati prendendo in considerazione una rete i cui nodi inizialmente non fossero nella stessa si-tuazione energetica.

In particolare è stato simulato il comportamento della rete in 3 particolari configurazioni di partenza:

• Rete con 25 nodi con Energia iniziale Random mentre i rimanenti nodi della rete con energia iniziale del 100% (Figura 8.11)

• Rete con 50 nodi con Energia iniziale Random mentre i rimanenti nodi della rete con energia iniziale del 100% (Figura 8.12)

• Rete con tutti i nodi della rete con energia iniziale Random. Per questo tipo di simulazione sono stati presi in considerazione 2 par-ticolari tipi di rete (mostrati in Figura 8.13 ed in Figura 8.14 )

43% 68% 54% 66% 43% _75% _54% 91% 97% 89% 76% 55% 90% 74% 90% 63% 72% 95% 65% 40% 88% 45% 87% 53% 76%

(12)

Figura 8.12 Schema Rete 50 Nodi con Energia Iniziale Random 76% 78% 99% 44% 35% 27% 5% 79% 39% 90% 34% 65% 98% 54% 66% 63% 87% 45% 95% 39% 77% 23% 97% 64% 72% 86% 53% 95% 58% 66% 40% 54% 75% 78% 44% 87% 74% 97% 55% 65% 45% 65% 84% 82% 81% 72% 92% 78% 53% 65%

(13)

Figura 8.13 Schema Rete Tuttti i Nodi con Energia Iniziale Random-Test1

Figura 8.14 Schema Rete Tuttti i Nodi con Energia Iniziale Random-Test2

1% 61 88 29 65 55 65 45 26 61 16 27 13 26 94 56 52 74 13 31 53 97 17 82 46 44 72 48 57 91 76 64 48 13 68 31 33 54 34 26 14 8% 28 53 80 31 1% 57 50 36 38 59 56 39 25 15 53 42 10 89 10 31 13 51 57 37 46 62 90 97 9% 74 30 29 61 56 76 36 59 10 81 38 46 40 28 75 90 11 73 88 21 26 79 44 17 18 61 70 57 68 8% 82 3% 99 25 84 32 78 60 68 54 99 1% 10 34 19 88 86 66 40 50 56 27 30 12 90 56 8% 11 15 37 24 43 47 7% 65 30 77 60 31 84 62 97 35 19 82 79 6% 8% 96 98 25 67 2% 73 85 52 30 94 46 58 80 59 11 26 64 40 40 13 35 35 19 16 96 94 78 40 49 72 42 57 10 83 41 1% 89 86 66 56 30 48 82 75 79 21 76 99 63 82 84 33 58 71 34 14 89 21 12 56 64 63 77 53 18 95 54 83 45 22 24 62 9% 84 10 46 80 74 90 99 45 32 70 5% 62 37 37 5% 10 10 97 54 27

(14)

8.2.1.1 RETE CON 25 NODI CON ENERGIA INIZIALE RANDOM

Da questo tipo di configurazione abbiamo avuto la conferma che il proto-collo proposto tende a bilanciare l’energia dei nodi della rete. Infatti nella Figura 8.15 viene riportato l’andamento dell’energia dei nodi della zona 1. Le due curve sono riferite ai nodi con energia iniziale al 100% e ai nodi con energia iniziale Random. Dal grafico è possibile notare come la di-stanza tra le due curve tende a diminuire all’aumentare del tempo di vita della rete. Nel finale del grafico le due curve vanno a coincidere. Infatti il protocollo riduce il consumo energetico ai nodi con energia minore a di-scapito di quelli con energia maggiore. Tale cosa è realizzata facendo leva sul ruolo di router assunto da ogni nodo. I nodi con alta energia devono ef-fettuare l’inoltro dei risultati degli altri nodi della rete verso il nodo Sink

mentre i nodi della zona 1 con energia iniziale minore del 100% assumono essenzialmente il ruolo di nodo foglia. Questa cosa è confermata nel grafi-co di Figura 8.16 dove è mostrato il numero di figli per i nodi della zona1 (sempre diviso in nodi con energia iniziale del 100% e nodi con Energia iniziale Random). Dal grafico si nota come i nodi della Zona1 con energia iniziale Random inizialmente non abbiano figli mentre, quando l’energia di tali nodi risulta simile a quella degli altri nodi della zona1, i figli vengano equamente divisi tra tutti i nodi della zona1. Una cosa analoga accade per il numero di discendenti e che è mostrata in Figura 8.17.

Sono stati riportati solo i risultati relativi ai nodi della zona1 ma anche per i nodi delle altre zona della rete gli andamenti risultano analoghi a quelli appena presentati anche se meno accentuati. Infatti, per i nodi delle zone periferiche risulta più difficile effettuare un bilanciamento energetico in quanto il lavoro da Router risulta già in partenza alleggerito rispetto ai nodi delle zone vicine al nodo Sink.

Infine, la Figura 8.18 mostra l’andamento della lunghezza dell’albero di

Routing. Fin dall’inizio l’albero non è molto compatto in quanto i nodi sono disposti su 7 livelli e non sui 6 minimi. Alla fine della rete l’albero, come accadeva anche nei test precedenti, tende a rilassarsi e quindi ad allun-garsi.

(15)

8.2.1.2 RETE CON 50 NODI CON ENERGIA INIZIALE RANDOM

Per questo tipo di rete i risultati trovati sono molto simili a quelli appena presentati e quindi non sono mostrati. Unica cosa da rilevare rispetto al caso precedente è sull’evoluzione della lunghezza dell’albero di Routing. Inizialmente l’energia tra i nodi della rete è molto disomogenea e quindi l’albero assume 8 livelli. Con il passare del tempo il protocollo tende a bi-lanciare l’energia dei nodi e quindi l’albero si comprime su 7 livelli. Sul finale si ha il naturale allungamento dell’albero dovuto alla caduta di alcuni nodi. ENERGIA ZONA1 0 20 40 60 80 100 120 1 ₁₂ ₂₃ ₃₄ ₄₅ ₅₆ ₆₇ ₇₈ ₈₉ 100 111 122 133 144 155 166 177 188 199 210 221 232 TEMPO (giorni)

NODI100% ALTRI NODI

(16)

FIGLI ZONA1 -0,5 0 0,5 1 1,5 2 2,5 3 3,5 0 ₁₂ ₂₄ ₃₆ ₄₈ ₆₀ ₇₂ ₈₄ ₉₆ 108 120 132 144 156 168 180 192 204 216 228 TEMPO (giorni)

NODI100% ALTRI NODI Poli. (NODI100%) Poli. (ALTRI NODI)

Figura 8.16 Rete 25 Nodi con Energia Iniziale Random:Figli Zona1

DISCENDENTI ZONA1 0 5 10 15 20 25 30 0 ₁₂ ₂₄ ₃₆ ₄₈ ₆₀ ₇₂ ₈₄ ₉₆ 108 120 132 144 156 168 180 192 204 216 228 TEMPO (giorni)

NODI100% ALTRI NODI Poli. (NODI100%) Poli. (ALTRI NODI)

(17)

LIVELLI ALBERO 6 6,5 7 7,5 8 8,5 9 0 ₁₂ ₂₄ ₃₆ ₄₈ ₆₀ ₇₂ ₈₄ ₉₆ 108 120 132 144 156 168 180 192 204 216 228 TEMPO (giorni)

Figura 8.18 Rete 25 Nodi con Energia Iniziale Random:Livelli albero di Routing

LIVELLI ALBERO 0 2 4 6 8 10 12 0 ₁₀ ₂₀ ₃₀ ₄₀ ₅₀ ₆₀ ₇₀ ₈₀ ₉₀ 100 110 120 130 140 150 160 170 180 190 200 210 220 TEMPO (giorni)

(18)

7.2.1.3 RETE CON TUTTI I NODI CON ENERGIA INIZIALE RANDOM

L’ultima tipologia di simulazioni effettuate è stata quella con una rete in cui tutti i nodi avessero come energia iniziale un valore scelto in modo

Random da una distribuzione uniforme. Sono stati eseguiti simulazioni con

due tipologie di rete distinte.

Nel primo test i risultati ottenuti confermano essenzialmente le simulazioni mostrate fino ad ora.

Dal grafico di Figura 8.20 vediamo l’andamento energetico dei nodi appar-tenenti alle varie zone della rete. È facile notare come la curva dei nodi della zona1 abbia un coefficiente angolare maggiore rispetto alle altre cur-ve.

Invece, dalla Figura 8.21 che riporta l’andamento della grandezza Delta-Energia, vediamo come il protocollo tende a diminuire il gap energetico presente tra nodi appartenenti alla stessa zona della rete di Sensori. L’equilibrio energetico naturalmente risulta più evidente per i nodi delle zone centrali della rete rispetto a quelli delle zone periferiche.

Come accadeva per la simulazione con una rete in cui per 50 nodi l’energia iniziale fosse stabilita in modo Random anche in questo caso l’albero di Routing (Figura 8.22) , dopo i primi istanti in cui conta di 10 li-velli, tende a compattarsi in corrispondenza del riequilibrio energetico per poi rilassarsi definitivamente verso la fine della vita della rete.

L’evoluzione dell’albero di Routing è confermata anche dall’andamento del livello medio occupato dai nodi di ciascuna zona mostrato in Figura 8.23. In Figura 8.24 è invece mostrato l’evoluzione del numero di figli per i nodi di ogni zona della rete. La caduta dei nodi della zona 1 è evidenziata dai bruschi ripieghi verso il basso della curva relativa al nodo Sink. Natural-mente la caduta di un nodo porta all’aumento del numero medio di figli sia per i nodi della stessa zona (in quanto i figli del nodo caduto sono spartiti tra i rimanenti nodi della stessa zona), sia dei nodi della zona inferiore (al-cuni nodi di tale zona potrebbero non essere più raggiungibili dai nodi del-la zona inferiore).

(19)

Infine, in Figura 8.25 è mostrato l’andamento del numero di discendenti che risulta compatibile con quello del numero di figli appena esaminato. Le simulazioni sull’altra tipologia di rete (Figura 8.14) ha essenzialmente confermato i risultati appena mostrati. L’unica cosa di rilievo da far notare è come non sempre è possibile riequilibrare l’energia dei nodi appartenenti alla stessa zona. Infatti, in Figura 8.26, vediamo come la grandezza delta-energia non sempre tende a diminuire ma, in alcuni momenti, al contrario tende a crescere. ENERGIA 0 10 20 30 40 50 60 1 7 ₁₃ ₁₉ ₂₅ ₃₁ ₃₇ ₄₃ ₄₉ ₅₅ ₆₁ ₆₇ ₇₃ ₇₉ ₈₅ ₉₁ 97 103 109 115 121 TEMPO (giorni)

(20)

DELTA ENERGIA 0 20 40 60 80 100 120 1 7 ₁₃ ₁₉ ₂₅ ₃₁ ₃₇ ₄₃ ₄₉ ₅₅ ₆₁ ₆₇ ₇₃ ₇₉ ₈₅ ₉₁ ₉₇ 103 109 115 121 TEMPO (giorni)

Figura 8.21 Rete Tuttti i Nodi con Energia Iniziale Random-Test1:Delta Energia

LIVELLI ALBERO 0 2 4 6 8 10 12 14 0 6 ₁₂ ₁₈ ₂₄ ₃₀ ₃₆ ₄₂ ₄₈ ₅₄ ₆₀ ₆₆ ₇₂ ₇₈ ₈₄ ₉₀ ₉₆ 102 108 114 120 TEMPO (giorni)

(21)

LIVELLO 0 1 2 3 4 5 6 7 8 0 6 ₁₂ ₁₈ ₂₄ ₃₀ ₃₆ ₄₂ ₄₈ ₅₄ ₆₀ ₆₆ ₇₂ ₇₈ ₈₄ ₉₀ ₉₆ 102 108 114 120 TEMPO (giorni)

Figura 8.23 Rete Tuttti i Nodi con Energia Iniziale Random-Test1:Livello

FIGLI 0 1 2 3 4 5 6 7 8 9 0 6 ₁₂ ₁₈ ₂₄ ₃₀ ₃₆ ₄₂ ₄₈ ₅₄ ₆₀ ₆₆ ₇₂ ₇₈ ₈₄ ₉₀ ₉₆ 102 108 114 120 TEMPO (giorni)

(22)

DISCENDENTI 0 20 40 60 80 100 120 140 0 6 ₁₂ ₁₈ ₂₄ ₃₀ ₃₆ ₄₂ ₄₈ ₅₄ ₆₀ ₆₆ ₇₂ ₇₈ ₈₄ ₉₀ ₉₆ 102 108 114 120 TEMPO (giorni)

Figura 8.25 Rete Tuttti i Nodi con Energia Iniziale Random-Test1:Discendenti

DELTA ENERGIA 0 20 40 60 80 100 120 1 8 15 22 29 36 43 50 57 64 71 78 85 92 99 106 113 120 127 134 141 148 TEMPO (giorni)