Optimal Fault-tolerant Broadcasting in Wireless Mesh Networks
In: International Conference on High Performance Switching and Routing (HPSR'08), ed. by Min Song, Naoaki Yamanaka, Andrea Bianco, Yaohui Jin, pp. 151-157, IEEE press (ISBN: 978-1-4244-1982-1)
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 in advance based on full knowledge about the size and the topology of the network. We show that broadcasting can complete in $D+O(\log n)$ 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.