This article is part of the series Object Tracking and Monitoring Using Advanced Signal Processing Techniques.

Open Access Research

Reference-free time-based localization for an asynchronous target

Yiyin Wang* and Geert Leus

Author Affiliations

Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, Mekelweg 4, 2628CD Delft, The Netherlands

For all author emails, please log on.

EURASIP Journal on Advances in Signal Processing 2012, 2012:19  doi:10.1186/1687-6180-2012-19


The electronic version of this article is the complete one and can be found online at: http://asp.eurasipjournals.com/content/2012/1/19


Received:13 May 2011
Accepted:26 January 2012
Published:26 January 2012

© 2012 Wang and Leus; licensee Springer.

This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

Low-complexity least-squares (LS) estimators based on time-of-arrival (TOA) or time-difference-of-arrival (TDOA) measurements have been developed to locate a target node with the help of anchors (nodes with known positions). They require to select a reference anchor in order to cancel nuisance parameters or relax stringent synchronization requirements. Thus, their localization performance relies heavily on the reference selection. In this article, we propose several reference-free localization estimators based on TOA measurements for a scenario, where anchor nodes are synchronized, and the clock of the target node runs freely. The reference-free LS estimators that are different from the reference-based ones do not suffer from a poor reference selection. Furthermore, we generalize existing reference-based localization estimators using TOA or TDOA measurements, which are scattered over different research areas, and we shed new light on their relations. We justify that the optimal weighting matrix can compensate the influence of the reference selection for reference-based weighted LS (WLS) estimators using TOA measurements, and make all those estimators identical. However, the optimal weighting matrix cannot decouple the reference dependency for reference-based WLS estimators using a nonredundant set of TDOA measurements, but can make the estimators using the same set identical as well. Moreover, the Cramér-Rao bounds are derived as benchmarks. Simulation results corroborate our analysis.

1. Introduction

Localization is a challenging research topic under investigation for many decades. It finds applications in the global positioning system (GPS) [1], radar systems [2], underwater systems [3], acoustic systems [4,5], cellular networks [6], wireless local area networks (WLANs) [7], wireless sensor networks (WSNs) [8,9], etc. It is embraced everywhere at any scale. New applications of localization are continuously emerging, which motivates further exploration and attracts many researchers from different research areas, such as geophysics, signal processing, aerospace engineering, and computer science. In general, the localization problem can be solved by two steps [7-9]: firstly measure the metrics bearing location information, the so-called ranging or bearing, and secondly estimate the positions based on those metrics, the so-called location information fusion. There are mainly four metrics: time-of-arrival (TOA) or time-of-flight (TOF) [10], time-difference-of-arrival (TDOA) [4,11], angle-of-arrival (AOA) [12], and received signal strength (RSS) [13]. The ranging methods using RSS can be implemented by energy detectors, but they can only achieve a coarse resolution. Antenna arrays are required for AOA-based methods, which encumbers their popularity. On the other hand, the high accuracy and potentially low cost implementation make TOA or TDOA based on ultra-wideband impulse radios (UWB-IRs) a promising ranging method [8].

Closed-form localization solutions based on TOAs or TDOAs are used to locate a target node with the help of anchors (nodes with known positions). They are appreciated for real-time localization applications, initiating iterative localization algorithms, and facilitating Kalman tracking [14]. They have much lower complexity compared to the optimal maximum likelihood estimator (MLE), and also do not require prior knowledge of noise statistics. However, a common feature of existing closed-form localization solutions is reference dependency. The reference here indicates the time associated with the reference anchor. For instance, in order to measure TDOAs, a reference anchor has to be chosen first [7]. The reference anchor is also needed to cancel nuisance parameters in closed-form solutions based on TOAs or TDOAs [15]. Thus, the localization performance depends heavily on the reference selection. There are some efforts to improve the reference selection [16-18], but they mainly rely on heuristics. Furthermore, when TOAs are measured using the one-way ranging protocol for calculating the distance between the target and the anchor, stringent synchronization is required between these two nodes in the conventional methods [7,10]. However, it is difficult to maintain synchronization due to the clock inaccuracy and other error sources. Therefore, various closed-form localization methods resort to using TDOA measurements to relax this synchronization constraint between the target and the anchor. These methods only require synchronization among the anchors, e.g., the source localization methods based on TDOAs using a passive sensor array [4,19-22].a

In this article, we also relax the above synchronization requirement, and consider a scenario, where anchor nodes are synchronized, and the clock of the target node runs freely. However, instead of using TDOAs, we model the asynchronous effect as a common bias, and propose reference-free least-squares (LS), weighted LS (WLS), and constrained WLS (CWLS) localization estimators based on TOA measurements. Furthermore, we generalize existing reference-based localization solutions using TOA or TDOA measurements, which are scattered over different research areas, and provide new insights into their relations, which have been overlooked. We clarify that the reference dependency for reference-based WLS estimators using TOA measurements can be decoupled by the optimal weighting matrix, which also makes all those estimators identical. However, the influence of the reference selection for reference-based WLS estimators using a nonredundant set of TDOA measurements cannot be compensated by the optimal weighting matrix. But the optimal weighting matrix can make the estimators using the same set equivalent as well. Moreover, the Cramér-Rao bounds (CRBs) are derived as benchmarks for comparison.

The rest of this article is organized as follows. In Section 2, different kinds of reference-free TOA-based estimators are proposed, as well as existing reference-based estimators using TOA measurements. Their relations are thoroughly investigated. In Section 3, we generalize existing reference-based localization algorithms using TDOA measurements, and shed light on their relations as well. Simulation results and performance bounds are shown in Section 4. Conclusions are drawn at the end of the article.

Notation: We use upper (lower) bold face letters to denote matrices (column vectors). [X]m,n, [X]m,: and [X]:,n denote the element on the mth row and nth column, the mth row, and the nth column of the matrix X, respectively. [x]n indicates the nth element of x. 0m (1m) is an all-zero (all-one) column vector of length m. Im indicates an identity matrix of size m × m. Moreover, (·)T, || · ||, and ⊙ designate transposition, ℓ2 norm, and element-wise product, respectively. All other notation should be self-explanatory.

2. Localization based on TOA measurements

Considering M anchor nodes and one target node, we would like to estimate the position of the target node. All the nodes are distributed in an l-dimensional space, e.g., l = 2 (a plane (2-D)) or l = 3 (a space (3-D)). The coordinates of the anchor nodes are known and defined as Xa = [x1, x2, ..., xM], where the vector xi = [x1,i, x2,i, . . ., xl,i]T of length l indicates the known coordinates of the ith anchor node. We employ a vector x of length l to denote the unknown coordinates of the target node. Our method can also be extended for multiple target nodes. We remark that in a large scale WSN, it is common to localize target nodes in a sequential way [23]. The target nodes that have enough anchors are localized first. Then, the located target nodes can be viewed as new anchors that can facilitate the localization of other target nodes. Therefore, the multiple-anchors-one-target scenario here is of practical interest. We can even consider a case with a moving anchor, in which a ranging signal is periodically transmitted by the target node, and all the positions where the moving anchor receives the ranging signal are viewed as the fixed positions of some virtual anchors. We assume that all the anchors are synchronized, and their clock skews are equal to 1, whereas the clock of the target node runs freely. Furthermore, we assume that the target node transmits a ranging signal, and all the anchors act as receivers. We remark that other systems may share the same data model such as a passive sensor array for source localization or a GPS system, where a GPS receiver locates itself by exploring the received ranging signals from several satellites [1]. All the satellites are synchronized to an atomic clock, but the GPS receiver has a clock offset relative to the satellite clock. Note that this is a stricter synchronization requirement than ours, as we allow the clock of the target node to run freely. Every satellite sends a ranging signal and a corresponding transmission time. The GPS receiver measures the TOAs, and calculates the time-of-flight (TOF) plus an unknown offset. In this section, TOA measurements are used, and TDOA measurements are employed in the next section.

2.1. System model

In this section, all localization algorithms are based on TOA measurements. When the target node transmits a ranging signal, all the anchors receive it and record a timestamp upon the arrival of the ranging signal independently. We define a vector u of length M to collect all the distances corresponding to the timestamps, which is given by u = [u1, u2, . . ., uM]T. We employ b to denote the distance corresponding to the true target node transmission instant, which is unknown. We remark that if we consider a GPS system, then u collects the distances corresponding to the biased TOFs calculated by the GPS receiver, and b indicates the distance bias corresponding to the unknown clock offset of the GPS receiver relative to the satellite. Consequently, the TOA measurements can be modeled as

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M1','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M1">View MathML</a>

(1)

where d = [d1, d2, ..., dM]T, with di = ||xi - x|| the true distance between the ith anchor node and the target node, and n = [n1, n2, ..., nM]T with ni the distance error term corresponding to the TOA measurement error at the ith anchor, which can be modeled as a random variable with zero mean and variance <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M2','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M2">View MathML</a>, and which is independent of the other terms (E[ni nj] = 0, i j). We remark that instead of using TDOAs to directly get rid of the distance bias, we use TOAs and take the bias into account in the system model.

2.2. Localization based on squared TOA measurements

2.2.1. Proposed localization algorithms

Note that (1) is a nonlinear equation with respect to (w.r.t.) x. To solve it, a MLE can be derived, which is optimal in the sense that for a large number of data it is unbiased and approaches the CRB. However, the MLE has a high computational complexity, and also requires the unknown noise statistics. Therefore, low-complexity solutions are of great interest for localization. From <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M3','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M3">View MathML</a>, we derive that <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M4','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M4">View MathML</a>, where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M5','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M5">View MathML</a>. Element-wise multiplication at both sides of (1) is carried out, which leads to

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M6','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M6">View MathML</a>

(2)

Moving knowns to one side and unknowns to the other side, we achieve

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M7','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M7">View MathML</a>

(3)

where m = -(2d n + n n). The stochastic properties of m are as follows

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M8','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M8">View MathML</a>

(4)

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M9','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M9">View MathML</a>

(5)

where we ignore the higher order noise terms to obtain (5) and assume that the noise mean E[[m]i] ≈ 0 under the condition of sufficiently small measurement errors. Note that the noise covariance matrix Σ depends on the unknown d.

Defining ϕ = ψa-u u, y = [xT, b, b2 - ||x||2]T, and <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M10','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M10">View MathML</a>, we can finally rewrite (3) as

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M11','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M11">View MathML</a>

(6)

Ignoring the parameter relations in y, an unconstrained LS and WLS estimate of y can be computed respectively given by

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M12','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M12">View MathML</a>

(7)

and

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M13','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M13">View MathML</a>

(8)

where W is a weighting matrix of size M × M. Note that M l + 2 is required in (7) and (8), which indicates that we need at least four anchors to estimate the target position on a plane. The optimal W is W* = Σ-1, which depends on the unknown d as we mentioned before. Thus, we can update it iteratively, and the resulting iterative WLS can be summarized as follows:

(1) Initialize W using the estimate of d based on the LS estimate of x;

(2) Estimate ŷ using (8);

(3) Update <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M15','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M15">View MathML</a> where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M16','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M16">View MathML</a> is computed using ŷ ;

(4) Repeat Steps (2) and (3) until a stopping criterion is satisfied.

The typical stopping criteria are discussed in [24]. We stop the iterations when <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M17','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M17">View MathML</a>, where ŷ (k)is the estimate of the kth iteration and ϵ is a given threshold [25]. An estimate of x is finally given by

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M19','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M19">View MathML</a>

(9)

To accurately estimate y, we can further explore the relations among the parameters in y. A CWLS estimator is obtained as

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M20','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M20">View MathML</a>

(10)

subject to

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M21','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M21">View MathML</a>

(11)

where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M22','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M22">View MathML</a> and

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M23','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M23">View MathML</a>

(12)

Solving the CWLS problem is equivalent to minimizing the Lagrangian [4,10]

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M24','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M24">View MathML</a>

(13)

where λ is a Lagrangian multiplier. A minimum point for (13) is given by

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M25','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M25">View MathML</a>

(14)

where λ is determined by plugging (14) into the following equation

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M26','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M26">View MathML</a>

(15)

We could find all the seven roots of (15) as in [4,10], or employ a bisection algorithm as in [26] to look for λ instead of finding all the roots. If we obtain seven roots as in [4,10], we discard the complex roots, and plug the real roots into (14). Finally, we choose the estimate ŷ , which fulfills (10). The details of solving (15) are mentioned in Appendix 1. Note that the proposed CWLS estimator (14) is different from the estimators in [4,10]. The CLS estimator in [4] is based on TDOA measurements, and the CWLS estimator in [10] is based on TOA measurements for a synchronous target (b = 0). Furthermore, we remark that the WLS estimator proposed in [27] based on the same data model as (1), is labeled as an extension of Bancroft's algorithm [28], which is actually similar to the spherical-intersection (SX) method proposed in [29] for TDOA measurements. It first solves a quadratic equation in b2 - ||x||2, and then estimates x and b via a WLS estimator. However, it fails to provide a solution for the quadratic equation under certain circumstances, and performs unsatisfactorily when the target node is far away from the anchors [29].

Many research works have focused on LS solutions ignoring the constraint (11) in order to obtain low-complexity closed-form estimates [7]. As squared range (SR) measurements are employed, we call them unconstrained SR-based LS (USR-LS) approaches, to be consistent with [26]. Because only x is of interest, b and b2 - ||x||2 are nuisance parameters. Different methods have been proposed to get rid of them instead of estimating them. A common characteristic of all these methods is that they have to choose a reference anchor first, and thus we label them reference-based USR-LS (REFB-USR-LS) approaches. As a result, the performance of these REFB-USR-LS methods depends on the reference selection [7]. However, note that the unconstrained LS estimate of y in (7) does not depend on the reference selection. Thus, we call (7) the reference-free USR-LS (REFF-USR-LS) estimate, (8) the REFF-USR-WLS, and (14) the REFF-SR-CWLS estimate.

Moreover, we propose the subspace minimization (SM) method [22] to achieve a REFF-USR-LS estimate of x alone, which is identical to <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M27','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M27">View MathML</a> in (7), but shows more insight into the links among different estimators. Treating b and b2 - ||x||2 as nuisance parameters, we try to get rid of them by orthogonal projections instead of random reference selection. We first use an orthogonal projection <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M28','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M28">View MathML</a> of size M × M onto the orthogonal complement of 1M to eliminate (b2 - ||x||2) 1M. Sequentially, we employ a second orthogonal projection Pu of size M × M onto the orthogonal complement of Pu to cancel -2bPu, which is given by

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M29','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M29">View MathML</a>

(16)

Thus, premultiplying (3) with PuP, we obtain

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M30','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M30">View MathML</a>

(17)

which is linear w.r.t. x. The price paid for applying these two projections is the loss of information. The rank of PuP is M - 2, which means that M l + 2 still has to be fulfilled as before to obtain an unconstrained LS or WLS estimate of x based on (17). In a different way, PuP can be achieved directly by calculating an orthogonal projection onto the orthogonal complement of [1M,u]. Let us define the nullspace <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M31','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M31">View MathML</a>, and <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M32','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M32">View MathML</a>, where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M33','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M33">View MathML</a> is the column space of U, ⊕ denotes the direct sum of two linearly independent subspaces and ℝM is the M-dimensional vector space. Therefore, PuP is the projection onto <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M33','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M33">View MathML</a>. Note that the rank of <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M34','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M34">View MathML</a> has to be equal to l, which indicates that the anchors should not be co-linear for both 2-D and 3-D or co-planar for 3-D. A special case occurs when u = k1M, where k is any positive real number. In this case, P can cancel out both (b2 - ||x||2)1M and -2bu, and one projection is enough, leading to the condition M l + 1. The drawback though is that we can then only estimate x and b2 - ||x||2 - 2bk due to the dependence between u and 1M according to (3). The SM method indicates all the insights mentioned above, which cannot be easily observed by the unconstrained estimators.

Based on (17), the LS and WLS estimate of x is respectively given by,

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M35','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M35">View MathML</a>

(18)

and

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M36','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M36">View MathML</a>

(19)

where Q is an aggregate weighting matrix of size M × M. The optimal Q is given by

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M37','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M37">View MathML</a>

(20)

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M38','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M38">View MathML</a>

(21)

where the pseudo-inverse (†) is employed, because the argument is rank deficient. Note that PuP is the projection onto <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M33','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M33">View MathML</a>, and is applied to both sides of Σ. Thus, (Pu PΣPPu)is still in <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M33','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M33">View MathML</a>, and would not change with applying the projection again. As a result, we can simplify (20) as (21). Consequently, Q* is the pseudo-inverse of the matrix obtained by projecting the columns and rows of Σ onto <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M33','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M33">View MathML</a>, which is of rank M - 2. We remark that <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M27','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M27">View MathML</a> in (18) (or (19)) is identical to the one in (7) (or (8)) according to [22]. The SM method and the unconstrained LS (or WLS) method lead to the same result. Therefore, <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M27','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M27">View MathML</a> in (18) and (7) (or in (19) and (8)) are all REFF-USR-LS (or REFF-USR-WLS) estimates.

2.2.2. Revisiting existing localization algorithms

As we mentioned before, all the REFB-USR-LS methods suffer from a poor reference selection. There are some efforts to improve the reference selection [16-18]. In [16], the operation employed to cancel ||x||21M is equivalent to the orthogonal projection P. All anchors are chosen as a reference once in [17] in order to obtain M(M - 1)/2 equations in total. A reference anchor is chosen based on the criterion of the shortest anchor-target distance measurement in [18]. However, reference-free methods are better than these heuristic reference-based methods in the sense that they cancel nuisance parameters in a systematic way. To clarify the relations between the REFB-USR and the REFF-USR approaches, we generalize the reference selection of all the reference-based methods as a linear transformation, which is used to cancel nuisance parameters, similarly as an orthogonal projection. To eliminate (b2 - ||x||2)1M, the ith anchor is chosen as a reference to make differences. As a result, the corresponding linear transformation Ti of size (M - 1) × M can be obtained by inserting the column vector -1M-1 after the (i-1)th column of IM-1, which fulfills Ti1M = 0M-1, i ∈ {1,..., M}. For example, if the first anchor is chosen as a reference, then T1 = [-1M-1, IM-1]. Furthermore, we can write Tid = Ti1 d - di 1m-1, where Ti1 is achieved by replacing the ith column of Ti with the column vector 0M-1. Applying Ti to both sides of (3), we arrive at

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M39','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M39">View MathML</a>

(22)

Sequentially, we investigate the second linear transformation Mj of size (M - 2) × (M - 1), which fulfills MjTiu = 0M-2, j ∈ {1,..., M} and j i. As a result, the nullspace <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M40','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M40">View MathML</a>, and <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M41','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M41">View MathML</a>. Note that b = 0 in [7,16-18,22,26], which means that there is no need to apply Mj in these works. But the double differencing method in [15] is equivalent to employing Mj, and thus the results of [15] can be used to design Mj. Let us first define a matrix <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M42','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M42">View MathML</a> of size (M - 2) × (M - 1) similarly as Ti1 using the column vector 0M-2 instead of 0M-1. When the jth anchor is chosen as a reference and j < i, Mj can be obtained by inserting the column vector -(1/(uj - ui))1M-2 after the (j - 1)th column of the matrix <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M43','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M43">View MathML</a>, where ∅ is element-wise division. If j > i, then Mj can be obtained by inserting the column vector -(1/(uj - ui))1M-2 after the (j - 2)th column of the matrix <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M44','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M44">View MathML</a>. For example, if the first anchor is chosen to cancel out (b2 - ||x||2) 1M (T1 is used), and the second anchor is chosen to eliminate T1 u, then M2 is given by

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M45','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M45">View MathML</a>

(23)

Premultiplying MjTi to both sides of (3), we achieve

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M46','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M46">View MathML</a>

(24)

Consequently, the general form of the REFB-USR-LS and the REFB-USR-WLS estimates are derived in the same way as (18) and (19) by replacing PPuP and Q with <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M47','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M47">View MathML</a> and Qi,j, respectively. We do not repeat these equations for the sake of brevity. Note that Qi,j is an aggregate weighting matrix of size M × M. The optimal Qi,j is given by

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M48','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M48">View MathML</a>

(25)

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M49','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M49">View MathML</a>

(26)

where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M50','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M50">View MathML</a>, which is also the projection onto <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M33','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M33">View MathML</a>, and thus is equivalent to PuP. The equality between (25) and (26) can be verified using a property of the pseudo-inverse.b Hence, <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M51','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M51">View MathML</a> is of rank M - 2, and <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M52','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M52">View MathML</a> with i j. As a result, the REFB-USR-WLS estimate and the REFF-USR-WLS estimate are identical if the optimal weighting matrix is used. Hence, the optimal weighting matrix can compensate the impact of random reference selection. However, since Σ depends on the unknown d, the optimal weighting matrix can only be approximated iteratively. Also note that the REFB-USR-LS estimate suffers from the ad-hoc reference selection, while the REFF-USR-LS estimate is independent of the reference selection.

2.3. Localization based on squared differences of TOA measurements

2.3.1. Proposed localization algorithms

Let us recall (1) here, i.e.,

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M53','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M53">View MathML</a>

(27)

In general, b is regarded as a nuisance parameter. Instead of first carrying out element-wise multiplication at both sides of (27), we can also try to get rid of b before element-wise multiplication. By choosing a reference anchor, and then subtracting the TOAs of other anchors from the TOA of the reference anchor [7], M - 1 TDOAs are obtained and b is canceled out. Note that these TDOAs are achieved differently from the TDOAs obtained directly by cross-correlating the received signals from different anchors. The obvious drawback of this conventional scheme is again the reference dependency. On the other hand, since b is a common term in (1), we can again apply P to eliminate -b1M instead of randomly choosing a reference anchor. Then we arrive at

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M54','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M54">View MathML</a>

(28)

Note that <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M55','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M55">View MathML</a>, where ū is the average TOA. Thus, Pu represents the differences between the anchor TOAs and the average TOA. Moreover, <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M57','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M57">View MathML</a>, where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M58','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M58">View MathML</a> is the unknown average of the distances between the target node and the anchors, and <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M59','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M59">View MathML</a>, where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M60','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M60">View MathML</a>. Thus, (28) can be rewritten as

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M61','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M61">View MathML</a>

(29)

By making element-wise multiplication of (29) and re-arranging all the terms, we achieve

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M62','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M62">View MathML</a>

(30)

where ψa = [||x1||2, ||x2||2,..., ||xM||2]T and m = -(2dn + n n) as before. Using the SM method to obtain an unconstrained LS estimate of x alone, we employ again two projections P and Pu, and arrive at

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M63','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M63">View MathML</a>

(31)

the right hand side of which is exactly the same as the one in (17), and thus we can state PuP(ψa - (Pu) ⊙ (Pu)) = Pu Pϕ. Note that although (30) is different from (3), we find that (31) and (17) become equivalent after premultiplying Pu P. Furthermore, (Pu) ⊙ (Pu) can be labeled as a SR difference (SRD) term. As a result, the unconstrained LS and WLS estimate of x based on (31), which are named the reference-free USRD-LS (REFF-USRD-LS) estimate and the REFF-USRD-WLS estimate, are exactly the same as the REFF-USR-LS estimate (18) and the REFF-USR-WLS estimate (19), respectively. We do not repeat them here in the interest of brevity. Moreover, the constrained LS and WLS based on (30), namely the REFF-SRD-CLS estimate and the REFF-SRD-CWLS estimate, are identical to the REFF-SR-CLS and the REFF-SR-CWLS estimate (14) as well.

2.3.2. Revisiting existing localization algorithms

Existing methods choose a reference anchor to obtain range differences, and further investigate low-complexity closed-form LS or WLS solutions. Thus, we call them reference-based USRD-LS (REFB-USRD-LS) and REFB-USRD-WLS approaches. To expose interesting links among the different reference-based or reference-free SR-based or SRD-based approaches, we generalize the conventional REFB-USRD-LS and REFB-USRD-WLS approaches [7] in the same way as in Section 2.2.2. The reference selection can be generalized by a linear transformation similarly as in Section 2.2.2. In order to eliminate -b1M in (27), the ith anchor is chosen as a reference, thus Ti defined in Section 2.2.2 is employed, which fulfills Ti1M = 0M-1. Applying Ti instead of P to (27), following the same operations to obtain (30), and noting that (Ti1 (d + n)) ⊙ (Ti1(d + n)) = Ti1 ((d + n) ⊙ (d + n)), we arrive at

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M64','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M64">View MathML</a>

(32)

which is different from (30), and has only one nuisance parameter di at the right hand side. Ignoring the relation between x and di, we still have two ways to deal with di. The first one is to estimate x and di together [22], which means we only use a reference once for calculating the TDOAs. The second one is again to apply Mj, which fulfills Mj Ti u = 0M-2. It employs two different references, one for calculating the TDOAs, and the other for eliminating the nuisance parameter. In order to distinguish these two, we call them the REFB-USRD-LS(1) and the REFB-USRD-LS(2) estimate, respectively, where the number between brackets indicates the number of references used in the approach. In the same way as we clarified the equivalence between the REFF-USRD-LS and the REFF-USR-LS estimate in the previous subsection, we can easily confirm the equivalence between the REFB-USRD-LS(2) (or the REFB-USRD-WLS(2)) and the REFB-USR-LS (or the REFB-USR-WLS) estimate of Section 2.2.2. We omit the details for the sake of brevity. Furthermore, we recall that similarly as above we could have dealt with -2bTi u in (22) in two different ways. But since b = 0 in [7,16-18,22,26], there are no discussions about these two different ways in literature, and we do not distinguish between them in the REFB-USR-LS method.

Since there is no counterpart of the REFB-USRD-LS(1) estimate in Section 2.2.2 for the SR-based methods, we briefly discuss the REFB-USRD-LS(1) estimate to complete the investigation of the links among all the estimators based on TOA measurements. Employing the SM method, we again use an orthogonal projection Pi of size (M - 1) × (M - 1) onto the orthogonal complement of Ti u to fulfill Pi Ti u = 0M-1, which can be derived in the same way as (16) by replacing IM and Pu with IM-1 and Tiu, respectively. As a result, <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M65','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M65">View MathML</a> and <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M66','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M66">View MathML</a>. Premultiplying (32) with Pi, we obtain

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M67','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M67">View MathML</a>

(33)

Note that Pi ((Ti u) ⊙ (Ti u)) = Pi Ti (u u) (see Appendix 2 for a proof), and thus we can state Pi Tiψa -Pi ((Ti u) ⊙ (Ti u)) = Pi Tiϕ). Consequently, the REFB-USRD-LS(1) and the REFB-USRD-WLS(1) estimates can also be written as (18) and (19) by replacing PPu P and Q with <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M68','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M68">View MathML</a> and Qi, respectively. We do not repeat the equations in the interest of brevity. We remark that Qi is again an aggregate weighting matrix of size M × M, and the optimal Qi of rank (M - 2) is given by

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M69','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M69">View MathML</a>

(34)

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M70','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M70">View MathML</a>

(35)

where Vi is of size M × (M - 2), and collects the right singular vectors corresponding to the M - 2 nonzero singular values of Pi Ti. We derive (35) in Appendix 3, and prove that <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M71','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M71">View MathML</a> is the projection onto <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M33','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M33">View MathML</a>. As a result, <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M72','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M72">View MathML</a> and i j.

Based on the above discussions, we achieve the important conclusion that the REFF-USRD-WLS, the REFB-USRD-WLS(1), the REFB-USRD-WLS(2), the REFF-USR-WLS, and the REFB-USR-WLS estimate are all identical if the optimal weighting matrix is adopted. The optimal weighting matrix releases the reference-based methods from the influence of a random reference selection. Moreover, the REFF-USR-LS and the REFF-USRD-LS estimate are identical, and free from a reference selection, whereas the REFB-USR-LS and the REFB-USRD-LS(2) estimate are equivalent, but still suffer from a poor reference selection.

To further improve the localization accuracy, a constrained WLS estimate based on (32) can be pursued considering the relation between x and di similarly as in [26]. We call it the reference-based SRD CWLS (REFB-SRD-CWLS) estimate. Denoting <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M73','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M73">View MathML</a> and ϱi = Ti ψa - (Ti u) ⊙ (Ti u), it is given by,

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M74','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M74">View MathML</a>

(36)

subject to

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M75','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M75">View MathML</a>

(37)

where Wi is a weighting matrix of size (M - 1) × (M - 1), <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M76','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M76">View MathML</a> and

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M77','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M77">View MathML</a>

(38)

The method to solve this CWLS problem is proposed in [26]. We do not review it for the sake of brevity. Note that there are two constraints for (36) compared to one for (10), thus the method to solve (36) is different from the one to solve (10).

All the estimators based on TOA measurements are summarized in Tables 1, 2, and 3. They are characterized by the number of references, the reference dependency, the minimum number of anchors, and the optimal weighting matrices. We also shed light on their relations and categorize the existing methods from literature. We remark that the authors in [30] claim that the error covariance of the optimal position estimate using TOAs with a distance bias is equivalent to the one using TDOAs regardless of the reference selection, where the error covariance is defined as the product of the position dilution of precision (PDOP) and a composite user-equivalent range error (UERE). However, a more appropriate indication of the localization performance is the Cramér-Rao bound (CRB), which is a bound for unbiased estimators. Therefore, the CRB based on (1) for TOAs with a distance bias is derived in Appendix 4. Since the TDOAs in Section 2.3 are calculated by making differences of the TOAs in (1), the CRB based on these TDOAs is the same as the one based on (1).

Table 1. LS estimators based on TOAs for locating an asynchronous target

Table 2. WLS estimators based on TOAs for locating an asynchronous target

Table 3. CLS estimators based on TOAs for locating an asynchronous target

3. Localization based on TDOA measurements

3.1. System model

Let us now focus on TDOA measurements. In passive sensor array or microphone array localization, TDOA measurements are obtained directly by cross-correlating a pair of received signals. Thus, no correlation template is needed, and the clock-offset can be canceled out immediately. We reemphasize that these TDOA measurements are different from the TDOAs calculated by subtracting the TOAs. The data model for these TDOA measurements is given by [31]

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M81','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M81">View MathML</a>

(39)

where ri,j is the TDOA measurement, which is obtained by cross-correlating the received signal from the jth anchor with the one from the ith anchor. Note that the stochastic properties of the noise terms ni,j are totally different from the ones of the noise terms ni of (1). We approximate ni,j as zero-mean random variables, where cov(ni,j, np,q) = E[(ni,j-E[ni,j])(np,q - E[np,q])] = E[ni,j np,q], i, j, p, q, ∈ {1, 2,..., M}, i j, and p q. Defining ri as the collection of the corresponding distances to the M -1 TDOA measurements using the ith anchor as a reference, ri = [ri,1,..., ri,i-1, ri,i+1,..., ri,M]T, and ni = [ni,1,..., ni,i-1, ni,i +1,..., ni,M]T as the related noise vector, we write (39) in vector form as

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M82','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M82">View MathML</a>

(40)

Moving -di 1M-1 to the other side, making an element-wise multiplication and re-arranging, we achieve

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M83','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M83">View MathML</a>

(41)

where φi = Tiψa- ri ri and mi = -(2(Ti1 d) ⊙ ni + n i ni). The stochastic properties of mi are as follows

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M84','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M84">View MathML</a>

(42)

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M85','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M85">View MathML</a>

(43)

where we ignore the higher order noise terms to obtain (43) and assume that the noise mean E[[m]i] ≈ 0 under the condition of sufficiently small measurement errors. Note that the noise covariance matrix Σi of size (M - 1) × (M - 1) depends on the unknown d as well.

3.2. Localization based on squared TDOA measurements

We do not propose any new algorithms in this section, but summarize existing localization algorithms spread over different research areas and shed light on their relations. All these algorithms are categorized as reference-based SRD approaches. Note that (41) looks similar to (32). Only the available data and the noise characteristics are different, which leads to totally different relations among the estimators as we will show in the following paragraphs. The approach to achieve the REFB-USRD-LS(1) estimate, the REFB-USRD-LS(2) estimate and the REFB-SRD-CWLS estimate (36) based on TOA measurements in Section 2.3.2 can be adopted here as well. The orthogonal projection <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M86','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M86">View MathML</a> of size (M - 1) × (M - 1) onto the complement of ri is employed, which is given by (16), where we replace IM and Pu with IM-1 and ri. Let us define the nullspace <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M87','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M87">View MathML</a>, and <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M88','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M88">View MathML</a>. Therefore, <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M86','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M86">View MathML</a> is the projection onto <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M89','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M89">View MathML</a>. As a result, the REFB-USRD-LS(1) and REFB-USRD-WLS(1) estimate based on TDOA measurements is respectively given by,

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M90','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M90">View MathML</a>

(44)

and

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M91','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M91">View MathML</a>

(45)

where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M92','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M92">View MathML</a> is an aggregate weighting matrix of size (M - 1) × (M - 1) as well. Note that (44) (or (45)) differs from (18) (or (19)) since M - 1 TDOA measurements are used instead of M TOA measurements. The optimal <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M92','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M92">View MathML</a> is given by

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M93','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M93">View MathML</a>

(46)

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M94','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M94">View MathML</a>

(47)

where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M95','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M95">View MathML</a> is the pseudo-inverse of the matrix achieved by projecting the columns and rows of Σi onto <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M96','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M96">View MathML</a>, which is of rank M - 2. We remark that the REFB-USRD-LS(1) estimate (44) is equivalent to the ones in [22,32].

Let us also revisit the REFB-USRD-LS(2) estimate and the REFB-USRD-WLS(2) estimate based on TDOA measurements. A linear transformation <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M97','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M97">View MathML</a> of size (M - 2) × (M - 1), which fulfills <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M98','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M98">View MathML</a>, can be devised in the same way as Mj by replacing Tiu and 1/(uj-ui) with ri and 1/ri,j, respectively. Thus, <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M99','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M99">View MathML</a>. Note that another heuristic method to obtain <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M97','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M97">View MathML</a> is proposed in [20]. As a result, the general form of the REFB-USRD-LS(2) and the REFB-USRD-WLS(2) estimates can be derived in the same way as (44) and (45) by replacing <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M86','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M86">View MathML</a> and <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M92','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M92">View MathML</a> with <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M100','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M100">View MathML</a> and <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M101','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M101">View MathML</a>, respectively. Note that <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M101','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M101">View MathML</a> is also an aggregate weighting matrix of size (M - 1) × (M - 1). The optimal <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M102','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M102">View MathML</a> is given by

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M103','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M103">View MathML</a>

(48)

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M104','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M104">View MathML</a>

(49)

where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M105','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M105">View MathML</a> is also the projection onto <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M96','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M96">View MathML</a>, which means that <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M106','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M106">View MathML</a> and i j. The REFB-USRD-LS(2) estimate and the REFB-USRD-WLS(2) estimate based on TDOA measurements are generalizations of the estimators proposed in [20]. However, the noise covariance matrix in [20] is a diagonal matrix, and the noise covariance matrix Σi here is a full matrix.

We remark here that with the optimal weighting matrix, the REFB-USRD-WLS(1) estimate (45) and the REFB-USRD-WLS(2) estimate based on the same set of TDOA measurements are identical. However, the optimal weighting matrix cannot decouple the reference dependency. The performance of all the estimates still depends on the reference selection, since the reference dependency is an inherent property of the available measurement data. To further improve the localization performance, the REFB-SRD-CWLS estimate based on (41) can be derived in the same way as the estimate (36) by replacing ϱi and Bi with φi and <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M107','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M107">View MathML</a>, respectively. A solution to this CLS problem is presented in [26].

Note that all the above estimators are based on a so-called nonredundant set of TDOA measurements [31], resulting in reference dependency. Recently, a SM method based on the full set of TDOA measurements has been proposed in [33], labeled "reference-free TDOA source localization". It is reference-free in the sense that every anchor plays the role of reference, as in [17], thus there is no need to specifically choose one. We revisit the proposed method in [33] here to clarify its relation to our framework. Let us define <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M108','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M108">View MathML</a>, where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M109','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M109">View MathML</a> can be achieved by inserting a 0 in ri between ri,i-1 and ri,i+1. Using our notations, we can rewrite (22) of [33] as

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M110','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M110">View MathML</a>

(50)

Then, a matrix G of size (M - 2) × M, which fulfills GDr = 0M-2, can be obtained by exploring the nullspace of Dr using the singular value decomposition (SVD). Consequently, an LS estimator of x is given by

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M111','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M111">View MathML</a>

(51)

Note that <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M112','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M112">View MathML</a> without noise, and GDr = 0M-2. Thus, 1M is in the nullspace of G. As P is the projection onto the orthogonal complement of 1M, GP is still of rank M - 2 with probability 1. In a different way, we can make use of the full set of TDOA measurements similarly as the second extension of the approach proposed in [32]. We collect (41) in vector form as

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M113','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M113">View MathML</a>

(52)

As a result, a LS estimator of x and d can be derived based on (52). We do not detail it in the interest of brevity.

Furthermore, as indicated in [31], an optimal nonredundant set can be achieved by the optimum conversion of the full TDOA set in order to approach the same localization performance, and the use of this optimal nonredundant set is recommended to reduce the complexity. Because [31] relies on the assumption that the received signals at the anchors are corrupted by noise with equal variances, the optimal nonredundant set can be estimated by a LS estimator. This is not the case here however, where it should be estimated by a WLS estimator, which requires the knowledge of the stochastic properties of the noise.

We summarize the characteristics of all the estimators based on TDOA measurements in Table 4. With the nonredundant TDOA measurement set of length M - 1, the estimator performance suffers from a poor reference selection. Although the performance improves with the full set or the optimal nonredundant set, it first has to measure the full set of TDOAs of length M(M - 1)/2.

Table 4. LS, WLS, and CWLS estimators based on TDOAs for locating an asynchronous target

4. Numerical results

4.1. Noise statistics

In order to make a fair comparison between the localization performance of the different estimators using TOA measurements and TDOA measurements, we derive the statistics of ni and ni,j based on the same received signal models. The received signal is modeled by [33]

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M115','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M115">View MathML</a>

(53)

where N is the number of samples, κ is a constant parameter, s(n) is the source signal, and ei(n) and τi are respectively the additive noise and the delay at the ith node. We assume that s(n) is a zero-mean white sequence with variance <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M116','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M116">View MathML</a>, and ei(n) is also a zero-mean white sequence with variance <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M117','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M117">View MathML</a>, independent from the other noise sequences and s(n).

For the TOA-based approaches, we assume knowledge of the template s(n), and estimate τi by cross-correlating the received signal with the clean template:

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M118','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M118">View MathML</a>

(54)

Since there is an unknown bias due to asynchronous nodes, the distance ui corresponding to the timestamp is modeled as <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M119','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M119">View MathML</a>, where c is the signal propagation speed. The statistical properties of ni can be derived in a similar way as in [31], and are given by

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M120','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M120">View MathML</a>

(55)

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M121','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M121">View MathML</a>

(56)

where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M122','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M122">View MathML</a>. We remark that in reality, it is very difficult to obtain a clean template, since there are various kinds of error sources, such as multipath fading, antenna mismatch, pulse distortion, etc. Plugging (55) and (56) into (5), the entries of the covariance matrix Σ are given by

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M123','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M123">View MathML</a>

(57)

On the other hand, the TDOA estimates can be achieved by cross-correlating two received signals as follows

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M124','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M124">View MathML</a>

(58)

Thus, the estimate of the distance difference is <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M125','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M125">View MathML</a>, where the bias is canceled out naturally. The statistical properties of ni,j can also be derived in a similar way as in [31,33], and are given by

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M126','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M126">View MathML</a>

(59)

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M127','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M127">View MathML</a>

(60)

Note that similarly as in [33] the signal attenuation is taken into account in order to obtain more general noise statistics than in [31], but we correct the derivation errors in [33]. We remark that in reality, the TDOA estimates may face similar problems as the TOA estimates, since the received signals at different anchors may be totally different. Plugging (59) and (60) into (43), the entries of the covariance matrix Σi are given by

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M128','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M128">View MathML</a>

(61)

In the simulations, we generate ni and ni,j as zero-mean Gaussian random variables with covariance matrices specified as above.

4.2. Performance evaluation

As a well-adopted lower bound, the CRB is derived for localization estimators based on TOA measurements and TDOA measurements, respectively. Note that the estimators derived in this paper are biased. We remark that although the CRB is a bound for unbiased estimators, it still is interesting to compare it with the proposed biased estimators. Here, we exemplify the CRBs for location estimation on a plane, e.g., we take l = 2. We assume that ni and ni,j are Gaussian distributed. The Fisher information matrix (FIM) I1(θ) based on model (1) in Section 2 for TOA measurements is derived in Appendix 4, where θ = [xT, b]T, and x = [x1, x2]T. Consequently, we obtain <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M129','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M129">View MathML</a>. We observe that b is not part of <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M130','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M130">View MathML</a>. Therefore, no matter how large b is, it has the same influence on the CRB for TOA measurements. The FIM I2(x) and I3(x) based on model (39) in Section 3 are derived in Appendix 5 for the nonredundant set and the full set of TDOA measurements, respectively.

We consider three simulation setups. In Setups 1 and 2, eight anchors are evenly located on the edges of a 100 m × 100 m rectangular. Meanwhile the target node is located at [200 m, 30 m] and [10 m, 20 m] for Setups 1 and 2, respectively. Thus, the target node is far away from the anchors in Setup 1, but close to them in Setup 2. In Setup 3, all anchors and the target node are randomly distributed on a grid with cells of size 1 m × 1 m inside the rectangular. The performance criterion is the root mean squared error (RMSE) of <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M27','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M27">View MathML</a> versus a reference range <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M131','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M131">View MathML</a>, which can be expressed as <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M132','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M132">View MathML</a>, where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M133','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M133">View MathML</a> is the estimate obtained in the jth trial. Each simulation result is averaged over Nexp = 1,000 Monte Carlo trials. The bias b corresponding to the clock offset is randomly generated in the range of [0 m, 100 m] in each Monte Carlo run. We would like to compare all the REFF and REFB estimators, as well as the estimator proposed in [27] (first iteration) using TOA measurements, labeled the LS1 estimator, and the estimator proposed in [33] using the full TDOA set, namely the REFF-LS2 estimator.

4.2.1. Estimators using TOA measurements

Figure 1 shows the localization performance of the REFF estimators using TOA measurements under the three considered setups. The <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M130','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M130">View MathML</a> (the dotted line with "×" markers) is used as a benchmark. The REFF-USR-WLS estimator (8) with the optimal weighting matrix (the solid line with "+" markers) achieves the best performance, while the iterative approach to update the weighting matrix (the solid line with "◊" markers) also helps the REFF-USR-WLS estimator to converge to the best performance. The REFF-SR-CLS estimator (14) (the solid line with "○" markers) benefits from the constraints, and thus outperforms the REFF-USR-LS estimator (7) (the solid line with "*" markers). The concrete value of the bias b does not influence the localization performance. The curve of the REFF-USR-LS estimator with fixed b (the solid line with "∇" markers) and the one with random b overlap. Furthermore, the LS1 estimator [27] (the solid line with "□" markers) is sensitive to the geometry. It performs better than the REFF-USR-LS estimator in Setup 2, but worse in Setup 1. This observation is consistent with the one in [19]. In Setup 3 (random geometry), it fails under some cases due to its inherent instability, and performs unsatisfactorily.

thumbnailFigure 1. RMSE of x for the REFF estimators using TOAs for locating an asynchronous target. (a) Setup 1 and Setup 2. (b) Setup 3.

Figure 2 compares the localization performance of the REFF with the one of the REFB estimators using TOA measurements under Setups 1 and 2. Since there are no fixed anchors in Setup 3, we skip it in the comparison. We show both the performance of the best and the worst reference selection, which indicates the performance limits of the REFB estimators. The dashed lines with "+" and "∇" markers denote the performance bounds for the REFB-USRD-LS(1) and the REFB-USRD-LS(2), respectively. The best reference choice for the REFB-USRD-LS(1) estimator is the reference anchor with the shortest distance to the target node. Meanwhile, we do not observe the best reference pair selection for the REFB-USRD-LS(2) estimator following any rules. The curves for the REFF-USR-LS estimator (7) (the solid line with "*" markers) and the REFF-SR-CLS estimator (14) (the solid line with "○" markers) lie inside these limits. Their performances are neither too bad nor too good, but they do not suffer from a poor reference selection. As we have already proved that the optimal weighting matrix can compensate the impact of the reference selection, the curves of all the WLS estimators with optimal weights will overlap. Thus, we do not show the performance of the REFF-USR-WLS estimator again, which is already illustrated in Figure 1.

thumbnailFigure 2. RMSE of x for the REFF and the REFB estimators using TOAs for locating an asynchronous target. (a) Setup 1. (b) Setup 2.

4.2.2. Estimators using TDOA measurements

Let us first compare the CRBs employing different measurements in Figure 3. We observe the same tendency for both Setups 1 and 2. All the CRBs overlap above a specific SNRr threshold, which is 55 dB for Setup 1, and 50dB for Setup 2. Below the threshold, the CRB using TOA measurements (the solid line with "×" markers) is lower than the other CRBs. Meanwhile, the CRB using the full TDOA set (the dotted line with "×" markers) is lower than the ones using a nonredundant TDOA set (the dotted lines). The observations are consistent with the ones in [31]. On the other hand, the SNRr ranges of interest corresponding to a RMSE smaller than 100 = 1 m, are SNRr > 60 dB and SNRr > 30 dB for Setup 1 and Setup 2, respectively. Within this range of interest, there are no differences among the CRBs in Setup 1, and only small differences in Setup 2. Therefore, using different measurements would not cause obvious differences in the CRB at high SNR.

thumbnailFigure 3. The CRBs using TOAs <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M130','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M130">View MathML</a>, the nonredundant TDOA set <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M134','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M134">View MathML</a>, and the full TDOA set <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M135','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M135">View MathML</a>for locating an asynchronous target.

Figure 4 shows the localization performance of the REFF estimators using the full TDOA set under three setups. The CRB <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M135','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M135">View MathML</a> (the dotted line with × markers) is still used as a benchmark. We observe similar tendencies as in Figure 1. The REFF-WLS estimator based on (52) with the optimal weighting matrix (the solid line with "+" markers) achieves the best performance, while the iterative approach to update the weighting matrix (the solid line with "◊" markers) also facilitates the REFF-WLS estimator based on (52) to converge to the best performance. Moreover, the performance of the REFF-LS2 estimator (51) [33] (the solid line with "□" markers) is slightly worse than the REFF-LS estimator based on (52) (the solid line with "*" markers) in Setup 1. In general, their performances are very close. In Setup 3 (random geometry), they almost overlap with each other.

thumbnailFigure 4. RMSE of x for the REFF estimators using the full set of TDOAs for locating an asynchronous target. (a) Setup 1 and Setup 2. (b) Setup 3.

Figure 5 compares the localization performance of the REFF estimator using the full TDOA set with the one of the REFB estimators using the nonredundant TDOA set under Setups 1 and 2. Since there are no fixed anchors in Setup 3, we again skip it in the comparison. We show both the performance of the best and the worst reference selection, which indicates the performance limits of the REFB estimators. The dashed lines with "+" and "∇" markers denote the performance limits for the REFB-USRD-LS(1) (44) and the REFB-USRD-LS(2) estimator, respectively. The best reference choice for the REFB-USRD-LS(1) estimator is again the reference anchor with the shortest distance to the target node, which means we cross-correlate the received signal at the reference anchor with the ones at other anchors in order to achieve a nonredundant set of TDOA measurements. Meanwhile, we do not observe the best reference pair selection for the REFB-USRD-LS(2) estimator following any rules either. The curves for the REFF-LS estimator based on (52) (the solid line with "*" markers) and the REFF-LS2 estimator (51) [33] (the solid line with "□" markers) lie inside these limits. They are very close to the lower limits in Setup 1, and in the middle of the performance band in Setup 2. The performance band of the REFB-USRD-LS(1) estimator is quite narrow in Setup 2. On the other hand, the performance variation is very obvious for the REFB-USRD-LS(2) estimator.

thumbnailFigure 5. RMSE of x for the REFF estimator using the full set of TDOAs and the REFB estimators using the nonredundant set of TDOAs for locating an asynchronous target. (a) Setup 1. (b) Setup 2.

Finally, we verify the equivalence of the REFB-USRD-WLS estimators with the same optimal weighting matrix in Figure 6. As we have discussed before, the optimal weighting matrix can only release the impact of the second reference selection. The first reference selection decides the obtained data set. Therefore, using the same nonredundant set of TDOAs, the curves of the REFB-USRD-WLS(1) (45) (the solid lines with "◊" markers) and the REFB-USRD-WLS(2) estimators (the solid lines with "+" markers) overlap. A different performance can be obtained by employing different nonredundant TDOA sets. However, similarly as the CRB, the performance converges after some SNRr threshold. Finally, in Figure 7, we compare the localization performance of the REFF estimators using TOAs and the full TDOA set, respectively. They are very close at high SNRr, but diverge at low SNRr.

thumbnailFigure 6. RMSE of x for the REFB-USRD-WLS estimators using the nonredundant set of TDOAs for locating an asynchronous target.

thumbnailFigure 7. RMSE of x for the REFF estimator using TOAs and the full set of TDOAs for locating an asynchronous target.

5. Conclusions

In this article, we have proposed reference-free localization estimators based on TOA measurements for a scenario, where anchors are synchronized, and the clock of the target node runs freely. The reference-free estimators do not suffer from a poor reference selection, which can seriously degrade the localization performance of reference-based LS estimators. Furthermore, we generalized existing reference-based localization estimators using TOA or TDOA measurements, and expose their relations. Based on analysis and simulations, we have obtained the following important conclusions:

(1) Applying a projection is always preferred over making differences with a reference to get rid of nuisance parameters.

(2) The optimal weighting matrix can compensate for the impact of the reference selection for reference-based WLS estimators using TOA measurements, and make all those estimators equivalent. However, the optimal weighting matrix cannot release the reference influence for reference-based WLS estimators using a nonredundant set of TDOA measurements, but can make the estimators using the same set identical as well.

(3) There are corresponding equivalences between the SR-based and the SR-difference-based methods, which are all using TOA measurements.

(4) Beyond some SNR threshold, there are no obvious differences among the CRBs using TOA measurements, the nonredundant set and the full set of TDOA measurements, respectively.

(5) The performance of the reference-free LS estimators is neither too bad nor too good, but they do not suffer from a poor reference selection.

(6) The concrete value of the distance bias caused by the inaccurate clock does not affect the localization performance of the LS or WLS estimators.

Appendix 1 Derivation of λ for CLS

Substituting (14) into the constraint (11), we obtain

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M136','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M136">View MathML</a>

(62)

which has to be solved for λ, leading to the estimate <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M137','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M137">View MathML</a>. We exemplify how to solve (62) for localization on a plane, i.e.,/= 2. Since J is of rank 3, there are only three non-zero eigenvalues of (AT WA)-1J. Therefore, the square matrix (ATWA)-1 J of size 4 × 4 can be diagonalized as (AT WA)-1 J = VΛV-1, where V is of size 4 × 3, collecting the singular vectors corresponding to the three nonzero singular values, and Λ is a diagonal matrix with the three nonzero singular values (γi, i = 1, 2, 3) on its diagonal. According to the Kailath variant [34] and plugging the eigenvalue decomposition of (AT WA)-1 J into (AT WA + λJ)-1, we obtain

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M138','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M138">View MathML</a>

(63)

Substituting (63) into the constraint (62), we achieve

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M139','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M139">View MathML</a>

(64)

where

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M140','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M140">View MathML</a>

(65)

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M141','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M141">View MathML</a>

(66)

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M142','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M142">View MathML</a>

(67)

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M143','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M143">View MathML</a>

(68)

Now, (64) can be simplified as a seven-order equation as follows

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M144','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M144">View MathML</a>

(69)

After obtaining the seven roots of (69), we discard the complex roots, and plug the real roots into (14). Finally, we choose the estimate ŷ , which fulfills (10). Note that (14) is a CLS estimate of y with W = I. Since the optimal W* depends on the unknown d, the CWLS problem can be solved in a similar way by iteratively updating the weights and the estimates, thus we do not repeat it here.

Appendix 2 Proof of Pi ((Tiu) ⊙ (Tiu)) = PiTi(u ⊙ u)

Recalling that Tiu = Ti1 u - ui 1m-i, Ti 1m = 0M-1, and Pi Ti u = 0M-1, we prove that Pi((Ti u) ⊙ (Ti u)) in (33) is equivalent to Pi Ti (u u) as follows

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M145','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M145">View MathML</a>

(70)

Appendix 3 Derivation of (35)

The SVD of Pi Ti is given by <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M146','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M146">View MathML</a>, where Ui is of size (M - 1) × (M - 2) and Vi is of size M × (M - 2), which collect the left and right singular vectors corresponding to the M - 2 nonzero singular values, and Λi is a diagonal matrix with the M - 2 nonzero singular values on its diagonal. Note that <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M147','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M147">View MathML</a> and <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M148','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M148">View MathML</a>. As a result, the nullspace <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M149','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M149">View MathML</a>, and <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M150','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M150">View MathML</a>. Using the SVD and the property of the pseudo-inverse, we can write <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M151','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M151">View MathML</a> as

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M152','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M152">View MathML</a>

(71)

Plugging (71) and the SVD of PiTi into (34), and making use of the property of the pseudo-inverse again, we arrive at

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M153','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M153">View MathML</a>

(72)

where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M154','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M154">View MathML</a> is the projection onto <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M33','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M33">View MathML</a>.

Appendix 4 CRB derivation for localization based on TOA measurements

We analyze the CRB for jointly estimating x and b based on (1), and assume ni is Gaussian distributed. The FIM I1(θ) is employed, where θ = [xT, b]T, with entries defined as:

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M155','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M155">View MathML</a>

(73)

where

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M156','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M156">View MathML</a>

(74)

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M157','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M157">View MathML</a>

(75)

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M158','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M158">View MathML</a>

(76)

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M159','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M159">View MathML</a>

(77)

Appendix 5 CRB derivation for localization based on TDOA measurements

We analyze the CRB for estimating x based on (40), and assume ni,j is Gaussian distributed. The FIM I2(x) for the nonredundant set of TDOA measurements is employed, with entries defined as:

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M160','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M160">View MathML</a>

(78)

Where

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M161','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M161">View MathML</a>

(79)

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M162','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M162">View MathML</a>

(80)

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M163','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M163">View MathML</a>

(81)

Furthermore, let us define <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M164','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M164">View MathML</a>, where μi = [ μi,1,..., μi,i-1, μi,i+1,..., μi,M]T, and C as the covariance matrix of this full set of TDOA measurements. Then the FIM I3(x) for the full set can also be derived based on (78) by replacing μi and Ci with μ and C, respectively. We can obtain [μ]k = μi,j, where k = (i -1)M-i2/2-i/2 + j, k ∈ {1,2,...,M(M-1)/2}, i ∈ {1, 2,..., M-1}, j ∈ {2, 3,..., M} and j > i.

Consequently, we achieve

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/19/mathml/M165','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/19/mathml/M165">View MathML</a>

(82)

In the same way, [C]k,l = cov(ni,j, np,q), where l = (p - 1)M -p2/2 - p/2 + q, l ∈ {1,2,..., M(M -1)/2}, p ∈ {1,2,..., M - 1}, q ∈ {2, 3,..., M} and q > p.

Endnotes

aThe sensor elements of a passive sensor array are equivalent to the anchor nodes here. bGiven the matrix C of size n × r and the matrix D of size r × m both of rank r, then if A = CD, it holds that A= DC[35].

Competing interests

The authors declare that they have no competing interests.

Authors' contributions

All authors read and approved the final manuscript.

Acknowledgements

This research was supported in part by STW under the Green and Smart Process Technologies Program (Project 7976).

References

  1. Parkinson, B, Spilker J, Jr. (eds.), Global Positioning System: Theory and Application (American Institute of Astronautics and Aeronautics, Washington, DC, 1996) I

  2. D Torrieri, Statistical theory of passive location systems. IEEE Trans Aerosp Electron Syst 20(2), 183–198 (1984)

  3. V Chandrasekhar, WK Seah, YS Choo, HV Ee, Localization in underwater sensor networks: survey and challenges. Proc ACM WUWNet (New York, USA, 2006), pp. 33–40

  4. Y Huang, J Benesty, G Elko, R Mersereati, Real-time passive source localization: a practical linear-correction least-squares approach. IEEE Trans Acoust Speech Signal Process 9(8), 943–956 (2001)

  5. D Li, YH Hu, Least square solutions of energy based acoustic source localization problems. Proc ICPPW (Montreal, Canada, August, 2004), pp. 443–446

  6. J Caffery Jr., GL Stuber, Subscriber location in CDMA cellular networks. IEEE Trans Veh Technol 47(2), 406–416 (1998). Publisher Full Text OpenURL

  7. A Sayed, A Tarighat, N Khajehnouri, Network-based wireless location: challenges faced in developing techniques for accurate wireless location information. IEEE Signal Process Mag 22(4), 24–40 (2005)

  8. S Gezici, Z Tian, G Giannakis, H Kobayashi, A Molisch, H Poor, Z Sahinoglu, Localization via ultra-wideband radios: a look at positioning aspects for future sensor networks. IEEE Signal Process Mag 22(4), 70–84 (2005)

  9. N Patwari, J Ash, S Kyperountas, I AO Hero, R Moses, N Correal, Locating the nodes: cooperative localization in wireless sensor networks. IEEE Signal Process Mag 22(4), 54–69 (2005)

  10. K Cheung, H So, WK Ma, Y Chan, Least squares algorithms for time-of-arrival-based mobile location. IEEE Trans Signal Process 52(4), 1121–1130 (2004). Publisher Full Text OpenURL

  11. A Savvides, CC Han, MB Strivastava, Dynamic fine-grained localization in ad-hoc networks of sensors. Proc ACM MobiCom (Rome, Italy, 2001), pp. 166–179

  12. D Niculescu, B Nath, Ad hoc positioning system (APS) using AOA. Proc IEEE INFOCOM (San Francisco, CA, USA, 2003) 3, pp. 1734–1743

  13. P Bahl, V Padmanabhan, RADAR: an in-building RF-based user location and tracking system. Proc IEEE INFOCOM (Tel Aviv, Israel, 2000) 2, pp. 775–784

  14. Y Wang, G Leus, X Ma, Tracking a mobile node by asynchronous networks. Proc IEEE SPAWC (San Francisco, CA, USA, 2011), pp. 1–5

  15. J Yan, Algorithms for indoor positioning systems using ultra-wideband signals (Delft University of Technology, 2010) PhD Thesis

  16. Z Li, W Trappe, Y Zhang, B Nath, Robust statistical methods for securing wireless localization in sensor networks. Proc IPSN (Los Angeles, CA, USA, April, 2005), pp. 91–98

  17. S Venkatesh, R Buehrer, A linear programming approach to NLOS error mitigation in sensor networks. Proc IPSN (Nashville, TN, USA, 2006), pp. 301–308

  18. I Guvenc, S Gezici, F Watanabe, H Inamura, Enhancements to linear least squares localization through reference selection and ML estimation. Proc IEEE WCNC (Las Vegas, NV, USA, 2008), pp. 284–289

  19. J Smith, J Abel, Closed-form least-squares source location estimation from range-difference measurements. IEEE Trans Acoust Speech Signal Process 35(12), 1661–1669 (1987). Publisher Full Text OpenURL

  20. B Friedlander, A passive localization algorithm and its accurancy analysis. IEEE J Ocean Eng 12(1), 234–245 (1987)

  21. Y Chan, K Ho, A simple and efficient estimator for hyperbolic location. IEEE Trans Signal Process 42(8), 1905–1915 (1994). Publisher Full Text OpenURL

  22. P Stoica, J Li, Lecture notes--source localization from range-difference measurements. IEEE Signal Process Mag 23(6), 63–66 (2006)

  23. S Ganeriwal, R Kumar, MB Srivastava, Timing-sync protocol for sensor networks. Proc ACM SenSys (Los Angeles, CA, USA, 2003), pp. 138–149

  24. F Chan, H So, Efficient weighted multidimensional scaling for wireless sensor network localization. IEEE Trans Signal Process 57(11), 4548–4553 (2009)

  25. Y Bresler, A Macovski, Exact maximum likelihood parameter estimation of superimposed exponential signals in noise. IEEE Trans Acoust Speech Signal Process 34(5), 1081–1089 (1986). Publisher Full Text OpenURL

  26. A Beck, P Stoica, J Li, Exact and approximate solutions of source localization problems. IEEE Trans Signal Process 56(5), 1770–1778 (2008)

  27. S Zhu, Z Ding, Joint synchronization and localization using TOAs: a linearization based WLS solution. IEEE J Sel Areas Commun 28(7), 1017–1025 (2010)

  28. S Bancroft, An algebraic solution of the GPS equations. IEEE Trans Aerosp Electron Syst 21(1), 56–59 (1985)

  29. H Schau, A Robinson, Passive source localization employing intersecting spherical surfaces from time-of-arrival differences. IEEE Trans Acoust Speech Signal Process 35(8), 1223–1225 (1987)

  30. DH Shin, TK Sung, Comparisons of error characteristics between TOA and TDOA positioning. IEEE Trans Aerosp Electron Syst 38(1), 307–311 (2002). Publisher Full Text OpenURL

  31. HC So, YT Chan, F Chan, Closed-form formulae for time-difference-of-arrival estimation. IEEE Trans Signal Process 56(6), 2614–2620 (2008)

  32. M Gillette, H Silverman, A linear closed-form algorithm for source localization from time-differences of arrival. IEEE Signal Process Lett 15, 1–4 (2008)

  33. A Amar, G Leus, A reference-free time difference of arrival source localization using a passive sensor array. IEEE SAM, 157–160 (2010)

  34. G Golub, C van Loan, Matrix Computation (The Johns Hopkins University Press, Baltimore, 1996)

  35. S Barnet, Matrices, Methods and Applications, Oxford Applied Mathematics and Computing Science Series (Clarendon Press, Oxford, 1990)

  36. J Smith, J Abel, The spherical interpolation method of source localization. IEEE J Ocean Eng 12(1), 246–252 (1987). Publisher Full Text OpenURL