Towards Optimal Broadcast in Wireless Networks

Broadcast is a fundamental operation in networks, especially in reconfigurable wireless ad hoc networks. For example, some form of broadcasting is used by all on-demand mobile networks routing protocols, when there is uncertainty as to the location of the destination node, or for service discovery. In this work, 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. We evaluate TSS, showing that its performance comes remarkably close to the corresponding theoretical performance bounds, even in the presence of packet loss due, for example, to MAC-layer collisions. Furthermore, we compare our algorithm with a number of recently proposed schemes considering their performance in various realistic network mobility scenarios. We demonstrate that TSS performance is robust in the context of mobility induced topology reconfigurations-including temporal network partitioning-during propagation of the broadcast message.