Iterated Local Search Algorithm for Clustering Wireless Sensor Networks

In this paper, a new clustering protocol employing an iterated local search (ILS) to solve cluster head selection problem is proposed. ILS uses a perturbation operator to change an initial random solution to produce a new point in the vicinity of the solution. Using a combination operator, this new point is mated with the random solution producing a new solution. A move from the current solution to the new solution is considered acceptable only for higher fitness value. If a move is rejected after a predetermined search length, the change rate of the current solution is increased in order to explore a wider search space for quality solutions. In each round, this search process continues until good solution that ensures balanced energy consumption is obtained for the network. Furthermore, we propose a sleep scheduling scheme inspired by the Boltzmann Selection process in genetic algorithms. This mechanism stochastically considers coverage effect in the selection of nodes that are required to go into sleep mode in order to conserve energy of sensor nodes. The proposed mechanism of inactive node and cluster head selection protocols are performed sequentially at every round and they form part of the main algorithm proposed, namely the Dynamic Local Search-Based Algorithm for Clustering Hierarchy (DLSACH). The ultimate goal of the DLSACH protocol is to extends the network lifetime of wireless sensor networks by reducing and balancing the energy consumption among sensor nodes during communication processes. Our protocol shows an improved performance compared to state-of-the-art protocols such as LEACH, TCAC and SEECH in terms of improved network lifetime for wireless sensor networks deployment.