Unified Fingerprinting/Ranging Localization in Harsh Environments

Abstract

Context-awareness in wireless sensor networks (WSNs) relies mainly on the position of objects and humans. The provision of this positional information becomes challenging in the harsh environmental conditions where WSNs are commonly deployed. With an antagonistic philosophy of design, fingerprinting and ranging have emerged as the key technologies underpinning wireless localization in harsh environments. Fingerprinting primarily focuses on accurate estimation at the expense of exhaustive calibration. Ranging mainly pursues an easy-to-deploy solution at the expense of moderate performance. In this paper, we present a resilient framework for sustained localization based on accurate fingerprinting in critical areas and light ranging in noncritical spaces. Such framework is conceived from the Bayesian perspective that facilitates the specification of recursive algorithms for real-time operation. In comparison to conventional implementations, we assessed the proposed framework in an indoor scenario with measurements gathered by commercial devices. The presented techniques noticeably outperform current approaches, enabling a flexible adaptation to the fluctuating conditions of harsh environments.

1. Introduction

The burgeoning demand for context-aware services and smarter environments has been largely motivated by the proliferation of the increasingly dense wireless sensor networks (WSNs) and intelligent embedded devices [1–5]. These services and environments accommodate applications in diverse fields such as healthcare [6–8], emergency [9–11], or industry [12–14]. In order to satisfy such a demand, the positional information plays a crucial role and has inevitably put indoor localization in the forefront of research [15–21]. Current positioning techniques that rely on global navigation satellite systems (GNSS) operate robustly in open areas and sparse environments [16, 22]. However, there is no alternative technique with analogous performance and affordable complexity in indoor areas or harsh environments [23, 24]. The proposed alternatives can be coarsely classified into fingerprinting and ranging localization techniques [25–35].

Fingerprinting techniques determine the location of a mobile target from position-related information provided by offline and online measurements [25–28]. In the offline phase, different features from the transmitted signals in the wireless network are stored at several positions to form a database of location fingerprints. In the online phase, the position is estimated by comparison of the new received values with the database (i.e., with their fingerprint). Fingerprinting techniques involve two major drawbacks: they require an arduous offline phase of calibration and are very sensitive to fast environmental changes [25].

Ranging techniques determine the location of a mobile target from range-related information provided by time-of-arrival (TOA) [29–31] or received signal-strength (RSS) [32–34] measurements. In a first stage, the distance to a set of anchors with known positions is estimated from the signals transmitted to the target. In a second stage, the position is estimated by a process known as trilateration (i.e., intersection of circles). Ranging techniques suffer from two dominant limitations: their accuracy is far from fingerprinting methods and falls down under multipath and non-line-of-sight (NLOS) conditions [35].

Strengths and weaknesses of fingerprinting and ranging localization have inevitably focused the challenge in developing unifying systems without substantially increasing complexity and cost. Such solutions will enable fine localization via fingerprinting in places where the accuracy is critical or when the database can be frequently updated and coarse localization via ranging in areas where there is no database or when it has become obsolete. In [36], fingerprint- and TOA-based methods are coupled to localize UWB devices from a maximum-likelihood (ML) perspective; in [37], fingerprint- and RSS-based techniques are fused by using RFID tags/readers and particle filtering; in [38], fingerprint-based localization and channel-estimation tracking are combined to localize UWB devices via extended Kalman filter (EKF); in [39], fingerprinting positioning and pyroelectric infrared sensors are joined to overcome error induced by RSS variation.

In this paper, we propose framework and algorithms for unified fingerprinting/ranging in harsh environments based on Bayesian filtering. Such framework integrates position-related measurements from the first and range-related measurements from the second. Moreover, it further considers the dynamic nature of the wireless channel entailing more accurate ranging localization. Specifically, the main contributions of the paper are as follows:

• (i)

We define a unifying framework for target localization that accommodates fine estimates via fingerprinting and coarse estimates via ranging.

(ii)

We provide realistic likelihood functions to model fingerprints and path-loss exponents based on kernel mixtures.

(iii)

We derive algorithms to implement such framework by means of the unscented transformation that allows for efficient computation.

(iv)

We assess the performance of the developed framework and algorithms in a real scenario over conventional light devices.

The rest of the paper is organized as follows: Section 2 outlines the multiagent architecture proposed in previous works for information fusion; Section 3 presents the framework for unified data fusion of fingerprinting/ranging measurements; Section 4 offers efficient algorithms to enable real-time operation under the proposed framework; Section 5 assesses the provided algorithms under an experimental case study with light devices; and Section 6 summarizes the conclusions drawn from the research.

Notations. ${\mathbf{x}}_{\mathrm{1}:k}$ denotes the sequence of random vectors $\{{\mathbf{x}}_{\mathrm{1}},\dots ,{\mathbf{x}}_k\}$ ; ${\left[·\right]}^T$ denotes the transpose of its argument; ${\mathbf{I}}_n\in {\mathbb{R}}^{n\times n}$ denotes the $n\times n$ identity matrix; $f(\mathbf{x})$ denotes the probability density function of a continuous random variable x; and $\phi (\mathbf{x};\mathit{\mu },\mathbf{\Sigma })$ denotes the probability density function of a Gaussian random vector $\mathbf{x}~\mathcal{N}(\mathit{\mu },\mathbf{\Sigma })$ .

2. Previous Work

This section provides a general overview of the multiagent architecture based on virtual organizations that we presented recently to accomplish the information fusion problem [40]. The virtual organization of agents manages the resources of the Cloud system in which it is deployed. It was created with the PANGEA platform that facilitates the development of agents in light devices and the integration of different hardware [41, 42]. The architecture is organized in $\mathrm{4}$ layers as can be seen in Figure 1 and that is what we briefly describe here for completeness [40].

Figure 1

The architecture presented in previous works consists of a multiagent architecture based on virtual organizations that integrates with an information fusion model [40].

Layer 0. It defines communication with sensor networks of different nature and gets the raw (encapsulated) data from them.

Layer 1. It processes the contextual information obtained from layer 0 and provides a set of low-level services for this purpose.

Layer 2. It incorporates agents specifically designed to interact with layer 1 and brings others specialized in information fusion.

Layer 3. It allows the management and customization of services to end users and facilitates decision-making by the user.

In the presented architecture, the fusion of different information flows is accomplished in layer 2. However, the low-level services that extract information from row data are implemented in layer 1. The greater the information extracted regarding a parameter in layer 1 the better the performance of the fusion model in layer 2 [43, 44]. In our previous work, we focused on layer 2, specifically on workflow and fusion organizations [40]. In this paper, we focus on layer 1 and layer 2, specifically on the processing of RSS data to extract position-related information.

3. Localization Framework

In this section, we formulate the problem of localization in harsh environments and provide a general framework for its solution based on optimal recursive Bayesian filtering [45, 46].

3.1. Problem Statement

In the following, we are going to assume a two-dimensional scenario where we estimate the position of a mobile target by fusing information provided by RSS measurements. In order to do that, we first accomplish an offline phase in which we collect RSS measurements at a set of M fingerprint points, $\{{\mathbf{f}}_m{\}}_{m=\mathrm{1}}^M$ , covering only a selected area. In the online phase, we collect again RSS measurements, $\{{\mathbf{y}}_k{\}}_{k\in \mathbb{N}}$ , at discrete time instants, $t_{k\in \mathbb{N}}$ , inside or outside the selected area (hereinafter, “fingerprinting area” or “ranging area,” resp.). From these measurements, we estimate the state vector, $\{{\mathbf{x}}_k{\}}_{k\in \mathbb{N}}$ . Next, we determine the entries to state and measurement vectors.

The state vector contains the position and its first derivatives so that $\{{\mathbf{x}}_k{\}}_{k\in \mathbb{N}}$ is a Markov chain (i.e., the current state only depends on the previous one) [35, 45]. In this paper, such a vector is augmented to include the path-loss exponent with respect to every anchor used in the ranging area (see Section 3.2). Therefore, the state vector is ${\mathbf{x}}_k=[{\mathbf{p}}_k,{\mathbf{v}}_k,{\mathbf{a}}_k,{\mathit{\beta }}_k]\in {\mathbb{R}}^{\mathrm{6}+L}$ , where ${\mathbf{p}}_k\in {\mathbb{R}}^{\mathrm{2}}$ is the target's position, ${\mathbf{v}}_k\in {\mathbb{R}}^{\mathrm{2}}$ its velocity, ${\mathbf{a}}_k\in {\mathbb{R}}^{\mathrm{2}}$ its acceleration, ${\mathit{\beta }}_k\in {\mathbb{R}}^L$ the vector of path-loss exponents, and $L\in \mathbb{R}$ the total number of anchors used for ranging.

The measurement vector conveys any state-related information received at time instant $t_k$ (i.e., its dimension may be different from the previous one). We have to use different measurements vector depending on whether we are within the fingerprinting or the ranging area. In the former case, the state vector is ${\mathbf{y}}_k={\mathbf{y}}_k^f\in {\mathbb{R}}^{L_k}$ , where ${\mathbf{y}}_k^f\in {\mathbb{R}}^{L_k}$ are the RSS measurements received at time $t_k$ . In the latter case, the state vector is ${\mathbf{y}}_k=[{\mathbf{y}}_k^s,{\mathbf{y}}_k^{\beta }]\in {\mathbb{R}}^{\mathrm{2}{L}_k}$ , where ${\mathbf{y}}_k^s\in {\mathbb{R}}^{L_k}$ are the RSS measurements received at time $t_k$ and ${\mathbf{y}}_k^{\beta }\in {\mathbb{R}}^{L_k}$ the path-loss exponents measured with respect to the visible anchors. In both cases, $L_k\in \mathbb{R}$ is the number of visible anchors at that particular moment.

In addition to the information conveyed by the measurements, the fact that the sequence of positions is highly correlated in time can also be used as another source of information. With the defined measurements and state vectors, it can be assumed that, given the current state vector, ${\mathbf{x}}_k$ , the measurement vector, ${\mathbf{y}}_k$ , is independent of all previous and future states and measurements [35, 45]. Therefore, we can build the hidden Markov model (HMM) shown in Figure 2 that leads to two kinds of dependence between the random variables: the relationship between the state vector in time $t_k$ and the state vector in time $t_{k-\mathrm{1}}$ , that is, $f\left({\mathbf{x}}_k\hspace{0.17em}|\hspace{0.17em}{\mathbf{x}}_{k-\mathrm{1}}\right)$ , called dynamic model; and the relationship between the measurements and the state vector in each time, that is, $f\left({\mathbf{y}}_k\hspace{0.17em}|\hspace{0.17em}{\mathbf{x}}_k\right)$ , called measurements model [35, 45]. (Note that, in addition to different measurements vectors, we have to use different measurements models for fingerprinting and ranging areas since the unknown dependencies between them prevent us from utilizing a joint model.) Next subsection defines both models for fingerprinting/ranging localization in harsh environments. (The proposed framework accommodates other position-related information given by diverse devices such as GPS receivers or foot-mounted inertial measurement units [47].)

Figure 2

HMM for states and measurements evolution. The relationship between ${\mathbf{x}}_k$ and ${\mathbf{x}}_{k-\mathrm{1}}$ and the relationship between ${\mathbf{y}}_k$ and ${\mathbf{x}}_k$ are the only two kinds of dependence.

3.2. Involved Models

In the following, we define realistic models for the fusion of time-evolution and measuring information.

3.2.1. Dynamic Model

The dynamic model is characterized by the conditional density $f\left({\mathbf{x}}_k\hspace{0.17em}|\hspace{0.17em}{\mathbf{x}}_{k-\mathrm{1}}\right)$ .

Given the position, velocity, and acceleration at time $t_{k-\mathrm{1}}$ , ${\mathbf{p}}_{k-\mathrm{1}}$ , ${\mathbf{v}}_{k-\mathrm{1}}$ , and ${\mathbf{a}}_{k-\mathrm{1}}$ , we can approximate their values in time $t_k$ , ${\mathbf{p}}_k$ , ${\mathbf{v}}_k$ , and ${\mathbf{a}}_k$ , by means of their Taylor series expansion as [45]

$$\begin{array}{cc}& \left[\begin{array}{c}{\mathbf{p}}_k\\ {\mathbf{v}}_k\\ {\mathbf{a}}_k\end{array}\right]=\left(\begin{array}{ccc}{\mathbf{I}}_{\mathrm{2}}& {\Delta }_k{\mathbf{I}}_{\mathrm{2}}& \frac{{\Delta }_k^{\mathrm{2}}}{\mathrm{2}}{\mathbf{I}}_{\mathrm{2}}\\ \mathbf{0}& {\mathbf{I}}_{\mathrm{2}}& {\Delta }_k{\mathbf{I}}_{\mathrm{2}}\\ \mathbf{0}& \mathbf{0}& {\mathbf{I}}_{\mathrm{2}}\end{array}\right)\left[\begin{array}{c}{\mathbf{p}}_{k-\mathrm{1}}\\ {\mathbf{v}}_{k-\mathrm{1}}\\ {\mathbf{a}}_{k-\mathrm{1}}\end{array}\right]+{\mathbf{n}}_k^{d,\mathrm{1}},\end{array}$$

(1) where ${\Delta }_k=(t_k-t_{k-\mathrm{1}})\in \mathbb{R}$ is the sampling interval and ${\mathbf{n}}_k^{d,\mathrm{1}}\in {\mathbb{R}}^{\mathrm{6}}$ is the error term. To model this error term as white Gaussian noise (i.e., as a discrete Wiener process) is the most common.

The characteristics of the wireless channel are highly related in time [48–50]. However, this fact is rarely considered in the design of positioning filtering algorithms [51]. In this paper, given the vector of path-loss exponents at time $t_{k-\mathrm{1}}$ , ${\mathit{\beta }}_{k-\mathrm{1}}$ , the vector of path-loss exponents at time $t_k$ , ${\mathit{\beta }}_k$ , is modeled as

$$\begin{array}{cc}& {\mathit{\beta }}_k={\mathit{\beta }}_{k-\mathrm{1}}+{\mathbf{n}}_k^{d,\mathrm{2}},\end{array}$$

(2) where the term ${\mathbf{n}}_k^{d,\mathrm{2}}\in {\mathbb{R}}^L$ is white Gaussian noise.

Therefore, the dynamic model, $f\left({\mathbf{x}}_k\hspace{0.17em}|\hspace{0.17em}{\mathbf{x}}_{k-\mathrm{1}}\right)$ , is given by

$$\begin{array}{cc}& f\left({\mathbf{x}}_k\hspace{0.17em}|\hspace{0.17em}{\mathbf{x}}_{k-\mathrm{1}}\right)=\phi \left({\mathbf{x}}_k;{\mathbf{F}}_k{\mathbf{x}}_{k-\mathrm{1}},{\mathbf{\Sigma }}_k^d\right),\end{array}$$

(3) where the transition matrix

$$\begin{array}{cc}& {\mathbf{F}}_k=\left(\begin{array}{cccc}{\mathbf{I}}_{\mathrm{2}}& {\Delta }_k{\mathbf{I}}_{\mathrm{2}}& \frac{{\Delta }_k^{\mathrm{2}}}{\mathrm{2}}{\mathbf{I}}_{\mathrm{2}}& \mathbf{0}\\ \mathbf{0}& {\mathbf{I}}_{\mathrm{2}}& {\Delta }_k{\mathbf{I}}_{\mathrm{2}}& \mathbf{0}\\ \mathbf{0}& \mathbf{0}& {\mathbf{I}}_{\mathrm{2}}& \mathbf{0}\\ \mathbf{0}& \mathbf{0}& \mathbf{0}& {\mathbf{I}}_L\end{array}\right)\end{array}$$

(4) and ${\mathbf{\Sigma }}_k^d\in {\mathbb{R}}^{(\mathrm{6}+L)\times (\mathrm{6}+L)}$ is the covariance matrix corresponding to the noise vector $[{\mathbf{n}}_k^{d,\mathrm{1}},{\mathbf{n}}_k^{d,\mathrm{2}}]$ .

3.2.2. Ranging Likelihood

The measurements model in ranging areas is characterized by the likelihood $f\left({\mathbf{y}}_k^s\hspace{0.17em}|\hspace{0.17em}{\mathbf{x}}_k\right)$ .

The RSS values are attenuated, among other factors, by the distance between target and anchors. This attenuation is proportional to the inverse of the distance raised to a path-loss exponent [34, 35]. In logarithmic units, we have that, for the lth anchor, with position ${\mathbf{p}}^{(l)}\in {\mathbb{R}}^{\mathrm{2}}$ ,

$$\begin{array}{cc}& y_k^s=\alpha -\mathrm{10}{\beta }_k{\log }_{\mathrm{10}}‖{\mathbf{p}}^{\left(l\right)}-{\mathbf{p}}_k‖+n_k^s,\end{array}$$

(5) where $\alpha \in \mathbb{R}$ is a constant that depends on several factors such as fast and slow fading, gains in transmitter and receiver antennas, and the transmitted power and ${\beta }_k\in \mathbb{R}$ is the path-loss exponent that characterizes the wireless channel [49]. Finally, $n_k^s$ is a Gaussian noise term caused by shadowing [34, 35]. The value of α can be previously known, for example, by averaging measured values at the reference distance (in this case, $\mathrm{1}$ meter away from the anchor) or by self-calibration with measurements shared among anchors (with known positions) [18]. The path-loss exponent, ${\beta }_k$ , in turn, can be dynamically obtained or trained in each scenario [27, 34].

Then, the RSS measurements in ranging areas are governed by the likelihood,

$$\begin{array}{cc}& f\left(y_k^s\hspace{0.17em}|\hspace{0.17em}{\mathbf{p}}_k\right)=\phi \left(y_k^s;\alpha -\mathrm{10}{\beta }_k{\log }_{\mathrm{10}}‖{\mathbf{p}}^{\left(l\right)}-{\mathbf{p}}_k‖,{\sigma }_k^s\right),\end{array}$$

(6) where ${\sigma }_k^s\in \mathbb{R}$ is the standard deviation corresponding to $n_k^s$ .

Figure 3 represents the performance of the likelihood function defined in (6). Figure 3(a) depicts the position of the anchors with known positions (in orange) as well as the position of the target (in red). Figure 3(b) shows the likelihood values obtained in the area by means of (6) after receiving one RSS measurement from every anchor. Figure 3(c) shows the likelihood values in the fixed axis (indicated in Figure 3(b)) obtained by means of (6) for different numbers of RSS measurements received from anchor $\mathrm{A}\mathrm{P}\mathrm{1}$ . From Figure 3 we can point out that the greater the number of measurements the narrower the likelihood in the direction joining target and anchor. This result is in concordance with the known fact that each range measurement only provides information about the position in the direction joining target and anchor [17].

Figure 3

The defined likelihood for ranging areas provides a continuous function that facilitates the information fusion under the Bayesian framework.

In order to generalize the localization framework, we here consider the most general case where path-loss exponents are dynamically estimated, for which a variety of algorithms can be found in the literature [34, 52–56]. Specifically, we adhere to the technique proposed in [34] based on maximizing the compatibility of the distances between the target and the anchors given a set of received RSS values and subject to a set of feasible solutions, Λ. (The set of constrains can come, e.g., from feasible distances between the target and the anchors based on transmission power and antenna gains [34].) That is,

$$\begin{array}{cc}& {\widehat{\mathit{\beta }}}_k=\underset{{\mathit{\beta }}_k}{\mathrm{argmax}}\hspace{0.17em}C\left({\mathbf{y}}_k^s,\alpha ,{\mathit{\beta }}_k,{\mathbf{p}}_k,{\left\{{\mathbf{p}}^{\left(l\right)}\right\}}_{l=\mathrm{1},\dots ,L_k}\right)\hspace{1em}\text{s.t.\hspace{0.17em}\hspace{0.17em}}{\mathit{\beta }}_k\in \Lambda ,\end{array}$$

(7) where $C(·)$ is the compatibility function as defined in [34].

Given the actual state, we can treat estimates of path-loss exponents as independent additional measurements,   ${\mathbf{y}}_k^{\beta }$ , related with the state by the model

$$\begin{array}{cc}& {\mathbf{y}}_k^{\beta }={\mathit{\beta }}_k+{\mathbf{n}}_k^{\beta },\end{array}$$

(8) where ${\mathbf{n}}_k^{\beta }\in {\mathbb{R}}^L$ is white Gaussian noise. (Note that this is a mild assumption since the main relationship between RSS measurements and path-loss exponents is given by the distance between target and anchor, and the remaining possible dependencies are unknown).

Then, the measured path-loss exponents in ranging areas are governed by the likelihood

$$\begin{array}{cc}& f\left({\mathbf{y}}_k^{\beta }\hspace{0.17em}|\hspace{0.17em}{\mathit{\beta }}_k\right)=\phi \left({\mathbf{y}}_k^{\beta };{\mathit{\beta }}_k,{\mathbf{\Sigma }}_k^{\beta }\right),\end{array}$$

(9) where ${\mathbf{\Sigma }}_k^{\beta }\in {\mathbb{R}}^{L\times L}$ is the covariance matrix corresponding to the noise vector ${\mathbf{n}}_k^{\beta }$ .

Therefore, the whole measurements model, $f\left({\mathbf{y}}_k^s\hspace{0.17em}|\hspace{0.17em}{\mathbf{x}}_k\right)$ , for ranging areas is given by (6) and (9).

3.2.3. Fingerprinting Likelihood

The measurements model in fingerprinting areas is characterized by the likelihood $f\left({\mathbf{y}}_k^f\hspace{0.17em}|\hspace{0.17em}{\mathbf{x}}_k\right)$ .

During the offline phase, for the mth fingerprint, ${\mathbf{f}}_m$ , we receive a set of $S_m^{(l)}$ RSS measurements, ${\mathbf{y}}_m^{(l)}$ , from each one of the visible anchors. We assume that the random variable associated with such a set of measurements follows a Gaussian distribution with mean its sample mean, ${\bar{\mathbf{y}}}_m^{(l)}$ , and standard deviation ${\sigma }_m^{(l)}/\sqrt{S_m^{(l)}}$ , where ${\sigma }_m^{(l)}$ is the sample standard deviation. During the online phase, given a set of received RSS measurements— ${\mathbf{y}}_k^f\in {\mathbb{R}}^{L_k}$ —the likelihood function of the fingerprint ${\mathbf{f}}_m$ is given by

$$\begin{array}{cc}& f\left({\mathbf{y}}_k^f\hspace{0.17em}|\hspace{0.17em}{\mathbf{f}}_m\right)={\displaystyle \prod }_{l=\mathrm{1}}^{L_k}\phi \left(y_k^{\left(l\right)};{\bar{\mathbf{y}}}_m^{\left(l\right)},\frac{{\sigma }_m^{\left(l\right)}}{\sqrt{S_m^{\left(l\right)}}}\right),\end{array}$$

(10) where $y_k^{(l)}$ is an RSS measurement received from the lth anchor in $t_k$ .

By considering a Gaussian kernel to represent the region of the map corresponding to each fingerprint [26, 28], we can approximate the measurements model by a mixture of the individual likelihood at every point of the set $\{{\mathbf{f}}_m{\}}_{m=\mathrm{1}}^M$ as

$$\begin{array}{cc}& f\left({\mathbf{y}}_k^f\hspace{0.17em}|\hspace{0.17em}{\mathbf{p}}_k\right)\approx {\displaystyle \sum }_{m=\mathrm{1}}^{M}f\left({\mathbf{y}}_k^f\hspace{0.17em}|\hspace{0.17em}{\mathbf{f}}_m\right)\phi \left({\mathbf{p}}_k;{\mathbf{f}}_m,h^{\mathrm{2}}{\mathbf{I}}_{\mathrm{2}}\right)\approx {\displaystyle \sum }_{m=\mathrm{1}}^M{\omega }_k^{\left(m\right)}\phi \left({\mathbf{p}}_k;{\mathbf{f}}_m,h^{\mathrm{2}}{\mathbf{I}}_{\mathrm{2}}\right),\end{array}$$

(11) where ${\mathbf{f}}_m\in {\mathbb{R}}^{\mathrm{2}}$ includes the coordinates of the mth fingerprint and $h\in \mathbb{R}$ is a positive number called bandwidth [26, 35, 57]. (A practical choice for the bandwidth can be obtained as one-half the resolution of the involved data, in this case, the change in coordinates between two adjacent fingerprints [35].)

Figure 4 represents the performance of the likelihood function defined in (11). Figure 4(a) depicts the position of the fingerprints stored in the offline phase (in grey) as well as the position of the target during the online phase (in red). Figure 4(b) shows the likelihood values obtained in the area by means of (11) after receiving one RSS measurement in the online phase. Figure 4(c) shows the likelihood values in the fixed axis (indicated in Figure 4(b)) obtained by means of (11) for different numbers of RSS measurements received during the online phase. From Figure 4 we can conclude that the greater the number of measurements the more likely the position of the closest fingerprint to the actual position. Moreover, the use of a kernel mixture provides a continuous function that facilitates the information fusion under the Bayesian framework.

Figure 4

The defined likelihood for fingerprinting areas provides a continuous function that facilitates the information fusion under the Bayesian framework.

The previous likelihood can be augmented to incorporate the information conveyed by the fingerprints with respect to the path-loss exponents. In such a case, the fingerprint vector ${\mathbf{f}}_m\in {\mathbb{R}}^{\mathrm{2}+L}$ includes its positional coordinates as well as the path-loss exponents with respect to each anchor used for ranging localization. The path-loss exponent stored for the lth anchor and the mth fingerprint is obtained as [34, 35]

$$\begin{array}{cc}& {\widehat{\beta }}_m^{\left(l\right)}=\frac{\alpha -{\bar{\mathbf{y}}}_m^{\left(l\right)}}{\mathrm{10}\hspace{0.17em}{\log }_{\mathrm{10}}‖{\mathbf{p}}^{\left(l\right)}-{\mathbf{p}}^{\left(m\right)}‖},\end{array}$$

(12) where ${\bar{\mathbf{y}}}_m^{(l)}$ is the sample mean of the set of measurements received in the offline phase from the l-anchor at the mth fingerprint and ${\mathbf{p}}^{(l)}$ and ${\mathbf{p}}^{(m)}$ are the coordinates corresponding to such anchor and fingerprint, respectively.

Therefore, the measurements model, $f\left({\mathbf{y}}_k^f\hspace{0.17em}|\hspace{0.17em}{\mathbf{x}}_k\right)$ , for fingerprinting areas is given by

$$\begin{array}{cc}& f\left({\mathbf{y}}_k^f\hspace{0.17em}|\hspace{0.17em}{\mathbf{p}}_k,{\mathit{\beta }}_k\right)\approx {\displaystyle \sum }_{m=\mathrm{1}}^M{\omega }_k^{\left(m\right)}\phi \left(\left[{\mathbf{p}}_k,{\mathit{\beta }}_m\right];{\mathbf{f}}_m,\mathbf{H}\right),\end{array}$$

(13) where ${\mathbf{f}}_m\in {\mathbb{R}}^{\mathrm{2}}$ includes the coordinates and the path-loss exponents for the mth fingerprint and $\mathbf{H}\in {\mathbb{R}}^{(\mathrm{2}+L)\times (\mathrm{2}+L)}$ is a diagonal bandwidth matrix with positive diagonal elements $\{h_i^{\mathrm{2}}{\}}_{i=\mathrm{1},\dots ,\mathrm{2}+L}$ [26, 35, 57].

4. Efficient Algorithms

The graphical model depicted in Figure 2 allows for optimal localization by means of the well-known Bayesian filtering process [45, 46]. In the following, we propose an efficient implementation for real-time localization systems in light devices.

4.1. Real-Time Filtering for Localization

Bayesian filtering acquires different expressions depending on the specific distributions of the dynamic model and the likelihood. The complexity constraints imposed by a real-time localization system and the tractability benefits of Gaussian family favor the selection of the latter for all the involved distributions [46]. Moreover, the lack of linearity in the models defined in Section 3 enforces the use of a suboptimal solution to the filtering problem. The most common is to linearize such models by Taylor series expansion (i.e., to use extended Kalman-like filters) [58]. In this paper, we select the unscented transformation since it better captures the higher order moments caused by the nonlinear transformation and avoids the computation of Jacobian and Hessian matrices [59, 60]. The complexity of both extended and unscented transformations is on the order of the cube of the dimension of the state, which cannot compromise their real-time operation [61]. Other approaches, such as particle filters or Gaussian mixture filters, are discarded since they suffer from the curse of dimensionality induced by the dimension of the state vector [61, 62]. (The number of filtered path-loss exponents, and consequently the dimension of the state, grows with the number of anchors used for ranging.)

Algorithm 1 shows the pseudocode of the unscented-based implementation for the proposed unified localization framework. (In Algorithm 1, $f\left({\mathbf{x}}_{\mathrm{1}}\hspace{0.17em}|\hspace{0.17em}{\mathbf{x}}_{\mathrm{0}}\right)=f({\mathbf{x}}_{\mathrm{1}})$ .)

Algorithm 1: Real-time filtering for unified localization.

(1) Initialization:

(2) Set π equal to the prior distribution of ${\mathbf{x}}_{\mathrm{1}}$ .

    $${\mathbf{\mu }}_{\pi }⟵\mathbb{E}\left\{{\mathbf{x}}_{\mathrm{1}}\right\}$$

    $${\mathbf{\Sigma }}_{\pi }⟵\mathbb{E}\left\{{\mathbf{x}}_{\mathrm{1}}{\mathbf{x}}_{\mathrm{1}}^T\right\}-{\mathbf{\mu }}_{\pi }{\mathbf{\mu }}_{\pi }^T$$

(3) $\pi \leftarrow \phi ({\mathbf{x}}_{\mathrm{1}};{\mathbf{\mu }}_{\pi },{\mathbf{\Sigma }}_{\pi })$

(4) RecursiveBayesian inference:

(5) for   $k=\mathrm{1,2},\dots$   do

(6)    (i) Prediction:

      π⟵ ut_predict $$\left(f\left({\mathbf{x}}_k\hspace{0.17em}|\hspace{0.17em}{\mathbf{x}}_{k-\mathrm{1}}\right),\pi \right)$$

(7)   if   ${\mathbf{\mu }}_{\pi }\in$ “Fingerprinting area” then

(8)    (ii) Fingerprinting update:

      π⟵ fp_update $$\left(f\left({\mathbf{y}}_k^f\hspace{0.17em}|\hspace{0.17em}{\mathbf{x}}_k\right),\pi \right)$$

(9)   else

(10)    (iii) Path-loss estimation:

       $$\left\{{\mathbf{\beta }}_{\pi }\right\}$$ ⟵ pl_estimate $$\left({\mathbf{y}}_k^s,{\left\{{\mathbf{p}}^{(l)}\right\}}_{l=\mathrm{1}}^L\right)$$

(11)    (iv) Ranging update:

       π⟵ ut_update $$\left(f\left({\mathbf{y}}_k^s\hspace{0.17em}|\hspace{0.17em}{\mathbf{x}}_k\right),\pi \right)$$

(12)  end if

(13)  return   $\mathbb{E}\{{\mathbf{x}}_k\hspace{0.17em}|\hspace{0.17em}{\mathbf{y}}_{\mathrm{1}:k}\}\leftarrow \mathbb{E}\{\pi \}={\mathbf{\mu }}_{\pi }$

(14) end for

In Algorithm 1, we utilize conventional predict (ut_predict()) and update functions (ut_update()) based on the unscented transformation [60, 63]. In the fingerprinting case, we update with a Gaussian mixture and approximate the posterior mixture density to a single Gaussian. This process is condensed within the functionfp_update() that we described in the next section. In the ranging case, we dynamically estimate the path-loss exponents previously to the update. This process is addressed in the functionpl_estimate() for which different alternatives can be adopted [34, 51–56].

4.2. Fingerprinting Update

As we stated in previous section, the real-time constraints favor the selection of the Gaussian family in the filtering process. However, we defined a Gaussian mixture for the likelihood in fingerprinting areas (see Section 3.2). The update step in Bayesian filtering consists of the product of the prediction and the likelihood (and a subsequent normalization), which leads to an exponential increase of the number of involved densities when using a likelihood mixture [45, 46]. In Algorithm 2 we address this issue by approximating the posterior mixture density to a single Gaussian density. This approximation is based on collapsing the M-component mixture arising after the update into one Gaussian with the same mean and covariance as the mixture.

Algorithm 2: Function to update state from fingerprints.

(1) function  fp_update $\left(\{{\omega }^{(m)},\mathbf{P},{\mathbf{f}}_m,\mathbf{H}{\}}_{m=\mathrm{1}}^M,\mathbf{\mu },\mathbf{\Sigma }\right)$

(2)   Fingerprinting update:

(3)   for   $m=\mathrm{1,2},\dots ,M$   do

     $${\mathbf{S}}_{\pi }^{(m)}⟵\mathbf{P}\mathbf{\Sigma }{\mathbf{P}}^T+\mathbf{H}$$

     $${\mathbf{K}}_{\pi }^{(m)}⟵\mathbf{\Sigma }{\mathbf{P}}^T{\left({\mathbf{S}}_{\pi }^{(m)}\right)}^{-\mathrm{1}}$$

     $${\mathbf{\Sigma }}_{\pi }^{(m)}⟵\left(\mathbf{I}-{\mathbf{K}}_{\pi }^{(m)}\mathbf{P}\right)\mathbf{\Sigma }$$

     $${\mathbf{\mu }}_{\pi }^{(m)}⟵\mathbf{\mu }+{\mathbf{K}}_{\pi }^{(m)}\left({\mathbf{f}}_m-\mathbf{P}\mathbf{\mu }\right)$$

     $${\omega }_{\pi }^{(m)}⟵{\omega }^{(m)}\phi \left({\mathbf{f}}_m;\mathbf{P}\mathbf{\mu },{\mathbf{S}}_{\pi }^{(m)}\right)$$

(4)   end for

(5)   Normalization:

     $${\left\{{\omega }_{\pi }^{(m)}\right\}}_{m=\mathrm{1}}^M⟵\frac{{\left\{{\omega }_{\pi }^{(m)}\right\}}_{m=\mathrm{1}}^M}{{\sum }_{m=\mathrm{1}}^M{\omega }_{\pi }^{(m)}}$$

(6)   Gaussian approximation:

     $${\mathbf{\mu }}_{\pi }⟵{{\displaystyle \sum }}_{m=\mathrm{1}}^M{\omega }_{\pi }^{(m)}{\mathbf{\mu }}_{\pi }^{(m)}$$

     $${\mathbf{\Sigma }}_{\pi }⟵{{\displaystyle \sum }}_{m=\mathrm{1}}^M{\omega }_{\pi }^{(m)}\left({\mathbf{\Sigma }}_{\pi }^{(m)}+\left({\mathbf{\mu }}_{\pi }^{(m)}-{\mathbf{\mu }}_{\pi }\right){\left({\mathbf{\mu }}_{\pi }^{(m)}-{\mathbf{\mu }}_{\pi }\right)}^T\right)$$

(7)   return   $\mathbf{\mu }\leftarrow {\mathbf{\mu }}_{\pi };\mathbf{\Sigma }\leftarrow {\mathbf{\Sigma }}_{\pi }$

(8) end function

Algorithm 2 shows the pseudocode of thefp_update() function, which takes as inputs the parameters that characterize the prediction, $\phi ({\mathbf{x}}_k;\mathit{\mu },\mathbf{\Sigma })$ , and the likelihood, ${\sum }_{m=\mathrm{1}}^M{\omega }^{(m)}\phi (\mathbf{P}{\mathbf{x}}_k;{\mathbf{f}}_m,\mathbf{H})$ , where P is a matrix projecting the components of ${\mathbf{x}}_k$ into the components stored in the fingerprints (position and path-loss exponents).

5. Results and Discussion

The goal of this section is to quantify the performance of the localization framework described in Section 3. The system is evaluated in the experimental case study of a human walking with a Smartphone that collects RSS measurements from the network. In the following, we describe the set-up for the experiments and present the performance results.

5.1. Experimental Set-Up

We selected WiFi as the underlying technology to provide indoor localization. WiFi technology is more accessible and less expensive than other alternative technologies such as RFID or UWB and has a longer range and larger bandwidth than ZigBee or Bluetooth. Moreover, from signals transmitted in the WiFi network, we can easily extract the RSS metric, while time- or angle-related measurements imply additional complexities and costs [35]. The anchors were Cisco Aironet 1600 Series Access Points (802.11a/g/n). The mobile target was a human with Smartphone LG Nexus 4 (802.11b/g/n) that covered the path shown in Figure 5(b). The total length of the path was approximately $\mathrm{120}$ meters, implying a total time of $\mathrm{2}$ minutes.

Figure 5

The proposed unified framework provides accurate localization via fingerprinting for critical areas and ready-to-use localization via ranging for noncritical spaces.

For fingerprinting localization, the database was created by storing at least $\mathrm{10}$ RSS values from all the detectable access points (up to $\mathrm{25}$ ) in the fingerprints marked in Figure 5(a). In the online phase, we employed $\mathrm{48}$ RSS values per point.

For ranging localization, we employed $\mathrm{16}$ RSS measurements per point from the $\mathrm{4}$ access points plotted in Figure 5(a). All the RSS measurements were considerably affected by NLOS and multipath propagation conditions.

To obtain the localization results we utilized dynamic and measurements models described in Section 3. We also added zero-mean Gaussian priors for velocity and acceleration. For the dynamic model, we selected a diagonal noise covariance matrix, ${\mathbf{\Sigma }}_k^d$ , with main diagonal values roughly $\mathrm{50}$ % of the maximum [35, 45]. For the measurements model, we utilized fixed distribution parameters learned from previous works [34, 35].

5.2. Experimental Results

Figure 5(b) and Table 1 show the localization results in the mentioned path. For each implemented technique we provide the quartiles of the error in position estimates as well as the root mean square error (RMSE). We call

• (i)

kNN: the position estimates in the fingerprinting area with a conventional implementation based on k-Nearest Neighbor classification [15],

(ii)

ML: the position estimates in the ranging area with a conventional implementation based on maximum likelihood by using (6) [64],

(iii)

kNN + ML: the position estimates in the complete scenario with the conventional implementation based on k-Nearest Neighbor classification for fingerprinting and maximum likelihood for ranging [15, 64],

(iv)

FL: the position estimates in the fingerprinting area with the proposed algorithm,

(v)

RL: the position estimates in the ranging area with the proposed algorithm (as stated above, in order to dynamically estimate the path-loss exponents, we implemented the technique proposed in [34] based on maximizing the compatibility of the distances among anchors and target from a set of received RSS values and a set of constraints. However, other alternatives could have been implemented [52–56]),

(vi)

FL + RL: the position estimates in the complete scenario with the proposed unifying fingerprinting/ranging algorithm.

Table 1

Position estimation error quartiles and RMSE obtained with conventional and proposed algorithms.

		Quartiles	RMSE
Conventional	kNN	0.00 m-0.00 m-0.00 m	0.61 m
	ML	3.05 m-3.87 m-5.39 m	5.11 m
	kNN + ML	0.00 m-0.38 m-3.12 m	3.17 m
Proposed	FL	0.05 m-0.06 m-0.15 m	0.57 m
	RL	2.17 m-3.66 m-5.05 m	3.83 m
	FL + RL	0.06 m-0.39 m-2.91 m	2.39 m

From Figure 5(b) and Table 1 we can point out that (1) the proposed framework facilitates the shift from accurate fingerprinting to coarse ranging; (2) fingerprinting outperforms ranging in harsh environments while requiring greater calibration effort; and (3) the proposed approach improves the RMSE in ranging and fingerprinting and unified localization approximately $\mathrm{6.6}$ %, $\mathrm{25.0}$ %, and $\mathrm{24.7}$ % with respect to conventional techniques, respectively. It is worth to mention that the quartiles for kNN are all equal to $\mathrm{0.00}$ meters since we have selected online positions that matched those stored in the database.

6. Conclusions

This paper has presented a principled framework and efficient algorithms for unified fingerprinting and ranging localization based on Bayesian filtering. We have defined realistic continuous likelihood functions that adapt to the changing propagation conditions of the wireless channel. We have implemented the proposed framework with efficient algorithms via unscented transform and Gaussian mixture collapse. Under severe NLOS and multipath conditions, the presented techniques have obtained an error in position estimation of $\mathrm{2.39}$ meters along a $\mathrm{120}$ -meter-long path covering fingerprinting-only and ranging-only areas, remarkably outperforming conventional implementations.