TITLE: Localized broadcasting with bounded number of redundant transmissions
SPEAKER: Majid Khabbazian (MIT)
PLACE: 32-G531
TIME:   1-2:30pm
DATE:   Friday May 8th, 2009


ABSTRACT:
One of the fundamental operations in wireless ad hoc networks is broadcasting,
where a wireless device (simply called node) disseminates a message to
all other
nodes in the network. A major challenge of efficient broadcast algorithms is to
reduce the number of transmissions required to disseminate a message.
Unfortunately, minimizing the total number of required transmissions is an
NP-hard problem even when the whole network topology is known by every node.
Reducing the number of transmissions becomes more challenging in
local broadcast algorithms, where each node makes decision
(whether or not to transmit a received message) based on local
neighborhood information.
In this talk, I describe a local broadcast algorithm and explain why it can
significantly reduce the number of transmissions required in a network wide
broadcast. In fact, it will be proven that the total number of transmissions
using the proposed broadcast algorithm is within a constant factor of
the minimum
number of required transmissions.