Optimal Fault-tolerant Broadcasting in Wireless Mesh Networks

Wireless Mesh Networks (WMNs) is an emerging communication paradigm to enable resilient, cost-efficient and reliable services for the future-generation wireless networks. In this paper, we study the broadcasting (one-to-all communication) in WMNs with known topology, i.e., where for each primitive the schedule of transmissions is precomputed based on full knowledge about the size and the topology of the network. We show that broadcasting can complete in D + O(logn) time units in the WMN with size n and diameter D. Furthermore, we explore the fault-tolerant broadcasting in WMN. We show an O(n)-time deterministic radio broadcasting schedule with large number of link failures. This is an optimal schedule in the sense that there exists a network topology in which the broadcasting cannot complete in less than Omega(n) units of time.