Information Technology Reference
In-Depth Information
Table 4.3
Decentralized algorithms monitoring flock movement patterns
Algorithm description
DeSC peculiarities
Flock patterns are inferred from
maturing information tokens that
survive constant exchange and
validation, Fig.
4.3
Mobility diffusion, here handing
around information tokens, allows
for decentralized
FLAGS
Latency allows individuals to
accumulate spatial information,
constant rearrangement offers
opportunities for information
exchange and enrichment, Figs.
4.4
and
4.5
Latency reduces detection error, but
this effect wears off with long
latencies
DDIG
4.2.2 Mobile Agents Monitor Their Collective Movement
The second system architecture included in this chapter involves roaming sensor
nodes that aim to infer movement patterns in a collaborative manner without the
need for a centralized database. Both, Laube et al. (
P6
.
2008
;
P12
.
2011
) investigate
if and how movement pattern mining can be performed in a decentralized spatial
information system. Can mobile agents that sense their own location and the presence
of neighbors infer if they build the movement pattern flock? Again, an
-flock
is a form of collective movement and defined as set of
n
moving entities that stay
within a disk of radius
p
for
k
time steps.
All algorithms summarized in this section are based on the assumption that the
nodes move in an
unconstrained
space. Whereas Laube et al. (
P12
.
2011
) relies on
nodes that can record their own position as coordinates, Laube et al. (
P6
.
2008
) only
requires sets of detected neighbors. In both studies, positions and neighbors are sensed
in a quasi continuous manner, be it with a GPS receiver, any other localization tech-
nology. Irrespective of the localization and sensing capabilities, both studies adhere
to the
Lagrangian
perspective. The mobility mode is rather challenging since both the
sensing nodes and the investigated phenomena (here the flock patterns) potentially
move. The constant rearrangement of the network topology and with it all connectiv-
ity links requires alternative strategies to popular strategies in decentralized spatial
computing such as trees or any other precomputed and maintained data structure.
First, Laube et al. (
P6
.
2008
) illustrates how collaborating nodes can extend
their knowledge beyond their limited individual spatial perception area. In the
FLAGS
algorithm (
fl
ocking
a
mongst
g
eo
s
ensors), information tokens capturing a
list of candidate nodes forming a flock are exchanged between roaming sensor nodes
(Fig.
4.3
). At each time step, nodes in the flock validate if the flock persists, update
their token accordingly, and pass it on to their immediate neighbors. Since invalid
tokens are removed, tokens that persist for
k
time steps “flag” the presence of a flock
pattern. The constant process of exchanging and validating information allows indi-
vidual sensor nodes to learn from their neighbors about processes beyond their own
limited perception range. The algorithm separates knowledge from sensor nodes,
knowledge becomes mobile. Hence,
FLAGS
presents both a form of
mobility diffu-
sion
(Sect.
4.3.2.2
) and
separation
(Sect.
4.3.3.4
).
(
n
,
k
,
p
)
