Suman Nath

Exploiting Redundancy for Robust Sensing Degree Type: Ph.D. in Computer Science
Advisor(s): Srinivasan Seshan
Graduated: May 2005

Abstract:

In this thesis, we explore the challenges in making an Internet-scale heterogeneous sensing system more robust. We target end-to-end robustness in that we address failures in collecting data from a large collection of wired and wireless sensors, and problems in making sensor readings available to end-users from storage on Internet-connected nodes. Although often overlooked, robustness is extremely crucial for such systems because they are often deployed in harsh environments and are not typically very well-maintained. Traditional robustness techniques generally involve tradeoffs between robustness and resource-efficiency; i.e., they mask failures by using additional resources (e.g., energy, storage). Unfortunately, these traditional tradeoffs are not well suited to resource constraints and large scales of typical sensing systems.

This dissertation puts forth the claim that more practical solutions can be developed by exploiting several unique deployment- and application-specific properties of typical sensing systems. We show that by slightly relaxing the requirements of exact or fresh answers, we can significantly improve the robustness of a system, without additional resource overheads. We argue that this approach is well suited to sensing systems since optimizing resource usage is one of the important goals of their designs and the applications can often tolerate approximate or slightly stale data. We support the above claim by proposing efficient solutions for robust data collection and storage in a sensing system.

For robust collection of data from wireless sensors, we present Synopsis Diffusion, a novel data aggregation scheme that exploits wireless sensors broadcast communication and sensing applications tolerance for approximate aggregate answers. Synopsis Diffusion, unlike previous schemes, decouples aggregation algorithms from underlying aggregation topologies, enabling highly robust aggregation with energy-efficient multipath routing. We also present Tributary-Delta, a novel adaptive aggregation scheme that efficiently combines the benefits of existing schemes and uses application-aware adaptation to cope with the dynamics of deployment environments. Under typical loss rates, our techniques can provide five times more accurate results than existing energy-efficient schemes, without additional energy overhead.

Thesis Committee:
Srinivasan Seshan (Chair)
Phillip B. Gibbons
M. Satyanarayanan
Deborah Estrin (University of California, Los Angeles)

Jeannette Wing, Head, Computer Science Department
Randy Bryant, Dean, School of Computer Science

Keywords:
Sensor networks, wide-area sensing, query processing, robustness and availability, resource-efficient algorithms