Keywords

1 Introduction

Indoor environment is beyond the coverage of GPS. Due to the high-temporal resolution and good obstacle-penetration capabilities of ultra-wide band (UWB) signals, UWB technique has the capability of high precision ranging, which makes it a strong enabler for indoor localization applications [1]. Therefore, UWB is seen as the potential technique for high-definition situation-aware applications such as equipment and personnel tracking, control of home appliances and a large set of emerging wireless sensor networks applications.

For UWB signals, time of arrival (TOA) based ranging can take full advantage of its large bandwidth and time-delay resolution [3]. However, in dense multipath indoor environments, there exists non-line-of-sight (NLOS) conditions [2]. In this case, the first path is not always the strongest path. Thus it is difficult to detect the TOA of first path. This phenomenon severely degrades the ranging and localization performances.

To address this problem, many approaches were proposed to obtain high accuracy first path detection results, such as maximum energy selection (MES), MES searching-back (MES-SB), coherent detection and some threshold-crossing-based methods (TC) [4]. In MES methods, the received signal block with the maximum energy is considered as the firs path. Thus the accuracy of first path detection mainly bases on the length of block. Furthermore, there is a delay between the first path and the path with maximum energy in NLOS conditions, which results in a biased estimation. In TC methods, the energy block which first exceeds the threshold is regarded as the first path. Therefore, the key of TC methods is to set a appropriate threshold. Besides, the mathematical models of ranging was also analyzed to improve the accuracy [5]. These methods depends on prior information. High computational complexity also makes them hard to deploy in real time applications. In recent years, information theory based approaches were proposed to exploit the difference of entropy of random noise and known UWB ranging pulse [6, 7]. These approaches can achieve high precision even in NLOS conditions.

In this paper, due to the difference of entropy of random noise and known UWB ranging pulse, an entropy based first path detection method is analyzed to obtain high accuracy ranging results. Besides, when the number of anchor nodes is not sufficient, some of the indoor users with known location are employed as auxiliary anchor nodes. In this way, sufficient reference nodes are available to achieve high precision localization results. Simulation results show that the proposed approach has high localization precision.

The rest of the paper is organized as follows. Section 2 presents the signal model of indoor UWB systems. The cooperative localization framework is introduced in Sect. 3, simulations and discussions are given in Sect. 4. Finally the paper is concluded in Sect. 5.

2 Signal Model of Indoor UWB System

The most often used UWB pulse signal is Gaussian pulse waveform and its derivatives in various orders. For example, the second order derivative of Gaussian pulse can be written as

$$\begin{aligned} s(t)=\left( 1-4\pi \left( \frac{t-t_d}{\tau _m}\right) ^2\right) \exp {\left( -2\pi \left( \frac{t-t_d}{\tau _m}\right) \right) }, \end{aligned}$$
(1)

where \(t_d\) is the pulse center and \(\tau _m\) is the pulse shape parameter.

In this paper, we consider the high precision localization application of UWB systems in indoor environments. Therefore, channel model of CM1 and CM2 in IEEE 802.15.4a are considered, which are LOS of indoor residential (7–20 m) and NLOS of indoor residential (7–20 m), respectively. The channel model described in IEEE 802.15.4a is a modified classical Saleh-Valenzuela model, in which the paths of UWB signals arrive in clusters. the channel impulse response of this kind of multi-path multi-cluster UWB channel can be expressed as

$$\begin{aligned} h(t)=\sum \limits _{l\mathrm{{ = }}0}^L {\sum \limits _{k\mathrm{{ = }}0}^K {{\alpha _{k\mathrm{{,}}l}}\exp \mathrm{{(}}j{\phi _{k\mathrm{{,}}l}}\mathrm{{)}}\delta \mathrm{{(}}t\mathrm{{ - }}{T_l}\mathrm{{ - }}{\tau _{k\mathrm{{,}}l}}\mathrm{{)}}} }, \end{aligned}$$
(2)

where \(\alpha _{k,l}\) is the gain factor of kth multipath component in the lth cluster. \(T_l\) is the time delay of lth cluster, \(\tau _{k,l}\) is the time delay of kth multipath component in the lth cluster. \(\phi _{k,l}\) denotes the signal phase of kth multipath component in the lth cluster, which is uniformly distributed in [0, 2\(\pi \)). L and K are the number of clusters and paths, respectively.

For given transmitted signal waveform s(t) and the channel impulse response h(t), the received signal can be expressed as

$$\begin{aligned} \begin{aligned} r(t)&=s(t)*h(t)+n(t)\\&= \sum \limits _{l\mathrm{{ = }}0}^L {\sum \limits _{k\mathrm{{ = }}0}^K {{\alpha _{k\mathrm{{,}}l}}\exp \mathrm{{(}}j{\phi _{k\mathrm{{,}}l}}\mathrm{{)}}s\mathrm{{(}}t\mathrm{{ - }}{T_l}\mathrm{{ - }}{\tau _{k\mathrm{{,}}l}}\mathrm{{)}}} } + n(t), \end{aligned} \end{aligned}$$
(3)

where n(t) is the additive white Gaussian noise (AWGN).

Fig. 1.
figure 1

Illustration of the indoor localization system (4 anchor nodes and 3 indoor users).

Full size image

3 Indoor Cooperative Localization Framework

3.1 Cooperative Localization Model

Consider a UWB-based indoor localization system, which adopts the round-trip time-of-flight (RTOF) measurement for ranging. We assume M stationary anchor nodes with known locations and N indoor users with localization requirements in an indoor region. In this system, indoor users sends a certain UWB pulse waveform to the anchors nodes, each anchor node responses with a UWB pulse signal. Then the indoor user can calculate the distances from these anchor nodes. Thereby, the position of indoor user can be calculated. The system is shown in Fig. 1.

However, due to long distance or severe blockage, the communication link between indoor user and the anchor nodes can not always be established effectively. In an indoor localization system show by Fig. 1, if indoor user 3 can not get the response pulse from some of the anchor node (e.g., anchor node 1 and 4 can not received the ranging request from indoor user 3), then only 2 anchor node are employed to locate indoor user 3. In a three-dimension environment, at least 3 anchor nodes are required to get the position of an indoor user. Therefore, a cooperative localization scheme is proposed to locate the indoor user when the number of anchor nodes is not sufficient. Firstly, indoor user 1 and user 2 can get their position by employing the 4 anchor nodes. Then indoor user 3 can send a ranging request to user 1 and user 2 to get the distance between them. In this way, indoor user 1 and user 2 are employed as auxiliary anchor nodes. At last, 5 anchor nodes are available to get the position of indoor user 3.

3.2 Entropy Based TOA Estimation for UWB Ranging

To obtain the position of indoor users, the first step is to estimate the distances between indoor user and these anchor nodes. An entropy based TOA estimation method is proposed to get these distances. The essential difference of noise and UWB signals can be effectively reflected by the entropy. As is known, AWGN is a kind of random signals at the receiver, whereas UWB pulse waveform is a known signal. Therefore, the first path (FP) at the receiver can be precisely estimated by detecting the dramatic decreasing of entropy of the received signals. The procedure of entropy based TOA estimation is shown in Fig. 2.

Fig. 2.
figure 2

Procedure of entropy based TOA estimation.

Full size image

Firstly, a preliminary threshold detection is employ to get a rough FP detection. Based on the variance of noise, the threshold can be

$$\begin{aligned} \eta = \alpha \sigma , \end{aligned}$$
(4)

where \(\sigma \) and \(\alpha \) denote the standard deviation of noise and the constant factor for threshold adjustment, respectively.

Then, the received signals can be expressed as \(\mathbf R\), the size of \(\mathbf R\) is \(N \times K \), where N is the number of frames of the received signal, K is the number of samples per frame. Thus \(\mathbf {R}_{n,k}\) is the kth sample of nth frame. By preliminary threshold detection, the following result can be obtained

(5)

where \(\mathbf {U}\) is a matrix with the same size of \(\mathbf {R}\).

For the kth sample, the sample before the kth index in all frames is regarded as a new sequence, and the subset \(\mathbf{{\Phi }}_{k}=\{l_{n}\}\) can expressed as

$$\begin{aligned}&{l_n} = \mathop {\arg }\limits _m {} \max {} {} m{} {}, \\ s.t. \quad&(a)\quad {\mathbf{{U}}_{n,m}} = 1;\nonumber \\&(b)\quad m < k \nonumber . \end{aligned}$$
(6)

Then, we get the subsets \(\mathbf{{\Phi }}_{k}\) of the received signals. We let \(e_{i}\) be the ith non-repetitive element in \(\mathbf{{\Phi }}_{k}\). Therefore, the entropy is given by

$$\begin{aligned} {E_k} = - \sum \limits _{i = 1}^I {\left( {{p_i}/K} \right) {{\log }_b}\left( {{p_i}/K} \right) }, \end{aligned}$$
(7)

where \(p_{i}\) denotes the occurrence frequency of \(e_{i}\).

In the view of information theory, the largest entropy will be achieved when all non-repetitive elements occur with the same frequency, namely, random distribution. However, for the desired signals, the corresponding entropies are relatively small, because these samples exceed threshold in most cases. In this way, the distances between nodes in this network can be obtained.

3.3 Cooperative Localization

Based on the obtained ranging results, the position of target indoor user can be estimated. If the coordinate of target indoor user is (x, y, z), the coordinates of anchor nodes are \(\{x_{am},y_{am},z_{am}\}_{m=1}^M\). Then we have the following results

$$\begin{aligned} \left\{ \begin{array}{l} \sqrt{{{({x_{a1}} - x)}^2} + {{({y_{a1}} - y)}^2} + {{({{z}_{a1}} - z)}^2}} = {d_{a1}}\\ \sqrt{{{({x_{a2}} - x)}^2} + {{({y_{a2}} - y)}^2} + {{({{z}_{a2}} - z)}^2}} = {d_{a2}}\\ \qquad \qquad \qquad ...\\ \sqrt{{{({x_{aM}} - x)}^2} + {{({y_{aM}} - y)}^2} + {{({{z}_{aM}} - z)}^2}} = {d_{aM}} \end{array}. \right. \end{aligned}$$
(8)

In (8) there are 3 variables, if the number of anchor nodes M is less than 3, the position of target user can not be estimated precisely. Therefore, in this paper some of the indoor users are employed as auxiliary anchor nodes, their coordinates are \(\{x_{un},y_{un},z_{un}\}_{n=1}^{N-1}\), then we have

$$\begin{aligned} \left\{ \begin{array}{l} \sqrt{{{({x_{u1}} - x)}^2} + {{({y_{u1}} - y)}^2} + {{({{z}_{u1}} - z)}^2}} = {d_{u1}}\\ \sqrt{{{({x_{u2}} - x)}^2} + {{({y_{u2}} - y)}^2} + {{({{z}_{u2}} - z)}^2}} = {d_{u2}}\\ \qquad \qquad \qquad ...\\ \sqrt{{{({x_{u(N-1)}} - x)}^2} + {{({y_{u(N-1)}} - y)}^2} + {{({{z}_{u(N-1)}} - z)}^2}} = {d_{u(N-1)}} \end{array}. \right. \end{aligned}$$
(9)

The position of target indoor user can be obtained by solving the following minimum optimization problem

$$\begin{aligned} \begin{aligned} \min \Bigg (\sum \limits _{m = 1}^M&{\left| {\sqrt{{{\left( {x - {x_{am}}} \right) }^2} + {{\left( {y - {y_{am}}} \right) }^2} + {{\left( {z - {z_{am}}} \right) }^2}} - {{\hat{d}}_{am}}} \right| } \\&+ {\sum \limits _{n = 1}^{N-1} {\left| {\sqrt{{{\left( {x - {x_{un}}} \right) }^2} + {{\left( {y - {y_{un}}} \right) }^2} + {{\left( {z - {z_{un}}} \right) }^2}} - {{\hat{d}}_{un}}} \right| }} \Bigg ), \end{aligned} \end{aligned}$$
(10)

where \(\hat{d}_{am}\) and \(\hat{d}_{un}\) are the estimation of \(d_{am}\) and \(d_{un}\), respectively. In this paper, the least square error (LSE) estimator is employed to solve (10).

Fig. 3.
figure 3

Entropy based first path detection.

Full size image
Fig. 4.
figure 4

Localization accuracy comparison in RMSE.

Full size image

4 Simulations and Discussions

In this section, the proposed cooperative localization scheme is evaluated. A indoor environment shown in Fig. 1 is considered. The length, width and height of this cubic region are 25 m, 10 m and 5 m, respectively. 4 anchor nodes are placed at the corners of this region. 3 indoor users are in this region. It is assumed that anchor node 1 and 4 can not received the ranging request from indoor user 3, then only 2 anchor node are employed to locate indoor user 3. In this case, indoor user 1 and user 2 get their own location firstly, then they are employed as auxiliary anchor nodes to obtain localization result for indoor user 3.

4.1 Precision of Entropy Based First Path Detection

The performance of first path detection is evaluated in IEEE 802.15.4a CM1 and CM2 channel, which is shown in Fig. 3(a) and (b), respectively. It can be seen from Fig. 3 that the entropy amplitude has a significant decline when the first path of UWB arrives. This is because for random noise, the entropy altitude has a high value, whereas the UWB signals are known signals at the receiver, thus it has a very low entropy. When the SNR of received signal is 20 dB, the TOA estimation errors in CM1 and CM2 channel are 0.06 ns and 0.14 ns, respectively.

4.2 Precision of Cooperative Localization

The precision of the proposed cooperative localization scheme is also evaluated by comparing with existing approaches. The ranging results obtained by MES, TC, coherent detection, as well as the proposed entropy based method are employed to get the location of indoor user 3 by solving Eq. (10) through least square error method. The results are shown in Fig. 4. It shows that the root mean square error (RMSE) of localization decreases when the SNR of received signal increases. The proposed entropy based cooperative localization scheme always has a better performance than existing approaches. In CM1 channel, which is a LOS channel, the RMSE is less than 1 cm when SNR is higher than 5 dB. In CM2 channel, which is a NLOS channel, The RMSE is less than 10 cm when SNR is higher than 5 dB. This is because in NLOS channel, the energy of first path is too weak to be precisely detected.

5 Conclusions

In this paper, a cooperative localization scheme is proposed for high precision localization applications in indoor environments. The differences between random noise and known UWB signal are exploited by calculating the entropy of received signal to obtain a high accuracy TOA estimation result. Besides, when the number of anchor nodes is not sufficient, we propose a cooperative localization method, where the indoor users with known locations are employed as auxiliary anchor nodes to obtain localization result for the target indoor user. Performance evaluation results show that the proposed cooperative localization scheme can achieve high accuracy localization results in both LOS and NLOS conditions. Hence, the proposed cooperative localization scheme can be a promising solution for high precision localization requirements in indoor harsh environments.