Energy Aware Distributed Clustering in Two-Tiered Sensor Networks

Two-tiered sensor networks, where higher-powered relay nodes are used as cluster heads, have been proposed recently for designing sensor networks. Assigning sensor nodes to clusters, in an energy efficient way, is known to improve the lifetime of such networks. In this paper we have proposed an efficient distributed algorithm for assigning sensor nodes to clusters in two-tiered networks, using both single-hop and multi- hop routing schemes. Our distributed clustering strategy allocates sensor nodes to clusters, based on limited local information only. However, the solutions generated are shown to be comparable to optimal solutions obtained using an ILP formulation. We have also compared our approach to a number of existing heuristics recently proposed in the literature and have shown, through simulations, that our approach consistently outperforms current heuristics. In summary, the quality of the solutions obtained using our approach is comparable to those obtained using an ILP formulation, but the solutions can be generated very quickly, making it suitable for practical-sized networks with hundreds of sensor nodes.