Abstract:

Extracting planar graph from network topologies is of great importance for efficient protocol design in wireless sensor networks. It has become the foundation of many important protocols and applications, such as geographic routing including GPSR, GOAFR, etc. Previous techniques of planar topology extraction are often based on the assumption of accurate node location measurements. It is highly desirable to relax assumptions and extract a planar topology in a locationfree and distributed manner. We present a novel method to construct a planar structure for wireless sensor networks in a distributed manner, merely using connectivity information. Our method can extract a provably planar graph from communication graphs. The extensive simulations also show the effectiveness of this design in randomly generated networks.

Key words: wireless sensor networks;planarization;topology;connectivity