非表示:
キーワード:
-
要旨:
Wireless sensor networks typically consist of small, very simple network nodes
without any positioning device like GPS.
After an initialization phase, the nodes know with whom they can talk directly,
but have no idea about their relative geographic locations.
We examine how much geometry information is nevertheless hidden in the
communication graph of the network:
Assuming that the connectivity is determined by the well-known unit-disk graph
model, we prove that using an extremely simple linear-time algorithm
one can identify nodes on the boundaries of holes of the network. That is,
there is enough geometry information hidden in the connectivity structure
to identify topological features -- in our example the holes in the network.
While the theoretical analysis turns out to be quite conservative, an actual
implementation shows that the algorithm works well under less stringent
conditions.
