Project

The goal of the project is for you to learn what a MANET is and to understand the issues that must be addressed in a MANET; learn one MANET algorithm well; and to apply the techniques you have learned this semester to analyzing it.

Content of Project Paper

You will pick a distributed algorithm from one of the papers in the second table, below, model it; prepare a paper based on it; and make a presentation in class summarizing the paper.

Content of the paper:

  1. Overview of the algorithm.
    What problem does it solve?
    What is the basic idea?
    Informal description of the properties the algorithm should have.
  2. Specification of the algorithm.
    What messages do the nodes send and receive?
    What are the trace properties (safety and liveness)? These should be based on the properties you described in part 1.
  3. Your model.
  4. Either:
    a) One or more state invariants that can be used to prove the safety properties and their proofs.
    or
    b) A simulation relation relating your model to a model known to have the safety properties.
  5. An informal explanation of why the liveness properties hold.
  6. Derive upper bounds on the message complexity and time for the most important operation of the algorithm.

Background

You may find these references useful for background reading, but they are not acceptable as the basis of your project.

Author Title Link
Wikipedia Mobile ad-hoc network web
List of ad-hoc routing protocols web
Christian Maihofer A Survey of Geocast Routing Protocols pdf
F. Baker IETF draft: An Outsider's View of MANET text
I. Chakeres, J. Macker, and T. Clausen IETF draft: Mobile Ad hoc Network Architecture pdf
Jiang Wu Wireless Mobile Ad-hoc Network Protocols and Evaluation with Model Checking pdf

Project Papers

The following papers contain algorithms that you may model for your project. Some papers may have multiple algorithms, so you need to specify which you will use.

If you think one of the references in any of the articles, here or above, would also make an interesting project, please ask me about it.

SubjectAuthorsTitleLink
Multi-point relay Amir Qayyum, Laurent Viennot, Anis Laouiti
Multipoint relaying: An efficient technique for flooding in mobile wireless networks
Michael Byrd and Edgardo Molina
pdf
Neighbor Discovery Sudarshan Vasudevan, Jim Kurose, Don Towsley On Neighbor Discovery in Wireless Networks With Directional Antennas pdf
R. Madan and S. Lall
An energy-optimal algorithm for neighbor discovery in wireless sensor networks
Severin Ngosse and Daniel Rubin
pdf
T. Clausen, C. Dearlove, and J. Dean
MANET Neighborhood Discovery Protocol (NHDP)
Selcuk Cevher and Cagil Tasdemir
txt
Routing Charles E. Perkins and Elizabeth Royer
Ad hoc On-Demand Distance Vector (AODV) Routing
Mehmet Bicer and Chris Cheng
pdf
T. Clausen, P. Jacquet Ravi Kaushik and Ahsan Bushra
Optimized Link State Routing Protocol
pdf
David B. Johnson and David A. Maltz
Dynamic Source Routing in Ad Hoc Wireless Networks
Erdal Kose and Janusz Kusyk
pdf
Charles E. Perkins and Pravin Bhagwat
Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers
Terry Cook and Justin Tojeira
pdf
Brad Karp and H. T. Kung
GPSR: Greedy Perimeter Stateless Routing for Wireless Networks
Zeki Bilgin and Omer Demir
pdf
Address Allocation Zhihua Hu and Baochun Li
ZAL: Zero-Maintenance Address Allocation in Mobile Wireless Ad Hoc Networks
Suzanne Tamang and Mohammed Zahrani
pdf
Mansi Thoppian and Ravi Prakash
A Distributed Protocol for Dynamic Address Assignment in Mobile Ad Hoc Networks
Jeremy Seideman and Matt Meyer
pdf
Sanket Nesargi and Ravi Prakash
MANETconf: Configuration of Hosts in a Mobile Ad Hoc Network
Hao Tang and Zheng Chen
pdf