A Low-Maintenance Energy-Aware Clustering Algorithm for Wireless Ad-hoc Networks

Clustering has often been used to impose structure in wireless ad hoc networks. In this work, we propose a modified lowest-ID clustering algorithm that tries to increase the stability of the created clusters. A stability factor is associated with nodes to improve the stability of clusters produced. The stability parameter is a measure of the time that a cluster head starts its leadership role. In our algorithm, nodes use periodic beacons as the only means of communications with its neighbors. The stability parameter is defined in one of the fields of the beacons. Nodes contend to become cluster head; the node with a lower ID and larger stability factor wins the contention. Since cluster heads have extra functionality and therefore consume more energy compared to the other nodes in the network, we propose an energy efficient load balancing mechanism on the created clusters based on their energy levels. To balance the energy consumption among the nodes, a cluster head retires after some time and hands over its role to another neighbor cluster head with higher energy levels. This is useful for prolonging the network lifetime. We demonstrate using simulations that our algorithm improves the average residual energy of the network as well as the stability of the clusters produced