CPSC 689-601: Special Topics in Discrete Algorithms for Mobile and Wireless Networks
Spring 2006

Announcements

• 2/6: I just posted scribe assignments -- check the calendar. We'll talk about scribe duties and due dates for scribed notes in class tomorrow.

• 1/25: My office hours are Mondays 2:00 - 3:30 PM, Wednesdays 8:45 - 10:15 AM.

• 1/17: Mandatory readings for class on Thu, 1/19 are
  • Balakrishnan's notes for lecture 11
  • Gallager paper, sections I (intro) and IV (Collision Resolution).
  Go the reading list to find the links (under section 0, General Background, and section 1, MAC Layer, respectively).

Back to beginning

Syllabus

Lecture: Tuesdays and Thursdays, 3:55-5:10 PM, HRBB 104

Textbook: None. We will use papers from the research literature.

Prerequisite: CPSC 629 (Analysis of Algorithms) or equivalent, or permission of the instructor. At least one of CPSC 619 (Networks and Distributed Computing), CPSC 662 (Distributed Processing Systems), or CPSC 668 (Distributed Algorithms and Systems) is recommended.

This is a theoretical course. We will be focusing on algorithms that have provable properties of correctness, complexity and/or optimality. A background in distributed systems or networking would be helpful in appreciating possible applications of the results in the course, but is not essential.

This course is being coordinated with essentially the the same course being taught simultaneously by Prof. Nancy Lynch at MIT.

• 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 evaluating algorithms?

• 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 needed.

• Identify some inherent limitations (lower bound and other impossibility results) on the solvability of problems in wireless networks.

• Identify useful abstraction layers for programming wireless networks.

Course Content: The course will cover the following topics. We will proceed roughly through the ``layers'' of a wireless network design:

• MAC layer
• Localization, time synchronization
• Topology control
• Local infrastructure (local consensus, local leader election, local reliable broadcast, etc.)
• Global broadcast
• Point-to-point routing
• Location-based communication services (location services, location-based routing,
• Global infrastructure (spanning trees, clusters, maximal independent sets, etc.)
• Middleware services (token circulation, resource allocation, consensus, group membership, etc.)
• Virtual node layers
• Applications (data aggregation and maintenance, query-processing, environmental sensing, tracking, intelligent highways, motion coordination, etc.)

Your grade will be based on these components:

• paper summaries 30%: One or two papers will be assigned for you to read for each class. For each paper you must turn in a typed one-page summary and critique of the paper at the beginning of class.

• presentation 30%: Each student will present some of the topics.

• scribe notes 30%: For each class, someone other than the presenter will be appointed scribe. The scribe will produce notes that document the presentation and discussion for that class.

• class participation 10%: based on attendance and your level of participation in the class discussions.

Course grades will be assigned according to this scale:

Collaboration: For the assignments in this class, discussion of concepts with others is encouraged, but all assignments must be done on your own, unless otherwise instructed. Reference every source you use, whether it be a person, a book, a paper, a solution set, a web page or whatever. You MUST write up your assignments in your own words. Copying is strictly forbidden. Every assignment must be turned in with this cover sheet, which lists all sources you used.

Back to beginning

Reading List

Back to beginning

Calendar

Back to beginning

Assignments

• Complete bibliographic reference
• Summary of the main points of the paper
• Why are the results new/interesting/significant
• Assumptions made concerning the model of computation
• Open questions
• Your critique of the paper
• Cover sheet

The student presenting a topic will usually have to read more papers on that topic than the rest of the class will (e.g., the supplementary papers as will as the mandatory papers). The presenter will prepare some written notes covering the presentation; these may be in outline form rather than polished prose.

During your presentation do not try to cover all details of the selected papers. Instead, try to find the main points, and bring in material from the other papers as needed to explain the main ideas. You may end up focusing on some small parts of the papers (e.g., a particularly interesting proof).

Scribe Notes: For each class, someone other than the presenter will be appointed as scribe. The scribe should try to produce a good record of what was said in class. Start with the presenter's notes and clarify any confusing points, improve the prose, etc. Also, record all the interesting points made in the class discussion and include them in the notes. Finally, you may want to include your personal perspective on the material.

Back to beginning

Useful Links

• Some tips for reading research papers from Swarthmore. You can find lots more if you google on "how to read a research paper".

• Advice on Research and Writing from CMU.