Hybrid Fingerprinting-EKF Based Tracking Schemes for Indoor Passive Localization

Abstract

This paper investigates a combination of fingerprinting (FP) and extended Kalman filter (EKF) based tracking aiming to tackle conventional problems related to implementation of either tracking or fingerprinting separately. One of the common drawbacks of FP belongs to large data size and consequent large search space. By taking advantage of latest position estimate got from EKF, a virtual surveillance area (VSA) is defined around the estimate. The dimension of this defined surveillance area is much smaller than the size of indoor environment. Consequently, there will be a possibility for FP to be applied in larger areas maintaining the possibility of adding necessary grid points in order to achieve a desired localization performance. Additionally, in order to improve accuracy of ranging, we investigate the impact of a priori knowledge related to the clusters impulse responses and other features; the applied so called soft ranging algorithm for time of arrival (TOA) estimation is modified in order to take advantage of this a priori information and to make its decision variables more accurate. Simulation results show a promising performance improvement via using the proposed hybrid tracking technique and applying a priori information to soft ranging. The tradeoff is along a reasonable increased implementation complexity.

1. Introduction

Due to recent developments in hardware electronics and communications, wireless personal area networks (WPANs) and wireless sensor networks (WSNs) have found outstanding importance in diverse applications such as industrial, medical, and public services and many other fields. Localization of moving targets inside an indoor environment turns out to be an actual and crucial application in terms of having acceptable precision in the predicted position information of target(s). In order to achieve this goal, a tradeoff between accuracy of the acquired position information (demanding higher complexity from a computational and implementation point of view) and energy efficiency is a significant issue which should be considered.

Estimations of targets’ position can be realized via static localization, tracking, or fingerprinting (FP) [1, 2]. The first two cases are based on the acquisition of distance dependent features from received signals, like received signal strength (RSS) and time of arrival (TOA) via ranging, and then on techniques as trilateration in static localization and extended Kalman filters (EKFs) in tracking. On the other hand, FP takes advantage of location dependent (LD) features of the received signals, exploited as unique signatures associated with the target locations. Firstly, a radio map containing stored LD parameters measured over predetermined points (grid points) is built during an offline or training phase. Subsequently, target position is estimated via pattern matching between ongoing measured LD parameters and those previously recorded (in Section 3.3, a more detailed discussion of FP will be presented).

The main core of the applied tracking strategy is based on [3], which is realized by passive signal receptions that exploit diffused reflections caused by the target(s) (as a passive small scattering object or by means of a backscattering process) during signal propagation. In this paper, we focus on indoor environments where a set of static nodes, called beacons, is used for localizing one or more targets moving in a limited area. The ranging process at each receiving beacon derives measures based on the total reflected paths between each couple of beacons. The tracking algorithm is done by means of a bank of extended Kalman filters (EKFs) and by managing available multiple measures in an appropriate manner. In each EKF update step, time of arrival (TOA) ranging measures resulting from soft ranging (SR) algorithm [4] is applied. Soft ranging outputs a vector of distances with associated likelihoods, instead of a single distance estimate, and hence it is well-suited to perform multiple hypothesis testing with a multifilter system for tracking multiple objects. In [5, 6], a static version of the problem is considered and an algorithm based on Lagrangian relaxation is proposed to solve it. This paper aims to deal with commonly addressed problem related to FP and tracking by proposing a combination of tracking and FP with a fusion mechanism between measures resulting from tracking and FP separately. One of the disadvantages related to FP online phase is the large data size depending on the size of the area under surveillance or on the large number of FP grid points for having better position estimates. This issue limits FP application to small indoor environments or larger areas with largely spaced grid points. To circumvent this drawback, the proposed algorithm defines a virtual surveillance area (VSA) around the latest estimate got from EKF which is much smaller than the original total search area. The FP part of the proposed hybrid algorithm is done over this aforementioned VSA and it is investigated and compared for different signatures, that is, impulse response, intensity profile, power, and duration.

Another contribution of this paper is the hybrid tracking method obtained by applying a measure fusion algorithm between measures from the fingerprinting procedure and measures resulting from the EKF inside the defined VSA. It is shown that the proposed method presents a performance enhancement with respect to the tracking algorithm proposed in [3], especially when tracking two passive targets, a task made really difficult by the ambiguity in the identification of paths clusters scattered by different targets and received overlapped.

Finally, the performance of tracking algorithm in [3] is investigated under the assumption of soft ranging measures enriched by different a priori information (impulse response, intensity profile, power, and duration like in the FP case) and, consequently, with EKF update steps improved by more accurate ranging measures. To the best of our knowledge, the combined impact of a priori channel information in ranging and FP has not been investigated before in the literature for passive and active localization. It should be emphasized that the considered tracking scenario in this work is tracking moving devices not transmitting to the beacons, that is, without energy consumption, since the final objective is to discuss the tracking performance of targets without energy consumption. The proposed hybrid algorithm is applicable for tracking mobile devices that can work as passive scatterers or relays with low or without signal amplification. The possible application areas of this type of algorithm are numerous including, for example, indoor asset localization using low-complexity amplify-and-forward devices and monitoring systems.

The remainder of this work is organized as follows: Section 2 describes the network scenario, Section 3 resumes the proposed tracking algorithm, and Section 4 is dedicated to the numerical results.

2. System Model

The considered network is an asynchronous sensor network containing a constant number of N mobile devices (targets) moving over a limited area and with two-dimensional coordinates $(x,y)$ . Besides, there are a set of fixed nodes called beacons with known coordinates $(x_B(i),y_B(i))$ with $i=\mathrm{1},\dots ,N_B$ . The applied scenario in the analysis is constituted by a bidimensional square area with $N_B=\mathrm{4}$ beacons in the corners, as sketched in Figure 1 (d is the room side). In this sample configuration presented in Figure 1, there are one or two targets moving along related trajectories. Two distinguished targets are shown with circle and square dots. The network has no centralized medium access control. All nodes transmit a single packet, randomly offset in time and with a node specific and globally known preamble, in a standard tracking or localization procedure. Each packet is time-stamped with respect to the local clock at the transmitting node. Afterwards, the beacons cooperatively estimate the unknown positions of the targets. Here, targets do not participate in active exchange of signals except in initial connection of target(s) to WSN. They act as passive scatterers while beacons cooperate for estimating the distance of the reflected path and execute the tracking algorithm described in Section 3. To shed more light on this, this fact is shown in Figure 1 in a way that a sample pairwise connection among the beacon pairs $(\mathrm{2,3})$ and $(\mathrm{1,4})$ is presented for each of the targets shown by circle and square dot, respectively.

Figure 1

A sample presentation of system reference scenario.

2.1. Signal Model

The baseband signal $s_j(t)$ , generated by the jth beacon, is an ultrawide band (UWB) signal constituted by a packet of length $L_{\text{PCK}}$ frames and can be written as

$$\begin{array}{cc}& s_j\left(t\right)={\displaystyle \sum }_{k=\mathrm{0}}^{L_{\text{PCK}}-\mathrm{1}}‍a_{j,k}w(t-k{T}_f-c_{j,k}{T}_c),\end{array}$$

(1)

where $w(t)$ is a root-raised-cosine pulse waveform. $T_f$ is the frame duration and $T_c$ is the chip time. Each frame consists of an integer number $N_c=T_f/T_c$ of chips and each pulse is amplitude modulated (PAM) with polarity $\pm \mathrm{1}$ . The PAM symbol sequences $\{a_{j,k}{\}}_{k=\mathrm{0}}^{L_{\text{PCK}}-\mathrm{1}}$ are chosen randomly in this work. The time-hopping pseudonoise (PN) sequence of node j is represented by $\{c_{j,k}{\}}_{k=\mathrm{0}}^{L_{\text{PCK}}-\mathrm{1}}$ . The UWB pulse has a −3 dB bandwidth of 494 MHz and the roll-off factor is 0.25. We observe that the expected time resolution of the system will be about 2 ns; that is, multipath components closer than 2 ns are indistinguishable at the receiver. The corresponding distance resolution is approximately 0.6 m. All simulations are made at baseband and in discrete time using complex baseband-equivalent channel models adopted by the IEEE 802.15.4a working group [7]. These channels are a low-pass filtered tapped delay-line where signal components arrive at the receiver in independent clusters and they include also path loss components according to LoS or NLoS conditions. Given a couple of beacons at locations $B_i$ and $B_j$ , the presence of a scattering device at location P is modeled by adding all the signal paths that are described by the convolution between the channel impulse response from $B_i$ to P and that from P to $B_j$ (ideal point scatterer or relay).

In our model, we assume that impulse responses generated by a target in two different locations are independent if the distance between these two locations is greater than or equal to a coherence distance $d_C$ . From a practical point of view, the indoor environment is covered by a rectangular grid of points at distances multiple of $d_C$ and the impulse response of a target in a generic location P is obtained by interpolating $\mathrm{4}$ independent impulse responses at the corners of the rectangular area that includes P. The rectangular grid map is depicted in Figure 1. Finally, after passing the channel, the signal is affected by additive white Gaussian noise (AWGN) with zero mean.

2.2. Receiver and Energy Model

We assume that the transmitted pulse waveform $w(t)$ is perfectly known at the receiver, although an extension of our work to unknown pulse-forms is straightforward. Hence, after $I/Q$ demodulation, the receiver is constituted by a filter matched to $w(t)$ and a chip-spaced sampler on each branch. The sampled matched filter outputs are input to a coarse acquisition block, where the presence of a preamble sequence is detected by cross correlation with the known PN sequences. It should be noted that the sampling instants are controlled by the data receiver and not by the ranging algorithm. Thus, the ranging algorithm assumes random chip-spaced sampling. We also note that since the algorithms used in this work operate only on the chip-spaced correlator output samples, a generalization of our work to nodes with different front-ends, for instance, energy detectors, is straightforward.

When a beacon does not transmit, it monitors the received signal and searches for the preambles of the other nodes in the network. When it finds one such preamble, it executes a ranging algorithm for estimating the distance. The necessity of using reflected paths between two beacons instead of directly reflected paths (e.g., between each beacon and the target) depends on the fact that each beacon is generally not able to transmit and receive simultaneously; in this application, due to the indoor short distances, the duration of a packet transmission is often much longer than the propagation time.

3. Algorithm for Zero Energy Localization

The principle exploited in the process is simple; the localization algorithm incorporates two components, ranging and tracking, which are implemented by soft ranging and a bank of $N_{\text{EKF}}$ EKFs. Each couple of beacons, i and j, is interested in the measure of the reflected or relayed path, $d_i+d_j$ (Figure 1). Section 3.1 elaborates the issue related to providing EKF update step by ranging measures with a priori information. Section 3.2 provides a brief review of the basic structure of the tracking strategy considered in this paper, based on [3]. Finally, the proposed hybrid tracking algorithm is introduced in Section 3.3.

3.1. Ranging with A Priori Parameter Knowledge

In this work, we use soft ranging algorithm [4], whose output is composed of a discrete vector of likely distances with an associated approximation of the probability that these distances correspond to the estimates. This soft information is also used to provide a measure of the uncertainty of the distance estimate, that is, an estimate of the error magnitude; in fact, a large uncertainty is often associated with a NLoS measure or with a measure obtained at low signal-to-noise ratio (SNR). The propagation path length between the beacons over a point scatterer at coordinates s is

$$\begin{array}{cc}& d_j\left(\mathbf{s}\right)=‖{\mathbf{x}}_{j,\mathrm{1}}-\mathbf{s}‖+‖{\mathbf{x}}_{j,\mathrm{2}}-\mathbf{s}‖,\end{array}$$

(2)

where $j=\mathrm{1},\dots ,N_M$ ; $N_M=\left(\begin{array}{c}{N}_B\\ \mathrm{2}\end{array}\right)$ . The term $\parallel ·\parallel$ denotes Euclidean norm, and ${\mathbf{x}}_{j,\mathrm{1}},{\mathbf{x}}_{j,\mathrm{2}}\in {\mathbf{R}}^d$ are the transceiver coordinates of the jth pair in $d=\mathrm{2}$ or $d=\mathrm{3}$ dimension. An estimate ${\widehat{d}}_j(s)$ is given by a cluster time of arrival. In general, each transceiver pair will compute several multipath distance estimates.

The commonly made assumption about soft ranging assumes that nodes have no a priori channel state information. However, due to the structure of soft ranging in the formation of decision variables for TOA estimation, it is inferred that when a priori information about some parameters of the signal is available, ranging performance can be improved. The soft ranging is based on the computation of probabilities of presence or absence of signal in a local interval around the early arrived signal paths ( $P_n$ is the probability that no signal component is present at correlator offset n in the local interval with $n=\mathrm{0},\dots ,N_w$ ). These probabilities are used in combination with the a priori information for improving the cluster ranging implementation. Without a priori information, first-path likelihood measure is given by

$$\begin{array}{cc}& l\left(n\right)=\left({\displaystyle \prod }_{j=n-N_w}^{n-\mathrm{1}}‍P_j\right)(\mathrm{1}-P_n)(\mathrm{1}-{\displaystyle \prod }_{j=n+\mathrm{1}}^{n+N_w}‍P_j),\end{array}$$

(3)

where $N_w$ is the window parameter. So an estimated cluster first-path probability vector $\widehat{\mathbf{p}}$ is formed by computing likelihoods $l(n)$ for all correlator offsets in memory and normalizing to unity for each detected cluster of paths. Soft ranging is easily suited to the inclusion of a priori knowledge of some channel parameters for improving the ranging output; the presence of this a priori information can be exploited for the following cases.

• CD:

  the knowledge of the cluster duration allows substituting in (3) the general window $N_w$ with the cluster duration in that area or location $N_{\text{CD}}$ .

• CP:

  the knowledge of the cluster power is used for improving the estimate of $P_n$ , which is computed through the evaluation of noise and signal power. When no a priori knowledge is available, the signal power is estimated by averaging some detected paths.

• CIP:

  the knowledge of the power associated with each path composing the cluster allows refining further the previous point, since a probability of cluster presence is computed by exploiting jointly the signal power in each path. Notice that CIP knowledge includes previous CP and CD knowledge.

• CIR:

  here, the impulse response of the cluster allows changing the probabilistic assumptions done in [3, 4]; in fact, all the received complex samples assume simply a Gaussian distribution with mean value equal to expected signal path and variance given by the noise power. The presence of the cluster is clearly given by the joint probability of these Gaussian variables.

In order to test the potential performance improvement due to ranging with a priori knowledge of some channel parameters, the numerical results will be obtained by using the ideal knowledge of CD, CP, CIP, and CIR, respectively. From a practical point of view, the implementation of such a system can be achieved in two suboptimal ways as follows:

• (1)

  by means of the data stored in the FP grid, during the tracking procedure, it is possible to recover a set of a priori channel parameters according to the target position predicted by the EKFs;

• (2)

  by means of an iterative procedure between the soft ranging algorithm and a conventional channel estimation process, after a first soft ranging estimate without a priori knowledge, an estimate of the channel parameter (CD, CP, CIP, or CIR) is done and it is used as a priori knowledge for a new soft ranging call with the aim of achieving a refined identification of the cluster.

3.2. Tracking Strategies

3.2.1. Mobility Model

In our scenario, the mobile targets move in a delimited area with two-dimensional coordinates $(x,y)$ . The set of $N_B$ beacons have known coordinates $(x_B(i),y_B(i))$ ( $i=\mathrm{1},\dots ,N_B$ ). Trajectories, randomly extracted for deriving the average mean square error (MSE) (or the root mean square error (RMS)), respond to different models (see Section 4). The state equation of the linearized process used in the EKF update is

$$\begin{array}{cc}& {\mathbf{x}}_{\mathbf{k}+\mathbf{1}}=A_k{\mathbf{x}}_{\mathbf{k}}+{\mathbf{w}}_{\mathbf{k}},\end{array}$$

(4)

where ${\mathbf{x}}_{\mathbf{k}}=[x,v_x,a_x,y,v_y,a_y{]}^T$ is the state vector containing the coordinates, the velocity, and the acceleration in both x and y directions. $A_k$ is the state matrix and $w_k$ is a Gaussian noise process with covariance $Q_k$ . Denoting by $T_S$ the sampling rate of the process, we can express the state and the covariance matrices as [8]

$$\begin{array}{cc}& A_k=\left[\begin{array}{cccccc}\mathrm{1}& T_S& \mathrm{0.5}{T}_S^{\mathrm{2}}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{1}& T_S& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{1}& T_S& \mathrm{0.5}{T}_S^{\mathrm{2}}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{1}& T_S\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{1}\end{array}\right],\\ Q_k={\sigma }_w^{\mathrm{2}}\left[\begin{array}{cc}{Q}_{\mathrm{0}}& \mathrm{0}\\ \mathrm{0}& Q_{\mathrm{0}}\end{array}\right]\end{array}$$

(5)

with

$$\begin{array}{cc}& Q_{\mathrm{0}}=\left[\begin{array}{ccc}\frac{T_S^{\mathrm{5}}}{\mathrm{20}}& \frac{T_S^{\mathrm{4}}}{\mathrm{8}}& \frac{T_S^{\mathrm{3}}}{\mathrm{6}}\\ \frac{T_S^{\mathrm{4}}}{\mathrm{8}}& \frac{T_S^{\mathrm{3}}}{\mathrm{3}}& \frac{T_S^{\mathrm{2}}}{\mathrm{2}}\\ \frac{T_S^{\mathrm{3}}}{\mathrm{6}}& \frac{T_S^{\mathrm{2}}}{\mathrm{2}}& T_S\end{array}\right].\end{array}$$

(6)

The process is completed by the observation model, that is, the relation between the observations, in the vector ${\mathbf{z}}_{\mathbf{k}}$ , and the state vector and it is defined as

$$\begin{array}{cc}& {\mathbf{z}}_{\mathbf{k}}=H\left(k,{\mathbf{x}}_{\mathbf{k}}\right)+{\mathbf{v}}_{\mathbf{k}},\end{array}$$

(7)

where ${\mathbf{v}}_{\mathbf{k}}$ is the Gaussian noise with covariance $R_k$ . With $N_B$ beacons, we will have $N_M=N_B$ measures per target and

$$\begin{array}{cc}& N_M=\left(\begin{array}{c}{N}_B\\ \mathrm{2}\end{array}\right).\end{array}$$

(8)

So, at the kth update step of each EKF, the set of measures, accumulated by the ranging phase, is passed to the EKF. If we denote $\{{\widehat{x}}_k^{-},{\widehat{y}}_k^{-}\}$ as the predicted coordinates of the target position, the Jacobian matrix of measurement functions H with the dimension of ( $N_M\times \mathrm{6}$ ) can be shown as

$$\begin{array}{l}{h}_k\left(i,\mathrm{1}\right)=\frac{{\widehat{x}}_k^{-}-x_B\left(c_{i,\mathrm{1}}\right)}{\sqrt{{\left({\widehat{x}}_k^{-}-x_B\left(c_{i,\mathrm{1}}\right)\right)}^{\mathrm{2}}+{\left({\widehat{y}}_k^{-}-y_B\left(c_{i,\mathrm{1}}\right)\right)}^{\mathrm{2}}}}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}+\frac{{\widehat{x}}_k^{-}-x_B\left(c_{i,\mathrm{2}}\right)}{\sqrt{{\left({\widehat{x}}_k^{-}-x_B\left(c_{i,\mathrm{2}}\right)\right)}^{\mathrm{2}}+{\left({\widehat{y}}_k^{-}-y_B\left(c_{i,\mathrm{2}}\right)\right)}^{\mathrm{2}}}},\\ h_k\left(i,\mathrm{2}\right)=\frac{{\widehat{y}}_k^{-}-y_B\left(c_{i,\mathrm{1}}\right)}{\sqrt{{\left({\widehat{x}}_k^{-}-x_B\left(c_{i,\mathrm{1}}\right)\right)}^{\mathrm{2}}+{\left({\widehat{y}}_k^{-}-y_B\left(c_{i,\mathrm{1}}\right)\right)}^{\mathrm{2}}}}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}+\frac{{\widehat{y}}_k^{-}-y_B\left(c_{i,\mathrm{2}}\right)}{\sqrt{{\left({\widehat{x}}_k^{-}-x_B\left(c_{i,\mathrm{2}}\right)\right)}^{\mathrm{2}}+{\left({\widehat{y}}_k^{-}-y_B\left(c_{i,\mathrm{2}}\right)\right)}^{\mathrm{2}}}},\end{array}$$

(9)

for the ith pair $\{c_{i,\mathrm{1}},c_{i,\mathrm{2}}\}$ of beacons (Figure 1). The other elements of H turn out to be zero.

3.2.2. Track Initialization

In our scenario, we assume the following.

• (i)

  The initial position estimate and the identification of the target are performed by exchanging dedicated packets between the beacons and the target. So, the initial connection of the target to the WSN is operated with an active cooperation of the target itself. After this initial step, the target switch-off and tracking is performed exploiting scattering caused by target. This initial “active” phase has the following clear advantage in the sense that the set of beacons not only know the number of targets in the environment but also obtain a precise position estimate of the first trajectory sample.

• (ii)

  When the number of targets is greater than $\mathrm{1}$ , they are initially divided uniformly among all the available $N_{\text{EKF}}$ EKFs. So, each target is initially assigned to an equal number of EKFs.

3.2.3. Filter Update

Due to the aforementioned nature of soft ranging producing multiple ranging estimates with corresponding likelihoods, there will be a number of more or less likely first cluster-path distance estimates for each beacon pair during each measurement cycle. Consequently, each EKF must select one estimate from each beacon pair in a possibly large number of different estimates with varying likelihood values. A metric is built and updated for selecting the most likely trajectories in a hypothesis tree that is updated at each step of the tracking process. Let us define a selection ${\tilde{\mathbf{Z}}}_n^{(k)}=[{\widehat{d}}_{\mathrm{1}}^{(k)},\dots ,{\widehat{d}}_J^{(k)}]$ as a possible set of distance estimates to use for updating the nth filter at update cycle k. In order to evaluate the merits of this selection and compare it to other different sets of estimates, we want to evaluate the probability $P({\tilde{\mathbf{Z}}}_n^{(k)}\mid {\mathbf{r}}^{(k)},{\mathbf{X}}_n^{(k-\mathrm{1})})$ , that is, the probability that distances in ${\tilde{\mathbf{Z}}}_n^{(k)}$ , conditioned on the received signals ${\mathbf{r}}^{(k)}$ and the previous filter state ${\mathbf{X}}_n^{(k-\mathrm{1})}$ , are estimates of multipath distances corresponding to the object currently tracked by filter n. If we assume that the received signals and the last filter state are statistically independent and apply Bayes’ rule, we can write

$$\begin{array}{l}P\left({\tilde{\mathbf{Z}}}_n^{\left(k\right)}\mid \mathbf{r},{\mathbf{X}}_n^{(k-\mathrm{1})}\right)=\frac{P\left(\mathbf{r}\mid {\tilde{\mathbf{Z}}}_n^{\left(k\right)},{\mathbf{X}}_n^{(k-\mathrm{1})}\right)P\left({\tilde{\mathbf{Z}}}_n^{\left(k\right)},{\mathbf{X}}_n^{(k-\mathrm{1})}\right)}{P\left(\mathbf{r}\right)P\left({\mathbf{X}}_n^{(k-\mathrm{1})}\right)}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{1em}\hspace{1em}\hspace{0.17em}=\frac{P\left(\mathbf{r}\mid {\tilde{\mathbf{Z}}}_n^{\left(k\right)}\right)·P\left({\tilde{\mathbf{Z}}}_n^{\left(k\right)}\mid {\mathbf{X}}_n^{\left(k-\mathrm{1}\right)}\right)}{P\left(\mathbf{r}\right)}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{1em}\hspace{1em}\hspace{0.17em}=\frac{P\left({\tilde{\mathbf{Z}}}_n^{\left(k\right)}\mid \mathbf{r}\right)·P\left({\tilde{\mathbf{Z}}}_n^{\left(k\right)}\mid {\mathbf{X}}_n^{(k-\mathrm{1})}\right)}{P\left({\tilde{\mathbf{Z}}}_n^{\left(k\right)}\right)}.\end{array}$$

(10)

Now, $P({\tilde{\mathbf{Z}}}_n^{(k)}\mid \mathbf{r})$ can be interpreted as the probability that distance estimates in ${\tilde{\mathbf{Z}}}_n^{(k)}$ really corresponds to first cluster-path distances (as opposed to that generated by noise or located in the middle of a cluster). This factor can therefore be approximated by $P({\tilde{\mathbf{Z}}}_n^{(k)}\mid \mathbf{r})={\prod }_{j=\mathrm{1}}^{\mathrm{6}}‍{\widehat{\mathbf{p}}}_j^{(k)}(i_j)$ , where $i_j$ is the index in ${\mathbf{p}}_j^{(k)}$ corresponding to the estimate from jth pair in ${\tilde{\mathbf{Z}}}_n^{(k)}$ . The factor $P({\tilde{\mathbf{Z}}}_n^{(k)})$ is a normalization term, while $P({\tilde{\mathbf{Z}}}_n^{(k)}\mid {\mathbf{X}}_n^{(k-\mathrm{1})})$ can be evaluated by means of the Gaussian assumption used in the motion model of the EKF filters [9]. If we let the estimated a priori error covariance matrix of the nth EKF be ${\mathbf{S}}_n^{(k\mid k-\mathrm{1})}$ , we can write

$$\begin{array}{l}P\left({\tilde{\mathbf{Z}}}_n^{\left(k\right)}\mid {\mathbf{X}}_n^{\left(k-\mathrm{1}\right)}\right)\\ \hspace{1em}=\frac{\mathrm{1}}{\sqrt{{\left(\mathrm{2}\pi \right)}^{\mathrm{6}}\left|{\mathbf{S}}_n^{(k\mid k-\mathrm{1})}\right|}}\\ \hspace{1em}\hspace{0.5em}·\exp \left(-\frac{\mathrm{1}}{\mathrm{2}}{\left({\tilde{\mathbf{Z}}}_n^{\left(k\right)}-{\mathbf{Z}}_n^{(k\mid k-\mathrm{1})}\right)}^T{\mathbf{S}}_n^{(k\mid k-\mathrm{1}{)}^{-\mathrm{1}}}({\tilde{\mathbf{Z}}}_n^{\left(k\right)}-{\mathbf{Z}}_n^{(k\mid k-\mathrm{1})})\right),\end{array}$$

(11)

where ${\mathbf{Z}}_n^{(k\mid k-\mathrm{1})}$ is a vector of predicted multipath distances at the nth EKF. Each EKF in the filter bank has an associated figure of merit ${\tilde{\lambda }}_n^{(k)}$ that measures how well the nth filter has tracked its intended target until kth step in the hypothesis tree. By computing this metric for all possible measurement combinations ${\tilde{\mathbf{Z}}}_n^{(k)}$ , we can select which measurements to use for filter update. The figure of merit for a given measurement combination is given by [3]

$$\begin{array}{cc}& {\lambda }_n^{\left(k\right)}={\lambda }_n^{(k-\mathrm{1})}-{\left({\tilde{\mathbf{Z}}}_n^{\left(k\right)}-{\mathbf{Z}}_n^{\left(k\mid k-\mathrm{1}\right)}\right)}^T·\left({\tilde{\mathbf{Z}}}_n^{\left(k\right)}-{\mathbf{Z}}_n^{\left(k\mid k-\mathrm{1}\right)}\right),\end{array}$$

(12)

where ${\lambda }_n^{(k-\mathrm{1})}$ is the current figure of merit of the nth EKF (at startup, all figures of merit are initialized as ${\lambda }_n^{(\mathrm{0})}=\mathrm{0}$ ). The term $N_M$ , as previously defined, is the number of measures per target at each EKF update step; ${\mathbf{Z}}_n^{(k\mid k-\mathrm{1})}$ is a vector of predicted multipath distances at the nth EKF. According to the figure of merit defined in (12), the following filter assignment and update strategy is applied for a bank of $N_{\text{EKF}}$ EKFs; the $N_{\text{EKF}}$ measurement combinations and filter states with highest merit are reassigned to the corresponding filters. This means that an EKF can at any time be reinitialized to a new trajectory.

3.3. Hybrid Fingerprinting and EKF Based Tracking

The strategies for passive tracking suffer from several problems related primarily to the low SNR levels and the large delay spread of clusters. Additionally, in case of multiple tracking, the difficulty of associating the measured distances with the correct target and hence the correct EKF is of great importance. In fact, when different targets are close to each other, the presence of multipath creates severe ambiguities since paths clusters, scattered by different targets’ overlap, make the correct discrimination among measures very challenging. In order to enhance robustness of the tracking algorithms, we introduce a hybrid tracking algorithm by means of a fusion strategy between two measurements of fingerprinting and the conventional tracking.

Conventional localization algorithm using signal information like time of arrival (TOA), received signal strength (RSS), angle of arrival (AOA), and time difference of arrival (TDOA) faces a serious performance degradation in indoor environments affected by phenomena like harsh multipath and nonline of sight (NLOS). Taking advantage of location dependent (LD) features of signal, there can exist a radio map containing LD parameters measured in predetermined points called grids so that target position can be estimated using pattern matching algorithms. Fingerprinting contains two basic steps: in the first step, which is called offline phase, LD parameters of signal are measured in a grid based map over surveillance area in order to be used as a reference in the second phase of FP called online phase in which target position is estimated by pattern matching between ongoing measurement of LD parameters and stored LD parameters in offline phase. The most common LD parameter is received signal strength (RSS). However, due to high temporal resolution of UWB signals, application of UWB CIR or some of its features has been reported in literature [10–14]. In [10], authors propose CIR as LD metric during FP. For pattern matching required for FP, a parameter called channel spatial correlation is introduced. The target position is estimated by maximizing channel spatial correlation over FP grid points. However, due to imperfection in CIR estimation, a threshold is required to be set in order to consider reasonable spatial correlations in pattern matching. In [11], channel impulse response is used as location dependent parameter. There is one fixed receiver recording CIR data collected from different location of a transmitter over different geometrical region during training (offline phase) of FP. Using a complex Gaussian distribution assumption for channel taps corresponding to a specific region, sample mean and covariance matrix is estimated over multiple observation of CIR over a specific area. In order to align measured CIRs, strongest path is considered by taking maximum absolute value. Besides, some simplifying assumptions including zero mean assumption and independent channel taps leading to a diagonal covariance matrix are considered. According to binary hypothesis testing, a probabilistic metric as a result of Gaussian assumption is built for two regions in order to map the location of transmitter. For existence of more than two regions, a pairwise selection among regions and a consequent computation of proposed metrics for each pair should be taken into account. In [12], CIR is applied as a location dependent signature of a transmitter. More specifically, they are using average power delay profile (APDP) of CIR for region decision. Their considered scenario contains one receiver in the way that receiver location is fixed and then a test transmitter is located in different regions. In training phase, multiple CIR PDP measurements are stored in the database. However, localization accuracy can be increased by increasing number of receivers as in the case of time dependent ranging techniques. Assuming the outcome of statically independent Gaussian random variables for APDP of different regions and using a maximum likelihood estimator, the position of transmitter is determined. In [13], they use a subcategory of CIR features including the mean excess delay, the rms delay spread, the maximum excess delay, the total received power, the number of multipath components, the power of the first path, and the arrival time of the first path of the channel as LD parameters. For the pattern matching part of the FP, an artificial neural network (AAN) based algorithm is proposed by which transmitter position is estimated. Reference [14] presents a pervasive review of existing fingerprinting techniques for both active and passive localization.

One of the simplest mapping techniques is the selection of target coordinates based on the coordinates of FP grid point leading to minimum Euclidean distance between measured LD metric and the metric related to that specific FP grid point measured during FP offline phase. To elaborate, let us assume that the number of LD measures is $N_M$ . For the sake of simplicity in mathematical representation, LD metric is assumed to be scalar although extension to the case, where LD parameter is a vector, is straightforward. During the offline phase of FP, the LD metric vector ${\mathbf{M}}_{{\mathbf{p}}_{\mathbf{i}}}$ ( $N_M\times \mathrm{1}$ ) is measured at each point of FP grid ( $p_i$ ) and stored in a database. Consequently, target position is estimated based on minimizing the following Euclidean distance over grid points:

$$\begin{array}{cc}& \underset{\left\{p_i\right\}}{\text{Arg}\hspace{0.17em}\min }\hspace{0.17em}\hspace{0.17em}‖\mathbf{M}-{\mathbf{M}}_{{\mathbf{p}}_{\mathbf{i}}}‖,\end{array}$$

(13)

where M is the LD metric vector measured in online phase of FP. Here, applied LD metrics are the same parameters related to a priori information in ranging and can be mentioned from the least to the most effective as

• (i)

  knowledge of the cluster duration (CD),

• (ii)

  knowledge of the cluster power (CP),

• (iii)

  knowledge of the cluster intensity profile (CIP), that is, the mean power of the resolvable paths composing the cluster,

• (iv)

  knowledge of the cluster impulse response (CIR), that is, the amplitudes and phases of the resolvable paths composing the cluster.

A square virtual surveillance area (VSA) is defined around the latest target position estimate got from EKF. Assuming ${\left[\begin{array}{cc}\widehat{x}& \widehat{y}\end{array}\right]}^T$ as target position estimate, the square surveillance area is defined with four vertices ${\left[\begin{array}{cc}\widehat{x}\pm \text{F}{\text{P}}_r& \widehat{y}\pm \text{F}{\text{P}}_r\end{array}\right]}^T$ , where $\text{F}{\text{P}}_r$ is the expansion of surveillance area. The vertex coordinate, exceeding room dimensions in x or y or both axes’ direction, will be replaced with corresponding room coordinates. Let us assume that the number of FP grid points, which fall inside VSA, is $i_x·i_y$ , where $i_x$ and $i_y$ are the number of the coordinates of $\text{FP}$ grid points along x- and y-axis, respectively. For each of the grid points inside VSA, two Euclidean distances are independently computed. The first distance parameter is related to conventional calculated Euclidean distance ( $d_{\text{FP}}$ ) between measured LD metric and that stored in FP offline phase. The second distance parameter ( $d_{\text{EKF}}$ ) is the Euclidean distance between target position estimate via EKF and coordinate of each of FP grid points in the surveillance area.

Considering two mentioned Euclidean distances to be computed for each of the grid points, there will be $N_{\text{FP}}=i_x·i_y$ values for each of Euclidean distances. For each grid point $p_i$ with the coordinate ${\left[\begin{array}{cc}{x}_{p_i}& y_{p_i}\end{array}\right]}^T$ and related FP metric ${\mathbf{M}}_{{\mathbf{p}}_{\mathbf{i}}}$ , two Euclidean distances $d_{\text{FP}}^{(i)}$ and $d_{\text{EKF}}^{(i)}$ are defined as

$$\begin{array}{cc}& d_{\text{FP}}^{\left(i\right)}=‖\mathbf{M}-{\mathbf{M}}_{{\mathbf{p}}_{\mathbf{i}}}‖,\\ d_{\text{EKF}}^{\left(i\right)}=‖\begin{array}{c}\widehat{x}-x_{p_i}\\ \widehat{y}-y_{p_i}\end{array}‖,\end{array}$$

(14)

where $i=\mathrm{1},\dots ,N_{\text{FP}}$ .

Assuming a Gaussian distribution and considering the fact that $d_{\text{FP}}^{(i)}$ and $d_{\text{EKF}}^{(i)}$ are independent, for each grid point $p_i$ , two independent probability metrics, that is, $P_{\text{FP}}^{(i)}$ and $P_{\text{EKF}}^{(i)}$ , can be assigned which are exponential function of two distances $d_{\text{FP}}^{(i)}$ and $d_{\text{EKF}}^{(i)}$ , receptively. It should be mentioned that, after computation of probability metrics for all grid points, they are normalized. Afterward, final decision variable is calculated as $P_i=P_{\text{FP}}^{(i)}·P_{\text{EKF}}^{(i)}$ . The grid location with highest $P_i$ will be considered as target position estimate. This estimate will be passed as a priori estimate to the next EKF update step.

4. Numerical Results

The physical parameters of the transmission are taken from the UWB technology. The standard pulse has a reference bandwidth of 512 MHz and the propagation exponent is fixed to a value of $\gamma =\mathrm{1.79}$ according to residential line-of-sight UWB channel model (channel model $\text{CM}=\mathrm{1}$ ). Each receiver noise figure is fixed to 7 dB and each node respects the UWB transmission power spectral density of −41.3 dBm/MHz. In this test scenario, we exploit ranging algorithms based on the times of arrival and characterized by soft detection techniques that have demonstrated performance advantages with respect to other approaches. Numerical results present the effect of the proposed tracking algorithm on localization error (i.e., the distance ϵ between estimated and correct points at each algorithm step).

The reference scenario is a square room with room side $d=\mathrm{30}$  m and the number of beacons is fixed to $N_B=\mathrm{4}$ at the room corners as a typical localization environment. Each LoS link is modeled by the IEEE 802.15.4a residential channel models ( $\text{CM}=\mathrm{1}$ ). The transmitted signal (1) experiences a channel that is obtained by the convolution between the channel realizations corresponding to the links between beacon a and the target and between the target and the beacon b that is supposed to receive the signal (1) (in a selected beacon pair $(a,b)$ ). This approach provides the approximate impact on the propagation of a target that can be assumed as a small (point) scatterer or as a passive relay without signal amplification (e.g., exploiting backscattering mechanisms). As previously mentioned, the path loss parameters are taken according to residential LoS parameters (i.e., propagation exponents $\gamma =\mathrm{1.79}$ [7]). The path loss model of the overall reflected path is computed in the simulations according to [15]. The number $L_{\text{PCK}}$ of pulses in a packet is $\mathrm{32}$ and all antenna gains are set to 0 dB. At each simulation, the set of 100 trajectories is used for averaging all the location errors. The localization algorithm is supposed to obtain distance measures corresponding to a sampling time $\Delta T=\mathrm{1}$  s on one (two) target(s) moving with a random walk model:

$$\begin{array}{cc}& x_k=x_{k-\mathrm{1}}+v·\cos \left({\alpha }_k\right)\Delta T,\\ y_k=y_{k-\mathrm{1}}+v·\sin \left({\alpha }_k\right)\Delta T,\end{array}$$

(15)

with ${\alpha }_k={\alpha }_{k-\mathrm{1}}+\delta$ and δ zero mean Gaussian random variable with ${\sigma }_{\delta }^{\mathrm{2}}$ within an observation time equal to 45 s. We will show a set of selected, significant figures reporting the cumulative distribution function (CDF) of the localization error. For simplicity, the ranging technique is referred to as $\text{SR}+\text{APR}$ (soft ranging) or $\text{TR}+\text{APR}$ (threshold ranging) with a priori information $\text{APR}=\{\text{CIP},\text{CD},\text{CP},\text{CIR}\}$ ; on the other hand, the fingerprinting process, when present in addition to the EKFs bank, is referred to as $\text{FP}[\text{SG}]$ with signature $\text{SG}=\{\text{CIP},\text{CD},\text{CP},\text{CIR}\}$ .

Figure 2 depicts the CDF of the distance error for the localization with ranging enriched by a priori information and without the FP scheme. As expected, using a priori information related to knowledge of cluster impulse response (CIR) or cluster intensity profile (CIP) shows a relevant advantage since this knowledge allows increasing the amount of received energy available for the cluster identification; little or no advantage can be observed for $\text{SR}+\text{CD}$ and $\text{SR}+\text{CP}$ since the ranging algorithm still estimates locally these parameters for detecting its first path. Similar results are obtained for threshold ranging (TR) in which the CIR and CIP cases coincide (Figure 4). On the other hand, Figure 3 presents the error CDFs by using the proposed FP scheme associated with the absence (left) and with the presence (right) of the best a priori information (CIR in Figure 2). As expected, $\text{FP}[\text{CIR}]$ and $\text{FP}[\text{CIP}]$ show the best performance advantage due to taking advantage of cluster complete information, that is, impulse response even if when no a priori information for ranging is present during tracking. In the error interval of interest, depending on the type of signature, we generally observe a performance improvement that increases with complexity; here, also the cases $\text{FP}[\text{CP}]$ and $\text{FP}[\text{CD}]$ can provide a remarkable improvement since one of the main performance key factors is the inclusion of the path delay in each FP signature, which provides a windowing effect on the estimated signatures. In fact, each point of the grid obviously contains also the distance and hence propagation delay information and this assists the fusion between the outputs of the EKFs and the correct positions. The synergy related to interaction of the EKF based tracking and the FP process is observable in Figure 3. Also the synergy between a priori information in ranging and the FP process can be observed comparing the left and right figures in Figure 3. Similar considerations can be derived from the threshold ranging case, reported in Figure 5.

Figure 2

CDF of localization error when tracking a single scatterer ( ${\sigma }_{\delta }=\pi /\mathrm{15}$ ) using soft ranging with one EKF and no FP.

Figure 3

CDF plots of localization error when tracking a single scatterer ( ${\sigma }_{\delta }=\pi /\mathrm{15}$ ) using soft ranging SR or $\text{SR}+\text{CIR}$ with one EKF and FP.

Figure 4

CDF of localization error when tracking a single scatterer ( ${\sigma }_{\delta }=\pi /\mathrm{15}$ ) using threshold ranging with one EKF and no FP.

Figure 5

CDF plots of localization error when tracking a single scatterer ( ${\sigma }_{\delta }=\pi /\mathrm{15}$ ) using threshold ranging TR or $\text{TR}+\text{CIP}$ with one EKF and FP.

Figure 6 depicts CDF of the distance error obtained from passive tracking of two scatterers without using the FP scheme. As for one target, using a priori information related to knowledge of CIR and CIP provides an advantage. At the same time, it is clear that when two objects are present in the environment, the average performance is considerably decreased by phenomena of ambiguity between the overlapping cluster signals received by passive reflections by the objects (see Figure 2). Figure 7 presents CDFs of the distance error for two scatterers by using the proposed FP schemes without any a priori information (left) and with the best CIR a priori information. Here, it is interesting to see that FP provides little advantage in the small error region (when localization is successful without ambiguity) in either absence (left) or presence (right) of SR with a priori information, pointing the main issue of occurring ambiguity between multiple targets when localization is performed in a passive way. It is important to remark that if, at a certain tracking step, one target is associated with the trajectory of the other and vice versa, the simulated performance will return an error since the position error is computed requiring all the points of a target be coherent only with a single trajectory. This has an impact on performance since, without an active transmission that identifies the targets without ambiguities, a mutual exchange of trajectories can occur particularly after the trajectory crossings. The rationale behind this part of the simulations is to test the impact of the signatures at the ranging EKF and FP levels in presence of a severe scenario with likely targets’ ambiguity. Of course, performance is affected by the association method chosen for assigning the measures to the targets and consequently to the trajectories; however, here, we are interested specifically to the contribution in discriminating different targets given by the a priori information at the ranging step and by different FP signatures. So we have limited the data association procedure to the multiple hypothesis tree for cluster assignment in the EKF filter bank described in Section 3.2.3; in fact, at least this step is strictly necessary since the number of EKFs is much lower than the typical number of clusters detected by the ranging algorithm. At the same time, the FP part is left purposely independent from this assignment, made at the EKF step, in order to measure the potential, additional discriminating information given by the signatures in the FP part. To this end, we may observe that FP does not provide a relevant advantage since, in a small environment, the mutual interference between targets’ signals affects negatively the search and association of the signatures; on the other hand, improving the ranging algorithm by using the most advanced forms of a priori information (cluster multipath response or intensity profile) can give an important performance improvement since the initial ranging level of the localization procedure. Starting from this performance basis, the potential enhancement of more advanced multiple targets association methods and of their different combinations in the ranging EKF and FP parts is still an open issue for future research.

Figure 6

CDF plot of localization error when tracking two scatterers ( ${\sigma }_{\delta }=\pi /\mathrm{15}$ ) using soft ranging with two EKFs and no FP.

Figure 7

CDF plots of localization error when tracking two scatterers ( ${\sigma }_{\delta }=\pi /\mathrm{15}$ ) using soft ranging SR or $\text{SR}+\text{CIR}$ with two EKFs and FP.

Figure 8 reports the computational time in our simulations corresponding to three different categories of localization with EKF based tracking (no FP), FP (without EKF), and the hybrid tracking for all points of trajectories versus different increasing values of the VSA side. The VSA side varies between 1 and 12 m. As expected, the EKF based tracking has a fixed computational time over different VSA sides. On the other hand, FP (without EKF) shows an increasing behavior for the computational time as the VSA side increases since a greater VSA side means an increased number of states in the search space and hence an increased computational time. The reported computational time for FP (without EKF) corresponds to the application of CP and CIP as illustrative examples of applied FP metrics. Interestingly, comparing the computational time of FP (without EKF) and EKF based tracking, we observe that computational time of EKF based tracking is much lower than that of FP (without EKF). Other curves depict the computational time for the hybrid algorithm with the same applied LD metrics in FP (without EKF), that is, CP and CIP. Primarily, it is observed that computational time of the hybrid algorithm presents an increasing trend with respect to increasing VSA side due to the FP part of the hybrid algorithm. More importantly, its computational time is almost the same as that of FP (without EKF) confirming the negligible role of EKF in the hybrid algorithm from a computational time point of view.

Figure 8

Computational time of localization with EKF based tracking (no FP), FP (without EKF), and the hybrid algorithm. Dashed curves (w/o EKFs) cannot be seen because they are approximately equal to the corresponding continuous ones (with EKFs).

5. Conclusions

In this paper, we have investigated two ways for improving performance of passive tracking: (i) use of a priori information for enhancing ranging quality and (ii) hybrid tracking achieved by a combination of standard EKFs and fingerprinting techniques based on different channel signatures. In fact, due to structure of soft ranging, which can take advantage of some a priori information about cluster parameters, the use of a priori information can improve the ranging measure, hence leading to a better localization performance. More importantly, the proposed hybrid tracking technique composed of a fingerprinting stage and its fusion with the measures resulting from EKFs shows a remarkable performance enhancement in all the cases with a single target. On the other hand, in the scenarios with more than one target and passive localization, ranging performance can be improved with a positive impact on the EKF stage while FP signatures do not enhance the solution of ambiguities in associating the ranging measures with the different targets especially at critical points when the targets intersect each other's trajectory or when they are too close as in small environments. This fact is particularly evident since here each target acts as a passive scatterer as in a typical radar scenario and specific, additional techniques should be adopted for limiting the impact of these ambiguities.