# Distributed Source Localization Based on TOA Measurements in Wireless Sensor Networks

Authors: Wanzhi Qiu; Efstratios Skafidas
Journal: Research Letters in Electronics
 (2009)

---

## Abstract

We study the problem of source localization in multihop wireless sensor networks. A fully distributed algorithm based on sensor measurements of time of arrivals (TOAs) is proposed. In contrast to centralized methods where all TOA measurements are transmitted via certain routes to a central location (the sink) for processing, the proposed method distributes the processing among the relay nodes on the routes to the sink. Fusion strategies are proposed so that the raw and intermediate data are progressively processed, and only the refined results are further relayed. As a result, the proposed scheme has improved flexibility and scalability since it does not impose any special requirements on the sink node. The proposed distributed strategy also has the potential to save energy and bandwidth due to reduced radio transmissions.


---

## Body

## 1. Introduction

In centralized wireless sensor network (WSN) source localization, the transmission of all the raw
measurements to a central point is required and the processing is performed in
a centralized manner. These schemes have the potential to achieve optimum
solutions due to the availability of the full data set at the processing point.
However, the centralized systems typically have low energy efficiency and low
scalability due to excessive radio transmissions and dependency on a central
processing node.Distributed methods based on clustering have been proposed [1]. In [2], the intermediate result is cycled through the network on specially
designed routes, and each node makes a small adjustment to the received
estimate based on deepest descent on a cost function, then passes updated
estimate to one of its neighbours.In this paper, we propose a fully distributed source localization
algorithm based on TOA measurements in multihop wireless sensor networks. The
proposed scheme distributes the localization process among the relay nodes
along the routes to the (arbitury) node where the localization estimate is
needed. Whenever determined feasible, the intermediate estimate is produced or
refined by incorporating TOAs and intermediate estimates available at the local
node. Data fusion strategies are proposed so that the raw and intermediate data
are progressively processed and only the refined results are further relayed.


## 2. The Data Model and Centralized Processing

As in [3] and illustrated in Figure 1, for a
signal emitted by the source at time T (unknown),
the TOA measurement at node i (i=1,…,N,N≥3) is modelled by (1)ti=T+Ric+εi,i=1,…,N,  where εi denotes measurement noise and c the propagation speed. The noise
samples are assumed to be uncorrelated with zero mean and variance σ2.
No assumption is made about the probability of density function of the noise.
The distance between the source and a node located at (xi,yi) is given by Ri=(x−xi)2+(y−yi)2.Figure 1
Source localization geometry.We assume that a nominal source position(xn,yn) is available. This nominal position, which
is close to the true source position (x,y), could have been obtained from the previous measurements. Such a
situation is typical when the source is being tracked [3]. Hence, to estimate
the source position we require an estimation of [(x−xn)(y−yn)]T=[δxδy]T,
where T denotes matrix transpose.Using a first-order Taylor  expansion ofRi about (xn,yn) and defining Rni=(xn−xi)2+(yn−yi)2,
we have Ri≈Rni+(xn−xi)Rniδx+(yn−yi)Rniδy. Therefore, (1) can be expressed as (2)τi≈T+cosαicδx+sinαicδy+εi, where cosαi=(xn−xi)Rni,sinαi=(yn−yi)Rni,, and τi=ti−Rni/c.By collecting all TOA measurements at one
point, the centralized processing scheme formulates the modelx=Hθ+w, where x=[τ1τ2⋯τN]T,θ=[Tδxδy]T,w=[ε1ε2⋯εN]T, and (3)H=[1cosα1csinα1c1cosα2csinα2c⋮⋮⋮1cosαNcsinαNc]. Based on this linear model, the unknowns T,δx, and δy can be solved by the best linear unbiased
estimator (BLUE) θ=[HTH]−1HTx, and the estimation variances are given by the diagonal
items of the covariance matrix Cθ=σ2[HTH]−1,
that is, [σT2,σδx2,σδy2]=[Cθ(1,1),Cθ(2,2),Cθ(3,3)].Note that, in order to perform the
estimation, the sink, where the processing is performed, has to know the
locations of all participating nodes as well as their TOA measurements. This
could cause severe communication/energy problems in situations when, for
example, nodes are moving and therefore
being required to constantly report their locations to the sink.


## 3. The Proposed Distributed Processing

As with the centralized processing, we assume that the sink is the
point where the final estimate is needed. However, in the proposed scheme, the
sink is just an ordinary node which does not have additional energy or
computing capacity and does not perform any additional work as compared to
other nodes. Only the nodes which have a TOA measurement or have received any
measurements or intermediate estimates (IEs) from the up-stream nodes participate
in the process. The principle is, for each participating node, to process the available measurements and/or IEs
whenever possible and to
send the result to the next-hop node (i.e., the down-stream node). The fusion
result from the sink node is the final estimate. Note that the proposed scheme
does not require any special arrangements on other functionalities of the
network such as routing; TOA measurements and IEs are fused naturally while
travelling on any established routes to the sink.Different fusion rules have to be used
depending on the information available at a node. Basically, three or more TOA
measurements can be fused into one IE where a TOA measurement is defined as the
location of the node and its measuredτi,
that is, TOA≜(xi,yi,τi).
The IE is defined as the estimates of the unknowns and their corresponding
variances, that is, IE=(δx^,δy^,δT^,σδx2,σδy2,σT2).  An IE can be further fused with one
measurement, two measurements, or one or more IEs. Fusion is performed at a
local node after receiving all TOAs and/or IEs from up-stream nodes. When an IE
is obtained, all follow-on transmission on this particular route will involve
one IE only. Figure 2 depicts a typical fusion scenario where the arrows
represent data transmissions, and rectangular blocks indicate performed fusion
functions which are described in detail below.Figure 2
A typical fusion scenario.


### 3.1. Fuse_TOAs()

This
function fusesN (≥3) TOA measurements into one IE.
The formulas used here are exactly the same as in Section 2.


### 3.2. Fuse_IEs()

WhenN (>1) IEs are available, they can be combined according to the
principle of BLUE to yield an updated IE. That is, for (δxn^,δyn^,δTn^,σδxn2,σδyn2,σTn2), where n=1,…,N, the updated IE is given by δx_new=σδx_new2∑n=1Nδxn^/σδxn2,δy_new=σδy_new2∑n=1Nδyn^/σδyn2, and Tn^_new=σT_new2∑n=1NTn^/σTn2, where σδx_new2=(∑n=1N1/σδxn2)−1,σδy_new2=(∑n=1N1/σδyn2)−1,   and σT_new2=(∑n=1N1/σTn2)−1.As
can be seen from the above equations, the BLUE is actually a weighted average of the estimates,
giving the more accurate (with smaller variances) ones larger weights.


### 3.3. Fuse_IE_with_one_TOA()

We now fuse one intermediate estimateIE0=(δx^,δy^,T^,σδx2,σδy2,σT2) with one TOA (xi,yi,τi) measured by a certain node ni.
In other words, we refine IE0 with
the new information provided by the TOA measurement. In order to do this, we
approximate T by its estimated value T^ and refine the estimates of δx and δy only. By denoting T≈T^+εT,
where εT is the error in the estimate of T, the TOA measurement (2) can be
expressed by τi−T^≈(cosαi/c)δx+(sinαi/c)δy+εi+εT which can be further simplified as (4)z=aδx+bδy, where a=cosαi/c,b=sinαi/c, and (5)z=zo+εi+εT,zo=τi−T^. When the error terms (εi and εT) are ignored, (4) can be represented by a
straight line in the δx−δy plane. The estimate (δx^,δy^) is a point on the same plane, and we propose
to use a weighted average of it and its projection onto line (4) (δx′^,δy′^) as the new estimate.
As far as the node ni can see, (δx′^,δy′^) lies on the circle centred
at (xi,yi) with radius r=czo,
where c is the propagation speed. It
can be seen from (5) that the variance of r is given by σr2=c2(σ2+σT2).
Since it is too complex to obtain the exact expressions for the variances of δx′^ and δy′^, in order to determine their weights in forming the new estimates, we
will use σr2 to approximate their variances,  that is, σδx′2≈σδy′2≈σr2.
This approximation is in line with the new information the TOA measurement
provides on the source location.By denotingK=a2+b2, the projection coordinates
can be expressed by (6)(δx′^,δy′^)=(aKzo+b2Kδx^−abKδy^,bKzo−abKδx^+a2Kδy^), leading to new estimates (7)δx_new=σδx_new2(δx^σδx2+δx′^σδx′2),δy_new=σδy_new2(δy^σδy2+δy′^σδy′2),    with updated variances σδx_new2=(1/σδx2+1/σδx′2)−1 and σδy_new2=(1/σδy2+1/σδy′2)−1.


### 3.4. Fuse_IE_with_two_TOAs()

Here, we have two TOA measurements(x1,y1,τ1) and (x2,y2,τ2) along with one IE IE0=(δx^,δy^,T^,σδx2,σδy2,σT2) available. We first use the BLUE principle to
fuse the two TOAs to obtain initial estimates δx′^ and δy′^.
The result is then further fused with IE0. As in the previous section, by denoting T≈T^+εT,
for i=1,2,
we have zi=aiδx+biδy+εi+εT,
where ai=cosαi/c, bi=sinαi/c, and zi=τi−T^.By definingx=[z1z2]T,H=[a1b1a2b2],θ=[δxδy]T, and w=[ε1+εTε2+εT]T,
we have x=Hθ+w which immediately leads to the following BLUE
[3]: (8)[δx′^,δy′^]T=[HTC−1H]-1HTC−1x, with covariance matrix Cθ=[HTC−1H]-1, where, with E denoting expectation, (9)C=E(wwT)=(σ2+σT2σT2σT2σ2+σT2). That is, [σδx'2,σδy'2]=[Cθ(1,1),Cθ(2,2)].
This fusion function is now summarized as follows. Step 1, use (8) to obtain δx′^ and δy′^.
Step 2, fuse (δx′^,δy′^) and (δx^,δy^) using (7).


## 3.1. Fuse_TOAs()

This
function fusesN (≥3) TOA measurements into one IE.
The formulas used here are exactly the same as in Section 2.


## 3.2. Fuse_IEs()

WhenN (>1) IEs are available, they can be combined according to the
principle of BLUE to yield an updated IE. That is, for (δxn^,δyn^,δTn^,σδxn2,σδyn2,σTn2), where n=1,…,N, the updated IE is given by δx_new=σδx_new2∑n=1Nδxn^/σδxn2,δy_new=σδy_new2∑n=1Nδyn^/σδyn2, and Tn^_new=σT_new2∑n=1NTn^/σTn2, where σδx_new2=(∑n=1N1/σδxn2)−1,σδy_new2=(∑n=1N1/σδyn2)−1,   and σT_new2=(∑n=1N1/σTn2)−1.As
can be seen from the above equations, the BLUE is actually a weighted average of the estimates,
giving the more accurate (with smaller variances) ones larger weights.


## 3.3. Fuse_IE_with_one_TOA()

We now fuse one intermediate estimateIE0=(δx^,δy^,T^,σδx2,σδy2,σT2) with one TOA (xi,yi,τi) measured by a certain node ni.
In other words, we refine IE0 with
the new information provided by the TOA measurement. In order to do this, we
approximate T by its estimated value T^ and refine the estimates of δx and δy only. By denoting T≈T^+εT,
where εT is the error in the estimate of T, the TOA measurement (2) can be
expressed by τi−T^≈(cosαi/c)δx+(sinαi/c)δy+εi+εT which can be further simplified as (4)z=aδx+bδy, where a=cosαi/c,b=sinαi/c, and (5)z=zo+εi+εT,zo=τi−T^. When the error terms (εi and εT) are ignored, (4) can be represented by a
straight line in the δx−δy plane. The estimate (δx^,δy^) is a point on the same plane, and we propose
to use a weighted average of it and its projection onto line (4) (δx′^,δy′^) as the new estimate.
As far as the node ni can see, (δx′^,δy′^) lies on the circle centred
at (xi,yi) with radius r=czo,
where c is the propagation speed. It
can be seen from (5) that the variance of r is given by σr2=c2(σ2+σT2).
Since it is too complex to obtain the exact expressions for the variances of δx′^ and δy′^, in order to determine their weights in forming the new estimates, we
will use σr2 to approximate their variances,  that is, σδx′2≈σδy′2≈σr2.
This approximation is in line with the new information the TOA measurement
provides on the source location.By denotingK=a2+b2, the projection coordinates
can be expressed by (6)(δx′^,δy′^)=(aKzo+b2Kδx^−abKδy^,bKzo−abKδx^+a2Kδy^), leading to new estimates (7)δx_new=σδx_new2(δx^σδx2+δx′^σδx′2),δy_new=σδy_new2(δy^σδy2+δy′^σδy′2),    with updated variances σδx_new2=(1/σδx2+1/σδx′2)−1 and σδy_new2=(1/σδy2+1/σδy′2)−1.


## 3.4. Fuse_IE_with_two_TOAs()

Here, we have two TOA measurements(x1,y1,τ1) and (x2,y2,τ2) along with one IE IE0=(δx^,δy^,T^,σδx2,σδy2,σT2) available. We first use the BLUE principle to
fuse the two TOAs to obtain initial estimates δx′^ and δy′^.
The result is then further fused with IE0. As in the previous section, by denoting T≈T^+εT,
for i=1,2,
we have zi=aiδx+biδy+εi+εT,
where ai=cosαi/c, bi=sinαi/c, and zi=τi−T^.By definingx=[z1z2]T,H=[a1b1a2b2],θ=[δxδy]T, and w=[ε1+εTε2+εT]T,
we have x=Hθ+w which immediately leads to the following BLUE
[3]: (8)[δx′^,δy′^]T=[HTC−1H]-1HTC−1x, with covariance matrix Cθ=[HTC−1H]-1, where, with E denoting expectation, (9)C=E(wwT)=(σ2+σT2σT2σT2σ2+σT2). That is, [σδx'2,σδy'2]=[Cθ(1,1),Cθ(2,2)].
This fusion function is now summarized as follows. Step 1, use (8) to obtain δx′^ and δy′^.
Step 2, fuse (δx′^,δy′^) and (δx^,δy^) using (7).


## 4. Simulation

In this section, we conduct simulation to verify
the proposed distributed source localization scheme. The tree routing protocol
and network setup process including parent-child relationship and address
assignment algorithms of the ZigBee [4] standard are followed in the simulation.100 ZigBee nodes are randomly deployed in a square region with size 500 m by
500 m. The root node (the coordinator in ZigBee’s terms) is acting
as the sink and is located at the centre of the lower edge of the region. The
nominal location of the sound source (target) (with speedc=344m/s) is the centre of the region, and it has an effective
range R=200m. When a node is less
than R meters away from the target,
it can make a TOA measurement. For each simulation scenario, the source takes a
small move in both x and y directions, that is, (δx,δy)=(0.5m,0.5m), and 1000 runs are conducted with independent and identically distributed zero-mean Gaussian
noise samples generated in each run. The estimation accuracy is measured by the
mean square error over all the runs: MSE=(1/1000)∑r=11000((x−x^r)2+(y−y^r)2),
where (xr,yr) is the estimate of the true source location (x,y) in the rth run.Figure3 shows the estimation errors with
varying noise variance. It can be seen that the proposed distributed scheme
works, and its performance attains that of the centralized best linear unbiased
estimator when the noise is reduced to a certain level.Figure 3
MSE of estimates.In summary, the benefit of the proposed
scheme is two-fold. First, it has improved flexibility and scalability over
centralized schemes since it shares the processing among multiple nodes and
does not pose any special requirements on the sink node. Second, it has the
potential to save energy/bandwidth consumption of the network due to reduced
radio transmissions.



---

*Source: 573129-2009-01-26.xml*