Group:Network Science Group
Title: Distributed Multi-Message Broadcast in Wireless Ad-Hoc Networks under the SINR M
Speaker: Dongxiao Yu University
Time: 2011-11-25 12:30-2011-11-25 14:00
Venue: FIT 1-222


 In the multi message broadcast, an arbitrary number of messages originate at arbitrary nodes in the network at arbitrary times. The problem is to disseminate all these messages to the whole network. This paper gives the first randomized distributed multi-message broadcast algorithm with worst-case performance guarantee in wireless ad-hoc networks employing the SINR interference model, which takes interference accumulation from all nodes in the network into account. The network model used in this paper also considers the harsh characteristics of wireless ad-hoc networks, such as no prior structure, no collision detection and nodes with little knowledge on the network topology. With all these rigorous restrictions, our proposed randomized distributed multi-message broadcast protocol can deliver any message $m$ to all nodes in the network in $O(D+k+\log^2n)$ timeslots with high probability, where $D$ is the network diameter, $k$ is the number of messages whose broadcast overlap $m$, and $n$ is the number of nodes in the network. We also study the lower bound for randomized distributed multi-message protocols. In particular, we prove that any uniform randomized algorithm needs $\Omega(D+k+\frac{\log^2n}{\log\log\log n})$ timeslots.

Short Bio: