A Variable-Length Chromosome Genetic Algorithm for Time-Based Sensor Network Schedule Optimization

Abstract

Scheduling sensor nodes has an important role in real monitoring applications using sensor networks, lowering the power consumption and maximizing the network lifetime, while maintaining the satisfaction to application requirements. Nevertheless, this problem is usually very complex and not easily resolved by analytical methods. In a different manner, genetic algorithms (GAs) are heuristic search strategies that help to find the exact or approximate global optimal solution efficiently with a stochastic approach. Genetic algorithms are advantageous for their robustness to discrete and noisy objective functions, as they are only evaluated at independent points without requirements of continuity or differentiability. However, as explained in this paper, a time-based sensor network schedule cannot be represented by a chromosome with fixed length that is required in traditional genetic algorithms. Therefore, an extended genetic algorithm is introduced with variable-length chromosome (VLC) along with mutation and crossover operations in order to address this problem. Simulation results show that, with help of carefully defined fitness functions, the proposed scheme is able to evolve the individuals in the population effectively and consistently from generation to generation towards optimal ones, and the obtained network schedules are better optimized in comparison with the result of algorithms employing a fixed-length chromosome.

Keywords

• wireless sensor networks
• variable-length chromosome genetic algorithms
• schedule optimization
• planning optimization
• energy efficiency