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

Sajal Das

Abstract

Given a set S = {S1,...,Sn} of n homogeneous wireless sensors deployed in a two dimensional area, a source point s and a destination point t, the least protected point p along a path (s,t) is that point such that the Euclidean distance between p and its closest sensor node Si is maximum. This distance between p and S_{i} is called the Cover value of the path P(s,t). The Best Coverage Path between s and t, denoted as BCP(s,t), is the path that has the minimum cover value. Although there exists efficient algorithms to compute BCP in O(n log n) time, the presence of obstacles inside the two dimensional area has not been addressed in the literature. In this thesis, we consider the problem of computing BCP(s,t) in the presence of m line segment obstacles distributed among n sensors. Because of the presence of obstacles, sensing by sensors can get obstructed and the constructed path may have to detour which pose significant challenges. We propose three algorithms to compute two different variations of the BCP(s; t) problem in the presence of obstacles. In particular, for the case of opaque obstacles, i.e., which obstruct both the sensing as well the computed path, we develop an algorithm that computes BCP(s,t) in $O((m^{2}n^{2} + n^{4})\log(mn+n^{2}))) time. The underlying idea is to leverage the concept of a quartic-time Constrained and Weighted Voronoi diagram among obstacles and creating its dual. For the case of transparent obstacles that cannot obstruct sensing but the computed path has to avoid obstacles, we develop two algorithms that compute BCP(s,t). The first algorithm runs in O(nm^{2}+n^{3}) time using the visibility graph data structure, while the second one is an approximation algorithm and requires O(nm+n^{2})time using spanners of the visibility graph. The approximation factor of the cover value is O nk where k is the stretch factor of the spanner graph. The proofs of correctness of the three proposed algorithms are also presented in this thesis.

Disciplines

Computer Sciences | Physical Sciences and Mathematics

Comments

Degree granted by The University of Texas at Arlington

Download

Share

COinS