Multi-objective energy-efficient dense deployment in Wireless Sensor Networks using a hybrid problem-specific MOEA/D

An energy-efficient Wireless Sensor Network (WSN) design often requires the decision of optimal locations (deployment) and power assignments of the sensors to be densely deployed in an area of interest. In the literature, no attempts have been made on optimizing both decision variables for maximizing the network coverage and lifetime objectives, while maintaining the connectivity constraint, at the same time. In this paper, the Dense Deployment and Power Assignment Problem (d-DPAP) in Wireless Sensor Networks (WSNs) is defined, and a Multi-objective Evolutionary Algorithm based on Decomposition (MOEA/D) hybridized with a problem-specific Generalized Subproblem-dependent Heuristic (GSH), is proposed. In our method, the d-DPAP is decomposed into a number of scalar subproblems. The subproblems are optimized in parallel, by using neighbourhood information and problem-specific knowledge. The proposed GSH probabilistically alternates between six d-DPAP specific strategies, which are designed based on various WSN concepts and according to the subproblems objective preferences. Simulation results have shown that the proposed hybrid problem-specific MOEA/D performs better than the general-purpose MOEA/D and NSGA-II in several WSN instances, providing a diverse set of high-quality near-optimal network designs to facilitate the decision making process. The behavior of the MOEA/D-GSH in the objective space is also discussed. (C) 2011 Elsevier B.V. All rights reserved.