An evolutionary algorithm for broadcast scheduling in wireless multihop networks

摘要

A technical challenge in successful deployment and utilization of wireless multihop networks (WMN) are to make effective use of the limited channel bandwidth. One method to solve this challenge is broadcast scheduling of channel usage by the way of time division multiple access (TDMA). Three evolutionary algorithms, namely genetic algorithm (GA), immune genetic algorithm (IGA) and memetic algorithm (MA) are used in this study to solve broadcast scheduling for TDMA in WMN. The aim is to minimize the TDMA cycle length and maximize the node transmissions with reduced computation time. In comparison to GA and IGA, MA actively aim on improving the solutions and is explicitly concerned in exploiting all available knowledge about the problem. The simulation results on numerous problem instances confirm that MA significantly outperforms several heuristic and evolutionary algorithms by solving well-known benchmark problem in terms of solution quality, which also demonstrates the effectiveness of MA in efficient use of channel bandwidth.