Title: On the Construction of Virtual Backbone in Wireless Ad hoc Networks.

Speaker: Prof. My Tra Thai


Room: NEB 101

Time: 4:05pm - 5:05pm


Abstract:
 
Since there is no fixed or pre-defined infrastructure in wireless ad
hoc networks,
Connected Dominating Set (CDS) has been proposed as the virtual
backbone for efficient routing, broadcasting and collision avoidance
protocols. With the help of the CDS, routing is easier and can adapt
quickly to network topology changes. Furthermore, using a CDS as the
number of forwarding nodes can efficiently reduce the energy
consumption, which is also one of the critical issues in wireless ad
hoc networks.
 
This talk will discuss the design and analysis of constructing a CDS
in many layers. At first, we will consider how to construct a 1-CDS
for homogeneous networks. Next, we will present a mathematical model
and approximation algorithms for 1-CDS in heterogeneous networks.
Finally, we will discuss the solutions to a fault tolerant CDS, which
is k-connected m-dominating set. All of these approximation algorithms
guarantee a constant factor.
 
Bio:
 
My T. Thai obtained a PhD degree in computer science from the
University of Minnesota, Twin Cities, in 2005. She is now an assistant
professor in the department of Computer and Information Sciences and
Engineering at the University of Florida. Her main research interests
include combinatorics, algorithms, wireless networks, and
computational biology. In particular, she is interested in developing
and analyzing algorithms for many computationally hard problems in
computer networks and computational biology. Her work has covered many
areas of wireless networks and computational biology, including
routing protocols, coverage in sensor networks, broadcast tree,
virtual backbone, nonadaptive group testing, and non-unique probe
selection. She serves as one of the editors for the book, entitled
"Wireless Sensor Networks and Applications" and also an editor of the
Journal of Optimization Letters.