Research Summary

For details, look at the publication page.

High Integrity Sensor Networks

Reputation-based framework for sensor networks (RFSN) - Webpage

The traditional approach of providing network security has been to borrow tools from cryptography and authentication. However, we argue that the conventional view of security based on cryptography alone is not sufficient for the unique characteristics and novel misbehaviors encountered in sensor networks. Fundamental to this is the observation that sensor network applications are based on collective interaction between a large numbers of nodes, which do collaborative data gathering, collective data/information processing, and multi-hop data delivery. This decentralized in-network decision-making, which relies on the inherent trust among the sensor nodes, can be abused by internal adversaries to carry out security breaches while generating information. Our approach is to combine cryptographic mechanisms with robust estimation techniques from signal processing and data analysis together with physics and statistics based models to counter these novel attacks in sensor networks. We believe that this Reputation-based Framework for Sensor Networks (RFSN) will provide a scalable, diverse and a generalized approach for countering all types of misbehavior resulting from malicious and faulty nodes. We are currently developing a system within this framework where we employ a Bayesian formulation, specifically a beta reputation system, for reputation representation, updates and integration. This framework has been implemented and rigorously tested in simulations as well as on Berkeley Motes. It is available as a middleware service under TinyOS and SOS environment.

Collaborators: Laura Balzano, M. B. Srivastava (NESL)

Trusted computing in sensor networks

Trusted computing is emerging as a promising approach to addressing security concerns in traditional computing systems (PCs, workstations, servers, etc). A critical component in this approach is a Trusted Platform Module (TPM), a hardware component that is added to the system in order to enable functions such as attestation, platform integrity measurement, reporting, and protected storage. In this work, we investigate how the concepts of trusted computing can be applied to sensor networks. In the sensor network domain, cost and size constraints make it difficult to equip each battery-powered sensor node with a TPM. Therefore, we explore a tiered network architecture wherein only a small number of sensor nodes are equipped with TPMs; the rest are not assumed to have any security hardware or tamper-resistance capabilities. Our current focus is on cryptographic key establishment, distribution, and management, which is an important foundation for many security protocols. We have developed a comprehensive, scalable, and energy-efficient framework for establishing symmetric cryptographic keys by leveraging the presence of trusted hardware at a few sensor nodes. The proposed scheme can generate unique secret keys between every node and a TPM equipped node, pairwise keys, as well as group keys shared by an arbitrary subset of nodes. It can also handle node mobility. Some important benefits of the TPM-based framework include: (i) high cryptographic strength of the generated keys, (ii) minimal pre deployment configuration, and (iii) limited consequences of nodes being physically compromised. We have implemented and evaluated the proposed protocol on a heterogeneous sensor network consisting of Stargates and Micaz motes. A public domain TPM emulator was ported to work on the Stargate platform in order to perform the TPM functions. We present results that demonstrate the feasibility and scalability of the proposed key establishment framework. We believe that this work is a first step towards addressing various problems in sensor network security through trusted computing.

Collaborators: Srivaths Ravi, Anand Raghunathan (NEC Labs America, Inc.)

Secure time synchronization service for sensor networks - Webpage

Existing solutions for time synchronization in sensor networks are not resilient to malicious behavior from external attackers or internally compromised nodes. We showcase the feasibility of a pulse-delay attack, whereby an attacker can introduce arbitrarily long delays in the packet propagation time directly affecting the achieved synchronization precision. We have proposed a suite of protocols for secure pairwise and group synchronization of nodes that lie in each other’s power ranges and of nodes that are separated by multiple hops. These protocols offer different points of operation in the energy-accuracy subspace and the choice of the specific protocol should be made by the network designer depending on his application needs. We believe that we have just scratched the surface in the solution space of secure time synchronization for sensor networks. In future, we plan to investigate secure network-wide synchronization schemes in the presence of multiple compromised nodes. In parallel, we are also developing better remedial actions against the malicious attacks than a simple abort of the protocol.

Collaborators: Srdjan Capkun (Technical University of Denmark), M. B. Srivastava (NESL)

Secure event reporting protocol for sense-response applications (SERP) - Webpage

Sense-response applications are widely being used for safeguarding critical infrastructure. In such applications, the sensor nodes detect and report events of interest to the base-station which promptly responds with a physical response. A concern that arises immediately is regarding the ability of the sensor nodes to encounter malicious entities that benefit from any form of damage to the critical infrastructure. Due to the lack of physical security and tamper resistant hardware around the sensor nodes, adversaries can easily compromise them, recover their embedded cryptographic material and subsequently make them pose as authorized nodes in the network. Such compromised nodes can now launch an attack on the network to either suppress the reporting of genuine events or inject false events to the base-station, thereby rendering the entire system useless. We have developed a Secure Event Reporting Protocol (SERP) for sense-response applications which ensures the generation and delivery of valid event reports in the presence of internal attacks launched by compromised nodes within the network. SERP exploits the redundancy and the mutual oversight within a group of nodes triggered by an event to generate an event report which is authenticated by a subset of these nodes. The protocol depends upon the presence of pair-wise cryptographic keys between two nodes detecting a common event. We also propose a scalable post-deployment mechanism for establishing these keys in the network. Our scheme exploits the Physical Attributes of the sensor nodes for Key Establishment and is referred to as PAKE. We have developed a prototype implementation of SERP and PAKE mechanisms for Mica2 motes and conducted several experiments to evaluate the overall system resiliency to attacks by internally compromised nodes. The obtained results show that SERP generates event report securely and efficiently.

Collaborators: Ramkumar Rengaswamy, Simon Han, M. B. Srivastava (NESL)

Time Synchronization for sensor networks

Rate-adaptive long-term time synchronization (RATS) - Webpage

Radio duty cycling has received significant attention in sensor networking literature, particularly in the form of protocols for medium access control and topology management. While many protocols have claimed to achieve significant duty-cycling benefits in theory and simulation, these benefits have often not translated to practice. The dominant factor that prevents the optimal usage of the radio in real deployment settings is time uncertainty between sensor nodes. This paper proposes an uncertainty-driven approach to duty-cycling where a model of long-term clock drift is used to minimize the duty-cycling overhead. First, we use long-term empirical measurements to evaluate and analyze in-depth the interplay between three key parameters that influence long-term synchronization rate, history of past synchronization beacons and the estimation scheme. Second, we use this measurement-based study to design a rate-adaptive, energy-efficient long-term time synchronization algorithm that can adapt to changing clock drift and environmental conditions while achieving application-specific precision with very high probability. Finally, we integrate our uncertainty-driven time synchronization scheme with a MAC layer protocol, BMAC, and empirically demonstrate one to two orders of magnitude reduction in the transmit energy consumption at a node with negligible impact on the packet loss rate.

Collaborators: Deepak Ganesan (Umass), Hohyun Sim, Vlassios Tsiatsis, M. B. Srivastava (NESL), D. Estrin, M. Hansen

Timing-sync protocol for sensor networks (TPSN)

The applications envisioned for wireless sensor networks require collaborative execution of a distributed task amongst a large set of sensor nodes. This is realized by exchanging messages that are time-stamped using the local clocks on the nodes. Therefore, time synchronization becomes an indispensable piece of infrastructure in such systems. For years, protocols such as NTP have kept the clocks of networked systems in perfect synchrony. However, this new class of networks has a large density of nodes and very limited energy resource at every node; this leads to scalability requirements while limiting the resources that can be used to achieve them. A new approach to time synchronization is needed for sensor networks. Timing-sync Protocol for Sensor Networks (TPSN) aims at providing network-wide time synchronization in a sensor network. The algorithm works in two steps. In the first step, a hierarchical structure is established in the network and then a pair wise synchronization is performed along the edges of this structure to establish a global timescale throughout the network. Eventually all nodes in the network synchronize their clocks to a reference node. We implement our algorithm on Berkeley motes and show that it can synchronize a pair of neighboring motes to an average accuracy of less than 20ms. We argue that TPSN roughly gives a 2x better performance as compared to Reference Broadcast Synchronization (RBS) and verify this by implementing RBS on motes. We also show the performance of TPSN over small multihop networks of motes and use simulations to verify its accuracy over large-scale networks.

Collaborators: Ramkumar Rengaswamy, M. B. Srivastava (NESL)

Cheating in CSMA/CA ad-hoc networks

CSMA/CA refers to the class of distributed MAC protocols that relies on random deferment of packet transmissions. As most other protocols, CSMA/CA was designed with the assumption that the nodes would play by the rules. This is important, since the nodes themselves have a control over their random deferment of packet transmissions. However, with the higher programmability of the network adapters, the temptation to tamper with the software or firmware is likely to grow; in this way, a user could obtain a larger share of the available bandwidth at the expense of other users. We use a game-theoretic approach to investigate the problem of selfish behavior of nodes, specifically geared towards the most widely accepted protocol in this class of protocols, IEEE 802.11. We will show that a selfish and non-cooperative behavior by a small population of cheaters (two or more) in the system results in disaster for them, eventually leading to a system collapse. We argue that this provides the incentive for cheaters to cooperate with each other. However, explicit cooperation among nodes is clearly impractical. By applying the model of repeated games from game theory, we are able to derive conditions for stable and optimal functioning of a population of cheaters. We use this insight to develop a simple, localized and distributed cheating protocol that needs no explicit cooperation between cheaters or a priori knowledge about the total number of nodes/cheaters in the system. We will show that the scheme successfully guides multiple selfish nodes in the system to reach a Pareto-optimal Nash equilibrium.

Collaborators: Mario Cagalj, Imad Aad, J. P. Hubaux (LCCA Labs, EPFL, Switzerland)

Topology Management

In wireless sensor networks, energy efficiency is crucial to achieve satisfactory network lifetime. In order to reduce the energy consumption of a node significantly, its radio needs to be turned off. We propose a new technique called Sparse Topology and Energy Management (STEM), which aggressively puts node to sleep. It provides a method to wake up nodes, where latency is traded off for energy savings. We have also proposed a hybrid scheme, which takes advantage of both setup latency and network density to increase the nodes lifetime.

Collaborators: Curt Schurgers (UCSD), Vlassios Tsiatsis, M. B. Srivastava (NESL)

Energy-efficient Scheduling

As embedded systems are being networked, often wirelessly, an increasingly larger share of their total energy budget is due to the communication. This necessitates the development of power management techniques that address communication subsystems, such as radios, as opposed to computation subsystems, such as embedded processors, to which most of the research effort thus far has been devoted. In this paper, we present techniques for energy efficient packet scheduling and fair queuing in wireless communication systems. Our techniques are based on an extensive slack management approach that dynamically adapts the output rate of the system in accordance with the input packet arrival rate. We use a recently proposed radio power management technique, Dynamic Modulation Scaling (DMS), as a control knob to enable energy-latency tradeoff during wireless packet transmission. We _rst analyze a single input stream scenario, and describe a rate adaptation technique that results in significantly lower energy consumption (reductions of up to 10X), while still bounding the resulting packet delays. By appropriately setting the various parameters of our algorithm, the system can be made to traverse the energy-latency-fidelity tradeoff space. We extend our techniques to a multiple input stream scenario, and present EEWFQ, an energy efficient version of the Weighted Fair Queuing (WFQ) algorithm for fair packet scheduling. Simulation results show that large energy savings can be obtained through the use of EEWFQ, with only a small, bounded increase in worst case packet latency. Further, our results demonstrate that EEWFQ does not adversely affect the throughput allocation (and hence, fairness) of WFQ.

Collaborators: Vijay Raghunathan (Purdue), Curt Schurgers (UCSD), M. B. Srivastava (NESL)

Self aware actuation

In Wireless Ad-hoc Sensor Networks (WASNs), energy efficiency is the key design challenge. Several factors in these networks like traffic characteristics and edge effects lead to situations where a certain segment of the network may become energy constrained before the remaining network. We argue that in this scenario, instead of rendering the complete network as useless, the remaining energy resources (sensor nodes) should reorganize to form a new functional topology in the network. The network, as a single entity, performs this self-aware actuation to increase its own performance. In this paper, we consider a network where nodes (or a subset of the nodes) are equipped with the facility of controlled mobility. The network uses mobility as an adaptive actuation facility to repair the coverage loss in the area being monitored by it. We present a completely distributed energy aware algorithm (referred to as Co-Fi) for coordinated coverage fidelity maintenance in sensor networks. The overheads of mobility are incorporated in the decision step, thus leaving no hidden costs. Our preliminary analysis shows that Co-Fi can significantly help improve the lifetime of these networks.

Collaborators: Aman Kansal, M. B. Srivastava (NESL)

Spatial Aggregation

A key aspect that makes wireless ad-hoc sensor networks different from traditional networks is their strong link to the physical world. We develop this perspective by studying an interesting class of sensor network applications called aggregation applications. We argue that when a user queries for a specific aggregates like average etc., he is interested in knowing the statistics of the underlying physical process. We introduce a distinction between aggregates calculated over a region and aggregates calculated over a discrete set of nodes and classify them as spatial and nodal aggregates respectively. We illustrate this distinction by specifically studying two aggregate functions – average and histogram. For a continuous physical process and a random deployment of sensor nodes, which are a norm for sensor networks, the conventional approach of doing nodal aggregation produces inaccurate results. We use a voronoi-based approach to propose an algorithm for calculating spatial aggregates in sensor networks. The algorithm can work in two modes – centralized and distributed. The energy and accuracy tradeoff associated with each of the two versions is analyzed in detail. The efficacy of the proposed algorithm is tested over a wide variety of physical processes including real precipitation data of South America acquired over a span of past 50 years. We will show that our algorithm gives a 2-4 times performance gain as compared to the conventional approach of doing nodal aggregation. We have implemented our algorithm on Berkeley motes. Our first prototype implementation termed as Voronoi Interpolated Spatial Aggregation (VISA) can be easily integrated with available frameworks for doing aggregation over a network of motes. Although not 100% accurate, our approach is a simple, efficient and a practical solution for calculating spatial aggregates in sensor networks.

Collaborators: Simon Han, M. B. Srivastava (NESL)

Distributed Estimation Approach to Periodic Aggregation

Wireless ad hoc sensor networks (WASNs) are in need of the study of useful applications that will help the researchers view them as a distributed physically-coupled collective that estimates the physical environment, and not just energy -limited ad hoc networks. We develop this perspective using a large and interesting class of WASN applications called aggregation applications. In particular, we consider the challenging periodic aggregation problem where the WASN provides the user with periodic estimates of the environment, as opposed to simpler and previously studied snapshot aggregation problems. In periodic aggregation our approach allows the spatio-temporal correlation among values sensed at the various nodes to be exploited towards energy –efficient estimation of the aggregated value of interest. Our approach also creates a system level energy vs. accuracy knob whereby the more the estimation error that the user can tolerate, the less is the energy consumed. We present the Intrinsically Distributed Estimation Algorithm (IDEA) that can be applied to a sub-class of the aggregation problems. IDEA, apart from being more flexible in the energy -accuracy subspace and more robust, can also bring considerable energy savings for a typical accuracy requirement (three-fold decrease in energy consumption for 5% estimation error) compared to repeated snapshot aggregation. IDEA is tested against a wide variety of physical process scenarios in order to reveal its system-level propert ies and possible failing points.

Collaborators: A. Boulis, M. B. Srivastava (NESL)

Multidimensional Design Perspective for Sensor Networks

With the growing interest in wireless sensor networks, techniques for their systematic analysis design and optimization are essential. Despite numerous research efforts in optimizing hardware, algorithms and protocols for these networks, it remains largely unexplored how these innovations can be all tied together to design a sensor network for a specific practical application. We propose a methodology that starts from four independent quality of service (QoS) parameters and allows the user to completely and unambiguously describe the desired performance, without having to deal with the details of individual devices or protocols. By making appropriate choices in terms of device capabilities and run-time techniques, a design can be positioned in this four dimensional QoS space. Furthermore, we describe a technique to explore the associated tradeoffs at design time, using both analytical expressions and simulations. To illustrate the benefits of our approach, a design example is worked out, which shows a five fold improvement in network operational lifetime by adapting the event reporting delay.

Collaborators: S. Adlakha, M. B. Srivastava (NESL)