Hybrid multi-objective evolutionary algorithms based on decomposition for wireless sensor network coverage optimization
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:
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. 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)
- et al.
Multi-objective optimization for coverage control in wireless sensor network with adjustable sensing radius
Comput. Math. Appl.
(2009) - et al.
WSN coverage hierarchical optimization method based on the improved MOEA/D
Metall. Min. Ind.
(2015) - et al.
Energy-aware evolutionary routing protocol for dynamic clustering of wireless sensor networks
Swarm Evol. Comput.
(2011) - et al.
Energy efficient chain based cooperative routing protocol for WSN
Appl. Soft Comput.
(2015) Coverage Control in Sensor Networks
(2010)Coverage in wireless sensor networks: a survey
Network Protoc. Algorithms
(2010)- et al.
Hybrid sensor networks coverage-enhancing approach based on particle swarm optimization
Appl. Res. Comp.
(2010) - et al.
Node deployment model of multi-objective optimization in wireless sensor networks
Appl. Res. Comp.
(2015) - et al.
Computational intelligence in wireless sensor networks: a survey
IEEE Commun. Surv.
(2011) - et al.
Probabilistic dynamic deployment of wireless sensor networks by artificial bee colony algorithm
Sensors
(2011)