Estimating Directional Data From Network Topology for Improving Tracking Performance

Abstract

This work proposes a novel approach for tracking a moving target in non-line-of-sight (NLOS) environments based on range estimates extracted from received signal strength (RSS) and time of arrival (TOA) measurements. By exploiting the known architecture of reference points to act as an improper antenna array and the range estimates, angle of arrival (AOA) of the signal emitted by the target is first estimated at each reference point. We then show how to take advantage of these angle estimates to convert the problem into a more convenient, polar space, where a linearization of the measurement models is easily achieved. The derived linear model serves as the main building block on top of which prior knowledge acquired during the movement of the target is incorporated by adapting a Kalman filter (KF). The performance of the proposed approach was assessed through computer simulations, which confirmed its effectiveness in combating the negative effect of NLOS bias and superiority in comparison with its naive counterpart, which does not take prior knowledge into consideration.

1. Introduction

Tracking a mobile target is important in many practical applications, such as autonomous surveillance, search-rescue, robotic navigation, and wildlife monitoring, to name a few [1,2,3,4,5,6,7,8,9,10,11,12,13]. Besides striving towards accurately attaining this goal, another important requirement is to do so while maintaining low implementation cost. Therefore, taking advantage of already installed technological solutions, such as terrestrial radio frequency founts, is highly supported. These include received signal strength (RSS) [14,15,16,17], time of arrival (TOA) [18,19,20,21,22], angle of arrival (AOA) [23,24,25], or perhaps an amalgamation of them [16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36].

Target localization and tracking problems have lured great attention in the research community lately. The authors of refs. [3,4,5,7,8,10,13,15,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36] considered only a classical problem of target localization in wireless sensor networks (WSNs), where the authors disregarded completely any previous knowledge and awarded all significance to measurements exclusively. The authors of refs. [27,28] studied the problem of range estimation founded on RSS and TOA contents. In refs. [34,35,36], the target localization problem in a mixture of line-of-sight (LOS)/non-line-of-sight (NLOS) environments is addressed. The authors of ref. [34] started by identifying the type of path for each link based on Nakagami distribution, after which they derived a weighted least squares (WLS) estimator that makes use of TOA-only/RSS-only observations if the link is recognized as LOS/NLOS, respectively. A sequential squared range WLS estimator is presented in ref. [35]. The authors of ref. [35] partially mitigated the harmful impact of NLOS biases by managing to approximate all NLOS biases by a lone (mean) variable, after which an intermittent process was applied to obtain an estimate the location of the target. In ref. [36], the authors took into account a worst-case setting where it was assumed that every link in the network is NLOS. Founded on this, as well as the presumption that (imperfect) knowledge about the magnitude of the NLOS bias is available, they deduced a min-max problem from which a robust estimator written in a generalized trust region sub-problem structure was derived. The works in refs. [16,37,38] consider the problem of tracking a moving target, where the measurements are integrated with some previously accumulated knowledge to complement the localization precision. Nevertheless, all of these works investigate only target tracking problem based on RSS solely. The authors of ref. [14] studied the problem of tracking a moving target by incorporating hybrid, RSS and AOA, observations. The solution proposed for such a problem in ref. [14] is based on a Kalman filter (KF). For this purpose, it is assumed that sensors are equipped with suitable hardware to measure AOA. Besides the referred schemes designed particularly for RSS- and RSS-AOA-based target tracking, several other classical approaches (fundamentally nothing else but alterations of the KF) can be found in the literature nowadays. Among others, these include the extended KF (EKF) [39,40,41,42,43,44,45], which does not require any presumptions regarding the linearity of the state or measurement models. Alternatively, EKF approximates these non-linear models by the use of the first-order Taylor series expansion. Nonetheless, this implies calculating the Jacobian matrix, which can be arduous or sometimes even not feasible. Another popular modification is unscented KF, which is based on unscented transformation. This transformation is based on the rationale that it is easier to approximate a probability distribution than it is to approximate an arbitrary non-linear function or transformation [46]. The key concept here is to represent the state distribution by a least possible set of thoughtfully chosen motes, also known as sigma points. The sigma points entirely apprehend both mean and covariance of the distribution, thus, even after they are fed into the original (non-linear) model, they can still seize the mean and covariance up to the third order (Taylor series extension) for any non-linearity [46,47,48]. Analogously with the unscented KF, particle filter (PF) tends to capture the posterior probability distribution function (PDF) of the state through sample motes, referred to as particles. However, the main distinction between the two methods is that the particles are chosen randomly, and usually, high number of particles is used. Basically, a particle filter is nothing else but an ordinary randomization scheme and its performance, as well as its computational burden, highly depend on the number of particles employed [14,37]. The particles are sequentially re-sampled based on latest measurements. Similar to the previous two extensions, particle filters do not require linearity or Gaussianity presumptions [48,49]. Furthermore, the authors of refs. [1,43,50] investigated the problem of tracking a moving target with mobile sensors. Lastly, in ref. [51,52], the authors considered the target tracking problem based on fused RSS and TOA measurements. More specifically, a PF is proposed in ref. [51], whereas an EKF is presented in ref. [52].

The main contribution of this work is threefold. We show how to obtain an estimate of the AOA of the incoming radio signal without the necessity of any additional hardware, such as a directional antenna or an antenna array, which could severely raise the financial cost of the network. This is done by using range estimates extracted from RSS and TOA measurements, as well as exploiting the known topology of the available reference points to play the role of an irregular antenna array. In this way, we form triangles between a pair of anchors and the target, and use the law of cosines to estimate the angle information. Next, we also show how to make use of the estimated AOA information to effortlessly approximate the highly non-linear measurement model by a linear one. This is accomplished by applying Cartesian to polar coordinates conversion, which allows us to tackle the problem in a more suitable space given that AOA information is available. Finally, we show how to incorporate prior knowledge acquired during the target’s movement on top of the derived linear model, which results in an efficient tracking algorithm. This is achieved by applying Bayesian methodology and adapting KF equations. Hence, in huge contrast to the existing RSS and TOA tracking algorithms [51,52], the new one takes advantage of the network topology to gather extra information about the AOA of the received signal. Note that this is also in sharp contrast to the RSS-AOA tracking algorithm presented in ref. [43], where the authors assumed that anchors are conveniently equipped with additional hardware in order to measure the AOA quantity of the received signal. Moreover, instead of employing a high number of particles [51] or calculating the Jacobian matrix [52], which can considerably elevate the computational burden, the proposed approach is based on linearizing the measurement models by the use of estimated AOA information, which makes it very light in terms of computational cost.

The current work is assembled as follows. Section 2 introduces the measurement model together with the target state transition model, and formulates the target tracking problem based on a Bayesian methodology. In Section 3, the proposed technique to estimate the AOA information of the received radio signal at each anchor is described. Section 4 shows how to make use of the additional AOA information in order to linearize the measurement model on top of which prior knowledge can easily be incorporated by means of adapting KF equations. In Section 5, simulation results for a fairly complex target trajectory are presented with the objective of validating the performance of the new approach. Lastly, Section 6 abridges the main findings of the work and identifies some possible directions of our future work.

2. Problem Formulation

Let us consider a two-dimensional WSN, where ${\mathit{a}}_i$ and ${\mathit{x}}_t$ represent the known location of the ith reference point, also called anchor ($i=1,\dots ,N$) and the unknown location of a moving target at time t, respectively. At each time instant, the target sends a radio signal to anchors, which are adequately equipped to withdraw the RSS and the TOA quantity from the received signal. In inauspicious NLOS surroundings, RSS and TOA observations at time t, labeled as $P_{i,t}$ and $d_{i,t}$ respectively, can be modeled [27,28] as

$$\begin{array}{c}{P}_{i,t}=P_0-b_{i,t}-10\gamma {log}_{10}\frac{\parallel {\mathit{x}}_t-{\mathit{a}}_i\parallel }{d_0}+n_{i,t},\end{array}$$

(1a)

$$\begin{array}{c}{d}_{i,t}=\parallel {\mathit{x}}_t-{\mathit{a}}_i\parallel +{\beta }_{i,t}+m_{i,t},\end{array}$$

(1b)

where $P_0$ is the RSS (dBm) at a reference distance $d_0$ ($\parallel {\mathit{x}}_t-{\mathit{a}}_i\parallel \ge d_0$), $b_{i,t}$ (dB) and ${\beta }_{i,t}$ (m) are the (positive) NLOS biases, $\gamma$ is the path loss exponent that indicates the rate at which the RSS decreases with distance, $n_{i,t}$ is the log-normal shadowing term (dB) modeled as a zero-mean Gaussian random variable, i.e., $n_{i,t}\sim \mathcal{N}(0,{\sigma }_{n_i}^2)$, and $m_{i,t}\sim \mathcal{N}(0,{\sigma }_{m_i}^2)$ is the TOA measurement noise (m). Similar to some existing works [19,20,21], it is assumed here that the magnitude of the NLOS biases can be bounded by a known constant, i.e., $0\le b_{i,t}\le b_{\max }$ and $0\le {\beta }_{i,t}\le {\beta }_{\max }$. This upper bound can be easily estimated during the calibration phase [21,36].

If all RSS and all TOA observations are stored into a sole vector, i.e., ${\mathit{P}}_t={\left[P_{i,t}\right]}^T$ and ${\mathit{d}}_t={\left[d_{i,t}\right]}^T$ (${\mathit{P}}_t,{\mathit{d}}_t\in {\mathbb{R}}^N$), the joint likelihood function can be written as

$$\begin{array}{c}\mathrm{\Lambda }({\mathit{P}}_t,{\mathit{d}}_t|{\mathit{x}}_t,b_{i,t},{\beta }_{i,t})=p\left({\mathit{P}}_t\right|{\mathit{x}}_t,b_{i,t})p\left({\mathit{d}}_t\right|{\mathit{x}}_t,{\beta }_{i,t})\\ =\frac{1}{\sqrt{2\pi {\sigma }_{n_i}^2{\sigma }_{m_i}^2}}exp\left\{-\frac{{\left(P_{i,t}-P_0+b_{i,t}+10\gamma {log}_{10}\frac{\parallel {\mathit{x}}_t-{\mathit{a}}_{i,t}\parallel }{d_0}\right)}^2{\sigma }_{m_i}^2+{\left(d_{i,t}-\parallel {\mathit{x}}_t-{\mathit{a}}_{i,t}\parallel -{\beta }_{i,t}\right)}^2{\sigma }_{n_i}^2}{{\sigma }_{n_i}^2{\sigma }_{m_i}^2}\right\},\end{array}$$

(2)

where $p(•)$ denotes the probability density function (PDF). The function in Equation (2) represents the exact likelihood function if RSS and TOA measurements are taken from independent sources [28]. Even though this might not be the case in practice, the authors of refs. [27,32] showed through experimental measurements that the observations extracted from the same signal are weakly correlated.

The joint RSS-TOA maximum likelihood (ML) estimator of ${\mathit{x}}_t$, $b_{i,t}$ and ${\beta }_{i,t}$ at time t is obtained by maximizing the joint PDF as

$${\displaystyle \left\{\widehat{{\mathit{x}}_t},{\widehat{b}}_{i,t},{\widehat{\beta }}_{i,t}\right\}=\underset{{\mathit{x}}_t,b_{i,t},{\beta }_{i,t}}{\arg \min }\sum _{i=1}^N\frac{{\left(P_{i,t}-P_0+b_{i,t}+10\gamma {log}_{10}\frac{\parallel {\mathit{x}}_t-{\mathit{a}}_i\parallel }{d_0}\right)}^2{\sigma }_{m_i}^2+{\left(d_{i,t}-\parallel {\mathit{x}}_t-{\mathit{a}}_i\parallel -{\beta }_{i,t}\right)}^2{\sigma }_{n_i}^2}{{\sigma }_{n_i}^2{\sigma }_{m_i}^2}.}$$

(3)

However, Equation (3) is a very difficult optimization problem that cannot be solved directly, since it is highly non-convex and under-determined (the number of unknowns, $2N+2$, is superior to the number of measurement readings, $2N$, at every time instant). Moreover, Equation (3) does not take any prior knowledge accumulated during the movement of the target into consideration, which, for the case of tracking a moving target, makes it a naive approach. Thus, to improve accuracy of an estimator, one should incorporate prior knowledge into the estimator.

Here, it is assumed that the target is moving according to a nearly constant velocity motion model. Therefore, the velocity elements in x- and y-directions at time t are given by

$${\mathit{v}}_t={\mathit{v}}_{t-1}+{\mathit{r}}_{v,t},$$

(4)

where ${\mathit{r}}_{v,t}$ represents the noise perturbations (e.g., due to wind gust). Therefore, according to the equations of motion [39], the location of the target at time instant t is given by

$${\mathit{x}}_t={\mathit{x}}_{t-1}+{\mathit{v}}_{t-1}\Delta +{\mathit{r}}_{x,t},$$

(5)

where $\Delta$ and ${\mathit{r}}_{x,t}$ are, respectively, the sampling interval among two successive time steps and location process noise. Hence, by describing the target state at time instant t by both its location and velocity, that is, ${\mathit{\theta }}_t={[{\mathit{x}}_t^T,{\mathit{v}}_t^T]}^T$ (i.e., ${\mathit{\theta }}_t\in {\mathbb{R}}^4$), from Equations (4) and (5) it follows that

$${\mathit{\theta }}_t=\mathit{S}{\mathit{\theta }}_{t-1}+{\mathit{r}}_t,$$

(6)

where

$$\mathit{S}=\left[\begin{array}{cccc}1& 0& \Delta & 0\\ 0& 1& 0& \Delta \\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right],$$

represents the state transition matrix and ${\mathit{r}}_t={[{\mathit{r}}_{x,t}^T,{\mathit{r}}_{v,t}^T]}^T$ is the state process noise [16,37,38,42], assumed to be a zero-mean Gaussian random variable with covariance matrix $\mathit{Q}$, that is, ${\mathit{r}}_t\sim \mathcal{N}(\mathbf{0},\mathit{Q})$. This noise covariance matrix is defined by

$$\mathit{Q}=q\left[\begin{array}{cccc}\frac{{\Delta }^3}{3}& 0& \frac{{\Delta }^2}{2}& 0\\ 0& \frac{{\Delta }^3}{3}& 0& \frac{{\Delta }^2}{2}\\ \frac{{\Delta }^2}{2}& 0& \Delta & 0\\ 0& \frac{{\Delta }^2}{2}& 0& \Delta \end{array}\right],$$

where q represents the intensity of the state process noise [38,42,53]. A detailed derivation of the state transition model, as well as the matrices $\mathit{S}$ and $\mathit{Q}$ is given in Appendix A.

Moreover, for ease of notation, the measurement equation (Equation (1)) is rewritten in vector form as

$${\mathit{z}}_t=\mathit{h}\left({\mathit{x}}_t\right)+{\mathit{n}}_t,$$

(7)

where ${\mathit{z}}_t={[{\mathit{P}}_t^T,{\mathit{d}}_t^T]}^T$ (${\mathit{z}}_t\in {\mathbb{R}}^{2N}$) is the vector of all measurements at time instant t. Thus, the function $\mathit{h}\left({\mathit{x}}_t\right)={\left[h_i\left({\mathit{x}}_t\right)\right]}^T$ in Equation (7) is defined as $h_i\left({\mathit{x}}_t\right)=P_0-b_{i,t}-10\gamma {log}_{10}\frac{\parallel {\mathit{x}}_t-{\mathit{a}}_i\parallel }{d_0}$ for $i=1,\dots ,N$ [54], and $h_i\left({\mathit{x}}_t\right)=\parallel {\mathit{x}}_t-{\mathit{a}}_i\parallel +{\beta }_{i,t}$ for $i=N+1,\dots ,2N$ [27]. The measurement noise, ${\mathit{n}}_t$, is modeled as ${\mathit{n}}_t\sim \mathcal{N}(\mathbf{0},\mathit{C})$, with the noise covariance matrix being defined as $\mathit{C}=\mathrm{diag}\left([{\sigma }_{n_i}^2,{\sigma }_{m_i}^2]\right)$, with $\mathrm{diag}(•)$ denoting a diagonal matrix.

According to Bayesian methodology, prior knowledge, acquired via the state transition model in  Equation (6), can be combined with noisy observations in Equation (7) to get a marginal posterior PDF, $p\left({\mathit{\theta }}_t\right|{\mathit{z}}_{1:t})$. The reason for this is that through $p\left({\mathit{\theta }}_t\right|{\mathit{z}}_{1:t})$ one can quantify the confidence one has in the values of the state ${\mathit{\theta }}_t$ given all the past observations ${\mathit{z}}_{1:t}$, from which an estimate at any desired time instant can be obtained. For the reader to have a better intuition of how it works, the key parts of the Bayesian estimation are summarized as follows [39].

• Initialization: The marginal posterior PDF at $t=0$ is set to the prior PDF $p\left({\mathit{\theta }}_0\right)$ of ${\mathit{\theta }}_0$.
• Prediction: By following the state transition model in Equation (6), the predictive PDF of the state at t is given by

  $$p\left({\mathit{\theta }}_t\right|{\mathit{z}}_{1:t-1})=\int p\left({\mathit{\theta }}_t\right|{\mathit{\theta }}_{t-1})p\left({\mathit{\theta }}_{t-1}\right|{\mathit{z}}_{1:t-1})d{\mathit{\theta }}_{t-1}.$$

  (8)
• Update: According to Bayes’ rule [42,53], one has that

  $$p\left({\mathit{\theta }}_t\right|{\mathit{z}}_{1:t})=\frac{p\left({\mathit{z}}_t\right|{\mathit{\theta }}_t)p\left({\mathit{\theta }}_t\right|{\mathit{z}}_{1:t-1})}{p\left({\mathit{z}}_t\right|{\mathit{z}}_{1:t-1})},$$

  (9)

  where $p\left({\mathit{z}}_t\right|{\mathit{\theta }}_t)$ is the likelihood and $p\left({\mathit{z}}_t\right|{\mathit{z}}_{1:t-1})=\int p\left({\mathit{z}}_t\right|{\mathit{\theta }}_t)p\left({\mathit{\theta }}_t\right|{\mathit{z}}_{1:t-1})d{\mathit{\theta }}_t$ is just a normalizing constant that does not depend on ${\mathit{\theta }}_t$, required to assure that $p\left({\mathit{\theta }}_t\right|{\mathit{z}}_{1:t})$ integrates to 1 [39]. Generally, the marginal PDF at $t-1$ cannot be calculated in analytic form. Moreover, the integral in  Equation (8) cannot be obtained in closed-form, unless the state model is linear. Hence, certain approximations are necessary to get $p\left({\mathit{\theta }}_t\right|{\mathit{z}}_{1:t})$.

In the following section, we show how to estimate AOA information at each anchor, by only taking advantage of the network architecture formed by anchors and range estimates from RSS and TOA measurements, without requiring any additional hardware. This information is then exploited to linearize the measurement models in Equation (1), which serve as a base on top of which we adapt a KF.

3. Angle of Arrival Estimation

Notice that, from Equation (1), the distances that best estimate $\parallel {\mathit{x}}_t-{\mathit{a}}_i\parallel$ in the mean ML sense are

$$\begin{array}{c}{\widehat{d}}_{i,t}^{\mathrm{RSS}}=d_0{10}^{\frac{P_0-P_{i,t}-\frac{b_{\max }}{2}}{10\gamma }},\end{array}$$

(10a)

$$\begin{array}{c}{\widehat{d}}_{i,t}^{\mathrm{TOA}}=d_{i,t}-\frac{{\beta }_{\max }}{2}.\end{array}$$

(10b)

Once these distance estimates are obtained at any time instant, together with ${\mathit{a}}_i$, $i=1,\dots ,N$, one can form triangles between any pair of anchors and the target, as illustrated in Figure 1, where ${\widehat{d}}_{i,t}$ is used instead of ${\widehat{d}}_{i,t}^{\mathrm{RSS}}$ and ${\widehat{d}}_{i,t}^{\mathrm{TOA}}$ for the sake of simplicity. Hence, in each of the triangles, the lengths of the three sides are (imperfectly) known. This allows for straightforward estimation of the angle ${\beta }_{i,t}$ (see Figure 1), by just applying the law of cosines [55] as

$${\widehat{\beta }}_{i,t}={cos}^{-1}\left(\frac{d_{ij}^2+{\widehat{d}}_{i,t}^2-{\widehat{d}}_{j,t}^2}{2d_{ij}{\widehat{d}}_{i,t}}\right),$$

(11)

based on both RSS and TOA observations. Then, the estimated azimuth angle of the received radio signal at the ith anchor at time t (from both RSS and TOA measurements) is obtained according to

$${\widehat{\phi }}_{i,t}={\alpha }_{ij}\pm {\widehat{\beta }}_{i,t},$$

(12)

where ${\alpha }_{ij}$ is the azimuth angle between anchors i and j, and ± is used due to possible orientation of the target (see Figure 1). In general, to find the right orientation of the target, i.e., the correct sign in Equation (12), it suffices to obtain only a coarse estimate of the target’s location, which, for example, can be accomplished by the trilateration approach in ref. [23]. However, due to high degree of difficulty of the problem at hand, achieving the right orientation of the target might not be feasible in practice. Therefore, due to flip-ambiguity issues, the estimation accuracy might get seriously compromised. Nonetheless, in some favorable deployments of the anchors (such as the ones considered in Section 5), where the orientation of the target is known a priori, we show that using the angle estimates in Equation (12) can significantly improve localization accuracy of an algorithm.

4. Target Tracking

In this section, we propose a novel tracking algorithm based on KF, which can be contemplated as a generalized consecutive minimum mean square estimator of a signal corrupted by noise, where the unknown parameters are permitted to develop in time in concordance with a given dynamical model [39]. What is characteristic for this filter is that, if both the state and the observation models are linear and the noise is known to be zero-mean (having finite covariance), KF renders the optimal solution in the least squares sense [42]. However, our measurement model in Equation (1) is highly non-linear. Therefore, we first take advantage of the angle estimates in Equation (12) to linearize it. This procedure allows straightforward derivation of a sub-optimal solution in a closed-form for the target localization problem in Equation (3), in which the prior knowledge is completely disregarded. Moreover, we also show that the derived linearized measurement model also triggers effortless adaptation of KF equations, which take the prior knowledge into consideration to improve the localization performance.

Note that one can rewrite Equation (10) as follows.

$$\begin{array}{c}{\lambda }_{i,t}\parallel {\mathit{x}}_t-{\mathit{a}}_i\parallel =\eta d_0,\end{array}$$

(13a)

$$\begin{array}{c}\parallel {\mathit{x}}_t-{\mathit{a}}_i\parallel =d_{i,t}-\frac{{\beta }_{\max }}{2},\end{array}$$

(13b)

where ${\lambda }_{i,t}={10}^{\frac{P_{i,t}+\frac{b_{\max }}{2}}{10\gamma }}$ and $\eta ={10}^{\frac{P_0}{10\gamma }}$. Furthermore, from geometry, one has that

$${\widehat{\phi }}_{i,t}={tan}^{-1}\left(\frac{x_{t\mathrm{y}}-a_{i\mathrm{y}}}{x_{t\mathrm{x}}-a_{i\mathrm{x}}}\right),$$

where $x_{t\mathrm{y}}$ and $a_{i\mathrm{y}}$, respectively, designate the y-coordinates of the target and the ith anchor at time t, and $x_{t\mathrm{x}}$ and $a_{i\mathrm{x}}$ their x-coordinates at t. By applying some simple algebraic manipulations, the above equation can be rewritten as

$$\begin{array}{c}{\mathit{c}}_{i,t}^T\left({\mathit{x}}_t-{\mathit{a}}_i\right)=0,\end{array}$$

(14a)

$$\begin{array}{c}{\mathit{k}}_{i,t}^T\left({\mathit{x}}_t-{\mathit{a}}_i\right)=0,\end{array}$$

(14b)

where ${\mathit{c}}_{i,t}={[-sin\left({\widehat{\phi }}_{i,t}^{\mathrm{RSS}}\right),cos\left({\widehat{\phi }}_{i,t}^{\mathrm{RSS}}\right)]}^T$ and ${\mathit{k}}_{i,t}={[-sin\left({\widehat{\phi }}_{i,t}^{\mathrm{TOA}}\right),cos\left({\widehat{\phi }}_{i,t}^{\mathrm{TOA}}\right)]}^T$.

Hence, an estimate of ${\mathit{x}}_t$ can be obtained by solving the following problem

$$\begin{array}{c}{\displaystyle {\widehat{\mathit{x}}}_t=\underset{{\mathit{x}}_t}{\arg \min }\underset{i=1}{\overset{N}{-}}{\left({\lambda }_{i,t}\parallel {\mathit{x}}_t-{\mathit{a}}_i\parallel -\eta d_0\right)}^2+\underset{i=1}{\overset{N}{-}}{\left({\mathit{c}}_{i,t}^T\left({\mathit{x}}_t-{\mathit{a}}_i\right)\right)}^2}\\ {\displaystyle +\sum _{i=1}^N{\left(\parallel {\mathit{x}}_t-{\mathit{a}}_i\parallel -{\widehat{d}}_{i,t}^{\mathrm{TOA}}\right)}^2+\sum _{i=1}^N{\left({\mathit{k}}_{i,t}^T\left({\mathit{x}}_t-{\mathit{a}}_i\right)\right)}^2,}\end{array}$$

(15)

resulting from the application of the least squares criterion to Equations (13) and (14).

However, the problem in Equation (15) is non-convex due to the norm terms containing ${\mathit{x}}_t$. Consequently, combating Equation (15) directly is difficult, and we take a different approach here. Rather than dealing with the problem in the Cartesian space, we exploit the estimated angles to transform Equation (15) into the polar space, a more suitable one when dealing with angles [33,56,57]. To do so, we express ${\mathit{x}}_t-{\mathit{a}}_i={\mathit{r}}_{i,t}{\mathit{u}}_{i,t}$ in Equation (13a), with ${\mathit{r}}_{i,t}\ge 0$ and $\parallel {\mathit{u}}_{i,t}\parallel =1$, where the estimated unit vector is defined as ${\mathit{u}}_{i,t}={[cos\left({\widehat{\phi }}_{i,t}^{\mathrm{RSS}}\right),sin\left({\widehat{\phi }}_{i,t}^{\mathrm{RSS}}\right)]}^T$. This results in $\parallel {\mathit{x}}_t-{\mathit{a}}_i\parallel =r_{i,t}$. A similar procedure is applied to Equation (13b), where ${\mathit{x}}_t-{\mathit{a}}_i={\rho }_{i,t}{\mathit{v}}_{i,t}$, with ${\rho }_{i,t}\ge 0$ and the estimated unit vector defined as ${\mathit{v}}_{i,t}={[cos\left({\widehat{\phi }}_{i,t}^{\mathrm{TOA}}\right),sin\left({\widehat{\phi }}_{i,t}^{\mathrm{TOA}}\right)]}^T$. The applied process is easily reversed by just multiplying the two equations by ${\mathit{u}}_{i,t}^T{\mathit{u}}_{i,t}=1$, i.e., ${\mathit{v}}_{i,t}^T{\mathit{v}}_{i,t}=1$, which brings us back to the Cartesian space. Thus, by enforcing the above described procedure to Equation (13), we get

$$\begin{array}{c}{\mathit{\lambda }}_{i,t}{\mathit{u}}_{i,t}^T{\mathit{r}}_{i,t}{\mathit{u}}_{i,t}=\eta d_0\iff {\lambda }_{i,t}{\mathit{u}}_{i,t}^T\left({\mathit{x}}_t-{\mathit{a}}_i\right)=\eta d_0,\end{array}$$

(16a)

$$\begin{array}{c}{\mathit{v}}_{i,t}^T{\mathit{\rho }}_{i,t}{\mathit{v}}_{i,t}={\widehat{d}}_{i,t}^{\mathrm{TOA}}\iff {\mathit{v}}_{i,t}^T\left({\mathit{x}}_t-{\mathit{a}}_i\right)={\widehat{d}}_{i,t}^{\mathrm{TOA}}.\end{array}$$

(16b)

Consequently, Equation (16) can be rephrased in a (linear) vector form as

$${\mathit{A}}_t{\mathit{x}}_t={\mathit{b}}_t,$$

(17)

where

$${\mathit{A}}_t=\left[\begin{array}{c}{\lambda }_{1,t}{\mathit{u}}_{1,t}^T\\ ⋮\\ {\lambda }_{N,t}{\mathit{u}}_{N,t}^T\\ {\mathit{c}}_{1,t}^T\\ ⋮\\ {\mathit{c}}_{N,t}^T\\ {\mathit{v}}_{1,t}^T\\ ⋮\\ {\mathit{v}}_{Ni,t}^T\\ {\mathit{k}}_{1,t}^T\\ ⋮\\ {\mathit{k}}_{N,t}^T\end{array}\right],{\mathit{b}}_t=\left[\begin{array}{c}{\lambda }_{1,t}{\mathit{u}}_{1,t}^T{\mathit{a}}_1+\eta d_0\\ ⋮\\ {\lambda }_{N,t}{\mathit{u}}_{N,t}^T{\mathit{a}}_N+\eta d_0\\ {\mathit{c}}_{1,t}^T{\mathit{a}}_1\\ ⋮\\ {\mathit{c}}_{N,t}^T{\mathit{a}}_N\\ {\mathit{v}}_{1,t}^T{\mathit{a}}_1+{\widehat{d}}_{1,t}^{\mathrm{TOA}}\\ ⋮\\ {\mathit{v}}_{N,t}^T{\mathit{a}}_N+{\widehat{d}}_{N,t}^{\mathrm{TOA}}\\ {\mathit{k}}_{1,t}^T{\mathit{a}}_1\\ ⋮\\ {\mathit{k}}_{N,t}^T{\mathit{a}}_N\end{array}\right],$$

which becomes our linearized measurement model.

With the intention to assign more belief to close by links (both RSS and TOA), we introduce weights, ${\mathit{w}}_t={\left[\sqrt{w_{i,t}}\right]}^T$ and ${\mathit{\omega }}_t={\left[\sqrt{{\omega }_{i,t}}\right]}^T$, with $w_{i,t}=1-{\widehat{d}}_{i,t}^{RSS}/{\sum }_{i=1}^N{\widehat{d}}_{i,t}^{RSS}$ and ${\omega }_{i,t}=1-{\widehat{d}}_{i,t}^{TOA}/{\sum }_{i=1}^N{\widehat{d}}_{i,t}^{TOA}$. Then, based on the WLS principle, we obtain an estimate of ${\mathit{x}}_t$ by solving

$$\begin{array}{c}{\displaystyle \widehat{{\mathit{x}}_t}=\underset{{\mathit{x}}_t}{\arg \min }\sum _{i=1}^N{w}_{i,t}{\left({\lambda }_{i,t}{\mathit{u}}_{i,t}^T\left({\mathit{x}}_t-{\mathit{a}}_i\right)-\eta d_0\right)}^2+\sum _{i=1}^N{w}_{i,t}{\left({\mathit{c}}_{i,t}^T\left({\mathit{x}}_t-{\mathit{a}}_i\right)\right)}^2}\\ {\displaystyle +\sum _{i=1}^N{\omega }_{i,t}{\left({\mathit{v}}_{i,t}^T\left({\mathit{x}}_t-{\mathit{a}}_i\right)-{\widehat{d}}_{i,t}^{TOA}\right)}^2+\sum _{i=1}^N{\omega }_{i,t}{\left({\mathit{k}}_{i,t}^T\left({\mathit{x}}_t-{\mathit{a}}_i\right)\right)}^2.}\end{array}$$

(18)

Note that the optimization variable appears in a quadratic form in Equation (18), which makes the problem convenient to solve in closed-form. To give its solution, we first rewrite Equation (18) in a vector form as

$$\underset{{\mathit{x}}_t}{\mathrm{minimize}}{\parallel {\mathit{W}}_t({\mathit{A}}_t{\mathit{x}}_t-{\mathit{b}}_t)\parallel }^2,$$

(19)

where ${\mathit{W}}_t=\mathrm{diag}\left(\left[{\mathit{w}}_t^T,{\mathit{w}}_t^T,{\mathit{\omega }}_t^T,{\mathit{\omega }}_t^T\right]\right)$, with $\mathrm{diag}(•)$ denoting a diagonal matrix. Hence, the solution to  Equation (19) is given in closed-form as

$${\widehat{\mathit{x}}}_t={\left({\mathit{A}}_t^T{\mathit{W}}_t^T{\mathit{W}}_t{\mathit{A}}_t\right)}^{-1}\left({\mathit{A}}_t^T{\mathit{W}}_t^T{\mathit{b}}_t\right).$$

In the remaining text, the estimator in Equation (18) is referred to as “WLS”.

Although Equation (18) is an efficient solution to the target localization problem, it completely disregards any prior knowledge one might have accumulated during the movement of the target along its trajectory. Therefore, in the following text, we show that Equation (18) can be used as the main building block on top of which prior knowledge can be incorporated.

To do so, we rely on the the most common principle of Bayesian methodology for getting a state estimate, which is the maximum a posteriori principle [39]. Based on this estimation criterion, one chooses a state estimate, ${\widehat{\mathit{\theta }}}_{t|t}$, that maximizes the marginal PDF, which formally translates into

$${\widehat{\mathit{\theta }}}_{t|t}=\underset{{\mathit{\theta }}_t}{\arg \max }p\left({\mathit{\theta }}_t\right|{\mathit{z}}_{1:t})=\underset{{\mathit{\theta }}_t}{\arg \max }p\left({\mathit{z}}_t\right|{\mathit{\theta }}_t)p\left({\mathit{\theta }}_t\right|{\mathit{z}}_{1:t-1}),$$

(20)

where the second equality comes from Equation (9). By taking a closer look at Equation (20), one notices that it contains exactly what we aspired for: ML part related to the measurement model and prior PDF part related to prior knowledge. This means that, by the help of KF approach [39], we can adapt the filter’s equations to derive our own version of the KF as follows.

The mean and the covariance of the one-step predicted state are obtained according to Equation (6) as

$${\widehat{\mathit{\theta }}}_{t|t-1}=\mathit{S}{\widehat{\mathit{\theta }}}_{t-1|t-1}$$

(21a)

$${\widehat{\mathbf{\Sigma }}}_{t|t-1}=\mathit{S}{\widehat{\mathbf{\Sigma }}}_{t-1|t-1}{\mathit{S}}^T+\mathit{Q},$$

(21b)

respectively, whereas the updated mean and covariance are given by

$${\widehat{\mathit{\theta }}}_{t|t}={\widehat{\mathit{\theta }}}_{t|t-1}+{\mathit{K}}_t({\tilde{\mathit{b}}}_t-{\mathit{G}}_t{\widehat{\mathit{\theta }}}_{t|t-1}),$$

(22a)

$${\widehat{\mathbf{\Sigma }}}_{t|t}=\left({\mathit{I}}_4-{\mathit{K}}_t{\mathit{G}}_t\right){\widehat{\mathbf{\Sigma }}}_{t|t-1},$$

(22b)

with

$${\mathit{K}}_t={\widehat{\mathbf{\Sigma }}}_{t|t-1}{\mathit{G}}_t^T{({\mathit{G}}_t{\widehat{\mathbf{\Sigma }}}_{t|t-1}{\mathit{G}}_t^T+\mathit{C})}^{-1}$$

(23)

representing the Kalman gain at time instant t, and ${\mathit{G}}_t=[{\mathit{A}}_t,{\mathbf{0}}_{2N\times 2}]$ (${\mathit{G}}_t\in {\mathbb{R}}^{2N\times 4}$).

A step-by-step framework of the proposed KF algorithm (labeled here as “KF”) is summarized in Algorithm 1, and its flow chart is illustrated in Figure 2.

Algorithm 1 KF algorithm description.

Require:$\mathit{S}$, $\mathit{Q}$, $\mathit{C}$, ${\mathit{z}}_t$, for $t=0,\dots ,T$ 1: Initialization:${\widehat{\mathit{x}}}_{0|0}\leftarrow Equation\left(19\right)$, ${\widehat{\mathit{\theta }}}_{0|0}\leftarrow {[{\widehat{\mathit{x}}}_{0|0}^T,0,0]}^T$, ${\widehat{\mathbf{\Sigma }}}_{0|0}\leftarrow {\mathit{I}}_4$ 2: for$t=1,\dots ,T$do 3:  Prediction: ${\widehat{\mathit{\theta }}}_{t|t-1}\leftarrow \mathit{\text{Equation}}\left(21\mathrm{a}\right)$ ${\widehat{\mathbf{\Sigma }}}_{t|t-1}\leftarrow \mathit{\text{Equation}}\left(21\mathrm{b}\right)$ 4:  Kalman gain: $\begin{array}{c}{\mathit{K}}_t\leftarrow \mathit{\text{Equation}}\left(23\right)\hfill \end{array}$ 5:  Update: ${\widehat{\mathit{\theta }}}_{t|t}\leftarrow \mathit{\text{Equation}}\left(22\mathrm{a}\right)$ ${\widehat{\mathbf{\Sigma }}}_{t|t}\leftarrow \mathit{\text{Equation}}\left(22\mathrm{b}\right)$ 6: end for

5. Performance Results

This section validates the performance of the proposed algorithm based on computer simulations. The considered algorithms, the PF in ref. [51] and the EKF in ref. [52], as well as the WLS in Equation (19) and the proposed KF in Algorithm 1, were implemented in MATLAB, and the radio measurements were generated according to Equation (1). True anchor locations are summarized in

Table 1. True locations of anchors in the simulation environment.

i	1	2	3	4	5	6	7	8
$a_i$ (m)	0	0	B	B	0	$B/2$	$B/2$	B
	0	B	0	B	$B/2$	0	B	$B/2$

, whereas the target follows the trajectory illustrated in Figure 3 within an area of $B\times B{\mathrm{m}}^2$ in every Monte Carlo, $M_c$, run. The rest of the simulation parameters are summarized in

Table 2. Summary of the simulation parameters.

Parameter	Description	Value
N	The number of sensors	≤8
$|{\mathcal{L}}_{\mathrm{NLOS}}|$	The number of NLOS links	N
B	The length of the area border	30
${\mathit{a}}_i$	The true anchor locations	See Table 1
$P_0$	The reference power	20 (dBm)
$d_0$	The reference distance	1 (m)
$\gamma$	The PLE	3
${\sigma }_i$	The noise power (RSS and TOA)	≤6 (dB, m)
${\mathrm{bias}}_{\max }$	The magnitude the NLOS bias (RSS and TOA)	≤6 (dB, m)
${\mathrm{bias}}_i$	The NLOS bias (RSS and TOA)	${\mathrm{bias}}_i\sim \mathcal{U}[0,{\mathrm{bias}}_{\max }]$ (dB, m)
$\parallel {\mathit{v}}_t\parallel$	Speed of the target	$0.5$ (m/s)
$\Delta$	The sampling interval	1 (s)
T	Trajectory duration	160 (s)
q	The state process noise	$2.5\times {10}^{-3}$ (${\mathrm{m}}^2/{\mathrm{s}}^3$)
$M_c$	The number of Monte Carlo runs	500

. Furthermore, NLOS biases (both $b_i$ (dB) and ${\beta }_i$ (m), jointly designated here as ${\mathrm{bias}}_i$ for simplicity) are generated randomly from a uniform distribution on the interval $[0,{\mathrm{bias}}_{\max }]$ (dB, m), i.e., ${\mathrm{bias}}_i\sim \mathcal{U}[0,{\mathrm{bias}}_{\max }]$, $i=1,\dots ,N$ in each $M_c$ run. The main performance metric is the root mean squared error (RMSE), $\mathrm{RMSE}=\sqrt{{\sum }_{i=1}^{M_c}\frac{\parallel {\mathit{x}}_{i,t}-{\widehat{\mathit{x}}}_{i,t}-}{M_c}}$, where ${\widehat{\mathit{x}}}_{i,t}$ denotes the estimate of the true target location, ${\mathit{x}}_{i,t}$, in the ith $M_c$ run at time instant t.

The proposed KF algorithm is compared with the existing RSS and TOA tracking algorithms, namely the PF in ref. [51] and the EKF in ref. [52], as well as the WLS in Equation (19), which represents its main building block that disregards the prior knowledge, in the scenario illustrated in Figure 3. Note that the trajectory in Figure 3 is composed of several straight-line trajectories connected by sharp maneuvers, together with somewhat smoother maneuvers, but with constant changes in the direction of movement; hence, it represents a fairly complex trajectory, whose portions are often found in practice. Moreover, notice that a constant speed of the target is considered here for simplicity. This does not cause loss of generality, since the proposed KF algorithm is extremely light in terms of computational cost, which translates into its execution time being of order of milliseconds. In other words, this means that we could drastically reduce the sampling interval, which would result in much smaller steps of the target (at the order of centimeters) within a sample period, producing the effect of approximately constant velocity model for virtually all achievable speeds in practice. Lastly, to conclude the simulation setting part, it is worth mentioning that, in all simulations presented here, the first N anchors from Table 1 were used.

Figure 4 plots a realization of the estimation trial in the considered setting of KF and WLS in a single $M_c$ run. On the one hand, the figure clearly shows that KF has much smoother performance and traces the target’s trajectory more accurately. Naturally, KF struggles slightly at each sharp maneuver of the target. This is explained by the fact that at these points all previously acquired prior knowledge becomes fallacious, and misleads KF to stumble. Nevertheless, it can be seen that KF recovers quite quickly from these predicaments. On the other hand, the figure shows that, although the performance of WLS does not suffer such inconveniences and is fairly good, the trace of the trajectory obtained through WLS seems a bit chaotic. This is because WLS disregards the prior knowledge, and every plotted estimation point is a result independent of any previous one.

Figure 5 illustrates the RMSE (m) versus t performance for various N. Besides the RMSE at each time instant t, the average RMSE, $\overline{\mathrm{RMSE}}$, for all t is also shown in the figure (straight horizontal lines marked with respective symbols and colors). Superior performance of tracking algorithms is clearly noted in general. Interestingly, the tracking algorithms are not always better than WLS, i.e., not at all time instants. It seems that KF and EKF struggle with the sharp maneuvers taken by the target at the top right corner of its trajectory and the one immediately after. Nevertheless, these peaks in the performance of KF and EKF are of relatively short duration, and do not change the overall conclusion that incorporating prior knowledge can improve the performance of an algorithm. Finally, it can be seen from the figure that, apart from the case where $N=2$, PF has the most stable performance, with very few peaks. This is not too surprising, since its performance is directly proportional to the number of particles used, but so is its computational complexity.

Figure 6 illustrates $\overline{\mathrm{RMSE}}$ (m) versus N performance. In addition to KF, PF, EKF and WLS algorithms, we also include the results for the counterpart of the proposed KF, when, instead of estimating the angles, anchors can measure them. These results can be seen as a lower bound on the performance of the new algorithm. Nonetheless, it is worth noting that, in order for these results to be feasible, anchors would require additional hardware, such as a directional antenna or an antenna array, which would raise the network implementation cost. Moreover, the angle measurement noise power was drawn from a zero-mean von Mises distribution [56] with the concentration parameter set as to correspond to a zero-mean Normal distribution with noise power ${\sigma }_{\mathrm{AOA}}=8^{\circ }$, as stated explicitly in Figure 6. The figure exhibits that the performance of all algorithms betters when N is increased. This behavior is anticipated, due to extra information gathered within the network with every additional anchor. Furthermore, apart from the performance of PF for $N=2$, the performance of the tracking algorithms is superior than that of WLS for all N, with the biggest margin for low N, which confirms the hypothesis that prior knowledge can be exploited to improve localization accuracy. Finally, one can notice that the performance of the proposed KF is fairly close to its counterpart that can measure the AOA. This is an important result, which suggests that the proposed approach for angle estimation is a useful one in practical scenarios where no additional hardware to measure the AOA is available.

Figure 7 illustrates $\overline{\mathrm{RMSE}}$ (m) versus noise powers, ${\sigma }_i$ (dB, m), performance comparison. To get a better comprehension of the influence of this parameter on localization performance, the magnitude of the NLOS bias was set to a relatively small value, i.e., ${\mathrm{bias}}_{\max }=1$ (dB, m) was considered. Naturally, when the measurement quality deteriorates, i.e., when ${\sigma }_i$ (dB, m) grows, the localization accuracy drops. Nevertheless, Figure 7 shows that KF has superior performance in noisy environments, outperforming significantly WLS (almost 2.5 m) and PF and EKF (roughly 1 m). This result confirms that our linearization technique is a well-founded solution, since our derivation do not make any assumptions about noise levels.

Figure 8 illustrates $\overline{\mathrm{RMSE}}$ (m) versus ${\mathrm{bias}}_{\max }$ (dB, m) performance comparison. Similar to the previous setting, to better see the influence of this parameter on the performance of the considered algorithm, the noise powers were set to a relatively small value, i.e., ${\sigma }_i=1$ (dB, m) was considered. As before, Figure 8 corroborates the superiority of tracking algorithms over classical localization ones for all considered values of ${\mathrm{bias}}_{\max }$ (dB, m), indicating that prior knowledge should not be disregarded. However, achieving precision just above 3 m for WLS suggests that the proposed approach handles NLOS bias efficiently, even for a naive approach.

6. Conclusions and Future Work

In this work, we proposed a novel approach for tracking a moving target in adverse NLOS environments by means of combined RSS and TOA measurements. Initially, we showed how to estimate the angle of the received signal at each reference point, without requiring any additional hardware. For this purpose, the known topology of the reference points was exploited to act as an irregular antenna array, which together with range estimates obtained through RSS and TOA measurements allowed us to form triangles with (imperfectly) known side lengths between a pair of reference points and the target. From there, we simply applied the law of cosines to get the desired AOA estimations. We then showed how to use these estimates to effortlessly convert the originally non-linear measurement model into a linear one, by applying Cartesian to polar coordinates transformation. On top of the linearized model, we incorporated prior knowledge acquired during the movement of the target, by adaptation of the KF equations. The proposed approach was assessed via computer simulations in which a fairly complex target trajectory was studied. In all considered scenarios, the new approach exhibited good performance, corroborating our intuition that one can benefit from extra information inherent in the network topology.

Note that the proposed approach is not restricted to RSS and/or TOA measurements, but can easily be adapted to any range-based localization/tracking technique, as it merely requires distance information and a couple of reference point. Even though we showed here that it can be very beneficial for the problem at hand, some challenges remain. For instance, the application of the proposed approach to an ad-hoc network is straightforward, but one has to be able to resolve the problem of target orientation, i.e., flip-ambiguity. This is very demanding to achieve always due to elevated degree of difficulty of the considered problem (NLOS bias, noise, etc.), which obviously reflects on the estimation accuracy. Therefore, our future research will include combating flip-ambiguity in order to accomplish also full potential of the proposed approach in ad-hoc networks. In addition, testing the proposed KF algorithm against real-world experimental measurements will be of highest priority.