Hybrid Genetic Algorithm Using a Forward Encoding Scheme for Lifetime Maximization of Wireless Sensor Networks

• Published in: IEEE transactions on evolutionary computation 2010-10, Vol.14 (5), p.766-781
• Main Authors: Xiao-Min Hu, Jun Zhang, Yan Yu, Chung, Henry Shu-Hung, Yuan-Long Li, Yu-Hui Shi, Xiao-Nan Luo
• Format: Article
• Language: English
• Subjects: Applied sciences; Biological cells; Chromosomes; Computer science education; Computer science; control theory; systems; Computer systems and distributed systems. User interface; Coverage; Detection; disjoint set covers problem; Encoding; encoding scheme; Energy efficiency; evolutionary algorithm; Exact sciences and technology; genetic algorithm; Genetic algorithms; Genetics; Maximization; memetic algorithm; Networks; Polynomials; redundancy; schedule; Schedules; Sensor phenomena and characterization; Sensors; SET k-cover problem; Software; Studies; Sun; Surveillance; wireless sensor network; Wireless sensor networks
• ISSN: 1089-778X; 1941-0026
• DOI: 10.1109/TEVC.2010.2040182

Maximizing the lifetime of a sensor network by scheduling operations of sensors is an effective way to construct energy efficient wireless sensor networks. After the random deployment of sensors in the target area, the problem of finding the largest number of disjoint sets of sensors, with every set being able to completely cover the target area, is nondeterministic polynomial-complete. This paper proposes a hybrid approach of combining a genetic algorithm with schedule transition operations, termed STHGA, to address this problem. Different from other methods in the literature, STHGA adopts a forward encoding scheme for chromosomes in the population and uses some effective genetic and sensor schedule transition operations. The novelty of the forward encoding scheme is that the maximum gene value of each chromosome is increased consistently with the solution quality, which relates to the number of disjoint complete cover sets. By exerting the restriction on chromosomes, the forward encoding scheme reflects the structural features of feasible schedules of sensors and provides guidance for further advancement. Complying with the encoding requirements, genetic operations and schedule transition operations in STHGA cooperate to change the incomplete cover set into a complete one, while the other sets still maintain complete coverage through the schedule of redundant sensors in the sets. Applications for sensing a number of target points, termed point-coverage, and for the whole area, termed area-coverage, have been used for evaluating the effectiveness of STHGA. Besides the number of sensors and sensors' sensing ranges, the influence of sensors' redundancy on the performance of STHGA has also been analyzed. Results show that the proposed algorithm is promising and outperforms the other existing approaches by both optimization speed and solution quality.