Distributed Computing
ETH Zurich

Ad Hoc and Sensor Networks (HS 2010)

Thousands of mini computers (in size comparable to a chewing gum), equipped with sensors, are deployed in some terrain. After activation the sensors form a self-organized network and provide data, for example about a forthcoming earthquake. The trend towards wireless communication affects more and more electronic devices in almost every sphere of life. Conventional networks rely on base stations, and the mobile devices exchange the data in a star-like fashion. In contrast, current research is mainly focused on networks that are completely unstructured, but are nevertheless able to communicate (via several hops), despite the low coverage of their antennas. Such systems are called sensor, ad hoc, or mesh networks, depending on the point of view and the application. For a few years now, these networks have been the focus of the research of the networking community. The goal of the lecture is to elaborate the relevant aspects of the field, from theory to practice.

Topics: Applications, Wireless Basics, Modeling, Media Access, Topology Control, Clustering, Clock Synchronization, Localization & Positioning, Routing & Data Gathering.

Course pre-requisites: Basic networking knowledge.

Course language: English.

Lecture by Roger Wattenhofer, Monday 13-15 @ CHN G42.

Exercises by Philipp Sommer and Johannes Schneider
Monday 15-17 @ CHN G42.


The exam is scheduled for Wednesday, 2. February 2011, 09:00-10:30, HG E5. You may use any written material like scripts, your own notes, exercise sheets, books, etc... All electronical devices (computers, calculators, cell phones, etc...) are not allowed during the exam!

The written exams covers the course material listed here.

In order to get a feeling of our exam style, you may have a look at this and this old exam.

Question Session

We will hold a question session in which we (try to) answer your questions about this lecture. The session is on Friday, 28. January 2011, 14:00 - 15:00 at ETZ F78.1 Please send us your questions ahead of time, at the latest until Thursday, 27. January 2011 at 14:00 by email to either of the assistants.


Algorithms for Sensor and Ad Hoc Networks
In addition to the lecture slides we recommend the newly published book Algorithms for Sensor and Ad Hoc Networks by Dorothea Wagner and Roger Wattenhofer. It is currently for sale at Springer, Amazon, Thalia, and other book stores.

Publisher: Springer
ISBN-10: 3-540-74990-X
ISBN-13: 9783540749905

From within the ETH network you may also access an online version of the book by following this link.

Lecture material

Title PDF 1:1 PDF 4:1 PowerPoint Additional Material

Chapter 1
Download Download Download

Chapter 2
Download Download Download Lecture Notes Chapter 2
Useful links:
Big O notation (NIST)
Big O notation (Wikipedia)
Lecture about Asymptotic Notation by Erik Demaine, MIT

Chapter 3
Topology Control
Download Download Download Lecture Notes Chapter 3

Chapter 4
Data Gathering
Download Download Download

Chapter 5
Network Coding
Download Download Download

Chapter 6
Media Access Control
Download Download Download

Chapter 7
MAC Theory
Download Download Download Lecture Notes Chapter 7

Chapter 8
Clock Synchronization
Download Download Download Lecture Notes Chapter 8

Chapter 9
Download Download Download

Chapter 10
Download Download Download Lecture Notes Chapter 10

Chapter 11
Download Download Download

Chapter 12
Download Download Download Lecture Notes Chapter 12

Chapter 13
Download Download Download

Exercise material

Title PDF Files

Exercise 1
Assigned: 2010/09/27
Due: 2010/12/17
Download ---

Exercise 2
Assigned: 2010/10/04
Due: 2010/10/11
Download Sample Solution

Exercise 3
Assigned: 2010/10/11
Due: 2010/10/18
Download Sample Solution

Exercise 4
Assigned: 2010/10/18
Due: 20010/10/25
Download Sample Solution

TinyOS Lab Exercise
Assigned: 2010/10/18
Due: 2010/12/24
Download Exercise Slides
Getting started with TinyOS
Code Skeleton
Hints/FAQ for the lab exercise
Lab Reservation Link (Doodle)

Exercise 5
Assigned: 2010/10/25
Due: 2010/11/1
Download Sample Solution

Exercise 6
Assigned: 2010/11/1
Due: 2010/11/8
Download Sample Solution

Exercise 7
Assigned: 2010/11/8
Due: 2010/11/15
Updated: 2010/11/07 22:00
Sample Solution
Solution Slides

Exercise 8
Assigned: 2010/11/15
Due: 2010/11/22
Download Sample Solution

Exercise 9
Assigned: 2010/11/22
Due: 2010/11/29
Download Sample Solution

Exercise 10
Assigned: 2010/11/29
Due: 2010/12/06
Updated: 2010/12/06
removed Exercise 2 (f) and (g)
Sample Solution

Exercise 11
Assigned: 2010/12/06
Due: 2010/12/13
Download Sample Solution

Exercise 12
Assigned: 2010/12/13
Due: 2010/12/20
Download Sample Solution

Exercise 13
Assigned: 2010/12/20
Due: -
Download Sample Solution