Hybrid genetic algorithm using a forward encoding scheme for lifetime maximization of wireless sensor networks

Xiao Min Hu*, Jun Zhang, Yan Yu, Henry Shu Hung Chung, Yuan Long Li, Yu Hui Shi, Xiao Nan Luo

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

136 Citations (Scopus)

Abstract

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.

Original languageEnglish
Article number5453089
Pages (from-to)766-781
Number of pages16
JournalIEEE Transactions on Evolutionary Computation
Volume14
Issue number5
DOIs
Publication statusPublished - Oct 2010

Keywords

  • Coverage
  • SET k-cover problem
  • disjoint set covers problem
  • encoding scheme
  • evolutionary algorithm
  • genetic algorithm
  • memetic algorithm
  • redundancy
  • schedule
  • wireless sensor network

Fingerprint

Dive into the research topics of 'Hybrid genetic algorithm using a forward encoding scheme for lifetime maximization of wireless sensor networks'. Together they form a unique fingerprint.

Cite this