| dc.identifier.uri | http://hdl.handle.net/11401/77066 | |
| 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 | |
| dc.format.medium | Electronic Resource | en_US |
| dc.language.iso | en_US | |
| dc.publisher | The Graduate School, Stony Brook University: Stony Brook, NY. | |
| dc.type | Dissertation | |
| dcterms.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. | |
| dcterms.available | 2017-09-20T16:51:50Z | |
| dcterms.contributor | Mitchell, Joseph S.B. | en_US |
| dcterms.contributor | Arkin, Esther M. | en_US |
| dcterms.contributor | Gao, Jie | en_US |
| dcterms.contributor | Liu, Zhenhua. | en_US |
| dcterms.creator | Citovsky, Gui Benjamin | |
| dcterms.dateAccepted | 2017-09-20T16:51:50Z | |
| dcterms.dateSubmitted | 2017-09-20T16:51:50Z | |
| dcterms.description | Department of Applied Mathematics and Statistics | en_US |
| dcterms.extent | 113 pg. | en_US |
| dcterms.format | Monograph | |
| dcterms.format | Application/PDF | en_US |
| dcterms.identifier | http://hdl.handle.net/11401/77066 | |
| dcterms.issued | 2016-12-01 | |
| dcterms.language | en_US | |
| dcterms.provenance | Made available in DSpace on 2017-09-20T16:51:50Z (GMT). No. of bitstreams: 1
Citovsky_grad.sunysb_0771E_12797.pdf: 1063771 bytes, checksum: fb5b25946b7234be21b4271b6f2a8950 (MD5)
Previous issue date: 1 | en |
| dcterms.publisher | The Graduate School, Stony Brook University: Stony Brook, NY. | |
| dcterms.subject | Applied mathematics -- Computer science | |
| dcterms.subject | Algorithms, Approximation Algorithm, Geometry, NP-hard, Sensor Networks | |
| dcterms.title | Geometric Optimization Problems in Sensor Networks | |
| dcterms.type | Dissertation | |
