Un algoritmo di gossiping per il routing nelle MANET
-
Upload
nunzio-gianfelice -
Category
Technology
-
view
109 -
download
3
description
Transcript of Un algoritmo di gossiping per il routing nelle MANET
UNIVERSITÀ DEGLI STUDI DI BARI FACOLTÀ DI SCIENZE MM.FF.NN.
CORSO DI LAUREA IN INFORMATICA MAGISTRALE
Un algoritmo di gossiping per il routing nelle MANET
Relatore:Chiar.mo Prof. Sebastiano Pizzutilo
Laureando:Nunzio GIANFELICE
Obiettivi della tesi
• Formalizzare un algoritmo di routing per le MANET con una strategia di diffusione di tipo Gossip
• Implementare un sistema di simulazione di tale algoritmo
• Simulare con il nuovo sistema l’algoritmo costruito
Mobile Ad-hoc NETwork
• Cos’è una MANET?Nessun APNodi mobiliCollegamenti wireless
• Routing nelle MANETTopologia sconosciutaEvoluzione dei collegamenti
Algoritmi epidemici• Somiglianza con la diffusione di una malattia infettiva
• Politica di contagio :– Modello di diffusione “anti – entropia”
Push Pull Push/Pull
– Modello di diffusione “gossiping” Gossiping direzionale
• Alta scalabilità del sistema
• Adatto per il routing nelle MANET
• Lavorano bene anche con una topologia di rete sconosciuta
Algoritmo Fast Gossip• L’ idea di un nuovo algoritmo: Fast Gossip
Vantaggi Anti - entropiaVantaggi Gossiping
• Caratteristiche algoritmo Fast Gossip:Due “viste” della rete per ogni nodoNumero di hop nell’ informazione diffusaVariazione lista di “pull”Diffusione basata sull’ effettiva disponibilità di risorse del
nodo
Algoritmo Fast Gossip
Active Thread
Passive Thread
Simulatore di rete• Stato dell’ arte
Network Simulator 2 (1983) Omnet++ (2004)
• Necessità di un simulatore ad-hoc Comportamento singolare dei nodi Alto numero di nodi da generare
• Progettazione del simulatore Sistema a regole con motore
inferenziale (Prolog) Rappresentazione del dominio Sistema di I/O gestito con
tecnologia Java Rappresentazione grafica della
rete in Java
• Caratteristiche considerate:
Proprietà nodo
Timestamp interno
“Passo temporale”
Gestione link fisici
Gestione lista vicini
Funzione di rigenerazione dei nodi
Simulatore di rete
Scenari simualti• Scenario n.1: Campus Universitario
– Dimensione: Grande– N° nodi: Alto– Mobilità: Sostenuta
• Scenario n.2: Parco pubblico cittadino– Dimensione: Media– N° nodi: Medio– Mobilità: Normale
• Scenario n.3: Bar– Dimensione: Piccola– N° nodi: Piccolo– Mobilità: Normale
Scenario n.1: Campus Universitario
• Larghezza area: 600 metri
• Altezza area: 500 metri
• Numero nodi: 1000 nodi
• Velocità nodi: 8 km/h
• Raggio dispositivi: 15 metri
• Passo temporale: 10 secondi
Scenario n.1: Campus Universitario-N° nodi rigenerati costante all’aumentare dei nodi focus
-Media hop decresce con l’aumentare dei nodi focus.
-Il rumore cresce con l’aumentare delle informazioni origine.
-La percentuale di disseminazione cresce con il crescere dei nodi focus
Conclusione e Sviluppi futuri Difficoltà incontrate nella
simulazione dell’ algoritmo
Non è stato confrontato con altri algoritmi di routing per questioni di tempo
Presenta prestazioni più che accettabili in relazione al tempo di diffusione
Grandezza limitata per le code di ‘push’ e ‘pull’
Confronto con altri algoritmi di routing per MANET tradizionali
Sviluppo App per smartphone per lo scambio di informazioni in locale con tecnologia Bluetooth 4.0
Principali riferimenti bibliografici
• P.Eugster- “Epidemic Information Dissemination in Distributed Systems” – IEEE Comuputer Society, Maggio 2004.
• Marco Conti - “Body, Personal, and Local Ad Hoc Wireless Networks” – Consiglio Nazionale delle Ricerche – Pisa- 2003.
• Luciano Maiorino - Tesi di Laurea: “Una rassegna di algoritmi di routing per le reti wireless opportunistiche” - Facoltà di Scienze Matematiche Fisiche Naturali, Università di Bologna – Corso di Laurea Specialistica in Informatica. A.A. 2009-2010.
Grazie per l’attenzione!