Min Kyung An

Graduation Semester and Year

2007

Language

English

Document Type

Thesis

Degree Name

Master of Science in Computer Science

Department

Computer Science and Engineering

First Advisor

Ramez Elmasri

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.

Disciplines

Computer Sciences | Physical Sciences and Mathematics

Comments

Degree granted by The University of Texas at Arlington

Download

Share

COinS