Nature-inspired relay node placement heuristics for wireless sensor networks

Abstract

Wireless Sensor Network (WSN) comprises a large number of spatially distributed sensor devices that can retrieve valuable information via low-cost, low-powered, tiny sensors, and send the data to a sink through its wireless communication units. In order to prolong network lifetime at minimum cost, a small number of powerful relay nodes can be deployed in the sensing area. The connectivity between the sensor nodes and the base stations is one of the most crucial design considerations for WSNs. In this paper, mixed-integer linear programming model of the constrained relay node placement problem is defined. Since the problem has NP-hard nature, novel nature-inspired meta-heuristic methods (Genetic Algorithm (GA) and Simulated Annealing (SA)) are presented to find the number and position of the relay nodes in a heterogeneous WSN. The algorithms have new problem specific representation and operators. The results of proposed GA is compared with exact, SA and minimum spanning tree solutions. Experimental analysis has shown that presented GA and SA approaches can find a near-optimal or efficient solution in a reasonable computation time.