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.
Refreshments will be offered starting 15 minutes prior to the scheduled start of the talk.