Performance tradeoffs among percolation-based broadcast protocols in wireless sensor networks

Abstract

Broadcast of information in wireless sensor networks is an important operation, for example, for code updates, queries and membership information. In this paper, we analyse and experimentally compare the performance of vanilla versions of several well-known broadcast mechanisms: flooding, site percolation, bond percolation and modified bond percolation. While flooding and some percolation-based approaches have been compared in the literature, there is no all-to-all comparison among all schemes. We carry out our comparison for several network topologies defined by node locations: random, grid and clustered. Our analysis is performed at the link layer level, where we use a propagation model based on real experiments from the literature. The link model used is independent of the medium access control (MAC) layer and, therefore, helps us in arriving at the best possible values for the metrics that we compare in our analysis. Our main metrics are bandwidth, energy usage and broadcast latency. Our analytical and experimental results show that, given a desired high reliability for all topologies, flooding has the lowest latency but consumes the most energy per broadcast. For dense networks, site percolation achieves comparable latency and reliability to flooding, while lowering energy consumption. Modified bond percolation further lowers energy consumption compared to site percolation, while basic bond percolation leads to a latency increase. For sparse networks, results are similar to a dense network except that site percolation consumes lower energy than modified bond percolation. We briefly discuss implications for different broadcast applications.

Keywords:

• gossiping
• percolation
• code updates
• query propagation
• membership management
• broadcast

Acknowledgements

The authors would like to acknowledge NSF for supporting this work in part by the CAREER grant CNS 04-48246, in part by NSF ITR grant CMS 04-27089 and in part by the grant CNS 05-19817.