Routing and transport challenges in multi-hop wireless networks

Konstantinos Psounis

EE and CS Depts. USC


Abstract: Several kinds of multi-hop wireless networks have been proposed in the research literature: wireless mesh networks, an attractive choice for network access, mobile ad hoc networks that may be intermittently-connected, useful to connect vehicles, 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 are intermittently connected, we propose to use node mobility to carry data and bridge disconnected clusters of nodes. 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 bad performance, we present a family of routing algorithms that spray a small number of copies to a carefully selected number of relays, and intelligently route each copy towards the destination. Realistic analysis is used to optimize various aspects of the proposed schemes. The analysis, coupled with extensive simulations, also shows that the proposed schemes are highly scalable, perform very close to an oracle-based optimal scheme, and, interestingly, achieve the lowest delay while using the least amount of resources over all existing practical schemes.

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 consider node-contention for the common medium and handle congestion at a neighborhood level rather than at an individual-node level. 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 results that compute the optimal rates in a contention-based multi-hop wireless network (an interesting result on its own right) coupled with experimental results with TinyOS motes show that the proposed algorithms ensure fairness and yield close to optimal rates.


Bio: 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.


Wednesday, February 20

4:00-5:00 p.m.

EECS 1003