The flooding test
Objective
The objective of this test is to ascertain your suitability as a research
student for the WALAN research lab.
The Problem
One of the main problems in ad hoc networks is the flooding of
information. By flooding we understand the network-wide disemination
of information from one node to all the other nodes (since not all
nodes are in the range of each other, a simple broadcast is not
sufficient). Many popular ad-hoc routing protcol (including AODV and
DSR) rely on flooding for route discovery. Other types of information
(e.g., node position, the existence and status of the neighbors for
link state protocols, etc.) may also need to be diseminated through
flooding.
The main problem with flooding is that it tends to be quite expensive
in terms of bandwidth. Your goal is to reduce the expense associated
with flooding.
Your Solution
Start by doing a literature review on
existing methods on reducing the cost of flooding. Notice that many
times, the flooding problem is called broadcast storm
.
Once you are sure you understand the problem and existing solution,
try to find a better solution. It doesn't have to be a super-general
solution. You are allowed make simplifying assumptions (e.g., all
nodes are fixed, all nodes have the same transmission ranges, or all
links are bidirectional). However, make sure that you do not
oversimplify (e.g., assuming that you have less than 10 nodes or that
all nodes can hear each other is an oversimplification).
Finally, once you develop the better solution, you have to prove it
that it is better than existing solutions (at the very least better
than the brute force solution). You can use any technique (or
combination) for this proof: analytical, C/Matlab program, network
simulation, etc.
Report
The organization of the final project report should resemble a
research paper. There is no page limit, but I certainly value short
reports that yet do not leave out important
details.
I suggest that the report should have the following
sections (you can adjust within reason according to taste):
Abstract - 150 - 400 words, self contained paragraph that
summarizes the report. It should answer "What?" "Why?" and
"How?" you did what you did.
Introduction Introduction to the problem of
interest. What is the problem? Why is the problem
important? What are possible applications? Very briefly
what is your contribution.
Related work Present briefly (one paragraph/paper) what
others did in the areas related to this problem. Make
sure to emphasize for each paper how you solution is
different from existing approaches. The more
comprehensive, the better. Finish the section by
re-emphasizing the difference between your
contribution and existing approaches.
Problem formulation, or Model Explain your ad hoc network
model you used. Make sure to list all assumptions (e.g.,
fixed transmission radius, wireless propagation model,
etc.).
Proposed solution In this section describe your proposed
solution. If it's a protocol, a finite state machine and packet format
might help.
Evaluation or Simulation Results In this section present
the evaluation of your proposed solution.
Please do not dump an inordinate amount
of data. It is an art to present the data in such a way
to yield maximum insight into a phenomenon. Do not expect
that the reader will read through three pages of data to
notice an interesting phenomenon. Most of the time graphs
are preferred to tables.
You should also analyze the results from your evaluation/simulation.
All
features (absolute values, relative values, variations,
irregularities, minimums, etc.) should be explained. You
should be confident in the explanations, and have the data
to back-up your confidence. "Maybe", "probably" and
"perhaps" should not exist in this section.
Conclusion Summarize the problem, solution and your findings,
pointing to anything out of the ordinary.
Appendices Include here anything that is not essential to the flow
of your report (e.g. theorem proofs, supplementary
data, implementation considerations, etc.)
Last modified: Fri Aug 13 13:16:54 EDT 2004