Award Date

1-1-2004

Degree Type

Thesis

Degree Name

Master of Science (MS)

Department

Computer Science

First Committee Member

Laxmi P. Gewali

Number of Pages

75

Abstract

Short-length paths in geometric graphs are not necessarily feasible in sensor networks and robotics. Paths with sharp-turn angles cannot be used by robotic vehicles and tend to consume more energy in sensor networks; In this thesis, we investigate the development of short-length paths without sharp-turn angles. We present a critical review of existing algorithms for generating angle constrained paths. We then consider the construction of routes having directional properties---d-monotone routes which are special cases of angle constrained paths. We develop a centralized algorithm for computing shortest d-monotone paths in triangulated networks. Since local computations are highly desired in sensor networks, we also consider localized online algorithms for computing length-reduced d-monotone paths in Delaunay Triangulation networks; The proposed algorithms are implemented in the Java programming language. Performances of the proposed algorithms are evaluated by examining the routes constructed by them on several randomly-generated Delaunay networks.

Keywords

Angle; Constrained; Networks; Paths; Sensor

Controlled Subject

Computer science

File Format

pdf

File Size

2.12 MB

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.


Share

COinS