Why Flooding is Unreliable in Multi-hop, Wireless Networks
Rachel Cardell‐Oliver · 2004
This paper examines the unreliability of the flooding protocol - a simple broadcast protocol for delivering a message to all nodes in a multi-hop, wireless network. The protocol is unreliable in that there exist protocol runs in which some network nodes fail to receive the message. A formal specification of the behaviour of a multi-hop network is used to characterize configurations that lead to failure, and to prove unreliability. The specification is also used for simulation, to analyse the percentage of runs that fail to reach all nodes, and the cost and eciency of flooding. The protocol’s performance is examined for dierent network topologies, radio transmission properties and protocol retransmission rules. Our results establish a fundamental limit on the reliability of protocols such as flooding, and show how networks can be configured to optimise reliability, cost and eciency. The formal specification provides a basis for future simulation and verification studies of a wide range of protocols for multi-hop, wireless networks and for modelling energy use, node mobility, and other interactions between nodes and their environment.