Algoritmi de dirijare în rețele de senzori

Conducător ştiinţific: Conf. Dr. Ing. Ştefan Stăncescu

Absolvent: Adrian-Alexandru Luca

Cuprins:

Rețele de senzori wireless- aplicații;- caracteristici;- probleme.

Protocoale de rutare- cerințe protocol de rutare performant;- prezentare protocoale studiate: DSDV, AODV, DSR;- optimizarea rutării pe baza căilor multiple.

Metode de evaluare a performanțeiAnaliza rezultatelorConcluzii

Rețele de senzori wireless – Aplicații

Exemple de aplicații: - asistență in caz de incendiu;

- controlul mediului;- clădiri inteligente;- agricultură de precizie; - medicină;- supravegherea utilajelor- logistică.

Rețele de senzori wireless – Caracteristici

auto – organizare dinamicitate scalabilitate costuri scăzute noduri resurse limitate

Rețele de senzori wireless – ProblemeProbleme moștenite de la rețele wireless:

- problema terminalelor ascunse;

- problema terminalelor expuse.

Rețele de senzori wireless – Probleme

Probleme specifice rețelelor de senzori:- securitatea;- legăturile unidirecționale;- energia;- rutarea.

Protocoale de rutare – Cerințe protocol performant

1. Utilizare căi optime;2. Reducere număr mesaje control;3. Evitare bucle infinite;4. Securitate;5. Auto – configurabil;6. Gestiune eficientă a resurselor;7. Face față legăturilor unidirectionale.

Protocoale de rutare – Protocoale studiate DSDV(Destination Sequenced Distance Vector)

• protocol proactiv;• memorează o tabelă de rutare cu toate desținatiile posibile;• alege ruta în funcție de 2 criterii:

- cea mai nouă;- cea mai scurtă.

• actualizare rute periodic sau când au apărut modificări.Avantaje:• rezolvă problema buclelor

infinite.

Dezavantaje:• supraincarcarea inutile a retelei;• problema căi unidirectionale.

Protocoale de rutare – Protocoale studiate AODV(Ad-Hoc On-demand Distance Vector)

• protocol reactiv;• memorează o tabelă de rutare strict necesară;• alege ruta în funcție de 2 criterii:

- cea mai nouă; - cea mai scurtă.

• actualizare la nevoie a informației de rutare.

Avantaje:• rezolva problema buclelor

infinite și a căilor unidirectionale.

Dezavantaje:• pot apărea congestii sau întârzieri

Protocoale de rutare – Protocoale studiate DSR(Dynamic Source Route)

• protocol reactiv;• memorează un cache de rute• alege ruta cea mai scurtă• actualizare informație rutare la nevoie.

Avantaje:• metoda scurtare rute;• rezolva problema buclelor

infinite și a căilor asimetrice.

Dezavantaje:• pot apărea congestii sau întârzieri;• nu face față la rețele de

dimensiuni mari;• rutele vechi nu dispar.

Protocoale de rutareOptimizarea rutării pe baza căilor multiple

AOMDV

• protocol reactiv;• optimizare a protocolului AODV;• reține mai multe rute diferite

pentru o destinație.Avantaje:• reluarea rapidă a transferului de

date la pierderea de rută;

Dezavantaje:• trebuie verificate toate rutele

înainte de a lansa o noua cerere de rută;

Scenarii

1. Scenariul cu variația numărului de noduri

Analiza performanțelor

Tv= momentul în care s-a trimis ultimul pachet de date – momentul când s-a trimis primul pachet de date

Ti = momentul de timp al trimiterii pachetului de date - momentul de timp

al apariției dorinței de trimitere a

pachetului

Timpul de initializare rute Timpul de initializare rute

 

DSDV

AODV

DSR

 AOMDV

 

25 64 100 196 25 64 100 196 25 64 100 196 25 64 100 196Durata de viață 4 4 3 3 1 1 1 1 2 3 4 4 3 2 2 2

Timp de inițializare 4 4 3 3 1 1 1 1 3 3 4 4 2 2 2 2Procent recepție 4 3 2 2 2 4 3 3 1 1 4 4 3 2 1 1

Număr de pachete de date recepționate 2 4 3 3 3 3 2 2 4 1 4 4 1 2 1 1

Throughput 2 3 2 2 4 4 3 3 2 1 4 4 1 2 1 1

Întârzieri capăt la captăt 3 3 3 3 1 2 2 1 4 4 4 4 2 1 1 2

Încărcătura de rutare normalizată 2 2 2 4 3 3 1 1 1 1 4 4 4 4 3 2

Punctaj rețea de 25 de noduri 21 15 17 16

Punctaj rețea de 64 de noduri 23 18 14 15

Punctaj rețea de 100 de noduri 18 13 28 11

Punctaj rețea de 196 de noduri 20 12 28 11

Punctaj total protocoale per scenariu 82 58 87 53

Protocol

Numar de noduri

2. Scenariul cu variația numărului de clustere

2. Scenariul cu variația numărului de clustere

2. Scenariul cu variația numărului de clustere

2. Scenariul cu variația numărului de clustere

Analiza performanțelor

Tv= momentul în care s-a trimis ultimul pachet de date – momentul când s-a trimis primul pachet de date

Ti = momentul de timp al trimiterii pachetului de date - momentul de timp

al apariției dorinței de trimitere a

pachetului

Protocol DSDV AODV DSR AOMDVNumăr de clustere 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4

Durata de viață 4 4 4 4 3 3 3 3 2 2 2 2 1 1 1 1Timp de inițializare 4 4 4 4 2 2 1 1 3 3 3 3 1 1 2 2

Procent recepție 2 2 3 2 3 3 2 3 1 1 1 1 4 4 4 4Număr de pachete de date

recepționate 4 4 2 2 1 1 1 1 2 2 4 4 3 3 3 3

Throughput 2 2 1 1 1 1 2 2 3 3 4 4 4 4 3 3

Întârzieri capăt la captăt 2 2 2 3 3 3 3 2 4 4 4 4 1 1 1 1

Încărcătura de rutare normalizată 2 1 1 1 1 2 2 2 3 3 3 3 4 4 4 4

Punctaj rețea cu 1 cluster 20 14 18 18

Punctaj rețea cu 2 clustere 19 15 18 18

Punctaj rețea cu 3 clustere 17 14 21 18

Punctaj rețea cu 4 clustere 17 14 21 18

Punctaj total protocoale per scenariu 73 57 78 72

3. Scenariul cu variația vitezei de miscare a nodurilor

3. Scenariul cu variația vitezei de miscare a nodurilor

Analiza performanțelor

Tv= momentul în care s-a trimis ultimul pachet de date – momentul când s-a trimis primul pachet de date

Ti = momentul de timp al trimiterii pachetului de date - momentul de timp

al apariției dorinței de trimitere a

pachetului

Protocol AODV DSR AOMDV

Viteza de deplasare (m/s) 1 5 10 15 20 1 5 10 15 20 1 5 10 15 20

Durata de viață 3 3 3 3 3 1 1 1 1 1 2 2 2 2 2Timp de inițializare 1 1 1 1 1 3 3 3 3 3 2 2 2 2 2

Procent recepție 3 3 3 3 3 1 1 1 1 1 2 2 2 2 2

Număr de pachete de date recepționate 2 2 2 2 2 3 3 3 3 3 1 1 1 1 1

Throughput 2 2 2 2 2 3 3 3 3 3 1 1 1 1 1

Întârzieri capăt la captăt 2 2 2 2 2 3 3 3 3 3 1 1 1 1 1

Încărcătura de rutare normalizată 2 2 2 1 2 1 1 1 3 3 3 3 3 2 1

Punctaj viteza de 1 m/s 15 15 12Punctaj viteza de 5 m/s 15 15 12

Punctaj viteza de 10 m/s 15 15 12

Punctaj viteza de 15 m/s 14 17 11

Punctaj viteza de 20 m/s 15 17 10

Punctaj total protocoale per scenariu 74 79 57

4. Scenariul cu variația frecveței de miscare a nodurilor

4. Scenariul cu variația frecveței de miscare a nodurilor

Analiza performanțelor

Tv= momentul în care s-a trimis ultimul pachet de date – momentul când s-a trimis primul pachet de date

Ti = momentul de timp al trimiterii pachetului de date - momentul de timp

al apariției dorinței de trimitere a

pachetului

Protocol AODV DSR AOMDV

Frecvență miscare (Hz) 1/200

1/150

1/100 1/50. 1/10. 1/20

01/15

01/10

0 1/50. 1/10. 1/200

1/150

1/100 1/50. 1/10.

Durata de viață 3 3 3 3 3 2 1 2 1 1 1 2 1 2 2Timp de inițializare 3 3 2 2 2 1 1 1 1 1 2 2 3 3 3

Procent recepție 3 3 3 3 3 1 1 1 1 1 2 2 2 2 2Număr de pachete de date

recepționate 1 3 3 2 2 3 1 1 3 3 2 2 2 1 1

Throughput 2 3 3 2 2 3 1 1 3 3 1 2 2 1 1Întârzieri capăt la captăt 2 2 2 2 2 3 3 3 3 3 1 1 1 1 1

Încărcătura de rutare normalizată 1 1 1 1 2 2 2 2 3 3 3 3 3 2 1

Punctaj frecvență de 1/200 Hz 15 15 12

Punctaj frecvență de 1/150 Hz 18 10 14

Punctaj frecvență de 1/100 Hz 17 11 14

Punctaj frecvență de 1/50 Hz 15 15 12

Punctaj frecvență de 1/10 Hz 16 15 11

Punctaj total protocoale per scenariu 81 66 63

Concluzii

• DSDV are cele mai slabe rezultate;

•DSR obtine rezultate bune, dar nu e scalabil;

•AODV este recomandat pentru scenarii cu clustere;

•AOMDV este recomandat in retele de dimensiuni mari si in scenarii mobile.