Abstracts for David E. Culler

The EECS Research Summary for 2003


Evaluation of Efficient Link Reliability Estimators for Low-Power Wireless Networks

Alec Woo
(Professor David E. Culler)
(DARPA) NEST F33615-01-C-1895 and Intel Research Laboratory, Berkeley

Real-time wireless link reliability estimation is a fundamental building block for self-organization of multihop sensor networks. Observed connectivity at low power is more chaotic and unpredictable than in wireless LANs, and available resources are severely constrained. We seek estimators that react quickly to large changes, yet are stable, have a small memory footprint, and are simple to compute. We create a simple model that generates link loss characteristics similar to empirical traces collected under different contexts. With this model, we simulate a variety of estimators, and use the simple exponentially weighted moving average (EWMA) estimator as a basis for comparison. We find that recently proposed flip-flop estimators are not superior, however, our cascaded EWMA on windowed averaging is very effective.


More information (http://webs.cs.berkeley.edu) or

Send mail to the author : (awoo@eecs.berkeley.edu)

Multihop Routing in Sensor Networks

Alec Woo
(Professor David E. Culler)
(DARPA) NEST F33615-01-C-1895 and Intel Research Laboratory, Berkeley

Motivated by our technical report on the subject of empirical study of epidemic algorithms in large scale multihop networks, we have pursued the idea of neighborhood discovery based on passive link quality estimations, and the use of such information to analyze different distributed algorithms to perform routing tree construction. One interesting routing algorithm we have developed seeks to obtain the maximum reliable routing path from each node to the base station in a distributed manner based on local link quality estimations. Initial results from static analysis to low level simulations in TOSSIM were promising and motivate us for further investigation against different distributed routing algorithms such as naÔve broadcast based routing, and shortest path routing over reliable neighbors. Lacking a visually rich simulator, we adopted Vanderbiltís Matlab simulator for TinyOS (Prowler) and enhanced it with features that allow detail study of routing algorithms and GUI support to visualize the routing tree evolution. To capture a more realistic model of the radio channel for the simulator, we perform new empirical experiments on the new MICA platform to create a probabilistic model for the radio channel and packet collision. Current results of this work were presented at the Berkeley NEST retreat, Intel Berkeley Research Lab, and NEST PI meeting.


More information (http://webs.cs.berkeley.edu) or

Send mail to the author : (awoo@eecs.berkeley.edu)

Next Generation Highly Integrated Wireless Sensor Network Platform

Jason Hill
(Professor David E. Culler)
(DARPA - NEST) F33615-01-C-1895

Emerging low-power, embedded wireless sensor devices are targeting a wide range of applications, yet have very limited processing, storage, and energy resources. An architecture must be developed that can efficiently meet system demands while simultaneously remaining flexible to application specific optimizations. To answer the demands of application specific operations, we are building an integrated CMOS version of the Berkeley motes wireless sensor platform. A prototype chip that included CPU, ADC, communication accelerators, and memory was designed and fabricated by National Semiconductor as shown in Figures 1 and 2. Measuring just 2 mm x 2 mm, it represents a significant reduction is size, cost, and power over current generation motes. The test chip was not fully functional, but it could successfully execute instructions and demonstrate basic I/O capabilities. A second generation of this node has been designed and is currently being fabricated. In addition to fixing the minor bugs in the first prototype, this second generation chip includes support for multiple register sets, data encryption, and it is equipped with a CMOS RF transmitter. The transmitter architecture uses a 32 Khz crystal as a reference oscillator and frequency lock for a capacitor array based VCO to a 900 Mhz transmission frequency.


Figure 1: TinyOS network stack accelerator

Figure 2: Floorplan for the mote chip

More information (http://webs.cs.berkeley.edu) or

Send mail to the author : (jhill@eecs.berkeley.edu)

Wireless Sensor Networks for Habitat Monitoring

Joseph Polastre, Robert Szewczyk, and Alan Mainwaring1
(Professor David E. Culler)
(DARPA) NEST F33615-01-C-1895 and Intel Research Laboratory, Berkeley

The ability to use wireless sensor networks to monitor habitats on the scale of the organism can provide higher resolution data and profound results for scientists. In order to study the feasibility of deploying wireless sensor networks for habitat monitoring and retreiving useful data, we performed an in-depth study of real-world habitat monitoring on Great Duck Island, Maine. We developed a set of system design requirements that cover the hardware design of the nodes, the design of the sensor network, and the capabilities for remote data access and management. A serious concern is sensor node power management. Scientists need to be able to collect data for an entire breeding season without replacing batteries or disrupting the animals in their natural habitat. By evaluating the power consumption of all aspects of the node during operation, we designed a strict power budget and management scheme. We designed a system architecture to address general habitat monitoring requirements and deployed an instance of the architecture for monitoring seabird nesting. The currently deployed network consists of 32 nodes on a small island off the coast of Maine streaming useful live data onto the web. The application-driven exercise serves to focus our efforts for further work in data sampling, communications, network retasking, and health monitoring in the field of wireless sensor networks. We are developing other operating system services including power management, watchdog functionality, and time synchronization.


Figure 1: The system architecture for habitat monitoring applications

Figure 2: The Mica wireless sensor node with the Mica weather board developed for environmental monitoring applications

[1]
A. Mainwaring, J. Polastre, R. Szewczyk, D. Culler, and J. Anderson, "Wireless Sensor Networks for Habitat Monitoring," ACM Int. Workshop on Wireless Sensor Networks and Applications, Atlanta GA, September 2002.
1Researcher, Intel Research Laboratory, Berkeley

More information (http://www.greatduckisland.net) or

Send mail to the author : (polastre@eecs.berkeley.edu)

Mate: A Tiny Virtual Machine for Sensor Networks

Philip Levis
(Professor David E. Culler)
(DARPA) F33615-01-C-1895 , (DARPA) N6601-99-2-8913, Intel Corporation, (NSF) 0122599, and (NSF) EIA-9802069

Composed of tens of thousands of tiny devices with very limited resources (motes), sensor networks are subject to novel systems problems and constraints. The large number of motes in a sensor network means that there will often be some failing nodes; networks must be easy to repopulate. Often there is no feasible method to recharge motes, so energy is a precious resource. Once deployed, a network must be reprogrammable although physically unreachable, and this reprogramming can have a significant energy cost.

We have developed Mate, a tiny communication-centric virtual machine designed for sensor networks. Mate's high-level interface allows complex programs to be very short (under 100 bytes), reducing the energy cost of transmitting new programs. Code is broken up into small capsules of 24 instructions, which can self-replicate through the network. Packet sending and reception capsules enable the deployment of ad-hoc routing and data aggregation algorithms. Mate's concise, high-level program representation simplifies programming and allows large networks to be frequently reprogrammed in an energy-efficient manner; in addition, its safe execution environment suggests a use of virtual machines to provide the user/kernel boundary on motes that have no hardware protection mechanisms.

[1]
P. Levis and D. Culler, "Mate: A Virtual Machine for Tiny Networked Sensors," Proc. ACM Conf. Architectural Support for Programming Languages and Operating Systems, San Jose, CA, October 2002.

More information (http://www.eecs.berkeley.edu/~pal) or

Send mail to the author : (pal@eecs.berkeley.edu)