Min Kyung An

Graduation Semester and Year




Document Type


Degree Name

Master of Science in Computer Science


Computer Science and Engineering

First Advisor

Ramez Elmasri


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.


Computer Sciences | Physical Sciences and Mathematics


Degree granted by The University of Texas at Arlington