Adaptive Decentralized Re-Clustering for Wireless Sensor Networks

This paper discusses a dynamic decentralized algorithm for re-clustering the sensors of an ad hoc sensor network. Each sensor uses a random waiting timer and local criteria to determine whether to form a new cluster or to join a current cluster. A localized clusterhead reselection process is triggered when the energy reserves of the clusterhead falls below a threshold. The algorithm operates without a centralized controller, it operates asynchronously, and does not require that the location of the sensors be known a priori. An analysis of cluster lifetime, the energy requirements of the algorithm, and a simplified model are used to study the behaviors of the proposed algorithm. The performance of the algorithm is described analytically and via simulation.