Graduate Seminar on Sensor Actuator Networks
CS294-11/CS298-41, Fall 2005

Announcements

• Poster Session: Tue, December 13, 11:30AM - 1:00PM, Soda Hall 6th Floor.
• 12/03/2005: Term project papers are due at 6:00 AM on Monday, December 19, 2005. Late papers will not be accepted. Please:
  1. Post the paper to the project homepage you provided earlier (linked below) and
  2. E-mail a copy to the following people: prabal@cs, davidchu@cs, hellerstein@cs, and culler@cs.
  If you're new to paper writing, the following links (culled from David Wagner's excellent course project pages) may be helpful:
  1. Advice on Research and Writing
  2. Writing Technical Articles
  3. Armando Fox's Advice
• 11/20/2005: For people registered in the CS294-11 class, we're going to have each team give a brief (< 5 minutes) project status on Tuesday, November 29, 2005. Please prepare three slides with the following information:
  1. Motivation and Problem Formulation
  2. Key Ideas of Your Solution
  3. Current Status and Future Plans
• 10/04/2005: CS294-11 Assignment 1 (due 10/18):
  (1) Create a project homepage with title and group members
  (2) Prepare a 1-page project proposal accessible from the project page
  (3) E-mail prabal@cs and davidchu@cs a link to the project page
  You may work individually or in a group of 2-3 students as long as at most two students are enrolled in the CS294-11 class. Potential project topics are available or you can pick your own. Feel free to talk with any of the course organizers about your project ideas.
• 09/29/2005: Naveen Sastry will be speaking about sensor network security on Nov 17. Only two more open days -- so e-mail us quickly if you've got a topic you want to cover!
• 09/23/2005: We have a few open days on the calendar (Nov 17, 22, and 29). The topics under consideration include: abstractions, actuation, architectures, design techniques, localization, security, signal processing, testbeds, time synchronization, tools, tracking, or Sensys'05 papers. Please e-mail me (prabal@cs) if you feel strongly about one of these topics or have some other ideas you would like to suggest.
• 09/18/2005: Added instructions for getting on the class mailing list.
• 09/01/2005: First meeting on Thu, Sep. 8, 2005

Course Overview

Wireless sensor actuator networks ("sensornets") represent a new computing class consisting of large numbers of nodes which are often embedded in their operating environments, distributed over wide geographical areas, or located in remote and largely inaccessible regions. The nodes themselves range from tiny, resource-constrained devices called motes to PDA-class computing devices that are capable of sensing, computation, communication, and actuation. Sensornets allow us to instrument, observe, and respond to the physical world on scales of space and time previously impossible.

The emergence of this new computing class raises many system design challenges since sensornets are closely coupled to the physical world with all its unpredictable variation, noise, and asynchrony; they involve many energy-constrained, resource-limited devices operating in concert; they must be largely self-organizing and self-maintaining; and they must be robust despite significant noise, loss, and failure. This area has reached a stage where solid initial platforms have been developed, a number of "leading applications" have been fielded, and a rich body of literature has emerged.

The course will cover one topic each week and will be structured as a combination between a speaker series and a discussion seminar. Each topic will be presented by a speaker selected from within or outside of Berkeley. Except for a very few topics, neither the instructors nor the assistants will be the speakers. Topics may include application-driven network architectures, emerging sensor/actuator/mobile platforms and technology, sensing and communications technology, resource constrained design techniques, media access control, network algorithms, time synchronization, ranging, localization, tracking, acquisitional query processing, in-network aggregation, signal processing, systems management, and other topics based on the interests of the class.

The course can be taken pass/fail as CS298-41, which requires that students attend and participate (i.e. submit questions) in the weekly guest lectures (Thursdays). The course also can be taken for a grade as CS294-11, which requires that students (1) attend and participate in weekly guest lectures (Thursdays), (2) lead one or more of the discussions (Tuesdays), and (3) do a research project/paper or write an in-depth survey paper about a topic.

We expect the participants will be varied across discipline (CS, EE, ME), stage of study (first-year grads, Ph.D. candidates, post docs and perhaps some faculty), and degree of involvement (taking the class for a grade, as pass/fail, or just sitting in occasionally).

Projects

• Chris Baker, Daekyeong Moon, Jorge Ortiz: A Location Service for BVR [Status]
• Jeremy Schiff, Dominic Antonelli: StatSense: Abstractions for Implementing Statistical Models in Sensor Networks [Status]
• Prasanth Jeevan: StatSense: Abstractions for Implementing Statistical Models in Sensor Networks [Status]
• Jay Taneja, Arsalan Tavakoli: Implementing a Narrow Waist Abstraction for Sensornets [Status]
• Xiofan Jiang: Simultaneous Transmissions Using the Capture Effect [Status]
• Russell Sears, Murali Rangan: Reliable, eventual data collection in wireless sensor networks [Status]

Schedule

Class	Date	Topic	Speaker	Readings
1 - Lecture	Sep 8	Introduction NESTFE Overview (18.4MB) Deluge, Drip, Drain, Nucleus (3.6MB) Detection, Tracking, Pursuit-Evasion (8.07MB)	J. Hellerstein P. Dutta G. Tolle B. Sinopoli, S. Oh, P. Chen	None
2 - Discussion	Sep 13	Research Drivers: Apps and Computer Science Issues (4.4MB)	Prabal Dutta	[SR05], [New], [Wei93], [ECPS02]
3 - Lecture	Sep 15	Research Drivers: Localization (16.5MB)	Kamin Whitehouse	[WKW+05]
4 - Discussion	Sep 20	Applications: Habitat (9.8MB), Shooter (4.2MB), VigilNet (15.8MB)	Prabal Dutta	[SMP+04], [SML+04], [HKS+05]
5 - Lecture	Sep 22	Application: A Macroscope in the Redwoods (38.9MB) [Abstract]	David Culler	[TPS+05]
6 - Discussion	Sep 27	Platforms: Mica (285KB), ZebraNet (618KB), Prometheus (3.01MB)	A. Tavakoli, J. Taneja, X. Jiang	[HC02], [ZSL+04], [JPC05]
7 - Lecture	Sep 29	Platforms: Telos/Tmote Sky (4.22MB), eXtreme Scale Mote/Trio (2.84MB)	J. Polastre (Moteiv), P. Dutta	[PSC05], [DGA+05]
8 - Discussion	Oct 4	Operating Systems: Contiki (487KB), SOS (2.03MB), MANTIS (457KB)	J. Schiff, J. Ortiz, M. Rangan	[DGV04], [HRS+05], [BCD+05]
9 - Lecture	Oct 6	Operating Systems: TinyOS 2.0	Phil Levis (Stanford)	[LMG+04], [GLC05]
10 - Discussion	Oct 11	Databases: TinyDB/TAG (1.9MB), Synopsis Diffusion (17.3MB), BBQ (3.7MB)	David Chu	[MFH+02], [NGS+04], [DGM+04]
11 - Lecture	Oct 13	Databases: Design Considerations for High Fan-In Systems (23.0MB) [Abstract]	Shawn Jeffrey	[FJK+05]
12 - Discussion	Oct 18	Networking: S-MAC (765KB), 802.15.4 (302KB), B-MAC (163KB)	P. Jeevan, A. Tavakoli, M. Rangan	[YHE02], [CGH+02], [PHC04]
13 - Lecture	Oct 20	Networking: SP: A Unifying Link Abstraction (3.98MB) [Abstract]	Joe Polastre (Moteiv)	[CDE+05]
14 - Lecture	Oct 25	Networking: Collection (2.19MB), Dissemination (20MB) [Notes], Any-to-Any	P. Dutta, R. Sears, R. Fonseca	[WTC03], [LPC+04], [FRZ+05]
15 - Lecture	Oct 27	Programming: An Environmentally Immersive Approach (1.1MB) [Abstract]	Tarek Abdelzaher (UIUC)	[LAH+05]
16 - Lecture	Nov 1	Programming: Models and Languages (5.64MB) [Abstract]	David Gay (Intel Research)	[LGC+05], Reread: [LMG+04], Opt: [GLB+03]
No class	Nov 3	Sensys'05 -- No Class
17 - Lecture	Nov 8	Sensor Placement [Abstract]	Carlos Guestrin (CMU)	[GKS+05]
18 - Lecture	Nov 10	Probabilistic Querying and Altering (36.3MB)	Joe Hellerstein	None
19 - Lecture	Nov 15	Value of Information and Sensornet Tasking.	Feng Zhao (MSR)	None
20 - Lecture	Nov 17	A Critical Look at Sensor Network Security (463KB) [Abstract]	Naveen Sastry	[KW03]
21 - Discussion	Nov 22	Networking: 802.15.4: Enabling Pervasive Wireless Sensor Networks (3.4MB) [Abstract]	Jose Gutierrez (Eaton)	Reread: [CGH+02], Skim: [ZigBee Spec]
No Class	Nov 24	Thanksgiving -- No Class
22 - Discussion	Nov 29	Signals: Processing, Coding	Prasant Jeevan, Alex Dimakis	[GJV+05], [DPR05]
23 - Lecture	Dec 1	PRESTO: A Predictive Storage Architecture for Sensor Networks [Abstract]	Deepak Ganesan (UMass)	[DGS+05], [DGL+05]
24 - Lecture	Dec 6	Cancelled	Cancelled	None
25 - Lecture	Dec 8	Geographic Routing in Sensor Networks [Abstract]	Ramesh Govindan (USC)	[KGKS05b], [KGKS05]
26 - Posters	Dec 13	Poster Session -- Soda Hall 6th Floor	Students & Faculty	None
27 - Lecture	Dec 15	Data Management for Next Generation Wireless Sensor Networks [Abstract]	Samuel Madden (MIT)	[GM04]

Readings

Research Drivers

1. [SR05]
   Richard Sharp and Kasim Rehman
   What Makes Good Application-Led Research?
   IEEE Pervasive Computing, pp. 80-82, July-September 2005.

2. [New]
   Allen Newell
   Allen Newell's Research Style
   Timeless...

3. [Wei93]
   Mark Weiser
   Some Computer Science Issues in Ubiquitous Computing
   Communications of the ACM, Vol. 36, No. 7 (July 1993), pp. 74-83

4. [ECPS02]
   D. Estrin, D. Culler, K. Pister, G. Sukhatme,
   Connecting the Physical World with Pervasive Networks
   IEEE Pervasive Computing, pp. 59-69, January-March 2002.

Applications

1. [SMP+04]
   Robert Szewczyk, Alan Mainwaring, Joseph Polastre, David Culler,
   An Analysis of a Large Scale Habitat Monitoring Application
   In Proceedings of the Second ACM Conference on Embedded Networked Sensor Systems (SenSys), November 3-5, 2004.

2. [SML+04]
   Gyula Simon, Miklos Maroti, Akos Ledeczi, Gyorgy Balogh, Branislav Kusy, Andras Nadas, Gabor Pap, Janos Sallai, and Ken Frampton,
   Sensor Network-Based Countersniper System
   In Proceedings of the Second ACM Conference on Embedded Networked Sensor Systems (SenSys), November 3-5, 2004.

3. [HKS+05]
   T. He, S. Krishnamurthy, J. A. Stankovic, et al.,
   Vigilnet: An Integrated Sensor Network System for Energy-Efficient Surveillance
   ACM Transactions on Sensor Networks, 2005.

4. [TPS+05]
   Gilman Tolle, Joseph Polastre, Robert Szewczyk, Neil Turner, Kevin Tu, Phil Buonadonna, Stephen Burgess, David Gay, Wei Hong, Todd Dawson, and David Culler,
   A Macroscope in the Redwoods
   In Proceedings of the Third ACM Conference on Embedded Networked Sensor Systems (SenSys), November 2-4, 2005 (To appear).

Platforms

1. [HC02]
   Jason Hill and David Culler,
   Mica: A Wireless Platform for Deeply Embedded Networks
   IEEE Micro., vol 22(6), Nov/Dec 2002, pp 12-24.

2. [ZSL+04]
   Pei Zhang, Christopher M. Sadler, Stephen A. Lyon, and Margaret Martonosi
   Hardware Design Experiences in ZebraNet
   In Proceedings of the Second ACM Conference on Embedded Networked Sensor Systems (SenSys), November 3-5, 2004.

3. [JPC05]
   Xiaofan Jiang, Joseph Polastre, David Culler,
   Perpetual Environmentally Powered Sensor Networks
   In Proceedings of the Fourth International Conference on Information Processing in Sensor Networks: Special track on Platform Tools and Design Methods for Network Embedded Sensors (IPSN/SPOTS), April 25-27, 2005

4. [PSC05]
   Joseph Polastre, Robert Szewczyk, David Culler,
   Telos: Enabling Ultra-Low Power Wireless Research
   In Proceedings of the Fourth International Conference on Information Processing in Sensor Networks: Special track on Platform Tools and Design Methods for Network Embedded Sensors (IPSN/SPOTS), April 25-27, 2005

5. [DGA+05]
   Prabal Dutta, Mike Grimmer, Anish Arora, Steven Bibyk, David Culler,
   Design of a Wireless Sensor Network Platform for Detecting Rare, Random, and Ephemeral Events
   In Proceedings of the Fourth International Conference on Information Processing in Sensor Networks: Special track on Platform Tools and Design Methods for Network Embedded Sensors (IPSN/SPOTS), April 25-27, 2005

Operating Systems

1. [DGV04]
   Adam Dunkels, Bjorn Gronvall, Thiemo Voigt,
   Contiki - A Lightweight and Flexible Operating System for Tiny Networked Sensors,
   Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks (LCN'04), p.455-462, November 16-18, 2004.

2. [HRS+05]
   Chih-Chieh Han, Ram Kumar Rengaswamy, Roy Shea, Eddie Kohler and Mani Srivastava,
   SOS: A dynamic operating system for sensor networks,
   Proceedings of the Third International Conference on Mobile Systems, Applications, And Services (Mobisys), 2005.

3. [BCD+05]
   S. Bhatti, J. Carlson, H. Dai, J. Deng, J. Rose, A. Sheth, B. Shucker, C. Gruenwald, A. Torgerson, R. Han,
   MANTIS OS: An Embedded Multithreaded Operating System for Wireless Micro Sensor Platforms,
   ACM/Kluwer Mobile Networks & Applications (MONET), Special Issue on Wireless Sensor Networks, vol. 10, no. 4, August 2005, P. Ramanathan, R. Govindan and K. Sivalingam Eds., pp. 563-579.

4. [LMG+04]
   Philip Levis, Sam Madden, David Gay, Joe Polastre, Robert Szewczyk, Alec Woo, Eric Brewer and David Culler,
   The Emergence of Networking Abstractions and Techniques in TinyOS,
   In Proceedings of the First USENIX/ACM Symposium on Networked Systems Design and Implementation (NSDI 2004).

5. [GLC05]
   David Gay, Philip Levis, and David Culler,
   Software Design Patterns for TinyOS,
   To appear in Proceedings of the ACM SIGPLAN/SIGBED 2005 Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES'05).

Databases, Data Management, Aggregation

1. [MFH+02]
   Samuel Madden, Michael Franklin, Joseph Hellerstein, and Wei Hong
   TAG: a Tiny AGgregation Service for Ad-Hoc Sensor Networks,
   In Proceedings of OSDI, 2002.

2. [NGS+04]
   Suman Nath, Phillip B. Gibbons, Srinivasan Seshan, and Zachary Anderson,
   Synopsis Diffusion for Robust Aggregation in Sensor Networks,
   ACM SenSys 2004.

3. [DGM+04]
   Amol Deshpande, Carlos Guestrin, Samuel Madden, Joseph Hellerstein, and Wei Hong,
   Model Driven Data Acquisition in Sensor Networks,
   In Proceedings of VLDB, 2004.

4. [FJK+05]
   Michael J. Franklin, Shawn R. Jeffery, Sailesh Krishnamurthy, Fredrick Reiss, Shariq Rizvi, Eugene Wu, Owen Cooper, Anil Edakkunni, and Wei Hong,
   Design Considerations for High Fan-In Systems: The HiFi Approach,
   CIDR 2005

5. [GM04]
   Johannes Gehrke and Samuel Madden,
   Query Processing in Sensor Networks,
   In Pervasive Computing, 2004

Networking & Datalink Control

1. [YHE02]
   Wei Ye, John Heidemann, and Deborah Estrin,
   An Energy-Efficient MAC Protocol for Wireless Sensor Networks,
   In Proceedings of the 21st International Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2002), New York, NY, USA, June, 2002.

2. [CGH+02]
   Callaway, E.; Gorday, P.; Hester, L.; Gutierrez, J.A.; Naeve, M.; Heile, B.; Bahl, V.,
   Home networking with IEEE 802.15.4: a developing standard for low-rate wireless personal area networks,
   IEEE Communications Magazine, Volume 40, Issue 8, Page(s):70 - 77, Aug. 2002.

3. [WTC03]
   Alec Woo, Terence Tong, and David Culler,
   Taming the Underlying Challenges of Reliable Multhop Routing in Sensor Networks,
   ACM SenSys 2003.

4. [LPC+04]
   Philip Levis, Neil Patel, David Culler, and Scott Shenker,
   Trickle: A Self-Regulating Algorithm for Code Propagation and Maintenance in Wireless Sensor Networks,
   In Proceedings of the First USENIX/ACM Symposium on Networked Systems Design and Implementation (NSDI 2004).

5. [FRZ+05]
   Rodrigo Fonseca, Sylvia Ratnasamy, Jerry Zhao, Cheng Tien Ee, David Culler, Scott Shenker, and Ion Stoica,
   Beacon Vector Routing: Scalable Point-to-Point Routing in Wireless Sensornets,
   In Proceedings of the First USENIX/ACM Symposium on Networked Systems Design and Implementation (NSDI 2005).

6. [PHC04]
   Joseph Polastre, Jason Hill, David Culler,
   Versatile Low Power Media Access for Wireless Sensor Networks,
   In Proceedings of the Second ACM Conference on Embedded Networked Sensor Systems (SenSys), November 3-5, 2004.

7. [PHL+05]
   Joseph Polastre, Jonathan Hui, Philip Levis, Jerry Zhao, David Culler, Scott Shenker, and Ion Stoica,
   A Unifying Link Abstraction for Wireless Sensor Networks,
   To appear in the Third ACM Conference on Embedded Networked Sensor Systems (SenSys), November 2-4, 2005.

8. [HJB+04]
   Bret Hull, Kyle Jamieson and Hari Balakrishnan,
   Mitigating Congestion in Wireless Sensor Networks
   ACM SenSys 2004, November 2-4, 2005.

9. [KGKS05]
   Young-Jin Kim, Ramesh Govindan, Brad Karp, and Scott Shenker,
   Geographic Routing Made Practical
   In Proceedings of the Second USENIX/ACM Symposium on Networked Systems Design and Implementation (NSDI 2005). Boston, MA. May, 2004.

10. [KGKS05b]
    Young-Jin Kim, Ramesh Govindan, Brad Karp, and Scott Shenker,
    On the Pitfalls of Geographic Face Routing
    Proceedings of the Third ACM/SIGMOBILE International Workshop on Foundations of Mobile Computing, September, 2005.

Architectures, Abstractions, and Programming Models

1. [CDE+05]
   David Culler, Prabal Dutta, C. T. Ee, Rodrigo Fonseca, Jonathan Hui, Philip Levis, Joseph Polastre, Scott Shenker, Ion Stoica, Gilman Tolle, Jerry Zhao,
   Towards a Sensor Network Architecture: Lowering the Waistline,
   In Proceedings of HotOS X: Tenth Workshop on Hot Topics in Operating Systems, June 12-15, 2005.

2. [HPH+05]
   Vlado Handziski, Joseph Polastre, Jan-Hinrich Hauer, Cory Sharp, Adam Wolisz, David Culler,
   Flexible Hardware Abstraction for Wireless Sensor Networks,
   In Proceedings of the Second European Workshop on Wireless Sensor Networks (EWSN '05), January 31-February 2, 2005

3. [LMG+04]
   Philip Levis, Sam Madden, David Gay, Joseph Polastre, Robert Szewczyk, Alec Woo, Eric Brewer, David Culler,
   The Emergence of Networking Abstractions and Techniques in TinyOS,
   In Proceedings of the First USENIX/ACM Symposium on Networked Systems Design and Implementation (NSDI 2004). San Francisco, CA. March 29-31, 2004.

4. [LGC+05]
   Philip Levis, David Gay, and David Culler,
   Active Sensor Networks,
   Proceedings of the Second USENIX/ACM Symposium on Networked Systems Design and Implementation (NSDI 2005).

5. [GLB+03]
   David Gay, Philip Levis, Robert von Behren, Matt Welsh, Eric Brewer, and David Culler,
   The nesC Language: A Holistic Approach to Network Embedded Systems,
   In Proceedings of the ACM SIGPLAN 2003 Conference on Programming Language Design and Implementation (PLDI), 2003.

6. [LAH+05]
   Liquin Luo, Tarek Abdelzaher, Tian He, John Stankovic
   EnviroSuite: An Environmentally Immersive Programming Framework for Sensor Networks,
   

Security

1. [KW03]
   Chris Karlof and David Wagner,
   Secure Routing in Wireless Sensor Networks: Attacks and Countermeasures,
   Elsevier's AdHoc Networks Journal, Special Issue on Sensor Network Applications and Protocols, Volume 1, Issues 2-3, pages 293-315, September 2003

Localization

1. [WKW+05]
   Kamin Whitehouse, Chris Karlof, Alec Woo, Fred Jiang, David Culler,
   The Effects of Ranging Noise on Multihop Localization: an Empirical Study,
   The Fourth International Conference on Information Processing in Sensor Networks (IPSN '05), Los Angeles, California, April 25-27, 2005

Storage

1. [DGL+05]
   Peter Desnoyers, Deepak Ganesan, Huan Li, Ming Li and Prashant Shenoy,
   PRESTO: A Predictive Storage Architecture for Sensor Networks,
   Tenth Workshop on Hot Topics in Operating Systems (HotOS X), Santa Fe, New Mexico, June 2005.

2. [DGS+05]
   Peter Desnoyers, Deepak Ganesan and Prashant Shenoy,
   TSAR: A Two Tier Storage Architecture Using Interval Skip Graphs,
   Third ACM Conference on Embedded Networked Sensor Systems (SenSys), 2005

Sensing, Signal Processing, and Coding

1. [GKS+05]
   Carlos Guestrin, Andreas Krause, Ajit Paul Singh,
   Near-Optimal Sensor Placement in Gaussian Processes,
   In the 22nd International Conference on Machine Learning (ICML 2005), Bonn, August 2005.

2. [GJV+05]
   Lin Gu, Dong Jia, Pascal Vicaire, et al.,
   Lightweight Detection and Classification for Wireless Sensor Networks in Realistic Environments,
   In Proceedings of the Third ACM Conference on Embedded Networked Sensor Systems (SenSys), November 2-4, 2005 (To appear).

3. [DPR05]
   Alexandros G. Dimakis, Vinod Prabhakaran, and Kannan Ramachandran,
   Ubiquitous Access to Distributed Data in Large-Scale Sensor Networks through Decentralized Erasure Codes,
   In Proceedings of the Fourth International Conference on Information Processing in Sensor Networks (IPSN'05), April 25-27, 2005

Miscellaneous