Events Calendar

Wireless Network Coding Algorithms

Speaker: Christina Fragouli,
School of Computer and Communication Sciences,
Swiss Federal Institute of Technology (EPFL), SwitzerlandAbstract: The paradigm of network coding allows intermediate nodes in a network to not only forward but also linearly combine their incoming information flows. This modern application of coding to the theory and practice of communication networks raises novel and exciting research problems, and is beginning to have an impact in diverse areas of network engineering that include multicasting, network monitoring, reliable delivery, resource sharing, efficient flow control and security.However, one of the main challenges is to enable network coding functionalities with implementable computational complexity. This aspect becomes particularly important in wireless networks where network coding can have a significant practical impact. We illustrate through two examples how algorithmic and combinatorial tools can be applied to make progress on this challenging question.We introduce the framework of vector network coding, which is applicable not only to graphs but also to deterministic models for wireless communications. We give the first polynomial time algorithms for unicast and multicast communication in such networks. Our unicast algorithm can be interpreted as an extension of the classical Ford-Fulkerson algorithm to deterministic networks. The framework of vector network coding generalizes the traditional scalar network coding, and thus offers a larger space of choices for optimizing cost parameters, such as the communication block length.Wireless sensor networks, require not only low-complexity operation, but also energy-efficient communication. There is a significant class of sensor-network applications, where the identities of the reporting sensors constitute the bulk of the communicated information, whereas the message itself can be as small as a single bit. We term this as identity-aware sensor networking, and re-examine the traditional message-identity separation, for such networks. We demonstrate that there can be a significant advantage (in terms of energy efficiency) to jointly encoding the messages and identity, instead of keeping them separate. We develop subspace coding methods that exploit this idea and give provable performance guarantees. We also translate our designs to networking protocols, and deploy them on a Tiny-OS sensor network testbed.Biography: Christina Fragouli is an Assistant Professor in the School of Computer and Communication Sciences, EPFL, Switzerland. She received the B.S. degree in Electrical Engineering from the National Technical University of Athens, Athens, Greece, in 1996, and the M.Sc. and Ph.D. degrees in electrical engineering from the University of California, Los Angeles, in 1998 and 2000, respectively. She has worked at the Information Sciences Center, AT&T Labs, Florham Park New Jersey, and the National University of Athens. She also visited Bell Laboratories, Murray Hill, NJ, and DIMACS, Rutgers University. From 2006 to 2007, she was an FNS Assistant Professor in the School of Computer and Communication Sciences, EPFL, Switzerland.Her research interests are in network information flow theory and algorithms, network coding, wireless sensor networks, and connections between communications, networking and computer science. She received the Fulbright Fellowship for her graduate studies, the Outstanding Ph.D. Student Award 2000-2001, UCLA, Electrical Engineering Department, the Zonta award 2008 in Switzerland, and the Young Investigator ERC grant award in 2009. She served as an editor for IEEE Communications Letters, and is currently serving as an editor for IEEE Transactions on Information Theory, IEEE Transactions on Communications and Elsevier Computer Communications. Host: Giuseppe Caire, caire@usc.edu, EEB 528, x04683

Location: Hughes Aircraft Electrical Engineering Center (EEB) - 248

Audiences: Everyone Is Invited

Contact: Gerrielyn Ramos