Comparison of Broadcasting Techniques for Mobile Ad Hoc Networks

Williams, Camp

network routing multicast smf mpr

@inproceedings{williams:smanetc-2002,
  title={Comparison of Broadcasting Techniques for Mobile Ad Hoc Networks},
  author={Williams, B. and Camp, T.},
  booktitle={{ACM} International Symposium on
             Mobile Ad Hoc Networking \& Computing},
  pages={194--205},
  year={2002},
  organization={ACM}
}

Comparison of Broadcasting Techniques for Mobile Ad Hoc Networks. Williams, Camp. MOBIHOC 2002.

• Broadcasting is a necessary component of many unicast protocols, frequently used for disseminating topology or route information
• No 802.11 RTS/CTS for broadcast traffic
• Must jitter scheduling of broadcast packets; otherwise we all talk at the same time
• Should discard queued packets if receive duplicate
  • How feasible/easy is this?
  • Alternatively, keep the packet at the network layer as long as possible
• Four families of techniques: Simple Flooding, Probability Based Methods, Area Based Methods, Neighbor Knowledge Methods
  • Simple flooding: Rebroadcast all packets
  • Probabilistic: Rebroadcast with pre-determined probability
    • Counter-Based Scheme: Probability I'll gain additional coverage is inversely proportional to number of times I've received packet; base retransmit prob on that
  • Area Based Methods: Distance-Based (based on signal strength), Location-Based(based on coordinates); only retransmit if covering significant additional (geographic) area
  • Neighbor Knowledge Methods; key distinguishing characteristic: self-election or explicit upstream pointing
  • Self-pruning: Compare neighbor lists; if equivalent, don't retransmit
  • Scalable Broadcast Algorithm: Examine neighbor list w/ neighbor list from received node; forward if differ; check each time a dupe is received
  • Dominant Pruning: Difference w/ MPR?
  • MPR: Choose neighbors best covering 2-hop neighborhood
  • Ad Hoc Broadcast Protocol: Same as MPR, except done per-packet, removes from consideration nodes in neighborhood known to have received same transmission, assumse relay if no info received (i.e. no HELLOs exchanged yet)
  • CDS-Based Broadcast Algorithms: Similar to AHBP, but takes into account coverage of MPRs
  • LENWB: Self-elect to rebroadcast based on priority, which is based on number of neighbors
• Simulation properties: Node density, mobility, traffic rates
• In sparse networks, performance approachs flooding; should do better as density increases; best case is Minimum Connected Dominating Set
  • Set of nodes are connected, all non-set nodes are within one-hop of at least one member of the set
  • Remember: Minimizing transmissions is not only thing here; ensuring delivery is also important
• Four studies: W/ no MAC, with congestion, with mobility, combined density, congestion, mobility
  • Study 2: Small and fixed packet size (as with most broadcast traffic), varying packet rates
• MCDS only increases with network area, not density
• Protocols minimizing redundant transmission deliver the most in congested networks
• In high mobility, explicit selection can falter when selected nodes are gone. Can lower HELLO frequency, but that increases overall transmissions. Can work out that implicit schemes work better.
• Have to adjust wait-for-duplicate intervals to account for congestion
• Good references