A multi-objective evolutionary algorithm for the deployment and power assignment problem in wireless sensor networks

A Wireless Sensor Network (WSN) design often requires the decision of optimal locations (deployment) and transmit power levels (power assignment) of the sensors to be deployed in an area of interest. Few attempts have been made on optimizing both decision variables for maximizing the network coverage and lifetime objectives, even though, most of the latter studies consider the two objectives individually. This paper defines the multiobjective Deployment and Power Assignment Problem (DPAP). Using the Multi-Objective Evolutionary Algorithm based on Decomposition (MOEA/D), the DPAP is decomposed into a set of scalar subproblems that are classified based on their objective preference and tackled in parallel by using neighborhood information and problem-specific evolutionary operators, in a single run. The proposed operators adapt to the requirements and objective preferences of each subproblem dynamically during the evolution, resulting in significant improvements on the overall performance of MOEA/D. Simulation results have shown the superiority of the problem-specific MOEA/D against the NSGA-II in several network instances, providing a diverse set of high quality network designs to facilitate the decision maker's choice. Crown Copyright (C) 2009 Published by Elsevier B.V. All rights reserved.