Fall 2005 CSE590 Information Processing in Sensor Networks

 

Locations and Hours:

Tuesday and Thursday, 12:50pm-2:10pm @ Physics P129

Instructors: 

Instructor: Jie Gao, 1415 Computer Science Building. Email: jgao at cs dot sunysb dot edu. Office hour: Thursday 2:10pm - 4pm or by appointment.

TA: Pengfei Sun, Email: pfsun at cs dot sunysb dot edu. Please email the TA the lecture notes and/or technical questions about Latex, software for project etc.

Announcements:

  1. The first class will be on Thursday 9/1.
  2. There is a discussion forum on blackboard system that you can use to find groupmates and discuss project ideas.
  3. The lecture notes for rigidity theory (lecture 3) is out. See below. Let's thank Amitabh Basu.
  4. On September 20, we'll have student presentations on 3 localization papers. 
  5. The lecture notes for lecture 4 is out. Let's thank Girishkumar Sabhnani.
  6. The lecture notes for lecture 5 is out. Let's thank Yue Wang.
  7. The lecture notes for lecture 8 is out. Let's thank Radhika Bargavi.

Course Description:

This course is a 3-credit course on the recent progress in wireless sensor networks, one of the fast developing areas in computer science and engineering. A wireless sensor network consists of a large number of autonomous, small-size, inexpensive sensor nodes that can communicate with each other by wireless radios. Networked sensor systems of large scale are becoming available in the foreseeable future and provide economical and practical solutions for data collection and environment monitoring, especially in hostile, inaccessible environments or emergent situations. It has the potential to revolutionize the way we observe, interact with and influence the physical world. One of the major challenges of sensor networks is to provide a scalable and efficient way to process the massive amount of spatially and temporally distributed data generated by a large number of sensors, under the constraint of limited computation and communication resources. How to deliver the information to users essentially determines the effectiveness and efficiency of a large sensor network.

This course will focus on how information sensed in a distributed manner is collected, delivered, and queried. In terms of networking stack, it will be mostly on routing layer and higher. Topics cover localization, location-based and location-free routing, information aggregation, storage and retrieval, geographical query, data-centric query, sensing coverage and topology discovery, information compression and replication in sensor networks. For each topic, I will introduce both existing practical solutions and their theoretical counterparts (for the purpose of a better understanding of the problems). I will pay special attention to the limitations of existing approaches and possible ways to improve them. Techniques from other fields, such as computational geometry, advanced data structures and coding theory will be introduced. The lectures will be self-contained so no prior knowledge on those topics is required. There will be little overlap with the previous CSE590 course on ad hoc and sensor networks in Spring 2005. Students who took that course are encouraged to take this one too. Prerequisites include undergraduate networking and algorithms or consult with the instructor.

Course Materials:

Most of the materials used in this course are technical papers. See the reading list below. A recommended textbook is Wireless Sensor Networks: An Information Processing Approach by F. Zhao and L. Guibas, Elsevier/Morgan-Kaufmann, 2004. The book is put on 2-hours reserve in computer science library.

Grading and Requirements:

We expect to have an interactive class. Grading includes class participation (20%) and a final project (80%). There are no homework nor exams. For class participation, each student is required to either present a paper in class (about 20 minutes) or scribe notes for a lecture (Please see below for how to scribe notes). We expect to have about 12 paper presentations and 16~17 lectures. 

For the final projects, students are encouraged to form a group of size 2 or 3 and choose either the theory track or the applied track.  The project on the theory track involves identifying a topic of interest, related to one of the topics covered in the class, and formulating it into a mathematical problem. For the evaluation of a theory track project, if significant progress on the problem is made, then the group will pass and get an A automatically. Otherwise, the evaluation will be based on a survey paper of at most 15 pages long that covers background knowledge, related work on this topic, possible techniques to solve the problem and interesting future directions. The applied track project will involve identifying a topic of interest, and simulation/implementation of an algorithm and performance evaluation, and a final report on your discovery. At the end of the semester the students are expected to make a 30 minutes presentation on their projects in class. There will also be a midterm progress check by which the students are expected to find a topic, and make a presentation about preliminary work, and get feedback from the class. 

Syllabus:

  Slides/Notes Lecture Topics Required readings Additional reading
9/1 Lecture 1 Overview and class organization [Estrin99][Culler04]  [Ganesan02][Hill04][TinyOS][Culler05] 
9/6 Lecture 2 Localization, overview, multilateration [Savvides01][Savvides03][Howard01]  
9/8 Lecture 3

Notes

 Rigidity theory, Pebble game [Eren04][Jacobs97] [Whiteley97][Graver93]
9/13 Lecture 4

Notes

 localization by quadruples, Hardness results [Moore04][Breu98] [Kuhn04]
9/15 Lecture 5

Notes

 More on hardness results, Location-based routing, Face routing, GPSR. [Bruck05a][Bose01][Karp00]  
9/20 Slides1, Slides2, Slides3 Student presentation [Shang03][Goldenberg05][Priyantha05]  
9/22 Lecture 6 Planar graph subtraction. Challenges in geographical routing [Kuhn03][Gao01][Kim05a][Kim05b] [Karp01]
9/27 Lecture 7 Location-free routing, virtual coordinates [Rao03][Newsome03][Papadimitriou]  
9/29 Lecture 8

Notes

 Glider, MAP [Fang05a][Bruck05b] [Fonseca05][Caruso05][Attali04] 
10/4   No class    
10/6   Midterm project presentation    
10/11   Midterm project presentation    
10/13   No class    
10/18 Slides1, Slides2, Slides3 Student presentation [Zhu05][Funke05b][Yang05]  
10/20 Lecture 9 Query the sensor network (TinyDB) [Madden02] [Hellerstein03] 
10/25 Lecture 10 q-digest, Synopsis diffusion [Shrivastava04][Nath04] [Considine04]
10/27 Lecture 11 Data-centric storage and retrieval, directed diffusion, GHT, GLS [Intanagonwiwat00][Braginsky01][Ratnasamy02][Li00]  
11/1 Lecture 12 DIM, fractional cascading [Li03a][Gao04] [Funke05a]
11/3 Guest lecture by Prof. Samir Das MAC in Sensor Networks    
11/8   Student presentation [Przydatek03][Greenstein03][Ganesan03] [Ganesan02]
11/10 Lecture 13 Synchronicity and firefly [Mirollo90][Lucarelli04][Werner05]  
11/15 Lecture 14 Percolation Theory [Grimmett99][Gilbert61][Franceschetti05]   
11/17 Lecture 15 Information compression and replication, Coding theory, Storage by erasure code, packet combining [Dimakis05][Dubois05]  
11/22 Guest lecture by Prof. Andrew Jiang Network coding [Ahlswede00][Li03b]  
11/24   Thanksgiving. No class    
11/29 Lecture 16 Gossip Algorithm and Distributed Fusion [Xiao05][Boyd05]  
12/1 Lecture 17 Game theory [Roughgarden02]  
12/6   Student presentation [Broder02][Kumar05]  
12/8   Final project presentation    
12/13   Final project presentation    

Reading List:

Overview

Hardware, software, architecture

Localization:

Location-based routing:

Location-free routing:

Information aggregation and query:

Multi-dimensional range queries:

Data-centric query:

Synchronization:

Percolation:

Information compression and replication:

Gossip algorithms:

Game Theory:

Sensing coverage and topology discovery:

Security, etc.:

New directions:

Scribe Notes:

You are required to use Latex. The style file is attached below. Please refer to the template file to start. (The style file and templates are copied from Michael Bender). 

Possible Project Ideas:

This will be distributed in class.

Simulators for sensor networks protocols:

How to:

Last updated: 8/30/05