6.033 2013 Design Project 2: Ad-Hoc Wireless Network

I. Due Dates and Deliverables

You will be working on the second design project in teams of three students who share the same recitation instructor. There are five deliverables for this design project:

  1. A list of team members emailed to your TA by April 16, 2013.
  2. One copy of an executive summary of your project (not exceeding 1,200 words), due at 5pm on May 3, 2013.
  3. A five-minute presentation of your executive summary, also due on May 3.
  4. One copy of a design report (not exceeding 5,000 words), due at 5pm on May 10, 2013.
  5. A five-minute in-recitation presentation, on May 14 or May 16, 2013.

All written deliverables should be submitted via the online submission site.

As with real life system designs, 6.033 design projects are under-specified, and it is your job to complete the specifications in a sensible way given the overall requirements of the project. As with designs in practice, the specifications often need some adjustment as the design is fleshed out. We recommend that you start early so that you can evolve your design over time. A good design is likely to take more than just a few days to put together.

II. The Problem

Ben Bitdiddle has been contracted to design a reliable communication system for first responders (e.g., police, fire-fighters, medical emergency workers, etc.).  First responders are deployed in disaster-stricken areas to search for survivors and estimate damages. They typically need to communicate with their base to report their location and ensure their safety. They also take pictures that they send to the base station to report damages, problems, or the status of those who need help. This information is used by those at the base to evaluate the need for deploying more rescuers, sending special equipment, asking for help, etc. However, when a disaster strikes, it is likely that the infrastructure becomes inaccessible. For example, during hurricane Katrina, the cell towers were knocked off preventing people from making phone calls or sending data using smart phones.

BenŐs objective is to design an ad hoc network infrastructure for transmitting messages from first responders to their base station wirelessly. In BenŐs scheme, every first responder has a handheld device (e.g., a portable small computer) with a Wi-Fi card and a GPS receiver. The device is also equipped with a camera. It also maintains a queue that stores a maximum of 200 images that it needs to forward.  The GPS receiver provides a new location reading every 30 seconds.  Image traffic can be bursty and unpredictable. BenŐs design has to support the following types of communications:

á      Location information: the network should strive to reliably deliver the most up-to-date GPS location of all first responders to their base station at least once every 5 minutes. If the location of a first responder is unknown for a period longer than 5 minutes, the base station should fire an alarm.

 

á      Images: It should provide a best effort service for delivering images collected by the first responders to their base station. Best effort means that the network design aims to maximize throughput even with congestion (the number of correct images delivered to the destination), but does not promise any guarantees.

When all nodes are static, the network topology may look as shown below. Circles refer to first respondersŐ nodes, the square refers to the base station, and the arrows show the direction of packets. This image is for illustration and may not be the best design for such a network.  Also it does not take into account that nodes are mobile and hence the network formation will change over time.

 

 

 

 

 

 


As Ben designs his network, he has to deal with the limitations of the wireless medium as well as the needs of his users. Specifically:

á      Wireless links are lossy. The packet loss probability between a pair of nodes, p_i,j, takes a value in the range [0,1]. In particular, if j is outside the radio range of i, it will not hear the signal and the loss rate will be 1. In contrast, in the absence of physical obstacles, nodes that are very close will hear each other perfectly and will have a loss probability of 0.  Most loss rates are between these two extremes depending on the relative location of the nodes as well as other parameters, e.g., being in the shadow of a metallic structure, etc. The loss rate is unpredictable; but one can measure it. You may assume that these measurements stay valid for a period of 30 seconds.

 

á      Wireless links have a broadcast nature, i.e., when a node transmits a packet, the nodes within radio range can hear the transmission. Different receiver nodes can correctly decode the packet according to the corresponding loss probability defined above. 

 

 

 


á      Due to their broadcast nature, wireless links suffer interference, i.e., if multiple nearby nodes transmit at the same time, their signals collide at the receivers, preventing them from decoding.  As a result, Wi-Fi nodes typically sense the medium and transmit only if the medium is idle (Please check the lecture on wireless MAC for details). Hence, larger paths typically translate to lower throughput. For example, in the figure below, the one-hop path leads to almost twice as much throughput as the two-hop path despite the two-hop path having fewer instances of lost packets.  Note that the intermediate node along the 2-hop path cannot transmit and receive at the same time.

 

 

 

 

 


In order to help Ben with his design, his employer has provided him wireless nodes equipped with the following initial set of functions:

To make things simpler you can make the following assumptions

á      If two nodes are within radio range, the ACK loss probability is zero

á      Each of the handheld devices has a unique ID.  

á      You can assume that the nodes have access to synchronized clocks.

á      The base station is not moving and is in a fixed GPS location known to all nodes.

á      You can assume that nodes do not fail. Links on the other hand can fail any time due to either movement or changes in the wireless channel characteristics.

á      Each node has a queue that can store a maximum of 200 images.  You can assume that location information consumes negligible storage space and transmission bandwidth in comparison to images.

á      Assume GPS has a resolution of 1 meter and provides a reading every 30 seconds. The radio range of the wireless system is 30 to 50 meters, and first responders typically move at a relatively low speed, i.e., they stay within radio range for multiple GPS readings. 

á      It is OK if not all images are delivered reliably. You should maximize the number of images delivered while focusing on delivering the most recent images.

III. Requirements

The challenges you should address in your design project are as follows:

  1. Design an ad hoc routing protocol. Your protocol should enable each first responder to send messages to the base station such that:
    1. The messages should reach the base station if there is any sequence of connected nodes between the sender and the base station.
    2. The protocol should pick routes that maximize throughput in times of congestion when there are many messages to deliver to the base station
  2. For location information, the routing protocol should strive to deliver these packets reliably to the base station within the 5-minute deadline. Note that the network may be disconnected at the time when the location information is sent.
  3. The system should accept messages only from first responders. Furthermore, it should not forward messages from non-trusted nodes or include such nodes in its routes.

After you have designed your system, you should evaluate it under the following scenarios:

Note that there are many possible correct designs. These designs may differ in how they use the GPS information, whether they code packets or not, how and when they update the routes, etc. No design is optimal. But different designs may differ in their performance under different traffic loads, and their level of robustness.

IV. Executive Summary

The executive summary should summarize your design in 1,200 words or fewer. It should outline the protocol and algorithms the nodes use to route messages, to ensure reliable delivery of location information, and to be robust against malicious nodes.

You do not have to present a detailed rationale or analysis in your executive summary. However, if any of your design decisions are unusual (particularly creative, experimental, or risky) or if you deviate from the requirements, you should explain and justify those decisions in your proposal.

You will receive feedback from your TA in time to adjust your final report.

V. Design report

Your report should explain your design. It should discuss the major design decisions and tradeoffs you made, and justify your choices. It should discuss any limitations of which you are aware. You should assume that someone who has read this assignment but has not thought carefully about this particular design problem is reading your report. Give enough detail that your project can be turned over successfully to an implementation team. Your report should convince the reader that your design satisfies the requirements in Section III.

Use this organization for your report:

Here are a few tips:

While the Writing Program will not be grading DP2, you should feel free to ask them for help.

VI. Presentation

This year, you will give two presentations. Each presentation is five minutes. In the first presentation, you will describe your executive summary, including your proposed design, to your writing instructor and TA. In the second presentation, you will describe your final DP2 design to your recitation instructor. In both presentations, the audience will be very familiar with the problem, so you can get right to the guts of your solution.

VII. How we evaluate your work

Your recitation instructor will assign your report a grade that reflects both the design itself and how well your report presents the design. These are the main high-level grading criteria: