Caso di studio particolare nelle reti wireless:

Wireless Sensor Network

Seminario di Simulazione di Sistemi Andrea Sghedoni A.A. 2014/2015 Gruppo 5

Architettura Wireless● La rete di comunicazione tra diversi terminali avviene

senza l’utilizzo di cavi trasmissivi● Principio di trasporto delle informazioni si basa su onde

elettromagnetiche● Standard IEEE 802.11● Situazioni attuali:

○ in presenza di un access point○ in assenza di un access point (ad-hoc networking)

2/19

Strumenti a disposizione della simulazione - NS2

● Approccio ibrido tra i linguaggi C++ e Otcl● Tcl è un linguaggio di scripting, realizzato per una

migliore usabilità del tool e una migliore interazione con gli utilizzatori

● Permette di studiare numerosi aspetti legati alle reti (es algoritmi routing, protocolli, gestione traffico)

● Caso di studio (focus su throughput, packet drop rate, end to end delay)

3/19

Objective Modular Network Test-bed OMNeT++

● Framework C++● Simple Module/Compound Module/Network(top-level module)● Scambio messaggi (self-msg→ self schedule)● Network Description language (NED)● Output e prime considerazioni● File .ini

4/19

Wireless Sensor Network● Certo numero di sensori distribuiti in un’area● Possono esser posizionati in ambienti ostili● Allo stesso tempo vi è necessità di reperire informazioni

dall’ambiente circostante● Ambiti applicativi sono molteplici:

○ monitoring situazioni ambientali/climatiche [inquinamento, livello precipitazioni ...]

○ elettrodomestici, domotica in particolare○ rilevamenti geografici 5/19

Struttura interna sensore● Coordinator mette in relazione i componenti

hardware con lo stack software● Batteria fornisce l’energia necessaria per il

completo funzionamento del sensore● Radio permette la comunicazione wireless

con gli altri nodi della rete. In un determinato istante può essere in uno dei seguenti stati: idle, sleep, transmit, and receive

● CPU è un’unità di calcolo elementare che può trovarsi in idle, sleep e active state

● Wireless channel può avere differenti modelli di propagazione come Free Space Propagation e Two-ray ground reflection

6/19

Problematiche di comunicazione a basso livello : Mac Layer

● Mac Layer si preoccupa di determinare l’accesso al canale trasmissivo di un nodo che intende trasmettere informazioni

● Necessità di protocolli che rilevino le collisioni tra pacchetti, generando così interferenza sul ricevitore

● Lo standard 802.11 in assenza di un controllo centrale utilizza il protocollo CSMA/CA

7/19

Stazione nascosta & stazione esposta

A B C STAZIONE NASCOSTA:● C sta trasmettendo a B, rilevando il canale vuoto● A pensa erroneamente di poter inviare a B● Collisione

portata onde radio di C

A B C STAZIONE ESPOSTA:● A sta trasmettendo a D● B vorrebbe trasmettere a C, ma rileva una

trasmissione sul canale● Mancata trasmissione di B portata onde

radio di A

D8/19

Soluzione protocollo CSMA/CA

A BC

A vuole inviare un pacchetto a B● A invia a B un RTS● B concede il permesso con un CTS● A invia il frame dati a B● B conferma ad A di aver ricevuto il pacchetto dati con un

ACK● C rileva l’RTS inviato da A e decide di non trasmettere per

non creare interferenze ● D rileva invece il CTS inviato da B e decide anch’esso di

rimanere inattivo per non creare interferenze● L’inattività dura finchè B non reinvia l’ACK di conferma ad

A (rappresentato da NAV)

portata onde radio di A

Dportata onde radio di B

ABCD

RTS

CTS

dataACK

NAV

NAV

RTS : Request To SendCTS : Clear To SendNAV : Network Allocation vector

SIFS DIFS

● SIFS: nodi coinvolti si scambiano messaggi di sincronizzazione

● DIFS: dopo un certo intervallo qualsiasi altro nodo può cercare di impossessarsi del canale di comunicazione 9/19

SIFS : Short Inter Frame SpaceDIFS : Distributed Inter Fame Space

Network Layer● Si supponga di voler campionare una certa misura, in

una determinata regione target della nostra WSN● Efficienza nel routing e risparmio energetico

○ flooding totale nella rete rappresenta una soluzione totalmente inefficiente dal punto di vista energetico e ridondanza dei pacchetti sulla rete

● Algoritmi Direct Diffusion e GEAR ● Caching delle informazione nei nodi intermedi

10/19

Direct Diffusion with GEAR(1)● Alcuni sensori [Subscrivers] iniziano la ricerca e come prima cosa inviano

un messaggio beacon ai vicini per conoscere, in seguito ad un beacon-replay, la loro posizione ed il loro livello di batteria residuo

● Sucessivamente l’AppLayer dei Subscrivers genera un messaggio interests, che contiene tutte le informazioni necessario riguardanti la query che si intende propagare (regione target, tasso di campionamento, tipo di dato da rilevare), e lo inoltra nella rete

● L’inoltro di questo messaggio viene fatto in modo intelligente tramite l’algoritmo di routing GEAR, che verrà illustrato a breve.

● Quando il pacchetto interest raggiunge un sensore della regione target [Publisher], quest’ultimo manda indietro (seguendo il medesimo path di andata) un messaggio di tipo Exploratory

11/19

Direct Diffusion with GEAR(2)● Quando il Subscriver vede arrivarsi un pacchetto di tipo Exploratory si

preoccupa di mandare un massaggio di tipo Reinforcement verso il Publisher● Quest’ultimo tipo di pacchetto serve a notificare su quale path il target deve

ritornare i dati campionati, con il rate indicato nella query● Questi percorsi di costo minore

possono variare in base all’evolversi della rete (sensori attivi,disattivi, livelli di batteria...)

● Necessità di aggiornare le tabelle dei sensori vicini periodicamente

12/19

Algoritmo GEAR(1)● L’obbiettivo dell’algortimo è quello di trovare il prossimo hop

nella rete di sensori che minimizzi il costo per raggiungere la regione target, tenendo in considerazione il livello di batteria dei sensori

● Prerequisiti:○ ogni sensore conosce la propria posizione e quella dei vicini○ ogni sensore conosce il proprio livello di batteria residua e

quello dei vicini○ range di propagazione di un pacchetti è limitato ai nodi vicini

13/19

Algoritmo GEAR(2)● Il nodo N vuole inoltrare la query alla regione target T● Il nodo N inoltra il pacchetto al nodo vicino Ni che minimizza il

costo per arrivare a T, rispetto a tutti gli altri vicini : h(Ni, T) ● Se non si ha questa misura il sensore N fa una stima del costo:

c(Ni,T) = α*d(Ni, T) + (1 - α)*e(Ni)dove α è un parametro che indica il peso che si vuol dare al percorso minimo, rispetto al peso dell’energia residua sul sensore e(Ni) è l’energia stimata, d(Ni, T) percorso stimato tra Ni e target T

14/19

Algoritmo GEAR(3)● Quando un pacchetto di interest arriva su un sensore N vi possono

essere due situazioni differenti:○ almeno un sensore vicino Ni è più vicino a T○ tutti i sensori vicini Ni sono più lontani a T, rispetto ad N(hole)

● Nel primo caso, si segue un approccio greedy e si sceglie il nodo più vicino alla destinazione (sempre bilanciando con la batteria)

● Nel secondo caso, Ni segnala ad N di essere un hole. N di conseguenza aggiorna la tabella dei vicini, rivede le stime e intraprende un percorso di routing differente

15/19

Algoritmo GEAR(4) - RGF● Quando un sensore rileva di essere all’interno della

regione target si utilizza il Recursive Geographic Forwarding

● Flooding totale, anche se all’interno di una medesima regione, risulta inefficiente

● L’algoritmo divide in sottoregioni in cui fare il flooding, finchè una sottoregione ha al suo interno un unico sensore, così facendo la ridondanza viene quanto meno limitata

16/19

Risultati NS2 vs OMNeT++ (1)

17/19

● Number of Queries: 100 ● Network Dimension: Varies

with the number of nodes● Number of Nodes in

Region: 15 ● Simulation Time: 250s

Notes: NS2 out of memory con nodi >> 2000

Risultati NS2 vs OMNeT++ (2)

18/19

● Number of Queries: 10● Network Dimension: Varies

with the number of nodes● Number of Nodes in

Region: 5● Simulation Time: 300s

Notes: NS2 out of memory con nodi >> 2000

Bibliografia● C. Intanagonwiwat, R. Govindan, D. Estrin, J. Heidemann, and F. Silva. “Directed Diffusion for Wireless

Sensor Networking”. IEEE/ACM Transactions on Networking, 11(1):2–16, February 2003.

● Y. Yu, R. Govindan, and D. Estrin. “Geographial and energy aware routing: A recursive data dissemination protocol for wireless sensor networks”. August 2001.

● C. Mallanda, A. Suri, V. Kunchakarra, S.S. Iyengar*,R. Kannan* and A. Durresi. “Simulating Wireless Sensor Networks with OMNeT++”.The University of Akron, Ohio, 2005

● Almargni Ezreik, Abdalla Gheryani. “Design and Simulation of Wireless Network using NS-2”.2nd International Conference on Computer Science and Information Technology , Singapore, April 28-29, 2012.

● A.S.Tanenbaum, “Reti di calcolatori”. 4th Edition, 2003.

19/19