Opportunistic Routing in Wireless Networks: A Stochastic/Adaptive Control Approach

January 26, 2009
1306 Mudd
Speaker: Prof. Tara Javidi, University of California, San Diego


Opportunistic routing for multi-hop wireless networks has seen recent research interest to overcome deficiencies of traditional routing. Specifically, the routing decisions are made opportunistically, choosing the next relay based on the actual transmission outcomes in addition to an expected sense of future opportunities. First, we, briefly, cast opportunistic routing as a Markov decision problem (MDP) and introduce a stochastic variant of distributed bellman-ford which provides a unifying framework for almost all versions of opportunistic routing such as SDF, GeRaF, and EXOR.

To formulate and identify the optimal routing strategy, MDP formulations rely on the availability of probabilistic (Markov) models. However, a perfect probabilistic model of channel qualities and network topology is restrictive in practical network settings. In the second part of the talk, we provide sensitivity analysis and adaptive algorithms to deal with the estimation aspect of the problem when imperfect probabilistic model of channel qualities and network topology is available. Specifically, we provide a sensitivity analysis where the robustness of the proposed algorithms to modeling errors is investigated. Furthermore, we use a reinforcement learning framework to propose an adaptive opportunistic routing algorithm which minimizes the expected average cost per packet independently of the initial knowledge about the channel quality and statistics across the network.
Lastly and time permitting, we touch upon the issue of congestion and throughput optimality under various traffic conditions. We propose a combination of the previous MDP framework and backpressure routing to arrive at policies with significantly more desirable delay/throughput performance.


Tara Javidi studied electrical engineering at Sharif University of Technology, Tehran, Iran from 1992 to 1996. She received the MS degrees in electrical engineering (systems), and in applied mathematics (stochastics) from the University of Michigan, Ann Arbor. She received her Ph.D. in electrical engineering and computer science from the University of Michigan, Ann Arbor, in May 2002. From 2002 to 2004, Tara was an assistant professor of electrical engineering at the University of Washington, Seattle. She joined University of California, San Diego, in 2005, where she is currently an assistant professor of electrical and computer engineering. She was a Barbour Scholar during 1999-2000 academic year and received an NSF CAREER Award in 2004. Her research interests are in communication networks, stochastic resource allocation, and wireless communications.

500 W. 120th St., Mudd 1310, New York, NY 10027    212-854-3105               
©2014 Columbia University