Multi-hop broadcast from theory to reality: practical design for ad hoc networks

We propose a complete design for a scope limited, multi- hop broadcast middleware, which is adapted to the vari- ability of the ad-hoc environment and works in unlimited ad-hoc networks such as a crowd in a city, or car passen- gers in a busy highway system. We address practical prob- lems posed by: the impossibility to set the TTL correctly at all times, the poor performance of multiple access pro- tocols in broadcast mode, flow control when there is no ac- knowledgment and scheduling of multiple concurrent broad- casts. Our design, called “Self Limiting Epidemic Forward- ing” (SLEF), automatically adapts its behavior from single hop MAC layer broadcast to epidemic forwarding when the environment changes from being extremely dense to sparse, sporadically connected. A main feature of SLEF is a non- classical manipulation of the TTL field, which combines the usual decrement-when-sending to many very small decre- ments when receiving. SLEF is intended as a replacement of k-hop limited broadcast for the unlimited ad-hoc setting.