Digital Signal Processing Reference
In-Depth Information
Fig. 4.5
Black nodes
(such
as
f
1
and
f
2
) correspond to
interior nodes (i.e., nodes
inside the contour). The
straight lines
trace the regions
which are closest to a certain
interior node (i.e., the
Voronoi
regions). The new proposed
backoff scheme ensures that
nodes (such as
A
and
B
)
which are closer to the
interior contour nodes are
updated first before they
propagate this contour
distance information to the
other nodes. This propagation
can be performed at a cost of
almost
N
transmissions, the
total number of nodes
update its neighbors more than once. This is illustrated for node
C
in Fig.
4.5
. Node
C
receives information of node
B
only before time 2
CW
, and hence thinks its clos-
est point on the contour is
f
2
. Following the algorithm,
C
will have chosen a ran-
dom backoff in the range
to start updating its
neighbors. If node
C
does not receive correct information before that random time,
wrong information will be propagated and node
C
will have to update his neigh-
bors a second time once information about the correct footpoint
f
1
is obtained. In
practice, with this scheme, the number of update events is experienced to be very
close to the number of nodes (neglecting collisions) as also illustrated in Table
4.1
.
The contour spreading as function of time is illustrated in Fig.
4.6
for a simulated
scenario.
It is important to see that the algorithm will converge for arbitrary complex con-
tour shapes, such as the one shown in Fig.
4.3
which consists of multiple parts.
[
(CW
−
B
B
)...(CW
−
B
B
)
+
CW
[
Fig. 4.6
Distributed distance-to-contour flooding shown at three intermediate timesteps during the
algorithm for a simulated scenario
