Infrastructure-Establishment from Scratch in Wireless Sensor Networks

Stefan Funke, Nikola Milosavljevic

We present a distributed, localized and integrated approach for establishing both low-level (i.e. exploration of $1$-hop neighbors, interference avoidance) and high-level (a subgraph of the unit-disk graph) infrastructure in wireless sensor networks. More concretely, our proposed scheme constructs a subgraph of the unit-disk graph which is connected, planar and has power stretch factor of $1$ (the well-known Gabriel graph intersected with the unit disk-graph) and -- most importantly -- deals \emph{explicitly} with the problem of interference between nearby stations. Due to our interleaved approach of constructing low- and high-level infrastructure simultaneously, this results in considerable improvements in running time when applied in dense wireless networks.

To substantiate the advantages of our approach, we introduce a novel distribution model inspired by actual sensing applications and analyze our new approach in that framework.

Proc. of 1st IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS) 2005, Marina del Rey