12:15PM, Thursday, May 24th 2007.
Gates 104

Routing and transport challenges in multi-hop wireless networks

Konstantinos Psounis
University of Southern California

About the talk:
Several kinds of multi-hop wireless networks have been proposed in the research literature: wireless mesh networks, an attractive choice for network access in rural communities, office buildings, etc., mobile ad hoc networks that may be intermittently-connected, useful to connect vehicles, underwater monitoring stations, handhelds, etc., and wireless sensor networks with various scientific and industrial applications. Despite the plethora of applications of such networks, low performance issues have prevented them from being widely adopted.

In this work we argue that the performance of multi-hop networks can be significantly improved by clean-slate designs at major network layers. We present two such case-studies. First, in the context of mobile ad hoc networks that may be intermittently connected, we propose to use node mobility to carry data around the network instead of transmitting them. The main motivation for this approach comes from the disconnected nature of some networks like vehicular and disaster ad hoc networks. Instead of resorting to flooding-based routing techniques, which lead to significant waste of resources and eventually to bad performance, we present a family of routing algorithms that spray a small, fixed number of copies to a carefully selected number of relays, and intelligently route each copy towards the destination. Realistic analysis and extensive simulations show that the proposed schemes are highly scalable, perform very close to an oracle-based optimal scheme, and, interestingly, outperform all existing practical schemes with respect to both delivery delay and number of transmissions per message delivered.

The second case-study investigates transport layer issues. The emphasis is on congestion control and fair rate allocation in the context of static nodes that may form a sensor or a mesh network. A central challenge to improving transport performance in such scenarios is to add contention-awareness. To understand what this means, consider two flows f1 and f2 that share no links or nodes, yet a node that forwards f1's data is within range of a node that forwards f2's data. In contention-based medium access layers, these two nodes would be prevented from transmitting simultaneously. Thus, to ensure that f1 and f2 can effectively contend for the medium, these nodes must detect that they interfere with each other, and exchange signals in case of congestion. With this in mind, we propose distributed, light weight algorithms that detect congestion, determine the exact set of nodes that contend with each other, and appropriately signal this set of nodes to ensure a fair and efficient rate allocation among the flows that traverse them. Analytical and experimental results with TinyOS motes show that the proposed algorithms ensure fairness and yield close to optimal rates.


About the speaker:
Konstantinos Psounis is an assistant professor of Electrical Engineering and Computer Science at the University of Southern California. He received his first degree from the department of Electrical and Computer Engineering of National Technical University of Athens, Greece, in June 1997, the M.S. degree in Electrical Engineering from Stanford University, California, in January 1999, and the Ph.D. degree in Electrical Engineering from Stanford University in December 2002.

Konstantinos models and analyzes the performance of a variety of networks, including the Internet, mobile ad hoc networks, delay and disruptive tolerant networks, sensor networks, mesh networks, peer to peer networks and the web. He also designs methods and algorithms to solve problems related to such systems. He is the author of more than 40 research papers on these topics. Konstantinos has received faculty awards from NSF and the Zumberge foundation, has been a Stanford graduate fellow throughout his graduate studies, and has received the best-student National Technical University of Athens award for graduating first in his class.