Robust Routing in Wireless Multi-Hop Networks

This paper introduces a robust approach to stochastic multi-hop routing for wireless networks when the quality of links is modelled through a reliability matrix R. Yielding to the practical constraint that link reliabilities have to be measured, we consider that R is random with known mean and variance. Thus, network utilities are also random quantities. Robust routing algorithms are then introduced to maximize an average utility subject to a variance constraint; or, alternatively, to minimize variance subject to a minimum utility yield. We prove that both problems can be solved by convex programming techniques. We further show that the robust routing optimization problems exhibit a separable structure enabling the proposal of routing protocols based on communication with one-hop neighbors only. Although the communication cost to compute the optimal routes is thus significantly reduced, we show that there is no performance penalty with respect to optimal routes computed by a centralized algorithm.