Clustering is one of the basic approaches for designing energy-efficient and scalable distributed sensor networks. HEED is a well known energy efficient clustering protocol. In this protocol, the message overhead is low and cluster heads are distributed fairly across the network. Our distributed clustering protocol, HEED*, improves HEED protocol to achieve energy efficiency with three techniques: 1) local clustering, i.e., whenever a cluster head consumes a prespecified part of its energy, it only informs its member nodes to hold cluster head elections for the upcoming round. Therefore, clustering is performed locally (in contrast to performing it globally). 2) Reducing the number of message exchanges per iteration through eliminating unnecessary cluster head messages. 3) In HEED*, a node with higher amount of remaining energy is considered more eligible candidate for election as a cluster head. Besides, each node computes a communication cost, and a regular (non cluster head) node elects the cluster head with the least communication cost to connect to. Simulation results show that the protocol outperforms HEED protocol in terms of network lifetime

Keywords