Browsing by Subject "Sensor networks"

Now showing 1 - 11 of 11

Clustering prediction for the ID-based clustering algorithm
(2007-12) Doyle, James C., 1983-; Akella, Maruthi Ram, 1972-
The field of clustering offers a very promising benefit to the field of multi-agent sensor networks. Within sensor networks, clustering is essential in creating a hierarchical structure to ad-hoc systems. Furthermore, in order to determine the necessary performance capabilities for the participating nodes of a sensor grid, it would be helpful to have a priori knowledge of the expected number of clusters that will be formed by a given clustering algorithm. The efficiency of operation within a decentralized, distributed sensor network can be greatly improved upon with the aid of both clustering and an accurate prediction of the total number of clusters to be expected. This thesis details an analysis of the ID-Based Clustering algorithm (originally proposed by Gao et al.[5]), an algorithm that utilizes node identification numbers as its clusterhead nomination criterion, and an attempt to determine an analytical model to accurately predict the number of clusters expected from this algorithm. The approach taken to analyzing this method utilizes techniques from probability theory and applies them to a 1-D field of length, L, populated by N sensors (or, alternatively, `nodes') that have a given radius of communication, R. The goal of the model is to predict the average number of clusters from the ID-Based Clustering algorithm knowing only N and the ratio R/L . The result of this study is a proposed model that is accurate to within 15% of a clustering average determined through analyzing trial computer simulations that emulate a one-dimensional sensor field populated with up to fifty sensors that are clustered using the ID-Based Clustering algorithm. In addition to the one-dimensional analysis presented, a two-dimensional analysis is initiated by the end of the study and an alternative to the ID- Based Clustering Algorithm dubbed the Cascade Nomination Method is introduced. Meaningful directions for future work would be to complete the two-dimensional model, improve upon the accuracy of the one-dimensional model, and perform similar analysis on the Cascade Nomination Method.
Design and analysis of self-stabilizing sensor network protocols
(2007-08) Choi, Young-ri; Gouda, Mohamed G., 1947-
A sensor is a battery-operated small computer with an antenna and a sensing board that can sense magnetism, sound, heat, etc. Sensors in a network communicate and cooperate with other sensors to perform given tasks. A sensor network is exposed to various dynamic factors and faults, such as topology changes, energy saving features, unreliable communication, and hardware/software failures. Thus, protocols in this sensor network should be able to adapt to dynamic factors and recover from faults. In this dissertation, we focus on designing and analyzing a class of sensor network protocols, called self-stabilizing protocols. A self-stabilizing protocol is guaranteed to return to a state where it performs its intended function correctly, when some dynamic factors or faults corrupt the state of the protocol arbitrarily. Therefore, in order to make a sensor network resilient to dynamic factors and faults, each protocol in the sensor network should be self-stabilizing. We first develop a state-based model that can be used to formally specify sensor network protocols. This model accommodates several unique characteristics of sensor networks, such as unavoidable local broadcast, probabilistic message transmission, asymmetric communication, message collision, and timeout actions and randomization steps. Second, we present analysis methods for verifying and analyzing the correctness and self-stabilization properties of sensor network protocols specified in this model. Third, using the state-based model and analysis methods, we design three self-stabilizing sensor network protocols, prove their self-stabilization properties, and estimate their performance. These three self-stabilizing protocols are a sentry-sleeper protocol that elects a sentry from a group of sensors at the beginning of each time period, a logical grid routing protocol that builds a routing tree whose root is the base station, and a family of flood sequencing protocols that distinguish between fresh and redundant flood messages using sequence numbers.
Embedded sensor speed and width estimation
(2017-12) DeKoning, Matthew Wayne; Evans, Brian L. (Brian Lawrence), 1965-; Valvano, Jonathan
The goal of this report is to provide a novel system of estimating width and velocity of an object passing perpendicularly through a sensor field. By fixing four sensors on an axis at known angles the distance and velocity of an object can be estimated from the times of detection of each sensor using a system of equations. To develop a prototype of this system the scenario was modeled and simulated, a processor and sensors were selected, and algorithms for detection and estimation were developed. The goal of the report was to develop a self-contained sensor network and computing platform that would correctly estimate the speed of the object in miles per hour within 15% accuracy, and to estimate the width of the object within 20% accuracy. Due to prototype design errors, these requirements were not met, however useful algorithms and simulations were developed to lead towards successful future work.
Intelligent, remote-controlled home protection system
(2013-12) Das, Anindita; Barber, Suzanne
As our society gets increasingly mobile, it is becoming commonplace for residences to remain vacant for a significant amount of time every day. Unfortunately, emergencies can occur during those time, which may require immediate mitigatory action. This project proposes an approach that allows the resident to be notified of such emergencies and to perform mitigatory actions, even when she is hundreds of miles away. Our infrastructure includes three components: (1) programmable sensor devices to detect emergency situations; (2) a Web service hosted in the resident's home computer to send a notification to the smartphone of the user; and (3) a smartphone app that communicates with this Web service to notify the user, and provides a interface for the user to perform any mitigatory action. We develop a prototype system for detecting fire and intrusion emergencies. Our prototype system uses two sunSPOTs as sensors, an iRobot Create® as a mitigatory device, an Android app for user notification.
Monitoring uncertain data for sensor-based real-time systems
(2008-05) Woo, Honguk; Mok, Aloysius Ka-Lau
Monitoring of user-defined constraints on time-varying data is a fundamental functionality in various sensor-based real-time applications such as environmental monitoring, process control, location-based surveillance, etc. In general, these applications track real-world objects and constantly evaluate the constraints over the object trace to take a timely reaction upon their violation or satisfaction. While it is ideal that all the constraints are evaluated accurately in real-time, data streams often contain incomplete and delayed information, rendering the evaluation results of the constraints uncertain to some degree. In this dissertation, we provide a comprehensive approach to the problem of monitoring constraint-based queries over data streams for which the data or timestamp values are inherently uncertain. First, we propose a generic framework, namely Ptmon, for monitoring timing constraints and detecting their violation early, based on the notion of probabilistic violation time. In doing so, we provide a systemic approach for deriving a set of necessary timing constraints at compilation time. Our work is innovative in that the framework is formulated to be modular with respect to the probability distributions on timestamp values. We demonstrate the applicability of the framework for different timestamp models. Second, we present a probabilistic timing join operator, namely Ptjoin, as an extended functionality of Ptmon, which performs stream join operations based on temporal proximity as well as temporal uncertainty. To efficiently check the Ptjoin condition upon event arrivals, we introduce the stream-partitioning technique that delimits the probing range tightly. Third, we address the problem of monitoring value-based constraints that are in the form of range predicates on uncertain data values with confidence thresholds. A new monitoring scheme Spmon that can reduce the amount of data transmission and thus expedite the processing of uncertain data streams is introduced. The similarity concept that was originally intended for real-time databases is extended for our probabilistic data stream model where each data value is given by a probability distribution. In particular, for uniform and gaussian distributions, we show how we derive a set of constraints on distribution parameters as a metric of similarity distances, exploiting the semantics of probabilistic queries being monitored. The derived constraints enable us to formulate the probabilistic similarity region that suppresses unnecessary data transmission in a monitoring system.
Networked control and efficient transmission in sensor networks
(2007) Wu, Wei, doctor of electrical and computer engineering; Arapostathis, Ari, 1954-
Enabling "intelligent environments" that are effortlessly automated is a key promise of sensor networks of the future. These networks have a wide range of domains in which they can be effectively deployed, including health-care, emergency response, manufacturing and surveillance. Unlike the majority of existing (and perhaps better-understood) network configurations, wireless-implemented sensor networks suffer from extremely stringent constraints in terms of scalability and end-goal of deployment. Thus, it is imperative that we determine solutions that are tailored to the constraints and goals of these systems, by bringing together ideas in the domains of control, computing and communications to a common analytical platform. In this dissertation, we build a theoretical framework that uses system theory, stochastic control, queuing theory and information theory to determine the following: 1. A characterization of the stability and optimal control policies with sensor querying (i.e. which set of sensors must be queried and when) using system theory and stochastic control; 2. A delay-optimal energy efficient transmission scheme for these networks (i.e. with what power level must they communicate) using heavy traffic limits and stochastic control; and 3. A cooperative transmission strategy for maximizing capacity of these networks (i.e. how they should encode their data to send the most through) using network information theory.
Query domains : grouping heterogeneous sensors based on proximity
(2007-05-19) Rajamani, Vasanth; Julien, Christine D. Sc.
Efficient query processing in sensor networks involves identifying groups of nodes that coordinate to satisfy applications’ requests. In this thesis, we propose a query domain abstraction that allows an application to dynamically specify the nodes best suited to answering a particular query. To self-organize into such a coalition, nodes must satisfy a proximity function, a user-defined function that constrains the relative relationship among the group of nodes (e.g., based on a property of the network or physical environment or a logical properties of the nodes). The proximity function removes the need to explicitly tag nodes with context information, and it provides a convenient mechanism for forming coalitions on the fly at query time. This facilitates the deployment of general-purpose sensor networks, where multiple applications can be run in the same network at the same time. In this work, we model this abstraction, present a set of protocols to support the abstraction, and evaluate their performance in comparison with alternatives.
Routing and broadcasting over sensor networks
(2008-08) Subramanian, Sundar, 1981-; Shakkottai, Sanjay
Advances in micro-embedded computing systems, coupled with developments in wireless technology have enabled the deployment of large scale wireless and sensor networks for many important applications. These networks are characterized by local geographic connectivity among nodes and by very little computational and storage capabilities at each node. Moreover, data transfer is mainly through packet forwarding by intermediary nodes. Due to the nature of their connectivity, nodes may have extremely limited information about their network, possibly only of their one-hop neighbors. In such a scenario where the nodes may have limited/erroneous network state information, we study the two basic network primitives: (i) point-to-point routing and (ii) broadcasting. First, we study the problem of point-to-point routing in a network of nodes where each node has a corresponding destination to send/receive data. We consider geographic routing (routing based on the position of the nodes), as this routing scheme is scalable and of low complexity and well suited to operate over sensor networks. We study the effect of imperfect routing information on the path lengths of the individual routes. We provide error models for the routing errors and demonstrate routing strategies that achieve order-wise optimal delays even when only a small fraction of the nodes have any (possibly imperfect) geographic information. We characterize the throughput capacity of the network and show that for a class of progressive routing strategies with limited routing data, the throughput capacity is order-wise optimal. While much of the current research focuses on greedy routing in uniform sensor networks, we study routing in imperfect (anisotropic) networks where greedy geographic forwarding fails due to holes (nodes without any neighbors that are closer to the destination). We develop routing strategies in such networks that operate with geographic location at the nodes to achieve order-wise optimal delays while maximizing the network throughput capacity. These algorithms inherit the beneficial properties of geographic routing algorithms such as scalability and low complexity while providing near-optimal throughput and delay in a robust manner. We also study routing strategies in networks where the traffic demand may be non-uniform. Routing schemes such as geographic routing that minimize some metric of routing distance cause local points of congestion as they do not consider the traffic demands across different parts of the network and may concentrate traffic along some paths that lie across regions of higher demand. We design randomized routing schemes based on geographic routing that are shown to be able to support any traffic demand that is achievable (i.e. achievable by any other scheme). Second, we study the issue of broadcasting in networks with limited local information. We analyze broadcast schemes where nodes have little geographic information or state information (memory of transmitted packets). We demonstrate randomized broadcast algorithms that utilize the limited information and perform broadcasting with minimal transmission overheads. Further, we also study branching random walks in R[superscript d], in the context of broadcasting a message over a spatial network to understand the asymptotic distribution of the broadcast. We derive analytic results on the density of these branching processes
Understanding query quality in dynamic networks
(2010-08) Rajamani, Vasanth; Julien, Christine, D. Sc.; Perry, Dewayne; Batory, Don; Garg, Vijay; Bias, Randolph
With the proliferation of laptops, smart phones, sensors and other small devices, our physical environment is increasingly networked. Applications in a variety of problem domains (e.g., intelligent construction, traffic monitoring, smart homes, etc.) need to efficiently and seamlessly execute on top of such emerging infrastructure. Such infrastructure tends to be unreliable, and the network configuration changes constantly (network hosts depart and reemerge frequently). Consequently, software has to be able to react to these changes continuously and change its behaviors accordingly. In this dissertation, I introduce PAQ (Persistent Adaptive Query), a middleware designed to ease the programming burden associated with writing such applications. PAQ employs a novel style of query-driven application development that allows programmers to build pervasive applications by employing persistent queries--queries that continuously monitor the environment. The dissertation discusses the design and implementation of a new middleware model that allows programmers to write high level specifications abstracting away several tedious implementation details. PAQ employs both novel protocols that automatically tag the quality of information obtained from the network and statistical techniques to post-process and smooth the data. The goal of this research is to ease the software engineering challenges encountered during the construction and deployment of several applications in emerging pervasive computing environments thorough the use of a query-driven application development paradigm.
Unpowered wireless sensors for structural health monitoring
(2006) Andringa, Matthew; Neikirk, Dean P.
The rapid advancement of wireless technology has allowed the development of new sensor technologies for many different applications. Unfortunately, many of the sensor systems have a substantial cost and require a continuous power source. A new class of sensors is proposed for use in situations where cost and long-term durability are of major concern. For example, corrosion of steel reinforced concrete is a worldwide problem, with potential damages estimated at billions of dollars in the United States alone. A simple low-cost resonant-based embeddable sensor platform is proposed. The sensor is wirelessly powered and interrogated through a magnetically coupled reader coil. The sensor circuit is analyzed and a series of design guidelines are developed. Two prototype sensors, one to detect corrosion of steel reinforcement in concrete and one to measure conductivity, are proposed and tested both in the laboratory as well as in actual reinforced concrete members. The use of the wireless platform for other types of sensors is also discussed. Results indicate that the sensor platform performs well and may aid in the early detection of corrosion in reinforced concrete.
Weak and strong authentication in computer networks
(2012-12) Choi, Taehwan; Gouda, Mohamed G., 1947-; Lam, Simon S; Mok, Aloysius K; Zhang, Yin; Young, William D; Kulkarni, Sandeep
In this dissertation, we design and analyze five authentication protocols that answer to the a firmative the following fi ve questions associated with the authentication functions in computer networks. 1. The transport protocol HTTP is intended to be lightweight. In particular, the execution of applications on top of HTTP is intended to be relatively inexpensive and to take full advantage of the middle boxes in the Internet. To achieve this goal, HTTP does not provide any security guarantees, including any authentication of a server by its clients. This situation raises the following question. Is it possible to design a version of HTTP that is still lightweight and yet provides some security guarantees including the authentication of servers by their clients? 2. The authentication protocol in HTTPS, called TLS, allows a client to authenti- cate the server with which it is communicating. Unfortunately, this protocol is known to be vulnerable to human mistakes and Phishing attacks and Pharm- ing attacks. Is it possible to design a version of TLS that can successfully defend against human mistakes and Phishing attacks and Pharming attacks? 3. In both HTTP and HTTPS, a server can authenticate a client, with which it is communicating, using a standard password protocol. However, standard password protocols are vulnerable to the mistake of a client that uses the same password with multiple servers and to Phishing and Pharming attacks. Is it possible to design a password protocol that is resilient to client mistakes (of using the same password with multiple servers) and to Phishing and Pharming attacks? 4. Each sensor in a sensor network needs to store n - 1 symmetric keys for secure communication if the sensor network has n sensor nodes. The storage is constrained in the sensor network and the earlier approaches succeeded to reduce the number of keys, but failed to achieve secure communications in the face of eavesdropping, impersonation, and collusion. Is it possible to design a secure keying protocol for sensor networks, which is e fficient in terms of computation and storage? 5. Most authentication protocols, where one user authenticates a second user, are based on the assumption that the second user has an "identity", i.e. has a name that is (1) fi xed for a relatively long time, (2) unique, and (3) ap- proved by a central authority. Unfortunately, the adoption of user identities in a network does create some security holes in that network, most notably anonymity loss, identity theft, and misplaced trust. This situation raises the following question. Is it possible to design an authentication protocol where the protocol users have no identities?