S. Funke, N. Milosavljevic, Network Sketching or: "How Much Geometry Hides in Connectivity? -- Part II", Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA) 2007.

Abstract:

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 a predecessor paper) 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.

Bibtex: 

@inproceedings{fm-nshmghicp2-07,
   author = {S. Funke and N. Milosavljevi\'c},
   title = {Network Sketching or: "{H}ow Much Geometry Hides in Connectivity? -- Part {II}"},
   booktitle = {Proc. of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA) 2007.},
   year = {2007}
}