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:

• scan() returns the list of nodes within radio range with the corresponding loss probability from the node performing the scan. The list is returned as a sequence of tuples (node, loss_prob)
• broadcast(msg) broadcasts msg to all nodes within radio range
• send(node, msg) broadcasts msg to all nodes within radio range with a header indicating that only the specified node should look at it. You can assume that send() obeys the 802.11 MAC. However, the MAC is not set up to retransmit lost messages. You will need to take care of retransmitting lost messages yourself.
• receive() is a call back function that is called whenever a message is received and decoded correctly.

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:

• List all conditions under which your system may use more resources than necessary to deliver a packet to its destination.
• List all the conditions under which your system may fail to inform the base station of the location of a first responder at least once every 5 minutes.
• Can a malicious node in your system prevent a first responder’s message from reaching the base station? If so, under what conditions?
• Explain how your design behaves in the following scenarios: no traffic, light load, and heavy congestion, both with respect to the location information and the images.
• Describe how your system behaves if a malicious node tries to mount a replay attack. Specifically, the malicious node can hear a legitimate message, then broadcasts 1million copy of this message pretending it received it from the source. Would the legitimate nodes in your network pick up those messages and forward them to the base station?
• Say that you have a route that goes from node i to node j to node k to the base station. Recall that losses are probabilistic. It might happen that with small probability, when i transmits a message, node k hears that message directly. In that case, what does k do with the message? Does k forward the message to the base station? Does k drop the message and wait until it receives it from j? What are the implications?
• Similarly, what happens in your system when a (trusted) node very close to the destination (or even the base station) hears a message that was not intended for it?

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:

• Title page: Give your report a title that reflects the subject and scope of your project. Include your names, email address, recitation instructor, section time(s), and the date on the title page.
• No table of contents.
• Introduction: Summarize what your design is intended to achieve, outline the design, and briefly outline why your design meets the requirements.
• Design: Explain your design. Identify your design's main components, state, algorithms, and protocols. You should sub-divide the design, with corresponding subsections in the text, so that the reader can focus on and understand one piece at a time. Explain why your design makes sense as well as explaining how it works. Use diagrams, pseudo-code, and worked examples as appropriate.
• Analysis: Explain how you expect your design to behave in different scenarios. What scenarios might pose problems for performance or correctness? What do you expect to be the scalability limits of your design?
• Conclusion: Briefly summarize your design and provide recommendations for further actions and a list of any problems that must be resolved before the design can be implemented.
• Acknowledgments and references: Give credit to individuals whom you consulted in developing your design. Provide a list of references at the end using the IEEE citation-sequence system ("IEEE style") described in the Mayfield Handbook.
• Word count. Please indicate the word count of your report at the end of the document.

Here are a few tips:

• Use ideas and terms from the course notes when appropriate; this will save you space (you can refer the reader to the relevant section of the notes) and will save the reader some effort.
• Before you explain the solution to any given problem, say what the problem is.
• Before presenting the details of any given design component, ensure that the purpose and requirements of that component are well described.
• It's often valuable to illustrate an idea using an example, but an example is no substitute for a full explanation of the idea.
• You may want to separate the explanation of a component's data structures (or packet formats) from its algorithms.
• Explain all figures, tables, and pseudo-code; explain what is being presented, and what conclusions the reader should draw.

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:

• Clarity. Is the design described well enough to be understood, evaluated, and implemented?
• Correctness. Does the design achieve the requirements laid out in Section III? Does your report give a convincing analysis that your design works under the described scenario? Will the design be stable if the workload is slightly different from the described scenario?
• Simplicity. Is the level of complexity in the design justified