Radio localization of mobile terminals in wireless networks

Introduction

Accurate location in radio systems has received great attention over the last years. Without exploiting satellite-aided positioning systems (e.g., by Global Positioning System), several radio positioning techniques have been proposed by exploiting only local radio measurements while transmitting. These techniques are based on one or more measurements types such as angle (AOA - Angle of Arrival), time (TOA - Time Of Arrival) or time difference (TDOA - Time Difference of Arrival) of arrivals and power profiles (RSS - Received Signal Strength).

The basic concept of localization of a terminal relies on the trilateration from a set of fixed anchor points. For example, in the case of angular measurements, it is sufficient to know L=2 directions, while for ranging a minimum of L=3 known distances is needed. However in a more complex network-aided radio localization scenario these angular or distances values are not directly measurable, but have to be estimated from a wider set of observed data; typically, those data consist in the raw radio signals exchanged between the base anchors (also called Access Points, AP) and the mobile terminal (MT). In real systems false localizations occur due to measurement impairment, calibration errors, multipath effects, inaccurate delay/distance estimations, etc. Thus, a set of L>3 measurements must be used.

Figure 1. Basic TOA and AOA positioning

In the next generation indoor wide-band mobile systems, such as Ultra Wide Band (UWB), the radio localization based on time or/and angle based methods (TOA, TDOA and AOA) is not feasible due to the dense multipath characteristics. Moreover, the local positioning problem is worsened by non-line-of-sight (NLOS) conditions due to signal blocking. In NLOS conditions the first arrivals can be heavily softened, so a strong bias in delay estimation is introduced.

Figure 2: a) LOS condition: the direct path carries the strongest arrival; b) NLOS condition: direct path is heavily blocked by some obstacles, so the first arrival comes from multipaths.

Formalization of the dynamic system

In order to reduce this bias and alleviate the dense multipath effects, we propose to exploit both locality of the MT position and LOS/NLOS conditions for all the MT/AP links by using a HMM (Hidden Markov Model) framework. A set of target tracking algorithms founded on the HMM Bayesian concept is also developed in order to track the MT motion and the change of sight condition on the L radio links. The first exploited method is D/TA (Detection Tracking Algorithm), which was originally developed for TOA tracking in remote sensing applications [Spagnolini-Rampa, 1999] [Nicoli-Rampa-Spagnolini, 2002]. Next, we propose a Particle Filtering (or Sequential MonteCarlo) approach, whose task is to minimize the computational complexity of the D/TA solution. The bayesian concept of Particle Filtering has been a focus topic in signal processing for many years and has been developed for a very extended range of possible applications. Both methods are forward-only algorithms so that real-time estimates can be directly achieved.

Through the use of HMM concept, the hidden state of our dynamic system is characterized by the MT position and by its LOS/NLOS conditions across the radio cell, both modelled as homogeneous first-order Markov chains. D/TA relies on the maximization of an a-posteriori probability of the joint position-LOS/NLOS state for each MT exploiting all the independent signal measurements (with respect to all APs), available up to the current instant. With respect to other methods, such as the extended Kalman filter (EKF), the DT/A algorithm does not rely on linearization and gaussian assumptions but has about the same computational complexity. Notice that the HMM framework here presented may model either self-positioning or remote location systems. Moreover, it may be employed in different scenarios and only observation probabilities have to be changed accordingly.

Figure 3. The state x_i is composed by the MT position q_i and by the MT/AP sight conditions s_i; transitions in the state space (e.g. the terminal moves) cause abrupt changes on the observed measurement set y_i (raw signals, average powers, etc...).

The computation of state probabilties in the D/TA is carried out on a finite and discrete regular grid of states. However, the complexity of the state space explodes with increasing L, so a more efficient method is found in the PF approach. At first, the state space is partitioned in a location subspace (continous) and in a sight subspace (discrete). Thanks to the Jump Markov System (JMS) technique, the target probability density function is evaluated only on a set of N points ("particles") across the couple of subspaces, using the concept of importance sampling. It is shown how performances of the state estimate are comparable with those of D/TA, even if the number N of particles is much lower than the amount needed by the grid-based algorithm.

Figure 4. HMM sequential filtering of the measure likelihoods: a) D/TA grid-based approach; b) particle filtering scheme.

Examples

The following links provide some examples for the MT tracking in a realistic indoor environment.
The first two movie samples simulate a UWB transmitting infrastructure (AP are plotted as green triangles). A terminal is shown while randomly moving across the permitted spaces (blue dot); the position is estimated in real-time using the basic memory-less Maximum Likelihood estimate (black dot) and the Detection / Tracking Algorithm (red dot).
A comparrison between the two methods is shown in both high NLOS and low NLOS probability (respectively, 80% and 30%)

Movie sample - ML+D/TA comparrison - high NLOS conditions
Movie sample - ML+D/TA comparrison - low NLOS conditions

The next two movie samples show an application to a different scenario, consisting on a MOTES Mica2 wide sensor network (WSN) of 6 AP. Observed measures are scalar RSS indicators. An example of the "cluster" tracking is shown in the following sample:

Movie sample - Cluster tracking in WSN

On the same sampled trajectory, the evolution of particles according to the PF estimate using the Sequential Importance Resampling (SIR) method are shown in the following movie (blue circle: real position; blue cross: estimated position; red crosses: current particles). Notice how the particle set has a quick convergence to the neightborhood of the real MT position, even if the starting condition assumes a uniform distribution across the space:

Movie sample - PF particle evolution

More examples will be made available further.

(Important: the movie samples are saved using the Intel Indeo 5.10 codec; to download, right-click the link and select "Save target as...").

Aknowledgements

The works here presented have been developed within the Virtual Immersive Communication (FIRB-VICom) Project, supported by the Italian Ministry of Education, University and Research. Details on the project tasks and on the partners involved are presented on the VICom website.

Measurement acquisition by Motes was carried out in cooperation with the Information Processing Systems group's staff.

Spagnolini U., Rampa V., Multitarget Detection / Tracking for monostatic Ground Penetrating Radar: application to pavement profiling, IEEE Transactions on Geoscience and Remote Sensing, vol 37, N. 1, pp. 383-394, Jan. 1999.
Nicoli M., Rampa V., Spagnolini U., Hidden Markov Models for multidimensional wavefront tracking, Geoscience and Remote Sensing, IEEE Transactions on Geoscience and Remote Sensing, vol. 40, N. 3, pp. 651 - 662, March 2002. (pdf)
Morelli C., Nicoli M., Rampa V., Spagnolini U., Hidden Markov Models for radio localization of moving terminals in LOS/NLOS conditions, Proc. IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP’05), vol. 4, pp. 877-880, 18-23 march 2005. (pdf)
Nicoli M., Morelli C., Rampa V., Spagnolini U., HMM-based tracking of moving terminals in dense multipath indoor environments, Proc. 13th European Signal Processing Conference (EUSIPCO '05), Antaya, September 2005. (pdf)
Morelli C., Nicoli M., Rampa V., Spagnolini U., Hidden Markov Models for radio localization in mixed LOS/NLOS conditions, IEEE Transactions on Signal Processing, Vol. 55,No. 4, pp. 1525-1542, April 2007. (pdf)
Morelli C., Nicoli M., Rampa V., Spagnolini U., Alippi C., Particle filters for RSS-based localization in wireless sensor networks: An experimental study, IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP’06), Toulouse, 14-19 Maggio 2006. (pdf)
M. Nicoli, C. Morelli, V. Rampa, “A jump Markov particle filter for localization of moving terminals in dense multipath indoor scenarios,” submitted.

Updated: October 2007