  We consider the adaptive routing problem in multihop wireless networks. The
link states are assumed to be random variables drawn from unknown
distributions, independent and identically distributed across links and time.
This model has attracted a growing interest recently in cognitive radio
networks and adaptive communication systems. In such networks, devices are
cognitive in the sense of learning the link states and updating the
transmission parameters to allow efficient resource utilization. This model
contrasts sharply with the vast literature on routing algorithms that assumed
complete knowledge about the link state means. The goal is to design an
algorithm that learns online optimal paths for data transmissions to maximize
the network throughput while attaining low path cost over flows in the network.
We develop a novel Online Learning for Shortest path and Backpressure (OLSB)
algorithm to achieve this goal. We analyze the performance of OLSB rigorously
and show that it achieves a logarithmic regret with time, defined as the loss
of an algorithm as compared to a genie that has complete knowledge about the
link state means. We further evaluate the performance of OLSB numerically via
extensive simulations, which support the theoretical findings and demonstrate
its high efficiency.
