On a vector space representation in genetic algorithms for sensor scheduling in wireless sensor networks

F.V.C. Martins, E.G. Carrano, E. F. Wanner, R.H.C. Takahashi, G.R. Mateus, F.G. Nakamura

Research output: Contribution to journalArticlepeer-review

Abstract

Recent works raised the hypothesis that the assignment of a geometry to the decision variable space of a combinatorial problem could be useful both for providing meaningful descriptions of the fitness landscape and for supporting the systematic construction of evolutionary operators (the geometric operators) that make a consistent usage of the space geometric properties in the search for problem optima. This paper introduces some new geometric operators that constitute the realization of searches along the combinatorial space versions of the geometric entities descent directions and subspaces. The new geometric operators are stated in the specific context of the wireless sensor network dynamic coverage and connectivity problem (WSN-DCCP). A genetic algorithm (GA) is developed for the WSN-DCCP using the proposed operators, being compared with a formulation based on integer linear programming (ILP) which is solved with exact methods. That ILP formulation adopts a proxy objective function based on the minimization of energy consumption in the network, in order to approximate the objective of network lifetime maximization, and a greedy approach for dealing with the system’s dynamics. To the authors’ knowledge, the proposed GA is the first algorithm to outperform the lifetime of networks as synthesized by the ILP formulation, also running in much smaller computational times for large instances.

Original languageEnglish
Pages (from-to)361-403
Number of pages43
JournalEvolutionary Computation
Volume22
Issue number3
Early online date13 Aug 2014
DOIs
Publication statusPublished - 13 Sep 2014

Keywords

  • dynamic optimization
  • genetic algorithms
  • geometric operators
  • wireless sensor networks

Fingerprint

Dive into the research topics of 'On a vector space representation in genetic algorithms for sensor scheduling in wireless sensor networks'. Together they form a unique fingerprint.

Cite this