Bayesian Algorithms for Indoor Radio Localization

by Monica Nicoli and Vittorio Rampa

Localization of moving users or terminals (MTs) is one of the hottest topics in mobile radio/network research and development. User localization may be achieved by satellites (eg using the GPS or the forthcoming GALILEO satellite system) or radio. While in the first case one or more additional devices must be embedded in the user terminal, thus making it more complex and expensive, the latter scenario requires no additional devices since only radio/network services are employed. Radio-assisted localization is the only method suitable in indoor or urban canyon scenarios where satellite signals are not available.

In wireless systems, MT localization is achieved by estimating the radio propagation parameters related to the MT location. These are obtained by exchanging radio signals with N fixed base stations or access points (APs), which are placed in known positions. Typical propagation parameters are: times of arrival (TOA), time differences of arrival (TDOA), angles of arrival (AOA), and received signal strength (RSS). The relationship between these parameters and the MT position can be given either by analytical models or through real field measurements. These measurements are exploited to evaluate the MT-AP distances: this step is called ranging. Localization is then obtained by tri-lateration (ie N=3) using only the minimum number of APs, or by multi-lateration (ie N>3) to increase the method robustness.

The localization steps may be computed by the MT device: this scheme is known as terminal-based localization. No wireless network modifications are required but more complex hardware is needed at the terminal side. In contrast, network-based localization is performed when the localization algorithm is carried out by the radio network itself. Usually this is obtained by using specialized synchronous network access points. This localization scheme is more complex than the previous one and is usually employed in cellular radio systems.

Positioning accuracy is the main benchmark for the localization algorithms. False localizations often arise in ranging methods due to errors in the MT-AP ranging step. These unwanted effects are due to parameter estimation errors, over-simplified assumptions about the propagation environment, multipath effects and non-line-of-sight (NLOS) conditions. In fact, the MT may not be visible from the AP. Moreover, in indoor radio localization scenarios characterized by dense multipath and/or NLOS conditions, these errors become more critical, since ranging leads to apparent or biased distances due to propagation over secondary paths. For these reasons, a localization approach that takes into account mixed LOS/NLOS conditions is mandatory. The most common techniques consist in exploiting redundant measurements (large N), merging different measurement types with data fusion techniques, combining analytical models with maps of measurements, or using Bayesian methods to estimate the whole MT trajectory rather than estimating one position at a time.

In our work, we considered a radio network with N=3 APs covering the area within which the MT must be localized. In principle, accurate ranging could be obtained by estimating the TOA or TDOA from the received signals. However, dense multipath and large delay spreading, often found in indoor environments, strongly reduce the signal resolution during the ranging step. In addition, multiuser access interference (MAI), introduces further signal degradation. In these conditions, the high resolution (ie sampling rate) required by the TOA or TDOA-based methods does not necessarily imply high-resolution ranging results, due to the rich multipath environment that prevents an accurate estimation of the first arrival delay.

Figure 1: Indoor layout used for simulations. Black dotted (solid) lines show NLOS (LOS) conditions between the specified AP and the MT at a given instant in time. Red dots indicate different MT positions (ie MT trajectory).

To improve the localization accuracy, we propose to track the MT position from the RSS-delay profile measurements rather than from the ranging steps. The proposed localization scheme exploits a Bayesian grid-based tracking algorithm. This method estimates the MT location at a given instant by using all the signals measured up to that instant along the MT trajectory over the N links (see Figure 1). It may be the core algorithm for both network-based and terminal-based localization schemes.

The proposed algorithm is the Detection/Tracking Algorithm (D/TA), based on a Hidden Markov Model (HMM). D/TA is a real-time forward-only algorithm that, given all the signals collected up to the current time instant, maximizes the a posteriori probability of the hidden state by using lateral continuity information about the MT trajectory. The HMM state is defined as the set of the MT position and the LOS/NLOS conditions with respect to all the N MT-AP links. Local-only algorithms (eg maximum likelihood estimation - MLE) introduce tracking errors since they do not take into consideration the physical constraints due to the MT trajectory. In contrast, the D/TA algorithm is based on an HMM Bayesian approach that models the MT moving capabilities and the sight conditions. In fact, to reduce tracking errors in mixed LOS/NLOS scenarios, the proposed D/TA algorithm jointly estimates both position and sight conditions of the MT. Finally, the power delay profiles for the signals received over the N radio links are used to track the most likely state sequence. It is worth noticing that this HMM-based approach does not depend on linearization or Gaussian assumptions.

Figure 2: Algorithm RMSE performance comparison. The D/TA algorithm can recover from severe false localization errors introduced by the MLE method and caused by mixed LOS/NLOS conditions (eg in the central alley).

Figure 1 illustrates the network layout used for simulations, while Figure 2 demonstrates how the D/TA method outperforms local-only algorithms like MLE. A faster implementation of the proposed algorithm that uses the Particle Filter approach has been presented. More details are given in the project Web site.

This research activity has been developed within the FIRB Vicom (Virtual Immersive COMmunication) project.

Monica Nicoli
Politecnico di Milano, Italy
E-mail: nicolielet.polimi.it

Vittorio Rampa
IEIIT-CNR, Italy
E-mail: rampaelet.polimi.it

Next issue
April 2018
Next special theme:
Autonomous Vehicles
Call for the next issue

This issue in ePub format

Get the latest issue to your desktop