Multipoint Relaying for Flooding Broadcast Messages in Mobile Wireless Networks

Qayyum, Viennot, Laouiti

network routing multicast smf mpr

@inproceedings{qayyum:hicss-2002,
  title={Multipoint Relaying for Flooding Broadcast Messages in
         Mobile Wireless Networks},
  author={Qayyum, A. and Viennot, L. and Laouiti, A.},
  booktitle={Hawaii International Conference on
             System Sciences ({HICSS})},
  pages={3866--3875},
  year={2002},
  organization={IEEE}
}

'Multipoint Relaying for Flooding Broadcast Messages in Mobile Wireless Networks. Qayyum, Viennot, Laouiti. 2002 Hawaii International Conference in System Sciences.

• Introduces MPR as a technique for controlling the amount of traffic produced in a network-wide broadcast
  • techniques must tradeoff amount of control traffic generated versus savings (don't spend more than saved!)
• Very simple: Pick a minimal set of neighbor nodes that cover the 2-hop neighborhood
  • 2-hop neighborhood easily exchanged/determined w/ HELLO messages
  • Basic problem is NP Hard; reduction from dominating set used in proof here
  • Simple heurisitic used here: Choose relay nodes in order of number of 2-hop nodes covered, after choosing those required to reach 2-hops (single path to 2nd node)
    • Heuristic is log n optimal
• Works well in smiulations w/ unit disk graph under varying probabilities of success
  • Much less traffic, though less redundancy and therefore higher probability of failure (important)
• Good references to follow up on