Fall 2006 CSE590 Algorithms for Wireless Sensor Networks

 

Locations and Hours:

Tuesday and Thursday, 12:50pm-2:10pm @ Social Behavior Science S218.

Instructors: 

Instructor: Prof. Jie Gao, 1415 Computer Science Building. Email: jgao at cs dot sunysb dot edu. Office hour: Tuesday/Thursday 3:00pm - 4pm or by appointment.

Announcements:

·         Class schedule change: Monday Oct 9th, 9:00-10:20am at CS2311. Two interesting papers on routing with virtual coordinates.

·         Please email me the project title, group members and when you prefer to present (Oct 17 or 19).

·         Class schedule changes: No class on 9/21. We will have classes on Mondays 9/25, 9:00am-10:20am, at CS building 2311. Consult the syllabus below.

·         Project ideas will be distributed in class on 9/19.

·         The first class is Thursday 9/7. See you there!

Course Description:

This course is a 3-credit graduate course on the recent progress in wireless sensor networks, one of the fastest 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, 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

·         network modeling, connectivity,

·         network localization,

·         geometric routing,

·         information aggregation,

·         information storage and query,

·         optimization and function evaluation via gossip algorithms,

·         node mobility issues.

Algorithms for sensor networks face a number of challenges.

·         Sensor nodes typically only have local views and have no knowledge of the global network layout, or even the location of itself. Thus localized, distributed algorithms are always preferred if not required;

·         Sensor nodes may die. Communication links are not stable. System robustness is an indispensable consideration.

·         Sensor data is noisy, due to sensor malfunction or packet loss during communication. Thus data-processing algorithms need to be robust to noises and outliers in the input.

·         Sensor nodes have limited resources in terms of energy, computation and communication. Any algorithms for large-scale sensor networks should be simple, distributed and light-weight.

The lectures will be self-contained so no prior knowledge on those topics is required. There will also be new topics that were not covered last year. Prerequisites include undergraduate networking, algorithm and probability courses or consult with the instructor.

Auditors are welcome!

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. Students are required to finish the “required readings” (typically 1-2 papers) before the class. For class participation, we will have students paired up. Each group chooses a paper, presents the paper in class (a 30mins talk), and writes a critique for this paper, which explains (i) if you like it, or do not like it, why? (ii) ways to improve over the results in the paper (iii) other related open problems motivated by this paper.

For the final projects, students are encouraged to form a group of two or three and choose either the theory track or the applied track.  A project on 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, 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. An 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 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. 

Possible project ideas will be distributed in class. You are highly encouraged to discuss with me about your project 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.

Syllabus:

 

Slides/Notes

Lecture Topics

Required readings

Additional reading

9/7

Lecture 1

Overview, class organization, modeling

[Culler04][Ganesan02]

[Estrin99][Hill04][TinyOS]

9/12

Lecture 2

Localization I

[Savvides01][Eren04]

[Savvides03][Graver93][Jacobs97]Notes on Linear Algebra

9/14

Lecture 3

Localization II

[Moore04][Shang03]

[Whitehouse06][Whitehouse05]Notes on MDS

9/19

[Priyantha05](critique)

[Li05](critique)

Student presentation

Project ideas will be handed out in this class

[Priyantha05][Li05]

 

9/25, 9:00am-10:20am, at CS building 2311

Lecture 4

Geometric routing I

[Karp00][Gao01]

[Kuhn03][Bruck05a]

10/3

Lecture 5

Geometric routing II

[Kim05a][Kim05b][Rao03]

[Frey06]

10/5

Lecture 6

Routing with virtual coordinates

[Fang05a][Bruck05b]

[Caesar06b][Fonseca05]

10/9, 9:00am-10:20am

at CS building 2311

[Newsome03](critique)

[Caesar06a](critique)

Student presentation

[Newsome03][Caesar06a]

[Caesar06b]

10/10

Lecture 7

Information aggregation I

[Madden02][Nath04]

 

10/12

Lecture 8

Information aggregation II

[Shrivastava04][Broder02]

[Considine04]

10/17

Project list

Midterm project presentation

 

 

10/19

Project list

Midterm project presentation

 

 

10/24

Lecture 9

Data-centric queries I

[Intanagonwiwat00] [Ratnasamy02][Li00]

 

10/26

Lecture 10

Data-centric queries II

[Sarkar06][Fang06]

[Braginsky01]

10/31

Invited Lecture by Shweta Jain

Abstract

TinyOS, Programming Sensor Networks, and Applications I

[TinyOS]

 

11/2

Invited Lecture by Shweta Jain

TinyOS, Programming Sensor Networks, and Applications II

[TinyOS]

 

11/7

[Silberstein06](critique)

[Avin04](critique)

Student presentation

[Silberstein06][Avin04]

 

11/9

Lecture 11

Distributed indexing

[Berg99][Li03a]

[Gao04]

11/14

Lecture 12

Coding in storage

[Dimakis05]

 

11/16

Lecture 13

Percolation theory and connectivity

[Grimmett99](photocopies available in my office)

[Franceschetti05]

A web demo.

Igor Pak’s notes on Coupon collector problem.

11/21

Lecture 14

Network coding

[Fragouli06]

Birthday paradox

11/23

Thanksgiving

No class

 

 

11/28

 

Student presentation

[Katti06][Zhang06]

 

11/30

Lecture 15

Synchronization

[Werner05]

 

12/5

Lecture 16

DNA self-assembly

[Winfree03], Erik Winfree’s webpage

 

12/7

 

Student presentation

[Zhu05][Nagpal06]

 

12/12

Presentation schedule

Final project presentation

 

 

12/14

 

Final project presentation

 

 

Reading List:

Overview

Modeling, connectivity

Localization:

·         [Savvides01] A. Savvides, C.-C. Han, and M. B. Strivastava. Dynamic fine-grained localization in ad-hoc networks of sensors. In MobiCom ’01: Proceedings of the 7th ACM Annual International Conference on Mobile Computing and Networking, pages 166–179, 2001.

·         [Savvides03] A. Savvides, H. Park, and M. B. Strivastava. The n-hop multilateration primitive for node localization problems, Mobile Networks and Applications, Volume 8, Issue 4, 443-451, 2003.

[Moore04] D. Moore, J. Leonard, D. Rus, S. Teller, Robust distributed network localization with noisy range measurements, Proc. ACM SenSys 2004.

Location-based routing:

Routing with virtual coordinates:

Information aggregation and query:

Multi-dimensional range queries:

Data-centric query:

Synchronization:

Information compression and replication:

Network coding:

Gossip algorithms:

 

New Directions:

 

Write a critique for one of the following papers:

Basic math notes:

·         Eero P. Simoncelli’s notes on Geometric Review of Linear Algebra. 

·         Classical Multi-dimensional Scaling (MDS).

·         Igor Pak’s notes on Coupon collector problem.

·         Birthday paradox.

Simulators for sensor networks protocols:

  • ns-2: network simulator.
  • TOSSIM: TinyOS mote simulator.

Previous year’s sample projects:

·         Amitabh Basu, Girishkumar Sabhnani, Distributed Localization by Noisy Distance and Angle Information, MobiHoc’06.

·         Yue Wang, Boundary Recognition in Sensor Networks by Topological Methods, MobiCom’06.

How to:

Last updated: 8/30/06