Browsing by Subject "Sensor networks"
- Results Per Page
- Sort Options
Item Open Access Applications of Persistent Homology to Time Varying Systems(2013) Munch, ElizabethThis dissertation extends the theory of persistent homology to time varying systems. Most of the previous work has been dedicated to using this powerful tool in topological data analysis to study static point clouds. In particular, given a point cloud, we can construct its persistence diagram. Since the diagram varies continuously as the point cloud varies continuously, we study the space of time varying persistence diagrams, called vineyards when they were introduced by Cohen-Steiner, Edelsbrunner, and Morozov.
We will first show that with a good choice of metric, these vineyards are stable for small perturbations of their associated point clouds. We will also define a new mean for a set of persistence diagrams based on the work of Mileyko et al. which, unlike the previously defined mean, is continuous for geodesic vineyards.
Next, we study the sensor network problem posed by Ghrist and de Silva, and their application of persistent homology to understand when a set of sensors covers a given region. Giving each of these sensors a probability of failure over time, we show that an exact computation of the probability of failure of the whole system is NP-hard, but give an algorithm which can predict failure in the case of a monitored system.
Finally, we apply these methods to an automated system which can cluster agents moving in aerial images by their behaviors. We build a data structure for storing and querying the information in real-time, and define behavior vectors which quantify behaviors of interest. This clustering by behavior can be used to find groups of interest, for which we can also quantify behaviors in order to determine whether the group is working together to achieve a common goal, and we speculate that this work can be extended to improving tracking algorithms as well as behavioral predictors.
Item Open Access Control and Optimization of Track Coverage in Underwater Sensor Networks(2007-12-14) Baumgartner, Kelli A. CrewsSensor network coverage refers to the quality of service provided by a sensor network surveilling a region of interest. So far, coverage problems have been formulated to address area coverage or to maintain line-of-sight visibility in the presence of obstacles (i.e., art-gallery problems). Although very useful in many sensor applications, none of the existing formulations address coverage as it pertains to target tracking by means of multiple sensors, nor do they provide a closed-form function that can be applied to the problem of allocating sensors for the surveilling objective of maximizing target detection while minimizing false alarms. This dissertation presents a new coverage formulation addressing the quality of service of sensor networks that cooperatively detect targets traversing a region of interest, and is readily applicable to the current sensor network coverage formulations. The problem of track coverage consists of finding the positions of n sensors such that the amount of tracks detected by at least k sensors is optimized. This dissertation studies the geometric properties of the network, addressing a deterministic track-coverage formulation and binary sensor models. It is shown that the tracks detected by a network of heterogeneous omnidirectional sensors are the geometric transversals of non-translates families of disks. A novel methodology based on cones and convex analysis is presented for representing and measuring sets of transversals as closed-form functions of the sensors positions and ranges. As a result, the problem of optimally deploying a sensor network with the aforementioned objectives can be formulated as an optimization problem subject to mission dynamics and constraints. The sensor placement problem, in which the sensors are placed such that track coverage is maximized for a fixed sensor network, is formulated as a nonlinear program and solved using sequential quadratic programming. The sensor deployment, involving a dynamic sensor network installed on non-maneuverable sonobuoys deployed in the ocean, is formulated as an optimization problem subject to inverse dynamics. Both a finite measure of the cumulative coverage provided by a sensor network over a fixed period of time and the oceanic-induced current velocity field are accounted for in order to optimize the dynamic sensor network configuration. It is shown that a state-space representation of the motions of the individual sensors subject to the current vector field can be derived from sonobuoys oceanic drift models and obtained from CODAR measurements. Also considered in the sensor model are the position-dependent acoustic ranges of the sensors due to the effects from heterogenous environmental conditions, such as ocean bathymetry, surface temporal variability, and bottom properties. A solution is presented for the initial deployment scheme of the non-maneuverable sonobuoys subject to the ocean's current, such that sufficient track coverage is maintained over the entire mission. As sensor networks are subject to random disturbances due to unforseen heterogenous environmental conditions propagated throughout the sensors trajectories, the optimal initial positions solution is evaluated for robustness through Monte Carlo simulations. Finally, the problem of controlling a network of maneuverable underwater vehicles, each equipped with an onboard acoustic sensor is formulated using optimal control theory. Consequently, a new optimal control problem is presented that integrates sensor objectives, such as track coverage, with cooperative path planning of a mobile sensor network subject to time-varying environmental dynamics.Item Open Access Geometric Hitting Sets and Their Variants(2011) Ganjugunte, Shashidhara KrishnamurthyThis thesis explores a few geometric optimization problems that arise
in robotics and sensor networks. In particular we present efficient
algorithms for the hitting-set problem and the budgeted hitting-set problem.
Given a set of objects and a collection of subsets of the objects,
called ranges, the hitting-set problem asks for a minimum number of
objects that intersect all the subsets in the collection.
In geometric settings, objects are
typically a set of points and ranges are defined by a set of geometric
regions (e.g., disks or polygons), i.e., the subset of points lying in each
region forms a range.
The first result of this thesis is an efficient algorithm for an instance
of the hitting-set problem in which both the set of points and the set
of ranges are implicitly defined. Namely, we are given a convex
polygonal robot and a set of convex polygonal obstacles, and we wish
to find a small number of congruent copies of the robot that intersect
all the obstacles.
Next, motivated by the application of sensor placement in sensor networks,
we study the so-called ``art-gallery'' problem. Given a polygonal
environment, we wish to place the minimum number of guards so that
the every point in the environment is visible from at least one guard.
This problem can be formulated as a hitting-set problem. We present
a sampling based algorithm for this problem and study various extensions
of this problem.
Next, we study the geometric hitting-set problem in a dynamic setting,
where the objects and/or the ranges change with time and the goal is
to maintain a hitting set. We present algorithms
which maintain a small size hitting set with sub-linear update time.
Finally, we consider the budgeted hitting-set problem, in which we
are asked to choose a bounded number of objects that intersect as many
ranges as possible. Motivated by applications in network vulnerability
analysis we study this problem in a probabilistic setting.
Item Open Access Location-Aware Protocols for Energy-Efficient Information Processing in Wireless Sensor Networks(2009) Sabbineni, HarshavardhanAdvances in the miniaturization of microelectromechanical components have led to battery powered and inexpensive sensor nodes, which can be networked in an ad hoc manner to perform distributed sensing and information processing. While sensor networks can be deployed in inhospitable terrain to provide continuous monitoring and processing capabilities for a wide range of applications, sensor nodes are severely resource-constrained; they typically run on batteries and have a small amount of memory. Therefore, energy-efficient and lightweight protocols are necessary for distributed information processing in these networks.
The data provided by a sensor node is often useful only in the context of the location of the data source. Thus, sensor networks rely on localization schemes to provide location information to sensor nodes. The premise of this thesis is that location-aware protocols, which are based on the assumption that sensor nodes can estimate their location, improve the efficiency of data gathering and resource utilization of wireless sensor networks. Location-awareness improves the energy-efficiency of the protocols needed for routing, transport, data dissemination and self-organization of sensor networks. Existing sensor network protocols typically do not use location information effectively, hence they are not energy-efficient. In this thesis, we show how location information can be leveraged in novel ways in sensor network protocols to achieve energy efficiency. The contributions of this thesis are in four important areas related to network protocol design for wireless sensor networks: 1) self-organization; 2) data dissemination or node reprogramming; 3) service differentiation; and 4) data collection. Work on self-organization (SCARE) and data dissemination (LAF) was carried out from 2002 to 2004 and the work on service differentiation (SensiQoS) and data collection (HTDC) was carried out from 2004 to 2009.
This thesis first presents a new approach for self-configuration of ad hoc sensor networks. The self-configuration of a large number of sensor nodes requires a distributed solution. We propose a scalable self-configuration and adaptive reconfiguration (SCARE) algorithm that exploits the redundancy in sensor networks to extend the lifetime of the network. SCARE distributes the set of nodes in the sensor network into subsets of coordinator nodes and non-coordinator nodes. While coordinator nodes stay awake, provide coverage, and perform multi-hop routing in the network, non-coordinator nodes go to sleep. When nodes fail, SCARE adaptively re-configures the network by selecting appropriate non-coordinator nodes to become coordinators and take over the role of failed coordinators. This scheme only needs local topology information and uses simple data structures in its implementation. SCARE organizes nodes into coordinator and non-coordinator nodes. A recent approach, termed Ripples, has improved upon the selforganization and reconfiguration mechanism proposed in SCARE. It uses a lightweight clustering algorithm to elect cluster heads instead of coordinator nodes based on location information as proposed by SCARE. Ripples selects fewer cluster-head nodes compared to the number of coordinator nodes elected by SCARE by varying the cluster radius and consequently realizes more energy savings while providing comparable sensing coverage.
This thesis next presents an energy-efficient protocol for data dissemination in sensor networks. Sensor networks also enable distributed collection and processing of sensed data. These networks are usually connected to the outside world with base stations or access points through which a user can retrieve the sensed data for further inference and action. Dissemination of information is a challenging problem in sensor networks because of resource constraints. Conventional methods use classical flooding for disseminating data in a sensor network. However, classical flooding suffers from disadvantages such as the broadcast storm problem. We have proposed an energy-efficient scheme that uses the concept of virtual grids to partition (self-configure) the set of nodes into groups of gateway nodes and internal nodes. While gateway nodes forward the packets across virtual grids, internal nodes forward the packets within a virtual grid. The proposed location-aided flooding protocol (LAF) reduces the number of redundant transmissions and receptions by storing a small amount of state information in a packet and inferring the information about nodes that already have the packet from the modified packet header. More recent approach, termed ALAF, has extended the virtual grid concept proposed by LAF to non-uniform sensor network deployments. In ALAF, non-uniform virtual grids are used to improve upon the energy savings provided by LAF and achieve higher energy savings for non-uniform sensor network topologies.
This thesis also addressees the challenging problem of timely data delivery in sensor networks. We propose SensiQos, which leverages the inherent properties of the data generated by events in a sensor network such as spatial and temporal correlation, and realizes energy savings through application-specific in-network aggregation of the data. This data delivery scheme is based on distributed packet scheduling, where nodes make localized decisions on when to schedule a packet for transmission to save energy and to which neighbor they should forward the packet to meet its end-to-end real-time deadline.
Finally, this thesis presents an energy-efficient data collection protocol for sensor networks. It is based on a combination of geographic hash table and mobile sinks that leverage mobile sinks to achieve energy-efficiency in event-driven sensor networks. Next, an analysis of the energy savings realized by the proposed protocol is presented. Simulation results demonstrate significant gains in energy savings for data collection with change in various parameter values.
In summary, this thesis represents an important step towards the design of location-aware energy-efficient protocols for self-configuration, data dissemination, data delivery, and data collection in wireless sensor networks. It is expected to lead to even more efficient protocols for data dissemination, routing, and transport-layer protocols for energy-constrained and failure-prone sensor networks.