Image Processing Reference
In-Depth Information
h
). Subtracting the
last equation
h
from all other equations decrements the number of equations and results in
A set of three or more of these equations builds a system of equations (
≤
j
≤
x
j
y
j
x
h
y
h
c
t
jh
t
ij
x
h
y
i
y
h
−
−
+
+
=
x
i
(
−
x
j
)+
(
−
y
j
)+
(
−
)
(.)
Equation.canberepresentedbythematrixform
A
x
=
b
and is solved by a minimum LS
A
T
b
. An extension of the basic algorithm is the iterative multilateration
(Figure .b), where every sensor node with an estimate starts to act as a beacon. hat means, every
sensor node requests positions from its direct neighbors, which are then included in a refinement
process. his method strongly depends on the precision of the first estimates.
If node density is low and some nodes cannot reach at least three beacons, normally the mul-
tilateration fails. For this case, collaborative multilateration was proposed, which extends the one
hop lateration to multiple hops by considering normal sensor nodes (Figure .c).
A
T
A
)
−
estimator
x
=(
6.3.6.2 Distributed Least Squares
In the following, we explain the distributed least squares (DLS) algorithm. DLS features high pre-
cision at minimal power consumption at sensor nodes and was developed by Reichenbach et al.
[RBTB,Rei]. DLS starts with the creation of an over determined system of non linear Euclidean
distances of the form
r
i
(
x
−
x
i
)
+(
y
−
y
i
)
=
with
i
=
,,...,
m
(where
m
is the number of
beacons,
S
is the position of beacon
i
and
r
i
is the distance
between them). This system of equations is linearized with the method described in [MH]. This
leads to the form
A
x
(
x
;
y
)
is the required position,
B
i
(
x
i
;
y
i
)
b
,where
A
is the coefficient matrix,
b
is the right side vector, and
x
is the
solution vector. By applying the LS method, we obtain the normal equation
x
=
A
T
b
.
he matrices in this equation have two important advantages. First, all elements in the coefficient
matrix
A
are generated by beacon positions
B
−
A
T
A
=(
)
only.Byassumingthat,wecan
establish communication links between all sensor nodes and all beacons (e.g., by multihop tech-
niques), then matrix
A
isthesameoneverysensornode.Second,thevector
b
contains the distances
between sensor nodes and beacons
r
(
x
;
y
)⋯
B
m
(
x
m
;
y
m
)
r
m
that must be estimated at every sensor node independently.
Given these facts, the normal equation is split into two parts—a more complex part, the precalcula-
tion:
A
p
⋯
−
A
T
A
T
and a simple part:
A
p
=
(
)
b
, which is further called the postcalculation.
The precalculation is executed on a powerful base station, which additionally avoids high redun-
dancy, because this precalculation would normally be executed on all sensor nodes separately. But
it is very important to emphasize that the precalculation is identical on every sensor node. Thus, it
is calculated only once, conserving expensive energy resources. The simple postcalculation is exe-
cuted at every sensor node with its individual distance measurements to all beacons. his approach
complies with two important design strategies for algorithms in large sensor networks—a resource-
aware and distributed localization procedure. Finally, this can be achieved with less communication
overhead required for other exact algorithms.
At this point, we briefly describe the algorithm process. DLS is divided into three phases, which
are shown in Figure .. In phase , all beacons send their position
B
i
⋅
A
⋅
⋅
hop-by-hop over their
beacon neighbors to the base station (Figure .a). In phase , the base station starts generating the
initial matrices and computes
A
p
(Figure .b). he result is sent over beacons to all sensor nodes,
which in phase estimate their position after measuring the distances to all beacons and executing
thepostcalculation(Figure.c).
(
x
i
;
y
i
)
6.3.6.3 Convex Position Estimation
The “convex position estimation” (CPE) of Doherty et al. estimates a position by using geometric con-
straints between nodes [DPG]. In more detail, a sensor network consists of nodes (positions) and
edges (communication links). The existence of some beacons is also assumed. Radial and angular
