Latency and Capacity Optimal Broadcasting in Wireless Multihop Networks

In this paper, we study the fundamental properties of broadcasting in multi-hop wireless networks. Previous studies have shown that, as long as broadcast capacity is concerned, asymptotically optimal broadcasting is possible in wireless multi-hop networks under very general conditions. However, none of the existing work on broadcast capacity has considered latency in message delivery, which is simply assumed to be finite (but not explicitly bounded). In this paper, we address the issue of investigating the fundamental properties of broadcast communications for what concerns both capacity and latency using a realistic, SINR-based interference model. In particular, we introduce a novel topological notion of network connectivity, and show that, if the network satisfies this property, asymptotically optimal broadcast capacity and latency can be achieved simultaneously. This is in sharp contrast to similar results obtained for the case of unicast transmissions, where strictly bounded latency in message delivery can be achieved only at the expense of asymptotically reducing network capacity. Thus, the results presented in this paper show that scalable broadcasting in multi-hop wireless networks is, in principle, possible.