A Novel Spatial Fluid Approach to Analyze
Large-Scale Wireless Sensor Networks
M. Gribaudo[1]
C.-F. Chiasserini[2]
R. Gaeta[1]
M. Garetto[2]
D. Manini[1]
M. Sereno[1]
[1]
[2]
Università di Torino
Politecnico di Torino
Progetto Pattern --- Firenze 12/10/2004
1
Reti di Sensori: valutazione delle
prestazioni
• Lo studio del comportamento di reti di sensori può
essere estremamente complesso
• Simulazione
• Sperimentazioni sul campo
• Le difficoltà nascono da:
• Dimensioni (numero di sensori)
• Comportamenti complessi
• Interferenza per accesso al canale wireless
• Problemi legati al routing
• Considerazioni energetiche
• In questo studio viene proposto un modello analitico di
una rete di sensori basato su un approccio fluido
Progetto Pattern --- Firenze 12/10/2004
2
Modello fluido di una rete di sensori
• Il modello è in grado di descrivere in modo
soddisfacente i comportamenti tipici di tali sistemi
• Comportamento dei sensori
• Strategie di routing
• Strategie di controllo della congestione
• L’approccio fluido permette lo studio di reti di sensori
di grandi dimensioni (con tempi per la soluzione del
modello limitati)
• Il modello permette sia lo studio in regime stazionario
che in regime transiente
• Possibilità di studiare comportamenti dinamici (es.
strategie di routing che cambiano nel tempo)
Progetto Pattern --- Firenze 12/10/2004
3
Assunzioni (I)
• Rete di N sensori distribuiti su un area circolare di
raggio unitario
• Presenta di un nodo sink
• I sensori hanno un raggio di trasmissione pari a d
• Ogni sensore genera pacchetti di dimensione costante
che possono essere in un buffer di capacità infinita
• L’energia consumata da un sensore i per trasmettere
un pacchetto al sensore j è
E(tx)= E(ele)+ E(proc)+dist(i,j)2 E(amp)
E(ele) consumo dovuto alla parte elettronica
E(proc) consumo dovuto a funzioni di processing
dist(i,j)2 E(amp) consumo dovuto a spedizione ad i a j
• L’energia consumata da un sensore j per ricevere un
pacchetto è
E(rx)= E(ele)+ E(proc)
Progetto Pattern --- Firenze 12/10/2004
4
Assunzioni (II)
• Per spedire i dati i sensori usano
comunicazioni multihop
• Il percorso scelto è quello lo shortest path
che minimizza il consumo di energia
• Algoritmo di Dijkstra
• Costo C(i,j) su ogni arco da i a j (con dist(i,j)<d)
C(i,j)= Ch + Cd dist(i,j)2
Ch = 2 (E(ele)+ E(proc))
Progetto Pattern --- Firenze 12/10/2004
5
Il Modello (I)
• L’approccio modellistico utilizzato è basato
sull’osservazione che in reti di grandi dimensioni i
sensori possono essere rappresentati mediante delle
grandezze continue
Ogni punto del piano è identificato dalle sue coordinate
r=(x,y)
r (r) è la densità (numero di sensori per unità di area al
punto r) e può essere misurata in sensori al metro
quadro
Progetto Pattern --- Firenze 12/10/2004
6
Il Modello (II)
• I sensori possono essere distribuiti in modo uniforme
oppure in modo non-uniforme
• Un sensore s in posizione r genera un traffico di
pacchetti con un tasso ls(r)
• Aggregando tutto il traffico generato dai sensori in
una piccola area nell’intorno del punto r, possiamo
definire un tasso di generazione l(r) = ls(r) r(r)
(misurato in pacchetti al secondo per unità di
superficie)
Progetto Pattern --- Firenze 12/10/2004
7
L’algoritmo di routing
• Ogni sensore ha come vicini diversi sensori
che possono essere utilizzati come relay
•non tutti I vicini possono essere usati come
relay (comportamenti di tipo on-off,
interferenza)
• Definizione probabilistica di next hop
u(r,r’) è la probabilità che un pacchetto
generato da un sensore in posizione r utilizza
come next hop il sensore in posizione r’
Progetto Pattern --- Firenze 12/10/2004
8
Traffico Totale
• Ogni sensore agisce sia come sorgente di
pacchetti che come relay
L(r) è il total traffic rate definito come la
somma del traffico generato localmentre dai
sensori al punto r e del traffico di relay
• Questa equatione può essere risolta mediante
discretizzazione spaziale (in questo modo il
sistema di equazioni integrali si riduce ad un
sistema di equazioni lineari)
Progetto Pattern --- Firenze 12/10/2004
9
Interferenza
• Il traffico di interferenza I(r) è il traffico
totale trasmesso nelle “vicinanze” del punto r
che impedisce ai sensori che sono in r di
trasmettere con successo
• Î(r,r’) è l’interference factor, la frazione del
traffico al punto r’ che interferisce con la
trasmissione di sensori localizzati in r
Progetto Pattern --- Firenze 12/10/2004
10
Consumo di Energia
• P(r) rappresenta il consumo di energia (per unità
di tempo) dei sensori in r
• Pi(r) rappresenta il consumo di energia dei
sensori in r mentre sono nello stato idle
• E(tx)(r,r’) è l’energia consumata per trasmettere
un pacchetto dal punto r al punto r’
• E(rx)(r’’,r) è l’energia consumata per ricevere un
pacchetto che arriva da r’’ a r
Progetto Pattern --- Firenze 12/10/2004
11
Tempo medio di attesa e numero
medio di hop
• w(r) = mean wating time
• h(r) = numero medio di hop
• q(r) = tempo medio di servizio (queueing delay +
transmission time)
Progetto Pattern --- Firenze 12/10/2004
12
Analisi in regime transiente
• C(r,t) = carica totale dei sensori al punto r al
tempo t
• C0(r) = carica iniziale
Progetto Pattern --- Firenze 12/10/2004
13
Risultati Numerici (I)
Progetto Pattern --- Firenze 12/10/2004
14
Risultati Numerici (II)
Progetto Pattern --- Firenze 12/10/2004
15
Risultati Numerici (III)
Progetto Pattern --- Firenze 12/10/2004
16