TIME: Thursdays 4:15-6pm
PLACE: Gates 260
INSTRUCTORS: Feng Zhao <fz@alum.mit.edu>, Leo Guibas <guibas@cs.stanford.edu>
 
 

COURSE DESCRIPTION

This course is a graduate level seminar, intended for students who plan to pursue research concerning information processing in sensor networks. The course will cover two fronts: introduce students to the diverse literature on sensor networks, and expose them to the fundamental issues in designing and analyzing sensor network information processing applications. In particular, we will use localization and tracking as canonical examples to expose important constraints in scaling and deploying these sensor networks. We will also cover topics of querying, data routing, and network self-organization and how they can support high-level information processing tasks.

PREREQUISITES: consent of instructor
 

Information processing for sensor networks is an emerging area of computer science. Because of advances in MEMS micro-sensors, wireless networking, and embedded processing, ad hoc networks of sensors are becoming increasingly available for commercial and military applications such as environmental monitoring (e.g. traffic, habitat, security), industrial sensing and diagnostics (e.g. factory, appliances), infrastructures (e.g. power grid, water distributions, waste disposal), and battlefield awareness (e.g. multi-target tracking). There is an active research community pursuing sensor network related research in U.S. and elsewhere, funded in part by DARPA (e.g. SensIT, NEST, PAC/C), ONR, and NSF. The State of California recently established the CITRIS Center at Berkeley, with a primary focus on sensor networks.

However, because this is an emerging research area involving a variety of different technologies, major contributions to sensor networks today are scattered in many specialized conferences on wireless networking, sensors, data fusion, signal/image processing, probabilistic reasoning, and robotics. For example, Infocom, Mobicom, Mobihoc, Fusion, and ICASSP regularly have papers on various topics concerning sensor networks. A practitioner in sensor network research often has to be versed in several disparate research areas before he/she can start to contribute to the sensor network research.

From the engineering and computing point of view, sensor networks become a rich source of problems in communication protocols, sensor tasking and control, sensor fusion, distributed data bases, probabilistic reasoning, and algorithmic design. This course aims to synthesize the diverse literature concerning various aspects of sensor networks such as information organization, querying, routing, and self-organization, with an emphasis on the high-level information processing tasks that these networks are designed to perform. To the best of our knowledge, no comparable courses are offered in the US universities today. It is our hope that this course will expose students to the fundamental issues and technology constraints of sensor networks and prepare them for research in this nascent area.
 

Format: 2-hour class each week, 10 weeks total.  Except for the first week, each class will comprise an overview by the instructors followed by presentations from students.

Week 1, 4/4/02: Class organization, schedule, grading, presentation signup; Driving applications, constraints/challenges, collaborative information processing in sensor nets

readings: weiser91, weiser93, kahn99, estrin02

readings: estrin99, intanagonwiwat02, heidemann01, krishnamachari02

readings: byers00, chu02, zhao02, chen02

readings: reid79, guibas02, video-tracking-paper

readings: hightower01, priyantha00, savvides01, li00, chen01

readings: bonnet00, faradjian02, hellerstein00, huang01

readings: matousek94, gao01a, gao01b

readings: royer99, yu01, karp00, royer01, krishnamachari02

readings: pottie00, raghunathan02, doherty01, chandrakasan99, hill00

readings: cerpa01, kidd99

Students must take the class as either pass/fail or letter graded. The reading materials as well as lecture notes will be available on the web ahead of the lecture.

The final grade will be based on:

(1) For those taking it pass/fail:

25% Participation in class discussion;
75% Presentation: each student is responsible for presenting paper(s) and lead a discussion on a selected topic

20% Participation in class discussion;
30% Presentation: each student is responsible for presenting paper(s) and lead a discussion on a selected topic
50% Project: each student will work on a project involving analysis, simulation, or implementation, and prepare a final project report. The topics of the project (and possibly teaming) must be selected by April 11th.

GENERAL

[weiser91] Mark Weiser, "The Computer for the Twenty-First Century," Scientific American, pp. 94-10, September 1991.

[weiser93] Mark Weiser, "Some Computer Science Problems in Ubiquitous Computing."  Communications of the ACM, July 1993.

[kahn99] J. M. Kahn, R. H. Katz, K. S. J. Pister. "Next century challenges: mobile networking for "Smart Dust", MobiCom 1999, pp. 271-278.

[estrin02] Deborah Estrin, David Culler, Kris Pister, Gaurav Sukhatme. "Instrumenting the physical world with pervasive networks." IEEE Pervasive Computing, to appear, 2002.

NETWORKING

Diffusion:

[estrin99] Deborah Estrin, Ramesh Govindan, John Heidemann and Satish Kumar.  "Next Century Challenges: Scalable Coordination in Sensor Networks."  In Proceedings of the Fifth Annual International Conference on Mobile Computing and Networks (MobiCOM '99), August 1999, Seattle, Washington.

[intanagonwiwat02] 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.

[heidemann01] John Heidemann, Fabio Silva, Chalermek Intanagonwiwat, Ramesh Govindan, Deborah Estrin, and Deepak Ganesan.  "Building Efficient Wireless Sensor Networks with Low-Level Naming", In Proceedings of the Symposium on Operating Systems Principles, Lake Louise, Banff, Canada, ACM. October, 2001.

Aggregation:

[krishnamachari02] Bhaskar Krishnamachari, Deborah Estrin, Stephen Wicker, "Modelling Data-Centric Routing in Wireless Sensor Networks." IEEE Infocom 2002.

Routing:

[royer99] E. M. Royer and C-K. Toh. "A review of current routing protocols for ad-hoc mobile wireless networks."  IEEE Personal
Communications, April 1999.

[yu01] Yan Yu, Ramesh Govindan and Deborah Estrin.  "Geographical and Energy Aware Routing: A Recursive Data Dissemination Protocol for Wireless Sensor Networks."  UCLA Computer Science Department Technical Report UCLA/CSD-TR-01-0023, May 2001.

[karp00] Karp, B., and Kung. H. T..  "GPSR: Greedy Perimeter Stateless Routing for Wireless Networks." In Proceedings of the 6th Annual International Conference on Mobile Computing and Networking (MobiCom 2000), 243-254, 2000.

[haas] Zygmunt Haas, Joe Halpern, and Li Li. "Gossip-Based Ad-hoc Routing." IEEE INFOCOM 2002, New York, 2002.

Large-scale analysis:

[royer01] Elizabeth M. Royer, P. Michael Melliar-Smith, and Louise E. Moser.  "An analysis of the optimum node density for ad hoc mobile networks."  Proc. IEEE International Conference on Communications, Helsinki, Finland, June 2001.

[krishnamachari02] Bhaskar Krishnamachari, Stephen Wicker, Ramon Bejar, and Marc Pearlman, "Critical Density Thresholds in Distributed Wireless Networks," to appear in a book on Advances in Coding and Information Theory, eds. H. Bhargava, H.V. Poor and V.  Tarokh, Kluwer Publishers.

COLLABORATIVE PROCESSING AND TRACKING

[byers00] John Byers and Gabriel Nasser.  "Utility-based decision making in wireless sensor networks."  Proc. of IEEE MobiHoc 2000,
Boston, MA, August 2000.

[rosenblatt99] Rosenblatt J, "Optimal selection of uncertain actions by maximizing expected utility".  IEEE International Symposium on
Computational Intelligence in Robotics & Automation (CIRA'99) 8-9 November 1999, Monterey CA, USA.

[chu02] M. Chu, H. Haussecker, F. Zhao, ``Scalable Information-Driven Sensor Querying and Routing for ad hoc Heterogeneous Sensor Networks.''  Int'l J. of High Performance Computing Applications, to appear, 2002.

[zhao02] Feng Zhao, Jaewon Shin, James Reich.  "Information-Driven Dynamic Sensor Collaboration for Target Tracking", IEEE Signal
Processing Magazine, Volume: 19 Issue: 2, Mar 2002.

[reid79] D.B. Reid. "An Algorithm for Tracking Multiple Targets." IEEE Trans. on Automatic Control, 24:6, 1979.

[guibas02] Leonidas Guibas. "Sensing, Tracking and Reasoning with Relations", IEEE Signal Processing Magazine, Volume: 19 Issue: 2, Mar 2002.

[chen02] Joe C. Chen, Kung Yao, and Ralph E. Hudson, "Source localization and beamforming", IEEE Signal Processing Magazine,
Volume: 19 Issue: 2, Mar 2002.

[li02] Dan Li, Kerry Wong, Yu Hen Hu, Akbar Sayeed. "Detection, Classification and Tracking of Targets in Distributed Sensor
Networks", IEEE Signal Processing Magazine, Volume: 19 Issue: 2, Mar 2002.

(I am also going to add 1-2 papers on multi-camera tracking and data association)

LOCATION/TIME SERVICES, NETWORK DISCOVERY

[priyantha00] Nissanka B. Priyantha, Anit Chakraborty, and Hari Balakrishnan.  "The Cricket Location-Support System."  Proc. of the
Sixth Annual ACM International Conference on Mobile Computing and Networking (MOBICOM), August 2000.

[hightower01] Jeffrey Hightower, Gaetano Borriello. "Location systems for ubiquitous computing." IEEE Computer, Vol. 34, No. 8, August 2001 pp 57-66.

[savvides01] Andreas Savvides, Chih-Chieh Han and Mani B. Strivastava. "Dynamic fine-grained localization in ad-hoc networks of sensors." 7-th annual international conference on Mobile computing and networking (MobiCom) 2001, July 16 - 21, 2001, Rome Italy.  Pages 166-179.

[li00] Jinyang Li, John Jannotti, Douglas S. J. De Couto, David R. Karger, Robert Morris.  "A scalable location service for geographic ad hoc routing."  ACM Mobicom 2000, Boston, MA, pages 120-130.

[chen01] Benjie Chen, Kyle Jamieson, Hari Balakrishnan, and Robert Morris.  "Span: an energy-efficient coordination algorithm for
topology maintenance in ad hoc wireless networks."  Proc. 7th ACM International Conference on Mobile Computing and Networking (MobiCom '01), Rome, Italy, July 2001, pages 85-96.

INFORMATION MANAGEMENT

Database and query processing:

[bonnet00] Philippe Bonnet, J. E. Gehrke, and Praveen Seshadri. "Querying the Physical World."  IEEE Personal Communications, Vol. 7, No. 5, October 2000, pages 10-15. Special Issue on Smart Spaces and Environments

[faradjian02] Anton Faradjian, J. E. Gehrke, and Philippe Bonnet. "GADT: A Probability Space ADT for Representing and Querying
the Physical World".  In Proceedings of the 18th International Conference on Data Engineering (ICDE 2002), San Jose, California,
February 2002.

[hellerstein00] Joseph M. Hellerstein and Ron Avnur. "Eddies: Continuously Adaptive Query Processing." In SIGMOD 2000.

[huang01] Huang, Yongqiang; Garcia-Molina, Hector. "Publish/Subscribe in a Mobile Environment." MobiDE01, 2001.

Geometric search and clustering:

[matousek94] Jirka Matousek, "Geometric range searching." Computing Surveys, volume 26, number 4, page. 422-461, 1994.

[gao01a] J. Gao, L. J. Guibas, J. Hershberger, L.  Zhang and A. Zhu. "Discrete mobile centers."  Proc. 17th ACM Symp. on
Computational Geometry (SoCG), June 2001, pages 190-198.

[gao01b] J. Gao, L. J.  Guibas, J. Hershberger, L. Zhang and A. Zhu. "Geometric spanners for routing in mobile networks."  Proc. 2nd ACM Symp. on Ad-Hoc Networking and Computing (MobiHoc), October 2001, pages 45-55.

PHYSICAL CONSTRAINTS

[pottie00] G. Pottie and W. Kaiser. "Wireless Integrated Network Sensors."  Communications of the ACM, 43 (5): 51-58, May 2000.

[raghunathan02] Vijay Raghunathan, Curt Schurgers, Sung Park, Mani B. Srivastava.  "Energy-aware wireless microsensor networks." IEEE Signal Processing Magazine, Volume: 19 Issue: 2, Mar 2002.

[doherty01] L. Doherty, B.A. Warneke, B.E. Boser, 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.

[chandrakasan99] Anantha Chandrakasan, Rajeevan Amirtharajah, SeongHwan Cho, James Goodman, Gangadhar Konduri, Joanna Kulik, Wendi Rabiner, Alice Wang.  "Design considerations for distributed microsensor systems."  Proc. IEEE 1999 Custom Integrated Circuits Conference (CICC '99) (May 1999), pp. 279-286.

[hill00] Jason Hill, Robert Szewczyk, Alec Woo, Seth Hollar, David E. Culler, Kristofer S. J. Pister. "System Architecture Directions for
Networked Sensors." ASPLOS 2000.

APPLICATIONS

[cerpa01] Alberto Cerpa, Jeremy Elson, Deborah Estrin, Lewis Girod, Michael Hamilton, and Jerry Zhao.  "Habitat monitoring: Application driver for wireless communications technology."  2001 ACM SIGCOMM Workshop on Data Communications in Latin America and the Caribbean, Costa Rica, April 2001.

[kidd99] Kidd, Cory D., Robert J. Orr, Gregory D. Abowd, Christopher G. Atkeson, Irfan A. Essa, Blair MacIntyre, Elizabeth Mynatt, Thad E. Starner and Wendy Newstetter.  "The Aware Home: A Living Laboratory for Ubiquitous Computing Research." In the Proceedings of the Second International Workshop on Cooperative Buildings, CoBuild'99.