Digital Signal Processing Reference
In-Depth Information
The algorithm proceeds iteratively by taking the first node
N
i
from the queue
(i.e., the one with the smallest
d
i
), and by updating its neighboring nodes
N
j
(those
within a communication distance
h
to
N
i
). The footpoint
f
i
stored with
N
i
is used
for doing this. If
x
j
<d
j
, i.e., if
N
j
is closer to
N
i
's footpoint than it is
to its previously computed own footpoint, it is needed to update
N
j
's distance and
footpoint information (
d
j
f
i
−
f
i
) and add
N
j
to the priority
queue. This process is repeated until the queue becomes empty.
Due to the use of a priority queue this algorithm requires a central base station.
However, it is possible to approximate this algorithm and make it fully distributed
by cleverly modifying the medium access protocol as will be discussed below.
←
f
i
−
x
j
and
f
j
←
4.3.3.2 Distributed Distance-to-Contour Flooding
When implementing the fast marching in a network, it is required that each node up-
dates its neighbors by sending its footpoint information. We note that nodes that are
inside the contour are footpoint to themselves, and hence have perfect information
at the start of the algorithm. Inspired by the optimal centralized implementation of
the algorithm, one can see that it is optimal to have nodes with a smaller distance to
the contour update their neighbors first. In practical networks, this can be achieved
by giving those nodes a higher probability
p
send
to gain access to the channel. While
nodes are waiting to access the channel, they can accumulate neighbor update events
and only propagate the best footpoint found so far. This probability
p
send
is typically
a function of a backoff timer in practical protocols such as 802.11, or alternatively,
it is a function of the scheduling algorithm carried out at the AP.
The simulations are done with a random backoff timer that determines when
nodes update their neighbors. Assume that CW is the initial backoff range that re-
sults in a low number of packet collisions that can be neglected. A backoff timer
can be used to determine when nodes can access the channel, by choosing a random
number in the backoff range. Since distance-to-contour information is spreading in
the network away from the contour, one wants to make sure that nodes only send
when all nodes in their neighborhood that are closer to the contour have sent first.
As illustrated in Fig.
4.5
, one can be sure that all black footpoints
f
i
with backoff
in the range
will have sent after time
CW
, if collisions requiring retrans-
missions are neglected for the ease of reasoning. As a result, a node
A
that receives
an update from a footpoint
f
1
(with backoff
B
f
1
[
0
...CW
[
[
[
in range
0
...CW
) will have to
wait an additional
CW
B
f
1
after reception of
f
1
's update. This can be achieved if
A
will select a random number in the range
−
.
Clearly, as indicated in Fig.
4.5
, the updating speed of the network will be approxi-
mately
1
the one-hop communication range
h
, each
CW
timeslots.
A distributed implementation of the scheme potentially results in a node spread-
ing information before it obtained its closest footpoint. Such a node will have to
[
(CW
−
B
f
1
)...(CW
−
B
f
1
)
+
CW
[
1
Due to sampling irregularities, as illustrated in Fig.
4.5
also, the contours do not spread exactly
over a distance
h
each step.
