Sage Journals: Discover world-class research

Abstract

A widely used scheme for target localization is to measure the time of arrival of a wireless signal emitted by a tag, which requires the clocks of the anchors (receivers at known locations) to be accurately synchronized. Conventional systems rely on transmissions from a timing reference node at a known location for clock synchronization and therefore are susceptible to reference node failure. In this article, we propose a novel localization scheme which jointly estimates anchor clock offsets and target positions. The system does not require timing reference nodes and is completely passive (non-intrusive). The positioning algorithm is formulated as a maximum likelihood estimation problem, which is solved efficiently using an iterative linear least square method. The Cramér–Rao lower bound of positioning error is also analyzed. It is shown that the performance of the proposed scheme improves with the number of targets in the system and approaches that of a system with perfectly synchronized anchors.

Keywords

passive localization time of arrival clock synchronization

Introduction

Wireless positioning¹ has attracted significant research interest in recent years due to its widespread applications. Various techniques have been developed for positioning, including those based on received signal strength (RSS) fingerprinting, round trip ranging (RTR), time of flight (TOF), time of arrival (TOA), and time difference of arrival (TDOA). Time-based approaches do not require site surveying as fingerprinting-based techniques and typically achieve higher accuracy than the RSS-based approaches. In particular, one of the most widely used schemes for target localization is to measure the TOA of a wireless signal emitted by a tag, which keeps the cost and power consumption of the tags low and can be used to locate existing commercial off-the-shelf devices (e.g. WiFi devices).²

To locate a target based on TOA measurements, the clocks of the anchors need to be precisely synchronized. Particularly, the clock skew and clock offset of each anchor need to be estimated and compensated.³ This is conventionally achieved by reference-broadcast synchronization,^2,3 which estimates the clock skew and offset among anchors based on the TOA of beacons transmitted by a timing reference node (RN) at a known location. The drawback of this scheme is that the system is susceptible to the failure of the timing RN. In addition, the transmission of the timing RN may interfere with those of the targets and compromise the operation of the targets (e.g. in the case of tracking WiFi devices, the network throughput maybe reduced due to the transmissions of the timing RN). Differential TDOA-based localization described in Li et al.⁴ and Makki et al.⁵ does not explicitly synchronize the anchor clocks but still requires a transmitting timing RN as in the reference-broadcast scheme. A scheme similar to differential TDOA was proposed in Xu et al.⁶ for acoustic localization systems. A synchronization-free TDOA-based localization algorithm was proposed in Kim and Chong,⁷ which assumes that the target transmits ranging signals periodically and makes use of the estimated target position in the previous time step to estimate the current position. However, the positioning accuracy of such a system is degraded if the target position in the previous time step is incorrectly estimated. Joint synchronization and localization for TOF-based localization systems was studied in literatures^8–12 and shown to improve the positioning performance. In particular, a Bayesian belief propagation scheme was proposed in Yuan et al.¹⁰ for joint cooperative localization and clock synchronization. Extended Kalman filter was employed in Koivisto and Colleagues^11,12 to jointly track the TOF and synchronize the clock between anchors and tags.

In this article, we consider a TOA-based passive positioning system with multiple targets and propose a novel scheme which jointly estimates the anchor clock offsets and target positions. The system does not require a timing RN and therefore is more robust than conventional systems that use reference-broadcast synchronization. In addition, it is completely passive and non-intrusive, allowing commercial off-the-shelf devices to be tracked without knowing the structure of the existing system or interfering with its operation (e.g. tracking WiFi mobile devices without incurring additional WiFi packet transmission in the network), as has also been considered in Jean and Weiss.¹³ The positioning algorithm is formulated as a maximum likelihood (ML) estimator, which is solved efficiently using an iterative linear least square (LS) method. In addition, an algorithm for initializing the ML estimator is provided, which significantly improves the convergence of the iterative linear LS method. The Cramér–Rao lower bound (CRLB) of positioning error and clock synchronization error is also provided. The performance of the proposed scheme is compared against systems with perfectly synchronized anchors under various configurations, and it is shown that the performance gap diminishes as the number of targets increases.

System model

Considering a positioning system with $N$ anchors and $M$ tags, we use $x_{i} = [x_{i}, y_{i}]^{T} (i = 1, \dots, M)$ and $a_{j} = [a_{j}, b_{j}]^{T} (j = 1, \dots, N)$ to denote the positions of the tags and anchors, respectively. (We consider two-dimensional (2D) positioning in this article. However, the algorithms and analysis can be readily extended to three-dimensional (3D) case.) The anchors sense the wireless signals emitted by the tags and record the arrival time of the signals to estimate the location of each tag. Since all the positioning-related processing is conducted by the anchors, the tags can be commercial off-the-shelf devices in an existing wireless system. For example, the access points (APs) in a WiFi network (if augmented with the capability of measuring high-precision packet arrival time) can be used as anchors to track mobile WiFi devices. It is also possible to deploy anchors that are purely passive and dedicated for positioning.

Each anchor $j$ in the system has a local clock that is not synchronized to each other or to any external reference in hardware. The reading of the clock at time instant $t$ (the world time, for example, UTC) is given by Sathyan et al.¹⁴

t_{j} = (1 + α_{j}) (t + β_{j})

(1)

where $α_{j}$ and $β_{j}$ denote the clock skew and clock offset of anchor $j$ , respectively. Note that $α_{j}$ is in the order of $10^{- 6}$ for typical crystal oscillators.³ Both $α_{j}$ and $β_{j}$ are time-varying, but can be considered invariant within a short-time window during which the measurements are made for positioning.

Suppose tag $i$ transmits a wireless signal at time $t_{i}$ , the TOA of the signal recorded by anchor $j$ is given by

r_{j, i} = (1 + α_{j}) (t_{i} + \frac{d_{j, i}}{c} + β_{j} + z_{j, i})

(2)

according to equation (1), where

d_{j, i} \overset{Δ}{=} | a_{j} - x_{i} |

(3)

denotes the distance between node $i$ and anchor $j$ , $c$ is the speed of light, and $z_{j, i} ~ G (0, σ^{2})$ is the Gaussian-distributed time measurement error with a variance of $σ^{2}$ .

To simplify the notations, we assume that the clock skew $α_{j}$ of each anchor $j$ has been estimated and corrected. Particularly, $α_{j}$ can be estimated based on two or more consecutive transmissions of a tag, as is outlined in Appendix 1. Therefore, equation (2) reduces to

r_{j, i} = t_{i} + \frac{d_{j, i}}{c} + β_{j} + z_{j, i}

(4)

The position of each tag is then estimated based on ${{r_{j, i}}_{j = 1}^{N}}_{i = 1}^{M}$ and ${a_{j}}_{j = 1}^{N}$ . Note that this article is focused on estimating a snapshot of the tag locations within a short-time window, during which $r_{j, i}$ are measured and the tags are considered stationary. However, the positioning results can be combined with filtering algorithms (e.g. Kalman filter) to provide tracking results.

In conventional systems based on reference-broadcast synchronization, the clock offset $β_{j}$ is estimated based on beacons transmitted by a timing RN at a known location. Specifically, the relative clock offset between anchor $j$ and $k$ is given by

β_{j} - β_{k} \approx r_{j, RN} - r_{k, RN} - \frac{1}{c} (d_{j, RN} - d_{k, RN})

(5)

According to equation (4), where $r_{l, RN}$ denotes the arrival time of a beacon recorded by anchor $l$ , $d_{l, RN}$ denotes the distance between anchor $l$ and the timing RN. The results obtained by equation (5) are used to compensate for the clock offsets in $r_{j, i}$ before computing the tag locations. The drawbacks of this approach are that the system is susceptible to RN failure and that the transmission of the timing RN may interfere with the operation of the tags.

Joint clock synchronization and position estimation

In this article, we propose a TOA-based passive localization scheme which jointly synchronizes anchor clocks and estimates target positions. Specifically, ${x_{i}}_{i = 1}^{M}$ , ${β_{j}}_{j = 1}^{N}$ , and ${t_{i}}_{i = 1}^{M}$ (see equation (4)) are estimated according to the ML criteria as follows

\begin{array}{l} {\begin{matrix} {{\hat{x}}_{i}, {\hat{t}}_{i}}_{i = 1}^{M}, \\ {{\hat{β}}_{j}}_{j = 1}^{N} \end{matrix}} = \arg \max_{x_{i}, t_{i}, β_{j}} \\ p ({x_{i}, t_{i}}_{i = 1}^{M}, {β_{j}}_{j = 1}^{N}; {a_{j}, {r_{j, i}}_{i = 1}^{M}}_{j = 1}^{N}) \end{array}

(6)

s . t . β_{1} = 0

(7)

where

\begin{matrix} p ({x_{i}, t_{i}}_{i = 1}^{M}, {β_{j}}_{j = 1}^{N}; {a_{j}, {r_{j, i}}_{i = 1}^{M}}_{j = 1}^{N}) \overset{Δ}{=} \\ Π_{j = 1}^{N} Π_{i = 1}^{M} \frac{1}{\sqrt{2 π} σ} e^{- \frac{1}{2 σ^{2}} {(t_{i} + \frac{d_{j, i} (x_{i})}{c} + β_{j} - r_{j, i})}^{2}} \end{matrix}

(8)

is the likelihood function, with $d_{j, i} (x_{i})$ defined in equation (3). Note that the constraint equation (7) is introduced so that the problem has a unique solution. Particularly, if ${x_{i}, t_{i}}_{i = 1}^{M}, {β_{j}}_{j = 1}^{N}$ is a solution to equation (6), ${x_{i}, t_{i} - Δ t}_{i = 1}^{M}, {β_{j} + Δ t}_{j = 1}^{N}$ is also a valid solution (for any $Δ t$ ), as can be shown by substituting the variables into equation (4). The reason is that only the relative clock offsets among anchors are required while the absolute values of clock offsets do not matter. Setting $β_{1} = 0$ means that the solution $β_{j}$ to equations (6) and (7) is the relative clock offset of anchor $j$ with respect to anchor 1.

Since no timing RN is required, the proposed scheme is completely passive and non-intrusive and is more robust than conventional systems that rely on reference-broadcast for clock synchronization. Note that equation (6) falls into the category of TOA-based one-way ranging, since the distances between the targets and the anchors are readily available once $β_{j}$ and $t_{i}$ are estimated.

Iterative LS estimation

In the following, we describe an algorithm that solves equation (6) based on iteratively LS estimation. Plugging equation (8) into equation (6), it is readily shown that equation (6) can be reformulated as a nonlinear LS problem as in the following

{{{\hat{x}}_{i}, {\hat{t}}_{i}}_{i = 1}^{M}, {{\hat{β}}_{j}}_{j = 1}^{N}} = \arg min_{x_{i}, t_{i}, β_{j}} f (θ)

(9)

where

f (θ) = \sum_{j = 1}^{N} \sum_{i = 1}^{M} {(t_{i} + \frac{d_{j, i} (x_{i})}{c} + β_{j} - r_{j, i})}^{2}

(10)

θ \overset{Δ}{=} {[x_{1}^{T}, \dots, x_{M}^{T}, t_{1}, \dots, t_{M}, β_{1}, \dots, β_{N}]}^{T}

(11)

collects all the unknown variables.

For each tag $i$ , given a position estimate ${\hat{x}}_{i}$ , $d_{j, i} (x_{i})$ can be approximated using first-order Taylor expansion by

d_{j, i} (x_{i}) \approx | {\hat{x}}_{i} - a_{j} | + \nabla d_{j, i} ({\hat{x}}_{i})^{T} (x_{i} - {\hat{x}}_{i})

(12)

where

\nabla d_{j, i} (x_{i}) \overset{Δ}{=} [\begin{matrix} \frac{\partial d_{j, i} (x_{i})}{x_{i}} \\ \frac{\partial d_{j, i} (x_{i})}{y_{i}} \end{matrix}] = \frac{1}{d_{j, i} (x_{i})} (x_{i} - a_{j})

(13)

Equation (9) can be approximated with a linear LS problem by substituting $d_{j, i} (x_{i})$ with equation (12). Specifically

\hat{θ} = \arg min_{θ} | A θ - b |^{2}

(14)

where $A$ is a matrix with $MN$ rows and $3 M + N$ columns and $b$ is a vector with $MN$ rows. Each row of $A$ and $b$ is given by

[A]_{k, :} = [\frac{1}{c} e_{M} (i) \otimes \nabla d_{j, i} {({\hat{x}}_{i})}^{T}, e_{M} (i), e_{N} (j)]

(15)

and

[b]_{k} = r_{j, i} + \frac{1}{c} (\nabla d_{j, i} ({\hat{x}}_{i})^{T} {\hat{x}}_{i} - | {\hat{x}}_{i} - a_{j} |)

(16)

respectively, where $k = (i - 1) N + j$ (since $i \in {1, \dots, M}$ and $j \in {1, \dots, N}$ , $k \in {1, \dots, MN}$ ), $e_{K} (k)$ denotes a K-element unit row vector whose kth element equals one, ⊗ denotes the Kronecker product operation.

The solution to equation (14) contains updated estimates of the target locations and can be used in equation (12) again to formulate an LS estimation problem to refine the position estimates. Accordingly, we propose an algorithm that iteratively estimates the unknown variables using linear LS method, which is described in Algorithm 1. Note that Step 2 can be solved straightforwardly through a linear LS problem with reduced dimension, by discarding the $(3 M + 1) th$ column of $A$ due to the simple equality constraint. The algorithm falls into the category of successive convex approximations.^15,16 Particularly, it solves an approximate version of the original optimization problem in each iteration. (Note that the gradient descent method can also be viewed as an implementation of successive convex approximation.¹²) It can be proven that the approximate objective function in equation (14) satisfies assumptions A1-A5 in Yang and Pesavento;¹⁶ therefore, Algorithm 1 converges to a stationary point of equation (9). Using an initialization algorithm proposed in the following section, Algorithm 1 typically converges within only a few iterations, as will be shown later.

Algorithm 1. Iterative Least Square Algorithm for Joint Clock Synchronization and Position Estimation in TOA-based Passive Localization Systems.
Initialization: Initialize $θ$ using the approach described in the following section. Repeat: 1. Construct matrix $A$ and vector $b$ according to equations (15) and (16). 2. Solve equation (14) subject to constraint $[θ]_{3 M + 1} = 0$ . 3. Solve $\hat{γ} = \arg min_{0 \leq γ \leq 1} f (θ + γ (\hat{θ} - θ))$ (17) 4. Update $θ$ with $θ + \hat{γ} (\hat{θ} - θ)$ . 5. For each tag $i$ , set ${\hat{x}}_{i}^{Prev} = {\hat{x}}_{i}$ , extract the estimated tag positions ${\hat{x}}_{i}$ from $θ$ according to the definition in equation (11). Until: $\| {\hat{x}}_{i}^{Prev} - {\hat{x}}_{i} \| < ϵ, \forall i \in {1, \dots, M}$ .

Algorithm 1. Iterative Least Square Algorithm for Joint Clock Synchronization and Position Estimation in TOA-based Passive Localization Systems.

Initialization: Initialize

θ

using the approach described in the following section.
Repeat:
1. Construct matrix

A

and vector

b

according to equations (15) and (16).
2. Solve equation (14) subject to constraint

[θ]_{3 M + 1} = 0

.
3. Solve

\hat{γ} = \arg min_{0 \leq γ \leq 1} f (θ + γ (\hat{θ} - θ))

(17)

4. Update

θ

with

θ + \hat{γ} (\hat{θ} - θ)

.
5. For each tag

i

, set

{\hat{x}}_{i}^{Prev} = {\hat{x}}_{i}

, extract the estimated tag positions

{\hat{x}}_{i}

from

θ

according to the definition in equation (11).
Until:

| {\hat{x}}_{i}^{Prev} - {\hat{x}}_{i} | < ϵ, \forall i \in {1, \dots, M}

Initialization

The tags’ positions are initialized using coarsely estimated anchor clock offsets. Specifically, taking the summation of equation (4) over the tags gives

\sum_{i = 1}^{M} r_{j, i} = \sum_{i = 1}^{M} t_{i} + \frac{1}{c} \sum_{i = 1}^{M} d_{j, i} + M β_{j} + \sum_{i = 1}^{M} z_{j, i}

(18)

Similarly, for a different anchor $k$

\sum_{i = 1}^{M} r_{k, i} = \sum_{i = 1}^{M} t_{i} + \frac{1}{c} \sum_{i = 1}^{M} d_{k, i} + M β_{k} + \sum_{i = 1}^{M} z_{k, i}

(19)

Subtracting equation (18) by (19) and assuming that

\sum_{i = 1}^{M} d_{j, i} \approx \sum_{i = 1}^{M} d_{k, i}

(20)

gives

β_{j} - β_{k} \approx \frac{1}{M} (\sum_{i = 1}^{M} r_{j, i} - \sum_{i = 1}^{M} r_{k, i})

(21)

The anchors are then synchronized based on equation (21), and ${x_{i}, t_{i}}_{i = 1}^{M}$ are initialized to the output of conventional localization algorithms with $r_{j, i}$ as inputs.

Note that equation (20) holds approximately with large number of evenly distributed tags. When the number of tags is small, equation (20) does not hold in general. However, the above approach provides a coarse initial point for Algorithm 1, which typically converges within few iterations based on the result.

System requirement

A necessary condition for a valid positioning algorithm is that the number of measurements/constraints is greater than or equal to the number of unknown variables. For a 2D positioning system using the proposed scheme, this corresponds to

MN \geq 3 M + N - 1

(22)

according to equations (6), (7), (9), and (14). Therefore, there needs to be at least four anchors in the system (since equation (22) never holds if $N \leq 3$ ), which is identical to that required in conventional systems. In addition, there needs to be multiple tags in the system for the proposed scheme to work. For example, the minimum number of tags is four and two if there are four anchors and six anchors, respectively, in the system. However, it should be noted that equation (22) hardly hinders the implementation of the proposed scheme, since the number of tags in a typical positioning system is significantly greater than one.

Performance analysis

The CRLB of the joint clock synchronization and position estimation problem is derived in this section to analyze the performance of the proposed scheme.

Combining equations (6)–(8), the log-likelihood function is given by

\begin{matrix} \ln p ({x_{i}, t_{i}}_{i = 1}^{M}, {β_{j}}_{j = 2}^{N}; {a_{j}, {r_{j, i}}_{i = 1}^{M}}_{j = 1}^{N}) = \\ - \sum_{j = 1}^{N} \sum_{i = 1}^{M} [\ln (\sqrt{2 π} σ) + \frac{1}{2 σ^{2}} {(t_{i} + \frac{d_{j, i} (x_{i})}{c} + β_{j} - r_{j, i})}^{2}] \end{matrix}

(23)

The CRLB for the unknown variables is given by Kay¹⁷

CRLB (θ') = F^{- 1}

(24)

where $θ' \overset{Δ}{=} {[x_{1}^{T}, \dots, x_{M}^{T}, t_{1}, \dots, t_{M}, β_{2}, \dots, β_{N}]}^{T}$ and $F$ is the corresponding Fisher information matrix. The element in the ith row and the jth column of $F$ is given by

[F]_{i, j} = - E [\frac{\partial^{2} \ln p}{\partial θ_{i'} \partial θ_{j'}}], i, j = 1, \dots, 3 M + N - 1

(25)

where $E [\cdot]$ denotes the expectation operation.

It can be shown that $F$ is given by

F = [\begin{matrix} F_{xx} & F_{xt} & F_{x β} \\ F_{xt}^{T} & F_{tt} & F_{t β} \\ F_{x β}^{T} & F_{t β}^{T} & F_{β β} \end{matrix}]

(26)

where each sub-matrix is given as follows

F_{xx} = [\begin{matrix} F_{x_{1} x_{1}} & 0 & \dots & 0 \\ 0 & F_{x_{2} x_{2}} & \dots & 0 \\ \dots & \dots & \dots & \dots \\ 0 & 0 & \dots & F_{x_{M} x_{M}} \end{matrix}]

(27)

where

F_{x_{i} x_{i}} = \frac{1}{c^{2} σ^{2}} \sum_{j = 1}^{N} \frac{(x_{i} - a_{j}) (x_{i} - a_{j})^{T}}{d_{j, i}^{2}}, i = 1, \dots, M

(28)

F_{xt} = [\begin{matrix} F_{x_{1} t_{1}} & 0 & \dots & 0 \\ 0 & F_{x_{2} t_{2}} & \dots & 0 \\ \dots & \dots & \dots & \dots \\ 0 & 0 & \dots & F_{x_{M} t_{M}} \end{matrix}]

(29)

where

F_{x_{i} t_{i}} = \frac{1}{c σ^{2}} \sum_{j = 1}^{N} \frac{x_{i} - a_{j}}{d_{j, i}}, i = 1, \dots, M

(30)

F_{x β} = [\begin{matrix} F_{x_{1} β_{2}} & \dots & F_{x_{1} β_{N}} \\ \dots & \dots & \dots \\ F_{x_{M} β_{2}} & \dots & F_{x_{M} β_{N}} \end{matrix}]

(31)

where

F_{x_{i} β_{j}} = \frac{x_{i} - a_{j}}{c σ^{2} d_{j, i}}, i = 1, \dots, M, j = 2, \dots, N

(32)

F_{tt} = \frac{N}{σ^{2}} I_{M}

(33)

where $I_{M}$ denotes an M-dimensional identity matrix

F_{t β} = \frac{1}{σ^{2}} J_{M, N - 1}

(34)

where $J_{M, N}$ denotes an all-ones matrix with $M$ rows and $N$ columns; finally

F_{β β} = \frac{M}{σ^{2}} I_{N - 1}

(35)

Based on equations (24)–(35), the standard deviation of positioning error for tag $i$ is lower bounded by

σ_{{\hat{x}}_{i}} \geq \sqrt{{[F^{- 1}]}_{2 i - 1, 2 i - 1} + {[F^{- 1}]}_{2 i, 2 i}}, i = 1, \dots, M

(36)

and the lower bound for anchor clock synchronization error is given by

σ_{{\hat{β}}_{j}} \geq \sqrt{{[F^{- 1}]}_{3 M + j - 1, 3 M + j - 1}}, j = 2, \dots, N

(37)

Simulation results

The performance of the proposed scheme was evaluated using computer simulation. Particularly, it is compared against a localization system with perfectly synchronized anchors. We considered a system with six anchors located at [20,0], [10,10√3], [−10,10√3], [−20,0], [−10, −10√3], and [10,−10√3], respectively (i.e. evenly placed on a circle with a radius of 20 m). The transmit time of the tags and the clock offsets of the anchors were drawn from uniform distributions $U [0, 1]$ and $U [0, 100]$ (s), respectively. The standard deviation of the time measurement error (i.e. $z_{j, i}$ in equations (2) and (4)) was σ = 1 ns. The following schemes were employed to locate the tags:

Proposed. The proposed scheme as described in equation (6) and Algorithm 1.

Clock-Synced. Conventional localization scheme where it is assumed that the anchors are perfectly synchronized (i.e. $β_{j}$ is perfectly known).

Fixed number of tags

We first considered a scenario with four tags in the system, which were located at [0,0], [10,10], [0,−10√3], and [−20,10], respectively. Algorithm 1 was employed to estimate the tag positioning, using measurement data generated according to equation (4). The value of $ε$ in the algorithm was set to $10^{- 2}$ .

Convergence

Figure 1 shows the typical convergence behavior of Algorithm 1 using both the proposed initialization algorithm and random initialization. Note that Algorithm 1 diverges if the randomly generated initial point is ill-conditioned, and the curve for random initialization in Figure 1 is generated using an proper initial point. However, Algorithm 1 always converges with the proposed initialization algorithm. It can be seen that the convergence is also improved significantly using the proposed initialization algorithm.

Figure 1.

Convergence of Algorithm 1.

Positioning accuracy

Figures 2 and 3 show the estimated tag locations generated from 10,000 simulations and the corresponding cumulative distribution function (CDF) of positioning error, respectively. It can be seen that the results are consistent with the actual positions of the tags. For comparison, the results of a conventional positioning system with ideal clock synchronization are also shown in Figure 3. Note that the results provide an upper bound on the accuracy of the proposed systems. Particularly, the performance of the proposed system approaches that of an ideal system as the number of targets increases, as will be shown in Figure 5. The root mean square error (RMSE) of the positioning results is compared against the CRLB in Table 1. It can be seen that the performance of the proposed positioning algorithm is very close to the CRLB. It can also be observed that the positioning accuracy deteriorates as the tag moves out of the convex hull of the anchors, which is due to the increased geometric dilution of precision (GDOP).¹⁸ This is consistent with conventional positioning systems.

Figure 2.

Tag locations estimated with Algorithm 1.

Figure 3.

Cumulative distribution function (CDF) of the positioning error for the proposed system and an ideal positioning system with perfect clock synchronization.

Table 1.

RMSE positioning error for the results in Figure 2 and the corresponding CRLB.

	Tag 1	Tag 2	Tag 3	Tag 4
Position [x y]	[0 0]	[10 10]	[0 −10√3]	[−20 10]
RMSE (m)	0.51	0.55	0.69	1.44
CRLB (m)	0.50	0.54	0.68	1.33

RMSE: root mean square error; CRLB: Cramer–Rao lower bound.

Clock synchronization accuracy

Figure 4 shows the CDF of the estimated clock offset errors for anchors 2–6. It can be seen that the medium synchronization error lies between 0.7 and 1.5 ns for different anchors. The RMSE of the estimated clock offset is compared against the CRLB in Table 2. It can be seen that the performance of clock synchronization is very close to the CRLB.

Figure 4.

CDF clock synchronization error.

Table 2.

RMSE of the estimated clock offset and the corresponding CRLB.

Anchor	2	3	4	5	6
RMSE (ns)	1.41	2.12	2.18	1.02	1.76
CRLB (ns)	1.39	2.09	2.17	1.02	1.75

RMSE: root mean square error; CRLB: Cramer–Rao lower bound.

Varying number of tags

This section investigates the dependency of positioning accuracy on the number of tags $(M)$ for the proposed scheme. During the simulation, the x and y coordinates of the tags were drawn from uniform distribution $U [- 10, 10]$ and used to generate time measurements $r_{j, i}$ according to equation (4). The tag positions were then estimated based on $r_{j, i}$ using both the proposed algorithm and an algorithm that assume perfect clock synchronization. The corresponding CRLBs were also evaluated. Particularly, the CRLB for clock-synced was computed based on equation (3) in Shin and Sung,¹⁹ and the corresponding positioning algorithm was adopted from Dailey and Bell.²⁰ A total of $N_{pos}$ different tag positions were simulated for each case of $M$ . All the positioning errors were aggregated to compute the RMSE positioning error, and the CRLB was averaged over all tags and different cases of tag positions. Specifically

{\bar{e}}_{RMS} = \sqrt{\frac{1}{N_{pos} M} \sum_{n = 1}^{N_{pos}} \sum_{i = 1}^{M} {(e_{i}^{n})}^{2}}

(38)

\bar{CRLB} = \sqrt{\frac{1}{N_{pos} M} \sum_{n = 1}^{N_{pos}} \sum_{i = 1}^{2 M} {[F_{n}^{- 1}]}_{i, i}}

(39)

where $e_{i}^{n}$ and $F_{n}$ denote the positioning error of tag $i$ and the Fisher information matrix, respectively, in the nth simulation case. $N_{pos}$ was set to 1000 in the simulation.

Figure 5 shows the relationship between the positioning errors and the number of tags. It can be seen that the proposed positioning algorithm achieves the CRLB. The root mean square positioning error is 0.3 m if there are 50 tags in the system, which is only 20% higher than that for an ideally synchronized system (0.25 m). In addition, the positioning error of the proposed scheme decreases and approaches that of clock-synced as the number of tags in the system increases. The reason is that more measurements become available as the number of tags increases, which improves the accuracy of clock synchronization among anchors. This can also be explained by equation (35), which shows that the Fisher information related to the anchor clock offset increases with the number of tags.

Figure 5.

Relationship between the positioning accuracy and the number of tags.

Formation of the tags

The dependency of positioning accuracy on the formation of the tags is studied for the proposed scheme in this section. We considered a case with four tags in the systems, which were evenly placed on a circle centered at (0 0) with a radius of 10 m. The formation of the tags were changed by varying the angular spacing between the tags (e.g. the tag positions are (10 0), (0 10), (−10 0), and (0 −10) if the angular spacing is 90° and (10 0), (5√2 5√2), (0 10), and (−5√2 5√2) if the angular spacing is 45°).

Figure 6 shows the relationship between the positioning errors and the angular spacing between tags, where the results are averaged over 1000 simulations. It can be seen that the performance of Clock-Synced hardly changes with the angular spacing, since the GDOP¹⁹ is almost identical for all the tag positions on the circle. However, the positioning error of the proposed scheme decreases as the tags become more dispersed on the circle. The reason is that the clock offsets are estimated more accurately if the tags are dispersed. Intuitively, the ML estimation problem equations (6) and (7) are undetermined in the extreme case where all the tags collapse to one position. The reason is that tags’ position and anchor clock offsets are not observable from the measurements $r_{j, i}$ . For any tag location $x_{i} = x$ , one can adjust the clock offset $β_{j}$ and tag transmit time $t_{i}$ such that equation (4) is satisfied $\forall j = 1, \dots, N, \forall i = 1, \dots, M$ . In addition, it can be verified that the Fisher information matrix equation (25) becomes singular in this case. Therefore, it is favorable for the proposed scheme to have multiple tags dispersed in the application environment.

Figure 6.

Relationship between the positioning accuracy and the angular spacing between tags. The tags are evenly placed on a circle centered at [0 0] with a radius of 10 m.

Conclusion

A joint synchronization and localization scheme was proposed for TOA-based positioning systems. The scheme does not require timing RNs as in conventional systems and therefore is more robust. In addition, it can be used to track commercial off-the-shelf devices in a completely passive and non-intrusive way. The positioning algorithm was formulated as an ML estimation problem, which was solved efficiently using an iterative LS method. The CRLB of positioning error was also analyzed. It was shown that the algorithm achieves the CRLB. In addition, the positioning error decreases with the number of tags in the system and approaches that of a system with perfectly synchronized anchors.

Footnotes

Appendix 1

Handling Editor: Mikko Valkama

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

References

Liu

Darabi

Banerjee

et al . Survey of wireless indoor positioning techniques and systems. IEEE T Syst Man Cyb 2007; 37(6): 1067–1080.

Makki

Siddig

Saad

et al . Indoor localization using 802.11 time differences of arrival. IEEE T Instrum Meas 2016; 65(3): 614–623.

Elson

Girod

Estrin

. Fine-grained network time synchronization using reference broadcasts. SIGOPS Oper Syst Rev 2002; 36: 147–163.

Dimitrova

Raluy

et al . TDOA for narrow-band signal with low sampling rate and imperfect synchronization. In: Proceedings of the 7th wireless and mobile Networking Conference (WMNC), Vilamoura, 20–22 May 2014, pp.1–8. New York: IEEE.

Makki

Siddig

Saad

et al . Survey of WiFi positioning using time-based techniques. Comput Netw 2015; 88: 218–233.

Sun

et al . High-accuracy TDOA-based localization without time synchronization. IEEE T Parall Distr 2013; 24(8): 1567–1576.

Kim

Chong

. An efficient TDOA-based localization algorithm without synchronization between base stations. Int J Distrib Sens N 2015; 11(9): 32351.

Zheng

. Joint time synchronization and localization of an unknown node in wireless sensor networks. IEEE T Signal Pr 2010; 58(3): 1309–1320.

Vaghefi

Buehrer

. Cooperative joint synchronization and localization in wireless sensor networks. IEEE T Signal Pr 2015; 63(14): 3615–3627.

10.

Yuan

Etzlinger

et al . Cooperative joint localization and clock synchronization based on Gaussian message passing in asynchronous wireless networks. IEEE T Veh Technol 2016; 65(9): 7258–7273.

11.

Koivisto

Costa

Werner

et al . Joint device positioning and clock synchronization in 5G ultra-dense networks. IEEE T Wirel Commun 2017; 16(5): 2866–2881.

12.

Koivisto

Hakkarainen

Costa

et al . High-efficiency device positioning and location-aware communications in dense 5G networks. IEEE Commun Mag 2017; 55(8): 188–195.

13.

Jean

Weiss

. Passive localization and synchronization using arbitrary signals. IEEE T Signal Pr 2014; 62(8): 2143–2150.

14.

Sathyan

Humphrey

Hedley

. WASP: a system and algorithms for accurate radio localization using low-cost hardware. IEEE T Syst Man Cyb 2011; 41(2): 211–222.

15.

Razaviyayn

. Successive convex approximation: analysis and applications. PhD Thesis, The University of Minnesota, Minneapolis, MN, 2014.

16.

Yang

Pesavento

. A unified successive pseudoconvex approximation framework. IEEE T Signal Pr 2017; 65(13): 3313–3328.

17.

Kay

. Fundamentals of statistical signal processing: estimation theory. Upper Saddle River, NJ: Prentice-Hall, 1993.

18.

Sharp

Hedley

. On the GDOP and accuracy for indoor positioning. IEEE T Aero Elec Sys 2012; 48(3): 2032–2051.

19.

Shin

Sung

. Comparisons of error characteristics between TOA and TDOA positioning. IEEE T Aero Elec Sys 2002; 38(1): 307–311.

20.

Dailey

Bell

. A method for GPS positioning. IEEE T Aero Elec Sys 1996; 32(3): 1148–1154.

Joint clock synchronization and position estimation in time of arrival–based passive positioning systems

Abstract

Keywords

Introduction

System model

Joint clock synchronization and position estimation

Iterative LS estimation

Initialization

System requirement

Performance analysis

Simulation results

Fixed number of tags

Convergence

Positioning accuracy

Clock synchronization accuracy

Varying number of tags

Formation of the tags

Conclusion

Footnotes

Appendix 1

Declaration of conflicting interests

Funding

References