Type
Text
Type
Dissertation
Advisor
Mitchell, Joseph | Gao, Jie | Arkin, Esther | Johnson, Matthew P.
Date
2016-12-01
Keywords
Computer science -- Applied mathematics | Algorithms, Computational Geometry, Sensor Networks
Department
Department of Computer Science
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/77259
Publisher
The Graduate School, Stony Brook University: Stony Brook, NY.
Format
application/pdf
Abstract
As computers become more ubiquitous in the prominent phenomenon of the Internet of Things, we encounter many unique challenges in the field of wireless sensor networks. A wireless sensor network is a group of small, low powered sensors with wireless capability to communicate with each other. The goal of these sensors, also called nodes, generally is to collect some information about their environment and report it back to a base station. Depending on the nature of the nodes or the environment, they may be placed in a deterministic pattern, deployed randomly, or mobile (i.e. cars on a highway). Due to the varying nature of these types of networks, they need specialized algorithms tailored to their scenarios and optimized to make efficient use of the limited power resources of the nodes. In this report, we provide upper and lower bounds for the following six different wireless sensor network problems. - Spanner on Imprecise Points: We consider the construction of a Euclidean spanner for imprecise points where we take advantage of prior, inexact knowledge of our input. - Distributed Mobile Sensor Coverage: We consider the problem of covering a domain by mobile sensors and the design of an ecient schedule that reduces unnecessary sensor overlap and energy consumption. - The Data Gathering Problem: A data mule tours around a sensor network and helps with network maintenance such as data collection and battery recharging/replacement. We assume that each sensor has a fixed data generation rate and a capacity (upper bound on storage size). If the data mule arrives after the storage capacity is met, additional data generated is lost. We aim to schedule a tour for the mule such that it optimally services the network. - The Shortest Separating Cycle Problem: Given a set of pairs of points in the plane, the goal of the minimum length separating cycle problem is to find a simple tour of minimum length that separates the two points of each pair on different sides. - r-gather Clustering: Given a set of points in Euclidean space and a value r, the aim of the r-gather problem is to cluster the points into groups of at least r points each such that the largest diameter of the clusters is minimized. - Geographical Routing in 3D: Given a graph on vertices embedded in R^3, the objective is to add the minimum number of virtual edges such that greedy routing succeeds for any source and destination pair. | 128 pages
Recommended Citation
Zeng, Jiemin, "Integrating Mobile Agents and Distributed Sensors in Wireless Sensor Networks" (2016). Stony Brook Theses and Dissertations Collection, 2006-2020 (closed to submissions). 3081.
https://commons.library.stonybrook.edu/stony-brook-theses-and-dissertations-collection/3081