Electrical Engineering Department, Yale University

EENG 460a / CPSC 436a / ENAS 960 Networked Embedded Systems and Sensor Networks - Fall 2004

Left: XYZ Sensor Node Right: Sensor Enabled XYZ Sensor Nodes

This course is an introduction to fundamental concepts of networked embedded systems and wireless sensor networks. It is intended for seniors and first year graduate students in Electrical Engineering, Computer Science and other engineering majors with the prerequisite background. Covered topics include: embedded systems programming concepts, low power and power aware design, radio technologies, communication protocols for ubiquitous computing systems, and some of the mathematical foundation of sensor behavior. Laboratory work consists of a set of programming assignments that consider a set of the issues described in class. Prerequisites: Senior or Graduate Student Standing in Electrical Engineering or Computer Science. Basic understanding of algorithms and data structures is required for students taking this course.

Attention: Please refer back to this page frequently, as new material will be posted here as the course progresses

Instructor:      Andreas Savvides
                        Office AKW #212
                        Phone 432-1275
                        Email: andreas.savvides@yale.edu
                        Office hours: Wed 11:00am – 12:00pm and by appointment

Teaching Assistant: Dimitrios Lymberopoulos
dimitrios.lymberopoulos@yale.edu
Office Hours: TBD

Class Meeting Times: Tue - Thu 2:30 - 3:45pm Becton 102

Class Material:

Main Text: Principles of Embedded Networked Systems Design by William Kaiser and Greg Pottie
Note: This is a pre-print of the book, it will be ordered in class.

Recommended Text: Wireless Sensor Networks: An Information Processing Approach by F. Zhao and L. Guibas.

^*Both texts are now on reserve in the Engineering Library

Acknowledgements: We would like to acknowledge the contribution of Professors Kaiser, Pottie, Srivastava and Estrin and many of the paper authors for contributing material to this course. We are also grateful to Cogent Computer for their help with XYZ.

Additional Handouts and Papers will be distributed in class.

Course Syllabus (Including tentative lecture schedule for Fall 2004)

Lab resources: To complete the programming assignments for the course you will use the lab in CO-40. In this course we will use a new wireless sensor platform the XYZ node developed here at Yale. This node features an OKI ML64Q5002 processor and a Zigbee compliant radio from Chipcon. More details and access to the lab will be discussed in class.

Homeworks & Programming Assignments

Homework #1 (5%) due 09/21/04 2:00pm
Homework #2a (5%) due Nov 11 before class
Homework #2b (5%) due Nov 11 before class
Homework #3 (5%) due Dec 1
Programming Assignment #1 (5%) due 10/05/04 2:00pm - Starting code for PA#1
(Handout Package for PA#1 distributed in class)
Programming Assignment#2(%5) due 11/30/04 Code for PA#2

Detailed Lecture Schedule and Lecture Slides

		Lecture Topic	Required Reading	Supplementary Material and Information
Sep 2	Lecture 1	Introduction and Course Overview	[Tenenhouse00]	[Pottie00]
Sep 7	Lecture 2	Sensor Network Motivating Applications & Modeling Embedded Systems HW #1 Posted Online	[Edwards97] [Lee02]
Sep 9	Lecture 3	Embedded Processors and Sensor Network Platforms		[Melconian00][Edwards02]
Sep 14	Lecture 4	Complete discussion from lecture 3 slides Intro to Location Discovery		[Lymberopoulos04] XYZ Sensor Node Website & Class handout
Sep 16	Lecture 5	Different Ways for Computing Locations & Error Behaviors	[Savvides04a]
Sep 21	Lecture 6 SOS Tutorial	Embedded Systems Programming Tutorial, PA#1 Discussion & Projects CO-40 lab opens today! Deadline: Homework 1 due PA #1 Posted Online	[Melconian00]
Sep 23	Lecture 7	Medium Access Control	[Langendoen04]	[HW1 Zigbee Results - by Cris Crck]
Sep 28	Lecture 8	MAC, Physical Layer and Power Consumption
Sep 30	Lecture 9 Andrew's Slides	Time Synchronization & Calibration Time Synch Presenter: Andrew Deadline: 1 page project proposal due tomorrow 10/1/04	[Elson02] Read before class on Thursday!!!
Oct 5	Lecture 10 Eugenio's Slides	Prof Cullurciello: Sensors and Prof. Koser MEMs Deadline PA#1 (tomorrow, Oct 6)
Oct 7	Lecture 11	David Goldenberg: Unique Localizability
Oct 12	Lecture 12 IDSQ Slides	Routing in Sensor Networks	Zhao & Guibas Sections 3.3 - 3.6
Oct 14	Lecture 13	Routing Part II Geographic Hash Tables (Andreas), Directed Diffusion (Paa Kwesi)	[Intanagonwiwat00]
Oct 19	Lecture 14	No Lecture (makeup lecture Friday of next week)
Oct 21	Lecture 15	Guest Lecture: Prof. Deepak Ganessan, UMass Amherst	[Ganesan03]
Oct 26	Lecture 16 Diffusion Slides	a) Directed Diffusion b) Mobility Overview
Oct 28	Lecture 17	a) Capacity of mobile ad-hoc networks(Andreas) b) Controlled Mobility (Anjan)
Nov 2	Lecture 18	SOS Tutorial, HW & Programming Assignment Reviews PA#2 Handed out today	Go through the material posted on the SOS Webite
Nov 4		No Class (make up class Monday, Nov 8, 2:30 - 3:45pm) Read tutorial paper [Fox03]
Nov 9	Lecture 19(Nov 8) Lecture 20	Estimation and Bayesian Learning Review	[Fox03]
Nov 11	Lecture 21	Guest Lecture on Factor Graphs and Learning Prof. Sekhar Tatikonda
Nov 16	Lecture 22	Deadline: Homework # 2 Due before the test In class midterm
Nov 18	Lecture 23	Presentation: Chris Crick (Belief Propagation)
Nov 30	Lecture 24	In class presentation - Stephen Tully and Nathan Francis (Shooter Localization - SenSys04) Presentations: John Corwin - (TinyDB) Deadline: PA#2 Due
Dec 2	Lecture 25	Jeffrey & Jason (TinySEC - SenSys04) Security Issues & Conclusions Deadline: Homework #3 Due
Dec 7		Final Project Presentations
Dec 14		Final Project Reports Due

Paper Reference List

This reference list will expand during the semester. This will include pointers to course readings and more in-depth information to support individual projects and research. Please note that NOT all of the material posted here is included in the required reading for this course!

Introductory Material and Motivation

[Tennenhouse00] Tennenhouse, D. Proactive computing. Communications of the ACM, vol.43, (no.5), ACM, May 2000. p.43-50.

[Pottie00] G. J. Pottie and W. J. Kaiser, Wireless Integrated Network Sensors , Communications of ACM, 43(5), May 2000.

Embedded Systems Introduction

[Lee02] Lee, E.A.; Embedded Software. To appear in Advances in Computers (M. Zelkowitz, editor), Vol. 56, Academic Press, London, 2002.

[Edwards02] Edwards, Stephen A. Design Languages for Embedded Systems. Computer Science Technical Report CUCS-009-03, Columbia University.

[Edwards97] S. Edwards, L. Lavagno, E.A Lee and A. Sangiovanni-Vincetelli, Design of Embedded Systems: Formal Models, Validation and Synthesis, Proceedings of the IEEE, Vol. 85, No. 3, March 1997, pp. 366-390

[Melkonian00] Melkonian, M.; Get by without an RTOS. Embedded Systems Programming, September, 2000.

HW/SW Platforms & Tools

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

[Doherty01] L. Doherty, B.A. Warneke, B.E. Boser, and K.S.J. Pister, Energy and Performance Considerations for Smart Dust International Journal of Parallel Distributed Systems and Networks, Volume 4, Number 3, 2001, pp. 121-133.

[Elson03] EmStar: An Environment for Developing Wireless Embedded Systems Software J. Elson, S. Bien, N. Busek, V. Bychkovskiy, A. Cerpa, D. Ganesan, L. Girod, B. Greenstein, T. Schoellhammer, T. Stathopoulos, and D. Estrin
CENS Technical Report 0009, March 24, 2003.

[Gay03] David Gay, Phil Levis, Rob von Behren, Matt Welsh, Eric Brewer, and David Culler, The nesC Language: A Holistic Approach to Networked Embedded Systems, Proceedings of Programming Language Design and Implementation (PLDI) 2003, June 2003.

[Lymberopolos04] D. Lymberopoulos and A. Savvides, A Wireless Sensor Node Architecture for Exploring Distributed Sensor Network Applications, Work in Progress, ENALAB, Yale University

Localization in Sensor Networks

[Ihler04] A. Ihler, J. Fisher, R. Moses and A. Willsky, Nonparametric Belief Propgation for Self-Calibration in Sensor Networks, Proceedings of Conference on Information Processing in Sensor Networks, IPSN 2004

[Savvides03] A. Savvides, H. Park and M. B. Srivastava, The n-Hop Multilateration Primitive for Node Localization Problems, Proceedings of Mobile Networks and Applications, 8, 443-451, 2003

[Savvides04a] A. Savvides and M. B. Srivastava, Location Discovery, Mobile Ad Hoc Networking. IEEE Press and John Wiley & Sons, Inc., New Jersey and New York, April 2004. (With M. Conti, S. Giordano, and I. Stojmenovic

[Goldenberg04] D. Goldenberg, A. Krishnamurthy, W. Maness, Y. R. Yang, A. Young and A. Savvides, Network Localization in Partially Localizable Networks, under submission

Time Synchronization and Sensor Calibration

[Karp03] Optimal and Global Time Synchronization in Sensornets Richard Karp, Jeremy Elson, Deborah Estrin, and Scott Shenker
CENS Technical Report 0012, April 10, 2003.

[Elson02] Fine-Grained Network Time Synchronization using Reference Broadcasts, Jeremy Elson, Lewis Girod and Deborah Estrin
In Proceedings of the Fifth Symposium on Operating Systems Design and Implementation (OSDI 2002), Boston, MA. December 2002. UCLA Technical Report 020008.

[Ganeriwal03] S. Ganeriwal, R. Kumar, M. B. Srivastava, Timing-sync protocol for sensor networks, Proceedings of the First ACM Conference on Embedded Networked Sensor Systems (SenSys 2003)

Medium Access Control and Routing Protocols

[Langendoen04] K. Langendoen, Energy Efficient Medium Access Control, Embedded Systems Handbook, CRC press to appear

Mobility and Distributed Control

[Sinopoli03] B. Sinopoli, C. Sharp, L. Schenato, S. Schaffert and S. Sastry, Distributed Control Applications Within Sensor Networks, EEE Proceedings, Volume: 91, Issue: 8, Special issue on sensor networks and applications, Aug. 2003, Page(s): 1235- 1246 (Alvise)

[Demirbas03] M. Demirbas, A. Arora, and M. Gouda. A Pursuer-Evader Game for Sensor Networks. Sixth Symposium on Self-Stabilizing Systems, San Fransisco, June 2003

[Howard03] Andrew Howard, Maja J. Mataric´, and Gaurav S. Sukhatme, An Incremental Self-Deployment Algorithm for Mobile Sensor Networks, In Autonomous Robots Special Issue on Intelligent Embedded Systems, Vol. 13, No. 2, pp. 113-126, 2002

[Poduri04] Sameera Poduri and Gaurav S. Sukhatme, Constrained Coverage for Mobile Sensor Networks, In IEEE International Conference on Robotics and Automation, pp. 165-172, New Orleans, LA, May 2004.

Routing

[Intanagonwiwat00] Chalermek Intanagonwiwat, Ramesh Govindan and Deborah Estrin Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks
In Proceedings of the Sixth Annual International Conference on Mobile Computing and Networks (MobiCOM 2000), August 2000, Boston, Massachusetts.

Topology Management

Sensor Databases

Miscellaneous Topics and Applications

[Ganesan03] Deepak Ganesan, Ben Greenstein. Denis Perelyubskiy, Deborah Estrin and John Heidemann An Evaluation of Multi-resolution Storage for Sensor Networks, Proceedings of the First ACM Conference on Embedded Networked Sensor Systems (SenSys 2003).

[Fox03] D. Fox, J. Hightower, L. Liao, D. Schultz, G. Boriello, Bayesian Filters for Location Estimation, IEEE Pervasive Computing Magazine, July-September 2003