Image Processing Reference
In-Depth Information
A
2
A
3
A
2
A
1
A
1
A
1
B
2
(
x
;
y
)
B
2
(
x
;
y
)
r
S
4
A
S
A
3
d
12
B
1
(
x
;
y
)
B
1
(
x
;
y
)
S
3
(
x
;
y
)
B
3
(
x
;
y
)
B
1
(
x
;
y
)
S
2
(
x
;
y
)
A
S
,hull
A
S
,hull
A
S
B
3
(
x
;
y
)
(a)
(b)
(c)
FIGURE .
(a) Bounding box of
B
(
x
;
y
)
, (b) bounding box
A
S
of sensor node
S
(
x
;
y
)(
S
∈
A
S
,
hull
)
,
and (c) bounding box
A
S
. (From Blumenthal, J., Resource aware and decentral localization of au-
tonomous sensor nodes in sensor networks, PhD thesis, University of Rostock, Rostock, Germany, , submitted.
With permission.)
(
S
∉
A
S
,
hull
)
6.3.6 Optimization Methods
6.3.6.1 Fine-Grained Localization
Oneofthemostcitedpreciselocalizationalgorithmsinliteratureisprobablythe“ine-grained
localization” (FGL) by Savvides et al. [SHS]. The name origins by achieving a fine-grained reso-
lution of position estimations. FGL demands minimal three beacon positions and can be executed
on every sensor node, respectively completely distributed. The core of FGL is the least squares
(LS) method. With more beacon positions than needed, the precision of the algorithm significantly
increases. Beside the basic atomic multilateration, the iterative and the collaborative multilateration
were presented (Figure .).
In atomic multilateration, every sensor node measures distances to all beacons in range. Both the
Euclidean distances and the beacon's positions lead to the equation for the distance error:
√
f
i
(
x
i
,
y
i
,
c
)=
c
∆
t
ij
−
(
x
j
−
x
i
)
+(
y
j
−
y
i
)
(.)
In Equation .,
c
∆
t
represents a distance which may be calculated by measuring the time dif-
ference ∆
t
multiplied with the propagation speed
c
of the signal. Savvides presented specialized
sensor nodes (Medusa) transmitting ultrasound signals with a propagation speed of
c
to determine
the time ∆
t
a signal needs from sensor node
i
to beacon
j
. Rearranging, squaring, and linearizing
of Equation . forms Equation ..
x
j
y
j
x
i
y
i
c
∆
t
ij
x
i
y
i
−
−
=
+
+
(−
x
j
)+
(−
y
j
)−
(.)
B
1
B
1
B
1
B
2
B
2
B
2
d
1
d
2
d
1
d
2
d
1
d
2
B
5
S
1
S
1
S
1
S
2
S
2
d
4
d
3
d
4
d
3
d
4
d
3
B
4
B
3
B
4
B
3
B
4
B
3
(a)
(b)
(c)
FIGURE .
(a) Atomic, (b) iterative, and (c) collaborative multilateration.
