Colloquium Details

On the power of broadcast algorithms in wireless ad hoc networks

Speaker: Majid Khabbazian, MIT

Location: Warren Weaver Hall 1302

Date: April 29, 2009, 11:30 a.m.

Host: Michael Overton


Wireless ad hoc networks have emerged to support applications, in which it is required/desired to have wireless communications among a variety of devices without relying on any infrastructure or central management.

In ad hoc networks, wireless devices, simply called nodes, have limited transmission range. Therefore, each node can directly communicate with only those within its transmission range (i.e., its neighbors) and requires other nodes to act as routers in order to communicate with out-of-range destinations. One of the fundamental operations in wireless ad hoc networks is broadcasting, where a 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, we consider two general types of local broadcast algorithms and show whether they are able to reasonably reduce the total number of required transmissions under some different network model assumptions.


In-person attendance only available to those with active NYU ID cards.

How to Subscribe