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

Abstract

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 problems posed by: the impossibility to set the TTL correctly at all times, the poor performance of multiple access protocols in broadcast mode, flow control when there is no acknowledgment and scheduling of multiple concurrent broadcasts. Our design, called Self Limiting Epidemic Forwarding (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.