A Distributed Energy-Efficient Re-Clustering Solution for Wireless Sensor Networks

Clustering algorithms are widely used in Wireless Sensor Networks (WSNs), which however incurs significant energy consumption at Cluster Headers(CHs). Therefore, a re-clustering operation is typically used to balance the workload, where different CHs are selected and clusters are reorganized. However, a considerable number of control messages is initiated during this process which inevitably consumes on-board node energy. Hence, the question of how often the network should perform the re-clustering operation needs to be addressed. In this paper, a distributed re-clustering solution is proposed, which provides an energy-efficient re-clustering rate to conserve node energy while also equalizing the node energy consumption across the network. The proposed algorithm calculates the approximate amount of energy required to reorganize the clusters and to deliver the sensory data. By properly predicting the levels of the energy consumptions values, the appropriate frequency of performing the re-clustering operation can be determined, which reduces control message overhead. To the best of our knowledge, this is the first work that analytically analyzes the overhead in re-clustering a WSN, groups re-clustering rounds to reduce this overhead, and simultaneously equalizes node lifetimes. Performance results show that the proposed algorithm outperforms two other popular clustering algorithms in node energy conservation and node lifetime equalization.