Award Date

1-1-2005

Degree Type

Thesis

Degree Name

Master of Science (MS)

Department

Computer Science

First Committee Member

Laxmi P. Gewali

Number of Pages

52

Abstract

Construction of a small size dominating set is a well known problem in graph theory and sensor networks. A Connected dominating set (CDS) can be used as a backbone structure in sensor networks for message delivery and broadcast. The general dominating set problem is known to be NP-hard and some approximation algorithms have been proposed; In most approximation algorithms for constructing connected dominating set only the size of the dominating set has been considered. In this thesis we address the problem of constructing connected dominating sets with several quality factors that include (i) diameter, (ii) risk-factor, and (iii) interference. We propose algorithms for constructing CDS of small diameter, reduced risk-factor, and reduced interference. We also report on the experimental investigation of the proposed techniques. Experimental results show that the proposed algorithms are very effective in reducing interference without significantly increasing CDS size. The proposed algorithms are the first algorithms in the sensor network community that address both size and interference for designing dominating sets.

Keywords

Dominating; Generating; Quality; Set

Controlled Subject

Computer science

File Format

pdf

File Size

1382.4 KB

Degree Grantor

University of Nevada, Las Vegas

Language

English

Permissions

If you are the rightful copyright holder of this dissertation or thesis and wish to have the full text removed from Digital Scholarship@UNLV, please submit a request to digitalscholarship@unlv.edu and include clear identification of the work, preferably with URL.

Rights

IN COPYRIGHT. For more information about this rights statement, please visit http://rightsstatements.org/vocab/InC/1.0/

Download


COinS