Special Topics Graduate Course:
Distributed Algorithms for Mobile Wireless Ad Hoc Networks
6.885, Spring 2006
Time and Location:
Mon/Wed 11:00 to 12:30
Algorithms (6.046 or equivalent)
Computer Systems (6.033 or equivalent)
Desirable: Distributed Algorithms (6.852 or equivalent)
Professor Jennifer Welch's Course Web Site.
Tentative Reading List.
Scribe and Lecture Sign-up.
This course will cover distributed algorithms for mobile (and some
non-mobile) wireless ad hoc networks, including those with interesting
interactions with the real world.
We will focus on algorithms that can be described precisely, and that
have relatively well-defined correctness, fault-tolerance, and
Our aim is to understand the existing theory of wireless network
algorithms and contribute to its further development.
Thus, we would like to:
- Understand the nature of wireless ad hoc network settings. What are
typical correctness, reliability, and performance properties that can
be assumed? What are the ``right'' complexity measures to use for
- Identify important, well-defined problems and subproblems that must
be solved by distributed algorithms in wireless ad hoc networks.
These will include problems of low-level and higher-level
communication, time synchronization, localization, network
configuration, resource allocation, tracking, and data management.
- Learn about the most important existing algorithms for many of these
problems, and identify places where additional algorithmic work is
- Identify some inherent limitations (lower bound and other
impossibility results) on the solvability of problems in wireless
- Identify useful abstraction layers for programming wireless networks.