Network Sketching or:``How Much Geometry Hides in Connectivity?
-- Part II''
Stefan Funke, Nikola Milosavljevic
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 show that using a very simple distributed
algorithm we can identify a large, provably planar subgraph of the
communication graph that faithfully reflects the topology of the
network. This planar subgraph can then be embedded using a simple
distributed rubber-banding procedure, finally obtaining \emph{virtual
coordinates} for the nodes of the subgraph which can be instrumented for
various protocols based on geographic location information. That is,
there is enough geometry information hidden in the connectivity structure
not only to identify topological features like network holes (as it was
also exhibited in the predecessor paper \cite{SoCG06}) but even enough
information to compute a \emph{sketch} of the network layout. Our
simulation results indicate that the algorithm works very well even for
very sparse network deployments and produces network sketches that come
close to the original layout.
PDF