Energy efficient localization techniques for WSN communications

This research considers energy efficient algorithms in the context of Wireless Sensor Network (WSN) localization. In this dissertation, the term localization refers to the concepts of static localization or fingerprinting for a single shot estimation of a target position and tracking of target positions over different time instants. Considered localization scenarios cover both active and passive localization. In active localization, the target participates in the estimation process of inter-node ranging information while in passive scenarios the target does not participate in the estimation process. The general trend in the design of localization algorithms is towards achieving more accurate position estimate. Additionally, algorithms should respect energy efficiency constraints due to the limited battery life in WSN nodes. The contribution of this thesis mainly focuses on the investigation and the proposal of localization algorithms which should achieve these two crucial design objectives: -accuracy improvement; -energy efficiency. As already mentioned, according to these design objectives the thesis considers algorithms which exploit both active and passive localization scenarios. The first section of the thesis deals with the investigation of energy efficient localization algorithms in which passive localization plays a crucial role. The first part developed for passive scenarios is devoted to the theoretical analysis of a hybrid tracking algorithm composed of active and passive steps. The analysis of this scheme, based on the Posterior Cramer Rao Bound (PCRB), confirms that mixing active and passive cases can be an effective tool towards energy efficiency. The second part of the investigation related to passive scenarios deals with the energy efficiency issue inspired by two perspectives. A hybrid tracking algorithm composed of Extended Kalman Filter (EKF) based tracking and Fingerprinting (FP) is proposed in order to tackle conventional problems related to the implementation of either tracking or fingerprinting separately. One of the common drawbacks of FP is the large data size and the consequent large search space as a result of either vastness of surveillance area or finer grid resolution in FP grid map; this usually limits the application of FP to small environments or scenarios with largely spaced grid points, leading to poor localization performance. The hybrid algorithm developed here enables FP to be applied in larger environments or environments with finer space grids. The second aspect of the scheme deals with the critical concern related to tracking more than one passive target. When targets move close to each other, the correct discrimination among measures, resulting from occurred ambiguity in paths clusters scattered by different targets, turns out to be a challenging task. The final phase of this analysis is devoted to considering a TOA-based ranging technique called soft ranging and its potential characteristics for providing more accurate ranging measures by means of feeding a kind of a-priori information. This solution provides EKF update steps with more precise ranging measures leading to a better localization performance. Simulation results validate a zero-energy tracking algorithm in which the mobile target does not consume energy. The second section of the thesis deals with energy efficient algorithms for active localization scenarios. Accordingly, transmit power allocation among the beacons (i.e. the reference points for the localization) is an effective tool toward this objective. In the section we present a pervasive literature review on existing Power Allocation (PA) schemes and, in particular, of the optimal ones, based on the minimization of a localization error bound (SPEB), function of the transmission power from each beacon. Then, two new sub-optimal algorithms are investigated. The former is based on the definition of a parameter called uncertainty area, which is a convex function of transmission power in the pair-wise selection of beacons. Numerical results confirm a notable performance advantage of localization with PA schemes w.r.t to the case of uniform power allocation among beacons especially in target locations in the vicinity of beacons. The latter proposed algorithm is based on the fact that the optimal SPEB based PA approach does not show any advantage when performance (i.e. Mean Square Error (MSE)) of the ranging estimator achieves a floor corresponding to a certain threshold in the received Signal to Noise Ratio (SNR). This corresponds to the behaviour of a practical ranging estimator where achieving higher ranging accuracy is not possible by increasing transmission power over a certain threshold because of phenomena like the limits imposed by the maximum sampling rate and by the computational load available in sensors. Consequently, this sub-optimal, simplified PA algorithm is based on the distribution of transmit powers of beacons with the SNR above the threshold to beacons with the SNR below the threshold, realizing a type of simple Adaptive Power Allocation (APA) directly based on the measured SNRs. Simulation results confirm that such a simple strategy can be effective in medium-low SNR regions, even w.r.t. more sophisticated optimization procedures.

Questa ricerca si è focalizzata sullo studio di algoritmi per la localizzazione efficienti sotto il profilo energetico. Nella tesi il termine localizzazione si riferisce ai concetti di localizzazione statica, effettuata punto per punto o di tracciamento ("tracking") della posizione effettuato su obiettivi mobili in differenti istanti di tempo. Gli scenari di applicazione considerati includono sia la localizzazione attiva che quella passiva: nella localizzazione attiva, l'obiettivo ("target") partecipa al processo di stima delle informazioni di distanza inter-nodo ("ranging") mentre nel caso passivo non partecipa al processo di stima. La tendenza generale nel progetto di algoritmi di localizzazione è quella di raggiungere stime di posizione sempre più accurate. In aggiunta, gli algoritmi dovrebbero rispettare limiti relativi all'efficienza energetica, giustificati dalla limitata vita delle batterie nei nodi di una rete radio di sensori (WSN). Il contributo di questa tesi è principalmente focalizzato sullo studio e la proposta di algoritmi di localizzazione che dovrebbero raggiungere i due seguenti obiettivi cruciali: - miglioramento delle prestazioni; - efficienza energetica. Come già menzionato, in questo ambito la tesi considera algoritmi per scenari di applicazione sia attivi che passivi. La prima sezione della tesi riguarda lo studio di algoritmi efficienti sotto il profilo energetico per la localizzazione passiva. La prima parte è dedicata all'analisi teorica di un algoritmo per il tracciamento ibrido, composto da passaggi di informazione in parte attivi e in parte passivi. L'analisi di questo schema, basato sul PCRB, conferma che bilanciare passaggi attivi e passivi può essere uno strumento efficace per aumentare l'efficienza energetica complessiva del procedimento. La seconda parte dello studio relativo agli scenari passivi riguarda il problema dell'efficienza energetica sotto una duplice prospettiva. Un algoritmo di tracciamento ibrido composto da EKF e FP è proposto per contrastare problemi comuni relativi all'implementazione separata delle tecniche basate su filtri EKF e fingerprinting. Ad esempio uno dei problemi comuni della tecnica FP è relativo alla grande dimensione dei dati e al conseguente grande spazio di ricerca come risultato sia della vastità dell'area di monitoraggio che della risoluzione fine nella mappa FP (che porta all'applicazione di FP ad ambienti piccoli o più ampi ma con prestazioni di localizzazione minori). L'algoritmo presentato permette l'applicazione di FP in ambienti più ampi con griglie e mappature più fini. Il secondo aspetto dello schema ha a che fare con i casi più critici nei problemi di tracciamento, costituiti dalla presenza di più di un obiettivo passivo. Quando questi oggetti o dispositivi, operanti in modalità passiva, si vengono a trovare in posizioni vicine, la discriminazione corretta tra le misure, associate ai segnali riflessi e ai relativi oggetti, risulta un compito estremamente difficoltoso. La parte finale di questa analisi è dedicata alle tecniche di "ranging" denominate "soft" e alle loro potenzialità nelle prestazioni quando sono disponibili varie modalità di informazioni a priori. I risultati delle simulazioni permettono di validare un algoritmo di tracciamento a consumo nullo, nel quale il "target" non consuma energia. La seconda sezione della tesi riguarda gli scenari di applicazione della localizzazione attiva. In questo contesto, l'allocazione della potenza tra i punti di riferimento ("beacon") è uno strumento efficace per raggiungere tale obiettivo. Nella sezione presentiamo un'estesa revisione della letteratura sugli schemi esistenti di PA e, in particolare, su quelli ottimi, basati sulla minimizzazione dell'errore di localizzazione (tramite una sua misura, detta SPEB), che è anche funzione della potenza in trasmissione da ogni beacon. In aggiunta, due nuovi algoritmi sub-ottimi sono stati analizzati. Il primo è basato su un parametro che è stato chiamato regione di incertezza e che risulta una funzione convessa della potenza di trasmissione nel caso di una coppia di beacon. I risultati numerici confermano un considerevole vantaggio di prestazioni negli schemi con PA rispetto al caso con allocazione uniforme della potenza, in particolare per le posizioni degli obiettivi nelle vicinanze dei "beacon". Il secondo algoritmo proposto è basato sul fatto che l'approccio basato sull'allocazione di potenza per l'ottimizzazione dello SPEB non mostra vantaggi quando le prestazioni dello stimatore di ranging raggiungono un errore minimo non migliorabile al di sopra di un certo limite di SNR (regione di "floor"). Questa situazione corresponde al comportamento di uno stimatore di ranging reale, in cui migliorare l'accuratezza della misura non è possibile incrementando la potenza di trasmissione sopra certe soglie a causa di fenomeni come la massima frequenza di campionamento o il carico computazionale nei sensori. Di conseguenza questo algoritmo sub-ottimo e semplificato è basato sulla distribuzione delle potenze di trasmissione ai beacon con rapporto segnale rumore superiore alle soglie a quelli con SNR inferiore, realizzando una sorta di allocazione adattativa di potenza. Le simulazioni confermano che questa semplice strategia può essere efficace nelle regioni di SNR medio-bassi, anche rispetto alle tecniche di ottimizazione più efficaci.