id: Simula.ND.104
authors: Qin Xin and Yan Zhang
title: Optimal Fault-tolerant Broadcasting in Wireless Mesh Networks
publication_year: 2008
abstract: 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.
publication_url: 
pdf_url: 
booktitle: International Conference on High Performance Switching and Routing (HPSR'08)
editor: Min Song, Naoaki Yamanaka, Andrea Bianco, Yaohui Jin
volume: 
number: 
chapter: 
pages: 151-157
publisher: IEEE press
organization: 
address: 
edition: 
series: 
isbn: 
keywords: ()
publication_month: May
note: 
annote: 
additional: []
location: 
publication_state: Published
simula_ou: [<Department at /simula/department/netsys>, <Department at /simula/research/win>, <Department at /simula/research/telco>]
publisher_url: 
category: Conference
from_date: 2008/05/15 00:00:00 GMT+2
to_date: 2008/05/17 00:00:00 GMT+2