Spring 2011 CSE590 Algorithms for Wireless Sensor Networks

Locations and Hours:

Tuesday Thursday, 2:20-3:40pm, Humanities 2047


Instructor: Prof. Jie Gao, 1415 Computer Science Building. Email: jgao at cs dot sunysb dot edu. Office hour: check instructor website or by appointment.


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, Spring 2010.

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. Most of the lectures will be given by the intructor. For standard lectures, students are required to finish the “required readings” (typically 1-2 papers) before class. 

About 1/3 of the lectures will be led by students, in the form of either a paper presentation or a discussion session on project ideas. For the project, the idea is to learn to do research. Students may form groups of 2 to work on the project. Each group will need to (1) choose a topic; (2) present existing literatures in class; (3) at the end of the semester, present research results. For class projects, a list of suggested topics will be distributed in class. The major evaluation metric for class projet is novelty. Students are required to submit progress updates during the semester and are highly encouraged to discuss with the instructor about research ideas. 

Grading includes class participation (20%), a late mideterm (30%), and a final project (50%).  

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.




Lecture Topics

Required readings

Additional reading

2/3 Introduction Introduction [Estrin99][Culler04][Hill04]
2/8 Localization I Localization: trilateration, graph rigidity [Savvides01][Eren04]
2/10 Localization II Localization: pebble game, anchor-free alg [Jacobs97][Moore04]
2/15 Localization III
Geographical routing I
Localization: MDS, SDP [Shang03][Biswas04]
2/17 Geographical routing II Geographical routing [Karp00][Gao01] [Frey06]
2/22 Geographical routing III Geographical routing: guarantee path stretch [Kuhn03]
2/24 Routing with virtual coordinates Geographical routing in practice, virtual coordinates [Kim05][Rao03]
3/1 Greedy embedding
Greedy embedding [Papadimitriou04][Leighton08][Newsome03]
3/3 Virtual coordinates
Landmark based distance estimation
Virtual ring routing, landmark-based distance estimation [Caesar06][Kleinberg04]
3/8 Landmark based routing Beacon vector routing, GLIDER [Fonseca05][Fang05a]
3/10 Landmark based routing S4 [Mao07]
3/22 Data centric routing Directed diffusion, GHT, rumor routing, double rulings [Intanagonwiwat00][Ratnasamy02][Braginsky02]
3/24 Range query Kd-tree, Range tree. [Li03a][Greenstein03]
3/29 Presentation by Prosenjit Sarkar, Aamir Manasawala and Pallav Bose, Nehal Bandi
3/31 Range query
4/5 Location service Location Service
4/7 Presentation by Connor Fitzsimons, 
4/12 Guest lecture by Prof David Gu Greedy routing using conformal geometry
4/14 Guest lecture by Xiaomeng Ban Wormhole attacks
4/26 Midterm review
In-network aggregation [Madden02][Hellerstein03][Shrivastava04]
4/28 Midterm in class
5/3 Aggregation
5/5 Coding in network

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



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:


New routing schemes:

Simulators for sensor networks protocols:,

Last updated: 1/30/11