DSpace Repository

Geometric Optimization Problems in Sensor Networks

Show simple item record

dc.contributor.advisor Mitchell, Joseph S.B. en_US
dc.contributor.author Citovsky, Gui Benjamin en_US
dc.contributor.other Department of Applied Mathematics and Statistics en_US
dc.date.accessioned 2017-09-20T16:51:50Z
dc.date.available 2017-09-20T16:51:50Z
dc.date.issued 2016-12-01 en_US
dc.identifier.uri http://hdl.handle.net/11401/77066 en_US
dc.description 113 pg. en_US
dc.description.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. en_US
dc.description.sponsorship This work is sponsored by the Stony Brook University Graduate School in compliance with the requirements for completion of degree. en_US
dc.format Monograph en_US
dc.format.medium Electronic Resource en_US
dc.language.iso en_US en_US
dc.publisher The Graduate School, Stony Brook University: Stony Brook, NY. en_US
dc.subject.lcsh Applied mathematics -- Computer science en_US
dc.subject.other Algorithms, Approximation Algorithm, Geometry, NP-hard, Sensor Networks en_US
dc.title Geometric Optimization Problems in Sensor Networks en_US
dc.type Dissertation en_US
dc.mimetype Application/PDF en_US
dc.contributor.committeemember Arkin, Esther M. en_US
dc.contributor.committeemember Gao, Jie en_US
dc.contributor.committeemember Liu, Zhenhua. en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search DSpace

Advanced Search


My Account