A Low Complexity Asynchronous UWB TDOA Localization Method

Abstract

Impulse-radio ultrawideband (IR-UWB) is a promising technique for indoor localization due to its high accuracy and robustness against multipath interferences. In this paper, to deal with the synchronization challenges among anchors in traditional time-difference-of-arrival (TDOA) localization systems, we propose an asynchronous TDOA (ATDOA) localization method. Based on the ranging error model, we derive the theoretical lower bounds as the performance metrics of localization accuracy. Compared with the ideal TDOA method, ATDOA degrades on localization accuracy for eliminating the high accuracy synchronization requirements, which is pretty much attractive in energy and complexity limited scenarios. Based on the performance analysis, we show that there exists optimal anchor deployment in ATDOA that minimizes the localization errors. We also formulate the relationship between this optimal deployment and the size of the covered area, which is meaningful in both theoretical analysis and practical system designs.

1. Introduction

Due to its advantages such as high temporal resolution and multipath immunity, impulse-radio ultrawideband (IR-UWB) is well suited for high accuracy ranging and localization, such as warehouse, people monitoring, and interactive gaming [1, 2].

Typical localization systems contain several anchor nodes with known positions. Range measurements are firstly conducted between the anchors and the agents whose positions are unknown yet. Depending on whether the measured range is absolute or relative, time of arrival (TOA) and time difference of arrival (TDOA) are both widely used for position estimation, respectively [3].

TDOA localization is attractive due to its unlimited users under ideal conditions. One famous example is the global positioning system (GPS). Another advantage is that agents are not required to transmit signals in TDOA, which is preferred in most energy-restricted and multiple-user scenarios, such as wireless sensor networks (WSNs).

On the other hand, since each node has its local clock that works independently, all anchors must be synchronized to estimate the absolute arrival time of the received signal in TDOA localization. High accuracy synchronization among anchors is one of the biggest challenges in TDOA system implementations [4]. Reference broadcast synchronization (RBS) is a popular method to achieve network synchronization [5]. In RBS, the reference node broadcasts a reference signal to all anchors which are prelocated at fixed positions. It is able to achieve the accuracy at μs level by RBS, which is not adequate for high accuracy positioning requirements. Pairwise synchronization is also an option [6], which exploits a typical way by exchanging messages between anchors to achieve synchronization. However, a large number of beacon packets for synchronization are generated for the peer-to-peer synchronization. Thereby, a very long synchronization time is required for the whole network, which is also not recommended in most real-time scenarios. Some similar methods based on the wire connections between anchors are given in [7]. However, they are all impractical and inconvenient in wireless applications.

Some recent work considered the use of TOA measurements to perform joint localization and synchronization [8, 9]. The authors in [10] present methods that achieve localization and synchronization simultaneously. We also find that TDOA can be derived from a general TOA framework for joint localization and synchronization as a special case.

Another issue to be addressed is the anchor deployment. Proper anchor geometric design can highly improve the localization accuracy [11–13]. Reference [14] suggests that, for 2D localization, optimal positions of M anchors are at the vertices of an M-sided regular polygon, and then the best geometric dilution of precision (GDOP) will be found when the target is located at the center of the polygon.

In [15, 16], optimal geometric deployment of anchors is studied by minimizing the CRLB of TDOA localization with a prelocated agent. The conclusions drawn from these researches are under the assumption that the target is prelocated at the center of anchor nodes, which can not be satisfied in practical systems. Reference [17] extends the optimal anchor nodes placement to practical applications by evaluating the average horizontal dilution of precision (HDOP) and vertical dilution of precision (VDOP). However, the results are obtained under the assumption that the path loss has no effect on ranging errors. The discussion of positioning performance with anchor deployment is also given in [18] based on TOA estimation. But to the best of the authors' knowledge, few practical suggestions on how to design the anchors' deployment are given.

In this paper, aiming at the previous discussed issues, the following contributions are made:

• (i)

To mitigate the synchronization challenge, we present an asynchronous TDOA (ATDOA) localization method using IR-UWB signals. The synchronization requirements among anchors are eliminated, which is able to reduce the system complexity.

(ii)

The error model of ATDOA is derived in terms of the fundamental limits. We use the Cramer-Rao lower bound (CRLB) to perform system evaluations. Practical issues such as clock drifts and path loss effects are considered.

(iii)

We study the optimal anchor deployment with no a priori knowledge available on the agents' positions. According to the error model of ATDOA, we show that there exists simple anchor deployment in the 2D scenario, by which the minimum average CRLB of localization errors can be achieved. It is meaningful for high accuracy and energy efficient localization system design.

2. Asynchronous TDOA Localization Method

In this section, the ATDOA localization method is introduced. We first give a general network scenario, inside which the localization strategy can be carried out.

2.1. Network Model

Consider a typical small scale WSN scenario, such as wireless personal area network (WPAN). There are $N_a+N_b$ nodes as depicted in Figure 1, including $N_b$ prelocated anchors and $N_a$ agents with unknown positions to be estimated. Anchors are identical to agents in capabilities, except that their positions are known. The set of agents is denoted by ${\mathcal{N}}_a=\{\mathrm{1,2},\dots ,N_a\}$ , while the set of anchors is ${\mathcal{N}}_b=\{\mathrm{1,2},\dots ,N_b\}$ . The position of node k is denoted by ${\mathbf{p}}_k\triangleq [x_k,y_k{]}^T$ , where $k\in {\mathcal{N}}_a\cup {\mathcal{N}}_b$ .

Figure 1

Network model.

2.2. Asynchronous TDOA Localization Method

Some statements for ATDOA localization are claimed below before the algorithm details are presented:

• (i)

There is no synchronization among any nodes in the network.

(ii)

Since it is a small scale network, all nodes are within the coverage of each anchor.

(iii)

The packet transmitted by anchor i consists of UWB signals, which contains the position of original anchor ${\mathbf{p}}_i$ , where $i\in {\mathcal{N}}_b$ .

(iv)

Anchor 1 is selected as the localization initiator, while all agents are kept silent during the whole procedure.

Then, the ATDOA localization method mainly involves the following four steps. Note that here we take one agent as an example, and all other agents can be treated equally and simultaneously:

• (1)

Anchor 1 broadcasts its position to the whole network in a packet by UWB signals.

(2)

After receiving the packet from anchor 1 by TOA estimation, other anchors ( $i\in \{\mathrm{2,3},\dots ,N_b\}$ ) reply their positions by broadcast immediately.

(3)

Each agent records the arrival time ${\widehat{t}}_i$ , $i\in {\mathcal{N}}_b$ , from all anchors, respectively.

(4)

Position estimation is performed on the agent based on the TDOA measurements and anchors' positions.

As shown in Figure 2, the following notations are used in the localization process. The distance between anchor i and anchor 1 is denoted by $d_{i\mathrm{1}}$ , which is available beforehand. The estimated distance difference between the direct coupled signal from anchor $\mathrm{1}$ and the indirect signal from anchor i ( $i=\mathrm{2,3},\dots ,N_b$ ) is denoted by ${\widehat{r}}_{i\mathrm{1}}$ . ${\widehat{t}}_j$ is the TOA estimates of the signals from anchor j ( $j=\mathrm{1,2},\dots ,N_b$ ) by the agent. The position of each agent can be obtained by solving the following hyperbolic equations:

$$\begin{array}{cc}& {\widehat{r}}_{\mathrm{21}}=c\left({\widehat{t}}_{\mathrm{2}}-{\widehat{t}}_{\mathrm{1}}\right)=d_{\mathrm{21}}+{\widehat{d}}_{\mathrm{2}}-{\widehat{d}}_{\mathrm{1}}\\ {\widehat{r}}_{\mathrm{31}}=c\left({\widehat{t}}_{\mathrm{3}}-{\widehat{t}}_{\mathrm{1}}\right)=d_{\mathrm{31}}+{\widehat{d}}_{\mathrm{3}}-{\widehat{d}}_{\mathrm{1}}\\ ⋮\\ {\widehat{r}}_{M\mathrm{1}}=c\left({\widehat{t}}_M-{\widehat{t}}_{\mathrm{1}}\right)=d_{M\mathrm{1}}+{\widehat{d}}_M-{\widehat{d}}_{\mathrm{1}},\end{array}$$

(1)

where ${\widehat{d}}_j=\sqrt{(\widehat{x}-x_j{)}^{\mathrm{2}}+(\widehat{y}-y_j{)}^{\mathrm{2}}}$ is the estimated distance between the agent and anchor j. c is the speed of light. From the geometric point of view, the agent is seated in the intersection of hyperbolas with anchors as foci which is depicted in Figure 3. Anchor 1 is always one of the foci in each hyperbola. Solving (1) is actually not a simple task, since the global convergence is not guaranteed. One option is to perform a local search by iterative algorithms such as Newton-Raphson, Gauss-Newton, and steepest descent methods around an initial position estimate ${\widehat{\mathbf{p}}}^{(\mathrm{0})}$ . If ${\widehat{\mathbf{p}}}^{(\mathrm{0})}$ is sufficiently close to p, it is expected that $\widehat{\mathbf{p}}$ can be obtained after an iterative procedure. One regular estimate of   ${\widehat{\mathbf{p}}}^{(\mathrm{0})}$ can be given by linear least square method (LLS) [19].

Figure 2

ATDOA demonstration.

Figure 3

Geometric explanations of ATDOA.

Based on the steps of ATDOA, the reason why no synchronization is needed among nodes is that all TOA estimates are recorded based on the clock of anchor 1, which can be regarded as a reference clock for the network. Since the agents only perform independent signal receiving during the localization, unlimited number of users can be adopted within the network theoretically.

3. Performance Analysis for ATDOA Localization

In this part, the performance analysis is carried out in terms of the fundamental limits. We choose the widely applied Cramer-Rao lower bound (CRLB) as the performance metric. Although the CRLB is a lower bound, which is not guaranteed to be achieved, it offers meaningful performance benchmarks of the proposed method. In addition, that CRLB is a tight bound in the high SNR regime.

3.1. Ranging Error Modeling

Based on the ATDOA localization process, since all agents are working independently, our analysis is started with one single agent, which can be easily extended to the whole network. To obtain the equations in (1), the anchor i ( $i=\mathrm{2,3},\dots ,N_b$ ) is required to perform TOA estimation once with anchor 1 before retransmitting the signals. On the other hand, the agent is required to perform TOA estimation both on the direct signals from anchor $\mathrm{1}$ and the retransmitted signals from other anchors. During our ranging error modeling, the true agent position is represented as $\mathbf{p}={\left[\begin{array}{cc}x& y\end{array}\right]}^T$ , while the ith anchor's position is denoted by ${\mathbf{p}}_i={\left[\begin{array}{cc}{x}_i& y_i\end{array}\right]}^T$ . $w_i$ is the TOA estimation error performed by the agent with anchor i. Therefore, the estimated range difference is modeled as

$$\begin{array}{cc}& {\widehat{r}}_{i\mathrm{1}}=c\left({\widehat{t}}_i-{\widehat{t}}_{\mathrm{1}}\right)=c\left(\left(t_i+w_i\right)-\left(t_{\mathrm{1}}+w_{\mathrm{1}}\right)\right)={\widehat{d}}_{i\mathrm{1}}+{\widehat{d}}_i-{\widehat{d}}_{\mathrm{1}}=‖{\mathbf{p}}_i-{\mathbf{p}}_{\mathrm{1}}‖+‖\widehat{\mathbf{p}}-{\mathbf{p}}_i‖-‖\widehat{\mathbf{p}}-{\mathbf{p}}_{\mathrm{1}}‖.\end{array}$$

(2)

One of the main error sources in UWB ranging is the multipath environment. In most research, the ranging errors are modeled as zero mean Gaussian variables, especially under line-of-sight (LOS) conditions [18, 20]. The variance is dependent on the measured range, as signals are attenuated with the propagation distance; that is,

$$\begin{array}{cc}& {\sigma }_{\mathrm{1}}^{\mathrm{2}}=\mathrm{var}\left(w_{\mathrm{1}}\right)={\sigma }_{\mathrm{0}}^{\mathrm{2}}·d_{\mathrm{1}}^{\alpha },\\ {\sigma }_i^{\mathrm{2}}=\mathrm{var}\left(w_i\right)={\sigma }_{\mathrm{0}}^{\mathrm{2}}·\left(d_{i\mathrm{1}}^{\alpha }+d_i^{\alpha }\right),\end{array}$$

(3)

where α is the path loss component and ${\sigma }_{\mathrm{0}}^{\mathrm{2}}$ is the variance of ranging error at reference distance $d_{\mathrm{0}}$ .

The variance of the error in range difference measurements can be obtained based on the results above:

$$\begin{array}{cc}& \mathrm{var}\left(w_i-w_{\mathrm{1}}\right)={\sigma }_{\mathrm{1}}^{\mathrm{2}}+{\sigma }_i^{\mathrm{2}}={\sigma }_{\mathrm{0}}^{\mathrm{2}}\left(d_{\mathrm{1}}^{\alpha }+d_{i\mathrm{1}}^{\alpha }+d_i^{\alpha }\right).\end{array}$$

(4)

3.2. Derivation of CRLB

CRLB is the theoretical minimum variance of any unbiased estimators, which is a useful benchmark for performance evaluation [21]. Based on the estimation theory, the variance of the position estimates $\widehat{\mathbf{p}}={\left[\begin{array}{cc}\widehat{x}& \widehat{y}\end{array}\right]}^T$ satisfies

$$\begin{array}{cc}& \mathbb{E}\left[{\left(\widehat{\mathbf{p}}-\mathbf{p}\right)}^T\left(\widehat{\mathbf{p}}-\mathbf{p}\right)\right]\ge \mathrm{C}\mathrm{R}\mathrm{L}\mathrm{B}=\mathrm{t}\mathrm{r}\left[{\mathbf{I}}_{\mathbf{p}}^{-\mathrm{1}}\right],\end{array}$$

(5)

where $\mathrm{t}\mathrm{r}[·]$ is the matrix trace and ${\mathbf{I}}_{\mathbf{p}}$ is the Fisher information matrix (FIM) of the position estimates, defined as

$$\begin{array}{cc}& {\left[{\mathbf{I}}_{\mathbf{p}}\right]}_{ij}=-\mathbb{E}\left[\frac{{\partial }^{\mathrm{2}}\ln p\left(\mathbf{r};\mathbf{p}\right)}{\partial {\mathbf{p}}_i\partial {\mathbf{p}}_j}\right].\end{array}$$

(6)

For 2D localization, the CRLB of $\widehat{x}$ and $\widehat{y}$ is (1,1) and (2,2) elements of ${\mathbf{I}}^{-\mathrm{1}}$ , respectively. In ATDOA method, the components of FIM are

$$\begin{array}{cc}& I_{\mathrm{11}}={\displaystyle \sum }_{i=\mathrm{2}}^M\frac{{\left(A_i-A_{\mathrm{1}}\right)}^{\mathrm{2}}}{{\sigma }_{i\mathrm{1}}^{\mathrm{2}}}+\frac{{\alpha }^{\mathrm{2}}}{\mathrm{2}}{\displaystyle \sum }_{i=\mathrm{2}}^M\frac{{\left(A_{\mathrm{1}}{d}_{\mathrm{1}}^{\alpha -\mathrm{1}}+A_i{d}_i^{\alpha -\mathrm{1}}\right)}^{\mathrm{2}}}{{\left(d_{\mathrm{1}}^{\alpha }+d_i^{\alpha }\right)}^{\mathrm{2}}},\\ I_{\mathrm{22}}={\displaystyle \sum }_{i=\mathrm{2}}^M\frac{{\left(B_i-B_{\mathrm{1}}\right)}^{\mathrm{2}}}{{\sigma }_{i\mathrm{1}}^{\mathrm{2}}}+\frac{{\alpha }^{\mathrm{2}}}{\mathrm{2}}{\displaystyle \sum }_{i=\mathrm{2}}^M\frac{{\left(B_{\mathrm{1}}{d}_{\mathrm{1}}^{\alpha -\mathrm{1}}+B_i{d}_i^{\alpha -\mathrm{1}}\right)}^{\mathrm{2}}}{{\left(d_{\mathrm{1}}^{\alpha }+d_i^{\alpha }\right)}^{\mathrm{2}}},\\ I_{\mathrm{12}}=I_{\mathrm{21}}={\displaystyle \sum }_{i=\mathrm{2}}^M\frac{\left(A_i-A_{\mathrm{1}}\right)\left(B_i-B_{\mathrm{1}}\right)}{{\sigma }_{i\mathrm{1}}^{\mathrm{2}}}+\frac{{\alpha }^{\mathrm{2}}}{\mathrm{2}}{\displaystyle \sum }_{i=\mathrm{2}}^M\frac{\left(A_{\mathrm{1}}{d}_{\mathrm{1}}^{\alpha -\mathrm{1}}+A_i{d}_i^{\alpha -\mathrm{1}}\right)\left(B_{\mathrm{1}}{d}_{\mathrm{1}}^{\alpha -\mathrm{1}}+B_i{d}_i^{\alpha -\mathrm{1}}\right)}{{\left(d_{\mathrm{1}}^{\alpha }+d_i^{\alpha }\right)}^{\mathrm{2}}},\end{array}$$

(7)

where

$$\begin{array}{cc}& A_i=\frac{x-x_i}{\sqrt{{\left(x-x_i\right)}^{\mathrm{2}}+{\left(y-y_i\right)}^{\mathrm{2}}}},\\ B_i=\frac{y-y_i}{\sqrt{{\left(x-x_i\right)}^{\mathrm{2}}+{\left(y-y_i\right)}^{\mathrm{2}}}}.\end{array}$$

(8)

Then, the CRLB of TDOA method is

$$\begin{array}{cc}& \mathrm{C}\mathrm{R}\mathrm{L}\mathrm{B}=\frac{I_{\mathrm{11}}+I_{\mathrm{22}}}{I_{\mathrm{11}}{I}_{\mathrm{22}}-I_{\mathrm{12}}{I}_{\mathrm{21}}}.\end{array}$$

(9)

The details in derivation are given in the Appendix.

3.3. Numeric Results Compared with Ideal TDOA

In Figure 4, the performance between ATDOA and perfectly synchronized TDOA is compared by the average CRLB. ATDOA is only about 0.7 dB worse due to the additional transmission from anchor 1 to the other anchor (from anchor 2 to $N_b$ ). However, the proposed method is low complexity and low cost by eliminating synchronization requirement, which is particularly important in energy constrained scenarios.

Figure 4

Performance comparison between ATDOA and ideal TDOA.

3.4. Clock Drift Considerations

Besides the multipath propagation, clock drift is another main error source in UWB ranging and localization [22]. As we know, there always exists a clock drift between two individual oscillators, especially in the low cost networks. In ATDOA, the clock in anchor 1 is regarded as the reference clock during ATDOA localization. $e_i$ and $e_a$ are used to denote the relative clock drift of anchor i and agent, respectively ( $i=\mathrm{2,3},\dots ,N_b$ ).

In step 2 of ATDOA, it requires anchor i to retransmit the UWB signals immediately. Actually, it is impossible for practical systems. A processing time ${\tau }_d$ is required to perform signal receiving and transmitting, which can be known beforehand depending on the system design. Therefore, without considering the clock drift effects, (1) can be extended as

$$\begin{array}{cc}& c\left({\widehat{t}}_{\mathrm{2}}-{\widehat{t}}_{\mathrm{1}}\right)=d_{\mathrm{21}}+{\widehat{d}}_{\mathrm{2}}-{\widehat{d}}_{\mathrm{1}}+c{\tau }_d\\ c\left({\widehat{t}}_{\mathrm{3}}-{\widehat{t}}_{\mathrm{1}}\right)=d_{\mathrm{31}}+{\widehat{d}}_{\mathrm{3}}-{\widehat{d}}_{\mathrm{1}}+c{\tau }_d\\ ⋮\\ c\left({\widehat{t}}_M-{\widehat{t}}_{\mathrm{1}}\right)=d_{M\mathrm{1}}+{\widehat{d}}_M-{\widehat{d}}_{\mathrm{1}}+c{\tau }_d.\end{array}$$

(10)

Note that ${\tau }_d$ is the time based on the calibration from the oscillator in anchor i. Since the ATDOA computation is finally performed on the agent, the corresponding processing time on the agent oscillator is ${\widehat{\tau }}_d={\tau }_d(\mathrm{1}+e_a)/\left(\mathrm{1}+e_i\right)$ :

$$\begin{array}{cc}& {\widehat{r}}_{i\mathrm{1}}=c\left({\widehat{t}}_{\mathrm{2}}-{\widehat{t}}_{\mathrm{1}}\right)-c{\widehat{\tau }}_d=c\left(\left(t_i+w_i\right)-\left(t_{\mathrm{1}}+w_{\mathrm{1}}\right)\right)-c\left({\tau }_d+\frac{{\tau }_d\left(e_a-e_i\right)}{\mathrm{1}+e_i}\right)=d_{i\mathrm{1}}+{\widehat{d}}_i-{\widehat{d}}_{\mathrm{1}}.\end{array}$$

(11)

Based on the discussion above, the ranging error ${\xi }_i$ during one measurement can be modeled as ${\xi }_i~N\left(-c{\tau }_d\left(e_a-e_i\right)/\left(\mathrm{1}+e_i\right),{\sigma }_{\mathrm{0}}^{\mathrm{2}}(d_{\mathrm{1}}^{\alpha }+d_{i\mathrm{1}}^{\alpha }+d_i^{\alpha })\right)$ . Define the relative clock drift as ${\epsilon }_i=e_a-e_i$ , and $e_i\ll \mathrm{1}$ ; the expectation of ${\xi }_i$ is

$$\begin{array}{cc}& {\mu }_i\approx c{\epsilon }_i{\tau }_d.\end{array}$$

(12)

From (12), it can be seen that the bias of ranging error during ATDOA localization is decided by the product of relative clock drift ${\epsilon }_i$ and processing delay ${\tau }_d$ , which is more clearly shown in Figure 5. For example, when the processing delay is shorter than 10 ms, the relative clock drift is required to be under 20 ppm, under which the ranging error expectation will be less than 5 cm.

Figure 5

Error introduced by clock drift.

During ATDOA localization, both ${\mu }_i$ and ${\sigma }_i^{\mathrm{2}}$ take effect independently. In Figure 6, we define root mean square error (RMSE) as the performance metrics; that is,

$$\begin{array}{cc}& \mathrm{R}\mathrm{M}\mathrm{S}\mathrm{E}=\sqrt{\frac{{\sum }_{i=\mathrm{1}}^{N_a}{\left(‖{\widehat{\mathbf{p}}}_i-{\mathbf{p}}_i‖\right)}^{\mathrm{2}}}{N_a}}.\end{array}$$

(13)

A large number of agents ( $N_a=\mathrm{10000}$ ) are randomly deployed within an area, and $N_b=\mathrm{5}$ prelocated anchors are utilized to perform ATDOA localization. The ranging bias expectation ${\mu }_{\mathrm{a}\mathrm{v}\mathrm{g}}$ caused by clock drift is set uniformly from $\mathrm{1.2}\times \mathrm{1}{\mathrm{0}}^{-\mathrm{2}}$  m to $\mathrm{1.08}\times \mathrm{1}{\mathrm{0}}^{-\mathrm{1}}$  m, while ${\sigma }_{\mathrm{0}}^{\mathrm{2}}=\mathrm{2.5}\times \mathrm{1}{\mathrm{0}}^{-\mathrm{3}}$ , and $\alpha =\mathrm{1.7}$ [23]. The results are shown in Figure 6.

Figure 6

RMSE performance of ATDOA.

It is quite clear that localization performance degrades when the ranging error is increasing. However, it should be noticed that μ and ${\sigma }^{\mathrm{2}}$ are from two independent error sources. Clock drift error is introduced from the hardware design, which can only be mitigated by choosing better oscillators or trying to decrease the processing time ${\tau }_d$ by multiple transmissions [24]. Both are difficult for low complexity energy efficient systems. On the other hand, from the analysis in Section 3.1, the ranging error variance is highly dependent on the anchor deployment. Therefore, some valuable instructions on anchor deployment are given based on the Cramer-Rao lower bound (CRLB) analysis in the next section.

4. Discussions on the Anchor Deployment Strategy

According to the analysis in the previous section, we study the anchor deployment of ATDOA based on the numeric results achieved. It can be concluded that there exists an optimal deployment strategy within a certain covered area. We also formulate the mathematical model between the deployment and the size of area, which is meaningful to the practical system design.

4.1. Network Settings

We first show that the performance evaluation is based on the following assumptions:

• (i)

Without loss of generality, the localization area of interest is approximated as a circle for simplicity, whose radius R varies from 4 m to 7 m, which is a typical indoor scenario.

(ii)

As the agent could be placed anywhere within the area with equal likelihood, an average CRLB is applied for the uncertainty of agent positions. Multiple possible positions ( $N=\mathrm{18000}$ ) are used in our analysis.

(iii)

Average CRLB is defined as

$$\begin{array}{cc}& \mathrm{C}\mathrm{R}\mathrm{L}\mathrm{B}=\frac{{\sum }_{i=\mathrm{1}}^N\mathrm{C}\mathrm{R}\mathrm{L}\mathrm{B}\left(i\right)}{N}.\end{array}$$

(14)

(iv)

Since ranging is performed in typical indoor environments, path loss component α is considered uniformly distributed between 1.7 and 4. Both 1.7 and 4 are typical LOS/NLOS path loss values proposed in [23]. The reference ranging error variance is chosen as ${\sigma }_{\mathrm{0}}^{\mathrm{2}}=\mathrm{2.5}\times \mathrm{1}{\mathrm{0}}^{-\mathrm{3}}$ , which is typical in UWB ranging with $d_{\mathrm{0}}=\mathrm{1}$  m obtained from practical measurements [25].

(v)

$N_b$ anchors are prelocated at the vertices of an $N_b$ -sided regular polygon as depicted in Figure 7, which is the suggested deployment without any a priori information available [18]. The distance between each anchor node and the center is r   $(r\le R)$ , and the coordinates of ith anchor are

$$\begin{array}{cc}& x_i=r\cos \frac{\mathrm{2}\pi \left(i-\mathrm{1}\right)}{N_b},\\ y_i=r\sin \frac{\mathrm{2}\pi \left(i-\mathrm{1}\right)}{N_b},\\ \hspace{1em}i=\mathrm{1,2},\dots ,N_b.\end{array}$$

(15)

Figure 7

Localization system description.

4.2. Existence of Optimal r

From the results in Figure 8, two conclusions can be drawn:

• (i)

First, the average CRLB decreases with increasing anchors. This is similar to traditional localization methods. Extra 0.5 to 1 dB gain can be obtained by adding one more anchor according to our results. However, this is not a preferred option in energy efficient scenarios, since more anchors require more power consumption and system complexity.

(ii)

It is obvious that reasonable anchors deployment is able to improve the system performance. From the results in Figure 8, there exists an optimal anchor deployment circle radius $r^{\star }$ , which is able to achieve the best accuracy results by ATDOA localization. For example, choosing $-\mathrm{1.8}\hspace{0.17em}\mathrm{d}\mathrm{B}{\mathrm{m}}^{\mathrm{2}}$ as the performance threshold, it can be seen from Table 1 that only 5 anchors are required if they are prelocated with $r^{\star }$ . On the contrary, if  r is chosen larger than 4 meters, more than 8 anchors are required, which leads to poor system efficiency. The reason for the existence of $r^{\star }$ is that if  r is too small, which means that the anchors are deployed in a more “centralized” fashion, the agents outside will suffer severely from it. On the other hand, if anchors are prelocated in highly “distributed” fashion (with a big r), this prevents the agents near the center from achieving high localization accuracy.

Table 1

Anchor number with respect to a certain accuracy.

$N_b$	r (m)
5	1.6
6	2.5
7	3.3
8	4

Figure 8

Numeric results with different r.

4.3. Mathematical Modeling of Optimal r

In order to make use of the optimal r for system design, a simplified model is given here. We take $N_b=\mathrm{6}$ as an example; it indicates that $r^{\star }$ changes with respect to the area radius R in Figure 9. Numeric results of $r^{\star }$ and R are listed in Table 2. Linear approximation is applied for $r^{\star }$ modeling:

$$\begin{array}{cc}& r=aR+b,\end{array}$$

(16)

which can be expressed as

$$\begin{array}{cc}& \mathbf{y}=\mathbf{A}\mathbf{\theta }\mathbf{,}\end{array}$$

(17)

where $\mathbf{y}=[r(\mathrm{4}),r(\mathrm{5}),r(\mathrm{6}),r(\mathrm{7}){]}^T$ and $\mathbf{\theta }=[a,b{]}^T$ . And

$$\begin{array}{cc}& \mathbf{A}=\left[\begin{array}{cc}\mathrm{4}& \mathrm{1}\\ \mathrm{5}& \mathrm{1}\\ \mathrm{6}& \mathrm{1}\\ \mathrm{7}& \mathrm{1}\end{array}\right].\end{array}$$

(18)

Table 2

Optimal r with respect to the area radius.

R (m)	$r^{\star }$
4	1.2
5	1.6
6	2.1
7	2.5

Figure 9

Optimal r modeling.

Using the least square (LS) method, θ can be calculated as

$$\begin{array}{cc}& \mathbf{\theta }={\left({\mathbf{A}}^T\mathbf{A}\right)}^{-\mathrm{1}}{\mathbf{A}}^T\mathbf{y}={\left[\mathrm{0.44},-\mathrm{0.57}\right]}^T.\end{array}$$

(19)

Then, (16) is

$$\begin{array}{cc}& r=\mathrm{0.44}R-\mathrm{0.57}.\end{array}$$

(20)

This result can be useful, for it provides insight into system design in different areas in order to achieve an optimal tradeoff between performance and energy consumption.

5. Conclusion

In this paper, a low complexity asynchronous TDOA (ATDOA) localization method using UWB signals is proposed. Based on the measurement error model, the performance of ATDOA is evaluated by both CRLB and RMSE. Generally speaking, ATDOA pays costs on localization performance for eliminating the high accuracy synchronization requirements, which is attractive in energy efficient applications. Based on the performance analysis, we show that there exists an appropriate anchor deployment strategy that minimizes the localization errors. Closed form between this anchor deployment and the localization area is given, which is meaningful for practical system designs.