讨论组:网络科学组
标题:Distributed Multi-Message Broadcast in Wireless Ad-Hoc Networks under the SINR M
演讲人: 于东晓 University
时间: 2011-11-25 12:30-2011-11-25 14:00
地点: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.



人物介绍: