Go to the content. | Move to the navigation | Go to the site search | Go to the menu | Contacts | Accessibility

| Create Account

Zorzi, Francesco (2010) Localization and network management in radio and underwater networks. [Ph.D. thesis]

Full text disponibile come:

PDF Document

Abstract (english)

Wireless Sensor Networks (WSNs) have been widely studied in the last decade because of the large set of applications that can be potentially enabled by this novel network paradigm, as environmental monitoring, home automation, localization and tracking of mobile users, seamless and ubiquitous data exchange. However, the severe constraints in terms of energy, processing, memory and reliability of the low--cost sensor devices left a number of unresolved problems, open to research.

This thesis tackles two of the most interesting problems concerning WSNs, namely localization and traffic management.

Accurate sensor localization is crucial for a wide variety of WSN applications and protocols, including monitoring, routing, scheduling, data fusion and so on.

Typically, localization algorithms are based on an infrastructure of nodes which are aware of their geographical positions, called beacons. These nodes broadcast their coordinates in order to let the other nodes in the network, referred to as stray nodes, infer their own position by means of some estimation technique.
The topic has been widely investigated, both in simulation and, more recently, in experimental testbeds. Nonetheless, the performance obtained by most of the proposed algorithms is still unsatisfactory, in particular in indoor environments. Therefore, further research is needed.

In this thesis, the problem has been tackled from different perspectives, in order to gain a deep and clear understanding of the several facets that characterize this interesting domain. As a consequence, we collected a rather wide set of results that apparently may not seem to be strongly correlated, though they all fit within the same research project.

As a first step, we compare well known localization algorithms in indoor environments for static networks, based on a Received Signal Strength Indicator (RSSI) ranging estimation technique. Results shed light on the actual potentialities and limits of common localization algorithms in indoor environments in a real testbed. In particular, we observed the strong impact of the shadowing random attenuation of the power of the received signal on the performance of the localization algorithms. Therefore, research has been addressed to the reduction of the shadowing term in the RSSI measures. To this end, we investigated the effect of the carrier frequency and of the antenna anisotropy on the randomness of the shadowing component, again using real measurements collected in different testbeds.

Successively, our attention turned to the problem of beacon positioning that we observed may strongly affect the localization performance. We analyzed the optimal beacons placement both using an exhaustive but very complex approach and a heuristic scheme that provides close to optimal solutions while maintaining a linear complexity with the number of beacons.

Looking at the localization performance separating the different effects of localization algorithms, channel parameters and beacon positioning, has been important to understand the contribution of each one of these aspects to the localization error and how much is it possible to improve the localization accuracy by means of a single technique, that usually is chosen depending on the particular scenario and available resources.

Then nodes mobility has been included into the framework.

We first considered an Autonomous Mobile Robot (AMR) that can interact with sensors, but is also capable to self--localize using onboard odometry. Leveraging on the complementarities of WSN and AMR, we considered the Simultaneous Localization and Mapping (SLAM) problem that consists in creating the map of an area without any a priori knowledge of the environment, while localizing the nodes in the WSN by combining the information provided by the WSN and by the AMR odometry.

Second, we considered a completely mobile wireless networks in which heterogeneous nodes with different self--localization capabilities can interact one another on an opportunistic basis, exchanging localization information with other nodes that occasionally happen to be in geographical proximity. The performance of this scheme has been analyzed through a mathematical framework. We considered a Maximum Likelihood (ML) approach, a Linear Matrix Inequality (LMI) system and a simple heuristic strategy to define opportunistic localization algorithms. The validity of the mathematical model has been confirmed through experimental measures. We considered two main settings, one in which a node can rely on a single opportunistic interaction and one in which multiple contacts can be set while the node remains in the same position. We analyzed the different techniques, finding that in the first scenario, if the channel is not very noisy and the self--localization of the cooperative node quite accurate, the heuristic algorithm performs very well, in some case slightly better than ML, while the ML approach is very robust and improves localization accuracy even in difficult scenarios. If multiple interactions are available, then the heuristic technique is quite poor and it is better to rely on the LMI technique. Moreover LMI is quite flexible, because it does not require an initial guess of the position by the stray node and it can be used both with and without ranging information.

The static scenario analysis was very useful to focus on the mobile localization. The design of the proposed algorithms and scenarios, the simulation parameters and limits, are strictly related to the knowledge of the channel behavior and localization performance gained from the previous studies. The opportunistic idea raises from two main considerations: the limited accuracy of the beacon based RSSI localization in a real scenario and the quite good ranging accuracy of RSSI when limiting the distance.

Alongside the main research line concerning localization in WSN, during the Ph.D. we also investigated other research topics, namely traffic management and underwater sensor network, which are not directly related to the previous ones but still of great scientific and educational interest. The most significant achievements obtained in these areas have also been collected in the thesis for two reasons. First, these topics still belong to the context of wireless sensor networks, sharing some basic characteristics such as the assumptions of simplicity and energy constraints. Second, the excursion on different but correlated fields may potentially open new perspectives to well known problems, thus contributing to the innovation and the progress of the research.

As mentioned, the second problem addressed in this thesis regards the traffic management in WSN. Usually all the nodes in a WSN send packets to a common node, called sink. This traffic pattern, under a certain load, can lead to congestion problems, causing packet losses, high delays and waste of energy. The proposed solutions in literature usually aim at detecting the occurence of congestion by involving in this task many nodes, sometimes the entire network. We propose a different protocol, called Efficient Packet Converge Casting (EPC$^2$), that mitigates the congestion at the sink involving only a fixed number of nodes, namely the sink's neighbors.

Another scenario we look into was that of underwater wireless sensor networks (UWSNs), which enable a number of applications as for radio WSNs, fostering interest in this research field.

Similarly to radio networks, the energy efficiency remains a main issue. Nodes are powered by battery and it is very important to extend the network lifetime as much as possible.
The different characteristics of the environment in which nodes are deployed raise new research challenges that require novel protocol design.

We addressed the energy efficiency problem in UWSN with two different approaches.

First, we investigated the effect of duty--cycle and node density on the energy consumption of the network, assuming that nodes can use different power levels to transmit. Second, we proposed a channel management scheme to optimize the energy consumption, considering the strong relationship between distance, frequency and channel attenuation.
Both solutions are very simple and suitable for the low--complexity underwater sensor devices and do not need any central unit to coordinate, but they work asyncronously and distributely.

Abstract (italian)

Negli ultimi anni, le reti wireless di sensori (WSN) sono state molto studiate a causa delle numerose applicazioni in cui possono essere usate, come il monitoraggio ambientale, la domotica, la localizzazione e il tracking di utenti mobili.
Le forti limitazioni dei nodi sensori in termini di energia, processamento, memoria e affidabilita', lasciano ancora aperti molti problemi per la ricerca.

Questa tesi affronta due problemi molto importanti relativi alle reti wireless di sensori: la localizzazione e la gestione del traffico.

Un'accurata localizzazione dei sensori e' importante per molte applicazioni per WSN, come monitoraggio, routing, scheduling, data fusion e molte altre.

Tipicamente, gli algoritmi di localizzazione si basano su una infrastruttra di nodi, detti nodi ancora che conoscono la loro posizione geografica. Questi nodi trasmettono in broadcast le loro coordinate agli altri nodi della rete, che da queste informazioni ricavano la loro posizione tramite tecniche di stima.
L'argomento e' stato largamente studiato, sia con simulazioni sia, piu' recentemente, con testbed sperimentali. Ciononostante, l'accuratezza ottenuta dalla maggior parte degli algoritmi proposti e' ancora insufficiente, soprattutto in ambienti interni. E' quindi necessario cercare nuove metodologie e nuovi approcci.

In questa tesi, il problema e' stato affrontato da diversi punti di vista, in modo da capire in maniera piu' chiara e accurata i diversi aspetti che lo caratterizzano. Come conseguenza, abbiamo raccolto una vasta quantita' di dati che potrebbero apparire come non molto legati uno all'altro, ma che in realta' rientrano tutti nello stesso progetto di ricerca.

Come primo passo, abbiamo confrontato algoritmi di localizzazione proposti in letteratura in uno scenario indoor e con nodi statici, stimando la distanza tra i nodi utilizzando la potenza del segnale ricevuto (RSSI). I risultati ci hanno permesso di capire le potenzialita' e i limiti dei piu' diffusi algoritmi di localizzazione in ambiente indoor e in un testbed reale. In particolare, abbiamo osservato il grande impatto che ha sulle prestazioni di localizzazione l'aleatorieta', data dal termine di shadowing, della misura di potenza ricevuta. Abbiamo quindi cercato delle strategie per ridurre la varianza di questo termine aleatorio. A questo scopo, abbiamo studiato l'effetto della frequenza della portante, utilizzando una stima della potenza ricevuta multi--canale, e l'impatto dell'anisotropia dell'antenna sulle oscillazioni dei valori di potenza ricevuta. Entrambi glil studi sono stati fatti con misure reali raccolte in diversi testbed.

Successivamente, abbiamo analizzato il problema del posizionamento dei nodi ancora, dopo aver osservato l'incidenza che questo ha sull'accuratezza della localizzazione. Abbiamo confrontato il posizionamento ottimo dei nodi ancora usando sia una tecnica esaustiva, ma computazionalmente molto complessa, sia uno schema euristico che raggiunge prestazioni molto vicine all'ottimo pur mantenendo una complessita' lineare con il numero di ancore.

Guardare alle prestazioni di localizzazione separando i diversi effetti degli algoritmi, dei parametri di canale e del posizionamento dei nodi ancora e' stato importante per capire il contributo dei diversi aspetti all'interno dell'errore di localizzazione e quanto sia possibile migliorare la precisione della localizzazione ottimizzando uno di questi aspetti, che solitamente viene scelto in base allo scenario e alle risorse disponibili.

Quindi, abbiamo incluso nel nostro scenario anche nodi mobili.

All'inizio abbiamo considerato un robot mobile (AMR) che poteva interagire con i sensori, ma anche capace di localizzarsi grazie all'odometria. Facendo leva sulla complementarieta' della rete di sensori e del robot mobile, abbiamo studiato e implementato un algoritmo di localizzazione e mappatura simultanea (SLAM), problema che consiste nel creare la mappa di un'area senza nessuna conoscenza a priori dell'ambiente e in contemporanea localizzare i nodi sensore confrontando le informazioni provenienti dai sensori e quelle ricavate dall'odometria del robot.

Poi abbiamo considerato uno scenario piu' generale composto da nodi mobili ed eterogenei, con diverse capacita' di autolocalizzazione, che possono interagire uno con l'altro in modo opportunistico, scambiandosi informazioni di localizzazione con altri nodi che occasionalmente si trovano in prossimita'. Le prestazioni di questo schema sono state analizzate in un modello matematico. Abbiamo studiato un approccio a Massima Verosimiglianza (ML), uno basato su Linear Matrix Inequalities (LMI) e una semplice strategia euristica per definire gli algoritmi di localizzazione opportunistica.
La validita' del modello matematico e' stata confermata attraverso misure sperimentali. Abbiamo considerato due scenari principali, uno in cui un nodo puo' contare su una sola interazione opportunistica e uno dove possono essere fatti contatti multipli mentre il nodo resta nella stessa posizione.
Abbiamo analizzato le diverse tecniche, trovando che nel primo caso, se le informazioni di autolocalizzazione del nodo cooperatore e di ranging sono buone, l'algoritmo euristico ha buone prestazioni, a volte addirittura meglio della Massima Verosimiglianza, che invece e' estremamente robusto e riesce a migliorare la stima di localizzazione anche in scenari molto difficili. Se invece sono disponibili numerose interazioni, allora l'algoritmo euristico porta prestazioni scarse ed e' meglio utilizzare la tecnica LMI, specialmente utilizzando l'informazione di ranging. Inoltre l'LMI non richiede una conoscenza della posizione iniziale del nodo incognito.

Lo scenario statico e' stato molto utile per studiare in maniera efficace la localizzazione mobile. La scelta degli algoritmi proposti e dello scenario, i parametri di simulazione e i limiti, sono strettamente legati a quello che abbiamo studiato riguardo al canale wireless e alle prestazioni di localizzazione nei lavori precedenti. L'idea dello scenario opportunistico infatti e' venuta a partire da due considerazioni: la limitata precisione della localizzazione con ancore basata su RSSI in uno scenario reale e la buona precisione nella stima di distanza con RSSI quando la distanza e' limitata.

Affianco al principale filone di ricerca riguardante la localizzazione nelle WSN, durante il dottorato di ricerca abbiamo approfondito anche altri argomenti, come la gestione del traffico e le reti di sensori sottomarine, che non sono direttamente collegate con il tema principale, ma sono comunque di grande interesse scientifico. I risultati piu' significativi ottenuti in questi temi sono stati inseriti all'interno della tesi per due motivi. Innanzitutto, questi argomenti appartengono al contesto delle reti di sensori wireless, condividendo alcune caratteristiche di base quali l'assunzione di semplicita' e le limitazioni energetiche. Inoltre, il trattare campi diversi ma correlati, puo' aprire nuove prospettive a problemi noti, contribuendo cosi' all'innovazione della ricerca.

Il secondo problema affrontato in questa tesi e' stato la gestione del traffico in reti di sensori wireless. Spesso, i nodi di una rete di sensori mandano i pacchetti ad un nodo comune, chiamato sink. Questo modello di traffico, quando il carico cresce, puo' portare a problemi di congestione, causando perdita di pacchetti, ritardi e spreco di energia. Le soluzioni proposte in letteratura solitamente cercando di individuare l'inizio di una congestione, utilizzando in questo compito molti nodi, talvolta l'intera rete. Il protocollo proposto, chiamato Efficient Packet Converge Casting (EPC$^2$), mitiga la congestione al sink, ma coinvolgnedo solo un numero fissato di nodi, i vicini del sink.

Un altro scenario che abbiamo analizzato in questa tesi, sono state le reti sottomarine di sensori che, come nel caso delle reti radio, possono essere utilizzato per molteplici applicazioni e quindi hanno ricevuto molta attenzione dal mondo della ricerca.

Similmente alle reti radio, l'efficienza energetica e' un problema molto sentito. I nodi sono alimentati a batteria ed e' molto importante incrementare la vita della rete il piu' possibile.
La profonda diversita' dell'ambiente in cui i nodi sono disposti crea nuove sfide per la ricerca che richiedono la progettazione di nuovi protocolli.

Abbiamo affrontato il problema dell'efficienza energetica in reti sottomarine con due diversi approcci.

Abbiamo studiato l'effetto del duty--cycle and della densita' dei nodi sul consumo energetico della rete, assumendo che i nodi potessero usare diversi livelli di potenza in trasmissione. Quindi abbiamo proposto uno schema di utilizzazione della banda disponibile per ottimizzare il consumo energetico, facendo leva sulla forte relazione tra distanza, frequenza e attenuazione del canale.
Entrambe le soluzioni sono molto semplici e adatte ai dispositivi sottomarini che hanno forti limitazioni. Inoltre non richiedono una unita' centrale per essere coordinate, ma operano in modo asincrono e distribuito.

Statistiche Download - Aggiungi a RefWorks
EPrint type:Ph.D. thesis
Tutor:Zanella, Andrea
Data di deposito della tesi:UNSPECIFIED
Anno di Pubblicazione:29 January 2010
Key Words:Wireless sensor networks, localization, underwater networks, energy-efficiency, channel measurements
Settori scientifico-disciplinari MIUR:Area 09 - Ingegneria industriale e dell'informazione > ING-INF/03 Telecomunicazioni
Struttura di riferimento:Dipartimenti > Dipartimento di Ingegneria dell'Informazione
Codice ID:2781
Depositato il:21 Sep 2010 12:59
Simple Metadata
Full Metadata
EndNote Format

Download statistics

Solo per lo Staff dell Archivio: Modifica questo record