Virtual Backbone in Wireless Networks: Algorithms and Analysis

My Thai, PhD
Department of Computer Science and Engineering
University of Minnesota
www.cs.umn.edu/~mythai

Abstract

Wireless ad hoc networks, including wireless sensor networks, can be flexibly and quickly deployed for many applications, both in military and civil. There is no fixed or pre-defined infrastructure in these networks. Virtual backbone has been proposed as routing infrastructure to alleviate the broadcasting storm problem as well as to reduce the energy consumption in communication. It is possible to approximate a virtual backbone by using a Connected Dominating Set (CDS) concept in graph theory. The problem of finding a minimum CDS is NP-hard. This talk describes several novel approximation algorithms and their performance analysis for different network scenarios. For the homogeneous networks, i.e., all nodes have the same transmission ranges, we model them as unit disk graphs and propose the best performance ratio algorithm. For the heterogeneous networks, i.e., nodes have different transmission ranges, we model them as disk graphs where the underline graph is directed and introduce a strongly CDS problem in disk graphs. Based on this novel model, this talk also presents an efficient algorithm with a constant performance ratio. This work is also the first work identifying the CDS in asymmetric networks.

Candidate Bio

My Thai received her B.S. degrees in both Computer Science and Mathematics majors from Iowa State University in 1999. She obtained her Ph.D. degree in Computer Science from University of Minnesota in December, 2005. Her research interests are centered on the design and analysis of algorithms and protocols for many combinatorial optimization problems in Computer Networks and Computational Biology, including wireless networks, wireless sensor networks, group testing, and biological networks. She has published more than 15 research papers in various prestigious journals and conferences, such as IEEE Transactions on Mobile Computing, IEEE Transactions on Wireless Communications, Journal of Combinatorial Optimization, and INFOCOM conference. She is also an editor of the book, entitled "Advances in Wireless Sensor Networks."