COSC 747 - Topics in Wireless Network Algorithms

Georgetown University

Prof. Calvin Newport

Tuesday and Thursday, 2:00 - 3:15 pm

3rd Floor Conference Room, Saint Mary's Hall

Course Overview


The formal study of algorithms for wireless networks has been an active research topic since the 1970s. Recently, however, it has received renewed interest, spurred by the increasing availability of cheap and versatile wireless chips. The question of what problems you can and cannot solve efficiently when communicating over the airwaves is now in urgent need of answers.

In this course, we will tackle the current state of the art research on this question. The field has been moving fast enough that there's no good survey available of what we know about these algorithms and what we need to know. The goal of this course is to produce such a survey. As detailed below, students will read and present research papers (guided by the professor). The class will culminate with the students synthesizing what we learned into a survey paper that will be submitted to a major computer science journal.

Along the way, we will identify multiple compelling research projects for those students interested in pursuing additional publications in the area over the summer.


This course is open to all graduate students. Any specific technique needed to understand the papers will be taught as needed.


This course is intended to help new graduate students transition to a research-oriented mindset, and help more senior graduate students jump start their publication count. In more detail, there are three specific goals for this course:

  1. The student will learn how to efficiently survey computer science research literature. (Techniques for tackling papers, including one-on-one instruction from the professor, is a major component of the course.)
  2. The student will gain an expert-level knowledge on the current state of wireless algorithm research.
  3. The student will be a co-author on a submitted journal paper and be exposed to several potential research projects to pursue, if interested, after the course concludes.

Student Responsibilities

As detailed in the syllabus below, we will cover two research papers in each class. Every student will be responsible for answering some basic questions about every paper we cover, due by the beginning of the class discussing the papers. As also detailed below, students will be responsible for answering a short lecture summary questions about each lecture, which will be sent out at the end of class and must be answered, via e-mail, the same day. In addition, most classes will led by a student who will be responsible for providing a more detailed presentation about the results and techniques from that day's papers. At the end of the semester, each student will be responsible for writing up a detailed summary in LaTex -- following a template and set of guidelines provided by the professor -- of the papers he or she presented in class.

Attendance in class and participation in our discussions is an important student responsibility. Absences should be rare and approved in advance, when possible.

Academic Integrity

Students are expected to work on their reading response questions on their own. It is okay to discuss papers with your classmates or the professor when working on your presentations. The presentations and associated write-ups, however, must be your own original work. No copy and pasting of existing text, or editing of existing text, is allowed. All writing must be done by the student from scratch.

Course Mechanics

Paper Reading Method

Below is the method we will use in this course for tackling research papers. It describes three levels of detail at which you can understand a paper. The key idea driving this course is that you must learn how to dive down to just enough detail when faced with a paper, but not more than you need at the moment. As described below, your reading response questions will help you practice the first level of detail, your presentations will help you practice the second, and we will practice the third level together in class.

Reading Response Questions

As detailed in the schedule below, we will cover 1 - 2 papers in each class. You are responsible for submitting reading response questions for the papers covered in a class, by the beginning of the class. Late submissions will receive 0 points.

In more detail, your reading response must take 1 result from each of the papers, and perform a level 1 analysis. That is, you must describe the problem and model, identify the specific time complexity proved (every parameter in the time complexity must be explained), describe how it compares to existing results, and summarize why we should care about the result. If we cover 2 papers, for example, you will analyze 2 results, 1 from each.

Submit your reading response questions by e-mailing them to the professor with the subject line: COSC 747: Reading Response: Class X, where X is the corresponding class number.

Lecture Summary Questions

At the end of each lecture, the professor will e-mail the class a question about the material covered during the presentation (and surrounding discussion). The question will require only a short answer. To respond, simply reply to my e-mail with your answer. This is due by midnight the same day as the lecture.

If you pay attention in class and make sure you follow both the presentation and discussion surrounding the presentation it should take you less than a minute to answer the question. If you do not pay attention an answer may be difficult to come by at all. You may not collaborate on these answers.


Students will rotate responsibility for presenting papers in the class, following a schedule that will be determined once the final enrollment is fixed. During a presentation, you must first walk the class through a level 1 analysis on all results in the papers covered in the class. You must then choose at least one result and walk the class through a level 2 analysis. Finally, by the beginning of the class in which you present, you must add a succinct summary of the papers to draft of the the class survey paper which we will keep in an SVN repository. These summaries will be brief (no more than one paragraph per paper), and you will be provided examples of what they should look like.

Your presentation should last around 45 - 50 minutes. If you worry that your presentation will run short, add additional level 2 analyses, or do a more detailed comparison of the results to existing work, to get it to the appropriate length.

A quick note on preparation: Because a presentation seems less concrete then a problem set, students sometimes assume they can get away with reading the papers at the last minute and winging their discussion. Don't do this. It is not difficult to tell the difference between a student who really knows the material and one who does not, and the latter will receive a low grade.

Presenter's Choice Presentations

As shown on the syllabus below, at the end of the semester, each student gets a chance to present a paper of his or her choice. Several students are assigned to each such lecture. They will each present one paper and the time will be split evenly among them.

For these lectures, it is the student's responsibility to find a new paper (i.e., that we have not covered yet) that studies algorithms in a wireless model. Please submit the paper to the professor for approval at least two days before your presentation.

Reading summary questions are not required for presenter's choice lectures. You do not have to do a final write-up on your presenter's choice papers. The professor will still send out lecture summary questions.

Final Write-Up

At the end of the semester, each student will be responsible for handing in a formal summary of each of the papers he or she presented in class. This does not include the presenter's choice papers.

These summaries should be handed in by the last day of classes for the semester in LaTex format. The professor will provide a detailed template/guidelines for these summaries. These write-ups should be understood to be similar to a take-home exam. That is, if you follow the template/guidelines, you will be forced to really understand the papers you present -- describing their model, problems, and results with clarity. The quality level expected for these write-ups is higher than the standard reading response summaries, as is reflected by their contribution to your final grade (see below).

The professor is happy to look at drafts of these summaries and provide feedback about where you are falling short of the template/guidelines. To maximize your chances of a good grade, it is highly recommended that you take advantage of this offer. Don't wait until the last minute, however, as the professor cannot guarantee same-day response or responses over the weekend.

Survey Paper

After the semester concludes, the professor will combine the final write-up summaries to produce a detailed annotated bibliography of the papers covered during the course. He will then massage this into the proper format for a survey paper and submitted with all students' names as co-authors. This will occur over the summer.


Students will be graded on their reading response questions, presentations, attendance/participation, and final write-up. In more detail, grades will be assigned on the following point scale:

At the end of the semester, I will add up all the points earned by each student and decide where the cut offs are for A, B, and C work. These cut offs will be independent of the actual student scores, so it is completely possible for all students to earn an A (so long as you put in the required effort).

Office Hours

I hold regular office hours from 11:30 am to 1:00 pm on Thursdays, in my office at 342 A Saint Mary's Hall.


The schedule below describes which papers we will cover in each class. You will be provided these papers electronically at the beginning of the class in an archive file. Each paper is named as follows: [last name of first author]-[publication year]. Some of the schedule is left empty -- these papers will be filled in as the class progresses.


Class NumberDateDescription Presenter
11/9Course Mechanics; Introduction to Wireless Algorithms 
Part 1: The Protocol Model
21/15Wireless Networks as Multi-Access Channels
  • N. Abramson. The ALOHA System: Another Alternative for Computer Communication (1970). [no reading response questions required]
  • R. Gallager. A Perspective on Multi-Access Channels (1985). [no reading response questions required]
  • J. Komlos and A. Greenberg. An Asymptotically Nonadaptive Algorithm for Conflict Resolution in Multiple-Access Channels (1985).
31/17Centralized Global Broadcast: Early Results
  • I. Chlamtac and S. Kutten. On Broadcasting in Radio Networks -- Problem Analysis and Protocol Design (1985).
  • I. Chlamtac and O. Weinstein. The Wave Expansion Approach to Broadcasting in Multihop Radio Networks (1991).
41/22Centralized Global Broadcast: Pursuing Optimality
  • N. Alon, A. bar-Noy, N. Linial, and D. Peleg. A Lower Bound for Radio Broadcast (1991).
  • L. Gasieniec, D. Peleg, and Q. Xin. Faster Communication in Known Topology Radio Networks (2007).
51/24Distributed Global Broadcast: Randomized Solutions
  • R. Bar-Yehuda, O. Goldreich, and A. Itai. On the Time-Complexity of Broadcast in Multi-Hop Radio Networks: An Exponential Gap between Determinism and Randomization (1992).
  • Errata Regarding: On the Time-Complexity of Broadcast in Multi-Hop Radio Networks: An Exponential Gap between Determinism and Randomization. [no reading response questions required; presenter should use errata to present results from above paper correctly]
  • E. Kushilevitz and Y. Mansour. An \Omega(D/log(N/D)) Lower Bound for Broadcast in Radio Networks (1998).
61/29Distributed Global Broadcast: Deterministic Solutions
  • D. Kowalski and A. Pelc. Deterministic Broadcasting Time in Radio Networks of Unknown Topology (2002).
  • D. Kowalski and A. Pelc. Broadcasting in Undirected Ad Hoc Radio Networks (2005). [also includes an important randomized result]
71/31Multihop Leader Election
  • R. Bar-Yehuda, O. Goldreich and A. Itai. Efficient Emulation of Single-Hop Radio Network with Collision Detection on Multi-Hop Radio Network with No Collision Detection (1991).
  • M. Ghaffari and B. Haeupler. Near Optimal Leader Election in Multi-Hop Radio Networks (2012).
82/5The Wake-Up Problem
  • T. Jurdzinski and G. Stachowiak. Probabilistic Algorithms for the Wakeup Problem in Single-Hop Radio Networks (2002).
  • S. Daum, F. Kuhn and C. Newport. Efficient Symmetry Breaking in Multi-Channel Radio Networks (2012). [you are only responsible for the single result in Section 4.2, though you will need to read Section 4.1 to understand it.]
92/7Local Broadcast
  • M. Bender, M. Farach-Colton, S. He, B. Kuszmaul and C. Leiserson. Adversarial Contention Resolution for Simple Channels (2005).
  • M. Ghaffari, B. Haeupler, N. Lynch and C. Newport. Bounds on Contention Management in Radio Networks (2012). [Only read results for the classical model (in this paper "classical" = "protocol").]
102/12Distributed Network Structuring
  • F. Kuhn, T. Moscibroda and R. Wattenhoffer. Initializing Newly Deployed Ad Hoc and Sensor Networks (2004).
  • T. Moscibroda and R. Wattenhoffer. Maximal Independent Sets in Radio Networks (2005).
  • [Ask about extra credit opportunity here.]
Part 2: The Physical Model
112/14Connectivity Scheduling: Early Results
  • T. Moscibroda and R. Wattenhofer. The Complexity of Connectivity in Wireless Networks (2006).
  • T. Moscibroda. The Worst-Case Capacity of Wireless Sensor Networks (2007).
122/19Connectivity Scheduling: Optimal/Distributed Results
  • M. M. Halldorsson and P. Mitra. Wireless Connectivity and Capacity (2012).
  • M. M. Halldorsson and P. Mitra. Distributed Connectivity of Wireless Networks (2012).
132/21Capacity and Link Scheduling: Centralized Results
  • O. Goussevskaia, R. Wattenhofer, M. Halldorsson, and E. Welzl. Capacity of Arbitrary Wireless Networks (2009).
  • M. M. Halldorsson and P. Mitra. Wireless Capacity with Oblivious Power in General Metrics (2011).
142/26Capacity and Link Scheduling: Distributed Results
  • T. Kesselheim and B. Vocking. Distributed Contention Resolution in Wireless Networks (2010).
  • M. Halldorsson and P. Mitra. Nearly Optimal Bounds for Distributed Wireless Scheduling in the SINR Model (2011).
152/28Dynamic Link Scheduling
  • T. Kesselheim. Dynamic Packet Scheduling in Wireless Networks (2012).
  • G. Pei and V. A. Kumar. Low-Complexity Scheduling for Wireless Networks (2012).
163/12Structuring Networks
  • C. Scheideler, A. Richa, and P. Santi. An O(log n) Dominating Set Protocol for Wireless Ad-Hoc Networks under the Physical Interference Model (2008).
  • D. Yu, Y. Wang, Q. Hua, and F. Lau. Distributed (Delta + 1)-Coloring in the Physical Model (2012).
173/14Global Broadcast
  • T. Jurdzinski and D. Kowalski. Distributed Backbone Structure for Algorithms in the SINR Model of Wireless Networks (2012). [Read results for broadcast and leader election. You can skip result on emulating stronger models.]
  • D. Yu, Q. Hua, Y. Wang, H. Tan, and F. Lau. Distributed Multiple-Message Broadcast in Wireless Ad-Hoc Networks Under the SINR Model (2012).
183/19Connecting Physical Model to Other Models
  • E. Lebhar and Z. Lotker. Unit Disk Graph and Physical Interference Model: Putting Pieces Together (2009).
  • T. Jurdzinski and D. Kowalski. Distributed Backbone Structure for Algorithms in the SINR Model of Wireless Networks (2012). [Read results for emulating stronger models.]
Part 3: Dynamic Models
193/21Distributed Algorithms in Dynamic Networks, Part 1
  • C. Avin, M. Koucky, and Z. Lotker. How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs). (2008)
  • F. Kuhn, N. Lynch, and R. Oshman. Distributed Computation in Dynamic Networks. (2010)
203/26Distributed Algorithms in Dynamic Networks, Part 2
  • F. Kuhn, R. Osham, and Y. Moses. Coordinated Consensus in Dynamic Networks. (2011)
  • A. Cornejo, S. Gilbert, and C. Newport. Aggregation in Dynamic Networks. (2012)
214/2Distributed Broadcasting in Dynamic Radio Networks
  • A. Clementi, A. Monti, and R. Silvestri. Broadcasting in Dynamic Radio Networks. (2009)
  • F. Kuhn, N. Lynch, C. Newport, R. Oshman, and A. Richa. Broadcasting in Unreliable Radio Networks. (2010)
224/4The Dual Graph Model
  • K. Censor-Hillel, S. Gilbert, F. Kuhn, N. Lynch, and C. Newport. Structuring Unreliable Radio Networks. (2011)
  • M. Ghaffari, N. Lynch, and C. Newport. The Cost of Radio Network Broadcast for Different Models of Unreliable Links. (Under Submission)
234/9Shared Spectrum: Deterministic Algorithms.
  • S. Dolev, S. Gilbert, R. Guerraoui, and C. Newport. Gossiping in a Multi-Channel Radio Network: An Oblivious Approach to Coping with Malicious Interference. (2007)
  • S. Gilbert, R. Guerraoui, D. Kowalski, and C. Newport. Interference-Resilient Information Exchange. (2009)
244/11Shared Spectrum: Randomized Algorithms.
  • S. Daum, S. Gilbert, F. Kuhn, and C. Newport. Leader Election in Shared Spectrum Radio Networks. (2012)
  • S. Daum, M. Ghaffari, S. Gilbert, F. Kuhn, and C. Newport. Maximal Independent Sets in Multichannel Radio Networks. (Under Submission)
254/16Single-Channel Jamming-Resistant Algorithms.
  • B. Awerbuch, A. Richa, and C. Scheideler. A Jamming-Resistant MAC Protocol for Single-Hop Wireless Networks. (2008)
  • V. King, J. Saia, and M. Young. Conflict on a Communication Channel. (2011)
264/18Presenter's Choice.Henry, Keelan
274/23Presenter's Choice.Weitong, Xi, Brendan
284/25Presenter's Choice.Tonghe, Changlong