Type
Text
Type
Dissertation
Advisor
Arkin, Esther M. | Mitchell, Joseph S.B. | Gao, Jie | Liu, Zhenhua.
Date
2016-12-01
Keywords
Applied mathematics -- Computer science | Algorithms, Approximation Algorithm, Geometry, NP-hard, Sensor Networks
Department
Department of Applied Mathematics and Statistics
Language
en_US
Source
This work is sponsored by the Stony Brook University Graduate School in compliance with the requirements for completion of degree.
Identifier
http://hdl.handle.net/11401/77066
Publisher
The Graduate School, Stony Brook University: Stony Brook, NY.
Format
application/pdf
Abstract
In this thesis, we address a variety of algorithmic problems motivated by applications in sensor networks. In many of these problems we consider that the placement of the sensors is in a general metric space and in all of the problems we consider the case that the sensors lie in the Euclidean plane and exploit geometric properties in order to achieve better results. We introduce the \sinrk\ model which is a generalization of the SINR model. Given a set of sender-receiver requests in the Euclidean plane, the goal is to minimize the number of rounds of scheduling needed to satisfy all of the requests. In order to determine whether or not receiver $c$ successfully receives the signal sent from its paired sender $s$, we only consider interference from the $k$ closest senders to $c$ (other than $s$). We also consider the maximum capacity problem where the objective is to maximize the number of requests satisfied in a single round of scheduling. We then focus on data gathering problems. In these problems we are given a set of sensors in the Euclidean plane or a general metric space, each of which generates data at a fixed rate and has a fixed capacity. Given a budget of data gathering mules, we route these mules in order to maximize their collective data gathering rate. We also look at the no data loss problem where the objective is to minimize the number of data mules needed for there not to be any data loss in the network. Next, we consider problems in which one needs to select or cover at most one element from each tuple of a set of tuples of elements in order to optimize certain objective functions. These elements are objects in the Euclidean plane. The applications to sensor networks are discussed later in the thesis. Finally, we consider problems where one is given a set of pairs of points in a certain metric space with the task of partitioning the pairs into "red'' and "blue'' sites. Each pair must have exactly one point colored red and exactly one point colored blue. The partition should be made to optimize the cost of certain structures that will be computed on both the red points and the blue points. These types of problems are motivated by applications in sensor networks. These applications will be discussed in this thesis. This work advances the field of sensor networks by improving on previously known results and by introducing and solving problems that have not been previously considered. | 113 pages
Recommended Citation
Citovsky, Gui Benjamin, "Geometric Optimization Problems in Sensor Networks" (2016). Stony Brook Theses and Dissertations Collection, 2006-2020 (closed to submissions). 2904.
https://commons.library.stonybrook.edu/stony-brook-theses-and-dissertations-collection/2904