A Hybrid Genetic Algorithm With Bidirectional Mutation for Maximizing Lifetime of Heterogeneous Wireless Sensor Networks

Abstract

Sleep scheduling is an effective mechanism to extend the lifetime of energy-constrained Wireless Sensor Networks(WSNs). It is often that the sensors are divided into sets with some constraints after plentiful sensors are deployed randomly, and then the sensors are scheduled to be activated successively according to the numbering of the sets. Many approaches divide the sensors into disjoint sets, which are not suitable for heterogeneous WSNs because of the waste of energy. In this paper, we propose a hybrid genetic algorithm which adopts greedy initialization and bidirectional mutation operations, termed BMHGA, to find a number of non-disjoint cover sets to prolong lifetime of heterogeneous WSNs, while subject to ensuring the full coverage of the monitoring area during the network lifetime. BMHGA adopts two-level structured chromosome to indicate the sensors and energy assignment to each set. A novel greedy method only uses little time to initialize the population that avoids time waste of random initialization. A new bidirectional mutation is proposed to keep multiplicity and global search. Through simulations, we show that the proposed algorithm outperforms the other existing approaches, finding the cover sets with longer lifetime by consuming less running time, especially in the large-scale networks. The experiment study also verifies the effectiveness of the proposed genetic operations and reveals the proper parameter settings for BMHGA.

Keywords

• Genetic algorithm
• non-disjoint set cover problem
• sleep scheduling
• wireless sensor networks