Broadcast in Wireless Networks

(publications 4 and 7)
 Uncovered
 Covered once (optimal)
 Covered twice
 Covered thrice
 Covered four times
 Covered five or more times

Broadcast is a fundamental network operation allowing a source node to send a message to all other nodes in the network. In the context of networks where all communications are carried over a wireless medium and network nodes are limited in energy and computational power (e.g. sensor and mesh networks), an efficient broadcast mechanism is exceptionally important for the overall network performance. Similarly, a robust broadcast solution is required in networks where topology can change rapidly due to nodes' mobility (e.g. networks of unmanned aerial vehicles (UAVs), or interconnected wearable devices).

As part of this project, we present a new approach to efficient broadcast in networks with dynamic topologies, and we introduce the Time Sequence Scheme (TSS), a new online local broadcasting algorithm for such networking environments. TSS ranks by priority, in a distributed way, candidate broadcasting nodes so that the overall number of re-broadcasts in the network is minimized. TSS does not require GPS information to achieve about 20-30% better performance than state-of-the-art schemes. Currently, a GPS chip constitutes about 30% (or more) of a typical sensor node price (for instance Waspmote). The demo videos illustrate the performance of three versions of the TSS algorithm as implemented in the full protocol stack wireless network simulator JiST/SWANS. The nodes change color as a single message propagates in the network. The TSS algorithms are compared here against a standard flooding protocol. Note that NTSS is a Naive TSS implementation with some defficiencies (see our preprint for details). In the paper we compare extensively the performance of TSS to that of other broadcast algorithms and in variety of network settings. The latter include node mobility leading to temporary network partitioning during a broadcast session. Code and data available upon request.