Spring 2010 CSE590 Algorithms for Wireless Sensor Networks

Locations and Hours:

Tuesday, 11:20-2:10pm (3-hour lecture with 10 mins break), CS 1306

Instructors: 

Instructor: Prof. Jie Gao, 1415 Computer Science Building. Email: jgao at cs dot sunysb dot edu. Office hour: Monday Tuesday 5:30-7pm or by appointment.

Announcements:

  1. Homework 3 is posted and is the last homework.
  2. The first class is on Jan 26th. See you there!

Course Description:

This course is a 3-credit graduate course on the recent progress in wireless sensor networks. 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, providing economical and practical solutions for data collection and environment monitoring, especially in hostile, inaccessible environments or emergent situations. Sensor networks have the potential to revolutionize the way we observe, interact with and influence the physical world. The major technical challenges of sensor networks include scalable network self-organization, as well as efficient processing of the massive amount of spatially and temporally distributed data, under the constraint of limited computation and communication resources.

This course will focus on the algorithmic issues for wireless sensor networks involved in important networking and data processing functions, such as

Algorithms for sensor networks face a number of challenges.

The lectures will be self-contained so no prior knowledge on those topics is required. Prerequisites include undergraduate networking, algorithm and probability courses or consult with the instructor. Previous years’ offerings: Fall 2005, Fall 2006, Spring 2009.

The lecture will be 3-hour long each week, including a 10 mins break in the middle.

Auditors are welcome!

Course Materials:

Most of the materials used in this course are technical papers. See the reading list below. Some recommended textbooks:

Grading and Requirements:

We expect to have an interactive class. Grading includes class participation (20%) and homework assignments (80%). Students are required to finish the “required readings” (typically 1-2 papers) before class. Class participation includes class attendance and paper presentation.

Paper presentation: each student will be asked to present at least 1 paper in class. The presentation is about 30 mins. Students will be evaluated by the audience, in terms of slides quality, presentation clarity and audience engagement. 

Homework assignments are going to be open-ended questions. Collaboration up to 2 students is allowed. In the case of a collaboration, only one homework solution from a group of 2 is required. The homework solutions will be peer-reviewed, in addition to the grades given by the instructor.  

Students are highly encouraged to discuss with the instructor about research ideas. In Fall 2005 offering, a number of successful projects have turned into publications in the best networking conferences such as ACM Mobicom and MobiHoc. Students who get papers published will be supported to travel to the conferences to present the work.

Syllabus:

 

Slides/Notes

Lecture Topics

Required readings

Additional reading

1/26 Localization slides Introduction, network localization [Culler04][Savvides01]
2/2 Localization II Slides Localization, rigidity theory [Eren04][Moore04]
Student presentation:
[Maroti05]
[Kusy07]
Homework 1 (on localization) out
2/9 Routing I Location-based routing [Karp00][Gao01]
Student presentation
[Biswas04][So05]
2/16 Routing II Location-based routing in practice [Kim05][Rao03][Papadimitriou04]
Student presentation
I: [Zhang08]

II: [Funke07a][Funke07b]
2/23 Routing III Location-free routing [Rao03][Papadimitriou04][Leighton08]
[Newsome03][Caesar06]
Student presentation
[Flury09]
Homework 1 due
Homework 2 out
3/2 Routing IV Landmark-based routing Student presentation
[Godfrey09]
3/9 Data-centric Data-centric routing Student presentation
[Moeller10]
3/16 Location service Location service Student presentation
[Motiwala08]
Homework 2 due

3/23 Aggregation I Data collection and aggregation Student presentation
[Lee10]
Homework 3 out
4/6 Aggregation II Data collection and aggregation Student presentation
[Kwong10]
4/13 Coding I Network coding and in-network data storage Student presentation
[Burri07][Gnawali09]
4/20 Coding II Network coding and in-network data storage Homework 3due
4/27 Selection Sensor selection Student presentation
[Gollakota08][Katti07]
5/4 Synchronization Student presentation
[Jaggi07]

Reading List (Continuously updated, Papers in shade will not be covered in this class):

Overview

Localization:

Location-based routing:

Routing with virtual coordinates:

Landmark-based routing:

Data-centric query:

Information aggregation:

Multi-dimensional range queries:

Boundary detection:

Coding and applications in wireless communication and storage:

Sensor selection:

Synchronization:

New routing schemes:

Simulators for sensor networks protocols:,

Last updated: 4/11/09