Information Technology Reference
In-Depth Information
y
x
1
2
1
b
d
2
3
a
b
b
2
e
1
a
d
2
e
1
a
p
d
e
t
6
t
7
t
5
T
Fig. 4.3
Maturing knowledge tokens detect a
(
n
=
4
,
k
=
3
,
p
)
-flock locally. At
t
5
sensor node
e
counts the required 4 neighbors, creates a token
(
{
a
,
b
,
d
,
e
}
,
1
)
that is transmitted to all its
neighbors within communication range
c
(little numbered flags). At
t
6
, after having moved and
potentially rearranged, all sensor nodes check their tokens. This time only sensor node
d
counts
enough neighbors and ages his token to
. All other sensor nodes drop their token.
Sensor node
d
, however, forwards its aged token to all its neighbors. Finally, at
t
7
,again
e
counts
enough neighbors, its token
(
{
a
,
b
,
d
,
e
}
,
2
)
3, and flags a “found
pattern”-message (
crown
) (With kind permission from Springer Science+Business Media: Cova,
T. J., Beard, K., Good-child, M.F., & Frank, A.U. (Eds.). (2008). Geographic Information Science.
Lecture Notes in Computer Science, 5266
, ISBN 978-3-540-87472-0; Laube, P., Duckham, M., &
Wolle, T. Decentralised movement pattern detection amongst mobil geosensor nodes, 199-216,
Fig. 2.)
(
{
a
,
b
,
d
,
e
}
,
3
)
reaches the mature age
k
=
A similar form of mobility diffusion builds the core of the
DDIG
algorithm
(
d
eferred
d
ecentralized
i
nformation
g
razing) presented in Laube et al. (
P12
.
2011
).
Here, roaming nodes exchange local histories of their recent positions whenever they
get into each other's communication range (Fig.
4.4
). Hence, through their mobility
and thereby constantly changing communication partners, they build up local spa-
tial knowledge that reaches beyond their individual spatial perception range (labeled
“information grazing”). In a subsequent step, which is deferred by the time the infor-
mation grazing requires, the local memory serves as a local knowledge base for the
actual detection of the flock patterns (Fig.
4.5
). To this end, any flocking algorithm
could be used, in Laube et al. (
P12
.
2011
) a simple heuristic was used based on an
outlier elimination that suited the memory data structure.
Rather than investigating computational efficiency, both articles base their eval-
the number of detectable patterns is known. To this end simulated and real obser-
vation data was used. Then the decentralized algorithms were confronted with a set
of experiments that systematically make their task harder, for instance, by reduc-
ing the communication radius (
FLAGS
and
DDIG
) or shortening the delay (
DDIG
).
The error analysis then measured
error of omission
(“missed patterns”) and
error of
commission
(“false positives”).
Both articles made clear that decentralized movement pattern mining is indeed
possible, when imperfect, approximate, or delayed solutions are acceptable. They
also showed that in the tested scenarios, node mobility was useful for succeeding
