On the performance of wireless sensor network time difference of arrival localization under realistic interference and timing estimation errors

Abstract

The article addresses the modeling and performance analysis of wireless sensor network localization with direct-sequence spread-spectrum signals and network-based, time difference of arrival measurements. Realistic radio channel propagation and interference conditions are taken into account. Synchronization by means of a delay-locked loop is adopted for sensor signal tracking at the wireless sensor network anchor nodes. A comprehensive timing estimation analysis is presented with channel impairments, including pathloss attenuation, shadowing, multipath fading, and multi-access interference. The full statistics of the delay-locked loop tracking jitter are derived, which serves to assess the practically achievable synchronization accuracy and its variability with radio channel conditions and specific sensor location. The time difference of arrival measurements are then used for sensor localization based on an efficient iterative maximum likelihood estimation approach shown to outperform weighted least squares methods. Numerical results are presented to quantify the sensor localization accuracy limits, showing that the error is not uniform but varies considerably across the coverage region depending on the relative sensor position with respect to the different anchor nodes. Various factors related to changing wireless sensor network topologies and network loading conditions are also considered and their impact on localization performance is quantified.

Keywords

Wireless sensor network time difference of arrival localization performance analysis timing estimation

Introduction

Wireless sensor networks (WSNs) have several advantages and are recently finding widespread use and many applications in various fields.^1–3 One of the features of WSNs is the ability to support node localization and tracking with good accuracy, and several WSN localization techniques have received a lot of interest in the literature (see, for example, the works of Kulaib et al.,⁴ Boukerche et al.,⁵ and Mao et al.,⁶ and references therein). In general, network-based localization can be achieved by means of statistical signal processing algorithms that exploit time of arrival (TOA), time difference of arrival (TDOA), angle of arrival (AOA), and received signal strength (RSS) measurements from transmitted sensor node (SN) signals collected at a number of fixed anchor nodes (ANs).⁷ Other terminal-based localization techniques rely on processing signals at the mobile SNs but are of less interest in WSN deployments since low-cost, limited-power SNs cannot implement intensive processing algorithms. Recent WSN localization applications have thus mainly focused on network-based AN processing. A review of previous related techniques is presented in the next section. In particular, timing-based approaches, combined with broadband spread-spectrum signaling waveforms, can support reliable target positioning due to their high timing resolution and resistance to noise and interference. TDOA schemes, which use the differences of sensor signal epochs of arrival at the receiving ANs, do not require perfect timing alignment of SNs with the network infrastructure and have less stringent synchronization requirements, which make them amenable to low-complexity WSN implementations. As such, the present work focuses on TDOA-based localization and analyzes the achievable localization accuracy in realistic WSN propagation environments.⁸ More specifically, among the important challenges not previously addressed is the large variation in SN signal hearability at the multiple network nodes needed for TDOA localization (which requires at least four AN timing measurements). The SN signal may not be adequately received at remote ANs, especially under severe pathloss and shadowing conditions as well as interference from other active transmitters. It is therefore important to analyze these aspects and assess their impact on localization performance.

Accordingly, a first contribution of this work presents a detailed analysis of signal timing of arrival estimation by means of a delay-locked loop (DLL) under applicable radio propagation and multi-user interference. The use of the DLL is crucial for fine tracking of signal timing,⁹ and its performance is shown to be strongly dependent upon RSS and multipath fading conditions. The specific error statistics are obtained at each AN involved in sensor positioning. The analysis shows that the accuracy of timing estimation is highly sensitive to the radio propagation environment and SN relative position vis-à-vis different ANs, which provides important insights into the limits of timing measurements under realistic operating conditions. In a second contribution of the work, the obtained DLL tracking results are combined with an efficient iterative maximum likelihood algorithm¹⁰ and adapted for TDOA localization. The viability of the proposed method is demonstrated with numerous examples for different sensor and AN locations and network loading conditions, and benchmarked against other methods and theoretical bounds.¹¹

The rest of the article is organized as follows. First, a review of previous work is presented in the “Related work” section. The system and signal models are then introduced in the “System and signal models” section. The “Signal timing estimation” section presents the analysis of DLL time tracking and derivation of its error statistics. In the “TDOA localization performance analysis” section, the maximum likelihood TDOA localization algorithm is presented, and numerical results and discussions are given in the “Results and analysis” section, with final conclusions summarized in the “Conclusion” section.

Related work

Different approaches, such as those presented in the literature,^12–16 use RSS-based data that exploit readily available signal strength measurements. Filtering and combined differential localization is adopted in Adewumi et al.¹⁷ to further smooth RSS data, while adaptive processing to enhance performance is proposed in Chen et al.¹⁸ and Zhang et al.¹⁹ However, the RSS-based approaches are generally vulnerable to large dynamic range and severe shadowing, and fading conditions encountered in radio channels.²⁰ On the other hand, AOA-based techniques require complex antenna arrays and are not practical to use in low-cost, reduced-complexity deployments.⁷ A different perspective for radiation source detection using a network of detectors is introduced in Chase et al.’s study,²¹ which proposes a source-attractor radiation detection approach. In another aspect, timing-based techniques including TOA and TDOA are more commonly used for WSN localization due to their robustness. A survey of TOA methods is presented in Guvenc and Chong²² and Xu et al.,²³ and in Yu et al.²⁴ and Mekonnen and Wittneben,²⁵ clock frequency offsets and node position uncertainties are taken into consideration. However, it is noted that TOA-based techniques need to have precise knowledge of SN transmission epochs, and maintain strict timing alignment of the sensors with the WSN reference clock, which adds more constraints to the synchronization complexity of the SNs and WSN infrastructure. To the contrary, TDOA localization schemes do not require knowledge of the sensors’ exact transmission times as long as the ANs have a common timing reference. TDOA-based approaches were introduced in Bandiera et al.²⁶ and Wang et al.²⁷ based on iterative and constrained least squares algorithms. In Luo et al.,²⁸ a geometric-based approach for successively localizing neighboring sensors is proposed, and asynchronous WSNs are considered in Xiong et al.²⁹ based on a simplified linearization model used with maximum likelihood estimation. Distributed sensor localization using TDOA with frequency-hopping signals is analyzed in Zhang et al.,³⁰ and a different approach based on neural networks is proposed in Singh and Agrawal,³¹ while Ghelichi et al.³² introduce another geometric TDOA localization technique. However, it is noted that these works adopt simplistic timing error models and hypothetical assumptions in the positioning algorithms without considering the impact of actual timing estimation limitations and large discrepancies among different ANs in tracking the targeted SN signal under realistic channel impairments and increased interference conditions, which motivates the studies undertaken in this present work.

System and signal models

A WSN model is considered with a central AN serving the SNs of interest, surrounded by a number of additional nodes as shown in the layout of Figure 1.

Figure 1.

WSN with selected sensor node (SN) and anchor node (AN) placement.

The transmitted signal from a given SN is assumed to undergo small-scale fading and large-scale attenuation due to radio pathloss and shadowing. For large-scale attenuation, we use typical models, which include both deterministic and probabilistic components. More specifically, based on the experimental results of Martinez-Sala et al.,⁸ we adopt a two-slope pathloss propagation model with random shadowing effects, whereby the SN signal attenuation (in dB) at distance $d_{i}$ from an anchor node AN_i can be expressed as

L (d_{i}) = {\begin{matrix} 10 n_{1} lo g_{10} (d_{i}) + X_{σ}, for d_{i} < d_{0} \\ 10 n_{2} lo g_{10} (d_{i}) + X_{σ}, for d_{i} \geq d_{0} \end{matrix}

(1)

where $n_{1}$ and $n_{2}$ are pathloss exponents that depend on the sensor’s relative position with respect to the breakpoint $d_{0}$ . Shadowing due to obstructions is modeled by a lognormally distributed random variable $X_{σ}$ . In addition, since obstructions are likely to affect the sensor links with multiple ANs simultaneously, the shadowing variables are assumed to be partially correlated, according to

X_{σ} = a X_{c} + b X_{i}

(2)

where $X_{c}$ and $X_{i}$ denote the common and independent variables, respectively, and $a^{2} + b^{2} = 1$ . The shadowing variables follow a zero-mean lognormal probability density given by

f_{X} (x) = \frac{1}{\sqrt{2 π} σ x} \exp [- \frac{{(\ln (x) - μ)}^{2}}{2 σ^{2}}]

(3)

with $μ$ and $σ$ denoting the mean and standard deviation of ln(X), respectively. The numerical values of the different parameters that characterize the radio propagation model have a significant impact on the received power levels at different ANs, as will be subsequently shown.

For the modulation scheme, the transmitted signal from a given SN is assumed to use direct-sequence spread-spectrum (DS-SS) waveforms with binary phase shift keying (BPSK),³³ the signal at a given anchor node AN_i involved in sensor localization, may be expressed as

r_{i} (t) = \sqrt{2 β_{i} P} A (t) d (t) c (t) \cos (ω_{c} t) + n_{i} (t)

(4)

where $\cos (ω_{c} t)$ is the sinusoidal carrier, $d (t) = \sum_{j} d_{j}$ $p (t - j T)$ represents the information bearing signal with binary data symbols ${d_{j}}$ and unitary pulse $p (t)$ of duration T, P denotes the transmitted power, with $β_{i}$ representing an average attenuation factor related to large-scale pathloss and shadowing, while $A (t)$ represents small-scale multipath fading modeled with Nakagami-m distribution. The signal $c (t)$ is a pseudo-noise (PN) spreading code obtained from a pulse-shaped binary chip sequence; $c (t) = \sum_{k} c_{k} h$ $(t - k T_{c})$ , where ${c_{k}}$ denotes the binary chip symbols, $T_{c}$ is the chip interval, the ratio $N = T / T_{c}$ is the spreading factor, and $h (t)$ is the chip pulse. The $n_{i} (t)$ component accounts for thermal noise and multi-access interference (MAI) resulting from other active SNs. In general, the MAI component is typically the dominant factor in dense WSN deployment scenarios. Based on the central limit theorem, it is noted that the MAI additive power term can be modeled as Gaussian-distributed in the presence of a large number of interfering sensors. Assuming random independent spreading codes and denoting the Fourier transform of the chip waveform as $H (f) = FT {h (t)}$ , the average power due to the interfering sensors served by the same anchor node AN_i as the SN of interest can be obtained as

P_{si} = β_{i} P μ_{d} (N_{s} - 1) \int_{- \infty}^{\infty} {| H (f) |}^{4} df

(5)

where $N_{s}$ is the number of sensors per cell, all assumed to be received with equal power at their respective serving access node, and $μ_{d}$ is a data activity factor representing the fraction of time a given sensor is actively transmitting. To account for the aggregate MAI effects from all active sensors in WSN, the total MAI power can be expressed by

P_{n_{i}} = (1 + k_{oc}) P_{si}

(6)

where $k_{oc}$ is a factor that accounts for the equivalent effective increase in MAI due to other active SNs covered by other cells besides the home access node serving the sensor of interest.

In the subsequent numerical results, the relative average power factors and other-cell interference will be obtained by simulation of the radio propagation model with its pathloss attenuation and shadowing assumptions, and will have a noticeable impact on the accuracy of sensor signal timing estimation at different ANs.

Signal timing estimation

DLL timing synchronization

The accuracy of sensor position determination is highly dependent upon the performance of TOA estimation. For the DS-SS signaling schemes used in this work, accurate synchronization tracking is typically achieved by means of a DLL mechanism that follows coarse timing acquisition.⁹ A non-coherent DLL structure, as depicted in Figure 2, is used to avoid coherent carrier synchronization and data demodulation prior to de-spreading. The targeted sensor served by the central anchor station AN₁ must also be tracked by other ANs as well (four nodes are needed for TDOA localization). For each anchor node AN_i involved in the sensor positioning, a DLL device is used to track the timing of the received sensor signal. The relative delay $τ_{i}$ of the locally estimated PN code with respect to the reference timing clock gives a measure of the time-of-arrival for a given anchor node AN_i tracking the sensor.

Figure 2.

Delay-locked loop processing blocks.

For the DLL operation, the received signal is first mixed with a local oscillator (LO) for down conversion, and then fed to early and late branches having timing offsets of $\pm Δ T_{c}$ (fraction of the chip period), followed by low-pass filters (LPFs) to give the baseband outputs after correlation with advanced and delayed PN code replicas. The difference between the early and late squared outputs produces a discriminator signal $Δ Z = Z_{-} - Z_{+}$ which is low-pass filtered to form a correction signal $η (t)$ driving the numerically controlled oscillator (NCO) used to adjust the PN code timing phase $K_{0}$ . The NCO correction signal is obtained as

η (t) = β A^{2} (t) [R_{c}^{2} (τ - \hat{τ} - Δ T_{c}) - R_{c}^{2} (τ - \hat{τ} + Δ T_{c})] + N (t)

(7)

where $τ$ is the true signal delay and $\hat{τ}$ is the estimated one, $N (t)$ represents additive noise, and $R_{c} (t)$ is the PN code autocorrelation function defined as

R_{c} (t) = \frac{1}{T} \int_{0}^{T} c (t + τ) c (τ) d τ

(8)

Using a discrete-time sampled structure, the kth sample normalized tracking error is defined by

ϵ_{k} = \frac{τ_{k} - {\hat{τ}}_{k}}{T_{c}}

(9)

The discretized loop discriminator output becomes

η_{k} = β A_{k}^{2} S (ϵ_{k}) + N_{k}

(10)

where $S (ϵ)$ denotes the normalized DLL S-curve function, defined as

S (ϵ) = R_{c}^{2} (ϵ - δ) - R_{c}^{2} (ϵ + δ)

(11)

with an early–late loop offset $δ$ typically set to 1/2 (i.e. $Δ T_{c} = T_{c} / 2$ ).

The statistics of the timing error estimates are of primary interest in the performance analysis of positioning algorithms. This is considered next under the general model assumptions of the “System and signal models” section.

Time tracking statistics analysis

A digital DLL model is adopted in this work, and the timing estimates are recursively given by

\frac{{\hat{τ}}_{k}}{T_{c}} = \frac{{\hat{τ}}_{k - 1}}{T_{c}} + K [h (k - 1) \times η_{k - 1}]

(12)

where $h (k)$ is the loop filter and K is the NCO gain. For quasi-static channels, a dynamic recursion for the normalized timing error can be obtained as

ϵ_{k} = ϵ_{k - 1} - K [h (k - 1) \times (β A_{k - 1}^{2} S (ϵ_{k - 1}) + N_{k - 1})]

(13)

For a simple first-order filter $(h (k) = δ (k))$ , the stochastic difference equation (SDE) becomes

ϵ_{k} = ϵ_{k - 1} - K (β A_{k - 1}^{2} S (ϵ_{k - 1}) + N_{k - 1})

(14)

The recursive SDE obeys a first-order Markov random process, where the Nakagami-m random sample $A_{k - 1}$ is assumed independent of the zero-mean Gaussian noise term $N_{k - 1}$ . Then, the error process satisfies the Kolmogorov–Chapman equation

p_{k} (ϵ | ϵ_{0}) = \int_{- \infty}^{\infty} f_{k - 1} (ϵ | x) p_{k - 1} (x | ϵ_{0}) dx

(15)

where $ϵ_{0}$ is the initial timing error value, $p_{k} (x | ϵ_{0})$ is the probability density function (PDF) of $ϵ_{k}$ given $ϵ_{0}$ , and $f_{k - 1} (ϵ | x)$ is the transition PDF of $ϵ_{k}$ given $ϵ_{k - 1} = x$ . Equation (15) can be used to compute the steady-state timing error distribution by repeated iteration starting with $p_{0} (x | ϵ_{0}) = δ (x - ϵ_{0})$ . To perform this, the transition PDF $f_{k - 1} (ϵ | x)$ is needed. This PDF can be obtained as follows.¹⁰ First, the Nakagami-m distribution for the fading amplitude $A_{k}$ is given by

f_{A_{k}} (a) = \frac{2 m^{m} a^{2 m - 1}}{Γ (m) Ω^{m}} \exp (- \frac{m a^{2}}{Ω})

(16)

with parameters $m = Ω^{2} / Var [A_{k}^{2}]$ and $Ω = E [A_{k}^{2}]$ . It then follows that the squared amplitude $A_{k}^{2}$ is a Gamma-distributed random variable with PDF

f_{A_{k}^{2}} (y) = \frac{m^{m} y^{m - 1}}{Γ (m) Ω^{m}} \exp (- \frac{my}{Ω})

(17)

From equation (14), the random variable $ϵ_{k}$ , conditioned on $ϵ_{k - 1} = x,$ becomes

ϵ_{k} = x - K β A_{k - 1}^{2} S (x) - K N_{k - 1}

(18)

Defining the random variables $Z = x - K N_{k - 1}$ and $V = - K β A_{k - 1}^{2} S (x)$ , their respective PDFs can be obtained, as

f_{Z} (z | x) = \frac{1}{\sqrt{2 π} K σ_{n}} \exp (- \frac{{(z - x)}^{2}}{2 {(K σ_{n})}^{2}})

(19)

f_{V} (v | x) = \frac{1}{| K β S (x) |} f_{A_{k}^{2}} (- \frac{v}{K β S (x)})

(20)

Using conditional independence of the variables Z and V, the transition PDF is obtained by convolving the conditional PDFs, giving

f_{k - 1} (ϵ | x) = \int_{- \infty}^{\infty} f_{Z} (ϵ - v | x) f_{V} (v | x) dv

(21)

The DLL error statistics can thus be obtained and will be applied for various cases of interest in the localization examples discussed in the “Results and analysis” section.

Evaluation of timing estimation accuracy

To quantify the signal timing estimation performance, numerical results for the DLL tracking are presented. For the signaling waveforms, a root raised cosine waveform spectrum with 25% roll-off, a 256 spreading factor, and a chip period of 5 ns are assumed. As noted, propagation models applicable to outdoor WSN environments are taken into account to assess the performance variability as a result of changing SN location vis-à-vis different ANs in the WSN.

To take into consideration interference from other sensors served by multiple ANs, a WSN network is assumed with 25 ANs placed on a rectangular grid with 200 m maximum AN-AN separation, corresponding to an SN-to-AN range within a 100 m, as a realistically achievable coverage limit. The WSN layout provides two tiers of ANs surrounding the central AN₁ of interest, which is adequate to accurately model the interference environment. The other-cell interference factor was obtained by Monte Carlo simulation used to generate sensors uniformly spread across the WSN coverage area, where each sensor’s transmitted power is adjusted to yield a specific received power at their dedicated serving AN. The interference power from all sensors not belonging to the AN₁ coverage zone is then aggregated and divided by the interference accrued from other sensors served by the central AN₁, besides the sensor of interest. This yields the relative other-cell to same-cell interference ratio k_oc of equation (6). The simulations show that this factor is particularly sensitive to the pathloss exponents of the radio attenuation model, as seen from the numerical results shown in Table 1. The random shadowing was also found to increase the $k_{oc}$ factor, especially for larger standard deviation values. However, this is less likely in WSN scenarios, as larger σ values (of 10 dB or more) are more relevant to macro-cellular mobile networks. For our purpose, we adopt a k_oc factor of 0.54 (i.e. approximately 50% interference increase from neighbor cells), obtained with n₁ and n₂ pathloss exponents of 2.3 and 3.7, respectively, a breakpoint at 6 m, and shadowing standard deviation of 3 dB, with 50% correlation. It is also noted that interference will depend on the intermittent activity of other transmitters. For the subsequent results, we assume a µ_d factor equal to 0.1 (i.e. sensor transmissions having 10% duty cycle) since sensors are typically power limited, and many WSN applications only need to gather data in a sporadic way.

Table 1.

Relative other-cell interference factor $k_{oc}$ dependency on radio channel attenuation model.

Pathloss
Shadowing	Exponentsn₁ = 2.3, n₂ = 2.7	Exponentsn₁ = 2.3, n₂ = 3.7	Exponentsn₁ = 2.3, n₂ = 4.7
SD σ = 3 dB	$k_{oc}$ = 0.98	$k_{oc}$ = 0.54	$k_{oc}$ = 0.36
SD σ = 10 dB	$k_{oc}$ = 1.21	$k_{oc}$ = 0.69	$k_{oc}$ = 0.44

To assess the impact of the sensor power levels at various access nodes, selected sensor locations are chosen at different points throughout the coverage area. Referring to Figure 1, representative sensors are denoted as SN₁ through SN₆, with coordinates (25,25), (50,50), (75,75), (100,100), (50,0), and (100,0), respectively. Other choices are also possible, but the main purpose is to investigate the variability in power levels and the proximity to one, two, or all four ANs needed for TDOA sensor localization. By symmetry, other choices from different sub-triangles will give similar results. In addition, the average performance for uniformly distributed sensors in the coverage zone will be assessed in the next section. Referring to the average power levels received at the access nodes, Table 2 shows the β_i power factors for different SN points. Without loss of generalization, the $β_{1}$ term at anchor node AN₁ is normalized to unity, and other terms are defined relative to it. A wide variability across the coverage area is clearly seen. For instance, SN₁ has low received power at all three access nodes besides AN₁, and hence a signal emitted from this location will have low hearability, and therefore poor timing estimation at the remote ANs, and likewise for SN₂ to some extent. However, SN₄ is centrally located and equally well received by all nodes, and to a lesser degree for SN₃ and SN₅. On the other hand, SN₆, being close to two ANs and further away from the two others, is accordingly having good reception but only at AN₁ and AN₂.

Table 2.

Average power factors at different ANs for sensors SN₁ through SN₆.

Average power factor	β₁ (at AN₁)	β₂ (at AN₂)	β₃ (at AN₃)	β₄ (at AN₄)
SN₁ (25,25)	1.00E+00	3.08E–03	0.89E–03	3.08E–03
SN₂ (50,50)	1.00E+00	5.42E–02	1.85E–02	5.42E–02
SN₃ (75,75)	1.00E+00	3.15E–01	1.56E–01	3.15E–01
SN₄ (100,100)	1.00E+00	1.00E+00	1.00E+00	1.00E+00
SN₅ (100,50)	1.00E+00	0.99E+00	1.75E–01	1.76E–01
SN₆ (100,0)	1.00E+00	0.99E+00	1.63E–02	1.65E–02

SN: sensor node; AN: anchor node.

Table 3 summarizes results for the DLL tracking at AN₁ to AN₄, and it is seen that the change in timing estimation jitter (quantified by the timing standard deviation) among the selected SN positions for each of the ANs is indeed consistent with the previous observations, whereby higher jitter is observed at the more distant ANs from the SNs of interest. For the results of Table 3, a uniform loading of 50 sensors per coverage cell across the WSN was assumed, with a data activity factor set to 10% as noted previously. To gain further insight into the impact of increased sensor loading, we consider two other levels, namely, 100 and 200 sensors per cell. The corresponding DLL timing error PDFs are obtained using the analysis of the “Signal timing estimation” section, and the results are plotted in Figures 3 –8. The impact of increased cell loading resulting in wider-spread DLL error PDFs is clearly seen. Also, the sensors’ relative proximity to ANs affects their timing tracking. For instance, SN₁ timing estimation at AN₁ is very good but is much poorer at the other ANs. On the other hand, SN₄ is equally well tracked by all nodes, while SN₆ is better tracked at AN₁ and AN₂. It should be noted that the DLL tracking ranges have been limited to ±1.5T_c as errors beyond this range are assumed to lead to out-of-lock condition, triggering new timing acquisition. In summary, the obtained results serve to quantify the large differences in timing synchronization capabilities for WSNs with different radio channel conditions, loading levels, and deployment topology.

Table 3.

DLL timing SD at the four ANs receiving sensor signals.

DLL SD σ/T_c	AN₁	AN₂	AN₃	AN₄
SN₁ (25,25)	0.238	0.809	0.856	0.811
SN₂ (50,50)	0.239	0.549	0.672	0.536
SN₃ (75,55)	0.238	0.341	0.412	0.334
SN₄ (100,100)	0.239	0.245	0.244	0.246
SN₅ (100,50)	0.238	0.245	0.408	0.406
SN₆ (100,0)	0.239	0.247	0.682	0.686

DLL: delay-locked loop; SD: standard deviation; AN: anchor node; SN: sensor node.

Figure 3.

DLL tracking error PDFs at access nodes AN₁ to AN₄ for sensor SN₁ (25,25), with various cell loading and interference conditions: 50, 100, and 200 sensors per cell.

Figure 4.

DLL tracking error PDFs at access nodes AN₁ to AN₄ for sensor SN₂ (50,50), with various cell loading and interference conditions: 50, 100, and 200 sensors per cell.

Figure 5.

DLL tracking error PDFs at access nodes AN₁ to AN₄ for sensor SN₃ (75,75), with various cell loading and interference conditions: 50, 100 and 200 sensors per cell.

Figure 6.

DLL tracking error PDFs at access nodes AN₁ to AN₄ for sensor SN₄ (100,100), with various cell loading and interference conditions: 50, 100, and 200 sensors per cell.

Figure 7.

DLL tracking error PDFs at access nodes AN₁ to AN₄ for sensor SN₅ (100,50), with various cell loading and interference conditions: 50, 100, and 200 sensors per cell.

Figure 8.

DLL tracking error PDFs at access nodes AN₁ to AN₄ for sensor SN₆ (100,0), with various cell loading and interference conditions: 50, 100, and 200 sensors per cell.

TDOA localization performance analysis

Iterative maximum likelihood TDOA algorithm

As noted, TDOA-based localization is well suited for WSNs, where low-complexity, power-limited SNs may not be able to maintain tight synchronization with the WSN. In this work, we use an iterative approximate maximum likelihood (AML) localization technique introduced in Chan et al.¹⁰ However, rather than assuming hypothetical and unrealistically identical timing error statistics at different ANs, the DLL analysis is used with the signal attenuation and fading models, interference loading conditions, and sensor placement variations, discussed in the “Signal timing estimation” section, to obtain the specific timing error variances.

With regard to TDOA localization, it is known that the differences in times of arrival of the sensor signal at a minimum of four access nodes are needed (with AN₁ taken as reference node). Referring to Figure 1, the exact range between the ith AN and the sensor to be localized is

r_{i} = \sqrt{{(x - x_{i})}^{2} + {(y - y_{i})}^{2}}, i = 1, \dots, N

(22)

where $θ = [x y]^{T}$ represents the sensor coordinates. The range differences with respect to AN₁ are

d_{i 1} = r_{i} - r_{1}, i = 2, \dots, N

(23)

With noisy measurements, the variables $Δ_{i 1}$ corrupted by noise terms $n_{i}$ are given by

Δ_{i 1} = d_{i 1} + n_{i} = c t_{i 1}, i = 2, \dots, N

(24)

where c is the speed of light, and the variable $t_{i 1}$ denotes the difference in time-of-arrival between the ith and first reference node, respectively

t_{i 1} = t_{i} - t_{1}, i = 2, \dots, N

(25)

For compact notation, the following vector variables will be used subsequently

d = {[d_{21} \dots d_{N 1}]}^{T}

(26)

T_{d} = {[t_{21} \dots t_{N 1}]}^{T}

(27)

It is also noted that the TDOA measurements are correlated since they have a common term t₁. Therefore, the covariance matrix $Q_{t} = E [T_{d} {T_{d}}^{T}]$ is non-diagonal and can be obtained as

Q_{t} = [\begin{matrix} σ_{1}^{2} + σ_{2}^{2} & σ_{1}^{2} & σ_{1}^{2} & \dots & σ_{1}^{2} \\ σ_{1}^{2} & σ_{1}^{2} + σ_{3}^{2} & σ_{1}^{2} & \dots & σ_{1}^{2} \\ σ_{1}^{2} & σ_{1}^{2} & σ_{1}^{2} + σ_{4}^{2} & \dots & σ_{1}^{2} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ σ_{1}^{2} & σ_{1}^{2} & σ_{1}^{2} & \dots & σ_{1}^{2} + σ_{N}^{2} \end{matrix}]

(28)

where $σ_{i}^{2}$ represents the timing error variance at the ith AN, as obtained from the DLL analysis. For mathematical tractability, a Gaussian approximation is adopted, where the variances are estimated from the timing error PDFs. With the DLL Gaussian error statistical model, the joint PDF of the TDOA vector $T_{d}$ given the sensor position $θ$ is written as

p (T_{d} | θ) = {(2 π)}^{- (N - 1) / 2} {(det Q_{t})}^{- 1 / 2} \exp [\frac{- J (θ)}{2}]

(29)

where $J (θ)$ is given by

J (θ) = {[T_{d} - \frac{d (θ)}{c}]}^{T} Q_{t}^{- 1} [T_{d} - \frac{d (θ)}{c}]

(30)

The maximum likelihood estimator (MLE) of the position vector $θ$ is the one that maximizes the PDF in equation (29) and is obtained by setting the gradient of $J (θ)$ to zero.^10,11 Re-arranging terms in matrix form gives

Φ a = 0

(31)

where $a = [r_{2}^{2} - (r_{1} + Δ_{21})^{2} \dots r_{N}^{2} - {(r_{1} + Δ_{N 1})^{2}]}^{T}$ and the matrix $Φ$ is given by $Φ = WG$ with

W = {[\frac{\partial d}{\partial θ}]}^{T} Q_{t}^{- 1}

(32)

G = diag [\frac{1}{r_{2} + r_{1} + Δ_{i 1}} \dots \frac{1}{r_{N} + r_{1} + Δ_{N 1}}]

(33)

It then follows that

\begin{matrix} r_{i}^{2} - {(r_{1} + Δ_{i 1})}^{2} = 2 (x_{1} - x_{i}) x + 2 (y_{1} - y_{i}) y \\ + k_{i} - k_{1} - 2 r_{1} Δ_{i 1} - Δ_{i 1}^{2} \end{matrix}

(34)

with $k_{i} = x_{i}^{2} + y_{i}^{2}$ . Then, to solve for $θ$ , we can further rewrite the equation in matrix form as

2 Φ D θ = Φ (v_{1} + r_{1}) ψ

(35)

where

D = [\begin{matrix} x_{1} - x_{2} & y_{1} - y_{2} \\ ⋮ & ⋮ \\ x_{1} - x_{N} & y_{1} - y_{N} \end{matrix}]

(36)

v_{1} = {[Δ_{21}^{2} + k_{1} - k_{2} \dots Δ_{21}^{2} + k_{1} - k_{2}]}^{T}

(37)

ψ = 2 {[Δ_{21} \dots Δ_{21}]}^{T}

(38)

It is noted that, although the formulation in equations (35) to (38) gives a linear equation in the unknown position vector $θ$ , the weighting matrix $Φ$ contains elements of $θ$ , precluding a closed-form solution, and it is therefore necessary to solve the problem iteratively as in Chan et al.¹⁰ The algorithm starts with an initial value for $θ$ obtained by weighted least squares (WLS) solution as

θ = \frac{1}{2} {(D^{T} Q_{t}^{- 1} D)}^{- 1} D^{T} Q_{t}^{- 1} (v_{1} + r_{1} ψ)

(39)

This gives $θ$ in terms of $r_{1}$ . Then, using the constraint, $r_{1}^{2} = (x - x_{1})^{2} + (y - y_{1})^{2}$ , a quadratic equation in $r_{1}$ is obtained, with two possible roots. The best root is selected by choosing the one that minimizes the cost function $J (θ)$ . The initial value of $θ$ is used to calculate $Φ$ , and a new updated position estimate may then be obtained as

θ = \frac{1}{2} {(Φ D)}^{- 1} Φ (v_{1} + r_{1} ψ)

(40)

The resulting solution is obtained in terms of $r_{1}$ and must also satisfy the same quadratic equation. Applying the root selection procedure, the value of $θ$ is updated accordingly, and the same steps are then iterated until convergence.

Cramér–Rao lower bound analysis

The Cramér–Rao lower bound (CRLB) is a known fundamental limit in estimation theory that gives a lower bound on the minimum achievable variance of unbiased estimator.¹¹ The CRLB provides a benchmark for assessing the optimality of estimation techniques and is obtained from the Fisher Information Matrix (FIM), which depends on the PDF of the measurements, parameterized by the sensor position $θ$ . In our case, the FIM denoted by $I (θ)$ is a $2 \times 2$ matrix with entries given by

{[I (θ)]}_{ij} = - E [\frac{\partial^{2} \ln p (d (θ))}{\partial θ_{i} θ_{j}}]

(41)

where $θ = [θ_{1} θ_{2}]^{T} = [x y]^{T}$ . For Gaussian-distributed measurements, the FIM reduces to

I (θ) = {[\frac{\partial d (θ)}{\partial θ}]}^{T} Q_{d}^{- 1} [\frac{\partial d (θ)}{\partial θ}]

(42)

From equation (23), we readily have

\frac{\partial d}{\partial θ} = [\begin{matrix} \frac{x - x_{2}}{r_{2}} - \frac{x - x_{1}}{r_{1}} & \frac{y - y_{2}}{r_{2}} - \frac{y - y_{1}}{r_{1}} \\ ⋮ & ⋮ \\ \frac{x - x_{N}}{r_{N}} - \frac{x - x_{1}}{r_{1}} & \frac{y - y_{N}}{r_{N}} - \frac{y - y_{1}}{r_{1}} \end{matrix}]

(43)

with the covariance matrix of the d vector given by $Q_{d} = c^{2} Q_{t}$ . The variances of the position vector $θ$ components are bounded by the diagonal elements of the inverse FIM as per the CRLB limit,¹¹ thus giving

Var (θ_{i}) \geq {[I^{- 1} (θ)]}_{ii}

(44)

The CRLB can be used to assess the efficiency of the TDOA AML algorithm by comparing it with the residual mean squared error (MSE) of the estimated sensor coordinates, as presented next.

Results and analysis

Numerical results are presented to evaluate the WSN sensor positioning accuracy and its dependency on various factors of interest. First, in Figure 9, we illustrate the residual localization error cumulative distribution functions (CDFs) giving Prob.[error <= abscissa] achieved by applying the TDOA AML. The CDFs are shown for the representative sensor locations SN₁ through SN₆, and the results confirm the previous observations and clearly demonstrate that positioning is more accurate for centrally located sensors at comparable distance from all ANs, while the accuracy worsens as they move further away from the center. Better accuracy is also noticed for sensors closer to two ANs (e.g. SN₅ and SN₆). Table 4 further shows quantitative results for the error percentiles giving thresholds that upper-bound the location error with a given probability. For example, the 50th percentile (which also corresponds to the mean error, as the CDFs are practically Gaussian-distributed) gives a mean value 0.25 m for SN₄ followed by 0.34 and 0.41 m for SN₅ and SN₃, respectively, while it is 0.91 m for SN₁. Similar observations hold with the 67th and 90th percentiles as well. For example, the 90% percentile giving the value below which the position error is confined with probability 0.9 (indicative of poor performance figure) is seen to be ranging from 0.46 m for SN₄ to 1.91 m for SN₁.

Figure 9.

Comparison of localization error cumulative distribution functions for selected SN locations.

Table 4.

Examples of residual positioning error percentiles for SNs—SN₁ through SN₆.

Location error (meters)	SN₁	SN₂	SN₃	SN₄	SN₅	SN₆
50% percentile	0.91	0.68	0.41	0.25	0.34	0.59
67% percentile	1.20	0.89	0.53	0.32	0.45	0.83
90% percentile	1.91	1.42	0.81	0.46	0.65	1.41

SN: sensor node.

A comparative assessment of the adopted AML localization algorithm with another commonly used approach based on WLS estimation is also shown in Figure 10 which depicts the CDFs of the residual localization error for several SNs. The comparisons clearly show that the proposed AML offers improved accuracy over the WLS method. In another aspect, to illustrate the variability in localization accuracy across the WSN, the iterative AML average performance is depicted by the color plot in Figure 11, which shows contours of equal residual MSE as a function of sensor coordinates in the coverage zone. It is noted that the MSE is lowest when the sensor is close to the center (at comparable distance from all ANs), while it is highest as it gets close to its home AN. To further demonstrate the viability of the proposed TDOA MLE localization technique, a similar color plot is given in Figure 12 based on the CRLB bound, and it can be seen that the CRLB results are in line with the previous observations, which validates the efficiency of the iterative MLE algorithm used in this work.

Figure 10.

Performance comparison of the proposed AML and WLS approaches.

Figure 11.

TDOA AML algorithm mean squared error (MSE) dependence on sensor coordinates.

Figure 12.

TDOA CRLB minimum achievable bound and its dependence on sensor coordinates.

In addition to the previous results obtained with a network loading of 50 sensors per cell, we illustrate in Figure 13 the impact of increased loading by considering 100 and 200 sensors per cell. The results show CDFs for the localization error assuming the sensors are uniformly distributed across the coverage zone. As expected, higher loading causes a deterioration in localization accuracy due to higher interference and subsequent increase in DLL timing jitter. As an example, the results of 50th percentile (mean) error are 0.54, 0.66, and 0.81 m for 50, 100, and 200 sensors per cell, respectively. Finally, in Figure 14, we investigate the impact of increasing the number of access nodes involved in TDOA sensor positioning (beyond the minimum number of four), and it can be seen that some incremental improvements in accuracy are achieved by using five and six ANs, especially if we consider the higher error percentile ranges (around 90%). However, it should also be noted that these small improvements are at the expense of increased messaging and processing complexity.

Figure 13.

Cumulative distribution functions (CDFs) for the average localization error across the coverage area. Comparison of different cell loadings: 50, 100, and 200 sensors per cell.

Figure 14.

Cumulative distribution functions (CDFs) for the average localization error across the WSN coverage area. Comparison for the results of TDOA localization using four, five, and six anchor nodes.

Conclusion

The article dealt with the performance analysis of TDOA positioning in WSNs employing DS-SS signals. A detailed radio propagation model incorporating pathloss, shadowing, and fading effects was used to assess the realistic capability of DLL time tracking of the sensors’ emitted signals at the ANs involved in positioning. The effect of MAI was also taken into account. It was found that the large variability in received power levels at different ANs has a major impact on synchronization accuracy depending on the sensor’s relative position with respect to the different ANs. Using the DLL tracking statistics, an iterative maximum likelihood technique was adopted for TDOA positioning, and validated by comparison with other approaches and theoretical bounds. It was found that the localization performance varies considerably across the coverage zone, whereby accuracy is best for sensors located in the central part at comparable distance from all access nodes, while the error deteriorates as the sensor gets closer to its main serving AN. Several simulations and numerical results were presented to quantify the achievable sensor localization accuracy under different radio channel impairments and network operating conditions.

Footnotes

Handling Editor: Chase Wu

Declaration of conflicting interests

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

Funding

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

ORCID iD

Mohamed Adnan Landolsi

References

Akyildiz

Sankarasubramaniam

et al . Wireless sensor networks: a survey. Comput Netw 2002; 38: 393–422.

Puccinelli

Haenggi

Wireless sensor networks: applications and challenges of ubiquitous sensing. IEEE Circuit Syst Mag 2005; 5: 19–31.

Zhang

. A review of wireless sensor networks and its applications. In: Proceedings of the IEEE international conference on automation and logistics, Zhengzhou, China, 15–17 August 2012, pp.386–389. New York: IEEE.

Kulaib

Shubair

Al-Qutayri

et al . An overview of localization techniques for wireless sensor networks. In: Proceedings of the international conference on innovations in informational technology, Abu Dhabi, UAE, 25–27 April 2011, pp.167–172. New York: IEEE.

Boukerche

Oliveira

Nakamura

et al . Localization systems for wireless sensor networks. IEEE Wirel Commun 2007; 14(6): 6–12.

Mao

Fidan

Anderson

Wireless sensor network localization techniques. Comput Netw 2007; 51(10): 2529–2553.

Sayed

Tarighat

Khajehnouri

Network-based wireless location. IEEE Signal Pr Mag 2005; 22: 24–40.

Martinez-Sala

Molina-Garcia-Pardo

J-M

Egea-Lopez

et al . An accurate radio channel model for wireless sensor networks simulation. J Commun Netw 2005; 7(4): 1–7.

Tsai

TH.

Stochastic-based analyses of non-coherent code tracking loops over wireless fading circumstances. IEEE T Veh Technol 2012; 61(1): 258–274.

10.

Chan

Hang

Ching

PC.

Exact and approximate maximum likelihood localization algorithms. IEEE T Veh Technol 2006; 55(1): 10–16.

11.

Kay

Fundamentals of statistical signal processing (Vol. I: Estimation Theory). Upper Saddle River, NJ: Prentice Hall, 1993.

12.

Sahu

Sahoo

DuRT: dual RSSI trend based localization for wireless sensor networks. IEEE Sens 2013; 13(8): 3115–3123.

13.

Yaghoubi

Abbasfar

Maham

Energy-efficient RSSI-based localization for wireless sensor networks. IEEE Commun Lett 2014; 18(6): 973–976.

14.

Al Alawi

RSSI based location estimation in wireless sensors networks. In: Proceedings of the 17th IEEE international conference on networks, Singapore, 14–16 December 2011, pp.118–122. New York: IEEE.

15.

Shu

Liu

. A performance evaluation model for RSS-based vertical handoff algorithms. In: Proceedings of the 14th IEEE symposium on computers and communications, Sousse, Tunisia, 5–8 July 2009, pp.271–276. New York: IEEE.

16.

Zhao

et al . Localization of wireless sensor networks in the wild: pursuit of ranging quality. IEEE/ACM Trans Netw 2013; 21(1): 311–323.

17.

Adewumi

Djouani

Kurien

. RSSI based indoor and outdoor distance estimation for localization in WSN. In: Proceedings of the IEEE international conference on industrial technology (ICIT), Cape Town, South Africa, 25–28 February 2013, pp.1534–1539. New York: IEEE.

18.

Chen

Pan

Liang

et al . AWCL: adaptive weighted centroid target localization algorithm based on RSSI in WSN. In: Proceedings of the 3rd international conference on computer science and information technology, Chengdu, China, 9–11 July 2010, pp.331–336. New York: IEEE.

19.

Zhang

An adaptive localization algorithm based on RSSI in wireless sensor networks. IEEE Int Conf Cloud Comp Int Syst 2012; 3: 1133–1136.

20.

Heurtefeux

Valois

Is RSSI a good choice for localization in wireless sensor networks? In: Proceedings of the IEEE 26th international conference on advanced information networking and applications, Fukuoka, Japan, 26–29 March 2012, pp.732–739. New York: IEEE.

21.

Chase

Mark

Berry Kayla

et al . A source-attractor approach to network detection of radiation sources. In: Proceedings of the IEEE international conference on multisensor fusion and integration for intelligent systems (MFI), Baden-Baden, 19–21 September 2016, pp.394–399. New York: IEEE.

22.

Guvenc

Chong

A survey on TOA-based wireless localization and NLOS mitigation techniques. IEEE Comm Surv Tutorial 2009; 11(3): 107–124.

23.

Xu;

Ding

Dasgupta

Source localization in wireless sensor networks from signal time-of-arrival measurements. IEEE Trans Signal Process 2011; 59(6): 2887–2897.

24.

Guo

Hedley

TOA-based distributed localisation with unknown internal delays and clock frequency offsets in wireless sensor networks. IET Signal Process 2009; 3(2): 106–118.

25.

Mekonnen

Wittneben

. Robust TOA based localization for wireless sensor networks with anchor position uncertainties. In: Proceedings of the IEEE 25th annual international symposium on personal, indoor, and mobile radio communication (PIMRC), Washington, DC, 2–5 September 2014, pp.2029–2033. New York: IEEE.

26.

Bandiera

Coluccia

Ricci

et al . TDOA localization in asynchronous WSNs. In: Proceedings of the 12th IEEE international conference on embedded and ubiquitous computing, Milano, 26–28 August 2014, pp.193–196. New York: IEEE.

27.

Wang

Bai

et al . Enhanced constrained total least squares estimator in TDOA localization for WSNs. In: Proceedings of the international conference on computer science and service system (CSSS), Nanjing, China, 27–29 June 2011. pp.389–392. New York: IEEE.

28.

Luo

Lin

Geometric location based on TDOA for wireless sensor networks. ISRN Appl Math 2012; 2012: 710979.

29.

Xiong

Chen

et al . Robust TDOA localization algorithm for asynchronous wireless sensor networks. Int J Distrib Sens Netw 2015; 2015: 598747.

30.

Zhang

Yin

Feng

et al . Distributed TDOA estimation for wireless sensor networks based on frequency-hopping in multipath environment. In: Proceedings of the IEEE 71st vehicular technology conference (VTC 2010-Spring), Taipei, Taiwan, 16–19 May 2010. New York: IEEE.

31.

Singh

Agrawal

TDOA based node localization in WSN using neural networks. In: Proceedings of the international conference on communication systems and network technologies, Gwalior, India, 6–8 April 2013, pp.400–404. New York: IEEE.

32.

Ghelichi

Yelamarthi

Abdelgawad

. Target localization in wireless sensor network based on time difference of arrival. In: Proceedings of 56th international Midwest symposium on circuits and systems (MWSCAS), 4–7 August 2013, pp.940–943. DOI:10.1109/MWSCAS.2013.6674805.

33.

Rappaport

TS.

Wireless communications: principles and practice. 2nd ed. Upper Saddle River, NJ: Prentice-Hall, 2001.