Latency and Capacity Optimal Broadcasting in Wireless Multi-Hop Networks with Arbitrary Number of Sources

This paper studies 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 {em latency} in message delivery, which is simply assumed to be finite (but not explicitly bounded). In this paper, the issue of investigating the fundamental properties of broadcast communications for what concerns {em both} capacity {em and} latency using a realistic, SINR-based interference model is investigated. In particular, a novel topological notion of network connectivity is introduced, and it is shown that, if the network satisfies this property, asymptotically optimal broadcast capacity and latency {em can be achieved simultaneously}. The above result holds in the general scenario in which an arbitrary number of broadcast sources arbitrarily share the available (optimal) network capacity. The result presented in this paper is in sharp contrast to similar results obtained for the case of unicast transmissions, where asymptotically optimal 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.