With the rapid rise in popularity, wireless sensor networks have become an integral part of a large spectrum of applications. As the networks continue to grow in size, the need for Energy Conservation, Fairness, Capacity, Reliability and Fault Tolerance are increased. Overlay creation is a standard technique to achieve the above mentioned goals.
In this work we present two distributed algorithms, T-Hex and T-Tri, to create a regular overlay topology in randomly deployed wireless sensor networks. The algorithms implement localized self-healing to prevent frequent reconfigurations and elongate network lifetime. T-Hex creates a regular hexagonal topology in a randomly deployed WSN by finding six neighbors that best fit hexagonal shape. T-Tri extends the work of T-Hex and creates a triangular topology by distributively eliminating nodes from the existing hexagons. We evaluate T-Hex and T-Tri by simulating them on a densely deployed WSN, and demonstrate their overlay formation and self-healing capabilities. We also present a solution to the Energy hole problem. We create a distributed algorithm to form hierarchical overlay topology in wireless sensor networks. We compare the non-hierarchical networks with hierarchical networks and show the increase in overall network lifetime. In the last part of this work, we implement T-Hex on a small network of 22 nodes and demonstrate the hexagon creation process for using TelosB sensor motes.