Studying the multiobjective variable neighbourhood search algorithm when solving the relay node placement problem in Wireless Sensor Networks

Nowadays, wireless sensor networks (WSNs) are considered in many fields of application. In this paper, we study how to efficiently deploy relay nodes into previously established static WSNs, with the purpose of optimising two relevant factors for the industry: average energy consumption of the sensors and average sensitivity area provided by the network. This is the so-called relay node placement problem, which is a known NP-hard optimisation problem in the literature. With the purpose of tackling this multiobjective (MO) optimisation problem, we consider two different approaches of the trajectory algorithm MO-VNS, assuming a wide range of stop conditions. Two additional standard genetic algorithms are included in this study, NSGA-II and SPEA2, which belong to evolutionary algorithms. The aim is to analyse the behaviour of MO-VNS compared to traditional methodologies. To this end, the four metaheuristics are applied to solve a freely available data set. The results obtained are analysed following a widely accepted statistical methodology and considering three MO quality metrics: hypervolume, set coverage, and attainment surface. After studying the results, we conclude that MO-VNS provides better performance than the standard algorithms NSGA-II and SPEA2. Moreover, we verify that the addition of relay nodes is a good way to optimise traditional WSNs.