Building Energy-efficient Broadcast Trees Using A Genetic Algorithm In Wireless Sensor Networks

Abstract

In wireless broadcast environment, data can be transmitted to several nodes by a single transmission. The nodes in that environment have limited energy resources; therefore we need to reduce the energy consumption when they broadcast data to all nodes to prolong the lifetime of the networks. We call this problem the MPB (minimum power broadcast) problem, and solving the problem has been shown to be an NP-Complete problem [2], [11]. We focus on finding 'near-optimal' solutions for the problem. An algorithm for constructing the minimum power broadcast trees, named BIP (broadcast incremental power) algorithm, was first proposed by Wieselthier et al. in [1], and several other algorithms also have been proposed by researchers so far. They use the broadcast nature of the problem to optimize energy consumption. We propose an alternate search based paradigm wherein the minimum broadcast tree is found using a genetic algorithm, which is used to find an approximate solution to avoid the NP-Completeness problems. We start by using the BIP algorithm and the MST (Minimum Spanning Tree) algorithm to create an initial search space in our genetic algorithm and we evolve the initial broadcast trees in the space to get more energy-efficient broadcast tree. Through the simulations, the genetic algorithm achieved up to 20.60% improvement over the other broadcasting algorithms including the traditional BIP algorithm.