Elsevier

Applied Soft Computing

Volume 68, July 2018, Pages 268-282
Applied Soft Computing

Hybrid multi-objective evolutionary algorithms based on decomposition for wireless sensor network coverage optimization

https://doi.org/10.1016/j.asoc.2018.03.053Get rights and content

Highlights

  • This paper models the coverage control optimization problem in WSN as a multi-objective optimization problem considering multiple objectives.

  • A hybrid reproduction operator based on Genetic Algorithm (GA) and Differential Evolution (DE) has been proposed to diversify the search.

  • An discrete binary particle swarm optimization method has been designed as the enhancement strategy to obtain a better Pareto solution set.

  • Large amount of experiments have been carried out to demonstrate the effectiveness of our proposed algorithms.

Abstract

In Wireless Sensor Networks (WSN), maintaining a high coverage and extending the network lifetime are two conflicting crucial issues considered by real world service providers. In this paper, we consider the coverage optimization problem in WSN with three objectives to strike the balance between network lifetime and coverage. These include minimizing the energy consumption, maximizing the coverage rate and maximizing the equilibrium of energy consumption. Two improved hybrid multi-objective evolutionary algorithms, namely Hybrid-MOEA/D-I and Hybrid-MOEA/D-II, have been proposed. Based on the well-known multi-objective evolutionary algorithm based on decomposition (MOEA/D), Hybrid-MOEA/D-I hybrids a genetic algorithm and a differential evolutionary algorithm to effectively optimize sub-problems of the multi-objective optimization problem in WSN. By integrating a discrete particle swarm algorithm, we further enhance solutions generated by Hybrid-MOEA/D-I in a new Hybrid-MOEA/D-II algorithm. Simulation results show that the proposed Hybrid-MOEA/D-I and Hybrid-MOEA/D-II algorithms have a significant better performance compared with existing algorithms in the literature in terms of all the objectives concerned.

Introduction

Wireless Sensor Networks (WSNs) are self-organized networks consisting of sensor nodes capable of sensing, processing and wireless communication. Coverage control is a crucial issue in WSN, which mainly concerns how well a sensor network monitors a field with proper node deployment [[1], [2], [3]]. The energy of sensor nodes, the network communication bandwidth and the computing ability are generally limited resources, and thus the coverage sustainability in WSNs cannot always be guaranteed. How to balance the network energy consumption to prolong network lifetime while maintaining a high coverage rate is an important issue, which can be modeled as a multi-objective optimization problem (MOP) [[4], [5]].

The goal to solve MOPs with two or more conflicting optimization objectives is to calculate an approximation of the Pareto Front. MOPs should be provided with multiple non dominated solutions concerning different objectives, which are difficult to be optimized if been converted into a single combined objective. Kulkarni et al. [6] used computational intelligence and evolutionary algorithms to solve MOPs of coverage control in WSN in complex and dynamic environments. Ozturk et al. [7] obtained better dynamic deployments for WSN by using an artificial bee colony algorithm. Kulkarni et al. [8] applied particle swarm optimization (PSO) to address issues such as optimal deployment, node localization, clustering, and data aggregation in WSN. It is shown that PSO is a simple, effective and efficient algorithm. Özdemir et al. [9] modelled the WSN coverage control problem as a MOP problem with two objectives: the coverage rate and the network lifetime. The multi-objective problem is then converted into a series of single objective sub-problems, each solved by a genetic algorithm. Experimental results showed that the proposed MOEA/D algorithm outperformed an improved non-dominated sorting genetic algorithm (NSGA-II) [10]. Shen et al. [11] proposed a MOEA/D-PSO algorithm by considering two optimization objectives including coverage rate and network lifetime, and applied a particle swarm optimization algorithm in MOEA/D. Since the balance of energy consumption has a great impact on the entire network, the energy equilibrium [12] is thus added as another objective in this research.

Hybrid algorithms and improved particle swarm optimization algorithms have been well applied in other fields. Xu et al. [13] proposed a new hybrid evolutionary algorithm to solve multi-objective multicast routing problems in telecommunication networks. The algorithm combines simulated annealing based strategies and a genetic local search to effectively find more non-dominated solutions. Experimental results demonstrated that both the simulated annealing based strategies and the genetic local search can efficiently identify high quality non-dominated solution sets for the problems and outperform other conventional multi-objective evolutionary algorithms. In a novel PSO algorithm based on the jumping PSO (JPSO) algorithm developed by Xu et al. [14], a path replacement operator has been used in particle moves to improve the positions of the particles with regard to the structure of the routing tree. The experimental results demonstrated the superior performance of the proposed JPSO algorithm over a number of other state-of-the-art approaches.

Based on the above analysis, this paper considers the multi-objective coverage control optimization problem in WSN with three objectives, including the energy consumption, the coverage rate and the equilibrium of energy consumption. We propose two improved multi-objective algorithms, namely Hybrid-MOEA/D-I and Hybrid-MOEA/D-II. In order to diversify the search, two reproduction operators based on Genetic Algorithm (GA) and Differential Evolution (DE) have been hybridized in Hybrid-MOEA/D-I to obtain a better Pareto solution set. A weight is also set for each objective to guide the search direction. To further enhance the search ability of Hybrid-MOEA/D-I and preserve high quality individuals in each generation, a new Hybrid-MOEA/D-II algorithm is devised to integrate an improved discrete binary particle swarm optimization algorithm in [15] as the enhancement strategy to obtain a better Pareto solution set. An extensive set of experiments have been carried out to systematically investigate the performance of our proposed algorithms.

The remainder of the paper is organized as follows. Section 2 gives the definition of the multi-objective coverage control optimization problem. Section 3 provides the summary of the related works of the multi-objective coverage optimization problem in WSN. We describe our proposed Hybrid-MOEA/D-I and Hybrid-MOEA/D-II algorithms in Section 4. Experimental results are reported in Section 5. The conclusion and some future work are given in Section 6.

Section snippets

The multi-objective coverage optimization (MCO) problem

In WSN, coverage problems can be divided into face coverage, line coverage and target point coverage. In this paper, we use the target point coverage, refers to the target point at any time by one or more than one sensor node coverage. Assume the target field D is a two-dimensional square, the targeting point ST = {t1, t2,…, tM}, tj = (xj, yj) are randomly distributed in D, M is the number of target points, j∈[1,…, M], xj and yj are the coordinates of each target point. A set of sensor nodes S

Related works for the multi-objective coverage optimization problem

Zhang et al. [38] proposed the MOEA/D algorithm by decomposing a MOP into a number of single objective optimization problems (i.e. sub-problems), and optimizing them simultaneously. By using the optimization information of the neighboring sub-problem, the sub-problem will be optimized. The Tchebycheff Approach is used as a decomposition method in MOEA/D due to its ability to transfer the objective function of the i-th sub-problem using non-convex Pareto optimal front in Eq. (17) as follows:mingt

The proposed hybrid-MOEA/D algorithms

In this paper, we proposed a hybrid MOEA/D algorithm based on the work in [9], namely Hybrid-MOEA/D-I, by combining Genetic Algorithm (GA) and Differential Evolution (DE) as the mixed reproduction operator to optimize each sub-problem.

In Hybrid-MOEA/D-I, the population IP = {I1, I2, …, Ipop} of pop individual solutions I is defined in Eq. (18), pop is the size of population, each as a fixed-length chromosome of size equal to the total number of nodes in WSN. Iji is the j-th gene (sensor node)

Performance comparison of different algorithms

In this paper, all algorithms are implemented using MATLAB. To evaluate the performance of Hybrid-MOEA/D-I and Hybrid-MOEA/D-II, simulation results are compared to those of MOPSO, NSGA-II, MOEA/D and MOEA/D-PSO using the same machine and parameters. The experimental parameters are shown in Table 3.

We compare the performance of our proposed two algorithms, i.e. Hybrid-MOEA/D-I and Hybrid-MOEA/D-II, with other four algorithms, including MOPSO, NSGA-II, MOEA/D and MOEAD-PSO for WSN with different

Conclusion

The issues of reducing and balancing the energy consumption while retaining high coverage rate represent conflicting objectives for WSN. In this paper, we model the coverage control problem in WSN as a MOP problem by considering three objectives, including the coverage rate, the energy consumption and the energy consumption equilibrium. A Hybrid-MOEA/D-I algorithm has been proposed based on the well-known MOEA/D algorithm. To increase population diversity, hybrid GA and DE reproduction

Acknowledgments

This work has been supported by the National Key Research and Development Plan (No: 2016YFB0200405), National Natural Science Foundation of China (No: 61202289 and 61772191) and the Science and Technology Plan of Hunan Province (No. 2015GK3015).

References (42)

  • R.V. Kulkarni et al.

    Particle swarm optimization in wireless-Sensor networks: a brief survey

    IEEE Trans. Syst. Man Cybern. Part C

    (2011)
  • S. Özdemir et al.

    Multi-Objective Evolutionary Algorithm Based on Decomposition for Energy Efficient Coverage in Wireless Sensor Networks

    Wireless Pers. Commun.

    (2013)
  • K. Deb et al.

    A fast and elitist multiobjective genetic algorithm: NSGA-II

    IEEE Trans. Evol. Comput.

    (2002)
  • T. Liang et al.

    Multi-objective coverage control strategy for wireless sensor networks

    Chin. J. Sens. Actuators

    (2010)
  • Y. Xu et al.

    A simulated annealing based genetic local search algorithm for multi-objective multicast routing problems

    Ann. Oper. Res.

    (2013)
  • R. Qu et al.

    Particle swarm optimization for the Steiner tree in graph and delay-constrained multicast routing problems

    J. Heuristics

    (2013)
  • J.H. Liu et al.

    The analysis of binary particle swarm optimization

    J. Nanjing Univ.

    (2011)
  • W.B. Heinzelman et al.

    An application specific protocol architecture for wireless microsensor networks

    IEEE Trans. Wireless Commun.

    (2002)
  • A. Gupta et al.

    H-IECBR: HBO based-Improved energy efficient chain based routing protocol in WSN

  • B. Kushal et al.

    Cluster based routing protocol to prolong network lifetime through mobile sink in WSN

    IEEE International Conference on Recent Trends in Electronics

    (2016)
  • Y. Li et al.

    Reliable energy-aware routing protocol for heterogeneous WSN based on beaconing

  • Cited by (0)

    View full text