An Online Learning Approach to Shortest Path and Backpressure Routing in Wireless Networks

Abstract

We consider the problem of adaptive routing in wireless communication networks. The problem is investigated in the online learning context, where the link states are assumed to be random variables drawn from unknown distributions, independent and identically distributed across links and time. This setting has attracted a growing interest in recent years in cognitive radio networks and adaptive communication systems. In these networks, the devices (or nodes) are cognitive in the sense of learning the link states and updating the transmission parameters, to allow efficient utilization of the network resources. This model contrasts sharply with the vast literature on routing algorithms that assumed complete knowledge about the link state means. The objective is to develop an algorithm that learns online optimal paths to transmit the data so as to maximize the network throughput with low path cost over the network. This study makes significant contributions in terms of algorithm design, theoretical analysis with performance guarantees, and extensive numerical analysis to evaluate the algorithm’s performance. To achieve this goal, we present a novel algorithm, dubbed Online Learning for Shortest-path and Backpressure (OLSB). OLSB optimizes an objective function that balances between the cost and the load over paths. Since the path states are unknown, the design is based on a novel learning strategy that allows efficient adaptive path selections in OLSB. We evaluate the theoretical performance of OLSB by computing the regret, defined as the loss between OLSB and a genie which holds full information on the link state means. We analyze the performance of OLSB rigorously, and show that it achieves a logarithmic regret with time. Finally, extensive simulations are presented to evaluate the performance of OLSB numerically as well. The numerical results support the theoretical findings and demonstrate the high efficiency of OLSB.

Keywords

• Adaptive routing
• online learning
• cognitive radio networks
• shortest path
• backpressure