A Leading Edge Detection Algorithm for UWB Based Indoor Positioning Systems

Abstract

Ultra-wide band (UWB) based indoor positioning systems are preferred for accurate positioning applications due to the high time resolution offered by UWB signals. This paper proposes an algorithm for determining the leading edge of UWB signal for indoor positioning applications and assess its performance in different signal-to-noise ratio (SNR) conditions. We found that the proposed algorithm outperforms the previously published methods, especially under low SNR situations. The performance of the algorithm can be further increased with an additional number of anchor nodes.

1 Introduction

Indoor positioning systems (IPS) have different applications such as asset tracking, indoor way finding, space management and location-based services. IPS offers benefits such as efficiency improvement, convenience and cost saving. IPS uses technologies like Bluetooth, Wi-Fi, RFID and UWB for position estimation [1,2,3,4,5,6]. UWB technology offers high positioning accuracy compared to other technologies due the high bandwidth of UWB signals [7,8,9]. IPS employs various ranging techniques such as received signal strength indicator (RSSI), time of arrival (TOA), time difference of arrival (TDOA) and angle of arrival (AOA) for target position estimation. RSSI based techniques determine the distance between target node and anchor node using RSSI [10] whereas AOA based techniques estimate the angle between target node and anchor node using antenna arrays [11, 12]. The RSSI based techniques are sensitive to the channel parameters and hence are less accurate. The AOA based methods do not perform well in multi-path environments [13]. TOA based techniques use the signal propagation delay for range estimation and need proper synchronization between the target and anchor nodes. TDOA approach uses TOA difference at each pair of anchor node for target position estimation [14, 15] and requires synchronization only among the anchor nodes. UWB based IPS utilizes TOA or TDOA based ranging method for position estimation. The anchor node of an UWB IPS implements a TOA estimation algorithm for range estimation. Different UWB receiver structures and TOA estimation algorithms are proposed in the literature [16, 17]. A Single channel receiver that implements standard leading edge detection (SLED) algorithm [19, 20] provides an improved accuracy compared to other methods [18]. The SLED algorithm is used to detect the leading edge in the received UWB signal. However, the SLED algorithm fails to detect the leading edge in low SNR conditions.

In this paper, we propose an Improved Leading Edge Detection (ILED) algorithm and evaluate its performance using simulations. The results show that the proposed algorithm outperforms the original SLED algorithm [19], especially under high noise conditions. The rest of the paper is organized as follows. Section 2 describes the proposed ILED algorithm, trilateration method and simulation setup of UWB localization system. Section 3 describes the simulation results concerning accuracy of the proposed algorithm and influence of the number of anchor nodes on the positioning accuracy. Finally, Sect. 4 concludes the paper.

Fig. 1.

Received signal at SNR = 4 dB

2 System Model

In an UWB based IPS, the target node transmits an UWB pulse g(t) to different anchor nodes given by,

$$\begin{aligned} g(t) = \frac{A}{\root \of {2\pi }\sigma }e^{-\frac{t^2}{2\sigma ^2}} \end{aligned}$$

(1)

where A is the amplitude of the Gaussian pulse and $\sigma$ is the shaping factor. The signal received at an anchor node h(t) can be represented as

$$\begin{aligned} h(t) = g(t)+a(t) \end{aligned}$$

(2)

where a(t) represents Additive White Gaussian Noise (AWGN).

2.1 Proposed ILED Algorithm

The received signal h(t) at an SNR of 4 dB is shown in Fig. 1. As shown in the figure, the received signal h(t) is fully noisy and it is difficult to detect the leading edge of the transmitted Gaussian pulse g(t) in it. We have improved the existing SLED algorithm to develop the proposed ILED algorithm for detecting the leading edge in such noisy signals. The original SLED algorithm [19, 20] and improvements to it are described below.

SLED Algorithm

At first, a Z point moving average filter is applied on the received signal h(t) to obtain z(t) where a Z point moving average filter returns the average of previous Z samples. In the next step, two maximum window filters of size $F_1$ and $F_2$ are applied on z(t) to obtain signals $f_1(t)$ and $f_2(t)$ respectively, where $F_2$ > $F_1$. Here, the F point maximum window filter returns the maximum-valued sample in the previous F samples.

The leading edge of h(t) is detected when the below condition (3) is fulfilled where $\eta$ is the leading edge factor.

$$\begin{aligned} \frac{f_{2}(t)}{f_{1}(t)}\,\,\le \,\,\eta \end{aligned}$$

(3)

In order to avoid mis-detection of the leading edge in pure noise, the leading edge is detected only when UWB signal is present in the received signal. Hence, the condition (3) is checked only when a signal v(t) crosses a threshold w given by,

$$\begin{aligned} v(t)\; \ge \;w \end{aligned}$$

(4)

where,

$$\begin{aligned} w = G_{noise}+t_{swt} \end{aligned}$$

(5)

$$\begin{aligned} v(t)=f_2(t) \end{aligned}$$

(6)

Here, $G_{noise}$ is the maximum value of filtered received signal z(t) before the occurrence of the UWB pulse and $t_{swt}$ is a pre-defined threshold [20].

Improvements to SLED Algorithm

The original SLED algorithm provides poor performance for SNR < 6 dB, due to false detection of the leading edge in noise due to steps (5)–(6) [20]. Since the standard deviation of noise $\sqrt{\tilde{G}}$ is a consistent measure of noise, we use it in our algorithm as noise threshold in (4), instead of the maximum value of filtered noise as in the case of original algorithm (5). The probability of false detection of leading edge increases due to the usage of $f_2(t)$ in (6) in the original algorithm. This is because $f_2(t)$ crosses the noise threshold before the onset of UWB pulse due to $F_2$ > $F_1$. In order to reduce the chance of mis-detection of leading edge, a faster signal shall be used in (4). Modified leading edge detection (MLED) algorithm [21] implements faster maximum window filter signal $f_1(t)$ for noise threshold comparison, as mentioned in (7).

$$\begin{aligned} v(t)=f_1(t) \end{aligned}$$

(7)

The accuracy of the algorithm can be further improved by using the fast moving average signal z(t) for noise threshold comparison instead of faster maximum window filter signal $f_1(t)$. This is due to the reason that z(t) leads in time when compared to $f_1(t)$ and hence by using z(t), the chance of mis-detection of the leading edge in noise can be reduced. Hence, the following changes are implemented when compared to the SLED and MLED algorithm to improve the performance in high noise conditions.

$$\begin{aligned} w = \gamma \sqrt{\tilde{G}} \end{aligned}$$

(8)

$$\begin{aligned} v(t) = z(t) \end{aligned}$$

(9)

where $\tilde{G}$ indicates the noise power calculated from h(t) in noise, before the occurrence of UWB pulse and $\gamma$ is the factor of noise standard deviation. Lower values of $\gamma$ increases the chance of detecting leading edge in noise prior to UWB pulse. On the other hand, higher values of $\gamma$ miss the leading edge detection under high noise conditions. Hence, by choosing an optimum value for $\gamma$ by means of simulations or experiments, an optimum performance can be achieved using the proposed algorithm.

2.2 Trilateration

Once the leading edge is detected in the signal received at an anchor node, the distance between the target node and the respective anchor node can be determined. Further, the target node position can be determined using the distance between target node to each anchor node based on trilateration as explained below.

Consider an IPS with N number of anchor nodes located at ($x_i$, $y_i$) where i indicates the anchor node index and a target node located at ($x_t$, $y_t$). Assume the distance from target node to each anchor node is $r_i$. Using the Euclidean distance between target and anchor nodes, the following non-linear system of equations can be obtained.

$$\begin{aligned} \left. \begin{array}{ll} (x_0-{x}_t)^2+(y_0-{y}_t)^2 &{}= \hat{r}_0^2 \\ (x_1-{x}_t)^2+(y_1-{y}_t)^2 &{}= \hat{r}_1^2 \\ &{}\vdots \\ (x_{N-1}-{x}_t)^2+(y_{N-1}-{y}_t)^2 &{}= \hat{r}_{N-1}^2 \\ \end{array} \right\} \end{aligned}$$

(10)

The following over-determined linear system of equations can be obtained by solving the above non-linear equations.

$$\begin{aligned} \mathbf{B} {} \mathbf {x} =\mathbf{c} \end{aligned}$$

(11)

where,

$$\begin{aligned} \mathbf{B} =\begin{bmatrix} (x_0-x_1) &{} (y_0-y_1) \\ \vdots &{} \vdots \\ (x_0-x_{N-1}) &{} (y_0-y_{N-1}) \\ \vdots &{} \vdots \\ (x_{N-2}-x_{N-1}) &{} (y_{N-2}-y_{N-1}) \\ \end{bmatrix} \, \mathbf{c} =\begin{bmatrix} C_{01} \\ \vdots \\ C_{0{(N-1)}} \\ \vdots \\ C_{{(N-2)}{(N-1)}} \\ \end{bmatrix} \end{aligned}$$

$$\begin{aligned} C_{ij} =\frac{1}{2}.( x_i^2-x_j^2+y_i^2-y_j^2+\hat{r}_j^2-\hat{r}_i^2) \end{aligned}$$

$$\begin{aligned} \mathbf{x} =\begin{bmatrix} {x}_t \; {y}_t \end{bmatrix}^{\text {T}} \end{aligned}$$

The target node position, can be estimated using the least square solution of (11) given by,

$$\begin{aligned} \hat{\mathbf{x }}=(\mathbf{B} ^\mathbf{T }{} \mathbf{B} )^\mathbf{-1 }{} \mathbf{B} ^\mathbf{T }{} \mathbf{c} \end{aligned}$$

(12)

Fig. 2.

Illustration of signals involved in the proposed leading edge detection algorithm for SNR = 10 dB and tuning parameters, $\eta$ = 1.2 and $\gamma$ = 1.2

2.3 System Simulation

An UWB IPS simulator is developed that supports a minimum of 3 and a maximum of 6 anchor nodes. The anchor nodes are located on the vertices of a regular polygon with a radius of 13 m. The location of the target node is chosen inside the circumference of a circle that encloses the polygon vertices. By choosing such a setup, the target node gets optimum coverage from all the anchor nodes. An UWB signal g(t) with a pulse width of 300 ps is used for the simulations. The received signal h(t) is modeled according to (2) where the noise power is determined based on the simulated SNR. The proposed algorithm with $Z = 16$, $F_1 = 16$ and $F_2 = 256$ is applied on h(t) to detect the leading edge. Finally, the position of the target is estimated using (12). Figure 2 shows all the signals involved in ILED algorithm which includes, the received signal h(t), 16 point moving averaged signal z(t), 16 point and 256 point maximum window filtered signals $f_1(t)$ and $f_2(t)$ respectively, the estimated leading edge binary signal l(t), expected leading edge binary signal $l_e(t)$ and the noise threshold w. As discussed in Sect. 2.1, we can clearly see from the Fig. 2 that the 16 point moving average filter output signal z(t) leads in time when compared to the 16 point maximum window filter output $f_1(t)$. By using z(t) for noise threshold comparison, we can avoid leading edge detection in noise, prior to the onset of UWB pulse.

3 Results

3.1 Ranging Accuracy

Monte-Carlo simulations are performed with the target position fixed at the center of polygon, to estimate the distance between the anchor node and the target node using the proposed algorithm. Ranging accuracy $\text {E}^{(1D)}$ is evaluated as mentioned below in (13).

$$\begin{aligned} \text {E}^{(1D)} = \sqrt{{\frac{1}{N_T.N_{BS}}}\sum \limits _{i=1}^{N_T}\sum \limits _{j=1}^{N_{BS}}{\left[ r^{\,ij}_{err}\right] }^2} \end{aligned}$$

(13)

where,

$$\begin{aligned} \begin{aligned} r^{\,ij}_{err} =&\sqrt{(x_t-x_a^j)^2+(y_t-y_a^j)^2}\\ {}&- \sqrt{(\hat{x}_t^i-x_a^j)^2+(\hat{y}_t^i-y_a^j)^2}, \end{aligned} \end{aligned}$$

$N_T$ and $N_{BS}$ represents the number of trials and number of anchor nodes respectively, $(x_a^j,\,y_a^j)$ represents the position of $j^{th}$ anchor node and $(x_t,\,y_t)$, $(\hat{x}_t^i,\,\hat{y}_t^i)$ represents the actual and estimated target positions during the $i^{th}$ trial, respectively.

Fig. 3.

Performance comparison of proposed ILED algorithm with SLED algorithm under normal SNR conditions for $\eta = 1.2$, $\gamma = 1.2$, $N_T=100$, $N_{BS}=3$ and target node position fixed at (0,0)

Fig. 4.

Performance comparison of proposed ILED algorithm with SLED algorithm under low SNR conditions for $\eta = 1.2$, $\gamma = 1.2$, $N_T=100$, $N_{BS}=3$ and target node position fixed at (0,0)

Figure 3 shows the $\text {E}^{(1D)}$ of the proposed algorithm and SLED algorithm for different normal SNR conditions. As we can see from Fig. 3, the proposed algorithm clearly provides less error when compared to the SLED algorithm. The proposed algorithm reports sub-centimeter accuracy for SNR in between 6 dB and 10 dB and sub-millimeter accuracy for SNR with in 10 dB and 30 dB, while the SLED algorithm reports an accuracy of higher than 1 cm for 6 dB < SNR < 10 dB and sub-centimeter accuracy for 10 dB < SNR < 25 dB.

Figure 4 shows the comparison of ranging accuracy between the proposed algorithm and SLED algorithm, under low SNR conditions. As we can see from Fig. 4, the SLED algorithm is unable to detect the leading edge for SNR < 1 dB, and hence reports a very high error, while the proposed algorithm reports sub-centimeter accuracy for this SNR range. For 0 dB < SNR < 6 dB, the SLED algorithm reports an error of higher than 2 cm, while the proposed ILED algorithm reports sub-centimeter accuracy. Table 1 reports the positioning error for the complete range of SNR.

Table 1. Comparison of positioning error using SLED and ILED algorithms for different SNR in LOS conditions. ’x’ indicates an unacceptably high positioning error.

From these results, we can conclude that the proposed algorithm provides improved accuracy when compared to the SLED algorithm. Especially under low SNR conditions, we can clearly see that the proposed algorithm outperforms the original algorithm.

Fig. 5.

$\text {E}^{(2D)}$ for $\eta = 1.2$, $\gamma = 1.2$, $N_T=100$, $N_{BS}=3$ and target node position is chosen randomly

Fig. 6.

Influence of number of anchor nodes on 2D positioning accuracy for $\eta = 1.2$, $\gamma = 1.2$ and the target position is randomly chosen

3.2 Positioning Accuracy

Monte-Carlo Simulations are performed with target position chosen randomly inside the circumscribed circle of polygon. The target position is estimated using the proposed algorithm and the trilateration described in Sect. 2.2. Positioning accuracy $\text {E}^{(2D)}$ is evaluated as mentioned below in (14).

$$\begin{aligned} \text {E}^{(2D)} = \sqrt{{\frac{1}{N_T}}\sum \limits _{i=1}^{N_T}\left[ ({x^i_{err}})^2+{(y^i_{err})}^2\right] } \end{aligned}$$

(14)

where,

$$\begin{aligned} x^i_{err} = (x_t^i - \hat{x}_t^i), \quad y^i_{err} = (y_t^i - \hat{y}_t^i) \end{aligned}$$

Figure 5 reports the positioning accuracy for different SNR values using 3 anchor nodes. As we can see from Fig. 5, the proposed system reports sub-centimeter accuracy for SNR < 12 dB and sub-millimeter accuracy for 13 dB < SNR < 30 dB. From these results, we can conclude that the proposed ILED algorithm in combination with the least square based trilateration provides high positioning accuracy.

3.3 Influence of Number of Anchor Nodes on the Positioning Accuracy

In order to study the influence of the number of anchor nodes on the positioning accuracy, $\text {E}^{(2D)}$ is determined for 3 to 6 number of anchor nodes. Simulations are performed with target positions chosen randomly inside the circumference of a circle that encloses the polygon vertices. Figure 6 depicts the positioning accuracy for different SNRs and number of anchor nodes. From the figure we can note that the positional accuracy improves with the increase in the number of anchor nodes for each SNR. This is due to an increased coverage of the target by more anchor nodes. Hence, we can conclude that the positioning accuracy of the proposed algorithm can be improved with an additional number of anchor nodes.

4 Conclusion

We propose an algorithm for determining the leading edge of a received UWB signal under Additive White Gaussian Noise (AWGN) conditions for indoor positioning applications. The proposed algorithm estimates accurate target position even under low signal-to-noise ratio (SNR) conditions. The accuracy of the proposed algorithm can be increased by using an additional number of anchor nodes. The proposed method finds its use in precise indoor positioning applications.