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 TBD
Class Material:
Recommended Text: Wireless Sensor Networks: An Information Processing Approach by F. Zhao and L. Guibas.
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.
*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 and OKI Semiconductor for their help with XYZ.
Additional Handouts and Papers will be distributed in class.
Lab resources: To complete the programming assignments for the course you will use the lab in CO-40.
Homework 1: (due Sept. 15, 2005): Write a 1-2 page review of [Frank05]. Your review should not be a mere summary of the paper. It should clearly identify the ideas of the paper, comment on their strengths and weaknesses. You should also spend at least one paragraph with your own comments, thoughts and ideas on the topic.
Programming Project (Due Oct 20, 2005)
| Lecture Topic | Required Reading | Supplementary Material and Information | ||
| Sep 1 | Lecture 1 | Introduction and Course Overview | [Tenenhouse00] | [Pottie00] |
| Sep 6 | Lecture 2 | Platforms and Power Considerations in Networked Embedded Systems | ||
| Sep 8 | Lecture 3 | Embedded Operating Systems & Tutorial |
SOS Paper [Han04] |
XYZ User Manual |
| Sep 13 | Lecture 4 | Location Discovery: Intro, Basics, EKF Setup | ||
| Sep 15 | Lecture 5 | Programmability Issues in Sensor Networks, Discussion of programmability issues, NesC and [Frank05] | ||
| Sep 20 | Lecture 6 | Location Discovery II: EKF, MDS, RSSI Experiments, Behaviors from CR-Bounds | ||
| Sep 22 | Lecture 7 | Location Discovery III: SCAAT EKF (example problems, building the state model) | ||
| Sep 27 | Lecture 8 | Lab session, class meets in CO-40 | 1 Page project proposals due | |
| Sep 29 | Lecture 9 | Localization Wrap up | ||
| Oct 4 | Lecture 10 | MAC Protocols | ||
| Oct 6 | Lecture 11 (slides emailed and distributed in class) | Formulate problems on MAC, latency and power control. Discussion leader: Deokwoo | ||
| Oct 11 | Lecture 12 | Coverage and Detection Scheduling | ||
| Oct 13 | Lecture 13 | MAC Wrapup and Topology Management | ||
| Oct 18 | Lecture 14 | Midterm 1 - No Lecture | ||
| Oct 20 | Lecture 15 | Time Synchronization | ||
| Oct 25 | Lecture 16 | Lab Day | XYZ Manual | |
| Oct 27 | Lecture 17 | Project Checkpoint | ||
| Nov 1 | Lecture 20 | Routing I | ||
| Nov 3 | Lecture 21 | Routing II | ||
| Nov 8 | Lecture 22 | |||
| Nov 10 | Lecture 23 | Spanning Trees and Clusters (Jonathan, Andreas) | ||
| Nov 15 | Lecture 24 | Junction Trees (Deokwoo) | ||
| Nov 17 | Lecture 25 | Go to Human Speech Home Talk (Wed Nov 16) | ||
| Nov 29 | Lecture 26 | |||
| Dec 1 | Lecture 27 | |||
| Dec 6 | Lecture 28 | |||
| Dec 8 | Lecture 29 | |||
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!
[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.
[Culler04] D. Culler, D. Estrin and M. B. Strivastava, Introduction: Overview of Sensor Networks, IEEE Computer August 2004, Available from http://ieeexplore.ieee.org
[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.
[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
[Lymberopoulos05] D. Lymberopoulos, A. Savvides, XYZ: A Motion-Enabled, Power Aware Sensor Node Platform for Distributed Sensor Network Applications, to appear in the proceedings of Information Processing in Sensor Networks (IPSN), SPOTS track, April 2005
[Han04] 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
[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
[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)
[Langendoen04] K. Langendoen, Energy Efficient Medium Access Control, Embedded Systems Handbook, CRC press to appear
[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.
[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.
[Magdon-Ismail03] M. Magdon-Ismail, F. Sivrikaya and B. Yener, Joint Problem of Power Optimal Connectivity and Coverage in Wireless Sensor Networks. ACM Wireless Networks
[Cao05] Q. Cao, T. Abde;zaher, T. He and J. Stankovic, Towards Optimal Sleep Scheduling in Sensor Networks for. Rare-Event Detection, Proceedings of IPSN 2005
[Frank05] C. Frank and K. Romer, Algorithms for Generic Role Assignment in Wireless Sensor Networks, to appear in the Proceedings of ACM SenSys 2005
[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
Details of project topics will be discussed in class.
EE202A Embedded and Real-Time Systems by Professor Mani Srivastava @UCLA, Fall 2003
UCLA CS 213 by Professor Deborah Estrin @UCLA , Winter 2004
CS294-1 Deeply Embedded Network Systems by Professor David Culler @UC Berkeley, Fall 2003
Sensor Networks Course at Stanford taught by Prof. Leonidas Guibas and Prof. Feng Zhao @ Stanford
Sensor Networks Bibliography at USC