Image Processing Reference
In-Depth Information
9.5.2 Star Algorithm
The Ring Algorithm is completely decentralized (Figure .). However, it will not converge to a
solutionifthefeasiblesets
i
,
k
do not have an intersection (which can happen due to measurement
noise) or one or more sensors in the network are faulty. The Star Algorithm is an alternative dis-
tributed algorithm for fusing individual sensors' data. It combines successive projections onto
Q
Q
i
,
k
with a kind of averaging operation to generate a sequence of solutions
P
(
m
)
.hissequencewill
eventually converge to a solution
P
∗
∈ ⋂
i
,
k
if one exists. The Star Algorithm is fully par-
allel and hence much faster than the Ring Algorithm. It provides some degree of robustness to
individual node's failure as well. However, it includes a centralized step, which needs to be accom-
modated for when the system's network protocol is being designed. Steps of the Star Algorithm
are summarized in the text box below. A graphical representation of this algorithm is shown in
Figure ..
Q
i
,
k
Star Algorithm
e
j
ω
Input
: A distance function
D
j
(
P
,
P
)
, an initial power spectrum
P
(
)
, the
e
j
ω
squared sensor frequency responses
G
i
(
)
, and the autocorrelation estimates
R
v
i
.
Output
: A power spectrum
P
(
k
)
e
j
ω
∗
(
)
.
Procedure
:
and
P
(
)
1. Let
m
=
=
P
.
2. Send
P
(
)
to all sensor nodes.
At the
i
th sensor:
m
and define
P
(
n
)
P
(
m
)
.
(
i
)
Let
n
=
=
Calculate
P
k
(
ii
)
=
P
[
for all
k
.
P
(
n
)
↦Q
i
,
k
;
D
j
]
Calculate
P
(
P
,
P
k
n
+
)
(
iii
)
=
arg min
P
∑
k
D
(
)
.
P
(
,
P
(
n
+
)
n
)
(
iv
)
If
D
(
)>
є
go to item
(
ii
)
and repeat. Otherwise, define
P
(
m
)
P
(
n
+
)
and send it to the central unit.
=
i
P
(
m
)
P
(
m
+
)
2. Receive
from all sensor and calculate
=
arg min
P
i
P
,
P
(
m
)
i
D
(
)
.
∑
i
P
(
m
+
)
,
P
(
m
)
3. If
D
(
)>
є
, go to step 2 and repeat. Otherwise stop and
output
P
∗
=
P
(
m
+
)
.
Example .
Considerasimple-sensornetworksimilartotheoneshowninFigure..Assumethatthedown-
sampling ratio in each Mote is equal to . .Thus, again, N
=
N
=
N
=
N
=
. Assume, further, that
the transfer functions H
(
z
)
to H
(
z
)
which relate the Motes' front-end output v
i
(
n
)
to the original
source signal x
(
n
)
are the same as those introduced in Example .. We simulated the Star Algorithm
with L
and the Euclidean metric D
as the distance function to estimate the input signal's spectrum.
The results are shown in (Figure .). Like the Ring Algorithm, the Star Algorithm also converges to a
solution, which is almost identical to the actual input spectrum in less than rounds.
=
♢
