Energy Balanced Two-level Clustering for Large-scale Wireless Sensor Networks based on the Gravitational Search Algorithm

Organizing sensor nodes in clusters is an effective method for energy preservation in a Wireless Sensor Network (WSN). Throughout this research work we present a novel hybrid clustering scheme that combines a typical gradient clustering protocol with an evolutionary optimization method that is mainly based on the Gravitational Search Algorithm (GSA). The proposed scheme aims at improved performance over large in size networks, where classical schemes in most cases lead to non-efficient solutions. It first creates suitably balanced multihop clusters, in which the sensors energy gets larger as coming closer to the cluster head (CH). In the next phase of the proposed scheme a suitable protocol based on the GSA runs to associate sets of cluster heads to specific gateway nodes for the eventual relaying of data to the base station (BS). The fitness function was appropriately chosen considering both the distance from the cluster heads to the gateway nodes and the remaining energy of the gateway nodes, and it was further optimized in order to gain more accurate results for large instances. Extended experimental measurements demonstrate the efficiency and scalability of the presented approach over very large WSNs, as well as its superiority over other known clustering approaches presented in the literature.